Last active
January 26, 2022 13:33
-
-
Save hackwaly/f0d090e514912acdc3bdcfcfcdc958fa to your computer and use it in GitHub Desktop.
Generic persistent treap
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import { assert } from "./Errors"; | |
| export type treap<a, b> = node<a, b> | undefined; | |
| export type node<a, b> = { | |
| left: treap<a, b>; | |
| right: treap<a, b>; | |
| priority: number; | |
| data: a; | |
| subtreeData: b; | |
| }; | |
| export interface Build<a, b> { | |
| subtreeData(data: a, left: b | undefined, right: b | undefined): b; | |
| mergeData?(left: a, right: a): a | undefined; | |
| } | |
| export interface Slice<a, b> { | |
| dataLength(data: a): number; | |
| subtreeDataLength(subtreeData: b): number; | |
| sliceData(data: a, startOffset: number, endOffset: number): a; | |
| } | |
| function fix<a, b>(M: Build<a, b>, node: node<a, b>) { | |
| node.subtreeData = M.subtreeData(node.data, node.left?.subtreeData, node.right?.subtreeData); | |
| return node; | |
| } | |
| export function singleton<a, b>(M: Build<a, b>, data: a): node<a, b> { | |
| const subtreeData = M.subtreeData(data, undefined, undefined); | |
| return { left: undefined, right: undefined, priority: Math.random(), data, subtreeData }; | |
| } | |
| export function length<a, b>(M: Slice<a, b>, node: treap<a, b>) { | |
| return node === undefined ? 0 : M.dataLength(node.data); | |
| } | |
| export function split<a, b>( | |
| M: Build<a, b> & Slice<a, b>, | |
| node: treap<a, b>, | |
| offset: number, | |
| returning: "left" | "right" | |
| ): treap<a, b> { | |
| if (offset === 0) return returning === "left" ? undefined : node; | |
| assert(node !== undefined); | |
| const llen = length(M, node.left); | |
| if (offset <= llen) return split(M, node.left, offset, returning); | |
| offset -= llen; | |
| const len = M.dataLength(node.data); | |
| if (offset >= len) return split(M, node.right, offset - len, returning); | |
| return returning === "left" | |
| ? fix(M, { ...node, data: M.sliceData(node.data, 0, offset), right: undefined }) | |
| : fix(M, { ...node, data: M.sliceData(node.data, offset, len), left: undefined }); | |
| } | |
| export function slice<a, b>(M: Build<a, b> & Slice<a, b>, node: treap<a, b>, startOffset: number, endOffset: number) { | |
| let leftMiddle = split(M, node, endOffset, "left"); | |
| return split(M, leftMiddle, startOffset, "right"); | |
| } | |
| export function first<a, b>(node: node<a, b>): a; | |
| export function first<a, b>(node: treap<a, b>): a | undefined { | |
| if (node === undefined) return undefined; | |
| if (node.left === undefined) return node.data; | |
| return first(node.left); | |
| } | |
| export function last<a, b>(node: node<a, b>): a; | |
| export function last<a, b>(node: treap<a, b>): a | undefined { | |
| if (node === undefined) return undefined; | |
| if (node.right === undefined) return node.data; | |
| return last(node.right); | |
| } | |
| export function withoutFirst<a, b>(M: Build<a, b>, node: treap<a, b>): treap<a, b> { | |
| if (node === undefined) return undefined; | |
| if (node.left === undefined) return node.right; | |
| return fix(M, { ...node, left: withoutFirst(M, node.left) }); | |
| } | |
| export function withoutLast<a, b>(M: Build<a, b>, node: treap<a, b>): treap<a, b> { | |
| if (node === undefined) return undefined; | |
| if (node.right === undefined) return node.left; | |
| return fix(M, { ...node, right: withoutLast(M, node.right) }); | |
| } | |
| function merge<a, b>(M: Build<a, b>, left: treap<a, b>, right: treap<a, b>): treap<a, b> { | |
| if (left === undefined) return right; | |
| if (right === undefined) return left; | |
| return left.priority < right.priority | |
| ? fix(M, { ...left, right: merge(M, left.right, right) }) | |
| : fix(M, { ...right, left: merge(M, right.left, left) }); | |
| } | |
| export function concat<a, b>(M: Build<a, b>, left: treap<a, b>, right: treap<a, b>) { | |
| if (left === undefined) return right; | |
| if (right === undefined) return left; | |
| let llastData = last(left); | |
| let merged = false; | |
| while (true) { | |
| let rfirstData = first(right); | |
| let data = M.mergeData?.(llastData, rfirstData); | |
| if (data === undefined) break; | |
| llastData = data; | |
| right = withoutFirst(M, right); | |
| merged = true; | |
| if (right === undefined) break; | |
| } | |
| if (merged) { | |
| left = merge(M, withoutLast(M, left), singleton(M, llastData)); | |
| } | |
| return merge(M, left, right); | |
| } | |
| export function from<a, b>(M: Build<a, b>, dataSource: Iterable<a>) { | |
| let p = 0; | |
| const root = { priority: -Infinity, right: undefined } as unknown as node<a, b>; | |
| const stack = [root]; | |
| for (const data of dataSource) { | |
| const node = singleton(M, data); | |
| let last!: node<a, b>; | |
| while (stack[p].priority > node.priority) { | |
| last = stack[p]; | |
| fix(M, last); | |
| p -= 1; | |
| } | |
| stack[p].right = node; | |
| node.left = last; | |
| p += 1; | |
| stack[p] = node; | |
| } | |
| while (p > 0) { | |
| fix(M, stack[p]); | |
| p -= 1; | |
| } | |
| return root.right; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment