/
NodeTraversor.java
131 lines (122 loc) · 4.86 KB
/
NodeTraversor.java
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package org.jsoup.select;
import org.jsoup.helper.Validate;
import org.jsoup.nodes.Element;
import org.jsoup.nodes.Node;
import org.jsoup.select.NodeFilter.FilterResult;
/**
* Depth-first node traversor. Use to iterate through all nodes under and including the specified root node.
* <p>
* This implementation does not use recursion, so a deep DOM does not risk blowing the stack.
* </p>
*/
public class NodeTraversor {
/**
* Start a depth-first traverse of the root and all of its descendants.
* @param visitor Node visitor.
* @param root the root node point to traverse.
*/
public static void traverse(NodeVisitor visitor, Node root) {
Validate.notNull(visitor);
Validate.notNull(root);
Node node = root;
Node parent; // remember parent to find nodes that get replaced in .head
int depth = 0;
while (node != null) {
parent = node.parentNode();
visitor.head(node, depth); // visit current node
if (parent != null && !node.hasParent()) // must have been replaced; find replacement
node = parent.childNode(node.siblingIndex()); // replace ditches parent but keeps sibling index
if (node.childNodeSize() > 0) { // descend
node = node.childNode(0);
depth++;
} else {
while (true) {
assert node != null; // as depth > 0, will have parent
if (!(node.nextSibling() == null && depth > 0)) break;
visitor.tail(node, depth); // when no more siblings, ascend
node = node.parentNode();
depth--;
}
visitor.tail(node, depth);
if (node == root)
break;
node = node.nextSibling();
}
}
}
/**
* Start a depth-first traverse of all elements.
* @param visitor Node visitor.
* @param elements Elements to filter.
*/
public static void traverse(NodeVisitor visitor, Elements elements) {
Validate.notNull(visitor);
Validate.notNull(elements);
for (Element el : elements)
traverse(visitor, el);
}
/**
* Start a depth-first filtering of the root and all of its descendants.
* @param filter Node visitor.
* @param root the root node point to traverse.
* @return The filter result of the root node, or {@link FilterResult#STOP}.
*/
public static FilterResult filter(NodeFilter filter, Node root) {
Node node = root;
int depth = 0;
while (node != null) {
FilterResult result = filter.head(node, depth);
if (result == FilterResult.STOP)
return result;
// Descend into child nodes:
if (result == FilterResult.CONTINUE && node.childNodeSize() > 0) {
node = node.childNode(0);
++depth;
continue;
}
// No siblings, move upwards:
while (true) {
assert node != null; // depth > 0, so has parent
if (!(node.nextSibling() == null && depth > 0)) break;
// 'tail' current node:
if (result == FilterResult.CONTINUE || result == FilterResult.SKIP_CHILDREN) {
result = filter.tail(node, depth);
if (result == FilterResult.STOP)
return result;
}
Node prev = node; // In case we need to remove it below.
node = node.parentNode();
depth--;
if (result == FilterResult.REMOVE)
prev.remove(); // Remove AFTER finding parent.
result = FilterResult.CONTINUE; // Parent was not pruned.
}
// 'tail' current node, then proceed with siblings:
if (result == FilterResult.CONTINUE || result == FilterResult.SKIP_CHILDREN) {
result = filter.tail(node, depth);
if (result == FilterResult.STOP)
return result;
}
if (node == root)
return result;
Node prev = node; // In case we need to remove it below.
node = node.nextSibling();
if (result == FilterResult.REMOVE)
prev.remove(); // Remove AFTER finding sibling.
}
// root == null?
return FilterResult.CONTINUE;
}
/**
* Start a depth-first filtering of all elements.
* @param filter Node filter.
* @param elements Elements to filter.
*/
public static void filter(NodeFilter filter, Elements elements) {
Validate.notNull(filter);
Validate.notNull(elements);
for (Element el : elements)
if (filter(filter, el) == FilterResult.STOP)
break;
}
}