vtkPriorityQueue Class Reference
#include <vtkPriorityQueue.h>
Inheritance diagram for vtkPriorityQueue:
Detailed Description
an list of ids arranged in priority order
- Date:
- 2002/12/26 18:24:21
- Revision:
- 1.37
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 (53%)
- Miller, Jim (9%)
- Martin, Ken (7%)
- Henderson, Amy (6%)
- Law, Charles (5%)
- Barre, Sebastien (5%)
Definition at line 63 of file vtkPriorityQueue.h.
Public Types | |
| typedef vtkObject | Superclass |
Public Methods | |
| 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 (float priority, vtkIdType id) |
| vtkIdType | Pop (vtkIdType location, float &priority) |
| vtkIdType | Pop (vtkIdType location=0) |
| vtkIdType | Peek (vtkIdType location, float &priority) |
| vtkIdType | Peek (vtkIdType location=0) |
| float | DeleteId (vtkIdType id) |
| float | GetPriority (vtkIdType id) |
| vtkIdType | GetNumberOfItems () |
| void | Reset () |
Static Public Methods | |
| vtkPriorityQueue * | New () |
| int | IsTypeOf (const char *type) |
| vtkPriorityQueue * | SafeDownCast (vtkObject *o) |
Protected Methods | |
| vtkPriorityQueue () | |
| ~vtkPriorityQueue () | |
| Item * | Resize (const vtkIdType sz) |
Protected Attributes | |
| vtkIdTypeArray * | ItemLocation |
| Item * | Array |
| vtkIdType | Size |
| vtkIdType | MaxId |
| vtkIdType | Extend |
Member Typedef Documentation
|
|
Reimplemented from vtkObject. Definition at line 79 of file vtkPriorityQueue.h. |
Constructor & Destructor Documentation
|
|
|
|
|
|
Member Function Documentation
|
|
Instantiate priority queue with default size and extension size of 1000. Reimplemented from vtkObject. |
|
|
Reimplemented from vtkObject. |
|
|
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. |
|
|
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. |
|
|
Reimplemented from vtkObject. |
|
||||||||||||
|
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. |
|
||||||||||||
|
Allocate initial space for priority queue. |
|
||||||||||||
|
Insert id with priority specified. The id is generally an index like a point id or cell id. |
|
||||||||||||
|
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(). |
|
|
Same as above but simplified for easier wrapping into interpreted languages. |
|
||||||||||||
|
Peek into the queue without actually removing anything. Returns the id and the priority. BTX Definition at line 165 of file vtkPriorityQueue.h. References Array, vtkPriorityQueue::Item::id, MaxId, vtkPriorityQueue::Item::priority, and vtkIdType. |
|
|
Peek into the queue without actually removing anything. Returns the id. Definition at line 178 of file vtkPriorityQueue.h. References Array, vtkPriorityQueue::Item::id, MaxId, and vtkIdType. |
|
|
Delete entry in queue with specified id. Returns priority value associated with that id; or VTK_LARGE_FLOAT if not in queue. Definition at line 140 of file vtkPriorityQueue.h. References vtkDataArray::GetMaxId(), vtkIdTypeArray::GetValue(), id, ItemLocation, Pop(), VTK_LARGE_FLOAT, and vtkIdType. |
|
|
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. Definition at line 153 of file vtkPriorityQueue.h. References Array, vtkDataArray::GetMaxId(), vtkIdTypeArray::GetValue(), id, ItemLocation, vtkPriorityQueue::Item::priority, VTK_LARGE_FLOAT, and vtkIdType. |
|
|
Return the number of items in this queue. Definition at line 118 of file vtkPriorityQueue.h. References vtkIdType. |
|
|
Empty the queue but without releasing memory. This avoids the overhead of memory allocation/deletion. |
|
|
|
Member Data Documentation
|
|
Definition at line 130 of file vtkPriorityQueue.h. Referenced by DeleteId(), and GetPriority(). |
|
|
Definition at line 131 of file vtkPriorityQueue.h. Referenced by GetPriority(), and Peek(). |
|
|
Definition at line 132 of file vtkPriorityQueue.h. |
|
|
Definition at line 133 of file vtkPriorityQueue.h. Referenced by Peek(). |
|
|
Definition at line 134 of file vtkPriorityQueue.h. |
The documentation for this class was generated from the following file:
- Common/vtkPriorityQueue.h