contrib/gcc-4.4/libstdc++-v3/include/ext/algorithm

   1 // Algorithm extensions -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   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 __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    *  "lexigraphically less than" the second, greater than zero if the second
 193    *  range is "lexigraphically less than" the first, and zero otherwise.
 194    *  This is an SGI extension.
 195    *  @ingroup SGIextensions
 196   */
 197   template<typename _InputIterator1, typename _InputIterator2>
 198     int
 199     lexicographical_compare_3way(_InputIterator1 __first1,
 200                                  _InputIterator1 __last1,
 201                                  _InputIterator2 __first2,
 202                                  _InputIterator2 __last2)
 203     {
 204       // concept requirements
 205       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 206       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 207       __glibcxx_function_requires(_LessThanComparableConcept<
 208             typename iterator_traits<_InputIterator1>::value_type>)
 209       __glibcxx_function_requires(_LessThanComparableConcept<
 210             typename iterator_traits<_InputIterator2>::value_type>)
 211       __glibcxx_requires_valid_range(__first1, __last1);
 212       __glibcxx_requires_valid_range(__first2, __last2);
 213
 214       return __lexicographical_compare_3way(__first1, __last1, __first2,
 215                                             __last2);
 216     }
 217
 218   // count and count_if: this version, whose return type is void, was present
 219   // in the HP STL, and is retained as an extension for backward compatibility.
 220   template<typename _InputIterator, typename _Tp, typename _Size>
 221     void
 222     count(_InputIterator __first, _InputIterator __last,
 223           const _Tp& __value,
 224           _Size& __n)
 225     {
 226       // concept requirements
 227       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 228       __glibcxx_function_requires(_EqualityComparableConcept<
 229             typename iterator_traits<_InputIterator>::value_type >)
 230       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
 231       __glibcxx_requires_valid_range(__first, __last);
 232
 233       for ( ; __first != __last; ++__first)
 234         if (*__first == __value)
 235           ++__n;
 236     }
 237
 238   template<typename _InputIterator, typename _Predicate, typename _Size>
 239     void
 240     count_if(_InputIterator __first, _InputIterator __last,
 241              _Predicate __pred,
 242              _Size& __n)
 243     {
 244       // concept requirements
 245       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 246       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 247             typename iterator_traits<_InputIterator>::value_type>)
 248       __glibcxx_requires_valid_range(__first, __last);
 249
 250       for ( ; __first != __last; ++__first)
 251         if (__pred(*__first))
 252           ++__n;
 253     }
 254
 255   // random_sample and random_sample_n (extensions, not part of the standard).
 256
 257   /**
 258    *  This is an SGI extension.
 259    *  @ingroup SGIextensions
 260    *  @doctodo
 261   */
 262   template<typename _ForwardIterator, typename _OutputIterator,
 263            typename _Distance>
 264     _OutputIterator
 265     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 266                     _OutputIterator __out, const _Distance __n)
 267     {
 268       // concept requirements
 269       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 270       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 271                 typename iterator_traits<_ForwardIterator>::value_type>)
 272       __glibcxx_requires_valid_range(__first, __last);
 273
 274       _Distance __remaining = std::distance(__first, __last);
 275       _Distance __m = min(__n, __remaining);
 276
 277       while (__m > 0)
 278         {
 279           if ((std::rand() % __remaining) < __m)
 280             {
 281               *__out = *__first;
 282               ++__out;
 283               --__m;
 284             }
 285           --__remaining;
 286           ++__first;
 287         }
 288       return __out;
 289     }
 290
 291   /**
 292    *  This is an SGI extension.
 293    *  @ingroup SGIextensions
 294    *  @doctodo
 295   */
 296   template<typename _ForwardIterator, typename _OutputIterator,
 297            typename _Distance, typename _RandomNumberGenerator>
 298     _OutputIterator
 299     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 300                    _OutputIterator __out, const _Distance __n,
 301                    _RandomNumberGenerator& __rand)
 302     {
 303       // concept requirements
 304       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 305       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 306                 typename iterator_traits<_ForwardIterator>::value_type>)
 307       __glibcxx_function_requires(_UnaryFunctionConcept<
 308                 _RandomNumberGenerator, _Distance, _Distance>)
 309       __glibcxx_requires_valid_range(__first, __last);
 310
 311       _Distance __remaining = std::distance(__first, __last);
 312       _Distance __m = min(__n, __remaining);
 313
 314       while (__m > 0)
 315         {
 316           if (__rand(__remaining) < __m)
 317             {
 318               *__out = *__first;
 319               ++__out;
 320               --__m;
 321             }
 322           --__remaining;
 323           ++__first;
 324         }
 325       return __out;
 326     }
 327
 328   template<typename _InputIterator, typename _RandomAccessIterator,
 329            typename _Distance>
 330     _RandomAccessIterator
 331     __random_sample(_InputIterator __first, _InputIterator __last,
 332                     _RandomAccessIterator __out,
 333                     const _Distance __n)
 334     {
 335       _Distance __m = 0;
 336       _Distance __t = __n;
 337       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 338         __out[__m] = *__first;
 339
 340       while (__first != __last)
 341         {
 342           ++__t;
 343           _Distance __M = std::rand() % (__t);
 344           if (__M < __n)
 345             __out[__M] = *__first;
 346           ++__first;
 347         }
 348       return __out + __m;
 349     }
 350
 351   template<typename _InputIterator, typename _RandomAccessIterator,
 352            typename _RandomNumberGenerator, typename _Distance>
 353     _RandomAccessIterator
 354     __random_sample(_InputIterator __first, _InputIterator __last,
 355                     _RandomAccessIterator __out,
 356                     _RandomNumberGenerator& __rand,
 357                     const _Distance __n)
 358     {
 359       // concept requirements
 360       __glibcxx_function_requires(_UnaryFunctionConcept<
 361             _RandomNumberGenerator, _Distance, _Distance>)
 362
 363       _Distance __m = 0;
 364       _Distance __t = __n;
 365       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 366         __out[__m] = *__first;
 367
 368       while (__first != __last)
 369         {
 370           ++__t;
 371           _Distance __M = __rand(__t);
 372           if (__M < __n)
 373             __out[__M] = *__first;
 374           ++__first;
 375         }
 376       return __out + __m;
 377     }
 378
 379   /**
 380    *  This is an SGI extension.
 381    *  @ingroup SGIextensions
 382    *  @doctodo
 383   */
 384   template<typename _InputIterator, typename _RandomAccessIterator>
 385     inline _RandomAccessIterator
 386     random_sample(_InputIterator __first, _InputIterator __last,
 387                   _RandomAccessIterator __out_first,
 388                   _RandomAccessIterator __out_last)
 389     {
 390       // concept requirements
 391       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 392       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 393             _RandomAccessIterator>)
 394       __glibcxx_requires_valid_range(__first, __last);
 395       __glibcxx_requires_valid_range(__out_first, __out_last);
 396
 397       return __random_sample(__first, __last,
 398                              __out_first, __out_last - __out_first);
 399     }
 400
 401   /**
 402    *  This is an SGI extension.
 403    *  @ingroup SGIextensions
 404    *  @doctodo
 405   */
 406   template<typename _InputIterator, typename _RandomAccessIterator,
 407            typename _RandomNumberGenerator>
 408     inline _RandomAccessIterator
 409     random_sample(_InputIterator __first, _InputIterator __last,
 410                   _RandomAccessIterator __out_first,
 411                   _RandomAccessIterator __out_last,
 412                   _RandomNumberGenerator& __rand)
 413     {
 414       // concept requirements
 415       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 416       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 417             _RandomAccessIterator>)
 418       __glibcxx_requires_valid_range(__first, __last);
 419       __glibcxx_requires_valid_range(__out_first, __out_last);
 420
 421       return __random_sample(__first, __last,
 422                              __out_first, __rand,
 423                              __out_last - __out_first);
 424     }
 425
 426   /**
 427    *  This is an SGI extension.
 428    *  @ingroup SGIextensions
 429    *  @doctodo
 430   */
 431   template<typename _RandomAccessIterator>
 432     inline bool
 433     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 434     {
 435       // concept requirements
 436       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 437                                   _RandomAccessIterator>)
 438       __glibcxx_function_requires(_LessThanComparableConcept<
 439             typename iterator_traits<_RandomAccessIterator>::value_type>)
 440       __glibcxx_requires_valid_range(__first, __last);
 441
 442       return std::__is_heap(__first, __last - __first);
 443     }
 444
 445   /**
 446    *  This is an SGI extension.
 447    *  @ingroup SGIextensions
 448    *  @doctodo
 449   */
 450   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
 451     inline bool
 452     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 453             _StrictWeakOrdering __comp)
 454     {
 455       // concept requirements
 456       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 457                                   _RandomAccessIterator>)
 458       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 459             typename iterator_traits<_RandomAccessIterator>::value_type,
 460             typename iterator_traits<_RandomAccessIterator>::value_type>)
 461       __glibcxx_requires_valid_range(__first, __last);
 462
 463       return std::__is_heap(__first, __comp, __last - __first);
 464     }
 465
 466   // is_sorted, a predicated testing whether a range is sorted in
 467   // nondescending order.  This is an extension, not part of the C++
 468   // standard.
 469
 470   /**
 471    *  This is an SGI extension.
 472    *  @ingroup SGIextensions
 473    *  @doctodo
 474   */
 475   template<typename _ForwardIterator>
 476     bool
 477     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
 478     {
 479       // concept requirements
 480       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 481       __glibcxx_function_requires(_LessThanComparableConcept<
 482             typename iterator_traits<_ForwardIterator>::value_type>)
 483       __glibcxx_requires_valid_range(__first, __last);
 484
 485       if (__first == __last)
 486         return true;
 487
 488       _ForwardIterator __next = __first;
 489       for (++__next; __next != __last; __first = __next, ++__next)
 490         if (*__next < *__first)
 491           return false;
 492       return true;
 493     }
 494
 495   /**
 496    *  This is an SGI extension.
 497    *  @ingroup SGIextensions
 498    *  @doctodo
 499   */
 500   template<typename _ForwardIterator, typename _StrictWeakOrdering>
 501     bool
 502     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
 503               _StrictWeakOrdering __comp)
 504     {
 505       // concept requirements
 506       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 507       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 508             typename iterator_traits<_ForwardIterator>::value_type,
 509             typename iterator_traits<_ForwardIterator>::value_type>)
 510       __glibcxx_requires_valid_range(__first, __last);
 511
 512       if (__first == __last)
 513         return true;
 514
 515       _ForwardIterator __next = __first;
 516       for (++__next; __next != __last; __first = __next, ++__next)
 517         if (__comp(*__next, *__first))
 518           return false;
 519       return true;
 520     }
 521
 522 _GLIBCXX_END_NAMESPACE
 523
 524 #endif /* _EXT_ALGORITHM */