# Collections

Generic, iterable data structures that all implement the `Collection<T>` interface. Every collection is fully typed and zero-dependency.

## Interface Hierarchy

```
Collection<T>                         Base — size, clear, values, [Symbol.iterator]
├── Queue<T>                          FIFO — enqueue, dequeue, peekFirst
├── Stack<T>                          LIFO — push, pop, peekLast
├── Deque<T>                          Both ends — extends Queue + Stack + pushFront
├── Heap<T>                           Priority queue — push, pop, peek, pushPop, ...
└── Keyed<K, V>                       Addressable keys — entries, keys
      └── ReadonlyGraph<K, N, E>      Directed graph — nodes, edges, neighbors
            └── Graph<K, N, E>        Mutable — addNode, addEdge, removeNode
```

## Capability Traits

Traits are standalone interfaces that implementations adopt independently. A class can implement any combination.

| Trait           | Meaning                                    | Guarantees                                     | Example                                     |
| :-------------- | :----------------------------------------- | :--------------------------------------------- | :------------------------------------------ |
| `Reversible<T>` | Supports in-place `reverse()`              | After `reverse()`, iteration order is reversed | `LinkedDeque`, `LinkedQueue`, `LinkedStack` |
| `Keyed<K, V>`   | Elements have meaningful, addressable keys | `entries()` and `keys()` available             | `AdjacencyGraph`                            |

### Collection vs Keyed

- **`Collection<T>`** — Universal base. Single type parameter — just values. All data structures implement this. Provides `size`, `clear()`, `values()`, and `[Symbol.iterator]`.

- **`Keyed<K, V>`** — Extension for structures where elements have meaningful keys. Adds `entries()` and `keys()`. Graphs use this (`Keyed<NodeId, GraphNode>`). Sequential structures (queues, stacks, heaps, deques) do **not** — their elements are accessed via domain-specific operations, not by key.

## Overview

| Category         | Implementations             | Interface      | Key Operations                                                            |
| :--------------- | :-------------------------- | :------------- | :------------------------------------------------------------------------ |
| [Heaps](heap/)   | `BinaryHeap`, `SkewHeap`    | `Heap<T>`      | `push`, `pop`, `peek`, `pushPop`, `popPush`, `has`, `delete`, `update`    |
| [Queues](queue/) | `ArrayQueue`, `LinkedQueue` | `Queue<T>`     | `enqueue`, `dequeue`, `peekFirst`                                         |
| [Stacks](stack/) | `ArrayStack`, `LinkedStack` | `Stack<T>`     | `push`, `pop`, `peekLast`                                                 |
| [Deques](deque/) | `ArrayDeque`, `LinkedDeque` | `Deque<T>`     | `push`, `pop`, `pushFront`, `dequeue`, `enqueue`, `peekFirst`, `peekLast` |
| Graph            | `AdjacencyGraph`            | `Graph<K,N,E>` | `addNode`, `addEdge`, `removeNode`, `removeEdges`, `inEdges`, `outEdges`  |

See each subdirectory's README for complexity tables, strengths/weaknesses, and "Which to use" guidance.

## Quick Reference

### "I need a priority queue"

**BinaryHeap** for general use. **SkewHeap** when you frequently merge heaps.

### "I need a FIFO queue"

**LinkedQueue** — O(1) enqueue and dequeue. ArrayQueue has O(n) dequeue.

### "I need a LIFO stack"

**ArrayStack** — cache-friendly, amortized O(1). LinkedStack only for guaranteed worst-case O(1).

### "I need both ends"

**LinkedDeque** — O(1) on all four endpoint operations. ArrayDeque has O(n) front operations.

### "I need a graph"

**AdjacencyGraph** — directed multigraph with typed nodes and edges, O(1) node lookup.

## Type Guards

```typescript
import { isCollection, isKeyed } from '@coda/data-structures';

isCollection(new BinaryHeap(...));    // true — all collections
isCollection(new LinkedQueue());      // true
isCollection(new AdjacencyGraph());   // true
isCollection([1, 2, 3]);             // false — no clear()

isKeyed(new AdjacencyGraph());        // true — has entries()/keys()
isKeyed(new BinaryHeap(...));         // false — no entries()/keys()
isKeyed(new Map());                   // true — native Map is keyed
```