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.automata.base.fast;
018
019import java.util.Collection;
020
021import net.automatalib.automata.FiniteAlphabetAutomaton;
022import net.automatalib.automata.abstractimpl.AbstractShrinkableAutomaton;
023import net.automatalib.automata.abstractimpl.AbstractShrinkableDeterministic;
024import net.automatalib.automata.base.StateIDDynamicMapping;
025import net.automatalib.automata.base.StateIDStaticMapping;
026import net.automatalib.automata.concepts.StateIDs;
027import net.automatalib.automata.graphs.AbstractAutomatonGraph;
028import net.automatalib.commons.util.Pair;
029import net.automatalib.commons.util.mappings.MutableMapping;
030import net.automatalib.commons.util.nid.DynamicList;
031import net.automatalib.commons.util.nid.IDChangeNotifier;
032import net.automatalib.graphs.UniversalGraph;
033import net.automatalib.graphs.concepts.NodeIDs;
034import net.automatalib.words.Alphabet;
035
036
037public abstract class FastMutableDet<S extends FastDetState<S, T>, I, T, SP, TP> extends
038                AbstractShrinkableDeterministic<S, I, T, SP, TP> implements
039                FiniteAlphabetAutomaton<S, I, T>, UniversalGraph<S,Pair<I,T>,SP,Pair<I,TP>>, StateIDs<S>, NodeIDs<S> {
040        
041        private final DynamicList<S> states
042                = new DynamicList<S>();
043        private final IDChangeNotifier<S> tracker
044                = new IDChangeNotifier<>();
045        
046        private S initialState;
047        
048        protected final Alphabet<I> inputAlphabet;
049        
050        public FastMutableDet(Alphabet<I> inputAlphabet) {
051                this.inputAlphabet = inputAlphabet;
052        }
053
054        /*
055         * (non-Javadoc)
056         * @see net.automatalib.automata.simple.SimpleAutomaton#getStates()
057         */
058        @Override
059        public Collection<S> getStates() {
060                return states;
061        }
062
063        /*
064         * (non-Javadoc)
065         * @see net.automatalib.automata.concepts.StateIDs#getState(int)
066         */
067        @Override
068        public S getState(int id) {
069                return states.get(id);
070        }
071
072        /*
073         * (non-Javadoc)
074         * @see net.automatalib.automata.concepts.StateIDs#getStateId(java.lang.Object)
075         */
076        @Override
077        public int getStateId(S state) {
078                return state.getId();
079        }
080
081        /*
082         * (non-Javadoc)
083         * @see net.automatalib.automata.MutableDeterministic#setInitialState(java.lang.Object)
084         */
085        @Override
086        public void setInitialState(S state) {
087                this.initialState = state;
088        }
089
090        /*
091         * (non-Javadoc)
092         * @see net.automatalib.automata.MutableDeterministic#setTransition(java.lang.Object, java.lang.Object, java.lang.Object)
093         */
094        @Override
095        public void setTransition(S state, I input, T transition) {
096                int inputIdx = inputAlphabet.getSymbolIndex(input);
097                state.setTransition(inputIdx, transition);
098        }
099
100        /*
101         * (non-Javadoc)
102         * @see net.automatalib.ts.simple.SimpleDTS#getInitialState()
103         */
104        @Override
105        public S getInitialState() {
106                return initialState;
107        }
108
109        
110        /*
111         * (non-Javadoc)
112         * @see net.automatalib.ts.DeterministicTransitionSystem#getTransition(java.lang.Object, java.lang.Object)
113         */
114        @Override
115        public T getTransition(S state, I input) {
116                int inputIdx = inputAlphabet.getSymbolIndex(input);
117                return state.getTransition(inputIdx);
118        }
119
120        /*
121         * (non-Javadoc)
122         * @see net.automatalib.automata.MutableAutomaton#clear()
123         */
124        @Override
125        public void clear() {
126                states.clear();
127                this.initialState = null;
128        }
129
130        /*
131         * (non-Javadoc)
132         * @see net.automatalib.automata.MutableAutomaton#addState(java.lang.Object)
133         */
134        @Override
135        public S addState(SP property) {
136                S newState = createState(property);
137                states.add(newState);
138                return newState;
139        }
140
141        /*
142         * (non-Javadoc)
143         * @see net.automatalib.automata.ShrinkableAutomaton#removeState(java.lang.Object, java.lang.Object)
144         */
145        @Override
146        public void removeState(S state, S replacement) {
147                AbstractShrinkableAutomaton.unlinkState(this, state, replacement, inputAlphabet);
148                states.remove(state);
149        }
150
151        /*
152         * (non-Javadoc)
153         * @see net.automatalib.automata.concepts.InputAlphabetHolder#getInputAlphabet()
154         */
155        @Override
156        public Alphabet<I> getInputAlphabet() {
157                return inputAlphabet;
158        }
159
160
161        /*
162         * (non-Javadoc)
163         * @see net.automatalib.graphs.concepts.NodeIDs#getNodeId(java.lang.Object)
164         */
165        @Override
166        public int getNodeId(S node) {
167                return node.getId();
168        }
169
170        /*
171         * (non-Javadoc)
172         * @see net.automatalib.graphs.concepts.NodeIDs#getNode(int)
173         */
174        @Override
175        public S getNode(int id) {
176                return states.get(id);
177        }
178
179        /*
180         * (non-Javadoc)
181         * @see net.automatalib.graphs.Graph#getNodes()
182         */
183        @Override
184        public Collection<S> getNodes() {
185                return AbstractAutomatonGraph.getNodes(this);
186        }
187
188        /*
189         * (non-Javadoc)
190         * @see net.automatalib.graphs.IndefiniteGraph#getOutgoingEdges(java.lang.Object)
191         */
192        @Override
193        public Collection<Pair<I, T>> getOutgoingEdges(S node) {
194                return AbstractAutomatonGraph.getOutgoingEdges(this, node);
195        }
196
197        /*
198         * (non-Javadoc)
199         * @see net.automatalib.graphs.IndefiniteGraph#getTarget(java.lang.Object)
200         */
201        @Override
202        public S getTarget(Pair<I, T> edge) {
203                return AbstractAutomatonGraph.getTarget(this, edge);
204        }
205        
206        /*
207         * (non-Javadoc)
208         * @see net.automatalib.automata.MutableAutomaton#removeAllTransitions(java.lang.Object)
209         */
210        @Override
211        public void removeAllTransitions(S state) {
212                state.clearTransitions();
213        }
214        
215        /*
216         * (non-Javadoc)
217         * @see net.automatalib.graphs.UniversalIndefiniteGraph#getNodeProperties(java.lang.Object)
218         */
219        @Override
220        public SP getNodeProperty(S node) {
221                return AbstractAutomatonGraph.getNodeProperties(this, node);
222        }
223        
224        /*
225         * (non-Javadoc)
226         * @see net.automatalib.graphs.UniversalIndefiniteGraph#getEdgeProperties(java.lang.Object)
227         */
228        @Override
229        public Pair<I,TP> getEdgeProperty(Pair<I,T> edge) {
230                return AbstractAutomatonGraph.getEdgeProperties(this, edge);
231        }
232        
233        /*
234         * (non-Javadoc)
235         * @see net.automatalib.automata.abstractimpl.AbstractDeterministicAutomaton#stateIDs()
236         */
237        @Override
238        public StateIDs<S> stateIDs() {
239                return this;
240        }
241        
242        /*
243         * (non-Javadoc)
244         * @see net.automatalib.graphs.Graph#nodeIDs()
245         */
246        @Override
247        public NodeIDs<S> nodeIDs() {
248                return this;
249        }
250        
251        
252        /*
253         * (non-Javadoc)
254         * @see net.automatalib.ts.abstractimpl.AbstractTS#createStaticStateMapping()
255         */
256        @Override
257        public <V> MutableMapping<S,V> createStaticStateMapping() {
258                return new StateIDStaticMapping<>(this, size());
259        }
260
261        /*
262         * (non-Javadoc)
263         * @see net.automatalib.ts.abstractimpl.AbstractTS#createDynamicStateMapping()
264         */
265        @Override
266        public <V> MutableMapping<S,V> createDynamicStateMapping() {
267                StateIDDynamicMapping<S, V> mapping = new StateIDDynamicMapping<>(this);
268                tracker.addListener(mapping, true);
269                return mapping;
270        }
271        
272        /*
273         * (non-Javadoc)
274         * @see net.automatalib.graphs.IndefiniteGraph#createStaticNodeMapping()
275         */
276        @Override
277        public <V> MutableMapping<S, V> createStaticNodeMapping() {
278                return AbstractAutomatonGraph.createStaticNodeMapping(this);
279        }
280
281        /*
282         * (non-Javadoc)
283         * @see net.automatalib.graphs.IndefiniteGraph#createDynamicNodeMapping()
284         */
285        @Override
286        public <V> MutableMapping<S, V> createDynamicNodeMapping() {
287                return AbstractAutomatonGraph.createDynamicNodeMapping(this);
288        }
289
290        protected abstract S createState(SP property);
291}