libs/geometry/index/test/rtree/test_rtree.hpp

   1 // Boost.Geometry Index
   2 // Unit Test
   3
   4 // Copyright (c) 2011-2014 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 // spatial query
 737
 738 template <typename Rtree, typename Value, typename Predicates>
 739 void spatial_query(Rtree & rtree, Predicates const& pred, std::vector<Value> const& expected_output)
 740 {
 741     BOOST_CHECK( bgi::detail::rtree::utilities::are_levels_ok(rtree) );
 742     if ( !rtree.empty() )
 743         BOOST_CHECK( bgi::detail::rtree::utilities::are_boxes_ok(rtree) );
 744
 745     std::vector<Value> output;
 746     size_t n = rtree.query(pred, std::back_inserter(output));
 747
 748     BOOST_CHECK( expected_output.size() == n );
 749     compare_outputs(rtree, output, expected_output);
 750
 751     std::vector<Value> output2;
 752     size_t n2 = query(rtree, pred, std::back_inserter(output2));
 753
 754     BOOST_CHECK( n == n2 );
 755     exactly_the_same_outputs(rtree, output, output2);
 756
 757     exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::queried(pred));
 758
 759     std::vector<Value> output3;
 760     std::copy(rtree.qbegin(pred), rtree.qend(), std::back_inserter(output3));
 761
 762     compare_outputs(rtree, output3, expected_output);
 763
 764     std::vector<Value> output4;
 765     std::copy(qbegin(rtree, pred), qend(rtree), std::back_inserter(output4));
 766
 767     exactly_the_same_outputs(rtree, output3, output4);
 768
 769 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
 770     {
 771         std::vector<Value> output4;
 772         std::copy(rtree.qbegin_(pred), rtree.qend_(pred), std::back_inserter(output4));
 773         compare_outputs(rtree, output4, expected_output);
 774         output4.clear();
 775         copy_alt(rtree.qbegin_(pred), rtree.qend_(), std::back_inserter(output4));
 776         compare_outputs(rtree, output4, expected_output);
 777     }
 778 #endif
 779 }
 780
 781 // rtree specific queries tests
 782
 783 template <typename Rtree, typename Value, typename Box>
 784 void intersects(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 785 {
 786     std::vector<Value> expected_output;
 787
 788     BOOST_FOREACH(Value const& v, input)
 789         if ( bg::intersects(tree.indexable_get()(v), qbox) )
 790             expected_output.push_back(v);
 791
 792     //spatial_query(tree, qbox, expected_output);
 793     spatial_query(tree, bgi::intersects(qbox), expected_output);
 794     spatial_query(tree, !bgi::disjoint(qbox), expected_output);
 795
 796     /*typedef bg::traits::point_type<Box>::type P;
 797     bg::model::ring<P> qring;
 798     bg::convert(qbox, qring);
 799     spatial_query(tree, bgi::intersects(qring), expected_output);
 800     spatial_query(tree, !bgi::disjoint(qring), expected_output);
 801     bg::model::polygon<P> qpoly;
 802     bg::convert(qbox, qpoly);
 803     spatial_query(tree, bgi::intersects(qpoly), expected_output);
 804     spatial_query(tree, !bgi::disjoint(qpoly), expected_output);*/
 805 }
 806
 807 template <typename Rtree, typename Value, typename Box>
 808 void disjoint(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 809 {
 810     std::vector<Value> expected_output;
 811
 812     BOOST_FOREACH(Value const& v, input)
 813         if ( bg::disjoint(tree.indexable_get()(v), qbox) )
 814             expected_output.push_back(v);
 815
 816     spatial_query(tree, bgi::disjoint(qbox), expected_output);
 817     spatial_query(tree, !bgi::intersects(qbox), expected_output);
 818
 819     /*typedef bg::traits::point_type<Box>::type P;
 820     bg::model::ring<P> qring;
 821     bg::convert(qbox, qring);
 822     spatial_query(tree, bgi::disjoint(qring), expected_output);
 823     bg::model::polygon<P> qpoly;
 824     bg::convert(qbox, qpoly);
 825     spatial_query(tree, bgi::disjoint(qpoly), expected_output);*/
 826 }
 827
 828 template <typename Tag>
 829 struct contains_impl
 830 {
 831     template <typename Rtree, typename Value, typename Box>
 832     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 833     {
 834         std::vector<Value> expected_output;
 835
 836         BOOST_FOREACH(Value const& v, input)
 837             if ( bg::within(qbox, tree.indexable_get()(v)) )
 838                 expected_output.push_back(v);
 839
 840         spatial_query(tree, bgi::contains(qbox), expected_output);
 841
 842         /*typedef bg::traits::point_type<Box>::type P;
 843         bg::model::ring<P> qring;
 844         bg::convert(qbox, qring);
 845         spatial_query(tree, bgi::contains(qring), expected_output);
 846         bg::model::polygon<P> qpoly;
 847         bg::convert(qbox, qpoly);
 848         spatial_query(tree, bgi::contains(qpoly), expected_output);*/
 849     }
 850 };
 851
 852 template <>
 853 struct contains_impl<bg::point_tag>
 854 {
 855     template <typename Rtree, typename Value, typename Box>
 856     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 857     {}
 858 };
 859
 860 template <>
 861 struct contains_impl<bg::segment_tag>
 862 {
 863     template <typename Rtree, typename Value, typename Box>
 864     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 865     {}
 866 };
 867
 868 template <typename Rtree, typename Value, typename Box>
 869 void contains(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 870 {
 871     contains_impl<
 872         typename bg::tag<
 873             typename Rtree::indexable_type
 874         >::type
 875     >::apply(tree, input, qbox);
 876 }
 877
 878 template <typename Tag>
 879 struct covered_by_impl
 880 {
 881     template <typename Rtree, typename Value, typename Box>
 882     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 883     {
 884         std::vector<Value> expected_output;
 885
 886         BOOST_FOREACH(Value const& v, input)
 887         {
 888             if ( bg::covered_by(
 889                     bgi::detail::return_ref_or_bounds(
 890                         tree.indexable_get()(v)),
 891                     qbox) )
 892             {
 893                 expected_output.push_back(v);
 894             }
 895         }
 896
 897         spatial_query(tree, bgi::covered_by(qbox), expected_output);
 898
 899         /*typedef bg::traits::point_type<Box>::type P;
 900         bg::model::ring<P> qring;
 901         bg::convert(qbox, qring);
 902         spatial_query(tree, bgi::covered_by(qring), expected_output);
 903         bg::model::polygon<P> qpoly;
 904         bg::convert(qbox, qpoly);
 905         spatial_query(tree, bgi::covered_by(qpoly), expected_output);*/
 906     }
 907 };
 908
 909 template <>
 910 struct covered_by_impl<bg::segment_tag>
 911 {
 912     template <typename Rtree, typename Value, typename Box>
 913     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 914     {}
 915 };
 916
 917 template <typename Rtree, typename Value, typename Box>
 918 void covered_by(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 919 {
 920     covered_by_impl<
 921         typename bg::tag<
 922             typename Rtree::indexable_type
 923         >::type
 924     >::apply(tree, input, qbox);
 925 }
 926
 927 template <typename Tag>
 928 struct covers_impl
 929 {
 930     template <typename Rtree, typename Value, typename Box>
 931     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 932     {
 933         std::vector<Value> expected_output;
 934
 935         BOOST_FOREACH(Value const& v, input)
 936             if ( bg::covered_by(qbox, tree.indexable_get()(v)) )
 937                 expected_output.push_back(v);
 938
 939         spatial_query(tree, bgi::covers(qbox), expected_output);
 940
 941         /*typedef bg::traits::point_type<Box>::type P;
 942         bg::model::ring<P> qring;
 943         bg::convert(qbox, qring);
 944         spatial_query(tree, bgi::covers(qring), expected_output);
 945         bg::model::polygon<P> qpoly;
 946         bg::convert(qbox, qpoly);
 947         spatial_query(tree, bgi::covers(qpoly), expected_output);*/
 948     }
 949 };
 950
 951 template <>
 952 struct covers_impl<bg::point_tag>
 953 {
 954     template <typename Rtree, typename Value, typename Box>
 955     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 956     {}
 957 };
 958
 959 template <>
 960 struct covers_impl<bg::segment_tag>
 961 {
 962     template <typename Rtree, typename Value, typename Box>
 963     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
 964     {}
 965 };
 966
 967 template <typename Rtree, typename Value, typename Box>
 968 void covers(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 969 {
 970     covers_impl<
 971         typename bg::tag<
 972             typename Rtree::indexable_type
 973         >::type
 974     >::apply(tree, input, qbox);
 975 }
 976
 977 template <typename Tag>
 978 struct overlaps_impl
 979 {
 980     template <typename Rtree, typename Value, typename Box>
 981     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
 982     {
 983         std::vector<Value> expected_output;
 984
 985         BOOST_FOREACH(Value const& v, input)
 986             if ( bg::overlaps(tree.indexable_get()(v), qbox) )
 987                 expected_output.push_back(v);
 988
 989         spatial_query(tree, bgi::overlaps(qbox), expected_output);
 990
 991         /*typedef bg::traits::point_type<Box>::type P;
 992         bg::model::ring<P> qring;
 993         bg::convert(qbox, qring);
 994         spatial_query(tree, bgi::overlaps(qring), expected_output);
 995         bg::model::polygon<P> qpoly;
 996         bg::convert(qbox, qpoly);
 997         spatial_query(tree, bgi::overlaps(qpoly), expected_output);*/
 998     }
 999 };
1000
1001 template <>
1002 struct overlaps_impl<bg::point_tag>
1003 {
1004     template <typename Rtree, typename Value, typename Box>
1005     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1006     {}
1007 };
1008
1009 template <>
1010 struct overlaps_impl<bg::segment_tag>
1011 {
1012     template <typename Rtree, typename Value, typename Box>
1013     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1014     {}
1015 };
1016
1017 template <typename Rtree, typename Value, typename Box>
1018 void overlaps(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1019 {
1020     overlaps_impl<
1021         typename bg::tag<
1022             typename Rtree::indexable_type
1023         >::type
1024     >::apply(tree, input, qbox);
1025 }
1026
1027 //template <typename Tag, size_t Dimension>
1028 //struct touches_impl
1029 //{
1030 //    template <typename Rtree, typename Value, typename Box>
1031 //    static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1032 //    {}
1033 //};
1034 //
1035 //template <>
1036 //struct touches_impl<bg::box_tag, 2>
1037 //{
1038 //    template <typename Rtree, typename Value, typename Box>
1039 //    static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1040 //    {
1041 //        std::vector<Value> expected_output;
1042 //
1043 //        BOOST_FOREACH(Value const& v, input)
1044 //            if ( bg::touches(tree.translator()(v), qbox) )
1045 //                expected_output.push_back(v);
1046 //
1047 //        spatial_query(tree, bgi::touches(qbox), expected_output);
1048 //    }
1049 //};
1050 //
1051 //template <typename Rtree, typename Value, typename Box>
1052 //void touches(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1053 //{
1054 //    touches_impl<
1055 //        bgi::traits::tag<typename Rtree::indexable_type>::type,
1056 //        bgi::traits::dimension<typename Rtree::indexable_type>::value
1057 //    >::apply(tree, input, qbox);
1058 //}
1059
1060 template <typename Tag>
1061 struct within_impl
1062 {
1063     template <typename Rtree, typename Value, typename Box>
1064     static void apply(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1065     {
1066         std::vector<Value> expected_output;
1067
1068         BOOST_FOREACH(Value const& v, input)
1069             if ( bg::within(tree.indexable_get()(v), qbox) )
1070                 expected_output.push_back(v);
1071
1072         spatial_query(tree, bgi::within(qbox), expected_output);
1073
1074         /*typedef bg::traits::point_type<Box>::type P;
1075         bg::model::ring<P> qring;
1076         bg::convert(qbox, qring);
1077         spatial_query(tree, bgi::within(qring), expected_output);
1078         bg::model::polygon<P> qpoly;
1079         bg::convert(qbox, qpoly);
1080         spatial_query(tree, bgi::within(qpoly), expected_output);*/
1081     }
1082 };
1083
1084 template <>
1085 struct within_impl<bg::segment_tag>
1086 {
1087     template <typename Rtree, typename Value, typename Box>
1088     static void apply(Rtree const& /*tree*/, std::vector<Value> const& /*input*/, Box const& /*qbox*/)
1089     {}
1090 };
1091
1092 template <typename Rtree, typename Value, typename Box>
1093 void within(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1094 {
1095     within_impl<
1096         typename bg::tag<
1097             typename Rtree::indexable_type
1098         >::type
1099     >::apply(tree, input, qbox);
1100 }
1101
1102 // rtree nearest queries
1103
1104 template <typename Rtree, typename Point>
1105 struct NearestKLess
1106 {
1107     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1108
1109     template <typename Value>
1110     bool operator()(std::pair<D, Value> const& p1, std::pair<D, Value> const& p2) const
1111     {
1112         return p1.first < p2.first;
1113     }
1114 };
1115
1116 template <typename Rtree, typename Point>
1117 struct NearestKTransform
1118 {
1119     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1120
1121     template <typename Value>
1122     Value const& operator()(std::pair<D, Value> const& p) const
1123     {
1124         return p.second;
1125     }
1126 };
1127
1128 template <typename Rtree, typename Value, typename Point, typename Distance>
1129 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)
1130 {
1131     // check output
1132     bool are_sizes_ok = (expected_output.size() == output.size());
1133     BOOST_CHECK( are_sizes_ok );
1134     if ( are_sizes_ok )
1135     {
1136         BOOST_FOREACH(Value const& v, output)
1137         {
1138             // TODO - perform explicit check here?
1139             // should all objects which are closest be checked and should exactly the same be found?
1140
1141             if ( find(rtree, expected_output.begin(), expected_output.end(), v) == expected_output.end() )
1142             {
1143                 Distance d = bg::comparable_distance(pt, rtree.indexable_get()(v));
1144                 BOOST_CHECK(d == greatest_distance);
1145             }
1146         }
1147     }
1148 }
1149
1150 template <typename Rtree, typename Value, typename Point>
1151 inline void check_sorted_by_distance(Rtree const& rtree, std::vector<Value> const& output, Point const& pt)
1152 {
1153     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1154
1155     D prev_dist = 0;
1156     BOOST_FOREACH(Value const& v, output)
1157     {
1158         D d = bg::comparable_distance(pt, rtree.indexable_get()(v));
1159         BOOST_CHECK(prev_dist <= d);
1160         prev_dist = d;
1161     }
1162 }
1163
1164 template <typename Rtree, typename Value, typename Point>
1165 inline void nearest_query_k(Rtree const& rtree, std::vector<Value> const& input, Point const& pt, unsigned int k)
1166 {
1167     // TODO: Nearest object may not be the same as found by the rtree if distances are equal
1168     // All objects with the same closest distance should be picked
1169
1170     typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
1171
1172     std::vector< std::pair<D, Value> > test_output;
1173
1174     // calculate test output - k closest values pairs
1175     BOOST_FOREACH(Value const& v, input)
1176     {
1177         D d = bg::comparable_distance(pt, rtree.indexable_get()(v));
1178
1179         if ( test_output.size() < k )
1180             test_output.push_back(std::make_pair(d, v));
1181         else
1182         {
1183             std::sort(test_output.begin(), test_output.end(), NearestKLess<Rtree, Point>());
1184             if ( d < test_output.back().first )
1185                 test_output.back() = std::make_pair(d, v);
1186         }
1187     }
1188
1189     // caluclate biggest distance
1190     std::sort(test_output.begin(), test_output.end(), NearestKLess<Rtree, Point>());
1191     D greatest_distance = 0;
1192     if ( !test_output.empty() )
1193         greatest_distance = test_output.back().first;
1194
1195     // transform test output to vector of values
1196     std::vector<Value> expected_output(test_output.size(), generate::value_default<Value>::apply());
1197     std::transform(test_output.begin(), test_output.end(), expected_output.begin(), NearestKTransform<Rtree, Point>());
1198
1199     // calculate output using rtree
1200     std::vector<Value> output;
1201     rtree.query(bgi::nearest(pt, k), std::back_inserter(output));
1202
1203     // check output
1204     compare_nearest_outputs(rtree, output, expected_output, pt, greatest_distance);
1205
1206     exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::queried(bgi::nearest(pt, k)));
1207
1208     std::vector<Value> output2(k, generate::value_default<Value>::apply());
1209     typename Rtree::size_type found_count = rtree.query(bgi::nearest(pt, k), output2.begin());
1210     output2.resize(found_count, generate::value_default<Value>::apply());
1211
1212     exactly_the_same_outputs(rtree, output, output2);
1213
1214     std::vector<Value> output3;
1215     std::copy(rtree.qbegin(bgi::nearest(pt, k)), rtree.qend(), std::back_inserter(output3));
1216
1217     compare_nearest_outputs(rtree, output3, expected_output, pt, greatest_distance);
1218     check_sorted_by_distance(rtree, output3, pt);
1219
1220 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
1221     {
1222         std::vector<Value> output4;
1223         std::copy(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(bgi::nearest(pt, k)), std::back_inserter(output4));
1224         exactly_the_same_outputs(rtree, output4, output3);
1225         output4.clear();
1226         copy_alt(rtree.qbegin_(bgi::nearest(pt, k)), rtree.qend_(), std::back_inserter(output4));
1227         exactly_the_same_outputs(rtree, output4, output3);
1228     }
1229 #endif
1230 }
1231
1232 // rtree nearest not found
1233
1234 struct AlwaysFalse
1235 {
1236     template <typename Value>
1237     bool operator()(Value const& ) const { return false; }
1238 };
1239
1240 template <typename Rtree, typename Point>
1241 void nearest_query_not_found(Rtree const& rtree, Point const& pt)
1242 {
1243     typedef typename Rtree::value_type Value;
1244
1245     std::vector<Value> output_v;
1246     size_t n_res = rtree.query(bgi::nearest(pt, 5) && bgi::satisfies(AlwaysFalse()), std::back_inserter(output_v));
1247     BOOST_CHECK(output_v.size() == n_res);
1248     BOOST_CHECK(n_res < 5);
1249 }
1250
1251 template <typename Value>
1252 bool satisfies_fun(Value const& ) { return true; }
1253
1254 struct satisfies_obj
1255 {
1256     template <typename Value>
1257     bool operator()(Value const& ) const { return true; }
1258 };
1259
1260 template <typename Rtree, typename Value>
1261 void satisfies(Rtree const& rtree, std::vector<Value> const& input)
1262 {
1263     std::vector<Value> result;
1264     rtree.query(bgi::satisfies(satisfies_obj()), std::back_inserter(result));
1265     BOOST_CHECK(result.size() == input.size());
1266     result.clear();
1267     rtree.query(!bgi::satisfies(satisfies_obj()), std::back_inserter(result));
1268     BOOST_CHECK(result.size() == 0);
1269
1270     result.clear();
1271     rtree.query(bgi::satisfies(satisfies_fun<Value>), std::back_inserter(result));
1272     BOOST_CHECK(result.size() == input.size());
1273     result.clear();
1274     rtree.query(!bgi::satisfies(satisfies_fun<Value>), std::back_inserter(result));
1275     BOOST_CHECK(result.size() == 0);
1276
1277 #ifndef BOOST_NO_CXX11_LAMBDAS
1278     result.clear();
1279     rtree.query(bgi::satisfies([](Value const&){ return true; }), std::back_inserter(result));
1280     BOOST_CHECK(result.size() == input.size());
1281     result.clear();
1282     rtree.query(!bgi::satisfies([](Value const&){ return true; }), std::back_inserter(result));
1283     BOOST_CHECK(result.size() == 0);
1284 #endif
1285 }
1286
1287 // rtree copying and moving
1288
1289 template <typename Rtree, typename Box>
1290 void copy_swap_move(Rtree const& tree, Box const& qbox)
1291 {
1292     typedef typename Rtree::value_type Value;
1293     typedef typename Rtree::parameters_type Params;
1294
1295     size_t s = tree.size();
1296     Params params = tree.parameters();
1297
1298     std::vector<Value> expected_output;
1299     tree.query(bgi::intersects(qbox), std::back_inserter(expected_output));
1300
1301     // copy constructor
1302     Rtree t1(tree);
1303
1304     BOOST_CHECK(tree.empty() == t1.empty());
1305     BOOST_CHECK(tree.size() == t1.size());
1306     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1307     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1308
1309     std::vector<Value> output;
1310     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1311     exactly_the_same_outputs(t1, output, expected_output);
1312
1313     // copying assignment operator
1314     t1 = tree;
1315
1316     BOOST_CHECK(tree.empty() == t1.empty());
1317     BOOST_CHECK(tree.size() == t1.size());
1318     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1319     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1320
1321     output.clear();
1322     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1323     exactly_the_same_outputs(t1, output, expected_output);
1324
1325     Rtree t2(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1326     t2.swap(t1);
1327     BOOST_CHECK(tree.empty() == t2.empty());
1328     BOOST_CHECK(tree.size() == t2.size());
1329     BOOST_CHECK(true == t1.empty());
1330     BOOST_CHECK(0 == t1.size());
1331     // those fails e.g. on darwin 4.2.1 because it can't copy base obejcts properly
1332     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1333     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1334     BOOST_CHECK(t2.parameters().get_max_elements() == params.get_max_elements());
1335     BOOST_CHECK(t2.parameters().get_min_elements() == params.get_min_elements());
1336
1337     output.clear();
1338     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1339     BOOST_CHECK(output.empty());
1340
1341     output.clear();
1342     t2.query(bgi::intersects(qbox), std::back_inserter(output));
1343     exactly_the_same_outputs(t2, output, expected_output);
1344     t2.swap(t1);
1345     // those fails e.g. on darwin 4.2.1 because it can't copy base obejcts properly
1346     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1347     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1348     BOOST_CHECK(t2.parameters().get_max_elements() == params.get_max_elements());
1349     BOOST_CHECK(t2.parameters().get_min_elements() == params.get_min_elements());
1350
1351     // moving constructor
1352     Rtree t3(boost::move(t1), tree.get_allocator());
1353
1354     BOOST_CHECK(t3.size() == s);
1355     BOOST_CHECK(t1.size() == 0);
1356     BOOST_CHECK(t3.parameters().get_max_elements() == params.get_max_elements());
1357     BOOST_CHECK(t3.parameters().get_min_elements() == params.get_min_elements());
1358
1359     output.clear();
1360     t3.query(bgi::intersects(qbox), std::back_inserter(output));
1361     exactly_the_same_outputs(t3, output, expected_output);
1362
1363     // moving assignment operator
1364     t1 = boost::move(t3);
1365
1366     BOOST_CHECK(t1.size() == s);
1367     BOOST_CHECK(t3.size() == 0);
1368     BOOST_CHECK(t1.parameters().get_max_elements() == params.get_max_elements());
1369     BOOST_CHECK(t1.parameters().get_min_elements() == params.get_min_elements());
1370
1371     output.clear();
1372     t1.query(bgi::intersects(qbox), std::back_inserter(output));
1373     exactly_the_same_outputs(t1, output, expected_output);
1374
1375     //TODO - test SWAP
1376
1377     ::boost::ignore_unused_variable_warning(params);
1378 }
1379
1380 template <typename I, typename O>
1381 inline void my_copy(I first, I last, O out)
1382 {
1383     for ( ; first != last ; ++first, ++out )
1384         *out = *first;
1385 }
1386
1387 // rtree creation and insertion
1388
1389 template <typename Rtree, typename Value, typename Box>
1390 void create_insert(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1391 {
1392     std::vector<Value> expected_output;
1393     tree.query(bgi::intersects(qbox), std::back_inserter(expected_output));
1394
1395     {
1396         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1397         BOOST_FOREACH(Value const& v, input)
1398             t.insert(v);
1399         BOOST_CHECK(tree.size() == t.size());
1400         std::vector<Value> output;
1401         t.query(bgi::intersects(qbox), std::back_inserter(output));
1402         exactly_the_same_outputs(t, output, expected_output);
1403     }
1404     {
1405         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1406         //std::copy(input.begin(), input.end(), bgi::inserter(t));
1407         my_copy(input.begin(), input.end(), bgi::inserter(t)); // to suppress MSVC warnings
1408         BOOST_CHECK(tree.size() == t.size());
1409         std::vector<Value> output;
1410         t.query(bgi::intersects(qbox), std::back_inserter(output));
1411         exactly_the_same_outputs(t, output, expected_output);
1412     }
1413     {
1414         Rtree t(input.begin(), input.end(), tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1415         BOOST_CHECK(tree.size() == t.size());
1416         std::vector<Value> output;
1417         t.query(bgi::intersects(qbox), std::back_inserter(output));
1418         compare_outputs(t, output, expected_output);
1419     }
1420     {
1421         Rtree t(input, tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1422         BOOST_CHECK(tree.size() == t.size());
1423         std::vector<Value> output;
1424         t.query(bgi::intersects(qbox), std::back_inserter(output));
1425         compare_outputs(t, output, expected_output);
1426     }
1427     {
1428         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1429         t.insert(input.begin(), input.end());
1430         BOOST_CHECK(tree.size() == t.size());
1431         std::vector<Value> output;
1432         t.query(bgi::intersects(qbox), std::back_inserter(output));
1433         exactly_the_same_outputs(t, output, expected_output);
1434     }
1435     {
1436         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1437         t.insert(input);
1438         BOOST_CHECK(tree.size() == t.size());
1439         std::vector<Value> output;
1440         t.query(bgi::intersects(qbox), std::back_inserter(output));
1441         exactly_the_same_outputs(t, output, expected_output);
1442     }
1443
1444     {
1445         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1446         BOOST_FOREACH(Value const& v, input)
1447             bgi::insert(t, v);
1448         BOOST_CHECK(tree.size() == t.size());
1449         std::vector<Value> output;
1450         bgi::query(t, bgi::intersects(qbox), std::back_inserter(output));
1451         exactly_the_same_outputs(t, output, expected_output);
1452     }
1453     {
1454         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1455         bgi::insert(t, input.begin(), input.end());
1456         BOOST_CHECK(tree.size() == t.size());
1457         std::vector<Value> output;
1458         bgi::query(t, bgi::intersects(qbox), std::back_inserter(output));
1459         exactly_the_same_outputs(t, output, expected_output);
1460     }
1461     {
1462         Rtree t(tree.parameters(), tree.indexable_get(), tree.value_eq(), tree.get_allocator());
1463         bgi::insert(t, input);
1464         BOOST_CHECK(tree.size() == t.size());
1465         std::vector<Value> output;
1466         bgi::query(t, bgi::intersects(qbox), std::back_inserter(output));
1467         exactly_the_same_outputs(t, output, expected_output);
1468     }
1469 }
1470
1471 // rtree removing
1472
1473 template <typename Rtree, typename Box>
1474 void remove(Rtree const& tree, Box const& qbox)
1475 {
1476     typedef typename Rtree::value_type Value;
1477
1478     std::vector<Value> values_to_remove;
1479     tree.query(bgi::intersects(qbox), std::back_inserter(values_to_remove));
1480     BOOST_CHECK(0 < values_to_remove.size());
1481
1482     std::vector<Value> expected_output;
1483     tree.query(bgi::disjoint(qbox), std::back_inserter(expected_output));
1484     size_t expected_removed_count = values_to_remove.size();
1485     size_t expected_size_after_remove = tree.size() - values_to_remove.size();
1486
1487     // Add value which is not stored in the Rtree
1488     Value outsider = generate::value_outside<Rtree>();
1489     values_to_remove.push_back(outsider);
1490
1491     {
1492         Rtree t(tree);
1493         size_t r = 0;
1494         BOOST_FOREACH(Value const& v, values_to_remove)
1495             r += t.remove(v);
1496         BOOST_CHECK( r == expected_removed_count );
1497         std::vector<Value> output;
1498         t.query(bgi::disjoint(qbox), std::back_inserter(output));
1499         BOOST_CHECK( t.size() == expected_size_after_remove );
1500         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1501         compare_outputs(t, output, expected_output);
1502     }
1503     {
1504         Rtree t(tree);
1505         size_t r = t.remove(values_to_remove.begin(), values_to_remove.end());
1506         BOOST_CHECK( r == expected_removed_count );
1507         std::vector<Value> output;
1508         t.query(bgi::disjoint(qbox), std::back_inserter(output));
1509         BOOST_CHECK( t.size() == expected_size_after_remove );
1510         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1511         compare_outputs(t, output, expected_output);
1512     }
1513     {
1514         Rtree t(tree);
1515         size_t r = t.remove(values_to_remove);
1516         BOOST_CHECK( r == expected_removed_count );
1517         std::vector<Value> output;
1518         t.query(bgi::disjoint(qbox), std::back_inserter(output));
1519         BOOST_CHECK( t.size() == expected_size_after_remove );
1520         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1521         compare_outputs(t, output, expected_output);
1522     }
1523
1524     {
1525         Rtree t(tree);
1526         size_t r = 0;
1527         BOOST_FOREACH(Value const& v, values_to_remove)
1528             r += bgi::remove(t, v);
1529         BOOST_CHECK( r == expected_removed_count );
1530         std::vector<Value> output;
1531         bgi::query(t, bgi::disjoint(qbox), std::back_inserter(output));
1532         BOOST_CHECK( t.size() == expected_size_after_remove );
1533         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1534         compare_outputs(t, output, expected_output);
1535     }
1536     {
1537         Rtree t(tree);
1538         size_t r = bgi::remove(t, values_to_remove.begin(), values_to_remove.end());
1539         BOOST_CHECK( r == expected_removed_count );
1540         std::vector<Value> output;
1541         bgi::query(t, bgi::disjoint(qbox), std::back_inserter(output));
1542         BOOST_CHECK( t.size() == expected_size_after_remove );
1543         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1544         compare_outputs(t, output, expected_output);
1545     }
1546     {
1547         Rtree t(tree);
1548         size_t r = bgi::remove(t, values_to_remove);
1549         BOOST_CHECK( r == expected_removed_count );
1550         std::vector<Value> output;
1551         bgi::query(t, bgi::disjoint(qbox), std::back_inserter(output));
1552         BOOST_CHECK( t.size() == expected_size_after_remove );
1553         BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
1554         compare_outputs(t, output, expected_output);
1555     }
1556 }
1557
1558 template <typename Rtree, typename Value, typename Box>
1559 void clear(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1560 {
1561     std::vector<Value> values_to_remove;
1562     tree.query(bgi::intersects(qbox), std::back_inserter(values_to_remove));
1563     BOOST_CHECK(0 < values_to_remove.size());
1564
1565     //clear
1566     {
1567         Rtree t(tree);
1568
1569         std::vector<Value> expected_output;
1570         t.query(bgi::intersects(qbox), std::back_inserter(expected_output));
1571         size_t s = t.size();
1572         t.clear();
1573         BOOST_CHECK(t.empty());
1574         BOOST_CHECK(t.size() == 0);
1575         t.insert(input);
1576         BOOST_CHECK(t.size() == s);
1577         std::vector<Value> output;
1578         t.query(bgi::intersects(qbox), std::back_inserter(output));
1579         exactly_the_same_outputs(t, output, expected_output);
1580     }
1581 }
1582
1583 // rtree queries
1584
1585 template <typename Rtree, typename Value, typename Box>
1586 void queries(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1587 {
1588     basictest::intersects(tree, input, qbox);
1589     basictest::disjoint(tree, input, qbox);
1590     basictest::covered_by(tree, input, qbox);
1591     basictest::overlaps(tree, input, qbox);
1592     //basictest::touches(tree, input, qbox);
1593     basictest::within(tree, input, qbox);
1594     basictest::contains(tree, input, qbox);
1595     basictest::covers(tree, input, qbox);
1596
1597     typedef typename bg::point_type<Box>::type P;
1598     P pt;
1599     bg::centroid(qbox, pt);
1600
1601     basictest::nearest_query_k(tree, input, pt, 10);
1602     basictest::nearest_query_not_found(tree, generate::outside_point<P>::apply());
1603
1604     basictest::satisfies(tree, input);
1605 }
1606
1607 // rtree creation and modification
1608
1609 template <typename Rtree, typename Value, typename Box>
1610 void modifiers(Rtree const& tree, std::vector<Value> const& input, Box const& qbox)
1611 {
1612     basictest::copy_swap_move(tree, qbox);
1613     basictest::create_insert(tree, input, qbox);
1614     basictest::remove(tree, qbox);
1615     basictest::clear(tree, input, qbox);
1616 }
1617
1618 } // namespace basictest
1619
1620 template <typename Value, typename Parameters, typename Allocator>
1621 void test_rtree_queries(Parameters const& parameters, Allocator const& allocator)
1622 {
1623     typedef bgi::indexable<Value> I;
1624     typedef bgi::equal_to<Value> E;
1625     typedef typename Allocator::template rebind<Value>::other A;
1626     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1627     typedef typename Tree::bounds_type B;
1628
1629     Tree tree(parameters, I(), E(), allocator);
1630     std::vector<Value> input;
1631     B qbox;
1632
1633     generate::rtree(tree, input, qbox);
1634
1635     basictest::queries(tree, input, qbox);
1636
1637     Tree empty_tree(parameters, I(), E(), allocator);
1638     std::vector<Value> empty_input;
1639
1640     basictest::queries(empty_tree, empty_input, qbox);
1641 }
1642
1643 template <typename Value, typename Parameters, typename Allocator>
1644 void test_rtree_modifiers(Parameters const& parameters, Allocator const& allocator)
1645 {
1646     typedef bgi::indexable<Value> I;
1647     typedef bgi::equal_to<Value> E;
1648     typedef typename Allocator::template rebind<Value>::other A;
1649     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1650     typedef typename Tree::bounds_type B;
1651
1652     Tree tree(parameters, I(), E(), allocator);
1653     std::vector<Value> input;
1654     B qbox;
1655
1656     generate::rtree(tree, input, qbox);
1657
1658     basictest::modifiers(tree, input, qbox);
1659
1660     Tree empty_tree(parameters, I(), E(), allocator);
1661     std::vector<Value> empty_input;
1662
1663     basictest::copy_swap_move(empty_tree, qbox);
1664 }
1665
1666 // run all tests for a single Algorithm and single rtree
1667 // defined by Value
1668
1669 template <typename Value, typename Parameters, typename Allocator>
1670 void test_rtree_by_value(Parameters const& parameters, Allocator const& allocator)
1671 {
1672     test_rtree_queries<Value>(parameters, allocator);
1673     test_rtree_modifiers<Value>(parameters, allocator);
1674 }
1675
1676 // rtree inserting and removing of counting_value
1677
1678 template <typename Indexable, typename Parameters, typename Allocator>
1679 void test_count_rtree_values(Parameters const& parameters, Allocator const& allocator)
1680 {
1681     typedef counting_value<Indexable> Value;
1682
1683     typedef bgi::indexable<Value> I;
1684     typedef bgi::equal_to<Value> E;
1685     typedef typename Allocator::template rebind<Value>::other A;
1686     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1687     typedef typename Tree::bounds_type B;
1688
1689     Tree t(parameters, I(), E(), allocator);
1690     std::vector<Value> input;
1691     B qbox;
1692
1693     generate::rtree(t, input, qbox);
1694
1695     size_t rest_count = input.size();
1696
1697     BOOST_CHECK(t.size() + rest_count == Value::counter());
1698
1699     std::vector<Value> values_to_remove;
1700     t.query(bgi::intersects(qbox), std::back_inserter(values_to_remove));
1701
1702     rest_count += values_to_remove.size();
1703
1704     BOOST_CHECK(t.size() + rest_count == Value::counter());
1705
1706     size_t values_count = Value::counter();
1707
1708     BOOST_FOREACH(Value const& v, values_to_remove)
1709     {
1710         size_t r = t.remove(v);
1711         --values_count;
1712
1713         BOOST_CHECK(1 == r);
1714         BOOST_CHECK(Value::counter() == values_count);
1715         BOOST_CHECK(t.size() + rest_count == values_count);
1716     }
1717 }
1718
1719 // rtree count
1720
1721 template <typename Indexable, typename Parameters, typename Allocator>
1722 void test_rtree_count(Parameters const& parameters, Allocator const& allocator)
1723 {
1724     typedef std::pair<Indexable, int> Value;
1725
1726     typedef bgi::indexable<Value> I;
1727     typedef bgi::equal_to<Value> E;
1728     typedef typename Allocator::template rebind<Value>::other A;
1729     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1730     typedef typename Tree::bounds_type B;
1731
1732     Tree t(parameters, I(), E(), allocator);
1733     std::vector<Value> input;
1734     B qbox;
1735
1736     generate::rtree(t, input, qbox);
1737
1738     BOOST_CHECK(t.count(input[0]) == 1);
1739     BOOST_CHECK(t.count(input[0].first) == 1);
1740
1741     t.insert(input[0]);
1742
1743     BOOST_CHECK(t.count(input[0]) == 2);
1744     BOOST_CHECK(t.count(input[0].first) == 2);
1745
1746     t.insert(std::make_pair(input[0].first, -1));
1747
1748     BOOST_CHECK(t.count(input[0]) == 2);
1749     BOOST_CHECK(t.count(input[0].first) == 3);
1750 }
1751
1752 // test rtree box
1753
1754 template <typename Value, typename Parameters, typename Allocator>
1755 void test_rtree_bounds(Parameters const& parameters, Allocator const& allocator)
1756 {
1757     typedef bgi::indexable<Value> I;
1758     typedef bgi::equal_to<Value> E;
1759     typedef typename Allocator::template rebind<Value>::other A;
1760     typedef bgi::rtree<Value, Parameters, I, E, A> Tree;
1761     typedef typename Tree::bounds_type B;
1762     //typedef typename bg::traits::point_type<B>::type P;
1763
1764     B b;
1765     bg::assign_inverse(b);
1766
1767     Tree t(parameters, I(), E(), allocator);
1768     std::vector<Value> input;
1769     B qbox;
1770
1771     BOOST_CHECK(bg::equals(t.bounds(), b));
1772
1773     generate::rtree(t, input, qbox);
1774
1775     BOOST_FOREACH(Value const& v, input)
1776         bg::expand(b, t.indexable_get()(v));
1777
1778     BOOST_CHECK(bg::equals(t.bounds(), b));
1779     BOOST_CHECK(bg::equals(t.bounds(), bgi::bounds(t)));
1780
1781     size_t s = input.size();
1782     while ( s/2 < input.size() && !input.empty() )
1783     {
1784         t.remove(input.back());
1785         input.pop_back();
1786     }
1787
1788     bg::assign_inverse(b);
1789     BOOST_FOREACH(Value const& v, input)
1790         bg::expand(b, t.indexable_get()(v));
1791
1792     BOOST_CHECK(bg::equals(t.bounds(), b));
1793
1794     Tree t2(t);
1795     BOOST_CHECK(bg::equals(t2.bounds(), b));
1796     t2.clear();
1797     t2 = t;
1798     BOOST_CHECK(bg::equals(t2.bounds(), b));
1799     t2.clear();
1800     t2 = boost::move(t);
1801     BOOST_CHECK(bg::equals(t2.bounds(), b));
1802
1803     t.clear();
1804
1805     bg::assign_inverse(b);
1806     BOOST_CHECK(bg::equals(t.bounds(), b));
1807 }
1808
1809 template <typename Indexable, typename Parameters, typename Allocator>
1810 void test_rtree_additional(Parameters const& parameters, Allocator const& allocator)
1811 {
1812     test_count_rtree_values<Indexable>(parameters, allocator);
1813     test_rtree_count<Indexable>(parameters, allocator);
1814     test_rtree_bounds<Indexable>(parameters, allocator);
1815 }
1816
1817 // run all tests for one Algorithm for some number of rtrees
1818 // defined by some number of Values constructed from given Point
1819
1820 template<typename Point, typename Parameters, typename Allocator>
1821 void test_rtree_for_point(Parameters const& parameters, Allocator const& allocator)
1822 {
1823     typedef std::pair<Point, int> PairP;
1824     typedef boost::tuple<Point, int, int> TupleP;
1825     typedef boost::shared_ptr< test_object<Point> > SharedPtrP;
1826     typedef value_no_dctor<Point> VNoDCtor;
1827
1828     test_rtree_by_value<Point, Parameters>(parameters, allocator);
1829     test_rtree_by_value<PairP, Parameters>(parameters, allocator);
1830     test_rtree_by_value<TupleP, Parameters>(parameters, allocator);
1831
1832     test_rtree_by_value<SharedPtrP, Parameters>(parameters, allocator);
1833     test_rtree_by_value<VNoDCtor, Parameters>(parameters, allocator);
1834
1835     test_rtree_additional<Point>(parameters, allocator);
1836
1837 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1838     typedef std::tuple<Point, int, int> StdTupleP;
1839     test_rtree_by_value<StdTupleP, Parameters>(parameters, allocator);
1840 #endif
1841 }
1842
1843 template<typename Point, typename Parameters, typename Allocator>
1844 void test_rtree_for_box(Parameters const& parameters, Allocator const& allocator)
1845 {
1846     typedef bg::model::box<Point> Box;
1847     typedef std::pair<Box, int> PairB;
1848     typedef boost::tuple<Box, int, int> TupleB;
1849     typedef value_no_dctor<Box> VNoDCtor;
1850
1851     test_rtree_by_value<Box, Parameters>(parameters, allocator);
1852     test_rtree_by_value<PairB, Parameters>(parameters, allocator);
1853     test_rtree_by_value<TupleB, Parameters>(parameters, allocator);
1854
1855     test_rtree_by_value<VNoDCtor, Parameters>(parameters, allocator);
1856
1857     test_rtree_additional<Box>(parameters, allocator);
1858
1859 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1860     typedef std::tuple<Box, int, int> StdTupleB;
1861     test_rtree_by_value<StdTupleB, Parameters>(parameters, allocator);
1862 #endif
1863 }
1864
1865 template<typename Point, typename Parameters>
1866 void test_rtree_for_point(Parameters const& parameters)
1867 {
1868     test_rtree_for_point<Point>(parameters, std::allocator<int>());
1869 }
1870
1871 template<typename Point, typename Parameters>
1872 void test_rtree_for_box(Parameters const& parameters)
1873 {
1874     test_rtree_for_box<Point>(parameters, std::allocator<int>());
1875 }
1876
1877 namespace testset {
1878
1879 template<typename Indexable, typename Parameters, typename Allocator>
1880 void modifiers(Parameters const& parameters, Allocator const& allocator)
1881 {
1882     typedef std::pair<Indexable, int> Pair;
1883     typedef boost::tuple<Indexable, int, int> Tuple;
1884     typedef boost::shared_ptr< test_object<Indexable> > SharedPtr;
1885     typedef value_no_dctor<Indexable> VNoDCtor;
1886
1887     test_rtree_modifiers<Indexable>(parameters, allocator);
1888     test_rtree_modifiers<Pair>(parameters, allocator);
1889     test_rtree_modifiers<Tuple>(parameters, allocator);
1890
1891     test_rtree_modifiers<SharedPtr>(parameters, allocator);
1892     test_rtree_modifiers<VNoDCtor>(parameters, allocator);
1893
1894 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1895     typedef std::tuple<Indexable, int, int> StdTuple;
1896     test_rtree_modifiers<StdTuple>(parameters, allocator);
1897 #endif
1898 }
1899
1900 template<typename Indexable, typename Parameters, typename Allocator>
1901 void queries(Parameters const& parameters, Allocator const& allocator)
1902 {
1903     typedef std::pair<Indexable, int> Pair;
1904     typedef boost::tuple<Indexable, int, int> Tuple;
1905     typedef boost::shared_ptr< test_object<Indexable> > SharedPtr;
1906     typedef value_no_dctor<Indexable> VNoDCtor;
1907
1908     test_rtree_queries<Indexable>(parameters, allocator);
1909     test_rtree_queries<Pair>(parameters, allocator);
1910     test_rtree_queries<Tuple>(parameters, allocator);
1911
1912     test_rtree_queries<SharedPtr>(parameters, allocator);
1913     test_rtree_queries<VNoDCtor>(parameters, allocator);
1914
1915 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1916     typedef std::tuple<Indexable, int, int> StdTuple;
1917     test_rtree_queries<StdTuple>(parameters, allocator);
1918 #endif
1919 }
1920
1921 template<typename Indexable, typename Parameters, typename Allocator>
1922 void additional(Parameters const& parameters, Allocator const& allocator)
1923 {
1924     test_rtree_additional<Indexable, Parameters>(parameters, allocator);
1925 }
1926
1927 } // namespace testset
1928
1929 #endif // BOOST_GEOMETRY_INDEX_TEST_RTREE_HPP