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}