[Boost-commit] svn:boost r69728 - in sandbox-branches/geometry/index_080_vis: boost boost/geometry boost/geometry/extensions boost/geometry/extensions/index boost/geometry/extensions/index/filters boost/geometry/extensions/index/rtree boost/geometry/extensions/index/translator tests

Subject: [Boost-commit] svn:boost r69728 - in sandbox-branches/geometry/index_080_vis: boost boost/geometry boost/geometry/extensions boost/geometry/extensions/index boost/geometry/extensions/index/filters boost/geometry/extensions/index/rtree boost/geometry/extensions/index/translator tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-03-08 16:13:08

Author: awulkiew
Date: 2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
New Revision: 69728
URL: http://svn.boost.org/trac/boost/changeset/69728

Log:
starting point
Added:
   sandbox-branches/geometry/index_080_vis/boost/
   sandbox-branches/geometry/index_080_vis/boost/geometry/
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/nearest_filter.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/spacial_filter.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/filters.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/helpers.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_internal_node.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_leaf.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_node.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/def.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/helpers.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/index.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/tests/
   sandbox-branches/geometry/index_080_vis/tests/additional_glut_vis.cpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/tests/additional_sizes_and_times.cpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/tests/main.cpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/tests/rtree_filters.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/tests/rtree_native.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_vis/tests/translators.hpp   (contents, props changed)

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/nearest_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/nearest_filter.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,78 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - nearest neighbour filter implementation
+//
+// 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_FILTERS_NEAREST_FILTER_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_FILTERS_NEAREST_FILTER_HPP
+
+namespace boost { namespace geometry { namespace index { namespace filters {
+
+template <typename SpacialIndex>
+class nearest_filter
+{
+public:
+    typedef int* iterator;
+    typedef const int* const_iterator;
+
+    template <typename Point>
+    nearest_filter(
+        SpacialIndex const&,
+        Point const&,
+        typename traits::coordinate_type<Point>::type const&
+    )
+    {}
+
+    iterator begin() { return 0; }
+    iterator end() { return 0; }
+    const_iterator begin() const { return 0; }
+    const_iterator end() const { return 0; }
+};
+
+namespace detail {
+
+template<typename Point>
+class nearest_filtered
+{
+public:
+    explicit nearest_filtered(
+        Point const& p,
+        typename traits::coordinate_type<Point>::type const& distance)
+        : m_point(p), m_distance(distance) {}
+
+    Point const& point() const { return m_point; }
+
+    typename traits::coordinate_type<Point>::type const&
+    distance() const { return m_distance; }
+
+private:
+    Point m_point;
+    typename traits::coordinate_type<Point>::type m_distance;
+};
+
+} // namespace detail
+
+template <typename Point>
+detail::nearest_filtered<Point> nearest_filtered(
+    Point const& p,
+    typename traits::coordinate_type<Point>::type const& distance)
+{
+    return detail::nearest_filtered<Point>(p, distance);
+}
+
+}}}} // namespace boost::geometry::index::filters
+
+template<typename SpacialIndex, typename Point>
+boost::geometry::index::filters::nearest_filter<SpacialIndex>
+    operator|(
+    SpacialIndex const& si,
+    boost::geometry::index::filters::detail::nearest_filtered<Point> const& f)
+{
+    return boost::geometry::index::filters::nearest_filter<SpacialIndex>(si, f.point(), f.distance());
+}
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_FILTERS_NEAREST_FILTER_HPP

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/spacial_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/filters/spacial_filter.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,63 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - box query filter implementation
+//
+// 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_FILTERS_SPACIAL_FILTER_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_FILTERS_SPACIAL_FILTER_HPP
+
+namespace boost { namespace geometry { namespace index { namespace filters {
+
+template <typename SpacialIndex>
+class spatial_filter
+{
+public:
+    typedef int* iterator;
+    typedef const int* const_iterator;
+
+    template <typename Box>
+    spatial_filter(SpacialIndex const&, Box const&) {}
+
+    iterator begin() { return 0; }
+    iterator end() { return 0; }
+    const_iterator begin() const { return 0; }
+    const_iterator end() const { return 0; }
+};
+
+namespace detail {
+
+template<typename Box>
+class spatially_filtered
+{
+public:
+    explicit spatially_filtered(Box const& b) : m_box(b) {}
+    Box const& box() const { return m_box; }
+
+private:
+    Box m_box;
+};
+
+} // namespace detail
+
+template <typename Box>
+detail::spatially_filtered<Box> spatially_filtered(Box const& b)
+{
+    return detail::spatially_filtered<Box>(b);
+}
+
+}}}} // namespace boost::geometry::index::filters
+
+template<typename SpacialIndex, typename Box>
+boost::geometry::index::filters::spatial_filter<SpacialIndex>
+operator|(
+    SpacialIndex const& si,
+    boost::geometry::index::filters::detail::spatially_filtered<Box> const& f)
+{
+    return boost::geometry::index::filters::spatial_filter<SpacialIndex>(si, f.box());
+}
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_FILTERS_SPACIAL_FILTER_HPP

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/filters.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/filters.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,118 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - rtree queries filters implementation
+//
+// 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_FILTERS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP
+
+#include <boost/static_assert.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+#include <boost/geometry/extensions/index/filters/spacial_filter.hpp>
+#include <boost/geometry/extensions/index/filters/nearest_filter.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace filters {
+
+template <typename Value, typename Translator, typename Box>
+class spatial_filter< index::rtree<Value, Translator, Box> >
+{
+public:
+    typedef typename std::deque<Value>::iterator iterator;
+    typedef typename std::deque<Value>::const_iterator const_iterator;
+
+    spatial_filter(index::rtree<Value, Translator, Box> const& rtree, Box const& b)
+    {
+        m_result = rtree.find(b);
+    }
+
+    iterator begin() { return m_result.begin(); }
+    iterator end() { return m_result.end(); }
+    const_iterator begin() const { return m_result.begin(); }
+    const_iterator end() const { return m_result.end(); }
+
+private:
+    std::deque<Value> m_result;
+};
+
+namespace detail {
+
+template <typename Box, size_t D>
+struct sphere_to_min_max
+{
+    BOOST_STATIC_ASSERT(0 < D);
+
+    static void apply(
+        typename traits::point_type<Box>::type & min_point,
+        typename traits::point_type<Box>::type & max_point,
+        typename traits::point_type<Box>::type const& centre,
+        typename traits::coordinate_type<typename traits::point_type<Box>::type>::type const& radius
+        )
+    {
+        geometry::set<D - 1>(min_point, geometry::get<D - 1>(centre) - radius);
+        geometry::set<D - 1>(max_point, geometry::get<D - 1>(centre) + radius);
+
+        sphere_to_min_max<Box, D - 1>::apply(min_point, max_point, centre, radius);
+    }
+};
+
+template <typename Box>
+struct sphere_to_min_max<Box, 1>
+{
+    static void apply(
+        typename traits::point_type<Box>::type & min_point,
+        typename traits::point_type<Box>::type & max_point,
+        typename traits::point_type<Box>::type const& centre,
+        typename traits::coordinate_type<typename traits::point_type<Box>::type>::type const& radius
+        )
+    {
+        geometry::set<0>(min_point, geometry::get<0>(centre) - radius);
+        geometry::set<0>(max_point, geometry::get<0>(centre) + radius);
+    }
+};
+
+} // namespace detail
+
+// TODO
+// implement final version of nearest filter
+// range should be sorted (for Boxes - by closest corner)
+
+template <typename Value, typename Translator, typename Box>
+class nearest_filter< index::rtree<Value, Translator, Box> >
+{
+public:
+    typedef typename std::deque<Value>::iterator iterator;
+    typedef typename std::deque<Value>::const_iterator const_iterator;
+
+    template <typename Point>
+    nearest_filter(
+        index::rtree<Value, Translator, Box> const& rtree,
+        Point const& box_centre,
+        typename traits::coordinate_type<Point>::type const& radius
+        )
+    {
+    	typename traits::point_type<Box>::type pmin, pmax;
+        detail::sphere_to_min_max<
+            Box,
+            traits::dimension<typename traits::point_type<Box>::type>::value
+        >::apply(pmin, pmax, box_centre, radius);
+
+        m_result = rtree.find(Box(pmin, pmax));
+    }
+
+    iterator begin() { return m_result.begin(); }
+    iterator end() { return m_result.end(); }
+    const_iterator begin() const { return m_result.begin(); }
+    const_iterator end() const { return m_result.end(); }
+
+private:
+    std::deque<Value> m_result;
+};
+
+}}}} // namespace boost::geometry::index::filters
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/helpers.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/helpers.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,218 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - geometry helper functions
+//
+// 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)
+
+// awulkiew 2011
+//   enlarge_box, is_overlapping removed (functions from boost::geometry used)
+//   compute_union_area changed
+//   other helpers added - some of them temporary
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_HELPERS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_HELPERS_HPP
+
+#include <boost/geometry/algorithms/area.hpp>
+#include <boost/geometry/algorithms/disjoint.hpp>
+#include <boost/geometry/core/point_type.hpp>
+
+// awulkiew - added
+#include <boost/geometry/algorithms/combine.hpp>
+#include <boost/geometry/algorithms/convert.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+/**
+ * \brief Given two boxes, returns the minimal box that contains them
+ */
+// TODO: use geometry::combine
+// awulkiew - geometry::combine used
+//template <typename Box>
+//inline Box enlarge_box(Box const& b1, Box const& b2)
+//{
+//    // TODO: mloskot - Refactor to readable form. Fix VC++8.0 min/max warnings:
+//    //  warning C4002: too many actual parameters for macro 'min
+//
+//    typedef typename geometry::point_type<Box>::type point_type;
+//
+//    point_type pmin(
+//        geometry::get<min_corner, 0>(b1) < geometry::get<min_corner, 0>(b2)
+//            ? geometry::get<min_corner, 0>(b1) : geometry::get<min_corner, 0>(b2),
+//        geometry::get<min_corner, 1>(b1) < geometry::get<min_corner, 1>(b2)
+//            ? geometry::get<min_corner, 1>(b1) : geometry::get<min_corner, 1>(b2));
+//
+//    point_type pmax(
+//        geometry::get<max_corner, 0>(b1) > geometry::get<max_corner, 0>(b2)
+//            ? geometry::get<max_corner, 0>(b1) : geometry::get<max_corner, 0>(b2),
+//        geometry::get<max_corner, 1>(b1) > geometry::get<max_corner, 1>(b2)
+//            ? geometry::get<max_corner, 1>(b1) : geometry::get<max_corner, 1>(b2));
+//
+//    return Box(pmin, pmax);
+//}
+
+/**
+ * \brief Compute the area of the union of b1 and b2
+ */
+template <typename Box, typename Geometry>
+inline typename area_result<Box>::type compute_union_area(Box const& b, Geometry const& g)
+{
+    //Box enlarged_box = enlarge_box(b1, b2);
+    // awulkiew - changed to geometry::combine
+    Box enlarged_box(b);
+    geometry::combine(enlarged_box, g);
+    return geometry::area(enlarged_box);
+}
+
+/**
+ * \brief Checks if boxes intersects
+ */
+// TODO: move to geometry::intersects
+// awulkiew - geometry::intersects used
+//template <typename Geometry1, typename Geometry2>
+//inline bool is_overlapping(Geometry1 const& b1, Geometry2 const& b2)
+//{
+//    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<typename traits::point_type<SrcBox>::type>::value
+        == traits::dimension<typename traits::point_type<DstBox>::type>::value
+    );
+
+    dispatch::copy_box<
+        traits::dimension<typename 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,
+        typename 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

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,865 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - rtree 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)
+
+// awulkiew 2011
+//   typedefs added
+//   nodes hierarchy changed
+//   coordinate_type changed to area_result<Box>::type in areas calculation
+//   translator added
+//   gl_draw added - temporary
+
+// TODO: awulkiew - implement different method of tree drawing algorithm
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_HPP
+
+#include <cstddef>
+#include <iostream> // TODO: Remove if print() is removed
+#include <stdexcept>
+#include <utility>
+#include <vector>
+
+#include <boost/concept_check.hpp>
+#include <boost/shared_ptr.hpp>
+
+#include <boost/geometry/algorithms/area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree_internal_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 {
+
+// awulkiew - template parameters changed
+template <
+    typename Value,
+    typename Translator = translator::def<Value>,
+    typename Box = typename detail::bounding_box
+		<typename Translator::bounding_geometry_type>::type
+>
+class rtree
+{
+public:
+    // awulkiew - typedefs added
+    typedef Value value_type;
+
+    typedef geometry::index::rtree_node<Value, Translator, Box> rtree_node;
+    typedef geometry::index::rtree_leaf<Value, Translator, Box> rtree_leaf;
+    typedef geometry::index::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;
+
+    /**
+     * \brief Creates a rtree with 'maximum' elements per node and 'minimum'.
+     */
+    rtree(unsigned int const& maximum, unsigned int const& minimum, Translator tr = Translator())
+        : m_count(0)
+        , m_min_elems_per_node(minimum)
+        , m_max_elems_per_node(maximum)
+        , m_root(new rtree_internal_node(node_pointer(), 1))
+        // awulkiew - added
+        , m_translator(tr)
+    {
+    }
+
+    /**
+     * \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, 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(node_pointer(), 1))
+        // awulkiew - added
+        , m_translator(tr)
+    {
+        boost::ignore_unused_variable_warning(box);
+    }
+
+    /**
+     * \brief destructor (virtual because we have virtual functions)
+     */
+    virtual ~rtree() {}
+
+
+    /**
+     * \brief Remove elements inside the '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::values_map q_values;
+
+            leaf->remove_in(box, m_translator);
+
+            if (leaf->elements() < m_min_elems_per_node && elements() > m_min_elems_per_node)
+            {
+                q_values = leaf->get_values();
+
+                // we remove the leaf_node in the parent node because now it's empty
+                leaf->get_parent()->remove_in(leaf->get_parent()->get_box(leaf), m_translator);
+            }
+
+            typename rtree_internal_node::node_map q_nodes;
+            condense_tree(leaf, q_nodes);
+
+            std::vector<Value> s;
+            for (typename rtree_internal_node::node_map::const_iterator it = q_nodes.begin();
+                 it != q_nodes.end(); ++it)
+            {
+                typename rtree_leaf::values_map values = it->second->get_values();
+
+                // reinserting values from nodes
+                for (typename rtree_leaf::values_map::const_iterator itl = values.begin();
+                     itl != values.end(); ++itl)
+                {
+                    s.push_back(*itl);
+                }
+            }
+
+            for (typename std::vector<Value>::const_iterator it = s.begin();
+                it != s.end();
+                ++it)
+            {
+                m_count--;
+                // awulkiew - changed
+                insert(*it);
+            }
+
+            // if the root has only one child and the child is not a leaf,
+            // make it the root
+            if (m_root->elements() == 1)
+            {
+                if (!m_root->first_element()->is_leaf())
+                {
+                    m_root = m_root->first_element();
+                }
+            }
+            // reinserting leaves
+            for (typename rtree_leaf::values_map::const_iterator it = q_values.begin();
+                 it != q_values.end(); ++it)
+            {
+                m_count--;
+                // awulkiew - parameters changed
+                insert(*it);
+            }
+
+            m_count--;
+        }
+        catch(std::logic_error & e)
+        {
+            // TODO: mloskot - replace with Boost.Geometry exception
+
+            // not found
+            std::cerr << e.what() << std::endl;
+            return;
+        }
+    }
+
+    /**
+     * \brief Remove element inside the box with value
+     */
+    void remove(Value const& value)
+    {
+        try
+        {
+            // awulkiew - added conversion to Box
+            Box box;
+            detail::convert_to_box(m_translator(value), box);
+            
+            node_pointer leaf;
+
+            // find possible leaves
+            typedef typename std::vector<node_pointer> node_type;
+            node_type nodes;
+            m_root->find_leaves(box, nodes);
+
+            // refine the result
+            for (typename node_type::const_iterator it = nodes.begin(); it != nodes.end(); ++it)
+            {
+                leaf = *it;
+                try
+                {
+                    // TODO: awulkiew - exception shouldn't be used as a way to check if value wasn't removed from leaf
+
+                    // awulkiew - translator passed
+                    leaf->remove(value, m_translator);
+                    break;
+                } catch (...)
+                {
+                    leaf = node_pointer();
+                }
+            }
+
+            if (!leaf)
+                return;
+
+            typename rtree_leaf::values_map q_values;
+
+            if (leaf->elements() < m_min_elems_per_node && elements() > m_min_elems_per_node)
+            {
+                q_values = leaf->get_values();
+
+                // we remove the leaf_node in the parent node because now it's empty
+                leaf->get_parent()->remove_in(leaf->get_parent()->get_box(leaf), m_translator);
+            }
+
+            typename rtree_internal_node::node_map q_nodes;
+            condense_tree(leaf, q_nodes);
+
+            std::vector<Value> s;
+            for (typename rtree_internal_node::node_map::const_iterator it = q_nodes.begin();
+                 it != q_nodes.end(); ++it)
+            {
+                typename rtree_leaf::values_map values = it->second->get_values();
+
+                // reinserting leaves from nodes
+                for (typename rtree_leaf::values_map::const_iterator itl = values.begin();
+                     itl != values.end(); ++itl)
+                {
+                    s.push_back(*itl);
+                }
+            }
+
+            for (typename std::vector<Value>::const_iterator it = s.begin();
+                it != s.end(); ++it)
+            {
+                m_count--;
+                // awulkiew - changed
+                //insert(it->first, it->second);
+                insert(*it);
+            }
+
+            // if the root has only one child and the child is not a leaf,
+            // make it the root
+            if (m_root->elements() == 1)
+            {
+                if (!m_root->first_element()->is_leaf())
+                {
+                    m_root = m_root->first_element();
+                }
+            }
+
+            // reinserting leaves
+            for (typename rtree_leaf::values_map::const_iterator it = q_values.begin();
+                 it != q_values.end(); ++it)
+            {
+                m_count--;
+                // awulkiew - changed
+                //insert(it->first, it->second);
+                insert(*it);
+            }
+
+            m_count--;
+
+        }
+        catch(std::logic_error & e)
+        {
+            // TODO: mloskot - ggl exception
+
+            // not found
+            std::cerr << e.what() << std::endl;
+            
+            // awulkiew - not needed
+            return;
+        }
+    }
+
+    /**
+     * \brief Returns the number of elements.
+     */
+    inline unsigned int elements() const
+    {
+        return m_count;
+    }
+
+
+    /**
+     * \brief Inserts an element with 'box' as key with value.
+     */
+    inline void insert(Value const& value)
+    {
+        // awulkiew - added conversion to Box
+        Box box;
+        detail::convert_to_box(m_translator(value), box);
+
+        m_count++;
+
+        node_pointer leaf(choose_corresponding_leaf(box));
+
+        // check if the selected leaf is full to do the split if necessary
+        if (leaf->elements() >= m_max_elems_per_node)
+        {
+            leaf->insert(value);
+
+            // split!
+            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);
+        }
+        else
+        {
+            leaf->insert(value);
+            adjust_tree(leaf);
+        }
+    }
+
+
+    /**
+     * \brief Returns all the values inside 'box'
+     */
+    inline std::deque<Value> find(Box const& box) const
+    {
+        std::deque<Value> result;
+        m_root->find(box, result, m_translator);
+        return result;
+    }
+
+    /**
+     * \brief Print Rtree (mainly for debug)
+     */
+    // awulkiew - print() method changed to operator<<
+    friend std::ostream & operator<<(std::ostream &os, rtree const& r)
+    {
+        os << "===================================" << std::endl;
+        os << " Min/Max: " << r.m_min_elems_per_node << " / " << r.m_max_elems_per_node << std::endl;
+        os << "Leaves: " << r.m_root->get_values().size() << std::endl;
+        r.m_root->print(os, r.m_translator);
+        os << "===================================" << std::endl;
+
+        return os;
+    }
+
+#ifdef BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    void gl_draw() const
+    {
+        glClear(GL_COLOR_BUFFER_BIT);
+
+        m_root->gl_draw(m_translator);
+
+        glFlush();
+    }
+
+#endif // BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    std::vector<Box> get_level_boxes(size_t level) const
+    {
+        m_root->get_level_boxes(level, m_translator);
+    }
+
+private:
+
+    /// number of elements
+    unsigned int m_count;
+
+    /// minimum number of elements per node
+    unsigned int m_min_elems_per_node;
+
+    /// maximum number of elements per node
+    unsigned int m_max_elems_per_node;
+
+    /// 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_internal_node::node_map& q_nodes)
+    {
+        if (leaf.get() == m_root.get())
+        {
+            // if it's the root we are done
+            return;
+        }
+
+        node_pointer parent = leaf->get_parent();
+        parent->adjust_box(leaf, m_translator);
+
+        if (parent->elements() < m_min_elems_per_node)
+        {
+            if (parent.get() == m_root.get())
+            {
+                // if the parent is underfull and it's the root we just exit
+                return;
+            }
+
+            // get the nodes that we should reinsert
+            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);
+            }
+
+            // we remove the node in the parent node because now it should be
+            // re inserted
+            parent->get_parent()->remove_in(parent->get_parent()->get_box(parent), m_translator);
+        }
+
+        condense_tree(parent, q_nodes);
+    }
+
+    /**
+     * \brief After an insertion splits nodes with more than 'maximum' elements.
+     */
+    inline void adjust_tree(node_pointer& node)
+    {
+        if (node.get() == m_root.get())
+        {
+            // we finished the adjust
+            return;
+        }
+
+        // as there are no splits just adjust the box of the parent and go on
+        node_pointer parent = node->get_parent();
+        parent->adjust_box(node, m_translator);
+        adjust_tree(parent);
+    }
+
+    /**
+     * \brief After an insertion splits nodes with more than maximum elements
+     *        (recursive step with subtrees 'n1' and 'n2' to be joined).
+     */
+    void adjust_tree(node_pointer& leaf, node_pointer& n1, node_pointer& n2)
+    {
+        // check if we are in the root and do the split
+        if (leaf.get() == m_root.get())
+        {
+            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);
+
+            n1->set_parent(new_root);
+            n2->set_parent(new_root);
+
+            n1->set_children_parent(n1);
+            n2->set_children_parent(n2);
+
+            m_root = new_root;
+            return;
+        }
+
+        node_pointer parent = leaf->get_parent();
+
+        parent->replace_node(leaf, n1, m_translator);
+        parent->add_node(n2->compute_box(m_translator), n2);
+
+        // if parent is full, split and readjust
+        if (parent->elements() > m_max_elems_per_node)
+        {
+            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);
+        }
+        else
+        {
+            adjust_tree(parent);
+        }
+    }
+
+    /**
+     * \brief Splits 'n' in 'n1' and 'n2'
+     */
+    void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const
+    {
+        unsigned int seed1 = 0;
+        unsigned int seed2 = 0;
+        std::vector<Box> boxes = n->get_boxes(m_translator);
+
+        n1->set_parent(n->get_parent());
+        n2->set_parent(n->get_parent());
+
+        // awulkiew - node_pointer parameter changed to std::vector<Box>
+        linear_pick_seeds(boxes, seed1, seed2);
+
+        if (n->is_leaf())
+        {
+            n1->add_value(n->get_value(seed1));
+            n2->add_value(n->get_value(seed2));
+        }
+        else
+        {
+            n1->add_node(boxes[seed1], n->get_node(seed1));
+            n2->add_node(boxes[seed2], n->get_node(seed2));
+        }
+
+        unsigned int index = 0;
+
+        if (n->is_leaf())
+        {
+            // TODO: mloskot - add assert(node.size() >= 2); or similar
+
+            typename rtree_leaf::values_map values = n->get_values();
+            unsigned int remaining = values.size() - 2;
+
+            for (typename rtree_leaf::values_map::const_iterator it = values.begin();
+                 it != values.end(); ++it, index++)
+            {
+                if (index != seed1 && index != seed2)
+                {
+                    if (n1->elements() + remaining == m_min_elems_per_node)
+                    {
+                        n1->add_value(*it);
+                        continue;
+                    }
+                    if (n2->elements() + remaining == m_min_elems_per_node)
+                    {
+                        n2->add_value(*it);
+                        continue;
+                    }
+
+                    remaining--;
+
+                    /// current boxes of each group
+                    Box b1, b2;
+
+                    /// enlarged boxes of each group
+                    Box eb1, eb2;
+                    b1 = n1->compute_box(m_translator);
+                    b2 = n2->compute_box(m_translator);
+
+                    /// areas
+                    // awulkiew - areas types changed
+                    typedef typename area_result<Box>::type area_type;
+                    area_type b1_area, b2_area;
+                    area_type eb1_area, eb2_area;
+
+                    b1_area = geometry::area(b1);
+                    b2_area = geometry::area(b2);
+                    eb1_area = compute_union_area(b1, m_translator(*it));
+                    eb2_area = compute_union_area(b2, m_translator(*it));
+
+                    if (eb1_area - b1_area > eb2_area - b2_area)
+                    {
+                        n2->add_value(*it);
+                    }
+                    if (eb1_area - b1_area < eb2_area - b2_area)
+                    {
+                        n1->add_value(*it);
+                    }
+                    if (eb1_area - b1_area == eb2_area - b2_area)
+                    {
+                        if (b1_area < b2_area)
+                        {
+                            n1->add_value(*it);
+                        }
+                        if (b1_area > b2_area)
+                        {
+                            n2->add_value(*it);
+                        }
+                        if (b1_area == b2_area)
+                        {
+                            if (n1->elements() > n2->elements())
+                            {
+                                n2->add_value(*it);
+                            }
+                            else
+                            {
+                                n1->add_value(*it);
+                            }
+                        }
+                    }
+                }
+            }
+        }
+        else
+        {
+            // TODO: mloskot - add assert(node.size() >= 2); or similar
+
+            typename rtree_node::node_map nodes = n->get_nodes();
+            unsigned int remaining = nodes.size() - 2;
+            for(typename rtree_node::node_map::const_iterator it = nodes.begin();
+                it != nodes.end(); ++it, index++)
+            {
+
+                if (index != seed1 && index != seed2)
+                {
+
+                    if (n1->elements() + remaining == m_min_elems_per_node)
+                    {
+                        n1->add_node(it->first, it->second);
+                        continue;
+                    }
+                    if (n2->elements() + remaining == m_min_elems_per_node)
+                    {
+                        n2->add_node(it->first, it->second);
+                        continue;
+                    }
+
+                    remaining--;
+
+                    /// current boxes of each group
+                    Box b1, b2;
+
+                    /// enlarged boxes of each group
+                    Box eb1, eb2;
+                    b1 = n1->compute_box(m_translator);
+                    b2 = n2->compute_box(m_translator);
+
+                    /// areas
+                    // awulkiew - areas types changed
+                    typedef typename area_result<Box>::type area_type;
+                    area_type b1_area, b2_area;
+                    area_type eb1_area, eb2_area;
+
+                    b1_area = geometry::area(b1);
+                    b2_area = geometry::area(b2);
+                    eb1_area = compute_union_area(b1, it->first);
+                    eb2_area = compute_union_area(b2, it->first);
+
+                    if (eb1_area - b1_area > eb2_area - b2_area)
+                    {
+                        n2->add_node(it->first, it->second);
+                    }
+                    if (eb1_area - b1_area < eb2_area - b2_area)
+                    {
+                        n1->add_node(it->first, it->second);
+                    }
+                    if (eb1_area - b1_area == eb2_area - b2_area)
+                    {
+                        if (b1_area < b2_area)
+                        {
+                            n1->add_node(it->first, it->second);
+                        }
+                        if (b1_area > b2_area)
+                        {
+                            n2->add_node(it->first, it->second);
+                        }
+                        if (b1_area == b2_area)
+                        {
+                            if (n1->elements() > n2->elements())
+                            {
+                                n2->add_node(it->first, it->second);
+                            }
+                            else
+                            {
+                                n1->add_node(it->first, it->second);
+                            }
+                        }
+                    }
+
+                }
+            }
+        }
+    }
+
+    /**
+     * \brief Choose initial values for the split algorithm (linear version)
+     */
+    // awulkiew - parameter changed from node_pointer to std::vector<Box>
+    void linear_pick_seeds(std::vector<Box> const& boxes, unsigned int &seed1, unsigned int &seed2) const
+    {
+        // get boxes from the node
+        // awulkiew - use of passed boxes instead of retrieving them second time
+        //std::vector<Box> boxes = n->get_boxes(m_translator);
+        if (boxes.size() == 0)
+        {
+            // TODO: mloskot - throw ggl exception
+            throw std::logic_error("Empty Node trying to Pick Seeds");
+        }
+
+        // only two dim for now
+        // unsigned int dimensions =
+        //   geometry::point_traits<Point>::coordinate_count;
+
+        // find the first two elements
+        typedef typename coordinate_type<Box>::type coordinate_type;
+        coordinate_type separation_x, separation_y;
+        unsigned int first_x, second_x;
+        unsigned int first_y, second_y;
+        find_normalized_separations<0u>(boxes, separation_x, first_x, second_x);
+        find_normalized_separations<1u>(boxes, separation_y, first_y, second_y);
+
+        if (separation_x > separation_y)
+        {
+            seed1 = first_x;
+            seed2 = second_x;
+        }
+        else
+        {
+            seed1 = first_y;
+            seed2 = second_y;
+        }
+    }
+
+    /**
+     * \brief Find distances between possible initial values for the
+     *        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
+    {
+        if (boxes.size() < 2)
+        {
+            throw std::logic_error("At least two boxes needed to split");
+        }
+
+        // find the lowest high
+        typename std::vector<Box>::const_iterator it = boxes.begin();
+        typedef typename coordinate_type<Box>::type coordinate_type;
+        coordinate_type lowest_high = geometry::get<max_corner, D>(*it);
+        unsigned int lowest_high_index = 0;
+        unsigned int index = 1;
+        ++it;
+        for(; it != boxes.end(); ++it)
+        {
+            if (geometry::get<max_corner, D>(*it) < lowest_high)
+            {
+                lowest_high = geometry::get<max_corner, D>(*it);
+                lowest_high_index = index;
+            }
+            index++;
+        }
+
+        // find the highest low
+        coordinate_type highest_low = 0;
+        unsigned int highest_low_index = 0;
+        if (lowest_high_index == 0)
+        {
+            highest_low = geometry::get<min_corner, D>(boxes[1]);
+            highest_low_index = 1;
+        }
+        else
+        {
+            highest_low = geometry::get<min_corner, D>(boxes[0]);
+            highest_low_index = 0;
+        }
+
+        index = 0;
+        for (typename std::vector<Box>::const_iterator it = boxes.begin();
+             it != boxes.end(); ++it, index++)
+        {
+            if (geometry::get<min_corner, D>(*it) >= highest_low && index != lowest_high_index)
+            {
+                highest_low = geometry::get<min_corner, D>(*it);
+                highest_low_index = index;
+            }
+        }
+
+        // find the lowest low
+        it = boxes.begin();
+        coordinate_type lowest_low = geometry::get<min_corner, D>(*it);
+        ++it;
+        for(; it != boxes.end(); ++it)
+        {
+            if (geometry::get<min_corner, D>(*it) < lowest_low)
+            {
+                lowest_low = geometry::get<min_corner, D>(*it);
+            }
+        }
+
+        // find the highest high
+        it = boxes.begin();
+        coordinate_type highest_high = geometry::get<max_corner, D>(*it);
+        ++it;
+        for(; it != boxes.end(); ++it)
+        {
+            if (geometry::get<max_corner, D>(*it) > highest_high)
+            {
+                highest_high = geometry::get<max_corner, D>(*it);
+            }
+        }
+
+        coordinate_type const width = highest_high - lowest_low;
+
+        separation = (highest_low - lowest_high) / width;
+        first = highest_low_index;
+        second = lowest_high_index;
+    }
+
+    /**
+     * \brief Choose one of the possible leaves to make an insertion
+     */
+    inline node_pointer choose_corresponding_leaf(Box const& e)
+    {
+        node_pointer node = m_root;
+
+        // if the tree is empty add an initial leaf
+        if (m_root->elements() == 0)
+        {
+            leaf_pointer new_leaf(new rtree_leaf(m_root));
+            m_root->add_leaf_node(Box(), new_leaf);
+
+            return new_leaf;
+        }
+
+        while (!node->is_leaf())
+        {
+            /// traverse node's map to see which node we should select
+            node = node->choose_node(e);
+        }
+        return node;
+    }
+
+    /**
+     * \brief Choose the exact leaf where an insertion should be done
+     */
+    // 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;
+        node_type nodes;
+        m_root->find_leaves(e, nodes);
+
+        // refine the result
+        for (typename node_type::const_iterator it = nodes.begin(); it != nodes.end(); ++it)
+        {
+            typedef typename rtree_leaf::values_map values_map;
+            values_map values = (*it)->get_values();
+
+            for (typename values_map::const_iterator itl = values.begin();
+                 itl != values.end(); ++itl)
+            {
+                // awulkiew - operator== changed to geometry::equals
+                // TODO - implement object specific equals() function
+                Box b;
+                detail::convert_to_box(m_translator(*itl), b);
+                if ( geometry::equals(b, e) )
+                {
+                    return *it;
+                }
+            }
+        }
+
+        // TODO: mloskot - ggl exception
+        throw std::logic_error("Leaf not found");
+    }
+};
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_HPP
+

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_internal_node.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_internal_node.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,522 @@
+// 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)
+
+// awulkiew 2011
+//   typedefs added
+//   nodes hierarchy changed, rtree_node changed to rtree_internal_node
+//   inconsistent names changed - get_leafs to get_values, update_parent to set_children_parent
+//   translator added
+//   exact match case removed
+//   gl_draw added - temporary
+
+#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 geometry::index::rtree_node<Value, Translator, Box> rtree_node;
+    typedef geometry::index::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_values() const
+    {
+        typedef typename rtree_leaf::values_map values_map;
+        values_map values;
+
+        for (typename node_map::const_iterator it = m_nodes.begin();
+             it != m_nodes.end(); ++it)
+        {
+            values_map this_values = it->second->get_values();
+
+            //TODO:
+            // awulkiew - reserve/resize, std::copy may be used here
+            for (typename values_map::const_iterator it_leaf = this_values.begin();
+                it_leaf != this_values.end(); ++it_leaf)
+            {
+                values.push_back(*it_leaf);
+            }
+        }
+
+        return values;
+    }
+
+    /**
+     * \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 Update the parent of all children nodes
+     */
+    virtual void set_children_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 Print Rtree subtree (mainly for debug)
+     */
+    // awulkiew - ostream parameter added
+    virtual void print(std::ostream &os, Translator const& tr) const
+    {
+        os << " --> Node --------" << std::endl;
+        os << "  Address: " << this << std::endl;
+        os << "  Level: " << this->get_level() << std::endl;
+        os << "  Size: " << m_nodes.size() << std::endl;
+        os << "  | ";
+        for(typename node_map::const_iterator it = m_nodes.begin(); it != m_nodes.end(); ++it)
+        {
+            if (this != it->second->get_parent().get())
+            {
+                os << "ERROR - " << this << " is not  " << it->second->get_parent().get() << " ";
+            }
+
+            os << "( " << geometry::get<min_corner, 0>(it->first) << " , "
+                << geometry::get<min_corner, 1>(it->first) << " ) x ";
+            os << "( " << geometry::get<max_corner, 0>(it->first) << " , "
+                << geometry::get<max_corner, 1>(it->first) << " )";
+            os << " | ";
+        }
+        os << std::endl;
+        os << " --< Node --------" << std::endl;
+
+        // print child nodes
+        os << " Children: " << std::endl;
+        for (typename node_map::const_iterator it = m_nodes.begin();
+            it != m_nodes.end(); ++it)
+        {
+            it->second->print(os, tr);
+        }
+    }
+
+#ifdef BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    /**
+     * \brief Draw Rtree subtree using OpenGL (mainly for debug)
+     */
+    virtual void gl_draw(Translator const& tr) const
+    {
+        // TODO: awulkiew - implement 3d version
+        if ( traits::dimension<traits::point_type<Box>::type>::value == 2 )
+        {
+            for (typename node_map::const_iterator it = m_nodes.begin();
+                it != m_nodes.end(); ++it)
+            {
+                size_t lvl = this->get_level();
+                if ( lvl == 0 )
+                    glColor3f(1.0f, 0.0f, 0.0f);
+                else if ( lvl == 1 )
+                    glColor3f(0.0f, 1.0f, 0.0f);
+                else if ( lvl == 2 )
+                    glColor3f(0.0f, 0.0f, 1.0f);
+                else if ( lvl == 3 )
+                    glColor3f(1.0f, 1.0f, 0.0f);
+                else if ( lvl == 4 )
+                    glColor3f(1.0f, 0.0f, 1.0f);
+                else if ( lvl == 5 )
+                    glColor3f(0.0f, 1.0f, 1.0f);
+                else
+                    glColor3f(0.5f, 0.5f, 0.5f);
+
+                glBegin(GL_LINE_LOOP);
+                glVertex2f(
+                    geometry::get<min_corner, 0>(it->first),
+                    geometry::get<min_corner, 1>(it->first));
+                glVertex2f(
+                    geometry::get<max_corner, 0>(it->first),
+                    geometry::get<min_corner, 1>(it->first));
+                glVertex2f(
+                    geometry::get<max_corner, 0>(it->first),
+                    geometry::get<max_corner, 1>(it->first));
+                glVertex2f(
+                    geometry::get<min_corner, 0>(it->first),
+                    geometry::get<max_corner, 1>(it->first));
+                glEnd();
+
+                it->second->gl_draw(tr);
+            }
+        }
+    }
+
+#endif // BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    typename std::vector<Box> get_level_boxes(size_t level, Translator const& tr) const
+    {
+        typename std::vector<Box> boxes;
+
+        if (level == this->get_level())
+        {
+            for (typename node_map::const_iterator it = m_nodes.begin();
+                it != m_nodes.end(); ++it)
+                boxes.push_back(it->first);
+        }
+        else
+        {
+            for (typename node_map::const_iterator it = m_nodes.begin();
+                it != m_nodes.end(); ++it)
+            {
+            	typename std::vector<Box> current_boxes = it->second->get_level_boxes(level, tr);
+
+                for (typename std::vector<Box>::const_iterator box_it = current_boxes.begin();
+                    box_it != current_boxes.end(); ++box_it)
+                    boxes.push_back(*box_it);
+            }
+        }
+
+        return boxes;
+    }
+
+    // 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));
+        // TODO: awulkiew - is this required?
+        // it updates the parent of all children nodes of a node which isn't changed
+        node->set_children_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->set_children_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 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

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_leaf.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_leaf.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,352 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - rtree leaf 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)
+
+// awulkiew 2011
+//   typedefs added
+//   nodes hierarchy changed
+//   inconsistent names changed - leafs to values, leaf_map to values_map, get_leafs to get_values, update_parent to set_children_parent
+//   exact match case removed
+//   gl_draw added - temporary
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_LEAF_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_LEAF_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/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
+{
+
+template <typename Value, typename Translator, typename Box>
+class rtree_leaf : public rtree_node<Value, Translator, Box>
+{
+public:
+
+    // awulkiew - typedef added
+    typedef geometry::index::rtree_node<Value, Translator, Box> rtree_node;
+
+    typedef boost::shared_ptr<rtree_node> node_pointer;
+
+    /// container type for the leaves
+    typedef std::vector<Value> values_map;
+
+    /**
+     * \brief Creates an empty leaf
+     */
+    inline rtree_leaf()
+    {
+    }
+
+    /**
+     * \brief Creates a new leaf, with 'parent' as parent
+     */
+    inline rtree_leaf(node_pointer const& parent)
+        : rtree_node(parent, 0)
+    {
+    }
+
+    // awulkiew - leaf methods
+
+    ///**
+    // * \brief Clear the node
+    // */
+    //// awulkiew - name changed from empty_nodes to clear_values
+    //void clear_values()
+    //{
+    //    m_values.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_values.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'. Otherwise return everything inside 'box'.
+     */
+    virtual void find(Box const& box, std::deque<Value>& result, Translator const& tr)
+    {
+        for (typename values_map::const_iterator it = m_values.begin();
+             it != m_values.end(); ++it)
+        {
+            // awulkiew - is_overlapping changed to geometry::intersects
+            if (geometry::intersects(tr(*it), box))
+            {
+                result.push_back(*it);
+            }
+        }
+    }
+
+    /**
+     * \brief Compute bounding box for this leaf
+     */
+    virtual Box compute_box(Translator const& tr) const
+    {
+        if (m_values.empty())
+        {
+            return Box ();
+        }
+
+        Box r;
+        geometry::assign_inverse(r);
+        for(typename values_map::const_iterator it = m_values.begin(); it != m_values.end(); ++it)
+        {
+            geometry::combine(r, tr(*it));
+        }
+        return r;
+    }
+
+    /**
+     * \brief Proyect leaves of this node.
+     */
+    virtual std::vector<Value> get_values() const
+    {
+        return m_values;
+    }
+
+    /**
+     * \brief Remove value with key 'box' in this leaf
+     */
+    // awulkiew - name changed to avoid ambiguity (Value may be of type Box)
+    virtual void remove_in(Box const& box, Translator const& tr)
+    {
+
+        for (typename values_map::iterator it = m_values.begin();
+             it != m_values.end(); ++it)
+        {
+            // TODO - awulkiew - implement object specific equals() function
+            Box b;
+            detail::convert_to_box(tr(*it), b);
+            if (geometry::equals(b, box))
+            {
+                m_values.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
+    {
+        std::vector<Box> result;
+        for (typename values_map::const_iterator it = m_values.begin();
+             it != m_values.end(); ++it)
+        {
+            // TODO: awulkiew - implement object specific behaviour - get_bounding_objects(get boxes or points)
+            Box box;
+            detail::convert_to_box(tr(*it), box);
+
+            result.push_back(box);
+        }
+
+        return result;
+    }
+
+    /**
+     * \brief Update the parent of all children nodes
+     */
+    virtual void set_children_parent(node_pointer const& node)
+    {
+        // TODO: awulkiew - should this method exist in leaf?
+        // Do nothing
+    }
+
+    /**
+    * \brief Print leaf (mainly for debug)
+    */
+    // awulkiew - ostream parameter added
+    virtual void print(std::ostream &os, Translator const& tr) const
+    {
+        os << "\t" << " --> Leaf --------" << std::endl;
+        os << "\t" << "  Size: " << m_values.size() << std::endl;
+        for (typename values_map::const_iterator it = m_values.begin();
+            it != m_values.end(); ++it)
+        {
+            // TODO: awulkiew - implement object specific behaviour - display boxes or points
+            Box box;
+            detail::convert_to_box(tr(*it), box);
+
+            os << "\t" << "  | ";
+            os << "( " << geometry::get<min_corner, 0>
+                (box) << " , " << geometry::get<min_corner, 1>
+                (box) << " ) x ";
+            os << "( " << geometry::get<max_corner, 0>
+                (box) << " , " << geometry::get<max_corner, 1>
+                (box) << " )";
+            // awulkiew - commented
+            //std::cerr << " -> ";
+            //std::cerr << it->second;
+            os << " | " << std::endl;;
+        }
+        os << "\t" << " --< Leaf --------" << std::endl;
+    }
+
+#ifdef BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    /**
+     * \brief Draw leaf using OpenGL (mainly for debug)
+     */
+    virtual void gl_draw(Translator const& tr) const
+    {
+        // TODO: awulkiew - implement 3d version
+        if ( traits::dimension<traits::point_type<Box>::type>::value == 2 )
+        {
+            for (typename values_map::const_iterator it = m_values.begin();
+                it != m_values.end(); ++it)
+            {
+                glColor3f(1.0f, 1.0f, 1.0f);
+
+                Box box;
+                detail::convert_to_box(tr(*it), box);
+
+                glBegin(GL_LINE_LOOP);
+                glVertex2f(
+                    geometry::get<min_corner, 0>(box),
+                    geometry::get<min_corner, 1>(box));
+                glVertex2f(
+                    geometry::get<max_corner, 0>(box),
+                    geometry::get<min_corner, 1>(box));
+                glVertex2f(
+                    geometry::get<max_corner, 0>(box),
+                    geometry::get<max_corner, 1>(box));
+                glVertex2f(
+                    geometry::get<min_corner, 0>(box),
+                    geometry::get<max_corner, 1>(box));
+                glEnd();
+            }
+        }
+    }
+
+#endif // BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    /**
+     * \brief Get boxes of objects if level is equal to leaf's level
+     */
+    std::vector<Box> get_level_boxes(size_t level, Translator const& tr) const
+    {
+        std::vector<Box> boxes;
+
+        /*if ( level == this->get_level())
+        {
+            for (typename values_map::const_iterator it = m_values.begin();
+                it != m_values.end(); ++it)
+            {            
+                Box box;
+                detail::convert_to_box(tr(*it), box);
+                boxes.push_back(box);
+            }
+        }*/
+
+        return boxes;
+    }
+
+    // awulkiew - leaf only virtual methods
+
+    /**
+     * \brief Insert a new element, with key 'box' and value 'v'
+     */
+    virtual void insert(Value const& v)
+    {
+        m_values.push_back(v);
+    }
+
+    /**
+     * \brief Add a new leaf to this node
+     */
+    virtual void add_value(Value const& v)
+    {
+        m_values.push_back(v);
+    }
+
+    /**
+     * \brief Proyect value in position 'index' in the nodes container
+     */
+    virtual Value get_value(unsigned int index) const
+    {
+        return m_values[index];
+    }
+
+    /**
+     * \brief Remove value in this leaf
+     */
+    virtual void remove(Value const& v, Translator const& tr)
+    {
+        for (typename values_map::iterator it = m_values.begin();
+             it != m_values.end(); ++it)
+        {
+            // awulkiew - use of translator
+            if ( tr.equals(*it, v) )
+            {
+                m_values.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_values[index]), box);
+    //    return box;
+    //}
+
+private:
+
+    /// leaves of this node
+    values_map m_values;
+};
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_LEAF_HPP
+

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_node.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/rtree/rtree_node.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,344 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - rtree node, base class to leafs and internal 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)
+
+// awulkiew 2011
+//   nodes hierarchy changed, rtree_node changed to rtree_internal_node
+//   inconsistent names changed - get_leafs to get_values, update_parent to set_children_parent
+//   translator added
+//   exact match case removed
+//   gl_draw added - temporary
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_NODE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_NODE_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+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:
+
+    typedef boost::shared_ptr<rtree_node<Value, Translator, Box> > node_pointer;
+    typedef boost::shared_ptr<rtree_leaf<Value, Translator, Box> > leaf_pointer;
+
+    typedef std::vector<std::pair<Box, node_pointer > > node_map;
+
+    /**
+     * \brief destructor (virtual because we have virtual functions)
+     */
+    virtual ~rtree_node()
+    {
+    }
+
+    // awulkiew - node methods
+
+    /**
+     * \brief Projector for parent
+     */
+    inline node_pointer get_parent() const
+    {
+        return m_parent;
+    }
+
+    /**
+     * \brief Set parent
+     */
+    void set_parent(node_pointer const& node)
+    {
+        m_parent = node;
+    }
+
+    /**
+     * \brief Level projector
+     */
+    size_t get_level() const
+    {
+        return m_level;
+    }
+
+    // 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 Number of elements in the subtree
+     */
+    virtual size_t elements() const
+    {
+        // 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'.
+     */
+    virtual void find(Box const& box, std::deque<Value>& result, Translator const& tr)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+    }
+
+    /**
+    * \brief Compute bounding box for this node
+    */
+    virtual Box compute_box(Translator const&) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+
+        return Box();
+    }
+
+    /**
+    * \brief Get leaves for a node
+    */
+    virtual std::vector<Value> get_values() const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+
+        return std::vector<Value>();
+    }
+
+    /**
+     * \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&)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+    }
+
+    /**
+     * \brief Get the envelopes of a node
+     */
+    virtual std::vector<Box> get_boxes(Translator const&) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+
+        return std::vector<Box>();
+    }
+
+    /**
+     * \brief Update the parent of all children nodes
+     */
+    virtual void set_children_parent(node_pointer const& node)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+    }
+
+    /**
+     * \brief Print Rtree subtree (mainly for debug)
+     */
+    // awulkiew - ostream parameter added
+    virtual void print(std::ostream &, Translator const&) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+    }
+
+#ifdef BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    /**
+     * \brief Draw Rtree subtree using OpenGL (mainly for debug)
+     */
+    virtual void gl_draw(Translator const&) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+    }
+
+#endif // BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+    std::vector<Box> get_level_boxes(size_t, Translator const&) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here");
+    }
+
+    // awulkiew - leaf only virtual methods
+
+    /**
+     * \brief Insert a value (not allowed for a node, only on leaves)
+     */
+    virtual void insert(Value const&)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("Insert in node!");
+    }
+
+    /**
+     * \brief add a value (not allowed in nodes, only on leaves)
+     */
+    virtual void add_value(Value const&)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("Can't add value to non-leaf node.");
+    }
+
+    /**
+     * \brief Value projector for leaf_node (not allowed for non-leaf nodes)
+     */
+    virtual Value get_value(unsigned int) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("No values in a non-leaf node.");
+    }
+
+    /**
+     * \brief Remove value in this leaf
+     */
+    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.");
+    }
+
+    // awulkiew - internal node only virtual methods
+
+    /**
+     * \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.");
+    }
+
+    virtual node_pointer first_element() const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+        return node_pointer();
+    }
+
+    /**
+     * \brief Proyector for the 'i' node
+     */
+    virtual node_pointer get_node(size_t index)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+        return node_pointer();
+    }
+
+    /**
+     * \brief Return in 'result' all the leaves inside 'box'
+     */
+    virtual void find_leaves(Box const& box, typename std::vector<node_pointer>& result) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+    }
+
+    /**
+     * \brief Recompute the bounding box
+     */
+    virtual void adjust_box(node_pointer const& node, Translator const& tr)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+    }
+
+    /**
+     * \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)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+    }
+
+    /**
+     * \brief Add a child leaf to this node
+     */
+    virtual void add_leaf_node(Box const& box, leaf_pointer const& leaf)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+    }
+
+    /**
+     * \brief Choose a node suitable for adding 'box'
+     */
+    virtual node_pointer choose_node(Box const& box)
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+    }
+
+    /**
+     * \brief Box projector for node pointed by 'leaf'
+     */
+    virtual Box get_box(node_pointer const& leaf) const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+        return Box();
+    }
+
+    /**
+     * \brief Children projector
+     */
+    virtual node_map get_nodes() const
+    {
+        // TODO: mloskot - define & use GGL exception
+        throw std::logic_error("shouldn't be here.");
+        return node_map();
+    }
+
+protected:
+
+    /**
+     * \brief Creates a default node
+     */
+    rtree_node()
+    {
+    }
+
+    /**
+     * \brief Creates a node with 'parent' as parent and 'level' as its level
+     */
+    rtree_node(node_pointer const& parent, size_t const& level)
+        : m_parent(parent), m_level(level)
+    {
+    }
+
+private:
+
+    /// parent node
+    node_pointer m_parent;
+
+    /// level of this node
+    // TODO: mloskot - Why not std::size_t or node_map::size_type, same with member functions?
+    // awulkiew - size_t used instead of unsigned int
+    size_t m_level;
+};
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_NODE_HPP

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/def.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/def.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,103 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - default value to bounding object translation
+//
+// 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_TRANSLATOR_DEF_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_DEF_HPP
+
+#include <boost/geometry/extensions/index/translator/helpers.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace translator {
+
+namespace dispatch {
+
+// Distinguish between def<Geometry>, def<Iterator> and def<SmartPtr>
+
+// Geometry
+template <typename Value, bool IsIterator, bool IsSmartPtr>
+struct def
+{
+    typedef typename detail::extract_bounding_geometry<Value>::type bounding_geometry_type;
+
+    bounding_geometry_type const& operator()(Value const& v) const
+    {
+        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
+template <typename Value, bool IsSmartPtr>
+struct def<Value, true, IsSmartPtr>
+{
+    typedef typename detail::extract_bounding_geometry<typename Value::value_type>::type bounding_geometry_type;
+
+    bounding_geometry_type const& operator()(Value const& v) const
+    {
+        return detail::extract_bounding_geometry<typename Value::value_type>::get(*v);
+    }
+
+    bool equals(Value const& v1, Value const& v2) const
+    {
+        return v1 == v2;
+    }
+};
+
+// SmartPtr
+template <typename Value>
+struct def<Value, false, true>
+{
+    typedef typename detail::extract_bounding_geometry<typename Value::element_type>::type bounding_geometry_type;
+
+    bounding_geometry_type const& operator()(Value const& v) const
+    {
+        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
+
+template <typename Value>
+struct def
+    : public dispatch::def
+        <
+            Value,
+            detail::is_iterator<Value>::value,
+            detail::is_smart_ptr<Value>::value
+        >
+{
+};
+
+template <typename Value>
+struct def<Value*>
+{
+    typedef typename detail::extract_bounding_geometry<Value>::type bounding_geometry_type;
+
+    bounding_geometry_type const& operator()(const Value *v) const
+    {
+        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
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_DEF_HPP

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/helpers.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/helpers.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,217 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - translators helper functions
+//
+// 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_TRANSLATOR_HELPERS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_HELPERS_HPP
+
+#include <utility>
+
+#include <boost/static_assert.hpp>
+
+#include <boost/mpl/has_xxx.hpp>
+#include <boost/mpl/and.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace translator {
+
+namespace dispatch {
+
+// Distinguish between bounding geometries and other geometries
+
+template <typename Geometry, typename GeometryTag>
+struct bounding_geometry
+{
+    typedef void type;
+};
+
+template <typename Point>
+struct bounding_geometry<Point, geometry::point_tag>
+{
+    typedef Point type;
+};
+
+template <typename Box>
+struct bounding_geometry<Box, geometry::box_tag>
+{
+    typedef Box type;
+};
+
+// Extract object from std::pair by non-void tag
+
+template <typename Pair, typename FirstTag, typename SecondTag>
+struct choose_pair_element
+{
+    typedef typename Pair::first_type type;
+    static type const& get(Pair const& p) { return p.first; }
+};
+
+template <typename Pair, typename FirstTag>
+struct choose_pair_element<Pair, FirstTag, void>
+{
+    typedef typename Pair::first_type type;
+    static type const& get(Pair const& p) { return p.first; }
+};
+
+template <typename Pair, typename Second>
+struct choose_pair_element<Pair, void, Second>
+{
+    typedef typename Pair::second_type type;
+    static type const& get(Pair const& p) { return p.second; }
+};
+
+template <typename Pair>
+struct choose_pair_element<Pair, void, void>
+{
+    typedef void type;
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename T>
+struct bounding_object_not_found_error
+{
+    static const bool value = false;
+};
+template <>
+struct bounding_object_not_found_error<void>
+{
+    static const bool value = true;
+};
+
+// Extract bounding geometry object
+
+template <typename Value>
+struct extract_bounding_geometry
+{
+    typedef typename dispatch::bounding_geometry<
+        Value,
+        typename geometry::traits::tag<Value>::type
+    >::type type;
+
+    BOOST_STATIC_ASSERT(!bounding_object_not_found_error<type>::value);
+
+    static type const& get(Value const& v) { return v; }
+};
+
+template <typename First, typename Second>
+struct extract_bounding_geometry< std::pair<First, Second> >
+{
+    typedef typename dispatch::choose_pair_element<
+        std::pair<First, Second>,
+        typename dispatch::bounding_geometry<
+            First,
+            typename geometry::traits::tag<First>::type
+        >::type,
+        typename dispatch::bounding_geometry<
+            Second,
+            typename geometry::traits::tag<Second>::type
+        >::type
+    > cp;
+
+    typedef typename cp::type type;
+
+    BOOST_STATIC_ASSERT(!bounding_object_not_found_error<type>::value);
+
+    static type const& get(std::pair<First, Second> const& v)
+    {
+        return cp::get(v);
+    }
+};
+
+// Recognize iterators and smart pointers
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(iterator_category)
+BOOST_MPL_HAS_XXX_TRAIT_DEF(value_type)
+BOOST_MPL_HAS_XXX_TRAIT_DEF(difference_type)
+BOOST_MPL_HAS_XXX_TRAIT_DEF(pointer)
+BOOST_MPL_HAS_XXX_TRAIT_DEF(reference)
+
+BOOST_MPL_HAS_XXX_TRAIT_DEF(element_type)
+
+// TODO
+// use has_operator_xxx in the future
+
+template <typename T>
+struct is_iterator
+{
+    static const bool value = boost::mpl::and_
+        <
+            has_iterator_category<T>,
+            has_value_type<T>,
+            has_difference_type<T>,
+            has_pointer<T>,
+            has_reference<T>
+        >::value;
+};
+
+template <typename T>
+struct is_smart_ptr
+{
+    static const bool value = has_element_type<T>::value;
+};
+
+} // 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,
+				typename traits::tag<First>::type
+			>::apply(p1.first, p2.first)
+			&&
+            dispatch::equals<
+				Second,
+				typename traits::tag<Second>::type
+			>::apply(p1.second, p2.second);
+    }
+};
+
+} // namespace detail
+
+}}}} // namespace boost::geometry::index::translator
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_HELPERS_HPP

Added: sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/index.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/boost/geometry/extensions/index/translator/index.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,43 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - container index value to bounding object translation
+//
+// 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_TRANSLATOR_INDEX_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_INDEX_HPP
+
+#include <boost/geometry/extensions/index/translator/helpers.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace translator {
+
+template <typename Container>
+class index
+{
+public:
+    typedef typename detail::extract_bounding_geometry
+        <typename Container::value_type>::type bounding_geometry_type;
+
+    explicit index(Container const& c) : m_c(c) {}
+
+    bounding_geometry_type const& operator()(size_t i) const
+    {
+        return detail::extract_bounding_geometry
+            <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;
+};
+
+}}}} // namespace boost::geometry::index::translator
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_INDEX_HPP

