]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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("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("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("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 |