|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r82515 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2013-01-16 22:54:53
Author: awulkiew
Date: 2013-01-16 22:54:52 EST (Wed, 16 Jan 2013)
New Revision: 82515
URL: http://svn.boost.org/trac/boost/changeset/82515
Log:
Box stored in the rtree.
box() returns box_type const&.
rtree adapted to Box concept.
error in remove() fixed - size change if the Value wasn't removed.
Tests added.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 157 ++++++++++++++++++++++++++-------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/children_box.hpp | 11 +-
sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 67 +++++++++++++++++
3 files changed, 177 insertions(+), 58 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-16 22:54:52 EST (Wed, 16 Jan 2013)
@@ -147,7 +147,9 @@
, m_values_count(0)
, m_leafs_level(0)
, m_root(0)
- {}
+ {
+ geometry::assign_inverse(m_box);
+ }
/*!
\brief The constructor.
@@ -168,7 +170,9 @@
, m_values_count(0)
, m_leafs_level(0)
, m_root(0)
- {}
+ {
+ geometry::assign_inverse(m_box);
+ }
/*!
\brief The constructor.
@@ -197,6 +201,8 @@
, m_leafs_level(0)
, m_root(0)
{
+ geometry::assign_inverse(m_box);
+
try
{
this->insert(first, last);
@@ -234,6 +240,8 @@
, m_leafs_level(0)
, m_root(0)
{
+ geometry::assign_inverse(m_box);
+
try
{
this->insert(rng);
@@ -276,9 +284,9 @@
, m_values_count(0)
, m_leafs_level(0)
, m_root(0)
+ , m_box(src.m_box)
{
//TODO use Boost.Container allocator_traits_type::select_on_container_copy_construction()
-
this->raw_copy(src, *this, false);
}
@@ -303,6 +311,7 @@
, m_values_count(0)
, m_leafs_level(0)
, m_root(0)
+ , m_box(src.m_box)
{
this->raw_copy(src, *this, false);
}
@@ -325,6 +334,7 @@
, m_values_count(src.m_values_count)
, m_leafs_level(src.m_leafs_level)
, m_root(src.m_root)
+ , m_box(src.m_box)
{
src.m_values_count = 0;
src.m_leafs_level = 0;
@@ -353,6 +363,7 @@
, m_values_count(0)
, m_leafs_level(0)
, m_root(0)
+ , m_box(src.m_box)
{
if ( src.m_allocators.allocator == allocator )
{
@@ -388,6 +399,8 @@
// It uses m_allocators
this->raw_copy(src, *this, true);
+ m_box = src.m_box;
+
return *this;
}
@@ -432,6 +445,8 @@
this->raw_copy(src, *this, true);
}
+ m_box = src.m_box;
+
return *this;
}
@@ -454,6 +469,7 @@
boost::swap(m_values_count, other.m_values_count);
boost::swap(m_leafs_level, other.m_leafs_level);
boost::swap(m_root, other.m_root);
+ boost::swap(m_box, other.m_box);
}
/*!
@@ -888,6 +904,7 @@
inline void clear()
{
this->raw_destroy(*this);
+ geometry::assign_inverse(m_box);
}
/*!
@@ -902,21 +919,9 @@
\par Throws
Nothing.
*/
- inline box_type box() const
+ inline box_type const& box() const
{
- if ( this->empty() )
- {
- box_type result;
- geometry::assign_inverse(result);
- return result;
- }
-
- detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
- children_box_v(m_translator);
-
- detail::rtree::apply_visitor(children_box_v, *m_root);
-
- return children_box_v.result;
+ return m_box;
}
/*!
@@ -967,7 +972,7 @@
\par Throws
Nothing.
*/
- inline const translator_type & translator() const
+ inline translator_type const& translator() const
{
return m_translator;
}
@@ -1067,6 +1072,8 @@
// TODO
// If exception is thrown, m_values_count may be invalid
++m_values_count;
+
+ geometry::expand(m_box, m_translator(value));
}
/*!
@@ -1081,7 +1088,6 @@
{
// TODO: awulkiew - assert for correct value (indexable) ?
BOOST_GEOMETRY_INDEX_ASSERT(m_root, "The root must exist");
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_values_count, "can't remove, there are no elements in the rtree");
detail::rtree::visitors::remove<
value_type, options_type, translator_type, box_type, allocators_type
@@ -1089,15 +1095,31 @@
detail::rtree::apply_visitor(remove_v, *m_root);
-// TODO
-// Think about this: If exception is thrown, may the root be removed?
-// Or it is just cleared?
+ // If exception is thrown, m_values_count may be invalid
-// TODO
-// If exception is thrown, m_values_count may be invalid
- --m_values_count;
+ if ( remove_v.is_value_removed() )
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_values_count, "unexpected state");
+
+ --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);
- return remove_v.is_value_removed() ? 1 : 0;
+ detail::rtree::apply_visitor(children_box_v, *m_root);
+ }
+
+ return 1;
+ }
+
+ return 0;
}
/*!
@@ -1259,6 +1281,8 @@
size_type m_values_count;
size_type m_leafs_level;
node * m_root;
+
+ box_type m_box;
};
/*!
@@ -1540,7 +1564,7 @@
\return The box containing all stored values or an invalid box.
*/
template <typename Value, typename Options, typename Translator, typename Allocator>
-inline typename rtree<Value, Options, Translator, Allocator>::box_type
+inline typename rtree<Value, Options, Translator, Allocator>::box_type const&
box(rtree<Value, Options, Translator, Allocator> const& tree)
{
return tree.box();
@@ -1548,44 +1572,73 @@
}}} // namespace boost::geometry::index
-#include <boost/geometry/algorithms/envelope.hpp>
+// Rtree adaptation to Box concept
namespace boost { namespace geometry {
-/*!
-\brief Get the box containing all stored values or an invalid box if the index has no values.
+// Traits specializations for box above
+#ifndef DOXYGEN_NO_TRAITS_SPECIALIZATIONS
+namespace traits
+{
-It calls \c rtree::box().
+template <typename Value, typename Parameters, typename Translator, typename Allocator>
+struct tag< index::rtree<Value, Parameters, Translator, Allocator> >
+{
+ typedef box_tag type;
+};
-\ingroup rtree_functions
+template <typename Value, typename Parameters, typename Translator, typename Allocator>
+struct point_type< index::rtree<Value, Parameters, Translator, Allocator> >
+{
+ typedef typename geometry::point_type<
+ typename index::rtree<Value, Parameters, Translator, Allocator>::box_type
+ >::type type;
+};
-\param tree The spatial index.
-\param box The object to which box containing all stored values or an invalid box will be assigned.
-*/
-template <typename Value, typename Options, typename Translator, typename Allocator, typename Box>
-void envelope(index::rtree<Value, Options, Translator, Allocator> const& tree, Box & box)
+template <typename Value, typename Parameters, typename Translator, typename Allocator, std::size_t Dimension>
+struct indexed_access<index::rtree<Value, Parameters, Translator, Allocator>, min_corner, Dimension>
{
- envelope(tree.box(), box);
-}
+ typedef typename geometry::coordinate_type<
+ typename geometry::point_type<
+ index::rtree<Value, Parameters, Translator, Allocator>
+ >::type
+ >::type coordinate_type;
-/*!
-\brief Get the box containing all stored values or an invalid box if the index has no values.
+ static inline coordinate_type get(index::rtree<Value, Parameters, Translator, Allocator> const& tree)
+ {
+ return geometry::get<min_corner, Dimension>(tree.box());
+ }
-It calls \c rtree::box().
+ static inline void set(index::rtree<Value, Parameters, Translator, Allocator> & tree,
+ coordinate_type const& value)
+ {
+ return geometry::set<min_corner, Dimension>(tree.box(), value);
+ }
+};
-\ingroup rtree_functions
+template <typename Value, typename Parameters, typename Translator, typename Allocator, std::size_t Dimension>
+struct indexed_access<index::rtree<Value, Parameters, Translator, Allocator>, max_corner, Dimension>
+{
+ typedef typename geometry::coordinate_type<
+ typename geometry::point_type<
+ index::rtree<Value, Parameters, Translator, Allocator>
+ >::type
+ >::type coordinate_type;
-\tparam Box The type of returned Box.
+ static inline coordinate_type get(index::rtree<Value, Parameters, Translator, Allocator> const& tree)
+ {
+ return geometry::get<max_corner, Dimension>(tree.box());
+ }
-\param tree The spatial index.
+ static inline void set(index::rtree<Value, Parameters, Translator, Allocator> & tree,
+ coordinate_type const& value)
+ {
+ return geometry::set<max_corner, Dimension>(tree.box(), value);
+ }
+};
-\return The box containing all stored values or an invalid box.
-*/
-template <typename Box, typename Value, typename Options, typename Translator, typename Allocator>
-Box return_envelope(index::rtree<Value, Options, Translator, Allocator> const& tree)
-{
- return return_envelope(tree.box());
-}
+} // namespace traits
+#endif // DOXYGEN_NO_TRAITS_SPECIALIZATIONS
}} //namespace boost::geometry
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/children_box.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/children_box.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/children_box.hpp 2013-01-16 22:54:52 EST (Wed, 16 Jan 2013)
@@ -26,8 +26,8 @@
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
public:
- inline children_box(Translator const& tr)
- : m_tr(tr)
+ inline children_box(Box & result, Translator const& tr)
+ : m_result(result), m_tr(tr)
{}
inline void operator()(internal_node const& n)
@@ -35,7 +35,7 @@
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
- result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
+ m_result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
}
inline void operator()(leaf const& n)
@@ -43,12 +43,11 @@
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
- result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
+ m_result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
}
- Box result;
-
private:
+ Box & m_result;
Translator const& m_tr;
};
Modified: sandbox-branches/geometry/index/test/rtree/test_rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index/test/rtree/test_rtree.hpp 2013-01-16 22:54:52 EST (Wed, 16 Jan 2013)
@@ -1049,6 +1049,7 @@
std::vector<Value> expected_output;
tree.spatial_query(bgi::disjoint(qbox), std::back_inserter(expected_output));
size_t expected_removed_count = values_to_remove.size();
+ size_t expected_size_after_remove = tree.size() - values_to_remove.size();
// Add value which is not stored in the Rtree
Value outsider = generate_value_outside<T>();
@@ -1062,6 +1063,7 @@
BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( t.size() == expected_size_after_remove );
BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
@@ -1071,6 +1073,7 @@
BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( t.size() == expected_size_after_remove );
BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
@@ -1080,6 +1083,7 @@
BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( t.size() == expected_size_after_remove );
BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
@@ -1092,6 +1096,7 @@
BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( t.size() == expected_size_after_remove );
BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
@@ -1101,6 +1106,7 @@
BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( t.size() == expected_size_after_remove );
BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
@@ -1110,6 +1116,7 @@
BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( t.size() == expected_size_after_remove );
BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
@@ -1265,6 +1272,64 @@
BOOST_CHECK(t.count(input[0].first) == 3);
}
+// test rtree box
+
+template <typename Value, typename Parameters>
+void test_rtree_box(Parameters const& parameters)
+{
+ typedef bgi::rtree<Value, Parameters> Tree;
+ typedef typename Tree::box_type B;
+ typedef typename bg::traits::point_type<B>::type P;
+
+ B b;
+ bg::assign_inverse(b);
+
+ Tree t(parameters);
+ std::vector<Value> input;
+ B qbox;
+
+ BOOST_CHECK(bg::equals(t.box(), b));
+
+ generate_rtree(t, input, qbox);
+
+ BOOST_FOREACH(Value const& v, input)
+ bg::expand(b, t.translator()(v));
+
+ BOOST_CHECK(bg::equals(t.box(), b));
+
+ //BOOST_CHECK(bg::equals(bg::return_envelope<B>(t), b));
+ //BOOST_CHECK(bg::area(t) == bg::area(b));
+ //BOOST_CHECK(bg::perimeter(t) == bg::perimeter(b));
+ //BOOST_CHECK(bg::equals(bg::return_centroid<P>(t), bg::return_centroid<P>(b)));
+
+ size_t s = input.size();
+ while ( s/2 < input.size() && !input.empty() )
+ {
+ t.remove(input.back());
+ input.pop_back();
+ }
+
+ bg::assign_inverse(b);
+ BOOST_FOREACH(Value const& v, input)
+ bg::expand(b, t.translator()(v));
+
+ BOOST_CHECK(bg::equals(t.box(), b));
+
+ Tree t2(t);
+ BOOST_CHECK(bg::equals(t2.box(), b));
+ t2.clear();
+ t2 = t;
+ BOOST_CHECK(bg::equals(t2.box(), b));
+ t2.clear();
+ t2 = boost::move(t);
+ BOOST_CHECK(bg::equals(t2.box(), b));
+
+ t.clear();
+
+ bg::assign_inverse(b);
+ BOOST_CHECK(bg::equals(t.box(), b));
+}
+
// run all tests for one Algorithm for some number of rtrees
// defined by some number of Values constructed from given Point
@@ -1286,6 +1351,7 @@
test_count_rtree_values<Point>(parameters);
test_rtree_count<Point>(parameters);
+ test_rtree_box<Point>(parameters);
}
template<typename Point, typename Parameters>
@@ -1305,6 +1371,7 @@
test_count_rtree_values<Box>(parameters);
test_rtree_count<Box>(parameters);
+ test_rtree_box<Box>(parameters);
}
#endif
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk