-
Notifications
You must be signed in to change notification settings - Fork 2.7k
/
DFSAState.java
150 lines (120 loc) · 3.43 KB
/
DFSAState.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
package edu.stanford.nlp.fsm;
import edu.stanford.nlp.util.Generics;
import edu.stanford.nlp.util.Scored;
import java.util.*;
/**
* DFSAState represents the state of a deterministic finite state
* automaton without epsilon transitions.
*
* @author Dan Klein
* @version 12/14/2000
* @author Sarah Spikes ([email protected]) - cleanup and filling in types
* @param <S> stateID type
* @param <T> transition type
*/
public final class DFSAState<T,S> implements Scored {
private S stateID;
private Map<T,DFSATransition<T,S>> inputToTransition;
public boolean accepting;
private DFSA<T,S> dfsa;
public double score;
public double score() {
return score;
}
public void setScore(double score) {
this.score = score;
}
public DFSA<T, S> dfsa() {
return dfsa;
}
public void setStateID(S stateID) {
this.stateID = stateID;
}
public S stateID() {
return stateID;
}
public void addTransition(DFSATransition<T,S> transition) {
inputToTransition.put(transition.input(), transition);
}
public DFSATransition<T,S> transition(T input) {
return inputToTransition.get(input);
}
public Collection<DFSATransition<T,S>> transitions() {
return inputToTransition.values();
}
public Set<T> continuingInputs() {
return inputToTransition.keySet();
}
public Set<DFSAState<T,S>> successorStates() {
Set<DFSAState<T,S>> successors = Generics.newHashSet();
Collection<DFSATransition<T, S>> transitions = inputToTransition.values();
for (DFSATransition<T,S> transition : transitions) {
successors.add(transition.getTarget());
}
return successors;
}
public void setAccepting(boolean accepting) {
this.accepting = accepting;
}
public boolean isAccepting() {
return accepting;
}
public boolean isContinuable() {
return !inputToTransition.isEmpty();
}
@Override
public String toString() {
return stateID.toString();
}
private int hashCodeCache; // = 0;
@Override
public int hashCode() {
if (hashCodeCache == 0) {
hashCodeCache = stateID.hashCode() ^ dfsa.hashCode();
}
return hashCodeCache;
}
// equals
@SuppressWarnings("unchecked")
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof DFSAState)) {
return false;
}
DFSAState s = (DFSAState) o;
// historically also checked: accepting == s.accepting &&
//inputToTransition.equals(s.inputToTransition))
return dfsa.equals(s.dfsa) && stateID.equals(s.stateID);
}
public Set<DFSAState<T, S>> statesReachable() {
Set<DFSAState<T, S>> visited = Generics.newHashSet();
List<DFSAState<T, S>> toVisit = new ArrayList<>();
toVisit.add(this);
exploreStates(toVisit, visited);
return visited;
}
private void exploreStates(List<DFSAState<T, S>> toVisit, Set<DFSAState<T, S>> visited) {
while (!toVisit.isEmpty()) {
DFSAState<T, S> state = toVisit.get(toVisit.size() - 1);
toVisit.remove(toVisit.size() - 1);
if (!visited.contains(state)) {
toVisit.addAll(state.successorStates());
visited.add(state);
}
}
}
public DFSAState(S id, DFSA<T,S> dfsa) {
this.dfsa = dfsa;
this.stateID = id;
this.accepting = false;
this.inputToTransition = Generics.newHashMap();
this.score = Double.NEGATIVE_INFINITY;
}
public DFSAState(S id, DFSA<T,S> dfsa, double score) {
this(id,dfsa);
setScore(score);
}
}