0001: /*
0002: * 01/07/2003 - 15:19:32
0003: *
0004: * Automaton.java -
0005: * Copyright (C) 2003 Buero fuer Softwarearchitektur GbR
0006: * ralf.meyer@karneim.com
0007: * http://jrexx.sf.net
0008: *
0009: * This program is free software; you can redistribute it and/or
0010: * modify it under the terms of the GNU Lesser General Public License
0011: * as published by the Free Software Foundation; either version 2
0012: * of the License, or (at your option) any later version.
0013: *
0014: * This program is distributed in the hope that it will be useful,
0015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
0016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0017: * GNU Lesser General Public License for more details.
0018: *
0019: * You should have received a copy of the GNU Lesser General Public License
0020: * along with this program; if not, write to the Free Software
0021: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
0022: */
0023: package com.tc.jrexx.automaton;
0024:
0025: import java.util.*;
0026: import java.lang.ref.SoftReference;
0027:
0028: import com.tc.jrexx.set.ISet_char;
0029:
0030: public abstract class Automaton implements Cloneable {
0031:
0032: protected final static int TRUE = 1;
0033: protected final static int FALSE = 0;
0034: protected final static int UNKNOWN = -1;
0035:
0036: private static int currentAutomatonNr = 0;
0037:
0038: // static final com.karneim.util.BitSet BITSET = new com.karneim.util.BitSet();
0039:
0040: public interface IChangedListener {
0041: public void stateAdded(State state);
0042:
0043: public void stateRemoved(State state);
0044:
0045: public void startStateChanged(State oldStartState,
0046: State newStartState);
0047: }
0048:
0049: protected LinkedList listeners = null;
0050:
0051: protected void addChangedListener(
0052: Automaton.IChangedListener listener) {
0053: if (listener == null)
0054: throw new IllegalArgumentException("listener==null");
0055: if (this .listeners == null)
0056: this .listeners = new LinkedList();
0057: this .listeners.add(listener);
0058: }
0059:
0060: protected boolean removeChangedListener(
0061: Automaton.IChangedListener listener) {
0062: if (this .listeners != null) {
0063: final Iterator it = this .listeners.iterator();
0064: for (int i = this .listeners.size(); i > 0; --i) {
0065: if (listener == it.next()) {
0066: if (this .listeners.size() > 1)
0067: it.remove();
0068: else
0069: this .listeners = null;
0070:
0071: return true;
0072: }
0073: }
0074: }
0075: return false;
0076: }
0077:
0078: public interface IStateVisitedListener {
0079: public void stateVisited(Automaton.State state);
0080:
0081: public void stateVisited(Automaton.State state, char ch);
0082:
0083: public void stateUnVisited(Automaton.State state);
0084: }
0085:
0086: public interface IStateChangedListener {
0087: public void transitionAdded(
0088: Automaton.State.Transition transition);
0089:
0090: public void transitionRemoved(
0091: Automaton.State.Transition transition);
0092: }
0093:
0094: public interface ITransitionVisitedListener {
0095: public void transitionVisited(
0096: Automaton.State.Transition transition);
0097:
0098: public void transitionVisited(
0099: Automaton.State.Transition transition, char ch);
0100: }
0101:
0102: public static final class Wrapper_State {
0103: public final State state;
0104: public Wrapper_State next = null;
0105:
0106: public Wrapper_State(State state) {
0107: this .state = state;
0108: }
0109: }
0110:
0111: public interface IState extends Cloneable {
0112: public IState next(char ch);
0113:
0114: public LinkedSet_State getAllReachableStates();
0115:
0116: public Object clone();
0117: }
0118:
0119: public class State implements IState {
0120: private final static int TRUE = 1;
0121: private final static int FALSE = 0;
0122: private final static int UNKNOWN = -1;
0123:
0124: transient protected LinkedList visitedListeners = null;
0125: transient protected LinkedList changedListeners = null;
0126:
0127: public void addVisitedListener(IStateVisitedListener listener) {
0128: if (this .visitedListeners == null)
0129: this .visitedListeners = new LinkedList();
0130: this .visitedListeners.add(listener);
0131: }
0132:
0133: public boolean removeVisitedListener(
0134: IStateVisitedListener listener) {
0135: if (this .visitedListeners != null) {
0136: final Iterator it = this .visitedListeners.iterator();
0137: for (int i = this .visitedListeners.size(); i > 0; --i) {
0138: if (listener == it.next()) {
0139: if (this .visitedListeners.size() > 1)
0140: it.remove();
0141: else
0142: this .visitedListeners = null;
0143:
0144: return true;
0145: }
0146: }
0147: }
0148: return false;
0149: }
0150:
0151: public void addChangedListener(IStateChangedListener listener) {
0152: if (this .changedListeners == null)
0153: this .changedListeners = new LinkedList();
0154: this .changedListeners.add(listener);
0155: }
0156:
0157: public boolean removeChangedListener(
0158: IStateChangedListener listener) {
0159: if (this .changedListeners != null) {
0160: final Iterator it = this .changedListeners.iterator();
0161: for (int i = this .changedListeners.size(); i > 0; --i) {
0162: if (listener == it.next()) {
0163: if (this .changedListeners.size() > 1)
0164: it.remove();
0165: else
0166: this .changedListeners = null;
0167:
0168: return true;
0169: }
0170: }
0171: }
0172: return false;
0173: }
0174:
0175: public final IState visit() {
0176: if (this .eTransitions == null) {
0177: if (this .visitedListeners != null) {
0178: final Iterator it = this .visitedListeners
0179: .iterator();
0180: for (int i = this .visitedListeners.size(); i > 0; --i)
0181: ((IStateVisitedListener) it.next())
0182: .stateVisited(this );
0183: }
0184: return this ;
0185: }
0186:
0187: final LinkedSet_State eClosure = Automaton.this
0188: .newLinkedSet_State(this );
0189: for (Wrapper_State w = eClosure.elements; w != null; w = w.next) {
0190: if (w.state.visitedListeners != null) {
0191: final Iterator it = w.state.visitedListeners
0192: .iterator();
0193: for (int i = w.state.visitedListeners.size(); i > 0; --i)
0194: ((IStateVisitedListener) it.next())
0195: .stateVisited(w.state);
0196: }
0197:
0198: for (Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
0199: trans.visit(eClosure);
0200: }
0201: }
0202:
0203: return eClosure;
0204: }
0205:
0206: protected final void unVisit() {
0207: if (this .visitedListeners != null) {
0208: final Iterator it = this .visitedListeners.iterator();
0209: for (int i = this .visitedListeners.size(); i > 0; --i)
0210: ((IStateVisitedListener) it.next())
0211: .stateUnVisited(this );
0212: }
0213: }
0214:
0215: ///////////////////////////////////////////////////////////////////////////
0216: // T r a n s i t i o n
0217: ////////////////////////////////////////////////////////////////////////////
0218:
0219: public final class Transition {
0220:
0221: transient LinkedList transitionVisitedListeners = null;
0222:
0223: public void addVisitedListener(
0224: ITransitionVisitedListener listener) {
0225: if (this .transitionVisitedListeners == null)
0226: this .transitionVisitedListeners = new LinkedList();
0227: this .transitionVisitedListeners.add(listener);
0228: }
0229:
0230: public boolean removeVisitedListener(
0231: ITransitionVisitedListener listener) {
0232: if (this .transitionVisitedListeners != null) {
0233: Iterator it = this .transitionVisitedListeners
0234: .iterator();
0235: for (int i = this .transitionVisitedListeners.size(); i > 0; --i) {
0236: if (listener == it.next()) {
0237: if (this .transitionVisitedListeners.size() > 1)
0238: it.remove();
0239: else
0240: this .transitionVisitedListeners = null;
0241: return true;
0242: }
0243: }
0244: }
0245: return false;
0246: }
0247:
0248: public final Automaton.State visit() {
0249: if (this .transitionVisitedListeners != null) {
0250: Iterator it = this .transitionVisitedListeners
0251: .iterator();
0252: for (int i = this .transitionVisitedListeners.size(); i > 0; --i)
0253: ((ITransitionVisitedListener) it.next())
0254: .transitionVisited(this );
0255: }
0256: return this .toState;
0257: }
0258:
0259: private final void visit(LinkedSet_State statesToVisit) {
0260: if (this .transitionVisitedListeners != null) {
0261: Iterator it = this .transitionVisitedListeners
0262: .iterator();
0263: for (int i = this .transitionVisitedListeners.size(); i > 0; --i)
0264: ((ITransitionVisitedListener) it.next())
0265: .transitionVisited(this );
0266: }
0267: statesToVisit.add(this .toState);
0268: }
0269:
0270: private final Automaton.State visit(char ch) {
0271: if (this .transitionVisitedListeners != null) {
0272: Iterator it = this .transitionVisitedListeners
0273: .iterator();
0274: for (int i = this .transitionVisitedListeners.size(); i > 0; --i) {
0275: ((ITransitionVisitedListener) it.next())
0276: .transitionVisited(this , ch);
0277: }
0278: }
0279: return this .toState;
0280: }
0281:
0282: private final void visit(char ch, LinkedSet_State states) {
0283: if (this .transitionVisitedListeners != null) {
0284: Iterator it = this .transitionVisitedListeners
0285: .iterator();
0286: for (int i = this .transitionVisitedListeners.size(); i > 0; --i)
0287: ((ITransitionVisitedListener) it.next())
0288: .transitionVisited(this , ch);
0289: }
0290: states.add(this .toState);
0291: }
0292:
0293: public final ISet_char charSet;
0294: public final State toState;
0295:
0296: public IProperties properties = null;
0297:
0298: public Transition next = null;
0299:
0300: /**
0301: * constructs a Transition that can transit with charSet's chars to toState.
0302: * if charSet==null, the Transition will be an epsilon transition, which means
0303: * that there are no chars needed to get to toState; in other words a state that has an
0304: * epsilon transition can get through this epsilon transition to toState
0305: * without any char, so that we can say that toState melts into the state.
0306: */
0307: protected Transition(IProperties properties,
0308: ISet_char charSet, State toState) {
0309: if (toState == null)
0310: throw new IllegalArgumentException("toState==null");
0311:
0312: this .properties = properties;
0313: this .charSet = charSet;
0314: this .toState = toState;
0315: }
0316:
0317: public State getFromState() {
0318: return State.this ;
0319: }
0320:
0321: public State getToState() {
0322: return this .toState;
0323: }
0324:
0325: public ISet_char getCharSet() {
0326: return this .charSet;
0327: }
0328:
0329: public String toString() {
0330: final StringBuffer buffer = new StringBuffer();
0331:
0332: buffer.append(State.this );
0333:
0334: if (this .charSet == null) {
0335: if (this .properties == null)
0336: buffer.append(" --> ");
0337: else
0338: buffer.append(" -").append(this .properties)
0339: .append(": -> ");
0340: } else {
0341: if (this .properties == null)
0342: buffer.append(" -").append(this .charSet)
0343: .append("-> ");
0344: else
0345: buffer.append(" -").append(this .properties)
0346: .append(':').append(this .charSet)
0347: .append("-> ");
0348: }
0349:
0350: buffer.append(this .toState);
0351:
0352: return buffer.toString();
0353: }
0354: } // end class Transition
0355:
0356: //////////////////////////////////////////////////////////////////
0357: //////////////// S T A T E B O D Y //////////
0358: //////////////////////////////////////////////////////////////////
0359:
0360: public transient int stateNr;
0361:
0362: {
0363: // synchronized(Automaton.BITSET) {
0364: // this.stateNr = Automaton.BITSET.setAClearedBit(0);
0365: // }
0366: this .stateNr = Automaton.this .currentStateNr++;
0367:
0368: // if (this.stateNr<10) System.out.println("0"+this.stateNr+" "+Automaton.BITSET+" "+Automaton.BITSET.cardinality());
0369: // else System.out.println(this.stateNr+" "+Automaton.BITSET+" "+Automaton.BITSET.cardinality());
0370: }
0371:
0372: public Transition transitions = null;
0373: public Transition eTransitions = null;
0374:
0375: private transient int isDeterministic = State.TRUE;
0376: private transient SoftReference nDetInterCharSet = null;
0377:
0378: protected State() {
0379: }
0380:
0381: // protected void finalize() throws Throwable {
0382: // try {
0383: // super.finalize();
0384: // synchronized(Automaton.BITSET) {
0385: // Automaton.BITSET.clearBit(this.stateNr);
0386: // }
0387: // if (this.stateNr<10) System.out.println("-0"+this.stateNr+" "+Automaton.BITSET+" "+Automaton.BITSET.cardinality());
0388: // else System.out.println("-"+this.stateNr+" "+Automaton.BITSET+" "+Automaton.BITSET.cardinality());
0389: //
0390: // } catch(Throwable t) {
0391: // throw new RuntimeException(t.getMessage());
0392: // }
0393: // }
0394:
0395: protected Automaton parent() {
0396: return Automaton.this ;
0397: }
0398:
0399: protected Transition addTransition(IProperties properties,
0400: ISet_char charSet, State toState) {
0401: final Transition result = new Transition(properties,
0402: charSet, toState);
0403: this .addTransition(result);
0404: return result;
0405: }
0406:
0407: protected void addTransition(Transition trans) {
0408: if (trans.charSet == null) {
0409: trans.next = this .eTransitions;
0410: this .eTransitions = trans;
0411: Automaton.this .isDeterministic = Automaton.FALSE;
0412: } else {
0413: trans.next = this .transitions;
0414: this .transitions = trans;
0415:
0416: if (this .isDeterministic == State.TRUE)
0417: this .isDeterministic = State.UNKNOWN;
0418: if (Automaton.this .isDeterministic == Automaton.TRUE)
0419: Automaton.this .isDeterministic = Automaton.UNKNOWN;
0420: }
0421:
0422: if (this .changedListeners != null) {
0423: final Iterator it = this .changedListeners.iterator();
0424: for (int i = this .changedListeners.size(); i > 0; --i) {
0425: ((IStateChangedListener) it.next())
0426: .transitionAdded(trans);
0427: }
0428: }
0429: }
0430:
0431: protected boolean removeTransition(Transition transition) {
0432: if (transition.getFromState() != this )
0433: throw new IllegalArgumentException(
0434: "transition.getFromState()!=this");
0435:
0436: if (transition.charSet == null) {
0437: for (Transition prevTrans = null, trans = this .eTransitions; trans != null; prevTrans = trans, trans = trans.next) {
0438: if (trans == transition) {
0439: if (prevTrans == null)
0440: this .eTransitions = trans.next;
0441: else
0442: prevTrans.next = trans.next;
0443:
0444: if (Automaton.this .isDeterministic == Automaton.FALSE)
0445: Automaton.this .isDeterministic = Automaton.UNKNOWN;
0446:
0447: if (this .changedListeners != null) {
0448: final Iterator it = this .changedListeners
0449: .iterator();
0450: for (int i = this .changedListeners.size(); i > 0; --i) {
0451: ((IStateChangedListener) it.next())
0452: .transitionRemoved(transition);
0453: }
0454: }
0455: return true;
0456: }
0457: }
0458: } else {
0459: for (Transition prevTrans = null, trans = this .transitions; trans != null; prevTrans = trans, trans = trans.next) {
0460: if (trans == transition) {
0461: if (prevTrans == null)
0462: this .transitions = trans.next;
0463: else
0464: prevTrans.next = trans.next;
0465:
0466: if (this .isDeterministic == State.FALSE)
0467: this .isDeterministic = State.UNKNOWN;
0468: if (Automaton.this .isDeterministic == Automaton.FALSE)
0469: Automaton.this .isDeterministic = Automaton.UNKNOWN;
0470:
0471: if (this .changedListeners != null) {
0472: final Iterator it = this .changedListeners
0473: .iterator();
0474: for (int i = this .changedListeners.size(); i > 0; --i) {
0475: ((IStateChangedListener) it.next())
0476: .transitionRemoved(transition);
0477: }
0478: }
0479: return true;
0480: }
0481: }
0482: }
0483: return false;
0484: }
0485:
0486: protected void removeAllTransitions() {
0487: for (Transition trans = this .eTransitions; trans != null; trans = trans.next) {
0488: this .removeTransition(trans);
0489: }
0490: for (Transition trans = this .transitions; trans != null; trans = trans.next) {
0491: this .removeTransition(trans);
0492: }
0493: }
0494:
0495: protected void setDeterministic(Boolean isDeterministic) {
0496: if (isDeterministic == null)
0497: this .isDeterministic = State.UNKNOWN;
0498: if (isDeterministic.booleanValue())
0499: this .isDeterministic = State.TRUE;
0500: else
0501: this .isDeterministic = State.FALSE;
0502: }
0503:
0504: // checks whether this.transitions are deterministic
0505: // this.eTransitions are not checked!
0506: public final boolean isDeterministic() {
0507: switch (this .isDeterministic) {
0508: case State.TRUE:
0509: return true;
0510: case State.FALSE:
0511: return false;
0512: case State.UNKNOWN: {
0513: if (this .transitions == null) {
0514: this .isDeterministic = State.TRUE;
0515: return true;
0516: }
0517: final ISet_char charSet = (ISet_char) this .transitions.charSet
0518: .clone();
0519: for (Transition trans = this .transitions.next; trans != null; trans = trans.next) {
0520: int oldSize = charSet.size();
0521: charSet.addAll(trans.charSet);
0522: int newSize = charSet.size();
0523: if (newSize - oldSize < trans.charSet.size()) {
0524: this .isDeterministic = State.FALSE;
0525: return false;
0526: }
0527: }
0528:
0529: this .isDeterministic = State.TRUE;
0530: return true;
0531: }
0532:
0533: default:
0534: throw new Error("Unknown deterministic state: "
0535: + this .isDeterministic);
0536: }
0537: }
0538:
0539: public final IState next(char ch) {
0540: this .unVisit();
0541: if (this .isDeterministic()) {
0542:
0543: for (Transition trans = this .transitions; trans != null; trans = trans.next) {
0544: if (trans.charSet.contains(ch)) {
0545: final Automaton.State toState = trans.visit(ch);
0546:
0547: if (toState.eTransitions == null) {
0548: if (toState.visitedListeners != null) {
0549: final Iterator it = this .visitedListeners
0550: .iterator();
0551: for (int i = this .visitedListeners
0552: .size(); i > 0; --i)
0553: ((IStateVisitedListener) it.next())
0554: .stateVisited(toState, ch);
0555: }
0556: return toState;
0557: } else {
0558: final LinkedSet_State statesToVisit = Automaton.this
0559: .newLinkedSet_State(toState);
0560: for (Wrapper_State w = statesToVisit.elements; w != null; w = w.next) {
0561: if (w.state.visitedListeners != null) {
0562: final Iterator it = w.state.visitedListeners
0563: .iterator();
0564: for (int i = w.state.visitedListeners
0565: .size(); i > 0; --i)
0566: ((IStateVisitedListener) it
0567: .next()).stateVisited(
0568: w.state, ch);
0569: }
0570:
0571: for (State.Transition t = w.state.eTransitions; t != null; t = t.next) {
0572: t.visit(statesToVisit);
0573: }
0574: }
0575: return statesToVisit;
0576: }
0577: }
0578: }
0579: return null;
0580:
0581: } else {
0582:
0583: final LinkedSet_State statesToVisit = Automaton.this
0584: .newLinkedSet_State();
0585: for (Transition trans = this .transitions; trans != null; trans = trans.next) {
0586: if (trans.charSet.contains(ch)) {
0587: trans.visit(ch, statesToVisit);
0588: }
0589: }
0590:
0591: for (Wrapper_State w = statesToVisit.elements; w != null; w = w.next) {
0592: if (w.state.visitedListeners != null) {
0593: final Iterator it = w.state.visitedListeners
0594: .iterator();
0595: for (int i = w.state.visitedListeners.size(); i > 0; --i)
0596: ((IStateVisitedListener) it.next())
0597: .stateVisited(w.state, ch);
0598: }
0599:
0600: for (Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
0601: trans.visit(statesToVisit);
0602: }
0603: }
0604:
0605: switch (statesToVisit.size) {
0606: case 0:
0607: return null;
0608: case 1:
0609: return statesToVisit.elements.state;
0610: default:
0611: return statesToVisit;
0612: }
0613: }
0614:
0615: }
0616:
0617: protected IState getEClosure() {
0618: if (this .eTransitions == null)
0619: return this ;
0620:
0621: final LinkedSet_State eClosure = Automaton.this
0622: .newLinkedSet_State(this );
0623: for (Wrapper_State w = eClosure.elements; w != null; w = w.next) {
0624: for (Transition trans = w.state.eTransitions; trans != null; trans = trans.next)
0625: eClosure.add(trans.toState);
0626: }
0627: switch (eClosure.size) {
0628: case 1:
0629: return eClosure.elements.state;
0630: default:
0631: return eClosure;
0632: }
0633: }
0634:
0635: protected void addEClosure(LinkedSet_State eClosure) {
0636: eClosure.add(this );
0637:
0638: Wrapper_State w = eClosure.lastElement;
0639:
0640: for (Transition trans = this .eTransitions; trans != null; trans = trans.next)
0641: eClosure.add(trans.toState);
0642:
0643: for (w = w.next; w != null; w = w.next) {
0644: for (Transition trans = w.state.eTransitions; trans != null; trans = trans.next)
0645: eClosure.add(trans.toState);
0646: }
0647: }
0648:
0649: /**
0650: * returns all states that are reachable from this states transitions.
0651: * Note: this state is only element of the returned array, if it is reachable through one of it's transitions
0652: */
0653:
0654: public LinkedSet_State getAllReachableStates() {
0655: final LinkedSet_State states = new LinkedSet_State();
0656:
0657: for (Transition trans = this .eTransitions; trans != null; trans = trans.next) {
0658: states.add(trans.toState);
0659: }
0660:
0661: for (Transition trans = this .transitions; trans != null; trans = trans.next) {
0662: if (trans.charSet.isEmpty() == false)
0663: states.add(trans.toState);
0664: }
0665:
0666: for (Wrapper_State w = states.elements; w != null; w = w.next) {
0667: for (Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
0668: states.add(trans.toState);
0669: }
0670: for (Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0671: if (trans.charSet.isEmpty() == false)
0672: states.add(trans.toState);
0673: }
0674: }
0675:
0676: return states;
0677: }
0678:
0679: public final Object clone() {
0680: return Automaton.this .cloneState(this ).get(this );
0681: }
0682:
0683: public String toString() {
0684: return Automaton.this .automatonNr + ".("
0685: + String.valueOf(this .stateNr) + ')';
0686: }
0687:
0688: } // end class State
0689:
0690: //////////////////////////////////////////////////////////////////
0691: //////////////////////////////////////////////////////////////////
0692:
0693: // should be named IdentityLinkedSet_State
0694: public class LinkedSet_State implements IState {
0695: /*
0696: protected abstract class Iterator {
0697: Wrapper_State current = null;
0698: protected Automaton.State nextState() {
0699: if (this.current==null) this.current = LinkedSet_State.this.elements;
0700: else this.current = this.current.next;
0701: return (this.current==null) ? null : this.current.state;
0702: }
0703: }
0704: */
0705:
0706: public Wrapper_State elements = null;
0707: protected Wrapper_State lastElement = null;
0708:
0709: transient int size = 0;
0710: transient int hashCode = 0;
0711: transient boolean hashCodeIsValid = true;
0712:
0713: public LinkedSet_State() {
0714: }
0715:
0716: public LinkedSet_State(Automaton.State state) {
0717: this .add(state);
0718: }
0719:
0720: public boolean add(Automaton.State state) {
0721: // performance leak
0722: if (this .size != 0
0723: && this .elements.state.parent() != state.parent())
0724: throw new IllegalArgumentException(
0725: "this.elements.state.parent()!=state.parent()");
0726:
0727: if (this .contains(state))
0728: return false;
0729:
0730: if (this .lastElement == null) {
0731: this .elements = new Wrapper_State(state);
0732: this .lastElement = this .elements;
0733: } else {
0734: this .lastElement.next = new Wrapper_State(state);
0735: this .lastElement = this .lastElement.next;
0736: }
0737: this .hashCodeIsValid = false;
0738: ++this .size;
0739: return true;
0740: }
0741:
0742: public void addAll(LinkedSet_State states) {
0743: for (Wrapper_State wrapper = states.elements; wrapper != null; wrapper = wrapper.next) {
0744: this .add(wrapper.state);
0745: }
0746: }
0747:
0748: public void addAll(IState state) {
0749: if (state instanceof State)
0750: this .add((State) state);
0751: else
0752: this .addAll((LinkedSet_State) state);
0753: }
0754:
0755: public boolean remove(Automaton.State state) {
0756: // performance leak
0757: if (this .size != 0
0758: && this .elements.state.parent() != state.parent())
0759: throw new IllegalArgumentException(
0760: "this.elements.state.parent()!=state.parent()");
0761:
0762: Wrapper_State prev = null;
0763: for (Wrapper_State wrapper = this .elements; wrapper != null; wrapper = wrapper.next) {
0764: if (wrapper.state == state) {
0765: if (prev == null)
0766: this .elements = wrapper.next;
0767: else
0768: prev.next = wrapper.next;
0769:
0770: if (wrapper == this .lastElement)
0771: this .lastElement = prev;
0772:
0773: this .hashCodeIsValid = false;
0774: --this .size;
0775: return true;
0776: }
0777: prev = wrapper;
0778: }
0779: return false;
0780: }
0781:
0782: /*
0783: int removeAll(LinkedSet_State states) {
0784: int answer = 0;
0785: Wrapper_State prev = null;
0786: for (Wrapper_State wrapper=this.elements; wrapper!=null; wrapper=wrapper.next) {
0787: if (states.contains(wrapper.state)) {
0788: if (prev==null) this.elements = wrapper.next;
0789: else prev.next = wrapper.next;
0790:
0791: if (wrapper==this.lastElement) this.lastElement = prev;
0792: --this.size;
0793: if (++answer==states.size()) return answer;
0794: }
0795: prev = wrapper;
0796: }
0797: return answer;
0798: }
0799: */
0800:
0801: public boolean contains(Automaton.State state) {
0802: // performance leak
0803: if (this .size != 0
0804: && this .elements.state.parent() != state.parent())
0805: throw new IllegalArgumentException(
0806: "this.elements.state.parent()!=state.parent()");
0807:
0808: for (Wrapper_State wrapper = this .elements; wrapper != null; wrapper = wrapper.next) {
0809: if (wrapper.state == state)
0810: return true;
0811: }
0812: return false;
0813: }
0814:
0815: public void clear() {
0816: this .elements = null;
0817: this .lastElement = null;
0818: this .size = 0;
0819: }
0820:
0821: public int size() {
0822: return this .size;
0823: }
0824:
0825: public boolean isEmpty() {
0826: return this .size == 0;
0827: }
0828:
0829: /*
0830: public LinkedSet_State.Iterator stateIterator() {
0831: return new LinkedSet_State.Iterator() {
0832: Wrapper_State current = null;
0833: public Automaton.State next() {
0834: if (this.current==null) this.current = LinkedSet_State.this.elements;
0835: else this.current = this.current.next;
0836: return (this.current==null) ? null : this.current.state;
0837: }
0838: };
0839: }
0840:
0841: public LinkedSet_State.Iterator stateIterator(final int offset) {
0842: return new LinkedSet_State.Iterator() {
0843: Wrapper_State current = null;
0844: public Automaton.State next() {
0845: if (this.current==null) {
0846: this.current = LinkedSet_State.this.elements;
0847: try {
0848: for (int i=offset; i>0; --i) this.current = this.current.next;
0849: } catch(NullPointerException e) {
0850: if (this.current!=null) throw e;
0851: }
0852: } else this.current = this.current.next;
0853: return (this.current==null) ? null : this.current.state;
0854: }
0855: };
0856: }
0857: */
0858: public boolean equals(Object obj) {
0859: try {
0860: return this .equals((LinkedSet_State) obj);
0861: } catch (ClassCastException e) {
0862: if ((obj instanceof LinkedSet_State) == false)
0863: throw new IllegalArgumentException(
0864: "obj not instanceof LinkedSet_State");
0865: throw e;
0866: }
0867: }
0868:
0869: public boolean equals(LinkedSet_State set) {
0870: if (this == set)
0871: return true;
0872: try {
0873: if (this .size != set.size)
0874: return false;
0875: for (Wrapper_State wrapper = set.elements; wrapper != null; wrapper = wrapper.next) {
0876: if (this .contains(wrapper.state) == false)
0877: return false;
0878: }
0879: return true;
0880: } catch (NullPointerException e) {
0881: if (set == null)
0882: throw new IllegalArgumentException("set==null");
0883: throw e;
0884: }
0885: }
0886:
0887: public int hashCode() {
0888: if (this .hashCodeIsValid == false) {
0889: long hash = 0;
0890: for (Wrapper_State wrapper = this .elements; wrapper != null; wrapper = wrapper.next) {
0891: // hash = ( (hash<<32) + wrapper.state.hashCode() ) % 4294967291L;
0892: hash += wrapper.state.hashCode();
0893: }
0894:
0895: this .hashCode = (int) (hash % 4294967291L);
0896: }
0897: return this .hashCode;
0898: }
0899:
0900: public Object clone() {
0901: try {
0902: final LinkedSet_State clone = (LinkedSet_State) super
0903: .clone();
0904: clone.clear();
0905: clone.addAll(this );
0906: return clone;
0907: } catch (CloneNotSupportedException e) {
0908: throw new Error();
0909: }
0910: }
0911:
0912: public String toString() {
0913: final StringBuffer result = new StringBuffer();
0914: result.append('(');
0915: for (Wrapper_State wrapper = this .elements; wrapper != null; wrapper = wrapper.next) {
0916: if (wrapper != this .elements)
0917: result.append(", ");
0918: result.append(wrapper.state.toString());
0919: }
0920: result.append(')');
0921: return result.toString();
0922: }
0923:
0924: // implementing methods of IState
0925:
0926: public LinkedSet_State getAllReachableStates() {
0927: // this is very tricky
0928: Wrapper_State wrapper = this .elements;
0929:
0930: for (int i = this .size; i > 0; --i) {
0931: for (State.Transition trans = wrapper.state.transitions; trans != null; trans = trans.next) {
0932: this .add(trans.toState);
0933: }
0934: wrapper = wrapper.next;
0935: }
0936:
0937: for (; wrapper != null; wrapper = wrapper.next) {
0938: for (State.Transition trans = wrapper.state.eTransitions; trans != null; trans = trans.next) {
0939: this .add(trans.toState);
0940: }
0941: for (State.Transition trans = wrapper.state.transitions; trans != null; trans = trans.next) {
0942: this .add(trans.toState);
0943: }
0944: }
0945:
0946: return this ;
0947: }
0948:
0949: public final IState next(char ch) {
0950: final LinkedSet_State statesToVisit = Automaton.this
0951: .newLinkedSet_State();
0952:
0953: for (Wrapper_State w = this .elements; w != null; w = w.next)
0954: w.state.unVisit();
0955:
0956: for (Wrapper_State w = this .elements; w != null; w = w.next) {
0957: if (w.state.isDeterministic()) {
0958: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0959: if (trans.charSet.contains(ch)) {
0960: trans.visit(ch, statesToVisit);
0961: break;
0962: }
0963: }
0964: } else {
0965: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0966: if (trans.charSet.contains(ch))
0967: trans.visit(ch, statesToVisit);
0968: }
0969: }
0970: }
0971:
0972: for (Wrapper_State w = statesToVisit.elements; w != null; w = w.next) {
0973: if (w.state.visitedListeners != null) {
0974: final Iterator it = w.state.visitedListeners
0975: .iterator();
0976: for (int i = w.state.visitedListeners.size(); i > 0; --i)
0977: ((IStateVisitedListener) it.next())
0978: .stateVisited(w.state, ch);
0979: }
0980:
0981: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
0982: trans.visit(statesToVisit);
0983: }
0984: }
0985: switch (statesToVisit.size) {
0986: case 0:
0987: return null;
0988: case 1:
0989: return statesToVisit.elements.state;
0990: default:
0991: return statesToVisit;
0992: }
0993: }
0994: } // end class LinkedSet_State
0995:
0996: //////////////////////////////////////////////////////////////////////
0997: ///////////////// A U T O M A T O N B O D Y /////////////////////
0998: /////////////////////////////////////////////////////////////////////
0999:
1000: protected State startState = null;
1001: protected LinkedSet_State aStates = new LinkedSet_State();
1002: protected int isDeterministic = Automaton.TRUE;
1003:
1004: protected int automatonNr = Automaton.currentAutomatonNr++;
1005: protected int currentStateNr = 0;
1006:
1007: protected abstract LinkedSet_State newLinkedSet_State();
1008:
1009: protected abstract LinkedSet_State newLinkedSet_State(State state);
1010:
1011: protected State createState() {
1012: return new State();
1013: }
1014:
1015: protected void setDeterminstic(Boolean isDeterministic) {
1016: if (isDeterministic == null)
1017: this .isDeterministic = Automaton.UNKNOWN;
1018: if (isDeterministic.booleanValue())
1019: this .isDeterministic = Automaton.TRUE;
1020: else
1021: this .isDeterministic = Automaton.FALSE;
1022: }
1023:
1024: protected boolean isDeterministic() {
1025: /*
1026: switch(this.isDeterministic) {
1027: case Automaton.FALSE : return false;
1028: case Automaton.TRUE : return true;
1029: case Automaton.UNKNOWN :
1030: if (this.startState==null || this.isDeterministic(this.startState)) {
1031: this.isDeterministic = Automaton.TRUE;
1032: return true;
1033: } else {
1034: this.isDeterministic = Automaton.FALSE;
1035: return false;
1036: }
1037: }
1038: */
1039: if (this .startState == null
1040: || this .isDeterministic(this .startState)) {
1041: this .isDeterministic = Automaton.TRUE;
1042: return true;
1043: } else {
1044: this .isDeterministic = Automaton.FALSE;
1045: return false;
1046: }
1047: }
1048:
1049: protected boolean isDeterministic(State startState) {
1050: final LinkedSet_State reachableStates = new LinkedSet_State(
1051: startState);
1052: for (Wrapper_State w = reachableStates.elements; w != null; w = w.next) {
1053: if (w.state.eTransitions != null
1054: || w.state.isDeterministic() == false)
1055: return false;
1056:
1057: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
1058: reachableStates.add(trans.toState);
1059: }
1060: }
1061: return true;
1062: }
1063:
1064: protected State addState() {
1065: final State result = this .createState();
1066: this .addState(result);
1067: return result;
1068: }
1069:
1070: protected void setStartState(State startState) {
1071: if (startState == this .startState)
1072: return;
1073:
1074: // performance leak
1075: if (startState != null) {
1076: if (startState.parent() != this )
1077: throw new IllegalArgumentException(
1078: "startState.parent()!=this");
1079: if (this .aStates.contains(startState) == false)
1080: throw new IllegalArgumentException(
1081: "this.states.contains(startState=" + startState
1082: + ")==false");
1083: }
1084:
1085: final State oldStartState = this .startState;
1086: this .startState = startState;
1087:
1088: this .isDeterministic = Automaton.UNKNOWN;
1089:
1090: //inform listener
1091: if (this .listeners != null) {
1092: final Iterator it = this .listeners.iterator();
1093: for (int i = this .listeners.size(); i > 0; --i) {
1094: ((IChangedListener) it.next()).startStateChanged(
1095: oldStartState, startState);
1096: }
1097: }
1098:
1099: }
1100:
1101: protected State getStartState() {
1102: return this .startState;
1103: }
1104:
1105: protected void addState(State state) {
1106: // performance leak
1107: if (state.parent() != this )
1108: throw new IllegalArgumentException("state.parent()!=this");
1109: this .aStates.add(state);
1110:
1111: //inform listener
1112: if (this .listeners != null) {
1113: final Iterator it = this .listeners.iterator();
1114: for (int i = this .listeners.size(); i > 0; --i) {
1115: ((IChangedListener) it.next()).stateAdded(state);
1116: }
1117: }
1118: }
1119:
1120: protected boolean removeState(State removeState) {
1121: // performance leak
1122: if (removeState.parent() != this )
1123: throw new IllegalArgumentException(
1124: "removeState.parent()!=this");
1125:
1126: if (this .startState == removeState)
1127: this .setStartState(null);
1128:
1129: for (Wrapper_State w = this .aStates.elements; w != null; w = w.next) {
1130: if (w.state != removeState) {
1131: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
1132: if (trans.toState == removeState)
1133: w.state.removeTransition(trans);
1134: }
1135: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
1136: if (trans.toState == removeState)
1137: w.state.removeTransition(trans);
1138: }
1139: }
1140: }
1141:
1142: if (this .aStates.remove(removeState) == false)
1143: return false;
1144:
1145: //inform listener;
1146: if (this .listeners != null) {
1147: final Iterator it = this .listeners.iterator();
1148: for (int i = this .listeners.size(); i > 0; --i) {
1149: ((IChangedListener) it.next())
1150: .stateRemoved(removeState);
1151: }
1152: }
1153:
1154: return true;
1155: }
1156:
1157: /*
1158: protected int removeStates(LinkedSet_State removeStates) {
1159: for (Wrapper_State w=this.states.elements; w!=null; w=w.next) {
1160: if (removeStates.contains(w.state)==false) {
1161: for (State.Transition trans=w.state.transitions; trans!=null; trans = trans.next) {
1162: if (removeStates.contains(trans.toState)) w.state.removeTransition(trans);
1163: }
1164: for (State.Transition trans=w.state.eTransitions; trans!=null; trans = trans.next) {
1165: if (removeStates.contains(trans.toState)) w.state.removeTransition(trans);
1166: }
1167: }
1168: }
1169:
1170: //inform listener;
1171:
1172: return this.states.removeAll(removeStates);
1173: }
1174: */
1175:
1176: protected void removeUnreachableStates() {
1177: if (this .startState == null)
1178: return;
1179:
1180: LinkedSet_State states = this .startState
1181: .getAllReachableStates();
1182: states.add(this .startState);
1183: for (Wrapper_State w = this .aStates.elements; w != null; w = w.next) {
1184: if (states.contains(w.state) == false)
1185: this .removeState(w.state);
1186: }
1187: }
1188:
1189: protected void clear() {
1190: for (Wrapper_State w = this .aStates.elements; w != null; w = w.next) {
1191: this .removeState(w.state);
1192: }
1193: }
1194:
1195: protected java.util.Map cloneState(State state) {
1196: final HashMap map = new HashMap();
1197: final LinkedSet_State states = new LinkedSet_State(state);
1198: for (Wrapper_State w = states.elements; w != null; w = w.next) {
1199: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next)
1200: states.add(trans.toState);
1201:
1202: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next)
1203: states.add(trans.toState);
1204:
1205: map.put(w.state, this .addState());
1206: }
1207: for (Wrapper_State w = states.elements; w != null; w = w.next) {
1208: State newState = (State) map.get(w.state);
1209: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
1210: if (trans.properties == null)
1211: newState.addTransition(null, null, (State) map
1212: .get(trans.toState));
1213: else
1214: newState.addTransition(
1215: (IProperties) trans.properties.clone(),
1216: null, (State) map.get(trans.toState));
1217: }
1218: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
1219: if (trans.properties == null)
1220: newState.addTransition(null,
1221: (ISet_char) trans.charSet.clone(),
1222: (State) map.get(trans.toState));
1223: else
1224: newState.addTransition(
1225: (IProperties) trans.properties.clone(),
1226: (ISet_char) trans.charSet.clone(),
1227: (State) map.get(trans.toState));
1228: }
1229: }
1230:
1231: return map;
1232: }
1233:
1234: protected java.util.Map cloneStates(LinkedSet_State states) {
1235: final HashMap map = new HashMap();
1236: /*
1237: final LinkedSet_State XXX = new LinkedSet_State();
1238: XXX.addAll(states); // critical beacuse xxx has another parent than states
1239: for (Wrapper_State w=XXX.elements; w!=null; w=w.next) {
1240: for (State.Transition trans=w.state.eTransitions; trans!=null; trans=trans.next) {
1241: XXX.add(trans.toState);
1242: }
1243: for (State.Transition trans=w.state.transitions; trans!=null; trans=trans.next) {
1244: XXX.add(trans.toState);
1245: }
1246:
1247: map.put(w.state,this.addState());
1248: }
1249: */
1250:
1251: for (Wrapper_State w = states.elements; w != null; w = w.next) {
1252: map.put(w.state, this .addState());
1253: }
1254:
1255: for (Wrapper_State w = states.elements; w != null; w = w.next) {
1256: State newState = (State) map.get(w.state);
1257: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
1258: if (trans.properties == null)
1259: newState.addTransition(null, null, (State) map
1260: .get(trans.toState));
1261: else
1262: newState.addTransition(
1263: (IProperties) trans.properties.clone(),
1264: null, (State) map.get(trans.toState));
1265: }
1266: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
1267: if (trans.properties == null)
1268: newState.addTransition(null,
1269: (ISet_char) trans.charSet.clone(),
1270: (State) map.get(trans.toState));
1271: else
1272: newState.addTransition(
1273: (IProperties) trans.properties.clone(),
1274: (ISet_char) trans.charSet.clone(),
1275: (State) map.get(trans.toState));
1276: }
1277: }
1278:
1279: return map;
1280: }
1281:
1282: public String toString() {
1283: final StringBuffer buffer = new StringBuffer();
1284:
1285: for (Wrapper_State w = this .aStates.elements; w != null; w = w.next) {
1286: buffer.append(" \n").append(w.state);
1287:
1288: if (w.state == this .startState)
1289: buffer.append('+');
1290:
1291: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
1292: buffer.append(" \n -");
1293: if (trans.properties != null)
1294: buffer.append(trans.properties).append(": ");
1295: buffer.append("-> ").append(trans.toState);
1296: }
1297:
1298: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
1299: buffer.append(" \n -");
1300: if (trans.properties != null)
1301: buffer.append(trans.properties).append(": ");
1302: buffer.append(trans.charSet).append("-> ").append(
1303: trans.toState);
1304: }
1305: }
1306:
1307: return buffer.toString();
1308: }
1309:
1310: protected Object clone() {
1311: try {
1312: Automaton clone = (Automaton) super .clone();
1313: clone.automatonNr = Automaton.currentAutomatonNr++;
1314: clone.currentStateNr = 0;
1315: clone.startState = null;
1316: clone.listeners = null;
1317: clone.aStates = clone.newLinkedSet_State();
1318:
1319: final java.util.Map map = clone.cloneStates(this .aStates);
1320:
1321: final Set keys = map.keySet();
1322: final Iterator it = keys.iterator();
1323: for (int i = keys.size(); i > 0; --i) {
1324: State oldState = (State) it.next();
1325: State newState = (State) map.get(oldState);
1326: newState.stateNr = oldState.stateNr;
1327: if (clone.currentStateNr <= newState.stateNr)
1328: clone.currentStateNr = newState.stateNr + 1;
1329: }
1330:
1331: if (this .startState != null)
1332: clone.setStartState((State) map.get(this .startState));
1333:
1334: return clone;
1335: } catch (CloneNotSupportedException e) {
1336: throw new Error();
1337: }
1338: }
1339:
1340: }
|