001package org.dllearner.algorithms.qtl.operations.traversal;
002
003import org.dllearner.algorithms.qtl.datastructures.impl.GenericTree;
004
005import java.util.*;
006
007/**
008 * An iterator for post-order resp. depth-first traversal on the nodes in the query tree.
009 *
010 * 1. Traverse the subtrees
011 * 2. Visit the root.
012 *
013 * @author Lorenz Buehmann
014 */
015public class PostOrderTreeTraversal2<V, T extends GenericTree<V, T>> extends AbstractTreeTraversal<T> {
016
017        private Deque<T> stack = new ArrayDeque<>();
018
019        public PostOrderTreeTraversal2(T root) {
020                super(root);
021                buildPostOrder(root, stack);
022        }
023
024        @Override
025        public boolean hasNext() {
026                return !stack.isEmpty();
027        }
028
029        @Override
030        public T next() {
031                if (!hasNext()) {
032                        throw new NoSuchElementException("All nodes have been visited!");
033                }
034
035                T res = stack.pop();
036
037                return res;
038        }
039
040        private void buildPostOrder(T node, Deque<T> postOrder) {
041                for (T child : node.getChildren()) {
042                        buildPostOrder(child, postOrder);
043                }
044                postOrder.add(node);
045        }
046}