1 // Boost.Geometry Index
2 // Unit Test
3
4 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
5
6 // Use, modification and distribution is subject to the Boost Software License,
7 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9
10 #include <boost/test/included/test_exec_monitor.hpp>
11 #include <boost/test/impl/execution_monitor.ipp>
12
13 #include <boost/geometry/index/detail/varray.hpp>
14
15 using namespace boost::geometry::index::detail;
16
17 class value_ndc
18 {
19 public:
value_ndc(int a)20 explicit value_ndc(int a) : aa(a) {}
~value_ndc()21 ~value_ndc() {}
operator ==(value_ndc const & v) const22 bool operator==(value_ndc const& v) const { return aa == v.aa; }
23 private:
value_ndc(value_ndc const &)24 value_ndc(value_ndc const&) {}
operator =(value_ndc const &)25 value_ndc & operator=(value_ndc const&) { return *this; }
26 int aa;
27 };
28
29 class value_nd
30 {
31 public:
value_nd(int a)32 explicit value_nd(int a) : aa(a) {}
~value_nd()33 ~value_nd() {}
operator ==(value_nd const & v) const34 bool operator==(value_nd const& v) const { return aa == v.aa; }
35 private:
36 int aa;
37 };
38
39 class value_nc
40 {
41 public:
value_nc(int a=0)42 explicit value_nc(int a = 0) : aa(a) {}
~value_nc()43 ~value_nc() {}
operator ==(value_nc const & v) const44 bool operator==(value_nc const& v) const { return aa == v.aa; }
45 private:
value_nc(value_nc const &)46 value_nc(value_nc const&) {}
operator =(value_ndc const &)47 value_nc & operator=(value_ndc const&) { return *this; }
48 int aa;
49 };
50
51 class counting_value
52 {
53 public:
counting_value(int a=0)54 explicit counting_value(int a = 0) : aa(a) { ++c(); }
counting_value(counting_value const & v)55 counting_value(counting_value const& v) : aa(v.aa) { ++c(); }
operator =(counting_value const & v)56 counting_value & operator=(counting_value const& v) { aa = v.aa; return *this; }
~counting_value()57 ~counting_value() { --c(); }
operator ==(counting_value const & v) const58 bool operator==(counting_value const& v) const { return aa == v.aa; }
count()59 static size_t count() { return c(); }
60 private:
c()61 static size_t & c() { static size_t co = 0; return co; }
62 int aa;
63 };
64
65 template <typename T, size_t N>
test_ctor_ndc()66 void test_ctor_ndc()
67 {
68 varray<T, N> s;
69 BOOST_CHECK(s.size() == 0);
70 BOOST_CHECK(s.capacity() == N);
71 BOOST_CHECK_THROW( s.at(0), std::out_of_range );
72 }
73
74 template <typename T, size_t N>
test_ctor_nc(size_t n)75 void test_ctor_nc(size_t n)
76 {
77 varray<T, N> s(n);
78 BOOST_CHECK(s.size() == n);
79 BOOST_CHECK(s.capacity() == N);
80 BOOST_CHECK_THROW( s.at(n), std::out_of_range );
81 if ( !boost::has_trivial_constructor<T>::value )
82 {
83 for ( size_t i = 0 ; i < n ; ++i )
84 BOOST_CHECK(T() == s[i]);
85 }
86 }
87
88 template <typename T, size_t N>
test_ctor_nd(size_t n,T const & v)89 void test_ctor_nd(size_t n, T const& v)
90 {
91 varray<T, N> s(n, v);
92 BOOST_CHECK(s.size() == n);
93 BOOST_CHECK(s.capacity() == N);
94 BOOST_CHECK_THROW( s.at(n), std::out_of_range );
95 if ( 1 < n )
96 {
97 BOOST_CHECK(v == s[0]);
98 BOOST_CHECK(v == s.at(0));
99 BOOST_CHECK(v == s[1]);
100 BOOST_CHECK(v == s.at(1));
101 s[0] = T(10);
102 BOOST_CHECK(T(10) == s[0]);
103 BOOST_CHECK(T(10) == s.at(0));
104 s.at(1) = T(20);
105 BOOST_CHECK(T(20) == s[1]);
106 BOOST_CHECK(T(20) == s.at(1));
107 }
108 }
109
110 template <typename T, size_t N>
test_resize_nc(size_t n)111 void test_resize_nc(size_t n)
112 {
113 varray<T, N> s;
114
115 s.resize(n);
116 BOOST_CHECK(s.size() == n);
117 BOOST_CHECK(s.capacity() == N);
118 BOOST_CHECK_THROW( s.at(n), std::out_of_range );
119
120 if ( !boost::has_trivial_constructor<T>::value )
121 {
122 for ( size_t i = 0 ; i < n ; ++i )
123 BOOST_CHECK(T() == s[i]);
124 }
125 }
126
127 template <typename T, size_t N>
test_resize_nd(size_t n,T const & v)128 void test_resize_nd(size_t n, T const& v)
129 {
130 varray<T, N> s;
131
132 s.resize(n, v);
133 BOOST_CHECK(s.size() == n);
134 BOOST_CHECK(s.capacity() == N);
135 BOOST_CHECK_THROW( s.at(n), std::out_of_range );
136 if ( 1 < n )
137 {
138 BOOST_CHECK(v == s[0]);
139 BOOST_CHECK(v == s.at(0));
140 BOOST_CHECK(v == s[1]);
141 BOOST_CHECK(v == s.at(1));
142 s[0] = T(10);
143 BOOST_CHECK(T(10) == s[0]);
144 BOOST_CHECK(T(10) == s.at(0));
145 s.at(1) = T(20);
146 BOOST_CHECK(T(20) == s[1]);
147 BOOST_CHECK(T(20) == s.at(1));
148 }
149 }
150
151 template <typename T, size_t N>
test_push_back_nd()152 void test_push_back_nd()
153 {
154 varray<T, N> s;
155
156 BOOST_CHECK(s.size() == 0);
157 BOOST_CHECK_THROW( s.at(0), std::out_of_range );
158
159 for ( size_t i = 0 ; i < N ; ++i )
160 {
161 s.push_back(T(i));
162 BOOST_CHECK(s.size() == i + 1);
163 BOOST_CHECK_THROW( s.at(i + 1), std::out_of_range );
164 BOOST_CHECK(T(i) == s.at(i));
165 BOOST_CHECK(T(i) == s[i]);
166 BOOST_CHECK(T(i) == s.back());
167 BOOST_CHECK(T(0) == s.front());
168 }
169 }
170
171 template <typename T, size_t N>
test_pop_back_nd()172 void test_pop_back_nd()
173 {
174 varray<T, N> s;
175
176 for ( size_t i = 0 ; i < N ; ++i )
177 s.push_back(T(i));
178
179 for ( size_t i = N ; i > 1 ; --i )
180 {
181 s.pop_back();
182 BOOST_CHECK(s.size() == i - 1);
183 BOOST_CHECK_THROW( s.at(i - 1), std::out_of_range );
184 BOOST_CHECK(T(i - 2) == s.at(i - 2));
185 BOOST_CHECK(T(i - 2) == s[i - 2]);
186 BOOST_CHECK(T(i - 2) == s.back());
187 BOOST_CHECK(T(0) == s.front());
188 }
189 }
190
191 template <typename It1, typename It2>
test_compare_ranges(It1 first1,It1 last1,It2 first2,It2 last2)192 void test_compare_ranges(It1 first1, It1 last1, It2 first2, It2 last2)
193 {
194 BOOST_CHECK(std::distance(first1, last1) == std::distance(first2, last2));
195 for ( ; first1 != last1 && first2 != last2 ; ++first1, ++first2 )
196 BOOST_CHECK(*first1 == *first2);
197 }
198
199 template <typename T, size_t N>
test_copy_and_assign_nd(T const & val)200 void test_copy_and_assign_nd(T const& val)
201 {
202 varray<T, N> s;
203 std::vector<T> v;
204 std::list<T> l;
205
206 for ( size_t i = 0 ; i < N ; ++i )
207 {
208 s.push_back(T(i));
209 v.push_back(T(i));
210 l.push_back(T(i));
211 }
212 // copy ctor
213 {
214 varray<T, N> s1(s);
215 BOOST_CHECK(s.size() == s1.size());
216 test_compare_ranges(s.begin(), s.end(), s1.begin(), s1.end());
217 }
218 // copy assignment
219 {
220 varray<T, N> s1;
221 BOOST_CHECK(0 == s1.size());
222 s1 = s;
223 BOOST_CHECK(s.size() == s1.size());
224 test_compare_ranges(s.begin(), s.end(), s1.begin(), s1.end());
225 }
226 // ctor(Iter, Iter)
227 {
228 varray<T, N> s1(s.begin(), s.end());
229 BOOST_CHECK(s.size() == s1.size());
230 test_compare_ranges(s.begin(), s.end(), s1.begin(), s1.end());
231 }
232 {
233 varray<T, N> s1(v.begin(), v.end());
234 BOOST_CHECK(v.size() == s1.size());
235 test_compare_ranges(v.begin(), v.end(), s1.begin(), s1.end());
236 }
237 {
238 varray<T, N> s1(l.begin(), l.end());
239 BOOST_CHECK(l.size() == s1.size());
240 test_compare_ranges(l.begin(), l.end(), s1.begin(), s1.end());
241 }
242 // assign(Iter, Iter)
243 {
244 varray<T, N> s1;
245 BOOST_CHECK(0 == s1.size());
246 s1.assign(s.begin(), s.end());
247 BOOST_CHECK(s.size() == s1.size());
248 test_compare_ranges(s.begin(), s.end(), s1.begin(), s1.end());
249 }
250 {
251 varray<T, N> s1;
252 BOOST_CHECK(0 == s1.size());
253 s1.assign(v.begin(), v.end());
254 BOOST_CHECK(v.size() == s1.size());
255 test_compare_ranges(v.begin(), v.end(), s1.begin(), s1.end());
256 }
257 {
258 varray<T, N> s1;
259 BOOST_CHECK(0 == s1.size());
260 s1.assign(l.begin(), l.end());
261 BOOST_CHECK(l.size() == s1.size());
262 test_compare_ranges(l.begin(), l.end(), s1.begin(), s1.end());
263 }
264 // assign(N, V)
265 {
266 varray<T, N> s1(s);
267 test_compare_ranges(s.begin(), s.end(), s1.begin(), s1.end());
268 std::vector<T> a(N, val);
269 s1.assign(N, val);
270 test_compare_ranges(a.begin(), a.end(), s1.begin(), s1.end());
271 }
272 }
273
274 template <typename T, size_t N>
test_iterators_nd()275 void test_iterators_nd()
276 {
277 varray<T, N> s;
278 std::vector<T> v;
279
280 for ( size_t i = 0 ; i < N ; ++i )
281 {
282 s.push_back(T(i));
283 v.push_back(T(i));
284 }
285
286 test_compare_ranges(s.begin(), s.end(), v.begin(), v.end());
287 test_compare_ranges(s.rbegin(), s.rend(), v.rbegin(), v.rend());
288
289 s.assign(v.rbegin(), v.rend());
290
291 test_compare_ranges(s.begin(), s.end(), v.rbegin(), v.rend());
292 test_compare_ranges(s.rbegin(), s.rend(), v.begin(), v.end());
293 }
294
295 template <typename T, size_t N>
test_erase_nd()296 void test_erase_nd()
297 {
298 varray<T, N> s;
299
300 for ( size_t i = 0 ; i < N ; ++i )
301 s.push_back(T(i));
302
303 // erase(pos)
304 {
305 for ( size_t i = 0 ; i < N ; ++i )
306 {
307 varray<T, N> s1(s);
308 s1.erase(s1.begin() + i);
309 BOOST_CHECK(s1.size() == N - 1);
310 for ( size_t j = 0 ; j < i ; ++j )
311 BOOST_CHECK(s1[j] == T(j));
312 for ( size_t j = i+1 ; j < N ; ++j )
313 BOOST_CHECK(s1[j-1] == T(j));
314 }
315 }
316 // erase(first, last)
317 {
318 size_t n = N/3;
319 for ( size_t i = 0 ; i <= N ; ++i )
320 {
321 varray<T, N> s1(s);
322 size_t removed = i + n < N ? n : N - i;
323 s1.erase(s1.begin() + i, s1.begin() + i + removed);
324 BOOST_CHECK(s1.size() == N - removed);
325 for ( size_t j = 0 ; j < i ; ++j )
326 BOOST_CHECK(s1[j] == T(j));
327 for ( size_t j = i+n ; j < N ; ++j )
328 BOOST_CHECK(s1[j-n] == T(j));
329 }
330 }
331 }
332
333 template <typename T, size_t N>
test_insert_nd(T const & val)334 void test_insert_nd(T const& val)
335 {
336 size_t h = N/2;
337
338 varray<T, N> s, ss;
339 std::vector<T> v;
340 std::list<T> l;
341
342 for ( size_t i = 0 ; i < h ; ++i )
343 {
344 s.push_back(T(i));
345 ss.push_back(T(100 + i));
346 v.push_back(T(100 + i));
347 l.push_back(T(100 + i));
348 }
349
350 // insert(pos, val)
351 {
352 for ( size_t i = 0 ; i <= h ; ++i )
353 {
354 varray<T, N> s1(s);
355 s1.insert(s1.begin() + i, val);
356 BOOST_CHECK(s1.size() == h+1);
357 for ( size_t j = 0 ; j < i ; ++j )
358 BOOST_CHECK(s1[j] == T(j));
359 BOOST_CHECK(s1[i] == val);
360 for ( size_t j = 0 ; j < h-i ; ++j )
361 BOOST_CHECK(s1[j+i+1] == T(j+i));
362 }
363 }
364 // insert(pos, n, val)
365 {
366 size_t n = size_t(h/1.5f);
367 for ( size_t i = 0 ; i <= h ; ++i )
368 {
369 varray<T, N> s1(s);
370 s1.insert(s1.begin() + i, n, val);
371 BOOST_CHECK(s1.size() == h+n);
372 for ( size_t j = 0 ; j < i ; ++j )
373 BOOST_CHECK(s1[j] == T(j));
374 for ( size_t j = 0 ; j < n ; ++j )
375 BOOST_CHECK(s1[j+i] == val);
376 for ( size_t j = 0 ; j < h-i ; ++j )
377 BOOST_CHECK(s1[j+i+n] == T(j+i));
378 }
379 }
380 // insert(pos, first, last)
381 {
382 size_t n = size_t(h/1.5f);
383 for ( size_t i = 0 ; i <= h ; ++i )
384 {
385 varray<T, N> s1(s);
386 s1.insert(s1.begin() + i, ss.begin(), ss.begin() + n);
387 BOOST_CHECK(s1.size() == h+n);
388 for ( size_t j = 0 ; j < i ; ++j )
389 BOOST_CHECK(s1[j] == T(j));
390 for ( size_t j = 0 ; j < n ; ++j )
391 BOOST_CHECK(s1[j+i] == T(100 + j));
392 for ( size_t j = 0 ; j < h-i ; ++j )
393 BOOST_CHECK(s1[j+i+n] == T(j+i));
394 }
395 }
396 {
397 size_t n = size_t(h/1.5f);
398 for ( size_t i = 0 ; i <= h ; ++i )
399 {
400 varray<T, N> s1(s);
401 s1.insert(s1.begin() + i, v.begin(), v.begin() + n);
402 BOOST_CHECK(s1.size() == h+n);
403 for ( size_t j = 0 ; j < i ; ++j )
404 BOOST_CHECK(s1[j] == T(j));
405 for ( size_t j = 0 ; j < n ; ++j )
406 BOOST_CHECK(s1[j+i] == T(100 + j));
407 for ( size_t j = 0 ; j < h-i ; ++j )
408 BOOST_CHECK(s1[j+i+n] == T(j+i));
409 }
410 }
411 {
412 size_t n = size_t(h/1.5f);
413 for ( size_t i = 0 ; i <= h ; ++i )
414 {
415 varray<T, N> s1(s);
416 typename std::list<T>::iterator it = l.begin();
417 std::advance(it, n);
418 s1.insert(s1.begin() + i, l.begin(), it);
419 BOOST_CHECK(s1.size() == h+n);
420 for ( size_t j = 0 ; j < i ; ++j )
421 BOOST_CHECK(s1[j] == T(j));
422 for ( size_t j = 0 ; j < n ; ++j )
423 BOOST_CHECK(s1[j+i] == T(100 + j));
424 for ( size_t j = 0 ; j < h-i ; ++j )
425 BOOST_CHECK(s1[j+i+n] == T(j+i));
426 }
427 }
428 }
429
test_main(int,char * [])430 int test_main(int, char* [])
431 {
432 BOOST_CHECK(counting_value::count() == 0);
433
434 test_ctor_ndc<int, 10>();
435 test_ctor_ndc<value_ndc, 10>();
436 test_ctor_ndc<counting_value, 10>();
437 BOOST_CHECK(counting_value::count() == 0);
438
439 test_ctor_nc<int, 10>(5);
440 test_ctor_nc<value_nc, 10>(5);
441 test_ctor_nc<counting_value, 10>(5);
442 BOOST_CHECK(counting_value::count() == 0);
443
444 test_ctor_nd<int, 10>(5, 1);
445 test_ctor_nd<value_nd, 10>(5, value_nd(1));
446 test_ctor_nd<counting_value, 10>(5, counting_value(1));
447 BOOST_CHECK(counting_value::count() == 0);
448
449 test_resize_nc<int, 10>(5);
450 test_resize_nc<value_nc, 10>(5);
451 test_resize_nc<counting_value, 10>(5);
452 BOOST_CHECK(counting_value::count() == 0);
453
454 test_resize_nd<int, 10>(5, 1);
455 test_resize_nd<value_nd, 10>(5, value_nd(1));
456 test_resize_nd<counting_value, 10>(5, counting_value(1));
457 BOOST_CHECK(counting_value::count() == 0);
458
459 test_push_back_nd<int, 10>();
460 test_push_back_nd<value_nd, 10>();
461 test_push_back_nd<counting_value, 10>();
462 BOOST_CHECK(counting_value::count() == 0);
463
464 test_pop_back_nd<int, 10>();
465 test_pop_back_nd<value_nd, 10>();
466 test_pop_back_nd<counting_value, 10>();
467 BOOST_CHECK(counting_value::count() == 0);
468
469 test_copy_and_assign_nd<int, 10>(1);
470 test_copy_and_assign_nd<value_nd, 10>(value_nd(1));
471 test_copy_and_assign_nd<counting_value, 10>(counting_value(1));
472 BOOST_CHECK(counting_value::count() == 0);
473
474 test_iterators_nd<int, 10>();
475 test_iterators_nd<value_nd, 10>();
476 test_iterators_nd<counting_value, 10>();
477 BOOST_CHECK(counting_value::count() == 0);
478
479 test_erase_nd<int, 10>();
480 test_erase_nd<value_nd, 10>();
481 test_erase_nd<counting_value, 10>();
482 BOOST_CHECK(counting_value::count() == 0);
483
484 test_insert_nd<int, 10>(50);
485 test_insert_nd<value_nd, 10>(value_nd(50));
486 test_insert_nd<counting_value, 10>(counting_value(50));
487 BOOST_CHECK(counting_value::count() == 0);
488
489 return 0;
490 }
491