ceph/src/boost/boost/geometry/algorithms/detail/partition.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2015, 2017.
   7 // Modifications copyright (c) 2015-2017 Oracle and/or its affiliates.
   8
   9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  11
  12 // Use, modification and distribution is subject to the Boost Software License,
  13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  14 // http://www.boost.org/LICENSE_1_0.txt)
  15
  16 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
  17 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
  18
  19 #include <cstddef>
  20 #include <vector>
  21 #include <boost/range.hpp>
  22 #include <boost/geometry/core/access.hpp>
  23 #include <boost/geometry/core/coordinate_type.hpp>
  24 #include <boost/geometry/algorithms/assign.hpp>
  25
  26
  27 namespace boost { namespace geometry
  28 {
  29
  30 namespace detail { namespace partition
  31 {
  32
  33 template <int Dimension, typename Box>
  34 inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
  35 {
  36     typedef typename coordinate_type<Box>::type ctype;
  37
  38     // Divide input box into two parts, e.g. left/right
  39     ctype two = 2;
  40     ctype mid = (geometry::get<min_corner, Dimension>(box)
  41             + geometry::get<max_corner, Dimension>(box)) / two;
  42
  43     lower_box = box;
  44     upper_box = box;
  45     geometry::set<max_corner, Dimension>(lower_box, mid);
  46     geometry::set<min_corner, Dimension>(upper_box, mid);
  47 }
  48
  49 // Divide forward_range into three subsets: lower, upper and oversized
  50 // (not-fitting)
  51 // (lower == left or bottom, upper == right or top)
  52 template <typename Box, typename IteratorVector, typename OverlapsPolicy>
  53 inline void divide_into_subsets(Box const& lower_box,
  54                                 Box const& upper_box,
  55                                 IteratorVector const& input,
  56                                 IteratorVector& lower,
  57                                 IteratorVector& upper,
  58                                 IteratorVector& exceeding,
  59                                 OverlapsPolicy const& overlaps_policy)
  60 {
  61     typedef typename boost::range_iterator
  62         <
  63             IteratorVector const
  64         >::type it_type;
  65
  66     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
  67     {
  68         bool const lower_overlapping = overlaps_policy.apply(lower_box, **it);
  69         bool const upper_overlapping = overlaps_policy.apply(upper_box, **it);
  70
  71         if (lower_overlapping && upper_overlapping)
  72         {
  73             exceeding.push_back(*it);
  74         }
  75         else if (lower_overlapping)
  76         {
  77             lower.push_back(*it);
  78         }
  79         else if (upper_overlapping)
  80         {
  81             upper.push_back(*it);
  82         }
  83         else
  84         {
  85             // Is nowhere. That is (since 1.58) possible, it might be
  86             // skipped by the OverlapsPolicy to enhance performance
  87         }
  88     }
  89 }
  90
  91 template
  92 <
  93     typename Box,
  94     typename IteratorVector,
  95     typename ExpandPolicy
  96 >
  97 inline void expand_with_elements(Box& total, IteratorVector const& input,
  98                                  ExpandPolicy const& expand_policy)
  99 {
 100     typedef typename boost::range_iterator<IteratorVector const>::type it_type;
 101     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
 102     {
 103         expand_policy.apply(total, **it);
 104     }
 105 }
 106
 107
 108 // Match forward_range with itself
 109 template <typename IteratorVector, typename VisitPolicy>
 110 inline bool handle_one(IteratorVector const& input, VisitPolicy& visitor)
 111 {
 112     if (boost::empty(input))
 113     {
 114         return true;
 115     }
 116
 117     typedef typename boost::range_iterator<IteratorVector const>::type it_type;
 118
 119     // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
 120     for (it_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
 121     {
 122         it_type it2 = it1;
 123         for (++it2; it2 != boost::end(input); ++it2)
 124         {
 125             if (! visitor.apply(**it1, **it2))
 126             {
 127                 return false; // interrupt
 128             }
 129         }
 130     }
 131
 132     return true;
 133 }
 134
 135 // Match forward range 1 with forward range 2
 136 template
 137 <
 138     typename IteratorVector1,
 139     typename IteratorVector2,
 140     typename VisitPolicy
 141 >
 142 inline bool handle_two(IteratorVector1 const& input1,
 143                        IteratorVector2 const& input2,
 144                        VisitPolicy& visitor)
 145 {
 146     typedef typename boost::range_iterator
 147         <
 148             IteratorVector1 const
 149         >::type iterator_type1;
 150
 151     typedef typename boost::range_iterator
 152         <
 153             IteratorVector2 const
 154         >::type iterator_type2;
 155
 156     if (boost::empty(input1) || boost::empty(input2))
 157     {
 158         return true;
 159     }
 160
 161     for(iterator_type1 it1 = boost::begin(input1);
 162         it1 != boost::end(input1);
 163         ++it1)
 164     {
 165         for(iterator_type2 it2 = boost::begin(input2);
 166             it2 != boost::end(input2);
 167             ++it2)
 168         {
 169             if (! visitor.apply(**it1, **it2))
 170             {
 171                 return false; // interrupt
 172             }
 173         }
 174     }
 175
 176     return true;
 177 }
 178
 179 template <typename IteratorVector>
 180 inline bool recurse_ok(IteratorVector const& input,
 181                        std::size_t min_elements, std::size_t level)
 182 {
 183     return boost::size(input) >= min_elements
 184         && level < 100;
 185 }
 186
 187 template <typename IteratorVector1, typename IteratorVector2>
 188 inline bool recurse_ok(IteratorVector1 const& input1,
 189                        IteratorVector2 const& input2,
 190                        std::size_t min_elements, std::size_t level)
 191 {
 192     return boost::size(input1) >= min_elements
 193         && recurse_ok(input2, min_elements, level);
 194 }
 195
 196 template
 197 <
 198     typename IteratorVector1,
 199     typename IteratorVector2,
 200     typename IteratorVector3
 201 >
 202 inline bool recurse_ok(IteratorVector1 const& input1,
 203                        IteratorVector2 const& input2,
 204                        IteratorVector3 const& input3,
 205                        std::size_t min_elements, std::size_t level)
 206 {
 207     return boost::size(input1) >= min_elements
 208         && recurse_ok(input2, input3, min_elements, level);
 209 }
 210
 211
 212 template <int Dimension, typename Box>
 213 class partition_two_ranges;
 214
 215
 216 template <int Dimension, typename Box>
 217 class partition_one_range
 218 {
 219     template <typename IteratorVector, typename ExpandPolicy>
 220     static inline Box get_new_box(IteratorVector const& input,
 221                                   ExpandPolicy const& expand_policy)
 222     {
 223         Box box;
 224         geometry::assign_inverse(box);
 225         expand_with_elements(box, input, expand_policy);
 226         return box;
 227     }
 228
 229     template
 230     <
 231         typename IteratorVector,
 232         typename VisitPolicy,
 233         typename ExpandPolicy,
 234         typename OverlapsPolicy,
 235         typename VisitBoxPolicy
 236     >
 237     static inline bool next_level(Box const& box,
 238                                   IteratorVector const& input,
 239                                   std::size_t level, std::size_t min_elements,
 240                                   VisitPolicy& visitor,
 241                                   ExpandPolicy const& expand_policy,
 242                                   OverlapsPolicy const& overlaps_policy,
 243                                   VisitBoxPolicy& box_policy)
 244     {
 245         if (recurse_ok(input, min_elements, level))
 246         {
 247             return partition_one_range
 248                 <
 249                     1 - Dimension,
 250                     Box
 251                 >::apply(box, input, level + 1, min_elements,
 252                          visitor, expand_policy, overlaps_policy, box_policy);
 253         }
 254         else
 255         {
 256             return handle_one(input, visitor);
 257         }
 258     }
 259
 260     // Function to switch to two forward ranges if there are
 261     // geometries exceeding the separation line
 262     template
 263     <
 264         typename IteratorVector,
 265         typename VisitPolicy,
 266         typename ExpandPolicy,
 267         typename OverlapsPolicy,
 268         typename VisitBoxPolicy
 269     >
 270     static inline bool next_level2(Box const& box,
 271                                    IteratorVector const& input1,
 272                                    IteratorVector const& input2,
 273                                    std::size_t level, std::size_t min_elements,
 274                                    VisitPolicy& visitor,
 275                                    ExpandPolicy const& expand_policy,
 276                                    OverlapsPolicy const& overlaps_policy,
 277                                    VisitBoxPolicy& box_policy)
 278     {
 279         if (recurse_ok(input1, input2, min_elements, level))
 280         {
 281             return partition_two_ranges
 282                 <
 283                     1 - Dimension, Box
 284                 >::apply(box, input1, input2, level + 1, min_elements,
 285                          visitor, expand_policy, overlaps_policy,
 286                          expand_policy, overlaps_policy, box_policy);
 287         }
 288         else
 289         {
 290             return handle_two(input1, input2, visitor);
 291         }
 292     }
 293
 294 public :
 295     template
 296     <
 297         typename IteratorVector,
 298         typename VisitPolicy,
 299         typename ExpandPolicy,
 300         typename OverlapsPolicy,
 301         typename VisitBoxPolicy
 302     >
 303     static inline bool apply(Box const& box,
 304                              IteratorVector const& input,
 305                              std::size_t level,
 306                              std::size_t min_elements,
 307                              VisitPolicy& visitor,
 308                              ExpandPolicy const& expand_policy,
 309                              OverlapsPolicy const& overlaps_policy,
 310                              VisitBoxPolicy& box_policy)
 311     {
 312         box_policy.apply(box, level);
 313
 314         Box lower_box, upper_box;
 315         divide_box<Dimension>(box, lower_box, upper_box);
 316
 317         IteratorVector lower, upper, exceeding;
 318         divide_into_subsets(lower_box, upper_box,
 319                             input, lower, upper, exceeding,
 320                             overlaps_policy);
 321
 322         if (! boost::empty(exceeding))
 323         {
 324             // Get the box of exceeding-only
 325             Box exceeding_box = get_new_box(exceeding, expand_policy);
 326
 327                    // Recursively do exceeding elements only, in next dimension they
 328                    // will probably be less exceeding within the new box
 329             if (! (next_level(exceeding_box, exceeding, level, min_elements,
 330                               visitor, expand_policy, overlaps_policy, box_policy)
 331                    // Switch to two forward ranges, combine exceeding with
 332                    // lower resp upper, but not lower/lower, upper/upper
 333                 && next_level2(exceeding_box, exceeding, lower, level, min_elements,
 334                                visitor, expand_policy, overlaps_policy, box_policy)
 335                 && next_level2(exceeding_box, exceeding, upper, level, min_elements,
 336                                visitor, expand_policy, overlaps_policy, box_policy)) )
 337             {
 338                 return false; // interrupt
 339             }
 340         }
 341
 342         // Recursively call operation both parts
 343         return next_level(lower_box, lower, level, min_elements,
 344                           visitor, expand_policy, overlaps_policy, box_policy)
 345             && next_level(upper_box, upper, level, min_elements,
 346                           visitor, expand_policy, overlaps_policy, box_policy);
 347     }
 348 };
 349
 350 template
 351 <
 352     int Dimension,
 353     typename Box
 354 >
 355 class partition_two_ranges
 356 {
 357     template
 358     <
 359         typename IteratorVector1,
 360         typename IteratorVector2,
 361         typename VisitPolicy,
 362         typename ExpandPolicy1,
 363         typename OverlapsPolicy1,
 364         typename ExpandPolicy2,
 365         typename OverlapsPolicy2,
 366         typename VisitBoxPolicy
 367     >
 368     static inline bool next_level(Box const& box,
 369                                   IteratorVector1 const& input1,
 370                                   IteratorVector2 const& input2,
 371                                   std::size_t level, std::size_t min_elements,
 372                                   VisitPolicy& visitor,
 373                                   ExpandPolicy1 const& expand_policy1,
 374                                   OverlapsPolicy1 const& overlaps_policy1,
 375                                   ExpandPolicy2 const& expand_policy2,
 376                                   OverlapsPolicy2 const& overlaps_policy2,
 377                                   VisitBoxPolicy& box_policy)
 378     {
 379         return partition_two_ranges
 380             <
 381                 1 - Dimension, Box
 382             >::apply(box, input1, input2, level + 1, min_elements,
 383                      visitor, expand_policy1, overlaps_policy1,
 384                      expand_policy2, overlaps_policy2, box_policy);
 385     }
 386
 387     template <typename IteratorVector, typename ExpandPolicy>
 388     static inline Box get_new_box(IteratorVector const& input,
 389                                   ExpandPolicy const& expand_policy)
 390     {
 391         Box box;
 392         geometry::assign_inverse(box);
 393         expand_with_elements(box, input, expand_policy);
 394         return box;
 395     }
 396
 397     template
 398     <
 399         typename IteratorVector1, typename IteratorVector2,
 400         typename ExpandPolicy1, typename ExpandPolicy2
 401     >
 402     static inline Box get_new_box(IteratorVector1 const& input1,
 403                                   IteratorVector2 const& input2,
 404                                   ExpandPolicy1 const& expand_policy1,
 405                                   ExpandPolicy2 const& expand_policy2)
 406     {
 407         Box box = get_new_box(input1, expand_policy1);
 408         expand_with_elements(box, input2, expand_policy2);
 409         return box;
 410     }
 411
 412 public :
 413     template
 414     <
 415         typename IteratorVector1,
 416         typename IteratorVector2,
 417         typename VisitPolicy,
 418         typename ExpandPolicy1,
 419         typename OverlapsPolicy1,
 420         typename ExpandPolicy2,
 421         typename OverlapsPolicy2,
 422         typename VisitBoxPolicy
 423     >
 424     static inline bool apply(Box const& box,
 425                              IteratorVector1 const& input1,
 426                              IteratorVector2 const& input2,
 427                              std::size_t level,
 428                              std::size_t min_elements,
 429                              VisitPolicy& visitor,
 430                              ExpandPolicy1 const& expand_policy1,
 431                              OverlapsPolicy1 const& overlaps_policy1,
 432                              ExpandPolicy2 const& expand_policy2,
 433                              OverlapsPolicy2 const& overlaps_policy2,
 434                              VisitBoxPolicy& box_policy)
 435     {
 436         box_policy.apply(box, level);
 437
 438         Box lower_box, upper_box;
 439         divide_box<Dimension>(box, lower_box, upper_box);
 440
 441         IteratorVector1 lower1, upper1, exceeding1;
 442         IteratorVector2 lower2, upper2, exceeding2;
 443         divide_into_subsets(lower_box, upper_box,
 444                             input1, lower1, upper1, exceeding1,
 445                             overlaps_policy1);
 446         divide_into_subsets(lower_box, upper_box,
 447                             input2, lower2, upper2, exceeding2,
 448                             overlaps_policy2);
 449
 450         if (! boost::empty(exceeding1))
 451         {
 452             // All exceeding from 1 with 2:
 453
 454             if (recurse_ok(exceeding1, exceeding2, min_elements, level))
 455             {
 456                 Box exceeding_box = get_new_box(exceeding1, exceeding2,
 457                                                 expand_policy1, expand_policy2);
 458                 if (! next_level(exceeding_box, exceeding1, exceeding2, level,
 459                                  min_elements, visitor, expand_policy1, overlaps_policy1,
 460                                  expand_policy2, overlaps_policy2, box_policy))
 461                 {
 462                     return false; // interrupt
 463                 }
 464             }
 465             else
 466             {
 467                 if (! handle_two(exceeding1, exceeding2, visitor))
 468                 {
 469                     return false; // interrupt
 470                 }
 471             }
 472
 473             // All exceeding from 1 with lower and upper of 2:
 474
 475             // (Check sizes of all three forward ranges to avoid recurse into
 476             // the same combinations again and again)
 477             if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
 478             {
 479                 Box exceeding_box = get_new_box(exceeding1, expand_policy1);
 480                 if (! (next_level(exceeding_box, exceeding1, lower2, level,
 481                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 482                                   expand_policy2, overlaps_policy2, box_policy)
 483                     && next_level(exceeding_box, exceeding1, upper2, level,
 484                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 485                                   expand_policy2, overlaps_policy2, box_policy)) )
 486                 {
 487                     return false; // interrupt
 488                 }
 489             }
 490             else
 491             {
 492                 if (! (handle_two(exceeding1, lower2, visitor)
 493                     && handle_two(exceeding1, upper2, visitor)) )
 494                 {
 495                     return false; // interrupt
 496                 }
 497             }
 498         }
 499
 500         if (! boost::empty(exceeding2))
 501         {
 502             // All exceeding from 2 with lower and upper of 1:
 503             if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
 504             {
 505                 Box exceeding_box = get_new_box(exceeding2, expand_policy2);
 506                 if (! (next_level(exceeding_box, lower1, exceeding2, level,
 507                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 508                                   expand_policy2, overlaps_policy2, box_policy)
 509                     && next_level(exceeding_box, upper1, exceeding2, level,
 510                                   min_elements, visitor, expand_policy1, overlaps_policy1,
 511                                   expand_policy2, overlaps_policy2, box_policy)) )
 512                 {
 513                     return false; // interrupt
 514                 }
 515             }
 516             else
 517             {
 518                 if (! (handle_two(lower1, exceeding2, visitor)
 519                     && handle_two(upper1, exceeding2, visitor)) )
 520                 {
 521                     return false; // interrupt
 522                 }
 523             }
 524         }
 525
 526         if (recurse_ok(lower1, lower2, min_elements, level))
 527         {
 528             if (! next_level(lower_box, lower1, lower2, level,
 529                              min_elements, visitor, expand_policy1, overlaps_policy1,
 530                              expand_policy2, overlaps_policy2, box_policy) )
 531             {
 532                 return false; // interrupt
 533             }
 534         }
 535         else
 536         {
 537             if (! handle_two(lower1, lower2, visitor))
 538             {
 539                 return false; // interrupt
 540             }
 541         }
 542
 543         if (recurse_ok(upper1, upper2, min_elements, level))
 544         {
 545             if (! next_level(upper_box, upper1, upper2, level,
 546                              min_elements, visitor, expand_policy1, overlaps_policy1,
 547                              expand_policy2, overlaps_policy2, box_policy) )
 548             {
 549                 return false; // interrupt
 550             }
 551         }
 552         else
 553         {
 554             if (! handle_two(upper1, upper2, visitor))
 555             {
 556                 return false; // interrupt
 557             }
 558         }
 559
 560         return true;
 561     }
 562 };
 563
 564 struct visit_no_policy
 565 {
 566     template <typename Box>
 567     static inline void apply(Box const&, std::size_t )
 568     {}
 569 };
 570
 571 struct include_all_policy
 572 {
 573     template <typename Item>
 574     static inline bool apply(Item const&)
 575     {
 576         return true;
 577     }
 578 };
 579
 580
 581 }} // namespace detail::partition
 582
 583 template
 584 <
 585     typename Box,
 586     typename IncludePolicy1 = detail::partition::include_all_policy,
 587     typename IncludePolicy2 = detail::partition::include_all_policy
 588 >
 589 class partition
 590 {
 591     static const std::size_t default_min_elements = 16;
 592
 593     template
 594     <
 595         typename IncludePolicy,
 596         typename ForwardRange,
 597         typename IteratorVector,
 598         typename ExpandPolicy
 599     >
 600     static inline void expand_to_range(ForwardRange const& forward_range,
 601                                        Box& total,
 602                                        IteratorVector& iterator_vector,
 603                                        ExpandPolicy const& expand_policy)
 604     {
 605         for(typename boost::range_iterator<ForwardRange const>::type
 606                 it = boost::begin(forward_range);
 607             it != boost::end(forward_range);
 608             ++it)
 609         {
 610             if (IncludePolicy::apply(*it))
 611             {
 612                 expand_policy.apply(total, *it);
 613                 iterator_vector.push_back(it);
 614             }
 615         }
 616     }
 617
 618 public:
 619     template
 620     <
 621         typename ForwardRange,
 622         typename VisitPolicy,
 623         typename ExpandPolicy,
 624         typename OverlapsPolicy
 625     >
 626     static inline bool apply(ForwardRange const& forward_range,
 627                              VisitPolicy& visitor,
 628                              ExpandPolicy const& expand_policy,
 629                              OverlapsPolicy const& overlaps_policy)
 630     {
 631         return apply(forward_range, visitor, expand_policy, overlaps_policy,
 632                      default_min_elements, detail::partition::visit_no_policy());
 633     }
 634
 635     template
 636     <
 637         typename ForwardRange,
 638         typename VisitPolicy,
 639         typename ExpandPolicy,
 640         typename OverlapsPolicy
 641     >
 642     static inline bool apply(ForwardRange const& forward_range,
 643                              VisitPolicy& visitor,
 644                              ExpandPolicy const& expand_policy,
 645                              OverlapsPolicy const& overlaps_policy,
 646                              std::size_t min_elements)
 647     {
 648         return apply(forward_range, visitor, expand_policy, overlaps_policy,
 649                      min_elements, detail::partition::visit_no_policy());
 650     }
 651
 652     template
 653     <
 654         typename ForwardRange,
 655         typename VisitPolicy,
 656         typename ExpandPolicy,
 657         typename OverlapsPolicy,
 658         typename VisitBoxPolicy
 659     >
 660     static inline bool apply(ForwardRange const& forward_range,
 661                              VisitPolicy& visitor,
 662                              ExpandPolicy const& expand_policy,
 663                              OverlapsPolicy const& overlaps_policy,
 664                              std::size_t min_elements,
 665                              VisitBoxPolicy box_visitor)
 666     {
 667         typedef typename boost::range_iterator
 668             <
 669                 ForwardRange const
 670             >::type iterator_type;
 671
 672         if (std::size_t(boost::size(forward_range)) > min_elements)
 673         {
 674             std::vector<iterator_type> iterator_vector;
 675             Box total;
 676             assign_inverse(total);
 677             expand_to_range<IncludePolicy1>(forward_range, total,
 678                                             iterator_vector, expand_policy);
 679
 680             return detail::partition::partition_one_range
 681                 <
 682                     0, Box
 683                 >::apply(total, iterator_vector, 0, min_elements,
 684                          visitor, expand_policy, overlaps_policy, box_visitor);
 685         }
 686         else
 687         {
 688             for(iterator_type it1 = boost::begin(forward_range);
 689                 it1 != boost::end(forward_range);
 690                 ++it1)
 691             {
 692                 iterator_type it2 = it1;
 693                 for(++it2; it2 != boost::end(forward_range); ++it2)
 694                 {
 695                     if (! visitor.apply(*it1, *it2))
 696                     {
 697                         return false; // interrupt
 698                     }
 699                 }
 700             }
 701         }
 702
 703         return true;
 704     }
 705
 706     template
 707     <
 708         typename ForwardRange1,
 709         typename ForwardRange2,
 710         typename VisitPolicy,
 711         typename ExpandPolicy1,
 712         typename OverlapsPolicy1
 713     >
 714     static inline bool apply(ForwardRange1 const& forward_range1,
 715                              ForwardRange2 const& forward_range2,
 716                              VisitPolicy& visitor,
 717                              ExpandPolicy1 const& expand_policy1,
 718                              OverlapsPolicy1 const& overlaps_policy1)
 719     {
 720         return apply(forward_range1, forward_range2, visitor,
 721                      expand_policy1, overlaps_policy1, expand_policy1, overlaps_policy1,
 722                      default_min_elements, detail::partition::visit_no_policy());
 723     }
 724
 725     template
 726     <
 727         typename ForwardRange1,
 728         typename ForwardRange2,
 729         typename VisitPolicy,
 730         typename ExpandPolicy1,
 731         typename OverlapsPolicy1,
 732         typename ExpandPolicy2,
 733         typename OverlapsPolicy2
 734     >
 735     static inline bool apply(ForwardRange1 const& forward_range1,
 736                              ForwardRange2 const& forward_range2,
 737                              VisitPolicy& visitor,
 738                              ExpandPolicy1 const& expand_policy1,
 739                              OverlapsPolicy1 const& overlaps_policy1,
 740                              ExpandPolicy2 const& expand_policy2,
 741                              OverlapsPolicy2 const& overlaps_policy2)
 742     {
 743         return apply(forward_range1, forward_range2, visitor,
 744                      expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
 745                      default_min_elements, detail::partition::visit_no_policy());
 746     }
 747
 748     template
 749     <
 750         typename ForwardRange1,
 751         typename ForwardRange2,
 752         typename VisitPolicy,
 753         typename ExpandPolicy1,
 754         typename OverlapsPolicy1,
 755         typename ExpandPolicy2,
 756         typename OverlapsPolicy2
 757     >
 758     static inline bool apply(ForwardRange1 const& forward_range1,
 759                              ForwardRange2 const& forward_range2,
 760                              VisitPolicy& visitor,
 761                              ExpandPolicy1 const& expand_policy1,
 762                              OverlapsPolicy1 const& overlaps_policy1,
 763                              ExpandPolicy2 const& expand_policy2,
 764                              OverlapsPolicy2 const& overlaps_policy2,
 765                              std::size_t min_elements)
 766     {
 767         return apply(forward_range1, forward_range2, visitor,
 768                      expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2,
 769                      min_elements, detail::partition::visit_no_policy());
 770     }
 771
 772     template
 773     <
 774         typename ForwardRange1,
 775         typename ForwardRange2,
 776         typename VisitPolicy,
 777         typename ExpandPolicy1,
 778         typename OverlapsPolicy1,
 779         typename ExpandPolicy2,
 780         typename OverlapsPolicy2,
 781         typename VisitBoxPolicy
 782     >
 783     static inline bool apply(ForwardRange1 const& forward_range1,
 784                              ForwardRange2 const& forward_range2,
 785                              VisitPolicy& visitor,
 786                              ExpandPolicy1 const& expand_policy1,
 787                              OverlapsPolicy1 const& overlaps_policy1,
 788                              ExpandPolicy2 const& expand_policy2,
 789                              OverlapsPolicy2 const& overlaps_policy2,
 790                              std::size_t min_elements,
 791                              VisitBoxPolicy box_visitor)
 792     {
 793         typedef typename boost::range_iterator
 794             <
 795                 ForwardRange1 const
 796             >::type iterator_type1;
 797
 798         typedef typename boost::range_iterator
 799             <
 800                 ForwardRange2 const
 801             >::type iterator_type2;
 802
 803         if (std::size_t(boost::size(forward_range1)) > min_elements
 804             && std::size_t(boost::size(forward_range2)) > min_elements)
 805         {
 806             std::vector<iterator_type1> iterator_vector1;
 807             std::vector<iterator_type2> iterator_vector2;
 808             Box total;
 809             assign_inverse(total);
 810             expand_to_range<IncludePolicy1>(forward_range1, total,
 811                                             iterator_vector1, expand_policy1);
 812             expand_to_range<IncludePolicy2>(forward_range2, total,
 813                                             iterator_vector2, expand_policy2);
 814
 815             return detail::partition::partition_two_ranges
 816                 <
 817                     0, Box
 818                 >::apply(total, iterator_vector1, iterator_vector2,
 819                          0, min_elements, visitor, expand_policy1,
 820                          overlaps_policy1, expand_policy2, overlaps_policy2,
 821                          box_visitor);
 822         }
 823         else
 824         {
 825             for(iterator_type1 it1 = boost::begin(forward_range1);
 826                 it1 != boost::end(forward_range1);
 827                 ++it1)
 828             {
 829                 for(iterator_type2 it2 = boost::begin(forward_range2);
 830                     it2 != boost::end(forward_range2);
 831                     ++it2)
 832                 {
 833                     if (! visitor.apply(*it1, *it2))
 834                     {
 835                         return false; // interrupt
 836                     }
 837                 }
 838             }
 839         }
 840
 841         return true;
 842     }
 843 };
 844
 845
 846 }} // namespace boost::geometry
 847
 848 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP