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

   1 // Boost.Geometry Index
   2 //
   3 // R-tree levels validating visitor implementation
   4 //
   5 // Copyright (c) 2011-2013 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_LEVELS_OK_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_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_levels_ok
  26     : public MembersHolder::visitor_const
  27 {
  28     typedef typename MembersHolder::internal_node internal_node;
  29     typedef typename MembersHolder::leaf leaf;
  30
  31 public:
  32     inline are_levels_ok()
  33         : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
  34     {}
  35
  36     inline void operator()(internal_node const& n)
  37     {
  38         typedef typename rtree::elements_type<internal_node>::type elements_type;
  39         elements_type const& elements = rtree::elements(n);
  40
  41         if (elements.empty())
  42         {
  43             result = false;
  44             return;
  45         }
  46
  47         size_t current_level_backup = m_current_level;
  48         ++m_current_level;
  49
  50         for ( typename elements_type::const_iterator it = elements.begin();
  51               it != elements.end() ; ++it)
  52         {
  53             rtree::apply_visitor(*this, *it->second);
  54
  55             if ( result == false )
  56                 return;
  57         }
  58
  59         m_current_level = current_level_backup;
  60     }
  61
  62     inline void operator()(leaf const& n)
  63     {
  64         typedef typename rtree::elements_type<leaf>::type elements_type;
  65         elements_type const& elements = rtree::elements(n);
  66
  67         // empty leaf in non-root node
  68         if (0 < m_current_level && elements.empty())
  69         {
  70             result = false;
  71             return;
  72         }
  73
  74         if ( m_leafs_level == (std::numeric_limits<size_t>::max)() )
  75         {
  76             m_leafs_level = m_current_level;
  77         }
  78         else if ( m_leafs_level != m_current_level )
  79         {
  80             result = false;
  81         }
  82     }
  83
  84     bool result;
  85
  86 private:
  87     size_t m_leafs_level;
  88     size_t m_current_level;
  89 };
  90
  91 } // namespace visitors
  92
  93 template <typename Rtree> inline
  94 bool are_levels_ok(Rtree const& tree)
  95 {
  96     typedef utilities::view<Rtree> RTV;
  97     RTV rtv(tree);
  98
  99     visitors::are_levels_ok<
 100         typename RTV::members_holder
 101     > v;
 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_LEVELS_OK_HPP