Imported from /home/lorry/working-area/delta_boost-tarball/boost_1_58_0.tar.bz2.HEADboost_1_58_0master

9 files changed, 419 insertions, 15 deletions

diff --git a/libs/geometry/index/example/benchmark_insert.cpp b/libs/geometry/index/example/benchmark_insert.cpp
new file mode 100644
index 000000000..4fe82e91f
--- /dev/null
+++ b/libs/geometry/index/example/benchmark_insert.cpp
@@ -0,0 +1,196 @@
+// Boost.Geometry Index
+// Additional tests
+
+// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
+
+// 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)
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+
+#include <boost/chrono.hpp>
+#include <boost/foreach.hpp>
+#include <boost/random.hpp>
+
+#include <boost/geometry.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/geometries/geometries.hpp>
+
+#include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp>
+#include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
+
+namespace bg = boost::geometry;
+namespace bgi = bg::index;
+
+typedef bg::model::point<double, 2, bg::cs::cartesian> P;
+typedef bg::model::box<P> B;
+typedef bg::model::segment<P> S;
+typedef P V;
+//typedef B V;
+//typedef S V;
+
+template <typename V>
+struct generate_value {};
+
+template <>
+struct generate_value<B>
+{
+    static inline B apply(float x, float y) { return B(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
+};
+
+template <>
+struct generate_value<S>
+{
+    static inline S apply(float x, float y) { return S(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
+};
+
+template <>
+struct generate_value<P>
+{
+    static inline P apply(float x, float y) { return P(x, y); }
+};
+
+template <typename RT>
+void test_queries(RT const& t, std::vector< std::pair<float, float> > const& coords, size_t queries_count)
+{
+    typedef boost::chrono::thread_clock clock_t;
+    typedef boost::chrono::duration<float> dur_t;
+
+    std::vector<V> result;
+    result.reserve(100);
+
+    clock_t::time_point start = clock_t::now();
+    size_t temp = 0;
+    for (size_t i = 0 ; i < queries_count ; ++i )
+    {
+        float x = coords[i].first;
+        float y = coords[i].second;
+        result.clear();
+        t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
+        temp += result.size();
+    }
+    dur_t time = clock_t::now() - start;
+    std::cout << time.count() << " " << temp << '\n';
+}
+
+//#define BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
+
+int main()
+{
+    //typedef bgi::rtree<V, bgi::linear<4, 2> > RT;
+    //typedef bgi::rtree<V, bgi::linear<16, 4> > RT;
+    //typedef bgi::rtree<V, bgi::quadratic<4, 2> > RT;
+    typedef bgi::rtree<V, bgi::rstar<8, 2> > RT;
+
+    typedef boost::chrono::thread_clock clock_t;
+    typedef boost::chrono::duration<float> dur_t;
+
+#ifndef BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
+    size_t values_count = 1000000;
+    size_t queries_count = 100000;
+    size_t nearest_queries_count = 20000;
+    unsigned neighbours_count = 10;
+    size_t max_range_inserts = 10;
+#else
+    size_t values_count = 10000;
+    size_t queries_count = 1000;
+    size_t nearest_queries_count = 100;
+    unsigned neighbours_count = 10;
+    size_t max_range_inserts = 10;
+#endif
+
+    float max_val = static_cast<float>(values_count / 2);
+    std::vector< std::pair<float, float> > coords;
+    std::vector<V> values;
+
+    //randomize values
+    {
+        boost::mt19937 rng;
+        //rng.seed(static_cast<unsigned int>(std::time(0)));
+        boost::uniform_real<float> range(-max_val, max_val);
+        boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
+        coords.reserve(values_count);
+
+        std::cout << "randomizing data\n";
+        for ( size_t i = 0 ; i < values_count ; ++i )
+        {
+            float x = rnd();
+            float y = rnd();
+            coords.push_back(std::make_pair(x, y));
+            values.push_back(generate_value<V>::apply(x, y));
+        }
+        std::cout << "randomized\n";
+    }
+
+    for (;;)
+    {
+        // packing test
+        {
+            clock_t::time_point start = clock_t::now();
+
+            RT t(values.begin(), values.end());
+
+            BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
+            BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
+            BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
+
+            dur_t time = clock_t::now() - start;
+            std::cout << "pack(" << values_count << ") - " << time.count() << ", ";
+
+            test_queries(t, coords, queries_count);
+        }
+
+        {
+            size_t n_per_max = values_count / max_range_inserts;
+
+            for ( size_t j = 0 ; j < max_range_inserts ; ++j )
+            {
+                clock_t::time_point start = clock_t::now();
+
+                RT t;
+
+                // perform j range-inserts
+                for ( size_t i = 0 ; i < j ; ++i )
+                {
+                    t.insert(values.begin() + n_per_max * i,
+                             values.begin() + (std::min)(n_per_max * (i + 1), values_count));
+                }
+
+                if ( !t.empty() )
+                {
+                    BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
+                    BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
+                    BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
+                }
+
+                // perform n-n/max_inserts*j inserts
+                size_t inserted_count = (std::min)(n_per_max*j, values_count);
+                for ( size_t i = inserted_count ; i < values_count ; ++i )
+                {
+                    t.insert(values[i]);
+                }
+
+                if ( !t.empty() )
+                {
+                    BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
+                    BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
+                    BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
+                }
+
+                dur_t time = clock_t::now() - start;
+                std::cout << j << "*insert(N/" << max_range_inserts << ")+insert(" << (values_count - inserted_count) << ") - " << time.count() << ", ";
+
+                test_queries(t, coords, queries_count);
+            }
+        }
+
+        std::cout << "------------------------------------------------\n";
+    }
+
+    return 0;
+}
diff --git a/libs/geometry/index/test/Jamfile.v2 b/libs/geometry/index/test/Jamfile.v2
index c2a192e1c..f19f6834c 100644
--- a/libs/geometry/index/test/Jamfile.v2
+++ b/libs/geometry/index/test/Jamfile.v2
@@ -15,12 +15,15 @@ project boost-geometry-index-test
         <include>../../test     # libs/geometry/test
         #<include>../../../../boost/geometry/extensions/contrib/ttmath
         <toolset>msvc:<asynch-exceptions>on
+        <toolset>msvc:<cxxflags>/bigobj
+        <host-os>windows,<toolset>intel:<cxxflags>/bigobj
+        <library>/boost/timer//boost_timer
     ;
 
 test-suite boost-geometry-index-varray
     :
     [ run varray_old.cpp ]
-    [ run varray.cpp : : : <toolset>msvc:<cxxflags>/bigobj ]
+    [ run varray.cpp ]
     ;
 
 build-project algorithms ;
diff --git a/libs/geometry/index/test/rtree/Jamfile.v2 b/libs/geometry/index/test/rtree/Jamfile.v2
index 463ccb3fa..23578b4e9 100644
--- a/libs/geometry/index/test/rtree/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/Jamfile.v2
@@ -12,6 +12,7 @@ build-project generated ;
 
 test-suite boost-geometry-index-rtree
     :
+    [ run rtree_move_pack.cpp ]
     [ run rtree_values.cpp ]
     [ compile-fail rtree_values_invalid.cpp ]
     ;
diff --git a/libs/geometry/index/test/rtree/exceptions/Jamfile.v2 b/libs/geometry/index/test/rtree/exceptions/Jamfile.v2
index 1728b245b..84855c4fd 100644
--- a/libs/geometry/index/test/rtree/exceptions/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/exceptions/Jamfile.v2
@@ -17,6 +17,7 @@ rule test_all
       :  # test-files
       :  # requirements
         <toolset>msvc:<cxxflags>/bigobj
+        <host-os>windows,<toolset>intel:<cxxflags>/bigobj
       ] ;
    }
 
diff --git a/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp b/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp
index d32c6bcca..4aa0ef750 100644
--- a/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp
+++ b/libs/geometry/index/test/rtree/exceptions/test_throwing_node.hpp
@@ -174,9 +174,13 @@ struct visitor<Value, Parameters, Box, Allocators, node_throwing_static_tag, IsV
 // allocators
 
 template <typename Allocator, typename Value, typename Parameters, typename Box>
-struct allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>
+class allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>
     : public Allocator::template rebind<
-        typename node<Value, Parameters, Box, allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>, node_throwing_static_tag>::type
+        typename node<
+            Value, Parameters, Box,
+            allocators<Allocator, Value, Parameters, Box, node_throwing_static_tag>,
+            node_throwing_static_tag
+        >::type
     >::other
 {
     typedef typename Allocator::template rebind<
diff --git a/libs/geometry/index/test/rtree/generated/Jamfile.v2 b/libs/geometry/index/test/rtree/generated/Jamfile.v2
index f3900741b..a5a6f3e41 100644
--- a/libs/geometry/index/test/rtree/generated/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/generated/Jamfile.v2
@@ -17,6 +17,7 @@ rule test_all
       :  # test-files
       :  # requirements
         <toolset>msvc:<cxxflags>/bigobj
+        <host-os>windows,<toolset>intel:<cxxflags>/bigobj
       ] ;
    }
 
diff --git a/libs/geometry/index/test/rtree/interprocess/Jamfile.v2 b/libs/geometry/index/test/rtree/interprocess/Jamfile.v2
index 9e8a05f2a..1a52eb953 100644
--- a/libs/geometry/index/test/rtree/interprocess/Jamfile.v2
+++ b/libs/geometry/index/test/rtree/interprocess/Jamfile.v2
@@ -23,6 +23,8 @@ rule test_all
         <toolset>gcc,<target-os>windows:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32" 
         <host-os>windows,<toolset>clang:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32"
         <toolset>msvc:<cxxflags>/bigobj
+        <host-os>windows,<toolset>intel:<cxxflags>/bigobj
+        <host-os>linux:<linkflags>"-lrt"
       ] ;
    }
 
