ceph/src/boost/libs/geometry/index/test/rtree/test_rtree.hpp

   1 // Boost.Geometry Index
   2 // Unit Test
   3
   4 // Copyright (c) 2011-2015 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 #ifndef BOOST_GEOMETRY_INDEX_TEST_RTREE_HPP
  11 #define BOOST_GEOMETRY_INDEX_TEST_RTREE_HPP
  12
  13 #include <boost/foreach.hpp>
  14 #include <vector>
  15 #include <algorithm>
  16
  17 #include <geometry_index_test_common.hpp>
  18
  19 #include <boost/geometry/index/rtree.hpp>
  20
  21 #include <boost/geometry/geometries/point.hpp>
  22 #include <boost/geometry/geometries/box.hpp>
  23 #include <boost/geometry/geometries/segment.hpp>
  24
  25 #include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
  26 #include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
  27
  28 //#include <boost/geometry/geometries/ring.hpp>
  29 //#include <boost/geometry/geometries/polygon.hpp>
  30
  31 namespace generate {
  32
  33 // Set point's coordinates
  34
  35 template <typename Point>
  36 struct outside_point
  37 {};
  38
  39 template <typename T, typename C>
  40 struct outside_point< bg::model::point<T, 2, C> >
  41 {
  42     typedef bg::model::point<T, 2, C> P;
  43     static P apply()
  44     {
  45         return P(13, 26);
  46     }
  47 };
  48
  49 template <typename T, typename C>
  50 struct outside_point< bg::model::point<T, 3, C> >
  51 {
  52     typedef bg::model::point<T, 3, C> P;
  53     static P apply()
  54     {
  55         return P(13, 26, 13);
  56     }
  57 };
  58
  59 // Default value generation
  60
  61 template <typename Value>
  62 struct value_default
  63 {
  64     static Value apply(){ return Value(); }
  65 };
  66
  67 // Values, input and rtree generation
  68
  69 template <typename Value>
  70 struct value
  71 {};
  72
  73 template <typename T, typename C>
  74 struct value< bg::model::point<T, 2, C> >
  75 {
  76     typedef bg::model::point<T, 2, C> P;
  77     static P apply(int x, int y)
  78     {
  79         return P(x, y);
  80     }
  81 };
  82
  83 template <typename T, typename C>
  84 struct value< bg::model::box< bg::model::point<T, 2, C> > >
  85 {
  86     typedef bg::model::point<T, 2, C> P;
  87     typedef bg::model::box<P> B;
  88     static B apply(int x, int y)
  89     {
  90         return B(P(x, y), P(x + 2, y + 3));
  91     }
  92 };
  93
  94 template <typename T, typename C>
  95 struct value< bg::model::segment< bg::model::point<T, 2, C> > >
  96 {
  97     typedef bg::model::point<T, 2, C> P;
  98     typedef bg::model::segment<P> S;
  99     static S apply(int x, int y)
 100     {
 101         return S(P(x, y), P(x + 2, y + 3));
 102     }
 103 };
 104
 105 template <typename T, typename C>
 106 struct value< std::pair<bg::model::point<T, 2, C>, int> >
 107 {
 108     typedef bg::model::point<T, 2, C> P;
 109     typedef std::pair<P, int> R;
 110     static R apply(int x, int y)
 111     {
 112         return std::make_pair(P(x, y), x + y * 100);
 113     }
 114 };
 115
 116 template <typename T, typename C>
 117 struct value< std::pair<bg::model::box< bg::model::point<T, 2, C> >, int> >
 118 {
 119     typedef bg::model::point<T, 2, C> P;
 120     typedef bg::model::box<P> B;
 121     typedef std::pair<B, int> R;
 122     static R apply(int x, int y)
 123     {
 124         return std::make_pair(B(P(x, y), P(x + 2, y + 3)), x + y * 100);
 125     }
 126 };
 127
 128 template <typename T, typename C>
 129 struct value< std::pair<bg::model::segment< bg::model::point<T, 2, C> >, int> >
 130 {
 131     typedef bg::model::point<T, 2, C> P;
 132     typedef bg::model::segment<P> S;
 133     typedef std::pair<S, int> R;
 134     static R apply(int x, int y)
 135     {
 136         return std::make_pair(S(P(x, y), P(x + 2, y + 3)), x + y * 100);
 137     }
 138 };
 139
 140 template <typename T, typename C>
 141 struct value< boost::tuple<bg::model::point<T, 2, C>, int, int> >
 142 {
 143     typedef bg::model::point<T, 2, C> P;
 144     typedef boost::tuple<P, int, int> R;
 145     static R apply(int x, int y)
 146     {
 147         return boost::make_tuple(P(x, y), x + y * 100, 0);
 148     }
 149 };
 150
 151 template <typename T, typename C>
 152 struct value< boost::tuple<bg::model::box< bg::model::point<T, 2, C> >, int, int> >
 153 {
 154     typedef bg::model::point<T, 2, C> P;
 155     typedef bg::model::box<P> B;
 156     typedef boost::tuple<B, int, int> R;
 157     static R apply(int x, int y)
 158     {
 159         return boost::make_tuple(B(P(x, y), P(x + 2, y + 3)), x + y * 100, 0);
 160     }
 161 };
 162
 163 template <typename T, typename C>
 164 struct value< boost::tuple<bg::model::segment< bg::model::point<T, 2, C> >, int, int> >
 165 {
 166     typedef bg::model::point<T, 2, C> P;
 167     typedef bg::model::segment<P> S;
 168     typedef boost::tuple<S, int, int> R;
 169     static R apply(int x, int y)
 170     {
 171         return boost::make_tuple(S(P(x, y), P(x + 2, y + 3)), x + y * 100, 0);
 172     }
 173 };
 174
 175 template <typename T, typename C>
 176 struct value< bg::model::point<T, 3, C> >
 177 {
 178     typedef bg::model::point<T, 3, C> P;
 179     static P apply(int x, int y, int z)
 180     {
 181         return P(x, y, z);
 182     }
 183 };
 184
 185 template <typename T, typename C>
 186 struct value< bg::model::box< bg::model::point<T, 3, C> > >
 187 {
 188     typedef bg::model::point<T, 3, C> P;
 189     typedef bg::model::box<P> B;
 190     static B apply(int x, int y, int z)
 191     {
 192         return B(P(x, y, z), P(x + 2, y + 3, z + 4));
 193     }
 194 };
 195
 196 template <typename T, typename C>
 197 struct value< std::pair<bg::model::point<T, 3, C>, int> >
 198 {
 199     typedef bg::model::point<T, 3, C> P;
 200     typedef std::pair<P, int> R;
 201     static R apply(int x, int y, int z)
 202     {
 203         return std::make_pair(P(x, y, z), x + y * 100 + z * 10000);
 204     }
 205 };
 206
 207 template <typename T, typename C>
 208 struct value< std::pair<bg::model::box< bg::model::point<T, 3, C> >, int> >
 209 {
 210     typedef bg::model::point<T, 3, C> P;
 211     typedef bg::model::box<P> B;
 212     typedef std::pair<B, int> R;
 213     static R apply(int x, int y, int z)
 214     {
 215         return std::make_pair(B(P(x, y, z), P(x + 2, y + 3, z + 4)), x + y * 100 + z * 10000);
 216     }
 217 };
 218
 219 template <typename T, typename C>
 220 struct value< boost::tuple<bg::model::point<T, 3, C>, int, int> >
 221 {
 222     typedef bg::model::point<T, 3, C> P;
 223     typedef boost::tuple<P, int, int> R;
 224     static R apply(int x, int y, int z)
 225     {
 226         return boost::make_tuple(P(x, y, z), x + y * 100 + z * 10000, 0);
 227     }
 228 };
 229
 230 template <typename T, typename C>
 231 struct value< boost::tuple<bg::model::box< bg::model::point<T, 3, C> >, int, int> >
 232 {
 233     typedef bg::model::point<T, 3, C> P;
 234     typedef bg::model::box<P> B;
 235     typedef boost::tuple<B, int, int> R;
 236     static R apply(int x, int y, int z)
 237     {
 238         return boost::make_tuple(B(P(x, y, z), P(x + 2, y + 3, z + 4)), x + y * 100 + z * 10000, 0);
 239     }
 240 };
 241
 242 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 243
 244 template <typename T, typename C>
 245 struct value< std::tuple<bg::model::point<T, 2, C>, int, int> >
 246 {
 247     typedef bg::model::point<T, 2, C> P;
 248     typedef std::tuple<P, int, int> R;
 249     static R apply(int x, int y)
 250     {
 251         return std::make_tuple(P(x, y), x + y * 100, 0);
 252     }
 253 };
 254
 255 template <typename T, typename C>
 256 struct value< std::tuple<bg::model::box< bg::model::point<T, 2, C> >, int, int> >
 257 {
 258     typedef bg::model::point<T, 2, C> P;
 259     typedef bg::model::box<P> B;
 260     typedef std::tuple<B, int, int> R;
 261     static R apply(int x, int y)
 262     {
 263         return std::make_tuple(B(P(x, y), P(x + 2, y + 3)), x + y * 100, 0);
 264     }
 265 };
 266
 267 template <typename T, typename C>
 268 struct value< std::tuple<bg::model::segment< bg::model::point<T, 2, C> >, int, int> >
 269 {
 270     typedef bg::model::point<T, 2, C> P;
 271     typedef bg::model::segment<P> S;
 272     typedef std::tuple<S, int, int> R;
 273     static R apply(int x, int y)
 274     {
 275         return std::make_tuple(S(P(x, y), P(x + 2, y + 3)), x + y * 100, 0);
 276     }
 277 };
 278
 279 template <typename T, typename C>
 280 struct value< std::tuple<bg::model::point<T, 3, C>, int, int> >
 281 {
 282     typedef bg::model::point<T, 3, C> P;
 283     typedef std::tuple<P, int, int> R;
 284     static R apply(int x, int y, int z)
 285     {
 286         return std::make_tuple(P(x, y, z), x + y * 100 + z * 10000, 0);
 287     }
 288 };
 289
 290 template <typename T, typename C>
 291 struct value< std::tuple<bg::model::box< bg::model::point<T, 3, C> >, int, int> >
 292 {
 293     typedef bg::model::point<T, 3, C> P;
 294     typedef bg::model::box<P> B;
 295     typedef std::tuple<B, int, int> R;
 296     static R apply(int x, int y, int z)
 297     {
 298         return std::make_tuple(B(P(x, y, z), P(x + 2, y + 3, z + 4)), x + y * 100 + z * 10000, 0);
 299     }
 300 };
 301
 302 #endif // #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 303
 304 } // namespace generate
 305
 306 // shared_ptr value
 307
 308 template <typename Indexable>
 309 struct test_object
 310 {
 311     test_object(Indexable const& indexable_) : indexable(indexable_) {}
 312     Indexable indexable;
 313 };
 314
 315 namespace boost { namespace geometry { namespace index {
 316
 317 template <typename Indexable>
 318 struct indexable< boost::shared_ptr< test_object<Indexable> > >
 319 {
 320     typedef boost::shared_ptr< test_object<Indexable> > value_type;
 321     typedef Indexable const& result_type;
 322
 323     result_type operator()(value_type const& value) const
 324     {
 325         return value->indexable;
 326     }
 327 };
 328
 329 }}}
 330
 331 namespace generate {
 332
 333 template <typename T, typename C>
 334 struct value< boost::shared_ptr<test_object<bg::model::point<T, 2, C> > > >
 335 {
 336     typedef bg::model::point<T, 2, C> P;
 337     typedef test_object<P> O;
 338     typedef boost::shared_ptr<O> R;
 339
 340     static R apply(int x, int y)
 341     {
 342         return R(new O(P(x, y)));
 343     }
 344 };
 345
 346 template <typename T, typename C>
 347 struct value< boost::shared_ptr<test_object<bg::model::point<T, 3, C> > > >
 348 {
 349     typedef bg::model::point<T, 3, C> P;
 350     typedef test_object<P> O;
 351     typedef boost::shared_ptr<O> R;
 352
 353     static R apply(int x, int y, int z)
 354     {
 355         return R(new O(P(x, y, z)));
 356     }
 357 };
 358
 359 template <typename T, typename C>
 360 struct value< boost::shared_ptr<test_object<bg::model::box<bg::model::point<T, 2, C> > > > >
 361 {
 362     typedef bg::model::point<T, 2, C> P;
 363     typedef bg::model::box<P> B;
 364     typedef test_object<B> O;
 365     typedef boost::shared_ptr<O> R;
 366
 367     static R apply(int x, int y)
 368     {
 369         return R(new O(B(P(x, y), P(x + 2, y + 3))));
 370     }
 371 };
 372
 373 template <typename T, typename C>
 374 struct value< boost::shared_ptr<test_object<bg::model::box<bg::model::point<T, 3, C> > > > >
 375 {
 376     typedef bg::model::point<T, 3, C> P;
 377     typedef bg::model::box<P> B;
 378     typedef test_object<B> O;
 379     typedef boost::shared_ptr<O> R;
 380
 381     static R apply(int x, int y, int z)
 382     {
 383         return R(new O(B(P(x, y, z), P(x + 2, y + 3, z + 4))));
 384     }
 385 };
 386
 387 template <typename T, typename C>
 388 struct value< boost::shared_ptr<test_object<bg::model::segment<bg::model::point<T, 2, C> > > > >
 389 {
 390     typedef bg::model::point<T, 2, C> P;
 391     typedef bg::model::segment<P> S;
 392     typedef test_object<S> O;
 393     typedef boost::shared_ptr<O> R;
 394
 395     static R apply(int x, int y)
 396     {
 397         return R(new O(S(P(x, y), P(x + 2, y + 3))));
 398     }
 399 };
 400
 401 } //namespace generate
 402
 403 // counting value
 404
 405 template <typename Indexable>
 406 struct counting_value
 407 {
 408     counting_value() { counter()++; }
 409     counting_value(Indexable const& i) : indexable(i) { counter()++; }
 410     counting_value(counting_value const& c) : indexable(c.indexable) { counter()++; }
 411     ~counting_value() { counter()--; }
 412
 413     static size_t & counter() { static size_t c = 0; return c; }
 414     Indexable indexable;
 415 };
 416
 417 namespace boost { namespace geometry { namespace index {
 418
 419 template <typename Indexable>
 420 struct indexable< counting_value<Indexable> >
 421 {
 422     typedef counting_value<Indexable> value_type;
 423     typedef Indexable const& result_type;
 424     result_type operator()(value_type const& value) const
 425     {
 426         return value.indexable;
 427     }
 428 };
 429
 430 template <typename Indexable>
 431 struct equal_to< counting_value<Indexable> >
 432 {
 433     typedef counting_value<Indexable> value_type;
 434     typedef bool result_type;
 435     bool operator()(value_type const& v1, value_type const& v2) const
 436     {
 437         return boost::geometry::equals(v1.indexable, v2.indexable);
 438     }
 439 };
 440
 441 }}}
 442
 443 namespace generate {
 444
 445 template <typename T, typename C>
 446 struct value< counting_value<bg::model::point<T, 2, C> > >
 447 {
 448     typedef bg::model::point<T, 2, C> P;
 449     typedef counting_value<P> R;
 450     static R apply(int x, int y) { return R(P(x, y)); }
 451 };
 452
 453 template <typename T, typename C>
 454 struct value< counting_value<bg::model::point<T, 3, C> > >
 455 {
 456     typedef bg::model::point<T, 3, C> P;
 457     typedef counting_value<P> R;
 458     static R apply(int x, int y, int z) { return R(P(x, y, z)); }
 459 };
 460
 461 template <typename T, typename C>
 462 struct value< counting_value<bg::model::box<bg::model::point<T, 2, C> > > >
 463 {
 464     typedef bg::model::point<T, 2, C> P;
 465     typedef bg::model::box<P> B;
 466     typedef counting_value<B> R;
 467     static R apply(int x, int y) { return R(B(P(x, y), P(x+2, y+3))); }
 468 };
 469
 470 template <typename T, typename C>
 471 struct value< counting_value<bg::model::box<bg::model::point<T, 3, C> > > >
 472 {
 473     typedef bg::model::point<T, 3, C> P;
 474     typedef bg::model::box<P> B;
 475     typedef counting_value<B> R;
 476     static R apply(int x, int y, int z) { return R(B(P(x, y, z), P(x+2, y+3, z+4))); }
 477 };
 478
 479 template <typename T, typename C>
 480 struct value< counting_value<bg::model::segment<bg::model::point<T, 2, C> > > >
 481 {
 482     typedef bg::model::point<T, 2, C> P;
 483     typedef bg::model::segment<P> S;
 484     typedef counting_value<S> R;
 485     static R apply(int x, int y) { return R(S(P(x, y), P(x+2, y+3))); }
 486 };
 487
 488 } // namespace generate
 489
 490 // value without default constructor
 491
 492 template <typename Indexable>
 493 struct value_no_dctor
 494 {
 495     value_no_dctor(Indexable const& i) : indexable(i) {}
 496     Indexable indexable;
 497 };
 498
 499 namespace boost { namespace geometry { namespace index {
 500
 501 template <typename Indexable>
 502 struct indexable< value_no_dctor<Indexable> >
 503 {
 504     typedef value_no_dctor<Indexable> value_type;
 505     typedef Indexable const& result_type;
 506     result_type operator()(value_type const& value) const
 507     {
 508         return value.indexable;
 509     }
 510 };
 511
 512 template <typename Indexable>
 513 struct equal_to< value_no_dctor<Indexable> >
 514 {
 515     typedef value_no_dctor<Indexable> value_type;
 516     typedef bool result_type;
 517     bool operator()(value_type const& v1, value_type const& v2) const
 518     {
 519         return boost::geometry::equals(v1.indexable, v2.indexable);
 520     }
 521 };
 522
 523 }}}
 524
 525 namespace generate {
 526
 527 template <typename Indexable>
 528 struct value_default< value_no_dctor<Indexable> >
 529 {
 530     static value_no_dctor<Indexable> apply() { return value_no_dctor<Indexable>(Indexable()); }
 531 };
 532
 533 template <typename T, typename C>
 534 struct value< value_no_dctor<bg::model::point<T, 2, C> > >
 535 {
 536     typedef bg::model::point<T, 2, C> P;
 537     typedef value_no_dctor<P> R;
 538     static R apply(int x, int y) { return R(P(x, y)); }
 539 };
 540
 541 template <typename T, typename C>
 542 struct value< value_no_dctor<bg::model::point<T, 3, C> > >
 543 {
 544     typedef bg::model::point<T, 3, C> P;
 545     typedef value_no_dctor<P> R;
 546     static R apply(int x, int y, int z) { return R(P(x, y, z)); }
 547 };
 548
 549 template <typename T, typename C>
 550 struct value< value_no_dctor<bg::model::box<bg::model::point<T, 2, C> > > >
 551 {
 552     typedef bg::model::point<T, 2, C> P;
 553     typedef bg::model::box<P> B;
 554     typedef value_no_dctor<B> R;
 555     static R apply(int x, int y) { return R(B(P(x, y), P(x+2, y+3))); }
 556 };
 557
 558 template <typename T, typename C>
 559 struct value< value_no_dctor<bg::model::box<bg::model::point<T, 3, C> > > >
 560 {
 561     typedef bg::model::point<T, 3, C> P;
 562     typedef bg::model::box<P> B;
 563     typedef value_no_dctor<B> R;
 564     static R apply(int x, int y, int z) { return R(B(P(x, y, z), P(x+2, y+3, z+4))); }
 565 };
 566
 567 template <typename T, typename C>
 568 struct value< value_no_dctor<bg::model::segment<bg::model::point<T, 2, C> > > >
 569 {
 570     typedef bg::model::point<T, 2, C> P;
 571     typedef bg::model::segment<P> S;
 572     typedef value_no_dctor<S> R;
 573     static R apply(int x, int y) { return R(S(P(x, y), P(x+2, y+3))); }
 574 };
 575
 576 // generate input
 577
 578 template <size_t Dimension>
 579 struct input
 580 {};
 581
 582 template <>
 583 struct input<2>
 584 {
 585     template <typename Value, typename Box>
 586     static void apply(std::vector<Value> & input, Box & qbox, int size = 1)
 587     {
 588         BOOST_GEOMETRY_INDEX_ASSERT(0 < size, "the value must be greather than 0");
 589
 590         for ( int i = 0 ; i < 12 * size ; i += 3 )
 591         {
 592             for ( int j = 1 ; j < 25 * size ; j += 4 )
 593             {
 594                 input.push_back( generate::value<Value>::apply(i, j) );
 595             }
 596         }
 597
 598         typedef typename bg::traits::point_type<Box>::type P;
 599
 600         qbox = Box(P(3, 0), P(10, 9));
 601     }
 602 };
 603
 604 template <>
 605 struct input<3>
 606 {
 607     template <typename Value, typename Box>
 608     static void apply(std::vector<Value> & input, Box & qbox, int size = 1)
 609     {
 610         BOOST_GEOMETRY_INDEX_ASSERT(0 < size, "the value must be greather than 0");
 611
 612         for ( int i = 0 ; i < 12 * size ; i += 3 )
 613         {
 614             for ( int j = 1 ; j < 25 * size ; j += 4 )
 615             {
 616                 for ( int k = 2 ; k < 12 * size ; k += 5 )
 617                 {
 618                     input.push_back( generate::value<Value>::apply(i, j, k) );
 619                 }
 620             }
 621         }
 622
 623         typedef typename bg::traits::point_type<Box>::type P;
 624
 625         qbox = Box(P(3, 0, 3), P(10, 9, 11));
 626     }
 627 };
 628
 629 // generate_value_outside
 630
 631 template <typename Value, size_t Dimension>
 632 struct value_outside_impl
 633 {};
 634
 635 template <typename Value>
 636 struct value_outside_impl<Value, 2>
 637 {
 638     static Value apply()
 639     {
 640         //TODO - for size > 1 in generate_input<> this won't be outside
 641         return generate::value<Value>::apply(13, 26);
 642     }
 643 };
 644
 645 template <typename Value>
 646 struct value_outside_impl<Value, 3>
 647 {
 648     static Value apply()
 649     {
 650         //TODO - for size > 1 in generate_input<> this won't be outside
 651         return generate::value<Value>::apply(13, 26, 13);
 652     }
 653 };
 654
 655 template <typename Rtree>
 656 inline typename Rtree::value_type
 657 value_outside()
 658 {
 659     typedef typename Rtree::value_type V;
 660     typedef typename Rtree::indexable_type I;
 661
 662     return value_outside_impl<V, bg::dimension<I>::value>::apply();
 663 }
 664
 665 template<typename Rtree, typename Elements, typename Box>
 666 void rtree(Rtree & tree, Elements & input, Box & qbox)
 667 {
 668     typedef typename Rtree::indexable_type I;
 669
 670     generate::input<
 671         bg::dimension<I>::value
 672     >::apply(input, qbox);
 673
 674     tree.insert(input.begin(), input.end());
 675 }
 676
 677 } // namespace generate
 678
 679 namespace basictest {
 680
 681 // low level test functions
 682
 683 template <typename Rtree, typename Iter, typename Value>
 684 Iter find(Rtree const& rtree, Iter first, Iter last, Value const& value)
 685 {
 686     for ( ; first != last ; ++first )
 687         if ( rtree.value_eq()(value, *first) )
 688             return first;
 689     return first;
 690 }
 691
 692 template <typename Rtree, typename Value>
 693 void compare_outputs(Rtree const& rtree, std::vector<Value> const& output, std::vector<Value> const& expected_output)
 694 {
 695     bool are_sizes_ok = (expected_output.size() == output.size());
 696     BOOST_CHECK( are_sizes_ok );
 697     if ( are_sizes_ok )
 698     {
 699         BOOST_FOREACH(Value const& v, expected_output)
 700         {
 701             BOOST_CHECK(find(rtree, output.begin(), output.end(), v) != output.end() );
 702         }
 703     }
 704 }
 705
 706 template <typename Rtree, typename Range1, typename Range2>
 707 void exactly_the_same_outputs(Rtree const& rtree, Range1 const& output, Range2 const& expected_output)
 708 {
 709     size_t s1 = std::distance(output.begin(), output.end());
 710     size_t s2 = std::distance(expected_output.begin(), expected_output.end());
 711     BOOST_CHECK(s1 == s2);
 712
 713     if ( s1 == s2 )
 714     {
 715         typename Range1::const_iterator it1 = output.begin();
 716         typename Range2::const_iterator it2 = expected_output.begin();
 717         for ( ; it1 != output.end() && it2 != expected_output.end() ; ++it1, ++it2 )
 718         {
 719             if ( !rtree.value_eq()(*it1, *it2) )
 720             {
 721                 BOOST_CHECK(false && "rtree.translator().equals(*it1, *it2)");
 722                 break;
 723             }
 724         }
 725     }
 726 }
 727
 728 // alternative version of std::copy taking iterators of differnet types
 729 template <typename First, typename Last, typename Out>
 730 void copy_alt(First first, Last last, Out out)
 731 {
 732     for ( ; first != last ; ++first, ++out )
 733         *out = *first;
 734 }
 735
 736 // test query iterators
 737 template <typename QItF, typename QItL>
 738 void check_fwd_iterators(QItF first, QItL last)
 739 {
 740     QItF vinit = QItF();
 741     BOOST_CHECK(vinit == last);
 742
 743 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
 744     QItL vinit2 = QItL();
 745     BOOST_CHECK(vinit2 == last);
 746 #endif
 747
 748     QItF def;
 749     BOOST_CHECK(def == last);
 750
 751 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
 752     QItL def2;
 753     BOOST_CHECK(def2 == last);
 754 #endif
 755
 756     QItF it = first;
 757     for ( ; it != last && first != last ; ++it, ++first)
 758     {
 759         BOOST_CHECK(it == first);
 760
 761         bg::index::equal_to<typename std::iterator_traits<QItF>::value_type> eq;
 762         BOOST_CHECK(eq(*it, *first));
 763     }
 764     BOOST_CHECK(it == last);
 765     BOOST_CHECK(first == last);
 766 }
 767
 768 // spatial query
 769
 770 template <typename Rtree, typename Value, typename Predicates>
 771 void spatial_query(Rtree & rtree, Predicates const& pred, std::vector<Value> const& expected_output)
 772 {
 773     BOOST_CHECK( bgi::detail::rtree::utilities::are_levels_ok(rtree) );
 774     if ( !rtree.empty() )
 775         BOOST_CHECK( bgi::detail::rtree::utilities::are_boxes_ok(rtree) );
 776
 777     std::vector<Value> output;
 778     size_t n = rtree.query(pred, std::back_inserter(output));
 779
 780     BOOST_CHECK( expected_output.size() == n );
 781     compare_outputs(rtree, output, expected_output);
 782
 783     std::vector<Value> output2;
 784     size_t n2 = query(rtree, pred, std::back_inserter(output2));
 785
 786     BOOST_CHECK( n == n2 );
 787     exactly_the_same_outputs(rtree, output, output2);
 788
 789     exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::queried(pred));
 790
 791     std::vector<Value> output3;
 792     std::copy(rtree.qbegin(pred), rtree.qend(), std::back_inserter(output3));
 793
 794     compare_outputs(rtree, output3, expected_output);
 795
 796     std::vector<Value> output4;
 797     std::copy(qbegin(rtree, pred), qend(rtree), std::back_inserter(output4));
 798
 799     exactly_the_same_outputs(rtree, output3, output4);
 800
 801     check_fwd_iterators(rtree.qbegin(pred), rtree.qend());
 802
 803 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
 804     {
 805         std::vector<Value> output4;
 806         std::copy(rtree.qbegin_(pred), rtree.qend_(pred), std::back_inserter(output4));
 807         compare_outputs(rtree, output4, expected_output);
 808         output4.clear();
 809         copy_alt(rtree.qbegin_(pred), rtree.qend_(), std::back_inserter(output4));
 810         compare_outputs(rtree, output4, expected_output);
 811
 812         check_fwd_iterators(rtree.qbegin_(pred), rtree.qend_(pred));
 813         check_fwd_iterators(rtree.qbegin_(pred), rtree.qend_());
 814     }
 815 #endif
 816 }
 817
 818 // rtree specific queries tests
 819
 820 template <typename Rtree, typename Value, typename Box>
 821 void intersects(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 822 {
 823     std::vector<Value> expected_output;
 824
 825     BOOST_FOREACH(Value const& v, input)
 826         if ( bg::intersects(tree.indexable_get()(v), qbox) )
 827             expected_output.push_back(v);
 828
 829     //spatial_query(tree, qbox, expected_output);
 830     spatial_query(tree, bgi::intersects(qbox), expected_output);
 831     spatial_query(tree, !bgi::disjoint(qbox), expected_output);
 832
 833     /*typedef bg::traits::point_type<Box>::type P;
 834     bg::model::ring<P> qring;
 835     bg::convert(qbox, qring);
 836     spatial_query(tree, bgi::intersects(qring), expected_output);
 837     spatial_query(tree, !bgi::disjoint(qring), expected_output);
 838     bg::model::polygon<P> qpoly;
 839     bg::convert(qbox, qpoly);
 840     spatial_query(tree, bgi::intersects(qpoly), expected_output);
 841     spatial_query(tree, !bgi::disjoint(qpoly), expected_output);*/
 842 }
 843
 844 template <typename Rtree, typename Value, typename Box>
 845 void disjoint(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 846 {
 847     std::vector<Value> expected_output;
 848
 849     BOOST_FOREACH(Value const& v, input)
 850         if ( bg::disjoint(tree.indexable_get()(v), qbox) )
 851             expected_output.push_back(v);
 852
 853     spatial_query(tree, bgi::disjoint(qbox), expected_output);
 854     spatial_query(tree, !bgi::intersects(qbox), expected_output);
 855
 856     /*typedef bg::traits::point_type<Box>::type P;
 857     bg::model::ring<P> qring;
 858     bg::convert(qbox, qring);
 859     spatial_query(tree, bgi::disjoint(qring), expected_output);
 860     bg::model::polygon<P> qpoly;
 861     bg::convert(qbox, qpoly);
 862     spatial_query(tree, bgi::disjoint(qpoly), expected_output);*/
 863 }
 864
 865 template <typename Tag>
 866 struct contains_impl
 867 {
 868     template <typename Rtree, typename Value, typename Box>
 869     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 870     {
 871         std::vector<Value> expected_output;
 872
 873         BOOST_FOREACH(Value const& v, input)
 874             if ( bg::within(qbox, tree.indexable_get()(v)) )
 875                 expected_output.push_back(v);
 876
 877         spatial_query(tree, bgi::contains(qbox), expected_output);
 878
 879         /*typedef bg::traits::point_type<Box>::type P;
 880         bg::model::ring<P> qring;
 881         bg::convert(qbox, qring);
 882         spatial_query(tree, bgi::contains(qring), expected_output);
 883         bg::model::polygon<P> qpoly;
 884         bg::convert(qbox, qpoly);
 885         spatial_query(tree, bgi::contains(qpoly), expected_output);*/
 886     }
 887 };
 888
 889 template <>
 890 struct contains_impl<bg::point_tag>
 891 {
 892     template <typename Rtree, typename Value, typename Box>
 893     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 894     {}
 895 };
 896
 897 template <>
 898 struct contains_impl<bg::segment_tag>
 899 {
 900     template <typename Rtree, typename Value, typename Box>
 901     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 902     {}
 903 };
 904
 905 template <typename Rtree, typename Value, typename Box>
 906 void contains(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 907 {
 908     contains_impl<
 909         typename bg::tag<
 910             typename Rtree::indexable_type
 911         >::type
 912     >::apply(tree, input, qbox);
 913 }
 914
 915 template <typename Tag>
 916 struct covered_by_impl
 917 {
 918     template <typename Rtree, typename Value, typename Box>
 919     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 920     {
 921         std::vector<Value> expected_output;
 922
 923         BOOST_FOREACH(Value const& v, input)
 924         {
 925             if ( bg::covered_by(
 926                     bgi::detail::return_ref_or_bounds(
 927                         tree.indexable_get()(v)),
 928                     qbox) )
 929             {
 930                 expected_output.push_back(v);
 931             }
 932         }
 933
 934         spatial_query(tree, bgi::covered_by(qbox), expected_output);
 935
 936         /*typedef bg::traits::point_type<Box>::type P;
 937         bg::model::ring<P> qring;
 938         bg::convert(qbox, qring);
 939         spatial_query(tree, bgi::covered_by(qring), expected_output);
 940         bg::model::polygon<P> qpoly;
 941         bg::convert(qbox, qpoly);
 942         spatial_query(tree, bgi::covered_by(qpoly), expected_output);*/
 943     }
 944 };
 945
 946 template <>
 947 struct covered_by_impl<bg::segment_tag>
 948 {
 949     template <typename Rtree, typename Value, typename Box>
 950     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 951     {}
 952 };
 953
 954 template <typename Rtree, typename Value, typename Box>
 955 void covered_by(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 956 {
 957     covered_by_impl<
 958         typename bg::tag<
 959             typename Rtree::indexable_type
 960         >::type
 961     >::apply(tree, input, qbox);
 962 }
 963
 964 template <typename Tag>
 965 struct covers_impl
 966 {
 967     template <typename Rtree, typename Value, typename Box>
 968     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 969     {
 970         std::vector<Value> expected_output;
 971
 972         BOOST_FOREACH(Value const& v, input)
 973             if ( bg::covered_by(qbox, tree.indexable_get()(v)) )
 974                 expected_output.push_back(v);
 975
 976         spatial_query(tree, bgi::covers(qbox), expected_output);
 977
 978         /*typedef bg::traits::point_type<Box>::type P;
 979         bg::model::ring<P> qring;
 980         bg::convert(qbox, qring);
 981         spatial_query(tree, bgi::covers(qring), expected_output);
 982         bg::model::polygon<P> qpoly;
 983         bg::convert(qbox, qpoly);
 984         spatial_query(tree, bgi::covers(qpoly), expected_output);*/
 985     }
 986 };
 987
 988 template <>
 989 struct covers_impl<bg::point_tag>
 990 {
 991     template <typename Rtree, typename Value, typename Box>
 992     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 993     {}
 994 };
 995
 996 template <>
 997 struct covers_impl<bg::segment_tag>
 998 {
 999     template <typename Rtree, typename Value, typename Box>
1000     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1001     {}
1002 };
1003
1004 template <typename Rtree, typename Value, typename Box>
1005 void covers(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1006 {
1007     covers_impl<
1008         typename bg::tag<
1009             typename Rtree::indexable_type
1010         >::type
1011     >::apply(tree, input, qbox);
1012 }
1013
1014 template <typename Tag>
1015 struct overlaps_impl
1016 {
1017     template <typename Rtree, typename Value, typename Box>
1018     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1019     {
1020         std::vector<Value> expected_output;
1021
1022         BOOST_FOREACH(Value const& v, input)
1023             if ( bg::overlaps(tree.indexable_get()(v), qbox) )
1024                 expected_output.push_back(v);
1025
1026         spatial_query(tree, bgi::overlaps(qbox), expected_output);
1027
1028         /*typedef bg::traits::point_type<Box>::type P;
1029         bg::model::ring<P> qring;
1030         bg::convert(qbox, qring);
1031         spatial_query(tree, bgi::overlaps(qring), expected_output);
1032         bg::model::polygon<P> qpoly;
1033         bg::convert(qbox, qpoly);
1034         spatial_query(tree, bgi::overlaps(qpoly), expected_output);*/
1035     }
1036 };
1037
1038 template <>
1039 struct overlaps_impl<bg::point_tag>
1040 {
1041     template <typename Rtree, typename Value, typename Box>
1042     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1043     {}
1044 };
1045
1046 template <>
1047 struct overlaps_impl<bg::segment_tag>
1048 {
1049     template <typename Rtree, typename Value, typename Box>
1050     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1051     {}
1052 };
1053
1054 template <typename Rtree, typename Value, typename Box>
1055 void overlaps(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1056 {
1057     overlaps_impl<
1058         typename bg::tag<
1059             typename Rtree::indexable_type
1060         >::type
1061     >::apply(tree, input, qbox);
1062 }
1063
1064 //template <typename Tag, size_t Dimension>
1065 //struct touches_impl
1066 //{
1067 //    template <typename Rtree, typename Value, typename Box>
1068 //    static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1069 //    {}
1070 //};
1071 //
1072 //template <>
1073 //struct touches_impl<bg::box_tag, 2>
1074 //{
1075 //    template <typename Rtree, typename Value, typename Box>
1076 //    static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1077 //    {
1078 //        std::vector<Value> expected_output;
1079 //
1080 //        BOOST_FOREACH(Value const& v, input)
1081 //            if ( bg::touches(tree.translator()(v), qbox) )
1082 //                expected_output.push_back(v);
1083 //
1084 //        spatial_query(tree, bgi::touches(qbox), expected_output);
1085 //    }
1086 //};
1087 //
1088 //template <typename Rtree, typename Value, typename Box>
1089 //void touches(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1090 //{
1091 //    touches_impl<
1092 //        bgi::traits::tag<typename Rtree::indexable_type>::type,
1093 //        bgi::traits::dimension<typename Rtree::indexable_type>::value
1094 //    >::apply(tree, input, qbox);
1095 //}
1096
1097 template <typename Tag>
1098 struct within_impl
1099 {
1100     template <typename Rtree, typename Value, typename Box>
1101     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1102     {
1103         std::vector<Value> expected_output;
1104
1105         BOOST_FOREACH(Value const& v, input)
1106             if ( bg::within(tree.indexable_get()(v), qbox) )
1107                 expected_output.push_back(v);
1108
1109         spatial_query(tree, bgi::within(qbox), expected_output);
1110
1111         /*typedef bg::traits::point_type<Box>::type P;
1112         bg::model::ring<P> qring;
1113         bg::convert(qbox, qring);
1114         spatial_query(tree, bgi::within(qring), expected_output);
1115         bg::model::polygon<P> qpoly;
1116         bg::convert(qbox, qpoly);
1117         spatial_query(tree, bgi::within(qpoly), expected_output);*/
1118     }
1119 };
1120
1121 template <>
1122 struct within_impl<bg::segment_tag>
1123 {
1124     template <typename Rtree, typename Value, typename Box>
1125     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1126     {}
1127 };
1128
1129 template <typename Rtree, typename Value, typename Box>
1130 void within(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1131 {
1132     within_impl<
1133         typename bg::tag<
1134             typename Rtree::indexable_type
1135         >::type
1136     >::apply(tree, input, qbox);
1137 }
1138
1139 // rtree nearest queries
1140
1141 template <typename Rtree, typename Point>
1142 struct NearestKLess
1143 {
1144     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1145
1146     template <typename Value>
1147     bool operator()(std::pair<D, Value> const& p1, std::pair<D, Value> const& p2) const
1148     {
1149         return p1.first < p2.first;
1150     }
1151 };
1152
1153 template <typename Rtree, typename Point>
1154 struct NearestKTransform
1155 {
1156     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1157
1158     template <typename Value>
1159     Value const& operator()(std::pair<D, Value> const& p) const
1160     {
1161         return p.second;
1162     }
1163 };
1164
1165 template <typename Rtree, typename Value, typename Point, typename Distance>
1166 inline void compare_nearest_outputs(Rtree const& rtree, std::vector<Value> const& output, std::vector<Value> const& expected_output, Point const& pt, Distance greatest_distance)
1167 {
1168     // check output
1169     bool are_sizes_ok = (expected_output.size() == output.size());
1170     BOOST_CHECK( are_sizes_ok );
1171     if ( are_sizes_ok )
1172     {
1173         BOOST_FOREACH(Value const& v, output)
1174         {
1175             // TODO - perform explicit check here?
1176             // should all objects which are closest be checked and should exactly the same be found?
1177
1178             if ( find(rtree, expected_output.begin(), expected_output.end(), v) == expected_output.end() )
1179             {
1180                 Distance d = bg::comparable_distance(pt, rtree.indexable_get()(v));
1181                 BOOST_CHECK(d == greatest_distance);
1182             }
1183         }
1184     }
1185 }
1186
1187 template <typename Rtree, typename Value, typename Point>
1188 inline void check_sorted_by_distance(Rtree const& rtree, std::vector<Value> const& output, Point const& pt)
1189 {
1190     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1191
1192     D prev_dist = 0;
1193     BOOST_FOREACH(Value const& v, output)
1194     {
1195         D d = bg::comparable_distance(pt, rtree.indexable_get()(v));
1196         BOOST_CHECK(prev_dist <= d);
1197         prev_dist = d;
1198     }
1199 }
1200
1201 template <typename Rtree, typename Value, typename Point>
1202 inline void nearest_query_k(Rtree const& rtree, std::vector<Value> const& input, Point const& pt, unsigned int k)
1203 {
1204     // TODO: Nearest object may not be the same as found by the rtree if distances are equal
1205     // All objects with the same closest distance should be picked
1206
1207     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1208
1209     std::vector< std::pair<D, Value> > test_output;
1210
1211     // calculate test output - k closest values pairs
1212     BOOST_FOREACH(Value const& v, input)
1213     {
1214         D d = bg::comparable_distance(pt, rtree.indexable_get()(v));
1215
1216         if ( test_output.size() < k )
1217             test_output.push_back(std::make_pair(d, v));
1218         else
1219         {
1220             std::sort(test_output.begin(), test_output.end(), NearestKLess<Rtree, Point>());
1221             if ( d < test_output.back().first )
1222                 test_output.back() = std::make_pair(d, v);
1223         }
1224     }
1225
1226     // caluclate biggest distance
1227     std::sort(test_output.begin(), test_output.end(), NearestKLess<Rtree, Point>());
1228     D greatest_distance = 0;
1229     if ( !test_output.empty() )
1230         greatest_distance = test_output.back().first;
1231
1232     // transform test output to vector of values
1233     std::vector<Value> expected_output(test_output.size(), generate::value_default<Value>::apply());
1234     std::transform(test_output.begin(), test_output.end(), expected_output.begin(), NearestKTransform<Rtree, Point>());
1235
1236     // calculate output using rtree
1237     std::vector<Value> output;
1238     rtree.query(bgi::nearest(pt, k), std::back_inserter(output));
1239
1240     // check output
1241     compare_nearest_outputs(rtree, output, expected_output, pt, greatest_distance);
1242
1243     exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::queried(bgi::nearest(pt, k)));
1244
1245     std::vector<Value> output2(k, generate::value_default<Value>::apply());
1246     typename Rtree::size_type found_count = rtree.query(bgi::nearest(pt, k), output2.begin());
1247     output2.resize(found_count, generate::value_default<Value>::apply());
1248
1249     exactly_the_same_outputs(rtree, output, output2);
1250
1251     std::vector<Value> output3;
1252     std::copy(rtree.qbegin(bgi::nearest(pt, k)), rtree.qend(), std::back_inserter(output3));
1253
1254     compare_nearest_outputs(rtree, output3, expected_output, pt, greatest_distance);
1255     check_sorted_by_distance(rtree, output3, pt);
1256
1257     check_fwd_iterators(rtree.qbegin(bgi::nearest(pt, k)), rtree.qend());
1258
1259 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
1260     {
1261         std::vector<Value> output4;
1262         std::copy(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(bgi::nearest(pt, k)), std::back_inserter(output4));
1263         exactly_the_same_outputs(rtree, output4, output3);
1264         output4.clear();
1265         copy_alt(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(), std::back_inserter(output4));
1266         exactly_the_same_outputs(rtree, output4, output3);
1267
1268         check_fwd_iterators(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(bgi::nearest(pt, k)));
1269         check_fwd_iterators(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_());
1270     }
1271 #endif
1272 }
1273
1274 // rtree nearest not found
1275
1276 struct AlwaysFalse
1277 {
1278     template <typename Value>
1279     bool operator()(Value const& ) const { return false; }
1280 };
1281
1282 template <typename Rtree, typename Point>
1283 void nearest_query_not_found(Rtree const& rtree, Point const& pt)
1284 {
1285     typedef typename Rtree::value_type Value;
1286
1287     std::vector<Value> output_v;
1288     size_t n_res = rtree.query(bgi::nearest(pt, 5) && bgi::satisfies(AlwaysFalse()), std::back_inserter(output_v));
1289     BOOST_CHECK(output_v.size() == n_res);
1290     BOOST_CHECK(n_res < 5);
1291 }
1292
1293 template <typename Value>
1294 bool satisfies_fun(Value const& ) { return true; }
1295
1296 struct satisfies_obj
1297 {
1298     template <typename Value>
1299     bool operator()(Value const& ) const { return true; }
1300 };
1301
1302 template <typename Rtree, typename Value>
1303 void satisfies(Rtree const& rtree, std::vector<Value> const& input)
1304 {
1305     std::vector<Value> result;
1306     rtree.query(bgi::satisfies(satisfies_obj()), std::back_inserter(result));
1307     BOOST_CHECK(result.size() == input.size());
1308     result.clear();
1309     rtree.query(!bgi::satisfies(satisfies_obj()), std::back_inserter(result));
1310     BOOST_CHECK(result.size() == 0);
1311
1312     result.clear();
1313     rtree.query(bgi::satisfies(satisfies_fun<Value>), std::back_inserter(result));
1314     BOOST_CHECK(result.size() == input.size());
1315     result.clear();
1316     rtree.query(!bgi::satisfies(satisfies_fun<Value>), std::back_inserter(result));
1317     BOOST_CHECK(result.size() == 0);
1318
1319 #ifndef BOOST_NO_CXX11_LAMBDAS
1320     result.clear();
1321     rtree.query(bgi::satisfies([](Value const&){ return true; }), std::back_inserter(result));
1322     BOOST_CHECK(result.size() == input.size());
1323     result.clear();
1324     rtree.query(!bgi::satisfies([](Value const&){ return true; }), std::back_inserter(result));
1325     BOOST_CHECK(result.size() == 0);
1326 #endif
1327 }
1328
1329 // rtree copying and moving
1330
1331 template <typename Rtree, typename Box>
1332 void copy_swap_move(Rtree const& tree, Box const& qbox)
1333 {
1334     typedef typename Rtree::value_type Value;
1335     typedef typename Rtree::parameters_type Params;
1336
1337     size_t s = tree.size();
1338     Params params = tree.parameters();
1339
1340     std::vector<Value> expected_output;
1341     tree.query(bgi::intersects(qbox), std::back_inserter(expected_output));
1342
1343     // copy constructor
1344     Rtree t1(tree);
1345
1346     BOOST_CHECK(tree.empty() == t1.empty());
1347     BOOST_CHECK(tree.size() == t1.size());
1348     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1349     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1350
1351     std::vector<Value> output;
1352     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1353     exactly_the_same_outputs(t1, output, expected_output);
1354
1355     // copying assignment operator
1356     t1 = tree;
1357
1358     BOOST_CHECK(tree.empty() == t1.empty());
1359     BOOST_CHECK(tree.size() == t1.size());
1360     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1361     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1362
1363     output.clear();
1364     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1365     exactly_the_same_outputs(t1, output, expected_output);
1366
1367     Rtree t2(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1368     t2.swap(t1);
1369     BOOST_CHECK(tree.empty() == t2.empty());
1370     BOOST_CHECK(tree.size() == t2.size());
1371     BOOST_CHECK(true == t1.empty());
1372     BOOST_CHECK(0 == t1.size());
1373     // those fails e.g. on darwin 4.2.1 because it can't copy base obejcts properly
1374     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1375     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1376     BOOST_CHECK(t2.parameters().get_max_elements() == params.get_max_elements());
1377     BOOST_CHECK(t2.parameters().get_min_elements() == params.get_min_elements());
1378
1379     output.clear();
1380     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1381     BOOST_CHECK(output.empty());
1382
1383     output.clear();
1384     t2.query(bgi::intersects(qbox), std::back_inserter(output));
1385     exactly_the_same_outputs(t2, output, expected_output);
1386     t2.swap(t1);
1387     // those fails e.g. on darwin 4.2.1 because it can't copy base obejcts properly
1388     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1389     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1390     BOOST_CHECK(t2.parameters().get_max_elements() == params.get_max_elements());
1391     BOOST_CHECK(t2.parameters().get_min_elements() == params.get_min_elements());
1392
1393     // moving constructor
1394     Rtree t3(boost::move(t1), tree.get_allocator());
1395
1396     BOOST_CHECK(t3.size() == s);
1397     BOOST_CHECK(t1.size() == 0);
1398     BOOST_CHECK(t3.parameters().get_max_elements() == params.get_max_elements());
1399     BOOST_CHECK(t3.parameters().get_min_elements() == params.get_min_elements());
1400
1401     output.clear();
1402     t3.query(bgi::intersects(qbox), std::back_inserter(output));
1403     exactly_the_same_outputs(t3, output, expected_output);
1404
1405     // moving assignment operator
1406     t1 = boost::move(t3);
1407
1408     BOOST_CHECK(t1.size() == s);
1409     BOOST_CHECK(t3.size() == 0);
1410     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1411     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1412
1413     output.clear();
1414     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1415     exactly_the_same_outputs(t1, output, expected_output);
1416
1417     //TODO - test SWAP
1418
1419     ::boost::ignore_unused_variable_warning(params);
1420 }
1421
1422 template <typename I, typename O>
1423 inline void my_copy(I first, I last, O out)
1424 {
1425     for ( ; first != last ; ++first, ++out )
1426         *out = *first;
1427 }
1428
1429 // rtree creation and insertion
1430
1431 template <typename Rtree, typename Value, typename Box>
1432 void create_insert(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1433 {
1434     std::vector<Value> expected_output;
1435     tree.query(bgi::intersects(qbox), std::back_inserter(expected_output));
1436
1437     {
1438         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1439         BOOST_FOREACH(Value const& v, input)
1440             t.insert(v);
1441         BOOST_CHECK(tree.size() == t.size());
1442         std::vector<Value> output;
1443         t.query(bgi::intersects(qbox), std::back_inserter(output));
1444         exactly_the_same_outputs(t, output, expected_output);
1445     }
1446     {
1447         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1448         //std::copy(input.begin(), input.end(), bgi::inserter(t));
1449         my_copy(input.begin(), input.end(), bgi::inserter(t)); // to suppress MSVC warnings
1450         BOOST_CHECK(tree.size() == t.size());
1451         std::vector<Value> output;
1452         t.query(bgi::intersects(qbox), std::back_inserter(output));
1453         exactly_the_same_outputs(t, output, expected_output);
1454     }
1455     {
1456         Rtree t(input.begin(), input.end(), tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1457         BOOST_CHECK(tree.size() == t.size());
1458         std::vector<Value> output;
1459         t.query(bgi::intersects(qbox), std::back_inserter(output));
1460         compare_outputs(t, output, expected_output);
1461     }
1462     {
1463         Rtree t(input, tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1464         BOOST_CHECK(tree.size() == t.size());
1465         std::vector<Value> output;
1466         t.query(bgi::intersects(qbox), std::back_inserter(output));
1467         compare_outputs(t, output, expected_output);
1468     }
1469     {
1470         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1471         t.insert(input.begin(), input.end());
1472         BOOST_CHECK(tree.size() == t.size());
1473         std::vector<Value> output;
1474         t.query(bgi::intersects(qbox), std::back_inserter(output));
1475         exactly_the_same_outputs(t, output, expected_output);
1476     }
1477     {
1478         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1479         t.insert(input);
1480         BOOST_CHECK(tree.size() == t.size());
1481         std::vector<Value> output;
1482         t.query(bgi::intersects(qbox), std::back_inserter(output));
1483         exactly_the_same_outputs(t, output, expected_output);
1484     }
1485
1486     {
1487         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1488         BOOST_FOREACH(Value const& v, input)
1489             bgi::insert(t, v);
1490         BOOST_CHECK(tree.size() == t.size());
1491         std::vector<Value> output;
1492         bgi::query(t, bgi::intersects(qbox), std::back_inserter(output));
1493         exactly_the_same_outputs(t, output, expected_output);
1494     }
1495     {
1496         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1497         bgi::insert(t, input.begin(), input.end());
1498         BOOST_CHECK(tree.size() == t.size());
1499         std::vector<Value> output;
1500         bgi::query(t, bgi::intersects(qbox), std::back_inserter(output));
1501         exactly_the_same_outputs(t, output, expected_output);
1502     }
1503     {
1504         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1505         bgi::insert(t, input);
1506         BOOST_CHECK(tree.size() == t.size());
1507         std::vector<Value> output;
1508         bgi::query(t, bgi::intersects(qbox), std::back_inserter(output));
1509         exactly_the_same_outputs(t, output, expected_output);
1510     }
1511 }
1512
1513 // rtree removing
1514
1515 template <typename Rtree, typename Box>
1516 void remove(Rtree const& tree, Box const& qbox)
1517 {
1518     typedef typename Rtree::value_type Value;
1519
1520     std::vector<Value> values_to_remove;
1521     tree.query(bgi::intersects(qbox), std::back_inserter(values_to_remove));
1522     BOOST_CHECK(0 < values_to_remove.size());
1523
1524     std::vector<Value> expected_output;
1525     tree.query(bgi::disjoint(qbox), std::back_inserter(expected_output));
1526     size_t expected_removed_count = values_to_remove.size();
1527     size_t expected_size_after_remove = tree.size() - values_to_remove.size();
1528
1529     // Add value which is not stored in the Rtree
1530     Value outsider = generate::value_outside<Rtree>();
1531     values_to_remove.push_back(outsider);
1532
1533     {
1534         Rtree t(tree);
1535         size_t r = 0;
1536         BOOST_FOREACH(Value const& v, values_to_remove)
1537             r += t.remove(v);
1538         BOOST_CHECK( r == expected_removed_count );
1539         std::vector<Value> output;
1540         t.query(bgi::disjoint(qbox), std::back_inserter(output));
1541         BOOST_CHECK( t.size() == expected_size_after_remove );
1542         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1543         compare_outputs(t, output, expected_output);
1544     }
1545     {
1546         Rtree t(tree);
1547         size_t r = t.remove(values_to_remove.begin(), values_to_remove.end());
1548         BOOST_CHECK( r == expected_removed_count );
1549         std::vector<Value> output;
1550         t.query(bgi::disjoint(qbox), std::back_inserter(output));
1551         BOOST_CHECK( t.size() == expected_size_after_remove );
1552         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1553         compare_outputs(t, output, expected_output);
1554     }
1555     {
1556         Rtree t(tree);
1557         size_t r = t.remove(values_to_remove);
1558         BOOST_CHECK( r == expected_removed_count );
1559         std::vector<Value> output;
1560         t.query(bgi::disjoint(qbox), std::back_inserter(output));
1561         BOOST_CHECK( t.size() == expected_size_after_remove );
1562         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1563         compare_outputs(t, output, expected_output);
1564     }
1565
1566     {
1567         Rtree t(tree);
1568         size_t r = 0;
1569         BOOST_FOREACH(Value const& v, values_to_remove)
1570             r += bgi::remove(t, v);
1571         BOOST_CHECK( r == expected_removed_count );
1572         std::vector<Value> output;
1573         bgi::query(t, bgi::disjoint(qbox), std::back_inserter(output));
1574         BOOST_CHECK( t.size() == expected_size_after_remove );
1575         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1576         compare_outputs(t, output, expected_output);
1577     }
1578     {
1579         Rtree t(tree);
1580         size_t r = bgi::remove(t, values_to_remove.begin(), values_to_remove.end());
1581         BOOST_CHECK( r == expected_removed_count );
1582         std::vector<Value> output;
1583         bgi::query(t, bgi::disjoint(qbox), std::back_inserter(output));
1584         BOOST_CHECK( t.size() == expected_size_after_remove );
1585         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1586         compare_outputs(t, output, expected_output);
1587     }
1588     {
1589         Rtree t(tree);
1590         size_t r = bgi::remove(t, values_to_remove);
1591         BOOST_CHECK( r == expected_removed_count );
1592         std::vector<Value> output;
1593         bgi::query(t, bgi::disjoint(qbox), std::back_inserter(output));
1594         BOOST_CHECK( t.size() == expected_size_after_remove );
1595         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1596         compare_outputs(t, output, expected_output);
1597     }
1598 }
1599
1600 template <typename Rtree, typename Value, typename Box>
1601 void clear(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1602 {
1603     std::vector<Value> values_to_remove;
1604     tree.query(bgi::intersects(qbox), std::back_inserter(values_to_remove));
1605     BOOST_CHECK(0 < values_to_remove.size());
1606
1607     //clear
1608     {
1609         Rtree t(tree);
1610
1611         std::vector<Value> expected_output;
1612         t.query(bgi::intersects(qbox), std::back_inserter(expected_output));
1613         size_t s = t.size();
1614         t.clear();
1615         BOOST_CHECK(t.empty());
1616         BOOST_CHECK(t.size() == 0);
1617         t.insert(input);
1618         BOOST_CHECK(t.size() == s);
1619         std::vector<Value> output;
1620         t.query(bgi::intersects(qbox), std::back_inserter(output));
1621         exactly_the_same_outputs(t, output, expected_output);
1622     }
1623 }
1624
1625 template <typename Rtree, typename Value>
1626 void range(Rtree & tree, std::vector<Value> const& input)
1627 {
1628     check_fwd_iterators(tree.begin(), tree.end());
1629
1630     size_t count = std::distance(tree.begin(), tree.end());
1631     BOOST_CHECK(count == tree.size());
1632     BOOST_CHECK(count == input.size());
1633
1634     count = std::distance(boost::begin(tree), boost::end(tree));
1635     BOOST_CHECK(count == tree.size());
1636
1637     count = boost::size(tree);
1638     BOOST_CHECK(count == tree.size());
1639
1640     count = 0;
1641     BOOST_FOREACH(Value const& v, tree)
1642     {
1643         boost::ignore_unused(v);
1644         ++count;
1645     }
1646     BOOST_CHECK(count == tree.size());
1647
1648 }
1649
1650 // rtree queries
1651
1652 template <typename Rtree, typename Value, typename Box>
1653 void queries(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1654 {
1655     basictest::intersects(tree, input, qbox);
1656     basictest::disjoint(tree, input, qbox);
1657     basictest::covered_by(tree, input, qbox);
1658     basictest::overlaps(tree, input, qbox);
1659     //basictest::touches(tree, input, qbox);
1660     basictest::within(tree, input, qbox);
1661     basictest::contains(tree, input, qbox);
1662     basictest::covers(tree, input, qbox);
1663
1664     typedef typename bg::point_type<Box>::type P;
1665     P pt;
1666     bg::centroid(qbox, pt);
1667
1668     basictest::nearest_query_k(tree, input, pt, 10);
1669     basictest::nearest_query_not_found(tree, generate::outside_point<P>::apply());
1670
1671     basictest::satisfies(tree, input);
1672 }
1673
1674 // rtree creation and modification
1675
1676 template <typename Rtree, typename Value, typename Box>
1677 void modifiers(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1678 {
1679     basictest::copy_swap_move(tree, qbox);
1680     basictest::create_insert(tree, input, qbox);
1681     basictest::remove(tree, qbox);
1682     basictest::clear(tree, input, qbox);
1683 }
1684
1685 } // namespace basictest
1686
1687 template <typename Value, typename Parameters, typename Allocator>
1688 void test_rtree_queries(Parameters const& parameters, Allocator const& allocator)
1689 {
1690     typedef bgi::indexable<Value> I;
1691     typedef bgi::equal_to<Value> E;
1692     typedef typename Allocator::template rebind<Value>::other A;
1693     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1694     typedef typename Tree::bounds_type B;
1695
1696     Tree tree(parameters, I(), E(), allocator);
1697     std::vector<Value> input;
1698     B qbox;
1699
1700     generate::rtree(tree, input, qbox);
1701
1702     basictest::queries(tree, input, qbox);
1703
1704     Tree empty_tree(parameters, I(), E(), allocator);
1705     std::vector<Value> empty_input;
1706
1707     basictest::queries(empty_tree, empty_input, qbox);
1708 }
1709
1710 template <typename Value, typename Parameters, typename Allocator>
1711 void test_rtree_modifiers(Parameters const& parameters, Allocator const& allocator)
1712 {
1713     typedef bgi::indexable<Value> I;
1714     typedef bgi::equal_to<Value> E;
1715     typedef typename Allocator::template rebind<Value>::other A;
1716     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1717     typedef typename Tree::bounds_type B;
1718
1719     Tree tree(parameters, I(), E(), allocator);
1720     std::vector<Value> input;
1721     B qbox;
1722
1723     generate::rtree(tree, input, qbox);
1724
1725     basictest::modifiers(tree, input, qbox);
1726
1727     Tree empty_tree(parameters, I(), E(), allocator);
1728     std::vector<Value> empty_input;
1729
1730     basictest::copy_swap_move(empty_tree, qbox);
1731 }
1732
1733 // run all tests for a single Algorithm and single rtree
1734 // defined by Value
1735
1736 template <typename Value, typename Parameters, typename Allocator>
1737 void test_rtree_by_value(Parameters const& parameters, Allocator const& allocator)
1738 {
1739     test_rtree_queries<Value>(parameters, allocator);
1740     test_rtree_modifiers<Value>(parameters, allocator);
1741 }
1742
1743 // rtree inserting and removing of counting_value
1744
1745 template <typename Indexable, typename Parameters, typename Allocator>
1746 void test_count_rtree_values(Parameters const& parameters, Allocator const& allocator)
1747 {
1748     typedef counting_value<Indexable> Value;
1749
1750     typedef bgi::indexable<Value> I;
1751     typedef bgi::equal_to<Value> E;
1752     typedef typename Allocator::template rebind<Value>::other A;
1753     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1754     typedef typename Tree::bounds_type B;
1755
1756     Tree t(parameters, I(), E(), allocator);
1757     std::vector<Value> input;
1758     B qbox;
1759
1760     generate::rtree(t, input, qbox);
1761
1762     size_t rest_count = input.size();
1763
1764     BOOST_CHECK(t.size() + rest_count == Value::counter());
1765
1766     std::vector<Value> values_to_remove;
1767     t.query(bgi::intersects(qbox), std::back_inserter(values_to_remove));
1768
1769     rest_count += values_to_remove.size();
1770
1771     BOOST_CHECK(t.size() + rest_count == Value::counter());
1772
1773     size_t values_count = Value::counter();
1774
1775     BOOST_FOREACH(Value const& v, values_to_remove)
1776     {
1777         size_t r = t.remove(v);
1778         --values_count;
1779
1780         BOOST_CHECK(1 == r);
1781         BOOST_CHECK(Value::counter() == values_count);
1782         BOOST_CHECK(t.size() + rest_count == values_count);
1783     }
1784 }
1785
1786 // rtree count
1787
1788 template <typename Indexable, typename Parameters, typename Allocator>
1789 void test_rtree_count(Parameters const& parameters, Allocator const& allocator)
1790 {
1791     typedef std::pair<Indexable, int> Value;
1792
1793     typedef bgi::indexable<Value> I;
1794     typedef bgi::equal_to<Value> E;
1795     typedef typename Allocator::template rebind<Value>::other A;
1796     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1797     typedef typename Tree::bounds_type B;
1798
1799     Tree t(parameters, I(), E(), allocator);
1800     std::vector<Value> input;
1801     B qbox;
1802
1803     generate::rtree(t, input, qbox);
1804
1805     BOOST_CHECK(t.count(input[0]) == 1);
1806     BOOST_CHECK(t.count(input[0].first) == 1);
1807
1808     t.insert(input[0]);
1809
1810     BOOST_CHECK(t.count(input[0]) == 2);
1811     BOOST_CHECK(t.count(input[0].first) == 2);
1812
1813     t.insert(std::make_pair(input[0].first, -1));
1814
1815     BOOST_CHECK(t.count(input[0]) == 2);
1816     BOOST_CHECK(t.count(input[0].first) == 3);
1817 }
1818
1819 // test rtree box
1820
1821 template <typename Value, typename Parameters, typename Allocator>
1822 void test_rtree_bounds(Parameters const& parameters, Allocator const& allocator)
1823 {
1824     typedef bgi::indexable<Value> I;
1825     typedef bgi::equal_to<Value> E;
1826     typedef typename Allocator::template rebind<Value>::other A;
1827     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1828     typedef typename Tree::bounds_type B;
1829     //typedef typename bg::traits::point_type<B>::type P;
1830
1831     Tree t(parameters, I(), E(), allocator);
1832     std::vector<Value> input;
1833     B qbox;
1834
1835     B b;
1836     bg::assign_inverse(b);
1837
1838     BOOST_CHECK(bg::equals(t.bounds(), b));
1839
1840     generate::rtree(t, input, qbox);
1841
1842     b = bgi::detail::rtree::values_box<B>(input.begin(), input.end(), t.indexable_get());
1843
1844     BOOST_CHECK(bg::equals(t.bounds(), b));
1845     BOOST_CHECK(bg::equals(t.bounds(), bgi::bounds(t)));
1846
1847     size_t s = input.size();
1848     while ( s/2 < input.size() && !input.empty() )
1849     {
1850         t.remove(input.back());
1851         input.pop_back();
1852     }
1853
1854     b = bgi::detail::rtree::values_box<B>(input.begin(), input.end(), t.indexable_get());
1855
1856     BOOST_CHECK(bg::equals(t.bounds(), b));
1857
1858     Tree t2(t);
1859     BOOST_CHECK(bg::equals(t2.bounds(), b));
1860     t2.clear();
1861     t2 = t;
1862     BOOST_CHECK(bg::equals(t2.bounds(), b));
1863     t2.clear();
1864     t2 = boost::move(t);
1865     BOOST_CHECK(bg::equals(t2.bounds(), b));
1866
1867     t.clear();
1868
1869     bg::assign_inverse(b);
1870     BOOST_CHECK(bg::equals(t.bounds(), b));
1871 }
1872
1873 // test rtree iterator
1874
1875 template <typename Indexable, typename Parameters, typename Allocator>
1876 void test_rtree_range(Parameters const& parameters, Allocator const& allocator)
1877 {
1878     typedef std::pair<Indexable, int> Value;
1879
1880     typedef bgi::indexable<Value> I;
1881     typedef bgi::equal_to<Value> E;
1882     typedef typename Allocator::template rebind<Value>::other A;
1883     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1884     typedef typename Tree::bounds_type B;
1885
1886     Tree t(parameters, I(), E(), allocator);
1887     std::vector<Value> input;
1888     B qbox;
1889
1890     generate::rtree(t, input, qbox);
1891
1892     basictest::range(t, input);
1893     basictest::range((Tree const&)t, input);
1894 }
1895
1896 template <typename Indexable, typename Parameters, typename Allocator>
1897 void test_rtree_additional(Parameters const& parameters, Allocator const& allocator)
1898 {
1899     test_count_rtree_values<Indexable>(parameters, allocator);
1900     test_rtree_count<Indexable>(parameters, allocator);
1901     test_rtree_bounds<Indexable>(parameters, allocator);
1902     test_rtree_range<Indexable>(parameters, allocator);
1903 }
1904
1905 // run all tests for one Algorithm for some number of rtrees
1906 // defined by some number of Values constructed from given Point
1907
1908 template<typename Point, typename Parameters, typename Allocator>
1909 void test_rtree_for_point(Parameters const& parameters, Allocator const& allocator)
1910 {
1911     typedef std::pair<Point, int> PairP;
1912     typedef boost::tuple<Point, int, int> TupleP;
1913     typedef boost::shared_ptr< test_object<Point> > SharedPtrP;
1914     typedef value_no_dctor<Point> VNoDCtor;
1915
1916     test_rtree_by_value<Point, Parameters>(parameters, allocator);
1917     test_rtree_by_value<PairP, Parameters>(parameters, allocator);
1918     test_rtree_by_value<TupleP, Parameters>(parameters, allocator);
1919
1920     test_rtree_by_value<SharedPtrP, Parameters>(parameters, allocator);
1921     test_rtree_by_value<VNoDCtor, Parameters>(parameters, allocator);
1922
1923     test_rtree_additional<Point>(parameters, allocator);
1924
1925 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1926     typedef std::tuple<Point, int, int> StdTupleP;
1927     test_rtree_by_value<StdTupleP, Parameters>(parameters, allocator);
1928 #endif
1929 }
1930
1931 template<typename Point, typename Parameters, typename Allocator>
1932 void test_rtree_for_box(Parameters const& parameters, Allocator const& allocator)
1933 {
1934     typedef bg::model::box<Point> Box;
1935     typedef std::pair<Box, int> PairB;
1936     typedef boost::tuple<Box, int, int> TupleB;
1937     typedef value_no_dctor<Box> VNoDCtor;
1938
1939     test_rtree_by_value<Box, Parameters>(parameters, allocator);
1940     test_rtree_by_value<PairB, Parameters>(parameters, allocator);
1941     test_rtree_by_value<TupleB, Parameters>(parameters, allocator);
1942
1943     test_rtree_by_value<VNoDCtor, Parameters>(parameters, allocator);
1944
1945     test_rtree_additional<Box>(parameters, allocator);
1946
1947 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1948     typedef std::tuple<Box, int, int> StdTupleB;
1949     test_rtree_by_value<StdTupleB, Parameters>(parameters, allocator);
1950 #endif
1951 }
1952
1953 template<typename Point, typename Parameters>
1954 void test_rtree_for_point(Parameters const& parameters)
1955 {
1956     test_rtree_for_point<Point>(parameters, std::allocator<int>());
1957 }
1958
1959 template<typename Point, typename Parameters>
1960 void test_rtree_for_box(Parameters const& parameters)
1961 {
1962     test_rtree_for_box<Point>(parameters, std::allocator<int>());
1963 }
1964
1965 namespace testset {
1966
1967 template<typename Indexable, typename Parameters, typename Allocator>
1968 void modifiers(Parameters const& parameters, Allocator const& allocator)
1969 {
1970     typedef std::pair<Indexable, int> Pair;
1971     typedef boost::tuple<Indexable, int, int> Tuple;
1972     typedef boost::shared_ptr< test_object<Indexable> > SharedPtr;
1973     typedef value_no_dctor<Indexable> VNoDCtor;
1974
1975     test_rtree_modifiers<Indexable>(parameters, allocator);
1976     test_rtree_modifiers<Pair>(parameters, allocator);
1977     test_rtree_modifiers<Tuple>(parameters, allocator);
1978
1979     test_rtree_modifiers<SharedPtr>(parameters, allocator);
1980     test_rtree_modifiers<VNoDCtor>(parameters, allocator);
1981
1982 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1983     typedef std::tuple<Indexable, int, int> StdTuple;
1984     test_rtree_modifiers<StdTuple>(parameters, allocator);
1985 #endif
1986 }
1987
1988 template<typename Indexable, typename Parameters, typename Allocator>
1989 void queries(Parameters const& parameters, Allocator const& allocator)
1990 {
1991     typedef std::pair<Indexable, int> Pair;
1992     typedef boost::tuple<Indexable, int, int> Tuple;
1993     typedef boost::shared_ptr< test_object<Indexable> > SharedPtr;
1994     typedef value_no_dctor<Indexable> VNoDCtor;
1995
1996     test_rtree_queries<Indexable>(parameters, allocator);
1997     test_rtree_queries<Pair>(parameters, allocator);
1998     test_rtree_queries<Tuple>(parameters, allocator);
1999
2000     test_rtree_queries<SharedPtr>(parameters, allocator);
2001     test_rtree_queries<VNoDCtor>(parameters, allocator);
2002
2003 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
2004     typedef std::tuple<Indexable, int, int> StdTuple;
2005     test_rtree_queries<StdTuple>(parameters, allocator);
2006 #endif
2007 }
2008
2009 template<typename Indexable, typename Parameters, typename Allocator>
2010 void additional(Parameters const& parameters, Allocator const& allocator)
2011 {
2012     test_rtree_additional<Indexable, Parameters>(parameters, allocator);
2013 }
2014
2015 } // namespace testset
2016
2017 #endif // BOOST_GEOMETRY_INDEX_TEST_RTREE_HPP