ceph/src/boost/boost/histogram/axis/variable.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_VARIABLE_HPP
   8 #define BOOST_HISTOGRAM_AXIS_VARIABLE_HPP
   9
  10 #include <algorithm>
  11 #include <boost/core/nvp.hpp>
  12 #include <boost/histogram/axis/interval_view.hpp>
  13 #include <boost/histogram/axis/iterator.hpp>
  14 #include <boost/histogram/axis/metadata_base.hpp>
  15 #include <boost/histogram/axis/option.hpp>
  16 #include <boost/histogram/detail/convert_integer.hpp>
  17 #include <boost/histogram/detail/detect.hpp>
  18 #include <boost/histogram/detail/limits.hpp>
  19 #include <boost/histogram/detail/relaxed_equal.hpp>
  20 #include <boost/histogram/detail/replace_type.hpp>
  21 #include <boost/histogram/fwd.hpp>
  22 #include <boost/throw_exception.hpp>
  23 #include <cassert>
  24 #include <cmath>
  25 #include <limits>
  26 #include <memory>
  27 #include <stdexcept>
  28 #include <string>
  29 #include <type_traits>
  30 #include <utility>
  31 #include <vector>
  32
  33 namespace boost {
  34 namespace histogram {
  35 namespace axis {
  36
  37 /** Axis for non-equidistant bins on the real line.
  38
  39   Binning is a O(log(N)) operation. If speed matters and the problem domain
  40   allows it, prefer a regular axis, possibly with a transform.
  41
  42   If the axis has an overflow bin (the default), a value on the upper edge of the last
  43   bin is put in the overflow bin. The axis range represents a semi-open interval.
  44
  45   If the overflow bin is deactivated, then a value on the upper edge of the last bin is
  46   still counted towards the last bin. The axis range represents a closed interval. This
  47   is the desired behavior for random numbers drawn from a bounded interval, which is
  48   usually closed.
  49
  50   @tparam Value     input value type, must be floating point.
  51   @tparam MetaData  type to store meta data.
  52   @tparam Options   see boost::histogram::axis::option.
  53   @tparam Allocator allocator to use for dynamic memory management.
  54 */
  55 template <class Value, class MetaData, class Options, class Allocator>
  56 class variable : public iterator_mixin<variable<Value, MetaData, Options, Allocator>>,
  57                  public metadata_base_t<MetaData> {
  58   // these must be private, so that they are not automatically inherited
  59   using value_type = Value;
  60   using metadata_base = metadata_base_t<MetaData>;
  61   using metadata_type = typename metadata_base::metadata_type;
  62   using options_type =
  63       detail::replace_default<Options, decltype(option::underflow | option::overflow)>;
  64   using allocator_type = Allocator;
  65   using vector_type = std::vector<Value, allocator_type>;
  66
  67   static_assert(
  68       std::is_floating_point<value_type>::value,
  69       "current version of variable axis requires floating point type; "
  70       "if you need a variable axis with an integral type, please submit an issue");
  71
  72   static_assert(
  73       (!options_type::test(option::circular) && !options_type::test(option::growth)) ||
  74           (options_type::test(option::circular) ^ options_type::test(option::growth)),
  75       "circular and growth options are mutually exclusive");
  76
  77 public:
  78   constexpr variable() = default;
  79   explicit variable(allocator_type alloc) : vec_(alloc) {}
  80
  81   /** Construct from iterator range of bin edges.
  82
  83      @param begin   begin of edge sequence.
  84      @param end     end of edge sequence.
  85      @param meta    description of the axis (optional).
  86      @param options see boost::histogram::axis::option (optional).
  87      @param alloc   allocator instance to use (optional).
  88    */
  89   template <class It, class = detail::requires_iterator<It>>
  90   variable(It begin, It end, metadata_type meta = {}, options_type options = {},
  91            allocator_type alloc = {})
  92       : metadata_base(std::move(meta)), vec_(std::move(alloc)) {
  93     (void)options;
  94
  95     if (std::distance(begin, end) < 2)
  96       BOOST_THROW_EXCEPTION(std::invalid_argument("bins > 0 required"));
  97
  98     vec_.reserve(std::distance(begin, end));
  99     vec_.emplace_back(*begin++);
 100     bool strictly_ascending = true;
 101     for (; begin != end; ++begin) {
 102       strictly_ascending &= vec_.back() < *begin;
 103       vec_.emplace_back(*begin);
 104     }
 105     if (!strictly_ascending)
 106       BOOST_THROW_EXCEPTION(
 107           std::invalid_argument("input sequence must be strictly ascending"));
 108   }
 109
 110   // kept for backward compatibility
 111   template <class It, class = detail::requires_iterator<It>>
 112   variable(It begin, It end, metadata_type meta, allocator_type alloc)
 113       : variable(begin, end, std::move(meta), {}, std::move(alloc)) {}
 114
 115   /** Construct variable axis from iterable range of bin edges.
 116
 117      @param iterable iterable range of bin edges.
 118      @param meta     description of the axis (optional).
 119      @param options  see boost::histogram::axis::option (optional).
 120      @param alloc    allocator instance to use (optional).
 121    */
 122   template <class U, class = detail::requires_iterable<U>>
 123   variable(const U& iterable, metadata_type meta = {}, options_type options = {},
 124            allocator_type alloc = {})
 125       : variable(std::begin(iterable), std::end(iterable), std::move(meta), options,
 126                  std::move(alloc)) {}
 127
 128   // kept for backward compatibility
 129   template <class U, class = detail::requires_iterable<U>>
 130   variable(const U& iterable, metadata_type meta, allocator_type alloc)
 131       : variable(std::begin(iterable), std::end(iterable), std::move(meta), {},
 132                  std::move(alloc)) {}
 133
 134   /** Construct variable axis from initializer list of bin edges.
 135
 136      @param list     `std::initializer_list` of bin edges.
 137      @param meta     description of the axis (optional).
 138      @param options  see boost::histogram::axis::option (optional).
 139      @param alloc    allocator instance to use (optional).
 140    */
 141   template <class U>
 142   variable(std::initializer_list<U> list, metadata_type meta = {},
 143            options_type options = {}, allocator_type alloc = {})
 144       : variable(list.begin(), list.end(), std::move(meta), options, std::move(alloc)) {}
 145
 146   // kept for backward compatibility
 147   template <class U>
 148   variable(std::initializer_list<U> list, metadata_type meta, allocator_type alloc)
 149       : variable(list.begin(), list.end(), std::move(meta), {}, std::move(alloc)) {}
 150
 151   /// Constructor used by algorithm::reduce to shrink and rebin (not for users).
 152   variable(const variable& src, index_type begin, index_type end, unsigned merge)
 153       : metadata_base(src), vec_(src.get_allocator()) {
 154     assert((end - begin) % merge == 0);
 155     if (options_type::test(option::circular) && !(begin == 0 && end == src.size()))
 156       BOOST_THROW_EXCEPTION(std::invalid_argument("cannot shrink circular axis"));
 157     vec_.reserve((end - begin) / merge);
 158     const auto beg = src.vec_.begin();
 159     for (index_type i = begin; i <= end; i += merge) vec_.emplace_back(*(beg + i));
 160   }
 161
 162   /// Return index for value argument.
 163   index_type index(value_type x) const noexcept {
 164     if (options_type::test(option::circular)) {
 165       const auto a = vec_[0];
 166       const auto b = vec_[size()];
 167       x -= std::floor((x - a) / (b - a)) * (b - a);
 168     }
 169     // upper edge of last bin is inclusive if overflow bin is not present
 170     if (!options_type::test(option::overflow) && x == vec_.back()) return size() - 1;
 171     return static_cast<index_type>(std::upper_bound(vec_.begin(), vec_.end(), x) -
 172                                    vec_.begin() - 1);
 173   }
 174
 175   std::pair<index_type, index_type> update(value_type x) noexcept {
 176     const auto i = index(x);
 177     if (std::isfinite(x)) {
 178       if (0 <= i) {
 179         if (i < size()) return std::make_pair(i, 0);
 180         const auto d = value(size()) - value(size() - 0.5);
 181         x = std::nextafter(x, (std::numeric_limits<value_type>::max)());
 182         x = (std::max)(x, vec_.back() + d);
 183         vec_.push_back(x);
 184         return {i, -1};
 185       }
 186       const auto d = value(0.5) - value(0);
 187       x = (std::min)(x, value(0) - d);
 188       vec_.insert(vec_.begin(), x);
 189       return {0, -i};
 190     }
 191     return {x < 0 ? -1 : size(), 0};
 192   }
 193
 194   /// Return value for fractional index argument.
 195   value_type value(real_index_type i) const noexcept {
 196     if (options_type::test(option::circular)) {
 197       auto shift = std::floor(i / size());
 198       i -= shift * size();
 199       double z;
 200       const auto k = static_cast<index_type>(std::modf(i, &z));
 201       const auto a = vec_[0];
 202       const auto b = vec_[size()];
 203       return (1.0 - z) * vec_[k] + z * vec_[k + 1] + shift * (b - a);
 204     }
 205     if (i < 0) return detail::lowest<value_type>();
 206     if (i == size()) return vec_.back();
 207     if (i > size()) return detail::highest<value_type>();
 208     const auto k = static_cast<index_type>(i); // precond: i >= 0
 209     const real_index_type z = i - k;
 210     // check z == 0 needed to avoid returning nan when vec_[k + 1] is infinity
 211     return (1.0 - z) * vec_[k] + (z == 0 ? 0 : z * vec_[k + 1]);
 212   }
 213
 214   /// Return bin for index argument.
 215   auto bin(index_type idx) const noexcept { return interval_view<variable>(*this, idx); }
 216
 217   /// Returns the number of bins, without over- or underflow.
 218   index_type size() const noexcept { return static_cast<index_type>(vec_.size()) - 1; }
 219
 220   /// Returns the options.
 221   static constexpr unsigned options() noexcept { return options_type::value; }
 222
 223   template <class V, class M, class O, class A>
 224   bool operator==(const variable<V, M, O, A>& o) const noexcept {
 225     const auto& a = vec_;
 226     const auto& b = o.vec_;
 227     return std::equal(a.begin(), a.end(), b.begin(), b.end()) &&
 228            detail::relaxed_equal{}(this->metadata(), o.metadata());
 229   }
 230
 231   template <class V, class M, class O, class A>
 232   bool operator!=(const variable<V, M, O, A>& o) const noexcept {
 233     return !operator==(o);
 234   }
 235
 236   /// Return allocator instance.
 237   auto get_allocator() const { return vec_.get_allocator(); }
 238
 239   template <class Archive>
 240   void serialize(Archive& ar, unsigned /* version */) {
 241     ar& make_nvp("seq", vec_);
 242     ar& make_nvp("meta", this->metadata());
 243   }
 244
 245 private:
 246   vector_type vec_;
 247
 248   template <class V, class M, class O, class A>
 249   friend class variable;
 250 };
 251
 252 #if __cpp_deduction_guides >= 201606
 253
 254 template <class T>
 255 variable(std::initializer_list<T>)
 256     -> variable<detail::convert_integer<T, double>, null_type>;
 257
 258 template <class T, class M>
 259 variable(std::initializer_list<T>, M)
 260     -> variable<detail::convert_integer<T, double>,
 261                 detail::replace_type<std::decay_t<M>, const char*, std::string>>;
 262
 263 template <class T, class M, unsigned B>
 264 variable(std::initializer_list<T>, M, const option::bitset<B>&)
 265     -> variable<detail::convert_integer<T, double>,
 266                 detail::replace_type<std::decay_t<M>, const char*, std::string>,
 267                 option::bitset<B>>;
 268
 269 template <class Iterable, class = detail::requires_iterable<Iterable>>
 270 variable(Iterable) -> variable<
 271     detail::convert_integer<
 272         std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
 273     null_type>;
 274
 275 template <class Iterable, class M>
 276 variable(Iterable, M) -> variable<
 277     detail::convert_integer<
 278         std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
 279     detail::replace_type<std::decay_t<M>, const char*, std::string>>;
 280
 281 template <class Iterable, class M, unsigned B>
 282 variable(Iterable, M, const option::bitset<B>&) -> variable<
 283     detail::convert_integer<
 284         std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
 285     detail::replace_type<std::decay_t<M>, const char*, std::string>, option::bitset<B>>;
 286
 287 #endif
 288
 289 } // namespace axis
 290 } // namespace histogram
 291 } // namespace boost
 292
 293 #endif