1 // Boost.Geometry Index
2 //
3 // R-tree algorithms parameters
4 //
5 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
6 //
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 //
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
18
19 #include <limits>
20
21 #include <boost/mpl/assert.hpp>
22
23 #include <boost/geometry/index/detail/exception.hpp>
24
25
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
default_min_elements_d()37 inline size_t default_min_elements_d()
38 {
39 return (std::numeric_limits<size_t>::max)();
40 }
41
default_min_elements_d_calc(size_t max_elements,size_t min_elements)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
default_rstar_reinserted_elements_d()59 inline size_t default_rstar_reinserted_elements_d()
60 {
61 return (std::numeric_limits<size_t>::max)();
62 }
63
default_rstar_reinserted_elements_d_calc(size_t max_elements,size_t reinserted_elements)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
get_max_elementsboost::geometry::index::linear92 static size_t get_max_elements() { return MaxElements; }
get_min_elementsboost::geometry::index::linear93 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
get_max_elementsboost::geometry::index::quadratic112 static size_t get_max_elements() { return MaxElements; }
get_min_elementsboost::geometry::index::quadratic113 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
get_max_elementsboost::geometry::index::rstar144 static size_t get_max_elements() { return MaxElements; }
get_min_elementsboost::geometry::index::rstar145 static size_t get_min_elements() { return MinElements; }
get_reinserted_elementsboost::geometry::index::rstar146 static size_t get_reinserted_elements() { return ReinsertedElements; }
get_overlap_cost_thresholdboost::geometry::index::rstar147 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 */
dynamic_linear(size_t max_elements,size_t min_elements=detail::default_min_elements_d ())169 explicit dynamic_linear(size_t max_elements,
170 size_t min_elements = detail::default_min_elements_d())
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
get_max_elements() const178 size_t get_max_elements() const { return m_max_elements; }
get_min_elements() const179 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 */
dynamic_quadratic(size_t max_elements,size_t min_elements=detail::default_min_elements_d ())198 explicit dynamic_quadratic(size_t max_elements,
199 size_t min_elements = detail::default_min_elements_d())
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
get_max_elements() const207 size_t get_max_elements() const { return m_max_elements; }
get_min_elements() const208 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 */
dynamic_rstar(size_t max_elements,size_t min_elements=detail::default_min_elements_d (),size_t reinserted_elements=detail::default_rstar_reinserted_elements_d (),size_t overlap_cost_threshold=32)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)
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
get_max_elements() const248 size_t get_max_elements() const { return m_max_elements; }
get_min_elements() const249 size_t get_min_elements() const { return m_min_elements; }
get_reinserted_elements() const250 size_t get_reinserted_elements() const { return m_reinserted_elements; }
get_overlap_cost_threshold() const251 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
260
261 template <typename Parameters, typename Strategy>
262 class parameters
263 : public Parameters
264 , private Strategy
265 {
266 public:
parameters()267 parameters()
268 : Parameters(), Strategy()
269 {}
270
parameters(Parameters const & params)271 parameters(Parameters const& params)
272 : Parameters(params), Strategy()
273 {}
274
parameters(Parameters const & params,Strategy const & strategy)275 parameters(Parameters const& params, Strategy const& strategy)
276 : Parameters(params), Strategy(strategy)
277 {}
278
strategy() const279 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 {
applyboost::geometry::index::detail::get_strategy_impl307 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 {
applyboost::geometry::index::detail::get_strategy_impl316 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
get_strategy(Parameters const & parameters)324 get_strategy(Parameters const& parameters)
325 {
326 return get_strategy_impl<Parameters>::apply(parameters);
327 }
328
329 } // namespace detail
330
331
332 }}} // namespace boost::geometry::index
333
334 #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
335