1// -*- C++ -*-
2//===-------------------------- utility -----------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UTILITY
12#define _LIBCPP_UTILITY
13
14/*
15    utility synopsis
16
17namespace std
18{
19
20template <class T>
21    void
22    swap(T& a, T& b);
23
24namespace rel_ops
25{
26    template<class T> bool operator!=(const T&, const T&);
27    template<class T> bool operator> (const T&, const T&);
28    template<class T> bool operator<=(const T&, const T&);
29    template<class T> bool operator>=(const T&, const T&);
30}
31
32template<class T>
33void
34swap(T& a, T& b) noexcept(is_nothrow_move_constructible<T>::value &&
35                          is_nothrow_move_assignable<T>::value);
36
37template <class T, size_t N>
38void
39swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b)));
40
41template <class T> T&& forward(typename remove_reference<T>::type& t) noexcept;
42template <class T> T&& forward(typename remove_reference<T>::type&& t) noexcept;
43
44template <class T> typename remove_reference<T>::type&& move(T&&) noexcept;
45
46template <class T>
47    typename conditional
48    <
49        !is_nothrow_move_constructible<T>::value && is_copy_constructible<T>::value,
50        const T&,
51        T&&
52    >::type
53    move_if_noexcept(T& x) noexcept;
54
55template <class T> typename add_rvalue_reference<T>::type declval() noexcept;
56
57template <class T1, class T2>
58struct pair
59{
60    typedef T1 first_type;
61    typedef T2 second_type;
62
63    T1 first;
64    T2 second;
65
66    pair(const pair&) = default;
67    pair(pair&&) = default;
68    constexpr pair();
69    pair(const T1& x, const T2& y);
70    template <class U, class V> pair(U&& x, V&& y);
71    template <class U, class V> pair(const pair<U, V>& p);
72    template <class U, class V> pair(pair<U, V>&& p);
73    template <class... Args1, class... Args2>
74        pair(piecewise_construct_t, tuple<Args1...> first_args,
75             tuple<Args2...> second_args);
76
77    template <class U, class V> pair& operator=(const pair<U, V>& p);
78    pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable<T1>::value &&
79                                       is_nothrow_move_assignable<T2>::value);
80    template <class U, class V> pair& operator=(pair<U, V>&& p);
81
82    void swap(pair& p) noexcept(noexcept(swap(first, p.first)) &&
83                                noexcept(swap(second, p.second)));
84};
85
86template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&);
87template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&);
88template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&);
89template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&);
90template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&);
91template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&);
92
93template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&);
94template <class T1, class T2>
95void
96swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y)));
97
98struct piecewise_construct_t { };
99constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
100
101template <class T> class tuple_size;
102template <size_t I, class T> class tuple_element;
103
104template <class T1, class T2> struct tuple_size<std::pair<T1, T2> >;
105template <class T1, class T2> struct tuple_element<0, std::pair<T1, T2> >;
106template <class T1, class T2> struct tuple_element<1, std::pair<T1, T2> >;
107
108template<size_t I, class T1, class T2>
109    typename tuple_element<I, std::pair<T1, T2> >::type&
110    get(std::pair<T1, T2>&) noexcept;
111
112template<size_t I, class T1, class T2>
113    const typename const tuple_element<I, std::pair<T1, T2> >::type&
114    get(const std::pair<T1, T2>&) noexcept;
115
116template<size_t I, class T1, class T2>
117    typename tuple_element<I, std::pair<T1, T2> >::type&&
118    get(std::pair<T1, T2>&&) noexcept;
119
120}  // std
121
122*/
123
124#include <__config>
125#include <__tuple>
126#include <type_traits>
127
128#pragma GCC system_header
129
130_LIBCPP_BEGIN_NAMESPACE_STD
131
132namespace rel_ops
133{
134
135template<class _Tp>
136inline _LIBCPP_INLINE_VISIBILITY
137bool
138operator!=(const _Tp& __x, const _Tp& __y)
139{
140    return !(__x == __y);
141}
142
143template<class _Tp>
144inline _LIBCPP_INLINE_VISIBILITY
145bool
146operator> (const _Tp& __x, const _Tp& __y)
147{
148    return __y < __x;
149}
150
151template<class _Tp>
152inline _LIBCPP_INLINE_VISIBILITY
153bool
154operator<=(const _Tp& __x, const _Tp& __y)
155{
156    return !(__y < __x);
157}
158
159template<class _Tp>
160inline _LIBCPP_INLINE_VISIBILITY
161bool
162operator>=(const _Tp& __x, const _Tp& __y)
163{
164    return !(__x < __y);
165}
166
167}  // rel_ops
168
169// swap_ranges
170
171template <class _ForwardIterator1, class _ForwardIterator2>
172inline _LIBCPP_INLINE_VISIBILITY
173_ForwardIterator2
174swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
175{
176    for(; __first1 != __last1; ++__first1, ++__first2)
177        swap(*__first1, *__first2);
178    return __first2;
179}
180
181template<class _Tp, size_t _N>
182inline _LIBCPP_INLINE_VISIBILITY
183void
184swap(_Tp (&__a)[_N], _Tp (&__b)[_N]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value)
185{
186    _VSTD::swap_ranges(__a, __a + _N, __b);
187}
188
189template <class _Tp>
190inline _LIBCPP_INLINE_VISIBILITY
191#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
192typename conditional
193<
194    !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value,
195    const _Tp&,
196    _Tp&&
197>::type
198#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
199const _Tp&
200#endif
201move_if_noexcept(_Tp& __x) _NOEXCEPT
202{
203    return _VSTD::move(__x);
204}
205
206struct _LIBCPP_VISIBLE piecewise_construct_t { };
207//constexpr
208extern const piecewise_construct_t piecewise_construct;// = piecewise_construct_t();
209
210template <class _T1, class _T2>
211struct _LIBCPP_VISIBLE pair
212{
213    typedef _T1 first_type;
214    typedef _T2 second_type;
215
216    _T1 first;
217    _T2 second;
218
219    // pair(const pair&) = default;
220    // pair(pair&&) = default;
221
222    _LIBCPP_INLINE_VISIBILITY pair() : first(), second() {}
223
224    _LIBCPP_INLINE_VISIBILITY pair(const _T1& __x, const _T2& __y)
225        : first(__x), second(__y) {}
226
227    template<class _U1, class _U2>
228        _LIBCPP_INLINE_VISIBILITY
229        pair(const pair<_U1, _U2>& __p
230#ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE
231                 ,typename enable_if<is_constructible<_T1, _U1>::value &&
232                                    is_constructible<_T2, _U2>::value>::type* = 0
233#endif
234                                      )
235            : first(__p.first), second(__p.second) {}
236
237    _LIBCPP_INLINE_VISIBILITY
238    pair(const pair& __p)
239        _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value &&
240                   is_nothrow_copy_constructible<second_type>::value)
241        : first(__p.first),
242          second(__p.second)
243    {
244    }
245
246    _LIBCPP_INLINE_VISIBILITY
247    pair& operator=(const pair& __p)
248        _NOEXCEPT_(is_nothrow_copy_assignable<first_type>::value &&
249                   is_nothrow_copy_assignable<second_type>::value)
250    {
251        first = __p.first;
252        second = __p.second;
253        return *this;
254    }
255
256#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
257
258    template <class _U1, class _U2,
259              class = typename enable_if<is_constructible<first_type, _U1 >::value &&
260                                         is_constructible<second_type, _U2>::value>::type>
261        _LIBCPP_INLINE_VISIBILITY
262        pair(_U1&& __u1, _U2&& __u2)
263            : first(_VSTD::forward<_U1>(__u1)),
264              second(_VSTD::forward<_U2>(__u2))
265            {}
266
267    template<class _U1, class _U2>
268        _LIBCPP_INLINE_VISIBILITY
269        pair(pair<_U1, _U2>&& __p,
270                 typename enable_if<is_constructible<_T1, _U1>::value &&
271                                    is_constructible<_T2, _U2>::value>::type* = 0)
272            : first(_VSTD::forward<_U1>(__p.first)),
273              second(_VSTD::forward<_U2>(__p.second)) {}
274
275    _LIBCPP_INLINE_VISIBILITY
276    pair(pair&& __p) _NOEXCEPT_(is_nothrow_move_constructible<first_type>::value &&
277                                is_nothrow_move_constructible<second_type>::value)
278        : first(_VSTD::forward<first_type>(__p.first)),
279          second(_VSTD::forward<second_type>(__p.second))
280    {
281    }
282
283    _LIBCPP_INLINE_VISIBILITY
284    pair&
285    operator=(pair&& __p) _NOEXCEPT_(is_nothrow_move_assignable<first_type>::value &&
286                                     is_nothrow_move_assignable<second_type>::value)
287    {
288        first = _VSTD::forward<first_type>(__p.first);
289        second = _VSTD::forward<second_type>(__p.second);
290        return *this;
291    }
292
293#ifndef _LIBCPP_HAS_NO_VARIADICS
294
295    template<class _Tuple,
296             class = typename enable_if<__tuple_convertible<_Tuple, pair>::value>::type>
297        _LIBCPP_INLINE_VISIBILITY
298        pair(_Tuple&& __p)
299            : first(_VSTD::forward<typename tuple_element<0,
300                                  typename __make_tuple_types<_Tuple>::type>::type>(get<0>(__p))),
301              second(_VSTD::forward<typename tuple_element<1,
302                                   typename __make_tuple_types<_Tuple>::type>::type>(get<1>(__p)))
303            {}
304
305
306
307    template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
308        _LIBCPP_INLINE_VISIBILITY
309        pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
310                                    tuple<_Args2...> __second_args)
311            : pair(__pc, __first_args, __second_args,
312                   typename __make_tuple_indices<sizeof...(_Args1)>::type(),
313                   typename __make_tuple_indices<sizeof...(_Args2) >::type())
314            {}
315
316    template <class _Tuple,
317              class = typename enable_if<__tuple_assignable<_Tuple, pair>::value>::type>
318        _LIBCPP_INLINE_VISIBILITY
319        pair&
320        operator=(_Tuple&& __p)
321        {
322            typedef typename __make_tuple_types<_Tuple>::type _TupleRef;
323            typedef typename tuple_element<0, _TupleRef>::type _U0;
324            typedef typename tuple_element<1, _TupleRef>::type _U1;
325            first  = _VSTD::forward<_U0>(_VSTD::get<0>(__p));
326            second = _VSTD::forward<_U1>(_VSTD::get<1>(__p));
327            return *this;
328        }
329
330#endif  // _LIBCPP_HAS_NO_VARIADICS
331
332#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
333    _LIBCPP_INLINE_VISIBILITY
334    void
335    swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable<first_type>::value &&
336                               __is_nothrow_swappable<second_type>::value)
337    {
338        _VSTD::iter_swap(&first, &__p.first);
339        _VSTD::iter_swap(&second, &__p.second);
340    }
341private:
342
343#ifndef _LIBCPP_HAS_NO_VARIADICS
344    template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
345        _LIBCPP_INLINE_VISIBILITY
346        pair(piecewise_construct_t,
347             tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args,
348             __tuple_indices<_I1...>, __tuple_indices<_I2...>);
349#endif  // _LIBCPP_HAS_NO_VARIADICS
350};
351
352template <class _T1, class _T2>
353inline _LIBCPP_INLINE_VISIBILITY
354bool
355operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
356{
357    return __x.first == __y.first && __x.second == __y.second;
358}
359
360template <class _T1, class _T2>
361inline _LIBCPP_INLINE_VISIBILITY
362bool
363operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
364{
365    return !(__x == __y);
366}
367
368template <class _T1, class _T2>
369inline _LIBCPP_INLINE_VISIBILITY
370bool
371operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
372{
373    return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second);
374}
375
376template <class _T1, class _T2>
377inline _LIBCPP_INLINE_VISIBILITY
378bool
379operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
380{
381    return __y < __x;
382}
383
384template <class _T1, class _T2>
385inline _LIBCPP_INLINE_VISIBILITY
386bool
387operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
388{
389    return !(__x < __y);
390}
391
392template <class _T1, class _T2>
393inline _LIBCPP_INLINE_VISIBILITY
394bool
395operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
396{
397    return !(__y < __x);
398}
399
400template <class _T1, class _T2>
401inline _LIBCPP_INLINE_VISIBILITY
402typename enable_if
403<
404    __is_swappable<_T1>::value &&
405    __is_swappable<_T2>::value,
406    void
407>::type
408swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
409                     _NOEXCEPT_((__is_nothrow_swappable<_T1>::value &&
410                                 __is_nothrow_swappable<_T2>::value))
411{
412    __x.swap(__y);
413}
414
415#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
416
417template <class _Tp> class reference_wrapper;
418
419template <class _Tp>
420struct ___make_pair_return
421{
422    typedef _Tp type;
423};
424
425template <class _Tp>
426struct ___make_pair_return<reference_wrapper<_Tp>>
427{
428    typedef _Tp& type;
429};
430
431template <class _Tp>
432struct __make_pair_return
433{
434    typedef typename ___make_pair_return<typename decay<_Tp>::type>::type type;
435};
436
437template <class _T1, class _T2>
438inline _LIBCPP_INLINE_VISIBILITY
439pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
440make_pair(_T1&& __t1, _T2&& __t2)
441{
442    return pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
443               (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2));
444}
445
446#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
447
448template <class _T1, class _T2>
449inline _LIBCPP_INLINE_VISIBILITY
450pair<_T1,_T2>
451make_pair(_T1 __x, _T2 __y)
452{
453    return pair<_T1, _T2>(__x, __y);
454}
455
456#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
457
458#ifndef _LIBCPP_HAS_NO_VARIADICS
459
460template <class _T1, class _T2>
461  class _LIBCPP_VISIBLE tuple_size<pair<_T1, _T2> >
462    : public integral_constant<size_t, 2> {};
463
464template <class _T1, class _T2>
465  class _LIBCPP_VISIBLE tuple_size<const pair<_T1, _T2> >
466    : public integral_constant<size_t, 2> {};
467
468template <class _T1, class _T2>
469class _LIBCPP_VISIBLE tuple_element<0, pair<_T1, _T2> >
470{
471public:
472    typedef _T1 type;
473};
474
475template <class _T1, class _T2>
476class _LIBCPP_VISIBLE tuple_element<1, pair<_T1, _T2> >
477{
478public:
479    typedef _T2 type;
480};
481
482template <class _T1, class _T2>
483class _LIBCPP_VISIBLE tuple_element<0, const pair<_T1, _T2> >
484{
485public:
486    typedef const _T1 type;
487};
488
489template <class _T1, class _T2>
490class _LIBCPP_VISIBLE tuple_element<1, const pair<_T1, _T2> >
491{
492public:
493    typedef const _T2 type;
494};
495
496template <size_t _Ip> struct __get_pair;
497
498template <>
499struct __get_pair<0>
500{
501    template <class _T1, class _T2>
502    static
503    _LIBCPP_INLINE_VISIBILITY
504    _T1&
505    get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
506
507    template <class _T1, class _T2>
508    static
509    _LIBCPP_INLINE_VISIBILITY
510    const _T1&
511    get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
512
513#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
514
515    template <class _T1, class _T2>
516    static
517    _LIBCPP_INLINE_VISIBILITY
518    _T1&&
519    get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);}
520
521#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
522};
523
524template <>
525struct __get_pair<1>
526{
527    template <class _T1, class _T2>
528    static
529    _LIBCPP_INLINE_VISIBILITY
530    _T2&
531    get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
532
533    template <class _T1, class _T2>
534    static
535    _LIBCPP_INLINE_VISIBILITY
536    const _T2&
537    get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
538
539#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
540
541    template <class _T1, class _T2>
542    static
543    _LIBCPP_INLINE_VISIBILITY
544    _T2&&
545    get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);}
546
547#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
548};
549
550template <size_t _Ip, class _T1, class _T2>
551_LIBCPP_INLINE_VISIBILITY inline
552typename tuple_element<_Ip, pair<_T1, _T2> >::type&
553get(pair<_T1, _T2>& __p) _NOEXCEPT
554{
555    return __get_pair<_Ip>::get(__p);
556}
557
558template <size_t _Ip, class _T1, class _T2>
559_LIBCPP_INLINE_VISIBILITY inline
560const typename tuple_element<_Ip, pair<_T1, _T2> >::type&
561get(const pair<_T1, _T2>& __p) _NOEXCEPT
562{
563    return __get_pair<_Ip>::get(__p);
564}
565
566#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
567
568template <size_t _Ip, class _T1, class _T2>
569_LIBCPP_INLINE_VISIBILITY inline
570typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
571get(pair<_T1, _T2>&& __p) _NOEXCEPT
572{
573    return __get_pair<_Ip>::get(_VSTD::move(__p));
574}
575
576#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
577
578#endif  // _LIBCPP_HAS_NO_VARIADICS
579
580_LIBCPP_END_NAMESPACE_STD
581
582#endif  // _LIBCPP_UTILITY
583