libstdc++-v3/include/bits/stl_algobase.h

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