diff options
Diffstat (limited to 'javaparser-core/src/main/java/com/github/javaparser/ast/Node.java')
| -rw-r--r-- | javaparser-core/src/main/java/com/github/javaparser/ast/Node.java | 1004 |
1 files changed, 1004 insertions, 0 deletions
diff --git a/javaparser-core/src/main/java/com/github/javaparser/ast/Node.java b/javaparser-core/src/main/java/com/github/javaparser/ast/Node.java new file mode 100644 index 000000000..98d0bbcb6 --- /dev/null +++ b/javaparser-core/src/main/java/com/github/javaparser/ast/Node.java @@ -0,0 +1,1004 @@ +/* + * Copyright (C) 2007-2010 Júlio Vilmar Gesser. + * Copyright (C) 2011, 2013-2016 The JavaParser Team. + * + * This file is part of JavaParser. + * + * JavaParser can be used either under the terms of + * a) the GNU Lesser General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * b) the terms of the Apache License + * + * You should have received a copy of both licenses in LICENCE.LGPL and + * LICENCE.APACHE. Please refer to those files for details. + * + * JavaParser is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + */ +package com.github.javaparser.ast; + +import com.github.javaparser.HasParentNode; +import com.github.javaparser.Range; +import com.github.javaparser.TokenRange; +import com.github.javaparser.ast.comments.BlockComment; +import com.github.javaparser.ast.comments.Comment; +import com.github.javaparser.ast.comments.LineComment; +import com.github.javaparser.ast.nodeTypes.NodeWithRange; +import com.github.javaparser.ast.nodeTypes.NodeWithTokenRange; +import com.github.javaparser.ast.observer.AstObserver; +import com.github.javaparser.ast.observer.ObservableProperty; +import com.github.javaparser.ast.observer.PropagatingAstObserver; +import com.github.javaparser.ast.visitor.CloneVisitor; +import com.github.javaparser.ast.visitor.EqualsVisitor; +import com.github.javaparser.ast.visitor.HashCodeVisitor; +import com.github.javaparser.ast.visitor.Visitable; +import com.github.javaparser.metamodel.*; +import com.github.javaparser.printer.PrettyPrinter; +import com.github.javaparser.printer.PrettyPrinterConfiguration; +import com.github.javaparser.resolution.SymbolResolver; +import javax.annotation.Generated; +import java.util.*; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Predicate; +import java.util.stream.Stream; +import java.util.stream.StreamSupport; +import static com.github.javaparser.ast.Node.Parsedness.PARSED; +import static com.github.javaparser.ast.Node.TreeTraversal.PREORDER; +import static java.util.Collections.unmodifiableList; +import static java.util.Spliterator.DISTINCT; +import static java.util.Spliterator.NONNULL; +import com.github.javaparser.ast.Node; +import com.github.javaparser.metamodel.NodeMetaModel; +import com.github.javaparser.metamodel.JavaParserMetaModel; + +/** + * Base class for all nodes of the abstract syntax tree. + * <h2>Construction</h2> + * <p>The tree is built by instantiating the required nodes, then adding them to other nodes. + * If it is the parser who is building the tree, it will use the largest constructor, + * the one with "range" as the first parameter. + * If you want to manually instantiate nodes, we suggest to... + * <ul> + * <li>use a convenience method, like "addStatement(...)", or if none are available...</li> + * <li>use a convenient constructor, like ClassOrInterfaceType(String name), or if none are available...</li> + * <li>use the default constructor.</li> + * <li>Alternatively, use one of the JavaParser.parse(snippet) methods.</li> + * </ul> + * ... and use the various methods on the node to initialize it further, if needed. + * <h2>Parent/child</h2> + * <p>The parent node field is managed automatically and can be seen as read only. + * Note that there is only one parent, + * and trying to use the same node in two places will lead to unexpected behaviour. + * It is advised to clone() a node before moving it around. + * <h2>Comments</h2> + * <p>Each Node can have one associated comment which describes it and + * a number of "orphan comments" which it contains but are not specifically + * associated to any child. + * <h2>Positions</h2> + * <p>When the parser creates nodes, it sets their source code position in the "range" field. + * When you manually instantiate nodes, their range is not set. + * The top left character is position 1, 1. + * Note that since this is an <i>abstract</i> syntax tree, + * it leaves out a lot of text from the original source file, + * like where braces or comma's are exactly. + * Therefore there is no position information on everything in the original source file. + * <h2>Observers</h2> + * <p>It is possible to add observers to the the tree. + * Any change in the tree is sent as an event to any observers watching. + * <h2>Visitors</h2> + * <p>The most comfortable way of working with an abstract syntax tree is using visitors. + * You can use one of the visitors in the visitor package, or extend one of them. + * A visitor can be "run" by calling accept on a node: + * <pre>node.accept(visitor, argument);</pre> + * where argument is an object of your choice (often simply null.) + * + * @author Julio Vilmar Gesser + */ +public abstract class Node implements Cloneable, HasParentNode<Node>, Visitable, NodeWithRange<Node>, NodeWithTokenRange<Node> { + + /** + * Different registration mode for observers on nodes. + */ + public enum ObserverRegistrationMode { + + /** + * Notify exclusively for changes happening on this node alone. + */ + JUST_THIS_NODE, + /** + * Notify for changes happening on this node and all its descendants existing at the moment in + * which the observer was registered. Nodes attached later will not be observed. + */ + THIS_NODE_AND_EXISTING_DESCENDANTS, + /** + * Notify for changes happening on this node and all its descendants. The descendants existing at the moment in + * which the observer was registered will be observed immediately. As new nodes are attached later they are + * automatically registered to be observed. + */ + SELF_PROPAGATING + } + + public enum Parsedness { + + PARSED, UNPARSABLE + } + + /** + * This can be used to sort nodes on position. + */ + public static Comparator<NodeWithRange<?>> NODE_BY_BEGIN_POSITION = (a, b) -> { + if (a.getRange().isPresent() && b.getRange().isPresent()) { + return a.getRange().get().begin.compareTo(b.getRange().get().begin); + } + if (a.getRange().isPresent() || b.getRange().isPresent()) { + if (a.getRange().isPresent()) { + return 1; + } + return -1; + } + return 0; + }; + + private static final PrettyPrinter toStringPrinter = new PrettyPrinter(new PrettyPrinterConfiguration()); + + protected static final PrettyPrinterConfiguration prettyPrinterNoCommentsConfiguration = new PrettyPrinterConfiguration().setPrintComments(false); + + @InternalProperty + private Range range; + + @InternalProperty + private TokenRange tokenRange; + + @InternalProperty + private Node parentNode; + + @InternalProperty + private List<Node> childNodes = new LinkedList<>(); + + @InternalProperty + private List<Comment> orphanComments = new LinkedList<>(); + + @InternalProperty + private IdentityHashMap<DataKey<?>, Object> data = null; + + @OptionalProperty + private Comment comment; + + @InternalProperty + private List<AstObserver> observers = new ArrayList<>(); + + @InternalProperty + private Parsedness parsed = PARSED; + + protected Node(TokenRange tokenRange) { + setTokenRange(tokenRange); + } + + /** + * Called in every constructor for node specific code. + * It can't be written in the constructor itself because it will + * be overwritten during code generation. + */ + protected void customInitialization() { + } + + /** + * This is a comment associated with this node. + * + * @return comment property + */ + @Generated("com.github.javaparser.generator.core.node.PropertyGenerator") + public Optional<Comment> getComment() { + return Optional.ofNullable(comment); + } + + /** + * @return the range of characters in the source code that this node covers. + */ + public Optional<Range> getRange() { + return Optional.ofNullable(range); + } + + /** + * @return the range of tokens that this node covers. + */ + public Optional<TokenRange> getTokenRange() { + return Optional.ofNullable(tokenRange); + } + + public Node setTokenRange(TokenRange tokenRange) { + this.tokenRange = tokenRange; + if (tokenRange == null || !(tokenRange.getBegin().getRange().isPresent() && tokenRange.getBegin().getRange().isPresent())) { + range = null; + } else { + range = new Range(tokenRange.getBegin().getRange().get().begin, tokenRange.getEnd().getRange().get().end); + } + return this; + } + + /** + * @param range the range of characters in the source code that this node covers. null can be used to indicate that + * no range information is known, or that it is not of interest. + */ + public Node setRange(Range range) { + if (this.range == range) { + return this; + } + notifyPropertyChange(ObservableProperty.RANGE, this.range, range); + this.range = range; + return this; + } + + /** + * Use this to store additional information to this node. + * + * @param comment to be set + */ + public final Node setComment(final Comment comment) { + if (this.comment == comment) { + return this; + } + if (comment != null && (this instanceof Comment)) { + throw new RuntimeException("A comment can not be commented"); + } + notifyPropertyChange(ObservableProperty.COMMENT, this.comment, comment); + if (this.comment != null) { + this.comment.setCommentedNode(null); + } + this.comment = comment; + if (comment != null) { + this.comment.setCommentedNode(this); + } + return this; + } + + /** + * Use this to store additional information to this node. + * + * @param comment to be set + */ + public final Node setLineComment(String comment) { + return setComment(new LineComment(comment)); + } + + /** + * Use this to store additional information to this node. + * + * @param comment to be set + */ + public final Node setBlockComment(String comment) { + return setComment(new BlockComment(comment)); + } + + /** + * Return the String representation of this node. + * + * @return the String representation of this node + */ + @Override + public final String toString() { + return toStringPrinter.print(this); + } + + public final String toString(PrettyPrinterConfiguration prettyPrinterConfiguration) { + return new PrettyPrinter(prettyPrinterConfiguration).print(this); + } + + @Override + public final int hashCode() { + return HashCodeVisitor.hashCode(this); + } + + @Override + public boolean equals(final Object obj) { + if (obj == null || !(obj instanceof Node)) { + return false; + } + return EqualsVisitor.equals(this, (Node) obj); + } + + @Override + public Optional<Node> getParentNode() { + return Optional.ofNullable(parentNode); + } + + /** + * Contains all nodes that have this node set as their parent. + * You can add and remove nodes from this list by adding or removing nodes from the fields of this node. + * + * @return all nodes that have this node as their parent. + */ + public List<Node> getChildNodes() { + return unmodifiableList(childNodes); + } + + public void addOrphanComment(Comment comment) { + orphanComments.add(comment); + comment.setParentNode(this); + } + + public boolean removeOrphanComment(Comment comment) { + boolean removed = orphanComments.remove(comment); + if (removed) { + comment.setParentNode(null); + } + return removed; + } + + /** + * This is a list of Comment which are inside the node and are not associated + * with any meaningful AST Node. + * <p> + * For example, comments at the end of methods (immediately before the parenthesis) + * or at the end of CompilationUnit are orphan comments. + * <p> + * When more than one comment preceeds a statement, the one immediately preceding it + * it is associated with the statements, while the others are orphans. + * <p> + * Changes to this list are not persisted. + * + * @return all comments that cannot be attributed to a concept + */ + public List<Comment> getOrphanComments() { + return new LinkedList<>(orphanComments); + } + + /** + * This is the list of Comment which are contained in the Node either because + * they are properly associated to one of its children or because they are floating + * around inside the Node + * + * @return all Comments within the node as a list + */ + public List<Comment> getAllContainedComments() { + List<Comment> comments = new LinkedList<>(); + comments.addAll(getOrphanComments()); + for (Node child : getChildNodes()) { + child.getComment().ifPresent(comments::add); + comments.addAll(child.getAllContainedComments()); + } + return comments; + } + + /** + * Assign a new parent to this node, removing it + * from the list of children of the previous parent, if any. + * + * @param newParentNode node to be set as parent + */ + @Override + public Node setParentNode(Node newParentNode) { + if (newParentNode == parentNode) { + return this; + } + observers.forEach(o -> o.parentChange(this, parentNode, newParentNode)); + // remove from old parent, if any + if (parentNode != null) { + final List<Node> parentChildNodes = parentNode.childNodes; + for (int i = 0; i < parentChildNodes.size(); i++) { + if (parentChildNodes.get(i) == this) { + parentChildNodes.remove(i); + } + } + } + parentNode = newParentNode; + // add to new parent, if any + if (parentNode != null) { + parentNode.childNodes.add(this); + } + return this; + } + + protected void setAsParentNodeOf(Node childNode) { + if (childNode != null) { + childNode.setParentNode(getParentNodeForChildren()); + } + } + + public static final int ABSOLUTE_BEGIN_LINE = -1; + + public static final int ABSOLUTE_END_LINE = -2; + + /** + * @deprecated use getComment().isPresent() + */ + @Deprecated + public boolean hasComment() { + return comment != null; + } + + public void tryAddImportToParentCompilationUnit(Class<?> clazz) { + getAncestorOfType(CompilationUnit.class).ifPresent(p -> p.addImport(clazz)); + } + + /** + * Recursively finds all nodes of a certain type. + * + * @param clazz the type of node to find. + * @deprecated use find(Class) + */ + public <N extends Node> List<N> getChildNodesByType(Class<N> clazz) { + List<N> nodes = new ArrayList<>(); + for (Node child : getChildNodes()) { + if (clazz.isInstance(child)) { + nodes.add(clazz.cast(child)); + } + nodes.addAll(child.getChildNodesByType(clazz)); + } + return nodes; + } + + /** + * @deprecated use findAll(Class) + */ + @Deprecated + public <N extends Node> List<N> getNodesByType(Class<N> clazz) { + return getChildNodesByType(clazz); + } + + /** + * Gets data for this node using the given key. + * + * @param <M> The type of the data. + * @param key The key for the data + * @return The data or null of no data was found for the given key + * @see DataKey + */ + @SuppressWarnings("unchecked") + public <M> M getData(final DataKey<M> key) { + if (data == null) { + return null; + } + return (M) data.get(key); + } + + /** + * Sets data for this node using the given key. + * For information on creating DataKey, see {@link DataKey}. + * + * @param <M> The type of data + * @param key The singleton key for the data + * @param object The data object + * @see DataKey + */ + public <M> void setData(DataKey<M> key, M object) { + if (data == null) { + data = new IdentityHashMap<>(); + } + data.put(key, object); + } + + /** + * @return does this node have data for this key? + */ + public boolean containsData(DataKey<?> key) { + if (data == null) { + return false; + } + return data.get(key) != null; + } + + /** + * Try to remove this node from the parent + * + * @return true if removed, false if it is a required property of the parent, or if the parent isn't set. + * @throws RuntimeException if it fails in an unexpected way + */ + public boolean remove() { + if (parentNode == null) { + return false; + } + return parentNode.remove(this); + } + + /** + * Try to replace this node in the parent with the supplied node. + * + * @return true if removed, or if the parent isn't set. + * @throws RuntimeException if it fails in an unexpected way + */ + public boolean replace(Node node) { + if (parentNode == null) { + return false; + } + return parentNode.replace(this, node); + } + + /** + * Forcibly removes this node from the AST. + * If it cannot be removed from the parent with remove(), + * it will try to remove its parent instead, + * until it finds a node that can be removed, + * or no parent can be found. + * <p> + * Since everything at CompilationUnit level is removable, + * this method will only (silently) fail when the node is in a detached AST fragment. + */ + public void removeForced() { + if (!remove()) { + getParentNode().ifPresent(Node::remove); + } + } + + @Override + public Node getParentNodeForChildren() { + return this; + } + + protected void setAsParentNodeOf(NodeList<? extends Node> list) { + if (list != null) { + list.setParentNode(getParentNodeForChildren()); + } + } + + public <P> void notifyPropertyChange(ObservableProperty property, P oldValue, P newValue) { + this.observers.forEach(o -> o.propertyChange(this, property, oldValue, newValue)); + } + + @Override + public void unregister(AstObserver observer) { + this.observers.remove(observer); + } + + @Override + public void register(AstObserver observer) { + this.observers.add(observer); + } + + /** + * Register a new observer for the given node. Depending on the mode specified also descendants, existing + * and new, could be observed. For more details see <i>ObserverRegistrationMode</i>. + */ + public void register(AstObserver observer, ObserverRegistrationMode mode) { + if (mode == null) { + throw new IllegalArgumentException("Mode should be not null"); + } + switch(mode) { + case JUST_THIS_NODE: + register(observer); + break; + case THIS_NODE_AND_EXISTING_DESCENDANTS: + registerForSubtree(observer); + break; + case SELF_PROPAGATING: + registerForSubtree(PropagatingAstObserver.transformInPropagatingObserver(observer)); + break; + default: + throw new UnsupportedOperationException("This mode is not supported: " + mode); + } + } + + /** + * Register the observer for the current node and all the contained node and nodelists, recursively. + */ + public void registerForSubtree(AstObserver observer) { + register(observer); + this.getChildNodes().forEach(c -> c.registerForSubtree(observer)); + for (PropertyMetaModel property : getMetaModel().getAllPropertyMetaModels()) { + if (property.isNodeList()) { + NodeList<?> nodeList = (NodeList<?>) property.getValue(this); + if (nodeList != null) + nodeList.register(observer); + } + } + } + + @Override + public boolean isRegistered(AstObserver observer) { + return this.observers.contains(observer); + } + + @Generated("com.github.javaparser.generator.core.node.RemoveMethodGenerator") + public boolean remove(Node node) { + if (node == null) + return false; + if (comment != null) { + if (node == comment) { + removeComment(); + return true; + } + } + return false; + } + + @Generated("com.github.javaparser.generator.core.node.RemoveMethodGenerator") + public Node removeComment() { + return setComment((Comment) null); + } + + @Override + @Generated("com.github.javaparser.generator.core.node.CloneGenerator") + public Node clone() { + return (Node) accept(new CloneVisitor(), null); + } + + /** + * @return get JavaParser specific node introspection information. + */ + @Generated("com.github.javaparser.generator.core.node.GetMetaModelGenerator") + public NodeMetaModel getMetaModel() { + return JavaParserMetaModel.nodeMetaModel; + } + + /** + * @return whether this node was successfully parsed or not. + * If it was not, only the range and tokenRange fields will be valid. + */ + public Parsedness getParsed() { + return parsed; + } + + /** + * Used by the parser to flag unparsable nodes. + */ + public Node setParsed(Parsedness parsed) { + this.parsed = parsed; + return this; + } + + @Generated("com.github.javaparser.generator.core.node.ReplaceMethodGenerator") + public boolean replace(Node node, Node replacementNode) { + if (node == null) + return false; + if (comment != null) { + if (node == comment) { + setComment((Comment) replacementNode); + return true; + } + } + return false; + } + + /** + * Finds the root node of this AST by finding the topmost parent. + */ + public Node findRootNode() { + Node n = this; + while (n.getParentNode().isPresent()) { + n = n.getParentNode().get(); + } + return n; + } + + /** + * @return the containing CompilationUnit, or empty if this node is not inside a compilation unit. + */ + public Optional<CompilationUnit> findCompilationUnit() { + Node rootNode = findRootNode(); + if (rootNode instanceof CompilationUnit) { + return Optional.of((CompilationUnit) rootNode); + } + return Optional.empty(); + } + + protected SymbolResolver getSymbolResolver() { + return findCompilationUnit().map(cu -> { + SymbolResolver symbolResolver = cu.getData(SYMBOL_RESOLVER_KEY); + if (symbolResolver == null) { + throw new IllegalStateException("Symbol resolution not configured: to configure consider setting a SymbolResolver in the ParserConfiguration"); + } + return symbolResolver; + }).orElseThrow(() -> new IllegalStateException("The node is not inserted in a CompilationUnit")); + } + + // We need to expose it because we will need to use it to inject the SymbolSolver + public static final DataKey<SymbolResolver> SYMBOL_RESOLVER_KEY = new DataKey<SymbolResolver>() { + }; + + public enum TreeTraversal { + + PREORDER, BREADTHFIRST, POSTORDER, PARENTS, DIRECT_CHILDREN + } + + private Iterator<Node> treeIterator(TreeTraversal traversal) { + switch(traversal) { + case BREADTHFIRST: + return new BreadthFirstIterator(this); + case POSTORDER: + return new PostOrderIterator(this); + case PREORDER: + return new PreOrderIterator(this); + case DIRECT_CHILDREN: + return new DirectChildrenIterator(this); + case PARENTS: + return new ParentsVisitor(this); + default: + throw new IllegalArgumentException("Unknown traversal choice."); + } + } + + private Iterable<Node> treeIterable(TreeTraversal traversal) { + return () -> treeIterator(traversal); + } + + /** + * Make a stream of nodes using traversal algorithm "traversal". + */ + public Stream<Node> stream(TreeTraversal traversal) { + return StreamSupport.stream(Spliterators.spliteratorUnknownSize(treeIterator(traversal), NONNULL | DISTINCT), false); + } + + /** + * Make a stream of nodes using pre-order traversal. + */ + public Stream<Node> stream() { + return StreamSupport.stream(Spliterators.spliteratorUnknownSize(treeIterator(PREORDER), NONNULL | DISTINCT), false); + } + + /** + * Walks the AST, calling the consumer for every node, with traversal algorithm "traversal". + * <br/>This is the most general walk method. All other walk and findAll methods are based on this. + */ + public void walk(TreeTraversal traversal, Consumer<Node> consumer) { + // Could be implemented as a call to the above walk method, but this is a little more efficient. + for (Node node : treeIterable(traversal)) { + consumer.accept(node); + } + } + + /** + * Walks the AST, calling the consumer for every node with pre-order traversal. + */ + public void walk(Consumer<Node> consumer) { + walk(PREORDER, consumer); + } + + /** + * Walks the AST with pre-order traversal, calling the consumer for every node of type "nodeType". + */ + public <T extends Node> void walk(Class<T> nodeType, Consumer<T> consumer) { + walk(TreeTraversal.PREORDER, node -> { + if (nodeType.isAssignableFrom(node.getClass())) { + consumer.accept(nodeType.cast(node)); + } + }); + } + + /** + * Walks the AST with pre-order traversal, returning all nodes of type "nodeType". + */ + public <T extends Node> List<T> findAll(Class<T> nodeType) { + final List<T> found = new ArrayList<>(); + walk(nodeType, found::add); + return found; + } + + /** + * Walks the AST with pre-order traversal, returning all nodes of type "nodeType" that match the predicate. + */ + public <T extends Node> List<T> findAll(Class<T> nodeType, Predicate<T> predicate) { + final List<T> found = new ArrayList<>(); + walk(nodeType, n -> { + if (predicate.test(n)) + found.add(n); + }); + return found; + } + + /** + * Walks the AST, applying the function for every node, with traversal algorithm "traversal". If the function + * returns something else than null, the traversal is stopped and the function result is returned. <br/>This is the + * most general findFirst method. All other findFirst methods are based on this. + */ + public <T> Optional<T> findFirst(TreeTraversal traversal, Function<Node, Optional<T>> consumer) { + for (Node node : treeIterable(traversal)) { + final Optional<T> result = consumer.apply(node); + if (result.isPresent()) { + return result; + } + } + return Optional.empty(); + } + + /** + * Walks the AST with pre-order traversal, returning the first node of type "nodeType" or empty() if none is found. + */ + public <N extends Node> Optional<N> findFirst(Class<N> nodeType) { + return findFirst(TreeTraversal.PREORDER, node -> { + if (nodeType.isAssignableFrom(node.getClass())) { + return Optional.of(nodeType.cast(node)); + } + return Optional.empty(); + }); + } + + /** + * Walks the AST with pre-order traversal, returning the first node of type "nodeType" that matches "predicate" or empty() if none is + * found. + */ + public <N extends Node> Optional<N> findFirst(Class<N> nodeType, Predicate<N> predicate) { + return findFirst(TreeTraversal.PREORDER, node -> { + if (nodeType.isAssignableFrom(node.getClass())) { + final N castNode = nodeType.cast(node); + if (predicate.test(castNode)) { + return Optional.of(castNode); + } + } + return Optional.empty(); + }); + } + + /** + * Walks the parents of this node, returning the first node of type "nodeType" or empty() if none is found. + */ + public <N extends Node> Optional<N> findParent(Class<N> nodeType) { + Node n = this; + while (n.getParentNode().isPresent()) { + n = n.getParentNode().get(); + if (nodeType.isAssignableFrom(n.getClass())) { + return Optional.of(nodeType.cast(n)); + } + } + return Optional.empty(); + } + + /** + * Performs a breadth-first node traversal starting with a given node. + * + * @see <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Breadth-first traversal</a> + */ + public static class BreadthFirstIterator implements Iterator<Node> { + + private final Queue<Node> queue = new LinkedList<>(); + + public BreadthFirstIterator(Node node) { + queue.add(node); + } + + @Override + public boolean hasNext() { + return !queue.isEmpty(); + } + + @Override + public Node next() { + Node next = queue.remove(); + queue.addAll(next.getChildNodes()); + return next; + } + } + + /** + * Performs a simple traversal over all nodes that have the passed node as their parent. + */ + public static class DirectChildrenIterator implements Iterator<Node> { + + private final Iterator<Node> childrenIterator; + + public DirectChildrenIterator(Node node) { + childrenIterator = new ArrayList<>(node.getChildNodes()).iterator(); + } + + @Override + public boolean hasNext() { + return childrenIterator.hasNext(); + } + + @Override + public Node next() { + return childrenIterator.next(); + } + } + + /** + * Iterates over the parent of the node, then the parent's parent, then the parent's parent's parent, until running + * out of parents. + */ + public static class ParentsVisitor implements Iterator<Node> { + + private Node node; + + public ParentsVisitor(Node node) { + this.node = node; + } + + @Override + public boolean hasNext() { + return node.getParentNode().isPresent(); + } + + @Override + public Node next() { + node = node.getParentNode().orElse(null); + return node; + } + } + + /** + * Performs a pre-order (or depth-first) node traversal starting with a given node. + * + * @see <a href="https://en.wikipedia.org/wiki/Pre-order">Pre-order traversal</a> + */ + public static class PreOrderIterator implements Iterator<Node> { + + private final Stack<Node> stack = new Stack<>(); + + public PreOrderIterator(Node node) { + stack.add(node); + } + + @Override + public boolean hasNext() { + return !stack.isEmpty(); + } + + @Override + public Node next() { + Node next = stack.pop(); + List<Node> children = next.getChildNodes(); + for (int i = children.size() - 1; i >= 0; i--) { + stack.add(children.get(i)); + } + return next; + } + } + + /** + * Performs a post-order (or leaves-first) node traversal starting with a given node. + * + * @see <a href="https://en.wikipedia.org/wiki/Post-order">Post-order traversal</a> + */ + public static class PostOrderIterator implements Iterator<Node> { + + private final Stack<List<Node>> nodesStack = new Stack<>(); + + private final Stack<Integer> cursorStack = new Stack<>(); + + private final Node root; + + private boolean hasNext = true; + + public PostOrderIterator(Node root) { + this.root = root; + fillStackToLeaf(root); + } + + private void fillStackToLeaf(Node node) { + while (true) { + List<Node> childNodes = new ArrayList<>(node.getChildNodes()); + if (childNodes.isEmpty()) { + break; + } + nodesStack.push(childNodes); + cursorStack.push(0); + node = childNodes.get(0); + } + } + + @Override + public boolean hasNext() { + return hasNext; + } + + @Override + public Node next() { + final List<Node> nodes = nodesStack.peek(); + final int cursor = cursorStack.peek(); + final boolean levelHasNext = cursor < nodes.size(); + if (levelHasNext) { + Node node = nodes.get(cursor); + fillStackToLeaf(node); + return nextFromLevel(); + } else { + nodesStack.pop(); + cursorStack.pop(); + hasNext = !nodesStack.empty(); + if (hasNext) { + return nextFromLevel(); + } + return root; + } + } + + private Node nextFromLevel() { + final List<Node> nodes = nodesStack.peek(); + final int cursor = cursorStack.pop(); + cursorStack.push(cursor + 1); + return nodes.get(cursor); + } + } +} |