Logo ROOT   master
Reference Guide
span.hxx
Go to the documentation of this file.
1 /// \file ROOT/rhysd_span.h
2 /// \ingroup Base StdExt
3 /// \author Axel Naumann <axel@cern.ch>
4 /// \date 2015-09-06
5 
6 /*************************************************************************
7  * Copyright (C) 1995-2015, Rene Brun and Fons Rademakers. *
8  * All rights reserved. *
9  * *
10  * For the licensing terms see $ROOTSYS/LICENSE. *
11  * For the list of contributors see $ROOTSYS/README/CREDITS. *
12  *************************************************************************/
13 
14 #ifndef ROOT_RHYSD_SPAN_H
15 #define ROOT_RHYSD_SPAN_H
16 
17 // Necessary to compile in c++11 mode
18 #if __cplusplus >= 201402L
19 #define R__CONSTEXPR_IF_CXX14 constexpr
20 #else
21 #define R__CONSTEXPR_IF_CXX14
22 #endif
23 
24 // From https://github.com/rhysd/array_view/blob/master/include/array_view.hpp
25 
26 #include <cstddef>
27 #include <iterator>
28 #include <array>
29 #include <vector>
30 #include <stdexcept>
31 #include <memory>
32 #include <type_traits>
33 #include <initializer_list>
34 
35 namespace ROOT {
36 namespace Detail {
37 using std::size_t;
38 
39 // detail meta functions {{{
40 template<class Array>
42  static bool const value = false;
43 };
44 template<class T, size_t N>
45 struct is_array_class<std::array<T, N>> {
46  static bool const value = true;
47 };
48 template<class T>
49 struct is_array_class<std::vector<T>> {
50  static bool const value = true;
51 };
52 template<class T>
53 struct is_array_class<std::initializer_list<T>> {
54  static bool const value = true;
55 };
56 // }}}
57 
58 // index sequences {{{
59 template< size_t... Indices >
60 struct indices{
61  static constexpr size_t value[sizeof...(Indices)] = {Indices...};
62 };
63 
64 template<class IndicesType, size_t Next>
66 
67 template<size_t... Indices, size_t Next>
68 struct make_indices_next<indices<Indices...>, Next> {
69  typedef indices<Indices..., (Indices + Next)...> type;
70 };
71 
72 template<class IndicesType, size_t Next, size_t Tail>
74 
75 template<size_t... Indices, size_t Next, size_t Tail>
76 struct make_indices_next2<indices<Indices...>, Next, Tail> {
77  typedef indices<Indices..., (Indices + Next)..., Tail> type;
78 };
79 
80 template<size_t First, size_t Step, size_t N, class = void>
82 
83 template<size_t First, size_t Step, size_t N>
84 struct make_indices_impl<
85  First,
86  Step,
87  N,
88  typename std::enable_if<(N == 0)>::type
89 > {
90  typedef indices<> type;
91 };
92 
93 template<size_t First, size_t Step, size_t N>
94 struct make_indices_impl<
95  First,
96  Step,
97  N,
98  typename std::enable_if<(N == 1)>::type
99 > {
100  typedef indices<First> type;
101 };
102 
103 template<size_t First, size_t Step, size_t N>
105  First,
106  Step,
107  N,
108  typename std::enable_if<(N > 1 && N % 2 == 0)>::type
109 >
111  typename ROOT::Detail::make_indices_impl<First, Step, N / 2>::type,
112  First + N / 2 * Step
113  >
114 {};
115 
116 template<size_t First, size_t Step, size_t N>
117 struct make_indices_impl<
118  First,
119  Step,
120  N,
121  typename std::enable_if<(N > 1 && N % 2 == 1)>::type
122 >
124  typename ROOT::Detail::make_indices_impl<First, Step, N / 2>::type,
125  First + N / 2 * Step,
126  First + (N - 1) * Step
127  >
128 {};
129 
130 template<size_t First, size_t Last, size_t Step = 1>
133  First,
134  Step,
135  ((Last - First) + (Step - 1)) / Step
136  >
137 {};
138 
139 template < size_t Start, size_t Last, size_t Step = 1 >
141 // }}}
142 } // namespace Detail
143 }
144 
145 namespace std {
146 
147 inline namespace __ROOT {
148 
149 // span {{{
150 
151 struct check_bound_t {};
152 static constexpr check_bound_t check_bound{};
153 
154 template<class T>
155 class span {
156 public:
157  /*
158  * types
159  */
160  typedef T element_type;
161  typedef std::remove_cv<T> value_type;
162  typedef element_type * pointer;
163  typedef element_type const* const_pointer;
164  typedef element_type & reference;
165  typedef element_type const& const_reference;
166  typedef element_type * iterator;
167  typedef element_type const* const_iterator;
168  typedef ptrdiff_t difference_type;
169  typedef std::size_t index_type;
170  typedef std::reverse_iterator<iterator> reverse_iterator;
171  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
172 
173  /*
174  * ctors and assign operators
175  */
176  constexpr span() noexcept
177  : length_(0), data_(nullptr)
178  {}
179 
180  constexpr span(span const&) noexcept = default;
181  constexpr span(span &&) noexcept = default;
182 
183  // Note:
184  // This constructor can't be constexpr because & operator can't be constexpr.
185  template<index_type N>
186  /*implicit*/ span(std::array<T, N> & a) noexcept
187  : length_(N), data_(N > 0 ? a.data() : nullptr)
188  {}
189 
190  // Note:
191  // This constructor can't be constexpr because & operator can't be constexpr.
192  template<index_type N>
193  /*implicit*/ span(T(& a)[N]) noexcept
194  : length_(N), data_(N > 0 ? std::addressof(a[0]) : nullptr)
195  {
196  static_assert(N > 0, "Zero-length array is not permitted in ISO C++.");
197  }
198 
199  /*implicit*/ span(std::vector<typename std::remove_cv<T>::type> const& v) noexcept
200  : length_(v.size()), data_(v.empty() ? nullptr : v.data())
201  {}
202 
203  /*implicit*/ span(std::vector<typename std::remove_cv<T>::type> & v) noexcept
204  : length_(v.size()), data_(v.empty() ? nullptr : v.data())
205  {}
206 
207  /*implicit*/ constexpr span(pointer a, index_type const n) noexcept
208  : length_(n), data_(a)
209  {}
210 
211  template<
212  class InputIterator,
213  class = typename std::enable_if<
214  std::is_same<
215  typename std::remove_cv<T>::type,
216  typename std::iterator_traits<InputIterator>::value_type
217  >::value
218  >::type
219  >
220  span(InputIterator start, InputIterator last)
221  : length_(std::distance(start, last)), data_(&*start)
222  {}
223 
224  span(std::initializer_list<T> const& l)
225  : length_(l.size()), data_(std::begin(l))
226  {}
227 
228  span& operator=(span const&) noexcept = default;
229  span& operator=(span &&) noexcept = delete;
230 
231  /*
232  * iterator interfaces
233  */
234  constexpr iterator begin() const noexcept
235  {
236  return data_;
237  }
238  constexpr iterator end() const noexcept
239  {
240  return data_ + length_;
241  }
242  constexpr const_iterator cbegin() const noexcept
243  {
244  return begin();
245  }
246  constexpr const_iterator cend() const noexcept
247  {
248  return end();
249  }
250  reverse_iterator rbegin() const
251  {
252  return {end()};
253  }
254  reverse_iterator rend() const
255  {
256  return {begin()};
257  }
258  const_reverse_iterator crbegin() const
259  {
260  return rbegin();
261  }
262  const_reverse_iterator crend() const
263  {
264  return rend();
265  }
266 
267  /*
268  * access
269  */
270  constexpr index_type size() const noexcept
271  {
272  return length_;
273  }
274  constexpr index_type length() const noexcept
275  {
276  return size();
277  }
278  constexpr index_type max_size() const noexcept
279  {
280  return size();
281  }
282  constexpr bool empty() const noexcept
283  {
284  return length_ == 0;
285  }
286  constexpr reference operator[](index_type const n) const noexcept
287  {
288  return *(data_ + n);
289  }
290  constexpr reference at(index_type const n) const
291  {
292  //Works only in C++14
293  //if (n >= length_) throw std::out_of_range("span::at()");
294  //return *(data_ + n);
295  return n >= length_ ? throw std::out_of_range("span::at()") : *(data_ + n);
296  }
297  constexpr pointer data() const noexcept
298  {
299  return data_;
300  }
301  constexpr const_reference front() const noexcept
302  {
303  return *data_;
304  }
305  constexpr const_reference back() const noexcept
306  {
307  return *(data_ + length_ - 1);
308  }
309 
310  /*
311  * slices
312  */
313  // slice with indices {{{
314  // check bound {{{
315  constexpr span<T> slice(check_bound_t, index_type const pos, index_type const slicelen) const
316  {
317  //Works only in C++14
318  //if (pos >= length_ || pos + slicelen >= length_) {
319  // throw std::out_of_range("span::slice()");
320  //}
321  //return span<T>{begin() + pos, begin() + pos + slicelen};
322  return pos >= length_ || pos + slicelen >= length_ ? throw std::out_of_range("span::slice()") : span<T>{begin() + pos, begin() + pos + slicelen};
323  }
324  constexpr span<T> slice_before(check_bound_t, index_type const pos) const
325  {
326  //Works only in C++14
327  //if (pos >= length_) {
328  // throw std::out_of_range("span::slice()");
329  //}
330  //return span<T>{begin(), begin() + pos};
331  return pos >= length_ ? std::out_of_range("span::slice()") : span<T>{begin(), begin() + pos};
332  }
333  constexpr span<T> slice_after(check_bound_t, index_type const pos) const
334  {
335  //Works only in C++14
336  //if (pos >= length_) {
337  // throw std::out_of_range("span::slice()");
338  //}
339  //return span<T>{begin() + pos, end()};
340  return pos >= length_ ? std::out_of_range("span::slice()") : span<T>{begin() + pos, end()};
341  }
342  // }}}
343  // not check bound {{{
344  constexpr span<T> slice(index_type const pos, index_type const slicelen) const
345  {
346  return span<T>{begin() + pos, begin() + pos + slicelen};
347  }
348  constexpr span<T> slice_before(index_type const pos) const
349  {
350  return span<T>{begin(), begin() + pos};
351  }
352  constexpr span<T> slice_after(index_type const pos) const
353  {
354  return span<T>{begin() + pos, end()};
355  }
356  // }}}
357  // }}}
358  // slice with iterators {{{
359  // check bound {{{
360  constexpr span<T> slice(check_bound_t, iterator start, iterator last) const
361  {
362  //Works only in C++14
363  //if ( start >= end() ||
364  // last > end() ||
365  // start > last ||
366  // static_cast<size_t>(std::distance(start, last > end() ? end() : last)) > length_ - std::distance(begin(), start) ) {
367  // throw std::out_of_range("span::slice()");
368  //}
369  //return span<T>{start, last > end() ? end() : last};
370  return ( start >= end() ||
371  last > end() ||
372  start > last ||
373  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};
374  }
375  constexpr span<T> slice_before(check_bound_t, iterator const pos) const
376  {
377  //Works only in C++14
378  //if (pos < begin() || pos > end()) {
379  // throw std::out_of_range("span::slice()");
380  //}
381  //return span<T>{begin(), pos > end() ? end() : pos};
382  return pos < begin() || pos > end() ? throw std::out_of_range("span::slice()") : span<T>{begin(), pos > end() ? end() : pos};
383  }
384  constexpr span<T> slice_after(check_bound_t, iterator const pos) const
385  {
386  //Works only in C++14
387  // if (pos < begin() || pos > end()) {
388  // throw std::out_of_range("span::slice()");
389  //}
390  //return span<T>{pos < begin() ? begin() : pos, end()};
391  return pos < begin() || pos > end() ? throw std::out_of_range("span::slice()") : span<T>{pos < begin() ? begin() : pos, end()};
392  }
393  // }}}
394  // not check bound {{{
395  constexpr span<T> slice(iterator start, iterator last) const
396  {
397  return span<T>{start, last};
398  }
399  constexpr span<T> slice_before(iterator const pos) const
400  {
401  return span<T>{begin(), pos};
402  }
403  constexpr span<T> slice_after(iterator const pos) const
404  {
405  return span<T>{pos, end()};
406  }
407  // }}}
408  // }}}
409 
410  /*
411  * others
412  */
414  auto to_vector(Allocator const& alloc = Allocator{}) const
415  -> std::vector<typename std::remove_cv<T>::type, Allocator>
416  {
417  return {begin(), end(), alloc};
418  }
419 
420  template<size_t N>
421  auto to_array() const
422  -> std::array<T, N>
423  {
424  return to_array_impl(ROOT::Detail::make_indices<0, N>{});
425  }
426 private:
427  template<size_t... I>
428  auto to_array_impl(ROOT::Detail::indices<I...>) const
429  -> std::array<T, sizeof...(I)>
430  {
431  return {{(I < length_ ? *(data_ + I) : T{} )...}};
432  }
433 
434 private:
435  index_type length_;
436  pointer data_;
437 };
438 // }}}
439 } // inline namespace __ROOT
440 } // namespace std
441 
442 namespace ROOT {
443 // compare operators {{{
444 namespace Detail {
445 
446 template< class ArrayL, class ArrayR >
448 bool operator_equal_impl(ArrayL const& lhs, size_t const lhs_size, ArrayR const& rhs, size_t const rhs_size)
449 {
450  if (lhs_size != rhs_size) {
451  return false;
452  }
453 
454  auto litr = std::begin(lhs);
455  auto ritr = std::begin(rhs);
456  for (; litr != std::end(lhs); ++litr, ++ritr) {
457  if (!(*litr == *ritr)) {
458  return false;
459  }
460  }
461 
462  return true;
463 }
464 } // namespace Detail
465 } // namespace ROOT
466 
467 namespace std {
468 inline namespace __ROOT {
469 
470 template<class T1, class T2>
471 inline constexpr
472 bool operator==(span<T1> const& lhs, span<T2> const& rhs)
473 {
474  return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.length());
475 }
476 
477 template<
478  class T,
479  class Array,
480  class = typename std::enable_if<
482  >::type
483 >
484 inline constexpr
485 bool operator==(span<T> const& lhs, Array const& rhs)
486 {
487  return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.size());
488 }
489 
490 template<class T1, class T2, size_t N>
491 inline constexpr
492 bool operator==(span<T1> const& lhs, T2 const (& rhs)[N])
493 {
494  return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, N);
495 }
496 
497 template<
498  class T,
499  class Array,
500  class = typename std::enable_if<
501  is_array<Array>::value
502  >::type
503 >
504 inline constexpr
505 bool operator!=(span<T> const& lhs, Array const& rhs)
506 {
507  return !(lhs == rhs);
508 }
509 
510 template<
511  class Array,
512  class T,
513  class = typename std::enable_if<
514  is_array<Array>::value
515  >::type
516 >
517 inline constexpr
518 bool operator==(Array const& lhs, span<T> const& rhs)
519 {
520  return rhs == lhs;
521 }
522 
523 template<
524  class Array,
525  class T,
526  class = typename std::enable_if<
527  is_array<Array>::value,
528  Array
529  >::type
530 >
531 inline constexpr
532 bool operator!=(Array const& lhs, span<T> const& rhs)
533 {
534  return !(rhs == lhs);
535 }
536 // }}}
537 
538 // helpers to construct view {{{
539 template<
540  class Array,
541  class = typename std::enable_if<
543  >::type
544 >
545 inline constexpr
546 auto make_view(Array const& a)
547 -> span<typename Array::value_type>
548 {
549  return {a};
550 }
551 
552 template< class T, size_t N>
553 inline constexpr
554 span<T> make_view(T const (&a)[N])
555 {
556  return {a};
557 }
558 
559 template<class T>
560 inline constexpr
561 span<T> make_view(T const* p, typename span<T>::index_type const n)
562 {
563  return span<T>{p, n};
564 }
565 
566 template<class InputIterator, class Result = span<typename std::iterator_traits<InputIterator>::value_type>>
567 inline constexpr
568 Result make_view(InputIterator begin, InputIterator end)
569 {
570  return Result{begin, end};
571 }
572 
573 template<class T>
574 inline constexpr
575 span<T> make_view(std::initializer_list<T> const& l)
576 {
577  return {l};
578 }
579 // }}}
580 
581 } // inline namespace __ROOT
582 } // namespace std
583 
584 
585 
586 
587 
588 #if 0
589 // This stuff is too complex for our simple use case!
590 
591 #include <cstddef>
592 #include <array>
593 #include <type_traits>
594 
595 // See N3851
596 
597 namespace std {
598 
599 template<int Rank>
600 class index;
601 
602 template<int Rank>
603 class bounds {
604 public:
605  static constexpr int rank = Rank;
606  using reference = ptrdiff_t &;
607  using const_reference = const ptrdiff_t &;
608  using size_type = size_t;
609  using value_type = ptrdiff_t;
610 
611 private:
612  std::array<value_type, Rank> m_B;
613 
614 public:
615  constexpr bounds() noexcept;
616 
617  constexpr bounds(value_type b) noexcept: m_B{{b}} { };
618  //constexpr bounds(const initializer_list<value_type>&) noexcept;
619  //constexpr bounds(const bounds&) noexcept;
620  //bounds& operator=(const bounds&) noexcept;
621 
622  reference operator[](size_type i) noexcept { return m_B[i]; }
623 
624  constexpr const_reference operator[](
625  size_type i) const noexcept { return m_B[i]; };
626 
627 
628  bool operator==(const bounds &rhs) const noexcept;
629 
630  bool operator!=(const bounds &rhs) const noexcept;
631 
632  bounds operator+(const index<rank> &rhs) const noexcept;
633 
634  bounds operator-(const index<rank> &rhs) const noexcept;
635 
636  bounds &operator+=(const index<rank> &rhs) noexcept;
637 
638  bounds &operator-=(const index<rank> &rhs) noexcept;
639 
640  constexpr size_type size() const noexcept;
641 
642  bool contains(const index<rank> &idx) const noexcept;
643  //bounds_iterator<rank> begin() const noexcept;
644  //bounds_iterator<rank> end() const noexcept;
645 
646 };
647 
648 //bounds operator+(const index<rank>& lhs, const bounds& rhs) noexcept;
649 
650 template<int Rank>
651 class index {
652 public:
653  static constexpr int rank = Rank;
654  using reference = ptrdiff_t &;
655  using const_reference = const ptrdiff_t &;
656  using size_type = size_t;
657  using value_type = ptrdiff_t;
658 
659 // For index<rank>:
660  constexpr index() noexcept;
661 
662  constexpr index(value_type) noexcept;
663 
664  constexpr index(const initializer_list<value_type> &) noexcept;
665 
666  constexpr index(const index &) noexcept;
667 
668  index &operator=(const index &) noexcept;
669 
670  reference operator[](size_type component_idx) noexcept;
671 
672  constexpr const_reference operator[](size_type component_idx) const noexcept;
673 
674  bool operator==(const index &rhs) const noexcept;
675 
676  bool operator!=(const index &rhs) const noexcept;
677 
678  index operator+(const index &rhs) const noexcept;
679 
680  index operator-(const index &rhs) const noexcept;
681 
682  index &operator+=(const index &rhs) noexcept;
683 
684  index &operator-=(const index &rhs) noexcept;
685 
686  index &operator++() noexcept;
687 
688  index operator++(int) noexcept;
689 
690  index &operator--() noexcept;
691 
692  index operator--(int) noexcept;
693 
694  index operator+() const noexcept;
695 
696  index operator-() const noexcept;
697 };
698 
699 /// Mock-up of future atd::(experimental::)span.
700 /// Supports only what we need for THist, e.g. Rank := 1.
701 template<typename ValueType, int Rank = 1>
702 class span {
703 public:
704  static constexpr int rank = Rank;
705  using index_type = index<rank>;
706  using bounds_type = bounds<rank>;
707  using size_type = typename bounds_type::size_type;
708  using value_type = ValueType;
709  using pointer = typename std::add_pointer_t<value_type>;
710  using reference = typename std::add_lvalue_reference_t<value_type>;
711 
712  constexpr span() noexcept;
713 
714  constexpr explicit span(std::vector<ValueType> &cont) noexcept;
715 
716  template<typename ArrayType>
717  constexpr explicit span(ArrayType &data) noexcept;
718 
719  template<typename ViewValueType>
720  constexpr span(const span<ViewValueType, rank> &rhs) noexcept;
721 
722  template<typename Container>
723  constexpr span(bounds_type bounds, Container &cont) noexcept;
724 
725  constexpr span(bounds_type bounds, pointer data) noexcept;
726 
727  template<typename ViewValueType>
728  span &operator=(const span<ViewValueType, rank> &rhs) noexcept;
729 
730  constexpr bounds_type bounds() const noexcept;
731  constexpr size_type size() const noexcept;
732  constexpr index_type stride() const noexcept;
733 
734  constexpr pointer data() const noexcept;
735  constexpr reference operator[](const index_type& idx) const noexcept;
736 };
737 
738 }
739 #endif // too complex!
740 #endif
Returns the available number of logical cores.
Definition: StringConv.hxx:21
double T(double x)
Definition: ChebyshevPol.h:34
void Step(const gsl_rng *r, void *xp, double step_size)
#define N
STL namespace.
static constexpr size_t value[sizeof...(Indices)]
Definition: span.hxx:61
typename make_indices_< Start, Last, Step >::type make_indices
Definition: span.hxx:140
R__CONSTEXPR_IF_CXX14 bool operator_equal_impl(ArrayL const &lhs, size_t const lhs_size, ArrayR const &rhs, size_t const rhs_size)
Definition: span.hxx:448
TTime operator-(const TTime &t1, const TTime &t2)
Definition: TTime.h:83
#define R__CONSTEXPR_IF_CXX14
Definition: span.hxx:21
Bool_t operator!=(const TDatime &d1, const TDatime &d2)
Definition: TDatime.h:104
TString operator+(const TString &s1, const TString &s2)
Use the special concatenation constructor.
Definition: TString.cxx:1474
const char * Array
auto * a
Definition: textangle.C:12
static bool const value
Definition: span.hxx:42
int type
Definition: TGX11.cxx:120
#define T2
Definition: md5.inl:146
Binding & operator=(OUT(*fun)(void))
Bool_t operator==(const TDatime &d1, const TDatime &d2)
Definition: TDatime.h:102
auto * l
Definition: textangle.C:4
you should not use this method at all Int_t Int_t Double_t Double_t Double_t Int_t Double_t Double_t Double_t Double_t b
Definition: TRolke.cxx:630
#define I(x, y, z)
const Int_t n
Definition: legend1.C:16
std::string & operator+=(std::string &left, const TString &right)
Definition: TString.h:473