ceph/src/boost/boost/histogram/axis/regular.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_AXIS_REGULAR_HPP
   8 #define BOOST_HISTOGRAM_AXIS_REGULAR_HPP
   9
  10 #include <boost/core/nvp.hpp>
  11 #include <boost/histogram/axis/interval_view.hpp>
  12 #include <boost/histogram/axis/iterator.hpp>
  13 #include <boost/histogram/axis/metadata_base.hpp>
  14 #include <boost/histogram/axis/option.hpp>
  15 #include <boost/histogram/detail/convert_integer.hpp>
  16 #include <boost/histogram/detail/relaxed_equal.hpp>
  17 #include <boost/histogram/detail/replace_type.hpp>
  18 #include <boost/histogram/fwd.hpp>
  19 #include <boost/mp11/utility.hpp>
  20 #include <boost/throw_exception.hpp>
  21 #include <cassert>
  22 #include <cmath>
  23 #include <limits>
  24 #include <stdexcept>
  25 #include <string>
  26 #include <type_traits>
  27 #include <utility>
  28
  29 namespace boost {
  30 namespace histogram {
  31 namespace detail {
  32
  33 template <class T>
  34 using get_scale_type_helper = typename T::value_type;
  35
  36 template <class T>
  37 using get_scale_type = mp11::mp_eval_or<T, detail::get_scale_type_helper, T>;
  38
  39 struct one_unit {};
  40
  41 template <class T>
  42 T operator*(T&& t, const one_unit&) {
  43   return std::forward<T>(t);
  44 }
  45
  46 template <class T>
  47 T operator/(T&& t, const one_unit&) {
  48   return std::forward<T>(t);
  49 }
  50
  51 template <class T>
  52 using get_unit_type_helper = typename T::unit_type;
  53
  54 template <class T>
  55 using get_unit_type = mp11::mp_eval_or<one_unit, detail::get_unit_type_helper, T>;
  56
  57 template <class T, class R = get_scale_type<T>>
  58 R get_scale(const T& t) {
  59   return t / get_unit_type<T>();
  60 }
  61
  62 } // namespace detail
  63
  64 namespace axis {
  65
  66 namespace transform {
  67
  68 /// Identity transform for equidistant bins.
  69 struct id {
  70   /// Pass-through.
  71   template <class T>
  72   static T forward(T&& x) noexcept {
  73     return std::forward<T>(x);
  74   }
  75
  76   /// Pass-through.
  77   template <class T>
  78   static T inverse(T&& x) noexcept {
  79     return std::forward<T>(x);
  80   }
  81
  82   template <class Archive>
  83   void serialize(Archive&, unsigned /* version */) {}
  84 };
  85
  86 /// Log transform for equidistant bins in log-space.
  87 struct log {
  88   /// Returns log(x) of external value x.
  89   template <class T>
  90   static T forward(T x) {
  91     return std::log(x);
  92   }
  93
  94   /// Returns exp(x) for internal value x.
  95   template <class T>
  96   static T inverse(T x) {
  97     return std::exp(x);
  98   }
  99
 100   template <class Archive>
 101   void serialize(Archive&, unsigned /* version */) {}
 102 };
 103
 104 /// Sqrt transform for equidistant bins in sqrt-space.
 105 struct sqrt {
 106   /// Returns sqrt(x) of external value x.
 107   template <class T>
 108   static T forward(T x) {
 109     return std::sqrt(x);
 110   }
 111
 112   /// Returns x^2 of internal value x.
 113   template <class T>
 114   static T inverse(T x) {
 115     return x * x;
 116   }
 117
 118   template <class Archive>
 119   void serialize(Archive&, unsigned /* version */) {}
 120 };
 121
 122 /// Pow transform for equidistant bins in pow-space.
 123 struct pow {
 124   double power = 1; /**< power index */
 125
 126   /// Make transform with index p.
 127   explicit pow(double p) : power(p) {}
 128   pow() = default;
 129
 130   /// Returns pow(x, power) of external value x.
 131   template <class T>
 132   auto forward(T x) const {
 133     return std::pow(x, power);
 134   }
 135
 136   /// Returns pow(x, 1/power) of external value x.
 137   template <class T>
 138   auto inverse(T x) const {
 139     return std::pow(x, 1.0 / power);
 140   }
 141
 142   bool operator==(const pow& o) const noexcept { return power == o.power; }
 143
 144   template <class Archive>
 145   void serialize(Archive& ar, unsigned /* version */) {
 146     ar& make_nvp("power", power);
 147   }
 148 };
 149
 150 } // namespace transform
 151
 152 #ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED
 153 // Type envelope to mark value as step size
 154 template <class T>
 155 struct step_type {
 156   T value;
 157 };
 158 #endif
 159
 160 /**
 161   Helper function to mark argument as step size.
 162  */
 163 template <class T>
 164 step_type<T> step(T t) {
 165   return step_type<T>{t};
 166 }
 167
 168 /** Axis for equidistant intervals on the real line.
 169
 170    The most common binning strategy. Very fast. Binning is a O(1) operation.
 171
 172    If the axis has an overflow bin (the default), a value on the upper edge of the last
 173    bin is put in the overflow bin. The axis range represents a semi-open interval.
 174
 175    If the overflow bin is deactivated, then a value on the upper edge of the last bin is
 176    still counted towards the last bin. The axis range represents a closed interval. This
 177    is the desired behavior for random numbers drawn from a bounded interval, which is
 178    usually closed.
 179
 180    @tparam Value input value type, must be floating point.
 181    @tparam Transform builtin or user-defined transform type.
 182    @tparam MetaData type to store meta data.
 183    @tparam Options see boost::histogram::axis::option.
 184  */
 185 template <class Value, class Transform, class MetaData, class Options>
 186 class regular : public iterator_mixin<regular<Value, Transform, MetaData, Options>>,
 187                 protected detail::replace_default<Transform, transform::id>,
 188                 public metadata_base_t<MetaData> {
 189   // these must be private, so that they are not automatically inherited
 190   using value_type = Value;
 191   using transform_type = detail::replace_default<Transform, transform::id>;
 192   using metadata_base = metadata_base_t<MetaData>;
 193   using metadata_type = typename metadata_base::metadata_type;
 194   using options_type =
 195       detail::replace_default<Options, decltype(option::underflow | option::overflow)>;
 196
 197   static_assert(std::is_nothrow_move_constructible<transform_type>::value,
 198                 "transform must be no-throw move constructible");
 199   static_assert(std::is_nothrow_move_assignable<transform_type>::value,
 200                 "transform must be no-throw move assignable");
 201
 202   using unit_type = detail::get_unit_type<value_type>;
 203   using internal_value_type = detail::get_scale_type<value_type>;
 204
 205   static_assert(std::is_floating_point<internal_value_type>::value,
 206                 "regular axis requires floating point type");
 207
 208   static_assert(
 209       (!options_type::test(option::circular) && !options_type::test(option::growth)) ||
 210           (options_type::test(option::circular) ^ options_type::test(option::growth)),
 211       "circular and growth options are mutually exclusive");
 212
 213 public:
 214   constexpr regular() = default;
 215
 216   /** Construct n bins over real transformed range [start, stop).
 217
 218      @param trans    transform instance to use.
 219      @param n        number of bins.
 220      @param start    low edge of first bin.
 221      @param stop     high edge of last bin.
 222      @param meta     description of the axis (optional).
 223      @param options  see boost::histogram::axis::option (optional).
 224    */
 225   regular(transform_type trans, unsigned n, value_type start, value_type stop,
 226           metadata_type meta = {}, options_type options = {})
 227       : transform_type(std::move(trans))
 228       , metadata_base(std::move(meta))
 229       , size_(static_cast<index_type>(n))
 230       , min_(this->forward(detail::get_scale(start)))
 231       , delta_(this->forward(detail::get_scale(stop)) - min_) {
 232     (void)options;
 233     if (size() == 0) BOOST_THROW_EXCEPTION(std::invalid_argument("bins > 0 required"));
 234     if (!std::isfinite(min_) || !std::isfinite(delta_))
 235       BOOST_THROW_EXCEPTION(
 236           std::invalid_argument("forward transform of start or stop invalid"));
 237     if (delta_ == 0)
 238       BOOST_THROW_EXCEPTION(std::invalid_argument("range of axis is zero"));
 239   }
 240
 241   /** Construct n bins over real range [start, stop).
 242
 243      @param n        number of bins.
 244      @param start    low edge of first bin.
 245      @param stop     high edge of last bin.
 246      @param meta     description of the axis (optional).
 247      @param options  see boost::histogram::axis::option (optional).
 248    */
 249   regular(unsigned n, value_type start, value_type stop, metadata_type meta = {},
 250           options_type options = {})
 251       : regular({}, n, start, stop, std::move(meta), options) {}
 252
 253   /** Construct bins with the given step size over real transformed range
 254      [start, stop).
 255
 256      @param trans    transform instance to use.
 257      @param step     width of a single bin.
 258      @param start    low edge of first bin.
 259      @param stop     upper limit of high edge of last bin (see below).
 260      @param meta     description of the axis (optional).
 261      @param options  see boost::histogram::axis::option (optional).
 262
 263      The axis computes the number of bins as n = abs(stop - start) / step,
 264      rounded down. This means that stop is an upper limit to the actual value
 265      (start + n * step).
 266    */
 267   template <class T>
 268   regular(transform_type trans, step_type<T> step, value_type start, value_type stop,
 269           metadata_type meta = {}, options_type options = {})
 270       : regular(trans, static_cast<index_type>(std::abs(stop - start) / step.value),
 271                 start,
 272                 start + static_cast<index_type>(std::abs(stop - start) / step.value) *
 273                             step.value,
 274                 std::move(meta), options) {}
 275
 276   /** Construct bins with the given step size over real range [start, stop).
 277
 278      @param step     width of a single bin.
 279      @param start    low edge of first bin.
 280      @param stop     upper limit of high edge of last bin (see below).
 281      @param meta     description of the axis (optional).
 282      @param options  see boost::histogram::axis::option (optional).
 283
 284      The axis computes the number of bins as n = abs(stop - start) / step,
 285      rounded down. This means that stop is an upper limit to the actual value
 286      (start + n * step).
 287    */
 288   template <class T>
 289   regular(step_type<T> step, value_type start, value_type stop, metadata_type meta = {},
 290           options_type options = {})
 291       : regular({}, step, start, stop, std::move(meta), options) {}
 292
 293   /// Constructor used by algorithm::reduce to shrink and rebin (not for users).
 294   regular(const regular& src, index_type begin, index_type end, unsigned merge)
 295       : regular(src.transform(), (end - begin) / merge, src.value(begin), src.value(end),
 296                 src.metadata()) {
 297     assert((end - begin) % merge == 0);
 298     if (options_type::test(option::circular) && !(begin == 0 && end == src.size()))
 299       BOOST_THROW_EXCEPTION(std::invalid_argument("cannot shrink circular axis"));
 300   }
 301
 302   /// Return instance of the transform type.
 303   const transform_type& transform() const noexcept { return *this; }
 304
 305   /// Return index for value argument.
 306   index_type index(value_type x) const noexcept {
 307     // Runs in hot loop, please measure impact of changes
 308     auto z = (this->forward(x / unit_type{}) - min_) / delta_;
 309     if (options_type::test(option::circular)) {
 310       if (std::isfinite(z)) {
 311         z -= std::floor(z);
 312         return static_cast<index_type>(z * size());
 313       }
 314     } else {
 315       if (z < 1) {
 316         if (z >= 0)
 317           return static_cast<index_type>(z * size());
 318         else
 319           return -1;
 320       }
 321       // upper edge of last bin is inclusive if overflow bin is not present
 322       if (!options_type::test(option::overflow) && z == 1) return size() - 1;
 323     }
 324     return size(); // also returned if x is NaN
 325   }
 326
 327   /// Returns index and shift (if axis has grown) for the passed argument.
 328   std::pair<index_type, index_type> update(value_type x) noexcept {
 329     assert(options_type::test(option::growth));
 330     const auto z = (this->forward(x / unit_type{}) - min_) / delta_;
 331     if (z < 1) { // don't use i here!
 332       if (z >= 0) {
 333         const auto i = static_cast<axis::index_type>(z * size());
 334         return {i, 0};
 335       }
 336       if (z != -std::numeric_limits<internal_value_type>::infinity()) {
 337         const auto stop = min_ + delta_;
 338         const auto i = static_cast<axis::index_type>(std::floor(z * size()));
 339         min_ += i * (delta_ / size());
 340         delta_ = stop - min_;
 341         size_ -= i;
 342         return {0, -i};
 343       }
 344       // z is -infinity
 345       return {-1, 0};
 346     }
 347     // z either beyond range, infinite, or NaN
 348     if (z < std::numeric_limits<internal_value_type>::infinity()) {
 349       const auto i = static_cast<axis::index_type>(z * size());
 350       const auto n = i - size() + 1;
 351       delta_ /= size();
 352       delta_ *= size() + n;
 353       size_ += n;
 354       return {i, -n};
 355     }
 356     // z either infinite or NaN
 357     return {size(), 0};
 358   }
 359
 360   /// Return value for fractional index argument.
 361   value_type value(real_index_type i) const noexcept {
 362     auto z = i / size();
 363     if (!options_type::test(option::circular) && z < 0.0)
 364       z = -std::numeric_limits<internal_value_type>::infinity() * delta_;
 365     else if (options_type::test(option::circular) || z <= 1.0)
 366       z = (1.0 - z) * min_ + z * (min_ + delta_);
 367     else {
 368       z = std::numeric_limits<internal_value_type>::infinity() * delta_;
 369     }
 370     return static_cast<value_type>(this->inverse(z) * unit_type());
 371   }
 372
 373   /// Return bin for index argument.
 374   decltype(auto) bin(index_type idx) const noexcept {
 375     return interval_view<regular>(*this, idx);
 376   }
 377
 378   /// Returns the number of bins, without over- or underflow.
 379   index_type size() const noexcept { return size_; }
 380
 381   /// Returns the options.
 382   static constexpr unsigned options() noexcept { return options_type::value; }
 383
 384   template <class V, class T, class M, class O>
 385   bool operator==(const regular<V, T, M, O>& o) const noexcept {
 386     return detail::relaxed_equal{}(transform(), o.transform()) && size() == o.size() &&
 387            min_ == o.min_ && delta_ == o.delta_ &&
 388            detail::relaxed_equal{}(this->metadata(), o.metadata());
 389   }
 390   template <class V, class T, class M, class O>
 391   bool operator!=(const regular<V, T, M, O>& o) const noexcept {
 392     return !operator==(o);
 393   }
 394
 395   template <class Archive>
 396   void serialize(Archive& ar, unsigned /* version */) {
 397     ar& make_nvp("transform", static_cast<transform_type&>(*this));
 398     ar& make_nvp("size", size_);
 399     ar& make_nvp("meta", this->metadata());
 400     ar& make_nvp("min", min_);
 401     ar& make_nvp("delta", delta_);
 402   }
 403
 404 private:
 405   index_type size_{0};
 406   internal_value_type min_{0}, delta_{1};
 407
 408   template <class V, class T, class M, class O>
 409   friend class regular;
 410 };
 411
 412 #if __cpp_deduction_guides >= 201606
 413
 414 template <class T>
 415 regular(unsigned, T, T)
 416     -> regular<detail::convert_integer<T, double>, transform::id, null_type>;
 417
 418 template <class T, class M>
 419 regular(unsigned, T, T, M) -> regular<detail::convert_integer<T, double>, transform::id,
 420                                       detail::replace_cstring<std::decay_t<M>>>;
 421
 422 template <class T, class M, unsigned B>
 423 regular(unsigned, T, T, M, const option::bitset<B>&)
 424     -> regular<detail::convert_integer<T, double>, transform::id,
 425                detail::replace_cstring<std::decay_t<M>>, option::bitset<B>>;
 426
 427 template <class Tr, class T, class = detail::requires_transform<Tr, T>>
 428 regular(Tr, unsigned, T, T) -> regular<detail::convert_integer<T, double>, Tr, null_type>;
 429
 430 template <class Tr, class T, class M>
 431 regular(Tr, unsigned, T, T, M) -> regular<detail::convert_integer<T, double>, Tr,
 432                                           detail::replace_cstring<std::decay_t<M>>>;
 433
 434 template <class Tr, class T, class M, unsigned B>
 435 regular(Tr, unsigned, T, T, M, const option::bitset<B>&)
 436     -> regular<detail::convert_integer<T, double>, Tr,
 437                detail::replace_cstring<std::decay_t<M>>, option::bitset<B>>;
 438
 439 #endif
 440
 441 /// Regular axis with circular option already set.
 442 template <class Value = double, class MetaData = use_default, class Options = use_default>
 443 #ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED
 444 using circular = regular<Value, transform::id, MetaData,
 445                          decltype(detail::replace_default<Options, option::overflow_t>{} |
 446                                   option::circular)>;
 447 #else
 448 class circular;
 449 #endif
 450
 451 } // namespace axis
 452 } // namespace histogram
 453 } // namespace boost
 454
 455 #endif