Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // R-tree algorithms parameters
Chris@16: //
Chris@16: // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_PARAMETERS_HPP
Chris@16: 
Chris@16: #include <limits>
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index {
Chris@16: 
Chris@16: namespace detail { 
Chris@16: 
Chris@16: template <size_t MaxElements>
Chris@16: struct default_min_elements_s
Chris@16: {
Chris@16:     static const size_t raw_value = (MaxElements * 3) / 10;
Chris@16:     static const size_t value = 1 <= raw_value ? raw_value : 1;
Chris@16: };
Chris@16: 
Chris@16: inline size_t default_min_elements_d()
Chris@16: {
Chris@16:     return (std::numeric_limits<size_t>::max)();
Chris@16: }
Chris@16: 
Chris@16: inline size_t default_min_elements_d_calc(size_t max_elements, size_t min_elements)
Chris@16: {
Chris@16:     if ( default_min_elements_d() == min_elements )
Chris@16:     {
Chris@16:         size_t raw_value = (max_elements * 3) / 10;
Chris@16:         return 1 <= raw_value ? raw_value : 1;
Chris@16:     }
Chris@16:     
Chris@16:     return min_elements;
Chris@16: }
Chris@16: 
Chris@16: template <size_t MaxElements>
Chris@16: struct default_rstar_reinserted_elements_s
Chris@16: {
Chris@16:     static const size_t value = (MaxElements * 3) / 10;
Chris@16: };
Chris@16: 
Chris@16: inline size_t default_rstar_reinserted_elements_d()
Chris@16: {
Chris@16:     return (std::numeric_limits<size_t>::max)();
Chris@16: }
Chris@16: 
Chris@16: inline size_t default_rstar_reinserted_elements_d_calc(size_t max_elements, size_t reinserted_elements)
Chris@16: {
Chris@16:     if ( default_rstar_reinserted_elements_d() == reinserted_elements )
Chris@16:     {
Chris@16:         return (max_elements * 3) / 10;
Chris@16:     }
Chris@16:     
Chris@16:     return reinserted_elements;
Chris@16: }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: /*!
Chris@16: \brief Linear r-tree creation algorithm parameters.
Chris@16: 
Chris@16: \tparam MaxElements     Maximum number of elements in nodes.
Chris@16: \tparam MinElements     Minimum number of elements in nodes. Default: 0.3*Max.
Chris@16: */
Chris@16: template <size_t MaxElements,
Chris@101:           size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
Chris@16: struct linear
Chris@16: {
Chris@16:     BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
Chris@16:                          INVALID_STATIC_MIN_MAX_PARAMETERS, (linear));
Chris@16: 
Chris@16:     static const size_t max_elements = MaxElements;
Chris@16:     static const size_t min_elements = MinElements;
Chris@16: 
Chris@16:     static size_t get_max_elements() { return MaxElements; }
Chris@16:     static size_t get_min_elements() { return MinElements; }
Chris@16: };
Chris@16: 
Chris@16: /*!
Chris@16: \brief Quadratic r-tree creation algorithm parameters.
Chris@16: 
Chris@16: \tparam MaxElements     Maximum number of elements in nodes.
Chris@16: \tparam MinElements     Minimum number of elements in nodes. Default: 0.3*Max.
Chris@16: */
Chris@16: template <size_t MaxElements,
Chris@16:           size_t MinElements = detail::default_min_elements_s<MaxElements>::value>
Chris@16: struct quadratic
Chris@16: {
Chris@16:     BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
Chris@16:                          INVALID_STATIC_MIN_MAX_PARAMETERS, (quadratic));
Chris@16: 
Chris@16:     static const size_t max_elements = MaxElements;
Chris@16:     static const size_t min_elements = MinElements;
Chris@16: 
Chris@16:     static size_t get_max_elements() { return MaxElements; }
Chris@16:     static size_t get_min_elements() { return MinElements; }
Chris@16: };
Chris@16: 
Chris@16: /*!
Chris@16: \brief R*-tree creation algorithm parameters.
Chris@16: 
Chris@16: \tparam MaxElements             Maximum number of elements in nodes.
Chris@16: \tparam MinElements             Minimum number of elements in nodes. Default: 0.3*Max.
Chris@16: \tparam ReinsertedElements      The number of elements reinserted by forced reinsertions algorithm.
Chris@16:                                 If 0 forced reinsertions are disabled. Maximum value is Max+1-Min.
Chris@16:                                 Greater values are truncated. Default: 0.3*Max.
Chris@16: \tparam OverlapCostThreshold    The number of most suitable leafs taken into account while choosing
Chris@16:                                 the leaf node to which currently inserted value will be added. If
Chris@16:                                 value is in range (0, MaxElements) - the algorithm calculates
Chris@16:                                 nearly minimum overlap cost, otherwise all leafs are analyzed
Chris@16:                                 and true minimum overlap cost is calculated. Default: 32.
Chris@16: */
Chris@16: template <size_t MaxElements,
Chris@16:           size_t MinElements = detail::default_min_elements_s<MaxElements>::value,
Chris@16:           size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value,
Chris@16:           size_t OverlapCostThreshold = 32>
Chris@16: struct rstar
Chris@16: {
Chris@16:     BOOST_MPL_ASSERT_MSG((0 < MinElements && 2*MinElements <= MaxElements+1),
Chris@16:                          INVALID_STATIC_MIN_MAX_PARAMETERS, (rstar));
Chris@16: 
Chris@16:     static const size_t max_elements = MaxElements;
Chris@16:     static const size_t min_elements = MinElements;
Chris@16:     static const size_t reinserted_elements = ReinsertedElements;
Chris@16:     static const size_t overlap_cost_threshold = OverlapCostThreshold;
Chris@16: 
Chris@16:     static size_t get_max_elements() { return MaxElements; }
Chris@16:     static size_t get_min_elements() { return MinElements; }
Chris@16:     static size_t get_reinserted_elements() { return ReinsertedElements; }
Chris@16:     static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; }
Chris@16: };
Chris@16: 
Chris@16: //template <size_t MaxElements, size_t MinElements>
Chris@16: //struct kmeans
Chris@16: //{
Chris@16: //    static const size_t max_elements = MaxElements;
Chris@16: //    static const size_t min_elements = MinElements;
Chris@16: //};
Chris@16: 
Chris@16: /*!
Chris@16: \brief Linear r-tree creation algorithm parameters - run-time version.
Chris@16: */
Chris@16: class dynamic_linear
Chris@16: {
Chris@16: public:
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     \param max_elements     Maximum number of elements in nodes.
Chris@16:     \param min_elements     Minimum number of elements in nodes. Default: 0.3*Max.
Chris@16:     */
Chris@16:     dynamic_linear(size_t max_elements,
Chris@16:                    size_t min_elements = detail::default_min_elements_d())
Chris@16:         : m_max_elements(max_elements)
Chris@16:         , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
Chris@16:     {
Chris@16:         if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
Chris@16:             detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_linear");
Chris@16:     }
Chris@16: 
Chris@16:     size_t get_max_elements() const { return m_max_elements; }
Chris@16:     size_t get_min_elements() const { return m_min_elements; }
Chris@16: 
Chris@16: private:
Chris@16:     size_t m_max_elements;
Chris@16:     size_t m_min_elements;
Chris@16: };
Chris@16: 
Chris@16: /*!
Chris@16: \brief Quadratic r-tree creation algorithm parameters - run-time version.
Chris@16: */
Chris@16: class dynamic_quadratic
Chris@16: {
Chris@16: public:
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     \param max_elements     Maximum number of elements in nodes.
Chris@16:     \param min_elements     Minimum number of elements in nodes. Default: 0.3*Max.
Chris@16:     */
Chris@16:     dynamic_quadratic(size_t max_elements,
Chris@16:                       size_t min_elements = detail::default_min_elements_d())
Chris@16:         : m_max_elements(max_elements)
Chris@16:         , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
Chris@16:     {
Chris@16:         if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
Chris@16:             detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_quadratic");
Chris@16:     }
Chris@16: 
Chris@16:     size_t get_max_elements() const { return m_max_elements; }
Chris@16:     size_t get_min_elements() const { return m_min_elements; }
Chris@16: 
Chris@16: private:
Chris@16:     size_t m_max_elements;
Chris@16:     size_t m_min_elements;
Chris@16: };
Chris@16: 
Chris@16: /*!
Chris@16: \brief R*-tree creation algorithm parameters - run-time version.
Chris@16: */
Chris@16: class dynamic_rstar
Chris@16: {
Chris@16: public:
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     \param max_elements             Maximum number of elements in nodes.
Chris@16:     \param min_elements             Minimum number of elements in nodes. Default: 0.3*Max.
Chris@16:     \param reinserted_elements      The number of elements reinserted by forced reinsertions algorithm.
Chris@16:                                     If 0 forced reinsertions are disabled. Maximum value is Max-Min+1.
Chris@16:                                     Greater values are truncated. Default: 0.3*Max.
Chris@16:     \param overlap_cost_threshold   The number of most suitable leafs taken into account while choosing
Chris@16:                                     the leaf node to which currently inserted value will be added. If
Chris@16:                                     value is in range (0, MaxElements) - the algorithm calculates
Chris@16:                                     nearly minimum overlap cost, otherwise all leafs are analyzed
Chris@16:                                     and true minimum overlap cost is calculated. Default: 32.
Chris@16:     */
Chris@16:     dynamic_rstar(size_t max_elements,
Chris@16:                   size_t min_elements = detail::default_min_elements_d(),
Chris@16:                   size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(),
Chris@16:                   size_t overlap_cost_threshold = 32)
Chris@16:         : m_max_elements(max_elements)
Chris@16:         , m_min_elements(detail::default_min_elements_d_calc(max_elements, min_elements))
Chris@16:         , m_reinserted_elements(detail::default_rstar_reinserted_elements_d_calc(max_elements, reinserted_elements))
Chris@16:         , m_overlap_cost_threshold(overlap_cost_threshold)
Chris@16:     {
Chris@16:         if (!(0 < m_min_elements && 2*m_min_elements <= m_max_elements+1))
Chris@16:             detail::throw_invalid_argument("invalid min or/and max parameters of dynamic_rstar");
Chris@16:     }
Chris@16: 
Chris@16:     size_t get_max_elements() const { return m_max_elements; }
Chris@16:     size_t get_min_elements() const { return m_min_elements; }
Chris@16:     size_t get_reinserted_elements() const { return m_reinserted_elements; }
Chris@16:     size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; }
Chris@16: 
Chris@16: private:
Chris@16:     size_t m_max_elements;
Chris@16:     size_t m_min_elements;
Chris@16:     size_t m_reinserted_elements;
Chris@16:     size_t m_overlap_cost_threshold;
Chris@16: };
Chris@16: 
Chris@16: }}} // namespace boost::geometry::index
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_PARAMETERS_HPP