1 package org.jsoup.select; 2 3 import org.jsoup.helper.Validate; 4 import org.jsoup.nodes.Element; 5 import org.jsoup.nodes.Node; 6 import org.jsoup.select.NodeFilter.FilterResult; 7 8 /** 9 A depth-first node traversor. Use to walk through all nodes under and including the specified root node, in document 10 order. The {@link NodeVisitor#head(Node, int)} and {@link NodeVisitor#tail(Node, int)} methods will be called for 11 each node. 12 <p> During traversal, structural changes to nodes are supported (e.g. {{@link Node#replaceWith(Node)}, 13 {@link Node#remove()}} 14 </p> 15 */ 16 public class NodeTraversor { 17 /** 18 Run a depth-first traverse of the root and all of its descendants. 19 @param visitor Node visitor. 20 @param root the initial node point to traverse. 21 @see NodeVisitor 22 */ traverse(NodeVisitor visitor, Node root)23 public static void traverse(NodeVisitor visitor, Node root) { 24 Validate.notNull(visitor); 25 Validate.notNull(root); 26 Node node = root; 27 int depth = 0; 28 29 while (node != null) { 30 Node parent = node.parentNode(); // remember parent to find nodes that get replaced in .head 31 int origSize = parent != null ? parent.childNodeSize() : 0; 32 Node next = node.nextSibling(); 33 34 visitor.head(node, depth); // visit current node 35 if (parent != null && !node.hasParent()) { // removed or replaced 36 if (origSize == parent.childNodeSize()) { // replaced 37 node = parent.childNode(node.siblingIndex()); // replace ditches parent but keeps sibling index 38 } else { // removed 39 node = next; 40 if (node == null) { // last one, go up 41 node = parent; 42 depth--; 43 } 44 continue; // don't tail removed 45 } 46 } 47 48 if (node.childNodeSize() > 0) { // descend 49 node = node.childNode(0); 50 depth++; 51 } else { 52 while (true) { 53 assert node != null; // as depth > 0, will have parent 54 if (!(node.nextSibling() == null && depth > 0)) break; 55 visitor.tail(node, depth); // when no more siblings, ascend 56 node = node.parentNode(); 57 depth--; 58 } 59 visitor.tail(node, depth); 60 if (node == root) 61 break; 62 node = node.nextSibling(); 63 } 64 } 65 } 66 67 /** 68 Run a depth-first traversal of each Element. 69 @param visitor Node visitor. 70 @param elements Elements to traverse. 71 */ traverse(NodeVisitor visitor, Elements elements)72 public static void traverse(NodeVisitor visitor, Elements elements) { 73 Validate.notNull(visitor); 74 Validate.notNull(elements); 75 for (Element el : elements) 76 traverse(visitor, el); 77 } 78 79 /** 80 Run a depth-first filtered traversal of the root and all of its descendants. 81 @param filter NodeFilter visitor. 82 @param root the root node point to traverse. 83 @return The filter result of the root node, or {@link FilterResult#STOP}. 84 85 @see NodeFilter 86 */ filter(NodeFilter filter, Node root)87 public static FilterResult filter(NodeFilter filter, Node root) { 88 Node node = root; 89 int depth = 0; 90 91 while (node != null) { 92 FilterResult result = filter.head(node, depth); 93 if (result == FilterResult.STOP) 94 return result; 95 // Descend into child nodes: 96 if (result == FilterResult.CONTINUE && node.childNodeSize() > 0) { 97 node = node.childNode(0); 98 ++depth; 99 continue; 100 } 101 // No siblings, move upwards: 102 while (true) { 103 assert node != null; // depth > 0, so has parent 104 if (!(node.nextSibling() == null && depth > 0)) break; 105 // 'tail' current node: 106 if (result == FilterResult.CONTINUE || result == FilterResult.SKIP_CHILDREN) { 107 result = filter.tail(node, depth); 108 if (result == FilterResult.STOP) 109 return result; 110 } 111 Node prev = node; // In case we need to remove it below. 112 node = node.parentNode(); 113 depth--; 114 if (result == FilterResult.REMOVE) 115 prev.remove(); // Remove AFTER finding parent. 116 result = FilterResult.CONTINUE; // Parent was not pruned. 117 } 118 // 'tail' current node, then proceed with siblings: 119 if (result == FilterResult.CONTINUE || result == FilterResult.SKIP_CHILDREN) { 120 result = filter.tail(node, depth); 121 if (result == FilterResult.STOP) 122 return result; 123 } 124 if (node == root) 125 return result; 126 Node prev = node; // In case we need to remove it below. 127 node = node.nextSibling(); 128 if (result == FilterResult.REMOVE) 129 prev.remove(); // Remove AFTER finding sibling. 130 } 131 // root == null? 132 return FilterResult.CONTINUE; 133 } 134 135 /** 136 Run a depth-first filtered traversal of each Element. 137 @param filter NodeFilter visitor. 138 @see NodeFilter 139 */ filter(NodeFilter filter, Elements elements)140 public static void filter(NodeFilter filter, Elements elements) { 141 Validate.notNull(filter); 142 Validate.notNull(elements); 143 for (Element el : elements) 144 if (filter(filter, el) == FilterResult.STOP) 145 break; 146 } 147 } 148