001: package com.tc.jrexx.set;
002:
003: /*
004: * 01/07/2003 - 15:19:32
005: *
006: * Automaton.java -
007: * Copyright (C) 2003 Buero fuer Softwarearchitektur GbR
008: InputStream* ralf.meyer@karneim.com
009: * http://jrexx.sf.net
010: *
011: * This program is free software; you can redistribute it and/or
012: * modify it under the terms of the GNU Lesser General Public License
013: * as published by the Free Software Foundation; either version 2
014: * of the License, or (at your option) any later version.
015: *
016: * This program is distributed in the hope that it will be useful,
017: * but WITHOUT ANY WARRANTY; without even the implied warranty of
018: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
019: * GNU Lesser General Public License for more details.
020: *
021: * You should have received a copy of the GNU Lesser General Public License
022: * along with this program; if not, write to the Free Software
023: * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
024: */
025: import java.io.*;
026: import java.util.*;
027:
028: /**
029: * DFASet is an immutable Set of strings based on a minimized deterministic automaton (DFA).
030: * @author Ralf Meyer
031: */
032: public class DFASet {
033:
034: protected static class State {
035: protected static class Transition {
036: protected final CharSet charSet;
037: protected final int toState;
038:
039: protected Transition(CharSet charSet, int toState) {
040: this .charSet = charSet;
041: this .toState = toState;
042: }
043: }
044:
045: protected final boolean isFinal;
046: protected final Transition[] transitions;
047:
048: protected State(boolean isFinal, Transition[] transitions) {
049: this .isFinal = isFinal;
050: this .transitions = transitions;
051: }
052: }
053:
054: protected final State[] states;
055: protected final Integer startState;
056:
057: protected DFASet(State[] states, Integer startState) {
058: this .states = states;
059: this .startState = startState;
060: }
061:
062: public DFASet(FSAData automaton) {
063: if (automaton == null)
064: throw new IllegalArgumentException("automaton==null");
065:
066: HashMap map = new HashMap();
067:
068: State[] newStates = new State[automaton.states == null ? 0
069: : automaton.states.length];
070:
071: for (int i = 0; i < newStates.length; ++i) {
072: FSAData.State state = automaton.states[i];
073: if (state == null)
074: throw new IllegalArgumentException((i + 1)
075: + ". state of automaton is null");
076:
077: State.Transition[] newTransitions = new State.Transition[state.transitions == null ? 0
078: : state.transitions.length];
079:
080: for (int t = 0; t < newTransitions.length; ++t) {
081: FSAData.State.Transition trans = state.transitions[t];
082: if (trans == null)
083: throw new IllegalArgumentException((t + 1)
084: + ". transition of state " + state.number
085: + " is null");
086: if (trans.charSet == null)
087: throw new IllegalArgumentException("charSet of "
088: + (t + 1) + ". transition of state "
089: + state.number + " is null");
090:
091: CharSet newCharSet = (CharSet) map.get(trans.charSet);
092: if (newCharSet == null) {
093: newCharSet = new CharSet(trans.charSet);
094: map.put(trans.charSet, newCharSet);
095: }
096:
097: int toStateNr = 0;
098: try {
099: while (automaton.states[toStateNr].number != trans.toStateNumber)
100: ++toStateNr;
101: } catch (ArrayIndexOutOfBoundsException e) {
102: throw new IllegalArgumentException("toState "
103: + trans.toStateNumber + " of " + (t + 1)
104: + ". transition of state " + state.number
105: + " does not exist");
106: }
107:
108: newTransitions[t] = new State.Transition(newCharSet,
109: toStateNr);
110: }
111:
112: newStates[i] = new State(state.isFinal, newTransitions);
113: }
114:
115: this .states = newStates;
116:
117: if (automaton.startStateNumber == null)
118: this .startState = null;
119: else {
120: int automatonStartStateNr = automaton.startStateNumber
121: .intValue();
122: int startStateNr = 0;
123: try {
124: while (automaton.states[startStateNr].number != automatonStartStateNr)
125: ++startStateNr;
126: } catch (ArrayIndexOutOfBoundsException e) {
127: throw new IllegalArgumentException("startState "
128: + automaton.startStateNumber
129: + " does not exist");
130: }
131: this .startState = new Integer(startStateNr);
132: }
133: }
134:
135: protected static FSAData toFSAData(Object obj) {
136: if (obj.getClass() != FSAData.class) {
137: SAutomatonData data = (SAutomatonData) obj;
138:
139: FSAData.State[] newStates = new FSAData.State[data.states == null ? 0
140: : data.states.length];
141: for (int i = 0; i < newStates.length; ++i) {
142: SAutomatonData.State state = data.states[i];
143: if (state != null) {
144: FSAData.State.Transition[] newTransitions = new FSAData.State.Transition[state.transitions == null ? 0
145: : state.transitions.length];
146: for (int t = 0; t < newTransitions.length; ++t) {
147: SAutomatonData.State.Transition trans = state.transitions[t];
148: newTransitions[t] = new FSAData.State.Transition(
149: trans.properties, trans.charSet,
150: trans.toStateNumber);
151: }
152: newStates[i] = new FSAData.State(state.number,
153: state.isFinal, newTransitions,
154: state.transitionsAreDeterministic);
155: }
156: }
157: return new FSAData(newStates, data.startStateNumber,
158: data.isDeterministic);
159:
160: } else {
161: FSAData data = (FSAData) obj;
162: switch (data.objectVersion) {
163: case FSAData.classVersion:
164: return data;
165: default:
166: return data;
167: }
168: }
169: }
170:
171: public DFASet(InputStream dfaDataStream) throws IOException,
172: ClassNotFoundException {
173: this (DFASet.toFSAData(new ObjectInputStream(dfaDataStream)
174: .readObject()));
175: }
176:
177: public boolean contains(char[] chars) {
178: return this .contains(chars, 0, chars.length);
179: }
180:
181: public boolean contains(char[] chars, int offset) {
182: return this .contains(chars, offset, chars.length - offset);
183: }
184:
185: public boolean contains(char[] chars, int offset, int length) {
186: if (this .startState == null)
187: return false;
188: State state = this .states[this .startState.intValue()];
189:
190: loop: for (; length > 0; ++offset, --length) {
191: for (int i = 0; i < state.transitions.length; ++i) {
192: if (state.transitions[i].charSet
193: .contains(chars[offset])) {
194: state = this .states[state.transitions[i].toState];
195: continue loop;
196: }
197: }
198: return false;
199: }
200:
201: return state.isFinal;
202: }
203:
204: public boolean contains(String s) {
205: return this .contains(s, 0, s.length());
206: }
207:
208: public boolean contains(String s, int offset) {
209: return this .contains(s, offset, s.length() - offset);
210: }
211:
212: public boolean contains(String s, int offset, int length) {
213: if (this .startState == null)
214: return false;
215: State state = this .states[this .startState.intValue()];
216:
217: loop: for (; length > 0; ++offset, --length) {
218: for (int i = 0; i < state.transitions.length; ++i) {
219: if (state.transitions[i].charSet.contains(s
220: .charAt(offset))) {
221: state = this .states[state.transitions[i].toState];
222: continue loop;
223: }
224: }
225: return false;
226: }
227:
228: return state.isFinal;
229: }
230:
231: public boolean contains(java.io.Reader in)
232: throws java.io.IOException {
233: if (this .startState == null)
234: return false;
235: State state = this .states[this .startState.intValue()];
236:
237: loop: for (int ch = in.read(); ch != -1; ch = in.read()) {
238: for (int i = 0; i < state.transitions.length; ++i) {
239: if (state.transitions[i].charSet.contains((char) ch)) {
240: state = this .states[state.transitions[i].toState];
241: continue loop;
242: }
243: }
244: return false;
245: }
246:
247: return state.isFinal;
248: }
249:
250: }
|