|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r71915 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/node boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-13 06:59:51
Author: awulkiew
Date: 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
New Revision: 71915
URL: http://svn.boost.org/trac/boost/changeset/71915
Log:
polymorphic node type added and used as default
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/node_poly.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/node_variant.hpp (contents, props changed)
Removed:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/load.hpp
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/save.hpp
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 6
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp | 148 ++++-----------------------------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 8 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 113 +++++++++++++-----------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 8 -
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 14 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 50 ++++++++-----
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/destroy.hpp | 10 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp | 8 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 8 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 48 ++++--------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp | 12 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp | 8 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 32 ++++----
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 37 +++++----
15 files changed, 188 insertions(+), 322 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -195,7 +195,7 @@
typedef typename index::default_area_result<Box>::type area_type;
// copy original elements
- elements_type elements_copy = rtree::elements_get(n);
+ elements_type elements_copy = rtree::elements(n);
size_t elements_count = elements_copy.size();
// calculate initial seeds
@@ -204,8 +204,8 @@
linear::pick_seeds<elements_type, Translator>::apply(elements_copy, tr, seed1, seed2);
// prepare nodes' elements containers
- elements_type & elements1 = rtree::elements_get(n);
- elements_type & elements2 = rtree::elements_get(second_node);
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
elements1.clear();
assert(elements2.empty());
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -1,6 +1,6 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
-// Boost.Index - R-tree default nodes
+// Boost.Index - R-tree nodes
//
// Copyright 2011 Adam Wulkiewicz.
// Use, modification and distribution is subject to the Boost Software License,
@@ -10,62 +10,21 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_HPP
-#include <vector>
-#include <boost/variant.hpp>
+#ifndef BOOST_GEOMETRY_INDEX_USE_VARIANT_NODES
-namespace boost { namespace geometry { namespace index {
-
-namespace detail { namespace rtree {
+#include <boost/geometry/extensions/index/rtree/node/node_poly.hpp>
-template <typename Value, typename Box, typename Tag>
-struct node;
-
-// nodes default types
-
-template <typename Value, typename Box, typename Tag>
-struct internal_node_def
-{
- typedef std::vector<
- std::pair<
- Box,
- typename node<Value, Box, Tag>::type *
- >
- > elements_type;
-
- elements_type elements;
-};
-
-template <typename Value, typename Box, typename Tag>
-struct leaf_def
-{
- typedef std::vector<Value> elements_type;
- elements_type elements;
-};
+#else
-// nodes traits
+#include <boost/geometry/extensions/index/rtree/node/node_variant.hpp>
-template <typename Value, typename Box, typename Tag>
-struct node
-{
- typedef boost::variant<
- leaf_def<Value, Box, Tag>,
- internal_node_def<Value, Box, Tag>
- > type;
-};
+#endif // BOOST_GEOMETRY_INDEX_USE_VARIANT_NODES
-template <typename Value, typename Box, typename Tag>
-struct internal_node
-{
- typedef internal_node_def<Value, Box, Tag> type;
-};
+namespace boost { namespace geometry { namespace index {
-template <typename Value, typename Box, typename Tag>
-struct leaf
-{
- typedef leaf_def<Value, Box, Tag> type;
-};
+namespace detail { namespace rtree {
-// nodes elements extractor
+// nodes elements
template <typename Node>
struct elements_type
@@ -74,67 +33,24 @@
};
template <typename Node>
-typename elements_type<Node>::type &
-elements_get(Node & n)
+inline typename elements_type<Node>::type &
+elements(Node & n)
{
return n.elements;
}
template <typename Node>
-typename elements_type<Node>::type const&
-elements_get(Node const& n)
+inline typename elements_type<Node>::type const&
+elements(Node const& n)
{
return n.elements;
}
-//template <typename Node>
-//struct element_type
-//{
-// typedef typename elements_type<Node>::type::value_type type;
-//};
-
-// uniform indexable type for child node element's box and value's indexable
-
-template <typename Value, typename Translator>
-struct element_indexable_type
-{
- typedef typename Translator::indexable_type type;
-};
-
-template <typename Value, typename Box, typename Tag, typename Translator>
-struct element_indexable_type<
- std::pair<
- Box,
- boost::variant<
- leaf_def<Value, Box, Tag>,
- internal_node_def<Value, Box, Tag>
- > *
- >,
- Translator
->
-{
- typedef Box type;
-};
-
// uniform indexable getter for child node element's box and value's indexable
-
-template <typename Value, typename Box, typename Tag, typename Translator>
-Box const&
-element_indexable(
- std::pair<
- Box,
- boost::variant<
- leaf_def<Value, Box, Tag>,
- internal_node_def<Value, Box, Tag>
- > *
- > const& el,
- Translator const&)
-{
- return el.first;
-}
+// value's indexable version
template <typename Value, typename Translator>
-typename Translator::indexable_type const&
+inline typename Translator::indexable_type const&
element_indexable(Value const& el, Translator const& tr)
{
return tr(el);
@@ -162,40 +78,6 @@
return result;
}
-// create leaf node
-
-template <typename Value, typename Box, typename Tag>
-typename node<Value, Box, Tag>::type *
-create_node(leaf_def<Value, Box, Tag> const& l)
-{
- typedef typename node<Value, Box, Tag>::type node;
- node * n = new node(l);
- return n;
-}
-
-// create internal node
-
-template <typename Value, typename Box, typename Tag>
-typename node<Value, Box, Tag>::type *
-create_node(internal_node_def<Value, Box, Tag> const& in)
-{
- typedef typename node<Value, Box, Tag>::type node;
- node * n = new node(in);
- return n;
-}
-
-// default node
-
-template <typename Value, typename Box, typename Tag>
-void delete_node(
- boost::variant<
- leaf_def<Value, Box, Tag>,
- internal_node_def<Value, Box, Tag>
- > * n)
-{
- delete n;
-}
-
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/node_poly.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/node_poly.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -0,0 +1,197 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree polymorphic nodes
+//
+// 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_NODE_NODE_POLY_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_POLY_HPP
+
+#include <vector>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree {
+
+// visitor forward declaration
+template <typename Value, typename Box, typename Tag, bool IsVisitableConst>
+struct visitor_poly;
+
+// nodes types
+
+template <typename Value, typename Box, typename Tag>
+struct node_poly
+{
+ virtual ~node_poly() {}
+ virtual void apply_visitor(visitor_poly<Value, Box, Tag, false> &) = 0;
+ virtual void apply_visitor(visitor_poly<Value, Box, Tag, true> &) const = 0;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct internal_node_poly : public node_poly<Value, Box, Tag>
+{
+ typedef std::vector<
+ std::pair<Box, node_poly<Value, Box, Tag> *>
+ > elements_type;
+
+ void apply_visitor(visitor_poly<Value, Box, Tag, false> & v) { v(*this); }
+ void apply_visitor(visitor_poly<Value, Box, Tag, true> & v) const { v(*this); }
+
+ elements_type elements;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct leaf_poly : public node_poly<Value, Box, Tag>
+{
+ typedef std::vector<Value> elements_type;
+
+ void apply_visitor(visitor_poly<Value, Box, Tag, false> & v) { v(*this); }
+ void apply_visitor(visitor_poly<Value, Box, Tag, true> & v) const { v(*this); }
+
+ elements_type elements;
+};
+
+// nodes traits
+
+template <typename Value, typename Box, typename Tag>
+struct node
+{
+ typedef node_poly<Value, Box, Tag> type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct internal_node
+{
+ typedef internal_node_poly<Value, Box, Tag> type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct leaf
+{
+ typedef leaf_poly<Value, Box, Tag> type;
+};
+
+// nodes conversion
+
+template <typename Derived, typename Value, typename Box, typename Tag>
+inline Derived & get(node_poly<Value, Box, Tag> & n)
+{
+ assert(dynamic_cast<Derived*>(&n));
+ return dynamic_cast<Derived&>(n);
+}
+
+template <typename Derived, typename Value, typename Box, typename Tag>
+inline Derived * get(node_poly<Value, Box, Tag> * n)
+{
+ assert(dynamic_cast<Derived*>(n));
+ return dynamic_cast<Derived*>(n);
+}
+
+// visitor
+
+template <typename Value, typename Box, typename Tag>
+struct visitor_poly<Value, Box, Tag, true>
+{
+ typedef typename internal_node<Value, Box, Tag>::type internal_node;
+ typedef typename leaf<Value, Box, Tag>::type leaf;
+
+ virtual ~visitor_poly() {}
+
+ virtual void operator()(internal_node const&) = 0;
+ virtual void operator()(leaf const&) = 0;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct visitor_poly<Value, Box, Tag, false>
+{
+ typedef typename internal_node<Value, Box, Tag>::type internal_node;
+ typedef typename leaf<Value, Box, Tag>::type leaf;
+
+ virtual ~visitor_poly() {}
+
+ virtual void operator()(internal_node &) = 0;
+ virtual void operator()(leaf &) = 0;
+};
+
+// visitor traits
+
+template <typename Value, typename Box, typename Tag, bool IsVisitableConst>
+struct visitor
+{
+ typedef visitor_poly<Value, Box, Tag, IsVisitableConst> type;
+};
+
+template <typename Visitor, typename Visitable>
+inline void apply_visitor(Visitor &v, Visitable & n)
+{
+ n.apply_visitor(v);
+}
+
+// uniform indexable for child node element's box and value's indexable
+
+// value's indexable version
+
+template <typename Value, typename Translator>
+struct element_indexable_type
+{
+ typedef typename Translator::indexable_type type;
+};
+
+// node element's indexable specialization
+
+template <typename Value, typename Box, typename Tag, typename Translator>
+struct element_indexable_type<
+ std::pair<Box, node_poly<Value, Box, Tag> *>,
+ Translator
+>
+{
+ typedef Box type;
+};
+
+template <typename Value, typename Box, typename Tag, typename Translator>
+inline Box const&
+element_indexable(
+ std::pair< Box, node_poly<Value, Box, Tag> *> const& el,
+ Translator const&)
+{
+ return el.first;
+}
+
+// create leaf node
+
+template <typename Value, typename Box, typename Tag>
+inline typename node<Value, Box, Tag>::type *
+ create_node(leaf_poly<Value, Box, Tag> const& l)
+{
+ typedef typename node<Value, Box, Tag>::type node;
+ node * n = new leaf_poly<Value, Box, Tag>(l);
+ return n;
+}
+
+// create internal node
+
+template <typename Value, typename Box, typename Tag>
+inline typename node<Value, Box, Tag>::type *
+ create_node(internal_node_poly<Value, Box, Tag> const& in)
+{
+ typedef typename node<Value, Box, Tag>::type node;
+ node * n = new internal_node_poly<Value, Box, Tag>(in);
+ return n;
+}
+
+// default node
+
+template <typename Value, typename Box, typename Tag>
+inline void delete_node(node_poly<Value, Box, Tag> * n)
+{
+ delete n;
+}
+
+}} // namespace detail::rtree
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_POLY_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/node_variant.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node/node_variant.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -0,0 +1,176 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree variant nodes
+//
+// 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_NODE_NODE_VARIANT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_VARIANT_HPP
+
+#include <vector>
+#include <boost/variant.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree {
+
+template <typename Value, typename Box, typename Tag>
+struct node;
+
+// nodes default types
+
+template <typename Value, typename Box, typename Tag>
+struct internal_node_variant
+{
+ typedef std::vector<
+ std::pair<
+ Box,
+ typename node<Value, Box, Tag>::type *
+ >
+ > elements_type;
+
+ elements_type elements;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct leaf_variant
+{
+ typedef std::vector<Value> elements_type;
+ elements_type elements;
+};
+
+// nodes traits
+
+template <typename Value, typename Box, typename Tag>
+struct node
+{
+ typedef boost::variant<
+ leaf_variant<Value, Box, Tag>,
+ internal_node_variant<Value, Box, Tag>
+ > type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct internal_node
+{
+ typedef internal_node_variant<Value, Box, Tag> type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct leaf
+{
+ typedef leaf_variant<Value, Box, Tag> type;
+};
+
+// nodes conversion
+
+template <typename V, typename Variant>
+inline V & get(Variant &v)
+{
+ return boost::get<V>(v);
+}
+
+template <typename V, typename Variant>
+inline V * get(Variant *v)
+{
+ return boost::get<V>(v);
+}
+
+// visitor traits
+
+template <typename Value, typename Box, typename Tag, bool IsVisitableConst>
+struct visitor
+{
+ typedef static_visitor<> type;
+};
+
+template <typename Visitor, typename Visitable>
+inline void apply_visitor(Visitor &v, Visitable &n)
+{
+ boost::apply_visitor(v, n);
+}
+
+// uniform indexable for child node element's box and value's indexable
+
+// value's indexable version
+
+template <typename Value, typename Translator>
+struct element_indexable_type
+{
+ typedef typename Translator::indexable_type type;
+};
+
+// node element's indexable specialization
+
+template <typename Value, typename Box, typename Tag, typename Translator>
+struct element_indexable_type<
+ std::pair<
+ Box,
+ boost::variant<
+ leaf_variant<Value, Box, Tag>,
+ internal_node_variant<Value, Box, Tag>
+ > *
+ >,
+ Translator
+>
+{
+ typedef Box type;
+};
+
+template <typename Value, typename Box, typename Tag, typename Translator>
+inline Box const&
+element_indexable(
+ std::pair<
+ Box,
+ boost::variant<
+ leaf_variant<Value, Box, Tag>,
+ internal_node_variant<Value, Box, Tag>
+ > *
+ > const& el,
+ Translator const&)
+{
+ return el.first;
+}
+
+// create leaf node
+
+template <typename Value, typename Box, typename Tag>
+inline typename node<Value, Box, Tag>::type *
+create_node(leaf_variant<Value, Box, Tag> const& l)
+{
+ typedef typename node<Value, Box, Tag>::type node;
+ node * n = new node(l);
+ return n;
+}
+
+// create internal node
+
+template <typename Value, typename Box, typename Tag>
+inline typename node<Value, Box, Tag>::type *
+create_node(internal_node_variant<Value, Box, Tag> const& in)
+{
+ typedef typename node<Value, Box, Tag>::type node;
+ node * n = new node(in);
+ return n;
+}
+
+// default node
+
+template <typename Value, typename Box, typename Tag>
+inline void delete_node(
+ boost::variant<
+ leaf_variant<Value, Box, Tag>,
+ internal_node_variant<Value, Box, Tag>
+ > * n)
+{
+ delete n;
+}
+
+}} // namespace detail::rtree
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_VARIANT_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -99,7 +99,7 @@
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
// copy original elements
- elements_type elements_copy = rtree::elements_get(n);
+ elements_type elements_copy = rtree::elements(n);
// calculate initial seeds
size_t seed1 = 0;
@@ -107,8 +107,8 @@
quadratic::pick_seeds<elements_type, Translator, Box>::apply(elements_copy, tr, seed1, seed2);
// prepare nodes' elements containers
- elements_type & elements1 = rtree::elements_get(n);
- elements_type & elements2 = rtree::elements_get(second_node);
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
elements1.clear();
assert(elements2.empty());
@@ -204,7 +204,7 @@
}
}
- // sprawdzic szukanie najmniejszego powiekszenia wezla dla grupy1 i grupy2
+ // TODO: awulkiew - change following function to static member of the pick_next class?
template <typename It>
static inline It pick_next(It first, It last,
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -43,81 +43,68 @@
template <typename Indexable>
static inline size_t apply(internal_node & n, Indexable const& indexable)
{
- children_type & children = rtree::elements_get(n);
+ children_type & children = rtree::elements(n);
assert(!children.empty());
- bool has_leaves = boost::apply_visitor(
- visitors::is_leaf<Value, Box, rstar_tag>(),
- *children.front().second);
+ visitors::is_leaf<Value, Box, rstar_tag> ilv;
+ rtree::apply_visitor(ilv, *children.front().second);
- if ( has_leaves )
- return branch_impl(n, indexable);
+ if ( ilv.result )
+ return choose_by_minimum_overlap_cost(children, indexable);
else
- return internal_node_impl(n, indexable);
+ return choose_by_minimum_area_cost(children, indexable);
}
private:
template <typename Indexable>
- static inline size_t branch_impl(internal_node & n, Indexable const& indexable)
+ static inline size_t choose_by_minimum_overlap_cost(children_type const& children, Indexable const& indexable)
{
- children_type & children = rtree::elements_get(n);
size_t children_count = children.size();
- // overlaps values of all nodes' boxes,
- // overlaps and areas of extended boxes are stored at indexes i + children_count
- std::vector<overlap_type> overlaps(children_count * 2, overlap_type(0));
- std::vector<overlap_type> areas(children_count * 2);
- // caculate overlaps and areas of all nodes' boxes
+ // choose index with smallest overlap change value, or area change or smallest area
+ size_t choosen_index = 0;
+ overlap_type smallest_overlap_diff = std::numeric_limits<overlap_type>::max();
+ area_type smallest_area_diff = std::numeric_limits<area_type>::max();
+ area_type smallest_area = std::numeric_limits<area_type>::max();
+
+ // for each child node
for (size_t i = 0 ; i < children_count ; ++i )
{
typedef typename children_type::value_type child_type;
child_type const& ch_i = children[i];
- Box ch_ext;
+ Box box_exp(ch_i.first);
// calculate expanded box fo node ch_i
- geometry::convert(ch_i.first, ch_ext);
- geometry::expand(ch_ext, indexable);
+ geometry::expand(box_exp, indexable);
- areas[i] = index::area(ch_i.first);
- areas[i + children_count] = index::area(ch_ext);
+ // calculate area and area diff
+ area_type area = index::area(ch_i.first);
+ area_type area_diff = index::area(box_exp) - area;
- for (size_t j = i + 1 ; j < children_count ; ++j )
+ overlap_type overlap = 0;
+ overlap_type overlap_exp = 0;
+
+ // calculate overlap
+ for ( size_t j = 0 ; j < children_count ; ++j )
{
- child_type const& ch_j = children[j];
-
- // add overlap of both boxes
- overlap_type ovl = index::overlap(ch_i.first, ch_j.first);
- overlaps[i] += ovl;
- overlaps[j] += ovl;
-
- // add overlap of expanded box i and box j
- overlaps[i + children_count] = index::overlap(ch_ext, ch_j.first);
-
- // add overlap of expanded box j and box i
- geometry::convert(ch_j.first, ch_ext);
- geometry::expand(ch_ext, indexable);
- overlaps[j + children_count] = index::overlap(ch_ext, ch_i.first);
+ if ( i != j )
+ {
+ child_type const& ch_j = children[j];
+
+ overlap += index::overlap(ch_i.first, ch_j.first);
+ overlap_exp += index::overlap(box_exp, ch_j.first);
+ }
}
- }
- // choose index with smallest overlap change value, or area change or smallest area
- size_t choosen_index = 0;
- overlap_type smallest_overlap_change = std::numeric_limits<overlap_type>::max();
- area_type smallest_area_change = std::numeric_limits<area_type>::max();
- area_type smallest_area = std::numeric_limits<area_type>::max();
+ overlap_type overlap_diff = overlap_exp - overlap;
- for ( size_t i = 0 ; i < children_count ; ++i )
- {
- overlap_type overlap_change = overlaps[i + children_count] - overlaps[i];
- area_type area_change = areas[i + children_count] - areas[i];
- area_type area = areas[i + children_count];
-
- if ( overlap_change < smallest_overlap_change ||
- ( overlap_change == smallest_overlap_change && area_change < smallest_area_change ) ||
- ( area_change == smallest_area_change && smallest_area < area ) )
+ // update result
+ if ( overlap_diff < smallest_overlap_diff ||
+ ( overlap_diff == smallest_overlap_diff && area_diff < smallest_area_diff ) ||
+ ( area_diff == smallest_area_diff && area < smallest_area ) )
{
- smallest_overlap_change = overlap_change;
- smallest_area_change = area_change;
+ smallest_overlap_diff = overlap_diff;
+ smallest_area_diff = area_diff;
smallest_area = area;
choosen_index = i;
}
@@ -127,14 +114,13 @@
}
template <typename Indexable>
- static inline size_t internal_node_impl(internal_node & n, Indexable const& indexable)
+ static inline size_t choose_by_minimum_area_cost(children_type const& children, Indexable const& indexable)
{
- children_type & children = rtree::elements_get(n);
size_t children_count = children.size();
// choose index with smallest area change or smallest area
size_t choosen_index = 0;
- area_type smallest_area_change = std::numeric_limits<area_type>::max();
+ area_type smallest_area_diff = std::numeric_limits<area_type>::max();
area_type smallest_area = std::numeric_limits<area_type>::max();
// caculate areas and areas of all nodes' boxes
@@ -143,17 +129,16 @@
typedef typename children_type::value_type child_type;
child_type const& ch_i = children[i];
- Box ch_exp;
- geometry::convert(ch_i.first, ch_exp);
- geometry::expand(ch_exp, indexable);
-
- area_type area = index::area(ch_exp);
- area_type area_change = area - index::area(ch_i.first);
-
- if ( area_change < smallest_area_change ||
- ( area_change == smallest_area_change && smallest_area < area ) )
+ Box box_exp(ch_i.first);
+ geometry::expand(box_exp, indexable);
+
+ area_type area = index::area(box_exp);
+ area_type area_diff = area - index::area(ch_i.first);
+
+ if ( area_diff < smallest_area_diff ||
+ ( area_diff == smallest_area_diff && area < smallest_area ) )
{
- smallest_area_change = area_change;
+ smallest_area_diff = area_diff;
smallest_area = area;
choosen_index = i;
}
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -49,7 +49,7 @@
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
// copy original elements
- elements_type elements_copy = rtree::elements_get(n);
+ elements_type elements_copy = rtree::elements(n);
// calculate initial seeds
size_t seed1 = 0;
@@ -57,8 +57,8 @@
quadratic::pick_seeds<elements_type, Translator, Box>::apply(elements_copy, tr, seed1, seed2);
// prepare nodes' elements containers
- elements_type & elements1 = rtree::elements_get(n);
- elements_type & elements2 = rtree::elements_get(second_node);
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
elements1.clear();
assert(elements2.empty());
@@ -154,8 +154,6 @@
}
}
- // sprawdzic szukanie najmniejszego powiekszenia wezla dla grupy1 i grupy2
-
template <typename It>
static inline It pick_next(It first, It last,
Box const& box1, Box const& box2,
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -22,7 +22,7 @@
#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
#include <boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp>
-//#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
namespace boost { namespace geometry { namespace index {
@@ -67,7 +67,7 @@
~rtree()
{
detail::rtree::visitors::destroy<value_type, translator_type, box_type, tag_type> del_v;
- boost::apply_visitor(del_v, *m_root);
+ detail::rtree::apply_visitor(del_v, *m_root);
}
// TODO: awulkiew - change name to query?
@@ -78,7 +78,7 @@
detail::rtree::visitors::find<value_type, translator_type, box_type, tag_type, Geometry, OutIter>
find_v(m_translator, geom, out_it);
- boost::apply_visitor(find_v, *m_root);
+ detail::rtree::apply_visitor(find_v, *m_root);
}
void insert(value_type const& value)
@@ -88,7 +88,7 @@
detail::rtree::visitors::insert<value_type, value_type, translator_type, box_type, tag_type>
insert_v(m_root, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
- boost::apply_visitor(insert_v, *m_root);
+ detail::rtree::apply_visitor(insert_v, *m_root);
++m_values_count;
}
@@ -101,7 +101,7 @@
detail::rtree::visitors::remove<value_type, translator_type, box_type, tag_type>
remove_v(m_root, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
- boost::apply_visitor(remove_v, *m_root);
+ detail::rtree::apply_visitor(remove_v, *m_root);
--m_values_count;
}
@@ -124,9 +124,9 @@
}
template <typename Visitor>
- typename Visitor::result_type apply_visitor(Visitor & visitor) const
+ void apply_visitor(Visitor & visitor) const
{
- return boost::apply_visitor(visitor, *m_root);
+ detail::rtree::apply_visitor(visitor, *m_root);
}
translator_type const& get_translator() const
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -18,23 +18,26 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Translator, typename Box, typename Tag>
-class are_boxes_ok : public boost::static_visitor<bool>
+class are_boxes_ok : public rtree::visitor<Value, Box, Tag, true>::type
{
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
public:
inline are_boxes_ok(Translator const& tr)
- : m_tr(tr), m_is_root(true)
+ : result(false), m_tr(tr), m_is_root(true)
{}
- inline bool operator()(internal_node const& n)
+ inline void operator()(internal_node const& n)
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
if (elements.empty())
- return false;
+ {
+ result = false;
+ return;
+ }
Box box_bckup = m_box;
bool is_root_bckup = m_is_root;
@@ -46,43 +49,50 @@
{
m_box = it->first;
- if ( false == boost::apply_visitor(*this, *it->second) )
- return false;
+ rtree::apply_visitor(*this, *it->second);
+
+ if ( result == false )
+ return;
}
m_box = box_bckup;
m_is_root = is_root_bckup;
- Box result;
- geometry::convert(elements.front().first, result);
+ Box box_exp;
+ geometry::convert(elements.front().first, box_exp);
for( typename elements_type::const_iterator it = elements.begin() + 1;
it != elements.end() ; ++it)
{
- geometry::expand(result, it->first);
+ geometry::expand(box_exp, it->first);
}
- return m_is_root || geometry::equals(result, m_box);
+ result = m_is_root || geometry::equals(box_exp, m_box);
}
- inline bool operator()(leaf const& n)
+ inline void operator()(leaf const& n)
{
typedef typename rtree::elements_type<leaf>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
if (elements.empty())
- return false;
+ {
+ result = false;
+ return;
+ }
- Box result;
- geometry::convert(m_tr(elements.front()), result);
+ 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(result, m_tr(*it));
+ geometry::expand(box_exp, m_tr(*it));
}
- return m_is_root || geometry::equals(result, m_box);
+ result = m_is_root || geometry::equals(box_exp, m_box);
}
+ bool result;
+
private:
Translator const& m_tr;
Box m_box;
@@ -101,7 +111,9 @@
typename rt::box_type,
typename rt::tag_type> v(tree.get_translator());
- return tree.apply_visitor(v);
+ tree.apply_visitor(v);
+
+ return v.result;
}
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/destroy.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/destroy.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/destroy.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -17,26 +17,26 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Translator, typename Box, typename Tag>
-struct destroy : public boost::static_visitor<>
+struct destroy : public rtree::visitor<Value, Box, Tag, false>::type
{
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
- inline void operator()(internal_node & n) const
+ inline void operator()(internal_node & n)
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type & elements = rtree::elements_get(n);
+ elements_type & elements = rtree::elements(n);
for (typename elements_type::iterator it = elements.begin();
it != elements.end(); ++it)
{
- boost::apply_visitor(*this, *it->second);
+ rtree::apply_visitor(*this, *it->second);
rtree::delete_node(it->second);
}
}
- inline void operator()(leaf & n) const
+ inline void operator()(leaf &)
{
}
};
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -143,7 +143,7 @@
// rtree spatial query visitor
template <typename Value, typename Translator, typename Box, typename Tag, typename Geometry, typename OutIter>
-struct find : public boost::static_visitor<>
+struct find : public rtree::visitor<Value, Box, Tag, true>::type
{
typedef typename rtree::node<Value, Box, Tag>::type node;
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
@@ -194,20 +194,20 @@
//}
typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
if ( geometry::intersects(it->first, geom) )
- boost::apply_visitor(*this, *it->second);
+ 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_get(n);
+ elements_type const& elements = rtree::elements(n);
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -95,7 +95,7 @@
} // namespace detail
template <typename Value, typename Translator, typename Box, typename Tag>
-struct gl_draw : public boost::static_visitor<>
+struct gl_draw : public rtree::visitor<Value, Box, Tag, true>::type
{
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
@@ -115,7 +115,7 @@
inline void operator()(internal_node const& n)
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
if ( level_f <= level )
{
@@ -151,7 +151,7 @@
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- boost::apply_visitor(*this, *it->second);
+ rtree::apply_visitor(*this, *it->second);
}
}
@@ -161,7 +161,7 @@
inline void operator()(leaf const& n)
{
typedef typename rtree::elements_type<leaf>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
if ( level_f <= level )
{
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -35,7 +35,7 @@
template <typename Indexable>
static inline size_t apply(internal_node & n, Indexable const& indexable)
{
- children_type & children = rtree::elements_get(n);
+ children_type & children = rtree::elements(n);
assert(!children.empty());
@@ -96,7 +96,7 @@
Translator const& tr)
{
node * second_node = rtree::create_node(Node());
- Node & n2 = boost::get<Node>(*second_node);
+ Node & n2 = rtree::get<Node>(*second_node);
// redistribute elements
Box box1, box2;
@@ -104,27 +104,27 @@
apply(n, n2, box1, box2, min_elems, max_elems, tr);
// check numbers of elements
- assert(min_elems <= rtree::elements_get(n).size() && rtree::elements_get(n).size() <= max_elems);
- assert(min_elems <= rtree::elements_get(n2).size() && rtree::elements_get(n2).size() <= max_elems);
+ assert(min_elems <= rtree::elements(n).size() && rtree::elements(n).size() <= max_elems);
+ assert(min_elems <= rtree::elements(n2).size() && rtree::elements(n2).size() <= max_elems);
// node is not the root
if ( parent != 0 )
{
// update old node's box
- rtree::elements_get(*parent)[current_child_index].first = box1;
+ rtree::elements(*parent)[current_child_index].first = box1;
// add new node to the parent's children
- rtree::elements_get(*parent).push_back(std::make_pair(box2, second_node));
+ rtree::elements(*parent).push_back(std::make_pair(box2, second_node));
}
// node is the root
else
{
- assert(&n == boost::get<Node>(root));
+ assert(&n == rtree::get<Node>(root));
// create new root and add nodes
node * new_root = rtree::create_node(internal_node());
- rtree::elements_get(boost::get<internal_node>(*new_root)).push_back(std::make_pair(box1, root));
- rtree::elements_get(boost::get<internal_node>(*new_root)).push_back(std::make_pair(box2, second_node));
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box1, root));
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box2, second_node));
root = new_root;
}
@@ -155,7 +155,7 @@
// Default insert visitor
template <typename Element, typename Value, typename Translator, typename Box, typename Tag>
-class insert : public boost::static_visitor<>
+class insert : public rtree::visitor<Value, Box, Tag, false>::type
{
public:
typedef typename rtree::node<Value, Box, Tag>::type node;
@@ -183,22 +183,6 @@
// assert - check if Box is correct
}
- inline void operator()(internal_node & n)
- {
- // traverse
- traverse(*this, n);
-
- post_traverse(n);
- }
-
- inline void operator()(leaf & n)
- {
- // push value
- rtree::elements_get(n).push_back(m_element);
-
- post_traverse(n);
- }
-
protected:
template <typename Visitor>
inline void traverse(Visitor & visitor, internal_node & n)
@@ -209,7 +193,7 @@
// expand the node to contain value
geometry::expand(
- rtree::elements_get(n)[choosen_node_index].first,
+ rtree::elements(n)[choosen_node_index].first,
rtree::element_indexable(m_element, m_tr));
// next traversing step
@@ -222,7 +206,7 @@
inline void post_traverse(Node &n)
{
// handle overflow
- if ( m_max_elems_per_node < rtree::elements_get(n).size() )
+ if ( m_max_elems_per_node < rtree::elements(n).size() )
{
detail::overflow_treatment<Value, Translator, Box, Tag>::
apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
@@ -242,7 +226,7 @@
++m_current_level;
// next traversing step
- boost::apply_visitor(visitor, *rtree::elements_get(n)[choosen_node_index].second);
+ rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -297,13 +281,13 @@
assert( base::m_level == base::m_current_level );
// push new child node
- rtree::elements_get(n).push_back(base::m_element);
+ rtree::elements(n).push_back(base::m_element);
}
base::post_traverse(n);
}
- inline void operator()(leaf & n)
+ inline void operator()(leaf &)
{
assert(false);
}
@@ -343,7 +327,7 @@
assert( base::m_level == base::m_current_level ||
base::m_level == std::numeric_limits<size_t>::max() );
- rtree::elements_get(n).push_back(base::m_element);
+ rtree::elements(n).push_back(base::m_element);
base::post_traverse(n);
}
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -17,20 +17,22 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Box, typename Tag>
-struct is_leaf : public boost::static_visitor<bool>
+struct is_leaf : public rtree::visitor<Value, Box, Tag, true>::type
{
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
- inline bool operator()(internal_node const&) const
+ inline void operator()(internal_node const&)
{
- return false;
+ result = false;
}
- inline bool operator()(leaf const&) const
+ inline void operator()(leaf const&)
{
- return true;
+ result = true;
}
+
+ bool result;
};
}}} // namespace detail::rtree::visitors
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/load.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/load.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
+++ (empty file)
@@ -1,111 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Boost.Index - R-tree loading visitor
-//
-// 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_LOAD_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_LOAD_HPP
-
-#include <iostream>
-
-#include <boost/geometry/extensions/index/rtree/node.hpp>
-
-namespace boost { namespace geometry { namespace index {
-
-namespace detail { namespace rtree { namespace visitors {
-
-template <typename Value, typename Translator, typename Box, typename Tag>
-struct load;
-
-template <typename Translator, typename Box, typename Tag>
-struct load<
- std::pair<
- boost::geometry::model::box<
- boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian>
- >,
- size_t
- >,
- typename Translator,
- Box,
- Tag
->
-: public boost::static_visitor<>
-{
- typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> point_type;
-
- typedef std::pair<
- boost::geometry::model::box<
- point_type
- >,
- size_t
- > value_type;
-
- typedef typename rtree::node<value_type, Box, Tag>::type node;
- typedef typename rtree::internal_node<value_type, Box, Tag>::type internal_node;
- typedef typename rtree::leaf<value_type, Box, Tag>::type leaf;
-
- inline load(std::istream & i, Translator const& t)
- : is(i), tr(t)
- {}
-
- inline void operator()(internal_node & n)
- {
- std::string node_type;
- float min_x, min_y, max_x, max_y;
- size_t c;
-
- is >> node_type;
- is >> min_x;
- is >> min_y;
- is >> max_x;
- is >> max_y;
- is >> c;
-
- Box b(point_type(min_x, min_y), point_type(max_x, max_y));
- node * new_n = 0;
-
- if ( node_type == "i" )
- new_n = rtree::create_node(internal_node());
- else if ( node_type == "l" )
- new_n = rtree::create_node(leaf());
- else
- assert(0);
-
- n.children.push_back(std::make_pair(b, new_n));
-
- for ( size_t i = 0 ; i < c ; ++i )
- boost::apply_visitor(*this, *new_n);
- }
-
- inline void operator()(leaf & n)
- {
- std::string node_type;
- float min_x, min_y, max_x, max_y;
- size_t id;
-
- is >> node_type;
- is >> min_x;
- is >> min_y;
- is >> max_x;
- is >> max_y;
- is >> id;
-
- assert(id == "v");
-
- Box b(point_type(min_x, min_y), point_type(max_x, max_y));
- n.values.push_back(std::make_pair(b, id));
- }
-
- std::istream & is;
- Translator const& tr;
-};
-
-}}} // namespace detail::rtree::visitors
-
-}}} // namespace boost::geometry::index
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_LOAD_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -114,7 +114,7 @@
} // namespace detail
template <typename Value, typename Translator, typename Box, typename Tag>
-struct print : public boost::static_visitor<>
+struct print : public rtree::visitor<Value, Box, Tag, true>::type
{
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
@@ -126,7 +126,7 @@
inline void operator()(internal_node const& n)
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
spaces(level) << "INTERNAL NODE - L:" << level << " Ch:" << elements.size() << " @:" << &n << '\n';
@@ -144,7 +144,7 @@
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- boost::apply_visitor(*this, *it->second);
+ rtree::apply_visitor(*this, *it->second);
}
level = level_backup;
@@ -153,7 +153,7 @@
inline void operator()(leaf const& n)
{
typedef typename rtree::elements_type<leaf>::type elements_type;
- elements_type const& elements = rtree::elements_get(n);
+ elements_type const& elements = rtree::elements(n);
spaces(level) << "LEAF - L:" << level << " V:" << elements.size() << " @:" << &n << '\n';
for (typename elements_type::const_iterator it = elements.begin();
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -20,7 +20,7 @@
// Default remove algorithm
template <typename Value, typename Translator, typename Box, typename Tag>
-class remove : public boost::static_visitor<>
+class remove : public rtree::visitor<Value, Box, Tag, false>::type
{
typedef typename rtree::node<Value, Box, Tag>::type node;
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
@@ -46,7 +46,7 @@
inline void operator()(internal_node & n)
{
typedef typename rtree::elements_type<internal_node>::type children_type;
- children_type & children = rtree::elements_get(n);
+ children_type & children = rtree::elements(n);
// traverse children which boxes intersects value's box
size_t child_node_index = 0;
@@ -69,7 +69,7 @@
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
typedef typename elements_type::iterator element_iterator;
- elements_type & elements = rtree::elements_get(n);
+ elements_type & elements = rtree::elements(n);
// underflow occured - child node should be removed
if ( m_is_underflow )
@@ -91,14 +91,14 @@
// note that there may be less than min_elems elements in root
assert((elements.size() < m_min_elems_per_node) == m_is_underflow);
- rtree::elements_get(*m_parent)[m_current_child_index].first
+ rtree::elements(*m_parent)[m_current_child_index].first
= rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
}
// n is root node
else
{
// current node must be a root
- assert(&n == boost::get<internal_node>(m_root_node));
+ assert(&n == rtree::get<internal_node>(m_root_node));
// value not found
assert(m_is_value_removed);
@@ -108,16 +108,18 @@
for ( typename std::vector< std::pair<size_t, node*> >::reverse_iterator it = m_underflowed_nodes.rbegin();
it != m_underflowed_nodes.rend() ; ++it )
{
- if ( boost::apply_visitor(is_leaf<Value, Box, Tag>(), *it->second) )
- reinsert_elements(boost::get<leaf>(*it->second), it->first);
+ is_leaf<Value, Box, Tag> ilv;
+ rtree::apply_visitor(ilv, *it->second);
+ if ( ilv.result )
+ reinsert_elements(rtree::get<leaf>(*it->second), it->first);
else
- reinsert_elements(boost::get<internal_node>(*it->second), it->first);
+ reinsert_elements(rtree::get<internal_node>(*it->second), it->first);
}
// shorten the tree
- if ( rtree::elements_get(n).size() == 1 )
+ if ( rtree::elements(n).size() == 1 )
{
- m_root_node = rtree::elements_get(n)[0].second;
+ m_root_node = rtree::elements(n)[0].second;
}
}
}
@@ -126,7 +128,7 @@
inline void operator()(leaf & n)
{
typedef typename rtree::elements_type<leaf>::type elements_type;
- elements_type & elements = rtree::elements_get(n);
+ elements_type & elements = rtree::elements(n);
// find value and remove it
for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
@@ -148,7 +150,7 @@
// n is not root - adjust aabb
if ( 0 != m_parent )
{
- rtree::elements_get(*m_parent)[m_current_child_index].first
+ rtree::elements(*m_parent)[m_current_child_index].first
= rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
}
}
@@ -167,7 +169,7 @@
++m_current_level;
// next traversing step
- boost::apply_visitor(*this, *rtree::elements_get(n)[choosen_node_index].second);
+ rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second);
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -179,7 +181,7 @@
void reinsert_elements(Node &n, size_t level)
{
typedef typename rtree::elements_type<Node>::type elements_type;
- elements_type & elements = rtree::elements_get(n);
+ elements_type & elements = rtree::elements(n);
for ( typename elements_type::iterator it = elements.begin();
it != elements.end() ; ++it )
{
@@ -191,7 +193,7 @@
m_tr,
level);
- boost::apply_visitor(insert_v, *m_root_node);
+ rtree::apply_visitor(insert_v, *m_root_node);
}
}
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/save.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/save.hpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
+++ (empty file)
@@ -1,103 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Boost.Index - R-tree saving visitor
-//
-// 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_SAVE_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_SAVE_HPP
-
-#include <iostream>
-
-#include <boost/geometry/extensions/index/rtree/node.hpp>
-
-namespace boost { namespace geometry { namespace index {
-
-namespace detail { namespace rtree { namespace visitors {
-
-template <typename Value, typename Translator, typename Box, typename Tag>
-struct save;
-
-template <typename Translator, typename Box, typename Tag>
-struct save<
- std::pair<
- boost::geometry::model::box<
- boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian>
- >,
- size_t
- >,
- Translator,
- Box,
- Tag
->
-: public boost::static_visitor<>
-{
- typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> point_type;
-
- typedef std::pair<
- boost::geometry::model::box<
- point_type
- >,
- size_t
- > value_type;
-
- typedef typename rtree::node<value_type, Box, Tag>::type node;
- typedef typename rtree::internal_node<value_type, Box, Tag>::type internal_node;
- typedef typename rtree::leaf<value_type, Box, Tag>::type leaf;
-
- inline save(std::ostream & o, Translator const& t)
- : os(o), tr(t)
- {}
-
- inline void operator()(internal_node & n)
- {
- typedef typename rtree::elements_type<internal_node>::type elements_type;
- elements_type & elements = rtree::elements_get(n);
-
- os << elements.size() << '\n';
-
- for ( size_t i = 0 ; i < elements.size() ; ++i )
- {
- if ( boost::apply_visitor(visitors::is_leaf<value_type, Box, Tag>(), *(elements[i].second)) )
- os << "l ";
- else
- os << "i ";
- os << geometry::get<min_corner, 0>(elements[i].first) << ' ';
- os << geometry::get<min_corner, 1>(elements[i].first) << ' ';
- os << geometry::get<max_corner, 0>(elements[i].first) << ' ';
- os << geometry::get<max_corner, 1>(elements[i].first) << ' ';
-
- boost::apply_visitor(*this, *(elements[i].second));
- }
- }
-
- inline void operator()(leaf & n)
- {
- typedef typename rtree::elements_type<leaf>::type elements_type;
- elements_type & elements = rtree::elements_get(n);
-
- os << elements.size() << '\n';
-
- for ( size_t i = 0 ; i < elements.size() ; ++i )
- {
- os << "v ";
- os << geometry::get<min_corner, 0>(elements[i].first) << ' ';
- os << geometry::get<min_corner, 1>(elements[i].first) << ' ';
- os << geometry::get<max_corner, 0>(elements[i].first) << ' ';
- os << geometry::get<max_corner, 1>(elements[i].first) << ' ';
- os << elements[i].second << '\n';
- }
- }
-
- std::ostream & os;
- Translator const& tr;
-};
-
-}}} // namespace detail::rtree::visitors
-
-}}} // namespace boost::geometry::index
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_SAVE_HPP
Modified: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp 2011-05-13 06:59:49 EDT (Fri, 13 May 2011)
@@ -1,13 +1,14 @@
+//#define BOOST_GEOMETRY_INDEX_USE_VARIANT_NODES
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
+
#include <iostream>
#include <fstream>
#include <boost/timer.hpp>
#include <boost/foreach.hpp>
-//#include <boost/geometry/extensions/index/rtree/visitors/save.hpp>
-
int main()
{
boost::timer tim;
@@ -17,9 +18,9 @@
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::default_parameter, bgi::linear_tag> RT;
+ //typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::linear_tag> RT;
//typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::quadratic_tag> RT;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::rstar_tag> RT;
+ typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::rstar_tag> RT;
std::ifstream file_cfg("config.txt");
size_t max_elems = 4;
@@ -61,20 +62,10 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
- /*if ( save_ch == 's' )
- {
- std::cout << "saving...\n";
- std::ofstream file("save_new.txt", std::ofstream::trunc);
- file << std::fixed;
- bgi::detail::rtree::visitors::save<
- RT::value_type,
- RT::translator_type,
- RT::box_type,
- RT::tag_type
- > saving_v(file, t.get_translator());
- t.apply_visitor(saving_v);
- std::cout << "saved...\n";
- }*/
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
{
std::cout << "searching time test...\n";
@@ -106,6 +97,11 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
+
{
std::cout << "searching time test...\n";
tim.restart();
@@ -136,6 +132,11 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
+
{
std::cout << "searching time test...\n";
tim.restart();
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