View Javadoc

1   /*
2    * Copyright (C) 2006  Tom Gibara
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the Free Software
16   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17   */
18  
19  package com.tomgibara.pronto.state.impl;
20  
21  import java.util.Collections;
22  import java.util.HashSet;
23  import java.util.Iterator;
24  import java.util.List;
25  import java.util.Set;
26  
27  import com.tomgibara.pronto.state.PathType;
28  import com.tomgibara.pronto.state.StateGraph;
29  import com.tomgibara.pronto.state.StateGraphEditor;
30  import com.tomgibara.pronto.state.StateTransition;
31  import com.tomgibara.pronto.util.Arguments;
32  
33  public class StateGraphEditorImpl<S, L> implements StateGraphEditor<S, L> {
34  
35      // fields
36  
37      private Set<S> states = new HashSet<S>();
38  
39      private Set<StateTransitionImpl<S, L>> transitions = new HashSet<StateTransitionImpl<S, L>>();
40  
41      private StateGraphImpl<S, L> graph = null;
42  
43      // constructors
44  
45      public StateGraphEditorImpl() {
46      }
47  
48      public StateGraphEditorImpl(final StateGraph<S, L> graph) {
49          states.addAll(graph.states());
50          for (StateTransition<S, L> transition : graph.transitions()) {
51              transitions.add(convert(transition));
52          }
53      }
54  
55      // state graph editor methods
56  
57      // basic mutation
58  
59      public boolean addState(final S state) {
60          return check(states.add(state));
61      }
62  
63      public boolean removeState(final S state) {
64          boolean changed = states.remove(state);
65          if (!changed) return check(false);
66          removeTransitionsOn(state);
67          return check(true);
68      }
69  
70      public boolean addTransition(final StateTransition<S, L> transition) {
71          boolean changed = transitions.add(convert(transition));
72          if (!changed) return check(false);
73          states.add(transition.getSource());
74          states.add(transition.getTarget());
75          return check(true);
76      }
77  
78      public boolean addTransition(final S source, final L label, final S target) {
79          StateTransitionImpl<S, L> trans = new StateTransitionImpl<S, L>(source, label, target);
80          boolean changed = transitions.add(trans);
81          if (!changed) return check(false);
82          states.add(source);
83          states.add(target);
84          return check(true);
85      }
86  
87      public boolean removeTransition(final S source, final L label, final S target) {
88          StateTransitionImpl<S, L> trans = new StateTransitionImpl<S, L>(source, label, target);
89          return check(transitions.remove(trans));
90      }
91  
92      public boolean removeTransitionsMatching(final S source, final L label, final S target) {
93          if (source != null && label != null && target != null) {
94              return check(removeTransition(source, label, target));
95          } else {
96              return check(remove(new TransitionFilter<S, L>() {
97                  public boolean accept(final StateTransitionImpl<S, L> transition) {
98                      if (source != null && !transition.getSource().equals(source)) return false;
99                      if (label != null && !transition.getLabel().equals(label)) return false;
100                     if (target != null && !transition.getTarget().equals(target)) return false;
101                     return true;
102                 }
103             }));
104         }
105     }
106 
107     public boolean removeTransitionsOn(final S state) {
108         return check(remove(new TransitionFilter<S, L>() {
109             public boolean accept(final StateTransitionImpl<S, L> transition) {
110                 return transition.getSource().equals(state) || transition.getTarget().equals(state);
111             }
112         }));
113     }
114 
115     // group mutation
116 
117     public boolean addStates(final Set<S> set) {
118         Arguments.notNull(states, "states");
119         return check(states.addAll(set));
120     }
121 
122     public boolean removeStates(final Set<S> set) {
123         Arguments.notNull(states, "states");
124         boolean changed = states.removeAll(set);
125         if (!changed) return check(false);
126         remove(new TransitionFilter<S, L>() {
127             public boolean accept(final StateTransitionImpl<S, L> transition) {
128                 return set.contains(transition.getSource()) || set.contains(transition.getTarget());
129             }
130         });
131         return check(true);
132     }
133 
134     public boolean retainStates(final Set<S> set) {
135         Arguments.notNull(states, "states");
136         boolean changed = states.retainAll(set);
137         if (!changed) return check(false);
138         remove(new TransitionFilter<S, L>() {
139             public boolean accept(final StateTransitionImpl<S, L> transition) {
140                 return !set.contains(transition.getSource()) || !set.contains(transition.getTarget());
141             }
142         });
143         return check(true);
144     }
145 
146     public boolean addTransitions(final Set<StateTransition<S, L>> trans) {
147         Arguments.notNull(trans, "trans");
148         Set<StateTransitionImpl<S, L>> set = convert(trans);
149         boolean changed = transitions.addAll(set);
150         if (!changed) return check(false);
151         for (StateTransitionImpl<S, L> transition : set) {
152             states.add(transition.getSource());
153             states.add(transition.getTarget());
154         }
155         return check(true);
156     }
157 
158     public boolean removeTransitions(final Set<StateTransition<S, L>> trans) {
159         Arguments.notNull(trans, "trans");
160         return check(transitions.removeAll(convert(trans)));
161     }
162 
163     public boolean retainTransitions(final Set<StateTransition<S, L>> trans) {
164         Arguments.notNull(trans, "trans");
165         final Set<StateTransitionImpl<S, L>> set = convert(trans);
166         return check(remove(new TransitionFilter<S, L>() {
167             public boolean accept(final StateTransitionImpl<S, L> transition) {
168                 return !set.contains(transition);
169             }
170         }));
171     }
172 
173     public boolean addGraph(final StateGraph<S, L> graph) {
174         Arguments.notNull(graph, "graph");
175         boolean changedStates = states.addAll(graph.states());
176         boolean changedTrans = transitions.addAll(convert(graph.transitions()));
177         return check(changedStates || changedTrans);
178     }
179 
180     public boolean retainGraph(final StateGraph<S, L> graph) {
181         Arguments.notNull(graph, "graph");
182         boolean changedStates = states.retainAll(graph.states());
183         boolean changedTrans = retainTransitions(graph.transitions());
184         return check(changedStates || changedTrans);
185     }
186 
187     public boolean removeTransitionsLabelled(final Set<L> labels) {
188         Arguments.notNull(labels, "labels");
189         return check(remove(new TransitionFilter<S, L>() {
190             public boolean accept(final StateTransitionImpl<S, L> transition) {
191                 return labels.contains(transition.getLabel());
192             }
193         }));
194     }
195 
196     public boolean retainTransitionsLabelled(final Set<L> labels) {
197         Arguments.notNull(labels, "labels");
198         return check(remove(new TransitionFilter<S, L>() {
199             public boolean accept(final StateTransitionImpl<S, L> transition) {
200                 return !labels.contains(transition.getLabel());
201             }
202         }));
203     }
204 
205     // substitution
206 
207     public boolean substituteState(final S from, final S to) {
208         Arguments.notNull(from, "from");
209         Arguments.notNull(to, "to");
210 
211         if (from.equals(to)) return false;
212         return check(substituteStates(Collections.singleton(from), to));
213     }
214 
215     // its own transitions
216     public boolean substituteStates(final Set<S> from, final S to) {
217         Arguments.notNull(from, "from");
218         Arguments.notNull(to, "to");
219 
220         // identify if there's work to do
221         final HashSet<S> change = new HashSet<S>(from);
222         change.retainAll(states);
223         change.remove(to);
224         if (change.isEmpty()) return check(false);
225 
226         // do the work
227         states.removeAll(change);
228         states.add(to);
229         replace(new TransitionReplacer<S, L>() {
230             public StateTransitionImpl<S, L> replace(final StateTransitionImpl<S, L> transition) {
231                 S source = transition.getSource();
232                 S target = transition.getTarget();
233                 L label = transition.getLabel();
234                 boolean sourceMatch = from.contains(source);
235                 boolean targetMatch = from.contains(target);
236                 if (sourceMatch && targetMatch) return new StateTransitionImpl<S, L>(to, label, to);
237                 else if (sourceMatch) return new StateTransitionImpl<S, L>(to, label, target);
238                 else if (targetMatch) return new StateTransitionImpl<S, L>(source, label, to);
239                 else return transition;
240             }
241         });
242         return check(true);
243     }
244 
245     public boolean substituteLabel(final L from, final L to) {
246         return check(substituteLabels(Collections.singleton(from), to));
247     }
248 
249     public boolean substituteLabels(final Set<L> from, final L to) {
250         return check(replace(new TransitionReplacer<S, L>() {
251             public StateTransitionImpl<S, L> replace(final StateTransitionImpl<S, L> transition) {
252                 L label = transition.getLabel();
253                 if (to.equals(label) || !from.contains(label)) return transition;
254                 return new StateTransitionImpl<S, L>(transition.getSource(), to, transition.getTarget());
255             }
256         }));
257     }
258 
259     public boolean reverse() {
260         return check(replace(new TransitionReplacer<S, L>() {
261             public StateTransitionImpl<S, L> replace(final StateTransitionImpl<S, L> transition) {
262                 if (transition.getSource().equals(transition.getTarget())) return transition;
263                 StateTransitionImpl<S, L> reversal = new StateTransitionImpl<S, L>(transition.getTarget(), transition
264                         .getLabel(), transition.getSource());
265                 //avoid replacement unless absolutely necessary, this ensures that the returned boolean is correct.
266                 return transitions.contains(reversal) ? transition : reversal;
267             };
268         }));
269     }
270 
271     // paths
272 
273     public boolean removePaths(final S initial, final S terminal, final PathType type) {
274         Arguments.notNull(initial, "initial");
275         Arguments.notNull(terminal, "terminal");
276         Arguments.notNull(type, "type");
277 
278         return check(removeMultiPaths(Collections.singleton(initial), Collections.singleton(terminal), type));
279     }
280 
281     public boolean removeMultiPaths(final Set<S> initial, final Set<S> terminal, final PathType type) {
282         Arguments.notNull(initial, "initial");
283         Arguments.notNull(terminal, "terminal");
284         Arguments.notNull(type, "type");
285 
286         if (states.isEmpty()) return check(false);
287         HashSet<S> initialStates = new HashSet<S>(initial);
288         initialStates.retainAll(states);
289         HashSet<S> terminalStates = new HashSet<S>(terminal);
290         terminalStates.retainAll(states);
291 
292         if (initialStates.isEmpty() || terminalStates.isEmpty()) return check(false);
293 
294         final HashSet<List<StateTransition<S, L>>> paths = new HashSet<List<StateTransition<S, L>>>();
295         PathFinder<S, L> pathFinder = new PathFinder<S, L>(states, transitions);
296         for (S state : initial) {
297             pathFinder.addPathsBetween(state, terminal, paths, type);
298         }
299 
300         if (paths.isEmpty()) return check(false);
301 
302         for (List<StateTransition<S, L>> path : paths) {
303             for (StateTransition<S, L> transition : path) {
304                 this.transitions.remove(transition);
305             }
306         }
307 
308         return check(true);
309     }
310 
311     public boolean retainPaths(final S initial, final S terminal, final PathType type) {
312         Arguments.notNull(initial, "initial");
313         Arguments.notNull(terminal, "terminal");
314         Arguments.notNull(type, "type");
315 
316         return check(retainMultiPaths(Collections.singleton(initial), Collections.singleton(terminal), type));
317     }
318 
319     public boolean retainMultiPaths(final Set<S> initial, final Set<S> terminal, final PathType type) {
320         Arguments.notNull(initial, "initial");
321         Arguments.notNull(terminal, "terminal");
322         Arguments.notNull(type, "type");
323         HashSet<S> initialStates = new HashSet<S>(initial);
324         initialStates.retainAll(states);
325         HashSet<S> terminalStates = new HashSet<S>(terminal);
326         terminalStates.retainAll(states);
327 
328         if (initialStates.isEmpty() || terminalStates.isEmpty()) {
329             if (states.isEmpty()) {
330                 return check(false);
331             } else {
332                 states.clear();
333                 transitions.clear();
334                 return check(true);
335             }
336         }
337 
338         final HashSet<List<StateTransition<S, L>>> paths = new HashSet<List<StateTransition<S, L>>>();
339         PathFinder<S, L> pathFinder = new PathFinder<S, L>(states, transitions);
340         for (S state : initial) {
341             pathFinder.addPathsBetween(state, terminal, paths, type);
342         }
343 
344         final HashSet<S> states = new HashSet<S>();
345         final HashSet<StateTransitionImpl<S, L>> transitions = new HashSet<StateTransitionImpl<S, L>>();
346         for (List<StateTransition<S, L>> path : paths) {
347             for (StateTransition<S, L> transition : path) {
348                 transitions.add((StateTransitionImpl<S, L>) transition);
349                 states.add(transition.getSource());
350                 states.add(transition.getTarget());
351             }
352         }
353 
354         boolean changedStates = this.states.retainAll(states);
355         boolean changedTrans = this.transitions.retainAll(transitions);
356         return check(changedStates || changedTrans);
357     }
358 
359     // creation
360 
361     public StateGraphImpl<S, L> getGraph() {
362         if (graph == null) graph = new StateGraphImpl<S, L>(states, transitions);
363         return graph;
364     }
365 
366     // private utility methods
367 
368     private boolean check(boolean changed) {
369         if (changed) graph = null;
370         return changed;
371     }
372     
373     private StateTransitionImpl<S, L> convert(final StateTransition<S, L> transition) {
374         if (transition instanceof StateTransitionImpl) {
375             return (StateTransitionImpl<S, L>) transition;
376         } else {
377             return new StateTransitionImpl<S, L>(transition);
378         }
379     }
380 
381     private Set<StateTransitionImpl<S, L>> convert(final Set<StateTransition<S, L>> trans) {
382         HashSet<StateTransitionImpl<S, L>> set = new HashSet<StateTransitionImpl<S, L>>();
383         for (StateTransition<S, L> transition : trans) {
384             set.add(convert(transition));
385         }
386         return set;
387     }
388 
389     private boolean remove(final TransitionFilter<S, L> filter) {
390         boolean removed = false;
391         for (Iterator<StateTransitionImpl<S, L>> i = transitions.iterator(); i.hasNext();) {
392             StateTransitionImpl<S, L> transition = i.next();
393             boolean remove = filter.accept(transition);
394             if (remove) {
395                 i.remove();
396                 removed = true;
397             }
398         }
399         return removed;
400     }
401 
402     private boolean replace(final TransitionReplacer<S, L> replacer) {
403         boolean replaced = false;
404         HashSet<StateTransitionImpl<S, L>> replacements = new HashSet<StateTransitionImpl<S, L>>();
405         for (Iterator<StateTransitionImpl<S, L>> i = transitions.iterator(); i.hasNext();) {
406             StateTransitionImpl<S, L> transition = i.next();
407             StateTransitionImpl<S, L> replacement = replacer.replace(transition);
408             if (replacement != transition) {
409                 i.remove();
410                 if (replacement != null) replacements.add(replacement);
411                 replaced = true;
412             }
413         }
414 
415         for (StateTransitionImpl<S, L> replacement : replacements) {
416             transitions.add(replacement);
417         }
418         return replaced;
419     }
420 
421 }