common/alspan.h

   1 #ifndef AL_SPAN_H
   2 #define AL_SPAN_H
   3
   4 #include <array>
   5 #include <cstddef>
   6 #include <initializer_list>
   7 #include <iterator>
   8 #include <type_traits>
   9
  10 namespace al {
  11
  12 template<typename T>
  13 constexpr auto size(const T &cont) noexcept(noexcept(cont.size())) -> decltype(cont.size())
  14 { return cont.size(); }
  15
  16 template<typename T, size_t N>
  17 constexpr size_t size(const T (&)[N]) noexcept
  18 { return N; }
  19
  20
  21 template<typename T>
  22 constexpr auto data(T &cont) noexcept(noexcept(cont.data())) -> decltype(cont.data())
  23 { return cont.data(); }
  24
  25 template<typename T>
  26 constexpr auto data(const T &cont) noexcept(noexcept(cont.data())) -> decltype(cont.data())
  27 { return cont.data(); }
  28
  29 template<typename T, size_t N>
  30 constexpr T* data(T (&arr)[N]) noexcept
  31 { return arr; }
  32
  33 template<typename T>
  34 constexpr const T* data(std::initializer_list<T> list) noexcept
  35 { return list.begin(); }
  36
  37
  38 constexpr size_t dynamic_extent{static_cast<size_t>(-1)};
  39
  40 template<typename T, size_t E=dynamic_extent>
  41 class span;
  42
  43 namespace detail_ {
  44     template<typename... Ts>
  45     struct make_void { using type = void; };
  46     template<typename... Ts>
  47     using void_t = typename make_void<Ts...>::type;
  48
  49     template<typename T>
  50     struct is_span_ : std::false_type { };
  51     template<typename T, size_t E>
  52     struct is_span_<span<T,E>> : std::true_type { };
  53     template<typename T>
  54     using is_span = is_span_<std::remove_cv_t<T>>;
  55
  56     template<typename T>
  57     struct is_std_array_ : std::false_type { };
  58     template<typename T, size_t N>
  59     struct is_std_array_<std::array<T,N>> : std::true_type { };
  60     template<typename T>
  61     using is_std_array = is_std_array_<std::remove_cv_t<T>>;
  62
  63     template<typename T, typename = void>
  64     struct has_size_and_data : std::false_type { };
  65     template<typename T>
  66     struct has_size_and_data<T,
  67         void_t<decltype(al::size(std::declval<T>())), decltype(al::data(std::declval<T>()))>>
  68         : std::true_type { };
  69 } // namespace detail_
  70
  71 #define REQUIRES(...) bool rt_=true, std::enable_if_t<rt_ && (__VA_ARGS__),bool> = true
  72 #define IS_VALID_CONTAINER(C)                                                 \
  73     !detail_::is_span<C>::value && !detail_::is_std_array<C>::value &&        \
  74     !std::is_array<C>::value && detail_::has_size_and_data<C>::value &&       \
  75     std::is_convertible<std::remove_pointer_t<decltype(al::data(std::declval<C&>()))>(*)[],element_type(*)[]>::value
  76
  77 template<typename T, size_t E>
  78 class span {
  79 public:
  80     using element_type = T;
  81     using value_type = std::remove_cv_t<T>;
  82     using index_type = size_t;
  83     using difference_type = ptrdiff_t;
  84
  85     using pointer = T*;
  86     using const_pointer = const T*;
  87     using reference = T&;
  88     using const_reference = const T&;
  89
  90     using iterator = pointer;
  91     using const_iterator = const_pointer;
  92     using reverse_iterator = std::reverse_iterator<iterator>;
  93     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  94
  95     static constexpr size_t extent{E};
  96
  97     template<REQUIRES(extent==0)>
  98     constexpr span() noexcept { }
  99     constexpr span(pointer ptr, index_type /*count*/) : mData{ptr} { }
 100     constexpr span(pointer first, pointer /*last*/) : mData{first} { }
 101     constexpr span(element_type (&arr)[E]) noexcept : span{al::data(arr), al::size(arr)} { }
 102     constexpr span(std::array<value_type,E> &arr) noexcept : span{al::data(arr), al::size(arr)} { }
 103     template<REQUIRES(std::is_const<element_type>::value)>
 104     constexpr span(const std::array<value_type,E> &arr) noexcept
 105       : span{al::data(arr), al::size(arr)}
 106     { }
 107     template<typename U, REQUIRES(IS_VALID_CONTAINER(U))>
 108     constexpr span(U &cont) : span{al::data(cont), al::size(cont)} { }
 109     template<typename U, REQUIRES(IS_VALID_CONTAINER(const U))>
 110     constexpr span(const U &cont) : span{al::data(cont), al::size(cont)} { }
 111     template<typename U, REQUIRES(!std::is_same<element_type,U>::value
 112         && std::is_convertible<U(*)[],element_type(*)[]>::value)>
 113     constexpr span(const span<U,E> &span_) noexcept : span{al::data(span_), al::size(span_)} { }
 114     constexpr span(const span&) noexcept = default;
 115
 116     constexpr span& operator=(const span &rhs) noexcept = default;
 117
 118     constexpr reference front() const { return *mData; }
 119     constexpr reference back() const { return *(mData+E-1); }
 120     constexpr reference operator[](index_type idx) const { return mData[idx]; }
 121     constexpr pointer data() const noexcept { return mData; }
 122
 123     constexpr index_type size() const noexcept { return E; }
 124     constexpr index_type size_bytes() const noexcept { return E * sizeof(value_type); }
 125     constexpr bool empty() const noexcept { return E == 0; }
 126
 127     constexpr iterator begin() const noexcept { return mData; }
 128     constexpr iterator end() const noexcept { return mData+E; }
 129     constexpr const_iterator cbegin() const noexcept { return mData; }
 130     constexpr const_iterator cend() const noexcept { return mData+E; }
 131
 132     constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
 133     constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
 134     constexpr const_reverse_iterator crbegin() const noexcept
 135     { return const_reverse_iterator{cend()}; }
 136     constexpr const_reverse_iterator crend() const noexcept
 137     { return const_reverse_iterator{cbegin()}; }
 138
 139     template<size_t C>
 140     constexpr span<element_type,C> first() const
 141     {
 142         static_assert(E >= C, "New size exceeds original capacity");
 143         return span<element_type,C>{mData, C};
 144     }
 145
 146     template<size_t C>
 147     constexpr span<element_type,C> last() const
 148     {
 149         static_assert(E >= C, "New size exceeds original capacity");
 150         return span<element_type,C>{mData+(E-C), C};
 151     }
 152
 153     template<size_t O, size_t C>
 154     constexpr auto subspan() const -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 155     {
 156         static_assert(E >= O, "Offset exceeds extent");
 157         static_assert(E-O >= C, "New size exceeds original capacity");
 158         return span<element_type,C>{mData+O, C};
 159     }
 160
 161     template<size_t O, size_t C=dynamic_extent>
 162     constexpr auto subspan() const -> std::enable_if_t<C==dynamic_extent,span<element_type,E-O>>
 163     {
 164         static_assert(E >= O, "Offset exceeds extent");
 165         return span<element_type,E-O>{mData+O, E-O};
 166     }
 167
 168     /* NOTE: Can't declare objects of a specialized template class prior to
 169      * defining the specialization. As a result, these methods need to be
 170      * defined later.
 171      */
 172     constexpr span<element_type,dynamic_extent> first(size_t count) const;
 173     constexpr span<element_type,dynamic_extent> last(size_t count) const;
 174     constexpr span<element_type,dynamic_extent> subspan(size_t offset,
 175         size_t count=dynamic_extent) const;
 176
 177 private:
 178     pointer mData{nullptr};
 179 };
 180
 181 template<typename T>
 182 class span<T,dynamic_extent> {
 183 public:
 184     using element_type = T;
 185     using value_type = std::remove_cv_t<T>;
 186     using index_type = size_t;
 187     using difference_type = ptrdiff_t;
 188
 189     using pointer = T*;
 190     using const_pointer = const T*;
 191     using reference = T&;
 192     using const_reference = const T&;
 193
 194     using iterator = pointer;
 195     using const_iterator = const_pointer;
 196     using reverse_iterator = std::reverse_iterator<iterator>;
 197     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 198
 199     static constexpr size_t extent{dynamic_extent};
 200
 201     constexpr span() noexcept = default;
 202     constexpr span(pointer ptr, index_type count) : mData{ptr}, mDataEnd{ptr+count} { }
 203     constexpr span(pointer first, pointer last) : mData{first}, mDataEnd{last} { }
 204     template<size_t N>
 205     constexpr span(element_type (&arr)[N]) noexcept : span{al::data(arr), al::size(arr)} { }
 206     template<size_t N>
 207     constexpr span(std::array<value_type,N> &arr) noexcept : span{al::data(arr), al::size(arr)} { }
 208     template<size_t N, REQUIRES(std::is_const<element_type>::value)>
 209     constexpr span(const std::array<value_type,N> &arr) noexcept
 210       : span{al::data(arr), al::size(arr)}
 211     { }
 212     template<typename U, REQUIRES(IS_VALID_CONTAINER(U))>
 213     constexpr span(U &cont) : span{al::data(cont), al::size(cont)} { }
 214     template<typename U, REQUIRES(IS_VALID_CONTAINER(const U))>
 215     constexpr span(const U &cont) : span{al::data(cont), al::size(cont)} { }
 216     template<typename U, size_t N, REQUIRES((!std::is_same<element_type,U>::value || extent != N)
 217         && std::is_convertible<U(*)[],element_type(*)[]>::value)>
 218     constexpr span(const span<U,N> &span_) noexcept : span{al::data(span_), al::size(span_)} { }
 219     constexpr span(const span&) noexcept = default;
 220
 221     constexpr span& operator=(const span &rhs) noexcept = default;
 222
 223     constexpr reference front() const { return *mData; }
 224     constexpr reference back() const { return *(mDataEnd-1); }
 225     constexpr reference operator[](index_type idx) const { return mData[idx]; }
 226     constexpr pointer data() const noexcept { return mData; }
 227
 228     constexpr index_type size() const noexcept { return static_cast<index_type>(mDataEnd-mData); }
 229     constexpr index_type size_bytes() const noexcept
 230     { return static_cast<index_type>(mDataEnd-mData) * sizeof(value_type); }
 231     constexpr bool empty() const noexcept { return mData == mDataEnd; }
 232
 233     constexpr iterator begin() const noexcept { return mData; }
 234     constexpr iterator end() const noexcept { return mDataEnd; }
 235     constexpr const_iterator cbegin() const noexcept { return mData; }
 236     constexpr const_iterator cend() const noexcept { return mDataEnd; }
 237
 238     constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
 239     constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
 240     constexpr const_reverse_iterator crbegin() const noexcept
 241     { return const_reverse_iterator{cend()}; }
 242     constexpr const_reverse_iterator crend() const noexcept
 243     { return const_reverse_iterator{cbegin()}; }
 244
 245     template<size_t C>
 246     constexpr span<element_type,C> first() const
 247     { return span<element_type,C>{mData, C}; }
 248
 249     constexpr span first(size_t count) const
 250     { return (count >= size()) ? *this : span{mData, mData+count}; }
 251
 252     template<size_t C>
 253     constexpr span<element_type,C> last() const
 254     { return span<element_type,C>{mDataEnd-C, C}; }
 255
 256     constexpr span last(size_t count) const
 257     { return (count >= size()) ? *this : span{mDataEnd-count, mDataEnd}; }
 258
 259     template<size_t O, size_t C>
 260     constexpr auto subspan() const -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 261     { return span<element_type,C>{mData+O, C}; }
 262
 263     template<size_t O, size_t C=dynamic_extent>
 264     constexpr auto subspan() const -> std::enable_if_t<C==dynamic_extent,span<element_type,C>>
 265     { return span<element_type,C>{mData+O, mDataEnd}; }
 266
 267     constexpr span subspan(size_t offset, size_t count=dynamic_extent) const
 268     {
 269         return (offset > size()) ? span{} :
 270             (count >= size()-offset) ? span{mData+offset, mDataEnd} :
 271             span{mData+offset, mData+offset+count};
 272     }
 273
 274 private:
 275     pointer mData{nullptr};
 276     pointer mDataEnd{nullptr};
 277 };
 278
 279 template<typename T, size_t E>
 280 constexpr inline auto span<T,E>::first(size_t count) const -> span<element_type,dynamic_extent>
 281 {
 282     return (count >= size()) ? span<element_type>{mData, extent} :
 283         span<element_type>{mData, count};
 284 }
 285
 286 template<typename T, size_t E>
 287 constexpr inline auto span<T,E>::last(size_t count) const -> span<element_type,dynamic_extent>
 288 {
 289     return (count >= size()) ? span<element_type>{mData, extent} :
 290         span<element_type>{mData+extent-count, count};
 291 }
 292
 293 template<typename T, size_t E>
 294 constexpr inline auto span<T,E>::subspan(size_t offset, size_t count) const
 295     -> span<element_type,dynamic_extent>
 296 {
 297     return (offset > size()) ? span<element_type>{} :
 298         (count >= size()-offset) ? span<element_type>{mData+offset, mData+extent} :
 299         span<element_type>{mData+offset, mData+offset+count};
 300 }
 301
 302 #undef IS_VALID_CONTAINER
 303 #undef REQUIRES
 304
 305 } // namespace al
 306
 307 #endif /* AL_SPAN_H */