1// Boost.Geometry Index
2//
3// R-tree algorithms parameters
4//
5// Copyright (c) 2011-2013 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_PARAMETERS_HPP
12#define BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
13
14#include <limits>
15
16namespace boost { namespace geometry { namespace index {
17
18namespace detail {
19
20template <size_t MaxElements>
21struct default_min_elements_s
22{
23 static const size_t raw_value = (MaxElements * 3) / 10;
24 static const size_t value = 1 <= raw_value ? raw_value : 1;
25};
26
27inline size_t default_min_elements_d()
28{
29 return (std::numeric_limits<size_t>::max)();
30}
31
32inline size_t default_min_elements_d_calc(size_t max_elements, size_t min_elements)
33{
34 if ( default_min_elements_d() == min_elements )
35 {
36 size_t raw_value = (max_elements * 3) / 10;
37 return 1 <= raw_value ? raw_value : 1;
38 }
39
40 return min_elements;
41}
42
43template <size_t MaxElements>
44struct default_rstar_reinserted_elements_s
45{
46 static const size_t value = (MaxElements * 3) / 10;
47};
48
49inline size_t default_rstar_reinserted_elements_d()
50{
51 return (std::numeric_limits<size_t>::max)();
52}
53
54inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size_t reinserted_elements)
55{
56 if ( default_rstar_reinserted_elements_d() == reinserted_elements )
57 {
58 return (max_elements * 3) / 10;
59 }
60
61 return reinserted_elements;
62}
63
64} // namespace detail
65
66/*!
67\brief Linear r-tree creation algorithm parameters.
68
69\tparam MaxElements Maximum number of elements in nodes.
70\tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
71*/
72template <size_t MaxElements,
73 size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
74struct linear
75{
76 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
77 INVALID_STATIC_MIN_MAX_PARAMETERS, (linear));
78
79 static const size_t max_elements = MaxElements;
80 static const size_t min_elements = MinElements;
81
82 static size_t get_max_elements() { return MaxElements; }
83 static size_t get_min_elements() { return MinElements; }
84};
85
86/*!
87\brief Quadratic r-tree creation algorithm parameters.
88
89\tparam MaxElements Maximum number of elements in nodes.
90\tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
91*/
92template <size_t MaxElements,
93 size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
94struct quadratic
95{
96 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
97 INVALID_STATIC_MIN_MAX_PARAMETERS, (quadratic));
98
99 static const size_t max_elements = MaxElements;
100 static const size_t min_elements = MinElements;
101
102 static size_t get_max_elements() { return MaxElements; }
103 static size_t get_min_elements() { return MinElements; }
104};
105
106/*!
107\brief R*-tree creation algorithm parameters.
108
109\tparam MaxElements Maximum number of elements in nodes.
110\tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
111\tparam ReinsertedElements The number of elements reinserted by forced reinsertions algorithm.
112 If 0 forced reinsertions are disabled. Maximum value is Max+1-Min.
113 Greater values are truncated. Default: 0.3*Max.
114\tparam OverlapCostThreshold The number of most suitable leafs taken into account while choosing
115 the leaf node to which currently inserted value will be added. If
116 value is in range (0, MaxElements) - the algorithm calculates
117 nearly minimum overlap cost, otherwise all leafs are analyzed
118 and true minimum overlap cost is calculated. Default: 32.
119*/
120template <size_t MaxElements,
121 size_t MinElements = detail::default_min_elements_s<MaxElements>::value,
122 size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value,
123 size_t OverlapCostThreshold = 32>
124struct rstar
125{
126 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
127 INVALID_STATIC_MIN_MAX_PARAMETERS, (rstar));
128
129 static const size_t max_elements = MaxElements;
130 static const size_t min_elements = MinElements;
131 static const size_t reinserted_elements = ReinsertedElements;
132 static const size_t overlap_cost_threshold = OverlapCostThreshold;
133
134 static size_t get_max_elements() { return MaxElements; }
135 static size_t get_min_elements() { return MinElements; }
136 static size_t get_reinserted_elements() { return ReinsertedElements; }
137 static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; }
138};
139
140//template <size_t MaxElements, size_t MinElements>
141//struct kmeans
142//{
143// static const size_t max_elements = MaxElements;
144// static const size_t min_elements = MinElements;
145//};
146
147/*!
148\brief Linear r-tree creation algorithm parameters - run-time version.
149*/
150class dynamic_linear
151{
152public:
153 /*!
154 \brief The constructor.
155
156 \param max_elements Maximum number of elements in nodes.
157 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
158 */
159 dynamic_linear(size_t max_elements,
160 size_t min_elements = detail::default_min_elements_d())
161 : m_max_elements(max_elements)
162 , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
163 {
164 if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
165 detail::throw_invalid_argument(str: "invalid min or/and max parameters of dynamic_linear");
166 }
167
168 size_t get_max_elements() const { return m_max_elements; }
169 size_t get_min_elements() const { return m_min_elements; }
170
171private:
172 size_t m_max_elements;
173 size_t m_min_elements;
174};
175
176/*!
177\brief Quadratic r-tree creation algorithm parameters - run-time version.
178*/
179class dynamic_quadratic
180{
181public:
182 /*!
183 \brief The constructor.
184
185 \param max_elements Maximum number of elements in nodes.
186 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
187 */
188 dynamic_quadratic(size_t max_elements,
189 size_t min_elements = detail::default_min_elements_d())
190 : m_max_elements(max_elements)
191 , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
192 {
193 if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
194 detail::throw_invalid_argument(str: "invalid min or/and max parameters of dynamic_quadratic");
195 }
196
197 size_t get_max_elements() const { return m_max_elements; }
198 size_t get_min_elements() const { return m_min_elements; }
199
200private:
201 size_t m_max_elements;
202 size_t m_min_elements;
203};
204
205/*!
206\brief R*-tree creation algorithm parameters - run-time version.
207*/
208class dynamic_rstar
209{
210public:
211 /*!
212 \brief The constructor.
213
214 \param max_elements Maximum number of elements in nodes.
215 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
216 \param reinserted_elements The number of elements reinserted by forced reinsertions algorithm.
217 If 0 forced reinsertions are disabled. Maximum value is Max-Min+1.
218 Greater values are truncated. Default: 0.3*Max.
219 \param overlap_cost_threshold The number of most suitable leafs taken into account while choosing
220 the leaf node to which currently inserted value will be added. If
221 value is in range (0, MaxElements) - the algorithm calculates
222 nearly minimum overlap cost, otherwise all leafs are analyzed
223 and true minimum overlap cost is calculated. Default: 32.
224 */
225 dynamic_rstar(size_t max_elements,
226 size_t min_elements = detail::default_min_elements_d(),
227 size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(),
228 size_t overlap_cost_threshold = 32)
229 : m_max_elements(max_elements)
230 , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
231 , m_reinserted_elements(detail::default_rstar_reinserted_elements_d_calc(max_elements, reinserted_elements))
232 , m_overlap_cost_threshold(overlap_cost_threshold)
233 {
234 if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
235 detail::throw_invalid_argument(str: "invalid min or/and max parameters of dynamic_rstar");
236 }
237
238 size_t get_max_elements() const { return m_max_elements; }
239 size_t get_min_elements() const { return m_min_elements; }
240 size_t get_reinserted_elements() const { return m_reinserted_elements; }
241 size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; }
242
243private:
244 size_t m_max_elements;
245 size_t m_min_elements;
246 size_t m_reinserted_elements;
247 size_t m_overlap_cost_threshold;
248};
249
250}}} // namespace boost::geometry::index
251
252#endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
253

source code of boost/boost/geometry/index/parameters.hpp