Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81940 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-12-14 09:49:46

Author: awulkiew
Date: 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
New Revision: 81940
URL: http://svn.boost.org/trac/boost/changeset/81940

Log:
Rtree value_type must no longer have default ctor defined.

Added static_vector::assign(), added assertion in static_vector::resize().
Added test for value without default ctor..
Text files modified:
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 45 ++++++++++-----
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 6 -
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 5 +
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp | 7 +-
   sandbox-branches/geometry/index/boost/geometry/extensions/index/static_vector.hpp | 45 +++++++++------
   sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 116 +++++++++++++++++++++++++++++++++++----
   6 files changed, 168 insertions(+), 56 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
@@ -60,19 +60,22 @@
 geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center);

 // fill the container of centers' distances of children from current node's center
- typename index::detail::rtree::container_from_elements_type<
+ typedef typename index::detail::rtree::container_from_elements_type<
 elements_type,
 std::pair<distance_type, element_type>
- >::type sorted_elements;
+ >::type sorted_elements_type;
+ sorted_elements_type sorted_elements;
 // If constructor is used instead of resize() MS implementation leaks here
- sorted_elements.resize(elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
+ sorted_elements.reserve(elements_count); // MAY THROW, STRONG (V, E: alloc, copy)

- for ( size_t i = 0 ; i < elements_count ; ++i )
+ for ( typename elements_type::const_iterator it = elements.begin() ;
+ it != elements.end() ; ++it )
 {
 point_type element_center;
- geometry::centroid( rtree::element_indexable(elements[i], translator), element_center);
- sorted_elements[i].first = geometry::comparable_distance(node_center, element_center);
- sorted_elements[i].second = elements[i]; // MAY THROW (V, E: copy)
+ geometry::centroid( rtree::element_indexable(*it, translator), element_center);
+ sorted_elements.push_back(std::make_pair(
+ geometry::comparable_distance(node_center, element_center),
+ *it)); // MAY THROW (V, E: copy)
 }

 // sort elements by distances from center
@@ -83,24 +86,34 @@
 distances_dsc<distance_type, element_type>); // MAY THROW, BASIC (V, E: copy)

 // copy elements which will be reinserted
