class LinkedDeque<T>

package polygonal.ds

implements Deque<T>

A deque is a "double-ended queue"

This is a linear list for which all insertions and deletions (and usually all accesses) are made at ends of the list.

Example:

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

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

Constructor

@:value({ reservedSize : 0 })new (reservedSize:Int = 0, ?source:Array<T>)

Parameters:

reservedSize

if > 0, this queue maintains an object pool of node objects. Prevents frequent node allocation and thus increases performance at the cost of using more memory.

Variables

@: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 last element of the deque.

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

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 deque contains val.

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

Calls f on all elements.

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

  • input: current element
  • index: position relative to the front(=0)
  • 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).

inlinefront ():T

Returns the first element of this deque.

getBack (i:Int):T

Returns the element at index i relative to the back of this deque.

The back element is at index [0], the front element is at index [this.size - 1].

getFront (i:Int):T

Returns the element at index i relative to the front of this deque.

The front element is at index [0], the back element is at index [this.size - 1].

indexOfBack (val:T):Int

Returns the index of the first occurrence of val or -1 if val does not exist.

The back element is at index [0], the front element is at index [this.size - 1].

indexOfFront (val:T):Int

Returns the index of the first occurrence of val or -1 if val does not exist.

The front element is at index [0], the back element is at index [this.size - 1].

inlineisEmpty ():Bool

Returns true only if this.size is 0.

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

Calls 'f` on all elements in order.

iterator ():Itr<T>

Returns a new LinkedDequeIterator object to iterate over all elements contained in this deque.

Preserves the natural order of a deque.

See:

http://haxe.org/ref/iterators

inlinepopBack ():T

Deletes the element at the end of the deque.

inlinepopFront ():T

Removes and returns the element at the beginning of this deque.

inlinepushBack (val:T):Void

Inserts val at the back of the deque.

inlinepushFront (val:T):Void

Inserts val at the front of this deque.

remove (val:T):Bool

Removes and nullifies all occurrences of val.

Returns:

true if at least one occurrence of val was removed.

toArray ():Array<T>

Returns an array containing all elements in this deque in the natural order.

toString ():String

Prints out all elements.