class ArrayedQueue<T>

package polygonal.ds

implements Queue<T>

An arrayed queue based on an arrayed circular queue

A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end.

This is called a FIFO structure (First In, First Out).

Example:

var o = new polygonal.ds.ArrayedQueue<Int>(4);
for (i in 0...o.capacity) o.enqueue(i);
trace(o); //outputs:

[ ArrayedQueue size=4 capacity=4
  front
  0 -> 0
  1 -> 1
  2 -> 2
  3 -> 3
]

Constructor

@:value({ initialCapacity : 16 })new (initialCapacity:Int = 16, ?source:Array<T>, ?fixed:Bool)

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.

source

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

fixed

If true, growthRate is set to FIXED

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

inlineback ():T

Returns the rear element.

This is the "newest" element.

@: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 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.

contains (val:T):Bool

Returns true if this queue contains val.

inlinecopy (i:Int, j:Int):ArrayedQueue<T>

Replaces the element at index i with the element from index j.

The index is measured relative to the index of the front element (=0).

inlinedequeue ():T

Dequeues and returns the front element.

inlineenqueue (val:T):Void

Enqueues val.

inlineforEach (f:T ‑> Int ‑> T):ArrayedQueue<T>

Calls f on all elements.

The function signature is: f(input, index):output

  • input: current element
  • index: position relative to the front(=0) of the queue
  • output: element to be stored at given index

free ():Void

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

Improves GC efficiency/performance (optional).

inlineget (i:Int):T

Returns the element at index i.

The index is measured relative to the index of the front element (=0).

inlineisEmpty ():Bool

Returns true if this queue is empty.

inlineisFull ():Bool

Returns true if this queue is full.

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

Calls 'f` on all elements in order.

iterator ():Itr<T>

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

Preserves the natural order of a queue (First-In-First-Out).

See:

http://haxe.org/ref/iterators

pack ():ArrayedQueue<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 "oldest" element.

remove (val:T):Bool

Removes and nullifies all occurrences of val.

Returns:

true if at least one occurrence of val was removed.

reserve (n:Int):ArrayedQueue<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.

inlineset (i:Int, val:T):ArrayedQueue<T>

Replaces the element at index i with val.

The index is measured relative to the index of the front element (=0).

@:value({ rvals : null })shuffle (?rvals:Array<Float>):ArrayedQueue<T>

Shuffles the elements of this collection by using the Fisher-Yates algorithm.

Parameters:

rvals

a list of random double values in the interval [0, 1) defining the new positions of the elements. If omitted, random values are generated on-the-fly by calling Shuffle.frand().

inlineswap (i:Int, j:Int):ArrayedQueue<T>

Swaps the element at index i with the element at index j.

The index is measured relative to the index of the front element (=0).

toArray ():Array<T>

Returns an array containing all elements in this queue.

Preserves the natural order of this queue (First-In-First-Out).

toString ():String

Prints out all elements.

inlineunsafeEnqueue (val:T):ArrayedQueue<T>

Faster than this.enqueue() by skipping boundary checking.

The user is responsible for making sure that there is enough space available (e.g. by calling this.reserve()).