libstdc++-v3/include/ext/algorithm

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