// xheap internal header
#ifndef _XHEAP_
#define _XHEAP_

 #if defined(__ghs)
  #pragma ghs start_cxx_lib_header
  #pragma ghs startdata
  #if defined(__ghs_max_pack_value)
   #pragma pack (push, __ghs_max_pack_value)
  #endif /* defined(__ghs_max_pack_value) */
 #endif /* defined(__ghs) */

_STD_BEGIN
 #if _ITERATOR_DEBUG_LEVEL == 2
		// TEMPLATE FUNCTION _Debug_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Debug_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// test if range is a heap ordered by _Pred
	if (_First != _Last)
		for (_RanIt _Root = _First; ++_First != _Last; ++_Root)
			{	// test a pair
			if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
				_DEBUG_ERROR("invalid heap");
			else if (++_First == _Last)
				break;
			else if (_DEBUG_LT_PRED(_Pred, *_Root, *_First))
				_DEBUG_ERROR("invalid heap");
			}
	}

  #define _DEBUG_HEAP_PRED(first, last, pred)	\
	_Debug_heap(_Unchecked(first), _Unchecked(last), pred)

 #else /* _ITERATOR_DEBUG_LEVEL == 2 */
  #define _DEBUG_HEAP_PRED(first, last, pred)
 #endif /* _ITERATOR_DEBUG_LEVEL == 2 */

		// TEMPLATE FUNCTION push_heap WITH PRED
template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Push_heap(_RanIt _First, _Diff _Hole,
		_Diff _Top, _Ty _VALREF _Val, _Pr _Pred)
	{	// percolate _Hole to _Top or where _Val belongs, using _Pred
	for (_Diff _Idx = (_Hole - 1) / 2;
		_Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val);
		_Idx = (_Hole - 1) / 2)
		{	// move _Hole up to parent
		*(_First + _Hole) = _Move(*(_First + _Idx));
		_Hole = _Idx;
		}

	*(_First + _Hole) = _Move(_Val);	// drop _Val into final hole
	}

template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Push_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
	{	// push *_Last onto heap at [_First, _Last), using _Pred
	_Diff _Count = _Last - _First;
	if (0 < _Count)
		{	// worth doing, percolate *_Last
		_Ty _Val = _Move(*_Last);
		_Push_heap(_First, _Count, _Diff(0), _Move(_Val), _Pred);
		}
	}

template<class _RanIt,
	class _Pr> inline
	void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	if (_First != _Last)
		{	// check and push to nontrivial heap
		--_Last;
		_DEBUG_HEAP_PRED(_First, _Last, _Pred);
		_Push_heap_0(_Unchecked(_First), _Unchecked(_Last), _Pred,
			_Dist_type(_First), _Val_type(_First));
		}
	}

		// TEMPLATE FUNCTION push_heap
template<class _RanIt> inline
	void push_heap(_RanIt _First, _RanIt _Last)
	{	// push *(_Last - 1) onto heap at [_First, _Last - 1), using operator<
	_STD push_heap(_First, _Last, _FUNCTOR(less, _First));
	}

		// TEMPLATE FUNCTION pop_heap WITH PRED
template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom,
		_Ty _VALREF _Val, _Pr _Pred)
	{	// percolate _Hole to _Bottom, then push _Val, using _Pred
	_Diff _Top = _Hole;
	_Diff _Idx = 2 * _Hole + 2;

	for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2)
		{	// move _Hole down to larger child
		if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1))))
			--_Idx;
		*(_First + _Hole) = _Move(*(_First + _Idx));
		_Hole = _Idx;
		}

	if (_Idx == _Bottom)
		{	// only child at bottom, move _Hole down to it
		*(_First + _Hole) = _Move(*(_First + (_Bottom - 1)));
		_Hole = _Bottom - 1;
		}
	_Push_heap(_First, _Hole, _Top, _Move(_Val), _Pred);
	}

