# Collections Consistency -- TRD

## Status

Proposed -- 2026-03-22

## Overview

The `common/` collections library has accumulated interface inconsistencies as implementations were added independently:

1. **List interface gaps.** `has()` and `delete()` were missing from the `List` interface even though SkipList already implemented them. ArrayList, LinkedList, and DoublyLinkedList had no way to check membership or do a boolean-returning index removal.
2. **Heap interface bloat.** `Heap` exposed both `has()` and `contains()` as aliases. Two names for one operation is confusing and inflates the API surface. Additionally, element search used linear scans instead of exploiting the heap ordering invariant.
3. **SkipList non-interface methods.** SkipList implemented `at()` and `forEach()`, which are not on the `List` interface. This created a leaky abstraction that encourages downcasting.
4. **SkipList capacity trap.** SkipList was the only `List` with a `capacity` concept. Constructing from an iterable silently locked capacity to the iterable's size, making subsequent `push()` calls throw. No other list behaves this way.
5. **SkipList index normalization drift.** SkipList used `toInteger`/`addIfBelow`/`isInRange` for index handling while all other lists use `wrapLeft` + `clamp`. This caused subtle behavioral differences for edge-case indices.

This TRD covers fixing all five issues to make the collections library internally consistent.

## Goals

- Every `List` implementation exposes the same public API -- no extra methods, no missing methods.
- A single membership-check name (`has()`) across both List and Heap hierarchies.
- SkipList behaves like other lists: no capacity, no surprise `RangeError`, same index normalization.
- Heap search operations leverage the heap property for comparator pruning instead of linear scans.
- Zero new runtime dependencies; all changes are within `common/`.

## Architecture

### Interface hierarchy

```
Collection<K, V>
  |
  +-- List<T> (Collection<number, T>, Sortable<T>)
  |     +-- ArrayList<T>
  |     +-- LinkedList<T>
  |     +-- DoublyLinkedList<T>
  |     +-- SkipList<T>
  |
  +-- Heap<T> (Collection<number, T>, Sorted<T>)
        +-- BinaryHeap<T>
        +-- SkewHeap<T>
```

### Changes at each level

| Level              | Change                                                                                                                                                                                                        |
| ------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `List` interface   | Add `has(value: T): boolean` and `delete(index: number): boolean`                                                                                                                                             |
| `ArrayList`        | Implement `has()` (delegates to `Array.includes`) and `delete()` (delegates to `Array.splice`)                                                                                                                |
| `LinkedList`       | Implement `has()` (linear traversal with `===`) and `delete()` (node unlinking)                                                                                                                               |
| `DoublyLinkedList` | Implement `has()` (linear traversal with `===`) and `delete()` (bidirectional node unlinking)                                                                                                                 |
| `SkipList`         | Remove `at()`, `forEach()`. Remove `capacity` concept entirely. Normalize index handling from `toInteger`/`addIfBelow`/`isInRange` to `wrapLeft`/`clamp`. Existing `has()` and `delete()` are retained as-is. |
| `Heap` interface   | Remove `contains()`. `has()` is the sole membership method.                                                                                                                                                   |
| `BinaryHeap`       | Remove `contains()`. Add `_find()` with DFS comparator pruning for `has()`, `delete()`, and `update()`.                                                                                                       |
| `SkewHeap`         | Remove `contains()`. Add `_findNode()` and `_findWithParent()` with recursive comparator pruning for `has()`, `delete()`, and `update()`.                                                                     |

## Detailed Design

### 1. List interface additions

**`has(value: T): boolean`** -- Checks whether `value` exists in the list using strict equality (`===`). Lists have no comparator, so identity comparison is the only sensible default.

**`delete(index: number): boolean`** -- Removes the element at `index` and returns `true` if the index was valid. Supports negative indices (same convention as `remove()`). This fills the gap where `remove()` returns `T | undefined` -- callers storing `undefined` values cannot distinguish "removed undefined" from "invalid index." `delete()` resolves this ambiguity.

### 2. Per-implementation details for `has()` and `delete()`

**ArrayList:** `has()` delegates to `Array.prototype.includes`. `delete()` uses `Array.prototype.splice` after bounds checking.

**LinkedList:** `has()` traverses from head using `===`. `delete()` traverses to the predecessor of the target index, then relinks `prev.next` to skip the target node. Updates `tail` if the last element is removed.

**DoublyLinkedList:** `has()` traverses from head using `===`. `delete()` traverses to the target node (choosing direction based on proximity to head/tail), then relinks `prev.next` and `next.prev`.

**SkipList:** Already has `has()` (linear scan of level-0 nodes) and `delete()`. No new implementation needed; only the index normalization fix (see below).

### 3. Heap `contains()` removal

The `Heap` interface currently defines both `has()` and `contains()`. In BinaryHeap, `has` delegated to `contains`. This TRD removes `contains()` entirely and makes `has()` the primary implementation. No deprecation alias is kept.

### 4. Heap comparator pruning

Both BinaryHeap and SkewHeap searched for elements using linear scans (`Array.some`, `Array.findIndex`, or full tree traversal). The heap property guarantees that children are "worse" than their parent. A search for element `X` can prune any subtree rooted at a node `N` where `compare(N, X) > 0`, because all of `N`'s descendants are even worse.

**BinaryHeap** -- `_find(element)`: Iterative DFS over the array-backed binary tree. Uses a stack. When `compare(array[i], element) > 0`, the children at `2i+1` and `2i+2` are skipped. Returns the index or `-1`. Used by `has()`, `delete()`, and `update()`.

**SkewHeap** -- `_findNode(node, element)`: Recursive DFS. Prunes when `compare(node.value, element) > 0`. Returns the matching node or `undefined`. Used by `has()`. `_findWithParent(element)`: Iterative DFS returning `{ parent, key }` so the caller can relink. Used by `delete()` and `update()`.

### 5. SkipList API cleanup

- Remove `at()` and `forEach()` -- not on the `List` interface.
- Normalize `delete()`, `fill()`, `slice()`, `splice()` index handling from `toInteger`/`addIfBelow`/`isInRange` to `wrapLeft` + `clamp`, matching ArrayList, LinkedList, and DoublyLinkedList.
- Rename `start`/`end` parameters to `min`/`max` where the interface uses those names.
- Remove unused imports (`addIfBelow`, `isInRange`, `toInteger`); add `wrapLeft`.

### 6. SkipList capacity removal

- Remove `_capacity` and `_isFinite` fields, `capacity` getter/setter, `capacity` from `SkipListConfig`.
- Remove `_insert()` (capacity-check wrapper). Rename `_safeInsert()` to `_insert()`.
- Remove `constructor(capacity?: number | null)` overload. Keep `constructor()`, `constructor(config)`, `constructor(items)`.
- Simplify `concat()`, `slice()`, `splice()` -- they no longer need to set capacity on returned lists.

## Alternatives Explored

### Fix the interface vs. remove the implementations

Removing the custom collections and using a third-party library (e.g., `mnemonist`, `denque`) was considered. Rejected because: (a) the implementations are well-tested and purpose-built for the project's needs, (b) third-party libraries would add a dependency for code that is stable and rarely changes, and (c) the inconsistencies are small and fixable without rewriting.

### Keep `contains()` as a deprecated alias

Rejected per project convention (see feedback: no deprecation shims). When renaming, old names are removed entirely. Consumers are updated in the same change.

### Add capacity to all lists instead of removing it from SkipList

Rejected. Capacity adds complexity (locking bugs, splice atomicity issues) for no demonstrated need. No consumer has ever required capacity on ArrayList or LinkedList. Removing it from SkipList is the simpler path to consistency.

## Cost Analysis

- **Engineering effort:** Small. Five tasks, each modifiable in a single session. Estimated 1-2 days total.
- **Infrastructure cost:** Zero. All changes are in the `common/` library package. No new services, no new dependencies.
- **Review cost:** Minimal. Each task is a focused, self-contained commit.

## Performance Analysis

### `has()` complexity by implementation

| Implementation      | Best | Average         | Worst |
| ------------------- | ---- | --------------- | ----- |
| ArrayList           | O(1) | O(n)            | O(n)  |
| LinkedList          | O(1) | O(n)            | O(n)  |
| DoublyLinkedList    | O(1) | O(n)            | O(n)  |
| SkipList            | O(1) | O(n)            | O(n)  |
| BinaryHeap (pruned) | O(1) | O(n)\*          | O(n)  |
| SkewHeap (pruned)   | O(1) | O(log n) pruned | O(n)  |

\*BinaryHeap `has()` worst case is unchanged at O(n), but comparator pruning skips subtrees where elements are "worse" than the target, yielding sub-linear performance in practice for elements near the top.

### `delete()` complexity by implementation

| Implementation   | Best | Average  | Worst |
| ---------------- | ---- | -------- | ----- |
| ArrayList        | O(1) | O(n)     | O(n)  |
| LinkedList       | O(1) | O(n)     | O(n)  |
| DoublyLinkedList | O(1) | O(n)     | O(n)  |
| SkipList         | O(1) | O(log n) | O(n)  |

List `delete()` has the same complexity as the existing `remove()` method -- the only difference is the return type (`boolean` vs `T | undefined`).

## Scaling Characteristics

Not applicable. This is library code within `common/`. It scales with usage -- no infrastructure, no network calls, no storage. The data structures scale with the number of elements stored, which is bounded by the caller's use case.

## Breakdown Points & Mitigations

### Breaking consumers of `contains()` on Heap

**Risk:** Any code calling `.contains()` on a BinaryHeap or SkewHeap will fail to compile after the change.

**Mitigation:** A codebase-wide search-and-replace of `.contains(` to `.has(` in all consumers is performed in the same commit. The `Heap` interface enforces this at compile time -- any missed call site will be a TypeScript error, not a runtime surprise.

### Breaking consumers of `at()` or `forEach()` on SkipList

**Risk:** Code that downcasts to `SkipList` and calls `at()` or `forEach()` will break.

**Mitigation:** Same approach -- search-and-replace in the same commit. `at(index)` is replaced with `get(index)` (equivalent behavior). `forEach()` is replaced with a `for...of` loop. TypeScript compilation catches any missed sites.

### Breaking consumers of SkipList `capacity`

**Risk:** Code that sets or reads `.capacity` will break.

**Mitigation:** Search for all references to `.capacity` on SkipList instances and remove them. The most common pattern -- constructing from an iterable and then pushing -- will now work correctly instead of throwing.

## Decision Log

| Date       | Decision                                                    | Rationale                                                                                                                                                   |
| ---------- | ----------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------- |
| 2026-03-21 | Use `===` for List `has()`, not a comparator                | Lists are unordered-by-comparator. Adding a comparator parameter would diverge from the simple, predictable behavior of `Array.includes`.                   |
| 2026-03-21 | Return `boolean` from List `delete()`, not `T \| undefined` | `remove()` already returns `T \| undefined`. A second method with the same return type adds no value. `boolean` resolves the `undefined`-element ambiguity. |
| 2026-03-21 | Remove `contains()` with no deprecation shim                | Project convention: no deprecated aliases. Clean break.                                                                                                     |
| 2026-03-21 | Remove SkipList capacity entirely                           | No other List has it. The locking behavior was a trap, not a feature.                                                                                       |

## Dependencies

- No external dependencies.
- Internal dependency: all changes are within the `common/` package. Consumers in `server/` and elsewhere will need recompilation but no code changes (except replacing `contains()` calls).

## Testing Strategy

Each task includes tests in the corresponding `common/src/__tests__/collections/` directory.

**List `has()` tests** (ArrayList, LinkedList, DoublyLinkedList, SkipList):

- Returns `false` on empty list
- Returns `false` when value is not present
- Returns `true` when value is present (first, last, middle)
- Uses strict equality -- `has(1)` returns `true` but `has("1" as any)` returns `false`

**List `delete()` tests** (ArrayList, LinkedList, DoublyLinkedList, SkipList):

- Returns `false` on empty list
- Returns `false` for out-of-bounds index (positive and negative)
- Returns `true` and removes first, middle, last elements
- Supports negative indices
- Works with `undefined` values in the list

**Heap `has()` tests** (BinaryHeap, SkewHeap):

- Existing `contains()` test suites renamed to `has()` -- same coverage, new method name

**SkipList cleanup tests:**

- Remove `at()` and `forEach()` test blocks
- Remove all capacity-related tests (capacity locking, numeric capacity constructor, `RangeError` overflow)
- Add test confirming `push()` works after iterable construction (the former trap case)

**Verification command:**

```bash
cd common && npx jest --testPathPattern='collections/' --verbose
```

## Rollout Plan

All changes are internal to `common/` and ship as a single version bump of the `@coda/common` package.

1. **Task 1:** Add `has()` and `delete()` to the List interface and implement on ArrayList, LinkedList, DoublyLinkedList. Commit.
2. **Task 2:** SkipList API cleanup -- remove `at()`/`forEach()`, normalize index handling. Commit.
3. **Task 3:** Remove SkipList capacity entirely. Commit.
4. **Task 4:** Remove `contains()` from Heap interface and BinaryHeap; add comparator pruning. Commit.
5. **Task 5:** Remove `contains()` from SkewHeap; add comparator pruning. Run full collection test suite. Commit.
6. **PR:** Single PR with all five commits. Merge to master.

No feature flag needed. No staged rollout. The changes are compile-time enforced -- if it builds, it works.

## Open Questions

None. The plan is fully specified and all design decisions have been made.