histogram/detail/linearize.hpp

0001 // Copyright 2019 Hans Dembinski
0002 //
0003 // Distributed under the Boost Software License, Version 1.0.
0004 // (See accompanying file LICENSE_1_0.txt
0005 // or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_HISTOGRAM_DETAIL_LINEARIZE_HPP
0008 #define BOOST_HISTOGRAM_DETAIL_LINEARIZE_HPP
0009
0010 #include <boost/histogram/axis/option.hpp>
0011 #include <boost/histogram/axis/traits.hpp>
0012 #include <boost/histogram/axis/variant.hpp>
0013 #include <boost/histogram/detail/optional_index.hpp>
0014 #include <boost/histogram/fwd.hpp>
0015 #include <boost/histogram/multi_index.hpp>
0016 #include <cassert>
0017
0018 namespace boost {
0019 namespace histogram {
0020 namespace detail {
0021
0022 // initial offset to out must be set;
0023 // this faster code can be used if all axes are inclusive
0024 template <class Opts>
0025 std::size_t linearize(Opts, std::size_t& out, const std::size_t stride,
0026                       const axis::index_type size, const axis::index_type idx) {
0027   constexpr bool u = Opts::test(axis::option::underflow);
0028   constexpr bool o = Opts::test(axis::option::overflow);
0029   assert(idx >= (u ? -1 : 0));
0030   assert(idx < (o ? size + 1 : size));
0031   assert(idx >= 0 || static_cast<std::size_t>(-idx * stride) <= out);
0032   out += idx * stride;
0033   return size + u + o;
0034 }
0035
0036 // initial offset to out must be set
0037 // this slower code must be used if not all axes are inclusive
0038 template <class Opts>
0039 std::size_t linearize(Opts, optional_index& out, const std::size_t stride,
0040                       const axis::index_type size, const axis::index_type idx) {
0041   constexpr bool u = Opts::test(axis::option::underflow);
0042   constexpr bool o = Opts::test(axis::option::overflow);
0043   assert(idx >= -1);
0044   assert(idx < size + 1);
0045   const bool is_valid = (u || idx >= 0) && (o || idx < size);
0046   if (is_valid)
0047     out += idx * stride;
0048   else
0049     out = invalid_index;
0050   return size + u + o;
0051 }
0052
0053 template <class Index, class Axis, class Value>
0054 std::size_t linearize(Index& out, const std::size_t stride, const Axis& ax,
0055                       const Value& v) {
0056   // mask options to reduce no. of template instantiations
0057   constexpr auto opts = axis::traits::get_options<Axis>{} &
0058                         (axis::option::underflow | axis::option::overflow);
0059   return linearize(opts, out, stride, ax.size(), axis::traits::index(ax, v));
0060 }
0061
0062 /**
0063   Must be used when axis is potentially growing. Also works for non-growing axis.
0064
0065   Initial offset of `out` must be zero. We cannot assert on this, because we do not
0066   know if this is the first call of `linearize_growth`.
0067 */
0068 template <class Index, class Axis, class Value>
0069 std::size_t linearize_growth(Index& out, axis::index_type& shift,
0070                              const std::size_t stride, Axis& a, const Value& v) {
0071   axis::index_type idx;
0072   std::tie(idx, shift) = axis::traits::update(a, v);
0073   constexpr bool u = axis::traits::get_options<Axis>::test(axis::option::underflow);
0074   if (u) ++idx;
0075   if (std::is_same<Index, std::size_t>::value) {
0076     assert(idx < axis::traits::extent(a));
0077     out += idx * stride;
0078   } else {
0079     if (0 <= idx && idx < axis::traits::extent(a))
0080       out += idx * stride;
0081     else
0082       out = invalid_index;
0083   }
0084   return axis::traits::extent(a);
0085 }
0086
0087 // initial offset of out must be zero
0088 template <class A>
0089 std::size_t linearize_index(optional_index& out, const std::size_t stride, const A& ax,
0090                             const axis::index_type idx) noexcept {
0091   const auto opt = axis::traits::get_options<A>();
0092   const axis::index_type begin = opt & axis::option::underflow ? -1 : 0;
0093   const axis::index_type end = opt & axis::option::overflow ? ax.size() + 1 : ax.size();
0094   const axis::index_type extent = end - begin;
0095   // i may be arbitrarily out of range
0096   if (begin <= idx && idx < end)
0097     out += (idx - begin) * stride;
0098   else
0099     out = invalid_index;
0100   return extent;
0101 }
0102
0103 template <class A, std::size_t N>
0104 optional_index linearize_indices(const A& axes, const multi_index<N>& indices) noexcept {
0105   assert(axes_rank(axes) == detail::size(indices));
0106
0107   optional_index idx{0}; // offset not used by linearize_index
0108   auto stride = static_cast<std::size_t>(1);
0109   using std::begin;
0110   auto i = begin(indices);
0111   for_each_axis(axes,
0112                 [&](const auto& a) { stride *= linearize_index(idx, stride, a, *i++); });
0113   return idx;
0114 }
0115
0116 template <class Index, class... Ts, class Value>
0117 std::size_t linearize(Index& o, const std::size_t s, const axis::variant<Ts...>& a,
0118                       const Value& v) {
0119   return axis::visit([&o, &s, &v](const auto& a) { return linearize(o, s, a, v); }, a);
0120 }
0121
0122 template <class Index, class... Ts, class Value>
0123 std::size_t linearize_growth(Index& o, axis::index_type& sh, const std::size_t st,
0124                              axis::variant<Ts...>& a, const Value& v) {
0125   return axis::visit([&](auto& a) { return linearize_growth(o, sh, st, a, v); }, a);
0126 }
0127
0128 } // namespace detail
0129 } // namespace histogram
0130 } // namespace boost
0131
0132 #endif // BOOST_HISTOGRAM_DETAIL_LINEARIZE_HPP