]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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: | |
29 | inline are_counts_ok(parameters_type const& parameters) | |
30 | : result(true), m_current_level(0), m_parameters(parameters) | |
31 | {} | |
32 | ||
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 | ||
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> | |
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 | |
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 |