Gecko [ c.stage.kornherr.net ]

Name	Size	Permission	Date
ascii.ts	4.41 KB	-rw-r--r--	2023-12-13 10:07
clone.ts	1.67 KB	-rw-r--r--	2023-12-13 10:07
compare.ts	1.06 KB	-rw-r--r--	2023-12-13 10:07
index.ts	462 B	-rw-r--r--	2023-12-13 10:07
merge.ts	10.62 KB	-rw-r--r--	2023-12-13 10:07
normalize.ts	2.32 KB	-rw-r--r--	2023-12-13 10:07
range-tree.ts	4.17 KB	-rw-r--r--	2023-12-13 10:07
types.ts	428 B	-rw-r--r--	2023-12-13 10:07

Rename

import { RangeCov } from "./types";

export class RangeTree {
  start: number;
  end: number;
  delta: number;
  children: RangeTree[];

constructor(
    start: number,
    end: number,
    delta: number,
    children: RangeTree[],
  ) {
    this.start = start;
    this.end = end;
    this.delta = delta;
    this.children = children;
  }

/**
   * @precodition `ranges` are well-formed and pre-order sorted
   */
  static fromSortedRanges(ranges: ReadonlyArray<RangeCov>): RangeTree | undefined {
    let root: RangeTree | undefined;
    // Stack of parent trees and parent counts.
    const stack: [RangeTree, number][] = [];
    for (const range of ranges) {
      const node: RangeTree = new RangeTree(range.startOffset, range.endOffset, range.count, []);
      if (root === undefined) {
        root = node;
        stack.push([node, range.count]);
        continue;
      }
      let parent: RangeTree;
      let parentCount: number;
      while (true) {
        [parent, parentCount] = stack[stack.length - 1];
        // assert: `top !== undefined` (the ranges are sorted)
        if (range.startOffset < parent.end) {
          break;
        } else {
          stack.pop();
        }
      }
      node.delta -= parentCount;
      parent.children.push(node);
      stack.push([node, range.count]);
    }
    return root;
  }

normalize(): void {
    const children: RangeTree[] = [];
    let curEnd: number;
    let head: RangeTree | undefined;
    const tail: RangeTree[] = [];
    for (const child of this.children) {
      if (head === undefined) {
        head = child;
      } else if (child.delta === head.delta && child.start === curEnd!) {
        tail.push(child);
      } else {
        endChain();
        head = child;
      }
      curEnd = child.end;
    }
    if (head !== undefined) {
      endChain();
    }

if (children.length === 1) {
      const child: RangeTree = children[0];
      if (child.start === this.start && child.end === this.end) {
        this.delta += child.delta;
        this.children = child.children;
        // `.lazyCount` is zero for both (both are after normalization)
        return;
      }
    }

this.children = children;

/**
   * @precondition `tree.start < value && value < tree.end`
   * @return RangeTree Right part
   */
  split(value: number): RangeTree {
    let leftChildLen: number = this.children.length;
    let mid: RangeTree | undefined;

// TODO(perf): Binary search (check overhead)
    for (let i: number = 0; i < this.children.length; i++) {
      const child: RangeTree = this.children[i];
      if (child.start < value && value < child.end) {
        mid = child.split(value);
        leftChildLen = i + 1;
        break;
      } else if (child.start >= value) {
        leftChildLen = i;
        break;
      }
    }

const rightLen: number = this.children.length - leftChildLen;
    const rightChildren: RangeTree[] = this.children.splice(leftChildLen, rightLen);
    if (mid !== undefined) {
      rightChildren.unshift(mid);
    }
    const result: RangeTree = new RangeTree(
      value,
      this.end,
      this.delta,
      rightChildren,
    );
    this.end = value;
    return result;
  }

/**
   * Get the range coverages corresponding to the tree.
   *
   * The ranges are pre-order sorted.
   */
  toRanges(): RangeCov[] {
    const ranges: RangeCov[] = [];
    // Stack of parent trees and counts.
    const stack: [RangeTree, number][] = [[this, 0]];
    while (stack.length > 0) {
      const [cur, parentCount]: [RangeTree, number] = stack.pop()!;
      const count: number = parentCount + cur.delta;
      ranges.push({startOffset: cur.start, endOffset: cur.end, count});
      for (let i: number = cur.children.length - 1; i >= 0; i--) {
        stack.push([cur.children[i], count]);
      }
    }
    return ranges;
  }
}