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

orion commented

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

Collaborator

Goal

Heap<Item>: the priority structure of COLLECTIONS.md section 3.4. It is not a Queue and has no trait; the ordering is a value it carries (Heap.by { _.priority }). The record still calls it Ordered in the snippet and in the C7 text; the owner renamed it to Heap on 2026-09-23 (section 6, question 4). Open: the member words (see the owner decision on #139), so this issue is not ready until it is answered.

Acceptance criteria

public type Heap<Item> over a List as a binary heap, built with Heap.by(key), O(log n) insert/take-smallest, O(1) peek.
Iteration order and length/clear decided with the member words.
The stale Ordered/Collection snippet in COLLECTIONS.md section 3.4 and the C7 text updated in the same PR.
Conformance program (ties, empty, many items against a sorted list); benchmark against List.sort.

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 `Heap<Item>`: the priority structure of COLLECTIONS.md section 3.4. It is not a `Queue` and has no trait; the ordering is a value it carries (`Heap.by { _.priority }`). The record still calls it `Ordered` in the snippet and in the C7 text; the owner renamed it to `Heap` on 2026-09-23 (section 6, question 4). Open: the member words (see the owner decision on #139), so this issue is **not ready** until it is answered. ## Acceptance criteria - [ ] `public type Heap<Item>` over a `List` as a binary heap, built with `Heap.by(key)`, O(log n) insert/take-smallest, O(1) peek. - [ ] Iteration order and `length`/`clear` decided with the member words. - [ ] The stale `Ordered`/`Collection` snippet in COLLECTIONS.md section 3.4 and the C7 text updated in the same PR. - [ ] Conformance program (ties, empty, many items against a sorted list); benchmark against `List.sort`. ## 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

label

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

orion referenced this issue

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

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

orion referenced this issue

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

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

orion referenced this issue

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

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

orion added the

ready

label

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

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): member words insert / removeSmallest / peekSmallest (see #139). Labelled ready.

[loop:torbscript] owner decision recorded (torben via WhatsApp, 2026-10-08 16:35 Europe/Berlin): member words `insert` / `removeSmallest` / `peekSmallest` (see #139). Labelled `ready`.

orion commented

2026-10-08 15:10:10 +00:00

Author

Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261008 until 2026-10-08T21:10Z

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

2026-10-08 15:14:49 +00:00

feat(collections): add Heap, a binary heap with insert, removeSmallest and peekSmallest #210

orion commented

2026-10-08 16:35:33 +00:00

Author

Collaborator

[loop:torbscript] review: the fix round for the merge gate's findings is pushed to PR #210 (1c95dea, review re-requested), CI is running, next: waiting (merge gate review on PR #210)

[loop:torbscript] review: the fix round for the merge gate's findings is pushed to PR #210 (1c95dea, review re-requested), CI is running, next: waiting (merge gate review on PR #210)