001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of LearnLib, http://www.learnlib.de/.
003 * 
004 * LearnLib 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 * LearnLib 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 LearnLib; if not, see
015 * <http://www.gnu.de/documents/lgpl.en.html>.
016 */
017package de.learnlib.algorithms.lstargeneric;
018
019import java.util.ArrayList;
020
021import net.automatalib.automata.MutableDeterministic;
022import net.automatalib.commons.util.collections.CollectionsUtil;
023import net.automatalib.words.Alphabet;
024import de.learnlib.algorithms.lstargeneric.table.Row;
025import de.learnlib.api.MembershipOracle;
026
027
028/**
029 * Abstract base class for algorithms that produce (subclasses of) {@link MutableDeterministic}
030 * automata. 
031 * 
032 * This class provides the L*-style hypothesis construction. Implementing classes solely have
033 * to specify how state and transition properties should be derived.
034 *  
035 * @author Malte Isberner <malte.isberner@gmail.com>
036 *
037 * @param <A> automaton class, must be a subclass of {@link MutableDeterministic}
038 * @param <I> input symbol class
039 * @param <O> output class
040 * @param <SP> state property class
041 * @param <TP> transition property class
042 */
043public abstract class AbstractAutomatonLStar<A,I,O,S,T,SP,TP,AI extends MutableDeterministic<S,I,T,SP,TP>> extends
044                AbstractLStar<A, I, O> {
045        
046        private static final class StateInfo<S,I> {
047                private final Row<I> row;
048                private final S state;
049                
050                public StateInfo(Row<I> row, S state) {
051                        this.row = row;
052                        this.state = state;
053                }
054                
055                public Row<I> getRow() {
056                        return row;
057                }
058                
059                public S getState() {
060                        return state;
061                }
062                
063                // IDENTITY SEMANTICS!
064        }
065
066        protected final AI internalHyp;
067        protected final ArrayList<StateInfo<S,I>> stateInfos
068                = new ArrayList<>();
069        
070        /**
071         * Constructor.
072         * @param alphabet the learning alphabet
073         * @param oracle the learning oracle
074         */
075        public AbstractAutomatonLStar(Alphabet<I> alphabet,
076                        MembershipOracle<I, O> oracle,
077                        AI internalHyp) {
078                super(alphabet, oracle);
079                this.internalHyp = internalHyp;
080                internalHyp.clear();
081        }
082        
083        /**
084         * Derives a state property from the corresponding row.
085         * @param stateRow the row for which the state is created
086         * @return the state property of the corresponding state
087         */
088        protected abstract SP stateProperty(Row<I> stateRow);
089        
090        /**
091         * Derives a transition property from the corresponding transition.
092         * N.B.: Not the transition row is passed to this method, but the
093         * row for the outgoing state. The transition row can be retrieved
094         * by <code>stateRow.getSuccessor(inputIdx)</code>.
095         * @param stateRow the row for the source state
096         * @param inputIdx the index of the input symbol to consider
097         * @return the transition property of the corresponding transition
098         */
099        protected abstract TP transitionProperty(Row<I> stateRow, int inputIdx);
100        
101        
102        protected abstract A exposeInternalHypothesis();
103        
104        /**
105         * Performs the L*-style hypothesis construction.
106         * For creating states and transitions, the {@link #stateProperty(Row)} and
107         * {@link #transitionProperty(Row, int)} methods are used to derive the
108         * respective properties.
109         * @param model the model to output
110         */
111        protected void updateInternalHypothesis() {
112                if(!table.isInitialized())
113                        throw new IllegalStateException("Cannot update internal hypothesis: not initialized");
114                
115                int oldStates = internalHyp.size();
116                int numDistinct = table.numDistinctRows();
117                
118
119                int newStates = numDistinct - oldStates;
120                
121                if(newStates <= 0)
122                        return;
123                
124                stateInfos.addAll(CollectionsUtil.<StateInfo<S,I>>nullList(newStates));
125                
126                
127                // TODO: Is there a quicker way than iterating over *all* rows?
128                // FIRST PASS: Create new hypothesis states
129                for(Row<I> sp : table.getShortPrefixRows()) {
130                        int id = sp.getRowContentId();
131                        StateInfo<S,I> info = stateInfos.get(id);
132                        if(info != null) {
133                                // State from previous hypothesis, property might have changed
134                                if(info.getRow() == sp)
135                                        internalHyp.setStateProperty(info.getState(), stateProperty(sp));
136                                continue;
137                        }
138                        
139                        S state = createState((id == 0), sp);
140                        
141                        stateInfos.set(id, new StateInfo<>(sp, state));
142                }
143                
144                // SECOND PASS: Create hypothesis transitions
145                for(StateInfo<S,I> info : stateInfos) {
146                        Row<I> sp = info.getRow();
147                        int rowId = sp.getRowContentId();
148                        S state = info.getState();
149                        
150                        for(int i = 0; i < alphabet.size(); i++) {
151                                I input = alphabet.getSymbol(i);
152                                
153                                Row<I> succ = sp.getSuccessor(i);
154                                int succId = succ.getRowContentId();
155                                
156                                if(rowId < oldStates && succId < oldStates)
157                                        continue;
158                                
159                                S succState = stateInfos.get(succId).getState();
160                                
161                                setTransition(state, input, succState, sp, i, succ);
162                        }
163                }
164        }
165        
166        protected S createState(boolean initial, Row<I> row) {
167                SP prop = stateProperty(row);
168                if(initial)
169                        return internalHyp.addInitialState(prop);
170                return internalHyp.addState(prop);
171        }
172        
173        protected void setTransition(S from, I input, S to, Row<I> fromRow, int inputIdx, Row<I> toRow) {
174                TP prop = transitionProperty(fromRow, inputIdx);
175                internalHyp.setTransition(from, input, to, prop);
176        }
177        
178        @Override
179        public A getHypothesisModel() {
180                updateInternalHypothesis();
181                return exposeInternalHypothesis();
182        }
183
184}