[Boost-commit] svn:boost r70531 - in sandbox-branches/geometry/index_080_new: . boost boost/geometry boost/geometry/extensions boost/geometry/extensions/index boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/filters boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors boost/geometry/extensions/index/translator tests

Subject: [Boost-commit] svn:boost r70531 - in sandbox-branches/geometry/index_080_new: . boost boost/geometry boost/geometry/extensions boost/geometry/extensions/index boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/filters boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors boost/geometry/extensions/index/translator tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-03-24 19:52:31

Author: awulkiew
Date: 2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
New Revision: 70531
URL: http://svn.boost.org/trac/boost/changeset/70531

Log:
R*tree implementation based on boost::variant
Added:
   sandbox-branches/geometry/index_080_new/
   sandbox-branches/geometry/index_080_new/boost/
   sandbox-branches/geometry/index_080_new/boost/geometry/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/default_parameter.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/filters/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/filters/nearest_filter.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/filters/spacial_filter.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/indexable.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/tags.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_delete.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_find.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_insert.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_remove.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/helpers.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/index.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/
   sandbox-branches/geometry/index_080_new/tests/TODO.txt   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/main.cpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/rtree_filters.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp   (contents, props changed)
   sandbox-branches/geometry/index_080_new/tests/translators.hpp   (contents, props changed)

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,58 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - n-dimensional box's area/volume
+//
+// 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_ALGORITHMS_AREA_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_AREA_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+template <typename Box>
+struct area_result
+{
+    typedef typename select_most_precise<
+        typename coordinate_type<Box>::type,
+        long double
+    >::type type;
+};
+
+namespace detail {
+
+template <typename Box, size_t CurrentDimension>
+struct area_for_each_dimension
+{
+    BOOST_STATIC_ASSERT(0 < CurrentDimension);
+    BOOST_STATIC_ASSERT(CurrentDimension <= traits::dimension<Box>::value);
+
+    static inline typename area_result<Box>::type apply(Box const& b)
+    {
+        return area_for_each_dimension<Box, CurrentDimension - 1>::apply(b) *
+            ( geometry::get<max_corner, CurrentDimension - 1>(b) - geometry::get<min_corner, CurrentDimension - 1>(b) );
+    }
+};
+
+template <typename Box>
+struct area_for_each_dimension<Box, 1>
+{
+    static inline typename area_result<Box>::type apply(Box const& b)
+    {
+        return geometry::get<max_corner, 0>(b) - geometry::get<min_corner, 0>(b);
+    }
+};
+
+} // namespace detail
+
+template <typename Box>
+typename area_result<Box>::type area(Box const& b)
+{
+    return detail::area_for_each_dimension<Box, traits::dimension<Box>::value>::apply(b);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_AREA_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,102 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - n-dimensional box's margin value, 2d perimeter, 3d surface, etc...
+//
+// 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_ALGORITHMS_MARGIN_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MARGIN_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+template <typename Box>
+struct margin_result
+{
+    typedef typename select_most_precise<
+        typename coordinate_type<Box>::type,
+        long double
+    >::type type;
+};
+
+namespace detail {
+
+template <typename Box, size_t CurrentDimension, size_t EdgeDimension>
+struct margin_for_each_edge
+{
+    BOOST_STATIC_ASSERT(0 < CurrentDimension);
+    BOOST_STATIC_ASSERT(0 < EdgeDimension);
+
+    static inline typename margin_result<Box>::type apply(Box const& b)
+    {
+        return margin_for_each_edge<Box, CurrentDimension, EdgeDimension - 1>::apply(b) *
+            ( geometry::get<max_corner, EdgeDimension - 1>(b) - geometry::get<min_corner, EdgeDimension - 1>(b) );
+    }
+};
+
+template <typename Box, size_t CurrentDimension>
+struct margin_for_each_edge<Box, CurrentDimension, CurrentDimension>
+{
+    BOOST_STATIC_ASSERT(0 < CurrentDimension);
+
+    static inline typename margin_result<Box>::type apply(Box const& b)
+    {
+        return margin_for_each_edge<Box, CurrentDimension, CurrentDimension - 1>::apply(b);
+    }
+};
+
+template <typename Box, size_t CurrentDimension>
+struct margin_for_each_edge<Box, CurrentDimension, 1>
+{
+    BOOST_STATIC_ASSERT(0 < CurrentDimension);
+
+    static inline typename margin_result<Box>::type apply(Box const& b)
+    {
+        return geometry::get<max_corner, 0>(b) - geometry::get<min_corner, 0>(b);
+    }
+};
+
+template <typename Box>
+struct margin_for_each_edge<Box, 1, 1>
+{
+    static inline typename margin_result<Box>::type apply(Box const& b)
+    {
+        return 1;
+    }
+};
+
+template <typename Box, size_t CurrentDimension>
+struct margin_for_each_dimension
+{
+    BOOST_STATIC_ASSERT(0 < CurrentDimension);
+    BOOST_STATIC_ASSERT(CurrentDimension <= traits::dimension<Box>::value);
+
+    static inline typename margin_result<Box>::type apply(Box const& b)
+    {
+        return margin_for_each_dimension<Box, CurrentDimension - 1>::apply(b) +
+            2 * margin_for_each_edge<Box, CurrentDimension, traits::dimension<Box>::value>::apply(b);
+    }
+};
+
+template <typename Box>
+struct margin_for_each_dimension<Box, 1>
+{
+    static inline typename margin_result<Box>::type apply(Box const& b)
+    {
+        return 2 * margin_for_each_edge<Box, 1, traits::dimension<Box>::value>::apply(b);
+    }
+};
+
+} // namespace detail
+
+template <typename Box>
+typename margin_result<Box>::type margin(Box const& b)
+{
+    return detail::margin_for_each_dimension<Box, traits::dimension<Box>::value>::apply(b);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_MARGIN_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,34 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - n-dimensional area/volume of boxes intersecion/overlap
+//
+// 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_ALGORITHMS_OVERLAP_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_OVERLAP_HPP
+
+#include <boost/geometry/algorithms/intersection.hpp>
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+template <typename Box>
+struct overlap_result
+{
+    typedef typename area_result<Box>::type type;
+};
+
+template <typename Box>
+typename overlap_result<Box>::type overlap(Box const& b1, Box const& b2)
+{
+    Box inters;
+    geometry::intersection(b1, b2, inters);
+    return index::area(inters);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_OVERLAP_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,32 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - boxes union/intersection area/volume
+//
+// Copyright 2008 Federico J. Fernandez.
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_UNION_AREA_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_UNION_AREA_HPP
+
+#include <boost/geometry/algorithms/expand.hpp>
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+/**
+ * \brief Compute the area of the union of b1 and b2
+ */
+template <typename Box, typename Geometry>
+inline typename area_result<Box>::type union_area(Box const& b, Geometry const& g)
+{
+    Box expanded_box(b);
+    geometry::expand(expanded_box, g);
+    return index::area(expanded_box);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_UNION_AREA_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/default_parameter.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/default_parameter.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,62 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - default indexes parameters
+//
+// 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_DEFAULT_PARAMETER_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_DEFAULT_PARAMETER_HPP
+
+#include <boost/geometry/geometries/point.hpp>
+#include <boost/geometry/geometries/box.hpp>
+#include <boost/geometry/extensions/index/translator/def.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+// TODO: awulkiew - move this elsewhere
+struct default_parameter {};
+
+namespace detail {
+
+template <typename Indexable>
+struct geometry_box_type
+{
+    typedef geometry::model::box<
+        geometry::model::point<
+            typename index::traits::coordinate_type<Indexable>::type,
+            index::traits::dimension<Indexable>::value,
+            typename index::traits::coordinate_system<Indexable>::type
+        >
+    > type;
+};
+
+template <typename Value, typename Translator>
+struct default_translator_type
+{
+    typedef Translator type;
+};
+template <typename Value>
+struct default_translator_type<Value, default_parameter>
+{
+    typedef translator::def<Value> type;
+};
+
+template <typename Indexable, typename Box>
+struct default_box_type
+{
+    typedef Box type;
+};
+template <typename Indexable>
+struct default_box_type<Indexable, default_parameter>
+{
+    typedef typename detail::geometry_box_type<Indexable>::type type;
+};
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_DEFAULT_PARAMETER_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/filters/nearest_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/filters/nearest_filter.hpp	2011-03-24 19:52:27 EDT (Thu, 24 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_new/boost/geometry/extensions/index/filters/spacial_filter.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/filters/spacial_filter.hpp	2011-03-24 19:52:27 EDT (Thu, 24 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 Geometry>
+    spatial_filter(SpacialIndex const&, Geometry 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 Geometry>
+class spatially_filtered
+{
+public:
+    explicit spatially_filtered(Geometry const& geom) : m_geom(geom) {}
+    Geometry const& geometry() const { return m_geom; }
+
+private:
+    Geometry const& m_geom;
+};
+
+} // namespace detail
+
+template <typename Geometry>
+detail::spatially_filtered<Geometry> spatially_filtered(Geometry const& geom)
+{
+    return detail::spatially_filtered<Geometry>(geom);
+}
+
+}}}} // namespace boost::geometry::index::filters
+
+template<typename SpacialIndex, typename Geometry>
+boost::geometry::index::filters::spatial_filter<SpacialIndex>
+operator|(
+    SpacialIndex const& si,
+    boost::geometry::index::filters::detail::spatially_filtered<Geometry> const& f)
+{
+    return boost::geometry::index::filters::spatial_filter<SpacialIndex>(si, f.geometry());
+}
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_FILTERS_SPACIAL_FILTER_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/indexable.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/indexable.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,160 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - indexable traits and 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_INDEXABLE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_INDEXABLE_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace dispatch {
+
+// Distinguish between indexables and other geometries
+
+template <typename Geometry, typename GeometryTag>
+struct indexable_type
+{
+    typedef void type;
+};
+
+template <typename Point>
+struct indexable_type<Point, geometry::point_tag>
+{
+    typedef Point type;
+};
+
+template <typename Box>
+struct indexable_type<Box, geometry::box_tag>
+{
+    typedef Box type;
+};
+
+} // namespace dispatch
+
+namespace traits
+{
+
+template <typename Indexable>
+struct indexable_type
+{
+    typedef typename dispatch::indexable_type<
+        Indexable,
+        typename geometry::traits::tag<Indexable>::type
+    >::type type;
+};
+
+} // namespace traits
+
+namespace dispatch {
+
+template <typename Indexable, typename IndexableTag>
+struct point_type
+{
+    typedef void type;
+};
+
+template <typename Indexable>
+struct point_type<Indexable, geometry::box_tag>
+{
+    typedef typename geometry::traits::point_type<Indexable>::type type;
+};
+
+template <typename Indexable>
+struct point_type<Indexable, geometry::point_tag>
+{
+    typedef Indexable type;
+};
+
+} // namespace dispatch
+
+namespace traits {
+
+template <typename Indexable>
+struct point_type
+{
+    typedef typename dispatch::point_type<
+        Indexable,
+        typename geometry::traits::tag<Indexable>::type
+    >::type type;
+};
+
+template <typename Indexable>
+struct coordinate_system
+{
+    typedef typename geometry::traits::coordinate_system<
+        typename point_type<Indexable>::type
+    >::type type;
+};
+
+template <typename Indexable>
+struct coordinate_type
+{
+    typedef typename geometry::traits::coordinate_type<
+        typename point_type<Indexable>::type
+    >::type type;
+};
+
+template <typename Indexable>
+struct dimension
+{
+    static const size_t value =
+        geometry::traits::dimension<
+            typename point_type<Indexable>::type
+        >::value;
+};
+
+} // namespace traits
+
+namespace dispatch {
+
+template <size_t Corner, size_t DimensionIndex, typename Indexable, typename IndexableTag>
+struct indexable_indexed_access {};
+
+template <size_t Corner, size_t DimensionIndex, typename Indexable>
+struct indexable_indexed_access<Corner, DimensionIndex, Indexable, box_tag>
+{
+    typedef typename traits::point_type<Indexable>::type point_type;
+    typedef typename traits::coordinate_type<point_type>::type coordinate_type;
+
+    static inline coordinate_type get(Indexable const& i)
+    {
+        return geometry::get<Corner, DimensionIndex>(i);
+    }
+};
+
+template <size_t Corner, size_t DimensionIndex, typename Indexable>
+struct indexable_indexed_access<Corner, DimensionIndex, Indexable, point_tag>
+{
+    typedef typename traits::coordinate_type<Indexable>::type coordinate_type;
+
+    static inline coordinate_type get(Indexable const& i)
+    {
+        return geometry::get<DimensionIndex>(i);
+    }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <size_t Corner, size_t DimensionIndex, typename Indexable>
+typename traits::coordinate_type<Indexable>::type get(Indexable const& i)
+{
+    return dispatch::indexable_indexed_access<
+        Corner,
+        DimensionIndex,
+        Indexable,
+        typename geometry::traits::tag<Indexable>::type
+    >::get(i);
+}
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_INDEXABLE_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/filters.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,52 @@
+// 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 <vector>
+#include <boost/static_assert.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 {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+class rtree;
+
+namespace filters {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+class spatial_filter< index::rtree<Value, Translator, Box, Tag> >
+{
+public:
+    typedef typename std::vector<Value>::iterator iterator;
+    typedef typename std::vector<Value>::const_iterator const_iterator;
+
+    template <typename Geometry>
+    spatial_filter(index::rtree<Value, Translator, Box, Tag> const& rtree, Geometry const& geom)
+    {
+        m_result = rtree.find(geom);
+    }
+
+    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::vector<Value> m_result;
+};
+
+} // namespace filters
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,16 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree
+//
+// 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_RSTAR_RSTAR_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_HPP
+
+#include <boost/geometry/extensions/index/rtree/rstar/tags.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp>
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,729 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree insert algorithm 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_RSTAR_RTREE_INSERT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RTREE_INSERT_HPP
+
+#include <algorithm>
+
+#include <boost/tuple/tuple.hpp>
+
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+#include <boost/geometry/extensions/index/algorithms/margin.hpp>
+#include <boost/geometry/extensions/index/algorithms/overlap.hpp>
+#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_insert.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+// ----------------------------------------------------------------------------- //
+// rstar/choose_next_node
+// ----------------------------------------------------------------------------- //
+
+// TODO: awulkiew - it's possible that goodness values may be used to choose next node
+
+// rtree choose_next_node algorithm for rstar variant
+
+template <typename Value, typename Box>
+class rtree_rstar_choose_next_node
+{
+    typedef typename index::detail::rtree_node<Value, Box, rtree_rstar_tag>::type node;
+    typedef typename index::detail::rtree_internal_node<Value, Box, rtree_rstar_tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, rtree_rstar_tag>::type leaf;
+
+    typedef typename internal_node::children_type children_type;
+
+public:
+    // TODO: awulkiew - alternative lower-cost version of overlap calculation may be used (branch_areas)
+    // TODO: awulkiew - further optimization: don't calculate area with the overlap, calculate it only if
+    // overlap < smallest_overlap (and current area must be stored) OR
+    // overlap == smallest_overlap (and area must be compared)
+    template <typename Indexable>
+    static inline size_t apply(internal_node & n, Indexable const& indexable)
+    {
+        assert(!n.children.empty());
+        
+        bool has_leaves = boost::apply_visitor(
+            visitors::rtree_is_leaf<Value, Box, rtree_rstar_tag>(),
+            *n.children.front().second);
+
+        if ( !has_leaves )
+            return impl<internal_node_areas>(n, indexable);
+        else
+            return impl<branch_areas>(n, indexable);
+    }
+
+private:
+    template <typename Areas, typename Indexable>
+    static inline size_t impl(internal_node & n, Indexable const& indexable)
+    {
+        typedef typename children_type::iterator children_iterator;
+
+        //assert(!n.children.empty());
+
+        children_iterator temp_it = n.children.begin();
+        children_iterator child_it = temp_it;
+        Areas min_areas(n.children, child_it, indexable);
+
+        for (children_iterator it = ++temp_it;
+            it != n.children.end(); ++it)
+        {
+            Areas areas(n.children, it, indexable);
+
+            if ( areas < min_areas )
+            {
+                child_it = it;
+                min_areas = areas;
+            }
+        }
+
+        // TODO: awulkiew - switch to indexes in the whole class?
+        return child_it - n.children.begin();
+    }
+
+    struct branch_areas
+    {
+        typedef typename area_result<Box>::type area_type;
+
+        template <typename Indexable>
+        inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
+        {
+            overlap_area = 0;
+            for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
+                if ( it != k_it )
+                    overlap_area += index::overlap(k_it->first, it->first);
+
+            area = index::area(k_it->first);
+
+            diff_area = index::union_area(k_it->first, indexable) - area;
+        }
+
+        inline bool operator<(branch_areas &a) const
+        {
+            return overlap_area < a.overlap_area ||
+                ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
+                ( diff_area == a.diff_area && area < a.area );
+        }
+
+        area_type overlap_area;
+        area_type diff_area;
+        area_type area;
+    };
+
+    struct internal_node_areas
+    {
+        typedef typename area_result<Box>::type area_type;
+
+        template <typename Indexable>
+        inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
+        {
+            area = index::area(k_it->first);
+            diff_area = index::union_area(k_it->first, indexable) - area;
+        }
+
+        inline bool operator<(internal_node_areas &a) const
+        {
+            return diff_area < a.diff_area ||
+                ( diff_area == a.diff_area && area < a.area );
+        }
+
+        area_type diff_area;
+        area_type area;
+    };
+};
+
+// ----------------------------------------------------------------------------- //
+// rstar/sorts
+// ----------------------------------------------------------------------------- //
+
+// elements ids less comparator
+
+template <typename Elements, typename Translator, size_t Corner, size_t AxisIndex>
+class rtree_rstar_elements_indexes_less
+{
+public:
+    rtree_rstar_elements_indexes_less(Elements const& elements, Translator const& tr)
+        : m_elements(elements), m_tr(tr)
+    {}
+
+    bool operator()(size_t e1_index, size_t e2_index)
+    {
+        return
+            index::detail::get<Corner, AxisIndex>(
+                index::detail::rtree_element_indexable(m_elements[e1_index], m_tr)
+            )
+            <
+            index::detail::get<Corner, AxisIndex>(
+                index::detail::rtree_element_indexable(m_elements[e2_index], m_tr)
+            );
+    }
+
+private:
+    Elements const& m_elements;
+    Translator const& m_tr;
+};
+
+template <typename T, size_t Dimension>
+class rtree_rstar_vectors
+{
+public:
+    inline rtree_rstar_vectors(size_t count)
+        : m_count(count), m_ids(Dimension * 2 * count)
+    {}
+
+    template <size_t AxisIndex, size_t Corner>
+    inline typename std::vector<T>::iterator begin()
+    {
+        BOOST_STATIC_ASSERT(AxisIndex < Dimension);
+        BOOST_STATIC_ASSERT(Corner < 2);
+        return m_ids.begin() + ( AxisIndex * 2 + Corner ) * m_count;
+    }
+
+    template <size_t AxisIndex, size_t Corner>
+    inline typename std::vector<T>::iterator end()
+    {
+        BOOST_STATIC_ASSERT(AxisIndex < Dimension);
+        BOOST_STATIC_ASSERT(Corner < 2);
+        return m_ids.begin() + ( AxisIndex * 2 + Corner + 1) * m_count;
+    }
+
+    template <size_t AxisIndex, size_t Corner>
+    inline T const& get(size_t index) const
+    {
+        BOOST_STATIC_ASSERT(AxisIndex < Dimension);
+        BOOST_STATIC_ASSERT(Corner < 2);
+        assert(index < m_count);
+        return m_ids[( AxisIndex * 2 + Corner ) * m_count + index];
+    }
+
+    template <size_t AxisIndex, size_t Corner>
+    inline void set(size_t index, T const& v)
+    {
+        BOOST_STATIC_ASSERT(AxisIndex < Dimension);
+        BOOST_STATIC_ASSERT(Corner < 2);
+        assert(index < m_count);
+        m_ids[( AxisIndex * 2 + Corner ) * m_count + index] = v;
+    }
+
+    inline T const& get(size_t axis, size_t corner, size_t index) const
+    {
+        assert(axis < Dimension);
+        assert(corner < 2);
+        assert(index < m_count);
+        return m_ids[( axis * 2 + corner ) * m_count + index];
+    }
+
+    inline size_t vector_size() const
+    {
+        return m_count;
+    }
+
+private:
+    size_t m_count;
+    std::vector<T> m_ids;
+};
+
+// init indexes of elements and sort them
+
+template <typename Elements, typename Translator, size_t Dimension>
+class rtree_rstar_sorts_fill_ids
+{
+    BOOST_STATIC_ASSERT(0 < Dimension);
+
+public:
+    template <size_t D>
+    static inline void apply(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
+    {
+        rtree_rstar_sorts_fill_ids<Elements, Translator, Dimension - 1>::apply(ids, elements, tr);
+
+        fill<min_corner>(ids, elements, tr);
+        fill<max_corner>(ids, elements, tr);
+    }
+
+private:
+    template <size_t Corner, size_t D>
+    static inline void fill(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
+    {
+        for ( size_t i = 0 ; i < elements.size() ; ++i )
+            ids.set<Dimension - 1, Corner>(i, i);
+
+        rtree_rstar_elements_indexes_less<Elements, Translator, Corner, Dimension - 1> less(elements, tr);
+        std::sort(ids.begin<Dimension - 1, Corner>(), ids.end<Dimension - 1, Corner>(), less);
+    }
+};
+
+template <typename Elements, typename Translator>
+class rtree_rstar_sorts_fill_ids<Elements, Translator, 1>
+{
+public:
+    template <size_t D>
+    static inline void apply(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
+    {
+        fill<min_corner>(ids, elements, tr);
+        fill<max_corner>(ids, elements, tr);
+    }
+
+private:
+    template <size_t Corner, size_t D>
+    static inline void fill(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
+    {
+        for ( size_t i = 0 ; i < elements.size() ; ++i )
+            ids.set<0, Corner>(i, i);
+
+        rtree_rstar_elements_indexes_less<Elements, Translator, Corner, 0> less(elements, tr);
+        std::sort(ids.begin<0, Corner>(), ids.end<0, Corner>(), less);
+    }
+};
+
+// sorts for each axis for min and max
+
+template <typename Elements, typename Translator, size_t Dimension>
+class rtree_rstar_sorts
+{
+public:
+    inline rtree_rstar_sorts(Elements const& elements, Translator const& tr)
+        : m_elems(elements), m_tr(tr), m_ids(m_elems.size())
+    {
+        rtree_rstar_sorts_fill_ids<Elements, Translator, Dimension>::apply(m_ids, elements, tr);
+    }
+
+    // TODO: awulkiew - should those methods be here? Just leave get_element?
+
+    template <size_t AxisIndex, size_t Corner>
+    inline typename index::detail::rtree_element_indexable_type<typename Elements::value_type, Translator>::type const&
+    get_indexable(size_t index) const
+    {
+        size_t id = m_ids.get<AxisIndex, Corner>(index);
+        return index::detail::rtree_element_indexable(m_elems[id], m_tr);
+    }
+
+    inline typename index::detail::rtree_element_indexable_type<typename Elements::value_type, Translator>::type const&
+    get_indexable(size_t axis, size_t corner, size_t index) const
+    {
+        size_t id = m_ids.get(axis, corner, index);
+        return index::detail::rtree_element_indexable(m_elems[id], m_tr);
+    }
+
+    template <size_t AxisIndex, size_t Corner>
+    inline typename Elements::value_type const& get_element(size_t index) const
+    {
+        size_t id = m_ids.get<AxisIndex, Corner>(index);
+        return m_elems[id];
+    }
+
+    inline typename Elements::value_type const& get_element(size_t axis, size_t corner, size_t index) const
+    {
+        size_t id = m_ids.get(axis, corner, index);
+        return m_elems[id];
+    }
+
+    inline size_t sort_size() const
+    {
+        return m_ids.vector_size();
+    }
+
+private:
+    Elements const& m_elems;
+    Translator const& m_tr;
+
+    rtree_rstar_vectors<size_t, Dimension> m_ids;
+};
+
+// ----------------------------------------------------------------------------- //
+// rstar/goodness_values
+// ----------------------------------------------------------------------------- //
+
+// calculate margins, areas and overlaps
+
+template <typename Box, size_t AxisIndex, size_t Corner>
+class rtree_rstar_calculate_goodness_values_for_axis
+{
+    typedef typename geometry::traits::coordinate_type<
+        typename geometry::traits::point_type<Box>::type
+    >::type coordinate_type;
+
+    static const size_t dimension = geometry::traits::dimension<
+        typename geometry::traits::point_type<Box>::type
+    >::value;
+
+    typedef typename area_result<Box>::type area_type;
+    typedef typename margin_result<Box>::type margin_type;
+    typedef typename overlap_result<Box>::type overlap_type;
+    typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
+
+public:
+    template <typename Elements, typename Translator>
+    static inline void apply(
+        rtree_rstar_vectors<goodness_type, dimension> & goodness_vectors,
+        rtree_rstar_sorts<Elements, Translator, dimension> const& sorts,
+        size_t min_elems,
+        size_t max_elems)
+    {
+        assert(sorts.sort_size() == max_elems + 1);
+        assert(goodness_vectors.vector_size() == max_elems - 2 * min_elems + 2);
+
+        size_t median_index_last = max_elems - min_elems + 2;
+        size_t i = 0;
+        for ( size_t median_index = min_elems ; median_index < median_index_last ; ++median_index, ++i )
+        {
+            Box left_box = calculate_box(sorts, 0, median_index);
+            Box right_box = calculate_box(sorts, median_index, sorts.sort_size());
+
+            margin_type margin = index::margin(left_box) + index::margin(right_box);
+            area_type area = index::area(left_box) + index::area(right_box);
+            overlap_type overlap = index::overlap(left_box, right_box);
+
+            goodness_vectors.set<AxisIndex, Corner>(
+                i,
+                boost::make_tuple(left_box, right_box, margin, overlap, area));
+        }
+    }
+private:
+    template <typename Elements, typename Translator>
+    static inline Box calculate_box(
+        rtree_rstar_sorts<Elements, Translator, dimension> const& sorts,
+        size_t index_first,
+        size_t index_last)
+    {
+        assert(index_first < index_last);
+
+        Box result;
+        geometry::convert(sorts.template get_indexable<AxisIndex, Corner>(index_first), result);
+        ++index_first;
+        for ( ; index_first < index_last ; ++index_first )
+            geometry::expand(result, sorts.template get_indexable<AxisIndex, Corner>(index_first));
+        return result;
+    }
+};
+
+// calculate goodness values for all axis
+
+template <typename Box, size_t Dimension>
+struct rtree_rstar_calculate_goodness_values
+{
+    BOOST_STATIC_ASSERT(0 < Dimension);
+
+    typedef typename area_result<Box>::type area_type;
+    typedef typename margin_result<Box>::type margin_type;
+    typedef typename overlap_result<Box>::type overlap_type;
+    typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
+
+    template <typename Elements, typename Translator, size_t D>
+    static inline void apply(
+        rtree_rstar_vectors<goodness_type, D> & goodness_vectors,
+        rtree_rstar_sorts<Elements, Translator, D> const& sorts,
+        size_t min_elems,
+        size_t max_elems)
+    {
+        rtree_rstar_calculate_goodness_values<Box, Dimension - 1>
+            ::apply(goodness_vectors, sorts, min_elems, max_elems);
+
+        rtree_rstar_calculate_goodness_values_for_axis<Box, Dimension - 1, min_corner>
+            ::apply(goodness_vectors, sorts, min_elems, max_elems);
+        rtree_rstar_calculate_goodness_values_for_axis<Box, Dimension - 1, max_corner>
+            ::apply(goodness_vectors, sorts, min_elems, max_elems);
+    }
+};
+
+template <typename Box>
+struct rtree_rstar_calculate_goodness_values<Box, 1>
+{
+    typedef typename area_result<Box>::type area_type;
+    typedef typename margin_result<Box>::type margin_type;
+    typedef typename overlap_result<Box>::type overlap_type;
+    typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
+
+    template <typename Elements, typename Translator, size_t D>
+    static inline void apply(
+        rtree_rstar_vectors<goodness_type, D> & goodness_vectors,
+        rtree_rstar_sorts<Elements, Translator, D> const& sorts,
+        size_t min_elems,
+        size_t max_elems)
+    {
+        rtree_rstar_calculate_goodness_values_for_axis<Box, 0, min_corner>
+            ::apply(goodness_vectors, sorts, min_elems, max_elems);
+        rtree_rstar_calculate_goodness_values_for_axis<Box, 0, max_corner>
+            ::apply(goodness_vectors, sorts, min_elems, max_elems);
+    }
+};
+
+// goodness values
+
+template <typename Elements, typename Translator, typename Box>
+class rtree_rstar_goodness_values
+{
+    typedef typename geometry::traits::coordinate_type<
+        typename geometry::traits::point_type<Box>::type
+    >::type coordinate_type;
+
+    static const size_t dimension = geometry::traits::dimension<
+        typename geometry::traits::point_type<Box>::type
+    >::value;
+
+    typedef typename area_result<Box>::type area_type;
+    typedef typename margin_result<Box>::type margin_type;
+    typedef typename overlap_result<Box>::type overlap_type;
+    typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
+
+public:
+    inline rtree_rstar_goodness_values(
+        Elements const& elements,
+        Translator const& tr,
+        size_t min_elems,
+        size_t max_elems)
+        : m_sorts(elements, tr)
+        , m_goodness_vectors(max_elems - 2 * min_elems + 2)
+    {
+        rtree_rstar_calculate_goodness_values<Box, dimension>::apply(
+            m_goodness_vectors, m_sorts, min_elems, max_elems);
+    }
+
+    inline size_t elements_size() const
+    {
+        return m_sorts.sort_size();
+    }
+
+    inline size_t goodnesses_size() const
+    {
+        return m_goodness_vectors.vector_size();
+    }
+
+    inline goodness_type const& get_goodness(size_t axis, size_t corner, size_t index) const
+    {
+        return m_goodness_vectors.get(axis, corner, index);
+    }
+
+    inline typename Elements::value_type const& get_element(size_t axis, size_t corner, size_t index) const
+    {
+        return m_sorts.get_element(axis, corner, index);
+    }
+
+private:
+    rtree_rstar_sorts<Elements, Translator, dimension> m_sorts;
+    rtree_rstar_vectors<goodness_type, dimension> m_goodness_vectors;
+};
+
+template <typename Elements, typename Translator, typename Box>
+class rtree_rstar_choose_split_axis
+{
+    typedef typename margin_result<Box>::type margin_type;
+public:
+    static inline std::pair<size_t, size_t> apply(rtree_rstar_goodness_values<Elements, Translator, Box> const& gv)
+    {
+        std::pair<size_t, size_t> smallest_distr = std::make_pair(0, 0);
+        margin_type smallest_margins_sum = calculate_margins_sum(0, 0, gv);
+
+        margin_type margins_sum = calculate_margins_sum(0, 1, gv);
+        if ( margins_sum < smallest_margins_sum )
+        {
+            smallest_distr.second = 1;
+            smallest_margins_sum = margins_sum;
+        }
+
+        for ( size_t a = 1 ; a < traits::dimension<Box>::value ; ++a )
+        {
+            for ( size_t c = 0 ; c < 2 ; ++c )
+            {
+                margins_sum = calculate_margins_sum(a, c, gv);
+                if ( margins_sum < smallest_margins_sum )
+                {
+                    smallest_distr.first = a;
+                    smallest_distr.second = c;
+                    smallest_margins_sum = margins_sum;
+                }
+            }
+        }
+        return smallest_distr;
+    }
+private:
+    static inline typename margin_result<Box>::type
+            calculate_margins_sum(size_t axis, size_t corner, rtree_rstar_goodness_values<Elements, Translator, Box> const& gv)
+    {
+        typename margin_result<Box>::type margins_sum = 0;
+        for ( size_t i = 0 ; i < gv.goodnesses_size() ; ++i )
+            margins_sum += boost::get<2>(gv.get_goodness(axis, corner, i));
+        return margins_sum;
+    }
+};
+
+template <typename Elements, typename Translator, typename Box>
+class rtree_rstar_choose_split_index
+{
+    typedef typename area_result<Box>::type area_type;
+    typedef typename overlap_result<Box>::type overlap_type;
+public:
+    static inline size_t apply(rtree_rstar_goodness_values<Elements, Translator, Box> const& gv, size_t axis, size_t corner)
+    {
+        size_t smallest_index = 0;
+        overlap_type smallest_overlap = boost::get<3>(gv.get_goodness(axis, corner, 0));
+        overlap_type smallest_area = boost::get<4>(gv.get_goodness(axis, corner, 0));
+
+        for ( size_t i = 1 ; i < gv.goodnesses_size() ; ++i )
+        {
+            overlap_type overlap = boost::get<3>(gv.get_goodness(axis, corner, i));
+            if ( overlap < smallest_overlap )
+            {
+                smallest_overlap = overlap;
+                smallest_area = boost::get<4>(gv.get_goodness(axis, corner, i));
+                smallest_index = i;
+            }
+            else if ( overlap == smallest_overlap )
+            {
+                area_type area = boost::get<4>(gv.get_goodness(axis, corner, i));
+                if ( area < smallest_area )
+                {
+                    smallest_area = area;
+                    smallest_index = i;
+                }
+            }
+        }
+
+        return smallest_index;
+    }
+};
+
+// rtree insert routine for rstar variant
+
+template <typename Value, typename Translator, typename Box>
+class rtree_insert<Value, Translator, Box, rtree_rstar_tag> : public boost::static_visitor<>
+{
+    typedef typename index::detail::rtree_node<Value, Box, rtree_rstar_tag>::type node;
+    typedef typename index::detail::rtree_internal_node<Value, Box, rtree_rstar_tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, rtree_rstar_tag>::type leaf;
+
+public:
+    inline explicit rtree_insert(node* & root, Value const& v, size_t min_elements, size_t max_elements, Translator const& t)
+        : m_value(v), m_tr(t), m_min_elems_per_node(min_elements), m_max_elems_per_node(max_elements)
+        , m_root_node(root)
+        , m_parent(0), m_current_child_index(0)
+    {}
+
+    inline void operator()(internal_node & n)
+    {
+        // save previous traverse inputs and set new ones
+        internal_node * parent_bckup = m_parent;
+        m_parent = &n;
+        size_t current_child_index_bckup = m_current_child_index;
+
+        // choose next node, where value insert traversing should go
+        m_current_child_index = rtree_rstar_choose_next_node<Value, Box>::apply(n, m_tr(m_value));
+
+        // TODO: awulkiew - if reinsert is implemented this must be changed
+        geometry::expand(n.children[m_current_child_index].first, m_tr(m_value));
+
+        // next traversing step
+        boost::apply_visitor(*this, *n.children[m_current_child_index].second);
+
+        // restore previous traverse inputs
+        m_parent = parent_bckup;
+        m_current_child_index = current_child_index_bckup;
+
+        if ( m_max_elems_per_node < n.children.size() )
+        {
+            split(n);
+        }
+    }
+
+    inline void operator()(leaf & n)
+    {
+        n.values.push_back(m_value);
+
+        if ( m_max_elems_per_node < n.values.size() )
+        {
+            split(n);
+        }
+    }
+
+private:
+    template <typename Node>
+    inline void split(Node & n)
+    {
+        typedef typename index::detail::rtree_elements_type<Node>::type elements_type;
+        typedef typename elements_type::value_type element_type;
+
+        elements_type & elems = index::detail::get_elements(n);
+
+        rtree_rstar_goodness_values<elements_type, Translator, Box> gv(elems, m_tr, m_min_elems_per_node, m_max_elems_per_node);
+
+        std::pair<size_t, size_t> axis_and_corner =
+            rtree_rstar_choose_split_axis<elements_type, Translator, Box>::apply(gv);
+        size_t axis = axis_and_corner.first;
+        size_t corner = axis_and_corner.second;
+
+        size_t choosen_index =
+            rtree_rstar_choose_split_index<elements_type, Translator, Box>::apply(gv, axis, corner);
+
+        size_t median_index = m_min_elems_per_node + choosen_index;
+        assert(median_index <= m_max_elems_per_node + 1 - m_min_elems_per_node);
+
+        // create new node
+        node * right_node = rtree_create_node(Node());
+        elements_type & new_elems = index::detail::get_elements(boost::get<Node>(*right_node));
+
+        // update new node's elements
+        new_elems.reserve(m_max_elems_per_node + 1 - median_index);
+        for ( size_t i = median_index ; i < m_max_elems_per_node + 1 ; ++i)
+            new_elems.push_back(gv.get_element(axis, corner, i));
+
+        // fill temporary container with left node's elements
+        elements_type left_elems;
+        left_elems.reserve(median_index);
+        for ( size_t i = 0 ; i < median_index ; ++i )
+            left_elems.push_back(gv.get_element(axis, corner, i));
+        // update old node's elements
+        elems = left_elems;
+        
+        if ( m_parent != 0 )
+        {
+            // update old node's box
+            m_parent->children[m_current_child_index].first = boost::get<0>(gv.get_goodness(axis, corner, choosen_index));
+            // add new node to the parent's children
+            m_parent->children.push_back( std::make_pair(
+                boost::get<1>(gv.get_goodness(axis, corner, choosen_index)), right_node ) );
+        }
+        else
+        {
+            assert(&n == boost::get<Node>(m_root_node));
+
+            // create new root and add nodes
+            node * new_root = rtree_create_node(internal_node());
+            
+            boost::get<internal_node>(*new_root).children.push_back(
+                std::make_pair(boost::get<0>(gv.get_goodness(axis, corner, choosen_index)), m_root_node)
+            );
+            boost::get<internal_node>(*new_root).children.push_back(
+                std::make_pair(boost::get<1>(gv.get_goodness(axis, corner, choosen_index)), right_node)
+            );
+            
+            m_root_node = new_root;
+        }
+    }
+
+    Value const& m_value;
+    Translator const& m_tr;
+    size_t m_min_elems_per_node;
+    size_t m_max_elems_per_node;
+
+    node* & m_root_node;
+
+    // traversing input parameters
+    internal_node *m_parent;
+    size_t m_current_child_index;
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RTREE_INSERT_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/tags.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/tags.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,19 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree tags
+//
+// 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_RSTAR_TAGS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_TAGS_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+struct rtree_rstar_tag {};
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_TAGS_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,111 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree implementation
+//
+// Copyright 2008 Federico J. Fernandez.
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RTREE_HPP
+
+#include <boost/geometry/extensions/index/default_parameter.hpp>
+
+#include <boost/geometry/extensions/index/rtree/filters.hpp>
+
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_find.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_delete.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+// TODO: awulkiew - min and max elems as template parameters?
+
+template <
+    typename Value,
+    typename Translator = default_parameter,
+    typename Box = default_parameter,
+    typename Tag = rtree_rstar_tag
+>
+class rtree
+{
+public:
+    typedef Value value_type;
+    typedef typename detail::default_translator_type<Value, Translator>::type translator_type;
+    typedef typename detail::default_box_type<typename translator_type::indexable_type, Box>::type box_type;
+
+    typedef typename detail::rtree_node<Value, box_type, rtree_rstar_tag>::type node;
+    typedef typename detail::rtree_internal_node<Value, box_type, rtree_rstar_tag>::type internal_node;
+    typedef typename detail::rtree_leaf<Value, box_type, rtree_rstar_tag>::type leaf;
+
+    inline explicit rtree(size_t max_elems_per_node = 4, size_t min_elems_per_node = 2, translator_type const& translator = translator_type())
+        : m_values_count(0)
+        , m_max_elems_per_node(max_elems_per_node)
+        , m_min_elems_per_node(min_elems_per_node)
+        , m_root(0)
+        , m_translator(translator)
+    {
+        if ( min_elems_per_node < 2 )
+            min_elems_per_node = 2;
+
+        // TODO: awulkiew - reconsider following assert
+        assert(2 * m_min_elems_per_node <= m_max_elems_per_node);
+
+        m_root = detail::rtree_create_node(leaf());
+    }
+
+    ~rtree()
+    {
+        visitors::rtree_delete<Value, translator_type, box_type, Tag> del_v;
+        boost::apply_visitor(del_v, *m_root);
+    }
+
+    template <typename Geometry>
+    inline std::vector<Value> find(Geometry const& geom) const
+    {
+        visitors::rtree_find<Value, translator_type, box_type, Tag, Geometry> find_v(geom, m_translator);
+        boost::apply_visitor(find_v, *m_root);
+        return find_v.result;
+    }
+
+    void insert(Value const& value)
+    {
+        visitors::rtree_insert<Value, translator_type, box_type, Tag>
+            insert_v(m_root, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
+
+        boost::apply_visitor(insert_v, *m_root);
+
+        ++m_values_count;
+    }
+
+    template <typename Visitor>
+    void apply_visitor(Visitor & visitor) const
+    {
+        boost::apply_visitor(visitor, *m_root);
+    }
+
+    translator_type const& get_translator() const
+    {
+        return  m_translator;
+    }
+
+private:
+    size_t m_values_count;
+    size_t m_max_elems_per_node;
+    size_t m_min_elems_per_node;
+    node *m_root;
+    translator_type m_translator;
+};
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+void insert(rtree<Value, Translator, Box, Tag> & tree, Value const& v)
+{
+    tree.insert(v);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RSTREE_RSTREE_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,196 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree details
+//
+// Copyright 2008 Federico J. Fernandez.
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DEFAULT_NODE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DEFAULT_NODE_HPP
+
+#include <vector>
+#include <boost/variant.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail {
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_node;
+
+// nodes default types
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_internal_node_def
+{
+    typedef std::vector<
+        std::pair<
+            Box,
+            typename rtree_node<Value, Box, Tag>::type *
+        >
+    > children_type;
+
+    children_type children;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_leaf_def
+{
+    typedef std::vector<Value> values_type;
+    values_type values;
+};
+
+// nodes traits
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_node
+{
+    typedef boost::variant<
+        rtree_leaf_def<Value, Box, Tag>,
+        rtree_internal_node_def<Value, Box, Tag>
+    > type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_internal_node
+{
+    typedef rtree_internal_node_def<Value, Box, Tag> type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_leaf
+{
+    typedef rtree_leaf_def<Value, Box, Tag> type;
+};
+
+// nodes elements extractor
+
+template <typename Node>
+struct rtree_elements_type
+{
+    typedef typename Node::elements_type type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_elements_type< rtree_internal_node_def<Value, Box, Tag> >
+{
+    typedef typename rtree_internal_node_def<Value, Box, Tag>::children_type type;
+};
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_elements_type< rtree_leaf_def<Value, Box, Tag> >
+{
+    typedef typename rtree_leaf_def<Value, Box, Tag>::values_type type;
+};
+
+template <typename Node>
+typename rtree_elements_type<Node>::type & get_elements(Node & n)
+{
+    return n.elements;
+}
+
+template <typename Value, typename Box, typename Tag>
+typename rtree_internal_node_def<Value, Box, Tag>::children_type &
+get_elements(rtree_internal_node_def<Value, Box, Tag> & n)
+{
+    return n.children;
+}
+
+template <typename Value, typename Box, typename Tag>
+typename rtree_leaf_def<Value, Box, Tag>::values_type &
+get_elements(rtree_leaf_def<Value, Box, Tag> & n)
+{
+    return n.values;
+}
+
+// uniform indexable type for child node element's box and value's indexable
+
+template <typename Value, typename Translator>
+struct rtree_element_indexable_type
+{
+    typedef typename Translator::indexable_type type;
+};
+
+template <typename Value, typename Box, typename Tag, typename Translator>
+struct rtree_element_indexable_type<
+    std::pair<
+        Box,
+        boost::variant<
+            rtree_leaf_def<Value, Box, Tag>,
+            rtree_internal_node_def<Value, Box, Tag>
+        > *
+    >,
+    Translator
+>
+{
+    typedef Box type;
+};
+
+// uniform indexable getter for child node element's box and value's indexable
+
+template <typename Value, typename Box, typename Tag, typename Translator>
+Box const&
+rtree_element_indexable(
+    std::pair<
+        Box,
+        boost::variant<
+            rtree_leaf_def<Value, Box, Tag>,
+            rtree_internal_node_def<Value, Box, Tag>
+        > *
+    > const& el,
+    Translator const&)
+{
+    return el.first;
+}
+
+template <typename Value, typename Translator>
+typename Translator::indexable_type const&
+rtree_element_indexable(Value const& el, Translator const& tr)
+{
+    return tr(el);
+};
+
+// create leaf node
+
+template <typename Value, typename Box, typename Tag>
+typename rtree_node<Value, Box, Tag>::type *
+rtree_create_node(rtree_leaf_def<Value, Box, Tag> const& l)
+{
+    typedef typename rtree_node<Value, Box, Tag>::type node;
+    node * n = new node();
+    *n = l;
+    return n;
+}
+
+// create internal node
+
+template <typename Value, typename Box, typename Tag>
+typename rtree_node<Value, Box, Tag>::type *
+rtree_create_node(rtree_internal_node_def<Value, Box, Tag> const& in)
+{
+    typedef typename rtree_node<Value, Box, Tag>::type node;
+    node * n = new node();
+    *n = in;
+    return n;
+}
+
+// default node
+
+template <typename Value, typename Box, typename Tag>
+void rtree_delete_node(
+    boost::variant<
+        rtree_leaf_def<Value, Box, Tag>,
+        rtree_internal_node_def<Value, Box, Tag>
+    > * n)
+{
+    delete n;
+}
+
+} // namespace detail
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_DEFAULT_NODE_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,182 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree GL-draw visitor
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP
+
+#include <iostream>
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+namespace dispatch {
+
+template <typename Point, size_t Dimension>
+struct rtree_gl_draw_point
+{};
+
+template <typename Point>
+struct rtree_gl_draw_point<Point, 2>
+{
+    static inline void apply(Point const& p)
+    {
+        glBegin(GL_POINT);
+        glVertex2f(geometry::get<0>(p), geometry::get<1>(p));
+        glEnd();
+    }
+};
+
+template <typename Box, size_t Dimension>
+struct rtree_gl_draw_box
+{};
+
+template <typename Box>
+struct rtree_gl_draw_box<Box, 2>
+{
+    static inline void apply(Box const& b)
+    {
+        glBegin(GL_LINE_LOOP);
+        glVertex2f(geometry::get<min_corner, 0>(b), geometry::get<min_corner, 1>(b));
+        glVertex2f(geometry::get<max_corner, 0>(b), geometry::get<min_corner, 1>(b));
+        glVertex2f(geometry::get<max_corner, 0>(b), geometry::get<max_corner, 1>(b));
+        glVertex2f(geometry::get<min_corner, 0>(b), geometry::get<max_corner, 1>(b));
+        glEnd();
+    }
+};
+
+template <typename Indexable, typename Tag>
+struct rtree_gl_draw_indexable
+{
+};
+
+template <typename Indexable>
+struct rtree_gl_draw_indexable<Indexable, box_tag>
+{
+    typedef typename geometry::traits::point_type<Indexable>::type point_type;
+    static const size_t dimension = geometry::traits::dimension<point_type>::value;
+
+    static inline void apply(Indexable const& i)
+    {
+        rtree_gl_draw_box<Indexable, dimension>::apply(i);
+    }
+};
+
+template <typename Indexable>
+struct rtree_gl_draw_indexable<Indexable, point_tag>
+{
+    static const size_t dimension = geometry::traits::dimension<Indexable>::value;
+
+    static inline void apply(std::ostream &os, Indexable const& i)
+    {
+        rtree_gl_draw_point<Indexable, dimension>::apply(i);
+    }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename Indexable>
+inline void rtree_gl_draw_indexable(Indexable const& i)
+{
+    dispatch::rtree_gl_draw_indexable<
+        Indexable,
+        typename geometry::traits::tag<Indexable>::type
+    >::apply(i);
+}
+
+} // namespace detail
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct rtree_gl_draw : public boost::static_visitor<>
+{
+    typedef typename index::detail::rtree_internal_node<Value, Box, Tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, Tag>::type leaf;
+
+    inline rtree_gl_draw(Translator const& t)
+        : tr(t), level(0)
+    {}
+
+    inline void operator()(internal_node const& n)
+    {
+        typedef typename internal_node::children_type children_type;
+
+        if ( level == 0 )
+            glColor3f(1.0f, 0.0f, 0.0f);
+        else if ( level == 1 )
+            glColor3f(0.0f, 1.0f, 0.0f);
+        else if ( level == 2 )
+            glColor3f(0.0f, 0.0f, 1.0f);
+        else if ( level == 3 )
+            glColor3f(1.0f, 1.0f, 0.0f);
+        else if ( level == 4 )
+            glColor3f(1.0f, 0.0f, 1.0f);
+        else if ( level == 5 )
+            glColor3f(0.0f, 1.0f, 1.0f);
+        else
+            glColor3f(0.5f, 0.5f, 0.5f);
+
+        for (typename children_type::const_iterator it = n.children.begin();
+            it != n.children.end(); ++it)
+        {
+            detail::rtree_gl_draw_indexable(it->first);
+        }
+        
+        size_t level_backup = level;
+        ++level;
+
+        for (typename children_type::const_iterator it = n.children.begin();
+            it != n.children.end(); ++it)
+        {
+            boost::apply_visitor(*this, *it->second);
+        }
+
+        level = level_backup;
+    }
+
+    inline void operator()(leaf const& n)
+    {
+        typedef typename leaf::values_type values_type;
+
+        glColor3f(1.0f, 1.0f, 1.0f);
+
+        for (typename values_type::const_iterator it = n.values.begin();
+            it != n.values.end(); ++it)
+        {
+            detail::rtree_gl_draw_indexable(tr(*it));
+        }
+    }
+
+    Translator const& tr;
+
+    size_t level;
+};
+
+} // namespace visitors
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+void gl_draw(rtree<Value, Translator, Box, Tag> const& tree)
+{
+    typedef typename rtree<Value, Translator, Box, Tag>::translator_type translator_type;
+    typedef typename rtree<Value, Translator, Box, Tag>::box_type box_type;
+
+    glClear(GL_COLOR_BUFFER_BIT);
+
+    visitors::rtree_gl_draw<Value, translator_type, box_type, Tag> gl_draw_v(tree.get_translator());
+    tree.apply_visitor(gl_draw_v);
+
+    glFlush();
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,207 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree printing visitor
+//
+// Copyright 2008 Federico J. Fernandez.
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_PRINT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_PRINT_HPP
+
+#include <iostream>
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+namespace dispatch {
+
+template <typename Point, size_t Dimension>
+struct rtree_print_point
+{
+    BOOST_STATIC_ASSERT(0 < Dimension);
+
+    static inline void apply(std::ostream & os, Point const& p)
+    {
+        rtree_print_point<Point, Dimension - 1>::apply(os, p);
+
+        os << ", " << geometry::get<Dimension - 1>(p);
+    }
+};
+
+template <typename Point>
+struct rtree_print_point<Point, 1>
+{
+    static inline void apply(std::ostream & os, Point const& p)
+    {
+        os << geometry::get<0>(p);
+    }
+};
+
+template <typename Box, size_t Corner, size_t Dimension>
+struct rtree_print_corner
+{
+    BOOST_STATIC_ASSERT(0 < Dimension);
+
+    static inline void apply(std::ostream & os, Box const& b)
+    {
+        rtree_print_corner<Box, Corner, Dimension - 1>::apply(os, b);
+
+        os << ", " << geometry::get<Corner, Dimension - 1>(b);
+    }
+};
+
+template <typename Box, size_t Corner>
+struct rtree_print_corner<Box, Corner, 1>
+{
+    static inline void apply(std::ostream & os, Box const& b)
+    {
+        os << geometry::get<Corner, 0>(b);
+    }
+};
+
+template <typename Indexable, typename Tag>
+struct rtree_print_indexable
+{
+};
+
+template <typename Indexable>
+struct rtree_print_indexable<Indexable, box_tag>
+{
+    typedef typename geometry::traits::point_type<Indexable>::type point_type;
+    static const size_t dimension = geometry::traits::dimension<point_type>::value;
+
+    static inline void apply(std::ostream &os, Indexable const& i)
+    {
+        os << '(';
+        rtree_print_corner<Indexable, min_corner, dimension>::apply(os, i);
+        os << ")x(";
+        rtree_print_corner<Indexable, max_corner, dimension>::apply(os, i);
+        os << ')';
+    }
+};
+
+template <typename Indexable>
+struct rtree_print_indexable<Indexable, point_tag>
+{
+    static const size_t dimension = geometry::traits::dimension<Indexable>::value;
+
+    static inline void apply(std::ostream &os, Indexable const& i)
+    {
+        os << '(';
+        rtree_print_point<Indexable, dimension>::apply(os, i);
+        os << ')';
+    }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename Indexable>
+inline void rtree_print_indexable(std::ostream & os, Indexable const& i)
+{
+    dispatch::rtree_print_indexable<
+        Indexable,
+        typename geometry::traits::tag<Indexable>::type
+    >::apply(os, i);
+}
+
+} // namespace detail
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct rtree_print : public boost::static_visitor<>
+{
+    typedef typename index::detail::rtree_internal_node<Value, Box, Tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, Tag>::type leaf;
+
+    inline rtree_print(std::ostream & o, Translator const& t)
+        : os(o), tr(t), level(0)
+    {}
+
+    inline void operator()(internal_node const& n)
+    {
+        typedef typename internal_node::children_type children_type;
+
+        os << " --> Node --------" << std::endl;
+        os << "  Address: " << this << std::endl;
+        os << "  Level: " << level << std::endl;
+        os << "  Children: " << n.children.size() << std::endl;
+        os << "  | ";
+
+        for (typename children_type::const_iterator it = n.children.begin();
+            it != n.children.end(); ++it)
+        {
+            detail::rtree_print_indexable(os, it->first);
+            os << " | ";
+        }
+        os << std::endl;
+        os << " --< Node --------" << std::endl;
+
+        os << " Children: " << std::endl;
+
+        size_t level_backup = level;
+        ++level;
+
+        for (typename children_type::const_iterator it = n.children.begin();
+            it != n.children.end(); ++it)
+        {
+            boost::apply_visitor(*this, *it->second);
+        }
+
+        level = level_backup;
+    }
+
+    inline void operator()(leaf const& n)
+    {
+        typedef typename leaf::values_type values_type;
+
+        os << "\t" << " --> Leaf --------" << std::endl;
+        os << "\t" << "  Values: " << n.values.size() << std::endl;
+        for (typename values_type::const_iterator it = n.values.begin();
+            it != n.values.end(); ++it)
+        {
+            os << "\t" << "  | ";
+            detail::rtree_print_indexable(os, tr(*it));
+            os << " | " << std::endl;;
+        }
+        os << "\t" << " --< Leaf --------" << std::endl;
+
+    }
+
+    std::ostream & os;
+    Translator const& tr;
+
+    size_t level;
+};
+
+} // namespace visitors
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+std::ostream & print(rtree<Value, Translator, Box, Tag> const& tree, std::ostream & os = std::cout)
+{
+    typedef typename rtree<Value, Translator, Box, Tag>::translator_type translator_type;
+    typedef typename rtree<Value, Translator, Box, Tag>::box_type box_type;
+    visitors::rtree_print<Value, translator_type, box_type, Tag> print_v(os, tree.get_translator());
+    tree.apply_visitor(print_v);
+    return os;
+}
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+std::ostream & operator<<(std::ostream & os, rtree<Value, Translator, Box, Tag> const& tree)
+{
+    typedef typename rtree<Value, Translator, Box, Tag>::translator_type translator_type;
+    typedef typename rtree<Value, Translator, Box, Tag>::box_type box_type;
+    visitors::rtree_print<Value, translator_type, box_type, Tag> print_v(os, tree.get_translator());
+    tree.apply_visitor(print_v);
+    return os;
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_PRINT_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_delete.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_delete.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,47 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree delete visitor
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_DELETE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_DELETE_HPP
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct rtree_delete : public boost::static_visitor<>
+{
+    typedef typename index::detail::rtree_internal_node<Value, Box, Tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, Tag>::type leaf;
+
+    inline void operator()(internal_node & n) const
+    {
+        typedef typename internal_node::children_type children_type;
+
+        for (typename children_type::iterator it = n.children.begin();
+            it != n.children.end(); ++it)
+        {
+            boost::apply_visitor(*this, *it->second);
+
+            index::detail::rtree_delete_node(it->second);
+        }
+    }
+
+    inline void operator()(leaf & n) const
+    {
+    }
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_DELETE_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_find.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_find.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,66 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree find
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_FIND_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_FIND_HPP
+
+#include <boost/geometry/algorithms/intersects.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+// rtree spatial query visitor
+
+template <typename Value, typename Translator, typename Box, typename Tag, typename Geometry>
+struct rtree_find : public boost::static_visitor<>
+{
+    typedef typename index::detail::rtree_internal_node<Value, Box, Tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, Tag>::type leaf;
+
+    inline rtree_find(Geometry const& g, Translator const& t)
+        : geom(g), tr(t)
+    {}
+
+    inline void operator()(internal_node const& n)
+    {
+        typedef typename internal_node::children_type children_type;
+
+        for (typename children_type::const_iterator it = n.children.begin();
+            it != n.children.end(); ++it)
+        {
+            if ( geometry::intersects(it->first, geom) )
+                boost::apply_visitor(*this, *it->second);
+        }
+    }
+
+    inline void operator()(leaf const& n)
+    {
+        typedef typename leaf::values_type values_type;
+
+        for (typename values_type::const_iterator it = n.values.begin();
+            it != n.values.end(); ++it)
+        {
+            if ( geometry::intersects(tr(*it), geom) )
+                result.push_back(*it);
+        }
+    }
+
+    Geometry const& geom;
+    Translator const& tr;
+    std::vector<Value> result;
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_FIND_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_insert.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_insert.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,29 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree details
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_INSERT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_INSERT_HPP
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct rtree_insert
+{
+    // not implemented here
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_INSERT_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,40 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree is leaf visitor
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_IS_LEAF_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_IS_LEAF_HPP
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+template <typename Value, typename Box, typename Tag>
+struct rtree_is_leaf : public boost::static_visitor<bool>
+{
+    typedef typename index::detail::rtree_internal_node<Value, Box, Tag>::type internal_node;
+    typedef typename index::detail::rtree_leaf<Value, Box, Tag>::type leaf;
+
+    inline bool operator()(internal_node const&) const
+    {
+        return false;
+    }
+
+    inline bool operator()(leaf const&) const
+    {
+        return true;
+    }
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_IS_LEAF_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_remove.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_remove.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,29 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree remove
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_REMOVE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_REMOVE_HPP
+
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct rtree_remove
+{
+    // not implemented here
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_REMOVE_HPP

Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp	2011-03-24 19:52:27 EDT (Thu, 24 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_indexable<Value>::type indexable_type;
+
+    indexable_type const& operator()(Value const& v) const
+    {
+        return detail::extract_indexable<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_indexable<typename Value::value_type>::type indexable_type;
+
+    indexable_type const& operator()(Value const& v) const
+    {
+        return detail::extract_indexable<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_indexable<typename Value::element_type>::type indexable_type;
+
+    indexable_type const& operator()(Value const& v) const
+    {
+        return detail::extract_indexable<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_indexable<Value>::type indexable_type;
+
+    indexable_type const& operator()(const Value *v) const
+    {
+        return detail::extract_indexable<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_new/boost/geometry/extensions/index/translator/helpers.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/helpers.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,192 @@
+// 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>
+
+#include <boost/geometry/extensions/index/indexable.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace translator {
+
+namespace dispatch {
+
+// 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 Geometry>
+struct indexable_not_found_error
+{
+    static const bool value = false;
+};
+template <>
+struct indexable_not_found_error<void>
+{
+    static const bool value = true;
+};
+
+// Extract indexable
+
+template <typename Value>
+struct extract_indexable
+{
+    typedef Value type;
+
+    BOOST_STATIC_ASSERT(!indexable_not_found_error<type>::value);
+
+    static type const& get(Value const& v) { return v; }
+};
+
+template <typename First, typename Second>
+struct extract_indexable< std::pair<First, Second> >
+{
+    typedef typename dispatch::choose_pair_element<
+        std::pair<First, Second>,
+        typename traits::indexable_type<First>::type,
+        typename traits::indexable_type<Second>::type
+    > cp;
+
+    typedef typename cp::type type;
+
+    BOOST_STATIC_ASSERT(!indexable_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_new/boost/geometry/extensions/index/translator/index.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/index.hpp	2011-03-24 19:52:27 EDT (Thu, 24 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_indexable
+        <typename Container::value_type>::type indexable_type;
+
+    explicit index(Container const& c) : m_c(c) {}
+
+    indexable_type const& operator()(size_t i) const
+    {
+        return detail::extract_indexable
+            <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_new/tests/TODO.txt
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/TODO.txt	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,20 @@
+// TODO
+// wewnetrzny typ pudelek zmienic na geometry::box<geometry::point>
+//   do kopiowania pudelek uzytkownik -> internal uzyc specjlnej funkcji
+// przydalaby sie inna struktura wezlow - w tej powielane sa dane
+//   node <- internal_node, node <- leaf_node
+//   traktowanie liscia jako wezla wewnetrznego tez jest bez sensu (nie widze dobrej sytuacji)
+
+// czy translator powinien zwracac geometry::model::point czy Point
+// a jesli zalozymy ze uzytkownik przechowuje Polygon to powinien on byc przechowywany z Boxem czy nie
+// to przechowuje pair<Box, Polygon> lub jesli przechowuje Box pisze sobie nowy translator
+
+// czy wewnatrz struktury powinny byc przechowywane: Box i geometry::box<Point>
+// czy geometry::box<geometry::point<traits::dimension<Point>::value>, ...>
+
+// 1. box wewnatrz wezlow
+// 2. bounding object w lisciach
+
+// 3. jakis automatyczny przechowywacz innych obiektow? polygon, segment
+//   powinien istniec automatyczny translator obiekt -> box
+//   i box/point przechowywany w lisciach razem z obiektem
\ No newline at end of file

Added: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,70 @@
+#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/rtree/visitors/gl_draw.hpp>
+
+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;
+
+void render_scene(void)
+{
+    boost::geometry::index::gl_draw(t);
+}
+
+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 )
+    {
+        float x = ( rand() % 10000 ) / 1000.0f;
+        float y = ( rand() % 10000 ) / 1000.0f;
+        float w = ( rand() % 10000 ) / 100000.0f;
+        float h = ( rand() % 10000 ) / 100000.0f;
+
+        boost::geometry::index::insert(t, B(P(x - w, y - h),P(x + w, y + h)));
+
+        glutPostRedisplay();
+    }
+}
+
+int main(int argc, char **argv)
+{
+    glutInit(&argc, argv);
+    glutInitDisplayMode(GLUT_DEPTH | GLUT_SINGLE | GLUT_RGBA);
+    glutInitWindowPosition(100,100);
+    glutInitWindowSize(800, 600);
+    glutCreateWindow("Mouse click to insert new value");
+
+    glutDisplayFunc(render_scene);
+    glutReshapeFunc(resize);
+    glutMouseFunc(mouse);
+
+    std::cout << "Mouse click to insert new value";
+
+    glutMainLoop();
+
+    return 0;
+}

Added: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,62 @@
+#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>::leaf l;
+        boost::geometry::index::rtree<B>::internal_node n;
+
+        std::cout << "internal node size: " << sizeof(n) << '\n';
+        std::cout << "leaf size: " << sizeof(l) << '\n';        
+    }
+
+    boost::timer tim;
+
+    {
+        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(4, 2);
+
+        std::cout << "inserting time test...\n";
+
+        tim.restart();    
+
+        BOOST_FOREACH(B &b, v)
+        {
+            boost::geometry::index::insert(t, b);
+        }
+
+        std::cout << "time: " << tim.elapsed() << "s\n";
+        
+        std::cout << "deleting time test...\n";
+        tim.restart();
+    }
+    std::cout << "time: " << tim.elapsed() << "s\n";
+
+#ifdef _MSC_VER
+    std::cin.get();
+#endif
+
+    return 0;
+}

Added: sandbox-branches/geometry/index_080_new/tests/main.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/main.cpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,16 @@
+#include <tests/translators.hpp>
+#include <tests/rtree_native.hpp>
+#include <tests/rtree_filters.hpp>
+
+int main()
+{
+    tests_translators_hpp();
+    tests_rtree_native_hpp();
+    tests_rtree_filters_hpp();
+
+#ifdef _MSC_VER
+    std::cin.get();
+#endif
+
+    return 0;
+}

Added: sandbox-branches/geometry/index_080_new/tests/rtree_filters.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/rtree_filters.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,54 @@
+#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(4, 2);
+        boost::geometry::index::insert(t, B(P(0, 0), P(1, 1)));
+        boost::geometry::index::insert(t, B(P(2, 2), P(3, 3)));
+        boost::geometry::index::insert(t, B(P(4, 4), P(5, 5)));
+        boost::geometry::index::insert(t, B(P(6, 6), P(7, 7)));
+        boost::geometry::index::insert(t, B(P(8, 8), P(9, 9)));
+        std::cout << t;
+
+        std::cout << "Query: (2.5, 2.5)x(4.5, 4.5)\n";
+        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))));
+    }
+}
+
+#endif // TESTS_RTREE_FILTERS_HPP

Added: sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp	2011-03-24 19:52:27 EDT (Thu, 24 Mar 2011)
@@ -0,0 +1,150 @@
+#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 <boost/geometry/extensions/index/rtree/visitors/print.hpp>
+
+#include <boost/range/algorithm.hpp>
+#include <boost/foreach.hpp>
+
+#include <map>
+
+void tests_rtree_native_hpp()
+{
+	std::cout << "tests/rtree_native.hpp\n";
+	
+    std::cout << "Boxes\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(4, 2);
+        boost::geometry::index::insert(t, B(P(0, 0), P(1, 1)));
+        boost::geometry::index::insert(t, B(P(2, 2), P(3, 3)));
+        boost::geometry::index::insert(t, B(P(4, 4), P(5, 5)));
+        boost::geometry::index::insert(t, B(P(6, 6), P(7, 7)));
+        boost::geometry::index::insert(t, B(P(8, 8), P(9, 9)));
+        std::cerr << t;
+    }
+
+    std::cout << "-------------------------------------------------\n";
+    std::cout << "-------------------------------------------------\n";
+
+    std::cout << "Points\n";
+    {
+        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(4, 2);
+        boost::geometry::index::insert(t, P(0, 0));
+        boost::geometry::index::insert(t, P(2, 2));
+        boost::geometry::index::insert(t, P(4, 4));
+        boost::geometry::index::insert(t, P(6, 6));
+        boost::geometry::index::insert(t, P(8, 8));
+        std::cerr << t;
+    }
+
+    std::cout << "-------------------------------------------------\n";
+    std::cout << "-------------------------------------------------\n";
+
+    std::cout << "std::pair<Box, int>\n";
+    {
+        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(4, 2);
+        boost::geometry::index::insert(t, V(B(P(0, 0), P(1, 1)), 0));
+        boost::geometry::index::insert(t, V(B(P(2, 2), P(3, 3)), 1));
+        boost::geometry::index::insert(t, V(B(P(4, 4), P(5, 5)), 2));
+        boost::geometry::index::insert(t, V(B(P(6, 6), P(7, 7)), 3));
+        boost::geometry::index::insert(t, V(B(P(8, 8), P(9, 9)), 4));
+        std::cerr << t;
+    }
+
+    std::cout << "-------------------------------------------------\n";
+    std::cout << "-------------------------------------------------\n";
+
+    std::cout << "boost::shared_ptr< std::pair<Box, int> >\n";
+    {
+        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) );
+        V v5( new std::pair<B, int>(B(P(8, 8), P(9, 9)), 4) );
+
+        boost::geometry::index::rtree<V> t(4, 2);
+        boost::geometry::index::insert(t, v1);
+        boost::geometry::index::insert(t, v2);
+        boost::geometry::index::insert(t, v3);
+        boost::geometry::index::insert(t, v4);
+        boost::geometry::index::insert(t, v5);
+        std::cerr << t;
+    }
+
+    std::cout << "-------------------------------------------------\n";
+    std::cout << "-------------------------------------------------\n";
+
+    std::cout << "std::map<int, Box>::iterator\n";
+    {
+        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))));
+        m.insert(std::pair<int, B>(4, B(P(8, 8), P(9, 9))));
+
+        boost::geometry::index::rtree<V> t(4, 2);
+        V vit = m.begin();
+        boost::geometry::index::insert(t, vit++);
+        boost::geometry::index::insert(t, vit++);
+        boost::geometry::index::insert(t, vit++);
+        boost::geometry::index::insert(t, vit++);
+        boost::geometry::index::insert(t, vit);
+        std::cerr << t;
+    }
+
+    std::cout << "-------------------------------------------------\n";
+    std::cout << "-------------------------------------------------\n";
+
+    std::cout << "size_t\n";
+    {
+        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)));
+        v.push_back(B(P(8, 8), P(9, 9)));
+
+        boost::geometry::index::rtree<V, T> t(4, 2, T(v));
+
+        boost::geometry::index::insert(t, 0u);
+        boost::geometry::index::insert(t, 1u);
+        boost::geometry::index::insert(t, 2u);
+        boost::geometry::index::insert(t, 3u);
+        boost::geometry::index::insert(t, 4u);
+        std::cerr << t;
+    }
+}
+
+#endif // TESTS_RTREE_NATIVE_HPP

Added: sandbox-branches/geometry/index_080_new/tests/translators.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/translators.hpp	2011-03-24 19:52:27 EDT (Thu, 24 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