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

Static Public Member Functions

static vtkPriorityQueueNew ()
 Instantiate priority queue with default size and extension size of 1000.
 
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.
 
static void BreakOnError ()
 This method is called when vtkErrorMacro executes.
 
static void SetGlobalWarningDisplay (int val)
 This is a global flag that controls whether any debug, warning or error messages are displayed.
 
static void GlobalWarningDisplayOn ()
 This is a global flag that controls whether any debug, warning or error messages are displayed.
 
static void GlobalWarningDisplayOff ()
 This is a global flag that controls whether any debug, warning or error messages are displayed.
 
static int GetGlobalWarningDisplay ()
 This is a global flag that controls whether any debug, warning or error messages are displayed.
 
- 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.
 
static vtkIdType GetNumberOfGenerationsFromBaseType (const char *name)
 Given a the name of a base class of this class type, return the distance of inheritance between this class type and the named class (how many generations of inheritance are there between this class and the named class).
 
static vtkObjectBaseNew ()
 Create an object with Debug turned off, modified time initialized to zero, and reference counting on.
 
static void SetMemkindDirectory (const char *directoryname)
 The name of a directory, ideally mounted -o dax, to memory map an extended memory space within.
 
static bool GetUsingMemkind ()
 A global state flag that controls whether vtkObjects are constructed in the usual way (the default) or within the extended memory space.
 

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.
 
void InternalReleaseFocus ()
 These methods allow a command to exclusively grab all events.
 
- Protected Member Functions inherited from vtkObjectBase
 vtkObjectBase ()
 
virtual ~vtkObjectBase ()
 
virtual void RegisterInternal (vtkObjectBase *, vtkTypeBool check)
 
virtual void UnRegisterInternal (vtkObjectBase *, vtkTypeBool check)
 
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
 

Additional Inherited Members

- Static Protected Member Functions inherited from vtkObjectBase
static vtkMallocingFunction GetCurrentMallocFunction ()
 
static vtkReallocingFunction GetCurrentReallocFunction ()
 
static vtkFreeingFunction GetCurrentFreeFunction ()
 
static vtkFreeingFunction GetAlternateFreeFunction ()
 

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: