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:
are_levels_ok()28     inline are_levels_ok()
29         : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
30     {}
31 
operator ()(internal_node const & n)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 
operator ()(leaf const & n)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
are_levels_ok(Rtree const & tree)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
110