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 level-order resp. breadth-first traversal on the nodes in the query tree.
012 * 
013 * @author Lorenz Buehmann
014 */
015public class LevelOrderTreeTraversal<V, T extends GenericTree<V, T>> extends AbstractTreeTraversal<T> {
016
017        private Deque<T> stack = new ArrayDeque<>();
018
019        public LevelOrderTreeTraversal(T root) {
020                super(root);
021                stack.push(root);
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                // retrieve and remove the head of queue
036                T res = stack.removeFirst();
037
038                // add children to stack
039                List<T> children = res.getChildren();
040                if(children != null) {
041                        stack.addAll(children);
042                }
043
044                return res;
045        }
046}