stdlib.collections

Collections Library

Generated from v0.60.1. 1 source files, 59 documented symbols.

collections.xi

fn as_slice[T](self: Self) -> Slice[T]

Generated summary: Method; Takes no arguments; returns Slice[T]. No source comment yet.

• Precondition: len >= 0
• Precondition: data != null || len == 0
• Postcondition: result.len() == len
• Postcondition: result.data.len == len

fn as_mut_slice[T](self: Self) -> Slice[T]

Generated summary: Method; Takes no arguments; returns Slice[T]. No source comment yet.

• Precondition: len >= 0
• Precondition: data != null || len == 0
• Postcondition: result.len() == len
• Postcondition: result.data.len == len

type Map

=== Map ===

Field	Type
keys	Vec[K]
values	Vec[V]

Invariants: - keys.len() == values.len()

type HashMap

Open-addressed hash map with linear probing.

Field	Type
data	Vec[HashMapBucket[K, V]]
len	Int
cap	Int

fn vec_reverse[T](v: &mut Vec[T])

Reverse elements in place. O(N).

fn vec_sort_asc[T](v: &mut Vec[T])

Sort elements in ascending order. O(N log N) avg.

fn vec_sort_desc[T](v: &mut Vec[T])

Sort elements in descending order. O(N log N) avg.

fn vec_contains[T](v: &Vec[T], value: T) -> Bool

Returns true if the value is present. O(N).

fn vec_dedup[T](v: &mut Vec[T])

Remove consecutive duplicate elements. O(N).

fn vec_rotate_left[T](v: &mut Vec[T], k: Int)

Rotate elements left by k positions. O(N).

fn vec_fill[T](v: &mut Vec[T], value: T)

Fill the vector with copies of value. O(N).

fn vec_swap_elems[T](v: &mut Vec[T], i: Int, j: Int)

Swap the elements at indices i and j. O(1).

fn vec_str_join(items: &Vec[Str], sep: Str) -> Str

Join a vector of strings with a separator. O(N-L) where L is avg string length.

fn vec_min[T](v: &Vec[T]) -> Option[T]

Minimum element in a vector, or None if empty. O(N).

fn vec_max[T](v: &Vec[T]) -> Option[T]

Maximum element in a vector, or None if empty. O(N).

fn vec_sum(v: &Vec[Int]) -> Int

Sum of all elements in an integer vector. O(N).

fn vec_avg(v: &Vec[Int]) -> Int

Integer average (truncated division) of a vector. Returns 0 if empty. O(N).

fn vec_count_if[T](v: &Vec[T], pred: fn(&T) -> Bool) -> Int

Count elements satisfying a predicate. O(N).

fn vec_any[T](v: &Vec[T], pred: fn(&T) -> Bool) -> Bool

Returns true if any element satisfies the predicate. O(N).

fn vec_all[T](v: &Vec[T], pred: fn(&T) -> Bool) -> Bool

Returns true if all elements satisfy the predicate. O(N).

fn map_len[K, V](m: Map[K, V]) -> Int

Number of entries in the map. O(1).

fn map_contains_key[K, V](m: &Map[K, V], key: &K) -> Bool

Returns true if the key exists in the map. O(N).

fn map_get_or[K, V](m: &Map[K, V], key: &K, default: V) -> V

Get value by key, or return default if not found. O(N).

fn map_remove_key[K, V](m: &mut Map[K, V], key: &K) -> Option[V]

Remove a key-value pair. Returns the value if the key was present. O(N).

fn map_clear[K, V](m: &mut Map[K, V])

Remove all entries from the map. O(1).

fn map_insert_if_absent[K, V](m: &mut Map[K, V], key: K, value: V) -> Bool

Insert a key-value pair only if the key is not already present. Returns true if inserted, false if key already existed. O(N).

fn map_merge[K, V](a: &Map[K, V], b: &Map[K, V]) -> Map[K, V]

Merge two maps into a new map. Entries from b overwrite those from a on key collision. O(N-M).

fn set_insert[T](s: &mut Set[T], value: T)

Insert a value into the set. O(N).

fn set_contains[T](s: &Set[T], value: &T) -> Bool

Returns true if the value is in the set. O(N).

fn set_remove[T](s: &mut Set[T], value: &T)

Remove a value from the set. O(N).

fn set_len[T](s: &Set[T]) -> Int

Number of elements in the set. O(1).

fn set_union[T](a: &Set[T], b: &Set[T]) -> Set[T]

Union of two sets: all elements present in either set. O(N-M).

fn set_intersection[T](a: &Set[T], b: &Set[T]) -> Set[T]

Intersection of two sets: elements present in both. O(N-M).

