ceph/src/boost/boost/histogram/detail/linearize.hpp

   1 // Copyright 2019 Hans Dembinski
   2 //
   3 // Distributed under the Boost Software License, Version 1.0.
   4 // (See accompanying file LICENSE_1_0.txt
   5 // or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_HISTOGRAM_DETAIL_LINEARIZE_HPP
   8 #define BOOST_HISTOGRAM_DETAIL_LINEARIZE_HPP
   9
  10 #include <boost/histogram/axis/option.hpp>
  11 #include <boost/histogram/axis/traits.hpp>
  12 #include <boost/histogram/axis/variant.hpp>
  13 #include <boost/histogram/detail/optional_index.hpp>
  14 #include <boost/histogram/fwd.hpp>
  15 #include <boost/histogram/multi_index.hpp>
  16 #include <cassert>
  17
  18 namespace boost {
  19 namespace histogram {
  20 namespace detail {
  21
  22 // initial offset to out must be set;
  23 // this faster code can be used if all axes are inclusive
  24 template <class Opts>
  25 std::size_t linearize(Opts, std::size_t& out, const std::size_t stride,
  26                       const axis::index_type size, const axis::index_type idx) {
  27   constexpr bool u = Opts::test(axis::option::underflow);
  28   constexpr bool o = Opts::test(axis::option::overflow);
  29   assert(idx >= (u ? -1 : 0));
  30   assert(idx < (o ? size + 1 : size));
  31   assert(idx >= 0 || static_cast<std::size_t>(-idx * stride) <= out);
  32   out += idx * stride;
  33   return size + u + o;
  34 }
  35
  36 // initial offset to out must be set
  37 // this slower code must be used if not all axes are inclusive
  38 template <class Opts>
  39 std::size_t linearize(Opts, optional_index& out, const std::size_t stride,
  40                       const axis::index_type size, const axis::index_type idx) {
  41   constexpr bool u = Opts::test(axis::option::underflow);
  42   constexpr bool o = Opts::test(axis::option::overflow);
  43   assert(idx >= -1);
  44   assert(idx < size + 1);
  45   const bool is_valid = (u || idx >= 0) && (o || idx < size);
  46   if (is_valid)
  47     out += idx * stride;
  48   else
  49     out = invalid_index;
  50   return size + u + o;
  51 }
  52
  53 template <class Index, class Axis, class Value>
  54 std::size_t linearize(Index& out, const std::size_t stride, const Axis& ax,
  55                       const Value& v) {
  56   // mask options to reduce no. of template instantiations
  57   constexpr auto opts = axis::traits::get_options<Axis>{} &
  58                         (axis::option::underflow | axis::option::overflow);
  59   return linearize(opts, out, stride, ax.size(), axis::traits::index(ax, v));
  60 }
  61
  62 /**
  63   Must be used when axis is potentially growing. Also works for non-growing axis.
  64
  65   Initial offset of `out` must be zero. We cannot assert on this, because we do not
  66   know if this is the first call of `linearize_growth`.
  67 */
  68 template <class Index, class Axis, class Value>
  69 std::size_t linearize_growth(Index& out, axis::index_type& shift,
  70                              const std::size_t stride, Axis& a, const Value& v) {
  71   axis::index_type idx;
  72   std::tie(idx, shift) = axis::traits::update(a, v);
  73   constexpr bool u = axis::traits::get_options<Axis>::test(axis::option::underflow);
  74   if (u) ++idx;
  75   if (std::is_same<Index, std::size_t>::value) {
  76     assert(idx < axis::traits::extent(a));
  77     out += idx * stride;
  78   } else {
  79     if (0 <= idx && idx < axis::traits::extent(a))
  80       out += idx * stride;
  81     else
  82       out = invalid_index;
  83   }
  84   return axis::traits::extent(a);
  85 }
  86
  87 // initial offset of out must be zero
  88 template <class A>
  89 std::size_t linearize_index(optional_index& out, const std::size_t stride, const A& ax,
  90                             const axis::index_type idx) noexcept {
  91   const auto opt = axis::traits::get_options<A>();
  92   const axis::index_type begin = opt & axis::option::underflow ? -1 : 0;
  93   const axis::index_type end = opt & axis::option::overflow ? ax.size() + 1 : ax.size();
  94   const axis::index_type extent = end - begin;
  95   // i may be arbitrarily out of range
  96   if (begin <= idx && idx < end)
  97     out += (idx - begin) * stride;
  98   else
  99     out = invalid_index;
 100   return extent;
 101 }
 102
 103 template <class A, std::size_t N>
 104 optional_index linearize_indices(const A& axes, const multi_index<N>& indices) noexcept {
 105   assert(axes_rank(axes) == detail::size(indices));
 106
 107   optional_index idx{0}; // offset not used by linearize_index
 108   auto stride = static_cast<std::size_t>(1);
 109   using std::begin;
 110   auto i = begin(indices);
 111   for_each_axis(axes,
 112                 [&](const auto& a) { stride *= linearize_index(idx, stride, a, *i++); });
 113   return idx;
 114 }
 115
 116 template <class Index, class... Ts, class Value>
 117 std::size_t linearize(Index& o, const std::size_t s, const axis::variant<Ts...>& a,
 118                       const Value& v) {
 119   return axis::visit([&o, &s, &v](const auto& a) { return linearize(o, s, a, v); }, a);
 120 }
 121
 122 template <class Index, class... Ts, class Value>
 123 std::size_t linearize_growth(Index& o, axis::index_type& sh, const std::size_t st,
 124                              axis::variant<Ts...>& a, const Value& v) {
 125   return axis::visit([&](auto& a) { return linearize_growth(o, sh, st, a, v); }, a);
 126 }
 127
 128 } // namespace detail
 129 } // namespace histogram
 130 } // namespace boost
 131
 132 #endif // BOOST_HISTOGRAM_DETAIL_LINEARIZE_HPP