Skip to content

Instantly share code, notes, and snippets.

@tim-evans

tim-evans/tree.ts

Created May 11, 2019 03:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tim-evans/6f404cba893f52c0f50c3819c6d2d5c2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tim-evans/6f404cba893f52c0f50c3819c6d2d5c2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tim-evans created this gist May 11, 2019.
    129 changes: 129 additions & 0 deletions tree.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,129 @@
    class Tree {
    label: string;
    rank: number;
    start: number;
    end: number;
    private children: Tree[];

    constructor(params: {
    label: string,
    start: number,
    end: number,
    rank: number
    }) {
    this.children = [];
    this.label = params.label;
    this.start = params.start;
    this.end = params.end;
    this.rank = params.rank;
    }

    // Currently assumes that nodes are sorted by rank
    insert(node: Tree) {
    for (let i = 0, len = this.children.length; i < len; i++) {
    let child = this.children[i];
    if (node.start < child.start) {
    // Splice in the full node and return if it's wholly
    // before this child
    if (node.end <= child.start) {
    this.children.splice(i, 0, node);
    i++;
    return;
    }
    // Otherwise, we have a left branch to take care of
    let [leftBranch, rest] = node.split(child.start);

    // Insert the branch
    this.children.splice(i, 0, leftBranch);
    i++;

    // Continue with partial node (to the next statement,
    // since this may extend past this node)
    if (rest == null) break;
    node = rest;
    }

    if (node.start >= child.start && node.start < child.end) {
    if (node.end <= child.end) {
    child.insert(node);
    return;
    }
    let [rightBranch, rest] = node.split(child.end);
    // Insert the branch
    child.insert(rightBranch);

    if (rest == null) break;
    // Continue with partial node
    node = rest;
    }
    }

    this.children.push(node);
    }

    split(at: number): [Tree, Tree] {
    if (this.rank === Infinity) {
    return [
    new Tree({
    label: this.label.slice(0, at - this.start),
    start: this.start,
    end: at,
    rank: this.rank
    }),
    new Tree({
    label: this.label.slice(at - this.start),
    start: at,
    end: this.end,
    rank: this.rank
    })
    ];
    }
    return [
    new Tree({
    label: this.label,
    start: this.start,
    end: at,
    rank: this.rank
    }),
    new Tree({
    label: this.label,
    start: at,
    end: this.end,
    rank: this.rank
    })
    ];
    }

    toJSON(): any {
    return {
    label: this.label,
    start: this.start,
    end: this.end,
    children: this.children.map(child => child.toJSON())
    };
    }

    trace(indent=0): any {
    // @ts-ignore
    let spacing = ' '.repeat(indent);
    if (this.rank === Infinity) {
    return `${spacing}${JSON.stringify(this.label)}`;
    }
    let children = this.children.map(child => child.trace(indent + 1));
    if (children.length === 0) {
    return `${spacing}${this.label}[${this.start}, ${this.end}]()`;
    } else {
    return `${spacing}${this.label}[${this.start}, ${this.end}](\n${children.join('\n')}\n${spacing})`;
    }
    }
    }

    let tree = new Tree({ label: 'document', start: 0, end: 10, rank: 0 });
    tree.insert(new Tree({ label: 'ol', start: 4, end: 8, rank: 10 }));
    tree.insert(new Tree({ label: 'li', start: 4, end: 8, rank: 10 }));
    tree.insert(new Tree({ label: 'paragraph', start: 0, end: 4, rank: 15 }));
    tree.insert(new Tree({ label: 'paragraph', start: 8, end: 10, rank: 15 }));
    tree.insert(new Tree({ label: 'paragraph', start: 4, end: 8, rank: 15 }));
    tree.insert(new Tree({ label: 'ab\n\nli\n\ncd', start: 0, end: 10, rank: Infinity }));

    console.log(tree.trace())