1 // Boost.Geometry Index
2 //
3 // R-tree visitor collecting basic statistics
4 //
5 // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
6 // Copyright (c) 2013 Mateusz Loskot, London, UK.
7 //
8 // This file was modified by Oracle on 2019.
9 // Modifications copyright (c) 2019 Oracle and/or its affiliates.
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 //
12 // Use, modification and distribution is subject to the Boost Software License,
13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
14 // http://www.boost.org/LICENSE_1_0.txt)
15
16 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP
17 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP
18
19 #include <algorithm>
20 #include <boost/tuple/tuple.hpp>
21
22 namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
23
24 namespace visitors {
25
26 template <typename MembersHolder>
27 struct statistics
28 : public MembersHolder::visitor_const
29 {
30 typedef typename MembersHolder::internal_node internal_node;
31 typedef typename MembersHolder::leaf leaf;
32
statisticsboost::geometry::index::detail::rtree::utilities::visitors::statistics33 inline statistics()
34 : level(0)
35 , levels(1) // count root
36 , nodes(0)
37 , leaves(0)
38 , values(0)
39 , values_min(0)
40 , values_max(0)
41 {}
42
operator ()boost::geometry::index::detail::rtree::utilities::visitors::statistics43 inline void operator()(internal_node const& n)
44 {
45 typedef typename rtree::elements_type<internal_node>::type elements_type;
46 elements_type const& elements = rtree::elements(n);
47
48 ++nodes; // count node
49
50 size_t const level_backup = level;
51 ++level;
52
53 levels += level++ > levels ? 1 : 0; // count level (root already counted)
54
55 for (typename elements_type::const_iterator it = elements.begin();
56 it != elements.end(); ++it)
57 {
58 rtree::apply_visitor(*this, *it->second);
59 }
60
61 level = level_backup;
62 }
63
operator ()boost::geometry::index::detail::rtree::utilities::visitors::statistics64 inline void operator()(leaf const& n)
65 {
66 typedef typename rtree::elements_type<leaf>::type elements_type;
67 elements_type const& elements = rtree::elements(n);
68
69 ++leaves; // count leaves
70
71 std::size_t const v = elements.size();
72 // count values spread per node and total
73 values_min = (std::min)(values_min == 0 ? v : values_min, v);
74 values_max = (std::max)(values_max, v);
75 values += v;
76 }
77
78 std::size_t level;
79 std::size_t levels;
80 std::size_t nodes;
81 std::size_t leaves;
82 std::size_t values;
83 std::size_t values_min;
84 std::size_t values_max;
85 };
86
87 } // namespace visitors
88
89 template <typename Rtree> inline
90 boost::tuple<std::size_t, std::size_t, std::size_t, std::size_t, std::size_t, std::size_t>
statistics(Rtree const & tree)91 statistics(Rtree const& tree)
92 {
93 typedef utilities::view<Rtree> RTV;
94 RTV rtv(tree);
95
96 visitors::statistics<
97 typename RTV::members_holder
98 > stats_v;
99
100 rtv.apply_visitor(stats_v);
101
102 return boost::make_tuple(stats_v.levels, stats_v.nodes, stats_v.leaves, stats_v.values, stats_v.values_min, stats_v.values_max);
103 }
104
105 }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
106
107 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP
108