Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-10-20 08:00:17 

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008 
0009 #include <boost/test/unit_test.hpp>
0010 
0011 #include "Acts/Utilities/Helpers.hpp"
0012 #include "Acts/Utilities/KDTree.hpp"
0013 #include "Acts/Utilities/RangeXD.hpp"
0014 
0015 #include <algorithm>
0016 #include <array>
0017 #include <cstddef>
0018 #include <iterator>
0019 #include <string>
0020 #include <utility>
0021 #include <vector>
0022 
0023 namespace {
0024 std::vector<std::pair<std::array<double, 3>, int>> test_vector{
0025     {{-8.5, 2.3, -1.6}, 84},   {{-9.7, -1.4, 7.6}, -56},
0026     {{6.4, 2.7, -1.0}, -94},   {{-2.2, -9.3, 3.6}, 56},
0027     {{-9.2, -2.8, -2.5}, -90}, {{3.8, 0.9, 7.2}, 43},
0028     {{7.6, 1.9, -1.0}, 83},    {{2.1, -1.6, -1.7}, -15},
0029     {{5.2, 3.2, -1.3}, 14},    {{-6.0, -7.5, 6.5}, 48},
0030     {{3.5, -7.1, -4.4}, 83},   {{5.0, 6.9, -0.7}, 1},
0031     {{8.0, 0.2, 3.8}, 69},     {{2.5, 0.8, 4.1}, -11},
0032     {{-1.5, -6.6, 8.4}, -98},  {{0.8, 6.1, 2.7}, 14},
0033     {{5.1, -5.1, 5.8}, 46},    {{-9.6, 0.7, 0.3}, 59},
0034     {{-8.8, 1.3, -9.8}, -19},  {{-7.5, -9.3, -2.2}, 6},
0035     {{-5.3, 1.9, -3.9}, 57},   {{-4.8, -9.8, -0.2}, 73},
0036     {{-6.3, -7.4, 9.2}, -94},  {{-4.8, -9.8, -2.6}, 77},
0037     {{2.4, 4.9, -8.4}, -72},   {{8.4, 6.1, -7.7}, -66},
0038     {{6.1, -8.2, 9.3}, 67},    {{9.4, 7.4, 7.5}, -99},
0039     {{9.4, 1.8, -4.4}, -87},   {{9.0, -3.7, 6.3}, -12},
0040     {{-1.8, 2.8, 6.3}, 71},    {{-7.6, 7.6, -4.5}, -77},
0041     {{-7.7, -1.2, 7.7}, -92},  {{-6.9, -0.5, -6.6}, -61},
0042     {{0.9, 5.7, 0.5}, 60},     {{-0.3, 3.7, -7.0}, 15},
0043     {{5.3, -0.6, -6.6}, 46},   {{-6.9, -3.0, 4.1}, -13},
0044     {{1.8, -6.5, 1.8}, -29},   {{1.4, -7.8, -0.3}, 100},
0045     {{8.2, 0.1, -7.6}, 69},    {{6.5, -9.1, 6.6}, -61},
0046     {{4.2, 6.6, -0.7}, 56},    {{8.6, -3.1, -6.8}, -88},
0047     {{9.7, -6.0, 2.9}, -44},   {{7.0, -3.2, 9.8}, 29},
0048     {{-6.1, 3.3, -3.0}, 54},   {{-2.6, 7.6, -4.2}, -52},
0049     {{-5.9, 7.8, 5.1}, -81},   {{0.6, 5.3, -2.5}, -69},
0050     {{-8.5, 1.8, 6.0}, 56},    {{6.4, 2.0, -6.8}, -14},
0051     {{-9.0, -2.1, 8.0}, 84},   {{7.0, 0.1, 6.3}, -17},
0052     {{8.0, 4.5, -0.8}, -85},   {{-5.5, 9.2, 7.5}, 13},
0053     {{-3.8, 2.1, 3.4}, 19},    {{-8.0, -5.2, 9.5}, -25},
0054     {{6.2, 6.0, -2.2}, 81},    {{5.1, -5.1, -9.7}, 74},
0055     {{-1.3, -9.0, 8.1}, -74},  {{5.4, -0.8, 2.4}, 32},
0056     {{-5.6, 3.8, 6.2}, 73},    {{8.9, -3.8, -7.8}, 93},
0057     {{7.7, 0.4, -2.9}, 78},    {{-6.9, -1.5, -3.3}, -75},
0058     {{-5.3, 2.5, -3.6}, 48},   {{-6.6, -9.2, -2.1}, -7},
0059     {{5.5, -7.7, 2.0}, 3},     {{4.1, -9.5, -6.9}, 82},
0060     {{-2.3, -0.2, -0.7}, -3},  {{2.3, 0.4, -5.5}, 43},
0061     {{5.0, 4.0, 9.0}, 59},     {{-8.7, -4.0, 1.0}, -17},
0062     {{7.6, -7.6, -7.9}, 18},   {{4.2, 6.3, -4.4}, 2},
0063     {{8.6, -6.3, 3.5}, -75},   {{9.8, 7.3, 0.1}, 8},
0064     {{-2.2, 9.3, -6.2}, -54},  {{-0.9, -0.4, 1.4}, 45},
0065     {{-5.3, 6.7, 7.6}, 20},    {{-2.7, 2.4, 8.8}, 42},
0066     {{9.3, -0.0, 9.1}, -84},   {{0.5, 1.5, -2.3}, -47},
0067     {{7.5, -5.7, 1.3}, 21},    {{0.4, 0.4, -2.0}, 50},
0068     {{0.8, -6.2, -7.7}, 46},   {{5.1, -7.3, -0.7}, 26},
0069     {{9.7, 2.8, 9.6}, 80},     {{7.3, -2.1, -6.7}, -91},
0070     {{-9.4, -5.3, -3.1}, -24}, {{-2.4, -1.6, -0.2}, -88},
0071     {{-9.9, -5.9, 0.0}, -90},  {{1.3, -3.0, 9.8}, 72},
0072     {{0.9, -6.8, -2.7}, 92},   {{-1.7, -3.8, 2.8}, -78},
0073     {{-6.4, -0.6, -0.6}, 95},  {{-4.7, 4.8, -8.0}, 95},
0074     {{-6.0, 3.5, -7.4}, 7},    {{3.2, -6.2, 3.9}, -25}};
0075 }
0076 
0077 using namespace Acts;
0078 
0079 namespace ActsTests {
0080 
0081 struct TreeFixture1DDoubleInt1 {
0082   TreeFixture1DDoubleInt1()
0083       : tree(std::vector<std::pair<std::array<double, 1>, int>>{
0084             {{1.0}, 5}, {{2.0}, 6}, {{-1.2}, 2}, {{0.9}, 10}}) {}
0085 
0086   KDTree<1, int, double> tree;
0087 };
0088 
0089 struct TreeFixture1DDoubleInt2 {
0090   TreeFixture1DDoubleInt2()
0091       : tree(std::vector<std::pair<std::array<double, 1>, int>>{
0092             {{1.0}, 5},
0093             {{2.0}, 6},
0094             {{-1.2}, 2},
0095             {{0.9}, 10},
0096             {{-10.0}, 9},
0097             {{110.0}, 1},
0098             {{-1000.0}, 3}}) {}
0099 
0100   KDTree<1, int, double> tree;
0101 };
0102 
0103 struct TreeFixture2DDoubleInt1 {
0104   TreeFixture2DDoubleInt1()
0105       : tree(std::vector<std::pair<std::array<double, 2>, int>>{
0106             {{1.0, 5.0}, 5}, {{2.0, -2.5}, 6}}) {}
0107 
0108   KDTree<2, int, double> tree;
0109 };
0110 
0111 struct TreeFixture3DDoubleInt1 {
0112   TreeFixture3DDoubleInt1()
0113       : tree(std::vector<std::pair<std::array<double, 3>, int>>{
0114             {{-4.7, -2.0, -1.7}, 63}, {{8.2, -0.0, 9.5}, -82},
0115             {{7.1, -3.6, -4.0}, -49}, {{-9.9, -4.6, 2.9}, 86},
0116             {{5.0, -3.8, -2.8}, -12}, {{-4.8, -1.8, -1.6}, -60},
0117             {{8.8, 9.6, -0.2}, 60},   {{7.6, 1.9, 8.8}, 74},
0118             {{9.0, -6.9, -6.2}, 35},  {{4.3, 7.5, -2.0}, 19},
0119             {{-7.7, 3.7, 7.1}, -54},  {{3.4, 7.4, -4.0}, -8},
0120             {{8.5, 3.0, -3.2}, -48},  {{6.5, -0.3, -3.1}, -25},
0121             {{6.9, -6.6, -8.0}, -4},  {{6.8, 5.5, -2.5}, 17},
0122             {{-2.8, 8.8, -7.2}, 62},  {{-0.1, 3.5, 5.5}, -95},
0123             {{-1.3, 6.9, 5.3}, -23},  {{6.2, 6.6, 7.1}, -84}}) {}
0124 
0125   KDTree<3, int, double> tree;
0126 };
0127 
0128 struct TreeFixture3DDoubleInt2 {
0129   TreeFixture3DDoubleInt2()
0130       : tree(std::vector<std::pair<std::array<double, 3>, int>>(test_vector)) {}
0131 
0132   KDTree<3, int, double> tree;
0133 };
0134 
0135 struct TreeFixture3DDoubleInt3 {
0136   TreeFixture3DDoubleInt3()
0137       : tree(std::vector<std::pair<std::array<double, 3>, int>>{
0138             {{-100.0, -1.1, -1.7}, 0},
0139             {{100.0, -0.0, 9.5}, 4},
0140             {{-100.0, -0.6, -1.0}, 1},
0141             {{100.0, -4.6, 2.9}, 5},
0142             {{-100.0, -1.4, -2.8}, 2},
0143             {{100.0, -1.8, -1.6}, 6},
0144             {{-100.0, -1.0, -0.2}, 3},
0145             {{100.0, 1.9, 8.8}, 7}}) {}
0146 
0147   KDTree<3, int, double> tree;
0148 };
0149 
0150 struct TreeFixture10DDoubleInt1 {
0151   TreeFixture10DDoubleInt1()
0152       : tree(std::vector<std::pair<std::array<double, 10>, int>>{
0153             {{5.6, 7.5, -9.8, 9.6, 3.3, -7.3, 2.0, 4.7, -2.1, 5.9}, 32},
0154             {{1.2, -1.5, -0.2, 0.9, 1.1, -1.4, -8.9, -1.2, -9.0, 7.4}, -66},
0155             {{1.6, 6.2, 9.9, -2.5, 4.0, 8.9, 3.9, 8.4, -1.2, -4.1}, -51},
0156             {{0.7, -5.7, -3.1, 5.4, 0.6, -8.7, 0.2, -0.2, 0.3, -2.7}, -19},
0157             {{-5.0, -5.5, -7.1, 9.2, 5.5, 0.7, 9.9, -7.0, -6.8, 3.1}, 27},
0158             {{0.4, 5.5, -5.8, -3.0, 6.0, -7.3, 2.1, 7.9, -8.0, -6.9}, -13},
0159             {{-2.3, -5.9, 9.0, 1.4, 4.6, 3.4, -9.5, -6.3, 3.3, -7.0}, 97},
0160             {{8.1, 3.6, -8.6, -0.4, 7.5, 10.0, -3.9, -5.8, -2.9, 9.8}, 15},
0161             {{8.4, -4.0, 6.3, 1.1, -5.7, 8.1, -8.0, -2.5, -0.5, 3.2}, -56},
0162             {{2.3, 5.8, 1.4, 4.0, 9.0, -6.4, 1.0, -7.8, 4.3, -5.3}, -83}}) {}
0163 
0164   KDTree<10, int, double> tree;
0165 };
0166 
0167 struct TreeFixture3DDoubleString1 {
0168   TreeFixture3DDoubleString1()
0169       : tree(std::vector<std::pair<std::array<double, 3>, std::string>>{
0170             {{-0.2, -0.2, -3.8}, "string0"},
0171             {{4.9, -7.8, -10.0}, "string1"},
0172             {{3.5, -10.0, -8.1}, "string2"},
0173             {{8.2, -6.1, 2.0}, "string3"},
0174             {{-9.9, 7.7, -1.4}, "string4"},
0175             {{-2.2, 2.1, 8.6}, "string5"},
0176             {{-6.9, -5.8, 5.3}, "string6"},
0177             {{-0.7, 0.9, -6.5}, "string7"},
0178             {{-2.7, -5.9, -7.3}, "string8"},
0179             {{3.1, -9.4, -2.5}, "string9"}}) {}
0180 
0181   KDTree<3, std::string, double> tree;
0182 };
0183 
0184 struct TreeFixture1DIntInt1 {
0185   TreeFixture1DIntInt1()
0186       : tree(std::vector<std::pair<std::array<int, 1>, int>>{
0187             {{1}, 5}, {{2}, 6}, {{-1}, 2}, {{5}, 10}}) {}
0188 
0189   KDTree<1, int, int> tree;
0190 };
0191 
0192 struct TreeFixture2DIntInt1 {
0193   TreeFixture2DIntInt1()
0194       : tree(std::vector<std::pair<std::array<int, 2>, int>>{
0195             {{1, 7}, 5}, {{2, 1}, 6}, {{-1, -11}, 2}, {{5, -2}, 10}}) {}
0196 
0197   KDTree<2, int, int> tree;
0198 };
0199 
0200 BOOST_AUTO_TEST_SUITE(UtilitiesSuite)
0201 
0202 BOOST_AUTO_TEST_SUITE(KDTreeSuite)
0203 
0204 BOOST_FIXTURE_TEST_CASE(size_1, TreeFixture1DDoubleInt1) {
0205   BOOST_CHECK_EQUAL(tree.size(), 4);
0206 }
0207 
0208 BOOST_FIXTURE_TEST_CASE(size_2, TreeFixture1DDoubleInt2) {
0209   BOOST_CHECK_EQUAL(tree.size(), 7);
0210 }
0211 
0212 BOOST_FIXTURE_TEST_CASE(size_3, TreeFixture2DDoubleInt1) {
0213   BOOST_CHECK_EQUAL(tree.size(), 2);
0214 }
0215 
0216 BOOST_FIXTURE_TEST_CASE(size_4, TreeFixture3DDoubleInt1) {
0217   BOOST_CHECK_EQUAL(tree.size(), 20);
0218 }
0219 
0220 BOOST_FIXTURE_TEST_CASE(size_5, TreeFixture10DDoubleInt1) {
0221   BOOST_CHECK_EQUAL(tree.size(), 10);
0222 }
0223 
0224 BOOST_FIXTURE_TEST_CASE(size_6, TreeFixture3DDoubleString1) {
0225   BOOST_CHECK_EQUAL(tree.size(), 10);
0226 }
0227 
0228 BOOST_FIXTURE_TEST_CASE(size_7, TreeFixture1DIntInt1) {
0229   BOOST_CHECK_EQUAL(tree.size(), 4);
0230 }
0231 
0232 BOOST_FIXTURE_TEST_CASE(size_8, TreeFixture3DDoubleInt2) {
0233   BOOST_CHECK_EQUAL(tree.size(), 100);
0234 }
0235 
0236 BOOST_FIXTURE_TEST_CASE(range_search_1, TreeFixture1DDoubleInt2) {
0237   RangeXD<1, double> range;
0238   range[0].shrink(0.0, 2.5);
0239 
0240   std::vector<int> result = tree.rangeSearch(range);
0241   BOOST_CHECK_EQUAL(result.size(), 3);
0242   BOOST_CHECK(rangeContainsValue(result, 5));
0243   BOOST_CHECK(rangeContainsValue(result, 6));
0244   BOOST_CHECK(rangeContainsValue(result, 10));
0245   BOOST_CHECK(!rangeContainsValue(result, 7));
0246   BOOST_CHECK(!rangeContainsValue(result, 2));
0247   BOOST_CHECK(!rangeContainsValue(result, 9));
0248 }
0249 
0250 BOOST_FIXTURE_TEST_CASE(range_search_2, TreeFixture1DDoubleInt2) {
0251   RangeXD<1, double> range;
0252   range[0].shrink(-10000.0, 10000.0);
0253 
0254   std::vector<int> result = tree.rangeSearch(range);
0255   BOOST_CHECK_EQUAL(result.size(), 7);
0256   BOOST_CHECK(rangeContainsValue(result, 1));
0257   BOOST_CHECK(rangeContainsValue(result, 2));
0258   BOOST_CHECK(rangeContainsValue(result, 3));
0259   BOOST_CHECK(rangeContainsValue(result, 5));
0260   BOOST_CHECK(rangeContainsValue(result, 6));
0261   BOOST_CHECK(rangeContainsValue(result, 9));
0262   BOOST_CHECK(rangeContainsValue(result, 10));
0263 }
0264 
0265 BOOST_FIXTURE_TEST_CASE(range_search_3, TreeFixture1DDoubleInt2) {
0266   RangeXD<1, double> range;
0267   range[0].shrink(5000.0, 10000.0);
0268 
0269   std::vector<int> result = tree.rangeSearch(range);
0270   BOOST_CHECK_EQUAL(result.size(), 0);
0271 }
0272 
0273 BOOST_FIXTURE_TEST_CASE(range_search_4, TreeFixture2DDoubleInt1) {
0274   RangeXD<2, double> range;
0275   range[0].shrink(0.0, 10.0);
0276   range[1].shrink(0.0, 10.0);
0277 
0278   std::vector<int> result = tree.rangeSearch(range);
0279   BOOST_CHECK_EQUAL(result.size(), 1);
0280   BOOST_CHECK(rangeContainsValue(result, 5));
0281 }
0282 
0283 BOOST_FIXTURE_TEST_CASE(range_search_5, TreeFixture2DDoubleInt1) {
0284   RangeXD<2, double> range;
0285   range[0].shrink(0.0, 10.0);
0286   range[1].shrink(-10.0, 10.0);
0287 
0288   std::vector<int> result = tree.rangeSearch(range);
0289   BOOST_CHECK_EQUAL(result.size(), 2);
0290   BOOST_CHECK(rangeContainsValue(result, 5));
0291   BOOST_CHECK(rangeContainsValue(result, 6));
0292 }
0293 
0294 BOOST_FIXTURE_TEST_CASE(range_search_6, TreeFixture10DDoubleInt1) {
0295   RangeXD<10, double> range;
0296   range[0].shrink(0.0, 5.0);
0297 
0298   std::vector<int> result = tree.rangeSearch(range);
0299   BOOST_CHECK_EQUAL(result.size(), 5);
0300   BOOST_CHECK(rangeContainsValue(result, -66));
0301   BOOST_CHECK(rangeContainsValue(result, -51));
0302   BOOST_CHECK(rangeContainsValue(result, -19));
0303   BOOST_CHECK(rangeContainsValue(result, -13));
0304   BOOST_CHECK(rangeContainsValue(result, -83));
0305 }
0306 
0307 BOOST_FIXTURE_TEST_CASE(range_search_7, TreeFixture10DDoubleInt1) {
0308   RangeXD<10, double> range;
0309   range[9].shrink(0.0, 5.0);
0310 
0311   std::vector<int> result = tree.rangeSearch(range);
0312   BOOST_CHECK_EQUAL(result.size(), 2);
0313   BOOST_CHECK(rangeContainsValue(result, 27));
0314   BOOST_CHECK(rangeContainsValue(result, -56));
0315 }
0316 
0317 BOOST_FIXTURE_TEST_CASE(range_search_8, TreeFixture3DDoubleString1) {
0318   RangeXD<3, double> range;
0319   range[0].shrink(-5.0, 5.0);
0320   range[1].shrink(-5.0, 5.0);
0321   range[2].shrink(-5.0, 5.0);
0322 
0323   std::vector<std::string> result = tree.rangeSearch(range);
0324   BOOST_CHECK_EQUAL(result.size(), 1);
0325   BOOST_CHECK(rangeContainsValue(result, "string0"));
0326 }
0327 
0328 BOOST_FIXTURE_TEST_CASE(range_search_9, TreeFixture3DDoubleString1) {
0329   RangeXD<3, double> range;
0330   range[0].shrink(-10.0, 10.0);
0331   range[1].shrink(-10.0, 10.0);
0332   range[2].shrink(-5.0, 5.0);
0333 
0334   std::vector<std::string> result = tree.rangeSearch(range);
0335   BOOST_CHECK_EQUAL(result.size(), 4);
0336   BOOST_CHECK(rangeContainsValue(result, "string0"));
0337   BOOST_CHECK(rangeContainsValue(result, "string3"));
0338   BOOST_CHECK(rangeContainsValue(result, "string4"));
0339   BOOST_CHECK(rangeContainsValue(result, "string9"));
0340 }
0341 
0342 BOOST_FIXTURE_TEST_CASE(range_search_10, TreeFixture1DIntInt1) {
0343   RangeXD<1, int> range;
0344   range[0].shrink(0, 3);
0345 
0346   std::vector<int> result = tree.rangeSearch(range);
0347   BOOST_CHECK_EQUAL(result.size(), 2);
0348   BOOST_CHECK(rangeContainsValue(result, 5));
0349   BOOST_CHECK(rangeContainsValue(result, 6));
0350 }
0351 
0352 BOOST_FIXTURE_TEST_CASE(range_search_11, TreeFixture2DIntInt1) {
0353   RangeXD<2, int> range;
0354   range[1].shrink(0, 10);
0355 
0356   std::vector<int> result = tree.rangeSearch(range);
0357   BOOST_CHECK_EQUAL(result.size(), 2);
0358   BOOST_CHECK(rangeContainsValue(result, 5));
0359   BOOST_CHECK(rangeContainsValue(result, 6));
0360 }
0361 
0362 BOOST_FIXTURE_TEST_CASE(range_search_inplace_1, TreeFixture10DDoubleInt1) {
0363   RangeXD<10, double> range;
0364   range[0].shrink(0.0, 5.0);
0365 
0366   std::vector<int> result;
0367   tree.rangeSearch(range, result);
0368 
0369   BOOST_CHECK_EQUAL(result.size(), 5);
0370   BOOST_CHECK(rangeContainsValue(result, -66));
0371   BOOST_CHECK(rangeContainsValue(result, -51));
0372   BOOST_CHECK(rangeContainsValue(result, -19));
0373   BOOST_CHECK(rangeContainsValue(result, -13));
0374   BOOST_CHECK(rangeContainsValue(result, -83));
0375 }
0376 
0377 BOOST_FIXTURE_TEST_CASE(range_search_inserter_1, TreeFixture10DDoubleInt1) {
0378   RangeXD<10, double> range;
0379   range[0].shrink(0.0, 5.0);
0380 
0381   std::vector<int> result;
0382   tree.rangeSearchInserter(range, std::back_inserter(result));
0383 
0384   BOOST_CHECK_EQUAL(result.size(), 5);
0385   BOOST_CHECK(rangeContainsValue(result, -66));
0386   BOOST_CHECK(rangeContainsValue(result, -51));
0387   BOOST_CHECK(rangeContainsValue(result, -19));
0388   BOOST_CHECK(rangeContainsValue(result, -13));
0389   BOOST_CHECK(rangeContainsValue(result, -83));
0390 }
0391 
0392 BOOST_FIXTURE_TEST_CASE(range_search_map_1, TreeFixture10DDoubleInt1) {
0393   RangeXD<10, double> range;
0394   range[0].shrink(0.0, 5.0);
0395 
0396   std::vector<int> result = tree.rangeSearchMap<int>(
0397       range,
0398       [](const std::array<double, 10>&, const int& i) -> int { return 2 * i; });
0399 
0400   BOOST_CHECK_EQUAL(result.size(), 5);
0401   BOOST_CHECK(rangeContainsValue(result, -132));
0402   BOOST_CHECK(rangeContainsValue(result, -102));
0403   BOOST_CHECK(rangeContainsValue(result, -38));
0404   BOOST_CHECK(rangeContainsValue(result, -26));
0405   BOOST_CHECK(rangeContainsValue(result, -166));
0406 }
0407 
0408 BOOST_FIXTURE_TEST_CASE(range_search_map_inserter_1, TreeFixture10DDoubleInt1) {
0409   RangeXD<10, double> range;
0410   range[0].shrink(0.0, 5.0);
0411 
0412   std::vector<std::string> result;
0413 
0414   tree.rangeSearchMapInserter<std::string>(
0415       range,
0416       [](const std::array<double, 10>&, const int& i) -> std::string {
0417         return std::to_string(i);
0418       },
0419       std::back_inserter(result));
0420 
0421   BOOST_CHECK_EQUAL(result.size(), 5);
0422   BOOST_CHECK(rangeContainsValue(result, "-66"));
0423   BOOST_CHECK(rangeContainsValue(result, "-51"));
0424   BOOST_CHECK(rangeContainsValue(result, "-19"));
0425   BOOST_CHECK(rangeContainsValue(result, "-13"));
0426   BOOST_CHECK(rangeContainsValue(result, "-83"));
0427 }
0428 
0429 BOOST_FIXTURE_TEST_CASE(range_search_map_inserter_2, TreeFixture2DIntInt1) {
0430   RangeXD<2, int> range;
0431   range[1].shrink(0, 10);
0432 
0433   std::vector<int> result;
0434   tree.rangeSearchMapInserter<int>(
0435       range,
0436       [](const std::array<int, 2>& c, const int& i) -> int {
0437         return i * (c[0] + c[1]);
0438       },
0439       std::back_inserter(result));
0440 
0441   BOOST_CHECK_EQUAL(result.size(), 2);
0442   BOOST_CHECK(rangeContainsValue(result, 40));
0443   BOOST_CHECK(rangeContainsValue(result, 18));
0444 }
0445 
0446 BOOST_FIXTURE_TEST_CASE(range_search_map_discard_1, TreeFixture2DIntInt1) {
0447   RangeXD<2, int> range;
0448   range[1].shrink(-100, 5);
0449 
0450   int result = 0;
0451 
0452   tree.rangeSearchMapDiscard(
0453       range, [&result](const std::array<int, 2>& c, const int& i) {
0454         result += i * (c[0] + c[1]);
0455       });
0456 
0457   BOOST_CHECK_EQUAL(result, 24);
0458 }
0459 
0460 BOOST_FIXTURE_TEST_CASE(range_search_map_discard_2, TreeFixture3DDoubleInt2) {
0461   RangeXD<3, double> range;
0462   range[0].shrinkMin(0.0);
0463 
0464   int result = 0;
0465 
0466   tree.rangeSearchMapDiscard(range, [&result](const std::array<double, 3>&,
0467                                               const int& i) { result += i; });
0468 
0469   BOOST_CHECK_EQUAL(result, 555);
0470 }
0471 
0472 BOOST_FIXTURE_TEST_CASE(range_search_combinatorial, TreeFixture3DDoubleInt2) {
0473   for (double xmin = -10.0; xmin <= 10.0; xmin += 2.0) {
0474     for (double xmax = -10.0; xmax <= 10.0; xmax += 2.0) {
0475       for (double ymin = -10.0; ymin <= 10.0; ymin += 2.0) {
0476         for (double ymax = -10.0; ymax <= 10.0; ymax += 2.0) {
0477           for (double zmin = -10.0; zmin <= 10.0; zmin += 2.0) {
0478             for (double zmax = -10.0; zmax <= 10.0; zmax += 2.0) {
0479               RangeXD<3, double> range;
0480 
0481               range[0].shrink(xmin, xmax);
0482               range[1].shrink(ymin, ymax);
0483               range[2].shrink(zmin, zmax);
0484 
0485               std::vector<int> valid;
0486 
0487               for (const auto& [c, value] : test_vector) {
0488                 if (xmin <= c[0] && c[0] < xmax && ymin <= c[1] &&
0489                     c[1] < ymax && zmin <= c[2] && c[2] < zmax) {
0490                   valid.push_back(value);
0491                 }
0492               }
0493 
0494               std::vector<int> result = tree.rangeSearch(range);
0495 
0496               BOOST_CHECK_EQUAL(result.size(), valid.size());
0497 
0498               for (int j : valid) {
0499                 BOOST_CHECK(rangeContainsValue(result, j));
0500               }
0501             }
0502           }
0503         }
0504       }
0505     }
0506   }
0507 }
0508 
0509 BOOST_FIXTURE_TEST_CASE(range_search_dominate1, TreeFixture3DDoubleInt3) {
0510   RangeXD<3, double> range1;
0511   range1[0].shrink(-200, 0);
0512 
0513   std::vector<int> result = tree.rangeSearch(range1);
0514   BOOST_CHECK_EQUAL(result.size(), 4);
0515   BOOST_CHECK(rangeContainsValue(result, 0));
0516   BOOST_CHECK(rangeContainsValue(result, 1));
0517   BOOST_CHECK(rangeContainsValue(result, 2));
0518   BOOST_CHECK(rangeContainsValue(result, 3));
0519 }
0520 
0521 BOOST_FIXTURE_TEST_CASE(range_search_dominate2, TreeFixture3DDoubleInt3) {
0522   RangeXD<3, double> range1;
0523   range1[0].shrink(0, 200);
0524 
0525   std::vector<int> result = tree.rangeSearch(range1);
0526   BOOST_CHECK_EQUAL(result.size(), 4);
0527   BOOST_CHECK(rangeContainsValue(result, 4));
0528   BOOST_CHECK(rangeContainsValue(result, 5));
0529   BOOST_CHECK(rangeContainsValue(result, 6));
0530   BOOST_CHECK(rangeContainsValue(result, 7));
0531 }
0532 
0533 BOOST_AUTO_TEST_CASE(range_search_very_big) {
0534   int q = 0;
0535 
0536   std::vector<std::pair<std::array<double, 3>, int>> points;
0537 
0538   for (double x = -10.0; x < 10.0; x += 0.5) {
0539     for (double y = -10.0; y < 10.0; y += 0.5) {
0540       for (double z = -10.0; z < 10.0; z += 0.5) {
0541         points.push_back({{x, y, z}, q++});
0542       }
0543     }
0544   }
0545 
0546   std::vector<std::pair<std::array<double, 3>, int>> copy(points);
0547 
0548   KDTree<3, int, double> tree(std::move(copy));
0549 
0550   for (double xmin = -10.0; xmin <= 10.0; xmin += 1.0) {
0551     for (double ymin = -10.0; ymin <= 10.0; ymin += 1.0) {
0552       for (double zmin = -10.0; zmin <= 10.0; zmin += 1.0) {
0553         RangeXD<3, double> range;
0554 
0555         double xmax = xmin + 1.0;
0556         double ymax = ymin + 1.0;
0557         double zmax = zmin + 1.0;
0558 
0559         range[0].shrink(xmin, xmax);
0560         range[1].shrink(ymin, ymax);
0561         range[2].shrink(zmin, zmax);
0562 
0563         std::vector<int> valid;
0564 
0565         for (const std::pair<std::array<double, 3>, int>& i : points) {
0566           const std::array<double, 3>& c = i.first;
0567           if (xmin <= c[0] && c[0] < xmax && ymin <= c[1] && c[1] < ymax &&
0568               zmin <= c[2] && c[2] < zmax) {
0569             valid.push_back(i.second);
0570           }
0571         }
0572 
0573         std::vector<int> result = tree.rangeSearch(range);
0574 
0575         BOOST_CHECK_EQUAL(result.size(), valid.size());
0576 
0577         for (int j : valid) {
0578           BOOST_CHECK(rangeContainsValue(result, j));
0579         }
0580       }
0581     }
0582   }
0583 }
0584 
0585 BOOST_AUTO_TEST_CASE(range_search_many_same) {
0586   int q = 0;
0587 
0588   std::vector<std::pair<std::array<double, 3>, int>> points;
0589 
0590   for (std::size_t i = 0; i < 50; ++i) {
0591     points.push_back({{64.0, 64.0, 64.0}, q++});
0592   }
0593 
0594   for (std::size_t i = 0; i < 50; ++i) {
0595     points.push_back({{-64.0, -64.0, -64.0}, q++});
0596   }
0597 
0598   KDTree<3, int, double> tree(std::move(points));
0599 
0600   RangeXD<3, double> range1;
0601   range1[0].shrink(50.0, 70.0);
0602   range1[1].shrink(50.0, 70.0);
0603   range1[2].shrink(50.0, 70.0);
0604 
0605   RangeXD<3, double> range2;
0606   range2[0].shrink(-70.0, -50.0);
0607   range2[1].shrink(-70.0, -50.0);
0608   range2[2].shrink(-70.0, -50.0);
0609 
0610   std::vector<int> result1 = tree.rangeSearch(range1);
0611   std::vector<int> result2 = tree.rangeSearch(range2);
0612 
0613   BOOST_CHECK_EQUAL(result1.size(), 50);
0614   BOOST_CHECK_EQUAL(result2.size(), 50);
0615 
0616   for (int i = 0; i < 50; ++i) {
0617     BOOST_CHECK(rangeContainsValue(result1, i));
0618   }
0619 
0620   for (int i = 50; i < 100; ++i) {
0621     BOOST_CHECK(rangeContainsValue(result2, i));
0622   }
0623 }
0624 
0625 BOOST_AUTO_TEST_SUITE_END()
0626 
0627 BOOST_AUTO_TEST_SUITE_END()
0628 }  // namespace ActsTests
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!