1/**
2 * This file is based on the std::array implementation of libstdc++ at
3 * https://gcc.gnu.org/onlinedocs/gcc-7.1.0/libstdc++/api/a01056_source.html
4 *
5 * Changes:
6 * - isolate, i.e. remove dependencies on internal libstdc++ stuff
7 * - use c++17 behavior even in c++11 or c++14
8 * - remove std::swappable special case because that doesn't work with MSVC
9 * - constexpr more things
10 * - add some features like prepend/tail
11 *
12 * If using std::array at runtime, feel free to either keep using std::array or
13 * use this one - it doesn't really matter. For compile time computations, this
14 * one here is preferred because std::array in C++11 misses some constexpr
15 * specifiers, forcing these methods to be called at runtime instead of compile
16 * time.
17 */
18
19// Copyright (C) 2007-2017 Free Software Foundation, Inc.
20//
21// This file is part of the GNU ISO C++ Library. This library is free
22// software; you can redistribute it and/or modify it under the
23// terms of the GNU General Public License as published by the
24// Free Software Foundation; either version 3, or (at your option)
25// any later version.
26
27// This library is distributed in the hope that it will be useful,
28// but WITHOUT ANY WARRANTY; without even the implied warranty of
29// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30// GNU General Public License for more details.
31
32// Under Section 7 of GPL version 3, you are granted additional
33// permissions described in the GCC Runtime Library Exception, version
34// 3.1, as published by the Free Software Foundation.
35
36// You should have received a copy of the GNU General Public License and
37// a copy of the GCC Runtime Library Exception along with this program;
38// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
39// <http://www.gnu.org/licenses/>.
40
41#pragma once
42
43#include <c10/util/C++17.h>
44#include <algorithm>
45#include <stdexcept>
46#include <string>
47#include <utility>
48
49namespace c10 {
50namespace guts {
51
52namespace detail {
53template <typename _Tp, std::size_t _Nm>
54struct __array_traits final {
55 using _Type = _Tp[_Nm];
56
57 static constexpr _Tp& _S_ref(const _Type& __t, std::size_t __n) noexcept {
58 return const_cast<_Tp&>(__t[__n]);
59 }
60
61 static constexpr _Tp* _S_ptr(const _Type& __t) noexcept {
62 return const_cast<_Tp*>(__t);
63 }
64};
65
66template <typename _Tp>
67struct __array_traits<_Tp, 0> final {
68 struct _Type final {};
69
70 static constexpr _Tp& _S_ref(const _Type& __t, std::size_t) noexcept {
71 return *_S_ptr(__t);
72 }
73
74 static constexpr _Tp* _S_ptr(const _Type&) noexcept {
75 return nullptr;
76 }
77};
78
79[[noreturn]] inline void __throw_out_of_range(const std::string& msg) {
80 throw std::out_of_range(msg);
81}
82} // namespace detail
83
84template <typename _Tp, std::size_t _Nm>
85class array final {
86 public:
87 using value_type = _Tp;
88 using pointer = value_type*;
89 using const_pointer = const value_type*;
90 using reference = value_type&;
91 using const_reference = const value_type&;
92 using iterator = value_type*;
93 using const_iterator = const value_type*;
94 using size_type = std::size_t;
95 using difference_type = std::ptrdiff_t;
96 using reverse_iterator = std::reverse_iterator<iterator>;
97 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
98
99 private:
100 using _AT_Type = detail::__array_traits<_Tp, _Nm>;
101
102 public: // needs to be public member for aggregate initialization
103 typename _AT_Type::_Type _M_elems;
104
105 public:
106 // No explicit construct/copy/destroy for aggregate type.
107
108 // DR 776.
109 constexpr void fill(const value_type& __u) {
110 std::fill_n(begin(), size(), __u);
111 }
112
113 constexpr void swap(array& __other) {
114 std::swap_ranges(begin(), end(), __other.begin());
115 }
116
117 // Iterators.
118 constexpr iterator begin() noexcept {
119 return iterator(data());
120 }
121
122 constexpr const_iterator begin() const noexcept {
123 return const_iterator(data());
124 }
125
126 constexpr iterator end() noexcept {
127 return iterator(data() + _Nm);
128 }
129
130 constexpr const_iterator end() const noexcept {
131 return const_iterator(data() + _Nm);
132 }
133
134 constexpr reverse_iterator rbegin() noexcept {
135 return reverse_iterator(end());
136 }
137
138 constexpr const_reverse_iterator rbegin() const noexcept {
139 return const_reverse_iterator(end());
140 }
141
142 constexpr reverse_iterator rend() noexcept {
143 return reverse_iterator(begin());
144 }
145
146 constexpr const_reverse_iterator rend() const noexcept {
147 return const_reverse_iterator(begin());
148 }
149
150 constexpr const_iterator cbegin() const noexcept {
151 return const_iterator(data());
152 }
153
154 constexpr const_iterator cend() const noexcept {
155 return const_iterator(data() + _Nm);
156 }
157
158 constexpr const_reverse_iterator crbegin() const noexcept {
159 return const_reverse_iterator(end());
160 }
161
162 constexpr const_reverse_iterator crend() const noexcept {
163 return const_reverse_iterator(begin());
164 }
165
166 // Capacity.
167 constexpr size_type size() const noexcept {
168 return _Nm;
169 }
170
171 constexpr size_type max_size() const noexcept {
172 return _Nm;
173 }
174
175 constexpr bool empty() const noexcept {
176 return size() == 0;
177 }
178
179 // Element access.
180 constexpr reference operator[](size_type __n) noexcept {
181 return _AT_Type::_S_ref(_M_elems, __n);
182 }
183
184 constexpr const_reference operator[](size_type __n) const noexcept {
185 return _AT_Type::_S_ref(_M_elems, __n);
186 }
187
188 constexpr reference at(size_type __n) {
189 if (__n >= _Nm) {
190 detail::__throw_out_of_range(
191 std::string() + "array::at: __n (which is " + to_string(__n) + ") " +
192 ">= _Nm (which is " + to_string(_Nm) + ")");
193 }
194 return _AT_Type::_S_ref(_M_elems, __n);
195 }
196
197 constexpr const_reference at(size_type __n) const {
198 // Result of conditional expression must be an lvalue so use
199 // boolean ? lvalue : (throw-expr, lvalue)
200 return __n < _Nm
201 ? _AT_Type::_S_ref(_M_elems, __n)
202 : (detail::__throw_out_of_range(
203 std::string() + "array::at: __n (which is " + to_string(__n) +
204 ") " + ">= _Nm (which is " + to_string(_Nm) + ")"),
205 _AT_Type::_S_ref(_M_elems, 0));
206 }
207
208 constexpr reference front() noexcept {
209 return *begin();
210 }
211
212 constexpr const_reference front() const noexcept {
213 return _AT_Type::_S_ref(_M_elems, 0);
214 }
215
216 constexpr reference back() noexcept {
217 return _Nm ? *(end() - 1) : *end();
218 }
219
220 constexpr const_reference back() const noexcept {
221 return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1)
222 : _AT_Type::_S_ref(_M_elems, 0);
223 }
224
225 constexpr pointer data() noexcept {
226 return _AT_Type::_S_ptr(_M_elems);
227 }
228
229 constexpr const_pointer data() const noexcept {
230 return _AT_Type::_S_ptr(_M_elems);
231 }
232};
233
234#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
235template <typename _Tp, typename... _Up>
236array(_Tp, _Up...) -> array<
237 std::enable_if_t<(std::is_same<_Tp, _Up>::value && ...), _Tp>,
238 1 + sizeof...(_Up)>;
239#endif
240
241// Array comparisons.
242namespace detail {
243template <class T, size_t N>
244constexpr inline bool array_equals_(
245 const array<T, N>& lhs,
246 const array<T, N>& rhs,
247 size_t current_index) {
248 return (current_index == N)
249 ? true
250 : (lhs.at(current_index) == rhs.at(current_index) &&
251 array_equals_(lhs, rhs, current_index + 1));
252}
253template <class T, size_t N>
254constexpr inline bool array_less_(
255 const array<T, N>& lhs,
256 const array<T, N>& rhs,
257 size_t current_index) {
258 return (current_index == N)
259 ? false
260 : (lhs.at(current_index) < rhs.at(current_index) ||
261 array_less_(lhs, rhs, current_index + 1));
262}
263} // namespace detail
264template <typename _Tp, std::size_t _Nm>
265constexpr inline bool operator==(
266 const array<_Tp, _Nm>& __one,
267 const array<_Tp, _Nm>& __two) {
268 return detail::array_equals_(__one, __two, 0);
269}
270
271template <typename _Tp, std::size_t _Nm>
272constexpr inline bool operator!=(
273 const array<_Tp, _Nm>& __one,
274 const array<_Tp, _Nm>& __two) {
275 return !(__one == __two);
276}
277
278template <typename _Tp, std::size_t _Nm>
279constexpr inline bool operator<(
280 const array<_Tp, _Nm>& __a,
281 const array<_Tp, _Nm>& __b) {
282 return detail::array_less_(__a, __b, 0);
283}
284
285template <typename _Tp, std::size_t _Nm>
286constexpr inline bool operator>(
287 const array<_Tp, _Nm>& __one,
288 const array<_Tp, _Nm>& __two) {
289 return __two < __one;
290}
291
292template <typename _Tp, std::size_t _Nm>
293constexpr inline bool operator<=(
294 const array<_Tp, _Nm>& __one,
295 const array<_Tp, _Nm>& __two) {
296 return !(__one > __two);
297}
298
299template <typename _Tp, std::size_t _Nm>
300constexpr inline bool operator>=(
301 const array<_Tp, _Nm>& __one,
302 const array<_Tp, _Nm>& __two) {
303 return !(__one < __two);
304}
305
306// Specialized algorithms.
307template <typename _Tp, std::size_t _Nm>
308inline void swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two) noexcept(
309 noexcept(__one.swap(__two))) {
310 __one.swap(__two);
311}
312
313template <std::size_t _Int, typename _Tp, std::size_t _Nm>
314constexpr _Tp& get(array<_Tp, _Nm>& __arr) noexcept {
315 static_assert(_Int < _Nm, "array index is within bounds");
316 return detail::__array_traits<_Tp, _Nm>::_S_ref(__arr._M_elems, _Int);
317}
318
319template <std::size_t _Int, typename _Tp, std::size_t _Nm>
320constexpr _Tp&& get(array<_Tp, _Nm>&& __arr) noexcept {
321 static_assert(_Int < _Nm, "array index is within bounds");
322 return std::move(get<_Int>(__arr));
323}
324
325template <std::size_t _Int, typename _Tp, std::size_t _Nm>
326constexpr const _Tp& get(const array<_Tp, _Nm>& __arr) noexcept {
327 static_assert(_Int < _Nm, "array index is within bounds");
328 return detail::__array_traits<_Tp, _Nm>::_S_ref(__arr._M_elems, _Int);
329}
330
331/**
332 * Some added features not available in std::array.
333 * Only call these at compile time, they're slow if called at runtime.
334 * Examples:
335 * tail({2, 3, 4}) == {3, 4}
336 * prepend(2, {3, 4}) == {2, 3, 4}
337 */
338namespace detail {
339template <class T, size_t N, size_t... INDEX>
340constexpr inline array<T, N - 1> tail_(
341 const array<T, N>& arg,
342 std::index_sequence<INDEX...>) {
343 static_assert(sizeof...(INDEX) == N - 1, "invariant");
344 return {{get<INDEX + 1>(arg)...}};
345}
346} // namespace detail
347template <class T, size_t N>
348constexpr inline array<T, N - 1> tail(const array<T, N>& arg) {
349 static_assert(
350 N > 0, "Can only call tail() on an array with at least one element");
351 return detail::tail_(arg, std::make_index_sequence<N - 1>());
352}
353
354namespace detail {
355template <class T, size_t N, size_t... INDEX>
356constexpr inline array<T, N + 1> prepend_(
357 T&& head,
358 const array<T, N>& tail,
359 std::index_sequence<INDEX...>) {
360 return {{std::forward<T>(head), get<INDEX>(tail)...}};
361}
362} // namespace detail
363template <class T, size_t N>
364constexpr inline array<T, N + 1> prepend(T&& head, const array<T, N>& tail) {
365 return detail::prepend_(
366 std::forward<T>(head), tail, std::make_index_sequence<N>());
367}
368
369/**
370 * Convert a C array into a std::array.
371 * Example:
372 * int source[3] = {2, 3, 4};
373 * std::array<int, 3> target = to_std_array(source);
374 */
375
376namespace detail {
377template <class T, size_t N, size_t... INDEX>
378constexpr array<T, N> to_array_(
379 const T (&arr)[N],
380 std::index_sequence<INDEX...>) {
381 return {{arr[INDEX]...}};
382}
383} // namespace detail
384
385template <class T, size_t N>
386constexpr array<T, N> to_array(const T (&arr)[N]) {
387 return detail::to_array_(arr, std::make_index_sequence<N>());
388}
389
390} // namespace guts
391} // namespace c10
392