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