优化

‘liusuyi’

2023-10-21 ae92b6823499cfab77201b4033922fa373fb37a3

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
const PERMANENT_MARKER = 2
const TEMPORARY_MARKER = 1
 
function createError(node, graph) {
  const er = new Error("Nondeterministic import's order")
 
  const related = graph[node]
  const relatedNode = related.find(
    relatedNode => graph[relatedNode].indexOf(node) > -1
  )
 
  er.nodes = [node, relatedNode]
 
  return er
}
 
function walkGraph(node, graph, state, result, strict) {
  if (state[node] === PERMANENT_MARKER) return
  if (state[node] === TEMPORARY_MARKER) {
    if (strict) return createError(node, graph)
    return
  }
 
  state[node] = TEMPORARY_MARKER
 
  const children = graph[node]
  const length = children.length
 
  for (let i = 0; i < length; ++i) {
    const er = walkGraph(children[i], graph, state, result, strict)
    if (er instanceof Error) return er
  }
 
  state[node] = PERMANENT_MARKER
 
  result.push(node)
}
 
function topologicalSort(graph, strict) {
  const result = []
  const state = {}
 
  const nodes = Object.keys(graph)
  const length = nodes.length
 
  for (let i = 0; i < length; ++i) {
    const er = walkGraph(nodes[i], graph, state, result, strict)
    if (er instanceof Error) return er
  }
 
  return result
}
 
module.exports = topologicalSort