[ceph.git] / ceph / src / boost / boost / histogram / axis / variable.hpp

// Copyright 2015-2018 Hans Dembinski
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt
// or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_HISTOGRAM_AXIS_VARIABLE_HPP
#define BOOST_HISTOGRAM_AXIS_VARIABLE_HPP

#include <algorithm>
#include <boost/assert.hpp>
#include <boost/core/nvp.hpp>
#include <boost/histogram/axis/interval_view.hpp>
#include <boost/histogram/axis/iterator.hpp>
#include <boost/histogram/axis/metadata_base.hpp>
#include <boost/histogram/axis/option.hpp>
#include <boost/histogram/detail/convert_integer.hpp>
#include <boost/histogram/detail/detect.hpp>
#include <boost/histogram/detail/limits.hpp>
#include <boost/histogram/detail/replace_type.hpp>
#include <boost/histogram/fwd.hpp>
#include <boost/throw_exception.hpp>
#include <cmath>
#include <limits>
#include <memory>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

namespace boost {
namespace histogram {
namespace axis {

/**
  Axis for non-equidistant bins on the real line.

  Binning is a O(log(N)) operation. If speed matters and the problem domain
  allows it, prefer a regular axis, possibly with a transform.

  @tparam Value input value type, must be floating point.
  @tparam MetaData type to store meta data.
  @tparam Options see boost::histogram::axis::option (all values allowed).
  @tparam Allocator allocator to use for dynamic memory management.
 */
template <class Value, class MetaData, class Options, class Allocator>
class variable : public iterator_mixin<variable<Value, MetaData, Options, Allocator>>,
                 public metadata_base<MetaData> {
  // these must be private, so that they are not automatically inherited
  using value_type = Value;
  using metadata_type = typename metadata_base<MetaData>::metadata_type;
  using options_type =
      detail::replace_default<Options, decltype(option::underflow | option::overflow)>;
  using allocator_type = Allocator;
  using vector_type = std::vector<Value, allocator_type>;

  static_assert(
      std::is_floating_point<value_type>::value,
      "current version of variable axis requires floating point type; "
      "if you need a variable axis with an integral type, please submit an issue");

  static_assert(
      (!options_type::test(option::circular) && !options_type::test(option::growth)) ||
          (options_type::test(option::circular) ^ options_type::test(option::growth)),
      "circular and growth options are mutually exclusive");

public:
  constexpr variable() = default;
  explicit variable(allocator_type alloc) : vec_(alloc) {}

  /** Construct from iterator range of bin edges.
   *
   * \param begin begin of edge sequence.
   * \param end   end of edge sequence.
   * \param meta  description of the axis.
   * \param alloc allocator instance to use.
   */
  template <class It, class = detail::requires_iterator<It>>
  variable(It begin, It end, metadata_type meta = {}, allocator_type alloc = {})
      : metadata_base<MetaData>(std::move(meta)), vec_(std::move(alloc)) {
    if (std::distance(begin, end) < 2)
      BOOST_THROW_EXCEPTION(std::invalid_argument("bins > 0 required"));

    vec_.reserve(std::distance(begin, end));
    vec_.emplace_back(*begin++);
    bool strictly_ascending = true;
    while (begin != end) {
      if (*begin <= vec_.back()) strictly_ascending = false;
      vec_.emplace_back(*begin++);
    }
    if (!strictly_ascending)
      BOOST_THROW_EXCEPTION(
          std::invalid_argument("input sequence must be strictly ascending"));
  }

  /** Construct variable axis from iterable range of bin edges.
   *
   * \param iterable iterable range of bin edges.
   * \param meta     description of the axis.
   * \param alloc    allocator instance to use.
   */
  template <class U, class = detail::requires_iterable<U>>
  variable(const U& iterable, metadata_type meta = {}, allocator_type alloc = {})
      : variable(std::begin(iterable), std::end(iterable), std::move(meta),
                 std::move(alloc)) {}

  /** Construct variable axis from initializer list of bin edges.
   *
   * @param list  `std::initializer_list` of bin edges.
   * @param meta  description of the axis.
   * @param alloc allocator instance to use.
   */
  template <class U>
  variable(std::initializer_list<U> list, metadata_type meta = {},
           allocator_type alloc = {})
      : variable(list.begin(), list.end(), std::move(meta), std::move(alloc)) {}

  /// Constructor used by algorithm::reduce to shrink and rebin (not for users).
  variable(const variable& src, index_type begin, index_type end, unsigned merge)
      : metadata_base<MetaData>(src), vec_(src.get_allocator()) {
    BOOST_ASSERT((end - begin) % merge == 0);
    if (options_type::test(option::circular) && !(begin == 0 && end == src.size()))
      BOOST_THROW_EXCEPTION(std::invalid_argument("cannot shrink circular axis"));
    vec_.reserve((end - begin) / merge);
    const auto beg = src.vec_.begin();
    for (index_type i = begin; i <= end; i += merge) vec_.emplace_back(*(beg + i));
  }

  /// Return index for value argument.
  index_type index(value_type x) const noexcept {
    if (options_type::test(option::circular)) {
      const auto a = vec_[0];
      const auto b = vec_[size()];
      x -= std::floor((x - a) / (b - a)) * (b - a);
    }
    return static_cast<index_type>(std::upper_bound(vec_.begin(), vec_.end(), x) -
                                   vec_.begin() - 1);
  }

  std::pair<index_type, index_type> update(value_type x) noexcept {
    const auto i = index(x);
    if (std::isfinite(x)) {
      if (0 <= i) {
        if (i < size()) return std::make_pair(i, 0);
        const auto d = value(size()) - value(size() - 0.5);
        x = std::nextafter(x, (std::numeric_limits<value_type>::max)());
        x = (std::max)(x, vec_.back() + d);
        vec_.push_back(x);
        return {i, -1};
      }
      const auto d = value(0.5) - value(0);
      x = (std::min)(x, value(0) - d);
      vec_.insert(vec_.begin(), x);
      return {0, -i};
    }
    return {x < 0 ? -1 : size(), 0};
  }

  /// Return value for fractional index argument.
  value_type value(real_index_type i) const noexcept {
    if (options_type::test(option::circular)) {
      auto shift = std::floor(i / size());
      i -= shift * size();
      double z;
      const auto k = static_cast<index_type>(std::modf(i, &z));
      const auto a = vec_[0];
      const auto b = vec_[size()];
      return (1.0 - z) * vec_[k] + z * vec_[k + 1] + shift * (b - a);
    }
    if (i < 0) return detail::lowest<value_type>();
    if (i == size()) return vec_.back();
    if (i > size()) return detail::highest<value_type>();
    const auto k = static_cast<index_type>(i); // precond: i >= 0
    const real_index_type z = i - k;
    return (1.0 - z) * vec_[k] + z * vec_[k + 1];
  }

  /// Return bin for index argument.
  auto bin(index_type idx) const noexcept { return interval_view<variable>(*this, idx); }

  /// Returns the number of bins, without over- or underflow.
  index_type size() const noexcept { return static_cast<index_type>(vec_.size()) - 1; }

  /// Returns the options.
  static constexpr unsigned options() noexcept { return options_type::value; }

  template <class V, class M, class O, class A>
  bool operator==(const variable<V, M, O, A>& o) const noexcept {
    const auto& a = vec_;
    const auto& b = o.vec_;
    return std::equal(a.begin(), a.end(), b.begin(), b.end()) &&
           metadata_base<MetaData>::operator==(o);
  }

  template <class V, class M, class O, class A>
  bool operator!=(const variable<V, M, O, A>& o) const noexcept {
    return !operator==(o);
  }

  /// Return allocator instance.
  auto get_allocator() const { return vec_.get_allocator(); }

  template <class Archive>
  void serialize(Archive& ar, unsigned /* version */) {
    ar& make_nvp("seq", vec_);
    ar& make_nvp("meta", this->metadata());
  }

private:
  vector_type vec_;

  template <class V, class M, class O, class A>
  friend class variable;
};

#if __cpp_deduction_guides >= 201606

template <class T>
variable(std::initializer_list<T>)
    ->variable<detail::convert_integer<T, double>, null_type>;

template <class T, class M>
variable(std::initializer_list<T>, M)
    ->variable<detail::convert_integer<T, double>,
               detail::replace_type<std::decay_t<M>, const char*, std::string>>;

template <class Iterable, class = detail::requires_iterable<Iterable>>
variable(Iterable)
    ->variable<
        detail::convert_integer<
            std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
        null_type>;

template <class Iterable, class M>
variable(Iterable, M)
    ->variable<
        detail::convert_integer<
            std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
        detail::replace_type<std::decay_t<M>, const char*, std::string>>;

#endif

} // namespace axis
} // namespace histogram
} // namespace boost

