# @crimson-carnival/ds-js

Production-ready data structures written in TypeScript — zero dependencies, tree-shakeable, fully tested.

[![npm version](https://img.shields.io/npm/v/@crimson-carnival/ds-js)](https://www.npmjs.com/package/@crimson-carnival/ds-js)
[![License: MIT](https://img.shields.io/badge/License-MIT-blue.svg)](./LICENSE)
[![Tests](https://img.shields.io/badge/tests-178%20passed-brightgreen)](#testing)

## Features

- **9 data structures** — from linked lists to graphs
- **TypeScript-first** — full generics, `.d.ts` declarations included
- **Zero dependencies** — no runtime deps, no bloat
- **Dual format** — ESM and CJS bundles via `tsup`
- **Tree-shakeable** — import only what you need
- **178 unit tests** — comprehensive `vitest` coverage

## Install

```bash
npm install @crimson-carnival/ds-js
```

```bash
pnpm add @crimson-carnival/ds-js
```

```bash
yarn add @crimson-carnival/ds-js
```

<details open>
<summary><strong>TypeScript</strong></summary>

```typescript
import { Stack, Queue, Deque, PriorityQueue, Graph, AVLTree, LRUCache } from '@crimson-carnival/ds-js'

// Stack — LIFO
const stack = new Stack<number>()
stack.push(1); stack.push(2)
stack.pop()   // → 2

// Queue — FIFO
const queue = new Queue<string>()
queue.enqueue('first'); queue.enqueue('second')
queue.dequeue()  // → 'first'

// Deque — double-ended, O(1) at both ends
const deque = new Deque<number>()
deque.pushFront(1); deque.pushBack(2)
deque.popFront()  // → 1
deque.popBack()   // → 2

// AVL Tree — self-balancing BST
const tree = new AVLTree<number>()
;[5, 3, 7, 1, 9].forEach(v => tree.insert(v))
tree.inOrder()  // → [1, 3, 5, 7, 9]
tree.search(7)  // → true

// PriorityQueue — min-heap; stable FIFO tiebreaking
interface Patient { name: string; priority: number }
const hospital = new PriorityQueue<Patient>(
  (a, b) => a.priority - b.priority,
  { stable: true }     // equal-priority → insertion order
)
hospital.enqueue({ name: 'Ana',  priority: 2 })
hospital.enqueue({ name: 'Luis', priority: 1 })  // critical
hospital.enqueue({ name: 'Eva',  priority: 2 })
hospital.dequeue()?.name  // → 'Luis'
hospital.dequeue()?.name  // → 'Ana'   (FIFO)
hospital.dequeue()?.name  // → 'Eva'   (FIFO)

// LRU Cache — fixed-capacity O(1) key-value store
const cache = new LRUCache<string, number>(3)
cache.put('a', 1); cache.put('b', 2); cache.put('c', 3)
cache.put('d', 4)  // evicts 'a' (least recently used)
cache.get('a')     // → undefined
cache.get('b')     // → 2

// Graph — adjacency-list, directed or undirected
const g = new Graph<string>(false)  // undirected
g.addEdge('A', 'B'); g.addEdge('A', 'C'); g.addEdge('B', 'D')
g.bfs('A')  // → ['A', 'B', 'C', 'D']
g.dfs('A')  // → ['A', 'B', 'D', 'C']
```

</details>

<details>
<summary><strong>JavaScript</strong></summary>

```javascript
import { Stack, Queue, Deque, PriorityQueue, Graph, AVLTree, LRUCache } from '@crimson-carnival/ds-js'

// Stack — LIFO
const stack = new Stack()
stack.push(1); stack.push(2)
stack.pop()   // → 2

// Queue — FIFO
const queue = new Queue()
queue.enqueue('first'); queue.enqueue('second')
queue.dequeue()  // → 'first'

// Deque — double-ended, O(1) at both ends
const deque = new Deque()
deque.pushFront(1); deque.pushBack(2)
deque.popFront()  // → 1
deque.popBack()   // → 2

// AVL Tree — self-balancing BST
const tree = new AVLTree()
;[5, 3, 7, 1, 9].forEach(v => tree.insert(v))
tree.inOrder()  // → [1, 3, 5, 7, 9]
tree.search(7)  // → true

// PriorityQueue — min-heap; stable FIFO tiebreaking
const hospital = new PriorityQueue(
  (a, b) => a.priority - b.priority,
  { stable: true }     // equal-priority → insertion order
)
hospital.enqueue({ name: 'Ana',  priority: 2 })
hospital.enqueue({ name: 'Luis', priority: 1 })  // critical
hospital.enqueue({ name: 'Eva',  priority: 2 })
hospital.dequeue().name  // → 'Luis'
hospital.dequeue().name  // → 'Ana'   (FIFO)
hospital.dequeue().name  // → 'Eva'   (FIFO)

// LRU Cache — fixed-capacity O(1) key-value store
const cache = new LRUCache(3)
cache.put('a', 1); cache.put('b', 2); cache.put('c', 3)
cache.put('d', 4)  // evicts 'a' (least recently used)
cache.get('a')     // → undefined
cache.get('b')     // → 2

// Graph — adjacency-list, directed or undirected
const g = new Graph(false)  // undirected
g.addEdge('A', 'B'); g.addEdge('A', 'C'); g.addEdge('B', 'D')
g.bfs('A')  // → ['A', 'B', 'C', 'D']
g.dfs('A')  // → ['A', 'B', 'D', 'C']
```

</details>

---

## API Reference

### DoublyLinkedList\<T\>

A doubly linked list with O(1) insertion and removal at both ends. Foundation for Stack, Queue, Deque, and LRU Cache.

```typescript
import { DoublyLinkedList } from '@crimson-carnival/ds-js'
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `push(value)` | `this` | O(1) |
| `pop()` | `T \| undefined` | O(1) |
| `unshift(value)` | `this` | O(1) |
| `shift()` | `T \| undefined` | O(1) |
| `get(index)` | `Node<T>` | O(n) |
| `set(index, value)` | `void` | O(n) |
| `insert(index, value)` | `void` | O(n) |
| `remove(index)` | `T` | O(n) |
| `removeNode(node)` | `T` | O(1) |
| `findNode(predicate)` | `Node<T> \| undefined` | O(n) |
| `find(predicate)` | `T \| undefined` | O(n) |
| `indexOf(value)` | `number` | O(n) |
| `contains(value)` | `boolean` | O(n) |
| `toArray()` | `T[]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |
| `[Symbol.iterator]()` | `Iterator<T>` | O(n) |

---

### Stack\<T\>

LIFO stack backed by DoublyLinkedList.

```typescript
import { Stack } from '@crimson-carnival/ds-js'
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `push(value)` | `void` | O(1) |
| `pop()` | `T \| undefined` | O(1) |
| `peek()` | `T \| undefined` | O(1) |
| `toArray()` | `T[]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |

---

### Queue\<T\>

FIFO queue backed by DoublyLinkedList with task cancellation support.

```typescript
import { Queue } from '@crimson-carnival/ds-js'
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `enqueue(value)` | `void` | O(1) |
| `dequeue()` | `T \| undefined` | O(1) |
| `peek()` | `T \| undefined` | O(1) |
| `cancel(predicate)` | `boolean` | O(n) |
| `positionOf(predicate)` | `number \| undefined` | O(n) |
| `toArray()` | `T[]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |

---

### Deque\<T\>

Double-ended queue — insert and remove from both ends in O(1).

```typescript
import { Deque } from '@crimson-carnival/ds-js'
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `pushBack(value)` | `void` | O(1) |
| `pushFront(value)` | `void` | O(1) |
| `popBack()` | `T \| undefined` | O(1) |
| `popFront()` | `T \| undefined` | O(1) |
| `peekBack()` | `T \| undefined` | O(1) |
| `peekFront()` | `T \| undefined` | O(1) |
| `toArray()` | `T[]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |
| `[Symbol.iterator]()` | `Iterator<T>` | O(n) |

---

### LRUCache\<K, V\>

Least Recently Used cache with fixed capacity. Combines a DoublyLinkedList (access order) with a Map (O(1) key lookup). When full, the least recently used entry is evicted automatically.

```typescript
import { LRUCache } from '@crimson-carnival/ds-js'
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `get(key)` | `V \| undefined` | O(1) |
| `put(key, value)` | `void` | O(1) |
| `has(key)` | `boolean` | O(1) |
| `delete(key)` | `boolean` | O(1) |
| `entries()` | `[K, V][]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |
| `capacity` | `number` | O(1) |

---

### PriorityQueue\<T\>

Min-heap based priority queue. The element with the highest priority (smallest value by default) is always dequeued first.

Supports an optional **`stable`** mode that guarantees FIFO ordering among elements with equal priority — ideal for scheduling, hospital triage, and task queues.

```typescript
import { PriorityQueue } from '@crimson-carnival/ds-js'

// Default min-heap
const pq = new PriorityQueue<number>()
pq.enqueue(5); pq.enqueue(1); pq.enqueue(3)
pq.dequeue()  // → 1

// Custom comparator (max-heap)
const maxHeap = new PriorityQueue<number>((a, b) => b - a)

// Stable mode — FIFO tiebreaking when priorities are equal
interface Task { label: string; priority: number }
const queue = new PriorityQueue<Task>(
  (a, b) => a.priority - b.priority,
  { stable: true }
)
```

| Method / Getter | Returns | Complexity |
|----------------|---------|------------|
| `enqueue(value)` | `void` | O(log n) |
| `dequeue()` | `T \| undefined` | O(log n) |
| `peek()` | `T \| undefined` | O(1) |
| `toArray()` | `T[]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |
| `stable` | `boolean` | O(1) |

---

### AVLTree\<T\>

Self-balancing binary search tree. Guarantees O(log n) insert, search, and delete by maintaining height balance (|left.height − right.height| ≤ 1) via rotations.

```typescript
import { AVLTree } from '@crimson-carnival/ds-js'

// Custom comparator
const tree = new AVLTree<{ id: number }>((a, b) => a.id - b.id)
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `insert(value)` | `void` | O(log n) |
| `search(value)` | `boolean` | O(log n) |
| `delete(value)` | `boolean` | O(log n) |
| `min()` | `T \| undefined` | O(log n) |
| `max()` | `T \| undefined` | O(log n) |
| `inOrder()` | `T[]` | O(n) |
| `preOrder()` | `T[]` | O(n) |
| `postOrder()` | `T[]` | O(n) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |

---

### Trie

Prefix tree optimized for string operations — autocomplete, spell-checking, prefix search.

```typescript
import { Trie } from '@crimson-carnival/ds-js'
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `insert(word)` | `void` | O(L) |
| `search(word)` | `boolean` | O(L) |
| `startsWith(prefix)` | `boolean` | O(L) |
| `delete(word)` | `boolean` | O(L) |
| `wordsWithPrefix(prefix)` | `string[]` | O(L + k) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `size` | `number` | O(1) |

> **L** = word/prefix length, **k** = total characters in matching results

---

### Graph\<T\>

Weighted adjacency-list graph with BFS and DFS traversals. Supports both directed and undirected modes.

```typescript
import { Graph } from '@crimson-carnival/ds-js'

const graph = new Graph<string>(false)  // undirected
graph.addEdge('A', 'B', 5)
graph.addEdge('B', 'C', 3)
graph.bfs('A')  // → ['A', 'B', 'C']
```

| Method | Returns | Complexity |
|--------|---------|------------|
| `addVertex(v)` | `void` | O(1) |
| `removeVertex(v)` | `boolean` | O(V + E) |
| `addEdge(u, v, weight?)` | `void` | O(1) |
| `removeEdge(u, v)` | `boolean` | O(1) |
| `hasVertex(v)` | `boolean` | O(1) |
| `hasEdge(u, v)` | `boolean` | O(1) |
| `neighbors(v)` | `T[]` | O(deg v) |
| `weight(u, v)` | `number \| undefined` | O(1) |
| `bfs(start)` | `T[]` | O(V + E) |
| `dfs(start)` | `T[]` | O(V + E) |
| `clear()` | `void` | O(1) |
| `isEmpty()` | `boolean` | O(1) |
| `vertexCount` | `number` | O(1) |
| `edgeCount` | `number` | O(1) |
| `directed` | `boolean` | O(1) |

---

## Complexity Overview

| Structure | Insert | Delete | Search/Access | Space |
|-----------|--------|--------|---------------|-------|
| DoublyLinkedList | O(1)* | O(1)* | O(n) | O(n) |
| Stack | O(1) | O(1) | O(n) | O(n) |
| Queue | O(1) | O(1) | O(n) | O(n) |
| Deque | O(1) | O(1) | O(n) | O(n) |
| LRU Cache | O(1) | O(1) | O(1) | O(n) |
| Priority Queue | O(log n) | O(log n) | O(1)† | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(n) |
| Trie | O(L) | O(L) | O(L) | O(Σ L) |
| Graph | O(1) | O(V+E) | O(1) | O(V+E) |

\* At head/tail. By index is O(n).  
† Peek only. Arbitrary access is O(n).

## Testing

```bash
npm test             # run all 178 tests
npm run test:watch   # watch mode
npm run test:lru     # run a single suite
```

## Building

```bash
npm run build        # ESM + CJS + .d.ts
```

## License

[MIT](./LICENSE)