#include <DetourNode.h>

Public Member Functions
	dtNodeQueue (int n)

	~dtNodeQueue ()

void	operator= (dtNodeQueue &)

void	clear ()

dtNode *	top ()

dtNode *	pop ()

void	push (dtNode *node)

void	modify (dtNode *node)

bool	empty () const

int	getMemUsed () const

int	getCapacity () const

Private Member Functions
void	bubbleUp (int i, dtNode *node)

void	trickleDown (int i, dtNode *node)

Private Attributes
dtNode **	m_heap

const int	m_capacity

int	m_size

Constructor & Destructor Documentation

dtNodeQueue::dtNodeQueue ( int n )

  :
  m_heap(0),
  m_capacity(n),
  m_size(0)
 {
  dtAssert(m_capacity > 0);
  
  m_heap = (dtNode**)dtAlloc(sizeof(dtNode*)*(m_capacity+1), DT_ALLOC_PERM);
  dtAssert(m_heap);
 }

Here is the call graph for this function:

dtNodeQueue::~dtNodeQueue ( )

 {
  dtFree(m_heap);
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

void dtNodeQueue::bubbleUp	(	int	i,
		dtNode *	node
	)

private

 {
  int parent = (i-1)/2;
  // note: (index > 0) means there is a parent
  while ((i > 0) && (m_heap[parent]->total > node->total))
  {
  m_heap[i] = m_heap[parent];
  i = parent;
  parent = (i-1)/2;
  }
  m_heap[i] = node;
 }

Here is the caller graph for this function:

void dtNodeQueue::clear ( )

inline

  {
  m_size = 0;
  }

Here is the caller graph for this function:

bool dtNodeQueue::empty ( ) const

inline

150 { return m_size == 0; }

dtNodeQueue::m_size

int m_size

Definition: DetourNode.h:166

Here is the caller graph for this function:

int dtNodeQueue::getCapacity ( ) const

inline

158 { return m_capacity; }

dtNodeQueue::m_capacity

const int m_capacity

Definition: DetourNode.h:165

Here is the caller graph for this function:

int dtNodeQueue::getMemUsed ( ) const

inline

  {
  return sizeof(*this) +
  sizeof(dtNode*)*(m_capacity+1);
  }

void dtNodeQueue::modify ( dtNode * node )

inline

  {
  for (int i = 0; i < m_size; ++i)
  {
  if (m_heap[i] == node)
  {
  bubbleUp(i, node);
  return;
  }
  }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void dtNodeQueue::operator= ( dtNodeQueue & )

inline

112 {}

dtNode* dtNodeQueue::pop ( )

inline

  {
  dtNode* result = m_heap[0];
  m_size--;
  trickleDown(0, m_heap[m_size]);
  return result;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

void dtNodeQueue::push ( dtNode * node )

inline

  {
  m_size++;
  bubbleUp(m_size-1, node);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

dtNode* dtNodeQueue::top ( )

inline

  {
  return m_heap[0];
  }

void dtNodeQueue::trickleDown	(	int	i,
		dtNode *	node
	)

private

 {
  int child = (i*2)+1;
  while (child < m_size)
  {
  if (((child+1) < m_size) && 
  (m_heap[child]->total > m_heap[child+1]->total))
  {
  child++;
  }
  m_heap[i] = m_heap[child];
  i = child;
  child = (i*2)+1;
  }
  bubbleUp(i, node);
 }