A dynamic arrayed stack
A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list.
This is called a LIFO structure (Last In, First Out).
Example:
var stack = new polygonal.ds.ArrayedStack<Int>(4);
for (i in 0...4) stack.push(i);
trace(stack); //outputs:
[ ArrayedStack size=4 capacity=4
top
3 -> 3
2 -> 2
1 -> 1
0 -> 0
]
Constructor
new (initialCapacity:Int = 16, ?source:Array<T>, ?fixed:Bool)
Parameters:
initialCapacity | the initial physical space for storing values.
|
|---|---|
source | copies all values from |
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).
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 stack.
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.
inlinecopy (i:Int, j:Int):ArrayedStack<T>
Overwrites the element at index i with the element from index j.
An index of 0 indicates the bottommost element.
An index of this.size - 1 indicates the topmost element.
inlinedup ():ArrayedStack<T>
Pops the top element of the stack, and pushes it back twice, so that an additional copy of the former top item is now on top, with the original below it.
inlineforEach (f:T ‑> Int ‑> T):ArrayedStack<T>
Calls f on all elements.
The function signature is: f(input, index):output
- input: current element
- index: position relative to the bottom(=0) of the stack
- 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 stored at index i.
An index of 0 indicates the bottommost element.
An index of this.size - 1 indicates the topmost element.
inlinegetData ():NativeArray<T>
Returns a reference to the internal container storing the elements of this collection.
Useful for fast iteration or low-level operations.
iterator ():Itr<T>
Returns a new ArrayedStackIterator object to iterate over all elements contained in this stack.
Preserves the natural order of a stack (First-In-Last-Out).
See:
pack ():ArrayedStack<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.
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):ArrayedStack<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.
rotLeft (n:Int):ArrayedStack<T>
Moves the n topmost elements on the stack in a rotating fashion.
Example:
top
|3| |2|
|2| rotate left |1|
|1| --> |0|
|0| |3|
rotRight (n:Int):ArrayedStack<T>
Moves the n topmost elements on the stack in a rotating fashion.
Example:
top
|3| |0|
|2| rotate right |3|
|1| --> |2|
|0| |1|
inlineset (i:Int, val:T):ArrayedStack<T>
Replaces the element at index i with val.
An index of 0 indicates the bottommost element.
An index of this.size - 1 indicates the topmost element.
shuffle (?rvals:Array<Float>):Void
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 |
|---|
inlineswap (i:Int, j:Int):ArrayedStack<T>
Swaps the element stored at i with the element stored at index j.
An index of 0 indicates the bottommost element.
An index of this.size - 1 indicates the topmost element.
toArray ():Array<T>
Returns an array containing all elements in this stack.
Preserves the natural order of this stack (First-In-Last-Out).