blob: a76cf38bf661c465725aac8aa55cbd45bd9e3e6b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
// Boost.Geometry Index
//
// R-tree levels validating visitor implementation
//
// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
//
// This file was modified by Oracle on 2019.
// Modifications copyright (c) 2019 Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
//
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP
#include <boost/geometry/index/detail/rtree/node/node.hpp>
namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
namespace visitors {
template <typename MembersHolder>
class are_levels_ok
: public MembersHolder::visitor_const
{
typedef typename MembersHolder::internal_node internal_node;
typedef typename MembersHolder::leaf leaf;
public:
inline are_levels_ok()
: result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
{}
inline void operator()(internal_node const& n)
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
if (elements.empty())
{
result = false;
return;
}
size_t current_level_backup = m_current_level;
++m_current_level;
for ( typename elements_type::const_iterator it = elements.begin();
it != elements.end() ; ++it)
{
rtree::apply_visitor(*this, *it->second);
if ( result == false )
return;
}
m_current_level = current_level_backup;
}
inline void operator()(leaf const& n)
{
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
// empty leaf in non-root node
if (0 < m_current_level && elements.empty())
{
result = false;
return;
}
if ( m_leafs_level == (std::numeric_limits<size_t>::max)() )
{
m_leafs_level = m_current_level;
}
else if ( m_leafs_level != m_current_level )
{
result = false;
}
}
bool result;
private:
size_t m_leafs_level;
size_t m_current_level;
};
} // namespace visitors
template <typename Rtree> inline
bool are_levels_ok(Rtree const& tree)
{
typedef utilities::view<Rtree> RTV;
RTV rtv(tree);
visitors::are_levels_ok<
typename RTV::members_holder
> v;
rtv.apply_visitor(v);
return v.result;
}
}}}}}} // namespace boost::geometry::index::detail::rtree::utilities
#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_ARE_LEVELS_OK_HPP
|