/home/ntakagi/work/STLport-5.1.5/stlport/stl/_algo.c

Go to the documentation of this file.
00001 /*
00002  *
00003  * Copyright (c) 1994
00004  * Hewlett-Packard Company
00005  *
00006  * Copyright (c) 1996,1997
00007  * Silicon Graphics Computer Systems, Inc.
00008  *
00009  * Copyright (c) 1997
00010  * Moscow Center for SPARC Technology
00011  *
00012  * Copyright (c) 1999
00013  * Boris Fomitchev
00014  *
00015  * This material is provided "as is", with absolutely no warranty expressed
00016  * or implied. Any use is at your own risk.
00017  *
00018  * Permission to use or copy this software for any purpose is hereby granted
00019  * without fee, provided the above notices are retained on all copies.
00020  * Permission to modify the code and to distribute modified code is granted,
00021  * provided the above notices are retained, and a notice that the code was
00022  * modified is included with the above copyright notice.
00023  *
00024  */
00025 
00026 #ifndef _STLP_ALGO_C
00027 #define _STLP_ALGO_C
00028 
00029 #if !defined (_STLP_INTERNAL_ALGO_H)
00030 #  include <stl/_algo.h>
00031 #endif
00032 
00033 #ifndef _STLP_INTERNAL_TEMPBUF_H
00034 #  include <stl/_tempbuf.h>
00035 #endif
00036 
00037 _STLP_BEGIN_NAMESPACE
00038 
00039 _STLP_MOVE_TO_PRIV_NAMESPACE
00040 
00041 template <class _BidirectionalIter, class _Distance, class _Compare>
00042 void __merge_without_buffer(_BidirectionalIter __first,
00043                             _BidirectionalIter __middle,
00044                             _BidirectionalIter __last,
00045                             _Distance __len1, _Distance __len2,
00046                             _Compare __comp);
00047 
00048 
00049 template <class _BidirectionalIter1, class _BidirectionalIter2,
00050           class _BidirectionalIter3, class _Compare>
00051 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
00052                                      _BidirectionalIter1 __last1,
00053                                      _BidirectionalIter2 __first2,
00054                                      _BidirectionalIter2 __last2,
00055                                      _BidirectionalIter3 __result,
00056                                      _Compare __comp);
00057 
00058 template <class _Tp>
00059 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
00060 inline
00061 #endif
00062 const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
00063   if (__a < __b)
00064     if (__b < __c)
00065       return __b;
00066     else if (__a < __c)
00067       return __c;
00068     else
00069       return __a;
00070   else if (__a < __c)
00071     return __a;
00072   else if (__b < __c)
00073     return __c;
00074   else
00075     return __b;
00076 }
00077 
00078 template <class _Tp, class _Compare>
00079 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
00080 inline
00081 #endif
00082 const _Tp&
00083 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
00084   if (__comp(__a, __b)) {
00085     _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00086     if (__comp(__b, __c)) {
00087       _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00088       return __b;
00089     }
00090     else if (__comp(__a, __c)) {
00091       _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00092       return __c;
00093     }
00094     else
00095       return __a;
00096   }
00097   else if (__comp(__a, __c)) {
00098     _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00099     return __a;
00100   }
00101   else if (__comp(__b, __c)) {
00102     _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00103     return __c;
00104   }
00105   else
00106     return __b;
00107 }
00108 
00109 _STLP_MOVE_TO_STD_NAMESPACE
00110 
00111 template <class _ForwardIter1, class _ForwardIter2>
00112 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
00113                      _ForwardIter2 __first2, _ForwardIter2 __last2) {
00114   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00115   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00116   // Test for empty ranges
00117   if (__first1 == __last1 || __first2 == __last2)
00118     return __first1;
00119 
00120   // Test for a pattern of length 1.
00121   _ForwardIter2 __p1(__first2);
00122 
00123   if ( ++__p1 == __last2 )
00124     return find(__first1, __last1, *__first2);
00125 
00126   // General case.
00127 
00128   for ( ; ; ) { // __first1 != __last1 will be checked in find below
00129     __first1 = find(__first1, __last1, *__first2);
00130     if (__first1 == __last1)
00131       return __last1;
00132 
00133     _ForwardIter2 __p = __p1;
00134     _ForwardIter1 __current = __first1;
00135     if (++__current == __last1)
00136       return __last1;
00137 
00138     while (*__current == *__p) {
00139       if (++__p == __last2)
00140         return __first1;
00141       if (++__current == __last1)
00142         return __last1;
00143     }
00144 
00145     ++__first1;
00146   }
00147   return __first1;
00148 }
00149 
00150 _STLP_MOVE_TO_PRIV_NAMESPACE
00151 
00152 template <class _RandomAccessIter, class _Integer, class _Tp,
00153           class _BinaryPred, class _Distance>
00154 _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
00155                              _Integer __count, const _Tp& __val, _BinaryPred __pred,
00156                              _Distance*, const random_access_iterator_tag &)
00157 {
00158   _Distance __tailSize = __last - __first;
00159   const _Distance __pattSize = __count;
00160   const _Distance __skipOffset = __pattSize - 1;
00161   _RandomAccessIter __backTrack;
00162   _Distance __remainder, __prevRemainder;
00163 
00164   for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...
00165     //__lookAhead here is always pointing to the last element of next possible match.
00166     __tailSize -= __pattSize;
00167 
00168     while ( !__pred(*__lookAhead, __val) ) { // the skip loop...
00169       if (__tailSize < __pattSize)
00170         return __last;
00171 
00172       __lookAhead += __pattSize;
00173       __tailSize -= __pattSize;
00174     }
00175 
00176     if ( __skipOffset == 0 ) {
00177       return (__lookAhead - __skipOffset); //Success
00178     }
00179 
00180     __remainder = __skipOffset;
00181 
00182     for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
00183       if (--__remainder == 0)
00184         return (__lookAhead - __skipOffset); //Success
00185     }
00186 
00187     if (__remainder > __tailSize)
00188       return __last; //failure
00189 
00190     __lookAhead += __remainder;
00191     __tailSize -= __remainder;
00192 
00193     while ( __pred(*__lookAhead, __val) ) {
00194       __prevRemainder = __remainder;
00195       __backTrack = __lookAhead;
00196 
00197       do {
00198         if (--__remainder == 0)
00199           return (__lookAhead - __skipOffset); //Success
00200       } while (__pred(*--__backTrack, __val));
00201 
00202       //adjust remainder for next comparison
00203       __remainder += __pattSize - __prevRemainder;
00204 
00205       if (__remainder > __tailSize)
00206         return __last; //failure
00207 
00208       __lookAhead += __remainder;
00209       __tailSize -= __remainder;
00210     }
00211 
00212     //__lookAhead here is always pointing to the element of the last mismatch.
00213   }
00214 
00215   return __last; //failure
00216 }
00217 
00218 template <class _ForwardIter, class _Integer, class _Tp,
00219           class _Distance, class _BinaryPred>
00220 _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
00221                         _Integer __count, const _Tp& __val, _BinaryPred __pred,
00222                         _Distance*, const forward_iterator_tag &) {
00223   for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
00224   while (__first != __last) {
00225     _Integer __n = __count - 1;
00226     _ForwardIter __i = __first;
00227     ++__i;
00228     while (__i != __last && __n != 0 && __pred(*__i, __val)) {
00229       ++__i;
00230       --__n;
00231     }
00232     if (__n == 0)
00233       return __first;
00234     else if (__i != __last)
00235       for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
00236     else
00237       break;
00238   }
00239   return __last;
00240 }
00241 
00242 _STLP_MOVE_TO_STD_NAMESPACE
00243 
00244 // search_n.  Search for __count consecutive copies of __val.
00245 template <class _ForwardIter, class _Integer, class _Tp>
00246 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
00247                       _Integer __count, const _Tp& __val) {
00248   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00249   if (__count <= 0)
00250     return __first;
00251   if (__count == 1)
00252     //We use find when __count == 1 to use potential find overload.
00253     return find(__first, __last, __val);
00254   return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
00255                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),
00256                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
00257 }
00258 
00259 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
00260 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
00261                       _Integer __count, const _Tp& __val,
00262                       _BinaryPred __binary_pred) {
00263   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00264   if (__count <= 0)
00265     return __first;
00266   return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,
00267                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),
00268                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
00269 }
00270 
00271 template <class _ForwardIter1, class _ForwardIter2>
00272 _ForwardIter1
00273 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
00274          _ForwardIter2 __first2, _ForwardIter2 __last2) {
00275   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
00276   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
00277   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
00278 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00279                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
00280                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
00281 #else
00282                                forward_iterator_tag(),
00283                                forward_iterator_tag(),
00284 #endif
00285                                _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
00286     );
00287 }
00288 
00289 // unique and unique_copy
00290 _STLP_MOVE_TO_PRIV_NAMESPACE
00291 
00292 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
00293           class _Tp>
00294 _STLP_INLINE_LOOP _OutputIterator
00295 __unique_copy(_InputIterator __first, _InputIterator __last,
00296               _OutputIterator __result,
00297               _BinaryPredicate __binary_pred, _Tp*) {
00298   _Tp __val = *__first;
00299   *__result = __val;
00300   while (++__first != __last)
00301     if (!__binary_pred(__val, *__first)) {
00302       __val = *__first;
00303       *++__result = __val;
00304     }
00305   return ++__result;
00306 }
00307 
00308 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
00309 inline _OutputIter
00310 __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
00311               _BinaryPredicate __binary_pred, const output_iterator_tag &) {
00312   return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
00313 }
00314 
00315 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
00316 _STLP_INLINE_LOOP _ForwardIter
00317 __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
00318               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
00319   *__result = *__first;
00320   while (++__first != __last)
00321     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
00322   return ++__result;
00323 }
00324 
00325 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
00326 template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
00327 inline _BidirectionalIterator
00328 __unique_copy(_InputIterator __first, _InputIterator __last,
00329               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
00330               const bidirectional_iterator_tag &) {
00331   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
00332 }
00333 
00334 template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
00335 inline _RandomAccessIterator
00336 __unique_copy(_InputIterator __first, _InputIterator __last,
00337               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
00338               const random_access_iterator_tag &) {
00339   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
00340 }
00341 #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
00342 
00343 _STLP_MOVE_TO_STD_NAMESPACE
00344 
00345 template <class _InputIter, class _OutputIter>
00346 _OutputIter
00347 unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
00348   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00349   if (__first == __last) return __result;
00350   return _STLP_PRIV __unique_copy(__first, __last, __result,
00351                                   _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
00352                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
00353 }
00354 
00355 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
00356 _OutputIter
00357 unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
00358             _BinaryPredicate __binary_pred) {
00359   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00360   if (__first == __last) return __result;
00361   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
00362                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
00363 }
00364 
00365 // rotate and rotate_copy, and their auxiliary functions
00366 _STLP_MOVE_TO_PRIV_NAMESPACE
00367 
00368 template <class _ForwardIter, class _Distance>
00369 _ForwardIter __rotate_aux(_ForwardIter __first,
00370                           _ForwardIter __middle,
00371                           _ForwardIter __last,
00372                           _Distance*,
00373                           const forward_iterator_tag &) {
00374   if (__first == __middle)
00375     return __last;
00376   if (__last  == __middle)
00377     return __first;
00378 
00379   _ForwardIter __first2 = __middle;
00380   do {
00381     swap(*__first++, *__first2++);
00382     if (__first == __middle)
00383       __middle = __first2;
00384   } while (__first2 != __last);
00385 
00386   _ForwardIter __new_middle = __first;
00387 
00388   __first2 = __middle;
00389 
00390   while (__first2 != __last) {
00391     swap (*__first++, *__first2++);
00392     if (__first == __middle)
00393       __middle = __first2;
00394     else if (__first2 == __last)
00395       __first2 = __middle;
00396   }
00397 
00398   return __new_middle;
00399 }
00400 
00401 template <class _BidirectionalIter, class _Distance>
00402 _BidirectionalIter __rotate_aux(_BidirectionalIter __first,
00403                                 _BidirectionalIter __middle,
00404                                 _BidirectionalIter __last,
00405                                 _Distance*,
00406                                 const bidirectional_iterator_tag &) {
00407   if (__first == __middle)
00408     return __last;
00409   if (__last  == __middle)
00410     return __first;
00411 
00412   __reverse(__first,  __middle, bidirectional_iterator_tag());
00413   __reverse(__middle, __last,   bidirectional_iterator_tag());
00414 
00415   while (__first != __middle && __middle != __last)
00416     swap (*__first++, *--__last);
00417 
00418   if (__first == __middle) {
00419     __reverse(__middle, __last,   bidirectional_iterator_tag());
00420     return __last;
00421   }
00422   else {
00423     __reverse(__first,  __middle, bidirectional_iterator_tag());
00424     return __first;
00425   }
00426 }
00427 
00428 template <class _RandomAccessIter, class _Distance, class _Tp>
00429 _RandomAccessIter __rotate_aux(_RandomAccessIter __first,
00430                                _RandomAccessIter __middle,
00431                                _RandomAccessIter __last,
00432                                _Distance *, _Tp *) {
00433 
00434   _Distance __n = __last   - __first;
00435   _Distance __k = __middle - __first;
00436   _Distance __l = __n - __k;
00437   _RandomAccessIter __result = __first + (__last - __middle);
00438 
00439   if (__k == 0)  /* __first == middle */
00440     return __last;
00441 
00442   if (__k == __l) {
00443     swap_ranges(__first, __middle, __middle);
00444     return __result;
00445   }
00446 
00447   _Distance __d = __gcd(__n, __k);
00448 
00449   for (_Distance __i = 0; __i < __d; __i++) {
00450     _Tp __tmp = *__first;
00451     _RandomAccessIter __p = __first;
00452 
00453     if (__k < __l) {
00454       for (_Distance __j = 0; __j < __l/__d; __j++) {
00455         if (__p > __first + __l) {
00456           *__p = *(__p - __l);
00457           __p -= __l;
00458         }
00459 
00460         *__p = *(__p + __k);
00461         __p += __k;
00462       }
00463     }
00464 
00465     else {
00466       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
00467         if (__p < __last - __k) {
00468           *__p = *(__p + __k);
00469           __p += __k;
00470         }
00471 
00472         *__p = * (__p - __l);
00473         __p -= __l;
00474       }
00475     }
00476 
00477     *__p = __tmp;
00478     ++__first;
00479   }
00480 
00481   return __result;
00482 }
00483 
00484 template <class _RandomAccessIter, class _Distance>
00485 inline _RandomAccessIter
00486 __rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
00487              _Distance * __dis, const random_access_iterator_tag &) {
00488   return __rotate_aux(__first, __middle, __last,
00489                       __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
00490 }
00491 
00492 template <class _ForwardIter>
00493 _ForwardIter
00494 __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
00495   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
00496   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
00497   return __rotate_aux(__first, __middle, __last,
00498                       _STLP_DISTANCE_TYPE(__first, _ForwardIter),
00499                       _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
00500 }
00501 
00502 _STLP_MOVE_TO_STD_NAMESPACE
00503 
00504 template <class _ForwardIter>
00505 void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
00506   _STLP_PRIV __rotate(__first, __middle, __last);
00507 }
00508 
00509 // Return a random number in the range [0, __n).  This function encapsulates
00510 // whether we're using rand (part of the standard C library) or lrand48
00511 // (not standard, but a much better choice whenever it's available).
00512 _STLP_MOVE_TO_PRIV_NAMESPACE
00513 
00514 template <class _Distance>
00515 inline _Distance __random_number(_Distance __n) {
00516 #ifdef _STLP_NO_DRAND48
00517   return rand() % __n;
00518 #else
00519   return lrand48() % __n;
00520 #endif
00521 }
00522 
00523 _STLP_MOVE_TO_STD_NAMESPACE
00524 
00525 template <class _RandomAccessIter>
00526 void random_shuffle(_RandomAccessIter __first,
00527                     _RandomAccessIter __last) {
00528   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00529   if (__first == __last) return;
00530   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
00531     iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
00532 }
00533 
00534 template <class _RandomAccessIter, class _RandomNumberGenerator>
00535 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
00536                     _RandomNumberGenerator &__rand) {
00537   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00538   if (__first == __last) return;
00539   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
00540     iter_swap(__i, __first + __rand((__i - __first) + 1));
00541 }
00542 
00543 #if !defined (_STLP_NO_EXTENSIONS)
00544 // random_sample and random_sample_n (extensions, not part of the standard).
00545 template <class _ForwardIter, class _OutputIter, class _Distance>
00546 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
00547                             _OutputIter __out_ite, const _Distance __n) {
00548   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00549   _Distance __remaining = distance(__first, __last);
00550   _Distance __m = (min) (__n, __remaining);
00551 
00552   while (__m > 0) {
00553     if (_STLP_PRIV __random_number(__remaining) < __m) {
00554       *__out_ite = *__first;
00555       ++__out_ite;
00556       --__m;
00557     }
00558 
00559     --__remaining;
00560     ++__first;
00561   }
00562   return __out_ite;
00563 }
00564 
00565 
00566 template <class _ForwardIter, class _OutputIter, class _Distance,
00567           class _RandomNumberGenerator>
00568 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
00569                             _OutputIter __out_ite, const _Distance __n,
00570                             _RandomNumberGenerator& __rand) {
00571   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00572   _Distance __remaining = distance(__first, __last);
00573   _Distance __m = (min) (__n, __remaining);
00574 
00575   while (__m > 0) {
00576     if (__rand(__remaining) < __m) {
00577       *__out_ite = *__first;
00578       ++__out_ite;
00579       --__m;
00580     }
00581 
00582     --__remaining;
00583     ++__first;
00584   }
00585   return __out_ite;
00586 }
00587 
00588 _STLP_MOVE_TO_PRIV_NAMESPACE
00589 
00590 template <class _InputIter, class _RandomAccessIter, class _Distance>
00591 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
00592                                   _RandomAccessIter __out_ite,
00593                                   const _Distance __n) {
00594   _Distance __m = 0;
00595   _Distance __t = __n;
00596   for ( ; __first != __last && __m < __n; ++__m, ++__first)
00597     __out_ite[__m] = *__first;
00598 
00599   while (__first != __last) {
00600     ++__t;
00601     _Distance __M = __random_number(__t);
00602     if (__M < __n)
00603       __out_ite[__M] = *__first;
00604     ++__first;
00605   }
00606 
00607   return __out_ite + __m;
00608 }
00609 
00610 template <class _InputIter, class _RandomAccessIter,
00611           class _RandomNumberGenerator, class _Distance>
00612 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
00613                                   _RandomAccessIter __out_ite,
00614                                   _RandomNumberGenerator& __rand,
00615                                   const _Distance __n) {
00616   _Distance __m = 0;
00617   _Distance __t = __n;
00618   for ( ; __first != __last && __m < __n; ++__m, ++__first)
00619     __out_ite[__m] = *__first;
00620 
00621   while (__first != __last) {
00622     ++__t;
00623     _Distance __M = __rand(__t);
00624     if (__M < __n)
00625       __out_ite[__M] = *__first;
00626     ++__first;
00627   }
00628 
00629   return __out_ite + __m;
00630 }
00631 
00632 _STLP_MOVE_TO_STD_NAMESPACE
00633 
00634 template <class _InputIter, class _RandomAccessIter>
00635 _RandomAccessIter
00636 random_sample(_InputIter __first, _InputIter __last,
00637               _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
00638   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00639   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
00640   return _STLP_PRIV __random_sample(__first, __last,
00641                                     __out_first, __out_last - __out_first);
00642 }
00643 
00644 template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
00645 _RandomAccessIter
00646 random_sample(_InputIter __first, _InputIter __last,
00647               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
00648               _RandomNumberGenerator& __rand) {
00649   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00650   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
00651   return _STLP_PRIV __random_sample(__first, __last,
00652                                     __out_first, __rand,
00653                                     __out_last - __out_first);
00654 }
00655 
00656 #endif /* _STLP_NO_EXTENSIONS */
00657 
00658 // partition, stable_partition, and their auxiliary functions
00659 _STLP_MOVE_TO_PRIV_NAMESPACE
00660 
00661 template <class _ForwardIter, class _Predicate>
00662 _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
00663                                            _ForwardIter __last,
00664                                            _Predicate   __pred,
00665                                            const forward_iterator_tag &) {
00666   if (__first == __last) return __first;
00667 
00668   while (__pred(*__first))
00669     if (++__first == __last) return __first;
00670 
00671   _ForwardIter __next = __first;
00672 
00673   while (++__next != __last) {
00674     if (__pred(*__next)) {
00675       swap(*__first, *__next);
00676       ++__first;
00677     }
00678   }
00679   return __first;
00680 }
00681 
00682 template <class _BidirectionalIter, class _Predicate>
00683 _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
00684                                                  _BidirectionalIter __last,
00685                                                  _Predicate __pred,
00686                                                  const bidirectional_iterator_tag &) {
00687   for (;;) {
00688     for (;;) {
00689       if (__first == __last)
00690         return __first;
00691       else if (__pred(*__first))
00692         ++__first;
00693       else
00694         break;
00695     }
00696     --__last;
00697     for (;;) {
00698       if (__first == __last)
00699         return __first;
00700       else if (!__pred(*__last))
00701         --__last;
00702       else
00703         break;
00704     }
00705     iter_swap(__first, __last);
00706     ++__first;
00707   }
00708 }
00709 
00710 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
00711 template <class _BidirectionalIter, class _Predicate>
00712 inline
00713 _BidirectionalIter __partition(_BidirectionalIter __first,
00714                                _BidirectionalIter __last,
00715                                _Predicate __pred,
00716                                const random_access_iterator_tag &) {
00717   return __partition(__first, __last, __pred, bidirectional_iterator_tag());
00718 }
00719 #endif
00720 
00721 _STLP_MOVE_TO_STD_NAMESPACE
00722 
00723 template <class _ForwardIter, class _Predicate>
00724 _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {
00725   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00726   return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
00727 }
00728 
00729 
00730 /* __pred_of_first: false if we know that __pred(*__first) is false,
00731  *                  true when we don't know the result of __pred(*__first).
00732  * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
00733  *                            false when we don't know the result of __pred(*--__last).
00734  */
00735 _STLP_MOVE_TO_PRIV_NAMESPACE
00736 
00737 template <class _ForwardIter, class _Predicate, class _Distance>
00738 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
00739                                         _ForwardIter __last,
00740                                         _Predicate __pred, _Distance __len,
00741                                         bool __pred_of_first, bool __pred_of_before_last) {
00742   if (__len == 1)
00743     return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
00744   _ForwardIter __middle = __first;
00745   _Distance __half_len = __len / 2;
00746   advance(__middle, __half_len);
00747   return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
00748                   __middle,
00749                   __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
00750 }
00751 
00752 template <class _ForwardIter, class _Pointer, class _Predicate,
00753           class _Distance>
00754 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
00755                                          _ForwardIter __last,
00756                                          _Predicate __pred, _Distance __len,
00757                                          _Pointer __buffer, _Distance __buffer_size,
00758                                          bool __pred_of_first, bool __pred_of_before_last) {
00759   if (__len <= __buffer_size) {
00760     _ForwardIter __result1 = __first;
00761     _Pointer __result2 = __buffer;
00762     if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
00763       *__result2 = *__first;
00764       ++__result2; ++__first; --__len;
00765     }
00766     for (; __first != __last ; ++__first, --__len) {
00767       if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
00768           ((__len != 1) && __pred(*__first))){
00769         *__result1 = *__first;
00770         ++__result1;
00771       }
00772       else {
00773         *__result2 = *__first;
00774         ++__result2;
00775       }
00776     }
00777     copy(__buffer, __result2, __result1);
00778     return __result1;
00779   }
00780   else {
00781     _ForwardIter __middle = __first;
00782     _Distance __half_len = __len / 2;
00783     advance(__middle, __half_len);
00784     return __rotate(__stable_partition_adaptive(
00785                           __first, __middle, __pred,
00786                           __half_len, __buffer, __buffer_size,
00787                           __pred_of_first, false),
00788                     __middle,
00789                     __stable_partition_adaptive(
00790                           __middle, __last, __pred,
00791                           __len - __half_len, __buffer, __buffer_size,
00792                           true, __pred_of_before_last));
00793   }
00794 }
00795 
00796 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
00797 inline _ForwardIter
00798 __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
00799                            _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
00800   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
00801   _STLP_MPWFIX_TRY    //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
00802   return (__buf.size() > 0) ?
00803     __stable_partition_adaptive(__first, __last, __pred,
00804                                 _Distance(__buf.requested_size()),
00805                                 __buf.begin(), __buf.size(),
00806                                 false, __pred_of_before_last)  :
00807     __inplace_stable_partition(__first, __last, __pred,
00808                                _Distance(__buf.requested_size()),
00809                                false, __pred_of_before_last);
00810   _STLP_MPWFIX_CATCH  //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
00811 }
00812 
00813 template <class _ForwardIter, class _Predicate>
00814 _ForwardIter
00815 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
00816                        const forward_iterator_tag &) {
00817   return __stable_partition_aux_aux(__first, __last, __pred,
00818                                     _STLP_VALUE_TYPE(__first, _ForwardIter),
00819                                     _STLP_DISTANCE_TYPE(__first, _ForwardIter));
00820 }
00821 
00822 template <class _BidirectIter, class _Predicate>
00823 _BidirectIter
00824 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
00825                        const bidirectional_iterator_tag &) {
00826   for (--__last;;) {
00827     if (__first == __last)
00828       return __first;
00829     else if (!__pred(*__last))
00830       --__last;
00831     else
00832       break;
00833   }
00834   ++__last;
00835   //Here we know that __pred(*--__last) is true
00836   return __stable_partition_aux_aux(__first, __last, __pred,
00837                                     _STLP_VALUE_TYPE(__first, _BidirectIter),
00838                                     _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);
00839 }
00840 
00841 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
00842 template <class _BidirectIter, class _Predicate>
00843 _BidirectIter
00844 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
00845                        const random_access_iterator_tag &) {
00846   return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());
00847 }
00848 #endif
00849 
00850 _STLP_MOVE_TO_STD_NAMESPACE
00851 
00852 template <class _ForwardIter, class _Predicate>
00853 _ForwardIter
00854 stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
00855   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00856   for (;;) {
00857     if (__first == __last)
00858       return __first;
00859     else if (__pred(*__first))
00860       ++__first;
00861     else
00862       break;
00863   }
00864   return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,
00865                                            _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
00866 }
00867 
00868 _STLP_MOVE_TO_PRIV_NAMESPACE
00869 
00870 template <class _RandomAccessIter, class _Tp, class _Compare>
00871 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
00872                                         _RandomAccessIter __last,
00873                                         _Tp __pivot, _Compare __comp) {
00874   for (;;) {
00875     while (__comp(*__first, __pivot)) {
00876       _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00877       ++__first;
00878     }
00879     --__last;
00880     while (__comp(__pivot, *__last)) {
00881       _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00882       --__last;
00883     }
00884     if (!(__first < __last))
00885       return __first;
00886     iter_swap(__first, __last);
00887     ++__first;
00888   }
00889 }
00890 
00891 // sort() and its auxiliary functions.
00892 #define __stl_threshold  16
00893 
00894 template <class _RandomAccessIter, class _Tp, class _Compare>
00895 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
00896                                _Compare __comp) {
00897   _RandomAccessIter __next = __last;
00898   --__next;
00899   while (__comp(__val, *__next)) {
00900     _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00901     *__last = *__next;
00902     __last = __next;
00903     --__next;
00904   }
00905   *__last = __val;
00906 }
00907 
00908 template <class _RandomAccessIter, class _Tp, class _Compare>
00909 inline void __linear_insert(_RandomAccessIter __first,
00910                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {
00911   //*TY 12/26/1998 - added __val as a paramter
00912   //  _Tp __val = *__last;        //*TY 12/26/1998 - __val supplied by caller
00913   if (__comp(__val, *__first)) {
00914     _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
00915     copy_backward(__first, __last, __last + 1);
00916     *__first = __val;
00917   }
00918   else
00919     __unguarded_linear_insert(__last, __val, __comp);
00920 }
00921 
00922 template <class _RandomAccessIter, class _Tp, class _Compare>
00923 void __insertion_sort(_RandomAccessIter __first,
00924                       _RandomAccessIter __last,
00925                       _Tp *, _Compare __comp) {
00926   if (__first == __last) return;
00927   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
00928     __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp);  //*TY 12/26/1998 - supply *__i as __val
00929 }
00930 
00931 template <class _RandomAccessIter, class _Tp, class _Compare>
00932 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
00933                                     _RandomAccessIter __last,
00934                                     _Tp*, _Compare __comp) {
00935   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
00936     __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
00937 }
00938 
00939 template <class _RandomAccessIter, class _Compare>
00940 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
00941                                        _RandomAccessIter __last,
00942                                        _Compare __comp) {
00943   __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
00944 }
00945 
00946 template <class _RandomAccessIter, class _Compare>
00947 void __final_insertion_sort(_RandomAccessIter __first,
00948                             _RandomAccessIter __last, _Compare __comp) {
00949   if (__last - __first > __stl_threshold) {
00950     __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
00951     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
00952   }
00953   else
00954     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
00955 }
00956 
00957 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
00958 void __introsort_loop(_RandomAccessIter __first,
00959                       _RandomAccessIter __last, _Tp*,
00960                       _Size __depth_limit, _Compare __comp) {
00961   while (__last - __first > __stl_threshold) {
00962     if (__depth_limit == 0) {
00963       partial_sort(__first, __last, __last, __comp);
00964       return;
00965     }
00966     --__depth_limit;
00967     _RandomAccessIter __cut =
00968       __unguarded_partition(__first, __last,
00969                             _Tp(__median(*__first,
00970                                          *(__first + (__last - __first)/2),
00971                                          *(__last - 1), __comp)),
00972        __comp);
00973     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
00974     __last = __cut;
00975   }
00976 }
00977 
00978 _STLP_MOVE_TO_STD_NAMESPACE
00979 
00980 template <class _RandomAccessIter>
00981 void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
00982   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00983   if (__first != __last) {
00984     _STLP_PRIV __introsort_loop(__first, __last,
00985                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),
00986                                 _STLP_PRIV __lg(__last - __first) * 2,
00987                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
00988     _STLP_PRIV __final_insertion_sort(__first, __last,
00989                                       _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
00990   }
00991 }
00992 
00993 template <class _RandomAccessIter, class _Compare>
00994 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
00995   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
00996   if (__first != __last) {
00997     _STLP_PRIV __introsort_loop(__first, __last,
00998                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),
00999                                 _STLP_PRIV __lg(__last - __first) * 2, __comp);
01000     _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
01001   }
01002 }
01003 
01004 // stable_sort() and its auxiliary functions.
01005 _STLP_MOVE_TO_PRIV_NAMESPACE
01006 
01007 template <class _RandomAccessIter, class _Compare>
01008 void __inplace_stable_sort(_RandomAccessIter __first,
01009                            _RandomAccessIter __last, _Compare __comp) {
01010   if (__last - __first < 15) {
01011     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
01012     return;
01013   }
01014   _RandomAccessIter __middle = __first + (__last - __first) / 2;
01015   __inplace_stable_sort(__first, __middle, __comp);
01016   __inplace_stable_sort(__middle, __last, __comp);
01017   __merge_without_buffer(__first, __middle, __last,
01018                          __middle - __first,
01019                          __last - __middle,
01020                          __comp);
01021 }
01022 
01023 template <class _RandomAccessIter1, class _RandomAccessIter2,
01024           class _Distance, class _Compare>
01025 void __merge_sort_loop(_RandomAccessIter1 __first,
01026                        _RandomAccessIter1 __last,
01027                        _RandomAccessIter2 __result, _Distance __step_size,
01028                        _Compare __comp) {
01029   _Distance __two_step = 2 * __step_size;
01030 
01031   while (__last - __first >= __two_step) {
01032     __result = merge(__first, __first + __step_size,
01033                      __first + __step_size, __first + __two_step,
01034                      __result,
01035                      __comp);
01036     __first += __two_step;
01037   }
01038   __step_size = (min) (_Distance(__last - __first), __step_size);
01039 
01040   merge(__first, __first + __step_size,
01041         __first + __step_size, __last,
01042         __result,
01043         __comp);
01044 }
01045 
01046 const int __stl_chunk_size = 7;
01047 
01048 template <class _RandomAccessIter, class _Distance, class _Compare>
01049 void __chunk_insertion_sort(_RandomAccessIter __first,
01050                             _RandomAccessIter __last,
01051                             _Distance __chunk_size, _Compare __comp) {
01052   while (__last - __first >= __chunk_size) {
01053     __insertion_sort(__first, __first + __chunk_size,
01054                      _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
01055     __first += __chunk_size;
01056   }
01057   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
01058 }
01059 
01060 template <class _RandomAccessIter, class _Pointer, class _Distance,
01061           class _Compare>
01062 void __merge_sort_with_buffer(_RandomAccessIter __first,
01063                               _RandomAccessIter __last, _Pointer __buffer,
01064                               _Distance*, _Compare __comp) {
01065   _Distance __len = __last - __first;
01066   _Pointer __buffer_last = __buffer + __len;
01067 
01068   _Distance __step_size = __stl_chunk_size;
01069   __chunk_insertion_sort(__first, __last, __step_size, __comp);
01070 
01071   while (__step_size < __len) {
01072     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
01073     __step_size *= 2;
01074     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
01075     __step_size *= 2;
01076   }
01077 }
01078 
01079 template <class _BidirectionalIter1, class _BidirectionalIter2,
01080           class _Distance>
01081 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
01082                                       _BidirectionalIter1 __middle,
01083                                       _BidirectionalIter1 __last,
01084                                       _Distance __len1, _Distance __len2,
01085                                       _BidirectionalIter2 __buffer,
01086                                       _Distance __buffer_size) {
01087   if (__len1 > __len2 && __len2 <= __buffer_size) {
01088     _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
01089     copy_backward(__first, __middle, __last);
01090     return copy(__buffer, __buffer_end, __first);
01091   }
01092   else if (__len1 <= __buffer_size) {
01093     _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
01094     copy(__middle, __last, __first);
01095     return copy_backward(__buffer, __buffer_end, __last);
01096   }
01097   else
01098     return __rotate(__first, __middle, __last);
01099 }
01100 
01101 template <class _BidirectionalIter, class _Distance, class _Pointer,
01102           class _Compare>
01103 void __merge_adaptive(_BidirectionalIter __first,
01104                       _BidirectionalIter __middle,
01105                       _BidirectionalIter __last,
01106                       _Distance __len1, _Distance __len2,
01107                       _Pointer __buffer, _Distance __buffer_size,
01108                       _Compare __comp) {
01109   if (__len1 <= __len2 && __len1 <= __buffer_size) {
01110     _Pointer __buffer_end = copy(__first, __middle, __buffer);
01111     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
01112   }
01113   else if (__len2 <= __buffer_size) {
01114     _Pointer __buffer_end = copy(__middle, __last, __buffer);
01115     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
01116                      __comp);
01117   }
01118   else {
01119     _BidirectionalIter __first_cut = __first;
01120     _BidirectionalIter __second_cut = __middle;
01121     _Distance __len11 = 0;
01122     _Distance __len22 = 0;
01123     if (__len1 > __len2) {
01124       __len11 = __len1 / 2;
01125       advance(__first_cut, __len11);
01126       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
01127       __len22 += distance(__middle, __second_cut);
01128     }
01129     else {
01130       __len22 = __len2 / 2;
01131       advance(__second_cut, __len22);
01132       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
01133       __len11 += distance(__first, __first_cut);
01134     }
01135     _BidirectionalIter __new_middle =
01136       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
01137                         __len22, __buffer, __buffer_size);
01138     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
01139                      __len22, __buffer, __buffer_size, __comp);
01140     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
01141                      __len2 - __len22, __buffer, __buffer_size, __comp);
01142   }
01143 }
01144 
01145 template <class _RandomAccessIter, class _Pointer, class _Distance,
01146           class _Compare>
01147 void __stable_sort_adaptive(_RandomAccessIter __first,
01148                             _RandomAccessIter __last, _Pointer __buffer,
01149                             _Distance __buffer_size, _Compare __comp) {
01150   _Distance __len = (__last - __first + 1) / 2;
01151   _RandomAccessIter __middle = __first + __len;
01152   if (__len > __buffer_size) {
01153     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
01154                            __comp);
01155     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
01156                            __comp);
01157   }
01158   else {
01159     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
01160                                __comp);
01161     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
01162                                __comp);
01163   }
01164   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
01165                    _Distance(__last - __middle), __buffer, __buffer_size,
01166                    __comp);
01167 }
01168 
01169 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
01170 void __stable_sort_aux(_RandomAccessIter __first,
01171                        _RandomAccessIter __last, _Tp*, _Distance*,
01172                        _Compare __comp) {
01173   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
01174   if (buf.begin() == 0)
01175     __inplace_stable_sort(__first, __last, __comp);
01176   else
01177     __stable_sort_adaptive(__first, __last, buf.begin(),
01178                            _Distance(buf.size()),
01179                            __comp);
01180 }
01181 
01182 _STLP_MOVE_TO_STD_NAMESPACE
01183 
01184 template <class _RandomAccessIter>
01185 void stable_sort(_RandomAccessIter __first,
01186                  _RandomAccessIter __last) {
01187   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01188   _STLP_PRIV __stable_sort_aux(__first, __last,
01189                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
01190                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
01191                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
01192 }
01193 
01194 template <class _RandomAccessIter, class _Compare>
01195 void stable_sort(_RandomAccessIter __first,
01196                  _RandomAccessIter __last, _Compare __comp) {
01197   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01198   _STLP_PRIV __stable_sort_aux(__first, __last,
01199                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
01200                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
01201                                __comp);
01202 }
01203 
01204 // partial_sort, partial_sort_copy, and auxiliary functions.
01205 _STLP_MOVE_TO_PRIV_NAMESPACE
01206 
01207 template <class _RandomAccessIter, class _Tp, class _Compare>
01208 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
01209                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
01210   make_heap(__first, __middle, __comp);
01211   for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
01212     if (__comp(*__i, *__first)) {
01213       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01214       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
01215                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
01216     }
01217   }
01218   sort_heap(__first, __middle, __comp);
01219 }
01220 
01221 _STLP_MOVE_TO_STD_NAMESPACE
01222 
01223 template <class _RandomAccessIter>
01224 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
01225                   _RandomAccessIter __last) {
01226   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
01227   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
01228   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
01229                             _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
01230 }
01231 
01232 template <class _RandomAccessIter, class _Compare>
01233 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
01234                   _RandomAccessIter __last, _Compare __comp) {
01235   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
01236   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
01237   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
01238 }
01239 
01240 _STLP_MOVE_TO_PRIV_NAMESPACE
01241 
01242 template <class _InputIter, class _RandomAccessIter, class _Compare,
01243           class _Distance, class _Tp>
01244 _RandomAccessIter __partial_sort_copy(_InputIter __first,
01245                                       _InputIter __last,
01246                                       _RandomAccessIter __result_first,
01247                                       _RandomAccessIter __result_last,
01248                                       _Compare __comp, _Distance*, _Tp*) {
01249   if (__result_first == __result_last) return __result_last;
01250   _RandomAccessIter __result_real_last = __result_first;
01251   while(__first != __last && __result_real_last != __result_last) {
01252     *__result_real_last = *__first;
01253     ++__result_real_last;
01254     ++__first;
01255   }
01256   make_heap(__result_first, __result_real_last, __comp);
01257   while (__first != __last) {
01258     if (__comp(*__first, *__result_first)) {
01259       _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01260       __adjust_heap(__result_first, _Distance(0),
01261                     _Distance(__result_real_last - __result_first),
01262                     _Tp(*__first),
01263                     __comp);
01264     }
01265     ++__first;
01266   }
01267   sort_heap(__result_first, __result_real_last, __comp);
01268   return __result_real_last;
01269 }
01270 
01271 _STLP_MOVE_TO_STD_NAMESPACE
01272 
01273 template <class _InputIter, class _RandomAccessIter>
01274 _RandomAccessIter
01275 partial_sort_copy(_InputIter __first, _InputIter __last,
01276                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
01277   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01278   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
01279   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
01280                                         _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
01281                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
01282                                         _STLP_VALUE_TYPE(__first, _InputIter));
01283 }
01284 
01285 template <class _InputIter, class _RandomAccessIter, class _Compare>
01286 _RandomAccessIter
01287 partial_sort_copy(_InputIter __first, _InputIter __last,
01288                   _RandomAccessIter __result_first,
01289                   _RandomAccessIter __result_last, _Compare __comp) {
01290   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01291   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
01292   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
01293                                         __comp,
01294                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
01295                                         _STLP_VALUE_TYPE(__first, _InputIter));
01296 }
01297 
01298 // nth_element() and its auxiliary functions.
01299 _STLP_MOVE_TO_PRIV_NAMESPACE
01300 
01301 template <class _RandomAccessIter, class _Tp, class _Compare>
01302 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
01303                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
01304   while (__last - __first > 3) {
01305     _RandomAccessIter __cut =
01306       __unguarded_partition(__first, __last,
01307                             _Tp(__median(*__first,
01308                                          *(__first + (__last - __first)/2),
01309                                          *(__last - 1),
01310                                          __comp)),
01311                             __comp);
01312     if (__cut <= __nth)
01313       __first = __cut;
01314     else
01315       __last = __cut;
01316   }
01317   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
01318 }
01319 
01320 _STLP_MOVE_TO_STD_NAMESPACE
01321 
01322 template <class _RandomAccessIter>
01323 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
01324                  _RandomAccessIter __last) {
01325   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
01326   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
01327   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
01328                            _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
01329 }
01330 
01331 template <class _RandomAccessIter, class _Compare>
01332 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
01333                  _RandomAccessIter __last, _Compare __comp) {
01334   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
01335   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
01336   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
01337 }
01338 
01339 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
01340 _STLP_MOVE_TO_PRIV_NAMESPACE
01341 
01342 template <class _ForwardIter, class _Tp,
01343           class _Compare1, class _Compare2, class _Distance>
01344 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
01345                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
01346   _Distance __len = distance(__first, __last);
01347   _Distance __half;
01348 
01349   while (__len > 0) {
01350     __half = __len >> 1;
01351     _ForwardIter __middle = __first;
01352     advance(__middle, __half);
01353     if (__comp2(__val, *__middle)) {
01354       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01355       __len = __half;
01356     }
01357     else {
01358       __first = __middle;
01359       ++__first;
01360       __len = __len - __half - 1;
01361     }
01362   }
01363   return __first;
01364 }
01365 
01366 template <class _ForwardIter, class _Tp,
01367           class _Compare1, class _Compare2, class _Distance>
01368 pair<_ForwardIter, _ForwardIter>
01369 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
01370               _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
01371   _Distance __len = distance(__first, __last);
01372   _Distance __half;
01373 
01374   while (__len > 0) {
01375     __half = __len >> 1;
01376     _ForwardIter __middle = __first;
01377     advance(__middle, __half);
01378     if (__comp1(*__middle, __val)) {
01379       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01380       __first = __middle;
01381       ++__first;
01382       __len = __len - __half - 1;
01383     }
01384     else if (__comp2(__val, *__middle)) {
01385       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01386       __len = __half;
01387     }
01388     else {
01389       _ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
01390       //Small optim: If lower_bound haven't found an equivalent value
01391       //there is no need to call upper_bound.
01392       if (__comp1(*__left, __val)) {
01393         _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01394         return pair<_ForwardIter, _ForwardIter>(__left, __left);
01395       }
01396       advance(__first, __len);
01397       _ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
01398       return pair<_ForwardIter, _ForwardIter>(__left, __right);
01399     }
01400   }
01401   return pair<_ForwardIter, _ForwardIter>(__first, __first);
01402 }
01403 
01404 _STLP_MOVE_TO_STD_NAMESPACE
01405 
01406 template <class _InputIter1, class _InputIter2, class _OutputIter>
01407 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
01408                   _InputIter2 __first2, _InputIter2 __last2,
01409                   _OutputIter __result) {
01410   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
01411   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
01412   while (__first1 != __last1 && __first2 != __last2) {
01413     if (*__first2 < *__first1) {
01414       *__result = *__first2;
01415       ++__first2;
01416     }
01417     else {
01418       *__result = *__first1;
01419       ++__first1;
01420     }
01421     ++__result;
01422   }
01423   return copy(__first2, __last2, copy(__first1, __last1, __result));
01424 }
01425 
01426 template <class _InputIter1, class _InputIter2, class _OutputIter,
01427           class _Compare>
01428 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
01429                   _InputIter2 __first2, _InputIter2 __last2,
01430                   _OutputIter __result, _Compare __comp) {
01431   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
01432   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
01433   while (__first1 != __last1 && __first2 != __last2) {
01434     if (__comp(*__first2, *__first1)) {
01435       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01436       *__result = *__first2;
01437       ++__first2;
01438     }
01439     else {
01440       *__result = *__first1;
01441       ++__first1;
01442     }
01443     ++__result;
01444   }
01445   return copy(__first2, __last2, copy(__first1, __last1, __result));
01446 }
01447 
01448 _STLP_MOVE_TO_PRIV_NAMESPACE
01449 
01450 template <class _BidirectionalIter, class _Distance, class _Compare>
01451 void __merge_without_buffer(_BidirectionalIter __first,
01452                             _BidirectionalIter __middle,
01453                             _BidirectionalIter __last,
01454                             _Distance __len1, _Distance __len2,
01455                             _Compare __comp) {
01456   if (__len1 == 0 || __len2 == 0)
01457     return;
01458   if (__len1 + __len2 == 2) {
01459     if (__comp(*__middle, *__first)) {
01460       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01461       iter_swap(__first, __middle);
01462     }
01463     return;
01464   }
01465   _BidirectionalIter __first_cut = __first;
01466   _BidirectionalIter __second_cut = __middle;
01467   _Distance __len11 = 0;
01468   _Distance __len22 = 0;
01469   if (__len1 > __len2) {
01470     __len11 = __len1 / 2;
01471     advance(__first_cut, __len11);
01472     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
01473     __len22 += distance(__middle, __second_cut);
01474   }
01475   else {
01476     __len22 = __len2 / 2;
01477     advance(__second_cut, __len22);
01478     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
01479     __len11 +=distance(__first, __first_cut);
01480   }
01481   _BidirectionalIter __new_middle
01482     = __rotate(__first_cut, __middle, __second_cut);
01483   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
01484                          __comp);
01485   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
01486                          __len2 - __len22, __comp);
01487 }
01488 
01489 template <class _BidirectionalIter1, class _BidirectionalIter2,
01490           class _BidirectionalIter3, class _Compare>
01491 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
01492                                      _BidirectionalIter1 __last1,
01493                                      _BidirectionalIter2 __first2,
01494                                      _BidirectionalIter2 __last2,
01495                                      _BidirectionalIter3 __result,
01496                                      _Compare __comp) {
01497   if (__first1 == __last1)
01498     return copy_backward(__first2, __last2, __result);
01499   if (__first2 == __last2)
01500     return copy_backward(__first1, __last1, __result);
01501   --__last1;
01502   --__last2;
01503   for (;;) {
01504     if (__comp(*__last2, *__last1)) {
01505       _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01506       *--__result = *__last1;
01507       if (__first1 == __last1)
01508         return copy_backward(__first2, ++__last2, __result);
01509       --__last1;
01510     }
01511     else {
01512       *--__result = *__last2;
01513       if (__first2 == __last2)
01514         return copy_backward(__first1, ++__last1, __result);
01515       --__last2;
01516     }
01517   }
01518 }
01519 
01520 template <class _BidirectionalIter, class _Tp,
01521           class _Distance, class _Compare>
01522 inline void __inplace_merge_aux(_BidirectionalIter __first,
01523                                 _BidirectionalIter __middle,
01524                                 _BidirectionalIter __last, _Tp*, _Distance*,
01525                                 _Compare __comp) {
01526   _Distance __len1 = distance(__first, __middle);
01527   _Distance __len2 = distance(__middle, __last);
01528 
01529   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
01530   if (__buf.begin() == 0)
01531     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
01532   else
01533     __merge_adaptive(__first, __middle, __last, __len1, __len2,
01534                      __buf.begin(), _Distance(__buf.size()),
01535                      __comp);
01536 }
01537 
01538 _STLP_MOVE_TO_STD_NAMESPACE
01539 
01540 template <class _BidirectionalIter>
01541 void inplace_merge(_BidirectionalIter __first,
01542                    _BidirectionalIter __middle,
01543                    _BidirectionalIter __last) {
01544   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
01545   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
01546   if (__first == __middle || __middle == __last)
01547     return;
01548   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
01549                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
01550                                  _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
01551 }
01552 
01553 template <class _BidirectionalIter, class _Compare>
01554 void inplace_merge(_BidirectionalIter __first,
01555                    _BidirectionalIter __middle,
01556                    _BidirectionalIter __last, _Compare __comp) {
01557   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
01558   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
01559   if (__first == __middle || __middle == __last)
01560     return;
01561   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
01562                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
01563                                  __comp);
01564 }
01565 
01566 _STLP_MOVE_TO_PRIV_NAMESPACE
01567 
01568 template <class _InputIter1, class _InputIter2, class _Compare>
01569 bool __includes(_InputIter1 __first1, _InputIter1 __last1,
01570                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
01571   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
01572   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
01573   while (__first1 != __last1 && __first2 != __last2)
01574     if (__comp(*__first2, *__first1)) {
01575       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01576       return false;
01577     }
01578     else if (__comp(*__first1, *__first2))
01579       ++__first1;
01580     else
01581       ++__first1, ++__first2;
01582 
01583   return __first2 == __last2;
01584 }
01585 
01586 _STLP_MOVE_TO_STD_NAMESPACE
01587 
01588 template <class _InputIter1, class _InputIter2, class _Compare>
01589 bool includes(_InputIter1 __first1, _InputIter1 __last1,
01590               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
01591   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
01592 }
01593 
01594 template <class _InputIter1, class _InputIter2>
01595 bool includes(_InputIter1 __first1, _InputIter1 __last1,
01596               _InputIter2 __first2, _InputIter2 __last2) {
01597   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
01598                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
01599 }
01600 
01601 _STLP_MOVE_TO_PRIV_NAMESPACE
01602 
01603 template <class _InputIter1, class _InputIter2, class _OutputIter,
01604           class _Compare>
01605 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
01606                         _InputIter2 __first2, _InputIter2 __last2,
01607                         _OutputIter __result, _Compare __comp) {
01608   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
01609   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
01610   while (__first1 != __last1 && __first2 != __last2) {
01611     if (__comp(*__first1, *__first2)) {
01612       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01613       *__result = *__first1;
01614       ++__first1;
01615     }
01616     else if (__comp(*__first2, *__first1)) {
01617       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01618       *__result = *__first2;
01619       ++__first2;
01620     }
01621     else {
01622       *__result = *__first1;
01623       ++__first1;
01624       ++__first2;
01625     }
01626     ++__result;
01627   }
01628   return copy(__first2, __last2, copy(__first1, __last1, __result));
01629 }
01630 
01631 _STLP_MOVE_TO_STD_NAMESPACE
01632 
01633 template <class _InputIter1, class _InputIter2, class _OutputIter>
01634 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
01635                       _InputIter2 __first2, _InputIter2 __last2,
01636                       _OutputIter __result) {
01637   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
01638                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
01639 }
01640 
01641 template <class _InputIter1, class _InputIter2, class _OutputIter,
01642           class _Compare>
01643 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
01644                       _InputIter2 __first2, _InputIter2 __last2,
01645                       _OutputIter __result, _Compare __comp) {
01646   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
01647 }
01648 
01649 _STLP_MOVE_TO_PRIV_NAMESPACE
01650 
01651 template <class _InputIter1, class _InputIter2, class _OutputIter,
01652           class _Compare>
01653 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
01654                                _InputIter2 __first2, _InputIter2 __last2,
01655                                _OutputIter __result, _Compare __comp) {
01656   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
01657   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
01658   while (__first1 != __last1 && __first2 != __last2)
01659     if (__comp(*__first1, *__first2)) {
01660       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01661       ++__first1;
01662     }
01663     else if (__comp(*__first2, *__first1))
01664       ++__first2;
01665     else {
01666       *__result = *__first1;
01667       ++__first1;
01668       ++__first2;
01669       ++__result;
01670     }
01671   return __result;
01672 }
01673 
01674 _STLP_MOVE_TO_STD_NAMESPACE
01675 
01676 template <class _InputIter1, class _InputIter2, class _OutputIter>
01677 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
01678                              _InputIter2 __first2, _InputIter2 __last2,
01679                              _OutputIter __result) {
01680   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
01681                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
01682 }
01683 
01684 template <class _InputIter1, class _InputIter2, class _OutputIter,
01685           class _Compare>
01686 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
01687                              _InputIter2 __first2, _InputIter2 __last2,
01688                              _OutputIter __result, _Compare __comp) {
01689   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
01690 }
01691 
01692 _STLP_MOVE_TO_PRIV_NAMESPACE
01693 
01694 template <class _InputIter1, class _InputIter2, class _OutputIter,
01695           class _Compare>
01696 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
01697                              _InputIter2 __first2, _InputIter2 __last2,
01698                              _OutputIter __result, _Compare __comp) {
01699   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
01700   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
01701   while (__first1 != __last1 && __first2 != __last2)
01702     if (__comp(*__first1, *__first2)) {
01703       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01704       *__result = *__first1;
01705       ++__first1;
01706       ++__result;
01707     }
01708     else if (__comp(*__first2, *__first1))
01709       ++__first2;
01710     else {
01711       ++__first1;
01712       ++__first2;
01713     }
01714   return copy(__first1, __last1, __result);
01715 }
01716 
01717 _STLP_MOVE_TO_STD_NAMESPACE
01718 
01719 template <class _InputIter1, class _InputIter2, class _OutputIter>
01720 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
01721                            _InputIter2 __first2, _InputIter2 __last2,
01722                            _OutputIter __result) {
01723   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,
01724                                      _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
01725 }
01726 
01727 template <class _InputIter1, class _InputIter2, class _OutputIter,
01728           class _Compare>
01729 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
01730                            _InputIter2 __first2, _InputIter2 __last2,
01731                            _OutputIter __result, _Compare __comp) {
01732   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
01733 }
01734 
01735 _STLP_MOVE_TO_PRIV_NAMESPACE
01736 
01737 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
01738 _OutputIter
01739 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
01740                            _InputIter2 __first2, _InputIter2 __last2,
01741                            _OutputIter __result, _Compare __comp) {
01742   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
01743   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
01744   while (__first1 != __last1 && __first2 != __last2) {
01745     if (__comp(*__first1, *__first2)) {
01746       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01747       *__result = *__first1;
01748       ++__first1;
01749       ++__result;
01750     }
01751     else if (__comp(*__first2, *__first1)) {
01752       *__result = *__first2;
01753       ++__first2;
01754       ++__result;
01755     }
01756     else {
01757       ++__first1;
01758       ++__first2;
01759     }
01760   }
01761   return copy(__first2, __last2, copy(__first1, __last1, __result));
01762 }
01763 
01764 _STLP_MOVE_TO_STD_NAMESPACE
01765 
01766 template <class _InputIter1, class _InputIter2, class _OutputIter>
01767 _OutputIter
01768 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
01769                          _InputIter2 __first2, _InputIter2 __last2,
01770                          _OutputIter __result) {
01771   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
01772                                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
01773 }
01774 
01775 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
01776 _OutputIter
01777 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
01778                          _InputIter2 __first2, _InputIter2 __last2,
01779                          _OutputIter __result,
01780                          _Compare __comp) {
01781   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
01782 }
01783 
01784 // min_element and max_element, with and without an explicitly supplied
01785 // comparison function.
01786 
01787 template <class _ForwardIter>
01788 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
01789   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01790   if (__first == __last) return __first;
01791   _ForwardIter __result = __first;
01792   while (++__first != __last)
01793     if (*__result < *__first)
01794       __result = __first;
01795   return __result;
01796 }
01797 
01798 template <class _ForwardIter, class _Compare>
01799 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
01800                          _Compare __comp) {
01801   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01802   if (__first == __last) return __first;
01803   _ForwardIter __result = __first;
01804   while (++__first != __last) {
01805     if (__comp(*__result, *__first)) {
01806       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01807       __result = __first;
01808     }
01809   }
01810   return __result;
01811 }
01812 
01813 template <class _ForwardIter>
01814 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
01815   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01816   if (__first == __last) return __first;
01817   _ForwardIter __result = __first;
01818   while (++__first != __last)
01819     if (*__first < *__result)
01820       __result = __first;
01821   return __result;
01822 }
01823 
01824 template <class _ForwardIter, class _Compare>
01825 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
01826                          _Compare __comp) {
01827   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01828   if (__first == __last) return __first;
01829   _ForwardIter __result = __first;
01830   while (++__first != __last) {
01831     if (__comp(*__first, *__result)) {
01832       _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01833       __result = __first;
01834     }
01835   }
01836   return __result;
01837 }
01838 
01839 // next_permutation and prev_permutation, with and without an explicitly
01840 // supplied comparison function.
01841 _STLP_MOVE_TO_PRIV_NAMESPACE
01842 
01843 template <class _BidirectionalIter, class _Compare>
01844 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
01845                         _Compare __comp) {
01846   _STLP_DEBUG_CHECK(__check_range(__first, __last))
01847   if (__first == __last)
01848     return false;
01849   _BidirectionalIter __i = __first;
01850   ++__i;
01851   if (__i == __last)
01852     return false;
01853   __i = __last;
01854   --__i;
01855 
01856   for(;;) {
01857     _BidirectionalIter __ii = __i;
01858     --__i;
01859     if (__comp(*__i, *__ii)) {
01860       _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01861       _BidirectionalIter __j = __last;
01862       while (!__comp(*__i, *--__j)) {}
01863       iter_swap(__i, __j);
01864       reverse(__ii, __last);
01865       return true;
01866     }
01867     if (__i == __first) {
01868       reverse(__first, __last);
01869       return false;
01870     }
01871   }
01872 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
01873     return false;
01874 #endif
01875 }
01876 
01877 _STLP_MOVE_TO_STD_NAMESPACE
01878 
01879 template <class _BidirectionalIter>
01880 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
01881   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01882   return _STLP_PRIV __next_permutation(__first, __last,
01883                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
01884 }
01885 
01886 template <class _BidirectionalIter, class _Compare>
01887 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
01888                       _Compare __comp) {
01889   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01890   return _STLP_PRIV __next_permutation(__first, __last, __comp);
01891 }
01892 
01893 _STLP_MOVE_TO_PRIV_NAMESPACE
01894 
01895 template <class _BidirectionalIter, class _Compare>
01896 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
01897                         _Compare __comp) {
01898   if (__first == __last)
01899     return false;
01900   _BidirectionalIter __i = __first;
01901   ++__i;
01902   if (__i == __last)
01903     return false;
01904   __i = __last;
01905   --__i;
01906 
01907   for(;;) {
01908     _BidirectionalIter __ii = __i;
01909     --__i;
01910     if (__comp(*__ii, *__i)) {
01911       _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01912       _BidirectionalIter __j = __last;
01913       while (!__comp(*--__j, *__i)) {}
01914       iter_swap(__i, __j);
01915       reverse(__ii, __last);
01916       return true;
01917     }
01918     if (__i == __first) {
01919       reverse(__first, __last);
01920       return false;
01921     }
01922   }
01923 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
01924     return false;
01925 #endif
01926 }
01927 
01928 _STLP_MOVE_TO_STD_NAMESPACE
01929 
01930 template <class _BidirectionalIter>
01931 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
01932   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01933   return _STLP_PRIV __prev_permutation(__first, __last,
01934                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
01935 }
01936 
01937 template <class _BidirectionalIter, class _Compare>
01938 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
01939                       _Compare __comp) {
01940   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01941   return _STLP_PRIV __prev_permutation(__first, __last, __comp);
01942 }
01943 
01944 #if !defined (_STLP_NO_EXTENSIONS)
01945 
01946 // is_heap, a predicate testing whether or not a range is
01947 // a heap.  This function is an extension, not part of the C++
01948 // standard.
01949 _STLP_MOVE_TO_PRIV_NAMESPACE
01950 
01951 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
01952 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
01953                _Distance __n) {
01954   _Distance __parent = 0;
01955   for (_Distance __child = 1; __child < __n; ++__child) {
01956     if (__comp(__first[__parent], __first[__child])) {
01957       _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01958       return false;
01959     }
01960     if ((__child & 1) == 0)
01961       ++__parent;
01962   }
01963   return true;
01964 }
01965 
01966 _STLP_MOVE_TO_STD_NAMESPACE
01967 
01968 template <class _RandomAccessIter>
01969 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
01970   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01971   return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
01972 }
01973 
01974 template <class _RandomAccessIter, class _StrictWeakOrdering>
01975 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
01976              _StrictWeakOrdering __comp) {
01977   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
01978   return _STLP_PRIV __is_heap(__first, __comp, __last - __first);
01979 }
01980 
01981 
01982 _STLP_MOVE_TO_PRIV_NAMESPACE
01983 
01984 template <class _ForwardIter, class _StrictWeakOrdering>
01985 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
01986                  _StrictWeakOrdering __comp) {
01987   _STLP_DEBUG_CHECK(__check_range(__first, __last))
01988   if (__first == __last)
01989     return true;
01990 
01991   _ForwardIter __next = __first;
01992   for (++__next; __next != __last; __first = __next, ++__next) {
01993     if (__comp(*__next, *__first)) {
01994       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
01995       return false;
01996     }
01997   }
01998 
01999   return true;
02000 }
02001 
02002 _STLP_MOVE_TO_STD_NAMESPACE
02003 #endif /* _STLP_NO_EXTENSIONS */
02004 
02005 _STLP_END_NAMESPACE
02006 
02007 #undef __stl_threshold
02008 
02009 #endif /* _STLP_ALGO_C */
02010 // Local Variables:
02011 // mode:C++
02012 // End:



Generated on Mon Mar 10 15:32:18 2008 by  doxygen 1.5.1