|
1
19
20
25
26
27 package soot.jimple.toolkits.typing.integer;
28
29 import soot.*;
30 import soot.jimple.*;
31 import soot.util.*;
32 import java.util.*;
33
34 class StronglyConnectedComponents
35 {
36 List variables;
37 Set black;
38 LinkedList finished;
39
40 LinkedList forest = new LinkedList();
41 LinkedList current_tree;
42
43 private static final boolean DEBUG = false;
44
45 public static void merge(List typeVariableList) throws TypeException
46 {
47 new StronglyConnectedComponents(typeVariableList);
48 }
49
50 private StronglyConnectedComponents(List typeVariableList) throws TypeException
51 {
52 variables = typeVariableList;
53
54 black = new TreeSet();
55 finished = new LinkedList();
56
57 for(Iterator i = variables.iterator(); i.hasNext(); )
58 {
59 TypeVariable var = (TypeVariable) i.next();
60
61 if(!black.contains(var))
62 {
63 black.add(var);
64 dfsg_visit(var);
65 }
66 }
67
68 black = new TreeSet();
69
70 for(Iterator i = finished.iterator(); i.hasNext(); )
71 {
72 TypeVariable var = (TypeVariable) i.next();
73
74 if(!black.contains(var))
75 {
76 current_tree = new LinkedList();
77 forest.add(current_tree);
78 black.add(var);
79 dfsgt_visit(var);
80 }
81 }
82
83 for(Iterator i = forest.iterator(); i.hasNext();)
84 {
85 LinkedList list = (LinkedList) i.next();
86 TypeVariable previous = null;
87 StringBuffer  s = null;
88 if(DEBUG)
89 {
90 s = new StringBuffer ("scc:\n");
91 }
92
93 for(Iterator j = list.iterator(); j.hasNext();)
94 {
95 TypeVariable current = (TypeVariable) j.next();
96
97 if(DEBUG)
98 {
99 s.append(" " + current + "\n");
100 }
101
102 if(previous == null)
103 {
104 previous = current;
105 }
106 else
107 {
108 try
109 {
110 previous = previous.union(current);
111 }
112 catch(TypeException e)
113 {
114 if(DEBUG)
115 {
116 G.v().out.println(s);
117 }
118 throw e;
119 }
120 }
121 }
122 }
123 }
124
125 private void dfsg_visit(TypeVariable var)
126 {
127 List parents = var.parents();
128
129 for(Iterator i = parents.iterator(); i.hasNext(); )
130 {
131 TypeVariable parent = (TypeVariable) i.next();
132
133 if(!black.contains(parent))
134 {
135 black.add(parent);
136 dfsg_visit(parent);
137 }
138 }
139
140 finished.add(0, var);
141 }
142
143 private void dfsgt_visit(TypeVariable var)
144 {
145 current_tree.add(var);
146
147 List children = var.children();
148
149 for(Iterator i = children.iterator(); i.hasNext(); )
150 {
151 TypeVariable child = (TypeVariable) i.next();
152
153 if(!black.contains(child))
154 {
155 black.add(child);
156 dfsgt_visit(child);
157 }
158 }
159 }
160 }
161 |
Popular Tags |
Java API By Example, From Geeks To Geeks.