BestTree.js -- humble B+Tree with configurable aggregations and search through arbitrary "secondary indexes"

BestTree.js

// Code formatted (ruthlessly and) automatically with Prettier

// number of $values being used
const NODE_LIMIT = Symbol("BEST_NODE_LIMIT");
// cumulative count of leaf $values (redundant with limit and/or last bound...)
const NODE_SIZE = Symbol("BEST_NODE_SIZE");
// "integral" of "size" for each stem node
const NODE_BOUND = Symbol("BEST_NODE_BOUND");
// left-most of leaf $values for each stem node
const NODE_EDGE = Symbol("BEST_NODE_EDGE");
// cached merged calculation for a given (partial) aggregation
const NODE_CALC = Symbol("BEST_NODE_CALC");
// cached merged model for a given search
const NODE_REP = Symbol("BEST_NODE_REP");

class BestTree {
  static defaultCmp(left, right) {
    return 0 | (right < left) || -1 * (left !== right);
  }

  static preprocessData(root, options = {}) {
    const {
      comparator = BestTree.defaultCmp,
      use = null,
      search = null,
      aggregate = null
    } =
      options || {};

    return root;
  }

  constructor(json = "", data = null, options = {}) {
    const {
      comparator = BestTree.defaultCmp,
      use = null,
      search = null &&
        new Map().set("interval", {
          init: (use, weigh, ctx) => null,
          reduce: (merge, datum, use, weigh, ctx) => {
            if (merge && 0 > weigh(merge[0], datum.end)) {
              merge[0] = datum.end;
            }
            return merge || [datum.end, datum.start];
          },
          fuse: (merge, stem, use, weigh, ctx) => {
            if (merge && 0 > weigh(merge[0], stem[0])) {
              merge[0] = stem[0];
            }
            return merge || stem.slice();
          },
          attempt: (model, params, use, weigh, ctx) => true || false,
          test: (value, params, use, weigh, ctx) => true || false
        }),
      aggregate = null &&
        new Map().set("total", {
          init: (use, weigh, ctx) => 0,
          reduce: (merge, datum, use, weigh, ctx) =>
            merge + datum.effects.length,
          fuse: (merge, stem, use, weigh, ctx) => merge + stem
        })
    } =
      options || {};

    this._cmp = comparator === null ? null : comparator || BestTree.defaultCmp;
    this._toKey = use || null;
    this._root = json
      ? BestTree.preprocessData(JSON.parse(json), options)
      : data || null;
    this._search = search || null;
    this._aggregate = aggregate || null;
    this._cached = -1;
    this._path = [];
    this._from = this._root || null;
  }

  _parental(node) {
    return 0 > node.$factor;
  }

  _clamp(offset, size) {
    const at = (0 | offset) < 0 ? 1 + (0 | size) + (0 | offset) : 0 | offset;
    return size < 0 ? 0 : at < 0 ? 0 : at < (0 | size) ? at : 0 | size;
  }

  net(key, datum, use = this._toKey, cmp = this._cmp) {
    return (cmp || BestTree.defaultCmp)(key, use ? use(datum) : datum);
  }

  _indexOf(
    key,
    index = -1,
    data = this._data,
    use = this._toKey,
    cmp = this._cmp
  ) {
    var high = 0 | this._clamp(0 | index, data.length);
    var low = 0;
    var mid = (low + high + 1) >> 1;
    var bias = 0;

    while (low < mid && mid < high) {
      bias = this.net(key, data[mid], use || null, cmp || null);
      if (bias > 0) {
        low = mid;
        mid = (low + high + 1) >> 1;
      } else {
        high = mid;
        mid = (low + high) >> 1;
      }
    }

    return mid < data.length &&
      0 < this.net(key, data[mid], use || null, cmp || null)
      ? mid + 1
      : mid;
  }

  _next(root = this._root || null) {
    let node = root || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    let at = (0 | this._cached) < 0 ? 0 : (0 | this._cached) + 1;
    const cached = at;
    let depth = 0;
    let child = node || null;

    if (!node || at >= size) {
      this._cached = -1;
      this._from = null;
      return -1;
    } else if (at === 0) {
      while (this._parental(node)) {
        this._path[depth++] = 0;
        node = node.$values[0];
      }

      this._path[depth++] = 0;
      this._cached = 0;
      this._from = root;
      return 0;
    } else {
      while (this._parental(node)) {
        child = node.$values[this._path[depth]];
        node[NODE_BOUND] = node[NODE_BOUND] || this._mark(node);
        at -= 0 | this._addr(this._path[depth], node);

        if (at < (child[NODE_SIZE] || this.size(child))) {
          node = child;
          depth++;
        } else {
          break;
        }
      }

      this._path[depth++] += 1;
      this._cached = cached;
      this._from = root;

      while (this._parental(node)) {
        node = node.$values[this._path[depth]];
        this._path[depth++] = 0;
      }

      return cached;
    }
  }

  _prior(root = this._root || null) {
    let node = root || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    let at = (0 | this._cached) < 0 ? size - 1 : (0 | this._cached) - 1;
    const cached = at;
    let depth = 0;
    let child = node || null;

    if (!node || at < 0) {
      this._cached = -1;
      this._from = null;
      return -1;
    } else if (at === size - 1) {
      while (this._parental(node)) {
        this._path[depth++] = this._amount(node) - 1;
        node = node.$values[this._amount(node) - 1];
      }

      this._path[depth++] = (node[NODE_SIZE] || this.size(node)) - 1;
      this._cached = size - 1;
      this._from = root;
      return size - 1;
    } else {
      while (this._parental(node)) {
        child = node.$values[this._path[depth]];
        node[NODE_BOUND] = node[NODE_BOUND] || this._mark(node);
        at -= 0 | this._addr(this._path[depth], node);

        if (at > -1) {
          node = child;
          depth++;
        } else {
          break;
        }
      }

      this._path[depth++] -= 1;
      this._cached = cached;
      this._from = root;

      while (this._parental(node)) {
        node = node.$values[this._path[depth]];
        this._path[depth++] = this._amount(node) - 1;
      }

      return cached;
    }
  }

  collection() {
    return new BestCollection("", this.data() || null, {
      comparator: this._cmp || null,
      use: this._toKey || null,
      search: this._search || null,
      aggregate: this._aggregate || null
    });
  }

  iterator() {
    return new BestIterator("", this.data() || null, {
      comparator: this._cmp || null,
      use: this._toKey || null,
      search: this._search || null,
      aggregate: this._aggregate || null
    });
  }

  data(root = this._root || null) {
    const data = this._root;

    if (root !== data) {
      this._root = root;
      this._cached = -1;
      this._from = null;
    }

    return data;
  }

  size(root = this._root || null) {
    const count = root ? this._amount(root) : 0;

    if (!root) {
      return 0;
    } else if (!this._parental(root)) {
      root[NODE_SIZE] = count;
      return 0 | root[NODE_SIZE];
    } else if (root[NODE_SIZE]) {
      return 0 | root[NODE_SIZE];
    } else {
      root[NODE_BOUND] = root[NODE_BOUND] || this._mark(root);
      root[NODE_SIZE] = 0 | root[NODE_BOUND][count - 1];
      return 0 | root[NODE_SIZE];
    }
  }

  _mark(node) {
    const count = this._amount(node);
    let index = 0;
    let bound = new Array(count);
    let sum = 0;

    for (index; index < count; index++) {
      sum +=
        0 | (node.$values[index][NODE_SIZE] || this.size(node.$values[index]));
      bound[index] = sum;
    }

    node[NODE_BOUND] = bound;
    node[NODE_SIZE] = 0 | sum;

    return bound;
  }

  _addr(index, node) {
    const at = 0 | index;
    return at > 0 ? 0 | node[NODE_BOUND][at - 1] : 0;
  }

  _amount(node) {
    node[NODE_LIMIT] = node[NODE_LIMIT] || node.$values.length;
    return 0 | node[NODE_LIMIT];
  }

  jump(delta = 1, root = this._root || null) {
    const node = root || null;
    let cycles = 0 | delta;
    let index = 0;

    if (!node) {
      return -1;
    } else if (!cycles) {
      return this._cached;
    } else if (cycles > 0) {
      while (cycles-- > 0 && index > -1) {
        index = this._next(node);
      }
      return index;
    } else {
      while (cycles++ < 0 && index > -1) {
        index = this._prior(node);
      }
      return index;
    }
  }

  look(
    offset = 0 | this._cached,
    sentinel = void 0,
    root = this._root || null
  ) {
    let node = root || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    let at = 0 | this._clamp(0 | offset, size);
    const cached = at;
    let depth = 0;
    let index = 0;

    if (at >= size || !node) {
      return sentinel;
    } else if (at === 0) {
      while (this._parental(node)) {
        this._path[depth++] = 0;
        node = node.$values[0];
      }

      this._path[depth++] = 0;
      this._cached = cached;
      this._from = root;
      return node.$values[0];
    } else if (at === size - 1) {
      while (this._parental(node)) {
        index = (0 | this._amount(node)) - 1;
        this._path[depth++] = index;
        node = node.$values[index];
      }

      index = (0 | this._amount(node)) - 1;
      this._path[depth++] = index;
      this._cached = cached;
      this._from = root;
      return node.$values[index];
    } else if (at === this._cached && root === this._from) {
      // TODO: guarantee immutable root (when bulk mutation is supported)
      while (this._parental(node)) {
        node = node.$values[this._path[depth++]];
      }
      return node.$values[this._path[depth++]];
    } else {
      while (this._parental(node)) {
        node[NODE_BOUND] = node[NODE_BOUND] || this._mark(node);
        index = 0 | this._indexOf(at + 1, -1, node[NODE_BOUND], null, null);
        at -= 0 | this._addr(index, node);
        this._path[depth++] = index;
        node = node.$values[index];
      }

      this._path[depth++] = at;
      this._cached = cached;
      this._from = root;
      return node.$values[at];
    }
  }

  offset(key, nearest = false, root = this._root || null) {
    let at = 0;
    let depth = 0;
    let node = root || null;
    let index = 0;

    if (!this._cmp) {
      return -1;
    } else if (!node) {
      return nearest ? 0 : -1;
    } else {
      while (this._parental(node)) {
        node[NODE_BOUND] = node[NODE_BOUND] || this._mark(node);
        node[NODE_BOUND] = node[NODE_BOUND] || this._trace(node);
        index = 0 | this._indexOf(key, -1, node[NODE_BOUND]);
        at -= 0 | this._addr(index, node);
        this._path[depth++] = index;
        node = node.$values[index];
      }

      index = this._indexOf(key, -1, node.$values);
      at += index;
      this._path[depth++] = index;
      this._cached = at;
      this._from = root;
      return nearest ? at : this.net(key, node.$values[index]) ? -1 : at;
    }
  }

  _trace(node) {
    const count = this._amount(node);
    let index = 0;
    let edge = new Array(count);
    let other = node;

    for (index; index < count; index++) {
      other = node.$values[index];

      if (this._parental(other)) {
        other[NODE_BOUND] = other[NODE_BOUND] || this._trace(other);
        edge[index] = other[NODE_BOUND][0];
      } else {
        edge[index] = other.$values[0];
      }
    }

    node[NODE_BOUND] = edge;

    return edge;
  }

  where(datum, nearest = false, root = this._root || null) {
    return this.offset(
      this._toKey ? this._toKey(datum) : datum,
      nearest,
      root || null
    );
  }

  match(datum, sentinel, root = this._root || null) {
    return this.get(
      this._toKey ? this._toKey(datum) : datum,
      sentinel,
      root || null
    );
  }

  get(key, sentinel, root = this._root || null) {
    const at = this.offset(key);
    return at < 0 ? sentinel : this.look(at, sentinel, root || null);
  }

  view(aggregate, offset, bound, sentinel, root = this._root || null) {
    const ctx = this._aggregate ? this._aggregate.get(aggregate) || null : null;
    const node = root || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    const at = 0 | this._clamp(0 | offset, size);
    const limit = 0 | this._clamp(0 | bound, size);

    if (!ctx || !size || limit < 1 || at >= size) {
      return sentinel;
    } else if (at === 0 && limit === size) {
      root[NODE_CALC] = root[NODE_CALC] || new Map();

      if (!root[NODE_CALC].has(aggregate)) {
        root[NODE_CALC].set(
          aggregate,
          this._view(ctx, root, aggregate, at, limit)
        );
      }

      return root[NODE_CALC].get(aggregate);
    } else {
      return this._view(ctx, root, aggregate, at, limit);
    }
  }

  _view(ctx, node, aggregate, offset, bound) {
    const size = node[NODE_SIZE] || this.size(node);
    let at = 0 | offset;
    let limit = 0 | bound;
    let count = 0;
    let index = 0;
    let delta = 0;
    let result;

    if (this._parental(node)) {
      node[NODE_BOUND] = node[NODE_BOUND] || this._mark(node);
    }

    count =
      limit === size
        ? 0 | this._amount(node)
        : this._parental(node)
          ? 0 | this._indexOf(limit + 1, -1, node[NODE_BOUND], null, null)
          : limit;
    index =
      at === 0
        ? 0
        : this._parental(node)
          ? 0 | this._indexOf(at + 1, -1, node[NODE_BOUND], null, null)
          : at;

    if (count === index) {
      return this._parental(node)
        ? this._view(
            ctx,
            node.$values[index],
            aggregate,
            at - this._addr(index, node),
            limit - this._addr(index, node)
          )
        : ctx.init(this._toKey || null, this._cmp || null, ctx);
    } else if (this._parental(node)) {
      index -= at === 0 ? 1 : 0;

      result =
        index < 0
          ? ctx.init(this._toKey || null, this._cmp || null, ctx)
          : this._view(
              ctx,
              node.$values[index],
              aggregate,
              at - this._addr(index, node),
              0 |
                (node.$values[index][NODE_SIZE] ||
                  this.size(node.$values[index]))
            );

      for (index++; index < count; index++) {
        node.$values[index][NODE_CALC] =
          node.$values[index][NODE_CALC] || new Map();

        if (!node.$values[index][NODE_CALC].has(aggregate)) {
          node.$values[index][NODE_CALC].set(
            aggregate,
            this._view(
              ctx,
              node.$values[index],
              aggregate,
              0,
              0 |
                (node.$values[index][NODE_SIZE] ||
                  this.size(node.$values[index]))
            )
          );
        }

        result = ctx.fuse(
          result,
          node.$values[index][NODE_CALC].get(aggregate),
          this._toKey || null,
          this._cmp || null,
          ctx
        );
      }

      return count < this._amount(node)
        ? ctx.fuse(
            result,
            this._view(
              ctx,
              node.$values[count],
              aggregate,
              0,
              limit - this._addr(count, node)
            ),
            this._toKey || null,
            this._cmp || null,
            ctx
          )
        : result;
    } else {
      result = ctx.init(this._toKey || null, this._cmp || null, ctx);

      for (index; index < count; index++) {
        result = ctx.reduce(
          result,
          node.$values[index],
          this._toKey || null,
          this._cmp || null,
          ctx
        );
      }

      return result;
    }
  }

