A growable, dense array.
Example:
var o = new polygonal.ds.ArrayList<Int>();
for (i in 0...4) o.pushBack(i);
trace(o); //outputs:
[ ArrayList size=4 capacity=4
0 -> 0
1 -> 1
2 -> 2
3 -> 3
]
Constructor
new (initalCapacity:Int = 2, ?source:Array<T>, ?fixed:Bool)
Parameters:
initialCapacity | the initial container size for storing values. Useful before inserting a large number of elements as this reduces the amount of incremental reallocation. |
---|---|
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
addArray (vals:Array<T>, first:Int = 0, count:Int = -1):Int
Appends count
elements stored in vals
starting at index first
to this list.
Parameters:
from | the index to start from. If omitted, |
---|---|
count | the number of elements to append. If omitted, |
addNativeArray (vals:NativeArray<T>, first:Int = 0, count:Int = -1):Int
Appends count
elements stored in vals
starting at index first
to this list.
Parameters:
from | the index to start from. If omitted, |
---|---|
count | the number of elements to append. If omitted, |
binarySearch (val:T, from:Int, ?cmp:T ‑> T ‑> Int):Int
Finds the first occurrence of val
by using the binary search algorithm assuming elements are sorted.
Parameters:
from | the index to start from. The default value is 0. |
---|---|
cmp | a comparison function for the binary search. If omitted, the method assumes that all elements implement |
Returns:
the index storing val
or the bitwise complement (~) of the index where the val
would be inserted (guaranteed to be a negative number).
The insertion point is only valid if from
is 0.
blit (destination:Int, source:Int, n:Int):ArrayList<T>
Copies n
elements from the location pointed by the index source
to the location pointed by destination
.
Copying takes place as if an intermediate buffer was used, allowing the destination and source to overlap.
See:
inlinebruteforce (f:T ‑> T ‑> Void):ArrayList<T>
Brute-force search (aka exhaustive search).
Calls f
on all pairs.
Example:
var list = new ArrayList<String>(["a", "b", "c"]);
list.bruteforce(function(a, b) trace('($a,$b)')); //outputs (a,b), (a,c), (b,c);
inlineclear (gc:Bool = false):Void
Clears this list by nullifying all elements 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 list.
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
.
concat (val:ArrayList<T>, copy:Bool = false):ArrayList<T>
Concatenates this array with val
by appending all elements of val
to this array.
Parameters:
copy | if true, returns a new array instead of modifying this array. |
---|
inlinecopy (src:Int, dst:Int):ArrayList<T>
Replaces the element at index dst
with the element stored at index src
.
inlineforEach (f:T ‑> Int ‑> T):ArrayList<T>
Calls f
on all elements in order.
The function signature is: f(value, index):output
- value: current element
- index: the index number of value
- 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).
inlinegetData ():NativeArray<T>
Returns a reference to the internal container storing the elements of this collection.
Useful for fast iteration or low-level operations.
getRange (fromIndex:Int, toIndex:Int):List<T>
Returns an ArrayList
object storing elements in the range [fromIndex
, toIndex
).
If toIndex
is negative, the value represents the number of elements.
indexOf (val:T):Int
Finds the first occurrence of val
(by incrementing indices - from left to right).
Returns:
the index storing val
or -1 if val
was not found.
init (n:Int, ?val:T):ArrayList<T>
Sets n
elements to val
(by reference).
Automatically reserves storage for n
elements so an additional call to this.reserve()
is not required.
insert (index:Int, val:T):Void
Inserts val
at the specified index
.
Shifts the element currently at that position (if any) and any subsequent elements to the right (indices + 1).
If index
equals this.size
, val
gets appended to the end of the list.
inlineinsertionSort (cmp:T ‑> T ‑> Int, first:Int, count:Int):ArrayList<T>
Sorts the elements using the insertion sort algorithm. Fast for nearly sorted lists.
Parameters:
cmp | a comparison function. |
---|---|
first | sort start index. |
count | the number of elements to sort (range: [ |
iterator ():Itr<T>
Returns a new ArrayListIterator object to iterate over all elements contained in this list.
Order: Row-major order (row-by-row).
See:
join (sep:String):String
Converts the data in this dense array to strings, inserts sep
between the elements, concatenates them, and returns the resulting string.
lastIndexOf (val:T, from:Int = -1):Int
Finds the first occurrence of val
(by decrementing indices - from right to left) and returns the index storing val
or -1 if val
was not found.
Parameters:
from | the index to start from.
|
---|
pack ():ArrayList<T>
Reduces the capacity of the internal container (up 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.
inlinepairwise (visit:Int ‑> T ‑> T ‑> Void):Void
Visits all elements in as a pair by calling visit
.
The function signature is: visit(currentPairIndex, firstPairElement, secondPairElement)
Example:
var points = [1.1, 1.2, 2.1, 2.2]; //format: [x0, y0, x1, y1, xn, yn, ...]
list.pairwise(function(i, x, y) trace('point $i: x=$x, y=$y'));
popFront ():T
Removes and returns the first element.
To fill the gap, any subsequent elements are shifted to the left (indices - 1).
pushFront (val:T):Int
Prepends val
to the first element and returns the new size.
Shifts the first element (if any) and any subsequent elements to the right (indices + 1).
remove (val:T):Bool
Removes all occurrences of val
.
Shifts any subsequent elements to the left (indices - 1).
Returns:
true if at least one occurrence of val
was removed.
removeAt (i:Int):T
Removes the element at the specified index i
.
Shifts any subsequent elements to the left (indices - 1).
reserve (n:Int):ArrayList<T>
Preallocates internal 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.
resize (n:Int):ArrayList<T>
Resizes the container so that it contains n
elements.
If n
< current container size, content is reduced to its first n
elements, removing those beyond.
If n
> current container size, content is expanded by appending as many elements as needed to reach a size of n
.
reverse (first:Int = 0, last:Int = -1):ArrayList<T>
Reverses this list in place in the range [first
, last
] (the first element becomes the last and the last becomes the first).
shuffle (?rvals:Array<Float>):ArrayList<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 |
---|
sort (?cmp:T ‑> T ‑> Int, useInsertionSort:Bool = false, first:Int = 0, count:Int = -1):ArrayList<T>
Sorts the elements of this dense array using the quick sort algorithm.
Parameters:
cmp | a comparison function.
|
---|---|
useInsertionSort | if true, the dense array is sorted using the insertion sort algorithm.
|
first | sort start index. The default value is 0. |
count | the number of elements to sort (range: [ |
inlineswap (i:Int, j:Int):ArrayList<T>
Swaps the element stored at index i
with the element stored at index j
.
inlineswapPop (i:Int):T
Fast removal of the element at index i
if the order of the elements doesn't matter.
Returns:
the element at index i
prior removal.
toArray ():Array<T>
Returns an array containing all elements in this list.
Preserves the natural order of this array.