|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r68980 - in sandbox-branches/geometry/index_080: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/translator tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-02-17 20:16:22
Author: awulkiew
Date: 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
New Revision: 68980
URL: http://svn.boost.org/trac/boost/changeset/68980
Log:
translators used, interface changed
Added:
sandbox-branches/geometry/index_080/tests/rtree_native.cpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/helpers.hpp | 137 ++++++++++++++++++++++++++++++++++
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree.hpp | 160 ++++++++++++++++++++++++---------------
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_leaf.hpp | 24 +++--
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_node.hpp | 19 +---
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/def.hpp | 20 +++++
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/helpers.hpp | 53 ++++++++++++-
sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/index.hpp | 5 +
7 files changed, 332 insertions(+), 86 deletions(-)
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/helpers.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/helpers.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/helpers.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -16,6 +16,7 @@
// awulkiew - added
#include <boost/geometry/algorithms/combine.hpp>
+#include <boost/geometry/algorithms/convert.hpp>
namespace boost { namespace geometry { namespace index {
@@ -70,6 +71,142 @@
return ! geometry::disjoint(b1, b2);
}
+// awulkiew - structures and functions added below
+
+namespace dispatch {
+
+template <size_t D, typename SrcBox, typename DstBox>
+struct copy_box
+{
+ BOOST_STATIC_ASSERT(0 < D);
+
+ static void apply(SrcBox const& src, DstBox & dst)
+ {
+ geometry::set<min_corner, D - 1>(dst, geometry::get<min_corner, D - 1>(src));
+ geometry::set<max_corner, D - 1>(dst, geometry::get<max_corner, D - 1>(src));
+
+ copy_box<D - 1, SrcBox, DstBox>::apply(src, dst);
+ }
+};
+
+template <typename SrcBox, typename DstBox>
+struct copy_box<1, SrcBox, DstBox>
+{
+ static void apply(SrcBox const& src, DstBox & dst)
+ {
+ geometry::set<min_corner, 0>(dst, geometry::get<min_corner, 0>(src));
+ geometry::set<max_corner, 0>(dst, geometry::get<max_corner, 0>(src));
+ }
+};
+
+template <size_t D, typename Box>
+struct copy_box<D, Box, Box>
+{
+ BOOST_STATIC_ASSERT(0 < D);
+
+ static void apply(Box const& src, Box & dst)
+ {
+ dst = src;
+ }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename SrcBox, typename DstBox>
+void copy_box(SrcBox const& src, DstBox & dst)
+{
+ BOOST_STATIC_ASSERT(
+ traits::dimension<traits::point_type<SrcBox>::type>::value
+ == traits::dimension<traits::point_type<DstBox>::type>::value
+ );
+
+ dispatch::copy_box<
+ traits::dimension<traits::point_type<SrcBox>::type>::value,
+ SrcBox,
+ DstBox
+ >::apply(src, dst);
+}
+
+} // namespace detail
+
+namespace dispatch {
+
+template <typename BoundingObject, typename BoundingObjectTag, typename Box>
+struct convert_to_box
+{
+};
+
+template <typename BoundingObject, typename Box>
+struct convert_to_box<BoundingObject, geometry::box_tag, Box>
+{
+ static void apply(BoundingObject const& bo, Box & b)
+ {
+ detail::copy_box(bo, b);
+ }
+};
+
+template <typename BoundingObject, typename Box>
+struct convert_to_box<BoundingObject, geometry::point_tag, Box>
+{
+ static void apply(BoundingObject const& bo, Box & b)
+ {
+ geometry::convert(bo, b);
+ }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename BoundingObject, typename Box>
+void convert_to_box(BoundingObject const& bo, Box & b)
+{
+ dispatch::convert_to_box<
+ BoundingObject,
+ traits::tag<BoundingObject>::type,
+ Box
+ >::apply(bo, b);
+}
+
+} // namespace detail
+
+namespace dispatch {
+
+template <typename BoundingGeometry, typename BoundingGeometryTag>
+struct bounding_box
+{
+ typedef void type;
+};
+
+template <typename BoundingGeometry>
+struct bounding_box<BoundingGeometry, geometry::box_tag>
+{
+ typedef BoundingGeometry type;
+};
+
+template <typename BoundingGeometry>
+struct bounding_box<BoundingGeometry, geometry::point_tag>
+{
+ typedef geometry::model::box<BoundingGeometry> type;
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename BoundingGeometry>
+struct bounding_box
+{
+ typedef typename dispatch::bounding_box<
+ BoundingGeometry,
+ typename traits::tag<BoundingGeometry>::type
+ >::type type;
+};
+
+} // namespace detail
+
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_HELPERS_HPP
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -24,25 +24,38 @@
#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
#include <boost/geometry/extensions/index/rtree/rtree_leaf.hpp>
+// awulkiew - added
+#include <boost/geometry/extensions/index/translator/def.hpp>
+
namespace boost { namespace geometry { namespace index
{
-template <typename Box, typename Value >
+// awulkiew - template parameters changed
+template <
+ typename Value,
+ typename Translator = translator::def<Value>,
+ typename Box = detail::bounding_box<Translator::bounding_geometry_type>::type
+>
class rtree
{
public:
+ // awulkiew - typedefs added
+ typedef rtree_node<Box, Value, Translator> rtree_node;
+ typedef rtree_leaf<Box, Value, Translator> rtree_leaf;
- typedef boost::shared_ptr<rtree_node<Box, Value> > node_pointer;
- typedef boost::shared_ptr<rtree_leaf<Box, Value> > leaf_pointer;
+ typedef boost::shared_ptr<rtree_node> node_pointer;
+ typedef boost::shared_ptr<rtree_leaf> leaf_pointer;
/**
* \brief Creates a rtree with 'maximum' elements per node and 'minimum'.
*/
- rtree(unsigned int const& maximum, unsigned int const& minimum)
+ rtree(unsigned int const& maximum, unsigned int const& minimum, Translator tr = translator::def<Value>())
: m_count(0)
, m_min_elems_per_node(minimum)
, m_max_elems_per_node(maximum)
- , m_root(new rtree_node<Box, Value>(node_pointer(), 1))
+ , m_root(new rtree_node(node_pointer(), 1))
+ // awulkiew - added
+ , m_translator(tr)
{
}
@@ -50,11 +63,13 @@
* \brief Creates a rtree with maximum elements per node
* and minimum (box is ignored).
*/
- rtree(Box const& box, unsigned int const& maximum, unsigned int const& minimum)
+ rtree(Box const& box, unsigned int const& maximum, unsigned int const& minimum, Translator tr = translator::def<Value>())
: m_count(0)
, m_min_elems_per_node(minimum)
, m_max_elems_per_node(maximum)
- , m_root(new rtree_node<Box, Value>(node_pointer(), 1))
+ , m_root(new rtree_node(node_pointer(), 1))
+ // awulkiew - added
+ , m_translator(tr)
{
boost::ignore_unused_variable_warning(box);
}
@@ -68,44 +83,52 @@
/**
* \brief Remove elements inside the 'box'
*/
- inline void remove(Box const& box)
+ // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
+ inline void remove_in(Box const& box)
{
try
{
+// awulkiew - an error!
+// choose_exact_leaf returns wrong value
+// remember that remove_in() function is used in remove() so changing it may corrupt the other one
+
node_pointer leaf(choose_exact_leaf(box));
- typename rtree_leaf<Box, Value>::leaf_map q_leaves;
+ typename rtree_leaf::leaf_map q_leaves;
- leaf->remove(box);
+ leaf->remove_in(box);
if (leaf->elements() < m_min_elems_per_node && elements() > m_min_elems_per_node)
{
q_leaves = leaf->get_leaves();
// we remove the leaf_node in the parent node because now it's empty
- leaf->get_parent()->remove(leaf->get_parent()->get_box(leaf));
+ leaf->get_parent()->remove_in(leaf->get_parent()->get_box(leaf));
}
- typename rtree_node<Box, Value>::node_map q_nodes;
+ typename rtree_node::node_map q_nodes;
condense_tree(leaf, q_nodes);
std::vector<std::pair<Box, Value> > s;
- for (typename rtree_node<Box, Value>::node_map::const_iterator it = q_nodes.begin();
+ for (typename rtree_node::node_map::const_iterator it = q_nodes.begin();
it != q_nodes.end(); ++it)
{
- typename rtree_leaf<Box, Value>::leaf_map leaves = it->second->get_leaves();
+ typename rtree_leaf::leaf_map leaves = it->second->get_leaves();
// reinserting leaves from nodes
- for (typename rtree_leaf<Box, Value>::leaf_map::const_iterator itl = leaves.begin();
+ for (typename rtree_leaf::leaf_map::const_iterator itl = leaves.begin();
itl != leaves.end(); ++itl)
{
s.push_back(*itl);
}
}
- for (typename std::vector<std::pair<Box, Value> >::const_iterator it = s.begin(); it != s.end(); ++it)
+ for (typename std::vector<std::pair<Box, Value> >::const_iterator it = s.begin();
+ it != s.end();
+ ++it)
{
m_count--;
- insert(it->first, it->second);
+ // awulkiew - changed
+ insert(it->second);
}
// if the root has only one child and the child is not a leaf,
@@ -118,11 +141,12 @@
}
}
// reinserting leaves
- for (typename rtree_leaf<Box, Value>::leaf_map::const_iterator it = q_leaves.begin();
+ for (typename rtree_leaf::leaf_map::const_iterator it = q_leaves.begin();
it != q_leaves.end(); ++it)
{
m_count--;
- insert(it->first, it->second);
+ // awulkiew - parameters changed
+ insert(it->second);
}
m_count--;
@@ -140,14 +164,18 @@
/**
* \brief Remove element inside the box with value
*/
- void remove(Box const& box, Value const& value)
+ // awulkiew - added conversion to Box
+ void remove(Value const& value)
{
try
{
+ Box box;
+ detail::convert_to_box(m_translator(value), box);
+
node_pointer leaf;
// find possible leaves
- typedef typename std::vector<node_pointer > node_type;
+ typedef typename std::vector<node_pointer> node_type;
node_type nodes;
m_root->find_leaves(box, nodes);
@@ -157,7 +185,8 @@
leaf = *it;
try
{
- leaf->remove(value);
+ // awulkiew - translator passed
+ leaf->remove(value, m_translator);
break;
} catch (...)
{
@@ -168,37 +197,40 @@
if (!leaf)
return;
- typename rtree_leaf < Box, Value >::leaf_map q_leaves;
+ typename rtree_leaf::leaf_map q_leaves;
if (leaf->elements() < m_min_elems_per_node && elements() > m_min_elems_per_node)
{
q_leaves = leaf->get_leaves();
// we remove the leaf_node in the parent node because now it's empty
- leaf->get_parent()->remove(leaf->get_parent()->get_box(leaf));
+ leaf->get_parent()->remove_in(leaf->get_parent()->get_box(leaf));
}
- typename rtree_node<Box, Value>::node_map q_nodes;
+ typename rtree_node::node_map q_nodes;
condense_tree(leaf, q_nodes);
std::vector<std::pair<Box, Value> > s;
- for (typename rtree_node<Box, Value>::node_map::const_iterator it = q_nodes.begin();
+ for (typename rtree_node::node_map::const_iterator it = q_nodes.begin();
it != q_nodes.end(); ++it)
{
- typename rtree_leaf<Box, Value>::leaf_map leaves = it->second->get_leaves();
+ typename rtree_leaf::leaf_map leaves = it->second->get_leaves();
// reinserting leaves from nodes
- for (typename rtree_leaf<Box, Value>::leaf_map::const_iterator itl = leaves.begin();
+ for (typename rtree_leaf::leaf_map::const_iterator itl = leaves.begin();
itl != leaves.end(); ++itl)
{
s.push_back(*itl);
}
}
- for (typename std::vector<std::pair<Box, Value> >::const_iterator it = s.begin(); it != s.end(); ++it)
+ for (typename std::vector<std::pair<Box, Value> >::const_iterator it = s.begin();
+ it != s.end(); ++it)
{
m_count--;
- insert(it->first, it->second);
+ // awulkiew - changed
+ //insert(it->first, it->second);
+ insert(it->second);
}
// if the root has only one child and the child is not a leaf,
@@ -212,11 +244,13 @@
}
// reinserting leaves
- for (typename rtree_leaf<Box, Value>::leaf_map::const_iterator it = q_leaves.begin();
+ for (typename rtree_leaf::leaf_map::const_iterator it = q_leaves.begin();
it != q_leaves.end(); ++it)
{
m_count--;
- insert(it->first, it->second);
+ // awulkiew - changed
+ //insert(it->first, it->second);
+ insert(it->second);
}
m_count--;
@@ -244,8 +278,12 @@
/**
* \brief Inserts an element with 'box' as key with value.
*/
- inline void insert(Box const& box, Value const& value)
+ // awulkiew - added conversion to Box
+ inline void insert(Value const& value)
{
+ Box box;
+ detail::convert_to_box(m_translator(value), box);
+
m_count++;
node_pointer leaf(choose_corresponding_leaf(box));
@@ -256,8 +294,8 @@
leaf->insert(box, value);
// split!
- node_pointer n1(new rtree_leaf<Box, Value>(leaf->get_parent()));
- node_pointer n2(new rtree_leaf<Box, Value>(leaf->get_parent()));
+ node_pointer n1(new rtree_leaf(leaf->get_parent()));
+ node_pointer n2(new rtree_leaf(leaf->get_parent()));
split_node(leaf, n1, n2);
adjust_tree(leaf, n1, n2);
@@ -306,12 +344,14 @@
/// tree root
node_pointer m_root;
+ // awulkiew - added
+ Translator m_translator;
+
/**
* \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<Box, Value>::node_map& q_nodes)
+ void condense_tree(node_pointer const& leaf, typename rtree_node::node_map& q_nodes)
{
if (leaf.get() == m_root.get())
{
@@ -331,8 +371,8 @@
}
// get the nodes that we should reinsert
- typename rtree_node<Box, Value>::node_map this_nodes = parent->get_nodes();
- for(typename rtree_node<Box, Value>::node_map::const_iterator it = this_nodes.begin();
+ typename rtree_node::node_map this_nodes = parent->get_nodes();
+ for(typename rtree_node::node_map::const_iterator it = this_nodes.begin();
it != this_nodes.end(); ++it)
{
q_nodes.push_back(*it);
@@ -340,7 +380,7 @@
// we remove the node in the parent node because now it should be
// re inserted
- parent->get_parent()->remove(parent->get_parent()->get_box(parent));
+ parent->get_parent()->remove_in(parent->get_parent()->get_box(parent));
}
condense_tree(parent, q_nodes);
@@ -372,7 +412,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<Box,Value>(node_pointer (), leaf->get_level() + 1));
+ node_pointer new_root(new rtree_node(node_pointer(), leaf->get_level() + 1));
new_root->add_node(n1->compute_box(), n1);
new_root->add_node(n2->compute_box(), n2);
@@ -394,8 +434,8 @@
// if parent is full, split and readjust
if (parent->elements() > m_max_elems_per_node)
{
- node_pointer p1(new rtree_node<Box, Value>(parent->get_parent(), parent->get_level()));
- node_pointer p2(new rtree_node<Box, Value>(parent->get_parent(), parent->get_level()));
+ node_pointer p1(new rtree_node(parent->get_parent(), parent->get_level()));
+ node_pointer p2(new rtree_node(parent->get_parent(), parent->get_level()));
split_node(parent, p1, p2);
adjust_tree(parent, p1, p2);
@@ -437,10 +477,10 @@
{
// TODO: mloskot - add assert(node.size() >= 2); or similar
- typename rtree_leaf<Box, Value>::leaf_map nodes = n->get_leaves();
+ typename rtree_leaf::leaf_map nodes = n->get_leaves();
unsigned int remaining = nodes.size() - 2;
- for (typename rtree_leaf<Box, Value>::leaf_map::const_iterator it = nodes.begin();
+ for (typename rtree_leaf::leaf_map::const_iterator it = nodes.begin();
it != nodes.end(); ++it, index++)
{
if (index != seed1 && index != seed2)
@@ -468,9 +508,6 @@
/// areas
// awulkiew - areas types changed
- //typedef typename coordinate_type<Box>::type coordinate_type;
- //coordinate_type b1_area, b2_area;
- //coordinate_type eb1_area, eb2_area;
typedef typename area_result<Box>::type area_type;
area_type b1_area, b2_area;
area_type eb1_area, eb2_area;
@@ -517,9 +554,9 @@
{
// TODO: mloskot - add assert(node.size() >= 2); or similar
- typename rtree_node<Box, Value>::node_map nodes = n->get_nodes();
+ typename rtree_node::node_map nodes = n->get_nodes();
unsigned int remaining = nodes.size() - 2;
- for(typename rtree_node<Box, Value>::node_map::const_iterator it = nodes.begin();
+ for(typename rtree_node::node_map::const_iterator it = nodes.begin();
it != nodes.end(); ++it, index++)
{
@@ -549,9 +586,6 @@
/// areas
// awulkiew - areas types changed
- //typedef typename coordinate_type<Box>::type coordinate_type;
- //coordinate_type b1_area, b2_area;
- //coordinate_type eb1_area, eb2_area;
typedef typename area_result<Box>::type area_type;
area_type b1_area, b2_area;
area_type eb1_area, eb2_area;
@@ -639,8 +673,12 @@
* pick_seeds algorithm.
*/
template <std::size_t D, typename T>
- void find_normalized_separations(std::vector<Box> const& boxes, T& separation,
- unsigned int& first, unsigned int& second) const
+ void find_normalized_separations(
+ std::vector<Box> const& boxes,
+ T& separation,
+ unsigned int& first,
+ unsigned int& second
+ ) const
{
if (boxes.size() < 2)
{
@@ -730,8 +768,8 @@
// if the tree is empty add an initial leaf
if (m_root->elements() == 0)
{
- leaf_pointer new_leaf(new rtree_leaf<Box, Value>(m_root));
- m_root->add_leaf_node(Box (), new_leaf);
+ leaf_pointer new_leaf(new rtree_leaf(m_root));
+ m_root->add_leaf_node(Box(), new_leaf);
return new_leaf;
}
@@ -747,7 +785,8 @@
/**
* \brief Choose the exact leaf where an insertion should be done
*/
- node_pointer choose_exact_leaf(Box const&e) const
+ // awulkiew - this method is used only in remove_in() method
+ node_pointer choose_exact_leaf(Box const& e) const
{
// find possible leaves
typedef typename std::vector<node_pointer> node_type;
@@ -763,9 +802,8 @@
for (typename leaves_type::const_iterator itl = leaves.begin();
itl != leaves.end(); ++itl)
{
-
- if (itl->first.max_corner() == e.max_corner()
- && itl->first.min_corner() == e.min_corner())
+ // awulkiew - operator== changed to geometry::equals
+ if ( geometry::equals(itl->first, e) )
{
return *it;
}
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_leaf.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_leaf.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_leaf.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -27,13 +27,16 @@
namespace boost { namespace geometry { namespace index
{
-template <typename Box, typename Value >
-class rtree_leaf : public rtree_node<Box, Value>
+template <typename Box, typename Value, typename Translator>
+class rtree_leaf : public rtree_node<Box, Value, Translator>
{
public:
+ // awulkiew - typedef added
+ typedef rtree_node<Box, Value, Translator> rtree_node;
+
/// container type for the leaves
- typedef boost::shared_ptr<rtree_node<Box, Value> > node_pointer;
+ typedef boost::shared_ptr<rtree_node> node_pointer;
typedef std::vector<std::pair<Box, Value> > leaf_map;
/**
@@ -47,7 +50,7 @@
* \brief Creates a new leaf, with 'parent' as parent
*/
inline rtree_leaf(node_pointer const& parent)
- : rtree_node<Box, Value> (parent, 0)
+ : rtree_node(parent, 0)
{
}
@@ -166,7 +169,8 @@
/**
* \brief Remove value with key 'box' in this leaf
*/
- virtual void remove(Box const& box)
+ // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
+ virtual void remove_in(Box const& box)
{
for (typename leaf_map::iterator it = m_nodes.begin();
@@ -186,12 +190,13 @@
/**
* \brief Remove value in this leaf
*/
- virtual void remove(Value const& v)
+ virtual void remove(Value const& v, Translator const& tr)
{
for (typename leaf_map::iterator it = m_nodes.begin();
it != m_nodes.end(); ++it)
{
- if (it->second == v)
+ // awulkiew - use of translator
+ if ( tr.equals(it->second, v) )
{
m_nodes.erase(it);
return;
@@ -234,8 +239,9 @@
std::cerr << "( " << geometry::get<max_corner, 0>
(it->first) << " , " << geometry::get<max_corner, 1>
(it->first) << " )";
- std::cerr << " -> ";
- std::cerr << it->second;
+ // awulkiew - commented
+ //std::cerr << " -> ";
+ //std::cerr << it->second;
std::cerr << " | " << std::endl;;
}
std::cerr << "\t" << " --< Leaf --------" << std::endl;
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_node.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/rtree/rtree_node.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -28,16 +28,16 @@
namespace boost { namespace geometry { namespace index {
/// forward declaration
-template <typename Box, typename Value>
+template <typename Box, typename Value, typename Translator>
class rtree_leaf;
-template <typename Box, typename Value>
+template <typename Box, typename Value, typename Translator>
class rtree_node
{
public:
- typedef boost::shared_ptr<rtree_node<Box, Value> > node_pointer;
- typedef boost::shared_ptr<rtree_leaf<Box, Value> > leaf_pointer;
+ typedef boost::shared_ptr<rtree_node<Box, Value, Translator> > node_pointer;
+ typedef boost::shared_ptr<rtree_leaf<Box, Value, Translator> > leaf_pointer;
/// type for the node map
typedef std::vector<std::pair<Box, node_pointer > > node_map;
@@ -210,7 +210,8 @@
/**
* \brief Remove elements inside the 'box'
*/
- virtual void remove(Box const& box)
+ // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
+ virtual void remove_in(Box const& box)
{
for (typename node_map::iterator it = m_nodes.begin();
it != m_nodes.end(); ++it)
@@ -226,7 +227,7 @@
/**
* \brief Remove value in this leaf
*/
- virtual void remove(Value const&)
+ virtual void remove(Value const&, Translator const&)
{
// TODO: mloskot - define & use GGL exception
throw std::logic_error("Can't remove a non-leaf node by value.");
@@ -290,13 +291,10 @@
}
// awulkiew - areas types changed
- //typedef typename coordinate_type<Box>::type coordinate_type;
typedef typename area_result<Box>::type area_type;
bool first = true;
- //coordinate_type min_area = 0;
area_type min_area = 0;
- //coordinate_type min_diff_area = 0;
area_type min_diff_area = 0;
node_pointer chosen_node;
@@ -304,9 +302,6 @@
for (typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
{
// awulkiew - areas types changed
- //coordinate_type const
- // diff_area = coordinate_type(compute_union_area(box, it->first))
- // - geometry::area(it->first);
area_type const diff_area = compute_union_area(box, it->first) - geometry::area(it->first);
if (first)
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/def.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/def.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/def.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -28,6 +28,11 @@
{
return detail::extract_bounding_geometry<Value>::get(v);
}
+
+ bool equals(Value const& v1, Value const& v2) const
+ {
+ return detail::equals<Value>::apply(v1, v2);
+ }
};
// Iterator
@@ -40,6 +45,11 @@
{
return detail::extract_bounding_geometry<typename Value::value_type>::get(*v);
}
+
+ bool equals(Value const& v1, Value const& v2) const
+ {
+ return v1 == v2;
+ }
};
// SmartPtr
@@ -52,6 +62,11 @@
{
return detail::extract_bounding_geometry<typename Value::element_type>::get(*v);
}
+
+ bool equals(Value const& v1, Value const& v2) const
+ {
+ return v1 == v2;
+ }
};
} // namespace dispatch
@@ -76,6 +91,11 @@
{
return detail::extract_bounding_geometry<Value>::get(*v);
}
+
+ bool equals(const Value* v1, const Value* v2) const
+ {
+ return v1 == v2;
+ }
};
}}}} // namespace boost::geometry::index::translator
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/helpers.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/helpers.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/helpers.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -106,12 +106,12 @@
typedef typename dispatch::choose_pair_element<
std::pair<First, Second>,
typename dispatch::bounding_geometry<
- First,
- typename geometry::traits::tag<First>::type
+ First,
+ typename geometry::traits::tag<First>::type
>::type,
typename dispatch::bounding_geometry<
- Second,
- typename geometry::traits::tag<Second>::type
+ Second,
+ typename geometry::traits::tag<Second>::type
>::type
> cp;
@@ -159,6 +159,51 @@
} // namespace detail
+namespace dispatch {
+
+template <typename Geometry, typename Tag>
+struct equals
+{
+ static bool apply(Geometry const& g1, Geometry const& g2)
+ {
+ return geometry::equals(g1, g2);
+ }
+};
+
+template <typename T>
+struct equals<T, void>
+{
+ static bool apply(T const& v1, T const& v2)
+ {
+ return v1 == v2;
+ }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename Geometry>
+struct equals
+{
+ static bool apply(Geometry const& g1, Geometry const& g2)
+ {
+ return geometry::equals(g1, g2);
+ }
+};
+
+template <typename First, typename Second>
+struct equals< std::pair<First, Second> >
+{
+ static bool apply(std::pair<First, Second> const& p1, std::pair<First, Second> const& p2)
+ {
+ return dispatch::equals<First, traits::tag<First>::type>::apply(p1.first, p2.first) &&
+ dispatch::equals<Second, traits::tag<Second>::type>::apply(p1.second, p2.second);
+ }
+};
+
+} // namespace detail
+
}}}} // namespace boost::geometry::index::translator
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_HELPERS_HPP
Modified: sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/index.hpp
==============================================================================
--- sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/index.hpp (original)
+++ sandbox-branches/geometry/index_080/boost/geometry/extensions/index/translator/index.hpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -29,6 +29,11 @@
<typename Container::value_type>::get(m_c[i]);
}
+ bool equals(size_t i1, size_t i2) const
+ {
+ return i1 == i2;
+ }
+
private:
Container const& m_c;
};
Added: sandbox-branches/geometry/index_080/tests/rtree_native.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080/tests/rtree_native.cpp 2011-02-17 20:16:18 EST (Thu, 17 Feb 2011)
@@ -0,0 +1,158 @@
+#include <boost/geometry/geometry.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
+#include <iostream>
+
+#include <boost/range/algorithm.hpp>
+#include <boost/foreach.hpp>
+
+#include <map>
+
+int main()
+{
+ // Box
+ {
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+ typedef boost::geometry::model::box<P> B;
+
+ boost::geometry::index::rtree<B> t(3, 0);
+ t.insert(B(P(0, 0), P(1, 1)));
+ t.insert(B(P(2, 2), P(3, 3)));
+ t.insert(B(P(4, 4), P(5, 5)));
+ t.insert(B(P(6, 6), P(7, 7)));
+ t.print();
+
+ // error
+ t.remove_in(B(P(-1, -1), P(2, 2)));
+ // ok
+ t.remove_in(B(P(0, 0), P(1, 1)));
+ t.print();
+
+ t.remove(B(P(6, 6), P(7, 7)));
+ t.print();
+ }
+
+ std::cout << "-------------------------------------------------\n";
+ std::cout << "-------------------------------------------------\n";
+
+ // Point
+ {
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+ typedef boost::geometry::model::box<P> B;
+
+ boost::geometry::index::rtree<P> t(3, 0);
+ t.insert(P(0, 0));
+ t.insert(P(2, 2));
+ t.insert(P(4, 4));
+ t.insert(P(6, 6));
+ t.print();
+
+ // error
+ t.remove_in(B(P(-1, -1), P(1, 1)));
+ // ok
+ t.remove_in(B(P(0, 0), P(0, 0)));
+ t.print();
+
+ t.remove(P(6, 6));
+ t.print();
+ }
+
+ std::cout << "-------------------------------------------------\n";
+ std::cout << "-------------------------------------------------\n";
+
+ // std::pair<Box, int>
+ {
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+ typedef boost::geometry::model::box<P> B;
+ typedef std::pair<B, int> V;
+
+ boost::geometry::index::rtree<V> t(3, 0);
+ t.insert(V(B(P(0, 0), P(1, 1)), 0));
+ t.insert(V(B(P(2, 2), P(3, 3)), 1));
+ t.insert(V(B(P(4, 4), P(5, 5)), 2));
+ t.insert(V(B(P(6, 6), P(7, 7)), 3));
+ t.print();
+
+ // error
+ t.remove_in(B(P(0, 0), P(2, 1)));
+ // ok
+ t.remove_in(B(P(0, 0), P(1, 1)));
+ t.print();
+
+ t.remove(V(B(P(6, 6), P(7, 7)), 3));
+ t.print();
+ }
+
+ std::cout << "-------------------------------------------------\n";
+ std::cout << "-------------------------------------------------\n";
+
+ // boost::shared_ptr< std::pair<Box, int> >
+ {
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+ typedef boost::geometry::model::box<P> B;
+
+ typedef boost::shared_ptr< std::pair<B, int> > V;
+
+ V v1( new std::pair<B, int>(B(P(0, 0), P(1, 1)), 0) );
+ V v2( new std::pair<B, int>(B(P(2, 2), P(3, 3)), 1) );
+ V v3( new std::pair<B, int>(B(P(4, 4), P(5, 5)), 2) );
+ V v4( new std::pair<B, int>(B(P(6, 6), P(7, 7)), 3) );
+
+ boost::geometry::index::rtree<V> t(3, 0);
+ t.insert(v1);
+ t.insert(v2);
+ t.insert(v3);
+ t.insert(v4);
+ t.print();
+
+ // error
+ t.remove_in(B(P(0, 0), P(2, 1)));
+ // ok
+ t.remove_in(B(P(0, 0), P(1, 1)));
+ t.print();
+
+ t.remove(v4);
+ t.print();
+ }
+
+ std::cout << "-------------------------------------------------\n";
+ std::cout << "-------------------------------------------------\n";
+
+ // std::map<int, Box>::iterator
+ {
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+ typedef boost::geometry::model::box<P> B;
+
+ typedef std::map<int, B>::iterator V;
+
+ std::map<int, B> m;
+ m.insert(std::pair<int, B>(0, B(P(0, 0), P(1, 1))));
+ m.insert(std::pair<int, B>(1, B(P(2, 2), P(3, 3))));
+ m.insert(std::pair<int, B>(2, B(P(4, 4), P(5, 5))));
+ m.insert(std::pair<int, B>(3, B(P(6, 6), P(7, 7))));
+
+ boost::geometry::index::rtree<V> t(3, 0);
+ V vit = m.begin();
+ t.insert(vit++);
+ t.insert(vit++);
+ t.insert(vit++);
+ t.insert(vit);
+ t.print();
+
+ // error
+ t.remove_in(B(P(0, 0), P(2, 1)));
+ // ok
+ t.remove_in(B(P(0, 0), P(1, 1)));
+ t.print();
+
+ t.remove(m.find(3));
+ t.print();
+ }
+
+ // ERROR!
+ // remove_in expects previously inserted box - it should remove all objects inside some bigger box
+
+ std::cin.get();
+ return 0;
+}
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