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.compact;
018
019import java.util.Collection;
020
021import net.automatalib.automata.FiniteAlphabetAutomaton;
022import net.automatalib.automata.abstractimpl.AbstractMutableDeterministic;
023import net.automatalib.automata.base.StateIDGrowingMapping;
024import net.automatalib.automata.base.StateIDStaticMapping;
025import net.automatalib.automata.concepts.StateIDs;
026import net.automatalib.automata.dot.DefaultDOTHelperAutomaton;
027import net.automatalib.automata.graphs.AbstractAutomatonGraph;
028import net.automatalib.automata.graphs.TransitionEdge;
029import net.automatalib.commons.util.collections.CollectionsUtil;
030import net.automatalib.commons.util.mappings.MutableMapping;
031import net.automatalib.graphs.UniversalGraph;
032import net.automatalib.graphs.concepts.NodeIDs;
033import net.automatalib.graphs.dot.DOTPlottableGraph;
034import net.automatalib.graphs.dot.GraphDOTHelper;
035import net.automatalib.words.Alphabet;
036
037public abstract class AbstractCompactSimpleDet<I, SP> extends
038                AbstractMutableDeterministic<Integer, I, Integer, SP, Void>
039                implements UniversalGraph<Integer,TransitionEdge<I,Integer>,SP,TransitionEdge.Property<I,Void>>,
040                FiniteAlphabetAutomaton<Integer,I,Integer>, StateIDs<Integer>,
041                NodeIDs<Integer>, DOTPlottableGraph<Integer, TransitionEdge<I,Integer>> {
042
043        public static final float DEFAULT_RESIZE_FACTOR = 1.5f;
044        public static final int DEFAULT_INIT_CAPACITY = 11;
045        
046        private final Alphabet<I> alphabet;
047        private final int alphabetSize;
048        private int[] transitions;
049        private int stateCapacity;
050        private int numStates;
051        private int initial = -1;
052        private final float resizeFactor;
053        
054        public AbstractCompactSimpleDet(Alphabet<I> alphabet) {
055                this(alphabet, DEFAULT_INIT_CAPACITY, DEFAULT_RESIZE_FACTOR);
056        }
057        
058        public AbstractCompactSimpleDet(Alphabet<I> alphabet, int stateCapacity) {
059                this(alphabet, stateCapacity, DEFAULT_RESIZE_FACTOR);
060        }
061        
062        public AbstractCompactSimpleDet(Alphabet<I> alphabet, float resizeFactor) {
063                this(alphabet, DEFAULT_INIT_CAPACITY, resizeFactor);
064        }
065        
066        public AbstractCompactSimpleDet(Alphabet<I> alphabet, int stateCapacity, float resizeFactor) {
067                this.alphabet = alphabet;
068                this.alphabetSize = alphabet.size();
069                this.transitions = new int[stateCapacity * alphabetSize];
070                this.resizeFactor = resizeFactor;
071                this.stateCapacity = stateCapacity;
072        }
073        
074        public void ensureCapacity(int newCapacity) {
075                if(newCapacity <= stateCapacity)
076                        return;
077                
078                int newCap = (int)(stateCapacity * resizeFactor);
079                if(newCap < newCapacity)
080                        newCap = newCapacity;
081                
082                int[] newTrans = new int[newCap * alphabetSize];
083                System.arraycopy(transitions, 0, newTrans, 0, stateCapacity * alphabetSize);
084                this.transitions = newTrans;
085                ensureCapacity(stateCapacity, newCap);
086                this.stateCapacity = newCap;
087        }
088        
089        
090        protected void ensureCapacity(int oldCap, int newCap) {}
091        
092        @Override
093        public Alphabet<I> getInputAlphabet() {
094                return alphabet;
095        }
096        
097        /*
098         * (non-Javadoc)
099         * @see net.automatalib.automata.abstractimpl.AbstractDeterministicAutomaton#size()
100         */
101        @Override
102        public int size() {
103                return numStates;
104        }
105
106        /*
107         * (non-Javadoc)
108         * @see net.automatalib.automata.simple.SimpleAutomaton#getStates()
109         */
110        @Override
111        public Collection<Integer> getStates() {
112                return CollectionsUtil.intRange(0, numStates);
113        }
114
115        /*
116         * (non-Javadoc)
117         * @see net.automatalib.automata.simple.SimpleAutomaton#getState(int)
118         */
119        @Override
120        public Integer getState(int id) {
121                return id;
122        }
123
124        /*
125         * (non-Javadoc)
126         * @see net.automatalib.automata.simple.SimpleAutomaton#getStateId(java.lang.Object)
127         */
128        @Override
129        public int getStateId(Integer state) {
130                return state.intValue();
131        }
132
133        /*
134         * (non-Javadoc)
135         * @see net.automatalib.ts.SimpleDTS#getInitialState()
136         */
137        @Override
138        public Integer getInitialState() {
139                return (initial != -1) ? Integer.valueOf(initial) : null;
140        }
141
142        /*
143         * (non-Javadoc)
144         * @see net.automatalib.ts.DeterministicTransitionSystem#getTransition(java.lang.Object, java.lang.Object)
145         */
146        @Override
147        public Integer getTransition(Integer state, I input) {
148                int transId = state.intValue() * alphabetSize + alphabet.getSymbolIndex(input);
149                int succId = transitions[transId];
150                if(succId == 0)
151                        return null;
152                return succId - 1;
153        }
154
155        public void setInitialState(int state) {
156                this.initial = state;
157        }
158
159        @Override
160        public void setInitialState(Integer state) {
161                setInitialState((state != null) ? state.intValue() : -1);
162        }
163        
164        public void setTransition(int state, int inputIdx, int succ) {
165                transitions[state * alphabetSize + inputIdx] = succ + 1;
166        }
167        
168        public void setTransition(int state, I input, int succ) {
169                setTransition(state, alphabet.getSymbolIndex(input), succ);
170        }
171
172        @Override
173        public void setTransition(Integer state, I input, Integer transition) {
174                int succId = (transition != null) ? transition.intValue() : -1;
175                setTransition(state.intValue(), input, succId);
176        }
177
178        @Override
179        public void clear() {
180                int endIdx = numStates * alphabetSize;
181                numStates = 0;
182                for(int i = 0; i < endIdx; i++)
183                        transitions[i] = 0;
184                initial = -1;
185        }
186
187
188        public void removeAllTransitions(int state) {
189                int base = state * alphabetSize;
190                
191                for(int i = 0; i < alphabetSize; i++)
192                        transitions[base++] = 0;
193        }
194        
195        @Override
196        public void removeAllTransitions(Integer state) {
197                removeAllTransitions(state.intValue());
198        }
199
200        @Override
201        public Integer copyTransition(Integer trans, Integer succ) {
202                return succ;
203        }
204
205        @Override
206        public Integer getSuccessor(Integer transition) {
207                return transition;
208        }
209        
210        public abstract SP getStateProperty(int stateId);
211
212        @Override
213        public SP getStateProperty(Integer state) {
214                return getStateProperty(state.intValue());
215        }
216
217        /*
218         * (non-Javadoc)
219         * @see net.automatalib.ts.UniversalTransitionSystem#getTransitionProperty(java.lang.Object)
220         */
221        @Override
222        public Void getTransitionProperty(Integer transition) {
223                return null;
224        }
225        
226        public abstract void initState(int stateId, SP property);
227
228        public int addIntState(SP property) {
229                int stateId = numStates++;
230                ensureCapacity(numStates);
231                initState(stateId, property);
232                return stateId;
233        }
234        
235        @Override
236        public Integer addState(SP property) {
237                return addIntState(property);
238        }
239        
240        public abstract void setStateProperty(int stateId, SP property);
241
242        @Override
243        public void setStateProperty(Integer state, SP property) {
244                setStateProperty(state.intValue(), property);
245        }
246
247        /*
248         * (non-Javadoc)
249         * @see net.automatalib.automata.MutableAutomaton#setTransitionProperty(java.lang.Object, java.lang.Object)
250         */
251        @Override
252        public void setTransitionProperty(Integer transition, Void property) {
253        }
254
255        /*
256         * (non-Javadoc)
257         * @see net.automatalib.automata.MutableAutomaton#createTransition(java.lang.Object, java.lang.Object)
258         */
259        @Override
260        public Integer createTransition(Integer successor, Void properties) {
261                return successor;
262        }
263        
264        
265        @Override
266        public StateIDs<Integer> stateIDs() {
267                return this;
268        }
269
270        @Override
271        public SP getNodeProperty(Integer node) {
272                return getStateProperty(node);
273        }
274
275        @Override
276        public TransitionEdge.Property<I, Void> getEdgeProperty(TransitionEdge<I, Integer> edge) {
277                return new TransitionEdge.Property<I,Void>(edge.getInput(), null);
278        }
279
280        @Override
281        public Collection<TransitionEdge<I, Integer>> getOutgoingEdges(Integer node) {
282                return AbstractAutomatonGraph.getOutgoingEdges(this, node);
283        }
284
285        @Override
286        public Integer getTarget(TransitionEdge<I, Integer> edge) {
287                return edge.getTransition();
288        }
289
290        @Override
291        public <V> MutableMapping<Integer, V> createStaticNodeMapping() {
292                return new StateIDStaticMapping<>(this, numStates);
293        }
294
295        @Override
296        public <V> MutableMapping<Integer, V> createDynamicNodeMapping() {
297                return new StateIDGrowingMapping<>(this, this);
298        }
299
300        @Override
301        public Collection<Integer> getNodes() {
302                return getStates();
303        }
304
305        @Override
306        public NodeIDs<Integer> nodeIDs() {
307                return this;
308        }
309
310        @Override
311        public GraphDOTHelper<Integer, TransitionEdge<I, Integer>> getGraphDOTHelper() {
312                return new DefaultDOTHelperAutomaton<>(this);
313        }
314
315        @Override
316        public int getNodeId(Integer node) {
317                return node.intValue();
318        }
319
320        @Override
321        public Integer getNode(int id) {
322                return Integer.valueOf(id);
323        }
324
325
326        
327}