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   /*implicit*/ span(std::vector<typename std::remove_cv<T>::type> const& v) noexcept
0208      : length_(v.size()), data_(v.empty() ? nullptr : v.data())
0209   {}
0210
0211   /*implicit*/ span(std::vector<typename std::remove_cv<T>::type> & v) noexcept
0212      : length_(v.size()), data_(v.empty() ? nullptr : v.data())
0213   {}
0214
0215   /*implicit*/ constexpr span(pointer a, size_type const n) noexcept
0216      : length_(n), data_(a)
0217   {}
0218
0219   template<
0220      class InputIterator,
0221      class = typename std::enable_if<
0222         std::is_same<
0223            typename std::remove_cv<T>::type,
0224            typename std::iterator_traits<InputIterator>::value_type
0225         >::value
0226      >::type
0227   >
0228   span(InputIterator start, InputIterator last)
0229      : length_(std::distance(start, last)), data_(&*start)
0230   {}
0231
0232   span(std::initializer_list<T> const& l)
0233      : length_(l.size()), data_(std::begin(l))
0234   {}
0235
0236   span& operator=(span const&) noexcept = default;
0237   span& operator=(span &&) noexcept = delete;
0238
0239   /*
0240    * iterator interfaces
0241    */
0242   constexpr iterator begin() const noexcept
0243   {
0244     return data_;
0245   }
0246   constexpr iterator end() const noexcept
0247   {
0248     return data_ + length_;
0249   }
0250   constexpr const_iterator cbegin() const noexcept
0251   {
0252     return begin();
0253   }
0254   constexpr const_iterator cend() const noexcept
0255   {
0256     return end();
0257   }
0258   reverse_iterator rbegin() const
0259   {
0260     return {end()};
0261   }
0262   reverse_iterator rend() const
0263   {
0264     return {begin()};
0265   }
0266   const_reverse_iterator crbegin() const
0267   {
0268     return rbegin();
0269   }
0270   const_reverse_iterator crend() const
0271   {
0272     return rend();
0273   }
0274
0275   /*
0276    * access
0277    */
0278   constexpr size_type size() const noexcept
0279   {
0280     return length_;
0281   }
0282   constexpr size_type length() const noexcept
0283   {
0284     return size();
0285   }
0286   constexpr size_type max_size() const noexcept
0287   {
0288     return size();
0289   }
0290   constexpr bool empty() const noexcept
0291   {
0292     return length_ == 0;
0293   }
0294   constexpr reference operator[](size_type const n) const noexcept
0295   {
0296     return *(data_ + n);
0297   }
0298   constexpr reference at(size_type const n) const
0299   {
0300     //Works only in C++14
0301     //if (n >= length_) throw std::out_of_range("span::at()");
0302     //return *(data_ + n);
0303     return n >= length_ ? throw std::out_of_range("span::at()") : *(data_ + n);
0304   }
0305   constexpr pointer data() const noexcept
0306   {
0307     return data_;
0308   }
0309   constexpr const_reference front() const noexcept
0310   {
0311     return *data_;
0312   }
0313   constexpr const_reference back() const noexcept
0314   {
0315     return *(data_ + length_ - 1);
0316   }
0317
0318   /*
0319    * slices
0320    */
0321   // slice with indices {{{
0322   // check bound {{{
0323   constexpr span<T> slice(check_bound_t, size_type const pos, size_type const slicelen) const
0324   {
0325     //Works only in C++14
0326     //if (pos >= length_ || pos + slicelen >= length_) {
0327     //  throw std::out_of_range("span::slice()");
0328     //}
0329     //return span<T>{begin() + pos, begin() + pos + slicelen};
0330     return pos >= length_ || pos + slicelen >= length_ ? throw std::out_of_range("span::slice()") : span<T>{begin() + pos, begin() + pos + slicelen};
0331   }
0332   constexpr span<T> slice_before(check_bound_t, size_type const pos) const
0333   {
0334     //Works only in C++14
0335     //if (pos >= length_) {
0336     //  throw std::out_of_range("span::slice()");
0337     //}
0338     //return span<T>{begin(), begin() + pos};
0339     return pos >= length_ ? std::out_of_range("span::slice()") : span<T>{begin(), begin() + pos};
0340   }
0341   constexpr span<T> slice_after(check_bound_t, size_type const pos) const
0342   {
0343     //Works only in C++14
0344     //if (pos >= length_) {
0345     //  throw std::out_of_range("span::slice()");
0346     //}
0347     //return span<T>{begin() + pos, end()};
0348     return pos >= length_ ? std::out_of_range("span::slice()") : span<T>{begin() + pos, end()};
0349   }
0350   // }}}
0351   // not check bound {{{
0352   constexpr span<T> slice(size_type const pos, size_type const slicelen) const
0353   {
0354     return span<T>{begin() + pos, begin() + pos + slicelen};
0355   }
0356   constexpr span<T> slice_before(size_type const pos) const
0357   {
0358     return span<T>{begin(), begin() + pos};
0359   }
0360   constexpr span<T> slice_after(size_type const pos) const
0361   {
0362     return span<T>{begin() + pos, end()};
0363   }
0364   // }}}
0365   // }}}
0366   // slice with iterators {{{
0367   // check bound {{{
0368   constexpr span<T> slice(check_bound_t, iterator start, iterator last) const
0369   {
0370     //Works only in C++14
0371     //if ( start >= end() ||
0372     //     last > end() ||
0373     //     start > last ||
0374     //     static_cast<size_t>(std::distance(start, last > end() ? end() : last)) > length_ - std::distance(begin(), start) ) {
0375     //  throw std::out_of_range("span::slice()");
0376     //}
0377     //return span<T>{start, last > end() ? end() : last};
0378     return ( 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) ) ? throw std::out_of_range("span::slice()") : span<T>{start, last > end() ? end() : last};
0382   }
0383   constexpr span<T> slice_before(check_bound_t, iterator const pos) const
0384   {
0385     //Works only in C++14
0386     //if (pos < begin() || pos > end()) {
0387     //  throw std::out_of_range("span::slice()");
0388     //}
0389     //return span<T>{begin(), pos > end() ? end() : pos};
0390     return pos < begin() || pos > end() ? throw std::out_of_range("span::slice()") : span<T>{begin(), pos > end() ? end() : pos};
0391   }
0392   constexpr span<T> slice_after(check_bound_t, iterator const pos) const
0393   {
0394     //Works only in C++14
0395     // if (pos < begin() || pos > end()) {
0396     //  throw std::out_of_range("span::slice()");
0397     //}
0398     //return span<T>{pos < begin() ? begin() : pos, end()};
0399     return pos < begin() || pos > end() ? throw std::out_of_range("span::slice()") : span<T>{pos < begin() ? begin() : pos, end()};
0400   }
0401   // }}}
0402   // not check bound {{{
0403   constexpr span<T> slice(iterator start, iterator last) const
0404   {
0405     return span<T>{start, last};
0406   }
0407   constexpr span<T> slice_before(iterator const pos) const
0408   {
0409     return span<T>{begin(), pos};
0410   }
0411   constexpr span<T> slice_after(iterator const pos) const
0412   {
0413     return span<T>{pos, end()};
0414   }
0415   // }}}
0416   // }}}
0417
0418   /*
0419    * others
0420    */
0421   template<class Allocator = std::allocator<typename std::remove_cv<T>::type>>
0422   auto to_vector(Allocator const& alloc = Allocator{}) const
0423   -> std::vector<typename std::remove_cv<T>::type, Allocator>
0424   {
0425     return {begin(), end(), alloc};
0426   }
0427
0428   template<size_t N>
0429   auto to_array() const
0430   -> std::array<T, N>
0431   {
0432     return to_array_impl(ROOT::Detail::make_indices<0, N>{});
0433   }
0434 private:
0435   template<size_t... I>
0436   auto to_array_impl(ROOT::Detail::indices<I...>) const
0437   -> std::array<T, sizeof...(I)>
0438   {
0439     return {{(I < length_ ? *(data_ + I) : T{} )...}};
0440   }
0441
0442 private:
0443   size_type length_;
0444   pointer data_;
0445 };
0446 // }}}
0447 } // inline namespace __ROOT
0448 } // namespace std
0449
0450 namespace ROOT {
0451 // compare operators {{{
0452 namespace Detail {
0453
0454 template< class ArrayL, class ArrayR >
0455 inline R__CONSTEXPR_IF_CXX14
0456 bool operator_equal_impl(ArrayL const& lhs, size_t const lhs_size, ArrayR const& rhs, size_t const rhs_size)
0457 {
0458   if (lhs_size != rhs_size) {
0459     return false;
0460   }
0461
0462   auto litr = std::begin(lhs);
0463   auto ritr = std::begin(rhs);
0464   for (; litr != std::end(lhs); ++litr, ++ritr) {
0465     if (!(*litr == *ritr)) {
0466       return false;
0467     }
0468   }
0469
0470   return true;
0471 }
0472 } // namespace Detail
0473 } // namespace ROOT
0474
0475 namespace std {
0476 inline namespace __ROOT {
0477
0478 template<class T1, class T2>
0479 inline constexpr
0480 bool operator==(span<T1> const& lhs, span<T2> const& rhs)
0481 {
0482   return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.length());
0483 }
0484
0485 template<
0486    class T,
0487    class Array,
0488    class = typename std::enable_if<
0489       ROOT::Detail::is_array_class<Array>::value
0490    >::type
0491 >
0492 inline constexpr
0493 bool operator==(span<T> const& lhs, Array const& rhs)
0494 {
0495   return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.size());
0496 }
0497
0498 template<class T1, class T2, size_t N>
0499 inline constexpr
0500 bool operator==(span<T1> const& lhs, T2 const (& rhs)[N])
0501 {
0502   return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, N);
0503 }
0504
0505 template<
0506    class T,
0507    class Array,
0508    class = typename std::enable_if<
0509       is_array<Array>::value
0510    >::type
0511 >
0512 inline constexpr
0513 bool operator!=(span<T> const& lhs, Array const& rhs)
0514 {
0515   return !(lhs == rhs);
0516 }
0517
0518 template<
0519    class Array,
0520    class T,
0521    class = typename std::enable_if<
0522       is_array<Array>::value
0523    >::type
0524 >
0525 inline constexpr
0526 bool operator==(Array const& lhs, span<T> const& rhs)
0527 {
0528   return rhs == lhs;
0529 }
0530
0531 template<
0532    class Array,
0533    class T,
0534    class = typename std::enable_if<
0535       is_array<Array>::value,
0536       Array
0537    >::type
0538 >
0539 inline constexpr
0540 bool operator!=(Array const& lhs, span<T> const& rhs)
0541 {
0542   return !(rhs == lhs);
0543 }
0544 // }}}
0545
0546 // helpers to construct view {{{
0547 template<
0548    class Array,
0549    class = typename std::enable_if<
0550       ROOT::Detail::is_array_class<Array>::value
0551    >::type
0552 >
0553 inline constexpr
0554 auto make_view(Array const& a)
0555 -> span<typename Array::value_type>
0556 {
0557   return {a};
0558 }
0559
0560 template< class T, size_t N>
0561 inline constexpr
0562 span<T> make_view(T const (&a)[N])
0563 {
0564   return {a};
0565 }
0566
0567 template<class T>
0568 inline constexpr
0569 span<T> make_view(T const* p, typename span<T>::size_type const n)
0570 {
0571   return span<T>{p, n};
0572 }
0573
0574 template<class InputIterator, class Result = span<typename std::iterator_traits<InputIterator>::value_type>>
0575 inline constexpr
0576 Result make_view(InputIterator begin, InputIterator end)
0577 {
0578   return Result{begin, end};
0579 }
0580
0581 template<class T>
0582 inline constexpr
0583 span<T> make_view(std::initializer_list<T> const& l)
0584 {
0585   return {l};
0586 }
0587 // }}}
0588
0589 } // inline namespace __ROOT
0590 } // namespace std
0591
0592
0593
0594
0595
0596 #if 0
0597 // This stuff is too complex for our simple use case!
0598
0599 #include <cstddef>
0600 #include <array>
0601 #include <type_traits>
0602
0603 // See N3851
0604
0605 namespace std {
0606
0607 template<int Rank>
0608 class index;
0609
0610 template<int Rank>
0611 class bounds {
0612 public:
0613   static constexpr int rank = Rank;
0614   using reference = ptrdiff_t &;
0615   using const_reference = const ptrdiff_t &;
0616   using size_type = size_t;
0617   using value_type = ptrdiff_t;
0618
0619 private:
0620   std::array<value_type, Rank> m_B;
0621
0622 public:
0623   constexpr bounds() noexcept;
0624
0625   constexpr bounds(value_type b) noexcept: m_B{{b}} { };
0626   //constexpr bounds(const initializer_list<value_type>&) noexcept;
0627   //constexpr bounds(const bounds&) noexcept;
0628   //bounds& operator=(const bounds&) noexcept;
0629
0630   reference operator[](size_type i) noexcept { return m_B[i]; }
0631
0632   constexpr const_reference operator[](
0633      size_type i) const noexcept { return m_B[i]; };
0634
0635
0636   bool operator==(const bounds &rhs) const noexcept;
0637
0638   bool operator!=(const bounds &rhs) const noexcept;
0639
0640   bounds operator+(const index<rank> &rhs) const noexcept;
0641
0642   bounds operator-(const index<rank> &rhs) const noexcept;
0643
0644   bounds &operator+=(const index<rank> &rhs) noexcept;
0645
0646   bounds &operator-=(const index<rank> &rhs) noexcept;
0647
0648   constexpr size_type size() const noexcept;
0649
0650   bool contains(const index<rank> &idx) const noexcept;
0651   //bounds_iterator<rank> begin() const noexcept;
0652   //bounds_iterator<rank> end() const noexcept;
0653
0654 };
0655
0656 //bounds operator+(const index<rank>& lhs, const bounds& rhs) noexcept;
0657
0658 template<int Rank>
0659 class index {
0660 public:
0661   static constexpr int rank = Rank;
0662   using reference = ptrdiff_t &;
0663   using const_reference = const ptrdiff_t &;
0664   using size_type = size_t;
0665   using value_type = ptrdiff_t;
0666
0667 // For index<rank>:
0668   constexpr index() noexcept;
0669
0670   constexpr index(value_type) noexcept;
0671
0672   constexpr index(const initializer_list<value_type> &) noexcept;
0673
0674   constexpr index(const index &) noexcept;
0675
0676   index &operator=(const index &) noexcept;
0677
0678   reference operator[](size_type component_idx) noexcept;
0679
0680   constexpr const_reference operator[](size_type component_idx) const noexcept;
0681
0682   bool operator==(const index &rhs) const noexcept;
0683
0684   bool operator!=(const index &rhs) const noexcept;
0685
0686   index operator+(const index &rhs) const noexcept;
0687
0688   index operator-(const index &rhs) const noexcept;
0689
0690   index &operator+=(const index &rhs) noexcept;
0691
0692   index &operator-=(const index &rhs) noexcept;
0693
0694   index &operator++() noexcept;
0695
0696   index operator++(int) noexcept;
0697
0698   index &operator--() noexcept;
0699
0700   index operator--(int) noexcept;
0701
0702   index operator+() const noexcept;
0703
0704   index operator-() const noexcept;
0705 };
0706
0707 /// Mock-up of future atd::(experimental::)span.
0708 /// Supports only what we need for THist, e.g. Rank := 1.
0709 template<typename ValueType, int Rank = 1>
0710 class span {
0711 public:
0712   static constexpr int rank = Rank;
0713   using size_type = index<rank>;
0714   using bounds_type = bounds<rank>;
0715   using size_type = typename bounds_type::size_type;
0716   using value_type = ValueType;
0717   using pointer = typename std::add_pointer_t<value_type>;
0718   using reference = typename std::add_lvalue_reference_t<value_type>;
0719
0720   constexpr span() noexcept;
0721
0722   constexpr explicit span(std::vector<ValueType> &cont) noexcept;
0723
0724   template<typename ArrayType>
0725   constexpr explicit span(ArrayType &data) noexcept;
0726
0727   template<typename ViewValueType>
0728   constexpr span(const span<ViewValueType, rank> &rhs) noexcept;
0729
0730   template<typename Container>
0731   constexpr span(bounds_type bounds, Container &cont) noexcept;
0732
0733   constexpr span(bounds_type bounds, pointer data) noexcept;
0734
0735   template<typename ViewValueType>
0736   span &operator=(const span<ViewValueType, rank> &rhs) noexcept;
0737
0738   constexpr bounds_type bounds() const noexcept;
0739   constexpr size_type size() const noexcept;
0740   constexpr size_type stride() const noexcept;
0741
0742   constexpr pointer data() const noexcept;
0743   constexpr reference operator[](const size_type& idx) const noexcept;
0744 };
0745
0746 }
0747 #endif // too complex!
0748 #endif // !defined(__cpp_lib_span)
0749 #endif