1 // algorithm stl/clr header
2 #ifndef _CLI_ALGORITHM_
3 #define _CLI_ALGORITHM_
4 #include <cliext/memory>
5
6 namespace cliext {
7         // REF CLASS _ISort
8 ref class _ISort
9     {    // define crossover for insertion sort
10 public:
11     literal int _Max = 32;
12     };
13
14         // TEMPLATE FUNCTION for_each
15 template<class _InIt,
16     class _Fn1> inline
17     _Fn1 for_each_unchecked(_InIt _First, _InIt _Last, _Fn1 _Func)
18     {    // perform function for each element
19     for (; _First != _Last; ++_First)
20         _Func(*_First);
21     return (_Func);
22     }
23
24 template<class _InIt,
25     class _Fn1> inline
26     _Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
27     {    // perform function for each element
28     _STLCLRDB_RANGE(_First, _Last);
29     _STLCLRDB_POINTER(_Func);
30     return (cliext::for_each_unchecked(_Unchecked(_First), _Unchecked(_Last),
31         _Func));
32     }
33
34         // TEMPLATE FUNCTION find
35 template<class _InIt,
36     class _Ty> inline
37     _InIt find_unchecked(_InIt _First, _InIt _Last, const _Ty% _Val)
38     {    // find first matching _Val
39     for (; _First != _Last; ++_First)
40         if (*_First == _Val)
41             break;
42     return (_First);
43     }
44
45 template<class _InIt,
46     class _Ty> inline
47     _InIt find(_InIt _First, _InIt _Last, const _Ty% _Val)
48     {    // find first matching _Val
49     _STLCLRDB_RANGE(_First, _Last);
50     return (cliext::find_unchecked(_Unchecked(_First), _Unchecked(_Last),
51         _Val));
52     }
53
54 #ifdef _M_CEE_SAFE
55 #else /* _M_CEE_SAFE */
56 inline const char *find(const char *_First, const char *_Last, int _Val)
57     {    // find first char that matches _Val
58     _STLCLRDB_RANGE(_First, _Last);
59     _First = (const char *)std::memchr(_First, _Val, _Last - _First);
60     return (_First == 0 ? _Last : _First);
61     }
62
63 inline const signed char *find(const signed char *_First,
64     const signed char *_Last, int _Val)
65     {    // find first signed char that matches _Val
66     _STLCLRDB_RANGE(_First, _Last);
67     _First = (const signed char *)std::memchr(_First, _Val,
68         _Last - _First);
69     return (_First == 0 ? _Last : _First);
70     }
71
72 inline const unsigned char *find(const unsigned char *_First,
73     const unsigned char *_Last, int _Val)
74     {    // find first unsigned char that matches _Val
75     _STLCLRDB_RANGE(_First, _Last);
76     _First = (const unsigned char *)std::memchr(_First, _Val,
77         _Last - _First);
78     return (_First == 0 ? _Last : _First);
79     }
80 #endif /* _M_CEE_SAFE */
81
82         // TEMPLATE FUNCTION find_if
83 template<class _InIt,
84     class _Pr> inline
85     _InIt find_if_unchecked(_InIt _First, _InIt _Last, _Pr _Pred)
86     {    // find first satisfying _Pred
87     for (; _First != _Last; ++_First)
88         if (_Pred(*_First))
89             break;
90     return (_First);
91     }
92
93 template<class _InIt,
94     class _Pr> inline
95     _InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
96     {    // find first satisfying _Pred
97     _STLCLRDB_RANGE(_First, _Last);
98     _STLCLRDB_POINTER(_Pred);
99     return (cliext::find_if_unchecked(
100         _Unchecked(_First), _Unchecked(_Last), _Pred));
101     }
102
103         // TEMPLATE FUNCTION adjacent_find
104 template<class _FwdIt> inline
Lines 105 ... 1325 are skipped.
1326     _STLCLRDB_RANGE(_First, _Last);
1327     _STLCLRDB_POINTER(_Pred);
1328     return (cliext::partition_unchecked(
1329         _Unchecked(_First), _Unchecked(_Last), _Pred));
1330     }
1331
1332         // TEMPLATE FUNCTION stable_partition
1333 template<class _BidIt,
1334     class _Pr,
1335     class _Diff,
1336     class _Ty> inline
1337     _BidIt _XStable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
1338         _Diff _Count, _Temp_iterator<_Ty> _Tempbuf)
1339     {    // partition preserving order of equivalents, using _Pred
1340     if (_Count == 1)
1341         return (_Pred(*_First) ? _Last : _First);
1342     else if (_Count <= _Tempbuf._Maxlen())
1343         {    // temp buffer big enough, copy right partition out and back
1344         _BidIt _Next = _First;
1345         for (_Tempbuf._Init(); _First != _Last; ++_First)
1346             if (_Pred(*_First))
1347                 *_Next++ = *_First;
1348             else
1349                 *_Tempbuf++ = *_First;
1350
1351         cliext::copy_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
1352             _Next);    // copy back
1353         return (_Next);
1354         }
1355     else
1356         {    // temp buffer not big enough, divide and conquer
1357         _BidIt _Mid = _First;
1358         cliext::advance(_Mid, _Count / 2);
1359
1360         _BidIt _Left = cliext::_XStable_partition(_First, _Mid, _Pred,
1361             _Count / 2, _Tempbuf);    // form L1R1 in left half
1362         _BidIt _Right = cliext::_XStable_partition(_Mid, _Last, _Pred,
1363             _Count - _Count / 2, _Tempbuf);    // form L2R2 in right half
1364
1365         _Diff _Count1 = 0;
1366         _Iter_distance(_Left, _Mid, _Count1);
1367         _Diff _Count2 = 0;
1368         _Iter_distance(_Mid, _Right, _Count2);
1369
1370         return (cliext::_XBuffered_rotate(_Left, _Mid, _Right,
1371             _Count1, _Count2, _Tempbuf));    // rotate L1R1L2R2 to L1L2R1R2
1372         }
1373     }
1374
1375 #if __cplusplus_cli
1376 template<class _BidIt,
1377     class _Pr,
1378     class _Diff,
1379     class _Ty> inline
1380     _BidIt _XStable_partition(_BidIt _First, _BidIt _Last, _Pr _Pred,
1381         _Diff _Count, _Temp_gc_iterator<_Ty> _Tempbuf)
1382     {    // partition preserving order of equivalents, using _Pred
1383     if (_Count == 0)
1384         return (_First);
1385     else if (_Count == 1)
1386         return (_Pred(*_First) ? _Last : _First);
1387     else if (_Count <= _Tempbuf._Maxlen())
1388         {    // temp buffer big enough, copy right partition out and back
1389         _BidIt _Next = _First;
1390         for (_Tempbuf._Init(); _First != _Last; ++_First)
1391             if (_Pred(*_First))
1392                 *_Next++ = *_First;
1393             else
1394                 *_Tempbuf++ = *_First;
1395
1396         cliext::copy_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
1397             _Next);    // copy back
1398         return (_Next);
1399         }
1400     else
1401         {    // temp buffer not big enough, divide and conquer
1402         _BidIt _Mid = _First;
1403         cliext::advance(_Mid, _Count / 2);
1404
1405         _BidIt _Left = cliext::_XStable_partition(_First, _Mid, _Pred,
1406             _Count / 2, _Tempbuf);    // form L1R1 in left half
1407         _BidIt _Right = cliext::_XStable_partition(_Mid, _Last, _Pred,
1408             _Count - _Count / 2, _Tempbuf);    // form L2R2 in right half
1409
1410         _Diff _Count1 = 0;
1411         _Iter_distance(_Left, _Mid, _Count1);
1412         _Diff _Count2 = 0;
1413         _Iter_distance(_Mid, _Right, _Count2);
1414
1415         return (cliext::_XBuffered_rotate(_Left, _Mid, _Right,
1416             _Count1, _Count2, _Tempbuf));    // rotate L1R1L2R2 to L1L2R1R2
1417         }
1418     }
1419 #endif    // __cplusplus_cli
1420
1421 template<class _BidIt,
1422     class _Pr> inline
1423     _BidIt stable_partition_unchecked(_BidIt _First, _BidIt _Last,
1424         _Pr _Pred)
1425     {    // partition preserving order of equivalents, using _Pred
1426     typedef iterator_traits<_BidIt>::difference_type _Diff;
1427     typedef iterator_traits<_BidIt>::value_type _Ty;
1428
1429     if (_First == _Last)
1430         return (_First);
1431     else
1432         {    // partition nontrivial sequence
1433         _Diff _Count = 0;
1434         _Iter_distance(_First, _Last, _Count);
1435         _TEMP_ITER(_BidIt, _Ty) _Tempbuf(_Count);
1436
1437         return (cliext::_XStable_partition(_First, _Last, _Pred, _Count,
1438             _Tempbuf));
1439         }
1440     }
1441
1442 template<class _BidIt,
1443     class _Pr> inline
1444     _BidIt stable_partition(_BidIt _First, _BidIt _Last,
1445         _Pr _Pred)
1446     {    // partition preserving order of equivalents, using _Pred
1447     _STLCLRDB_RANGE(_First, _Last);
1448     _STLCLRDB_POINTER(_Pred);
1449     return (cliext::stable_partition_unchecked(
1450         _Unchecked(_First), _Unchecked(_Last), _Pred));
1451
1452     }
1453
1454  #if _HAS_ITERATOR_DEBUGGING
1455         // TEMPLATE FUNCTION _XDebug_heap
1456 template<class _RanIt> inline
1457     void _XDebug_heap(_RanIt _First, _RanIt _Last)
1458     {    // test if range is a heap ordered by operator<
1459     typedef iterator_traits<_RanIt>::difference_type _Diff;
1460
1461     _Diff _Size = _Last - _First;
1462     if (2 <= _Size)
1463         for (_Diff _Off = 0; ++_Off < _Size; )
1464             if (_STLCLRDB_LT(*(_First + (_Off - 1) / 2), *(_First + _Off)))
1465                 _STLCLRDB_ERROR("invalid heap");
1466     }
1467
1468         // TEMPLATE FUNCTION _XDebug_heap WITH PRED
1469 template<class _RanIt,
1470     class _Pr> inline
1471     void _XDebug_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
1472     {    // test if range is a heap ordered by _Pred
1473     typedef iterator_traits<_RanIt>::difference_type _Diff;
1474
1475     _Diff _Size = _Last - _First;
1476     if (2 <= _Size)
1477         for (_Diff _Off = 0; ++_Off < _Size; )
1478             if (_STLCLRDB_LT_PRED(_Pred, *(_First + (_Off - 1) / 2),
1479                 *(_First + _Off)))
1480                 _STLCLRDB_ERROR("invalid heap");
1481     }
1482
1483   #define _STLCLRDB_HEAP(first, last)    \
1484     _XDebug_heap(first, last)
1485   #define _STLCLRDB_HEAP_PRED(first, last, pred)    \
1486     _XDebug_heap(first, last, pred)
1487
1488  #else /* _HAS_ITERATOR_DEBUGGING */
1489   #define _STLCLRDB_HEAP(first, last)
1490   #define _STLCLRDB_HEAP_PRED(first, last, pred)
1491  #endif /* _HAS_ITERATOR_DEBUGGING */
1492
1493         // TEMPLATE FUNCTION push_heap
1494 template<class _RanIt,
1495     class _Diff,
1496     class _Ty> inline
1497     void _XPush_heap(_RanIt _First, _Diff _Hole,
1498         _Diff _Top, _Ty _Val)
1499     {    // percolate _Hole to _Top or where _Val belongs, using operator<
1500     for (_Diff _Idx = (_Hole - 1) / 2;
1501         _Top < _Hole && _STLCLRDB_LT(*(_First + _Idx), _Val);
1502         _Idx = (_Hole - 1) / 2)
1503         {    // move _Hole up to parent
1504         *(_First + _Hole) = *(_First + _Idx);
Lines 1505 ... 2114 are skipped.
2115     _Dest = cliext::copy_unchecked(_First1, _Last1, _Dest);    // copy any tail
2116     return (cliext::copy_unchecked(_First2, _Last2, _Dest));
2117     }
2118
2119 template<class _InIt1,
2120     class _InIt2,
2121     class _OutIt,
2122     class _Pr> inline
2123     _OutIt merge(_InIt1 _First1, _InIt1 _Last1,
2124         _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest, _Pr _Pred)
2125     {    //  copy merging ranges, both using _Pred
2126     _STLCLRDB_ORDER_PRED(_First1, _Last1, _Pred);
2127     _STLCLRDB_ORDER_PRED(_First2, _Last2, _Pred);
2128     _STLCLRDB_POINTER(_Dest);
2129     return (cliext::merge_unchecked(
2130         _Unchecked(_First1), _Unchecked(_Last1),
2131         _Unchecked(_First2), _Unchecked(_Last2),
2132         _Unchecked(_Dest), _Pred));
2133     }
2134
2135         // TEMPLATE FUNCTION inplace_merge
2136 template<class _BidIt,
2137     class _Diff,
2138     class _Ty> inline
2139     _BidIt _XBuffered_rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2140         _Diff _Count1, _Diff _Count2, _Temp_iterator<_Ty> _Tempbuf)
2141     {    // rotate [_First, _Last) using temp buffer
2142     if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2143         {    // buffer left partition, then copy parts
2144         cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
2145         cliext::copy_unchecked(_Mid, _Last, _First);
2146         return (cliext::copy_backward_unchecked(
2147             _Tempbuf._First(), _Tempbuf._Last(), _Last));
2148         }
2149     else if (_Count2 <= _Tempbuf._Maxlen())
2150         {    // buffer right partition, then copy parts
2151         cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
2152         cliext::copy_backward_unchecked(_First, _Mid, _Last);
2153         return (cliext::copy_unchecked(
2154             _Tempbuf._First(), _Tempbuf._Last(), _First));
2155         }
2156     else
2157         {    // buffer too small, rotate in place
2158         cliext::rotate_unchecked(_First, _Mid, _Last);
2159         cliext::advance(_First, _Count2);
2160         return (_First);
2161         }
2162     }
2163
2164 #if  __cplusplus_cli
2165 template<class _BidIt,
2166     class _Diff,
2167     class _Ty> inline
2168     _BidIt _XBuffered_rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2169         _Diff _Count1, _Diff _Count2, _Temp_gc_iterator<_Ty> _Tempbuf)
2170     {    // rotate [_First, _Last) using temp buffer
2171     if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2172         {    // buffer left partition, then copy parts
2173         cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
2174         cliext::copy_unchecked(_Mid, _Last, _First);
2175         return (cliext::copy_backward_unchecked(
2176             _Tempbuf._First(), _Tempbuf._Last(), _Last));
2177         }
2178     else if (_Count2 <= _Tempbuf._Maxlen())
2179         {    // buffer right partition, then copy parts
2180         cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
2181         cliext::copy_backward_unchecked(_First, _Mid, _Last);
2182         return (cliext::copy_unchecked(
2183             _Tempbuf._First(), _Tempbuf._Last(), _First));
2184         }
2185     else
2186         {    // buffer too small, rotate in place
2187         cliext::rotate_unchecked(_First, _Mid, _Last);
2188         cliext::advance(_First, _Count2);
2189         return (_First);
2190         }
2191     }
2192 #endif    // __cplusplus_cli
2193
2194 template<class _BidIt1,
2195     class _BidIt2,
2196     class _BidIt3> inline
2197     _BidIt3 _XMerge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2198         _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest)
2199     {    // merge backwards to _Dest, using operator<
2200     for (; ; )
2201         if (_First1 == _Last1)
2202             return (cliext::copy_backward_unchecked(_First2, _Last2, _Dest));
2203         else if (_First2 == _Last2)
2204             return (cliext::copy_backward_unchecked(_First1, _Last1, _Dest));
2205         else if (_STLCLRDB_LT(*--_Last2, *--_Last1))
2206             *--_Dest = *_Last1, ++_Last2;
2207         else
2208             *--_Dest = *_Last2, ++_Last1;
2209     }
2210
2211 template<class _BidIt,
2212     class _Diff,
2213     class _Ty> inline
2214     void _XBuffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2215         _Diff _Count1, _Diff _Count2,
2216             _Temp_iterator<_Ty> _Tempbuf)
2217     {    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2218     if (_Count1 + _Count2 == 2)
2219         {    // order two one-element partitions
2220         if (_STLCLRDB_LT(*_Mid, *_First))
2221             cliext::iter_swap(_First, _Mid);
2222         }
2223     else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2224         {    // buffer left partition, then merge
2225         cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
2226         cliext::merge_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
2227             _Mid, _Last, _First);
2228         }
2229     else if (_Count2 <= _Tempbuf._Maxlen())
2230         {    // buffer right partition, then merge
2231         cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
2232         cliext::_XMerge_backward(_First, _Mid,
2233             _Tempbuf._First(), _Tempbuf._Last(), _Last);
2234         }
2235     else
2236         {    // buffer too small, divide and conquer
2237         _BidIt _Firstn, _Lastn;
2238         _Diff _Count1n, _Count2n;
2239
2240         if (_Count2 < _Count1)
2241             {    // left larger, cut it in half and partition right to match
2242             _Count1n = _Count1 / 2, _Count2n = 0;
2243             _Firstn = _First;
2244             cliext::advance(_Firstn, _Count1n);
2245             _Lastn = cliext::lower_bound_unchecked(_Mid, _Last, *_Firstn);
2246             _Iter_distance(_Mid, _Lastn, _Count2n);
2247             }
2248         else
2249             {    // right larger, cut it in half and partition left to match
2250             _Count1n = 0, _Count2n = _Count2 / 2;
2251             _Lastn = _Mid;
2252             cliext::advance(_Lastn, _Count2n);
2253             _Firstn = cliext::upper_bound_unchecked(_First, _Mid, *_Lastn);
2254             _Iter_distance(_First, _Firstn, _Count1n);
2255             }
2256
2257         _BidIt _Midn = cliext::_XBuffered_rotate(_Firstn, _Mid, _Lastn,
2258             _Count1 - _Count1n, _Count2n, _Tempbuf);    // rearrange middle
2259         cliext::_XBuffered_merge(_First, _Firstn, _Midn,
2260             _Count1n, _Count2n, _Tempbuf);    // merge each new part
2261         cliext::_XBuffered_merge(_Midn, _Lastn, _Last,
2262             _Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf);
2263         }
2264     }
2265
2266 #if __cplusplus_cli
2267 template<class _BidIt,
2268     class _Diff,
2269     class _Ty> inline
2270     void _XBuffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2271         _Diff _Count1, _Diff _Count2,
2272             _Temp_gc_iterator<_Ty> _Tempbuf)
2273     {    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2274     if (_Count1 + _Count2 == 2)
2275         {    // order two one-element partitions
2276         if (_STLCLRDB_LT(*_Mid, *_First))
2277             cliext::iter_swap(_First, _Mid);
2278         }
2279     else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2280         {    // buffer left partition, then merge
2281         cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
2282         cliext::merge_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
2283             _Mid, _Last, _First);
2284         }
2285     else if (_Count2 <= _Tempbuf._Maxlen())
2286         {    // buffer right partition, then merge
2287         cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
2288         cliext::_XMerge_backward(_First, _Mid,
2289             _Tempbuf._First(), _Tempbuf._Last(), _Last);
2290         }
2291     else
2292         {    // buffer too small, divide and conquer
2293         _BidIt _Firstn, _Lastn;
2294         _Diff _Count1n, _Count2n;
2295
2296         if (_Count2 < _Count1)
2297             {    // left larger, cut it in half and partition right to match
2298             _Count1n = _Count1 / 2, _Count2n = 0;
2299             _Firstn = _First;
2300             cliext::advance(_Firstn, _Count1n);
2301             _Lastn = cliext::lower_bound_unchecked(_Mid, _Last, *_Firstn);
2302             _Iter_distance(_Mid, _Lastn, _Count2n);
2303             }
2304         else
2305             {    // right larger, cut it in half and partition left to match
2306             _Count1n = 0, _Count2n = _Count2 / 2;
2307             _Lastn = _Mid;
2308             cliext::advance(_Lastn, _Count2n);
2309             _Firstn = cliext::upper_bound_unchecked(_First, _Mid, *_Lastn);
2310             _Iter_distance(_First, _Firstn, _Count1n);
2311             }
2312
2313         _BidIt _Midn = cliext::_XBuffered_rotate(_Firstn, _Mid, _Lastn,
2314             _Count1 - _Count1n, _Count2n, _Tempbuf);    // rearrange middle
2315         cliext::_XBuffered_merge(_First, _Firstn, _Midn,
2316             _Count1n, _Count2n, _Tempbuf);    // merge each new part
2317         cliext::_XBuffered_merge(_Midn, _Lastn, _Last,
2318             _Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf);
2319         }
2320     }
2321 #endif    // __cplusplus_cli
2322
2323 template<class _BidIt> inline
2324     void inplace_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last)
2325     {    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2326     typedef iterator_traits<_BidIt>::difference_type _Diff;
2327     typedef iterator_traits<_BidIt>::value_type _Ty;
2328
2329     if (_First != _Mid && _Mid != _Last)
2330         {    // merge nontrivial sequence
2331         _Diff _Count1 = 0;
2332         _Iter_distance(_First, _Mid, _Count1);
2333         _Diff _Count2 = 0;
2334         _Iter_distance(_Mid, _Last, _Count2);
2335         _TEMP_ITER(_BidIt, _Ty)
2336             _Tempbuf(_Count1 < _Count2 ? _Count1 : _Count2);
2337
2338         cliext::_XBuffered_merge(_First, _Mid, _Last,
2339             _Count1, _Count2, _Tempbuf);
2340         }
2341     }
2342
2343 template<class _BidIt> inline
2344     void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
2345     {    // merge [_First, _Mid) with [_Mid, _Last), using operator<
2346     _STLCLRDB_ORDER(_First, _Mid);
2347     _STLCLRDB_ORDER(_Mid, _Last);
2348     cliext::inplace_merge_unchecked(
2349         _Unchecked(_First), _Unchecked(_Mid), _Unchecked(_Last));
2350     }
2351
2352         // TEMPLATE FUNCTION inplace_merge WITH PRED
2353 template<class _BidIt1,
2354     class _BidIt2,
2355     class _BidIt3,
2356     class _Pr> inline
2357     _BidIt3 _XMerge_backward(_BidIt1 _First1, _BidIt1 _Last1,
2358         _BidIt2 _First2, _BidIt2 _Last2, _BidIt3 _Dest, _Pr _Pred)
2359     {    // merge backwards to _Dest, using _Pred
2360     for (; ; )
2361         if (_First1 == _Last1)
2362             return (cliext::copy_backward_unchecked(_First2, _Last2, _Dest));
2363         else if (_First2 == _Last2)
2364             return (cliext::copy_backward_unchecked(_First1, _Last1, _Dest));
2365         else if (_STLCLRDB_LT_PRED(_Pred, *--_Last2, *--_Last1))
2366             *--_Dest = *_Last1, ++_Last2;
2367         else
2368             *--_Dest = *_Last2, ++_Last1;
2369     }
2370
2371 template<class _BidIt,
2372     class _Diff,
2373     class _Ty,
2374     class _Pr> inline
2375     void _XBuffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2376         _Diff _Count1, _Diff _Count2,
2377             _Temp_iterator<_Ty> _Tempbuf, _Pr _Pred)
2378     {    // merge [_First, _Mid) with [_Mid, _Last), using _Pred
2379     if (_Count1 + _Count2 == 2)
2380         {    // order two one-element partitions
2381         if (_STLCLRDB_LT_PRED(_Pred, *_Mid, *_First))
2382             cliext::iter_swap(_First, _Mid);
2383         }
2384     else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2385         {    // buffer left partition, then merge
2386         cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
2387         cliext::merge_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
2388             _Mid, _Last, _First, _Pred);
2389         }
2390     else if (_Count2 <= _Tempbuf._Maxlen())
2391         {    // buffer right partition, then merge
2392         cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
2393         cliext::_XMerge_backward(_First, _Mid,
2394             _Tempbuf._First(), _Tempbuf._Last(), _Last, _Pred);
2395         }
2396     else
2397         {    // buffer too small, divide and conquer
2398         _BidIt _Firstn, _Lastn;
2399         _Diff _Count1n, _Count2n;
2400         if (_Count2 < _Count1)
2401             {    // left larger, cut it in half and partition right to match
2402             _Count1n = _Count1 / 2, _Count2n = 0;
2403             _Firstn = _First;
2404             cliext::advance(_Firstn, _Count1n);
2405             _Lastn = cliext::lower_bound_unchecked(_Mid, _Last,
2406                 *_Firstn, _Pred);
2407             _Iter_distance(_Mid, _Lastn, _Count2n);
2408             }
2409         else
2410             {    // right larger, cut it in half and partition left to match
2411             _Count1n = 0, _Count2n = _Count2 / 2;
2412             _Lastn = _Mid;
2413             cliext::advance(_Lastn, _Count2n);
2414             _Firstn = cliext::upper_bound_unchecked(_First, _Mid,
2415                 *_Lastn, _Pred);
2416             _Iter_distance(_First, _Firstn, _Count1n);
2417             }
2418         _BidIt _Midn = cliext::_XBuffered_rotate(_Firstn, _Mid, _Lastn,
2419             _Count1 - _Count1n, _Count2n, _Tempbuf);    // rearrange middle
2420         cliext::_XBuffered_merge(_First, _Firstn, _Midn,
2421             _Count1n, _Count2n, _Tempbuf, _Pred);    // merge each new part
2422         cliext::_XBuffered_merge(_Midn, _Lastn, _Last,
2423             _Count1 - _Count1n, _Count2 - _Count2n, _Tempbuf, _Pred);
2424         }
2425     }
2426
2427 #if __cplusplus_cli
2428 template<class _BidIt,
2429     class _Diff,
2430     class _Ty,
2431     class _Pr> inline
2432     void _XBuffered_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last,
2433         _Diff _Count1, _Diff _Count2,
2434             _Temp_gc_iterator<_Ty> _Tempbuf, _Pr _Pred)
2435     {    // merge [_First, _Mid) with [_Mid, _Last), using _Pred
2436     if (_Count1 + _Count2 == 2)
2437         {    // order two one-element partitions
2438         if (_STLCLRDB_LT_PRED(_Pred, *_Mid, *_First))
2439             cliext::iter_swap(_First, _Mid);
2440         }
2441     else if (_Count1 <= _Count2 && _Count1 <= _Tempbuf._Maxlen())
2442         {    // buffer left partition, then merge
2443         cliext::copy_unchecked(_First, _Mid, _Tempbuf._Init());
2444         cliext::merge_unchecked(_Tempbuf._First(), _Tempbuf._Last(),
2445             _Mid, _Last, _First, _Pred);
2446         }
2447     else if (_Count2 <= _Tempbuf._Maxlen())
2448         {    // buffer right partition, then merge
2449         cliext::copy_unchecked(_Mid, _Last, _Tempbuf._Init());
2450         cliext::_XMerge_backward(_First, _Mid,
2451             _Tempbuf._First(), _Tempbuf._Last(), _Last, _Pred);
2452         }
2453     else
2454         {    // buffer too small, divide and conquer
2455         _BidIt _Firstn, _Lastn;
2456         _Diff _Count1n, _Count2n;
2457         if (_Count2 < _Count1)
2458             {    // left larger, cut it in half and partition right to match
2459             _Count1n = _Count1 / 2, _Count2n = 0;
2460             _Firstn = _First;
2461             cliext::advance(_Firstn, _Count1n);
2462             _Lastn = cliext::lower_bound_unchecked(_Mid, _Last,
2463                 *_Firstn, _Pred);
2464             _Iter_distance(_Mid, _Lastn, _Count2n);
2465             }
2466         else
2467             {    // right larger, cut it in half and partition left to match
2468             _Count1n = 0, _Count2n = _Count2 / 2;
2469             _Lastn = _Mid;
2470             cliext::advance(_Lastn, _Count2n);
2471             _Firstn = cliext::upper_bound_unchecked(_First, _Mid,
2472                 *_Lastn, _Pred);
2473             _Iter_distance(_First, _Firstn, _Count1n);
2474             }
2475         _BidIt _Midn = cliext::_XBuffered_rotate(_Firstn, _Mid, _Lastn,
2476             _Count1 - _Count1n, _Count2n, _Tempbuf);    // rearrange middle
2477         cliext::_XBuffered_merge(_First, _Firstn, _Midn,
Lines 2478 ... 2845 are skipped.
2846         {    // copy merging pairs of adjacent chunks
2847         _BidIt _Mid1 = _First;
2848         cliext::advance(_Mid1, _Chunk);
2849         _BidIt _Mid2 = _Mid1;
2850         cliext::advance(_Mid2, _Chunk);
2851
2852         _Dest = cliext::merge_unchecked(_First, _Mid1,
2853             _Mid1, _Mid2, _Dest);
2854         _First = _Mid2;
2855         }
2856
2857     if (_Count <= _Chunk)
2858         cliext::copy_unchecked(_First, _Last,
2859             _Dest);    // copy partial last chunk
2860     else
2861         {    // copy merging whole and partial last chunk
2862         _BidIt _Mid = _First;
2863         cliext::advance(_Mid, _Chunk);
2864
2865         cliext::merge_unchecked(_First, _Mid, _Mid, _Last, _Dest);
2866         }
2867     }
2868
2869 template<class _BidIt,
2870     class _Diff,
2871     class _Ty> inline
2872     void _XBuffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
2873         _Temp_iterator<_Ty> _Tempbuf)
2874     {    // sort using temp buffer for merges, using operator<
2875     _BidIt _Mid = _First;
2876     for (_Diff _Nleft = _Count; _ISort::_Max <= _Nleft; _Nleft -= _ISort::_Max)
2877         {    // sort chunks
2878         _BidIt _Midend = _Mid;
2879         cliext::advance(_Midend, (int)_ISort::_Max);
2880
2881         cliext::_XInsertion_sort(_Mid, _Midend);
2882         _Mid = _Midend;
2883         }
2884     cliext::_XInsertion_sort(_Mid, _Last);    // sort partial last chunk
2885
2886     for (_Diff _Chunk = _ISort::_Max; _Chunk < _Count; _Chunk *= 2)
2887         {    // merge adjacent pairs of chunks to and from temp buffer
2888         cliext::_XChunked_merge(_First, _Last, _Tempbuf._Init(),
2889             _Chunk, _Count);
2890         cliext::_XChunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
2891             _Chunk *= 2, _Count);
2892         }
2893     }
2894
2895 #if __cplusplus_cli
2896 template<class _BidIt,
2897     class _Diff,
2898     class _Ty> inline
2899     void _XBuffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
2900         _Temp_gc_iterator<_Ty> _Tempbuf)
2901     {    // sort using temp buffer for merges, using operator<
2902     _BidIt _Mid = _First;
2903     for (_Diff _Nleft = _Count; _ISort::_Max <= _Nleft; _Nleft -= _ISort::_Max)
2904         {    // sort chunks
2905         _BidIt _Midend = _Mid;
2906         cliext::advance(_Midend, (int)_ISort::_Max);
2907
2908         cliext::_XInsertion_sort(_Mid, _Midend);
2909         _Mid = _Midend;
2910         }
2911     cliext::_XInsertion_sort(_Mid, _Last);    // sort partial last chunk
2912
2913     for (_Diff _Chunk = _ISort::_Max; _Chunk < _Count; _Chunk *= 2)
2914         {    // merge adjacent pairs of chunks to and from temp buffer
2915         cliext::_XChunked_merge(_First, _Last, _Tempbuf._Init(),
2916             _Chunk, _Count);
2917         cliext::_XChunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
2918             _Chunk *= 2, _Count);
2919         }
2920     }
2921 #endif    // __cplusplus_cli
2922
2923 template<class _BidIt,
2924     class _Diff,
2925     class _Ty> inline
2926     void _XStable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
2927         _Temp_iterator<_Ty> _Tempbuf)
2928     {    //  sort preserving order of equivalents, using operator<
2929     if (_Count <= _ISort::_Max)
2930         cliext::_XInsertion_sort(_First, _Last);    // small
2931     else
2932         {    // sort halves and merge
2933         _Diff _Count2 = (_Count + 1) / 2;
2934         _BidIt _Mid = _First;
2935         cliext::advance(_Mid, _Count2);
2936
2937         if (_Count2 <= _Tempbuf._Maxlen())
2938             {    // temp buffer big enough, sort each half using buffer
2939             cliext::_XBuffered_merge_sort(_First, _Mid, _Count2,
2940                 _Tempbuf);
2941             cliext::_XBuffered_merge_sort(_Mid, _Last, _Count - _Count2,
2942                 _Tempbuf);
2943             }
2944         else
2945             {    // temp buffer not big enough, divide and conquer
2946             cliext::_XStable_sort(_First, _Mid, _Count2, _Tempbuf);
2947             cliext::_XStable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
2948             }
2949
2950         cliext::_XBuffered_merge(_First, _Mid, _Last,
2951             _Count2, _Count - _Count2, _Tempbuf);    // merge sorted halves
2952         }
2953     }
2954
2955 #if __cplusplus_cli
2956 template<class _BidIt,
2957     class _Diff,
2958     class _Ty> inline
2959     void _XStable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
2960         _Temp_gc_iterator<_Ty> _Tempbuf)
2961     {    //  sort preserving order of equivalents, using operator<
2962     if (_Count <= _ISort::_Max)
2963         cliext::_XInsertion_sort(_First, _Last);    // small
2964     else
2965         {    // sort halves and merge
2966         _Diff _Count2 = (_Count + 1) / 2;
2967         _BidIt _Mid = _First;
2968         cliext::advance(_Mid, _Count2);
2969
2970         if (_Count2 <= _Tempbuf._Maxlen())
2971             {    // temp buffer big enough, sort each half using buffer
2972             cliext::_XBuffered_merge_sort(_First, _Mid, _Count2,
2973                 _Tempbuf);
2974             cliext::_XBuffered_merge_sort(_Mid, _Last, _Count - _Count2,
2975                 _Tempbuf);
2976             }
2977         else
2978             {    // temp buffer not big enough, divide and conquer
2979             cliext::_XStable_sort(_First, _Mid, _Count2, _Tempbuf);
2980             cliext::_XStable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf);
2981             }
2982
2983         cliext::_XBuffered_merge(_First, _Mid, _Last,
2984             _Count2, _Count - _Count2, _Tempbuf);    // merge sorted halves
2985         }
2986     }
2987 #endif    // __cplusplus_cli
2988
2989 template<class _BidIt> inline
2990     void stable_sort_unchecked(_BidIt _First, _BidIt _Last)
2991     {    // sort preserving order of equivalents, using operator<
2992     typedef iterator_traits<_BidIt>::difference_type _Diff;
2993     typedef iterator_traits<_BidIt>::value_type _Ty;
2994
2995     if (_First != _Last)
2996         {    // sort nontrivial sequence
2997         _Diff _Count = 0;
2998         _Iter_distance(_First, _Last, _Count);
2999         _TEMP_ITER(_BidIt, _Ty) _Tempbuf((_Count + 1) / 2);
3000
3001         cliext::_XStable_sort(_First, _Last, _Count, _Tempbuf);
3002         }
3003     }
3004
3005 template<class _BidIt> inline
3006     void stable_sort(_BidIt _First, _BidIt _Last)
3007     {    // sort preserving order of equivalents, using operator<
3008     _STLCLRDB_RANGE(_First, _Last);
3009     cliext::stable_sort_unchecked(_Unchecked(_First), _Unchecked(_Last));
3010     }
3011
3012         // TEMPLATE FUNCTION stable_sort WITH PRED
3013 template<class _BidIt,
3014     class _OutIt,
3015     class _Diff,
3016     class _Pr> inline
3017     void _XChunked_merge(_BidIt _First, _BidIt _Last, _OutIt _Dest,
3018         _Diff _Chunk, _Diff _Count, _Pr _Pred)
3019     {    // copy merging chunks, using _Pred
3020     for (_Diff _Chunk2 = _Chunk * 2; _Chunk2 <= _Count; _Count -= _Chunk2)
3021         {    // copy merging pairs of adjacent chunks
3022         _BidIt _Mid1 = _First;
3023         cliext::advance(_Mid1, _Chunk);
3024         _BidIt _Mid2 = _Mid1;
3025         cliext::advance(_Mid2, _Chunk);
3026
3027         _Dest = cliext::merge_unchecked(_First, _Mid1,
3028             _Mid1, _Mid2, _Dest, _Pred);
3029         _First = _Mid2;
3030         }
3031
3032     if (_Count <= _Chunk)
3033         cliext::copy_unchecked(_First, _Last,
3034             _Dest);    // copy partial last chunk
3035     else
3036         {    // copy merging whole and partial last chunk
3037         _BidIt _Mid1 = _First;
3038         cliext::advance(_Mid1, _Chunk);
3039
3040         cliext::merge_unchecked(_First, _Mid1,
3041             _Mid1, _Last, _Dest, _Pred);
3042         }
3043     }
3044
3045 template<class _BidIt,
3046     class _Diff,
3047     class _Ty,
3048     class _Pr> inline
3049     void _XBuffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3050         _Temp_iterator<_Ty> _Tempbuf, _Pr _Pred)
3051     {    // sort using temp buffer for merges, using _Pred
3052     _BidIt _Mid = _First;
3053     for (_Diff _Nleft = _Count; _ISort::_Max <= _Nleft; _Nleft -= _ISort::_Max)
3054         {    // sort chunks
3055         _BidIt _Midn = _Mid;
3056         cliext::advance(_Midn, (int)_ISort::_Max);
3057
3058         cliext::_XInsertion_sort(_Mid, _Midn, _Pred);
3059         _Mid = _Midn;
3060         }
3061     cliext::_XInsertion_sort(_Mid, _Last, _Pred);    // sort partial last chunk
3062
3063     for (_Diff _Chunk = _ISort::_Max; _Chunk < _Count; _Chunk *= 2)
3064         {    // merge adjacent pairs of chunks to and from temp buffer
3065         cliext::_XChunked_merge(_First, _Last, _Tempbuf._Init(),
3066             _Chunk, _Count, _Pred);
3067         cliext::_XChunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
3068             _Chunk *= 2, _Count, _Pred);
3069         }
3070     }
3071
3072 #if __cplusplus_cli
3073 template<class _BidIt,
3074     class _Diff,
3075     class _Ty,
3076     class _Pr> inline
3077     void _XBuffered_merge_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3078         _Temp_gc_iterator<_Ty> _Tempbuf, _Pr _Pred)
3079     {    // sort using temp buffer for merges, using _Pred
3080     _BidIt _Mid = _First;
3081     for (_Diff _Nleft = _Count; _ISort::_Max <= _Nleft; _Nleft -= _ISort::_Max)
3082         {    // sort chunks
3083         _BidIt _Midn = _Mid;
3084         cliext::advance(_Midn, (int)_ISort::_Max);
3085
3086         cliext::_XInsertion_sort(_Mid, _Midn, _Pred);
3087         _Mid = _Midn;
3088         }
3089     cliext::_XInsertion_sort(_Mid, _Last, _Pred);    // sort partial last chunk
3090
3091     for (_Diff _Chunk = _ISort::_Max; _Chunk < _Count; _Chunk *= 2)
3092         {    // merge adjacent pairs of chunks to and from temp buffer
3093         cliext::_XChunked_merge(_First, _Last, _Tempbuf._Init(),
3094             _Chunk, _Count, _Pred);
3095         cliext::_XChunked_merge(_Tempbuf._First(), _Tempbuf._Last(), _First,
3096             _Chunk *= 2, _Count, _Pred);
3097         }
3098     }
3099 #endif    // __cplusplus_cli
3100
3101 template<class _BidIt,
3102     class _Diff,
3103     class _Ty,
3104     class _Pr> inline
3105     void _XStable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3106         _Temp_iterator<_Ty> _Tempbuf, _Pr _Pred)
3107     {    // sort preserving order of equivalents, using _Pred
3108     if (_Count <= _ISort::_Max)
3109         cliext::_XInsertion_sort(_First, _Last, _Pred);    // small
3110     else
3111         {    // sort halves and merge
3112         _Diff _Count2 = (_Count + 1) / 2;
3113         _BidIt _Mid = _First;
3114         cliext::advance(_Mid, _Count2);
3115
3116         if (_Count2 <= _Tempbuf._Maxlen())
3117             {    // temp buffer big enough, sort each half using buffer
3118             cliext::_XBuffered_merge_sort(_First, _Mid, _Count2,
3119                 _Tempbuf, _Pred);
3120             cliext::_XBuffered_merge_sort(_Mid, _Last, _Count - _Count2,
3121                 _Tempbuf, _Pred);
3122             }
3123         else
3124             {    // temp buffer not big enough, divide and conquer
3125             cliext::_XStable_sort(_First, _Mid, _Count2, _Tempbuf,
3126                 _Pred);
3127             cliext::_XStable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf,
3128                 _Pred);
3129             }
3130
3131         cliext::_XBuffered_merge(_First, _Mid, _Last,
3132             _Count2, _Count - _Count2, _Tempbuf, _Pred);    // merge halves
3133         }
3134     }
3135
3136 #if __cplusplus_cli
3137 template<class _BidIt,
3138     class _Diff,
3139     class _Ty,
3140     class _Pr> inline
3141     void _XStable_sort(_BidIt _First, _BidIt _Last, _Diff _Count,
3142         _Temp_gc_iterator<_Ty> _Tempbuf, _Pr _Pred)
3143     {    // sort preserving order of equivalents, using _Pred
3144     if (_Count <= _ISort::_Max)
3145         cliext::_XInsertion_sort(_First, _Last, _Pred);    // small
3146     else
3147         {    // sort halves and merge
3148         _Diff _Count2 = (_Count + 1) / 2;
3149         _BidIt _Mid = _First;
3150         cliext::advance(_Mid, _Count2);
3151
3152         if (_Count2 <= _Tempbuf._Maxlen())
3153             {    // temp buffer big enough, sort each half using buffer
3154             cliext::_XBuffered_merge_sort(_First, _Mid, _Count2,
3155                 _Tempbuf, _Pred);
3156             cliext::_XBuffered_merge_sort(_Mid, _Last, _Count - _Count2,
3157                 _Tempbuf, _Pred);
3158             }
3159         else
3160             {    // temp buffer not big enough, divide and conquer
3161             cliext::_XStable_sort(_First, _Mid, _Count2, _Tempbuf,
3162                 _Pred);
3163             cliext::_XStable_sort(_Mid, _Last, _Count - _Count2, _Tempbuf,
3164                 _Pred);
3165             }
3166
3167         cliext::_XBuffered_merge(_First, _Mid, _Last,
3168             _Count2, _Count - _Count2, _Tempbuf, _Pred);    // merge halves
3169         }
3170     }
3171 #endif    // __cplusplus_cli
3172
3173 template<class _BidIt,
3174     class _Pr> inline
3175     void stable_sort_unchecked(_BidIt _First, _BidIt _Last, _Pr _Pred)
3176     {    // sort preserving order of equivalents, using _Pred
3177     typedef iterator_traits<_BidIt>::difference_type _Diff;
3178     typedef iterator_traits<_BidIt>::value_type _Ty;
3179
3180     if (_First != _Last)
3181         {    // sort nontrivial sequence
3182         _Diff _Count = 0;
3183         _Iter_distance(_First, _Last, _Count);
3184         _TEMP_ITER(_BidIt, _Ty) _Tempbuf((_Count + 1) / 2);
3185         cliext::_XStable_sort(_First, _Last, _Count, _Tempbuf, _Pred);
3186         }
Lines 3187 ... 3915 are skipped.
3916
3917         // TEMPLATE FUNCTION prev_permutation WITH PRED
3918 template<class _BidIt,
3919     class _Pr> inline
3920     bool prev_permutation_unchecked(_BidIt _First, _BidIt _Last, _Pr _Pred)
3921     {    // reverse permute and test for pure descending, using _Pred
3922     _BidIt _Next = _Last;
3923     if (_First == _Last || _First == --_Next)
3924         return (false);
3925
3926     for (; ; )
3927         {    // find rightmost element not smaller than successor
3928         _BidIt _Next1 = _Next;
3929         if (_STLCLRDB_LT_PRED(_Pred, *_Next1, *--_Next))
3930             {    // swap with rightmost element that's not smaller, flip suffix
3931             _BidIt _Mid = _Last;
3932             for (; !_STLCLRDB_LT_PRED(_Pred, *--_Mid, *_Next); )
3933                 ;
3934             cliext::iter_swap(_Next, _Mid);
3935             cliext::reverse(_Next1, _Last);
3936             return (true);
3937             }
3938
3939         if (_Next == _First)
3940             {    // pure ascending, flip all
3941             cliext::reverse(_First, _Last);
3942             return (false);
3943             }
3944         }
3945     }
3946
3947 template<class _BidIt,
3948     class _Pr> inline
3949     bool prev_permutation(_BidIt _First, _BidIt _Last, _Pr _Pred)
3950     {    // reverse permute and test for pure descending, using _Pred
3951     _STLCLRDB_RANGE(_First, _Last);
3952     _STLCLRDB_POINTER(_Pred);
3953     return (cliext::prev_permutation_unchecked(
3954         _Unchecked(_First), _Unchecked(_Last), _Pred));
3955     }
3956 } // namespace cliext
3957
3958 #endif /* _CLI_ALGORITHM_ */
3959
3960 /*
3961  * Copyright (c) 2004-2007 by Dinkumware, Ltd.  ALL RIGHTS RESERVED.
3962  * Consult your license regarding permissions and restrictions.
3963 V5.03:0009 */
3964