Main Page   Class Hierarchy   Alphabetical List   Compound List   Compound Members   Related Pages  

vtkPriorityQueue Class Reference

an list of ids arranged in priority order. More...

#include <vtkPriorityQueue.h>

Inheritance diagram for vtkPriorityQueue:

Inheritance graph
[legend]
Collaboration diagram for vtkPriorityQueue:

Collaboration graph
[legend]
List of all members.

Public Methods

virtual const char * GetClassName ()
virtual int IsA (const char *type)
void PrintSelf (ostream &os, vtkIndent indent)
void Allocate (const int sz, const int ext=1000)
void Insert (float priority, int id)
int Pop (float &priority, int location=0)
int Pop (int location=0)
int Peek (float &priority, int location=0)
int Peek (int location=0)
float DeleteId (int id)
float GetPriority (int id)
int GetNumberOfItems ()
void Reset ()

Static Public Methods

vtkPriorityQueue * New ()
int IsTypeOf (const char *type)
vtkPriorityQueue * SafeDownCast (vtkObject *o)

Protected Methods

 vtkPriorityQueue ()
 ~vtkPriorityQueue ()
 vtkPriorityQueue (const vtkPriorityQueue &)
void operator= (const vtkPriorityQueue &)
vtkPriorityItem * Resize (const int sz)

Protected Attributes

vtkIntArrayItemLocation
vtkPriorityItem * Array
int Size
int MaxId
int Extend

Detailed Description

an list of ids arranged in priority order.

Date:
2000/12/10 20:08:16
Revision:
1.25

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.


Member Function Documentation

void vtkPriorityQueue::Allocate const int    sz,
const int    ext = 1000
 

Allocate initial space for priority queue.

float vtkPriorityQueue::DeleteId int    id [inline]
 

Delete entry in queue with specified id. Returns priority value associated with that id; or VTK_LARGE_FLOAT if not in queue.

virtual const char* vtkPriorityQueue::GetClassName   [virtual]
 

Return the class name as a string. This method is defined in all subclasses of vtkObject with the vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkObject.

int vtkPriorityQueue::GetNumberOfItems   [inline]
 

Return the number of items in this queue.

float vtkPriorityQueue::GetPriority int    id [inline]
 

Get the priority of an entry in the queue with specified id. Returns priority value of that id or VTK_LARGE_FLOAT if not in queue.

void vtkPriorityQueue::Insert float    priority,
int    id
 

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

virtual int vtkPriorityQueue::IsA const char *    type [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.

int vtkPriorityQueue::IsTypeOf const char *    type [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.

vtkPriorityQueue* vtkPriorityQueue::New   [static]
 

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

Reimplemented from vtkObject.

int vtkPriorityQueue::Peek int    location = 0 [inline]
 

Peek into the queue without actually removing anything. Returns the id.

int vtkPriorityQueue::Peek float &    priority,
int    location = 0
[inline]
 

Peek into the queue without actually removing anything. Returns the id and the priority.

int vtkPriorityQueue::Pop int    location = 0
 

Same as above but simplified for easier wrapping into interpreted languages.

int vtkPriorityQueue::Pop float &    priority,
int    location = 0
 

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.)

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::Reset  
 

Empty the queue but without releasing memory. This avoids the overhead of memory allocation/deletion.

vtkPriorityQueue* vtkPriorityQueue::SafeDownCast vtkObject   o [static]
 

Will cast the supplied object to vtkObject* is this is a safe operation (i.e., a safe downcast); otherwise NULL is returned. This method is defined in all subclasses of vtkObject with the vtkTypeMacro found in vtkSetGet.h.

Reimplemented from vtkObject.


The documentation for this class was generated from the following file:
Generated on Tue Mar 19 13:31:26 2002 for VTK by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002