fn set_difference[T](a: &Set[T], b: &Set[T]) -> Set[T]

Difference of two sets: elements in a but not in b. O(N-M).

fn set_is_subset[T](sub: &Set[T], sup: &Set[T]) -> Bool

Returns true if sub is a subset of sup (all elements of sub are in sup). O(N-M).

fn set_is_empty[T](s: &Set[T]) -> Bool

Returns true if the set contains no elements. O(1).

fn set_to_vec[T](s: &Set[T]) -> Vec[T]

Convert a set to a vector containing all its elements. O(N).

fn set_from_vec[T](v: &Vec[T]) -> Set[T]

Create a set from a vector (deduplicates). O(N2).

fn vec_sort_by[T](v: &mut Vec[T], compare: fn(&T, &T) -> Int)

Sort a vector using a custom comparator. Delegates to xiom.sort.sort_by. O(N log N) average, O(N2) worst. Unstable. NOTE: the comparator must be a NAMED function -- inline lambdas crash the current runtime (see xiom.sort comparator note).

fn vec_window_max(v: &Vec[Int], k: Int) -> Vec[Int]

Sliding-window maximum: for each window of size k starting at index 0, the maximum element of that window. O(N-K) with O(K) extra space.

fn vec_window_min(v: &Vec[Int], k: Int) -> Vec[Int]

Sliding-window minimum: for each window of size k, the minimum element. O(N-K) with O(K) extra space.

fn vec_cumsum(v: &Vec[Int]) -> Vec[Int]

Cumulative sum: result[i] = v[0] + ... + v[i]. O(N). Empty input -> empty.

fn vec_dot(a: &Vec[Int], b: &Vec[Int]) -> Option[Int]

Dot product of two integer vectors, or None if lengths differ. O(N).

fn vec_product(v: &Vec[Int]) -> Int

Product of all elements in an integer vector. Returns 1 if empty. O(N).

fn vec_frequency_keys(v: &Vec[Int]) -> Vec[Int]

Frequency keys: distinct values of the vector, sorted ascending. O(N + M2). Companion of vec_frequency_counts; the two result vectors are parallel (keys[i] occurs counts[i] times).

fn vec_frequency_counts(v: &Vec[Int]) -> Vec[Int]

Frequency counts: occurrence counts aligned with vec_frequency_keys. O(N + M2).

fn vec_median(v: &mut Vec[Int]) -> Option[Int]

Median of an integer vector, or None if empty. O(N log N). Convention: returns the lower-middle element (index (n-1)/2) of the sorted copy, so even-length inputs yield the smaller of the two middle values.

fn vec_percentile(v: &mut Vec[Int], p: Int) -> Option[Int]

Percentile of an integer vector at p (0..100), or None if empty or p invalid. O(N log N). Convention: nearest-rank, index floor((n-1) * p / 100).

fn vec_find_all[T](v: &Vec[T], value: T) -> Vec[Int]

All indices where value occurs. O(N). Empty if not found.

fn vec_remove_all[T](v: &mut Vec[T], value: T)

Remove every occurrence of value in place. O(N). Stability preserved.

fn vec_retain[T](v: &mut Vec[T], keep: fn(&T) -> Bool) -> Int

Keep only elements for which keep returns true. Returns the number of removed elements. O(N). NOTE: pass a NAMED predicate -- lambdas crash the current runtime.

fn vec_is_sorted[T](v: &Vec[T]) -> Bool

Returns true if the vector is sorted in non-decreasing order. O(N).

fn vec_is_empty[T](v: &Vec[T]) -> Bool

Returns true if the vector has no elements. O(1).

fn vec_get_or[T](v: &Vec[T], i: Int, default: T) -> T

Element at index i, or default if out of bounds. O(1).

fn vec_left(v: &Vec[Int], i: Int) -> Vec[Int]

Left part of a vector: elements [0, i), clamped to the valid range. O(N).

fn vec_right(v: &Vec[Int], i: Int) -> Vec[Int]

Right part of a vector: elements [i, n). If i <= 0 the whole vector is returned; if i >= n the result is empty. O(N).

fn vec_zip_int(a: &Vec[Int], b: &Vec[Int]) -> Vec[Int]

Zip two integer vectors, interleaving pairs [a0, b0, a1, b1, ...] up to the shorter length. O(N).

fn vec_unzip_evens(v: &Vec[Int]) -> Vec[Int]

Even-indexed elements of a vector: [v[0], v[2], v[4], ...]. O(N). Pairs with vec_unzip_odds to recover the two halves of a zipped vector.

fn vec_unzip_odds(v: &Vec[Int]) -> Vec[Int]

Odd-indexed elements of a vector: [v[1], v[3], v[5], ...]. O(N).

---

---