root/ROOT/span.hxx

0001 /// \file ROOT/span.hxx
0002 /// \ingroup Base StdExt
0003 /// \author Axel Naumann <axel@cern.ch>
0004 /// \date 2015-09-06
0005
0006 /*************************************************************************
0007  * Copyright (C) 1995-2015, Rene Brun and Fons Rademakers.               *
0008  * All rights reserved.                                                  *
0009  *                                                                       *
0010  * For the licensing terms see $ROOTSYS/LICENSE.                         *
0011  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
0012  *************************************************************************/
0013
0014 #ifndef ROOT_RHYSD_SPAN_H
0015 #define ROOT_RHYSD_SPAN_H
0016
0017 #if __cplusplus >= 202002
0018 # if __has_include(<span>)
0019 #  include <span>
0020 # endif
0021 #endif
0022
0023 #if !defined(__cpp_lib_span)
0024
0025 // Necessary to compile in c++11 mode
0026 #if __cplusplus >= 201402L
0027 #define R__CONSTEXPR_IF_CXX14 constexpr
0028 #else
0029 #define R__CONSTEXPR_IF_CXX14
0030 #endif
0031
0032 // From https://github.com/rhysd/array_view/blob/master/include/array_view.hpp
0033
0034 #include <cstddef>
0035 #include <iterator>
0036 #include <array>
0037 #include <vector>
0038 #include <stdexcept>
0039 #include <memory>
0040 #include <type_traits>
0041 #include <initializer_list>
0042
0043 namespace ROOT {
0044 namespace Detail {
0045 using std::size_t;
0046
0047 // detail meta functions {{{
0048 template<class Array>
0049 struct is_array_class {
0050   static bool const value = false;
0051 };
0052 template<class T, size_t N>
0053 struct is_array_class<std::array<T, N>> {
0054   static bool const value = true;
0055 };
0056 template<class T>
0057 struct is_array_class<std::vector<T>> {
0058   static bool const value = true;
0059 };
0060 template<class T>
0061 struct is_array_class<std::initializer_list<T>> {
0062   static bool const value = true;
0063 };
0064 // }}}
0065
0066 // index sequences {{{
0067 template< size_t... Indices >
0068 struct indices{
0069   static constexpr size_t value[sizeof...(Indices)] = {Indices...};
0070 };
0071
0072 template<class IndicesType, size_t Next>
0073 struct make_indices_next;
0074
0075 template<size_t... Indices, size_t Next>
0076 struct make_indices_next<indices<Indices...>, Next> {
0077   typedef indices<Indices..., (Indices + Next)...> type;
0078 };
0079
0080 template<class IndicesType, size_t Next, size_t Tail>
0081 struct make_indices_next2;
0082
0083 template<size_t... Indices, size_t Next, size_t Tail>
0084 struct make_indices_next2<indices<Indices...>, Next, Tail> {
0085   typedef indices<Indices..., (Indices + Next)..., Tail> type;
0086 };
0087
0088 template<size_t First, size_t Step, size_t N, class = void>
0089 struct make_indices_impl;
0090
0091 template<size_t First, size_t Step, size_t N>
0092 struct make_indices_impl<
0093    First,
0094    Step,
0095    N,
0096    typename std::enable_if<(N == 0)>::type
0097 > {
0098   typedef indices<> type;
0099 };
0100
0101 template<size_t First, size_t Step, size_t N>
0102 struct make_indices_impl<
0103    First,
0104    Step,
0105    N,
0106    typename std::enable_if<(N == 1)>::type
0107 > {
0108   typedef indices<First> type;
0109 };
0110
0111 template<size_t First, size_t Step, size_t N>
0112 struct make_indices_impl<
0113    First,
0114    Step,
0115    N,
0116    typename std::enable_if<(N > 1 && N % 2 == 0)>::type
0117 >
0118    : ROOT::Detail::make_indices_next<
0119       typename ROOT::Detail::make_indices_impl<First, Step, N / 2>::type,
0120       First + N / 2 * Step
0121    >
0122 {};
0123
0124 template<size_t First, size_t Step, size_t N>
0125 struct make_indices_impl<
0126    First,
0127    Step,
0128    N,
0129    typename std::enable_if<(N > 1 && N % 2 == 1)>::type
0130 >
0131    : ROOT::Detail::make_indices_next2<
0132       typename ROOT::Detail::make_indices_impl<First, Step, N / 2>::type,
0133       First + N / 2 * Step,
0134       First + (N - 1) * Step
0135    >
0136 {};
0137
0138 template<size_t First, size_t Last, size_t Step = 1>
0139 struct make_indices_
0140    : ROOT::Detail::make_indices_impl<
0141       First,
0142       Step,
0143       ((Last - First) + (Step - 1)) / Step
0144    >
0145 {};
0146
0147 template < size_t Start, size_t Last, size_t Step = 1 >
0148 using make_indices = typename make_indices_< Start, Last, Step >::type;
0149 // }}}
0150 } // namespace Detail
0151 }
0152
0153 namespace std {
0154
0155 inline namespace __ROOT {
0156
0157 // span {{{
0158
0159 struct check_bound_t {};
0160 static constexpr check_bound_t check_bound{};
0161
0162 template<class T>
0163 class span {
0164 public:
0165   /*
0166    * types
0167    */
0168   typedef T element_type;
0169   typedef std::remove_cv<T>     value_type;
0170   typedef element_type *        pointer;
0171   typedef element_type const*   const_pointer;
0172   typedef element_type &        reference;
0173   typedef element_type const&   const_reference;
0174   typedef element_type *        iterator;
0175   typedef element_type const*   const_iterator;
0176   typedef ptrdiff_t             difference_type;
0177   typedef std::size_t           size_type;
0178   typedef std::reverse_iterator<iterator> reverse_iterator;
0179   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0180
0181   /*
0182    * ctors and assign operators
0183    */
0184   constexpr span() noexcept
0185      : length_(0), data_(nullptr)
0186   {}
0187
0188   constexpr span(span const&) noexcept = default;
0189   constexpr span(span &&) noexcept = default;
0190
0191   // Note:
0192   // This constructor can't be constexpr because & operator can't be constexpr.
0193   template<size_type N>
0194   /*implicit*/ span(std::array<T, N> & a) noexcept
0195      : length_(N), data_(N > 0 ? a.data() : nullptr)
0196   {}
0197
0198   // Note:
0199   // This constructor can't be constexpr because & operator can't be constexpr.
0200   template<size_type N>
0201   /*implicit*/ span(T(& a)[N]) noexcept
0202      : length_(N), data_(N > 0 ? std::addressof(a[0]) : nullptr)
0203   {
0204     static_assert(N > 0, "Zero-length array is not permitted in ISO C++.");
0205   }
0206
0207   // Note:
0208   // This constructor needs to be disabled if T is not a const type, because we
0209   // don't want to create span<T> from vector<T> const&.
0210   // The explicit disabling via SFINAE is necessary to this overload is not
0211   // accidentally taken by cppyy, resulting in the failure of constructor
0212   // wrapper code compilation.
0213   template <class U = T, class = typename std::enable_if<std::is_const<U>::value>::type>
0214   /*implicit*/ span(std::vector<typename std::remove_cv<T>::type> const& v) noexcept
0215      : length_(v.size()), data_(v.empty() ? nullptr : v.data())
0216   {}
0217
0218   /*implicit*/ span(std::vector<typename std::remove_cv<T>::type> & v) noexcept
0219      : length_(v.size()), data_(v.empty() ? nullptr : v.data())
0220   {}
0221
0222   /*implicit*/ constexpr span(pointer a, size_type const n) noexcept
0223      : length_(n), data_(a)
0224   {}
0225
0226   template<
0227      class InputIterator,
0228      class = typename std::enable_if<
0229         std::is_same<
0230            typename std::remove_cv<T>::type,
0231            typename std::iterator_traits<InputIterator>::value_type
0232         >::value
0233      >::type
0234   >
0235   span(InputIterator start, InputIterator last)
0236      : length_(std::distance(start, last)), data_(&*start)
0237   {}
0238
0239   span(std::initializer_list<T> const& l)
0240      : length_(l.size()), data_(std::begin(l))
0241   {}
0242
0243   span& operator=(span const&) noexcept = default;
0244   span& operator=(span &&) noexcept = delete;
0245
0246   /*
0247    * iterator interfaces
0248    */
0249   constexpr iterator begin() const noexcept
0250   {
0251     return data_;
0252   }
0253   constexpr iterator end() const noexcept
0254   {
0255     return data_ + length_;
0256   }
0257   constexpr const_iterator cbegin() const noexcept
0258   {
0259     return begin();
0260   }
0261   constexpr const_iterator cend() const noexcept
0262   {
0263     return end();
0264   }
0265   reverse_iterator rbegin() const
0266   {
0267     return {end()};
0268   }
0269   reverse_iterator rend() const
0270   {
0271     return {begin()};
0272   }
0273   const_reverse_iterator crbegin() const
0274   {
0275     return rbegin();
0276   }
0277   const_reverse_iterator crend() const
0278   {
0279     return rend();
0280   }
0281
0282   /*
0283    * access
0284    */
0285   constexpr size_type size() const noexcept
0286   {
0287     return length_;
0288   }
0289   constexpr size_type length() const noexcept
0290   {
0291     return size();
0292   }
0293   constexpr size_type max_size() const noexcept
0294   {
0295     return size();
0296   }
0297   constexpr bool empty() const noexcept
0298   {
0299     return length_ == 0;
0300   }
0301   constexpr reference operator[](size_type const n) const noexcept
0302   {
0303     return *(data_ + n);
0304   }
0305   constexpr reference at(size_type const n) const
0306   {
0307     //Works only in C++14
0308     //if (n >= length_) throw std::out_of_range("span::at()");
0309     //return *(data_ + n);
0310     return n >= length_ ? throw std::out_of_range("span::at()") : *(data_ + n);
0311   }
0312   constexpr pointer data() const noexcept
0313   {
0314     return data_;
0315   }
0316   constexpr const_reference front() const noexcept
0317   {
0318     return *data_;
0319   }
0320   constexpr const_reference back() const noexcept
0321   {
0322     return *(data_ + length_ - 1);
0323   }
0324
0325   /*
0326    * slices
0327    */
0328   // slice with indices {{{
0329   // check bound {{{
0330   constexpr span<T> slice(check_bound_t, size_type const pos, size_type const slicelen) const
0331   {
0332     //Works only in C++14
0333     //if (pos >= length_ || pos + slicelen >= length_) {
0334     //  throw std::out_of_range("span::slice()");
0335     //}
0336     //return span<T>{begin() + pos, begin() + pos + slicelen};
0337     return pos >= length_ || pos + slicelen >= length_ ? throw std::out_of_range("span::slice()") : span<T>{begin() + pos, begin() + pos + slicelen};
0338   }
0339   constexpr span<T> slice_before(check_bound_t, size_type const pos) const
0340   {
0341     //Works only in C++14
0342     //if (pos >= length_) {
0343     //  throw std::out_of_range("span::slice()");
0344     //}
0345     //return span<T>{begin(), begin() + pos};
0346     return pos >= length_ ? std::out_of_range("span::slice()") : span<T>{begin(), begin() + pos};
0347   }
0348   constexpr span<T> slice_after(check_bound_t, size_type const pos) const
0349   {
0350     //Works only in C++14
0351     //if (pos >= length_) {
0352     //  throw std::out_of_range("span::slice()");
0353     //}
0354     //return span<T>{begin() + pos, end()};
0355     return pos >= length_ ? std::out_of_range("span::slice()") : span<T>{begin() + pos, end()};
0356   }
0357   // }}}
0358   // not check bound {{{
0359   constexpr span<T> slice(size_type const pos, size_type const slicelen) const
0360   {
0361     return span<T>{begin() + pos, begin() + pos + slicelen};
0362   }
0363   constexpr span<T> slice_before(size_type const pos) const
0364   {
0365     return span<T>{begin(), begin() + pos};
0366   }
0367   constexpr span<T> slice_after(size_type const pos) const
0368   {
0369     return span<T>{begin() + pos, end()};
0370   }
0371   // }}}
0372   // }}}
0373   // slice with iterators {{{
0374   // check bound {{{
0375   constexpr span<T> slice(check_bound_t, iterator start, iterator last) const
0376   {
0377     //Works only in C++14
0378     //if ( start >= end() ||
0379     //     last > end() ||
0380     //     start > last ||
0381     //     static_cast<size_t>(std::distance(start, last > end() ? end() : last)) > length_ - std::distance(begin(), start) ) {
0382     //  throw std::out_of_range("span::slice()");
0383     //}
0384     //return span<T>{start, last > end() ? end() : last};
0385     return ( start >= end() ||
0386              last > end() ||
0387              start > last ||
0388              static_cast<size_t>(std::distance(start, last > end() ? end() : last)) > length_ - std::distance(begin(), start) ) ? throw std::out_of_range("span::slice()") : span<T>{start, last > end() ? end() : last};
0389   }
0390   constexpr span<T> slice_before(check_bound_t, iterator const pos) const
0391   {
0392     //Works only in C++14
0393     //if (pos < begin() || pos > end()) {
0394     //  throw std::out_of_range("span::slice()");
0395     //}
0396     //return span<T>{begin(), pos > end() ? end() : pos};
0397     return pos < begin() || pos > end() ? throw std::out_of_range("span::slice()") : span<T>{begin(), pos > end() ? end() : pos};
0398   }
0399   constexpr span<T> slice_after(check_bound_t, iterator const pos) const
0400   {
0401     //Works only in C++14
0402     // if (pos < begin() || pos > end()) {
0403     //  throw std::out_of_range("span::slice()");
0404     //}
0405     //return span<T>{pos < begin() ? begin() : pos, end()};
0406     return pos < begin() || pos > end() ? throw std::out_of_range("span::slice()") : span<T>{pos < begin() ? begin() : pos, end()};
0407   }
0408   // }}}
0409   // not check bound {{{
0410   constexpr span<T> slice(iterator start, iterator last) const
0411   {
0412     return span<T>{start, last};
0413   }
0414   constexpr span<T> slice_before(iterator const pos) const
0415   {
0416     return span<T>{begin(), pos};
0417   }
0418   constexpr span<T> slice_after(iterator const pos) const
0419   {
0420     return span<T>{pos, end()};
0421   }
0422   // }}}
0423   // }}}
0424
0425   /*
0426    * others
0427    */
0428   template<class Allocator = std::allocator<typename std::remove_cv<T>::type>>
0429   auto to_vector(Allocator const& alloc = Allocator{}) const
0430   -> std::vector<typename std::remove_cv<T>::type, Allocator>
0431   {
0432     return {begin(), end(), alloc};
0433   }
0434
0435   template<size_t N>
0436   auto to_array() const
0437   -> std::array<T, N>
0438   {
0439     return to_array_impl(ROOT::Detail::make_indices<0, N>{});
0440   }
0441 private:
0442   template<size_t... I>
0443   auto to_array_impl(ROOT::Detail::indices<I...>) const
0444   -> std::array<T, sizeof...(I)>
0445   {
0446     return {{(I < length_ ? *(data_ + I) : T{} )...}};
0447   }
0448
0449 private:
0450   size_type length_;
0451   pointer data_;
0452 };
0453 // }}}
0454 } // inline namespace __ROOT
0455 } // namespace std
0456
0457 namespace ROOT {
0458 // compare operators {{{
0459 namespace Detail {
0460
0461 template< class ArrayL, class ArrayR >
0462 inline R__CONSTEXPR_IF_CXX14
0463 bool operator_equal_impl(ArrayL const& lhs, size_t const lhs_size, ArrayR const& rhs, size_t const rhs_size)
0464 {
0465   if (lhs_size != rhs_size) {
0466     return false;
0467   }
0468
0469   auto litr = std::begin(lhs);
0470   auto ritr = std::begin(rhs);
0471   for (; litr != std::end(lhs); ++litr, ++ritr) {
0472     if (!(*litr == *ritr)) {
0473       return false;
0474     }
0475   }
0476
0477   return true;
0478 }
0479 } // namespace Detail
0480 } // namespace ROOT
0481
0482 namespace std {
0483 inline namespace __ROOT {
0484
0485 template<class T1, class T2>
0486 inline constexpr
0487 bool operator==(span<T1> const& lhs, span<T2> const& rhs)
0488 {
0489   return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.length());
0490 }
0491
0492 template<
0493    class T,
0494    class Array,
0495    class = typename std::enable_if<
0496       ROOT::Detail::is_array_class<Array>::value
0497    >::type
0498 >
0499 inline constexpr
0500 bool operator==(span<T> const& lhs, Array const& rhs)
0501 {
0502   return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.size());
0503 }
0504
0505 template<class T1, class T2, size_t N>
0506 inline constexpr
0507 bool operator==(span<T1> const& lhs, T2 const (& rhs)[N])
0508 {
0509   return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, N);
0510 }
0511
0512 template<
0513    class T,
0514    class Array,
0515    class = typename std::enable_if<
0516       is_array<Array>::value
0517    >::type
0518 >
0519 inline constexpr
0520 bool operator!=(span<T> const& lhs, Array const& rhs)
0521 {
0522   return !(lhs == rhs);
0523 }
0524
0525 template<
0526    class Array,
0527    class T,
0528    class = typename std::enable_if<
0529       is_array<Array>::value
0530    >::type
0531 >
0532 inline constexpr
0533 bool operator==(Array const& lhs, span<T> const& rhs)
0534 {
0535   return rhs == lhs;
0536 }
0537
0538 template<
0539    class Array,
0540    class T,
0541    class = typename std::enable_if<
0542       is_array<Array>::value,
0543       Array
0544    >::type
0545 >
0546 inline constexpr
0547 bool operator!=(Array const& lhs, span<T> const& rhs)
0548 {
0549   return !(rhs == lhs);
0550 }
0551 // }}}
0552
0553 // helpers to construct view {{{
0554 template<
0555    class Array,
0556    class = typename std::enable_if<
0557       ROOT::Detail::is_array_class<Array>::value
0558    >::type
0559 >
0560 inline constexpr
0561 auto make_view(Array const& a)
0562 -> span<typename Array::value_type>
0563 {
0564   return {a};
0565 }
0566
0567 template< class T, size_t N>
0568 inline constexpr
0569 span<T> make_view(T const (&a)[N])
0570 {
0571   return {a};
0572 }
0573
0574 template<class T>
0575 inline constexpr
0576 span<T> make_view(T const* p, typename span<T>::size_type const n)
0577 {
0578   return span<T>{p, n};
0579 }
0580
0581 template<class InputIterator, class Result = span<typename std::iterator_traits<InputIterator>::value_type>>
0582 inline constexpr
0583 Result make_view(InputIterator begin, InputIterator end)
0584 {
0585   return Result{begin, end};
0586 }
0587
0588 template<class T>
0589 inline constexpr
0590 span<T> make_view(std::initializer_list<T> const& l)
0591 {
0592   return {l};
0593 }
0594 // }}}
0595
0596 } // inline namespace __ROOT
0597 } // namespace std
0598
0599
0600
0601
0602
0603 #if 0
0604 // This stuff is too complex for our simple use case!
0605
0606 #include <cstddef>
0607 #include <array>
0608 #include <type_traits>
0609
0610 // See N3851
0611
0612 namespace std {
0613
0614 template<int Rank>
0615 class index;
0616
0617 template<int Rank>
0618 class bounds {
0619 public:
0620   static constexpr int rank = Rank;
0621   using reference = ptrdiff_t &;
0622   using const_reference = const ptrdiff_t &;
0623   using size_type = size_t;
0624   using value_type = ptrdiff_t;
0625
0626 private:
0627   std::array<value_type, Rank> m_B;
0628
0629 public:
0630   constexpr bounds() noexcept;
0631
0632   constexpr bounds(value_type b) noexcept: m_B{{b}} { };
0633   //constexpr bounds(const initializer_list<value_type>&) noexcept;
0634   //constexpr bounds(const bounds&) noexcept;
0635   //bounds& operator=(const bounds&) noexcept;
0636
0637   reference operator[](size_type i) noexcept { return m_B[i]; }
0638
0639   constexpr const_reference operator[](
0640      size_type i) const noexcept { return m_B[i]; };
0641
0642
0643   bool operator==(const bounds &rhs) const noexcept;
0644
0645   bool operator!=(const bounds &rhs) const noexcept;
0646
0647   bounds operator+(const index<rank> &rhs) const noexcept;
0648
0649   bounds operator-(const index<rank> &rhs) const noexcept;
0650
0651   bounds &operator+=(const index<rank> &rhs) noexcept;
0652
0653   bounds &operator-=(const index<rank> &rhs) noexcept;
0654
0655   constexpr size_type size() const noexcept;
0656
0657   bool contains(const index<rank> &idx) const noexcept;
0658   //bounds_iterator<rank> begin() const noexcept;
0659   //bounds_iterator<rank> end() const noexcept;
0660
0661 };
0662
0663 //bounds operator+(const index<rank>& lhs, const bounds& rhs) noexcept;
0664
0665 template<int Rank>
0666 class index {
0667 public:
0668   static constexpr int rank = Rank;
0669   using reference = ptrdiff_t &;
0670   using const_reference = const ptrdiff_t &;
0671   using size_type = size_t;
0672   using value_type = ptrdiff_t;
0673
0674 // For index<rank>:
0675   constexpr index() noexcept;
0676
0677   constexpr index(value_type) noexcept;
0678
0679   constexpr index(const initializer_list<value_type> &) noexcept;
0680
0681   constexpr index(const index &) noexcept;
0682
0683   index &operator=(const index &) noexcept;
0684
0685   reference operator[](size_type component_idx) noexcept;
0686
0687   constexpr const_reference operator[](size_type component_idx) const noexcept;
0688
0689   bool operator==(const index &rhs) const noexcept;
0690
0691   bool operator!=(const index &rhs) const noexcept;
0692
0693   index operator+(const index &rhs) const noexcept;
0694
0695   index operator-(const index &rhs) const noexcept;
0696
0697   index &operator+=(const index &rhs) noexcept;
0698
0699   index &operator-=(const index &rhs) noexcept;
0700
0701   index &operator++() noexcept;
0702
0703   index operator++(int) noexcept;
0704
0705   index &operator--() noexcept;
0706
0707   index operator--(int) noexcept;
0708
0709   index operator+() const noexcept;
0710
0711   index operator-() const noexcept;
0712 };
0713
0714 /// Mock-up of future atd::(experimental::)span.
0715 /// Supports only what we need for THist, e.g. Rank := 1.
0716 template<typename ValueType, int Rank = 1>
0717 class span {
0718 public:
0719   static constexpr int rank = Rank;
0720   using size_type = index<rank>;
0721   using bounds_type = bounds<rank>;
0722   using size_type = typename bounds_type::size_type;
0723   using value_type = ValueType;
0724   using pointer = typename std::add_pointer_t<value_type>;
0725   using reference = typename std::add_lvalue_reference_t<value_type>;
0726
0727   constexpr span() noexcept;
0728
0729   constexpr explicit span(std::vector<ValueType> &cont) noexcept;
0730
0731   template<typename ArrayType>
0732   constexpr explicit span(ArrayType &data) noexcept;
0733
0734   template<typename ViewValueType>
0735   constexpr span(const span<ViewValueType, rank> &rhs) noexcept;
0736
0737   template<typename Container>
0738   constexpr span(bounds_type bounds, Container &cont) noexcept;
0739
0740   constexpr span(bounds_type bounds, pointer data) noexcept;
0741
0742   template<typename ViewValueType>
0743   span &operator=(const span<ViewValueType, rank> &rhs) noexcept;
0744
0745   constexpr bounds_type bounds() const noexcept;
0746   constexpr size_type size() const noexcept;
0747   constexpr size_type stride() const noexcept;
0748
0749   constexpr pointer data() const noexcept;
0750   constexpr reference operator[](const size_type& idx) const noexcept;
0751 };
0752
0753 }
0754 #endif // too complex!
0755 #endif // !defined(__cpp_lib_span)
0756 #endif