DynamicTopSortQueue.ts

/**
 * Queue for dynamic topological sorting.
 * Paste a node and it kind, where
 * `one` - is node with one up,
 * `few` - is node with few up.
 * After each `add` you must to extract next node by `get` method,
 * process it, add it children, and so on.
 */
export class Queue<T> {
  one = new Array<T>();
  few = new Array<T>();
  add(el: T, type: "one" | "few"): void {
    if (type === "one" || !this.few.includes(el)) this[type].push(el);
  }
  get(): T | undefined {
    return this.one.shift() || this.few.shift();
  }
}

class Node {
  constructor(
    public cb: () => void,
    /** children */
    public to: Node[] = [],
    /** parents */
    public up: Node[] = []
  ) {}
}

function link(up: Node, child: Node) {
  up.to.push(child);
  child.up.push(up);
}

// const { log } = console;
const _log = [];
const log = (msg) => _log.push(msg);

const a = new Node(() => log("a"));
const b = new Node(() => log("b"));
const c = new Node(() => log("c"));
const d = new Node(() => log("d"));
link(a, b);
link(a, c);
link(b, d);
link(c, d);
link(new Node(() => {}), b);

walk(a);
_log; //?

const e = new Node(() => log("e"));
const f = new Node(() => log("f"));
link(a, e);
link(e, f);
link(f, d);
link(new Node(() => {}), f);
_log.length = 0;
walk(a);
_log; //?

function walk(node: Node) {
  // return;
  const queue = new Queue<Node>();

  while (node) {
    node.cb();

    node.to.forEach((n) => {
      queue.add(n, n.up.length > 1 ? "few" : "one");
    });

    node = queue.get();

    while (node && queue.few.some((n) => isDeepChild(n, node))) {
      queue.add(node, "few");
      node = queue.get();
    }
  }
}

function isDeepChild(node: Node, possibleChild: Node): boolean {
  return node.to.some(
    (child) => child === possibleChild || isDeepChild(child, possibleChild)
  );
}