Module collections/array_list

Number of elements. O(1) — the length is stored, never counted.

True when the list holds no elements — len() == 0.

Elements the current buffer can hold before push has to reallocate.

SIZE_MAX for a zero-sized element type, which never grows — see _zst_anchor. Rust's Vec::capacity reports usize::MAX for the same reason.

Raw pointer to the element buffer, or .None when nothing is allocated yet — Rust's Vec::as_ptr, minus the dangling-pointer guarantee.

The pointer is only valid until the next reallocation (push past capacity, reserve, ensure_total_capacity, shrink_to_fit), and it borrows: it does not keep the list alive.

Declare that the first new_len slots of the buffer are live — Rust's Vec::set_len, and just as unsafe.

Nothing is initialized and nothing is dropped: growing the length exposes whatever bytes the buffer already held, and shrinking it leaks the elements past the new end (dispose and clear only walk [0, len)). Reach for it only after filling the buffer through ptr() or extend_from_ptr. PANICS when new_len exceeds the capacity.

Empty list. Allocates nothing — the first push buys the buffer (four elements), as Rust's Vec::new does.

Owned copy of [r.start, r.end) of a fixed-size array. The end is clamped to N, so an over-long range yields a short list.

Inclusive-range companion of slice_copy (arr(a..=b)).

Owned ArrayList copy of a fixed-size array's elements — the companion to array range-indexing (plans/archive/SLICE_REWORK.md).

N comes from the array's type, so the exact capacity is reserved up front and no growth happens.

Empty list whose buffer already holds cap elements — Rust's Vec::with_capacity.

PANICS on "capacity overflow" when sizeof(T) * cap would wrap (Rust panics with the same message), and on allocation failure. A zero-sized element type takes the one-byte anchor buffer instead of allocating cap of nothing.

The one buffer an ArrayList of a ZERO-SIZED element type ever has.

sizeof(T) == 0 (unit, an all-unit aggregate, Array(unit, N)) means the elements occupy no bytes: a store writes nothing, a read reads nothing, and the byte size of every buffer is 0. Rust's Vec<()> never allocates and reports capacity() == usize::MAX. Yo cannot conjure a non-null dangling pointer, so the stand-in is ONE one-byte block, allocated once and never resized: the capacity is SIZE_MAX, so push never reaches the grow path, and shrink_to_fit is a no-op. Going through the allocator with sizeof(T) * cap == 0 instead would malloc(0) and then realloc(p, 0) — which frees p and returns NULL on glibc and the Windows CRT — and the list would report "allocation failed" on its second growth.

Append an element, reporting allocation failure as .Err(.AllocError(.OutOfMemory)) instead of panicking.

The allocator-aware form (D9); push is the one to reach for. Amortized O(1) — the buffer doubles (4 elements first), so a growth INVALIDATES every pointer previously handed out by ptr(), iter() or the Index impl.

Append an element — amortized O(1).

PANICS on allocation failure: Rust's Vec::push aborts, and so do this list's own ensure_total_capacity / with_capacity. Before D9 this returned a Result that every one of its callers discarded, usually via a throwaway _p := binding — a Result nobody checks is strictly worse than a panic, because it reads as if the failure were handled. Use try_push when the caller genuinely handles OOM.

A growth reallocates, so any pointer into the buffer (ptr(), iter(), self(i)) is invalid afterwards.

Remove and return the last element, or .None when empty — O(1), and the capacity is kept.

Copy of the element at index, or .None when index >= len().

The bounds-checked reader. self(index) (the Index impl) hands back a POINTER into the buffer and panics out of range instead; iter() is the way to walk without copying a refcounted T.

Give the unused tail of the buffer back to the allocator so that capacity() == len() — Rust's Vec::shrink_to_fit.

Reallocates (an empty list frees its buffer outright), so every pointer into the buffer is invalid afterwards and the next push grows again. .Err(.AllocError(.OutOfMemory)) when the shrinking realloc fails — the list is left untouched and usable. A zero-sized element type is a no-op: its anchor buffer cannot shrink.

Remove the elements in [r.start, r.end) and return them, in order, as a fresh list — Rust's Vec::drain, collected eagerly rather than lazily (Yo has no borrowing iterator to hold the source open).

O(n): the tail shifts left to close the gap. PANICS on an inverted range or an end past the length — the old remove(start, count) silently clamped the count, which hid caller bugs.

Insert value at idx, shifting the tail right — O(n). idx == len appends, as in Rust.

Move every element of other onto the end of self, leaving other EMPTY — Rust's append. extend copies instead.

First element, or .None when empty.

Last element, or .None when empty.

Reserve room for additional MORE elements.

Rust's spelling. ensure_total_capacity takes a TOTAL, which is the same call with a different meaning and an easy one to get wrong at a call site.

Exchange the elements at i and j.

Moves the raw slots, like reverse — no dup/drop, so this is RC-neutral however the element type is refcounted.

Remove the element at idx and return it, moving the LAST element into the hole — O(1), and it does not preserve order. Rust's swap_remove.

Shorten to new_len, dropping the elements past it. Longer new_len is a no-op, as in Rust.

Resize to exactly new_len, dropping the tail when shrinking and appending copies of value when growing. Rust's resize.

Distinct from resize_with_byte, which memsets raw storage and is only meaningful for a plain-old-data element type.

Overwrite every element with value, keeping the length. Rust's fill.

Split off [at, len) into a new list, leaving [0, at) here.

Remove the element at idx and return it, shifting the tail left — O(n), order preserved. Rust's Vec::remove.

PANICS when idx >= len(). swap_remove is the O(1) alternative when order does not matter, and LinkedList.remove returns a Result instead — a deliberate difference (D1): the list that has to walk to the index reports the caller's mistake as a value.

Owned copy of [start, end), or an .IndexOutOfBounds error — the CHECKED counterpart of slice_copy, which clamps instead.

An inverted range reports .IndexOutOfBounds(index : start, length : end). O(end - start), one allocation of the exact size.

Grow the buffer so it holds at least min_cap elements in TOTAL, doubling as it goes; a request under the current capacity does nothing.

reserve(additional) is the Rust spelling and takes a COUNT TO ADD — the same call with a different meaning, and the easy one to get right at a call site. PANICS on capacity overflow and on allocation failure (try_push is the only allocator-aware entry point). Reallocates, so pointers into the buffer do not survive it.

Append count elements from a raw buffer with one memcpy.

The caller guarantees src holds count initialized, correctly aligned Ts that do not alias this list's buffer. The bytes are copied WITHOUT per-element dup, so for a refcounted T this MOVES the source elements: the caller must not also release them. Reaching for it on a plain-data element type is the point — that is where it beats a push loop.

Drop every element and set the length to 0, KEEPING the capacity — Rust's Vec::clear. Use shrink_to_fit afterwards to release the buffer too.

Overwrite the live len() elements with a repeated byte via memset — the fast way to zero a bool / integer list.

Writes over the elements without dropping them, so it is only sound for a plain-data T: on a refcounted element type it strands every handle it overwrites. fill(value) is the type-safe form.

Set the length to exactly new_len, memsetting any newly exposed slots to a repeated byte.

Shrinking does NOT run destructors and growing does not construct anything, so — like fill_with_byte — this is for a plain-data T only; resize(new_len, value) is the type-safe form. Growing may reallocate and can panic on allocation failure.

Returns a pointer to the element at the given index. Panics if the index is out of bounds.

Drops every live element and frees the buffer. Runs when the last reference to the list goes away, not at the end of the binding's scope.

Cycle-GC tracing. The elements live in a malloc'd buffer the compiler's auto-derived field walk cannot reach, so trace each element's buffer slot. tracer.visit takes the slot POINTER and reads it WITHOUT touching the element's reference count — a by-value managed handle would be dup'd then dropped, freeing a live element mid-collection.

Borrowing walk over a shared handle: yields a *(T) into the list's buffer and leaves the list intact — for(list.iter(), ptr => ...), where into_iter would move the list and yield values (D14; the iter / into_iter split every other std collection already had).

The receiver arrives RC-dup'd at the method boundary, so moving it into the iterator is balanced and the buffer outlives the walk. Do not grow the list mid-walk: a reallocation invalidates the pointers already yielded.

Remove CONSECUTIVE duplicates, keeping the first of each run — Rust's dedup. Only adjacent equals collapse, so [1,2,1] is unchanged; sort first if you want set semantics.

Whether self begins with prefix — Rust's starts_with.

Whether self ends with suffix — Rust's ends_with.

Whether any element equals value — a linear scan, O(n), stopping at the first match. Rust's Vec::contains.

Index of the FIRST element equal to value, or .None — a linear scan, O(n). Rust spells this iter().position(...); on a sorted list reach for binary_search instead.

Reverse the elements in place, O(n).

Exchanges raw slots, like swap, so no element is dup'd or dropped — RC-neutral however T is refcounted.

Sort ascending by Ord. STABLE (D17): equal elements keep their input order, as sort does in Rust, Python, Java and Go.

O(n log n) with one usize index array plus scratch allocated for the merge — sort_unstable is the allocation-free heapsort for when order among equals does not matter.

Sort ascending by Ord WITHOUT preserving the order of equal elements — Rust's sort_unstable. Heapsort: O(n log n) worst case, in place, no allocation, no recursion (see _heapsort_by).

The default value of the type.

Create an independent clone of self.

The empty collection collect starts from.

Add one element to a partially-built collection and return it.

Sort by a caller-supplied strict "less" — less(a, b) is true when a must come before b. STABLE: equal elements keep their input order, matching Rust's sort_by. Use sort_unstable_by for the allocation-free heapsort.

Sort ascending by a KEY extracted from each element — Rust's sort_by_key. Stable, like sort_by, which it delegates to.

The key type is a method-level generic(K : Type), which the clause order requires to come BEFORE self; it is inferred from the closure at the call site, so xs.sort_by_key((p) => p.age) needs no annotation.

Binary search over a list ordered by cmp — Rust's binary_search_by.

cmp reports how each ELEMENT orders against the target (.Less when the element comes first), so searching does not require constructing a T to compare against — which is the whole reason to reach for this over binary_search. .Ok(index) of a match (any one of an equal run), or .Err(insertion_index).

Non-overlapping chunks of size, in order — Rust's chunks. The final chunk is SHORT when the length is not a multiple of size.

PANICS on size == 0, as Rust does.

Overlapping windows of EXACTLY size, advancing one element at a time — Rust's windows. Yields nothing when the list is shorter than size.

PANICS on size == 0, as Rust does.

Sort by a caller-supplied strict "less" WITHOUT preserving the order of equal elements (heapsort). Rust's sort_unstable_by.

Keep only the elements pred accepts, in place and in order; the rejected elements are dropped. One pass: the survivors are collected into a fresh list, clear releases every original, extend moves the survivors back — O(n) with a single allocation, and every RC step is one of the module's proven public operations (push / clear / extend). The first cut compacted through raw pointers and double-released RC elements (the Linux-ASan heap-use-after-free on PR #313's first run; local ASan is non-functional, so CI was the first to see it); the second walked backwards over drain, which was O(n²) with an allocation per rejection (issues/fixed/array-list-retain-is-quadratic.md).

Append a copy of every element of other.

Binary search over a SORTED list (ascending, sort's order): .Ok(index) of a matching element (any one of an equal run), or .Err(insertion_index) where the value would keep the order.

Advance the iterator and return the next value, or None when exhausted.

Advance the iterator from the back and return the previous value, or None when the two ends have met.

Advance the iterator and return the next value, or None when exhausted.

Advance the iterator from the back and return the previous value, or None when the two ends have met.

Advance the iterator and return the next value, or None when exhausted.

Advance the iterator and return the next value, or None when exhausted.