diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/partition.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/partition.hpp | 294 |
1 files changed, 175 insertions, 119 deletions
diff --git a/boost/geometry/algorithms/detail/partition.hpp b/boost/geometry/algorithms/detail/partition.hpp index 12c6a54661..db134d548d 100644 --- a/boost/geometry/algorithms/detail/partition.hpp +++ b/boost/geometry/algorithms/detail/partition.hpp @@ -1,6 +1,7 @@ // Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2011-2015 Barend Gehrels, Amsterdam, the Netherlands. +// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2015, 2017. // Modifications copyright (c) 2015-2017 Oracle and/or its affiliates. @@ -106,11 +107,11 @@ inline void expand_with_elements(Box& total, IteratorVector const& input, // Match forward_range with itself template <typename IteratorVector, typename VisitPolicy> -inline void handle_one(IteratorVector const& input, VisitPolicy& visitor) +inline bool handle_one(IteratorVector const& input, VisitPolicy& visitor) { - if (boost::size(input) == 0) + if (boost::empty(input)) { - return; + return true; } typedef typename boost::range_iterator<IteratorVector const>::type it_type; @@ -121,9 +122,14 @@ inline void handle_one(IteratorVector const& input, VisitPolicy& visitor) it_type it2 = it1; for (++it2; it2 != boost::end(input); ++it2) { - visitor.apply(**it1, **it2); + if (! visitor.apply(**it1, **it2)) + { + return false; // interrupt + } } } + + return true; } // Match forward range 1 with forward range 2 @@ -133,7 +139,7 @@ template typename IteratorVector2, typename VisitPolicy > -inline void handle_two(IteratorVector1 const& input1, +inline bool handle_two(IteratorVector1 const& input1, IteratorVector2 const& input2, VisitPolicy& visitor) { @@ -147,9 +153,9 @@ inline void handle_two(IteratorVector1 const& input1, IteratorVector2 const >::type iterator_type2; - if (boost::size(input1) == 0 || boost::size(input2) == 0) + if (boost::empty(input1) || boost::empty(input2)) { - return; + return true; } for(iterator_type1 it1 = boost::begin(input1); @@ -160,9 +166,14 @@ inline void handle_two(IteratorVector1 const& input1, it2 != boost::end(input2); ++it2) { - visitor.apply(**it1, **it2); + if (! visitor.apply(**it1, **it2)) + { + return false; // interrupt + } } } + + return true; } template <typename IteratorVector> @@ -223,7 +234,7 @@ class partition_one_range typename OverlapsPolicy, typename VisitBoxPolicy > - static inline void next_level(Box const& box, + static inline bool next_level(Box const& box, IteratorVector const& input, std::size_t level, std::size_t min_elements, VisitPolicy& visitor, @@ -233,7 +244,7 @@ class partition_one_range { if (recurse_ok(input, min_elements, level)) { - partition_one_range + return partition_one_range < 1 - Dimension, Box @@ -242,7 +253,7 @@ class partition_one_range } else { - handle_one(input, visitor); + return handle_one(input, visitor); } } @@ -256,18 +267,18 @@ class partition_one_range typename OverlapsPolicy, typename VisitBoxPolicy > - static inline void next_level2(Box const& box, - IteratorVector const& input1, - IteratorVector const& input2, - std::size_t level, std::size_t min_elements, - VisitPolicy& visitor, - ExpandPolicy const& expand_policy, - OverlapsPolicy const& overlaps_policy, - VisitBoxPolicy& box_policy) + static inline bool next_level2(Box const& box, + IteratorVector const& input1, + IteratorVector const& input2, + std::size_t level, std::size_t min_elements, + VisitPolicy& visitor, + ExpandPolicy const& expand_policy, + OverlapsPolicy const& overlaps_policy, + VisitBoxPolicy& box_policy) { if (recurse_ok(input1, input2, min_elements, level)) { - partition_two_ranges + return partition_two_ranges < 1 - Dimension, Box >::apply(box, input1, input2, level + 1, min_elements, @@ -276,7 +287,7 @@ class partition_one_range } else { - handle_two(input1, input2, visitor); + return handle_two(input1, input2, visitor); } } @@ -289,7 +300,7 @@ public : typename OverlapsPolicy, typename VisitBoxPolicy > - static inline void apply(Box const& box, + static inline bool apply(Box const& box, IteratorVector const& input, std::size_t level, std::size_t min_elements, @@ -308,29 +319,31 @@ public : input, lower, upper, exceeding, overlaps_policy); - if (boost::size(exceeding) > 0) + if (! boost::empty(exceeding)) { // Get the box of exceeding-only Box exceeding_box = get_new_box(exceeding, expand_policy); - // Recursively do exceeding elements only, in next dimension they - // will probably be less exceeding within the new box - next_level(exceeding_box, exceeding, level, min_elements, - visitor, expand_policy, overlaps_policy, box_policy); - - // Switch to two forward ranges, combine exceeding with - // lower resp upper, but not lower/lower, upper/upper - next_level2(exceeding_box, exceeding, lower, level, min_elements, - visitor, expand_policy, overlaps_policy, box_policy); - next_level2(exceeding_box, exceeding, upper, level, min_elements, - visitor, expand_policy, overlaps_policy, box_policy); + // Recursively do exceeding elements only, in next dimension they + // will probably be less exceeding within the new box + if (! (next_level(exceeding_box, exceeding, level, min_elements, + visitor, expand_policy, overlaps_policy, box_policy) + // Switch to two forward ranges, combine exceeding with + // lower resp upper, but not lower/lower, upper/upper + && next_level2(exceeding_box, exceeding, lower, level, min_elements, + visitor, expand_policy, overlaps_policy, box_policy) + && next_level2(exceeding_box, exceeding, upper, level, min_elements, + visitor, expand_policy, overlaps_policy, box_policy)) ) + { + return false; // interrupt + } } // Recursively call operation both parts - next_level(lower_box, lower, level, min_elements, - visitor, expand_policy, overlaps_policy, box_policy); - next_level(upper_box, upper, level, min_elements, - visitor, expand_policy, overlaps_policy, box_policy); + return next_level(lower_box, lower, level, min_elements, + visitor, expand_policy, overlaps_policy, box_policy) + && next_level(upper_box, upper, level, min_elements, + visitor, expand_policy, overlaps_policy, box_policy); } }; @@ -352,23 +365,23 @@ class partition_two_ranges typename OverlapsPolicy2, typename VisitBoxPolicy > - static inline void next_level(Box const& box, - IteratorVector1 const& input1, - IteratorVector2 const& input2, - std::size_t level, std::size_t min_elements, - VisitPolicy& visitor, - ExpandPolicy1 const& expand_policy1, - OverlapsPolicy1 const& overlaps_policy1, - ExpandPolicy2 const& expand_policy2, - OverlapsPolicy2 const& overlaps_policy2, - VisitBoxPolicy& box_policy) + static inline bool next_level(Box const& box, + IteratorVector1 const& input1, + IteratorVector2 const& input2, + std::size_t level, std::size_t min_elements, + VisitPolicy& visitor, + ExpandPolicy1 const& expand_policy1, + OverlapsPolicy1 const& overlaps_policy1, + ExpandPolicy2 const& expand_policy2, + OverlapsPolicy2 const& overlaps_policy2, + VisitBoxPolicy& box_policy) { - partition_two_ranges - < - 1 - Dimension, Box - >::apply(box, input1, input2, level + 1, min_elements, - visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); + return partition_two_ranges + < + 1 - Dimension, Box + >::apply(box, input1, input2, level + 1, min_elements, + visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy); } template <typename IteratorVector, typename ExpandPolicy> @@ -408,17 +421,17 @@ public : typename OverlapsPolicy2, typename VisitBoxPolicy > - static inline void apply(Box const& box, - IteratorVector1 const& input1, - IteratorVector2 const& input2, - std::size_t level, - std::size_t min_elements, - VisitPolicy& visitor, - ExpandPolicy1 const& expand_policy1, - OverlapsPolicy1 const& overlaps_policy1, - ExpandPolicy2 const& expand_policy2, - OverlapsPolicy2 const& overlaps_policy2, - VisitBoxPolicy& box_policy) + static inline bool apply(Box const& box, + IteratorVector1 const& input1, + IteratorVector2 const& input2, + std::size_t level, + std::size_t min_elements, + VisitPolicy& visitor, + ExpandPolicy1 const& expand_policy1, + OverlapsPolicy1 const& overlaps_policy1, + ExpandPolicy2 const& expand_policy2, + OverlapsPolicy2 const& overlaps_policy2, + VisitBoxPolicy& box_policy) { box_policy.apply(box, level); @@ -434,7 +447,7 @@ public : input2, lower2, upper2, exceeding2, overlaps_policy2); - if (boost::size(exceeding1) > 0) + if (! boost::empty(exceeding1)) { // All exceeding from 1 with 2: @@ -442,13 +455,19 @@ public : { Box exceeding_box = get_new_box(exceeding1, exceeding2, expand_policy1, expand_policy2); - next_level(exceeding_box, exceeding1, exceeding2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); + if (! next_level(exceeding_box, exceeding1, exceeding2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy)) + { + return false; // interrupt + } } else { - handle_two(exceeding1, exceeding2, visitor); + if (! handle_two(exceeding1, exceeding2, visitor)) + { + return false; // interrupt + } } // All exceeding from 1 with lower and upper of 2: @@ -458,60 +477,87 @@ public : if (recurse_ok(lower2, upper2, exceeding1, min_elements, level)) { Box exceeding_box = get_new_box(exceeding1, expand_policy1); - next_level(exceeding_box, exceeding1, lower2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); - next_level(exceeding_box, exceeding1, upper2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); + if (! (next_level(exceeding_box, exceeding1, lower2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy) + && next_level(exceeding_box, exceeding1, upper2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy)) ) + { + return false; // interrupt + } } else { - handle_two(exceeding1, lower2, visitor); - handle_two(exceeding1, upper2, visitor); + if (! (handle_two(exceeding1, lower2, visitor) + && handle_two(exceeding1, upper2, visitor)) ) + { + return false; // interrupt + } } } - if (boost::size(exceeding2) > 0) + if (! boost::empty(exceeding2)) { // All exceeding from 2 with lower and upper of 1: if (recurse_ok(lower1, upper1, exceeding2, min_elements, level)) { Box exceeding_box = get_new_box(exceeding2, expand_policy2); - next_level(exceeding_box, lower1, exceeding2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); - next_level(exceeding_box, upper1, exceeding2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); + if (! (next_level(exceeding_box, lower1, exceeding2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy) + && next_level(exceeding_box, upper1, exceeding2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy)) ) + { + return false; // interrupt + } } else { - handle_two(lower1, exceeding2, visitor); - handle_two(upper1, exceeding2, visitor); + if (! (handle_two(lower1, exceeding2, visitor) + && handle_two(upper1, exceeding2, visitor)) ) + { + return false; // interrupt + } } } if (recurse_ok(lower1, lower2, min_elements, level)) { - next_level(lower_box, lower1, lower2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); + if (! next_level(lower_box, lower1, lower2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy) ) + { + return false; // interrupt + } } else { - handle_two(lower1, lower2, visitor); + if (! handle_two(lower1, lower2, visitor)) + { + return false; // interrupt + } } + if (recurse_ok(upper1, upper2, min_elements, level)) { - next_level(upper_box, upper1, upper2, level, - min_elements, visitor, expand_policy1, overlaps_policy1, - expand_policy2, overlaps_policy2, box_policy); + if (! next_level(upper_box, upper1, upper2, level, + min_elements, visitor, expand_policy1, overlaps_policy1, + expand_policy2, overlaps_policy2, box_policy) ) + { + return false; // interrupt + } } else { - handle_two(upper1, upper2, visitor); + if (! handle_two(upper1, upper2, visitor)) + { + return false; // interrupt + } } + + return true; } }; @@ -577,13 +623,13 @@ public: typename ExpandPolicy, typename OverlapsPolicy > - static inline void apply(ForwardRange const& forward_range, + static inline bool apply(ForwardRange const& forward_range, VisitPolicy& visitor, ExpandPolicy const& expand_policy, OverlapsPolicy const& overlaps_policy) { - apply(forward_range, visitor, expand_policy, overlaps_policy, - default_min_elements, detail::partition::visit_no_policy()); + return apply(forward_range, visitor, expand_policy, overlaps_policy, + default_min_elements, detail::partition::visit_no_policy()); } template @@ -593,14 +639,14 @@ public: typename ExpandPolicy, typename OverlapsPolicy > - static inline void apply(ForwardRange const& forward_range, + static inline bool apply(ForwardRange const& forward_range, VisitPolicy& visitor, ExpandPolicy const& expand_policy, OverlapsPolicy const& overlaps_policy, std::size_t min_elements) { - apply(forward_range, visitor, expand_policy, overlaps_policy, - min_elements, detail::partition::visit_no_policy()); + return apply(forward_range, visitor, expand_policy, overlaps_policy, + min_elements, detail::partition::visit_no_policy()); } template @@ -611,7 +657,7 @@ public: typename OverlapsPolicy, typename VisitBoxPolicy > - static inline void apply(ForwardRange const& forward_range, + static inline bool apply(ForwardRange const& forward_range, VisitPolicy& visitor, ExpandPolicy const& expand_policy, OverlapsPolicy const& overlaps_policy, @@ -631,7 +677,7 @@ public: expand_to_range<IncludePolicy1>(forward_range, total, iterator_vector, expand_policy); - detail::partition::partition_one_range + return detail::partition::partition_one_range < 0, Box >::apply(total, iterator_vector, 0, min_elements, @@ -646,10 +692,15 @@ public: iterator_type it2 = it1; for(++it2; it2 != boost::end(forward_range); ++it2) { - visitor.apply(*it1, *it2); + if (! visitor.apply(*it1, *it2)) + { + return false; // interrupt + } } } } + + return true; } template @@ -660,15 +711,15 @@ public: typename ExpandPolicy1, typename OverlapsPolicy1 > - static inline void apply(ForwardRange1 const& forward_range1, + static inline bool apply(ForwardRange1 const& forward_range1, ForwardRange2 const& forward_range2, VisitPolicy& visitor, ExpandPolicy1 const& expand_policy1, OverlapsPolicy1 const& overlaps_policy1) { - apply(forward_range1, forward_range2, visitor, - expand_policy1, overlaps_policy1, expand_policy1, overlaps_policy1, - default_min_elements, detail::partition::visit_no_policy()); + return apply(forward_range1, forward_range2, visitor, + expand_policy1, overlaps_policy1, expand_policy1, overlaps_policy1, + default_min_elements, detail::partition::visit_no_policy()); } template @@ -681,7 +732,7 @@ public: typename ExpandPolicy2, typename OverlapsPolicy2 > - static inline void apply(ForwardRange1 const& forward_range1, + static inline bool apply(ForwardRange1 const& forward_range1, ForwardRange2 const& forward_range2, VisitPolicy& visitor, ExpandPolicy1 const& expand_policy1, @@ -689,9 +740,9 @@ public: ExpandPolicy2 const& expand_policy2, OverlapsPolicy2 const& overlaps_policy2) { - apply(forward_range1, forward_range2, visitor, - expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2, - default_min_elements, detail::partition::visit_no_policy()); + return apply(forward_range1, forward_range2, visitor, + expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy2, + default_min_elements, detail::partition::visit_no_policy()); } template @@ -704,7 +755,7 @@ public: typename ExpandPolicy2, typename OverlapsPolicy2 > - static inline void apply(ForwardRange1 const& forward_range1, + static inline bool apply(ForwardRange1 const& forward_range1, ForwardRange2 const& forward_range2, VisitPolicy& visitor, ExpandPolicy1 const& expand_policy1, @@ -713,9 +764,9 @@ public: OverlapsPolicy2 const& overlaps_policy2, std::size_t min_elements) { - apply(forward_range1, forward_range2, visitor, - expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy1, - min_elements, detail::partition::visit_no_policy()); + return apply(forward_range1, forward_range2, visitor, + expand_policy1, overlaps_policy1, expand_policy2, overlaps_policy1, + min_elements, detail::partition::visit_no_policy()); } template @@ -729,7 +780,7 @@ public: typename OverlapsPolicy2, typename VisitBoxPolicy > - static inline void apply(ForwardRange1 const& forward_range1, + static inline bool apply(ForwardRange1 const& forward_range1, ForwardRange2 const& forward_range2, VisitPolicy& visitor, ExpandPolicy1 const& expand_policy1, @@ -761,7 +812,7 @@ public: expand_to_range<IncludePolicy2>(forward_range2, total, iterator_vector2, expand_policy2); - detail::partition::partition_two_ranges + return detail::partition::partition_two_ranges < 0, Box >::apply(total, iterator_vector1, iterator_vector2, @@ -779,10 +830,15 @@ public: it2 != boost::end(forward_range2); ++it2) { - visitor.apply(*it1, *it2); + if (! visitor.apply(*it1, *it2)) + { + return false; // interrupt + } } } } + + return true; } }; |