rtree/utilities/are_counts_ok.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree nodes elements numbers validating visitor implementation
0004 //
0005 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2023.
0008 // Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP
0018
0019 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0020 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
0021
0022 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
0023
0024 namespace visitors {
0025
0026 template <typename MembersHolder>
0027 class are_counts_ok
0028     : public MembersHolder::visitor_const
0029 {
0030     typedef typename MembersHolder::parameters_type parameters_type;
0031
0032     typedef typename MembersHolder::internal_node internal_node;
0033     typedef typename MembersHolder::leaf leaf;
0034
0035 public:
0036     inline are_counts_ok(parameters_type const& parameters, bool check_min = true)
0037         : result(true)
0038         , m_current_level(0)
0039         , m_parameters(parameters)
0040         , m_check_min(check_min)
0041     {}
0042
0043     inline void operator()(internal_node const& n)
0044     {
0045         typedef typename rtree::elements_type<internal_node>::type elements_type;
0046         elements_type const& elements = rtree::elements(n);
0047
0048         // root internal node shouldn't contain 0 elements
0049         if ( (elements.empty() && m_check_min)
0050           || !check_count(elements) )
0051         {
0052             result = false;
0053             return;
0054         }
0055
0056         size_t current_level_backup = m_current_level;
0057         ++m_current_level;
0058
0059         for ( typename elements_type::const_iterator it = elements.begin();
0060               it != elements.end() && result == true ;
0061               ++it)
0062         {
0063             rtree::apply_visitor(*this, *it->second);
0064         }
0065
0066         m_current_level = current_level_backup;
0067     }
0068
0069     inline void operator()(leaf const& n)
0070     {
0071         typedef typename rtree::elements_type<leaf>::type elements_type;
0072         elements_type const& elements = rtree::elements(n);
0073
0074         // empty leaf in non-root node
0075         if ( (m_current_level > 0 && elements.empty() && m_check_min)
0076           || !check_count(elements) )
0077         {
0078             result = false;
0079         }
0080     }
0081
0082     bool result;
0083
0084 private:
0085     template <typename Elements>
0086     bool check_count(Elements const& elements)
0087     {
0088         // root may contain count < min but should never contain count > max
0089         return elements.size() <= m_parameters.get_max_elements()
0090             && ( elements.size() >= m_parameters.get_min_elements()
0091               || m_current_level == 0 || !m_check_min );
0092     }
0093
0094     size_t m_current_level;
0095     parameters_type const& m_parameters;
0096     bool m_check_min;
0097 };
0098
0099 } // namespace visitors
0100
0101 template <typename Rtree> inline
0102 bool are_counts_ok(Rtree const& tree, bool check_min = true)
0103 {
0104     typedef utilities::view<Rtree> RTV;
0105     RTV rtv(tree);
0106
0107     visitors::are_counts_ok<
0108         typename RTV::members_holder
0109     > v(tree.parameters(), check_min);
0110
0111     rtv.apply_visitor(v);
0112
0113     return v.result;
0114 }
0115
0116 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
0117
0118 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP