1  import { RangeCov } from "./types";
  2  
  3  export class RangeTree {
  4    start: number;
  5    end: number;
  6    delta: number;
  7    children: RangeTree[];
  8  
  9    constructor(
 10      start: number,
 11      end: number,
 12      delta: number,
 13      children: RangeTree[],
 14    ) {
 15      this.start = start;
 16      this.end = end;
 17      this.delta = delta;
 18      this.children = children;
 19    }
 20  
 21    /**
 22     * @precodition `ranges` are well-formed and pre-order sorted
 23     */
 24    static fromSortedRanges(ranges: ReadonlyArray<RangeCov>): RangeTree | undefined {
 25      let root: RangeTree | undefined;
 26      // Stack of parent trees and parent counts.
 27      const stack: [RangeTree, number][] = [];
 28      for (const range of ranges) {
 29        const node: RangeTree = new RangeTree(range.startOffset, range.endOffset, range.count, []);
 30        if (root === undefined) {
 31          root = node;
 32          stack.push([node, range.count]);
 33          continue;
 34        }
 35        let parent: RangeTree;
 36        let parentCount: number;
 37        while (true) {
 38          [parent, parentCount] = stack[stack.length - 1];
 39          // assert: `top !== undefined` (the ranges are sorted)
 40          if (range.startOffset < parent.end) {
 41            break;
 42          } else {
 43            stack.pop();
 44          }
 45        }
 46        node.delta -= parentCount;
 47        parent.children.push(node);
 48        stack.push([node, range.count]);
 49      }
 50      return root;
 51    }
 52  
 53    normalize(): void {
 54      const children: RangeTree[] = [];
 55      let curEnd: number;
 56      let head: RangeTree | undefined;
 57      const tail: RangeTree[] = [];
 58      for (const child of this.children) {
 59        if (head === undefined) {
 60          head = child;
 61        } else if (child.delta === head.delta && child.start === curEnd!) {
 62          tail.push(child);
 63        } else {
 64          endChain();
 65          head = child;
 66        }
 67        curEnd = child.end;
 68      }
 69      if (head !== undefined) {
 70        endChain();
 71      }
 72  
 73      if (children.length === 1) {
 74        const child: RangeTree = children[0];
 75        if (child.start === this.start && child.end === this.end) {
 76          this.delta += child.delta;
 77          this.children = child.children;
 78          // `.lazyCount` is zero for both (both are after normalization)
 79          return;
 80        }
 81      }
 82  
 83      this.children = children;
 84  
 85      function endChain(): void {
 86        if (tail.length !== 0) {
 87          head!.end = tail[tail.length - 1].end;
 88          for (const tailTree of tail) {
 89            for (const subChild of tailTree.children) {
 90              subChild.delta += tailTree.delta - head!.delta;
 91              head!.children.push(subChild);
 92            }
 93          }
 94          tail.length = 0;
 95        }
 96        head!.normalize();
 97        children.push(head!);
 98      }
 99    }
100  
101    /**
102     * @precondition `tree.start < value && value < tree.end`
103     * @return RangeTree Right part
104     */
105    split(value: number): RangeTree {
106      let leftChildLen: number = this.children.length;
107      let mid: RangeTree | undefined;
108  
109      // TODO(perf): Binary search (check overhead)
110      for (let i: number = 0; i < this.children.length; i++) {
111        const child: RangeTree = this.children[i];
112        if (child.start < value && value < child.end) {
113          mid = child.split(value);
114          leftChildLen = i + 1;
115          break;
116        } else if (child.start >= value) {
117          leftChildLen = i;
118          break;
119        }
120      }
121  
122      const rightLen: number = this.children.length - leftChildLen;
123      const rightChildren: RangeTree[] = this.children.splice(leftChildLen, rightLen);
124      if (mid !== undefined) {
125        rightChildren.unshift(mid);
126      }
127      const result: RangeTree = new RangeTree(
128        value,
129        this.end,
130        this.delta,
131        rightChildren,
132      );
133      this.end = value;
134      return result;
135    }
136  
137    /**
138     * Get the range coverages corresponding to the tree.
139     *
140     * The ranges are pre-order sorted.
141     */
142    toRanges(): RangeCov[] {
143      const ranges: RangeCov[] = [];
144      // Stack of parent trees and counts.
145      const stack: [RangeTree, number][] = [[this, 0]];
146      while (stack.length > 0) {
147        const [cur, parentCount]: [RangeTree, number] = stack.pop()!;
148        const count: number = parentCount + cur.delta;
149        ranges.push({startOffset: cur.start, endOffset: cur.end, count});
150        for (let i: number = cur.children.length - 1; i >= 0; i--) {
151          stack.push([cur.children[i], count]);
152        }
153      }
154      return ranges;
155    }
156  }