]>
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 | // |
20effc67 TL |
7 | // This file was modified by Oracle on 2019-2020. |
8 | // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates. | |
92f5a8d4 TL |
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 | ||
20effc67 | 21 | #include <boost/geometry/core/static_assert.hpp> |
b32b8144 FG |
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 | { | |
20effc67 TL |
86 | BOOST_GEOMETRY_STATIC_ASSERT((0 < MinElements && 2*MinElements <= MaxElements+1), |
87 | "Invalid MaxElements or MinElements.", | |
88 | std::integer_sequence<size_t, MaxElements, MinElements>); | |
7c673cae FG |
89 | |
90 | static const size_t max_elements = MaxElements; | |
91 | static const size_t min_elements = MinElements; | |
92 | ||
93 | static size_t get_max_elements() { return MaxElements; } | |
94 | static size_t get_min_elements() { return MinElements; } | |
95 | }; | |
96 | ||
97 | /*! | |
98 | \brief Quadratic r-tree creation algorithm parameters. | |
99 | ||
100 | \tparam MaxElements Maximum number of elements in nodes. | |
101 | \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max. | |
102 | */ | |
103 | template <size_t MaxElements, | |
104 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value> | |
105 | struct quadratic | |
106 | { | |
20effc67 TL |
107 | BOOST_GEOMETRY_STATIC_ASSERT((0 < MinElements && 2*MinElements <= MaxElements+1), |
108 | "Invalid MaxElements or MinElements.", | |
109 | std::integer_sequence<size_t, MaxElements, MinElements>); | |
7c673cae FG |
110 | |
111 | static const size_t max_elements = MaxElements; | |
112 | static const size_t min_elements = MinElements; | |
113 | ||
114 | static size_t get_max_elements() { return MaxElements; } | |
115 | static size_t get_min_elements() { return MinElements; } | |
116 | }; | |
117 | ||
118 | /*! | |
119 | \brief R*-tree creation algorithm parameters. | |
120 | ||
121 | \tparam MaxElements Maximum number of elements in nodes. | |
122 | \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max. | |
123 | \tparam ReinsertedElements The number of elements reinserted by forced reinsertions algorithm. | |
124 | If 0 forced reinsertions are disabled. Maximum value is Max+1-Min. | |
125 | Greater values are truncated. Default: 0.3*Max. | |
126 | \tparam OverlapCostThreshold The number of most suitable leafs taken into account while choosing | |
127 | the leaf node to which currently inserted value will be added. If | |
128 | value is in range (0, MaxElements) - the algorithm calculates | |
129 | nearly minimum overlap cost, otherwise all leafs are analyzed | |
130 | and true minimum overlap cost is calculated. Default: 32. | |
131 | */ | |
132 | template <size_t MaxElements, | |
133 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value, | |
134 | size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value, | |
135 | size_t OverlapCostThreshold = 32> | |
136 | struct rstar | |
137 | { | |
20effc67 TL |
138 | BOOST_GEOMETRY_STATIC_ASSERT((0 < MinElements && 2*MinElements <= MaxElements+1), |
139 | "Invalid MaxElements or MinElements.", | |
140 | std::integer_sequence<size_t, MaxElements, MinElements>); | |
7c673cae FG |
141 | |
142 | static const size_t max_elements = MaxElements; | |
143 | static const size_t min_elements = MinElements; | |
144 | static const size_t reinserted_elements = ReinsertedElements; | |
145 | static const size_t overlap_cost_threshold = OverlapCostThreshold; | |
146 | ||
147 | static size_t get_max_elements() { return MaxElements; } | |
148 | static size_t get_min_elements() { return MinElements; } | |
149 | static size_t get_reinserted_elements() { return ReinsertedElements; } | |
150 | static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; } | |
151 | }; | |
152 | ||
153 | //template <size_t MaxElements, size_t MinElements> | |
154 | //struct kmeans | |
155 | //{ | |
156 | // static const size_t max_elements = MaxElements; | |
157 | // static const size_t min_elements = MinElements; | |
158 | //}; | |
159 | ||
160 | /*! | |
161 | \brief Linear r-tree creation algorithm parameters - run-time version. | |
162 | */ | |
163 | class dynamic_linear | |
164 | { | |
165 | public: | |
166 | /*! | |
167 | \brief The constructor. | |
168 | ||
169 | \param max_elements Maximum number of elements in nodes. | |
170 | \param min_elements Minimum number of elements in nodes. Default: 0.3*Max. | |
171 | */ | |
b32b8144 FG |
172 | explicit dynamic_linear(size_t max_elements, |
173 | size_t min_elements = detail::default_min_elements_d()) | |
7c673cae FG |
174 | : m_max_elements(max_elements) |
175 | , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements)) | |
176 | { | |
177 | if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1)) | |
178 | detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_linear"); | |
179 | } | |
180 | ||
181 | size_t get_max_elements() const { return m_max_elements; } | |
182 | size_t get_min_elements() const { return m_min_elements; } | |
183 | ||
184 | private: | |
185 | size_t m_max_elements; | |
186 | size_t m_min_elements; | |
187 | }; | |
188 | ||
189 | /*! | |
190 | \brief Quadratic r-tree creation algorithm parameters - run-time version. | |
191 | */ | |
192 | class dynamic_quadratic | |
193 | { | |
194 | public: | |
195 | /*! | |
196 | \brief The constructor. | |
197 | ||
198 | \param max_elements Maximum number of elements in nodes. | |
199 | \param min_elements Minimum number of elements in nodes. Default: 0.3*Max. | |
200 | */ | |
b32b8144 FG |
201 | explicit dynamic_quadratic(size_t max_elements, |
202 | size_t min_elements = detail::default_min_elements_d()) | |
7c673cae FG |
203 | : m_max_elements(max_elements) |
204 | , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements)) | |
205 | { | |
206 | if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1)) | |
207 | detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_quadratic"); | |
208 | } | |
209 | ||
210 | size_t get_max_elements() const { return m_max_elements; } | |
211 | size_t get_min_elements() const { return m_min_elements; } | |
212 | ||
213 | private: | |
214 | size_t m_max_elements; | |
215 | size_t m_min_elements; | |
216 | }; | |
217 | ||
218 | /*! | |
219 | \brief R*-tree creation algorithm parameters - run-time version. | |
220 | */ | |
221 | class dynamic_rstar | |
222 | { | |
223 | public: | |
224 | /*! | |
225 | \brief The constructor. | |
226 | ||
227 | \param max_elements Maximum number of elements in nodes. | |
228 | \param min_elements Minimum number of elements in nodes. Default: 0.3*Max. | |
229 | \param reinserted_elements The number of elements reinserted by forced reinsertions algorithm. | |
230 | If 0 forced reinsertions are disabled. Maximum value is Max-Min+1. | |
231 | Greater values are truncated. Default: 0.3*Max. | |
232 | \param overlap_cost_threshold The number of most suitable leafs taken into account while choosing | |
233 | the leaf node to which currently inserted value will be added. If | |
234 | value is in range (0, MaxElements) - the algorithm calculates | |
235 | nearly minimum overlap cost, otherwise all leafs are analyzed | |
236 | and true minimum overlap cost is calculated. Default: 32. | |
237 | */ | |
b32b8144 FG |
238 | explicit dynamic_rstar(size_t max_elements, |
239 | size_t min_elements = detail::default_min_elements_d(), | |
240 | size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(), | |
241 | size_t overlap_cost_threshold = 32) | |
7c673cae FG |
242 | : m_max_elements(max_elements) |
243 | , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements)) | |
244 | , m_reinserted_elements(detail::default_rstar_reinserted_elements_d_calc(max_elements, reinserted_elements)) | |
245 | , m_overlap_cost_threshold(overlap_cost_threshold) | |
246 | { | |
247 | if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1)) | |
248 | detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_rstar"); | |
249 | } | |
250 | ||
251 | size_t get_max_elements() const { return m_max_elements; } | |
252 | size_t get_min_elements() const { return m_min_elements; } | |
253 | size_t get_reinserted_elements() const { return m_reinserted_elements; } | |
254 | size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; } | |
255 | ||
256 | private: | |
257 | size_t m_max_elements; | |
258 | size_t m_min_elements; | |
259 | size_t m_reinserted_elements; | |
260 | size_t m_overlap_cost_threshold; | |
261 | }; | |
262 | ||
92f5a8d4 TL |
263 | |
264 | template <typename Parameters, typename Strategy> | |
265 | class parameters | |
266 | : public Parameters | |
267 | , private Strategy | |
268 | { | |
269 | public: | |
270 | parameters() | |
271 | : Parameters(), Strategy() | |
272 | {} | |
273 | ||
274 | parameters(Parameters const& params) | |
275 | : Parameters(params), Strategy() | |
276 | {} | |
277 | ||
278 | parameters(Parameters const& params, Strategy const& strategy) | |
279 | : Parameters(params), Strategy(strategy) | |
280 | {} | |
281 | ||
282 | Strategy const& strategy() const | |
283 | { | |
284 | return static_cast<Strategy const&>(*this); | |
285 | } | |
286 | }; | |
287 | ||
288 | ||
289 | namespace detail | |
290 | { | |
291 | ||
292 | template <typename Parameters> | |
293 | struct strategy_type | |
294 | { | |
295 | typedef default_strategy type; | |
296 | typedef default_strategy result_type; | |
297 | }; | |
298 | ||
299 | template <typename Parameters, typename Strategy> | |
300 | struct strategy_type< parameters<Parameters, Strategy> > | |
301 | { | |
302 | typedef Strategy type; | |
303 | typedef Strategy const& result_type; | |
304 | }; | |
305 | ||
306 | ||
307 | template <typename Parameters> | |
308 | struct get_strategy_impl | |
309 | { | |
310 | static inline default_strategy apply(Parameters const&) | |
311 | { | |
312 | return default_strategy(); | |
313 | } | |
314 | }; | |
315 | ||
316 | template <typename Parameters, typename Strategy> | |
317 | struct get_strategy_impl<parameters<Parameters, Strategy> > | |
318 | { | |
319 | static inline Strategy const& apply(parameters<Parameters, Strategy> const& parameters) | |
320 | { | |
321 | return parameters.strategy(); | |
322 | } | |
323 | }; | |
324 | ||
325 | template <typename Parameters> | |
326 | inline typename strategy_type<Parameters>::result_type | |
327 | get_strategy(Parameters const& parameters) | |
328 | { | |
329 | return get_strategy_impl<Parameters>::apply(parameters); | |
330 | } | |
331 | ||
332 | } // namespace detail | |
333 | ||
334 | ||
7c673cae FG |
335 | }}} // namespace boost::geometry::index |
336 | ||
337 | #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP |