libstdc++-v3/include/ext/algorithm

   1 // Algorithm extensions -*- C++ -*-
   2
   3 // Copyright (C) 2001-2020 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 */