mingw/lib/gcc/mingw32/4.3.3/include/c++/ext/algorithm

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