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

Subject: [Boost-commit] svn:boost r74608 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-29 07:48:13

Author: awulkiew
Date: 2011-09-29 07:48:13 EDT (Thu, 29 Sep 2011)
New Revision: 74608
URL: http://svn.boost.org/trac/boost/changeset/74608

Log:
k-nearest query optimized by use of heap instead of sorting.
Text files modified: 
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp |    37 +++++++++++++++++++++++--------------   
   sandbox-branches/geometry/index/tests/rtree_function.hpp                                   |    39 ++++++++++++++++++++++++++++++++++++++- 
   2 files changed, 61 insertions(+), 15 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp	(original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp	2011-09-29 07:48:13 EDT (Thu, 29 Sep 2011)
@@ -73,22 +73,30 @@
     inline explicit nearest_k(size_t k)
         : m_count(k)
     {
-        // TEMP?
-        m_neighbors.reserve(m_count + 1);
+        BOOST_GEOMETRY_INDEX_ASSERT(0 < m_count, "Number of neighbors should be greater than 0");
+
+        m_neighbors.reserve(m_count);
     }
 
     inline void store(Value const& val, distance_type const& curr_comp_dist)
     {
-        m_neighbors.push_back(std::make_pair(curr_comp_dist, val));
-        std::sort(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
-
-        if ( m_count < m_neighbors.size() )
-            m_neighbors.pop_back();
+        if ( m_neighbors.size() < m_count )
+        {
+            m_neighbors.push_back(std::make_pair(curr_comp_dist, val));
 
-        // TODO: awulkiew - test other methods:
-        // heap, manual inserting
-        // don't sort if size < k ?
-        // check the furthest distance at the first place, before push_back()
+            if ( m_neighbors.size() == m_count )
+                std::make_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+        }
+        else
+        {
+            if ( curr_comp_dist < m_neighbors.front().first )
+            {
+                std::pop_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+                m_neighbors.back().first = curr_comp_dist;
+                m_neighbors.back().second = val;
+                std::push_heap(m_neighbors.begin(), m_neighbors.end(), neighbors_less);
+            }
+        }
     }
 
     inline bool is_comparable_distance_valid() const
@@ -98,9 +106,9 @@
 
     inline distance_type comparable_distance() const
     {
-        return m_neighbors.size() < m_count ?
-            std::numeric_limits<distance_type>::max() :
-            m_neighbors.back().first;
+        return m_neighbors.size() < 0
+            ? std::numeric_limits<distance_type>::max()
+            : m_neighbors.front().first;
     }
 
     template <typename OutIter>
@@ -123,6 +131,7 @@
 
     size_t m_count;
     std::vector< std::pair<distance_type, Value> > m_neighbors;
+    distance_type m_biggest_comp_dist;
 };
 
 // TODO: awulkiew - add additional pruning before adding nodes to the ABL

Modified: sandbox-branches/geometry/index/tests/rtree_function.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/rtree_function.hpp	(original)
+++ sandbox-branches/geometry/index/tests/rtree_function.hpp	2011-09-29 07:48:13 EDT (Thu, 29 Sep 2011)
@@ -148,6 +148,43 @@
         return true;
     }
 
+    template <typename Point, typename Cont, typename Translator>
+    bool nearest_results_compare(Point const& p, Cont const& c1, Cont const& c2, Translator const& tr)
+    {
+        namespace bg = boost::geometry;
+        namespace bgi = boost::geometry::index;
+
+        typedef typename Translator::indexable_type indexable_type;
+        typedef bg::default_distance_result<Point, indexable_type>::type distance_type;
+
+        if ( c1.size() != c2.size() )
+            return false;
+
+        if ( c1.size() == 0 && c2.size() == 0 )
+            return true;
+
+        distance_type biggest_distance1 = 0;
+
+        for ( typename Cont::const_iterator it = c1.begin() ; it != c1.end() ; ++it )
+        {
+            distance_type curr_distance = bgi::comparable_distance_near(p, tr(*it));
+
+            if ( biggest_distance1 < curr_distance )
+                biggest_distance1 = curr_distance;
+        }
+
+        distance_type biggest_distance2 = 0;
+        for ( typename Cont::const_iterator it = c2.begin() ; it != c2.end() ; ++it )
+        {
+            distance_type curr_distance = bgi::comparable_distance_near(p, tr(*it));
+
+            if ( biggest_distance2 < curr_distance )
+                biggest_distance2 = curr_distance;
+        }
+
+        return biggest_distance1 == biggest_distance2;
+    }
+
     template <typename Predicate, typename Rtree, typename Cont, typename Randomizer>
     void random_query_check(Rtree const& t, Cont const& c, size_t n, Randomizer r)
     {
@@ -233,7 +270,7 @@
             std::stringstream ss;
             ss << "\nPredicate: " << typeid(Predicate).name() << "\nres1: " << res1.size() << ", res2: " << res2.size() << '\n';
 
-            BOOST_CHECK_MESSAGE( helpers::results_compare(res1, res2, t.get_translator()), ss.str());
+            BOOST_CHECK_MESSAGE(helpers::nearest_results_compare(pt, res1, res2, t.get_translator()), ss.str());
         }
     }
 }