Class IndexPriorityQueue

This is a min-heap priority queue class that does not use an object for each queue node. Integer IDs must be provided by the user to identify unique nodes. Internally an array is used to keep track of the mapping from ids to internal indices, so the max ID must also be provided.

See DijkstraGraphDistance for example usage.

conceptually based on https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp

Inheritance
Object
IndexPriorityQueue
Inherited Members
Namespace: g3
Assembly: cs.temp.dll.dll
Syntax
public class IndexPriorityQueue : IEnumerable<int>, IEnumerable

Constructors

IndexPriorityQueue(Int32)

maxIndex parameter is required because internally a fixed-size array is used to track mapping from IDs to internal node indices. If this seems problematic because you won't be inserting the full index space, consider a DynamicPriorityQueue instead.

Declaration
public IndexPriorityQueue(int maxID)
Parameters
Type Name Description
Int32 maxID

Fields

EnableDebugChecks

Declaration
public bool EnableDebugChecks
Field Value
Type Description
Boolean

Properties

Count

Declaration
public int Count { get; }
Property Value
Type Description
Int32

First

id of node at head of queue

Declaration
public int First { get; }
Property Value
Type Description
Int32

FirstPriority

Priority of node at head of queue

Declaration
public float FirstPriority { get; }
Property Value
Type Description
Single

Methods

Clear(Boolean)

reset the queue to empty state. if bFreeMemory is false, we don't discard internal data structures, so there will be less allocation next time (this does not make a huge difference...)

Declaration
public void Clear(bool bFreeMemory = true)
Parameters
Type Name Description
Boolean bFreeMemory

Contains(Int32)

constant-time check to see if id is already in queue

Declaration
public bool Contains(int id)
Parameters
Type Name Description
Int32 id
Returns
Type Description
Boolean

DebugPrint()

Declaration
public void DebugPrint()

Dequeue()

remove node at head of queue, update queue, and return id for that node

Declaration
public int Dequeue()
Returns
Type Description
Int32

Enqueue(Int32, Single)

Declaration
public void Enqueue(int id, float priority)
Parameters
Type Name Description
Int32 id
Single priority

GetEnumerator()

Declaration
public IEnumerator<int> GetEnumerator()
Returns
Type Description
IEnumerator<Int32>

GetPriority(Int32)

Query the priority at node id, assuming it exists in queue

Declaration
public float GetPriority(int id)
Parameters
Type Name Description
Int32 id
Returns
Type Description
Single

Insert(Int32, Single)

Add id to list w/ given priority Behavior is undefined if you call w/ same id twice

Declaration
public void Insert(int id, float priority)
Parameters
Type Name Description
Int32 id
Single priority

IsValidQueue()

Check if queue has been corrupted

Declaration
public bool IsValidQueue()
Returns
Type Description
Boolean

Remove(Int32)

remove this node from queue. Undefined behavior if called w/ same id twice! Behavior is undefined if you call w/ id that is not in queue

Declaration
public void Remove(int id)
Parameters
Type Name Description
Int32 id

Update(Int32, Single)

update priority at node id, and then move it to correct position in queue Behavior is undefined if you call w/ id that is not in queue

Declaration
public void Update(int id, float priority)
Parameters
Type Name Description
Int32 id
Single priority

Implements