  _model(node, search, ctx) {
    const limit = 0 | this._amount(node);
    let index = 0;
    let result = ctx.init(this._toKey || null, this._cmp || null, ctx);

    if (this._parental(node)) {
      for (index; index < limit; index++) {
        node.$values[index][NODE_REP] =
          node.$values[index][NODE_REP] || new Map();

        if (!node.$values[index][NODE_REP].has(search)) {
          node.$values[index][NODE_REP].set(
            search,
            this._model(node.$values[index], search, ctx)
          );
        }

        result = ctx.fuse(
          result,
          node.$values[index][NODE_REP].get(search),
          this._toKey || null,
          this._cmp || null,
          ctx
        );
      }
    } else {
      for (index; index < limit; index++) {
        result = ctx.reduce(
          result,
          node.$values[index],
          this._toKey || null,
          this._cmp || null,
          ctx
        );
      }
    }

    // node[NODE_REP] = node[NODE_REP] || new Map();
    // node[NODE_REP].set(search, result);
    return result;
  }

  forward(search, params, offset = this._cached, root = this._root || null) {
    const ctx = this._search ? this._search.get(search) || null : null;
    const node = root || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    const at = 0 | this._clamp(0 | offset, size);
    let result = -1;

    if (!ctx || !size || at >= size) {
      return -1;
    } else {
      this.look(at, void 0, node);
      result = 0 | this._forward(ctx, node, at, 0, search, params);

      if (result < 0) {
        this._cached = -1;
        this._from = null;
        return -1;
      } else {
        this._cached = result;
        this._from = node;
        return result;
      }
    }
  }

  _forward(ctx, node, offset, depth, search, params) {
    const limit = this._amount(node);
    let index = this._path[0 | depth];
    let at = 0 | offset;
    let count = 0;
    let result = -1;

    if (index < 0) {
      index = 0;
      this._path[0 | depth] = 0;
    }

    if (this._parental(node)) {
      count = 0 | this._addr(index, node);
      result =
        0 |
        this._forward(
          ctx,
          node.$values[index],
          at - count,
          1 + (0 | depth),
          search,
          params
        );

      if (result > -1) {
        this._path[0 | depth] = index;
        return result + count;
      } else {
        node[NODE_REP] = node[NODE_REP] || new Map();

        if (!node[NODE_REP].has(search)) {
          node[NODE_REP].set(search, this._model(node, search, ctx));
        }

        if (
          ctx.attempt(
            node[NODE_REP].get(search),
            params,
            this._toKey || null,
            this._cmp || null,
            ctx
          )
        ) {
          for (index++; index < limit; index++) {
            count = 0 | this._addr(index, node);
            result =
              0 |
              this._forward(
                ctx,
                node.$values[index],
                0,
                1 + (0 | depth),
                search,
                params
              );

            if (result > -1) {
              this._path[0 | depth] = index;
              return result + count;
            }
          }

          this._path[0 | depth] = -1;
          return -1;
        } else {
          this._path[0 | depth] = -1;
          return -1;
        }
      }
    } else {
      node[NODE_REP] = node[NODE_REP] || new Map();

      if (!node[NODE_REP].has(search)) {
        node[NODE_REP].set(search, this._model(node, search, ctx));
      }

      if (
        ctx.attempt(
          node[NODE_REP].get(search),
          params,
          this._toKey || null,
          this._cmp || null,
          ctx
        )
      ) {
        for (index; index < limit; index++) {
          if (
            ctx.test(
              node.$values[index],
              params,
              this._toKey || null,
              this._cmp || null,
              ctx
            )
          ) {
            this._path[0 | depth] = index;
            return index;
          }
        }

        this._path[0 | depth] = -1;
        return -1;
      } else {
        this._path[0 | depth] = -1;
        return -1;
      }
    }
  }

  backward(search, params, offset = this._cached, root = this._root || null) {
    const ctx = this._search ? this._search.get(search) || null : null;
    const node = root || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    const at = 0 | this._clamp(0 | offset, size);
    let result = -1;

    if (!ctx || !size || at >= size) {
      return -1;
    } else {
      this.look(at, void 0, node);
      result = 0 | this._backward(ctx, node, at, 0, search, params);

      if (result < 0) {
        this._cached = -1;
        this._from = null;
        return -1;
      } else {
        this._cached = result;
        this._from = node;
        return result;
      }
    }
  }

