release/src-rt-6.x.4708/toolchains/hndtools-arm-linux-2.6.36-uclibc-4.5.3/arm-brcm-linux-uclibcgnueabi/include/c++/4.5.3/ext/algorithm

   1 // Algorithm extensions -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
   4 // 2009, 2010, 2011
   5 // Free Software Foundation, Inc.
   6 //
   7 // This file is part of the GNU ISO C++ Library.  This library is free
   8 // software; you can redistribute it and/or modify it under the
   9 // terms of the GNU General Public License as published by the
  10 // Free Software Foundation; either version 3, or (at your option)
  11 // any later version.
  12
  13 // This library is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // Under Section 7 of GPL version 3, you are granted additional
  19 // permissions described in the GCC Runtime Library Exception, version
  20 // 3.1, as published by the Free Software Foundation.
  21
  22 // You should have received a copy of the GNU General Public License and
  23 // a copy of the GCC Runtime Library Exception along with this program;
  24 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 // <http://www.gnu.org/licenses/>.
  26
  27 /*
  28  *
  29  * Copyright (c) 1994
  30  * Hewlett-Packard Company
  31  *
  32  * Permission to use, copy, modify, distribute and sell this software
  33  * and its documentation for any purpose is hereby granted without fee,
  34  * provided that the above copyright notice appear in all copies and
  35  * that both that copyright notice and this permission notice appear
  36  * in supporting documentation.  Hewlett-Packard Company makes no
  37  * representations about the suitability of this software for any
  38  * purpose.  It is provided "as is" without express or implied warranty.
  39  *
  40  *
  41  * Copyright (c) 1996
  42  * Silicon Graphics Computer Systems, Inc.
  43  *
  44  * Permission to use, copy, modify, distribute and sell this software
  45  * and its documentation for any purpose is hereby granted without fee,
  46  * provided that the above copyright notice appear in all copies and
  47  * that both that copyright notice and this permission notice appear
  48  * in supporting documentation.  Silicon Graphics makes no
  49  * representations about the suitability of this software for any
  50  * purpose.  It is provided "as is" without express or implied warranty.
  51  */
  52
  53 /** @file ext/algorithm
  54  *  This file is a GNU extension to the Standard C++ Library (possibly
  55  *  containing extensions from the HP/SGI STL subset).
  56  */
  57
  58 #ifndef _EXT_ALGORITHM
  59 #define _EXT_ALGORITHM 1
  60
  61 #pragma GCC system_header
  62
  63 #include <algorithm>
  64
  65 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  66
  67   using std::ptrdiff_t;
  68   using std::min;
  69   using std::pair;
  70   using std::input_iterator_tag;
  71   using std::random_access_iterator_tag;
  72   using std::iterator_traits;
  73
  74   //--------------------------------------------------
  75   // copy_n (not part of the C++ standard)
  76
  77   template<typename _InputIterator, typename _Size, typename _OutputIterator>
  78     pair<_InputIterator, _OutputIterator>
  79     __copy_n(_InputIterator __first, _Size __count,
  80              _OutputIterator __result,
  81              input_iterator_tag)
  82     {
  83       for ( ; __count > 0; --__count)
  84         {
  85           *__result = *__first;
  86           ++__first;
  87           ++__result;
  88         }
  89       return pair<_InputIterator, _OutputIterator>(__first, __result);
  90     }
  91
  92   template<typename _RAIterator, typename _Size, typename _OutputIterator>
  93     inline pair<_RAIterator, _OutputIterator>
  94     __copy_n(_RAIterator __first, _Size __count,
  95              _OutputIterator __result,
  96              random_access_iterator_tag)
  97     {
  98       _RAIterator __last = __first + __count;
  99       return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
 100                                                                   __last,
 101                                                                   __result));
 102     }
 103
 104   /**
 105    *  @brief Copies the range [first,first+count) into [result,result+count).
 106    *  @param  first  An input iterator.
 107    *  @param  count  The number of elements to copy.
 108    *  @param  result An output iterator.
 109    *  @return   A std::pair composed of first+count and result+count.
 110    *
 111    *  This is an SGI extension.
 112    *  This inline function will boil down to a call to @c memmove whenever
 113    *  possible.  Failing that, if random access iterators are passed, then the
 114    *  loop count will be known (and therefore a candidate for compiler
 115    *  optimizations such as unrolling).
 116    *  @ingroup SGIextensions
 117   */
 118   template<typename _InputIterator, typename _Size, typename _OutputIterator>
 119     inline pair<_InputIterator, _OutputIterator>
 120     copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
 121     {
 122       // concept requirements
 123       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 124       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 125             typename iterator_traits<_InputIterator>::value_type>)
 126
 127       return __gnu_cxx::__copy_n(__first, __count, __result,
 128                                  std::__iterator_category(__first));
 129     }
 130
 131   template<typename _InputIterator1, typename _InputIterator2>
 132     int
 133     __lexicographical_compare_3way(_InputIterator1 __first1,
 134                                    _InputIterator1 __last1,
 135                                    _InputIterator2 __first2,
 136                                    _InputIterator2 __last2)
 137     {
 138       while (__first1 != __last1 && __first2 != __last2)
 139         {
 140           if (*__first1 < *__first2)
 141             return -1;
 142           if (*__first2 < *__first1)
 143             return 1;
 144           ++__first1;
 145           ++__first2;
 146         }
 147       if (__first2 == __last2)
 148         return !(__first1 == __last1);
 149       else
 150         return -1;
 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 = __builtin_memcmp(__first1, __first2,
 162                                           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((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    *  <em>lexigraphically less than</em> the second, greater than zero
 194    *  if the second range is <em>lexigraphically less than</em> the
 195    *  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,
 202                                  _InputIterator1 __last1,
 203                                  _InputIterator2 __first2,
 204                                  _InputIterator2 __last2)
 205     {
 206       // concept requirements
 207       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 208       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 209       __glibcxx_function_requires(_LessThanComparableConcept<
 210             typename iterator_traits<_InputIterator1>::value_type>)
 211       __glibcxx_function_requires(_LessThanComparableConcept<
 212             typename iterator_traits<_InputIterator2>::value_type>)
 213       __glibcxx_requires_valid_range(__first1, __last1);
 214       __glibcxx_requires_valid_range(__first2, __last2);
 215
 216       return __lexicographical_compare_3way(__first1, __last1, __first2,
 217                                             __last2);
 218     }
 219
 220   // count and count_if: this version, whose return type is void, was present
 221   // in the HP STL, and is retained as an extension for backward compatibility.
 222   template<typename _InputIterator, typename _Tp, typename _Size>
 223     void
 224     count(_InputIterator __first, _InputIterator __last,
 225           const _Tp& __value,
 226           _Size& __n)
 227     {
 228       // concept requirements
 229       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 230       __glibcxx_function_requires(_EqualityComparableConcept<
 231             typename iterator_traits<_InputIterator>::value_type >)
 232       __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
 233       __glibcxx_requires_valid_range(__first, __last);
 234
 235       for ( ; __first != __last; ++__first)
 236         if (*__first == __value)
 237           ++__n;
 238     }
 239
 240   template<typename _InputIterator, typename _Predicate, typename _Size>
 241     void
 242     count_if(_InputIterator __first, _InputIterator __last,
 243              _Predicate __pred,
 244              _Size& __n)
 245     {
 246       // concept requirements
 247       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 248       __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
 249             typename iterator_traits<_InputIterator>::value_type>)
 250       __glibcxx_requires_valid_range(__first, __last);
 251
 252       for ( ; __first != __last; ++__first)
 253         if (__pred(*__first))
 254           ++__n;
 255     }
 256
 257   // random_sample and random_sample_n (extensions, not part of the standard).
 258
 259   /**
 260    *  This is an SGI extension.
 261    *  @ingroup SGIextensions
 262    *  @doctodo
 263   */
 264   template<typename _ForwardIterator, typename _OutputIterator,
 265            typename _Distance>
 266     _OutputIterator
 267     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 268                     _OutputIterator __out, const _Distance __n)
 269     {
 270       // concept requirements
 271       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 272       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 273                 typename iterator_traits<_ForwardIterator>::value_type>)
 274       __glibcxx_requires_valid_range(__first, __last);
 275
 276       _Distance __remaining = std::distance(__first, __last);
 277       _Distance __m = min(__n, __remaining);
 278
 279       while (__m > 0)
 280         {
 281           if ((std::rand() % __remaining) < __m)
 282             {
 283               *__out = *__first;
 284               ++__out;
 285               --__m;
 286             }
 287           --__remaining;
 288           ++__first;
 289         }
 290       return __out;
 291     }
 292
 293   /**
 294    *  This is an SGI extension.
 295    *  @ingroup SGIextensions
 296    *  @doctodo
 297   */
 298   template<typename _ForwardIterator, typename _OutputIterator,
 299            typename _Distance, typename _RandomNumberGenerator>
 300     _OutputIterator
 301     random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
 302                    _OutputIterator __out, const _Distance __n,
 303                    _RandomNumberGenerator& __rand)
 304     {
 305       // concept requirements
 306       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 307       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 308                 typename iterator_traits<_ForwardIterator>::value_type>)
 309       __glibcxx_function_requires(_UnaryFunctionConcept<
 310                 _RandomNumberGenerator, _Distance, _Distance>)
 311       __glibcxx_requires_valid_range(__first, __last);
 312
 313       _Distance __remaining = std::distance(__first, __last);
 314       _Distance __m = min(__n, __remaining);
 315
 316       while (__m > 0)
 317         {
 318           if (__rand(__remaining) < __m)
 319             {
 320               *__out = *__first;
 321               ++__out;
 322               --__m;
 323             }
 324           --__remaining;
 325           ++__first;
 326         }
 327       return __out;
 328     }
 329
 330   template<typename _InputIterator, typename _RandomAccessIterator,
 331            typename _Distance>
 332     _RandomAccessIterator
 333     __random_sample(_InputIterator __first, _InputIterator __last,
 334                     _RandomAccessIterator __out,
 335                     const _Distance __n)
 336     {
 337       _Distance __m = 0;
 338       _Distance __t = __n;
 339       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 340         __out[__m] = *__first;
 341
 342       while (__first != __last)
 343         {
 344           ++__t;
 345           _Distance __M = std::rand() % (__t);
 346           if (__M < __n)
 347             __out[__M] = *__first;
 348           ++__first;
 349         }
 350       return __out + __m;
 351     }
 352
 353   template<typename _InputIterator, typename _RandomAccessIterator,
 354            typename _RandomNumberGenerator, typename _Distance>
 355     _RandomAccessIterator
 356     __random_sample(_InputIterator __first, _InputIterator __last,
 357                     _RandomAccessIterator __out,
 358                     _RandomNumberGenerator& __rand,
 359                     const _Distance __n)
 360     {
 361       // concept requirements
 362       __glibcxx_function_requires(_UnaryFunctionConcept<
 363             _RandomNumberGenerator, _Distance, _Distance>)
 364
 365       _Distance __m = 0;
 366       _Distance __t = __n;
 367       for ( ; __first != __last && __m < __n; ++__m, ++__first)
 368         __out[__m] = *__first;
 369
 370       while (__first != __last)
 371         {
 372           ++__t;
 373           _Distance __M = __rand(__t);
 374           if (__M < __n)
 375             __out[__M] = *__first;
 376           ++__first;
 377         }
 378       return __out + __m;
 379     }
 380
 381   /**
 382    *  This is an SGI extension.
 383    *  @ingroup SGIextensions
 384    *  @doctodo
 385   */
 386   template<typename _InputIterator, typename _RandomAccessIterator>
 387     inline _RandomAccessIterator
 388     random_sample(_InputIterator __first, _InputIterator __last,
 389                   _RandomAccessIterator __out_first,
 390                   _RandomAccessIterator __out_last)
 391     {
 392       // concept requirements
 393       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 394       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 395             _RandomAccessIterator>)
 396       __glibcxx_requires_valid_range(__first, __last);
 397       __glibcxx_requires_valid_range(__out_first, __out_last);
 398
 399       return __random_sample(__first, __last,
 400                              __out_first, __out_last - __out_first);
 401     }
 402
 403   /**
 404    *  This is an SGI extension.
 405    *  @ingroup SGIextensions
 406    *  @doctodo
 407   */
 408   template<typename _InputIterator, typename _RandomAccessIterator,
 409            typename _RandomNumberGenerator>
 410     inline _RandomAccessIterator
 411     random_sample(_InputIterator __first, _InputIterator __last,
 412                   _RandomAccessIterator __out_first,
 413                   _RandomAccessIterator __out_last,
 414                   _RandomNumberGenerator& __rand)
 415     {
 416       // concept requirements
 417       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 418       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 419             _RandomAccessIterator>)
 420       __glibcxx_requires_valid_range(__first, __last);
 421       __glibcxx_requires_valid_range(__out_first, __out_last);
 422
 423       return __random_sample(__first, __last,
 424                              __out_first, __rand,
 425                              __out_last - __out_first);
 426     }
 427
 428 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 429   using std::is_heap;
 430 #else
 431   /**
 432    *  This is an SGI extension.
 433    *  @ingroup SGIextensions
 434    *  @doctodo
 435   */
 436   template<typename _RandomAccessIterator>
 437     inline bool
 438     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 439     {
 440       // concept requirements
 441       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 442                                   _RandomAccessIterator>)
 443       __glibcxx_function_requires(_LessThanComparableConcept<
 444             typename iterator_traits<_RandomAccessIterator>::value_type>)
 445       __glibcxx_requires_valid_range(__first, __last);
 446
 447       return std::__is_heap(__first, __last - __first);
 448     }
 449
 450   /**
 451    *  This is an SGI extension.
 452    *  @ingroup SGIextensions
 453    *  @doctodo
 454   */
 455   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
 456     inline bool
 457     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 458             _StrictWeakOrdering __comp)
 459     {
 460       // concept requirements
 461       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 462                                   _RandomAccessIterator>)
 463       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 464             typename iterator_traits<_RandomAccessIterator>::value_type,
 465             typename iterator_traits<_RandomAccessIterator>::value_type>)
 466       __glibcxx_requires_valid_range(__first, __last);
 467
 468       return std::__is_heap(__first, __comp, __last - __first);
 469     }
 470 #endif
 471
 472   // is_sorted, a predicated testing whether a range is sorted in
 473   // nondescending order.  This is an extension, not part of the C++
 474   // standard.
 475
 476   /**
 477    *  This is an SGI extension.
 478    *  @ingroup SGIextensions
 479    *  @doctodo
 480   */
 481   template<typename _ForwardIterator>
 482     bool
 483     is_sorted(_ForwardIterator __first, _ForwardIterator __last)
 484     {
 485       // concept requirements
 486       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 487       __glibcxx_function_requires(_LessThanComparableConcept<
 488             typename iterator_traits<_ForwardIterator>::value_type>)
 489       __glibcxx_requires_valid_range(__first, __last);
 490
 491       if (__first == __last)
 492         return true;
 493
 494       _ForwardIterator __next = __first;
 495       for (++__next; __next != __last; __first = __next, ++__next)
 496         if (*__next < *__first)
 497           return false;
 498       return true;
 499     }
 500
 501   /**
 502    *  This is an SGI extension.
 503    *  @ingroup SGIextensions
 504    *  @doctodo
 505   */
 506   template<typename _ForwardIterator, typename _StrictWeakOrdering>
 507     bool
 508     is_sorted(_ForwardIterator __first, _ForwardIterator __last,
 509               _StrictWeakOrdering __comp)
 510     {
 511       // concept requirements
 512       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
 513       __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
 514             typename iterator_traits<_ForwardIterator>::value_type,
 515             typename iterator_traits<_ForwardIterator>::value_type>)
 516       __glibcxx_requires_valid_range(__first, __last);
 517
 518       if (__first == __last)
 519         return true;
 520
 521       _ForwardIterator __next = __first;
 522       for (++__next; __next != __last; __first = __next, ++__next)
 523         if (__comp(*__next, *__first))
 524           return false;
 525       return true;
 526     }
 527
 528   /**
 529    *  @brief Find the median of three values.
 530    *  @param  a  A value.
 531    *  @param  b  A value.
 532    *  @param  c  A value.
 533    *  @return One of @p a, @p b or @p c.
 534    *
 535    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
 536    *  then the value returned will be @c m.
 537    *  This is an SGI extension.
 538    *  @ingroup SGIextensions
 539   */
 540   template<typename _Tp>
 541     const _Tp&
 542     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
 543     {
 544       // concept requirements
 545       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 546       if (__a < __b)
 547         if (__b < __c)
 548           return __b;
 549         else if (__a < __c)
 550           return __c;
 551         else
 552           return __a;
 553       else if (__a < __c)
 554         return __a;
 555       else if (__b < __c)
 556         return __c;
 557       else
 558         return __b;
 559     }
 560
 561   /**
 562    *  @brief Find the median of three values using a predicate for comparison.
 563    *  @param  a     A value.
 564    *  @param  b     A value.
 565    *  @param  c     A value.
 566    *  @param  comp  A binary predicate.
 567    *  @return One of @p a, @p b or @p c.
 568    *
 569    *  If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
 570    *  and @p comp(m,n) are both true then the value returned will be @c m.
 571    *  This is an SGI extension.
 572    *  @ingroup SGIextensions
 573   */
 574   template<typename _Tp, typename _Compare>
 575     const _Tp&
 576     __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
 577     {
 578       // concept requirements
 579       __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
 580                                                          _Tp, _Tp>)
 581       if (__comp(__a, __b))
 582         if (__comp(__b, __c))
 583           return __b;
 584         else if (__comp(__a, __c))
 585           return __c;
 586         else
 587           return __a;
 588       else if (__comp(__a, __c))
 589         return __a;
 590       else if (__comp(__b, __c))
 591         return __c;
 592       else
 593         return __b;
 594     }
 595
 596 _GLIBCXX_END_NAMESPACE
 597
 598 #endif /* _EXT_ALGORITHM */