envzn
0.8 · beta · not released

Library / Collections / Sequences / OrderedArray

CLASSEXTENDS Array<T> · IMPLEMENTS Comparable<OrderedArray<T>>, Equatable<OrderedArray<T>>

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 void
modifies

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 boolean
reads

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 boolean
reads

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 boolean
reads

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.