|
1
23 package com.tc.jrexx.automaton;
24
25 import java.util.*;
26 import java.lang.ref.SoftReference  ;
27
28 import com.tc.jrexx.set.ISet_char;
29
30 public abstract class Automaton implements Cloneable {
31
32 protected final static int TRUE = 1;
33 protected final static int FALSE = 0;
34 protected final static int UNKNOWN = -1;
35
36 private static int currentAutomatonNr = 0;
37
38
40 public interface IChangedListener {
41 public void stateAdded(State state);
42 public void stateRemoved(State state);
43 public void startStateChanged(State oldStartState,State newStartState);
44 }
45
46 protected LinkedList listeners = null;
47
48 protected void addChangedListener(Automaton.IChangedListener listener) {
49 if (listener==null) throw new IllegalArgumentException ("listener==null");
50 if (this.listeners==null) this.listeners = new LinkedList();
51 this.listeners.add(listener);
52 }
53
54 protected boolean removeChangedListener(Automaton.IChangedListener listener) {
55 if (this.listeners!=null) {
56 final Iterator it = this.listeners.iterator();
57 for (int i=this.listeners.size(); i>0; --i) {
58 if (listener==it.next()) {
59 if (this.listeners.size()>1) it.remove();
60 else this.listeners = null;
61
62 return true;
63 }
64 }
65 }
66 return false;
67 }
68
69 public interface IStateVisitedListener {
70 public void stateVisited(Automaton.State state);
71 public void stateVisited(Automaton.State state,char ch);
72 public void stateUnVisited(Automaton.State state);
73 }
74 public interface IStateChangedListener {
75 public void transitionAdded(Automaton.State.Transition transition);
76 public void transitionRemoved(Automaton.State.Transition transition);
77 }
78
79 public interface ITransitionVisitedListener {
80 public void transitionVisited(Automaton.State.Transition transition);
81 public void transitionVisited(Automaton.State.Transition transition,char ch);
82 }
83
84 public static final class Wrapper_State {
85 public final State state;
86 public Wrapper_State next=null;
87
88 public Wrapper_State(State state) {
89 this.state = state;
90 }
91 }
92
93 public interface IState extends Cloneable {
94 public IState next(char ch);
95 public LinkedSet_State getAllReachableStates();
96 public Object clone();
97 }
98
99 public class State implements IState {
100 private final static int TRUE = 1;
101 private final static int FALSE = 0;
102 private final static int UNKNOWN = -1;
103
104 transient protected LinkedList visitedListeners = null;
105 transient protected LinkedList changedListeners = null;
106
107 public void addVisitedListener(IStateVisitedListener listener) {
108 if (this.visitedListeners==null) this.visitedListeners = new LinkedList();
109 this.visitedListeners.add(listener);
110 }
111
112 public boolean removeVisitedListener(IStateVisitedListener listener) {
113 if (this.visitedListeners!=null) {
114 final Iterator it = this.visitedListeners.iterator();
115 for (int i=this.visitedListeners.size(); i>0; --i) {
116 if (listener==it.next()) {
117 if (this.visitedListeners.size()>1) it.remove();
118 else this.visitedListeners = null;
119
120 return true;
121 }
122 }
123 }
124 return false;
125 }
126
127 public void addChangedListener(IStateChangedListener listener) {
128 if (this.changedListeners==null) this.changedListeners = new LinkedList();
129 this.changedListeners.add(listener);
130 }
131
132 public boolean removeChangedListener(IStateChangedListener listener) {
133 if (this.changedListeners!=null) {
134 final Iterator it = this.changedListeners.iterator();
135 for (int i=this.changedListeners.size(); i>0; --i) {
136 if (listener==it.next()) {
137 if (this.changedListeners.size()>1) it.remove();
138 else this.changedListeners = null;
139
140 return true;
141 }
142 }
143 }
144 return false;
145 }
146
147 public final IState visit() {
148 if (this.eTransitions==null) {
149 if (this.visitedListeners!=null) {
150 final Iterator it = this.visitedListeners.iterator();
151 for (int i=this.visitedListeners.size(); i>0; --i)
152 ((IStateVisitedListener)it.next()).stateVisited(this);
153 }
154 return this;
155 }
156
157 final LinkedSet_State eClosure = Automaton.this.newLinkedSet_State(this);
158 for (Wrapper_State w=eClosure.elements; w!=null; w=w.next) {
159 if (w.state.visitedListeners!=null) {
160 final Iterator it = w.state.visitedListeners.iterator();
161 for (int i=w.state.visitedListeners.size(); i>0; --i)
162 ((IStateVisitedListener)it.next()).stateVisited(w.state);
163 }
164
165 for (Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
166 trans.visit(eClosure);
167 }
168 }
169
170 return eClosure;
171 }
172
173 protected final void unVisit() {
174 if (this.visitedListeners!=null) {
175 final Iterator it = this.visitedListeners.iterator();
176 for (int i=this.visitedListeners.size(); i>0; --i)
177 ((IStateVisitedListener)it.next()).stateUnVisited(this);
178 }
179 }
180
181
182
186
187 public final class Transition {
188
189 transient LinkedList transitionVisitedListeners = null;
190
191 public void addVisitedListener(ITransitionVisitedListener listener) {
192 if (this.transitionVisitedListeners==null) this.transitionVisitedListeners = new LinkedList();
193 this.transitionVisitedListeners.add(listener);
194 }
195
196 public boolean removeVisitedListener(ITransitionVisitedListener listener) {
197 if (this.transitionVisitedListeners!=null) {
198 Iterator it = this.transitionVisitedListeners.iterator();
199 for (int i=this.transitionVisitedListeners.size(); i>0; --i) {
200 if (listener==it.next()) {
201 if (this.transitionVisitedListeners.size()>1) it.remove();
202 else this.transitionVisitedListeners = null;
203 return true;
204 }
205 }
206 }
207 return false;
208 }
209
210 public final Automaton.State visit() {
211 if (this.transitionVisitedListeners!=null) {
212 Iterator it = this.transitionVisitedListeners.iterator();
213 for (int i=this.transitionVisitedListeners.size(); i>0; --i)
214 ((ITransitionVisitedListener)it.next()).transitionVisited(this);
215 }
216 return this.toState;
217 }
218
219 private final void visit(LinkedSet_State statesToVisit) {
220 if (this.transitionVisitedListeners!=null) {
221 Iterator it = this.transitionVisitedListeners.iterator();
222 for (int i=this.transitionVisitedListeners.size(); i>0; --i)
223 ((ITransitionVisitedListener)it.next()).transitionVisited(this);
224 }
225 statesToVisit.add(this.toState);
226 }
227
228
229 private final Automaton.State visit(char ch) {
230 if (this.transitionVisitedListeners!=null) {
231 Iterator it = this.transitionVisitedListeners.iterator();
232 for (int i=this.transitionVisitedListeners.size(); i>0; --i) {
233 ((ITransitionVisitedListener)it.next()).transitionVisited(this,ch);
234 }
235 }
236 return this.toState;
237 }
238
239 private final void visit(char ch,LinkedSet_State states) {
240 if (this.transitionVisitedListeners!=null) {
241 Iterator it = this.transitionVisitedListeners.iterator();
242 for (int i=this.transitionVisitedListeners.size(); i>0; --i)
243 ((ITransitionVisitedListener)it.next()).transitionVisited(this,ch);
244 }
245 states.add(this.toState);
246 }
247
248
249 public final ISet_char charSet;
250 public final State toState;
251
252 public IProperties properties = null;
253
254 public Transition next = null;
255
256
263 protected Transition(IProperties properties,ISet_char charSet,State toState) {
264 if (toState==null) throw new IllegalArgumentException ("toState==null");
265
266 this.properties = properties;
267 this.charSet = charSet;
268 this.toState = toState;
269 }
270
271
272 public State getFromState() {
273 return State.this;
274 }
275
276 public State getToState() {
277 return this.toState;
278 }
279
280 public ISet_char getCharSet() {
281 return this.charSet;
282 }
283
284 public String toString() {
285 final StringBuffer buffer = new StringBuffer ();
286
287 buffer.append(State.this);
288
289 if (this.charSet==null) {
290 if (this.properties==null) buffer.append(" --> ");
291 else buffer.append(" -").append(this.properties).append(": -> ");
292 } else {
293 if (this.properties==null) buffer.append(" -").append(this.charSet).append("-> ");
294 else buffer.append(" -").append(this.properties).append(':').append(this.charSet).append("-> ");
295 }
296
297 buffer.append(this.toState);
298
299 return buffer.toString();
300 }
301 }
303
304
308 public transient int stateNr;
309
310 {
311 this.stateNr = Automaton.this.currentStateNr++;
315
316 }
319
320
321 public Transition transitions = null;
322 public Transition eTransitions = null;
323
324 private transient int isDeterministic = State.TRUE;
325 private transient SoftReference nDetInterCharSet = null;
326
327 protected State() {}
328
329
330
344
345 protected Automaton parent() {
346 return Automaton.this;
347 }
348
349 protected Transition addTransition(IProperties properties,ISet_char charSet,State toState) {
350 final Transition result = new Transition(properties,charSet,toState);
351 this.addTransition(result);
352 return result;
353 }
354
355 protected void addTransition(Transition trans) {
356 if (trans.charSet==null) {
357 trans.next = this.eTransitions;
358 this.eTransitions = trans;
359 Automaton.this.isDeterministic = Automaton.FALSE;
360 } else {
361 trans.next = this.transitions;
362 this.transitions = trans;
363
364 if (this.isDeterministic==State.TRUE) this.isDeterministic = State.UNKNOWN;
365 if (Automaton.this.isDeterministic==Automaton.TRUE) Automaton.this.isDeterministic = Automaton.UNKNOWN;
366 }
367
368 if (this.changedListeners!=null) {
369 final Iterator it = this.changedListeners.iterator();
370 for (int i=this.changedListeners.size(); i>0; --i) {
371 ((IStateChangedListener)it.next()).transitionAdded(trans);
372 }
373 }
374 }
375
376 protected boolean removeTransition(Transition transition) {
377 if (transition.getFromState()!=this) throw new IllegalArgumentException ("transition.getFromState()!=this");
378
379 if (transition.charSet==null) {
380 for (Transition prevTrans=null, trans=this.eTransitions; trans!=null; prevTrans=trans, trans=trans.next) {
381 if (trans==transition) {
382 if (prevTrans==null) this.eTransitions = trans.next;
383 else prevTrans.next = trans.next;
384
385 if (Automaton.this.isDeterministic==Automaton.FALSE) Automaton.this.isDeterministic = Automaton.UNKNOWN;
386
387 if (this.changedListeners!=null) {
388 final Iterator it = this.changedListeners.iterator();
389 for (int i=this.changedListeners.size(); i>0; --i) {
390 ((IStateChangedListener)it.next()).transitionRemoved(transition);
391 }
392 }
393 return true;
394 }
395 }
396 } else {
397 for (Transition prevTrans=null, trans=this.transitions; trans!=null; prevTrans=trans, trans=trans.next) {
398 if (trans==transition) {
399 if (prevTrans==null) this.transitions = trans.next;
400 else prevTrans.next = trans.next;
401
402 if (this.isDeterministic==State.FALSE) this.isDeterministic = State.UNKNOWN;
403 if (Automaton.this.isDeterministic==Automaton.FALSE) Automaton.this.isDeterministic = Automaton.UNKNOWN;
404
405 if (this.changedListeners!=null) {
406 final Iterator it = this.changedListeners.iterator();
407 for (int i=this.changedListeners.size(); i>0; --i) {
408 ((IStateChangedListener)it.next()).transitionRemoved(transition);
409 }
410 }
411 return true;
412 }
413 }
414 }
415 return false;
416 }
417
418 protected void removeAllTransitions() {
419 for (Transition trans=this.eTransitions; trans!=null; trans=trans.next) {
420 this.removeTransition(trans);
421 }
422 for (Transition trans=this.transitions; trans!=null; trans=trans.next) {
423 this.removeTransition(trans);
424 }
425 }
426
427
428 protected void setDeterministic(Boolean isDeterministic) {
429 if (isDeterministic==null) this.isDeterministic = State.UNKNOWN;
430 if (isDeterministic.booleanValue()) this.isDeterministic = State.TRUE;
431 else this.isDeterministic = State.FALSE;
432 }
433
434 public final boolean isDeterministic() {
437 switch(this.isDeterministic) {
438 case State.TRUE : return true;
439 case State.FALSE : return false;
440 case State.UNKNOWN : {
441 if (this.transitions==null) {
442 this.isDeterministic = State.TRUE;
443 return true;
444 }
445 final ISet_char charSet = (ISet_char)this.transitions.charSet.clone();
446 for (Transition trans=this.transitions.next; trans!=null; trans=trans.next) {
447 int oldSize = charSet.size();
448 charSet.addAll(trans.charSet);
449 int newSize = charSet.size();
450 if (newSize-oldSize<trans.charSet.size()) {
451 this.isDeterministic = State.FALSE;
452 return false;
453 }
454 }
455
456 this.isDeterministic = State.TRUE;
457 return true;
458 }
459
460 default :
461 throw new Error ("Unknown deterministic state: "+this.isDeterministic);
462 }
463 }
464
465 public final IState next(char ch) {
466 this.unVisit();
467 if (this.isDeterministic()) {
468
469 for (Transition trans=this.transitions; trans!=null; trans=trans.next) {
470 if (trans.charSet.contains(ch)) {
471 final Automaton.State toState = trans.visit(ch);
472
473 if (toState.eTransitions==null) {
474 if (toState.visitedListeners!=null) {
475 final Iterator it = this.visitedListeners.iterator();
476 for (int i=this.visitedListeners.size(); i>0; --i)
477 ((IStateVisitedListener)it.next()).stateVisited(toState,ch);
478 }
479 return toState;
480 } else {
481 final LinkedSet_State statesToVisit = Automaton.this.newLinkedSet_State(toState);
482 for (Wrapper_State w=statesToVisit.elements; w!=null; w=w.next) {
483 if (w.state.visitedListeners!=null) {
484 final Iterator it = w.state.visitedListeners.iterator();
485 for (int i=w.state.visitedListeners.size(); i>0; --i)
486 ((IStateVisitedListener)it.next()).stateVisited(w.state,ch);
487 }
488
489 for (State.Transition t=w.state.eTransitions; t!=null; t=t.next) {
490 t.visit(statesToVisit);
491 }
492 }
493 return statesToVisit;
494 }
495 }
496 }
497 return null;
498
499 } else {
500
501 final LinkedSet_State statesToVisit = Automaton.this.newLinkedSet_State();
502 for (Transition trans=this.transitions; trans!=null; trans=trans.next) {
503 if (trans.charSet.contains(ch)) {
504 trans.visit(ch,statesToVisit);
505 }
506 }
507
508 for (Wrapper_State w=statesToVisit.elements; w!=null; w=w.next) {
509 if (w.state.visitedListeners!=null) {
510 final Iterator it = w.state.visitedListeners.iterator();
511 for (int i=w.state.visitedListeners.size(); i>0; --i)
512 ((IStateVisitedListener)it.next()).stateVisited(w.state,ch);
513 }
514
515 for (Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
516 trans.visit(statesToVisit);
517 }
518 }
519
520 switch(statesToVisit.size) {
521 case 0 : return null;
522 case 1 : return statesToVisit.elements.state;
523 default : return statesToVisit;
524 }
525 }
526
527 }
528
529 protected IState getEClosure() {
530 if (this.eTransitions==null) return this;
531
532 final LinkedSet_State eClosure = Automaton.this.newLinkedSet_State(this);
533 for (Wrapper_State w=eClosure.elements; w!=null; w=w.next) {
534 for(Transition trans=w.state.eTransitions; trans!=null; trans=trans.next)
535 eClosure.add(trans.toState);
536 }
537 switch(eClosure.size) {
538 case 1 : return eClosure.elements.state;
539 default : return eClosure;
540 }
541 }
542
543 protected void addEClosure(LinkedSet_State eClosure) {
544 eClosure.add(this);
545
546 Wrapper_State w=eClosure.lastElement;
547
548 for(Transition trans=this.eTransitions; trans!=null; trans=trans.next)
549 eClosure.add(trans.toState);
550
551 for (w=w.next; w!=null; w=w.next) {
552 for(Transition trans=w.state.eTransitions; trans!=null; trans=trans.next)
553 eClosure.add(trans.toState);
554 }
555 }
556
557
561
562 public LinkedSet_State getAllReachableStates() {
563 final LinkedSet_State states = new LinkedSet_State();
564
565 for(Transition trans=this.eTransitions; trans!=null; trans=trans.next) {
566 states.add(trans.toState);
567 }
568
569 for(Transition trans=this.transitions; trans!=null; trans=trans.next) {
570 if (trans.charSet.isEmpty()==false) states.add(trans.toState);
571 }
572
573 for (Wrapper_State w=states.elements; w!=null; w=w.next) {
574 for(Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
575 states.add(trans.toState);
576 }
577 for(Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
578 if (trans.charSet.isEmpty()==false) states.add(trans.toState);
579 }
580 }
581
582 return states;
583 }
584
585 public final Object clone() {
586 return Automaton.this.cloneState(this).get(this);
587 }
588
589 public String toString() {
590 return Automaton.this.automatonNr+".("+String.valueOf(this.stateNr)+')';
591 }
592
593 }
595
596
597
600 public class LinkedSet_State implements IState {
602
612
613 public Wrapper_State elements = null;
614 protected Wrapper_State lastElement = null;
615
616 transient int size = 0;
617 transient int hashCode = 0;
618 transient boolean hashCodeIsValid = true;
619
620 public LinkedSet_State(){}
621
622 public LinkedSet_State(Automaton.State state) {
623 this.add(state);
624 }
625
626 public boolean add(Automaton.State state) {
627 if (this.size!=0 && this.elements.state.parent()!=state.parent()) throw new IllegalArgumentException ("this.elements.state.parent()!=state.parent()");
629
630 if (this.contains(state)) return false;
631
632 if (this.lastElement==null) {
633 this.elements = new Wrapper_State(state);
634 this.lastElement = this.elements;
635 } else {
636 this.lastElement.next = new Wrapper_State(state);
637 this.lastElement = this.lastElement.next;
638 }
639 this.hashCodeIsValid = false;
640 ++this.size;
641 return true;
642 }
643
644
645 public void addAll(LinkedSet_State states) {
646 for (Wrapper_State wrapper=states.elements; wrapper!=null; wrapper=wrapper.next) {
647 this.add(wrapper.state);
648 }
649 }
650
651 public void addAll(IState state) {
652 if (state instanceof State) this.add((State)state);
653 else this.addAll((LinkedSet_State)state);
654 }
655
656
657 public boolean remove(Automaton.State state) {
658 if (this.size!=0 && this.elements.state.parent()!=state.parent()) throw new IllegalArgumentException ("this.elements.state.parent()!=state.parent()");
660
661 Wrapper_State prev = null;
662 for (Wrapper_State wrapper=this.elements; wrapper!=null; wrapper=wrapper.next) {
663 if (wrapper.state==state) {
664 if (prev==null) this.elements = wrapper.next;
665 else prev.next = wrapper.next;
666
667 if (wrapper==this.lastElement) this.lastElement = prev;
668
669 this.hashCodeIsValid = false;
670 --this.size;
671 return true;
672 }
673 prev = wrapper;
674 }
675 return false;
676 }
677
695
696 public boolean contains(Automaton.State state) {
697 if (this.size!=0 && this.elements.state.parent()!=state.parent()) throw new IllegalArgumentException ("this.elements.state.parent()!=state.parent()");
699
700 for (Wrapper_State wrapper=this.elements; wrapper!=null; wrapper=wrapper.next) {
701 if (wrapper.state==state) return true;
702 }
703 return false;
704 }
705
706 public void clear() {
707 this.elements = null;
708 this.lastElement = null;
709 this.size = 0;
710 }
711
712 public int size() {
713 return this.size;
714 }
715
716 public boolean isEmpty() {
717 return this.size==0;
718 }
719
748 public boolean equals(Object obj) {
749 try {
750 return this.equals((LinkedSet_State)obj);
751 } catch(ClassCastException e) {
752 if ((obj instanceof LinkedSet_State)==false) throw new IllegalArgumentException ("obj not instanceof LinkedSet_State");
753 throw e;
754 }
755 }
756
757 public boolean equals(LinkedSet_State set) {
758 if (this==set) return true;
759 try {
760 if (this.size!=set.size) return false;
761 for (Wrapper_State wrapper=set.elements; wrapper!=null; wrapper=wrapper.next) {
762 if (this.contains(wrapper.state)==false) return false;
763 }
764 return true;
765 } catch(NullPointerException e) {
766 if (set==null) throw new IllegalArgumentException ("set==null");
767 throw e;
768 }
769 }
770
771 public int hashCode() {
772 if (this.hashCodeIsValid==false) {
773 long hash = 0;
774 for (Wrapper_State wrapper=this.elements; wrapper!=null; wrapper=wrapper.next) {
775 hash+= wrapper.state.hashCode();
777 }
778
779 this.hashCode = (int)(hash % 4294967291L);
780 }
781 return this.hashCode;
782 }
783
784 public Object clone() {
785 try {
786 final LinkedSet_State clone = (LinkedSet_State)super.clone();
787 clone.clear();
788 clone.addAll(this);
789 return clone;
790 } catch(CloneNotSupportedException e) {
791 throw new Error ();
792 }
793 }
794
795 public String toString() {
796 final StringBuffer result = new StringBuffer ();
797 result.append('(');
798 for (Wrapper_State wrapper=this.elements; wrapper!=null; wrapper=wrapper.next) {
799 if (wrapper!=this.elements) result.append(", ");
800 result.append(wrapper.state.toString());
801 }
802 result.append(')');
803 return result.toString();
804 }
805
806
808 public LinkedSet_State getAllReachableStates() {
809 Wrapper_State wrapper=this.elements;
811
812 for (int i=this.size; i>0; --i) {
813 for (State.Transition trans=wrapper.state.transitions; trans!=null; trans=trans.next) {
814 this.add(trans.toState);
815 }
816 wrapper=wrapper.next;
817 }
818
819 for (; wrapper!=null; wrapper=wrapper.next) {
820 for (State.Transition trans=wrapper.state.eTransitions; trans!=null; trans=trans.next) {
821 this.add(trans.toState);
822 }
823 for (State.Transition trans=wrapper.state.transitions; trans!=null; trans=trans.next) {
824 this.add(trans.toState);
825 }
826 }
827
828 return this;
829 }
830
831 public final IState next(char ch) {
832 final LinkedSet_State statesToVisit = Automaton.this.newLinkedSet_State();
833
834 for (Wrapper_State w=this.elements; w!=null; w=w.next) w.state.unVisit();
835
836 for (Wrapper_State w=this.elements; w!=null; w=w.next) {
837 if (w.state.isDeterministic()) {
838 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
839 if (trans.charSet.contains(ch)) {
840 trans.visit(ch,statesToVisit);
841 break;
842 }
843 }
844 } else {
845 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
846 if (trans.charSet.contains(ch)) trans.visit(ch,statesToVisit);
847 }
848 }
849 }
850
851 for (Wrapper_State w=statesToVisit.elements; w!=null; w=w.next) {
852 if (w.state.visitedListeners!=null) {
853 final Iterator it = w.state.visitedListeners.iterator();
854 for (int i=w.state.visitedListeners.size(); i>0; --i)
855 ((IStateVisitedListener)it.next()).stateVisited(w.state,ch);
856 }
857
858 for (State.Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
859 trans.visit(statesToVisit);
860 }
861 }
862 switch(statesToVisit.size) {
863 case 0 : return null;
864 case 1 : return statesToVisit.elements.state;
865 default: return statesToVisit;
866 }
867 }
868 }
870
871
875 protected State startState = null;
876 protected LinkedSet_State aStates = new LinkedSet_State();
877 protected int isDeterministic = Automaton.TRUE;
878
879 protected int automatonNr = Automaton.currentAutomatonNr++;
880 protected int currentStateNr = 0;
881
882 protected abstract LinkedSet_State newLinkedSet_State();
883 protected abstract LinkedSet_State newLinkedSet_State(State state);
884
885 protected State createState() {
886 return new State();
887 }
888
889 protected void setDeterminstic(Boolean isDeterministic) {
890 if (isDeterministic==null) this.isDeterministic = Automaton.UNKNOWN;
891 if (isDeterministic.booleanValue()) this.isDeterministic = Automaton.TRUE;
892 else this.isDeterministic = Automaton.FALSE;
893 }
894
895 protected boolean isDeterministic() {
896
910 if (this.startState==null || this.isDeterministic(this.startState)) {
911 this.isDeterministic = Automaton.TRUE;
912 return true;
913 } else {
914 this.isDeterministic = Automaton.FALSE;
915 return false;
916 }
917 }
918
919 protected boolean isDeterministic(State startState) {
920 final LinkedSet_State reachableStates = new LinkedSet_State(startState);
921 for (Wrapper_State w=reachableStates.elements; w!=null; w=w.next) {
922 if (w.state.eTransitions!=null || w.state.isDeterministic()==false)
923 return false;
924
925 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
926 reachableStates.add(trans.toState);
927 }
928 }
929 return true;
930 }
931
932 protected State addState() {
933 final State result = this.createState();
934 this.addState(result);
935 return result;
936 }
937
938 protected void setStartState(State startState) {
939 if (startState==this.startState) return;
940
941 if (startState!=null) {
943 if (startState.parent()!=this) throw new IllegalArgumentException ("startState.parent()!=this");
944 if (this.aStates.contains(startState)==false)
945 throw new IllegalArgumentException ("this.states.contains(startState="+startState+")==false");
946 }
947
948 final State oldStartState = this.startState;
949 this.startState = startState;
950
951 this.isDeterministic = Automaton.UNKNOWN;
952
953 if (this.listeners!=null) {
955 final Iterator it = this.listeners.iterator();
956 for (int i=this.listeners.size(); i>0; --i) {
957 ((IChangedListener)it.next()).startStateChanged(oldStartState,startState);
958 }
959 }
960
961 }
962
963 protected State getStartState() {
964 return this.startState;
965 }
966
967 protected void addState(State state) {
968 if (state.parent()!=this) throw new IllegalArgumentException ("state.parent()!=this");
970 this.aStates.add(state);
971
972 if (this.listeners!=null) {
974 final Iterator it = this.listeners.iterator();
975 for (int i=this.listeners.size(); i>0; --i) {
976 ((IChangedListener)it.next()).stateAdded(state);
977 }
978 }
979 }
980
981 protected boolean removeState(State removeState) {
982 if (removeState.parent()!=this) throw new IllegalArgumentException ("removeState.parent()!=this");
984
985 if (this.startState==removeState) this.setStartState(null);
986
987 for (Wrapper_State w=this.aStates.elements; w!=null; w=w.next) {
988 if (w.state!=removeState) {
989 for (State.Transition trans=w.state.transitions; trans!=null; trans = trans.next) {
990 if (trans.toState==removeState) w.state.removeTransition(trans);
991 }
992 for (State.Transition trans=w.state.eTransitions; trans!=null; trans = trans.next) {
993 if (trans.toState==removeState) w.state.removeTransition(trans);
994 }
995 }
996 }
997
998 if (this.aStates.remove(removeState)==false) return false;
999
1000 if (this.listeners!=null) {
1002 final Iterator it = this.listeners.iterator();
1003 for (int i=this.listeners.size(); i>0; --i) {
1004 ((IChangedListener)it.next()).stateRemoved(removeState);
1005 }
1006 }
1007
1008 return true;
1009 }
1010
1028
1029 protected void removeUnreachableStates() {
1030 if (this.startState==null) return;
1031
1032 LinkedSet_State states = this.startState.getAllReachableStates();
1033 states.add(this.startState);
1034 for (Wrapper_State w=this.aStates.elements; w!=null; w=w.next) {
1035 if (states.contains(w.state)==false) this.removeState(w.state);
1036 }
1037 }
1038
1039
1040 protected void clear() {
1041 for (Wrapper_State w=this.aStates.elements; w!=null; w=w.next) {
1042 this.removeState(w.state);
1043 }
1044 }
1045
1046 protected java.util.Map cloneState(State state) {
1047 final HashMap map = new HashMap();
1048 final LinkedSet_State states = new LinkedSet_State(state);
1049 for (Wrapper_State w=states.elements; w!=null; w=w.next) {
1050 for (State.Transition trans=w.state.eTransitions; trans!=null; trans=trans.next)
1051 states.add(trans.toState);
1052
1053 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next)
1054 states.add(trans.toState);
1055
1056 map.put(w.state,this.addState());
1057 }
1058 for (Wrapper_State w=states.elements; w!=null; w=w.next) {
1059 State newState = (State)map.get(w.state);
1060 for (State.Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
1061 if (trans.properties==null)
1062 newState.addTransition(null,null,(State)map.get(trans.toState));
1063 else
1064 newState.addTransition((IProperties)trans.properties.clone(),null,(State)map.get(trans.toState));
1065 }
1066 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
1067 if (trans.properties==null)
1068 newState.addTransition(null,(ISet_char)trans.charSet.clone(),(State)map.get(trans.toState));
1069 else
1070 newState.addTransition((IProperties)trans.properties.clone(),(ISet_char)trans.charSet.clone(),(State)map.get(trans.toState));
1071 }
1072 }
1073
1074 return map;
1075 }
1076
1077 protected java.util.Map cloneStates(LinkedSet_State states) {
1078 final HashMap map = new HashMap();
1079
1093
1094 for (Wrapper_State w=states.elements; w!=null; w=w.next) {
1095 map.put(w.state,this.addState());
1096 }
1097
1098 for (Wrapper_State w=states.elements; w!=null; w=w.next) {
1099 State newState = (State)map.get(w.state);
1100 for (State.Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
1101 if (trans.properties==null)
1102 newState.addTransition(null,null,(State)map.get(trans.toState));
1103 else
1104 newState.addTransition((IProperties)trans.properties.clone(),null,(State)map.get(trans.toState));
1105 }
1106 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
1107 if (trans.properties==null)
1108 newState.addTransition(null,(ISet_char)trans.charSet.clone(),(State)map.get(trans.toState));
1109 else
1110 newState.addTransition((IProperties)trans.properties.clone(),(ISet_char)trans.charSet.clone(),(State)map.get(trans.toState));
1111 }
1112 }
1113
1114 return map;
1115 }
1116
1117
1118 public String toString() {
1119 final StringBuffer buffer = new StringBuffer ();
1120
1121 for (Wrapper_State w=this.aStates.elements; w!=null; w=w.next) {
1122 buffer.append(" \n").append(w.state);
1123
1124 if (w.state==this.startState) buffer.append('+');
1125
1126 for (State.Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
1127 buffer.append(" \n -");
1128 if (trans.properties!=null) buffer.append(trans.properties).append(": ");
1129 buffer.append("-> ").append(trans.toState);
1130 }
1131
1132 for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
1133 buffer.append(" \n -");
1134 if (trans.properties!=null) buffer.append(trans.properties).append(": ");
1135 buffer.append(trans.charSet).append("-> ").append(trans.toState);
1136 }
1137 }
1138
1139 return buffer.toString();
1140 }
1141
1142
1143
1144 protected Object clone() {
1145 try {
1146 Automaton clone = (Automaton)super.clone();
1147 clone.automatonNr = Automaton.currentAutomatonNr++;
1148 clone.currentStateNr = 0;
1149 clone.startState = null;
1150 clone.listeners = null;
1151 clone.aStates = clone.newLinkedSet_State();
1152
1153 final java.util.Map map = clone.cloneStates(this.aStates);
1154
1155 final Set keys = map.keySet();
1156 final Iterator it = keys.iterator();
1157 for (int i=keys.size(); i>0; --i) {
1158 State oldState = (State)it.next();
1159 State newState = (State)map.get(oldState);
1160 newState.stateNr = oldState.stateNr;
1161 if (clone.currentStateNr<=newState.stateNr)
1162 clone.currentStateNr = newState.stateNr+1;
1163 }
1164
1165 if (this.startState!=null)
1166 clone.setStartState((State)map.get(this.startState));
1167
1168 return clone;
1169 } catch(CloneNotSupportedException e) {
1170 throw new Error ();
1171 }
1172 }
1173
1174
1175
1176}
1177 |
Popular Tags |
Java API By Example, From Geeks To Geeks.