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

   1 // Algorithm extensions -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  *
  44  * Copyright (c) 1996
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file ext/algorithm
  57  *  This file is a GNU extension to the Standard C++ Library (possibly
  58  *  containing extensions from the HP/SGI STL subset).
  59  */
  60
  61 #ifndef _EXT_ALGORITHM
  62 #define _EXT_ALGORITHM 1
  63
  64 #pragma GCC system_header
  65
  66 #include <algorithm>
  67
  68 namespace __gnu_cxx
  69 {
  70   using std::ptrdiff_t;
  71   using std::min;
  72   using std::pair;
  73   using std::input_iterator_tag;
  74   using std::random_access_iterator_tag;
  75   using std::iterator_traits;
  76
  77   //--------------------------------------------------
  78   // copy_n (not part of the C++ standard)
  79
  80   template<typename _InputIterator, typename _Size, typename _OutputIterator>
  81     pair<_InputIterator, _OutputIterator>
  82     __copy_n(_InputIterator __first, _Size __count,
  83              _OutputIterator __result,
  84              input_iterator_tag)
  85     {
  86       for ( ; __count > 0; --__count)
  87         {
  88           *__result = *__first;
  89           ++__first;
  90           ++__result;
  91         }
  92       return pair<_InputIterator, _OutputIterator>(__first, __result);
  93     }
  94
  95   template<typename _RAIterator, typename _Size, typename _OutputIterator>
  96     inline pair<_RAIterator, _OutputIterator>
  97     __copy_n(_RAIterator __first, _Size __count,
  98              _OutputIterator __result,
  99              random_access_iterator_tag)
 100     {
 101       _RAIterator __last = __first + __count;
 102       return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
 103                                                                   __last,
 104                                                                   __result));
 105     }
 106
 107   /**
 108    *  @brief Copies the range [first,first+count) into [result,result+count).
 109    *  @param  first  An input iterator.
 110    *  @param  count  The number of elements to copy.
 111    *  @param  result An output iterator.
 112    *  @return   A std::pair composed of first+count and result+count.
 113    *
 114    *  This is an SGI extension.
 115    *  This inline function will boil down to a call to @c memmove whenever
 116    *  possible.  Failing that, if random access iterators are passed, then the
 117    *  loop count will be known (and therefore a candidate for compiler
 118    *  optimizations such as unrolling).
 119    *  @ingroup SGIextensions
 120   */
 121   template<typename _InputIterator, typename _Size, typename _OutputIterator>
 122     inline pair<_InputIterator, _OutputIterator>
 123     copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
 124     {
 125       // concept requirements
 126       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 127       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 128             typename iterator_traits<_InputIterator>::value_type>)
 129
 130       return __copy_n(__first, __count, __result,
 131                       std::__iterator_category(__first));
 132     }
 133
 134   template<typename _InputIterator1, typename _InputIterator2>
 135     int
 136     __lexicographical_compare_3way(_InputIterator1 __first1,
 137                                    _InputIterator1 __last1,
 138                                    _InputIterator2 __first2,
 139                                    _InputIterator2 __last2)
 140     {
 141       while (__first1 != __last1 && __first2 != __last2)
 142         {
 143           if (*__first1 < *__first2)
 144             return -1;
 145           if (*__first2 < *__first1)
 146             return 1;
 147           ++__first1;
 148           ++__first2;
 149         }
 150       if (__first2 == __last2)
 151         return !(__first1 == __last1);
 152       else
 153         return -1;
 154     }
 155
 156   inline int
 157   __lexicographical_compare_3way(const unsigned char* __first1,
 158                                  const unsigned char* __last1,
 159                                  const unsigned char* __first2,
 160                                  const unsigned char* __last2)
 161   {
 162     const ptrdiff_t __len1 = __last1 - __first1;
 163     const ptrdiff_t __len2 = __last2 - __first2;
 164     const int __result = std::memcmp(__first1, __first2, 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    *  "lexigraphically less than" the second, greater than zero if the second
 196    *  range is "lexigraphically less than" the first, and zero otherwise.
 197    *  This is an SGI extension.
 198    *  @ingroup SGIextensions
 199   */
 200   template<typename _InputIterator1, typename _InputIterator2>
 201     int
 202     lexicographical_compare_3way(_InputIterator1 __first1,
 203                                  _InputIterator1 __last1,
 204                                  _InputIterator2 __first2,
 205                                  _InputIterator2 __last2)
 206     {
 207       // concept requirements
 208       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 209       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 210       __glibcxx_function_requires(_LessThanComparableConcept<
 211             typename iterator_traits<_InputIterator1>::value_type>)
 212       __glibcxx_function_requires(_LessThanComparableConcept<
 213             typename iterator_traits<_InputIterator2>::value_type>)
 214       __glibcxx_requires_valid_range(__first1, __last1);
 215       __glibcxx_requires_valid_range(__first2, __last2);
 216
 217       return __lexicographical_compare_3way(__first1, __last1, __first2,
 218                                             __last2);
 219     }
 220
 221   // count and count_if: this version, whose return type is void, was present
 222   // in the HP STL, and is retained as an extension for backward compatibility.
 223   template<typename _InputIterator, typename _Tp, typename _Size>
 224     void
 225     count(_InputIterator __first, _InputIterator __last,
 226           const _Tp& __value,
 227           _Size& __n)
 228     {
 229       // concept requirements
 230       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 231       __glibcxx_function_requires(_EqualityComparableConcept<
 232             typename iterator_traits<_InputIterator>::value_type >)
 233       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
 234       __glibcxx_requires_valid_range(__first, __last);
 235
 236       for ( ; __first != __last; ++__first)
 237         if (*__first == __value)
 238           ++__n;
 239     }
 240
 241   template<typename _InputIterator, typename _Predicate, typename _Size>
 242     void
 243     count_if(_InputIterator __first, _InputIterator __last,
 244              _Predicate __pred,
 245              _Size& __n)
 246     {
 247       // concept requirements
 248       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 249       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 250             typename iterator_traits<_InputIterator>::value_type>)
 251       __glibcxx_requires_valid_range(__first, __last);
 252
 253       for ( ; __first != __last; ++__first)
 254         if (__pred(*__first))
 255           ++__n;
 256     }
 257
 258   // random_sample and random_sample_n (extensions, not part of the standard).
 259
 260   /**
 261    *  This is an SGI extension.
 262    *  @ingroup SGIextensions
 263    *  @doctodo
 264   */
 265   template<typename _ForwardIterator, typename _OutputIterator,
 266            typename _Distance>
 267     _OutputIterator
 268     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 269                     _OutputIterator __out, const _Distance __n)
 270     {
 271       // concept requirements
 272       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 273       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 274                 typename iterator_traits<_ForwardIterator>::value_type>)
 275       __glibcxx_requires_valid_range(__first, __last);
 276
 277       _Distance __remaining = std::distance(__first, __last);
 278       _Distance __m = min(__n, __remaining);
 279
 280       while (__m > 0)
 281         {
 282           if ((std::rand() % __remaining) < __m)
 283             {
 284               *__out = *__first;
 285               ++__out;
 286               --__m;
 287             }
 288           --__remaining;
 289           ++__first;
 290         }
 291       return __out;
 292     }
 293
 294   /**
 295    *  This is an SGI extension.
 296    *  @ingroup SGIextensions
 297    *  @doctodo
 298   */
 299   template<typename _ForwardIterator, typename _OutputIterator,
 300            typename _Distance, typename _RandomNumberGenerator>
 301     _OutputIterator
 302     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 303                    _OutputIterator __out, const _Distance __n,
 304                    _RandomNumberGenerator& __rand)
 305     {
 306       // concept requirements
 307       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 308       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 309                 typename iterator_traits<_ForwardIterator>::value_type>)
 310       __glibcxx_function_requires(_UnaryFunctionConcept<
 311                 _RandomNumberGenerator, _Distance, _Distance>)
 312       __glibcxx_requires_valid_range(__first, __last);
 313
 314       _Distance __remaining = std::distance(__first, __last);
 315       _Distance __m = min(__n, __remaining);
 316
 317       while (__m > 0)
 318         {
 319           if (__rand(__remaining) < __m)
 320             {
 321               *__out = *__first;
 322               ++__out;
 323               --__m;
 324             }
 325           --__remaining;
 326           ++__first;
 327         }
 328       return __out;
 329     }
 330
 331   template<typename _InputIterator, typename _RandomAccessIterator,
 332            typename _Distance>
 333     _RandomAccessIterator
 334     __random_sample(_InputIterator __first, _InputIterator __last,
 335                     _RandomAccessIterator __out,
 336                     const _Distance __n)
 337     {
 338       _Distance __m = 0;
 339       _Distance __t = __n;
 340       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 341         __out[__m] = *__first;
 342
 343       while (__first != __last)
 344         {
 345           ++__t;
 346           _Distance __M = std::rand() % (__t);
 347           if (__M < __n)
 348             __out[__M] = *__first;
 349           ++__first;
 350         }
 351       return __out + __m;
 352     }
 353
 354   template<typename _InputIterator, typename _RandomAccessIterator,
 355            typename _RandomNumberGenerator, typename _Distance>
 356     _RandomAccessIterator
 357     __random_sample(_InputIterator __first, _InputIterator __last,
 358                     _RandomAccessIterator __out,
 359                     _RandomNumberGenerator& __rand,
 360                     const _Distance __n)
 361     {
 362       // concept requirements
 363       __glibcxx_function_requires(_UnaryFunctionConcept<
 364             _RandomNumberGenerator, _Distance, _Distance>)
 365
 366       _Distance __m = 0;
 367       _Distance __t = __n;
 368       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 369         __out[__m] = *__first;
 370
 371       while (__first != __last)
 372         {
 373           ++__t;
 374           _Distance __M = __rand(__t);
 375           if (__M < __n)
 376             __out[__M] = *__first;
 377           ++__first;
 378         }
 379       return __out + __m;
 380     }
 381
 382   /**
 383    *  This is an SGI extension.
 384    *  @ingroup SGIextensions
 385    *  @doctodo
 386   */
 387   template<typename _InputIterator, typename _RandomAccessIterator>
 388     inline _RandomAccessIterator
 389     random_sample(_InputIterator __first, _InputIterator __last,
 390                   _RandomAccessIterator __out_first,
 391                   _RandomAccessIterator __out_last)
 392     {
 393       // concept requirements
 394       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 395       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 396             _RandomAccessIterator>)
 397       __glibcxx_requires_valid_range(__first, __last);
 398       __glibcxx_requires_valid_range(__out_first, __out_last);
 399
 400       return __random_sample(__first, __last,
 401                              __out_first, __out_last - __out_first);
 402     }
 403
 404   /**
 405    *  This is an SGI extension.
 406    *  @ingroup SGIextensions
 407    *  @doctodo
 408   */
 409   template<typename _InputIterator, typename _RandomAccessIterator,
 410            typename _RandomNumberGenerator>
 411     inline _RandomAccessIterator
 412     random_sample(_InputIterator __first, _InputIterator __last,
 413                   _RandomAccessIterator __out_first,
 414                   _RandomAccessIterator __out_last,
 415                   _RandomNumberGenerator& __rand)
 416     {
 417       // concept requirements
 418       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 419       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 420             _RandomAccessIterator>)
 421       __glibcxx_requires_valid_range(__first, __last);
 422       __glibcxx_requires_valid_range(__out_first, __out_last);
 423
 424       return __random_sample(__first, __last,
 425                              __out_first, __rand,
 426                              __out_last - __out_first);
 427     }
 428
 429   /**
 430    *  This is an SGI extension.
 431    *  @ingroup SGIextensions
 432    *  @doctodo
 433   */
 434   template<typename _RandomAccessIterator>
 435     inline bool
 436     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 437     {
 438       // concept requirements
 439       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 440                                   _RandomAccessIterator>)
 441       __glibcxx_function_requires(_LessThanComparableConcept<
 442             typename iterator_traits<_RandomAccessIterator>::value_type>)
 443       __glibcxx_requires_valid_range(__first, __last);
 444
 445       return std::__is_heap(__first, __last - __first);
 446     }
 447
 448   /**
 449    *  This is an SGI extension.
 450    *  @ingroup SGIextensions
 451    *  @doctodo
 452   */
 453   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
 454     inline bool
 455     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 456             _StrictWeakOrdering __comp)
 457     {
 458       // concept requirements
 459       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 460                                   _RandomAccessIterator>)
 461       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 462             typename iterator_traits<_RandomAccessIterator>::value_type,
 463             typename iterator_traits<_RandomAccessIterator>::value_type>)
 464       __glibcxx_requires_valid_range(__first, __last);
 465
 466       return std::__is_heap(__first, __comp, __last - __first);
 467     }
 468
 469   // is_sorted, a predicated testing whether a range is sorted in
 470   // nondescending order.  This is an extension, not part of the C++
 471   // standard.
 472
 473   /**
 474    *  This is an SGI extension.
 475    *  @ingroup SGIextensions
 476    *  @doctodo
 477   */
 478   template<typename _ForwardIterator>
 479     bool
 480     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
 481     {
 482       // concept requirements
 483       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 484       __glibcxx_function_requires(_LessThanComparableConcept<
 485             typename iterator_traits<_ForwardIterator>::value_type>)
 486       __glibcxx_requires_valid_range(__first, __last);
 487
 488       if (__first == __last)
 489         return true;
 490
 491       _ForwardIterator __next = __first;
 492       for (++__next; __next != __last; __first = __next, ++__next)
 493         if (*__next < *__first)
 494           return false;
 495       return true;
 496     }
 497
 498   /**
 499    *  This is an SGI extension.
 500    *  @ingroup SGIextensions
 501    *  @doctodo
 502   */
 503   template<typename _ForwardIterator, typename _StrictWeakOrdering>
 504     bool
 505     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
 506               _StrictWeakOrdering __comp)
 507     {
 508       // concept requirements
 509       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 510       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 511             typename iterator_traits<_ForwardIterator>::value_type,
 512             typename iterator_traits<_ForwardIterator>::value_type>)
 513       __glibcxx_requires_valid_range(__first, __last);
 514
 515       if (__first == __last)
 516         return true;
 517
 518       _ForwardIterator __next = __first;
 519       for (++__next; __next != __last; __first = __next, ++__next)
 520         if (__comp(*__next, *__first))
 521           return false;
 522       return true;
 523     }
 524 } // namespace __gnu_cxx
 525
 526 #endif /* _EXT_ALGORITHM */