diff options
Diffstat (limited to 'boost/histogram')
46 files changed, 3279 insertions, 1949 deletions
diff --git a/boost/histogram/accumulators.hpp b/boost/histogram/accumulators.hpp new file mode 100644 index 0000000000..b515c1de5c --- /dev/null +++ b/boost/histogram/accumulators.hpp @@ -0,0 +1,16 @@ +// Copyright 2019 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_ACCUMULATORS_HPP +#define BOOST_HISTOGRAM_ACCUMULATORS_HPP + +#include <boost/histogram/accumulators/mean.hpp> +#include <boost/histogram/accumulators/sum.hpp> +#include <boost/histogram/accumulators/thread_safe.hpp> +#include <boost/histogram/accumulators/weighted_mean.hpp> +#include <boost/histogram/accumulators/weighted_sum.hpp> + +#endif diff --git a/boost/histogram/accumulators/ostream.hpp b/boost/histogram/accumulators/ostream.hpp index b88c133ae3..76e102a562 100644 --- a/boost/histogram/accumulators/ostream.hpp +++ b/boost/histogram/accumulators/ostream.hpp @@ -10,39 +10,58 @@ #include <boost/histogram/fwd.hpp> #include <iosfwd> +/** + \file boost/histogram/accumulators/ostream.hpp + Simple streaming operators for the builtin accumulator types. + + The text representation is not guaranteed to be stable between versions of + Boost.Histogram. This header is only included by + [boost/histogram/ostream.hpp](histogram/reference.html#header.boost.histogram.ostream_hpp). + To you use your own, include your own implementation instead of this header and do not + include + [boost/histogram/ostream.hpp](histogram/reference.html#header.boost.histogram.ostream_hpp). + */ + #ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED namespace boost { namespace histogram { namespace accumulators { -template <typename CharT, typename Traits, typename W> +template <class CharT, class Traits, class W> std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const sum<W>& x) { os << "sum(" << x.large() << " + " << x.small() << ")"; return os; } -template <typename CharT, typename Traits, typename W> +template <class CharT, class Traits, class W> std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const weighted_sum<W>& x) { os << "weighted_sum(" << x.value() << ", " << x.variance() << ")"; return os; } -template <typename CharT, typename Traits, typename W> +template <class CharT, class Traits, class W> std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const mean<W>& x) { os << "mean(" << x.count() << ", " << x.value() << ", " << x.variance() << ")"; return os; } -template <typename CharT, typename Traits, typename W> +template <class CharT, class Traits, class W> std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const weighted_mean<W>& x) { os << "weighted_mean(" << x.sum_of_weights() << ", " << x.value() << ", " << x.variance() << ")"; return os; } + +template <class CharT, class Traits, class T> +std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, + const thread_safe<T>& x) { + os << x.load(); + return os; +} } // namespace accumulators } // namespace histogram } // namespace boost diff --git a/boost/histogram/accumulators/thread_safe.hpp b/boost/histogram/accumulators/thread_safe.hpp new file mode 100644 index 0000000000..699bd4b1e4 --- /dev/null +++ b/boost/histogram/accumulators/thread_safe.hpp @@ -0,0 +1,57 @@ +// Copyright 2019 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_ACCUMULATORS_THREAD_SAFE_HPP +#define BOOST_HISTOGRAM_ACCUMULATORS_THREAD_SAFE_HPP + +#include <atomic> +#include <boost/mp11/utility.hpp> +#include <type_traits> + +namespace boost { +namespace histogram { +namespace accumulators { + +/** Thread-safe adaptor for builtin integral and floating point numbers. + + This adaptor uses std::atomic to make concurrent increments and additions safe for the + stored value. + + On common computing platforms, the adapted integer has the same size and + alignment as underlying type. The atomicity is implemented with a special CPU + instruction. On exotic platforms the size of the adapted number may be larger and/or the + type may have different alignment, which means it cannot be tightly packed into arrays. + + @tparam T type to adapt, must be supported by std::atomic. + */ +template <class T> +class thread_safe : public std::atomic<T> { +public: + using super_t = std::atomic<T>; + + thread_safe() noexcept : super_t(static_cast<T>(0)) {} + // non-atomic copy and assign is allowed, because storage is locked in this case + thread_safe(const thread_safe& o) noexcept : super_t(o.load()) {} + thread_safe& operator=(const thread_safe& o) noexcept { + super_t::store(o.load()); + return *this; + } + + thread_safe(T arg) : super_t(arg) {} + thread_safe& operator=(T arg) { + super_t::store(arg); + return *this; + } + + void operator+=(T arg) { super_t::fetch_add(arg, std::memory_order_relaxed); } + void operator++() { operator+=(static_cast<T>(1)); } +}; + +} // namespace accumulators +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/algorithm/project.hpp b/boost/histogram/algorithm/project.hpp index be69fe87b6..6c0495c8d0 100644 --- a/boost/histogram/algorithm/project.hpp +++ b/boost/histogram/algorithm/project.hpp @@ -8,16 +8,20 @@ #define BOOST_HISTOGRAM_ALGORITHM_PROJECT_HPP #include <algorithm> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/axis/variant.hpp> +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/make_default.hpp> +#include <boost/histogram/detail/static_if.hpp> #include <boost/histogram/histogram.hpp> #include <boost/histogram/indexed.hpp> #include <boost/histogram/unsafe_access.hpp> -#include <boost/mp11/algorithm.hpp> #include <boost/mp11/list.hpp> #include <boost/mp11/set.hpp> +#include <boost/mp11/utility.hpp> #include <boost/throw_exception.hpp> #include <stdexcept> #include <type_traits> +#include <vector> namespace boost { namespace histogram { @@ -41,8 +45,7 @@ auto project(const histogram<A, S>& h, std::integral_constant<unsigned, N>, Ns.. return std::make_tuple(std::get<N>(old_axes), std::get<Ns::value>(old_axes)...); }, [&](const auto& old_axes) { - return detail::remove_cvref_t<decltype(old_axes)>( - {old_axes[N], old_axes[Ns::value]...}); + return std::decay_t<decltype(old_axes)>({old_axes[N], old_axes[Ns::value]...}); }, old_axes); @@ -50,7 +53,7 @@ auto project(const histogram<A, S>& h, std::integral_constant<unsigned, N>, Ns.. using A2 = decltype(axes); auto result = histogram<A2, S>(std::move(axes), detail::make_default(old_storage)); auto idx = detail::make_stack_buffer<int>(unsafe_access::axes(result)); - for (auto x : indexed(h, coverage::all)) { + for (auto&& x : indexed(h, coverage::all)) { auto i = idx.begin(); mp11::mp_for_each<LN>([&i, &x](auto J) { *i++ = x.index(J); }); result.at(idx) += *x; @@ -66,23 +69,24 @@ auto project(const histogram<A, S>& h, std::integral_constant<unsigned, N>, Ns.. */ template <class A, class S, class Iterable, class = detail::requires_iterable<Iterable>> auto project(const histogram<A, S>& h, const Iterable& c) { - static_assert(detail::is_sequence_of_any_axis<A>::value, - "this version of project requires histogram with non-static axes"); - + using namespace boost::mp11; const auto& old_axes = unsafe_access::axes(h); - auto axes = detail::make_default(old_axes); + + // axes is always std::vector<...>, even if A is tuple + auto axes = detail::make_empty_dynamic_axes(old_axes); axes.reserve(c.size()); auto seen = detail::make_stack_buffer<bool>(old_axes, false); for (auto d : c) { if (seen[d]) BOOST_THROW_EXCEPTION(std::invalid_argument("indices must be unique")); seen[d] = true; - axes.emplace_back(old_axes[d]); + axes.emplace_back(detail::axis_get(old_axes, d)); } const auto& old_storage = unsafe_access::storage(h); - auto result = histogram<A, S>(std::move(axes), detail::make_default(old_storage)); + auto result = + histogram<decltype(axes), S>(std::move(axes), detail::make_default(old_storage)); auto idx = detail::make_stack_buffer<int>(unsafe_access::axes(result)); - for (auto x : indexed(h, coverage::all)) { + for (auto&& x : indexed(h, coverage::all)) { auto i = idx.begin(); for (auto d : c) *i++ = x.index(d); result.at(idx) += *x; diff --git a/boost/histogram/algorithm/reduce.hpp b/boost/histogram/algorithm/reduce.hpp index 12db033785..ba71cb7246 100644 --- a/boost/histogram/algorithm/reduce.hpp +++ b/boost/histogram/algorithm/reduce.hpp @@ -1,4 +1,4 @@ -// Copyright 2018 Hans Dembinski +// Copyright 2018-2019 Hans Dembinski // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt @@ -8,43 +8,42 @@ #define BOOST_HISTOGRAM_ALGORITHM_REDUCE_HPP #include <boost/assert.hpp> +#include <boost/histogram/axis/traits.hpp> #include <boost/histogram/detail/axes.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/cat.hpp> +#include <boost/histogram/detail/make_default.hpp> +#include <boost/histogram/detail/static_if.hpp> +#include <boost/histogram/detail/type_name.hpp> #include <boost/histogram/fwd.hpp> #include <boost/histogram/indexed.hpp> #include <boost/histogram/unsafe_access.hpp> #include <boost/throw_exception.hpp> #include <cmath> -#include <limits> +#include <initializer_list> #include <stdexcept> -#include <type_traits> namespace boost { namespace histogram { -namespace algorithm { - -/** - Option type returned by the helper functions shrink_and_rebin(), shrink(), rebin(). - */ +namespace detail { struct reduce_option { -#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED unsigned iaxis = 0; - double lower, upper; + bool indices_set = false; + axis::index_type begin = 0, end = 0; + bool values_set = false; + double lower = 0.0, upper = 0.0; unsigned merge = 0; +}; +} // namespace detail - reduce_option() noexcept = default; +namespace algorithm { - reduce_option(unsigned i, double l, double u, unsigned m) - : iaxis(i), lower(l), upper(u), merge(m) { - if (lower == upper) - BOOST_THROW_EXCEPTION(std::invalid_argument("lower != upper required")); - if (merge == 0) BOOST_THROW_EXCEPTION(std::invalid_argument("merge > 0 required")); - } -#endif -}; +using reduce_option = detail::reduce_option; /** - Shrink and rebin option. + Shrink and rebin option to be used in reduce(). + + To shrink and rebin in one command. Equivalent to passing both the shrink() and the + rebin() option for the same axis to reduce. @param iaxis which axis to operate on. @param lower lowest bound that should be kept. @@ -52,90 +51,162 @@ struct reduce_option { whole interval is removed. @param merge how many adjacent bins to merge into one. */ -inline auto shrink_and_rebin(unsigned iaxis, double lower, double upper, unsigned merge) { - return reduce_option{iaxis, lower, upper, merge}; +inline reduce_option shrink_and_rebin(unsigned iaxis, double lower, double upper, + unsigned merge) { + if (lower == upper) + BOOST_THROW_EXCEPTION(std::invalid_argument("lower != upper required")); + if (merge == 0) BOOST_THROW_EXCEPTION(std::invalid_argument("merge > 0 required")); + return {iaxis, false, 0, 0, true, lower, upper, merge}; +} + +/** + Slice and rebin option to be used in reduce(). + + To slice and rebin in one command. Equivalent to passing both the slice() and the + rebin() option for the same axis to reduce. + + @param iaxis which axis to operate on. + @param begin first index that should be kept. + @param end one past the last index that should be kept. + @param merge how many adjacent bins to merge into one. + */ +inline reduce_option slice_and_rebin(unsigned iaxis, axis::index_type begin, + axis::index_type end, unsigned merge) { + if (!(begin < end)) + BOOST_THROW_EXCEPTION(std::invalid_argument("begin < end required")); + if (merge == 0) BOOST_THROW_EXCEPTION(std::invalid_argument("merge > 0 required")); + return {iaxis, true, begin, end, false, 0.0, 0.0, merge}; } /** - Shrink option. + Shrink option to be used in reduce(). @param iaxis which axis to operate on. @param lower lowest bound that should be kept. @param upper highest bound that should be kept. If upper is inside bin interval, the whole interval is removed. */ -inline auto shrink(unsigned iaxis, double lower, double upper) { - return reduce_option{iaxis, lower, upper, 1}; +inline reduce_option shrink(unsigned iaxis, double lower, double upper) { + return shrink_and_rebin(iaxis, lower, upper, 1); +} + +/** + Slice option to be used in reduce(). + + @param iaxis which axis to operate on. + @param begin first index that should be kept. + @param end one past the last index that should be kept. + */ +inline reduce_option slice(unsigned iaxis, axis::index_type begin, axis::index_type end) { + return slice_and_rebin(iaxis, begin, end, 1); } /** - Rebin option. + Rebin option to be used in reduce(). @param iaxis which axis to operate on. @param merge how many adjacent bins to merge into one. */ -inline auto rebin(unsigned iaxis, unsigned merge) { - return reduce_option{iaxis, std::numeric_limits<double>::quiet_NaN(), - std::numeric_limits<double>::quiet_NaN(), merge}; +inline reduce_option rebin(unsigned iaxis, unsigned merge) { + if (merge == 0) BOOST_THROW_EXCEPTION(std::invalid_argument("merge > 0 required")); + return reduce_option{iaxis, false, 0, 0, false, 0.0, 0.0, merge}; } /** - Convenience overload for single axis. + Shrink and rebin option to be used in reduce() (onvenience overload for + single axis). @param lower lowest bound that should be kept. @param upper highest bound that should be kept. If upper is inside bin interval, the whole interval is removed. @param merge how many adjacent bins to merge into one. */ -inline auto shrink_and_rebin(double lower, double upper, unsigned merge) { +inline reduce_option shrink_and_rebin(double lower, double upper, unsigned merge) { return shrink_and_rebin(0, lower, upper, merge); } /** - Convenience overload for single axis. + Slice and rebin option to be used in reduce() (convenience for 1D histograms). + + @param begin first index that should be kept. + @param end one past the last index that should be kept. + @param merge how many adjacent bins to merge into one. +*/ +inline reduce_option slice_and_rebin(axis::index_type begin, axis::index_type end, + unsigned merge) { + return slice_and_rebin(0, begin, end, merge); +} + +/** + Shrink option to be used in reduce() (convenience for 1D histograms). @param lower lowest bound that should be kept. @param upper highest bound that should be kept. If upper is inside bin interval, the whole interval is removed. */ -inline auto shrink(double lower, double upper) { return shrink(0, lower, upper); } +inline reduce_option shrink(double lower, double upper) { + return shrink(0, lower, upper); +} + +/** + Slice option to be used in reduce() (convenience for 1D histograms). + + @param begin first index that should be kept. + @param end one past the last index that should be kept. +*/ +inline reduce_option slice(axis::index_type begin, axis::index_type end) { + return slice(0, begin, end); +} /** - Convenience overload for single axis. + Rebin option to be used in reduce() (convenience for 1D histograms). @param merge how many adjacent bins to merge into one. */ -inline auto rebin(unsigned merge) { return rebin(0, merge); } +inline reduce_option rebin(unsigned merge) { return rebin(0, merge); } /** - Shrink and/or rebin axes of a histogram. + Shrink, slice, and/or rebin axes of a histogram. Returns the reduced copy of the histogram. + Shrinking only works with axes that accept double values. Some axis types do not support + the reduce operation, for example, the builtin category axis, which is not ordered. + Custom axis types must implement a special constructor (see concepts) to be reducible. + @param hist original histogram. - @param options iterable sequence of reduce_options, generated by shrink_and_rebin(), - shrink(), and rebin(). + @param options iterable sequence of reduce options, generated by shrink_and_rebin(), + slice_and_rebin(), shrink(), slice(), and rebin(). */ -#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED template <class Histogram, class Iterable, class = detail::requires_iterable<Iterable>> -#else -template <class Histogram, class Iterable> -#endif decltype(auto) reduce(const Histogram& hist, const Iterable& options) { const auto& old_axes = unsafe_access::axes(hist); - struct option_item : reduce_option { - int begin, end; - }; - - auto opts = detail::make_stack_buffer<option_item>(old_axes); - for (const auto& o : options) { - auto& oi = opts[o.iaxis]; - if (oi.merge > 0) // did we already set the option for this axis? - BOOST_THROW_EXCEPTION(std::invalid_argument("indices must be unique")); - oi.lower = o.lower; - oi.upper = o.upper; - oi.merge = o.merge; + auto opts = detail::make_stack_buffer<reduce_option>(old_axes); + for (const reduce_option& o_in : options) { + BOOST_ASSERT(o_in.merge > 0); + if (o_in.iaxis >= hist.rank()) + BOOST_THROW_EXCEPTION(std::invalid_argument("invalid axis index")); + reduce_option& o_out = opts[o_in.iaxis]; + if (o_out.merge > 0) { + // some option was already set for this axis, see if we can merge requests + if (o_in.merge > 1 && o_out.merge > 1) + BOOST_THROW_EXCEPTION(std::invalid_argument("conflicting merge requests")); + if ((o_in.indices_set || o_in.values_set) && + (o_out.indices_set || o_out.values_set)) + BOOST_THROW_EXCEPTION( + std::invalid_argument("conflicting slice or shrink requests")); + } + if (o_in.values_set) { + o_out.values_set = true; + o_out.lower = o_in.lower; + o_out.upper = o_in.upper; + } else if (o_in.indices_set) { + o_out.indices_set = true; + o_out.begin = o_in.begin; + o_out.end = o_in.end; + } + o_out.merge = std::max(o_in.merge, o_out.merge); } // make new axes container with default-constructed axis instances @@ -144,33 +215,52 @@ decltype(auto) reduce(const Histogram& hist, const Iterable& options) { [](auto&, const auto&) {}, [](auto& axes, const auto& old_axes) { axes.reserve(old_axes.size()); - for (const auto& a : old_axes) axes.emplace_back(detail::make_default(a)); + detail::for_each_axis(old_axes, [&axes](const auto& a) { + axes.emplace_back(detail::make_default(a)); + }); }, axes, old_axes); // override default-constructed axis instances with modified instances unsigned iaxis = 0; hist.for_each_axis([&](const auto& a) { - using T = detail::remove_cvref_t<decltype(a)>; - + using A = std::decay_t<decltype(a)>; auto& o = opts[iaxis]; - o.begin = 0; - o.end = a.size(); if (o.merge > 0) { // option is set? - if (o.lower < o.upper) { - while (o.begin != o.end && a.value(o.begin) < o.lower) ++o.begin; - while (o.end != o.begin && a.value(o.end - 1) >= o.upper) --o.end; - } else if (o.lower > o.upper) { - // for inverted axis::regular - while (o.begin != o.end && a.value(o.begin) > o.lower) ++o.begin; - while (o.end != o.begin && a.value(o.end - 1) <= o.upper) --o.end; - } - o.end -= (o.end - o.begin) % o.merge; - auto a2 = T(a, o.begin, o.end, o.merge); - axis::get<T>(detail::axis_get(axes, iaxis)) = a2; + detail::static_if_c<axis::traits::is_reducible<A>::value>( + [&o](auto&& aout, const auto& ain) { + using A = std::decay_t<decltype(ain)>; + if (o.indices_set) { + o.begin = std::max(0, o.begin); + o.end = std::min(o.end, ain.size()); + } else { + o.begin = 0; + o.end = ain.size(); + if (o.values_set) { + if (o.lower < o.upper) { + while (o.begin != o.end && ain.value(o.begin) < o.lower) ++o.begin; + while (o.end != o.begin && ain.value(o.end - 1) >= o.upper) --o.end; + } else if (o.lower > o.upper) { + // for inverted axis::regular + while (o.begin != o.end && ain.value(o.begin) > o.lower) ++o.begin; + while (o.end != o.begin && ain.value(o.end - 1) <= o.upper) --o.end; + } + } + } + o.end -= (o.end - o.begin) % o.merge; + aout = A(ain, o.begin, o.end, o.merge); + }, + [](auto&&, const auto& ain) { + using A = std::decay_t<decltype(ain)>; + BOOST_THROW_EXCEPTION(std::invalid_argument( + detail::cat(detail::type_name<A>(), " is not reducible"))); + }, + axis::get<A>(detail::axis_get(axes, iaxis)), a); } else { o.merge = 1; - axis::get<T>(detail::axis_get(axes, iaxis)) = a; + o.begin = 0; + o.end = a.size(); + axis::get<A>(detail::axis_get(axes, iaxis)) = a; } ++iaxis; }); @@ -179,7 +269,7 @@ decltype(auto) reduce(const Histogram& hist, const Iterable& options) { auto result = Histogram(std::move(axes), std::move(storage)); auto idx = detail::make_stack_buffer<int>(unsafe_access::axes(result)); - for (auto x : indexed(hist, coverage::all)) { + for (auto&& x : indexed(hist, coverage::all)) { auto i = idx.begin(); auto o = opts.begin(); for (auto j : x.indices()) { @@ -201,16 +291,21 @@ decltype(auto) reduce(const Histogram& hist, const Iterable& options) { } /** - Shrink and/or rebin axes of a histogram. + Shrink, slice, and/or rebin axes of a histogram. + + Returns the reduced copy of the histogram. - Returns the modified copy. + Shrinking only works with axes that accept double values. Some axis types do not support + the reduce operation, for example, the builtin category axis, which is not ordered. + Custom axis types must implement a special constructor (see concepts) to be reducible. @param hist original histogram. @param opt reduce option generated by shrink_and_rebin(), shrink(), and rebin(). - @param opts more reduce_options. + @param opts more reduce options. */ template <class Histogram, class... Ts> -decltype(auto) reduce(const Histogram& hist, const reduce_option& opt, Ts&&... opts) { +decltype(auto) reduce(const Histogram& hist, const reduce_option& opt, + const Ts&... opts) { // this must be in one line, because any of the ts could be a temporary return reduce(hist, std::initializer_list<reduce_option>{opt, opts...}); } diff --git a/boost/histogram/algorithm/sum.hpp b/boost/histogram/algorithm/sum.hpp index 63316adef3..5ff437dd6f 100644 --- a/boost/histogram/algorithm/sum.hpp +++ b/boost/histogram/algorithm/sum.hpp @@ -30,7 +30,7 @@ auto sum(const histogram<A, S>& h) { using T = typename histogram<A, S>::value_type; using Sum = mp11::mp_if<std::is_arithmetic<T>, accumulators::sum<double>, T>; Sum sum; - for (auto x : h) sum += x; + for (auto&& x : h) sum += x; using R = mp11::mp_if<std::is_arithmetic<T>, double, T>; return static_cast<R>(sum); } diff --git a/boost/histogram/axis/category.hpp b/boost/histogram/axis/category.hpp index 03a3b842ea..309aae0d6b 100644 --- a/boost/histogram/axis/category.hpp +++ b/boost/histogram/axis/category.hpp @@ -11,10 +11,13 @@ #include <boost/histogram/axis/iterator.hpp> #include <boost/histogram/axis/option.hpp> #include <boost/histogram/detail/compressed_pair.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/relaxed_equal.hpp> +#include <boost/histogram/detail/replace_default.hpp> #include <boost/histogram/fwd.hpp> #include <boost/throw_exception.hpp> #include <stdexcept> +#include <string> #include <type_traits> #include <utility> #include <vector> @@ -56,6 +59,22 @@ class category : public iterator_mixin<category<Value, MetaData, Options, Alloca public: explicit category(allocator_type alloc = {}) : vec_meta_(vector_type(alloc)) {} + category(const category&) = default; + category& operator=(const category&) = default; + category(category&& o) noexcept : vec_meta_(std::move(o.vec_meta_)) { + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_constructible<metadata_type>::value, + ""); + } + category& operator=(category&& o) noexcept { + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_assignable<metadata_type>::value, + ""); + vec_meta_ = std::move(o.vec_meta_); + return *this; + } /** Construct from iterator range of unique values. * @@ -92,14 +111,6 @@ public: allocator_type alloc = {}) : category(list.begin(), list.end(), std::move(meta), std::move(alloc)) {} - /// Constructor used by algorithm::reduce to shrink and rebin. - category(const category& src, index_type begin, index_type end, unsigned merge) - : category(src.vec_meta_.first().begin() + begin, - src.vec_meta_.first().begin() + end, src.metadata()) { - if (merge > 1) - BOOST_THROW_EXCEPTION(std::invalid_argument("cannot merge bins for category axis")); - } - /// Return index for value argument. index_type index(const value_type& x) const noexcept { const auto beg = vec_meta_.first().begin(); diff --git a/boost/histogram/axis/integer.hpp b/boost/histogram/axis/integer.hpp index 6e55d83354..8768b0fbfa 100644 --- a/boost/histogram/axis/integer.hpp +++ b/boost/histogram/axis/integer.hpp @@ -10,12 +10,17 @@ #include <boost/histogram/axis/iterator.hpp> #include <boost/histogram/axis/option.hpp> #include <boost/histogram/detail/compressed_pair.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/convert_integer.hpp> +#include <boost/histogram/detail/limits.hpp> +#include <boost/histogram/detail/relaxed_equal.hpp> +#include <boost/histogram/detail/replace_default.hpp> +#include <boost/histogram/detail/static_if.hpp> #include <boost/histogram/fwd.hpp> #include <boost/throw_exception.hpp> #include <cmath> #include <limits> #include <stdexcept> +#include <string> #include <type_traits> #include <utility> @@ -52,6 +57,23 @@ class integer : public iterator_mixin<integer<Value, MetaData, Options>> { public: constexpr integer() = default; + integer(const integer&) = default; + integer& operator=(const integer&) = default; + integer(integer&& o) noexcept : size_meta_(std::move(o.size_meta_)), min_(o.min_) { + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_constructible<metadata_type>::value, + ""); + } + integer& operator=(integer&& o) noexcept { + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_assignable<metadata_type>::value, + ""); + size_meta_ = std::move(o.size_meta_); + min_ = o.min_; + return *this; + } /** Construct over semi-open integer interval [start, stop). * diff --git a/boost/histogram/axis/iterator.hpp b/boost/histogram/axis/iterator.hpp index 29b8ee0091..8b8c15e392 100644 --- a/boost/histogram/axis/iterator.hpp +++ b/boost/histogram/axis/iterator.hpp @@ -8,34 +8,25 @@ #define BOOST_HISTOGRAM_AXIS_ITERATOR_HPP #include <boost/histogram/axis/interval_view.hpp> -#include <boost/histogram/detail/meta.hpp> -#include <boost/iterator/iterator_adaptor.hpp> -#include <boost/iterator/reverse_iterator.hpp> +#include <boost/histogram/detail/iterator_adaptor.hpp> +#include <iterator> namespace boost { namespace histogram { namespace axis { -template <typename Axis> -class iterator - : public boost::iterator_adaptor<iterator<Axis>, int, - decltype(std::declval<const Axis&>().bin(0)), - std::random_access_iterator_tag, - decltype(std::declval<const Axis&>().bin(0)), int> { +template <class Axis> +class iterator : public detail::iterator_adaptor<iterator<Axis>, int, + decltype(std::declval<Axis>().bin(0))> { public: - explicit iterator(const Axis& axis, int idx) - : iterator::iterator_adaptor_(idx), axis_(axis) {} + /// Make iterator from axis and index. + iterator(const Axis& axis, int idx) : iterator::iterator_adaptor_(idx), axis_(axis) {} -protected: - bool equal(const iterator& other) const noexcept { - return &axis_ == &other.axis_ && this->base() == other.base(); - } - - decltype(auto) dereference() const { return axis_.bin(this->base()); } + /// Return current bin object. + decltype(auto) operator*() const { return axis_.bin(this->base()); } private: const Axis& axis_; - friend class boost::iterator_core_access; }; /// Uses CRTP to inject iterator logic into Derived. @@ -43,7 +34,7 @@ template <typename Derived> class iterator_mixin { public: using const_iterator = iterator<Derived>; - using const_reverse_iterator = boost::reverse_iterator<const_iterator>; + using const_reverse_iterator = std::reverse_iterator<const_iterator>; /// Bin iterator to beginning of the axis (read-only). const_iterator begin() const noexcept { @@ -58,12 +49,12 @@ public: /// Reverse bin iterator to the last entry of the axis (read-only). const_reverse_iterator rbegin() const noexcept { - return boost::make_reverse_iterator(end()); + return std::make_reverse_iterator(end()); } /// Reverse bin iterator to the end (read-only). const_reverse_iterator rend() const noexcept { - return boost::make_reverse_iterator(begin()); + return std::make_reverse_iterator(begin()); } }; diff --git a/boost/histogram/axis/ostream.hpp b/boost/histogram/axis/ostream.hpp index 282e7496c3..5a7295ade2 100644 --- a/boost/histogram/axis/ostream.hpp +++ b/boost/histogram/axis/ostream.hpp @@ -10,10 +10,10 @@ #define BOOST_HISTOGRAM_AXIS_OSTREAM_HPP #include <boost/assert.hpp> -#include <boost/core/typeinfo.hpp> #include <boost/histogram/axis/regular.hpp> #include <boost/histogram/detail/cat.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/static_if.hpp> +#include <boost/histogram/detail/type_name.hpp> #include <boost/histogram/fwd.hpp> #include <boost/throw_exception.hpp> #include <iomanip> @@ -21,6 +21,18 @@ #include <stdexcept> #include <type_traits> +/** + \file boost/histogram/axis/ostream.hpp + Simple streaming operators for the builtin axis types. + + The text representation is not guaranteed to be stable between versions of + Boost.Histogram. This header is only included by + [boost/histogram/ostream.hpp](histogram/reference.html#header.boost.histogram.ostream_hpp). + To you use your own, include your own implementation instead of this header and do not + include + [boost/histogram/ostream.hpp](histogram/reference.html#header.boost.histogram.ostream_hpp). + */ + #ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED namespace boost { @@ -40,10 +52,7 @@ void stream_metadata(OStream& os, const T& t) { oss << t; if (!oss.str().empty()) { os << ", metadata=" << std::quoted(oss.str()); } }, - [&os](const auto&) { - os << ", metadata=" << boost::core::demangled_name(BOOST_CORE_TYPEID(T)); - }, - t); + [&os](const auto&) { os << ", metadata=" << detail::type_name<T>(); }, t); } template <class OStream> @@ -170,13 +179,12 @@ std::basic_ostream<Ts...>& operator<<(std::basic_ostream<Ts...>& os, const variant<Us...>& v) { visit( [&os](const auto& x) { - using A = detail::remove_cvref_t<decltype(x)>; + using A = std::decay_t<decltype(x)>; detail::static_if<detail::is_streamable<A>>( [&os](const auto& x) { os << x; }, [](const auto&) { BOOST_THROW_EXCEPTION(std::runtime_error( - detail::cat(boost::core::demangled_name(BOOST_CORE_TYPEID(A)), - " is not streamable"))); + detail::cat(detail::type_name<A>(), " is not streamable"))); }, x); }, diff --git a/boost/histogram/axis/polymorphic_bin.hpp b/boost/histogram/axis/polymorphic_bin.hpp index 1b70938e4c..773fcf1cdc 100644 --- a/boost/histogram/axis/polymorphic_bin.hpp +++ b/boost/histogram/axis/polymorphic_bin.hpp @@ -7,7 +7,7 @@ #ifndef BOOST_HISTOGRAM_AXIS_POLYMORPHIC_BIN_HPP #define BOOST_HISTOGRAM_AXIS_POLYMORPHIC_BIN_HPP -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/detect.hpp> #include <type_traits> namespace boost { @@ -15,20 +15,21 @@ namespace histogram { namespace axis { /** - Holds the bin data of a axis::variant. + Holds the bin data of an axis::variant. - The interface is a superset of the `value_bin_view` and `interval_bin_view` - classes. The methods value() and lower() return the same number. For a value bin, - upper() and lower() and center() return the same number, width() returns zero. + The interface is a superset of the axis::interval_view + class. In addition, the object is implicitly convertible to the value type, + returning the equivalent of a call to lower(). For discrete axes, lower() == + upper(), and width() returns zero. - This is not a view like interval_bin_view or value_bin_view for two reasons. + This is not a view like axis::interval_view for two reasons. - Sequential calls to lower() and upper() would have to each loop through the variant types. This is likely to be slower than filling all the data in one loop. - polymorphic_bin may be created from a temporary instance of axis::variant, like in the call histogram::axis(0). Storing a reference to the axis would result in a dangling reference. Rather than specialing the code to handle - this, it seems easier to just use a value instead of a view here. + this, it seems easier to just use a value instead of a view. */ template <typename RealType> class polymorphic_bin { diff --git a/boost/histogram/axis/regular.hpp b/boost/histogram/axis/regular.hpp index 6f6b2605a0..a7b9828ec0 100644 --- a/boost/histogram/axis/regular.hpp +++ b/boost/histogram/axis/regular.hpp @@ -12,18 +12,54 @@ #include <boost/histogram/axis/iterator.hpp> #include <boost/histogram/axis/option.hpp> #include <boost/histogram/detail/compressed_pair.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/convert_integer.hpp> +#include <boost/histogram/detail/relaxed_equal.hpp> +#include <boost/histogram/detail/replace_default.hpp> #include <boost/histogram/fwd.hpp> #include <boost/mp11/utility.hpp> #include <boost/throw_exception.hpp> #include <cmath> #include <limits> #include <stdexcept> +#include <string> #include <type_traits> #include <utility> namespace boost { namespace histogram { +namespace detail { + +template <class T> +using get_scale_type_helper = typename T::value_type; + +template <class T> +using get_scale_type = mp11::mp_eval_or<T, detail::get_scale_type_helper, T>; + +struct one_unit {}; + +template <class T> +T operator*(T&& t, const one_unit&) { + return std::forward<T>(t); +} + +template <class T> +T operator/(T&& t, const one_unit&) { + return std::forward<T>(t); +} + +template <class T> +using get_unit_type_helper = typename T::unit_type; + +template <class T> +using get_unit_type = mp11::mp_eval_or<one_unit, detail::get_unit_type_helper, T>; + +template <class T, class R = get_scale_type<T>> +R get_scale(const T& t) { + return t / get_unit_type<T>(); +} + +} // namespace detail + namespace axis { namespace transform { @@ -140,6 +176,31 @@ class regular : public iterator_mixin<regular<Value, Transform, MetaData, Option public: constexpr regular() = default; + regular(const regular&) = default; + regular& operator=(const regular&) = default; + regular(regular&& o) noexcept + : transform_type(std::move(o)) + , size_meta_(std::move(o.size_meta_)) + , min_(o.min_) + , delta_(o.delta_) { + static_assert(std::is_nothrow_move_constructible<transform_type>::value, ""); + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_constructible<metadata_type>::value, + ""); + } + regular& operator=(regular&& o) noexcept { + static_assert(std::is_nothrow_move_assignable<transform_type>::value, ""); + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_assignable<metadata_type>::value, + ""); + transform_type::operator=(std::move(o)); + size_meta_ = std::move(o.size_meta_); + min_ = o.min_; + delta_ = o.delta_; + return *this; + } /** Construct n bins over real transformed range [start, stop). * @@ -347,10 +408,15 @@ regular(Tr, unsigned, T, T, M)->regular<detail::convert_integer<T, double>, Tr, #endif +/// Regular axis with circular option already set. template <class Value = double, class MetaData = use_default, class Options = use_default> +#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED using circular = regular<Value, transform::id, MetaData, decltype(detail::replace_default<Options, option::overflow_t>{} | option::circular)>; +#else +class circular; +#endif } // namespace axis } // namespace histogram diff --git a/boost/histogram/axis/traits.hpp b/boost/histogram/axis/traits.hpp index 48e3dbf135..d907d6dd54 100644 --- a/boost/histogram/axis/traits.hpp +++ b/boost/histogram/axis/traits.hpp @@ -7,12 +7,19 @@ #ifndef BOOST_HISTOGRAM_AXIS_TRAITS_HPP #define BOOST_HISTOGRAM_AXIS_TRAITS_HPP -#include <boost/core/typeinfo.hpp> #include <boost/histogram/axis/option.hpp> +#include <boost/histogram/detail/args_type.hpp> #include <boost/histogram/detail/cat.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/static_if.hpp> +#include <boost/histogram/detail/try_cast.hpp> +#include <boost/histogram/detail/type_name.hpp> #include <boost/histogram/fwd.hpp> +#include <boost/mp11/algorithm.hpp> +#include <boost/mp11/list.hpp> +#include <boost/mp11/utility.hpp> #include <boost/throw_exception.hpp> +#include <boost/variant2/variant.hpp> #include <stdexcept> #include <utility> @@ -23,45 +30,68 @@ namespace detail { template <class T> using static_options_impl = axis::option::bitset<T::options()>; -template <class FIntArg, class FDoubleArg, class T> -decltype(auto) value_method_switch(FIntArg&& iarg, FDoubleArg&& darg, const T& t) { - return static_if<has_method_value<T>>( - [](FIntArg&& iarg, FDoubleArg&& darg, const auto& t) { - using A = remove_cvref_t<decltype(t)>; - return static_if<std::is_same<arg_type<decltype(&A::value), 0>, int>>( - std::forward<FIntArg>(iarg), std::forward<FDoubleArg>(darg), t); - }, - [](FIntArg&&, FDoubleArg&&, const auto& t) -> double { - using A = remove_cvref_t<decltype(t)>; - BOOST_THROW_EXCEPTION(std::runtime_error(detail::cat( - boost::core::demangled_name(BOOST_CORE_TYPEID(A)), " has no value method"))); -#ifndef _MSC_VER // msvc warns about unreachable return - return double{}; -#endif - }, - std::forward<FIntArg>(iarg), std::forward<FDoubleArg>(darg), t); +template <class I, class D, class A> +double value_method_switch_impl1(std::false_type, I&&, D&&, const A&) { + // comma trick to make all compilers happy; some would complain about + // unreachable code after the throw, others about a missing return + return BOOST_THROW_EXCEPTION( + std::runtime_error(cat(type_name<A>(), " has no value method"))), + double{}; } -template <class R1, class R2, class FIntArg, class FDoubleArg, class T> -R2 value_method_switch_with_return_type(FIntArg&& iarg, FDoubleArg&& darg, const T& t) { - return static_if<has_method_value_with_convertible_return_type<T, R1>>( - [](FIntArg&& iarg, FDoubleArg&& darg, const auto& t) -> R2 { - using A = remove_cvref_t<decltype(t)>; - return static_if<std::is_same<arg_type<decltype(&A::value), 0>, int>>( - std::forward<FIntArg>(iarg), std::forward<FDoubleArg>(darg), t); - }, - [](FIntArg&&, FDoubleArg&&, const auto&) -> R2 { - BOOST_THROW_EXCEPTION(std::runtime_error( - detail::cat(boost::core::demangled_name(BOOST_CORE_TYPEID(T)), - " has no value method or return type is not convertible to ", - boost::core::demangled_name(BOOST_CORE_TYPEID(R1))))); -#ifndef _MSC_VER // msvc warns about unreachable return - // conjure a value out of thin air to satisfy syntactic requirement - return *reinterpret_cast<R2*>(0); -#endif - }, - std::forward<FIntArg>(iarg), std::forward<FDoubleArg>(darg), t); +template <class I, class D, class A> +decltype(auto) value_method_switch_impl1(std::true_type, I&& i, D&& d, const A& a) { + using T = arg_type<decltype(&A::value)>; + return static_if<std::is_same<T, axis::index_type>>(std::forward<I>(i), + std::forward<D>(d), a); +} + +template <class I, class D, class A> +decltype(auto) value_method_switch(I&& i, D&& d, const A& a) { + return value_method_switch_impl1(has_method_value<A>{}, std::forward<I>(i), + std::forward<D>(d), a); } + +static axis::null_type null_value; + +struct variant_access { + template <class T, class T0, class Variant> + static auto get_if_impl(mp11::mp_list<T, T0>, Variant* v) noexcept { + return variant2::get_if<T>(&(v->impl)); + } + + template <class T, class T0, class Variant> + static auto get_if_impl(mp11::mp_list<T, T0*>, Variant* v) noexcept { + auto tp = variant2::get_if<mp11::mp_if<std::is_const<T0>, const T*, T*>>(&(v->impl)); + return tp ? *tp : nullptr; + } + + template <class T, class Variant> + static auto get_if(Variant* v) noexcept { + using T0 = mp11::mp_first<std::decay_t<Variant>>; + return get_if_impl(mp11::mp_list<T, T0>{}, v); + } + + template <class T0, class Visitor, class Variant> + static decltype(auto) visit_impl(mp11::mp_identity<T0>, Visitor&& vis, Variant&& v) { + return variant2::visit(std::forward<Visitor>(vis), v.impl); + } + + template <class T0, class Visitor, class Variant> + static decltype(auto) visit_impl(mp11::mp_identity<T0*>, Visitor&& vis, Variant&& v) { + return variant2::visit( + [&vis](auto&& x) -> decltype(auto) { return std::forward<Visitor>(vis)(*x); }, + v.impl); + } + + template <class Visitor, class Variant> + static decltype(auto) visit(Visitor&& vis, Variant&& v) { + using T0 = mp11::mp_first<std::decay_t<Variant>>; + return visit_impl(mp11::mp_identity<T0>{}, std::forward<Visitor>(vis), + std::forward<Variant>(v)); + } +}; + } // namespace detail namespace axis { @@ -77,32 +107,35 @@ namespace traits { */ template <class Axis> decltype(auto) metadata(Axis&& axis) noexcept { - return detail::static_if< - detail::has_method_metadata<const detail::remove_cvref_t<Axis>>>( + return detail::static_if<detail::has_method_metadata<std::decay_t<Axis>>>( [](auto&& a) -> decltype(auto) { return a.metadata(); }, - [](auto &&) -> detail::copy_qualifiers<Axis, null_type> { - static null_type m; - return m; + [](auto &&) -> mp11::mp_if<std::is_const<std::remove_reference_t<Axis>>, + axis::null_type const&, axis::null_type&> { + return detail::null_value; }, std::forward<Axis>(axis)); } -/** Generates static axis option type for axis type. +/** Get static axis options for axis type. - WARNING: Doxygen does not render the synopsis correctly. This is a templated using - directive, which accepts axis type and returns boost::histogram::axis::option::bitset. + Doxygen does not render this well. This is a meta-function, it accepts an axis + type and represents its boost::histogram::axis::option::bitset. - If Axis::options() is valid and constexpr, return the corresponding option type. - Otherwise, return boost::histogram::axis::option::growth_t, if the axis has a method - `update`, else return boost::histogram::axis::option::none_t. + If Axis::options() is valid and constexpr, static_options is the corresponding + option type. Otherwise, it is boost::histogram::axis::option::growth_t, if the + axis has a method `update`, else boost::histogram::axis::option::none_t. @tparam Axis axis type */ template <class Axis> -using static_options = detail::mp_eval_or< - mp11::mp_if<detail::has_method_update<detail::remove_cvref_t<Axis>>, option::growth_t, - option::none_t>, - detail::static_options_impl, detail::remove_cvref_t<Axis>>; +#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED +using static_options = + mp11::mp_eval_or<mp11::mp_if<detail::has_method_update<std::decay_t<Axis>>, + option::growth_t, option::none_t>, + detail::static_options_impl, std::decay_t<Axis>>; +#else +struct static_options; +#endif /** Returns axis options as unsigned integer. @@ -113,7 +146,7 @@ using static_options = detail::mp_eval_or< */ template <class Axis> constexpr unsigned options(const Axis& axis) noexcept { - // cannot reuse static_options here, because this should also work for axis::variant + // cannot reuse static_options here, must also work for axis::variant return detail::static_if<detail::has_method_options<Axis>>( [](const auto& a) { return a.options(); }, [](const auto&) { return static_options<Axis>::value; }, axis); @@ -143,7 +176,7 @@ constexpr index_type extent(const Axis& axis) noexcept { template <class Axis> decltype(auto) value(const Axis& axis, real_index_type index) { return detail::value_method_switch( - [index](const auto& a) { return a.value(static_cast<int>(index)); }, + [index](const auto& a) { return a.value(static_cast<index_type>(index)); }, [index](const auto& a) { return a.value(index); }, axis); } @@ -159,11 +192,8 @@ decltype(auto) value(const Axis& axis, real_index_type index) { */ template <class Result, class Axis> Result value_as(const Axis& axis, real_index_type index) { - return detail::value_method_switch_with_return_type<Result, Result>( - [index](const auto& a) { - return static_cast<Result>(a.value(static_cast<int>(index))); - }, - [index](const auto& a) { return static_cast<Result>(a.value(index)); }, axis); + return detail::try_cast<Result, std::runtime_error>( + value(axis, index)); // avoid conversion warning } /** Returns axis index for value. @@ -173,31 +203,16 @@ Result value_as(const Axis& axis, real_index_type index) { @param axis any axis instance @param value argument to be passed to `index` method */ -template <class Axis, class U> -auto index(const Axis& axis, const U& value) { - using V = detail::arg_type<decltype(&Axis::index)>; - return detail::static_if<std::is_convertible<U, V>>( - [&value](const auto& axis) { - using A = detail::remove_cvref_t<decltype(axis)>; - using V2 = detail::arg_type<decltype(&A::index)>; - return axis.index(static_cast<V2>(value)); - }, - [](const Axis&) -> index_type { - BOOST_THROW_EXCEPTION(std::invalid_argument( - detail::cat(boost::core::demangled_name(BOOST_CORE_TYPEID(Axis)), - ": cannot convert argument of type ", - boost::core::demangled_name(BOOST_CORE_TYPEID(U)), " to ", - boost::core::demangled_name(BOOST_CORE_TYPEID(V))))); -#ifndef _MSC_VER // msvc warns about unreachable return - return index_type{}; -#endif - }, - axis); +template <class Axis, class U, + class _V = std::decay_t<detail::arg_type<decltype(&Axis::index)>>> +axis::index_type index(const Axis& axis, + const U& value) noexcept(std::is_convertible<U, _V>::value) { + return axis.index(detail::try_cast<_V, std::invalid_argument>(value)); } -/// @copydoc index(const Axis&, const U& value) +// specialization for variant template <class... Ts, class U> -auto index(const variant<Ts...>& axis, const U& value) { +axis::index_type index(const variant<Ts...>& axis, const U& value) { return axis.index(value); } @@ -212,33 +227,21 @@ auto index(const variant<Ts...>& axis, const U& value) { @param axis any axis instance @param value argument to be passed to `update` or `index` method */ -template <class Axis, class U> -std::pair<int, int> update(Axis& axis, const U& value) { - using V = detail::arg_type<decltype(&Axis::index)>; - return detail::static_if<std::is_convertible<U, V>>( +template <class Axis, class U, + class _V = std::decay_t<detail::arg_type<decltype(&Axis::index)>>> +std::pair<index_type, index_type> update(Axis& axis, const U& value) noexcept( + std::is_convertible<U, _V>::value) { + return detail::static_if_c<static_options<Axis>::test(option::growth)>( [&value](auto& a) { - using A = detail::remove_cvref_t<decltype(a)>; - return detail::static_if_c<static_options<A>::test(option::growth)>( - [&value](auto& a) { return a.update(value); }, - [&value](auto& a) { return std::make_pair(a.index(value), 0); }, a); + return a.update(detail::try_cast<_V, std::invalid_argument>(value)); }, - [](Axis&) -> std::pair<index_type, index_type> { - BOOST_THROW_EXCEPTION(std::invalid_argument( - detail::cat(boost::core::demangled_name(BOOST_CORE_TYPEID(Axis)), - ": cannot convert argument of type ", - boost::core::demangled_name(BOOST_CORE_TYPEID(U)), " to ", - boost::core::demangled_name(BOOST_CORE_TYPEID(V))))); -#ifndef _MSC_VER // msvc warns about unreachable return - return std::make_pair(index_type{}, index_type{}); -#endif - }, - axis); + [&value](auto& a) { return std::make_pair(index(a, value), index_type{0}); }, axis); } -/// @copydoc update(Axis& axis, const U& value) +// specialization for variant template <class... Ts, class U> -auto update(variant<Ts...>& axis, const U& value) { - return axis.update(value); +std::pair<index_type, index_type> update(variant<Ts...>& axis, const U& value) { + return visit([&value](auto& a) { return a.update(value); }, axis); } /** Returns bin width at axis index. @@ -267,14 +270,31 @@ decltype(auto) width(const Axis& axis, index_type index) { */ template <class Result, class Axis> Result width_as(const Axis& axis, index_type index) { - return detail::value_method_switch_with_return_type<Result, Result>( + return detail::value_method_switch( [](const auto&) { return Result{}; }, [index](const auto& a) { - return static_cast<Result>(a.value(index + 1) - a.value(index)); + return detail::try_cast<Result, std::runtime_error>(a.value(index + 1) - + a.value(index)); }, axis); } +/** Meta-function to detect whether an axis is reducible. + + Doxygen does not render this well. This is a meta-function, it accepts an axis + type and represents std::true_type or std::false_type, depending on whether the axis can + be reduced with boost::histogram::algorithm::reduce(). + + @tparam Axis axis type. + */ +template <class Axis> +#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED +using is_reducible = std::is_constructible<Axis, const Axis&, axis::index_type, + axis::index_type, unsigned>; +#else +struct is_reducible; +#endif + } // namespace traits } // namespace axis } // namespace histogram diff --git a/boost/histogram/axis/variable.hpp b/boost/histogram/axis/variable.hpp index d3d6b855cf..10641c96ee 100644 --- a/boost/histogram/axis/variable.hpp +++ b/boost/histogram/axis/variable.hpp @@ -13,13 +13,18 @@ #include <boost/histogram/axis/iterator.hpp> #include <boost/histogram/axis/option.hpp> #include <boost/histogram/detail/compressed_pair.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/convert_integer.hpp> +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/limits.hpp> +#include <boost/histogram/detail/relaxed_equal.hpp> +#include <boost/histogram/detail/replace_default.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> @@ -52,7 +57,23 @@ class variable : public iterator_mixin<variable<Value, MetaData, Options, Alloca using vec_type = std::vector<Value, allocator_type>; public: - explicit variable(allocator_type alloc = {}) : vec_meta_(std::move(alloc)) {} + explicit variable(allocator_type alloc = {}) : vec_meta_(vec_type{alloc}) {} + variable(const variable&) = default; + variable& operator=(const variable&) = default; + variable(variable&& o) noexcept : vec_meta_(std::move(o.vec_meta_)) { + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_constructible<metadata_type>::value, + ""); + } + variable& operator=(variable&& o) noexcept { + // std::string explicitly guarantees nothrow only in C++17 + static_assert(std::is_same<metadata_type, std::string>::value || + std::is_nothrow_move_assignable<metadata_type>::value, + ""); + vec_meta_ = std::move(o.vec_meta_); + return *this; + } /** Construct from iterator range of bin edges. * @@ -215,22 +236,19 @@ variable(std::initializer_list<U>, const char*)->variable<T>; template <class U, class M, class T = detail::convert_integer<U, double>> variable(std::initializer_list<U>, M)->variable<T, M>; -template < - class Iterable, - class T = detail::convert_integer< - detail::remove_cvref_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>> +template <class Iterable, + class T = detail::convert_integer< + std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>> variable(Iterable)->variable<T>; -template < - class Iterable, - class T = detail::convert_integer< - detail::remove_cvref_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>> +template <class Iterable, + class T = detail::convert_integer< + std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>> variable(Iterable, const char*)->variable<T>; -template < - class Iterable, class M, - class T = detail::convert_integer< - detail::remove_cvref_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>> +template <class Iterable, class M, + class T = detail::convert_integer< + std::decay_t<decltype(*std::begin(std::declval<Iterable&>()))>, double>> variable(Iterable, M)->variable<T, M>; #endif diff --git a/boost/histogram/axis/variant.hpp b/boost/histogram/axis/variant.hpp index 55ba85ab34..aa13fefbb3 100644 --- a/boost/histogram/axis/variant.hpp +++ b/boost/histogram/axis/variant.hpp @@ -7,24 +7,21 @@ #ifndef BOOST_HISTOGRAM_AXIS_VARIANT_HPP #define BOOST_HISTOGRAM_AXIS_VARIANT_HPP -#include <boost/core/typeinfo.hpp> #include <boost/histogram/axis/iterator.hpp> #include <boost/histogram/axis/polymorphic_bin.hpp> #include <boost/histogram/axis/traits.hpp> #include <boost/histogram/detail/cat.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/relaxed_equal.hpp> +#include <boost/histogram/detail/static_if.hpp> +#include <boost/histogram/detail/type_name.hpp> #include <boost/histogram/fwd.hpp> -#include <boost/mp11/bind.hpp> #include <boost/mp11/function.hpp> #include <boost/mp11/list.hpp> +#include <boost/mp11/utility.hpp> #include <boost/throw_exception.hpp> -#include <boost/variant/apply_visitor.hpp> -#include <boost/variant/get.hpp> -#include <boost/variant/static_visitor.hpp> -#include <boost/variant/variant.hpp> +#include <boost/variant2/variant.hpp> #include <ostream> #include <stdexcept> -#include <tuple> #include <type_traits> #include <utility> @@ -32,27 +29,20 @@ namespace boost { namespace histogram { namespace axis { -template <class T, class... Us> -T* get_if(variant<Us...>* v); - -template <class T, class... Us> -const T* get_if(const variant<Us...>* v); - /// Polymorphic axis type template <class... Ts> class variant : public iterator_mixin<variant<Ts...>> { - using impl_type = boost::variant<Ts...>; - using raw_types = mp11::mp_transform<detail::remove_cvref_t, impl_type>; + using impl_type = boost::variant2::variant<Ts...>; template <class T> - using is_bounded_type = mp11::mp_contains<raw_types, detail::remove_cvref_t<T>>; + using is_bounded_type = mp11::mp_contains<variant, std::decay_t<T>>; template <typename T> using requires_bounded_type = std::enable_if_t<is_bounded_type<T>::value>; // maybe metadata_type or const metadata_type, if bounded type is const using metadata_type = std::remove_reference_t<decltype( - traits::metadata(std::declval<mp11::mp_first<impl_type>>()))>; + traits::metadata(std::declval<std::remove_pointer_t<mp11::mp_first<variant>>>()))>; public: // cannot import ctors with using directive, it breaks gcc and msvc @@ -62,10 +52,10 @@ public: variant(variant&&) = default; variant& operator=(variant&&) = default; - template <typename T, typename = requires_bounded_type<T>> + template <class T, class = requires_bounded_type<T>> variant(T&& t) : impl(std::forward<T>(t)) {} - template <typename T, typename = requires_bounded_type<T>> + template <class T, class = requires_bounded_type<T>> variant& operator=(T&& t) { impl = std::forward<T>(t); return *this; @@ -80,14 +70,13 @@ public: variant& operator=(const variant<Us...>& u) { visit( [this](const auto& u) { - using U = detail::remove_cvref_t<decltype(u)>; + using U = std::decay_t<decltype(u)>; detail::static_if<is_bounded_type<U>>( [this](const auto& u) { this->operator=(u); }, [](const auto&) { BOOST_THROW_EXCEPTION(std::runtime_error(detail::cat( - boost::core::demangled_name(BOOST_CORE_TYPEID(U)), - " is not convertible to a bounded type of ", - boost::core::demangled_name(BOOST_CORE_TYPEID(variant))))); + detail::type_name<U>(), " is not convertible to a bounded type of ", + detail::type_name<variant>()))); }, u); }, @@ -97,12 +86,12 @@ public: /// Return size of axis. index_type size() const { - return visit([](const auto& x) { return x.size(); }, *this); + return visit([](const auto& a) { return a.size(); }, *this); } /// Return options of axis or option::none_t if axis has no options. unsigned options() const { - return visit([](const auto& x) { return axis::traits::options(x); }, *this); + return visit([](const auto& a) { return axis::traits::options(a); }, *this); } /// Return reference to const metadata or instance of null_type if axis has no @@ -114,13 +103,12 @@ public: return detail::static_if<std::is_same<M, const metadata_type&>>( [](const auto& a) -> const metadata_type& { return traits::metadata(a); }, [](const auto&) -> const metadata_type& { - BOOST_THROW_EXCEPTION(std::runtime_error(detail::cat( - "cannot return metadata of type ", - boost::core::demangled_name(BOOST_CORE_TYPEID(M)), - " through axis::variant interface which uses type ", - boost::core::demangled_name(BOOST_CORE_TYPEID(metadata_type)), - "; use boost::histogram::axis::get to obtain a reference " - "of this axis type"))); + BOOST_THROW_EXCEPTION(std::runtime_error( + detail::cat("cannot return metadata of type ", detail::type_name<M>(), + " through axis::variant interface which uses type ", + detail::type_name<metadata_type>(), + "; use boost::histogram::axis::get to obtain a reference " + "of this axis type"))); }, a); }, @@ -131,166 +119,184 @@ public: /// metadata. metadata_type& metadata() { return visit( - [](auto&& a) -> metadata_type& { + [](auto& a) -> metadata_type& { using M = decltype(traits::metadata(a)); return detail::static_if<std::is_same<M, metadata_type&>>( [](auto& a) -> metadata_type& { return traits::metadata(a); }, [](auto&) -> metadata_type& { - BOOST_THROW_EXCEPTION(std::runtime_error(detail::cat( - "cannot return metadata of type ", - boost::core::demangled_name(BOOST_CORE_TYPEID(M)), - " through axis::variant interface which uses type ", - boost::core::demangled_name(BOOST_CORE_TYPEID(metadata_type)), - "; use boost::histogram::axis::get to obtain a reference " - "of this axis type"))); + BOOST_THROW_EXCEPTION(std::runtime_error( + detail::cat("cannot return metadata of type ", detail::type_name<M>(), + " through axis::variant interface which uses type ", + detail::type_name<metadata_type>(), + "; use boost::histogram::axis::get to obtain a reference " + "of this axis type"))); }, a); }, *this); } - /// Return index for value argument. - /// Throws std::invalid_argument if axis has incompatible call signature. + /** Return index for value argument. + + Throws std::invalid_argument if axis has incompatible call signature. + */ template <class U> index_type index(const U& u) const { return visit([&u](const auto& a) { return traits::index(a, u); }, *this); } - /// Return value for index argument. - /// Only works for axes with value method that returns something convertible - /// to double and will throw a runtime_error otherwise, see - /// axis::traits::value(). + /** Return value for index argument. + + Only works for axes with value method that returns something convertible + to double and will throw a runtime_error otherwise, see + axis::traits::value(). + */ double value(real_index_type idx) const { return visit([idx](const auto& a) { return traits::value_as<double>(a, idx); }, *this); } - /// Return bin for index argument. - /// Only works for axes with value method that returns something convertible - /// to double and will throw a runtime_error otherwise, see - /// axis::traits::value(). + /** Return bin for index argument. + + Only works for axes with value method that returns something convertible + to double and will throw a runtime_error otherwise, see + axis::traits::value(). + */ auto bin(index_type idx) const { return visit( [idx](const auto& a) { - return detail::value_method_switch_with_return_type<double, - polymorphic_bin<double>>( + return detail::value_method_switch( [idx](const auto& a) { // axis is discrete - const auto x = a.value(idx); + const double x = traits::value_as<double>(a, idx); return polymorphic_bin<double>(x, x); }, [idx](const auto& a) { // axis is continuous - return polymorphic_bin<double>(a.value(idx), a.value(idx + 1)); + const double x1 = traits::value_as<double>(a, idx); + const double x2 = traits::value_as<double>(a, idx + 1); + return polymorphic_bin<double>(x1, x2); }, a); }, *this); } + /** Compare two variants. + + Return true if the variants point to the same concrete axis type and the types compare + equal. Otherwise return false. + */ template <class... Us> bool operator==(const variant<Us...>& u) const { return visit([&u](const auto& x) { return u == x; }, *this); } + /** Compare variant with a concrete axis type. + + Return true if the variant point to the same concrete axis type and the types compare + equal. Otherwise return false. + */ template <class T> bool operator==(const T& t) const { - // boost::variant::operator==(T) implemented only to fail, cannot use it - auto tp = get_if<T>(this); - return tp && detail::relaxed_equal(*tp, t); + return detail::static_if_c<(mp11::mp_contains<impl_type, T>::value || + mp11::mp_contains<impl_type, T*>::value || + mp11::mp_contains<impl_type, const T*>::value)>( + [&](const auto& t) { + using U = std::decay_t<decltype(t)>; + const U* tp = detail::variant_access::template get_if<U>(this); + return tp && detail::relaxed_equal(*tp, t); + }, + [&](const auto&) { return false; }, t); } + /// The negation of operator==. template <class T> bool operator!=(const T& t) const { return !operator==(t); } - template <class Archive> - void serialize(Archive& ar, unsigned); - - template <class Visitor, class Variant> - friend auto visit(Visitor&&, Variant &&) - -> detail::visitor_return_type<Visitor, Variant>; - - template <class T, class... Us> - friend T& get(variant<Us...>& v); - - template <class T, class... Us> - friend const T& get(const variant<Us...>& v); +private: + impl_type impl; - template <class T, class... Us> - friend T&& get(variant<Us...>&& v); + friend struct detail::variant_access; + friend struct boost::histogram::unsafe_access; +}; - template <class T, class... Us> - friend T* get_if(variant<Us...>* v); +// specialization for empty argument list, useful for meta-programming +template <> +class variant<> {}; - template <class T, class... Us> - friend const T* get_if(const variant<Us...>* v); +/// Apply visitor to variant (reference). +template <class Visitor, class... Us> +decltype(auto) visit(Visitor&& vis, variant<Us...>& var) { + return detail::variant_access::visit(vis, var); +} -private: - boost::variant<Ts...> impl; -}; +/// Apply visitor to variant (movable reference). +template <class Visitor, class... Us> +decltype(auto) visit(Visitor&& vis, variant<Us...>&& var) { + return detail::variant_access::visit(vis, std::move(var)); +} -/// Apply visitor to variant. -template <class Visitor, class Variant> -auto visit(Visitor&& vis, Variant&& var) - -> detail::visitor_return_type<Visitor, Variant> { - return boost::apply_visitor(std::forward<Visitor>(vis), var.impl); +/// Apply visitor to variant (const reference). +template <class Visitor, class... Us> +decltype(auto) visit(Visitor&& vis, const variant<Us...>& var) { + return detail::variant_access::visit(vis, var); } -/// Return lvalue reference to T, throws unspecified exception if type does not -/// match. +/// Returns pointer to T in variant or null pointer if type does not match. template <class T, class... Us> -T& get(variant<Us...>& v) { - return boost::get<T>(v.impl); +T* get_if(variant<Us...>* v) { + return detail::variant_access::template get_if<T>(v); } -/// Return rvalue reference to T, throws unspecified exception if type does not -/// match. +/// Returns pointer to const T in variant or null pointer if type does not match. template <class T, class... Us> -T&& get(variant<Us...>&& v) { - return boost::get<T>(std::move(v.impl)); +const T* get_if(const variant<Us...>* v) { + return detail::variant_access::template get_if<T>(v); } -/// Return const reference to T, throws unspecified exception if type does not -/// match. +/// Return reference to T, throws std::runtime_error if type does not match. template <class T, class... Us> -const T& get(const variant<Us...>& v) { - return boost::get<T>(v.impl); +decltype(auto) get(variant<Us...>& v) { + auto tp = get_if<T>(&v); + if (!tp) BOOST_THROW_EXCEPTION(std::runtime_error("T is not the held type")); + return *tp; } -/// Returns pointer to T in variant or null pointer if type does not match. +/// Return movable reference to T, throws unspecified exception if type does not match. template <class T, class... Us> -T* get_if(variant<Us...>* v) { - return boost::relaxed_get<T>(&(v->impl)); +decltype(auto) get(variant<Us...>&& v) { + auto tp = get_if<T>(&v); + if (!tp) BOOST_THROW_EXCEPTION(std::runtime_error("T is not the held type")); + return std::move(*tp); } -/// Returns pointer to const T in variant or null pointer if type does not -/// match. +/// Return const reference to T, throws unspecified exception if type does not match. template <class T, class... Us> -const T* get_if(const variant<Us...>* v) { - return boost::relaxed_get<T>(&(v->impl)); +decltype(auto) get(const variant<Us...>& v) { + auto tp = get_if<T>(&v); + if (!tp) BOOST_THROW_EXCEPTION(std::runtime_error("T is not the held type")); + return *tp; } -#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED // pass-through version of get for generic programming template <class T, class U> decltype(auto) get(U&& u) { - return static_cast<detail::copy_qualifiers<U, T>>(u); + return std::forward<U>(u); } // pass-through version of get_if for generic programming template <class T, class U> T* get_if(U* u) { - return std::is_same<T, detail::remove_cvref_t<U>>::value ? reinterpret_cast<T*>(u) - : nullptr; + return std::is_same<T, std::decay_t<U>>::value ? reinterpret_cast<T*>(u) : nullptr; } // pass-through version of get_if for generic programming template <class T, class U> const T* get_if(const U* u) { - return std::is_same<T, detail::remove_cvref_t<U>>::value ? reinterpret_cast<const T*>(u) - : nullptr; + return std::is_same<T, std::decay_t<U>>::value ? reinterpret_cast<const T*>(u) + : nullptr; } -#endif } // namespace axis } // namespace histogram diff --git a/boost/histogram/detail/args_type.hpp b/boost/histogram/detail/args_type.hpp new file mode 100644 index 0000000000..a6c442d550 --- /dev/null +++ b/boost/histogram/detail/args_type.hpp @@ -0,0 +1,38 @@ +// 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_DETAIL_ARGS_TYPE_HPP +#define BOOST_HISTOGRAM_DETAIL_ARGS_TYPE_HPP + +#include <boost/config/workaround.hpp> +#if BOOST_WORKAROUND(BOOST_GCC, >= 60000) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wnoexcept-type" +#endif +#include <boost/callable_traits/args.hpp> +#if BOOST_WORKAROUND(BOOST_GCC, >= 60000) +#pragma GCC diagnostic pop +#endif +#include <boost/mp11/list.hpp> // mp_pop_front +#include <tuple> +#include <type_traits> // is_member_function_pointer + +namespace boost { +namespace histogram { +namespace detail { + +template <class T, class Args = boost::callable_traits::args_t<T>> +using args_type = std::conditional_t<std::is_member_function_pointer<T>::value, + mp11::mp_pop_front<Args>, Args>; + +template <class T, std::size_t N = 0> +using arg_type = std::tuple_element_t<N, args_type<T>>; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/attribute.hpp b/boost/histogram/detail/attribute.hpp index 1fbfc43e9e..436b11498b 100644 --- a/boost/histogram/detail/attribute.hpp +++ b/boost/histogram/detail/attribute.hpp @@ -8,9 +8,9 @@ #define BOOST_HISTOGRAM_DETAIL_ATTRIBUTE_HPP #if __cplusplus >= 201703L -#define BOOST_HISTOGRAM_DETAIL_NODISCARD [[nodiscard]] +#define BOOST_HISTOGRAM_NODISCARD [[nodiscard]] #else -#define BOOST_HISTOGRAM_DETAIL_NODISCARD +#define BOOST_HISTOGRAM_NODISCARD #endif #endif diff --git a/boost/histogram/detail/axes.hpp b/boost/histogram/detail/axes.hpp index 7af45c3e45..1372936d4e 100644 --- a/boost/histogram/detail/axes.hpp +++ b/boost/histogram/detail/axes.hpp @@ -7,23 +7,49 @@ #ifndef BOOST_HISTOGRAM_DETAIL_AXES_HPP #define BOOST_HISTOGRAM_DETAIL_AXES_HPP +#include <array> #include <boost/assert.hpp> #include <boost/histogram/axis/traits.hpp> #include <boost/histogram/axis/variant.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/static_if.hpp> #include <boost/histogram/fwd.hpp> #include <boost/mp11/algorithm.hpp> #include <boost/mp11/list.hpp> #include <boost/mp11/tuple.hpp> +#include <boost/mp11/utility.hpp> #include <boost/throw_exception.hpp> #include <stdexcept> #include <tuple> #include <type_traits> +/* Most of the histogram code is generic and works for any number of axes. Buffers with a + * fixed maximum capacity are used in some places, which have a size equal to the rank of + * a histogram. The buffers are statically allocated to improve performance, which means + * that they need a preset maximum capacity. 32 seems like a safe upper limit for the rank + * (you can nevertheless increase it here if necessary): the simplest non-trivial axis has + * 2 bins; even if counters are used which need only a byte of storage per bin, this still + * corresponds to 4 GB of storage. + */ +#ifndef BOOST_HISTOGRAM_DETAIL_AXES_LIMIT +#define BOOST_HISTOGRAM_DETAIL_AXES_LIMIT 32 +#endif + namespace boost { namespace histogram { namespace detail { +template <class T> +unsigned axes_rank(const T& axes) { + using std::begin; + using std::end; + return static_cast<unsigned>(std::distance(begin(axes), end(axes))); +} + +template <class... Ts> +constexpr unsigned axes_rank(const std::tuple<Ts...>&) { + return static_cast<unsigned>(sizeof...(Ts)); +} + template <unsigned N, class... Ts> decltype(auto) axis_get(std::tuple<Ts...>& axes) { return std::get<N>(axes); @@ -46,14 +72,18 @@ decltype(auto) axis_get(const T& axes) { template <class... Ts> decltype(auto) axis_get(std::tuple<Ts...>& axes, unsigned i) { - return mp11::mp_with_index<sizeof...(Ts)>( - i, [&](auto I) { return axis::variant<Ts&...>(std::get<I>(axes)); }); + using namespace boost::mp11; + constexpr auto S = sizeof...(Ts); + using V = mp_unique<axis::variant<Ts*...>>; + return mp_with_index<S>(i, [&axes](auto i) { return V(&std::get<i>(axes)); }); } template <class... Ts> decltype(auto) axis_get(const std::tuple<Ts...>& axes, unsigned i) { - return mp11::mp_with_index<sizeof...(Ts)>( - i, [&](auto I) { return axis::variant<const Ts&...>(std::get<I>(axes)); }); + using namespace boost::mp11; + constexpr auto S = sizeof...(Ts); + using V = mp_unique<axis::variant<const Ts*...>>; + return mp_with_index<S>(i, [&axes](auto i) { return V(&std::get<i>(axes)); }); } template <class T> @@ -70,7 +100,7 @@ template <class... Ts, class... Us> bool axes_equal(const std::tuple<Ts...>& ts, const std::tuple<Us...>& us) { return static_if<std::is_same<mp11::mp_list<Ts...>, mp11::mp_list<Us...>>>( [](const auto& ts, const auto& us) { - using N = mp11::mp_size<remove_cvref_t<decltype(ts)>>; + using N = mp11::mp_size<std::decay_t<decltype(ts)>>; bool equal = true; mp11::mp_for_each<mp11::mp_iota<N>>( [&](auto I) { equal &= relaxed_equal(std::get<I>(ts), std::get<I>(us)); }); @@ -79,17 +109,17 @@ bool axes_equal(const std::tuple<Ts...>& ts, const std::tuple<Us...>& us) { [](const auto&, const auto&) { return false; }, ts, us); } -template <class... Ts, class U> -bool axes_equal(const std::tuple<Ts...>& t, const U& u) { - if (sizeof...(Ts) != u.size()) return false; +template <class T, class... Us> +bool axes_equal(const T& t, const std::tuple<Us...>& u) { + if (t.size() != sizeof...(Us)) return false; bool equal = true; - mp11::mp_for_each<mp11::mp_iota_c<sizeof...(Ts)>>( - [&](auto I) { equal &= u[I] == std::get<I>(t); }); + mp11::mp_for_each<mp11::mp_iota_c<sizeof...(Us)>>( + [&](auto I) { equal &= t[I] == std::get<I>(u); }); return equal; } -template <class T, class... Us> -bool axes_equal(const T& t, const std::tuple<Us...>& u) { +template <class... Ts, class U> +bool axes_equal(const std::tuple<Ts...>& t, const U& u) { return axes_equal(u, t); } @@ -131,9 +161,23 @@ void axes_assign(T& t, const U& u) { t.assign(u.begin(), u.end()); } +// create empty dynamic axis which can store any axes types from the argument +template <class T> +auto make_empty_dynamic_axes(const T& axes) { + return make_default(axes); +} + +template <class... Ts> +auto make_empty_dynamic_axes(const std::tuple<Ts...>&) { + using namespace ::boost::mp11; + using L = mp_unique<axis::variant<Ts...>>; + // return std::vector<axis::variant<Axis0, Axis1, ...>> or std::vector<Axis0> + return std::vector<mp_if_c<(mp_size<L>::value == 1), mp_first<L>, L>>{}; +} + template <typename T> void axis_index_is_valid(const T& axes, const unsigned N) { - BOOST_ASSERT_MSG(N < get_size(axes), "index out of range"); + BOOST_ASSERT_MSG(N < axes_rank(axes), "index out of range"); } template <typename F, typename T> @@ -169,6 +213,50 @@ std::size_t bincount(const T& axes) { return n; } +template <class T> +using tuple_size_t = typename std::tuple_size<T>::type; + +template <class T> +using buffer_size = mp11::mp_eval_or< + std::integral_constant<std::size_t, BOOST_HISTOGRAM_DETAIL_AXES_LIMIT>, tuple_size_t, + T>; + +template <class T, std::size_t N> +class sub_array : public std::array<T, N> { + using base_type = std::array<T, N>; + +public: + explicit sub_array(std::size_t s) noexcept( + std::is_nothrow_default_constructible<T>::value) + : size_(s) { + BOOST_ASSERT_MSG(size_ <= N, "requested size exceeds size of static buffer"); + } + + sub_array(std::size_t s, + const T& value) noexcept(std::is_nothrow_copy_constructible<T>::value) + : size_(s) { + BOOST_ASSERT_MSG(size_ <= N, "requested size exceeds size of static buffer"); + std::array<T, N>::fill(value); + } + + // need to override both versions of std::array + auto end() noexcept { return base_type::begin() + size_; } + auto end() const noexcept { return base_type::begin() + size_; } + + auto size() const noexcept { return size_; } + +private: + std::size_t size_; +}; + +template <class U, class T> +using stack_buffer = sub_array<U, buffer_size<T>::value>; + +template <class U, class T, class... Ts> +auto make_stack_buffer(const T& t, const Ts&... ts) { + return stack_buffer<U, T>(axes_rank(t), ts...); +} + } // namespace detail } // namespace histogram } // namespace boost diff --git a/boost/histogram/detail/common_type.hpp b/boost/histogram/detail/common_type.hpp index e1a4b66469..848d10a452 100644 --- a/boost/histogram/detail/common_type.hpp +++ b/boost/histogram/detail/common_type.hpp @@ -7,7 +7,7 @@ #ifndef BOOST_HISTOGRAM_DETAIL_COMMON_TYPE_HPP #define BOOST_HISTOGRAM_DETAIL_COMMON_TYPE_HPP -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/detect.hpp> #include <boost/histogram/fwd.hpp> #include <boost/mp11/list.hpp> #include <boost/mp11/utility.hpp> @@ -26,51 +26,20 @@ using common_axes = mp11::mp_cond< is_sequence_of_axis<U>, U, std::true_type, T >; - -template <class T, class U> -using common_container = mp11::mp_cond< - is_array_like<T>, T, - is_array_like<U>, U, - is_vector_like<T>, T, - is_vector_like<U>, U, - std::true_type, T ->; // clang-format on -template <class T> -using type_score = mp11::mp_size_t<((!std::is_pod<T>::value) * 1000 + - std::is_floating_point<T>::value * 50 + sizeof(T))>; - -template <class T, class U> -struct common_storage_impl; +// Non-PODs rank highest, then floats, than integers; types with more capacity are higher +template <class Storage> +static constexpr std::size_t type_rank() { + using T = typename Storage::value_type; + return !std::is_pod<T>::value * 10000 + std::is_floating_point<T>::value * 100 + + 10 * sizeof(T) + 2 * is_array_like<Storage>::value + + is_vector_like<Storage>::value; + ; +} template <class T, class U> -struct common_storage_impl<storage_adaptor<T>, storage_adaptor<U>> { - using type = - mp11::mp_if_c<(type_score<typename storage_adaptor<T>::value_type>::value >= - type_score<typename storage_adaptor<U>::value_type>::value), - storage_adaptor<T>, storage_adaptor<U>>; -}; - -template <class T, class A> -struct common_storage_impl<storage_adaptor<T>, unlimited_storage<A>> { - using type = - mp11::mp_if_c<(type_score<typename storage_adaptor<T>::value_type>::value >= - type_score<typename unlimited_storage<A>::value_type>::value), - storage_adaptor<T>, unlimited_storage<A>>; -}; - -template <class C, class A> -struct common_storage_impl<unlimited_storage<A>, storage_adaptor<C>> - : common_storage_impl<storage_adaptor<C>, unlimited_storage<A>> {}; - -template <class A1, class A2> -struct common_storage_impl<unlimited_storage<A1>, unlimited_storage<A2>> { - using type = unlimited_storage<A1>; -}; - -template <class A, class B> -using common_storage = typename common_storage_impl<A, B>::type; +using common_storage = mp11::mp_if_c<(type_rank<T>() >= type_rank<U>()), T, U>; } // namespace detail } // namespace histogram } // namespace boost diff --git a/boost/histogram/detail/compressed_pair.hpp b/boost/histogram/detail/compressed_pair.hpp index 8288e5d8b1..aead2cb59d 100644 --- a/boost/histogram/detail/compressed_pair.hpp +++ b/boost/histogram/detail/compressed_pair.hpp @@ -14,59 +14,79 @@ namespace boost { namespace histogram { namespace detail { -template <typename T1, typename T2, bool B> +template <class T1, class T2, bool B> class compressed_pair_impl; -template <typename T1, typename T2> -class compressed_pair_impl<T1, T2, true> : protected T2 { +// normal implementation +template <class T1, class T2> +class compressed_pair_impl<T1, T2, false> { public: - template <typename U1, typename U2> - compressed_pair_impl(U1&& u1, U2&& u2) - : T2(std::forward<U2>(u2)), first_(std::forward<U1>(u1)) {} - template <typename U1> - compressed_pair_impl(U1&& u1) : first_(std::forward<U1>(u1)) {} + using first_type = T1; + using second_type = T2; + compressed_pair_impl() = default; - T1& first() { return first_; } - T2& second() { return static_cast<T2&>(*this); } - const T1& first() const { return first_; } - const T2& second() const { return static_cast<const T2&>(*this); } + compressed_pair_impl(first_type&& x, second_type&& y) + : first_(std::move(x)), second_(std::move(y)) {} + + compressed_pair_impl(const first_type& x, const second_type& y) + : first_(x), second_(y) {} + + compressed_pair_impl(first_type&& x) : first_(std::move(x)) {} + compressed_pair_impl(const first_type& x) : first_(x) {} + + first_type& first() noexcept { return first_; } + second_type& second() noexcept { return second_; } + const first_type& first() const noexcept { return first_; } + const second_type& second() const noexcept { return second_; } private: - T1 first_; + first_type first_; + second_type second_; }; -template <typename T1, typename T2> -class compressed_pair_impl<T1, T2, false> { +// compressed implementation, T2 consumes no space +template <class T1, class T2> +class compressed_pair_impl<T1, T2, true> : protected T2 { public: - template <typename U1, typename U2> - compressed_pair_impl(U1&& u1, U2&& u2) - : first_(std::forward<U1>(u1)), second_(std::forward<U2>(u2)) {} - template <typename U1> - compressed_pair_impl(U1&& u1) : first_(std::forward<U1>(u1)) {} + using first_type = T1; + using second_type = T2; + compressed_pair_impl() = default; - T1& first() { return first_; } - T2& second() { return second_; } - const T1& first() const { return first_; } - const T2& second() const { return second_; } + compressed_pair_impl(first_type&& x, second_type&& y) + : T2(std::move(y)), first_(std::move(x)) {} + + compressed_pair_impl(const first_type& x, const second_type& y) : T2(y), first_(x) {} + + compressed_pair_impl(first_type&& x) : first_(std::move(x)) {} + compressed_pair_impl(const first_type& x) : first_(x) {} + + first_type& first() noexcept { return first_; } + second_type& second() noexcept { return static_cast<second_type&>(*this); } + const first_type& first() const noexcept { return first_; } + const second_type& second() const noexcept { + return static_cast<const second_type&>(*this); + } private: - T1 first_; - T2 second_; + first_type first_; }; -template <typename... Ts> -void swap(compressed_pair_impl<Ts...>& a, compressed_pair_impl<Ts...>& b) { +template <typename T1, typename T2> +using compressed_pair = + compressed_pair_impl<T1, T2, (!std::is_final<T2>::value && std::is_empty<T2>::value)>; + +template <class T, class U> +void swap(compressed_pair<T, U>& a, compressed_pair<T, U>& b) noexcept( + std::is_nothrow_move_constructible<T>::value&& std::is_nothrow_move_assignable< + T>::value&& std::is_nothrow_move_constructible<U>::value&& + std::is_nothrow_move_assignable<U>::value) { using std::swap; swap(a.first(), b.first()); swap(a.second(), b.second()); } -template <typename T1, typename T2> -using compressed_pair = - compressed_pair_impl<T1, T2, (!std::is_final<T2>::value && std::is_empty<T2>::value)>; - } // namespace detail } // namespace histogram } // namespace boost diff --git a/boost/histogram/detail/convert_integer.hpp b/boost/histogram/detail/convert_integer.hpp new file mode 100644 index 0000000000..bed52f7599 --- /dev/null +++ b/boost/histogram/detail/convert_integer.hpp @@ -0,0 +1,24 @@ +// Copyright 2018-2019 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_DETAIL_CONVERT_INTEGER_HPP +#define BOOST_HISTOGRAM_DETAIL_CONVERT_INTEGER_HPP + +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T, class U> +using convert_integer = + std::conditional_t<std::is_integral<std::decay_t<T>>::value, U, T>; + +} +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/detect.hpp b/boost/histogram/detail/detect.hpp new file mode 100644 index 0000000000..c1cf87717f --- /dev/null +++ b/boost/histogram/detail/detect.hpp @@ -0,0 +1,209 @@ +// Copyright 2015-2019 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_DETAIL_DETECT_HPP +#define BOOST_HISTOGRAM_DETAIL_DETECT_HPP + +#include <boost/histogram/fwd.hpp> +#include <boost/mp11/algorithm.hpp> +#include <boost/mp11/function.hpp> +#include <boost/mp11/utility.hpp> +#include <iterator> +#include <tuple> +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { + +#define BOOST_HISTOGRAM_DETECT(name, cond) \ + template <class T, class = decltype(cond)> \ + struct name##_impl {}; \ + template <class T> \ + struct name : mp11::mp_valid<name##_impl, T>::type {} + +#define BOOST_HISTOGRAM_DETECT_BINARY(name, cond) \ + template <class T, class U, class = decltype(cond)> \ + struct name##_impl {}; \ + template <class T, class U = T> \ + struct name : mp11::mp_valid<name##_impl, T, U>::type {} + +// metadata has overloads, trying to get pmf in this case always fails +BOOST_HISTOGRAM_DETECT(has_method_metadata, (std::declval<T&>().metadata())); + +// resize has overloads, trying to get pmf in this case always fails +BOOST_HISTOGRAM_DETECT(has_method_resize, (std::declval<T&>().resize(0))); + +BOOST_HISTOGRAM_DETECT(has_method_size, &T::size); + +BOOST_HISTOGRAM_DETECT(has_method_clear, &T::clear); + +BOOST_HISTOGRAM_DETECT(has_method_lower, &T::lower); + +BOOST_HISTOGRAM_DETECT(has_method_value, &T::value); + +BOOST_HISTOGRAM_DETECT(has_method_update, (&T::update)); + +// reset has overloads, trying to get pmf in this case always fails +BOOST_HISTOGRAM_DETECT(has_method_reset, (std::declval<T>().reset(0))); + +BOOST_HISTOGRAM_DETECT(has_method_options, (&T::options)); + +BOOST_HISTOGRAM_DETECT(has_allocator, &T::get_allocator); + +BOOST_HISTOGRAM_DETECT(is_indexable, (std::declval<T&>()[0])); + +BOOST_HISTOGRAM_DETECT(is_transform, (&T::forward, &T::inverse)); + +BOOST_HISTOGRAM_DETECT(is_indexable_container, + (std::declval<T>()[0], &T::size, std::begin(std::declval<T>()), + std::end(std::declval<T>()))); + +BOOST_HISTOGRAM_DETECT(is_vector_like, + (std::declval<T>()[0], &T::size, std::declval<T>().resize(0), + std::begin(std::declval<T>()), std::end(std::declval<T>()))); + +BOOST_HISTOGRAM_DETECT(is_array_like, + (std::declval<T>()[0], &T::size, std::tuple_size<T>::value, + std::begin(std::declval<T>()), std::end(std::declval<T>()))); + +BOOST_HISTOGRAM_DETECT(is_map_like, + (std::declval<typename T::key_type>(), + std::declval<typename T::mapped_type>(), + std::begin(std::declval<T>()), std::end(std::declval<T>()))); + +// ok: is_axis is false for axis::variant, because T::index is templated +BOOST_HISTOGRAM_DETECT(is_axis, (&T::size, &T::index)); + +BOOST_HISTOGRAM_DETECT(is_iterable, + (std::begin(std::declval<T&>()), std::end(std::declval<T&>()))); + +BOOST_HISTOGRAM_DETECT(is_iterator, + (typename std::iterator_traits<T>::iterator_category())); + +BOOST_HISTOGRAM_DETECT(is_streamable, + (std::declval<std::ostream&>() << std::declval<T&>())); + +BOOST_HISTOGRAM_DETECT(has_operator_preincrement, (++std::declval<T&>())); + +BOOST_HISTOGRAM_DETECT_BINARY(has_operator_equal, + (std::declval<const T&>() == std::declval<const U>())); + +BOOST_HISTOGRAM_DETECT_BINARY(has_operator_radd, + (std::declval<T&>() += std::declval<U>())); + +BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rsub, + (std::declval<T&>() -= std::declval<U>())); + +BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rmul, + (std::declval<T&>() *= std::declval<U>())); + +BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rdiv, + (std::declval<T&>() /= std::declval<U>())); + +BOOST_HISTOGRAM_DETECT_BINARY( + has_method_eq, (std::declval<const T>().operator==(std::declval<const U>()))); + +BOOST_HISTOGRAM_DETECT(has_threading_support, (T::has_threading_support)); + +template <typename T> +struct is_weight_impl : std::false_type {}; + +template <typename T> +struct is_weight_impl<weight_type<T>> : std::true_type {}; + +template <typename T> +using is_weight = is_weight_impl<std::decay_t<T>>; + +template <typename T> +struct is_sample_impl : std::false_type {}; + +template <typename T> +struct is_sample_impl<sample_type<T>> : std::true_type {}; + +template <typename T> +using is_sample = is_sample_impl<std::decay_t<T>>; + +template <typename T> +using is_storage = mp11::mp_and<is_indexable_container<T>, has_method_reset<T>, + has_threading_support<T>>; + +template <class T> +using is_adaptible = mp11::mp_or<is_vector_like<T>, is_array_like<T>, is_map_like<T>>; + +template <class T, class _ = std::decay_t<T>, + class = std::enable_if_t<(is_storage<_>::value || is_adaptible<_>::value)>> +struct requires_storage_or_adaptible {}; + +template <typename T> +struct is_tuple_impl : std::false_type {}; + +template <typename... Ts> +struct is_tuple_impl<std::tuple<Ts...>> : std::true_type {}; + +template <typename T> +using is_tuple = typename is_tuple_impl<T>::type; + +template <typename T> +struct is_axis_variant_impl : std::false_type {}; + +template <typename... Ts> +struct is_axis_variant_impl<axis::variant<Ts...>> : std::true_type {}; + +template <typename T> +using is_axis_variant = typename is_axis_variant_impl<T>::type; + +template <typename T> +using is_any_axis = mp11::mp_or<is_axis<T>, is_axis_variant<T>>; + +template <typename T> +using is_sequence_of_axis = mp11::mp_and<is_iterable<T>, is_axis<mp11::mp_first<T>>>; + +template <typename T> +using is_sequence_of_axis_variant = + mp11::mp_and<is_iterable<T>, is_axis_variant<mp11::mp_first<T>>>; + +template <typename T> +using is_sequence_of_any_axis = + mp11::mp_and<is_iterable<T>, is_any_axis<mp11::mp_first<T>>>; + +// poor-mans concept checks +template <class T, class = std::enable_if_t<is_iterator<std::decay_t<T>>::value>> +struct requires_iterator {}; + +template <class T, class = std::enable_if_t< + is_iterable<std::remove_cv_t<std::remove_reference_t<T>>>::value>> +struct requires_iterable {}; + +template <class T, class = std::enable_if_t<is_axis<std::decay_t<T>>::value>> +struct requires_axis {}; + +template <class T, class = std::enable_if_t<is_any_axis<std::decay_t<T>>::value>> +struct requires_any_axis {}; + +template <class T, class = std::enable_if_t<is_sequence_of_axis<std::decay_t<T>>::value>> +struct requires_sequence_of_axis {}; + +template <class T, + class = std::enable_if_t<is_sequence_of_axis_variant<std::decay_t<T>>::value>> +struct requires_sequence_of_axis_variant {}; + +template <class T, + class = std::enable_if_t<is_sequence_of_any_axis<std::decay_t<T>>::value>> +struct requires_sequence_of_any_axis {}; + +template <class T, + class = std::enable_if_t<is_any_axis<mp11::mp_first<std::decay_t<T>>>::value>> +struct requires_axes {}; + +template <class T, class U, class = std::enable_if_t<std::is_convertible<T, U>::value>> +struct requires_convertible {}; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/iterator_adaptor.hpp b/boost/histogram/detail/iterator_adaptor.hpp new file mode 100644 index 0000000000..345a4abb19 --- /dev/null +++ b/boost/histogram/detail/iterator_adaptor.hpp @@ -0,0 +1,162 @@ +// Copyright 2019 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) +// +// Uses code segments from boost/iterator/iterator_adaptor.hpp +// and boost/iterator/iterator_fascade.hpp + +#ifndef BOOST_HISTOGRAM_DETAIL_ITERATOR_ADAPTOR_HPP +#define BOOST_HISTOGRAM_DETAIL_ITERATOR_ADAPTOR_HPP + +#include <iterator> +#include <memory> +#include <type_traits> +#include <utility> + +namespace boost { +namespace histogram { +namespace detail { + +// operator->() needs special support for input iterators to strictly meet the +// standard's requirements. If *i is not a reference type, we must still +// produce an lvalue to which a pointer can be formed. We do that by +// returning a proxy object containing an instance of the reference object. +template <class Reference> +struct operator_arrow_dispatch_t // proxy references +{ + struct proxy { + explicit proxy(Reference const& x) noexcept : m_ref(x) {} + Reference* operator->() noexcept { return std::addressof(m_ref); } + Reference m_ref; + }; + + using result_type = proxy; + static result_type apply(Reference const& x) noexcept { return proxy(x); } +}; + +template <class T> +struct operator_arrow_dispatch_t<T&> // "real" references +{ + using result_type = T*; + static result_type apply(T& x) noexcept { return std::addressof(x); } +}; + +// only for random access Base +template <class Derived, class Base, class Reference = std::remove_pointer_t<Base>&, + class Value = std::decay_t<Reference>> +class iterator_adaptor { + using operator_arrow_dispatch = operator_arrow_dispatch_t<Reference>; + +public: + using base_type = Base; + + using reference = Reference; + using value_type = std::remove_const_t<Value>; + using pointer = typename operator_arrow_dispatch::result_type; + using difference_type = std::ptrdiff_t; + using iterator_category = std::random_access_iterator_tag; + + iterator_adaptor() = default; + + explicit iterator_adaptor(base_type const& iter) : iter_(iter) {} + + pointer operator->() const noexcept { + return operator_arrow_dispatch::apply(this->derived().operator*()); + } + reference operator[](difference_type n) const { return *(this->derived() + n); } + + Derived& operator++() { + ++iter_; + return this->derived(); + } + + Derived& operator--() { + --iter_; + return this->derived(); + } + + Derived operator++(int) { + Derived tmp(this->derived()); + ++iter_; + return tmp; + } + + Derived operator--(int) { + Derived tmp(this->derived()); + --iter_; + return tmp; + } + + Derived& operator+=(difference_type n) { + iter_ += n; + return this->derived(); + } + + Derived& operator-=(difference_type n) { + iter_ -= n; + return this->derived(); + } + + Derived operator+(difference_type n) const { + Derived tmp(this->derived()); + tmp += n; + return tmp; + } + + Derived operator-(difference_type n) const { return operator+(-n); } + + template <class... Ts> + difference_type operator-(const iterator_adaptor<Ts...>& x) const noexcept { + return iter_ - x.iter_; + } + + template <class... Ts> + bool operator==(const iterator_adaptor<Ts...>& x) const noexcept { + return iter_ == x.iter_; + } + template <class... Ts> + bool operator!=(const iterator_adaptor<Ts...>& x) const noexcept { + return !this->derived().operator==(x); // equal operator may be overridden in derived + } + template <class... Ts> + bool operator<(const iterator_adaptor<Ts...>& x) const noexcept { + return iter_ < x.iter_; + } + template <class... Ts> + bool operator>(const iterator_adaptor<Ts...>& x) const noexcept { + return iter_ > x.iter_; + } + template <class... Ts> + bool operator<=(const iterator_adaptor<Ts...>& x) const noexcept { + return iter_ <= x.iter_; + } + template <class... Ts> + bool operator>=(const iterator_adaptor<Ts...>& x) const noexcept { + return iter_ >= x.iter_; + } + + friend Derived operator+(difference_type n, const Derived& x) { return x + n; } + + Base const& base() const noexcept { return iter_; } + +protected: + // for convenience in derived classes + using iterator_adaptor_ = iterator_adaptor; + +private: + Derived& derived() noexcept { return *static_cast<Derived*>(this); } + const Derived& derived() const noexcept { return *static_cast<Derived const*>(this); } + + Base iter_; + + template <class, class, class, class> + friend class iterator_adaptor; +}; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/large_int.hpp b/boost/histogram/detail/large_int.hpp new file mode 100644 index 0000000000..2259cbda5f --- /dev/null +++ b/boost/histogram/detail/large_int.hpp @@ -0,0 +1,227 @@ +// Copyright 2018-2019 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_DETAIL_LARGE_INT_HPP +#define BOOST_HISTOGRAM_DETAIL_LARGE_INT_HPP + +#include <boost/assert.hpp> +#include <boost/histogram/detail/operators.hpp> +#include <boost/histogram/detail/safe_comparison.hpp> +#include <boost/mp11/algorithm.hpp> +#include <boost/mp11/function.hpp> +#include <boost/mp11/list.hpp> +#include <boost/mp11/utility.hpp> +#include <cmath> +#include <cstdint> +#include <limits> +#include <type_traits> +#include <utility> +#include <vector> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T> +using is_unsigned_integral = mp11::mp_and<std::is_integral<T>, std::is_unsigned<T>>; + +template <class T> +bool safe_increment(T& t) { + if (t < std::numeric_limits<T>::max()) { + ++t; + return true; + } + return false; +} + +template <class T, class U> +bool safe_radd(T& t, const U& u) { + static_assert(is_unsigned_integral<T>::value, "T must be unsigned integral type"); + static_assert(is_unsigned_integral<U>::value, "T must be unsigned integral type"); + if (static_cast<T>(std::numeric_limits<T>::max() - t) >= u) { + t += static_cast<T>(u); // static_cast to suppress conversion warning + return true; + } + return false; +} + +// An integer type which can grow arbitrarily large (until memory is exhausted). +// Use boost.multiprecision.cpp_int in your own code, it is much more sophisticated. +// We use it only to reduce coupling between boost libs. +template <class Allocator> +struct large_int : totally_ordered<large_int<Allocator>, large_int<Allocator>>, + partially_ordered<large_int<Allocator>, void> { + explicit large_int(const Allocator& a = {}) : data(1, 0, a) {} + explicit large_int(std::uint64_t v, const Allocator& a = {}) : data(1, v, a) {} + + large_int(const large_int&) = default; + large_int& operator=(const large_int&) = default; + large_int(large_int&&) = default; + large_int& operator=(large_int&&) = default; + + large_int& operator=(std::uint64_t o) { + data = decltype(data)(1, o); + return *this; + } + + large_int& operator++() { + BOOST_ASSERT(data.size() > 0u); + std::size_t i = 0; + while (!safe_increment(data[i])) { + data[i] = 0; + ++i; + if (i == data.size()) { + data.push_back(1); + break; + } + } + return *this; + } + + large_int& operator+=(const large_int& o) { + if (this == &o) { + auto tmp{o}; + return operator+=(tmp); + } + bool carry = false; + std::size_t i = 0; + for (std::uint64_t oi : o.data) { + auto& di = maybe_extend(i); + if (carry) { + if (safe_increment(oi)) + carry = false; + else { + ++i; + continue; + } + } + if (!safe_radd(di, oi)) { + add_remainder(di, oi); + carry = true; + } + ++i; + } + while (carry) { + auto& di = maybe_extend(i); + if (safe_increment(di)) break; + di = 0; + ++i; + } + return *this; + } + + large_int& operator+=(std::uint64_t o) { + BOOST_ASSERT(data.size() > 0u); + if (safe_radd(data[0], o)) return *this; + add_remainder(data[0], o); + // carry the one, data may grow several times + std::size_t i = 1; + while (true) { + auto& di = maybe_extend(i); + if (safe_increment(di)) break; + di = 0; + ++i; + } + return *this; + } + + explicit operator double() const noexcept { + BOOST_ASSERT(data.size() > 0u); + double result = static_cast<double>(data[0]); + std::size_t i = 0; + while (++i < data.size()) + result += static_cast<double>(data[i]) * std::pow(2.0, i * 64); + return result; + } + + bool operator<(const large_int& o) const noexcept { + BOOST_ASSERT(data.size() > 0u); + BOOST_ASSERT(o.data.size() > 0u); + // no leading zeros allowed + BOOST_ASSERT(data.size() == 1 || data.back() > 0u); + BOOST_ASSERT(o.data.size() == 1 || o.data.back() > 0u); + if (data.size() < o.data.size()) return true; + if (data.size() > o.data.size()) return false; + auto s = data.size(); + while (s > 0u) { + --s; + if (data[s] < o.data[s]) return true; + if (data[s] > o.data[s]) return false; + } + return false; // args are equal + } + + bool operator==(const large_int& o) const noexcept { + BOOST_ASSERT(data.size() > 0u); + BOOST_ASSERT(o.data.size() > 0u); + // no leading zeros allowed + BOOST_ASSERT(data.size() == 1 || data.back() > 0u); + BOOST_ASSERT(o.data.size() == 1 || o.data.back() > 0u); + if (data.size() != o.data.size()) return false; + return std::equal(data.begin(), data.end(), o.data.begin()); + } + + template <class U> + std::enable_if_t<std::is_integral<U>::value, bool> operator<(const U& o) const + noexcept { + BOOST_ASSERT(data.size() > 0u); + return data.size() == 1 && safe_less()(data[0], o); + } + + template <class U> + std::enable_if_t<std::is_integral<U>::value, bool> operator>(const U& o) const + noexcept { + BOOST_ASSERT(data.size() > 0u); + BOOST_ASSERT(data.size() == 1 || data.back() > 0u); // no leading zeros allowed + return data.size() > 1 || safe_less()(o, data[0]); + } + + template <class U> + std::enable_if_t<std::is_integral<U>::value, bool> operator==(const U& o) const + noexcept { + BOOST_ASSERT(data.size() > 0u); + return data.size() == 1 && safe_equal()(data[0], o); + } + + template <class U> + std::enable_if_t<std::is_floating_point<U>::value, bool> operator<(const U& o) const + noexcept { + return operator double() < o; + } + template <class U> + std::enable_if_t<std::is_floating_point<U>::value, bool> operator>(const U& o) const + noexcept { + return operator double() > o; + } + template <class U> + std::enable_if_t<std::is_floating_point<U>::value, bool> operator==(const U& o) const + noexcept { + return operator double() == o; + } + + std::uint64_t& maybe_extend(std::size_t i) { + while (i >= data.size()) data.push_back(0); + return data[i]; + } + + static void add_remainder(std::uint64_t& d, const std::uint64_t o) noexcept { + BOOST_ASSERT(d > 0u); + // in decimal system it would look like this: + // 8 + 8 = 6 = 8 - (9 - 8) - 1 + // 9 + 1 = 0 = 9 - (9 - 1) - 1 + auto tmp = std::numeric_limits<std::uint64_t>::max(); + tmp -= o; + --d -= tmp; + } + + std::vector<std::uint64_t, Allocator> data; +}; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/limits.hpp b/boost/histogram/detail/limits.hpp new file mode 100644 index 0000000000..23b8a6f1c5 --- /dev/null +++ b/boost/histogram/detail/limits.hpp @@ -0,0 +1,50 @@ +// Copyright 2015-2019 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_DETAIL_LIMITS_HPP +#define BOOST_HISTOGRAM_DETAIL_LIMITS_HPP + +#include <limits> + +namespace boost { +namespace histogram { +namespace detail { + +template <typename T> +constexpr T lowest() { + return std::numeric_limits<T>::lowest(); +} + +template <> +constexpr double lowest() { + return -std::numeric_limits<double>::infinity(); +} + +template <> +constexpr float lowest() { + return -std::numeric_limits<float>::infinity(); +} + +template <typename T> +constexpr T highest() { + return std::numeric_limits<T>::max(); +} + +template <> +constexpr double highest() { + return std::numeric_limits<double>::infinity(); +} + +template <> +constexpr float highest() { + return std::numeric_limits<float>::infinity(); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/linearize.hpp b/boost/histogram/detail/linearize.hpp index e07590ab4d..b24be8efbd 100644 --- a/boost/histogram/detail/linearize.hpp +++ b/boost/histogram/detail/linearize.hpp @@ -11,16 +11,19 @@ #include <boost/assert.hpp> #include <boost/histogram/axis/traits.hpp> #include <boost/histogram/axis/variant.hpp> +#include <boost/histogram/detail/args_type.hpp> #include <boost/histogram/detail/axes.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/make_default.hpp> +#include <boost/histogram/detail/static_if.hpp> +#include <boost/histogram/detail/tuple_slice.hpp> #include <boost/histogram/fwd.hpp> -#include <boost/histogram/unsafe_access.hpp> #include <boost/mp11/algorithm.hpp> #include <boost/mp11/function.hpp> #include <boost/mp11/integral.hpp> #include <boost/mp11/list.hpp> #include <boost/mp11/tuple.hpp> #include <boost/throw_exception.hpp> +#include <mutex> #include <stdexcept> #include <tuple> #include <type_traits> @@ -30,25 +33,33 @@ namespace histogram { namespace detail { template <class T> -struct is_accumulator_set : std::false_type {}; - -template <class T> using has_underflow = decltype(axis::traits::static_options<T>::test(axis::option::underflow)); template <class T> -struct is_growing - : decltype(axis::traits::static_options<T>::test(axis::option::growth)) {}; +using is_growing = decltype(axis::traits::static_options<T>::test(axis::option::growth)); + +template <class T> +using is_multidim = is_tuple<std::decay_t<arg_type<decltype(&T::index)>>>; + +template <template <class> class Trait, class T> +struct has_special_axis_impl : Trait<T> {}; + +template <template <class> class Trait, class... Ts> +struct has_special_axis_impl<Trait, std::tuple<Ts...>> : mp11::mp_or<Trait<Ts>...> {}; -template <class... Ts> -struct is_growing<std::tuple<Ts...>> : mp11::mp_or<is_growing<Ts>...> {}; +template <template <class> class Trait, class... Ts> +struct has_special_axis_impl<Trait, axis::variant<Ts...>> : mp11::mp_or<Trait<Ts>...> {}; -template <class... Ts> -struct is_growing<axis::variant<Ts...>> : mp11::mp_or<is_growing<Ts>...> {}; +template <template <class> class Trait, class T> +using has_special_axis = + has_special_axis_impl<Trait, mp11::mp_if<is_vector_like<T>, mp11::mp_first<T>, T>>; template <class T> -using has_growing_axis = - mp11::mp_if<is_vector_like<T>, is_growing<mp11::mp_first<T>>, is_growing<T>>; +using has_multidim_axis = has_special_axis<is_multidim, T>; + +template <class T> +using has_growing_axis = has_special_axis<is_growing, T>; /// Index with an invalid state struct optional_index { @@ -58,64 +69,85 @@ struct optional_index { std::size_t operator*() const { return idx; } }; -inline void linearize(optional_index& out, const axis::index_type extent, - const axis::index_type j) noexcept { - // j is internal index shifted by +1 if axis has underflow bin - out.idx += j * out.stride; - // set stride to 0, if j is invalid - out.stride *= (0 <= j && j < extent) * extent; +// no underflow, no overflow +inline void linearize(std::false_type, std::false_type, optional_index& out, + const axis::index_type size, const axis::index_type i) noexcept { + out.idx += i * out.stride; + out.stride *= i >= 0 && i < size ? size : 0; +} + +// no underflow, overflow +inline void linearize(std::false_type, std::true_type, optional_index& out, + const axis::index_type size, const axis::index_type i) noexcept { + BOOST_ASSERT(i <= size); + out.idx += i * out.stride; + out.stride *= i >= 0 ? size + 1 : 0; +} + +// underflow, no overflow +inline void linearize(std::true_type, std::false_type, optional_index& out, + const axis::index_type size, const axis::index_type i) noexcept { + // internal index must be shifted by +1 since axis has underflow bin + BOOST_ASSERT(i + 1 >= 0); + out.idx += (i + 1) * out.stride; + out.stride *= i < size ? size + 1 : 0; +} + +// underflow, overflow +inline void linearize(std::true_type, std::true_type, optional_index& out, + const axis::index_type size, const axis::index_type i) noexcept { + // internal index must be shifted by +1 since axis has underflow bin + BOOST_ASSERT(i + 1 >= 0); + BOOST_ASSERT(i <= size); + out.idx += (i + 1) * out.stride; + out.stride *= size + 2; } -// for non-growing axis template <class Axis, class Value> void linearize_value(optional_index& o, const Axis& a, const Value& v) { - using B = decltype(axis::traits::static_options<Axis>::test(axis::option::underflow)); - const auto j = axis::traits::index(a, v) + B::value; - linearize(o, axis::traits::extent(a), j); + using O = axis::traits::static_options<Axis>; + linearize(O::test(axis::option::underflow), O::test(axis::option::overflow), o, + a.size(), axis::traits::index(a, v)); } -// for variant that does not contain any growing axis template <class... Ts, class Value> void linearize_value(optional_index& o, const axis::variant<Ts...>& a, const Value& v) { axis::visit([&o, &v](const auto& a) { linearize_value(o, a, v); }, a); } -// for growing axis template <class Axis, class Value> -void linearize_value(optional_index& o, axis::index_type& s, Axis& a, const Value& v) { - axis::index_type j; - std::tie(j, s) = axis::traits::update(a, v); - j += has_underflow<Axis>::value; - linearize(o, axis::traits::extent(a), j); +axis::index_type linearize_value_growth(optional_index& o, Axis& a, const Value& v) { + using O = axis::traits::static_options<Axis>; + axis::index_type i, s; + std::tie(i, s) = axis::traits::update(a, v); + linearize(O::test(axis::option::underflow), O::test(axis::option::overflow), o, + a.size(), i); + return s; } -// for variant which contains at least one growing axis template <class... Ts, class Value> -void linearize_value(optional_index& o, axis::index_type& s, axis::variant<Ts...>& a, - const Value& v) { - axis::visit([&o, &s, &v](auto&& a) { linearize_value(o, s, a, v); }, a); +axis::index_type linearize_value_growth(optional_index& o, axis::variant<Ts...>& a, + const Value& v) { + return axis::visit([&o, &v](auto& a) { return linearize_value_growth(o, a, v); }, a); } template <class A> -void linearize_index(optional_index& out, const A& axis, const axis::index_type j) { +void linearize_index(optional_index& out, const A& axis, const axis::index_type i) { // A may be axis or variant, cannot use static option detection here const auto opt = axis::traits::options(axis); const auto shift = opt & axis::option::underflow ? 1 : 0; - const auto n = axis.size() + (opt & axis::option::overflow ? 1 : 0); - linearize(out, n + shift, j + shift); + const auto extent = axis.size() + (opt & axis::option::overflow ? 1 : 0) + shift; + // i may be arbitrarily out of range + linearize(std::false_type{}, std::false_type{}, out, extent, i + shift); } -template <class S, class A, class T> -void maybe_replace_storage(S& storage, const A& axes, const T& shifts) { - bool update_needed = false; - auto sit = shifts; - for_each_axis(axes, [&](const auto&) { update_needed |= (*sit++ != 0); }); - if (!update_needed) return; +template <class S, class A> +void grow_storage(const A& axes, S& storage, const axis::index_type* shifts) { struct item { axis::index_type idx, old_extent; std::size_t new_stride; } data[buffer_size<A>::value]; - sit = shifts; + const auto* sit = shifts; auto dit = data; std::size_t s = 1; for_each_axis(axes, [&](const auto& a) { @@ -124,8 +156,8 @@ void maybe_replace_storage(S& storage, const A& axes, const T& shifts) { s *= n; }); auto new_storage = make_default(storage); - new_storage.reset(detail::bincount(axes)); - const auto dlast = data + get_size(axes) - 1; + new_storage.reset(bincount(axes)); + const auto dlast = data + axes_rank(axes) - 1; for (const auto& x : storage) { auto ns = new_storage.begin(); sit = shifts; @@ -170,6 +202,30 @@ void maybe_replace_storage(S& storage, const A& axes, const T& shifts) { storage = std::move(new_storage); } +// histogram has no growing and no multidim axis, axis rank known at compile-time +template <class S, class... As, class... Us> +optional_index index(std::false_type, std::false_type, const std::tuple<As...>& axes, S&, + const std::tuple<Us...>& args) { + optional_index idx; + static_assert(sizeof...(As) == sizeof...(Us), "number of arguments != histogram rank"); + mp11::mp_for_each<mp11::mp_iota_c<sizeof...(As)>>( + [&](auto i) { linearize_value(idx, axis_get<i>(axes), std::get<i>(args)); }); + return idx; +} + +// histogram has no growing and no multidim axis, axis rank known at run-time +template <class A, class S, class U> +optional_index index(std::false_type, std::false_type, const A& axes, S&, const U& args) { + constexpr auto nargs = static_cast<unsigned>(std::tuple_size<U>::value); + optional_index idx; + if (axes_rank(axes) != nargs) + BOOST_THROW_EXCEPTION(std::invalid_argument("number of arguments != histogram rank")); + constexpr auto nbuf = buffer_size<A>::value; + mp11::mp_for_each<mp11::mp_iota_c<(nargs < nbuf ? nargs : nbuf)>>( + [&](auto i) { linearize_value(idx, axis_get<i>(axes), std::get<i>(args)); }); + return idx; +} + // special case: if histogram::operator()(tuple(1, 2)) is called on 1d histogram // with axis that accepts 2d tuple, this should not fail // - solution is to forward tuples of size > 1 directly to axis for 1d @@ -179,55 +235,78 @@ void maybe_replace_storage(S& storage, const A& axes, const T& shifts) { // (axis::variant provides generic call interface and hides concrete // interface), so we throw at runtime if incompatible argument is passed (e.g. // 3d tuple) -// histogram has only non-growing axes -template <unsigned I, unsigned N, class S, class T, class U> -optional_index args_to_index(std::false_type, S&, const T& axes, const U& args) { + +// histogram has no growing multidim axis, axis rank == 1 known at compile-time +template <class S, class A, class U> +optional_index index(std::false_type, std::true_type, const std::tuple<A>& axes, S&, + const U& args) { optional_index idx; - const auto rank = get_size(axes); - if (rank == 1 && N > 1) - linearize_value(idx, axis_get<0>(axes), tuple_slice<I, N>(args)); + linearize_value(idx, axis_get<0>(axes), args); + return idx; +} + +// histogram has no growing multidim axis, axis rank > 1 known at compile-time +template <class S, class U, class A0, class A1, class... As> +optional_index index(std::false_type, std::true_type, + const std::tuple<A0, A1, As...>& axes, S& s, const U& args) { + return index(std::false_type{}, std::false_type{}, axes, s, args); +} + +// histogram has no growing multidim axis, axis rank known at run-time +template <class A, class S, class U> +optional_index index(std::false_type, std::true_type, const A& axes, S&, const U& args) { + optional_index idx; + const auto rank = axes_rank(axes); + constexpr auto nargs = static_cast<unsigned>(std::tuple_size<U>::value); + if (rank == 1 && nargs > 1) + linearize_value(idx, axis_get<0>(axes), args); else { - if (rank != N) + if (rank != nargs) BOOST_THROW_EXCEPTION( std::invalid_argument("number of arguments != histogram rank")); - constexpr unsigned M = buffer_size<remove_cvref_t<decltype(axes)>>::value; - mp11::mp_for_each<mp11::mp_iota_c<(N < M ? N : M)>>([&](auto J) { - linearize_value(idx, axis_get<J>(axes), std::get<(J + I)>(args)); - }); + constexpr auto nbuf = buffer_size<A>::value; + mp11::mp_for_each<mp11::mp_iota_c<(nargs < nbuf ? nargs : nbuf)>>( + [&](auto i) { linearize_value(idx, axis_get<i>(axes), std::get<i>(args)); }); } return idx; } -// histogram has growing axes -template <unsigned I, unsigned N, class S, class T, class U> -optional_index args_to_index(std::true_type, S& storage, T& axes, const U& args) { +// histogram has growing axis +template <class B, class T, class S, class U> +optional_index index(std::true_type, B, T& axes, S& storage, const U& args) { optional_index idx; - axis::index_type shifts[buffer_size<T>::value]; - const auto rank = get_size(axes); - if (rank == 1 && N > 1) - linearize_value(idx, shifts[0], axis_get<0>(axes), tuple_slice<I, N>(args)); - else { - if (rank != N) + constexpr unsigned nbuf = buffer_size<T>::value; + axis::index_type shifts[nbuf]; + const auto rank = axes_rank(axes); + constexpr auto nargs = static_cast<unsigned>(std::tuple_size<U>::value); + + bool update_needed = false; + if (rank == 1 && nargs > 1) { + shifts[0] = linearize_value_growth(idx, axis_get<0>(axes), args); + update_needed = (shifts[0] != 0); + } else { + if (rank != nargs) BOOST_THROW_EXCEPTION( std::invalid_argument("number of arguments != histogram rank")); - constexpr unsigned M = buffer_size<remove_cvref_t<decltype(axes)>>::value; - mp11::mp_for_each<mp11::mp_iota_c<(N < M ? N : M)>>([&](auto J) { - linearize_value(idx, shifts[J], axis_get<J>(axes), std::get<(J + I)>(args)); + mp11::mp_for_each<mp11::mp_iota_c<(nargs < nbuf ? nargs : nbuf)>>([&](auto i) { + shifts[i] = linearize_value_growth(idx, axis_get<i>(axes), std::get<i>(args)); + update_needed |= (shifts[i] != 0); }); } - maybe_replace_storage(storage, axes, shifts); + + if (update_needed) grow_storage(axes, storage, shifts); return idx; } -template <typename U> -constexpr auto weight_sample_indices() { +template <class U> +constexpr auto weight_sample_indices() noexcept { if (is_weight<U>::value) return std::make_pair(0, -1); if (is_sample<U>::value) return std::make_pair(-1, 0); return std::make_pair(-1, -1); } -template <typename U0, typename U1, typename... Us> -constexpr auto weight_sample_indices() { +template <class U0, class U1, class... Us> +constexpr auto weight_sample_indices() noexcept { using L = mp11::mp_list<U0, U1, Us...>; const int n = sizeof...(Us) + 1; if (is_weight<mp11::mp_at_c<L, 0>>::value) { @@ -254,72 +333,71 @@ constexpr auto weight_sample_indices() { } template <class T, class U> -void fill_storage(mp11::mp_int<-1>, mp11::mp_int<-1>, T&& t, U&&) { - static_if<is_incrementable<remove_cvref_t<T>>>( - [](auto&& t) { ++t; }, [](auto&& t) { t(); }, std::forward<T>(t)); +void fill_impl(mp11::mp_int<-1>, mp11::mp_int<-1>, std::false_type, T&& t, + const U&) noexcept { + t(); +} + +template <class T, class U> +void fill_impl(mp11::mp_int<-1>, mp11::mp_int<-1>, std::true_type, T&& t, + const U&) noexcept { + ++t; } template <class IW, class T, class U> -void fill_storage(IW, mp11::mp_int<-1>, T&& t, U&& args) { - static_if<is_incrementable<remove_cvref_t<T>>>( - [](auto&& t, const auto& w) { t += w; }, - [](auto&& t, const auto& w) { -#ifdef BOOST_HISTOGRAM_WITH_ACCUMULATORS_SUPPORT - static_if<is_accumulator_set<remove_cvref_t<T>>>( - [w](auto&& t) { t(::boost::accumulators::weight = w); }, - [w](auto&& t) { t(w); }, t); -#else - t(w); -#endif - }, - std::forward<T>(t), std::get<IW::value>(args).value); +void fill_impl(IW, mp11::mp_int<-1>, std::false_type, T&& t, const U& u) noexcept { + t(std::get<IW::value>(u).value); +} + +template <class IW, class T, class U> +void fill_impl(IW, mp11::mp_int<-1>, std::true_type, T&& t, const U& u) noexcept { + t += std::get<IW::value>(u).value; } template <class IS, class T, class U> -void fill_storage(mp11::mp_int<-1>, IS, T&& t, U&& args) { - mp11::tuple_apply([&t](auto&&... args) { t(args...); }, - std::get<IS::value>(args).value); +void fill_impl(mp11::mp_int<-1>, IS, std::false_type, T&& t, const U& u) noexcept { + mp11::tuple_apply([&t](auto&&... args) { t(args...); }, std::get<IS::value>(u).value); } template <class IW, class IS, class T, class U> -void fill_storage(IW, IS, T&& t, U&& args) { - mp11::tuple_apply( - [&](auto&&... args2) { t(std::get<IW::value>(args).value, args2...); }, - std::get<IS::value>(args).value); +void fill_impl(IW, IS, std::false_type, T&& t, const U& u) noexcept { + mp11::tuple_apply([&](auto&&... args2) { t(std::get<IW::value>(u).value, args2...); }, + std::get<IS::value>(u).value); } -template <class S, class A, class... Us> -auto fill(S& storage, A& axes, const std::tuple<Us...>& args) { +template <class A, class S, class... Us> +typename S::iterator fill(A& axes, S& storage, const std::tuple<Us...>& tus) { constexpr auto iws = weight_sample_indices<Us...>(); constexpr unsigned n = sizeof...(Us) - (iws.first > -1) - (iws.second > -1); constexpr unsigned i = (iws.first == 0 || iws.second == 0) ? (iws.first == 1 || iws.second == 1 ? 2 : 1) : 0; - optional_index idx = args_to_index<i, n>(has_growing_axis<A>(), storage, axes, args); + const auto idx = index(has_growing_axis<A>{}, has_multidim_axis<A>{}, axes, storage, + tuple_slice<i, n>(tus)); if (idx) { - fill_storage(mp11::mp_int<iws.first>(), mp11::mp_int<iws.second>(), storage[*idx], - args); + fill_impl(mp11::mp_int<iws.first>{}, mp11::mp_int<iws.second>{}, + has_operator_preincrement<typename S::value_type>{}, storage[*idx], tus); return storage.begin() + *idx; } return storage.end(); } -template <typename A, typename... Us> +template <class A, class... Us> optional_index at(const A& axes, const std::tuple<Us...>& args) { - if (get_size(axes) != sizeof...(Us)) + if (axes_rank(axes) != sizeof...(Us)) BOOST_THROW_EXCEPTION(std::invalid_argument("number of arguments != histogram rank")); optional_index idx; - mp11::mp_for_each<mp11::mp_iota_c<sizeof...(Us)>>([&](auto I) { + mp11::mp_for_each<mp11::mp_iota_c<sizeof...(Us)>>([&](auto i) { // axes_get works with static and dynamic axes - linearize_index(idx, axis_get<I>(axes), - static_cast<axis::index_type>(std::get<I>(args))); + linearize_index(idx, axis_get<i>(axes), + static_cast<axis::index_type>(std::get<i>(args))); }); return idx; } -template <typename A, typename U> +template <class A, class U> optional_index at(const A& axes, const U& args) { - if (get_size(axes) != get_size(args)) + if (axes_rank(axes) != axes_rank(args)) BOOST_THROW_EXCEPTION(std::invalid_argument("number of arguments != histogram rank")); optional_index idx; using std::begin; diff --git a/boost/histogram/detail/make_default.hpp b/boost/histogram/detail/make_default.hpp new file mode 100644 index 0000000000..738bde6fb6 --- /dev/null +++ b/boost/histogram/detail/make_default.hpp @@ -0,0 +1,27 @@ +// Copyright 2015-2019 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_DETAIL_MAKE_DEFAULT_HPP +#define BOOST_HISTOGRAM_DETAIL_MAKE_DEFAULT_HPP + +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/static_if.hpp> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T> +auto make_default(const T& t) { + return static_if<has_allocator<T>>([](const auto& t) { return T(t.get_allocator()); }, + [](const auto&) { return T{}; }, t); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/meta.hpp b/boost/histogram/detail/meta.hpp deleted file mode 100644 index 0a5c5ea0ff..0000000000 --- a/boost/histogram/detail/meta.hpp +++ /dev/null @@ -1,436 +0,0 @@ -// 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_DETAIL_META_HPP -#define BOOST_HISTOGRAM_DETAIL_META_HPP - -/* Most of the histogram code is generic and works for any number of axes. Buffers with a - * fixed maximum capacity are used in some places, which have a size equal to the rank of - * a histogram. The buffers are statically allocated to improve performance, which means - * that they need a preset maximum capacity. 32 seems like a safe upper limit for the rank - * (you can nevertheless increase it here if necessary): the simplest non-trivial axis has - * 2 bins; even if counters are used which need only a byte of storage per bin, this still - * corresponds to 4 GB of storage. - */ -#ifndef BOOST_HISTOGRAM_DETAIL_AXES_LIMIT -#define BOOST_HISTOGRAM_DETAIL_AXES_LIMIT 32 -#endif - -#include <boost/config/workaround.hpp> -#if BOOST_WORKAROUND(BOOST_GCC, >= 60000) -#pragma GCC diagnostic push -#pragma GCC diagnostic ignored "-Wnoexcept-type" -#endif -#include <boost/callable_traits/args.hpp> -#include <boost/callable_traits/return_type.hpp> -#if BOOST_WORKAROUND(BOOST_GCC, >= 60000) -#pragma GCC diagnostic pop -#endif -#include <array> -#include <boost/histogram/fwd.hpp> -#include <boost/mp11/algorithm.hpp> -#include <boost/mp11/function.hpp> -#include <boost/mp11/integer_sequence.hpp> -#include <boost/mp11/list.hpp> -#include <boost/mp11/utility.hpp> -#include <functional> -#include <iterator> -#include <limits> -#include <tuple> -#include <type_traits> - -namespace boost { -namespace histogram { -namespace detail { - -template <class T> -using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<T>>; - -template <class T, class U> -using convert_integer = mp11::mp_if<std::is_integral<remove_cvref_t<T>>, U, T>; - -// to be replaced by official version from mp11 -template <class E, template <class...> class F, class... Ts> -using mp_eval_or = mp11::mp_eval_if_c<!(mp11::mp_valid<F, Ts...>::value), E, F, Ts...>; - -template <class T1, class T2> -using copy_qualifiers = mp11::mp_if< - std::is_rvalue_reference<T1>, T2&&, - mp11::mp_if<std::is_lvalue_reference<T1>, - mp11::mp_if<std::is_const<typename std::remove_reference<T1>::type>, - const T2&, T2&>, - mp11::mp_if<std::is_const<T1>, const T2, T2>>>; - -template <class L> -using mp_last = mp11::mp_at_c<L, (mp11::mp_size<L>::value - 1)>; - -template <class T, class Args = boost::callable_traits::args_t<T>> -using args_type = - mp11::mp_if<std::is_member_function_pointer<T>, mp11::mp_pop_front<Args>, Args>; - -template <class T, std::size_t N = 0> -using arg_type = typename mp11::mp_at_c<args_type<T>, N>; - -template <class T> -using return_type = typename boost::callable_traits::return_type<T>::type; - -template <class F, class V, - class T = copy_qualifiers<V, mp11::mp_first<remove_cvref_t<V>>>> -using visitor_return_type = decltype(std::declval<F>()(std::declval<T>())); - -template <bool B, typename T, typename F, typename... Ts> -constexpr decltype(auto) static_if_c(T&& t, F&& f, Ts&&... ts) { - return std::get<(B ? 0 : 1)>(std::forward_as_tuple( - std::forward<T>(t), std::forward<F>(f)))(std::forward<Ts>(ts)...); -} - -template <typename B, typename... Ts> -constexpr decltype(auto) static_if(Ts&&... ts) { - return static_if_c<B::value>(std::forward<Ts>(ts)...); -} - -template <typename T> -constexpr T lowest() { - return std::numeric_limits<T>::lowest(); -} - -template <> -constexpr double lowest() { - return -std::numeric_limits<double>::infinity(); -} - -template <> -constexpr float lowest() { - return -std::numeric_limits<float>::infinity(); -} - -template <typename T> -constexpr T highest() { - return std::numeric_limits<T>::max(); -} - -template <> -constexpr double highest() { - return std::numeric_limits<double>::infinity(); -} - -template <> -constexpr float highest() { - return std::numeric_limits<float>::infinity(); -} - -template <std::size_t I, class T, std::size_t... N> -decltype(auto) tuple_slice_impl(T&& t, mp11::index_sequence<N...>) { - return std::forward_as_tuple(std::get<(N + I)>(std::forward<T>(t))...); -} - -template <std::size_t I, std::size_t N, class T> -decltype(auto) tuple_slice(T&& t) { - static_assert(I + N <= mp11::mp_size<remove_cvref_t<T>>::value, - "I and N must describe a slice"); - return tuple_slice_impl<I>(std::forward<T>(t), mp11::make_index_sequence<N>{}); -} - -#define BOOST_HISTOGRAM_DETECT(name, cond) \ - template <class T, class = decltype(cond)> \ - struct name##_impl {}; \ - template <class T> \ - using name = typename mp11::mp_valid<name##_impl, T> - -#define BOOST_HISTOGRAM_DETECT_BINARY(name, cond) \ - template <class T, class U, class = decltype(cond)> \ - struct name##_impl {}; \ - template <class T, class U = T> \ - using name = typename mp11::mp_valid<name##_impl, T, U> - -BOOST_HISTOGRAM_DETECT(has_method_metadata, (std::declval<T&>().metadata())); - -// resize has two overloads, trying to get pmf in this case always fails -BOOST_HISTOGRAM_DETECT(has_method_resize, (std::declval<T&>().resize(0))); - -BOOST_HISTOGRAM_DETECT(has_method_size, &T::size); - -BOOST_HISTOGRAM_DETECT(has_method_clear, &T::clear); - -BOOST_HISTOGRAM_DETECT(has_method_lower, &T::lower); - -BOOST_HISTOGRAM_DETECT(has_method_value, &T::value); - -BOOST_HISTOGRAM_DETECT(has_method_update, (&T::update)); - -BOOST_HISTOGRAM_DETECT(has_method_reset, (std::declval<T>().reset(0))); - -template <typename T> -using get_value_method_return_type_impl = decltype(std::declval<T&>().value(0)); - -template <typename T, typename R> -using has_method_value_with_convertible_return_type = - typename std::is_convertible<mp_eval_or<void, get_value_method_return_type_impl, T>, - R>::type; - -BOOST_HISTOGRAM_DETECT(has_method_options, (&T::options)); - -BOOST_HISTOGRAM_DETECT(has_allocator, &T::get_allocator); - -BOOST_HISTOGRAM_DETECT(is_indexable, (std::declval<T&>()[0])); - -BOOST_HISTOGRAM_DETECT(is_transform, (&T::forward, &T::inverse)); - -BOOST_HISTOGRAM_DETECT(is_indexable_container, - (std::declval<T>()[0], &T::size, std::begin(std::declval<T>()), - std::end(std::declval<T>()))); - -BOOST_HISTOGRAM_DETECT(is_vector_like, - (std::declval<T>()[0], &T::size, std::declval<T>().resize(0), - std::begin(std::declval<T>()), std::end(std::declval<T>()))); - -BOOST_HISTOGRAM_DETECT(is_array_like, - (std::declval<T>()[0], &T::size, std::tuple_size<T>::value, - std::begin(std::declval<T>()), std::end(std::declval<T>()))); - -BOOST_HISTOGRAM_DETECT(is_map_like, - (std::declval<typename T::key_type>(), - std::declval<typename T::mapped_type>(), - std::begin(std::declval<T>()), std::end(std::declval<T>()))); - -// ok: is_axis is false for axis::variant, operator() is templated -BOOST_HISTOGRAM_DETECT(is_axis, (&T::size, &T::index)); - -BOOST_HISTOGRAM_DETECT(is_iterable, - (std::begin(std::declval<T&>()), std::end(std::declval<T&>()))); - -BOOST_HISTOGRAM_DETECT(is_iterator, - (typename std::iterator_traits<T>::iterator_category())); - -BOOST_HISTOGRAM_DETECT(is_streamable, - (std::declval<std::ostream&>() << std::declval<T&>())); - -BOOST_HISTOGRAM_DETECT(is_incrementable, (++std::declval<T&>())); - -BOOST_HISTOGRAM_DETECT(has_operator_preincrement, (++std::declval<T&>())); - -BOOST_HISTOGRAM_DETECT_BINARY(has_operator_equal, - (std::declval<const T&>() == std::declval<const U&>())); - -BOOST_HISTOGRAM_DETECT_BINARY(has_operator_radd, - (std::declval<T&>() += std::declval<U&>())); - -BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rsub, - (std::declval<T&>() -= std::declval<U&>())); - -BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rmul, - (std::declval<T&>() *= std::declval<U&>())); - -BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rdiv, - (std::declval<T&>() /= std::declval<U&>())); - -template <typename T> -using is_storage = - mp11::mp_bool<(is_indexable_container<T>::value && has_method_reset<T>::value)>; - -template <typename T> -struct is_tuple_impl : std::false_type {}; - -template <typename... Ts> -struct is_tuple_impl<std::tuple<Ts...>> : std::true_type {}; - -template <typename T> -using is_tuple = typename is_tuple_impl<T>::type; - -template <typename T> -struct is_axis_variant_impl : std::false_type {}; - -template <typename... Ts> -struct is_axis_variant_impl<axis::variant<Ts...>> : std::true_type {}; - -template <typename T> -using is_axis_variant = typename is_axis_variant_impl<T>::type; - -template <typename T> -using is_any_axis = mp11::mp_or<is_axis<T>, is_axis_variant<T>>; - -template <typename T> -using is_sequence_of_axis = mp11::mp_and<is_iterable<T>, is_axis<mp11::mp_first<T>>>; - -template <typename T> -using is_sequence_of_axis_variant = - mp11::mp_and<is_iterable<T>, is_axis_variant<mp11::mp_first<T>>>; - -template <typename T> -using is_sequence_of_any_axis = - mp11::mp_and<is_iterable<T>, is_any_axis<mp11::mp_first<T>>>; - -template <typename T> -struct is_weight_impl : std::false_type {}; - -template <typename T> -struct is_weight_impl<weight_type<T>> : std::true_type {}; - -template <typename T> -using is_weight = is_weight_impl<remove_cvref_t<T>>; - -template <typename T> -struct is_sample_impl : std::false_type {}; - -template <typename T> -struct is_sample_impl<sample_type<T>> : std::true_type {}; - -template <typename T> -using is_sample = is_sample_impl<remove_cvref_t<T>>; - -// poor-mans concept checks -template <class T, class = std::enable_if_t<is_iterator<remove_cvref_t<T>>::value>> -struct requires_iterator {}; - -template <class T, class = std::enable_if_t<is_iterable<remove_cvref_t<T>>::value>> -struct requires_iterable {}; - -template <class T, class = std::enable_if_t<is_axis<remove_cvref_t<T>>::value>> -struct requires_axis {}; - -template <class T, class = std::enable_if_t<is_any_axis<remove_cvref_t<T>>::value>> -struct requires_any_axis {}; - -template <class T, - class = std::enable_if_t<is_sequence_of_axis<remove_cvref_t<T>>::value>> -struct requires_sequence_of_axis {}; - -template <class T, - class = std::enable_if_t<is_sequence_of_axis_variant<remove_cvref_t<T>>::value>> -struct requires_sequence_of_axis_variant {}; - -template <class T, - class = std::enable_if_t<is_sequence_of_any_axis<remove_cvref_t<T>>::value>> -struct requires_sequence_of_any_axis {}; - -template <class T, - class = std::enable_if_t<is_any_axis<mp11::mp_first<remove_cvref_t<T>>>::value>> -struct requires_axes {}; - -template <class T, class U, class = std::enable_if_t<std::is_convertible<T, U>::value>> -struct requires_convertible {}; - -template <class T> -auto make_default(const T& t) { - return static_if<has_allocator<T>>([](const auto& t) { return T(t.get_allocator()); }, - [](const auto&) { return T(); }, t); -} - -template <class T> -using tuple_size_t = typename std::tuple_size<T>::type; - -template <class T> -constexpr std::size_t get_size_impl(std::true_type, const T&) noexcept { - return std::tuple_size<T>::value; -} - -template <class T> -std::size_t get_size_impl(std::false_type, const T& t) noexcept { - using std::begin; - using std::end; - return static_cast<std::size_t>(std::distance(begin(t), end(t))); -} - -template <class T> -std::size_t get_size(const T& t) noexcept { - return get_size_impl(mp11::mp_valid<tuple_size_t, T>(), t); -} - -template <class T> -using buffer_size = - mp_eval_or<std::integral_constant<std::size_t, BOOST_HISTOGRAM_DETAIL_AXES_LIMIT>, - tuple_size_t, T>; - -template <class T, std::size_t N> -class sub_array : public std::array<T, N> { -public: - explicit sub_array(std::size_t s) : size_(s) {} - sub_array(std::size_t s, T value) : size_(s) { std::array<T, N>::fill(value); } - - // need to override both versions of std::array - auto end() noexcept { return std::array<T, N>::begin() + size_; } - auto end() const noexcept { return std::array<T, N>::begin() + size_; } - - auto size() const noexcept { return size_; } - -private: - std::size_t size_ = N; -}; - -template <class U, class T> -using stack_buffer = sub_array<U, buffer_size<T>::value>; - -template <class U, class T, class... Ts> -auto make_stack_buffer(const T& t, Ts&&... ts) { - return stack_buffer<U, T>(get_size(t), std::forward<Ts>(ts)...); -} - -template <class T> -constexpr bool relaxed_equal(const T& a, const T& b) noexcept { - return static_if<has_operator_equal<T>>( - [](const auto& a, const auto& b) { return a == b; }, - [](const auto&, const auto&) { return true; }, a, b); -} - -template <class T> -using get_scale_type_helper = typename T::value_type; - -template <class T> -using get_scale_type = mp_eval_or<T, detail::get_scale_type_helper, T>; - -struct one_unit {}; - -template <class T> -T operator*(T&& t, const one_unit&) { - return std::forward<T>(t); -} - -template <class T> -T operator/(T&& t, const one_unit&) { - return std::forward<T>(t); -} - -template <class T> -using get_unit_type_helper = typename T::unit_type; - -template <class T> -using get_unit_type = mp_eval_or<one_unit, detail::get_unit_type_helper, T>; - -template <class T, class R = get_scale_type<T>> -R get_scale(const T& t) { - return t / get_unit_type<T>(); -} - -template <class T, class Default> -using replace_default = mp11::mp_if<std::is_same<T, use_default>, Default, T>; - -template <class T, class U> -using is_convertible_helper = - mp11::mp_apply<mp11::mp_all, mp11::mp_transform<std::is_convertible, T, U>>; - -template <class T, class U> -using is_convertible = mp_eval_or<std::false_type, is_convertible_helper, T, U>; - -template <class T> -auto make_unsigned_impl(std::true_type, const T t) noexcept { - return static_cast<typename std::make_unsigned<T>::type>(t); -} - -template <class T> -auto make_unsigned_impl(std::false_type, const T t) noexcept { - return t; -} - -template <class T> -auto make_unsigned(const T t) noexcept { - return make_unsigned_impl(std::is_integral<T>{}, t); -} - -} // namespace detail -} // namespace histogram -} // namespace boost - -#endif diff --git a/boost/histogram/detail/noop_mutex.hpp b/boost/histogram/detail/noop_mutex.hpp new file mode 100644 index 0000000000..543284d099 --- /dev/null +++ b/boost/histogram/detail/noop_mutex.hpp @@ -0,0 +1,24 @@ +// Copyright 2019 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_DETAIL_NOOP_MUTEX_HPP +#define BOOST_HISTOGRAM_DETAIL_NOOP_MUTEX_HPP + +namespace boost { +namespace histogram { +namespace detail { + +struct noop_mutex { + bool try_lock() noexcept { return true; } + void lock() noexcept {} + void unlock() noexcept {} +}; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/operators.hpp b/boost/histogram/detail/operators.hpp new file mode 100644 index 0000000000..b781c495ad --- /dev/null +++ b/boost/histogram/detail/operators.hpp @@ -0,0 +1,135 @@ +// Copyright 2019 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_DETAIL_OPERATORS_HPP +#define BOOST_HISTOGRAM_DETAIL_OPERATORS_HPP + +#include <boost/histogram/detail/detect.hpp> +#include <boost/mp11/algorithm.hpp> +#include <boost/mp11/list.hpp> +#include <boost/mp11/utility.hpp> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T, class U> +using if_not_same_and_has_eq = + std::enable_if_t<(!std::is_same<T, U>::value && has_method_eq<T, U>::value), bool>; + +// totally_ordered is for types with a <= b == !(a > b) [floats with NaN violate this] +// Derived must implement <,== for symmetric form and <,>,== for non-symmetric. + +// partially_ordered is for types with a <= b == a < b || a == b [for floats with NaN] +// Derived must implement <,== for the symmetric form and <,>,== for non-symmetric. + +template <class T, class U> +struct mirrored { + friend bool operator<(const U& a, const T& b) noexcept { return b > a; } + friend bool operator>(const U& a, const T& b) noexcept { return b < a; } + friend bool operator==(const U& a, const T& b) noexcept { return b == a; } + friend bool operator<=(const U& a, const T& b) noexcept { return b >= a; } + friend bool operator>=(const U& a, const T& b) noexcept { return b <= a; } + friend bool operator!=(const U& a, const T& b) noexcept { return b != a; } +}; + +template <class T> +struct mirrored<T, void> { + template <class U> + friend if_not_same_and_has_eq<T, U> operator<(const U& a, const T& b) noexcept { + return b > a; + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator>(const U& a, const T& b) noexcept { + return b < a; + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator==(const U& a, const T& b) noexcept { + return b == a; + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator<=(const U& a, const T& b) noexcept { + return b >= a; + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator>=(const U& a, const T& b) noexcept { + return b <= a; + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator!=(const U& a, const T& b) noexcept { + return b != a; + } +}; + +template <class T> +struct mirrored<T, T> { + friend bool operator>(const T& a, const T& b) noexcept { return b.operator<(a); } +}; + +template <class T, class U> +struct equality { + friend bool operator!=(const T& a, const U& b) noexcept { return !a.operator==(b); } +}; + +template <class T> +struct equality<T, void> { + template <class U> + friend if_not_same_and_has_eq<T, U> operator!=(const T& a, const U& b) noexcept { + return !(a == b); + } +}; + +template <class T, class U> +struct totally_ordered_impl : equality<T, U>, mirrored<T, U> { + friend bool operator<=(const T& a, const U& b) noexcept { return !(a > b); } + friend bool operator>=(const T& a, const U& b) noexcept { return !(a < b); } +}; + +template <class T> +struct totally_ordered_impl<T, void> : equality<T, void>, mirrored<T, void> { + template <class U> + friend if_not_same_and_has_eq<T, U> operator<=(const T& a, const U& b) noexcept { + return !(a > b); + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator>=(const T& a, const U& b) noexcept { + return !(a < b); + } +}; + +template <class T, class... Ts> +using totally_ordered = mp11::mp_rename< + mp11::mp_product<totally_ordered_impl, mp11::mp_list<T>, mp11::mp_list<Ts...> >, + mp11::mp_inherit>; + +template <class T, class U> +struct partially_ordered_impl : equality<T, U>, mirrored<T, U> { + friend bool operator<=(const T& a, const U& b) noexcept { return a < b || a == b; } + friend bool operator>=(const T& a, const U& b) noexcept { return a > b || a == b; } +}; + +template <class T> +struct partially_ordered_impl<T, void> : equality<T, void>, mirrored<T, void> { + template <class U> + friend if_not_same_and_has_eq<T, U> operator<=(const T& a, const U& b) noexcept { + return a < b || a == b; + } + template <class U> + friend if_not_same_and_has_eq<T, U> operator>=(const T& a, const U& b) noexcept { + return a > b || a == b; + } +}; + +template <class T, class... Ts> +using partially_ordered = mp11::mp_rename< + mp11::mp_product<partially_ordered_impl, mp11::mp_list<T>, mp11::mp_list<Ts...> >, + mp11::mp_inherit>; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif // BOOST_HISTOGRAM_DETAIL_OPERATORS_HPP diff --git a/boost/histogram/detail/relaxed_equal.hpp b/boost/histogram/detail/relaxed_equal.hpp new file mode 100644 index 0000000000..123a05a20b --- /dev/null +++ b/boost/histogram/detail/relaxed_equal.hpp @@ -0,0 +1,28 @@ +// Copyright 2015-2019 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_DETAIL_RELAXED_EQUAL_HPP +#define BOOST_HISTOGRAM_DETAIL_RELAXED_EQUAL_HPP + +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/static_if.hpp> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T> +constexpr bool relaxed_equal(const T& a, const T& b) noexcept { + return static_if<has_operator_equal<T>>( + [](const auto& a, const auto& b) { return a == b; }, + [](const auto&, const auto&) { return true; }, a, b); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/replace_default.hpp b/boost/histogram/detail/replace_default.hpp new file mode 100644 index 0000000000..16c4c071c4 --- /dev/null +++ b/boost/histogram/detail/replace_default.hpp @@ -0,0 +1,25 @@ +// Copyright 2015-2019 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_DETAIL_REPLACE_DEFAULT_HPP +#define BOOST_HISTOGRAM_DETAIL_REPLACE_DEFAULT_HPP + +#include <boost/core/use_default.hpp> +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T, class Default> +using replace_default = + std::conditional_t<std::is_same<T, boost::use_default>::value, Default, T>; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/safe_comparison.hpp b/boost/histogram/detail/safe_comparison.hpp new file mode 100644 index 0000000000..3ac793ba44 --- /dev/null +++ b/boost/histogram/detail/safe_comparison.hpp @@ -0,0 +1,87 @@ +// Copyright 2019 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_DETAIL_SAFE_COMPARISON_HPP +#define BOOST_HISTOGRAM_DETAIL_SAFE_COMPARISON_HPP + +#include <boost/mp11/utility.hpp> +#include <boost/type.hpp> +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T> +auto make_unsigned(const T& t) noexcept { + static_assert(std::is_integral<T>::value, ""); + return static_cast<std::make_unsigned_t<T>>(t); +} + +template <class T> +using number_category = + mp11::mp_if<std::is_integral<T>, + mp11::mp_if<std::is_signed<T>, type<int>, type<unsigned>>, type<void>>; + +// version of std::equal_to<> which handles signed and unsigned integers correctly +struct safe_equal { + template <class T, class U> + bool operator()(const T& t, const U& u) const noexcept { + return impl(number_category<T>{}, number_category<U>{}, t, u); + } + + template <class C1, class C2, class T, class U> + bool impl(C1, C2, const T& t, const U& u) const noexcept { + return t == u; + } + + template <class T, class U> + bool impl(type<int>, type<unsigned>, const T& t, const U& u) const noexcept { + return t >= 0 && make_unsigned(t) == u; + } + + template <class T, class U> + bool impl(type<unsigned>, type<int>, const T& t, const U& u) const noexcept { + return impl(type<int>{}, type<unsigned>{}, u, t); + } +}; + +// version of std::less<> which handles signed and unsigned integers correctly +struct safe_less { + template <class T, class U> + bool operator()(const T& t, const U& u) const noexcept { + return impl(number_category<T>{}, number_category<U>{}, t, u); + } + + template <class C1, class C2, class T, class U> + bool impl(C1, C2, const T& t, const U& u) const noexcept { + return t < u; + } + + template <class T, class U> + bool impl(type<int>, type<unsigned>, const T& t, const U& u) const noexcept { + return t < 0 || make_unsigned(t) < u; + } + + template <class T, class U> + bool impl(type<unsigned>, type<int>, const T& t, const U& u) const noexcept { + return 0 < u && t < make_unsigned(u); + } +}; + +// version of std::greater<> which handles signed and unsigned integers correctly +struct safe_greater { + template <class T, class U> + bool operator()(const T& t, const U& u) const noexcept { + return safe_less()(u, t); + } +}; + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/static_if.hpp b/boost/histogram/detail/static_if.hpp new file mode 100644 index 0000000000..0f12a02229 --- /dev/null +++ b/boost/histogram/detail/static_if.hpp @@ -0,0 +1,46 @@ +// Copyright 2018-2019 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_DETAIL_STATIC_IF_HPP +#define BOOST_HISTOGRAM_DETAIL_STATIC_IF_HPP + +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T, class F, class... Args> +constexpr decltype(auto) static_if_impl( + std::true_type, T&& t, F&&, + Args&&... args) noexcept(noexcept(std::declval<T>()(std::declval<Args>()...))) { + return std::forward<T>(t)(std::forward<Args>(args)...); +} + +template <class T, class F, class... Args> +constexpr decltype(auto) static_if_impl( + std::false_type, T&&, F&& f, + Args&&... args) noexcept(noexcept(std::declval<F>()(std::declval<Args>()...))) { + return std::forward<F>(f)(std::forward<Args>(args)...); +} + +template <bool B, class... Ts> +constexpr decltype(auto) static_if_c(Ts&&... ts) noexcept( + noexcept(static_if_impl(std::integral_constant<bool, B>{}, std::declval<Ts>()...))) { + return static_if_impl(std::integral_constant<bool, B>{}, std::forward<Ts>(ts)...); +} + +template <class Bool, class... Ts> +constexpr decltype(auto) static_if(Ts&&... ts) noexcept( + noexcept(static_if_impl(Bool{}, std::declval<Ts>()...))) { + return static_if_impl(Bool{}, std::forward<Ts>(ts)...); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/try_cast.hpp b/boost/histogram/detail/try_cast.hpp new file mode 100644 index 0000000000..249f4e0317 --- /dev/null +++ b/boost/histogram/detail/try_cast.hpp @@ -0,0 +1,49 @@ +// Copyright 2019 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_DETAIL_TRY_CAST_HPP +#define BOOST_HISTOGRAM_DETAIL_TRY_CAST_HPP + +#include <boost/config.hpp> +#include <boost/core/demangle.hpp> +#include <boost/histogram/detail/cat.hpp> +#include <boost/histogram/detail/type_name.hpp> +#include <boost/mp11/integral.hpp> +#include <boost/throw_exception.hpp> +#include <stdexcept> +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { +template <class T, class E, class U> +BOOST_NORETURN T try_cast_impl(mp11::mp_int<0>, U&&) { + BOOST_THROW_EXCEPTION(E(cat("cannot cast ", type_name<T>(), " to ", type_name<U>()))); +} + +template <class T, class E, class U> +T try_cast_impl(mp11::mp_int<1>, U&& u) noexcept { + return static_cast<T>(u); +} + +template <class T, class E, class U> +decltype(auto) try_cast_impl(mp11::mp_int<2>, U&& u) noexcept { + return std::forward<U>(u); +} + +// cast fails at runtime with exception E instead of compile-time, T must be a value +template <class T, class E, class U> +decltype(auto) try_cast(U&& u) noexcept(std::is_convertible<U, T>::value) { + return try_cast_impl<T, E>(mp11::mp_int<(std::is_convertible<U, T>::value + + std::is_same<T, std::decay_t<U>>::value)>{}, + std::forward<U>(u)); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/tuple_slice.hpp b/boost/histogram/detail/tuple_slice.hpp new file mode 100644 index 0000000000..a48a10598c --- /dev/null +++ b/boost/histogram/detail/tuple_slice.hpp @@ -0,0 +1,34 @@ +// Copyright 2015-2019 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_DETAIL_TUPLE_SLICE_HPP +#define BOOST_HISTOGRAM_DETAIL_TUPLE_SLICE_HPP + +#include <boost/mp11/integer_sequence.hpp> +#include <tuple> +#include <type_traits> + +namespace boost { +namespace histogram { +namespace detail { + +template <std::size_t I, class T, std::size_t... K> +decltype(auto) tuple_slice_impl(T&& t, mp11::index_sequence<K...>) { + return std::forward_as_tuple(std::get<(I + K)>(std::forward<T>(t))...); +} + +template <std::size_t I, std::size_t N, class Tuple> +decltype(auto) tuple_slice(Tuple&& t) { + constexpr auto S = std::tuple_size<std::decay_t<Tuple>>::value; + static_assert(I + N <= S, "I, N must be a valid subset"); + return tuple_slice_impl<I>(std::forward<Tuple>(t), mp11::make_index_sequence<N>{}); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/detail/type_name.hpp b/boost/histogram/detail/type_name.hpp new file mode 100644 index 0000000000..25950bcaba --- /dev/null +++ b/boost/histogram/detail/type_name.hpp @@ -0,0 +1,51 @@ +// Copyright 2019 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_DETAIL_TYPE_NAME_HPP +#define BOOST_HISTOGRAM_DETAIL_TYPE_NAME_HPP + +#include <boost/core/typeinfo.hpp> +#include <boost/type.hpp> +#include <sstream> +#include <string> + +namespace boost { +namespace histogram { +namespace detail { + +template <class T> +std::ostream& type_name_impl(std::ostream& os, boost::type<T>) { + os << boost::core::demangled_name(BOOST_CORE_TYPEID(T)); + return os; +} + +template <class T> +std::ostream& type_name_impl(std::ostream& os, boost::type<const T>) { + return type_name_impl(os, boost::type<T>{}) << " const"; +} + +template <class T> +std::ostream& type_name_impl(std::ostream& os, boost::type<T&>) { + return type_name_impl(os, boost::type<T>{}) << "&"; +} + +template <class T> +std::ostream& type_name_impl(std::ostream& os, boost::type<T&&>) { + return type_name_impl(os, boost::type<T>{}) << "&&"; +} + +template <class T> +std::string type_name() { + std::ostringstream os; + type_name_impl(os, boost::type<T>{}); + return os.str(); +} + +} // namespace detail +} // namespace histogram +} // namespace boost + +#endif diff --git a/boost/histogram/fwd.hpp b/boost/histogram/fwd.hpp index 60f372e903..cc042bb7eb 100644 --- a/boost/histogram/fwd.hpp +++ b/boost/histogram/fwd.hpp @@ -1,4 +1,4 @@ -// Copyright 2015-2017 Hans Dembinski +// Copyright 2015-2019 Hans Dembinski // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt @@ -13,8 +13,7 @@ */ #include <boost/core/use_default.hpp> -#include <boost/histogram/detail/attribute.hpp> // BOOST_HISTOGRAM_DETAIL_NODISCARD -#include <string> +#include <boost/histogram/detail/attribute.hpp> // BOOST_HISTOGRAM_NODISCARD #include <vector> namespace boost { @@ -82,6 +81,14 @@ template <class Value = double> class mean; template <class Value = double> class weighted_mean; + +template <class T> +class thread_safe; + +template <class T> +struct is_thread_safe : std::false_type {}; +template <class T> +struct is_thread_safe<thread_safe<T>> : std::true_type {}; } // namespace accumulators struct unsafe_access; @@ -94,26 +101,26 @@ class storage_adaptor; #endif // BOOST_HISTOGRAM_DOXYGEN_INVOKED -/// Vector-like storage for fast zero-overhead access to cells +/// Vector-like storage for fast zero-overhead access to cells. template <class T, class A = std::allocator<T>> using dense_storage = storage_adaptor<std::vector<T, A>>; /// Default storage, optimized for unweighted histograms using default_storage = unlimited_storage<>; -/// Dense storage which tracks sums of weights and a variance estimate +/// Dense storage which tracks sums of weights and a variance estimate. using weight_storage = dense_storage<accumulators::weighted_sum<>>; -/// Dense storage which tracks means of samples in each cell +/// Dense storage which tracks means of samples in each cell. using profile_storage = dense_storage<accumulators::mean<>>; -/// Dense storage which tracks means of weighted samples in each cell +/// Dense storage which tracks means of weighted samples in each cell. using weighted_profile_storage = dense_storage<accumulators::weighted_mean<>>; #ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED template <class Axes, class Storage = default_storage> -class BOOST_HISTOGRAM_DETAIL_NODISCARD histogram; +class BOOST_HISTOGRAM_NODISCARD histogram; #endif } // namespace histogram diff --git a/boost/histogram/histogram.hpp b/boost/histogram/histogram.hpp index 2cb34feca1..75bc0df49f 100644 --- a/boost/histogram/histogram.hpp +++ b/boost/histogram/histogram.hpp @@ -9,15 +9,21 @@ #include <boost/histogram/detail/axes.hpp> #include <boost/histogram/detail/common_type.hpp> +#include <boost/histogram/detail/compressed_pair.hpp> #include <boost/histogram/detail/linearize.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/noop_mutex.hpp> +#include <boost/histogram/detail/static_if.hpp> #include <boost/histogram/fwd.hpp> +#include <boost/histogram/storage_adaptor.hpp> +#include <boost/histogram/unsafe_access.hpp> #include <boost/mp11/list.hpp> #include <boost/throw_exception.hpp> +#include <mutex> #include <stdexcept> #include <tuple> #include <type_traits> #include <utility> +#include <vector> namespace boost { namespace histogram { @@ -44,7 +50,7 @@ template <class Axes, class Storage> class histogram { public: static_assert(mp11::mp_size<Axes>::value > 0, "at least one axis required"); - static_assert(std::is_same<detail::remove_cvref_t<Storage>, Storage>::value, + static_assert(std::is_same<std::decay_t<Storage>, Storage>::value, "Storage may not be a reference or const or volatile"); public: @@ -56,53 +62,69 @@ public: using const_iterator = typename storage_type::const_iterator; histogram() = default; - histogram(const histogram& rhs) = default; - histogram(histogram&& rhs) = default; - histogram& operator=(const histogram& rhs) = default; - histogram& operator=(histogram&& rhs) = default; + histogram(const histogram& rhs) + : axes_(rhs.axes_), storage_and_mutex_(rhs.storage_and_mutex_.first()) {} + histogram(histogram&& rhs) + : axes_(std::move(rhs.axes_)) + , storage_and_mutex_(std::move(rhs.storage_and_mutex_.first())) {} + histogram& operator=(histogram&& rhs) { + if (this != &rhs) { + axes_ = std::move(rhs.axes_); + storage_and_mutex_.first() = std::move(rhs.storage_and_mutex_.first()); + } + return *this; + } + histogram& operator=(const histogram& rhs) { + if (this != &rhs) { + axes_ = rhs.axes_; + storage_and_mutex_.first() = rhs.storage_and_mutex_.first(); + } + return *this; + } template <class A, class S> - explicit histogram(histogram<A, S>&& rhs) : storage_(std::move(rhs.storage_)) { - detail::axes_assign(axes_, rhs.axes_); + explicit histogram(histogram<A, S>&& rhs) + : storage_and_mutex_(std::move(unsafe_access::storage(rhs))) { + detail::axes_assign(axes_, std::move(unsafe_access::axes(rhs))); } template <class A, class S> - explicit histogram(const histogram<A, S>& rhs) : storage_(rhs.storage_) { - detail::axes_assign(axes_, rhs.axes_); + explicit histogram(const histogram<A, S>& rhs) + : storage_and_mutex_(unsafe_access::storage(rhs)) { + detail::axes_assign(axes_, unsafe_access::axes(rhs)); } template <class A, class S> histogram& operator=(histogram<A, S>&& rhs) { - detail::axes_assign(axes_, std::move(rhs.axes_)); - storage_ = std::move(rhs.storage_); + detail::axes_assign(axes_, std::move(unsafe_access::axes(rhs))); + storage_and_mutex_.first() = std::move(unsafe_access::storage(rhs)); return *this; } template <class A, class S> histogram& operator=(const histogram<A, S>& rhs) { - detail::axes_assign(axes_, rhs.axes_); - storage_ = rhs.storage_; + detail::axes_assign(axes_, unsafe_access::axes(rhs)); + storage_and_mutex_.first() = unsafe_access::storage(rhs); return *this; } template <class A, class S> - histogram(A&& a, S&& s) : axes_(std::forward<A>(a)), storage_(std::forward<S>(s)) { - storage_.reset(detail::bincount(axes_)); + histogram(A&& a, S&& s) + : axes_(std::forward<A>(a)), storage_and_mutex_(std::forward<S>(s)) { + storage_and_mutex_.first().reset(detail::bincount(axes_)); } template <class A, class = detail::requires_axes<A>> explicit histogram(A&& a) : histogram(std::forward<A>(a), storage_type()) {} /// Number of axes (dimensions). - constexpr unsigned rank() const noexcept { - return static_cast<unsigned>(detail::get_size(axes_)); - } + constexpr unsigned rank() const noexcept { return detail::axes_rank(axes_); } /// Total number of bins (including underflow/overflow). - std::size_t size() const noexcept { return storage_.size(); } + std::size_t size() const noexcept { return storage_and_mutex_.first().size(); } /// Reset all bins to default initialized values. - void reset() { storage_.reset(storage_.size()); } + void reset() { storage_and_mutex_.first().reset(size()); } /// Get N-th axis using a compile-time number. /// This version is more efficient than the one accepting a run-time number. @@ -113,7 +135,7 @@ public: } /// Get N-th axis with run-time number. - /// Use version that accepts a compile-time number, if possible. + /// Prefer the version that accepts a compile-time number, if you can use it. decltype(auto) axis(unsigned i) const { detail::axis_index_is_valid(axes_, i); return detail::axis_get(axes_, i); @@ -131,13 +153,6 @@ public: not convertible to the value type accepted by the axis or passing the wrong number of arguments causes a throw of `std::invalid_argument`. - __Axis with multiple arguments__ - - If the histogram contains an axis which accepts a `std::tuple` of arguments, the - arguments for that axis need to passed as a `std::tuple`, for example, - `std::make_tuple(1.2, 2.3)`. If the histogram contains only this axis and no other, - the arguments can be passed directly. - __Optional weight__ An optional weight can be passed as the first or last argument @@ -151,89 +166,101 @@ public: [sample](boost/histogram/sample.html) helper function can pass one or more arguments to the storage element. If samples and weights are used together, they can be passed in any order at the beginning or end of the argument list. + + __Axis with multiple arguments__ + + If the histogram contains an axis which accepts a `std::tuple` of arguments, the + arguments for that axis need to passed as a `std::tuple`, for example, + `std::make_tuple(1.2, 2.3)`. If the histogram contains only this axis and no other, + the arguments can be passed directly. */ template <class... Ts> - auto operator()(const Ts&... ts) { - return operator()(std::make_tuple(ts...)); + iterator operator()(const Ts&... ts) { + return operator()(std::forward_as_tuple(ts...)); } /// Fill histogram with values, an optional weight, and/or a sample from a `std::tuple`. template <class... Ts> - auto operator()(const std::tuple<Ts...>& t) { - return detail::fill(storage_, axes_, t); + iterator operator()(const std::tuple<Ts...>& t) { + std::lock_guard<mutex_type> guard{storage_and_mutex_.second()}; + return detail::fill(axes_, storage_and_mutex_.first(), t); } - /// Access cell value at integral indices. - /** + /** Access cell value at integral indices. + You can pass indices as individual arguments, as a std::tuple of integers, or as an interable range of integers. Passing the wrong number of arguments causes a throw of std::invalid_argument. Passing an index which is out of bounds causes a throw of std::out_of_range. + + @param i index of first axis. + @param is indices of second, third, ... axes. + @returns reference to cell value. */ - template <class... Ts> - decltype(auto) at(axis::index_type t, Ts... ts) { - return at(std::forward_as_tuple(t, ts...)); + template <class... Indices> + decltype(auto) at(axis::index_type i, Indices... is) { + return at(std::forward_as_tuple(i, is...)); } /// Access cell value at integral indices (read-only). - /// @copydoc at(axis::index_type t, Ts... ts) - template <class... Ts> - decltype(auto) at(axis::index_type t, Ts... ts) const { - return at(std::forward_as_tuple(t, ts...)); + template <class... Indices> + decltype(auto) at(axis::index_type i, Indices... is) const { + return at(std::forward_as_tuple(i, is...)); } /// Access cell value at integral indices stored in `std::tuple`. - /// @copydoc at(axis::index_type t, Ts... ts) - template <typename... Ts> - decltype(auto) at(const std::tuple<Ts...>& t) { - const auto idx = detail::at(axes_, t); - if (!idx) BOOST_THROW_EXCEPTION(std::out_of_range("indices out of bounds")); - return storage_[*idx]; + template <typename... Indices> + decltype(auto) at(const std::tuple<Indices...>& is) { + const auto idx = detail::at(axes_, is); + if (!idx) + BOOST_THROW_EXCEPTION(std::out_of_range("at least one index out of bounds")); + return storage_and_mutex_.first()[*idx]; } /// Access cell value at integral indices stored in `std::tuple` (read-only). - /// @copydoc at(axis::index_type t, Ts... ts) - template <typename... Ts> - decltype(auto) at(const std::tuple<Ts...>& t) const { - const auto idx = detail::at(axes_, t); - if (!idx) BOOST_THROW_EXCEPTION(std::out_of_range("indices out of bounds")); - return storage_[*idx]; + template <typename... Indices> + decltype(auto) at(const std::tuple<Indices...>& is) const { + const auto idx = detail::at(axes_, is); + if (!idx) + BOOST_THROW_EXCEPTION(std::out_of_range("at least one index out of bounds")); + return storage_and_mutex_.first()[*idx]; } /// Access cell value at integral indices stored in iterable. - /// @copydoc at(axis::index_type t, Ts... ts) template <class Iterable, class = detail::requires_iterable<Iterable>> - decltype(auto) at(const Iterable& c) { - const auto idx = detail::at(axes_, c); - if (!idx) BOOST_THROW_EXCEPTION(std::out_of_range("indices out of bounds")); - return storage_[*idx]; + decltype(auto) at(const Iterable& is) { + const auto idx = detail::at(axes_, is); + if (!idx) + BOOST_THROW_EXCEPTION(std::out_of_range("at least one index out of bounds")); + return storage_and_mutex_.first()[*idx]; } /// Access cell value at integral indices stored in iterable (read-only). - /// @copydoc at(axis::index_type t, Ts... ts) template <class Iterable, class = detail::requires_iterable<Iterable>> - decltype(auto) at(const Iterable& c) const { - const auto idx = detail::at(axes_, c); - if (!idx) BOOST_THROW_EXCEPTION(std::out_of_range("indices out of bounds")); - return storage_[*idx]; + decltype(auto) at(const Iterable& is) const { + const auto idx = detail::at(axes_, is); + if (!idx) + BOOST_THROW_EXCEPTION(std::out_of_range("at least one index out of bounds")); + return storage_and_mutex_.first()[*idx]; } /// Access value at index (number for rank = 1, else `std::tuple` or iterable). - template <class T> - decltype(auto) operator[](const T& t) { - return at(t); + template <class Indices> + decltype(auto) operator[](const Indices& is) { + return at(is); } - /// @copydoc operator[] - template <class T> - decltype(auto) operator[](const T& t) const { - return at(t); + /// Access value at index (read-only). + template <class Indices> + decltype(auto) operator[](const Indices& is) const { + return at(is); } /// Equality operator, tests equality for all axes and the storage. template <class A, class S> bool operator==(const histogram<A, S>& rhs) const noexcept { - return detail::axes_equal(axes_, rhs.axes_) && storage_ == rhs.storage_; + return detail::axes_equal(axes_, unsafe_access::axes(rhs)) && + storage_and_mutex_.first() == unsafe_access::storage(rhs); } /// Negation of the equality operator. @@ -243,54 +270,54 @@ public: } /// Add values of another histogram. - template <class A, class S> + template <class A, class S, + class = std::enable_if_t<detail::has_operator_radd< + value_type, typename histogram<A, S>::value_type>::value>> histogram& operator+=(const histogram<A, S>& rhs) { - static_assert(detail::has_operator_radd<value_type, - typename histogram<A, S>::value_type>::value, - "cell value does not support adding value of right-hand-side"); - if (!detail::axes_equal(axes_, rhs.axes_)) + if (!detail::axes_equal(axes_, unsafe_access::axes(rhs))) BOOST_THROW_EXCEPTION(std::invalid_argument("axes of histograms differ")); - auto rit = rhs.storage_.begin(); - std::for_each(storage_.begin(), storage_.end(), [&rit](auto&& x) { x += *rit++; }); + auto rit = unsafe_access::storage(rhs).begin(); + auto& s = storage_and_mutex_.first(); + std::for_each(s.begin(), s.end(), [&rit](auto&& x) { x += *rit++; }); return *this; } /// Subtract values of another histogram. - template <class A, class S> + template <class A, class S, + class = std::enable_if_t<detail::has_operator_rsub< + value_type, typename histogram<A, S>::value_type>::value>> histogram& operator-=(const histogram<A, S>& rhs) { - static_assert(detail::has_operator_rsub<value_type, - typename histogram<A, S>::value_type>::value, - "cell value does not support subtracting value of right-hand-side"); - if (!detail::axes_equal(axes_, rhs.axes_)) + if (!detail::axes_equal(axes_, unsafe_access::axes(rhs))) BOOST_THROW_EXCEPTION(std::invalid_argument("axes of histograms differ")); - auto rit = rhs.storage_.begin(); - std::for_each(storage_.begin(), storage_.end(), [&rit](auto&& x) { x -= *rit++; }); + auto rit = unsafe_access::storage(rhs).begin(); + auto& s = storage_and_mutex_.first(); + std::for_each(s.begin(), s.end(), [&rit](auto&& x) { x -= *rit++; }); return *this; } /// Multiply by values of another histogram. - template <class A, class S> + template <class A, class S, + class = std::enable_if_t<detail::has_operator_rmul< + value_type, typename histogram<A, S>::value_type>::value>> histogram& operator*=(const histogram<A, S>& rhs) { - static_assert(detail::has_operator_rmul<value_type, - typename histogram<A, S>::value_type>::value, - "cell value does not support multiplying by value of right-hand-side"); - if (!detail::axes_equal(axes_, rhs.axes_)) + if (!detail::axes_equal(axes_, unsafe_access::axes(rhs))) BOOST_THROW_EXCEPTION(std::invalid_argument("axes of histograms differ")); - auto rit = rhs.storage_.begin(); - std::for_each(storage_.begin(), storage_.end(), [&rit](auto&& x) { x *= *rit++; }); + auto rit = unsafe_access::storage(rhs).begin(); + auto& s = storage_and_mutex_.first(); + std::for_each(s.begin(), s.end(), [&rit](auto&& x) { x *= *rit++; }); return *this; } /// Divide by values of another histogram. - template <class A, class S> + template <class A, class S, + class = std::enable_if_t<detail::has_operator_rdiv< + value_type, typename histogram<A, S>::value_type>::value>> histogram& operator/=(const histogram<A, S>& rhs) { - static_assert(detail::has_operator_rdiv<value_type, - typename histogram<A, S>::value_type>::value, - "cell value does not support dividing by value of right-hand-side"); - if (!detail::axes_equal(axes_, rhs.axes_)) + if (!detail::axes_equal(axes_, unsafe_access::axes(rhs))) BOOST_THROW_EXCEPTION(std::invalid_argument("axes of histograms differ")); - auto rit = rhs.storage_.begin(); - std::for_each(storage_.begin(), storage_.end(), [&rit](auto&& x) { x /= *rit++; }); + auto rit = unsafe_access::storage(rhs).begin(); + auto& s = storage_and_mutex_.first(); + std::for_each(s.begin(), s.end(), [&rit](auto&& x) { x /= *rit++; }); return *this; } @@ -304,7 +331,7 @@ public: [](storage_type& s, auto x) { for (auto&& si : s) si *= x; }, - storage_, x); + storage_and_mutex_.first(), x); return *this; } @@ -316,67 +343,101 @@ public: } /// Return value iterator to the beginning of the histogram. - iterator begin() noexcept { return storage_.begin(); } + iterator begin() noexcept { return storage_and_mutex_.first().begin(); } /// Return value iterator to the end in the histogram. - iterator end() noexcept { return storage_.end(); } + iterator end() noexcept { return storage_and_mutex_.first().end(); } /// Return value iterator to the beginning of the histogram (read-only). - const_iterator begin() const noexcept { return storage_.begin(); } + const_iterator begin() const noexcept { return storage_and_mutex_.first().begin(); } /// Return value iterator to the end in the histogram (read-only). - const_iterator end() const noexcept { return storage_.end(); } + const_iterator end() const noexcept { return storage_and_mutex_.first().end(); } /// Return value iterator to the beginning of the histogram (read-only). - const_iterator cbegin() const noexcept { return storage_.begin(); } + const_iterator cbegin() const noexcept { return begin(); } /// Return value iterator to the end in the histogram (read-only). - const_iterator cend() const noexcept { return storage_.end(); } + const_iterator cend() const noexcept { return end(); } private: axes_type axes_; - storage_type storage_; - template <class A, class S> - friend class histogram; + using mutex_type = mp11::mp_if_c<(storage_type::has_threading_support && + detail::has_growing_axis<axes_type>::value), + std::mutex, detail::noop_mutex>; + + detail::compressed_pair<storage_type, mutex_type> storage_and_mutex_; + friend struct unsafe_access; }; +/** + Pairwise add cells of two histograms and return histogram with the sum. + + The returned histogram type is the most efficient and safest one constructible from the + inputs, if they are not the same type. If one histogram has a tuple axis, the result has + a tuple axis. The chosen storage is the one with the larger dynamic range. +*/ template <class A1, class S1, class A2, class S2> auto operator+(const histogram<A1, S1>& a, const histogram<A2, S2>& b) { auto r = histogram<detail::common_axes<A1, A2>, detail::common_storage<S1, S2>>(a); return r += b; } +/** Pairwise multiply cells of two histograms and return histogram with the product. + + For notes on the returned histogram type, see operator+. +*/ template <class A1, class S1, class A2, class S2> auto operator*(const histogram<A1, S1>& a, const histogram<A2, S2>& b) { auto r = histogram<detail::common_axes<A1, A2>, detail::common_storage<S1, S2>>(a); return r *= b; } +/** Pairwise subtract cells of two histograms and return histogram with the difference. + + For notes on the returned histogram type, see operator+. +*/ template <class A1, class S1, class A2, class S2> auto operator-(const histogram<A1, S1>& a, const histogram<A2, S2>& b) { auto r = histogram<detail::common_axes<A1, A2>, detail::common_storage<S1, S2>>(a); return r -= b; } +/** Pairwise divide cells of two histograms and return histogram with the quotient. + + For notes on the returned histogram type, see operator+. +*/ template <class A1, class S1, class A2, class S2> auto operator/(const histogram<A1, S1>& a, const histogram<A2, S2>& b) { auto r = histogram<detail::common_axes<A1, A2>, detail::common_storage<S1, S2>>(a); return r /= b; } +/** Multiply all cells of the histogram by a number and return a new histogram. + + If the original histogram has integer cells, the result has double cells. +*/ template <class A, class S> auto operator*(const histogram<A, S>& h, double x) { auto r = histogram<A, detail::common_storage<S, dense_storage<double>>>(h); return r *= x; } +/** Multiply all cells of the histogram by a number and return a new histogram. + + If the original histogram has integer cells, the result has double cells. +*/ template <class A, class S> auto operator*(double x, const histogram<A, S>& h) { return h * x; } +/** Divide all cells of the histogram by a number and return a new histogram. + + If the original histogram has integer cells, the result has double cells. +*/ template <class A, class S> auto operator/(const histogram<A, S>& h, double x) { return h * (1.0 / x); @@ -385,29 +446,32 @@ auto operator/(const histogram<A, S>& h, double x) { #if __cpp_deduction_guides >= 201606 template <class Axes> -histogram(Axes&& axes)->histogram<detail::remove_cvref_t<Axes>, default_storage>; +histogram(Axes&& axes)->histogram<std::decay_t<Axes>, default_storage>; template <class Axes, class Storage> histogram(Axes&& axes, Storage&& storage) - ->histogram<detail::remove_cvref_t<Axes>, detail::remove_cvref_t<Storage>>; + ->histogram<std::decay_t<Axes>, std::decay_t<Storage>>; #endif -/// Helper function to mark argument as weight. -/// @param t argument to be forward to the histogram. +/** Helper function to mark argument as weight. + + @param t argument to be forward to the histogram. +*/ template <typename T> auto weight(T&& t) noexcept { return weight_type<T>{std::forward<T>(t)}; } -/// Helper function to mark arguments as sample. -/// @param ts arguments to be forwarded to the accumulator. +/** Helper function to mark arguments as sample. + + @param ts arguments to be forwarded to the accumulator. +*/ template <typename... Ts> auto sample(Ts&&... ts) noexcept { return sample_type<std::tuple<Ts...>>{std::forward_as_tuple(std::forward<Ts>(ts)...)}; } -#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED template <class T> struct weight_type { T value; @@ -417,7 +481,6 @@ template <class T> struct sample_type { T value; }; -#endif } // namespace histogram } // namespace boost diff --git a/boost/histogram/indexed.hpp b/boost/histogram/indexed.hpp index 1c31cafcfe..3b4ec823e4 100644 --- a/boost/histogram/indexed.hpp +++ b/boost/histogram/indexed.hpp @@ -7,21 +7,20 @@ #ifndef BOOST_HISTOGRAM_INDEXED_HPP #define BOOST_HISTOGRAM_INDEXED_HPP +#include <array> #include <boost/histogram/axis/traits.hpp> #include <boost/histogram/detail/attribute.hpp> #include <boost/histogram/detail/axes.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/iterator_adaptor.hpp> +#include <boost/histogram/detail/operators.hpp> #include <boost/histogram/fwd.hpp> -#include <boost/histogram/unsafe_access.hpp> -#include <boost/iterator/iterator_adaptor.hpp> #include <type_traits> #include <utility> namespace boost { namespace histogram { -/** - Coverage mode of the indexed range generator. +/** Coverage mode of the indexed range generator. Defines options for the iteration strategy. */ @@ -30,185 +29,315 @@ enum class coverage { all, /*!< iterate over all bins, including underflow and overflow */ }; -/// Range over histogram bins with multi-dimensional index. +/** Input iterator range over histogram bins with multi-dimensional index. + + The iterator returned by begin() can only be incremented. begin() may only be called + once, calling it a second time returns the end() iterator. If several copies of the + input iterators exist, the other copies become invalid if one of them is incremented. +*/ template <class Histogram> -class BOOST_HISTOGRAM_DETAIL_NODISCARD indexed_range { - using max_dim = mp11::mp_size_t< - detail::buffer_size<typename detail::remove_cvref_t<Histogram>::axes_type>::value>; - using value_iterator = decltype(std::declval<Histogram>().begin()); - struct cache_item { - int idx, begin, end, extent; - }; +class BOOST_HISTOGRAM_NODISCARD indexed_range { +private: + using histogram_type = Histogram; + static constexpr std::size_t buffer_size = + detail::buffer_size<typename std::remove_const_t<histogram_type>::axes_type>::value; public: - /** - Pointer-like class to access value and index of current cell. - - Its methods allow one to query the current indices and bins. Furthermore, it acts like - a pointer to the cell value. + using value_iterator = decltype(std::declval<histogram_type>().begin()); + using value_reference = typename value_iterator::reference; + using value_type = typename value_iterator::value_type; + + class iterator; + using range_iterator = iterator; ///< deprecated + + /** Pointer-like class to access value and index of current cell. + + Its methods provide access to the current indices and bins and it acts like a pointer + to the cell value. To interoperate with the algorithms of the standard library, the + accessor is implicitly convertible to a cell value. Assignments and comparisons + are passed through to the cell. The accessor is coupled to its parent + iterator. Moving the parent iterator forward also updates the linked + accessor. Accessors are not copyable. They cannot be stored in containers, but + range_iterators can be stored. */ - class accessor { + class accessor : detail::mirrored<accessor, void> { public: /// Array-like view into the current multi-dimensional index. class index_view { + using index_pointer = const typename iterator::index_data*; + public: -#ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED - class index_iterator - : public boost::iterator_adaptor<index_iterator, const cache_item*> { + using const_reference = const axis::index_type&; + using reference = const_reference; ///< deprecated + + /// implementation detail + class const_iterator + : public detail::iterator_adaptor<const_iterator, index_pointer, + const_reference> { public: - index_iterator(const cache_item* i) : index_iterator::iterator_adaptor_(i) {} - decltype(auto) operator*() const noexcept { return index_iterator::base()->idx; } + const_reference operator*() const noexcept { return const_iterator::base()->idx; } + + private: + explicit const_iterator(index_pointer i) noexcept + : const_iterator::iterator_adaptor_(i) {} + + friend class index_view; }; -#endif - auto begin() const noexcept { return index_iterator(begin_); } - auto end() const noexcept { return index_iterator(end_); } - auto size() const noexcept { return static_cast<std::size_t>(end_ - begin_); } - int operator[](unsigned d) const noexcept { return begin_[d].idx; } - int at(unsigned d) const { return begin_[d].idx; } + const_iterator begin() const noexcept { return const_iterator{begin_}; } + const_iterator end() const noexcept { return const_iterator{end_}; } + std::size_t size() const noexcept { + return static_cast<std::size_t>(end_ - begin_); + } + const_reference operator[](unsigned d) const noexcept { return begin_[d].idx; } + const_reference at(unsigned d) const { return begin_[d].idx; } private: - index_view(const cache_item* b, const cache_item* e) : begin_(b), end_(e) {} - const cache_item *begin_, *end_; + /// implementation detail + index_view(index_pointer b, index_pointer e) : begin_(b), end_(e) {} + + index_pointer begin_, end_; friend class accessor; }; - /// Returns the cell value. - decltype(auto) operator*() const noexcept { return *iter_; } - /// Returns the cell value. - decltype(auto) get() const noexcept { return *iter_; } + // assignment is pass-through + accessor& operator=(const accessor& o) { + get() = o.get(); + return *this; + } + + // assignment is pass-through + template <class T> + accessor& operator=(const T& x) { + get() = x; + return *this; + } + + /// Returns the cell reference. + value_reference get() const noexcept { return *(iter_.iter_); } + /// @copydoc get() + value_reference operator*() const noexcept { return get(); } /// Access fields and methods of the cell object. - decltype(auto) operator-> () const noexcept { return iter_; } + value_iterator operator->() const noexcept { return iter_.iter_; } /// Access current index. /// @param d axis dimension. - int index(unsigned d = 0) const noexcept { return parent_.cache_[d].idx; } + axis::index_type index(unsigned d = 0) const noexcept { + return iter_.indices_[d].idx; + } /// Access indices as an iterable range. - auto indices() const noexcept { - return index_view(parent_.cache_, parent_.cache_ + parent_.hist_.rank()); + index_view indices() const noexcept { + BOOST_ASSERT(iter_.indices_.hist_); + return {iter_.indices_.data(), + iter_.indices_.data() + iter_.indices_.hist_->rank()}; } /// Access current bin. /// @tparam N axis dimension. template <unsigned N = 0> decltype(auto) bin(std::integral_constant<unsigned, N> = {}) const { - return parent_.hist_.axis(std::integral_constant<unsigned, N>()).bin(index(N)); + BOOST_ASSERT(iter_.indices_.hist_); + return iter_.indices_.hist_->axis(std::integral_constant<unsigned, N>()) + .bin(index(N)); } /// Access current bin. /// @param d axis dimension. - decltype(auto) bin(unsigned d) const { return parent_.hist_.axis(d).bin(index(d)); } + decltype(auto) bin(unsigned d) const { + BOOST_ASSERT(iter_.indices_.hist_); + return iter_.indices_.hist_->axis(d).bin(index(d)); + } - /** - Computes density in current cell. + /** Computes density in current cell. The density is computed as the cell value divided by the product of bin widths. Axes without bin widths, like axis::category, are treated as having unit bin with. */ double density() const { + BOOST_ASSERT(iter_.indices_.hist_); double x = 1; - auto it = parent_.cache_; - parent_.hist_.for_each_axis([&](const auto& a) { - const auto w = axis::traits::width_as<double>(a, it++->idx); + unsigned d = 0; + iter_.indices_.hist_->for_each_axis([&](const auto& a) { + const auto w = axis::traits::width_as<double>(a, this->index(d++)); x *= w ? w : 1; }); - return *iter_ / x; + return get() / x; } + // forward all comparison operators to the value + bool operator<(const accessor& o) noexcept { return get() < o.get(); } + bool operator>(const accessor& o) noexcept { return get() > o.get(); } + bool operator==(const accessor& o) noexcept { return get() == o.get(); } + bool operator!=(const accessor& o) noexcept { return get() != o.get(); } + bool operator<=(const accessor& o) noexcept { return get() <= o.get(); } + bool operator>=(const accessor& o) noexcept { return get() >= o.get(); } + + template <class U> + bool operator<(const U& o) const noexcept { + return get() < o; + } + + template <class U> + bool operator>(const U& o) const noexcept { + return get() > o; + } + + template <class U> + bool operator==(const U& o) const noexcept { + return get() == o; + } + + template <class U> + bool operator!=(const U& o) const noexcept { + return get() != o; + } + + template <class U> + bool operator<=(const U& o) const noexcept { + return get() <= o; + } + + template <class U> + bool operator>=(const U& o) const noexcept { + return get() >= o; + } + + operator value_type() const noexcept { return get(); } + private: - accessor(indexed_range& p, value_iterator i) : parent_(p), iter_(i) {} - indexed_range& parent_; - value_iterator iter_; - friend class indexed_range; + accessor(iterator& i) noexcept : iter_(i) {} + + accessor(const accessor&) = default; // only callable by indexed_range::iterator + + iterator& iter_; + + friend class iterator; }; - class range_iterator - : public boost::iterator_adaptor<range_iterator, value_iterator, accessor, - std::forward_iterator_tag, accessor> { + /// implementation detail + class iterator { public: - accessor operator*() const noexcept { return {*parent_, range_iterator::base()}; } + using value_type = typename indexed_range::value_type; + using reference = accessor; private: - range_iterator(indexed_range* p, value_iterator i) noexcept - : range_iterator::iterator_adaptor_(i), parent_(p) {} + struct pointer_proxy { + reference* operator->() noexcept { return std::addressof(ref_); } + reference ref_; + }; + + public: + using pointer = pointer_proxy; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + reference operator*() noexcept { return *this; } + pointer operator->() noexcept { return pointer_proxy{operator*()}; } - void increment() noexcept { + iterator& operator++() { + BOOST_ASSERT(indices_.hist_); std::size_t stride = 1; - auto c = parent_->cache_; + auto c = indices_.begin(); ++c->idx; - ++range_iterator::base_reference(); - while (c->idx == c->end && (c != (parent_->cache_ + parent_->hist_.rank() - 1))) { + ++iter_; + while (c->idx == c->end && (c != (indices_.end() - 1))) { c->idx = c->begin; - range_iterator::base_reference() -= (c->end - c->begin) * stride; + iter_ -= (c->end - c->begin) * stride; stride *= c->extent; ++c; ++c->idx; - range_iterator::base_reference() += stride; + iter_ += stride; } + return *this; } - mutable indexed_range* parent_; + iterator operator++(int) { + auto prev = *this; + operator++(); + return prev; + } + + bool operator==(const iterator& x) const noexcept { return iter_ == x.iter_; } + bool operator!=(const iterator& x) const noexcept { return !operator==(x); } + + private: + iterator(histogram_type* h) : iter_(h->begin()), indices_(h) {} + + value_iterator iter_; + + struct index_data { + axis::index_type idx, begin, end, extent; + }; + + struct indices_t : std::array<index_data, buffer_size> { + using base_type = std::array<index_data, buffer_size>; + + indices_t(histogram_type* h) noexcept : hist_{h} {} + + constexpr auto end() noexcept { return base_type::begin() + hist_->rank(); } + constexpr auto end() const noexcept { return base_type::begin() + hist_->rank(); } + histogram_type* hist_; + } indices_; - friend class boost::iterator_core_access; friend class indexed_range; }; - indexed_range(Histogram& h, coverage c) - : hist_(h), cover_all_(c == coverage::all), begin_(hist_.begin()), end_(begin_) { - auto ca = cache_; - const auto clast = ca + hist_.rank() - 1; + indexed_range(histogram_type& hist, coverage cov) : begin_(&hist), end_(&hist) { std::size_t stride = 1; - h.for_each_axis([&, this](const auto& a) { - using opt = axis::traits::static_options<decltype(a)>; - constexpr int under = opt::test(axis::option::underflow); - constexpr int over = opt::test(axis::option::overflow); - const auto size = a.size(); - - ca->extent = size + under + over; - // -1 if underflow and cover all, else 0 - ca->begin = cover_all_ ? -under : 0; - // size + 1 if overflow and cover all, else size - ca->end = cover_all_ ? size + over : size; - ca->idx = ca->begin; - - begin_ += (ca->begin + under) * stride; - if (ca < clast) - end_ += (ca->begin + under) * stride; - else - end_ += (ca->end + under) * stride; - - stride *= ca->extent; - ++ca; - }); + auto ca = begin_.indices_.begin(); + const auto clast = ca + begin_.indices_.hist_->rank() - 1; + begin_.indices_.hist_->for_each_axis( + [ca, clast, cov, &stride, this](const auto& a) mutable { + using opt = axis::traits::static_options<decltype(a)>; + constexpr int under = opt::test(axis::option::underflow); + constexpr int over = opt::test(axis::option::overflow); + const auto size = a.size(); + + ca->extent = size + under + over; + // -1 if underflow and cover all, else 0 + ca->begin = cov == coverage::all ? -under : 0; + // size + 1 if overflow and cover all, else size + ca->end = cov == coverage::all ? size + over : size; + ca->idx = ca->begin; + + begin_.iter_ += (ca->begin + under) * stride; + end_.iter_ += ((ca < clast ? ca->begin : ca->end) + under) * stride; + + stride *= ca->extent; + ++ca; + }); } - range_iterator begin() noexcept { return {this, begin_}; } - range_iterator end() noexcept { return {nullptr, end_}; } + iterator begin() noexcept { return begin_; } + iterator end() noexcept { return end_; } private: - Histogram& hist_; - const bool cover_all_; - value_iterator begin_, end_; - mutable cache_item cache_[max_dim::value]; + iterator begin_, end_; }; -/** - Generates a range over the histogram entries. +/** Generates an indexed range of <a + href="https://en.cppreference.com/w/cpp/named_req/ForwardIterator">forward iterators</a> + over the histogram cells. Use this in a range-based for loop: ``` - for (auto x : indexed(hist)) { ... } + for (auto&& x : indexed(hist)) { ... } ``` - The iterators dereference to an indexed_range::accessor, which has methods to query the - current indices and bins, and acts like a pointer to the cell value. + This generates an optimized loop which is nearly always faster than a hand-written loop + over the histogram cells. The iterators dereference to an indexed_range::accessor, which + has methods to query the current indices and bins and acts like a pointer to the cell + value. The returned iterators are forward iterators. They can be stored in a container, + but may not be used after the life-time of the histogram ends. + + @returns indexed_range @param hist Reference to the histogram. @param cov Iterate over all or only inner bins (optional, default: inner). */ -template <typename Histogram> +template <class Histogram> auto indexed(Histogram&& hist, coverage cov = coverage::inner) { return indexed_range<std::remove_reference_t<Histogram>>{std::forward<Histogram>(hist), cov}; diff --git a/boost/histogram/make_histogram.hpp b/boost/histogram/make_histogram.hpp index a777b223d9..818fc1893f 100644 --- a/boost/histogram/make_histogram.hpp +++ b/boost/histogram/make_histogram.hpp @@ -13,7 +13,6 @@ */ #include <boost/histogram/accumulators/weighted_sum.hpp> -#include <boost/histogram/detail/meta.hpp> #include <boost/histogram/histogram.hpp> #include <boost/histogram/storage_adaptor.hpp> #include <boost/histogram/unlimited_storage.hpp> // = default_storage @@ -30,10 +29,12 @@ namespace histogram { @param axis First axis instance. @param axes Other axis instances. */ -template <class Storage, class Axis, class... Axes, class = detail::requires_axis<Axis>> +template <class Storage, class Axis, class... Axes, + class = detail::requires_storage_or_adaptible<Storage>, + class = detail::requires_axis<Axis>> auto make_histogram_with(Storage&& storage, Axis&& axis, Axes&&... axes) { auto a = std::make_tuple(std::forward<Axis>(axis), std::forward<Axes>(axes)...); - using U = detail::remove_cvref_t<Storage>; + using U = std::decay_t<Storage>; using S = mp11::mp_if<detail::is_storage<U>, U, storage_adaptor<U>>; return histogram<decltype(a), S>(std::move(a), S(std::forward<Storage>(storage))); } @@ -66,11 +67,12 @@ auto make_weighted_histogram(Axis&& axis, Axes&&... axes) { @param iterable Iterable range of axis objects. */ template <class Storage, class Iterable, + class = detail::requires_storage_or_adaptible<Storage>, class = detail::requires_sequence_of_any_axis<Iterable>> auto make_histogram_with(Storage&& storage, Iterable&& iterable) { - using U = detail::remove_cvref_t<Storage>; + using U = std::decay_t<Storage>; using S = mp11::mp_if<detail::is_storage<U>, U, storage_adaptor<U>>; - using It = detail::remove_cvref_t<Iterable>; + using It = std::decay_t<Iterable>; using A = mp11::mp_if<detail::is_indexable_container<It>, It, std::vector<mp11::mp_first<It>>>; return histogram<A, S>(std::forward<Iterable>(iterable), @@ -101,9 +103,11 @@ auto make_weighted_histogram(Iterable&& iterable) { @param begin Iterator to range of axis objects. @param end Iterator to range of axis objects. */ -template <class Storage, class Iterator, class = detail::requires_iterator<Iterator>> +template <class Storage, class Iterator, + class = detail::requires_storage_or_adaptible<Storage>, + class = detail::requires_iterator<Iterator>> auto make_histogram_with(Storage&& storage, Iterator begin, Iterator end) { - using T = detail::remove_cvref_t<decltype(*begin)>; + using T = std::decay_t<decltype(*begin)>; return make_histogram_with(std::forward<Storage>(storage), std::vector<T>(begin, end)); } diff --git a/boost/histogram/ostream.hpp b/boost/histogram/ostream.hpp index bef4a78e30..e38a0600cd 100644 --- a/boost/histogram/ostream.hpp +++ b/boost/histogram/ostream.hpp @@ -12,6 +12,17 @@ #include <boost/histogram/fwd.hpp> #include <iosfwd> +/** + \file boost/histogram/ostream.hpp + + A simple streaming operator for the histogram type. The text representation is + rudimentary and not guaranteed to be stable between versions of Boost.Histogram. This + header is not included by any other header and must be explicitly included to use the + streaming operator. + + To you use your own, simply include your own implementation instead of this header. + */ + #ifndef BOOST_HISTOGRAM_DOXYGEN_INVOKED namespace boost { diff --git a/boost/histogram/serialization.hpp b/boost/histogram/serialization.hpp index 832c3cc6be..0f4c93acd6 100644 --- a/boost/histogram/serialization.hpp +++ b/boost/histogram/serialization.hpp @@ -7,6 +7,7 @@ #ifndef BOOST_HISTOGRAM_SERIALIZATION_HPP #define BOOST_HISTOGRAM_SERIALIZATION_HPP +#include <boost/archive/archive_exception.hpp> #include <boost/assert.hpp> #include <boost/histogram/accumulators/mean.hpp> #include <boost/histogram/accumulators/sum.hpp> @@ -21,12 +22,15 @@ #include <boost/histogram/storage_adaptor.hpp> #include <boost/histogram/unlimited_storage.hpp> #include <boost/histogram/unsafe_access.hpp> +#include <boost/mp11/algorithm.hpp> #include <boost/mp11/tuple.hpp> #include <boost/serialization/array.hpp> #include <boost/serialization/map.hpp> #include <boost/serialization/nvp.hpp> +#include <boost/serialization/serialization.hpp> +#include <boost/serialization/split_member.hpp> #include <boost/serialization/string.hpp> -#include <boost/serialization/variant.hpp> +#include <boost/serialization/throw_exception.hpp> #include <boost/serialization/vector.hpp> #include <tuple> #include <type_traits> @@ -83,6 +87,13 @@ void weighted_mean<RealType>::serialize(Archive& ar, unsigned /* version */) { ar& serialization::make_nvp("sum_of_weighted_deltas_squared", sum_of_weighted_deltas_squared_); } + +template <class Archive, class T> +void serialize(Archive& ar, thread_safe<T>& t, unsigned /* version */) { + T value = t; + ar& serialization::make_nvp("value", value); + t = value; +} } // namespace accumulators namespace axis { @@ -138,10 +149,51 @@ void category<T, M, O, A>::serialize(Archive& ar, unsigned /* version */) { ar& serialization::make_nvp("meta", vec_meta_.second()); } -template <class... Ts> -template <class Archive> -void variant<Ts...>::serialize(Archive& ar, unsigned /* version */) { - ar& serialization::make_nvp("variant", impl); +// variant_proxy is a workaround to remain backward compatible in the serialization +// format. It uses only the public interface of axis::variant for serialization and +// therefore works independently of the underlying variant implementation. +template <class Variant> +struct variant_proxy { + Variant& v; + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + template <class Archive> + void save(Archive& ar, unsigned /* version */) const { + visit( + [&ar](auto& value) { + using T = std::decay_t<decltype(value)>; + int which = static_cast<int>(mp11::mp_find<Variant, T>::value); + ar << serialization::make_nvp("which", which); + ar << serialization::make_nvp("value", value); + }, + v); + } + + template <class Archive> + void load(Archive& ar, unsigned /* version */) { + int which = 0; + ar >> serialization::make_nvp("which", which); + constexpr unsigned N = mp11::mp_size<Variant>::value; + if (which < 0 || static_cast<unsigned>(which) >= N) + // throw on invalid which, which >= N can happen if type was removed from variant + serialization::throw_exception( + archive::archive_exception(archive::archive_exception::unsupported_version)); + mp11::mp_with_index<N>(static_cast<unsigned>(which), [&ar, this](auto i) { + using T = mp11::mp_at_c<Variant, i>; + T value; + ar >> serialization::make_nvp("value", value); + v = std::move(value); + T* new_address = get_if<T>(&v); + ar.reset_object_address(new_address, &value); + }); + } +}; + +template <class Archive, class... Ts> +void serialize(Archive& ar, variant<Ts...>& v, unsigned /* version */) { + variant_proxy<variant<Ts...>> p{v}; + ar& serialization::make_nvp("variant", p); } } // namespace axis @@ -165,35 +217,37 @@ void serialize(Archive& ar, map_impl<T>& impl, unsigned /* version */) { } template <class Archive, class Allocator> -void serialize(Archive& ar, mp_int<Allocator>& x, unsigned /* version */) { +void serialize(Archive& ar, large_int<Allocator>& x, unsigned /* version */) { ar& serialization::make_nvp("data", x.data); } } // namespace detail template <class Archive, class T> -void serialize(Archive& ar, storage_adaptor<T>& s, unsigned /* version */) { - ar& serialization::make_nvp("impl", static_cast<detail::storage_adaptor_impl<T>&>(s)); +void serialize(Archive& ar, storage_adaptor<T>& x, unsigned /* version */) { + auto& impl = unsafe_access::storage_adaptor_impl(x); + ar& serialization::make_nvp("impl", impl); } -template <class A> -template <class Archive> -void unlimited_storage<A>::serialize(Archive& ar, unsigned /* version */) { +template <class Allocator, class Archive> +void serialize(Archive& ar, unlimited_storage<Allocator>& s, unsigned /* version */) { + auto& buffer = unsafe_access::unlimited_storage_buffer(s); + using buffer_t = std::remove_reference_t<decltype(buffer)>; if (Archive::is_loading::value) { - buffer_type dummy(buffer.alloc); + buffer_t helper(buffer.alloc); std::size_t size; - ar& serialization::make_nvp("type", dummy.type); + ar& serialization::make_nvp("type", helper.type); ar& serialization::make_nvp("size", size); - dummy.apply([this, size](auto* tp) { + helper.visit([&buffer, size](auto* tp) { BOOST_ASSERT(tp == nullptr); - using T = detail::remove_cvref_t<decltype(*tp)>; + using T = std::decay_t<decltype(*tp)>; buffer.template make<T>(size); }); } else { ar& serialization::make_nvp("type", buffer.type); ar& serialization::make_nvp("size", buffer.size); } - buffer.apply([this, &ar](auto* tp) { - using T = detail::remove_cvref_t<decltype(*tp)>; + buffer.visit([&buffer, &ar](auto* tp) { + using T = std::decay_t<decltype(*tp)>; ar& serialization::make_nvp( "buffer", serialization::make_array(reinterpret_cast<T*>(buffer.ptr), buffer.size)); diff --git a/boost/histogram/storage_adaptor.hpp b/boost/histogram/storage_adaptor.hpp index 15e8cc4162..4e278a690b 100644 --- a/boost/histogram/storage_adaptor.hpp +++ b/boost/histogram/storage_adaptor.hpp @@ -1,4 +1,4 @@ -// Copyright 2018 Hans Dembinski +// Copyright 2018-2019 Hans Dembinski // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt @@ -8,13 +8,14 @@ #define BOOST_HISTOGRAM_STORAGE_ADAPTOR_HPP #include <algorithm> -#include <boost/assert.hpp> #include <boost/histogram/detail/cat.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/histogram/detail/detect.hpp> +#include <boost/histogram/detail/iterator_adaptor.hpp> +#include <boost/histogram/detail/safe_comparison.hpp> #include <boost/histogram/fwd.hpp> -#include <boost/iterator/iterator_adaptor.hpp> #include <boost/mp11/utility.hpp> #include <boost/throw_exception.hpp> +#include <iosfwd> #include <stdexcept> #include <type_traits> @@ -24,16 +25,23 @@ namespace detail { template <class T> struct vector_impl : T { - vector_impl() = default; + using allocator_type = typename T::allocator_type; + static constexpr bool has_threading_support = + accumulators::is_thread_safe<typename T::value_type>::value; + + vector_impl(const allocator_type& a = {}) : T(a) {} + vector_impl(const vector_impl&) = default; + vector_impl& operator=(const vector_impl&) = default; + vector_impl(vector_impl&&) = default; + vector_impl& operator=(vector_impl&&) = default; + + explicit vector_impl(T&& t) : T(std::move(t)) {} explicit vector_impl(const T& t) : T(t) {} - explicit vector_impl(typename T::allocator_type a) : T(a) {} template <class U, class = requires_iterable<U>> - explicit vector_impl(const U& u) { - T::reserve(u.size()); - for (auto&& x : u) T::emplace_back(x); - } + explicit vector_impl(const U& u, const allocator_type& a = {}) + : T(std::begin(u), std::end(u), a) {} template <class U, class = requires_iterable<U>> vector_impl& operator=(const U& u) { @@ -49,17 +57,29 @@ struct vector_impl : T { T::resize(n, value_type()); std::fill_n(T::begin(), std::min(n, old_size), value_type()); } -}; +}; // namespace detail template <class T> struct array_impl : T { + static constexpr bool has_threading_support = + accumulators::is_thread_safe<typename T::value_type>::value; + array_impl() = default; + array_impl(const array_impl& t) : T(t), size_(t.size_) {} + array_impl& operator=(const array_impl& t) { + T::operator=(t); + size_ = t.size_; + return *this; + } + explicit array_impl(T&& t) : T(std::move(t)) {} explicit array_impl(const T& t) : T(t) {} + template <class U, class = requires_iterable<U>> explicit array_impl(const U& u) : size_(u.size()) { - std::size_t i = 0; - for (auto&& x : u) T::operator[](i++) = x; + using std::begin; + using std::end; + std::copy(begin(u), end(u), this->begin()); } template <class U, class = requires_iterable<U>> @@ -98,10 +118,18 @@ struct map_impl : T { using value_type = typename T::mapped_type; using const_reference = const value_type&; + static constexpr bool has_threading_support = false; + static_assert( + !accumulators::is_thread_safe<value_type>::value, + "std::map and std::unordered_map do not support thread-safe element access. " + "If you have a map with thread-safe element access, please file an issue and" + "support will be added."); + struct reference { reference(map_impl* m, std::size_t i) noexcept : map(m), idx(i) {} + reference(const reference&) noexcept = default; - reference operator=(reference o) { + reference& operator=(const reference& o) { if (this != &o) operator=(static_cast<const_reference>(o)); return *this; } @@ -110,15 +138,14 @@ struct map_impl : T { return static_cast<const map_impl*>(map)->operator[](idx); } - template <class U, class = requires_convertible<U, value_type>> - reference& operator=(const U& u) { + reference& operator=(const_reference u) { auto it = map->find(idx); - if (u == value_type()) { - if (it != static_cast<T*>(map)->end()) map->erase(it); + if (u == value_type{}) { + if (it != static_cast<T*>(map)->end()) { map->erase(it); } } else { - if (it != static_cast<T*>(map)->end()) + if (it != static_cast<T*>(map)->end()) { it->second = u; - else { + } else { map->emplace(idx, u); } } @@ -127,29 +154,31 @@ struct map_impl : T { template <class U, class V = value_type, class = std::enable_if_t<has_operator_radd<V, U>::value>> - reference operator+=(const U& u) { + reference& operator+=(const U& u) { auto it = map->find(idx); - if (it != static_cast<T*>(map)->end()) + if (it != static_cast<T*>(map)->end()) { it->second += u; - else + } else { map->emplace(idx, u); + } return *this; } template <class U, class V = value_type, class = std::enable_if_t<has_operator_rsub<V, U>::value>> - reference operator-=(const U& u) { + reference& operator-=(const U& u) { auto it = map->find(idx); - if (it != static_cast<T*>(map)->end()) + if (it != static_cast<T*>(map)->end()) { it->second -= u; - else + } else { map->emplace(idx, -u); + } return *this; } template <class U, class V = value_type, class = std::enable_if_t<has_operator_rmul<V, U>::value>> - reference operator*=(const U& u) { + reference& operator*=(const U& u) { auto it = map->find(idx); if (it != static_cast<T*>(map)->end()) it->second *= u; return *this; @@ -157,12 +186,13 @@ struct map_impl : T { template <class U, class V = value_type, class = std::enable_if_t<has_operator_rdiv<V, U>::value>> - reference operator/=(const U& u) { + reference& operator/=(const U& u) { auto it = map->find(idx); - if (it != static_cast<T*>(map)->end()) + if (it != static_cast<T*>(map)->end()) { it->second /= u; - else if (!(value_type{} / u == value_type{})) + } else if (!(value_type{} / u == value_type{})) { map->emplace(idx, value_type{} / u); + } return *this; } @@ -170,21 +200,41 @@ struct map_impl : T { class = std::enable_if_t<has_operator_preincrement<V>::value>> reference operator++() { auto it = map->find(idx); - if (it != static_cast<T*>(map)->end()) + if (it != static_cast<T*>(map)->end()) { ++it->second; - else - map->emplace(idx, 1); + } else { + value_type tmp{}; + ++tmp; + map->emplace(idx, tmp); + } return *this; } template <class V = value_type, class = std::enable_if_t<has_operator_preincrement<V>::value>> value_type operator++(int) { - const value_type tmp = operator const_reference(); + const value_type tmp = *this; operator++(); return tmp; } + template <class U, class = std::enable_if_t<has_operator_equal<value_type, U>::value>> + bool operator==(const U& rhs) const { + return operator const_reference() == rhs; + } + + template <class U, class = std::enable_if_t<has_operator_equal<value_type, U>::value>> + bool operator!=(const U& rhs) const { + return !operator==(rhs); + } + + template <typename CharT, typename Traits> + friend std::basic_ostream<CharT, Traits>& operator<<( + std::basic_ostream<CharT, Traits>& os, reference x) { + os << static_cast<const_reference>(x); + return os; + } + template <class... Ts> decltype(auto) operator()(Ts&&... args) { return map->operator[](idx)(std::forward<Ts>(args)...); @@ -196,9 +246,7 @@ struct map_impl : T { template <class Value, class Reference, class MapPtr> struct iterator_t - : boost::iterator_adaptor<iterator_t<Value, Reference, MapPtr>, std::size_t, Value, - std::random_access_iterator_tag, Reference, - std::ptrdiff_t> { + : iterator_adaptor<iterator_t<Value, Reference, MapPtr>, std::size_t, Reference> { iterator_t() = default; template <class V, class R, class M, class = requires_convertible<M, MapPtr>> iterator_t(const iterator_t<V, R, M>& it) noexcept : iterator_t(it.map_, it.base()) {} @@ -208,20 +256,27 @@ struct map_impl : T { bool equal(const iterator_t<V, R, M>& rhs) const noexcept { return map_ == rhs.map_ && iterator_t::base() == rhs.base(); } - decltype(auto) dereference() const { return (*map_)[iterator_t::base()]; } + Reference operator*() const { return (*map_)[iterator_t::base()]; } MapPtr map_ = nullptr; }; using iterator = iterator_t<value_type, reference, map_impl*>; using const_iterator = iterator_t<const value_type, const_reference, const map_impl*>; - map_impl() = default; + using allocator_type = typename T::allocator_type; + + map_impl(const allocator_type& a = {}) : T(a) {} - explicit map_impl(const T& t) : T(t) {} - explicit map_impl(typename T::allocator_type a) : T(a) {} + map_impl(const map_impl&) = default; + map_impl& operator=(const map_impl&) = default; + map_impl(map_impl&&) = default; + map_impl& operator=(map_impl&&) = default; + + map_impl(const T& t) : T(t), size_(t.size()) {} + map_impl(T&& t) : T(std::move(t)), size_(t.size()) {} template <class U, class = requires_iterable<U>> - explicit map_impl(const U& u) : size_(u.size()) { + explicit map_impl(const U& u, const allocator_type& a = {}) : T(a), size_(u.size()) { using std::begin; using std::end; std::copy(begin(u), end(u), this->begin()); @@ -263,33 +318,53 @@ struct map_impl : T { std::size_t size_ = 0; }; -template <typename T> +template <class T> struct ERROR_type_passed_to_storage_adaptor_not_recognized; -template <typename T> -using storage_adaptor_impl = mp11::mp_if< +// clang-format off +template <class T> +using storage_adaptor_impl = + mp11::mp_cond< is_vector_like<T>, vector_impl<T>, - mp11::mp_if<is_array_like<T>, array_impl<T>, - mp11::mp_if<is_map_like<T>, map_impl<T>, - ERROR_type_passed_to_storage_adaptor_not_recognized<T>>>>; - + is_array_like<T>, array_impl<T>, + is_map_like<T>, map_impl<T>, + std::true_type, ERROR_type_passed_to_storage_adaptor_not_recognized<T> + >; +// clang-format on } // namespace detail -/// Turns any vector-like array-like, and map-like container into a storage type. -template <typename T> +/// Turns any vector-like, array-like, and map-like container into a storage type. +template <class T> class storage_adaptor : public detail::storage_adaptor_impl<T> { - using base_type = detail::storage_adaptor_impl<T>; + using impl_type = detail::storage_adaptor_impl<T>; public: - using base_type::base_type; - using base_type::operator=; + // standard copy, move, assign + storage_adaptor(storage_adaptor&&) = default; + storage_adaptor(const storage_adaptor&) = default; + storage_adaptor& operator=(storage_adaptor&&) = default; + storage_adaptor& operator=(const storage_adaptor&) = default; + + // forwarding constructor + template <class... Ts> + storage_adaptor(Ts&&... ts) : impl_type(std::forward<Ts>(ts)...) {} + + // forwarding assign + template <class U> + storage_adaptor& operator=(U&& u) { + impl_type::operator=(std::forward<U>(u)); + return *this; + } template <class U, class = detail::requires_iterable<U>> bool operator==(const U& u) const { using std::begin; using std::end; - return std::equal(this->begin(), this->end(), begin(u), end(u)); + return std::equal(this->begin(), this->end(), begin(u), end(u), detail::safe_equal{}); } + +private: + friend struct unsafe_access; }; } // namespace histogram diff --git a/boost/histogram/unlimited_storage.hpp b/boost/histogram/unlimited_storage.hpp index 10f3a8b621..bce10986eb 100644 --- a/boost/histogram/unlimited_storage.hpp +++ b/boost/histogram/unlimited_storage.hpp @@ -1,4 +1,5 @@ -// Copyright 2015-2017 Hans Dembinski +// Copyright 2015-2019 Hans Dembinski +// Copyright 2019 Glen Joseph Fernandes (glenjofe@gmail.com) // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt @@ -9,392 +10,103 @@ #include <algorithm> #include <boost/assert.hpp> -#include <boost/config/workaround.hpp> -#include <boost/cstdint.hpp> -#include <boost/histogram/detail/meta.hpp> +#include <boost/core/alloc_construct.hpp> +#include <boost/core/exchange.hpp> +#include <boost/histogram/detail/iterator_adaptor.hpp> +#include <boost/histogram/detail/large_int.hpp> +#include <boost/histogram/detail/operators.hpp> +#include <boost/histogram/detail/safe_comparison.hpp> +#include <boost/histogram/detail/static_if.hpp> #include <boost/histogram/fwd.hpp> -#include <boost/iterator/iterator_adaptor.hpp> #include <boost/mp11/algorithm.hpp> #include <boost/mp11/list.hpp> +#include <boost/mp11/utility.hpp> #include <cmath> +#include <cstdint> #include <functional> -#include <limits> +#include <iterator> #include <memory> #include <type_traits> namespace boost { namespace histogram { - namespace detail { -// version of std::equal_to<> which handles comparison of signed and unsigned -struct equal { - template <class T, class U> - bool operator()(const T& t, const U& u) const noexcept { - return impl(std::is_signed<T>{}, std::is_signed<U>{}, t, u); - } - - template <class T, class U> - bool impl(std::false_type, std::false_type, const T& t, const U& u) const noexcept { - return t == u; - } - - template <class T, class U> - bool impl(std::false_type, std::true_type, const T& t, const U& u) const noexcept { - return u >= 0 && t == make_unsigned(u); - } - - template <class T, class U> - bool impl(std::true_type, std::false_type, const T& t, const U& u) const noexcept { - return t >= 0 && make_unsigned(t) == u; - } - - template <class T, class U> - bool impl(std::true_type, std::true_type, const T& t, const U& u) const noexcept { - return t == u; - } -}; - -// version of std::less<> which handles comparison of signed and unsigned -struct less { - template <class T, class U> - bool operator()(const T& t, const U& u) const noexcept { - return impl(std::is_signed<T>{}, std::is_signed<U>{}, t, u); - } - - template <class T, class U> - bool impl(std::false_type, std::false_type, const T& t, const U& u) const noexcept { - return t < u; - } - - template <class T, class U> - bool impl(std::false_type, std::true_type, const T& t, const U& u) const noexcept { - return u >= 0 && t < make_unsigned(u); - } - - template <class T, class U> - bool impl(std::true_type, std::false_type, const T& t, const U& u) const noexcept { - return t < 0 || make_unsigned(t) < u; - } - - template <class T, class U> - bool impl(std::true_type, std::true_type, const T& t, const U& u) const noexcept { - return t < u; - } -}; - -// version of std::greater<> which handles comparison of signed and unsigned -struct greater { - template <class T, class U> - bool operator()(const T& t, const U& u) const noexcept { - return impl(std::is_signed<T>{}, std::is_signed<U>{}, t, u); - } - - template <class T, class U> - bool impl(std::false_type, std::false_type, const T& t, const U& u) const noexcept { - return t > u; - } - - template <class T, class U> - bool impl(std::false_type, std::true_type, const T& t, const U& u) const noexcept { - return u < 0 || t > make_unsigned(u); - } - - template <class T, class U> - bool impl(std::true_type, std::false_type, const T& t, const U& u) const noexcept { - return t >= 0 && make_unsigned(t) > u; - } - - template <class T, class U> - bool impl(std::true_type, std::true_type, const T& t, const U& u) const noexcept { - return t > u; - } -}; - -template <class Allocator> -struct mp_int; - template <class T> -struct is_unsigned_integral : mp11::mp_and<std::is_integral<T>, std::is_unsigned<T>> {}; +struct is_large_int : std::false_type {}; -template <class T> -bool safe_increment(T& t) { - if (t < std::numeric_limits<T>::max()) { - ++t; - return true; - } - return false; -} +template <class A> +struct is_large_int<large_int<A>> : std::true_type {}; -template <class T, class U> -bool safe_radd(T& t, const U& u) { - static_assert(is_unsigned_integral<T>::value, "T must be unsigned integral type"); - static_assert(is_unsigned_integral<U>::value, "T must be unsigned integral type"); - if (static_cast<T>(std::numeric_limits<T>::max() - t) >= u) { - t += static_cast<T>(u); // static_cast to suppress conversion warning - return true; - } - return false; -} +template <class T, class ReturnType> +using if_arithmetic_or_large_int = + std::enable_if_t<(std::is_arithmetic<T>::value || is_large_int<T>::value), + ReturnType>; -// use boost.multiprecision.cpp_int in your own code, it is much more sophisticated -// than this implementation; we use it here to reduce coupling between boost libs -template <class Allocator> -struct mp_int { - explicit mp_int(Allocator a = {}) : data(1, 0, std::move(a)) {} - explicit mp_int(uint64_t v, Allocator a = {}) : data(1, v, std::move(a)) {} - mp_int(const mp_int&) = default; - mp_int& operator=(const mp_int&) = default; - mp_int(mp_int&&) = default; - mp_int& operator=(mp_int&&) = default; - - mp_int& operator=(uint64_t o) { - data = decltype(data)(1, o); - return *this; - } +template <class L, class T> +using next_type = mp11::mp_at_c<L, (mp11::mp_find<L, T>::value + 1)>; - mp_int& operator++() { - BOOST_ASSERT(data.size() > 0u); - std::size_t i = 0; - while (!safe_increment(data[i])) { - data[i] = 0; - ++i; - if (i == data.size()) { - data.push_back(1); - break; - } - } - return *this; - } - - mp_int& operator+=(const mp_int& o) { - if (this == &o) { - auto tmp{o}; - return operator+=(tmp); - } - bool carry = false; - std::size_t i = 0; - for (uint64_t oi : o.data) { - auto& di = maybe_extend(i); - if (carry) { - if (safe_increment(oi)) - carry = false; - else { - ++i; - continue; - } - } - if (!safe_radd(di, oi)) { - add_remainder(di, oi); - carry = true; - } - ++i; - } - while (carry) { - auto& di = maybe_extend(i); - if (safe_increment(di)) break; - di = 0; - ++i; - } - return *this; - } - - mp_int& operator+=(uint64_t o) { - BOOST_ASSERT(data.size() > 0u); - if (safe_radd(data[0], o)) return *this; - add_remainder(data[0], o); - // carry the one, data may grow several times - std::size_t i = 1; - while (true) { - auto& di = maybe_extend(i); - if (safe_increment(di)) break; - di = 0; - ++i; - } - return *this; - } - - operator double() const noexcept { - BOOST_ASSERT(data.size() > 0u); - double result = static_cast<double>(data[0]); - std::size_t i = 0; - while (++i < data.size()) - result += static_cast<double>(data[i]) * std::pow(2.0, i * 64); - return result; - } - - // total ordering for mp_int, mp_int - bool operator<(const mp_int& o) const noexcept { - BOOST_ASSERT(data.size() > 0u); - BOOST_ASSERT(o.data.size() > 0u); - // no leading zeros allowed - BOOST_ASSERT(data.size() == 1 || data.back() > 0u); - BOOST_ASSERT(o.data.size() == 1 || o.data.back() > 0u); - if (data.size() < o.data.size()) return true; - if (data.size() > o.data.size()) return false; - auto s = data.size(); - while (s > 0u) { - --s; - if (data[s] < o.data[s]) return true; - if (data[s] > o.data[s]) return false; - } - return false; // args are equal - } - - bool operator==(const mp_int& o) const noexcept { - BOOST_ASSERT(data.size() > 0u); - BOOST_ASSERT(o.data.size() > 0u); - // no leading zeros allowed - BOOST_ASSERT(data.size() == 1 || data.back() > 0u); - BOOST_ASSERT(o.data.size() == 1 || o.data.back() > 0u); - if (data.size() != o.data.size()) return false; - return std::equal(data.begin(), data.end(), o.data.begin()); - } - - // copied from boost/operators.hpp - friend bool operator>(const mp_int& x, const mp_int& y) { return y < x; } - friend bool operator<=(const mp_int& x, const mp_int& y) { return !(y < x); } - friend bool operator>=(const mp_int& x, const mp_int& y) { return !(x < y); } - friend bool operator!=(const mp_int& x, const mp_int& y) { return !(x == y); } - - // total ordering for mp_int, uint64; partial ordering for mp_int, double - template <class U> - bool operator<(const U& o) const noexcept { - BOOST_ASSERT(data.size() > 0u); - return static_if<is_unsigned_integral<U>>( - [this](uint64_t o) { return data.size() == 1 && data[0] < o; }, - [this](double o) { return operator double() < o; }, o); - } - - template <class U> - bool operator>(const U& o) const noexcept { - BOOST_ASSERT(data.size() > 0u); - BOOST_ASSERT(data.back() > 0u); // no leading zeros allowed - return static_if<is_unsigned_integral<U>>( - [this](uint64_t o) { return data.size() > 1 || data[0] > o; }, - [this](double o) { return operator double() > o; }, o); - } +template <class Allocator> +class construct_guard { +public: + using pointer = typename std::allocator_traits<Allocator>::pointer; - template <class U> - bool operator==(const U& o) const noexcept { - BOOST_ASSERT(data.size() > 0u); - return static_if<is_unsigned_integral<U>>( - [this](uint64_t o) { return data.size() == 1 && data[0] == o; }, - [this](double o) { return operator double() == o; }, o); - } + construct_guard(Allocator& a, pointer p, std::size_t n) noexcept + : a_(a), p_(p), n_(n) {} - // adapted copy from boost/operators.hpp - template <class U> - friend bool operator<=(const mp_int& x, const U& y) { - if (is_unsigned_integral<U>::value) return !(x > y); - return (x < y) || (x == y); - } - template <class U> - friend bool operator>=(const mp_int& x, const U& y) { - if (is_unsigned_integral<U>::value) return !(x < y); - return (x > y) || (x == y); - } - template <class U> - friend bool operator>(const U& x, const mp_int& y) { - if (is_unsigned_integral<U>::value) return y < x; - return y < x; - } - template <class U> - friend bool operator<(const U& x, const mp_int& y) { - if (is_unsigned_integral<U>::value) return y > x; - return y > x; - } - template <class U> - friend bool operator<=(const U& x, const mp_int& y) { - if (is_unsigned_integral<U>::value) return !(y < x); - return (y > x) || (y == x); - } - template <class U> - friend bool operator>=(const U& x, const mp_int& y) { - if (is_unsigned_integral<U>::value) return !(y > x); - return (y < x) || (y == x); - } - template <class U> - friend bool operator==(const U& y, const mp_int& x) { - return x == y; - } - template <class U> - friend bool operator!=(const U& y, const mp_int& x) { - return !(x == y); - } - template <class U> - friend bool operator!=(const mp_int& y, const U& x) { - return !(y == x); + ~construct_guard() { + if (p_) { a_.deallocate(p_, n_); } } - uint64_t& maybe_extend(std::size_t i) { - while (i >= data.size()) data.push_back(0); - return data[i]; - } + void release() { p_ = pointer(); } - static void add_remainder(uint64_t& d, const uint64_t o) noexcept { - BOOST_ASSERT(d > 0u); - // in decimal system it would look like this: - // 8 + 8 = 6 = 8 - (9 - 8) - 1 - // 9 + 1 = 0 = 9 - (9 - 1) - 1 - auto tmp = std::numeric_limits<uint64_t>::max(); - tmp -= o; - --d -= tmp; - } + construct_guard(const construct_guard&) = delete; + construct_guard& operator=(const construct_guard&) = delete; - std::vector<uint64_t, Allocator> data; +private: + Allocator& a_; + pointer p_; + std::size_t n_; }; template <class Allocator> -auto create_buffer(Allocator& a, std::size_t n) { - using AT = std::allocator_traits<Allocator>; - auto ptr = AT::allocate(a, n); // may throw +void* buffer_create(Allocator& a, std::size_t n) { + auto ptr = a.allocate(n); // may throw static_assert(std::is_trivially_copyable<decltype(ptr)>::value, "ptr must be trivially copyable"); - auto it = ptr; - const auto end = ptr + n; - try { - // this loop may throw - while (it != end) AT::construct(a, it++, typename AT::value_type{}); - } catch (...) { - // release resources that were already acquired before rethrowing - while (it != ptr) AT::destroy(a, --it); - AT::deallocate(a, ptr, n); - throw; - } - return ptr; + construct_guard<Allocator> guard(a, ptr, n); + boost::alloc_construct_n(a, ptr, n); + guard.release(); + return static_cast<void*>(ptr); } template <class Allocator, class Iterator> -auto create_buffer(Allocator& a, std::size_t n, Iterator iter) { +auto buffer_create(Allocator& a, std::size_t n, Iterator iter) { BOOST_ASSERT(n > 0u); - using AT = std::allocator_traits<Allocator>; - auto ptr = AT::allocate(a, n); // may throw + auto ptr = a.allocate(n); // may throw static_assert(std::is_trivially_copyable<decltype(ptr)>::value, "ptr must be trivially copyable"); - auto it = ptr; - const auto end = ptr + n; - try { - // this loop may throw - while (it != end) AT::construct(a, it++, *iter++); - } catch (...) { - // release resources that were already acquired before rethrowing - while (it != ptr) AT::destroy(a, --it); - AT::deallocate(a, ptr, n); - throw; - } + construct_guard<Allocator> guard(a, ptr, n); + using T = typename std::allocator_traits<Allocator>::value_type; + struct casting_iterator { + void operator++() noexcept { ++iter_; } + T operator*() noexcept { + return static_cast<T>(*iter_); + } // silence conversion warnings + Iterator iter_; + }; + boost::alloc_construct_n(a, ptr, n, casting_iterator{iter}); + guard.release(); return ptr; } template <class Allocator> -void destroy_buffer(Allocator& a, typename std::allocator_traits<Allocator>::pointer p, +void buffer_destroy(Allocator& a, typename std::allocator_traits<Allocator>::pointer p, std::size_t n) { BOOST_ASSERT(p); BOOST_ASSERT(n > 0u); - using AT = std::allocator_traits<Allocator>; - auto it = p + n; - while (it != p) AT::destroy(a, --it); - AT::deallocate(a, p, n); + boost::alloc_destroy_n(a, p, n); + a.deallocate(p, n); } } // namespace detail @@ -402,16 +114,16 @@ void destroy_buffer(Allocator& a, typename std::allocator_traits<Allocator>::poi /** Memory-efficient storage for integral counters which cannot overflow. - This storage provides a no-overflow-guarantee if it is filled with integral weights - only. This storage implementation keeps a contiguous array of elemental counters, one - for each cell. If an operation is requested, which would overflow a counter, the whole - array is replaced with another of a wider integral type, then the operation is executed. - The storage uses integers of 8, 16, 32, 64 bits, and then switches to a multiprecision + This storage provides a no-overflow-guarantee if the counters are incremented with + integer weights. It maintains a contiguous array of elemental counters, one for each + cell. If an operation is requested which would overflow a counter, the array is + replaced with another of a wider integral type, then the operation is executed. The + storage uses integers of 8, 16, 32, 64 bits, and then switches to a multiprecision integral type, similar to those in [Boost.Multiprecision](https://www.boost.org/doc/libs/develop/libs/multiprecision/doc/html/index.html). - A scaling operation or adding a floating point number turns the elements into doubles, - which voids the no-overflow-guarantee. + A scaling operation or adding a floating point number triggers a conversion of the + elemental counters into doubles, which voids the no-overflow-guarantee. */ template <class Allocator> class unlimited_storage { @@ -419,67 +131,65 @@ class unlimited_storage { std::is_same<typename std::allocator_traits<Allocator>::pointer, typename std::allocator_traits<Allocator>::value_type*>::value, "unlimited_storage requires allocator with trivial pointer type"); + using U8 = std::uint8_t; + using U16 = std::uint16_t; + using U32 = std::uint32_t; + using U64 = std::uint64_t; public: + static constexpr bool has_threading_support = false; + using allocator_type = Allocator; using value_type = double; - using mp_int = detail::mp_int< - typename std::allocator_traits<allocator_type>::template rebind_alloc<uint64_t>>; - -private: - using types = mp11::mp_list<uint8_t, uint16_t, uint32_t, uint64_t, mp_int, double>; - - template <class T> - static constexpr char type_index() noexcept { - return static_cast<char>(mp11::mp_find<types, T>::value); - } + using large_int = detail::large_int< + typename std::allocator_traits<allocator_type>::template rebind_alloc<U64>>; struct buffer_type { - allocator_type alloc; - std::size_t size = 0; - char type = 0; - void* ptr = nullptr; + // cannot be moved outside of scope of unlimited_storage, large_int is dependent type + using types = mp11::mp_list<U8, U16, U32, U64, large_int, double>; + + template <class T> + static constexpr unsigned type_index() noexcept { + return static_cast<unsigned>(mp11::mp_find<types, T>::value); + } template <class F, class... Ts> - decltype(auto) apply(F&& f, Ts&&... ts) const { + decltype(auto) visit(F&& f, Ts&&... ts) const { // this is intentionally not a switch, the if-chain is faster in benchmarks - if (type == type_index<uint8_t>()) - return f(static_cast<uint8_t*>(ptr), std::forward<Ts>(ts)...); - if (type == type_index<uint16_t>()) - return f(static_cast<uint16_t*>(ptr), std::forward<Ts>(ts)...); - if (type == type_index<uint32_t>()) - return f(static_cast<uint32_t*>(ptr), std::forward<Ts>(ts)...); - if (type == type_index<uint64_t>()) - return f(static_cast<uint64_t*>(ptr), std::forward<Ts>(ts)...); - if (type == type_index<mp_int>()) - return f(static_cast<mp_int*>(ptr), std::forward<Ts>(ts)...); + if (type == type_index<U8>()) + return f(static_cast<U8*>(ptr), std::forward<Ts>(ts)...); + if (type == type_index<U16>()) + return f(static_cast<U16*>(ptr), std::forward<Ts>(ts)...); + if (type == type_index<U32>()) + return f(static_cast<U32*>(ptr), std::forward<Ts>(ts)...); + if (type == type_index<U64>()) + return f(static_cast<U64*>(ptr), std::forward<Ts>(ts)...); + if (type == type_index<large_int>()) + return f(static_cast<large_int*>(ptr), std::forward<Ts>(ts)...); return f(static_cast<double*>(ptr), std::forward<Ts>(ts)...); } - buffer_type(allocator_type a = {}) : alloc(std::move(a)) {} + buffer_type(const allocator_type& a = {}) : alloc(a) {} buffer_type(buffer_type&& o) noexcept - : alloc(std::move(o.alloc)), size(o.size), type(o.type), ptr(o.ptr) { - o.size = 0; - o.type = 0; - o.ptr = nullptr; - } + : alloc(std::move(o.alloc)) + , size(boost::exchange(o.size, 0)) + , type(boost::exchange(o.type, 0)) + , ptr(boost::exchange(o.ptr, nullptr)) {} buffer_type& operator=(buffer_type&& o) noexcept { - if (this != &o) { - using std::swap; - swap(alloc, o.alloc); - swap(size, o.size); - swap(type, o.type); - swap(ptr, o.ptr); - } + using std::swap; + swap(alloc, o.alloc); + swap(size, o.size); + swap(type, o.type); + swap(ptr, o.ptr); return *this; } - buffer_type(const buffer_type& o) : alloc(o.alloc) { - o.apply([this, &o](auto* otp) { - using T = detail::remove_cvref_t<decltype(*otp)>; - this->template make<T>(o.size, otp); + buffer_type(const buffer_type& x) : alloc(x.alloc) { + x.visit([this, n = x.size](const auto* xp) { + using T = std::decay_t<decltype(*xp)>; + this->template make<T>(n, xp); }); } @@ -493,23 +203,18 @@ private: void destroy() noexcept { BOOST_ASSERT((ptr == nullptr) == (size == 0)); if (ptr == nullptr) return; - apply([this](auto* tp) { - using T = detail::remove_cvref_t<decltype(*tp)>; + visit([this](auto* p) { + using T = std::decay_t<decltype(*p)>; using alloc_type = typename std::allocator_traits<allocator_type>::template rebind_alloc<T>; alloc_type a(alloc); // rebind allocator - detail::destroy_buffer(a, tp, size); + detail::buffer_destroy(a, p, this->size); }); size = 0; type = 0; ptr = nullptr; } -#if defined(_MSC_VER) -#pragma warning(push) -#pragma warning(disable : 4244) // possible loss of data -#endif - template <class T> void make(std::size_t n) { // note: order of commands is to not leave buffer in invalid state upon throw @@ -519,7 +224,7 @@ private: using alloc_type = typename std::allocator_traits<allocator_type>::template rebind_alloc<T>; alloc_type a(alloc); - ptr = detail::create_buffer(a, n); // may throw + ptr = detail::buffer_create(a, n); // may throw } size = n; type = type_index<T>(); @@ -528,14 +233,14 @@ private: template <class T, class U> void make(std::size_t n, U iter) { // note: iter may be current ptr, so create new buffer before deleting old buffer - T* new_ptr = nullptr; + void* new_ptr = nullptr; const auto new_type = type_index<T>(); if (n > 0) { // rebind allocator using alloc_type = typename std::allocator_traits<allocator_type>::template rebind_alloc<T>; alloc_type a(alloc); - new_ptr = detail::create_buffer(a, n, iter); // may throw + new_ptr = detail::buffer_create(a, n, iter); // may throw } destroy(); size = n; @@ -543,229 +248,204 @@ private: ptr = new_ptr; } -#if defined(_MSC_VER) -#pragma warning(pop) -#endif + allocator_type alloc; + std::size_t size = 0; + unsigned type = 0; + mutable void* ptr = nullptr; }; - template <class Buffer> - class reference_t { - public: - reference_t(Buffer* b, std::size_t i) : buffer_(b), idx_(i) {} + class reference; // forward declare to make friend of const_reference - reference_t(const reference_t&) = default; - reference_t& operator=(const reference_t&) = delete; // references do not rebind - reference_t& operator=(reference_t&&) = delete; // references do not rebind + /// implementation detail + class const_reference + : detail::partially_ordered<const_reference, const_reference, void> { + public: + const_reference(buffer_type& b, std::size_t i) noexcept : bref_(b), idx_(i) { + BOOST_ASSERT(idx_ < bref_.size); + } - // minimal operators for partial ordering - bool operator<(reference_t rhs) const { return op<detail::less>(rhs); } - bool operator>(reference_t rhs) const { return op<detail::greater>(rhs); } - bool operator==(reference_t rhs) const { return op<detail::equal>(rhs); } + const_reference(const const_reference&) noexcept = default; - // adapted copy from boost/operators.hpp for partial ordering - friend bool operator<=(reference_t x, reference_t y) { return !(y < x); } - friend bool operator>=(reference_t x, reference_t y) { return !(y > x); } - friend bool operator!=(reference_t y, reference_t x) { return !(x == y); } + // no assignment for const_references + const_reference& operator=(const const_reference&) = delete; + const_reference& operator=(const_reference&&) = delete; - template <class U> - bool operator<(const U& rhs) const { - return op<detail::less>(rhs); + operator double() const noexcept { + return bref_.visit( + [this](const auto* p) { return static_cast<double>(p[this->idx_]); }); } - template <class U> - bool operator>(const U& rhs) const { - return op<detail::greater>(rhs); + bool operator<(const const_reference& o) const noexcept { + return apply_binary<detail::safe_less>(o); } - template <class U> - bool operator==(const U& rhs) const { - return op<detail::equal>(rhs); + bool operator==(const const_reference& o) const noexcept { + return apply_binary<detail::safe_equal>(o); } - // adapted copy from boost/operators.hpp template <class U> - friend bool operator<=(reference_t x, const U& y) { - if (detail::is_unsigned_integral<U>::value) return !(x > y); - return (x < y) || (x == y); - } - template <class U> - friend bool operator>=(reference_t x, const U& y) { - if (detail::is_unsigned_integral<U>::value) return !(x < y); - return (x > y) || (x == y); - } - template <class U> - friend bool operator>(const U& x, reference_t y) { - return y < x; - } - template <class U> - friend bool operator<(const U& x, reference_t y) { - return y > x; - } - template <class U> - friend bool operator<=(const U& x, reference_t y) { - if (detail::is_unsigned_integral<U>::value) return !(y < x); - return (y > x) || (y == x); - } - template <class U> - friend bool operator>=(const U& x, reference_t y) { - if (detail::is_unsigned_integral<U>::value) return !(y > x); - return (y < x) || (y == x); - } - template <class U> - friend bool operator==(const U& y, reference_t x) { - return x == y; - } - template <class U> - friend bool operator!=(const U& y, reference_t x) { - return !(x == y); + detail::if_arithmetic_or_large_int<U, bool> operator<(const U& o) const noexcept { + return apply_binary<detail::safe_less>(o); } + template <class U> - friend bool operator!=(reference_t y, const U& x) { - return !(y == x); + detail::if_arithmetic_or_large_int<U, bool> operator>(const U& o) const noexcept { + return apply_binary<detail::safe_greater>(o); } - operator double() const { - return buffer_->apply( - [this](const auto* tp) { return static_cast<double>(tp[idx_]); }); + template <class U> + detail::if_arithmetic_or_large_int<U, bool> operator==(const U& o) const noexcept { + return apply_binary<detail::safe_equal>(o); } - protected: - template <class Binary, class U> - bool op(const reference_t<U>& rhs) const { - const auto i = idx_; - const auto j = rhs.idx_; - return buffer_->apply([i, j, &rhs](const auto* ptr) { - const auto& pi = ptr[i]; - return rhs.buffer_->apply([&pi, j](const auto* q) { return Binary()(pi, q[j]); }); + private: + template <class Binary> + bool apply_binary(const const_reference& x) const noexcept { + return x.bref_.visit([this, ix = x.idx_](const auto* xp) { + return this->apply_binary<Binary>(xp[ix]); }); } template <class Binary, class U> - bool op(const U& rhs) const { - const auto i = idx_; - return buffer_->apply([i, &rhs](const auto* tp) { return Binary()(tp[i], rhs); }); + bool apply_binary(const U& x) const noexcept { + return bref_.visit([i = idx_, &x](const auto* p) { return Binary()(p[i], x); }); } - template <class U> - friend class reference_t; - - Buffer* buffer_; + protected: + buffer_type& bref_; std::size_t idx_; + friend class reference; }; -public: - using const_reference = reference_t<const buffer_type>; - - class reference : public reference_t<buffer_type> { - using base_type = reference_t<buffer_type>; - + /// implementation detail + class reference : public const_reference, + public detail::partially_ordered<reference, reference, void> { public: - using base_type::base_type; + reference(buffer_type& b, std::size_t i) noexcept : const_reference(b, i) {} - reference operator=(reference t) { - t.buffer_->apply([this, &t](const auto* otp) { *this = otp[t.idx_]; }); - return *this; + // references do copy-construct + reference(const reference& x) noexcept = default; + + // references do not rebind, assign through + reference& operator=(const reference& x) { + return operator=(static_cast<const_reference>(x)); } - reference operator=(const_reference t) { - t.buffer_->apply([this, &t](const auto* otp) { *this = otp[t.idx_]; }); + // references do not rebind, assign through + reference& operator=(const const_reference& x) { + // safe for self-assignment, assigning matching type doesn't invalide buffer + x.bref_.visit([this, ix = x.idx_](const auto* xp) { this->operator=(xp[ix]); }); return *this; } template <class U> - reference operator=(const U& t) { - base_type::buffer_->apply([this, &t](auto* tp) { - tp[this->idx_] = 0; - adder()(tp, *(this->buffer_), this->idx_, t); + detail::if_arithmetic_or_large_int<U, reference&> operator=(const U& x) { + this->bref_.visit([this, &x](auto* p) { + // gcc-8 optimizes the expression `p[this->idx_] = 0` away even at -O0, + // so we merge it into the next line which is properly counted + adder()((p[this->idx_] = 0, p), this->bref_, this->idx_, x); }); return *this; } + bool operator<(const reference& o) const noexcept { + return const_reference::operator<(o); + } + + bool operator==(const reference& o) const noexcept { + return const_reference::operator==(o); + } + template <class U> - reference operator+=(const U& t) { - base_type::buffer_->apply(adder(), *base_type::buffer_, base_type::idx_, t); - return *this; + detail::if_arithmetic_or_large_int<U, bool> operator<(const U& o) const noexcept { + return const_reference::operator<(o); } template <class U> - reference operator*=(const U& t) { - base_type::buffer_->apply(multiplier(), *base_type::buffer_, base_type::idx_, t); - return *this; + detail::if_arithmetic_or_large_int<U, bool> operator>(const U& o) const noexcept { + return const_reference::operator>(o); } template <class U> - reference operator-=(const U& t) { - return operator+=(-t); + detail::if_arithmetic_or_large_int<U, bool> operator==(const U& o) const noexcept { + return const_reference::operator==(o); + } + + reference& operator+=(const const_reference& x) { + x.bref_.visit([this, ix = x.idx_](const auto* xp) { this->operator+=(xp[ix]); }); + return *this; } template <class U> - reference operator/=(const U& t) { - return operator*=(1.0 / static_cast<double>(t)); + detail::if_arithmetic_or_large_int<U, reference&> operator+=(const U& x) { + this->bref_.visit(adder(), this->bref_, this->idx_, x); + return *this; } - reference operator++() { - base_type::buffer_->apply(incrementor(), *base_type::buffer_, base_type::idx_); + reference& operator-=(const double x) { return operator+=(-x); } + + reference& operator*=(const double x) { + this->bref_.visit(multiplier(), this->bref_, this->idx_, x); return *this; } - // minimal operators for partial ordering - bool operator<(reference rhs) const { return base_type::operator<(rhs); } - bool operator>(reference rhs) const { return base_type::operator>(rhs); } - bool operator==(reference rhs) const { return base_type::operator==(rhs); } + reference& operator/=(const double x) { return operator*=(1.0 / x); } - // adapted copy from boost/operators.hpp for partial ordering - friend bool operator<=(reference x, reference y) { return !(y < x); } - friend bool operator>=(reference x, reference y) { return !(y > x); } - friend bool operator!=(reference y, reference x) { return !(x == y); } + reference& operator++() { + this->bref_.visit(incrementor(), this->bref_, this->idx_); + return *this; + } }; private: - template <class Value, class Reference, class Buffer> - class iterator_t - : public boost::iterator_adaptor<iterator_t<Value, Reference, Buffer>, std::size_t, - Value, std::random_access_iterator_tag, Reference, - std::ptrdiff_t> { - + template <class Value, class Reference> + class iterator_impl : public detail::iterator_adaptor<iterator_impl<Value, Reference>, + std::size_t, Reference, Value> { public: - iterator_t() = default; - template <class V, class R, class B> - iterator_t(const iterator_t<V, R, B>& it) - : iterator_t::iterator_adaptor_(it.base()), buffer_(it.buffer_) {} - iterator_t(Buffer* b, std::size_t i) noexcept - : iterator_t::iterator_adaptor_(i), buffer_(b) {} + iterator_impl() = default; + template <class V, class R> + iterator_impl(const iterator_impl<V, R>& it) + : iterator_impl::iterator_adaptor_(it.base()), buffer_(it.buffer_) {} + iterator_impl(buffer_type* b, std::size_t i) noexcept + : iterator_impl::iterator_adaptor_(i), buffer_(b) {} - protected: - template <class V, class R, class B> - bool equal(const iterator_t<V, R, B>& rhs) const noexcept { - return buffer_ == rhs.buffer_ && this->base() == rhs.base(); - } - Reference dereference() const { return {buffer_, this->base()}; } + Reference operator*() const noexcept { return {*buffer_, this->base()}; } - friend class ::boost::iterator_core_access; - template <class V, class R, class B> - friend class iterator_t; + template <class V, class R> + friend class iterator_impl; private: - Buffer* buffer_ = nullptr; + mutable buffer_type* buffer_ = nullptr; }; public: - using const_iterator = iterator_t<const value_type, const_reference, const buffer_type>; - using iterator = iterator_t<value_type, reference, buffer_type>; + using const_iterator = iterator_impl<const value_type, const_reference>; + using iterator = iterator_impl<value_type, reference>; - explicit unlimited_storage(allocator_type a = {}) : buffer(std::move(a)) {} + explicit unlimited_storage(const allocator_type& a = {}) : buffer_(a) {} unlimited_storage(const unlimited_storage&) = default; unlimited_storage& operator=(const unlimited_storage&) = default; unlimited_storage(unlimited_storage&&) = default; unlimited_storage& operator=(unlimited_storage&&) = default; - template <class T> - unlimited_storage(const storage_adaptor<T>& s) { - using V = detail::remove_cvref_t<decltype(s[0])>; - constexpr auto ti = type_index<V>(); - detail::static_if_c<(ti < mp11::mp_size<types>::value)>( - [&](auto) { buffer.template make<V>(s.size(), s.begin()); }, - [&](auto) { buffer.template make<double>(s.size(), s.begin()); }, 0); + // TODO + // template <class Allocator> + // unlimited_storage(const unlimited_storage<Allocator>& s) + + template <class Iterable, class = detail::requires_iterable<Iterable>> + explicit unlimited_storage(const Iterable& s) { + using std::begin; + using std::end; + auto s_begin = begin(s); + auto s_end = end(s); + using V = typename std::iterator_traits<decltype(begin(s))>::value_type; + constexpr auto ti = buffer_type::template type_index<V>(); + constexpr auto nt = mp11::mp_size<typename buffer_type::types>::value; + const std::size_t size = static_cast<std::size_t>(std::distance(s_begin, s_end)); + detail::static_if_c<(ti < nt)>( + [this, &size, &s_begin](auto) { buffer_.template make<V>(size, s_begin); }, + [this, &size, &s_begin](auto) { buffer_.template make<double>(size, s_begin); }, + 0); } template <class Iterable, class = detail::requires_iterable<Iterable>> @@ -774,147 +454,156 @@ public: return *this; } - allocator_type get_allocator() const { return buffer.alloc; } + allocator_type get_allocator() const { return buffer_.alloc; } - void reset(std::size_t s) { buffer.template make<uint8_t>(s); } + void reset(std::size_t n) { buffer_.template make<U8>(n); } - std::size_t size() const noexcept { return buffer.size; } + std::size_t size() const noexcept { return buffer_.size; } - reference operator[](std::size_t i) noexcept { return {&buffer, i}; } - const_reference operator[](std::size_t i) const noexcept { return {&buffer, i}; } + reference operator[](std::size_t i) noexcept { return {buffer_, i}; } + const_reference operator[](std::size_t i) const noexcept { return {buffer_, i}; } - bool operator==(const unlimited_storage& o) const noexcept { - if (size() != o.size()) return false; - return buffer.apply([&o](const auto* ptr) { - return o.buffer.apply([ptr, &o](const auto* optr) { - return std::equal(ptr, ptr + o.size(), optr, detail::equal{}); + bool operator==(const unlimited_storage& x) const noexcept { + if (size() != x.size()) return false; + return buffer_.visit([&x](const auto* p) { + return x.buffer_.visit([p, n = x.size()](const auto* xp) { + return std::equal(p, p + n, xp, detail::safe_equal{}); }); }); } - template <class T> - bool operator==(const T& o) const { - if (size() != o.size()) return false; - return buffer.apply([&o](const auto* ptr) { - return std::equal(ptr, ptr + o.size(), std::begin(o), detail::equal{}); + template <class Iterable> + bool operator==(const Iterable& iterable) const { + if (size() != iterable.size()) return false; + return buffer_.visit([&iterable](const auto* p) { + return std::equal(p, p + iterable.size(), std::begin(iterable), + detail::safe_equal{}); }); } unlimited_storage& operator*=(const double x) { - buffer.apply(multiplier(), buffer, x); + buffer_.visit(multiplier(), buffer_, x); return *this; } - iterator begin() noexcept { return {&buffer, 0}; } - iterator end() noexcept { return {&buffer, size()}; } - const_iterator begin() const noexcept { return {&buffer, 0}; } - const_iterator end() const noexcept { return {&buffer, size()}; } + iterator begin() noexcept { return {&buffer_, 0}; } + iterator end() noexcept { return {&buffer_, size()}; } + const_iterator begin() const noexcept { return {&buffer_, 0}; } + const_iterator end() const noexcept { return {&buffer_, size()}; } - /// @private used by unit tests, not part of generic storage interface + /// implementation detail; used by unit tests, not part of generic storage interface template <class T> - unlimited_storage(std::size_t s, const T* p, allocator_type a = {}) - : buffer(std::move(a)) { - buffer.template make<T>(s, p); + unlimited_storage(std::size_t s, const T* p, const allocator_type& a = {}) + : buffer_(std::move(a)) { + buffer_.template make<T>(s, p); } - template <class Archive> - void serialize(Archive&, unsigned); - private: struct incrementor { - template <class T, class Buffer> - void operator()(T* tp, Buffer& b, std::size_t i) { + template <class T> + void operator()(T* tp, buffer_type& b, std::size_t i) { + BOOST_ASSERT(tp && i < b.size); if (!detail::safe_increment(tp[i])) { - using U = mp11::mp_at_c<types, (type_index<T>() + 1)>; + using U = detail::next_type<typename buffer_type::types, T>; b.template make<U>(b.size, tp); ++static_cast<U*>(b.ptr)[i]; } } - template <class Buffer> - void operator()(mp_int* tp, Buffer&, std::size_t i) { - ++tp[i]; - } + void operator()(large_int* tp, buffer_type&, std::size_t i) { ++tp[i]; } - template <class Buffer> - void operator()(double* tp, Buffer&, std::size_t i) { - ++tp[i]; - } + void operator()(double* tp, buffer_type&, std::size_t i) { ++tp[i]; } }; struct adder { - template <class Buffer, class U> - void operator()(double* tp, Buffer&, std::size_t i, const U& x) { + template <class U> + void operator()(double* tp, buffer_type&, std::size_t i, const U& x) { tp[i] += static_cast<double>(x); } - template <class T, class Buffer, class U> - void operator()(T* tp, Buffer& b, std::size_t i, const U& x) { - U_is_integral(std::is_integral<U>{}, tp, b, i, x); + void operator()(large_int* tp, buffer_type&, std::size_t i, const large_int& x) { + tp[i] += x; // potentially adding large_int to itself is safe } - template <class T, class Buffer, class U> - void U_is_integral(std::false_type, T* tp, Buffer& b, std::size_t i, const U& x) { + template <class T, class U> + void operator()(T* tp, buffer_type& b, std::size_t i, const U& x) { + is_x_integral(std::is_integral<U>{}, tp, b, i, x); + } + + template <class T, class U> + void is_x_integral(std::false_type, T* tp, buffer_type& b, std::size_t i, + const U& x) { + // x could be reference to buffer we manipulate, make copy before changing buffer + const auto v = static_cast<double>(x); b.template make<double>(b.size, tp); - operator()(static_cast<double*>(b.ptr), b, i, x); + operator()(static_cast<double*>(b.ptr), b, i, v); + } + + template <class T> + void is_x_integral(std::false_type, T* tp, buffer_type& b, std::size_t i, + const large_int& x) { + // x could be reference to buffer we manipulate, make copy before changing buffer + const auto v = static_cast<large_int>(x); + b.template make<large_int>(b.size, tp); + operator()(static_cast<large_int*>(b.ptr), b, i, v); } - template <class T, class Buffer, class U> - void U_is_integral(std::true_type, T* tp, Buffer& b, std::size_t i, const U& x) { - U_is_unsigned_integral(std::is_unsigned<U>{}, tp, b, i, x); + template <class T, class U> + void is_x_integral(std::true_type, T* tp, buffer_type& b, std::size_t i, const U& x) { + is_x_unsigned(std::is_unsigned<U>{}, tp, b, i, x); } - template <class T, class Buffer, class U> - void U_is_unsigned_integral(std::false_type, T* tp, Buffer& b, std::size_t i, - const U& x) { + template <class T, class U> + void is_x_unsigned(std::false_type, T* tp, buffer_type& b, std::size_t i, + const U& x) { if (x >= 0) - U_is_unsigned_integral(std::true_type{}, tp, b, i, detail::make_unsigned(x)); + is_x_unsigned(std::true_type{}, tp, b, i, detail::make_unsigned(x)); else - U_is_integral(std::false_type{}, tp, b, i, static_cast<double>(x)); + is_x_integral(std::false_type{}, tp, b, i, static_cast<double>(x)); } - template <class Buffer, class U> - void U_is_unsigned_integral(std::true_type, mp_int* tp, Buffer&, std::size_t i, - const U& x) { - tp[i] += x; + template <class T, class U> + void is_x_unsigned(std::true_type, T* tp, buffer_type& b, std::size_t i, const U& x) { + if (detail::safe_radd(tp[i], x)) return; + // x could be reference to buffer we manipulate, need to convert to value + const auto y = x; + using TN = detail::next_type<typename buffer_type::types, T>; + b.template make<TN>(b.size, tp); + is_x_unsigned(std::true_type{}, static_cast<TN*>(b.ptr), b, i, y); } - template <class T, class Buffer, class U> - void U_is_unsigned_integral(std::true_type, T* tp, Buffer& b, std::size_t i, - const U& x) { - if (detail::safe_radd(tp[i], x)) return; - using V = mp11::mp_at_c<types, (type_index<T>() + 1)>; - b.template make<V>(b.size, tp); - U_is_unsigned_integral(std::true_type{}, static_cast<V*>(b.ptr), b, i, x); + template <class U> + void is_x_unsigned(std::true_type, large_int* tp, buffer_type&, std::size_t i, + const U& x) { + tp[i] += x; } }; struct multiplier { - template <class T, class Buffer> - void operator()(T* tp, Buffer& b, const double x) { + template <class T> + void operator()(T* tp, buffer_type& b, const double x) { // potential lossy conversion that cannot be avoided b.template make<double>(b.size, tp); operator()(static_cast<double*>(b.ptr), b, x); } - template <class Buffer> - void operator()(double* tp, Buffer& b, const double x) { + void operator()(double* tp, buffer_type& b, const double x) { for (auto end = tp + b.size; tp != end; ++tp) *tp *= x; } - template <class T, class Buffer, class U> - void operator()(T* tp, Buffer& b, std::size_t i, const U& x) { + template <class T> + void operator()(T* tp, buffer_type& b, std::size_t i, const double x) { b.template make<double>(b.size, tp); operator()(static_cast<double*>(b.ptr), b, i, x); } - template <class Buffer, class U> - void operator()(double* tp, Buffer&, std::size_t i, const U& x) { + void operator()(double* tp, buffer_type&, std::size_t i, const double x) { tp[i] *= static_cast<double>(x); } }; - buffer_type buffer; + mutable buffer_type buffer_; + friend struct unsafe_access; }; } // namespace histogram diff --git a/boost/histogram/unsafe_access.hpp b/boost/histogram/unsafe_access.hpp index 9cff0ea99e..4a39965373 100644 --- a/boost/histogram/unsafe_access.hpp +++ b/boost/histogram/unsafe_access.hpp @@ -13,7 +13,18 @@ namespace boost { namespace histogram { -/// Unsafe read/write access to classes that potentially break consistency +/** Unsafe read/write access to private data that potentially breaks consistency. + + This struct enables access to private data of some classes. It is intended for library + developers who need this to implement algorithms efficiently, for example, + serialization. Users should not use this. If you are a user who absolutely needs this to + get a specific effect, please submit an issue on Github. Perhaps the public + interface is insufficient and should be extended for your use case. + + Unlike the normal interface, the unsafe_access interface may change between versions. + If your code relies on unsafe_access, it may or may not break when you update Boost. + This is another reason to not use it unless you are ok with these conditions. +*/ struct unsafe_access { /** Get axes. @@ -58,13 +69,31 @@ struct unsafe_access { */ template <class Histogram> static auto& storage(Histogram& hist) { - return hist.storage_; + return hist.storage_and_mutex_.first(); } /// @copydoc storage() template <class Histogram> static const auto& storage(const Histogram& hist) { - return hist.storage_; + return hist.storage_and_mutex_.first(); + } + + /** + Get buffer of unlimited_storage. + @param storage instance of unlimited_storage. + */ + template <class Allocator> + static constexpr auto& unlimited_storage_buffer(unlimited_storage<Allocator>& storage) { + return storage.buffer_; + } + + /** + Get implementation of storage_adaptor. + @param storage instance of storage_adaptor. + */ + template <class T> + static constexpr auto& storage_adaptor_impl(storage_adaptor<T>& storage) { + return static_cast<typename storage_adaptor<T>::impl_type&>(storage); } }; |