[Boost-commit] svn:boost r70627 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar tests

Subject: [Boost-commit] svn:boost r70627 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-03-27 09:44:56

Author: awulkiew
Date: 2011-03-27 09:44:55 EDT (Sun, 27 Mar 2011)
New Revision: 70627
URL: http://svn.boost.org/trac/boost/changeset/70627

Log:
overlap error patch + minor changes
Text files modified: 
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp |     1                                         
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp  |    15 +++++++++----                           
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp        |     5 ++++                                    
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp   |    15 ++++++-------                           
   sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp                   |    43 ++++++++++++++++++++++++++------------- 
   5 files changed, 51 insertions(+), 28 deletions(-)

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp	2011-03-27 09:44:55 EDT (Sun, 27 Mar 2011)
@@ -25,6 +25,7 @@
 typename overlap_result<Box>::type overlap(Box const& b1, Box const& b2)
 {
     Box inters;
+    geometry::assign_zero(inters);
     geometry::intersection(b1, b2, inters);
     return index::area(inters);
 }

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp	2011-03-27 09:44:55 EDT (Sun, 27 Mar 2011)
@@ -124,8 +124,8 @@
         size_t median_index_last = max_elems - min_elems + 2;
         for ( size_t median_index = min_elems ; median_index < median_index_last ; ++median_index )
         {
-            Box left_box = index::detail::elements_box<Box>(sorted_elements.begin(), sorted_elements.begin() + median_index, tr);
-            Box right_box = index::detail::elements_box<Box>(sorted_elements.begin() + median_index, sorted_elements.end(), tr);
+            Box left_box = index::detail::rtree_elements_box<Box>(sorted_elements.begin(), sorted_elements.begin() + median_index, tr);
+            Box right_box = index::detail::rtree_elements_box<Box>(sorted_elements.begin() + median_index, sorted_elements.end(), tr);
 
             margin_type margin = index::margin(left_box) + index::margin(right_box);
             overlap_type overlap = index::overlap(left_box, right_box);
@@ -284,16 +284,21 @@
         typedef typename index::detail::rtree_elements_type<Node>::type elements_type;
         typedef typename elements_type::value_type element_type;
 
-        elements_type & elements = index::detail::get_elements(n);
+        elements_type & elements = index::detail::rtree_elements_get(n);
+
+        assert(elements.size() == max_elems + 1);
 
         // get split data
         rtree_rstar_split_data<elements_type, Box> split_data;
         rtree_rstar_split_update_data<Value, Translator, Box, dimension>::
             apply(split_data, elements, min_elems, max_elems, tr);
-        
+       
+        assert(min_elems <= split_data.choosen_median_index);
+        assert(split_data.choosen_median_index <= max_elems + 1 - min_elems);
+
         // create new node
         node * right_node = rtree_create_node(Node());
-        elements_type & new_elems = index::detail::get_elements(boost::get<Node>(*right_node));
+        elements_type & new_elems = index::detail::rtree_elements_get(boost::get<Node>(*right_node));
 
         // update new node's elements
         new_elems.resize(max_elems + 1 - split_data.choosen_median_index);

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp	2011-03-27 09:44:55 EDT (Sun, 27 Mar 2011)
@@ -91,6 +91,11 @@
         return  m_translator;
     }
 
+    size_t values_count() const
+    {
+        return m_values_count;
+    }
+
 private:
     size_t m_values_count;
     size_t m_max_elems_per_node;

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp	2011-03-27 09:44:55 EDT (Sun, 27 Mar 2011)
@@ -87,21 +87,22 @@
 };
 
 template <typename Node>
-typename rtree_elements_type<Node>::type & get_elements(Node & n)
+typename rtree_elements_type<Node>::type &
+rtree_elements_get(Node & n)
 {
     return n.elements;
 }
 
 template <typename Value, typename Box, typename Tag>
 typename rtree_internal_node_def<Value, Box, Tag>::children_type &
