Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // R-tree visitor collecting basic statistics
Chris@16: //
Chris@16: // Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
Chris@16: // Copyright (c) 2013 Mateusz Loskot, London, UK.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace utilities {
Chris@16: 
Chris@16: namespace visitors {
Chris@16: 
Chris@16: template <typename Value, typename Options, typename Box, typename Allocators>
Chris@16: struct statistics : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
Chris@16: {
Chris@16:     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
Chris@16:     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
Chris@16: 
Chris@16:     inline statistics()
Chris@16:         : level(0)
Chris@16:         , levels(1) // count root
Chris@16:         , nodes(0)
Chris@16:         , leaves(0)
Chris@16:         , values(0)
Chris@16:         , values_min(0)
Chris@16:         , values_max(0)
Chris@16:     {}
Chris@16: 
Chris@16:     inline void operator()(internal_node const& n)
Chris@16:     {
Chris@16:         typedef typename rtree::elements_type<internal_node>::type elements_type;
Chris@16:         elements_type const& elements = rtree::elements(n);
Chris@16:         
Chris@16:         ++nodes; // count node
Chris@16: 
Chris@16:         size_t const level_backup = level;
Chris@16:         ++level;
Chris@16: 
Chris@16:         levels += level++ > levels ? 1 : 0; // count level (root already counted)
Chris@16:                 
Chris@16:         for (typename elements_type::const_iterator it = elements.begin();
Chris@16:             it != elements.end(); ++it)
Chris@16:         {
Chris@16:             rtree::apply_visitor(*this, *it->second);
Chris@16:         }
Chris@16:         
Chris@16:         level = level_backup;
Chris@16:     }
Chris@16: 
Chris@16:     inline void operator()(leaf const& n)
Chris@16:     {   
Chris@16:         typedef typename rtree::elements_type<leaf>::type elements_type;
Chris@16:         elements_type const& elements = rtree::elements(n);
Chris@16: 
Chris@16:         ++leaves; // count leaves
Chris@16:         
Chris@16:         std::size_t const v = elements.size();
Chris@16:         // count values spread per node and total
Chris@16:         values_min = (std::min)(values_min == 0 ? v : values_min, v);
Chris@16:         values_max = (std::max)(values_max, v);
Chris@16:         values += v;
Chris@16:     }
Chris@16:     
Chris@16:     std::size_t level;
Chris@16:     std::size_t levels;
Chris@16:     std::size_t nodes;
Chris@16:     std::size_t leaves;
Chris@16:     std::size_t values;
Chris@16:     std::size_t values_min;
Chris@16:     std::size_t values_max;
Chris@16: };
Chris@16: 
Chris@16: } // namespace visitors
Chris@16: 
Chris@16: template <typename Rtree> inline
Chris@16: boost::tuple<std::size_t, std::size_t, std::size_t, std::size_t, std::size_t, std::size_t>
Chris@16: statistics(Rtree const& tree)
Chris@16: {
Chris@16:     typedef utilities::view<Rtree> RTV;
Chris@16:     RTV rtv(tree);
Chris@16: 
Chris@16:     visitors::statistics<
Chris@16:         typename RTV::value_type,
Chris@16:         typename RTV::options_type,
Chris@16:         typename RTV::box_type,
Chris@16:         typename RTV::allocators_type
Chris@16:     > stats_v;
Chris@16: 
Chris@16:     rtv.apply_visitor(stats_v);
Chris@16:     
Chris@16:     return boost::make_tuple(stats_v.levels, stats_v.nodes, stats_v.leaves, stats_v.values, stats_v.values_min, stats_v.values_max);
Chris@16: }
Chris@16: 
Chris@16: }}}}}} // namespace boost::geometry::index::detail::rtree::utilities
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_UTILITIES_STATISTICS_HPP