inplace_merge overhaul

algorithm.cpp

template<class _BidIt,
	class _Diff,
	class _Ty> inline
	_BidIt _Buffered_rotate_unchecked(const _BidIt _First, const _BidIt _Mid, const _BidIt _Last,
		const _Diff _Count1, const _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf)
	{	// rotate [_First, _Last) using temp buffer
		// precondition: _Count1 == distance(_First, _Mid)
		// precondition: _Count2 == distance(_Mid, _Last)
	if (_Count1 == 0)
		{	// do nothing
		return (_Last);
		}

	if (_Count2 == 0)
		{	// do nothing
		return (_First);
		}

	if (_Count1 <= _Count2 && _Count1 <= _Temp_buf._Capacity)
		{	// buffer left range, then copy parts
		_Temporary_range<_Ty> _Temp(_Temp_buf, _First, _Mid, _Count1);
		const _BidIt _New_mid = _Move_unchecked(_Mid, _Last, _First);
		_Move_unchecked(_Temp._Begin(), _Temp._End(), _New_mid);
		return (_New_mid);
		}

	if (_Count2 <= _Temp_buf._Capacity)
		{	// buffer right range, then copy parts
		_Temporary_range<_Ty> _Temp(_Temp_buf, _Mid, _Last, _Count2);
		_Move_backward_unchecked(_First, _Mid, _Last);
		return (_Move_unchecked(_Temp._Begin(), _Temp._End(), _First));
		}

	// buffer too small, rotate in place
	return (_Rotate_unchecked(_First, _Mid, _Last));
	}


