001package org.jsoup.select; 002 003import org.jsoup.helper.Validate; 004import org.jsoup.nodes.Element; 005import org.jsoup.nodes.Node; 006import org.jsoup.select.NodeFilter.FilterResult; 007 008/** 009 A depth-first node traversor. Use to walk through all nodes under and including the specified root node, in document 010 order. The {@link NodeVisitor#head(Node, int)} and {@link NodeVisitor#tail(Node, int)} methods will be called for 011 each node. 012 <p> During traversal, structural changes to nodes are supported (e.g. {{@link Node#replaceWith(Node)}, 013 {@link Node#remove()}} 014 </p> 015 */ 016public class NodeTraversor { 017 /** 018 Run a depth-first traverse of the root and all of its descendants. 019 @param visitor Node visitor. 020 @param root the initial node point to traverse. 021 @see NodeVisitor 022 */ 023 public static void traverse(NodeVisitor visitor, Node root) { 024 Validate.notNull(visitor); 025 Validate.notNull(root); 026 Node node = root; 027 int depth = 0; 028 029 while (node != null) { 030 Node parent = node.parentNode(); // remember parent to find nodes that get replaced in .head 031 int origSize = parent != null ? parent.childNodeSize() : 0; 032 Node next = node.nextSibling(); 033 034 visitor.head(node, depth); // visit current node 035 if (parent != null && !node.hasParent()) { // removed or replaced 036 if (origSize == parent.childNodeSize()) { // replaced 037 node = parent.childNode(node.siblingIndex()); // replace ditches parent but keeps sibling index 038 } else { // removed 039 node = next; 040 if (node == null) { // last one, go up 041 node = parent; 042 depth--; 043 } 044 continue; // don't tail removed 045 } 046 } 047 048 if (node.childNodeSize() > 0) { // descend 049 node = node.childNode(0); 050 depth++; 051 } else { 052 while (true) { 053 assert node != null; // as depth > 0, will have parent 054 if (!(node.nextSibling() == null && depth > 0)) break; 055 visitor.tail(node, depth); // when no more siblings, ascend 056 node = node.parentNode(); 057 depth--; 058 } 059 visitor.tail(node, depth); 060 if (node == root) 061 break; 062 node = node.nextSibling(); 063 } 064 } 065 } 066 067 /** 068 Run a depth-first traversal of each Element. 069 @param visitor Node visitor. 070 @param elements Elements to traverse. 071 */ 072 public static void traverse(NodeVisitor visitor, Elements elements) { 073 Validate.notNull(visitor); 074 Validate.notNull(elements); 075 for (Element el : elements) 076 traverse(visitor, el); 077 } 078 079 /** 080 Run a depth-first filtered traversal of the root and all of its descendants. 081 @param filter NodeFilter visitor. 082 @param root the root node point to traverse. 083 @return The filter result of the root node, or {@link FilterResult#STOP}. 084 085 @see NodeFilter 086 */ 087 public static FilterResult filter(NodeFilter filter, Node root) { 088 Node node = root; 089 int depth = 0; 090 091 while (node != null) { 092 FilterResult result = filter.head(node, depth); 093 if (result == FilterResult.STOP) 094 return result; 095 // Descend into child nodes: 096 if (result == FilterResult.CONTINUE && node.childNodeSize() > 0) { 097 node = node.childNode(0); 098 ++depth; 099 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 */ 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}