-get_elements(rtree_internal_node_def<Value, Box, Tag> & n)
+rtree_elements_get(rtree_internal_node_def<Value, Box, Tag> & n)
 {
     return n.children;
 }
 
 template <typename Value, typename Box, typename Tag>
 typename rtree_leaf_def<Value, Box, Tag>::values_type &
-get_elements(rtree_leaf_def<Value, Box, Tag> & n)
+rtree_elements_get(rtree_leaf_def<Value, Box, Tag> & n)
 {
     return n.values;
 }
@@ -156,7 +157,7 @@
 // elements box
 
 template <typename Box, typename FwdIter, typename Translator>
-inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr)
+inline Box rtree_elements_box(FwdIter first, FwdIter last, Translator const& tr)
 {
     assert(first != last);
 
@@ -178,8 +179,7 @@
 rtree_create_node(rtree_leaf_def<Value, Box, Tag> const& l)
 {
     typedef typename rtree_node<Value, Box, Tag>::type node;
-    node * n = new node();
-    *n = l;
+    node * n = new node(l);
     return n;
 }
 
@@ -190,8 +190,7 @@
 rtree_create_node(rtree_internal_node_def<Value, Box, Tag> const& in)
 {
     typedef typename rtree_node<Value, Box, Tag>::type node;
-    node * n = new node();
-    *n = in;
+    node * n = new node(in);
     return n;
 }
 

Modified: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp	(original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp	2011-03-27 09:44:55 EDT (Sun, 27 Mar 2011)
@@ -1,10 +1,21 @@
 #include <boost/geometry/extensions/index/rtree/rtree.hpp>
 
 #include <iostream>
+#include <fstream>
 
 #include <boost/timer.hpp>
 #include <boost/foreach.hpp>
 
+template <typename Box>
+void print(Box const& b)
+{
+    using namespace boost::geometry;
+    std::cout << boost::geometry::get<min_corner, 0>(b) << ", ";
+    std::cout << boost::geometry::get<min_corner, 1>(b) << " x ";
+    std::cout << boost::geometry::get<max_corner, 0>(b) << ", ";
+    std::cout << boost::geometry::get<max_corner, 1>(b)<< std::endl;
+}
+
 int main()
 {
     {
@@ -20,30 +31,31 @@
 
     boost::timer tim;
 
-    {
-        typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
-        typedef boost::geometry::model::box<P> B;
+    typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+    typedef boost::geometry::model::box<P> B;
 
-        // randomize boxes
-        const size_t n = 10000;
-        std::vector<B> v(n);
-        for ( size_t i = 0 ; i < n ; ++i )
-        {
-            float x = float( rand() % 1000 );
-            float y = float( rand() % 1000 );
-            float w = float( rand() % 10 ) / 10.0f;
-            float h = float( rand() % 10 ) / 10.0f;
-            v[i] = B(P(x - w, y - h),P(x + w, y + h));
-        }
+    // randomize boxes
+    const size_t n = 10000;
+    std::vector<B> v(n);
+    for ( size_t i = 0 ; i < n ; ++i )
+    {
+        float x = float( rand() % 1000 );
+        float y = float( rand() % 1000 );
+        float w = float( rand() % 10 ) / 10.0f;
+        float h = float( rand() % 10 ) / 10.0f;
+        v[i] = B(P(x - w, y - h),P(x + w, y + h));
+    }
 
+    {
         boost::geometry::index::rtree<B> t(4, 2);
 
         std::cout << "inserting time test...\n";
 
         tim.restart();    
 
-        BOOST_FOREACH(B &b, v)
+        for (size_t i = 0 ; i < n ; ++i )
         {
+            B const& b = v[i];
             boost::geometry::index::insert(t, b);
         }
 
@@ -52,6 +64,7 @@
         std::cout << "deleting time test...\n";
         tim.restart();
     }
+
     std::cout << "time: " << tim.elapsed() << "s\n";
 
 #ifdef _MSC_VER