// Heap Plus implementation 1.01alpha
// ChangeLog:
//  2009.09.26  - Updated __down_heap, added _updatepos (Yanbin Lu)
//  2009.08.10  - Added update_heap_pos functions so that we can adjust
//                heap values outside of update_heap functions -- e.g., if
//                we have external pointers into the heap entries -- then
//                call update_heap on the position only, regardless of the value.
//                (Danny Tarlow: dtarlow@cs.toronto.edu)
//  2006.12.18  - Initially created (lihw)
 
#ifndef HEAPPLUS_H_
#define HEAPPLUS_H_
 
#include <iterator>
 
namespace std {
  template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
	typename _Compare, typename _Updatepos>
    void
    __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
				_Distance __topIndex, _Tp __value, _Compare __comp, _Updatepos __updatepos)
    {
      _Distance __parent = (__holeIndex - 1) / 2;
      while (__holeIndex > __topIndex
			 && __comp(*(__first + __parent), __value))
		{
		  *(__first + __holeIndex) = *(__first + __parent);
		  __updatepos(*(__first + __holeIndex), __holeIndex); /* yanbin */
		  __holeIndex = __parent;
		  __parent = (__holeIndex - 1) / 2;
		}
      *(__first + __holeIndex) = __value;
	  __updatepos(*(__first + __holeIndex), __holeIndex); /* yanbin */
    }

  template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
    inline void
    push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	      _Compare __comp, _Updatepos __updatepos)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap_pred(__first, __last - 1, __comp);

      std::__push_heap(__first, _DistanceType((__last - __first) - 1),
		       _DistanceType(0), _ValueType(*(__last - 1)), __comp, __updatepos);
    }

  template<typename _RandomAccessIterator, typename _Distance,
	typename _Tp, typename _Compare, typename _Updatepos>
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
				  _Distance __len, _Tp __value, _Compare __comp, _Updatepos __updatepos)
  {
	const _Distance __topIndex = __holeIndex;
	_Distance __secondChild = 2 * __holeIndex + 2;
	while (__secondChild < __len)
	  {
		if (__comp(*(__first + __secondChild),
				   *(__first + (__secondChild - 1))))
		  __secondChild--;
		*(__first + __holeIndex) = *(__first + __secondChild);
		__updatepos(*(__first + __holeIndex), __holeIndex); /* yanbin */
		__holeIndex = __secondChild;
		__secondChild = 2 * (__secondChild + 1);
	  }
	if (__secondChild == __len)
	  {
		*(__first + __holeIndex) = *(__first + (__secondChild - 1));
		__updatepos(*(__first + __holeIndex), __holeIndex); /* yanbin */
		__holeIndex = __secondChild - 1;
	  }
	std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp, __updatepos);
  }

  template<typename _RandomAccessIterator, typename _Tp, typename _Compare, typename _Updatepos>
    inline void
    __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
	       _RandomAccessIterator __result, _Tp __value, _Compare __comp, _Updatepos __updatepos)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	_Distance;
      *__result = *__first;
      std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
			 __value, __comp, __updatepos);
    }

  template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
    inline void
    pop_heap(_RandomAccessIterator __first,
			 _RandomAccessIterator __last, _Compare __comp, _Updatepos __updatepos)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
	    _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_heap_pred(__first, __last, __comp);

      typedef typename iterator_traits<_RandomAccessIterator>::value_type
	_ValueType;
      std::__pop_heap(__first, __last - 1, __last - 1,
		      _ValueType(*(__last - 1)), __comp, __updatepos);
    }

  template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
    inline void
    make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
			  _Compare __comp, _Updatepos __updatepos)
  {
	typedef typename iterator_traits<_RandomAccessIterator>::value_type
	  _ValueType;
	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
	  _DistanceType;

	// concept requirements
	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
								_RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);

	if (__last - __first < 2)
	  {
		for (_DistanceType __len = 0; __len < __last - __first; __len ++)
		  {
			__updatepos(*(__first + __len), __len); /* yanbin */
		  }

		return;
	  }
	const _DistanceType __len = __last - __first;
	_DistanceType __parent = (__len - 2) / 2;
	while (true)
	  {
		std::__adjust_heap(__first, __parent, __len,
						   _ValueType(*(__first + __parent)), __comp, __updatepos);
		if (__parent == 0)
		  {
			for (_DistanceType __len = 0; __len < __last - __first; __len ++)
			  {
				__updatepos(*(__first + __len), __len); /* yanbin */
			  }

			return;
		  }
		__parent--;
	  }

  }


  template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare, typename _Updatepos>
