All files toposort.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
1x
1x
1x
7x
7x
38x
2x
2x
2x
2x
 
 
2x
2x
36x
38x
 
 
36x
36x
26x
26x
38x
38x
38x
38x
38x
18x
18x
20x
20x
18x
12x
12x
20x
20x
38x
7x
7x
7x
1x
7x
7x
7x
7x
7x
7x
7x
7x
7x
7x
22x
22x
5x
5x
5x
1x
1x
8x
8x
8x
8x
1x
1x
5x
5x
1x
1x
1x
1x
 
 
import { makeNodesHash, makeOutgoingEdges, uniqueNodes } from './helpers.js'
import { validateEdges } from './validators.js'
 
function visitFactory(visited: Record<string, boolean>, outgoingEdges: Map<unknown, Set<unknown>>, nodesHash: Map<unknown, number>, sorted: any[], cursor: number) {
  function visit(node: unknown, i: number, predecessors: Set<unknown>) {
    if (predecessors.has(node)) {
      let nodeRep
      try {
        nodeRep = ', node was:' + JSON.stringify(node)
      } catch {
        nodeRep = ''
      }
      throw new Error('Cyclic dependency' + nodeRep)
    }
 
    if (!nodesHash.has(node)) {
      throw new Error('Found unknown node. Make sure to provided all involved nodes. Unknown node: ' + JSON.stringify(node))
    }
 
    if (visited[i]) return
    visited[i] = true
 
    const outgoingSet: (Set<unknown> | unknown[]) = outgoingEdges.get(node) || new Set()
    const outgoing = [...outgoingSet]
    i = outgoing.length
 
    if (i) {
      predecessors.add(node)
      do {
        const child: any = outgoing[--i]
        visit(child, nodesHash.get(child) as number, predecessors)
      } while (i)
      predecessors.delete(node)
    }
 
    sorted[--cursor] = node
  }
 
  return visit
}
 
function toposortCore(nodes: unknown[], edges: unknown[][]) {
  const cursor = nodes.length
  let i = cursor
  const sorted: any[] = []
  const visited: Record<string, boolean> = {}
  const nodesHash = makeNodesHash(nodes)
  const outgoingEdges = makeOutgoingEdges(edges)
  const visit = visitFactory(visited, outgoingEdges, nodesHash, sorted, cursor)
 
  while (i--) {
    if (!visited[i]) visit(nodes[i], i, new Set())
  }
 
  return sorted
}
 
export function toposort(nodes: unknown[], edges: unknown[][]) {
  validateEdges(nodes, edges)
 
  return toposortCore(nodes, edges)
}
 
export function toposortDefault(edges: unknown[][]) {
  return toposort(uniqueNodes(edges), edges)
}
 
toposortDefault.array = toposort
 
export default toposortDefault