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