- result_elements.resize(reinserted_elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
- for ( size_t i = 0 ; i < reinserted_elements_count ; ++i )
- result_elements[i] = sorted_elements[i].second; // MAY THROW (V, E: copy)
+ result_elements.clear();
+ result_elements.reserve(reinserted_elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
+ for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() ;
+ it != sorted_elements.begin() + reinserted_elements_count ; ++it )
+ {
+ result_elements.push_back(it->second); // MAY THROW (V, E: copy)
+ }

 try
 {
 // copy remaining elements to the current node
- size_t elements_new_count = elements_count - reinserted_elements_count;
- elements.resize(elements_new_count); // SHOULDN'T THROW (new_size <= old size)
- for ( size_t i = 0 ; i < elements_new_count ; ++i )
- elements[i] = sorted_elements[i + reinserted_elements_count].second; // MAY THROW (V, E: copy)
+ elements.clear();
+ elements.reserve(elements_count - reinserted_elements_count); // SHOULDN'T THROW (new_size <= old size)
+ for ( typename sorted_elements_type::const_iterator it = sorted_elements.begin() + reinserted_elements_count;
+ it != sorted_elements.end() ; ++it )
+ {
+ elements.push_back(it->second); // MAY THROW (V, E: copy)
+ }
 }
 catch(...)
 {
 elements.clear();

- for ( size_t i = 0 ; i < elements_count ; ++i )
- destroy_element<Value, Options, Translator, Box, Allocators>::apply(sorted_elements[i].second, allocators);
+ for ( typename sorted_elements_type::iterator it = sorted_elements.begin() ;
+ it != sorted_elements.end() ; ++it )
+ {
+ destroy_element<Value, Options, Translator, Box, Allocators>::apply(it->second, allocators);
+ }

 throw; // RETHROW
 }

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
@@ -382,10 +382,8 @@
 try
 {
 // copy elements to nodes
- elements1.resize(split_index); // SHOULDN'T THROW
- std::copy(elements_copy.begin(), elements_copy.begin() + split_index, elements1.begin()); // MAY THROW, BASIC
- elements2.resize(parameters.get_max_elements() + 1 - split_index); // MAY THROW, STRONG
- std::copy(elements_copy.begin() + split_index, elements_copy.end(), elements2.begin()); // MAY THROW, BASIC
+ elements1.assign(elements_copy.begin(), elements_copy.begin() + split_index); // MAY THROW, BASIC
+ elements2.assign(elements_copy.begin() + split_index, elements_copy.end()); // MAY THROW, BASIC

 // calculate boxes
 box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator);

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 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
@@ -873,7 +873,7 @@
 point_type
> result_type;

- result_type result;
+ result_type result(v);

 detail::rtree::visitors::nearest_query<
 value_type,
@@ -888,7 +888,8 @@

 detail::rtree::apply_visitor(nearest_v, *m_root);

- return result.get(v);
+ //return result.get(v);
+ return result.is_comparable_distance_valid() ? 1 : 0;
 }

 /*!

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
@@ -33,8 +33,9 @@
 typename translator::indexable_type<Translator>::type
>::type distance_type;

- inline nearest_query_result_one()
- : m_comp_dist((std::numeric_limits<distance_type>::max)())
+ inline nearest_query_result_one(Value & value)
+ : m_value(value)
+ , m_comp_dist((std::numeric_limits<distance_type>::max)())
 {}

 inline void store(Value const& val, distance_type const& curr_comp_dist)
@@ -63,7 +64,7 @@
 }

private:
- Value m_value;
+ Value & m_value;
 distance_type m_comp_dist;
};

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/static_vector.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/static_vector.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/static_vector.hpp 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
@@ -73,24 +73,7 @@
 {
 //BOOST_ASSERT_MSG(other.m_size <= Capacity, "capacity too small");

- if ( m_size <= other.m_size )
- {
- this->copy(other.ptr(0), other.ptr(m_size), this->ptr(0),
- boost::has_trivial_assign<value_type>()); // may throw
-
- this->uninitialized_copy(other.ptr(m_size), other.ptr(other.m_size), this->ptr(m_size),
- boost::has_trivial_copy<value_type>()); // may throw
- m_size = other.m_size;
- }
- else
- {
- this->copy(other.ptr(0), other.ptr(other.m_size), this->ptr(0),
- boost::has_trivial_assign<value_type>()); // may throw
-
- this->destroy(this->ptr(other.m_size), this->ptr(m_size),
- boost::has_trivial_destructor<value_type>());
- m_size = other.m_size;
- }
+ this->assign(other->ptr(0), other->ptr(other.m_size));

 return *this;
 }
@@ -113,6 +96,7 @@
 }
 else
 {
+ BOOST_ASSERT_MSG(s <= Capacity, "size can't exceed the capacity");
 this->uninitialized_fill(this->ptr(m_size), this->ptr(s), value); // may throw
 m_size = s;
 }
@@ -143,6 +127,31 @@
 this->destroy(this->ptr(m_size), boost::has_trivial_destructor<value_type>());
 }

+ // basic
+ void assign(const value_type * first, const value_type * last)
+ {
+ size_type s = std::distance(first, last);
+
+ if ( m_size <= s )
+ {
+ this->copy(first, first + m_size, this->ptr(0),
+ boost::has_trivial_assign<value_type>()); // may throw
+
+ this->uninitialized_copy(first + m_size, last, this->ptr(m_size),
+ boost::has_trivial_copy<value_type>()); // may throw
+ m_size = s;
+ }
+ else
+ {
+ this->copy(first, last, this->ptr(0),
+ boost::has_trivial_assign<value_type>()); // may throw
+
+ this->destroy(this->ptr(s), this->ptr(m_size),
+ boost::has_trivial_destructor<value_type>());
+ m_size = s;
+ }
+ }
+
 // nothrow
 void clear()
 {

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 2012-12-14 09:49:45 EST (Fri, 14 Dec 2012)
@@ -50,6 +50,14 @@
 }
};

+// Default value generation
+
+template <typename Value>
+struct generate_value_default
+{
+ static Value apply(){ return Value(); }
+};
+
// Values, input and rtree generation

template <typename Value>
@@ -225,10 +233,11 @@
{
 typedef bg::model::point<T, 2, C> P;
 typedef test_object O;
+ typedef boost::shared_ptr<O> R;

- static boost::shared_ptr<O> apply(int x, int y)
+ static R apply(int x, int y)
 {
- return boost::shared_ptr<O>(new O(P(x, y)));
+ return R(new O(P(x, y)));
 }
};

@@ -237,10 +246,11 @@
{
 typedef bg::model::point<T, 3, C> P;
 typedef test_object O;
+ typedef boost::shared_ptr<O> R;

- static boost::shared_ptr<O> apply(int x, int y, int z)
+ static R apply(int x, int y, int z)
 {
- return boost::shared_ptr<O>(new O(P(x, y, z)));
+ return R(new O(P(x, y, z)));
 }
};

@@ -283,14 +293,16 @@
struct generate_value< counting_value<bg::model::point<T, 2, C> > >
{
 typedef bg::model::point<T, 2, C> P;
- static counting_value apply(int x, int y) { return counting_value(P(x, y)); }
+ typedef counting_value R;
+ static R apply(int x, int y) { return R(P(x, y)); }
};

template <typename T, typename C>
struct generate_value< counting_value<bg::model::point<T, 3, C> > >
{
 typedef bg::model::point<T, 3, C> P;
- static counting_value apply(int x, int y, int z) { return counting_value(P(x, y, z)); }
+ typedef counting_value R;
+ static R apply(int x, int y, int z) { return R(P(x, y, z)); }
};

template <typename T, typename C>
@@ -298,7 +310,8 @@
{
 typedef bg::model::point<T, 2, C> P;
 typedef bg::model::box B;
- static counting_value apply(int x, int y) { return counting_value(B(P(x, y), P(x+2, y+3))); }
+ typedef counting_value R;
+ static R apply(int x, int y) { return R(B(P(x, y), P(x+2, y+3))); }
};

template <typename T, typename C>
@@ -306,7 +319,78 @@
{
 typedef bg::model::point<T, 3, C> P;
 typedef bg::model::box B;
- static counting_value apply(int x, int y, int z) { return counting_value(B(P(x, y, z), P(x+2, y+3, z+4))); }
+ typedef counting_value R;
+ static R apply(int x, int y, int z) { return R(B(P(x, y, z), P(x+2, y+3, z+4))); }
+};
+
+// value without default constructor
+
+template <typename Indexable>
+struct value_no_dctor
+{
+ value_no_dctor(Indexable const& i) : indexable(i) {}
+ Indexable indexable;
+};
+
+namespace boost { namespace geometry { namespace index { namespace translator {
+
+ template <typename Indexable>
+ struct def< value_no_dctor<Indexable> >
+ {
+ typedef value_no_dctor<Indexable> value_type;
+ typedef Indexable const& result_type;
+
+ result_type operator()(value_type const& value) const
+ {
+ return value.indexable;
+ }
+
+ bool equals(value_type const& v1, value_type const& v2) const
+ {
+ return boost::geometry::equals(v1.indexable, v2.indexable);
+ }
+ };
+
+}}}}
+
+template <typename Indexable>
+struct generate_value_default< value_no_dctor<Indexable> >
+{
+ static value_no_dctor<Indexable> apply() { return value_no_dctor<Indexable>(Indexable()); }
+};
+
+template <typename T, typename C>
+struct generate_value< value_no_dctor<bg::model::point<T, 2, C> > >
+{
+ typedef bg::model::point<T, 2, C> P;
+ typedef value_no_dctor R;
+ static R apply(int x, int y) { return R(P(x, y)); }
+};
+
+template <typename T, typename C>
+struct generate_value< value_no_dctor<bg::model::point<T, 3, C> > >
+{
+ typedef bg::model::point<T, 3, C> P;
+ typedef value_no_dctor R;
+ static R apply(int x, int y, int z) { return R(P(x, y, z)); }
+};
+
+template <typename T, typename C>
+struct generate_value< value_no_dctor<bg::model::box<bg::model::point<T, 2, C> > > >
+{
+ typedef bg::model::point<T, 2, C> P;
+ typedef bg::model::box B;
+ typedef value_no_dctor R;
+ static R apply(int x, int y) { return R(B(P(x, y), P(x+2, y+3))); }
+};
+
+template <typename T, typename C>
+struct generate_value< value_no_dctor<bg::model::box<bg::model::point<T, 3, C> > > >
+{
+ typedef bg::model::point<T, 3, C> P;
+ typedef bg::model::box B;
+ typedef value_no_dctor R;
+ static R apply(int x, int y, int z) { return R(B(P(x, y, z), P(x+2, y+3, z+4))); }
};

// generate input
@@ -625,7 +709,7 @@

 typedef typename bg::default_distance_result<Point, typename Rtree::indexable_type>::type D;
 D smallest_d = (std::numeric_limits<D>::max)();
- Value expected_output;
+ Value expected_output(generate_value_default<Value>::apply());
 BOOST_FOREACH(Value const& v, input)
 {
 D d = bgi::comparable_distance_near(pt, rtree.translator()(v));
@@ -637,7 +721,7 @@
 }
 size_t n = ( (std::numeric_limits<D>::max)() == smallest_d ) ? 0 : 1;

- Value output;
+ Value output(generate_value_default<Value>::apply());
 size_t n_res = rtree.nearest_query(pt, output);

 BOOST_CHECK(n == n_res);
@@ -711,7 +795,7 @@
 biggest_d = test_output.back().first;

 // transform test output to vector of values
- std::vector<Value> expected_output(test_output.size());
+ std::vector<Value> expected_output(test_output.size(), generate_value_default<Value>::apply());
 std::transform(test_output.begin(), test_output.end(), expected_output.begin(), TestNearestKTransform<Rtree, Point>());

 // calculate output using rtree
@@ -744,11 +828,12 @@
template <typename Rtree, typename Point, typename CoordinateType>
void test_nearest_query_not_found(Rtree const& rtree, Point const& pt, CoordinateType max_distance_1, CoordinateType max_distance_k)
{
- typename Rtree::value_type output;
+ typedef typename Rtree::value_type Value;
+ Value output(generate_value_default<Value>::apply());
 size_t n_res = rtree.nearest_query(bgi::max_bounded(pt, max_distance_1), output);
 BOOST_CHECK(0 == n_res);

- std::vector<typename Rtree::value_type> output_v;
+ std::vector<Value> output_v;
 n_res = rtree.nearest_query(bgi::max_bounded(pt, max_distance_k), 5, std::back_inserter(output_v));
 BOOST_CHECK(output_v.size() == n_res);
 BOOST_CHECK(n_res < 5);
@@ -1159,12 +1244,14 @@
 typedef std::pair<Point, int> PairP;
 typedef boost::tuple<Point, int, int> TupleP;
 typedef boost::shared_ptr< test_object<Point> > SharedPtrP;
+ typedef value_no_dctor<Point> VNoDCtor;

 test_rtree_by_value<Point, Parameters>(parameters);
 test_rtree_by_value<PairP, Parameters>(parameters);
 test_rtree_by_value<TupleP, Parameters>(parameters);

 test_rtree_by_value<SharedPtrP, Parameters>(parameters);
+ test_rtree_by_value<VNoDCtor, Parameters>(parameters);

 test_count_rtree_values<Point>(parameters);
}
@@ -1175,11 +1262,14 @@
 typedef bg::model::box<Point> Box;
 typedef std::pair<Box, int> PairB;
 typedef boost::tuple<Box, int, int> TupleB;
+ typedef value_no_dctor<Box> VNoDCtor;

 test_rtree_by_value<Box, Parameters>(parameters);
 test_rtree_by_value<PairB, Parameters>(parameters);
 test_rtree_by_value<TupleB, Parameters>(parameters);

+ test_rtree_by_value<VNoDCtor, Parameters>(parameters);
+
 test_count_rtree_values<Box>(parameters);
}

Date view	Thread view	Subject view	Author view

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