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}