001/* Copyright (C) 2013 TU Dortmund 002 * This file is part of AutomataLib, http://www.automatalib.net/. 003 * 004 * AutomataLib is free software; you can redistribute it and/or 005 * modify it under the terms of the GNU Lesser General Public 006 * License version 3.0 as published by the Free Software Foundation. 007 * 008 * AutomataLib is distributed in the hope that it will be useful, 009 * but WITHOUT ANY WARRANTY; without even the implied warranty of 010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 011 * Lesser General Public License for more details. 012 * 013 * You should have received a copy of the GNU Lesser General Public 014 * License along with AutomataLib; if not, see 015 * http://www.gnu.de/documents/lgpl.en.html. 016 */ 017package net.automatalib.util.ts.traversal; 018 019import java.util.ArrayDeque; 020import java.util.Collection; 021import java.util.Iterator; 022import java.util.Queue; 023 024import net.automatalib.commons.util.mappings.MutableMapping; 025import net.automatalib.ts.simple.SimpleTS; 026import net.automatalib.util.traversal.VisitedState; 027 028 029public class BFSOrderIterator<S, I> implements Iterator<S> { 030 031 private final Collection<? extends I> inputs; 032 private final SimpleTS<S, I> ts; 033 private final Queue<S> bfsQueue = new ArrayDeque<S>(); 034 private final MutableMapping<S,VisitedState> seen; 035 036 public BFSOrderIterator(SimpleTS<S,I> ts, Collection<? extends I> inputs) { 037 this.ts = ts; 038 this.inputs = inputs; 039 Collection<? extends S> initial = ts.getInitialStates(); 040 bfsQueue.addAll(initial); 041 seen = ts.createStaticStateMapping(); 042 for(S state : initial) 043 seen.put(state, VisitedState.VISITED); 044 } 045 046 /* 047 * (non-Javadoc) 048 * @see java.util.Iterator#hasNext() 049 */ 050 @Override 051 public boolean hasNext() { 052 return !bfsQueue.isEmpty(); 053 } 054 055 /* 056 * (non-Javadoc) 057 * @see java.util.Iterator#next() 058 */ 059 @Override 060 public S next() { 061 S state = bfsQueue.poll(); 062 063 for(I input : inputs) { 064 Collection<S> succs = ts.getSuccessors(state, input); 065 if(succs != null) { 066 for(S succ : succs) { 067 if(seen.put(succ, VisitedState.VISITED) != VisitedState.VISITED) 068 bfsQueue.add(succ); 069 } 070 } 071 } 072 073 return state; 074 } 075 076 /* 077 * (non-Javadoc) 078 * @see java.util.Iterator#remove() 079 */ 080 @Override 081 public void remove() { 082 throw new UnsupportedOperationException(); 083 } 084 085}