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.ArrayedDeque<Int>();
for (i in 0...4) o.pushFront(i);
trace(o); //outputs:
[ ArrayedDeque size=4
front
0 -> 3
1 -> 2
2 -> 1
3 -> 0
]
Constructor
new (blockSize:Int = 64, blockPoolCapacity:Int = 4, ?source:Array<T>)
Parameters:
blockSize | a block represents a contiguous piece of memory; whenever the deque runs out of space an additional block with a capacity of |
---|---|
blockPoolCapacity | the total number of blocks to reuse when blocks are removed or relocated (from front to back or vice-versa). This improves performances but uses more memory. The default value is 4; a value of 0 disables block pooling. |
source | copies all values from |
Variables
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.
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.
Methods
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. |
---|
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
.
forEach (f:T ‑> Int ‑> T):ArrayedDeque<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).
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 occurence 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 occurence 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].
iterator ():Itr<T>
Returns a new ArrayedDequeIterator object to iterate over all elements contained in this deque.
Preserves the natural order of a deque.
See:
pack ():ArrayedDeque<T>
Removes all superfluous blocks and overwrites elements stored in empty locations with null.
An application can use this operation to free up memory by unlocking resources for the garbage collector.
remove (val:T):Bool
Removes and nullifies all occurrences of val
.
Returns:
true if at least one occurrence of val
was removed.