Boost logo

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