ceph/src/boost/libs/geometry/include/boost/geometry/index/parameters.hpp

   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