]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | // Use, modification and distribution is subject to the Boost Software License, | |
9 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
10 | // http://www.boost.org/LICENSE_1_0.txt) | |
11 | ||
12 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP | |
13 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP | |
14 | ||
15 | #include <algorithm> | |
16 | #include <boost/tuple/tuple.hpp> | |
17 | ||
18 | namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities { | |
19 | ||
20 | namespace visitors { | |
21 | ||
22 | template <typename Value, typename Options, typename Box, typename Allocators> | |
23 | struct statistics : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
24 | { | |
25 | typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
26 | typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
27 | ||
28 | inline statistics() | |
29 | : level(0) | |
30 | , levels(1) // count root | |
31 | , nodes(0) | |
32 | , leaves(0) | |
33 | , values(0) | |
34 | , values_min(0) | |
35 | , values_max(0) | |
36 | {} | |
37 | ||
38 | inline void operator()(internal_node const& n) | |
39 | { | |
40 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
41 | elements_type const& elements = rtree::elements(n); | |
42 | ||
43 | ++nodes; // count node | |
44 | ||
45 | size_t const level_backup = level; | |
46 | ++level; | |
47 | ||
48 | levels += level++ > levels ? 1 : 0; // count level (root already counted) | |
49 | ||
50 | for (typename elements_type::const_iterator it = elements.begin(); | |
51 | it != elements.end(); ++it) | |
52 | { | |
53 | rtree::apply_visitor(*this, *it->second); | |
54 | } | |
55 | ||
56 | level = 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 | ++leaves; // count leaves | |
65 | ||
66 | std::size_t const v = elements.size(); | |
67 | // count values spread per node and total | |
68 | values_min = (std::min)(values_min == 0 ? v : values_min, v); | |
69 | values_max = (std::max)(values_max, v); | |
70 | values += v; | |
71 | } | |
72 | ||
73 | std::size_t level; | |
74 | std::size_t levels; | |
75 | std::size_t nodes; | |
76 | std::size_t leaves; | |
77 | std::size_t values; | |
78 | std::size_t values_min; | |
79 | std::size_t values_max; | |
80 | }; | |
81 | ||
82 | } // namespace visitors | |
83 | ||
84 | template <typename Rtree> inline | |
85 | boost::tuple<std::size_t, std::size_t, std::size_t, std::size_t, std::size_t, std::size_t> | |
86 | statistics(Rtree const& tree) | |
87 | { | |
88 | typedef utilities::view<Rtree> RTV; | |
89 | RTV rtv(tree); | |
90 | ||
91 | visitors::statistics< | |
92 | typename RTV::value_type, | |
93 | typename RTV::options_type, | |
94 | typename RTV::box_type, | |
95 | typename RTV::allocators_type | |
96 | > stats_v; | |
97 | ||
98 | rtv.apply_visitor(stats_v); | |
99 | ||
100 | return boost::make_tuple(stats_v.levels, stats_v.nodes, stats_v.leaves, stats_v.values, stats_v.values_min, stats_v.values_max); | |
101 | } | |
102 | ||
103 | }}}}}} // namespace boost::geometry::index::detail::rtree::utilities | |
104 | ||
105 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP |