Subject: [Boost-commit] svn:boost r71640 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-04-30 20:42:55
Author: awulkiew
Date: 2011-04-30 20:42:54 EDT (Sat, 30 Apr 2011)
New Revision: 71640
URL: http://svn.boost.org/trac/boost/changeset/71640
Log:
rtree::find parameters changed
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp | 14 +++++----
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp | 6 ++--
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 9 +++--
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp | 56 +++++++++++++++++++++++++++++++++++----
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 3 +
5 files changed, 68 insertions(+), 20 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp 2011-04-30 20:42:54 EDT (Sat, 30 Apr 2011)
@@ -10,11 +10,13 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP
-#include <vector>
+#include <deque>
#include <boost/static_assert.hpp>
#include <boost/geometry/extensions/index/filters/spacial_filter.hpp>
-#include <boost/geometry/extensions/index/filters/nearest_filter.hpp>
+
+// TODO: awulkiew - implement nearest filter
+//#include <boost/geometry/extensions/index/filters/nearest_filter.hpp>
namespace boost { namespace geometry { namespace index {
@@ -27,13 +29,13 @@
class spatial_filter< index::rtree<Value, Translator, Tag> >
{
public:
- typedef typename std::vector<Value>::iterator iterator;
- typedef typename std::vector<Value>::const_iterator const_iterator;
+ typedef typename std::deque<Value>::iterator iterator;
+ typedef typename std::deque<Value>::const_iterator const_iterator;
template <typename Geometry>
spatial_filter(index::rtree<Value, Translator, Tag> const& rtree, Geometry const& geom)
{
- m_result = rtree.find(geom);
+ rtree.find(geom, std::back_inserter(m_result));
}
iterator begin() { return m_result.begin(); }
@@ -42,7 +44,7 @@
const_iterator end() const { return m_result.end(); }
private:
- std::vector<Value> m_result;
+ std::deque<Value> m_result;
};
} // namespace filters
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp 2011-04-30 20:42:54 EDT (Sat, 30 Apr 2011)
@@ -46,8 +46,8 @@
assert(2 <= elements_count);
// find the lowest low, highest high
- coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
- coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
+ coordinate_type lowest_low = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
+ coordinate_type highest_high = index::get<max_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
// and the lowest high
coordinate_type lowest_high = highest_high;
size_t lowest_high_index = 0;
@@ -71,7 +71,7 @@
// find the highest low
size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
- coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[highest_low_index], tr));
+ coordinate_type highest_low = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[highest_low_index], tr));
for ( size_t i = highest_low_index ; i < elements_count ; ++i )
{
coordinate_type min_coord = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[i], tr));
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-04-30 20:42:54 EDT (Sat, 30 Apr 2011)
@@ -70,12 +70,13 @@
boost::apply_visitor(del_v, *m_root);
}
- template <typename Geometry>
- inline std::deque<value_type> find(Geometry const& geom) const
+ // TODO: awulkiew - change name to query?
+
+ template <typename Geometry, typename OutIter>
+ inline void find(Geometry const& geom, OutIter out_it) const
{
- detail::rtree::visitors::find<value_type, translator_type, box_type, tag_type, Geometry> find_v(geom, m_translator);
+ detail::rtree::visitors::find<value_type, translator_type, box_type, tag_type, Geometry, OutIter> find_v(m_translator, geom, out_it);
boost::apply_visitor(find_v, *m_root);
- return find_v.result;
}
void insert(value_type const& value)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp 2011-04-30 20:42:54 EDT (Sat, 30 Apr 2011)
@@ -14,24 +14,65 @@
#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree { namespace visitors {
// rtree spatial query visitor
-template <typename Value, typename Translator, typename Box, typename Tag, typename Geometry>
+template <typename Value, typename Translator, typename Box, typename Tag, typename Geometry, typename OutIter>
struct find : public boost::static_visitor<>
{
+ typedef typename rtree::node<Value, Box, Tag>::type node;
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
- inline find(Geometry const& g, Translator const& t)
- : geom(g), tr(t)
+ inline find(Translator const& t, Geometry const& g, OutIter out_it)
+ : tr(t), geom(g), out_iter(out_it)
{}
inline void operator()(internal_node const& n)
{
+ /*typedef typename internal_node::children_type children_type;
+
+ std::deque<node*> nodes;
+
+ for (typename children_type::const_iterator it = n.children.begin();
+ it != n.children.end(); ++it)
+ {
+ if ( geometry::intersects(it->first, geom) )
+ {
+ nodes.push_back(it->second);
+ }
+ }
+
+ while ( !nodes.empty() )
+ {
+ node *n = nodes.back();
+ nodes.pop_back();
+
+ if ( !boost::apply_visitor(visitors::is_leaf<Value, Box, Tag>(), *n) )
+ {
+ internal_node &in = boost::get<internal_node>(*n);
+
+ for (typename children_type::const_iterator it = in.children.begin();
+ it != in.children.end(); ++it)
+ {
+ if ( geometry::intersects(it->first, geom) )
+ {
+ nodes.push_back(it->second);
+ }
+ }
+ }
+ else
+ {
+ operator()(boost::get<leaf>(*n));
+ }
+ }
+ */
+
typedef typename internal_node::children_type children_type;
for (typename children_type::const_iterator it = n.children.begin();
@@ -50,13 +91,16 @@
it != n.values.end(); ++it)
{
if ( geometry::intersects(tr(*it), geom) )
- result.push_back(*it);
+ {
+ out_iter = *it;
+ ++out_iter;
+ }
}
}
- Geometry const& geom;
Translator const& tr;
- std::deque<Value> result;
+ Geometry const& geom;
+ OutIter out_iter;
};
}}} // namespace detail::rtree::visitors
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-04-30 20:42:54 EDT (Sat, 30 Apr 2011)
@@ -95,7 +95,8 @@
{
float x = coords[i].first;
float y = coords[i].second;
- std::deque< std::pair<B, size_t> > result = t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)));
+ std::deque< std::pair<B, size_t> > result;
+ t.find(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";