[Boost-commit] svn:boost r71763 - in sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree: linear quadratic

Subject: [Boost-commit] svn:boost r71763 - in sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree: linear quadratic
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-06 09:36:37

Author: awulkiew
Date: 2011-05-06 09:36:37 EDT (Fri, 06 May 2011)
New Revision: 71763
URL: http://svn.boost.org/trac/boost/changeset/71763

Log:
quadratic split error corrected
Text files modified: 
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp    |    30 ++++++++++++------------------          
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp |    34 +++++++++++++++++++---------------      
   2 files changed, 31 insertions(+), 33 deletions(-)

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp	2011-05-06 09:36:37 EDT (Fri, 06 May 2011)
@@ -231,17 +231,20 @@
             {
                 element_type const& elem = elements_copy[i];
                 indexable_type const& indexable = rtree::element_indexable(elem, tr);
-                bool insert_into_group1 = false;
 
                 // if there is small number of elements left and the number of elements in node is lesser than min_elems
                 // just insert them to this node
                 if ( elements1.size() + remaining <= min_elems )
                 {
-                    insert_into_group1 = true;
+                    elements1.push_back(elem);
+                    geometry::expand(box1, indexable);
+                    area1 = index::area(box1);
                 }
                 else if ( elements2.size() + remaining <= min_elems )
                 {
-                    insert_into_group1 = false;
+                    elements2.push_back(elem);
+                    geometry::expand(box2, indexable);
+                    area2 = index::area(box2);
                 }
                 // choose better node and insert element
                 else
@@ -262,26 +265,17 @@
                          ( area_increase1 == area_increase2 && area1 < area2 ) ||
                          ( area1 == area2 && elements1.size() <= elements2.size() ) )
                     {
-                        insert_into_group1 = true;
+                        elements1.push_back(elem);
+                        box1 = enlarged_box1;
+                        area1 = enlarged_area1;
                     }
                     else
                     {
-                        insert_into_group1 = false;
+                        elements2.push_back(elem);
+                        box2 = enlarged_box2;
+                        area2 = enlarged_area2;
                     }
                 }
-
-                if ( insert_into_group1 )
-                {
-                    elements1.push_back(elem);
-                    geometry::expand(box1, indexable);
-                    area1 = index::area(box1);
-                }
-                else
-                {
-                    elements2.push_back(elem);
-                    geometry::expand(box2, indexable);
-                    area2 = index::area(box2);
-                }
                 
                 assert(0 < remaining);
                 --remaining;

Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp	(original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp	2011-05-06 09:36:37 EDT (Fri, 06 May 2011)
@@ -47,10 +47,11 @@
 
         assert(2 <= elements_count);
 
+        area_type greatest_free_area = 0;
         seed1 = 0;
         seed2 = 1;
-        area_type greatest_free_area = 0;
-        for ( size_t i = 0 ; i < elements_count ; ++i )
+
+        for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
         {
             for ( size_t j = i + 1 ; j < elements_count ; ++j )
             {
@@ -164,9 +165,9 @@
                 // find element with minimum groups areas increses differences
                 area_type area_increase1 = 0;
                 area_type area_increase2 = 0;
-                pick_next(elements_copy.rbegin(), elements_copy.rend(),
-                          box1, box2, area1, area2, tr,
-                          el_it, area_increase1, area_increase2);
+                el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
+                                  box1, box2, area1, area2, tr,
+                                  area_increase1, area_increase2);
 
                 if ( area_increase1 < area_increase2 ||
                      ( area_increase1 == area_increase2 && area1 < area2 ) ||
@@ -198,7 +199,7 @@
             }
 
             assert(!elements_copy.empty());
-            elements_copy.erase(elements_copy.begin() + elements_copy.size() - 1);
+            elements_copy.erase(--el_it.base());
 
             assert(0 < remaining);
             --remaining;
@@ -208,21 +209,24 @@
         assert(min_elems <= elements2.size() && elements2.size() <= max_elems);
     }
 
+    // sprawdzic szukanie najmniejszego powiekszenia wezla dla grupy1 i grupy2
+
     template <typename It>
-    static inline void pick_next(It first, It last,
-                                 Box const& box1, Box const& box2,
-                                 area_type const& area1, area_type const& area2,
-                                 Translator const& tr,
-                                 It out_it, area_type & out_area_increase1, area_type & out_area_increase2)
+    static inline It pick_next(It first, It last,
+                               Box const& box1, Box const& box2,
+                               area_type const& area1, area_type const& area2,
+                               Translator const& tr,
+                               area_type & out_area_increase1, area_type & out_area_increase2)
     {
         typedef typename boost::iterator_value<It>::type element_type;
         typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
 
         area_type greatest_area_incrase_diff = 0;
-        out_it = first;
+        It out_it = first;
         out_area_increase1 = 0;
         out_area_increase2 = 0;
-
+        
+        // find element with greatest difference between increased group's boxes areas
         for ( It el_it = first ; el_it != last ; ++el_it )
         {
             indexable_type const& indexable = rtree::element_indexable(*el_it, tr);
@@ -248,9 +252,9 @@
                 out_area_increase1 = area_incrase1;
                 out_area_increase2 = area_incrase2;
             }
-
-            break;
         }
+
+        return out_it;
     }
 };