The C and C++ Include Header Files

/usr/include/c++/11/ext/algorithm


$ cat -n /usr/include/c++/11/ext/algorithm

     1	// Algorithm extensions -*- C++ -*-
     2	
     3	// Copyright (C) 2001-2021 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
    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 ext/algorithm
    52	 *  This file is a GNU extension to the Standard C++ Library (possibly
    53	 *  containing extensions from the HP/SGI STL subset).
    54	 */
    55	
    56	#ifndef _EXT_ALGORITHM
    57	#define _EXT_ALGORITHM 1
    58	
    59	#pragma GCC system_header
    60	
    61	#include <algorithm>
    62	
    63	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
    64	{
    65	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    66	
    67	  //--------------------------------------------------
    68	  // copy_n (not part of the C++ standard)
    69	
    70	  template<typename _InputIterator, typename _Size, typename _OutputIterator>
    71	    std::pair<_InputIterator, _OutputIterator>
    72	    __copy_n(_InputIterator __first, _Size __count,
    73		     _OutputIterator __result,
    74		     std::input_iterator_tag)
    75	    {
    76	      for ( ; __count > 0; --__count)
    77		{
    78		  *__result = *__first;
    79		  ++__first;
    80		  ++__result;
    81		}
    82	      return std::pair<_InputIterator, _OutputIterator>(__first, __result);
    83	    }
    84	
    85	  template<typename _RAIterator, typename _Size, typename _OutputIterator>
    86	    inline std::pair<_RAIterator, _OutputIterator>
    87	    __copy_n(_RAIterator __first, _Size __count,
    88		     _OutputIterator __result,
    89		     std::random_access_iterator_tag)
    90	    {
    91	      _RAIterator __last = __first + __count;
    92	      return std::pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
    93									  __last,
    94									  __result));
    95	    }
    96	
    97	  /**
    98	   *  @brief Copies the range [first,first+count) into [result,result+count).
    99	   *  @param  __first  An input iterator.
   100	   *  @param  __count  The number of elements to copy.
   101	   *  @param  __result An output iterator.
   102	   *  @return   A std::pair composed of first+count and result+count.
   103	   *
   104	   *  This is an SGI extension.
   105	   *  This inline function will boil down to a call to @c memmove whenever
   106	   *  possible.  Failing that, if random access iterators are passed, then the
   107	   *  loop count will be known (and therefore a candidate for compiler
   108	   *  optimizations such as unrolling).
   109	   *  @ingroup SGIextensions
   110	  */
   111	  template<typename _InputIterator, typename _Size, typename _OutputIterator>
   112	    inline std::pair<_InputIterator, _OutputIterator>
   113	    copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
   114	    {
   115	      // concept requirements
   116	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
   117	      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   118		    typename std::iterator_traits<_InputIterator>::value_type>)
   119	
   120	      return __gnu_cxx::__copy_n(__first, __count, __result,
   121					 std::__iterator_category(__first));
   122	    }
   123	
   124	  template<typename _InputIterator1, typename _InputIterator2>
   125	    int
   126	    __lexicographical_compare_3way(_InputIterator1 __first1,
   127					   _InputIterator1 __last1,
   128					   _InputIterator2 __first2,
   129					   _InputIterator2 __last2)
   130	    {
   131	      while (__first1 != __last1 && __first2 != __last2)
   132		{
   133		  if (*__first1 < *__first2)
   134		    return -1;
   135		  if (*__first2 < *__first1)
   136		    return 1;
   137		  ++__first1;
   138		  ++__first2;
   139		}
   140	      if (__first2 == __last2)
   141		return !(__first1 == __last1);
   142	      else
   143		return -1;
   144	    }
   145	
   146	  inline int
   147	  __lexicographical_compare_3way(const unsigned char* __first1,
   148					 const unsigned char* __last1,
   149					 const unsigned char* __first2,
   150					 const unsigned char* __last2)
   151	  {
   152	    const std::ptrdiff_t __len1 = __last1 - __first1;
   153	    const std::ptrdiff_t __len2 = __last2 - __first2;
   154	    const int __result = __builtin_memcmp(__first1, __first2,
   155						  (std::min)(__len1, __len2));
   156	    return __result != 0 ? __result
   157				 : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
   158	  }
   159	
   160	  inline int
   161	  __lexicographical_compare_3way(const char* __first1, const char* __last1,
   162					 const char* __first2, const char* __last2)
   163	  {
   164	#if CHAR_MAX == SCHAR_MAX
   165	    return __lexicographical_compare_3way((const signed char*) __first1,
   166						  (const signed char*) __last1,
   167						  (const signed char*) __first2,
   168						  (const signed char*) __last2);
   169	#else
   170	    return __lexicographical_compare_3way((const unsigned char*) __first1,
   171						  (const unsigned char*) __last1,
   172						  (const unsigned char*) __first2,
   173						  (const unsigned char*) __last2);
   174	#endif
   175	  }
   176	
   177	  /**
   178	   *  @brief @c memcmp on steroids.
   179	   *  @param  __first1  An input iterator.
   180	   *  @param  __last1   An input iterator.
   181	   *  @param  __first2  An input iterator.
   182	   *  @param  __last2   An input iterator.
   183	   *  @return   An int, as with @c memcmp.
   184	   *
   185	   *  The return value will be less than zero if the first range is
   186	   *  <em>lexigraphically less than</em> the second, greater than zero
   187	   *  if the second range is <em>lexigraphically less than</em> the
   188	   *  first, and zero otherwise.
   189	   *  This is an SGI extension.
   190	   *  @ingroup SGIextensions
   191	  */
   192	  template<typename _InputIterator1, typename _InputIterator2>
   193	    int
   194	    lexicographical_compare_3way(_InputIterator1 __first1,
   195					 _InputIterator1 __last1,
   196					 _InputIterator2 __first2,
   197					 _InputIterator2 __last2)
   198	    {
   199	      // concept requirements
   200	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
   201	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
   202	      __glibcxx_function_requires(_LessThanComparableConcept<
   203		    typename std::iterator_traits<_InputIterator1>::value_type>)
   204	      __glibcxx_function_requires(_LessThanComparableConcept<
   205		    typename std::iterator_traits<_InputIterator2>::value_type>)
   206	      __glibcxx_requires_valid_range(__first1, __last1);
   207	      __glibcxx_requires_valid_range(__first2, __last2);
   208	
   209	      return __lexicographical_compare_3way(__first1, __last1, __first2,
   210						    __last2);
   211	    }
   212	
   213	  // count and count_if: this version, whose return type is void, was present
   214	  // in the HP STL, and is retained as an extension for backward compatibility.
   215	  template<typename _InputIterator, typename _Tp, typename _Size>
   216	    void
   217	    count(_InputIterator __first, _InputIterator __last,
   218		  const _Tp& __value,
   219		  _Size& __n)
   220	    {
   221	      // concept requirements
   222	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
   223	      __glibcxx_function_requires(_EqualityComparableConcept<
   224		    typename std::iterator_traits<_InputIterator>::value_type >)
   225	      __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
   226	      __glibcxx_requires_valid_range(__first, __last);
   227	
   228	      for ( ; __first != __last; ++__first)
   229		if (*__first == __value)
   230		  ++__n;
   231	    }
   232	
   233	  template<typename _InputIterator, typename _Predicate, typename _Size>
   234	    void
   235	    count_if(_InputIterator __first, _InputIterator __last,
   236		     _Predicate __pred,
   237		     _Size& __n)
   238	    {
   239	      // concept requirements
   240	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
   241	      __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
   242		    typename std::iterator_traits<_InputIterator>::value_type>)
   243	      __glibcxx_requires_valid_range(__first, __last);
   244	
   245	      for ( ; __first != __last; ++__first)
   246		if (__pred(*__first))
   247		  ++__n;
   248	    }
   249	
   250	  // random_sample and random_sample_n (extensions, not part of the standard).
   251	
   252	  /**
   253	   *  This is an SGI extension.
   254	   *  @ingroup SGIextensions
   255	   *  @doctodo
   256	  */
   257	  template<typename _ForwardIterator, typename _OutputIterator,
   258		   typename _Distance>
   259	    _OutputIterator
   260	    random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
   261	                    _OutputIterator __out, const _Distance __n)
   262	    {
   263	      // concept requirements
   264	      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
   265	      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   266			typename std::iterator_traits<_ForwardIterator>::value_type>)
   267	      __glibcxx_requires_valid_range(__first, __last);
   268	
   269	      _Distance __remaining = std::distance(__first, __last);
   270	      _Distance __m = (std::min)(__n, __remaining);
   271	
   272	      while (__m > 0)
   273		{
   274		  if ((std::rand() % __remaining) < __m)
   275		    {
   276		      *__out = *__first;
   277		      ++__out;
   278		      --__m;
   279		    }
   280		  --__remaining;
   281		  ++__first;
   282		}
   283	      return __out;
   284	    }
   285	
   286	  /**
   287	   *  This is an SGI extension.
   288	   *  @ingroup SGIextensions
   289	   *  @doctodo
   290	  */
   291	  template<typename _ForwardIterator, typename _OutputIterator,
   292		   typename _Distance, typename _RandomNumberGenerator>
   293	    _OutputIterator
   294	    random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
   295	                   _OutputIterator __out, const _Distance __n,
   296			   _RandomNumberGenerator& __rand)
   297	    {
   298	      // concept requirements
   299	      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
   300	      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
   301			typename std::iterator_traits<_ForwardIterator>::value_type>)
   302	      __glibcxx_function_requires(_UnaryFunctionConcept<
   303			_RandomNumberGenerator, _Distance, _Distance>)
   304	      __glibcxx_requires_valid_range(__first, __last);
   305	
   306	      _Distance __remaining = std::distance(__first, __last);
   307	      _Distance __m = (std::min)(__n, __remaining);
   308	
   309	      while (__m > 0)
   310		{
   311		  if (__rand(__remaining) < __m)
   312		    {
   313		      *__out = *__first;
   314		      ++__out;
   315		      --__m;
   316		    }
   317		  --__remaining;
   318		  ++__first;
   319		}
   320	      return __out;
   321	    }
   322	
   323	  template<typename _InputIterator, typename _RandomAccessIterator,
   324		   typename _Distance>
   325	    _RandomAccessIterator
   326	    __random_sample(_InputIterator __first, _InputIterator __last,
   327			    _RandomAccessIterator __out,
   328			    const _Distance __n)
   329	    {
   330	      _Distance __m = 0;
   331	      _Distance __t = __n;
   332	      for ( ; __first != __last && __m < __n; ++__m, ++__first)
   333		__out[__m] = *__first;
   334	
   335	      while (__first != __last)
   336		{
   337		  ++__t;
   338		  _Distance __M = std::rand() % (__t);
   339		  if (__M < __n)
   340		    __out[__M] = *__first;
   341		  ++__first;
   342		}
   343	      return __out + __m;
   344	    }
   345	
   346	  template<typename _InputIterator, typename _RandomAccessIterator,
   347		   typename _RandomNumberGenerator, typename _Distance>
   348	    _RandomAccessIterator
   349	    __random_sample(_InputIterator __first, _InputIterator __last,
   350			    _RandomAccessIterator __out,
   351			    _RandomNumberGenerator& __rand,
   352			    const _Distance __n)
   353	    {
   354	      // concept requirements
   355	      __glibcxx_function_requires(_UnaryFunctionConcept<
   356		    _RandomNumberGenerator, _Distance, _Distance>)
   357	
   358	      _Distance __m = 0;
   359	      _Distance __t = __n;
   360	      for ( ; __first != __last && __m < __n; ++__m, ++__first)
   361		__out[__m] = *__first;
   362	
   363	      while (__first != __last)
   364		{
   365		  ++__t;
   366		  _Distance __M = __rand(__t);
   367		  if (__M < __n)
   368		    __out[__M] = *__first;
   369		  ++__first;
   370		}
   371	      return __out + __m;
   372	    }
   373	
   374	  /**
   375	   *  This is an SGI extension.
   376	   *  @ingroup SGIextensions
   377	   *  @doctodo
   378	  */
   379	  template<typename _InputIterator, typename _RandomAccessIterator>
   380	    inline _RandomAccessIterator
   381	    random_sample(_InputIterator __first, _InputIterator __last,
   382			  _RandomAccessIterator __out_first,
   383			  _RandomAccessIterator __out_last)
   384	    {
   385	      // concept requirements
   386	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
   387	      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   388		    _RandomAccessIterator>)
   389	      __glibcxx_requires_valid_range(__first, __last);
   390	      __glibcxx_requires_valid_range(__out_first, __out_last);
   391	
   392	      return __random_sample(__first, __last,
   393				     __out_first, __out_last - __out_first);
   394	    }
   395	
   396	  /**
   397	   *  This is an SGI extension.
   398	   *  @ingroup SGIextensions
   399	   *  @doctodo
   400	  */
   401	  template<typename _InputIterator, typename _RandomAccessIterator,
   402		   typename _RandomNumberGenerator>
   403	    inline _RandomAccessIterator
   404	    random_sample(_InputIterator __first, _InputIterator __last,
   405			  _RandomAccessIterator __out_first,
   406			  _RandomAccessIterator __out_last,
   407			  _RandomNumberGenerator& __rand)
   408	    {
   409	      // concept requirements
   410	      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
   411	      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
   412		    _RandomAccessIterator>)
   413	      __glibcxx_requires_valid_range(__first, __last);
   414	      __glibcxx_requires_valid_range(__out_first, __out_last);
   415	
   416	      return __random_sample(__first, __last,
   417				     __out_first, __rand,
   418				     __out_last - __out_first);
   419	    }
   420	
   421	#if __cplusplus >= 201103L
   422	  using std::is_heap;
   423	#else
   424	  /**
   425	   *  This is an SGI extension.
   426	   *  @ingroup SGIextensions
   427	   *  @doctodo
   428	  */
   429	  template<typename _RandomAccessIterator>
   430	    inline bool
   431	    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
   432	    {
   433	      // concept requirements
   434	      __glibcxx_function_requires(_RandomAccessIteratorConcept<
   435					  _RandomAccessIterator>)
   436	      __glibcxx_function_requires(_LessThanComparableConcept<
   437		    typename std::iterator_traits<_RandomAccessIterator>::value_type>)
   438	      __glibcxx_requires_valid_range(__first, __last);
   439	
   440	      return std::__is_heap(__first, __last - __first);
   441	    }
   442	
   443	  /**
   444	   *  This is an SGI extension.
   445	   *  @ingroup SGIextensions
   446	   *  @doctodo
   447	  */
   448	  template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
   449	    inline bool
   450	    is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
   451		    _StrictWeakOrdering __comp)
   452	    {
   453	      // concept requirements
   454	      __glibcxx_function_requires(_RandomAccessIteratorConcept<
   455					  _RandomAccessIterator>)
   456	      __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
   457		    typename std::iterator_traits<_RandomAccessIterator>::value_type,
   458		    typename std::iterator_traits<_RandomAccessIterator>::value_type>)
   459	      __glibcxx_requires_valid_range(__first, __last);
   460	
   461	      return std::__is_heap(__first, __comp, __last - __first);
   462	    }
   463	#endif
   464	
   465	#if __cplusplus >= 201103L
   466	  using std::is_sorted;
   467	#else
   468	  // is_sorted, a predicated testing whether a range is sorted in
   469	  // nondescending order.  This is an extension, not part of the C++
   470	  // standard.
   471	
   472	  /**
   473	   *  This is an SGI extension.
   474	   *  @ingroup SGIextensions
   475	   *  @doctodo
   476	  */
   477	  template<typename _ForwardIterator>
   478	    bool
   479	    is_sorted(_ForwardIterator __first, _ForwardIterator __last)
   480	    {
   481	      // concept requirements
   482	      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
   483	      __glibcxx_function_requires(_LessThanComparableConcept<
   484		    typename std::iterator_traits<_ForwardIterator>::value_type>)
   485	      __glibcxx_requires_valid_range(__first, __last);
   486	
   487	      if (__first == __last)
   488		return true;
   489	
   490	      _ForwardIterator __next = __first;
   491	      for (++__next; __next != __last; __first = __next, ++__next)
   492		if (*__next < *__first)
   493		  return false;
   494	      return true;
   495	    }
   496	
   497	  /**
   498	   *  This is an SGI extension.
   499	   *  @ingroup SGIextensions
   500	   *  @doctodo
   501	  */
   502	  template<typename _ForwardIterator, typename _StrictWeakOrdering>
   503	    bool
   504	    is_sorted(_ForwardIterator __first, _ForwardIterator __last,
   505		      _StrictWeakOrdering __comp)
   506	    {
   507	      // concept requirements
   508	      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
   509	      __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
   510		    typename std::iterator_traits<_ForwardIterator>::value_type,
   511		    typename std::iterator_traits<_ForwardIterator>::value_type>)
   512	      __glibcxx_requires_valid_range(__first, __last);
   513	
   514	      if (__first == __last)
   515		return true;
   516	
   517	      _ForwardIterator __next = __first;
   518	      for (++__next; __next != __last; __first = __next, ++__next)
   519		if (__comp(*__next, *__first))
   520		  return false;
   521	      return true;
   522	    }
   523	#endif  // C++11
   524	
   525	  /**
   526	   *  @brief Find the median of three values.
   527	   *  @param  __a  A value.
   528	   *  @param  __b  A value.
   529	   *  @param  __c  A value.
   530	   *  @return One of @p a, @p b or @p c.
   531	   *
   532	   *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
   533	   *  then the value returned will be @c m.
   534	   *  This is an SGI extension.
   535	   *  @ingroup SGIextensions
   536	  */
   537	  template<typename _Tp>
   538	    const _Tp&
   539	    __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
   540	    {
   541	      // concept requirements
   542	      __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
   543	      if (__a < __b)
   544		if (__b < __c)
   545		  return __b;
   546		else if (__a < __c)
   547		  return __c;
   548		else
   549		  return __a;
   550	      else if (__a < __c)
   551		return __a;
   552	      else if (__b < __c)
   553		return __c;
   554	      else
   555		return __b;
   556	    }
   557	
   558	  /**
   559	   *  @brief Find the median of three values using a predicate for comparison.
   560	   *  @param  __a     A value.
   561	   *  @param  __b     A value.
   562	   *  @param  __c     A value.
   563	   *  @param  __comp  A binary predicate.
   564	   *  @return One of @p a, @p b or @p c.
   565	   *
   566	   *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
   567	   *  and @p comp(m,n) are both true then the value returned will be @c m.
   568	   *  This is an SGI extension.
   569	   *  @ingroup SGIextensions
   570	  */
   571	  template<typename _Tp, typename _Compare>
   572	    const _Tp&
   573	    __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
   574	    {
   575	      // concept requirements
   576	      __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
   577					                         _Tp, _Tp>)
   578	      if (__comp(__a, __b))
   579		if (__comp(__b, __c))
   580		  return __b;
   581		else if (__comp(__a, __c))
   582		  return __c;
   583		else
   584		  return __a;
   585	      else if (__comp(__a, __c))
   586		return __a;
   587	      else if (__comp(__b, __c))
   588		return __c;
   589	      else
   590		return __b;
   591	    }
   592	
   593	_GLIBCXX_END_NAMESPACE_VERSION
   594	} // namespace
   595	
   596	#endif /* _EXT_ALGORITHM */