Skip to content
Snippets Groups Projects
Select Git revision
  • 0bf739058957acfde46df23c0ea35e05eaa1ac8d
  • master default protected
2 results

leafy_tree.js

Blame
  • 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 {}';
      }
    }