Subject: [Boost-commit] svn:boost r69057 - in sandbox-branches/geometry/index_080_nhch: boost/geometry/extensions/index/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-02-19 09:23:39
Author: awulkiew
Date: 2011-02-19 09:23:37 EST (Sat, 19 Feb 2011)
New Revision: 69057
URL: http://svn.boost.org/trac/boost/changeset/69057
Log:
experimental nodes structure
Added:
sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_internal_node.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree.hpp | 26 +-
sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_leaf.hpp | 176 ++++++++-------
sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_node.hpp | 421 +++++++++++----------------------------
sandbox-branches/geometry/index_080_nhch/tests/rtree_native.cpp | 2
4 files changed, 228 insertions(+), 397 deletions(-)
Modified: sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree.hpp 2011-02-19 09:23:37 EST (Sat, 19 Feb 2011)
@@ -21,7 +21,7 @@
#include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+#include <boost/geometry/extensions/index/rtree/rtree_internal_node.hpp>
#include <boost/geometry/extensions/index/rtree/rtree_leaf.hpp>
// awulkiew - added
@@ -43,8 +43,10 @@
// awulkiew - typedefs added
typedef rtree_node<Value, Translator, Box> rtree_node;
typedef rtree_leaf<Value, Translator, Box> rtree_leaf;
+ typedef rtree_internal_node<Value, Translator, Box> rtree_internal_node;
typedef boost::shared_ptr<rtree_node> node_pointer;
+ typedef boost::shared_ptr<rtree_internal_node> internal_node_pointer;
typedef boost::shared_ptr<rtree_leaf> leaf_pointer;
/**
@@ -54,7 +56,7 @@
: m_count(0)
, m_min_elems_per_node(minimum)
, m_max_elems_per_node(maximum)
- , m_root(new rtree_node(node_pointer(), 1))
+ , m_root(new rtree_internal_node(node_pointer(), 1))
// awulkiew - added
, m_translator(tr)
{
@@ -106,11 +108,11 @@
leaf->get_parent()->remove_in(leaf->get_parent()->get_box(leaf), m_translator);
}
- typename rtree_node::node_map q_nodes;
+ typename rtree_internal_node::node_map q_nodes;
condense_tree(leaf, q_nodes);
std::vector<Value> s;
- for (typename rtree_node::node_map::const_iterator it = q_nodes.begin();
+ for (typename rtree_internal_node::node_map::const_iterator it = q_nodes.begin();
it != q_nodes.end(); ++it)
{
typename rtree_leaf::leaf_map leaves = it->second->get_leaves();
@@ -208,11 +210,11 @@
leaf->get_parent()->remove_in(leaf->get_parent()->get_box(leaf), m_translator);
}
- typename rtree_node::node_map q_nodes;
+ typename rtree_internal_node::node_map q_nodes;
condense_tree(leaf, q_nodes);
std::vector<Value> s;
- for (typename rtree_node::node_map::const_iterator it = q_nodes.begin();
+ for (typename rtree_internal_node::node_map::const_iterator it = q_nodes.begin();
it != q_nodes.end(); ++it)
{
typename rtree_leaf::leaf_map leaves = it->second->get_leaves();
@@ -352,7 +354,7 @@
* \brief Reorganize the tree after a removal. It tries to
* join nodes with less elements than m.
*/
- void condense_tree(node_pointer const& leaf, typename rtree_node::node_map& q_nodes)
+ void condense_tree(node_pointer const& leaf, typename rtree_internal_node::node_map& q_nodes)
{
if (leaf.get() == m_root.get())
{
@@ -372,8 +374,8 @@
}
// get the nodes that we should reinsert
- typename rtree_node::node_map this_nodes = parent->get_nodes();
- for(typename rtree_node::node_map::const_iterator it = this_nodes.begin();
+ typename rtree_internal_node::node_map this_nodes = parent->get_nodes();
+ for(typename rtree_internal_node::node_map::const_iterator it = this_nodes.begin();
it != this_nodes.end(); ++it)
{
q_nodes.push_back(*it);
@@ -413,7 +415,7 @@
// check if we are in the root and do the split
if (leaf.get() == m_root.get())
{
- node_pointer new_root(new rtree_node(node_pointer(), leaf->get_level() + 1));
+ node_pointer new_root(new rtree_internal_node(node_pointer(), leaf->get_level() + 1));
new_root->add_node(n1->compute_box(m_translator), n1);
new_root->add_node(n2->compute_box(m_translator), n2);
@@ -435,8 +437,8 @@
// if parent is full, split and readjust
if (parent->elements() > m_max_elems_per_node)
{
- node_pointer p1(new rtree_node(parent->get_parent(), parent->get_level()));
- node_pointer p2(new rtree_node(parent->get_parent(), parent->get_level()));
+ node_pointer p1(new rtree_internal_node(parent->get_parent(), parent->get_level()));
+ node_pointer p2(new rtree_internal_node(parent->get_parent(), parent->get_level()));
split_node(parent, p1, p2);
adjust_tree(parent, p1, p2);
Added: sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_internal_node.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_internal_node.hpp 2011-02-19 09:23:37 EST (Sat, 19 Feb 2011)
@@ -0,0 +1,432 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - rtree node implementation
+//
+// Copyright 2008 Federico J. Fernandez.
+// 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_RTREE_INTERNAL_NODE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_INTERNAL_NODE_HPP
+
+#include <deque>
+#include <iostream> // TODO: Remove if print() is removed
+#include <stdexcept>
+#include <utility>
+#include <vector>
+
+#include <boost/shared_ptr.hpp>
+
+#include <boost/geometry/algorithms/area.hpp>
+#include <boost/geometry/algorithms/assign.hpp>
+#include <boost/geometry/algorithms/combine.hpp>
+#include <boost/geometry/algorithms/equals.hpp>
+
+#include <boost/geometry/extensions/index/rtree/helpers.hpp>
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+template <typename Value, typename Translator, typename Box>
+class rtree_internal_node : public rtree_node<Value, Translator, Box>
+{
+public:
+
+ typedef rtree_node<Value, Translator, Box> rtree_node;
+ typedef rtree_leaf<Value, Translator, Box> rtree_leaf;
+
+ typedef boost::shared_ptr<rtree_node> node_pointer;
+ typedef boost::shared_ptr<rtree_leaf> leaf_pointer;
+
+ /// type for the node map
+ typedef std::vector<std::pair<Box, node_pointer > > node_map;
+
+ /**
+ * \brief Creates a default node (needed for the containers)
+ */
+ rtree_internal_node()
+ {
+ }
+
+ /**
+ * \brief Creates a node with 'parent' as parent and 'level' as its level
+ */
+ rtree_internal_node(node_pointer const& parent, size_t const& level)
+ : rtree_node(parent, level)
+ {
+ }
+
+ // awulkiew - internal node methods
+
+ /**
+ * \brief Clear the node
+ */
+ // awulkiew - name changed from empty_nodes to clear_nodes
+ void clear_nodes()
+ {
+ m_nodes.clear();
+ }
+
+ // awulkiew - internal node and leaf virtual methods
+
+ /**
+ * \brief True if it is a leaf node
+ */
+ virtual bool is_leaf() const
+ {
+ return false;
+ }
+
+ /**
+ * \brief Number of elements in the subtree
+ */
+ virtual size_t elements() const
+ {
+ return m_nodes.size();
+ }
+
+ /**
+ * \brief Search for elements in 'box' in the Rtree. Add them to 'result'.
+ * If exact_match is true only return the elements having as
+ * key the box 'box'. Otherwise return everything inside 'box'.
+ */
+ // awulkiew - exact match case removed
+ virtual void find(Box const& box, std::deque<Value>& result, Translator const& tr)
+ {
+ for (typename node_map::const_iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ // awulkiew - is_overlapping changed to geometry::intersects
+ if (geometry::intersects(it->first, box))
+ {
+ it->second->find(box, result, tr);
+ }
+ }
+ }
+
+ /**
+ * \brief Compute bounding box for this node
+ */
+ virtual Box compute_box(Translator const&) const
+ {
+ if (m_nodes.empty())
+ {
+ return Box();
+ }
+
+ Box result;
+ geometry::assign_inverse(result);
+ for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
+ {
+ geometry::combine(result, it->first);
+ }
+
+ return result;
+ }
+
+ /**
+ * \brief Get leaves for a node
+ */
+ virtual std::vector<Value> get_leaves() const
+ {
+ typedef std::vector<Value> leaf_type;
+ leaf_type leaf;
+
+ for (typename node_map::const_iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ leaf_type this_leaves = it->second->get_leaves();
+
+ for (typename leaf_type::iterator it_leaf = this_leaves.begin();
+ it_leaf != this_leaves.end(); ++it_leaf)
+ {
+ leaf.push_back(*it_leaf);
+ }
+ }
+
+ return leaf;
+ }
+
+ /**
+ * \brief Remove elements inside the 'box'
+ */
+ // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
+ virtual void remove_in(Box const& box, Translator const&)
+ {
+ for (typename node_map::iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ if (geometry::equals(it->first, box))
+ {
+ m_nodes.erase(it);
+ return;
+ }
+ }
+ }
+
+ /**
+ * \brief Get the envelopes of a node
+ */
+ virtual std::vector<Box> get_boxes(Translator const&) const
+ {
+ std::vector<Box> result;
+ for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
+ {
+ result.push_back(it->first);
+ }
+ return result;
+ }
+
+ /**
+ * \brief Print Rtree subtree (mainly for debug)
+ */
+ virtual void print(Translator const& tr) const
+ {
+ std::cerr << " --> Node --------" << std::endl;
+ std::cerr << " Address: " << this << std::endl;
+ std::cerr << " Level: " << this->get_level() << std::endl;
+ std::cerr << " Size: " << m_nodes.size() << std::endl;
+ std::cerr << " | ";
+ for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
+ {
+ if (this != it->second->get_parent().get())
+ {
+ std::cerr << "ERROR - " << this << " is not " << it->second->get_parent().get() << " ";
+ }
+
+ std::cerr << "( " << geometry::get<min_corner, 0>(it->first) << " , "
+ << geometry::get<min_corner, 1>(it->first) << " ) x ";
+ std::cerr << "( " << geometry::get<max_corner, 0>(it->first) << " , "
+ << geometry::get<max_corner, 1>(it->first) << " )";
+ std::cerr << " | ";
+ }
+ std::cerr << std::endl;
+ std::cerr << " --< Node --------" << std::endl;
+
+ // print child nodes
+ std::cerr << " Children: " << std::endl;
+ for (typename node_map::const_iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ it->second->print(tr);
+ }
+ }
+
+ // awulkiew - internal node only virtual methods
+
+ /**
+ * \brief Add a child to this node
+ */
+ virtual void add_node(Box const& box, node_pointer const& node)
+ {
+ m_nodes.push_back(std::make_pair(box, node));
+ node->update_parent(node);
+ }
+
+ /**
+ * \brief Project first element, to replace root in case of condensing
+ */
+ virtual node_pointer first_element() const
+ {
+ if (0 == m_nodes.size())
+ {
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("first_element in empty node");
+ }
+ return m_nodes.begin()->second;
+ }
+
+ /**
+ * \brief Proyector for the 'i' node
+ */
+ virtual node_pointer get_node(size_t index)
+ {
+ return m_nodes[index].second;
+ }
+
+ /**
+ * \brief Return in 'result' all the leaves inside 'box'
+ */
+ virtual void find_leaves(Box const& box, typename std::vector<node_pointer>& result) const
+ {
+ for (typename node_map::const_iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ // awulkiew - is_overlapping changed to geometry::intersects
+ if (geometry::intersects(it->first, box))
+ {
+ if (it->second->is_leaf())
+ {
+ result.push_back(it->second);
+ }
+ else
+ {
+ it->second->find_leaves(box, result);
+ }
+ }
+ }
+ }
+
+ /**
+ * \brief Recompute the bounding box
+ */
+ virtual void adjust_box(node_pointer const& node, Translator const& tr)
+ {
+ unsigned int index = 0;
+ for (typename node_map::iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it, index++)
+ {
+ if (it->second.get() == node.get())
+ {
+ m_nodes[index] = std::make_pair(node->compute_box(tr), node);
+ return;
+ }
+ }
+ }
+
+ /**
+ * \brief Replace the node in the m_nodes vector and recompute the box
+ */
+ virtual void replace_node(node_pointer const& leaf, node_pointer& new_leaf, Translator const& tr)
+ {
+ unsigned int index = 0;
+ for(typename node_map::iterator it = m_nodes.begin(); it != m_nodes.end(); ++it, index++)
+ {
+ if (it->second.get() == leaf.get())
+ {
+ m_nodes[index] = std::make_pair(new_leaf->compute_box(tr), new_leaf);
+ new_leaf->update_parent(new_leaf);
+ return;
+ }
+ }
+
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("Node not found.");
+ }
+
+ /**
+ * \brief Add a child leaf to this node
+ */
+ virtual void add_leaf_node(Box const& box, leaf_pointer const& leaf)
+ {
+ m_nodes.push_back(std::make_pair(box, leaf));
+ }
+
+ /**
+ * \brief Choose a node suitable for adding 'box'
+ */
+ virtual node_pointer choose_node(Box const& box)
+ {
+ if (m_nodes.size() == 0)
+ {
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("Empty node trying to choose the least enlargement node.");
+ }
+
+ // awulkiew - areas types changed
+ typedef typename area_result<Box>::type area_type;
+
+ bool first = true;
+ area_type min_area = 0;
+ area_type min_diff_area = 0;
+ node_pointer chosen_node;
+
+ // check for the least enlargement
+ for (typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
+ {
+ // awulkiew - areas types changed
+ area_type const diff_area = compute_union_area(box, it->first) - geometry::area(it->first);
+
+ if (first)
+ {
+ // it's the first time, we keep the first
+ min_diff_area = diff_area;
+ min_area = geometry::area(it->first);
+ chosen_node = it->second;
+
+ first = false;
+ }
+ else
+ {
+ if (diff_area < min_diff_area)
+ {
+ min_diff_area = diff_area;
+ min_area = geometry::area(it->first);
+ chosen_node = it->second;
+ }
+ else
+ {
+ if (diff_area == min_diff_area)
+ {
+ if (geometry::area(it->first) < min_area)
+ {
+ min_diff_area = diff_area;
+ min_area = geometry::area(it->first);
+ chosen_node = it->second;
+ }
+ }
+ }
+ }
+ }
+
+ return chosen_node;
+ }
+
+ /**
+ * \brief Update the parent of all the childs
+ */
+ virtual void update_parent(node_pointer const& node)
+ {
+ for (typename node_map::iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
+ {
+ it->second->set_parent(node);
+ }
+ }
+
+ /**
+ * \brief Box projector for node pointed by 'leaf'
+ */
+ virtual Box get_box(node_pointer const& leaf) const
+ {
+ for (typename node_map::const_iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ if (it->second.get() == leaf.get())
+ {
+ return it->first;
+ }
+ }
+
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("Node not found");
+ }
+
+ /**
+ * \brief Children projector
+ */
+ virtual node_map get_nodes() const
+ {
+ return m_nodes;
+ }
+
+ // awulkiew - unclassified methods
+
+ /**
+ * \brief Box projector for node 'index'
+ */
+ // awulkiew - commented, not used
+ /*virtual Box get_box(unsigned int index, Translator const& tr) const
+ {
+ return m_nodes[index].first;
+ }*/
+
+private:
+
+ /// child nodes
+ node_map m_nodes;
+};
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_INTERNAL_NODE_HPP
Modified: sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_leaf.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_leaf.hpp (original)
+++ sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_leaf.hpp 2011-02-19 09:23:37 EST (Sat, 19 Feb 2011)
@@ -23,6 +23,7 @@
#include <boost/geometry/algorithms/combine.hpp>
#include <boost/geometry/algorithms/intersects.hpp>
+#include <boost/geometry/extensions/index/rtree/helpers.hpp>
#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
namespace boost { namespace geometry { namespace index
@@ -36,8 +37,9 @@
// awulkiew - typedef added
typedef rtree_node<Value, Translator, Box> rtree_node;
- /// container type for the leaves
typedef boost::shared_ptr<rtree_node> node_pointer;
+
+ /// container type for the leaves
typedef std::vector<Value> leaf_map;
/**
@@ -55,6 +57,35 @@
{
}
+ // awulkiew - leaf methods
+
+ /**
+ * \brief Clear the node
+ */
+ // awulkiew - name changed from empty_nodes to clear_values
+ void clear_values()
+ {
+ m_nodes.clear();
+ }
+
+ // awulkiew - internal node and leaf virtual methods
+
+ /**
+ * \brief True if we are a leaf
+ */
+ virtual bool is_leaf() const
+ {
+ return true;
+ }
+
+ /**
+ * \brief Number of elements in the tree
+ */
+ virtual size_t elements() const
+ {
+ return m_nodes.size();
+ }
+
/**
* \brief Search for elements in 'box' in the Rtree. Add them to 'result'.
* If exact_match is true only return the elements having as
@@ -107,30 +138,6 @@
}
/**
- * \brief True if we are a leaf
- */
- virtual bool is_leaf() const
- {
- return true;
- }
-
- /**
- * \brief Number of elements in the tree
- */
- virtual unsigned int elements() const
- {
- return m_nodes.size();
- }
-
- /**
- * \brief Insert a new element, with key 'box' and value 'v'
- */
- virtual void insert(Value const& v)
- {
- m_nodes.push_back(v);
- }
-
- /**
* \brief Proyect leaves of this node.
*/
virtual std::vector<Value> get_leaves() const
@@ -139,44 +146,6 @@
}
/**
- * \brief Add a new child (node) to this node
- */
- virtual void add_node(Box const&, node_pointer const&)
- {
- // TODO: mloskot - define & use GGL exception
- throw std::logic_error("Can't add node to leaf node.");
- }
-
- /**
- * \brief Add a new leaf to this node
- */
- virtual void add_value(Value const& v)
- {
- m_nodes.push_back(v);
- }
-
- /**
- * \brief Proyect value in position 'index' in the nodes container
- */
- virtual Value get_value(unsigned int index) const
- {
- return m_nodes[index];
- }
-
- /**
- * \brief Box projector for leaf
- */
- // awulkiew - commented, not used
- //virtual Box get_box(unsigned int index, Translator const& tr) const
- //{
- // // TODO: awulkiew - get_bounding_object - add object specific behaviour
- // // or just base on get_value
- // Box box;
- // detail::convert_to_box(tr(m_nodes[index]), box);
- // return box;
- //}
-
- /**
* \brief Remove value with key 'box' in this leaf
*/
// awulkiew - name changed to avoid ambiguity (Value may be of type Box)
@@ -201,26 +170,6 @@
}
/**
- * \brief Remove value in this leaf
- */
- virtual void remove(Value const& v, Translator const& tr)
- {
- for (typename leaf_map::iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- // awulkiew - use of translator
- if ( tr.equals(*it, v) )
- {
- m_nodes.erase(it);
- return;
- }
- }
-
- // TODO: mloskot - use GGL exception
- throw std::logic_error("Node not found.");
- }
-
- /**
* \brief Proyect boxes from this node
*/
virtual std::vector<Box> get_boxes(Translator const& tr) const
@@ -268,6 +217,67 @@
std::cerr << "\t" << " --< Leaf --------" << std::endl;
}
+ // awulkiew - leaf only virtual methods
+
+ /**
+ * \brief Insert a new element, with key 'box' and value 'v'
+ */
+ virtual void insert(Value const& v)
+ {
+ m_nodes.push_back(v);
+ }
+
+ /**
+ * \brief Add a new leaf to this node
+ */
+ virtual void add_value(Value const& v)
+ {
+ m_nodes.push_back(v);
+ }
+
+ /**
+ * \brief Proyect value in position 'index' in the nodes container
+ */
+ virtual Value get_value(unsigned int index) const
+ {
+ return m_nodes[index];
+ }
+
+ /**
+ * \brief Remove value in this leaf
+ */
+ virtual void remove(Value const& v, Translator const& tr)
+ {
+ for (typename leaf_map::iterator it = m_nodes.begin();
+ it != m_nodes.end(); ++it)
+ {
+ // awulkiew - use of translator
+ if ( tr.equals(*it, v) )
+ {
+ m_nodes.erase(it);
+ return;
+ }
+ }
+
+ // TODO: mloskot - use GGL exception
+ throw std::logic_error("Node not found.");
+ }
+
+ // awulkiew - unclassified methods
+
+ /**
+ * \brief Box projector for leaf
+ */
+ // awulkiew - commented, not used
+ //virtual Box get_box(unsigned int index, Translator const& tr) const
+ //{
+ // // TODO: awulkiew - get_bounding_object - add object specific behaviour
+ // // or just base on get_value
+ // Box box;
+ // detail::convert_to_box(tr(m_nodes[index]), box);
+ // return box;
+ //}
+
private:
/// leaves of this node
Modified: sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_node.hpp (original)
+++ sandbox-branches/geometry/index_080_nhch/boost/geometry/extensions/index/rtree/rtree_node.hpp 2011-02-19 09:23:37 EST (Sat, 19 Feb 2011)
@@ -1,8 +1,8 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
-// Boost.SpatialIndex - rtree node implementation
+// Boost.SpatialIndex - rtree node, base class to leafs and internal nodes
//
-// Copyright 2008 Federico J. Fernandez.
+// 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)
@@ -10,28 +10,15 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_NODE_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_NODE_HPP
-#include <deque>
-#include <iostream> // TODO: Remove if print() is removed
-#include <stdexcept>
-#include <utility>
-#include <vector>
-
-#include <boost/shared_ptr.hpp>
-
-#include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/algorithms/assign.hpp>
-#include <boost/geometry/algorithms/combine.hpp>
-#include <boost/geometry/algorithms/equals.hpp>
-
-#include <boost/geometry/extensions/index/rtree/helpers.hpp>
-
namespace boost { namespace geometry { namespace index {
-/// forward declaration
template <typename Value, typename Translator, typename Box>
class rtree_leaf;
template <typename Value, typename Translator, typename Box>
+class rtree_internal_node;
+
+template <typename Value, typename Translator, typename Box>
class rtree_node
{
public:
@@ -39,144 +26,102 @@
typedef boost::shared_ptr<rtree_node<Value, Translator, Box> > node_pointer;
typedef boost::shared_ptr<rtree_leaf<Value, Translator, Box> > leaf_pointer;
- /// type for the node map
typedef std::vector<std::pair<Box, node_pointer > > node_map;
/**
- * \brief Creates a default node (needed for the containers)
+ * \brief destructor (virtual because we have virtual functions)
*/
- rtree_node()
+ virtual ~rtree_node()
{
}
+ // awulkiew - node methods
+
/**
- * \brief Creates a node with 'parent' as parent and 'level' as its level
+ * \brief Projector for parent
*/
- rtree_node(node_pointer const& parent, unsigned int const& level)
- : m_parent(parent), m_level(level)
+ inline node_pointer get_parent() const
{
+ return m_parent;
}
/**
- * \brief destructor (virtual because we have virtual functions)
+ * \brief Set parent
*/
- virtual ~rtree_node()
+ void set_parent(node_pointer const& node)
{
+ m_parent = node;
}
/**
* \brief Level projector
*/
- virtual unsigned int get_level() const
+ size_t get_level() const
{
return m_level;
}
- /**
- * \brief Number of elements in the subtree
- */
- virtual unsigned int elements() const
- {
- return m_nodes.size();
- }
-
- /**
- * \brief Project first element, to replace root in case of condensing
- */
- inline node_pointer first_element() const
- {
- if (0 == m_nodes.size())
- {
- // TODO: mloskot - define & use GGL exception
- throw std::logic_error("first_element in empty node");
- }
- return m_nodes.begin()->second;
- }
+ // awulkiew - internal node and leaf virtual methods
/**
* \brief True if it is a leaf node
*/
virtual bool is_leaf() const
{
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
return false;
}
/**
- * \brief Proyector for the 'i' node
+ * \brief Number of elements in the subtree
*/
- node_pointer get_node(unsigned int index)
+ virtual size_t elements() const
{
- return m_nodes[index].second;
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
+ return 0;
}
/**
* \brief Search for elements in 'box' in the Rtree. Add them to 'result'.
- * If exact_match is true only return the elements having as
- * key the box 'box'. Otherwise return everything inside 'box'.
*/
- virtual void find(Box const& box, std::deque<Value>& result, bool const exact_match, Translator const& tr)
+ virtual void find(Box const& box, std::deque<Value>& result, Translator const& tr)
{
- for (typename node_map::const_iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- // awulkiew - is_overlapping changed to geometry::intersects
- if (geometry::intersects(it->first, box))
- {
- it->second->find(box, result, exact_match, tr);
- }
- }
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
}
/**
- * \brief Return in 'result' all the leaves inside 'box'
- */
- void find_leaves(Box const& box, typename std::vector<node_pointer>& result) const
+ * \brief Compute bounding box for this node
+ */
+ virtual Box compute_box(Translator const&) const
{
- for (typename node_map::const_iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- // awulkiew - is_overlapping changed to geometry::intersects
- if (geometry::intersects(it->first, box))
- {
- if (it->second->is_leaf())
- {
- result.push_back(it->second);
- }
- else
- {
- it->second->find_leaves(box, result);
- }
- }
- }
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
+
+ return Box();
}
/**
- * \brief Compute bounding box for this node
+ * \brief Get leaves for a node
*/
- virtual Box compute_box(Translator const&) const
+ virtual std::vector<Value> get_leaves() const
{
- if (m_nodes.empty())
- {
- return Box();
- }
-
- Box result;
- geometry::assign_inverse(result);
- for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
- {
- geometry::combine(result, it->first);
- }
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
- return result;
+ return std::vector<Value>();
}
/**
- * \brief Insert a value (not allowed for a node, only on leaves)
+ * \brief Remove elements inside the 'box'
*/
- virtual void insert(Value const&)
+ // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
+ virtual void remove_in(Box const& box, Translator const&)
{
// TODO: mloskot - define & use GGL exception
- throw std::logic_error("Insert in node!");
+ throw std::logic_error("shouldn't be here");
}
/**
@@ -184,299 +129,175 @@
*/
virtual std::vector<Box> get_boxes(Translator const&) const
{
- std::vector<Box> result;
- for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
- {
- result.push_back(it->first);
- }
- return result;
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
+
+ return std::vector<Box>();
}
/**
- * \brief Recompute the bounding box
+ * \brief Print Rtree subtree (mainly for debug)
*/
- void adjust_box(node_pointer const& node, Translator const& tr)
+ virtual void print(Translator const& tr) const
{
- unsigned int index = 0;
- for (typename node_map::iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it, index++)
- {
- if (it->second.get() == node.get())
- {
- m_nodes[index] = std::make_pair(node->compute_box(tr), node);
- return;
- }
- }
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here");
}
+ // awulkiew - leaf only virtual methods
+
/**
- * \brief Remove elements inside the 'box'
+ * \brief Insert a value (not allowed for a node, only on leaves)
*/
- // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
- virtual void remove_in(Box const& box, Translator const&)
+ virtual void insert(Value const&)
{
- for (typename node_map::iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- if (geometry::equals(it->first, box))
- {
- m_nodes.erase(it);
- return;
- }
- }
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("Insert in node!");
}
/**
- * \brief Remove value in this leaf
+ * \brief add a value (not allowed in nodes, only on leaves)
*/
- virtual void remove(Value const&, Translator const&)
+ virtual void add_value(Value const&)
{
// TODO: mloskot - define & use GGL exception
- throw std::logic_error("Can't remove a non-leaf node by value.");
+ throw std::logic_error("Can't add value to non-leaf node.");
}
/**
- * \brief Replace the node in the m_nodes vector and recompute the box
+ * \brief Value projector for leaf_node (not allowed for non-leaf nodes)
*/
- void replace_node(node_pointer const& leaf, node_pointer& new_leaf, Translator const& tr)
+ virtual Value get_value(unsigned int) const
{
- unsigned int index = 0;
- for(typename node_map::iterator it = m_nodes.begin(); it != m_nodes.end(); ++it, index++)
- {
- if (it->second.get() == leaf.get())
- {
- m_nodes[index] = std::make_pair(new_leaf->compute_box(tr), new_leaf);
- new_leaf->update_parent(new_leaf);
- return;
- }
- }
-
// TODO: mloskot - define & use GGL exception
- throw std::logic_error("Node not found.");
+ throw std::logic_error("No values in a non-leaf node.");
}
/**
- * \brief Add a child to this node
+ * \brief Remove value in this leaf
*/
- virtual void add_node(Box const& box, node_pointer const& node)
+ virtual void remove(Value const&, Translator const&)
{
- m_nodes.push_back(std::make_pair(box, node));
- node->update_parent(node);
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("Can't remove a non-leaf node by value.");
}
+ // awulkiew - internal node only virtual methods
+
/**
- * \brief add a value (not allowed in nodes, only on leaves)
+ * \brief Add a new child (node) to this node
*/
- virtual void add_value(Value const&)
+ virtual void add_node(Box const&, node_pointer const&)
{
// TODO: mloskot - define & use GGL exception
- throw std::logic_error("Can't add value to non-leaf node.");
+ throw std::logic_error("Can't add node to leaf node.");
}
- /**
- * \brief Add a child leaf to this node
- */
- inline void add_leaf_node(Box const& box, leaf_pointer const& leaf)
+ virtual node_pointer first_element() const
{
- m_nodes.push_back(std::make_pair(box, leaf));
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
+ return node_pointer();
}
/**
- * \brief Choose a node suitable for adding 'box'
+ * \brief Proyector for the 'i' node
*/
- node_pointer choose_node(Box const& box)
+ virtual node_pointer get_node(size_t index)
{
- if (m_nodes.size() == 0)
- {
- // TODO: mloskot - define & use GGL exception
- throw std::logic_error("Empty node trying to choose the least enlargement node.");
- }
-
- // awulkiew - areas types changed
- typedef typename area_result<Box>::type area_type;
-
- bool first = true;
- area_type min_area = 0;
- area_type min_diff_area = 0;
- node_pointer chosen_node;
-
- // check for the least enlargement
- for (typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
- {
- // awulkiew - areas types changed
- area_type const diff_area = compute_union_area(box, it->first) - geometry::area(it->first);
-
- if (first)
- {
- // it's the first time, we keep the first
- min_diff_area = diff_area;
- min_area = geometry::area(it->first);
- chosen_node = it->second;
-
- first = false;
- }
- else
- {
- if (diff_area < min_diff_area)
- {
- min_diff_area = diff_area;
- min_area = geometry::area(it->first);
- chosen_node = it->second;
- }
- else
- {
- if (diff_area == min_diff_area)
- {
- if (geometry::area(it->first) < min_area)
- {
- min_diff_area = diff_area;
- min_area = geometry::area(it->first);
- chosen_node = it->second;
- }
- }
- }
- }
- }
-
- return chosen_node;
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
+ return node_pointer();
}
/**
- * \brief Empty the node
+ * \brief Return in 'result' all the leaves inside 'box'
*/
- virtual void empty_nodes()
+ virtual void find_leaves(Box const& box, typename std::vector<node_pointer>& result) const
{
- m_nodes.clear();
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
}
/**
- * \brief Projector for parent
+ * \brief Recompute the bounding box
*/
- inline node_pointer get_parent() const
+ virtual void adjust_box(node_pointer const& node, Translator const& tr)
{
- return m_parent;
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
}
/**
- * \brief Update the parent of all the childs
+ * \brief Replace the node in the m_nodes vector and recompute the box
*/
- void update_parent(node_pointer const& node)
+ virtual void replace_node(node_pointer const& leaf, node_pointer& new_leaf, Translator const& tr)
{
- for (typename node_map::iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
- {
- it->second->set_parent(node);
- }
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
}
/**
- * \brief Set parent
+ * \brief Add a child leaf to this node
*/
- void set_parent(node_pointer const& node)
+ virtual void add_leaf_node(Box const& box, leaf_pointer const& leaf)
{
- m_parent = node;
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
}
/**
- * \brief Value projector for leaf_node (not allowed for non-leaf nodes)
+ * \brief Choose a node suitable for adding 'box'
*/
- virtual Value get_value(unsigned int) const
+ virtual node_pointer choose_node(Box const& box)
{
// TODO: mloskot - define & use GGL exception
- throw std::logic_error("No values in a non-leaf node.");
+ throw std::logic_error("shouldn't be here.");
}
/**
- * \brief Box projector for node 'index'
+ * \brief Update the parent of all the childs
*/
- // awulkiew - commented, not used
- /*virtual Box get_box(unsigned int index, Translator const& tr) const
+ virtual void update_parent(node_pointer const& node)
{
- return m_nodes[index].first;
- }*/
+ // In case of leaf do nothing
+ }
/**
* \brief Box projector for node pointed by 'leaf'
*/
- // awulkiew - virtual keyword not needed
virtual Box get_box(node_pointer const& leaf) const
{
- for (typename node_map::const_iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- if (it->second.get() == leaf.get())
- {
- return it->first;
- }
- }
-
// TODO: mloskot - define & use GGL exception
- throw std::logic_error("Node not found");
+ throw std::logic_error("shouldn't be here.");
+ return Box();
}
/**
* \brief Children projector
*/
- node_map get_nodes() const
+ virtual node_map get_nodes() const
{
- return m_nodes;
+ // TODO: mloskot - define & use GGL exception
+ throw std::logic_error("shouldn't be here.");
+ return node_map();
}
+protected:
+
/**
- * \brief Get leaves for a node
- */
- virtual std::vector<Value> get_leaves() const
+ * \brief Creates a default node
+ */
+ rtree_node()
{
- typedef std::vector<Value> leaf_type;
- leaf_type leaf;
-
- for (typename node_map::const_iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- leaf_type this_leaves = it->second->get_leaves();
-
- for (typename leaf_type::iterator it_leaf = this_leaves.begin();
- it_leaf != this_leaves.end(); ++it_leaf)
- {
- leaf.push_back(*it_leaf);
- }
- }
-
- return leaf;
}
/**
- * \brief Print Rtree subtree (mainly for debug)
+ * \brief Creates a node with 'parent' as parent and 'level' as its level
*/
- virtual void print(Translator const& tr) const
+ rtree_node(node_pointer const& parent, size_t const& level)
+ : m_parent(parent), m_level(level)
{
- std::cerr << " --> Node --------" << std::endl;
- std::cerr << " Address: " << this << std::endl;
- std::cerr << " Level: " << m_level << std::endl;
- std::cerr << " Size: " << m_nodes.size() << std::endl;
- std::cerr << " | ";
- for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
- {
- if (this != it->second->get_parent().get())
- {
- std::cerr << "ERROR - " << this << " is not " << it->second->get_parent().get() << " ";
- }
-
- std::cerr << "( " << geometry::get<min_corner, 0>(it->first) << " , "
- << geometry::get<min_corner, 1>(it->first) << " ) x ";
- std::cerr << "( " << geometry::get<max_corner, 0>(it->first) << " , "
- << geometry::get<max_corner, 1>(it->first) << " )";
- std::cerr << " | ";
- }
- std::cerr << std::endl;
- std::cerr << " --< Node --------" << std::endl;
-
- // print child nodes
- std::cerr << " Children: " << std::endl;
- for (typename node_map::const_iterator it = m_nodes.begin();
- it != m_nodes.end(); ++it)
- {
- it->second->print(tr);
- }
}
private:
@@ -486,10 +307,8 @@
/// level of this node
// TODO: mloskot - Why not std::size_t or node_map::size_type, same with member functions?
- unsigned int m_level;
-
- /// child nodes
- node_map m_nodes;
+ // awulkiew - size_t used instead of unsigned int
+ size_t m_level;
};
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index_080_nhch/tests/rtree_native.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_nhch/tests/rtree_native.cpp (original)
+++ sandbox-branches/geometry/index_080_nhch/tests/rtree_native.cpp 2011-02-19 09:23:37 EST (Sat, 19 Feb 2011)
@@ -191,7 +191,7 @@
typedef boost::geometry::model::box<P> B;
boost::geometry::index::rtree<B>::rtree_leaf l;
- boost::geometry::index::rtree<B>::rtree_node n;
+ boost::geometry::index::rtree<B>::rtree_internal_node n;
std::cout << sizeof(boost::shared_ptr<int>) << '\n';
std::cout << sizeof(std::vector<int>) << '\n';