export interface Operation {
  opId: string;
  /** Causal predecessors. Omitted or empty for a root op. */
  previousOpIds?: string[];
}

/**
 * Sort operations into a deterministic order, deduplicated by opId.
 *
 * Algorithm:
 *  - Deduplicate by opId — opId is identity, so duplicate copies of an op fold
 *    once (a redelivered insert must not splice twice). A deterministic
 *    representative is kept (see the body), so the result is independent of
 *    input order.
 *  - Each operation is assigned a bucket. An op with no previousOpIds is in
 *    bucket 0. Otherwise its bucket is MAX(bucket of each previousOpId) + 1.
 *  - Operations are ordered by bucket ascending, then lexically by opId
 *    within a bucket. opIds are unique after dedup, so the order is total.
 *
 * An op is dropped from the result if its previousOpIds can never be satisfied
 * by an applied op. That covers references to a missing opId, ops in a cycle,
 * and ops that transitively depend on either.
 */
export function sortOperations<T extends Operation>(operations: T[]): T[] {
  // Deduplicate by opId: the opId *is* the op's identity (see `identity.ts`), so
  // two ops sharing one are the same op and must fold once — otherwise a redelivered
  // insert would splice its block twice. Same-opId copies are byte-identical except
  // possibly in `previousOpIds` (a content id that excludes deps, e.g. `delete`, can
  // be issued from different causal views). We keep a deterministic representative —
  // the one whose sorted `previousOpIds` is lexicographically smallest — so the pick
  // never depends on input order and every replica converges on it. The choice is
  // arbitrary but stable; it is sound because a deps-excluding id is, by definition,
  // one whose effect does not depend on its causal position. Deps-bearing ids carry
  // their deps in the id, so all their copies tie here and the first is kept.
  const depsKey = (op: Operation): string =>
    JSON.stringify([...(op.previousOpIds ?? [])].sort());
  const byId = new Map<string, T>();
  for (const op of operations) {
    const existing = byId.get(op.opId);
    if (!existing || depsKey(op) < depsKey(existing)) byId.set(op.opId, op);
  }

  // Final memoized bucket per opId. `null` means unresolvable (cyclic or
  // depends on a cycle) and the op is excluded from the result.
  const buckets = new Map<string, number | null>();
  const onStack = new Set<string>();

  const bucketOf = (opId: string): number | null => {
    if (buckets.has(opId)) return buckets.get(opId)!;

    const op = byId.get(opId);
    // Missing reference: never applied -> unresolvable.
    if (!op) {
      buckets.set(opId, null);
      return null;
    }
    // No predecessors (omitted or empty) -> root, bucket 0.
    const previousOpIds = op.previousOpIds ?? [];
    if (previousOpIds.length === 0) {
      buckets.set(opId, 0);
      return 0;
    }

    // Back edge: opId is still resolving further up the stack -> cycle.
    // Don't cache here; this frame finishes resolving below.
    if (onStack.has(opId)) return null;
    onStack.add(opId);

    let max = -1;
    let resolvable = true;
    for (const prev of previousOpIds) {
      const prevBucket = bucketOf(prev);
      if (prevBucket === null) {
        resolvable = false;
        break;
      }
      max = Math.max(max, prevBucket);
    }
    onStack.delete(opId);

    const bucket = resolvable ? max + 1 : null;
    buckets.set(opId, bucket);
    return bucket;
  };

  return [...byId.values()]
    .filter((op) => bucketOf(op.opId) !== null)
    .sort((a, b) => {
      const bucketDiff = bucketOf(a.opId)! - bucketOf(b.opId)!;
      if (bucketDiff !== 0) return bucketDiff;
      return a.opId < b.opId ? -1 : a.opId > b.opId ? 1 : 0;
    });
}