// TEMPLATE FUNCTION inplace_merge WITH PRED
		// The "usual invariants" for the inplace_merge helpers below are:
		// [_First, _Mid) and [_Mid, _Last) are sorted
		// _Pred(*_Mid, *_First)
		// _Pred(*prev(_Last), *prev(_Mid))
		// _Count1 == distance(_First, _Mid)
		// _Count2 == distance(_Mid, _Last)

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Inplace_merge_buffer_left_and_merge_down(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// copy the range [_First, _Mid) to _Temp_buf, and merge it down to _First, using _Pred
		// usual invariants apply
	_Temporary_range<_Ty> _Temp(_Temp_buf, _First, _Mid, _Count1);
	_Ty * _Left_first = _Temp._Begin();
	_Ty * const _Left_last = _Temp._End() - 1; // avoid a compare with the highest element
	*_First = _STD move(*_Mid); // the lowest element is now in position
	++_First;
	++_Mid;
	for (;;)
		{
		if (_Pred(*_Mid, *_Left_first))
			{	// take element from the right partition
			*_First = _STD move(*_Mid);
			++_First;
			++_Mid;
			if (_Mid == _Last)
				{
				_Move_unchecked(_Left_first, _Temp._End(), _First);	// move any tail (and the highest element)
				return;
				}
			}
		else
			{	// take element from the left partition
			*_First = _STD move(*_Left_first);
			++_First;
			++_Left_first;
			if (_Left_first == _Left_last)
				{	// move the remaining right partition and highest element, since *_Left_first is highest
				*_Move_unchecked(_Mid, _Last, _First) = _STD move(*_Left_last);
				return;
				}
			}
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Inplace_merge_buffer_right_and_merge_up(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// copy the range [_Mid, _Last) to _Temp_buf, and merge it up to _Last, using _Pred
		// usual invariants apply
	_Temporary_range<_Ty> _Temp(_Temp_buf, _Mid, _Last, _Count2);
	*--_Last = _STD move(*--_Mid); // move the highest element into position
	_Ty * const _Right_first = _Temp._Begin();
	_Ty * _Right_last = _Temp._End();
	--_Mid;
	--_Right_last;
	for (;;)
		{
		if (_Pred(*_Right_last, *_Mid))
			{	// merge from the left partition
			*--_Last = _STD move(*_Mid);
			if (_First == _Mid)
				{
				*--_Last = _STD move(*_Right_last);	// to make [_Right_first, _Right_last) a halfopen range
				_Move_backward_unchecked(_Right_first, _Right_last, _Last);	// move any head (and lowest element)
				return;
				}

			--_Mid;
			}
		else
			{	// merge from the right partition
			*--_Last = _STD move(*_Right_last);
			--_Right_last;
			if (_Right_first == _Right_last)
				{	// we can't compare with *_Right_first, but we know it is lowest
				*--_Last = _STD move(*_Mid);	// restore half-open range [_First, _Mid)
				_Move_backward_unchecked(_First, _Mid, _Last);
				*_First = _STD move(*_Right_first);
				return;
				}
			}
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred);

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_divide_and_conquer2(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred,
		_BidIt _Firstn, _BidIt _Lastn, _Diff _Count1n, _Diff _Count2n)
	{	// common block of _Buffered_inplace_merge_divide_and_conquer, below
	_BidIt _Midn = _Buffered_rotate_unchecked(_Firstn, _Mid, _Lastn,
		_Count1 - _Count1n, _Count2n, _Temp_buf);	// rearrange middle
	if (_Count1n != 0 && _Count2n != 0)
		{
		_Buffered_inplace_merge_unchecked(_First, _Firstn, _Midn,
			_Count1n, _Count2n, _Temp_buf, _Pred);	// merge each new part
		}

	_Count1 -= _Count1n;
	_Count2 -= _Count2n;
	if (_Count1 != 0 && _Count2 != 0)
		{
		_Buffered_inplace_merge_unchecked(_Midn, _Lastn, _Last,
			_Count1, _Count2, _Temp_buf, _Pred);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_divide_and_conquer(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// merge sorted [_First, _Mid) with sorted [_Mid, _Last), using _Pred
		// usual invariants apply
	if (_Count1 <= _Count2)
		{
		_Diff _Count1n = _Count1 >> 1;	// TRANSITION, VSO#433486
		const _BidIt _Firstn = _STD next(_First, _Count1n);
		const _BidIt _Lastn = _Lower_bound_unchecked(_Mid, _Last, *_Firstn, _Pred);
		_Buffered_inplace_merge_divide_and_conquer2(_First, _Mid, _Last, _Count1, _Count2,
			_Temp_buf, _Pred,
			_Firstn, _Lastn, _Count1n, _STD distance(_Mid, _Lastn));
		}
	else
		{
		_Diff _Count2n = _Count2 >> 1;	// TRANSITION, VSO#433486
		const _BidIt _Lastn = _STD next(_Mid, _Count2n);
		const _BidIt _Firstn = _Upper_bound_unchecked(_First, _Mid, *_Lastn, _Pred);
		_Buffered_inplace_merge_divide_and_conquer2(_First, _Mid, _Last, _Count1, _Count2,
			_Temp_buf, _Pred,
			_Firstn, _Lastn, _STD distance(_First, _Firstn), _Count2n);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_unchecked_impl(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// merge sorted [_First, _Mid) with sorted [_Mid, _Last), using _Pred
		// usual invariants apply
	if (_Count1 == 1 || _Count2 == 1)
		{	// either the left partition is only the highest element, or the right is only the lowest
			// so no compares are needed
		_Buffered_rotate_unchecked(_First, _Mid, _Last, _Count1, _Count2, _Temp_buf);
		}
	else if (_Count1 <= _Count2 && _Count1 <= _Temp_buf._Capacity)
		{
		_Inplace_merge_buffer_left_and_merge_down(_First, _Mid, _Last, _Count1, _Temp_buf, _Pred);
		}
	else if (_Count2 <= _Temp_buf._Capacity)
		{
		_Inplace_merge_buffer_right_and_merge_up(_First, _Mid, _Last, _Count2, _Temp_buf, _Pred);
		}
	else
		{
		_Buffered_inplace_merge_divide_and_conquer(_First, _Mid, _Last, _Count1, _Count2, _Temp_buf, _Pred);
		}
	}

template<class _BidIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Buffered_inplace_merge_unchecked(_BidIt _First, _BidIt _Mid, _BidIt _Last,
		_Diff _Count1, _Diff _Count2, _Temporary_buffer<_Ty>& _Temp_buf, _Pr _Pred)
	{	// merge sorted [_First, _Mid) with sorted [_Mid, _Last), using _Pred
		// usual invariants *do not* apply; only sortedness applies
	// establish the usual invariants (explained in pretty inplace_merge)
	if (_Mid == _Last)
		{
		return;
		}

	for (;;)
		{
		if (_First == _Mid)
			{
			return;
			}

		if (_Pred(*_Mid, *_First))
			{
			break;
			}

		++_First;
		--_Count1;
		}

	const auto _Highest = _Prev_iter(_Mid);
	do
		{
		--_Last;
		--_Count2;
		}
	while (_Last != _Mid && !_Pred(*_Last, *_Highest));
	++_Last;
	++_Count2;
	_Buffered_inplace_merge_unchecked_impl(_First, _Mid, _Last, _Count1, _Count2, _Temp_buf, _Pred);
	}

template<class _BidIt,
	class _Pr> inline
	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last, _Pr _Pred)
	{	// merge [_First, _Mid) with [_Mid, _Last), using _Pred
	_DEBUG_RANGE(_First, _Mid);
	_DEBUG_RANGE(_Mid, _Last);
	using _UBidIt = _Unchecked_t<_BidIt>;
	auto _UFirst = _Unchecked(_First);
	auto _UMid = _Unchecked(_Mid);
	auto _ULast = _Unchecked(_Last);
	_DEBUG_ORDER_UNCHECKED(_UFirst, _UMid, _Pred);
	_DEBUG_ORDER_UNCHECKED(_UMid, _ULast, _Pred);

	// establish the usual invariants:
	if (_UMid == _ULast)
		{	// degenerate case
		return;
		}

	for (;;)
		{
		if (_UFirst == _UMid)
			{	// degenerate case
			return;
			}

		if (_Pred(*_UMid, *_UFirst))
			{	// found an element in the left partition which will have to move to the right one
			break;
			}

		++_UFirst;
		}

	// in the loop below, the _ULast != _UMid compare is not necessary for the algorithm to produce
	// a correct answer, but is necessary to comply with the standard's "at most N-1 compares"
	// requirement in an example like [5, [7), 6)
	const auto _Highest = _Prev_iter(_UMid);
	do
		{
		--_ULast;
		}
	while (_ULast != _UMid && !_Pred(*_ULast, *_Highest));
	++_ULast;

	_Iter_diff_t<_UBidIt> _Count1 = _STD distance(_UFirst, _UMid);
	_Iter_diff_t<_UBidIt> _Count2 = _STD distance(_UMid, _ULast);
	_Temporary_buffer<_Iter_value_t<_UBidIt>> _Temp_buf{_Min_value(_Count1, _Count2)};
	_Buffered_inplace_merge_unchecked_impl(_UFirst, _UMid, _ULast,
		_Count1, _Count2, _Temp_buf, _Pass_fn(_Pred));
	}

		// TEMPLATE FUNCTION inplace_merge
template<class _BidIt> inline
	void inplace_merge(_BidIt _First, _BidIt _Mid, _BidIt _Last)
	{	// merge [_First, _Mid) with [_Mid, _Last), using operator<
	_STD inplace_merge(_First, _Mid, _Last, less<>());
	}