001 /*
002 * Created on May 14, 2007
003 */
004 package com.x8ing.lsm4j.state;
005
006 import java.util.ArrayList;
007 import java.util.HashMap;
008 import java.util.Iterator;
009 import java.util.List;
010 import java.util.Map;
011
012 /**
013 * Stores the structure of a graph. It must be possible to have several tansitions between two nodes.
014 * <p>
015 * We need two ways to fast get a transition.
016 * <p>
017 * 1. get all transitions starting from a node A.<br>
018 * 2. get all transition between node A and node B <br>
019 *
020 * We make a memory/speed tradeoff and use two hashmaps: <br>
021 * 1. internode hashmap <br>
022 * 2. outgoing node hashmap
023 *
024 *
025 * @author Patrick Heusser
026 */
027 public class StaticGraph {
028
029 private static final String KEY_SEP = ",";
030
031 /**
032 * key: String using method getInternodeKey() <br>
033 * value: TransitionList
034 */
035 private Map internodes = new HashMap();
036
037 /**
038 * key: String using method getOutgoingKey() <br>
039 * value: TransitionList
040 */
041 private Map outgoings = new HashMap();
042
043 /**
044 * A list of transitions.
045 *
046 * @author Patrick Heusser
047 */
048 protected static class TransitionList {
049
050 /**
051 * type: StaticTransition
052 */
053 private List transitions = new ArrayList();
054
055 protected void addTransition(StaticTransition transition) {
056 transitions.add(transition);
057 }
058
059 protected List getTransitionsList() {
060 return transitions;
061 }
062
063 }
064
065 /**
066 * TODO implement stateiterator and transition iterator!!!
067 *
068 * Iterates over all states in the graph.
069 *
070 * @author Patrick Heusser
071 */
072 protected static class StateIterator implements Iterator {
073
074 private Map outgoings = null;
075
076 private Iterator itOutGoings = null;
077
078 private StaticState nextReturn = null;
079
080 protected StateIterator(Map outgoings) {
081 this.outgoings = outgoings;
082 }
083
084 public boolean hasNext() {
085 return false;
086 }
087
088 /**
089 * Type: {@link StaticState}
090 */
091 public Object next() {
092
093 return null;
094 }
095
096 private void prepareNextReturn() {
097
098 }
099
100 /**
101 * Not supported. Iterator is read only!
102 *
103 * @throws UnsupportedOperationException
104 */
105 public void remove() {
106
107 // TODO may be implement once...
108 throw new UnsupportedOperationException("graph is read only. remove is not allowed.");
109
110 }
111 }
112
113 /**
114 * @return null if not found
115 */
116 protected StaticState getStateWithID(int stateUID) {
117 List list = getTransitionListForState(stateUID);
118
119 if(list==null || list.isEmpty()) {
120 return null;
121 }
122
123 StaticTransition trans = (StaticTransition) list.get(0);
124
125 if (trans == null) {
126 return null;
127 }
128
129 return trans.getCurrentState();
130 }
131
132 /**
133 *
134 */
135 public void addTransition(StaticTransition transition) {
136
137 // add it to internodes
138 {
139 String keyInternode = getInternodeKey(transition);
140 TransitionList internodeTransitionList = (TransitionList) internodes.get(keyInternode);
141 if (internodeTransitionList == null) {
142 // lazy add one entry
143 internodeTransitionList = new TransitionList();
144 }
145 internodeTransitionList.addTransition(transition);
146 internodes.put(keyInternode, internodeTransitionList);
147 }
148
149 // add it to outgoing nodes
150 {
151 String keyOutgoing = getOutgoingKey(transition);
152 TransitionList outgoingTransitionList = (TransitionList) outgoings.get(keyOutgoing);
153 if (outgoingTransitionList == null) {
154 // lazy add one entry
155 outgoingTransitionList = new TransitionList();
156 }
157 outgoingTransitionList.addTransition(transition);
158 outgoings.put(keyOutgoing, outgoingTransitionList);
159
160 }
161
162 }
163
164 /**
165 * Get a list of transitions that leave a certain state.
166 *
167 * If nothing is found, an empty list is returned.
168 *
169 * @param stateUID
170 * @return List with elements of type: {@link StaticTransition}
171 */
172 public List getTransitionListForState(int stateUID) {
173
174 String key = getOutgoingKey(stateUID);
175
176 TransitionList transitionList = (TransitionList) outgoings.get(key);
177
178 // return empty list
179 if (transitionList == null) {
180 return new ArrayList();
181 }
182
183 return transitionList.getTransitionsList();
184
185 }
186
187 /**
188 * Get a list of transitions that are between two states.
189 *
190 * If nothing is found, an empty list is returned.
191 *
192 * @param currentStateUID
193 * @param nextStateUID
194 * @return List with elements of type: {@link StaticTransition}
195 */
196 public List getTransitionsBetweenStates(int currentStateUID, int nextStateUID) {
197
198 String key = getInternodeKey(currentStateUID, nextStateUID);
199
200 TransitionList transitionList = (TransitionList) internodes.get(key);
201
202 // return empty list
203 if (transitionList == null) {
204 return new ArrayList();
205 }
206
207 return transitionList.getTransitionsList();
208
209 }
210
211 /**
212 * @return currentNode.UID + SEP + nextNode.UID
213 */
214 private static String getInternodeKey(StaticTransition transition) {
215
216 return getInternodeKey(transition.currentState.getUniqueID(), transition.nextState.getUniqueID());
217 }
218
219 /**
220 * @return currentNode.UID + SEP + nextNode.UID
221 */
222 private static String getInternodeKey(int currentUID, int nextUID) {
223
224 String key = String.valueOf(currentUID) + KEY_SEP + String.valueOf(nextUID);
225
226 return key;
227 }
228
229 /**
230 * @return currentNode.UID
231 */
232 private static String getOutgoingKey(StaticTransition transition) {
233
234 return getOutgoingKey(transition.currentState.getUniqueID());
235 }
236
237 /**
238 * @return currentNode.UID
239 */
240 private static String getOutgoingKey(int stateUID) {
241
242 String key = String.valueOf(stateUID);
243
244 return key;
245 }
246
247 public String printGraph() {
248
249 StringBuffer ret = new StringBuffer();
250
251 ret.append("\n");
252 for (Iterator it1 = outgoings.values().iterator(); it1.hasNext();) {
253 TransitionList transitionList = (TransitionList) it1.next();
254 for (Iterator it2 = transitionList.getTransitionsList().iterator(); it2.hasNext();) {
255
256 StaticTransition staticTransition = (StaticTransition) it2.next();
257 ret.append("\n");
258 ret.append(staticTransition);
259
260 }
261
262 }
263
264 return ret.toString();
265 }
266
267 /**
268 *
269 * @return the count of transitions in the graph.
270 */
271 public int getTransitionsCount() {
272
273 return internodes.size();
274
275 }
276
277 /**
278 *
279 * @return the count of states in the graph.
280 */
281 public int getStateCount() {
282
283 return outgoings.size();
284 }
285
286 public void addValidTransition(StaticTransition transition) {
287 addTransition(transition);
288 }
289
290 public void addValidTransition(StaticState currentState, StaticState nextState) {
291 StaticTransition transition = new StaticTransition(currentState, nextState);
292 addValidTransition(transition);
293 }
294
295 public boolean isValidTransition(StaticTransition transition) {
296 int uid1 = transition.currentState.getUniqueID();
297 int uid2 = transition.nextState.getUniqueID();
298 List list = getTransitionsBetweenStates(uid1, uid2);
299 return list.isEmpty();
300 }
301
302 public boolean isValidTransition(StaticState currentState, StaticState nextState) {
303 int uid1 = currentState.getUniqueID();
304 int uid2 = nextState.getUniqueID();
305 List list = getTransitionsBetweenStates(uid1, uid2);
306 return !list.isEmpty();
307
308 }
309
310 public String toString() {
311 StringBuffer ret = new StringBuffer();
312 ret.append(printGraph());
313 ret.append("\n stateCount=");
314 ret.append(getStateCount());
315 ret.append("\n transitionsCount=");
316 ret.append(getTransitionsCount());
317 ret.append("\n");
318
319 return ret.toString();
320 }
321 }
|