1 salcianu 1.1.2.1 // AbstrRelation.java, created Thu Jun 29 19:13:12 2000 by salcianu
2 cananian 1.1.2.5 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Util.DataStructs;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import java.util.Collection;
7 salcianu 1.1.2.1 import java.util.Iterator;
8 salcianu 1.1.2.1 import java.util.LinkedList;
9 salcianu 1.1.2.1 import java.util.Vector;
10 salcianu 1.1.2.1 import java.util.HashSet;
11 salcianu 1.1.2.1 import java.util.Set;
12 salcianu 1.3 import java.util.Map;
13 salcianu 1.1.2.1
14 salcianu 1.1.2.1 import harpoon.Util.PredicateWrapper;
15 salcianu 1.1.2.1 import harpoon.Analysis.PointerAnalysis.Debug;
16 salcianu 1.1.2.1
17 salcianu 1.1.2.1 /**
18 salcianu 1.1.2.1 * <code>AbstrRelation</code>
19 salcianu 1.1.2.1 *
20 cananian 1.1.2.5 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
21 salcianu 1.4 * @version $Id: AbstrRelation.java,v 1.4 2003/06/04 16:06:31 salcianu Exp $
22 salcianu 1.1.2.1 */
23 salcianu 1.1.2.1 public abstract class AbstrRelation implements Relation, Cloneable,
24 salcianu 1.1.2.1 java.io.Serializable {
25 salcianu 1.1.2.1
26 salcianu 1.1.2.2 /** Optimizes the .hashCode() method by caching the hash code.
27 salcianu 1.1.2.2 The cached value is invalidated after each update. */
28 salcianu 1.1.2.2 public static final boolean OPTIMIZE_HASH_CODE = true;
29 salcianu 1.1.2.2
30 salcianu 1.1.2.1 protected Relation getEmptyRelation() {
31 salcianu 1.1.2.1 throw new UnsupportedOperationException();
32 salcianu 1.1.2.1 }
33 salcianu 1.1.2.1
34 salcianu 1.1.2.1
35 salcianu 1.1.2.1 public boolean add(Object key, Object value) {
36 salcianu 1.1.2.1 throw new UnsupportedOperationException();
37 salcianu 1.1.2.1 }
38 salcianu 1.1.2.1
39 salcianu 1.1.2.1 // functional but inefficient implementation
40 salcianu 1.1.2.1 public boolean addAll(Object key, Collection values) {
41 salcianu 1.1.2.1 hashCode = 0;
42 salcianu 1.1.2.1 boolean retval = false;
43 salcianu 1.1.2.1 for(Iterator it = values.iterator(); it.hasNext(); )
44 salcianu 1.1.2.1 if(add(key, it.next()))
45 salcianu 1.1.2.1 retval = true;
46 salcianu 1.1.2.1 return retval;
47 salcianu 1.1.2.1 }
48 salcianu 1.1.2.1
49 salcianu 1.1.2.1
50 salcianu 1.1.2.1 public void remove(Object key, Object value) {
51 salcianu 1.1.2.3 Set vals = getValues2(key);
52 salcianu 1.1.2.1 if(vals == null) return;
53 salcianu 1.1.2.1
54 salcianu 1.1.2.1 hashCode = 0;
55 salcianu 1.1.2.1 vals.remove(value);
56 salcianu 1.1.2.1 if(vals.isEmpty())
57 salcianu 1.1.2.1 removeKey(key);
58 salcianu 1.1.2.4 }
59 salcianu 1.1.2.4
60 salcianu 1.3 public Relation revert(final Relation result) {
61 salcianu 1.1.2.4 forAllEntries(new RelationEntryVisitor() {
62 salcianu 1.1.2.4 public void visit(Object key, Object value) {
63 salcianu 1.1.2.4 result.add(value, key);
64 salcianu 1.1.2.4 }
65 salcianu 1.1.2.4 });
66 salcianu 1.3 return result;
67 salcianu 1.1.2.3 }
68 salcianu 1.1.2.3
69 salcianu 1.1.2.3
70 salcianu 1.1.2.3 protected Set getValues2(Object key) {
71 salcianu 1.1.2.3 throw new UnsupportedOperationException();
72 salcianu 1.1.2.1 }
73 salcianu 1.1.2.1
74 salcianu 1.1.2.1
75 salcianu 1.1.2.1 // functional but inefficient implementation
76 salcianu 1.1.2.1 public void removeAll(Object key, Collection values) {
77 salcianu 1.1.2.1 for(Iterator it = values.iterator(); it.hasNext(); )
78 salcianu 1.1.2.1 remove(key, it.next());
79 salcianu 1.1.2.1 }
80 salcianu 1.1.2.1
81 salcianu 1.1.2.1
82 salcianu 1.1.2.1 public void removeKey(Object key) {
83 salcianu 1.1.2.1 throw new UnsupportedOperationException();
84 salcianu 1.1.2.1 }
85 salcianu 1.1.2.1
86 salcianu 1.1.2.1
87 salcianu 1.1.2.1 public void removeKeys(PredicateWrapper predicate) {
88 salcianu 1.1.2.1 hashCode = 0;
89 salcianu 1.1.2.1 // 1. put all the keys that satisfy predicate in keysToRemove
90 salcianu 1.1.2.1 Collection keysToRemove = new Vector();
91 salcianu 1.1.2.1 for(Iterator it = keys().iterator(); it.hasNext(); ) {
92 salcianu 1.1.2.1 Object key = it.next();
93 salcianu 1.1.2.1 if(predicate.check(key))
94 salcianu 1.1.2.1 keysToRemove.add(key);
95 salcianu 1.1.2.1 }
96 salcianu 1.1.2.1 // 2. actually do the removal
97 salcianu 1.1.2.1 for(Iterator it = keysToRemove.iterator(); it.hasNext(); )
98 salcianu 1.1.2.1 removeKey(it.next());
99 salcianu 1.1.2.1 }
100 salcianu 1.1.2.1
101 salcianu 1.1.2.1
102 salcianu 1.1.2.1 public void removeValues(PredicateWrapper predicate) {
103 salcianu 1.1.2.1 hashCode = 0;
104 salcianu 1.1.2.1
105 salcianu 1.1.2.1 Collection keysToRemove = new Vector();
106 salcianu 1.1.2.1 for(Iterator itk = keys().iterator(); itk.hasNext(); ) {
107 salcianu 1.1.2.1 Object key = itk.next();
108 salcianu 1.1.2.1 Set vals = getValues(key);
109 salcianu 1.1.2.1 for(Iterator itv = vals.iterator(); itv.hasNext(); ) {
110 salcianu 1.1.2.1 Object value = itv.next();
111 salcianu 1.1.2.1 if(predicate.check(value))
112 salcianu 1.1.2.1 itv.remove();
113 salcianu 1.1.2.1 }
114 salcianu 1.1.2.1 if(vals.isEmpty())
115 salcianu 1.1.2.1 keysToRemove.add(key);
116 salcianu 1.1.2.1 }
117 salcianu 1.1.2.1
118 salcianu 1.1.2.1 for(Iterator itk = keysToRemove.iterator(); itk.hasNext(); )
119 salcianu 1.1.2.1 removeKey(itk.next());
120 salcianu 1.1.2.1 }
121 salcianu 1.1.2.1
122 salcianu 1.1.2.1
123 salcianu 1.1.2.1 public void removeObjects(PredicateWrapper predicate) {
124 salcianu 1.1.2.1 removeKeys(predicate);
125 salcianu 1.1.2.1 removeValues(predicate);
126 salcianu 1.1.2.1 }
127 salcianu 1.1.2.1
128 salcianu 1.1.2.1
129 salcianu 1.1.2.1 public boolean contains(Object key, Object value) {
130 salcianu 1.1.2.1 Set vals = getValues(key);
131 salcianu 1.1.2.1 return (vals != null) && vals.contains(value);
132 salcianu 1.1.2.1 }
133 salcianu 1.1.2.1
134 salcianu 1.1.2.1
135 salcianu 1.1.2.1 public boolean containsKey(Object key) {
136 salcianu 1.1.2.1 Set vals = getValues(key);
137 salcianu 1.1.2.1 return (vals != null) && !vals.isEmpty();
138 salcianu 1.1.2.1 }
139 salcianu 1.1.2.1
140 salcianu 1.1.2.1
141 salcianu 1.1.2.1 public boolean isEmpty() {
142 salcianu 1.1.2.1 return keys().isEmpty();
143 salcianu 1.1.2.1 }
144 salcianu 1.1.2.1
145 salcianu 1.1.2.1
146 salcianu 1.1.2.1 public Set getValues(Object key) {
147 salcianu 1.1.2.1 throw new UnsupportedOperationException();
148 salcianu 1.1.2.1 }
149 salcianu 1.1.2.1
150 salcianu 1.1.2.1
151 salcianu 1.1.2.1 public Set keys() {
152 salcianu 1.1.2.1 throw new UnsupportedOperationException();
153 salcianu 1.1.2.1 }
154 salcianu 1.1.2.1
155 salcianu 1.1.2.1
156 salcianu 1.1.2.1 public Set values() {
157 salcianu 1.1.2.1 Set vals = new HashSet();
158 salcianu 1.1.2.1 for(Iterator it = keys().iterator(); it.hasNext(); )
159 salcianu 1.1.2.1 vals.addAll(getValues(it.next()));
160 salcianu 1.1.2.1 return vals;
161 salcianu 1.1.2.1 }
162 salcianu 1.1.2.1
163 salcianu 1.1.2.1
164 salcianu 1.4 public boolean union(Relation rel) {
165 salcianu 1.4 boolean changed = false;
166 salcianu 1.1.2.1 for(Iterator itk = rel.keys().iterator(); itk.hasNext(); ) {
167 salcianu 1.1.2.1 Object key = itk.next();
168 salcianu 1.4 if(addAll(key, rel.getValues(key)))
169 salcianu 1.4 changed = true;
170 salcianu 1.1.2.1 }
171 salcianu 1.4 return changed;
172 salcianu 1.1.2.1 }
173 salcianu 1.1.2.1
174 salcianu 1.1.2.1
175 salcianu 1.1.2.1 public boolean equals(Object o) {
176 salcianu 1.1.2.2 if((o == null) || !(o instanceof Relation))
177 salcianu 1.1.2.1 return false;
178 salcianu 1.1.2.1 Relation rel2 = (Relation) o;
179 salcianu 1.1.2.1
180 salcianu 1.1.2.1 Set ks = keys();
181 salcianu 1.1.2.1 Set ks2 = rel2.keys();
182 salcianu 1.1.2.1
183 salcianu 1.1.2.2 if(!equal_sets(ks, ks2))
184 salcianu 1.1.2.1 return false;
185 salcianu 1.1.2.1
186 salcianu 1.1.2.1 for(Iterator it = ks.iterator(); it.hasNext(); ){
187 salcianu 1.1.2.1 Object key = it.next();
188 salcianu 1.1.2.1 Set vs = getValues(key);
189 salcianu 1.1.2.1 Set vs2 = rel2.getValues(key);
190 salcianu 1.1.2.2 if(!equal_sets(vs, vs2))
191 salcianu 1.1.2.1 return false;
192 salcianu 1.1.2.1 }
193 salcianu 1.1.2.1
194 salcianu 1.1.2.1 return true;
195 salcianu 1.1.2.1 }
196 salcianu 1.1.2.1
197 salcianu 1.1.2.1
198 salcianu 1.1.2.1 public int hashCode() {
199 salcianu 1.1.2.2 if((hashCode == 0) || !OPTIMIZE_HASH_CODE) {
200 salcianu 1.1.2.2 hashCode = 0;
201 salcianu 1.1.2.1 for(Iterator itk = keys().iterator(); itk.hasNext(); ) {
202 salcianu 1.1.2.1 Object key = itk.next();
203 salcianu 1.1.2.1 hashCode += key.hashCode();
204 salcianu 1.1.2.1 for(Iterator itv = getValues(key).iterator(); itv.hasNext(); ){
205 salcianu 1.1.2.1 Object value = itv.next();
206 salcianu 1.1.2.1 hashCode += value.hashCode();
207 salcianu 1.1.2.1 }
208 salcianu 1.1.2.1 }
209 salcianu 1.1.2.2 }
210 salcianu 1.1.2.1 return hashCode;
211 salcianu 1.1.2.1 }
212 salcianu 1.1.2.1 protected int hashCode = 0;
213 salcianu 1.1.2.1
214 salcianu 1.1.2.1
215 salcianu 1.1.2.1 // Test whether c1 and c2 contain the same elements.
216 salcianu 1.1.2.1 // Precondition: c1 and c2 don't contain duplicates.
217 salcianu 1.1.2.1 // So, we can say that c1 and c2 are equal if they have the same number
218 salcianu 1.1.2.1 // of elements and each element of c1 is also in c2.
219 salcianu 1.1.2.1 private boolean equal_sets(Collection c1, Collection c2) {
220 salcianu 1.1.2.1 if((c1 == null) || (c2 == null))
221 salcianu 1.1.2.1 return c1 == c2;
222 salcianu 1.1.2.1
223 salcianu 1.1.2.2 if(c1.size() != c2.size())
224 salcianu 1.1.2.1 return false;
225 salcianu 1.1.2.1
226 salcianu 1.1.2.1 for(Iterator it = c1.iterator(); it.hasNext(); ) {
227 salcianu 1.1.2.1 Object obj = it.next();
228 salcianu 1.1.2.2 if(!c2.contains(obj))
229 salcianu 1.1.2.1 return false;
230 salcianu 1.1.2.1 }
231 salcianu 1.1.2.1
232 salcianu 1.1.2.1 return true;
233 salcianu 1.1.2.1 }
234 salcianu 1.1.2.1
235 salcianu 1.1.2.1
236 salcianu 1.1.2.1 public Relation select(Collection selected_keys) {
237 salcianu 1.1.2.1 Relation retval = getEmptyRelation();
238 salcianu 1.1.2.1
239 salcianu 1.1.2.1 for(Iterator it = selected_keys.iterator(); it.hasNext(); ) {
240 salcianu 1.1.2.1 Object key = it.next();
241 salcianu 1.1.2.1 retval.addAll(key, getValues(key));
242 salcianu 1.1.2.1 }
243 salcianu 1.1.2.1
244 salcianu 1.1.2.1 return retval;
245 salcianu 1.1.2.1 }
246 salcianu 1.1.2.1
247 salcianu 1.1.2.1
248 salcianu 1.1.2.1 public void forAllEntries(RelationEntryVisitor visitor) {
249 salcianu 1.1.2.1 for(Iterator itk = keys().iterator(); itk.hasNext(); ) {
250 salcianu 1.1.2.1 Object key = itk.next();
251 salcianu 1.1.2.1 for(Iterator itv = getValues(key).iterator(); itv.hasNext(); )
252 salcianu 1.1.2.1 visitor.visit(key, itv.next());
253 salcianu 1.1.2.1 }
254 salcianu 1.1.2.1 }
255 salcianu 1.1.2.1
256 salcianu 1.1.2.1
257 salcianu 1.1.2.1 public String toString() {
258 salcianu 1.1.2.1 StringBuffer buffer = new StringBuffer();
259 salcianu 1.1.2.1
260 salcianu 1.1.2.1 buffer.append("{");
261 salcianu 1.1.2.1
262 salcianu 1.1.2.1 Object[] ks = Debug.sortedCollection(keys());
263 salcianu 1.1.2.1 for(int i = 0 ; i < ks.length ; i++ ){
264 salcianu 1.1.2.1 Object key = ks[i];
265 salcianu 1.1.2.1 buffer.append("\n ");
266 salcianu 1.1.2.1 buffer.append(key);
267 salcianu 1.1.2.1 buffer.append(" -> ");
268 salcianu 1.1.2.1 buffer.append(Debug.stringImg(getValues(key)));
269 salcianu 1.1.2.1 }
270 salcianu 1.1.2.1
271 salcianu 1.1.2.1 buffer.append("\n }\n");
272 salcianu 1.1.2.1
273 salcianu 1.1.2.1 return buffer.toString();
274 salcianu 1.1.2.1 }
275 salcianu 1.1.2.1
276 salcianu 1.1.2.1
277 salcianu 1.1.2.1 public Object clone() {
278 salcianu 1.1.2.1 try{
279 salcianu 1.1.2.1 return super.clone();
280 salcianu 1.1.2.1 } catch(CloneNotSupportedException e) {
281 salcianu 1.1.2.1 throw new InternalError();
282 salcianu 1.1.2.1 }
283 salcianu 1.3 }
284 salcianu 1.3
285 salcianu 1.3 public Relation convert(final Map map, final Relation result) {
286 salcianu 1.3 forAllEntries(new RelationEntryVisitor() {
287 salcianu 1.3 public void visit(Object key, Object value) {
288 salcianu 1.3 Object keyp = map.get(key);
289 salcianu 1.3 if(keyp == null) keyp = key;
290 salcianu 1.3 Object valuep = map.get(value);
291 salcianu 1.3 if(valuep == null) valuep = value;
292 salcianu 1.3 result.add(keyp, valuep);
293 salcianu 1.3 }
294 salcianu 1.3 });
295 salcianu 1.3 return result;
296 salcianu 1.1.2.1 }
297 salcianu 1.1.2.1
298 cananian 1.2 }