all files / src/ search.js

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
1×
 
514×
 
 
 
 
 
 
 
30×
 
 
 
 
 
 
 
 
 
113×
 
 
 
 
9×
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
122×
4×
24×
26×
 
 
 
 
 
 
11×
27×
27×
 
 
 
 
 
 
 
 
import Node from './node';
 
export function* dfsPreOrder(node, onlyLeaves, parentSeen) {
  if (node.isLeaf()) {
    yield node;
    return;
  }
  if (!onlyLeaves) {
    yield node;
  }
  const seen = parentSeen.add(node.value);
  for (let [key, value] of node.createIterator()) {
    yield* dfsPreOrder(
      new Node(key, value, node, seen.has(value)),
      onlyLeaves,
      seen
    );
  }
}
 
export function* dfsPostOrder(node, onlyLeaves, parentSeen) {
  if (node.isLeaf()) {
    yield node;
    return;
  }
  const seen = parentSeen.add(node.value);
  for (let [key, value] of node.createIterator()) {
    yield* dfsPostOrder(
      new Node(key, value, node, seen.has(value)),
      onlyLeaves,
      seen
    );
  }
  if (!onlyLeaves) {
    yield node;
  }
}
 
// transpiled generator has uncovered branches
// istanbul issue #645
/* istanbul ignore next */
export function* bfs(rootNode, onlyLeaves, parentSeen) {
  const queue = [{node: rootNode, seen: parentSeen}];
  for (let i = 0; i < queue.length; i++) {
    const node = queue[i].node;
    if (node.isLeaf()) {
      yield node;
    } else {
      if (!onlyLeaves) {
        yield node;
      }
      const seen = queue[i].seen.add(node.value);
      for (let [key, value] of node.createIterator()) {
        queue.push({
          node: new Node(key, value, node, seen.has(value)),
          seen
        });
      }
    }
  }
}