Library / Collections / Sequences / OrderedArray
OrderedArray
Opaque-size, ordered, indexable collection.
Constructors 2
INIT()Default constructor
INIT(int64 presized)
for presized Stack allocation
Methods 5
OVERRIDE METHOD clone() RETURNS OrderedArray[T]reads
Deep copy. Each element is cloned via T->clone(); T must
implement Cloneable when T is a class type.
For T IS Inoperative (opaque only today): returns
an empty Array — Inoperative values are opaque so we can't
preserve them on clone.
MODIFY METHOD sort() RETURNS voidmodifies
In-place insertion sort using T->isLessThan(other). T must
implement Comparable[T] — the compiler emits a clear "T does
not implement Comparable" diagnostic at instantiation otherwise.
Each element is walked down by swapping it with its left neighbour
while it is strictly smaller, so equal elements keep their order
(stable). No element is copied and no slot is ever empty: the old
form lifted the element out with T key := .data[i], which is a move
from a reference (E6040) and silently deep-cloned every key.
O(n^2) worst case; acceptable for the small-N collections this
V1 kernel typically holds. A heap-or-merge-sort upgrade is a
V2 candidate if profiling demands it.
METHOD contains(REFERENCE T value) RETURNS booleanreads
Linear scan for an element equal to value. T must implement
Equatable[T] for class T. O(n).
METHOD equals(REFERENCE OrderedArray[T] other) RETURNS booleanreads
Element-wise equality. Two arrays are equal when they are the same
length and every element at the same index is equal — which makes two
EMPTY arrays equal, the case the previous form got wrong: it seeded
result = FALSE and only ever set it TRUE from inside the element
loop, so a pair of empty arrays passed the length test, never entered
the loop, and were reported UNEQUAL.
METHOD isLessThan(REFERENCE OrderedArray[T] other) RETURNS booleanreads
LEXICOGRAPHIC, the same order String.isLessThan settled on and for the
same reason. The first differing element decides; if neither array
differs through the shorter one's length, the shorter is less — so a
prefix sorts before what extends it.
This returned .length < other.length. Length-first is a different
total order, not a cheaper route to this one: it ranks [9] below
[1,1] and calls every pair of same-length arrays equal-or-greater
regardless of content, which silently reorders any OrderedArray-keyed
RedBlackTreeDictionary and makes sort() over arrays-of-arrays wrong.