Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // R-tree nodes
Chris@16: //
Chris@101: // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
Chris@16: 
Chris@16: #include <boost/container/vector.hpp>
Chris@16: #include <boost/geometry/index/detail/varray.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/node/concept.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/node/pairs.hpp>
Chris@101: #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
Chris@101: #include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp>
Chris@16: 
Chris@101: //#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
Chris@101: //#include <boost/geometry/index/detail/rtree/node/weak_dynamic.hpp>
Chris@101: //#include <boost/geometry/index/detail/rtree/node/weak_static.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/index/detail/rtree/node/variant_visitor.hpp>
Chris@101: #include <boost/geometry/index/detail/rtree/node/variant_dynamic.hpp>
Chris@101: #include <boost/geometry/index/detail/rtree/node/variant_static.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/expand.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/algorithms/bounds.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index {
Chris@16: 
Chris@16: namespace detail { namespace rtree {
Chris@16: 
Chris@16: // elements box
Chris@16: 
Chris@16: template <typename Box, typename FwdIter, typename Translator>
Chris@16: inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr)
Chris@16: {
Chris@16:     Box result;
Chris@16: 
Chris@16:     if ( first == last )
Chris@16:     {
Chris@16:         geometry::assign_inverse(result);
Chris@16:         return result;
Chris@16:     }
Chris@16: 
Chris@16:     detail::bounds(element_indexable(*first, tr), result);
Chris@16:     ++first;
Chris@16: 
Chris@16:     for ( ; first != last ; ++first )
Chris@16:         geometry::expand(result, element_indexable(*first, tr));
Chris@16: 
Chris@16:     return result;
Chris@16: }
Chris@16: 
Chris@16: // destroys subtree if the element is internal node's element
Chris@16: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct destroy_element
Chris@16: {
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
Chris@16:     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
Chris@16: 
Chris@101:     typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
Chris@16: 
Chris@16:     inline static void apply(typename internal_node::elements_type::value_type & element, Allocators & allocators)
Chris@16:     {
Chris@101:          subtree_destroyer dummy(element.second, allocators);
Chris@16:          element.second = 0;
Chris@16:     }
Chris@16: 
Chris@16:     inline static void apply(typename leaf::elements_type::value_type &, Allocators &) {}
Chris@16: };
Chris@16: 
Chris@16: // destroys stored subtrees if internal node's elements are passed
Chris@16: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct destroy_elements
Chris@16: {
Chris@101:     template <typename Range>
Chris@101:     inline static void apply(Range & elements, Allocators & allocators)
Chris@16:     {
Chris@101:         apply(boost::begin(elements), boost::end(elements), allocators);
Chris@16:     }
Chris@16: 
Chris@101:     template <typename It>
Chris@101:     inline static void apply(It first, It last, Allocators & allocators)
Chris@101:     {
Chris@101:         typedef boost::mpl::bool_<
Chris@101:             boost::is_same<
Chris@101:                 Value, typename std::iterator_traits<It>::value_type
Chris@101:             >::value
Chris@101:         > is_range_of_values;
Chris@16: 
Chris@101:         apply_dispatch(first, last, allocators, is_range_of_values());
Chris@101:     }
Chris@101: 
Chris@101: private:
Chris@101:     template <typename It>
Chris@101:     inline static void apply_dispatch(It first, It last, Allocators & allocators,
Chris@101:                                       boost::mpl::bool_<false> const& /*is_range_of_values*/)
Chris@16:     {
Chris@101:         typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
Chris@101: 
Chris@16:         for ( ; first != last ; ++first )
Chris@16:         {
Chris@101:             subtree_destroyer dummy(first->second, allocators);
Chris@16:             first->second = 0;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@101:     template <typename It>
Chris@101:     inline static void apply_dispatch(It /*first*/, It /*last*/, Allocators & /*allocators*/,
Chris@101:                                       boost::mpl::bool_<true> const& /*is_range_of_values*/)
Chris@16:     {}
Chris@16: };
Chris@16: 
Chris@16: // clears node, deletes all subtrees stored in node
Chris@16: template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
Chris@16: struct clear_node
Chris@16: {
Chris@16:     typedef typename Options::parameters_type parameters_type;
Chris@16: 
Chris@16:     typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
Chris@16:     typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
Chris@16:     typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
Chris@16: 
Chris@16:     inline static void apply(node & node, Allocators & allocators)
Chris@16:     {
Chris@16:         rtree::visitors::is_leaf<Value, Options, Box, Allocators> ilv;
Chris@16:         rtree::apply_visitor(ilv, node);
Chris@16:         if ( ilv.result )
Chris@16:         {
Chris@16:             apply(rtree::get<leaf>(node), allocators);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             apply(rtree::get<internal_node>(node), allocators);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     inline static void apply(internal_node & internal_node, Allocators & allocators)
Chris@16:     {
Chris@16:         destroy_elements<Value, Options, Translator, Box, Allocators>::apply(rtree::elements(internal_node), allocators);
Chris@16:         rtree::elements(internal_node).clear();
Chris@16:     }
Chris@16: 
Chris@16:     inline static void apply(leaf & leaf, Allocators &)
Chris@16:     {
Chris@16:         rtree::elements(leaf).clear();
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Container, typename Iterator>
Chris@16: void move_from_back(Container & container, Iterator it)
Chris@16: {
Chris@16:     BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container");
Chris@16:     Iterator back_it = container.end();
Chris@16:     --back_it;
Chris@16:     if ( it != back_it )
Chris@16:     {
Chris@16:         *it = boost::move(*back_it);                                                             // MAY THROW (copy)
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: }} // namespace detail::rtree
Chris@16: 
Chris@16: }}} // namespace boost::geometry::index
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP