@absoluteui/helpers/ds

Data structures: queues, heaps, caches, sorted maps, tries, graphs, interval trees, and more.

import { ... } from '@absoluteui/helpers/ds';

How to use

Data structures that JavaScript lacks, with documented complexity: graphs with cycle detection and shortest paths, interval trees for overlaps, tries for prefix search, heaps and priority queues, bounded caches, sorted maps, queues, and more. Reach for one when an array or Map would make an operation linear (or quadratic) at your data size, such as checking every booking against every other. All algorithms are iterative, so large inputs cannot overflow the stack. Conventions are in the Helpers and services guide.

How do I stop a reporting-line change from creating a loop?

Model “reports to” as a directed graph. Before saving a change, add the edge to a copy and ask findCycle; topologicalSort gives an order in which every manager comes before their reports.

import { Graph } from '@absoluteui/helpers/ds';

const reportsTo: [string, string][] = [['CEO', 'CFO'], ['CFO', 'Payroll Lead'], ['Payroll Lead', 'Asha']];
const org = new Graph<string>();
for (const [manager, report] of reportsTo) org.addEdge(manager, report);
org.topologicalSort(); // => ['CEO', 'CFO', 'Payroll Lead', 'Asha']

const proposed = new Graph<string>();
for (const [from, to] of org.edges()) proposed.addEdge(from, to);
proposed.addEdge('Asha', 'CFO'); // Asha would manage the CFO
proposed.hasCycle(); // => true
proposed.findCycle(); // => ['CFO', 'Payroll Lead', 'Asha'] // each manages the next, and the last manages the first

How do I find overlapping bookings or shifts?

Store each interval once in an IntervalTree; search returns everything that overlaps a range in O(log n + k). With bounds: '[)', a shift ending at 14:00 does not clash with one starting at 14:00.

import { IntervalTree } from '@absoluteui/helpers/ds';

const at = (hhmm: string) => Date.parse(`2026-10-05T${hhmm}:00Z`);
const room = new IntervalTree<string>({ bounds: '[)' });
room.insert(at('09:00'), at('10:00'), 'Stand-up');
room.insert(at('10:00'), at('12:00'), 'Payroll review');
room.insert(at('13:00'), at('14:00'), 'Interview');

room.search(at('11:30'), at('13:30')).map((e) => e.value); // => ['Payroll review', 'Interview']
room.overlaps(at('12:00'), at('13:00')); // => false // the free slot
room.searchPoint(at('10:00')).map((e) => e.value); // => ['Payroll review']

How do I autocomplete names from a large list?

A Trie answers prefix queries without scanning the list; caseFold: true makes matching case-insensitive, and limit caps the suggestions. countPrefix tells you how many matches exist beyond the ones you show.

import { Trie } from '@absoluteui/helpers/ds';

const names = new Trie(['Asha Rao', 'Ashok Kumar', 'Aisha Khan', 'Liam Chen', 'asher Cole'], { caseFold: true });
names.findByPrefix('ash', 2).length; // => 2
names.countPrefix('ASH'); // => 3
names.startsWith('li'); // => true
names.has('liam chen'); // => true

How do I work through tickets by deadline?

A PriorityQueue always gives you the item that sorts first by your comparer, in O(log n) per push and pop, instead of re-sorting an array on every insert.

import { PriorityQueue } from '@absoluteui/helpers/ds';

interface Ticket { id: string; dueAt: string }
const queue = new PriorityQueue<Ticket>([], (a, b) => a.dueAt.localeCompare(b.dueAt));
queue.push({ id: 'HR-12', dueAt: '2026-10-07T17:00:00Z' });
queue.push({ id: 'HR-9', dueAt: '2026-10-05T09:00:00Z' });
queue.push({ id: 'HR-15', dueAt: '2026-10-06T12:00:00Z' });
queue.pop()?.id; // => 'HR-9'
[...queue.drain()].map((t) => t.id); // => ['HR-15', 'HR-12']

For deadlines in business hours (weekends and holidays excluded), compute dueAt with @absoluteui/helpers/business-calendar first.

How do I keep a bounded cache and a recent-activity list?

LRUCache evicts the least recently used entry when full and can expire entries (ttlMs); onEvict tells you why an entry went. CircularBuffer keeps the last N items, overwriting the oldest.

import { CircularBuffer, LRUCache } from '@absoluteui/helpers/ds';

const evicted: string[] = [];
const profiles = new LRUCache<string, { name: string }>({ maxSize: 2, ttlMs: 60_000, onEvict: (key, _v, reason) => evicted.push(`${key}:${reason}`) });
profiles.set('E-1', { name: 'Asha Rao' }).set('E-2', { name: 'Liam Chen' });
profiles.get('E-1');
profiles.set('E-3', { name: 'Zoë Müller' });
evicted; // => ['E-2:capacity']
[...profiles.keys()]; // => ['E-1', 'E-3']

const recent = new CircularBuffer<string>(3);
for (const action of ['login', 'view payslip', 'edit address', 'logout']) recent.push(action);
recent.toArray(); // => ['view payslip', 'edit address', 'logout']

What goes wrong?

Structures fail loudly instead of returning wrong answers: a topological sort of a cyclic graph throws (with the cycle in details.cycle), a BiMap refuses a second key for the same value, and changing a SortedMap while iterating it throws.

import { BiMap, Graph, SortedMap, naturalCompare } from '@absoluteui/helpers/ds';

new Graph<string>().addEdge('a', 'b').addEdge('b', 'a').topologicalSort(); // => throws HLP_DS_GRAPH_CYCLE
new BiMap([['E-1', 'asha@example.com']]).set('E-2', 'asha@example.com'); // => throws HLP_DS_BIMAP_DUPLICATE_VALUE
const m = new SortedMap<number, string>([[1, 'a'], [2, 'b']]);
(() => { for (const [k] of m) m.set(k + 10, 'x'); })(); // => throws HLP_DS_CONCURRENT_MODIFICATION
naturalCompare(1, '1'); // => throws HLP_DS_NOT_COMPARABLE

API reference

Bitset

Classes

BitSet

Growable bit set on a Uint32Array. size is the number of set bits. Complexity: set, clear(i), has, toggle O(1) amortized; count, set algebra, iteration O(words).

class BitSet implements Iterable<number> {
  constructor(capacity?: number);
  static from(indexes: Iterable<number>): BitSet;
  get capacity(): number;
  get size(): number;
  set(index: number): this;
  clear(index?: number): this;
  has(index: number): boolean;
  toggle(index: number): boolean;
  count(): number;
  union(other: BitSet): BitSet;
  intersect(other: BitSet): BitSet;
  difference(other: BitSet): BitSet;
  xor(other: BitSet): BitSet;
  equals(other: BitSet): boolean;
  clone(): BitSet;
  toArray(): number[];
  [Symbol.iterator](): Iterator<number>;
}

Example:

const b = new BitSet();
b.set(3).set(64);
b.has(3);         // => true
[...b];           // => [3, 64]
b.union(BitSet.from([1])).toArray(); // => [1, 3, 64]

Bloom

Classes

BloomFilter

Probabilistic set membership: has may return false positives at about the configured rate, never false negatives. Sized from expected items and target rate; hashing is FNV-1a and MurmurHash3 combined by double hashing (not cryptographic; do not use against adversarial inputs for security decisions). Complexity: add, has O(k) with k hash functions; memory m bits. Not iterable: a Bloom filter cannot list its items.

class BloomFilter<T = string> {
  readonly bits: number;
  readonly hashCount: number;
  constructor(options: BloomFilterOptions<T>);
  get size(): number;
  add(item: T): this;
  has(item: T): boolean;
  estimatedFalsePositiveRate(): number;
  clear(): void;
}

Example:

const seen = new BloomFilter<string>({ expectedItems: 10_000, falsePositiveRate: 0.001 });
seen.add('alice@example.com');
seen.has('alice@example.com'); // => true
seen.has('bob@example.com');   // => false // almost certainly

Interfaces

BloomFilterOptions

interface BloomFilterOptions<T> {
  readonly expectedItems: number;
  readonly falsePositiveRate?: number;
  readonly key?: (item: T) => string | Uint8Array;
}

Caches

Classes

LFUCache

Least-frequently-used cache with O(1) operations (frequency buckets in a linked list; ties broken by least recent use within a bucket). Complexity: get, set, has, peek, delete O(1); iteration O(n).

class LFUCache<K, V> implements Iterable<[K, V]> {
  readonly maxSize: number;
  constructor(options: LFUCacheOptions<K, V>);
  get size(): number;
  get(key: K): V | undefined;
  peek(key: K): V | undefined;
  has(key: K): boolean;
  frequency(key: K): number;
  set(key: K, value: V): this;
  delete(key: K): boolean;
  clear(): void;
  toArray(): [K, V][];
  [Symbol.iterator](): Iterator<[K, V]>;
}

Example:

const c = new LFUCache<string, number>({ maxSize: 2 });
c.set('a', 1).set('b', 2);
c.get('a'); c.get('a');
c.set('c', 3); // evicts 'b' (used least)

LRUCache

Least-recently-used cache on an insertion-ordered Map. Complexity: get, set, has, peek, delete O(1); prune and iteration O(n). Iteration runs least to most recently used and skips expired entries.

class LRUCache<K, V> implements Iterable<[K, V]> {
  readonly maxSize: number;
  constructor(options?: LRUCacheOptions<K, V>);
  get size(): number;
  get(key: K): V | undefined;
  peek(key: K): V | undefined;
  has(key: K): boolean;
  set(key: K, value: V, options?: { readonly ttlMs?: number; }): this;
  delete(key: K): boolean;
  clear(): void;
  prune(): number;
  keys(): Generator<K>;
  values(): Generator<V>;
  toArray(): [K, V][];
  [Symbol.iterator](): Iterator<[K, V]>;
}

Example:

const c = new LRUCache<string, number>({ maxSize: 2 });
c.set('a', 1).set('b', 2);
c.get('a');
c.set('c', 3); // evicts 'b'

TTLCache

Cache whose entries expire after a per-entry time to live. Expiry is lazy; call prune() periodically to reclaim memory. Access does not refresh the TTL (use touch). Complexity: get, set, has, delete, touch O(1); prune and iteration O(n).

class TTLCache<K, V> implements Iterable<[K, V]> {
  constructor(options: TTLCacheOptions<K, V>);
  get size(): number;
  set(key: K, value: V, options?: { readonly ttlMs?: number; }): this;
  get(key: K): V | undefined;
  has(key: K): boolean;
  ttlRemaining(key: K): number | undefined;
  touch(key: K, ttlMs?: number): boolean;
  delete(key: K): boolean;
  clear(): void;
  prune(): number;
  toArray(): [K, V][];
  [Symbol.iterator](): Iterator<[K, V]>;
}

Example:

const c = new TTLCache<string, string>({ ttlMs: 60_000 });
c.set('token', 'abc', { ttlMs: 5_000 });
c.get('token'); // 'abc' until 5 s later

Interfaces

LFUCacheOptions

interface LFUCacheOptions<K, V> {
  readonly maxSize: number;
  readonly onEvict?: (key: K, value: V) => void;
}

LRUCacheOptions

interface LRUCacheOptions<K, V> {
  readonly maxSize?: number;
  readonly ttlMs?: number;
  readonly onEvict?: (key: K, value: V, reason: EvictionReason) => void;
  readonly now?: () => number;
}

TTLCacheOptions

interface TTLCacheOptions<K, V> {
  readonly ttlMs: number;
  readonly maxSize?: number;
  readonly onEvict?: (key: K, value: V, reason: EvictionReason) => void;
  readonly now?: () => number;
}

Types

EvictionReason

Why a cache dropped an entry on its own.

type EvictionReason = 'capacity' | 'expired';

Disjoint set

Classes

DisjointSet

Union-find with path compression and union by rank. Complexity: add, find, union, connected, sizeOf O(α(n)) amortized (effectively constant); sets O(n). find is iterative.

class DisjointSet<T> implements Iterable<T> {
  constructor(items?: Iterable<T>);
  get size(): number;
  get setCount(): number;
  add(item: T): this;
  has(item: T): boolean;
  find(item: T): T | undefined;
  union(a: T, b: T): boolean;
  connected(a: T, b: T): boolean;
  sizeOf(item: T): number;
  sets(): T[][];
  clear(): void;
  toArray(): T[];
  [Symbol.iterator](): Iterator<T>;
}

Example:

const ds = new DisjointSet(['a', 'b', 'c']);
ds.union('a', 'b');
ds.connected('a', 'b'); // => true
ds.setCount;            // => 2

Emitter

Classes

TypedEventEmitter

Strongly typed event emitter. on returns an unsubscribe function; listeners are snapshotted per emit, so adding or removing listeners during an emit is safe. Complexity: on, emit O(listeners of the event); off O(listeners of the event). Not iterable and has no size; use listenerCount.

class TypedEventEmitter<E extends EventMap<E>> {
  constructor(options?: TypedEventEmitterOptions);
  on<K extends keyof E>(event: K, listener: Listener<E, K>): () => void;
  once<K extends keyof E>(event: K, listener: Listener<E, K>): () => void;
  off<K extends keyof E>(event: K, listener: Listener<E, K>): boolean;
  emit<K extends keyof E>(event: K, ...args: E[K]): boolean;
  listenerCount(event?: keyof E): number;
  eventNames(): (keyof E)[];
  removeAllListeners(event?: keyof E): void;
  clear(): void;
}

Example:

const bus = new TypedEventEmitter<{ saved: [id: string]; reset: [] }>();
const messages: string[] = [];
const stop = bus.on('saved', (id) => { messages.push(`Saved ${id}`); });
bus.emit('saved', 'e-42');
stop();
bus.emit('saved', 'e-43'); // no listener any more
messages; // => ['Saved e-42']

Interfaces

TypedEventEmitterOptions

interface TypedEventEmitterOptions {
  readonly isolateErrors?: boolean;
  readonly onError?: (error: Error, event: PropertyKey) => void;
  readonly maxListeners?: number;
  readonly onMaxListeners?: (event: PropertyKey, count: number) => void;
}

Types

EventMap

Event map: event name -> listener argument tuple, e.g. { change: [value: number]; close: [] }.

type EventMap<E> = {
  [K in keyof E]: unknown[];
};

Listener

Listener for event K.

type Listener<E extends EventMap<E>, K extends keyof E> = (...args: E[K]) => void;

Graph

Classes

Graph

Directed or undirected weighted graph on adjacency maps. Nodes are compared with Map semantics (SameValueZero). Every algorithm is iterative, so deep or long graphs cannot overflow the stack. Complexity (V nodes, E edges): addNode, addEdge, removeEdge, hasEdge, weight O(1); removeNode O(degree); bfs, dfs, topologicalSort, hasCycle, findCycle, connectedComponents, stronglyConnectedComponents O(V + E); shortestPath O((V + E) log V).

class Graph<N> implements Iterable<N> {
  readonly directed: boolean;
  constructor(options?: GraphOptions);
  get size(): number;
  get edgeCount(): number;
  addNode(node: N): this;
  hasNode(node: N): boolean;
  addEdge(from: N, to: N, weight?: number): this;
  hasEdge(from: N, to: N): boolean;
  weight(from: N, to: N): number | undefined;
  removeEdge(from: N, to: N): boolean;
  removeNode(node: N): boolean;
  neighbors(node: N): N[];
  inNeighbors(node: N): N[];
  nodes(): N[];
  edges(): Generator<[N, N, number]>;
  clear(): void;
  toArray(): N[];
  [Symbol.iterator](): Iterator<N>;
  bfs(start: N): Generator<N>;
  dfs(start: N): Generator<N>;
  topologicalSort(): N[];
  hasCycle(): boolean;
  findCycle(): N[] | undefined;
  shortestPath(from: N, to: N): ShortestPath<N> | undefined;
  distancesFrom(from: N): Map<N, number>;
  connectedComponents(): N[][];
  stronglyConnectedComponents(): N[][];
}

Example:

const g = new Graph<string>();
g.addEdge('shirt', 'tie').addEdge('tie', 'jacket').addEdge('trousers', 'jacket');
g.topologicalSort(); // => ['shirt', 'trousers', 'tie', 'jacket']

Interfaces

GraphOptions

interface GraphOptions {
  readonly directed?: boolean;
}

ShortestPath

Result of shortestPath.

interface ShortestPath<N> {
  readonly path: N[];
  readonly distance: number;
}

Heap

Classes

BinaryHeap

Array-backed binary min-heap ordered by comparer (pass a reversed comparer for a max-heap). Complexity: push, pop, replace O(log n); peek O(1); construction from an iterable O(n); remove O(n). Iteration order is the internal heap order; use drain() for sorted order.

class BinaryHeap<T> implements Iterable<T> {
  constructor(items?: Iterable<T>, comparer?: Comparer<T>);
  static from<T>(items: Iterable<T>, comparer?: Comparer<T>): BinaryHeap<T>;
  get size(): number;
  isEmpty(): boolean;
  push(item: T): this;
  peek(): T | undefined;
  pop(): T | undefined;
  replace(item: T): T | undefined;
  remove(item: T, equals?: (a: T, b: T) => boolean): boolean;
  clear(): void;
  toArray(): T[];
  toSortedArray(): T[];
  drain(): Generator<T>;
  [Symbol.iterator](): Iterator<T>;
}

Example:

const h = new BinaryHeap([5, 1, 3]);
h.pop(); // => 1
const byPriority = new BinaryHeap<{ p: number }>([], (a, b) => a.p - b.p);

PriorityQueue

Priority queue (alias of BinaryHeap): lowest value per comparer comes out first.

class PriorityQueue<T> extends BinaryHeap<T> {

}

Example:

const pq = new PriorityQueue<[number, string]>([], (a, b) => a[0] - b[0]);
pq.push([2, 'b']).push([1, 'a']);
pq.pop(); // => [1, 'a']

Internal

Functions

naturalCompare

Natural ordering for numbers, strings (code-unit order), bigints, booleans, and Dates. NaN sorts after every other number. Mixed or unsupported types throw HLP_DS_NOT_COMPARABLE.

function naturalCompare(a: unknown, b: unknown): number;

Example:

[3, 1, 2].sort(naturalCompare); // => [1, 2, 3]

Types

Comparer

Three-way comparer: negative when a sorts before b, zero when equal, positive otherwise.

type Comparer<T> = (a: T, b: T) => number;

Interval tree

Classes

IntervalTree

Augmented AVL interval tree (each node keeps the max end in its subtree). Complexity: insert, remove O(log n); search, searchPoint O(log n + k); iteration O(n). Results come back ordered by start, then end, then insertion order.

class IntervalTree<T> implements Iterable<IntervalEntry<T>> {
  readonly bounds: '[]' | '[)';
  constructor(options?: IntervalTreeOptions);
  get size(): number;
  insert(start: number, end: number, value: T): IntervalEntry<T>;
  remove(entry: IntervalEntry<T>): boolean;
  delete(start: number, end: number, value: T): boolean;
  search(start: number, end: number): IntervalEntry<T>[];
  searchPoint(point: number): IntervalEntry<T>[];
  overlaps(start: number, end: number): boolean;
  clear(): void;
  toArray(): IntervalEntry<T>[];
  [Symbol.iterator](): Iterator<IntervalEntry<T>>;
}

Example:

const t = new IntervalTree<string>({ bounds: '[)' });
t.insert(9, 10, 'standup');
t.insert(10, 11, 'review');
t.search(9.5, 10).map((e) => e.value); // => ['standup']
t.searchPoint(10).map((e) => e.value);  // => ['review']

Interfaces

IntervalEntry

A stored interval; the object identity is the handle for remove.

interface IntervalEntry<T> {
  readonly start: number;
  readonly end: number;
  readonly value: T;
}

IntervalTreeOptions

interface IntervalTreeOptions {
  readonly bounds?: '[]' | '[)';
}

Linked list

Classes

LinkedList

Doubly linked list with node handles for O(1) insertion and removal anywhere. Complexity: push, pop, shift, unshift, insertAfter, insertBefore, remove O(1); find, reverse, iteration O(n).

class LinkedList<T> implements Iterable<T> {
  constructor(items?: Iterable<T>);
  get size(): number;
  get head(): LinkedListNode<T> | undefined;
  get tail(): LinkedListNode<T> | undefined;
  isEmpty(): boolean;
  push(value: T): LinkedListNode<T>;
  unshift(value: T): LinkedListNode<T>;
  pop(): T | undefined;
  shift(): T | undefined;
  insertAfter(node: LinkedListNode<T>, value: T): LinkedListNode<T>;
  insertBefore(node: LinkedListNode<T>, value: T): LinkedListNode<T>;
  remove(node: LinkedListNode<T>): T;
  find(predicate: (value: T) => boolean): LinkedListNode<T> | undefined;
  reverse(): this;
  clear(): void;
  toArray(): T[];
  nodes(): Generator<LinkedListNode<T>>;
  [Symbol.iterator](): Iterator<T>;
}

Example:

const list = new LinkedList([1, 3]);
const one = list.find((v) => v === 1)!;
list.insertAfter(one, 2);
list.toArray(); // => [1, 2, 3]

Interfaces

LinkedListNode

Node handle returned by LinkedList; links are read-only to callers.

interface LinkedListNode<T> {
  value: T;
  readonly prev: LinkedListNode<T> | undefined;
  readonly next: LinkedListNode<T> | undefined;
}

Maps

Classes

BiMap

Two-way map with unique keys and unique values. Complexity: every operation O(1).

class BiMap<K, V> implements Iterable<[K, V]> {
  constructor(entries?: Iterable<readonly [K, V]>);
  get size(): number;
  set(key: K, value: V): this;
  forceSet(key: K, value: V): this;
  get(key: K): V | undefined;
  getKey(value: V): K | undefined;
  has(key: K): boolean;
  hasValue(value: V): boolean;
  delete(key: K): boolean;
  deleteValue(value: V): boolean;
  inverse(): BiMap<V, K>;
  clear(): void;
  keys(): IterableIterator<K>;
  values(): IterableIterator<V>;
  toArray(): [K, V][];
  [Symbol.iterator](): Iterator<[K, V]>;
}

Example:

const codes = new BiMap([['IN', 'India']]);
codes.getKey('India');       // => 'IN'
codes.set('FR', 'India');    // => throws HLP_DS_BIMAP_DUPLICATE_VALUE

MultiMap

Map from a key to many values. size counts values; keyCount counts keys. Complexity: add, get, has, delete O(1); hasEntry, deleteEntry O(1) with unique, O(values of key) otherwise.

class MultiMap<K, V> implements Iterable<[K, V]> {
  readonly unique: boolean;
  constructor(entries?: Iterable<readonly [K, V]>, options?: MultiMapOptions);
  get size(): number;
  get keyCount(): number;
  add(key: K, value: V): this;
  get(key: K): V[];
  has(key: K): boolean;
  hasEntry(key: K, value: V): boolean;
  delete(key: K): boolean;
  deleteEntry(key: K, value: V): boolean;
  clear(): void;
  keys(): IterableIterator<K>;
  groups(): Generator<[K, V[]]>;
  toArray(): [K, V][];
  [Symbol.iterator](): Iterator<[K, V]>;
}

Example:

const m = new MultiMap<string, number>();
m.add('a', 1).add('a', 2).add('b', 3);
m.get('a'); // => [1, 2]
m.size;     // => 3

Interfaces

MultiMapOptions

interface MultiMapOptions {
  readonly unique?: boolean;
}

Ring

Classes

CircularBuffer

Fixed-capacity buffer that overwrites the oldest item when full (logs, sliding windows, undo history). Complexity: push, shift, pop, at O(1); iteration O(n).

class CircularBuffer<T> implements Iterable<T> {
  constructor(capacity: number);
  get capacity(): number;
  get size(): number;
  isFull(): boolean;
  isEmpty(): boolean;
  push(item: T): T | undefined;
  shift(): T | undefined;
  pop(): T | undefined;
  at(index: number): T | undefined;
  clear(): void;
  toArray(): T[];
  [Symbol.iterator](): Iterator<T>;
}

Example:

const b = new CircularBuffer<number>(2);
b.push(1); b.push(2); b.push(3); // evicts 1
b.toArray(); // => [2, 3]

Deque

Double-ended queue on a growable ring buffer. Complexity: push, pop, shift, unshift, at O(1) amortized; iteration O(n).

class Deque<T> implements Iterable<T> {
  constructor(items?: Iterable<T>);
  get size(): number;
  isEmpty(): boolean;
  push(item: T): this;
  unshift(item: T): this;
  pop(): T | undefined;
  shift(): T | undefined;
  peekFront(): T | undefined;
  peekBack(): T | undefined;
  at(index: number): T | undefined;
  clear(): void;
  toArray(): T[];
  [Symbol.iterator](): Iterator<T>;
}

Example:

const d = new Deque<number>();
d.push(2); d.unshift(1);
d.shift(); // => 1
d.pop();   // => 2

Queue

FIFO queue on a growable ring buffer (no O(n) Array#shift). Complexity: enqueue, dequeue, peek O(1) amortized; iteration O(n).

class Queue<T> implements Iterable<T> {
  constructor(items?: Iterable<T>);
  get size(): number;
  isEmpty(): boolean;
  enqueue(item: T): this;
  dequeue(): T | undefined;
  peek(): T | undefined;
  clear(): void;
  toArray(): T[];
  [Symbol.iterator](): Iterator<T>;
}

Example:

const q = new Queue(['a']);
q.enqueue('b');
q.dequeue(); // => 'a'

Sorted

Classes

SortedMap

Map ordered by key on a balanced (AVL) tree with a custom comparer. Complexity: get, set, has, delete, floor, ceiling, lower, higher, first, last O(log n); between O(log n + k); full iteration O(n). Modifying the map while iterating throws HLP_DS_CONCURRENT_MODIFICATION (updating an existing key’s value is allowed).

class SortedMap<K, V> implements Iterable<[K, V]> {
  constructor(entries?: Iterable<readonly [K, V]>, comparer?: Comparer<K>);
  get size(): number;
  get(key: K): V | undefined;
  has(key: K): boolean;
  set(key: K, value: V): this;
  delete(key: K): boolean;
  clear(): void;
  first(): [K, V] | undefined;
  last(): [K, V] | undefined;
  floor(key: K): [K, V] | undefined;
  ceiling(key: K): [K, V] | undefined;
  lower(key: K): [K, V] | undefined;
  higher(key: K): [K, V] | undefined;
  shift(): [K, V] | undefined;
  pop(): [K, V] | undefined;
  between(lo: K, hi: K, bounds?: RangeBounds): Generator<[K, V]>;
  keys(): Generator<K>;
  values(): Generator<V>;
  entries(): Generator<[K, V]>;
  reversed(): Generator<[K, V]>;
  toArray(): [K, V][];
  [Symbol.iterator](): Generator<[K, V]>;
}

Example:

const m = new SortedMap<number, string>([[3, 'c'], [1, 'a']]);
m.set(2, 'b');
[...m.keys()];        // => [1, 2, 3]
m.floor(2.5);         // => [2, 'b']
[...m.between(2, 3)]; // => [[2, 'b'], [3, 'c']]

SortedSet

Set ordered by a custom comparer on a balanced (AVL) tree. Complexity: add, has, delete, floor, ceiling, first, last O(log n); between O(log n + k).

class SortedSet<T> implements Iterable<T> {
  constructor(items?: Iterable<T>, comparer?: Comparer<T>);
  get size(): number;
  add(item: T): this;
  has(item: T): boolean;
  delete(item: T): boolean;
  clear(): void;
  first(): T | undefined;
  last(): T | undefined;
  floor(item: T): T | undefined;
  ceiling(item: T): T | undefined;
  lower(item: T): T | undefined;
  higher(item: T): T | undefined;
  between(lo: T, hi: T, bounds?: RangeBounds): Generator<T>;
  reversed(): Generator<T>;
  toArray(): T[];
  [Symbol.iterator](): Generator<T>;
}

Example:

const s = new SortedSet(['pear', 'apple']);
s.add('fig');
s.toArray();       // => ['apple', 'fig', 'pear']
s.ceiling('b');    // => 'fig'

Types

RangeBounds

Bound inclusion for range queries: '[]' both ends (default), '[)', '(]', '()'.

type RangeBounds = '[]' | '[)' | '(]' | '()';

Stack

Classes

Stack

Array-backed LIFO stack. Complexity: push, pop, peek O(1) amortized; iteration O(n).

class Stack<T> implements Iterable<T> {
  constructor(items?: Iterable<T>);
  get size(): number;
  isEmpty(): boolean;
  push(item: T): this;
  pop(): T | undefined;
  peek(): T | undefined;
  clear(): void;
  toArray(): T[];
  [Symbol.iterator](): Iterator<T>;
}

Example:

const s = new Stack([1, 2]);
s.push(3);
s.pop(); // => 3

Trie

Classes

Trie

Set of strings as a prefix tree (autocomplete, prefix checks). Complexity as TrieMap.

class Trie implements Iterable<string> {
  constructor(words?: Iterable<string>, options?: TrieOptions);
  get size(): number;
  insert(word: string): this;
  has(word: string): boolean;
  delete(word: string): boolean;
  startsWith(prefix: string): boolean;
  findByPrefix(prefix: string, limit?: number): string[];
  countPrefix(prefix: string): number;
  longestCommonPrefix(): string;
  longestPrefixOf(text: string): string | undefined;
  clear(): void;
  toArray(): string[];
  [Symbol.iterator](): Iterator<string>;
}

Example:

const t = new Trie(['car', 'cart', 'cat']);
t.startsWith('ca');       // => true
t.findByPrefix('car');    // => ['car', 'cart']
t.longestCommonPrefix();  // => 'ca'

TrieMap

Prefix tree mapping string keys to values. Walks by code point (surrogate-pair safe); every operation is iterative, so very long keys cannot overflow the stack. Complexity (m = key length, k = results): set, get, has, delete, hasPrefix, countPrefix O(m); entriesWithPrefix O(m + subtree size) with children visited in code-unit order.

class TrieMap<V> implements Iterable<[string, V]> {
  constructor(entries?: Iterable<readonly [string, V]>, options?: TrieOptions);
  get size(): number;
  set(key: string, value: V): this;
  get(key: string): V | undefined;
  has(key: string): boolean;
  delete(key: string): boolean;
  hasPrefix(prefix: string): boolean;
  countPrefix(prefix: string): number;
  entriesWithPrefix(prefix: string, limit?: number): [string, V][];
  keysWithPrefix(prefix: string, limit?: number): string[];
  longestCommonPrefix(): string;
  longestPrefixOf(text: string): string | undefined;
  clear(): void;
  toArray(): [string, V][];
  [Symbol.iterator](): Iterator<[string, V]>;
}

Example:

const t = new TrieMap<number>(undefined, { caseFold: true });
t.set('Apple', 1).set('apricot', 2);
t.get('APPLE');              // => 1
t.keysWithPrefix('ap');      // => ['Apple', 'apricot']

Interfaces

TrieOptions

interface TrieOptions {
  readonly caseFold?: boolean | string;
}