Homec4science
Diffusion Open Access Compliance Check Tool (OACCT) (paginated-inlines) Browse

rOACCT/node_modules/@bcoe/v8-coverage/src/lib/range-tree.ts
5d92ed19fb80paginated-inlines

Last Change
Raw File

range-tree.ts
View Options

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;
function endChain(): void {
if (tail.length !== 0) {
head!.end = tail[tail.length - 1].end;
for (const tailTree of tail) {
for (const subChild of tailTree.children) {
subChild.delta += tailTree.delta - head!.delta;
head!.children.push(subChild);
}
}
tail.length = 0;
}
head!.normalize();
children.push(head!);
}
}
/**
* @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;
}
}
c4science · Help