#endif
Commit	Line	Data
92f5a8d4 TL	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/assert.hpp>
	12	#include <boost/core/nvp.hpp>
	13	#include <boost/histogram/axis/interval_view.hpp>
	14	#include <boost/histogram/axis/iterator.hpp>
	15	#include <boost/histogram/axis/metadata_base.hpp>
	16	#include <boost/histogram/axis/option.hpp>
	17	#include <boost/histogram/detail/convert_integer.hpp>
	18	#include <boost/histogram/detail/detect.hpp>
	19	#include <boost/histogram/detail/limits.hpp>
	20	#include <boost/histogram/detail/replace_type.hpp>
	21	#include <boost/histogram/fwd.hpp>
	22	#include <boost/throw_exception.hpp>
	23	#include <cmath>
	24	#include <limits>
	25	#include <memory>
	26	#include <stdexcept>
	27	#include <string>
	28	#include <type_traits>
	29	#include <utility>
	30	#include <vector>
	31
	32	namespace boost {
	33	namespace histogram {
	34	namespace axis {
	35
	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	@tparam Value input value type, must be floating point.
	43	@tparam MetaData type to store meta data.
	44	@tparam Options see boost::histogram::axis::option (all values allowed).
	45	@tparam Allocator allocator to use for dynamic memory management.
	46	*/
	47	template <class Value, class MetaData, class Options, class Allocator>
	48	class variable : public iterator_mixin<variable<Value, MetaData, Options, Allocator>>,
	49	public metadata_base<MetaData> {
f67539c2	50	// these must be private, so that they are not automatically inherited
92f5a8d4 TL	51	using value_type = Value;
	52	using metadata_type = typename metadata_base<MetaData>::metadata_type;
	53	using options_type =
	54	detail::replace_default<Options, decltype(option::underflow \| option::overflow)>;
	55	using allocator_type = Allocator;
	56	using vector_type = std::vector<Value, allocator_type>;
	57
	58	static_assert(
	59	std::is_floating_point<value_type>::value,
	60	"current version of variable axis requires floating point type; "
	61	"if you need a variable axis with an integral type, please submit an issue");
	62
	63	static_assert(
	64	(!options_type::test(option::circular) && !options_type::test(option::growth)) \|\|
	65	(options_type::test(option::circular) ^ options_type::test(option::growth)),
	66	"circular and growth options are mutually exclusive");
	67
	68	public:
	69	constexpr variable() = default;
	70	explicit variable(allocator_type alloc) : vec_(alloc) {}
	71
	72	/** Construct from iterator range of bin edges.
	73	*
	74	* \param begin begin of edge sequence.
	75	* \param end end of edge sequence.
	76	* \param meta description of the axis.
	77	* \param alloc allocator instance to use.
	78	*/
	79	template <class It, class = detail::requires_iterator<It>>
	80	variable(It begin, It end, metadata_type meta = {}, allocator_type alloc = {})
	81	: metadata_base<MetaData>(std::move(meta)), vec_(std::move(alloc)) {
	82	if (std::distance(begin, end) < 2)
	83	BOOST_THROW_EXCEPTION(std::invalid_argument("bins > 0 required"));
	84
	85	vec_.reserve(std::distance(begin, end));
	86	vec_.emplace_back(*begin++);
	87	bool strictly_ascending = true;
	88	while (begin != end) {
	89	if (*begin <= vec_.back()) strictly_ascending = false;
	90	vec_.emplace_back(*begin++);
	91	}
	92	if (!strictly_ascending)
	93	BOOST_THROW_EXCEPTION(
	94	std::invalid_argument("input sequence must be strictly ascending"));
	95	}
	96
	97	/** Construct variable axis from iterable range of bin edges.
	98	*
	99	* \param iterable iterable range of bin edges.
	100	* \param meta description of the axis.
	101	* \param alloc allocator instance to use.
	102	*/
	103	template <class U, class = detail::requires_iterable<U>>
	104	variable(const U& iterable, metadata_type meta = {}, allocator_type alloc = {})
	105	: variable(std::begin(iterable), std::end(iterable), std::move(meta),
	106	std::move(alloc)) {}
	107
	108	/** Construct variable axis from initializer list of bin edges.
	109	*
	110	* @param list `std::initializer_list` of bin edges.
	111	* @param meta description of the axis.
	112	* @param alloc allocator instance to use.
	113	*/
	114	template <class U>
115	variable(std::initializer_list<U> list, metadata_type meta = {},
116	allocator_type alloc = {})
117	: variable(list.begin(), list.end(), std::move(meta), std::move(alloc)) {}
118
119	/// Constructor used by algorithm::reduce to shrink and rebin (not for users).
120	variable(const variable& src, index_type begin, index_type end, unsigned merge)
121	: metadata_base<MetaData>(src), vec_(src.get_allocator()) {
122	BOOST_ASSERT((end - begin) % merge == 0);
123	if (options_type::test(option::circular) && !(begin == 0 && end == src.size()))
124	BOOST_THROW_EXCEPTION(std::invalid_argument("cannot shrink circular axis"));
125	vec_.reserve((end - begin) / merge);
126	const auto beg = src.vec_.begin();
127	for (index_type i = begin; i <= end; i += merge) vec_.emplace_back(*(beg + i));
128	}
129
130	/// Return index for value argument.
131	index_type index(value_type x) const noexcept {
132	if (options_type::test(option::circular)) {
133	const auto a = vec_[0];
134	const auto b = vec_[size()];
135	x -= std::floor((x - a) / (b - a)) * (b - a);
136	}
137	return static_cast<index_type>(std::upper_bound(vec_.begin(), vec_.end(), x) -
138	vec_.begin() - 1);
139	}
140
f67539c2	141	std::pair<index_type, index_type> update(value_type x) noexcept {
92f5a8d4 TL	142	const auto i = index(x);
	143	if (std::isfinite(x)) {
	144	if (0 <= i) {
	145	if (i < size()) return std::make_pair(i, 0);
	146	const auto d = value(size()) - value(size() - 0.5);
	147	x = std::nextafter(x, (std::numeric_limits<value_type>::max)());
	148	x = (std::max)(x, vec_.back() + d);
	149	vec_.push_back(x);
f67539c2	150	return {i, -1};
92f5a8d4 TL	151	}
	152	const auto d = value(0.5) - value(0);
	153	x = (std::min)(x, value(0) - d);
	154	vec_.insert(vec_.begin(), x);
f67539c2	155	return {0, -i};
92f5a8d4	156	}
f67539c2	157	return {x < 0 ? -1 : size(), 0};
92f5a8d4 TL	158	}
	159
	160	/// Return value for fractional index argument.
	161	value_type value(real_index_type i) const noexcept {
	162	if (options_type::test(option::circular)) {
	163	auto shift = std::floor(i / size());
	164	i -= shift * size();
	165	double z;
	166	const auto k = static_cast<index_type>(std::modf(i, &z));
	167	const auto a = vec_[0];
	168	const auto b = vec_[size()];
	169	return (1.0 - z) * vec_[k] + z * vec_[k + 1] + shift * (b - a);
	170	}
	171	if (i < 0) return detail::lowest<value_type>();
	172	if (i == size()) return vec_.back();
	173	if (i > size()) return detail::highest<value_type>();
	174	const auto k = static_cast<index_type>(i); // precond: i >= 0
	175	const real_index_type z = i - k;
	176	return (1.0 - z) * vec_[k] + z * vec_[k + 1];
	177	}
	178
	179	/// Return bin for index argument.
	180	auto bin(index_type idx) const noexcept { return interval_view<variable>(*this, idx); }
	181
	182	/// Returns the number of bins, without over- or underflow.
	183	index_type size() const noexcept { return static_cast<index_type>(vec_.size()) - 1; }
	184
	185	/// Returns the options.
	186	static constexpr unsigned options() noexcept { return options_type::value; }
	187
	188	template <class V, class M, class O, class A>
	189	bool operator==(const variable<V, M, O, A>& o) const noexcept {
	190	const auto& a = vec_;
	191	const auto& b = o.vec_;
	192	return std::equal(a.begin(), a.end(), b.begin(), b.end()) &&
	193	metadata_base<MetaData>::operator==(o);
	194	}
	195
	196	template <class V, class M, class O, class A>
	197	bool operator!=(const variable<V, M, O, A>& o) const noexcept {
	198	return !operator==(o);
	199	}
	200
	201	/// Return allocator instance.
	202	auto get_allocator() const { return vec_.get_allocator(); }
	203
	204	template <class Archive>
	205	void serialize(Archive& ar, unsigned /* version */) {
	206	ar& make_nvp("seq", vec_);
	207	ar& make_nvp("meta", this->metadata());
	208	}
	209
	210	private:
	211	vector_type vec_;
	212
	213	template <class V, class M, class O, class A>
	214	friend class variable;
	215	};
	216
	217	#if __cpp_deduction_guides >= 201606
	218
	219	template <class T>
	220	variable(std::initializer_list<T>)
	221	->variable<detail::convert_integer<T, double>, null_type>;
222
223	template <class T, class M>
224	variable(std::initializer_list<T>, M)
225	->variable<detail::convert_integer<T, double>,
226	detail::replace_type<std::decay_t<M>, const char*, std::string>>;
227
228	template <class Iterable, class = detail::requires_iterable<Iterable>>
229	variable(Iterable)
230	->variable<
231	detail::convert_integer<
232	std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
233	null_type>;
234
235	template <class Iterable, class M>
236	variable(Iterable, M)
237	->variable<
238	detail::convert_integer<
239	std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>,
240	detail::replace_type<std::decay_t<M>, const char*, std::string>>;
241
242	#endif
243
244	} // namespace axis
245	} // namespace histogram
246	} // namespace boost
247
248	#endif