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