ceph/src/boost/libs/geometry/include/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 // 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_LEVELS_OK_HPP
  12 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_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_levels_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
  27 public:
  28     inline are_levels_ok()
  29         : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
  30     {}
  31
  32     inline void operator()(internal_node const& n)
  33     {
  34         typedef typename rtree::elements_type<internal_node>::type elements_type;
  35         elements_type const& elements = rtree::elements(n);
  36
  37         if (elements.empty())
  38         {
  39             result = false;
  40             return;
  41         }
  42
  43         size_t current_level_backup = m_current_level;
  44         ++m_current_level;
  45
  46         for ( typename elements_type::const_iterator it = elements.begin();
  47               it != elements.end() ; ++it)
  48         {
  49             rtree::apply_visitor(*this, *it->second);
  50
  51             if ( result == false )
  52                 return;
  53         }
  54
  55         m_current_level = current_level_backup;
  56     }
  57
  58     inline void operator()(leaf const& n)
  59     {
  60         typedef typename rtree::elements_type<leaf>::type elements_type;
  61         elements_type const& elements = rtree::elements(n);
  62
  63         // empty leaf in non-root node
  64         if (0 < m_current_level && elements.empty())
  65         {
  66             result = false;
  67             return;
  68         }
  69
  70         if ( m_leafs_level == (std::numeric_limits<size_t>::max)() )
  71         {
  72             m_leafs_level = m_current_level;
  73         }
  74         else if ( m_leafs_level != m_current_level )
  75         {
  76             result = false;
  77         }
  78     }
  79
  80     bool result;
  81
  82 private:
  83     size_t m_leafs_level;
  84     size_t m_current_level;
  85 };
  86
  87 } // namespace visitors
  88
  89 template <typename Rtree> inline
  90 bool are_levels_ok(Rtree const& tree)
  91 {
  92     typedef utilities::view<Rtree> RTV;
  93     RTV rtv(tree);
  94
  95     visitors::are_levels_ok<
  96         typename RTV::value_type,
  97         typename RTV::options_type,
  98         typename RTV::box_type,
  99         typename RTV::allocators_type
 100     > v;
 101
 102     rtv.apply_visitor(v);
 103
 104     return v.result;
 105 }
 106
 107 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
 108
 109 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP