]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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: | |
28 | inline are_levels_ok() | |
29 | : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0) | |
30 | {} | |
31 | ||
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 | ||
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 | |
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 |