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
  64
  65 #pragma GCC system_header
  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 _InputIter, typename _Size, typename _OutputIter>
  81     pair<_InputIter, _OutputIter>
  82     __copy_n(_InputIter __first, _Size __count,
  83              _OutputIter __result,
  84              input_iterator_tag)
  85     {
  86       for ( ; __count > 0; --__count) {
  87         *__result = *__first;
  88         ++__first;
  89         ++__result;
  90       }
  91       return pair<_InputIter, _OutputIter>(__first, __result);
  92     }
  93
  94   template<typename _RAIter, typename _Size, typename _OutputIter>
  95     inline pair<_RAIter, _OutputIter>
  96     __copy_n(_RAIter __first, _Size __count,
  97              _OutputIter __result,
  98              random_access_iterator_tag)
  99     {
 100       _RAIter __last = __first + __count;
 101       return pair<_RAIter, _OutputIter>(__last,
 102                                         std::copy(__first, __last, __result));
 103     }
 104
 105   /**
 106    *  @brief Copies the range [first,first+count) into [result,result+count).
 107    *  @param  first  An input iterator.
 108    *  @param  count  The number of elements to copy.
 109    *  @param  result An output iterator.
 110    *  @return   A std::pair composed of first+count and result+count.
 111    *
 112    *  This is an SGI extension.
 113    *  This inline function will boil down to a call to @c memmove whenever
 114    *  possible.  Failing that, if random access iterators are passed, then the
 115    *  loop count will be known (and therefore a candidate for compiler
 116    *  optimizations such as unrolling).
 117    *  @ingroup SGIextensions
 118   */
 119   template<typename _InputIter, typename _Size, typename _OutputIter>
 120     inline pair<_InputIter, _OutputIter>
 121     copy_n(_InputIter __first, _Size __count, _OutputIter __result)
 122     {
 123       // concept requirements
 124       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 125       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 126             typename iterator_traits<_InputIter>::value_type>)
 127
 128       return __copy_n(__first, __count, __result,
 129                       std::__iterator_category(__first));
 130     }
 131
 132   template<typename _InputIter1, typename _InputIter2>
 133     int
 134     __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 135                                    _InputIter2 __first2, _InputIter2 __last2)
 136     {
 137       while (__first1 != __last1 && __first2 != __last2) {
 138         if (*__first1 < *__first2)
 139           return -1;
 140         if (*__first2 < *__first1)
 141           return 1;
 142         ++__first1;
 143         ++__first2;
 144       }
 145       if (__first2 == __last2) {
 146         return !(__first1 == __last1);
 147       }
 148       else {
 149         return -1;
 150       }
 151     }
 152
 153   inline int
 154   __lexicographical_compare_3way(const unsigned char* __first1,
 155                                  const unsigned char* __last1,
 156                                  const unsigned char* __first2,
 157                                  const unsigned char* __last2)
 158   {
 159     const ptrdiff_t __len1 = __last1 - __first1;
 160     const ptrdiff_t __len2 = __last2 - __first2;
 161     const int __result = std::memcmp(__first1, __first2, 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(
 172                                   (const signed char*) __first1,
 173                                   (const signed char*) __last1,
 174                                   (const signed char*) __first2,
 175                                   (const signed char*) __last2);
 176 #else
 177     return __lexicographical_compare_3way((const unsigned char*) __first1,
 178                                           (const unsigned char*) __last1,
 179                                           (const unsigned char*) __first2,
 180                                           (const unsigned char*) __last2);
 181 #endif
 182   }
 183
 184   /**
 185    *  @brief @c memcmp on steroids.
 186    *  @param  first1  An input iterator.
 187    *  @param  last1   An input iterator.
 188    *  @param  first2  An input iterator.
 189    *  @param  last2   An input iterator.
 190    *  @return   An int, as with @c memcmp.
 191    *
 192    *  The return value will be less than zero if the first range is
 193    *  "lexigraphically less than" the second, greater than zero if the second
 194    *  range is "lexigraphically less than" the first, and zero otherwise.
 195    *  This is an SGI extension.
 196    *  @ingroup SGIextensions
 197   */
 198   template<typename _InputIter1, typename _InputIter2>
 199     int
 200     lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 201                                  _InputIter2 __first2, _InputIter2 __last2)
 202     {
 203       // concept requirements
 204       __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
 205       __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
 206       __glibcpp_function_requires(_LessThanComparableConcept<
 207             typename iterator_traits<_InputIter1>::value_type>)
 208       __glibcpp_function_requires(_LessThanComparableConcept<
 209             typename iterator_traits<_InputIter2>::value_type>)
 210
 211       return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
 212     }
 213
 214   // count and count_if: this version, whose return type is void, was present
 215   // in the HP STL, and is retained as an extension for backward compatibility.
 216
 217   template<typename _InputIter, typename _Tp, typename _Size>
 218     void
 219     count(_InputIter __first, _InputIter __last,
 220           const _Tp& __value,
 221           _Size& __n)
 222     {
 223       // concept requirements
 224       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 225       __glibcpp_function_requires(_EqualityComparableConcept<
 226             typename iterator_traits<_InputIter>::value_type >)
 227       __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)
 228       for ( ; __first != __last; ++__first)
 229         if (*__first == __value)
 230           ++__n;
 231     }
 232
 233   template<typename _InputIter, typename _Predicate, typename _Size>
 234     void
 235     count_if(_InputIter __first, _InputIter __last,
 236              _Predicate __pred,
 237              _Size& __n)
 238     {
 239       // concept requirements
 240       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 241       __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
 242             typename iterator_traits<_InputIter>::value_type>)
 243       for ( ; __first != __last; ++__first)
 244         if (__pred(*__first))
 245           ++__n;
 246     }
 247
 248   // random_sample and random_sample_n (extensions, not part of the standard).
 249
 250   /**
 251    *  This is an SGI extension.
 252    *  @ingroup SGIextensions
 253    *  @doctodo
 254   */
 255   template<typename _ForwardIter, typename _OutputIter, typename _Distance>
 256     _OutputIter
 257     random_sample_n(_ForwardIter __first, _ForwardIter __last,
 258                     _OutputIter __out, const _Distance __n)
 259     {
 260       // concept requirements
 261       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 262       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 263                 typename iterator_traits<_ForwardIter>::value_type>)
 264
 265       _Distance __remaining = std::distance(__first, __last);
 266       _Distance __m = min(__n, __remaining);
 267
 268       while (__m > 0) {
 269         if (std::__random_number(__remaining) < __m) {
 270               *__out = *__first;
 271               ++__out;
 272               --__m;
 273         }
 274
 275         --__remaining;
 276         ++__first;
 277       }
 278       return __out;
 279     }
 280
 281   /**
 282    *  This is an SGI extension.
 283    *  @ingroup SGIextensions
 284    *  @doctodo
 285   */
 286   template<typename _ForwardIter, typename _OutputIter, typename _Distance,
 287            typename _RandomNumberGenerator>
 288     _OutputIter
 289     random_sample_n(_ForwardIter __first, _ForwardIter __last,
 290                    _OutputIter __out, const _Distance __n,
 291                    _RandomNumberGenerator& __rand)
 292     {
 293       // concept requirements
 294       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 295       __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
 296                 typename iterator_traits<_ForwardIter>::value_type>)
 297       __glibcpp_function_requires(_UnaryFunctionConcept<
 298                 _RandomNumberGenerator, _Distance, _Distance>)
 299
 300       _Distance __remaining = std::distance(__first, __last);
 301       _Distance __m = min(__n, __remaining);
 302
 303       while (__m > 0) {
 304         if (__rand(__remaining) < __m) {
 305               *__out = *__first;
 306               ++__out;
 307               --__m;
 308         }
 309
 310         --__remaining;
 311         ++__first;
 312       }
 313       return __out;
 314     }
 315
 316   template<typename _InputIter, typename _RandomAccessIter, typename _Distance>
 317     _RandomAccessIter
 318     __random_sample(_InputIter __first, _InputIter __last,
 319                     _RandomAccessIter __out,
 320                     const _Distance __n)
 321     {
 322       _Distance __m = 0;
 323       _Distance __t = __n;
 324       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 325         __out[__m] = *__first;
 326
 327       while (__first != __last) {
 328         ++__t;
 329         _Distance __M = std::__random_number(__t);
 330         if (__M < __n)
 331           __out[__M] = *__first;
 332         ++__first;
 333       }
 334
 335       return __out + __m;
 336     }
 337
 338   template<typename _InputIter, typename _RandomAccessIter,
 339            typename _RandomNumberGenerator, typename _Distance>
 340     _RandomAccessIter
 341     __random_sample(_InputIter __first, _InputIter __last,
 342                     _RandomAccessIter __out,
 343                     _RandomNumberGenerator& __rand,
 344                     const _Distance __n)
 345     {
 346       // concept requirements
 347       __glibcpp_function_requires(_UnaryFunctionConcept<
 348             _RandomNumberGenerator, _Distance, _Distance>)
 349
 350       _Distance __m = 0;
 351       _Distance __t = __n;
 352       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 353         __out[__m] = *__first;
 354
 355       while (__first != __last) {
 356         ++__t;
 357         _Distance __M = __rand(__t);
 358         if (__M < __n)
 359           __out[__M] = *__first;
 360         ++__first;
 361       }
 362
 363       return __out + __m;
 364     }
 365
 366   /**
 367    *  This is an SGI extension.
 368    *  @ingroup SGIextensions
 369    *  @doctodo
 370   */
 371   template<typename _InputIter, typename _RandomAccessIter>
 372     inline _RandomAccessIter
 373     random_sample(_InputIter __first, _InputIter __last,
 374                   _RandomAccessIter __out_first, _RandomAccessIter __out_last)
 375     {
 376       // concept requirements
 377       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 378       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 379             _RandomAccessIter>)
 380
 381       return __random_sample(__first, __last,
 382                              __out_first, __out_last - __out_first);
 383     }
 384
 385   /**
 386    *  This is an SGI extension.
 387    *  @ingroup SGIextensions
 388    *  @doctodo
 389   */
 390   template<typename _InputIter, typename _RandomAccessIter,
 391            typename _RandomNumberGenerator>
 392     inline _RandomAccessIter
 393     random_sample(_InputIter __first, _InputIter __last,
 394                   _RandomAccessIter __out_first, _RandomAccessIter __out_last,
 395                   _RandomNumberGenerator& __rand)
 396     {
 397       // concept requirements
 398       __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
 399       __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 400             _RandomAccessIter>)
 401
 402       return __random_sample(__first, __last,
 403                              __out_first, __rand,
 404                              __out_last - __out_first);
 405     }
 406
 407   // is_heap, a predicate testing whether or not a range is
 408   // a heap.  This function is an extension, not part of the C++
 409   // standard.
 410
 411   template<typename _RandomAccessIter, typename _Distance>
 412     bool
 413     __is_heap(_RandomAccessIter __first, _Distance __n)
 414     {
 415       _Distance __parent = 0;
 416       for (_Distance __child = 1; __child < __n; ++__child) {
 417         if (__first[__parent] < __first[__child])
 418           return false;
 419         if ((__child & 1) == 0)
 420           ++__parent;
 421       }
 422       return true;
 423     }
 424
 425   template<typename _RandomAccessIter, typename _Distance,
 426            typename _StrictWeakOrdering>
 427     bool
 428     __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
 429               _Distance __n)
 430     {
 431       _Distance __parent = 0;
 432       for (_Distance __child = 1; __child < __n; ++__child) {
 433         if (__comp(__first[__parent], __first[__child]))
 434           return false;
 435         if ((__child & 1) == 0)
 436           ++__parent;
 437       }
 438       return true;
 439     }
 440
 441   /**
 442    *  This is an SGI extension.
 443    *  @ingroup SGIextensions
 444    *  @doctodo
 445   */
 446   template<typename _RandomAccessIter>
 447     inline bool
 448     is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
 449     {
 450       // concept requirements
 451       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
 452       __glibcpp_function_requires(_LessThanComparableConcept<
 453             typename iterator_traits<_RandomAccessIter>::value_type>)
 454
 455       return __is_heap(__first, __last - __first);
 456     }
 457
 458   /**
 459    *  This is an SGI extension.
 460    *  @ingroup SGIextensions
 461    *  @doctodo
 462   */
 463   template<typename _RandomAccessIter, typename _StrictWeakOrdering>
 464     inline bool
 465     is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
 466             _StrictWeakOrdering __comp)
 467     {
 468       // concept requirements
 469       __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>)
 470       __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 471             typename iterator_traits<_RandomAccessIter>::value_type,
 472             typename iterator_traits<_RandomAccessIter>::value_type>)
 473
 474       return __is_heap(__first, __comp, __last - __first);
 475     }
 476
 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 _ForwardIter>
 487     bool
 488     is_sorted(_ForwardIter __first, _ForwardIter __last)
 489     {
 490       // concept requirements
 491       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 492       __glibcpp_function_requires(_LessThanComparableConcept<
 493             typename iterator_traits<_ForwardIter>::value_type>)
 494
 495       if (__first == __last)
 496         return true;
 497
 498       _ForwardIter __next = __first;
 499       for (++__next; __next != __last; __first = __next, ++__next) {
 500         if (*__next < *__first)
 501           return false;
 502       }
 503
 504       return true;
 505     }
 506
 507   /**
 508    *  This is an SGI extension.
 509    *  @ingroup SGIextensions
 510    *  @doctodo
 511   */
 512   template<typename _ForwardIter, typename _StrictWeakOrdering>
 513     bool
 514     is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
 515     {
 516       // concept requirements
 517       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
 518       __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 519             typename iterator_traits<_ForwardIter>::value_type,
 520             typename iterator_traits<_ForwardIter>::value_type>)
 521
 522       if (__first == __last)
 523         return true;
 524
 525       _ForwardIter __next = __first;
 526       for (++__next; __next != __last; __first = __next, ++__next) {
 527         if (__comp(*__next, *__first))
 528           return false;
 529       }
 530
 531       return true;
 532     }
 533
 534 } // namespace __gnu_cxx
 535
 536 #endif /* _EXT_ALGORITHM */