_heap.c File Reference

#include <stl/_heap.h>
#include <stl/_iterator_base.h>

Include dependency graph for _heap.c:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	_STLP_HEAP_C

Functions
template<class _RandomAccessIterator , class _Distance , class _Tp >
_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void	__push_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val)
template<class _RandomAccessIterator , class _Distance , class _Tp >
void	__push_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance *, _Tp *)
template<class _RandomAccessIterator >
void	push_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >
_STLP_INLINE_LOOP void	__push_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __val, _Compare __comp)
template<class _RandomAccessIterator , class _Compare , class _Distance , class _Tp >
void	__push_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Distance *, _Tp *)
template<class _RandomAccessIterator , class _Compare >
void	push_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
template<class _RandomAccessIterator , class _Distance , class _Tp >
void	__adjust_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val)
template<class _RandomAccessIterator , class _Tp >
void	__pop_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *)
template<class _RandomAccessIterator >
void	pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >
void	__adjust_heap (_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __val, _Compare __comp)
template<class _RandomAccessIterator , class _Tp , class _Compare >
void	__pop_heap_aux (_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Compare __comp)
template<class _RandomAccessIterator , class _Compare >
void	pop_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
template<class _RandomAccessIterator , class _Tp , class _Distance >
_STLP_INLINE_LOOP void	__make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp *, _Distance *)
template<class _RandomAccessIterator >
void	make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last)
template<class _RandomAccessIterator , class _Compare , class _Tp , class _Distance >
_STLP_INLINE_LOOP void	__make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Tp *, _Distance *)
template<class _RandomAccessIterator , class _Compare >
void	make_heap (_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)

Macro Definition Documentation

_STLP_HEAP_C

#define _STLP_HEAP_C

Definition at line 27 of file _heap.c.

Function Documentation

__adjust_heap() [1/2]

template<class _RandomAccessIterator , class _Distance , class _Tp >

void __adjust_heap	(	_RandomAccessIterator	__first,
		_Distance	__holeIndex,
		_Distance	__len,
		_Tp	__val
	)

Definition at line 111 of file _heap.c.

                                          {
  _Distance __topIndex = __holeIndex;
  _Distance __secondChild = 2 * __holeIndex + 2;
  while (__secondChild < __len) {
    if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
      __secondChild--;
    *(__first + __holeIndex) = *(__first + __secondChild);
    __holeIndex = __secondChild;
    __secondChild = 2 * (__secondChild + 1);
  }
  if (__secondChild == __len) {
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    __holeIndex = __secondChild - 1;
  }
  __push_heap(__first, __holeIndex, __topIndex, __val);
}

Referenced by __make_heap(), __partial_sort_copy(), and __pop_heap().

__adjust_heap() [2/2]

template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >

void __adjust_heap	(	_RandomAccessIterator	__first,
		_Distance	__holeIndex,
		_Distance	__len,
		_Tp	__val,
		_Compare	__comp
	)

Definition at line 146 of file _heap.c.

{
  _Distance __topIndex = __holeIndex;
  _Distance __secondChild = 2 * __holeIndex + 2;
  while (__secondChild < __len) {
    if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) {
      _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
                           _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __secondChild--;
    }
    *(__first + __holeIndex) = *(__first + __secondChild);
    __holeIndex = __secondChild;
    __secondChild = 2 * (__secondChild + 1);
  }
  if (__secondChild == __len) {
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
    __holeIndex = __secondChild - 1;
  }
  __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
}

__make_heap() [1/2]

template<class _RandomAccessIterator , class _Compare , class _Tp , class _Distance >

_STLP_INLINE_LOOP void __make_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last,
		_Compare	__comp,
		_Tp *	,
		_Distance *
	)

Definition at line 216 of file _heap.c.

{
  if (__last - __first < 2) return;
  _Distance __len = __last - __first;
  _Distance __parent = (__len - 2)/2;
 
  for (;;) {
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
                  __comp);
    if (__parent == 0) return;
    __parent--;
  }
}

__make_heap() [2/2]

template<class _RandomAccessIterator , class _Tp , class _Distance >

_STLP_INLINE_LOOP void __make_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last,
		_Tp *	,
		_Distance *
	)

Definition at line 190 of file _heap.c.

{
  if (__last - __first < 2) return;
  _Distance __len = __last - __first;
  _Distance __parent = (__len - 2)/2;
 
  for (;;) {
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
    if (__parent == 0) return;
    __parent--;
  }
}

Referenced by make_heap().

__pop_heap_aux() [1/2]

template<class _RandomAccessIterator , class _Tp >

