[Boost-commit] svn:boost r82522 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests

Subject: [Boost-commit] svn:boost r82522 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2013-01-17 09:37:41

Author: awulkiew
Date: 2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
New Revision: 82522
URL: http://svn.boost.org/trac/boost/changeset/82522

Log:
root box calculation after remove moved from rtree::raw_remove() to visitor::remove.
Text files modified: 
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp           |    20 ++---------------                       
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp |    20 +++++++++++++++++                       
   sandbox-branches/geometry/index/tests/additional_speed.cpp                                |    45 ++++++++++++++++++++------------------- 
   3 files changed, 46 insertions(+), 39 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp	(original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp	2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
@@ -38,7 +38,6 @@
 #include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
 #include <boost/geometry/extensions/index/rtree/visitors/spatial_query.hpp>
 #include <boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp>
-#include <boost/geometry/extensions/index/rtree/visitors/children_box.hpp>
 #include <boost/geometry/extensions/index/rtree/visitors/count.hpp>
 
 #include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
@@ -1057,6 +1056,8 @@
         BOOST_GEOMETRY_INDEX_ASSERT(m_root, "The root must exist");
         BOOST_GEOMETRY_INDEX_ASSERT(index::is_valid(m_translator(value)), "Indexable is invalid");
 
+        geometry::expand(m_box, m_translator(value));
+
         detail::rtree::visitors::insert<
             value_type,
             value_type, options_type, translator_type, box_type, allocators_type,
@@ -1072,8 +1073,6 @@
 // TODO
 // If exception is thrown, m_values_count may be invalid
         ++m_values_count;
-
-        geometry::expand(m_box, m_translator(value));
     }
 
     /*!
@@ -1091,7 +1090,7 @@
 
         detail::rtree::visitors::remove<
             value_type, options_type, translator_type, box_type, allocators_type
-        > remove_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
+        > remove_v(m_root, m_leafs_level, m_box, value, m_parameters, m_translator, m_allocators);
 
         detail::rtree::apply_visitor(remove_v, *m_root);
 
@@ -1103,19 +1102,6 @@
 
             --m_values_count;
 
-            // Calculate new box
-            if ( m_values_count == 0 )
-            {
-                geometry::assign_inverse(m_box);
-            }
-            else
-            {
-                detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
-                    children_box_v(m_box, m_translator);
-
-                detail::rtree::apply_visitor(children_box_v, *m_root);
-            }
-
             return 1;
         }
 

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp	(original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp	2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
@@ -38,6 +38,7 @@
 public:
     inline remove(node* & root,
                   size_t & leafs_level,
+                  Box & root_box,
                   Value const& value,
                   parameters_type const& parameters,
                   Translator const& translator,
@@ -47,6 +48,7 @@
         , m_translator(translator)
         , m_allocators(allocators)
         , m_root_node(root)
+        , m_root_box(root_box)
         , m_leafs_level(leafs_level)
         , m_is_value_removed(false)
         , m_parent(0)
@@ -110,6 +112,9 @@
             {
                 BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
 
+                // assign new root's box
+                assign_root_box(elements);
+
                 // reinsert elements from removed nodes (underflows)
                 reinsert_removed_nodes_elements();                                                                  // MAY THROW (V, E: alloc, copy, N: alloc)
 
@@ -155,6 +160,10 @@
                 rtree::elements(*m_parent)[m_current_child_index].first
                     = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
             }
+            else
+            {
+               assign_root_box(elements);
+            }
         }
     }
 
@@ -285,13 +294,24 @@
         }
     }
 
+    template <typename Elements>
+    void assign_root_box(Elements const& elements)
+    {
+        if ( elements.empty() )
+            geometry::assign_inverse(m_root_box);
+        else
+            m_root_box = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
+    }    
+
     Value const& m_value;
     parameters_type const& m_parameters;
     Translator const& m_translator;
     Allocators & m_allocators;
 
     node* & m_root_node;
+    Box & m_root_box;
     size_t & m_leafs_level;
+
     bool m_is_value_removed;
     UnderflowNodes m_underflowed_nodes;
 

Modified: sandbox-branches/geometry/index/tests/additional_speed.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_speed.cpp	(original)
+++ sandbox-branches/geometry/index/tests/additional_speed.cpp	2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
@@ -71,8 +71,6 @@
 
         // inserting test
         {
-            std::cout << "rtree inserting time test... ("
-                << values_count << ")\n";
             tim.restart();
             for (size_t i = 0 ; i < values_count ; ++i )
             {
@@ -82,14 +80,8 @@
 
                 t.insert(b);
             }
-            std::cout << "time: " << tim.elapsed() << "s\n";
-        }
-
-        {
-            float x = coords[0].first;
-            float y = coords[0].second;
-            B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
-            t.remove(b);
+            double time = tim.elapsed();
+            std::cout << time << "s - insert " << values_count << '\n';
         }
 
         std::vector<B> result;
@@ -98,8 +90,6 @@
 
         // query test
         {
-            std::cout << "query(B) searching time test... ("
-                << queries_count << ")\n";
             tim.restart();    
             size_t temp = 0;
             for (size_t i = 0 ; i < queries_count ; ++i )
@@ -110,16 +100,14 @@
                 t.spatial_query(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
                 temp += result.size();
             }
-            std::cout << "time: " << tim.elapsed() << "s\n";
-            std::cout << "found: " << temp << "\n";
+            double time = tim.elapsed();
+            std::cout << time << "s - spatial_query(B) " << queries_count << " found " << temp << '\n';
         }
 
         result.clear();
 
         // searching test
         {
-            std::cout << "nearest 10 searching time test... ("
-                << queries_count / 10 << ")\n";
             tim.restart();    
             size_t temp = 0;
             for (size_t i = 0 ; i < queries_count / 10 ; ++i )
@@ -129,13 +117,11 @@
                 result.clear();
                 temp += t.nearest_query(P(x, y), 5, std::back_inserter(result));
             }
-            std::cout << "time: " << tim.elapsed() << "s\n";
-            std::cout << "found: " << temp << "\n";
+            double time = tim.elapsed();
+            std::cout << time << "s - nearest_query(P, 5) " << (queries_count / 10) << " found " << temp << '\n';
         }
 
         {
-            std::cout << "nearest 1 searching time test... ("
-                << queries_count / 10 << ")\n";
             tim.restart();    
             size_t temp = 0;
             for (size_t i = 0 ; i < queries_count / 10 ; ++i )
@@ -144,8 +130,23 @@
                 float y = coords[i].second + 100;
                 temp += t.nearest_query(P(x, y), result_one);
             }
-            std::cout << "time: " << tim.elapsed() << "s\n";
-            std::cout << "found: " << temp << "\n";
+            double time = tim.elapsed();
+            std::cout << time << "s - nearest_query(P) " << (queries_count / 10) << " found " << temp << '\n';
+        }
+
+        // inserting test
+        {
+            tim.restart();
+            for (size_t i = 0 ; i < values_count / 10 ; ++i )
+            {
+                float x = coords[i].first;
+                float y = coords[i].second;
+                B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+                t.remove(b);
+            }
+            double time = tim.elapsed();
+            std::cout << time << "s - remove " << values_count / 10 << '\n';
         }
     }