rtree/node/node.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree nodes
0004 //
0005 // Copyright (c) 2011-2023 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2020.
0008 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP
0017
0018 #include <type_traits>
0019
0020 #include <boost/container/vector.hpp>
0021
0022 #include <boost/geometry/core/static_assert.hpp>
0023
0024 #include <boost/geometry/index/detail/varray.hpp>
0025
0026 #include <boost/geometry/index/detail/rtree/node/concept.hpp>
0027 #include <boost/geometry/index/detail/rtree/node/pairs.hpp>
0028 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0029 #include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp>
0030
0031 //#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp>
0032 //#include <boost/geometry/index/detail/rtree/node/weak_dynamic.hpp>
0033 //#include <boost/geometry/index/detail/rtree/node/weak_static.hpp>
0034
0035 #include <boost/geometry/index/detail/rtree/node/variant_visitor.hpp>
0036 #include <boost/geometry/index/detail/rtree/node/variant_dynamic.hpp>
0037 #include <boost/geometry/index/detail/rtree/node/variant_static.hpp>
0038
0039 #include <boost/geometry/algorithms/expand.hpp>
0040
0041 #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
0042 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
0043
0044 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
0045 #include <boost/geometry/index/detail/is_bounding_geometry.hpp>
0046
0047 namespace boost { namespace geometry { namespace index {
0048
0049 namespace detail { namespace rtree {
0050
0051 // elements box
0052
0053 template <typename Box, typename FwdIter, typename Translator, typename Strategy>
0054 inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr,
0055                         Strategy const& strategy)
0056 {
0057     Box result;
0058
0059     // Only here to suppress 'uninitialized local variable used' warning
0060     // until the suggestion below is not implemented
0061     geometry::assign_inverse(result);
0062
0063     //BOOST_GEOMETRY_INDEX_ASSERT(first != last, "non-empty range required");
0064     // NOTE: this is not elegant temporary solution,
0065     //       reference to box could be passed as parameter and bool returned
0066     if ( first == last )
0067         return result;
0068
0069     detail::bounds(element_indexable(*first, tr), result, strategy);
0070     ++first;
0071
0072     for ( ; first != last ; ++first )
0073         detail::expand(result, element_indexable(*first, tr), strategy);
0074
0075     return result;
0076 }
0077
0078 // Enlarge bounds of a leaf node WRT epsilon if needed.
0079 // It's because Points and Segments are compared WRT machine epsilon.
0080 // This ensures that leafs bounds correspond to the stored elements.
0081 // NOTE: this is done only if the Indexable is not a Box
0082 //       in the future don't do it also for NSphere
0083 template <typename Box, typename FwdIter, typename Translator, typename Strategy>
0084 inline Box values_box(FwdIter first, FwdIter last, Translator const& tr,
0085                       Strategy const& strategy)
0086 {
0087     typedef typename std::iterator_traits<FwdIter>::value_type element_type;
0088     BOOST_GEOMETRY_STATIC_ASSERT((is_leaf_element<element_type>::value),
0089         "This function should be called only for elements of leaf nodes.",
0090         element_type);
0091
0092     Box result = elements_box<Box>(first, last, tr, strategy);
0093
0094 #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
0095     if (BOOST_GEOMETRY_CONDITION((
0096         ! is_bounding_geometry
0097             <
0098                 typename indexable_type<Translator>::type
0099             >::value)))
0100     {
0101         geometry::detail::expand_by_epsilon(result);
0102     }
0103 #endif
0104
0105     return result;
0106 }
0107
0108 // destroys subtree if the element is internal node's element
0109 template <typename MembersHolder>
0110 struct destroy_element
0111 {
0112     typedef typename MembersHolder::parameters_type parameters_type;
0113     typedef typename MembersHolder::allocators_type allocators_type;
0114
0115     typedef typename MembersHolder::internal_node internal_node;
0116     typedef typename MembersHolder::leaf leaf;
0117
0118     inline static void apply(typename internal_node::elements_type::value_type & element,
0119                              allocators_type & allocators)
0120     {
0121          detail::rtree::visitors::destroy<MembersHolder>::apply(element.second, allocators);
0122
0123          element.second = 0;
0124     }
0125
0126     inline static void apply(typename leaf::elements_type::value_type &,
0127                              allocators_type &)
0128     {}
0129 };
0130
0131 // destroys stored subtrees if internal node's elements are passed
0132 template <typename MembersHolder>
0133 struct destroy_elements
0134 {
0135     typedef typename MembersHolder::value_type value_type;
0136     typedef typename MembersHolder::allocators_type allocators_type;
0137
0138     template <typename Range>
0139     inline static void apply(Range & elements, allocators_type & allocators)
0140     {
0141         apply(boost::begin(elements), boost::end(elements), allocators);
0142     }
0143
0144     template <typename It>
0145     inline static void apply(It first, It last, allocators_type & allocators)
0146     {
0147         typedef std::is_same
0148             <
0149                 value_type, typename std::iterator_traits<It>::value_type
0150             > is_range_of_values;
0151
0152         apply_dispatch(first, last, allocators, is_range_of_values());
0153     }
0154
0155 private:
0156     template <typename It>
0157     inline static void apply_dispatch(It first, It last, allocators_type & allocators,
0158                                       std::false_type /*is_range_of_values*/)
0159     {
0160         for ( ; first != last ; ++first )
0161         {
0162             detail::rtree::visitors::destroy<MembersHolder>::apply(first->second, allocators);
0163
0164             first->second = 0;
0165         }
0166     }
0167
0168     template <typename It>
0169     inline static void apply_dispatch(It /*first*/, It /*last*/, allocators_type & /*allocators*/,
0170                                       std::true_type /*is_range_of_values*/)
0171     {}
0172 };
0173
0174 // clears node, deletes all subtrees stored in node
0175 /*
0176 template <typename MembersHolder>
0177 struct clear_node
0178 {
0179     typedef typename MembersHolder::parameters_type parameters_type;
0180     typedef typename MembersHolder::allocators_type allocators_type;
0181
0182     typedef typename MembersHolder::node node;
0183     typedef typename MembersHolder::internal_node internal_node;
0184     typedef typename MembersHolder::leaf leaf;
0185
0186     inline static void apply(node & node, allocators_type & allocators)
0187     {
0188         rtree::visitors::is_leaf<MembersHolder> ilv;
0189         rtree::apply_visitor(ilv, node);
0190         if ( ilv.result )
0191         {
0192             apply(rtree::get<leaf>(node), allocators);
0193         }
0194         else
0195         {
0196             apply(rtree::get<internal_node>(node), allocators);
0197         }
0198     }
0199
0200     inline static void apply(internal_node & internal_node, allocators_type & allocators)
0201     {
0202         destroy_elements<MembersHolder>::apply(rtree::elements(internal_node), allocators);
0203         rtree::elements(internal_node).clear();
0204     }
0205
0206     inline static void apply(leaf & leaf, allocators_type &)
0207     {
0208         rtree::elements(leaf).clear();
0209     }
0210 };
0211 */
0212
0213 template <typename Container, typename Iterator>
0214 void move_from_back(Container & container, Iterator it)
0215 {
0216     BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container");
0217     Iterator back_it = container.end();
0218     --back_it;
0219     if ( it != back_it )
0220     {
0221         *it = std::move(*back_it);                                                             // MAY THROW (copy)
0222     }
0223 }
0224
0225 }} // namespace detail::rtree
0226
0227 }}} // namespace boost::geometry::index
0228
0229 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP