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 final HashSet flagstate;
35 private final ClassDescriptor cd;
37 public void setOption(String option) {
38 this.nodeoption=","+option;
41 public void setMerge() {
45 public FlagState(ClassDescriptor cd) {
46 this.flagstate=new HashSet();
50 private FlagState(HashSet flagstate, ClassDescriptor cd) {
51 this.flagstate=flagstate;
55 public boolean get(FlagDescriptor fd) {
56 return flagstate.contains(fd);
59 public String toString() {
60 return cd.toString()+getTextLabel();
63 public Iterator getFlags() {
64 return flagstate.iterator();
67 public String toString(FlagDescriptor[] flags)
69 StringBuffer sb = new StringBuffer(flagstate.size());
70 for(int i=0;i < flags.length; i++)
78 return new String(sb);
82 public ClassDescriptor getClassDescriptor(){
86 public FlagState setFlag(FlagDescriptor fd, boolean status) {
87 HashSet newset=(HashSet) flagstate.clone();
90 else if (newset.contains(fd)){
93 return new FlagState(newset, cd);
96 public boolean equals(Object o) {
97 if (o instanceof FlagState) {
98 FlagState fs=(FlagState)o;
101 return fs.flagstate.equals(flagstate);
106 public int hashCode() {
107 return cd.hashCode()^flagstate.hashCode();
110 public static void computeclosure(Collection nodes, Collection removed) {
111 Stack tovisit=new Stack();
112 tovisit.addAll(nodes);
113 while(!tovisit.isEmpty()) {
114 FlagState gn=(FlagState)tovisit.pop();
115 for(Iterator it=gn.edges();it.hasNext();) {
116 Edge edge=(Edge)it.next();
117 FlagState target=edge.getTarget();
118 if (!nodes.contains(target)) {
119 if ((removed==null)||
120 (!removed.contains(target))) {
122 tovisit.push(target);
129 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
130 Stack tovisit=new Stack();
131 Stack newvisit=new Stack();
132 tovisit.addAll(nodes);
133 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
134 while(!tovisit.isEmpty()) {
135 FlagState gn=(FlagState)tovisit.pop();
136 for(Iterator it=gn.edges();it.hasNext();) {
137 Edge edge=(Edge)it.next();
138 FlagState target=edge.getTarget();
139 if (!nodes.contains(target)) {
140 if ((removed==null)||
141 (!removed.contains(target))) {
143 newvisit.push(target);
149 newvisit=new Stack();
153 public void setDotNodeParameters(String param) {
155 throw new NullPointerException();
157 if (param.length() > 0) {
158 dotnodeparams = "," + param;
160 dotnodeparams = new String();
164 public void setStatus(NodeStatus status) {
165 if (status == null) {
166 throw new NullPointerException();
168 this.status = status;
171 public String getLabel() {
172 return getTextLabel();
175 public String getTextLabel() {
177 for(Iterator it=getFlags();it.hasNext();) {
178 FlagDescriptor fd=(FlagDescriptor) it.next();
182 label+=", "+fd.toString();
187 public NodeStatus getStatus() {
191 public Iterator edges() {
192 return edges.iterator();
195 public Iterator inedges() {
196 return inedges.iterator();
199 public void addEdge(Edge newedge) {
200 newedge.setSource(this);
201 edges.addElement(newedge);
202 FlagState tonode=newedge.getTarget();
203 tonode.inedges.addElement(newedge);
216 void discover(int time) {
217 discoverytime = time;
221 void finish(int time) {
222 assert status == PROCESSING;
223 finishingtime = time;
227 /** Returns finishing time for dfs */
229 public int getFinishingTime() {
230 return finishingtime;
234 public static class DOTVisitor {
236 java.io.PrintWriter output;
240 private DOTVisitor(java.io.OutputStream output) {
243 this.output = new java.io.PrintWriter(output, true);
246 private String getNewID(String name) {
247 tokennumber = tokennumber + 1;
248 return new String (name+tokennumber);
254 public static void visit(java.io.OutputStream output, Collection nodes) {
255 visit(output,nodes,null);
258 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
259 DOTVisitor visitor = new DOTVisitor(output);
260 visitor.special=special;
261 visitor.nodes = nodes;
265 private void make() {
266 output.println("digraph dotvisitor {");
267 output.println("\trotate=90;");
268 /* output.println("\tpage=\"8.5,11\";");
269 output.println("\tnslimit=1000.0;");
270 output.println("\tnslimit1=1000.0;");
271 output.println("\tmclimit=1000.0;");
272 output.println("\tremincross=true;");*/
273 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
274 output.println("\tedge [fontsize=6];");
276 output.println("}\n");
279 private void traverse() {
280 Set cycleset=FlagState.findcycles(nodes);
282 Iterator i = nodes.iterator();
283 while (i.hasNext()) {
284 FlagState gn = (FlagState) i.next();
285 Iterator edges = gn.edges();
286 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
287 String option=gn.nodeoption;
288 if (special!=null&&special.contains(gn))
289 option+=",shape=box";
291 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
294 while (edges.hasNext()) {
295 Edge edge = (Edge) edges.next();
296 FlagState node = edge.getTarget();
297 if (nodes.contains(node)) {
298 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
299 FlagState node2=(FlagState)nodeit.next();
300 String edgelabel = "label=\"" + edge.getLabel() + "\"";
301 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
309 Set nonmerge(FlagState gn) {
310 HashSet newset=new HashSet();
311 HashSet toprocess=new HashSet();
313 while(!toprocess.isEmpty()) {
314 FlagState gn2=(FlagState)toprocess.iterator().next();
315 toprocess.remove(gn2);
319 Iterator edges = gn2.edges();
320 while (edges.hasNext()) {
321 Edge edge = (Edge) edges.next();
322 FlagState node = edge.getTarget();
323 if (!newset.contains(node)&&nodes.contains(node))
333 /** This function returns the set of nodes involved in cycles.
334 * It only considers cycles containing nodes in the set 'nodes'.
336 public static Set findcycles(Collection nodes) {
337 HashSet cycleset=new HashSet();
338 SCC scc=DFS.computeSCC(nodes);
339 if (!scc.hasCycles())
341 for(int i=0;i<scc.numSCC();i++) {
343 cycleset.addAll(scc.getSCC(i));
348 public static class SCC {
352 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
353 this.acyclic=acyclic;
359 /** Returns whether the graph has any cycles */
360 public boolean hasCycles() {
364 /** Returns the number of Strongly Connected Components */
365 public int numSCC() {
369 /** Returns the strongly connected component number for the FlagState gn*/
370 public int getComponent(FlagState gn) {
371 return ((Integer)revmap.get(gn)).intValue();
374 /** Returns the set of nodes in the strongly connected component i*/
375 public Set getSCC(int i) {
376 Integer scc=new Integer(i);
377 return (Set)map.get(scc);
380 /** Returns whether the strongly connected component i contains a cycle */
381 boolean hasCycle(int i) {
382 Integer scc=new Integer(i);
383 Set s=(Set)map.get(scc);
386 Object [] array=s.toArray();
387 FlagState gn=(FlagState)array[0];
388 for(Iterator it=gn.edges();it.hasNext();) {
389 Edge e=(Edge)it.next();
390 if (e.getTarget()==gn)
391 return true; /* Self Cycle */
398 * DFS encapsulates the depth first search algorithm
400 public static class DFS {
405 Vector finishingorder=null;
409 private DFS(Collection nodes) {
412 /** Calculates the strong connected components for the graph composed
413 * of the set of nodes 'nodes'*/
414 public static SCC computeSCC(Collection nodes) {
416 throw new NullPointerException();
418 DFS dfs=new DFS(nodes);
419 dfs.sccmap=new HashMap();
420 dfs.sccmaprev=new HashMap();
421 dfs.finishingorder=new Vector();
422 boolean acyclic=dfs.go();
423 for (Iterator it = nodes.iterator();it.hasNext();) {
424 FlagState gn = (FlagState) it.next();
427 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
428 FlagState gn=(FlagState)dfs.finishingorder.get(i);
429 if (gn.getStatus() == UNVISITED) {
431 dfs.sccindex++; /* Increment scc index */
434 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
437 void dfsprev(FlagState gn) {
438 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
440 gn.setStatus(FINISHED);
441 Integer i=new Integer(sccindex);
442 if (!sccmap.containsKey(i))
443 sccmap.put(i,new HashSet());
444 ((Set)sccmap.get(i)).add(gn);
446 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
447 Edge e=(Edge)edgeit.next();
448 FlagState gn2=e.getSource();
453 public static boolean depthFirstSearch(Collection nodes) {
455 throw new NullPointerException();
458 DFS dfs = new DFS(nodes);
462 private boolean go() {
465 boolean acyclic=true;
466 i = nodes.iterator();
467 while (i.hasNext()) {
468 FlagState gn = (FlagState) i.next();
472 i = nodes.iterator();
473 while (i.hasNext()) {
474 FlagState gn = (FlagState) i.next();
475 assert gn.getStatus() != PROCESSING;
476 if (gn.getStatus() == UNVISITED) {
484 private boolean dfs(FlagState gn) {
485 boolean acyclic=true;
487 Iterator edges = gn.edges();
489 while (edges.hasNext()) {
490 Edge edge = (Edge) edges.next();
491 FlagState node = edge.getTarget();
492 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
494 if (node.getStatus() == UNVISITED) {
497 } else if (node.getStatus()==PROCESSING) {
501 if (finishingorder!=null)
502 finishingorder.add(gn);