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; 020import java.util.HashSet; 021import java.util.Set; 022 023import net.automatalib.automata.FiniteAlphabetAutomaton; 024import net.automatalib.automata.abstractimpl.AbstractShrinkableAutomaton; 025import net.automatalib.automata.base.StateIDDynamicMapping; 026import net.automatalib.automata.base.StateIDStaticMapping; 027import net.automatalib.automata.concepts.StateIDs; 028import net.automatalib.automata.graphs.AbstractAutomatonGraph; 029import net.automatalib.commons.util.Pair; 030import net.automatalib.commons.util.mappings.MutableMapping; 031import net.automatalib.commons.util.nid.DynamicList; 032import net.automatalib.commons.util.nid.IDChangeNotifier; 033import net.automatalib.graphs.UniversalGraph; 034import net.automatalib.graphs.concepts.NodeIDs; 035import net.automatalib.words.Alphabet; 036 037 038public abstract class FastMutableNondet<S extends FastNondetState<S, T>, I, T, SP, TP> 039 extends AbstractShrinkableAutomaton<S, I, T, SP, TP> implements 040 FiniteAlphabetAutomaton<S, I, T>, UniversalGraph<S,Pair<I,T>,SP,Pair<I,TP>>, StateIDs<S>, 041 NodeIDs<S> { 042 043 044 private final DynamicList<S> states 045 = new DynamicList<>(); 046 private final IDChangeNotifier<S> tracker 047 = new IDChangeNotifier<>(); 048 049 private final Set<S> initialStates 050 = new HashSet<>(); 051 052 protected Alphabet<I> inputAlphabet; 053 054 public FastMutableNondet(Alphabet<I> inputAlphabet) { 055 this.inputAlphabet = inputAlphabet; 056 } 057 058 @Override 059 public Collection<S> getStates() { 060 return states; 061 } 062 063 @Override 064 public S getState(int id) { 065 return states.get(id); 066 } 067 068 @Override 069 public int getStateId(S state) { 070 return state.getId(); 071 } 072 073 @Override 074 public Set<S> getInitialStates() { 075 return initialStates; 076 } 077 078 @Override 079 public Collection<T> getTransitions(S state, I input) { 080 int inputIdx = inputAlphabet.getSymbolIndex(input); 081 return state.getTransitions(inputIdx); 082 } 083 084 085 086 @Override 087 public void clear() { 088 states.clear(); 089 initialStates.clear(); 090 } 091 092 @Override 093 public S addState(SP property) { 094 S newState = createState(property); 095 states.add(newState); 096 return newState; 097 } 098 099 @Override 100 public void setInitial(S state, boolean initial) { 101 if(initial) 102 initialStates.add(state); 103 else 104 initialStates.remove(state); 105 } 106 107 @Override 108 public void removeState(S state, S replacement) { 109 AbstractShrinkableAutomaton.unlinkState(this, state, replacement, inputAlphabet); 110 states.remove(state); 111 if(initialStates.remove(state)) 112 initialStates.add(state); 113 } 114 115 @Override 116 public void removeAllTransitions(S state) { 117 state.clearTransitions(); 118 } 119 120 121 @Override 122 public void setTransitions(S state, I input, Collection<? extends T> transitions) { 123 int inputIdx = inputAlphabet.getSymbolIndex(input); 124 state.setTransitions(inputIdx, transitions); 125 } 126 127 @Override 128 public Alphabet<I> getInputAlphabet() { 129 return inputAlphabet; 130 } 131 132 @Override 133 public StateIDs<S> stateIDs() { 134 return this; 135 } 136 137 /* 138 * (non-Javadoc) 139 * @see net.automatalib.ts.abstractimpl.AbstractTS#createStaticStateMapping() 140 */ 141 @Override 142 public <V> MutableMapping<S,V> createStaticStateMapping() { 143 return new StateIDStaticMapping<>(this, size()); 144 } 145 146 /* 147 * (non-Javadoc) 148 * @see net.automatalib.ts.abstractimpl.AbstractTS#createDynamicStateMapping() 149 */ 150 @Override 151 public <V> MutableMapping<S,V> createDynamicStateMapping() { 152 StateIDDynamicMapping<S, V> mapping = new StateIDDynamicMapping<>(this); 153 tracker.addListener(mapping, true); 154 return mapping; 155 } 156 157 /* 158 * (non-Javadoc) 159 * @see net.automatalib.graphs.IndefiniteGraph#createStaticNodeMapping() 160 */ 161 @Override 162 public <V> MutableMapping<S, V> createStaticNodeMapping() { 163 return AbstractAutomatonGraph.createStaticNodeMapping(this); 164 } 165 166 /* 167 * (non-Javadoc) 168 * @see net.automatalib.graphs.IndefiniteGraph#createDynamicNodeMapping() 169 */ 170 @Override 171 public <V> MutableMapping<S, V> createDynamicNodeMapping() { 172 return AbstractAutomatonGraph.createDynamicNodeMapping(this); 173 } 174 175 /* 176 * (non-Javadoc) 177 * @see net.automatalib.graphs.concepts.NodeIDs#getNodeId(java.lang.Object) 178 */ 179 @Override 180 public int getNodeId(S node) { 181 return node.getId(); 182 } 183 184 /* 185 * (non-Javadoc) 186 * @see net.automatalib.graphs.concepts.NodeIDs#getNode(int) 187 */ 188 @Override 189 public S getNode(int id) { 190 return states.get(id); 191 } 192 193 /* 194 * (non-Javadoc) 195 * @see net.automatalib.graphs.Graph#getNodes() 196 */ 197 @Override 198 public Collection<S> getNodes() { 199 return AbstractAutomatonGraph.getNodes(this); 200 } 201 202 /* 203 * (non-Javadoc) 204 * @see net.automatalib.graphs.IndefiniteGraph#getOutgoingEdges(java.lang.Object) 205 */ 206 @Override 207 public Collection<Pair<I, T>> getOutgoingEdges(S node) { 208 return AbstractAutomatonGraph.getOutgoingEdges(this, node); 209 } 210 211 /* 212 * (non-Javadoc) 213 * @see net.automatalib.graphs.IndefiniteGraph#getTarget(java.lang.Object) 214 */ 215 @Override 216 public S getTarget(Pair<I, T> edge) { 217 return AbstractAutomatonGraph.getTarget(this, edge); 218 } 219 220 @Override 221 public NodeIDs<S> nodeIDs() { 222 return this; 223 } 224 225 @Override 226 public SP getNodeProperty(S node) { 227 return AbstractAutomatonGraph.getNodeProperties(this, node); 228 } 229 230 @Override 231 public Pair<I, TP> getEdgeProperty(Pair<I, T> edge) { 232 return AbstractAutomatonGraph.getEdgeProperties(this, edge); 233 } 234 235 protected abstract S createState(SP property); 236 237}