metautil-data-structures

Metautil Data Structures

Import from the package root. Prefer these ADTs over ad-hoc Array/Object when the discipline (FIFO, LIFO, persistence, schema) matters.

const metautil = require('metautil');
const { ConsList, cons, uncons, Struct, Deque, Queue, Stack } = metautil;
const { List, ListNode, CircularBuffer, UnrolledList, Trie } = metautil;

Choose the right structure

• FIFO jobs / BFS / sliding failure window: Queue
• LIFO undo / nested layers / brackets: Stack
• Both ends O(1), capped window: Deque or CircularBuffer
• Index + mid-sequence edit/move/group: List
• Immutable history / branching / sharing: ConsList
• Typed sealed/frozen records: Struct
• Prefix autocomplete / string keys: Trie
• Extreme enqueue/dequeue volume only: UnrolledList (no peek / interop)
• Random access on a ring: CircularBuffer.at (not Deque)

Complexity and surface

• CircularBuffer — ends O(1), index O(1) via at
• Deque / Queue / Stack — ends O(1); no index (at only on buffer)
• UnrolledList — ends O(1); no peek / interop
• List — ends O(1), index O(n)
• ConsList — prepend O(1), walk O(n)
• Trie — string-key prefix map

Who has what (beyond size / isEmpty where present):

• fromArray / toArray / iterator: all except UnrolledList (and Trie)
• peek: Queue, Stack
• at: CircularBuffer only
• every / reduce: CircularBuffer, Deque, Stack (not Queue)
• clear / includes: ring family + List + Trie.clear; not ConsList / UnrolledList

Interoperability

Convert through Array:

const list = List.fromArray([1, 2, 3, 4, 5]);
const queue = Queue.fromArray(list.filter((n) => n % 2 === 0).toArray());
const consList = ConsList.fromArray(queue.toArray());

Deque, Queue, and Stack are thin facades over CircularBuffer (same ring storage).

Struct

Schema is inferred from default literals. Immutable uses Object.freeze; mutable uses Object.seal. Class name becomes constructor.name. Statics: fields, schema, mutable.