- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_algo.h

    00001 /*
    00002  *
    00003  * Copyright (c) 1994
    00004  * Hewlett-Packard Company
    00005  *
    00006  * Permission to use, copy, modify, distribute and sell this software
    00007  * and its documentation for any purpose is hereby granted without fee,
    00008  * provided that the above copyright notice appear in all copies and
    00009  * that both that copyright notice and this permission notice appear
    00010  * in supporting documentation.  Hewlett-Packard Company makes no
    00011  * representations about the suitability of this software for any
    00012  * purpose.  It is provided "as is" without express or implied warranty.
    00013  *
    00014  *
    00015  * Copyright (c) 1996
    00016  * Silicon Graphics Computer Systems, Inc.
    00017  *
    00018  * Permission to use, copy, modify, distribute and sell this software
    00019  * and its documentation for any purpose is hereby granted without fee,
    00020  * provided that the above copyright notice appear in all copies and
    00021  * that both that copyright notice and this permission notice appear
    00022  * in supporting documentation.  Silicon Graphics makes no
    00023  * representations about the suitability of this software for any
    00024  * purpose.  It is provided "as is" without express or implied warranty.
    00025  */
    00026
    00027 /* NOTE: This is an internal header file, included by other STL headers.
    00028  *   You should not attempt to use it directly.
    00029  */
    00030
    00031 #ifndef __SGI_STL_INTERNAL_ALGO_H
    00032 #define __SGI_STL_INTERNAL_ALGO_H
    00033
    00034 #include <stl_heap.h>
    00035
    00036 __STL_BEGIN_NAMESPACE
    00037
    00038 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    00039 #pragma set woff 1209
    00040 #endif
    00041
    00042 // __median (an extension, not present in the C++ standard).
    00043
    00044 template <class _Tp>
    00045 inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
    00046   if (__a < __b)
    00047     if (__b < __c)
    00048       return __b;
    00049     else if (__a < __c)
    00050       return __c;
    00051     else
    00052       return __a;
    00053   else if (__a < __c)
    00054     return __a;
    00055   else if (__b < __c)
    00056     return __c;
    00057   else
    00058     return __b;
    00059 }
    00060
    00061 template <class _Tp, class _Compare>
    00062 inline const _Tp&
    00063 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
    00064   if (__comp(__a, __b))
    00065     if (__comp(__b, __c))
    00066       return __b;
    00067     else if (__comp(__a, __c))
    00068       return __c;
    00069     else
    00070       return __a;
    00071   else if (__comp(__a, __c))
    00072     return __a;
    00073   else if (__comp(__b, __c))
    00074     return __c;
    00075   else
    00076     return __b;
    00077 }
    00078
    00079 // for_each.  Apply a function to every element of a range.
    00080 template <class _InputIter, class _Function>
    00081 _Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
    00082   for ( ; __first != __last; ++__first)
    00083     __f(*__first);
    00084   return __f;
    00085 }
    00086
    00087 // find and find_if.
    00088
    00089 template <class _InputIter, class _Tp>
    00090 inline _InputIter find(_InputIter __first, _InputIter __last,
    00091                        const _Tp& __val,
    00092                        input_iterator_tag)
    00093 {
    00094   while (__first != __last && *__first != __val)
    00095     ++__first;
    00096   return __first;
    00097 }
    00098
    00099 template <class _InputIter, class _Predicate>
    00100 inline _InputIter find_if(_InputIter __first, _InputIter __last,
    00101                           _Predicate __pred,
    00102                           input_iterator_tag)
    00103 {
    00104   while (__first != __last && !__pred(*__first))
    00105     ++__first;
    00106   return __first;
    00107 }
    00108
    00109 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00110
    00111 template <class _RandomAccessIter, class _Tp>
    00112 _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
    00113                        const _Tp& __val,
    00114                        random_access_iterator_tag)
    00115 {
    00116   typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
    00117     = (__last - __first) >> 2;
    00118
    00119   for ( ; __trip_count > 0 ; --__trip_count) {
    00120     if (*__first == __val) return __first;
    00121     ++__first;
    00122
    00123     if (*__first == __val) return __first;
    00124     ++__first;
    00125
    00126     if (*__first == __val) return __first;
    00127     ++__first;
    00128
    00129     if (*__first == __val) return __first;
    00130     ++__first;
    00131   }
    00132
    00133   switch(__last - __first) {
    00134   case 3:
    00135     if (*__first == __val) return __first;
    00136     ++__first;
    00137   case 2:
    00138     if (*__first == __val) return __first;
    00139     ++__first;
    00140   case 1:
    00141     if (*__first == __val) return __first;
    00142     ++__first;
    00143   case 0:
    00144   default:
    00145     return __last;
    00146   }
    00147 }
    00148
    00149 template <class _RandomAccessIter, class _Predicate>
    00150 _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
    00151                           _Predicate __pred,
    00152                           random_access_iterator_tag)
    00153 {
    00154   typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
    00155     = (__last - __first) >> 2;
    00156
    00157   for ( ; __trip_count > 0 ; --__trip_count) {
    00158     if (__pred(*__first)) return __first;
    00159     ++__first;
    00160
    00161     if (__pred(*__first)) return __first;
    00162     ++__first;
    00163
    00164     if (__pred(*__first)) return __first;
    00165     ++__first;
    00166
    00167     if (__pred(*__first)) return __first;
    00168     ++__first;
    00169   }
    00170
    00171   switch(__last - __first) {
    00172   case 3:
    00173     if (__pred(*__first)) return __first;
    00174     ++__first;
    00175   case 2:
    00176     if (__pred(*__first)) return __first;
    00177     ++__first;
    00178   case 1:
    00179     if (__pred(*__first)) return __first;
    00180     ++__first;
    00181   case 0:
    00182   default:
    00183     return __last;
    00184   }
    00185 }
    00186
    00187 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00188
    00189 template <class _InputIter, class _Tp>
    00190 inline _InputIter find(_InputIter __first, _InputIter __last,
    00191                        const _Tp& __val)
    00192 {
    00193   return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));
    00194 }
    00195
    00196 template <class _InputIter, class _Predicate>
    00197 inline _InputIter find_if(_InputIter __first, _InputIter __last,
    00198                           _Predicate __pred) {
    00199   return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
    00200 }
    00201
    00202 // adjacent_find.
    00203
    00204 template <class _ForwardIter>
    00205 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
    00206   if (__first == __last)
    00207     return __last;
    00208   _ForwardIter __next = __first;
    00209   while(++__next != __last) {
    00210     if (*__first == *__next)
    00211       return __first;
    00212     __first = __next;
    00213   }
    00214   return __last;
    00215 }
    00216
    00217 template <class _ForwardIter, class _BinaryPredicate>
    00218 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
    00219                            _BinaryPredicate __binary_pred) {
    00220   if (__first == __last)
    00221     return __last;
    00222   _ForwardIter __next = __first;
    00223   while(++__next != __last) {
    00224     if (__binary_pred(*__first, *__next))
    00225       return __first;
    00226     __first = __next;
    00227   }
    00228   return __last;
    00229 }
    00230
    00231 // count and count_if.  There are two version of each, one whose return type
    00232 // type is void and one (present only if we have partial specialization)
    00233 // whose return type is iterator_traits<_InputIter>::difference_type.  The
    00234 // C++ standard only has the latter version, but the former, which was present
    00235 // in the HP STL, is retained for backward compatibility.
    00236
    00237 template <class _InputIter, class _Tp, class _Size>
    00238 void count(_InputIter __first, _InputIter __last, const _Tp& __value,
    00239            _Size& __n) {
    00240   for ( ; __first != __last; ++__first)
    00241     if (*__first == __value)
    00242       ++__n;
    00243 }
    00244
    00245 template <class _InputIter, class _Predicate, class _Size>
    00246 void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
    00247               _Size& __n) {
    00248   for ( ; __first != __last; ++__first)
    00249     if (__pred(*__first))
    00250       ++__n;
    00251 }
    00252
    00253 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    00254
    00255 template <class _InputIter, class _Tp>
    00256 typename iterator_traits<_InputIter>::difference_type
    00257 count(_InputIter __first, _InputIter __last, const _Tp& __value) {
    00258   typename iterator_traits<_InputIter>::difference_type __n = 0;
    00259   for ( ; __first != __last; ++__first)
    00260     if (*__first == __value)
    00261       ++__n;
    00262   return __n;
    00263 }
    00264
    00265 template <class _InputIter, class _Predicate>
    00266 typename iterator_traits<_InputIter>::difference_type
    00267 count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
    00268   typename iterator_traits<_InputIter>::difference_type __n = 0;
    00269   for ( ; __first != __last; ++__first)
    00270     if (__pred(*__first))
    00271       ++__n;
    00272   return __n;
    00273 }
    00274
    00275
    00276 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    00277
    00278 // search.
    00279
    00280 template <class _ForwardIter1, class _ForwardIter2>
    00281 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
    00282                      _ForwardIter2 __first2, _ForwardIter2 __last2)
    00283 {
    00284   // Test for empty ranges
    00285   if (__first1 == __last1 || __first2 == __last2)
    00286     return __first1;
    00287
    00288   // Test for a pattern of length 1.
    00289   _ForwardIter2 __tmp(__first2);
    00290   ++__tmp;
    00291   if (__tmp == __last2)
    00292     return find(__first1, __last1, *__first2);
    00293
    00294   // General case.
    00295
    00296   _ForwardIter2 __p1, __p;
    00297
    00298   __p1 = __first2; ++__p1;
    00299
    00300   _ForwardIter1 __current = __first1;
    00301
    00302   while (__first1 != __last1) {
    00303     __first1 = find(__first1, __last1, *__first2);
    00304     if (__first1 == __last1)
    00305       return __last1;
    00306
    00307     __p = __p1;
    00308     __current = __first1;
    00309     if (++__current == __last1)
    00310       return __last1;
    00311
    00312     while (*__current == *__p) {
    00313       if (++__p == __last2)
    00314         return __first1;
    00315       if (++__current == __last1)
    00316         return __last1;
    00317     }
    00318
    00319     ++__first1;
    00320   }
    00321   return __first1;
    00322 }
    00323
    00324 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
    00325 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
    00326                      _ForwardIter2 __first2, _ForwardIter2 __last2,
    00327                      _BinaryPred  __predicate)
    00328 {
    00329   // Test for empty ranges
    00330   if (__first1 == __last1 || __first2 == __last2)
    00331     return __first1;
    00332
    00333   // Test for a pattern of length 1.
    00334   _ForwardIter2 __tmp(__first2);
    00335   ++__tmp;
    00336   if (__tmp == __last2)
    00337     return find(__first1, __last1, *__first2);
    00338
    00339   // General case.
    00340
    00341   _ForwardIter2 __p1, __p;
    00342
    00343   __p1 = __first2; ++__p1;
    00344
    00345   _ForwardIter1 __current = __first1;
    00346
    00347   while (__first1 != __last1) {
    00348     while (__first1 != __last1) {
    00349       if (__predicate(*__first1, *__first2))
    00350         break;
    00351       ++__first1;
    00352     }
    00353     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
    00354       ++__first1;
    00355     if (__first1 == __last1)
    00356       return __last1;
    00357
    00358     __p = __p1;
    00359     __current = __first1;
    00360     if (++__current == __last1) return __last1;
    00361
    00362     while (__predicate(*__current, *__p)) {
    00363       if (++__p == __last2)
    00364         return __first1;
    00365       if (++__current == __last1)
    00366         return __last1;
    00367     }
    00368
    00369     ++__first1;
    00370   }
    00371   return __first1;
    00372 }
    00373
    00374 // search_n.  Search for __count consecutive copies of __val.
    00375
    00376 template <class _ForwardIter, class _Integer, class _Tp>
    00377 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
    00378                       _Integer __count, const _Tp& __val) {
    00379   if (__count <= 0)
    00380     return __first;
    00381   else {
    00382     __first = find(__first, __last, __val);
    00383     while (__first != __last) {
    00384       _Integer __n = __count - 1;
    00385       _ForwardIter __i = __first;
    00386       ++__i;
    00387       while (__i != __last && __n != 0 && *__i == __val) {
    00388         ++__i;
    00389         --__n;
    00390       }
    00391       if (__n == 0)
    00392         return __first;
    00393       else
    00394         __first = find(__i, __last, __val);
    00395     }
    00396     return __last;
    00397   }
    00398 }
    00399
    00400 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
    00401 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
    00402                       _Integer __count, const _Tp& __val,
    00403                       _BinaryPred __binary_pred) {
    00404   if (__count <= 0)
    00405     return __first;
    00406   else {
    00407     while (__first != __last) {
    00408       if (__binary_pred(*__first, __val))
    00409         break;
    00410       ++__first;
    00411     }
    00412     while (__first != __last) {
    00413       _Integer __n = __count - 1;
    00414       _ForwardIter __i = __first;
    00415       ++__i;
    00416       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
    00417         ++__i;
    00418         --__n;
    00419       }
    00420       if (__n == 0)
    00421         return __first;
    00422       else {
    00423         while (__i != __last) {
    00424           if (__binary_pred(*__i, __val))
    00425             break;
    00426           ++__i;
    00427         }
    00428         __first = __i;
    00429       }
    00430     }
    00431     return __last;
    00432   }
    00433 }
    00434
    00435 // swap_ranges
    00436
    00437 template <class _ForwardIter1, class _ForwardIter2>
    00438 _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
    00439                           _ForwardIter2 __first2) {
    00440   for ( ; __first1 != __last1; ++__first1, ++__first2)
    00441     iter_swap(__first1, __first2);
    00442   return __first2;
    00443 }
    00444
    00445 // transform
    00446
    00447 template <class _InputIter, class _OutputIter, class _UnaryOperation>
    00448 _OutputIter transform(_InputIter __first, _InputIter __last,
    00449                       _OutputIter __result, _UnaryOperation __oper) {
    00450   for ( ; __first != __last; ++__first, ++__result)
    00451     *__result = __oper(*__first);
    00452   return __result;
    00453 }
    00454
    00455 template <class _InputIter1, class _InputIter2, class _OutputIter,
    00456           class _BinaryOperation>
    00457 _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
    00458                       _InputIter2 __first2, _OutputIter __result,
    00459                       _BinaryOperation __binary_op) {
    00460   for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
    00461     *__result = __binary_op(*__first1, *__first2);
    00462   return __result;
    00463 }
    00464
    00465 // replace, replace_if, replace_copy, replace_copy_if
    00466
    00467 template <class _ForwardIter, class _Tp>
    00468 void replace(_ForwardIter __first, _ForwardIter __last,
    00469              const _Tp& __old_value, const _Tp& __new_value) {
    00470   for ( ; __first != __last; ++__first)
    00471     if (*__first == __old_value)
    00472       *__first = __new_value;
    00473 }
    00474
    00475 template <class _ForwardIter, class _Predicate, class _Tp>
    00476 void replace_if(_ForwardIter __first, _ForwardIter __last,
    00477                 _Predicate __pred, const _Tp& __new_value) {
    00478   for ( ; __first != __last; ++__first)
    00479     if (__pred(*__first))
    00480       *__first = __new_value;
    00481 }
    00482
    00483 template <class _InputIter, class _OutputIter, class _Tp>
    00484 _OutputIter replace_copy(_InputIter __first, _InputIter __last,
    00485                          _OutputIter __result,
    00486                          const _Tp& __old_value, const _Tp& __new_value) {
    00487   for ( ; __first != __last; ++__first, ++__result)
    00488     *__result = *__first == __old_value ? __new_value : *__first;
    00489   return __result;
    00490 }
    00491
    00492 template <class Iterator, class _OutputIter, class _Predicate, class _Tp>
    00493 _OutputIter replace_copy_if(Iterator __first, Iterator __last,
    00494                             _OutputIter __result,
    00495                             _Predicate __pred, const _Tp& __new_value) {
    00496   for ( ; __first != __last; ++__first, ++__result)
    00497     *__result = __pred(*__first) ? __new_value : *__first;
    00498   return __result;
    00499 }
    00500
    00501 // generate and generate_n
    00502
    00503 template <class _ForwardIter, class _Generator>
    00504 void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
    00505   for ( ; __first != __last; ++__first)
    00506     *__first = __gen();
    00507 }
    00508
    00509 template <class _OutputIter, class _Size, class _Generator>
    00510 _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
    00511   for ( ; __n > 0; --__n, ++__first)
    00512     *__first = __gen();
    00513   return __first;
    00514 }
    00515
    00516 // remove, remove_if, remove_copy, remove_copy_if
    00517
    00518 template <class _InputIter, class _OutputIter, class _Tp>
    00519 _OutputIter remove_copy(_InputIter __first, _InputIter __last,
    00520                         _OutputIter __result, const _Tp& __value) {
    00521   for ( ; __first != __last; ++__first)
    00522     if (*__first != __value) {
    00523       *__result = *__first;
    00524       ++__result;
    00525     }
    00526   return __result;
    00527 }
    00528
    00529 template <class _InputIter, class _OutputIter, class _Predicate>
    00530 _OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
    00531                            _OutputIter __result, _Predicate __pred) {
    00532   for ( ; __first != __last; ++__first)
    00533     if (!__pred(*__first)) {
    00534       *__result = *__first;
    00535       ++__result;
    00536     }
    00537   return __result;
    00538 }
    00539
    00540 template <class _ForwardIter, class _Tp>
    00541 _ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
    00542                     const _Tp& __value) {
    00543   __first = find(__first, __last, __value);
    00544   _ForwardIter __i = __first;
    00545   return __first == __last ? __first
    00546                            : remove_copy(++__i, __last, __first, __value);
    00547 }
    00548
    00549 template <class _ForwardIter, class _Predicate>
    00550 _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
    00551                        _Predicate __pred) {
    00552   __first = find_if(__first, __last, __pred);
    00553   _ForwardIter __i = __first;
    00554   return __first == __last ? __first
    00555                            : remove_copy_if(++__i, __last, __first, __pred);
    00556 }
    00557
    00558 // unique and unique_copy
    00559
    00560 template <class _InputIter, class _OutputIter, class _Tp>
    00561 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
    00562                           _OutputIter __result, _Tp*) {
    00563   _Tp __value = *__first;
    00564   *__result = __value;
    00565   while (++__first != __last)
    00566     if (__value != *__first) {
    00567       __value = *__first;
    00568       *++__result = __value;
    00569     }
    00570   return ++__result;
    00571 }
    00572
    00573 template <class _InputIter, class _OutputIter>
    00574 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
    00575                                  _OutputIter __result,
    00576                                  output_iterator_tag) {
    00577   return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
    00578 }
    00579
    00580 template <class _InputIter, class _ForwardIter>
    00581 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
    00582                            _ForwardIter __result, forward_iterator_tag) {
    00583   *__result = *__first;
    00584   while (++__first != __last)
    00585     if (*__result != *__first) *++__result = *__first;
    00586   return ++__result;
    00587 }
    00588
    00589 template <class _InputIter, class _OutputIter>
    00590 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
    00591                                _OutputIter __result) {
    00592   if (__first == __last) return __result;
    00593   return __unique_copy(__first, __last, __result,
    00594                        __ITERATOR_CATEGORY(__result));
    00595 }
    00596
    00597 template <class _InputIter, class _OutputIter, class _BinaryPredicate,
    00598           class _Tp>
    00599 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
    00600                           _OutputIter __result,
    00601                           _BinaryPredicate __binary_pred, _Tp*) {
    00602   _Tp __value = *__first;
    00603   *__result = __value;
    00604   while (++__first != __last)
    00605     if (!__binary_pred(__value, *__first)) {
    00606       __value = *__first;
    00607       *++__result = __value;
    00608     }
    00609   return ++__result;
    00610 }
    00611
    00612 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
    00613 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
    00614                                  _OutputIter __result,
    00615                                  _BinaryPredicate __binary_pred,
    00616                                  output_iterator_tag) {
    00617   return __unique_copy(__first, __last, __result, __binary_pred,
    00618                        __VALUE_TYPE(__first));
    00619 }
    00620
    00621 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
    00622 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
    00623                            _ForwardIter __result,
    00624                            _BinaryPredicate __binary_pred,
    00625                            forward_iterator_tag) {
    00626   *__result = *__first;
    00627   while (++__first != __last)
    00628     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
    00629   return ++__result;
    00630 }
    00631
    00632 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
    00633 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
    00634                                _OutputIter __result,
    00635                                _BinaryPredicate __binary_pred) {
    00636   if (__first == __last) return __result;
    00637   return __unique_copy(__first, __last, __result, __binary_pred,
    00638                        __ITERATOR_CATEGORY(__result));
    00639 }
    00640
    00641 template <class _ForwardIter>
    00642 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
    00643   __first = adjacent_find(__first, __last);
    00644   return unique_copy(__first, __last, __first);
    00645 }
    00646
    00647 template <class _ForwardIter, class _BinaryPredicate>
    00648 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
    00649                     _BinaryPredicate __binary_pred) {
    00650   __first = adjacent_find(__first, __last, __binary_pred);
    00651   return unique_copy(__first, __last, __first, __binary_pred);
    00652 }
    00653
    00654 // reverse and reverse_copy, and their auxiliary functions
    00655
    00656 template <class _BidirectionalIter>
    00657 void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
    00658                bidirectional_iterator_tag) {
    00659   while (true)
    00660     if (__first == __last || __first == --__last)
    00661       return;
    00662     else
    00663       iter_swap(__first++, __last);
    00664 }
    00665
    00666 template <class _RandomAccessIter>
    00667 void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
    00668                random_access_iterator_tag) {
    00669   while (__first < __last)
    00670     iter_swap(__first++, --__last);
    00671 }
    00672
    00673 template <class _BidirectionalIter>
    00674 inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
    00675   __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
    00676 }
    00677
    00678 template <class _BidirectionalIter, class _OutputIter>
    00679 _OutputIter reverse_copy(_BidirectionalIter __first,
    00680                             _BidirectionalIter __last,
    00681                             _OutputIter __result) {
    00682   while (__first != __last) {
    00683     --__last;
    00684     *__result = *__last;
    00685     ++__result;
    00686   }
    00687   return __result;
    00688 }
    00689
    00690 // rotate and rotate_copy, and their auxiliary functions
    00691
    00692 template <class _EuclideanRingElement>
    00693 _EuclideanRingElement __gcd(_EuclideanRingElement __m,
    00694                             _EuclideanRingElement __n)
    00695 {
    00696   while (__n != 0) {
    00697     _EuclideanRingElement __t = __m % __n;
    00698     __m = __n;
    00699     __n = __t;
    00700   }
    00701   return __m;
    00702 }
    00703
    00704 template <class _ForwardIter, class _Distance>
    00705 _ForwardIter __rotate(_ForwardIter __first,
    00706                       _ForwardIter __middle,
    00707                       _ForwardIter __last,
    00708                       _Distance*,
    00709                       forward_iterator_tag) {
    00710   if (__first == __middle)
    00711     return __last;
    00712   if (__last  == __middle)
    00713     return __first;
    00714
    00715   _ForwardIter __first2 = __middle;
    00716   do {
    00717     swap(*__first++, *__first2++);
    00718     if (__first == __middle)
    00719       __middle = __first2;
    00720   } while (__first2 != __last);
    00721
    00722   _ForwardIter __new_middle = __first;
    00723
    00724   __first2 = __middle;
    00725
    00726   while (__first2 != __last) {
    00727     swap (*__first++, *__first2++);
    00728     if (__first == __middle)
    00729       __middle = __first2;
    00730     else if (__first2 == __last)
    00731       __first2 = __middle;
    00732   }
    00733
    00734   return __new_middle;
    00735 }
    00736
    00737
    00738 template <class _BidirectionalIter, class _Distance>
    00739 _BidirectionalIter __rotate(_BidirectionalIter __first,
    00740                             _BidirectionalIter __middle,
    00741                             _BidirectionalIter __last,
    00742                             _Distance*,
    00743                             bidirectional_iterator_tag) {
    00744   if (__first == __middle)
    00745     return __last;
    00746   if (__last  == __middle)
    00747     return __first;
    00748
    00749   __reverse(__first,  __middle, bidirectional_iterator_tag());
    00750   __reverse(__middle, __last,   bidirectional_iterator_tag());
    00751
    00752   while (__first != __middle && __middle != __last)
    00753     swap (*__first++, *--__last);
    00754
    00755   if (__first == __middle) {
    00756     __reverse(__middle, __last,   bidirectional_iterator_tag());
    00757     return __last;
    00758   }
    00759   else {
    00760     __reverse(__first,  __middle, bidirectional_iterator_tag());
    00761     return __first;
    00762   }
    00763 }
    00764
    00765 template <class _RandomAccessIter, class _Distance, class _Tp>
    00766 _RandomAccessIter __rotate(_RandomAccessIter __first,
    00767                            _RandomAccessIter __middle,
    00768                            _RandomAccessIter __last,
    00769                            _Distance *, _Tp *) {
    00770
    00771   _Distance __n = __last   - __first;
    00772   _Distance __k = __middle - __first;
    00773   _Distance __l = __n - __k;
    00774   _RandomAccessIter __result = __first + (__last - __middle);
    00775
    00776   if (__k == __l) {
    00777     swap_ranges(__first, __middle, __middle);
    00778     return __result;
    00779   }
    00780
    00781   _Distance __d = __gcd(__n, __k);
    00782
    00783   for (_Distance __i = 0; __i < __d; __i++) {
    00784     _Tp __tmp = *__first;
    00785     _RandomAccessIter __p = __first;
    00786
    00787     if (__k < __l) {
    00788       for (_Distance __j = 0; __j < __l/__d; __j++) {
    00789         if (__p > __first + __l) {
    00790           *__p = *(__p - __l);
    00791           __p -= __l;
    00792         }
    00793
    00794         *__p = *(__p + __k);
    00795         __p += __k;
    00796       }
    00797     }
    00798
    00799     else {
    00800       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
    00801         if (__p < __last - __k) {
    00802           *__p = *(__p + __k);
    00803           __p += __k;
    00804         }
    00805
    00806         *__p = * (__p - __l);
    00807         __p -= __l;
    00808       }
    00809     }
    00810
    00811     *__p = __tmp;
    00812     ++__first;
    00813   }
    00814
    00815   return __result;
    00816 }
    00817
    00818 template <class _ForwardIter>
    00819 inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
    00820                            _ForwardIter __last) {
    00821   return __rotate(__first, __middle, __last,
    00822                   __DISTANCE_TYPE(__first),
    00823                   __ITERATOR_CATEGORY(__first));
    00824 }
    00825
    00826 template <class _ForwardIter, class _OutputIter>
    00827 _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
    00828                             _ForwardIter __last, _OutputIter __result) {
    00829   return copy(__first, __middle, copy(__middle, __last, __result));
    00830 }
    00831
    00832 // Return a random number in the range [0, __n).  This function encapsulates
    00833 // whether we're using rand (part of the standard C library) or lrand48
    00834 // (not standard, but a much better choice whenever it's available).
    00835
    00836 template <class _Distance>
    00837 inline _Distance __random_number(_Distance __n) {
    00838 #ifdef __STL_NO_DRAND48
    00839   return rand() % __n;
    00840 #else
    00841   return lrand48() % __n;
    00842 #endif
    00843 }
    00844
    00845 // random_shuffle
    00846
    00847 template <class _RandomAccessIter>
    00848 inline void random_shuffle(_RandomAccessIter __first,
    00849                            _RandomAccessIter __last) {
    00850   if (__first == __last) return;
    00851   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    00852     iter_swap(__i, __first + __random_number((__i - __first) + 1));
    00853 }
    00854
    00855 template <class _RandomAccessIter, class _RandomNumberGenerator>
    00856 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
    00857                     _RandomNumberGenerator& __rand) {
    00858   if (__first == __last) return;
    00859   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    00860     iter_swap(__i, __first + __rand((__i - __first) + 1));
    00861 }
    00862
    00863 // random_sample and random_sample_n (extensions, not part of the standard).
    00864
    00865 template <class _ForwardIter, class _OutputIter, class _Distance>
    00866 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
    00867                             _OutputIter __out, const _Distance __n)
    00868 {
    00869   _Distance __remaining = 0;
    00870   distance(__first, __last, __remaining);
    00871   _Distance __m = min(__n, __remaining);
    00872
    00873   while (__m > 0) {
    00874     if (__random_number(__remaining) < __m) {
    00875       *__out = *__first;
    00876       ++__out;
    00877       --__m;
    00878     }
    00879
    00880     --__remaining;
    00881     ++__first;
    00882   }
    00883   return __out;
    00884 }
    00885
    00886 template <class _ForwardIter, class _OutputIter, class _Distance,
    00887           class _RandomNumberGenerator>
    00888 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
    00889                             _OutputIter __out, const _Distance __n,
    00890                             _RandomNumberGenerator& __rand)
    00891 {
    00892   _Distance __remaining = 0;
    00893   distance(__first, __last, __remaining);
    00894   _Distance __m = min(__n, __remaining);
    00895
    00896   while (__m > 0) {
    00897     if (__rand(__remaining) < __m) {
    00898       *__out = *__first;
    00899       ++__out;
    00900       --__m;
    00901     }
    00902
    00903     --__remaining;
    00904     ++__first;
    00905   }
    00906   return __out;
    00907 }
    00908
    00909 template <class _InputIter, class _RandomAccessIter, class _Distance>
    00910 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
    00911                                   _RandomAccessIter __out,
    00912                                   const _Distance __n)
    00913 {
    00914   _Distance __m = 0;
    00915   _Distance __t = __n;
    00916   for ( ; __first != __last && __m < __n; ++__m, ++__first)
    00917     __out[__m] = *__first;
    00918
    00919   while (__first != __last) {
    00920     ++__t;
    00921     _Distance __M = __random_number(__t);
    00922     if (__M < __n)
    00923       __out[__M] = *__first;
    00924     ++__first;
    00925   }
    00926
    00927   return __out + __m;
    00928 }
    00929
    00930 template <class _InputIter, class _RandomAccessIter,
    00931           class _RandomNumberGenerator, class _Distance>
    00932 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
    00933                                   _RandomAccessIter __out,
    00934                                   _RandomNumberGenerator& __rand,
    00935                                   const _Distance __n)
    00936 {
    00937   _Distance __m = 0;
    00938   _Distance __t = __n;
    00939   for ( ; __first != __last && __m < __n; ++__m, ++__first)
    00940     __out[__m] = *__first;
    00941
    00942   while (__first != __last) {
    00943     ++__t;
    00944     _Distance __M = __rand(__t);
    00945     if (__M < __n)
    00946       __out[__M] = *__first;
    00947     ++__first;
    00948   }
    00949
    00950   return __out + __m;
    00951 }
    00952
    00953 template <class _InputIter, class _RandomAccessIter>
    00954 inline _RandomAccessIter
    00955 random_sample(_InputIter __first, _InputIter __last,
    00956               _RandomAccessIter __out_first, _RandomAccessIter __out_last)
    00957 {
    00958   return __random_sample(__first, __last,
    00959                          __out_first, __out_last - __out_first);
    00960 }
    00961
    00962
    00963 template <class _InputIter, class _RandomAccessIter,
    00964           class _RandomNumberGenerator>
    00965 inline _RandomAccessIter
    00966 random_sample(_InputIter __first, _InputIter __last,
    00967               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
    00968               _RandomNumberGenerator& __rand)
    00969 {
    00970   return __random_sample(__first, __last,
    00971                          __out_first, __rand,
    00972                          __out_last - __out_first);
    00973 }
    00974
    00975 // partition, stable_partition, and their auxiliary functions
    00976
    00977 template <class _ForwardIter, class _Predicate>
    00978 _ForwardIter __partition(_ForwardIter __first,
    00979                          _ForwardIter __last,
    00980                          _Predicate   __pred,
    00981                          forward_iterator_tag) {
    00982   if (__first == __last) return __first;
    00983
    00984   while (__pred(*__first))
    00985     if (++__first == __last) return __first;
    00986
    00987   _ForwardIter __next = __first;
    00988
    00989   while (++__next != __last)
    00990     if (__pred(*__next)) {
    00991       swap(*__first, *__next);
    00992       ++__first;
    00993     }
    00994
    00995   return __first;
    00996 }
    00997
    00998 template <class _BidirectionalIter, class _Predicate>
    00999 _BidirectionalIter __partition(_BidirectionalIter __first,
    01000                                _BidirectionalIter __last,
    01001                                _Predicate __pred,
    01002                                bidirectional_iterator_tag) {
    01003   while (true) {
    01004     while (true)
    01005       if (__first == __last)
    01006         return __first;
    01007       else if (__pred(*__first))
    01008         ++__first;
    01009       else
    01010         break;
    01011     --__last;
    01012     while (true)
    01013       if (__first == __last)
    01014         return __first;
    01015       else if (!__pred(*__last))
    01016         --__last;
    01017       else
    01018         break;
    01019     iter_swap(__first, __last);
    01020     ++__first;
    01021   }
    01022 }
    01023
    01024 template <class _ForwardIter, class _Predicate>
    01025 inline _ForwardIter partition(_ForwardIter __first,
    01026                               _ForwardIter __last,
    01027                               _Predicate   __pred) {
    01028   return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
    01029 }
    01030
    01031
    01032 template <class _ForwardIter, class _Predicate, class _Distance>
    01033 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
    01034                                         _ForwardIter __last,
    01035                                         _Predicate __pred, _Distance __len) {
    01036   if (__len == 1)
    01037     return __pred(*__first) ? __last : __first;
    01038   _ForwardIter __middle = __first;
    01039   advance(__middle, __len / 2);
    01040   return rotate(__inplace_stable_partition(__first, __middle, __pred,
    01041                                            __len / 2),
    01042                 __middle,
    01043                 __inplace_stable_partition(__middle, __last, __pred,
    01044                                            __len - __len / 2));
    01045 }
    01046
    01047 template <class _ForwardIter, class _Pointer, class _Predicate,
    01048           class _Distance>
    01049 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
    01050                                          _ForwardIter __last,
    01051                                          _Predicate __pred, _Distance __len,
    01052                                          _Pointer __buffer,
    01053                                          _Distance __buffer_size)
    01054 {
    01055   if (__len <= __buffer_size) {
    01056     _ForwardIter __result1 = __first;
    01057     _Pointer __result2 = __buffer;
    01058     for ( ; __first != __last ; ++__first)
    01059       if (__pred(*__first)) {
    01060         *__result1 = *__first;
    01061         ++__result1;
    01062       }
    01063       else {
    01064         *__result2 = *__first;
    01065         ++__result2;
    01066       }
    01067     copy(__buffer, __result2, __result1);
    01068     return __result1;
    01069   }
    01070   else {
    01071     _ForwardIter __middle = __first;
    01072     advance(__middle, __len / 2);
    01073     return rotate(__stable_partition_adaptive(
    01074                           __first, __middle, __pred,
    01075                           __len / 2, __buffer, __buffer_size),
    01076                     __middle,
    01077                     __stable_partition_adaptive(
    01078                           __middle, __last, __pred,
    01079                           __len - __len / 2, __buffer, __buffer_size));
    01080   }
    01081 }
    01082
    01083 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
    01084 inline _ForwardIter
    01085 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
    01086                        _Predicate __pred, _Tp*, _Distance*)
    01087 {
    01088   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
    01089   if (__buf.size() > 0)
    01090     return __stable_partition_adaptive(__first, __last, __pred,
    01091                                        _Distance(__buf.requested_size()),
    01092                                        __buf.begin(), __buf.size());
    01093   else
    01094     return __inplace_stable_partition(__first, __last, __pred,
    01095                                       _Distance(__buf.requested_size()));
    01096 }
    01097
    01098 template <class _ForwardIter, class _Predicate>
    01099 inline _ForwardIter stable_partition(_ForwardIter __first,
    01100                                      _ForwardIter __last,
    01101                                      _Predicate __pred) {
    01102   if (__first == __last)
    01103     return __first;
    01104   else
    01105     return __stable_partition_aux(__first, __last, __pred,
    01106                                   __VALUE_TYPE(__first),
    01107                                   __DISTANCE_TYPE(__first));
    01108 }
    01109
    01110 template <class _RandomAccessIter, class _Tp>
    01111 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
    01112                                         _RandomAccessIter __last,
    01113                                         _Tp __pivot)
    01114 {
    01115   while (true) {
    01116     while (*__first < __pivot)
    01117       ++__first;
    01118     --__last;
    01119     while (__pivot < *__last)
    01120       --__last;
    01121     if (!(__first < __last))
    01122       return __first;
    01123     iter_swap(__first, __last);
    01124     ++__first;
    01125   }
    01126 }
    01127
    01128 template <class _RandomAccessIter, class _Tp, class _Compare>
    01129 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
    01130                                         _RandomAccessIter __last,
    01131                                         _Tp __pivot, _Compare __comp)
    01132 {
    01133   while (true) {
    01134     while (__comp(*__first, __pivot))
    01135       ++__first;
    01136     --__last;
    01137     while (__comp(__pivot, *__last))
    01138       --__last;
    01139     if (!(__first < __last))
    01140       return __first;
    01141     iter_swap(__first, __last);
    01142     ++__first;
    01143   }
    01144 }
    01145
    01146 const int __stl_threshold = 16;
    01147
    01148 // sort() and its auxiliary functions.
    01149
    01150 template <class _RandomAccessIter, class _Tp>
    01151 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
    01152   _RandomAccessIter __next = __last;
    01153   --__next;
    01154   while (__val < *__next) {
    01155     *__last = *__next;
    01156     __last = __next;
    01157     --__next;
    01158   }
    01159   *__last = __val;
    01160 }
    01161
    01162 template <class _RandomAccessIter, class _Tp, class _Compare>
    01163 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
    01164                                _Compare __comp) {
    01165   _RandomAccessIter __next = __last;
    01166   --__next;
    01167   while (__comp(__val, *__next)) {
    01168     *__last = *__next;
    01169     __last = __next;
    01170     --__next;
    01171   }
    01172   *__last = __val;
    01173 }
    01174
    01175 template <class _RandomAccessIter, class _Tp>
    01176 inline void __linear_insert(_RandomAccessIter __first,
    01177                             _RandomAccessIter __last, _Tp*) {
    01178   _Tp __val = *__last;
    01179   if (__val < *__first) {
    01180     copy_backward(__first, __last, __last + 1);
    01181     *__first = __val;
    01182   }
    01183   else
    01184     __unguarded_linear_insert(__last, __val);
    01185 }
    01186
    01187 template <class _RandomAccessIter, class _Tp, class _Compare>
    01188 inline void __linear_insert(_RandomAccessIter __first,
    01189                             _RandomAccessIter __last, _Tp*, _Compare __comp) {
    01190   _Tp __val = *__last;
    01191   if (__comp(__val, *__first)) {
    01192     copy_backward(__first, __last, __last + 1);
    01193     *__first = __val;
    01194   }
    01195   else
    01196     __unguarded_linear_insert(__last, __val, __comp);
    01197 }
    01198
    01199 template <class _RandomAccessIter>
    01200 void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) {
    01201   if (__first == __last) return;
    01202   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    01203     __linear_insert(__first, __i, __VALUE_TYPE(__first));
    01204 }
    01205
    01206 template <class _RandomAccessIter, class _Compare>
    01207 void __insertion_sort(_RandomAccessIter __first,
    01208                       _RandomAccessIter __last, _Compare __comp) {
    01209   if (__first == __last) return;
    01210   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    01211     __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
    01212 }
    01213
    01214 template <class _RandomAccessIter, class _Tp>
    01215 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
    01216                                     _RandomAccessIter __last, _Tp*) {
    01217   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    01218     __unguarded_linear_insert(__i, _Tp(*__i));
    01219 }
    01220
    01221 template <class _RandomAccessIter>
    01222 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
    01223                                 _RandomAccessIter __last) {
    01224   __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
    01225 }
    01226
    01227 template <class _RandomAccessIter, class _Tp, class _Compare>
    01228 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
    01229                                     _RandomAccessIter __last,
    01230                                     _Tp*, _Compare __comp) {
    01231   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
    01232     __unguarded_linear_insert(__i, _Tp(*__i), __comp);
    01233 }
    01234
    01235 template <class _RandomAccessIter, class _Compare>
    01236 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
    01237                                        _RandomAccessIter __last,
    01238                                        _Compare __comp) {
    01239   __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),
    01240                                  __comp);
    01241 }
    01242
    01243 template <class _RandomAccessIter>
    01244 void __final_insertion_sort(_RandomAccessIter __first,
    01245                             _RandomAccessIter __last) {
    01246   if (__last - __first > __stl_threshold) {
    01247     __insertion_sort(__first, __first + __stl_threshold);
    01248     __unguarded_insertion_sort(__first + __stl_threshold, __last);
    01249   }
    01250   else
    01251     __insertion_sort(__first, __last);
    01252 }
    01253
    01254 template <class _RandomAccessIter, class _Compare>
    01255 void __final_insertion_sort(_RandomAccessIter __first,
    01256                             _RandomAccessIter __last, _Compare __comp) {
    01257   if (__last - __first > __stl_threshold) {
    01258     __insertion_sort(__first, __first + __stl_threshold, __comp);
    01259     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
    01260   }
    01261   else
    01262     __insertion_sort(__first, __last, __comp);
    01263 }
    01264
    01265 template <class _Size>
    01266 inline _Size __lg(_Size __n) {
    01267   _Size __k;
    01268   for (__k = 0; __n != 1; __n >>= 1) ++__k;
    01269   return __k;
    01270 }
    01271
    01272 template <class _RandomAccessIter, class _Tp, class _Size>
    01273 void __introsort_loop(_RandomAccessIter __first,
    01274                       _RandomAccessIter __last, _Tp*,
    01275                       _Size __depth_limit)
    01276 {
    01277   while (__last - __first > __stl_threshold) {
    01278     if (__depth_limit == 0) {
    01279       partial_sort(__first, __last, __last);
    01280       return;
    01281     }
    01282     --__depth_limit;
    01283     _RandomAccessIter __cut =
    01284       __unguarded_partition(__first, __last,
    01285                             _Tp(__median(*__first,
    01286                                          *(__first + (__last - __first)/2),
    01287                                          *(__last - 1))));
    01288     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
    01289     __last = __cut;
    01290   }
    01291 }
    01292
    01293 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
    01294 void __introsort_loop(_RandomAccessIter __first,
    01295                       _RandomAccessIter __last, _Tp*,
    01296                       _Size __depth_limit, _Compare __comp)
    01297 {
    01298   while (__last - __first > __stl_threshold) {
    01299     if (__depth_limit == 0) {
    01300       partial_sort(__first, __last, __last, __comp);
    01301       return;
    01302     }
    01303     --__depth_limit;
    01304     _RandomAccessIter __cut =
    01305       __unguarded_partition(__first, __last,
    01306                             _Tp(__median(*__first,
    01307                                          *(__first + (__last - __first)/2),
    01308                                          *(__last - 1), __comp)),
    01309        __comp);
    01310     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
    01311     __last = __cut;
    01312   }
    01313 }
    01314
    01315 template <class _RandomAccessIter>
    01316 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
    01317   if (__first != __last) {
    01318     __introsort_loop(__first, __last,
    01319                      __VALUE_TYPE(__first),
    01320                      __lg(__last - __first) * 2);
    01321     __final_insertion_sort(__first, __last);
    01322   }
    01323 }
    01324
    01325 template <class _RandomAccessIter, class _Compare>
    01326 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
    01327                  _Compare __comp) {
    01328   if (__first != __last) {
    01329     __introsort_loop(__first, __last,
    01330                      __VALUE_TYPE(__first),
    01331                      __lg(__last - __first) * 2,
    01332                      __comp);
    01333     __final_insertion_sort(__first, __last, __comp);
    01334   }
    01335 }
    01336
    01337 // stable_sort() and its auxiliary functions.
    01338
    01339 template <class _RandomAccessIter>
    01340 void __inplace_stable_sort(_RandomAccessIter __first,
    01341                            _RandomAccessIter __last) {
    01342   if (__last - __first < 15) {
    01343     __insertion_sort(__first, __last);
    01344     return;
    01345   }
    01346   _RandomAccessIter __middle = __first + (__last - __first) / 2;
    01347   __inplace_stable_sort(__first, __middle);
    01348   __inplace_stable_sort(__middle, __last);
    01349   __merge_without_buffer(__first, __middle, __last,
    01350                          __middle - __first,
    01351                          __last - __middle);
    01352 }
    01353
    01354 template <class _RandomAccessIter, class _Compare>
    01355 void __inplace_stable_sort(_RandomAccessIter __first,
    01356                            _RandomAccessIter __last, _Compare __comp) {
    01357   if (__last - __first < 15) {
    01358     __insertion_sort(__first, __last, __comp);
    01359     return;
    01360   }
    01361   _RandomAccessIter __middle = __first + (__last - __first) / 2;
    01362   __inplace_stable_sort(__first, __middle, __comp);
    01363   __inplace_stable_sort(__middle, __last, __comp);
    01364   __merge_without_buffer(__first, __middle, __last,
    01365                          __middle - __first,
    01366                          __last - __middle,
    01367                          __comp);
    01368 }
    01369
    01370 template <class _RandomAccessIter1, class _RandomAccessIter2,
    01371           class _Distance>
    01372 void __merge_sort_loop(_RandomAccessIter1 __first,
    01373                        _RandomAccessIter1 __last,
    01374                        _RandomAccessIter2 __result, _Distance __step_size) {
    01375   _Distance __two_step = 2 * __step_size;
    01376
    01377   while (__last - __first >= __two_step) {
    01378     __result = merge(__first, __first + __step_size,
    01379                      __first + __step_size, __first + __two_step,
    01380                      __result);
    01381     __first += __two_step;
    01382   }
    01383
    01384   __step_size = min(_Distance(__last - __first), __step_size);
    01385   merge(__first, __first + __step_size, __first + __step_size, __last,
    01386         __result);
    01387 }
    01388
    01389 template <class _RandomAccessIter1, class _RandomAccessIter2,
    01390           class _Distance, class _Compare>
    01391 void __merge_sort_loop(_RandomAccessIter1 __first,
    01392                        _RandomAccessIter1 __last,
    01393                        _RandomAccessIter2 __result, _Distance __step_size,
    01394                        _Compare __comp) {
    01395   _Distance __two_step = 2 * __step_size;
    01396
    01397   while (__last - __first >= __two_step) {
    01398     __result = merge(__first, __first + __step_size,
    01399                      __first + __step_size, __first + __two_step,
    01400                      __result,
    01401                      __comp);
    01402     __first += __two_step;
    01403   }
    01404   __step_size = min(_Distance(__last - __first), __step_size);
    01405
    01406   merge(__first, __first + __step_size,
    01407         __first + __step_size, __last,
    01408         __result,
    01409         __comp);
    01410 }
    01411
    01412 const int __stl_chunk_size = 7;
    01413
    01414 template <class _RandomAccessIter, class _Distance>
    01415 void __chunk_insertion_sort(_RandomAccessIter __first,
    01416                             _RandomAccessIter __last, _Distance __chunk_size)
    01417 {
    01418   while (__last - __first >= __chunk_size) {
    01419     __insertion_sort(__first, __first + __chunk_size);
    01420     __first += __chunk_size;
    01421   }
    01422   __insertion_sort(__first, __last);
    01423 }
    01424
    01425 template <class _RandomAccessIter, class _Distance, class _Compare>
    01426 void __chunk_insertion_sort(_RandomAccessIter __first,
    01427                             _RandomAccessIter __last,
    01428                             _Distance __chunk_size, _Compare __comp)
    01429 {
    01430   while (__last - __first >= __chunk_size) {
    01431     __insertion_sort(__first, __first + __chunk_size, __comp);
    01432     __first += __chunk_size;
    01433   }
    01434   __insertion_sort(__first, __last, __comp);
    01435 }
    01436
    01437 template <class _RandomAccessIter, class _Pointer, class _Distance>
    01438 void __merge_sort_with_buffer(_RandomAccessIter __first,
    01439                               _RandomAccessIter __last,
    01440                               _Pointer __buffer, _Distance*) {
    01441   _Distance __len = __last - __first;
    01442   _Pointer __buffer_last = __buffer + __len;
    01443
    01444   _Distance __step_size = __stl_chunk_size;
    01445   __chunk_insertion_sort(__first, __last, __step_size);
    01446
    01447   while (__step_size < __len) {
    01448     __merge_sort_loop(__first, __last, __buffer, __step_size);
    01449     __step_size *= 2;
    01450     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
    01451     __step_size *= 2;
    01452   }
    01453 }
    01454
    01455 template <class _RandomAccessIter, class _Pointer, class _Distance,
    01456           class _Compare>
    01457 void __merge_sort_with_buffer(_RandomAccessIter __first,
    01458                               _RandomAccessIter __last, _Pointer __buffer,
    01459                               _Distance*, _Compare __comp) {
    01460   _Distance __len = __last - __first;
    01461   _Pointer __buffer_last = __buffer + __len;
    01462
    01463   _Distance __step_size = __stl_chunk_size;
    01464   __chunk_insertion_sort(__first, __last, __step_size, __comp);
    01465
    01466   while (__step_size < __len) {
    01467     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
    01468     __step_size *= 2;
    01469     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
    01470     __step_size *= 2;
    01471   }
    01472 }
    01473
    01474 template <class _RandomAccessIter, class _Pointer, class _Distance>
    01475 void __stable_sort_adaptive(_RandomAccessIter __first,
    01476                             _RandomAccessIter __last, _Pointer __buffer,
    01477                             _Distance __buffer_size) {
    01478   _Distance __len = (__last - __first + 1) / 2;
    01479   _RandomAccessIter __middle = __first + __len;
    01480   if (__len > __buffer_size) {
    01481     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
    01482     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
    01483   }
    01484   else {
    01485     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
    01486     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
    01487   }
    01488   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
    01489                    _Distance(__last - __middle), __buffer, __buffer_size);
    01490 }
    01491
    01492 template <class _RandomAccessIter, class _Pointer, class _Distance,
    01493           class _Compare>
    01494 void __stable_sort_adaptive(_RandomAccessIter __first,
    01495                             _RandomAccessIter __last, _Pointer __buffer,
    01496                             _Distance __buffer_size, _Compare __comp) {
    01497   _Distance __len = (__last - __first + 1) / 2;
    01498   _RandomAccessIter __middle = __first + __len;
    01499   if (__len > __buffer_size) {
    01500     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
    01501                            __comp);
    01502     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
    01503                            __comp);
    01504   }
    01505   else {
    01506     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
    01507                                __comp);
    01508     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
    01509                                __comp);
    01510   }
    01511   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
    01512                    _Distance(__last - __middle), __buffer, __buffer_size,
    01513                    __comp);
    01514 }
    01515
    01516 template <class _RandomAccessIter, class _Tp, class _Distance>
    01517 inline void __stable_sort_aux(_RandomAccessIter __first,
    01518                               _RandomAccessIter __last, _Tp*, _Distance*) {
    01519   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
    01520   if (buf.begin() == 0)
    01521     __inplace_stable_sort(__first, __last);
    01522   else
    01523     __stable_sort_adaptive(__first, __last, buf.begin(),
    01524                            _Distance(buf.size()));
    01525 }
    01526
    01527 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
    01528 inline void __stable_sort_aux(_RandomAccessIter __first,
    01529                               _RandomAccessIter __last, _Tp*, _Distance*,
    01530                               _Compare __comp) {
    01531   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
    01532   if (buf.begin() == 0)
    01533     __inplace_stable_sort(__first, __last, __comp);
    01534   else
    01535     __stable_sort_adaptive(__first, __last, buf.begin(),
    01536                            _Distance(buf.size()),
    01537                            __comp);
    01538 }
    01539
    01540 template <class _RandomAccessIter>
    01541 inline void stable_sort(_RandomAccessIter __first,
    01542                         _RandomAccessIter __last) {
    01543   __stable_sort_aux(__first, __last,
    01544                     __VALUE_TYPE(__first),
    01545                     __DISTANCE_TYPE(__first));
    01546 }
    01547
    01548 template <class _RandomAccessIter, class _Compare>
    01549 inline void stable_sort(_RandomAccessIter __first,
    01550                         _RandomAccessIter __last, _Compare __comp) {
    01551   __stable_sort_aux(__first, __last,
    01552                     __VALUE_TYPE(__first),
    01553                     __DISTANCE_TYPE(__first),
    01554                     __comp);
    01555 }
    01556
    01557 // partial_sort, partial_sort_copy, and auxiliary functions.
    01558
    01559 template <class _RandomAccessIter, class _Tp>
    01560 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
    01561                     _RandomAccessIter __last, _Tp*) {
    01562   make_heap(__first, __middle);
    01563   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
    01564     if (*__i < *__first)
    01565       __pop_heap(__first, __middle, __i, _Tp(*__i),
    01566                  __DISTANCE_TYPE(__first));
    01567   sort_heap(__first, __middle);
    01568 }
    01569
    01570 template <class _RandomAccessIter>
    01571 inline void partial_sort(_RandomAccessIter __first,
    01572                          _RandomAccessIter __middle,
    01573                          _RandomAccessIter __last) {
    01574   __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
    01575 }
    01576
    01577 template <class _RandomAccessIter, class _Tp, class _Compare>
    01578 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
    01579                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
    01580   make_heap(__first, __middle, __comp);
    01581   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
    01582     if (__comp(*__i, *__first))
    01583       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
    01584                  __DISTANCE_TYPE(__first));
    01585   sort_heap(__first, __middle, __comp);
    01586 }
    01587
    01588 template <class _RandomAccessIter, class _Compare>
    01589 inline void partial_sort(_RandomAccessIter __first,
    01590                          _RandomAccessIter __middle,
    01591                          _RandomAccessIter __last, _Compare __comp) {
    01592   __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp);
    01593 }
    01594
    01595 template <class _InputIter, class _RandomAccessIter, class _Distance,
    01596           class _Tp>
    01597 _RandomAccessIter __partial_sort_copy(_InputIter __first,
    01598                                          _InputIter __last,
    01599                                          _RandomAccessIter __result_first,
    01600                                          _RandomAccessIter __result_last,
    01601                                          _Distance*, _Tp*) {
    01602   if (__result_first == __result_last) return __result_last;
    01603   _RandomAccessIter __result_real_last = __result_first;
    01604   while(__first != __last && __result_real_last != __result_last) {
    01605     *__result_real_last = *__first;
    01606     ++__result_real_last;
    01607     ++__first;
    01608   }
    01609   make_heap(__result_first, __result_real_last);
    01610   while (__first != __last) {
    01611     if (*__first < *__result_first)
    01612       __adjust_heap(__result_first, _Distance(0),
    01613                     _Distance(__result_real_last - __result_first),
    01614                     _Tp(*__first));
    01615     ++__first;
    01616   }
    01617   sort_heap(__result_first, __result_real_last);
    01618   return __result_real_last;
    01619 }
    01620
    01621 template <class _InputIter, class _RandomAccessIter>
    01622 inline _RandomAccessIter
    01623 partial_sort_copy(_InputIter __first, _InputIter __last,
    01624                   _RandomAccessIter __result_first,
    01625                   _RandomAccessIter __result_last) {
    01626   return __partial_sort_copy(__first, __last, __result_first, __result_last,
    01627                              __DISTANCE_TYPE(__result_first),
    01628                              __VALUE_TYPE(__first));
    01629 }
    01630
    01631 template <class _InputIter, class _RandomAccessIter, class _Compare,
    01632           class _Distance, class _Tp>
    01633 _RandomAccessIter __partial_sort_copy(_InputIter __first,
    01634                                          _InputIter __last,
    01635                                          _RandomAccessIter __result_first,
    01636                                          _RandomAccessIter __result_last,
    01637                                          _Compare __comp, _Distance*, _Tp*) {
    01638   if (__result_first == __result_last) return __result_last;
    01639   _RandomAccessIter __result_real_last = __result_first;
    01640   while(__first != __last && __result_real_last != __result_last) {
    01641     *__result_real_last = *__first;
    01642     ++__result_real_last;
    01643     ++__first;
    01644   }
    01645   make_heap(__result_first, __result_real_last, __comp);
    01646   while (__first != __last) {
    01647     if (__comp(*__first, *__result_first))
    01648       __adjust_heap(__result_first, _Distance(0),
    01649                     _Distance(__result_real_last - __result_first),
    01650                     _Tp(*__first),
    01651                     __comp);
    01652     ++__first;
    01653   }
    01654   sort_heap(__result_first, __result_real_last, __comp);
    01655   return __result_real_last;
    01656 }
    01657
    01658 template <class _InputIter, class _RandomAccessIter, class _Compare>
    01659 inline _RandomAccessIter
    01660 partial_sort_copy(_InputIter __first, _InputIter __last,
    01661                   _RandomAccessIter __result_first,
    01662                   _RandomAccessIter __result_last, _Compare __comp) {
    01663   return __partial_sort_copy(__first, __last, __result_first, __result_last,
    01664                              __comp,
    01665                              __DISTANCE_TYPE(__result_first),
    01666                              __VALUE_TYPE(__first));
    01667 }
    01668
    01669 // nth_element() and its auxiliary functions.
    01670
    01671 template <class _RandomAccessIter, class _Tp>
    01672 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
    01673                    _RandomAccessIter __last, _Tp*) {
    01674   while (__last - __first > 3) {
    01675     _RandomAccessIter __cut =
    01676       __unguarded_partition(__first, __last,
    01677                             _Tp(__median(*__first,
    01678                                          *(__first + (__last - __first)/2),
    01679                                          *(__last - 1))));
    01680     if (__cut <= __nth)
    01681       __first = __cut;
    01682     else
    01683       __last = __cut;
    01684   }
    01685   __insertion_sort(__first, __last);
    01686 }
    01687
    01688 template <class _RandomAccessIter>
    01689 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
    01690                         _RandomAccessIter __last) {
    01691   __nth_element(__first, __nth, __last, __VALUE_TYPE(__first));
    01692 }
    01693
    01694 template <class _RandomAccessIter, class _Tp, class _Compare>
    01695 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
    01696                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
    01697   while (__last - __first > 3) {
    01698     _RandomAccessIter __cut =
    01699       __unguarded_partition(__first, __last,
    01700                             _Tp(__median(*__first,
    01701                                          *(__first + (__last - __first)/2),
    01702                                          *(__last - 1),
    01703                                          __comp)),
    01704                             __comp);
    01705     if (__cut <= __nth)
    01706       __first = __cut;
    01707     else
    01708       __last = __cut;
    01709   }
    01710   __insertion_sort(__first, __last, __comp);
    01711 }
    01712
    01713 template <class _RandomAccessIter, class _Compare>
    01714 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
    01715                  _RandomAccessIter __last, _Compare __comp) {
    01716   __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp);
    01717 }
    01718
    01719
    01720 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
    01721
    01722 template <class _ForwardIter, class _Tp, class _Distance>
    01723 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
    01724                            const _Tp& __val, _Distance*)
    01725 {
    01726   _Distance __len = 0;
    01727   distance(__first, __last, __len);
    01728   _Distance __half;
    01729   _ForwardIter __middle;
    01730
    01731   while (__len > 0) {
    01732     __half = __len >> 1;
    01733     __middle = __first;
    01734     advance(__middle, __half);
    01735     if (*__middle < __val) {
    01736       __first = __middle;
    01737       ++__first;
    01738       __len = __len - __half - 1;
    01739     }
    01740     else
    01741       __len = __half;
    01742   }
    01743   return __first;
    01744 }
    01745
    01746 template <class _ForwardIter, class _Tp>
    01747 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
    01748                                    const _Tp& __val) {
    01749   return __lower_bound(__first, __last, __val,
    01750                        __DISTANCE_TYPE(__first));
    01751 }
    01752
    01753 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
    01754 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
    01755                               const _Tp& __val, _Compare __comp, _Distance*)
    01756 {
    01757   _Distance __len = 0;
    01758   distance(__first, __last, __len);
    01759   _Distance __half;
    01760   _ForwardIter __middle;
    01761
    01762   while (__len > 0) {
    01763     __half = __len >> 1;
    01764     __middle = __first;
    01765     advance(__middle, __half);
    01766     if (__comp(*__middle, __val)) {
    01767       __first = __middle;
    01768       ++__first;
    01769       __len = __len - __half - 1;
    01770     }
    01771     else
    01772       __len = __half;
    01773   }
    01774   return __first;
    01775 }
    01776
    01777 template <class _ForwardIter, class _Tp, class _Compare>
    01778 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
    01779                                 const _Tp& __val, _Compare __comp) {
    01780   return __lower_bound(__first, __last, __val, __comp,
    01781                        __DISTANCE_TYPE(__first));
    01782 }
    01783
    01784 template <class _ForwardIter, class _Tp, class _Distance>
    01785 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
    01786                            const _Tp& __val, _Distance*)
    01787 {
    01788   _Distance __len = 0;
    01789   distance(__first, __last, __len);
    01790   _Distance __half;
    01791   _ForwardIter __middle;
    01792
    01793   while (__len > 0) {
    01794     __half = __len >> 1;
    01795     __middle = __first;
    01796     advance(__middle, __half);
    01797     if (__val < *__middle)
    01798       __len = __half;
    01799     else {
    01800       __first = __middle;
    01801       ++__first;
    01802       __len = __len - __half - 1;
    01803     }
    01804   }
    01805   return __first;
    01806 }
    01807
    01808 template <class _ForwardIter, class _Tp>
    01809 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
    01810                                 const _Tp& __val) {
    01811   return __upper_bound(__first, __last, __val,
    01812                        __DISTANCE_TYPE(__first));
    01813 }
    01814
    01815 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
    01816 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
    01817                            const _Tp& __val, _Compare __comp, _Distance*)
    01818 {
    01819   _Distance __len = 0;
    01820   distance(__first, __last, __len);
    01821   _Distance __half;
    01822   _ForwardIter __middle;
    01823
    01824   while (__len > 0) {
    01825     __half = __len >> 1;
    01826     __middle = __first;
    01827     advance(__middle, __half);
    01828     if (__comp(__val, *__middle))
    01829       __len = __half;
    01830     else {
    01831       __first = __middle;
    01832       ++__first;
    01833       __len = __len - __half - 1;
    01834     }
    01835   }
    01836   return __first;
    01837 }
    01838
    01839 template <class _ForwardIter, class _Tp, class _Compare>
    01840 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
    01841                                 const _Tp& __val, _Compare __comp) {
    01842   return __upper_bound(__first, __last, __val, __comp,
    01843                        __DISTANCE_TYPE(__first));
    01844 }
    01845
    01846 template <class _ForwardIter, class _Tp, class _Distance>
    01847 pair<_ForwardIter, _ForwardIter>
    01848 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
    01849               _Distance*)
    01850 {
    01851   _Distance __len = 0;
    01852   distance(__first, __last, __len);
    01853   _Distance __half;
    01854   _ForwardIter __middle, __left, __right;
    01855
    01856   while (__len > 0) {
    01857     __half = __len >> 1;
    01858     __middle = __first;
    01859     advance(__middle, __half);
    01860     if (*__middle < __val) {
    01861       __first = __middle;
    01862       ++__first;
    01863       __len = __len - __half - 1;
    01864     }
    01865     else if (__val < *__middle)
    01866       __len = __half;
    01867     else {
    01868       __left = lower_bound(__first, __middle, __val);
    01869       advance(__first, __len);
    01870       __right = upper_bound(++__middle, __first, __val);
    01871       return pair<_ForwardIter, _ForwardIter>(__left, __right);
    01872     }
    01873   }
    01874   return pair<_ForwardIter, _ForwardIter>(__first, __first);
    01875 }
    01876
    01877 template <class _ForwardIter, class _Tp>
    01878 inline pair<_ForwardIter, _ForwardIter>
    01879 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
    01880   return __equal_range(__first, __last, __val,
    01881                        __DISTANCE_TYPE(__first));
    01882 }
    01883
    01884 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
    01885 pair<_ForwardIter, _ForwardIter>
    01886 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
    01887               _Compare __comp, _Distance*)
    01888 {
    01889   _Distance __len = 0;
    01890   distance(__first, __last, __len);
    01891   _Distance __half;
    01892   _ForwardIter __middle, __left, __right;
    01893
    01894   while (__len > 0) {
    01895     __half = __len >> 1;
    01896     __middle = __first;
    01897     advance(__middle, __half);
    01898     if (__comp(*__middle, __val)) {
    01899       __first = __middle;
    01900       ++__first;
    01901       __len = __len - __half - 1;
    01902     }
    01903     else if (__comp(__val, *__middle))
    01904       __len = __half;
    01905     else {
    01906       __left = lower_bound(__first, __middle, __val, __comp);
    01907       advance(__first, __len);
    01908       __right = upper_bound(++__middle, __first, __val, __comp);
    01909       return pair<_ForwardIter, _ForwardIter>(__left, __right);
    01910     }
    01911   }
    01912   return pair<_ForwardIter, _ForwardIter>(__first, __first);
    01913 }
    01914
    01915 template <class _ForwardIter, class _Tp, class _Compare>
    01916 inline pair<_ForwardIter, _ForwardIter>
    01917 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
    01918             _Compare __comp) {
    01919   return __equal_range(__first, __last, __val, __comp,
    01920                        __DISTANCE_TYPE(__first));
    01921 }
    01922
    01923 template <class _ForwardIter, class _Tp>
    01924 bool binary_search(_ForwardIter __first, _ForwardIter __last,
    01925                    const _Tp& __val) {
    01926   _ForwardIter __i = lower_bound(__first, __last, __val);
    01927   return __i != __last && !(__val < *__i);
    01928 }
    01929
    01930 template <class _ForwardIter, class _Tp, class _Compare>
    01931 bool binary_search(_ForwardIter __first, _ForwardIter __last,
    01932                    const _Tp& __val,
    01933                    _Compare __comp) {
    01934   _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
    01935   return __i != __last && !__comp(__val, *__i);
    01936 }
    01937
    01938 // merge, with and without an explicitly supplied comparison function.
    01939
    01940 template <class _InputIter1, class _InputIter2, class _OutputIter>
    01941 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
    01942                   _InputIter2 __first2, _InputIter2 __last2,
    01943                   _OutputIter __result) {
    01944   while (__first1 != __last1 && __first2 != __last2) {
    01945     if (*__first2 < *__first1) {
    01946       *__result = *__first2;
    01947       ++__first2;
    01948     }
    01949     else {
    01950       *__result = *__first1;
    01951       ++__first1;
    01952     }
    01953     ++__result;
    01954   }
    01955   return copy(__first2, __last2, copy(__first1, __last1, __result));
    01956 }
    01957
    01958 template <class _InputIter1, class _InputIter2, class _OutputIter,
    01959           class _Compare>
    01960 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
    01961                   _InputIter2 __first2, _InputIter2 __last2,
    01962                   _OutputIter __result, _Compare __comp) {
    01963   while (__first1 != __last1 && __first2 != __last2) {
    01964     if (__comp(*__first2, *__first1)) {
    01965       *__result = *__first2;
    01966       ++__first2;
    01967     }
    01968     else {
    01969       *__result = *__first1;
    01970       ++__first1;
    01971     }
    01972     ++__result;
    01973   }
    01974   return copy(__first2, __last2, copy(__first1, __last1, __result));
    01975 }
    01976
    01977 // inplace_merge and its auxiliary functions.
    01978
    01979 template <class _BidirectionalIter, class _Distance>
    01980 void __merge_without_buffer(_BidirectionalIter __first,
    01981                             _BidirectionalIter __middle,
    01982                             _BidirectionalIter __last,
    01983                             _Distance __len1, _Distance __len2) {
    01984   if (__len1 == 0 || __len2 == 0)
    01985     return;
    01986   if (__len1 + __len2 == 2) {
    01987     if (*__middle < *__first)
    01988       iter_swap(__first, __middle);
    01989     return;
    01990   }
    01991   _BidirectionalIter __first_cut = __first;
    01992   _BidirectionalIter __second_cut = __middle;
    01993   _Distance __len11 = 0;
    01994   _Distance __len22 = 0;
    01995   if (__len1 > __len2) {
    01996     __len11 = __len1 / 2;
    01997     advance(__first_cut, __len11);
    01998     __second_cut = lower_bound(__middle, __last, *__first_cut);
    01999     distance(__middle, __second_cut, __len22);
    02000   }
    02001   else {
    02002     __len22 = __len2 / 2;
    02003     advance(__second_cut, __len22);
    02004     __first_cut = upper_bound(__first, __middle, *__second_cut);
    02005     distance(__first, __first_cut, __len11);
    02006   }
    02007   _BidirectionalIter __new_middle
    02008     = rotate(__first_cut, __middle, __second_cut);
    02009   __merge_without_buffer(__first, __first_cut, __new_middle,
    02010                          __len11, __len22);
    02011   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
    02012                          __len2 - __len22);
    02013 }
    02014
    02015 template <class _BidirectionalIter, class _Distance, class _Compare>
    02016 void __merge_without_buffer(_BidirectionalIter __first,
    02017                             _BidirectionalIter __middle,
    02018                             _BidirectionalIter __last,
    02019                             _Distance __len1, _Distance __len2,
    02020                             _Compare __comp) {
    02021   if (__len1 == 0 || __len2 == 0)
    02022     return;
    02023   if (__len1 + __len2 == 2) {
    02024     if (__comp(*__middle, *__first))
    02025       iter_swap(__first, __middle);
    02026     return;
    02027   }
    02028   _BidirectionalIter __first_cut = __first;
    02029   _BidirectionalIter __second_cut = __middle;
    02030   _Distance __len11 = 0;
    02031   _Distance __len22 = 0;
    02032   if (__len1 > __len2) {
    02033     __len11 = __len1 / 2;
    02034     advance(__first_cut, __len11);
    02035     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
    02036     distance(__middle, __second_cut, __len22);
    02037   }
    02038   else {
    02039     __len22 = __len2 / 2;
    02040     advance(__second_cut, __len22);
    02041     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
    02042     distance(__first, __first_cut, __len11);
    02043   }
    02044   _BidirectionalIter __new_middle
    02045     = rotate(__first_cut, __middle, __second_cut);
    02046   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
    02047                          __comp);
    02048   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
    02049                          __len2 - __len22, __comp);
    02050 }
    02051
    02052 template <class _BidirectionalIter1, class _BidirectionalIter2,
    02053           class _Distance>
    02054 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
    02055                                       _BidirectionalIter1 __middle,
    02056                                       _BidirectionalIter1 __last,
    02057                                       _Distance __len1, _Distance __len2,
    02058                                       _BidirectionalIter2 __buffer,
    02059                                       _Distance __buffer_size) {
    02060   _BidirectionalIter2 __buffer_end;
    02061   if (__len1 > __len2 && __len2 <= __buffer_size) {
    02062     __buffer_end = copy(__middle, __last, __buffer);
    02063     copy_backward(__first, __middle, __last);
    02064     return copy(__buffer, __buffer_end, __first);
    02065   }
    02066   else if (__len1 <= __buffer_size) {
    02067     __buffer_end = copy(__first, __middle, __buffer);
    02068     copy(__middle, __last, __first);
    02069     return copy_backward(__buffer, __buffer_end, __last);
    02070   }
    02071   else
    02072     return rotate(__first, __middle, __last);
    02073 }
    02074
    02075 template <class _BidirectionalIter1, class _BidirectionalIter2,
    02076           class _BidirectionalIter3>
    02077 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
    02078                                      _BidirectionalIter1 __last1,
    02079                                      _BidirectionalIter2 __first2,
    02080                                      _BidirectionalIter2 __last2,
    02081                                      _BidirectionalIter3 __result) {
    02082   if (__first1 == __last1)
    02083     return copy_backward(__first2, __last2, __result);
    02084   if (__first2 == __last2)
    02085     return copy_backward(__first1, __last1, __result);
    02086   --__last1;
    02087   --__last2;
    02088   while (true) {
    02089     if (*__last2 < *__last1) {
    02090       *--__result = *__last1;
    02091       if (__first1 == __last1)
    02092         return copy_backward(__first2, ++__last2, __result);
    02093       --__last1;
    02094     }
    02095     else {
    02096       *--__result = *__last2;
    02097       if (__first2 == __last2)
    02098         return copy_backward(__first1, ++__last1, __result);
    02099       --__last2;
    02100     }
    02101   }
    02102 }
    02103
    02104 template <class _BidirectionalIter1, class _BidirectionalIter2,
    02105           class _BidirectionalIter3, class _Compare>
    02106 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
    02107                                      _BidirectionalIter1 __last1,
    02108                                      _BidirectionalIter2 __first2,
    02109                                      _BidirectionalIter2 __last2,
    02110                                      _BidirectionalIter3 __result,
    02111                                      _Compare __comp) {
    02112   if (__first1 == __last1)
    02113     return copy_backward(__first2, __last2, __result);
    02114   if (__first2 == __last2)
    02115     return copy_backward(__first1, __last1, __result);
    02116   --__last1;
    02117   --__last2;
    02118   while (true) {
    02119     if (__comp(*__last2, *__last1)) {
    02120       *--__result = *__last1;
    02121       if (__first1 == __last1)
    02122         return copy_backward(__first2, ++__last2, __result);
    02123       --__last1;
    02124     }
    02125     else {
    02126       *--__result = *__last2;
    02127       if (__first2 == __last2)
    02128         return copy_backward(__first1, ++__last1, __result);
    02129       --__last2;
    02130     }
    02131   }
    02132 }
    02133
    02134 template <class _BidirectionalIter, class _Distance, class _Pointer>
    02135 void __merge_adaptive(_BidirectionalIter __first,
    02136                       _BidirectionalIter __middle,
    02137                       _BidirectionalIter __last,
    02138                       _Distance __len1, _Distance __len2,
    02139                       _Pointer __buffer, _Distance __buffer_size) {
    02140   if (__len1 <= __len2 && __len1 <= __buffer_size) {
    02141     _Pointer __buffer_end = copy(__first, __middle, __buffer);
    02142     merge(__buffer, __buffer_end, __middle, __last, __first);
    02143   }
    02144   else if (__len2 <= __buffer_size) {
    02145     _Pointer __buffer_end = copy(__middle, __last, __buffer);
    02146     __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
    02147   }
    02148   else {
    02149     _BidirectionalIter __first_cut = __first;
    02150     _BidirectionalIter __second_cut = __middle;
    02151     _Distance __len11 = 0;
    02152     _Distance __len22 = 0;
    02153     if (__len1 > __len2) {
    02154       __len11 = __len1 / 2;
    02155       advance(__first_cut, __len11);
    02156       __second_cut = lower_bound(__middle, __last, *__first_cut);
    02157       distance(__middle, __second_cut, __len22);
    02158     }
    02159     else {
    02160       __len22 = __len2 / 2;
    02161       advance(__second_cut, __len22);
    02162       __first_cut = upper_bound(__first, __middle, *__second_cut);
    02163       distance(__first, __first_cut, __len11);
    02164     }
    02165     _BidirectionalIter __new_middle =
    02166       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
    02167                         __len22, __buffer, __buffer_size);
    02168     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
    02169                      __len22, __buffer, __buffer_size);
    02170     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
    02171                      __len2 - __len22, __buffer, __buffer_size);
    02172   }
    02173 }
    02174
    02175 template <class _BidirectionalIter, class _Distance, class _Pointer,
    02176           class _Compare>
    02177 void __merge_adaptive(_BidirectionalIter __first,
    02178                       _BidirectionalIter __middle,
    02179                       _BidirectionalIter __last,
    02180                       _Distance __len1, _Distance __len2,
    02181                       _Pointer __buffer, _Distance __buffer_size,
    02182                       _Compare __comp) {
    02183   if (__len1 <= __len2 && __len1 <= __buffer_size) {
    02184     _Pointer __buffer_end = copy(__first, __middle, __buffer);
    02185     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
    02186   }
    02187   else if (__len2 <= __buffer_size) {
    02188     _Pointer __buffer_end = copy(__middle, __last, __buffer);
    02189     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
    02190                      __comp);
    02191   }
    02192   else {
    02193     _BidirectionalIter __first_cut = __first;
    02194     _BidirectionalIter __second_cut = __middle;
    02195     _Distance __len11 = 0;
    02196     _Distance __len22 = 0;
    02197     if (__len1 > __len2) {
    02198       __len11 = __len1 / 2;
    02199       advance(__first_cut, __len11);
    02200       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
    02201       distance(__middle, __second_cut, __len22);
    02202     }
    02203     else {
    02204       __len22 = __len2 / 2;
    02205       advance(__second_cut, __len22);
    02206       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
    02207       distance(__first, __first_cut, __len11);
    02208     }
    02209     _BidirectionalIter __new_middle =
    02210       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
    02211                         __len22, __buffer, __buffer_size);
    02212     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
    02213                      __len22, __buffer, __buffer_size, __comp);
    02214     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
    02215                      __len2 - __len22, __buffer, __buffer_size, __comp);
    02216   }
    02217 }
    02218
    02219 template <class _BidirectionalIter, class _Tp, class _Distance>
    02220 inline void __inplace_merge_aux(_BidirectionalIter __first,
    02221                                 _BidirectionalIter __middle,
    02222                                 _BidirectionalIter __last, _Tp*, _Distance*) {
    02223   _Distance __len1 = 0;
    02224   distance(__first, __middle, __len1);
    02225   _Distance __len2 = 0;
    02226   distance(__middle, __last, __len2);
    02227
    02228   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
    02229   if (__buf.begin() == 0)
    02230     __merge_without_buffer(__first, __middle, __last, __len1, __len2);
    02231   else
    02232     __merge_adaptive(__first, __middle, __last, __len1, __len2,
    02233                      __buf.begin(), _Distance(__buf.size()));
    02234 }
    02235
    02236 template <class _BidirectionalIter, class _Tp,
    02237           class _Distance, class _Compare>
    02238 inline void __inplace_merge_aux(_BidirectionalIter __first,
    02239                                 _BidirectionalIter __middle,
    02240                                 _BidirectionalIter __last, _Tp*, _Distance*,
    02241                                 _Compare __comp) {
    02242   _Distance __len1 = 0;
    02243   distance(__first, __middle, __len1);
    02244   _Distance __len2 = 0;
    02245   distance(__middle, __last, __len2);
    02246
    02247   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
    02248   if (__buf.begin() == 0)
    02249     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
    02250   else
    02251     __merge_adaptive(__first, __middle, __last, __len1, __len2,
    02252                      __buf.begin(), _Distance(__buf.size()),
    02253                      __comp);
    02254 }
    02255
    02256 template <class _BidirectionalIter>
    02257 inline void inplace_merge(_BidirectionalIter __first,
    02258                           _BidirectionalIter __middle,
    02259                           _BidirectionalIter __last) {
    02260   if (__first == __middle || __middle == __last)
    02261     return;
    02262   __inplace_merge_aux(__first, __middle, __last,
    02263                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
    02264 }
    02265
    02266 template <class _BidirectionalIter, class _Compare>
    02267 inline void inplace_merge(_BidirectionalIter __first,
    02268                           _BidirectionalIter __middle,
    02269                           _BidirectionalIter __last, _Compare __comp) {
    02270   if (__first == __middle || __middle == __last)
    02271     return;
    02272   __inplace_merge_aux(__first, __middle, __last,
    02273                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first),
    02274                       __comp);
    02275 }
    02276
    02277 // Set algorithms: includes, set_union, set_intersection, set_difference,
    02278 // set_symmetric_difference.  All of these algorithms have the precondition
    02279 // that their input ranges are sorted and the postcondition that their output
    02280 // ranges are sorted.
    02281
    02282 template <class _InputIter1, class _InputIter2>
    02283 bool includes(_InputIter1 __first1, _InputIter1 __last1,
    02284               _InputIter2 __first2, _InputIter2 __last2) {
    02285   while (__first1 != __last1 && __first2 != __last2)
    02286     if (*__first2 < *__first1)
    02287       return false;
    02288     else if(*__first1 < *__first2)
    02289       ++__first1;
    02290     else
    02291       ++__first1, ++__first2;
    02292
    02293   return __first2 == __last2;
    02294 }
    02295
    02296 template <class _InputIter1, class _InputIter2, class _Compare>
    02297 bool includes(_InputIter1 __first1, _InputIter1 __last1,
    02298               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
    02299   while (__first1 != __last1 && __first2 != __last2)
    02300     if (__comp(*__first2, *__first1))
    02301       return false;
    02302     else if(__comp(*__first1, *__first2))
    02303       ++__first1;
    02304     else
    02305       ++__first1, ++__first2;
    02306
    02307   return __first2 == __last2;
    02308 }
    02309
    02310 template <class _InputIter1, class _InputIter2, class _OutputIter>
    02311 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
    02312                       _InputIter2 __first2, _InputIter2 __last2,
    02313                       _OutputIter __result) {
    02314   while (__first1 != __last1 && __first2 != __last2) {
    02315     if (*__first1 < *__first2) {
    02316       *__result = *__first1;
    02317       ++__first1;
    02318     }
    02319     else if (*__first2 < *__first1) {
    02320       *__result = *__first2;
    02321       ++__first2;
    02322     }
    02323     else {
    02324       *__result = *__first1;
    02325       ++__first1;
    02326       ++__first2;
    02327     }
    02328     ++__result;
    02329   }
    02330   return copy(__first2, __last2, copy(__first1, __last1, __result));
    02331 }
    02332
    02333 template <class _InputIter1, class _InputIter2, class _OutputIter,
    02334           class _Compare>
    02335 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
    02336                       _InputIter2 __first2, _InputIter2 __last2,
    02337                       _OutputIter __result, _Compare __comp) {
    02338   while (__first1 != __last1 && __first2 != __last2) {
    02339     if (__comp(*__first1, *__first2)) {
    02340       *__result = *__first1;
    02341       ++__first1;
    02342     }
    02343     else if (__comp(*__first2, *__first1)) {
    02344       *__result = *__first2;
    02345       ++__first2;
    02346     }
    02347     else {
    02348       *__result = *__first1;
    02349       ++__first1;
    02350       ++__first2;
    02351     }
    02352     ++__result;
    02353   }
    02354   return copy(__first2, __last2, copy(__first1, __last1, __result));
    02355 }
    02356
    02357 template <class _InputIter1, class _InputIter2, class _OutputIter>
    02358 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
    02359                              _InputIter2 __first2, _InputIter2 __last2,
    02360                              _OutputIter __result) {
    02361   while (__first1 != __last1 && __first2 != __last2)
    02362     if (*__first1 < *__first2)
    02363       ++__first1;
    02364     else if (*__first2 < *__first1)
    02365       ++__first2;
    02366     else {
    02367       *__result = *__first1;
    02368       ++__first1;
    02369       ++__first2;
    02370       ++__result;
    02371     }
    02372   return __result;
    02373 }
    02374
    02375 template <class _InputIter1, class _InputIter2, class _OutputIter,
    02376           class _Compare>
    02377 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
    02378                              _InputIter2 __first2, _InputIter2 __last2,
    02379                              _OutputIter __result, _Compare __comp) {
    02380   while (__first1 != __last1 && __first2 != __last2)
    02381     if (__comp(*__first1, *__first2))
    02382       ++__first1;
    02383     else if (__comp(*__first2, *__first1))
    02384       ++__first2;
    02385     else {
    02386       *__result = *__first1;
    02387       ++__first1;
    02388       ++__first2;
    02389       ++__result;
    02390     }
    02391   return __result;
    02392 }
    02393
    02394 template <class _InputIter1, class _InputIter2, class _OutputIter>
    02395 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
    02396                            _InputIter2 __first2, _InputIter2 __last2,
    02397                            _OutputIter __result) {
    02398   while (__first1 != __last1 && __first2 != __last2)
    02399     if (*__first1 < *__first2) {
    02400       *__result = *__first1;
    02401       ++__first1;
    02402       ++__result;
    02403     }
    02404     else if (*__first2 < *__first1)
    02405       ++__first2;
    02406     else {
    02407       ++__first1;
    02408       ++__first2;
    02409     }
    02410   return copy(__first1, __last1, __result);
    02411 }
    02412
    02413 template <class _InputIter1, class _InputIter2, class _OutputIter,
    02414           class _Compare>
    02415 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
    02416                            _InputIter2 __first2, _InputIter2 __last2,
    02417                            _OutputIter __result, _Compare __comp) {
    02418   while (__first1 != __last1 && __first2 != __last2)
    02419     if (__comp(*__first1, *__first2)) {
    02420       *__result = *__first1;
    02421       ++__first1;
    02422       ++__result;
    02423     }
    02424     else if (__comp(*__first2, *__first1))
    02425       ++__first2;
    02426     else {
    02427       ++__first1;
    02428       ++__first2;
    02429     }
    02430   return copy(__first1, __last1, __result);
    02431 }
    02432
    02433 template <class _InputIter1, class _InputIter2, class _OutputIter>
    02434 _OutputIter
    02435 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
    02436                          _InputIter2 __first2, _InputIter2 __last2,
    02437                          _OutputIter __result) {
    02438   while (__first1 != __last1 && __first2 != __last2)
    02439     if (*__first1 < *__first2) {
    02440       *__result = *__first1;
    02441       ++__first1;
    02442       ++__result;
    02443     }
    02444     else if (*__first2 < *__first1) {
    02445       *__result = *__first2;
    02446       ++__first2;
    02447       ++__result;
    02448     }
    02449     else {
    02450       ++__first1;
    02451       ++__first2;
    02452     }
    02453   return copy(__first2, __last2, copy(__first1, __last1, __result));
    02454 }
    02455
    02456 template <class _InputIter1, class _InputIter2, class _OutputIter,
    02457           class _Compare>
    02458 _OutputIter
    02459 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
    02460                          _InputIter2 __first2, _InputIter2 __last2,
    02461                          _OutputIter __result,
    02462                          _Compare __comp) {
    02463   while (__first1 != __last1 && __first2 != __last2)
    02464     if (__comp(*__first1, *__first2)) {
    02465       *__result = *__first1;
    02466       ++__first1;
    02467       ++__result;
    02468     }
    02469     else if (__comp(*__first2, *__first1)) {
    02470       *__result = *__first2;
    02471       ++__first2;
    02472       ++__result;
    02473     }
    02474     else {
    02475       ++__first1;
    02476       ++__first2;
    02477     }
    02478   return copy(__first2, __last2, copy(__first1, __last1, __result));
    02479 }
    02480
    02481 // min_element and max_element, with and without an explicitly supplied
    02482 // comparison function.
    02483
    02484 template <class _ForwardIter>
    02485 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
    02486   if (__first == __last) return __first;
    02487   _ForwardIter __result = __first;
    02488   while (++__first != __last)
    02489     if (*__result < *__first)
    02490       __result = __first;
    02491   return __result;
    02492 }
    02493
    02494 template <class _ForwardIter, class _Compare>
    02495 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
    02496                             _Compare __comp) {
    02497   if (__first == __last) return __first;
    02498   _ForwardIter __result = __first;
    02499   while (++__first != __last)
    02500     if (__comp(*__result, *__first)) __result = __first;
    02501   return __result;
    02502 }
    02503
    02504 template <class _ForwardIter>
    02505 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
    02506   if (__first == __last) return __first;
    02507   _ForwardIter __result = __first;
    02508   while (++__first != __last)
    02509     if (*__first < *__result)
    02510       __result = __first;
    02511   return __result;
    02512 }
    02513
    02514 template <class _ForwardIter, class _Compare>
    02515 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
    02516                             _Compare __comp) {
    02517   if (__first == __last) return __first;
    02518   _ForwardIter __result = __first;
    02519   while (++__first != __last)
    02520     if (__comp(*__first, *__result))
    02521       __result = __first;
    02522   return __result;
    02523 }
    02524
    02525 // next_permutation and prev_permutation, with and without an explicitly
    02526 // supplied comparison function.
    02527
    02528 template <class _BidirectionalIter>
    02529 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
    02530   if (__first == __last)
    02531     return false;
    02532   _BidirectionalIter __i = __first;
    02533   ++__i;
    02534   if (__i == __last)
    02535     return false;
    02536   __i = __last;
    02537   --__i;
    02538
    02539   for(;;) {
    02540     _BidirectionalIter __ii = __i;
    02541     --__i;
    02542     if (*__i < *__ii) {
    02543       _BidirectionalIter __j = __last;
    02544       while (!(*__i < *--__j))
    02545         {}
    02546       iter_swap(__i, __j);
    02547       reverse(__ii, __last);
    02548       return true;
    02549     }
    02550     if (__i == __first) {
    02551       reverse(__first, __last);
    02552       return false;
    02553     }
    02554   }
    02555 }
    02556
    02557 template <class _BidirectionalIter, class _Compare>
    02558 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
    02559                       _Compare __comp) {
    02560   if (__first == __last)
    02561     return false;
    02562   _BidirectionalIter __i = __first;
    02563   ++__i;
    02564   if (__i == __last)
    02565     return false;
    02566   __i = __last;
    02567   --__i;
    02568
    02569   for(;;) {
    02570     _BidirectionalIter __ii = __i;
    02571     --__i;
    02572     if (__comp(*__i, *__ii)) {
    02573       _BidirectionalIter __j = __last;
    02574       while (!__comp(*__i, *--__j))
    02575         {}
    02576       iter_swap(__i, __j);
    02577       reverse(__ii, __last);
    02578       return true;
    02579     }
    02580     if (__i == __first) {
    02581       reverse(__first, __last);
    02582       return false;
    02583     }
    02584   }
    02585 }
    02586
    02587 template <class _BidirectionalIter>
    02588 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
    02589   if (__first == __last)
    02590     return false;
    02591   _BidirectionalIter __i = __first;
    02592   ++__i;
    02593   if (__i == __last)
    02594     return false;
    02595   __i = __last;
    02596   --__i;
    02597
    02598   for(;;) {
    02599     _BidirectionalIter __ii = __i;
    02600     --__i;
    02601     if (*__ii < *__i) {
    02602       _BidirectionalIter __j = __last;
    02603       while (!(*--__j < *__i))
    02604         {}
    02605       iter_swap(__i, __j);
    02606       reverse(__ii, __last);
    02607       return true;
    02608     }
    02609     if (__i == __first) {
    02610       reverse(__first, __last);
    02611       return false;
    02612     }
    02613   }
    02614 }
    02615
    02616 template <class _BidirectionalIter, class _Compare>
    02617 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
    02618                       _Compare __comp) {
    02619   if (__first == __last)
    02620     return false;
    02621   _BidirectionalIter __i = __first;
    02622   ++__i;
    02623   if (__i == __last)
    02624     return false;
    02625   __i = __last;
    02626   --__i;
    02627
    02628   for(;;) {
    02629     _BidirectionalIter __ii = __i;
    02630     --__i;
    02631     if (__comp(*__ii, *__i)) {
    02632       _BidirectionalIter __j = __last;
    02633       while (!__comp(*--__j, *__i))
    02634         {}
    02635       iter_swap(__i, __j);
    02636       reverse(__ii, __last);
    02637       return true;
    02638     }
    02639     if (__i == __first) {
    02640       reverse(__first, __last);
    02641       return false;
    02642     }
    02643   }
    02644 }
    02645
    02646 // find_first_of, with and without an explicitly supplied comparison function.
    02647
    02648 template <class _InputIter, class _ForwardIter>
    02649 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
    02650                          _ForwardIter __first2, _ForwardIter __last2)
    02651 {
    02652   for ( ; __first1 != __last1; ++__first1)
    02653     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
    02654       if (*__first1 == *__iter)
    02655         return __first1;
    02656   return __last1;
    02657 }
    02658
    02659 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
    02660 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
    02661                          _ForwardIter __first2, _ForwardIter __last2,
    02662                          _BinaryPredicate __comp)
    02663 {
    02664   for ( ; __first1 != __last1; ++__first1)
    02665     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
    02666       if (__comp(*__first1, *__iter))
    02667         return __first1;
    02668   return __last1;
    02669 }
    02670
    02671
    02672 // find_end, with and without an explicitly supplied comparison function.
    02673 // Search [first2, last2) as a subsequence in [first1, last1), and return
    02674 // the *last* possible match.  Note that find_end for bidirectional iterators
    02675 // is much faster than for forward iterators.
    02676
    02677 // find_end for forward iterators.
    02678 template <class _ForwardIter1, class _ForwardIter2>
    02679 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
    02680                          _ForwardIter2 __first2, _ForwardIter2 __last2,
    02681                          forward_iterator_tag, forward_iterator_tag)
    02682 {
    02683   if (__first2 == __last2)
    02684     return __last1;
    02685   else {
    02686     _ForwardIter1 __result = __last1;
    02687     while (1) {
    02688       _ForwardIter1 __new_result
    02689         = search(__first1, __last1, __first2, __last2);
    02690       if (__new_result == __last1)
    02691         return __result;
    02692       else {
    02693         __result = __new_result;
    02694         __first1 = __new_result;
    02695         ++__first1;
    02696       }
    02697     }
    02698   }
    02699 }
    02700
    02701 template <class _ForwardIter1, class _ForwardIter2,
    02702           class _BinaryPredicate>
    02703 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
    02704                          _ForwardIter2 __first2, _ForwardIter2 __last2,
    02705                          forward_iterator_tag, forward_iterator_tag,
    02706                          _BinaryPredicate __comp)
    02707 {
    02708   if (__first2 == __last2)
    02709     return __last1;
    02710   else {
    02711     _ForwardIter1 __result = __last1;
    02712     while (1) {
    02713       _ForwardIter1 __new_result
    02714         = search(__first1, __last1, __first2, __last2, __comp);
    02715       if (__new_result == __last1)
    02716         return __result;
    02717       else {
    02718         __result = __new_result;
    02719         __first1 = __new_result;
    02720         ++__first1;
    02721       }
    02722     }
    02723   }
    02724 }
    02725
    02726 // find_end for bidirectional iterators.  Requires partial specialization.
    02727 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    02728
    02729 template <class _BidirectionalIter1, class _BidirectionalIter2>
    02730 _BidirectionalIter1
    02731 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
    02732            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
    02733            bidirectional_iterator_tag, bidirectional_iterator_tag)
    02734 {
    02735   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
    02736   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
    02737
    02738   _RevIter1 __rlast1(__first1);
    02739   _RevIter2 __rlast2(__first2);
    02740   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
    02741                                _RevIter2(__last2), __rlast2);
    02742
    02743   if (__rresult == __rlast1)
    02744     return __last1;
    02745   else {
    02746     _BidirectionalIter1 __result = __rresult.base();
    02747     advance(__result, -distance(__first2, __last2));
    02748     return __result;
    02749   }
    02750 }
    02751
    02752 template <class _BidirectionalIter1, class _BidirectionalIter2,
    02753           class _BinaryPredicate>
    02754 _BidirectionalIter1
    02755 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
    02756            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
    02757            bidirectional_iterator_tag, bidirectional_iterator_tag,
    02758            _BinaryPredicate __comp)
    02759 {
    02760   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
    02761   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
    02762
    02763   _RevIter1 __rlast1(__first1);
    02764   _RevIter2 __rlast2(__first2);
    02765   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
    02766                                _RevIter2(__last2), __rlast2,
    02767                                __comp);
    02768
    02769   if (__rresult == __rlast1)
    02770     return __last1;
    02771   else {
    02772     _BidirectionalIter1 __result = __rresult.base();
    02773     advance(__result, -distance(__first2, __last2));
    02774     return __result;
    02775   }
    02776 }
    02777 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    02778
    02779 // Dispatching functions for find_end.
    02780
    02781 template <class _ForwardIter1, class _ForwardIter2>
    02782 inline _ForwardIter1
    02783 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
    02784          _ForwardIter2 __first2, _ForwardIter2 __last2)
    02785 {
    02786   return __find_end(__first1, __last1, __first2, __last2,
    02787                     __ITERATOR_CATEGORY(__first1),
    02788                     __ITERATOR_CATEGORY(__first2));
    02789 }
    02790
    02791 template <class _ForwardIter1, class _ForwardIter2,
    02792           class _BinaryPredicate>
    02793 inline _ForwardIter1
    02794 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
    02795          _ForwardIter2 __first2, _ForwardIter2 __last2,
    02796          _BinaryPredicate __comp)
    02797 {
    02798   return __find_end(__first1, __last1, __first2, __last2,
    02799                     __ITERATOR_CATEGORY(__first1),
    02800                     __ITERATOR_CATEGORY(__first2),
    02801                     __comp);
    02802 }
    02803
    02804 // is_heap, a predicate testing whether or not a range is
    02805 // a heap.  This function is an extension, not part of the C++
    02806 // standard.
    02807
    02808 template <class _RandomAccessIter, class _Distance>
    02809 bool __is_heap(_RandomAccessIter __first, _Distance __n)
    02810 {
    02811   _Distance __parent = 0;
    02812   for (_Distance __child = 1; __child < __n; ++__child) {
    02813     if (__first[__parent] < __first[__child])
    02814       return false;
    02815     if ((__child & 1) == 0)
    02816       ++__parent;
    02817   }
    02818   return true;
    02819 }
    02820
    02821 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
    02822 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
    02823                _Distance __n)
    02824 {
    02825   _Distance __parent = 0;
    02826   for (_Distance __child = 1; __child < __n; ++__child) {
    02827     if (__comp(__first[__parent], __first[__child]))
    02828       return false;
    02829     if ((__child & 1) == 0)
    02830       ++__parent;
    02831   }
    02832   return true;
    02833 }
    02834
    02835 template <class _RandomAccessIter>
    02836 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
    02837 {
    02838   return __is_heap(__first, __last - __first);
    02839 }
    02840
    02841
    02842 template <class _RandomAccessIter, class _StrictWeakOrdering>
    02843 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
    02844                     _StrictWeakOrdering __comp)
    02845 {
    02846   return __is_heap(__first, __comp, __last - __first);
    02847 }
    02848
    02849 // is_sorted, a predicated testing whether a range is sorted in
    02850 // nondescending order.  This is an extension, not part of the C++
    02851 // standard.
    02852
    02853 template <class _ForwardIter>
    02854 bool is_sorted(_ForwardIter __first, _ForwardIter __last)
    02855 {
    02856   if (__first == __last)
    02857     return true;
    02858
    02859   _ForwardIter __next = __first;
    02860   for (++__next; __next != __last; __first = __next, ++__next) {
    02861     if (*__next < *__first)
    02862       return false;
    02863   }
    02864
    02865   return true;
    02866 }
    02867
    02868 template <class _ForwardIter, class _StrictWeakOrdering>
    02869 bool is_sorted(_ForwardIter __first, _ForwardIter __last,
    02870                _StrictWeakOrdering __comp)
    02871 {
    02872   if (__first == __last)
    02873     return true;
    02874
    02875   _ForwardIter __next = __first;
    02876   for (++__next; __next != __last; __first = __next, ++__next) {
    02877     if (__comp(*__next, *__first))
    02878       return false;
    02879   }
    02880
    02881   return true;
    02882 }
    02883
    02884 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    02885 #pragma reset woff 1209
    02886 #endif
    02887
    02888 __STL_END_NAMESPACE
    02889
    02890 #endif /* __SGI_STL_INTERNAL_ALGO_H */
    02891
    02892 // Local Variables:
    02893 // mode:C++
    02894 // End: