ceph/src/boost/libs/geometry/include/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
   5 // This file was modified by Oracle on 2015.
   6 // Modifications copyright (c) 2015 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP
  16
  17 #include <cstddef>
  18 #include <vector>
  19 #include <boost/range.hpp>
  20 #include <boost/geometry/core/access.hpp>
  21 #include <boost/geometry/core/coordinate_type.hpp>
  22 #include <boost/geometry/algorithms/assign.hpp>
  23
  24
  25 namespace boost { namespace geometry
  26 {
  27
  28 namespace detail { namespace partition
  29 {
  30
  31 template <int Dimension, typename Box>
  32 inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
  33 {
  34     typedef typename coordinate_type<Box>::type ctype;
  35
  36     // Divide input box into two parts, e.g. left/right
  37     ctype two = 2;
  38     ctype mid = (geometry::get<min_corner, Dimension>(box)
  39             + geometry::get<max_corner, Dimension>(box)) / two;
  40
  41     lower_box = box;
  42     upper_box = box;
  43     geometry::set<max_corner, Dimension>(lower_box, mid);
  44     geometry::set<min_corner, Dimension>(upper_box, mid);
  45 }
  46
  47 // Divide forward_range into three subsets: lower, upper and oversized
  48 // (not-fitting)
  49 // (lower == left or bottom, upper == right or top)
  50 template <typename OverlapsPolicy, typename Box, typename IteratorVector>
  51 inline void divide_into_subsets(Box const& lower_box,
  52         Box const& upper_box,
  53         IteratorVector const& input,
  54         IteratorVector& lower,
  55         IteratorVector& upper,
  56         IteratorVector& exceeding)
  57 {
  58     typedef typename boost::range_iterator
  59         <
  60             IteratorVector const
  61         >::type it_type;
  62
  63     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
  64     {
  65         bool const lower_overlapping = OverlapsPolicy::apply(lower_box, **it);
  66         bool const upper_overlapping = OverlapsPolicy::apply(upper_box, **it);
  67
  68         if (lower_overlapping && upper_overlapping)
  69         {
  70             exceeding.push_back(*it);
  71         }
  72         else if (lower_overlapping)
  73         {
  74             lower.push_back(*it);
  75         }
  76         else if (upper_overlapping)
  77         {
  78             upper.push_back(*it);
  79         }
  80         else
  81         {
  82             // Is nowhere. That is (since 1.58) possible, it might be
  83             // skipped by the OverlapsPolicy to enhance performance
  84         }
  85     }
  86 }
  87
  88 template
  89 <
  90     typename ExpandPolicy,
  91     typename Box,
  92     typename IteratorVector
  93 >
  94 inline void expand_with_elements(Box& total, IteratorVector const& input)
  95 {
  96     typedef typename boost::range_iterator<IteratorVector const>::type it_type;
  97     for(it_type it = boost::begin(input); it != boost::end(input); ++it)
  98     {
  99         ExpandPolicy::apply(total, **it);
 100     }
 101 }
 102
 103
 104 // Match forward_range with itself
 105 template <typename Policy, typename IteratorVector>
 106 inline void handle_one(IteratorVector const& input, Policy& policy)
 107 {
 108     if (boost::size(input) == 0)
 109     {
 110         return;
 111     }
 112
 113     typedef typename boost::range_iterator<IteratorVector const>::type it_type;
 114
 115     // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
 116     for (it_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
 117     {
 118         it_type it2 = it1;
 119         for (++it2; it2 != boost::end(input); ++it2)
 120         {
 121             policy.apply(**it1, **it2);
 122         }
 123     }
 124 }
 125
 126 // Match forward range 1 with forward range 2
 127 template
 128 <
 129     typename Policy,
 130     typename IteratorVector1,
 131     typename IteratorVector2
 132 >
 133 inline void handle_two(IteratorVector1 const& input1,
 134         IteratorVector2 const& input2,
 135         Policy& policy)
 136 {
 137     typedef typename boost::range_iterator
 138         <
 139             IteratorVector1 const
 140         >::type iterator_type1;
 141
 142     typedef typename boost::range_iterator
 143         <
 144             IteratorVector2 const
 145         >::type iterator_type2;
 146
 147     if (boost::size(input1) == 0 || boost::size(input2) == 0)
 148     {
 149         return;
 150     }
 151
 152     for(iterator_type1 it1 = boost::begin(input1);
 153         it1 != boost::end(input1);
 154         ++it1)
 155     {
 156         for(iterator_type2 it2 = boost::begin(input2);
 157             it2 != boost::end(input2);
 158             ++it2)
 159         {
 160             policy.apply(**it1, **it2);
 161         }
 162     }
 163 }
 164
 165 template <typename IteratorVector>
 166 inline bool recurse_ok(IteratorVector const& input,
 167                 std::size_t min_elements, std::size_t level)
 168 {
 169     return boost::size(input) >= min_elements
 170         && level < 100;
 171 }
 172
 173 template <typename IteratorVector1, typename IteratorVector2>
 174 inline bool recurse_ok(IteratorVector1 const& input1,
 175                 IteratorVector2 const& input2,
 176                 std::size_t min_elements, std::size_t level)
 177 {
 178     return boost::size(input1) >= min_elements
 179         && recurse_ok(input2, min_elements, level);
 180 }
 181
 182 template
 183 <
 184     typename IteratorVector1,
 185     typename IteratorVector2,
 186     typename IteratorVector3
 187 >
 188 inline bool recurse_ok(IteratorVector1 const& input1,
 189                 IteratorVector2 const& input2,
 190                 IteratorVector3 const& input3,
 191                 std::size_t min_elements, std::size_t level)
 192 {
 193     return boost::size(input1) >= min_elements
 194         && recurse_ok(input2, input3, min_elements, level);
 195 }
 196
 197 template
 198 <
 199     int Dimension,
 200     typename Box,
 201     typename OverlapsPolicy1,
 202     typename OverlapsPolicy2,
 203     typename ExpandPolicy1,
 204     typename ExpandPolicy2,
 205     typename VisitBoxPolicy
 206 >
 207 class partition_two_ranges;
 208
 209
 210 template
 211 <
 212     int Dimension,
 213     typename Box,
 214     typename OverlapsPolicy,
 215     typename ExpandPolicy,
 216     typename VisitBoxPolicy
 217 >
 218 class partition_one_range
 219 {
 220     template <typename IteratorVector>
 221     static inline Box get_new_box(IteratorVector const& input)
 222     {
 223         Box box;
 224         geometry::assign_inverse(box);
 225         expand_with_elements<ExpandPolicy>(box, input);
 226         return box;
 227     }
 228
 229     template <typename Policy, typename IteratorVector>
 230     static inline void next_level(Box const& box,
 231             IteratorVector const& input,
 232             std::size_t level, std::size_t min_elements,
 233             Policy& policy, VisitBoxPolicy& box_policy)
 234     {
 235         if (recurse_ok(input, min_elements, level))
 236         {
 237             partition_one_range
 238             <
 239                 1 - Dimension,
 240                 Box,
 241                 OverlapsPolicy,
 242                 ExpandPolicy,
 243                 VisitBoxPolicy
 244             >::apply(box, input, level + 1, min_elements, policy, box_policy);
 245         }
 246         else
 247         {
 248             handle_one(input, policy);
 249         }
 250     }
 251
 252     // Function to switch to two forward ranges if there are
 253     // geometries exceeding the separation line
 254     template <typename Policy, typename IteratorVector>
 255     static inline void next_level2(Box const& box,
 256             IteratorVector const& input1,
 257             IteratorVector const& input2,
 258             std::size_t level, std::size_t min_elements,
 259             Policy& policy, VisitBoxPolicy& box_policy)
 260     {
 261         if (recurse_ok(input1, input2, min_elements, level))
 262         {
 263             partition_two_ranges
 264             <
 265                 1 - Dimension,
 266                 Box,
 267                 OverlapsPolicy, OverlapsPolicy,
 268                 ExpandPolicy, ExpandPolicy,
 269                 VisitBoxPolicy
 270             >::apply(box, input1, input2, level + 1, min_elements,
 271                 policy, box_policy);
 272         }
 273         else
 274         {
 275             handle_two(input1, input2, policy);
 276         }
 277     }
 278
 279 public :
 280     template <typename Policy, typename IteratorVector>
 281     static inline void apply(Box const& box,
 282             IteratorVector const& input,
 283             std::size_t level,
 284             std::size_t min_elements,
 285             Policy& policy, VisitBoxPolicy& box_policy)
 286     {
 287         box_policy.apply(box, level);
 288
 289         Box lower_box, upper_box;
 290         divide_box<Dimension>(box, lower_box, upper_box);
 291
 292         IteratorVector lower, upper, exceeding;
 293         divide_into_subsets<OverlapsPolicy>(lower_box, upper_box,
 294                     input, lower, upper, exceeding);
 295
 296         if (boost::size(exceeding) > 0)
 297         {
 298             // Get the box of exceeding-only
 299             Box exceeding_box = get_new_box(exceeding);
 300
 301             // Recursively do exceeding elements only, in next dimension they
 302             // will probably be less exceeding within the new box
 303             next_level(exceeding_box, exceeding, level, min_elements,
 304                 policy, box_policy);
 305
 306             // Switch to two forward ranges, combine exceeding with
 307             // lower resp upper, but not lower/lower, upper/upper
 308             next_level2(exceeding_box, exceeding, lower, level, min_elements,
 309                 policy, box_policy);
 310             next_level2(exceeding_box, exceeding, upper, level, min_elements,
 311                 policy, box_policy);
 312         }
 313
 314         // Recursively call operation both parts
 315         next_level(lower_box, lower, level, min_elements, policy, box_policy);
 316         next_level(upper_box, upper, level, min_elements, policy, box_policy);
 317     }
 318 };
 319
 320 template
 321 <
 322     int Dimension,
 323     typename Box,
 324     typename OverlapsPolicy1,
 325     typename OverlapsPolicy2,
 326     typename ExpandPolicy1,
 327     typename ExpandPolicy2,
 328     typename VisitBoxPolicy
 329 >
 330 class partition_two_ranges
 331 {
 332     template
 333     <
 334         typename Policy,
 335         typename IteratorVector1,
 336         typename IteratorVector2
 337     >
 338     static inline void next_level(Box const& box,
 339             IteratorVector1 const& input1,
 340             IteratorVector2 const& input2,
 341             std::size_t level, std::size_t min_elements,
 342             Policy& policy, VisitBoxPolicy& box_policy)
 343     {
 344         partition_two_ranges
 345         <
 346             1 - Dimension,
 347             Box,
 348             OverlapsPolicy1,
 349             OverlapsPolicy2,
 350             ExpandPolicy1,
 351             ExpandPolicy2,
 352             VisitBoxPolicy
 353         >::apply(box, input1, input2, level + 1, min_elements,
 354                  policy, box_policy);
 355     }
 356
 357     template <typename ExpandPolicy, typename IteratorVector>
 358     static inline Box get_new_box(IteratorVector const& input)
 359     {
 360         Box box;
 361         geometry::assign_inverse(box);
 362         expand_with_elements<ExpandPolicy>(box, input);
 363         return box;
 364     }
 365
 366     template <typename IteratorVector1, typename IteratorVector2>
 367     static inline Box get_new_box(IteratorVector1 const& input1,
 368                     IteratorVector2 const& input2)
 369     {
 370         Box box = get_new_box<ExpandPolicy1>(input1);
 371         expand_with_elements<ExpandPolicy2>(box, input2);
 372         return box;
 373     }
 374
 375 public :
 376     template
 377     <
 378         typename Policy,
 379         typename IteratorVector1,
 380         typename IteratorVector2
 381     >
 382     static inline void apply(Box const& box,
 383             IteratorVector1 const& input1,
 384             IteratorVector2 const& input2,
 385             std::size_t level,
 386             std::size_t min_elements,
 387             Policy& policy, VisitBoxPolicy& box_policy)
 388     {
 389         box_policy.apply(box, level);
 390
 391         Box lower_box, upper_box;
 392         divide_box<Dimension>(box, lower_box, upper_box);
 393
 394         IteratorVector1 lower1, upper1, exceeding1;
 395         IteratorVector2 lower2, upper2, exceeding2;
 396         divide_into_subsets<OverlapsPolicy1>(lower_box, upper_box,
 397                     input1, lower1, upper1, exceeding1);
 398         divide_into_subsets<OverlapsPolicy2>(lower_box, upper_box,
 399                     input2, lower2, upper2, exceeding2);
 400
 401         if (boost::size(exceeding1) > 0)
 402         {
 403             // All exceeding from 1 with 2:
 404
 405             if (recurse_ok(exceeding1, exceeding2, min_elements, level))
 406             {
 407                 Box exceeding_box = get_new_box(exceeding1, exceeding2);
 408                 next_level(exceeding_box, exceeding1, exceeding2, level,
 409                            min_elements, policy, box_policy);
 410             }
 411             else
 412             {
 413                 handle_two(exceeding1, exceeding2, policy);
 414             }
 415
 416             // All exceeding from 1 with lower and upper of 2:
 417
 418             // (Check sizes of all three forward ranges to avoid recurse into
 419             // the same combinations again and again)
 420             if (recurse_ok(lower2, upper2, exceeding1, min_elements, level))
 421             {
 422                 Box exceeding_box = get_new_box<ExpandPolicy1>(exceeding1);
 423                 next_level(exceeding_box, exceeding1, lower2, level,
 424                            min_elements, policy, box_policy);
 425                 next_level(exceeding_box, exceeding1, upper2, level,
 426                            min_elements, policy, box_policy);
 427             }
 428             else
 429             {
 430                 handle_two(exceeding1, lower2, policy);
 431                 handle_two(exceeding1, upper2, policy);
 432             }
 433         }
 434
 435         if (boost::size(exceeding2) > 0)
 436         {
 437             // All exceeding from 2 with lower and upper of 1:
 438             if (recurse_ok(lower1, upper1, exceeding2, min_elements, level))
 439             {
 440                 Box exceeding_box = get_new_box<ExpandPolicy2>(exceeding2);
 441                 next_level(exceeding_box, lower1, exceeding2, level,
 442                     min_elements, policy, box_policy);
 443                 next_level(exceeding_box, upper1, exceeding2, level,
 444                     min_elements, policy, box_policy);
 445             }
 446             else
 447             {
 448                 handle_two(lower1, exceeding2, policy);
 449                 handle_two(upper1, exceeding2, policy);
 450             }
 451         }
 452
 453         if (recurse_ok(lower1, lower2, min_elements, level))
 454         {
 455             next_level(lower_box, lower1, lower2, level,
 456                        min_elements, policy, box_policy);
 457         }
 458         else
 459         {
 460             handle_two(lower1, lower2, policy);
 461         }
 462         if (recurse_ok(upper1, upper2, min_elements, level))
 463         {
 464             next_level(upper_box, upper1, upper2, level,
 465                        min_elements, policy, box_policy);
 466         }
 467         else
 468         {
 469             handle_two(upper1, upper2, policy);
 470         }
 471     }
 472 };
 473
 474 struct visit_no_policy
 475 {
 476     template <typename Box>
 477     static inline void apply(Box const&, std::size_t )
 478     {}
 479 };
 480
 481 struct include_all_policy
 482 {
 483     template <typename Item>
 484     static inline bool apply(Item const&)
 485     {
 486         return true;
 487     }
 488 };
 489
 490
 491 }} // namespace detail::partition
 492
 493 template
 494 <
 495     typename Box,
 496     typename ExpandPolicy1,
 497     typename OverlapsPolicy1,
 498     typename ExpandPolicy2 = ExpandPolicy1,
 499     typename OverlapsPolicy2 = OverlapsPolicy1,
 500     typename IncludePolicy1 = detail::partition::include_all_policy,
 501     typename IncludePolicy2 = detail::partition::include_all_policy,
 502     typename VisitBoxPolicy = detail::partition::visit_no_policy
 503 >
 504 class partition
 505 {
 506     template
 507     <
 508         typename ExpandPolicy,
 509         typename IncludePolicy,
 510         typename ForwardRange,
 511         typename IteratorVector
 512     >
 513     static inline void expand_to_range(ForwardRange const& forward_range,
 514                 Box& total, IteratorVector& iterator_vector)
 515     {
 516         for(typename boost::range_iterator<ForwardRange const>::type it
 517             = boost::begin(forward_range);
 518             it != boost::end(forward_range);
 519             ++it)
 520         {
 521             if (IncludePolicy::apply(*it))
 522             {
 523                 ExpandPolicy::apply(total, *it);
 524                 iterator_vector.push_back(it);
 525             }
 526         }
 527     }
 528
 529 public :
 530     template <typename ForwardRange, typename VisitPolicy>
 531     static inline void apply(ForwardRange const& forward_range,
 532             VisitPolicy& visitor,
 533             std::size_t min_elements = 16,
 534             VisitBoxPolicy box_visitor = detail::partition::visit_no_policy()
 535             )
 536     {
 537         typedef typename boost::range_iterator
 538             <
 539                 ForwardRange const
 540             >::type iterator_type;
 541
 542         if (std::size_t(boost::size(forward_range)) > min_elements)
 543         {
 544             std::vector<iterator_type> iterator_vector;
 545             Box total;
 546             assign_inverse(total);
 547             expand_to_range<ExpandPolicy1, IncludePolicy1>(forward_range,
 548                     total, iterator_vector);
 549
 550             detail::partition::partition_one_range
 551                 <
 552                     0, Box,
 553                     OverlapsPolicy1,
 554                     ExpandPolicy1,
 555                     VisitBoxPolicy
 556                 >::apply(total, iterator_vector, 0, min_elements,
 557                          visitor, box_visitor);
 558         }
 559         else
 560         {
 561             for(iterator_type it1 = boost::begin(forward_range);
 562                 it1 != boost::end(forward_range);
 563                 ++it1)
 564             {
 565                 iterator_type it2 = it1;
 566                 for(++it2; it2 != boost::end(forward_range); ++it2)
 567                 {
 568                     visitor.apply(*it1, *it2);
 569                 }
 570             }
 571         }
 572     }
 573
 574     template
 575     <
 576         typename ForwardRange1,
 577         typename ForwardRange2,
 578         typename VisitPolicy
 579     >
 580     static inline void apply(ForwardRange1 const& forward_range1,
 581                 ForwardRange2 const& forward_range2,
 582                 VisitPolicy& visitor,
 583                 std::size_t min_elements = 16,
 584                 VisitBoxPolicy box_visitor
 585                     = detail::partition::visit_no_policy()
 586                 )
 587     {
 588         typedef typename boost::range_iterator
 589             <
 590                 ForwardRange1 const
 591             >::type iterator_type1;
 592
 593         typedef typename boost::range_iterator
 594             <
 595                 ForwardRange2 const
 596             >::type iterator_type2;
 597
 598         if (std::size_t(boost::size(forward_range1)) > min_elements
 599             && std::size_t(boost::size(forward_range2)) > min_elements)
 600         {
 601             std::vector<iterator_type1> iterator_vector1;
 602             std::vector<iterator_type2> iterator_vector2;
 603             Box total;
 604             assign_inverse(total);
 605             expand_to_range<ExpandPolicy1, IncludePolicy1>(forward_range1,
 606                     total, iterator_vector1);
 607             expand_to_range<ExpandPolicy2, IncludePolicy2>(forward_range2,
 608                     total, iterator_vector2);
 609
 610             detail::partition::partition_two_ranges
 611                 <
 612                     0, Box, OverlapsPolicy1, OverlapsPolicy2,
 613                     ExpandPolicy1, ExpandPolicy2, VisitBoxPolicy
 614                 >::apply(total, iterator_vector1, iterator_vector2,
 615                          0, min_elements, visitor, box_visitor);
 616         }
 617         else
 618         {
 619             for(iterator_type1 it1 = boost::begin(forward_range1);
 620                 it1 != boost::end(forward_range1);
 621                 ++it1)
 622             {
 623                 for(iterator_type2 it2 = boost::begin(forward_range2);
 624                     it2 != boost::end(forward_range2);
 625                     ++it2)
 626                 {
 627                     visitor.apply(*it1, *it2);
 628                 }
 629             }
 630         }
 631     }
 632 };
 633
 634
 635 }} // namespace boost::geometry
 636
 637 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP