Branch data Line data Source code
1 : : /*
2 : : * Copyright 2003-2005 Daniel F. Savarese
3 : : * Copyright 2006-2009 Savarese Software Research Corporation
4 : : *
5 : : * Licensed under the Apache License, Version 2.0 (the "License");
6 : : * you may not use this file except in compliance with the License.
7 : : * You may obtain a copy of the License at
8 : : *
9 : : * https://www.savarese.com/software/ApacheLicense-2.0
10 : : *
11 : : * Unless required by applicable law or agreed to in writing, software
12 : : * distributed under the License is distributed on an "AS IS" BASIS,
13 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : : * See the License for the specific language governing permissions and
15 : : * limitations under the License.
16 : : */
17 : :
18 : : #include <ssrc/spatial/kd_tree.h>
19 : :
20 : : #include <cstdlib>
21 : : #include <list>
22 : : #include <set>
23 : : #include <array>
24 : : #include <utility>
25 : : #include <ctime>
26 : :
27 : : #define BOOST_TEST_MODULE RangeSearchTreeTest
28 : : #include <boost/test/unit_test.hpp>
29 : : #include <boost/mpl/list.hpp>
30 : :
31 : : using namespace ssrc::spatial;
32 : : using namespace std::rel_ops;
33 : :
34 : : template<typename T>
35 : : struct TruePred {
36 : 147456 : bool operator()(const T &) { return true; }
37 : : };
38 : :
39 : : const unsigned int SquareSize = 16;
40 : : // TODO: Move these into TestData and test ranges that span negative values.
41 : : const unsigned int MinCoord = 0;
42 : : const unsigned int MaxCoord = (1 << SquareSize);
43 : :
44 : : template<typename number_type>
45 : 65536 : number_type random_coord() {
46 : 65536 : return (MinCoord + std::rand() % (MaxCoord - MinCoord));
47 : : }
48 : :
49 : : template<>
50 : 32768 : double random_coord<double>() {
51 : : const double scale =
52 : 32768 : (static_cast<double>(std::rand()) / (static_cast<double>(RAND_MAX) + 1.0));
53 : : return (static_cast<double>(MinCoord) +
54 : 32768 : scale*static_cast<double>(MaxCoord - MinCoord));
55 : : }
56 : :
57 : : template<typename V>
58 : : struct TestData {
59 : : static const unsigned int NumPoints = 16384;
60 : :
61 : : typedef V coordinate_type;
62 : : typedef NS_TR1::array<coordinate_type, 2> Point;
63 : : typedef kd_tree<Point, Point*> Tree;
64 : : typedef TruePred<typename Tree::value_type> True;
65 : : typedef std::list<Point *> PointList;
66 : : typedef std::set<Point> PointSet;
67 : :
68 : : static PointList points;
69 : :
70 : 3 : TestData() {
71 : : // ensures no duplicate coordinates
72 : 6 : PointSet set;
73 : :
74 : 3 : std::srand(std::time(0));
75 : :
76 [ + + ][ + + ]: 49155 : for(unsigned int i = 0; i < NumPoints; ++i) {
[ + + ]
77 : : Point point;
78 : 49152 : point[0] = random_coord<coordinate_type>();
79 : 49152 : point[1] = random_coord<coordinate_type>();
80 [ + - ]: 49152 : std::pair<typename PointSet::iterator, bool> result = set.insert(point);
[ + - + - ]
[ + - + - ]
[ + - ]
81 : :
82 [ + - ][ + - ]: 49152 : if(result.second) {
[ + - ]
83 [ + - ][ + - ]: 49152 : points.push_back(new Point(point));
[ + - ][ + - ]
[ + - ][ + - ]
84 : : }
85 : : }
86 : 3 : }
87 : :
88 : 6 : virtual ~TestData() {
89 [ + + ][ + + ]: 49155 : while(!points.empty()) {
[ + + ]
90 : 49152 : Point *point = points.back();
91 : 49152 : points.pop_back();
92 [ - + ][ - + ]: 49155 : delete point;
[ - + ]
93 : : }
94 : 6 : }
95 : : };
96 : :
97 [ + - ][ + - ]: 1 : template<class V> typename TestData<V>::PointList TestData<V>::points;
[ + - ][ # # ]
[ # # ][ # # ]
98 : :
99 : : template<typename TD>
100 : : struct FillTree {
101 : : typedef typename TD::PointList PointList;
102 : : typedef typename TD::Tree Tree;
103 : :
104 : 51 : void operator()(Tree & tree, const PointList & points) {
105 [ + + ][ + + ]: 835635 : for(typename PointList::const_iterator p = points.begin();
[ + + ]
106 : : p != points.end(); ++p)
107 : 835584 : tree[**p] = *p;
108 : 51 : }
109 : : };
110 : :
111 : : template<typename TD>
112 : : struct FillTreeAndOptimize : public FillTree<TD> {
113 : : typedef FillTree<TD> super;
114 : :
115 : 21 : void operator()(typename super::Tree & tree,
116 : : const typename super::PointList & points)
117 : : {
118 : 21 : super::operator()(tree, points);
119 : 21 : tree.optimize();
120 : 21 : }
121 : : };
122 : :
123 : : template<typename TD, typename FT>
124 : : struct TestScenario {
125 : : typedef TD test_data;
126 : : typedef FT fill_tree;
127 : : };
128 : :
129 : : typedef TestData<unsigned int> uint_data;
130 : : typedef TestData<int> int_data;
131 : : typedef TestData<double> dbl_data;
132 : :
133 : : typedef boost::mpl::list<uint_data, int_data, dbl_data> test_data_types;
134 : : typedef
135 : : boost::mpl::list<TestScenario<uint_data, FillTree<uint_data> >,
136 : : TestScenario<uint_data, FillTreeAndOptimize<uint_data> >,
137 : : TestScenario<int_data, FillTree<int_data> >,
138 : : TestScenario<int_data, FillTreeAndOptimize<int_data> >,
139 : : TestScenario<dbl_data, FillTree<dbl_data> >,
140 : : TestScenario<dbl_data, FillTreeAndOptimize<dbl_data> > >
141 : : test_scenario_types;
142 : :
143 : 1 : BOOST_GLOBAL_FIXTURE(uint_data)
144 : 1 : BOOST_GLOBAL_FIXTURE(int_data)
145 : 1 : BOOST_GLOBAL_FIXTURE(dbl_data)
146 : :
147 [ + - ]: 4 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_begin, test_data, test_data_types) {
148 : 6 : typename test_data::Tree tree;
149 : 3 : typename test_data::Point point{ { 15, 17 } };
150 : :
151 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.begin() == tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
152 : :
153 [ + - ][ + - ]: 3 : tree[point] = &point;
[ + - ]
154 : :
155 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.begin() != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
156 : :
157 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.begin()->first == point);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
158 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.begin()->second == &point);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
159 : 3 : }
160 : :
161 [ + - ]: 4 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_size, test_data, test_data_types) {
162 : : typedef typename test_data::Tree Tree;
163 : : typedef typename test_data::True True;
164 : : typedef typename test_data::PointList PointList;
165 : :
166 : 3 : const PointList & points = test_data::points;
167 : 6 : Tree tree;
168 : 3 : typename Tree::size_type size = typename Tree::size_type();
169 : :
170 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.size() == 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
171 : :
172 [ + - ][ + - ]: 49155 : for(typename PointList::const_iterator p = points.begin();
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ]
173 : : p != points.end(); ++p)
174 : : {
175 [ + - ][ + - ]: 49152 : if(!tree.insert(**p, *p))
[ + - ][ + - ]
[ + - ][ + - ]
176 : 49152 : ++size;
177 : : }
178 : :
179 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.size() == size);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
180 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.size() <= tree.max_size());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
181 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.empty() == (tree.size() == 0));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
182 [ + - ][ + - ]: 3 : BOOST_REQUIRE_EQUAL(tree.size(),
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
183 : : static_cast<typename Tree::size_type>(std::count_if(tree.begin(), tree.end(), True())));
184 : 3 : }
185 : :
186 [ + - ]: 4 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_indexed_access, test_data, test_data_types) {
187 : : typedef typename test_data::Tree Tree;
188 : : typedef typename test_data::PointList PointList;
189 : :
190 : 3 : const PointList & points = test_data::points;
191 : 6 : Tree tree;
192 : :
193 [ + - ][ + - ]: 49155 : for(typename PointList::const_iterator p = points.begin();
[ + + + - ]
[ + - ]
[ + + + - ]
[ + - ][ + + ]
194 : : p != points.end(); ++p)
195 : : {
196 [ + - ][ + - ]: 49152 : tree[**p] = *p;
[ + - ]
197 [ + - ][ + - ]: 49152 : BOOST_REQUIRE(tree[**p] == *p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
198 : : }
199 : 3 : }
200 : :
201 : :
202 [ + - ]: 7 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_clear, scenario_type, test_scenario_types) {
203 : : typename scenario_type::fill_tree fill_tree;
204 : 12 : typename scenario_type::test_data::Tree tree;
205 : :
206 [ + - + - : 6 : fill_tree(tree, scenario_type::test_data::points);
+ - + - +
- + - ]
207 : :
208 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.size() > 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
209 : :
210 [ + - ][ + - ]: 6 : tree.clear();
[ + - ][ + - ]
[ + - ][ + - ]
211 : :
212 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.empty());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
213 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.size() == 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
214 : 6 : }
215 : :
216 : : // TODO: Add search of a known subrange
217 : 8 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_range_search,
218 [ + - ]: 1 : scenario_type, test_scenario_types)
219 : : {
220 : : typedef typename scenario_type::test_data::Tree Tree;
221 : : typedef typename scenario_type::test_data::True True;
222 : : typedef typename scenario_type::test_data::Point Point;
223 : :
224 : : typename scenario_type::fill_tree fill_tree;
225 : 12 : Tree tree;
226 : :
227 [ + - + - : 6 : fill_tree(tree, scenario_type::test_data::points);
+ - + - +
- + - ]
228 : :
229 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.size() ==
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
230 : : static_cast<typename Tree::traits::size_type>(
231 : : std::count_if<typename Tree::iterator, True>(
232 : : tree.begin(Point{{MinCoord, MinCoord}},
233 : : Point{{MaxCoord, MaxCoord}}),
234 : : tree.end(), True())));
235 : 6 : }
236 : :
237 [ + - ]: 7 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_find, scenario_type, test_scenario_types) {
238 : : typedef typename scenario_type::test_data::Tree Tree;
239 : : typedef typename scenario_type::test_data::PointList PointList;
240 : :
241 : 6 : const PointList & points = scenario_type::test_data::points;
242 : : typename scenario_type::fill_tree fill_tree;
243 : 12 : Tree tree;
244 : 6 : const Tree & constTree = tree;
245 : :
246 [ + - ][ + - ]: 6 : BOOST_REQUIRE(!tree.get(*points.back()));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
247 : :
248 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.find(*points.back()) == tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
249 : :
250 [ + - ][ + - ]: 6 : fill_tree(tree, points);
[ + - ][ + - ]
[ + - ][ + - ]
251 : :
252 [ + - ][ + - ]: 98310 : for(typename PointList::const_iterator p = points.begin();
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
253 : : p != points.end(); ++p)
254 : : {
255 : : typename Tree::mapped_type value;
256 : :
257 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(tree.get(**p, &value));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
258 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(value == *p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
259 : :
260 [ + - ][ + - ]: 196608 : typename Tree::iterator it = tree.find(**p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
261 : :
262 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(it != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
263 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(it->first == **p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
264 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(it->second == *p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
265 : :
266 [ + - ][ + - ]: 196608 : typename Tree::const_iterator cit = constTree.find(**p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
267 : :
268 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(cit != constTree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
269 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(cit->first == **p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
270 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(cit->second == *p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
271 : : }
272 : 6 : }
273 : :
274 [ + - ]: 4 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_insert, test_data, test_data_types) {
275 : : typedef typename test_data::Tree Tree;
276 : : typedef typename test_data::PointList PointList;
277 : :
278 : 3 : const PointList & points = test_data::points;
279 : 6 : Tree tree;
280 : :
281 [ + - ][ + - ]: 49155 : for(typename PointList::const_iterator p = points.begin();
[ + + + - ]
[ + - ]
[ + + + - ]
[ + - ][ + + ]
282 : : p != points.end(); ++p)
283 : : {
284 [ + - ][ + - ]: 49152 : tree.insert(**p, *p);
[ + - ]
285 [ + - ][ + - ]: 49152 : BOOST_REQUIRE(tree.get(**p));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
286 : : }
287 : :
288 [ + - ][ + - ]: 3 : tree.clear();
[ + - ]
289 : :
290 [ + - ][ + - ]: 49155 : for(typename PointList::const_iterator p = points.begin();
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ]
291 : : p != points.end(); ++p)
292 : : {
293 [ + - ][ + - ]: 49152 : typename Tree::value_type value(**p, *p);
[ + - ]
294 [ + - ][ + - ]: 98304 : std::pair<typename Tree::iterator,bool> pair = tree.insert(value);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
295 : :
296 [ + - ][ + - ]: 49152 : BOOST_REQUIRE(pair.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
297 [ + - ][ + - ]: 49152 : BOOST_REQUIRE(tree.get(**p));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
298 [ + - ][ + - ]: 49152 : BOOST_REQUIRE(*(pair.first) == value);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
299 : : }
300 : :
301 : : typename Tree::mapped_type original, replaced;
302 : :
303 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.get(*points.back(), &original));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
304 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.insert(*points.back(), original, &replaced));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
305 [ + - ][ + - ]: 3 : BOOST_REQUIRE(original == replaced);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
306 : :
307 [ + - ][ + - ]: 6 : std::pair<typename Tree::iterator,bool> result;
[ + - ][ + - ]
[ + - ][ + - ]
308 : :
309 [ + - ][ + - ]: 3 : result = tree.insert(typename Tree::value_type(*points.back(), replaced));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
310 [ + - ][ + - ]: 3 : BOOST_REQUIRE(!result.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
311 [ + - ][ + - ]: 3 : BOOST_REQUIRE(result.first->second == replaced);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
312 : 3 : }
313 : :
314 [ + - ]: 4 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_assignment, test_data, test_data_types) {
315 : : typedef typename test_data::Tree Tree;
316 : : typedef typename test_data::Point Point;
317 : : typedef typename test_data::PointList PointList;
318 : :
319 : 3 : const PointList & points = test_data::points;
320 : 6 : Tree tree1;
321 : :
322 [ + - ][ + - ]: 49155 : for(typename PointList::const_iterator p = points.begin();
[ + + + - ]
[ + - ]
[ + + + - ]
[ + - ][ + + ]
323 : : p != points.end(); ++p)
324 : : {
325 [ + - ][ + - ]: 49152 : tree1.insert(**p, *p);
[ + - ]
326 : : }
327 : :
328 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree1 == tree1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
329 : :
330 : : // Test copy constructor.
331 [ + - ][ + - ]: 6 : Tree tree2(tree1);
[ + - ][ + - ]
[ + - ][ + - ]
332 : :
333 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree2 == tree1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
334 : :
335 : : // Test assignment operator.
336 : :
337 [ + - ][ + - ]: 6 : Tree tree3;
[ + - ][ + - ]
[ + - ][ + - ]
338 : :
339 [ + - ][ + - ]: 3 : tree3.insert(**points.begin(), *points.begin());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
340 : :
341 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree3 != tree1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
342 : :
343 [ + - ][ + - ]: 3 : tree3 = tree1;
[ + - ]
344 : :
345 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree3 == tree1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
346 : :
347 [ + - ][ + - ]: 3 : tree3.erase(**points.rbegin());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
348 : :
349 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree3 != tree1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
350 : 3 : }
351 : :
352 [ + - ]: 7 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_erase, scenario_type, test_scenario_types) {
353 : : typedef typename scenario_type::test_data::Tree Tree;
354 : : typedef typename scenario_type::test_data::PointList PointList;
355 : :
356 : 6 : const PointList & points = scenario_type::test_data::points;
357 : : typename scenario_type::fill_tree fill_tree;
358 : 12 : Tree tree;
359 : :
360 [ + - + - : 6 : fill_tree(tree, points);
+ - + - +
- + - ]
361 : :
362 [ + - ][ + - ]: 98310 : for(typename PointList::const_iterator p = points.begin();
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
363 : : p != points.end(); ++p)
364 : : {
365 : : typename Tree::mapped_type erased;
366 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(tree.remove(**p, &erased));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
367 [ + - ][ + - ]: 98304 : BOOST_REQUIRE(erased == *p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
368 : : }
369 : :
370 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.empty());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
371 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.size() == 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
372 : :
373 [ + - ][ + - ]: 6 : fill_tree(tree, points);
[ + - ][ + - ]
[ + - ][ + - ]
374 : :
375 [ + - ][ + - ]: 98310 : for(typename PointList::const_iterator p = points.begin();
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
376 : : p != points.end(); ++p)
377 : : {
378 [ + - ][ + - ]: 98304 : tree.erase(tree.find(**p));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
379 : : }
380 : :
381 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.empty());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
382 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.size() == 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
383 : :
384 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.erase(*points.back()) == 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
385 : :
386 [ + - ][ + - ]: 6 : fill_tree(tree, points);
[ + - ][ + - ]
[ + - ][ + - ]
387 : :
388 : 6 : typename Tree::size_type size = tree.size();
389 : 6 : typename Tree::size_type erased = 0;
390 : 6 : typename Tree::size_type count = 0;
391 [ + - ][ + + ]: 98310 : for(typename Tree::iterator p = tree.begin(); p != tree.end(); ++count) {
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
392 [ + + ][ + + ]: 98304 : if(std::rand() % 2) {
[ + + ][ + + ]
[ + + ][ + + ]
393 [ + - ][ + - ]: 49277 : p = tree.erase(p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
394 : 49277 : ++erased;
395 : : } else {
396 [ + - ][ + - ]: 49027 : ++p;
[ + - ][ + - ]
[ + - ][ + - ]
397 : : }
398 : : }
399 : :
400 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.size() == size - erased);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
401 [ + - ][ + - ]: 6 : BOOST_REQUIRE_EQUAL(size, count);
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
402 : :
403 [ + - ][ + - ]: 6 : tree.clear();
[ + - ][ + - ]
[ + - ][ + - ]
404 [ + - ][ + - ]: 6 : fill_tree(tree, points);
[ + - ][ + - ]
[ + - ][ + - ]
405 : :
406 : 6 : size = tree.size();
407 : 6 : count = 0;
408 : :
409 [ + - ][ + + ]: 98310 : for(typename Tree::iterator p = tree.begin(); p != tree.end(); ++count) {
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ][ + - ]
410 [ + - ][ + - ]: 98304 : p = tree.erase(p);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
411 : : }
412 : :
413 [ + - ][ + - ]: 6 : BOOST_REQUIRE(tree.empty());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
414 [ + - ][ + - ]: 6 : BOOST_REQUIRE(size == count);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
415 : 6 : }
416 : :
417 : 5 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_find_nearest_neighbor, test_data,
418 [ + - ]: 1 : test_data_types)
419 : : {
420 : : typedef typename test_data::Tree Tree;
421 : : typedef typename test_data::Point Point;
422 : : typedef typename test_data::PointList PointList;
423 : : typedef typename Tree::knn_iterator knn_iterator;
424 : : typedef typename test_data::coordinate_type coordinate_type;
425 : :
426 : 6 : Tree tree;
427 : 3 : Point query{{1,1}};
428 : :
429 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.find_nearest_neighbor(query) == tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
430 : :
431 [ + - ][ + - ]: 3 : tree.insert(Point{{1,1}}, 0);
[ + - ]
432 : :
433 [ + - ][ + - ]: 3 : BOOST_REQUIRE(tree.find_nearest_neighbor(query) == tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
434 : :
435 [ + - ][ + - ]: 3 : tree.insert(Point{{100,100}}, 0);
[ + - ]
436 : :
437 [ + - ][ + - ]: 6 : typename Tree::iterator it = tree.find_nearest_neighbor(query);
[ + - ][ + - ]
[ + - ][ + - ]
438 : :
439 [ + - ][ + - ]: 3 : BOOST_REQUIRE(it != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
440 [ + - ][ + - ]: 3 : BOOST_REQUIRE((it->first == Point{{100,100}}));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
441 : :
442 [ + - ][ + - ]: 3 : tree.insert(Point{{3,3}}, 0);
[ + - ]
443 : :
444 [ + - ][ + - ]: 3 : it = tree.find_nearest_neighbor(query);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
445 : :
446 [ + - ][ + - ]: 3 : BOOST_REQUIRE(it != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
447 [ + - ][ + - ]: 3 : BOOST_REQUIRE((it->first == Point{{3,3}}));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
448 : :
449 : : std::pair<knn_iterator,knn_iterator> range =
450 [ + - ][ + - ]: 6 : tree.find_nearest_neighbors(query, 1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
451 : :
452 [ + - ][ + - ]: 3 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
453 [ + - ][ + - ]: 3 : BOOST_REQUIRE((range.first->first == it->first));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
454 : :
455 : : FillTree<test_data> fill_tree;
456 : :
457 [ + - ][ + - ]: 3 : tree.clear();
[ + - ]
458 : :
459 [ + - ][ + - ]: 3 : fill_tree(tree, test_data::points);
[ + - ]
460 [ + - ][ + - ]: 3 : tree.insert(Point{{2,2}}, 0);
[ + - ]
461 : :
462 [ + - ][ + - ]: 3 : it = tree.find_nearest_neighbor(query);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
463 : :
464 [ + - ][ + - ]: 3 : BOOST_REQUIRE(it != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
465 [ + - ][ + - ]: 3 : BOOST_REQUIRE((it->first == Point{{2,2}} ||
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ - + ]
466 : : euclidean_distance<Point>::d2(query, it->first) < 2));
467 : :
468 [ + - ][ + - ]: 3 : range = tree.find_nearest_neighbors(query, 1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
469 : :
470 [ + - ][ + - ]: 3 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
471 [ + - ][ + - ]: 3 : BOOST_REQUIRE((range.first->first == it->first));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
472 : :
473 [ + - ][ + - ]: 3 : it = tree.find_nearest_neighbor(Point{{2,2}}, false);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
474 : :
475 [ + - ][ + - ]: 3 : BOOST_REQUIRE(it != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
476 [ + - ][ + - ]: 3 : BOOST_REQUIRE((it->first == Point{{2,2}}));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
477 : :
478 [ + - ][ + - ]: 3 : range = tree.find_nearest_neighbors(query, 1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
479 : :
480 [ + - ][ + - ]: 3 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
481 [ + - ][ + - ]: 3 : BOOST_REQUIRE((range.first->first == it->first));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
482 : :
483 : : // Now a brute force check. Note, we don't account for the possiblity
484 : : // of ties, which may cause a false failure on rare occasion.
485 [ + - ][ + - ]: 3 : tree.clear();
[ + - ]
486 [ + - ][ + - ]: 3 : fill_tree(tree, test_data::points);
[ + - ]
487 : 3 : Point *nearest = 0;
488 : 3 : double min = detail::coordinate_limits<double>::highest();
489 : :
490 : 3 : query[0] = query[1] = MaxCoord / 2;
491 : :
492 [ + - ][ + + ]: 49155 : for(typename PointList::const_iterator p = test_data::points.begin();
[ + - ][ + + ]
[ + - ][ + + ]
493 : : p != test_data::points.end(); ++p)
494 : : {
495 [ + - ][ + - ]: 49152 : const double ed = euclidean_distance<Point>::d2(query, **p);
[ + - ]
496 [ + + ][ + + ]: 49152 : if(ed < min) {
[ + + ]
497 : 26 : min = ed;
498 : 26 : nearest = *p;
499 : : }
500 : : }
501 : :
502 [ + - ][ + - ]: 3 : BOOST_REQUIRE(nearest != 0);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
503 : :
504 [ + - ][ + - ]: 3 : it = tree.find_nearest_neighbor(query);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
505 : :
506 [ + - ][ + - ]: 3 : BOOST_REQUIRE(it != tree.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
507 [ + - ][ + - ]: 3 : BOOST_REQUIRE(it->first == *nearest);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
508 : :
509 [ + - ][ + - ]: 3 : range = tree.find_nearest_neighbors(query, 1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
510 : :
511 [ + - ][ + - ]: 3 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
512 [ + - ][ + - ]: 3 : BOOST_REQUIRE((range.first->first == it->first));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
513 : :
514 : 3 : query[0] = query[1] = -1;
515 : :
516 : : // This should be a separate regression test. It catches the bug
517 : : // whereby nearest neighbors tests for k = 1 would produce an
518 : : // incorrect result when k > 2 would be correct.
519 : : // Skip for unsigned tests.
520 [ - + + - : 3 : if(query[0] < 0) {
+ - ]
521 : : Point data[6] = { {{0, 0}}, {{ 3, 1}}, {{4, 2}}, {{1, 1}},
522 : : {{static_cast<coordinate_type>(0.5),
523 : : static_cast<coordinate_type>(1.5)}},
524 : : {{static_cast<coordinate_type>(4.8),
525 : 2 : static_cast<coordinate_type>(4.9)}} };
526 [ # # ][ + - ]: 2 : tree.clear();
[ + - ]
527 : :
528 [ # # ][ + + ]: 14 : for(unsigned int i = 0; i < 6; ++i) {
[ + + ]
529 [ # # ][ + - ]: 12 : tree.insert(data[i], &data[i]);
[ + - ]
530 : : }
531 : :
532 [ # # ][ # # ]: 2 : it = tree.find_nearest_neighbor(query, 1);
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
533 : :
534 [ # # ][ # # ]: 2 : BOOST_REQUIRE(it != tree.end());
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
535 [ # # ][ # # ]: 2 : BOOST_REQUIRE((it->first == Point{{0,0}}));
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
536 : :
537 [ # # ][ # # ]: 2 : range = tree.find_nearest_neighbors(query, 2);
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
538 : :
539 [ # # ][ # # ]: 2 : BOOST_REQUIRE(range.first != range.second);
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
540 : :
541 [ # # ][ # # ]: 2 : range = tree.find_nearest_neighbors(query, 1);
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
542 : :
543 [ # # ][ # # ]: 2 : BOOST_REQUIRE(range.first != range.second);
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
544 [ # # ][ # # ]: 2 : BOOST_REQUIRE(range.first->first == it->first);
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ # # ]
[ # # ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
545 : : }
546 : 3 : }
547 : :
548 : : template<typename Point>
549 : : struct knn_comp {
550 : : const Point & query;
551 : :
552 : 3 : knn_comp(const Point & query) : query(query) { }
553 : :
554 : 864629 : bool operator()(const Point * const p1, const Point * const p2) {
555 : : return (euclidean_distance<Point>::d2(query, *p1) <
556 : 864629 : euclidean_distance<Point>::d2(query, *p2));
557 : : }
558 : : };
559 : :
560 : 5 : BOOST_AUTO_TEST_CASE_TEMPLATE(test_find_nearest_neighbors, test_data,
561 [ + - ][ - + ]: 2 : test_data_types)
[ # # ]
562 : : {
563 : : typedef typename test_data::Tree Tree;
564 : : typedef typename Tree::knn_iterator knn_iterator;
565 : : typedef typename test_data::Point Point;
566 : : typedef typename test_data::PointList PointList;
567 : :
568 : 3 : Point query{{MaxCoord / 2, MaxCoord /2}};
569 : 6 : Tree tree;
570 : : FillTree<test_data> fill_tree;
571 : :
572 [ + - + - : 3 : fill_tree(tree, test_data::points);
+ - ]
573 : :
574 : : // Brute force sorting of points by distance for use as expected values.
575 : : // Note, we may get occasional false failures in the presence of ties
576 : : // because we use an unstable sort.
577 : : std::vector<Point *> sorted_points(test_data::points.begin(),
578 [ + - ][ + - ]: 6 : test_data::points.end());
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
579 [ + - ][ + - ]: 3 : std::sort(sorted_points.begin(), sorted_points.end(), knn_comp<Point>(query));
[ + - + - ]
[ + - ]
[ + - + - ]
[ + - ][ + - ]
580 : :
581 [ + + ][ + + ]: 33 : for(unsigned int i = 1; i < 11; ++i) {
[ + + ]
582 : : std::pair<knn_iterator,knn_iterator> range =
583 [ + - ][ + - ]: 60 : tree.find_nearest_neighbors(query, i, false);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
584 : 30 : unsigned int j = 0;
585 [ + - ][ + - ]: 30 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
586 [ + - ][ + - ]: 195 : for(knn_iterator & it = range.first, & end = range.second; it != end; ++it)
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ]
587 : : {
588 [ + - ][ + - ]: 165 : BOOST_REQUIRE(it->first == *sorted_points[j++]);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
589 : : }
590 : : }
591 : :
592 [ + + ][ + + ]: 33 : for(unsigned int i = 1; i < 11; ++i) {
[ + + ]
593 : : std::pair<knn_iterator,knn_iterator> range =
594 [ + - ][ + - ]: 60 : tree.find_nearest_neighbors(query, i, true);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
595 : 30 : unsigned int j = 0;
596 [ + - ][ - + ]: 30 : if(*sorted_points[0] == query) {
[ + - ][ - + ]
[ + - ][ - + ]
597 : 0 : ++j;
598 : : }
599 [ + - ][ + - ]: 30 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
600 [ + - ][ + - ]: 195 : for(knn_iterator & it = range.first, & end = range.second; it != end; ++it)
[ + + ][ + - ]
[ + - ][ + + ]
[ + - ][ + - ]
[ + + ]
601 : : {
602 [ + - ][ + - ]: 165 : BOOST_REQUIRE(it->first == *sorted_points[j++]);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
603 : : }
604 : : }
605 : :
606 : : // Verify degenerate case.
607 : :
608 : 3 : query[0] = query[1] = 1;
609 [ + - + - : 3 : tree.insert(Point{{2,2}}, 0);
+ - ]
610 : :
611 : : std::pair<knn_iterator,knn_iterator> range =
612 [ + - ][ + - ]: 6 : tree.find_nearest_neighbors(query, 1);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
613 : :
614 [ + - ][ + - ]: 3 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
615 [ + - ][ + - ]: 3 : BOOST_REQUIRE((range.first->first == Point{{2,2}} ||
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ # # ]
[ # # ][ # # ]
[ + - ][ + - ]
[ + - ][ - + ]
616 : : euclidean_distance<Point>::d2(query, range.first->first) < 2));
617 : :
618 : 3 : query[0] = query[1] = 2;
619 [ + - ][ + - ]: 3 : range = tree.find_nearest_neighbors(query, 1, false);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ]
620 : :
621 [ + - ][ + - ]: 3 : BOOST_REQUIRE(range.first != range.second);
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ - + ]
622 [ + - ][ + - ]: 3 : BOOST_REQUIRE((range.first->first == Point{{2,2}}));
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ + - ]
[ + - ][ - + ]
623 [ + - ][ + - ]: 8 : }
[ + - ][ + - ]
|
