Whole document tree
    

Whole document tree

stl_algobase.h Source File
Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

stl_algobase.h

Go to the documentation of this file.
00001 // Bits and pieces used in algorithms -*- C++ -*-
00002 
00003 // Copyright (C) 2001 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /*
00031  *
00032  * Copyright (c) 1994
00033  * Hewlett-Packard Company
00034  *
00035  * Permission to use, copy, modify, distribute and sell this software
00036  * and its documentation for any purpose is hereby granted without fee,
00037  * provided that the above copyright notice appear in all copies and
00038  * that both that copyright notice and this permission notice appear
00039  * in supporting documentation.  Hewlett-Packard Company makes no
00040  * representations about the suitability of this software for any
00041  * purpose.  It is provided "as is" without express or implied warranty.
00042  *
00043  *
00044  * Copyright (c) 1996-1998
00045  * Silicon Graphics Computer Systems, Inc.
00046  *
00047  * Permission to use, copy, modify, distribute and sell this software
00048  * and its documentation for any purpose is hereby granted without fee,
00049  * provided that the above copyright notice appear in all copies and
00050  * that both that copyright notice and this permission notice appear
00051  * in supporting documentation.  Silicon Graphics makes no
00052  * representations about the suitability of this software for any
00053  * purpose.  It is provided "as is" without express or implied warranty.
00054  */
00055 
00056 /* NOTE: This is an internal header file, included by other STL headers.
00057  *   You should not attempt to use it directly.
00058  */
00059 
00060 
00061 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
00062 #define __SGI_STL_INTERNAL_ALGOBASE_H
00063 
00064 #include <bits/c++config.h>
00065 #ifndef __SGI_STL_INTERNAL_PAIR_H
00066 #include <bits/stl_pair.h>
00067 #endif
00068 #ifndef _CPP_BITS_TYPE_TRAITS_H
00069 #include <bits/type_traits.h>
00070 #endif
00071 #include <bits/std_cstring.h>
00072 #include <bits/std_climits.h>
00073 #include <bits/std_cstdlib.h>
00074 #include <bits/std_cstddef.h>
00075 #include <new>
00076 
00077 #include <bits/std_iosfwd.h>
00078 #include <bits/stl_iterator_base_types.h>
00079 #include <bits/stl_iterator_base_funcs.h>
00080 #include <bits/stl_iterator.h>
00081 #include <bits/concept_check.h>
00082 
00083 namespace std
00084 {
00085 
00086 // swap and iter_swap
00087 
00088 template <class _ForwardIter1, class _ForwardIter2, class _Tp>
00089 inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*)
00090 {
00091   _Tp __tmp = *__a;
00092   *__a = *__b;
00093   *__b = __tmp;
00094 }
00095 
00096 template <class _ForwardIter1, class _ForwardIter2>
00097 inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
00098 {
00099   // concept requirements
00100   __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>);
00101   __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>);
00102   __glibcpp_function_requires(_ConvertibleConcept<
00103         typename iterator_traits<_ForwardIter1>::value_type,
00104         typename iterator_traits<_ForwardIter2>::value_type>);
00105   __glibcpp_function_requires(_ConvertibleConcept<
00106         typename iterator_traits<_ForwardIter2>::value_type,
00107         typename iterator_traits<_ForwardIter1>::value_type>);
00108 
00109   __iter_swap(__a, __b, __value_type(__a));
00110 }
00111 
00112 template <class _Tp>
00113 inline void swap(_Tp& __a, _Tp& __b)
00114 {
00115   // concept requirements
00116   __glibcpp_function_requires(_SGIAssignableConcept<_Tp>);
00117 
00118   _Tp __tmp = __a;
00119   __a = __b;
00120   __b = __tmp;
00121 }
00122 
00123 //--------------------------------------------------
00124 // min and max
00125 
00126 #undef min
00127 #undef max
00128 
00129 template <class _Tp>
00130 inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
00131   // concept requirements
00132   __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
00133   //return __b < __a ? __b : __a;
00134   if (__b < __a) return __b; return __a;
00135 }
00136 
00137 template <class _Tp>
00138 inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
00139   // concept requirements
00140   __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
00141   //return  __a < __b ? __b : __a;
00142   if (__a < __b) return __b; return __a;
00143 }
00144 
00145 template <class _Tp, class _Compare>
00146 inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
00147   //return __comp(__b, __a) ? __b : __a;
00148   if (__comp(__b, __a)) return __b; return __a;
00149 }
00150 
00151 template <class _Tp, class _Compare>
00152 inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
00153   //return __comp(__a, __b) ? __b : __a;
00154   if (__comp(__a, __b)) return __b; return __a;
00155 }
00156 
00157 //--------------------------------------------------
00158 // copy
00159 
00160 // All of these auxiliary functions serve two purposes.  (1) Replace
00161 // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
00162 // because the input and output ranges are permitted to overlap.)
00163 // (2) If we're using random access iterators, then write the loop as
00164 // a for loop with an explicit count.
00165 
00166 template <class _InputIter, class _OutputIter, class _Distance>
00167 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
00168                           _OutputIter __result,
00169                           input_iterator_tag, _Distance*)
00170 {
00171   for ( ; __first != __last; ++__result, ++__first)
00172     *__result = *__first;
00173   return __result;
00174 }
00175 
00176 template <class _RandomAccessIter, class _OutputIter, class _Distance>
00177 inline _OutputIter
00178 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
00179        _OutputIter __result, random_access_iterator_tag, _Distance*)
00180 {
00181   for (_Distance __n = __last - __first; __n > 0; --__n) {
00182     *__result = *__first;
00183     ++__first;
00184     ++__result;
00185   }
00186   return __result;
00187 }
00188 
00189 template <class _Tp>
00190 inline _Tp*
00191 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
00192 {
00193   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
00194   return __result + (__last - __first);
00195 }
00196 
00197 
00198 template <class _InputIter, class _OutputIter>
00199 inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
00200                                _OutputIter __result, __false_type)
00201 {
00202   return __copy(__first, __last, __result,
00203                 __iterator_category(__first),
00204                 __distance_type(__first));
00205 }
00206 
00207 template <class _InputIter, class _OutputIter>
00208 inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
00209                                _OutputIter __result, __true_type)
00210 {
00211   return __copy(__first, __last, __result,
00212                 __iterator_category(__first),
00213                 __distance_type(__first));
00214 }
00215 
00216 template <class _Tp>
00217 inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,
00218                         __true_type)
00219 {
00220   return __copy_trivial(__first, __last, __result);
00221 }
00222 
00223 template <class _Tp>
00224 inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
00225                         __true_type)
00226 {
00227   return __copy_trivial(__first, __last, __result);
00228 }
00229 
00230 
00231 template <class _InputIter, class _OutputIter, class _Tp>
00232 inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
00233                               _OutputIter __result, _Tp*)
00234 {
00235   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
00236           _Trivial;
00237   return __copy_aux2(__first, __last, __result, _Trivial());
00238 }
00239 
00240 template<typename _InputIter, typename _OutputIter>
00241 inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
00242                                _OutputIter __result, __true_type)
00243 {
00244   return _OutputIter(__copy_aux(__first, __last, __result.base(),
00245                                 __value_type(__first)));
00246 }
00247 
00248 template<typename _InputIter, typename _OutputIter>
00249 inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
00250                   _OutputIter __result, __false_type)
00251 {
00252   return __copy_aux(__first, __last, __result, __value_type(__first));
00253 }
00254 
00255 template<typename _InputIter, typename _OutputIter>
00256 inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
00257                                _OutputIter __result, __true_type)
00258 {
00259   typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
00260   return __copy_ni2(__first.base(), __last.base(), __result, __Normal());
00261 }
00262 
00263 template<typename _InputIter, typename _OutputIter>
00264 inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
00265                                _OutputIter __result, __false_type)
00266 {
00267   typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
00268   return __copy_ni2(__first, __last, __result, __Normal());
00269 }
00270 
00271 template <class _InputIter, class _OutputIter>
00272 inline _OutputIter copy(_InputIter __first, _InputIter __last,
00273                         _OutputIter __result)
00274 {
00275   // concept requirements
00276   __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00277   __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00278         typename iterator_traits<_InputIter>::value_type>);
00279 
00280    typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;
00281    return __copy_ni1(__first, __last, __result, __Normal());
00282 }
00283 
00284 //--------------------------------------------------
00285 // copy_backward
00286 
00287 template <class _BidirectionalIter1, class _BidirectionalIter2, 
00288           class _Distance>
00289 inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
00290                                            _BidirectionalIter1 __last, 
00291                                            _BidirectionalIter2 __result,
00292                                            bidirectional_iterator_tag,
00293                                            _Distance*)
00294 {
00295   while (__first != __last)
00296     *--__result = *--__last;
00297   return __result;
00298 }
00299 
00300 template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
00301 inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
00302                                           _RandomAccessIter __last, 
00303                                           _BidirectionalIter __result,
00304                                           random_access_iterator_tag,
00305                                           _Distance*)
00306 {
00307   for (_Distance __n = __last - __first; __n > 0; --__n)
00308     *--__result = *--__last;
00309   return __result;
00310 }
00311 
00312 
00313 // This dispatch class is a workaround for compilers that do not 
00314 // have partial ordering of function templates.  All we're doing is
00315 // creating a specialization so that we can turn a call to copy_backward
00316 // into a memmove whenever possible.
00317 
00318 template <class _BidirectionalIter1, class _BidirectionalIter2,
00319           class _BoolType>
00320 struct __copy_backward_dispatch
00321 {
00322   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category 
00323           _Cat;
00324   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
00325           _Distance;
00326 
00327   static _BidirectionalIter2 copy(_BidirectionalIter1 __first, 
00328                                   _BidirectionalIter1 __last, 
00329                                   _BidirectionalIter2 __result) {
00330     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
00331   }
00332 };
00333 
00334 template <class _Tp>
00335 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
00336 {
00337   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
00338     const ptrdiff_t _Num = __last - __first;
00339     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
00340     return __result - _Num;
00341   }
00342 };
00343 
00344 template <class _Tp>
00345 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
00346 {
00347   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
00348     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
00349       ::copy(__first, __last, __result);
00350   }
00351 };
00352 
00353 template <class _BI1, class _BI2>
00354 inline _BI2 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) {
00355   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
00356                         ::has_trivial_assignment_operator
00357           _Trivial;
00358   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
00359               ::copy(__first, __last, __result);
00360 }
00361 
00362 template <typename _BI1, typename _BI2>
00363 inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
00364                                                    _BI2 __result, __true_type) {
00365   return _BI2(__copy_backward_aux(__first, __last, __result.base()));
00366 }
00367 
00368 template <typename _BI1, typename _BI2>
00369 inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
00370                                                    _BI2 __result, __false_type){
00371   return __copy_backward_aux(__first, __last, __result);
00372 }
00373 
00374 template <typename _BI1, typename _BI2>
00375 inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
00376                                                   _BI2 __result, __true_type) {
00377   typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
00378   return __copy_backward_output_normal_iterator(__first.base(), __last.base(),
00379                                                 __result, __Normal());
00380 }
00381 
00382 template <typename _BI1, typename _BI2>
00383 inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
00384                                                   _BI2 __result, __false_type) {
00385   typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
00386   return __copy_backward_output_normal_iterator(__first, __last, __result,
00387                                                 __Normal());
00388 }
00389 
00390 template <typename _BI1, typename _BI2>
00391 inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
00392 {
00393   // concept requirements
00394   __glibcpp_function_requires(_BidirectionalIteratorConcept<_BI1>);
00395   __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>);
00396   __glibcpp_function_requires(_ConvertibleConcept<
00397         typename iterator_traits<_BI1>::value_type,
00398         typename iterator_traits<_BI2>::value_type>);
00399 
00400   typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
00401   return __copy_backward_input_normal_iterator(__first, __last, __result,
00402                                                __Normal());
00403 }
00404 
00405 //--------------------------------------------------
00406 // copy_n (not part of the C++ standard)
00407 
00408 template <class _InputIter, class _Size, class _OutputIter>
00409 pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
00410                                        _OutputIter __result,
00411                                        input_iterator_tag) {
00412   for ( ; __count > 0; --__count) {
00413     *__result = *__first;
00414     ++__first;
00415     ++__result;
00416   }
00417   return pair<_InputIter, _OutputIter>(__first, __result);
00418 }
00419 
00420 template <class _RAIter, class _Size, class _OutputIter>
00421 inline pair<_RAIter, _OutputIter>
00422 __copy_n(_RAIter __first, _Size __count,
00423          _OutputIter __result,
00424          random_access_iterator_tag) {
00425   _RAIter __last = __first + __count;
00426   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
00427 }
00428 
00429 template <class _InputIter, class _Size, class _OutputIter>
00430 inline pair<_InputIter, _OutputIter>
00431 __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
00432   return __copy_n(__first, __count, __result,
00433                   __iterator_category(__first));
00434 }
00435 
00436 template <class _InputIter, class _Size, class _OutputIter>
00437 inline pair<_InputIter, _OutputIter>
00438 copy_n(_InputIter __first, _Size __count, _OutputIter __result)
00439 {
00440   // concept requirements
00441   __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
00442   __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
00443         typename iterator_traits<_InputIter>::value_type>);
00444 
00445   return __copy_n(__first, __count, __result);
00446 }
00447 
00448 //--------------------------------------------------
00449 // fill and fill_n
00450 
00451 
00452 template <class _ForwardIter, class _Tp>
00453 void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
00454 {
00455   // concept requirements
00456   __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
00457 
00458   for ( ; __first != __last; ++__first)
00459     *__first = __value;
00460 }
00461 
00462 template <class _OutputIter, class _Size, class _Tp>
00463 _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
00464 {
00465   // concept requirements
00466   __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,_Tp>);
00467 
00468   for ( ; __n > 0; --__n, ++__first)
00469     *__first = __value;
00470   return __first;
00471 }
00472 
00473 // Specialization: for one-byte types we can use memset.
00474 
00475 inline void fill(unsigned char* __first, unsigned char* __last,
00476                  const unsigned char& __c)
00477 {
00478   unsigned char __tmp = __c;
00479   memset(__first, __tmp, __last - __first);
00480 }
00481 
00482 inline void fill(signed char* __first, signed char* __last,
00483                  const signed char& __c)
00484 {
00485   signed char __tmp = __c;
00486   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00487 }
00488 
00489 inline void fill(char* __first, char* __last, const char& __c)
00490 {
00491   char __tmp = __c;
00492   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
00493 }
00494 
00495 template <class _Size>
00496 inline unsigned char* fill_n(unsigned char* __first, _Size __n,
00497                              const unsigned char& __c)
00498 {
00499   fill(__first, __first + __n, __c);
00500   return __first + __n;
00501 }
00502 
00503 template <class _Size>
00504 inline signed char* fill_n(char* __first, _Size __n,
00505                            const signed char& __c)
00506 {
00507   fill(__first, __first + __n, __c);
00508   return __first + __n;
00509 }
00510 
00511 template <class _Size>
00512 inline char* fill_n(char* __first, _Size __n, const char& __c)
00513 {
00514   fill(__first, __first + __n, __c);
00515   return __first + __n;
00516 }
00517 
00518 
00519 //--------------------------------------------------
00520 // equal and mismatch
00521 
00522 template <class _InputIter1, class _InputIter2>
00523 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
00524                                         _InputIter1 __last1,
00525                                         _InputIter2 __first2)
00526 {
00527   // concept requirements
00528   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00529   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00530   __glibcpp_function_requires(_EqualityComparableConcept<
00531         typename iterator_traits<_InputIter1>::value_type>);
00532   __glibcpp_function_requires(_EqualityComparableConcept<
00533         typename iterator_traits<_InputIter2>::value_type>);
00534 
00535   while (__first1 != __last1 && *__first1 == *__first2) {
00536     ++__first1;
00537     ++__first2;
00538   }
00539   return pair<_InputIter1, _InputIter2>(__first1, __first2);
00540 }
00541 
00542 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
00543 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
00544                                         _InputIter1 __last1,
00545                                         _InputIter2 __first2,
00546                                         _BinaryPredicate __binary_pred)
00547 {
00548   // concept requirements
00549   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00550   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00551 
00552   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
00553     ++__first1;
00554     ++__first2;
00555   }
00556   return pair<_InputIter1, _InputIter2>(__first1, __first2);
00557 }
00558 
00559 template <class _InputIter1, class _InputIter2>
00560 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
00561                   _InputIter2 __first2)
00562 {
00563   // concept requirements
00564   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00565   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00566   __glibcpp_function_requires(_EqualOpConcept<
00567         typename iterator_traits<_InputIter1>::value_type,
00568         typename iterator_traits<_InputIter2>::value_type>);
00569 
00570   for ( ; __first1 != __last1; ++__first1, ++__first2)
00571     if (!(*__first1 == *__first2))
00572       return false;
00573   return true;
00574 }
00575 
00576 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
00577 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
00578                   _InputIter2 __first2, _BinaryPredicate __binary_pred)
00579 {
00580   // concept requirements
00581   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00582   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00583 
00584   for ( ; __first1 != __last1; ++__first1, ++__first2)
00585     if (!__binary_pred(*__first1, *__first2))
00586       return false;
00587   return true;
00588 }
00589 
00590 //--------------------------------------------------
00591 // lexicographical_compare and lexicographical_compare_3way.
00592 // (the latter is not part of the C++ standard.)
00593 
00594 template <class _InputIter1, class _InputIter2>
00595 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
00596                              _InputIter2 __first2, _InputIter2 __last2)
00597 {
00598   // concept requirements
00599   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00600   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00601   __glibcpp_function_requires(_LessThanComparableConcept<
00602         typename iterator_traits<_InputIter1>::value_type>);
00603   __glibcpp_function_requires(_LessThanComparableConcept<
00604         typename iterator_traits<_InputIter2>::value_type>);
00605 
00606   for ( ; __first1 != __last1 && __first2 != __last2
00607         ; ++__first1, ++__first2) {
00608     if (*__first1 < *__first2)
00609       return true;
00610     if (*__first2 < *__first1)
00611       return false;
00612   }
00613   return __first1 == __last1 && __first2 != __last2;
00614 }
00615 
00616 template <class _InputIter1, class _InputIter2, class _Compare>
00617 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
00618                              _InputIter2 __first2, _InputIter2 __last2,
00619                              _Compare __comp)
00620 {
00621   // concept requirements
00622   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00623   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00624 
00625   for ( ; __first1 != __last1 && __first2 != __last2
00626         ; ++__first1, ++__first2) {
00627     if (__comp(*__first1, *__first2))
00628       return true;
00629     if (__comp(*__first2, *__first1))
00630       return false;
00631   }
00632   return __first1 == __last1 && __first2 != __last2;
00633 }
00634 
00635 inline bool 
00636 lexicographical_compare(const unsigned char* __first1,
00637                         const unsigned char* __last1,
00638                         const unsigned char* __first2,
00639                         const unsigned char* __last2)
00640 {
00641   const size_t __len1 = __last1 - __first1;
00642   const size_t __len2 = __last2 - __first2;
00643   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
00644   return __result != 0 ? __result < 0 : __len1 < __len2;
00645 }
00646 
00647 inline bool lexicographical_compare(const char* __first1, const char* __last1,
00648                                     const char* __first2, const char* __last2)
00649 {
00650 #if CHAR_MAX == SCHAR_MAX
00651   return lexicographical_compare((const signed char*) __first1,
00652                                  (const signed char*) __last1,
00653                                  (const signed char*) __first2,
00654                                  (const signed char*) __last2);
00655 #else /* CHAR_MAX == SCHAR_MAX */
00656   return lexicographical_compare((const unsigned char*) __first1,
00657                                  (const unsigned char*) __last1,
00658                                  (const unsigned char*) __first2,
00659                                  (const unsigned char*) __last2);
00660 #endif /* CHAR_MAX == SCHAR_MAX */
00661 }
00662 
00663 template <class _InputIter1, class _InputIter2>
00664 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
00665                                    _InputIter2 __first2, _InputIter2 __last2)
00666 {
00667   while (__first1 != __last1 && __first2 != __last2) {
00668     if (*__first1 < *__first2)
00669       return -1;
00670     if (*__first2 < *__first1)
00671       return 1;
00672     ++__first1;
00673     ++__first2;
00674   }
00675   if (__first2 == __last2) {
00676     return !(__first1 == __last1);
00677   }
00678   else {
00679     return -1;
00680   }
00681 }
00682 
00683 inline int
00684 __lexicographical_compare_3way(const unsigned char* __first1,
00685                                const unsigned char* __last1,
00686                                const unsigned char* __first2,
00687                                const unsigned char* __last2)
00688 {
00689   const ptrdiff_t __len1 = __last1 - __first1;
00690   const ptrdiff_t __len2 = __last2 - __first2;
00691   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
00692   return __result != 0 ? __result 
00693                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
00694 }
00695 
00696 inline int 
00697 __lexicographical_compare_3way(const char* __first1, const char* __last1,
00698                                const char* __first2, const char* __last2)
00699 {
00700 #if CHAR_MAX == SCHAR_MAX
00701   return __lexicographical_compare_3way(
00702                                 (const signed char*) __first1,
00703                                 (const signed char*) __last1,
00704                                 (const signed char*) __first2,
00705                                 (const signed char*) __last2);
00706 #else
00707   return __lexicographical_compare_3way((const unsigned char*) __first1,
00708                                         (const unsigned char*) __last1,
00709                                         (const unsigned char*) __first2,
00710                                         (const unsigned char*) __last2);
00711 #endif
00712 }
00713 
00714 template <class _InputIter1, class _InputIter2>
00715 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
00716                                  _InputIter2 __first2, _InputIter2 __last2)
00717 {
00718   // concept requirements
00719   __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
00720   __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
00721   __glibcpp_function_requires(_LessThanComparableConcept<
00722         typename iterator_traits<_InputIter1>::value_type>);
00723   __glibcpp_function_requires(_LessThanComparableConcept<
00724         typename iterator_traits<_InputIter2>::value_type>);
00725 
00726   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
00727 }
00728 
00729 } // namespace std
00730 
00731 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
00732 
00733 // Local Variables:
00734 // mode:C++
00735 // End:

Generated on Mon Apr 8 03:11:37 2002 for libstdc++-v3 Source by doxygen1.2.15