l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/bits/stl_algobase.h

   1 // Core algorithmic facilities -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
   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-1998
  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 stl_algobase.h
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _STL_ALGOBASE_H
  63 #define _STL_ALGOBASE_H 1
  64
  65 #include <bits/c++config.h>
  66 #include <cstddef>
  67 #include <bits/functexcept.h>
  68 #include <bits/cpp_type_traits.h>
  69 #include <ext/type_traits.h>
  70 #include <ext/numeric_traits.h>
  71 #include <bits/stl_pair.h>
  72 #include <bits/stl_iterator_base_types.h>
  73 #include <bits/stl_iterator_base_funcs.h>
  74 #include <bits/stl_iterator.h>
  75 #include <bits/concept_check.h>
  76 #include <debug/debug.h>
  77 #include <bits/stl_move.h> // For std::swap and _GLIBCXX_MOVE
  78
  79 _GLIBCXX_BEGIN_NAMESPACE(std)
  80
  81   // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
  82   // nutshell, we are partially implementing the resolution of DR 187,
  83   // when it's safe, i.e., the value_types are equal.
  84   template<bool _BoolType>
  85     struct __iter_swap
  86     {
  87       template<typename _ForwardIterator1, typename _ForwardIterator2>
  88         static void
  89         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
  90         {
  91           typedef typename iterator_traits<_ForwardIterator1>::value_type
  92             _ValueType1;
  93           _ValueType1 __tmp = _GLIBCXX_MOVE(*__a);
  94           *__a = _GLIBCXX_MOVE(*__b);
  95           *__b = _GLIBCXX_MOVE(__tmp);
  96         }
  97     };
  98
  99   template<>
 100     struct __iter_swap<true>
 101     {
 102       template<typename _ForwardIterator1, typename _ForwardIterator2>
 103         static void
 104         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
 105         {
 106           swap(*__a, *__b);
 107         }
 108     };
 109
 110   /**
 111    *  @brief Swaps the contents of two iterators.
 112    *  @param  a  An iterator.
 113    *  @param  b  Another iterator.
 114    *  @return   Nothing.
 115    *
 116    *  This function swaps the values pointed to by two iterators, not the
 117    *  iterators themselves.
 118   */
 119   template<typename _ForwardIterator1, typename _ForwardIterator2>
 120     inline void
 121     iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
 122     {
 123       typedef typename iterator_traits<_ForwardIterator1>::value_type
 124         _ValueType1;
 125       typedef typename iterator_traits<_ForwardIterator2>::value_type
 126         _ValueType2;
 127
 128       // concept requirements
 129       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 130                                   _ForwardIterator1>)
 131       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 132                                   _ForwardIterator2>)
 133       __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
 134                                   _ValueType2>)
 135       __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
 136                                   _ValueType1>)
 137
 138       typedef typename iterator_traits<_ForwardIterator1>::reference
 139         _ReferenceType1;
 140       typedef typename iterator_traits<_ForwardIterator2>::reference
 141         _ReferenceType2;
 142       std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
 143         && __are_same<_ValueType1&, _ReferenceType1>::__value
 144         && __are_same<_ValueType2&, _ReferenceType2>::__value>::
 145         iter_swap(__a, __b);
 146     }
 147
 148   /**
 149    *  @brief Swap the elements of two sequences.
 150    *  @param  first1  A forward iterator.
 151    *  @param  last1   A forward iterator.
 152    *  @param  first2  A forward iterator.
 153    *  @return   An iterator equal to @p first2+(last1-first1).
 154    *
 155    *  Swaps each element in the range @p [first1,last1) with the
 156    *  corresponding element in the range @p [first2,(last1-first1)).
 157    *  The ranges must not overlap.
 158   */
 159   template<typename _ForwardIterator1, typename _ForwardIterator2>
 160     _ForwardIterator2
 161     swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 162                 _ForwardIterator2 __first2)
 163     {
 164       // concept requirements
 165       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 166                                   _ForwardIterator1>)
 167       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 168                                   _ForwardIterator2>)
 169       __glibcxx_requires_valid_range(__first1, __last1);
 170
 171       for (; __first1 != __last1; ++__first1, ++__first2)
 172         std::iter_swap(__first1, __first2);
 173       return __first2;
 174     }
 175
 176   /**
 177    *  @brief This does what you think it does.
 178    *  @param  a  A thing of arbitrary type.
 179    *  @param  b  Another thing of arbitrary type.
 180    *  @return   The lesser of the parameters.
 181    *
 182    *  This is the simple classic generic implementation.  It will work on
 183    *  temporary expressions, since they are only evaluated once, unlike a
 184    *  preprocessor macro.
 185   */
 186   template<typename _Tp>
 187     inline const _Tp&
 188     min(const _Tp& __a, const _Tp& __b)
 189     {
 190       // concept requirements
 191       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 192       //return __b < __a ? __b : __a;
 193       if (__b < __a)
 194         return __b;
 195       return __a;
 196     }
 197
 198   /**
 199    *  @brief This does what you think it does.
 200    *  @param  a  A thing of arbitrary type.
 201    *  @param  b  Another thing of arbitrary type.
 202    *  @return   The greater of the parameters.
 203    *
 204    *  This is the simple classic generic implementation.  It will work on
 205    *  temporary expressions, since they are only evaluated once, unlike a
 206    *  preprocessor macro.
 207   */
 208   template<typename _Tp>
 209     inline const _Tp&
 210     max(const _Tp& __a, const _Tp& __b)
 211     {
 212       // concept requirements
 213       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 214       //return  __a < __b ? __b : __a;
 215       if (__a < __b)
 216         return __b;
 217       return __a;
 218     }
 219
 220   /**
 221    *  @brief This does what you think it does.
 222    *  @param  a  A thing of arbitrary type.
 223    *  @param  b  Another thing of arbitrary type.
 224    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
 225    *  @return   The lesser of the parameters.
 226    *
 227    *  This will work on temporary expressions, since they are only evaluated
 228    *  once, unlike a preprocessor macro.
 229   */
 230   template<typename _Tp, typename _Compare>
 231     inline const _Tp&
 232     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
 233     {
 234       //return __comp(__b, __a) ? __b : __a;
 235       if (__comp(__b, __a))
 236         return __b;
 237       return __a;
 238     }
 239
 240   /**
 241    *  @brief This does what you think it does.
 242    *  @param  a  A thing of arbitrary type.
 243    *  @param  b  Another thing of arbitrary type.
 244    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
 245    *  @return   The greater of the parameters.
 246    *
 247    *  This will work on temporary expressions, since they are only evaluated
 248    *  once, unlike a preprocessor macro.
 249   */
 250   template<typename _Tp, typename _Compare>
 251     inline const _Tp&
 252     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
 253     {
 254       //return __comp(__a, __b) ? __b : __a;
 255       if (__comp(__a, __b))
 256         return __b;
 257       return __a;
 258     }
 259
 260
 261   // If _Iterator is a __normal_iterator return its base (a plain pointer,
 262   // normally) otherwise return it untouched.  See copy, fill, ...
 263   template<typename _Iterator,
 264            bool _IsNormal = __is_normal_iterator<_Iterator>::__value>
 265     struct __niter_base
 266     {
 267       static _Iterator
 268       __b(_Iterator __it)
 269       { return __it; }
 270     };
 271
 272   template<typename _Iterator>
 273     struct __niter_base<_Iterator, true>
 274     {
 275       static typename _Iterator::iterator_type
 276       __b(_Iterator __it)
 277       { return __it.base(); }
 278     };
 279
 280   // Likewise, for move_iterator.
 281   template<typename _Iterator,
 282            bool _IsMove = __is_move_iterator<_Iterator>::__value>
 283     struct __miter_base
 284     {
 285       static _Iterator
 286       __b(_Iterator __it)
 287       { return __it; }
 288     };
 289
 290   template<typename _Iterator>
 291     struct __miter_base<_Iterator, true>
 292     {
 293       static typename _Iterator::iterator_type
 294       __b(_Iterator __it)
 295       { return __it.base(); }
 296     };
 297
 298   // All of these auxiliary structs serve two purposes.  (1) Replace
 299   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
 300   // because the input and output ranges are permitted to overlap.)
 301   // (2) If we're using random access iterators, then write the loop as
 302   // a for loop with an explicit count.
 303
 304   template<bool, bool, typename>
 305     struct __copy_move
 306     {
 307       template<typename _II, typename _OI>
 308         static _OI
 309         __copy_m(_II __first, _II __last, _OI __result)
 310         {
 311           for (; __first != __last; ++__result, ++__first)
 312             *__result = *__first;
 313           return __result;
 314         }
 315     };
 316
 317 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 318   template<typename _Category>
 319     struct __copy_move<true, false, _Category>
 320     {
 321       template<typename _II, typename _OI>
 322         static _OI
 323         __copy_m(_II __first, _II __last, _OI __result)
 324         {
 325           for (; __first != __last; ++__result, ++__first)
 326             *__result = std::move(*__first);
 327           return __result;
 328         }
 329     };
 330 #endif
 331
 332   template<>
 333     struct __copy_move<false, false, random_access_iterator_tag>
 334     {
 335       template<typename _II, typename _OI>
 336         static _OI
 337         __copy_m(_II __first, _II __last, _OI __result)
 338         {
 339           typedef typename iterator_traits<_II>::difference_type _Distance;
 340           for(_Distance __n = __last - __first; __n > 0; --__n)
 341             {
 342               *__result = *__first;
 343               ++__first;
 344               ++__result;
 345             }
 346           return __result;
 347         }
 348     };
 349
 350 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 351   template<>
 352     struct __copy_move<true, false, random_access_iterator_tag>
 353     {
 354       template<typename _II, typename _OI>
 355         static _OI
 356         __copy_m(_II __first, _II __last, _OI __result)
 357         {
 358           typedef typename iterator_traits<_II>::difference_type _Distance;
 359           for(_Distance __n = __last - __first; __n > 0; --__n)
 360             {
 361               *__result = std::move(*__first);
 362               ++__first;
 363               ++__result;
 364             }
 365           return __result;
 366         }
 367     };
 368 #endif
 369
 370   template<bool _IsMove>
 371     struct __copy_move<_IsMove, true, random_access_iterator_tag>
 372     {
 373       template<typename _Tp>
 374         static _Tp*
 375         __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
 376         {
 377           __builtin_memmove(__result, __first,
 378                             sizeof(_Tp) * (__last - __first));
 379           return __result + (__last - __first);
 380         }
 381     };
 382
 383   template<bool _IsMove, typename _II, typename _OI>
 384     inline _OI
 385     __copy_move_a(_II __first, _II __last, _OI __result)
 386     {
 387       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
 388       typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
 389       typedef typename iterator_traits<_II>::iterator_category _Category;
 390       const bool __simple = (__is_pod(_ValueTypeI)
 391                              && __is_pointer<_II>::__value
 392                              && __is_pointer<_OI>::__value
 393                              && __are_same<_ValueTypeI, _ValueTypeO>::__value);
 394
 395       return std::__copy_move<_IsMove, __simple,
 396                               _Category>::__copy_m(__first, __last, __result);
 397     }
 398
 399   // Helpers for streambuf iterators (either istream or ostream).
 400   // NB: avoid including <iosfwd>, relatively large.
 401   template<typename _CharT>
 402     struct char_traits;
 403
 404   template<typename _CharT, typename _Traits>
 405     class istreambuf_iterator;
 406
 407   template<typename _CharT, typename _Traits>
 408     class ostreambuf_iterator;
 409
 410   template<bool _IsMove, typename _CharT>
 411     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 412              ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
 413     __copy_move_a2(_CharT*, _CharT*,
 414                    ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 415
 416   template<bool _IsMove, typename _CharT>
 417     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 418              ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
 419     __copy_move_a2(const _CharT*, const _CharT*,
 420                    ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 421
 422   template<bool _IsMove, typename _CharT>
 423     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 424                                     _CharT*>::__type
 425     __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
 426                    istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
 427
 428   template<bool _IsMove, typename _II, typename _OI>
 429     inline _OI
 430     __copy_move_a2(_II __first, _II __last, _OI __result)
 431     {
 432       return _OI(std::__copy_move_a<_IsMove>
 433                  (std::__niter_base<_II>::__b(__first),
 434                   std::__niter_base<_II>::__b(__last),
 435                   std::__niter_base<_OI>::__b(__result)));
 436     }
 437
 438   /**
 439    *  @brief Copies the range [first,last) into result.
 440    *  @param  first  An input iterator.
 441    *  @param  last   An input iterator.
 442    *  @param  result An output iterator.
 443    *  @return   result + (first - last)
 444    *
 445    *  This inline function will boil down to a call to @c memmove whenever
 446    *  possible.  Failing that, if random access iterators are passed, then the
 447    *  loop count will be known (and therefore a candidate for compiler
 448    *  optimizations such as unrolling).  Result may not be contained within
 449    *  [first,last); the copy_backward function should be used instead.
 450    *
 451    *  Note that the end of the output range is permitted to be contained
 452    *  within [first,last).
 453   */
 454   template<typename _II, typename _OI>
 455     inline _OI
 456     copy(_II __first, _II __last, _OI __result)
 457     {
 458       // concept requirements
 459       __glibcxx_function_requires(_InputIteratorConcept<_II>)
 460       __glibcxx_function_requires(_OutputIteratorConcept<_OI,
 461             typename iterator_traits<_II>::value_type>)
 462       __glibcxx_requires_valid_range(__first, __last);
 463
 464       return (std::__copy_move_a2<__is_move_iterator<_II>::__value>
 465               (std::__miter_base<_II>::__b(__first),
 466                std::__miter_base<_II>::__b(__last), __result));
 467     }
 468
 469 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 470   /**
 471    *  @brief Moves the range [first,last) into result.
 472    *  @param  first  An input iterator.
 473    *  @param  last   An input iterator.
 474    *  @param  result An output iterator.
 475    *  @return   result + (first - last)
 476    *
 477    *  This inline function will boil down to a call to @c memmove whenever
 478    *  possible.  Failing that, if random access iterators are passed, then the
 479    *  loop count will be known (and therefore a candidate for compiler
 480    *  optimizations such as unrolling).  Result may not be contained within
 481    *  [first,last); the move_backward function should be used instead.
 482    *
 483    *  Note that the end of the output range is permitted to be contained
 484    *  within [first,last).
 485   */
 486   template<typename _II, typename _OI>
 487     inline _OI
 488     move(_II __first, _II __last, _OI __result)
 489     {
 490       // concept requirements
 491       __glibcxx_function_requires(_InputIteratorConcept<_II>)
 492       __glibcxx_function_requires(_OutputIteratorConcept<_OI,
 493             typename iterator_traits<_II>::value_type>)
 494       __glibcxx_requires_valid_range(__first, __last);
 495
 496       return (std::__copy_move_a2<true>
 497               (std::__miter_base<_II>::__b(__first),
 498                std::__miter_base<_II>::__b(__last), __result));
 499     }
 500
 501 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
 502 #else
 503 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
 504 #endif
 505
 506   template<bool, bool, typename>
 507     struct __copy_move_backward
 508     {
 509       template<typename _BI1, typename _BI2>
 510         static _BI2
 511         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 512         {
 513           while (__first != __last)
 514             *--__result = *--__last;
 515           return __result;
 516         }
 517     };
 518
 519 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 520   template<typename _Category>
 521     struct __copy_move_backward<true, false, _Category>
 522     {
 523       template<typename _BI1, typename _BI2>
 524         static _BI2
 525         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 526         {
 527           while (__first != __last)
 528             *--__result = std::move(*--__last);
 529           return __result;
 530         }
 531     };
 532 #endif
 533
 534   template<>
 535     struct __copy_move_backward<false, false, random_access_iterator_tag>
 536     {
 537       template<typename _BI1, typename _BI2>
 538         static _BI2
 539         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 540         {
 541           typename iterator_traits<_BI1>::difference_type __n;
 542           for (__n = __last - __first; __n > 0; --__n)
 543             *--__result = *--__last;
 544           return __result;
 545         }
 546     };
 547
 548 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 549   template<>
 550     struct __copy_move_backward<true, false, random_access_iterator_tag>
 551     {
 552       template<typename _BI1, typename _BI2>
 553         static _BI2
 554         __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
 555         {
 556           typename iterator_traits<_BI1>::difference_type __n;
 557           for (__n = __last - __first; __n > 0; --__n)
 558             *--__result = std::move(*--__last);
 559           return __result;
 560         }
 561     };
 562 #endif
 563
 564   template<bool _IsMove>
 565     struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
 566     {
 567       template<typename _Tp>
 568         static _Tp*
 569         __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
 570         {
 571           const ptrdiff_t _Num = __last - __first;
 572           __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
 573           return __result - _Num;
 574         }
 575     };
 576
 577   template<bool _IsMove, typename _BI1, typename _BI2>
 578     inline _BI2
 579     __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
 580     {
 581       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
 582       typedef typename iterator_traits<_BI2>::value_type _ValueType2;
 583       typedef typename iterator_traits<_BI1>::iterator_category _Category;
 584       const bool __simple = (__is_pod(_ValueType1)
 585                              && __is_pointer<_BI1>::__value
 586                              && __is_pointer<_BI2>::__value
 587                              && __are_same<_ValueType1, _ValueType2>::__value);
 588
 589       return std::__copy_move_backward<_IsMove, __simple,
 590                                        _Category>::__copy_move_b(__first,
 591                                                                  __last,
 592                                                                  __result);
 593     }
 594
 595   template<bool _IsMove, typename _BI1, typename _BI2>
 596     inline _BI2
 597     __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
 598     {
 599       return _BI2(std::__copy_move_backward_a<_IsMove>
 600                   (std::__niter_base<_BI1>::__b(__first),
 601                    std::__niter_base<_BI1>::__b(__last),
 602                    std::__niter_base<_BI2>::__b(__result)));
 603     }
 604
 605   /**
 606    *  @brief Copies the range [first,last) into result.
 607    *  @param  first  A bidirectional iterator.
 608    *  @param  last   A bidirectional iterator.
 609    *  @param  result A bidirectional iterator.
 610    *  @return   result - (first - last)
 611    *
 612    *  The function has the same effect as copy, but starts at the end of the
 613    *  range and works its way to the start, returning the start of the result.
 614    *  This inline function will boil down to a call to @c memmove whenever
 615    *  possible.  Failing that, if random access iterators are passed, then the
 616    *  loop count will be known (and therefore a candidate for compiler
 617    *  optimizations such as unrolling).
 618    *
 619    *  Result may not be in the range [first,last).  Use copy instead.  Note
 620    *  that the start of the output range may overlap [first,last).
 621   */
 622   template<typename _BI1, typename _BI2>
 623     inline _BI2
 624     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
 625     {
 626       // concept requirements
 627       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
 628       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
 629       __glibcxx_function_requires(_ConvertibleConcept<
 630             typename iterator_traits<_BI1>::value_type,
 631             typename iterator_traits<_BI2>::value_type>)
 632       __glibcxx_requires_valid_range(__first, __last);
 633
 634       return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
 635               (std::__miter_base<_BI1>::__b(__first),
 636                std::__miter_base<_BI1>::__b(__last), __result));
 637     }
 638
 639 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 640   /**
 641    *  @brief Moves the range [first,last) into result.
 642    *  @param  first  A bidirectional iterator.
 643    *  @param  last   A bidirectional iterator.
 644    *  @param  result A bidirectional iterator.
 645    *  @return   result - (first - last)
 646    *
 647    *  The function has the same effect as move, but starts at the end of the
 648    *  range and works its way to the start, returning the start of the result.
 649    *  This inline function will boil down to a call to @c memmove whenever
 650    *  possible.  Failing that, if random access iterators are passed, then the
 651    *  loop count will be known (and therefore a candidate for compiler
 652    *  optimizations such as unrolling).
 653    *
 654    *  Result may not be in the range [first,last).  Use move instead.  Note
 655    *  that the start of the output range may overlap [first,last).
 656   */
 657   template<typename _BI1, typename _BI2>
 658     inline _BI2
 659     move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
 660     {
 661       // concept requirements
 662       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
 663       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
 664       __glibcxx_function_requires(_ConvertibleConcept<
 665             typename iterator_traits<_BI1>::value_type,
 666             typename iterator_traits<_BI2>::value_type>)
 667       __glibcxx_requires_valid_range(__first, __last);
 668
 669       return (std::__copy_move_backward_a2<true>
 670               (std::__miter_base<_BI1>::__b(__first),
 671                std::__miter_base<_BI1>::__b(__last), __result));
 672     }
 673
 674 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
 675 #else
 676 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
 677 #endif
 678
 679   template<typename _ForwardIterator, typename _Tp>
 680     inline typename
 681     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
 682     __fill_a(_ForwardIterator __first, _ForwardIterator __last,
 683              const _Tp& __value)
 684     {
 685       for (; __first != __last; ++__first)
 686         *__first = __value;
 687     }
 688
 689   template<typename _ForwardIterator, typename _Tp>
 690     inline typename
 691     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
 692     __fill_a(_ForwardIterator __first, _ForwardIterator __last,
 693              const _Tp& __value)
 694     {
 695       const _Tp __tmp = __value;
 696       for (; __first != __last; ++__first)
 697         *__first = __tmp;
 698     }
 699
 700   // Specialization: for char types we can use memset.
 701   template<typename _Tp>
 702     inline typename
 703     __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
 704     __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
 705     {
 706       const _Tp __tmp = __c;
 707       __builtin_memset(__first, static_cast<unsigned char>(__tmp),
 708                        __last - __first);
 709     }
 710
 711   /**
 712    *  @brief Fills the range [first,last) with copies of value.
 713    *  @param  first  A forward iterator.
 714    *  @param  last   A forward iterator.
 715    *  @param  value  A reference-to-const of arbitrary type.
 716    *  @return   Nothing.
 717    *
 718    *  This function fills a range with copies of the same value.  For char
 719    *  types filling contiguous areas of memory, this becomes an inline call
 720    *  to @c memset or @c wmemset.
 721   */
 722   template<typename _ForwardIterator, typename _Tp>
 723     inline void
 724     fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
 725     {
 726       // concept requirements
 727       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 728                                   _ForwardIterator>)
 729       __glibcxx_requires_valid_range(__first, __last);
 730
 731       std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first),
 732                     std::__niter_base<_ForwardIterator>::__b(__last), __value);
 733     }
 734
 735   template<typename _OutputIterator, typename _Size, typename _Tp>
 736     inline typename
 737     __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
 738     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
 739     {
 740       for (; __n > 0; --__n, ++__first)
 741         *__first = __value;
 742       return __first;
 743     }
 744
 745   template<typename _OutputIterator, typename _Size, typename _Tp>
 746     inline typename
 747     __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
 748     __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
 749     {
 750       const _Tp __tmp = __value;
 751       for (; __n > 0; --__n, ++__first)
 752         *__first = __tmp;
 753       return __first;
 754     }
 755
 756   template<typename _Size, typename _Tp>
 757     inline typename
 758     __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
 759     __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
 760     {
 761       std::__fill_a(__first, __first + __n, __c);
 762       return __first + __n;
 763     }
 764
 765   /**
 766    *  @brief Fills the range [first,first+n) with copies of value.
 767    *  @param  first  An output iterator.
 768    *  @param  n      The count of copies to perform.
 769    *  @param  value  A reference-to-const of arbitrary type.
 770    *  @return   The iterator at first+n.
 771    *
 772    *  This function fills a range with copies of the same value.  For char
 773    *  types filling contiguous areas of memory, this becomes an inline call
 774    *  to @c memset or @ wmemset.
 775   */
 776   template<typename _OI, typename _Size, typename _Tp>
 777     inline _OI
 778     fill_n(_OI __first, _Size __n, const _Tp& __value)
 779     {
 780       // concept requirements
 781       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
 782
 783       return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first),
 784                                  __n, __value));
 785     }
 786
 787   template<bool _BoolType>
 788     struct __equal
 789     {
 790       template<typename _II1, typename _II2>
 791         static bool
 792         equal(_II1 __first1, _II1 __last1, _II2 __first2)
 793         {
 794           for (; __first1 != __last1; ++__first1, ++__first2)
 795             if (!(*__first1 == *__first2))
 796               return false;
 797           return true;
 798         }
 799     };
 800
 801   template<>
 802     struct __equal<true>
 803     {
 804       template<typename _Tp>
 805         static bool
 806         equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
 807         {
 808           return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
 809                                    * (__last1 - __first1));
 810         }
 811     };
 812
 813   template<typename _II1, typename _II2>
 814     inline bool
 815     __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
 816     {
 817       typedef typename iterator_traits<_II1>::value_type _ValueType1;
 818       typedef typename iterator_traits<_II2>::value_type _ValueType2;
 819       const bool __simple = (__is_integer<_ValueType1>::__value
 820                              && __is_pointer<_II1>::__value
 821                              && __is_pointer<_II2>::__value
 822                              && __are_same<_ValueType1, _ValueType2>::__value);
 823
 824       return std::__equal<__simple>::equal(__first1, __last1, __first2);
 825     }
 826
 827
 828   template<typename, typename>
 829     struct __lc_rai
 830     {
 831       template<typename _II1, typename _II2>
 832         static _II1
 833         __newlast1(_II1, _II1 __last1, _II2, _II2)
 834         { return __last1; }
 835
 836       template<typename _II>
 837         static bool
 838         __cnd2(_II __first, _II __last)
 839         { return __first != __last; }
 840     };
 841
 842   template<>
 843     struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
 844     {
 845       template<typename _RAI1, typename _RAI2>
 846         static _RAI1
 847         __newlast1(_RAI1 __first1, _RAI1 __last1,
 848                    _RAI2 __first2, _RAI2 __last2)
 849         {
 850           const typename iterator_traits<_RAI1>::difference_type
 851             __diff1 = __last1 - __first1;
 852           const typename iterator_traits<_RAI2>::difference_type
 853             __diff2 = __last2 - __first2;
 854           return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
 855         }
 856
 857       template<typename _RAI>
 858         static bool
 859         __cnd2(_RAI, _RAI)
 860         { return true; }
 861     };
 862
 863   template<bool _BoolType>
 864     struct __lexicographical_compare
 865     {
 866       template<typename _II1, typename _II2>
 867         static bool __lc(_II1, _II1, _II2, _II2);
 868     };
 869
 870   template<bool _BoolType>
 871     template<typename _II1, typename _II2>
 872       bool
 873       __lexicographical_compare<_BoolType>::
 874       __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
 875       {
 876         typedef typename iterator_traits<_II1>::iterator_category _Category1;
 877         typedef typename iterator_traits<_II2>::iterator_category _Category2;
 878         typedef std::__lc_rai<_Category1, _Category2>   __rai_type;
 879
 880         __last1 = __rai_type::__newlast1(__first1, __last1,
 881                                          __first2, __last2);
 882         for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
 883              ++__first1, ++__first2)
 884           {
 885             if (*__first1 < *__first2)
 886               return true;
 887             if (*__first2 < *__first1)
 888               return false;
 889           }
 890         return __first1 == __last1 && __first2 != __last2;
 891       }
 892
 893   template<>
 894     struct __lexicographical_compare<true>
 895     {
 896       template<typename _Tp, typename _Up>
 897         static bool
 898         __lc(const _Tp* __first1, const _Tp* __last1,
 899              const _Up* __first2, const _Up* __last2)
 900         {
 901           const size_t __len1 = __last1 - __first1;
 902           const size_t __len2 = __last2 - __first2;
 903           const int __result = __builtin_memcmp(__first1, __first2,
 904                                                 std::min(__len1, __len2));
 905           return __result != 0 ? __result < 0 : __len1 < __len2;
 906         }
 907     };
 908
 909   template<typename _II1, typename _II2>
 910     inline bool
 911     __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
 912                                   _II2 __first2, _II2 __last2)
 913     {
 914       typedef typename iterator_traits<_II1>::value_type _ValueType1;
 915       typedef typename iterator_traits<_II2>::value_type _ValueType2;
 916       const bool __simple =
 917         (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
 918          && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
 919          && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
 920          && __is_pointer<_II1>::__value
 921          && __is_pointer<_II2>::__value);
 922
 923       return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
 924                                                             __first2, __last2);
 925     }
 926
 927 _GLIBCXX_END_NAMESPACE
 928
 929 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 930
 931   /**
 932    *  @brief Tests a range for element-wise equality.
 933    *  @param  first1  An input iterator.
 934    *  @param  last1   An input iterator.
 935    *  @param  first2  An input iterator.
 936    *  @return   A boolean true or false.
 937    *
 938    *  This compares the elements of two ranges using @c == and returns true or
 939    *  false depending on whether all of the corresponding elements of the
 940    *  ranges are equal.
 941   */
 942   template<typename _II1, typename _II2>
 943     inline bool
 944     equal(_II1 __first1, _II1 __last1, _II2 __first2)
 945     {
 946       // concept requirements
 947       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
 948       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
 949       __glibcxx_function_requires(_EqualOpConcept<
 950             typename iterator_traits<_II1>::value_type,
 951             typename iterator_traits<_II2>::value_type>)
 952       __glibcxx_requires_valid_range(__first1, __last1);
 953
 954       return std::__equal_aux(std::__niter_base<_II1>::__b(__first1),
 955                               std::__niter_base<_II1>::__b(__last1),
 956                               std::__niter_base<_II2>::__b(__first2));
 957     }
 958
 959   /**
 960    *  @brief Tests a range for element-wise equality.
 961    *  @param  first1  An input iterator.
 962    *  @param  last1   An input iterator.
 963    *  @param  first2  An input iterator.
 964    *  @param binary_pred A binary predicate @link s20_3_1_base
 965    *                  functor@endlink.
 966    *  @return         A boolean true or false.
 967    *
 968    *  This compares the elements of two ranges using the binary_pred
 969    *  parameter, and returns true or
 970    *  false depending on whether all of the corresponding elements of the
 971    *  ranges are equal.
 972   */
 973   template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
 974     inline bool
 975     equal(_IIter1 __first1, _IIter1 __last1,
 976           _IIter2 __first2, _BinaryPredicate __binary_pred)
 977     {
 978       // concept requirements
 979       __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
 980       __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
 981       __glibcxx_requires_valid_range(__first1, __last1);
 982
 983       for (; __first1 != __last1; ++__first1, ++__first2)
 984         if (!bool(__binary_pred(*__first1, *__first2)))
 985           return false;
 986       return true;
 987     }
 988
 989   /**
 990    *  @brief Performs "dictionary" comparison on ranges.
 991    *  @param  first1  An input iterator.
 992    *  @param  last1   An input iterator.
 993    *  @param  first2  An input iterator.
 994    *  @param  last2   An input iterator.
 995    *  @return   A boolean true or false.
 996    *
 997    *  "Returns true if the sequence of elements defined by the range
 998    *  [first1,last1) is lexicographically less than the sequence of elements
 999    *  defined by the range [first2,last2).  Returns false otherwise."
1000    *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
1001    *  then this is an inline call to @c memcmp.
1002   */
1003   template<typename _II1, typename _II2>
1004     inline bool
1005     lexicographical_compare(_II1 __first1, _II1 __last1,
1006                             _II2 __first2, _II2 __last2)
1007     {
1008       // concept requirements
1009       typedef typename iterator_traits<_II1>::value_type _ValueType1;
1010       typedef typename iterator_traits<_II2>::value_type _ValueType2;
1011       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1012       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1013       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1014       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1015       __glibcxx_requires_valid_range(__first1, __last1);
1016       __glibcxx_requires_valid_range(__first2, __last2);
1017
1018       return std::__lexicographical_compare_aux
1019         (std::__niter_base<_II1>::__b(__first1),
1020          std::__niter_base<_II1>::__b(__last1),
1021          std::__niter_base<_II2>::__b(__first2),
1022          std::__niter_base<_II2>::__b(__last2));
1023     }
1024
1025   /**
1026    *  @brief Performs "dictionary" comparison on ranges.
1027    *  @param  first1  An input iterator.
1028    *  @param  last1   An input iterator.
1029    *  @param  first2  An input iterator.
1030    *  @param  last2   An input iterator.
1031    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
1032    *  @return   A boolean true or false.
1033    *
1034    *  The same as the four-parameter @c lexicographical_compare, but uses the
1035    *  comp parameter instead of @c <.
1036   */
1037   template<typename _II1, typename _II2, typename _Compare>
1038     bool
1039     lexicographical_compare(_II1 __first1, _II1 __last1,
1040                             _II2 __first2, _II2 __last2, _Compare __comp)
1041     {
1042       typedef typename iterator_traits<_II1>::iterator_category _Category1;
1043       typedef typename iterator_traits<_II2>::iterator_category _Category2;
1044       typedef std::__lc_rai<_Category1, _Category2>     __rai_type;
1045
1046       // concept requirements
1047       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1048       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1049       __glibcxx_requires_valid_range(__first1, __last1);
1050       __glibcxx_requires_valid_range(__first2, __last2);
1051
1052       __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1053       for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1054            ++__first1, ++__first2)
1055         {
1056           if (__comp(*__first1, *__first2))
1057             return true;
1058           if (__comp(*__first2, *__first1))
1059             return false;
1060         }
1061       return __first1 == __last1 && __first2 != __last2;
1062     }
1063
1064   /**
1065    *  @brief Finds the places in ranges which don't match.
1066    *  @param  first1  An input iterator.
1067    *  @param  last1   An input iterator.
1068    *  @param  first2  An input iterator.
1069    *  @return   A pair of iterators pointing to the first mismatch.
1070    *
1071    *  This compares the elements of two ranges using @c == and returns a pair
1072    *  of iterators.  The first iterator points into the first range, the
1073    *  second iterator points into the second range, and the elements pointed
1074    *  to by the iterators are not equal.
1075   */
1076   template<typename _InputIterator1, typename _InputIterator2>
1077     pair<_InputIterator1, _InputIterator2>
1078     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1079              _InputIterator2 __first2)
1080     {
1081       // concept requirements
1082       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1083       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1084       __glibcxx_function_requires(_EqualOpConcept<
1085             typename iterator_traits<_InputIterator1>::value_type,
1086             typename iterator_traits<_InputIterator2>::value_type>)
1087       __glibcxx_requires_valid_range(__first1, __last1);
1088
1089       while (__first1 != __last1 && *__first1 == *__first2)
1090         {
1091           ++__first1;
1092           ++__first2;
1093         }
1094       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1095     }
1096
1097   /**
1098    *  @brief Finds the places in ranges which don't match.
1099    *  @param  first1  An input iterator.
1100    *  @param  last1   An input iterator.
1101    *  @param  first2  An input iterator.
1102    *  @param binary_pred A binary predicate @link s20_3_1_base
1103    *         functor@endlink.
1104    *  @return   A pair of iterators pointing to the first mismatch.
1105    *
1106    *  This compares the elements of two ranges using the binary_pred
1107    *  parameter, and returns a pair
1108    *  of iterators.  The first iterator points into the first range, the
1109    *  second iterator points into the second range, and the elements pointed
1110    *  to by the iterators are not equal.
1111   */
1112   template<typename _InputIterator1, typename _InputIterator2,
1113            typename _BinaryPredicate>
1114     pair<_InputIterator1, _InputIterator2>
1115     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1116              _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1117     {
1118       // concept requirements
1119       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1120       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1121       __glibcxx_requires_valid_range(__first1, __last1);
1122
1123       while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
1124         {
1125           ++__first1;
1126           ++__first2;
1127         }
1128       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1129     }
1130
1131 _GLIBCXX_END_NESTED_NAMESPACE
1132
1133 // NB: This file is included within many other C++ includes, as a way
1134 // of getting the base algorithms. So, make sure that parallel bits
1135 // come in too if requested.
1136 #ifdef _GLIBCXX_PARALLEL
1137 # include <parallel/algobase.h>
1138 #endif
1139
1140 #endif