[Boost-commit] svn:boost r69942 - trunk/boost/geometry/algorithms/detail

Subject: [Boost-commit] svn:boost r69942 - trunk/boost/geometry/algorithms/detail
From: barend.gehrels_at_[hidden]
Date: 2011-03-13 10:43:20

Author: barendgehrels
Date: 2011-03-13 10:43:17 EDT (Sun, 13 Mar 2011)
New Revision: 69942
URL: http://svn.boost.org/trac/boost/changeset/69942

Log:
Implemented partition for two ranges
Text files modified: 
   trunk/boost/geometry/algorithms/detail/partition.hpp |   272 +++++++++++++++++++++++++++++---------- 
   1 files changed, 201 insertions(+), 71 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-13 10:43:17 EDT (Sun, 13 Mar 2011)
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 //
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Copyright Barend Gehrels 2011, Geodan, Amsterdam, the Netherlands.
 // Use, modification and distribution is subject to the Boost Software License,
 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
@@ -19,57 +19,120 @@
 namespace detail
 {
 
+template <int Dimension, typename Box>
+inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
+{
+    typedef typename coordinate_type<Box>::type ctype;
+
+    // Divide input box into two parts, e.g. left/right
+    ctype two = 2;
+    ctype mid = (geometry::get<min_corner, Dimension>(box)
+            + geometry::get<max_corner, Dimension>(box)) / two;
+
+    lower_box = box;
+    upper_box = box;
+    geometry::set<max_corner, Dimension>(lower_box, mid);
+    geometry::set<min_corner, Dimension>(upper_box, mid);
+}
+
 template
 <
-    int Dimension,
     typename Box,
     typename OverlapsPolicy
 >
-class partition
+class partition_generic
 {
-    typedef typename coordinate_type<Box>::type ctype;
     typedef std::vector<std::size_t> index_vector_type;
+protected :
     typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
-    typedef partition
-            <
-                1 - Dimension,
-                Box,
-                OverlapsPolicy
-            > sub_divide;
 
+    // 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)
+        {
+            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);
+            }
+        }
+    }
+
+    // Match collection 1 with collection 2
     template <typename InputCollection, typename Policy>
-    static inline void handle(InputCollection const& collection,
+    static inline void handle_one(InputCollection const& collection,
             index_vector_type const& input,
             Policy& policy)
     {
         // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
         for(index_iterator_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
         {
-            for(index_iterator_type it2 = boost::begin(input); it2 != boost::end(input); ++it2)
+            index_iterator_type it2 = it1;
+            for(++it2; it2 != boost::end(input); ++it2)
             {
                 policy.apply(collection[*it1], collection[*it2]);
             }
         }
     }
 
+    // Match collection 1 with collection 2
     template <typename InputCollection, typename Policy>
-    static inline void handle_exceeding(InputCollection const& collection,
-            index_vector_type const& exceeding,
-            index_vector_type const& input,
+    static inline void handle_two(
+            InputCollection const& collection1, index_vector_type const& input1,
+            InputCollection const& collection2, index_vector_type const& input2,
             Policy& policy)
     {
-        if (boost::size(input) > 0)
+        for(index_iterator_type it1 = boost::begin(input1); it1 != boost::end(input1); ++it1)
         {
-            for(index_iterator_type it1 = boost::begin(exceeding); it1 != boost::end(exceeding); ++it1)
+            for(index_iterator_type it2 = boost::begin(input2); it2 != boost::end(input2); ++it2)
             {
-                for(index_iterator_type it2 = boost::begin(input); it2 != boost::end(input); ++it2)
-                {
-                    policy.apply(collection[*it1], collection[*it2]);
-                }
+                policy.apply(collection1[*it1], collection2[*it2]);
             }
         }
     }
+};
+
+
+
+template
+<
+    int Dimension,
+    typename Box,
+    typename OverlapsPolicy
+>
+class partition_one_collection : public partition_generic<Box, OverlapsPolicy>
+{
+    typedef std::vector<std::size_t> index_vector_type;
+    typedef typename coordinate_type<Box>::type ctype;
+    typedef partition_one_collection
+            <
+                1 - Dimension,
+                Box,
+                OverlapsPolicy
+            > sub_divide;
 
     template <typename InputCollection, typename Policy>
     static inline void next_level(Box const& box,
@@ -86,7 +149,7 @@
             }
             else
             {
-                handle(collection, input, policy);
+                handle_one(collection, input, policy);
             }
         }
     }
@@ -100,62 +163,106 @@
             int min_elements,
             Policy& policy)
     {
-        typedef typename boost::range_value<InputCollection>::type item_type;
-
-        // Divide input box into two parts, e.g. left/right
-        ctype two = 2;
-        ctype mid = (geometry::get<min_corner, Dimension>(box)
-                + geometry::get<max_corner, Dimension>(box)) / two;
-
-        Box lower_box = box, upper_box = box;
-        geometry::set<max_corner, Dimension>(lower_box, mid);
-        geometry::set<min_corner, Dimension>(upper_box, mid);
+        Box lower_box, upper_box;
+        divide_box<Dimension>(box, lower_box, upper_box);
 
-        // Divide collection into three subsets: lower, upper and oversized (not-fitting)
-        // (lower == left or bottom, upper == right or top)
         index_vector_type lower, upper, exceeding;
-        for(index_iterator_type it = boost::begin(input);
-            it != boost::end(input);
-            ++it)
+        divide_into_subsets(lower_box, upper_box, collection, input, lower, upper, exceeding);
+
+        if (boost::size(exceeding) > 0)
         {
-            bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
-            bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);
+            // All what is not fitting a partition should be combined
+            // with each other, and with all which is fitting.
+            handle_one(collection, exceeding, policy);
+            handle_two(collection, exceeding, collection, lower, policy);
+            handle_two(collection, exceeding, collection, upper, policy);
+        }
 
-            if (lower_overlapping && upper_overlapping)
-            {
-                exceeding.push_back(*it);
-            }
-            else if (lower_overlapping)
-            {
-                lower.push_back(*it);
-            }
-            else if (upper_overlapping)
+        // 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);
+    }
+};
+
+
+template
+<
+    int Dimension,
+    typename Box,
+    typename OverlapsPolicy
+>
+class partition_two_collections : public partition_generic<Box, OverlapsPolicy>
+{
+    typedef std::vector<std::size_t> index_vector_type;
+    typedef typename coordinate_type<Box>::type ctype;
+    typedef partition_two_collections
+            <
+                1 - Dimension,
+                Box,
+                OverlapsPolicy
+            > sub_divide;
+
+    template <typename InputCollection, typename Policy>
+    static inline void next_level(Box const& box,
+            InputCollection const& collection1, index_vector_type const& input1,
+            InputCollection const& collection2, index_vector_type const& input2,
+            int level, int min_elements,
+            Policy& policy)
+    {
+        if (boost::size(input1) > 0 && boost::size(input2) > 0)
+        {
+            if (boost::size(input1) > min_elements 
+                && boost::size(input2) > min_elements 
+                && level < 100)
             {
-                upper.push_back(*it);
+                sub_divide::apply(box, collection1, input1, collection2, input2, level + 1, min_elements, policy);
             }
             else
             {
-                // Is nowhere! Should not occur!
-                BOOST_ASSERT(true);
+                handle_two(collection1, input1, collection2, input2, policy);
             }
         }
+    }
 
-        if (boost::size(exceeding) > 0)
+public :
+    template <typename InputCollection, typename Policy>
+    static inline void apply(Box const& box,
+            InputCollection const& collection1, index_vector_type const& input1,
+            InputCollection const& collection2, index_vector_type const& input2,
+            int level,
+            int min_elements,
+            Policy& policy)
+    {
+        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);
+
+        if (boost::size(exceeding1) > 0)
         {
-            // All what is not fitting a partition should be combined
-            // with each other, and with all which is fitting.
-            handle(collection, exceeding, policy);
-            handle_exceeding(collection, exceeding, lower, policy);
-            handle_exceeding(collection, exceeding, upper, policy);
+            // All exceeding from 1 with 2:
+            handle_two(collection1, exceeding1, collection2, exceeding2, policy);
+
+            // All exceeding from 1 with lower and upper of 2:
+            handle_two(collection1, exceeding1, collection2, lower2, policy);
+            handle_two(collection1, exceeding1, collection2, upper2, policy);
+        }
+        if (boost::size(exceeding2) > 0)
+        {
+            // All exceeding from 2 with lower and upper of 1:
+            handle_two(collection1, lower1, collection2, exceeding2, policy);
+            handle_two(collection1, upper1, collection2, exceeding2, policy);
         }
 
-        // Recursively call operation both halves
-        next_level(lower_box, collection, lower, level, min_elements, policy);
-        next_level(upper_box, collection, upper, level, min_elements, 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);
     }
 };
 
-}
+} // namespace detail
 
 
 template
@@ -168,15 +275,9 @@
 {
     typedef std::vector<std::size_t> index_vector_type;
 
-public :
-    template <typename InputCollection, typename Visitor>
-    static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
+    template <typename InputCollection>
+    static inline void expand_to_collection(InputCollection const& collection, Box& total, index_vector_type& index_vector)
     {
-        index_vector_type index_vector;
-
-        // Determine total box
-        Box total;
-        assign_inverse(total);
         std::size_t index = 0;
         for(typename boost::range_iterator<InputCollection const>::type it
             = boost::begin(collection);
@@ -186,13 +287,42 @@
             ExpandPolicy::apply(total, *it);
             index_vector.push_back(index);
         }
+    }
 
-        // Start recursion
-        detail::partition
+
+public :
+    template <typename InputCollection, typename Visitor>
+    static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
+    {
+        index_vector_type index_vector;
+        Box total;
+        assign_inverse(total);
+        expand_to_collection(collection, total, index_vector);
+
+        detail::partition_one_collection
             <
                 0, Box, OverlapsPolicy
             >::apply(total, collection, index_vector, 0, min_elements, visitor);
     }
+
+    template <typename InputCollection, typename Visitor>
+    static inline void apply(InputCollection const& collection1, InputCollection const& collection2, Visitor& visitor, int min_elements = 16)
+    {
+        index_vector_type index_vector1, index_vector2;
+        Box total;
+        assign_inverse(total);
+        expand_to_collection(collection1, total, index_vector1);
+        expand_to_collection(collection2, total, index_vector2);
+
+        detail::partition_two_collections
+            <
+                0, Box, OverlapsPolicy
+            >::apply(total, 
+                collection1, index_vector1, 
+                collection2, index_vector2, 
+                0, min_elements, visitor);
+    }
+
 };