Main Page | Directories | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages

vtkPriorityQueue Class Reference

#include <vtkPriorityQueue.h>

Inheritance diagram for vtkPriorityQueue:

Inheritance graph
[legend]
Collaboration diagram for vtkPriorityQueue:

Collaboration graph
[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.
Created by:
  • Schroeder, Will
CVS contributions (if > 5%):
  • Schroeder, Will (51%)
  • Martin, Ken (10%)
  • Miller, Jim (8%)
  • Law, Charles (6%)
  • Henderson, Amy (5%)
CVS logs (CVSweb):
  • .h (/Common/vtkPriorityQueue.h)
  • .cxx (/Common/vtkPriorityQueue.cxx)

Definition at line 58 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

vtkPriorityQueueNew ()
int IsTypeOf (const char *type)
vtkPriorityQueueSafeDownCast (vtkObject *o)

Protected Member Functions

 vtkPriorityQueue ()
 ~vtkPriorityQueue ()
ItemResize (const vtkIdType sz)

Protected Attributes

vtkIdTypeArrayItemLocation
ItemArray
vtkIdType Size
vtkIdType MaxId
vtkIdType Extend


Member Typedef Documentation

typedef vtkObject vtkPriorityQueue::Superclass
 

Reimplemented from vtkObject.

Definition at line 74 of file vtkPriorityQueue.h.


Constructor & Destructor Documentation

vtkPriorityQueue::vtkPriorityQueue  )  [protected]
 

vtkPriorityQueue::~vtkPriorityQueue  )  [protected]
 


Member Function Documentation

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.

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 vtkTypeRevisionMacro found in vtkSetGet.h.

Reimplemented from vtkObject.

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 vtkTypeRevisionMacro found in vtkSetGet.h.

Reimplemented from vtkObject.

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

Referenced by DeleteId().

vtkIdType vtkPriorityQueue::Pop vtkIdType  location = 0  ) 
 

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

vtkIdType vtkPriorityQueue::Peek vtkIdType  location,
double &  priority
[inline]
 

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

Definition at line 160 of file vtkPriorityQueue.h.

References Array, MaxId, vtkPriorityQueue::Item::priority, and vtkIdType.

vtkIdType vtkPriorityQueue::Peek vtkIdType  location = 0  )  [inline]
 

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

Definition at line 173 of file vtkPriorityQueue.h.

References Array, vtkPriorityQueue::Item::id, MaxId, and vtkIdType.

double vtkPriorityQueue::DeleteId vtkIdType  id  )  [inline]
 

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

Definition at line 135 of file vtkPriorityQueue.h.

References vtkDataArray::GetMaxId(), vtkIdTypeArray::GetValue(), ItemLocation, Pop(), and vtkIdType.

double vtkPriorityQueue::GetPriority vtkIdType  id  )  [inline]
 

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

Definition at line 148 of file vtkPriorityQueue.h.

References Array, vtkDataArray::GetMaxId(), vtkIdTypeArray::GetValue(), ItemLocation, vtkPriorityQueue::Item::priority, and vtkIdType.

vtkIdType vtkPriorityQueue::GetNumberOfItems  )  [inline]
 

Return the number of items in this queue.

Definition at line 113 of file vtkPriorityQueue.h.

References vtkIdType.

void vtkPriorityQueue::Reset  ) 
 

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

Item* vtkPriorityQueue::Resize const vtkIdType  sz  )  [protected]
 


Member Data Documentation

vtkIdTypeArray* vtkPriorityQueue::ItemLocation [protected]
 

Definition at line 125 of file vtkPriorityQueue.h.

Referenced by DeleteId(), and GetPriority().

Item* vtkPriorityQueue::Array [protected]
 

Definition at line 126 of file vtkPriorityQueue.h.

Referenced by GetPriority(), and Peek().

vtkIdType vtkPriorityQueue::Size [protected]
 

Definition at line 127 of file vtkPriorityQueue.h.

vtkIdType vtkPriorityQueue::MaxId [protected]
 

Definition at line 128 of file vtkPriorityQueue.h.

Referenced by Peek().

vtkIdType vtkPriorityQueue::Extend [protected]
 

Definition at line 129 of file vtkPriorityQueue.h.


The documentation for this class was generated from the following file: