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