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}