Added: sandbox-branches/geometry/index_080_vis/tests/additional_glut_vis.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/tests/additional_glut_vis.cpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,77 @@
+#include <boost/geometry/geometry.hpp>
+
+#include <gl/glut.h>
+#define BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
+
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+#include <boost/geometry/extensions/index/translator/index.hpp>
+
+#include <iostream>
+
+void render_scene(void)
+{
+    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(5, 0);
+
+    for ( size_t i = 0 ; i < 50 ; ++i )
+    {
+        float x = ( rand() % 10000 ) / 1000.0f;
+        float y = ( rand() % 10000 ) / 1000.0f;
+        float w = ( rand() % 10000 ) / 100000.0f;
+        float h = ( rand() % 10000 ) / 100000.0f;
+
+        t.insert(B(P(x - w, y - h),P(x + w, y + h)));
+    }
+
+    t.gl_draw();
+}
+
+void resize(int w, int h)
+{
+    if ( h == 0 )
+        h = 1;
+
+    float ratio = float(w) / h;
+
+    glMatrixMode(GL_PROJECTION);
+    glLoadIdentity();
+
+    glViewport(0, 0, w, h);
+
+    gluPerspective(45, ratio, 1, 1000);
+    glMatrixMode(GL_MODELVIEW);
+    glLoadIdentity();
+    gluLookAt(
+        5.0f, 5.0f, 15.0f, 
+        5.0f, 5.0f, -1.0f,
+        0.0f, 1.0f, 0.0f);
+}
+
+void mouse(int button, int state, int x, int y)
+{
+    if ( state == GLUT_DOWN )
+    {
+        glutPostRedisplay();
+    }
+}
+
+int main(int argc, char **argv)
+{
+    glutInit(&argc, argv);
+    glutInitDisplayMode(GLUT_DEPTH | GLUT_SINGLE | GLUT_RGBA);
+    glutInitWindowPosition(100,100);
+    glutInitWindowSize(320,320);
+    glutCreateWindow("Mouse click to generate new tree");
+
+    glutDisplayFunc(render_scene);
+    glutReshapeFunc(resize);
+    glutMouseFunc(mouse);
+
+    std::cout << "Mouse click to generate new tree";
+
+    glutMainLoop();
+
+    return 0;
+}

