ceph/src/boost/boost/geometry/index/detail/rtree/utilities/statistics.hpp

   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