0001: /*
0002: * 01/07/2003 - 15:19:32
0003: *
0004: * SAutomaton.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.set;
0024:
0025: import com.tc.jrexx.automaton.*;
0026: import java.util.*;
0027: import java.io.*;
0028:
0029: /**
0030: * This class represents a (non-)deterministic final automaton (NFA/DFA).
0031: * Use this class to create an automaton manually by adding states to the automaton and transitions to other states
0032: * or to browse through the automaton's states and implement your own matching strategies.
0033: * <br>to create an automaton manually try
0034: * <code>
0035: * <br>import com.karneim.util.collection.set.*;
0036: * <br>public class Test {
0037: * <br> public static void main(String[] args) {
0038: * <br> SAutomaton automaton = new SAutomaton();
0039: * <br> {@link IStatePro} s1 = automaton.addState(false);
0040: * <br> IStatePro s2 = automaton.addState(true);
0041: * <br> s1.addTransition(new {@link CharSet}("0123456789"),s2);
0042: * <br> s2.addTransition(new CharSet("0123456789"),s2);
0043: * <br> automaton.setStartState(s1);
0044: * <br> }
0045: * <br>}
0046: * <br>
0047: * </code>
0048: * <br>to browse through the automaton's states try
0049: * <code>
0050: * <br> final {@link IStatePro} startState = automaton.getStartState();
0051: * <br> final {@link StateProSet} states = new StateProSet(startState);
0052: * <br> final {@link StateProSet.Iterator} it = states.iterator();
0053: * <br> for (IStatePro state=it.next(); state!=null; state=it.next()) {
0054: * <br> IStatePro.ITransition[] transitions = state.getTransitions();
0055: * <br> for (int i=0; i transitions.length; ++i) {
0056: * <br> states.add(transitions[i].getToState());
0057: * <br> System.out.println(
0058: * <br> "from " + transitions[i].getFromState()
0059: * <br> + " through " + transitions[i].getCharSet()
0060: * <br> + " to " + transitions[i].getToState()
0061: * <br> );
0062: * <br> }
0063: * <br> }
0064: * <br>
0065: * </code>
0066: * <br>to implement own matching strategies try
0067: * <code>
0068: * <br> /**
0069: * <br> * returns true if input is an existing path through automaton's states
0070: * <br> * otherwise false.
0071: * <br> *
0072: * <br> public static boolean incompleteMatch(SAutomaton automaton,String input) {
0073: * <br> {@link IState} current = automaton.getStartState().visit();
0074: * <br> for (int i=0; i input.length(); ++i) {
0075: * <br> current = current.next(input.charAt(i));
0076: * <br> if (current == null) return false;
0077: * <br> }
0078: * <br> return true;
0079: * <br> }
0080: * </code>
0081: *
0082: * @author Ralf Meyer
0083: * @version 1.0
0084: */
0085: public class SAutomaton {
0086:
0087: final class SAutomatonChangeListener implements
0088: Automaton.IChangedListener {
0089:
0090: public void stateAdded(Automaton.State state) {
0091: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0092: .get(state);
0093: if (wrapper == null)
0094: wrapper = new StatePro(
0095: (AutomatonSet_String.SState) state);
0096:
0097: final Iterator it = SAutomaton.this .listeners.iterator();
0098: for (int i = SAutomaton.this .listeners.size(); i > 0; --i) {
0099: ((SAutomaton.IChangeListener) it.next())
0100: .stateAdded(wrapper);
0101: }
0102: }
0103:
0104: public void stateRemoved(Automaton.State state) {
0105: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0106: .get(state);
0107: if (wrapper == null)
0108: wrapper = new StatePro(
0109: (AutomatonSet_String.SState) state);
0110:
0111: final Iterator it = SAutomaton.this .listeners.iterator();
0112: for (int i = SAutomaton.this .listeners.size(); i > 0; --i) {
0113: ((SAutomaton.IChangeListener) it.next())
0114: .stateRemoved(wrapper);
0115: }
0116: }
0117:
0118: public void startStateChanged(Automaton.State oldStartState,
0119: Automaton.State newStartState) {
0120: StatePro oldWrapper = null;
0121: if (oldStartState != null) {
0122: oldWrapper = (StatePro) SAutomaton.this .state2wrapper
0123: .get(oldStartState);
0124: if (oldWrapper == null)
0125: oldWrapper = new StatePro(
0126: (AutomatonSet_String.SState) oldStartState);
0127: }
0128:
0129: StatePro newWrapper = null;
0130: if (newStartState != null) {
0131: newWrapper = (StatePro) SAutomaton.this .state2wrapper
0132: .get(newStartState);
0133: if (newWrapper == null)
0134: newWrapper = new StatePro(
0135: (AutomatonSet_String.SState) newStartState);
0136: }
0137:
0138: final Iterator it = SAutomaton.this .listeners.iterator();
0139: for (int i = SAutomaton.this .listeners.size(); i > 0; --i) {
0140: ((SAutomaton.IChangeListener) it.next())
0141: .startStateChanged(oldWrapper, newWrapper);
0142: }
0143: }
0144: }
0145:
0146: /**
0147: * The listener interface for receiving change events of a SAutomaton.
0148: * The class that is interested in processing an automaton's change event implements this interface.
0149: * A listener instance of that class is registered with the automaton using the automaton's addChangeListener method.
0150: * @author Ralf Meyer
0151: * @version 1.0
0152: */
0153: public interface IChangeListener {
0154: /**
0155: The Automaton invokes this method on all registered listener if a new state has been added to the automaton.
0156: */
0157: public void stateAdded(IStatePro state);
0158:
0159: /**
0160: The Automaton invokes this method on all registered listener if an existing state has been removed from the automaton.
0161: */
0162: public void stateRemoved(IStatePro state);
0163:
0164: /**
0165: The Automaton invokes this method on all registered listener if the automaton's current startState has been changed.
0166: Both oldStartState and newStartState can be null.
0167: */
0168: public void startStateChanged(IStatePro oldStartState,
0169: IStatePro newStartState);
0170: }
0171:
0172: protected class State implements IState {
0173: protected final AutomatonSet_String.ISState state;
0174:
0175: protected State(AutomatonSet_String.ISState state) {
0176: this .state = state;
0177: }
0178:
0179: public boolean isFinal() {
0180: return this .state.isFinal();
0181: }
0182:
0183: public IState next(char ch) {
0184: final Automaton.IState nextState = this .state.next(ch);
0185: return nextState == null ? null : new State(
0186: (AutomatonSet_String.ISState) nextState);
0187: }
0188:
0189: /*
0190: public IState nnext(String s) {
0191: return this.nnext(s,0,s.length());
0192: }
0193:
0194: public IState nnext(String s,int offset) {
0195: return this.nnext(s,0,s.length()-offset);
0196: }
0197:
0198: public IState nnext(String s,int offset,int length) {
0199: AutomatonSet_String.IState state = this.state;
0200: for (;length>0; --length, ++offset) {
0201: AutomatonSet_String.IState newState = state.next(s.charAt(offset));
0202: if (newState==null) break;
0203: state = newState;
0204: }
0205: return new State((AutomatonSet_String.ISState)state);
0206: }
0207: */
0208:
0209: public StateProSet getAllReachableStates() {
0210: final StateProSet result = new StateProSet();
0211: final Automaton.LinkedSet_State states = this .state
0212: .getAllReachableStates();
0213: for (Automaton.Wrapper_State w = states.elements; w != null; w = w.next) {
0214:
0215: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0216: .get(w.state);
0217: if (wrapper == null)
0218: wrapper = new StatePro(
0219: (AutomatonSet_String.SState) w.state);
0220: result.add(wrapper);
0221: }
0222: return result;
0223: }
0224:
0225: public String toString() {
0226: return this .state.toString();
0227: }
0228: }
0229:
0230: protected class Transition implements IStatePro.ITransition {
0231: protected final Automaton.State.Transition transition;
0232:
0233: protected Transition(Automaton.State.Transition transition) {
0234: this .transition = transition;
0235: SAutomaton.this .transition2wrapper.put(transition, this );
0236: }
0237:
0238: /*
0239: protected void finalize() {
0240: SAutomaton.this.transition2wrapper.remove(this.transition);
0241: }
0242: */
0243: public IStatePro getFromState() {
0244: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0245: .get(this .transition.getFromState());
0246: if (wrapper == null)
0247: wrapper = new StatePro(
0248: (AutomatonSet_String.SState) this .transition
0249: .getFromState());
0250: return wrapper;
0251: }
0252:
0253: public Set getLabels() {
0254: final HashSet labels = (HashSet) this .transition.properties;
0255: // if (labels!=null) return java.util.Collections.unmodifiableSet(labels);
0256: if (labels != null)
0257: return labels;
0258: return java.util.Collections.EMPTY_SET;
0259: }
0260:
0261: public ISet_char getCharSet() {
0262: return this .transition.getCharSet();
0263: }
0264:
0265: public IStatePro getToState() {
0266: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0267: .get(this .transition.getToState());
0268: if (wrapper == null)
0269: wrapper = new StatePro(
0270: (AutomatonSet_String.SState) this .transition
0271: .getToState());
0272: return wrapper;
0273: }
0274:
0275: public String toString() {
0276: final StringBuffer buffer = new StringBuffer();
0277: final AutomatonSet_String.SState fromState = (AutomatonSet_String.SState) this .transition
0278: .getFromState();
0279: final AutomatonSet_String.SState toState = (AutomatonSet_String.SState) this .transition
0280: .getToState();
0281:
0282: if (fromState.isFinal())
0283: buffer.append('[').append(fromState.stateNr)
0284: .append(']');
0285: else
0286: buffer.append('(').append(fromState.stateNr)
0287: .append(')');
0288:
0289: if (this .transition.getCharSet() == null) {
0290: if (this .transition.properties == null)
0291: buffer.append(" --> ");
0292: else
0293: buffer.append(" - ").append(
0294: this .transition.properties).append(": -> ");
0295: } else {
0296: if (this .transition.properties == null)
0297: buffer.append(" - ").append(
0298: this .transition.getCharSet())
0299: .append(" -> ");
0300: else
0301: buffer.append(" - ").append(
0302: this .transition.properties).append(':')
0303: .append(this .transition.getCharSet())
0304: .append(" ->");
0305: }
0306:
0307: if (toState.isFinal())
0308: buffer.append('[').append(toState.stateNr).append(']');
0309: else
0310: buffer.append('(').append(toState.stateNr).append(')');
0311:
0312: return buffer.toString();
0313: }
0314:
0315: }
0316:
0317: private final class StateProVisitedListener implements
0318: AutomatonSet_String.IStateVisitedListener {
0319: private final StatePro statePro;
0320:
0321: public StateProVisitedListener(StatePro statePro) {
0322: this .statePro = statePro;
0323: }
0324:
0325: public void stateVisited(Automaton.State state) {
0326: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0327: .get(state);
0328: if (wrapper == null)
0329: wrapper = new StatePro(
0330: (AutomatonSet_String.SState) state);
0331:
0332: final Iterator it = statePro.visitListeners.iterator();
0333: for (int i = statePro.visitListeners.size(); i > 0; --i) {
0334: ((IStatePro.IVisitListener) it.next())
0335: .stateVisited(wrapper);
0336: }
0337: }
0338:
0339: public void stateVisited(Automaton.State state, char ch) {
0340: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0341: .get(state);
0342: if (wrapper == null)
0343: wrapper = new StatePro(
0344: (AutomatonSet_String.SState) state);
0345:
0346: final Iterator it = statePro.visitListeners.iterator();
0347: for (int i = statePro.visitListeners.size(); i > 0; --i) {
0348: ((IStatePro.IVisitListener) it.next()).stateVisited(
0349: wrapper, ch);
0350: }
0351: }
0352:
0353: public void stateUnVisited(Automaton.State state) {
0354: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0355: .get(state);
0356: if (wrapper == null)
0357: wrapper = new StatePro(
0358: (AutomatonSet_String.SState) state);
0359:
0360: final Iterator it = statePro.visitListeners.iterator();
0361: for (int i = statePro.visitListeners.size(); i > 0; --i) {
0362: ((IStatePro.IVisitListener) it.next())
0363: .stateUnVisited(wrapper);
0364: }
0365: }
0366: }
0367:
0368: private final class StateProChangedListener implements
0369: AutomatonSet_String.ISStateChangedListener {
0370:
0371: private final StatePro statePro;
0372:
0373: public StateProChangedListener(StatePro statePro) {
0374: this .statePro = statePro;
0375: }
0376:
0377: public void transitionAdded(
0378: Automaton.State.Transition transition) {
0379: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0380: .get(transition);
0381: if (wrapper == null)
0382: wrapper = new Transition(transition);
0383:
0384: final Iterator it = statePro.changeListeners.iterator();
0385: for (int i = statePro.changeListeners.size(); i > 0; --i) {
0386: ((IStatePro.IChangeListener) it.next())
0387: .transitionAdded(wrapper);
0388: }
0389: }
0390:
0391: public void transitionRemoved(
0392: Automaton.State.Transition transition) {
0393: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0394: .get(transition);
0395: if (wrapper == null)
0396: wrapper = new Transition(transition);
0397: final Iterator it = statePro.changeListeners.iterator();
0398: for (int i = statePro.changeListeners.size(); i > 0; --i) {
0399: ((IStatePro.IChangeListener) it.next())
0400: .transitionRemoved(wrapper);
0401: }
0402: }
0403:
0404: public void isFinalChanged(AutomatonSet_String.SState state,
0405: boolean isFinal) {
0406: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0407: .get(state);
0408: if (wrapper == null)
0409: wrapper = new StatePro(
0410: (AutomatonSet_String.SState) state);
0411:
0412: final Iterator it = statePro.changeListeners.iterator();
0413: for (int i = statePro.changeListeners.size(); i > 0; --i) {
0414: ((IStatePro.IChangeListener) it.next()).isFinalChanged(
0415: wrapper, isFinal);
0416: }
0417: }
0418: }
0419:
0420: protected class StatePro implements IStatePro {
0421:
0422: protected final Automaton.IStateVisitedListener stateVisitedListener = new StateProVisitedListener(
0423: this );
0424:
0425: protected final Automaton.IStateChangedListener stateChangedListener = new StateProChangedListener(
0426: this );
0427:
0428: protected LinkedList visitListeners = null;
0429: protected LinkedList changeListeners = null;
0430:
0431: public void addVisitListener(IStatePro.IVisitListener listener) {
0432: if (this .visitListeners == null) {
0433: this .visitListeners = new LinkedList();
0434: this .state
0435: .addVisitedListener(this .stateVisitedListener);
0436: }
0437: this .visitListeners.add(listener);
0438: }
0439:
0440: public boolean removeVisitListener(
0441: IStatePro.IVisitListener listener) {
0442: if (this .visitListeners != null) {
0443: final Iterator it = this .visitListeners.iterator();
0444: for (int i = this .visitListeners.size(); i > 0; --i) {
0445: if (listener == it.next()) {
0446: if (this .visitListeners.size() > 1)
0447: it.remove();
0448: else {
0449: this .state
0450: .removeVisitedListener(this .stateVisitedListener);
0451: this .visitListeners = null;
0452: }
0453: return true;
0454: }
0455: }
0456: }
0457: return false;
0458: }
0459:
0460: public void addChangeListener(IStatePro.IChangeListener listener) {
0461: if (this .changeListeners == null) {
0462: this .changeListeners = new LinkedList();
0463: this .state
0464: .addChangedListener(this .stateChangedListener);
0465: }
0466: this .changeListeners.add(listener);
0467: }
0468:
0469: public boolean removeChangeListener(
0470: IStatePro.IChangeListener listener) {
0471: if (this .changeListeners != null) {
0472: final Iterator it = this .changeListeners.iterator();
0473: for (int i = this .changeListeners.size(); i > 0; --i) {
0474: if (listener == it.next()) {
0475: if (this .changeListeners.size() > 1)
0476: it.remove();
0477: else {
0478: this .state
0479: .removeChangedListener(this .stateChangedListener);
0480: this .changeListeners = null;
0481: }
0482: return true;
0483: }
0484: }
0485: }
0486: return false;
0487: }
0488:
0489: protected final AutomatonSet_String.SState state;
0490:
0491: protected StatePro(AutomatonSet_String.SState state) {
0492: if (state == null)
0493: throw new Error("state==null");
0494: this .state = state;
0495: SAutomaton.this .state2wrapper.put(state, this );
0496: }
0497:
0498: protected void finalize() {
0499: SAutomaton.this .state2wrapper.remove(this .state);
0500: }
0501:
0502: protected SAutomaton parent() {
0503: return SAutomaton.this ;
0504: }
0505:
0506: public boolean isFinal() {
0507: return this .state.isFinal();
0508: }
0509:
0510: public void setFinal(boolean isFinal) {
0511: this .state.setFinal(isFinal);
0512: }
0513:
0514: public IState visit() {
0515: return new State((AutomatonSet_String.ISState) this .state
0516: .visit());
0517: }
0518:
0519: public IStatePro.ITransition addTransition(ISet_char charSet,
0520: IStatePro toState) {
0521: final AutomatonSet_String.SState.Transition trans = this .state
0522: .addTransition(null, charSet,
0523: ((StatePro) toState).state);
0524: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0525: .get(trans);
0526: if (wrapper == null)
0527: wrapper = new Transition(trans);
0528: return wrapper;
0529: }
0530:
0531: public boolean removeTransition(IStatePro.ITransition transition) {
0532: return this .state
0533: .removeTransition(((Transition) transition).transition);
0534: }
0535:
0536: public void removeAllTransitions() {
0537: this .state.removeAllTransitions();
0538: }
0539:
0540: public StateProSet getAllReachableStates() {
0541: final StateProSet result = new StateProSet();
0542: final Automaton.LinkedSet_State states = this .state
0543: .getAllReachableStates();
0544: for (Automaton.Wrapper_State w = states.elements; w != null; w = w.next) {
0545:
0546: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0547: .get(w.state);
0548: if (wrapper == null)
0549: wrapper = new StatePro(
0550: (AutomatonSet_String.SState) w.state);
0551: result.add(wrapper);
0552: }
0553: return result;
0554: }
0555:
0556: public IStatePro.ITransition[] getTransitions() {
0557: final LinkedList list = new LinkedList();
0558: for (AutomatonSet_String.State.Transition trans = this .state.transitions; trans != null; trans = trans.next) {
0559: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0560: .get(trans);
0561: if (wrapper == null)
0562: wrapper = new Transition(trans);
0563: // list.add(wrapper);
0564: list.addFirst(wrapper);
0565: }
0566: return (IStatePro.ITransition[]) list
0567: .toArray(new IStatePro.ITransition[list.size()]);
0568: }
0569:
0570: public IStatePro.ITransition[] getETransitions() {
0571: final LinkedList list = new LinkedList();
0572: for (AutomatonSet_String.State.Transition trans = this .state.eTransitions; trans != null; trans = trans.next) {
0573: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0574: .get(trans);
0575: if (wrapper == null)
0576: wrapper = new Transition(trans);
0577: // list.add(wrapper);
0578: list.addFirst(wrapper);
0579: }
0580: return (IStatePro.ITransition[]) list
0581: .toArray(new IStatePro.ITransition[list.size()]);
0582: }
0583:
0584: /**
0585: * returns all transitions (normal and epsilon transitions) of this state.
0586: * the result array contains first all epsilon transitions and then all normal transitions
0587: */
0588: public IStatePro.ITransition[] getAllTransitions() {
0589: final LinkedList list = new LinkedList();
0590: for (AutomatonSet_String.State.Transition trans = this .state.transitions; trans != null; trans = trans.next) {
0591: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0592: .get(trans);
0593: if (wrapper == null)
0594: wrapper = new Transition(trans);
0595: // list.add(wrapper);
0596: list.addFirst(wrapper);
0597: }
0598: for (AutomatonSet_String.State.Transition trans = this .state.eTransitions; trans != null; trans = trans.next) {
0599: Transition wrapper = (Transition) SAutomaton.this .transition2wrapper
0600: .get(trans);
0601: if (wrapper == null)
0602: wrapper = new Transition(trans);
0603: // list.add(wrapper);
0604: list.addFirst(wrapper);
0605: }
0606: return (IStatePro.ITransition[]) list
0607: .toArray(new IStatePro.ITransition[list.size()]);
0608: }
0609:
0610: public int getStateNumber() {
0611: return this .state.stateNr;
0612: }
0613:
0614: public String toString() {
0615: if (this .isFinal())
0616: return "[" + this .state.stateNr + "]";
0617: return "(" + this .state.stateNr + ")";
0618: }
0619:
0620: }
0621:
0622: // should be IdentityMap
0623: protected transient HashMap state2wrapper = null;
0624: protected transient HashMap transition2wrapper = null;
0625:
0626: protected transient Automaton.IChangedListener automatonChangedListener = null;
0627:
0628: protected Automaton.IChangedListener getAutomatonChangedListener() {
0629: if (this .automatonChangedListener != null)
0630: return this .automatonChangedListener;
0631:
0632: this .automatonChangedListener = new SAutomatonChangeListener();
0633:
0634: return this .automatonChangedListener;
0635: }
0636:
0637: protected transient LinkedList listeners = null;
0638:
0639: /**
0640: * Adds the specified listener to receive change events from this automaton.
0641: * The listener will be registered as listener in any case, even if it has been registered yet.
0642: * If a listener instance is added two times, it will receive events twice.
0643: * important: don't forget to remove the listener, if you don't need it any longer but still have the automaton in use.
0644: * Otherwise your listener won't be carbage collected (because it is registered with this automaton)
0645: * and still will receive events.
0646: */
0647: public void addChangeListener(SAutomaton.IChangeListener listener) {
0648: if (this .listeners == null) {
0649: this .listeners = new LinkedList();
0650: ((AutomatonSet_String) this .automaton)
0651: .addChangedListener(this
0652: .getAutomatonChangedListener());
0653: }
0654: this .listeners.add(listener);
0655: }
0656:
0657: /**
0658: * Removes the specified listener so that it no longer receives change events from this automaton.
0659: * If the listener instance is registered more than ones, only one instance will be removed.
0660: * @param listener
0661: * @throw IllegalArgumentException - if null is passed as listener
0662: * @return true if the listener was registered else false
0663: */
0664: public boolean removeChangeListener(
0665: SAutomaton.IChangeListener listener) {
0666: if (this .listeners != null) {
0667: final Iterator it = this .listeners.iterator();
0668: for (int i = this .listeners.size(); i > 0; --i) {
0669: if (listener == it.next()) {
0670: if (this .listeners.size() > 1)
0671: it.remove();
0672: else {
0673: this .automaton
0674: .removeChangedListener(this .automatonChangedListener);
0675: this .automatonChangedListener = null;
0676: this .listeners = null;
0677: }
0678: return true;
0679: }
0680: }
0681: }
0682: return false;
0683: }
0684:
0685: protected transient AutomatonSet_String automaton;
0686:
0687: /**
0688: * Creates a new empty automaton
0689: */
0690: public SAutomaton() {
0691: this (new AutomatonSet_String());
0692: }
0693:
0694: public SAutomaton(FSAData data) {
0695: this (new AutomatonSet_String());
0696: this .init(data);
0697: }
0698:
0699: protected static FSAData toFSAData(Object obj) {
0700: if (obj.getClass() != FSAData.class) {
0701: SAutomatonData data = (SAutomatonData) obj;
0702:
0703: FSAData.State[] newStates = new FSAData.State[data.states == null ? 0
0704: : data.states.length];
0705: for (int i = 0; i < newStates.length; ++i) {
0706: SAutomatonData.State state = data.states[i];
0707: if (state != null) {
0708: FSAData.State.Transition[] newTransitions = new FSAData.State.Transition[state.transitions == null ? 0
0709: : state.transitions.length];
0710: for (int t = 0; t < newTransitions.length; ++t) {
0711: SAutomatonData.State.Transition trans = state.transitions[t];
0712: newTransitions[t] = new FSAData.State.Transition(
0713: trans.properties, trans.charSet,
0714: trans.toStateNumber);
0715: }
0716: newStates[i] = new FSAData.State(state.number,
0717: state.isFinal, newTransitions,
0718: state.transitionsAreDeterministic);
0719: }
0720: }
0721: return new FSAData(newStates, data.startStateNumber,
0722: data.isDeterministic);
0723:
0724: } else {
0725: FSAData data = (FSAData) obj;
0726: switch (data.objectVersion) {
0727: case FSAData.classVersion:
0728: return data;
0729: default:
0730: return data;
0731: }
0732: }
0733: }
0734:
0735: public SAutomaton(InputStream automatonDataStream)
0736: throws IOException, ClassNotFoundException {
0737: this (new AutomatonSet_String());
0738: // this.init((FSAData)automatonDataStream.readObject());
0739: this .init(toFSAData(new ObjectInputStream(automatonDataStream)
0740: .readObject()));
0741: }
0742:
0743: protected SAutomaton(AutomatonSet_String automaton) {
0744: this .automaton = automaton;
0745: this .state2wrapper = new HashMap();
0746: this .transition2wrapper = new HashMap();
0747: }
0748:
0749: public boolean isDeterministic() {
0750: return this .automaton.isDeterministic();
0751: }
0752:
0753: /**
0754: * Returns the current start state of the automaton.
0755: * important: The result is null, if and only if the current start state is null
0756: * @return the current start state of the automaton
0757: */
0758: public IStatePro getStartState() {
0759: Automaton.State startState = ((AutomatonSet_String) this .automaton)
0760: .getStartState();
0761: if (startState == null)
0762: return null;
0763:
0764: StatePro wrapper = (StatePro) this .state2wrapper
0765: .get(startState);
0766: if (wrapper == null)
0767: wrapper = new StatePro(
0768: (AutomatonSet_String.SState) startState);
0769: return wrapper;
0770: }
0771:
0772: /**
0773: * Sets the automaton's start state to the specified state.
0774: * If the automaton should have no start state pass null.
0775: * <br>important: the specified state must be a state of this automaton which means
0776: * <br>a) the state must have been created via the addState() method of this automaton
0777: * <br>b) the state must not have been removed from this automaton via the removeState method
0778: * @param state
0779: */
0780: public void setStartState(IStatePro state) {
0781: if ((state instanceof StatePro) == false)
0782: throw new IllegalArgumentException(
0783: "state is no state of mine");
0784:
0785: final StatePro wrapper = (StatePro) state;
0786: if (wrapper.parent() != this )
0787: throw new IllegalArgumentException(
0788: "state is no state of mine");
0789:
0790: this .automaton.setStartState(wrapper.state);
0791: }
0792:
0793: /**
0794: * Adds a new non final state to this automaton.
0795: * @return a new state
0796: */
0797: public IStatePro addState() {
0798: return this .addState(false);
0799: }
0800:
0801: /**
0802: * Adds a new final or non final state to this automaton.
0803: * @return a new state
0804: */
0805: public IStatePro addState(boolean isFinal) {
0806: final AutomatonSet_String.SState newState = this .automaton
0807: .addState(isFinal);
0808: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0809: .get(newState);
0810: if (wrapper == null)
0811: wrapper = new StatePro(
0812: (AutomatonSet_String.SState) newState);
0813: return wrapper;
0814: }
0815:
0816: /**
0817: * Removes the specified state from this automaton.
0818: * <br>First all transitions pointing to state are removed and then the state itself.
0819: * <br>If state is this automaton's start state then first of all this automaton's start state is set to null.
0820: * <br>important: the specified state must have been created via the addState method of this automaton
0821: * otherwise an IllegalArgumentException is thrown.
0822: * @param state
0823: * @return true if this automaton owns the specified state else false
0824: */
0825: public boolean removeState(IStatePro state) {
0826: if ((state instanceof StatePro) == false)
0827: throw new IllegalArgumentException(
0828: "state is no state of mine");
0829:
0830: final StatePro wrapper = (StatePro) state;
0831: if (wrapper.parent() != this )
0832: throw new IllegalArgumentException(
0833: "state is no state of mine");
0834: return this .automaton.removeState(wrapper.state);
0835: }
0836:
0837: /**
0838: * Removes all states of this automaton.
0839: */
0840: public void clear() {
0841: this .automaton.clear();
0842: }
0843:
0844: /**
0845: * Minimizes this automaton as much as possible.
0846: * The resulting automaton has as less states as possible.
0847: * <br>important: the current implementation removes all properties from all transitions
0848: */
0849: public void minimize() {
0850: this .automaton.minimize();
0851: }
0852:
0853: /**
0854: * Returns all states of this automaton whatever they are reachable through the current start state or not.
0855: * @return
0856: */
0857: public StateProSet getStates() {
0858: final StateProSet result = new StateProSet();
0859: final Automaton.LinkedSet_State states = this .automaton
0860: .getStates();
0861: for (Automaton.Wrapper_State w = states.elements; w != null; w = w.next) {
0862: StatePro wrapper = (StatePro) SAutomaton.this .state2wrapper
0863: .get(w.state);
0864: if (wrapper == null)
0865: wrapper = new StatePro(
0866: (AutomatonSet_String.SState) w.state);
0867: result.add(wrapper);
0868: }
0869: return result;
0870: }
0871:
0872: public void complement() {
0873: this .automaton.complement();
0874: }
0875:
0876: public void addAll(SAutomaton automaton) {
0877: this .automaton.addAll(automaton.automaton);
0878: }
0879:
0880: public void retainAll(SAutomaton automaton) {
0881: this .automaton.retainAll(automaton.automaton);
0882: }
0883:
0884: public void removeAll(SAutomaton automaton) {
0885: this .automaton.removeAll(automaton.automaton);
0886: }
0887:
0888: public String toString() {
0889: return this .automaton.toString();
0890: }
0891:
0892: private String getCharSet(ISet_char charSet) {
0893: if (charSet == null)
0894: return null;
0895: final StringBuffer buffer = new StringBuffer(charSet.size());
0896: ISet_char.Iterator it_charSet = charSet.iterator();
0897: for (int i = charSet.size(); i > 0; --i)
0898: buffer.append(it_charSet.next());
0899:
0900: ISet_char cs = new CharSet(buffer.toString());
0901: if (cs.equals(charSet) == false)
0902: throw new Error("" + charSet + " " + cs);
0903:
0904: return buffer.toString();
0905: }
0906:
0907: public FSAData toData() {
0908: Automaton.LinkedSet_State xxx = this .automaton.getStates();
0909: AutomatonSet_String.SState[] states = new AutomatonSet_String.SState[xxx
0910: .size()];
0911: int x = 0;
0912: for (Automaton.Wrapper_State w = xxx.elements; w != null; w = w.next, ++x) {
0913: states[x] = (AutomatonSet_String.SState) w.state;
0914: }
0915:
0916: FSAData.State[] data_states = new FSAData.State[states.length];
0917: for (int i = 0; i < states.length; ++i) {
0918: LinkedList data_transitions = new LinkedList();
0919: for (Automaton.State.Transition trans = states[i].transitions; trans != null; trans = trans.next) {
0920: // int toStateNr = 0; while (states[toStateNr]!=trans.toState) ++toStateNr;
0921: data_transitions.addFirst(new FSAData.State.Transition(
0922: trans.properties, this
0923: .getCharSet(trans.charSet)
0924: // ,toStateNr
0925: , trans.toState.stateNr));
0926: }
0927: for (Automaton.State.Transition trans = states[i].eTransitions; trans != null; trans = trans.next) {
0928: // int toStateNr = 0; while (states[toStateNr]!=trans.toState) ++toStateNr;
0929: data_transitions.addFirst(
0930: // new SAutomatonData.State.Transition(trans.properties,null,toStateNr)
0931: new FSAData.State.Transition(trans.properties,
0932: null, trans.toState.stateNr));
0933: }
0934:
0935: FSAData.State.Transition[] transitions = (FSAData.State.Transition[]) data_transitions
0936: .toArray(new FSAData.State.Transition[data_transitions
0937: .size()]);
0938:
0939: // data_states[i] = new SAutomatonData.State(i,states[i].isFinal,transitions,states[i].isDeterministic());
0940: data_states[i] = new FSAData.State(states[i].stateNr,
0941: states[i].isFinal, transitions, states[i]
0942: .isDeterministic());
0943: }
0944:
0945: final Automaton.State startState = this .automaton
0946: .getStartState();
0947: if (startState == null)
0948: return new FSAData(data_states, null, this .automaton
0949: .isDeterministic());
0950:
0951: // int startStateNr = 0; while (states[startStateNr]!=startState) ++startStateNr;
0952:
0953: FSAData result = new FSAData(data_states, new Integer(
0954: startState.stateNr), this .automaton.isDeterministic());
0955:
0956: return result;
0957: }
0958:
0959: protected void init(FSAData a) {
0960: // this.automatonChangedListener = null;
0961: // this.state2wrapper = new HashMap();
0962: // this.transition2wrapper = new HashMap();
0963: // this.automaton = this.newAutomaton();
0964:
0965: final HashMap map = new HashMap();
0966:
0967: if (a.states != null) {
0968: for (int i = 0; i < a.states.length; ++i) {
0969: Integer stateNr = new Integer(a.states[i].number);
0970: if (map.containsKey(stateNr))
0971: throw new IllegalArgumentException(
0972: "bad automatonData: state with number "
0973: + stateNr + " does already exists");
0974:
0975: AutomatonSet_String.SState state = this .automaton
0976: .addState(a.states[i].isFinal,
0977: a.states[i].number);
0978:
0979: map.put(stateNr, state);
0980: }
0981:
0982: for (int i = 0; i < a.states.length; ++i) {
0983: FSAData.State stateData = a.states[i];
0984:
0985: AutomatonSet_String.SState state = (AutomatonSet_String.SState) map
0986: .get(new Integer(stateData.number));
0987:
0988: if (stateData.transitions != null) {
0989: for (int t = 0; t < stateData.transitions.length; ++t) {
0990: FSAData.State.Transition transData = stateData.transitions[t];
0991:
0992: CharSet charSet = (transData.charSet == null) ? null
0993: : new CharSet(transData.charSet);
0994:
0995: AutomatonSet_String.SState toState = (AutomatonSet_String.SState) map
0996: .get(new Integer(
0997: transData.toStateNumber));
0998:
0999: state.addTransition(transData.properties,
1000: charSet, toState);
1001: }
1002: }
1003:
1004: state
1005: .setDeterministic(stateData.transitionsAreDeterministic);
1006: }
1007: }
1008:
1009: if (a.startStateNumber != null) {
1010: AutomatonSet_String.SState startState = (AutomatonSet_String.SState) map
1011: .get(a.startStateNumber);
1012:
1013: if (startState == null)
1014: throw new IllegalArgumentException(
1015: "bad automatonData: startState "
1016: + a.startStateNumber
1017: + " does not exists");
1018:
1019: this .automaton.setStartState(startState);
1020: }
1021:
1022: this .automaton.setDeterministic(a.isDeterministic);
1023: }
1024:
1025: public void toData(OutputStream automatonDataStream)
1026: throws IOException {
1027: new ObjectOutputStream(automatonDataStream).writeObject(this
1028: .toData());
1029: }
1030:
1031: }
|