Added: sandbox-branches/geometry/index_080_vis/tests/additional_sizes_and_times.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/tests/additional_sizes_and_times.cpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,70 @@
+#include <boost/geometry/geometry.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
+#include <iostream>
+
+#include <boost/timer.hpp>
+#include <boost/foreach.hpp>
+
+int main()
+{
+    {
+        typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+        typedef boost::geometry::model::box<P> B;
+
+        boost::geometry::index::rtree<B>::rtree_leaf l;
+        boost::geometry::index::rtree<B>::rtree_internal_node n;
+
+        std::cout << "shared ptr size: " << sizeof(boost::shared_ptr<int>) << '\n';
+        std::cout << "vector size: " << sizeof(std::vector<int>) << '\n';
+        std::cout << "internal node size: " << sizeof(n) << '\n';
+        std::cout << "leaf size: " << sizeof(l) << '\n';        
+    }
+
+    {
+        typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+        typedef boost::geometry::model::box<P> B;
+
+        // randomize boxes
+        const size_t n = 10000;
+        std::vector<B> v(n);
+        for ( size_t i = 0 ; i < n ; ++i )
+        {
+            float x = ( rand() % 10000 ) / 1000.0f;
+            float y = ( rand() % 10000 ) / 1000.0f;
+            float w = ( rand() % 10000 ) / 100000.0f;
+            float h = ( rand() % 10000 ) / 100000.0f;
+            v[i] = B(P(x - w, y - h),P(x + w, y + h));
+        }
+
+        boost::geometry::index::rtree<B> t(10, 0);
+
+        std::cout << "inserting time test...\n";
+
+        boost::timer tim;
+
+        BOOST_FOREACH(B &b, v)
+        {
+            t.insert(b);
+        }
+
+        std::cout << "time: " << tim.elapsed() << "s\n";
+        std::cout << "removing time test...\n";
+
+        tim.restart();
+
+        BOOST_FOREACH(B &b, v)
+        {
+            t.remove(b);
+        }
+
+        std::cout << "time: " << tim.elapsed() << "s\n";
+    }
+
+#ifdef _MSC_VER
+    std::cin.get();
+#endif
+
+    return 0;
+}

