libstdc++-v3/include/ext/algorithm

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