Subject: [Boost-commit] svn:boost r72619 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-06-16 19:10:13
Author: awulkiew
Date: 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
New Revision: 72619
URL: http://svn.boost.org/trac/boost/changeset/72619
Log:
Static parameters are now used everywhere in the code. Further optimizations implemented in quadratic redistribute_elements. Some errors corrected in pushable_array.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp | 33 +++++++++++++++++++++++++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp | 7 +++++
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 48 +++++++++++++++++++++++----------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 15 -----------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 6 ++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/print.hpp | 6 ++--
sandbox-branches/geometry/index/tests/additional_glut_vis.cpp | 2
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 6 ++--
sandbox-branches/geometry/index/tests/main.cpp | 5 ++-
sandbox-branches/geometry/index/tests/rtree_filters.hpp | 2
sandbox-branches/geometry/index/tests/rtree_native.hpp | 17 +++++++------
sandbox-branches/geometry/index/tests/translators.hpp | 2
12 files changed, 90 insertions(+), 59 deletions(-)
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-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -26,16 +26,23 @@
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 pushable_array(size_type s, Element const& v)
+ inline explicit pushable_array(size_type s)
: m_size(s)
{
- BOOST_GEOMETRY_INDEX_ASSERT(s < Capacity, "size too big");
- std::fill(m_array.begin(), m_array.begin() + s, v);
+ 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)
@@ -94,6 +101,26 @@
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;
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-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -30,6 +30,12 @@
struct default_variant_tag {};
struct default_static_tag {};
+// TODO: awulkiew - implement those:
+//if ( 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;
+
template <size_t MaxElements, size_t MinElements>
struct linear
{
@@ -86,6 +92,7 @@
template <typename Tag>
struct options_type
{
+ // TODO: awulkiew - use static assert
typedef void type;
};
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -27,7 +27,7 @@
namespace quadratic {
-template <typename Elements, typename Translator, typename Box>
+template <typename Elements, typename Parameters, typename Translator, typename Box>
struct pick_seeds
{
typedef typename Elements::value_type element_type;
@@ -41,9 +41,9 @@
size_t & seed1,
size_t & seed2)
{
- size_t elements_count = elements.size();
-
- BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "wrong number of elements");
+ const size_t elements_count = Parameters::max_elements + 1;
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
+ BOOST_STATIC_ASSERT(2 <= elements_count);
area_type greatest_free_area = 0;
seed1 = 0;
@@ -78,9 +78,11 @@
template <typename Value, typename Options, typename Translator, typename Box>
struct redistribute_elements<Value, Options, Translator, Box, quadratic_tag>
{
- 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 rtree::node<Value, parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, parameters_type, Box, typename Options::node_tag>::type leaf;
typedef typename index::default_area_result<Box>::type area_type;
@@ -89,8 +91,6 @@
Node & second_node,
Box & box1,
Box & box2,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -98,19 +98,26 @@
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
+ const size_t elements1_count = parameters_type::max_elements + 1;
+
+ typedef index::pushable_array<element_type, elements1_count> elements_copy_type;
+
+ BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
+
// copy original elements
- elements_type elements_copy = rtree::elements(n);
+ elements_copy_type elements_copy(elements1_count);
+ std::copy(elements1.begin(), elements1.end(), elements_copy.begin());
// calculate initial seeds
size_t seed1 = 0;
size_t seed2 = 0;
- quadratic::pick_seeds<elements_type, Translator, Box>::apply(elements_copy, tr, seed1, seed2);
+ quadratic::pick_seeds<elements_copy_type, parameters_type, Translator, Box>::apply(elements_copy, tr, seed1, seed2);
// prepare nodes' elements containers
- elements_type & elements1 = rtree::elements(n);
- elements_type & elements2 = rtree::elements(second_node);
elements1.clear();
- assert(elements2.empty());
+ BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
// add seeds
elements1.push_back(elements_copy[seed1]);
@@ -141,7 +148,7 @@
// redistribute the rest of the elements
while ( !elements_copy.empty() )
{
- typename elements_type::reverse_iterator el_it = elements_copy.rbegin();
+ typename elements_copy_type::reverse_iterator el_it = elements_copy.rbegin();
bool insert_into_group1 = false;
size_t elements1_count = elements1.size();
@@ -149,11 +156,11 @@
// if there is small number of elements left and the number of elements in node is lesser than min_elems
// just insert them to this node
- if ( elements1_count + remaining <= min_elems )
+ if ( elements1_count + remaining <= parameters_type::min_elements )
{
insert_into_group1 = true;
}
- else if ( elements2_count + remaining <= min_elems )
+ else if ( elements2_count + remaining <= parameters_type::min_elements )
{
insert_into_group1 = false;
}
@@ -196,10 +203,11 @@
area2 = index::area(box2);
}
- assert(!elements_copy.empty());
- elements_copy.erase(--el_it.base());
+ BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
+ typename elements_copy_type::iterator el_it_base = el_it.base();
+ elements_copy.erase(--el_it_base);
- assert(0 < remaining);
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
--remaining;
}
}
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-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -56,23 +56,12 @@
typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, node_tag>::type internal_node;
typedef typename detail::rtree::leaf<value_type, typename options_type::parameters_type, box_type, node_tag>::type leaf;
- inline explicit rtree(
- size_t max_elems_per_node = 4,
- size_t min_elems_per_node = 2,
- translator_type const& translator = translator_type()
- )
+ inline explicit rtree(translator_type const& translator = translator_type())
: m_values_count(0)
- , m_max_elems_per_node(max_elems_per_node)
- , m_min_elems_per_node(min_elems_per_node)
, m_root(0)
, m_leafs_level(0)
, m_translator(translator)
{
- if ( 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_root = detail::rtree::create_node(leaf());
}
@@ -154,8 +143,6 @@
private:
size_t m_values_count;
- size_t m_max_elems_per_node;
- size_t m_min_elems_per_node;
node *m_root;
size_t m_leafs_level;
translator_type m_translator;
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-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -94,10 +94,10 @@
} // namespace detail
template <typename Value, typename Options, typename Translator, typename Box>
-struct gl_draw : public rtree::visitor<Value, Box, typename Options::node_tag, true>::type
+struct gl_draw : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
{
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ 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 gl_draw(Translator const& t,
size_t level_first = 0,
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-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -112,10 +112,10 @@
} // namespace detail
template <typename Value, typename Options, typename Translator, typename Box>
-struct print : public rtree::visitor<Value, Box, typename Options::node_tag, true>::type
+struct print : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
{
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ 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 print(std::ostream & o, Translator const& t)
: os(o), tr(t), level(0)
Modified: sandbox-branches/geometry/index/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_glut_vis.cpp 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -22,7 +22,7 @@
//boost::geometry::index::rtree<B> t(2, 1);
boost::geometry::index::rtree<
B,
- boost::geometry::index::rstar_tag> t(4, 2);
+ boost::geometry::index::rstar<4, 2> > t;
std::vector<B> vect;
void render_scene(void)
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-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -29,8 +29,8 @@
typedef bg::model::point<float, 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::quadratic<32, 8> > RT;
- typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar<32, 8, true> > 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, true> > RT;
/*typedef bgi::rtree<
std::pair<B, size_t>,
bgi::options::rtree<bgi::linear<32, 8>, bgi::insert_tag, bgi::choose_by_area_diff_tag, bgi::linear_tag, bgi::default_static_tag>
@@ -106,7 +106,7 @@
}
// create rtree
- RT t(max_elems, min_elems);
+ RT t;
// elements inserting test
{
Modified: sandbox-branches/geometry/index/tests/main.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/main.cpp (original)
+++ sandbox-branches/geometry/index/tests/main.cpp 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -16,8 +16,9 @@
int main()
{
tests_translators_hpp();
- tests_rtree_native_hpp<boost::geometry::index::linear_tag>();
- tests_rtree_native_hpp<boost::geometry::index::quadratic_tag>();
+ 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_filters_hpp();
/*
{
Modified: sandbox-branches/geometry/index/tests/rtree_filters.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/rtree_filters.hpp (original)
+++ sandbox-branches/geometry/index/tests/rtree_filters.hpp 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -37,7 +37,7 @@
typedef boost::geometry::model::box<P> B;
{
- boost::geometry::index::rtree<B> t(4, 2);
+ boost::geometry::index::rtree<B, boost::geometry::index::rstar<4, 2> > t;
boost::geometry::index::insert(t, B(P(0, 0), P(1, 1)));
boost::geometry::index::insert(t, B(P(2, 2), P(3, 3)));
boost::geometry::index::insert(t, B(P(4, 4), P(5, 5)));
Modified: sandbox-branches/geometry/index/tests/rtree_native.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/rtree_native.hpp (original)
+++ sandbox-branches/geometry/index/tests/rtree_native.hpp 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -13,7 +13,7 @@
#include <map>
-template <typename Tag>
+template <typename Options>
void tests_rtree_native_hpp()
{
std::cout << "tests/rtree_native.hpp\n";
@@ -23,7 +23,7 @@
typedef boost::geometry::model::point<float, 3, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- boost::geometry::index::rtree<B, Tag> t(4, 2);
+ boost::geometry::index::rtree<B, Options> t;
boost::geometry::index::insert(t, B(P(0, 0, 0), P(1, 1, 1)));
boost::geometry::index::insert(t, B(P(2, 2, 2), P(3, 3, 3)));
boost::geometry::index::insert(t, B(P(4, 4, 4), P(5, 5, 5)));
@@ -40,7 +40,7 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- boost::geometry::index::rtree<B, Tag> t(4, 2);
+ boost::geometry::index::rtree<B, Options> t;
boost::geometry::index::insert(t, B(P(0, 0), P(1, 1)));
boost::geometry::index::insert(t, B(P(2, 2), P(3, 3)));
boost::geometry::index::insert(t, B(P(4, 4), P(5, 5)));
@@ -57,7 +57,7 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- boost::geometry::index::rtree<P, Tag> t(4, 2);
+ boost::geometry::index::rtree<P, Options> t;
boost::geometry::index::insert(t, P(0, 0));
boost::geometry::index::insert(t, P(2, 2));
boost::geometry::index::insert(t, P(4, 4));
@@ -75,7 +75,7 @@
typedef boost::geometry::model::box<P> B;
typedef std::pair<B, int> V;
- boost::geometry::index::rtree<V, Tag> t(4, 2);
+ boost::geometry::index::rtree<V, Options> t;
boost::geometry::index::insert(t, V(B(P(0, 0), P(1, 1)), 0));
boost::geometry::index::insert(t, V(B(P(2, 2), P(3, 3)), 1));
boost::geometry::index::insert(t, V(B(P(4, 4), P(5, 5)), 2));
@@ -100,7 +100,7 @@
V v4( new std::pair<B, int>(B(P(6, 6), P(7, 7)), 3) );
V v5( new std::pair<B, int>(B(P(8, 8), P(9, 9)), 4) );
- boost::geometry::index::rtree<V, Tag> t(4, 2);
+ boost::geometry::index::rtree<V, Options> t;
boost::geometry::index::insert(t, v1);
boost::geometry::index::insert(t, v2);
boost::geometry::index::insert(t, v3);
@@ -126,7 +126,7 @@
m.insert(std::pair<int, B>(3, B(P(6, 6), P(7, 7))));
m.insert(std::pair<int, B>(4, B(P(8, 8), P(9, 9))));
- boost::geometry::index::rtree<V, Tag> t(4, 2);
+ boost::geometry::index::rtree<V, Options> t;
V vit = m.begin();
boost::geometry::index::insert(t, vit++);
boost::geometry::index::insert(t, vit++);
@@ -154,7 +154,8 @@
v.push_back(B(P(6, 6), P(7, 7)));
v.push_back(B(P(8, 8), P(9, 9)));
- boost::geometry::index::rtree<V, Tag, Tr> t(4, 2, Tr(v));
+ Tr tr(v);
+ boost::geometry::index::rtree<V, Options, Tr> t(tr);
boost::geometry::index::insert(t, 0u);
boost::geometry::index::insert(t, 1u);
Modified: sandbox-branches/geometry/index/tests/translators.hpp
==============================================================================
--- sandbox-branches/geometry/index/tests/translators.hpp (original)
+++ sandbox-branches/geometry/index/tests/translators.hpp 2011-06-16 19:10:10 EDT (Thu, 16 Jun 2011)
@@ -35,7 +35,7 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- typedef boost::geometry::index::rtree<B> I;
+ //typedef boost::geometry::index::rtree<B> I;
using namespace boost::geometry;