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:
are_levels_ok()32     inline are_levels_ok()
33         : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
34     {}
35 
operator ()(internal_node const & n)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 
operator ()(leaf const & n)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
are_levels_ok(Rtree const & tree)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
111