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}