void __pop_heap_aux ( _RandomAccessIterator  __first, _RandomAccessIterator  __last, _Tp *    )

inline

Definition at line 132 of file _heap.c.

                                                                                  {
  __pop_heap(__first, __last - 1, __last - 1,
             _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
}

Referenced by pop_heap().

__pop_heap_aux() [2/2]

template<class _RandomAccessIterator , class _Tp , class _Compare >

void __pop_heap_aux ( _RandomAccessIterator  __first, _RandomAccessIterator  __last, _Tp *  , _Compare  __comp  )

inline

Definition at line 171 of file _heap.c.

{
  __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
             _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
}

__push_heap() [1/2]

template<class _RandomAccessIterator , class _Distance , class _Tp >

_STLP_BEGIN_NAMESPACE _STLP_INLINE_LOOP void __push_heap	(	_RandomAccessIterator	__first,
		_Distance	__holeIndex,
		_Distance	__topIndex,
		_Tp	__val
	)

Definition at line 42 of file _heap.c.

{
  _Distance __parent = (__holeIndex - 1) / 2;
  while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
    *(__first + __holeIndex) = *(__first + __parent);
    __holeIndex = __parent;
    __parent = (__holeIndex - 1) / 2;
  }
  *(__first + __holeIndex) = __val;
}

Referenced by __adjust_heap(), and __push_heap_aux().

__push_heap() [2/2]

template<class _RandomAccessIterator , class _Distance , class _Tp , class _Compare >

_STLP_INLINE_LOOP void __push_heap	(	_RandomAccessIterator	__first,
		_Distance	__holeIndex,
		_Distance	__topIndex,
		_Tp	__val,
		_Compare	__comp
	)

Definition at line 76 of file _heap.c.

{
  _Distance __parent = (__holeIndex - 1) / 2;
  while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
    _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
    *(__first + __holeIndex) = *(__first + __parent);
    __holeIndex = __parent;
    __parent = (__holeIndex - 1) / 2;
  }
  *(__first + __holeIndex) = __val;
}

__push_heap_aux() [1/2]

template<class _RandomAccessIterator , class _Compare , class _Distance , class _Tp >

void __push_heap_aux ( _RandomAccessIterator  __first, _RandomAccessIterator  __last, _Compare  __comp, _Distance *  , _Tp *    )

inline

Definition at line 92 of file _heap.c.

{
  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
              _Tp(*(__last - 1)), __comp);
}

__push_heap_aux() [2/2]

template<class _RandomAccessIterator , class _Distance , class _Tp >

void __push_heap_aux ( _RandomAccessIterator  __first, _RandomAccessIterator  __last, _Distance *  , _Tp *    )

inline

Definition at line 56 of file _heap.c.

{
  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
              _Tp(*(__last - 1)));
}

Referenced by push_heap().

make_heap() [1/2]

template<class _RandomAccessIterator >

void make_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last
	)

Definition at line 206 of file _heap.c.

{
  __make_heap(__first, __last,
              _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
}

Referenced by __partial_sort(), __partial_sort_copy(), HeapTest::mkheap0(), HeapTest::mkheap1(), HeapTest::pheap1(), HeapTest::pheap2(), and priority_queue< _Tp, _Sequence, _Compare >::priority_queue().

make_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >

void make_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last,
		_Compare	__comp
	)

Definition at line 233 of file _heap.c.

{
  __make_heap(__first, __last, __comp,
              _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
}

pop_heap() [1/2]

template<class _RandomAccessIterator >

void pop_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last
	)

Definition at line 138 of file _heap.c.

                                      {
  __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
}

Referenced by HeapTest::mkheap0(), HeapTest::mkheap1(), priority_queue< _Tp, _Sequence, _Compare >::pop(), and sort_heap().

pop_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >

void pop_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last,
		_Compare	__comp
	)

Definition at line 181 of file _heap.c.

{
    __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
}

push_heap() [1/2]

template<class _RandomAccessIterator >

void push_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last
	)

Definition at line 65 of file _heap.c.

{
  __push_heap_aux(__first, __last,
                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
}

Referenced by HeapTest::pheap1(), HeapTest::pheap2(), and priority_queue< _Tp, _Sequence, _Compare >::push().

push_heap() [2/2]

template<class _RandomAccessIterator , class _Compare >

void push_heap	(	_RandomAccessIterator	__first,
		_RandomAccessIterator	__last,
		_Compare	__comp
	)

Definition at line 102 of file _heap.c.

{
  __push_heap_aux(__first, __last, __comp,
                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
}