1 // Boost.Geometry Index
3 // R-tree algorithms parameters
5 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
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)
11 #ifndef BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
12 #define BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
16 namespace boost { namespace geometry { namespace index {
20 template <size_t MaxElements>
21 struct default_min_elements_s
23 static const size_t raw_value = (MaxElements * 3) / 10;
24 static const size_t value = 1 <= raw_value ? raw_value : 1;
27 inline size_t default_min_elements_d()
29 return (std::numeric_limits<size_t>::max)();
32 inline size_t default_min_elements_d_calc(size_t max_elements, size_t min_elements)
34 if ( default_min_elements_d() == min_elements )
36 size_t raw_value = (max_elements * 3) / 10;
37 return 1 <= raw_value ? raw_value : 1;
43 template <size_t MaxElements>
44 struct default_rstar_reinserted_elements_s
46 static const size_t value = (MaxElements * 3) / 10;
49 inline size_t default_rstar_reinserted_elements_d()
51 return (std::numeric_limits<size_t>::max)();
54 inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size_t reinserted_elements)
56 if ( default_rstar_reinserted_elements_d() == reinserted_elements )
58 return (max_elements * 3) / 10;
61 return reinserted_elements;
67 \brief Linear r-tree creation algorithm parameters.
69 \tparam MaxElements Maximum number of elements in nodes.
70 \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
72 template <size_t MaxElements,
73 size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
76 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
77 INVALID_STATIC_MIN_MAX_PARAMETERS, (linear));
79 static const size_t max_elements = MaxElements;
80 static const size_t min_elements = MinElements;
82 static size_t get_max_elements() { return MaxElements; }
83 static size_t get_min_elements() { return MinElements; }
87 \brief Quadratic r-tree creation algorithm parameters.
89 \tparam MaxElements Maximum number of elements in nodes.
90 \tparam MinElements Minimum number of elements in nodes. Default: 0.3*Max.
92 template <size_t MaxElements,
93 size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
96 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
97 INVALID_STATIC_MIN_MAX_PARAMETERS, (quadratic));
99 static const size_t max_elements = MaxElements;
100 static const size_t min_elements = MinElements;
102 static size_t get_max_elements() { return MaxElements; }
103 static size_t get_min_elements() { return MinElements; }
107 \brief R*-tree creation algorithm parameters.
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.
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>
126 BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
127 INVALID_STATIC_MIN_MAX_PARAMETERS, (rstar));
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;
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; }
140 //template <size_t MaxElements, size_t MinElements>
143 // static const size_t max_elements = MaxElements;
144 // static const size_t min_elements = MinElements;
148 \brief Linear r-tree creation algorithm parameters - run-time version.
154 \brief The constructor.
156 \param max_elements Maximum number of elements in nodes.
157 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
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))
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");
168 size_t get_max_elements() const { return m_max_elements; }
169 size_t get_min_elements() const { return m_min_elements; }
172 size_t m_max_elements;
173 size_t m_min_elements;
177 \brief Quadratic r-tree creation algorithm parameters - run-time version.
179 class dynamic_quadratic
183 \brief The constructor.
185 \param max_elements Maximum number of elements in nodes.
186 \param min_elements Minimum number of elements in nodes. Default: 0.3*Max.
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))
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");
197 size_t get_max_elements() const { return m_max_elements; }
198 size_t get_min_elements() const { return m_min_elements; }
201 size_t m_max_elements;
202 size_t m_min_elements;
206 \brief R*-tree creation algorithm parameters - run-time version.
212 \brief The constructor.
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.
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)
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");
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; }
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;
250 }}} // namespace boost::geometry::index
252 #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP