diff options
Diffstat (limited to 'boost/geometry/index')
34 files changed, 578 insertions, 647 deletions
diff --git a/boost/geometry/index/detail/algorithms/is_valid.hpp b/boost/geometry/index/detail/algorithms/is_valid.hpp index d85ac56d69..676eec2d2a 100644 --- a/boost/geometry/index/detail/algorithms/is_valid.hpp +++ b/boost/geometry/index/detail/algorithms/is_valid.hpp @@ -80,6 +80,9 @@ struct is_valid<Indexable, segment_tag> template <typename Indexable> inline bool is_valid(Indexable const& b) { + // CONSIDER: detection of NaNs + // e.g. by comparison of b with copy of b + return dispatch::is_valid<Indexable>::apply(b); } diff --git a/boost/geometry/index/detail/assert.hpp b/boost/geometry/index/detail/assert.hpp index 22af315bc8..311f37f640 100644 --- a/boost/geometry/index/detail/assert.hpp +++ b/boost/geometry/index/detail/assert.hpp @@ -1,6 +1,6 @@ // Boost.Geometry Index // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2014 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 @@ -11,20 +11,11 @@ #include <boost/assert.hpp> +#ifndef BOOST_GEOMETRY_INDEX_ASSERT + #define BOOST_GEOMETRY_INDEX_ASSERT(CONDITION, TEXT_MSG) \ BOOST_ASSERT_MSG(CONDITION, TEXT_MSG) -// TODO - change it to something like: -// BOOST_ASSERT((CONDITION) && (TEXT_MSG)) - -#if defined(BOOST_DISABLE_ASSERTS) || defined(NDEBUG) - -#define BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(PARAM) - -#else - -#define BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(PARAM) PARAM - -#endif +#endif // BOOST_GEOMETRY_INDEX_ASSERT #endif // BOOST_GEOMETRY_INDEX_DETAIL_ASSERT_HPP diff --git a/boost/geometry/index/detail/bounded_view.hpp b/boost/geometry/index/detail/bounded_view.hpp index 572368e273..0cd882fc94 100644 --- a/boost/geometry/index/detail/bounded_view.hpp +++ b/boost/geometry/index/detail/bounded_view.hpp @@ -155,7 +155,7 @@ struct indexed_access<index::detail::bounded_view<Segment, Box, Tag, box_tag>, //static inline void set(box_type & b, coordinate_type const& value) //{ - // BOOST_ASSERT(false); + // BOOST_GEOMETRY_INDEX_ASSERT(false, "unable to modify a box through view"); //} }; @@ -173,7 +173,7 @@ struct indexed_access<index::detail::bounded_view<Segment, Box, Tag, box_tag>, //static inline void set(box_type & b, coordinate_type const& value) //{ - // BOOST_ASSERT(false); + // BOOST_GEOMETRY_INDEX_ASSERT(false, "unable to modify a box through view"); //} }; diff --git a/boost/geometry/index/detail/distance_predicates.hpp b/boost/geometry/index/detail/distance_predicates.hpp index 3e057290a6..9a9371df95 100644 --- a/boost/geometry/index/detail/distance_predicates.hpp +++ b/boost/geometry/index/detail/distance_predicates.hpp @@ -3,7 +3,7 @@ // Spatial index distance predicates, calculators and checkers // used in nearest query - specialized for envelopes // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -104,13 +104,13 @@ struct calculate_distance // this handles nearest() with default Point parameter, to_nearest() and bounds template <typename PointRelation, typename Indexable, typename Tag> -struct calculate_distance< nearest<PointRelation>, Indexable, Tag > +struct calculate_distance< predicates::nearest<PointRelation>, Indexable, Tag > { typedef detail::relation<PointRelation> relation; typedef typename relation::value_type point_type; typedef typename geometry::default_comparable_distance_result<point_type, Indexable>::type result_type; - static inline bool apply(nearest<PointRelation> const& p, Indexable const& i, result_type & result) + static inline bool apply(predicates::nearest<PointRelation> const& p, Indexable const& i, result_type & result) { result = geometry::comparable_distance(relation::value(p.point_or_relation), i); return true; @@ -118,12 +118,12 @@ struct calculate_distance< nearest<PointRelation>, Indexable, Tag > }; template <typename Point, typename Indexable> -struct calculate_distance< nearest< to_centroid<Point> >, Indexable, value_tag> +struct calculate_distance< predicates::nearest< to_centroid<Point> >, Indexable, value_tag> { typedef Point point_type; typedef typename geometry::default_comparable_distance_result<point_type, Indexable>::type result_type; - static inline bool apply(nearest< to_centroid<Point> > const& p, Indexable const& i, result_type & result) + static inline bool apply(predicates::nearest< to_centroid<Point> > const& p, Indexable const& i, result_type & result) { result = index::detail::comparable_distance_centroid(p.point_or_relation.value, i); return true; @@ -131,12 +131,12 @@ struct calculate_distance< nearest< to_centroid<Point> >, Indexable, value_tag> }; template <typename Point, typename Indexable> -struct calculate_distance< nearest< to_furthest<Point> >, Indexable, value_tag> +struct calculate_distance< predicates::nearest< to_furthest<Point> >, Indexable, value_tag> { typedef Point point_type; typedef typename geometry::default_comparable_distance_result<point_type, Indexable>::type result_type; - static inline bool apply(nearest< to_furthest<Point> > const& p, Indexable const& i, result_type & result) + static inline bool apply(predicates::nearest< to_furthest<Point> > const& p, Indexable const& i, result_type & result) { result = index::detail::comparable_distance_far(p.point_or_relation.value, i); return true; @@ -144,13 +144,13 @@ struct calculate_distance< nearest< to_furthest<Point> >, Indexable, value_tag> }; template <typename SegmentOrLinestring, typename Indexable, typename Tag> -struct calculate_distance< path<SegmentOrLinestring>, Indexable, Tag> +struct calculate_distance< predicates::path<SegmentOrLinestring>, Indexable, Tag> { typedef typename index::detail::default_path_intersection_distance_type< Indexable, SegmentOrLinestring >::type result_type; - static inline bool apply(path<SegmentOrLinestring> const& p, Indexable const& i, result_type & result) + static inline bool apply(predicates::path<SegmentOrLinestring> const& p, Indexable const& i, result_type & result) { return index::detail::path_intersection(i, p.geometry, result); } diff --git a/boost/geometry/index/detail/exception.hpp b/boost/geometry/index/detail/exception.hpp index c3ea0e1923..e2090533e7 100644 --- a/boost/geometry/index/detail/exception.hpp +++ b/boost/geometry/index/detail/exception.hpp @@ -1,6 +1,6 @@ // Boost.Geometry Index // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2014 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,10 +9,14 @@ #ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXCEPTION_HPP #define BOOST_GEOMETRY_INDEX_DETAIL_EXCEPTION_HPP +#include <boost/core/no_exceptions_support.hpp> + #ifndef BOOST_NO_EXCEPTIONS #include <stdexcept> +#include <boost/throw_exception.hpp> #else #include <cstdlib> +#include <boost/geometry/index/detail/assert.hpp> #endif namespace boost { namespace geometry { namespace index { namespace detail { @@ -21,47 +25,58 @@ namespace boost { namespace geometry { namespace index { namespace detail { inline void throw_runtime_error(const char * str) { - throw std::runtime_error(str); + BOOST_THROW_EXCEPTION(std::runtime_error(str)); } inline void throw_logic_error(const char * str) { - throw std::logic_error(str); + BOOST_THROW_EXCEPTION(std::logic_error(str)); } inline void throw_invalid_argument(const char * str) { - throw std::invalid_argument(str); + BOOST_THROW_EXCEPTION(std::invalid_argument(str)); } inline void throw_length_error(const char * str) { - throw std::length_error(str); + BOOST_THROW_EXCEPTION(std::length_error(str)); +} + +inline void throw_out_of_range(const char * str) +{ + BOOST_THROW_EXCEPTION(std::out_of_range(str)); } #else inline void throw_runtime_error(const char * str) { - BOOST_ASSERT_MSG(!"runtime_error thrown", str); + BOOST_GEOMETRY_INDEX_ASSERT(!"runtime_error thrown", str); std::abort(); } inline void throw_logic_error(const char * str) { - BOOST_ASSERT_MSG(!"logic_error thrown", str); + BOOST_GEOMETRY_INDEX_ASSERT(!"logic_error thrown", str); std::abort(); } inline void throw_invalid_argument(const char * str) { - BOOST_ASSERT_MSG(!"invalid_argument thrown", str); + BOOST_GEOMETRY_INDEX_ASSERT(!"invalid_argument thrown", str); std::abort(); } inline void throw_length_error(const char * str) { - BOOST_ASSERT_MSG(!"length_error thrown", str); + BOOST_GEOMETRY_INDEX_ASSERT(!"length_error thrown", str); + std::abort(); +} + +inline void throw_out_of_range(const char * str) +{ + BOOST_GEOMETRY_INDEX_ASSERT(!"out_of_range thrown", str); std::abort(); } diff --git a/boost/geometry/index/detail/predicates.hpp b/boost/geometry/index/detail/predicates.hpp index b92256649a..60f80207d8 100644 --- a/boost/geometry/index/detail/predicates.hpp +++ b/boost/geometry/index/detail/predicates.hpp @@ -2,7 +2,7 @@ // // Spatial query predicates definition and checks. // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -16,6 +16,8 @@ namespace boost { namespace geometry { namespace index { namespace detail { +namespace predicates { + // ------------------------------------------------------------------ // // predicates // ------------------------------------------------------------------ // @@ -92,6 +94,8 @@ struct path unsigned count; }; +} // namespace predicates + // ------------------------------------------------------------------ // // predicate_check // ------------------------------------------------------------------ // @@ -108,20 +112,20 @@ struct predicate_check // ------------------------------------------------------------------ // template <typename Fun> -struct predicate_check<satisfies<Fun, false>, value_tag> +struct predicate_check<predicates::satisfies<Fun, false>, value_tag> { template <typename Value, typename Indexable> - static inline bool apply(satisfies<Fun, false> const& p, Value const& v, Indexable const&) + static inline bool apply(predicates::satisfies<Fun, false> const& p, Value const& v, Indexable const&) { return p.fun(v); } }; template <typename Fun> -struct predicate_check<satisfies<Fun, true>, value_tag> +struct predicate_check<predicates::satisfies<Fun, true>, value_tag> { template <typename Value, typename Indexable> - static inline bool apply(satisfies<Fun, true> const& p, Value const& v, Indexable const&) + static inline bool apply(predicates::satisfies<Fun, true> const& p, Value const& v, Indexable const&) { return !p.fun(v); } @@ -136,7 +140,7 @@ struct spatial_predicate_call }; template <> -struct spatial_predicate_call<contains_tag> +struct spatial_predicate_call<predicates::contains_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -146,7 +150,7 @@ struct spatial_predicate_call<contains_tag> }; template <> -struct spatial_predicate_call<covered_by_tag> +struct spatial_predicate_call<predicates::covered_by_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -156,7 +160,7 @@ struct spatial_predicate_call<covered_by_tag> }; template <> -struct spatial_predicate_call<covers_tag> +struct spatial_predicate_call<predicates::covers_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -166,7 +170,7 @@ struct spatial_predicate_call<covers_tag> }; template <> -struct spatial_predicate_call<disjoint_tag> +struct spatial_predicate_call<predicates::disjoint_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -176,7 +180,7 @@ struct spatial_predicate_call<disjoint_tag> }; template <> -struct spatial_predicate_call<intersects_tag> +struct spatial_predicate_call<predicates::intersects_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -186,7 +190,7 @@ struct spatial_predicate_call<intersects_tag> }; template <> -struct spatial_predicate_call<overlaps_tag> +struct spatial_predicate_call<predicates::overlaps_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -196,7 +200,7 @@ struct spatial_predicate_call<overlaps_tag> }; template <> -struct spatial_predicate_call<touches_tag> +struct spatial_predicate_call<predicates::touches_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -206,7 +210,7 @@ struct spatial_predicate_call<touches_tag> }; template <> -struct spatial_predicate_call<within_tag> +struct spatial_predicate_call<predicates::within_tag> { template <typename G1, typename G2> static inline bool apply(G1 const& g1, G2 const& g2) @@ -219,9 +223,9 @@ struct spatial_predicate_call<within_tag> // spatial predicate template <typename Geometry, typename Tag> -struct predicate_check<spatial_predicate<Geometry, Tag, false>, value_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, Tag, false>, value_tag> { - typedef spatial_predicate<Geometry, Tag, false> Pred; + typedef predicates::spatial_predicate<Geometry, Tag, false> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) @@ -232,9 +236,9 @@ struct predicate_check<spatial_predicate<Geometry, Tag, false>, value_tag> // negated spatial predicate template <typename Geometry, typename Tag> -struct predicate_check<spatial_predicate<Geometry, Tag, true>, value_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, Tag, true>, value_tag> { - typedef spatial_predicate<Geometry, Tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, Tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) @@ -246,20 +250,20 @@ struct predicate_check<spatial_predicate<Geometry, Tag, true>, value_tag> // ------------------------------------------------------------------ // template <typename DistancePredicates> -struct predicate_check<nearest<DistancePredicates>, value_tag> +struct predicate_check<predicates::nearest<DistancePredicates>, value_tag> { template <typename Value, typename Box> - static inline bool apply(nearest<DistancePredicates> const&, Value const&, Box const&) + static inline bool apply(predicates::nearest<DistancePredicates> const&, Value const&, Box const&) { return true; } }; template <typename Linestring> -struct predicate_check<path<Linestring>, value_tag> +struct predicate_check<predicates::path<Linestring>, value_tag> { template <typename Value, typename Box> - static inline bool apply(path<Linestring> const&, Value const&, Box const&) + static inline bool apply(predicates::path<Linestring> const&, Value const&, Box const&) { return true; } @@ -270,10 +274,10 @@ struct predicate_check<path<Linestring>, value_tag> // ------------------------------------------------------------------ // template <typename Fun, bool Negated> -struct predicate_check<satisfies<Fun, Negated>, bounds_tag> +struct predicate_check<predicates::satisfies<Fun, Negated>, bounds_tag> { template <typename Value, typename Box> - static bool apply(satisfies<Fun, Negated> const&, Value const&, Box const&) + static bool apply(predicates::satisfies<Fun, Negated> const&, Value const&, Box const&) { return true; } @@ -295,53 +299,53 @@ struct predicate_check<satisfies<Fun, Negated>, bounds_tag> // spatial predicate - default template <typename Geometry, typename Tag> -struct predicate_check<spatial_predicate<Geometry, Tag, false>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, Tag, false>, bounds_tag> { - typedef spatial_predicate<Geometry, Tag, false> Pred; + typedef predicates::spatial_predicate<Geometry, Tag, false> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return spatial_predicate_call<intersects_tag>::apply(i, p.geometry); + return spatial_predicate_call<predicates::intersects_tag>::apply(i, p.geometry); } }; // spatial predicate - contains template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, contains_tag, false>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::contains_tag, false>, bounds_tag> { - typedef spatial_predicate<Geometry, contains_tag, false> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::contains_tag, false> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return spatial_predicate_call<contains_tag>::apply(i, p.geometry); + return spatial_predicate_call<predicates::contains_tag>::apply(i, p.geometry); } }; // spatial predicate - covers template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, covers_tag, false>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::covers_tag, false>, bounds_tag> { - typedef spatial_predicate<Geometry, covers_tag, false> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::covers_tag, false> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return spatial_predicate_call<covers_tag>::apply(i, p.geometry); + return spatial_predicate_call<predicates::covers_tag>::apply(i, p.geometry); } }; // spatial predicate - disjoint template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, disjoint_tag, false>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::disjoint_tag, false>, bounds_tag> { - typedef spatial_predicate<Geometry, disjoint_tag, false> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::disjoint_tag, false> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return !spatial_predicate_call<covered_by_tag>::apply(i, p.geometry); + return !spatial_predicate_call<predicates::covered_by_tag>::apply(i, p.geometry); } }; @@ -359,9 +363,9 @@ struct predicate_check<spatial_predicate<Geometry, disjoint_tag, false>, bounds_ // negated spatial predicate - default template <typename Geometry, typename Tag> -struct predicate_check<spatial_predicate<Geometry, Tag, true>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, Tag, true>, bounds_tag> { - typedef spatial_predicate<Geometry, Tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, Tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) @@ -372,9 +376,9 @@ struct predicate_check<spatial_predicate<Geometry, Tag, true>, bounds_tag> // negated spatial predicate - contains template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, contains_tag, true>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::contains_tag, true>, bounds_tag> { - typedef spatial_predicate<Geometry, contains_tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::contains_tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& , Value const&, Indexable const& ) @@ -385,9 +389,9 @@ struct predicate_check<spatial_predicate<Geometry, contains_tag, true>, bounds_t // negated spatial predicate - covers template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, covers_tag, true>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::covers_tag, true>, bounds_tag> { - typedef spatial_predicate<Geometry, covers_tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::covers_tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& , Value const&, Indexable const& ) @@ -398,22 +402,22 @@ struct predicate_check<spatial_predicate<Geometry, covers_tag, true>, bounds_tag // negated spatial predicate - intersects template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, intersects_tag, true>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::intersects_tag, true>, bounds_tag> { - typedef spatial_predicate<Geometry, intersects_tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::intersects_tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return !spatial_predicate_call<covered_by_tag>::apply(i, p.geometry); + return !spatial_predicate_call<predicates::covered_by_tag>::apply(i, p.geometry); } }; // negated spatial predicate - overlaps template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, overlaps_tag, true>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::overlaps_tag, true>, bounds_tag> { - typedef spatial_predicate<Geometry, overlaps_tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::overlaps_tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& , Value const&, Indexable const& ) @@ -424,34 +428,34 @@ struct predicate_check<spatial_predicate<Geometry, overlaps_tag, true>, bounds_t // negated spatial predicate - touches template <typename Geometry> -struct predicate_check<spatial_predicate<Geometry, touches_tag, true>, bounds_tag> +struct predicate_check<predicates::spatial_predicate<Geometry, predicates::touches_tag, true>, bounds_tag> { - typedef spatial_predicate<Geometry, touches_tag, true> Pred; + typedef predicates::spatial_predicate<Geometry, predicates::touches_tag, true> Pred; template <typename Value, typename Indexable> static inline bool apply(Pred const& p, Value const&, Indexable const& i) { - return !spatial_predicate_call<intersects_tag>::apply(i, p.geometry); + return !spatial_predicate_call<predicates::intersects_tag>::apply(i, p.geometry); } }; // ------------------------------------------------------------------ // template <typename DistancePredicates> -struct predicate_check<nearest<DistancePredicates>, bounds_tag> +struct predicate_check<predicates::nearest<DistancePredicates>, bounds_tag> { template <typename Value, typename Box> - static inline bool apply(nearest<DistancePredicates> const&, Value const&, Box const&) + static inline bool apply(predicates::nearest<DistancePredicates> const&, Value const&, Box const&) { return true; } }; template <typename Linestring> -struct predicate_check<path<Linestring>, bounds_tag> +struct predicate_check<predicates::path<Linestring>, bounds_tag> { template <typename Value, typename Box> - static inline bool apply(path<Linestring> const&, Value const&, Box const&) + static inline bool apply(predicates::path<Linestring> const&, Value const&, Box const&) { return true; } @@ -697,13 +701,13 @@ struct predicates_is_distance }; template <typename DistancePredicates> -struct predicates_is_distance< nearest<DistancePredicates> > +struct predicates_is_distance< predicates::nearest<DistancePredicates> > { static const unsigned value = 1; }; template <typename Linestring> -struct predicates_is_distance< path<Linestring> > +struct predicates_is_distance< predicates::path<Linestring> > { static const unsigned value = 1; }; diff --git a/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp b/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp index 05a64c7b72..a10b046c0d 100644 --- a/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp +++ b/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp @@ -149,7 +149,7 @@ struct find_greatest_normalized_separation // highest_low - lowest_high separation = difference<separation_type>(lowest_high, highest_low); - // BOOST_ASSERT(0 <= width); + // BOOST_GEOMETRY_INDEX_ASSERT(0 <= width); if ( std::numeric_limits<coordinate_type>::epsilon() < width ) separation /= width; diff --git a/boost/geometry/index/detail/rtree/node/auto_deallocator.hpp b/boost/geometry/index/detail/rtree/node/auto_deallocator.hpp deleted file mode 100644 index dd55c6d76c..0000000000 --- a/boost/geometry/index/detail/rtree/node/auto_deallocator.hpp +++ /dev/null @@ -1,38 +0,0 @@ -// Boost.Geometry Index -// -// R-tree auto deallocator -// -// Copyright (c) 2011-2013 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) - -#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_AUTO_DEALLOCATOR_HPP -#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_AUTO_DEALLOCATOR_HPP - -namespace boost { namespace geometry { namespace index { - -namespace detail { namespace rtree { - -template <typename Alloc> -class auto_deallocator -{ - auto_deallocator(auto_deallocator const&); - auto_deallocator & operator=(auto_deallocator const&); -public: - typedef typename Alloc::pointer pointer; - inline auto_deallocator(Alloc & a, pointer p) : m_alloc(a), m_ptr(p) {} - inline ~auto_deallocator() { if ( m_ptr ) boost::container::allocator_traits<Alloc>::deallocate(m_alloc, m_ptr, 1); } - inline void release() { m_ptr = 0; } - inline pointer ptr() { return m_ptr; } -private: - Alloc & m_alloc; - pointer m_ptr; -}; - -}} // namespace detail::rtree - -}}} // namespace boost::geometry::index - -#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_AUTO_DEALLOCATOR_HPP diff --git a/boost/geometry/index/detail/rtree/node/dynamic_visitor.hpp b/boost/geometry/index/detail/rtree/node/dynamic_visitor.hpp deleted file mode 100644 index 43dff56bcb..0000000000 --- a/boost/geometry/index/detail/rtree/node/dynamic_visitor.hpp +++ /dev/null @@ -1,67 +0,0 @@ -// Boost.Geometry Index -// -// R-tree nodes weak visitor and nodes base type -// -// Copyright (c) 2011-2014 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) - -#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_WEAK_VISITOR_HPP -#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_WEAK_VISITOR_HPP - -namespace boost { namespace geometry { namespace index { - -namespace detail { namespace rtree { - -// empty visitor -template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag, bool IsVisitableConst> -struct weak_visitor {}; - -// node - -template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> -struct weak_node {}; - -// nodes variants forward declarations - -template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> -struct weak_internal_node; - -template <typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> -struct weak_leaf; - -// nodes conversion - -template <typename Derived, typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> -inline Derived & get(weak_node<Value, Parameters, Box, Allocators, Tag> & n) -{ - return static_cast<Derived&>(n); -} - -// apply visitor - -template <typename Visitor, typename Value, typename Parameters, typename Box, typename Allocators, typename Tag> -inline void apply_visitor(Visitor & v, - raw_node<Value, Parameters, Box, Allocators, Tag> & n, - bool is_internal_node) -{ - BOOST_GEOMETRY_INDEX_ASSERT(&n, "null ptr"); - if ( is_internal_node ) - { - typedef raw_internal_node<Value, Parameters, Box, Allocators, Tag> internal_node; - v(get<internal_node>(n)); - } - else - { - typedef raw_leaf<Value, Parameters, Box, Allocators, Tag> leaf; - v(get<leaf>(n)); - } -} - -}} // namespace detail::rtree - -}}} // namespace boost::geometry::index - -#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_DYNAMIC_VISITOR_HPP diff --git a/boost/geometry/index/detail/rtree/node/node.hpp b/boost/geometry/index/detail/rtree/node/node.hpp index a632ece66a..528d473170 100644 --- a/boost/geometry/index/detail/rtree/node/node.hpp +++ b/boost/geometry/index/detail/rtree/node/node.hpp @@ -2,7 +2,7 @@ // // R-tree nodes // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -16,8 +16,8 @@ #include <boost/geometry/index/detail/rtree/node/concept.hpp> #include <boost/geometry/index/detail/rtree/node/pairs.hpp> -#include <boost/geometry/index/detail/rtree/node/auto_deallocator.hpp> #include <boost/geometry/index/detail/rtree/node/node_elements.hpp> +#include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp> //#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp> //#include <boost/geometry/index/detail/rtree/node/weak_dynamic.hpp> @@ -27,7 +27,7 @@ #include <boost/geometry/index/detail/rtree/node/variant_dynamic.hpp> #include <boost/geometry/index/detail/rtree/node/variant_static.hpp> -#include <boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp> +#include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp> #include <boost/geometry/algorithms/expand.hpp> @@ -70,11 +70,11 @@ struct destroy_element typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; inline static void apply(typename internal_node::elements_type::value_type & element, Allocators & allocators) { - node_auto_ptr dummy(element.second, allocators); + subtree_destroyer dummy(element.second, allocators); element.second = 0; } @@ -108,11 +108,11 @@ private: inline static void apply_dispatch(It first, It last, Allocators & allocators, boost::mpl::bool_<false> const& /*is_range_of_values*/) { - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; for ( ; first != last ; ++first ) { - node_auto_ptr dummy(first->second, allocators); + subtree_destroyer dummy(first->second, allocators); first->second = 0; } } diff --git a/boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp b/boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp new file mode 100644 index 0000000000..2d08d89ef7 --- /dev/null +++ b/boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp @@ -0,0 +1,48 @@ +// Boost.Geometry Index +// +// R-tree scoped deallocator +// +// 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) + +#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_SCOPED_DEALLOCATOR_HPP +#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_SCOPED_DEALLOCATOR_HPP + +namespace boost { namespace geometry { namespace index { + +namespace detail { namespace rtree { + +template <typename Alloc> +class scoped_deallocator +{ + scoped_deallocator(scoped_deallocator const&); + scoped_deallocator & operator=(scoped_deallocator const&); +public: + typedef typename Alloc::pointer pointer; + inline scoped_deallocator(pointer p, Alloc & a) + : m_ptr(p), m_alloc(a) + {} + inline ~scoped_deallocator() + { + if ( m_ptr ) + { + boost::container::allocator_traits<Alloc>::deallocate(m_alloc, m_ptr, 1); + } + } + inline void release() + { + m_ptr = 0; + } +private: + pointer m_ptr; + Alloc & m_alloc; +}; + +}} // namespace detail::rtree + +}}} // namespace boost::geometry::index + +#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_SCOPED_DEALLOCATOR_HPP diff --git a/boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp b/boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp index c19e123b62..3376068eed 100644 --- a/boost/geometry/index/detail/rtree/node/node_auto_ptr.hpp +++ b/boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp @@ -1,15 +1,15 @@ // Boost.Geometry Index // -// R-tree node auto ptr +// R-tree subtree scoped destroyer // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// 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) -#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_AUTO_PTR_HPP -#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_AUTO_PTR_HPP +#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_SUBTREE_DESTROYED_HPP +#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_SUBTREE_DESTROYED_HPP #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp> @@ -17,31 +17,29 @@ namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { -// TODO - change the name to node_scoped_ptr - template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> -class node_auto_ptr +class subtree_destroyer { typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; typedef typename Allocators::node_pointer pointer; - node_auto_ptr(node_auto_ptr const&); - node_auto_ptr & operator=(node_auto_ptr const&); + subtree_destroyer(subtree_destroyer const&); + subtree_destroyer & operator=(subtree_destroyer const&); public: - node_auto_ptr(pointer ptr, Allocators & allocators) + subtree_destroyer(pointer ptr, Allocators & allocators) : m_ptr(ptr) , m_allocators(allocators) {} - ~node_auto_ptr() + ~subtree_destroyer() { reset(); } void reset(pointer ptr = 0) { - if ( m_ptr ) + if ( m_ptr && m_ptr != ptr ) { detail::rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(m_ptr, m_allocators); detail::rtree::apply_visitor(del_v, *m_ptr); @@ -78,4 +76,4 @@ private: }}} // namespace boost::geometry::index -#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_AUTO_PTR_HPP +#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_SUBTREE_DESTROYED_HPP diff --git a/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp b/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp index f13dd10360..8e052e5216 100644 --- a/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp +++ b/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp @@ -96,7 +96,8 @@ class allocators<Allocator, Value, Parameters, Box, node_variant_dynamic_tag> typename node< Value, Parameters, Box, allocators<Allocator, Value, Parameters, Box, node_variant_dynamic_tag>, - node_variant_dynamic_tag>::type + node_variant_dynamic_tag + >::type >::other { typedef typename Allocator::template rebind< @@ -180,7 +181,7 @@ struct create_variant_node if ( 0 == p ) throw_runtime_error("boost::geometry::index::rtree node creation failed"); - auto_deallocator<AllocNode> deallocator(alloc_node, p); + scoped_deallocator<AllocNode> deallocator(p, alloc_node); Al::construct(alloc_node, boost::addressof(*p), Node(alloc_node)); // implicit cast to Variant diff --git a/boost/geometry/index/detail/rtree/node/variant_static.hpp b/boost/geometry/index/detail/rtree/node/variant_static.hpp index f6e9761b2d..174ceb7e7f 100644 --- a/boost/geometry/index/detail/rtree/node/variant_static.hpp +++ b/boost/geometry/index/detail/rtree/node/variant_static.hpp @@ -79,7 +79,7 @@ struct visitor<Value, Parameters, Box, Allocators, node_variant_static_tag, IsVi // allocators template <typename Allocator, typename Value, typename Parameters, typename Box> -struct allocators<Allocator, Value, Parameters, Box, node_variant_static_tag> +class allocators<Allocator, Value, Parameters, Box, node_variant_static_tag> : public Allocator::template rebind< typename node< Value, Parameters, Box, @@ -153,40 +153,6 @@ public: node_allocator_type const& node_allocator() const { return *this; } }; -// create_node - -template <typename Allocators, typename Value, typename Parameters, typename Box> -struct create_node< - Allocators, - variant_internal_node<Value, Parameters, Box, Allocators, node_variant_static_tag> -> -{ - static inline typename Allocators::node_pointer - apply(Allocators & allocators) - { - return create_variant_node< - typename Allocators::node_pointer, - variant_internal_node<Value, Parameters, Box, Allocators, node_variant_static_tag> - >::apply(allocators.node_allocator()); - } -}; - -template <typename Allocators, typename Value, typename Parameters, typename Box> -struct create_node< - Allocators, - variant_leaf<Value, Parameters, Box, Allocators, node_variant_static_tag> -> -{ - static inline typename Allocators::node_pointer - apply(Allocators & allocators) - { - return create_variant_node< - typename Allocators::node_pointer, - variant_leaf<Value, Parameters, Box, Allocators, node_variant_static_tag> - >::apply(allocators.node_allocator()); - } -}; - }} // namespace detail::rtree }}} // namespace boost::geometry::index diff --git a/boost/geometry/index/detail/rtree/node/variant_visitor.hpp b/boost/geometry/index/detail/rtree/node/variant_visitor.hpp index ffd67039d2..e272f9e1d9 100644 --- a/boost/geometry/index/detail/rtree/node/variant_visitor.hpp +++ b/boost/geometry/index/detail/rtree/node/variant_visitor.hpp @@ -11,7 +11,9 @@ #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_VISITOR_HPP #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_VARIANT_VISITOR_HPP -#include <boost/variant.hpp> +#include <boost/variant/apply_visitor.hpp> +#include <boost/variant/get.hpp> +#include <boost/variant/variant.hpp> namespace boost { namespace geometry { namespace index { diff --git a/boost/geometry/index/detail/rtree/node/weak_dynamic.hpp b/boost/geometry/index/detail/rtree/node/weak_dynamic.hpp index b828b35f45..d49e347826 100644 --- a/boost/geometry/index/detail/rtree/node/weak_dynamic.hpp +++ b/boost/geometry/index/detail/rtree/node/weak_dynamic.hpp @@ -197,7 +197,7 @@ struct create_weak_node if ( 0 == p ) throw_runtime_error("boost::geometry::index::rtree node creation failed"); - auto_deallocator<AllocNode> deallocator(alloc_node, p); + scoped_deallocator<AllocNode> deallocator(p, alloc_node); Al::construct(alloc_node, boost::addressof(*p), alloc_node); diff --git a/boost/geometry/index/detail/rtree/pack_create.hpp b/boost/geometry/index/detail/rtree/pack_create.hpp index 46bf357fc4..b7be41ab2b 100644 --- a/boost/geometry/index/detail/rtree/pack_create.hpp +++ b/boost/geometry/index/detail/rtree/pack_create.hpp @@ -2,7 +2,7 @@ // // R-tree initial packing // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -122,7 +122,7 @@ class pack typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; typedef typename Allocators::node_pointer node_pointer; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; typedef typename Allocators::size_type size_type; typedef typename geometry::point_type<Box>::type point_type; @@ -161,10 +161,21 @@ public: geometry::assign_inverse(hint_box); for ( ; first != last ; ++first ) { - geometry::expand(hint_box, translator(*first)); + // NOTE: support for iterators not returning true references adapted + // to Geometry concept and default translator returning true reference + // An alternative would be to dereference the iterator and translate + // in one expression each time the indexable was needed. + typename std::iterator_traits<InIt>::reference in_ref = *first; + typename Translator::result_type indexable = translator(in_ref); + + // NOTE: added for consistency with insert() + // CONSIDER: alternative - ignore invalid indexable or throw an exception + BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(indexable), "Indexable is invalid"); + + geometry::expand(hint_box, indexable); point_type pt; - geometry::centroid(translator(*first), pt); + geometry::centroid(indexable, pt); entries.push_back(std::make_pair(pt, first)); } @@ -187,17 +198,19 @@ private: internal_element per_level(EIt first, EIt last, Box const& hint_box, std::size_t values_count, subtree_elements_counts const& subtree_counts, parameters_type const& parameters, Translator const& translator, Allocators & allocators) { - BOOST_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count); + BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count, + "unexpected parameters"); if ( subtree_counts.maxc <= 1 ) { // ROOT or LEAF - BOOST_ASSERT(values_count <= parameters.get_max_elements()); + BOOST_GEOMETRY_INDEX_ASSERT(values_count <= parameters.get_max_elements(), + "too big number of elements"); // if !root check m_parameters.get_min_elements() <= count // create new leaf node node_pointer n = rtree::create_node<Allocators, leaf>::apply(allocators); // MAY THROW (A) - node_auto_ptr auto_remover(n, allocators); + subtree_destroyer auto_remover(n, allocators); leaf & l = rtree::get<leaf>(*n); // reserve space for values @@ -207,8 +220,11 @@ private: geometry::assign_inverse(elements_box); for ( ; first != last ; ++first ) { - rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C) + // NOTE: push_back() must be called at the end in order to support move_iterator. + // The iterator is dereferenced 2x (no temporary reference) to support + // non-true reference types and move_iterator without boost::forward<>. geometry::expand(elements_box, translator(*(first->second))); + rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C) } auto_remover.release(); @@ -222,7 +238,7 @@ private: // create new internal node node_pointer n = rtree::create_node<Allocators, internal_node>::apply(allocators); // MAY THROW (A) - node_auto_ptr auto_remover(n, allocators); + subtree_destroyer auto_remover(n, allocators); internal_node & in = rtree::get<internal_node>(*n); // reserve space for values @@ -248,9 +264,11 @@ private: internal_elements & elements, Box & elements_box, parameters_type const& parameters, Translator const& translator, Allocators & allocators) { - BOOST_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count); + BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count, + "unexpected parameters"); - BOOST_ASSERT_MSG( subtree_counts.minc <= values_count, "too small number of elements"); + BOOST_GEOMETRY_INDEX_ASSERT(subtree_counts.minc <= values_count, + "too small number of elements"); // only one packet if ( values_count <= subtree_counts.maxc ) @@ -262,7 +280,7 @@ private: // in case if push_back() do throw here // and even if this is not probable (previously reserved memory, nonthrowing pairs copy) // this case is also tested by exceptions test. - node_auto_ptr auto_remover(el.second, allocators); + subtree_destroyer auto_remover(el.second, allocators); // this container should have memory allocated, reserve() called outside elements.push_back(el); // MAY THROW (A?,C) - however in normal conditions shouldn't auto_remover.release(); @@ -343,7 +361,7 @@ private: { if ( subtree_counts.minc <= r ) // e.g. 10 <= 2 == false { - //BOOST_ASSERT_MSG(0 < n, "unexpected value"); + //BOOST_GEOMETRY_INDEX_ASSERT(0 < n, "unexpected value"); median_count = ((n+1)/2) * subtree_counts.maxc; // if calculated ((2+1)/2) * 25 which would be ok, but not in all cases } else // r < subtree_counts.second // e.g. 2 < 10 == true @@ -354,7 +372,7 @@ private: if ( r == 0 ) // e.g. false { // n can't be equal to 0 because then there wouldn't be any element in the other node - //BOOST_ASSERT_MSG(0 < n, "unexpected value"); + //BOOST_GEOMETRY_INDEX_ASSERT(0 < n, "unexpected value"); median_count = ((n+1)/2) * subtree_counts.maxc; // if calculated ((1+1)/2) * 25 which would be ok, but not in all cases } else diff --git a/boost/geometry/index/detail/rtree/query_iterators.hpp b/boost/geometry/index/detail/rtree/query_iterators.hpp index 8366fca191..74000d03ef 100644 --- a/boost/geometry/index/detail/rtree/query_iterators.hpp +++ b/boost/geometry/index/detail/rtree/query_iterators.hpp @@ -2,7 +2,7 @@ // // R-tree query iterators // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -11,9 +11,8 @@ #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP -#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL -//#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION -//#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE +#include <boost/scoped_ptr.hpp> + //#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators { @@ -29,27 +28,27 @@ struct end_query_iterator reference operator*() const { - BOOST_ASSERT_MSG(false, "iterator not dereferencable"); + BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not dereferencable"); pointer p(0); return *p; } const value_type * operator->() const { - BOOST_ASSERT_MSG(false, "iterator not dereferencable"); + BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not dereferencable"); const value_type * p = 0; return p; } end_query_iterator & operator++() { - BOOST_ASSERT_MSG(false, "iterator not incrementable"); + BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not incrementable"); return *this; } end_query_iterator operator++(int) { - BOOST_ASSERT_MSG(false, "iterator not incrementable"); + BOOST_GEOMETRY_INDEX_ASSERT(false, "iterator not incrementable"); return *this; } @@ -197,9 +196,6 @@ inline bool operator!=(L const& l, R const& r) }}}}}} // namespace boost::geometry::index::detail::rtree::iterators -#if defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL) || defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION) - -#if defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL) namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators { @@ -246,73 +242,7 @@ public: virtual bool equals(base_t const& r) const { const query_iterator_wrapper * p = dynamic_cast<const query_iterator_wrapper *>(boost::addressof(r)); - BOOST_ASSERT_MSG(p, "those iterators can't be compared"); - return m_iterator == p->m_iterator; - } - -private: - Iterator m_iterator; -}; - -#elif defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION) - -#include <boost/function.hpp> -#include <boost/bind.hpp> - -namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators { - -template <typename Value, typename Allocators> -class query_iterator_base -{ -public: - typedef std::input_iterator_tag iterator_category; - typedef Value value_type; - typedef typename Allocators::const_reference reference; - typedef typename Allocators::difference_type difference_type; - typedef typename Allocators::const_pointer pointer; - - virtual ~query_iterator_base() {} - - boost::function<query_iterator_base*()> clone; - boost::function<bool()> is_end; - boost::function<reference()> dereference; - boost::function<void()> increment; - boost::function<bool(query_iterator_base const&)> equals; -}; - -template <typename Value, typename Allocators, typename Iterator> -class query_iterator_wrapper - : public query_iterator_base<Value, Allocators> -{ - typedef query_iterator_base<Value, Allocators> base_t; - -public: - typedef std::input_iterator_tag iterator_category; - typedef Value value_type; - typedef typename Allocators::const_reference reference; - typedef typename Allocators::difference_type difference_type; - typedef typename Allocators::const_pointer pointer; - - explicit query_iterator_wrapper(Iterator const& it) - : m_iterator(it) - { - base_t::clone = boost::bind(&query_iterator_wrapper::clone_, this); - base_t::is_end = boost::bind(&query_iterator_wrapper::is_end_, this); - base_t::dereference = boost::bind(&query_iterator_wrapper::dereference_, this); - base_t::increment = boost::bind(&query_iterator_wrapper::increment_, this); - base_t::equals = boost::bind(&query_iterator_wrapper::equals_, this, _1); - } - -private: - base_t * clone_() const { return new query_iterator_wrapper(m_iterator); } - - bool is_end_() const { return m_iterator == end_query_iterator<Value, Allocators>(); } - reference dereference_() const { return *m_iterator; } - void increment_() { ++m_iterator; } - bool equals_(base_t const& r) const - { - const query_iterator_wrapper * p = dynamic_cast<const query_iterator_wrapper *>(boost::addressof(r)); - BOOST_ASSERT_MSG(p, "those iterators can't be compared"); + BOOST_GEOMETRY_INDEX_ASSERT(p, "iterators can't be compared"); return m_iterator == p->m_iterator; } @@ -320,13 +250,12 @@ private: Iterator m_iterator; }; -#endif template <typename Value, typename Allocators> class query_iterator { typedef query_iterator_base<Value, Allocators> iterator_base; - typedef std::auto_ptr<iterator_base> iterator_ptr; + typedef boost::scoped_ptr<iterator_base> iterator_ptr; public: typedef std::input_iterator_tag iterator_category; @@ -353,21 +282,24 @@ public: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE query_iterator & operator=(query_iterator const& o) { - m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0); + if ( this != boost::addressof(o) ) + { + m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0); + } return *this; } #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES query_iterator(query_iterator && o) - : m_ptr(o.m_ptr.get()) + : m_ptr(0) { - o.m_ptr.release(); + m_ptr.swap(o.m_ptr); } query_iterator & operator=(query_iterator && o) { if ( this != boost::addressof(o) ) { - m_ptr.reset(o.m_ptr.get()); - o.m_ptr.release(); + m_ptr.swap(o.m_ptr); + o.m_ptr.reset(); } return *this; } @@ -378,20 +310,23 @@ private: public: query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o) { - m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0); + if ( this != boost::addressof(o) ) + { + m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0); + } return *this; } query_iterator(BOOST_RV_REF(query_iterator) o) - : m_ptr(o.m_ptr.get()) + : m_ptr(0) { - o.m_ptr.release(); + m_ptr.swap(o.m_ptr); } query_iterator & operator=(BOOST_RV_REF(query_iterator) o) { if ( this != boost::addressof(o) ) { - m_ptr.reset(o.m_ptr.get()); - o.m_ptr.release(); + m_ptr.swap(o.m_ptr); + o.m_ptr.reset(); } return *this; } @@ -444,156 +379,4 @@ private: }}}}}} // namespace boost::geometry::index::detail::rtree::iterators -#elif defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE) - -#include <boost/type_erasure/any.hpp> -#include <boost/type_erasure/operators.hpp> -#include <boost/type_erasure/is_empty.hpp> - -namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators { - -template<typename T, typename Value, typename Allocators> -struct single_pass_iterator_concept : - ::boost::mpl::vector< - ::boost::type_erasure::copy_constructible<T>, - ::boost::type_erasure::equality_comparable<T>, - ::boost::type_erasure::dereferenceable<typename Allocators::const_reference, T>, - ::boost::type_erasure::assignable<T>, - ::boost::type_erasure::incrementable<T>, - ::boost::type_erasure::equality_comparable<T, end_query_iterator<Value, Allocators> >, - ::boost::type_erasure::relaxed // default ctor - > -{}; - -template <typename Value, typename Allocators> -struct single_pass_iterator_type -{ - typedef ::boost::type_erasure::any< - single_pass_iterator_concept< - ::boost::type_erasure::_self, Value, Allocators - > - > type; -}; - -}}}}}} // namespace boost::geometry::index::detail::rtree::iterators - -namespace boost { namespace type_erasure { - -template<typename T, typename Value, typename Allocators, typename Base> -struct concept_interface< - ::boost::geometry::index::detail::rtree::single_pass_iterator_concept< - T, Value, Allocators - >, Base, T> - : Base -{ - typedef Value value_type; - typedef typename Allocators::const_reference reference; - typedef typename Allocators::const_pointer pointer; - typedef typename Allocators::difference_type difference_type; - typedef ::std::input_iterator_tag iterator_category; -}; - -}} // boost::type_erasure - -namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators { - -template <typename Value, typename Allocators> -class query_iterator -{ -public: - typedef std::input_iterator_tag iterator_category; - typedef Value value_type; - typedef typename Allocators::const_reference reference; - typedef typename Allocators::difference_type difference_type; - typedef typename Allocators::const_pointer pointer; - -private: - typedef typename rtree::single_pass_iterator_type<Value, Allocators>::type iterator_type; - -public: - - query_iterator() {} - - template <typename It> - query_iterator(It const& it) - : m_iterator(it) - {} - - query_iterator(end_query_iterator<Value, Allocators> const& /*it*/) - {} - -#ifdef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE -private: - BOOST_COPYABLE_AND_MOVABLE(query_iterator) -public: - query_iterator(query_iterator const& o) - : m_iterator(o.m_iterator) - {} - query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o) - { - m_iterator = o.m_iterator; - return *this; - } - query_iterator(BOOST_RV_REF(query_iterator) o) - : m_iterator(boost::move(o.m_iterator)) - {} - query_iterator & operator=(BOOST_RV_REF(query_iterator) o) - { - if ( this != boost::addressof(o) ) - { - m_iterator = boost::move(o.m_iterator); - } - return *this; - } -#endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE - - reference operator*() const - { - return *m_iterator; - } - - const value_type * operator->() const - { - return boost::addressof(*m_iterator); - } - - query_iterator & operator++() - { - ++m_iterator; - return *this; - } - - query_iterator operator++(int) - { - query_iterator temp = *this; - ++m_iterator; - return temp; - } - - friend bool operator==(query_iterator const& l, query_iterator const& r) - { - if ( !::boost::type_erasure::is_empty(l.m_iterator) ) - { - if ( !::boost::type_erasure::is_empty(r.m_iterator) ) - return l.m_iterator == r.m_iterator; - else - return l.m_iterator == end_query_iterator<Value, Allocators>(); - } - else - { - if ( !::boost::type_erasure::is_empty(r.m_iterator) ) - return r.m_iterator == end_query_iterator<Value, Allocators>(); - else - return true; - } - } - -private: - iterator_type m_iterator; -}; - -}}}}}} // namespace boost::geometry::index::detail::rtree::iterators - -#endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE - #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP diff --git a/boost/geometry/index/detail/rtree/rstar/insert.hpp b/boost/geometry/index/detail/rtree/rstar/insert.hpp index e544d6dd1e..ce92140872 100644 --- a/boost/geometry/index/detail/rtree/rstar/insert.hpp +++ b/boost/geometry/index/detail/rtree/rstar/insert.hpp @@ -472,8 +472,9 @@ public: , m_relative_level(relative_level), m_allocators(allocators) {} - inline void operator()(internal_node & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n)) + inline void operator()(internal_node & n) { + boost::ignore_unused(n); BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root"); // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one @@ -498,8 +499,9 @@ public: } } - inline void operator()(leaf & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n)) + inline void operator()(leaf & n) { + boost::ignore_unused(n); BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root"); // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one diff --git a/boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp b/boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp new file mode 100644 index 0000000000..10a1bec6ad --- /dev/null +++ b/boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp @@ -0,0 +1,110 @@ +// Boost.Geometry Index +// +// R-tree nodes elements numbers validating visitor implementation +// +// 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) + +#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP +#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP + +#include <boost/geometry/index/detail/rtree/node/node.hpp> + +namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities { + +namespace visitors { + +template <typename Value, typename Options, typename Box, typename Allocators> +class are_counts_ok + : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type +{ + typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; + typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; + typedef typename Options::parameters_type parameters_type; + +public: + inline are_counts_ok(parameters_type const& parameters) + : result(true), m_current_level(0), m_parameters(parameters) + {} + + inline void operator()(internal_node const& n) + { + typedef typename rtree::elements_type<internal_node>::type elements_type; + elements_type const& elements = rtree::elements(n); + + // root internal node shouldn't contain 0 elements + if ( elements.empty() + || !check_count(elements) ) + { + result = false; + return; + } + + size_t current_level_backup = m_current_level; + ++m_current_level; + + for ( typename elements_type::const_iterator it = elements.begin(); + it != elements.end() && result == true ; + ++it) + { + rtree::apply_visitor(*this, *it->second); + } + + m_current_level = current_level_backup; + } + + inline void operator()(leaf const& n) + { + typedef typename rtree::elements_type<leaf>::type elements_type; + elements_type const& elements = rtree::elements(n); + + // empty leaf in non-root node + if ( ( m_current_level > 0 && elements.empty() ) + || !check_count(elements) ) + { + result = false; + } + } + + bool result; + +private: + template <typename Elements> + bool check_count(Elements const& elements) + { + // root may contain count < min but should never contain count > max + return elements.size() <= m_parameters.get_max_elements() + && ( elements.size() >= m_parameters.get_min_elements() + || m_current_level == 0 ); + } + + size_t m_current_level; + parameters_type const& m_parameters; +}; + +} // namespace visitors + +template <typename Rtree> inline +bool are_counts_ok(Rtree const& tree) +{ + typedef utilities::view<Rtree> RTV; + RTV rtv(tree); + + visitors::are_counts_ok< + typename RTV::value_type, + typename RTV::options_type, + typename RTV::box_type, + typename RTV::allocators_type + > v(tree.parameters()); + + rtv.apply_visitor(v); + + return v.result; +} + +}}}}}} // namespace boost::geometry::index::detail::rtree::utilities + +#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP diff --git a/boost/geometry/index/detail/rtree/visitors/copy.hpp b/boost/geometry/index/detail/rtree/visitors/copy.hpp index 8fc25ac803..86ffc99caf 100644 --- a/boost/geometry/index/detail/rtree/visitors/copy.hpp +++ b/boost/geometry/index/detail/rtree/visitors/copy.hpp @@ -2,7 +2,7 @@ // // R-tree deep copying visitor implementation // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -24,7 +24,7 @@ public: typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; typedef typename Allocators::node_pointer node_pointer; explicit inline copy(Allocators & allocators) @@ -35,7 +35,7 @@ public: inline void operator()(internal_node & n) { node_pointer raw_new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators); // MAY THROW, STRONG (N: alloc) - node_auto_ptr new_node(raw_new_node, m_allocators); + subtree_destroyer new_node(raw_new_node, m_allocators); typedef typename rtree::elements_type<internal_node>::type elements_type; elements_type & elements = rtree::elements(n); @@ -48,7 +48,7 @@ public: rtree::apply_visitor(*this, *it->second); // MAY THROW (V, E: alloc, copy, N: alloc) // for exception safety - node_auto_ptr auto_result(result, m_allocators); + subtree_destroyer auto_result(result, m_allocators); elements_dst.push_back( rtree::make_ptr_pair(it->first, result) ); // MAY THROW, STRONG (E: alloc, copy) @@ -62,7 +62,7 @@ public: inline void operator()(leaf & l) { node_pointer raw_new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators); // MAY THROW, STRONG (N: alloc) - node_auto_ptr new_node(raw_new_node, m_allocators); + subtree_destroyer new_node(raw_new_node, m_allocators); typedef typename rtree::elements_type<leaf>::type elements_type; elements_type & elements = rtree::elements(l); diff --git a/boost/geometry/index/detail/rtree/visitors/destroy.hpp b/boost/geometry/index/detail/rtree/visitors/destroy.hpp index 62722b97a8..b4a800eac2 100644 --- a/boost/geometry/index/detail/rtree/visitors/destroy.hpp +++ b/boost/geometry/index/detail/rtree/visitors/destroy.hpp @@ -2,7 +2,7 @@ // // R-tree destroying visitor implementation // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2014 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 @@ -51,8 +51,9 @@ public: rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, node_to_destroy); } - inline void operator()(leaf & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(l)) + inline void operator()(leaf & l) { + boost::ignore_unused(l); BOOST_GEOMETRY_INDEX_ASSERT(&l == &rtree::get<leaf>(*m_current_node), "invalid pointers"); rtree::destroy_node<Allocators, leaf>::apply(m_allocators, m_current_node); diff --git a/boost/geometry/index/detail/rtree/visitors/distance_query.hpp b/boost/geometry/index/detail/rtree/visitors/distance_query.hpp index 342cc4bbc3..fc0929e9ed 100644 --- a/boost/geometry/index/detail/rtree/visitors/distance_query.hpp +++ b/boost/geometry/index/detail/rtree/visitors/distance_query.hpp @@ -344,7 +344,7 @@ public: , next_closest_node_distance((std::numeric_limits<node_distance_type>::max)()) { - BOOST_ASSERT_MSG(0 < max_count(), "k must be greather than 0"); + BOOST_GEOMETRY_INDEX_ASSERT(0 < max_count(), "k must be greather than 0"); } const_reference dereference() const @@ -399,7 +399,7 @@ public: } // if node is further than the furthest neighbour, following nodes also will be further - BOOST_ASSERT_MSG(neighbors.size() <= max_count(), "unexpected neighbours count"); + BOOST_GEOMETRY_INDEX_ASSERT(neighbors.size() <= max_count(), "unexpected neighbours count"); if ( max_count() <= neighbors.size() && is_node_prunable(neighbors.back().first, branches[current_branch].first) ) { @@ -426,10 +426,10 @@ public: friend bool operator==(distance_query_incremental const& l, distance_query_incremental const& r) { - BOOST_ASSERT_MSG(l.current_neighbor != r.current_neighbor || - (std::numeric_limits<size_type>::max)() == l.current_neighbor || - l.neighbors[l.current_neighbor].second == r.neighbors[r.current_neighbor].second, - "not corresponding iterators"); + BOOST_GEOMETRY_INDEX_ASSERT(l.current_neighbor != r.current_neighbor || + (std::numeric_limits<size_type>::max)() == l.current_neighbor || + l.neighbors[l.current_neighbor].second == r.neighbors[r.current_neighbor].second, + "not corresponding iterators"); return l.current_neighbor == r.current_neighbor; } diff --git a/boost/geometry/index/detail/rtree/visitors/insert.hpp b/boost/geometry/index/detail/rtree/visitors/insert.hpp index 388b3193f6..e697c065e1 100644 --- a/boost/geometry/index/detail/rtree/visitors/insert.hpp +++ b/boost/geometry/index/detail/rtree/visitors/insert.hpp @@ -2,7 +2,7 @@ // // R-tree inserting visitor implementation // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -115,7 +115,7 @@ protected: typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; public: typedef index::detail::varray< @@ -133,8 +133,8 @@ public: { // TODO - consider creating nodes always with sufficient memory allocated - // create additional node, use auto ptr for automatic destruction on exception - node_auto_ptr second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW, STRONG (N: alloc) + // create additional node, use auto destroyer for automatic destruction on exception + subtree_destroyer second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW, STRONG (N: alloc) // create reference to the newly created node Node & n2 = rtree::get<Node>(*second_node); @@ -232,7 +232,7 @@ protected: typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; typedef typename Allocators::node_pointer node_pointer; typedef typename Allocators::size_type size_type; @@ -340,7 +340,7 @@ protected: // Implement template <node_tag> struct node_element_type or something like that // for exception safety - node_auto_ptr additional_node_ptr(additional_nodes[0].second, m_allocators); + subtree_destroyer additional_node_ptr(additional_nodes[0].second, m_allocators); // node is not the root - just add the new node if ( !m_traverse_data.current_is_root() ) @@ -356,7 +356,7 @@ protected: BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<Node>(*m_root_node), "node should be the root"); // create new root and add nodes - node_auto_ptr new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc) + subtree_destroyer new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc) BOOST_TRY { @@ -365,7 +365,7 @@ protected: } BOOST_CATCH(...) { - // clear new root to not delete in the ~node_auto_ptr() potentially stored old root node + // clear new root to not delete in the ~subtree_destroyer() potentially stored old root node rtree::elements(rtree::get<internal_node>(*new_root)).clear(); BOOST_RETHROW // RETHROW } diff --git a/boost/geometry/index/detail/rtree/visitors/is_leaf.hpp b/boost/geometry/index/detail/rtree/visitors/is_leaf.hpp index 6d21afd99e..dd2159c71e 100644 --- a/boost/geometry/index/detail/rtree/visitors/is_leaf.hpp +++ b/boost/geometry/index/detail/rtree/visitors/is_leaf.hpp @@ -2,7 +2,7 @@ // // R-tree leaf node checking visitor implementation // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -21,9 +21,13 @@ struct is_leaf : public rtree::visitor<Value, typename Options::parameters_type, typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; + is_leaf() + : result(false) + {} + inline void operator()(internal_node const&) { - result = false; + // result = false; } inline void operator()(leaf const&) diff --git a/boost/geometry/index/detail/rtree/visitors/remove.hpp b/boost/geometry/index/detail/rtree/visitors/remove.hpp index d4890a368b..494d5a019e 100644 --- a/boost/geometry/index/detail/rtree/visitors/remove.hpp +++ b/boost/geometry/index/detail/rtree/visitors/remove.hpp @@ -2,7 +2,7 @@ // // R-tree removing visitor implementation // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -30,7 +30,7 @@ class remove typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; typedef typename Allocators::node_pointer node_pointer; typedef typename Allocators::size_type size_type; @@ -152,7 +152,7 @@ public: // if value was removed if ( m_is_value_removed ) { - BOOST_ASSERT_MSG(0 < m_parameters.get_min_elements(), "min number of elements is too small"); + BOOST_GEOMETRY_INDEX_ASSERT(0 < m_parameters.get_min_elements(), "min number of elements is too small"); // calc underflow m_is_underflow = elements.size() < m_parameters.get_min_elements(); @@ -222,6 +222,13 @@ private: return elements.size() < m_parameters.get_min_elements(); } + static inline bool is_leaf(node const& n) + { + visitors::is_leaf<Value, Options, Box, Allocators> ilv; + rtree::apply_visitor(ilv, n); + return ilv.result; + } + void reinsert_removed_nodes_elements() { typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin(); @@ -232,9 +239,11 @@ private: // begin with levels closer to the root for ( ; it != m_underflowed_nodes.rend() ; ++it ) { - is_leaf<Value, Options, Box, Allocators> ilv; - rtree::apply_visitor(ilv, *it->second); - if ( ilv.result ) + // it->first is an index of a level of a node, not children + // counted from the leafs level + bool const node_is_leaf = it->first == 1; + BOOST_GEOMETRY_INDEX_ASSERT(node_is_leaf == is_leaf(*it->second), "unexpected condition"); + if ( node_is_leaf ) { reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc) @@ -255,7 +264,7 @@ private: // destroy current and remaining nodes for ( ; it != m_underflowed_nodes.rend() ; ++it ) { - node_auto_ptr dummy(it->second, m_allocators); + subtree_destroyer dummy(it->second, m_allocators); } //m_underflowed_nodes.clear(); diff --git a/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp b/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp index 0a43111ac4..f00189fe77 100644 --- a/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp +++ b/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp @@ -2,7 +2,7 @@ // // R-tree spatial query visitor implementation // -// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2011-2014 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 @@ -116,7 +116,7 @@ public: const_reference dereference() const { - BOOST_ASSERT_MSG(m_values, "not dereferencable"); + BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable"); return *m_current; } diff --git a/boost/geometry/index/detail/serialization.hpp b/boost/geometry/index/detail/serialization.hpp index 34036e3904..550a37565b 100644 --- a/boost/geometry/index/detail/serialization.hpp +++ b/boost/geometry/index/detail/serialization.hpp @@ -1,6 +1,6 @@ // Boost.Geometry Index // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -353,7 +353,7 @@ class load typedef typename Options::parameters_type parameters_type; typedef typename Allocators::node_pointer node_pointer; - typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr; + typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; typedef typename Allocators::size_type size_type; public: @@ -385,7 +385,7 @@ private: if ( current_level < leafs_level ) { node_pointer n = rtree::create_node<Allocators, internal_node>::apply(allocators); // MAY THROW (A) - node_auto_ptr auto_remover(n, allocators); + subtree_destroyer auto_remover(n, allocators); internal_node & in = rtree::get<internal_node>(*n); elements_type & elements = rtree::elements(in); @@ -408,7 +408,7 @@ private: BOOST_GEOMETRY_INDEX_ASSERT(current_level == leafs_level, "unexpected value"); node_pointer n = rtree::create_node<Allocators, leaf>::apply(allocators); // MAY THROW (A) - node_auto_ptr auto_remover(n, allocators); + subtree_destroyer auto_remover(n, allocators); leaf & l = rtree::get<leaf>(*n); typedef typename rtree::elements_type<leaf>::type elements_type; @@ -537,7 +537,7 @@ void load(Archive & ar, boost::geometry::index::rtree<V, P, I, E, A> & rt, unsig typedef typename options_type::parameters_type parameters_type; typedef typename allocators_type::node_pointer node_pointer; - typedef detail::rtree::node_auto_ptr<value_type, options_type, translator_type, box_type, allocators_type> node_auto_ptr; + typedef detail::rtree::subtree_destroyer<value_type, options_type, translator_type, box_type, allocators_type> subtree_destroyer; view tree(rt); @@ -554,7 +554,7 @@ void load(Archive & ar, boost::geometry::index::rtree<V, P, I, E, A> & rt, unsig n = detail::rtree::load<value_type, options_type, translator_type, box_type, allocators_type> ::apply(ar, version, leafs_level, loaded_values_count, params, tree.members().translator(), tree.members().allocators()); // MAY THROW - node_auto_ptr remover(n, tree.members().allocators()); + subtree_destroyer remover(n, tree.members().allocators()); if ( loaded_values_count != values_count ) BOOST_THROW_EXCEPTION(std::runtime_error("unexpected number of values")); // TODO change exception type remover.release(); @@ -564,7 +564,7 @@ void load(Archive & ar, boost::geometry::index::rtree<V, P, I, E, A> & rt, unsig tree.members().values_count = values_count; tree.members().leafs_level = leafs_level; - node_auto_ptr remover(tree.members().root, tree.members().allocators()); + subtree_destroyer remover(tree.members().root, tree.members().allocators()); tree.members().root = n; } diff --git a/boost/geometry/index/detail/varray.hpp b/boost/geometry/index/detail/varray.hpp index 63577e64a7..1b084aafdb 100644 --- a/boost/geometry/index/detail/varray.hpp +++ b/boost/geometry/index/detail/varray.hpp @@ -1,6 +1,6 @@ // Boost.Container varray // -// Copyright (c) 2012-2014 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2012-2015 Adam Wulkiewicz, Lodz, Poland. // Copyright (c) 2011-2013 Andrew Hundt. // // Use, modification and distribution is subject to the Boost Software License, @@ -13,7 +13,10 @@ // TODO - REMOVE/CHANGE #include <boost/container/detail/config_begin.hpp> #include <boost/container/detail/workaround.hpp> -#include <boost/container/detail/preprocessor.hpp> + +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> +#endif #include <boost/config.hpp> #include <boost/swap.hpp> @@ -32,12 +35,11 @@ #include <boost/iterator/iterator_concepts.hpp> #include <boost/geometry/index/detail/assert.hpp> +#include <boost/geometry/index/detail/exception.hpp> -#include <boost/geometry/index/detail/assert.hpp> #include <boost/geometry/index/detail/varray_detail.hpp> #include <boost/concept_check.hpp> -#include <boost/throw_exception.hpp> /*! \defgroup varray_non_member varray non-member functions @@ -79,12 +81,8 @@ struct checker static inline void throw_out_of_bounds(Varray const& v, size_type i) { -//#ifndef BOOST_NO_EXCEPTIONS if ( v.size() <= i ) - BOOST_THROW_EXCEPTION(std::out_of_range("index out of bounds")); -//#else // BOOST_NO_EXCEPTIONS -// BOOST_GEOMETRY_INDEX_ASSERT(i < v.size(), "index out of bounds"); -//#endif // BOOST_NO_EXCEPTIONS + throw_out_of_range("index out of bounds"); ::boost::ignore_unused_variable_warning(v); ::boost::ignore_unused_variable_warning(i); @@ -920,9 +918,9 @@ public: difference_type n = std::distance(first, last); //TODO - add invalid range check? - //BOOST_ASSERT_MSG(0 <= n, "invalid range"); + //BOOST_GEOMETRY_INDEX_ASSERT(0 <= n, "invalid range"); //TODO - add this->size() check? - //BOOST_ASSERT_MSG(n <= this->size(), "invalid range"); + //BOOST_GEOMETRY_INDEX_ASSERT(n <= this->size(), "invalid range"); sv::move(last, this->end(), first); // may throw sv::destroy(this->end() - n, this->end()); @@ -984,7 +982,7 @@ public: } #if !defined(BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE) -#if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! @pre <tt>size() < capacity()</tt> //! //! @brief Inserts a Value constructed with @@ -1065,27 +1063,23 @@ public: return position; } -#else // BOOST_CONTAINER_PERFECT_FORWARDING || BOOST_CONTAINER_DOXYGEN_INVOKED +#else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - void emplace_back(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + #define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + void emplace_back(BOOST_MOVE_UREF##N) \ { \ typedef typename vt::disable_trivial_init dti; \ \ errh::check_capacity(*this, m_size + 1); /*may throw*/\ \ - namespace sv = varray_detail; \ - sv::construct(dti(), this->end() BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); /*may throw*/\ + namespace sv = varray_detail; \ + sv::construct(dti(), this->end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\ ++m_size; /*update end*/ \ } \ - // - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() - - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace(iterator position BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace(iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N) \ { \ typedef typename vt::disable_trivial_init dti; \ namespace sv = varray_detail; \ @@ -1095,7 +1089,7 @@ public: \ if ( position == this->end() ) \ { \ - sv::construct(dti(), position BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); /*may throw*/\ + sv::construct(dti(), position BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\ ++m_size; /*update end*/ \ } \ else \ @@ -1104,24 +1098,24 @@ public: /* TODO - should move be used only if it's nonthrowing? */ \ \ value_type & r = *(this->end() - 1); \ - sv::construct(dti(), this->end(), boost::move(r)); /*may throw*/\ + sv::construct(dti(), this->end(), boost::move(r)); /*may throw*/\ ++m_size; /*update end*/ \ sv::move_backward(position, this->end() - 2, this->end() - 1); /*may throw*/\ \ aligned_storage<sizeof(value_type), alignment_of<value_type>::value> temp_storage; \ value_type * val_p = static_cast<value_type *>(temp_storage.address()); \ - sv::construct(dti(), val_p BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ); /*may throw*/\ + sv::construct(dti(), val_p BOOST_MOVE_I##N BOOST_MOVE_FWD##N ); /*may throw*/\ sv::scoped_destructor<value_type> d(val_p); \ sv::assign(position, ::boost::move(*val_p)); /*may throw*/\ } \ \ return position; \ } \ - // - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() + + BOOST_MOVE_ITERATE_0TO9(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE) + #undef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_EMPLACE -#endif // BOOST_CONTAINER_PERFECT_FORWARDING || BOOST_CONTAINER_DOXYGEN_INVOKED +#endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) #endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE //! @brief Removes all elements from the container. @@ -1614,7 +1608,8 @@ private: // Linear O(N). void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::true_type const& /*use_memop*/) { - //BOOST_ASSERT_MSG(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la)); + //BOOST_GEOMETRY_INDEX_ASSERT(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la), + // "incompatible ranges"); namespace sv = varray_detail; for (; first_sm != last_sm ; ++first_sm, ++first_la) @@ -1639,7 +1634,8 @@ private: // Linear O(N). void swap_dispatch_impl(iterator first_sm, iterator last_sm, iterator first_la, iterator last_la, boost::false_type const& /*use_memop*/) { - //BOOST_ASSERT_MSG(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la)); + //BOOST_GEOMETRY_INDEX_ASSERT(std::distance(first_sm, last_sm) <= std::distance(first_la, last_la), + // "incompatible ranges"); namespace sv = varray_detail; for (; first_sm != last_sm ; ++first_sm, ++first_la) @@ -1961,7 +1957,7 @@ public: errh::check_iterator_end_eq(*this, first); errh::check_iterator_end_eq(*this, last); - //BOOST_ASSERT_MSG(0 <= n, "invalid range"); + //BOOST_GEOMETRY_INDEX_ASSERT(0 <= n, "invalid range"); } // basic diff --git a/boost/geometry/index/detail/varray_detail.hpp b/boost/geometry/index/detail/varray_detail.hpp index 962d4d8288..31b77c40fe 100644 --- a/boost/geometry/index/detail/varray_detail.hpp +++ b/boost/geometry/index/detail/varray_detail.hpp @@ -2,7 +2,7 @@ // // varray details // -// Copyright (c) 2012-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2012-2015 Adam Wulkiewicz, Lodz, Poland. // Copyright (c) 2011-2013 Andrew Hundt. // // Use, modification and distribution is subject to the Boost Software License, @@ -39,9 +39,13 @@ #include <boost/detail/no_exceptions_support.hpp> #include <boost/config.hpp> #include <boost/move/move.hpp> -#include <boost/utility/addressof.hpp> +#include <boost/core/addressof.hpp> #include <boost/iterator/iterator_traits.hpp> +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> +#endif + // TODO - move vectors iterators optimization to the other, optional file instead of checking defines? #if defined(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_ENABLE_VECTOR_OPTIMIZATION) && !defined(BOOST_NO_EXCEPTIONS) @@ -618,22 +622,22 @@ void construct(DisableTrivialInit const&, // !BOOST_NO_CXX11_RVALUE_REFERENCES -> P0 && p0 // which means that version with one parameter may take V const& v -#define BOOST_PP_LOCAL_MACRO(n) \ -template <typename DisableTrivialInit, typename I, typename P BOOST_PP_ENUM_TRAILING_PARAMS(n, typename P) > \ +#define BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_DETAIL_CONSTRUCT(N) \ +template <typename DisableTrivialInit, typename I, typename P BOOST_MOVE_I##N BOOST_MOVE_CLASS##N > \ inline \ void construct(DisableTrivialInit const&, \ I pos, \ - BOOST_CONTAINER_PP_PARAM(P, p) \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + BOOST_FWD_REF(P) p \ + BOOST_MOVE_I##N BOOST_MOVE_UREF##N) \ { \ typedef typename boost::iterator_value<I>::type V; \ new \ (static_cast<void*>(boost::addressof(*pos))) \ - V(p, BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); /*may throw*/ \ + V(boost::forward<P>(p) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); /*may throw*/ \ } \ -// -#define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) -#include BOOST_PP_LOCAL_ITERATE() + +BOOST_MOVE_ITERATE_1TO9(BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_DETAIL_CONSTRUCT) +#undef BOOST_GEOMETRY_INDEX_DETAIL_VARRAY_DETAIL_CONSTRUCT #endif // !BOOST_NO_CXX11_VARIADIC_TEMPLATES #endif // !BOOST_CONTAINER_VARRAY_DISABLE_EMPLACE diff --git a/boost/geometry/index/equal_to.hpp b/boost/geometry/index/equal_to.hpp index 5fbaa8209f..b0cf098f1d 100644 --- a/boost/geometry/index/equal_to.hpp +++ b/boost/geometry/index/equal_to.hpp @@ -24,6 +24,15 @@ struct equals } }; +template <typename Geometry, typename Tag> +struct equals<Geometry *, Tag> +{ + inline static bool apply(const Geometry * g1, const Geometry * g2) + { + return g1 == g2; + } +}; + template <typename T> struct equals<T, void> { diff --git a/boost/geometry/index/parameters.hpp b/boost/geometry/index/parameters.hpp index fd6df716ee..2b94907686 100644 --- a/boost/geometry/index/parameters.hpp +++ b/boost/geometry/index/parameters.hpp @@ -70,8 +70,7 @@ inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max. */ template <size_t MaxElements, - size_t MinElements = detail::default_min_elements_s<MaxElements>::value -> + size_t MinElements = detail::default_min_elements_s<MaxElements>::value> struct linear { BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1), diff --git a/boost/geometry/index/predicates.hpp b/boost/geometry/index/predicates.hpp index 10033abff8..3bb1bf4d87 100644 --- a/boost/geometry/index/predicates.hpp +++ b/boost/geometry/index/predicates.hpp @@ -2,7 +2,7 @@ // // Spatial query predicates // -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -43,10 +43,15 @@ bgi::query(spatial_index, bgi::contains(box), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::contains_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::contains_tag, false> contains(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::contains_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::contains_tag, + false + >(g); } /*! @@ -68,10 +73,15 @@ bgi::query(spatial_index, bgi::covered_by(box), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::covered_by_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::covered_by_tag, false> covered_by(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::covered_by_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::covered_by_tag, + false + >(g); } /*! @@ -93,10 +103,15 @@ bgi::query(spatial_index, bgi::covers(box), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::covers_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::covers_tag, false> covers(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::covers_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::covers_tag, + false + >(g); } /*! @@ -118,10 +133,15 @@ bgi::query(spatial_index, bgi::disjoint(box), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::disjoint_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::disjoint_tag, false> disjoint(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::disjoint_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::disjoint_tag, + false + >(g); } /*! @@ -145,10 +165,15 @@ bgi::query(spatial_index, bgi::intersects(polygon), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::intersects_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::intersects_tag, false> intersects(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::intersects_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::intersects_tag, + false + >(g); } /*! @@ -170,10 +195,15 @@ bgi::query(spatial_index, bgi::overlaps(box), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::overlaps_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::overlaps_tag, false> overlaps(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::overlaps_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::overlaps_tag, + false + >(g); } #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL @@ -192,10 +222,15 @@ returns true. \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::touches_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::touches_tag, false> touches(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::touches_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::touches_tag, + false + >(g); } #endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL @@ -219,10 +254,15 @@ bgi::query(spatial_index, bgi::within(box), std::back_inserter(result)); \param g The Geometry object. */ template <typename Geometry> inline -detail::spatial_predicate<Geometry, detail::within_tag, false> +detail::predicates::spatial_predicate<Geometry, detail::predicates::within_tag, false> within(Geometry const& g) { - return detail::spatial_predicate<Geometry, detail::within_tag, false>(g); + return detail::predicates::spatial_predicate + < + Geometry, + detail::predicates::within_tag, + false + >(g); } /*! @@ -259,10 +299,10 @@ std::back_inserter(result)); \param pred The unary predicate function or function object. */ template <typename UnaryPredicate> inline -detail::satisfies<UnaryPredicate, false> +detail::predicates::satisfies<UnaryPredicate, false> satisfies(UnaryPredicate const& pred) { - return detail::satisfies<UnaryPredicate, false>(pred); + return detail::predicates::satisfies<UnaryPredicate, false>(pred); } /*! @@ -289,10 +329,10 @@ Only one \c nearest() predicate may be used in a query. \param k The maximum number of values to return. */ template <typename Geometry> inline -detail::nearest<Geometry> +detail::predicates::nearest<Geometry> nearest(Geometry const& geometry, unsigned k) { - return detail::nearest<Geometry>(geometry, k); + return detail::predicates::nearest<Geometry>(geometry, k); } #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL @@ -319,15 +359,15 @@ Only one distance predicate (\c nearest() or \c path()) may be used in a query. \param k The maximum number of values to return. */ template <typename SegmentOrLinestring> inline -detail::path<SegmentOrLinestring> +detail::predicates::path<SegmentOrLinestring> path(SegmentOrLinestring const& linestring, unsigned k) { - return detail::path<SegmentOrLinestring>(linestring, k); + return detail::predicates::path<SegmentOrLinestring>(linestring, k); } #endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL -namespace detail { +namespace detail { namespace predicates { // operator! generators @@ -378,7 +418,7 @@ operator&&(boost::tuples::cons<Head, Tail> const& t, Pred const& p) >::apply(t, p); } -} // namespace detail +}} // namespace detail::predicates }}} // namespace boost::geometry::index diff --git a/boost/geometry/index/rtree.hpp b/boost/geometry/index/rtree.hpp index 503f47b89f..9d5d57d059 100644 --- a/boost/geometry/index/rtree.hpp +++ b/boost/geometry/index/rtree.hpp @@ -3,7 +3,7 @@ // R-tree implementation // // Copyright (c) 2008 Federico J. Fernandez. -// Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland. +// 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 @@ -96,12 +96,13 @@ namespace boost { namespace geometry { namespace index { /*! \brief The R-tree spatial index. -This is self-balancing spatial index capable to store various types of Values and balancing algorithms. +This is self-balancing spatial index capable to store various types of Values +and balancing algorithms. \par Parameters The user must pass a type defining the Parameters which will -be used in rtree creation process. This type is used e.g. to specify balancing algorithm -with specific parameters like min and max number of elements in node. +be used in rtree creation process. This type is used e.g. to specify balancing +algorithm with specific parameters like min and max number of elements in node. \par Predefined algorithms with compile-time parameters are: @@ -116,23 +117,31 @@ Predefined algorithms with run-time parameters are: \li \c boost::geometry::index::dynamic_rstar. \par IndexableGetter -The object of IndexableGetter type translates from Value to Indexable each time r-tree requires it. Which means that this -operation is done for each Value access. Therefore the IndexableGetter should return the Indexable by -const reference instead of a value. Default one can translate all types adapted to Point, Box or Segment -concepts (called Indexables). It also handles <tt>std::pair<Indexable, T></tt> and -<tt>boost::tuple<Indexable, ...></tt>. For example, if <tt>std::pair<Box, int></tt> is stored in the -container, the default IndexableGetter translates from <tt>std::pair<Box, int> const&</tt> to <tt>Box const&</tt>. +The object of IndexableGetter type translates from Value to Indexable each time +r-tree requires it. This means that this operation is done for each Value +access. Therefore the IndexableGetter should return the Indexable by +a reference type. The Indexable should not be calculated since it could harm +the performance. The default IndexableGetter can translate all types adapted +to Point, Box or Segment concepts (called Indexables). Furthermore, it can +handle <tt>std::pair<Indexable, T></tt>, <tt>boost::tuple<Indexable, ...></tt> +and <tt>std::tuple<Indexable, ...></tt> when possible. For example, for Value +of type <tt>std::pair<Box, int></tt>, the default IndexableGetter translates +from <tt>std::pair<Box, int> const&</tt> to <tt>Box const&</tt>. \par EqualTo -The object of EqualTo type compares Values and returns <tt>true</tt> if they're equal. It's similar to <tt>std::equal_to<></tt>. -The default EqualTo returns the result of <tt>boost::geometry::equals()</tt> for types adapted to some Geometry concept -defined in Boost.Geometry and the result of operator= for other types. Components of Pairs and Tuples are compared left-to-right. +The object of EqualTo type compares Values and returns <tt>true</tt> if they +are equal. It's similar to <tt>std::equal_to<></tt>. The default EqualTo +returns the result of <tt>boost::geometry::equals()</tt> for types adapted to +some Geometry concept defined in Boost.Geometry and the result of +<tt>operator==</tt> for other types. Components of Pairs and Tuples are +compared left-to-right. \tparam Value The type of objects stored in the container. \tparam Parameters Compile-time parameters. \tparam IndexableGetter The function object extracting Indexable from Value. \tparam EqualTo The function object comparing objects of type Value. -\tparam Allocator The allocator used to allocate/deallocate memory, construct/destroy nodes and Values. +\tparam Allocator The allocator used to allocate/deallocate memory, + construct/destroy nodes and Values. */ template < typename Value, @@ -188,7 +197,7 @@ private: typedef typename allocators_type::node_pointer node_pointer; typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; - typedef detail::rtree::node_auto_ptr<value_type, options_type, translator_type, box_type, allocators_type> node_auto_ptr; + typedef detail::rtree::subtree_destroyer<value_type, options_type, translator_type, box_type, allocators_type> subtree_destroyer; friend class detail::rtree::utilities::view<rtree>; #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL @@ -1088,6 +1097,8 @@ public: template <typename ValueOrIndexable> size_type count(ValueOrIndexable const& vori) const { + // the input should be convertible to Value or Indexable type + enum { as_val = 0, as_ind, dont_know }; typedef boost::mpl::int_ < @@ -1113,15 +1124,9 @@ public: indexable_type >::type value_or_indexable; - if ( !m_members.root ) - return 0; - - detail::rtree::visitors::count<value_or_indexable, value_type, options_type, translator_type, box_type, allocators_type> - count_v(vori, m_members.translator()); - - detail::rtree::apply_visitor(count_v, *m_members.root); - - return count_v.found_count; + // NOTE: If an object of convertible but not the same type is passed + // into the function, here a temporary will be created. + return this->template raw_count<value_or_indexable>(vori); } /*! @@ -1239,6 +1244,7 @@ private: inline void raw_insert(value_type const& value) { BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist"); + // CONSIDER: alternative - ignore invalid indexable or throw an exception BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid"); detail::rtree::visitors::insert< @@ -1356,7 +1362,7 @@ private: dst.m_members.parameters() = src.m_members.parameters(); } - // TODO use node_auto_ptr + // TODO use subtree_destroyer if ( dst.m_members.root ) { detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> @@ -1492,6 +1498,33 @@ private: return distance_v.finish(); } + + /*! + \brief Count elements corresponding to value or indexable. + + \par Exception-safety + strong + */ + template <typename ValueOrIndexable> + size_type raw_count(ValueOrIndexable const& vori) const + { + if ( !m_members.root ) + return 0; + + detail::rtree::visitors::count + < + ValueOrIndexable, + value_type, + options_type, + translator_type, + box_type, + allocators_type + > count_v(vori, m_members.translator()); + + detail::rtree::apply_visitor(count_v, *m_members.root); + + return count_v.found_count; + } struct members_holder : public translator_type |