diff options
Diffstat (limited to 'boost/geometry/index/detail/rtree/utilities/statistics.hpp')
-rw-r--r-- | boost/geometry/index/detail/rtree/utilities/statistics.hpp | 105 |
1 files changed, 105 insertions, 0 deletions
diff --git a/boost/geometry/index/detail/rtree/utilities/statistics.hpp b/boost/geometry/index/detail/rtree/utilities/statistics.hpp new file mode 100644 index 0000000000..bbaed8100e --- /dev/null +++ b/boost/geometry/index/detail/rtree/utilities/statistics.hpp @@ -0,0 +1,105 @@ +// Boost.Geometry Index +// +// R-tree visitor collecting basic statistics +// +// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland. +// Copyright (c) 2013 Mateusz Loskot, London, UK. +// +// 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_STATISTICS_HPP +#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP + +#include <algorithm> +#include <boost/tuple/tuple.hpp> + +namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities { + +namespace visitors { + +template <typename Value, typename Options, typename Box, typename Allocators> +struct statistics : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type +{ + typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; + typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; + + inline statistics() + : level(0) + , levels(1) // count root + , nodes(0) + , leaves(0) + , values(0) + , values_min(0) + , values_max(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); + + ++nodes; // count node + + size_t const level_backup = level; + ++level; + + levels += level++ > levels ? 1 : 0; // count level (root already counted) + + for (typename elements_type::const_iterator it = elements.begin(); + it != elements.end(); ++it) + { + rtree::apply_visitor(*this, *it->second); + } + + level = level_backup; + } + + inline void operator()(leaf const& n) + { + typedef typename rtree::elements_type<leaf>::type elements_type; + elements_type const& elements = rtree::elements(n); + + ++leaves; // count leaves + + std::size_t const v = elements.size(); + // count values spread per node and total + values_min = (std::min)(values_min == 0 ? v : values_min, v); + values_max = (std::max)(values_max, v); + values += v; + } + + std::size_t level; + std::size_t levels; + std::size_t nodes; + std::size_t leaves; + std::size_t values; + std::size_t values_min; + std::size_t values_max; +}; + +} // namespace visitors + +template <typename Rtree> inline +boost::tuple<std::size_t, std::size_t, std::size_t, std::size_t, std::size_t, std::size_t> +statistics(Rtree const& tree) +{ + typedef utilities::view<Rtree> RTV; + RTV rtv(tree); + + visitors::statistics< + typename RTV::value_type, + typename RTV::options_type, + typename RTV::box_type, + typename RTV::allocators_type + > stats_v; + + rtv.apply_visitor(stats_v); + + return boost::make_tuple(stats_v.levels, stats_v.nodes, stats_v.leaves, stats_v.values, stats_v.values_min, stats_v.values_max); +} + +}}}}}} // namespace boost::geometry::index::detail::rtree::utilities + +#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP |