-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathNode.java
More file actions
82 lines (78 loc) · 2.71 KB
/
Node.java
File metadata and controls
82 lines (78 loc) · 2.71 KB
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
73
74
75
76
77
78
79
80
81
82
package iterator;
import java.util.*;
public class Node {
private final String name;
private List<Node> children = new ArrayList<>();
public Node(String name) {
this.name = name;
}
public Node(String name, Node... children) {
this.name = name;
this.children.addAll(Arrays.asList(children));
}
public String getName() {
return this.name;
}
public List<Node> getChildren() {
return this.children;
}
public Iterable<Node> breadthFirstSearch() {
return () -> new NodeIterator(this, true);
}
public Iterable<Node> depthFirstSearch() {
return () -> new NodeIterator(this, false);
}
@Override
public String toString() {
return "Node[" + this.name + "]";
}
static class NodeIterator implements Iterator<Node> {
private final Deque<Iterator<Node>> iterators = new ArrayDeque<>();
private final boolean breadthFirst;
public NodeIterator(Node node, boolean breadthFirst) {
this.iterators.add(Collections.singleton(node).iterator());
this.breadthFirst = breadthFirst;
}
@Override
public boolean hasNext() {
return ! this.iterators.isEmpty();
}
@Override
public Node next() {
Iterator<Node> iterator = this.iterators.removeFirst();
Node node = iterator.next();
if (iterator.hasNext())
this.iterators.addFirst(iterator);
if (! node.getChildren().isEmpty()) {
if (this.breadthFirst)
this.iterators.addLast(node.getChildren().iterator());
else
this.iterators.addFirst(node.getChildren().iterator());
}
return node;
}
}
public static void main(String[] args) {
Node root = new Node("root",
new Node("1",
new Node("1.1",
new Node("1.1.1"),
new Node("1.1.2")),
new Node("1.2",
new Node("1.2.1"),
new Node("1.2.2"))
),
new Node("2",
new Node("2.1",
new Node("2.1.1"),
new Node("2.1.2")),
new Node("2.2",
new Node("2.2.1"),
new Node("2.2.2"))));
for (Node node : root.breadthFirstSearch())
System.out.println(node);
System.out.println();
for (Node node : root.depthFirstSearch())
System.out.println(node);
}
}