1    	// <utility> -*- C++ -*-
2    	
3    	// Copyright (C) 2001-2017 Free Software Foundation, Inc.
4    	//
5    	// This file is part of the GNU ISO C++ Library.  This library is free
6    	// software; you can redistribute it and/or modify it under the
7    	// terms of the GNU General Public License as published by the
8    	// Free Software Foundation; either version 3, or (at your option)
9    	// any later version.
10   	
11   	// This library is distributed in the hope that it will be useful,
12   	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13   	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   	// GNU General Public License for more details.
15   	
16   	// Under Section 7 of GPL version 3, you are granted additional
17   	// permissions described in the GCC Runtime Library Exception, version
18   	// 3.1, as published by the Free Software Foundation.
19   	
20   	// You should have received a copy of the GNU General Public License and
21   	// a copy of the GCC Runtime Library Exception along with this program;
22   	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23   	// <http://www.gnu.org/licenses/>.
24   	
25   	/*
26   	 *
27   	 * Copyright (c) 1994
28   	 * Hewlett-Packard Company
29   	 *
30   	 * Permission to use, copy, modify, distribute and sell this software
31   	 * and its documentation for any purpose is hereby granted without fee,
32   	 * provided that the above copyright notice appear in all copies and
33   	 * that both that copyright notice and this permission notice appear
34   	 * in supporting documentation.  Hewlett-Packard Company makes no
35   	 * representations about the suitability of this software for any
36   	 * purpose.  It is provided "as is" without express or implied warranty.
37   	 *
38   	 *
39   	 * Copyright (c) 1996,1997
40   	 * Silicon Graphics Computer Systems, Inc.
41   	 *
42   	 * Permission to use, copy, modify, distribute and sell this software
43   	 * and its documentation for any purpose is hereby granted without fee,
44   	 * provided that the above copyright notice appear in all copies and
45   	 * that both that copyright notice and this permission notice appear
46   	 * in supporting documentation.  Silicon Graphics makes no
47   	 * representations about the suitability of this software for any
48   	 * purpose.  It is provided "as is" without express or implied warranty.
49   	 */
50   	
51   	/** @file include/utility
52   	 *  This is a Standard C++ Library header.
53   	 */
54   	
55   	#ifndef _GLIBCXX_UTILITY
56   	#define _GLIBCXX_UTILITY 1
57   	
58   	#pragma GCC system_header
59   	
60   	/**
61   	 * @defgroup utilities Utilities
62   	 *
63   	 * Components deemed generally useful. Includes pair, tuple,
64   	 * forward/move helpers, ratio, function object, metaprogramming and
65   	 * type traits, time, date, and memory functions.
66   	 */
67   	
68   	#include <bits/c++config.h>
69   	#include <bits/stl_relops.h>
70   	#include <bits/stl_pair.h>
71   	
72   	#if __cplusplus >= 201103L
73   	
74   	#include <type_traits>
75   	#include <bits/move.h>
76   	#include <initializer_list>
77   	
78   	namespace std _GLIBCXX_VISIBILITY(default)
79   	{
80   	_GLIBCXX_BEGIN_NAMESPACE_VERSION
81   	
82   	  /// Finds the size of a given tuple type.
83   	  template<typename _Tp>
84   	    struct tuple_size;
85   	
86   	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
87   	  // 2770. tuple_size<const T> specialization is not SFINAE compatible
88   	
89   	#if __cplusplus <= 201402L
90   	  template<typename _Tp, typename = void>
91   	    struct __tuple_size_cv_impl { };
92   	
93   	  template<typename _Tp>
94   	    struct __tuple_size_cv_impl<_Tp, __void_t<decltype(tuple_size<_Tp>::value)>>
95   	    : integral_constant<size_t, tuple_size<_Tp>::value> { };
96   	
97   	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
98   	  // 2313. tuple_size should always derive from integral_constant<size_t, N>
99   	  template<typename _Tp>
100  	    struct tuple_size<const _Tp> : __tuple_size_cv_impl<_Tp> { };
101  	
102  	  template<typename _Tp>
103  	    struct tuple_size<volatile _Tp> : __tuple_size_cv_impl<_Tp> { };
104  	
105  	  template<typename _Tp>
106  	    struct tuple_size<const volatile _Tp> : __tuple_size_cv_impl<_Tp> { };
107  	#else
108  	  template<typename _Tp,
109  		   typename _Up = typename remove_cv<_Tp>::type,
110  		   typename = typename enable_if<is_same<_Tp, _Up>::value>::type,
111  		   size_t = tuple_size<_Tp>::value>
112  	    using __enable_if_has_tuple_size = _Tp;
113  	
114  	  template<typename _Tp>
115  	    struct tuple_size<const __enable_if_has_tuple_size<_Tp>>
116  	    : public tuple_size<_Tp> { };
117  	
118  	  template<typename _Tp>
119  	    struct tuple_size<volatile __enable_if_has_tuple_size<_Tp>>
120  	    : public tuple_size<_Tp> { };
121  	
122  	  template<typename _Tp>
123  	    struct tuple_size<const volatile __enable_if_has_tuple_size<_Tp>>
124  	    : public tuple_size<_Tp> { };
125  	#endif
126  	
127  	  /// Gives the type of the ith element of a given tuple type.
128  	  template<std::size_t __i, typename _Tp>
129  	    struct tuple_element;
130  	
131  	  // Duplicate of C++14's tuple_element_t for internal use in C++11 mode
132  	  template<std::size_t __i, typename _Tp>
133  	    using __tuple_element_t = typename tuple_element<__i, _Tp>::type;
134  	
135  	  template<std::size_t __i, typename _Tp>
136  	    struct tuple_element<__i, const _Tp>
137  	    {
138  	      typedef typename add_const<__tuple_element_t<__i, _Tp>>::type type;
139  	    };
140  	
141  	  template<std::size_t __i, typename _Tp>
142  	    struct tuple_element<__i, volatile _Tp>
143  	    {
144  	      typedef typename add_volatile<__tuple_element_t<__i, _Tp>>::type type;
145  	    };
146  	
147  	  template<std::size_t __i, typename _Tp>
148  	    struct tuple_element<__i, const volatile _Tp>
149  	    {
150  	      typedef typename add_cv<__tuple_element_t<__i, _Tp>>::type type;
151  	    };
152  	
153  	#if __cplusplus > 201103L
154  	#define __cpp_lib_tuple_element_t 201402
155  	
156  	  template<std::size_t __i, typename _Tp>
157  	    using tuple_element_t = typename tuple_element<__i, _Tp>::type;
158  	#endif
159  	
160  	  // Various functions which give std::pair a tuple-like interface.
161  	
162  	  /// Partial specialization for std::pair
163  	  template<typename _T1, typename _T2>
164  	    struct __is_tuple_like_impl<std::pair<_T1, _T2>> : true_type
165  	    { };
166  	
167  	  /// Partial specialization for std::pair
168  	  template<class _Tp1, class _Tp2>
169  	    struct tuple_size<std::pair<_Tp1, _Tp2>>
170  	    : public integral_constant<std::size_t, 2> { };
171  	
172  	  /// Partial specialization for std::pair
173  	  template<class _Tp1, class _Tp2>
174  	    struct tuple_element<0, std::pair<_Tp1, _Tp2>>
175  	    { typedef _Tp1 type; };
176  	
177  	  /// Partial specialization for std::pair
178  	  template<class _Tp1, class _Tp2>
179  	    struct tuple_element<1, std::pair<_Tp1, _Tp2>>
180  	    { typedef _Tp2 type; };
181  	
182  	  template<std::size_t _Int>
183  	    struct __pair_get;
184  	
185  	  template<>
186  	    struct __pair_get<0>
187  	    {
188  	      template<typename _Tp1, typename _Tp2>
189  	        static constexpr _Tp1&
190  	        __get(std::pair<_Tp1, _Tp2>& __pair) noexcept
191  	        { return __pair.first; }
192  	
193  	      template<typename _Tp1, typename _Tp2>
194  	        static constexpr _Tp1&&
195  	        __move_get(std::pair<_Tp1, _Tp2>&& __pair) noexcept
196  	        { return std::forward<_Tp1>(__pair.first); }
197  	
198  	      template<typename _Tp1, typename _Tp2>
199  	        static constexpr const _Tp1&
200  	        __const_get(const std::pair<_Tp1, _Tp2>& __pair) noexcept
201  	        { return __pair.first; }
202  	    };
203  	
204  	  template<>
205  	    struct __pair_get<1>
206  	    {
207  	      template<typename _Tp1, typename _Tp2>
208  	        static constexpr _Tp2&
209  	        __get(std::pair<_Tp1, _Tp2>& __pair) noexcept
210  	        { return __pair.second; }
211  	
212  	      template<typename _Tp1, typename _Tp2>
213  	        static constexpr _Tp2&&
214  	        __move_get(std::pair<_Tp1, _Tp2>&& __pair) noexcept
215  	        { return std::forward<_Tp2>(__pair.second); }
216  	
217  	      template<typename _Tp1, typename _Tp2>
218  	        static constexpr const _Tp2&
219  	        __const_get(const std::pair<_Tp1, _Tp2>& __pair) noexcept
220  	        { return __pair.second; }
221  	    };
222  	
223  	  template<std::size_t _Int, class _Tp1, class _Tp2>
224  	    constexpr typename tuple_element<_Int, std::pair<_Tp1, _Tp2>>::type&
225  	    get(std::pair<_Tp1, _Tp2>& __in) noexcept
226  	    { return __pair_get<_Int>::__get(__in); }
227  	
228  	  template<std::size_t _Int, class _Tp1, class _Tp2>
229  	    constexpr typename tuple_element<_Int, std::pair<_Tp1, _Tp2>>::type&&
230  	    get(std::pair<_Tp1, _Tp2>&& __in) noexcept
231  	    { return __pair_get<_Int>::__move_get(std::move(__in)); }
232  	
233  	  template<std::size_t _Int, class _Tp1, class _Tp2>
234  	    constexpr const typename tuple_element<_Int, std::pair<_Tp1, _Tp2>>::type&
235  	    get(const std::pair<_Tp1, _Tp2>& __in) noexcept
236  	    { return __pair_get<_Int>::__const_get(__in); }
237  	
238  	#if __cplusplus > 201103L
239  	
240  	#define __cpp_lib_tuples_by_type 201304
241  	
242  	  template <typename _Tp, typename _Up>
243  	    constexpr _Tp&
244  	    get(pair<_Tp, _Up>& __p) noexcept
245  	    { return __p.first; }
246  	
247  	  template <typename _Tp, typename _Up>
248  	    constexpr const _Tp&
249  	    get(const pair<_Tp, _Up>& __p) noexcept
250  	    { return __p.first; }
251  	
252  	  template <typename _Tp, typename _Up>
253  	    constexpr _Tp&&
254  	    get(pair<_Tp, _Up>&& __p) noexcept
255  	    { return std::move(__p.first); }
256  	
257  	  template <typename _Tp, typename _Up>
258  	    constexpr _Tp&
259  	    get(pair<_Up, _Tp>& __p) noexcept
260  	    { return __p.second; }
261  	
262  	  template <typename _Tp, typename _Up>
263  	    constexpr const _Tp&
264  	    get(const pair<_Up, _Tp>& __p) noexcept
265  	    { return __p.second; }
266  	
267  	  template <typename _Tp, typename _Up>
268  	    constexpr _Tp&&
269  	    get(pair<_Up, _Tp>&& __p) noexcept
270  	    { return std::move(__p.second); }
271  	
272  	#define __cpp_lib_exchange_function 201304
273  	
274  	  /// Assign @p __new_val to @p __obj and return its previous value.
275  	  template <typename _Tp, typename _Up = _Tp>
276  	    inline _Tp
277  	    exchange(_Tp& __obj, _Up&& __new_val)
278  	    { return std::__exchange(__obj, std::forward<_Up>(__new_val)); }
279  	#endif
280  	
281  	  // Stores a tuple of indices.  Used by tuple and pair, and by bind() to
282  	  // extract the elements in a tuple.
283  	  template<size_t... _Indexes> struct _Index_tuple { };
284  	
285  	  // Concatenates two _Index_tuples.
286  	  template<typename _Itup1, typename _Itup2> struct _Itup_cat;
287  	
288  	  template<size_t... _Ind1, size_t... _Ind2>
289  	    struct _Itup_cat<_Index_tuple<_Ind1...>, _Index_tuple<_Ind2...>>
290  	    {
291  	      using __type = _Index_tuple<_Ind1..., (_Ind2 + sizeof...(_Ind1))...>;
292  	    };
293  	
294  	  // Builds an _Index_tuple<0, 1, 2, ..., _Num-1>.
295  	  template<size_t _Num>
296  	    struct _Build_index_tuple
297  	    : _Itup_cat<typename _Build_index_tuple<_Num / 2>::__type,
298  			typename _Build_index_tuple<_Num - _Num / 2>::__type>
299  	    { };
300  	
301  	  template<>
302  	    struct _Build_index_tuple<1>
303  	    {
304  	      typedef _Index_tuple<0> __type;
305  	    };
306  	
307  	  template<>
308  	    struct _Build_index_tuple<0>
309  	    {
310  	      typedef _Index_tuple<> __type;
311  	    };
312  	
313  	#if __cplusplus > 201103L
314  	
315  	#define __cpp_lib_integer_sequence 201304
316  	
317  	  /// Class template integer_sequence
318  	  template<typename _Tp, _Tp... _Idx>
319  	    struct integer_sequence
320  	    {
321  	      typedef _Tp value_type;
322  	      static constexpr size_t size() noexcept { return sizeof...(_Idx); }
323  	    };
324  	
325  	  template<typename _Tp, _Tp _Num,
326  		   typename _ISeq = typename _Build_index_tuple<_Num>::__type>
327  	    struct _Make_integer_sequence;
328  	
329  	  template<typename _Tp, _Tp _Num,  size_t... _Idx>
330  	    struct _Make_integer_sequence<_Tp, _Num, _Index_tuple<_Idx...>>
331  	    {
332  	      static_assert( _Num >= 0,
333  			     "Cannot make integer sequence of negative length" );
334  	
335  	      typedef integer_sequence<_Tp, static_cast<_Tp>(_Idx)...> __type;
336  	    };
337  	
338  	  /// Alias template make_integer_sequence
339  	  template<typename _Tp, _Tp _Num>
340  	    using make_integer_sequence
341  	      = typename _Make_integer_sequence<_Tp, _Num>::__type;
342  	
343  	  /// Alias template index_sequence
344  	  template<size_t... _Idx>
345  	    using index_sequence = integer_sequence<size_t, _Idx...>;
346  	
347  	  /// Alias template make_index_sequence
348  	  template<size_t _Num>
349  	    using make_index_sequence = make_integer_sequence<size_t, _Num>;
350  	
351  	  /// Alias template index_sequence_for
352  	  template<typename... _Types>
353  	    using index_sequence_for = make_index_sequence<sizeof...(_Types)>;
354  	#endif
355  	
356  	#if __cplusplus > 201402L
357  	
358  	  struct in_place_t {
359  	    explicit in_place_t() = default;
360  	  };
361  	
362  	  inline constexpr in_place_t in_place{};
363  	
364  	  template<typename _Tp> struct in_place_type_t
365  	  {
366  	    explicit in_place_type_t() = default;
367  	  };
368  	
369  	  template<typename _Tp>
370  	    inline constexpr in_place_type_t<_Tp> in_place_type{};
371  	
372  	  template<size_t _Idx> struct in_place_index_t
373  	  {
374  	    explicit in_place_index_t() = default;
375  	  };
376  	
377  	  template<size_t _Idx>
378  	    inline constexpr in_place_index_t<_Idx> in_place_index{};
379  	
380  	  template<typename>
381  	    struct __is_in_place_type_impl : false_type
382  	    { };
383  	
384  	  template<typename _Tp>
385  	    struct __is_in_place_type_impl<in_place_type_t<_Tp>> : true_type
386  	    { };
387  	
388  	  template<typename _Tp>
389  	    struct __is_in_place_type
390  	      : public __is_in_place_type_impl<_Tp>
391  	    { };
392  	
393  	#define  __cpp_lib_as_const 201510
394  	  template<typename _Tp>
395  	    constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; }
396  	
397  	  template<typename _Tp>
398  	    void as_const(const _Tp&&) = delete;
399  	
400  	#endif // C++17
401  	
402  	_GLIBCXX_END_NAMESPACE_VERSION
403  	} // namespace
404  	
405  	#endif
406  	
407  	#endif /* _GLIBCXX_UTILITY */
408