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