Analysis Software
Documentation for sPHENIX simulation software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
KDTreeTests.cpp
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file KDTreeTests.cpp
1 // This file is part of the Acts project.
2 //
3 // Copyright (C) 2021 CERN for the benefit of the Acts project
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public
6 // License, v. 2.0. If a copy of the MPL was not distributed with this
7 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 
9 #include <boost/test/unit_test.hpp>
10 
11 #include "Acts/Utilities/KDTree.hpp"
12 #include "Acts/Utilities/Range1D.hpp"
13 #include "Acts/Utilities/RangeXD.hpp"
14 
15 #include <algorithm>
16 #include <array>
17 #include <cstddef>
18 #include <iterator>
19 #include <string>
20 #include <utility>
21 #include <vector>
22 
23 namespace {
24 std::vector<std::pair<std::array<double, 3>, int>> test_vector{
25  {{-8.5, 2.3, -1.6}, 84}, {{-9.7, -1.4, 7.6}, -56},
26  {{6.4, 2.7, -1.0}, -94}, {{-2.2, -9.3, 3.6}, 56},
27  {{-9.2, -2.8, -2.5}, -90}, {{3.8, 0.9, 7.2}, 43},
28  {{7.6, 1.9, -1.0}, 83}, {{2.1, -1.6, -1.7}, -15},
29  {{5.2, 3.2, -1.3}, 14}, {{-6.0, -7.5, 6.5}, 48},
30  {{3.5, -7.1, -4.4}, 83}, {{5.0, 6.9, -0.7}, 1},
31  {{8.0, 0.2, 3.8}, 69}, {{2.5, 0.8, 4.1}, -11},
32  {{-1.5, -6.6, 8.4}, -98}, {{0.8, 6.1, 2.7}, 14},
33  {{5.1, -5.1, 5.8}, 46}, {{-9.6, 0.7, 0.3}, 59},
34  {{-8.8, 1.3, -9.8}, -19}, {{-7.5, -9.3, -2.2}, 6},
35  {{-5.3, 1.9, -3.9}, 57}, {{-4.8, -9.8, -0.2}, 73},
36  {{-6.3, -7.4, 9.2}, -94}, {{-4.8, -9.8, -2.6}, 77},
37  {{2.4, 4.9, -8.4}, -72}, {{8.4, 6.1, -7.7}, -66},
38  {{6.1, -8.2, 9.3}, 67}, {{9.4, 7.4, 7.5}, -99},
39  {{9.4, 1.8, -4.4}, -87}, {{9.0, -3.7, 6.3}, -12},
40  {{-1.8, 2.8, 6.3}, 71}, {{-7.6, 7.6, -4.5}, -77},
41  {{-7.7, -1.2, 7.7}, -92}, {{-6.9, -0.5, -6.6}, -61},
42  {{0.9, 5.7, 0.5}, 60}, {{-0.3, 3.7, -7.0}, 15},
43  {{5.3, -0.6, -6.6}, 46}, {{-6.9, -3.0, 4.1}, -13},
44  {{1.8, -6.5, 1.8}, -29}, {{1.4, -7.8, -0.3}, 100},
45  {{8.2, 0.1, -7.6}, 69}, {{6.5, -9.1, 6.6}, -61},
46  {{4.2, 6.6, -0.7}, 56}, {{8.6, -3.1, -6.8}, -88},
47  {{9.7, -6.0, 2.9}, -44}, {{7.0, -3.2, 9.8}, 29},
48  {{-6.1, 3.3, -3.0}, 54}, {{-2.6, 7.6, -4.2}, -52},
49  {{-5.9, 7.8, 5.1}, -81}, {{0.6, 5.3, -2.5}, -69},
50  {{-8.5, 1.8, 6.0}, 56}, {{6.4, 2.0, -6.8}, -14},
51  {{-9.0, -2.1, 8.0}, 84}, {{7.0, 0.1, 6.3}, -17},
52  {{8.0, 4.5, -0.8}, -85}, {{-5.5, 9.2, 7.5}, 13},
53  {{-3.8, 2.1, 3.4}, 19}, {{-8.0, -5.2, 9.5}, -25},
54  {{6.2, 6.0, -2.2}, 81}, {{5.1, -5.1, -9.7}, 74},
55  {{-1.3, -9.0, 8.1}, -74}, {{5.4, -0.8, 2.4}, 32},
56  {{-5.6, 3.8, 6.2}, 73}, {{8.9, -3.8, -7.8}, 93},
57  {{7.7, 0.4, -2.9}, 78}, {{-6.9, -1.5, -3.3}, -75},
58  {{-5.3, 2.5, -3.6}, 48}, {{-6.6, -9.2, -2.1}, -7},
59  {{5.5, -7.7, 2.0}, 3}, {{4.1, -9.5, -6.9}, 82},
60  {{-2.3, -0.2, -0.7}, -3}, {{2.3, 0.4, -5.5}, 43},
61  {{5.0, 4.0, 9.0}, 59}, {{-8.7, -4.0, 1.0}, -17},
62  {{7.6, -7.6, -7.9}, 18}, {{4.2, 6.3, -4.4}, 2},
63  {{8.6, -6.3, 3.5}, -75}, {{9.8, 7.3, 0.1}, 8},
64  {{-2.2, 9.3, -6.2}, -54}, {{-0.9, -0.4, 1.4}, 45},
65  {{-5.3, 6.7, 7.6}, 20}, {{-2.7, 2.4, 8.8}, 42},
66  {{9.3, -0.0, 9.1}, -84}, {{0.5, 1.5, -2.3}, -47},
67  {{7.5, -5.7, 1.3}, 21}, {{0.4, 0.4, -2.0}, 50},
68  {{0.8, -6.2, -7.7}, 46}, {{5.1, -7.3, -0.7}, 26},
69  {{9.7, 2.8, 9.6}, 80}, {{7.3, -2.1, -6.7}, -91},
70  {{-9.4, -5.3, -3.1}, -24}, {{-2.4, -1.6, -0.2}, -88},
71  {{-9.9, -5.9, 0.0}, -90}, {{1.3, -3.0, 9.8}, 72},
72  {{0.9, -6.8, -2.7}, 92}, {{-1.7, -3.8, 2.8}, -78},
73  {{-6.4, -0.6, -0.6}, 95}, {{-4.7, 4.8, -8.0}, 95},
74  {{-6.0, 3.5, -7.4}, 7}, {{3.2, -6.2, 3.9}, -25}};
75 }
76 
77 namespace Acts {
78 namespace Test {
79 
80 struct TreeFixture1DDoubleInt1 {
81  TreeFixture1DDoubleInt1()
82  : tree(std::vector<std::pair<std::array<double, 1>, int>>{
83  {{1.0}, 5}, {{2.0}, 6}, {{-1.2}, 2}, {{0.9}, 10}}) {}
84 
85  Acts::KDTree<1, int, double> tree;
86 };
87 
88 struct TreeFixture1DDoubleInt2 {
89  TreeFixture1DDoubleInt2()
90  : tree(std::vector<std::pair<std::array<double, 1>, int>>{
91  {{1.0}, 5},
92  {{2.0}, 6},
93  {{-1.2}, 2},
94  {{0.9}, 10},
95  {{-10.0}, 9},
96  {{110.0}, 1},
97  {{-1000.0}, 3}}) {}
98 
99  Acts::KDTree<1, int, double> tree;
100 };
101 
102 struct TreeFixture2DDoubleInt1 {
103  TreeFixture2DDoubleInt1()
104  : tree(std::vector<std::pair<std::array<double, 2>, int>>{
105  {{1.0, 5.0}, 5}, {{2.0, -2.5}, 6}}) {}
106 
107  Acts::KDTree<2, int, double> tree;
108 };
109 
110 struct TreeFixture3DDoubleInt1 {
111  TreeFixture3DDoubleInt1()
112  : tree(std::vector<std::pair<std::array<double, 3>, int>>{
113  {{-4.7, -2.0, -1.7}, 63}, {{8.2, -0.0, 9.5}, -82},
114  {{7.1, -3.6, -4.0}, -49}, {{-9.9, -4.6, 2.9}, 86},
115  {{5.0, -3.8, -2.8}, -12}, {{-4.8, -1.8, -1.6}, -60},
116  {{8.8, 9.6, -0.2}, 60}, {{7.6, 1.9, 8.8}, 74},
117  {{9.0, -6.9, -6.2}, 35}, {{4.3, 7.5, -2.0}, 19},
118  {{-7.7, 3.7, 7.1}, -54}, {{3.4, 7.4, -4.0}, -8},
119  {{8.5, 3.0, -3.2}, -48}, {{6.5, -0.3, -3.1}, -25},
120  {{6.9, -6.6, -8.0}, -4}, {{6.8, 5.5, -2.5}, 17},
121  {{-2.8, 8.8, -7.2}, 62}, {{-0.1, 3.5, 5.5}, -95},
122  {{-1.3, 6.9, 5.3}, -23}, {{6.2, 6.6, 7.1}, -84}}) {}
123 
124  Acts::KDTree<3, int, double> tree;
125 };
126 
127 struct TreeFixture3DDoubleInt2 {
128  TreeFixture3DDoubleInt2()
129  : tree(std::vector<std::pair<std::array<double, 3>, int>>(test_vector)) {}
130 
131  Acts::KDTree<3, int, double> tree;
132 };
133 
134 struct TreeFixture3DDoubleInt3 {
135  TreeFixture3DDoubleInt3()
136  : tree(std::vector<std::pair<std::array<double, 3>, int>>{
137  {{-100.0, -1.1, -1.7}, 0},
138  {{100.0, -0.0, 9.5}, 4},
139  {{-100.0, -0.6, -1.0}, 1},
140  {{100.0, -4.6, 2.9}, 5},
141  {{-100.0, -1.4, -2.8}, 2},
142  {{100.0, -1.8, -1.6}, 6},
143  {{-100.0, -1.0, -0.2}, 3},
144  {{100.0, 1.9, 8.8}, 7}}) {}
145 
146  Acts::KDTree<3, int, double> tree;
147 };
148 
149 struct TreeFixture10DDoubleInt1 {
150  TreeFixture10DDoubleInt1()
151  : tree(std::vector<std::pair<std::array<double, 10>, int>>{
152  {{5.6, 7.5, -9.8, 9.6, 3.3, -7.3, 2.0, 4.7, -2.1, 5.9}, 32},
153  {{1.2, -1.5, -0.2, 0.9, 1.1, -1.4, -8.9, -1.2, -9.0, 7.4}, -66},
154  {{1.6, 6.2, 9.9, -2.5, 4.0, 8.9, 3.9, 8.4, -1.2, -4.1}, -51},
155  {{0.7, -5.7, -3.1, 5.4, 0.6, -8.7, 0.2, -0.2, 0.3, -2.7}, -19},
156  {{-5.0, -5.5, -7.1, 9.2, 5.5, 0.7, 9.9, -7.0, -6.8, 3.1}, 27},
157  {{0.4, 5.5, -5.8, -3.0, 6.0, -7.3, 2.1, 7.9, -8.0, -6.9}, -13},
158  {{-2.3, -5.9, 9.0, 1.4, 4.6, 3.4, -9.5, -6.3, 3.3, -7.0}, 97},
159  {{8.1, 3.6, -8.6, -0.4, 7.5, 10.0, -3.9, -5.8, -2.9, 9.8}, 15},
160  {{8.4, -4.0, 6.3, 1.1, -5.7, 8.1, -8.0, -2.5, -0.5, 3.2}, -56},
161  {{2.3, 5.8, 1.4, 4.0, 9.0, -6.4, 1.0, -7.8, 4.3, -5.3}, -83}}) {}
162 
163  Acts::KDTree<10, int, double> tree;
164 };
165 
166 struct TreeFixture3DDoubleString1 {
167  TreeFixture3DDoubleString1()
168  : tree(std::vector<std::pair<std::array<double, 3>, std::string>>{
169  {{-0.2, -0.2, -3.8}, "string0"},
170  {{4.9, -7.8, -10.0}, "string1"},
171  {{3.5, -10.0, -8.1}, "string2"},
172  {{8.2, -6.1, 2.0}, "string3"},
173  {{-9.9, 7.7, -1.4}, "string4"},
174  {{-2.2, 2.1, 8.6}, "string5"},
175  {{-6.9, -5.8, 5.3}, "string6"},
176  {{-0.7, 0.9, -6.5}, "string7"},
177  {{-2.7, -5.9, -7.3}, "string8"},
178  {{3.1, -9.4, -2.5}, "string9"}}) {}
179 
180  Acts::KDTree<3, std::string, double> tree;
181 };
182 
183 struct TreeFixture1DIntInt1 {
184  TreeFixture1DIntInt1()
185  : tree(std::vector<std::pair<std::array<int, 1>, int>>{
186  {{1}, 5}, {{2}, 6}, {{-1}, 2}, {{5}, 10}}) {}
187 
188  Acts::KDTree<1, int, int> tree;
189 };
190 
191 struct TreeFixture2DIntInt1 {
192  TreeFixture2DIntInt1()
193  : tree(std::vector<std::pair<std::array<int, 2>, int>>{
194  {{1, 7}, 5}, {{2, 1}, 6}, {{-1, -11}, 2}, {{5, -2}, 10}}) {}
195 
196  Acts::KDTree<2, int, int> tree;
197 };
198 
199 BOOST_AUTO_TEST_SUITE(Utilities)
200 
201 BOOST_AUTO_TEST_SUITE(KDTree)
202 
203 BOOST_FIXTURE_TEST_CASE(size_1, TreeFixture1DDoubleInt1) {
204  BOOST_CHECK_EQUAL(tree.size(), 4);
205 }
206 
207 BOOST_FIXTURE_TEST_CASE(size_2, TreeFixture1DDoubleInt2) {
208  BOOST_CHECK_EQUAL(tree.size(), 7);
209 }
210 
211 BOOST_FIXTURE_TEST_CASE(size_3, TreeFixture2DDoubleInt1) {
212  BOOST_CHECK_EQUAL(tree.size(), 2);
213 }
214 
215 BOOST_FIXTURE_TEST_CASE(size_4, TreeFixture3DDoubleInt1) {
216  BOOST_CHECK_EQUAL(tree.size(), 20);
217 }
218 
219 BOOST_FIXTURE_TEST_CASE(size_5, TreeFixture10DDoubleInt1) {
220  BOOST_CHECK_EQUAL(tree.size(), 10);
221 }
222 
223 BOOST_FIXTURE_TEST_CASE(size_6, TreeFixture3DDoubleString1) {
224  BOOST_CHECK_EQUAL(tree.size(), 10);
225 }
226 
227 BOOST_FIXTURE_TEST_CASE(size_7, TreeFixture1DIntInt1) {
228  BOOST_CHECK_EQUAL(tree.size(), 4);
229 }
230 
231 BOOST_FIXTURE_TEST_CASE(size_8, TreeFixture3DDoubleInt2) {
232  BOOST_CHECK_EQUAL(tree.size(), 100);
233 }
234 
235 BOOST_FIXTURE_TEST_CASE(range_search_1, TreeFixture1DDoubleInt2) {
236  RangeXD<1, double> range;
237  range[0].shrink(0.0, 2.5);
238 
239  std::vector<int> result = tree.rangeSearch(range);
240  BOOST_CHECK_EQUAL(result.size(), 3);
241  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
242  BOOST_CHECK((std::find(result.begin(), result.end(), 6) != result.end()));
243  BOOST_CHECK((std::find(result.begin(), result.end(), 10) != result.end()));
244  BOOST_CHECK((std::find(result.begin(), result.end(), 7) == result.end()));
245  BOOST_CHECK((std::find(result.begin(), result.end(), 2) == result.end()));
246  BOOST_CHECK((std::find(result.begin(), result.end(), 9) == result.end()));
247 }
248 
249 BOOST_FIXTURE_TEST_CASE(range_search_2, TreeFixture1DDoubleInt2) {
250  RangeXD<1, double> range;
251  range[0].shrink(-10000.0, 10000.0);
252 
253  std::vector<int> result = tree.rangeSearch(range);
254  BOOST_CHECK_EQUAL(result.size(), 7);
255  BOOST_CHECK((std::find(result.begin(), result.end(), 1) != result.end()));
256  BOOST_CHECK((std::find(result.begin(), result.end(), 2) != result.end()));
257  BOOST_CHECK((std::find(result.begin(), result.end(), 3) != result.end()));
258  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
259  BOOST_CHECK((std::find(result.begin(), result.end(), 6) != result.end()));
260  BOOST_CHECK((std::find(result.begin(), result.end(), 9) != result.end()));
261  BOOST_CHECK((std::find(result.begin(), result.end(), 10) != result.end()));
262 }
263 
264 BOOST_FIXTURE_TEST_CASE(range_search_3, TreeFixture1DDoubleInt2) {
265  RangeXD<1, double> range;
266  range[0].shrink(5000.0, 10000.0);
267 
268  std::vector<int> result = tree.rangeSearch(range);
269  BOOST_CHECK_EQUAL(result.size(), 0);
270 }
271 
272 BOOST_FIXTURE_TEST_CASE(range_search_4, TreeFixture2DDoubleInt1) {
273  RangeXD<2, double> range;
274  range[0].shrink(0.0, 10.0);
275  range[1].shrink(0.0, 10.0);
276 
277  std::vector<int> result = tree.rangeSearch(range);
278  BOOST_CHECK_EQUAL(result.size(), 1);
279  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
280 }
281 
282 BOOST_FIXTURE_TEST_CASE(range_search_5, TreeFixture2DDoubleInt1) {
283  RangeXD<2, double> range;
284  range[0].shrink(0.0, 10.0);
285  range[1].shrink(-10.0, 10.0);
286 
287  std::vector<int> result = tree.rangeSearch(range);
288  BOOST_CHECK_EQUAL(result.size(), 2);
289  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
290  BOOST_CHECK((std::find(result.begin(), result.end(), 6) != result.end()));
291 }
292 
293 BOOST_FIXTURE_TEST_CASE(range_search_6, TreeFixture10DDoubleInt1) {
294  RangeXD<10, double> range;
295  range[0].shrink(0.0, 5.0);
296 
297  std::vector<int> result = tree.rangeSearch(range);
298  BOOST_CHECK_EQUAL(result.size(), 5);
299  BOOST_CHECK((std::find(result.begin(), result.end(), -66) != result.end()));
300  BOOST_CHECK((std::find(result.begin(), result.end(), -51) != result.end()));
301  BOOST_CHECK((std::find(result.begin(), result.end(), -19) != result.end()));
302  BOOST_CHECK((std::find(result.begin(), result.end(), -13) != result.end()));
303  BOOST_CHECK((std::find(result.begin(), result.end(), -83) != result.end()));
304 }
305 
306 BOOST_FIXTURE_TEST_CASE(range_search_7, TreeFixture10DDoubleInt1) {
307  RangeXD<10, double> range;
308  range[9].shrink(0.0, 5.0);
309 
310  std::vector<int> result = tree.rangeSearch(range);
311  BOOST_CHECK_EQUAL(result.size(), 2);
312  BOOST_CHECK((std::find(result.begin(), result.end(), 27) != result.end()));
313  BOOST_CHECK((std::find(result.begin(), result.end(), -56) != result.end()));
314 }
315 
316 BOOST_FIXTURE_TEST_CASE(range_search_8, TreeFixture3DDoubleString1) {
317  RangeXD<3, double> range;
318  range[0].shrink(-5.0, 5.0);
319  range[1].shrink(-5.0, 5.0);
320  range[2].shrink(-5.0, 5.0);
321 
322  std::vector<std::string> result = tree.rangeSearch(range);
323  BOOST_CHECK_EQUAL(result.size(), 1);
324  BOOST_CHECK(
325  (std::find(result.begin(), result.end(), "string0") != result.end()));
326 }
327 
328 BOOST_FIXTURE_TEST_CASE(range_search_9, TreeFixture3DDoubleString1) {
329  RangeXD<3, double> range;
330  range[0].shrink(-10.0, 10.0);
331  range[1].shrink(-10.0, 10.0);
332  range[2].shrink(-5.0, 5.0);
333 
334  std::vector<std::string> result = tree.rangeSearch(range);
335  BOOST_CHECK_EQUAL(result.size(), 4);
336  BOOST_CHECK(
337  (std::find(result.begin(), result.end(), "string0") != result.end()));
338  BOOST_CHECK(
339  (std::find(result.begin(), result.end(), "string3") != result.end()));
340  BOOST_CHECK(
341  (std::find(result.begin(), result.end(), "string4") != result.end()));
342  BOOST_CHECK(
343  (std::find(result.begin(), result.end(), "string9") != result.end()));
344 }
345 
346 BOOST_FIXTURE_TEST_CASE(range_search_10, TreeFixture1DIntInt1) {
347  RangeXD<1, int> range;
348  range[0].shrink(0, 3);
349 
350  std::vector<int> result = tree.rangeSearch(range);
351  BOOST_CHECK_EQUAL(result.size(), 2);
352  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
353  BOOST_CHECK((std::find(result.begin(), result.end(), 6) != result.end()));
354 }
355 
356 BOOST_FIXTURE_TEST_CASE(range_search_11, TreeFixture2DIntInt1) {
357  RangeXD<2, int> range;
358  range[1].shrink(0, 10);
359 
360  std::vector<int> result = tree.rangeSearch(range);
361  BOOST_CHECK_EQUAL(result.size(), 2);
362  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
363  BOOST_CHECK((std::find(result.begin(), result.end(), 6) != result.end()));
364 }
365 
366 BOOST_FIXTURE_TEST_CASE(range_search_inplace_1, TreeFixture10DDoubleInt1) {
367  RangeXD<10, double> range;
368  range[0].shrink(0.0, 5.0);
369 
370  std::vector<int> result;
371  tree.rangeSearch(range, result);
372 
373  BOOST_CHECK_EQUAL(result.size(), 5);
374  BOOST_CHECK((std::find(result.begin(), result.end(), -66) != result.end()));
375  BOOST_CHECK((std::find(result.begin(), result.end(), -51) != result.end()));
376  BOOST_CHECK((std::find(result.begin(), result.end(), -19) != result.end()));
377  BOOST_CHECK((std::find(result.begin(), result.end(), -13) != result.end()));
378  BOOST_CHECK((std::find(result.begin(), result.end(), -83) != result.end()));
379 }
380 
381 BOOST_FIXTURE_TEST_CASE(range_search_inserter_1, TreeFixture10DDoubleInt1) {
382  RangeXD<10, double> range;
383  range[0].shrink(0.0, 5.0);
384 
385  std::vector<int> result;
386  tree.rangeSearchInserter(range, std::back_inserter(result));
387 
388  BOOST_CHECK_EQUAL(result.size(), 5);
389  BOOST_CHECK((std::find(result.begin(), result.end(), -66) != result.end()));
390  BOOST_CHECK((std::find(result.begin(), result.end(), -51) != result.end()));
391  BOOST_CHECK((std::find(result.begin(), result.end(), -19) != result.end()));
392  BOOST_CHECK((std::find(result.begin(), result.end(), -13) != result.end()));
393  BOOST_CHECK((std::find(result.begin(), result.end(), -83) != result.end()));
394 }
395 
396 BOOST_FIXTURE_TEST_CASE(range_search_map_1, TreeFixture10DDoubleInt1) {
397  RangeXD<10, double> range;
398  range[0].shrink(0.0, 5.0);
399 
400  std::vector<int> result = tree.rangeSearchMap<int>(
401  range,
402  [](const std::array<double, 10>&, const int& i) -> int { return 2 * i; });
403 
404  BOOST_CHECK_EQUAL(result.size(), 5);
405  BOOST_CHECK((std::find(result.begin(), result.end(), -132) != result.end()));
406  BOOST_CHECK((std::find(result.begin(), result.end(), -102) != result.end()));
407  BOOST_CHECK((std::find(result.begin(), result.end(), -38) != result.end()));
408  BOOST_CHECK((std::find(result.begin(), result.end(), -26) != result.end()));
409  BOOST_CHECK((std::find(result.begin(), result.end(), -166) != result.end()));
410 }
411 
412 BOOST_FIXTURE_TEST_CASE(range_search_map_inserter_1, TreeFixture10DDoubleInt1) {
413  RangeXD<10, double> range;
414  range[0].shrink(0.0, 5.0);
415 
416  std::vector<std::string> result;
417 
418  tree.rangeSearchMapInserter<std::string>(
419  range,
420  [](const std::array<double, 10>&, const int& i) -> std::string {
421  return std::to_string(i);
422  },
423  std::back_inserter(result));
424 
425  BOOST_CHECK_EQUAL(result.size(), 5);
426  BOOST_CHECK((std::find(result.begin(), result.end(), "-66") != result.end()));
427  BOOST_CHECK((std::find(result.begin(), result.end(), "-51") != result.end()));
428  BOOST_CHECK((std::find(result.begin(), result.end(), "-19") != result.end()));
429  BOOST_CHECK((std::find(result.begin(), result.end(), "-13") != result.end()));
430  BOOST_CHECK((std::find(result.begin(), result.end(), "-83") != result.end()));
431 }
432 
433 BOOST_FIXTURE_TEST_CASE(range_search_map_inserter_2, TreeFixture2DIntInt1) {
434  RangeXD<2, int> range;
435  range[1].shrink(0, 10);
436 
437  std::vector<int> result;
438  tree.rangeSearchMapInserter<int>(
439  range,
440  [](const std::array<int, 2>& c, const int& i) -> int {
441  return i * (c[0] + c[1]);
442  },
443  std::back_inserter(result));
444 
445  BOOST_CHECK_EQUAL(result.size(), 2);
446  BOOST_CHECK((std::find(result.begin(), result.end(), 40) != result.end()));
447  BOOST_CHECK((std::find(result.begin(), result.end(), 18) != result.end()));
448 }
449 
450 BOOST_FIXTURE_TEST_CASE(range_search_map_discard_1, TreeFixture2DIntInt1) {
451  RangeXD<2, int> range;
452  range[1].shrink(-100, 5);
453 
454  int result = 0;
455 
456  tree.rangeSearchMapDiscard(
457  range, [&result](const std::array<int, 2>& c, const int& i) {
458  result += i * (c[0] + c[1]);
459  });
460 
461  BOOST_CHECK_EQUAL(result, 24);
462 }
463 
464 BOOST_FIXTURE_TEST_CASE(range_search_map_discard_2, TreeFixture3DDoubleInt2) {
465  RangeXD<3, double> range;
466  range[0].shrinkMin(0.0);
467 
468  int result = 0;
469 
470  tree.rangeSearchMapDiscard(range, [&result](const std::array<double, 3>&,
471  const int& i) { result += i; });
472 
473  BOOST_CHECK_EQUAL(result, 555);
474 }
475 
476 BOOST_FIXTURE_TEST_CASE(range_search_combinatorial, TreeFixture3DDoubleInt2) {
477  for (double xmin = -10.0; xmin <= 10.0; xmin += 2.0) {
478  for (double xmax = -10.0; xmax <= 10.0; xmax += 2.0) {
479  for (double ymin = -10.0; ymin <= 10.0; ymin += 2.0) {
480  for (double ymax = -10.0; ymax <= 10.0; ymax += 2.0) {
481  for (double zmin = -10.0; zmin <= 10.0; zmin += 2.0) {
482  for (double zmax = -10.0; zmax <= 10.0; zmax += 2.0) {
483  RangeXD<3, double> range;
484 
485  range[0].shrink(xmin, xmax);
486  range[1].shrink(ymin, ymax);
487  range[2].shrink(zmin, zmax);
488 
489  std::vector<int> valid;
490 
491  for (const std::pair<std::array<double, 3>, int>& i :
492  test_vector) {
493  const std::array<double, 3>& c = i.first;
494  if (xmin <= c[0] && c[0] < xmax && ymin <= c[1] &&
495  c[1] < ymax && zmin <= c[2] && c[2] < zmax) {
496  valid.push_back(i.second);
497  }
498  }
499 
500  std::vector<int> result = tree.rangeSearch(range);
501 
502  BOOST_CHECK_EQUAL(result.size(), valid.size());
503 
504  for (int j : valid) {
505  BOOST_CHECK((std::find(result.begin(), result.end(), j) !=
506  result.end()));
507  }
508  }
509  }
510  }
511  }
512  }
513  }
514 }
515 
516 BOOST_FIXTURE_TEST_CASE(range_search_dominate1, TreeFixture3DDoubleInt3) {
517  RangeXD<3, double> range1;
518  range1[0].shrink(-200, 0);
519 
520  std::vector<int> result = tree.rangeSearch(range1);
521  BOOST_CHECK_EQUAL(result.size(), 4);
522  BOOST_CHECK((std::find(result.begin(), result.end(), 0) != result.end()));
523  BOOST_CHECK((std::find(result.begin(), result.end(), 1) != result.end()));
524  BOOST_CHECK((std::find(result.begin(), result.end(), 2) != result.end()));
525  BOOST_CHECK((std::find(result.begin(), result.end(), 3) != result.end()));
526 }
527 
528 BOOST_FIXTURE_TEST_CASE(range_search_dominate2, TreeFixture3DDoubleInt3) {
529  RangeXD<3, double> range1;
530  range1[0].shrink(0, 200);
531 
532  std::vector<int> result = tree.rangeSearch(range1);
533  BOOST_CHECK_EQUAL(result.size(), 4);
534  BOOST_CHECK((std::find(result.begin(), result.end(), 4) != result.end()));
535  BOOST_CHECK((std::find(result.begin(), result.end(), 5) != result.end()));
536  BOOST_CHECK((std::find(result.begin(), result.end(), 6) != result.end()));
537  BOOST_CHECK((std::find(result.begin(), result.end(), 7) != result.end()));
538 }
539 
540 BOOST_AUTO_TEST_CASE(range_search_very_big) {
541  int q = 0;
542 
543  std::vector<std::pair<std::array<double, 3>, int>> points;
544 
545  for (double x = -10.0; x < 10.0; x += 0.5) {
546  for (double y = -10.0; y < 10.0; y += 0.5) {
547  for (double z = -10.0; z < 10.0; z += 0.5) {
548  points.push_back({{x, y, z}, q++});
549  }
550  }
551  }
552 
553  std::vector<std::pair<std::array<double, 3>, int>> copy(points);
554 
555  Acts::KDTree<3, int, double> tree(std::move(copy));
556 
557  for (double xmin = -10.0; xmin <= 10.0; xmin += 1.0) {
558  for (double ymin = -10.0; ymin <= 10.0; ymin += 1.0) {
559  for (double zmin = -10.0; zmin <= 10.0; zmin += 1.0) {
560  RangeXD<3, double> range;
561 
562  double xmax = xmin + 1.0;
563  double ymax = ymin + 1.0;
564  double zmax = zmin + 1.0;
565 
566  range[0].shrink(xmin, xmax);
567  range[1].shrink(ymin, ymax);
568  range[2].shrink(zmin, zmax);
569 
570  std::vector<int> valid;
571 
572  for (const std::pair<std::array<double, 3>, int>& i : points) {
573  const std::array<double, 3>& c = i.first;
574  if (xmin <= c[0] && c[0] < xmax && ymin <= c[1] && c[1] < ymax &&
575  zmin <= c[2] && c[2] < zmax) {
576  valid.push_back(i.second);
577  }
578  }
579 
580  std::vector<int> result = tree.rangeSearch(range);
581 
582  BOOST_CHECK_EQUAL(result.size(), valid.size());
583 
584  for (int j : valid) {
585  BOOST_CHECK(
586  (std::find(result.begin(), result.end(), j) != result.end()));
587  }
588  }
589  }
590  }
591 }
592 
593 BOOST_AUTO_TEST_CASE(range_search_many_same) {
594  int q = 0;
595 
596  std::vector<std::pair<std::array<double, 3>, int>> points;
597 
598  for (std::size_t i = 0; i < 50; ++i) {
599  points.push_back({{64.0, 64.0, 64.0}, q++});
600  }
601 
602  for (std::size_t i = 0; i < 50; ++i) {
603  points.push_back({{-64.0, -64.0, -64.0}, q++});
604  }
605 
606  Acts::KDTree<3, int, double> tree(std::move(points));
607 
608  RangeXD<3, double> range1;
609  range1[0].shrink(50.0, 70.0);
610  range1[1].shrink(50.0, 70.0);
611  range1[2].shrink(50.0, 70.0);
612 
613  RangeXD<3, double> range2;
614  range2[0].shrink(-70.0, -50.0);
615  range2[1].shrink(-70.0, -50.0);
616  range2[2].shrink(-70.0, -50.0);
617 
618  std::vector<int> result1 = tree.rangeSearch(range1);
619  std::vector<int> result2 = tree.rangeSearch(range2);
620 
621  BOOST_CHECK_EQUAL(result1.size(), 50);
622  BOOST_CHECK_EQUAL(result2.size(), 50);
623 
624  for (int i = 0; i < 50; ++i) {
625  BOOST_CHECK(
626  (std::find(result1.begin(), result1.end(), i) != result1.end()));
627  }
628 
629  for (int i = 50; i < 100; ++i) {
630  BOOST_CHECK(
631  (std::find(result2.begin(), result2.end(), i) != result2.end()));
632  }
633 }
634 
635 BOOST_AUTO_TEST_SUITE_END()
636 
637 BOOST_AUTO_TEST_SUITE_END()
638 } // namespace Test
639 } // namespace Acts