|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r70183 - in trunk/boost/geometry/algorithms/detail: . sections
From: barend.gehrels_at_[hidden]
Date: 2011-03-19 10:01:12
Author: barendgehrels
Date: 2011-03-19 10:01:11 EDT (Sat, 19 Mar 2011)
New Revision: 70183
URL: http://svn.boost.org/trac/boost/changeset/70183
Log:
Bugfix partition for clang
Added undocked par for sectionalize
Text files modified:
trunk/boost/geometry/algorithms/detail/partition.hpp | 216 ++++++++++++++++++++++-----------------
trunk/boost/geometry/algorithms/detail/sections/sectionalize.hpp | 2
2 files changed, 122 insertions(+), 96 deletions(-)
Modified: trunk/boost/geometry/algorithms/detail/partition.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/partition.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/partition.hpp 2011-03-19 10:01:11 EDT (Sat, 19 Mar 2011)
@@ -16,9 +16,11 @@
{
-namespace detail
+namespace detail { namespace partition
{
+typedef std::vector<std::size_t> index_vector_type;
+
template <int Dimension, typename Box>
inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
{
@@ -35,95 +37,90 @@
geometry::set<min_corner, Dimension>(upper_box, mid);
}
-template
-<
- typename Box,
- typename OverlapsPolicy
->
-class partition_generic
+// Divide collection into three subsets: lower, upper and oversized (not-fitting)
+// (lower == left or bottom, upper == right or top)
+template <typename OverlapsPolicy, typename InputCollection, typename Box>
+static inline void divide_into_subsets(Box const& lower_box, Box const& upper_box,
+ InputCollection const& collection,
+ index_vector_type const& input,
+ index_vector_type& lower,
+ index_vector_type& upper,
+ index_vector_type& exceeding)
{
- typedef std::vector<std::size_t> index_vector_type;
-protected :
typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
- // Divide collection into three subsets: lower, upper and oversized (not-fitting)
- // (lower == left or bottom, upper == right or top)
- template <typename InputCollection>
- static inline void divide_into_subsets(Box const& lower_box, Box const& upper_box,
- InputCollection const& collection,
- index_vector_type const& input,
- index_vector_type& lower, index_vector_type& upper, index_vector_type& exceeding)
+ for(index_iterator_type it = boost::begin(input);
+ it != boost::end(input);
+ ++it)
{
- for(index_iterator_type it = boost::begin(input);
- it != boost::end(input);
- ++it)
- {
- bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
- bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);
+ bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
+ bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);
- if (lower_overlapping && upper_overlapping)
- {
- exceeding.push_back(*it);
- }
- else if (lower_overlapping)
- {
- lower.push_back(*it);
- }
- else if (upper_overlapping)
- {
- upper.push_back(*it);
- }
- else
- {
- // Is nowhere! Should not occur!
- BOOST_ASSERT(true);
- }
+ if (lower_overlapping && upper_overlapping)
+ {
+ exceeding.push_back(*it);
+ }
+ else if (lower_overlapping)
+ {
+ lower.push_back(*it);
+ }
+ else if (upper_overlapping)
+ {
+ upper.push_back(*it);
+ }
+ else
+ {
+ // Is nowhere! Should not occur!
+ BOOST_ASSERT(true);
}
}
+}
- // Match collection 1 with collection 2
- template <typename InputCollection, typename Policy>
- static inline void handle_one(InputCollection const& collection,
- index_vector_type const& input,
- Policy& policy)
+
+// Match collection 1 with collection 2
+template <typename InputCollection, typename Policy>
+static inline void handle_one(InputCollection const& collection,
+ index_vector_type const& input,
+ Policy& policy)
+{
+ typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
+ // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
+ for(index_iterator_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
{
- // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
- for(index_iterator_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
+ index_iterator_type it2 = it1;
+ for(++it2; it2 != boost::end(input); ++it2)
{
- index_iterator_type it2 = it1;
- for(++it2; it2 != boost::end(input); ++it2)
- {
- policy.apply(collection[*it1], collection[*it2]);
- }
+ policy.apply(collection[*it1], collection[*it2]);
}
}
+}
- // Match collection 1 with collection 2
- template <typename InputCollection, typename Policy>
- static inline void handle_two(
- InputCollection const& collection1, index_vector_type const& input1,
- InputCollection const& collection2, index_vector_type const& input2,
- Policy& policy)
+// Match collection 1 with collection 2
+template <typename InputCollection, typename Policy>
+static inline void handle_two(
+ InputCollection const& collection1, index_vector_type const& input1,
+ InputCollection const& collection2, index_vector_type const& input2,
+ Policy& policy)
+{
+ typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
+ for(index_iterator_type it1 = boost::begin(input1); it1 != boost::end(input1); ++it1)
{
- for(index_iterator_type it1 = boost::begin(input1); it1 != boost::end(input1); ++it1)
+ for(index_iterator_type it2 = boost::begin(input2); it2 != boost::end(input2); ++it2)
{
- for(index_iterator_type it2 = boost::begin(input2); it2 != boost::end(input2); ++it2)
- {
- policy.apply(collection1[*it1], collection2[*it2]);
- }
+ policy.apply(collection1[*it1], collection2[*it2]);
}
}
-};
-
+}
template
<
int Dimension,
typename Box,
- typename OverlapsPolicy
+ typename OverlapsPolicy,
+ typename VisitBoxPolicy
>
-class partition_one_collection : public partition_generic<Box, OverlapsPolicy>
+class partition_one_collection
{
typedef std::vector<std::size_t> index_vector_type;
typedef typename coordinate_type<Box>::type ctype;
@@ -131,7 +128,8 @@
<
1 - Dimension,
Box,
- OverlapsPolicy
+ OverlapsPolicy,
+ VisitBoxPolicy
> sub_divide;
template <typename InputCollection, typename Policy>
@@ -139,13 +137,13 @@
InputCollection const& collection,
index_vector_type const& input,
int level, int min_elements,
- Policy& policy)
+ Policy& policy, VisitBoxPolicy& box_policy)
{
if (boost::size(input) > 0)
{
if (boost::size(input) > min_elements && level < 100)
{
- sub_divide::apply(box, collection, input, level + 1, min_elements, policy);
+ sub_divide::apply(box, collection, input, level + 1, min_elements, policy, box_policy);
}
else
{
@@ -161,13 +159,15 @@
index_vector_type const& input,
int level,
int min_elements,
- Policy& policy)
+ Policy& policy, VisitBoxPolicy& box_policy)
{
+ box_policy.apply(box, level);
+
Box lower_box, upper_box;
divide_box<Dimension>(box, lower_box, upper_box);
index_vector_type lower, upper, exceeding;
- divide_into_subsets(lower_box, upper_box, collection, input, lower, upper, exceeding);
+ divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection, input, lower, upper, exceeding);
if (boost::size(exceeding) > 0)
{
@@ -179,8 +179,8 @@
}
// Recursively call operation both parts
- next_level(lower_box, collection, lower, level, min_elements, policy);
- next_level(upper_box, collection, upper, level, min_elements, policy);
+ next_level(lower_box, collection, lower, level, min_elements, policy, box_policy);
+ next_level(upper_box, collection, upper, level, min_elements, policy, box_policy);
}
};
@@ -189,9 +189,10 @@
<
int Dimension,
typename Box,
- typename OverlapsPolicy
+ typename OverlapsPolicy,
+ typename VisitBoxPolicy
>
-class partition_two_collections : public partition_generic<Box, OverlapsPolicy>
+class partition_two_collections
{
typedef std::vector<std::size_t> index_vector_type;
typedef typename coordinate_type<Box>::type ctype;
@@ -199,7 +200,8 @@
<
1 - Dimension,
Box,
- OverlapsPolicy
+ OverlapsPolicy,
+ VisitBoxPolicy
> sub_divide;
template <typename InputCollection, typename Policy>
@@ -207,7 +209,7 @@
InputCollection const& collection1, index_vector_type const& input1,
InputCollection const& collection2, index_vector_type const& input2,
int level, int min_elements,
- Policy& policy)
+ Policy& policy, VisitBoxPolicy& box_policy)
{
if (boost::size(input1) > 0 && boost::size(input2) > 0)
{
@@ -215,10 +217,11 @@
&& boost::size(input2) > min_elements
&& level < 100)
{
- sub_divide::apply(box, collection1, input1, collection2, input2, level + 1, min_elements, policy);
+ sub_divide::apply(box, collection1, input1, collection2, input2, level + 1, min_elements, policy, box_policy);
}
else
{
+ box_policy.apply(box, level + 1);
handle_two(collection1, input1, collection2, input2, policy);
}
}
@@ -231,15 +234,17 @@
InputCollection const& collection2, index_vector_type const& input2,
int level,
int min_elements,
- Policy& policy)
+ Policy& policy, VisitBoxPolicy& box_policy)
{
+ box_policy.apply(box, level);
+
Box lower_box, upper_box;
divide_box<Dimension>(box, lower_box, upper_box);
index_vector_type lower1, upper1, exceeding1;
index_vector_type lower2, upper2, exceeding2;
- divide_into_subsets(lower_box, upper_box, collection1, input1, lower1, upper1, exceeding1);
- divide_into_subsets(lower_box, upper_box, collection2, input2, lower2, upper2, exceeding2);
+ divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection1, input1, lower1, upper1, exceeding1);
+ divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection2, input2, lower2, upper2, exceeding2);
if (boost::size(exceeding1) > 0)
{
@@ -257,19 +262,29 @@
handle_two(collection1, upper1, collection2, exceeding2, policy);
}
- next_level(lower_box, collection1, lower1, collection2, lower2, level, min_elements, policy);
- next_level(upper_box, collection1, upper1, collection2, upper2, level, min_elements, policy);
+ next_level(lower_box, collection1, lower1, collection2, lower2, level, min_elements, policy, box_policy);
+ next_level(upper_box, collection1, upper1, collection2, upper2, level, min_elements, policy, box_policy);
}
};
-} // namespace detail
+
+
+}} // namespace detail::partition
+
+struct visit_no_policy
+{
+ template <typename Box>
+ static inline void apply(Box const&, int )
+ {}
+};
template
<
typename Box,
typename ExpandPolicy,
- typename OverlapsPolicy
+ typename OverlapsPolicy,
+ typename VisitBoxPolicy = visit_no_policy
>
class partition
{
@@ -291,8 +306,12 @@
public :
- template <typename InputCollection, typename Visitor>
- static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
+ template <typename InputCollection, typename VisitPolicy>
+ static inline void apply(InputCollection const& collection,
+ VisitPolicy& visitor,
+ int min_elements = 16,
+ VisitBoxPolicy box_visitor = visit_no_policy()
+ )
{
if (boost::size(collection) > min_elements)
{
@@ -301,10 +320,12 @@
assign_inverse(total);
expand_to_collection(collection, total, index_vector);
- detail::partition_one_collection
+ detail::partition::partition_one_collection
<
- 0, Box, OverlapsPolicy
- >::apply(total, collection, index_vector, 0, min_elements, visitor);
+ 0, Box,
+ OverlapsPolicy,
+ VisitBoxPolicy
+ >::apply(total, collection, index_vector, 0, min_elements, visitor, box_visitor);
}
else
{
@@ -320,8 +341,13 @@
}
}
- template <typename InputCollection, typename Visitor>
- static inline void apply(InputCollection const& collection1, InputCollection const& collection2, Visitor& visitor, int min_elements = 16)
+ template <typename InputCollection, typename VisitPolicy>
+ static inline void apply(InputCollection const& collection1,
+ InputCollection const& collection2,
+ VisitPolicy& visitor,
+ int min_elements = 16,
+ VisitBoxPolicy box_visitor = visit_no_policy()
+ )
{
if (boost::size(collection1) > min_elements && boost::size(collection2) > min_elements)
{
@@ -331,13 +357,13 @@
expand_to_collection(collection1, total, index_vector1);
expand_to_collection(collection2, total, index_vector2);
- detail::partition_two_collections
+ detail::partition::partition_two_collections
<
- 0, Box, OverlapsPolicy
+ 0, Box, OverlapsPolicy, VisitBoxPolicy
>::apply(total,
collection1, index_vector1,
collection2, index_vector2,
- 0, min_elements, visitor);
+ 0, min_elements, visitor, box_visitor);
}
else
{
Modified: trunk/boost/geometry/algorithms/detail/sections/sectionalize.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/sections/sectionalize.hpp (original)
+++ trunk/boost/geometry/algorithms/detail/sections/sectionalize.hpp 2011-03-19 10:01:11 EDT (Sat, 19 Mar 2011)
@@ -607,7 +607,7 @@
\tparam Sections type of sections to create
\param geometry geometry to create sections from
\param sections structure with sections
-
+ \param source_index index to assign to the ring_identifiers
*/
template<bool Reverse, typename Geometry, typename Sections>
inline void sectionalize(Geometry const& geometry, Sections& sections, int source_index = 0)
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk