NodeTree.ts

class NodeTree {
    insert(node: Node): void {
        if (this.has(node)) {
            throw new UnexpectedStructure() // TODO
        }

        const getParent = (): Node | undefined => {
            const filter: TravelFilter = candidate => candidate.contains(node) ? Travel.ACCEPT : Travel.REJECT
            const ancestorPaths = this.DFS(document.body, filter)

            let parentPath: Array<Node> = []
            for (const path of ancestorPaths) {
                if (path.length < parentPath.length) {
                    break
                }
                parentPath = path
            }

            return parentPath[parentPath.length - 1]
        }

        const parent = getParent()
        const children = new Set<Node>()
        if (existing(parent)) {
            this.parentMap.set(node, parent)
            const adjacents = this.childrenMap.get(node)!
            new Set(adjacents).forEach(adjacent => {
                if (node.contains(adjacent)) {
                    children.add(adjacent)
                    adjacents.delete(adjacent)
                }
            })
        }

        this.childrenMap.set(node, children)
    }

    ancestors(node: Node): Path {
        const result = []
        for (let parent = this.parentMap.get(node);
             existing(parent);
             parent = this.parentMap.get(parent)) {
            result.unshift(parent)
        }
        return result
    }

    * DFS(node: Node, filter: TravelFilter = () => Travel.ACCEPT): IterableIterator<Path> {
        yield [node]
        const children = this.childrenMap.get(node)
        if (existing(children)) {
            for (const child of children) {
                if (filter(child) === Travel.REJECT) {
                    continue
                }
                for (const subpath of this.DFS(child)) {
                    const path = [child, ...subpath]
                    if (filter(child) === Travel.ACCEPT) {
                        yield path
                    }
                }
            }
        }
    }

    children(node: Node): Set<Node> {
        let result = this.childrenMap.get(node)
        if (notExisting(result)) {
            result = new Set<Node>()
            this.childrenMap.set(node, result)
        }
        return result
    }

    has(node: Node): boolean {
        return existing(this.childrenMap.get(node))
    }

    clear(): void {
        this.parentMap = new Map()
        this.childrenMap = new Map([[document.body, new Set()]])
    }

    private parentMap: Map<Node, Node> = new Map()
    private childrenMap: Map<Node, Set<Node>> = new Map([[document.body, new Set()]])
}

enum Travel {
    ACCEPT,
    SKIP,
    REJECT
}

type TravelFilter = (path: Readonly<Node>) => Travel
type Path = Array<Node>

class UnexpectedStructure extends Error {}