home *** CD-ROM | disk | FTP | other *** search
/ Supercompiler 1997 / SUPERCOMPILER97.iso / MS_VC.50 / VC / INCLUDE / Algorithm < prev    next >
Encoding:
Text File  |  1996-12-04  |  46.4 KB  |  1,478 lines
  1. // algorithm standard header
  2. #ifndef _ALGORITHM_
  3. #define _ALGORITHM_
  4. #include <iterator>
  5. #include <memory>
  6. #include <xutility>
  7.  
  8. #ifdef  _MSC_VER
  9. #pragma pack(push,8)
  10. #endif  /* _MSC_VER */
  11. _STD_BEGIN
  12. const int _CHUNK_SIZE = 7;
  13. const int _SORT_MAX = 16;
  14.         // TEMPLATE FUNCTION _Median
  15. template<class _Ty> inline
  16.     _Ty _Median(_Ty _X, _Ty _Y, _Ty _Z)
  17.         {if (_X < _Y)
  18.             return (_Y < _Z ? _Y : _X < _Z ? _Z : _X);
  19.         else
  20.             return (_X < _Z ? _X : _Y < _Z ? _Z : _Y); }
  21.         // TEMPLATE FUNCTION _Median WITH PRED
  22. template<class _Ty, class _Pr> inline
  23.     _Ty _Median(_Ty _X, _Ty _Y, _Ty _Z, _Pr _P)
  24.         {if (_P(_X, _Y))
  25.             return (_P(_Y, _Z) ? _Y : _P(_X, _Z) ? _Z : _X);
  26.         else
  27.             return (_P(_X, _Z) ? _X : _P(_Y, _Z) ? _Z : _Y); }
  28.         // TEMPLATE FUNCTION for_each
  29. template<class _II, class _Fn> inline
  30.     _Fn for_each(_II _F, _II _L, _Fn _Op)
  31.     {for (; _F != _L; ++_F)
  32.         _Op(*_F);
  33.     return (_Op); }
  34.         // TEMPLATE FUNCTION find
  35. template<class _II, class _Ty> inline
  36.     _II find(_II _F, _II _L, const _Ty& _V)
  37.     {for (; _F != _L; ++_F)
  38.         if (*_F == _V)
  39.             break;
  40.     return (_F); }
  41.         // TEMPLATE FUNCTION find_if
  42. template<class _II, class _Pr> inline
  43.     _II find_if(_II _F, _II _L, _Pr _P)
  44.     {for (; _F != _L; ++_F)
  45.         if (_P(*_F))
  46.             break;
  47.     return (_F); }
  48.         // TEMPLATE FUNCTION adjacent_find
  49. template<class _FI> inline
  50.     _FI adjacent_find(_FI _F, _FI _L)
  51.     {for (_FI _Fb; (_Fb = _F) != _L && ++_F != _L; )
  52.         if (*_Fb == *_F)
  53.             return (_Fb);
  54.     return (_L); }
  55.         // TEMPLATE FUNCTION adjacent_find WITH PRED
  56. template<class _FI, class _Pr> inline
  57.     _FI adjacent_find(_FI _F, _FI _L, _Pr _P)
  58.     {for (_FI _Fb; (_Fb = _F) != _L && ++_F != _L; )
  59.         if (_P(*_Fb, *_F))
  60.             return (_Fb);
  61.     return (_L); }
  62.         // TEMPLATE FUNCTION count
  63. template<class _II, class _Ty> inline
  64.     _CNTSIZ(_II) count(_II _F, _II _L, const _Ty& _V)
  65.     {_CNTSIZ(_II) _N = 0;
  66.     for (; _F != _L; ++_F)
  67.         if (*_F == _V)
  68.             ++_N;
  69.     return (_N); }
  70.         // TEMPLATE FUNCTION count_if
  71. template<class _II, class _Pr> inline
  72.     _CNTSIZ(_II) count_if(_II _F, _II _L, _Pr _P)
  73.     {_CNTSIZ(_II) _N = 0;
  74.     for (; _F != _L; ++_F)
  75.         if (_P(*_F))
  76.             ++_N;
  77.     return (_N); }
  78.         // TEMPLATE FUNCTION search
  79. template<class _FI1, class _FI2> inline
  80.     _FI1 search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2)
  81.     {return (_Search(_F1, _L1, _F2, _L2,
  82.         _Dist_type(_F1), _Dist_type(_F2))); }
  83. template<class _FI1, class _FI2, class _Pd1, class _Pd2> inline
  84.     _FI1 _Search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
  85.         _Pd1 *, _Pd2 *)
  86.     {_Pd1 _D1 = 0;
  87.     _Distance(_F1, _L1, _D1);
  88.     _Pd2 _D2 = 0;
  89.     _Distance(_F2, _L2, _D2);
  90.     for (; _D2 <= _D1; ++_F1, --_D1)
  91.         {_FI1 _X1 = _F1;
  92.         for (_FI2 _X2 = _F2; ; ++_X1, ++_X2)
  93.             if (_X2 == _L2)
  94.                 return (_F1);
  95.             else if (!(*_X1 == *_X2))
  96.                 break; }
  97.     return (_L1); }
  98.         // TEMPLATE FUNCTION search WITH PRED
  99. template<class _FI1, class _FI2, class _Pr> inline
  100.     _FI1 search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pr _P)
  101.     {return (_Search(_F1, _L1, _F2, _L2, _P,
  102.         _Dist_type(_F1), _Dist_type(_F2))); }
  103. template<class _FI1, class _FI2, class _Pd1, class _Pd2,
  104.     class _Pr> inline
  105.     _FI1 _Search(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
  106.         _Pr _P, _Pd1 *, _Pd2 *)
  107.     {_Pd1 _D1 = 0;
  108.     _Distance(_F1, _L1, _D1);
  109.     _Pd2 _D2 = 0;
  110.     _Distance(_F2, _L2, _D2);
  111.     for (; _D2 <= _D1; ++_F1, --_D1)
  112.         {_FI1 _X1 = _F1;
  113.         for (_FI2 _X2 = _F2; ; ++_X1, ++_X2)
  114.             if (_X2 == _L2)
  115.                 return (_F1);
  116.             else if (!_P(*_X1, *_X2))
  117.                 break; }
  118.     return (_L1); }
  119.         // TEMPLATE FUNCTION search_n
  120. template<class _FI1, class _Pd2, class _Ty> inline
  121.     _FI1 search_n(_FI1 _F1, _FI1 _L1, _Pd2 _N, const _Ty& _V)
  122.     {return (_Search_n(_F1, _L1, _N, _V, _Dist_type(_F1))); }
  123. template<class _FI1, class _Pd2, class _Ty, class _Pd1> inline
  124.     _FI1 _Search_n(_FI1 _F1, _FI1 _L1,
  125.         _Pd2 _N, const _Ty& _V, _Pd1 *)
  126.     {_Pd1 _D1 = 0;
  127.     _Distance(_F1, _L1, _D1);
  128.     for (; _N <= _D1; ++_F1, --_D1)
  129.         {_FI1 _X1 = _F1;
  130.         for (_Pd2 _D2 = _N; ; ++_X1, --_D2)
  131.             if (_D2 == 0)
  132.                 return (_F1);
  133.             else if (!(*_X1 == _V))
  134.                 break; }
  135.     return (_L1); }
  136.         // TEMPLATE FUNCTION search_n WITH PRED
  137. template<class _FI1, class _Pd2, class _Ty, class _Pr> inline
  138.     _FI1 search_n(_FI1 _F1, _FI1 _L1,
  139.         _Pd2 _N, const _Ty& _V, _Pr _P)
  140.     {return (_Search_n(_F1, _L1,
  141.         _N, _V, _P, _Dist_type(_F1))); }
  142. template<class _FI1, class _Pd2,
  143.     class _Ty, class _Pd1, class _Pr> inline
  144.     _FI1 _Search_n(_FI1 _F1, _FI1 _L1,
  145.         _Pd2 _N, const _Ty& _V, _Pr _P, _Pd1 *)
  146.     {_Pd1 _D1 = 0;
  147.     _Distance(_F1, _L1, _D1);
  148.     for (; _N <= _D1; ++_F1, --_D1)
  149.         {_FI1 _X1 = _F1;
  150.         for (_Pd2 _D2 = _N; ; ++_X1, --_D2)
  151.             if (_D2 == 0)
  152.                 return (_F1);
  153.             else if (!_P(*_X1, _V))
  154.                 break; }
  155.     return (_L1); }
  156.         // TEMPLATE FUNCTION find_end
  157. template<class _FI1, class _FI2> inline
  158.     _FI1 find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2)
  159.     {return (_Find_end(_F1, _L1, _F2, _L2,
  160.         _Dist_type(_F1), _Dist_type(_F2))); }
  161. template<class _FI1, class _FI2, class _Pd1, class _Pd2> inline
  162.     _FI1 _Find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
  163.         _Pd1 *, _Pd2 *)
  164.     {_Pd1 _D1 = 0;
  165.     _Distance(_F1, _L1, _D1);
  166.     _Pd2 _D2 = 0;
  167.     _Distance(_F2, _L2, _D2);
  168.     _FI1 _Ans = _L1;
  169.     if (0 < _D2)
  170.         for (; _D2 <= _D1; ++_F1, --_D1)
  171.             {_FI1 _X1 = _F1;
  172.             for (_FI2 _X2 = _F2; ; ++_X1)
  173.                 if (!(*_X1 == *_X2))
  174.                     break;
  175.                 else if (++_X2 == _L2)
  176.                     {_Ans = _F1;
  177.                     break; }}
  178.     return (_Ans); }
  179.         // TEMPLATE FUNCTION find_end WITH PRED
  180. template<class _FI1, class _FI2, class _Pr> inline
  181.     _FI1 find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pr _P)
  182.     {return (_Find_end(_F1, _L1, _F2, _L2, _P,
  183.         _Dist_type(_F1), _Dist_type(_F2))); }
  184. template<class _FI1, class _FI2, class _Pd1, class _Pd2,
  185.     class _Pr> inline
  186.     _FI1 _Find_end(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2, _Pr _P,
  187.         _Pd1 *, _Pd2 *)
  188.     {_Pd1 _D1 = 0;
  189.     _Distance(_F1, _L1, _D1);
  190.     _Pd2 _D2 = 0;
  191.     _Distance(_F2, _L2, _D2);
  192.     _FI1 _Ans = _L1;
  193.     if (0 < _D2)
  194.         for (; _D2 <= _D1; ++_F1, --_D1)
  195.             {_FI1 _X1 = _F1;
  196.             for (_FI2 _X2 = _F2; ; ++_X1)
  197.                 if (!_P(*_X1, *_X2))
  198.                     break;
  199.                 else if (++_X2 == _L2)
  200.                     {_Ans = _F1;
  201.                     break; }}
  202.     return (_Ans); }
  203.         // TEMPLATE FUNCTION find_first_of
  204. template<class _FI1, class _FI2> inline
  205.     _FI1 find_first_of(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2)
  206.     {for (; _F1 != _L1; ++_F1)
  207.         for (_FI2 _X2 = _F2; _X2 != _L2; ++_X2)
  208.             if (*_F1 == *_X2)
  209.                 return (_F1);
  210.     return (_F1); }
  211.         // TEMPLATE FUNCTION find_first_of WITH PRED
  212. template<class _FI1, class _FI2, class _Pr> inline
  213.     _FI1 find_first_of(_FI1 _F1, _FI1 _L1, _FI2 _F2, _FI2 _L2,
  214.         _Pr _P)
  215.     {for (; _F1 != _L1; ++_F1)
  216.         for (_FI2 _X2 = _F2; _X2 != _L2; ++_X2)
  217.             if (_P(*_F1, *_X2))
  218.                 return (_F1);
  219.     return (_F1); }
  220.         // TEMPLATE FUNCTION iter_swap
  221. template<class _FI1, class _FI2> inline
  222.     void iter_swap(_FI1 _X, _FI2 _Y)
  223.     {_Iter_swap(_X, _Y, _Val_type(_X)); }
  224. template<class _FI1, class _FI2, class _Ty> inline
  225.     void _Iter_swap(_FI1 _X, _FI2 _Y, _Ty *)
  226.     {_Ty _Tmp = *_X;
  227.     *_X = *_Y, *_Y = _Tmp; }
  228.         // TEMPLATE FUNCTION swap_ranges
  229. template<class _FI1, class _FI2> inline
  230.     _FI2 swap_ranges(_FI1 _F, _FI1 _L, _FI2 _X)
  231.     {for (; _F != _L; ++_F, ++_X)
  232.         iter_swap(_F, _X);
  233.     return (_X); }
  234.         // TEMPLATE FUNCTION transform WITH UNARY OP
  235. template<class _II, class _OI, class _Uop> inline
  236.     _OI transform(_II _F, _II _L, _OI _X, _Uop _U)
  237.     {for (; _F != _L; ++_F, ++_X)
  238.         *_X = _U(*_F);
  239.     return (_X); }
  240.         // TEMPLATE FUNCTION transform WITH BINARY OP
  241. template<class _II1, class _II2, class _OI, class _Bop> inline
  242.     _OI transform(_II1 _F1, _II1 _L1, _II2 _F2, _OI _X, _Bop _B)
  243.     {for (; _F1 != _L1; ++_F1, ++_F2, ++_X)
  244.         *_X = _B(*_F1, *_F2);
  245.     return (_X); }
  246.         // TEMPLATE FUNCTION replace
  247. template<class _FI, class _Ty> inline
  248.     void replace(_FI _F, _FI _L, const _Ty& _Vo, const _Ty& _Vn)
  249.     {for (; _F != _L; ++_F)
  250.         if (*_F == _Vo)
  251.             *_F = _Vn; }
  252.         // TEMPLATE FUNCTION replace_if
  253. template<class _FI, class _Pr, class _Ty> inline
  254.     void replace_if(_FI _F, _FI _L, _Pr _P, const _Ty& _V)
  255.     {for (; _F != _L; ++_F)
  256.         if (_P(*_F))
  257.             *_F = _V; }
  258.         // TEMPLATE FUNCTION replace_copy
  259. template<class _II, class _OI, class _Ty> inline
  260.     _OI replace_copy(_II _F, _II _L, _OI _X,
  261.         const _Ty& _Vo, const _Ty& _Vn)
  262.     {for (; _F != _L; ++_F, ++_X)
  263.         *_X = *_F == _Vo ? _Vn : *_F;
  264.         return (_X); }
  265.         // TEMPLATE FUNCTION replace_copy_if
  266. template<class _II, class _OI, class _Pr, class _Ty> inline
  267.     _OI replace_copy_if(_II _F, _II _L, _OI _X,
  268.         _Pr _P, const _Ty& _V)
  269.     {for (; _F != _L; ++_F, ++_X)
  270.         *_X = _P(*_F) ? _V : *_F;
  271.         return (_X); }
  272.         // TEMPLATE FUNCTION generate
  273. template<class _FI, class _Gen> inline
  274.     void generate(_FI _F, _FI _L, _Gen _G)
  275.     {for (; _F != _L; ++_F)
  276.         *_F = _G(); }
  277.         // TEMPLATE FUNCTION generate_n
  278. template<class _OI, class _Pd, class _Gen> inline
  279.     void generate_n(_OI _F, _Pd _N, _Gen _G)
  280.     {for (; 0 < _N; --_N, ++_F)
  281.         *_F = _G(); }
  282.         // TEMPLATE FUNCTION remove
  283. template<class _FI, class _Ty> inline
  284.     _FI remove(_FI _F, _FI _L, const _Ty& _V)
  285.     {_F = find(_F, _L, _V);
  286.     if (_F == _L)
  287.         return (_F);
  288.     else
  289.         {_FI _Fb = _F;
  290.         return (remove_copy(++_F, _L, _Fb, _V)); }}
  291.         // TEMPLATE FUNCTION remove_if
  292. template<class _FI, class _Pr> inline
  293.     _FI remove_if(_FI _F, _FI _L, _Pr _P)
  294.     {_F = find_if(_F, _L, _P);
  295.     if (_F == _L)
  296.         return (_F);
  297.     else
  298.         {_FI _Fb = _F;
  299.         return (remove_copy_if(++_F, _L, _Fb, _P)); }}
  300.         // TEMPLATE FUNCTION remove_copy
  301. template<class _II, class _OI, class _Ty> inline
  302.     _OI remove_copy(_II _F, _II _L, _OI _X, const _Ty& _V)
  303.     {for (; _F != _L; ++_F)
  304.         if (!(*_F == _V))
  305.             *_X++ = *_F;
  306.     return (_X); }
  307.         // TEMPLATE FUNCTION remove_copy_if
  308. template<class _II, class _OI, class _Pr> inline
  309.     _OI remove_copy_if(_II _F, _II _L, _OI _X, _Pr _P)
  310.     {for (; _F != _L; ++_F)
  311.         if (!_P(*_F))
  312.             *_X++ = *_F;
  313.     return (_X); }
  314.         // TEMPLATE FUNCTION unique
  315. template<class _FI> inline
  316.     _FI unique(_FI _F, _FI _L)
  317.     {_F = adjacent_find(_F, _L);
  318.     return (unique_copy(_F, _L, _F)); }
  319.         // TEMPLATE FUNCTION unique WITH PRED
  320. template<class _FI, class _Pr> inline
  321.     _FI unique(_FI _F, _FI _L, _Pr _P)
  322.     {_F = adjacent_find(_F, _L, _P);
  323.     return (unique_copy(_F, _L, _F, _P)); }
  324.         // TEMPLATE FUNCTION unique_copy
  325. template<class _II, class _OI> inline
  326.     _OI unique_copy(_II _F, _II _L, _OI _X)
  327.     {return (_F == _L ? _X :
  328.         _Unique_copy(_F, _L, _X, _Iter_cat(_F))); }
  329. template<class _II, class _OI> inline
  330.     _OI _Unique_copy(_II _F, _II _L, _OI _X, input_iterator_tag)
  331.     {return (_Unique_copy(_F, _L, _X, _Val_type(_F))); }
  332. template<class _II, class _OI, class _Ty> inline
  333.     _OI _Unique_copy(_II _F, _II _L, _OI _X, _Ty *)
  334.     {_Ty _V = *_F;
  335.     for (*_X++ = _V; ++_F != _L; )
  336.         if (!(_V == *_F))
  337.             _V = *_F, *_X++ = _V;
  338.     return (_X); }
  339. template<class _FI, class _OI> inline
  340.     _OI _Unique_copy(_FI _F, _FI _L, _OI _X, forward_iterator_tag)
  341.     {_FI _Fb = _F;
  342.     for (*_X++ = *_Fb; ++_F != _L; )
  343.         if (!(*_Fb == *_F))
  344.             _Fb = _F, *_X++ = *_Fb;
  345.     return (_X); }
  346. template<class _BI, class _OI> inline
  347.     _OI _Unique_copy(_BI _F, _BI _L, _OI _X,
  348.         bidirectional_iterator_tag)
  349.     {return (_Unique_copy(_F, _L, _X, forward_iterator_tag())); }
  350. template<class _RI, class _OI> inline
  351.     _OI _Unique_copy(_RI _F, _RI _L, _OI _X,
  352.         random_access_iterator_tag)
  353.     {return (_Unique_copy(_F, _L, _X, forward_iterator_tag())); }
  354.         // TEMPLATE FUNCTION unique_copy WITH PRED
  355. template<class _II, class _OI, class _Pr> inline
  356.     _OI unique_copy(_II _F, _II _L, _OI _X, _Pr _P)
  357.     {return (_F == _L ? _X :
  358.         _Unique_copy(_F, _L, _X, _P, _Iter_cat(_F))); }
  359. template<class _II, class _OI, class _Pr> inline
  360.     _OI _Unique_copy(_II _F, _II _L, _OI _X, _Pr _P,
  361.         input_iterator_tag)
  362.     {return (_Unique_copy(_F, _L, _X, _P, _Val_type(_F))); }
  363. template<class _II, class _OI, class _Ty, class _Pr> inline
  364.     _OI _Unique_copy(_II _F, _II _L, _OI _X, _Pr _P, _Ty *)
  365.     {_Ty _V = *_F;
  366.     for (*_X++ = _V; ++_F != _L; )
  367.         if (!_P(_V, *_F))
  368.             _V = *_F, *_X++ = _V;
  369.     return (_X); }
  370. template<class _FI, class _OI, class _Pr> inline
  371.     _OI _Unique_copy(_FI _F, _FI _L, _OI _X, _Pr _P,
  372.         forward_iterator_tag)
  373.     {_FI _Fb = _F;
  374.     for (*_X++ = *_Fb; ++_F != _L; )
  375.         if (!_P(*_Fb, *_F))
  376.             _Fb = _F, *_X++ = *_Fb;
  377.     return (_X); }
  378. template<class _BI, class _OI, class _Pr> inline
  379.     _OI _Unique_copy(_BI _F, _BI _L, _OI _X, _Pr _P,
  380.         bidirectional_iterator_tag)
  381.     {return (_Unique_copy(_F, _L, _X, _P,
  382.         forward_iterator_tag())); }
  383. template<class _RI, class _OI, class _Pr> inline
  384.     _OI _Unique_copy(_RI _F, _RI _L, _OI _X, _Pr _P,
  385.         random_access_iterator_tag)
  386.     {return (_Unique_copy(_F, _L, _X, _P,
  387.         forward_iterator_tag())); }
  388.         // TEMPLATE FUNCTION reverse
  389. template<class _BI> inline
  390.     void reverse(_BI _F, _BI _L)
  391.     {_Reverse(_F, _L, _Iter_cat(_F)); }
  392. template<class _BI> inline
  393.     void _Reverse(_BI _F, _BI _L, bidirectional_iterator_tag)
  394.     {for (; _F != _L && _F != --_L; ++_F)
  395.         iter_swap(_F, _L); }
  396. template<class _RI> inline
  397.     void _Reverse(_RI _F, _RI _L, random_access_iterator_tag)
  398.     {for (; _F < _L; ++_F)
  399.         iter_swap(_F, --_L); }
  400.         // TEMPLATE FUNCTION reverse_copy
  401. template<class _BI, class _OI> inline
  402.     _OI reverse_copy(_BI _F, _BI _L, _OI _X)
  403.     {for (; _F != _L; ++_X)
  404.         *_X = *--_L;
  405.     return (_X); }
  406.         // TEMPLATE FUNCTION rotate
  407. template<class _FI> inline
  408.     void rotate(_FI _F, _FI _M, _FI _L)
  409.     {if (_F != _M && _M != _L)
  410.         _Rotate(_F, _M, _L, _Iter_cat(_F)); }
  411. template<class _FI> inline
  412.     void _Rotate(_FI _F, _FI _M, _FI _L,
  413.         forward_iterator_tag)
  414.     {for (_FI _X = _M; ; )
  415.         {iter_swap(_F, _X);
  416.         if (++_F == _M)
  417.             if (++_X == _L)
  418.                 break;
  419.             else
  420.                 _M = _X;
  421.         else if (++_X == _L)
  422.             _X = _M; }}
  423. template<class _BI> inline
  424.     void _Rotate(_BI _F, _BI _M, _BI _L,
  425.         bidirectional_iterator_tag)
  426.     {reverse(_F, _M);
  427.     reverse(_M, _L);
  428.     reverse(_F, _L); }
  429. template<class _RI> inline
  430.     void _Rotate(_RI _F, _RI _M, _RI _L,
  431.             random_access_iterator_tag)
  432.     {_Rotate(_F, _M, _L, _Dist_type(_F), _Val_type(_F)); }
  433. template<class _RI, class _Pd, class _Ty> inline
  434.     void _Rotate(_RI _F, _RI _M, _RI _L, _Pd *, _Ty *)
  435.     {_Pd _D = _M - _F;
  436.     _Pd _N = _L - _F;
  437.     for (_Pd _I = _D; _I != 0; )
  438.         {_Pd _J = _N % _I;
  439.         _N = _I, _I = _J; }
  440.     if (_N < _L - _F)
  441.         for (; 0 < _N; --_N)
  442.             {_RI _X = _F + _N;
  443.             _RI _Y = _X;
  444.             _Ty _V = *_X;
  445.             _RI _Z = _Y + _D == _L ? _F : _Y + _D;
  446.             while (_Z != _X)
  447.                 {*_Y = *_Z;
  448.                 _Y = _Z;
  449.                 _Z = _D < _L - _Z ? _Z + _D
  450.                     : _F + (_D - (_L - _Z)); }
  451.             *_Y = _V; }}
  452.         // TEMPLATE FUNCTION rotate_copy
  453. template<class _FI, class _OI> inline
  454.     _OI rotate_copy(_FI _F, _FI _M, _FI _L, _OI _X)
  455.     {return (copy(_F, _M, copy(_M, _L, _X))); }
  456.         // TEMPLATE FUNCTION random_shuffle
  457. template<class _RI> inline
  458.     void random_shuffle(_RI _F, _RI _L)
  459.     {if (_F != _L)
  460.         _Random_shuffle(_F, _L, _Dist_type(_F)); }
  461. template<class _RI, class _Pd> inline
  462.     void _Random_shuffle(_RI _F, _RI _L, _Pd *)
  463.     {const int _RBITS = 15;
  464.     const int _RMAX = (1U << _RBITS) - 1;
  465.     _RI _X = _F;
  466.     for (_Pd _D = 1; ++_X != _L; ++_D)
  467.         {unsigned long _Rm = _RMAX;
  468.         unsigned long _Rn = rand() & _RMAX;
  469.         for (; _Rm < _D && _Rm != ~0UL;
  470.             _Rm = _Rm << _RBITS | _RMAX)
  471.             _Rn = _Rn << _RBITS | _RMAX;
  472.         iter_swap(_X, _F + _Pd(_Rn % _D)); }}
  473. template<class _RI, class _Pf> inline
  474.     void random_shuffle(_RI _F, _RI _L, _Pf& _R)
  475.     {if (_F != _L)
  476.         _Random_shuffle(_F, _L, _R, _Dist_type(_F)); }
  477. template<class _RI, class _Pf, class _Pd> inline
  478.     void _Random_shuffle(_RI _F, _RI _L, _Pf& _R, _Pd *)
  479.     {_RI _X = _F;
  480.     for (_Pd _D = 1; ++_X != _L; ++_D)
  481.         iter_swap(_X, _F + _Pd(_R(_D))); }
  482.         // TEMPLATE FUNCTION partition
  483. template<class _BI, class _Pr> inline
  484.     _BI partition(_BI _F, _BI _L, _Pr _P)
  485.     {for (; ; ++_F)
  486.         {for (; _F != _L && _P(*_F); ++_F)
  487.             ;
  488.         if (_F == _L)
  489.             break;
  490.         for (; _F != --_L && !_P(*_L); )
  491.             ;
  492.         if (_F == _L)
  493.             break;
  494.         iter_swap(_F, _L); }
  495.     return (_F); }
  496.         // TEMPLATE FUNCTION stable_partition
  497. template<class _FI, class _Pr> inline
  498.     _FI stable_partition(_FI _F, _FI _L, _Pr _P)
  499.     {return (_F == _L ? _F : _Stable_partition(_F, _L, _P,
  500.         _Dist_type(_F), _Val_type(_F))); }
  501. template<class _FI, class _Pr, class _Pd, class _Ty> inline
  502.     _FI _Stable_partition(_FI _F, _FI _L, _Pr _P, _Pd *, _Ty *)
  503.     {_Pd _N = 0;
  504.     _Distance(_F, _L, _N);
  505.     _Temp_iterator<_Ty> _Xb(_N);
  506.     return (_Stable_partition(_F, _L, _P, _N, _Xb)); }
  507. template<class _FI, class _Pr, class _Pd, class _Ty> inline
  508.     _FI _Stable_partition(_FI _F, _FI _L, _Pr _P, _Pd _N,
  509.         _Temp_iterator<_Ty>& _Xb)
  510.     {if (_N == 1)
  511.         return (_P(*_F) ? _L : _F);
  512.     else if (_N <= _Xb._Maxlen())
  513.         {_FI _X = _F;
  514.         for (_Xb._Init(); _F != _L; ++_F)
  515.             if (_P(*_F))
  516.                 *_X++ = *_F;
  517.             else
  518.                 *_Xb++ = *_F;
  519.         copy(_Xb._First(), _Xb._Last(), _X);
  520.         return (_X); }
  521.     else
  522.         {_FI _M = _F;
  523.         advance(_M, _N / 2);
  524.         _FI _Lp = _Stable_partition(_F, _M, _P, _N / 2, _Xb);
  525.         _FI _Rp = _Stable_partition(_M, _L, _P, _N - _N / 2, _Xb);
  526.         _Pd _D1 = 0;
  527.         _Distance(_Lp, _M, _D1);
  528.         _Pd _D2 = 0;
  529.         _Distance(_M, _Rp, _D2);
  530.         return (_Buffered_rotate(_Lp, _M, _Rp, _D1, _D2, _Xb)); }}
  531.         // TEMPLATE FUNCTION sort
  532. template<class _RI> inline
  533.     void sort(_RI _F, _RI _L)
  534.     {_Sort_0(_F, _L, _Val_type(_F)); }
  535. template<class _RI, class _Ty> inline
  536.     void _Sort_0(_RI _F, _RI _L, _Ty *)
  537.     {if (_L - _F <= _SORT_MAX)
  538.         _Insertion_sort(_F, _L);
  539.     else
  540.         {_Sort(_F, _L, (_Ty *)0);
  541.         _Insertion_sort(_F, _F + _SORT_MAX);
  542.         for (_F += _SORT_MAX; _F != _L; ++_F)
  543.             _Unguarded_insert(_F, _Ty(*_F)); }}
  544. template<class _RI, class _Ty> inline
  545.     void _Sort(_RI _F, _RI _L, _Ty *)
  546.     {for (; _SORT_MAX < _L - _F; )
  547.         {_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
  548.             _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1))));
  549.         if (_L - _M <= _M - _F)
  550.             _Sort(_M, _L, _Val_type(_F)), _L = _M;
  551.         else
  552.             _Sort(_F, _M, _Val_type(_F)), _F = _M; }}
  553. template<class _RI, class _Ty> inline
  554.     _RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv)
  555.     {for (; ; ++_F)
  556.         {for (; *_F < _Piv; ++_F)
  557.             ;
  558.         for (; _Piv < *--_L; )
  559.             ;
  560.         if (_L <= _F)
  561.             return (_F);
  562.         iter_swap(_F, _L); }}
  563. template<class _RI> inline
  564.     void _Insertion_sort(_RI _F, _RI _L)
  565.     {_Insertion_sort_1(_F, _L, _Val_type(_F)); }
  566. template<class _BI, class _Ty> inline
  567.     void _Insertion_sort_1(_BI _F, _BI _L, _Ty *)
  568.     {if (_F != _L)
  569.         for (_BI _M = _F; ++_M != _L; )
  570.             {_Ty _V = *_M;
  571.             if (!(_V < *_F))
  572.                 _Unguarded_insert(_M, _V);
  573.             else
  574.                 {copy_backward(_F, _M, _M + 1);
  575.                 *_F = _V; }}}
  576. template<class _BI, class _Ty> inline
  577.     void _Unguarded_insert(_BI _L, _Ty _V)
  578.     {for (_BI _M = _L; _V < *--_M; _L = _M)
  579.         *_L = *_M;
  580.     *_L = _V; }
  581.         // TEMPLATE FUNCTION sort WITH PRED
  582. template<class _RI, class _Pr> inline
  583.     void sort(_RI _F, _RI _L, _Pr _P)
  584.     {_Sort_0(_F, _L, _P, _Val_type(_F)); }
  585. template<class _RI, class _Ty, class _Pr> inline
  586.     void _Sort_0(_RI _F, _RI _L, _Pr _P, _Ty *)
  587.     {if (_L - _F <= _SORT_MAX)
  588.         _Insertion_sort(_F, _L, _P);
  589.     else
  590.         {_Sort(_F, _L, _P, (_Ty *)0);
  591.         _Insertion_sort(_F, _F + _SORT_MAX, _P);
  592.         for (_F += _SORT_MAX; _F != _L; ++_F)
  593.             _Unguarded_insert(_F, _Ty(*_F), _P); }}
  594. template<class _RI, class _Ty, class _Pr> inline
  595.     void _Sort(_RI _F, _RI _L, _Pr _P, _Ty *)
  596.     {for (; _SORT_MAX < _L - _F; )
  597.         {_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
  598.             _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1)), _P), _P);
  599.         if (_L - _M <= _M - _F)
  600.             _Sort(_M, _L, _P, _Val_type(_F)), _L = _M;
  601.         else
  602.             _Sort(_F, _M, _P, _Val_type(_F)), _F = _M; }}
  603. template<class _RI, class _Ty, class _Pr> inline
  604.     _RI _Unguarded_partition(_RI _F, _RI _L, _Ty _Piv, _Pr _P)
  605.     {for (; ; ++_F)
  606.         {for (; _P(*_F, _Piv); ++_F)
  607.             ;
  608.         for (; _P(_Piv, *--_L); )
  609.             ;
  610.         if (_L <= _F)
  611.             return (_F);
  612.         iter_swap(_F, _L); }}
  613. template<class _RI, class _Pr> inline
  614.     void _Insertion_sort(_RI _F, _RI _L, _Pr _P)
  615.     {_Insertion_sort_1(_F, _L, _P, _Val_type(_F)); }
  616. template<class _RI, class _Ty, class _Pr> inline
  617.     void _Insertion_sort_1(_RI _F, _RI _L, _Pr _P, _Ty *)
  618.     {if (_F != _L)
  619.         for (_RI _M = _F; ++_M != _L; )
  620.             {_Ty _V = *_M;
  621.             if (!_P(_V, *_F))
  622.                 _Unguarded_insert(_M, _V, _P);
  623.             else
  624.                 {copy_backward(_F, _M, _M + 1);
  625.                 *_F = _V; }}}
  626. template<class _RI, class _Ty, class _Pr> inline
  627.     void _Unguarded_insert(_RI _L, _Ty _V, _Pr _P)
  628.     {for (_RI _M = _L; _P(_V, *--_M); _L = _M)
  629.         *_L = *_M;
  630.     *_L = _V; }
  631.         // TEMPLATE FUNCTION stable_sort
  632. template<class _BI> inline
  633.     void stable_sort(_BI _F, _BI _L)
  634.     {if (_F != _L)
  635.         _Stable_sort(_F, _L, _Dist_type(_F), _Val_type(_F)); }
  636. template<class _BI, class _Pd, class _Ty> inline
  637.     void _Stable_sort(_BI _F, _BI _L, _Pd *, _Ty *)
  638.     {_Pd _N = 0;
  639.     _Distance(_F, _L, _N);
  640.     _Temp_iterator<_Ty> _Xb(_N);
  641.     _Stable_sort(_F, _L, _N, _Xb); }
  642. template<class _BI, class _Pd, class _Ty> inline
  643.     void _Stable_sort(_BI _F, _BI _L, _Pd _N,
  644.         _Temp_iterator<_Ty>& _Xb)
  645.     {if (_N <= _SORT_MAX)
  646.         _Insertion_sort(_F, _L);
  647.     else
  648.         {_Pd _N2 = (_N + 1) / 2;
  649.         _BI _M = _F;
  650.         advance(_M, _N2);
  651.         if (_N2 <= _Xb._Maxlen())
  652.             {_Buffered_merge_sort(_F, _M, _N2, _Xb);
  653.             _Buffered_merge_sort(_M, _L, _N - _N2, _Xb); }
  654.         else
  655.             {_Stable_sort(_F, _M, _N2, _Xb);
  656.             _Stable_sort(_M, _L, _N - _N2, _Xb); }
  657.         _Buffered_merge(_F, _M, _L, _N2, _N - _N2, _Xb); }}
  658. template<class _BI, class _Pd, class _Ty> inline
  659.     void _Buffered_merge_sort(_BI _F, _BI _L, _Pd _N,
  660.         _Temp_iterator<_Ty>& _Xb)
  661.     {_BI _M = _F;
  662.     for (_Pd _I = _N; _CHUNK_SIZE <= _I; _I -= _CHUNK_SIZE)
  663.         {_BI _Mn = _M;
  664.         advance(_Mn, (int)_CHUNK_SIZE);
  665.         _Insertion_sort(_M, _Mn);
  666.         _M = _Mn; }
  667.     _Insertion_sort(_M, _L);
  668.     for (_Pd _D = _CHUNK_SIZE; _D < _N; _D *= 2)
  669.         {_BI _Ft = _F;
  670.         _Chunked_merge(_F, _L, _Xb._Init(), _D, _N);
  671.         _Chunked_merge(_Xb._First(), _Xb._Last(), _Ft,
  672.             _D *= 2, _N); }}
  673. template<class _BI, class _OI, class _Pd> inline
  674.     void _Chunked_merge(_BI _F, _BI _L, _OI& _X, _Pd _D, _Pd _N)
  675.     {_Pd _D2 = _D * 2;
  676.     for (; _D2 <= _N; _N -= _D2)
  677.         {_BI _F1 = _F;
  678.         advance(_F1, _D);
  679.         _BI _F2 = _F1;
  680.         advance(_F2, _D);
  681.         _X = merge(_F, _F1, _F1, _F2, _X);
  682.         _F = _F2; }
  683.     if (_N <= _D)
  684.         copy(_F, _L, _X);
  685.     else
  686.         {_BI _F1 = _F;
  687.         advance(_F1, _D);
  688.         merge(_F, _F1, _F1, _L, _X); }}
  689.         // TEMPLATE FUNCTION stable_sort WITH PRED
  690. template<class _BI, class _Pr> inline
  691.     void stable_sort(_BI _F, _BI _L, _Pr _P)
  692.     {if (_F != _L)
  693.         _Stable_sort(_F, _L,
  694.             _Dist_type(_F), _Val_type(_F), _P); }
  695. template<class _BI, class _Pd, class _Ty, class _Pr> inline
  696.     void _Stable_sort(_BI _F, _BI _L, _Pd *, _Ty *, _Pr _P)
  697.     {_Pd _N = 0;
  698.     _Distance(_F, _L, _N);
  699.     _Temp_iterator<_Ty> _Xb(_N);
  700.     _Stable_sort(_F, _L, _N, _Xb, _P); }
  701. template<class _BI, class _Pd, class _Ty, class _Pr> inline
  702.     void _Stable_sort(_BI _F, _BI _L, _Pd _N,
  703.         _Temp_iterator<_Ty>& _Xb, _Pr _P)
  704.     {if (_N <= _SORT_MAX)
  705.         _Insertion_sort(_F, _L, _P);
  706.     else
  707.         {_Pd _N2 = (_N + 1) / 2;
  708.         _BI _M = _F;
  709.         advance(_M, _N2);
  710.         if (_N2 <= _Xb._Maxlen())
  711.             {_Buffered_merge_sort(_F, _M, _N2, _Xb, _P);
  712.             _Buffered_merge_sort(_M, _L, _N - _N2, _Xb, _P); }
  713.         else
  714.             {_Stable_sort(_F, _M, _N2, _Xb, _P);
  715.             _Stable_sort(_M, _L, _N - _N2, _Xb, _P); }
  716.         _Buffered_merge(_F, _M, _L, _N2, _N - _N2, _Xb, _P); }}
  717. template<class _BI, class _Pd, class _Ty, class _Pr> inline
  718.     void _Buffered_merge_sort(_BI _F, _BI _L, _Pd _N,
  719.         _Temp_iterator<_Ty>& _Xb, _Pr _P)
  720.     {_BI _M = _F;
  721.     for (_Pd _I = _N; _CHUNK_SIZE <= _I; _I -= _CHUNK_SIZE)
  722.         {_BI _Mn = _M;
  723.         advance(_Mn, (int)_CHUNK_SIZE);
  724.         _Insertion_sort(_M, _Mn, _P);
  725.         _M = _Mn; }
  726.     _Insertion_sort(_M, _L, _P);
  727.     for (_Pd _D = _CHUNK_SIZE; _D < _N; _D *= 2)
  728.         {_BI _Ft = _F;
  729.         _Chunked_merge(_F, _L, _Xb._Init(), _D, _N, _P);
  730.         _Chunked_merge(_Xb._First(), _Xb._Last(), _Ft,
  731.             _D *= 2, _N, _P); }}
  732. template<class _BI, class _OI, class _Pd, class _Pr> inline
  733.     void _Chunked_merge(_BI _F, _BI _L, _OI& _X,
  734.         _Pd _D, _Pd _N, _Pr _P)
  735.     {_Pd _D2 = _D * 2;
  736.     for (; _D2 <= _N; _N -= _D2)
  737.         {_BI _F1 = _F;
  738.         advance(_F1, _D);
  739.         _BI _F2 = _F1;
  740.         advance(_F2, _D);
  741.         _X = merge(_F, _F1, _F1, _F2, _X, _P);
  742.         _F = _F2; }
  743.     if (_N <= _D)
  744.         copy(_F, _L, _X);
  745.     else
  746.         {_BI _F1 = _F;
  747.         advance(_F1, _D);
  748.         merge(_F, _F1, _F1, _L, _X, _P); }}
  749.         // TEMPLATE FUNCTION partial_sort
  750. template<class _RI> inline
  751.     void partial_sort(_RI _F, _RI _M, _RI _L)
  752.     {_Partial_sort(_F, _M, _L, _Val_type(_F)); }
  753. template<class _RI, class _Ty> inline
  754.     void _Partial_sort(_RI _F, _RI _M, _RI _L, _Ty *)
  755.     {make_heap(_F, _M);
  756.     for (_RI _I = _M; _I < _L; ++_I)
  757.         if (*_I < *_F)
  758.             _Pop_heap(_F, _M, _I, _Ty(*_I), _Dist_type(_F));
  759.     sort_heap(_F, _M); }
  760.         // TEMPLATE FUNCTION partial_sort WITH PRED
  761. template<class _RI, class _Pr> inline
  762.     void partial_sort(_RI _F, _RI _M, _RI _L, _Pr _P)
  763.     {_Partial_sort(_F, _M, _L, _P, _Val_type(_F)); }
  764. template<class _RI, class _Ty, class _Pr> inline
  765.     void _Partial_sort(_RI _F, _RI _M, _RI _L, _Pr _P, _Ty *)
  766.     {make_heap(_F, _M, _P);
  767.     for (_RI _I = _M; _I < _L; ++_I)
  768.         if (_P(*_I, *_F))
  769.             _Pop_heap(_F, _M, _I, _Ty(*_I), _P, _Dist_type(_F));
  770.     sort_heap(_F, _M, _P); }
  771.         // TEMPLATE FUNCTION partial_sort_copy
  772. template<class _II, class _RI> inline
  773.     _RI partial_sort_copy(_II _F1, _II _L1, _RI _F2, _RI _L2)
  774.     {return (_Partial_sort_copy(_F1, _L1, _F2, _L2,
  775.         _Dist_type(_F2), _Val_type(_F1))); }
  776. template<class _II, class _RI, class _Pd, class _Ty> inline
  777.     _RI _Partial_sort_copy(_II _F1, _II _L1, _RI _F2, _RI _L2,
  778.         _Pd *, _Ty *)
  779.     {_RI _X = _F2;
  780.     if (_X != _L2)
  781.         {for (; _F1 != _L1 && _X != _L2; ++_F1, ++_X)
  782.             *_X = *_F1;
  783.         make_heap(_F2, _X);
  784.         for (; _F1 != _L1; ++_F1)
  785.             if (*_F1 < *_F2)
  786.                 _Adjust_heap(_F2, _Pd(0), _Pd(_X - _F2),
  787.                     _Ty(*_F1));
  788.         sort_heap(_F2, _X); }
  789.     return (_X); }
  790.         // TEMPLATE FUNCTION partial_sort_copy WITH PRED
  791. template<class _II, class _RI, class _Pr> inline
  792.     _RI partial_sort_copy(_II _F1, _II _L1, _RI _F2, _RI _L2,
  793.         _Pr _P)
  794.     {return (_Partial_sort_copy(_F1, _L1, _F2, _L2, _P,
  795.         _Dist_type(_F2), _Val_type(_F1))); }
  796. template<class _II, class _RI, class _Pd,
  797.     class _Ty, class _Pr> inline
  798.     _RI _Partial_sort_copy(_II _F1, _II _L1, _RI _F2, _RI _L2,
  799.         _Pr _P, _Pd *, _Ty *)
  800.     {_RI _X = _F2;
  801.     if (_X != _L2)
  802.         {for (; _F1 != _L1 && _X != _L2; ++_F1, ++_X)
  803.             *_X = *_F1;
  804.         make_heap(_F2, _X, _P);
  805.         for (; _F1 != _L1; ++_F1)
  806.             if (_P(*_F1, *_F2))
  807.                 _Adjust_heap(_F2, _Pd(0), _Pd(_X - _F2),
  808.                     _Ty(*_F1), _P);
  809.         sort_heap(_F2, _X, _P); }
  810.     return (_X); }
  811.         // TEMPLATE FUNCTION nth_element
  812. template<class _RI> inline
  813.     void nth_element(_RI _F, _RI _Nth, _RI _L)
  814.     {_Nth_element(_F, _Nth, _L, _Val_type(_F)); }
  815. template<class _RI, class _Ty> inline
  816.     void _Nth_element(_RI _F, _RI _Nth, _RI _L, _Ty *)
  817.     {for (; _SORT_MAX < _L - _F; )
  818.         {_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
  819.             _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1))));
  820.         if (_M <= _Nth)
  821.             _F = _M;
  822.         else
  823.             _L = _M; }
  824.     _Insertion_sort(_F, _L); }
  825.         // TEMPLATE FUNCTION nth_element WITH PRED
  826. template<class _RI, class _Pr> inline
  827.     void nth_element(_RI _F, _RI _Nth, _RI _L, _Pr _P)
  828.     {_Nth_element(_F, _Nth, _L, _P, _Val_type(_F)); }
  829. template<class _RI, class _Ty, class _Pr> inline
  830.     void _Nth_element(_RI _F, _RI _Nth, _RI _L, _Pr _P, _Ty *)
  831.     {for (; _SORT_MAX < _L - _F; )
  832.         {_RI _M = _Unguarded_partition(_F, _L, _Median(_Ty(*_F),
  833.             _Ty(*(_F + (_L - _F) / 2)), _Ty(*(_L - 1)), _P), _P);
  834.         if (_M <= _Nth)
  835.             _F = _M;
  836.         else
  837.             _L = _M; }
  838.     _Insertion_sort(_F, _L, _P); }
  839.         // TEMPLATE FUNCTION lower_bound
  840. template<class _FI, class _Ty> inline
  841.     _FI lower_bound(_FI _F, _FI _L, const _Ty& _V)
  842.     {return (_Lower_bound(_F, _L, _V, _Dist_type(_F))); }
  843. template<class _FI, class _Ty, class _Pd> inline
  844.     _FI _Lower_bound(_FI _F, _FI _L, const _Ty& _V, _Pd *)
  845.     {_Pd _N = 0;
  846.     _Distance(_F, _L, _N);
  847.     for (; 0 < _N; )
  848.         {_Pd _N2 = _N / 2;
  849.         _FI _M = _F;
  850.         advance(_M, _N2);
  851.         if (*_M < _V)
  852.             _F = ++_M, _N -= _N2 + 1;
  853.         else
  854.             _N = _N2; }
  855.     return (_F); } 
  856.         // TEMPLATE FUNCTION lower_bound WITH PRED
  857. template<class _FI, class _Ty, class _Pr> inline
  858.     _FI lower_bound(_FI _F, _FI _L, const _Ty& _V, _Pr _P)
  859.     {return (_Lower_bound(_F, _L, _V, _P, _Dist_type(_F))); }
  860. template<class _FI, class _Ty, class _Pd, class _Pr> inline
  861.     _FI _Lower_bound(_FI _F, _FI _L, const _Ty& _V, _Pr _P, _Pd *)
  862.     {_Pd _N = 0;
  863.     _Distance(_F, _L, _N);
  864.     for (; 0 < _N; )
  865.         {_Pd _N2 = _N / 2;
  866.         _FI _M = _F;
  867.         advance(_M, _N2);
  868.         if (_P(*_M, _V))
  869.             _F = ++_M, _N -= _N2 + 1;
  870.         else
  871.             _N = _N2; }
  872.     return (_F); } 
  873.         // TEMPLATE FUNCTION upper_bound
  874. template<class _FI, class _Ty> inline
  875.     _FI upper_bound(_FI _F, _FI _L, const _Ty& _V)
  876.     {return (_Upper_bound(_F, _L, _V, _Dist_type(_F))); }
  877. template<class _FI, class _Ty, class _Pd> inline
  878.     _FI _Upper_bound(_FI _F, _FI _L, const _Ty& _V, _Pd *)
  879.     {_Pd _N = 0;
  880.     _Distance(_F, _L, _N);
  881.     for (; 0 < _N; )
  882.         {_Pd _N2 = _N / 2;
  883.         _FI _M = _F;
  884.         advance(_M, _N2);
  885.         if (!(_V < *_M))
  886.             _F = ++_M, _N -= _N2 + 1;
  887.         else
  888.             _N = _N2; }
  889.     return (_F); } 
  890.         // TEMPLATE FUNCTION upper_bound WITH PRED
  891. template<class _FI, class _Ty, class _Pr> inline
  892.     _FI upper_bound(_FI _F, _FI _L, const _Ty& _V, _Pr _P)
  893.     {return (_Upper_bound(_F, _L, _V, _P, _Dist_type(_F))); }
  894. template<class _FI, class _Ty, class _Pd, class _Pr> inline
  895.     _FI _Upper_bound(_FI _F, _FI _L, const _Ty& _V, _Pr _P, _Pd *)
  896.     {_Pd _N = 0;
  897.     _Distance(_F, _L, _N);
  898.     for (; 0 < _N; )
  899.         {_Pd _N2 = _N / 2;
  900.         _FI _M = _F;
  901.         advance(_M, _N2);
  902.         if (!_P(_V, *_M))
  903.             _F = ++_M, _N -= _N2 + 1;
  904.         else
  905.             _N = _N2; }
  906.     return (_F); } 
  907.         // TEMPLATE FUNCTION equal_range
  908. template<class _FI, class _Ty> inline
  909.     pair<_FI, _FI> equal_range(_FI _F, _FI _L, const _Ty& _V)
  910.     {return (_Equal_range(_F, _L, _V, _Dist_type(_F))); }
  911. template<class _FI, class _Ty, class _Pd> inline
  912.     pair<_FI, _FI> _Equal_range(_FI _F, _FI _L,
  913.         const _Ty& _V, _Pd *)
  914.     {_Pd _N = 0;
  915.     _Distance(_F, _L, _N);
  916.     for (; 0 < _N; )
  917.         {_Pd _N2 = _N / 2;
  918.         _FI _M = _F;
  919.         advance(_M, _N2);
  920.         if (*_M < _V)
  921.             _F = ++_M, _N -= _N2 + 1;
  922.         else if (_V < *_M)
  923.             _N = _N2;
  924.         else
  925.             {_FI _F2 = lower_bound(_F, _M, _V);
  926.             advance(_F, _N);
  927.             _FI _L2 = upper_bound(++_M, _F, _V);
  928.             return (pair<_FI, _FI>(_F2, _L2)); }} 
  929.     return (pair<_FI, _FI>(_F, _F)); } 
  930.         // TEMPLATE FUNCTION equal_range WITH PRED
  931. template<class _FI, class _Ty, class _Pr> inline
  932.     pair<_FI, _FI> equal_range(_FI _F, _FI _L, const _Ty& _V,
  933.         _Pr _P)
  934.     {return (_Equal_range(_F, _L, _V, _P, _Dist_type(_F))); }
  935. template<class _FI, class _Ty, class _Pd, class _Pr> inline
  936.     pair<_FI, _FI> _Equal_range(_FI _F, _FI _L, const _Ty& _V,
  937.         _Pr _P, _Pd *)
  938.     {_Pd _N = 0;
  939.     _Distance(_F, _L, _N);
  940.     for (; 0 < _N; )
  941.         {_Pd _N2 = _N / 2;
  942.         _FI _M = _F;
  943.         advance(_M, _N2);
  944.         if (_P(*_M, _V))
  945.             _F = ++_M, _N -= _N2 + 1;
  946.         else if (_P(_V, *_M))
  947.             _N = _N2;
  948.         else
  949.             {_FI _F2 = lower_bound(_F, _M, _V, _P);
  950.             advance(_F, _N);
  951.             _FI _L2 = upper_bound(++_M, _F, _V, _P);
  952.             return (pair<_FI, _FI>(_F2, _L2)); }}
  953.     return (pair<_FI, _FI>(_F, _F)); } 
  954.         // TEMPLATE FUNCTION binary_search
  955. template<class _FI, class _Ty> inline
  956.     bool binary_search(_FI _F, _FI _L, const _Ty& _V)
  957.     {_FI _I = lower_bound(_F, _L, _V);
  958.     return (_I != _L && !(_V < *_I)); }
  959.         // TEMPLATE FUNCTION binary_search WITH PRED
  960. template<class _FI, class _Ty, class _Pr> inline
  961.     bool binary_search(_FI _F, _FI _L, const _Ty& _V, _Pr _P)
  962.     {_FI _I = lower_bound(_F, _L, _V, _P);
  963.     return (_I != _L && !_P(_V, *_I)); }
  964.         // TEMPLATE FUNCTION merge
  965. template<class _II1, class _II2, class _OI> inline
  966.     _OI merge(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X)
  967.     {for (; _F1 != _L1 && _F2 != _L2; ++_X)
  968.         if (*_F2 < *_F1)
  969.             *_X = *_F2++;
  970.         else
  971.             *_X = *_F1++;
  972.     return (copy(_F2, _L2, copy(_F1, _L1, _X))); } 
  973.         // TEMPLATE FUNCTION merge WITH PRED
  974. template<class _II1, class _II2, class _OI, class _Pr> inline
  975.     _OI merge(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X,
  976.         _Pr _P)
  977.     {for (; _F1 != _L1 && _F2 != _L2; ++_X)
  978.         if (_P(*_F2, *_F1))
  979.             *_X = *_F2++;
  980.         else
  981.             *_X = *_F1++;
  982.     return (copy(_F2, _L2, copy(_F1, _L1, _X))); } 
  983.         // TEMPLATE FUNCTION inplace_merge
  984. template<class _BI> inline
  985.     void inplace_merge(_BI _F, _BI _M, _BI _L)
  986.     {if (_F != _L)
  987.         _Inplace_merge(_F, _M, _L,
  988.             _Dist_type(_F), _Val_type(_F)); }
  989. template<class _BI, class _Pd, class _Ty> inline
  990.     void _Inplace_merge(_BI _F, _BI _M, _BI _L, _Pd *, _Ty *)
  991.     {_Pd _D1 = 0;
  992.     _Distance(_F, _M, _D1);
  993.     _Pd _D2 = 0;
  994.     _Distance(_M, _L, _D2);
  995.     _Temp_iterator<_Ty> _Xb(_D1 < _D2 ? _D1 : _D2);
  996.     _Buffered_merge(_F, _M, _L, _D1, _D2, _Xb); }
  997. template<class _BI, class _Pd, class _Ty> inline
  998.     void _Buffered_merge(_BI _F, _BI _M, _BI _L,
  999.         _Pd _D1, _Pd _D2, _Temp_iterator<_Ty>& _Xb)
  1000.     {if (_D1 == 0 || _D2 == 0)
  1001.         ;
  1002.     else if (_D1 + _D2 == 2)
  1003.         {if (*_M < *_F)
  1004.             iter_swap(_F, _M); }
  1005.     else if (_D1 <= _D2 && _D1 <= _Xb._Maxlen())
  1006.         {copy(_F, _M, _Xb._Init());
  1007.         merge(_Xb._First(), _Xb._Last(), _M, _L, _F); }
  1008.     else if (_D2 <= _Xb._Maxlen())
  1009.         {copy(_M, _L, _Xb._Init());
  1010.         _Merge_backward(_F, _M, _Xb._First(), _Xb._Last(), _L); }
  1011.     else
  1012.         {_BI _Fn, _Ln;
  1013.         _Pd _D1n, _D2n;
  1014.         if (_D2 < _D1)
  1015.             {_D1n = _D1 / 2;
  1016.             _Fn = _F;
  1017.             advance(_Fn, _D1n);
  1018.             _Ln = lower_bound(_M, _L, _Ty(*_Fn));
  1019.             _Distance(_M, _Ln, _D2n); }
  1020.         else
  1021.             {_D2n = _D2 / 2;
  1022.             _Ln = _M;
  1023.             advance(_Ln, _D2n);
  1024.             _Fn = upper_bound(_F, _M, _Ty(*_Ln));
  1025.             _Distance(_F, _Fn, _D1n); }
  1026.         _BI _Mn = _Buffered_rotate(_Fn, _M, _Ln,
  1027.             _D1 - _D1n, _D2n, _Xb);
  1028.         _Buffered_merge(_F, _Fn, _Mn, _D1n, _D2n, _Xb);
  1029.         _Buffered_merge(_Mn, _Ln, _L,
  1030.             _D1 - _D1n, _D2 - _D2n, _Xb); }}
  1031. template<class _BI1, class _BI2, class _BI3> inline
  1032.     _BI3 _Merge_backward(_BI1 _F1, _BI1 _L1, _BI2 _F2, _BI2 _L2,
  1033.         _BI3 _X)
  1034.     {for (; ; )
  1035.         if (_F1 == _L1)
  1036.             return (copy_backward(_F2, _L2, _X));
  1037.         else if (_F2 == _L2)
  1038.             return (copy_backward(_F1, _L1, _X));
  1039.         else if (*--_L2 < *--_L1)
  1040.             *--_X = *_L1, ++_L2;
  1041.         else
  1042.             *--_X = *_L2, ++_L1; }
  1043. template<class _BI, class _Pd, class _Ty> inline
  1044.     _BI _Buffered_rotate(_BI _F, _BI _M, _BI _L,
  1045.         _Pd _D1, _Pd _D2, _Temp_iterator<_Ty>& _Xb)
  1046.     {if (_D1 <= _D2 && _D1 <= _Xb._Maxlen())
  1047.         {copy(_F, _M, _Xb._Init());
  1048.         copy(_M, _L, _F);
  1049.         return (copy_backward(_Xb._First(), _Xb._Last(), _L)); }
  1050.     else if (_D2 <= _Xb._Maxlen())
  1051.         {copy(_M, _L, _Xb._Init());
  1052.         copy_backward(_F, _M, _L);
  1053.         return (copy(_Xb._First(), _Xb._Last(), _F)); }
  1054.     else
  1055.         {rotate(_F, _M, _L);
  1056.         advance(_F, _D2);
  1057.         return (_F); }}
  1058.         // TEMPLATE FUNCTION inplace_merge WITH PRED
  1059. template<class _BI, class _Pr> inline
  1060.     void inplace_merge(_BI _F, _BI _M, _BI _L, _Pr _P)
  1061.     {if (_F != _L)
  1062.         _Inplace_merge(_F, _M, _L, _P,
  1063.             _Dist_type(_F), _Val_type(_F)); }
  1064. template<class _BI, class _Pd, class _Ty, class _Pr> inline
  1065.     void _Inplace_merge(_BI _F, _BI _M, _BI _L, _Pr _P,
  1066.         _Pd *, _Ty *)
  1067.     {_Pd _D1 = 0;
  1068.     _Distance(_F, _M, _D1);
  1069.     _Pd _D2 = 0;
  1070.     _Distance(_M, _L, _D2);
  1071.     _Temp_iterator<_Ty> _Xb(_D1 < _D2 ? _D1 : _D2);
  1072.     _Buffered_merge(_F, _M, _L, _D1, _D2, _Xb, _P); }
  1073. template<class _BI, class _Pd, class _Ty, class _Pr> inline
  1074.     void _Buffered_merge(_BI _F, _BI _M, _BI _L,
  1075.         _Pd _D1, _Pd _D2, _Temp_iterator<_Ty>& _Xb, _Pr _P)
  1076.     {if (_D1 == 0 || _D2 == 0)
  1077.         ;
  1078.     else if (_D1 + _D2 == 2)
  1079.         {if (_P(*_M, *_F))
  1080.             iter_swap(_F, _M); }
  1081.     else if (_D1 <= _D2 && _D1 <= _Xb._Maxlen())
  1082.         {copy(_F, _M, _Xb._Init());
  1083.         merge(_Xb._First(), _Xb._Last(), _M, _L, _F, _P); }
  1084.     else if (_D2 <= _Xb._Maxlen())
  1085.         {copy(_M, _L, _Xb._Init());
  1086.         _Merge_backward(_F, _M, _Xb._First(), _Xb._Last(),
  1087.             _L, _P); }
  1088.     else
  1089.         {_BI _Fn, _Ln;
  1090.         _Pd _D1n, _D2n;
  1091.         if (_D2 < _D1)
  1092.             {_D1n = _D1 / 2;
  1093.             _Fn = _F;
  1094.             advance(_Fn, _D1n);
  1095.             _Ln = lower_bound(_M, _L, _Ty(*_Fn), _P);
  1096.             _Distance(_M, _Ln, _D2n); }
  1097.         else
  1098.             {_D2n = _D2 / 2;
  1099.             _Ln = _M;
  1100.             advance(_Ln, _D2n);
  1101.             _Fn = upper_bound(_F, _M, _Ty(*_Ln), _P);
  1102.             _Distance(_F, _Fn, _D1n); }
  1103.         _BI _Mn = _Buffered_rotate(_Fn, _M, _Ln,
  1104.             _D1 - _D1n, _D2n, _Xb);
  1105.         _Buffered_merge(_F, _Fn, _Mn, _D1n, _D2n, _Xb, _P);
  1106.         _Buffered_merge(_Mn, _Ln, _L,
  1107.             _D1 - _D1n, _D2 - _D2n, _Xb, _P); }}
  1108. template<class _BI1, class _BI2, class _BI3, class _Pr> inline
  1109.     _BI3 _Merge_backward(_BI1 _F1, _BI1 _L1, _BI2 _F2, _BI2 _L2,
  1110.         _BI3 _X, _Pr _P)
  1111.     {for (; ; )
  1112.         if (_F1 == _L1)
  1113.             return (copy_backward(_F2, _L2, _X));
  1114.         else if (_F2 == _L2)
  1115.             return (copy_backward(_F1, _L1, _X));
  1116.         else if (_P(*--_L2, *--_L1))
  1117.             *--_X = *_L1, ++_L2;
  1118.         else
  1119.             *--_X = *_L2, ++_L1; }
  1120.         // TEMPLATE FUNCTION includes
  1121. template<class _II1, class _II2> inline
  1122.     bool includes(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2)
  1123.     {for (; _F1 != _L1 && _F2 != _L2; )
  1124.         if (*_F2 < *_F1)
  1125.             return (false);
  1126.         else if (*_F1 < *_F2)
  1127.             ++_F1;
  1128.         else
  1129.             ++_F2;
  1130.     return (_F2 == _L2); }
  1131.         // TEMPLATE FUNCTION includes WITH PRED
  1132. template<class _II1, class _II2, class _Pr> inline
  1133.     bool includes(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _Pr _P)
  1134.     {for (; _F1 != _L1 && _F2 != _L2; )
  1135.         if (_P(*_F2, *_F1))
  1136.             return (false);
  1137.         else if (_P(*_F1, *_F2))
  1138.             ++_F1;
  1139.         else
  1140.             ++_F2;
  1141.     return (_F2 == _L2); }
  1142.         // TEMPLATE FUNCTION set_union
  1143. template<class _II1, class _II2, class _OI> inline
  1144.     _OI set_union(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X)
  1145.     {for (; _F1 != _L1 && _F2 != _L2; )
  1146.         if (*_F1 < *_F2)
  1147.             *_X++ = *_F1++;
  1148.         else if (*_F2 < *_F1)
  1149.             *_X++ = *_F2++;
  1150.         else
  1151.             *_X++ = *_F1++, ++_F2;
  1152.     return (copy(_F2, _L2, copy(_F1, _L1, _X))); }
  1153.         // TEMPLATE FUNCTION set_union WITH PRED
  1154. template<class _II1, class _II2, class _OI, class _Pr> inline
  1155.     _OI set_union(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2, _OI _X,
  1156.         _Pr _P)
  1157.     {for (; _F1 != _L1 && _F2 != _L2; )
  1158.         if (_P(*_F1, *_F2))
  1159.             *_X++ = *_F1++;
  1160.         else if (_P(*_F2, *_F1))
  1161.             *_X++ = *_F2++;
  1162.         else
  1163.             *_X++ = *_F1++, ++_F2;
  1164.     return (copy(_F2, _L2, copy(_F1, _L1, _X))); }
  1165.         // TEMPLATE FUNCTION set_intersection
  1166. template<class _II1, class _II2, class _OI> inline
  1167.     _OI set_intersection(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2,
  1168.         _OI _X)
  1169.     {for (; _F1 != _L1 && _F2 != _L2; )
  1170.         if (*_F1 < *_F2)
  1171.             ++_F1;
  1172.         else if (*_F2 < *_F1)
  1173.             ++_F2;
  1174.         else
  1175.             *_X++ = *_F1++, ++_F2;
  1176.     return (_X); }
  1177.         // TEMPLATE FUNCTION set_intersection WITH PRED
  1178. template<class _II1, class _II2, class _OI, class _Pr> inline
  1179.     _OI set_intersection(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2,
  1180.         _OI _X, _Pr _P)
  1181.     {for (; _F1 != _L1 && _F2 != _L2; )
  1182.         if (_P(*_F1, *_F2))
  1183.             ++_F1;
  1184.         else if (_P(*_F2, *_F1))
  1185.             ++_F2;
  1186.         else
  1187.             *_X++ = *_F1++, ++_F2;
  1188.     return (_X); }
  1189.         // TEMPLATE FUNCTION set_difference
  1190. template<class _II1, class _II2, class _OI> inline
  1191.     _OI set_difference(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2,
  1192.         _OI _X)
  1193.     {for (; _F1 != _L1 && _F2 != _L2; )
  1194.         if (*_F1 < *_F2)
  1195.             *_X++ = *_F1++;
  1196.         else if (*_F2 < *_F1)
  1197.             ++_F2;
  1198.         else
  1199.             ++_F1, ++_F2;
  1200.     return (copy(_F1, _L1, _X)); }
  1201.         // TEMPLATE FUNCTION set_difference WITH PRED
  1202. template<class _II1, class _II2, class _OI, class _Pr> inline
  1203.     _OI set_difference(_II1 _F1, _II1 _L1, _II2 _F2, _II2 _L2,
  1204.         _OI _X, _Pr _P)
  1205.     {for (; _F1 != _L1 && _F2 != _L2; )
  1206.         if (_P(*_F1, *_F2))
  1207.             *_X++ = *_F1++;
  1208.         else if (_P(*_F2, *_F1))
  1209.             ++_F2;
  1210.         else
  1211.             ++_F1, ++_F2;
  1212.     return (copy(_F1, _L1, _X)); }
  1213.         // TEMPLATE FUNCTION set_symmetric_difference
  1214. template<class _II1, class _II2, class _OI> inline
  1215.     _OI set_symmetric_difference(_II1 _F1, _II1 _L1, _II2 _F2,
  1216.         _II2 _L2, _OI _X)
  1217.     {for (; _F1 != _L1 && _F2 != _L2; )
  1218.         if (*_F1 < *_F2)
  1219.             *_X++ = *_F1++;
  1220.         else if (*_F2 < *_F1)
  1221.             *_X++ = *_F2++;
  1222.         else
  1223.             ++_F1, ++_F2;
  1224.     return (copy(_F2, _L2, copy(_F1, _L1, _X))); }
  1225.         // TEMPLATE FUNCTION set_symmetric_difference WITH PRED
  1226. template<class _II1, class _II2, class _OI, class _Pr> inline
  1227.     _OI set_symmetric_difference(_II1 _F1, _II1 _L1, _II2 _F2,
  1228.         _II2 _L2, _OI _X, _Pr _P)
  1229.     {for (; _F1 != _L1 && _F2 != _L2; )
  1230.         if (_P(*_F1, *_F2))
  1231.             *_X++ = *_F1++;
  1232.         else if (_P(*_F2, *_F1))
  1233.             *_X++ = *_F2++;
  1234.         else
  1235.             ++_F1, ++_F2;
  1236.     return (copy(_F2, _L2, copy(_F1, _L1, _X))); }
  1237.         // TEMPLATE FUNCTION push_heap
  1238. template<class _RI> inline
  1239.     void push_heap(_RI _F, _RI _L)
  1240.     {_Push_heap_0(_F, _L, _Dist_type(_F), _Val_type(_F)); }
  1241. template<class _RI, class _Pd, class _Ty> inline
  1242.     void _Push_heap_0(_RI _F, _RI _L, _Pd *, _Ty *)
  1243.     {_Push_heap(_F, _Pd(_L - _F - 1), _Pd(0), _Ty(*(_L - 1))); }
  1244. template<class _RI, class _Pd, class _Ty> inline
  1245.     void _Push_heap(_RI _F, _Pd _H, _Pd _J, _Ty _V)
  1246.     {for (_Pd _I = (_H - 1) / 2; _J < _H && *(_F + _I) < _V;
  1247.         _I = (_H - 1) / 2)
  1248.         *(_F + _H) = *(_F + _I), _H = _I;
  1249.     *(_F + _H) = _V; }
  1250.         // TEMPLATE FUNCTION push_heap WITH PRED
  1251. template<class _RI, class _Pr> inline
  1252.     void push_heap(_RI _F, _RI _L, _Pr _P)
  1253.     {_Push_heap_0(_F, _L, _P,
  1254.         _Dist_type(_F), _Val_type(_F)); }
  1255. template<class _RI, class _Pd, class _Ty, class _Pr> inline
  1256.     void _Push_heap_0(_RI _F, _RI _L, _Pr _P, _Pd *, _Ty *)
  1257.     {_Push_heap(_F, _Pd(_L - _F - 1), _Pd(0),
  1258.         _Ty(*(_L - 1)), _P); }
  1259. template<class _RI, class _Pd, class _Ty, class _Pr> inline
  1260.     void _Push_heap(_RI _F, _Pd _H, _Pd _J, _Ty _V, _Pr _P)
  1261.     {for (_Pd _I = (_H - 1) / 2; _J < _H && _P(*(_F + _I), _V);
  1262.         _I = (_H - 1) / 2)
  1263.         *(_F + _H) = *(_F + _I), _H = _I;
  1264.     *(_F + _H) = _V; }
  1265.         // TEMPLATE FUNCTION pop_heap
  1266. template<class _RI> inline
  1267.     void pop_heap(_RI _F, _RI _L)
  1268.     {_Pop_heap_0(_F, _L, _Val_type(_F)); }
  1269. template<class _RI, class _Ty> inline
  1270.     void _Pop_heap_0(_RI _F, _RI _L, _Ty *)
  1271.     {_Pop_heap(_F, _L - 1, _L - 1, _Ty(*(_L - 1)),
  1272.         _Dist_type(_F)); }
  1273. template<class _RI, class _Pd, class _Ty> inline
  1274.     void _Pop_heap(_RI _F, _RI _L, _RI _X, _Ty _V, _Pd *)
  1275.     {*_X = *_F;
  1276.     _Adjust_heap(_F, _Pd(0), _Pd(_L - _F), _V); }
  1277. template<class _RI, class _Pd, class _Ty> inline
  1278.     void _Adjust_heap(_RI _F, _Pd _H, _Pd _N, _Ty _V)
  1279.     {_Pd _J = _H;
  1280.     _Pd _K = 2 * _H + 2;
  1281.     for (; _K < _N; _K = 2 * _K + 2)
  1282.         {if (*(_F + _K) < *(_F + (_K - 1)))
  1283.             --_K;
  1284.         *(_F + _H) = *(_F + _K), _H = _K; }
  1285.     if (_K == _N)
  1286.         *(_F + _H) = *(_F + (_K - 1)), _H = _K - 1;
  1287.     _Push_heap(_F, _H, _J, _V); }
  1288.         // TEMPLATE FUNCTION pop_heap WITH PRED
  1289. template<class _RI, class _Pr> inline
  1290.     void pop_heap(_RI _F, _RI _L, _Pr _P)
  1291.     {_Pop_heap_0(_F, _L, _P, _Val_type(_F)); }
  1292. template<class _RI, class _Ty, class _Pr> inline
  1293.     void _Pop_heap_0(_RI _F, _RI _L, _Pr _P, _Ty *)
  1294.     {_Pop_heap(_F, _L - 1, _L - 1, _Ty(*(_L - 1)), _P,
  1295.         _Dist_type(_F)); }
  1296. template<class _RI, class _Pd, class _Ty, class _Pr> inline
  1297.     void _Pop_heap(_RI _F, _RI _L, _RI _X, _Ty _V, _Pr _P, _Pd *)
  1298.     {*_X = *_F;
  1299.     _Adjust_heap(_F, _Pd(0), _Pd(_L - _F), _V, _P); }
  1300. template<class _RI, class _Pd, class _Ty, class _Pr> inline
  1301.     void _Adjust_heap(_RI _F, _Pd _H, _Pd _N, _Ty _V, _Pr _P)
  1302.     {_Pd _J = _H;
  1303.     _Pd _K = 2 * _H + 2;
  1304.     for (; _K < _N; _K = 2 * _K + 2)
  1305.         {if (_P(*(_F + _K), *(_F + (_K - 1))))
  1306.             --_K;
  1307.         *(_F + _H) = *(_F + _K), _H = _K; }
  1308.     if (_K == _N)
  1309.         *(_F + _H) = *(_F + (_K - 1)), _H = _K - 1;
  1310.     _Push_heap(_F, _H, _J, _V, _P); }
  1311.         // TEMPLATE FUNCTION make_heap
  1312. template<class _RI> inline
  1313.     void make_heap(_RI _F, _RI _L)
  1314.     {if (2 <= _L - _F)
  1315.         _Make_heap(_F, _L, _Dist_type(_F), _Val_type(_F)); }
  1316. template<class _RI, class _Pd, class _Ty> inline
  1317.     void _Make_heap(_RI _F, _RI _L, _Pd *, _Ty *)
  1318.     {_Pd _N = _L - _F;
  1319.     for (_Pd _H = _N / 2; 0 < _H; )
  1320.         --_H, _Adjust_heap(_F, _H, _N, _Ty(*(_F + _H))); }
  1321.         // TEMPLATE FUNCTION make_heap WITH PRED
  1322. template<class _RI, class _Pr> inline
  1323.     void make_heap(_RI _F, _RI _L, _Pr _P)
  1324.     {if (2 <= _L - _F)
  1325.         _Make_heap(_F, _L, _P,
  1326.             _Dist_type(_F), _Val_type(_F)); }
  1327. template<class _RI, class _Pd, class _Ty, class _Pr> inline
  1328.     void _Make_heap(_RI _F, _RI _L, _Pr _P, _Pd *, _Ty *)
  1329.     {_Pd _N = _L - _F;
  1330.     for (_Pd _H = _N / 2; 0 < _H; )
  1331.         --_H, _Adjust_heap(_F, _H, _N, _Ty(*(_F + _H)), _P); }
  1332.         // TEMPLATE FUNCTION sort_heap
  1333. template<class _RI> inline
  1334.     void sort_heap(_RI _F, _RI _L)
  1335.     {for (; 1 < _L - _F; --_L)
  1336.         pop_heap(_F, _L); }
  1337.         // TEMPLATE FUNCTION sort_heap WITH PRED
  1338. template<class _RI, class _Pr> inline
  1339.     void sort_heap(_RI _F, _RI _L, _Pr _P)
  1340.     {for (; 1 < _L - _F; --_L)
  1341.         pop_heap(_F, _L, _P); }
  1342.         // TEMPLATE FUNCTION max_element
  1343. template<class _FI> inline
  1344.     _FI max_element(_FI _F, _FI _L)
  1345.     {_FI _X = _F;
  1346.     if (_F != _L)
  1347.         for (; ++_F != _L; )
  1348.             if (*_X < *_F)
  1349.                 _X = _F;
  1350.     return (_X); }
  1351.         // TEMPLATE FUNCTION max_element WITH PRED
  1352. template<class _FI, class _Pr> inline
  1353.     _FI max_element(_FI _F, _FI _L, _Pr _P)
  1354.     {_FI _X = _F;
  1355.     if (_F != _L)
  1356.         for (; ++_F != _L; )
  1357.             if (_P(*_X, *_F))
  1358.                 _X = _F;
  1359.     return (_X); }
  1360.         // TEMPLATE FUNCTION min_element
  1361. template<class _FI> inline
  1362.     _FI min_element(_FI _F, _FI _L)
  1363.     {_FI _X = _F;
  1364.     if (_F != _L)
  1365.         for (; ++_F != _L; )
  1366.             if (*_F < *_X)
  1367.                 _X = _F;
  1368.     return (_X); }
  1369.         // TEMPLATE FUNCTION min_element WITH PRED
  1370. template<class _FI, class _Pr> inline
  1371.     _FI min_element(_FI _F, _FI _L, _Pr _P)
  1372.     {_FI _X = _F;
  1373.     if (_F != _L)
  1374.         for (; ++_F != _L; )
  1375.             if (_P(*_F, *_X))
  1376.                 _X = _F;
  1377.     return (_X); }
  1378.         // TEMPLATE FUNCTION next_permutation
  1379. template<class _BI> inline
  1380.     bool next_permutation(_BI _F, _BI _L)
  1381.     {_BI _I = _L;
  1382.     if (_F == _L || _F == --_I)
  1383.         return (false);
  1384.     for (; ; )
  1385.         {_BI _Ip = _I;
  1386.         if (*--_I < *_Ip)
  1387.             {_BI _J = _L;
  1388.             for (; !(*_I < *--_J); )
  1389.                 ;
  1390.             iter_swap(_I, _J);
  1391.             reverse(_Ip, _L);
  1392.             return (true); }
  1393.         if (_I == _F)
  1394.             {reverse(_F, _L);
  1395.             return (false); }}}
  1396.         // TEMPLATE FUNCTION next_permutation WITH PRED
  1397. template<class _BI, class _Pr> inline
  1398.     bool next_permutation(_BI _F, _BI _L, _Pr _P)
  1399.     {_BI _I = _L;
  1400.     if (_F == _L || _F == --_I)
  1401.         return (false);
  1402.     for (; ; )
  1403.         {_BI _Ip = _I;
  1404.         if (_P(*--_I, *_Ip))
  1405.             {_BI _J = _L;
  1406.             for (; !_P(*_I, *--_J); )
  1407.                 ;
  1408.             iter_swap(_I, _J);
  1409.             reverse(_Ip, _L);
  1410.             return (true); }
  1411.         if (_I == _F)
  1412.             {reverse(_F, _L);
  1413.             return (false); }}}
  1414.         // TEMPLATE FUNCTION prev_permutation
  1415. template<class _BI> inline
  1416.     bool prev_permutation(_BI _F, _BI _L)
  1417.     {_BI _I = _L;
  1418.     if (_F == _L || _F == --_I)
  1419.         return (false);
  1420.     for (; ; )
  1421.         {_BI _Ip = _I;
  1422.         if (!(*--_I < *_Ip))
  1423.             {_BI _J = _L;
  1424.             for (; *_I < *--_J; )
  1425.                 ;
  1426.             iter_swap(_I, _J);
  1427.             reverse(_Ip, _L);
  1428.             return (true); }
  1429.         if (_I == _F)
  1430.             {reverse(_F, _L);
  1431.             return (false); }}}
  1432.         // TEMPLATE FUNCTION prev_permutation WITH PRED
  1433. template<class _BI, class _Pr> inline
  1434.     bool prev_permutation(_BI _F, _BI _L, _Pr _P)
  1435.     {_BI _I = _L;
  1436.     if (_F == _L || _F == --_I)
  1437.         return (false);
  1438.     for (; ; )
  1439.         {_BI _Ip = _I;
  1440.         if (!_P(*--_I, *_Ip))
  1441.             {_BI _J = _L;
  1442.             for (; _P(*_I, *--_J); )
  1443.                 ;
  1444.             iter_swap(_I, _J);
  1445.             reverse(_Ip, _L);
  1446.             return (true); }
  1447.         if (_I == _F)
  1448.             {reverse(_F, _L);
  1449.             return (false); }}}
  1450. _STD_END
  1451. #ifdef  _MSC_VER
  1452. #pragma pack(pop)
  1453. #endif  /* _MSC_VER */
  1454.  
  1455. #endif /* _ALGORITHM_ */
  1456.  
  1457. /*
  1458.  * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
  1459.  * Consult your license regarding permissions and restrictions.
  1460.  */
  1461.  
  1462. /*
  1463.  * This file is derived from software bearing the following
  1464.  * restrictions:
  1465.  *
  1466.  * Copyright (c) 1994
  1467.  * Hewlett-Packard Company
  1468.  *
  1469.  * Permission to use, copy, modify, distribute and sell this
  1470.  * software and its documentation for any purpose is hereby
  1471.  * granted without fee, provided that the above copyright notice
  1472.  * appear in all copies and that both that copyright notice and
  1473.  * this permission notice appear in supporting documentation.
  1474.  * Hewlett-Packard Company makes no representations about the
  1475.  * suitability of this software for any purpose. It is provided
  1476.  * "as is" without express or implied warranty.
  1477.  */
  1478.