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 | |
16 | namespace boost { namespace geometry { namespace index { |
17 | |
18 | namespace detail { |
19 | |
20 | template <size_t MaxElements> |
21 | struct 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 | |
27 | inline size_t default_min_elements_d() |
28 | { |
29 | return (std::numeric_limits<size_t>::max)(); |
30 | } |
31 | |
32 | inline 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 | |
43 | template <size_t MaxElements> |
44 | struct default_rstar_reinserted_elements_s |
45 | { |
46 | static const size_t value = (MaxElements * 3) / 10; |
47 | }; |
48 | |
49 | inline size_t default_rstar_reinserted_elements_d() |
50 | { |
51 | return (std::numeric_limits<size_t>::max)(); |
52 | } |
53 | |
54 | inline 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 | */ |
72 | template <size_t MaxElements, |
73 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value> |
74 | struct 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 | */ |
92 | template <size_t MaxElements, |
93 | size_t MinElements = detail::default_min_elements_s<MaxElements>::value> |
94 | struct 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 | */ |
120 | template <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> |
124 | struct 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 | */ |
150 | class dynamic_linear |
151 | { |
152 | public: |
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 | |
171 | private: |
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 | */ |
179 | class dynamic_quadratic |
180 | { |
181 | public: |
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 | |
200 | private: |
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 | */ |
208 | class dynamic_rstar |
209 | { |
210 | public: |
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 | |
243 | private: |
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 | |