[Boost-commit] svn:boost r84667 - trunk/boost/geometry/index/detail/rtree/linear

Subject: [Boost-commit] svn:boost r84667 - trunk/boost/geometry/index/detail/rtree/linear
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-06 21:29:19

Author: awulkiew
Date: 2013-06-06 21:29:19 EDT (Thu, 06 Jun 2013)
New Revision: 84667
URL: http://svn.boost.org/trac/boost/changeset/84667

Log:
geometry.index: handled floating point types comparison and unsigned types difference calculation in linear/redistribute_elements.

Text files modified: 
   trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp |    69 ++++++++++++++++++++++++++++----------- 
   1 files changed, 50 insertions(+), 19 deletions(-)

Modified: trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp	Thu Jun  6 21:04:48 2013	(r84666)
+++ trunk/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp	2013-06-06 21:29:19 EDT (Thu, 06 Jun 2013)	(r84667)
@@ -32,8 +32,8 @@
 
 // TODO: Implement separate version for Points
 
-// What if width calculated inside find_greatest_normalized_separation::apply() is near 0?
-// What epsilon should be taken to calculation and what would be the value of resulting separation?
+// [DONE] What if width calculated inside find_greatest_normalized_separation::apply() is near 0?
+// [DONE] What epsilon should be taken to calculation and what would be the value of resulting separation?
 
 // from void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
 
@@ -44,10 +44,20 @@
     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
     typedef typename index::detail::traits::coordinate_type<indexable_type>::type coordinate_type;
 
+    typedef typename boost::mpl::if_c<
+        boost::is_integral<coordinate_type>::value,
+        double,
+        coordinate_type
+    >::type separation_type;
+
+    typedef ::boost::mpl::bool_<
+        boost::is_unsigned<coordinate_type>::value
+    > is_coordinate_type_unsigned;
+
     static inline void apply(Elements const& elements,
                              Parameters const& parameters,
                              Translator const& translator,
-                             coordinate_type & separation,
+                             separation_type & separation,
                              size_t & seed1,
                              size_t & seed2)
     {
@@ -96,24 +106,36 @@
         coordinate_type const width = highest_high - lowest_low;
 
         // TODO: awulkiew - following separation calculation has two flaws:
-        // 1. for floating point numbers width should be compared witn some EPS
-        // 2. separation calculation won't work for unsigned numbers
+        // 1. [DONE] for floating point numbers width should be compared witn some EPS
+        // 2. [DONE] separation calculation won't work for unsigned numbers
         //    but there should be possible to calculate negative value (cast to some floating point type?)
 
-        // Temporary workaround
-        BOOST_STATIC_ASSERT(!boost::is_unsigned<coordinate_type>::value);
-
-        if ( width == 0 )
-            separation = 0;
-            // (highest_low - lowest_high) == 0
-        else
-            separation = (highest_low - lowest_high) / width;
+        separation = difference(highest_low, lowest_high, is_coordinate_type_unsigned());
+        // BOOST_ASSERT(0 <= width);
+        if ( std::numeric_limits<coordinate_type>::epsilon() < width )
+            separation /= width;
 
         seed1 = highest_low_index;
         seed2 = lowest_high_index;
 
         BOOST_GEOMETRY_INDEX_DETAIL_USE_PARAM(parameters)
     }
+
+    static inline separation_type difference(coordinate_type const& highest_low,
+                                             coordinate_type const& lowest_high,
+                                             ::boost::mpl::bool_<false> const& /*is_unsigned*/)
+    {
+        return (highest_low - lowest_high);
+    }
+
+    static inline separation_type difference(coordinate_type const& highest_low,
+                                             coordinate_type const& lowest_high,
+                                             ::boost::mpl::bool_<true> const& /*is_unsigned*/)
+    {
+        return lowest_high <= highest_low ?
+            separation_type(highest_low - lowest_high) :
+            -separation_type(lowest_high - highest_low);
+    }
 };
 
 template <typename Elements, typename Parameters, typename Translator, size_t Dimension>
@@ -125,18 +147,21 @@
     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
     typedef typename index::detail::traits::coordinate_type<indexable_type>::type coordinate_type;
 
+    typedef find_greatest_normalized_separation<Elements, Parameters, Translator, Dimension - 1> find_norm_sep;
+    typedef typename find_norm_sep::separation_type separation_type;
+
     static inline void apply(Elements const& elements,
                              Parameters const& parameters,
                              Translator const& tr,
-                             coordinate_type & separation,
+                             separation_type & separation,
                              size_t & seed1,
                              size_t & seed2)
     {
         pick_seeds_impl<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, separation, seed1, seed2);
 
-        coordinate_type current_separation;
+        separation_type current_separation;
         size_t s1, s2;
-        find_greatest_normalized_separation<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, current_separation, s1, s2);
+        find_norm_sep::apply(elements, parameters, tr, current_separation, s1, s2);
 
         // in the old implementation different operator was used: <= (y axis prefered)
         if ( separation < current_separation )
@@ -155,14 +180,17 @@
     typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
     typedef typename index::detail::traits::coordinate_type<indexable_type>::type coordinate_type;
 
+    typedef find_greatest_normalized_separation<Elements, Parameters, Translator, 0> find_norm_sep;
+    typedef typename find_norm_sep::separation_type separation_type;
+
     static inline void apply(Elements const& elements,
                              Parameters const& parameters,
                              Translator const& tr,
-                             coordinate_type & separation,
+                             separation_type & separation,
                              size_t & seed1,
                              size_t & seed2)
     {
-        find_greatest_normalized_separation<Elements, Parameters, Translator, 0>::apply(elements, parameters, tr, separation, seed1, seed2);
+        find_norm_sep::apply(elements, parameters, tr, separation, seed1, seed2);
     }
 };
 
@@ -177,13 +205,16 @@
 
     static const size_t dimension = index::detail::traits::dimension<indexable_type>::value;
 
+    typedef pick_seeds_impl<Elements, Parameters, Translator, dimension> impl;
+    typedef typename impl::separation_type separation_type;
+
     static inline void apply(Elements const& elements,
                              Parameters const& parameters,
                              Translator const& tr,
                              size_t & seed1,
                              size_t & seed2)
     {
-        coordinate_type separation = 0;
+        separation_type separation = 0;
         pick_seeds_impl<Elements, Parameters, Translator, dimension>::apply(elements, parameters, tr, separation, seed1, seed2);
     }
 };