Added: sandbox-branches/geometry/index_080_vis/tests/main.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/tests/main.cpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,18 @@
+#include <tests/translators.hpp>
+#include <tests/rtree_native.hpp>
+#include <tests/rtree_filters.hpp>
+//#include <tests/rtree_iterator.hpp>
+
+int main()
+{
+    tests_translators_hpp();
+    tests_rtree_native_hpp();
+    tests_rtree_filters_hpp();
+    //tests_rtree_iterator_hpp();
+
+#ifdef _MSC_VER
+    std::cin.get();
+#endif
+
+    return 0;
+}

Added: sandbox-branches/geometry/index_080_vis/tests/rtree_filters.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/tests/rtree_filters.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,56 @@
+#ifndef TESTS_RTREE_FILTERS_HPP
+#define TESTS_RTREE_FILTERS_HPP
+
+#include <boost/geometry/geometry.hpp>
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
+#include <boost/geometry/extensions/index/rtree/filters.hpp>
+#include <boost/geometry/extensions/index/filters/nearest_filter.hpp>
+
+#include <iostream>
+
+#include <boost/range/algorithm.hpp>
+#include <boost/foreach.hpp>
+
+template <typename R>
+void tests_rtree_filters_hpp_print_range(R const& r)
+{
+    BOOST_FOREACH(typename boost::iterator_value<typename R::const_iterator>::type const& b, r)
+    {
+        float min_x = b.min_corner().template get<0>();
+        float min_y = b.min_corner().template get<1>();
+        float max_x = b.max_corner().template get<0>();
+        float max_y = b.max_corner().template get<1>();
+        std::cout << "(" << min_x << ", " << min_y << ")";
+        std::cout << 'x';
+        std::cout << "(" << max_x << ", " << max_y << ")";
+        std::cout << '\n';
+    }
+    std::cout << std::endl;
+}
+
+void tests_rtree_filters_hpp()
+{
+	std::cout << "tests/rtree_filters.hpp\n";
+
+    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)));
+        std::cerr << t;
+
+        std::deque<B> res = t.find(B(P(2.5f, 2.5f), P(4.5f, 4.5f)));
+        tests_rtree_filters_hpp_print_range(res);
+
+        namespace f = boost::geometry::index::filters;
+        tests_rtree_filters_hpp_print_range(t | f::spatially_filtered(B(P(2.5f, 2.5f), P(4.5f, 4.5f))));
+        tests_rtree_filters_hpp_print_range(t | f::nearest_filtered(P(3.5f, 3.5f), 1.0f));
+    }
+}
+
+#endif // TESTS_RTREE_FILTERS_HPP

