Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 {}
Add Comment
Please, Sign In to add comment