collections: BankersQueue, a persistent queue with shared structure (C7) #199

New issue

Closed

opened 2026-10-08 13:42:01 +00:00 by orion · 2 comments

orion commented

2026-10-08 13:42:01 +00:00

Collaborator

Goal

BankersQueue<Item>: an implementation of Queue as two cons lists (front, and rear reversed), O(1) amortised enqueue/dequeue, with copies sharing structure (COLLECTIONS.md section 3.3 table).

Acceptance criteria

public type BankersQueue<Item> with Queue<Item>, From<Iterate<Item>>; enqueue, dequeue, peek, length, iterate (front to back), clear, compact, Equals/Hash as ArrayQueue.
Reuses or mirrors the node type of ConsStack (#198); if it needs a shared private node type, it lands after that issue.
Copies are independent; the rear is reversed once per rebalance, not per operation.
Conformance program (interleaved enqueue/dequeue, copies, empty cases, order equal to ArrayQueue on the same sequence); benchmark against ArrayQueue.

Seed impact

None. A new public type in std/collections written in plain TorbScript over a List; no syntax change, no new native, no runtime change (runtime/list.c stays the one storage, COLLECTIONS.md section 3.10 point 5), and the compiler looks up none of the new names by string (section 6a). Not breaking: only additions.

Size

One PR, one feat(collections) commit (plus tests and docs in the same commit or a second test/docs one).

Common to the C7 types

Export from std/collections/src/lib.trb (public use ...), doc comments with the cost profile of the implementation, as ArrayQueue has.
A conformance program in tests/conformance/ (.trb + .expected), run natively and in the VM, in the style of queue-grows.trb.
A benchmark in benchmarks/ (one small program plus its C counterpart, see benchmarks/README.md) against the array implementation. It is a measurement, not a gate.
skills/ regenerated when docs change; the worker does not run gates locally, CI does.

Source

COLLECTIONS.md C7, parent #139

## Goal `BankersQueue<Item>`: an implementation of `Queue` as two cons lists (front, and rear reversed), O(1) amortised `enqueue`/`dequeue`, with copies sharing structure (COLLECTIONS.md section 3.3 table). ## Acceptance criteria - [ ] `public type BankersQueue<Item> with Queue<Item>, From<Iterate<Item>>`; `enqueue`, `dequeue`, `peek`, `length`, `iterate` (front to back), `clear`, `compact`, `Equals`/`Hash` as `ArrayQueue`. - [ ] Reuses or mirrors the node type of `ConsStack` (#198); if it needs a shared private node type, it lands after that issue. - [ ] Copies are independent; the rear is reversed once per rebalance, not per operation. - [ ] Conformance program (interleaved enqueue/dequeue, copies, empty cases, order equal to `ArrayQueue` on the same sequence); benchmark against `ArrayQueue`. ## Seed impact None. A new public type in `std/collections` written in plain TorbScript over a `List`; no syntax change, no new native, no runtime change (`runtime/list.c` stays the one storage, COLLECTIONS.md section 3.10 point 5), and the compiler looks up none of the new names by string (section 6a). Not breaking: only additions. ## Size One PR, one `feat(collections)` commit (plus tests and docs in the same commit or a second `test`/`docs` one). ## Common to the C7 types - Export from `std/collections/src/lib.trb` (`public use ...`), doc comments with the cost profile of the implementation, as `ArrayQueue` has. - A conformance program in `tests/conformance/` (`.trb` + `.expected`), run natively and in the VM, in the style of `queue-grows.trb`. - A benchmark in `benchmarks/` (one small program plus its C counterpart, see `benchmarks/README.md`) against the array implementation. It is a measurement, not a gate. - `skills/` regenerated when docs change; the worker does not run gates locally, CI does. ## Source - [COLLECTIONS.md C7](https://git.torb.dev/torbscript/language/blob/main/docs/design/COLLECTIONS.md#L992), parent #139

orion added the

loop

ready

labels

2026-10-08 13:42:01 +00:00

orion referenced this issue

2026-10-08 13:42:17 +00:00

collections: RingList, ConsStack, BankersQueue, Heap (C7) #139