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