libstdc++-v3/include/ext/algorithm

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