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

   1 // Copyright 2015-2018 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_AXES_HPP
   8 #define BOOST_HISTOGRAM_DETAIL_AXES_HPP
   9
  10 #include <array>
  11 #include <boost/core/nvp.hpp>
  12 #include <boost/histogram/axis/traits.hpp>
  13 #include <boost/histogram/axis/variant.hpp>
  14 #include <boost/histogram/detail/make_default.hpp>
  15 #include <boost/histogram/detail/nonmember_container_access.hpp>
  16 #include <boost/histogram/detail/optional_index.hpp>
  17 #include <boost/histogram/detail/priority.hpp>
  18 #include <boost/histogram/detail/relaxed_tuple_size.hpp>
  19 #include <boost/histogram/detail/static_if.hpp>
  20 #include <boost/histogram/detail/sub_array.hpp>
  21 #include <boost/histogram/detail/try_cast.hpp>
  22 #include <boost/histogram/fwd.hpp>
  23 #include <boost/mp11/algorithm.hpp>
  24 #include <boost/mp11/integer_sequence.hpp>
  25 #include <boost/mp11/list.hpp>
  26 #include <boost/mp11/tuple.hpp>
  27 #include <boost/mp11/utility.hpp>
  28 #include <boost/throw_exception.hpp>
  29 #include <cassert>
  30 #include <initializer_list>
  31 #include <iterator>
  32 #include <stdexcept>
  33 #include <string>
  34 #include <tuple>
  35 #include <type_traits>
  36 #include <vector>
  37
  38 namespace boost {
  39 namespace histogram {
  40 namespace detail {
  41
  42 template <class T, class Unary>
  43 void for_each_axis_impl(dynamic_size, T& t, Unary& p) {
  44   for (auto& a : t) axis::visit(p, a);
  45 }
  46
  47 template <class N, class T, class Unary>
  48 void for_each_axis_impl(N, T& t, Unary& p) {
  49   mp11::tuple_for_each(t, p);
  50 }
  51
  52 // also matches const T and const Unary
  53 template <class T, class Unary>
  54 void for_each_axis(T&& t, Unary&& p) {
  55   for_each_axis_impl(relaxed_tuple_size(t), t, p);
  56 }
  57
  58 // merge if a and b are discrete and growing
  59 struct axis_merger {
  60   template <class T, class U>
  61   T operator()(const T& a, const U& u) {
  62     const T* bp = ptr_cast<T>(&u);
  63     if (!bp) BOOST_THROW_EXCEPTION(std::invalid_argument("axes not mergable"));
  64     using O = axis::traits::get_options<T>;
  65     constexpr bool discrete_and_growing =
  66         axis::traits::is_continuous<T>::value == false && O::test(axis::option::growth);
  67     return impl(mp11::mp_bool<discrete_and_growing>{}, a, *bp);
  68   }
  69
  70   template <class T>
  71   T impl(std::false_type, const T& a, const T& b) {
  72     if (!relaxed_equal{}(a, b))
  73       BOOST_THROW_EXCEPTION(std::invalid_argument("axes not mergable"));
  74     return a;
  75   }
  76
  77   template <class T>
  78   T impl(std::true_type, const T& a, const T& b) {
  79     if (relaxed_equal{}(axis::traits::metadata(a), axis::traits::metadata(b))) {
  80       auto r = a;
  81       if (axis::traits::is_ordered<T>::value) {
  82         r.update(b.value(0));
  83         r.update(b.value(b.size() - 1));
  84       } else
  85         for (auto&& v : b) r.update(v);
  86       return r;
  87     }
  88     return impl(std::false_type{}, a, b);
  89   }
  90 };
  91
  92 // create empty dynamic axis which can store any axes types from the argument
  93 template <class T>
  94 auto make_empty_dynamic_axes(const T& axes) {
  95   return make_default(axes);
  96 }
  97
  98 template <class... Ts>
  99 auto make_empty_dynamic_axes(const std::tuple<Ts...>&) {
 100   using namespace ::boost::mp11;
 101   using L = mp_unique<axis::variant<Ts...>>;
 102   // return std::vector<axis::variant<Axis0, Axis1, ...>> or std::vector<Axis0>
 103   return std::vector<mp_if_c<(mp_size<L>::value == 1), mp_first<L>, L>>{};
 104 }
 105
 106 template <class T, class Functor, std::size_t... Is>
 107 auto axes_transform_impl(const T& t, Functor&& f, mp11::index_sequence<Is...>) {
 108   return std::make_tuple(f(Is, std::get<Is>(t))...);
 109 }
 110
 111 // warning: sequential order of functor execution is platform-dependent!
 112 template <class... Ts, class Functor>
 113 auto axes_transform(const std::tuple<Ts...>& old_axes, Functor&& f) {
 114   return axes_transform_impl(old_axes, std::forward<Functor>(f),
 115                              mp11::make_index_sequence<sizeof...(Ts)>{});
 116 }
 117
 118 // changing axes type is not supported
 119 template <class T, class Functor>
 120 T axes_transform(const T& old_axes, Functor&& f) {
 121   T axes = make_default(old_axes);
 122   axes.reserve(old_axes.size());
 123   for_each_axis(old_axes, [&](const auto& a) { axes.emplace_back(f(axes.size(), a)); });
 124   return axes;
 125 }
 126
 127 template <class... Ts, class Binary, std::size_t... Is>
 128 std::tuple<Ts...> axes_transform_impl(const std::tuple<Ts...>& lhs,
 129                                       const std::tuple<Ts...>& rhs, Binary&& bin,
 130                                       mp11::index_sequence<Is...>) {
 131   return std::make_tuple(bin(std::get<Is>(lhs), std::get<Is>(rhs))...);
 132 }
 133
 134 template <class... Ts, class Binary>
 135 std::tuple<Ts...> axes_transform(const std::tuple<Ts...>& lhs,
 136                                  const std::tuple<Ts...>& rhs, Binary&& bin) {
 137   return axes_transform_impl(lhs, rhs, bin, mp11::make_index_sequence<sizeof...(Ts)>{});
 138 }
 139
 140 template <class T, class Binary>
 141 T axes_transform(const T& lhs, const T& rhs, Binary&& bin) {
 142   T ax = make_default(lhs);
 143   ax.reserve(lhs.size());
 144   using std::begin;
 145   auto ir = begin(rhs);
 146   for (auto&& li : lhs) {
 147     axis::visit(
 148         [&](const auto& li) {
 149           axis::visit([&](const auto& ri) { ax.emplace_back(bin(li, ri)); }, *ir);
 150         },
 151         li);
 152     ++ir;
 153   }
 154   return ax;
 155 }
 156
 157 template <class T>
 158 unsigned axes_rank(const T& axes) {
 159   using std::begin;
 160   using std::end;
 161   return static_cast<unsigned>(std::distance(begin(axes), end(axes)));
 162 }
 163
 164 template <class... Ts>
 165 constexpr unsigned axes_rank(const std::tuple<Ts...>&) {
 166   return static_cast<unsigned>(sizeof...(Ts));
 167 }
 168
 169 template <class T>
 170 void throw_if_axes_is_too_large(const T& axes) {
 171   if (axes_rank(axes) > BOOST_HISTOGRAM_DETAIL_AXES_LIMIT)
 172     BOOST_THROW_EXCEPTION(
 173         std::invalid_argument("length of axis vector exceeds internal buffers, "
 174                               "recompile with "
 175                               "-DBOOST_HISTOGRAM_DETAIL_AXES_LIMIT=<new max size> "
 176                               "to increase internal buffers"));
 177 }
 178
 179 // tuple is never too large because internal buffers adapt to size of tuple
 180 template <class... Ts>
 181 void throw_if_axes_is_too_large(const std::tuple<Ts...>&) {}
 182
 183 template <unsigned N, class... Ts>
 184 decltype(auto) axis_get(std::tuple<Ts...>& axes) {
 185   return std::get<N>(axes);
 186 }
 187
 188 template <unsigned N, class... Ts>
 189 decltype(auto) axis_get(const std::tuple<Ts...>& axes) {
 190   return std::get<N>(axes);
 191 }
 192
 193 template <unsigned N, class T>
 194 decltype(auto) axis_get(T& axes) {
 195   return axes[N];
 196 }
 197
 198 template <unsigned N, class T>
 199 decltype(auto) axis_get(const T& axes) {
 200   return axes[N];
 201 }
 202
 203 template <class... Ts>
 204 auto axis_get(std::tuple<Ts...>& axes, const unsigned i) {
 205   constexpr auto S = sizeof...(Ts);
 206   using V = mp11::mp_unique<axis::variant<Ts*...>>;
 207   return mp11::mp_with_index<S>(i, [&axes](auto i) { return V(&std::get<i>(axes)); });
 208 }
 209
 210 template <class... Ts>
 211 auto axis_get(const std::tuple<Ts...>& axes, const unsigned i) {
 212   constexpr auto S = sizeof...(Ts);
 213   using V = mp11::mp_unique<axis::variant<const Ts*...>>;
 214   return mp11::mp_with_index<S>(i, [&axes](auto i) { return V(&std::get<i>(axes)); });
 215 }
 216
 217 template <class T>
 218 decltype(auto) axis_get(T& axes, const unsigned i) {
 219   return axes[i];
 220 }
 221
 222 template <class T>
 223 decltype(auto) axis_get(const T& axes, const unsigned i) {
 224   return axes[i];
 225 }
 226
 227 template <class T, class U, std::size_t... Is>
 228 bool axes_equal_impl(const T& t, const U& u, mp11::index_sequence<Is...>) noexcept {
 229   bool result = true;
 230   // operator folding emulation
 231   (void)std::initializer_list<bool>{
 232       (result &= relaxed_equal{}(std::get<Is>(t), std::get<Is>(u)))...};
 233   return result;
 234 }
 235
 236 template <class... Ts, class... Us>
 237 bool axes_equal_impl(const std::tuple<Ts...>& t, const std::tuple<Us...>& u) noexcept {
 238   return axes_equal_impl(
 239       t, u, mp11::make_index_sequence<std::min(sizeof...(Ts), sizeof...(Us))>{});
 240 }
 241
 242 template <class... Ts, class U>
 243 bool axes_equal_impl(const std::tuple<Ts...>& t, const U& u) noexcept {
 244   using std::begin;
 245   auto iu = begin(u);
 246   bool result = true;
 247   mp11::tuple_for_each(t, [&](const auto& ti) {
 248     axis::visit([&](const auto& ui) { result &= relaxed_equal{}(ti, ui); }, *iu);
 249     ++iu;
 250   });
 251   return result;
 252 }
 253
 254 template <class T, class... Us>
 255 bool axes_equal_impl(const T& t, const std::tuple<Us...>& u) noexcept {
 256   return axes_equal_impl(u, t);
 257 }
 258
 259 template <class T, class U>
 260 bool axes_equal_impl(const T& t, const U& u) noexcept {
 261   using std::begin;
 262   auto iu = begin(u);
 263   bool result = true;
 264   for (auto&& ti : t) {
 265     axis::visit(
 266         [&](const auto& ti) {
 267           axis::visit([&](const auto& ui) { result &= relaxed_equal{}(ti, ui); }, *iu);
 268         },
 269         ti);
 270     ++iu;
 271   }
 272   return result;
 273 }
 274
 275 template <class T, class U>
 276 bool axes_equal(const T& t, const U& u) noexcept {
 277   return axes_rank(t) == axes_rank(u) && axes_equal_impl(t, u);
 278 }
 279
 280 // enable_if_t needed by msvc :(
 281 template <class... Ts, class... Us>
 282 std::enable_if_t<!(std::is_same<std::tuple<Ts...>, std::tuple<Us...>>::value)>
 283 axes_assign(std::tuple<Ts...>&, const std::tuple<Us...>&) {
 284   BOOST_THROW_EXCEPTION(std::invalid_argument("cannot assign axes, types do not match"));
 285 }
 286
 287 template <class... Ts>
 288 void axes_assign(std::tuple<Ts...>& t, const std::tuple<Ts...>& u) {
 289   t = u;
 290 }
 291
 292 template <class... Ts, class U>
 293 void axes_assign(std::tuple<Ts...>& t, const U& u) {
 294   if (sizeof...(Ts) == detail::size(u)) {
 295     using std::begin;
 296     auto iu = begin(u);
 297     mp11::tuple_for_each(t, [&](auto& ti) {
 298       using T = std::decay_t<decltype(ti)>;
 299       ti = axis::get<T>(*iu);
 300       ++iu;
 301     });
 302     return;
 303   }
 304   BOOST_THROW_EXCEPTION(std::invalid_argument("cannot assign axes, sizes do not match"));
 305 }
 306
 307 template <class T, class... Us>
 308 void axes_assign(T& t, const std::tuple<Us...>& u) {
 309   // resize instead of reserve, because t may not be empty and we want exact capacity
 310   t.resize(sizeof...(Us));
 311   using std::begin;
 312   auto it = begin(t);
 313   mp11::tuple_for_each(u, [&](const auto& ui) { *it++ = ui; });
 314 }
 315
 316 template <class T, class U>
 317 void axes_assign(T& t, const U& u) {
 318   t.assign(u.begin(), u.end());
 319 }
 320
 321 template <class Archive, class T>
 322 void axes_serialize(Archive& ar, T& axes) {
 323   ar& make_nvp("axes", axes);
 324 }
 325
 326 template <class Archive, class... Ts>
 327 void axes_serialize(Archive& ar, std::tuple<Ts...>& axes) {
 328   // needed to keep serialization format backward compatible
 329   struct proxy {
 330     std::tuple<Ts...>& t;
 331     void serialize(Archive& ar, unsigned /* version */) {
 332       mp11::tuple_for_each(t, [&ar](auto& x) { ar& make_nvp("item", x); });
 333     }
 334   };
 335   proxy p{axes};
 336   ar& make_nvp("axes", p);
 337 }
 338
 339 // total number of bins including *flow bins
 340 template <class T>
 341 std::size_t bincount(const T& axes) {
 342   std::size_t n = 1;
 343   for_each_axis(axes, [&n](const auto& a) {
 344     const auto old = n;
 345     const auto s = axis::traits::extent(a);
 346     n *= s;
 347     if (s > 0 && n < old) BOOST_THROW_EXCEPTION(std::overflow_error("bincount overflow"));
 348   });
 349   return n;
 350 }
 351
 352 /** Initial offset for the linear index.
 353
 354   This precomputes an offset for the global index so that axis index = -1 addresses the
 355   first entry in the storage. Example: one-dim. histogram. The offset is 1, stride is 1,
 356   and global_index = offset + axis_index * stride == 0 addresses the first element of
 357   the storage.
 358
 359   Using the offset makes the hot inner loop that computes the global_index simpler and
 360   thus faster, because we do not have to branch for each axis to check whether it has
 361   an underflow bin.
 362
 363   The offset is set to an invalid value when the histogram contains at least one growing
 364   axis, because this optimization then cannot be used. See detail/linearize.hpp, in this
 365   case linearize_growth is called.
 366 */
 367 template <class T>
 368 std::size_t offset(const T& axes) {
 369   std::size_t n = 0;
 370   auto stride = static_cast<std::size_t>(1);
 371   for_each_axis(axes, [&](const auto& a) {
 372     if (axis::traits::options(a) & axis::option::growth)
 373       n = invalid_index;
 374     else if (n != invalid_index && axis::traits::options(a) & axis::option::underflow)
 375       n += stride;
 376     stride *= axis::traits::extent(a);
 377   });
 378   return n;
 379 }
 380
 381 // make default-constructed buffer (no initialization for POD types)
 382 template <class T, class A>
 383 auto make_stack_buffer(const A& a) {
 384   return sub_array<T, buffer_size<A>::value>(axes_rank(a));
 385 }
 386
 387 // make buffer with elements initialized to v
 388 template <class T, class A>
 389 auto make_stack_buffer(const A& a, const T& t) {
 390   return sub_array<T, buffer_size<A>::value>(axes_rank(a), t);
 391 }
 392
 393 template <class T>
 394 using has_underflow =
 395     decltype(axis::traits::get_options<T>::test(axis::option::underflow));
 396
 397 template <class T>
 398 using is_growing = decltype(axis::traits::get_options<T>::test(axis::option::growth));
 399
 400 template <class T>
 401 using is_not_inclusive = mp11::mp_not<axis::traits::is_inclusive<T>>;
 402
 403 // for vector<T>
 404 template <class T>
 405 struct axis_types_impl {
 406   using type = mp11::mp_list<std::decay_t<T>>;
 407 };
 408
 409 // for vector<variant<Ts...>>
 410 template <class... Ts>
 411 struct axis_types_impl<axis::variant<Ts...>> {
 412   using type = mp11::mp_list<std::decay_t<Ts>...>;
 413 };
 414
 415 // for tuple<Ts...>
 416 template <class... Ts>
 417 struct axis_types_impl<std::tuple<Ts...>> {
 418   using type = mp11::mp_list<std::decay_t<Ts>...>;
 419 };
 420
 421 template <class T>
 422 using axis_types =
 423     typename axis_types_impl<mp11::mp_if<is_vector_like<T>, mp11::mp_first<T>, T>>::type;
 424
 425 template <template <class> class Trait, class Axes>
 426 using has_special_axis = mp11::mp_any_of<axis_types<Axes>, Trait>;
 427
 428 template <class Axes>
 429 using has_growing_axis = mp11::mp_any_of<axis_types<Axes>, is_growing>;
 430
 431 template <class Axes>
 432 using has_non_inclusive_axis = mp11::mp_any_of<axis_types<Axes>, is_not_inclusive>;
 433
 434 template <class T>
 435 constexpr std::size_t type_score() {
 436   return sizeof(T) *
 437          (std::is_integral<T>::value ? 1 : std::is_floating_point<T>::value ? 10 : 100);
 438 }
 439
 440 // arbitrary ordering of types
 441 template <class T, class U>
 442 using type_less = mp11::mp_bool<(type_score<T>() < type_score<U>())>;
 443
 444 template <class Axes>
 445 using value_types = mp11::mp_sort<
 446     mp11::mp_unique<mp11::mp_transform<axis::traits::value_type, axis_types<Axes>>>,
 447     type_less>;
 448
 449 } // namespace detail
 450 } // namespace histogram
 451 } // namespace boost
 452
 453 #endif