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 // 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_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP
  13
  14 #include <boost/geometry/index/detail/rtree/node/node.hpp>
  15
  16 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
  17
  18 namespace visitors {
  19
  20 template <typename Value, typename Options, typename Box, typename Allocators>
  21 class are_counts_ok
  22     : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
  23 {
  24     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
  25     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
  26     typedef typename Options::parameters_type parameters_type;
  27
  28 public:
  29     inline are_counts_ok(parameters_type const& parameters)
  30         : result(true), m_current_level(0), m_parameters(parameters)
  31     {}
  32
  33     inline void operator()(internal_node const& n)
  34     {
  35         typedef typename rtree::elements_type<internal_node>::type elements_type;
  36         elements_type const& elements = rtree::elements(n);
  37
  38         // root internal node shouldn't contain 0 elements
  39         if ( elements.empty()
  40           || !check_count(elements) )
  41         {
  42             result = false;
  43             return;
  44         }
  45
  46         size_t current_level_backup = m_current_level;
  47         ++m_current_level;
  48
  49         for ( typename elements_type::const_iterator it = elements.begin();
  50               it != elements.end() && result == true ;
  51               ++it)
  52         {
  53             rtree::apply_visitor(*this, *it->second);
  54         }
  55
  56         m_current_level = current_level_backup;
  57     }
  58
  59     inline void operator()(leaf const& n)
  60     {
  61         typedef typename rtree::elements_type<leaf>::type elements_type;
  62         elements_type const& elements = rtree::elements(n);
  63
  64         // empty leaf in non-root node
  65         if ( ( m_current_level > 0 && elements.empty() )
  66           || !check_count(elements) )
  67         {
  68             result = false;
  69         }
  70     }
  71
  72     bool result;
  73
  74 private:
  75     template <typename Elements>
  76     bool check_count(Elements const& elements)
  77     {
  78         // root may contain count < min but should never contain count > max
  79         return elements.size() <= m_parameters.get_max_elements()
  80             && ( elements.size() >= m_parameters.get_min_elements()
  81               || m_current_level == 0 );
  82     }
  83
  84     size_t m_current_level;
  85     parameters_type const& m_parameters;
  86 };
  87
  88 } // namespace visitors
  89
  90 template <typename Rtree> inline
  91 bool are_counts_ok(Rtree const& tree)
  92 {
  93     typedef utilities::view<Rtree> RTV;
  94     RTV rtv(tree);
  95
  96     visitors::are_counts_ok<
  97         typename RTV::value_type,
  98         typename RTV::options_type,
  99         typename RTV::box_type,
 100         typename RTV::allocators_type
 101     > v(tree.parameters());
 102
 103     rtv.apply_visitor(v);
 104
 105     return v.result;
 106 }
 107
 108 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
 109
 110 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_COUNTS_OK_HPP