diff --git a/libs/geometry/index/test/rtree/rtree_move_pack.cpp b/libs/geometry/index/test/rtree/rtree_move_pack.cpp
new file mode 100644
index 000000000..b7210772d
--- /dev/null
+++ b/libs/geometry/index/test/rtree/rtree_move_pack.cpp
@@ -0,0 +1,134 @@
+// Boost.Geometry Index
+// Unit Test
+
+// Copyright (c) 2015 Adam Wulkiewicz, Lodz, Poland.
+
+// 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)
+
+#include <rtree/test_rtree.hpp>
+
+#include <algorithm>
+#include <boost/container/vector.hpp>
+#include <boost/move/move.hpp>
+#include <boost/move/iterator.hpp>
+
+#include <boost/geometry/geometries/register/point.hpp>
+
+class point_cm
+{
+    BOOST_COPYABLE_AND_MOVABLE(point_cm)
+
+public:
+    point_cm(double xx = 0, double yy = 0)
+        : x(xx)
+        , y(yy)
+        , moved(false)
+    {}
+    point_cm(point_cm const& other)
+        : x(other.x)
+        , y(other.y)
+        , moved(false)
+    {
+        BOOST_CHECK_MESSAGE(false, "copy not allowed");
+    }
+    point_cm & operator=(BOOST_COPY_ASSIGN_REF(point_cm) other)
+    {
+        BOOST_CHECK_MESSAGE(false, "copy not allowed");
+        x = other.x;
+        y = other.y;
+        moved = false;
+        return *this;
+    }
+    point_cm(BOOST_RV_REF(point_cm) other)
+        : x(other.x)
+        , y(other.y)
+        , moved(false)
+    {
+        BOOST_CHECK_MESSAGE(!other.moved, "only one move allowed");
+        other.moved = true;
+    }
+    point_cm & operator=(BOOST_RV_REF(point_cm) other)
+    {
+        BOOST_CHECK_MESSAGE(!other.moved, "only one move allowed");
+        x = other.x;
+        y = other.y;
+        moved = false;
+        other.moved = true;
+        return *this;
+    }
+
+    double x, y;
+    bool moved;
+};
+
+template <typename Point>
+struct indexable
+{
+    typedef Point const& result_type;
+    result_type operator()(Point const& p) const
+    {
+        BOOST_CHECK_MESSAGE(!p.moved, "can't access indexable of moved Value");
+        return p;
+    }
+};
+
+BOOST_GEOMETRY_REGISTER_POINT_2D(point_cm, double, bg::cs::cartesian, x, y)
+
+template <typename Vector>
+void append(Vector & vec, double x, double y)
+{
+    point_cm pt(x, y);
+    BOOST_CHECK(!pt.moved);
+    vec.push_back(boost::move(pt));
+    BOOST_CHECK(pt.moved);
+}
+
+struct test_moved
+{
+    test_moved(bool ex)
+        : expected(ex)
+    {}
+    template <typename Point>
+    void operator()(Point const& p) const
+    {
+        BOOST_CHECK_EQUAL(p.moved, expected);
+    }
+    bool expected;
+};
+
+template <typename Point, typename Params>
+void test_rtree(Params const& params = Params())
+{
+    // sanity check
+    boost::container::vector<Point> vec;
+    append(vec, 0, 0); append(vec, 0, 1); append(vec, 0, 2);
+    append(vec, 1, 0); append(vec, 1, 1); append(vec, 1, 2);
+    append(vec, 2, 0); append(vec, 2, 1); append(vec, 2, 2);
+
+    std::for_each(vec.begin(), vec.end(), test_moved(false));
+
+    bgi::rtree<Point, Params, indexable<Point> > rt(
+        boost::make_move_iterator(vec.begin()),
+        boost::make_move_iterator(vec.end()),
+        params);
+
+    std::for_each(vec.begin(), vec.end(), test_moved(true));
+
+    BOOST_CHECK_EQUAL(rt.size(), vec.size());
+}
+
+
+int test_main(int, char* [])
+{
+    test_rtree< point_cm, bgi::linear<4> >();
+    test_rtree< point_cm, bgi::quadratic<4> >();
+    test_rtree< point_cm, bgi::rstar<4> >();
+
+    test_rtree<point_cm>(bgi::dynamic_linear(4));
+    test_rtree<point_cm>(bgi::dynamic_quadratic(4));
+    test_rtree<point_cm>(bgi::dynamic_rstar(4));
+
+    return 0;
+}
diff --git a/libs/geometry/index/test/rtree/rtree_values.cpp b/libs/geometry/index/test/rtree/rtree_values.cpp
index 2a9c3a0dd..e9eb13810 100644
--- a/libs/geometry/index/test/rtree/rtree_values.cpp
+++ b/libs/geometry/index/test/rtree/rtree_values.cpp
@@ -1,7 +1,7 @@
 // Boost.Geometry Index
 // Unit Test
 
-// Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
+// Copyright (c) 2014-2015 Adam Wulkiewicz, Lodz, Poland.
 
 // Use, modification and distribution is subject to the Boost Software License,
 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -9,8 +9,10 @@
 
 #include <rtree/test_rtree.hpp>
 
+#include <boost/core/addressof.hpp>
 
 #include <boost/geometry/geometries/register/point.hpp>
+#include <boost/geometry/geometries/polygon.hpp>
 
 struct point
 {
@@ -20,6 +22,30 @@ struct point
 
 BOOST_GEOMETRY_REGISTER_POINT_2D(point, double, bg::cs::cartesian, x, y)
 
+template <typename Rtree, typename Convertible>
+void check_convertible_to_value(Rtree const& rt, Convertible const& conv)
+{
+    static const bool
+        is_conv_to_indexable
+            = boost::is_convertible<Convertible, typename Rtree::indexable_type>::value;
+    static const bool
+        is_conv_to_value
+            = boost::is_convertible<Convertible, typename Rtree::value_type>::value;
+    static const bool
+        is_same_as_indexable
+            = boost::is_same<Convertible, typename Rtree::indexable_type>::value;
+    static const bool
+        is_same_as_value
+            = boost::is_same<Convertible, typename Rtree::value_type>::value;
+
+    BOOST_CHECK_EQUAL(is_same_as_indexable, false);
+    BOOST_CHECK_EQUAL(is_same_as_value, false);
+    BOOST_CHECK_EQUAL(is_conv_to_indexable, false);
+    BOOST_CHECK_EQUAL(is_conv_to_value, true);
+
+    typename Rtree::value_type const& val = conv;
+    BOOST_CHECK(rt.value_eq()(val, conv));
+}
 
 template <typename Box, typename Params>
 void test_pair()
@@ -41,17 +67,49 @@ void test_pair()
     rt.insert(val);
     rt.insert(std::make_pair(box, 0));
     rt.insert(std::make_pair(box, (unsigned short)0));
-    BOOST_CHECK( rt.size() == 3 );
+    BOOST_CHECK_EQUAL(rt.size(), 3u);
+
+    check_convertible_to_value(rt, std::make_pair(box, 0));
+    check_convertible_to_value(rt, std::make_pair(box, (unsigned short)0));
+    BOOST_CHECK(bg::covered_by(rt.indexable_get()(std::make_pair(box, 0)), rt.bounds()));
+    BOOST_CHECK(bg::covered_by(rt.indexable_get()(std::make_pair(box, (unsigned short)0)), rt.bounds()));
+
+    BOOST_CHECK_EQUAL(rt.count(val), 3u);
+    BOOST_CHECK_EQUAL(rt.count(std::make_pair(box, 0)), 3u);
+    BOOST_CHECK_EQUAL(rt.count(std::make_pair(box, (unsigned short)0)), 3u);
+    BOOST_CHECK_EQUAL(rt.count(box), 3u);
+
+    BOOST_CHECK_EQUAL(rt.remove(val), 1u);
+    BOOST_CHECK_EQUAL(rt.remove(std::make_pair(box, 0)), 1u);
+    BOOST_CHECK_EQUAL(rt.remove(std::make_pair(box, (unsigned short)0)), 1u);
+    BOOST_CHECK_EQUAL(rt.size(), 0u);
+}
 
-    BOOST_CHECK( rt.count(val) == 3 );
-    BOOST_CHECK( rt.count(std::make_pair(box, 0)) == 3 );
-    BOOST_CHECK( rt.count(std::make_pair(box, (unsigned short)0)) == 3 );
-    BOOST_CHECK( rt.count(box) == 3 );
+template <typename Box, typename Params>
+void test_pair_geom_ptr()
+{
+    typedef typename bg::point_type<Box>::type point_t;
+    typedef bg::model::polygon<point_t> polygon_t;
+
+    typedef std::pair<Box, polygon_t*> Value;
+
+    typename boost::remove_const<Box>::type box;
+    bg::assign_zero(box);
 
-    BOOST_CHECK( rt.remove(val) == 1 );
-    BOOST_CHECK( rt.remove(std::make_pair(box, 0)) == 1 );
-    BOOST_CHECK( rt.remove(std::make_pair(box, (unsigned short)0)) == 1 );
-    BOOST_CHECK( rt.size() == 0 );
+    polygon_t poly;
+
+    Value val(box, boost::addressof(poly));
+
+    bgi::rtree<Value, Params> rt;
+    rt.insert(val);
+    rt.insert(std::make_pair(box, boost::addressof(poly)));
+
+    BOOST_CHECK_EQUAL(rt.size(), 2u);
+
+    BOOST_CHECK_EQUAL(rt.remove(val), 1u);
+    BOOST_CHECK_EQUAL(rt.remove(std::make_pair(box, boost::addressof(poly))), 1u);
+
+    BOOST_CHECK_EQUAL(rt.size(), 0u);
 }
 
 template <typename Params>
@@ -60,8 +118,8 @@ void test_point()
     bgi::rtree<point, Params> rt;
     
     rt.insert(0.0);
-    BOOST_CHECK( rt.size() == 1 );
-    BOOST_CHECK( rt.remove(0.0) == 1 );
+    BOOST_CHECK_EQUAL(rt.size(), 1u);
+    BOOST_CHECK_EQUAL(rt.remove(0.0), 1u);
 }
 
 int test_main(int, char* [])
@@ -76,6 +134,10 @@ int test_main(int, char* [])
     //test_rtree< Box const, bgi::quadratic<4> >();
     //test_rtree< Box const, bgi::rstar<4> >();
 
+    test_pair_geom_ptr< Box, bgi::linear<16> >();
+    test_pair_geom_ptr< Box, bgi::quadratic<4> >();
+    test_pair_geom_ptr< Box, bgi::rstar<4> >();
+
     test_point< bgi::linear<16> >();
     test_point< bgi::quadratic<4> >();
     test_point< bgi::rstar<4> >();