ceph/src/boost/boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp

   1 // Boost.Geometry Index
   2 //
   3 // R-tree nodes elements numbers validating visitor implementation
   4 //
   5 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
   6 //
   7 // This file was modified by Oracle on 2019.
   8 // Modifications copyright (c) 2019 Oracle and/or its affiliates.
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10 //
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP
  17
  18 #include <boost/geometry/index/detail/rtree/node/node.hpp>
  19
  20 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
  21
  22 namespace visitors {
  23
  24 template <typename MembersHolder>
  25 class are_counts_ok
  26     : public MembersHolder::visitor_const
  27 {
  28     typedef typename MembersHolder::parameters_type parameters_type;
  29
  30     typedef typename MembersHolder::internal_node internal_node;
  31     typedef typename MembersHolder::leaf leaf;
  32
  33 public:
  34     inline are_counts_ok(parameters_type const& parameters, bool check_min = true)
  35         : result(true)
  36         , m_current_level(0)
  37         , m_parameters(parameters)
  38         , m_check_min(check_min)
  39     {}
  40
  41     inline void operator()(internal_node const& n)
  42     {
  43         typedef typename rtree::elements_type<internal_node>::type elements_type;
  44         elements_type const& elements = rtree::elements(n);
  45
  46         // root internal node shouldn't contain 0 elements
  47         if ( (elements.empty() && m_check_min)
  48           || !check_count(elements) )
  49         {
  50             result = false;
  51             return;
  52         }
  53
  54         size_t current_level_backup = m_current_level;
  55         ++m_current_level;
  56
  57         for ( typename elements_type::const_iterator it = elements.begin();
  58               it != elements.end() && result == true ;
  59               ++it)
  60         {
  61             rtree::apply_visitor(*this, *it->second);
  62         }
  63
  64         m_current_level = current_level_backup;
  65     }
  66
  67     inline void operator()(leaf const& n)
  68     {
  69         typedef typename rtree::elements_type<leaf>::type elements_type;
  70         elements_type const& elements = rtree::elements(n);
  71
  72         // empty leaf in non-root node
  73         if ( (m_current_level > 0 && elements.empty() && m_check_min)
  74           || !check_count(elements) )
  75         {
  76             result = false;
  77         }
  78     }
  79
  80     bool result;
  81
  82 private:
  83     template <typename Elements>
  84     bool check_count(Elements const& elements)
  85     {
  86         // root may contain count < min but should never contain count > max
  87         return elements.size() <= m_parameters.get_max_elements()
  88             && ( elements.size() >= m_parameters.get_min_elements()
  89               || m_current_level == 0 || !m_check_min );
  90     }
  91
  92     size_t m_current_level;
  93     parameters_type const& m_parameters;
  94     bool m_check_min;
  95 };
  96
  97 } // namespace visitors
  98
  99 template <typename Rtree> inline
 100 bool are_counts_ok(Rtree const& tree, bool check_min = true)
 101 {
 102     typedef utilities::view<Rtree> RTV;
 103     RTV rtv(tree);
 104
 105     visitors::are_counts_ok<
 106         typename RTV::members_holder
 107     > v(tree.parameters(), check_min);
 108
 109     rtv.apply_visitor(v);
 110
 111     return v.result;
 112 }
 113
 114 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
 115
 116 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP