collections: `RingList`, `ConsStack`, `BankersQueue`, `Heap` (C7)

orion commented

2026-10-05 21:07:24 +00:00

Collaborator

Goal

Tracking issue for C7 of COLLECTIONS.md: the implementations that make the List, Stack and Queue traits worth having, and the priority structure of section 3.4. C7 is larger than one PR (four types, each with conformance tests and a benchmark), so it is split one issue per type:

#197 RingList (ready)
#198 ConsStack (ready)
#199 BankersQueue (ready; shares the node type with #198)
#200 Heap (waiting on an owner decision: member words)

Acceptance criteria

#197, #198, #199 and #200 are closed.
The C7 paragraph of COLLECTIONS.md reads Done (the last PR to land marks it), and uses Heap instead of the superseded name Ordered.
docs/ROADMAP.md collections row stays accurate (C8 / #140 is separate).

Design record

COLLECTIONS.md: section 3.3 (cost table), 3.4 (no Deque, no PriorityQueue trait), 3.10 (points 4 and 5), section 6 questions 4 to 6 (names answered 2026-09-23: Heap, RingList, tour keeps Stack/Queue).

Seed impact

None for any of the four: new public types in std/collections in plain TorbScript, no syntax change, no new native, no std name looked up by string.

Dependencies

#199 after #198 if they share the node type. Otherwise independent.

## Goal Tracking issue for C7 of [COLLECTIONS.md](https://git.torb.dev/torbscript/language/blob/main/docs/design/COLLECTIONS.md#L992): the implementations that make the `List`, `Stack` and `Queue` traits worth having, and the priority structure of section 3.4. C7 is larger than one PR (four types, each with conformance tests and a benchmark), so it is split one issue per type: - [ ] #197 `RingList` (ready) - [ ] #198 `ConsStack` (ready) - [ ] #199 `BankersQueue` (ready; shares the node type with #198) - [ ] #200 `Heap` (waiting on an owner decision: member words) ## Acceptance criteria - [ ] #197, #198, #199 and #200 are closed. - [ ] The C7 paragraph of COLLECTIONS.md reads **Done** (the last PR to land marks it), and uses `Heap` instead of the superseded name `Ordered`. - [ ] `docs/ROADMAP.md` collections row stays accurate (C8 / #140 is separate). ## Design record [COLLECTIONS.md](https://git.torb.dev/torbscript/language/blob/main/docs/design/COLLECTIONS.md): section 3.3 (cost table), 3.4 (no `Deque`, no `PriorityQueue` trait), 3.10 (points 4 and 5), section 6 questions 4 to 6 (names answered 2026-09-23: `Heap`, `RingList`, tour keeps `Stack`/`Queue`). ## Seed impact None for any of the four: new public types in `std/collections` in plain TorbScript, no syntax change, no new native, no std name looked up by string. ## Dependencies #199 after #198 if they share the node type. Otherwise independent.

orion added the

loop

label

2026-10-05 21:07:24 +00:00

orion commented

2026-10-08 13:40:46 +00:00

Author

Collaborator

[loop:torbscript] claim refine by session:loop-torbscript-20261008 until 2026-10-08T17:40:00Z

orion referenced this issue

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

collections: RingList, a List with O(1) at both ends (C7) #197

orion referenced this issue

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

collections: ConsStack, a persistent stack with shared tails (C7) #198

orion referenced this issue

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

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

orion referenced this issue

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

collections: Heap, a priority structure ordered by a key (C7) #200

orion commented

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

Author

Collaborator

[loop:torbscript] refine: C7 is larger than one PR, so it is split into #197 (RingList), #198 (ConsStack), #199 (BankersQueue) and #200 (Heap); this issue is now the tracking issue (body rewritten with goal, acceptance criteria, design record and seed impact: none). #197 to #199 are ready (names settled by the owner on 2026-09-23, additive, no seed refresh), next: implement.

[loop:torbscript] owner decision: which member words does Heap use?

What: the Heap snippet in COLLECTIONS.md section 3.4 still reads type Ordered<Item> with Collection<Item> with add/remove. Since then Collection was deleted and every kind got its own words (section 6b: push/pop, enqueue/dequeue, append, insert). The name Heap is settled, the words are not, and Heap is neither a Stack nor a Queue.

Options:

insert(value) / removeSmallest() / peekSmallest(): says the contract (the smallest key leaves first) at the call, no clash with the Stack/Queue verbs.
push(value) / pop() / peek(): the words everybody knows from a binary heap, but they read as a stack and Stack has a different order contract.
add(value) / remove() as in the stale snippet: add was taken away from the container kinds in 6b, so it would reintroduce the word the record removed.

Recommendation: option 1. It keeps one vocabulary per kind, and the key order is visible in the name. #200 follows the answer; the other three types do not wait for it.

v: 1
id: q1
asked_by: orion
to: torben
blocking: true
kind: decision
question: Which member words for Heap: insert/removeSmallest/peekSmallest (option 1), push/pop/peek (option 2), or add/remove as in the old snippet (option 3)?
options: 1 = insert/removeSmallest/peekSmallest, 2 = push/pop/peek, 3 = add/remove
recommendation: 1

next: waiting (owner decision)

[loop:torbscript] refine: C7 is larger than one PR, so it is split into #197 (`RingList`), #198 (`ConsStack`), #199 (`BankersQueue`) and #200 (`Heap`); this issue is now the tracking issue (body rewritten with goal, acceptance criteria, design record and seed impact: none). #197 to #199 are `ready` (names settled by the owner on 2026-09-23, additive, no seed refresh), next: implement. [loop:torbscript] owner decision: which member words does `Heap` use? What: the `Heap` snippet in COLLECTIONS.md section 3.4 still reads `type Ordered<Item> with Collection<Item>` with `add`/`remove`. Since then `Collection` was deleted and every kind got its own words (section 6b: `push`/`pop`, `enqueue`/`dequeue`, `append`, `insert`). The name `Heap` is settled, the words are not, and `Heap` is neither a `Stack` nor a `Queue`. Options: 1. `insert(value)` / `removeSmallest()` / `peekSmallest()`: says the contract (the smallest key leaves first) at the call, no clash with the `Stack`/`Queue` verbs. 2. `push(value)` / `pop()` / `peek()`: the words everybody knows from a binary heap, but they read as a stack and `Stack` has a different order contract. 3. `add(value)` / `remove()` as in the stale snippet: `add` was taken away from the container kinds in 6b, so it would reintroduce the word the record removed. Recommendation: option 1. It keeps one vocabulary per kind, and the key order is visible in the name. #200 follows the answer; the other three types do not wait for it. ```hos-question v: 1 id: q1 asked_by: orion to: torben blocking: true kind: decision question: Which member words for Heap: insert/removeSmallest/peekSmallest (option 1), push/pop/peek (option 2), or add/remove as in the old snippet (option 3)? options: 1 = insert/removeSmallest/peekSmallest, 2 = push/pop/peek, 3 = add/remove recommendation: 1 ``` next: waiting (owner decision)

orion referenced this issue

2026-10-08 13:52:25 +00:00

feat(std/collections): add RingList, a List with O(1) at both ends #201

orion commented

2026-10-08 14:36:19 +00:00

Author

Collaborator

[loop:torbscript] owner decision recorded (torben via WhatsApp, 2026-10-08 16:35 Europe/Berlin): "Ja okay" (option 1).

Resolution: Heap uses insert(value) / removeSmallest() / peekSmallest(); COLLECTIONS.md 3.4 snippet updated in the same PR. #200 labelled ready.

[loop:torbscript] owner decision recorded (torben via WhatsApp, 2026-10-08 16:35 Europe/Berlin): "Ja okay" (option 1). Resolution: `Heap` uses `insert(value)` / `removeSmallest()` / `peekSmallest()`; COLLECTIONS.md 3.4 snippet updated in the same PR. #200 labelled `ready`.

orion referenced this issue

2026-10-08 14:36:19 +00:00

collections: Heap, a priority structure ordered by a key (C7) #200

orion commented

2026-10-08 17:48:53 +00:00

Author

Collaborator

[question-closed] q=q1 reason=answered-elsewhere

orion commented

2026-10-09 06:50:47 +00:00

Author

Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261009 until 2026-10-09T12:50Z

#197 to #200 are closed and merged, but the C7 paragraph of COLLECTIONS.md still reads "Built so far: RingList" and is not marked Done. A docs-only PR closes that.

[loop:torbscript] claim implement by session:loop-torbscript-20261009 until 2026-10-09T12:50Z #197 to #200 are closed and merged, but the C7 paragraph of COLLECTIONS.md still reads "Built so far: RingList" and is not marked Done. A docs-only PR closes that.

orion referenced this issue from a pull request that will close it,

2026-10-09 06:51:35 +00:00

docs: mark C7 done #256

argus closed this issue

2026-10-09 07:33:03 +00:00

orion commented

2026-10-09 07:33:14 +00:00

Author

Collaborator

[loop:torbscript] implement: PR #256 open, CI green (a47e171a), next: review (waiting on the merge gate argus)

[loop:torbscript] implement: PR https://git.torb.dev/torbscript/language/pulls/256 open, CI green (a47e171a), next: review (waiting on the merge gate argus)

orion commented

2026-10-09 07:33:18 +00:00

Author

Collaborator

[loop:torbscript] close: correction to the comment above, PR #256 is already merged by argus (merge commit b1d76a4f). All four C7 types landed and COLLECTIONS.md C7 reads Done; #212 stays open as the known literal gap. Issue closed.

[loop:torbscript] close: correction to the comment above, PR #256 is already merged by argus (merge commit b1d76a4f). All four C7 types landed and COLLECTIONS.md C7 reads Done; #212 stays open as the known literal gap. Issue closed.

Rows
Columns

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

Goal

Acceptance criteria

Design record

Seed impact

Dependencies

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