---

PriorityQueue Class Reference

A heap based minimum priority queue. Used in the A* implementation. More...

#include <priorityqueue.h>

Public Member Functions
	PriorityQueue ()
	PriorityQueue (SEARCH_TYPE)
bool	Add (GENERIC_NODE elem, Priority priority)
bool	PopLowest (GENERIC_NODE &elem)
Priority &	TopKey (void)
	Returns the the smallest priority of all vertices in priority queue.
bool	empty (void)
	Return whether queue is empty.
int	size (void)
void	Clear (void)
void	Update (GENERIC_NODE elem, Priority p)
	void Update(GENERIC_NODE elem, Priority p, bool (*cmp)(GENERIC_NODE,GENERIC_NODE));
GENERIC_NODE	Element (unsigned int i)
bool	Remove (GENERIC_NODE elem)
	bool Remove(GENERIC_NODE elem, bool (*cmp)(GENERIC_NODE,GENERIC_NODE));
bool	Search (GENERIC_NODE src, Priority &p)
void	Dump ()
	bool Search(GENERIC_NODE src, Priority& p, bool (*cmp)(GENERIC_NODE,GENERIC_NODE));
bool	HeapDecreasePriority (unsigned int i)
bool	HeapIncreasePriority (unsigned int i)
void	Copy (PriorityQueue &p)
Static Public Attributes
Priority	MINPRIORITY
Private Member Functions
bool	Exchange (unsigned int a, unsigned int b)
unsigned int	Left (unsigned int i)
unsigned int	Right (unsigned int i)
unsigned int	Parent (unsigned int i)
void	MinHeapify (unsigned int i)
Private Attributes
unsigned int	m_ElemCount
Priority	m_Priority [MAXDEPTH]
GENERIC_NODE	Gm_Elems [MAXDEPTH]

---

Detailed Description

A heap based minimum priority queue. Used in the A* implementation.

PriorityQueue Class. This is a heap-based minimum priority queue. The number of elements the queue can store is kept in the MAXDEPTH constant in the header file. The details of how the queue works can be found in Introduction to Algorithms, by CLRS.

---

Constructor & Destructor Documentation

PriorityQueue (   )

PriorityQueue (  SEARCH_TYPE   )

---

Member Function Documentation

bool Add (  GENERIC_NODE  elem, Priority  priority )

Adds a new element to the priority queue and resorts the queue. Will return failure if the queue is full. Parameters: elem  The element to be added. priority  The priority of the element to be added. Returns: Whether the element was successfully added.

void Clear (  void   )

void Copy (  PriorityQueue &  p  )

void Dump (   )

bool Search(GENERIC_NODE src, Priority& p, bool (*cmp)(GENERIC_NODE,GENERIC_NODE)); Dumps the queue data to STDOUT.

GENERIC_NODE Element (  unsigned int  i  )

bool empty (  void   )

Return whether queue is empty.

bool Exchange (  unsigned int  a, unsigned int  b )  [private]

Exchanges the two elements at the given locations. Does NOT resort the queue. Parameters: a  The element to exchange. b  The element to exchange. Returns: Whether it was successful.

bool HeapDecreasePriority (  unsigned int  i  )

Resorts the queue at the element argument, assumes that the priority of the element has its priority reduced. NOTE: Requires the priority to be reduced prior to the call. Parameters: i  The element with reduced priority. Returns: Whether it was successful.

bool HeapIncreasePriority (  unsigned int  i  )

unsigned int Left (  unsigned int  i  )  [private]

void MinHeapify (  unsigned int  i  )  [private]

unsigned int Parent (  unsigned int  i  )  [private]

bool PopLowest (  GENERIC_NODE &  elem  )

Pops the element with the lowest priority from the queue. The element is removed and the queue is resorted. Will return failure if the queue is empty. Parameters: elem  The variable to hold the popped result. Returns: Whether the element was successfully popped.

bool Remove (  GENERIC_NODE  elem  )

bool Remove(GENERIC_NODE elem, bool (*cmp)(GENERIC_NODE,GENERIC_NODE)); Removes an element from the queue using the passed comparison function and resorts the queue. Will return failure if no matching element is found. Parameters: elem  The element to remove. cmp  The comparason function to use. Returns: Whether the element was successfully removed.

unsigned int Right (  unsigned int  i  )  [private]

bool Search (  GENERIC_NODE  src, Priority &  p )

Searches for an element in the queue and returns whether the element is found. The queue is unmodified. Parameters: src  The element to find. cmp  The comparason function to use. Returns: Whether the element was found.

int size (  void   )

Priority& TopKey (  void   )

Returns the the smallest priority of all vertices in priority queue.

void Update (  GENERIC_NODE  elem, Priority  p )

void Update(GENERIC_NODE elem, Priority p, bool (*cmp)(GENERIC_NODE,GENERIC_NODE));

---

Field Documentation

GENERIC_NODE Gm_Elems[MAXDEPTH] [private]

The array of elements. Shares the same indices of the priority array. It has a flattened tree structure.

unsigned int m_ElemCount [private]

The number of elements in the queue. Initially initialized to 0.

Priority m_Priority[MAXDEPTH] [private]

The array of element priorities. Shares the same indices of the element array. It has a flattened tree structure.

Priority MINPRIORITY [static]

Constructor. Initializes the class instance.

---