summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/partition.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/partition.hpp')
-rw-r--r--boost/geometry/algorithms/detail/partition.hpp294
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;
}
};