]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree algorithms parameters | |
4 | // | |
b32b8144 | 5 | // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland. |
7c673cae | 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_PARAMETERS_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_PARAMETERS_HPP | |
17 | ||
b32b8144 | 18 | |
7c673cae FG |
19 | #include <limits> |
20 | ||
b32b8144 FG |
21 | #include <boost/mpl/assert.hpp> |
22 | ||
23 | #include <boost/geometry/index/detail/exception.hpp> | |
24 | ||
25 | ||
7c673cae FG |
26 | namespace boost { namespace geometry { namespace index { |
27 | ||
28 | namespace detail { | |
29 | ||
30 | template <size_t MaxElements> | |
31 | struct default_min_elements_s | |
32 | { | |
33 | static const size_t raw_value = (MaxElements * 3) / 10; | |
34 | static const size_t value = 1 <= raw_value ? raw_value : 1; | |
35 | }; | |
36 | ||
37 | inline size_t default_min_elements_d() | |
38 | { | |
39 | return (std::numeric_limits<size_t>::max)(); | |
40 | } | |
41 | ||
42 | inline size_t default_min_elements_d_calc(size_t max_elements, size_t min_elements) | |
43 | { | |
44 | if ( default_min_elements_d() == min_elements ) | |
45 | { | |
46 | size_t raw_value = (max_elements * 3) / 10; | |
47 | return 1 <= raw_value ? raw_value : 1; | |
48 | } | |
49 | ||
50 | return min_elements; | |
51 | } | |
52 | ||
53 | template <size_t MaxElements> | |
54 | struct default_rstar_reinserted_elements_s | |
55 | { | |
56 | static const size_t value = (MaxElements * 3) / 10; | |
57 | }; | |
58 | ||
59 | inline size_t default_rstar_reinserted_elements_d() | |
60 | { | |
61 | return (std::numeric_limits<size_t>::max)(); | |
62 | } | |
63 | ||
64 | inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size_t reinserted_elements) | |
65 | { | |
66 | if ( default_rstar_reinserted_elements_d() == reinserted_elements ) | |
67 | { | |
68 | return (max_elements * 3) / 10; | |
69 | } | |
70 | ||
71 | return reinserted_elements; | |
72 | } | |
73 | ||
74 | } // namespace detail | |
75 | ||
76 | /*! | |
77 | \brief Linear r-tree creation algorithm parameters. | |
78 | ||
79 | \tparam MaxElements Maximum number of elements in nodes. | |
80 | \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max. | |
81 | */ | |
82 | template <size_t MaxElements, | |
83 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value> | |
84 | struct linear | |
85 | { | |
86 | BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1), | |
87 | INVALID_STATIC_MIN_MAX_PARAMETERS, (linear)); | |
88 | ||
89 | static const size_t max_elements = MaxElements; | |
90 | static const size_t min_elements = MinElements; | |
91 | ||
92 | static size_t get_max_elements() { return MaxElements; } | |
93 | static size_t get_min_elements() { return MinElements; } | |
94 | }; | |
95 | ||
96 | /*! | |
97 | \brief Quadratic r-tree creation algorithm parameters. | |
98 | ||
99 | \tparam MaxElements Maximum number of elements in nodes. | |
100 | \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max. | |
101 | */ | |
102 | template <size_t MaxElements, | |
103 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value> | |
104 | struct quadratic | |
105 | { | |
106 | BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1), | |
107 | INVALID_STATIC_MIN_MAX_PARAMETERS, (quadratic)); | |
108 | ||
109 | static const size_t max_elements = MaxElements; | |
110 | static const size_t min_elements = MinElements; | |
111 | ||
112 | static size_t get_max_elements() { return MaxElements; } | |
113 | static size_t get_min_elements() { return MinElements; } | |
114 | }; | |
115 | ||
116 | /*! | |
117 | \brief R*-tree creation algorithm parameters. | |
118 | ||
119 | \tparam MaxElements Maximum number of elements in nodes. | |
120 | \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max. | |
121 | \tparam ReinsertedElements The number of elements reinserted by forced reinsertions algorithm. | |
122 | If 0 forced reinsertions are disabled. Maximum value is Max+1-Min. | |
123 | Greater values are truncated. Default: 0.3*Max. | |
124 | \tparam OverlapCostThreshold The number of most suitable leafs taken into account while choosing | |
125 | the leaf node to which currently inserted value will be added. If | |
126 | value is in range (0, MaxElements) - the algorithm calculates | |
127 | nearly minimum overlap cost, otherwise all leafs are analyzed | |
128 | and true minimum overlap cost is calculated. Default: 32. | |
129 | */ | |
130 | template <size_t MaxElements, | |
131 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value, | |
132 | size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value, | |
133 | size_t OverlapCostThreshold = 32> | |
134 | struct rstar | |
135 | { | |
136 | BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1), | |
137 | INVALID_STATIC_MIN_MAX_PARAMETERS, (rstar)); | |
138 | ||
139 | static const size_t max_elements = MaxElements; | |
140 | static const size_t min_elements = MinElements; | |
141 | static const size_t reinserted_elements = ReinsertedElements; | |
142 | static const size_t overlap_cost_threshold = OverlapCostThreshold; | |
143 | ||
144 | static size_t get_max_elements() { return MaxElements; } | |
145 | static size_t get_min_elements() { return MinElements; } | |
146 | static size_t get_reinserted_elements() { return ReinsertedElements; } | |
147 | static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; } | |
148 | }; | |
149 | ||
150 | //template <size_t MaxElements, size_t MinElements> | |
151 | //struct kmeans | |
152 | //{ | |
153 | // static const size_t max_elements = MaxElements; | |
154 | // static const size_t min_elements = MinElements; | |
155 | //}; | |
156 | ||
157 | /*! | |
158 | \brief Linear r-tree creation algorithm parameters - run-time version. | |
159 | */ | |
160 | class dynamic_linear | |
161 | { | |
162 | public: | |
163 | /*! | |
164 | \brief The constructor. | |
165 | ||
166 | \param max_elements Maximum number of elements in nodes. | |
167 | \param min_elements Minimum number of elements in nodes. Default: 0.3*Max. | |
168 | */ | |
b32b8144 FG |
169 | explicit dynamic_linear(size_t max_elements, |
170 | size_t min_elements = detail::default_min_elements_d()) | |
7c673cae FG |
171 | : m_max_elements(max_elements) |
172 | , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements)) | |
173 | { | |
174 | if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1)) | |
175 | detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_linear"); | |
176 | } | |
177 | ||
178 | size_t get_max_elements() const { return m_max_elements; } | |
179 | size_t get_min_elements() const { return m_min_elements; } | |
180 | ||
181 | private: | |
182 | size_t m_max_elements; | |
183 | size_t m_min_elements; | |
184 | }; | |
185 | ||
186 | /*! | |
187 | \brief Quadratic r-tree creation algorithm parameters - run-time version. | |
188 | */ | |
189 | class dynamic_quadratic | |
190 | { | |
191 | public: | |
192 | /*! | |
193 | \brief The constructor. | |
194 | ||
195 | \param max_elements Maximum number of elements in nodes. | |
196 | \param min_elements Minimum number of elements in nodes. Default: 0.3*Max. | |
197 | */ | |
b32b8144 FG |
198 | explicit dynamic_quadratic(size_t max_elements, |
199 | size_t min_elements = detail::default_min_elements_d()) | |
7c673cae FG |
200 | : m_max_elements(max_elements) |
201 | , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements)) | |
202 | { | |
203 | if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1)) | |
204 | detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_quadratic"); | |
205 | } | |
206 | ||
207 | size_t get_max_elements() const { return m_max_elements; } | |
208 | size_t get_min_elements() const { return m_min_elements; } | |
209 | ||
210 | private: | |
211 | size_t m_max_elements; | |
212 | size_t m_min_elements; | |
213 | }; | |
214 | ||
215 | /*! | |
216 | \brief R*-tree creation algorithm parameters - run-time version. | |
217 | */ | |
218 | class dynamic_rstar | |
219 | { | |
220 | public: | |
221 | /*! | |
222 | \brief The constructor. | |
223 | ||
224 | \param max_elements Maximum number of elements in nodes. | |
225 | \param min_elements Minimum number of elements in nodes. Default: 0.3*Max. | |
226 | \param reinserted_elements The number of elements reinserted by forced reinsertions algorithm. | |
227 | If 0 forced reinsertions are disabled. Maximum value is Max-Min+1. | |
228 | Greater values are truncated. Default: 0.3*Max. | |
229 | \param overlap_cost_threshold The number of most suitable leafs taken into account while choosing | |
230 | the leaf node to which currently inserted value will be added. If | |
231 | value is in range (0, MaxElements) - the algorithm calculates | |
232 | nearly minimum overlap cost, otherwise all leafs are analyzed | |
233 | and true minimum overlap cost is calculated. Default: 32. | |
234 | */ | |
b32b8144 FG |
235 | explicit dynamic_rstar(size_t max_elements, |
236 | size_t min_elements = detail::default_min_elements_d(), | |
237 | size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(), | |
238 | size_t overlap_cost_threshold = 32) | |
7c673cae FG |
239 | : m_max_elements(max_elements) |
240 | , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements)) | |
241 | , m_reinserted_elements(detail::default_rstar_reinserted_elements_d_calc(max_elements, reinserted_elements)) | |
242 | , m_overlap_cost_threshold(overlap_cost_threshold) | |
243 | { | |
244 | if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1)) | |
245 | detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_rstar"); | |
246 | } | |
247 | ||
248 | size_t get_max_elements() const { return m_max_elements; } | |
249 | size_t get_min_elements() const { return m_min_elements; } | |
250 | size_t get_reinserted_elements() const { return m_reinserted_elements; } | |
251 | size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; } | |
252 | ||
253 | private: | |
254 | size_t m_max_elements; | |
255 | size_t m_min_elements; | |
256 | size_t m_reinserted_elements; | |
257 | size_t m_overlap_cost_threshold; | |
258 | }; | |
259 | ||
92f5a8d4 TL |
260 | |
261 | template <typename Parameters, typename Strategy> | |
262 | class parameters | |
263 | : public Parameters | |
264 | , private Strategy | |
265 | { | |
266 | public: | |
267 | parameters() | |
268 | : Parameters(), Strategy() | |
269 | {} | |
270 | ||
271 | parameters(Parameters const& params) | |
272 | : Parameters(params), Strategy() | |
273 | {} | |
274 | ||
275 | parameters(Parameters const& params, Strategy const& strategy) | |
276 | : Parameters(params), Strategy(strategy) | |
277 | {} | |
278 | ||
279 | Strategy const& strategy() const | |
280 | { | |
281 | return static_cast<Strategy const&>(*this); | |
282 | } | |
283 | }; | |
284 | ||
285 | ||
286 | namespace detail | |
287 | { | |
288 | ||
289 | template <typename Parameters> | |
290 | struct strategy_type | |
291 | { | |
292 | typedef default_strategy type; | |
293 | typedef default_strategy result_type; | |
294 | }; | |
295 | ||
296 | template <typename Parameters, typename Strategy> | |
297 | struct strategy_type< parameters<Parameters, Strategy> > | |
298 | { | |
299 | typedef Strategy type; | |
300 | typedef Strategy const& result_type; | |
301 | }; | |
302 | ||
303 | ||
304 | template <typename Parameters> | |
305 | struct get_strategy_impl | |
306 | { | |
307 | static inline default_strategy apply(Parameters const&) | |
308 | { | |
309 | return default_strategy(); | |
310 | } | |
311 | }; | |
312 | ||
313 | template <typename Parameters, typename Strategy> | |
314 | struct get_strategy_impl<parameters<Parameters, Strategy> > | |
315 | { | |
316 | static inline Strategy const& apply(parameters<Parameters, Strategy> const& parameters) | |
317 | { | |
318 | return parameters.strategy(); | |
319 | } | |
320 | }; | |
321 | ||
322 | template <typename Parameters> | |
323 | inline typename strategy_type<Parameters>::result_type | |
324 | get_strategy(Parameters const& parameters) | |
325 | { | |
326 | return get_strategy_impl<Parameters>::apply(parameters); | |
327 | } | |
328 | ||
329 | } // namespace detail | |
330 | ||
331 | ||
7c673cae FG |
332 | }}} // namespace boost::geometry::index |
333 | ||
334 | #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP |