VTK
Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
vtkPriorityQueue Class Reference

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

#include <vtkPriorityQueue.h>

Inheritance diagram for vtkPriorityQueue:
[legend]
Collaboration diagram for vtkPriorityQueue:
[legend]

Classes

class  Item
 

Public Types

typedef vtkObject Superclass
 

Public Member Functions

virtual vtkTypeBool IsA (const char *type)
 Return 1 if this class is the same type of (or a subclass of) the named class. More...
 
vtkPriorityQueueNewInstance () const
 
void PrintSelf (ostream &os, vtkIndent indent) override
 Methods invoked by print to print information about the object including superclasses. More...
 
void Allocate (vtkIdType sz, vtkIdType ext=1000)
 Allocate initial space for priority queue. More...
 
void Insert (double priority, vtkIdType id)
 Insert id with priority specified. More...
 
vtkIdType Pop (vtkIdType location, double &priority)
 Removes item at specified location from tree; then reorders and balances tree. More...
 
vtkIdType Pop (vtkIdType location=0)
 Same as above but simplified for easier wrapping into interpreted languages. More...
 
vtkIdType Peek (vtkIdType location, double &priority)
 Peek into the queue without actually removing anything. More...
 
vtkIdType Peek (vtkIdType location=0)
 Peek into the queue without actually removing anything. More...
 
double DeleteId (vtkIdType id)
 Delete entry in queue with specified id. More...
 
double GetPriority (vtkIdType id)
 Get the priority of an entry in the queue with specified id. More...
 
vtkIdType GetNumberOfItems ()
 Return the number of items in this queue. More...
 
void Reset ()
 Empty the queue but without releasing memory. More...
 
- Public Member Functions inherited from vtkObject
 vtkBaseTypeMacro (vtkObject, vtkObjectBase)
 
virtual void DebugOn ()
 Turn debugging output on. More...
 
virtual void DebugOff ()
 Turn debugging output off. More...
 
bool GetDebug ()
 Get the value of the debug flag. More...
 
void SetDebug (bool debugFlag)
 Set the value of the debug flag. More...
 
virtual void Modified ()
 Update the modification time for this object. More...
 
virtual vtkMTimeType GetMTime ()
 Return this object's modified time. More...
 
unsigned long AddObserver (unsigned long event, vtkCommand *, float priority=0.0f)
 Allow people to add/remove/invoke observers (callbacks) to any VTK object. More...
 
unsigned long AddObserver (const char *event, vtkCommand *, float priority=0.0f)
 
vtkCommandGetCommand (unsigned long tag)
 
void RemoveObserver (vtkCommand *)
 
void RemoveObservers (unsigned long event, vtkCommand *)
 
void RemoveObservers (const char *event, vtkCommand *)
 
vtkTypeBool HasObserver (unsigned long event, vtkCommand *)
 
vtkTypeBool HasObserver (const char *event, vtkCommand *)
 
void RemoveObserver (unsigned long tag)
 
void RemoveObservers (unsigned long event)
 
void RemoveObservers (const char *event)
 
void RemoveAllObservers ()
 
vtkTypeBool HasObserver (unsigned long event)
 
vtkTypeBool HasObserver (const char *event)
 
template<class U , class T >
unsigned long AddObserver (unsigned long event, U observer, void(T::*callback)(), float priority=0.0f)
 Overloads to AddObserver that allow developers to add class member functions as callbacks for events. More...
 
template<class U , class T >
unsigned long AddObserver (unsigned long event, U observer, void(T::*callback)(vtkObject *, unsigned long, void *), float priority=0.0f)
 
template<class U , class T >
unsigned long AddObserver (unsigned long event, U observer, bool(T::*callback)(vtkObject *, unsigned long, void *), float priority=0.0f)
 Allow user to set the AbortFlagOn() with the return value of the callback method. More...
 
int InvokeEvent (unsigned long event, void *callData)
 This method invokes an event and return whether the event was aborted or not. More...
 
int InvokeEvent (const char *event, void *callData)
 
int InvokeEvent (unsigned long event)
 
int InvokeEvent (const char *event)
 
- Public Member Functions inherited from vtkObjectBase
const char * GetClassName () const
 Return the class name as a string. More...
 
virtual void Delete ()
 Delete a VTK object. More...
 
virtual void FastDelete ()
 Delete a reference to this object. More...
 
void InitializeObjectBase ()
 
void Print (ostream &os)
 Print an object to an ostream. More...
 
virtual void PrintHeader (ostream &os, vtkIndent indent)
 
virtual void PrintTrailer (ostream &os, vtkIndent indent)
 
virtual void Register (vtkObjectBase *o)
 Increase the reference count (mark as used by another object). More...
 
virtual void UnRegister (vtkObjectBase *o)
 Decrease the reference count (release by another object). More...
 
int GetReferenceCount ()
 Return the current reference count of this object. More...
 
void SetReferenceCount (int)
 Sets the reference count. More...
 
void PrintRevisions (ostream &)
 Legacy. More...
 

Static Public Member Functions

static vtkPriorityQueueNew ()
 Instantiate priority queue with default size and extension size of 1000. More...
 
static vtkTypeBool IsTypeOf (const char *type)
 
static vtkPriorityQueueSafeDownCast (vtkObjectBase *o)
 
- Static Public Member Functions inherited from vtkObject
static vtkObjectNew ()
 Create an object with Debug turned off, modified time initialized to zero, and reference counting on. More...
 
static void BreakOnError ()
 This method is called when vtkErrorMacro executes. More...
 
static void SetGlobalWarningDisplay (int val)
 This is a global flag that controls whether any debug, warning or error messages are displayed. More...
 
static void GlobalWarningDisplayOn ()
 
static void GlobalWarningDisplayOff ()
 
static int GetGlobalWarningDisplay ()
 
- Static Public Member Functions inherited from vtkObjectBase
static vtkTypeBool IsTypeOf (const char *name)
 Return 1 if this class type is the same type of (or a subclass of) the named class. More...
 
static vtkObjectBaseNew ()
 Create an object with Debug turned off, modified time initialized to zero, and reference counting on. More...
 

Protected Member Functions

virtual vtkObjectBaseNewInstanceInternal () const
 
 vtkPriorityQueue ()
 
 ~vtkPriorityQueue () override
 
ItemResize (const vtkIdType sz)
 
- Protected Member Functions inherited from vtkObject
 vtkObject ()
 
 ~vtkObject () override
 
void RegisterInternal (vtkObjectBase *, vtkTypeBool check) override
 
void UnRegisterInternal (vtkObjectBase *, vtkTypeBool check) override
 
void InternalGrabFocus (vtkCommand *mouseEvents, vtkCommand *keypressEvents=nullptr)
 These methods allow a command to exclusively grab all events. More...
 
void InternalReleaseFocus ()
 
- Protected Member Functions inherited from vtkObjectBase
 vtkObjectBase ()
 
virtual ~vtkObjectBase ()
 
virtual void CollectRevisions (ostream &)
 
virtual void ReportReferences (vtkGarbageCollector *)
 
 vtkObjectBase (const vtkObjectBase &)
 
void operator= (const vtkObjectBase &)
 

Protected Attributes

vtkIdTypeArrayItemLocation
 
ItemArray
 
vtkIdType Size
 
vtkIdType MaxId
 
vtkIdType Extend
 
- Protected Attributes inherited from vtkObject
bool Debug
 
vtkTimeStamp MTime
 
vtkSubjectHelper * SubjectHelper
 
- Protected Attributes inherited from vtkObjectBase
std::atomic< int32_t > ReferenceCount
 
vtkWeakPointerBase ** WeakPointers
 

Detailed Description

a 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 46 of file vtkPriorityQueue.h.

Member Typedef Documentation

◆ Superclass

Definition at line 61 of file vtkPriorityQueue.h.

Constructor & Destructor Documentation

◆ vtkPriorityQueue()

vtkPriorityQueue::vtkPriorityQueue ( )
protected

◆ ~vtkPriorityQueue()

vtkPriorityQueue::~vtkPriorityQueue ( )
overrideprotected

Member Function Documentation

◆ New()

static vtkPriorityQueue* vtkPriorityQueue::New ( )
static

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

◆ IsTypeOf()

static vtkTypeBool vtkPriorityQueue::IsTypeOf ( const char *  type)
static

◆ IsA()

virtual vtkTypeBool 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 vtkObjectBase.

◆ SafeDownCast()

static vtkPriorityQueue* vtkPriorityQueue::SafeDownCast ( vtkObjectBase o)
static

◆ NewInstanceInternal()

virtual vtkObjectBase* vtkPriorityQueue::NewInstanceInternal ( ) const
protectedvirtual

◆ NewInstance()

vtkPriorityQueue* vtkPriorityQueue::NewInstance ( ) const

◆ PrintSelf()

void vtkPriorityQueue::PrintSelf ( ostream &  os,
vtkIndent  indent 
)
overridevirtual

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

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

Allocate initial space for priority queue.

◆ Insert()

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.

◆ Pop() [1/2]

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

◆ Pop() [2/2]

vtkIdType vtkPriorityQueue::Pop ( vtkIdType  location = 0)

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

◆ Peek() [1/2]

vtkIdType vtkPriorityQueue::Peek ( vtkIdType  location,
double &  priority 
)
inline

Peek into the queue without actually removing anything.

Returns the id and the priority.

Definition at line 164 of file vtkPriorityQueue.h.

◆ Peek() [2/2]

vtkIdType vtkPriorityQueue::Peek ( vtkIdType  location = 0)
inline

Peek into the queue without actually removing anything.

Returns the id.

Definition at line 177 of file vtkPriorityQueue.h.

◆ DeleteId()

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 141 of file vtkPriorityQueue.h.

◆ GetPriority()

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 153 of file vtkPriorityQueue.h.

◆ GetNumberOfItems()

vtkIdType vtkPriorityQueue::GetNumberOfItems ( )
inline

Return the number of items in this queue.

Definition at line 116 of file vtkPriorityQueue.h.

◆ Reset()

void vtkPriorityQueue::Reset ( )

Empty the queue but without releasing memory.

This avoids the overhead of memory allocation/deletion.

◆ Resize()

Item* vtkPriorityQueue::Resize ( const vtkIdType  sz)
protected

Member Data Documentation

◆ ItemLocation

vtkIdTypeArray* vtkPriorityQueue::ItemLocation
protected

Definition at line 130 of file vtkPriorityQueue.h.

◆ Array

Item* vtkPriorityQueue::Array
protected

Definition at line 131 of file vtkPriorityQueue.h.

◆ Size

vtkIdType vtkPriorityQueue::Size
protected

Definition at line 132 of file vtkPriorityQueue.h.

◆ MaxId

vtkIdType vtkPriorityQueue::MaxId
protected

Definition at line 133 of file vtkPriorityQueue.h.

◆ Extend

vtkIdType vtkPriorityQueue::Extend
protected

Definition at line 134 of file vtkPriorityQueue.h.


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