]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree nodes | |
4 | // | |
5 | // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
92f5a8d4 TL |
7 | // This file was modified by Oracle on 2019. |
8 | // Modifications copyright (c) 2019 Oracle and/or its affiliates. | |
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
10 | // | |
7c673cae FG |
11 | // Use, modification and distribution is subject to the Boost Software License, |
12 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
13 | // http://www.boost.org/LICENSE_1_0.txt) | |
14 | ||
15 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP | |
17 | ||
18 | #include <boost/container/vector.hpp> | |
19 | #include <boost/geometry/index/detail/varray.hpp> | |
20 | ||
21 | #include <boost/geometry/index/detail/rtree/node/concept.hpp> | |
22 | #include <boost/geometry/index/detail/rtree/node/pairs.hpp> | |
23 | #include <boost/geometry/index/detail/rtree/node/node_elements.hpp> | |
24 | #include <boost/geometry/index/detail/rtree/node/scoped_deallocator.hpp> | |
25 | ||
26 | //#include <boost/geometry/index/detail/rtree/node/weak_visitor.hpp> | |
27 | //#include <boost/geometry/index/detail/rtree/node/weak_dynamic.hpp> | |
28 | //#include <boost/geometry/index/detail/rtree/node/weak_static.hpp> | |
29 | ||
30 | #include <boost/geometry/index/detail/rtree/node/variant_visitor.hpp> | |
31 | #include <boost/geometry/index/detail/rtree/node/variant_dynamic.hpp> | |
32 | #include <boost/geometry/index/detail/rtree/node/variant_static.hpp> | |
33 | ||
34 | #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp> | |
35 | ||
36 | #include <boost/geometry/algorithms/expand.hpp> | |
37 | ||
38 | #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp> | |
39 | ||
40 | #include <boost/geometry/index/detail/algorithms/bounds.hpp> | |
41 | #include <boost/geometry/index/detail/is_bounding_geometry.hpp> | |
42 | ||
43 | namespace boost { namespace geometry { namespace index { | |
44 | ||
45 | namespace detail { namespace rtree { | |
46 | ||
47 | // elements box | |
48 | ||
92f5a8d4 TL |
49 | template <typename Box, typename FwdIter, typename Translator, typename Strategy> |
50 | inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr, | |
51 | Strategy const& strategy) | |
7c673cae FG |
52 | { |
53 | Box result; | |
54 | ||
55 | // Only here to suppress 'uninitialized local variable used' warning | |
56 | // until the suggestion below is not implemented | |
57 | geometry::assign_inverse(result); | |
58 | ||
59 | //BOOST_GEOMETRY_INDEX_ASSERT(first != last, "non-empty range required"); | |
60 | // NOTE: this is not elegant temporary solution, | |
61 | // reference to box could be passed as parameter and bool returned | |
62 | if ( first == last ) | |
63 | return result; | |
64 | ||
92f5a8d4 | 65 | detail::bounds(element_indexable(*first, tr), result, strategy); |
7c673cae FG |
66 | ++first; |
67 | ||
68 | for ( ; first != last ; ++first ) | |
92f5a8d4 | 69 | detail::expand(result, element_indexable(*first, tr), strategy); |
7c673cae FG |
70 | |
71 | return result; | |
72 | } | |
73 | ||
74 | // Enlarge bounds of a leaf node WRT epsilon if needed. | |
75 | // It's because Points and Segments are compared WRT machine epsilon. | |
76 | // This ensures that leafs bounds correspond to the stored elements. | |
77 | // NOTE: this is done only if the Indexable is not a Box | |
78 | // in the future don't do it also for NSphere | |
92f5a8d4 TL |
79 | template <typename Box, typename FwdIter, typename Translator, typename Strategy> |
80 | inline Box values_box(FwdIter first, FwdIter last, Translator const& tr, | |
81 | Strategy const& strategy) | |
7c673cae FG |
82 | { |
83 | typedef typename std::iterator_traits<FwdIter>::value_type element_type; | |
84 | BOOST_MPL_ASSERT_MSG((is_leaf_element<element_type>::value), | |
85 | SHOULD_BE_CALLED_ONLY_FOR_LEAF_ELEMENTS, | |
86 | (element_type)); | |
87 | ||
92f5a8d4 | 88 | Box result = elements_box<Box>(first, last, tr, strategy); |
7c673cae FG |
89 | |
90 | #ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON | |
91 | if (BOOST_GEOMETRY_CONDITION(( | |
92 | ! is_bounding_geometry | |
93 | < | |
94 | typename indexable_type<Translator>::type | |
95 | >::value))) | |
96 | { | |
97 | geometry::detail::expand_by_epsilon(result); | |
98 | } | |
99 | #endif | |
100 | ||
101 | return result; | |
102 | } | |
103 | ||
104 | // destroys subtree if the element is internal node's element | |
105 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
106 | struct destroy_element | |
107 | { | |
108 | typedef typename Options::parameters_type parameters_type; | |
109 | ||
110 | typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
111 | typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
112 | ||
113 | typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; | |
114 | ||
115 | inline static void apply(typename internal_node::elements_type::value_type & element, Allocators & allocators) | |
116 | { | |
117 | subtree_destroyer dummy(element.second, allocators); | |
118 | element.second = 0; | |
119 | } | |
120 | ||
121 | inline static void apply(typename leaf::elements_type::value_type &, Allocators &) {} | |
122 | }; | |
123 | ||
124 | // destroys stored subtrees if internal node's elements are passed | |
125 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
126 | struct destroy_elements | |
127 | { | |
128 | template <typename Range> | |
129 | inline static void apply(Range & elements, Allocators & allocators) | |
130 | { | |
131 | apply(boost::begin(elements), boost::end(elements), allocators); | |
132 | } | |
133 | ||
134 | template <typename It> | |
135 | inline static void apply(It first, It last, Allocators & allocators) | |
136 | { | |
137 | typedef boost::mpl::bool_< | |
138 | boost::is_same< | |
139 | Value, typename std::iterator_traits<It>::value_type | |
140 | >::value | |
141 | > is_range_of_values; | |
142 | ||
143 | apply_dispatch(first, last, allocators, is_range_of_values()); | |
144 | } | |
145 | ||
146 | private: | |
147 | template <typename It> | |
148 | inline static void apply_dispatch(It first, It last, Allocators & allocators, | |
149 | boost::mpl::bool_<false> const& /*is_range_of_values*/) | |
150 | { | |
151 | typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer; | |
152 | ||
153 | for ( ; first != last ; ++first ) | |
154 | { | |
155 | subtree_destroyer dummy(first->second, allocators); | |
156 | first->second = 0; | |
157 | } | |
158 | } | |
159 | ||
160 | template <typename It> | |
161 | inline static void apply_dispatch(It /*first*/, It /*last*/, Allocators & /*allocators*/, | |
162 | boost::mpl::bool_<true> const& /*is_range_of_values*/) | |
163 | {} | |
164 | }; | |
165 | ||
166 | // clears node, deletes all subtrees stored in node | |
167 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
168 | struct clear_node | |
169 | { | |
170 | typedef typename Options::parameters_type parameters_type; | |
171 | ||
172 | typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
173 | typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
174 | typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
175 | ||
176 | inline static void apply(node & node, Allocators & allocators) | |
177 | { | |
178 | rtree::visitors::is_leaf<Value, Options, Box, Allocators> ilv; | |
179 | rtree::apply_visitor(ilv, node); | |
180 | if ( ilv.result ) | |
181 | { | |
182 | apply(rtree::get<leaf>(node), allocators); | |
183 | } | |
184 | else | |
185 | { | |
186 | apply(rtree::get<internal_node>(node), allocators); | |
187 | } | |
188 | } | |
189 | ||
190 | inline static void apply(internal_node & internal_node, Allocators & allocators) | |
191 | { | |
192 | destroy_elements<Value, Options, Translator, Box, Allocators>::apply(rtree::elements(internal_node), allocators); | |
193 | rtree::elements(internal_node).clear(); | |
194 | } | |
195 | ||
196 | inline static void apply(leaf & leaf, Allocators &) | |
197 | { | |
198 | rtree::elements(leaf).clear(); | |
199 | } | |
200 | }; | |
201 | ||
202 | template <typename Container, typename Iterator> | |
203 | void move_from_back(Container & container, Iterator it) | |
204 | { | |
205 | BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container"); | |
206 | Iterator back_it = container.end(); | |
207 | --back_it; | |
208 | if ( it != back_it ) | |
209 | { | |
210 | *it = boost::move(*back_it); // MAY THROW (copy) | |
211 | } | |
212 | } | |
213 | ||
214 | }} // namespace detail::rtree | |
215 | ||
216 | }}} // namespace boost::geometry::index | |
217 | ||
218 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_NODE_NODE_HPP |