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}