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}