containers

use containers

The collection of structures you summon when you need them: Deque, PriorityQueue, SortedMap/ SortedSet (B-tree), Trie (ART), RingBuffer, and which grows each release. It is the open roster (tier 1) that complements the closed set of collections (List/Map/Set, tier 0): each algorithm here is frozen (tier 0 content), but the roster changes (tier 1). It follows the template of collections: assoc new/with_order, generic, access via at/get -> Optional (no overload of []), colorless (the @mm travels with the object, §5), Iterator, honest names (§14). The bar is what keeps the collection coherent as it accumulates, not a fixed list.

Construction convention (mirrors sort/sort_by)

T.new() gives natural order (the </== operator on the element, like collections.sort); T.with_order(cmp) gives a custom comparator fn(K,K)->Order. A structure without a sensible natural order does not expose new(), instead of inventing a third constructor: RingBuffer has only with_capacity (the capacity is the ring); PriorityQueue offers both (natural when the element has <, custom via with_order).

SortedMap[int, V].new()                    // natural order of the keys
SortedMap[Key, V].with_order(by_field)     // custom comparator
PriorityQueue[int].new()                   // min-heap by natural order
PriorityQueue[Task].with_order(by_pri)     // custom priority (Task has no natural order)
RingBuffer[T].with_capacity(1024)          // only with_capacity, no new()

---

Deque[T]: double-ended queue

Contiguous ring: push/pop O(1) at both ends. It needs no order, being a sequence, not keyed.

decl Deque[T] { ... }
fn (Deque[T]) new() -> Deque[T]
fn (Deque[T]) with_capacity(n: usize) -> Deque[T]

fn (d: *Deque[T]) push_front(item: T)
fn (d: *Deque[T]) push_back(item: T)
fn (d: *Deque[T]) pop_front() -> Optional[T]            // none if empty
fn (d: *Deque[T]) pop_back()  -> Optional[T]
fn (d: Deque[T])  front() -> Optional[T]
fn (d: Deque[T])  back()  -> Optional[T]
fn (d: Deque[T])  get(i: usize) -> Optional[T]          // logical index (0 = front)
fn (d: Deque[T])  len() -> usize
fn (d: Deque[T])  is_empty() -> bool
fn (d: *Deque[T]) clear()
fn (d: Deque[T])  iter() -> Iterator[T]                 // front → back

PriorityQueue[T]: binary heap

new() is a min-heap by natural order; with_order(cmp) is custom priority (max-heap = inverted comparator).

decl PriorityQueue[T] { ... }
fn (PriorityQueue[T]) new() -> PriorityQueue[T]                          // min-heap ('<' on T)
fn (PriorityQueue[T]) with_order(cmp: fn(T, T) -> Order) -> PriorityQueue[T]
fn (PriorityQueue[T]) with_capacity(n: usize) -> PriorityQueue[T]        // natural order + pre-reserve

fn (q: *PriorityQueue[T]) push(item: T)
fn (q: *PriorityQueue[T]) pop()  -> Optional[T]         // removes and returns the highest-priority one
fn (q: PriorityQueue[T])  peek() -> Optional[T]         // peeks without removing
fn (q: PriorityQueue[T])  len() -> usize
fn (q: PriorityQueue[T])  is_empty() -> bool

use containers

pq := containers.PriorityQueue[Task].with_order(by_priority)   // Task has no natural order → with_order
pq.push(task_a)
pq.push(task_b)
next := pq.pop()                                               // Optional[Task]: the highest-priority one

SortedMap[K, V] / SortedSet[T]: B-tree

The differential over the hash Map/Set is the maintained order: ordered iteration, range, floor/ceiling. O(log n) operations.

decl SortedMap[K, V] { ... }
fn (SortedMap[K, V]) new() -> SortedMap[K, V]                          // natural order of K
fn (SortedMap[K, V]) with_order(cmp: fn(K, K) -> Order) -> SortedMap[K, V]

fn (m: *SortedMap[K, V]) put(key: K, value: V) -> Optional[V]          // old value, if there was one
fn (m: SortedMap[K, V])  get(key: K) -> Optional[V]
fn (m: *SortedMap[K, V]) remove(key: K) -> Optional[V]
fn (m: SortedMap[K, V])  contains(key: K) -> bool
fn (m: SortedMap[K, V])  len() -> usize
fn (m: SortedMap[K, V])  first() -> Optional[(K, V)]                   // smallest key
fn (m: SortedMap[K, V])  last()  -> Optional[(K, V)]                   // largest key
fn (m: SortedMap[K, V])  floor(key: K)   -> Optional[(K, V)]           // largest key ≤ key
fn (m: SortedMap[K, V])  ceiling(key: K) -> Optional[(K, V)]           // smallest key ≥ key
fn (m: SortedMap[K, V])  range(lo: K, hi: K) -> Iterator[(K, V)]       // [lo, hi) in order
fn (m: SortedMap[K, V])  iter()   -> Iterator[(K, V)]                  // everything, in key order
fn (m: SortedMap[K, V])  keys()   -> Iterator[K]
fn (m: SortedMap[K, V])  values() -> Iterator[V]

decl SortedSet[T] { ... }
fn (SortedSet[T]) new() -> SortedSet[T]
fn (SortedSet[T]) with_order(cmp: fn(T, T) -> Order) -> SortedSet[T]
fn (s: *SortedSet[T]) add(item: T)    -> bool                          // false if it already existed
fn (s: *SortedSet[T]) remove(item: T) -> bool
fn (s: SortedSet[T])  contains(item: T) -> bool
fn (s: SortedSet[T])  len() -> usize
fn (s: SortedSet[T])  first() -> Optional[T]
fn (s: SortedSet[T])  last()  -> Optional[T]
fn (s: SortedSet[T])  floor(item: T)   -> Optional[T]
fn (s: SortedSet[T])  ceiling(item: T) -> Optional[T]
fn (s: SortedSet[T])  range(lo: T, hi: T) -> Iterator[T]               // [lo, hi) in order
fn (s: SortedSet[T])  iter() -> Iterator[T]                           // in order

scores := containers.SortedMap[int, string].new()
scores.put(90, "ana"); scores.put(75, "beto"); scores.put(60, "caio")
loop pair in scores.range(70, 100) { ... }            // [70,100) in order: (75,"beto"), (90,"ana")

Trie[K, V]: prefix tree, generic over a sequence (ART)

The key is a sequence []K; string (K = byte) is the special case. The implementation is an ART (adaptive radix tree) for byte keys (the common case), with general nodes for other K. The differential over the Map is the prefix operations.

decl Trie[K, V] { ... }
fn (Trie[K, V]) new() -> Trie[K, V]

fn (t: *Trie[K, V]) put(key: []K, value: V) -> Optional[V]
fn (t: Trie[K, V])  get(key: []K) -> Optional[V]
fn (t: *Trie[K, V]) remove(key: []K) -> Optional[V]
fn (t: Trie[K, V])  contains(key: []K) -> bool
fn (t: Trie[K, V])  len() -> usize
fn (t: Trie[K, V])  with_prefix(prefix: []K)  -> Iterator[([]K, V)]    // pairs whose key starts with prefix
fn (t: Trie[K, V])  longest_prefix(key: []K)  -> Optional[([]K, V)]    // the longest prefix of key present
fn (t: Trie[K, V])  iter() -> Iterator[([]K, V)]                       // in lexicographic order

alias StringTrie[V] = Trie[byte, V]      // the special case: string key (the UTF-8 bytes, s.bytes, §16)

routes := containers.Trie[byte, Route].new()
routes.put("/api/users".bytes, users_route)           // key = UTF-8 bytes of the string (§16)
match routes.longest_prefix("/api/users/42".bytes) {  // the longest prefix present
    none => not_found()
    hit  => dispatch(hit)
}

RingBuffer[T]: fixed-capacity ring (two ports)

Fixed capacity (does not grow): the capacity defines the ring, so there is only with_capacity. The overflow policy is yours, at the call site, via two ports: push rejects when full; force_push overwrites the oldest one.

decl RingBuffer[T] { ... }
fn (RingBuffer[T]) with_capacity(n: usize) -> RingBuffer[T]    // mandatory (defines the ring), no new()

fn (r: *RingBuffer[T]) push(item: T)       -> bool             // PORT 1: false if full (rejects)
fn (r: *RingBuffer[T]) force_push(item: T) -> Optional[T]      // PORT 2: overwrites; returns the evicted one (none if there was space)
fn (r: *RingBuffer[T]) pop()  -> Optional[T]                   // removes the oldest (FIFO)
fn (r: RingBuffer[T])  front() -> Optional[T]                  // the oldest
fn (r: RingBuffer[T])  back()  -> Optional[T]                  // the newest
fn (r: RingBuffer[T])  get(i: usize) -> Optional[T]            // logical index (0 = oldest)
fn (r: RingBuffer[T])  len() -> usize
fn (r: RingBuffer[T])  capacity() -> usize
fn (r: RingBuffer[T])  is_full()  -> bool
fn (r: RingBuffer[T])  is_empty() -> bool
fn (r: RingBuffer[T])  iter() -> Iterator[T]                   // oldest → newest

buf := containers.RingBuffer[Event].with_capacity(1024)
if !buf.push(ev) { dropped.inc() }                    // port 1: rejects if full
evicted := buf.force_push(ev)                          // port 2: overwrites; Optional of the evicted one

---

Curation

• Open roster, tier 1. collections is the closed and fundamental set (List/Map/Set, tier 0); containers is the collection that grows. Each algorithm inside is frozen (tier 0 content); the roster changes (tier 1), and that is what makes it an official lib and not core.
• The collections template governs, not a fixed list: assoc new/with_order, generic, at/ get -> Optional (no overload of []), colorless, Iterator, honest names. The bar is what keeps the collection from turning into a Frankenstein as it accumulates structures.
• new() + with_order() mirroring sort/sort_by: natural by default (< on the element), custom via fn(K,K)->Order. A structure without a natural order does not invent a third constructor: RingBuffer has only with_capacity; PriorityQueue accepts both (gated on <).
• RingBuffer is fixed-capacity, two ports. push rejects (returns whether it fit), force_push overwrites (returns the evicted one). The overflow policy is the user’s, at the call site, not fixed in the type.
• Trie generic over a sequence ([]K; string/K=byte is the special case; ART impl for the bytes). The prefix operations (with_prefix/longest_prefix) are what justify the Trie against the Map.
• SortedMap/SortedSet are B-tree. Order plus range plus floor/ceiling are the differential over the hash Map/Set; iteration always in key order.
• No allocator in the signatures (colorless): everything allocates via the context’s @mm; range/iter/ with_prefix are lazy Iterator.
• The collection grows. Next candidates, under the same template: intrusive list (the most coupled to the language, with the node embedding the link, *T), union-find (disjoint-set), bloom filter, LRU cache, skip list. They come in as additions (open roster), without touching what already exists.