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 * Depth-first node traversor. Use to iterate through all nodes under and including the specified root node. 010 * <p> 011 * This implementation does not use recursion, so a deep DOM does not risk blowing the stack. 012 * </p> 013 */ 014public class NodeTraversor { 015 private NodeVisitor visitor; 016 017 /** 018 * Create a new traversor. 019 * @param visitor a class implementing the {@link NodeVisitor} interface, to be called when visiting each node. 020 * @deprecated Just use the static {@link NodeTraversor#filter(NodeFilter, Node)} method. 021 */ 022 public NodeTraversor(NodeVisitor visitor) { 023 this.visitor = visitor; 024 } 025 026 /** 027 * Start a depth-first traverse of the root and all of its descendants. 028 * @param root the root node point to traverse. 029 * @deprecated Just use the static {@link NodeTraversor#filter(NodeFilter, Node)} method. 030 */ 031 public void traverse(Node root) { 032 traverse(visitor, root); 033 } 034 035 /** 036 * Start a depth-first traverse of the root and all of its descendants. 037 * @param visitor Node visitor. 038 * @param root the root node point to traverse. 039 */ 040 public static void traverse(NodeVisitor visitor, Node root) { 041 Node node = root; 042 int depth = 0; 043 044 while (node != null) { 045 visitor.head(node, depth); 046 if (node.childNodeSize() > 0) { 047 node = node.childNode(0); 048 depth++; 049 } else { 050 while (node.nextSibling() == null && depth > 0) { 051 visitor.tail(node, depth); 052 node = node.parentNode(); 053 depth--; 054 } 055 visitor.tail(node, depth); 056 if (node == root) 057 break; 058 node = node.nextSibling(); 059 } 060 } 061 } 062 063 /** 064 * Start a depth-first traverse of all elements. 065 * @param visitor Node visitor. 066 * @param elements Elements to filter. 067 */ 068 public static void traverse(NodeVisitor visitor, Elements elements) { 069 Validate.notNull(visitor); 070 Validate.notNull(elements); 071 for (Element el : elements) 072 traverse(visitor, el); 073 } 074 075 /** 076 * Start a depth-first filtering of the root and all of its descendants. 077 * @param filter Node visitor. 078 * @param root the root node point to traverse. 079 * @return The filter result of the root node, or {@link FilterResult#STOP}. 080 */ 081 public static FilterResult filter(NodeFilter filter, Node root) { 082 Node node = root; 083 int depth = 0; 084 085 while (node != null) { 086 FilterResult result = filter.head(node, depth); 087 if (result == FilterResult.STOP) 088 return result; 089 // Descend into child nodes: 090 if (result == FilterResult.CONTINUE && node.childNodeSize() > 0) { 091 node = node.childNode(0); 092 ++depth; 093 continue; 094 } 095 // No siblings, move upwards: 096 while (node.nextSibling() == null && depth > 0) { 097 // 'tail' current node: 098 if (result == FilterResult.CONTINUE || result == FilterResult.SKIP_CHILDREN) { 099 result = filter.tail(node, depth); 100 if (result == FilterResult.STOP) 101 return result; 102 } 103 Node prev = node; // In case we need to remove it below. 104 node = node.parentNode(); 105 depth--; 106 if (result == FilterResult.REMOVE) 107 prev.remove(); // Remove AFTER finding parent. 108 result = FilterResult.CONTINUE; // Parent was not pruned. 109 } 110 // 'tail' current node, then proceed with siblings: 111 if (result == FilterResult.CONTINUE || result == FilterResult.SKIP_CHILDREN) { 112 result = filter.tail(node, depth); 113 if (result == FilterResult.STOP) 114 return result; 115 } 116 if (node == root) 117 return result; 118 Node prev = node; // In case we need to remove it below. 119 node = node.nextSibling(); 120 if (result == FilterResult.REMOVE) 121 prev.remove(); // Remove AFTER finding sibling. 122 } 123 // root == null? 124 return FilterResult.CONTINUE; 125 } 126 127 /** 128 * Start a depth-first filtering of all elements. 129 * @param filter Node filter. 130 * @param elements Elements to filter. 131 */ 132 public static void filter(NodeFilter filter, Elements elements) { 133 Validate.notNull(filter); 134 Validate.notNull(elements); 135 for (Element el : elements) 136 if (filter(filter, el) == FilterResult.STOP) 137 break; 138 } 139}