llparse-builder/src/reachability.ts


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import { Node } from './node';

/**
 * This class finds all reachable nodes
 */
export class Reachability {
  /**
   * Build and return list of reachable nodes.
   */
  public build(root: Node): ReadonlyArray<Node> {
    const res = new Set();
    const queue = [ root ];
    while (queue.length !== 0) {
      const node = queue.pop()!;
      if (res.has(node)) {
        continue;
      }
      res.add(node);

      for (const edge of node) {
        queue.push(edge.node);
      }

      const otherwise = node.getOtherwiseEdge();
      if (otherwise !== undefined) {
        queue.push(otherwise.node);
      }
    }
    return Array.from(res) as ReadonlyArray<Node>;
  }
}