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 | |
49 | namespace c10 { |
50 | namespace guts { |
51 | |
52 | namespace detail { |
53 | template <typename _Tp, std::size_t _Nm> |
54 | struct __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 | |
66 | template <typename _Tp> |
67 | struct __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 | |
84 | template <typename _Tp, std::size_t _Nm> |
85 | class 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 |
235 | template <typename _Tp, typename... _Up> |
236 | array(_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. |
242 | namespace detail { |
243 | template <class T, size_t N> |
244 | constexpr 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 | } |
253 | template <class T, size_t N> |
254 | constexpr 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 |
264 | template <typename _Tp, std::size_t _Nm> |
265 | constexpr 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 | |
271 | template <typename _Tp, std::size_t _Nm> |
272 | constexpr inline bool operator!=( |
273 | const array<_Tp, _Nm>& __one, |
274 | const array<_Tp, _Nm>& __two) { |
275 | return !(__one == __two); |
276 | } |
277 | |
278 | template <typename _Tp, std::size_t _Nm> |
279 | constexpr 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 | |
285 | template <typename _Tp, std::size_t _Nm> |
286 | constexpr inline bool operator>( |
287 | const array<_Tp, _Nm>& __one, |
288 | const array<_Tp, _Nm>& __two) { |
289 | return __two < __one; |
290 | } |
291 | |
292 | template <typename _Tp, std::size_t _Nm> |
293 | constexpr inline bool operator<=( |
294 | const array<_Tp, _Nm>& __one, |
295 | const array<_Tp, _Nm>& __two) { |
296 | return !(__one > __two); |
297 | } |
298 | |
299 | template <typename _Tp, std::size_t _Nm> |
300 | constexpr inline bool operator>=( |
301 | const array<_Tp, _Nm>& __one, |
302 | const array<_Tp, _Nm>& __two) { |
303 | return !(__one < __two); |
304 | } |
305 | |
306 | // Specialized algorithms. |
307 | template <typename _Tp, std::size_t _Nm> |
308 | inline void swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two) noexcept( |
309 | noexcept(__one.swap(__two))) { |
310 | __one.swap(__two); |
311 | } |
312 | |
313 | template <std::size_t _Int, typename _Tp, std::size_t _Nm> |
314 | constexpr _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 | |
319 | template <std::size_t _Int, typename _Tp, std::size_t _Nm> |
320 | constexpr _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 | |
325 | template <std::size_t _Int, typename _Tp, std::size_t _Nm> |
326 | constexpr 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 | */ |
338 | namespace detail { |
339 | template <class T, size_t N, size_t... INDEX> |
340 | constexpr 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 |
347 | template <class T, size_t N> |
348 | constexpr 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 | |
354 | namespace detail { |
355 | template <class T, size_t N, size_t... INDEX> |
356 | constexpr 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 |
363 | template <class T, size_t N> |
364 | constexpr 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 | |
376 | namespace detail { |
377 | template <class T, size_t N, size_t... INDEX> |
378 | constexpr array<T, N> to_array_( |
379 | const T (&arr)[N], |
380 | std::index_sequence<INDEX...>) { |
381 | return {{arr[INDEX]...}}; |
382 | } |
383 | } // namespace detail |
384 | |
385 | template <class T, size_t N> |
386 | constexpr 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 | |