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}