inline void
__up_heap(_RandomAccessIterator __first, _RandomAccessIterator __end, _RandomAccessIterator __pos,
		  _Distance, _Tp __value,  _Compare __comp, _Updatepos __updatepos)
{
    _Distance __parent = (__pos - __first - 1) /  2;
    _Distance __index = __pos - __first;
    while (__index > 0 && __comp(*(__first + __parent), __value)) {
        *(__first + __index) = *(__first + __parent);
		__updatepos(*(__first + __index), __index); /* yanbin */

        __index = __parent;
        __parent = (__parent - 1) / 2;
    }
        
    if (__pos != (__first + __index)) {
        *(__first + __index) = __value;
		__updatepos(*(__first + __index), __index); /* yanbin */
	}
}
 
template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare, typename _Updatepos>
inline void
__down_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pos,
        _Distance, _Tp __value, _Compare __comp, _Updatepos __updatepos)
{
    _Distance __len = __last - __first;
    _Distance __index = __pos - __first;
    _Distance __left = __index * 2 + 1;
    _Distance __right = __index * 2 + 2;
    _Distance __largest;
    while (__index < __len) 
	  {
		if (__right < __len)
		  {
			if (__comp(*(__first + __left), *(__first + __right)))
			  {
				__largest = __right;
			  }
			else
			  {
				__largest = __left;
			  }
		  }
		else if (__left < __len)
		  {
			__largest = __left;
		  }
		else
		  {
			__largest = __index;
		  }

        if (__largest < __len && __comp(__value, *(__first + __largest))) 
		  {
            *(__first + __index) = *(__first + __largest);
			__updatepos(*(__first + __index), __index); /* yanbin */
            __index = __largest;
            __left = __index * 2 + 1;
            __right = __index * 2 + 2;
		  } else
		  break;
	  }
 
    if (__pos != (__first + __index)) {
        *(__first + __index) = __value;
		__updatepos(*(__first + __index), __index); /* yanbin */
	}
}
 
template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
    typename _Compare, typename _Updatepos>
inline void
__update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _RandomAccessIterator __pos, _Distance, _Tp __value, _Compare __comp, _Updatepos __updatepos)
{
    *(__pos) = __value;
     
    _Distance __index = (__pos - __first);
    _Distance __parent = (__index - 1) / 2;
 
    if (__index > 0 && __comp(*(__first + __parent), __value))
	  __up_heap(__first, __last, __pos, _Distance(), __value, __comp, __updatepos);
    else
	  __down_heap(__first, __last, __pos, _Distance(), __value, __comp, __updatepos);
}
 
template<typename _RandomAccessIterator, typename _Distance, typename _Compare, typename _Updatepos>
inline void
__update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _RandomAccessIterator __pos, _Distance, _Compare __comp, _Updatepos __updatepos)
{
    _Distance __index = (__pos - __first);
    _Distance __parent = (__index - 1) / 2;
    if (__index > 0 && __comp(*(__first + __parent), *(__pos)))
      __up_heap(__first, __last, __pos, _Distance(), *(__pos), __comp, __updatepos);
    else
      __down_heap(__first, __last, __pos, _Distance(), *(__pos), __comp, __updatepos);
}
 
template<typename _RandomAccessIterator, typename _Tp, typename _Updatepos>
inline void
update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _RandomAccessIterator __pos, _Tp __value, _Updatepos __updatepos)
{
      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
 
      __update_heap(__first, __last, __pos, _DistanceType(), __value, less<_ValueType>(), __updatepos);
}
 
template<typename _RandomAccessIterator, typename _Tp, typename _Compare, typename _Updatepos>
inline void
update_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
        _RandomAccessIterator __pos, _Tp __value, _Compare __comp, _Updatepos __updatepos)
{
  __update_heap(__first, __last, __pos, __value, __comp, __updatepos);
}
 
 
 template<typename _RandomAccessIterator, typename _Updatepos>
inline void
update_heap_pos(_RandomAccessIterator __first, _RandomAccessIterator __last,
  _RandomAccessIterator __pos, _Updatepos __updatepos) {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;
 
      __update_heap(__first, __last, __pos, _DistanceType(), less<_ValueType>(), __updatepos);
}
 
 
template<typename _RandomAccessIterator, typename _Compare, typename _Updatepos>
inline void
update_heap_pos(_RandomAccessIterator __first, _RandomAccessIterator __last,
  _RandomAccessIterator __pos, _Compare __comp, _Updatepos __updatepos) {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;
      typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType;

      __update_heap(__first, __last, __pos, _DistanceType(), __comp, __updatepos);
}
 
 
 
}; // namespace std
 
#endif // !HEAPPLUS_H_