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