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); |
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, |
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 |
|
} |