Select Git revision
leafy_tree.js
-
Brady James Garvin authoredBrady James Garvin authored
leafy_tree.js 13.71 KiB
import './utility.js';
// Besides the usual identity (identitySummary) and binary operator (combineSummaries) that every monoid has, here we also include a function (summarizeValue)
// to convert values in a leafy tree's leaves into summaries. That way, leafy trees can have one type for their elements and a different type for their
// summaries. (And when different types are not required, summarizeValue can just be set to the identity function.)
export class Monoid {
constructor(identitySummary, summarizeValue, combineSummaries) {
this.identitySummary = identitySummary;
this.summarizeValue = summarizeValue;
this.combineSummaries = combineSummaries;
}
}
// Likewise, we not only give an ordered monoid a way to compare its summaries (compareSummaries), we also include a function (summarizePosition) to convert
// from a position type to the summary type. That way, leafy trees can have one type for positions and a different type for summaries. (Yet again, if
// different types are not required, then summarizePosition can just be set to the identity function.)
//
// Note that, by convention, compareSummaries should be defined so that compareSummaries(x, y) is true iff x ≼ y.
export class OrderedMonoid extends Monoid {
constructor(identitySummary, summarizeValue, combineSummaries, summarizePosition, compareSummaries) {
super(identitySummary, summarizeValue, combineSummaries);
this.summarizePosition = summarizePosition;
this.compareSummaries = compareSummaries;
}
}
// An AnnotatedMonoid is a product monoid that is ordered only by its left coordinate. (So its positions are exactly the positions of the left monoid.) An
// AnnotatedMonoid is normally used to annotate the summaries in an ordered monoid with additional summary information from an unordered monoid on the right.
export class AnnotatedMonoid extends OrderedMonoid {
constructor(orderedMonoid, unorderedMonoid) {
super(
[orderedMonoid.identitySummary, unorderedMonoid.identitySummary],
(value) => [orderedMonoid.summarizeValue(value), unorderedMonoid.summarizeValue(value)],
([left, leftAnnotation], [right, rightAnnotation]) =>
[orderedMonoid.combineSummaries(left, right), unorderedMonoid.combineSummaries(leftAnnotation, rightAnnotation)],
(position) => [orderedMonoid.summarizePosition(position), undefined],
([left, leftAnnotation], [right, rightAnnotation]) => orderedMonoid.compareSummaries(left, right) // eslint-disable-line no-unused-vars
);
}
}
// A KeyValueMonoid is a Monoid for leafy trees that store key/value pairs sorted by key. (Hence, the keys must belong to an ordered monoid, and the values
// usually belong to a different, not necessarily ordered monoid.) When specifying positions in a leafy tree using a KeyValueMonoid, it is only necessary to
// give a position for the key monoid.
export class KeyValueMonoid extends AnnotatedMonoid {
constructor(keyMonoid, valueMonoid) {
super(
new OrderedMonoid(
keyMonoid.identitySummary,
([key, value]) => keyMonoid.summarizeValue(key), // eslint-disable-line no-unused-vars
keyMonoid.combineSummaries,
keyMonoid.summarizePosition,
keyMonoid.compareSummaries
),
new Monoid(
valueMonoid.identitySummary,
([key, value]) => valueMonoid.summarizeValue(value), // eslint-disable-line no-unused-vars
valueMonoid.combineSummaries
)
);
}
}
// COUNT_MONOID is a monoid meant to be used as the ordered part of an annotated monoid for leafy trees that act like lists. It's positions can be used to
// index the tree's leaves, with indices counting from zero from left to right.
export const COUNT_MONOID = new OrderedMonoid(
0,
(value) => 1, // eslint-disable-line no-unused-vars
(left, right) => left + right,
(index) => index + 1,
(left, right) => left <= right
);
// RANGE_MONOID is a monoid meant to be used as the ordered part of an annotated monoid for leafy trees that act like ordered sets or as the key part of a
// key/value monoid for leafy trees that act like ordered dictionaries. It's positions can be used to index the set or dictionary much like a dictionary key.
export const RANGE_MONOID = new OrderedMonoid(
[Infinity, -Infinity],
(value) => [value, value], // eslint-disable-line no-unused-vars
([leftMinimum, leftMaximum], [rightMinimum, rightMaximum]) => [Math.min(leftMinimum, rightMinimum), Math.max(leftMaximum, rightMaximum)],
(position) => [position, position],
([leftMinimum, leftMaximum], [rightMinimum, rightMaximum]) => leftMaximum <= rightMaximum // eslint-disable-line no-unused-vars
);
class LeafyTreeNode {
constructor(tree, parent) {
this.tree = tree;
this.parent = parent;
}
summarize(summaryOfBeginPosition, summaryOfEndPosition, summaryOfLeftSide) {
const orderedMonoid = this.tree.orderedMonoid;
const minimum = orderedMonoid.combineSummaries(summaryOfLeftSide, this.summaryOfLeftmostLeaf);
const maximum = orderedMonoid.combineSummaries(summaryOfLeftSide, this.summary);
// containment case:
if (orderedMonoid.compareSummaries(summaryOfBeginPosition, minimum) &&
!orderedMonoid.compareSummaries(summaryOfEndPosition, maximum)) {
return this.summary;
}
// disjointness case:
if (!orderedMonoid.compareSummaries(summaryOfBeginPosition, maximum) ||
orderedMonoid.compareSummaries(summaryOfEndPosition, minimum)) {
return orderedMonoid.identitySummary;
}
// partial overlap case:
console.assert(this.children !== undefined, 'Tried to summarize part of a leaf in a leafy tree.');
let result = orderedMonoid.identitySummary;
let accumulator = summaryOfLeftSide;
for (const child of this.children) {
result = orderedMonoid.combineSummaries(result, child.summarize(summaryOfBeginPosition, summaryOfEndPosition, accumulator));
accumulator = orderedMonoid.combineSummaries(accumulator, child.summary);
}
return result;
}
}
class Branch extends LeafyTreeNode {
constructor(tree, parent, children) {
super(tree, parent);
console.assert(children.every((child) => child.height === 0), 'Tried to create a new branch above height one in a leafy tree.');
if (parent !== undefined) {
for (let index = parent.children.length; index--;) {
if (children.includes(parent.children[index])) {
parent.children[index] = this;
}
}
console.assert(
parent.children.filter((child) => child === this).length === 1,
'Tried to create a leafy tree branch that does not replace exactly one node.'
);
} else {
console.assert(
children.includes(this.tree._root), // eslint-disable-line no-underscore-dangle, (read by friend)
'Tried to add a second root to a leafy tree.'
);
this.tree._root = this; // eslint-disable-line no-underscore-dangle, (write by friend)
}
this.children = children;
for (const child of children) {
child.parent = this;
}
this._updateSummaries();
}
_updateSummaries() {
console.assert(this.children.length > 0, 'Found a branch-type vertex in a leafy tree with no children.');
if (this.children.length === 1) {
if (this.parent !== undefined) {
const ownIndex = this.parent.children.indexOf(this);
console.assert(ownIndex >= 0, 'Found a branch in a leafy tree that is not a child of its parent.');
this.parent.children[ownIndex] = this.children[0];
this.children[0].parent = this.parent;
} else {
this.tree._root = this.children[0]; // eslint-disable-line no-underscore-dangle, (write by friend)
this.children[0].parent = undefined;
}
} else {
this.height = 1 + Math.max(...this.children.map((child) => child.height));
this.summaryOfLeftmostLeaf = this.children[0].summaryOfLeftmostLeaf;
this.summary = this.children.reduce((left, right) => this.tree.orderedMonoid.combineSummaries(left.summary, right.summary));
}
if (this.parent !== undefined) {
this.parent._updateSummaries(); // eslint-disable-line no-underscore-dangle, (call from friend)
}
}
findLeafAndSummaryOfLeftSide(positionSummary, summaryOfLeftSide) {
const orderedMonoid = this.tree.orderedMonoid;
let accumulator = summaryOfLeftSide;
for (const child of this.children.slice(0, -1)) {
const candidate = orderedMonoid.combineSummaries(accumulator, child.summary);
if (orderedMonoid.compareSummaries(positionSummary, candidate)) {
return child.findLeafAndSummaryOfLeftSide(positionSummary, accumulator);
}
accumulator = candidate;
}
return this.children.top().findLeafAndSummaryOfLeftSide(positionSummary, accumulator);
}
dump(indentation) {
const newIndentation = indentation + 2;
const children = this.children.map((child) => `${child.dump(newIndentation)}\n`).join('');
return `${' '.repeat(indentation)}Branch (height=${this.height}) ` +
`{\n${' '.repeat(newIndentation)}summary: ${this.summary}\n${children}${' '.repeat(indentation)}}`;
}
}
class Leaf extends LeafyTreeNode {
constructor(tree, value) {
super(tree, undefined);
this.value = value;
this.summary = tree.orderedMonoid.summarizeValue(value);
}
get _successor() {
let [child, current] = [this, this.parent];
while (current !== undefined) {
const childIndex = current.children.indexOf(child);
if (childIndex + 1 < current.children.length) {
for (current = current.children[childIndex + 1]; // eslint-disable-line curly
current.children !== undefined;
current = current.children[0]);
return current;
}
[child, current] = [current, current.parent];
}
return undefined;
}
get height() { // eslint-disable-line class-methods-use-this
return 0;
}
get summaryOfLeftmostLeaf() {
return this.summary;
}
findLeafAndSummaryOfLeftSide(positionSummary, summaryOfLeftSide) {
return [this, summaryOfLeftSide];
}
add(positionSummary, value, summaryOfLeftSide) {
const orderedMonoid = this.tree.orderedMonoid;
const sibling = new Leaf(this.tree, value);
// For now, only use binary branching:
if (orderedMonoid.compareSummaries(positionSummary, orderedMonoid.combineSummaries(summaryOfLeftSide, this.summary))) {
new Branch(this.tree, this.parent, [sibling, this]); // eslint-disable-line no-new
} else {
new Branch(this.tree, this.parent, [this, sibling]); // eslint-disable-line no-new
}
return sibling;
}
_matchesPosition(positionSummary, summaryOfLeftSide) {
const orderedMonoid = this.tree.orderedMonoid;
const summaryOfLeftSideAndSelf = orderedMonoid.combineSummaries(summaryOfLeftSide, this.summary);
return orderedMonoid.compareSummaries(positionSummary, summaryOfLeftSideAndSelf) &&
orderedMonoid.compareSummaries(summaryOfLeftSideAndSelf, positionSummary);
}
_delete() {
if (this.parent !== undefined) {
this.parent.children.delete(this);
this.parent._updateSummaries(); // eslint-disable-line no-underscore-dangle, (call from friend)
} else {
this.tree._root = undefined; // eslint-disable-line no-underscore-dangle, (write by friend)
}
}
delete(positionSummary, summaryOfLeftSide) {
if (this._matchesPosition(positionSummary, summaryOfLeftSide)) {
this._delete();
return true;
}
return false;
}
deleteMatch(positionSummary, criterion, summaryOfLeftSide) {
if (this._matchesPosition(positionSummary, summaryOfLeftSide)) {
const orderedMonoid = this.tree.orderedMonoid;
if (criterion(this.value)) {
this._delete();
return true;
}
const successor = this._successor;
if (successor !== undefined) {
return successor.deleteMatch(positionSummary, criterion, orderedMonoid.combineSummaries(summaryOfLeftSide, this.summary));
}
}
return false;
}
dump(indentation) {
return `${' '.repeat(indentation)}Leaf { value: ${this.value}, summary: ${this.summary} }`;
}
}
export class LeafyTree {
constructor(orderedMonoid) {
this.orderedMonoid = orderedMonoid;
this._root = undefined;
}
summarize(begin, end) {
if (this._root !== undefined) {
return this._root.summarize(this.orderedMonoid.summarizePosition(begin), this.orderedMonoid.summarizePosition(end), this.orderedMonoid.identitySummary);
}
return this.orderedMonoid.identitySummary;
}
add(position, value) {
if (this._root !== undefined) {
const positionSummary = this.orderedMonoid.summarizePosition(position);
const [leaf, accumulation] = this._root.findLeafAndSummaryOfLeftSide(positionSummary, this.orderedMonoid.identitySummary);
return leaf.add(positionSummary, value, accumulation);
}
this._root = new Leaf(this, value);
return this._root;
}
// syntactic sugar for dictionary-like leafy trees where we want to store key/value pairs, not just values
set(position, value) {
this.add(position, [position, value]);
}
delete(position) {
if (this._root !== undefined) {
const positionSummary = this.orderedMonoid.summarizePosition(position);
const [leaf, accumulation] = this._root.findLeafAndSummaryOfLeftSide(positionSummary, this.orderedMonoid.identitySummary);
return leaf.delete(positionSummary, accumulation);
}
return false;
}
deleteMatch(position, criterion) {
if (this._root !== undefined) {
const positionSummary = this.orderedMonoid.summarizePosition(position);
const [leaf, accumulation] = this._root.findLeafAndSummaryOfLeftSide(positionSummary, this.orderedMonoid.identitySummary);
return leaf.deleteMatch(positionSummary, criterion, accumulation);
}
return false;
}
toString() {
if (this._root !== undefined) {
return `LeafyTree {\n${this._root.dump(2)}\n}`;
}
return 'LeafyTree {}';
}
}