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

   1 // Algorithm extensions -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  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).  You should only
  59  *  include this header if you are using GCC 3 or later.
  60  */
  61
  62 #ifndef _EXT_ALGORITHM
  63 #define _EXT_ALGORITHM 1
  64
  65 #pragma GCC system_header
  66
  67 #include <algorithm>
  68
  69 namespace __gnu_cxx
  70 {
  71   using std::ptrdiff_t;
  72   using std::min;
  73   using std::pair;
  74   using std::input_iterator_tag;
  75   using std::random_access_iterator_tag;
  76   using std::iterator_traits;
  77
  78   //--------------------------------------------------
  79   // copy_n (not part of the C++ standard)
  80
  81   template<typename _InputIterator, typename _Size, typename _OutputIterator>
  82     pair<_InputIterator, _OutputIterator>
  83     __copy_n(_InputIterator __first, _Size __count,
  84              _OutputIterator __result,
  85              input_iterator_tag)
  86     {
  87       for ( ; __count > 0; --__count) {
  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,
 103                                         std::copy(__first, __last, __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 __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, _InputIterator1 __last1,
 136                                    _InputIterator2 __first2, _InputIterator2 __last2)
 137     {
 138       while (__first1 != __last1 && __first2 != __last2) {
 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       }
 149       else {
 150         return -1;
 151       }
 152     }
 153
 154   inline int
 155   __lexicographical_compare_3way(const unsigned char* __first1,
 156                                  const unsigned char* __last1,
 157                                  const unsigned char* __first2,
 158                                  const unsigned char* __last2)
 159   {
 160     const ptrdiff_t __len1 = __last1 - __first1;
 161     const ptrdiff_t __len2 = __last2 - __first2;
 162     const int __result = std::memcmp(__first1, __first2, 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(
 173                                   (const signed char*) __first1,
 174                                   (const signed char*) __last1,
 175                                   (const signed char*) __first2,
 176                                   (const signed char*) __last2);
 177 #else
 178     return __lexicographical_compare_3way((const unsigned char*) __first1,
 179                                           (const unsigned char*) __last1,
 180                                           (const unsigned char*) __first2,
 181                                           (const unsigned char*) __last2);
 182 #endif
 183   }
 184
 185   /**
 186    *  @brief @c memcmp on steroids.
 187    *  @param  first1  An input iterator.
 188    *  @param  last1   An input iterator.
 189    *  @param  first2  An input iterator.
 190    *  @param  last2   An input iterator.
 191    *  @return   An int, as with @c memcmp.
 192    *
 193    *  The return value will be less than zero if the first range is
 194    *  "lexigraphically less than" the second, greater than zero if the second
 195    *  range is "lexigraphically less than" the 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, _InputIterator1 __last1,
 202                                  _InputIterator2 __first2, _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, __last2);
 215     }
 216
 217   // count and count_if: this version, whose return type is void, was present
 218   // in the HP STL, and is retained as an extension for backward compatibility.
 219
 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, typename _Distance>
 263     _OutputIterator
 264     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 265                     _OutputIterator __out, const _Distance __n)
 266     {
 267       // concept requirements
 268       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 269       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 270                 typename iterator_traits<_ForwardIterator>::value_type>)
 271       __glibcxx_requires_valid_range(__first, __last);
 272
 273       _Distance __remaining = std::distance(__first, __last);
 274       _Distance __m = min(__n, __remaining);
 275
 276       while (__m > 0) {
 277         if ((std::rand() % __remaining) < __m) {
 278               *__out = *__first;
 279               ++__out;
 280               --__m;
 281         }
 282
 283         --__remaining;
 284         ++__first;
 285       }
 286       return __out;
 287     }
 288
 289   /**
 290    *  This is an SGI extension.
 291    *  @ingroup SGIextensions
 292    *  @doctodo
 293   */
 294   template<typename _ForwardIterator, typename _OutputIterator, typename _Distance,
 295            typename _RandomNumberGenerator>
 296     _OutputIterator
 297     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 298                    _OutputIterator __out, const _Distance __n,
 299                    _RandomNumberGenerator& __rand)
 300     {
 301       // concept requirements
 302       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 303       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 304                 typename iterator_traits<_ForwardIterator>::value_type>)
 305       __glibcxx_function_requires(_UnaryFunctionConcept<
 306                 _RandomNumberGenerator, _Distance, _Distance>)
 307       __glibcxx_requires_valid_range(__first, __last);
 308
 309       _Distance __remaining = std::distance(__first, __last);
 310       _Distance __m = min(__n, __remaining);
 311
 312       while (__m > 0) {
 313         if (__rand(__remaining) < __m) {
 314               *__out = *__first;
 315               ++__out;
 316               --__m;
 317         }
 318
 319         --__remaining;
 320         ++__first;
 321       }
 322       return __out;
 323     }
 324
 325   template<typename _InputIterator, typename _RandomAccessIterator, typename _Distance>
 326     _RandomAccessIterator
 327     __random_sample(_InputIterator __first, _InputIterator __last,
 328                     _RandomAccessIterator __out,
 329                     const _Distance __n)
 330     {
 331       _Distance __m = 0;
 332       _Distance __t = __n;
 333       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 334         __out[__m] = *__first;
 335
 336       while (__first != __last) {
 337         ++__t;
 338         _Distance __M = std::rand() % (__t);
 339         if (__M < __n)
 340           __out[__M] = *__first;
 341         ++__first;
 342       }
 343
 344       return __out + __m;
 345     }
 346
 347   template<typename _InputIterator, typename _RandomAccessIterator,
 348            typename _RandomNumberGenerator, typename _Distance>
 349     _RandomAccessIterator
 350     __random_sample(_InputIterator __first, _InputIterator __last,
 351                     _RandomAccessIterator __out,
 352                     _RandomNumberGenerator& __rand,
 353                     const _Distance __n)
 354     {
 355       // concept requirements
 356       __glibcxx_function_requires(_UnaryFunctionConcept<
 357             _RandomNumberGenerator, _Distance, _Distance>)
 358
 359       _Distance __m = 0;
 360       _Distance __t = __n;
 361       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 362         __out[__m] = *__first;
 363
 364       while (__first != __last) {
 365         ++__t;
 366         _Distance __M = __rand(__t);
 367         if (__M < __n)
 368           __out[__M] = *__first;
 369         ++__first;
 370       }
 371
 372       return __out + __m;
 373     }
 374
 375   /**
 376    *  This is an SGI extension.
 377    *  @ingroup SGIextensions
 378    *  @doctodo
 379   */
 380   template<typename _InputIterator, typename _RandomAccessIterator>
 381     inline _RandomAccessIterator
 382     random_sample(_InputIterator __first, _InputIterator __last,
 383                   _RandomAccessIterator __out_first, _RandomAccessIterator __out_last)
 384     {
 385       // concept requirements
 386       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 387       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 388             _RandomAccessIterator>)
 389       __glibcxx_requires_valid_range(__first, __last);
 390       __glibcxx_requires_valid_range(__out_first, __out_last);
 391
 392       return __random_sample(__first, __last,
 393                              __out_first, __out_last - __out_first);
 394     }
 395
 396   /**
 397    *  This is an SGI extension.
 398    *  @ingroup SGIextensions
 399    *  @doctodo
 400   */
 401   template<typename _InputIterator, typename _RandomAccessIterator,
 402            typename _RandomNumberGenerator>
 403     inline _RandomAccessIterator
 404     random_sample(_InputIterator __first, _InputIterator __last,
 405                   _RandomAccessIterator __out_first, _RandomAccessIterator __out_last,
 406                   _RandomNumberGenerator& __rand)
 407     {
 408       // concept requirements
 409       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 410       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 411             _RandomAccessIterator>)
 412       __glibcxx_requires_valid_range(__first, __last);
 413       __glibcxx_requires_valid_range(__out_first, __out_last);
 414
 415       return __random_sample(__first, __last,
 416                              __out_first, __rand,
 417                              __out_last - __out_first);
 418     }
 419
 420   /**
 421    *  This is an SGI extension.
 422    *  @ingroup SGIextensions
 423    *  @doctodo
 424   */
 425   template<typename _RandomAccessIterator>
 426     inline bool
 427     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 428     {
 429       // concept requirements
 430       __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
 431       __glibcxx_function_requires(_LessThanComparableConcept<
 432             typename iterator_traits<_RandomAccessIterator>::value_type>)
 433       __glibcxx_requires_valid_range(__first, __last);
 434
 435       return std::__is_heap(__first, __last - __first);
 436     }
 437
 438   /**
 439    *  This is an SGI extension.
 440    *  @ingroup SGIextensions
 441    *  @doctodo
 442   */
 443   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
 444     inline bool
 445     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 446             _StrictWeakOrdering __comp)
 447     {
 448       // concept requirements
 449       __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>)
 450       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 451             typename iterator_traits<_RandomAccessIterator>::value_type,
 452             typename iterator_traits<_RandomAccessIterator>::value_type>)
 453       __glibcxx_requires_valid_range(__first, __last);
 454
 455       return std::__is_heap(__first, __comp, __last - __first);
 456     }
 457
 458   // is_sorted, a predicated testing whether a range is sorted in
 459   // nondescending order.  This is an extension, not part of the C++
 460   // standard.
 461
 462   /**
 463    *  This is an SGI extension.
 464    *  @ingroup SGIextensions
 465    *  @doctodo
 466   */
 467   template<typename _ForwardIterator>
 468     bool
 469     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
 470     {
 471       // concept requirements
 472       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 473       __glibcxx_function_requires(_LessThanComparableConcept<
 474             typename iterator_traits<_ForwardIterator>::value_type>)
 475       __glibcxx_requires_valid_range(__first, __last);
 476
 477       if (__first == __last)
 478         return true;
 479
 480       _ForwardIterator __next = __first;
 481       for (++__next; __next != __last; __first = __next, ++__next) {
 482         if (*__next < *__first)
 483           return false;
 484       }
 485
 486       return true;
 487     }
 488
 489   /**
 490    *  This is an SGI extension.
 491    *  @ingroup SGIextensions
 492    *  @doctodo
 493   */
 494   template<typename _ForwardIterator, typename _StrictWeakOrdering>
 495     bool
 496     is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp)
 497     {
 498       // concept requirements
 499       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 500       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 501             typename iterator_traits<_ForwardIterator>::value_type,
 502             typename iterator_traits<_ForwardIterator>::value_type>)
 503       __glibcxx_requires_valid_range(__first, __last);
 504
 505       if (__first == __last)
 506         return true;
 507
 508       _ForwardIterator __next = __first;
 509       for (++__next; __next != __last; __first = __next, ++__next) {
 510         if (__comp(*__next, *__first))
 511           return false;
 512       }
 513
 514       return true;
 515     }
 516 } // namespace __gnu_cxx
 517
 518 #endif /* _EXT_ALGORITHM */