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