Logo ROOT  
Reference Guide
span.hxx
Go to the documentation of this file.
1/// \file ROOT/span.hxx
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
35namespace ROOT {
36namespace Detail {
37using std::size_t;
38
39// detail meta functions {{{
40template<class Array>
42 static bool const value = false;
43};
44template<class T, size_t N>
45struct is_array_class<std::array<T, N>> {
46 static bool const value = true;
47};
48template<class T>
49struct is_array_class<std::vector<T>> {
50 static bool const value = true;
51};
52template<class T>
53struct is_array_class<std::initializer_list<T>> {
54 static bool const value = true;
55};
56// }}}
57
58// index sequences {{{
59template< size_t... Indices >
60struct indices{
61 static constexpr size_t value[sizeof...(Indices)] = {Indices...};
62};
63
64template<class IndicesType, size_t Next>
66
67template<size_t... Indices, size_t Next>
68struct make_indices_next<indices<Indices...>, Next> {
69 typedef indices<Indices..., (Indices + Next)...> type;
70};
71
72template<class IndicesType, size_t Next, size_t Tail>
74
75template<size_t... Indices, size_t Next, size_t Tail>
76struct make_indices_next2<indices<Indices...>, Next, Tail> {
77 typedef indices<Indices..., (Indices + Next)..., Tail> type;
78};
79
80template<size_t First, size_t Step, size_t N, class = void>
82
83template<size_t First, size_t Step, size_t N>
85 First,
86 Step,
87 N,
88 typename std::enable_if<(N == 0)>::type
89> {
90 typedef indices<> type;
91};
92
93template<size_t First, size_t Step, size_t N>
95 First,
96 Step,
97 N,
98 typename std::enable_if<(N == 1)>::type
99> {
100 typedef indices<First> type;
101};
102
103template<size_t First, size_t Step, size_t N>
104struct make_indices_impl<
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
116template<size_t First, size_t Step, size_t N>
117struct 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
130template<size_t First, size_t Last, size_t Step = 1>
133 First,
134 Step,
135 ((Last - First) + (Step - 1)) / Step
136 >
137{};
138
139template < size_t Start, size_t Last, size_t Step = 1 >
141// }}}
142} // namespace Detail
143}
144
145namespace std {
146
147inline namespace __ROOT {
148
149// span {{{
150
151struct check_bound_t {};
152static constexpr check_bound_t check_bound{};
153
154template<class T>
155class span {
156public:
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<
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 }
426private:
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
434private:
435 index_type length_;
436 pointer data_;
437};
438// }}}
439} // inline namespace __ROOT
440} // namespace std
441
442namespace ROOT {
443// compare operators {{{
444namespace Detail {
445
446template< class ArrayL, class ArrayR >
448bool 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
467namespace std {
468inline namespace __ROOT {
469
470template<class T1, class T2>
471inline constexpr
472bool 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
477template<
478 class T,
479 class Array,
480 class = typename std::enable_if<
482 >::type
483>
484inline constexpr
485bool operator==(span<T> const& lhs, Array const& rhs)
486{
487 return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, rhs.size());
488}
489
490template<class T1, class T2, size_t N>
491inline constexpr
492bool operator==(span<T1> const& lhs, T2 const (& rhs)[N])
493{
494 return ROOT::Detail::operator_equal_impl(lhs, lhs.length(), rhs, N);
495}
496
497template<
498 class T,
499 class Array,
500 class = typename std::enable_if<
501 is_array<Array>::value
502 >::type
503>
504inline constexpr
505bool operator!=(span<T> const& lhs, Array const& rhs)
506{
507 return !(lhs == rhs);
508}
509
510template<
511 class Array,
512 class T,
513 class = typename std::enable_if<
514 is_array<Array>::value
515 >::type
516>
517inline constexpr
518bool operator==(Array const& lhs, span<T> const& rhs)
519{
520 return rhs == lhs;
521}
522
523template<
524 class Array,
525 class T,
526 class = typename std::enable_if<
527 is_array<Array>::value,
528 Array
529 >::type
530>
531inline constexpr
532bool operator!=(Array const& lhs, span<T> const& rhs)
533{
534 return !(rhs == lhs);
535}
536// }}}
537
538// helpers to construct view {{{
539template<
540 class Array,
541 class = typename std::enable_if<
543 >::type
544>
545inline constexpr
546auto make_view(Array const& a)
547-> span<typename Array::value_type>
548{
549 return {a};
550}
551
552template< class T, size_t N>
553inline constexpr
554span<T> make_view(T const (&a)[N])
555{
556 return {a};
557}
558
559template<class T>
560inline constexpr
561span<T> make_view(T const* p, typename span<T>::index_type const n)
562{
563 return span<T>{p, n};
564}
565
566template<class InputIterator, class Result = span<typename std::iterator_traits<InputIterator>::value_type>>
567inline constexpr
568Result make_view(InputIterator begin, InputIterator end)
569{
570 return Result{begin, end};
571}
572
573template<class T>
574inline constexpr
575span<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
597namespace std {
598
599template<int Rank>
600class index;
601
602template<int Rank>
603class bounds {
604public:
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
611private:
612 std::array<value_type, Rank> m_B;
613
614public:
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
650template<int Rank>
651class index {
652public:
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.
701template<typename ValueType, int Rank = 1>
702class span {
703public:
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
#define b(i)
Definition: RSha256.hxx:100
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
Bool_t operator!=(const TDatime &d1, const TDatime &d2)
Definition: TDatime.h:104
Bool_t operator==(const TDatime &d1, const TDatime &d2)
Definition: TDatime.h:102
#define N
int type
Definition: TGX11.cxx:121
Binding & operator=(OUT(*fun)(void))
TString operator+(const TString &s1, const TString &s2)
Use the special concatenation constructor.
Definition: TString.cxx:1499
std::string & operator+=(std::string &left, const TString &right)
Definition: TString.h:478
TTime operator-(const TTime &t1, const TTime &t2)
Definition: TTime.h:83
const Int_t n
Definition: legend1.C:16
#define T2
Definition: md5.inl:146
#define I(x, y, z)
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
typename make_indices_< Start, Last, Step >::type make_indices
Definition: span.hxx:140
double T(double x)
Definition: ChebyshevPol.h:34
void Step(const gsl_rng *r, void *xp, double step_size)
tbb::task_arena is an alias of tbb::interface7::task_arena, which doesn't allow to forward declare tb...
const char * Array
#define R__CONSTEXPR_IF_CXX14
Definition: span.hxx:21
static constexpr size_t value[sizeof...(Indices)]
Definition: span.hxx:61
static bool const value
Definition: span.hxx:42
auto * l
Definition: textangle.C:4
auto * a
Definition: textangle.C:12