001package org.dllearner.algorithms.qtl.operations.traversal;
002
003import org.dllearner.algorithms.qtl.datastructures.impl.GenericTree;
004
005import java.util.ArrayDeque;
006import java.util.Deque;
007import java.util.List;
008import java.util.NoSuchElementException;
009
010/**
011 * An iterator for post-order resp. depth-first traversal on the nodes in the query tree.
012 *
013 * 1. Traverse the subtrees
014 * 2. Visit the root.
015 *
016 * @author Lorenz Buehmann
017 */
018public class PostOrderTreeTraversal<V, T extends GenericTree<V, T>> extends AbstractTreeTraversal<T> {
019
020        private Deque<T> stack = new ArrayDeque<>();
021
022        public PostOrderTreeTraversal(T root) {
023                super(root);
024                findNextLeaf(root);
025        }
026
027        @Override
028        public boolean hasNext() {
029                return !stack.isEmpty();
030        }
031
032        @Override
033        public T next() {
034                if (!hasNext()) {
035                        throw new NoSuchElementException("All nodes have been visited!");
036                }
037
038                T res = stack.pop();
039                if (!stack.isEmpty()) {
040                        T top = stack.peek();
041                        List<T> children = top.getChildren();
042                        int pos = children.indexOf(res);
043                        if (pos < children.size() - 1) {
044                                findNextLeaf(children.get(pos + 1)); // find next leaf in right sub-tree
045                        }
046                }
047
048                return res;
049        }
050
051        /** find the first leaf in a tree rooted at cur and store intermediate nodes */
052        private void findNextLeaf(T cur) {
053                while (cur != null) {
054                        stack.push(cur);
055                        List<T> children = cur.getChildren();
056                        if(!children.isEmpty()) {
057                                cur = children.get(0);
058                        }
059                }
060        }
061}