diff options
Diffstat (limited to 'boost/geometry/index/detail/rtree')
21 files changed, 292 insertions, 455 deletions
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; } |