Subject: [Boost-commit] svn:boost r82353 - 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-04 12:38:19
Author: awulkiew
Date: 2013-01-04 12:38:18 EST (Fri, 04 Jan 2013)
New Revision: 82353
URL: http://svn.boost.org/trac/boost/changeset/82353
Log:
Added number of removed elements returned by rtree::remove().
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 47 +++++++++++++++++------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 6 ++
sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 76 +++++++++++++++++++++++++++++++++------
3 files changed, 102 insertions(+), 27 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-04 12:38:18 EST (Fri, 04 Jan 2013)
@@ -373,10 +373,12 @@
\note Exception-safety: basic
\param value The value which will be removed from the container.
+
+ \return 1 if the value was removed, 0 otherwise.
*/
- inline void remove(value_type const& value)
+ inline size_type remove(value_type const& value)
{
- this->raw_remove(value);
+ return this->raw_remove(value);
}
/*!
@@ -386,12 +388,16 @@
\param first The beginning of the range of values.
\param last The end of the range of values.
+
+ \return The number of removed values.
*/
template <typename Iterator>
- inline void remove(Iterator first, Iterator last)
+ inline size_type remove(Iterator first, Iterator last)
{
+ size_type result = 0;
for ( ; first != last ; ++first )
- this->raw_remove(*first);
+ result += this->raw_remove(*first);
+ return result;
}
/*!
@@ -400,13 +406,17 @@
\note Exception-safety: basic
\param rng The range of values.
+
+ \return The number of removed values.
*/
template <typename Range>
- inline void remove(Range const& rng)
+ inline size_type remove(Range const& rng)
{
+ size_type result = 0;
typedef typename boost::range_const_iterator<Range>::type It;
for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
- this->raw_remove(*it);
+ result += this->raw_remove(*it);
+ return result;
}
/*!
@@ -787,7 +797,7 @@
\param value The value which will be removed from the container.
*/
- inline void raw_remove(value_type const& value)
+ inline size_type raw_remove(value_type const& value)
{
// TODO: awulkiew - assert for correct value (indexable) ?
BOOST_GEOMETRY_INDEX_ASSERT(m_root, "The root must exist");
@@ -806,6 +816,8 @@
// TODO
// If exception is thrown, m_values_count may be invalid
--m_values_count;
+
+ return remove_v.is_value_removed() ? 1 : 0;
}
/*!
@@ -1005,11 +1017,14 @@
\param tree The spatial index.
\param v The value which will be removed from the index.
+
+\return 1 if value was removed, 0 otherwise.
*/
template <typename Value, typename Options, typename Translator, typename Allocator>
-inline void remove(rtree<Value, Options, Translator, Allocator> & tree, Value const& v)
+inline typename rtree<Value, Options, Translator, Allocator>::size_type
+remove(rtree<Value, Options, Translator, Allocator> & tree, Value const& v)
{
- tree.remove(v);
+ return tree.remove(v);
}
/*!
@@ -1018,11 +1033,14 @@
\param tree The spatial index.
\param first The beginning of the range of values.
\param last The end of the range of values.
+
+\return The number of removed values.
*/
template<typename Value, typename Options, typename Translator, typename Allocator, typename Iterator>
-inline void remove(rtree<Value, Options, Translator, Allocator> & tree, Iterator first, Iterator last)
+inline typename rtree<Value, Options, Translator, Allocator>::size_type
+remove(rtree<Value, Options, Translator, Allocator> & tree, Iterator first, Iterator last)
{
- tree.remove(first, last);
+ return tree.remove(first, last);
}
/*!
@@ -1030,11 +1048,14 @@
\param tree The spatial index.
\param rng The range of values.
+
+\return The number of removed values.
*/
template<typename Value, typename Options, typename Translator, typename Allocator, typename Range>
-inline void remove(rtree<Value, Options, Translator, Allocator> & tree, Range const& rng)
+inline typename rtree<Value, Options, Translator, Allocator>::size_type
+remove(rtree<Value, Options, Translator, Allocator> & tree, Range const& rng)
{
- tree.remove(rng);
+ return tree.remove(rng);
}
/*!
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 2013-01-04 12:38:18 EST (Fri, 04 Jan 2013)
@@ -109,7 +109,6 @@
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");
// reinsert elements from removed nodes (underflows)
reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc)
@@ -159,6 +158,11 @@
}
}
+ bool is_value_removed() const
+ {
+ return m_is_value_removed;
+ }
+
private:
typedef std::vector< std::pair<size_t, node*> > UnderflowNodes;
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-04 12:38:18 EST (Fri, 04 Jan 2013)
@@ -446,6 +446,42 @@
}
};
+// generate_value_outside
+
+template <typename Value, size_t Dimension>
+struct generate_value_outside_impl
+{};
+
+template <typename Value>
+struct generate_value_outside_impl<Value, 2>
+{
+ static Value apply()
+ {
+ //TODO - for size > 1 in generate_input<> this won't be outside
+ return generate_value<Value>::apply(13, 26);
+ }
+};
+
+template <typename Value>
+struct generate_value_outside_impl<Value, 3>
+{
+ static Value apply()
+ {
+ //TODO - for size > 1 in generate_input<> this won't be outside
+ return generate_value<Value>::apply(13, 26, 13);
+ }
+};
+
+template <typename Rtree>
+inline typename Rtree::value_type
+generate_value_outside()
+{
+ typedef typename Rtree::value_type V;
+ typedef typename Rtree::indexable_type I;
+
+ return generate_value_outside_impl<V, bgi::traits::dimension<I>::value>::apply();
+}
+
template<typename Value, typename Algo, typename Box>
void generate_rtree(bgi::rtree<Value, Algo> & tree, std::vector<Value> & input, Box & qbox)
{
@@ -1006,56 +1042,69 @@
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();
+ // Add value which is not stored in the Rtree
+ Value outsider = generate_value_outside<T>();
+ values_to_remove.push_back(outsider);
+
{
T t(tree);
+ size_t r = 0;
BOOST_FOREACH(Value const& v, values_to_remove)
- t.remove(v);
+ r += t.remove(v);
+ BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
- BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
{
T t(tree);
- t.remove(values_to_remove.begin(), values_to_remove.end());
+ size_t r = t.remove(values_to_remove.begin(), values_to_remove.end());
+ BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
- BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
{
T t(tree);
- t.remove(values_to_remove);
+ size_t r = t.remove(values_to_remove);
+ BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
- BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
{
T t(tree);
+ size_t r = 0;
BOOST_FOREACH(Value const& v, values_to_remove)
- bgi::remove(t, v);
+ r += bgi::remove(t, v);
+ BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
- BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
{
T t(tree);
- bgi::remove(t, values_to_remove.begin(), values_to_remove.end());
+ size_t r = bgi::remove(t, values_to_remove.begin(), values_to_remove.end());
+ BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
- BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
{
T t(tree);
- bgi::remove(t, values_to_remove);
+ size_t r = bgi::remove(t, values_to_remove);
+ BOOST_CHECK( r == expected_removed_count );
std::vector<Value> output;
bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
- BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ BOOST_CHECK( output.size() == tree.size() - expected_removed_count );
test_compare_outputs(t, output, expected_output);
}
}
@@ -1222,9 +1271,10 @@
BOOST_FOREACH(Value const& v, values_to_remove)
{
- t.remove(v);
+ size_t r = t.remove(v);
--values_count;
+ BOOST_CHECK(1 == r);
BOOST_CHECK(Value::counter() == values_count);
BOOST_CHECK(t.size() + rest_count == values_count);
}