  _backward(ctx, node, offset, depth, search, params) {
    const limit = 0 | this._amount(node);
    let index = 0 | this._path[0 | depth];
    let at = 0 | offset;
    let count = 0;
    let result = -1;

    if (index < 0) {
      index = limit - 1;
      this._path[0 | depth] = index;
    }

    if (this._parental(node)) {
      count = 0 | this._addr(index, node);
      result =
        0 |
        this._backward(
          ctx,
          node.$values[index],
          at - count,
          1 + (0 | depth),
          search,
          params
        );

      if (result > -1) {
        this._path[0 | depth] = index;
        return result + count;
      } else {
        node[NODE_REP] = node[NODE_REP] || new Map();

        if (!node[NODE_REP].has(search)) {
          node[NODE_REP].set(search, this._model(node, search, ctx));
        }

        if (
          ctx.attempt(
            node[NODE_REP].get(search),
            params,
            this._toKey || null,
            this._cmp || null,
            ctx
          )
        ) {
          for (index; index-- > 0; ) {
            count = 0 | this._addr(index, node);
            result =
              0 |
              this._backward(
                ctx,
                node.$values[index],
                0,
                1 + (0 | depth),
                search,
                params
              );

            if (result > -1) {
              this._path[0 | depth] = index;
              return result + count;
            }
          }

          this._path[0 | depth] = -1;
          return -1;
        } else {
          this._path[0 | depth] = -1;
          return -1;
        }
      }
    } else {
      node[NODE_REP] = node[NODE_REP] || new Map();

      if (!node[NODE_REP].has(search)) {
        node[NODE_REP].set(search, this._model(node, search, ctx));
      }

      if (
        ctx.attempt(
          node[NODE_REP].get(search),
          params,
          this._toKey || null,
          this._cmp || null,
          ctx
        )
      ) {
        for (index++; index-- > 0; ) {
          if (
            ctx.test(
              node.$values[index],
              params,
              this._toKey || null,
              this._cmp || null,
              ctx
            )
          ) {
            this._path[0 | depth] = index;
            return index;
          }
        }

        this._path[0 | depth] = -1;
        return -1;
      } else {
        this._path[0 | depth] = -1;
        return -1;
      }
    }
  }
}

class BestIterator extends BestTree {}

class BestCollection extends BestTree {
  static Leaf(values, factor) {
    return {
      $factor: 0 | factor,
      $values: values || null,
      [NODE_LIMIT]: values ? values.length : 0,
      [NODE_SIZE]: 0,
      [NODE_BOUND]: null,
      [NODE_EDGE]: null,
      [NODE_CALC]: null,
      [NODE_REP]: null
    };
  }

  static Branch(stems, factor) {
    return BestCollection.Leaf(stems, -factor);
  }

  constructor(options) {
    super(options);
    this._datum = void 0;
  }

  take(offset = this.jump(), sentinel = void 0) {
    const node = this.data() || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    const at = 0 | this._clamp(0 | offset, size);
    const result = this.look(at, sentinel);
  }

  enter(offset, datum, sentinel) {
    // replaces this._root with a fresh immutable pojo
    // old version is not mutated to support snapshots
  }

  assign(offset, datum, sentinel) {
    // replaces this._root with a fresh immutable pojo
    // old version is not mutated to support snapshots
  }

  put(datum, sentinel) {
    const node = this.data() || null;
    const size = node ? 0 | (node[NODE_SIZE] || this.size(node)) : 0;
    const key = this._toKey ? this._toKey(datum) : datum;
    const at = 0 | this.offset(key);
    const index = at < 0 ? size : at;

    if (index < size && 0 === this.net(key, this.look(index))) {
      return this.assign(index, datum, sentinel);
    } else {
      return this.enter(index, datum, sentinel);
    }
  }

  remove(datum, sentinel) {
    return this.unset(this._toKey ? this._toKey(datum) : datum, sentinel);
  }

  unset(key, sentinel) {
    const at = this.offset(key);
    return at < 0 ? sentinel : this.take(at, sentinel);
  }
}