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