1 package Analysis.TaskStateAnalysis;
2 import Analysis.TaskStateAnalysis.*;
10 public class FlagState {
11 /* NodeStatus enumeration pattern ***********/
13 public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
14 public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
15 public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
17 public static class NodeStatus {
18 private static String name;
19 private NodeStatus(String name) { this.name = name; }
20 public String toString() { return name; }
24 int discoverytime = -1;
25 int finishingtime = -1; /* used for searches */
27 Vector edges = new Vector();
28 Vector inedges = new Vector();
29 NodeStatus status = UNVISITED;
30 protected String dotnodeparams = new String();
34 private static int nodeid=0;
36 private final HashSet flagstate;
37 private final ClassDescriptor cd;
39 public void setOption(String option) {
40 this.nodeoption=","+option;
43 public void setMerge() {
47 public FlagState(ClassDescriptor cd) {
48 this.flagstate=new HashSet();
50 this.uid=FlagState.nodeid++;
53 private FlagState(HashSet flagstate, ClassDescriptor cd) {
54 this.flagstate=flagstate;
56 this.uid=FlagState.nodeid++;
59 public boolean get(FlagDescriptor fd) {
60 return flagstate.contains(fd);
63 public String toString() {
64 return cd.toString()+getTextLabel();
67 public Iterator getFlags() {
68 return flagstate.iterator();
71 public String toString(FlagDescriptor[] flags)
73 StringBuffer sb = new StringBuffer(flagstate.size());
74 for(int i=0;i < flags.length; i++)
82 return new String(sb);
86 public ClassDescriptor getClassDescriptor(){
90 public FlagState setFlag(FlagDescriptor fd, boolean status) {
91 HashSet newset=(HashSet) flagstate.clone();
94 else if (newset.contains(fd)){
97 return new FlagState(newset, cd);
100 public boolean equals(Object o) {
101 if (o instanceof FlagState) {
102 FlagState fs=(FlagState)o;
105 return fs.flagstate.equals(flagstate);
110 public int hashCode() {
111 return cd.hashCode()^flagstate.hashCode();
114 public static void computeclosure(Collection nodes, Collection removed) {
115 Stack tovisit=new Stack();
116 tovisit.addAll(nodes);
117 while(!tovisit.isEmpty()) {
118 FlagState gn=(FlagState)tovisit.pop();
119 for(Iterator it=gn.edges();it.hasNext();) {
120 Edge edge=(Edge)it.next();
121 FlagState target=edge.getTarget();
122 if (!nodes.contains(target)) {
123 if ((removed==null)||
124 (!removed.contains(target))) {
126 tovisit.push(target);
133 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
134 Stack tovisit=new Stack();
135 Stack newvisit=new Stack();
136 tovisit.addAll(nodes);
137 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
138 while(!tovisit.isEmpty()) {
139 FlagState gn=(FlagState)tovisit.pop();
140 for(Iterator it=gn.edges();it.hasNext();) {
141 Edge edge=(Edge)it.next();
142 FlagState target=edge.getTarget();
143 if (!nodes.contains(target)) {
144 if ((removed==null)||
145 (!removed.contains(target))) {
147 newvisit.push(target);
153 newvisit=new Stack();
157 public void setDotNodeParameters(String param) {
159 throw new NullPointerException();
161 if (param.length() > 0) {
162 dotnodeparams = "," + param;
164 dotnodeparams = new String();
168 public void setStatus(NodeStatus status) {
169 if (status == null) {
170 throw new NullPointerException();
172 this.status = status;
175 public String getLabel() {
179 public String getTextLabel() {
181 for(Iterator it=getFlags();it.hasNext();) {
182 FlagDescriptor fd=(FlagDescriptor) it.next();
186 label+=", "+fd.toString();
191 public NodeStatus getStatus() {
195 public Iterator edges() {
196 return edges.iterator();
199 public Iterator inedges() {
200 return inedges.iterator();
203 public void addEdge(Edge newedge) {
204 newedge.setSource(this);
205 edges.addElement(newedge);
206 FlagState tonode=newedge.getTarget();
207 tonode.inedges.addElement(newedge);
220 void discover(int time) {
221 discoverytime = time;
225 void finish(int time) {
226 assert status == PROCESSING;
227 finishingtime = time;
231 /** Returns finishing time for dfs */
233 public int getFinishingTime() {
234 return finishingtime;
238 public static class DOTVisitor {
240 java.io.PrintWriter output;
244 private DOTVisitor(java.io.OutputStream output) {
247 this.output = new java.io.PrintWriter(output, true);
250 private String getNewID(String name) {
251 tokennumber = tokennumber + 1;
252 return new String (name+tokennumber);
258 public static void visit(java.io.OutputStream output, Collection nodes) {
259 visit(output,nodes,null);
262 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
263 DOTVisitor visitor = new DOTVisitor(output);
264 visitor.special=special;
265 visitor.nodes = nodes;
269 private void make() {
270 output.println("digraph dotvisitor {");
271 output.println("\trotate=90;");
272 /* output.println("\tpage=\"8.5,11\";");
273 output.println("\tnslimit=1000.0;");
274 output.println("\tnslimit1=1000.0;");
275 output.println("\tmclimit=1000.0;");
276 output.println("\tremincross=true;");*/
277 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
278 output.println("\tedge [fontsize=6];");
280 output.println("}\n");
283 private void traverse() {
284 Iterator i = nodes.iterator();
285 while (i.hasNext()) {
286 FlagState gn = (FlagState) i.next();
287 Iterator edges = gn.edges();
288 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
289 String option=gn.nodeoption;
290 if (special!=null&&special.contains(gn))
291 option+=",shape=box";
293 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
296 while (edges.hasNext()) {
297 Edge edge = (Edge) edges.next();
298 FlagState node = edge.getTarget();
299 if (nodes.contains(node)) {
300 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
301 FlagState node2=(FlagState)nodeit.next();
302 String edgelabel = "label=\"" + edge.getLabel() + "\"";
303 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
311 Set nonmerge(FlagState gn) {
312 HashSet newset=new HashSet();
313 HashSet toprocess=new HashSet();
315 while(!toprocess.isEmpty()) {
316 FlagState gn2=(FlagState)toprocess.iterator().next();
317 toprocess.remove(gn2);
321 Iterator edges = gn2.edges();
322 while (edges.hasNext()) {
323 Edge edge = (Edge) edges.next();
324 FlagState node = edge.getTarget();
325 if (!newset.contains(node)&&nodes.contains(node))
335 /** This function returns the set of nodes involved in cycles.
336 * It only considers cycles containing nodes in the set 'nodes'.
338 public static Set findcycles(Collection nodes) {
339 HashSet cycleset=new HashSet();
340 SCC scc=DFS.computeSCC(nodes);
341 if (!scc.hasCycles())
343 for(int i=0;i<scc.numSCC();i++) {
345 cycleset.addAll(scc.getSCC(i));
350 public static class SCC {
354 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
355 this.acyclic=acyclic;
361 /** Returns whether the graph has any cycles */
362 public boolean hasCycles() {
366 /** Returns the number of Strongly Connected Components */
367 public int numSCC() {
371 /** Returns the strongly connected component number for the FlagState gn*/
372 public int getComponent(FlagState gn) {
373 return ((Integer)revmap.get(gn)).intValue();
376 /** Returns the set of nodes in the strongly connected component i*/
377 public Set getSCC(int i) {
378 Integer scc=new Integer(i);
379 return (Set)map.get(scc);
382 /** Returns whether the strongly connected component i contains a cycle */
383 boolean hasCycle(int i) {
384 Integer scc=new Integer(i);
385 Set s=(Set)map.get(scc);
388 Object [] array=s.toArray();
389 FlagState gn=(FlagState)array[0];
390 for(Iterator it=gn.edges();it.hasNext();) {
391 Edge e=(Edge)it.next();
392 if (e.getTarget()==gn)
393 return true; /* Self Cycle */
400 * DFS encapsulates the depth first search algorithm
402 public static class DFS {
407 Vector finishingorder=null;
411 private DFS(Collection nodes) {
414 /** Calculates the strong connected components for the graph composed
415 * of the set of nodes 'nodes'*/
416 public static SCC computeSCC(Collection nodes) {
418 throw new NullPointerException();
420 DFS dfs=new DFS(nodes);
421 dfs.sccmap=new HashMap();
422 dfs.sccmaprev=new HashMap();
423 dfs.finishingorder=new Vector();
424 boolean acyclic=dfs.go();
425 for (Iterator it = nodes.iterator();it.hasNext();) {
426 FlagState gn = (FlagState) it.next();
429 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
430 FlagState gn=(FlagState)dfs.finishingorder.get(i);
431 if (gn.getStatus() == UNVISITED) {
433 dfs.sccindex++; /* Increment scc index */
436 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
439 void dfsprev(FlagState gn) {
440 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
442 gn.setStatus(FINISHED);
443 Integer i=new Integer(sccindex);
444 if (!sccmap.containsKey(i))
445 sccmap.put(i,new HashSet());
446 ((Set)sccmap.get(i)).add(gn);
448 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
449 Edge e=(Edge)edgeit.next();
450 FlagState gn2=e.getSource();
455 public static boolean depthFirstSearch(Collection nodes) {
457 throw new NullPointerException();
460 DFS dfs = new DFS(nodes);
464 private boolean go() {
467 boolean acyclic=true;
468 i = nodes.iterator();
469 while (i.hasNext()) {
470 FlagState gn = (FlagState) i.next();
474 i = nodes.iterator();
475 while (i.hasNext()) {
476 FlagState gn = (FlagState) i.next();
477 assert gn.getStatus() != PROCESSING;
478 if (gn.getStatus() == UNVISITED) {
486 private boolean dfs(FlagState gn) {
487 boolean acyclic=true;
489 Iterator edges = gn.edges();
491 while (edges.hasNext()) {
492 Edge edge = (Edge) edges.next();
493 FlagState node = edge.getTarget();
494 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
496 if (node.getStatus() == UNVISITED) {
499 } else if (node.getStatus()==PROCESSING) {
503 if (finishingorder!=null)
504 finishingorder.add(gn);