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 // This file was modified by Oracle on 2019-2020.
   9 // Modifications copyright (c) 2019-2020 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 <tuple>
  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
  33     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
  43     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
  64     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 std::tuple<std::size_t, std::size_t, std::size_t, std::size_t, std::size_t, std::size_t>
  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 std::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