Added: sandbox-branches/geometry/index_080_vis/tests/rtree_native.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/tests/rtree_native.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,198 @@
+#ifndef TESTS_RTREE_NATIVE_HPP
+#define TESTS_RTREE_NATIVE_HPP
+
+#include <boost/geometry/geometry.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+#include <boost/geometry/extensions/index/translator/index.hpp>
+
+#include <iostream>
+
+#include <boost/range/algorithm.hpp>
+#include <boost/foreach.hpp>
+
+#include <map>
+
+void tests_rtree_native_hpp()
+{
+	std::cout << "tests/rtree_native.hpp\n";
+	
+    // 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)));
+        std::cerr << t;
+
+        // error
+        t.remove_in(B(P(-1, -1), P(2, 2)));
+        // ok
+        t.remove_in(B(P(0, 0), P(1, 1)));
+        std::cerr << t;
+
+        t.remove(B(P(6, 6), P(7, 7)));
+        std::cerr << t;
+    }
+
+    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));
+        std::cerr << t;
+
+        // error
+        t.remove_in(B(P(-1, -1), P(1, 1)));
+        // ok
+        t.remove_in(B(P(0, 0), P(0, 0)));
+        std::cerr << t;
+
+        t.remove(P(6, 6));
+        std::cerr << t;
+    }
+
+    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));
+        std::cerr << t;
+
+        // error
+        t.remove_in(B(P(0, 0), P(2, 1)));
+        // ok
+        t.remove_in(B(P(0, 0), P(1, 1)));
+        std::cerr << t;
+
+        t.remove(V(B(P(6, 6), P(7, 7)), 3));
+        std::cerr << t;
+    }
+
+    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);
+        std::cerr << t;
+
+        // error
+        t.remove_in(B(P(0, 0), P(2, 1)));
+        // ok
+        t.remove_in(B(P(0, 0), P(1, 1)));
+        std::cerr << t;
+
+        t.remove(v4);
+        std::cerr << t;
+    }
+
+    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);
+        std::cerr << t;
+
+        // error
+        t.remove_in(B(P(0, 0), P(2, 1)));
+        // ok
+        t.remove_in(B(P(0, 0), P(1, 1)));
+        std::cerr << t;
+
+        t.remove(m.find(3));
+        std::cerr << t;
+    }
+
+    std::cout << "-------------------------------------------------\n";
+    std::cout << "-------------------------------------------------\n";
+
+    // size_t
+    {
+        typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+        typedef boost::geometry::model::box<P> B;
+
+        typedef size_t V;
+        typedef boost::geometry::index::translator::index<std::vector<B> > T;
+
+        std::vector<B> v;
+        v.push_back(B(P(0, 0), P(1, 1)));
+        v.push_back(B(P(2, 2), P(3, 3)));
+        v.push_back(B(P(4, 4), P(5, 5)));
+        v.push_back(B(P(6, 6), P(7, 7)));
+
+        boost::geometry::index::rtree<V, T> t(3, 0, T(v));
+
+        t.insert(0);
+        t.insert(1);
+        t.insert(2);
+        t.insert(3);
+        std::cerr << t;
+
+        // error
+        t.remove_in(B(P(0, 0), P(2, 1)));
+        // ok
+        t.remove_in(B(P(0, 0), P(1, 1)));
+        std::cerr << t;
+
+        t.remove(3);
+        std::cerr << t;
+    }
+
+    // ERROR!
+    // remove_in expects previously inserted box - it should remove all objects inside some bigger box
+}
+
+#endif // TESTS_RTREE_NATIVE_HPP

Added: sandbox-branches/geometry/index_080_vis/tests/translators.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_vis/tests/translators.hpp	2011-03-08 16:13:05 EST (Tue, 08 Mar 2011)
@@ -0,0 +1,72 @@
+#ifndef TESTS_TRANSLATORS_HPP
+#define TESTS_TRANSLATORS_HPP
+
+#include <boost/geometry/geometry.hpp>
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
+#include <boost/geometry/extensions/index/translator/def.hpp>
+#include <boost/geometry/extensions/index/translator/index.hpp>
+
+#include <vector>
+#include <map>
+
+#include <boost/shared_ptr.hpp>
+#include <boost/scoped_ptr.hpp>
+
+void tests_translators_hpp()
+{
+	std::cout << "tests/translators.hpp\n";
+
+    typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+    typedef boost::geometry::model::box<P> B;
+    typedef boost::geometry::index::rtree<B> I;
+
+    using namespace boost::geometry;
+
+    index::translator::def<P> p;
+    index::translator::def<P*> pp;
+    index::translator::def<std::pair<int, P>*> pip;
+    index::translator::def< boost::shared_ptr<P> > sp;
+    index::translator::def< std::vector<P>::iterator > ip;
+    index::translator::def< std::map<int, P>::iterator > mip;
+    index::translator::def< std::pair<P, size_t> > ppi;
+    index::translator::def< boost::shared_ptr< std::pair<int, P> > > spip;
+    index::translator::def< boost::shared_ptr< std::pair<P, int> > > sppi;
+    index::translator::def< boost::scoped_ptr< std::pair<P, int> > > scppi;
+    index::translator::def< boost::scoped_ptr< std::pair<int, P> > > scpip;
+
+    P tmp_p;
+    boost::shared_ptr<P> tmp_sp(new P());
+    std::vector<P> tmp_v(1);
+    std::map<int, P> tmp_m;
+    tmp_m.insert(std::pair<int, P>(0, P()));
+    std::pair<int, P> tmp_pip;
+    boost::shared_ptr< std::pair<int, P> > tmp_spip(new std::pair<int, P>(0, P()));
+    boost::shared_ptr< std::pair<P, int> > tmp_sppi(new std::pair<P, int>(P(), 0));
+    boost::scoped_ptr< std::pair<int, P> > tmp_scpip(new std::pair<int, P>(0, P()));
+    boost::scoped_ptr< std::pair<P, int> > tmp_scppi(new std::pair<P, int>(P(), 0));
+
+    tmp_p = p(P());
+    tmp_p = pp(&tmp_p);
+    tmp_p = pip(&tmp_pip);
+    tmp_p = sp(tmp_sp);
+    tmp_p = ip(tmp_v.begin());
+    tmp_p = mip(tmp_m.begin());
+    tmp_p = ppi(std::pair<P, size_t>(P(), 0));
+    tmp_p = spip(tmp_spip);
+    tmp_p = sppi(tmp_sppi);
+    tmp_p = scpip(tmp_scpip);
+    tmp_p = scppi(tmp_scppi);
+
+    //index::translator::def<int> d;					// error
+    //index::translator::def< model::segment<P> > d;	// error
+
+    index::translator::def< std::pair<model::polygon<P>, B> > d;
+    index::translator::def< std::pair<B, model::polygon<P> > > dd;
+
+    B tmp_b;
+    tmp_b = d( std::pair<model::polygon<P>, B>() );
+    tmp_b = dd( std::pair<B, model::polygon<P> >() );
+}
+
+#endif // TESTS_TRANSLATORS_HPP