1 package net.kwfgrid.gworkflowdl.analysis;
2
3 import java.util.ArrayList;
4 import java.util.HashSet;
5 import java.util.Iterator;
6
7 /***
8 * Created by IntelliJ IDEA.
9 * User: hans
10 * Date: 28.10.2005
11 * Time: 14:36:39
12 * To change this template use File | Settings | File Templates.
13 */
14 public class FiniteStateMachine extends Net {
15 public static int MAX_COMPLEXITY = 200000;
16
17
18 public boolean[] quasiLivePlaces;
19 public boolean[] quasiLiveTransitions;
20 public boolean[] isFinallyMarked;
21
22
23 public Marking[] states = null;
24
25 public HashSet stateList = new HashSet();
26 private HashSet unprocessed = new HashSet();
27
28
29 public void build() {
30 type = Net.FINITE_STATE_MACHINE;
31 if (capacities == null) {
32 capacities = new Marking(N, KarpMillerTree.INFINITY);
33 }
34 quasiLivePlaces = new boolean[N];
35 quasiLiveTransitions = new boolean[transitions.length];
36 isFinallyMarked = new boolean[N];
37
38 for (int i = 0; i < N; i++) {
39 quasiLivePlaces[i] = false;
40 isFinallyMarked[i] = true;
41 }
42 quasiLiveTransitions = new boolean[transitions.length];
43 for (int i = 0; i < transitions.length; i++) {
44 quasiLiveTransitions[i] = false;
45 }
46
47 unprocessed.add(initial);
48 while (unprocessed.size() > 0) {
49 if (complexity > MAX_COMPLEXITY) {
50 break;
51 }
52 if (stateList.size() % 1000 == 0) System.out.println(stateList.size() + " " + unprocessed.size());
53 Iterator it = unprocessed.iterator();
54 Marking m = (Marking) it.next();
55
56 unprocessed.remove(m);
57
58
59 stateList.add(m);
60 complexity += N;
61
62 for (int i = 0; i < N; i++) {
63 if (m.get(i) > 0) {
64 quasiLivePlaces[i] = true;
65 }
66 }
67
68 boolean dead = true;
69 for (int i = 0; i < transitions.length; i++) {
70 Marking newM = transitions[i].fire(m, capacities);
71 if (newM != null) {
72 dead = false;
73 quasiLiveTransitions[i] = true;
74
75
76
77
78
79
80
81 if (!stateList.contains(newM)
82 unprocessed.add(newM);
83 }
84 }
85 }
86 if (dead) {
87 for (int i = 0; i < N; i++) {
88 if (m.get(i) == 0) {
89 isFinallyMarked[i] = false;
90 }
91 }
92 }
93 }
94 states = new Marking[stateList.size()];
95
96
97
98
99
100 Iterator it = stateList.iterator();
101 int i = 0;
102 while (it.hasNext()) {
103 states[i++] = (Marking) it.next();
104 }
105 System.out.println("statesNum = " + states.length);
106 }
107
108
109
110
111
112
113
114
115 public boolean isFireable(int t) {
116 return quasiLiveTransitions[t];
117 }
118
119 public boolean isFinallyMarked(int p) {
120 return isFinallyMarked[p];
121 }
122
123 public boolean oneOfIsFinallyMarked(int[] is) {
124 boolean ret = true;
125 for (int i = 0; i < states.length; i++) {
126 Marking m = states[i];
127 boolean dead = true;
128 for (int j = 0; j < transitions.length; j++) {
129 if (transitions[j].fire(m, capacities) != null) {
130 dead = false;
131 break;
132 }
133 }
134 if (dead) {
135 boolean flag = false;
136 for (int k = 0; k < is.length; k++) {
137 if (m.get(is[k]) > 0) {
138 flag = true;
139 break;
140 }
141 }
142 if (!flag) {
143 return false;
144 }
145 }
146 }
147 return true;
148 }
149
150 public boolean isQuasiLive(int p) {
151 return quasiLivePlaces[p];
152 }
153
154
155 public void gatherDecisions(Marking m, HashSet gather) {
156
157
158 for (int placeIndex = 0; placeIndex < N; placeIndex++) {
159
160 int type = -1;
161 if (m.get(placeIndex) == 1) {
162 type = Decision.TAKE_CONFLICT;
163 } else {
164 type = Decision.TAKE_CHOICE;
165 }
166
167 ArrayList list = new ArrayList();
168 for (int j = 0; j < transitions.length; j++) {
169 Marking next = transitions[j].fire(m, capacities);
170 Marking in = transitions[j].in;
171 if (next != null && in.get(placeIndex) > 0) {
172 list.add(new Integer(j));
173 }
174 }
175
176 if (list.size() > 1) {
177 IndexDecision id = new IndexDecision();
178 id.type = type;
179 id.placeIndex = placeIndex;
180 id.transitionIndices = list;
181 gather.add(id);
182 }
183 }
184
185
186 for (int placeIndex = 0; placeIndex < N; placeIndex++) {
187
188 int type = -1;
189 if (m.get(placeIndex) == capacities.get(placeIndex) - 1) {
190 type = Decision.PUT_CONFLICT;
191 } else {
192 type = Decision.PUT_CHOICE;
193 }
194
195 ArrayList list = new ArrayList();
196 for (int j = 0; j < transitions.length; j++) {
197 Marking next = transitions[j].fire(m, capacities);
198 Marking out = transitions[j].out;
199 if (next != null && out.get(placeIndex) > 0) {
200 list.add(new Integer(j));
201 }
202 }
203
204 if (list.size() > 1) {
205 IndexDecision id = new IndexDecision();
206 id.type = type;
207 id.placeIndex = placeIndex;
208 id.transitionIndices = list;
209 gather.add(id);
210
211 }
212 }
213 }
214
215
216 public HashSet gatherDecisions() {
217 HashSet gather = new HashSet();
218 for (int i = 0; i < states.length; i++) {
219 gatherDecisions(states[i], gather);
220 }
221 return gather;
222 }
223 }