001package org.jsoup.nodes;
002
003import org.jsoup.helper.Validate;
004import org.jspecify.annotations.Nullable;
005
006import java.util.Iterator;
007import java.util.NoSuchElementException;
008
009/**
010 Iterate through a Node and its tree of descendants, in document order, and returns nodes of the specified type. This
011 iterator supports structural changes to the tree during the traversal, such as {@link Node#remove()},
012 {@link Node#replaceWith(Node)}, {@link Node#wrap(String)}, etc.
013 <p>See also the {@link org.jsoup.select.NodeTraversor NodeTraversor} if {@code head} and {@code tail} callbacks are
014 desired for each node.</p>
015 @since 1.17.1
016 */
017public class NodeIterator<T extends Node> implements Iterator<T> {
018    private Node root;                      // root / starting node
019    private @Nullable T next;               // the next node to return
020    private Node current;                   // the current (last emitted) node
021    private Node previous;                  // the previously emitted node; used to recover from structural changes
022    private @Nullable Node currentParent;   // the current node's parent; used to detect structural changes
023    private final Class<T> type;            // the desired node class type
024
025    /**
026     Create a NoteIterator that will iterate the supplied node, and all of its descendants. The returned {@link #next}
027     type will be filtered to the input type.
028     * @param start initial node
029     * @param type node type to filter for
030     */
031    public NodeIterator(Node start, Class<T> type) {
032        Validate.notNull(start);
033        Validate.notNull(type);
034        this.type = type;
035
036        restart(start);
037    }
038
039    /**
040     Create a NoteIterator that will iterate the supplied node, and all of its descendants. All node types will be
041     returned.
042     * @param start initial node
043     */
044    public static NodeIterator<Node> from(Node start) {
045        return new NodeIterator<>(start, Node.class);
046    }
047
048    /**
049     Restart this Iterator from the specified start node. Will act as if it were newly constructed. Useful for e.g. to
050     save some GC if the iterator is used in a tight loop.
051     * @param start the new start node.
052     */
053    public void restart(Node start) {
054        if (type.isInstance(start))
055            next = type.cast(start); // first next() will be the start node
056
057        root = previous = current = start;
058        currentParent = current.parent();
059    }
060
061    @Override public boolean hasNext() {
062        maybeFindNext();
063        return next != null;
064    }
065
066    @Override public T next() {
067        maybeFindNext();
068        if (next == null) throw new NoSuchElementException();
069
070        T result = next;
071        previous = current;
072        current = next;
073        currentParent = current.parent();
074        next = null;
075        return result;
076    }
077
078    /**
079     If next is not null, looks for and sets next. If next is null after this, we have reached the end.
080     */
081    private void maybeFindNext() {
082        if (next != null) return;
083
084        //  change detected (removed or replaced), redo from previous
085        if (currentParent != null && !current.hasParent())
086            current = previous;
087
088        next = findNextNode();
089    }
090
091    private @Nullable T findNextNode() {
092        Node node = current;
093        while (true) {
094            if (node.childNodeSize() > 0)
095                node = node.childNode(0);                   // descend children
096            else if (root.equals(node))
097                node = null;                                // complete when all children of root are fully visited
098            else if (node.nextSibling() != null)
099                node = node.nextSibling();                  // in a descendant with no more children; traverse
100            else {
101                while (true) {
102                    node = node.parent();                   // pop out of descendants
103                    if (node == null || root.equals(node))
104                        return null;                        // got back to root; complete
105                    if (node.nextSibling() != null) {
106                        node = node.nextSibling();          // traverse
107                        break;
108                    }
109                }
110            }
111            if (node == null)
112                return null;                                // reached the end
113
114            if (type.isInstance(node))
115                return type.cast(node);
116        }
117    }
118
119    @Override public void remove() {
120        current.remove();
121    }
122}