vtkPriorityQueue Class Reference

#include <vtkPriorityQueue.h>

Inheritance diagram for vtkPriorityQueue:

[legend]

Collaboration diagram for vtkPriorityQueue:

[legend]

List of all members.

Detailed Description

an list of ids arranged in priority order

vtkPriorityQueue is a general object for creating and manipulating lists of object ids (e.g., point or cell ids). Object ids are sorted according to a user-specified priority, where entries at the top of the queue have the smallest values.

This implementation provides a feature beyond the usual ability to insert and retrieve (or pop) values from the queue. It is also possible to pop any item in the queue given its id number. This allows you to delete entries in the queue which can useful for reinserting an item into the queue.

Warning:: This implementation is a variation of the priority queue described in "Data Structures & Algorithms" by Aho, Hopcroft, Ullman. It creates a balanced, partially ordered binary tree implemented as an ordered array. This avoids the overhead associated with parent/child pointers, and frequent memory allocation and deallocation.

Definition at line 44 of file vtkPriorityQueue.h.


Public Types
typedef vtkObject	Superclass
Public Member Functions
virtual const char *	GetClassName ()
virtual int	IsA (const char *type)
void	PrintSelf (ostream &os, vtkIndent indent)
void	Allocate (const vtkIdType sz, const vtkIdType ext=1000)
void	Insert (double priority, vtkIdType id)
vtkIdType	Pop (vtkIdType location, double &priority)
vtkIdType	Pop (vtkIdType location=0)
vtkIdType	Peek (vtkIdType location, double &priority)
vtkIdType	Peek (vtkIdType location=0)
double	DeleteId (vtkIdType id)
double	GetPriority (vtkIdType id)
vtkIdType	GetNumberOfItems ()
void	Reset ()
Static Public Member Functions
static vtkPriorityQueue *	New ()
static int	IsTypeOf (const char *type)
static vtkPriorityQueue *	SafeDownCast (vtkObject *o)
Protected Member Functions
	vtkPriorityQueue ()
	~vtkPriorityQueue ()
Item *	Resize (const vtkIdType sz)
Protected Attributes
vtkIdTypeArray *	ItemLocation
Item *	Array
vtkIdType	Size
vtkIdType	MaxId
vtkIdType	Extend
Classes
class	Item

Member Typedef Documentation

typedef vtkObject vtkPriorityQueue::Superclass

Reimplemented from vtkObject.

Definition at line 60 of file vtkPriorityQueue.h.

Constructor & Destructor Documentation

vtkPriorityQueue::vtkPriorityQueue ( ) [protected]

vtkPriorityQueue::~vtkPriorityQueue ( ) [protected]

Member Function Documentation

static vtkPriorityQueue* vtkPriorityQueue::New ( ) [static]

Instantiate priority queue with default size and extension size of 1000.

Reimplemented from vtkObject.

virtual const char* vtkPriorityQueue::GetClassName ( ) [virtual]

Reimplemented from vtkObject.

static int vtkPriorityQueue::IsTypeOf ( const char * name ) [static]

Return 1 if this class type is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkObject.

virtual int vtkPriorityQueue::IsA ( const char * name ) [virtual]

Return 1 if this class is the same type of (or a subclass of) the named class. Returns 0 otherwise. This method works in combination with vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkObject.

static vtkPriorityQueue* vtkPriorityQueue::SafeDownCast ( vtkObject * o ) [static]

Reimplemented from vtkObject.

void vtkPriorityQueue::PrintSelf	(	ostream &	os,
		vtkIndent	indent
	)			`[virtual]`

Methods invoked by print to print information about the object including superclasses. Typically not called by the user (use Print() instead) but used in the hierarchical print process to combine the output of several classes.

Reimplemented from vtkObject.

void vtkPriorityQueue::Allocate	(	const vtkIdType	sz,
		const vtkIdType	ext = `1000`
	)

Allocate initial space for priority queue.

void vtkPriorityQueue::Insert	(	double	priority,
		vtkIdType	id
	)

Insert id with priority specified. The id is generally an index like a point id or cell id.

vtkIdType vtkPriorityQueue::Pop	(	vtkIdType	location,
		double &	priority
	)

Removes item at specified location from tree; then reorders and balances tree. The location == 0 is the root of the tree. If queue is exhausted, then a value < 0 is returned. (Note: the location is not the same as deleting an id; id is mapped to location.) BTX

vtkIdType vtkPriorityQueue::Pop ( vtkIdType location = 0 )