Horizon
span.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Casey Carter 2016-2017
5 //
6 // Use, modification and distribution is subject to the
7 // Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //
11 // Project home: https://github.com/ericniebler/range-v3
12 //
13 
14 #ifndef RANGES_V3_VIEW_SPAN_HPP
15 #define RANGES_V3_VIEW_SPAN_HPP
16 
17 #include <cstddef>
18 
19 #include <meta/meta.hpp>
20 
21 #include <range/v3/range_fwd.hpp>
22 
31 
32 #include <range/v3/detail/prologue.hpp>
33 
34 namespace ranges
35 {
38 
40  namespace detail
41  {
42  using span_index_t = std::ptrdiff_t;
43  } // namespace detail
45 
46  constexpr detail::span_index_t dynamic_extent = -1;
47 
49  namespace detail
50  {
51  template(typename To, typename From)(
52  requires integral<To> AND integral<From>)
53  constexpr To narrow_cast(From from) noexcept
54  {
55  using C = common_type_t<To, From>;
56  return RANGES_EXPECT((from > 0) == (static_cast<To>(from) > 0)),
57  RANGES_EXPECT(static_cast<C>(from) ==
58  static_cast<C>(static_cast<To>(from))),
59  static_cast<To>(from);
60  }
61 
62  template<typename T>
63  constexpr span_index_t byte_size(span_index_t n) noexcept
64  {
65  return n == dynamic_extent ? dynamic_extent
66  : (RANGES_EXPECT(n >= 0),
67  RANGES_EXPECT(narrow_cast<std::size_t>(n) <=
68  PTRDIFF_MAX / sizeof(T)),
69  n * narrow_cast<span_index_t>(sizeof(T)));
70  }
71 
72  template<span_index_t N>
73  struct span_extent
74  {
75  CPP_assert(N >= 0);
76 
77  constexpr span_extent() noexcept = default;
78  constexpr span_extent(span_index_t size) noexcept
79  // this constructor does nothing, the delegation exists only
80  // to provide a place for the contract check expression.
81  : span_extent{(RANGES_EXPECT(size == N), tag{})}
82  {}
83 
84  constexpr span_index_t size() const noexcept
85  {
86  return N;
87  }
88 
89  private:
90  struct tag
91  {};
92  constexpr span_extent(tag) noexcept
93  {}
94  };
95  template<>
96  struct span_extent<dynamic_extent>
97  {
98  span_extent() = default;
99  constexpr span_extent(span_index_t size) noexcept
100  : size_{((void)RANGES_EXPECT(size >= 0), size)}
101  {}
102  constexpr span_index_t size() const noexcept
103  {
104  return size_;
105  }
106 
107  private:
108  span_index_t size_ = 0;
109  };
110 
111  constexpr span_index_t subspan_extent(span_index_t Extent, span_index_t Offset,
112  span_index_t Count) noexcept
113  {
114  return Count == dynamic_extent && Extent != dynamic_extent ? Extent - Offset
115  : Count;
116  }
117  } // namespace detail
118 
119  // clang-format off
122  template(typename Rng, typename T)(
123  concept (span_compatible_range_)(Rng, T),
124  detail::is_convertible<detail::element_t<Rng>(*)[], T(*)[]>::value
125  );
128  template<typename Rng, typename T>
129  CPP_concept span_compatible_range =
130  sized_range<Rng> && contiguous_range<Rng> &&
131  CPP_concept_ref(ranges::span_compatible_range_, Rng, T);
132 
135  template<typename Rng, detail::span_index_t N>
136  CPP_concept span_dynamic_conversion =
137  N == dynamic_extent ||
138  range_cardinality<Rng>::value < cardinality();
139 
142  template<typename Rng, detail::span_index_t N>
143  CPP_concept span_static_conversion =
144  N != dynamic_extent && range_cardinality<Rng>::value == N;
145  // clang-format on
147 
148  template<typename T, detail::span_index_t N = dynamic_extent>
149  struct RANGES_EMPTY_BASES span
150  : public view_interface<
151  span<T, N>, (N == dynamic_extent ? finite : static_cast<cardinality>(N))>
152  , public detail::span_extent<N>
153  {
154  CPP_assert(std::is_object<T>::value);
155 
156  using element_type = T;
157  using value_type = meta::_t<std::remove_cv<T>>;
158  using index_type = detail::span_index_t;
159  using difference_type = index_type;
160  using pointer = T *;
161  using reference = T &;
162  using iterator = T *;
164 
165  static constexpr index_type extent = N;
166 
167  constexpr span() noexcept = default;
168  constexpr span(pointer ptr, index_type cnt) noexcept
169  : detail::span_extent<N>{(RANGES_EXPECT(cnt >= 0), cnt)}
170  , data_{(RANGES_EXPECT(0 == cnt || ptr != nullptr), ptr)}
171  {}
172  template<typename = void> // Artificially templatize so that the other
173  // constructor is preferred for {ptr, 0}
174  constexpr span(pointer first, pointer last) noexcept
175  : span{first, last - first}
176  {}
177 
178  template(typename Rng)(
179  requires (!same_as<span, uncvref_t<Rng>>) AND
180  span_compatible_range<Rng, T> AND
181  span_dynamic_conversion<Rng, N>)
182  constexpr span(Rng && rng) noexcept(noexcept(ranges::data(rng),
183  ranges::size(rng)))
184  : span{ranges::data(rng), detail::narrow_cast<index_type>(ranges::size(rng))}
185  {}
186 
187  template(typename Rng)(
188  requires (!same_as<span, uncvref_t<Rng>>) AND
189  span_compatible_range<Rng, T> AND
190  span_static_conversion<Rng, N>)
191  constexpr span(Rng && rng) noexcept(noexcept(ranges::data(rng)))
192  : span{ranges::data(rng), N}
193  {}
194 
195  template<index_type Count>
196  constexpr span<T, Count> first() const noexcept
197  {
198  static_assert(Count >= 0, "Count of elements to extract cannot be negative.");
199  static_assert(
200  N == dynamic_extent || Count <= N,
201  "Count of elements to extract must be less than the static span extent.");
202  return RANGES_EXPECT(Count <= size()),
203  RANGES_EXPECT(Count == 0 || data_ != nullptr),
204  span<T, Count>{data_, Count};
205  }
206  constexpr span<T> first(index_type cnt) const noexcept
207  {
208  return RANGES_EXPECT(cnt >= 0 && cnt <= size()),
209  RANGES_EXPECT(cnt == 0 || data_ != nullptr), span<T>{data_, cnt};
210  }
211 
212  template<index_type Count>
213  constexpr span<T, Count> last() const noexcept
214  {
215  static_assert(Count >= 0, "Count of elements to extract cannot be negative.");
216  static_assert(
217  N == dynamic_extent || Count <= N,
218  "Count of elements to extract must be less than the static span extent.");
219  return RANGES_EXPECT(Count <= size()),
220  RANGES_EXPECT((Count == 0 && size() == 0) || data_ != nullptr),
221  span<T, Count>{data_ + size() - Count, Count};
222  }
223  constexpr span<T> last(index_type cnt) const noexcept
224  {
225  return RANGES_EXPECT(cnt >= 0 && cnt <= size()),
226  RANGES_EXPECT((cnt == 0 && size() == 0) || data_ != nullptr),
227  span<T>{data_ + size() - cnt, cnt};
228  }
229 
230  template<index_type Offset, index_type Count>
231  constexpr span<T, detail::subspan_extent(N, Offset, Count)> subspan() const
232  noexcept
233  {
234  static_assert(Offset >= 0,
235  "Offset of first element to extract cannot be negative.");
236  static_assert(Count >= dynamic_extent,
237  "Count of elements to extract cannot be negative.");
238  static_assert(
239  N == dynamic_extent ||
240  N >= Offset + (Count == dynamic_extent ? 0 : Count),
241  "Sequence of elements to extract must be within the static span extent.");
242  return RANGES_EXPECT(size() >=
243  Offset + (Count == dynamic_extent ? 0 : Count)),
244  RANGES_EXPECT((Offset == 0 && Count <= 0) || data_ != nullptr),
245  span<T, detail::subspan_extent(N, Offset, Count)>{
246  data_ + Offset, Count == dynamic_extent ? size() - Offset : Count};
247  }
248  template<index_type Offset>
249  constexpr span<T, (N >= Offset ? N - Offset : dynamic_extent)> subspan() const
250  noexcept
251  {
252  static_assert(Offset >= 0,
253  "Offset of first element to extract cannot be negative.");
254  static_assert(N == dynamic_extent || N >= Offset,
255  "Offset of first element to extract must be within the static "
256  "span extent.");
257  return RANGES_EXPECT(size() >= Offset),
258  RANGES_EXPECT((Offset == 0 && size() == 0) || data_ != nullptr),
259  span < T,
260  N >= Offset ? N - Offset
261  : dynamic_extent > {data_ + Offset, size() - Offset};
262  }
263  constexpr span<T, dynamic_extent> subspan(index_type offset) const noexcept
264  {
265  return RANGES_EXPECT(offset >= 0), RANGES_EXPECT(size() >= offset),
266  RANGES_EXPECT((offset == 0 && size() == 0) || data_ != nullptr),
267  span<T, dynamic_extent>{data_ + offset, size() - offset};
268  }
269  constexpr span<T, dynamic_extent> subspan(index_type offset, index_type cnt) const
270  noexcept
271  {
272  return RANGES_EXPECT(offset >= 0), RANGES_EXPECT(cnt >= 0),
273  RANGES_EXPECT(size() >= offset + cnt),
274  RANGES_EXPECT((offset == 0 && cnt == 0) || data_ != nullptr),
275  span<T, dynamic_extent>{data_ + offset, cnt};
276  }
277 
278  constexpr pointer data() const noexcept
279  {
280  return data_;
281  }
283  constexpr index_type size_bytes() const noexcept
284  {
285  return detail::byte_size<T>(size());
286  }
287  constexpr bool empty() const noexcept
288  {
289  return size() == 0;
290  }
291 
292  constexpr reference operator[](index_type idx) const noexcept
293  {
294  return RANGES_EXPECT(idx >= 0), RANGES_EXPECT(idx < size()),
295  RANGES_EXPECT(data_), data_[idx];
296  }
297 
298  constexpr iterator begin() const noexcept
299  {
300  return RANGES_EXPECT(!size() || data_), data_;
301  }
302  constexpr iterator end() const noexcept
303  {
304  return RANGES_EXPECT(!size() || data_), data_ + size();
305  }
306  constexpr reverse_iterator rbegin() const noexcept
307  {
308  return reverse_iterator{end()};
309  }
310  constexpr reverse_iterator rend() const noexcept
311  {
312  return reverse_iterator{begin()};
313  }
314 
315  template(typename U, index_type M)(
316  requires equality_comparable_with<T, U>)
317  bool operator==(span<U, M> const & that) const
318  {
319  RANGES_EXPECT(!size() || data());
320  RANGES_EXPECT(!that.size() || that.data());
321  return ranges::equal(*this, that);
322  }
323  template(typename U, index_type M)(
324  requires equality_comparable_with<T, U>)
325  bool operator!=(span<U, M> const & that) const
326  {
327  return !(*this == that);
328  }
329 
330  template(typename U, index_type M)(
331  requires totally_ordered_with<T, U>)
332  bool operator<(span<U, M> const & that) const
333  {
334  RANGES_EXPECT(!size() || data());
335  RANGES_EXPECT(!that.size() || that.data());
336  return ranges::lexicographical_compare(*this, that);
337  }
338  template(typename U, index_type M)(
339  requires totally_ordered_with<T, U>)
340  bool operator>(span<U, M> const & that) const
341  {
342  return that < *this;
343  }
344  template(typename U, index_type M)(
345  requires totally_ordered_with<T, U>)
346  bool operator<=(span<U, M> const & that) const
347  {
348  return !(that < *this);
349  }
350  template(typename U, index_type M)(
351  requires totally_ordered_with<T, U>)
352  bool operator>=(span<U, M> const & that) const
353  {
354  return !(*this < that);
355  }
356 
357  private:
358  T * data_ = nullptr;
359  };
360 
361  template<typename T, detail::span_index_t N>
362  RANGES_INLINE_VAR constexpr bool enable_borrowed_range<span<T, N>> = true;
363 
364  template<typename T, detail::span_index_t N>
365  constexpr detail::span_index_t span<T, N>::extent;
366 
367 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
368  template(typename Rng)(
369  requires contiguous_range<Rng>)
370  span(Rng && rng)
371  ->span<detail::element_t<Rng>, (range_cardinality<Rng>::value < cardinality()
372  ? dynamic_extent
373  : static_cast<detail::span_index_t>(
375 #endif
376 
377  template<typename T, detail::span_index_t N>
379  {
380  return {reinterpret_cast<unsigned char const *>(s.data()), s.size_bytes()};
381  }
382  template<typename T, detail::span_index_t N>
383  span<unsigned char, detail::byte_size<T>(N)> as_writeable_bytes(span<T, N> s) noexcept
384  {
385  return {reinterpret_cast<unsigned char *>(s.data()), s.size_bytes()};
386  }
387 
388  template<typename ElementType>
389  constexpr span<ElementType> make_span(ElementType * ptr,
390  detail::span_index_t cnt) noexcept
391  {
392  return span<ElementType>{ptr, cnt};
393  }
394  template<typename ElementType>
395  constexpr span<ElementType> make_span(ElementType * first,
396  ElementType * last) noexcept
397  {
398  return span<ElementType>{first, last};
399  }
400  template(typename Rng)(
401  requires contiguous_range<Rng> AND
402  (range_cardinality<Rng>::value < cardinality())) //
403  constexpr span<detail::element_t<Rng>> make_span(Rng && rng) noexcept(
404  noexcept(ranges::data(rng), ranges::size(rng)))
405  {
406  return {ranges::data(rng),
407  detail::narrow_cast<detail::span_index_t>(ranges::size(rng))};
408  }
409  template(typename Rng)(
410  requires contiguous_range<Rng> AND
411  (range_cardinality<Rng>::value >= cardinality())) //
412  constexpr span<
413  detail::element_t<Rng>,
414  static_cast<detail::span_index_t>(
415  range_cardinality<Rng>::
416  value)> make_span(Rng && rng) noexcept(noexcept(ranges::data(rng)))
417  {
418  return {ranges::data(rng), range_cardinality<Rng>::value};
419  }
420 
422 } // namespace ranges
423 
424 #include <range/v3/detail/epilogue.hpp>
425 
426 #endif // RANGES_V3_VIEW_SPAN_HPP
typename T::type _t
Type alias for T::type.
Definition: meta.hpp:141
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
bool_< 0==size< L >::type::value > empty
An Boolean integral constant wrapper around true if L is an empty type list; false,...
Definition: meta.hpp:2231
Tiny meta-programming library.
Definition: basic_iterator.hpp:532
Definition: traits.hpp:128
Definition: span.hpp:153
Definition: interface.hpp:129