// State.java
/*
Copyright 2005 Takuya Murata
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
import java.util.*;
import java.io.*;
public final class State {
public static interface Delta {
public void move (int input, Collection<State> result);
}
public static final Delta nil = new Delta () {
public void move (int input, Collection<State> result) { }
};
public static final int
EMPTY = -2, BEGIN_INPUT = -1, EOF = -1, ACCEPT = 0;
public String label; // for the debugging purpose.
private Delta delta = nil;
public State () {
this.label = super.toString ().replaceAll ("^.+@", "@");
}
private State (String label, int i) {
this.label = label + super.toString ().replaceAll ("^.+@", "@");
}
public State (String label) {
this.label = label;
}
public void setTransition (final int entry, final State dest) {
final Delta prev = delta;
delta = new Delta () {
public void move (int input, Collection<State> result) {
if (entry == input)
result.add (dest);
prev.move (input, result);
}
};
}
public void setTransition (final String inputs, final State dest) {
final Delta prev = delta;
delta = new Delta () {
public void move (int input, Collection<State> result) {
if (inputs.contains (input))
result.add (dest);
prev.move (input, result);
}
};
}
public void setTransition (final Delta d) {
final Delta prev = delta;
delta = new Delta () {
public void move (int input, Collection<State> result) {
d.move (input, result);
prev.move (input, result);
}
};
}
public static final State[] toArray (Collection<State> col) {
return col.toArray (new State[col.size ()]);
}
public static Set<State> closure (Collection<State> t) {
Set<State> ret = new HashSet<State> (t);
for (;;) {
Collection<State> u = new ArrayList<State> ();
for (State s : t) {
Delta d = s.delta;
d.move (State.EMPTY, ret);
d.move (State.EMPTY, u);
}
if (u.isEmpty ())
break;
else
t = u;
}
return ret;
}
public static Set<State> move (Set<State> t, int input) {
assert BEGIN_INPUT <= input && input < 256;
Set<State> ret = new HashSet<State> ();
for (State s : closure (t))
s.delta.move (input, ret);
return ret;
}
public State[] move (int input) {
return toArray (move (Collections.singleton (this), input));
}
// A set of states reachable from this state without shifting an input.
public State[] closure () {
return toArray (closure (Collections.singleton (this)));
}
public State[] move (CharSequence string) {
Set<State> ret = Collections.singleton (this);
for (int i = 0; i < string.length (); i++)
ret = move (ret, string.charAt (i));
return toArray (ret);
}
private static class SingleItemSet<T> extends AbstractList<T> implements Set<T> {
private T item = null;
public int size () { return (item != null) ? 1 : 0; }
public T get (int i) { return item; }
public T set (int i, T item) {
T ret = this.item;
assert 0 <= i && i < size ();
this.item = item;
return ret;
}
public void add (int i, T item) {
assert i == 0;
this.item = item;
}
public T remove (int i) { return set (i, null); }
public T first () { return item; }
}
public State moveDFA (int input) {
if (input == EMPTY)
return this;
SingleItemSet<State> t = new SingleItemSet<State> ();
delta.move (input, t);
if (!t.isEmpty ())
return t.first ();
else
return null;
}
public State moveDFA (CharSequence string) {
State s = this;
for (int i = 0; i < string.length (); i++) {
s = s.moveDFA (string.charAt (i));
if (s == null)
return null;
}
return s;
}
private static State createState (Set<State> t, Map<Set<State>, State> table) {
State existing = table.get (t);
if (existing != null)
return existing;
// We now need to make a new state for this states set.
State q = new State ("q" + table.size ());
table.put (t, q);
for (int i = BEGIN_INPUT; i < 256; i++) {
assert i != EMPTY : i;
Set<State> u = move (t, i);
if (!u.isEmpty ())
q.setTransition (i, createState (u, table));
}
return q;
}
public State toDFA () {
Map<Set<State>, State> table = new HashMap<Set<State>, State> ();
return createState (Collections.singleton (this), table);
}
private void prettyPrint (StringBuffer buf, Collection<State> marked) {
if (marked.contains (this))
return;
marked.add (this);
buf.append (label + "[");
boolean notfirst = false;
for (int i = BEGIN_INPUT; i < 256; i++) {
Set<State> t = move (Collections.singleton (this), i);
if (!t.isEmpty ()) {
if (notfirst)
buf.append (", ");
if (i == EMPTY)
buf.append ("@e");
else if (i == ACCEPT)
buf.append ("@acc");
else
buf.append ((char) i);
buf.append (":" + t);
notfirst = true;
}
}
buf.append ("]\n");
for (int i = BEGIN_INPUT; i < 256; i++) {
Set<State> t = move (Collections.singleton (this), i);
for (State s : t)
s.prettyPrint (buf, marked);
}
}
public String outputString () {
Set<State> marked = new HashSet<State> ();
StringBuffer buf = new StringBuffer ();
this.prettyPrint (buf, marked);
return buf.toString ();
}
public String toString () {
return label;
}
// Create states and transitions for a string sequence
public static final State[] stringSequence (CharSequence string) {
int len = string.length ();
State q[] = new State[len + 1]; // need s[len]
for (int i = 0; i <= len; i++)
q[i] = new State ("q" + i, 0);
for (int i = 0; i < len; i++)
q[i].setTransition (string.charAt (i), q[i + 1]);
return new State[] { q[0], q[len] };
}
public static final State[] stringSequenceIgnoreCase (CharSequence string) {
int len = string.length ();
State q[] = new State[len + 1]; // need s[len]
for (int i = 0; i <= len; i++)
q[i] = new State ("q" + i, 0);
for (int i = 0; i < len; i++) {
char
lower = Character.toLowerCase (string.charAt (i)),
upper = Character.toUpperCase (lower);
q[i].setTransition (lower, q[i + 1]);
q[i].setTransition (upper, q[i + 1]);
}
return new State[] { q[0], q[len] };
}
}
