sync-playground/sync/ordt/plain-text.ts

import { Timestamp, timestampCompare } from "../common.ts";
import { AnyCausalTreeOp, CausalTree, CausalTreeOp } from "./causal-tree.ts";

export type PlainTextOperation =
  | {
      type: "insert";
      sequence: string;
    }
  | { type: "delete" };

export class PlainTextORDT extends CausalTree<PlainTextOperation> {
  onevent?: (
    op: CausalTreeOp<PlainTextOperation>,
    textIndex: number,
    affectedLength: number,
  ) => void;

  // caches for insert op <=> text transformation,
  // all these arrays should be the same length (SoA)
  opIndexCache: number[] = [];
  sequences: string[] = [];
  timestamps: Timestamp[] = [];
  deleted: boolean[] = [];

  override apply(op: AnyCausalTreeOp<PlainTextOperation>): number {
    const opIdx = super.apply(op);
    op = this.operations[opIdx];

    const [idx, len] = this.#applyCacheUpdate(op, opIdx);
    this.onevent?.(op, idx, len);
    return opIdx;
  }

  #applyCacheUpdate(op: CausalTreeOp<PlainTextOperation>, opIdx: number): [number, number] {
    for (let i = 0; i < this.opIndexCache.length; i++) {
      if (this.opIndexCache[i] >= opIdx) {
        this.opIndexCache[i] += 1;
      }
    }

    const parentTimestamp = op.parent?.at;
    const parentCacheIdx = this.timestamps.findIndex(it => it === parentTimestamp);

    if (op.type === "insert") {
      let cacheIdx = parentCacheIdx + 1;
      for (; cacheIdx < this.timestamps.length; cacheIdx++) {
        const curr = this.timestamps[cacheIdx];
        if (timestampCompare(curr, op.at) < 0) break;
      }

      this.sequences.splice(cacheIdx, 0, op.sequence);
      this.timestamps.splice(cacheIdx, 0, op.at);
      this.deleted.splice(cacheIdx, 0, false);
      this.opIndexCache.splice(cacheIdx, 0, opIdx);

      let textIndex = 0;
      for (let i = 0; i < cacheIdx; i++) {
        if (this.deleted[i]) continue;
        textIndex += this.sequences[i].length;
      }
      return [textIndex, op.sequence.length];
    }
    if (op.type === "delete" && parentCacheIdx !== -1) {
      this.deleted[parentCacheIdx] = true;

      let textIndex = 0;
      for (let i = 0; i < parentCacheIdx; i++) {
        if (this.deleted[i]) continue;
        textIndex += this.sequences[i].length;
      }
      return [textIndex, -this.sequences[parentCacheIdx].length];
    }

    return [-1, 0];
  }

  findOpAtTextIndex(textIndex: number): number {
    let start = 0;
    for (let idx = 0; idx < this.sequences.length; idx++) {
      if (this.deleted[idx]) continue;

      const sequence = this.sequences[idx];
      if (start < textIndex && textIndex <= start + sequence.length)
        return this.opIndexCache[idx];

      start += this.sequences[idx].length;
    }

    return -1;
  }

  render() {
    let s = "";
    let start = 0;
    const metadata = [];
    for (let idx = 0; idx < this.sequences.length; idx++) {
      if (this.deleted[idx]) continue;
      const sequence = this.sequences[idx];
      s += sequence;
      metadata.push({
        start,
        end: start + sequence.length,
        op: this.operations[this.opIndexCache[idx]],
      });
      start += sequence.length;
    }
    return [s, metadata] as const;
  }
}