]>
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 | // | |
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> | |
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> | |
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 | ||
109 | 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 | ||
115 | 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> | |
123 | inline static void apply(Range & elements, Allocators & allocators) | |
124 | { | |
125 | apply(boost::begin(elements), boost::end(elements), allocators); | |
126 | } | |
127 | ||
128 | template <typename It> | |
129 | 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> | |
142 | 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> | |
155 | 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 | ||
170 | 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 | ||
184 | 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 | ||
190 | inline static void apply(leaf & leaf, Allocators &) | |
191 | { | |
192 | rtree::elements(leaf).clear(); | |
193 | } | |
194 | }; | |
195 | ||
196 | template <typename Container, typename Iterator> | |
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 |