geometry/index/parameters.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree algorithms parameters
0004 //
0005 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2021.
0008 // Modifications copyright (c) 2019-2021 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
0016 #define BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
0017
0018 #include <limits>
0019
0020 #include <boost/geometry/core/static_assert.hpp>
0021
0022 #include <boost/geometry/index/detail/exception.hpp>
0023
0024 #include <boost/geometry/strategies/default_strategy.hpp>
0025
0026 namespace boost { namespace geometry { namespace index {
0027
0028 namespace detail {
0029
0030 template <size_t MaxElements>
0031 struct default_min_elements_s
0032 {
0033     static const size_t raw_value = (MaxElements * 3) / 10;
0034     static const size_t value = 1 <= raw_value ? raw_value : 1;
0035 };
0036
0037 inline size_t default_min_elements_d()
0038 {
0039     return (std::numeric_limits<size_t>::max)();
0040 }
0041
0042 inline size_t default_min_elements_d_calc(size_t max_elements, size_t min_elements)
0043 {
0044     if ( default_min_elements_d() == min_elements )
0045     {
0046         size_t raw_value = (max_elements * 3) / 10;
0047         return 1 <= raw_value ? raw_value : 1;
0048     }
0049
0050     return min_elements;
0051 }
0052
0053 template <size_t MaxElements>
0054 struct default_rstar_reinserted_elements_s
0055 {
0056     static const size_t value = (MaxElements * 3) / 10;
0057 };
0058
0059 inline size_t default_rstar_reinserted_elements_d()
0060 {
0061     return (std::numeric_limits<size_t>::max)();
0062 }
0063
0064 inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size_t reinserted_elements)
0065 {
0066     if ( default_rstar_reinserted_elements_d() == reinserted_elements )
0067     {
0068         return (max_elements * 3) / 10;
0069     }
0070
0071     return reinserted_elements;
0072 }
0073
0074 } // namespace detail
0075
0076 /*!
0077 \brief Linear r-tree creation algorithm parameters.
0078
0079 \tparam MaxElements     Maximum number of elements in nodes.
0080 \tparam MinElements     Minimum number of elements in nodes. Default: 0.3*Max.
0081 */
0082 template <size_t MaxElements,
0083           size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
0084 struct linear
0085 {
0086     BOOST_GEOMETRY_STATIC_ASSERT((0 < MinElements && 2*MinElements <= MaxElements+1),
0087         "Invalid MaxElements or MinElements.",
0088         std::integer_sequence<size_t, MaxElements, MinElements>);
0089
0090     static const size_t max_elements = MaxElements;
0091     static const size_t min_elements = MinElements;
0092
0093     static size_t get_max_elements() { return MaxElements; }
0094     static size_t get_min_elements() { return MinElements; }
0095 };
0096
0097 /*!
0098 \brief Quadratic r-tree creation algorithm parameters.
0099
0100 \tparam MaxElements     Maximum number of elements in nodes.
0101 \tparam MinElements     Minimum number of elements in nodes. Default: 0.3*Max.
0102 */
0103 template <size_t MaxElements,
0104           size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
0105 struct quadratic
0106 {
0107     BOOST_GEOMETRY_STATIC_ASSERT((0 < MinElements && 2*MinElements <= MaxElements+1),
0108         "Invalid MaxElements or MinElements.",
0109         std::integer_sequence<size_t, MaxElements, MinElements>);
0110
0111     static const size_t max_elements = MaxElements;
0112     static const size_t min_elements = MinElements;
0113
0114     static size_t get_max_elements() { return MaxElements; }
0115     static size_t get_min_elements() { return MinElements; }
0116 };
0117
0118 /*!
0119 \brief R*-tree creation algorithm parameters.
0120
0121 \tparam MaxElements             Maximum number of elements in nodes.
0122 \tparam MinElements             Minimum number of elements in nodes. Default: 0.3*Max.
0123 \tparam ReinsertedElements      The number of elements reinserted by forced reinsertions algorithm.
0124                                 If 0 forced reinsertions are disabled. Maximum value is Max+1-Min.
0125                                 Greater values are truncated. Default: 0.3*Max.
0126 \tparam OverlapCostThreshold    The number of most suitable leafs taken into account while choosing
0127                                 the leaf node to which currently inserted value will be added. If
0128                                 value is in range (0, MaxElements) - the algorithm calculates
0129                                 nearly minimum overlap cost, otherwise all leafs are analyzed
0130                                 and true minimum overlap cost is calculated. Default: 32.
0131 */
0132 template <size_t MaxElements,
0133           size_t MinElements = detail::default_min_elements_s<MaxElements>::value,
0134           size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value,
0135           size_t OverlapCostThreshold = 32>
0136 struct rstar
0137 {
0138     BOOST_GEOMETRY_STATIC_ASSERT((0 < MinElements && 2*MinElements <= MaxElements+1),
0139         "Invalid MaxElements or MinElements.",
0140         std::integer_sequence<size_t, MaxElements, MinElements>);
0141
0142     static const size_t max_elements = MaxElements;
0143     static const size_t min_elements = MinElements;
0144     static const size_t reinserted_elements = ReinsertedElements;
0145     static const size_t overlap_cost_threshold = OverlapCostThreshold;
0146
0147     static size_t get_max_elements() { return MaxElements; }
0148     static size_t get_min_elements() { return MinElements; }
0149     static size_t get_reinserted_elements() { return ReinsertedElements; }
0150     static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; }
0151 };
0152
0153 //template <size_t MaxElements, size_t MinElements>
0154 //struct kmeans
0155 //{
0156 //    static const size_t max_elements = MaxElements;
0157 //    static const size_t min_elements = MinElements;
0158 //};
0159
0160 /*!
0161 \brief Linear r-tree creation algorithm parameters - run-time version.
0162 */
0163 class dynamic_linear
0164 {
0165 public:
0166     /*!
0167     \brief The constructor.
0168
0169     \param max_elements     Maximum number of elements in nodes.
0170     \param min_elements     Minimum number of elements in nodes. Default: 0.3*Max.
0171     */
0172     explicit dynamic_linear(size_t max_elements,
0173                             size_t min_elements = detail::default_min_elements_d())
0174         : m_max_elements(max_elements)
0175         , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
0176     {
0177         if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
0178             detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_linear");
0179     }
0180
0181     size_t get_max_elements() const { return m_max_elements; }
0182     size_t get_min_elements() const { return m_min_elements; }
0183
0184 private:
0185     size_t m_max_elements;
0186     size_t m_min_elements;
0187 };
0188
0189 /*!
0190 \brief Quadratic r-tree creation algorithm parameters - run-time version.
0191 */
0192 class dynamic_quadratic
0193 {
0194 public:
0195     /*!
0196     \brief The constructor.
0197
0198     \param max_elements     Maximum number of elements in nodes.
0199     \param min_elements     Minimum number of elements in nodes. Default: 0.3*Max.
0200     */
0201     explicit dynamic_quadratic(size_t max_elements,
0202                                size_t min_elements = detail::default_min_elements_d())
0203         : m_max_elements(max_elements)
0204         , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
0205     {
0206         if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
0207             detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_quadratic");
0208     }
0209
0210     size_t get_max_elements() const { return m_max_elements; }
0211     size_t get_min_elements() const { return m_min_elements; }
0212
0213 private:
0214     size_t m_max_elements;
0215     size_t m_min_elements;
0216 };
0217
0218 /*!
0219 \brief R*-tree creation algorithm parameters - run-time version.
0220 */
0221 class dynamic_rstar
0222 {
0223 public:
0224     /*!
0225     \brief The constructor.
0226
0227     \param max_elements             Maximum number of elements in nodes.
0228     \param min_elements             Minimum number of elements in nodes. Default: 0.3*Max.
0229     \param reinserted_elements      The number of elements reinserted by forced reinsertions algorithm.
0230                                     If 0 forced reinsertions are disabled. Maximum value is Max-Min+1.
0231                                     Greater values are truncated. Default: 0.3*Max.
0232     \param overlap_cost_threshold   The number of most suitable leafs taken into account while choosing
0233                                     the leaf node to which currently inserted value will be added. If
0234                                     value is in range (0, MaxElements) - the algorithm calculates
0235                                     nearly minimum overlap cost, otherwise all leafs are analyzed
0236                                     and true minimum overlap cost is calculated. Default: 32.
0237     */
0238     explicit dynamic_rstar(size_t max_elements,
0239                            size_t min_elements = detail::default_min_elements_d(),
0240                            size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(),
0241                            size_t overlap_cost_threshold = 32)
0242         : m_max_elements(max_elements)
0243         , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
0244         , m_reinserted_elements(detail::default_rstar_reinserted_elements_d_calc(max_elements, reinserted_elements))
0245         , m_overlap_cost_threshold(overlap_cost_threshold)
0246     {
0247         if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
0248             detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_rstar");
0249     }
0250
0251     size_t get_max_elements() const { return m_max_elements; }
0252     size_t get_min_elements() const { return m_min_elements; }
0253     size_t get_reinserted_elements() const { return m_reinserted_elements; }
0254     size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; }
0255
0256 private:
0257     size_t m_max_elements;
0258     size_t m_min_elements;
0259     size_t m_reinserted_elements;
0260     size_t m_overlap_cost_threshold;
0261 };
0262
0263
0264 template <typename Parameters, typename Strategy>
0265 class parameters
0266     : public Parameters
0267     , private Strategy
0268 {
0269 public:
0270     parameters()
0271         : Parameters(), Strategy()
0272     {}
0273
0274     parameters(Parameters const& params)
0275         : Parameters(params), Strategy()
0276     {}
0277
0278     parameters(Parameters const& params, Strategy const& strategy)
0279         : Parameters(params), Strategy(strategy)
0280     {}
0281
0282     Strategy const& strategy() const
0283     {
0284         return static_cast<Strategy const&>(*this);
0285     }
0286 };
0287
0288
0289 namespace detail
0290 {
0291
0292 template <typename Parameters>
0293 struct strategy_type
0294 {
0295     typedef default_strategy type;
0296     typedef default_strategy result_type;
0297 };
0298
0299 template <typename Parameters, typename Strategy>
0300 struct strategy_type< parameters<Parameters, Strategy> >
0301 {
0302     typedef Strategy type;
0303     typedef Strategy const& result_type;
0304 };
0305
0306
0307 template <typename Parameters>
0308 struct get_strategy_impl
0309 {
0310     static inline default_strategy apply(Parameters const&)
0311     {
0312         return default_strategy();
0313     }
0314 };
0315
0316 template <typename Parameters, typename Strategy>
0317 struct get_strategy_impl<parameters<Parameters, Strategy> >
0318 {
0319     static inline Strategy const& apply(parameters<Parameters, Strategy> const& parameters)
0320     {
0321         return parameters.strategy();
0322     }
0323 };
0324
0325 template <typename Parameters>
0326 inline typename strategy_type<Parameters>::result_type
0327     get_strategy(Parameters const& parameters)
0328 {
0329     return get_strategy_impl<Parameters>::apply(parameters);
0330 }
0331
0332 } // namespace detail
0333
0334
0335 }}} // namespace boost::geometry::index
0336
0337 #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP