29:null 2a:["$","title",null,{"children":"ADTs and Data Structures | Jo Wood | Observable"}] 2f:T470,display(md`\`▶ Queue\``); // In place of cell introspection class Queue { #in; // Forward-facing queue items, added via enqueue operations. #out = []; // Reverse-facing items for efficient dequeue operations. constructor(xs = []) { this.#in = [...xs]; } // ------------------------------ Public ADT methods size() { return this.#in.length + this.#out.length; } isEmpty() { return this.#in.length === 0 && this.#out.length === 0; } peek() { if (this.isEmpty()) { throw new Error("Attempting to peek into an empty queue"); } if (this.#out.length > 0) { return this.#out[this.#out.length - 1]; } return this.#in[0]; } toArray() { return [...this.#out].reverse().concat(this.#in); } enqueue(x) { this.#in.push(x); return this; } dequeue() { if (this.isEmpty()) { throw new Error("Attempting to dequeue an empty queue"); } if (this.#out.length === 0) { this.#out = this.#in.reverse(); this.#in = []; } return this.#out.pop(); } clear() { this.#in = []; this.#out = []; return this; } }30:T91f,display(md`\`▶ Deque\``); // In place of cell introspection class Deque { #xs = {}; // Sparse circular buffer storage #front = 0; // Index of the front of the Deque #back = 0; // Index of the back of the Deque #capacity = Infinity; // If finite, we can create a circular buffer (useful for sliding windows etc.) constructor(xs = [], capacity = Infinity) { if ( capacity !== Infinity && (!Number.isInteger(capacity) || capacity <= 0) ) { throw new RangeError( "Deque capacity must be a positive integer or Infinity" ); } this.#capacity = capacity; for (const x of xs) { this.enqueueBack(x); } } // ------------------------------ Public ADT methods size() { return this.#back - this.#front; } isEmpty() { return this.size() === 0; } peekFront() { if (this.isEmpty()) { throw new Error("Attempting to peek at the front of an empty deque"); } return this.#xs[this.#front]; } peekBack() { if (this.isEmpty()) { throw new Error("Attempting to peek at the back of an empty deque"); } return this.#xs[this.#back - 1]; } toArray() { const result = []; for (let i = this.#front; i < this.#back; i++) { result.push(this.#xs[i]); } return result; } enqueueFront(x) { if (this.#isFull()) { this.dequeueBack(); // Drop newest if full } this.#front--; this.#xs[this.#front] = x; return this; } enqueueBack(x) { if (this.#isFull()) { this.dequeueFront(); // Drop oldest if full } this.#xs[this.#back] = x; this.#back++; return this; } dequeueFront() { if (this.isEmpty()) { throw new Error("Attempting to dequeue the front of an empty deque"); } const x = this.#xs[this.#front]; delete this.#xs[this.#front]; this.#front++; return x; } dequeueBack() { if (this.isEmpty()) { throw new Error("Attempting to dequeue the back of an empty deque"); } this.#back--; const x = this.#xs[this.#back]; delete this.#xs[this.#back]; return x; } clear() { this.#xs = {}; this.#front = 0; this.#back = 0; return this; } // ------------------------------ Private helper methods #isFull() { return this.size() >= this.#capacity; } }31:Ta96,display(md`\`▶ PriorityQueue\``); // In place of cell introspection class PriorityQueue { #heap = []; #nextOrder = 0; constructor(entries = []) { // API uses [value, priority]; internally add insertion order for stable ties. this.#heap = entries.map(([value, priority = 0], order) => [ priority, order, value ]); this.#nextOrder = this.#heap.length; this.#heapify(); } size() { return this.#heap.length; } isEmpty() { return this.#heap.length === 0; } peek() { if (this.isEmpty()) { throw new Error("Attempting to peek into an empty priority queue"); } return this.#heap[0][2]; } peekPriority() { if (this.isEmpty()) { throw new Error( "Attempting to peek at the priority of an empty priority queue" ); } return this.#heap[0][0]; } toArray() { return [...this.#heap] .sort(PriorityQueue.#compare) .map(([, , value]) => value); } enqueue(value, priority = 0) { const entry = [priority, this.#nextOrder++, value]; this.#heap.push(entry); this.#siftUp(this.#heap.length - 1); return this; } dequeue() { if (this.isEmpty()) { throw new Error("Attempting to dequeue from an empty priority queue"); } const [root, last] = [this.#heap[0], this.#heap.pop()]; if (!this.isEmpty()) { this.#heap[0] = last; this.#siftDown(0); } return root[2]; } clear() { this.#heap = []; this.#nextOrder = 0; return this; } // ------------------------------ Private methods static #compare(a, b) { return a[0] - b[0] || a[1] - b[1]; } static #comesBefore(a, b) { return PriorityQueue.#compare(a, b) < 0; } #heapify() { const start = Math.floor(this.#heap.length / 2) - 1; for (let i = start; i >= 0; i--) { this.#siftDown(i); } } #siftUp(i) { const heap = this.#heap; const entry = heap[i]; while (i > 0) { const parent = (i - 1) >> 1; if (!PriorityQueue.#comesBefore(entry, heap[parent])) { break; } heap[i] = heap[parent]; i = parent; } heap[i] = entry; } #siftDown(i) { const heap = this.#heap; const n = heap.length; const entry = heap[i]; while (true) { const left = 2 * i + 1; const right = left + 1; let best = i; if (left < n && PriorityQueue.#comesBefore(heap[left], heap[best])) { best = left; } if (right < n && PriorityQueue.#comesBefore(heap[right], heap[best])) { best = right; } if (best === i) { break; } heap[i] = heap[best]; i = best; } heap[i] = entry; } }32:Ta36,display(md`\`▶ BoundedPriorityQueue\``); // In place of cell introspection class BoundedPriorityQueue { #heap = []; #capacity; constructor(capacity = Infinity) { this.#capacity = capacity; this.#heap = []; // Array of [priority, value] tuples if ( capacity !== Infinity && (!Number.isInteger(capacity) || capacity <= 0) ) { throw new RangeError( "BoundedPriorityQueue capacity must be a positive integer or Infinity" ); } } size() { return this.#heap.length; } peek() { if (this.isEmpty()) { throw new Error( "Attempting to peek at value in an empty BoundedPriorityQueue" ); } return this.#heap[0][1]; } peekPriority() { if (this.isEmpty()) { throw new Error( "Attempting to peek at priority in an empty BoundedPriorityQueue" ); } return this.#heap[0][0]; } dequeue() { if (this.isEmpty()) { throw new Error("Cannot dequeue from an empty BoundedPriorityQueue"); } const max = this.#heap[0]; const last = this.#heap.pop(); if (!this.isEmpty()) { this.#heap[0] = last; this.#siftDown(0); } return max[1]; } insert(x, priority = 0) { if (this.#heap.length < this.#capacity) { this.#heap.push([priority, x]); this.#siftUp(this.#heap.length - 1); } else if (priority < this.#heap[0][0]) { this.#heap[0] = [priority, x]; this.#siftDown(0); } return this; } toArray() { return this.#heap.map(([_, x]) => x); } toSortedArray() { return [...this.#heap].sort((a, b) => a[0] - b[0]).map(([_, x]) => x); } isEmpty() { return this.#heap.length === 0; } clear() { this.#heap = []; return this; } // ---------------------- Private helper methods #siftUp(i) { while (i > 0) { const parent = (i - 1) >> 1; if (this.#heap[i][0] <= this.#heap[parent][0]) { break; } [this.#heap[i], this.#heap[parent]] = [this.#heap[parent], this.#heap[i]]; i = parent; } } #siftDown(i) { const n = this.#heap.length; while (true) { const [left, right] = [2 * i + 1, 2 * i + 2]; let largest = i; if (left < n && this.#heap[left][0] > this.#heap[largest][0]) { largest = left; } if (right < n && this.#heap[right][0] > this.#heap[largest][0]) { largest = right; } if (largest === i) { break; } [this.#heap[i], this.#heap[largest]] = [ this.#heap[largest], this.#heap[i] ]; i = largest; } } }33:T1185,display(md`\`▶ DoublyLinkedList\``); // In place of cell introspection class DoublyLinkedList { #head = null; #tail = null; #size = 0; constructor(xs = []) { for (const x of xs) { this.pushBack(x); } } // ------------------------------ Public ADT methods size() { return this.#size; } isEmpty() { return this.#size === 0; } peekFront() { if (this.isEmpty()) { throw new Error("Attempting to peek at the front of an empty list"); } return this.#head.x; } peekBack() { if (this.isEmpty()) { throw new Error("Attempting to peek at the back of an empty list"); } return this.#tail.x; } toArray() { const result = []; for (let node = this.#head; node; node = node.next) { result.push(node.x); } return result; } pushFront(x) { const node = {x, prev: null, next: this.#head}; if (this.#head) { this.#head.prev = node; } else { this.#tail = node; } this.#head = node; this.#size++; return this; } pushBack(x) { const node = {x, prev: this.#tail, next: null}; if (this.#tail) { this.#tail.next = node; } else { this.#head = node; } this.#tail = node; this.#size++; return this; } popFront() { if (this.isEmpty()) { throw new Error("Attempting to pop from the front of an empty list"); } const x = this.#head.x; this.#head = this.#head.next; if (this.#head) { this.#head.prev = null; } else { this.#tail = null; } this.#size--; return x; } popBack() { if (this.isEmpty()) { throw new Error("Attempting to pop from the back of an empty list"); } const x = this.#tail.x; this.#tail = this.#tail.prev; if (this.#tail) { this.#tail.next = null; } else { this.#head = null; } this.#size--; return x; } clear() { this.#head = null; this.#tail = null; this.#size = 0; return this; } indexOf(x) { let i = 0; for (let node = this.#head; node; node = node.next, i++) { if (node.x === x) { return i; } } return -1; } find(pred) { for (let node = this.#head; node; node = node.next) { if (pred(node.x)) { return node; } } return null; } findLast(pred) { for (let node = this.#tail; node; node = node.prev) { if (pred(node.x)) { return node; } } return null; } insertAt(i, x) { if (i < 0 || i > this.#size) { throw new Error( `Index out of bounds: ${i} in DoublyLinkedList of size ${this.#size}` ); } if (i === 0) { this.pushFront(x); } else if (i === this.#size) { this.pushBack(x); } else { const node = this.#getNodeAt(i); this.insertBefore(node, x); } return this; } insertAfter(node, x) { if (!node) { throw new Error("insertAfter: reference node cannot be null"); } const next = node.next; const newNode = {x, prev: node, next}; node.next = newNode; if (next) { next.prev = newNode; } else { this.#tail = newNode; } this.#size++; return this; } insertBefore(node, x) { if (!node) { throw new Error("insertBefore: reference node cannot be null"); } const prev = node.prev; const newNode = {x, prev, next: node}; node.prev = newNode; if (prev) { prev.next = newNode; } else { this.#head = newNode; } this.#size++; return this; } removeAt(i) { const node = this.#getNodeAt(i); return this.remove(node); } remove(node) { if (!node) { return null; } const {prev, next, x} = node; if (prev) { prev.next = next; } else { this.#head = next; } if (next) { next.prev = prev; } else { this.#tail = prev; } this.#size--; return x; } // ------------------------------ Private helper methods #getNodeAt(i) { if (i < 0 || i >= this.#size) { throw new Error( `Index out of bounds: ${i} in DoublyLinkedList of size ${this.#size}` ); } let node; if (i < this.#size / 2) { node = this.#head; for (let n = 0; n < i; n++) { node = node.next; } } else { node = this.#tail; for (let n = this.#size - 1; n > i; n--) { node = node.prev; } } return node; } }34:T436,display(md`\`▶ TreeNode\``); // In place of cell introspection class TreeNode { constructor(value) { this.value = value; this.children = []; this.parent = null; } addChild(node) { if (!(node instanceof TreeNode)) { throw new TypeError("TreeNode addChild: child must be a TreeNode"); } if (node.parent !== null) { throw new Error("TreeNode addChild: child already has a parent"); } // Look for attempt to attach an ancestor beneath one of its descendants. for (let ancestor = this; ancestor; ancestor = ancestor.parent) { if (ancestor === node) { throw new Error("TreeNode addChild: attachment would create a cycle"); } } node.parent = this; this.children.push(node); return this; } removeChild(node) { const i = this.children.indexOf(node); if (i !== -1) { this.children.splice(i, 1); node.parent = null; } return this; } isLeaf() { return this.children.length === 0; } childValues() { return this.children.map((c) => c.value); } }35:Tf8c,display(md`\`▶ Tree\``); // In place of cell introspection class Tree { constructor(root = null) { this.root = root; } *[Symbol.iterator]() { yield* this.dfsPreOrder(); } clear() { this.root = null; return this; } addChild(parent, child) { if (!(parent instanceof TreeNode)) { throw new TypeError("Tree addChild: parent must be a TreeNode"); } if (!(child instanceof TreeNode)) { throw new TypeError("Tree addChild: child must be a TreeNode"); } if (!this.root) { if (parent.parent !== null) { throw new Error( "Tree addChild: the root of an empty tree cannot have a parent" ); } parent.addChild(child); this.root = parent; return this; } // O(h) and confirms that parent belongs to this tree without traversing every node. let ancestor = parent; while (ancestor.parent) { ancestor = ancestor.parent; } if (ancestor !== this.root) { throw new Error("Tree addChild: parent does not belong to this tree"); } parent.addChild(child); return this; } *nodesPreOrder(node = this.root) { if (!node) { return; } yield node; for (const child of node.children) { yield* this.nodesPreOrder(child); } } *nodesPostOrder(node = this.root) { if (!node) { return; } for (const child of node.children) { yield* this.nodesPostOrder(child); } yield node; } *dfsPreOrder(node = this.root) { if (!node) { return; } yield node.value; for (const child of node.children) { yield* this.dfsPreOrder(child); } } *dfsPostOrder(node = this.root) { if (!node) return; for (const child of node.children) { yield* this.dfsPostOrder(child); } yield node.value; } *bfs() { if (!this.root) { return; } const queue = [this.root]; let head = 0; while (head < queue.length) { const node = queue[head++]; yield node.value; queue.push(...node.children); } } toArray(traversal = "bfs") { switch (traversal) { case "pre": return [...this.dfsPreOrder()]; case "post": return [...this.dfsPostOrder()]; case "bfs": return [...this.bfs()]; default: throw new Error(`Unsupported traversal: ${traversal}`); } } find(value) { for (const node of this.nodesPreOrder()) { if (node.value === value) return node; } return null; } findAll(value) { const matches = []; for (const node of this.nodesPreOrder()) { if (node.value === value) matches.push(node); } return matches; } findWhere(predicate) { for (const node of this.nodesPreOrder()) { if (predicate(node)) return node; } return null; } toDot(options = {}) { const { rankDir = "TB", scale = 1, compact = true, fillClr = () => "white", labelClr = () => "black" } = options; const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const idMap = new Map(); let idCounter = 0; for (const node of this.nodesPreOrder()) { const id = `n${idCounter++}`; idMap.set(node, id); lines.push( ` ${id} [label="${node.value}" style=filled fillcolor=${fillClr( node )} fontcolor=${labelClr(node)}];` ); } for (const node of this.nodesPreOrder()) { const fromId = idMap.get(node); for (const child of node.children) { const toId = idMap.get(child); lines.push(` ${fromId} -> ${toId};`); } } lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } }36:T46f,display(md`\`▶ BinaryTreeNode\``); // In place of cell introspection class BinaryTreeNode { #value; constructor(x, left = null, right = null) { this.#value = x; this.parent = null; this.setLeft(left); this.setRight(right); } // Value accessors get value() { return this.#value; } set value(x) { this.#value = x; } // Child value accessors get leftValue() { return this.left?.value ?? null; } get rightValue() { return this.right?.value ?? null; } // Set child nodes and manage parent reference setLeft(node) { if (this.left?.parent === this) { this.left.parent = null; } this.left = node; if (node) { node.parent = this; } return this; } setRight(node) { if (this.right?.parent === this) { this.right.parent = null; } this.right = node; if (node) { node.parent = this; } return this; } // Structural checks isLeaf() { return this.left === null && this.right === null; } hasLeft() { return this.left !== null; } hasRight() { return this.right !== null; } }37:Td2d,display(md`\`▶ AbstractBinaryTree\``); // In place of cell introspection class AbstractBinaryTree { // Can iterate over entire tree in dfs in-order *[Symbol.iterator]() { yield* this.dfsInOrder(); } // Node-based depth-first pre-order traversal of the tree *nodesPreOrder(node = this.root) { if (!node) { return; } yield node; yield* this.nodesPreOrder(node.left); yield* this.nodesPreOrder(node.right); } // Value-based depth-first pre-order traversal (VLR) *dfsPreOrder(node = this.root) { if (!node) { return; } yield node.value; yield* this.dfsPreOrder(node.left); yield* this.dfsPreOrder(node.right); } // Value-based depth-first in-order traversal (LVR) *dfsInOrder(node = this.root) { if (!node) { return; } yield* this.dfsInOrder(node.left); yield node.value; yield* this.dfsInOrder(node.right); } // Value-based depth-first post-order traversal (LRV) *dfsPostOrder(node = this.root) { if (!node) { return; } yield* this.dfsPostOrder(node.left); yield* this.dfsPostOrder(node.right); yield node.value; } // Breadth-first traversal (BFS) *bfs() { if (!this.root) { return; } const queue = [this.root]; let head = 0; while (head < queue.length) { const node = queue[head++]; yield node.value; if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } } // Convert to array using specified traversal strategy toArray(traversal = "bfs") { switch (traversal) { case "in": return [...this.dfsInOrder()]; case "pre": return [...this.dfsPreOrder()]; case "post": return [...this.dfsPostOrder()]; case "bfs": return [...this.bfs()]; default: throw new Error(`Unsupported traversal type: ${traversal}`); } } // Remove all nodes from the tree clear() { this.root = null; return this; } // Generate GraphViz DOT representation of the tree toDot(options = {}) { const { rankDir = "TB", scale = 1, compact = true, fillClr = () => "white", labelClr = () => "black" } = options; const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const idMap = new Map(); let idCounter = 0; for (const node of this.nodesPreOrder()) { const id = `n${idCounter++}`; idMap.set(node, id); const fill = fillClr(node); const font = labelClr(node); lines.push( ` ${id} [label="${node.value}" style=filled fillcolor=${fill} fontcolor=${font}];` ); } for (const node of this.nodesPreOrder()) { const fromId = idMap.get(node); if (node.left) { const toId = idMap.get(node.left); lines.push(` ${fromId} -> ${toId};`); } if (node.right) { const toId = idMap.get(node.right); lines.push(` ${fromId} -> ${toId};`); } } lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } }38:T418,display(md`\`▶ BinaryTree\``); // In place of cell introspection class BinaryTree extends AbstractBinaryTree { constructor(root = null) { super(); this.root = root; } // Link a child node to a parent node on the given side setChild(parent, child, direction = "L") { const dir = direction.toUpperCase(); if (!["L", "R"].includes(dir)) { throw new Error(`Invalid direction: ${dir}`); } if (!this.root) { this.root = parent; } if (dir === "L") { parent.setLeft(child); } else { parent.setRight(child); } return this; } // Return an array of all nodes whose value matches x find(x) { const result = []; for (const node of this.nodesPreOrder()) { if (node.value === x) { result.push(node); } } return result; } // Return the first node matching the given predicate findWhere(predicate) { for (const node of this.nodesPreOrder()) { if (predicate(node)) { return node; } } return null; } }39:T746,display(md`\`▶ BinarySearchTree\``); // In place of cell introspection class BinarySearchTree extends AbstractBinaryTree { constructor(rootValue = null) { super(); this.root = rootValue !== null ? new BinaryTreeNode(rootValue) : null; } insert(x) { const newNode = new BinaryTreeNode(x); if (!this.root) { this.root = newNode; return this; } let curr = this.root; while (true) { if (x === curr.value) { return this; // Duplicate, so don't insert } if (x < curr.value) { if (!curr.left) { curr.setLeft(newNode); return this; } curr = curr.left; } else { if (!curr.right) { curr.setRight(newNode); return this; } curr = curr.right; } } } find(x) { let curr = this.root; while (curr) { if (x === curr.value) { return curr; } curr = x < curr.value ? curr.left : curr.right; } return null; } remove(x) { const removeNode = (node, x) => { if (!node) { return null; } if (x < node.value) { node.setLeft(removeNode(node.left, x)); } else if (x > node.value) { node.setRight(removeNode(node.right, x)); } else { // Node to remove found if (!node.left) { return node.right; } if (!node.right) { return node.left; } // Two children: replace with in-order successor let succ = node.right; while (succ.left) { succ = succ.left; } node.value = succ.value; node.setRight(removeNode(node.right, succ.value)); } return node; }; this.root = removeNode(this.root, x); if (this.root) { this.root.parent = null; } return this; } }3a:Tb3e,display(md`\`▶ AVLTree\``); // In place of cell introspection class AVLTree extends BinarySearchTree { constructor(rootValue = null) { super(); this.root = rootValue !== null ? new AVLTreeNode(rootValue) : null; if (this.root) { this.root.parent = null; } } // All new insertions maintain balanced tree by rotating sub-trees where necessary. insert(x) { const newNode = new AVLTreeNode(x); const insertRec = (node) => { if (!node) { return newNode; } if (x === node.value) { return node; // Ignore duplicates } if (x < node.value) { node.setLeft(insertRec(node.left)); } else { node.setRight(insertRec(node.right)); } return this.#rebalance(node); }; this.root = insertRec(this.root); if (this.root) { this.root.parent = null; } return this; } // All node deletions rebalance tree by rotating sub-trees where necessary. remove(x) { const removeRec = (node, x) => { if (!node) { return null; } if (x < node.value) { node.setLeft(removeRec(node.left, x)); } else if (x > node.value) { node.setRight(removeRec(node.right, x)); } else { if (!node.left) { return node.right; } if (!node.right) { return node.left; } let succ = node.right; while (succ.left) { succ = succ.left; } node.value = succ.value; node.setRight(removeRec(node.right, succ.value)); } return this.#rebalance(node); }; this.root = removeRec(this.root, x); if (this.root) { this.root.parent = null; } return this; } // ------------------------------ Private methods #height(node) { return node ? node.height : 0; } #updateHeight(node) { AVLTreeNode.setNodeHeight( node, 1 + Math.max(this.#height(node.left), this.#height(node.right)) ); } #balanceFactor(node) { return this.#height(node.left) - this.#height(node.right); } #rebalance(node) { this.#updateHeight(node); const balance = this.#balanceFactor(node); if (balance > 1) { if (this.#balanceFactor(node.left) < 0) { node.setLeft(this.#rotateLeft(node.left)); } return this.#rotateRight(node); } if (balance < -1) { if (this.#balanceFactor(node.right) > 0) { node.setRight(this.#rotateRight(node.right)); } return this.#rotateLeft(node); } return node; } #rotateLeft(a) { const b = a.right; a.setRight(b.left); b.setLeft(a); this.#updateHeight(a); this.#updateHeight(b); return b; } #rotateRight(a) { const b = a.left; a.setLeft(b.right); b.setRight(a); this.#updateHeight(a); this.#updateHeight(b); return b; } }3b:T1046,display(md`\`▶ RedBlackTree\``); // In place of cell introspection class RedBlackTree extends AbstractBinaryTree { constructor(rootValue = null) { super(); this.root = rootValue !== null ? new RedBlackTreeNode(rootValue) : null; if (this.root) { this.root.clr = "B"; // Root must be black this.root.parent = null; } } // All new insertions maintain an approximately balanced tree by performing a maximum of one rotation. insert(x) { const newNode = new RedBlackTreeNode(x); const insertRec = (node) => { if (!node) { return newNode; } if (x === node.value) { return node; // Ignore duplicates } if (x < node.value) { node.setLeft(insertRec(node.left)); } else { node.setRight(insertRec(node.right)); } return this.#fixUp(node); }; this.root = insertRec(this.root); if (this.root) { this.root.clr = "B"; this.root.parent = null; } return this; } // Restore the left-leaning red–black invariants while unwinding the insertion. remove(x) { if (!this.find(x)) { return this; } const minNode = (n) => { while (n.left) { n = n.left; } return n; }; const removeRec = (node) => { if (!node) return null; if (x < node.value) { if (node.left) { if (!this.#isRed(node.left) && !this.#isRed(node.left.left)) { node = this.#moveRedLeft(node); } node.setLeft(removeRec(node.left)); } } else { if (this.#isRed(node.left)) { node = this.#rotateRight(node); } if (x === node.value && !node.right) { return null; } if (node.right) { if (!this.#isRed(node.right) && !this.#isRed(node.right.left)) { node = this.#moveRedRight(node); } if (x === node.value) { const m = minNode(node.right); node.value = m.value; node.setRight(this.#deleteMin(node.right)); } else { node.setRight(removeRec(node.right)); } } } return this.#fixUp(node); }; this.root = removeRec(this.root); if (this.root) { this.root.clr = "B"; this.root.parent = null; } return this; } find(x) { let curr = this.root; while (curr) { if (x === curr.value) return curr; curr = x < curr.value ? curr.left : curr.right; } return null; } // ------------------------------ Private helpers #isRed(node) { return node?.clr === "R"; } #flipClrs(node) { node.clr = this.#isRed(node) ? "B" : "R"; if (node.left) node.left.clr = this.#isRed(node.left) ? "B" : "R"; if (node.right) node.right.clr = this.#isRed(node.right) ? "B" : "R"; } #rotateLeft(a) { const b = a.right; a.setRight(b.left); b.setLeft(a); b.clr = a.clr; a.clr = "R"; return b; } #rotateRight(a) { const b = a.left; a.setLeft(b.right); b.setRight(a); b.clr = a.clr; a.clr = "R"; return b; } #fixUp(node) { if (this.#isRed(node.right) && !this.#isRed(node.left)) { node = this.#rotateLeft(node); } if (this.#isRed(node.left) && this.#isRed(node.left.left)) { node = this.#rotateRight(node); } if (this.#isRed(node.left) && this.#isRed(node.right)) { this.#flipClrs(node); } return node; } #deleteMin(node) { if (!node.left) { return null; } if (!this.#isRed(node.left) && !this.#isRed(node.left.left)) { node = this.#moveRedLeft(node); } node.setLeft(this.#deleteMin(node.left)); return this.#fixUp(node); } #moveRedLeft(node) { this.#flipClrs(node); if (this.#isRed(node.right?.left)) { node.setRight(this.#rotateRight(node.right)); node = this.#rotateLeft(node); this.#flipClrs(node); } return node; } #moveRedRight(node) { this.#flipClrs(node); if (this.#isRed(node.left?.left)) { node = this.#rotateRight(node); this.#flipClrs(node); } return node; } }3c:T1103,display(md`\`▶ Trie\``); // In place of cell introspection class Trie { #root = new TrieNode(); *[Symbol.iterator]() { yield* this.#dfsLex(); } // Distribute the characters of the word to insert in the trie insert(word) { let node = this.#root; for (const ch of word) { if (!node.children.has(ch)) { node.children.set(ch, new TrieNode()); } node = node.children.get(ch); } node.markAsWord(); return this; } // Is the given word represented in the trie? has(word) { return this.#walk(word)?.isWord ?? false; } // Does the given prefix exist in the trie? startsWith(prefix) { const node = this.#walk(prefix); return ( node !== null && (prefix.length > 0 || node.isWord || node.children.size > 0) ); } // Remove the given word from the trie. remove(word) { const chars = [...word]; // Treat each Unicode code point as one trie symbol. const removeRec = (node, depth = 0) => { if (!node) { return false; } if (depth === chars.length) { if (!node.isWord) { return false; } node.unmarkAsWord(); return node.children.size === 0; } const ch = chars[depth]; const child = node.children.get(ch); if (!removeRec(child, depth + 1)) { return false; } node.children.delete(ch); return !node.isWord && node.children.size === 0; }; removeRec(this.#root); return this; } // How many words stored in the trie? wordCount() { let count = 0; for (const _ of this.dfs()) { count++; } return count; } // Depth-first traversal of the Trie to yield words in DFS order (not lexicographic) *dfs(node = this.#root, path = "") { if (node.isWord) { yield path; } for (const [ch, child] of node.children) { yield* this.dfs(child, path + ch); } } // Breadth-first traversal of the Trie to yield words in word length order (shortest first) *bfs() { const q = [this.#root, ""]; let i = 0; while (i < q.length) { const node = q[i++]; const path = q[i++]; if (node.isWord) { yield path; } for (const [ch, child] of node.children) { q.push(child, path + ch); } } } // Empty the trie clear() { this.#root = new TrieNode(); return this; } // Show the trie as a horizontally laid out tree with word ending characters indicated toDot(options = {}) { const { rankDir = "LR", scale = 1, compact = true, fillClr = (node) => (node.isWord ? "lightblue" : "white"), labelClr = () => "black" } = options; let id = 0; const ids = new Map(); const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const visit = (node, label = "", parentId = null) => { const thisId = id++; ids.set(node, thisId); const shape = node.isWord ? "doublecircle" : "circle"; lines.push( ` ${thisId} [label="${label}", style=filled, fillcolor=${fillClr( node )}, fontcolor=${labelClr(node)}, shape=${shape}];` ); if (parentId !== null) { lines.push(` ${parentId} -> ${thisId};`); } for (const [ch, child] of node.children) { visit(child, ch, thisId); } }; visit(this.#root, "•"); lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } // --------------------------------------- Private helper methods // Depth-first traversal of the Trie to yield words in lexicographic order // To use via the API just iterate over the entire Trie *#dfsLex(node = this.#root, path = "") { if (node.isWord) { yield path; } const keys = [...node.children.keys()].sort((a, b) => a.localeCompare(b)); for (const ch of keys) { yield* this.#dfsLex(node.children.get(ch), path + ch); } } #walk(prefix) { let node = this.#root; for (const ch of prefix) { node = node.children.get(ch); if (!node) return null; } return node; } }3d:T17c3,display(md`\`▶ SuffixTrie\``); // In place of cell introspection class SuffixTrie { #root = new SuffixTrieNode(); #seq = ""; #symbolCount = 0; constructor(seq = "") { this.insertSuffixes(seq); } // Iterate over all distinct factors in lexicographic order *[Symbol.iterator]() { yield* this.#dfsLex(); } // Insert every suffix of the given sequence into the suffix trie. // Each Unicode code point is treated as one symbol. insertSuffixes(seq) { this.clear(); this.#seq = seq; const symbols = [...seq]; this.#symbolCount = symbols.length; for (let start = 0; start < symbols.length; start++) { this.#insertSuffix(symbols, start); } return this; } // Does the given pattern occur as a substring? has(pattern) { return this.#walk(pattern) !== null; } // Return all starting positions at which the pattern occurs positionsOf(pattern) { if (pattern.length === 0) { return [...Array(this.#symbolCount + 1).keys()]; } const node = this.#walk(pattern); return node ? [...node.positions] : []; } // Depth-first traversal yielding all distinct factors *dfs(node = this.#root, path = "") { for (const [ch, child] of node.children) { const factor = path + ch; yield factor; yield* this.dfs(child, factor); } } // Breadth-first traversal yielding all distinct factors in length order *bfs() { const q = [this.#root, ""]; let i = 0; while (i < q.length) { const node = q[i++]; const path = q[i++]; for (const [ch, child] of node.children) { const factor = path + ch; yield factor; q.push(child, factor); } } } // Depth-first traversal yielding factors with occurrence positions *entries(node = this.#root, path = "") { for (const [ch, child] of node.children) { const factor = path + ch; yield { factor, positions: [...child.positions], count: child.positions.length }; yield* this.entries(child, factor); } } // Yield all distinct factors up to a maximum length *factors(options = {}) { const {maxLength = Infinity, minLength = 1} = options; yield* this.#factors(this.#root, "", {minLength, maxLength}); } // Yield all distinct factors up to a maximum length, with positions *factorEntries(options = {}) { const {maxLength = Infinity, minLength = 1} = options; yield* this.#factorEntries(this.#root, "", {minLength, maxLength}); } // Empty the suffix trie clear() { this.#root = new SuffixTrieNode(); this.#seq = ""; this.#symbolCount = 0; return this; } // Show the suffix trie as a horizontally laid out tree toDot(options = {}) { const { rankDir = "LR", scale = 1, compact = true, showPositions = false, fillClr = (node) => (node.positions.length ? "lightblue" : "white"), labelClr = () => "black" } = options; let id = 0; const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const visit = (node, label = "", parentId = null) => { const thisId = id++; const posLabel = showPositions && node.positions.length ? `\\n[${node.positions.join(",")}]` : ""; const nodeLabel = `${this.#esc(label)}${posLabel}`; lines.push( ` ${thisId} [label="${nodeLabel}", style=filled, fillcolor="${fillClr( node )}", fontcolor="${labelClr(node)}", shape=circle];` ); if (parentId !== null) { lines.push(` ${parentId} -> ${thisId};`); } for (const [ch, child] of node.children) { visit(child, ch, thisId); } }; visit(this.#root, "•"); lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } // --------------------------------------- Private helper methods #insertSuffix(symbols, start) { let node = this.#root; for (let i = start; i < symbols.length; i++) { const symbol = symbols[i]; if (!node.children.has(symbol)) { node.children.set(symbol, new SuffixTrieNode()); } node = node.children.get(symbol); node.positions.push(start); // Positions are Unicode code-point indices. } } #walk(pattern) { let node = this.#root; for (const ch of pattern) { node = node.children.get(ch); if (!node) { return null; } } return node; } // Depth-first traversal yielding factors in lexicographic order *#dfsLex(node = this.#root, path = "") { const keys = [...node.children.keys()].sort((a, b) => a.localeCompare(b)); for (const ch of keys) { const factor = path + ch; yield factor; yield* this.#dfsLex(node.children.get(ch), factor); } } *#factors(node, path, options, depth = 0) { const {minLength, maxLength} = options; if (depth >= maxLength) { return; } for (const [symbol, child] of node.children) { const factor = path + symbol; const factorLength = depth + 1; if (factorLength >= minLength) { yield factor; } yield* this.#factors(child, factor, options, factorLength); } } *#factorEntries(node, path, options, depth = 0) { const {minLength, maxLength} = options; if (depth >= maxLength) { return; } for (const [symbol, child] of node.children) { const factor = path + symbol; const factorLength = depth + 1; if (factorLength >= minLength) { yield { factor, positions: [...child.positions], count: child.positions.length }; } yield* this.#factorEntries(child, factor, options, factorLength); } } #esc(value) { return `${value}`.replaceAll("\\", "\\\\").replaceAll('"', '\\"'); } }3e:Tea6,display(md`\`▶ RopeNode\``); // In place of cell introspection class RopeNode { constructor(text = null, left = null, right = null) { this.text = text; // String at leaf, or null for internal node this.left = left; this.right = right; this.height = 1; this.weight = RopeNode.#len(left); } static length(node) { return RopeNode.#len(node); } // Join: all characters in A precede all characters in B. static join(A, B) { if (!A) { return B; } if (!B) { return A; } // Descend the taller tree until the two heights are compatible. if (RopeNode.#h(A) > RopeNode.#h(B) + 1) { A.right = RopeNode.join(A.right, B); return RopeNode.#rebalance(A); } if (RopeNode.#h(B) > RopeNode.#h(A) + 1) { B.left = RopeNode.join(A, B.left); return RopeNode.#rebalance(B); } return RopeNode.#update(new RopeNode(null, A, B)); } // Split T at index i -> [L, R] static split(T, i) { if (!T) { return [null, null]; } if (T.text !== null) { // Leaf return i <= 0 ? [null, T] : i >= T.text.length ? [T, null] : [new RopeNode(T.text.slice(0, i)), new RopeNode(T.text.slice(i))]; } const leftLen = T.weight; if (i < leftLen) { const [L, L2] = RopeNode.split(T.left, i); return [L, RopeNode.join(L2, T.right)]; } if (i > leftLen) { const [R1, R] = RopeNode.split(T.right, i - leftLen); return [RopeNode.join(T.left, R1), R]; } // Cut between left and right return [T.left, T.right]; } static forEachLeaf(node, fn) { if (!node) { return; } if (node.text !== null) { fn(node.text); return; } RopeNode.forEachLeaf(node.left, fn); RopeNode.forEachLeaf(node.right, fn); } // Visit only the parts of leaves intersecting [start, end). static forEachLeafInRange(node, start, end, fn) { if (!node || start >= end) { return; } if (node.text !== null) { fn(node.text.slice(start, end)); return; } if (start < node.weight) { RopeNode.forEachLeafInRange( node.left, start, Math.min(end, node.weight), fn ); } if (end > node.weight) { RopeNode.forEachLeafInRange( node.right, Math.max(0, start - node.weight), end - node.weight, fn ); } } // ----------------- Private helper methods static #len(node) { return !node ? 0 : node.text !== null ? node.text.length : node.weight + RopeNode.#len(node.right); } static #h(node) { return node ? node.height : 0; } static #update(node) { if (!node) { return node; } node.height = 1 + Math.max(RopeNode.#h(node.left), RopeNode.#h(node.right)); node.weight = RopeNode.length(node.left); return node; } static #bf(node) { return node ? RopeNode.#h(node.left) - RopeNode.#h(node.right) : 0; } static #rotRight(a) { const b = a.left; a.left = b.right; b.right = a; RopeNode.#update(a); return RopeNode.#update(b); } static #rotLeft(a) { const b = a.right; a.right = b.left; b.left = a; RopeNode.#update(a); return RopeNode.#update(b); } static #rebalance(node) { RopeNode.#update(node); const bf = RopeNode.#bf(node); if (bf > 1) { if (RopeNode.#bf(node.left) < 0) { node.left = RopeNode.#rotLeft(node.left); } return RopeNode.#rotRight(node); } if (bf < -1) { if (RopeNode.#bf(node.right) > 0) { node.right = RopeNode.#rotRight(node.right); } return RopeNode.#rotLeft(node); } return node; } }3f:T14e8,display(md`\`▶ Rope\``); // In place of cell introspection class Rope { #chunkSize; constructor(text = "", {chunkSize = 1024} = {}) { this.#chunkSize = Math.max(16, chunkSize); this.root = Rope.#fromString(text, this.#chunkSize); } get length() { return RopeNode.length(this.root); } toString() { let out = ""; RopeNode.forEachLeaf(this.root, (text) => { out += text; }); return out; } charAt(i) { if (i < 0) { return ""; } let [node, index] = [this.root, i]; while (node && node.text === null) { if (index < node.weight) { node = node.left; } else { index -= node.weight; node = node.right; } } if (!node || node.text === null) { return ""; } return node.text[index] ?? ""; } substring(a = 0, b = this.length) { const length = this.length; a = Rope.#substringIndex(a, length); b = Rope.#substringIndex(b, length); // Argument swap is to match convention of String's substring() argument order if (a > b) { [a, b] = [b, a]; } let out = ""; RopeNode.forEachLeafInRange(this.root, a, b, (text) => { out += text; }); return out; } concat(other) { const right = (() => { if (typeof other === "string") { return Rope.#fromString(other, this.#chunkSize); } if (other instanceof Rope) { // Copy the incoming rope so subsequent balancing cannot modify it. return Rope.#fromString(other.toString(), this.#chunkSize); } throw new TypeError("Rope.concat expects a string or Rope"); })(); this.root = RopeNode.join(this.root, right); return this; } insert(i, text) { if (!text) { return this; } if (i < 0) { i = 0; } if (i > this.length) { i = this.length; } const [L, R] = RopeNode.split(this.root, i); const M = Rope.#fromString(text, this.#chunkSize); this.root = RopeNode.join(RopeNode.join(L, M), R); return this; } delete(a, b) { if (a < 0) { a = 0; } if (b > this.length) { b = this.length; } if (a >= b) { return this; } const [L, t1] = RopeNode.split(this.root, a); const [, R] = RopeNode.split(t1, b - a); this.root = RopeNode.join(L, R); return this; } toDot(options = {}) { const { rankDir = "LR", scale = 1, compact = true, fillClr = (node) => (node.text !== null ? "lightblue" : "white"), labelClr = () => "black", maxLeafChars = 24 } = options; const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const esc = (text) => text.replace(/\\/g, "\\\\").replace(/"/g, '\\"').replace(/\n/g, "⏎"); let id = 0; const visit = (node) => { const thisId = `n${id++}`; if (!node) { lines.push(` ${thisId} [label="∅", shape=plaintext];`); return thisId; } const isLeaf = node.text !== null; const shape = isLeaf ? "box" : "ellipse"; const fill = fillClr(node); const font = labelClr(node); let label; if (isLeaf) { const text = node.text.length <= maxLeafChars ? node.text : `${node.text.slice(0, maxLeafChars)}…`; label = `"${esc(text)}\\n(len:${node.text.length})"`; } else { label = `"w:${node.weight}"`; } lines.push( ` ${thisId} [label=${label}, style=filled, fillcolor=${fill}, fontcolor=${font}, shape=${shape}];` ); if (!isLeaf) { if (node.left) { const leftId = visit(node.left); lines.push(` ${thisId} -> ${leftId};`); } if (node.right) { const rightId = visit(node.right); lines.push(` ${thisId} -> ${rightId};`); } } return thisId; }; if (this.root) { visit(this.root); } else { lines.push(` n0 [label="∅", shape=plaintext];`); } lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } // ---------------- Private helpers static #substringIndex(value, length) { const n = Number(value); if (Number.isNaN(n) || n <= 0) { return 0; } if (n >= length) { return length; } return Math.trunc(n); } static #fromString(text, chunkSize) { if (!text) { return null; } // Build a nearly balanced rope by chunking then folding with joins. const leaves = []; for (let i = 0; i < text.length; i += chunkSize) { leaves.push(new RopeNode(text.slice(i, i + chunkSize))); } if (leaves.length === 1) { return leaves[0]; } // Bottom-up pairwise joining keeps height to around log n. let curr = leaves; while (curr.length > 1) { const next = []; for (let i = 0; i < curr.length; i += 2) { if (i + 1 < curr.length) { next.push(RopeNode.join(curr[i], curr[i + 1])); } else { next.push(curr[i]); } } curr = next; } return curr[0]; } }40:T1edb,display(md`\`▶ KdTree\``); // In place of cell introspection class KdTree { constructor(points = [], coordKeys = ["x", "y"]) { if (coordKeys === null) { coordKeys = points.length > 0 ? Object.keys(points[0]).filter( (k) => typeof points[0][k] === "number" ) : []; } if (coordKeys.length < 1) { throw new Error("KdTree: need at least one numeric key"); } this.axisKeys = [...coordKeys]; this.k = coordKeys.length; this.root = points.length > 0 ? this.#buildBalanced(points) : null; } insert(pt) { const insertRec = (node, depth = 0) => { if (!node) { return new KdTreeNode(pt, depth % this.k); } const axis = node.axis; const key = this.axisKeys[axis]; const delta = pt[key] - node.pt[key]; if (delta < 0) { node.setLeft(insertRec(node.left, depth + 1)); } else if (delta > 0 || !this.#equal(pt, node.pt)) { node.setRight(insertRec(node.right, depth + 1)); } return node; }; this.root = insertRec(this.root); return this; } find(target) { let node = this.root; let depth = 0; while (node) { if (this.#equal(node.pt, target)) { return node; } const key = this.axisKeys[depth % this.k]; if (target[key] < node.pt[key]) { node = node.left; } else { node = node.right; } depth++; } return null; } clear() { this.root = null; return this; } *[Symbol.iterator]() { yield* this.spatialMedian(); } *dfsPreOrder(node = this.root) { if (!node) { return; } yield node.pt; yield* this.dfsPreOrder(node.left); yield* this.dfsPreOrder(node.right); } *bfs() { if (!this.root) { return; } const queue = [this.root]; let head = 0; while (head < queue.length) { const node = queue[head++]; yield node.pt; if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } } *spatialMedian() { const pts = [...this.dfsPreOrder()]; yield* this.#recursiveMedian(pts); } rebalance() { const pts = [...this.dfsPreOrder()]; this.root = this.#buildBalanced(pts); return this; } *rangeQuery(minPt, maxPt, node = this.root) { if (!node) { return; } if (this.#inBox(node.pt, minPt, maxPt)) { yield node.pt; } const axis = node.axis; const key = this.axisKeys[axis]; if (minPt[key] <= node.pt[key]) { yield* this.rangeQuery(minPt, maxPt, node.left); } if (maxPt[key] >= node.pt[key]) { yield* this.rangeQuery(minPt, maxPt, node.right); } } pointsWithinRadius(queryPt, r) { const r2 = r * r; const visit = function* (node) { if (!node) { return; } const d = this.#distSq(queryPt, node.pt); if (d <= r2) { yield node.pt; } const axis = node.axis; const key = this.axisKeys[axis]; const delta = queryPt[key] - node.pt[key]; const [first, second] = delta < 0 ? [node.left, node.right] : [node.right, node.left]; yield* visit.call(this, first); if (delta * delta <= r2) { yield* visit.call(this, second); } }; return visit.call(this, this.root); } nearestNeighbour(queryPt, excludeSelf = false) { let best = null; let bestDistSq = Infinity; const search = (node) => { if (!node) { return; } const d = this.#distSq(queryPt, node.pt); if (!excludeSelf || !this.#equal(queryPt, node.pt)) { if (d < bestDistSq) { best = node; bestDistSq = d; } } const axis = node.axis; const key = this.axisKeys[axis]; const delta = queryPt[key] - node.pt[key]; const [first, second] = delta < 0 ? [node.left, node.right] : [node.right, node.left]; search(first); if (delta * delta < bestDistSq) { search(second); } }; search(this.root); return best?.pt ?? null; } kNearestNeighbours(queryPt, k, {sorted = false} = {}) { if (k <= 0 || !this.root) { return []; } const heap = new BoundedPriorityQueue(k); const search = (node) => { if (!node) { return; } const distSq = this.#distSq(queryPt, node.pt); heap.insert(node.pt, distSq); const axis = node.axis; const key = this.axisKeys[axis]; const delta = queryPt[key] - node.pt[key]; const [first, second] = delta < 0 ? [node.left, node.right] : [node.right, node.left]; search(first); if (heap.size() < k || delta * delta < heap.peekPriority()) { search(second); } }; search(this.root); return sorted ? heap.toSortedArray() : heap.toArray(); } toArray(traversal = "bfs") { switch (traversal) { case "pre": return [...this.dfsPreOrder()]; case "bfs": return [...this.bfs()]; case "median": return [...this.spatialMedian()]; default: throw new Error(`KdTree: Unsupported traversal: ${traversal}`); } } toDot(options = {}) { const { rankDir = "TB", scale = 1, compact = true, fillClr = () => "white", labelClr = () => "black", label = (node) => { const coords = Object.entries(node.pt) .map(([k, v]) => `${k}:${v}`) .join(", "); return `{${coords}}`; } } = options; const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ' node [margin="0.05,0" width=0 height=0];' : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const idMap = new Map(); let idCounter = 0; const visit = (node) => { if (!node) { return; } const id = `n${idCounter++}`; idMap.set(node, id); lines.push( ` ${id} [label="${label(node)}" style=filled fillcolor=${fillClr( node )} fontcolor=${labelClr(node)}];` ); if (node.left) { visit(node.left); lines.push(` ${id} -> ${idMap.get(node.left)};`); } if (node.right) { visit(node.right); lines.push(` ${id} -> ${idMap.get(node.right)};`); } }; visit(this.root); lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } // --------------------- Private helpers --------------------- *#recursiveMedian(points, depth = 0) { if (points.length === 0) { return; } const axis = depth % this.k; const key = this.axisKeys[axis]; const sorted = [...points].sort((a, b) => a[key] - b[key]); const mid = Math.floor(sorted.length / 2); yield sorted[mid]; yield* this.#recursiveMedian(sorted.slice(0, mid), depth + 1); yield* this.#recursiveMedian(sorted.slice(mid + 1), depth + 1); } #buildBalanced(points, depth = 0) { if (points.length === 0) { return null; } const axis = depth % this.k; const key = this.axisKeys[axis]; const sorted = [...points].sort((a, b) => a[key] - b[key]); const mid = Math.floor(sorted.length / 2); const node = new KdTreeNode(sorted[mid], axis); node.setLeft(this.#buildBalanced(sorted.slice(0, mid), depth + 1)); node.setRight(this.#buildBalanced(sorted.slice(mid + 1), depth + 1)); return node; } #equal(a, b) { return this.axisKeys.every((key) => a[key] === b[key]); } #distSq(a, b) { return this.axisKeys.reduce((sum, key) => { const d = a[key] - b[key]; return sum + d * d; }, 0); } #inBox(pt, minPt, maxPt) { return this.axisKeys.every( (key) => pt[key] >= minPt[key] && pt[key] <= maxPt[key] ); } }41:T10ed,display(md`\`▶ QuadtreeNode\``); // In place of cell introspection class QuadtreeNode { #boundary; #capacity; #items = []; #divided = false; #nw = null; #ne = null; #sw = null; #se = null; constructor(boundary, capacity) { this.#boundary = boundary; this.#capacity = capacity; } get boundary() { return this.#boundary; } get isDivided() { return this.#divided; } get size() { return this.#items.length; } children() { if (!this.#divided) { return []; } return [ ["NW", this.#nw], ["NE", this.#ne], ["SW", this.#sw], ["SE", this.#se] ]; } itemsSnapshot() { return [...this.#items]; } insert(item, policy, maxDepth, depth = 0) { if (!policy.fits(this.#boundary, item)) { return false; } if ( !this.#divided && (this.#items.length < this.#capacity || depth >= maxDepth) ) { this.#items.push(item); return true; } if (!this.#divided) { this.#subdivide(); const stay = []; for (const old of this.#items) { if (!this.#routeToChild(old, policy, maxDepth, depth)) { stay.push(old); } } this.#items = stay; } if (this.#routeToChild(item, policy, maxDepth, depth)) { return true; } this.#items.push(item); // Straddler or maxDepth reached return true; } // Range query (policy-agnostic) query(range, found, policy) { if (!policy.intersects(this.#boundary, range)) { return found; } if (!this.#divided) { for (const item of this.#items) { if (policy.fits(range, item)) { found.push(item); } } } else { this.#nw.query(range, found, policy); this.#ne.query(range, found, policy); this.#sw.query(range, found, policy); this.#se.query(range, found, policy); for (const item of this.#items) { if (policy.fits(range, item)) { found.push(item); } } } return found; } // Yield all items in the subtree *items() { if (!this.#divided) { yield* this.#items; return; } yield* this.#nw.items(); yield* this.#ne.items(); yield* this.#sw.items(); yield* this.#se.items(); yield* this.#items; } // Attach an existing node as the specified quadrant; create missing siblings attachChild(direction, child) { if (!this.#divided) { this.#subdivide(); } if (direction === "NW") { this.#nw = child; } if (direction === "NE") { this.#ne = child; } if (direction === "SW") { this.#sw = child; } if (direction === "SE") { this.#se = child; } } // ------------------------------ Private helpers #subdivide() { const {x, y, halfWidth, halfHeight} = this.#boundary; const hw2 = halfWidth / 2; const hh2 = halfHeight / 2; const make = (dx, dy) => ({ x: x + dx * hw2, y: y + dy * hh2, halfWidth: hw2, halfHeight: hh2 }); this.#nw = new QuadtreeNode(make(-1, -1), this.#capacity); this.#ne = new QuadtreeNode(make(1, -1), this.#capacity); this.#sw = new QuadtreeNode(make(-1, 1), this.#capacity); this.#se = new QuadtreeNode(make(1, 1), this.#capacity); this.#divided = true; } #childByIndex(idx) { if (idx === 0) { return this.#nw; } if (idx === 1) { return this.#ne; } if (idx === 2) { return this.#sw; } if (idx === 3) { return this.#se; } return null; } #routeToChild(item, policy, maxDepth, depth) { if (typeof policy.childIndex === "function") { const idx = policy.childIndex(this.#boundary, item); if (idx >= 0) { const child = this.#childByIndex(idx); if (child && child.insert(item, policy, maxDepth, depth + 1)) { return true; } } } // Fallback: try all children in NW,NE,SW,SE order return this.#tryInsertIntoChildren(item, policy, maxDepth, depth); } #tryInsertIntoChildren(item, policy, maxDepth, depth) { const children = [this.#nw, this.#ne, this.#sw, this.#se]; for (const child of children) { if (child.insert(item, policy, maxDepth, depth + 1)) { return true; } } return false; } }42:T3458,display(md`\`▶ Quadtree\``); // In place of cell introspection class Quadtree { #capacity; #autoResize; #strict; #maxDepth; #square; #policy; root = null; constructor({ boundary = null, capacity = 4, autoResize = true, strict = false, maxDepth = 64, square = true, policy } = {}) { if (!policy) { throw new Error("Quadtree: 'policy' is required"); } if (!Number.isInteger(capacity) || capacity < 1) { throw new RangeError("Quadtree: capacity must be a positive integer"); } if ( maxDepth !== Infinity && (!Number.isInteger(maxDepth) || maxDepth < 0) ) { throw new RangeError( "Quadtree: maxDepth must be a non-negative integer or Infinity" ); } if (boundary !== null) { Quadtree.#validateBounds(boundary, { label: "root boundary", allowZeroSize: false }); } this.#capacity = capacity; this.#autoResize = autoResize; this.#strict = strict; this.#maxDepth = maxDepth; this.#square = square; this.#policy = policy; this.root = boundary ? new QuadtreeNode({...boundary}, this.#capacity) : null; } // Insert item and auto-resize if enabled insert(item) { const itemBounds = this.#itemBounds(item); if (!this.root) { const boundary = this.#bootstrapBounds(itemBounds); this.root = new QuadtreeNode(boundary, this.#capacity); } const fits = this.#policy.fits(this.root.boundary, item); if (!this.#autoResize && !fits) { if (this.#strict) { throw new RangeError( "Quadtree: item outside root boundary in strict mode" ); } return this; } if (this.#autoResize && !fits) { this.#growToFit(item, itemBounds); } this.root.insert(item, this.#policy, this.#maxDepth, 0); return this; } // Does the given item fit within the existing quadtree? fitsRoot(item) { this.#itemBounds(item); if (!this.root) { return true; } return this.#policy.fits(this.root.boundary, item); } // Remove all nodes clear() { this.root = null; return this; } get capacity() { return this.#capacity; } get maxDepth() { return this.#maxDepth; } get bounds() { return this.root ? {...this.root.boundary} : null; } // Iterate all items in the tree *items() { if (!this.root) { return; } yield* this.root.items(); } *[Symbol.iterator]() { yield* this.items(); } *cells(options = {}) { const { leavesOnly = false, // if true, yield only leaf cells includeInternal = true, // if false, suppress internal cells order = "pre" // "pre" (DFS pre-order) or "bfs" } = options; if (order !== "pre" && order !== "bfs") { throw new Error(`Quadtree: Unsupported cell traversal order: ${order}`); } if (!this.root) { return; } if (order === "bfs") { const queue = [{node: this.root, depth: 0}]; let head = 0; while (head < queue.length) { const {node, depth} = queue[head++]; const isLeaf = !node.isDivided; if (isLeaf || (!leavesOnly && includeInternal)) { const b = node.boundary; yield { boundary: { x: b.x, y: b.y, halfWidth: b.halfWidth, halfHeight: b.halfHeight }, depth, isLeaf, size: node.size }; } if (!isLeaf) { // NW, NE, SW, SE for (const [, child] of node.children()) { if (child) { queue.push({node: child, depth: depth + 1}); } } } } return; } // DFS pre-order (default) const stack = [{node: this.root, depth: 0}]; while (stack.length > 0) { const {node, depth} = stack.pop(); const isLeaf = !node.isDivided; if (isLeaf || (!leavesOnly && includeInternal)) { const b = node.boundary; yield { boundary: { x: b.x, y: b.y, halfWidth: b.halfWidth, halfHeight: b.halfHeight }, depth, isLeaf, size: node.size }; } if (!isLeaf) { // Push children in reverse to visit NW->NE->SW->SE const kids = node.children(); for (let i = kids.length - 1; i >= 0; i--) { const [, child] = kids[i]; if (child) { stack.push({node: child, depth: depth + 1}); } } } } } toArray() { return [...this.items()]; } *rangeQuery(range) { Quadtree.#validateBounds(range, { label: "query range", allowZeroSize: true }); if (!this.root) { return; } const stack = [this.root]; while (stack.length > 0) { const node = stack.pop(); if (!this.#policy.intersects(node.boundary, range)) { continue; } if (!node.isDivided) { for (const item of node.itemsSnapshot()) { if (this.#policy.fits(range, item)) { yield item; } } continue; } // Push children in reverse to visit NW, NE, SW, SE. const children = node.children(); for (let i = children.length - 1; i >= 0; i--) { const [, child] = children[i]; if (child) { stack.push(child); } } // Region items that straddle child boundaries remain at internal nodes. for (const item of node.itemsSnapshot()) { if (this.#policy.fits(range, item)) { yield item; } } } } // Generate GraphViz DOT representation of the tree toDot(options = {}) { const { rankDir = "TB", scale = 1, compact = true, fillClr = () => "white", labelClr = () => "black", label = (d) => { const b = d.boundary; const t = d.isDivided ? "" : d.size > 1 ? `${d.size} items` : d.size > 0 ? `${d.size} item` : ""; return `${b.x - b.halfWidth},${b.y - b.halfHeight} to ${ b.x + b.halfWidth },${b.y + b.halfHeight}\\n${t}`; }, showItems = false, itemLabel = (it) => { if (it && typeof it === "object" && "x" in it && "y" in it) { return `(${it.x},${it.y})`; } if (it?.bounds) { const {x, y, halfWidth: hw, halfHeight: hh} = it.bounds; return `{${x - hw},${y - hh} to ${x + hw},${y + hh}]`; } return String(it); } } = options; if (!this.root) { return dot`digraph {}`; } const esc = (s) => String(s).replaceAll('"', '\\"'); const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const idMap = new Map(); let idCounter = 0; const visit = (node) => { if (!node) { return; } const id = `n${idCounter++}`; idMap.set(node, id); const fill = fillClr(node); const font = labelClr(node); const lbl = esc(label(node)); lines.push( ` ${id} [label="${lbl}" style=filled fillcolor=${fill} fontcolor=${font}];` ); if (!node.isDivided) { if (showItems && node.size > 0) { for (const it of node.itemsSnapshot()) { const iid = `n${idCounter++}`; const ilbl = esc(itemLabel(it)); lines.push( ` ${iid} [label="${ilbl}" shape=box style=dashed];`, ` ${id} -> ${iid} [style=dotted];` ); } } return; } for (const [dir, child] of node.children()) { if (child) { visit(child); const cid = idMap.get(child); lines.push( ` ${id} -> ${cid} [taillabel="${dir}" fontsize=6 labeldistance=2.5 labelangle=15];` ); } } }; visit(this.root); lines.push("}"); const spec = dot`${lines.join("\n")}`; if (scale === 1) { return spec; } else { return md`

${spec}

`; } } // ----------------------------- Static geometry utilities static minL1DistancePointAABB(p = {}, box = {}) { const {x = 0, y = 0} = p; const {minX = 0, minY = 0, maxX = 1, maxY = 1} = box; // Manhattan distance from point to axis-aligned rectangle const dx = Math.abs(x - Quadtree.#clamp(x, minX, maxX)); const dy = Math.abs(y - Quadtree.#clamp(y, minY, maxY)); return dx + dy; } static halfToMinMax(b = {}) { const {x = 32768, y = 32768, halfWidth = 32768, halfHeight = 32768} = b; return { minX: x - halfWidth, maxX: x + halfWidth, minY: y - halfHeight, maxY: y + halfHeight }; } static minMaxToHalf(box = {}) { const {minX = 0, minY = 0, maxX = 65536, maxY = 65536} = box; return { x: (minX + maxX) / 2, y: (minY + maxY) / 2, halfWidth: (maxX - minX) / 2, halfHeight: (maxY - minY) / 2 }; } static splitBox(box = {}) { const {minX = 0, minY = 0, maxX = 65536, maxY = 65536} = box; const mx = Math.floor((minX + maxX) / 2); const my = Math.floor((minY + maxY) / 2); return [ {dir: "NW", bounds: {minX, maxX: mx, minY: my + 1, maxY}}, {dir: "NE", bounds: {minX: mx + 1, maxX, minY: my + 1, maxY}}, {dir: "SW", bounds: {minX, maxX: mx, minY, maxY: my}}, {dir: "SE", bounds: {minX: mx + 1, maxX, minY, maxY: my}} ].filter( (q) => q.bounds.minX <= q.bounds.maxX && q.bounds.minY <= q.bounds.maxY ); } static intersectsAABB(a = {}, r = {}) { const {x: ax = 0, y: ay = 0, halfWidth: ahw = 0, halfHeight: ahh = 0} = a; const {x: rx = 0, y: ry = 0, halfWidth: rhw = 0, halfHeight: rhh = 0} = r; const [aMinX, aMaxX] = [ax - ahw, ax + ahw]; const [aMinY, aMaxY] = [ay - ahh, ay + ahh]; const [rMinX, rMaxX] = [rx - rhw, rx + rhw]; const [rMinY, rMaxY] = [ry - rhh, ry + rhh]; return !(rMinX > aMaxX || rMaxX < aMinX || rMinY > aMaxY || rMaxY < aMinY); } // ------------------------------ Private helpers static #clamp(v, lo, hi) { if (v < lo) { return lo; } if (v > hi) { return hi; } return v; } static #validateBounds( bounds, {label = "boundary", allowZeroSize = false} = {} ) { if (!bounds || typeof bounds !== "object") { throw new TypeError(`Quadtree: ${label} must be an object`); } for (const key of ["x", "y"]) { if (!Number.isFinite(bounds[key])) { throw new RangeError( `Quadtree: ${label}.${key} must be a finite number` ); } } for (const key of ["halfWidth", "halfHeight"]) { const value = bounds[key]; const valid = Number.isFinite(value) && (allowZeroSize ? value >= 0 : value > 0); if (!valid) { const requirement = allowZeroSize ? "a non-negative finite number" : "a positive finite number"; throw new RangeError( `Quadtree: ${label}.${key} must be ${requirement}` ); } } return bounds; } #itemBounds(item) { if (!item || typeof item !== "object") { throw new TypeError("Quadtree: item must be an object"); } const bounds = this.#policy.itemBounds(item); return Quadtree.#validateBounds(bounds, { label: "item bounds", allowZeroSize: true }); } #bootstrapBounds(itemBounds) { const halfWidth = Math.max(1, itemBounds.halfWidth); const halfHeight = Math.max(1, itemBounds.halfHeight); if (this.#square) { const halfSize = Math.max(halfWidth, halfHeight); return { x: itemBounds.x, y: itemBounds.y, halfWidth: halfSize, halfHeight: halfSize }; } return {x: itemBounds.x, y: itemBounds.y, halfWidth, halfHeight}; } #growToFit(item, itemBounds) { while (!this.#policy.fits(this.root.boundary, item)) { this.#enlargeRootToCover(itemBounds); } } #enlargeRootToCover(itemBounds) { const rootBounds = this.root.boundary; const halfSize = Math.max(rootBounds.halfWidth, rootBounds.halfHeight); const halfWidth = this.#square ? halfSize : rootBounds.halfWidth; const halfHeight = this.#square ? halfSize : rootBounds.halfHeight; const centreX = itemBounds.x >= rootBounds.x ? rootBounds.x + halfWidth : rootBounds.x - halfWidth; const centreY = itemBounds.y >= rootBounds.y ? rootBounds.y + halfHeight : rootBounds.y - halfHeight; const parentBounds = { x: centreX, y: centreY, halfWidth: halfWidth * 2, halfHeight: halfHeight * 2 }; // Also detects numeric overflow during repeated enlargement. Quadtree.#validateBounds(parentBounds, { label: "expanded root boundary", allowZeroSize: false }); const parent = new QuadtreeNode(parentBounds, this.#capacity); const direction = (rootBounds.y < centreY ? "N" : "S") + (rootBounds.x < centreX ? "W" : "E"); parent.attachChild(direction, this.root); this.root = parent; } }43:T48a,display(md`\`▶ PointQuadtree\``); // In place of cell introspection class PointQuadtree extends Quadtree { static #POLICY = { itemBounds(p) { return {x: p.x, y: p.y, halfWidth: 0, halfHeight: 0}; }, fits(b, p) { const [minX, maxX] = [b.x - b.halfWidth, b.x + b.halfWidth]; const [minY, maxY] = [b.y - b.halfHeight, b.y + b.halfHeight]; return p.x >= minX && p.x <= maxX && p.y >= minY && p.y <= maxY; }, childIndex(b, p) { const [cx, cy] = [b.x, b.y]; const [east, south] = [p.x >= cx, p.y >= cy]; if (!east && !south) { return 0; // NW } if (east && !south) { return 1; // NE } if (!east && south) { return 2; // SW } return 3; // SE }, intersects: Quadtree.intersectsAABB }; constructor(opts = {}) { const { boundary = null, capacity = 4, autoResize = true, maxDepth = Infinity, square = true, strict = false } = opts; super({ boundary, capacity, autoResize, maxDepth, square, strict, policy: PointQuadtree.#POLICY }); } }44:T6d2,display(md`\`▶ RegionQuadtree\``); // In place of cell introspection class RegionQuadtree extends Quadtree { static #POLICY = { itemBounds(region) { return region.bounds; }, fits(b, region) { const r = region.bounds; const [bMinX, bMaxX] = [b.x - b.halfWidth, b.x + b.halfWidth]; const [bMinY, bMaxY] = [b.y - b.halfHeight, b.y + b.halfHeight]; const [rMinX, rMaxX] = [r.x - r.halfWidth, r.x + r.halfWidth]; const [rMinY, rMaxY] = [r.y - r.halfHeight, r.y + r.halfHeight]; return ( rMinX >= bMinX && rMaxX <= bMaxX && rMinY >= bMinY && rMaxY <= bMaxY ); }, childIndex(b, region) { const r = region.bounds; const [cx, cy] = [b.x, b.y]; const [rMinX, rMaxX] = [r.x - r.halfWidth, r.x + r.halfWidth]; const [rMinY, rMaxY] = [r.y - r.halfHeight, r.y + r.halfHeight]; const whollyNorth = rMaxY <= cy; const whollySouth = rMinY >= cy; const whollyWest = rMaxX <= cx; const whollyEast = rMinX >= cx; if (whollyWest && whollyNorth) { return 0; // NW } if (whollyEast && whollyNorth) { return 1; // NE } if (whollyWest && whollySouth) { return 2; // SW } if (whollyEast && whollySouth) { return 3; // SE } return -1; // Straddles a split }, intersects: Quadtree.intersectsAABB }; constructor(opts = {}) { const { boundary = null, capacity = 4, autoResize = true, maxDepth = Infinity, square = true, strict = false } = opts; super({ boundary, capacity, autoResize, maxDepth, square, strict, policy: RegionQuadtree.#POLICY }); } }45:T1623,display(md`\`▶ OctreeNode\``); // In place of cell introspection class OctreeNode { #boundary; #capacity; #items = []; #divided = false; #nwb = null; #neb = null; #swb = null; #seb = null; // bottom layer (z < centre) #nwt = null; #net = null; #swt = null; #set = null; // top layer (z >= centre) constructor(boundary, capacity) { this.#boundary = boundary; // { x, y, z, halfWidth, halfHeight, halfDepth } this.#capacity = capacity; } get boundary() { return this.#boundary; } get isDivided() { return this.#divided; } get size() { return this.#items.length; } children() { if (!this.#divided) { return []; } // Fixed order: NWB, NEB, SWB, SEB, NWT, NET, SWT, SET return [ ["NWB", this.#nwb], ["NEB", this.#neb], ["SWB", this.#swb], ["SEB", this.#seb], ["NWT", this.#nwt], ["NET", this.#net], ["SWT", this.#swt], ["SET", this.#set] ]; } itemsSnapshot() { return [...this.#items]; } insert(item, policy, maxDepth, depth = 0) { if (!policy.fits(this.#boundary, item)) { return false; } if ( !this.#divided && (this.#items.length < this.#capacity || depth >= maxDepth) ) { this.#items.push(item); return true; } if (!this.#divided) { this.#subdivide(); const stay = []; for (const old of this.#items) { if (!this.#routeToChild(old, policy, maxDepth, depth)) { stay.push(old); } } this.#items = stay; } if (this.#routeToChild(item, policy, maxDepth, depth)) { return true; } this.#items.push(item); // Straddler or depth limit return true; } // Policy-agnostic range query (3D) query(range, found, policy) { if (!policy.intersects(this.#boundary, range)) { return found; } if (!this.#divided) { for (const it of this.#items) { if (policy.fits(range, it)) { found.push(it); } } } else { this.#nwb.query(range, found, policy); this.#neb.query(range, found, policy); this.#swb.query(range, found, policy); this.#seb.query(range, found, policy); this.#nwt.query(range, found, policy); this.#net.query(range, found, policy); this.#swt.query(range, found, policy); this.#set.query(range, found, policy); for (const it of this.#items) { if (policy.fits(range, it)) { found.push(it); } } } return found; } *items() { if (!this.#divided) { yield* this.#items; return; } yield* this.#nwb.items(); yield* this.#neb.items(); yield* this.#swb.items(); yield* this.#seb.items(); yield* this.#nwt.items(); yield* this.#net.items(); yield* this.#swt.items(); yield* this.#set.items(); yield* this.#items; } attachChild(direction, child) { if (!this.#divided) { this.#subdivide(); } if (direction === "NWB") { this.#nwb = child; } if (direction === "NEB") { this.#neb = child; } if (direction === "SWB") { this.#swb = child; } if (direction === "SEB") { this.#seb = child; } if (direction === "NWT") { this.#nwt = child; } if (direction === "NET") { this.#net = child; } if (direction === "SWT") { this.#swt = child; } if (direction === "SET") { this.#set = child; } } // ------------------------------ Private helpers #subdivide() { const {x, y, z, halfWidth, halfHeight, halfDepth} = this.#boundary; const hw2 = halfWidth / 2, hh2 = halfHeight / 2, hd2 = halfDepth / 2; const make = (dx, dy, dz) => ({ x: x + dx * hw2, y: y + dy * hh2, z: z + dz * hd2, halfWidth: hw2, halfHeight: hh2, halfDepth: hd2 }); // bottom layer (z < centre) this.#nwb = new OctreeNode(make(-1, -1, -1), this.#capacity); this.#neb = new OctreeNode(make(1, -1, -1), this.#capacity); this.#swb = new OctreeNode(make(-1, 1, -1), this.#capacity); this.#seb = new OctreeNode(make(1, 1, -1), this.#capacity); // top layer (z >= centre) this.#nwt = new OctreeNode(make(-1, -1, 1), this.#capacity); this.#net = new OctreeNode(make(1, -1, 1), this.#capacity); this.#swt = new OctreeNode(make(-1, 1, 1), this.#capacity); this.#set = new OctreeNode(make(1, 1, 1), this.#capacity); this.#divided = true; } #childByIndex(idx) { if (idx === 0) { return this.#nwb; } if (idx === 1) { return this.#neb; } if (idx === 2) { return this.#swb; } if (idx === 3) { return this.#seb; } if (idx === 4) { return this.#nwt; } if (idx === 5) { return this.#net; } if (idx === 6) { return this.#swt; } if (idx === 7) { return this.#set; } return null; } #routeToChild(item, policy, maxDepth, depth) { if (typeof policy.childIndex === "function") { const idx = policy.childIndex(this.#boundary, item); if (idx >= 0) { const child = this.#childByIndex(idx); if (child && child.insert(item, policy, maxDepth, depth + 1)) { return true; } } } // fallback: try all children const kids = [ this.#nwb, this.#neb, this.#swb, this.#seb, this.#nwt, this.#net, this.#swt, this.#set ]; for (const ch of kids) { if (ch.insert(item, policy, maxDepth, depth + 1)) { return true; } } return false; } }46:T3844,display(md`\`▶ Octree\``); // In place of cell introspection class Octree { #capacity; #autoResize; #strict; #maxDepth; #cube; #policy; root = null; constructor({ boundary = null, capacity = 4, autoResize = true, strict = false, maxDepth = Infinity, cube = true, policy } = {}) { if (!policy) { throw new Error("Octree: 'policy' is required"); } if (!Number.isInteger(capacity) || capacity < 1) { throw new RangeError("Octree: capacity must be a positive integer"); } if ( maxDepth !== Infinity && (!Number.isInteger(maxDepth) || maxDepth < 0) ) { throw new RangeError( "Octree: maxDepth must be a non-negative integer or Infinity" ); } if (boundary !== null) { Octree.#validateBounds(boundary, { label: "root boundary", allowZeroSize: false }); } this.#capacity = capacity; this.#autoResize = autoResize; this.#strict = strict; this.#maxDepth = maxDepth; this.#cube = cube; this.#policy = policy; this.root = boundary ? new OctreeNode({...boundary}, this.#capacity) : null; } insert(item) { const itemBounds = this.#itemBounds(item); if (!this.root) { const boundary = this.#bootstrapBounds(itemBounds); this.root = new OctreeNode(boundary, this.#capacity); } const fits = this.#policy.fits(this.root.boundary, item); if (!this.#autoResize && !fits) { if (this.#strict) { throw new RangeError( "Octree: Item outside root boundary in strict mode" ); } return this; } if (this.#autoResize && !fits) { this.#growToFit(item, itemBounds); } this.root.insert(item, this.#policy, this.#maxDepth, 0); return this; } fitsRoot(item) { if (!this.root) { return true; } this.#itemBounds(item); return this.#policy.fits(this.root.boundary, item); } clear() { this.root = null; return this; } get capacity() { return this.#capacity; } get maxDepth() { return this.#maxDepth; } get bounds() { return this.root ? {...this.root.boundary} : null; } *items() { if (!this.root) { return; } yield* this.root.items(); } *[Symbol.iterator]() { yield* this.items(); } *cells(options = {}) { const { leavesOnly = false, // If true, yield only leaf cells includeInternal = true, // If false, suppress internal cells order = "pre" // "pre" (DFS pre-order) or "bfs" } = options; if (!this.root) { return; } if (order !== "pre" && order !== "bfs") { throw new Error(`Octree: Unsupported cell traversal order: ${order}`); } const emit = (node, depth) => { const isLeaf = !node.isDivided; // leavesOnly takes precedence over includeInternal. if (!isLeaf && (leavesOnly || !includeInternal)) { return null; } const b = node.boundary; return { boundary: { x: b.x, y: b.y, z: b.z, halfWidth: b.halfWidth, halfHeight: b.halfHeight, halfDepth: b.halfDepth }, depth, isLeaf, size: node.size }; }; if (order === "bfs") { const queue = [{node: this.root, depth: 0}]; let head = 0; while (head < queue.length) { const {node, depth} = queue[head++]; const record = emit(node, depth); if (record) { yield record; } if (!node.isDivided) { continue; } for (const [, child] of node.children()) { if (child) { queue.push({node: child, depth: depth + 1}); } } } return; } // DFS pre-order (default) const stack = [{node: this.root, depth: 0}]; while (stack.length > 0) { const {node, depth} = stack.pop(); const record = emit(node, depth); if (record) { yield record; } if (!node.isDivided) { continue; } // Push children in reverse so we visit in the order: // NWB, NEB, SWB, SEB, NWT, NET, SWT, SET const children = node.children(); for (let i = children.length - 1; i >= 0; i--) { const [, child] = children[i]; if (child) { stack.push({node: child, depth: depth + 1}); } } } } toArray() { return [...this.items()]; } *rangeQuery(range) { if (!this.root) { return; } Octree.#validateBounds(range, { label: "query range", allowZeroSize: true }); const stack = [this.root]; while (stack.length > 0) { const node = stack.pop(); if (!this.#policy.intersects(node.boundary, range)) { continue; } if (!node.isDivided) { for (const item of node.itemsSnapshot()) { if (this.#policy.fits(range, item)) { yield item; } } continue; } const children = node.children(); for (let i = children.length - 1; i >= 0; i--) { const [, child] = children[i]; if (child) { stack.push(child); } } // Items stored at internal nodes, such as straddling regions. for (const item of node.itemsSnapshot()) { if (this.#policy.fits(range, item)) { yield item; } } } } toDot(options = {}) { const { rankDir = "TB", scale = 1, compact = true, fillClr = () => "white", labelClr = () => "black", label = (d) => { const b = d.boundary; const text = d.isDivided ? "" : d.size > 1 ? `${d.size} items` : d.size > 0 ? `${d.size} item` : ""; return ( `${b.x - b.halfWidth},${b.y - b.halfHeight},${ b.z - b.halfDepth } to ` + `${b.x + b.halfWidth},${b.y + b.halfHeight},${ b.z + b.halfDepth }\\n${text}` ); }, showItems = false, itemLabel = (item) => { if ( item && typeof item === "object" && "x" in item && "y" in item && "z" in item ) { return `(${item.x},${item.y},${item.z})`; } if (item?.bounds) { const { x, y, z, halfWidth: hw, halfHeight: hh, halfDepth: hd } = item.bounds; return `{${x - hw},${y - hh},${z - hd} to ${x + hw},${ y + hh },${z + hd}}`; } return String(item); } } = options; if (!this.root) { return dot`digraph {}`; } const esc = (text) => String(text).replaceAll('"', '\\"'); const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const idMap = new Map(); let idCounter = 0; const visit = (node) => { const id = `n${idCounter++}`; idMap.set(node, id); const fill = fillClr(node); const font = labelClr(node); const nodeLabel = esc(label(node)); lines.push( ` ${id} [label="${nodeLabel}" style=filled fillcolor=${fill} fontcolor=${font}];` ); if (!node.isDivided) { if (showItems && node.size > 0) { for (const item of node.itemsSnapshot()) { const itemId = `n${idCounter++}`; const itemText = esc(itemLabel(item)); lines.push( ` ${itemId} [label="${itemText}" shape=box style=dashed];`, ` ${id} -> ${itemId} [style=dotted];` ); } } return; } for (const [direction, child] of node.children()) { if (!child) { continue; } visit(child); const childId = idMap.get(child); lines.push( ` ${id} -> ${childId} [taillabel="${direction}" fontsize=6 labeldistance=2.5 labelangle=15];` ); } }; visit(this.root); lines.push("}"); const spec = dot`${lines.join("\n")}`; return scale === 1 ? spec : md`

${spec}

`; } // ----------------------------- Static geometry utilities static minL1DistancePointAABB3D(point, box) { const dx = Math.abs(point.x - Octree.#clamp(point.x, box.minX, box.maxX)); const dy = Math.abs(point.y - Octree.#clamp(point.y, box.minY, box.maxY)); const dz = Math.abs(point.z - Octree.#clamp(point.z, box.minZ, box.maxZ)); return dx + dy + dz; } static halfToMinMax(boundary) { return { minX: boundary.x - boundary.halfWidth, maxX: boundary.x + boundary.halfWidth, minY: boundary.y - boundary.halfHeight, maxY: boundary.y + boundary.halfHeight, minZ: boundary.z - boundary.halfDepth, maxZ: boundary.z + boundary.halfDepth }; } static minMaxToHalf(box) { return { x: (box.minX + box.maxX) / 2, y: (box.minY + box.maxY) / 2, z: (box.minZ + box.maxZ) / 2, halfWidth: (box.maxX - box.minX) / 2, halfHeight: (box.maxY - box.minY) / 2, halfDepth: (box.maxZ - box.minZ) / 2 }; } static splitBox(box) { const mx = Math.floor((box.minX + box.maxX) / 2); const my = Math.floor((box.minY + box.maxY) / 2); const mz = Math.floor((box.minZ + box.maxZ) / 2); const xs = [ [box.minX, mx], [mx + 1, box.maxX] ]; const ys = [ [box.minY, my], [my + 1, box.maxY] ]; const zs = [ [box.minZ, mz], [mz + 1, box.maxZ] ]; const result = []; for (const [minX, maxX] of xs) { for (const [minY, maxY] of ys) { for (const [minZ, maxZ] of zs) { if (minX <= maxX && minY <= maxY && minZ <= maxZ) { result.push({ minX, maxX, minY, maxY, minZ, maxZ }); } } } } return result; } static intersectsAABB3D(a, r) { const [aMinX, aMaxX] = [a.x - a.halfWidth, a.x + a.halfWidth]; const [aMinY, aMaxY] = [a.y - a.halfHeight, a.y + a.halfHeight]; const [aMinZ, aMaxZ] = [a.z - a.halfDepth, a.z + a.halfDepth]; const [rMinX, rMaxX] = [r.x - r.halfWidth, r.x + r.halfWidth]; const [rMinY, rMaxY] = [r.y - r.halfHeight, r.y + r.halfHeight]; const [rMinZ, rMaxZ] = [r.z - r.halfDepth, r.z + r.halfDepth]; return !( rMinX > aMaxX || rMaxX < aMinX || rMinY > aMaxY || rMaxY < aMinY || rMinZ > aMaxZ || rMaxZ < aMinZ ); } // ----------------------------- Private helpers static #clamp = (value, min, max) => value < min ? min : value > max ? max : value; static #validateBounds( bounds, {label = "boundary", allowZeroSize = false} = {} ) { if (!bounds || typeof bounds !== "object") { throw new TypeError(`Octree: ${label} must be an object`); } for (const key of ["x", "y", "z"]) { if (!Number.isFinite(bounds[key])) { throw new RangeError(`Octree: ${label}.${key} must be a finite number`); } } for (const key of ["halfWidth", "halfHeight", "halfDepth"]) { const value = bounds[key]; const valid = Number.isFinite(value) && (allowZeroSize ? value >= 0 : value > 0); if (!valid) { const requirement = allowZeroSize ? "a non-negative finite number" : "a positive finite number"; throw new RangeError(`Octree: ${label}.${key} must be ${requirement}`); } } return bounds; } #itemBounds(item) { const bounds = this.#policy.itemBounds(item); return Octree.#validateBounds(bounds, { label: "item bounds", allowZeroSize: true }); } #bootstrapBounds(itemBounds) { const halfWidth = Math.max(1, itemBounds.halfWidth); const halfHeight = Math.max(1, itemBounds.halfHeight); const halfDepth = Math.max(1, itemBounds.halfDepth); if (this.#cube) { const halfSize = Math.max(halfWidth, halfHeight, halfDepth); return { x: itemBounds.x, y: itemBounds.y, z: itemBounds.z, halfWidth: halfSize, halfHeight: halfSize, halfDepth: halfSize }; } return { x: itemBounds.x, y: itemBounds.y, z: itemBounds.z, halfWidth, halfHeight, halfDepth }; } #growToFit(item, itemBounds) { while (!this.#policy.fits(this.root.boundary, item)) { this.#enlargeRootToCover(itemBounds); } } #enlargeRootToCover(itemBounds) { const rootBounds = this.root.boundary; const halfSize = Math.max( rootBounds.halfWidth, rootBounds.halfHeight, rootBounds.halfDepth ); const halfWidth = this.#cube ? halfSize : rootBounds.halfWidth; const halfHeight = this.#cube ? halfSize : rootBounds.halfHeight; const halfDepth = this.#cube ? halfSize : rootBounds.halfDepth; const centreX = itemBounds.x >= rootBounds.x ? rootBounds.x + halfWidth : rootBounds.x - halfWidth; const centreY = itemBounds.y >= rootBounds.y ? rootBounds.y + halfHeight : rootBounds.y - halfHeight; const centreZ = itemBounds.z >= rootBounds.z ? rootBounds.z + halfDepth : rootBounds.z - halfDepth; const parentBounds = { x: centreX, y: centreY, z: centreZ, halfWidth: halfWidth * 2, halfHeight: halfHeight * 2, halfDepth: halfDepth * 2 }; // This also detects numeric overflow during repeated enlargement. Octree.#validateBounds(parentBounds, { label: "expanded root boundary", allowZeroSize: false }); const parent = new OctreeNode(parentBounds, this.#capacity); const direction = (rootBounds.y < centreY ? "N" : "S") + // y: north (smaller y) vs south (greater y) (rootBounds.x < centreX ? "W" : "E") + // x: west vs east (rootBounds.z < centreZ ? "B" : "T"); // z: bottom vs top parent.attachChild(direction, this.root); this.root = parent; } }47:T715,display(md`\`▶ PointOctree\``); // In place of cell introspection class PointOctree extends Octree { static #POLICY = { itemBounds(p) { return { x: p.x, y: p.y, z: p.z, halfWidth: 0, halfHeight: 0, halfDepth: 0 }; }, fits(b, p) { const [minX, maxX] = [b.x - b.halfWidth, b.x + b.halfWidth]; const [minY, maxY] = [b.y - b.halfHeight, b.y + b.halfHeight]; const [minZ, maxZ] = [b.z - b.halfDepth, b.z + b.halfDepth]; return ( p.x >= minX && p.x <= maxX && p.y >= minY && p.y <= maxY && p.z >= minZ && p.z <= maxZ ); }, childIndex(b, p) { const [cx, cy, cz] = [b.x, b.y, b.z]; const east = p.x >= cx; const south = p.y >= cy; const top = p.z >= cz; // z up // Index order must match children(): NWB,NEB,SWB,SEB,NWT,NET,SWT,SET if (!east && !south && !top) { return 0; } // NWB if (east && !south && !top) { return 1; } // NEB if (!east && south && !top) { return 2; } // SWB if (east && south && !top) { return 3; } // SEB if (!east && !south && top) { return 4; } // NWT if (east && !south && top) { return 5; } // NET if (!east && south && top) { return 6; } // SWT return 7; // SET }, intersects: Octree.intersectsAABB3D }; constructor(opts = {}) { const { boundary = null, capacity = 4, autoResize = true, strict = false, maxDepth = Infinity, cube = true } = opts; super({ boundary, capacity, autoResize, strict, maxDepth, cube, policy: PointOctree.#POLICY }); } }48:T9fe,display(md`\`▶ RegionOctree\``); // In place of cell introspection class RegionOctree extends Octree { static #POLICY = { itemBounds(region) { return region.bounds; // { x,y,z, halfWidth, halfHeight, halfDepth } }, fits(b, region) { const r = region.bounds; const [bMinX, bMaxX] = [b.x - b.halfWidth, b.x + b.halfWidth]; const [bMinY, bMaxY] = [b.y - b.halfHeight, b.y + b.halfHeight]; const [bMinZ, bMaxZ] = [b.z - b.halfDepth, b.z + b.halfDepth]; const [rMinX, rMaxX] = [r.x - r.halfWidth, r.x + r.halfWidth]; const [rMinY, rMaxY] = [r.y - r.halfHeight, r.y + r.halfHeight]; const [rMinZ, rMaxZ] = [r.z - r.halfDepth, r.z + r.halfDepth]; return ( rMinX >= bMinX && rMaxX <= bMaxX && rMinY >= bMinY && rMaxY <= bMaxY && rMinZ >= bMinZ && rMaxZ <= bMaxZ ); }, childIndex(b, region) { const r = region.bounds; const [cx, cy, cz] = [b.x, b.y, b.z]; const [rMinX, rMaxX] = [r.x - r.halfWidth, r.x + r.halfWidth]; const [rMinY, rMaxY] = [r.y - r.halfHeight, r.y + r.halfHeight]; const [rMinZ, rMaxZ] = [r.z - r.halfDepth, r.z + r.halfDepth]; const whollyNorth = rMaxY <= cy; const whollySouth = rMinY >= cy; const whollyWest = rMaxX <= cx; const whollyEast = rMinX >= cx; const whollyBottom = rMaxZ <= cz; const whollyTop = rMinZ >= cz; if (whollyWest && whollyNorth && whollyBottom) { return 0; } // NWB if (whollyEast && whollyNorth && whollyBottom) { return 1; } // NEB if (whollyWest && whollySouth && whollyBottom) { return 2; } // SWB if (whollyEast && whollySouth && whollyBottom) { return 3; } // SEB if (whollyWest && whollyNorth && whollyTop) { return 4; } // NWT if (whollyEast && whollyNorth && whollyTop) { return 5; } // NET if (whollyWest && whollySouth && whollyTop) { return 6; } // SWT if (whollyEast && whollySouth && whollyTop) { return 7; } // SET return -1; // Straddles a split }, intersects: Octree.intersectsAABB3D }; constructor(opts = {}) { const { boundary = null, capacity = 4, autoResize = true, strict = false, maxDepth = Infinity, cube = true } = opts; super({ boundary, capacity, autoResize, strict, maxDepth, cube, policy: RegionOctree.#POLICY }); } }49:T65c,#### Deque tests ${[ assert(new Deque(["cat", "dog", "fish"]).toArray().join(","), "cat,dog,fish", "Array constructor and toArray:"), assert(new Deque(["cat", "dog", "fish"], 2).toArray().join(","), "dog,fish", "Bounded deque array constructor:"), (() => { let threw = false; try { new Deque([], 0); } catch (error) { threw = error instanceof RangeError; } return assert(threw, true, "Invalid bounded deque capacity throws RangeError:");})(), (() => { const dq = new Deque().enqueueFront("cat").enqueueFront("dog").enqueueFront("fish"); dq.dequeueBack(); return assert(dq.toArray().join(","), "fish,dog", "enqueueFront and dequeueBack:")})(), (() => { const dq = new Deque().enqueueBack("cat").enqueueBack("dog").enqueueBack("fish"); dq.dequeueFront(); return assert(dq.toArray().join(","), "dog,fish", "enqueueBack and dequeueFront:")})(), assert(new Deque([], 2).enqueueFront("cat").enqueueFront("dog").enqueueFront("fish").toArray().join(","), "fish,dog", "Bounded deque enqueueFront:"), assert(new Deque([], 2).enqueueBack("cat").enqueueBack("dog").enqueueBack("fish").toArray().join(","), "dog,fish", "Bounded deque enqueueBack:"), (()=> { const dq = new Deque([1066, 1999, 2025]); return assert(dq.peekBack() + 2 * dq.peekFront() + dq.size(), 2025 + 1066 * 2 + 3, "peekFront, peekBack and size:")})(), assert(new Deque([true, false, false]).clear().isEmpty(),true, "clear and isEmpty:"), assert(new Deque([true, false, false]).size(), 3, "size:") ].join("
")}4a:T9b2,#### PriorityQueue tests ${[ assert(new PriorityQueue([["cat", 3],["dog", 1],["fish", 2]]).toArray().join(","), "dog,fish,cat", "Array constructor and toArray:"), assert(new PriorityQueue([["cat"], ["dog"], ["fish"]]).toArray().join(","), "cat,dog,fish", "Constructor without priorities:"), (() => { const pq = new PriorityQueue().enqueue("cat", 3).enqueue("dog", 1).enqueue("fish", 2); pq.dequeue(); return assert( pq.toArray().join(","), "fish,cat", "enqueue and dequeue:")})(), assert(new PriorityQueue().enqueue("cat", 2).enqueue("dog", 1).enqueue("fish", 2).toArray().join(","), "dog,cat,fish", "enqueue with duplicate priorities:"), assert(new PriorityQueue().enqueue("cat").peekPriority(), 0, "peekPriority default priority is 0"), (() => { const pq = new PriorityQueue().enqueue("cat", 3).enqueue("dog", 1).enqueue("fish", 2); pq.dequeue(); pq.enqueue("axolotl", 0); return assert( pq.toArray().join(","), "axolotl,fish,cat", "Retain order after enqueue/dequeue:")})(), (()=>{ const pq = new PriorityQueue().enqueue("cat", 3).enqueue("dog", 1).enqueue("fish", 2); const results = []; while (!pq.isEmpty()) results.push(pq.dequeue()) return assert(results.join(","), "dog,fish,cat", "dequeue until empty gives priority sorted order:")})(), (()=>{ let threw = false; try { const pq = new PriorityQueue().enqueue("cat"); pq.dequeue(); pq.peek(); } catch { threw = true;} return assert(threw, true, "peek at an empty queue throws error:")})(), (()=>{ let threw = false; try { const pq = new PriorityQueue().enqueue("cat"); pq.dequeue(); pq.dequeue(); } catch { threw = true;} return assert(threw,true,"dequeue an empty queue throws error:")})(), (()=>{ const pq = new PriorityQueue([[1066, -5],[1999, 0],[2025, -10]]); return assert(pq.peek() + pq.size(), 2028, "peek and size:")})(), assert(new PriorityQueue([[true], [false], [false]]).clear().isEmpty(),true, "clear and isEmpty:"), assert(new PriorityQueue([[true], [false], [false]]).size(), 3, "size:"), (() => { const pq = new PriorityQueue([["a", 1], ["b", 1]]).enqueue("c", 1); const result = []; while (!pq.isEmpty()) { result.push(pq.dequeue()); } return assert(result.join(","), "a,b,c", "Equal priorities retain insertion order:");})(), ].join("
")}4b:Teb1,#### BoundedPriorityQueue tests ${[ assert(new BoundedPriorityQueue().insert("cat",3).insert("dog",1).insert("fish",2).toSortedArray().join(","), "dog,fish,cat", "Constructor, insert within capacity and toSortedArray:"), assert(new BoundedPriorityQueue().insert("cat").insert("dog").insert("fish").toSortedArray().join(","), "cat,dog,fish", "Insert without priorities within capacity:"), (() => { let threw = false; try { new BoundedPriorityQueue(0); } catch (error) { threw = error instanceof RangeError; } return assert(threw, true, "Invalid capacity throws RangeError:");})(), assert(new BoundedPriorityQueue(3).insert("cat",3).insert("dog",1).insert("fish",2).insert("axolotl",0).toSortedArray().join(","), "axolotl,dog,fish", "Insert exceeding capacity and toSortedArray:"), assert(new BoundedPriorityQueue(3).insert("cat").insert("dog").insert("fish").insert("axolotl").toSortedArray().join(","), "cat,dog,fish", "Insert without priorities exceeding capacity:"), assert(new BoundedPriorityQueue(999).insert("fish",2).insert("cat",3).insert("dog",1).dequeue(), "cat", "dequeue returns highest numerical priority element"), assert(new BoundedPriorityQueue(999).insert("cat").peekPriority(), 0, "peekPriority default priority is 0"), (()=>{ let threw = false; try { const bmh = new BoundedPriorityQueue().insert("cat"); bmh.dequeue(); bmh.peek(); } catch { threw = true;} return assert(threw, true, "peek at an empty BoundedPriorityQueue throws error:")})(), (()=>{ let threw = false; try { const bmh = new BoundedPriorityQueue().insert("cat"); bmh.dequeue(); bmh.peekPriority(); } catch { threw = true;} return assert(threw, true, "peekPriority at an empty BoundedPriorityQueue throws error:")})(), (()=>{ let threw = false; try { const bmh = new BoundedPriorityQueue().insert("cat"); bmh.dequeue(); bmh.dequeue(); } catch { threw = true;} return assert(threw,true,"dequeue an empty BoundedPriorityQueue throws error:")})(), (()=>{ const bmh = new BoundedPriorityQueue().insert(1066,-5).insert(1990,42).insert(2025,-10); return assert(bmh.peek() + bmh.size(), 1993, "peek and size:")})(), assert(new BoundedPriorityQueue().insert(1066,-5).insert(1990,42).insert(2025,-10).peekPriority(), 42, "peekPriority:"), assert(new BoundedPriorityQueue().insert("cat", 2).insert("dog", 1).insert("fish", 2).toSortedArray().join(","), "dog,cat,fish", "insert with duplicate priorities:"), (() => { const bmh = new BoundedPriorityQueue().insert("cat", 3).insert("dog", 1).insert("fish", 2); bmh.dequeue(); bmh.insert("axolotl", 0); return assert(bmh.toSortedArray().join(","), "axolotl,dog,fish", "Retain order after insert/dequeue:")})(), (()=>{ const bmh = new BoundedPriorityQueue().insert("cat", 3).insert("dog", 1).insert("fish", 2); const sorted = bmh.toSortedArray(); const results = []; while (!bmh.isEmpty()) results.push(bmh.dequeue()) return assert(results.join(","), sorted.reverse().join(","), "dequeue until empty gives reversed priority sorted order:")})(), assert(new BoundedPriorityQueue().insert(true).insert(false).insert(false).clear().isEmpty(), true, "clear and isEmpty:"), assert(new BoundedPriorityQueue().insert(true).insert(false).insert(false).size(), 3, "size:"), (() => { const bmh = new BoundedPriorityQueue().insert("cat", 3).insert("dog", 1).insert("fish", 2); bmh.dequeue(); return assert( bmh.toSortedArray().join(","), "dog,fish", "insert and dequeue:")})(), ].join("
")}4c:T896,#### DoublyLinkedList tests ${[ assert(new DoublyLinkedList(["cat", "dog", "fish"]).toArray().join(","), "cat,dog,fish", "Constructor and toArray:"), assert(new DoublyLinkedList().pushFront("cat").pushBack("axolotl").pushFront("dog").pushFront("fish").toArray().join(","), "fish,dog,cat,axolotl", "pushFront and pushBack:"), (() => { const dll = new DoublyLinkedList(["cat", "dog", "fish"]); dll.insertBefore(dll.find((x) => x === "fish"),"axolotl"); return assert(dll.toArray().join(","), "cat,dog,axolotl,fish", "find and insertBefore:")})(), (() => { const dll = new DoublyLinkedList(["cat", "dog", "fish"]); dll.insertAfter(dll.find((x) => x === "fish"),"axolotl"); return assert(dll.toArray().join(","), "cat,dog,fish,axolotl", "find and insertAfter:")})(), (()=>{{ const dll = new DoublyLinkedList(["cat", "dog", "cat", "fish"]); dll.insertAfter(dll.findLast((x) => x === "cat"),"axolotl"); return assert(dll.toArray().join(","), "cat,dog,cat,axolotl,fish", "findLast:")}})(), (()=>{ const dll = new DoublyLinkedList(["cat", "dog", "fish"]); dll.insertAt(dll.indexOf("dog"), "axolotl"); return assert(dll.toArray().join(","), "cat,axolotl,dog,fish", "indexOf and insertAt:")})(), (()=>{ const dll = new DoublyLinkedList(["cat", "dog", "fish", "axolotl"]); dll.popFront(); dll.pushBack("fox").popBack(); return assert(dll.toArray().join(","), "dog,fish,axolotl", "popFront and popBack:")})(), (()=>{ const dll = new DoublyLinkedList(["cat", "dog", "fish", "axolotl"]); dll.remove(dll.find((d) => d === "dog")); dll.removeAt(1); return assert(dll.toArray().join(","), "cat,axolotl", "remove and removeAt:")})(), (()=>{ const dll = new DoublyLinkedList([1066, 1999, 2025]); return assert(2 * dll.peekFront() + dll.peekBack() + dll.size(), 2 * 1066 + 2025 + 3, "peekFront, peekBack and size:")})(), assert(new DoublyLinkedList([true, false, false]).clear().isEmpty(),true, "clear and isEmpty:"), assert(new DoublyLinkedList([true, false, false]).size(), 3, "size:") ].join("
")}4d:T289d,#### Tree tests ${(()=>{ const t = new Tree(new TreeNode("cat")); return t .addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) .toDot({ scale: 0.5 }); })()} ${[ (()=>{ const t = new Tree(new TreeNode("cat")); return assert( [ ...t .addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("dog"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .bfs() ].join(","), "cat,dog,fox,fish,lemur,axolotl", "Constructor, addChild, find and bfs:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert(t.findAll("fox").map(d=>d.value).join(","), "fox,fox", "Tree with repeats and findAll:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert(t.findWhere(d=>d.value === "fox" && d.parent.value === "lemur").value, "fox", "Tree with repeats and findWhere:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert(t.toArray('bfs').join(","), "cat,dog,fox,lemur,fish,axolotl,parrot,fox,elephant,eel", "toArray('bfs'):" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert([...t.bfs()].join(","), "cat,dog,fox,lemur,fish,axolotl,parrot,fox,elephant,eel", "bfs:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert(t.toArray('pre').join(","), "cat,dog,fish,fox,lemur,axolotl,parrot,fox,eel,elephant", "toArray('pre'):" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert([...t].join(","), "cat,dog,fish,fox,lemur,axolotl,parrot,fox,eel,elephant", "Iterate over tree:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert([...t.dfsPreOrder()].join(","), "cat,dog,fish,fox,lemur,axolotl,parrot,fox,eel,elephant", "dfsPreOrder:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert([...t.dfsPostOrder()].join(","), "fish,dog,fox,axolotl,parrot,eel,fox,elephant,lemur,cat", "dfsPostOrder:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert(t.toArray('post').join(","), "fish,dog,fox,axolotl,parrot,eel,fox,elephant,lemur,cat", "toArray('post'):" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .addChild(t.find("lemur"), new TreeNode("elephant")) return assert([...t.nodesPostOrder()].map(d=>d.value).join(","), "fish,dog,fox,axolotl,parrot,eel,fox,elephant,lemur,cat", "nodesPostOrder:" ); })(), (()=>{ const t = new Tree(new TreeNode("cat")); t.addChild(t.find("cat"), new TreeNode("dog")) .addChild(t.find("cat"), new TreeNode("fox")) .addChild(t.find("dog"), new TreeNode("fish")) .addChild(t.find("cat"), new TreeNode("lemur")) .addChild(t.find("lemur"), new TreeNode("axolotl")) .addChild(t.find("lemur"), new TreeNode("parrot")) .addChild(t.find("lemur"), new TreeNode("fox")) .addChild(t.findAll("fox").at(-1), new TreeNode("eel")) .clear() .addChild(new TreeNode("eel"), new TreeNode("elephant")) return assert(t.toArray('bfs').join(","), "eel,elephant", "clear:" ); })(), (() => { const root = new TreeNode("root"); const first = new TreeNode("first"); const second = new TreeNode("second"); const tree = new Tree(root).addChild(root, first).addChild(root, second); let threw = false; try { tree.addChild(second, first); } catch (error) { threw = error instanceof Error; } return assert( [ threw, first.parent === root, root.childValues().join(",") ].join("|"), "true|true|first,second", "Validation rejects a child that already has a parent:" ); })(), (() => { const root = new TreeNode("root"); const child = new TreeNode("child"); const grandchild = new TreeNode("grandchild"); const tree = new Tree(root).addChild(root, child).addChild(child, grandchild); let threw = false; try { tree.addChild(grandchild, root); } catch (error) { threw = error instanceof Error; } return assert( [ threw, root.parent === null, grandchild.children.length, tree.toArray("bfs").join(",") ].join("|"), "true|true|0|root,child,grandchild", "Validation rejects an attachment that would create a cycle:" ); })(), (() => { const root = new TreeNode("root"); const outsider = new TreeNode("outsider"); const child = new TreeNode("child"); const tree = new Tree(root); let threw = false; try { tree.addChild(outsider, child); } catch (error) { threw = error instanceof Error; } return assert( [ threw, child.parent === null, outsider.children.length, tree.toArray("bfs").join(",") ].join("|"), "true|true|0|root", "Validation rejects a parent outside the tree:" ); })(), (() => { const root = new TreeNode("root"); const tree = new Tree(root); let threw = false; try { tree.addChild(root, {}); } catch (error) { threw = error instanceof TypeError; } return assert( [threw, root.children.length].join(","), "true,0", "Validation rejects a child that is not a TreeNode:" ); })(), ].join("
")}4e:T52b,#### BinaryTreeNode tests ${[ assert(new BinaryTreeNode("cat").value, "cat", "Constructor and value:"), assert(new BinaryTreeNode("cat").isLeaf(), true, "isLeaf:"), assert(new BinaryTreeNode("cat").setLeft(new BinaryTreeNode("dog")).leftValue, "dog", "setLeft and leftValue:"), assert(new BinaryTreeNode("cat").setRight(new BinaryTreeNode("dog")).leftValue, null, "leftValue with null:"), assert(new BinaryTreeNode("cat").setRight(new BinaryTreeNode("dog")).rightValue, "dog", "setRight and rightValue:"), assert(new BinaryTreeNode("cat").setLeft(new BinaryTreeNode("dog")).rightValue, null, "rightValue with null:"), (() => { const cat = new BinaryTreeNode("cat"); const dog = new BinaryTreeNode("dog"); const lemur = new BinaryTreeNode("lemur"); const fish = new BinaryTreeNode("fish"); cat.setLeft(dog).setRight(lemur); lemur.setLeft(fish); return assert([fish.parent.value, lemur.parent.value].join(","), "lemur,cat", "parent: ")})(), (() => { const btn = new BinaryTreeNode("cat"); const l = new BinaryTreeNode("dog"); btn.setLeft(l).setRight(new BinaryTreeNode("fish")); return assert([btn.hasLeft(),btn.hasRight(),l.hasLeft(),l.hasRight()].join(","), "true,true,false,false", "hasLeft, hasRight:")})(), ].join("
")}4f:T1a48,#### BinaryTree tests ${new BinaryTree( new BinaryTreeNode( "cat", new BinaryTreeNode( "dog", new BinaryTreeNode("fish"), new BinaryTreeNode("lemur", null, new BinaryTreeNode("axolotl")) ), new BinaryTreeNode("fox") ) ).toDot({ scale: 0.5 })} ${[ (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .bfs() ].join(","), "cat,dog,fox,fish,lemur,axolotl", "Constructor, setChild, find and bfs:" ); })(), (()=>{ const bt = new BinaryTree( new BinaryTreeNode( "cat", new BinaryTreeNode( "cat", new BinaryTreeNode("fish"), new BinaryTreeNode("lemur") ), new BinaryTreeNode("cat") ) ); const noi = bt.findWhere( (node) => node.value === "cat" && node.leftValue === "fish" ); return assert( [noi.left.value, noi.right.value].join(","), "fish,lemur", "Constructor with repeats, findWhere:" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .toArray("bfs") .join(","), "cat,dog,fox,fish,lemur,axolotl", "toArray('bfs'):" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .nodesPreOrder() ] .map((d) => d.value) .join(","), "cat,dog,fish,lemur,axolotl,fox", "nodesPreOrder:" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .dfsPreOrder() ].join(","), "cat,dog,fish,lemur,axolotl,fox", "dfsPreOrder:" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .toArray("pre") .join(","), "cat,dog,fish,lemur,axolotl,fox", "toArray('pre'):" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) ].join(","), "fish,dog,axolotl,lemur,cat,fox", "Iterate in dfs in-order:" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .dfsInOrder() ].join(","), "fish,dog,axolotl,lemur,cat,fox", "dfsInOrder:" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .toArray("in") .join(","), "fish,dog,axolotl,lemur,cat,fox", "toArray('in'):" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .dfsPostOrder() ].join(","), "fish,axolotl,lemur,dog,fox,cat", "dfsPostOrder:" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .toArray("post") .join(","), "fish,axolotl,lemur,dog,fox,cat", "toArray('post'):" ); })(), (()=>{ const bt = new BinaryTree(new BinaryTreeNode("cat")); return assert( [ ...bt .setChild(bt.find("cat")[0], new BinaryTreeNode("dog")) .setChild(bt.find("cat")[0], new BinaryTreeNode("fox"), "R") .setChild(bt.find("dog")[0], new BinaryTreeNode("fish")) .setChild(bt.find("dog")[0], new BinaryTreeNode("lemur"), "R") .setChild(bt.find("lemur")[0], new BinaryTreeNode("axolotl")) .clear() .bfs() ].join(","), "", "clear:" ); })() ].join("
")}50:Tf64,#### BinarySearchTree tests ${d3.shuffle(d3.range(1,17)).reduce((bst, x) => bst.insert(x), new BinarySearchTree()).toDot({scale:0.5})} ${[ (()=>assert(new BinarySearchTree(5) .insert(6) .insert(4) .insert(6) .insert(7) .toArray("bfs") .join(","), "5,4,6,7", "Constructor, toArray('bfs') and insert duplicate:" ))(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [ bst.find(14).parent.value, bst.find(12).left.value, bst.find(12).right.value, bst.find("cat") ].join(","), "12,11,14,", "find, parent, left and right:" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ] .reduce((bst, x) => bst.insert(x), new BinarySearchTree()) .remove(12); return assert(bst.find(8).right.value, 13, "remove:"); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( bst.toArray("bfs").join(","), "15,5,20,2,8,19,1,3,7,12,18,4,6,11,14,17,10,13,16,9", "toArray('bfs'):" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [...bst.dfsPreOrder()].join(","), "15,5,2,1,3,4,8,7,6,12,11,10,9,14,13,20,19,18,17,16", "dfsPreOrder:" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [...bst.nodesPreOrder()].map((d) => d.value).join(","), "15,5,2,1,3,4,8,7,6,12,11,10,9,14,13,20,19,18,17,16", "nodesPreOrder:" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( bst.toArray("pre").join(","), "15,5,2,1,3,4,8,7,6,12,11,10,9,14,13,20,19,18,17,16", "toArray('pre'):" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [...bst].join(","), d3.range(1, 21).join(","), "Iterate in dfs in-order:" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [...bst.dfsInOrder()].join(","), d3.range(1, 21).join(","), "dfsInOrder:" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( bst.toArray("in").join(","), d3.range(1, 21).join(","), "toArray('in'):" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [...bst.dfsPostOrder()].join(","), "1,4,3,2,6,7,9,10,11,13,14,12,8,5,16,17,18,19,20,15", "dfsPostOrder:" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( bst.toArray("post").join(","), "1,4,3,2,6,7,9,10,11,13,14,12,8,5,16,17,18,19,20,15", "toArray('post'):" ); })(), (()=>{ const bst = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((bst, x) => bst.insert(x), new BinarySearchTree()); return assert( [...bst.clear().bfs()].join(","), "", "clear:" ); })(), (()=>{})(), ].join("
")}51:T615,#### AVLTreeNode tests ${[ assert(new AVLTreeNode("cat").value, "cat", "Constructor and value:"), assert(new AVLTreeNode("cat").isLeaf(), true, "isLeaf:"), assert(new AVLTreeNode("cat").setLeft(new AVLTreeNode("dog")).leftValue, "dog", "setLeft and leftValue:"), assert(new AVLTreeNode("cat").setRight(new AVLTreeNode("dog")).leftValue, null, "leftValue with null:"), assert(new AVLTreeNode("cat").setRight(new AVLTreeNode("dog")).rightValue, "dog", "setRight and rightValue:"), assert(new AVLTreeNode("cat").setLeft(new AVLTreeNode("dog")).rightValue, null, "rightValue with null:"), (() => { const cat = new AVLTreeNode("cat"); const dog = new AVLTreeNode("dog"); const lemur = new AVLTreeNode("lemur"); const fish = new AVLTreeNode("fish"); cat.setLeft(dog).setRight(lemur); lemur.setLeft(fish); return assert([fish.parent.value, lemur.parent.value].join(","), "lemur,cat", "parent: ")})(), (() => { const btn = new AVLTreeNode("cat"); const l = new AVLTreeNode("dog"); btn.setLeft(l).setRight(new AVLTreeNode("fish")); return assert([btn.hasLeft(),btn.hasRight(),l.hasLeft(),l.hasRight()].join(","), "true,true,false,false", "hasLeft, hasRight:")})(), (()=>{ const cat = new AVLTreeNode("cat"); const dog = new AVLTreeNode("dog"); const lemur = new AVLTreeNode("lemur"); const fish = new AVLTreeNode("fish"); cat.setLeft(dog).setRight(lemur); lemur.setLeft(fish); return assert(fish.height, 1, "height")})() ].join("
")}52:T12f7,#### AVLTree tests ${d3.shuffle(d3.range(1,17)).reduce((bst, x) => bst.insert(x), new AVLTree()).toDot({scale:0.5})} ${[ (()=>assert( new AVLTree(5) .insert(6) .insert(4) .insert(6) .insert(7) .toArray("bfs") .join(","), "5,4,6,7", "Constructor, toArray('bfs') and insert duplicate:" ))(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( [ avl.find(14).parent.value, avl.find(12).left.value, avl.find(12).right.value, avl.find("cat") ].join(","), "12,10,14,", "find, parent, left and right:" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ] .reduce((avl, x) => avl.insert(x), new AVLTree()) .remove(12); return assert(avl.find(15).left.value, 13, "remove:"); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( avl.toArray("bfs").join(","), "8,5,15,3,7,12,18,2,4,6,10,14,17,19,1,9,11,13,16,20", "toArray('bfs'):" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( [...avl.dfsPreOrder()].join(","), "8,5,3,2,1,4,7,6,15,12,10,9,11,14,13,18,17,16,19,20", "dfsPreOrder:" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( [...avl.nodesPreOrder()].map((d) => d.value).join(","), "8,5,3,2,1,4,7,6,15,12,10,9,11,14,13,18,17,16,19,20", "nodesPreOrder:" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( avl.toArray("pre").join(","), "8,5,3,2,1,4,7,6,15,12,10,9,11,14,13,18,17,16,19,20", "toArray('pre'):" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( [...avl].join(","), d3.range(1, 21).join(","), "Iterate in dfs in-order:" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( [...avl.dfsInOrder()].join(","), d3.range(1, 21).join(","), "dfsInOrder:" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( avl.toArray("in").join(","), d3.range(1, 21).join(","), "toArray('in'):" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( [...avl.dfsPostOrder()].join(","), "1,2,4,3,6,7,5,9,11,10,13,14,12,16,17,20,19,18,15,8", "dfsPostOrder:" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert( avl.toArray("post").join(","), "1,2,4,3,6,7,5,9,11,10,13,14,12,16,17,20,19,18,15,8", "toArray('post'):" ); })(), (()=>{ const avl = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((avl, x) => avl.insert(x), new AVLTree()); return assert([...avl.clear().bfs()].join(","), "", "clear:"); })(), (() => { const values = d3.range(1, 101).map((value) => (value * 37) % 101); const tree = values.reduce((tree, value) => tree.insert(value),new AVLTree()); for (const value of d3.range(3, 101, 3)) { tree.remove(value); } const inspect = (node, min = -Infinity, max = Infinity) => { if (!node) { return {valid: true, height: 0}; } const left = inspect(node.left, min, node.value); const right = inspect(node.right, node.value, max); const height = 1 + Math.max(left.height, right.height); return { height, valid: left.valid && right.valid && node.value > min && node.value < max && Math.abs(left.height - right.height) <= 1 && node.height === height && (!node.left || node.left.parent === node) && (!node.right || node.right.parent === node) }; }; const result = inspect(tree.root); return assert( result.valid && (!tree.root || tree.root.parent === null), true, "Ordering, heights, balance and parent links remain valid:"); })() ].join("
")}53:Td1c,#### RedBlackTreeNode tests ${[ assert(new RedBlackTreeNode("cat").value, "cat", "Constructor and value:"), assert(new RedBlackTreeNode("cat").isLeaf(), true, "isLeaf:"), assert(new RedBlackTreeNode("cat").setLeft(new RedBlackTreeNode("dog")).leftValue, "dog", "setLeft and leftValue:"), assert(new RedBlackTreeNode("cat").setRight(new RedBlackTreeNode("dog")).leftValue, null, "leftValue with null:"), assert(new RedBlackTreeNode("cat").setRight(new RedBlackTreeNode("dog")).rightValue, "dog", "setRight and rightValue:"), assert(new RedBlackTreeNode("cat").setLeft(new RedBlackTreeNode("dog")).rightValue, null, "rightValue with null:"), (() => { const cat = new RedBlackTreeNode("cat"); const dog = new RedBlackTreeNode("dog"); const lemur = new RedBlackTreeNode("lemur"); const fish = new RedBlackTreeNode("fish"); cat.setLeft(dog).setRight(lemur); lemur.setLeft(fish); return assert([fish.parent.value, lemur.parent.value].join(","), "lemur,cat", "parent: ")})(), (() => { const btn = new RedBlackTreeNode("cat"); const l = new RedBlackTreeNode("dog"); btn.setLeft(l).setRight(new RedBlackTreeNode("fish")); return assert([btn.hasLeft(),btn.hasRight(),l.hasLeft(),l.hasRight()].join(","), "true,true,false,false", "hasLeft, hasRight:")})(), (()=>{ const cat = new RedBlackTreeNode("cat"); const dog = new RedBlackTreeNode("dog"); const lemur = new RedBlackTreeNode("lemur"); const fish = new RedBlackTreeNode("fish"); cat.setLeft(dog).setRight(lemur); lemur.setLeft(fish); return assert([cat.clr,dog.clr,lemur.clr,fish.clr].join(","), "R,R,R,R", "clr")})(), (()=>{ const cat = new RedBlackTreeNode("cat"); const dog = new RedBlackTreeNode("dog"); const lemur = new RedBlackTreeNode("lemur"); const fish = new RedBlackTreeNode("fish"); cat.setLeft(dog).setRight(lemur); lemur.setLeft(fish); return assert([cat.isRed,dog.isRed,lemur.isRed,fish.isRed].join(","), "true,true,true,true", "isRed")})(), (() => { const values = d3.range(1, 101).map((value) => (value * 37) % 101); const tree = values.reduce((tree, value) => tree.insert(value), new RedBlackTree()); for (const value of d3.range(4, 101, 4)) { tree.remove(value); } const inspect = (node, min = -Infinity, max = Infinity) => { if (!node) { return {valid: true, blackHeight: 1}; } const left = inspect(node.left, min, node.value); const right = inspect(node.right, node.value, max); const isRed = node.clr === "R"; return { blackHeight: left.blackHeight + (node.clr === "B" ? 1 : 0), valid: left.valid && right.valid && node.value > min && node.value < max && (node.clr === "R" || node.clr === "B") && (!isRed || (node.left?.clr !== "R" && node.right?.clr !== "R")) && left.blackHeight === right.blackHeight && (!node.left || node.left.parent === node) && (!node.right || node.right.parent === node) }; }; const result = inspect(tree.root); return assert(result.valid && (!tree.root || (tree.root.clr === "B" && tree.root.parent === null)), true, "Ordering, colours, black heights and parent links remain valid:"); })(), ].join("
")}54:Te12,#### RedBlackTree tests ${d3.shuffle(d3.range(1,17)).reduce((bst, x) => bst.insert(x), new RedBlackTree()).toDot({scale:0.5, fillClr: (node) => (node.clr === "R" ? "pink" : "lightgrey"), })} ${[ (()=>assert( new RedBlackTree(5) .insert(6) .insert(4) .insert(6) .insert(7) .toArray("bfs") .join(","), "5,4,7,6", "Constructor, toArray('bfs') and insert duplicate:" ))(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( [ rbt.find(14).parent.value, rbt.find(12).left.value, rbt.find(12).right.value, rbt.find("cat") ].join(","), "12,10,14,", "find, parent, left and right:" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ] .reduce((rbt, x) => rbt.insert(x), new RedBlackTree()) .remove(12); return assert(rbt.find(8).right.value, 13, "remove:"); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( rbt.toArray("bfs").join(","), "15,8,19,5,12,17,20,3,7,10,14,16,18,2,4,6,9,11,13,1", "toArray('bfs'):" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( [...rbt.dfsPreOrder()].join(","), "15,8,5,3,2,1,4,7,6,12,10,9,11,14,13,19,17,16,18,20", "dfsPreOrder:" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( rbt.toArray("pre").join(","), "15,8,5,3,2,1,4,7,6,12,10,9,11,14,13,19,17,16,18,20", "toArray('pre'):" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( [...rbt.dfsInOrder()].join(","), d3.range(1, 21).join(","), "dfsInOrder:" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( [...rbt].join(","), d3.range(1, 21).join(","), "Iterate in dfs in-order:" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( rbt.toArray("in").join(","), d3.range(1, 21).join(","), "toArray('in'):" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( [...rbt.dfsPostOrder()].join(","), "1,2,4,3,6,7,5,9,11,10,13,14,12,8,16,18,17,20,19,15", "dfsPostOrder:" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert( rbt.toArray("post").join(","), "1,2,4,3,6,7,5,9,11,10,13,14,12,8,16,18,17,20,19,15", "toArray('post'):" ); })(), (()=>{ const rbt = [ 15, 5, 20, 8, 12, 7, 19, 18, 17, 11, 16, 2, 14, 10, 3, 9, 13, 6, 4, 1 ].reduce((rbt, x) => rbt.insert(x), new RedBlackTree()); return assert([...rbt.clear().bfs()].join(","), "", "clear:"); })() ].join("
")}55:Tea6,#### Trie tests ${ "cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()).toDot({scale:0.5})} ${[ assert( [ ..."cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()) .dfs() ].join(","), "cat,car,carpet,a,app,apple,ape,dog,zebra,he,her,here,I", "Constructor, dfs and insert:" ), assert( [ ..."cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()) .bfs() ].join(","), "a,I,he,cat,car,app,ape,dog,her,here,apple,zebra,carpet", "bfs:" ), assert( [ ..."cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()) ].join(","), "a,ape,app,apple,car,carpet,cat,dog,he,her,here,I,zebra", "iterate in lex order:" ), assert( [ ..."cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()) .remove("car") .remove("xxxx") ].join(","), "a,ape,app,apple,carpet,cat,dog,he,her,here,I,zebra", "remove:" ), (()=>{ const trie = "cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()); return assert( [ trie.has("app"), trie.has("apple"), trie.has("apples"), trie.has("Apple"), trie.has("") ].join(","), "true,true,false,false,false", "has with suffix, case change and absent empty string:" ); })(), (()=>{ const trie = new Trie().insert("I").insert(""); return assert( [trie.has("I"), trie.has("")].join(","), "true,true", "has with present empty string:" ); })(), (()=>{ const trie = "cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()); return assert( [ trie.startsWith("a"), trie.startsWith("ap"), trie.startsWith("app"), trie.startsWith("apps"), trie.startsWith("") ].join(","), "true,true,true,false,true", "startsWith:" ); })(), (()=>{ const str = "cat car carpet apple ape app dog zebra he her here a I"; const trie = str .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()); return assert(trie.wordCount(), str.split(/\s+/).length, "wordCount:"); })(), assert( [ ..."cat car carpet apple ape app dog zebra he her here a I" .split(/\s+/) .reduce((trie, word) => trie.insert(word), new Trie()) .clear() .dfs() ].join(","), "", "clear:" ), (() => { const emptyTrie = new Trie(); const populatedTrie = new Trie().insert("cat"); return assert( [ emptyTrie.startsWith(""), populatedTrie.startsWith("") ].join(","), "false,true", "Empty prefix matches only when the trie contains a word:" ); })(), (() => { const trie = new Trie().insert("😀").insert("a😀").remove("😀"); return assert( [trie.has("😀"), trie.has("a😀"), trie.startsWith("a😀")].join(","), "false,true,true", "Unicode code-point insertion, lookup and removal:" ); })(), (() => { const composed = "\u00e9"; const decomposed = "e\u0301"; const trie = new Trie().insert(composed).insert(decomposed).remove(decomposed); return assert( [ [...composed].length, [...decomposed].length, trie.has(composed), trie.has(decomposed) ].join(","), "1,2,true,false", "Precomposed and decomposed Unicode forms remain distinct:" ); })(), ].join("
")}56:T8f6,#### Suffix trie tests ${new SuffixTrie("banana$").toDot({scale:0.5})} ${[ assert( [ ...new SuffixTrie("banana$") .dfs() ].join(","), "b,ba,ban,bana,banan,banana,banana$,a,an,ana,anan,anana,anana$,ana$,a$,n,na,nan,nana,nana$,na$,$", "Constructor and dfs:" ), assert( [ ...new SuffixTrie("banana$") .bfs() ].join(","), "b,a,n,$,ba,an,a$,na,ban,ana,nan,na$,bana,anan,ana$,nana,banan,anana,nana$,banana,anana$,banana$", "bfs:" ), assert( [...new SuffixTrie("banana$")].join(","), "$,a,a$,an,ana,ana$,anan,anana,anana$,b,ba,ban,bana,banan,banana,banana$,n,na,na$,nan,nana,nana$", "iterate in lex order:" ), assert( [...new SuffixTrie("banana$").entries()].filter((d) => d.factor === "a")[0] .positions.join(","), "1,3,5", // 'a' occurs at positions 1, 3 and 5 of 'banana' "entries:" ), assert( [...new SuffixTrie().entries()].join(","), "", "entries on empty suffix trie:" ), assert( new SuffixTrie("banana$").has("nan") && !(new SuffixTrie("banana$").has("naan")) && !(new SuffixTrie().has("a")), true, "has:" ), assert( new SuffixTrie("banana$").positionsOf("an").join(","), "1,3", "positionsOf:" ), assert( new SuffixTrie("banana$").positionsOf("naan").join(","), "", "positionsOf non-existent substring" ), assert( [...new SuffixTrie("banana$").factors({ minLength:2, maxLength: 2 })].sort().join(","), "a$,an,ba,na", "factors with minLength and maxLength of 2:" ), assert( [...new SuffixTrie("banana$").factors({ minLength:3, maxLength: 2 })].join(","), "", "factors with minLength greater than maxLength:" ), assert( [...new SuffixTrie("banana$").factorEntries()].filter((d) => d.factor === "an")[0] .positions.join(","), "1,3", "factor entries:" ), assert( [...new SuffixTrie("banana$").clear().dfs()].join(","), "", "clear:" ), (() => { const trie = new SuffixTrie("a😀b😀"); return assert( [ trie.has("😀"), trie.has("😀b"), trie.positionsOf("😀").join(",") ].join("|"), "true|true|1,3", "Unicode code-point factors and positions:" ); })(), assert( [...new SuffixTrie("a😀b").factors({ minLength: 1, maxLength: 1 })].sort().join(","), "a,b,😀", "Unicode code-point factor lengths:" ) ].join("
")}57:T4d8c,const austen = `The family of Dashwood had long been settled in Sussex. Their estate was large, and their residence was at Norland Park, in the centre of their property, where, for many generations, they had lived in so respectable a manner as to engage the general good opinion of their surrounding acquaintance. The late owner of this estate was a single man, who lived to a very advanced age, and who for many years of his life, had a constant companion and housekeeper in his sister. But her death, which happened ten years before his own, produced a great alteration in his home; for to supply her loss, he invited and received into his house the family of his nephew Mr. Henry Dashwood, the legal inheritor of the Norland estate, and the person to whom he intended to bequeath it. In the society of his nephew and niece, and their children, the old Gentleman’s days were comfortably spent. His attachment to them all increased. The constant attention of Mr. and Mrs. Henry Dashwood to his wishes, which proceeded not merely from interest, but from goodness of heart, gave him every degree of solid comfort which his age could receive; and the cheerfulness of the children added a relish to his existence. By a former marriage, Mr. Henry Dashwood had one son: by his present lady, three daughters. The son, a steady respectable young man, was amply provided for by the fortune of his mother, which had been large, and half of which devolved on him on his coming of age. By his own marriage, likewise, which happened soon afterwards, he added to his wealth. To him therefore the succession to the Norland estate was not so really important as to his sisters; for their fortune, independent of what might arise to them from their father’s inheriting that property, could be but small. Their mother had nothing, and their father only seven thousand pounds in his own disposal; for the remaining moiety of his first wife’s fortune was also secured to her child, and he had only a life-interest in it. The old gentleman died: his will was read, and like almost every other will, gave as much disappointment as pleasure. He was neither so unjust, nor so ungrateful, as to leave his estate from his nephew;—but he left it to him on such terms as destroyed half the value of the bequest. Mr. Dashwood had wished for it more for the sake of his wife and daughters than for himself or his son;—but to his son, and his son’s son, a child of four years old, it was secured, in such a way, as to leave to himself no power of providing for those who were most dear to him, and who most needed a provision by any charge on the estate, or by any sale of its valuable woods. The whole was tied up for the benefit of this child, who, in occasional visits with his father and mother at Norland, had so far gained on the affections of his uncle, by such attractions as are by no means unusual in children of two or three years old; an imperfect articulation, an earnest desire of having his own way, many cunning tricks, and a great deal of noise, as to outweigh all the value of all the attention which, for years, he had received from his niece and her daughters. He meant not to be unkind, however, and, as a mark of his affection for the three girls, he left them a thousand pounds a-piece. Mr. Dashwood’s disappointment was, at first, severe; but his temper was cheerful and sanguine; and he might reasonably hope to live many years, and by living economically, lay by a considerable sum from the produce of an estate already large, and capable of almost immediate improvement. But the fortune, which had been so tardy in coming, was his only one twelvemonth. He survived his uncle no longer; and ten thousand pounds, including the late legacies, was all that remained for his widow and daughters. His son was sent for as soon as his danger was known, and to him Mr. Dashwood recommended, with all the strength and urgency which illness could command, the interest of his mother-in-law and sisters. Mr. John Dashwood had not the strong feelings of the rest of the family; but he was affected by a recommendation of such a nature at such a time, and he promised to do every thing in his power to make them comfortable. His father was rendered easy by such an assurance, and Mr. John Dashwood had then leisure to consider how much there might prudently be in his power to do for them. He was not an ill-disposed young man, unless to be rather cold hearted and rather selfish is to be ill-disposed: but he was, in general, well respected; for he conducted himself with propriety in the discharge of his ordinary duties. Had he married a more amiable woman, he might have been made still more respectable than he was:—he might even have been made amiable himself; for he was very young when he married, and very fond of his wife. But Mrs. John Dashwood was a strong caricature of himself;—more narrow-minded and selfish. When he gave his promise to his father, he meditated within himself to increase the fortunes of his sisters by the present of a thousand pounds a-piece. He then really thought himself equal to it. The prospect of four thousand a-year, in addition to his present income, besides the remaining half of his own mother’s fortune, warmed his heart, and made him feel capable of generosity. “Yes, he would give them three thousand pounds: it would be liberal and handsome! It would be enough to make them completely easy. Three thousand pounds! he could spare so considerable a sum with little inconvenience.” He thought of it all day long, and for many days successively, and he did not repent. No sooner was his father’s funeral over, than Mrs. John Dashwood, without sending any notice of her intention to her mother-in-law, arrived with her child and their attendants. No one could dispute her right to come; the house was her husband’s from the moment of his father’s decease; but the indelicacy of her conduct was so much the greater, and to a woman in Mrs. Dashwood’s situation, with only common feelings, must have been highly unpleasing;—but in _her_ mind there was a sense of honor so keen, a generosity so romantic, that any offence of the kind, by whomsoever given or received, was to her a source of immovable disgust. Mrs. John Dashwood had never been a favourite with any of her husband’s family; but she had had no opportunity, till the present, of showing them with how little attention to the comfort of other people she could act when occasion required it. So acutely did Mrs. Dashwood feel this ungracious behaviour, and so earnestly did she despise her daughter-in-law for it, that, on the arrival of the latter, she would have quitted the house for ever, had not the entreaty of her eldest girl induced her first to reflect on the propriety of going, and her own tender love for all her three children determined her afterwards to stay, and for their sakes avoid a breach with their brother. Elinor, this eldest daughter, whose advice was so effectual, possessed a strength of understanding, and coolness of judgment, which qualified her, though only nineteen, to be the counsellor of her mother, and enabled her frequently to counteract, to the advantage of them all, that eagerness of mind in Mrs. Dashwood which must generally have led to imprudence. She had an excellent heart;—her disposition was affectionate, and her feelings were strong; but she knew how to govern them: it was a knowledge which her mother had yet to learn; and which one of her sisters had resolved never to be taught. Marianne’s abilities were, in many respects, quite equal to Elinor’s. She was sensible and clever; but eager in everything: her sorrows, her joys, could have no moderation. She was generous, amiable, interesting: she was everything but prudent. The resemblance between her and her mother was strikingly great. Elinor saw, with concern, the excess of her sister’s sensibility; but by Mrs. Dashwood it was valued and cherished. They encouraged each other now in the violence of their affliction. The agony of grief which overpowered them at first, was voluntarily renewed, was sought for, was created again and again. They gave themselves up wholly to their sorrow, seeking increase of wretchedness in every reflection that could afford it, and resolved against ever admitting consolation in future. Elinor, too, was deeply afflicted; but still she could struggle, she could exert herself. She could consult with her brother, could receive her sister-in-law on her arrival, and treat her with proper attention; and could strive to rouse her mother to similar exertion, and encourage her to similar forbearance. Margaret, the other sister, was a good-humored, well-disposed girl; but as she had already imbibed a good deal of Marianne’s romance, without having much of her sense, she did not, at thirteen, bid fair to equal her sisters at a more advanced period of life. Mrs. John Dashwood now installed herself mistress of Norland; and her mother and sisters-in-law were degraded to the condition of visitors. As such, however, they were treated by her with quiet civility; and by her husband with as much kindness as he could feel towards anybody beyond himself, his wife, and their child. He really pressed them, with some earnestness, to consider Norland as their home; and, as no plan appeared so eligible to Mrs. Dashwood as remaining there till she could accommodate herself with a house in the neighbourhood, his invitation was accepted. A continuance in a place where everything reminded her of former delight, was exactly what suited her mind. In seasons of cheerfulness, no temper could be more cheerful than hers, or possess, in a greater degree, that sanguine expectation of happiness which is happiness itself. But in sorrow she must be equally carried away by her fancy, and as far beyond consolation as in pleasure she was beyond alloy. Mrs. John Dashwood did not at all approve of what her husband intended to do for his sisters. To take three thousand pounds from the fortune of their dear little boy would be impoverishing him to the most dreadful degree. She begged him to think again on the subject. How could he answer it to himself to rob his child, and his only child too, of so large a sum? And what possible claim could the Miss Dashwoods, who were related to him only by half blood, which she considered as no relationship at all, have on his generosity to so large an amount. It was very well known that no affection was ever supposed to exist between the children of any man by different marriages; and why was he to ruin himself, and their poor little Harry, by giving away all his money to his half sisters? “It was my father’s last request to me,” replied her husband, “that I should assist his widow and daughters.” “He did not know what he was talking of, I dare say; ten to one but he was light-headed at the time. Had he been in his right senses, he could not have thought of such a thing as begging you to give away half your fortune from your own child.” “He did not stipulate for any particular sum, my dear Fanny; he only requested me, in general terms, to assist them, and make their situation more comfortable than it was in his power to do. Perhaps it would have been as well if he had left it wholly to myself. He could hardly suppose I should neglect them. But as he required the promise, I could not do less than give it; at least I thought so at the time. The promise, therefore, was given, and must be performed. Something must be done for them whenever they leave Norland and settle in a new home.” “Well, then, _let_ something be done for them; but _that_ something need not be three thousand pounds. Consider,” she added, “that when the money is once parted with, it never can return. Your sisters will marry, and it will be gone for ever. If, indeed, it could be restored to our poor little boy—” “Why, to be sure,” said her husband, very gravely, “that would make great difference. The time may come when Harry will regret that so large a sum was parted with. If he should have a numerous family, for instance, it would be a very convenient addition.” “To be sure it would.” “Perhaps, then, it would be better for all parties, if the sum were diminished one half.—Five hundred pounds would be a prodigious increase to their fortunes!” “Oh! beyond anything great! What brother on earth would do half so much for his sisters, even if _really_ his sisters! And as it is—only half blood!—But you have such a generous spirit!” “I would not wish to do any thing mean,” he replied. “One had rather, on such occasions, do too much than too little. No one, at least, can think I have not done enough for them: even themselves, they can hardly expect more.” “There is no knowing what _they_ may expect,” said the lady, “but we are not to think of their expectations: the question is, what you can afford to do.” “Certainly—and I think I may afford to give them five hundred pounds a-piece. As it is, without any addition of mine, they will each have about three thousand pounds on their mother’s death—a very comfortable fortune for any young woman.” “To be sure it is; and, indeed, it strikes me that they can want no addition at all. They will have ten thousand pounds divided amongst them. If they marry, they will be sure of doing well, and if they do not, they may all live very comfortably together on the interest of ten thousand pounds.” “That is very true, and, therefore, I do not know whether, upon the whole, it would not be more advisable to do something for their mother while she lives, rather than for them—something of the annuity kind I mean.—My sisters would feel the good effects of it as well as herself. A hundred a year would make them all perfectly comfortable.” His wife hesitated a little, however, in giving her consent to this plan. “To be sure,” said she, “it is better than parting with fifteen hundred pounds at once. But, then, if Mrs. Dashwood should live fifteen years we shall be completely taken in.” “Fifteen years! my dear Fanny; her life cannot be worth half that purchase.” “Certainly not; but if you observe, people always live for ever when there is an annuity to be paid them; and she is very stout and healthy, and hardly forty. An annuity is a very serious business; it comes over and over every year, and there is no getting rid of it. You are not aware of what you are doing. I have known a great deal of the trouble of annuities; for my mother was clogged with the payment of three to old superannuated servants by my father’s will, and it is amazing how disagreeable she found it. Twice every year these annuities were to be paid; and then there was the trouble of getting it to them; and then one of them was said to have died, and afterwards it turned out to be no such thing. My mother was quite sick of it. Her income was not her own, she said, with such perpetual claims on it; and it was the more unkind in my father, because, otherwise, the money would have been entirely at my mother’s disposal, without any restriction whatever. It has given me such an abhorrence of annuities, that I am sure I would not pin myself down to the payment of one for all the world.” “It is certainly an unpleasant thing,” replied Mr. Dashwood, “to have those kind of yearly drains on one’s income. One’s fortune, as your mother justly says, is _not_ one’s own. To be tied down to the regular payment of such a sum, on every rent day, is by no means desirable: it takes away one’s independence.” “Undoubtedly; and after all you have no thanks for it. They think themselves secure, you do no more than what is expected, and it raises no gratitude at all. If I were you, whatever I did should be done at my own discretion entirely. I would not bind myself to allow them any thing yearly. It may be very inconvenient some years to spare a hundred, or even fifty pounds from our own expenses.” “I believe you are right, my love; it will be better that there should be no annuity in the case; whatever I may give them occasionally will be of far greater assistance than a yearly allowance, because they would only enlarge their style of living if they felt sure of a larger income, and would not be sixpence the richer for it at the end of the year. It will certainly be much the best way. A present of fifty pounds, now and then, will prevent their ever being distressed for money, and will, I think, be amply discharging my promise to my father.” “To be sure it will. Indeed, to say the truth, I am convinced within myself that your father had no idea of your giving them any money at all. The assistance he thought of, I dare say, was only such as might be reasonably expected of you; for instance, such as looking out for a comfortable small house for them, helping them to move their things, and sending them presents of fish and game, and so forth, whenever they are in season. I’ll lay my life that he meant nothing farther; indeed, it would be very strange and unreasonable if he did. Do but consider, my dear Mr. Dashwood, how excessively comfortable your mother-in-law and her daughters may live on the interest of seven thousand pounds, besides the thousand pounds belonging to each of the girls, which brings them in fifty pounds a year a-piece, and, of course, they will pay their mother for their board out of it. Altogether, they will have five hundred a-year amongst them, and what on earth can four women want for more than that?—They will live so cheap! Their housekeeping will be nothing at all. They will have no carriage, no horses, and hardly any servants; they will keep no company, and can have no expenses of any kind! Only conceive how comfortable they will be! Five hundred a year! I am sure I cannot imagine how they will spend half of it; and as to your giving them more, it is quite absurd to think of it. They will be much more able to give _you_ something.” “Upon my word,” said Mr. Dashwood, “I believe you are perfectly right. My father certainly could mean nothing more by his request to me than what you say. I clearly understand it now, and I will strictly fulfil my engagement by such acts of assistance and kindness to them as you have described. When my mother removes into another house my services shall be readily given to accommodate her as far as I can. Some little present of furniture too may be acceptable then.” “Certainly,” returned Mrs. John Dashwood. “But, however, _one_ thing must be considered. When your father and mother moved to Norland, though the furniture of Stanhill was sold, all the china, plate, and linen was saved, and is now left to your mother. Her house will therefore be almost completely fitted up as soon as she takes it.” “That is a material consideration undoubtedly. A valuable legacy indeed! And yet some of the plate would have been a very pleasant addition to our own stock here.” “Yes; and the set of breakfast china is twice as handsome as what belongs to this house. A great deal too handsome, in my opinion, for any place _they_ can ever afford to live in. But, however, so it is. Your father thought only of _them_. And I must say this: that you owe no particular gratitude to him, nor attention to his wishes; for we very well know that if he could, he would have left almost everything in the world to _them_.” This argument was irresistible. It gave to his intentions whatever of decision was wanting before; and he finally resolved, that it would be absolutely unnecessary, if not highly indecorous, to do more for the widow and children of his father, than such kind of neighbourly acts as his own wife pointed out.`;58:Tf23,${[ assert(new Rope(austen).toString(), austen, "Constructor and toString: "), assert(new Rope(austen).length, austen.length, "length: "), (() => { const r = new Rope(austen); return assert( [r.charAt(0), r.charAt(Math.round(austen.length/2)), r.charAt(austen.length-1), r.charAt(-1),r.charAt(austen.length) ].join(","), [austen.charAt(0), austen.charAt(Math.round(austen.length/2)), austen.charAt(austen.length-1), austen.charAt(-1),austen.charAt(austen.length) ].join(","), "charAt bounds: " ); })(), (() => { const r = new Rope(austen); return assert( [r.substring(1, 4), r.substring(0, 5), r.substring(2, austen.length+100), r.substring(austen.length, austen.length)].join("|"), [austen.substring(1, 4), austen.substring(0, 5), austen.substring(2, austen.length+100), austen.substring(austen.length, austen.length)].join("|"), "substring clamps: " ); })(), (() => { const r = new Rope("cat").concat("dog").concat(new Rope("fish")); return assert([r.toString(), r.length].join(","), "catdogfish,10", "concat string and new rope: "); })(), (() => { const r = new Rope("dogfish").insert(0, "cat").insert(3, " or "); r.insert(r.length, "."); return assert(r.toString(), "cat or dogfish.", "insert at start, middle and end: "); })(), assert(new Rope("0123456789").delete(0, 2).delete(3, 3).delete(4, 99).toString(), "2345", "delete ranges and clamps: "), (() => { const r = new Rope("cat dog fish"); r.delete(0, r.length); return assert([r.toString(), r.length].join(","), ",0", "delete whole rope: "); })(), (() => { const r = new Rope(austen, { chunkSize: 2 }); return assert([r.charAt(1), r.charAt(100), r.substring(120, 130)].join("|"), [austen.charAt(1), austen.charAt(100), austen.substring(120, 130)].join("|"), "ops across chunk boundaries: "); })(), (() => { const s1 = new Rope("cat ").concat("dog ").concat("fish ").toString(); const s2 = new Rope().concat(new Rope("cat ")).concat(new Rope().concat("dog ").concat("fish ")).toString(); return assert(s1, s2, "concat associativity (by value): "); })(), (() => { const r = new Rope(""); const parts = austen.split(/\s+/); for (const p of parts) { r.concat(p).concat(" "); } return assert(r.toString().trim(), parts.join(" "), "many small concats: "); })(), (() => { const r = new Rope(austen); let rebuilt = ""; for (const i of [...Array(r.length).keys()]) { rebuilt += r.charAt(i); } return assert(rebuilt, r.toString(), "charAt reconstructs string: "); })(), (() => { const r = new Rope(austen); r.insert(1, "").delete(2, 2).concat(""); // no-ops return assert(r.toString(), austen, "no-ops (empty insert/delete/concat): "); })(), (() => { const rope = new Rope(); for (let i = 0; i < 4096; i++) { rope.concat("x"); } const inspect = (node) => { if (!node) { return {valid: true, height: 0, length: 0}; } if (node.text !== null) { return {valid: node.height === 1 && node.weight === 0, height: 1, length: node.text.length}; } const left = inspect(node.left); const right = inspect(node.right); const height = 1 + Math.max(left.height, right.height); const length = left.length + right.length; return { height, length, valid: left.valid && right.valid && Math.abs(left.height - right.height) <= 1 && node.height === height && node.weight === left.length }; }; const structure = inspect(rope.root); const other = new Rope("A".repeat(2048)); const before = other.toString(); new Rope("B").concat(other); return assert( structure.valid && structure.length === 4096 && rope.length === 4096 && other.toString() === before && new Rope("0123456789").substring(7, 2) === "23456", true, "Balance, weights, non-aliasing and reversed substring arguments:" ); })(), ].join("
")}59:T1a32,

${pts1 .reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()) .toDot({ scale: 0.5 })} ${(()=>{ const kd = pts1.reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const medianSeq = kd.toArray("median"); return Plot.plot({ inset: 15, width: 300, aspectRatio: 1, x: { ticks: 8, grid: true }, y: { ticks: 8, grid: true }, marks: [ Plot.line(medianSeq, { x: "x", y: "y", curve: "catmull-rom", strokeDasharray: [8, 8], opacity: 0.5 }), Plot.dot(pts1, { fill: "firebrick", r: 5, opacity: 0.7 }), Plot.frame() ] }); })()}

${[ assert([...new KdTree([{ x: 1, y: 4 },{ x: 5, y: -7 }, { x: 0, y: 0 }])].map(({ x, y }) => `(${x},${y})`).join(","), "(1,4),(0,0),(5,-7)", "Constructor and iterator"), assert([...new KdTree().insert({ x: 1, y: 4 }).insert({ x: 5, y: -7 })].map(({ x, y }) => `(${x},${y})`).join(","), "(5,-7),(1,4)", "Empty constructor and insert"), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert(kd.toArray("bfs").map(({x,y}) => `(${x},${y})`).join(","), "(10,0),(0,3),(9,-2),(9,4),(0,0),(8,5),(2.5,5.5)", "toArray('bfs')")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert(kd.toArray("pre").map(({x,y}) => `(${x},${y})`).join(","), "(10,0),(0,3),(9,-2),(0,0),(9,4),(8,5),(2.5,5.5)", "toArray('pre')")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert(kd.toArray("median").map(({x,y}) => `(${x},${y})`).join(","), "(8,5),(0,3),(0,0),(2.5,5.5),(10,0),(9,-2),(9,4)", "toArray('median')")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const {x,y} = kd.find({x:8,y:5}).pt; return assert(`(${x},${y})`,"(8,5)","find existing")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert(kd.find({x:3.5,y:4}),null,"find missing")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert([...kd.bfs()].map(({x,y}) => `(${x},${y})`).join(","), "(10,0),(0,3),(9,-2),(9,4),(0,0),(8,5),(2.5,5.5)", "bfs")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert([...kd.dfsPreOrder()].map(({x,y}) => `(${x},${y})`).join(","), "(10,0),(0,3),(9,-2),(0,0),(9,4),(8,5),(2.5,5.5)", "dfsPreOrder")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert([...kd.spatialMedian()].map(({x,y}) => `(${x},${y})`).join(","), "(8,5),(0,3),(0,0),(2.5,5.5),(10,0),(9,-2),(9,4)", "spatialMedian")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert([...kd].map(({x,y}) => `(${x},${y})`).join(","), "(8,5),(0,3),(0,0),(2.5,5.5),(10,0),(9,-2),(9,4)", "Iterate in spatial median order")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pt = kd.nearestNeighbour({x:7,y:0}) return assert(`(${pt.x},${pt.y})`, "(9,-2)", "Nearest neighbour")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pt = kd.nearestNeighbour({x:5,y:0}) return assert(`(${pt.x},${pt.y})`, "(9,-2)", "Nearest neighbour tied")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pts = [...kd.rangeQuery({x:7,y:3},{x:10,y:5})].map(({x,y})=>`(${x},${y})`) return assert(pts.join(","), "(9,4),(8,5)", "Range query")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pts = [...kd.rangeQuery({x:10,y:5},{x:7,y:3})].map(({x,y})=>`(${x},${y})`) return assert(pts.join(","), "", "Range query empty")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pts = [...kd.pointsWithinRadius({x:2,y:3},3)].map(({x,y})=>`(${x},${y})`) return assert(pts.join(","), "(0,3),(2.5,5.5)", "pointsWithinRadius")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pts = [...kd.pointsWithinRadius({x:1,y:3},0.99999)].map(({x,y})=>`(${x},${y})`) return assert(pts.join(","), "", "pointsWithinRadius empty")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pts = [...kd.kNearestNeighbours({x:1,y:3},3)].map(({x,y})=>`(${x},${y})`) return assert(pts.join(","), "(0,0),(0,3),(2.5,5.5)", "kNearestNeighbours")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); const pts = [...kd.kNearestNeighbours({x:1,y:3},0)].map(({x,y})=>`(${x},${y})`) return assert(pts.join(","), "", "kNearestNeighbours empty")})(), (()=>{ const kd = [[10, 0],[0, 3],[9, -2],[9, 4],[8, 5],[0, 0],[2.5, 5.5]].reduce((kd, [x, y]) => kd.insert({ x, y }), new KdTree()); return assert(kd.clear().toArray('pre').join(","),"","clear")})(), (() => { const points = [ {id: "a", x: 0, y: 0, z: 1000}, {id: "b", x: 2, y: 0, z: 0} ]; const kd = new KdTree(points, ["x", "y"]); const nearest = kd.nearestNeighbour({x: 0, y: 0, z: 0}); const within = [...kd.pointsWithinRadius({x: 0, y: 0, z: 0}, 0.5)]; const ranged = [...kd.rangeQuery({x: -1, y: -1, z: 9999}, {x: 1, y: 1, z: 9999})]; return assert([ nearest.id, within.map((point) => point.id).join(","), ranged.map((point) => point.id).join(",") ].join("|"), "a|a|a", "Distance and range calculations use only configured coordinate axes:" ); })() ].join("
")}5a:T97f,${ [ (() => { const b = { x: 0, y: 0, halfWidth: 2, halfHeight: 3 }; const mm = Quadtree.halfToMinMax(b); return assert( JSON.stringify(mm), JSON.stringify({ minX: -2, maxX: 2, minY: -3, maxY: 3 }), "Quadtree.halfToMinMax: conversion from half to min/max" ); })(), (() => { const mm = { minX: -2, maxX: 2, minY: -3, maxY: 3 }; const b = Quadtree.minMaxToHalf(mm); return assert( JSON.stringify(b), JSON.stringify({ x: 0, y: 0, halfWidth: 2, halfHeight: 3 }), "Quadtree.minMaxToHalf: conversion from min/max to half" ); })(), (() => { const dist = Quadtree.minL1DistancePointAABB({ x: 5, y: 5 }, { minX: 0, minY: 0, maxX: 2, maxY: 2 }); return assert( dist, 6, // (5-2) + (5-2) "Quadtree.minL1DistancePointAABB: Manhattan distance outside box" ); })(), (() => { const dist = Quadtree.minL1DistancePointAABB({ x: 1, y: 1 }, { minX: 0, minY: 0, maxX: 2, maxY: 2 }); return assert( dist, 0, "Quadtree.minL1DistancePointAABB: zero distance inside box" ); })(), (() => { const box = { minX: 0, minY: 0, maxX: 3, maxY: 3 }; const quads = Quadtree.splitBox(box).map(q => q.dir); return assert( quads.join(","), "NW,NE,SW,SE", "Quadtree.splitBox: quadrants in consistent NW, NE, SW, SE order" ); })(), (() => { const a = { x: 0, y: 0, halfWidth: 2, halfHeight: 2 }; const r = { x: 5, y: 5, halfWidth: 2, halfHeight: 2 }; return assert( Quadtree.intersectsAABB(a, r), false, "Quadtree.intersectsAABB: non-overlapping boxes return false" ); })(), (() => { const a = { x: 0, y: 0, halfWidth: 2, halfHeight: 2 }; const r = { x: 1, y: 1, halfWidth: 2, halfHeight: 2 }; return assert( Quadtree.intersectsAABB(a, r), true, "Quadtree.intersectsAABB: overlapping boxes return true" ); })(), (() => { const b = { x: 10, y: 20, halfWidth: 3, halfHeight: 4 }; const mm = Quadtree.halfToMinMax(b); const b2 = Quadtree.minMaxToHalf(mm); return assert( JSON.stringify(b2), JSON.stringify(b), "Quadtree: halfToMinMax to minMaxToHalf round-trip preserves boundary" ); })(), (() => { const mm = { minX: -5, maxX: 7, minY: -2, maxY: 6 }; const b = Quadtree.minMaxToHalf(mm); const mm2 = Quadtree.halfToMinMax(b); return assert( JSON.stringify(mm2), JSON.stringify(mm), "Quadtree: minMaxToHalf to halfToMinMax round-trip preserves min/max box" ); })() ].join("
") }5b:Td52,${ [ (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 4, 4), capacity: 2 }); for (const p of [{x:-3,y:-1},{x:2,y:-2},{x:1,y:1},{x:-1,y:3},{x:0,y:0}]) { qt.insert(p); } return assert( [...qt.rangeQuery({ x: 0, y: 0, halfWidth: 1e9, halfHeight: 1e9 })].length, 5, "PointQuadtree: constructor, insert and rangeQuery(all): "); })(), (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 4, 4), capacity: 2 }); for (const p of [{x:-3,y:-1},{x:2,y:-2},{x:1,y:1},{x:-1,y:3},{x:0,y:0}]) { qt.insert(p); } return assert( ptsStr([...qt.rangeQuery(rect(-2, -2, 2, 2))]), ptsStr([{x:-3,y:-1},{x:0,y:0}]), "PointQuadtree: rangeQuery NW (inclusive edges): "); })(), (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 2, 2), autoResize: true, capacity: 1 }); qt.insert({ x: 5, y: 5 }); return assert( ptsStr([...qt.rangeQuery(rect(5, 5, 0, 0))]), ptsStr([{x:5,y:5}]), "PointQuadtree: autoResize=true admits out-of-bounds: "); })(), (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 2, 2), autoResize: false, capacity: 1 }) .insert({ x: 0, y: 0 }).insert({ x: 5, y: 5 }); return assert( [...qt.rangeQuery({ x: 0, y: 0, halfWidth: 1e9, halfHeight: 1e9 })].length, 1, "PointQuadtree: autoResize=false rejects out-of-bounds: "); })(), (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 8, 8), capacity: 1, maxDepth: 8 }); for (const x of [-3,-2,-1,0,1,2,3]) { for (const y of [-3,-2,-1,0,1,2,3]) { qt.insert({ x, y }); } } return assert( [...qt.rangeQuery(rect(0, 0, 1, 1))].length, 9, "PointQuadtree: local range after many inserts: "); })(), (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 4, 4), capacity: 2 }); for (const p of [{x:0,y:0},{x:2,y:0},{x:0,y:2},{x:2,y:2}]) { qt.insert(p); } return assert( ptsStr([...qt.rangeQuery(rect(1, 1, 1, 1))]), ptsStr([{x:0,y:0},{x:2,y:0},{x:0,y:2},{x:2,y:2}]), "PointQuadtree: rangeQuery includes boundary points: "); })(), (() => { const qt = new PointQuadtree({ boundary: rect(0, 0, 8, 8), capacity: 1, maxDepth: 0 }); for (const p of [{x:-1,y:-1},{x:0,y:0},{x:1,y:1}]) { qt.insert(p); } return assert( ptsStr([...qt.rangeQuery(rect(0, 0, 1, 1))]), ptsStr([{x:-1,y:-1},{x:0,y:0},{x:1,y:1}]), "PointQuadtree: correctness with maxDepth=0: "); })(), (() => { const qt = new PointQuadtree({boundary: rect(0, 0, 8, 8),capacity: 1}); for (const point of [ {x: -4, y: -4}, {x: 4, y: -4}, {x: -4, y: 4}, {x: 4, y: 4} ]) { qt.insert(point); } const cells = [...qt.cells({leavesOnly: true})]; return assert( cells.length > 0 && cells.every((cell) => cell.isLeaf), true, "PointQuadtree: leavesOnly excludes internal cells:" ); })(), (() => { let threw = false; try { new PointQuadtree({ boundary: rect(0, 0, 2, 2), autoResize: false, strict: true}).insert({x: 10, y: 10}); } catch (error) { threw = error instanceof RangeError; } return assert(threw, true, "PointQuadtree: strict mode rejects an out-of-bounds point:"); })(), (() => { let threw = false; try { new PointQuadtree({boundary: rect(0, 0, 0, 2)}); } catch (error) { threw = error instanceof RangeError; } return assert(threw, true, "PointQuadtree: zero-width root boundary is rejected:"); })(), ].join("
") }5c:Tb37,${ [ (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 8, 8), capacity: 2 }); const regions = [ regionBounds("A", -6, -6, 1, 1), // NW regionBounds("B", 5, -5, 1, 1), // NE regionBounds("C", 0, 0, 3, 3), // Straddles centre (stored at ancestor) regionBounds("D", -5, 5, 1, 2), // SW regionBounds("E", 6, 6, 1, 1) // SE ]; for (const r of regions) { qt.insert(r); } return assert( rgnsStr([...qt.rangeQuery({ x: 0, y: 0, halfWidth: 1e9, halfHeight: 1e9 })]), rgnsStr(regions), "RegionQuadtree: constructor, insert and rangeQuery(all): "); })(), (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 8, 8), capacity: 1 }); const a = regionBounds("a", -6, -6, 1, 1); const b = regionBounds("b", 5, -5, 1, 1); // fully in NE const c = regionBounds("c", 0, 0, 3, 3); // straddles centre for (const r of [a, b, c]) { qt.insert(r); } return assert( rgnsStr([...qt.rangeQuery(rect(4, -4, 4, 4))]), "b", "RegionQuadtree: rangeQuery NE excludes straddlers (wholly-inside): "); })(), (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 8, 8), capacity: 1 }); qt.insert(regionBounds("a", -2, -2, 2, 2)); return assert( rgnsStr( [...qt.rangeQuery(rect(-2, -2, 4, 4))]), "a", "RegionQuadtree: boundary-inclusive match: "); })(), (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 2, 2), capacity: 1, autoResize: true }); qt.insert(regionBounds("a", 10, 10, 1, 1)); return assert( rgnsStr([...qt.rangeQuery(rect(10, 10, 2, 2))]), "a", "RegionQuadtree: autoResize=true admits out-of-bounds: "); })(), (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 2, 2), capacity: 1, autoResize: false }); qt.insert(regionBounds("ok", 0, 0, 1, 1)); qt.insert(regionBounds("bad", 10, 10, 1, 1)); return assert( rgnsStr([...qt.rangeQuery({ x: 0, y: 0, halfWidth: 1e9, halfHeight: 1e9 })]), "ok", "RegionQuadtree: autoResize=false rejects out-of-bounds: "); })(), (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 16, 16), capacity: 1, maxDepth: 6 }); const ins = []; for (const x of [-6,-4,-2,0,2,4,6]) { for (const y of [-6,-4,-2,0,2,4,6]) { ins.push(regionBounds(`${x},${y}`, x, y, 0.5, 0.5)); // 1x1 regions } } for (const r of ins) { qt.insert(r); } return assert( rgnsStr([...qt.rangeQuery(rect(2, 2, 1, 1))]), "2,2", "RegionQuadtree: local range returns only fully contained regions: "); })(), (() => { const qt = new RegionQuadtree({ boundary: rect(0, 0, 16, 16), capacity: 1 }); qt.insert(regionBounds("a", 2, 2, 0.5, 0.5)); return assert( rgnsStr([...qt.rangeQuery(rect(2, 2, 0.2, 0.2))]), "", "RegionQuadtree: small range excludes partially overlapping region: "); })(), ].join("
") }5d:Te77,${ [ (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 4, 4, 4), capacity: 2 }); for (const p of [{x:-3,y:-1,z:-2},{x:2,y:-2,z:-1},{x:1,y:1,z:1},{x:-1,y:3,z:0},{x:0,y:0,z:0}]) { ot.insert(p); } return assert( [...ot.rangeQuery(box(0, 0, 0, 1e9, 1e9, 1e9))].length, 5, "PointOctree: constructor, insert and rangeQuery(all): " ); })(), (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 4, 4, 4), capacity: 2 }); for (const p of [{x:-3,y:-1,z:-2},{x:2,y:-2,z:-1},{x:1,y:1,z:1},{x:-1,y:3,z:0},{x:0,y:0,z:0}]) { ot.insert(p); } return assert( pts3Str([...ot.rangeQuery(box(-2, -2, -2, 2, 2, 2))]), pts3Str([{x:-3,y:-1,z:-2},{x:0,y:0,z:0}]), "PointOctree: rangeQuery NWB (inclusive edges): " ); })(), (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 2, 2, 2), autoResize: true, capacity: 1 }); ot.insert({ x: 5, y: 5, z: 5 }); return assert( pts3Str([...ot.rangeQuery(box(5, 5, 5, 0, 0, 0))]), pts3Str([{x:5,y:5,z:5}]), "PointOctree: autoResize=true admits out-of-bounds: " ); })(), (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 2, 2, 2), autoResize: false, capacity: 1 }) .insert({ x: 0, y: 0, z: 0 }) .insert({ x: 5, y: 5, z: 5 }); return assert( [...ot.rangeQuery(box(0, 0, 0, 1e9, 1e9, 1e9))].length, 1, "PointOctree: autoResize=false rejects out-of-bounds: " ); })(), (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 8, 8, 8), capacity: 1, maxDepth: 8 }); for (const x of [-3,-2,-1,0,1,2,3]) { for (const y of [-3,-2,-1,0,1,2,3]) { for (const z of [-3,-2,-1,0,1,2,3]) { ot.insert({ x, y, z }); } } } return assert( [...ot.rangeQuery(box(0, 0, 0, 1, 1, 1))].length, 27, "PointOctree: local range after many inserts: " ); })(), (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 4, 4, 4), capacity: 2 }); const corners = [ {x:0,y:0,z:0},{x:2,y:0,z:0},{x:0,y:2,z:0},{x:0,y:0,z:2}, {x:2,y:2,z:0},{x:2,y:0,z:2},{x:0,y:2,z:2},{x:2,y:2,z:2} ]; for (const p of corners) { ot.insert(p); } return assert( pts3Str([...ot.rangeQuery(box(1, 1, 1, 1, 1, 1))]), pts3Str(corners), "PointOctree: rangeQuery includes boundary points (corners): " ); })(), (() => { const ot = new PointOctree({ boundary: box(0, 0, 0, 8, 8, 8), capacity: 1, maxDepth: 0 }); for (const p of [{x:-1,y:-1,z:-1},{x:0,y:0,z:0},{x:1,y:1,z:1}]) { ot.insert(p); } return assert( pts3Str([...ot.rangeQuery(box(0, 0, 0, 1, 1, 1))]), pts3Str([{x:-1,y:-1,z:-1},{x:0,y:0,z:0},{x:1,y:1,z:1}]), "PointOctree: correctness with maxDepth=0: " ); })(), (() => { const ot = new PointOctree({boundary: box(0, 0, 0, 8, 8, 8), capacity: 1}); for (const point of [ {x: -4, y: -4, z: -4}, {x: 4, y: -4, z: -4}, {x: -4, y: 4, z: 4}, {x: 4, y: 4, z: 4} ]) { ot.insert(point); } const cells = [...ot.cells({leavesOnly: true})]; return assert(cells.length > 0 && cells.every((cell) => cell.isLeaf), true, "PointOctree: leavesOnly excludes internal cells:"); })(), (() => { let threw = false; try { new PointOctree({ boundary: box(0, 0, 0, 2, 2, 2), autoResize: false, strict: true}).insert({x: 10, y: 10, z: 10}); } catch (error) { threw = error instanceof RangeError; } return assert(threw, true, "PointOctree: strict mode rejects an out-of-bounds point:"); })(), (() => { let threw = false; try {new PointOctree({boundary: box(0, 0, 0, 0, 2, 2)}); } catch (error) { threw = error instanceof RangeError; } return assert(threw, true, "PointOctree: zero-width root boundary is rejected:"); })(), ].join("
") }5e:Tc13,${ [ (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 8, 8, 8), capacity: 2 }); const regions = [ {id:"a", bounds:box(-6, -6, -6, 1, 1, 1)}, // NWB {id:"b", bounds:box(5, -5, -5, 1, 1, 1)}, // NEB {id:"c", bounds:box(0, 0, 0, 3, 3, 3)}, // straddles center {id:"d", bounds:box(-5, 5, -4, 1, 2, 1)}, // SWB-ish {id:"e", bounds:box(6, 6, 6, 1, 1, 1)} // SET ]; for (const r of regions) { ot.insert(r); } return assert( rgns3Str([...ot.rangeQuery(box(0, 0, 0, 1e9, 1e9, 1e9))]), rgns3Str(regions), "RegionOctree: constructor, insert and rangeQuery(all): " ); })(), (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 8, 8, 8), capacity: 1 }); const a = {id:"a", bounds:box( -6, -6, -6, 1, 1, 1)}; const b = {id:"b", bounds:box( 5, -5, -5, 1, 1, 1)}; // fully NEB const c = {id:"c", bounds:box( 0, 0, 0, 3, 3, 3)}; // straddles center for (const r of [a, b, c]) { ot.insert(r); } return assert( rgns3Str([...ot.rangeQuery(box(4, -4, -4, 4, 4, 4))]), "b", "RegionOctree: rangeQuery NEB excludes straddlers (wholly-inside): " ); })(), (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 8, 8, 8), capacity: 1 }); ot.insert({id:"a", bounds:box( -2, -2, -2, 2, 2, 2)}); return assert( rgns3Str([...ot.rangeQuery(box(-2, -2, -2, 4, 4, 4))]), "a", "RegionOctree: boundary-inclusive match: " ); })(), (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 2, 2, 2), capacity: 1, autoResize: true }); ot.insert({id:"z", bounds:box( 10, 10, 10, 1, 1, 1)}); return assert( rgns3Str([...ot.rangeQuery(box(10, 10, 10, 2, 2, 2))]), "z", "RegionOctree: autoResize=true admits out-of-bounds: " ); })(), (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 2, 2, 2), capacity: 1, autoResize: false }); ot.insert({id:"ok", bounds:box( 0, 0, 0, 1, 1, 1)}); ot.insert({id:"bad", bounds:box(10, 10, 10, 1, 1, 1)}); return assert( rgns3Str([...ot.rangeQuery(box(0, 0, 0, 1e9, 1e9, 1e9))]), "ok", "RegionOctree: autoResize=false rejects out-of-bounds: " ); })(), (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 16, 16, 16), capacity: 1, maxDepth: 6 }); const ins = []; for (const x of [-6,-4,-2,0,2,4,6]) { for (const y of [-6,-4,-2,0,2,4,6]) { for (const z of [-6,-4,-2,0,2,4,6]) { ins.push({id:`${x},${y},${z}`, bounds:box(x, y, z, 0.5, 0.5, 0.5)}); } } } for (const r of ins) { ot.insert(r); } return assert( rgns3Str([...ot.rangeQuery(box(2, 2, 2, 1, 1, 1))]), "2,2,2", "RegionOctree: local range returns only fully contained regions: " ); })(), (() => { const ot = new RegionOctree({ boundary: box(0, 0, 0, 16, 16, 16), capacity: 1 }); ot.insert({id:"a", bounds:box( 2, 2, 2, 0.5, 0.5, 0.5)}); const tiny = [...ot.rangeQuery(box(2, 2, 2, 0.2, 0.2, 0.2))]; // [1.8,2.2]^3 return assert( rgns3Str(tiny), "", "RegionOctree: small range excludes partially overlapping region: " ); })(), ].join("
") }5f:[] 2d:{"id":"f1b50b3e970d2c44","slug":"adts-and-data-structures","title":"ADTs and Data Structures","thumbnail":"59f397852fe75f061ba4bca04e091dc5b9fadf841ddfc48bce2e410d23f2f40f","access_level":"public","create_time":"$D2025-07-07T14:31:34.290Z","update_time":"$D2026-09-22T14:00:44.474Z","view_time":null,"first_public_time":"$D2026-09-22T14:24:21.972Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":5176,"publish_version":5176,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"},{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"cf3a41cde0560514","slug":"data-structures","title":"data structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"ADTs and Data Structures","cells":[{"id":0,"value":"# ADTs and Data Structures\n\n_Implementations of some common abstract data types (ADTs). The goal is to provide accessible and efficient data structures with clear source code for learning and teaching._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":493,"value":"This page contains all classes in one document for ease of use when importing into your own pages. For example, to use both a priority queue and a k-d tree :\n\n```javascript\nimport { PriorityQueue, KdTree } from \"observable:@jwolondon/adts-and-data-structures\"\n```\nFor details see the [data structure documentation](https://observablehq.com/@jwolondon/data-structure-docs). The classes are grouped by their API even if internally they use other data structures. For example, a `BoundedPriorityQueue` is used to represent an ordered linear sequence of values while internally it is an array-backed binary heap for efficient querying.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":496,"value":"## 1. Linear data structures \n_See [documentation](https://observablehq.com/@jwolondon/data-structures-linear)._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":9,"value":"display(md`\\`▶ Stack\\``); // In place of cell introspection\n\nclass Stack {\n #xs; // The stack items\n\n constructor(xs = []) {\n this.#xs = [...xs];\n }\n\n // ------------------------------ Public ADT methods\n\n size() {\n return this.#xs.length;\n }\n\n isEmpty() {\n return this.#xs.length === 0;\n }\n\n peek() {\n if (this.isEmpty()) {\n throw new Error(\"Attempting to peek an empty stack\");\n }\n return this.#xs.at(-1);\n }\n\n toArray() {\n return [...this.#xs];\n }\n\n push(x) {\n this.#xs.push(x);\n return this;\n }\n\n pop() {\n if (this.isEmpty()) {\n throw new Error(\"Attempting to pop an empty stack\");\n }\n return this.#xs.pop();\n }\n\n clear() {\n this.#xs = [];\n return this;\n }\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":61,"value":"$2f","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":319,"value":"$30","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2770,"value":"$31","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2898,"value":"$32","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":533,"value":"$33","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":642,"value":"## 2. General tree data structures\n_See [documentation](https://observablehq.com/@jwolondon/data-structures-tree)._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1849,"value":"$34","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1852,"value":"$35","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":647,"value":"$36","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":662,"value":"$37","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":928,"value":"$38","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4452,"value":"## 3. Search-oriented tree structures\n\nSee [documentation](https://observablehq.com/@jwolondon/data-structures-search-tree).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":936,"value":"$39","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1044,"value":"$3a","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1472,"value":"display(md`\\`▶ AVLTreeNode\\``); // In place of cell introspection\n\nclass AVLTreeNode extends BinaryTreeNode {\n #height = 1;\n\n get height() {\n return this.#height;\n }\n\n static setNodeHeight(node, h) {\n if (node instanceof AVLTreeNode) {\n node.#setHeight(h);\n } else {\n throw new TypeError(\"Expected AVLTreeNode\");\n }\n }\n\n // ------------------------------ Private helpers\n\n #setHeight(h) {\n this.#height = h;\n }\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1074,"value":"$3b","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1483,"value":"display(md`\\`▶ RedBlackTreeNode\\``); // In place of cell introspection\n\nclass RedBlackTreeNode extends BinaryTreeNode {\n constructor(value) {\n super(value);\n this.clr = \"R\"; // R = red, B = black\n }\n\n get isRed() {\n return this.clr === \"R\";\n }\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4456,"value":"## 4. Text-oriented tree structures\n\nSee [documentation](https://observablehq.com/@jwolondon/data-structures-text-tree).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":1208,"value":"display(md`\\`▶ TrieNode\\``); // In place of cell introspection\n\nclass TrieNode {\n constructor() {\n this.children = new Map();\n this.isWord = false;\n }\n\n markAsWord() {\n this.isWord = true;\n }\n\n unmarkAsWord() {\n this.isWord = false;\n }\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1147,"value":"$3c","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4900,"value":"$3d","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4903,"value":"display(md`\\`▶ SuffixTrieNode\\``); // In place of cell introspection\n\nclass SuffixTrieNode {\n constructor() {\n this.children = new Map();\n this.positions = [];\n }\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4448,"value":"$3e","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4461,"value":"$3f","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1880,"value":"## 5. Spatial data structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4057,"value":"_See [documentation](https://observablehq.com/@jwolondon/data-structures-spatial)._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4096,"value":"display(md`\\`▶ KdTreeNode\\``); // In place of cell introspection\n\nclass KdTreeNode {\n #pt;\n #axis;\n #left = null;\n #right = null;\n #parent = null;\n\n constructor(pt, axis = 0) {\n this.#pt = pt;\n this.#axis = axis;\n }\n\n get pt() {\n return this.#pt;\n }\n get axis() {\n return this.#axis;\n }\n get left() {\n return this.#left;\n }\n get right() {\n return this.#right;\n }\n get parent() {\n return this.#parent;\n }\n\n setLeft(node) {\n this.#left = node;\n if (node) {\n node.#parent = this;\n }\n return this;\n }\n\n setRight(node) {\n this.#right = node;\n if (node) {\n node.#parent = this;\n }\n return this;\n }\n\n isLeaf() {\n return this.#left === null && this.#right === null;\n }\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4099,"value":"$40","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4201,"value":"$41","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4171,"value":"$42","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4177,"value":"$43","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4179,"value":"$44","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4730,"value":"$45","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4735,"value":"$46","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4737,"value":"$47","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4739,"value":"$48","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"---\n\n## Appendix: Tests","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":193,"value":"function assert(obs, exp = \"value not yet provided\", msg = \"\") {\n if (obs === exp) {\n return `${msg}✓`;\n } else {\n throw Error(`✗ Assertion failed in ${msg}: expected ${exp}, while observed value was ${obs}.`);\n }\n}\n\nfunction assertEqualsPt(obs, exp = {}, msg = \"\") {\n if (obs.x === exp.x && obs.y === exp.y) {\n return `${msg}✓`;\n } else {\n throw Error(`✗ Assertion failed in ${msg}: expected (${exp.x},${exp.y}), while observed value was (${obs.x},${obs.y}).`);\n }\n}\n\nfunction ptsStr(pts) {\n return pts\n .map((p) => `(${p.x},${p.y})`)\n .sort()\n .join(\",\");\n}\n\nfunction rgnsStr(regions) {\n return regions\n .map((r) => r.id)\n .sort()\n .join(\" \");\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":415,"value":"#### Stack tests\n\n${[\n assert(new Stack([\"cat\", \"dog\", \"fish\"]).toArray().join(\",\"),\n \"cat,dog,fish\",\n \"Array constructor and toArray:\"\n ),\n\n (() => {\n const s = new Stack().push(\"cat\").push(\"dog\").push(\"fish\");\n s.pop();\n return assert(s.toArray().join(\",\"), \"cat,dog\", \"push and pop:\");\n })(),\n\n (() => {\n const s = new Stack([1066, 1999, 2025]);\n return assert(s.peek() + s.size(), 2028, \"peek and size:\");\n })(),\n\n assert(new Stack([true, false, false]).clear().isEmpty(), true, \"clear and isEmpty:\"),\n\n assert(new Stack([true, false, false]).size(), 3, \"size:\")\n].join(\"
\")}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3008,"value":"#### Queue tests\n\n${[\n assert(new Queue([\"cat\", \"dog\", \"fish\"]).toArray().join(\",\"),\n \"cat,dog,fish\",\n \"Array constructor and toArray:\"),\n\n (() => {\n const q = new Queue().enqueue(\"cat\").enqueue(\"dog\").enqueue(\"fish\");\n q.dequeue();\n return assert(q.toArray().join(\",\"),\"dog,fish\",\n \"enqueue and dequeue:\")})(),\n\n (() => {\n const q = new Queue([1066, 1999, 2025]);\n return assert(q.peek() + q.size(), 1069, \"peek and size:\")})(),\n\n assert(new Queue([true, false, false]).clear().isEmpty(),true, \"clear and isEmpty:\"),\n\n assert(new Queue([true, false, false]).size(), 3, \"size:\")\n].join(\"
\")}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3044,"value":"$49","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3083,"value":"$4a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3206,"value":"$4b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3139,"value":"$4c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3201,"value":"#### TreeNode tests\n\n${[\n assert(new TreeNode(\"cat\").value, \"cat\", \"Constructor and value:\"),\n assert(new TreeNode(3).isLeaf(), true, \"isLeaf:\"),\n assert(new TreeNode(\"cat\")\n .addChild(new TreeNode(\"dog\"))\n .addChild(new TreeNode(\"fox\"))\n .addChild(new TreeNode(\"lemur\"))\n .children.map((node) => node.value).join(\",\"), \"dog,fox,lemur\", \"addChild and children:\"),\n assert(new TreeNode(\"cat\")\n .addChild(new TreeNode(\"dog\"))\n .addChild(new TreeNode(\"fox\"))\n .addChild(new TreeNode(\"lemur\"))\n .childValues().join(\",\"), \"dog,fox,lemur\", \"childValues:\"),\n \n (() => {\n const cat = new TreeNode(\"cat\");\n const dog = new TreeNode(\"dog\");\n const fox = new TreeNode(\"fox\");\n const lemur = new TreeNode(\"lemur\");\n return assert(cat.addChild(dog).addChild(fox).addChild(lemur).removeChild(fox).removeChild(cat).childValues().join(\",\"),\n \"dog,lemur\",\n \"removeChild:\")})(),\n \n].join(\"
\")}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3203,"value":"$4d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3189,"value":"$4e","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3410,"value":"$4f","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3416,"value":"$50","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3376,"value":"$51","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3418,"value":"$52","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3393,"value":"$53","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3420,"value":"$54","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":3422,"value":"$55","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4920,"value":"$56","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4497,"value":"#### Rope tests","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4567,"value":"$57","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4557,"value":"new Rope(austen).toDot({maxLeafChars: 22, scale: 0.5})","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4486,"value":"$58","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4502,"value":"#### KdTree tests","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4328,"value":"const pts1 = [\n [10, 0],\n [0, 3],\n [9, -2],\n [9, 4],\n [8, 5],\n [0, 0],\n [2.5, 5.5]\n];","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4122,"value":"$59","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4424,"value":"#### Quadtree tests","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4413,"value":"pts2 = {\n const rand = d3.randomNormal(0, 4);\n return Array.from({ length: 50 }, (d) => [rand(), rand()]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4348,"value":"pqt = pts2.reduce(\n (qt, [x, y]) => qt.insert({ x, y }),\n new PointQuadtree({\n boundary: {\n x: 0,\n y: 0,\n halfWidth: 16,\n halfHeight: 16\n },\n capacity: 5\n })\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4709,"value":"

\n${pqt.toDot({\n rankDir: \"LR\",\n showItems: false,\n scale: 0.3,\n fillClr: (d) => (d.isDivided || d.size < 1 ? \"white\" : \"lightblue\")\n})}\n \n${(() => {\n const cells = [...pqt.cells()].map((d) => d.boundary);\n\n return Plot.plot({\n width: 360,\n aspectRatio: 1,\n x: { ticks: d3.range(-16, 16.1, 4) },\n y: { ticks: d3.range(-16, 16.1, 4) },\n marks: [\n Plot.rect(cells, {\n x1: (d) => d.x - d.halfWidth,\n y1: (d) => d.y - d.halfHeight,\n x2: (d) => d.x + d.halfWidth,\n y2: (d) => d.y + d.halfHeight,\n stroke: \"firebrick\",\n strokeWidth: 0.2\n }),\n Plot.dot(pts2, { fill: \"steelblue\", opacity: 0.8, r: 2 })\n ]\n });\n})()}\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4625,"value":"function rect(x, y, hw, hh) {\n return {x, y, halfWidth: hw, halfHeight: hh};\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4651,"value":"const regionBounds = (id, x, y, hw, hh) => ({id, bounds: rect(x, y, hw, hh)});","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4885,"value":"$5a","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4628,"value":"$5b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4654,"value":"$5c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4746,"value":"### Octree tests","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4807,"value":"const pts3 = (() => {\n const rand = d3.randomNormal(0, 4);\n return Array.from({length: 50}, (d) => [rand(), rand(), rand()]);\n})();","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4811,"value":"const pot = (() =>\n pts3.reduce(\n (ot, [x, y, z]) => ot.insert({x, y, z}),\n new PointOctree({boundary: box(0, 0, 0, 16, 16, 16), capacity: 8})\n ))();","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4826,"value":"pot.toDot({\n rankDir: \"LR\",\n showItems: false,\n scale: 0.5,\n fillClr: (d) => (d.isDivided || d.size < 1 ? \"white\" : \"lightblue\")\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4748,"value":"function box(x, y, z, halfWidth, halfHeight, halfDepth) {\n return {x, y, z, halfWidth, halfHeight, halfDepth};\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4753,"value":"function pts3Str(regions) {\n return regions\n .map((p) => `(${p.x},${p.y},${p.z})`)\n .sort()\n .join(\" \");\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4758,"value":"function rgns3Str(regions) {\n return regions\n .map((r) => r.id)\n .sort()\n .join(\" \");\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4764,"value":"$5d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4772,"value":"$5e","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":4921,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4922,"value":"_For page styling:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4923,"value":"import {defaultStyle} from \"observable:@jwolondon/utilities-cdt-2026\"","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4924,"value":"defaultStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W5f","stdlib":"2","titling":"auto"}} 2e:"$2d:body"