template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Pop_heap(_RanIt _First, _RanIt _Last, _RanIt _Dest,
		_Ty _VALREF _Val, _Pr _Pred, _Diff *)
	{	// pop *_First to *_Dest and reheap, using _Pred
	*_Dest = _Move(*_First);
	_Adjust_heap(_First, _Diff(0), _Diff(_Last - _First),
		_Move(_Val), _Pred);
	}

template<class _RanIt,
	class _Ty,
	class _Pr> inline
	void _Pop_heap_0(_RanIt _First, _RanIt _Last, _Pr _Pred, _Ty *)
	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
	_Ty _Val = _Move(*(_Last - 1));
	_Pop_heap(_First, _Last - 1, _Last - 1,
		_Move(_Val), _Pred, _Dist_type(_First));
	}

template<class _RanIt,
	class _Pr> inline
	void _Pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
	_Pop_heap_0(_Unchecked(_First), _Unchecked(_Last), _Pred,
		_Val_type(_First));
	}

template<class _RanIt,
	class _Pr> inline
	void pop_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// pop *_First to *(_Last - 1) and reheap, using _Pred
	_DEBUG_RANGE_PTR(_First, _Last, _Pred);
	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
	if (2 <= _Last - _First)
		_Pop_heap(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION pop_heap
template<class _RanIt> inline
	void pop_heap(_RanIt _First, _RanIt _Last)
	{	// pop *_First to *(_Last - 1) and reheap, using operator<
	_STD pop_heap(_First, _Last, _FUNCTOR(less, _First));
	}

		// TEMPLATE FUNCTION make_heap WITH PRED
template<class _RanIt,
	class _Diff,
	class _Ty,
	class _Pr> inline
	void _Make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred, _Diff *, _Ty *)
	{	// make nontrivial [_First, _Last) into a heap, using _Pred
	_Diff _Bottom = _Last - _First;
	for (_Diff _Hole = _Bottom / 2; 0 < _Hole; )
		{	// reheap top half, bottom to top
		--_Hole;
		_Ty _Val = _Move(*(_First + _Hole));
		_Adjust_heap(_First, _Hole, _Bottom,
			_Move(_Val), _Pred);
		}
	}

template<class _RanIt,
	class _Pr> inline
	void make_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// make [_First, _Last) into a heap, using _Pred
	_DEBUG_RANGE(_First, _Last);
	if (2 <= _Last - _First)
		{	// validate _Pred and heapify
		_DEBUG_POINTER(_Pred);
		_Make_heap(_Unchecked(_First), _Unchecked(_Last), _Pred,
			_Dist_type(_First), _Val_type(_First));
		}
	}

		// TEMPLATE FUNCTION make_heap
template<class _RanIt> inline
	void make_heap(_RanIt _First, _RanIt _Last)
	{	// make [_First, _Last) into a heap, using operator<
	_STD make_heap(_First, _Last, _FUNCTOR(less, _First));
	}

		// TEMPLATE FUNCTION sort_heap WITH PRED
template<class _RanIt,
	class _Pr> inline
	void _Sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// order heap by repeatedly popping, using _Pred
	for (; 2 <= _Last - _First; --_Last)
		_Pop_heap(_First, _Last, _Pred);
	}

template<class _RanIt,
	class _Pr> inline
	void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred)
	{	// order heap by repeatedly popping, using _Pred
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER_IF(2 <= _Last - _First, _Pred);
	_DEBUG_HEAP_PRED(_First, _Last, _Pred);
	_Sort_heap(_Unchecked(_First), _Unchecked(_Last), _Pred);
	}

		// TEMPLATE FUNCTION sort_heap
template<class _RanIt> inline
	void sort_heap(_RanIt _First, _RanIt _Last)
	{	// order heap by repeatedly popping, using operator<
	_STD sort_heap(_First, _Last, _FUNCTOR(less, _First));
	}
_STD_END

 #if defined(__ghs)
  #if defined(__ghs_max_pack_value)
   #pragma pack(pop)
  #endif /* defined(__ghs_max_pack_value) */
  #pragma ghs enddata
  #pragma ghs end_cxx_lib_header
 #endif /* defined(__ghs) */

#endif /* _XHEAP_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V8.03b/17:0063 */