containers

use containers

A coletânea de estruturas que você convoca quando precisa: Deque, PriorityQueue, SortedMap/ SortedSet (B-tree), Trie (ART), RingBuffer, e que cresce a cada release. É o roster aberto (tier 1) que complementa o conjunto fechado do collections (List/Map/Set, tier 0): cada algoritmo aqui é frozen (conteúdo tier 0), mas o roster muda (tier 1). Segue o template do collections: assoc new/with_order, genérico, acesso por at/get -> Optional (sem overload de []), colorless (o @mm viaja com o objeto, §5), Iterator, nomes honestos (§14). A régua é o que mantém a coletânea coerente conforme acumula, não uma lista fixa.

Convenção de construção (espelha sort/sort_by)

T.new() dá ordem natural (operador </== no elemento, como collections.sort); T.with_order(cmp) dá comparador custom fn(K,K)->Order. Estrutura sem ordem natural sensata não expõe new(), em vez de inventar um terceiro construtor: RingBuffer só tem with_capacity (a capacidade é o anel); PriorityQueue oferece os dois (natural quando o elemento tem <, custom via with_order).

SortedMap[int, V].new()                    // ordem natural das chaves
SortedMap[Key, V].with_order(by_field)     // comparador custom
PriorityQueue[int].new()                   // min-heap por ordem natural
PriorityQueue[Task].with_order(by_pri)     // prioridade custom (Task não tem ordem natural)
RingBuffer[T].with_capacity(1024)          // só with_capacity, sem new()

---

Deque[T]: fila de duas pontas

Anel contíguo: push/pop O(1) nas duas pontas. Não precisa de ordem, por ser sequência, não chaveada.

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 se vazia
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]          // índice lógico (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]: heap binário

new() é min-heap por ordem natural; with_order(cmp) é prioridade custom (max-heap = comparador invertido).

decl PriorityQueue[T] { ... }
fn (PriorityQueue[T]) new() -> PriorityQueue[T]                          // min-heap ('<' em T)
fn (PriorityQueue[T]) with_order(cmp: fn(T, T) -> Order) -> PriorityQueue[T]
fn (PriorityQueue[T]) with_capacity(n: usize) -> PriorityQueue[T]        // ordem natural + pré-reserva

fn (q: *PriorityQueue[T]) push(item: T)
fn (q: *PriorityQueue[T]) pop()  -> Optional[T]         // remove e devolve o de maior prioridade
fn (q: PriorityQueue[T])  peek() -> Optional[T]         // espia sem remover
fn (q: PriorityQueue[T])  len() -> usize
fn (q: PriorityQueue[T])  is_empty() -> bool

use containers

pq := containers.PriorityQueue[Task].with_order(by_priority)   // Task não tem ordem natural → with_order
pq.push(task_a)
pq.push(task_b)
next := pq.pop()                                               // Optional[Task]: o de maior prioridade

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

O diferencial sobre o hash Map/Set é a ordem mantida: iteração ordenada, range, floor/ceiling. Operações O(log n).

decl SortedMap[K, V] { ... }
fn (SortedMap[K, V]) new() -> SortedMap[K, V]                          // ordem natural de 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]          // valor antigo, se havia
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)]                   // menor chave
fn (m: SortedMap[K, V])  last()  -> Optional[(K, V)]                   // maior chave
fn (m: SortedMap[K, V])  floor(key: K)   -> Optional[(K, V)]           // maior chave ≤ key
fn (m: SortedMap[K, V])  ceiling(key: K) -> Optional[(K, V)]           // menor chave ≥ key
fn (m: SortedMap[K, V])  range(lo: K, hi: K) -> Iterator[(K, V)]       // [lo, hi) em ordem
fn (m: SortedMap[K, V])  iter()   -> Iterator[(K, V)]                  // tudo, em ordem de chave
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 se já existia
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) em ordem
fn (s: SortedSet[T])  iter() -> Iterator[T]                           // em ordem

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) em ordem: (75,"beto"), (90,"ana")

Trie[K, V]: árvore de prefixo, genérica sobre sequência (ART)

A chave é uma sequência []K; string (K = byte) é o caso especial. A implementação é uma ART (adaptive radix tree) para chaves de bytes (o comum), com nós gerais para outros K. O diferencial sobre o Map são as operações de prefixo.

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)]    // pares cuja chave começa com prefix
fn (t: Trie[K, V])  longest_prefix(key: []K)  -> Optional[([]K, V)]    // o prefixo mais longo de key presente
fn (t: Trie[K, V])  iter() -> Iterator[([]K, V)]                       // em ordem lexicográfica

alias StringTrie[V] = Trie[byte, V]      // o caso especial: chave string (os bytes UTF-8, s.bytes, §16)

routes := containers.Trie[byte, Route].new()
routes.put("/api/users".bytes, users_route)           // chave = bytes UTF-8 da string (§16)
match routes.longest_prefix("/api/users/42".bytes) {  // o prefixo mais longo presente
    none => not_found()
    hit  => dispatch(hit)
}

RingBuffer[T]: anel de capacidade fixa (duas portas)

Capacidade fixa (não cresce): a capacidade define o anel, então só há with_capacity. A política de overflow é sua, no call site, via duas portas: push rejeita quando cheio; force_push sobrescreve o mais antigo.

decl RingBuffer[T] { ... }
fn (RingBuffer[T]) with_capacity(n: usize) -> RingBuffer[T]    // obrigatória (define o anel), sem new()

fn (r: *RingBuffer[T]) push(item: T)       -> bool             // PORTA 1: false se cheio (rejeita)
fn (r: *RingBuffer[T]) force_push(item: T) -> Optional[T]      // PORTA 2: sobrescreve; devolve o despejado (none se havia espaço)
fn (r: *RingBuffer[T]) pop()  -> Optional[T]                   // remove o mais antigo (FIFO)
fn (r: RingBuffer[T])  front() -> Optional[T]                  // o mais antigo
fn (r: RingBuffer[T])  back()  -> Optional[T]                  // o mais novo
fn (r: RingBuffer[T])  get(i: usize) -> Optional[T]            // índice lógico (0 = mais antigo)
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]                   // mais antigo → mais novo

buf := containers.RingBuffer[Event].with_capacity(1024)
if !buf.push(ev) { dropped.inc() }                    // porta 1: rejeita se cheio
evicted := buf.force_push(ev)                          // porta 2: sobrescreve; Optional do despejado

---

Curadoria

• Roster aberto, tier 1. collections é o conjunto fechado e fundamental (List/Map/Set, tier 0); containers é a coletânea que cresce. Cada algoritmo dentro é frozen (conteúdo tier 0); o roster muda (tier 1), e é isso que faz dele lib oficial e não core.
• O template do collections governa, não uma lista fixa: assoc new/with_order, genérico, at/ get -> Optional (sem overload de []), colorless, Iterator, nomes honestos. A régua é o que impede a coletânea de virar Frankenstein conforme acumula estruturas.
• new() + with_order() espelhando sort/sort_by: natural por default (< no elemento), custom via fn(K,K)->Order. Estrutura sem ordem natural não inventa um terceiro construtor: RingBuffer só tem with_capacity; PriorityQueue aceita os dois (gated em <).
• RingBuffer é capacidade fixa, duas portas. push rejeita (devolve se coube), force_push sobrescreve (devolve o despejado). A política de overflow é do usuário, no call site, não fixa no tipo.
• Trie genérico sobre sequência ([]K; string/K=byte é o caso especial; impl ART pros bytes). As operações de prefixo (with_prefix/longest_prefix) são o que justifica a Trie frente ao Map.
• SortedMap/SortedSet são B-tree. Ordem mais range mais floor/ceiling são o diferencial sobre o hash Map/Set; iteração sempre em ordem de chave.
• Sem allocator nas assinaturas (colorless): tudo aloca pelo @mm do contexto; range/iter/ with_prefix são Iterator lazy.
• A coletânea cresce. Próximos candidatos, sob o mesmo template: lista intrusiva (a mais acoplada à linguagem, com o nó embutindo o elo, *T), union-find (disjoint-set), bloom filter, LRU cache, skip list. Entram como adição (roster aberto), sem mexer no que já existe.