0001: /*
0002: * 01/07/2003 - 15:19:32
0003: *
0004: * AutomatonSet_String.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:
0027: import java.util.*;
0028:
0029: public class AutomatonSet_String extends Automaton {
0030: protected static final ISet_char FULLSET = new com.tc.jrexx.set.CharSet();
0031: static {
0032: AutomatonSet_String.FULLSET.complement();
0033: }
0034:
0035: protected static class SProperties extends HashSet implements
0036: IProperties {
0037:
0038: public SProperties() {
0039: }
0040:
0041: public boolean containsAll(IProperties p) {
0042: //performance leak
0043: if ((p instanceof SProperties) == false)
0044: throw new IllegalArgumentException(
0045: "(p instanceof SProperties)==false");
0046: return super .containsAll((SProperties) p);
0047: }
0048:
0049: public void addAll(IProperties p) {
0050: //performance leak
0051: if ((p instanceof SProperties) == false)
0052: throw new IllegalArgumentException(
0053: "(p instanceof SProperties)==false");
0054: super .addAll((SProperties) p);
0055: }
0056:
0057: public void retainAll(IProperties p) {
0058: //performance leak
0059: if ((p instanceof SProperties) == false)
0060: throw new IllegalArgumentException(
0061: "(p instanceof SProperties)==false");
0062: super .retainAll((SProperties) p);
0063: }
0064:
0065: public void removeAll(IProperties p) {
0066: //performance leak
0067: if ((p instanceof SProperties) == false)
0068: throw new IllegalArgumentException(
0069: "(p instanceof SProperties)==false");
0070: super .removeAll((SProperties) p);
0071: }
0072:
0073: public Object clone() {
0074: return super .clone();
0075: }
0076:
0077: }
0078:
0079: public interface ISStateChangedListener extends
0080: IStateChangedListener {
0081: public void isFinalChanged(SState state, boolean isFinal);
0082: }
0083:
0084: public interface ISState extends Automaton.IState {
0085: public boolean isFinal();
0086: }
0087:
0088: public class SState extends Automaton.State implements ISState {
0089:
0090: public boolean isFinal;
0091:
0092: public SState(boolean isFinal) {
0093: this .isFinal = isFinal;
0094: }
0095:
0096: protected Automaton parent() {
0097: return AutomatonSet_String.this ;
0098: }
0099:
0100: protected void setDeterministic(Boolean isDeterministic) {
0101: super .setDeterministic(isDeterministic);
0102: }
0103:
0104: public boolean isFinal() {
0105: return this .isFinal;
0106: }
0107:
0108: protected void setFinal(boolean isFinal) {
0109: if (this .isFinal == isFinal)
0110: return;
0111: this .isFinal = isFinal;
0112: //inform listener
0113: if (this .changedListeners != null) {
0114: final Iterator it = this .changedListeners.iterator();
0115: for (int i = this .changedListeners.size(); i > 0; --i) {
0116: ((ISStateChangedListener) it.next())
0117: .isFinalChanged(this , isFinal);
0118: }
0119: }
0120: }
0121:
0122: /*
0123: protected void addTransition(State.Transition trans) {
0124: super.addTransition(trans);
0125: }
0126: */
0127: protected Transition addTransition(IProperties properties,
0128: ISet_char charSet, State toState) {
0129: // performance leak
0130: if (properties != null
0131: && (properties instanceof SProperties) == false)
0132: throw new IllegalArgumentException(
0133: "(properties instanceof SProperties)==false");
0134: if ((toState instanceof SState) == false)
0135: throw new IllegalArgumentException("(toState("
0136: + toState + ") instanceof SState)==false");
0137:
0138: return super .addTransition(properties, charSet, toState);
0139: }
0140:
0141: protected boolean removeTransition(State.Transition trans) {
0142: return super .removeTransition(trans);
0143: /*
0144: if(super.removeTransition(trans)) {
0145: return true;
0146: }
0147: return false;
0148: */
0149: }
0150:
0151: protected void removeAllTransitions() {
0152: super .removeAllTransitions();
0153: }
0154:
0155: protected IState getEClosure() {
0156: return super .getEClosure();
0157: }
0158:
0159: public String toString() {
0160: if (this .isFinal)
0161: return AutomatonSet_String.this .automatonNr + ".["
0162: + String.valueOf(this .stateNr) + ']';
0163: else
0164: return super .toString();
0165: }
0166:
0167: }
0168:
0169: protected class LinkedSet_SState extends Automaton.LinkedSet_State
0170: implements ISState {
0171:
0172: protected LinkedSet_SState() {
0173: super ();
0174: }
0175:
0176: protected LinkedSet_SState(SState state) {
0177: super (state);
0178: }
0179:
0180: public boolean isFinal() {
0181: for (Wrapper_State w = this .elements; w != null; w = w.next) {
0182: if (((SState) w.state).isFinal)
0183: return true;
0184: }
0185: return false;
0186: }
0187:
0188: public String toString() {
0189: final StringBuffer result = new StringBuffer();
0190: result.append(this .isFinal() ? '[' : '(');
0191: for (Wrapper_State wrapper = this .elements; wrapper != null; wrapper = wrapper.next) {
0192: if (wrapper != this .elements)
0193: result.append(", ");
0194: result.append(wrapper.state.toString());
0195: }
0196: result.append(this .isFinal() ? ']' : ')');
0197: return result.toString();
0198: }
0199:
0200: }
0201:
0202: protected final ISet_char fullSet;
0203:
0204: // protected boolean isMinimized = true;
0205:
0206: protected AutomatonSet_String(ISet_char fullSet) {
0207: super ();
0208: this .fullSet = fullSet;
0209: }
0210:
0211: protected void addChangedListener(
0212: Automaton.IChangedListener listener) {
0213: super .addChangedListener(listener);
0214: }
0215:
0216: protected boolean removeChangedListener(
0217: Automaton.IChangedListener listener) {
0218: return super .removeChangedListener(listener);
0219: }
0220:
0221: protected boolean isDeterministic() {
0222: return super .isDeterministic();
0223: }
0224:
0225: protected Automaton.State getStartState() {
0226: return this .startState;
0227: }
0228:
0229: protected AutomatonSet_String() {
0230: super ();
0231: this .fullSet = AutomatonSet_String.FULLSET;
0232: }
0233:
0234: protected LinkedSet_State newLinkedSet_State() {
0235: return new LinkedSet_SState();
0236: }
0237:
0238: protected LinkedSet_State newLinkedSet_State(State state) {
0239: return new LinkedSet_SState((SState) state);
0240: }
0241:
0242: protected State createState() {
0243: return new SState(false);
0244: }
0245:
0246: protected SState createState(boolean isFinal) {
0247: return new SState(isFinal);
0248: }
0249:
0250: protected SState addState(boolean isFinal) {
0251: final SState result = this .createState(isFinal);
0252: this .addState(result);
0253: return result;
0254: }
0255:
0256: protected SState addState(boolean isFinal, int stateNr) {
0257: this .currentStateNr = stateNr;
0258: return this .addState(isFinal);
0259: }
0260:
0261: protected boolean removeState(State removeState) {
0262: return super .removeState(removeState);
0263: }
0264:
0265: protected void clear() {
0266: super .clear();
0267: }
0268:
0269: protected void setDeterministic(Boolean isDeterministic) {
0270: super .setDeterminstic(isDeterministic);
0271: }
0272:
0273: protected void setStartState(State startState) {
0274: super .setStartState(startState);
0275: }
0276:
0277: protected LinkedSet_State getStates() {
0278: return this .aStates;
0279: }
0280:
0281: protected SState complement(SState state) {
0282: if (state == null) {
0283: SState totalFinalState = this .addState(true);
0284: totalFinalState.addTransition(null,
0285: (ISet_char) this .fullSet.clone(), totalFinalState);
0286: return totalFinalState;
0287: }
0288:
0289: if (this .isDeterministic(state) == false) {
0290: // remove all properties
0291: LinkedSet_State states = new LinkedSet_State(state);
0292: for (Wrapper_State w = states.elements; w != null; w = w.next) {
0293: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
0294: states.add(trans.toState);
0295: trans.properties = null;
0296: }
0297: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0298: states.add(trans.toState);
0299: trans.properties = null;
0300: }
0301: }
0302:
0303: state = this .makeDeterministic(state);
0304: }
0305:
0306: SState totalFinalState = null;
0307:
0308: LinkedSet_State reachableStates = new LinkedSet_State(state);
0309: for (Wrapper_State w = reachableStates.elements; w != null; w = w.next) {
0310: ISet_char charSet = (ISet_char) this .fullSet.clone();
0311: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0312: reachableStates.add(trans.toState);
0313: charSet.removeAll(trans.charSet);
0314: }
0315:
0316: SState sstate = (SState) w.state;
0317: if (charSet.isEmpty() == false) {
0318: if (totalFinalState == null) {
0319: totalFinalState = this .addState(true);
0320: totalFinalState.addTransition(null,
0321: (ISet_char) this .fullSet.clone(),
0322: totalFinalState);
0323: }
0324:
0325: sstate.addTransition(null, charSet, totalFinalState);
0326: }
0327: sstate.setFinal(!sstate.isFinal);
0328: }
0329:
0330: return state;
0331: }
0332:
0333: protected SState optional(SState state) {
0334: if (state.isFinal)
0335: return state;
0336: final SState newState = this .addState(true);
0337: newState.addTransition(null, null, state);
0338: return newState;
0339: }
0340:
0341: protected SState concat(SState state_A, SState state_B) {
0342: final LinkedSet_State states = new LinkedSet_State(state_A);
0343: for (Wrapper_State w = states.elements; w != null; w = w.next) {
0344: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next)
0345: states.add(trans.toState);
0346:
0347: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next)
0348: states.add(trans.toState);
0349:
0350: SState sState = (SState) w.state;
0351: if (sState.isFinal) {
0352: sState.setFinal(false);
0353: sState.addTransition(null, null, state_B);
0354: }
0355: }
0356: return state_A;
0357: }
0358:
0359: protected SState repeat(SState element, int minTimes, int maxTimes) {
0360: SState startState = element;
0361:
0362: if (minTimes == 0) {
0363: startState = this .optional(element);
0364: minTimes = 1;
0365: } else {
0366: for (int i = minTimes - 1; i > 0; --i) {
0367: SState newState = (SState) element.clone();
0368: startState = (SState) this .concat(newState, startState);
0369: }
0370: }
0371:
0372: if (maxTimes == 0) {
0373: final LinkedSet_State states = new LinkedSet_State(element);
0374:
0375: for (Wrapper_State w = states.elements; w != null; w = w.next) {
0376: for (Automaton.State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next)
0377: states.add(trans.toState);
0378:
0379: for (Automaton.State.Transition trans = w.state.transitions; trans != null; trans = trans.next)
0380: states.add(trans.toState);
0381:
0382: if (((SState) w.state).isFinal)
0383: ((SState) w.state).addTransition(null, null,
0384: element);
0385: }
0386: } else {
0387: for (int i = maxTimes - minTimes; i > 0; --i) {
0388: SState newState = (SState) element.clone();
0389:
0390: LinkedSet_State states = element
0391: .getAllReachableStates();
0392: states.add(element);
0393:
0394: for (Wrapper_State w = states.elements; w != null; w = w.next) {
0395: if (((SState) w.state).isFinal)
0396: ((SState) w.state).addTransition(null, null,
0397: newState);
0398: }
0399:
0400: element = newState;
0401: }
0402: }
0403:
0404: return startState;
0405: }
0406:
0407: protected SState union(SState state_A, SState state_B) {
0408: final SState newState = this .addState(false);
0409: newState.addTransition(null, null, state_A);
0410: newState.addTransition(null, null, state_B);
0411: return newState;
0412: }
0413:
0414: protected SState intersect(SState state_A, SState state_B) {
0415: // A & B = !(!A + !B)
0416: return this .complement(this .union(this .complement(state_A),
0417: this .complement(state_B)));
0418: }
0419:
0420: protected SState minus(SState state_A, SState state_B) {
0421: // A \ B = A & !B = !(!A + !!B) = !(!A + B)
0422: return this .complement(this .union(this .complement(state_A),
0423: state_B));
0424: }
0425:
0426: protected void addAll(SState state) {
0427: if (this .startState == null)
0428: this .setStartState(state);
0429: else
0430: this .setStartState(this .union((SState) this .startState,
0431: state));
0432: }
0433:
0434: protected void retainAll(SState state) {
0435: if (this .startState == null)
0436: return;
0437: this .setStartState(this .intersect((SState) this .startState,
0438: state));
0439: }
0440:
0441: protected void removeAll(SState state) {
0442: if (this .startState == null)
0443: return;
0444: this .setStartState(this .minus((SState) this .startState, state));
0445: }
0446:
0447: protected void concatAll(SState state) {
0448: if (this .startState == null)
0449: return;
0450: this
0451: .setStartState(this .concat((SState) this .startState,
0452: state));
0453: }
0454:
0455: protected void removeUselessStates() {
0456: if (5 == 6) {
0457: this .removeUnreachableStates();
0458: return;
0459: }
0460: final LinkedSet_State usefullStates = new LinkedSet_State();
0461: if (this .startState != null) {
0462: final LinkedSet_State uselessStates = this .startState
0463: .getAllReachableStates();
0464: uselessStates.add(this .startState);
0465: for (Wrapper_State w = uselessStates.elements; w != null; w = w.next) {
0466: if (((SState) w.state).isFinal) {
0467: if (uselessStates.remove(w.state) == false)
0468: throw new Error();
0469: /*
0470: if (prev==null) uselessStates.elements = w.next;
0471: else prev.next = w.next;
0472: */
0473: if (usefullStates.add(w.state) == false)
0474: throw new Error();
0475: }
0476: }
0477: //System.out.println(uselessStates);
0478: for (boolean flag = true; flag;) {
0479: flag = false;
0480: loop: for (Wrapper_State w = uselessStates.elements; w != null; w = w.next) {
0481: for (State.Transition trans = w.state.eTransitions; trans != null; trans = trans.next) {
0482: if (usefullStates.contains(trans.toState)) {
0483: if (uselessStates.remove(w.state) == false)
0484: throw new Error();
0485: if (usefullStates.add(w.state) == false)
0486: throw new Error();
0487: flag = true;
0488: continue loop;
0489: }
0490: }
0491: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0492: if (trans.charSet.isEmpty() == false
0493: && usefullStates
0494: .contains(trans.toState)) {
0495: if (uselessStates.remove(w.state) == false)
0496: throw new Error();
0497: if (usefullStates.add(w.state) == false)
0498: throw new Error();
0499: flag = true;
0500: continue loop;
0501: }
0502: }
0503: }
0504: }
0505: }
0506:
0507: for (Wrapper_State w = this .aStates.elements; w != null; w = w.next) {
0508: if (usefullStates.contains(w.state) == false) {
0509: if (this .removeState(w.state) == false)
0510: throw new Error();
0511: // System.out.println("####"+w.state.stateNr+"####");
0512: }
0513: }
0514: }
0515:
0516: protected void complement() {
0517: this .setStartState(this .complement((SState) this .startState));
0518: this .removeUselessStates();
0519: }
0520:
0521: protected void addAll(AutomatonSet_String automaton) {
0522: if (automaton.startState == null)
0523: return;
0524:
0525: // final LinkedSet_State reachableStates = automaton.startState.getAllReachableStates();
0526: // reachableStates.addAll(automaton.startState);
0527: // java.util.Map map = this.cloneStates(reachableStates);
0528: java.util.Map map = this .cloneState(automaton.startState);
0529: this .addAll((SState) map.get(automaton.startState));
0530: }
0531:
0532: protected void retainAll(AutomatonSet_String automaton) {
0533: if (automaton.startState == null)
0534: return;
0535:
0536: // final LinkedSet_State reachableStates = automaton.startState.getAllReachableStates();
0537: // reachableStates.addAll(automaton.startState);
0538: // java.util.Map map = this.cloneStates(reachableStates);
0539: java.util.Map map = this .cloneState(automaton.startState);
0540: this .retainAll((SState) map.get(automaton.startState));
0541: this .removeUselessStates();
0542: }
0543:
0544: protected void removeAll(AutomatonSet_String automaton) {
0545: if (automaton.startState == null)
0546: return;
0547:
0548: // final LinkedSet_State reachableStates = automaton.startState.getAllReachableStates();
0549: // reachableStates.addAll(automaton.startState);
0550: // java.util.Map map = this.cloneStates(reachableStates);
0551: java.util.Map map = this .cloneState(automaton.startState);
0552: this .removeAll((SState) map.get(automaton.startState));
0553: this .removeUselessStates();
0554: }
0555:
0556: protected void concatAll(AutomatonSet_String automaton) {
0557: if (automaton.startState == null)
0558: return;
0559:
0560: // java.util.Map map = this.cloneStates(automaton.startState.getAllReachableStates());
0561: java.util.Map map = this .cloneState(automaton.startState);
0562: this .concatAll((SState) map.get(automaton.startState));
0563: }
0564:
0565: protected Map cloneState(State state) {
0566: final Map map = super .cloneState(state);
0567: final Set keys = map.keySet();
0568: final Iterator it = keys.iterator();
0569: for (int i = keys.size(); i > 0; --i) {
0570: SState oldState = (SState) it.next();
0571: SState newState = (SState) map.get(oldState);
0572: newState.setFinal(oldState.isFinal);
0573: }
0574: return map;
0575: }
0576:
0577: protected Map cloneStates(LinkedSet_State states) {
0578: final Map map = super .cloneStates(states);
0579: final Set keys = map.keySet();
0580: final Iterator it = keys.iterator();
0581: for (int i = keys.size(); i > 0; --i) {
0582: SState oldState = (SState) it.next();
0583: SState newState = (SState) map.get(oldState);
0584: newState.setFinal(oldState.isFinal);
0585: }
0586: return map;
0587: }
0588:
0589: protected Object clone() {
0590: return super .clone();
0591: }
0592:
0593: private static class Transition {
0594: final ISet_char charSet;
0595: final EClosure toEClosure;
0596: IProperties properties = null;
0597: Transition next = null;
0598:
0599: Transition(IProperties properties, ISet_char charSet,
0600: EClosure toEClosure) {
0601: this .properties = properties;
0602: this .charSet = charSet;
0603: this .toEClosure = toEClosure;
0604: }
0605: }
0606:
0607: class EClosure {
0608: final LinkedSet_SState states;
0609: Transition eTransitions = null;
0610: Transition transitions = null;
0611:
0612: SState state = null;
0613:
0614: EClosure(LinkedSet_SState eStates) {
0615: this .states = eStates;
0616: }
0617:
0618: /*
0619: EClosure(SState state) {
0620: this.state = state;
0621: }
0622: */
0623: Transition addTransition(IProperties properties,
0624: ISet_char charSet, EClosure toEClosure) {
0625: Transition newTrans = new Transition(properties, charSet,
0626: toEClosure);
0627: newTrans.next = this .transitions;
0628: this .transitions = newTrans;
0629: return newTrans;
0630: }
0631:
0632: boolean removeTransition(Transition transition) {
0633: for (Transition prevTrans = null, trans = this .transitions; trans != null; prevTrans = trans, trans = trans.next) {
0634: if (trans == transition) {
0635: if (prevTrans == null)
0636: this .transitions = trans.next;
0637: else
0638: prevTrans.next = trans.next;
0639:
0640: return true;
0641: }
0642: }
0643: return false;
0644: }
0645:
0646: public boolean equals(Object obj) {
0647: return this .states.equals(((EClosure) obj).states);
0648: }
0649:
0650: public int hashCode() {
0651: return this .states.hashCode();
0652: }
0653:
0654: }
0655:
0656: class EClosureSet {
0657: final EClosure eClosure;
0658: EClosureSet next = null;
0659:
0660: EClosureSet(EClosure eClosure) {
0661: this .eClosure = eClosure;
0662: }
0663:
0664: boolean add(EClosure eClosure) {
0665: EClosureSet prev = null;
0666:
0667: for (EClosureSet eCS = this ; eCS != null; prev = eCS, eCS = eCS.next) {
0668: if (eCS.eClosure == eClosure)
0669: return false;
0670: }
0671:
0672: prev.next = new EClosureSet(eClosure);
0673: return true;
0674: }
0675: }
0676:
0677: protected SState makeDeterministic(SState state) {
0678: //performance leak
0679: if ((state instanceof SState) == false)
0680: throw new IllegalArgumentException(
0681: "state instanceof SState)==false");
0682: if (AutomatonSet_String.this .isDeterministic(state))
0683: return state;
0684:
0685: final HashMap eStates2EClosure = new HashMap();
0686:
0687: IState istate = state.getEClosure();
0688: LinkedSet_SState startEStates = (istate instanceof SState) ? (LinkedSet_SState) this
0689: .newLinkedSet_State((SState) istate)
0690: : (LinkedSet_SState) istate;
0691:
0692: EClosure startEClosure = new EClosure(startEStates);
0693: eStates2EClosure.put(startEStates, startEClosure);
0694:
0695: final EClosureSet eClosureSet = new EClosureSet(startEClosure);
0696: for (EClosureSet eCS = eClosureSet; eCS != null; eCS = eCS.next) {
0697: final EClosure eClosure = eCS.eClosure;
0698:
0699: for (Wrapper_State w = eClosure.states.elements; w != null; w = w.next) {
0700: loop: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0701: ISet_char trans_charSet = trans.charSet;
0702: istate = ((SState) trans.toState).getEClosure();
0703: LinkedSet_SState trans_toEStates = (istate instanceof SState) ? (LinkedSet_SState) this
0704: .newLinkedSet_State(trans.toState)
0705: : (LinkedSet_SState) istate;
0706:
0707: inner: for (Transition newTrans = eClosure.transitions; newTrans != null; newTrans = newTrans.next) {
0708: ISet_char intersection = (ISet_char) newTrans.charSet
0709: .clone();
0710: intersection.retainAll(trans_charSet);
0711:
0712: if (intersection.isEmpty() == false) {
0713:
0714: if (trans_toEStates
0715: .equals(newTrans.toEClosure.states) == false) {
0716: if (newTrans.charSet.size() == intersection
0717: .size())
0718: eClosure.removeTransition(newTrans);
0719: else
0720: newTrans.charSet
0721: .removeAll(intersection);
0722:
0723: /////////////////////////
0724:
0725: LinkedSet_SState tmpEStates = ((LinkedSet_SState) trans_toEStates
0726: .clone());
0727: tmpEStates
0728: .addAll(newTrans.toEClosure.states);
0729:
0730: EClosure newToEClosure = (EClosure) eStates2EClosure
0731: .get(tmpEStates);
0732: if (newToEClosure == null) {
0733: newToEClosure = new EClosure(
0734: tmpEStates);
0735: eStates2EClosure.put(tmpEStates,
0736: newToEClosure);
0737: }
0738:
0739: if (trans.properties == null)
0740: eClosure
0741: .addTransition(null,
0742: intersection,
0743: newToEClosure);
0744: else
0745: eClosure
0746: .addTransition(
0747: (IProperties) trans.properties
0748: .clone(),
0749: intersection,
0750: newToEClosure);
0751: }
0752:
0753: if (trans_charSet.size() == intersection
0754: .size())
0755: continue loop;
0756:
0757: if (trans_charSet == trans.charSet)
0758: trans_charSet = (ISet_char) trans.charSet
0759: .clone();
0760: trans_charSet.removeAll(intersection);
0761: }
0762: }
0763:
0764: if (trans_charSet.isEmpty() == false) {
0765: EClosure toEClosure = (EClosure) eStates2EClosure
0766: .get(trans_toEStates);
0767: if (toEClosure != null) {
0768: for (Transition newTrans = eClosure.transitions; newTrans != null; newTrans = newTrans.next) {
0769: if (newTrans.toEClosure == toEClosure) {
0770: if (newTrans.properties == null
0771: && trans.properties == null
0772: || newTrans.properties != null
0773: && newTrans.properties
0774: .equals(trans.properties)) {
0775: newTrans.charSet
0776: .addAll(trans.charSet);
0777: continue loop;
0778: }
0779: }
0780: }
0781: } else {
0782: toEClosure = new EClosure(trans_toEStates);
0783: eStates2EClosure.put(trans_toEStates,
0784: toEClosure);
0785: }
0786:
0787: if (trans_charSet == trans.charSet)
0788: trans_charSet = (ISet_char) trans.charSet
0789: .clone();
0790: if (trans.properties == null)
0791: eClosure.addTransition(null, trans_charSet,
0792: toEClosure);
0793: else {
0794: eClosure.addTransition(
0795: (IProperties) trans.properties
0796: .clone(), trans_charSet,
0797: toEClosure);
0798: }
0799: }
0800: }
0801: }
0802:
0803: if (eClosure.state == null)
0804: eClosure.state = this .addState(eClosure.states
0805: .isFinal());
0806: for (Transition trans = eClosure.transitions; trans != null; trans = trans.next) {
0807: if (trans.toEClosure.state == null)
0808: trans.toEClosure.state = this
0809: .addState(trans.toEClosure.states.isFinal());
0810:
0811: State.Transition newTrans = eClosure.state
0812: .addTransition(trans.properties, trans.charSet,
0813: trans.toEClosure.state);
0814:
0815: eClosureSet.add(trans.toEClosure);
0816: }
0817:
0818: }
0819:
0820: this .isDeterministic = Automaton.UNKNOWN;
0821: return startEClosure.state;
0822: }
0823:
0824: protected void minimize() {
0825: if (this .startState == null)
0826: return;
0827: SState state = (SState) this .startState;
0828:
0829: int states = this .aStates.size();
0830: this .setStartState(this .minimize(state));
0831: // this.setStartState(this.makeDeterministic(state));
0832:
0833: this .removeUnreachableStates();
0834: if (this .aStates.size() > states)
0835: throw new Error("more states(" + this .aStates.size()
0836: + ") after minimzing than before (" + states + ")");
0837: }
0838:
0839: private static class Tupel {
0840: final SState a;
0841: final SState b;
0842: final int hashCode;
0843:
0844: Tupel next = null;
0845:
0846: Tupel(SState a, SState b) {
0847: if (a == b)
0848: throw new Error("a==b");
0849: this .a = a;
0850: this .b = b;
0851:
0852: this .hashCode = (int) ((((long) a.hashCode()) + ((long) b
0853: .hashCode())) % 4294967291L);
0854: }
0855:
0856: public boolean equals(Object obj) {
0857: if (this == obj)
0858: return true;
0859:
0860: final Tupel tupel = (Tupel) obj;
0861: if (this .a != tupel.a && this .a != tupel.b)
0862: return false;
0863: if (this .b != tupel.a && this .b != tupel.b)
0864: return false;
0865: return true;
0866: }
0867:
0868: public int hashCode() {
0869: return this .hashCode;
0870: }
0871: }
0872:
0873: protected SState minimize(SState state) {
0874:
0875: //System.out.println("states before makeDeterministic: "+state.getAllReachableStates().size());
0876: SState newStartState = this .makeDeterministic(state);
0877: //System.out.println("states after makeDeterministic: "+newStartState.getAllReachableStates().size());
0878: if (this .aStates.contains(newStartState) == false)
0879: throw new Error(
0880: "this.states.contains(newStartState)==false");
0881:
0882: LinkedSet_State states = newStartState.getAllReachableStates();
0883: states.add(newStartState);
0884:
0885: final SState totalState = this .addState(false);
0886: states.add(totalState);
0887: //System.out.println("totalState: "+totalState);
0888:
0889: HashSet tupelList_ne = new HashSet();
0890: Tupel tupelList = null;
0891: for (Wrapper_State w1 = states.elements; w1 != null; w1 = w1.next) {
0892: ISet_char rest = (ISet_char) this .fullSet.clone();
0893: for (State.Transition trans = w1.state.transitions; trans != null; trans = trans.next) {
0894: rest.removeAll(trans.charSet);
0895: }
0896: if (rest.isEmpty() == false)
0897: ((SState) w1.state).addTransition(null, rest,
0898: totalState);
0899:
0900: for (Wrapper_State w2 = w1.next; w2 != null; w2 = w2.next) {
0901: Tupel tupel = new Tupel((SState) w1.state,
0902: (SState) w2.state);
0903: if (tupel.a.isFinal ^ tupel.b.isFinal)
0904: tupelList_ne.add(tupel);
0905: else {
0906: tupel.next = tupelList;
0907: tupelList = tupel;
0908: }
0909: }
0910: }
0911:
0912: //System.out.println("++++++++++++++++++++++++++++++++++++++");
0913: //for (Tupel tupel=tupelList; tupel!=null; tupel=tupel.next) {
0914: // System.out.println(tupel.a +"=="+tupel.b );
0915: //}
0916: //Iterator _it = tupelList_ne.iterator();
0917: //while (_it.hasNext() ) {
0918: // Tupel t = (Tupel)_it.next();
0919: // System.out.println( t.a+"!="+t.b );
0920: //}
0921:
0922: boolean flag = true;
0923: while (flag) {
0924: flag = false;
0925: loop: for (Tupel tupel = tupelList, prev = null; tupel != null; tupel = tupel.next) {
0926: for (State.Transition trans_a = tupel.a.transitions; trans_a != null; trans_a = trans_a.next) {
0927: for (State.Transition trans_b = tupel.b.transitions; trans_b != null; trans_b = trans_b.next) {
0928: if (trans_a.toState != trans_b.toState) {
0929: Tupel newTupel = new Tupel(
0930: (SState) trans_a.toState,
0931: (SState) trans_b.toState);
0932: if (tupelList_ne.contains(newTupel)) {
0933: ISet_char intersection = (ISet_char) trans_a.charSet
0934: .clone();
0935: intersection.retainAll(trans_b.charSet);
0936: if (intersection.isEmpty() == false) {
0937: if (prev == null)
0938: tupelList = tupel.next;
0939: else
0940: prev.next = tupel.next;
0941:
0942: tupelList_ne.add(tupel);
0943:
0944: flag = true;
0945: continue loop;
0946: }
0947: }
0948: }
0949: }
0950: }
0951: prev = tupel;
0952: }
0953: }
0954:
0955: //System.out.println("#############################");
0956: //for (Tupel tupel=tupelList; tupel!=null; tupel=tupel.next) {
0957: // System.out.println(tupel.a.stateNr +"=="+tupel.b.stateNr );
0958: //}
0959: // _it = tupelList_ne.iterator();
0960: //while (_it.hasNext() ) {
0961: // Tupel t = (Tupel)_it.next();
0962: // System.out.println( t.a.stateNr+"!="+t.b.stateNr );
0963: //}
0964:
0965: //should be IdentityMap
0966: final HashMap map = new HashMap();
0967: for (Tupel tupel = tupelList; tupel != null; tupel = tupel.next) {
0968: SState eqState = (SState) map.get(tupel.a);
0969: if (eqState != null)
0970: map.put(tupel.b, eqState);
0971: else {
0972: eqState = (SState) map.get(tupel.b);
0973: if (eqState != null)
0974: map.put(tupel.a, eqState);
0975: else if (tupel.b != totalState)
0976: map.put(tupel.a, tupel.b);
0977: else
0978: map.put(tupel.b, tupel.a);
0979: }
0980: }
0981:
0982: //System.out.println("***********************************");
0983: //Iterator it_ = map.keySet().iterator();
0984: //while (it_.hasNext()) {
0985: // State key = (State)it_.next();
0986: // System.out.println(key.stateNr+"="+((State)map.get(key)).stateNr);
0987: //}
0988:
0989: this .removeState(totalState);
0990:
0991: for (Wrapper_State w = states.elements; w != null; w = w.next) {
0992: SState newState = (SState) map.get(w.state);
0993: if (newState == null) {
0994: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
0995: SState newToState = (SState) map.get(trans.toState);
0996: if (newToState != null) {
0997: ((SState) w.state).removeTransition(trans);
0998:
0999: for (State.Transition tmp = w.state.transitions; tmp != null; tmp = tmp.next) {
1000: if (tmp.toState == newToState) {
1001: if (tmp.properties == null
1002: && trans.properties == null
1003: || tmp.properties != null
1004: && tmp.properties
1005: .equals(trans.properties)) {
1006: ((SState) w.state)
1007: .removeTransition(tmp);
1008: trans.charSet.addAll(tmp.charSet);
1009: break;
1010: }
1011: }
1012: }
1013:
1014: ((SState) w.state).addTransition(
1015: trans.properties, trans.charSet,
1016: newToState);
1017: }
1018: }
1019: } else {
1020: loop: for (State.Transition trans = w.state.transitions; trans != null; trans = trans.next) {
1021: SState newToState = (SState) map.get(trans.toState);
1022: if (newToState == null)
1023: newToState = (SState) trans.toState;
1024:
1025: ((SState) w.state).removeTransition(trans);
1026:
1027: for (State.Transition tmp = newState.transitions; tmp != null; tmp = tmp.next) {
1028: if (tmp.toState == newToState) {
1029: if (tmp.properties == null
1030: && trans.properties == null
1031: || tmp.properties != null
1032: && tmp.properties
1033: .equals(trans.properties)) {
1034: continue loop;
1035: }
1036: }
1037: }
1038:
1039: newState.addTransition(trans.properties,
1040: trans.charSet, newToState);
1041: }
1042: }
1043: }
1044:
1045: Iterator it = map.keySet().iterator();
1046: for (int i = map.size(); i > 0; --i)
1047: this .removeState((SState) it.next());
1048:
1049: SState newNewStartState = (SState) map.get(newStartState);
1050: if (newNewStartState != null)
1051: return newNewStartState;
1052: return newStartState;
1053: }
1054:
1055: }
|