1 package org.jsoup.nodes; 2 3 import org.jsoup.helper.Validate; 4 import org.jspecify.annotations.Nullable; 5 6 import java.util.Iterator; 7 import java.util.NoSuchElementException; 8 9 /** 10 Iterate through a Node and its tree of descendants, in document order, and returns nodes of the specified type. This 11 iterator supports structural changes to the tree during the traversal, such as {@link Node#remove()}, 12 {@link Node#replaceWith(Node)}, {@link Node#wrap(String)}, etc. 13 <p>See also the {@link org.jsoup.select.NodeTraversor NodeTraversor} if {@code head} and {@code tail} callbacks are 14 desired for each node.</p> 15 @since 1.17.1 16 */ 17 public class NodeIterator<T extends Node> implements Iterator<T> { 18 private Node root; // root / starting node 19 private @Nullable T next; // the next node to return 20 private Node current; // the current (last emitted) node 21 private Node previous; // the previously emitted node; used to recover from structural changes 22 private @Nullable Node currentParent; // the current node's parent; used to detect structural changes 23 private final Class<T> type; // the desired node class type 24 25 /** 26 Create a NoteIterator that will iterate the supplied node, and all of its descendants. The returned {@link #next} 27 type will be filtered to the input type. 28 * @param start initial node 29 * @param type node type to filter for 30 */ NodeIterator(Node start, Class<T> type)31 public NodeIterator(Node start, Class<T> type) { 32 Validate.notNull(start); 33 Validate.notNull(type); 34 this.type = type; 35 36 restart(start); 37 } 38 39 /** 40 Create a NoteIterator that will iterate the supplied node, and all of its descendants. All node types will be 41 returned. 42 * @param start initial node 43 */ from(Node start)44 public static NodeIterator<Node> from(Node start) { 45 return new NodeIterator<>(start, Node.class); 46 } 47 48 /** 49 Restart this Iterator from the specified start node. Will act as if it were newly constructed. Useful for e.g. to 50 save some GC if the iterator is used in a tight loop. 51 * @param start the new start node. 52 */ restart(Node start)53 public void restart(Node start) { 54 if (type.isInstance(start)) 55 //noinspection unchecked 56 next = (T) start; // first next() will be the start node 57 58 root = previous = current = start; 59 currentParent = current.parent(); 60 } 61 hasNext()62 @Override public boolean hasNext() { 63 maybeFindNext(); 64 return next != null; 65 } 66 next()67 @Override public T next() { 68 maybeFindNext(); 69 if (next == null) throw new NoSuchElementException(); 70 71 T result = next; 72 previous = current; 73 current = next; 74 currentParent = current.parent(); 75 next = null; 76 return result; 77 } 78 79 /** 80 If next is not null, looks for and sets next. If next is null after this, we have reached the end. 81 */ maybeFindNext()82 private void maybeFindNext() { 83 if (next != null) return; 84 85 // change detected (removed or replaced), redo from previous 86 if (currentParent != null && !current.hasParent()) 87 current = previous; 88 89 next = findNextNode(); 90 } 91 findNextNode()92 private @Nullable T findNextNode() { 93 Node node = current; 94 while (true) { 95 if (node.childNodeSize() > 0) 96 node = node.childNode(0); // descend children 97 else if (root.equals(node)) 98 node = null; // complete when all children of root are fully visited 99 else if (node.nextSibling() != null) 100 node = node.nextSibling(); // in a descendant with no more children; traverse 101 else { 102 while (true) { 103 node = node.parent(); // pop out of descendants 104 if (node == null || root.equals(node)) 105 return null; // got back to root; complete 106 if (node.nextSibling() != null) { 107 node = node.nextSibling(); // traverse 108 break; 109 } 110 } 111 } 112 if (node == null) 113 return null; // reached the end 114 115 if (type.isInstance(node)) 116 //noinspection unchecked 117 return (T) node; 118 } 119 } 120 remove()121 @Override public void remove() { 122 current.remove(); 123 } 124 } 125