class PriorityQueue<T>

package polygonal.ds

implements Queue<T>

@:allow(polygonal.ds.Heap)

A priority queue is heap but with a simplified API for managing prioritized data

Adds additional methods for removing and re-prioritizing elements.

Example:

class Element implements polygonal.ds.Prioritizable {
    public var priority:Int;
    public var position:Int;
    public function new(priority:Int) {
        this.priority = priority;
    }
    public function toString():String {
        return "Element" + priority;
    }
}

...

var o = new polygonal.ds.PriorityQueue<Element>(4);
o.enqueue(new Element(3));
o.enqueue(new Element(0));
o.enqueue(new Element(5));
trace(o); //outputs:

[ PriorityQueue size=3
  front
  0 -> Element5
  1 -> Element3
  2 -> Element0
]

Constructor

@:value({ inverse : false, initalCapacity : 1 })new (initalCapacity:Int = 1, inverse:Bool = false, ?source:Array<T>)

Parameters:

initialCapacity

the initial physical space for storing values. Useful before inserting a large number of elements as this reduces the amount of incremental reallocation.

inverse

if true, the lower the number, the higher the priority. By default a higher number means a higher priority.

source

copies all values from source in the range [0, source.length - 1] to this collection.

Variables

read onlycapacity:Int

The size of the allocated storage space for the elements. If more space is required to accommodate new elements, capacity grows according to this.growthRate. The capacity never falls below the initial size defined in the constructor and is usually a bit larger than this.size (mild overallocation).

@:value(GrowthRate.NORMAL)growthRate:Int = GrowthRate.NORMAL

The growth rate of the container.

See:

GrowthRate

@:value(HashKey.next())read onlykey:Int = HashKey.next()

A unique identifier for this object.

A hash table transforms this key into an index of an array element by using a hash function.

@:value(false)reuseIterator:Bool = false

If true, reuses the iterator object instead of allocating a new one when calling this.iterator().

The default is false.

If this value is true, nested iterations will fail as only one iteration is allowed at a time.

read onlysize:Int

The total number of elements.

Methods

back ():T

Returns the rear element.

This is the element with the lowest priority.

@:value({ gc : false })clear (gc:Bool = false):Void

Removes all elements.

Parameters:

gc

if true, elements are nullified upon removal so the garbage collector can reclaim used memory.

@:value({ copier : null, byRef : true })clone (byRef:Bool = true, ?copier:T ‑> T):Collection<T>

Creates and returns a shallow copy (structure only - default) or deep copy (structure & elements) of this priority queue.

If byRef is true, primitive elements are copied by value whereas objects are copied by reference.

If byRef is false, the copier function is used for copying elements. If omitted, clone() is called on each element assuming all elements implement Cloneable.

inlinecontains (val:T):Bool

Returns true if this priority queue contains val.

dequeue ():T

Dequeues the front element.

enqueue (val:T):Void

Enqueues val.

free ():Void

Destroys this object by explicitly nullifying all elements for GC'ing used resources.

Improves GC efficiency/performance (optional).

inlineisEmpty ():Bool

Returns true only if this.size is 0.

inlineiter (f:T ‑> Void):PriorityQueue<T>

Calls 'f` on all elements in unsorted order.

iterator ():Itr<T>

Returns a new PriorityQueueIterator object to iterate over all elements contained in this priority queue.

The values are visited in an unsorted order.

See:

http://haxe.org/ref/iterators

pack ():PriorityQueue<T>

Reduces the capacity of the internal container to the initial capacity.

May cause a reallocation, but has no effect on this.size and its elements. An application can use this operation to free up memory by unlocking resources for the garbage collector.

inlinepeek ():T

Returns the front element.

This is the element with the highest priority.

remove (val:T):Bool

Removes val.

Returns:

true if val was removed.

reprioritize (val:T, priority:Float):PriorityQueue<T>

Re-prioritizes val.

Parameters:

priority

the new priority.

reserve (n:Int):PriorityQueue<T>

Preallocates storage for n elements.

May cause a reallocation, but has no effect on this.size and its elements. Useful before inserting a large number of elements as this reduces the amount of incremental reallocation.

sort ():Array<T>

Returns a sorted array of all elements.

toArray ():Array<T>

Returns an unordered array containing all elements in this priority queue.

toString ():String

Prints out all elements.