1 ovy 1.1 /*
2 ovy 1.1 Some utilities for MultiMaps
3 ovy 1.1 */
4 ovy 1.1
5 ovy 1.1 package harpoon.Analysis.MemOpt;
6 ovy 1.1
7 cananian 1.2 import harpoon.Analysis.GraphColoring.Color;
8 cananian 1.2 import harpoon.Analysis.GraphColoring.ColorFactory;
9 cananian 1.2 import harpoon.Analysis.GraphColoring.DefaultSparseNode;
10 cananian 1.2 import harpoon.Analysis.GraphColoring.SimpleGraphColorer;
11 cananian 1.2 import harpoon.Analysis.GraphColoring.SparseGraph;
12 cananian 1.2 import harpoon.Analysis.GraphColoring.SparseNode;
13 cananian 1.2 import harpoon.Analysis.GraphColoring.UnboundedGraphColorer;
14 cananian 1.3 import net.cscott.jutil.AggregateSetFactory;
15 cananian 1.3 import net.cscott.jutil.GenericMultiMap;
16 cananian 1.3 import net.cscott.jutil.MultiMap;
17 cananian 1.3 import net.cscott.jutil.WorkSet;
18 cananian 1.2 import java.util.ArrayList;
19 cananian 1.2 import java.util.Collection;
20 cananian 1.2 import java.util.Comparator;
21 cananian 1.2 import java.util.HashMap;
22 cananian 1.2 import java.util.HashSet;
23 cananian 1.2 import java.util.Iterator;
24 cananian 1.2 import java.util.LinkedList;
25 cananian 1.2 import java.util.List;
26 cananian 1.2 import java.util.Map;
27 cananian 1.2 import java.util.Set;
28 ovy 1.1
29 ovy 1.1 public final class MultiMapUtils {
30 ovy 1.1 /*
31 ovy 1.1 "Closes" the given multi-map, i.e. makes it transitive.
32 ovy 1.1 only nodes accessible from startingNodes are processed.
33 ovy 1.1 Time: O(N*M)
34 ovy 1.1 N: number of nodes in startingNodes
35 ovy 1.1 M: number of edges accessible from startingNodes
36 ovy 1.1
37 ovy 1.1 Only uses iterator from startingNodes, i.e. other ops can be slow
38 ovy 1.1
39 ovy 1.1 UPDATE: now forbids closures over dontCloseOver. I *really* need this
40 ovy 1.1 capability. dontCloseOver can be null, and it'll be ignored.
41 ovy 1.1 For sane results, dontCloseOver should be a subset of startingNodes.
42 ovy 1.1
43 ovy 1.1 FIXME: I have to make this specification clearer.
44 ovy 1.1 */
45 ovy 1.1 static MultiMap multiMapClosure(MultiMap oldMap, Collection startingNodes,
46 ovy 1.1 Set dontCloseOver) {
47 ovy 1.1 MultiMap map = new GenericMultiMap(new AggregateSetFactory());
48 ovy 1.1
49 ovy 1.1 Set reachable = new HashSet();
50 ovy 1.1 WorkSet workset = new WorkSet();
51 ovy 1.1
52 ovy 1.1 for (Iterator i = startingNodes.iterator(); i.hasNext(); ) {
53 ovy 1.1 Object x = i.next();
54 ovy 1.1
55 ovy 1.1 reachable.clear();
56 ovy 1.1
57 ovy 1.1 workset.add(x);
58 ovy 1.1
59 ovy 1.1 while (!workset.isEmpty()) {
60 ovy 1.1 Object y = workset.removeFirst();
61 ovy 1.1
62 ovy 1.1 if (dontCloseOver != null && y!= x &&
63 ovy 1.1 dontCloseOver.contains(y)) continue;
64 ovy 1.1
65 ovy 1.1 for (Iterator j = oldMap.getValues(y).iterator();
66 ovy 1.1 j.hasNext(); ) {
67 ovy 1.1 Object z = j.next();
68 ovy 1.1
69 ovy 1.1 if (reachable.add(z) && z!=x) {
70 ovy 1.1 workset.addLast(z);
71 ovy 1.1 }
72 ovy 1.1 }
73 ovy 1.1
74 ovy 1.1 }
75 ovy 1.1 map.addAll(x, reachable);
76 ovy 1.1 }
77 ovy 1.1
78 ovy 1.1 return map;
79 ovy 1.1 }
80 ovy 1.1
81 ovy 1.1
82 ovy 1.1 // compute map inverse, as per relevantNodes (i.e, only relevantNodes
83 ovy 1.1 // will appear on the right hand side
84 ovy 1.1 // Only uses iterator from relevantNodes, i.e. other ops can be slow
85 ovy 1.1 // Relevantnodes can be null to invert the whole map
86 ovy 1.1 static MultiMap multiMapInvert(MultiMap oldMap, Collection relevantNodes) {
87 ovy 1.1 MultiMap map = new GenericMultiMap(new AggregateSetFactory());
88 ovy 1.1
89 ovy 1.1 if (relevantNodes == null) relevantNodes = new ArrayList(oldMap.keySet());
90 ovy 1.1
91 ovy 1.1 for (Iterator i = relevantNodes.iterator(); i.hasNext(); ) {
92 ovy 1.1 Object x = i.next();
93 ovy 1.1
94 ovy 1.1 for (Iterator j = oldMap.getValues(x).iterator(); j.hasNext(); ) {
95 ovy 1.1 Object y = j.next();
96 ovy 1.1 map.add(y, x);
97 ovy 1.1
98 ovy 1.1 }
99 ovy 1.1 }
100 ovy 1.1
101 ovy 1.1 return map;
102 ovy 1.1 }
103 ovy 1.1
104 ovy 1.1 // computes the union of the mappings of the elements in the collection
105 ovy 1.1 // Only uses iterator from keys, i.e. other ops can be slow
106 ovy 1.1 static Set multiMapUnion(MultiMap map, Collection keys) {
107 ovy 1.1 Set union = new HashSet();
108 ovy 1.1
109 ovy 1.1 for (Iterator i = keys.iterator(); i.hasNext(); ) {
110 ovy 1.1 Object x = i.next();
111 ovy 1.1 union.addAll(map.getValues(x));
112 ovy 1.1 }
113 ovy 1.1
114 ovy 1.1 return union;
115 ovy 1.1 }
116 ovy 1.1
117 ovy 1.1 // filters the given multimap through the given key and value sets
118 ovy 1.1 // only mappings with key in relevantKeys and values in relValues
119 ovy 1.1 // are kept
120 ovy 1.1 // one or both of relKeys and relValues can be null, in which case they
121 ovy 1.1 // will be ignored. also, they can be equal
122 ovy 1.1 // this uses the contains operations of both collections, which should
123 ovy 1.1 // therefore be fast
124 ovy 1.1 static MultiMap multiMapFilter(MultiMap oldMap, Collection relevantKeys, Collection relevantValues) {
125 ovy 1.1 MultiMap newMap = new GenericMultiMap(new AggregateSetFactory());
126 ovy 1.1
127 ovy 1.1 for (Iterator it = oldMap.keySet().iterator(); it.hasNext(); ) {
128 ovy 1.1 Object key = it.next();
129 ovy 1.1
130 ovy 1.1 // add this key?
131 ovy 1.1 if (relevantKeys == null ||
132 ovy 1.1 relevantKeys.contains(key)) {
133 ovy 1.1
134 cananian 1.4 for (Object value : oldMap.getValues(key)) {
135 ovy 1.1 if (relevantValues == null ||
136 ovy 1.1 relevantValues.contains(value)) {
137 ovy 1.1 newMap.add(key, value);
138 ovy 1.1 }
139 ovy 1.1 }
140 ovy 1.1 }
141 ovy 1.1 }
142 ovy 1.1
143 ovy 1.1 return newMap;
144 ovy 1.1 }
145 ovy 1.1
146 ovy 1.1 // similar to the above, but filters only keys
147 ovy 1.1 // optimized on the assumption that:
148 ovy 1.1 // relevantKeys is a small subset of oldMap.keySet()
149 ovy 1.1 // uses only the iterator in relevantKeys(), i.e. other ops can be slow
150 ovy 1.1 static MultiMap multiMapFilterKeys(MultiMap oldMap, Collection relevantKeys) {
151 ovy 1.1 MultiMap newMap = new GenericMultiMap(new AggregateSetFactory());
152 ovy 1.1
153 ovy 1.1 for (Iterator it = relevantKeys.iterator(); it.hasNext(); ) {
154 ovy 1.1 Object key = it.next();
155 ovy 1.1 newMap.addAll(key, oldMap.getValues(key));
156 ovy 1.1 }
157 ovy 1.1
158 ovy 1.1 return newMap;
159 ovy 1.1 }
160 ovy 1.1
161 ovy 1.1 // add a value for all the specified keys
162 ovy 1.1 static void multiMapAddAll(MultiMap map, Collection keys, Object value) {
163 ovy 1.1 for (Iterator it = keys.iterator(); it.hasNext(); ) {
164 ovy 1.1 Object key = it.next();
165 ovy 1.1 map.add(key, value);
166 ovy 1.1 }
167 ovy 1.1 }
168 ovy 1.1
169 ovy 1.1 // this does not really belong here...
170 ovy 1.1 // optimized on the assumption that:
171 ovy 1.1 // - b is a large collection with a fast contains() operation
172 ovy 1.1 // - a is a rather small collection (does not have to have a fast contains()
173 ovy 1.1
174 ovy 1.1 static Set intersect(Collection a, Collection b) {
175 ovy 1.1 Set intersection = new HashSet();
176 ovy 1.1
177 ovy 1.1 for (Iterator i = a.iterator(); i.hasNext(); ) {
178 ovy 1.1 Object x = i.next();
179 ovy 1.1 if (b.contains(x)) {
180 ovy 1.1 intersection.add(x);
181 ovy 1.1 }
182 ovy 1.1 }
183 ovy 1.1
184 ovy 1.1 return intersection;
185 ovy 1.1 }
186 ovy 1.1
187 ovy 1.1 static void ensureSymmetric(MultiMap map) {
188 ovy 1.1 List keyList = new ArrayList(map.keySet());
189 ovy 1.1
190 ovy 1.1 for (Iterator it = keyList.iterator(); it.hasNext(); ) {
191 ovy 1.1 Object key = it.next();
192 ovy 1.1
193 ovy 1.1 multiMapAddAll(map, map.getValues(key), key);
194 ovy 1.1 }
195 ovy 1.1 }
196 ovy 1.1
197 ovy 1.1 // this does not belong here and WILL be deleted
198 ovy 1.1 // new and better code is in MyGraphColorer
199 ovy 1.1 // keeping it around just in case for a few more days
200 ovy 1.1 static Collection computeCompatibleClasses(final MultiMap incompatible) {
201 ovy 1.1
202 ovy 1.1 // decreasing order of incompatibilites
203 ovy 1.1 Comparator myComparator = new Comparator() {
204 ovy 1.1 public int compare(Object a, Object b) {
205 ovy 1.1 int sizeA = incompatible.getValues(a).size();
206 ovy 1.1 int sizeB = incompatible.getValues(b).size();
207 ovy 1.1
208 ovy 1.1 return sizeB - sizeA;
209 ovy 1.1 }
210 ovy 1.1
211 ovy 1.1 };
212 ovy 1.1
213 ovy 1.1
214 ovy 1.1 Object[] nodes = incompatible.keySet().toArray();
215 ovy 1.1
216 ovy 1.1 // sort on decreasing order of #incompatible
217 ovy 1.1 // Arrays.sort(nodes, myComparator);
218 ovy 1.1
219 ovy 1.1 Collection classes = new LinkedList();
220 ovy 1.1
221 ovy 1.1 for (int i = 0; i < nodes.length; i++) {
222 ovy 1.1 Object candidate = nodes[i];
223 ovy 1.1
224 ovy 1.1 boolean assigned = false;
225 ovy 1.1
226 ovy 1.1 for (Iterator it = classes.iterator(); it.hasNext() && !assigned; ) {
227 ovy 1.1 Collection members = (Collection) it.next();
228 ovy 1.1 boolean compatible = true;
229 ovy 1.1 for (Iterator it2 = members.iterator(); it2.hasNext() && compatible; ) {
230 ovy 1.1 Object member = it2.next();
231 ovy 1.1
232 ovy 1.1 compatible &= !incompatible.contains(candidate, member);
233 ovy 1.1 }
234 ovy 1.1
235 ovy 1.1 if (compatible) {
236 ovy 1.1 members.add(candidate);
237 ovy 1.1 assigned = true;
238 ovy 1.1 }
239 ovy 1.1 }
240 ovy 1.1
241 ovy 1.1 if (!assigned) {
242 ovy 1.1 Collection newClass = new LinkedList();
243 ovy 1.1 newClass.add(candidate);
244 ovy 1.1
245 ovy 1.1 classes.add(newClass);
246 ovy 1.1 }
247 ovy 1.1 }
248 ovy 1.1
249 ovy 1.1 return classes;
250 ovy 1.1 }
251 ovy 1.1
252 ovy 1.1 // alternate algorithm for above using Felix's UnboundedGraphColoring
253 ovy 1.1 // this will be deleted too, since that alg performs very poorly
254 ovy 1.1 // currently does not return anything, just prints a result for comparison
255 ovy 1.1 static Collection computeCompatibleClassesAlt(final MultiMap incompatible) {
256 ovy 1.1 Map tokens2nodes = new HashMap();
257 ovy 1.1 SparseGraph graph = new SparseGraph();
258 ovy 1.1
259 ovy 1.1 // nodes
260 ovy 1.1 for (Iterator it = incompatible.keySet().iterator(); it.hasNext(); ) {
261 ovy 1.1 Object token = it.next();
262 ovy 1.1 SparseNode node = new DefaultSparseNode();
263 ovy 1.1 tokens2nodes.put(token, node);
264 ovy 1.1 graph.addNode(node);
265 ovy 1.1 }
266 ovy 1.1
267 ovy 1.1 // edges
268 ovy 1.1 for (Iterator it = incompatible.keySet().iterator(); it.hasNext(); ) {
269 ovy 1.1 Object token1 = it.next();
270 ovy 1.1 SparseNode node1 = (SparseNode) tokens2nodes.get(token1);
271 ovy 1.1 for (Iterator it2 = incompatible.getValues(token1).iterator();
272 ovy 1.1 it2.hasNext(); ) {
273 ovy 1.1 Object token2 = it2.next();
274 ovy 1.1 SparseNode node2 = (SparseNode) tokens2nodes.get(token2);
275 ovy 1.1 graph.makeEdge(node1, node2);
276 ovy 1.1 }
277 ovy 1.1 }
278 ovy 1.1
279 ovy 1.1 ColorFactory cfactory = new ColorFactory() {
280 ovy 1.1 protected Color newColor() {
281 ovy 1.1 return new Color() {
282 ovy 1.1 };
283 ovy 1.1 }
284 ovy 1.1 };
285 ovy 1.1
286 ovy 1.1 UnboundedGraphColorer colorer =
287 ovy 1.1 new UnboundedGraphColorer(new SimpleGraphColorer(),
288 ovy 1.1 cfactory);
289 ovy 1.1
290 ovy 1.1 colorer.findColoring(graph);
291 ovy 1.1
292 ovy 1.1 System.out.println("*** # classes via alt method: "
293 ovy 1.1 + cfactory.getColors().size());
294 ovy 1.1
295 ovy 1.1 return null;
296 ovy 1.1 }
297 ovy 1.1
298 ovy 1.1 }