Subject: [Boost-commit] svn:boost r74082 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors boost/geometry/extensions/index/translator tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-08-26 20:05:56
Author: awulkiew
Date: 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
New Revision: 74082
URL: http://svn.boost.org/trac/boost/changeset/74082
Log:
predicates implemented, query() method added to the rtree + some cleanup.
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/intersection_content.hpp | 16 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/assert.hpp | 6
sandbox-branches/geometry/index/boost/geometry/extensions/index/indexable.hpp | 14 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp | 274 ++++++++++++++++++++--------------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp | 92 ++++++------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 24 ++-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 42 +++---
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp | 32 ++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp | 4
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 152 +++++++++++-----------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/print.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 10
sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/getter.hpp | 4
sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp | 16 +-
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 106 ++++++++++-----
sandbox-branches/geometry/index/tests/main.cpp | 2
18 files changed, 422 insertions(+), 378 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/intersection_content.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/intersection_content.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/intersection_content.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -21,14 +21,14 @@
template <typename Box>
inline typename default_content_result<Box>::type intersection_content(Box const& box1, Box const& box2)
{
- typename default_content_result<Box>::type result = 0;
- if ( geometry::intersects(box1, box2) )
- {
- Box box_intersection;
- geometry::intersection(box1, box2, box_intersection);
- result = index::content(box_intersection);
- }
- return result;
+ typename default_content_result<Box>::type result = 0;
+ if ( geometry::intersects(box1, box2) )
+ {
+ Box box_intersection;
+ geometry::intersection(box1, box2, box_intersection);
+ result = index::content(box_intersection);
+ }
+ return result;
}
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/assert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/assert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/assert.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -7,8 +7,8 @@
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef BOOST_GEOMETRY_EXTENSIONS_ASSERT_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_ASSERT_HPP
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ASSERT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ASSERT_HPP
#ifdef NDEBUG
@@ -24,4 +24,4 @@
#endif
-#endif // BOOST_GEOMETRY_EXTENSIONS_ASSERT_HPP
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ASSERT_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/indexable.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/indexable.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/indexable.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -162,13 +162,13 @@
template <typename Indexable>
struct default_box_type
{
- typedef geometry::model::box<
- geometry::model::point<
- typename traits::coordinate_type<Indexable>::type,
- traits::dimension<Indexable>::value,
- typename traits::coordinate_system<Indexable>::type
- >
- > type;
+ typedef geometry::model::box<
+ geometry::model::point<
+ typename traits::coordinate_type<Indexable>::type,
+ traits::dimension<Indexable>::value,
+ typename traits::coordinate_system<Indexable>::type
+ >
+ > type;
};
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -14,7 +14,7 @@
class nonassignable
{
- nonassignable & operator=(nonassignable const&);
+ nonassignable & operator=(nonassignable const&);
};
}}} // namespace boost::geometry::index
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -0,0 +1,217 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - Spatial index query predicates
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_PREDICATES_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_PREDICATES_HPP
+
+#include <utility>
+#include <boost/tuple/tuple.hpp>
+#include <boost/mpl/assert.hpp>
+
+// TODO: awulkiew - temporary
+#include <boost/geometry/algorithms/covered_by.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+// predicates
+
+namespace detail {
+
+template <typename Geometry>
+struct covered_by
+{
+ covered_by(Geometry const& g) : geometry(g) {}
+ Geometry const& geometry;
+};
+
+template <typename Geometry>
+struct intersects
+{
+ intersects(Geometry const& g) : geometry(g) {}
+ Geometry const& geometry;
+};
+
+template <typename Geometry>
+struct overlaps
+{
+ overlaps(Geometry const& g) : geometry(g) {}
+ Geometry const& geometry;
+};
+
+template <typename Geometry>
+struct within
+{
+ within(Geometry const& g) : geometry(g) {}
+ Geometry const& geometry;
+};
+
+} // namespace detail
+
+template <typename Geometry>
+inline detail::covered_by<Geometry> covered_by(Geometry const& g)
+{
+ return detail::covered_by<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::intersects<Geometry> intersects(Geometry const& g)
+{
+ return detail::intersects<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::overlaps<Geometry> overlaps(Geometry const& g)
+{
+ return detail::overlaps<Geometry>(g);
+}
+
+template <typename Geometry>
+inline detail::within<Geometry> within(Geometry const& g)
+{
+ return detail::within<Geometry>(g);
+}
+
+// predicates checks
+
+namespace detail
+{
+
+template <typename Geometry, typename Tag>
+struct predicate_check
+{
+ template <typename Indexable>
+ static inline bool apply(Geometry const& g, Indexable const& i)
+ {
+ return geometry::intersects(i, g);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<covered_by<Geometry>, Tag>
+{
+ template <typename Indexable>
+ static inline bool apply(covered_by<Geometry> const& p, Indexable const& i)
+ {
+ return geometry::covered_by(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<intersects<Geometry>, Tag>
+{
+ template <typename Indexable>
+ static inline bool apply(intersects<Geometry> const& p, Indexable const& i)
+ {
+ return geometry::intersects(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<overlaps<Geometry>, Tag>
+{
+ template <typename Indexable>
+ static inline bool apply(overlaps<Geometry> const& p, Indexable const& i)
+ {
+ return geometry::overlaps(i, p.geometry);
+ }
+};
+
+template <typename Geometry, typename Tag>
+struct predicate_check<within<Geometry>, Tag>
+{
+ template <typename Indexable>
+ static inline bool apply(within<Geometry> const& p, Indexable const& i)
+ {
+ return geometry::within(i, p.geometry);
+ }
+};
+
+template <typename TuplePredicates, typename Tag, unsigned int N>
+struct predicates_check_tuple
+{
+ template <typename Indexable>
+ static inline bool apply(TuplePredicates const& p, Indexable const& i)
+ {
+ return predicates_check_tuple<TuplePredicates, Tag, N - 1>::apply(p, i)
+ && predicate_check<
+ typename boost::tuples::element<N - 1, TuplePredicates>::type,
+ Tag
+ >::apply(boost::get<N - 1>(p), i);
+ }
+};
+
+template <typename TuplePredicates, typename Tag>
+struct predicates_check_tuple<TuplePredicates, Tag, 0>
+{
+ template <typename Indexable>
+ static inline bool apply(TuplePredicates const& p, Indexable const& i)
+ {
+ return predicate_check<
+ typename boost::tuples::element<0, TuplePredicates>::type,
+ Tag
+ >::apply(boost::get<0>(p), i);
+ }
+};
+
+template <typename Predicate, typename Tag>
+struct predicates_check
+{
+ template <typename Indexable>
+ static inline bool apply(Predicate const& p, Indexable const& i)
+ {
+ return predicate_check<Predicate, Tag>::apply(p, i);
+ }
+};
+
+template <typename Predicate1, typename Predicate2, typename Tag>
+struct predicates_check<std::pair<Predicate1, Predicate2>, Tag>
+{
+ template <typename Indexable>
+ static inline bool apply(std::pair<Predicate1, Predicate2> const& p, Indexable const& i)
+ {
+ return predicate_check<Predicate1, Tag>::apply(p.first, i)
+ && predicate_check<Predicate2, Tag>::apply(p.second, i);
+ }
+};
+
+template <
+ typename T0, typename T1, typename T2, typename T3, typename T4,
+ typename T5, typename T6, typename T7, typename T8, typename T9,
+ typename Tag
+>
+struct predicates_check<
+ boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>,
+ Tag
+>
+{
+ typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> predicates_type;
+
+ template <typename Indexable>
+ static inline bool apply(predicates_type const& p, Indexable const& i)
+ {
+ return predicates_check_tuple<
+ predicates_type,
+ Tag,
+ boost::tuples::length<predicates_type>::value
+ >::apply(p, i);
+ }
+};
+
+} // namespace detail
+
+template <typename Tag, typename Predicates, typename Indexable>
+inline bool predicates_check(Predicates const& p, Indexable const& i)
+{
+ return detail::predicates_check<Predicates, Tag>
+ ::apply(p, i);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_PREDICATES_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -19,146 +19,146 @@
template <typename Element, size_t Capacity>
class pushable_array
{
- typedef typename boost::array<Element, Capacity> array_type;
+ typedef typename boost::array<Element, Capacity> array_type;
public:
- typedef typename array_type::value_type value_type;
- typedef typename array_type::size_type size_type;
- typedef typename array_type::iterator iterator;
- typedef typename array_type::const_iterator const_iterator;
- typedef typename array_type::reverse_iterator reverse_iterator;
- typedef typename array_type::const_reverse_iterator const_reverse_iterator;
-
- inline pushable_array()
- : m_size(0)
- {}
-
- inline explicit pushable_array(size_type s)
- : m_size(s)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
- }
-
- inline void resize(size_type s)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
- m_size = s;
- }
-
- inline Element & operator[](size_type i)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
- return m_array[i];
- }
-
- inline Element const& operator[](size_type i) const
- {
- BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
- return m_array[i];
- }
-
- inline Element const& front() const
- {
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
- return m_array.front();
- }
-
- inline Element & front()
- {
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
- return m_array.front();
- }
-
- inline Element const& back() const
- {
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
- return *(begin() + (m_size - 1));
- }
-
- inline Element & back()
- {
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
- return *(begin() + (m_size - 1));
- }
-
- inline iterator begin()
- {
- return m_array.begin();
- }
-
- inline iterator end()
- {
- return m_array.begin() + m_size;
- }
-
- inline const_iterator begin() const
- {
- return m_array.begin();
- }
-
- inline const_iterator end() const
- {
- return m_array.begin() + m_size;
- }
-
- inline reverse_iterator rbegin()
- {
- return reverse_iterator(end());
- }
-
- inline reverse_iterator rend()
- {
- return reverse_iterator(begin());
- }
-
- inline const_reverse_iterator rbegin() const
- {
- return const_reverse_iterator(end());
- }
-
- inline const_reverse_iterator rend() const
- {
- return const_reverse_iterator(begin());
- }
-
- inline void clear()
- {
- m_size = 0;
- }
-
- inline void erase(iterator it)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
- BOOST_GEOMETRY_INDEX_ASSERT(begin() <= it && it < end(), "iterator points on the element outside the container");
- //std::copy(it + 1, end(), it);
- *it = back();
- --m_size;
- }
-
- inline void push_back(Element const& v)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(m_size < Capacity, "can't further increase the size of the container");
- m_array[m_size++] = v;
- }
-
- inline bool empty() const
- {
- return m_size == 0;
- }
-
- inline size_t size() const
- {
- return m_size;
- }
-
- inline size_t capacity() const
- {
- return Capacity;
- }
-
+ typedef typename array_type::value_type value_type;
+ typedef typename array_type::size_type size_type;
+ typedef typename array_type::iterator iterator;
+ typedef typename array_type::const_iterator const_iterator;
+ typedef typename array_type::reverse_iterator reverse_iterator;
+ typedef typename array_type::const_reverse_iterator const_reverse_iterator;
+
+ inline pushable_array()
+ : m_size(0)
+ {}
+
+ inline explicit pushable_array(size_type s)
+ : m_size(s)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
+ }
+
+ inline void resize(size_type s)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
+ m_size = s;
+ }
+
+ inline Element & operator[](size_type i)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
+ return m_array[i];
+ }
+
+ inline Element const& operator[](size_type i) const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
+ return m_array[i];
+ }
+
+ inline Element const& front() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return m_array.front();
+ }
+
+ inline Element & front()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return m_array.front();
+ }
+
+ inline Element const& back() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return *(begin() + (m_size - 1));
+ }
+
+ inline Element & back()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return *(begin() + (m_size - 1));
+ }
+
+ inline iterator begin()
+ {
+ return m_array.begin();
+ }
+
+ inline iterator end()
+ {
+ return m_array.begin() + m_size;
+ }
+
+ inline const_iterator begin() const
+ {
+ return m_array.begin();
+ }
+
+ inline const_iterator end() const
+ {
+ return m_array.begin() + m_size;
+ }
+
+ inline reverse_iterator rbegin()
+ {
+ return reverse_iterator(end());
+ }
+
+ inline reverse_iterator rend()
+ {
+ return reverse_iterator(begin());
+ }
+
+ inline const_reverse_iterator rbegin() const
+ {
+ return const_reverse_iterator(end());
+ }
+
+ inline const_reverse_iterator rend() const
+ {
+ return const_reverse_iterator(begin());
+ }
+
+ inline void clear()
+ {
+ m_size = 0;
+ }
+
+ inline void erase(iterator it)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ BOOST_GEOMETRY_INDEX_ASSERT(begin() <= it && it < end(), "iterator points on the element outside the container");
+ //std::copy(it + 1, end(), it);
+ *it = back();
+ --m_size;
+ }
+
+ inline void push_back(Element const& v)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(m_size < Capacity, "can't further increase the size of the container");
+ m_array[m_size++] = v;
+ }
+
+ inline bool empty() const
+ {
+ return m_size == 0;
+ }
+
+ inline size_t size() const
+ {
+ return m_size;
+ }
+
+ inline size_t capacity() const
+ {
+ return Capacity;
+ }
+
private:
- boost::array<Element, Capacity> m_array;
- size_type m_size;
+ boost::array<Element, Capacity> m_array;
+ size_type m_size;
};
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -35,22 +35,22 @@
// TODO: awulkiew - implement those:
//if ( m_min_elems_per_node < 1 )
-// m_min_elems_per_node = 1;
+// m_min_elems_per_node = 1;
//if ( m_max_elems_per_node < 2 )
-// m_max_elems_per_node = 2;
+// m_max_elems_per_node = 2;
template <size_t MaxElements, size_t MinElements>
struct linear
{
- static const size_t max_elements = MaxElements;
- static const size_t min_elements = MinElements;
+ static const size_t max_elements = MaxElements;
+ static const size_t min_elements = MinElements;
};
template <size_t MaxElements, size_t MinElements>
struct quadratic
{
- static const size_t max_elements = MaxElements;
- static const size_t min_elements = MinElements;
+ static const size_t max_elements = MaxElements;
+ static const size_t min_elements = MinElements;
};
namespace options { namespace detail {
@@ -58,22 +58,22 @@
template <size_t MaxElements>
struct default_rstar_reinserted_elements
{
- static const size_t value = (MaxElements * 3) / 10;
+ static const size_t value = (MaxElements * 3) / 10;
};
}} // namespace options::detail
template <size_t MaxElements,
- size_t MinElements,
- size_t OverlapCostThreshold = 0,
- size_t ReinsertedElements = options::detail::default_rstar_reinserted_elements<MaxElements>::value
- >
+ size_t MinElements,
+ size_t OverlapCostThreshold = 0,
+ size_t ReinsertedElements = options::detail::default_rstar_reinserted_elements<MaxElements>::value
+ >
struct rstar
{
- static const size_t max_elements = MaxElements;
- static const size_t min_elements = MinElements;
- static const size_t overlap_cost_threshold = OverlapCostThreshold;
- static const size_t reinserted_elements = ReinsertedElements;
+ static const size_t max_elements = MaxElements;
+ static const size_t min_elements = MinElements;
+ static const size_t overlap_cost_threshold = OverlapCostThreshold;
+ static const size_t reinserted_elements = ReinsertedElements;
};
namespace options {
@@ -81,12 +81,12 @@
template <typename Parameters, typename InsertTag, typename ChooseNextNodeTag, typename SplitTag, typename RedistributeTag, typename NodeTag>
struct rtree
{
- typedef Parameters parameters_type;
- typedef InsertTag insert_tag;
- typedef ChooseNextNodeTag choose_next_node_tag;
- typedef SplitTag split_tag;
- typedef RedistributeTag redistribute_tag;
- typedef NodeTag node_tag;
+ typedef Parameters parameters_type;
+ typedef InsertTag insert_tag;
+ typedef ChooseNextNodeTag choose_next_node_tag;
+ typedef SplitTag split_tag;
+ typedef RedistributeTag redistribute_tag;
+ typedef NodeTag node_tag;
};
} // namespace options
@@ -96,46 +96,46 @@
template <typename Parameters>
struct options_type
{
- // TODO: awulkiew - use static assert
+ // TODO: awulkiew - use static assert
};
template <size_t MaxElements, size_t MinElements>
struct options_type< linear<MaxElements, MinElements> >
{
- typedef options::rtree<
- linear<MaxElements, MinElements>,
- insert_default_tag,
- choose_by_content_diff_tag,
- split_default_tag,
- linear_tag,
- node_default_static_tag
- > type;
+ typedef options::rtree<
+ linear<MaxElements, MinElements>,
+ insert_default_tag,
+ choose_by_content_diff_tag,
+ split_default_tag,
+ linear_tag,
+ node_default_static_tag
+ > type;
};
template <size_t MaxElements, size_t MinElements>
struct options_type< quadratic<MaxElements, MinElements> >
{
- typedef options::rtree<
- quadratic<MaxElements, MinElements>,
- insert_default_tag,
- choose_by_content_diff_tag,
- split_default_tag,
- quadratic_tag,
- node_default_static_tag
- > type;
+ typedef options::rtree<
+ quadratic<MaxElements, MinElements>,
+ insert_default_tag,
+ choose_by_content_diff_tag,
+ split_default_tag,
+ quadratic_tag,
+ node_default_static_tag
+ > type;
};
template <size_t MaxElements, size_t MinElements, size_t OverlapCostThreshold, size_t ReinsertedElements>
struct options_type< rstar<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements> >
{
- typedef options::rtree<
- rstar<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements>,
- insert_reinsert_tag,
- choose_by_overlap_diff_tag,
- split_default_tag,
- rstar_tag,
- node_default_static_tag
- > type;
+ typedef options::rtree<
+ rstar<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements>,
+ insert_reinsert_tag,
+ choose_by_overlap_diff_tag,
+ split_default_tag,
+ rstar_tag,
+ node_default_static_tag
+ > type;
};
}} // namespace detail::rtree
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -0,0 +1,52 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - Spatial index query predicates
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_PREDICATES_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_PREDICATES_HPP
+
+#include <boost/geometry/extensions/index/predicates.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+namespace rtree {
+
+struct value_predicates_tag {};
+struct node_predicates_tag {};
+
+} // namespace rtree
+
+template <typename Geometry>
+struct predicate_check<covered_by<Geometry>, rtree::node_predicates_tag>
+{
+ template <typename Indexable>
+ static bool apply(covered_by<Geometry> const& p, Indexable const& i)
+ {
+ return geometry::intersects(i, p.geometry);
+ }
+};
+
+template <typename Geometry>
+struct predicate_check<within<Geometry>, rtree::node_predicates_tag>
+{
+ template <typename Indexable>
+ static bool apply(within<Geometry> const& p, Indexable const& i)
+ {
+ // TODO: awulkiew - possibly change to the version without border case
+ // e.g. intersects_without_border(0,0x1,1, 1,1x2,2) should give false
+ return geometry::intersects(i, p.geometry);
+ }
+};
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_PREDICATES_HPP
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 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -22,11 +22,13 @@
#include <boost/geometry/extensions/index/translator/translator.hpp>
#include <boost/geometry/extensions/index/rtree/options.hpp>
-#include <boost/geometry/extensions/index/rtree/filters.hpp>
+#include <boost/geometry/extensions/index/rtree/predicates.hpp>
+//#include <boost/geometry/extensions/index/rtree/filters.hpp>
#include <boost/geometry/extensions/index/rtree/node/node.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/find.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/query.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/remove.hpp>
@@ -42,19 +44,19 @@
template <
typename Value,
typename Parameters,
- typename Translator = translator::def<Value>
+ typename Translator = translator::def<Value>
>
class rtree
- : public boost::noncopyable
+ : public boost::noncopyable
{
public:
typedef Value value_type;
typedef Translator translator_type;
- typedef typename translator_type::indexable_type indexable_type;
+ typedef typename translator_type::indexable_type indexable_type;
typedef typename index::default_box_type<indexable_type>::type box_type;
- typedef typename detail::rtree::options_type<Parameters>::type options_type;
- typedef typename options_type::node_tag node_tag;
+ typedef typename detail::rtree::options_type<Parameters>::type options_type;
+ typedef typename options_type::node_tag node_tag;
typedef typename detail::rtree::node<value_type, typename options_type::parameters_type, box_type, node_tag>::type node;
typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, node_tag>::type internal_node;
@@ -75,8 +77,16 @@
detail::rtree::apply_visitor(del_v, *m_root);
}
- // TODO: awulkiew - change name to query?
+ template <typename Predicates, typename OutIter>
+ inline void query(Predicates const& pred, OutIter out_it) const
+ {
+ detail::rtree::visitors::query<value_type, options_type, translator_type, box_type, Predicates, OutIter>
+ find_v(m_translator, pred, out_it);
+
+ detail::rtree::apply_visitor(find_v, *m_root);
+ }
+ // TODO: delete find method
template <typename Geometry, typename OutIter>
inline void find(Geometry const& geom, OutIter out_it) const
{
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -19,8 +19,8 @@
template <typename Value, typename Options, typename Translator, typename Box>
class are_boxes_ok
- : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
+ , index::nonassignable
{
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
@@ -76,27 +76,27 @@
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
- // non-root node
+ // non-root node
if (!m_is_root)
{
- if ( elements.empty() )
- {
- result = false;
- return;
- }
+ if ( elements.empty() )
+ {
+ result = false;
+ return;
+ }
- Box box_exp;
- geometry::convert(m_tr(elements.front()), box_exp);
- for(typename elements_type::const_iterator it = elements.begin() + 1;
- it != elements.end() ; ++it)
- {
- geometry::expand(box_exp, m_tr(*it));
- }
-
- result = geometry::equals(box_exp, m_box);
- }
- else
- result = true;
+ Box box_exp;
+ geometry::convert(m_tr(elements.front()), box_exp);
+ for(typename elements_type::const_iterator it = elements.begin() + 1;
+ it != elements.end() ; ++it)
+ {
+ geometry::expand(box_exp, m_tr(*it));
+ }
+
+ result = geometry::equals(box_exp, m_box);
+ }
+ else
+ result = true;
}
bool result;
@@ -115,7 +115,7 @@
typedef rtree<Value, Options, Translator> rt;
detail::rtree::visitors::are_boxes_ok<
typename rt::value_type,
- typename rt::options_type,
+ typename rt::options_type,
typename rt::translator_type,
typename rt::box_type> v(tree.get_translator());
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -18,8 +18,8 @@
template <typename Value, typename Options, typename Translator, typename Box>
class are_levels_ok
- : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
+ , index::nonassignable
{
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
@@ -40,10 +40,10 @@
return;
}
- size_t current_level_backup = m_current_level;
- ++m_current_level;
+ size_t current_level_backup = m_current_level;
+ ++m_current_level;
- for ( typename elements_type::const_iterator it = elements.begin();
+ for ( typename elements_type::const_iterator it = elements.begin();
it != elements.end() ; ++it)
{
rtree::apply_visitor(*this, *it->second);
@@ -52,7 +52,7 @@
return;
}
- m_current_level = current_level_backup;
+ m_current_level = current_level_backup;
}
inline void operator()(leaf const& n)
@@ -60,7 +60,7 @@
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
- // empty leaf in non-root node
+ // empty leaf in non-root node
if (0 < m_current_level && elements.empty())
{
result = false;
@@ -68,13 +68,13 @@
}
if ( m_leafs_level == std::numeric_limits<size_t>::max() )
- {
- m_leafs_level = m_current_level;
- }
- else if ( m_leafs_level != m_current_level )
- {
- result = false;
- }
+ {
+ m_leafs_level = m_current_level;
+ }
+ else if ( m_leafs_level != m_current_level )
+ {
+ result = false;
+ }
}
bool result;
@@ -82,7 +82,7 @@
private:
Translator const& m_tr;
size_t m_leafs_level;
- size_t m_current_level;
+ size_t m_current_level;
};
}}} // namespace detail::rtree::visitors
@@ -93,7 +93,7 @@
typedef rtree<Value, Options, Translator> rt;
detail::rtree::visitors::are_levels_ok<
typename rt::value_type,
- typename rt::options_type,
+ typename rt::options_type,
typename rt::translator_type,
typename rt::box_type> v(tree.get_translator());
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -142,8 +142,8 @@
template <typename Value, typename Options, typename Translator, typename Box, typename Geometry, typename OutIter>
struct find
- : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
+ , index::nonassignable
{
typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -196,7 +196,7 @@
)
{
typedef typename rtree<Value, Options, Translator>::value_type value_type;
- typedef typename rtree<Value, Options, Translator>::options_type options_type;
+ typedef typename rtree<Value, Options, Translator>::options_type options_type;
typedef typename rtree<Value, Options, Translator>::translator_type translator_type;
typedef typename rtree<Value, Options, Translator>::box_type box_type;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -40,7 +40,7 @@
{
children_type & children = rtree::elements(n);
- BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty");
+ BOOST_GEOMETRY_INDEX_ASSERT(!children.empty(), "can't choose the next node if children are empty");
size_t children_count = children.size();
@@ -94,61 +94,61 @@
class split<Value, Options, Translator, Box, split_default_tag>
{
protected:
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
- typedef typename Options::parameters_type parameters_type;
+ typedef typename Options::parameters_type parameters_type;
public:
- template <typename Node>
- static inline void apply(node* & root_node,
- size_t & leafs_level,
- Node & n,
- internal_node *parent_node,
- size_t current_child_index,
- Translator const& tr)
- {
- // create additional node
- node * second_node = rtree::create_node(Node());
- Node & n2 = rtree::get<Node>(*second_node);
-
- // redistribute elements
- Box box1, box2;
- redistribute_elements<Value, Options, Translator, Box, typename Options::redistribute_tag>::
- apply(n, n2, box1, box2, tr);
-
- // check numbers of elements
- BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= rtree::elements(n).size() &&
- rtree::elements(n).size() <= parameters_type::max_elements,
- "unexpected number of elements");
- BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= rtree::elements(n2).size() &&
- rtree::elements(n2).size() <= parameters_type::max_elements,
- "unexpected number of elements");
-
- // node is not the root - just add the new node
- if ( parent_node != 0 )
- {
- // update old node's box
- rtree::elements(*parent_node)[current_child_index].first = box1;
- // add new node to the parent's children
- rtree::elements(*parent_node).push_back(std::make_pair(box2, second_node));
- }
- // node is the root - add level
- else
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(root_node), "node should be the root");
-
- // create new root and add nodes
- node * new_root = rtree::create_node(internal_node());
-
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box1, root_node));
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box2, second_node));
-
- root_node = new_root;
- ++leafs_level;
- }
- }
+ template <typename Node>
+ static inline void apply(node* & root_node,
+ size_t & leafs_level,
+ Node & n,
+ internal_node *parent_node,
+ size_t current_child_index,
+ Translator const& tr)
+ {
+ // create additional node
+ node * second_node = rtree::create_node(Node());
+ Node & n2 = rtree::get<Node>(*second_node);
+
+ // redistribute elements
+ Box box1, box2;
+ redistribute_elements<Value, Options, Translator, Box, typename Options::redistribute_tag>::
+ apply(n, n2, box1, box2, tr);
+
+ // check numbers of elements
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= rtree::elements(n).size() &&
+ rtree::elements(n).size() <= parameters_type::max_elements,
+ "unexpected number of elements");
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= rtree::elements(n2).size() &&
+ rtree::elements(n2).size() <= parameters_type::max_elements,
+ "unexpected number of elements");
+
+ // node is not the root - just add the new node
+ if ( parent_node != 0 )
+ {
+ // update old node's box
+ rtree::elements(*parent_node)[current_child_index].first = box1;
+ // add new node to the parent's children
+ rtree::elements(*parent_node).push_back(std::make_pair(box2, second_node));
+ }
+ // node is the root - add level
+ else
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(root_node), "node should be the root");
+
+ // create new root and add nodes
+ node * new_root = rtree::create_node(internal_node());
+
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box1, root_node));
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box2, second_node));
+
+ root_node = new_root;
+ ++leafs_level;
+ }
+ }
};
// ----------------------------------------------------------------------- //
@@ -156,15 +156,15 @@
// Default insert visitor
template <typename Element, typename Value, typename Options, typename Translator, typename Box>
class insert
- : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
+ , index::nonassignable
{
protected:
typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
- typedef typename Options::parameters_type parameters_type;
+ typedef typename Options::parameters_type parameters_type;
inline insert(node* & root,
size_t & leafs_level,
@@ -174,7 +174,7 @@
)
: m_element(element)
, m_tr(t)
- , m_relative_level(relative_level)
+ , m_relative_level(relative_level)
, m_level(leafs_level - relative_level)
, m_root_node(root)
, m_leafs_level(leafs_level)
@@ -182,8 +182,8 @@
, m_current_child_index(0)
, m_current_level(0)
{
- BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
- BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
+ BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
+ BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
// TODO
// assert - check if Box is correct
}
@@ -209,13 +209,13 @@
template <typename Node>
inline void post_traverse(Node &n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(0 == m_parent || &n == rtree::get<Node>(rtree::elements(*m_parent)[m_current_child_index].second),
- "if node isn't the root current_child_index should be valid");
+ BOOST_GEOMETRY_INDEX_ASSERT(0 == m_parent || &n == rtree::get<Node>(rtree::elements(*m_parent)[m_current_child_index].second),
+ "if node isn't the root current_child_index should be valid");
// handle overflow
if ( parameters_type::max_elements < rtree::elements(n).size() )
{
- split(n);
+ split(n);
}
}
@@ -241,17 +241,17 @@
m_current_level = current_level_bckup;
}
- template <typename Node>
- inline void split(Node & n) const
- {
- detail::split<Value, Options, Translator, Box, typename Options::split_tag>::apply(m_root_node, m_leafs_level, n, m_parent, m_current_child_index, m_tr);
- }
+ template <typename Node>
+ inline void split(Node & n) const
+ {
+ detail::split<Value, Options, Translator, Box, typename Options::split_tag>::apply(m_root_node, m_leafs_level, n, m_parent, m_current_child_index, m_tr);
+ }
// TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
Element const& m_element;
Translator const& m_tr;
- const size_t m_relative_level;
+ const size_t m_relative_level;
const size_t m_level;
node* & m_root_node;
@@ -272,7 +272,7 @@
// Default insert visitor used for nodes elements
template <typename Element, typename Value, typename Options, typename Translator, typename Box>
struct insert<Element, Value, Options, Translator, Box, insert_default_tag>
- : public detail::insert<Element, Value, Options, Translator, Box>
+ : public detail::insert<Element, Value, Options, Translator, Box>
{
typedef detail::insert<Element, Value, Options, Translator, Box> base;
typedef typename base::node node;
@@ -290,7 +290,7 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
if ( base::m_current_level < base::m_level )
{
@@ -299,7 +299,7 @@
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level, "unexpected level");
// push new child node
rtree::elements(n).push_back(base::m_element);
@@ -317,7 +317,7 @@
// Default insert visitor specialized for Values elements
template <typename Value, typename Options, typename Translator, typename Box>
struct insert<Value, Value, Options, Translator, Box, insert_default_tag>
- : public detail::insert<Value, Value, Options, Translator, Box>
+ : public detail::insert<Value, Value, Options, Translator, Box>
{
typedef detail::insert<Value, Value, Options, Translator, Box> base;
typedef typename base::node node;
@@ -335,8 +335,8 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
// next traversing step
base::traverse(*this, n);
@@ -346,8 +346,8 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == std::numeric_limits<size_t>::max(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == std::numeric_limits<size_t>::max(), "unexpected level");
rtree::elements(n).push_back(base::m_element);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/print.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/print.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/print.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -182,7 +182,7 @@
std::ostream & operator<<(std::ostream & os, rtree<Value, Options, Translator> const& tree)
{
typedef typename rtree<Value, Options, Translator>::value_type value_type;
- typedef typename rtree<Value, Options, Translator>::options_type options_type;
+ typedef typename rtree<Value, Options, Translator>::options_type options_type;
typedef typename rtree<Value, Options, Translator>::translator_type translator_type;
typedef typename rtree<Value, Options, Translator>::box_type box_type;
detail::rtree::visitors::print<value_type, options_type, translator_type, box_type> print_v(os, tree.get_translator());
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -0,0 +1,70 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree spatial query
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_QUERY_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_QUERY_HPP
+
+#include <boost/geometry/extensions/index/rtree/node/node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Value, typename Options, typename Translator, typename Box, typename Predicates, typename OutIter>
+struct query
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
+ , index::nonassignable
+{
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ inline query(Translator const& t, Predicates const& p, OutIter out_it)
+ : tr(t), pred(p), out_iter(out_it)
+ {}
+
+ inline void operator()(internal_node const& n)
+ {
+ typedef typename rtree::elements_type<internal_node>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ if ( index::predicates_check<rtree::node_predicates_tag>(pred, it->first) )
+ rtree::apply_visitor(*this, *it->second);
+ }
+ }
+
+ inline void operator()(leaf const& n)
+ {
+ typedef typename rtree::elements_type<leaf>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ if ( index::predicates_check<rtree::value_predicates_tag>(pred, tr(*it)) )
+ {
+ out_iter = *it;
+ ++out_iter;
+ }
+ }
+ }
+
+ Translator const& tr;
+ Predicates const& pred;
+ OutIter out_iter;
+};
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_QUERY_HPP
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 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -23,14 +23,14 @@
// Default remove algorithm
template <typename Value, typename Options, typename Translator, typename Box>
class remove
- : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
+ , index::nonassignable
{
typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
- typedef typename Options::parameters_type parameters_type;
+ typedef typename Options::parameters_type parameters_type;
public:
inline remove(node* & root,
@@ -104,8 +104,8 @@
// n is root node
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
- BOOST_GEOMETRY_INDEX_ASSERT(m_is_value_removed, "value not found");
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
+ BOOST_GEOMETRY_INDEX_ASSERT(m_is_value_removed, "value not found");
// reinsert elements from removed nodes
// begin with levels closer to the root
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/getter.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/getter.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/getter.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -17,7 +17,7 @@
{
typedef Indexable indexable_type;
- indexable_type const& operator()(Value const& v) const
+ indexable_type const& operator()(Value const& v) const
{
return (v.*Getter)();
}
@@ -25,7 +25,7 @@
bool equals(Value const& v1, Value const& v2) const
{
//return geometry::equals(operator()(v1), operator()(v2));
- return v1 == v2;
+ return v1 == v2;
}
};
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/helpers.hpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -173,15 +173,15 @@
static bool apply(std::pair<First, Second> const& p1, std::pair<First, Second> const& p2)
{
return
- dispatch::equals<
- First,
- typename traits::tag<First>::type
- >::apply(p1.first, p2.first)
- &&
dispatch::equals<
- Second,
- typename traits::tag<Second>::type
- >::apply(p1.second, p2.second);
+ First,
+ typename traits::tag<First>::type
+ >::apply(p1.first, p2.first)
+ &&
+ dispatch::equals<
+ Second,
+ typename traits::tag<Second>::type
+ >::apply(p1.second, p2.second);
}
};
Modified: sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -26,16 +26,16 @@
namespace bg = boost::geometry;
namespace bgi = bg::index;
- //typedef bg::model::d2::point_xy<double> P;
+ //typedef bg::model::d2::point_xy<double> P;
typedef bg::model::point<double, 2, bg::cs::cartesian> P;
typedef bg::model::box<P> B;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::linear<32, 8> > RT;
+ typedef bgi::rtree<std::pair<B, size_t>, bgi::linear<32, 8> > RT;
//typedef bgi::rtree<std::pair<B, size_t>, bgi::quadratic<32, 8> > RT;
- typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar<32, 8> > RT;
- /*typedef bgi::rtree<
- std::pair<B, size_t>,
- bgi::options::rtree<bgi::rstar<32, 8, 0, 10>, bgi::reinsert_tag, bgi::choose_by_area_diff_tag, bgi::rstar_tag, bgi::default_tag>
- > RT;*/
+ //typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar<32, 8> > RT;
+ /*typedef bgi::rtree<
+ std::pair<B, size_t>,
+ bgi::options::rtree<bgi::rstar<32, 8, 0, 10>, bgi::reinsert_tag, bgi::choose_by_area_diff_tag, bgi::rstar_tag, bgi::default_tag>
+ > RT;*/
// load config file
std::ifstream file_cfg("config.txt");
@@ -89,13 +89,13 @@
else
{
boost::mt19937 rng;
- //rng.seed(static_cast<unsigned int>(std::time(0)));
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
- float max_val = static_cast<float>(values_count / 2);
+ float max_val = static_cast<float>(values_count / 2);
boost::uniform_real<float> range(-max_val, max_val);
- boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
-
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
std::cout << "randomizing data\n";
for ( size_t i = 0 ; i < values_count ; ++i )
{
@@ -127,14 +127,14 @@
std::cout << "BOXES OK\n";
else
std::cout << "WRONG BOXES\n";
- if ( bgi::are_levels_ok(t) )
- std::cout << "LEVELS OK\n";
- else
- std::cout << "WRONG LEVELS\n";
+ if ( bgi::are_levels_ok(t) )
+ std::cout << "LEVELS OK\n";
+ else
+ std::cout << "WRONG LEVELS\n";
// searching test
{
- std::cout << "searching time test...\n";
+ std::cout << "find(B) searching time test...\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -149,6 +149,40 @@
std::cout << "found: " << temp << "\n";
}
+ // searching test
+ {
+ std::cout << "query(intersects(B)) searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.query(bgi::intersects(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";
+ }
+
+ // searching test
+ {
+ std::cout << "query(B) searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.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";
+ }
+
// elements removing test
{
std::cout << "removing time test...\n";
@@ -164,15 +198,15 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
- // check
- if ( bgi::are_boxes_ok(t) )
- std::cout << "BOXES OK\n";
- else
- std::cout << "WRONG BOXES\n";
- if ( bgi::are_levels_ok(t) )
- std::cout << "LEVELS OK\n";
- else
- std::cout << "WRONG LEVELS\n";
+ // check
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
+ if ( bgi::are_levels_ok(t) )
+ std::cout << "LEVELS OK\n";
+ else
+ std::cout << "WRONG LEVELS\n";
// searching test
{
@@ -184,7 +218,7 @@
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::back_inserter(result));
+ t.query(bgi::intersects(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";
@@ -206,15 +240,15 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
- // check
- if ( bgi::are_boxes_ok(t) )
- std::cout << "BOXES OK\n";
- else
- std::cout << "WRONG BOXES\n";
- if ( bgi::are_levels_ok(t) )
- std::cout << "LEVELS OK\n";
- else
- std::cout << "WRONG LEVELS\n";
+ // check
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
+ if ( bgi::are_levels_ok(t) )
+ std::cout << "LEVELS OK\n";
+ else
+ std::cout << "WRONG LEVELS\n";
// searching test
{
@@ -226,7 +260,7 @@
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::back_inserter(result));
+ t.query(bgi::intersects(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";
Modified: sandbox-branches/geometry/index/tests/main.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/main.cpp (original)
+++ sandbox-branches/geometry/index/tests/main.cpp 2011-08-26 20:05:54 EDT (Fri, 26 Aug 2011)
@@ -18,7 +18,7 @@
tests_translators_hpp();
tests_rtree_native_hpp<boost::geometry::index::linear<4, 2> >();
tests_rtree_native_hpp<boost::geometry::index::quadratic<4, 2> >();
- tests_rtree_native_hpp<boost::geometry::index::rstar<4, 2> >();
+ tests_rtree_native_hpp<boost::geometry::index::rstar<4, 2> >();
tests_rtree_filters_hpp();
/*
{