1 salcianu 1.1.2.1 // RelationImpl.java, created Tue Jan 11 14:52:48 2000 by salcianu
2 cananian 1.1.2.3 // 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.Hashtable;
7 salcianu 1.1.2.1 import java.util.Collections;
8 salcianu 1.1.2.1 import java.util.HashSet;
9 salcianu 1.1.2.1 import java.util.Set;
10 salcianu 1.1.2.1 import java.util.Iterator;
11 salcianu 1.1.2.1 import java.util.Map;
12 salcianu 1.1.2.1 import java.util.Collection;
13 salcianu 1.1.2.1
14 salcianu 1.1.2.1 import java.util.Arrays;
15 salcianu 1.1.2.1
16 salcianu 1.1.2.1 import harpoon.Util.Util;
17 salcianu 1.1.2.1 import harpoon.Analysis.PointerAnalysis.Debug;
18 salcianu 1.1.2.1 import harpoon.Util.PredicateWrapper;
19 salcianu 1.1.2.1
20 salcianu 1.1.2.1 /**
21 salcianu 1.1.2.1 * <code>RelationImpl</code> is a heavy-weight implementation of the
22 salcianu 1.1.2.1 * <code>Relation</code> interface: it is basically a Hashtable from keys
23 salcianu 1.1.2.1 * to HashSet's of values. It is good for very big relations but consumes
24 salcianu 1.1.2.1 * lots of memory.
25 salcianu 1.1.2.1 *
26 cananian 1.1.2.3 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
27 cananian 1.5 * @version $Id: RelationImpl.java,v 1.5 2004/02/08 03:21:50 cananian Exp $
28 salcianu 1.1.2.1 */
29 salcianu 1.1.2.1 public class RelationImpl implements Relation, java.io.Serializable {
30 salcianu 1.1.2.1
31 salcianu 1.1.2.1 /** The top-level <code>Hashtable</code>. */
32 salcianu 1.1.2.1 Hashtable hash;
33 salcianu 1.1.2.1
34 salcianu 1.1.2.1
35 salcianu 1.1.2.1 /** Creates an empty <code>Relation</code>. */
36 salcianu 1.1.2.1 public RelationImpl() {
37 salcianu 1.1.2.1 hash = new Hashtable();
38 salcianu 1.1.2.1 }
39 salcianu 1.1.2.1
40 salcianu 1.1.2.1
41 salcianu 1.1.2.1 public Relation getEmptyRelation() {
42 salcianu 1.1.2.1 return new RelationImpl();
43 salcianu 1.1.2.1 }
44 salcianu 1.1.2.1
45 salcianu 1.1.2.1
46 salcianu 1.1.2.1 public boolean add(Object key, Object value){
47 salcianu 1.1.2.1 HashSet set = (HashSet)hash.get(key);
48 salcianu 1.1.2.1 if(set==null) hash.put(key,set = new HashSet());
49 salcianu 1.1.2.1 return set.add(value);
50 salcianu 1.1.2.1 }
51 salcianu 1.1.2.1
52 salcianu 1.1.2.1
53 salcianu 1.1.2.1 public boolean addAll(Object key, Collection values) {
54 salcianu 1.1.2.1 if(values.isEmpty()) return false;
55 salcianu 1.1.2.1 HashSet set = (HashSet) hash.get(key);
56 salcianu 1.1.2.1 if(set==null)
57 salcianu 1.1.2.1 hash.put(key,set = new HashSet());
58 salcianu 1.1.2.1 return set.addAll(values);
59 salcianu 1.1.2.1 }
60 salcianu 1.1.2.1
61 salcianu 1.1.2.1 public void remove(Object key, Object value){
62 salcianu 1.1.2.1 HashSet set = (HashSet)hash.get(key);
63 salcianu 1.1.2.1 if(set==null) return;
64 salcianu 1.1.2.1 set.remove(value);
65 salcianu 1.1.2.1 if(set.isEmpty())
66 salcianu 1.1.2.1 hash.remove(key);
67 salcianu 1.1.2.1 }
68 salcianu 1.1.2.1
69 salcianu 1.1.2.1 public void removeAll(Object key, Collection values){
70 salcianu 1.1.2.1 Iterator it_values = values.iterator();
71 salcianu 1.1.2.1 while(it_values.hasNext())
72 salcianu 1.1.2.1 remove(key, it_values.next());
73 salcianu 1.1.2.1 }
74 salcianu 1.1.2.1
75 salcianu 1.1.2.1
76 salcianu 1.1.2.1 public void removeKey(Object key){
77 salcianu 1.1.2.1 hash.remove(key);
78 salcianu 1.1.2.1 }
79 salcianu 1.1.2.1
80 salcianu 1.1.2.1
81 salcianu 1.1.2.1 public void removeKeys(PredicateWrapper predicate){
82 salcianu 1.1.2.1 Set keys = hash.keySet();
83 salcianu 1.1.2.1 Iterator it_keys = keys.iterator();
84 salcianu 1.1.2.1 while(it_keys.hasNext()){
85 salcianu 1.1.2.1 Object obj = it_keys.next();
86 salcianu 1.1.2.1 if(predicate.check(obj))
87 salcianu 1.1.2.1 it_keys.remove();
88 salcianu 1.1.2.1 }
89 salcianu 1.1.2.1 }
90 salcianu 1.1.2.1
91 salcianu 1.1.2.1
92 salcianu 1.1.2.1 private boolean removeValues(Object key, PredicateWrapper predicate){
93 salcianu 1.1.2.1 Set values = (Set) hash.get(key);
94 salcianu 1.1.2.1 Iterator it_values = values.iterator();
95 salcianu 1.1.2.1 while(it_values.hasNext()){
96 salcianu 1.1.2.1 Object value = it_values.next();
97 salcianu 1.1.2.1 if(predicate.check(value))
98 salcianu 1.1.2.1 it_values.remove();
99 salcianu 1.1.2.1 }
100 salcianu 1.1.2.1 return values.isEmpty();
101 salcianu 1.1.2.1 }
102 salcianu 1.1.2.1
103 salcianu 1.1.2.1 public void removeValues(PredicateWrapper predicate){
104 salcianu 1.1.2.1 Iterator it_keys = keys().iterator();
105 salcianu 1.1.2.1 while(it_keys.hasNext())
106 salcianu 1.1.2.1 if(removeValues(it_keys.next(), predicate))
107 salcianu 1.1.2.1 it_keys.remove();
108 salcianu 1.1.2.1 }
109 salcianu 1.1.2.1
110 salcianu 1.1.2.1
111 salcianu 1.1.2.1 public void removeObjects(PredicateWrapper predicate){
112 salcianu 1.1.2.1 removeKeys(predicate);
113 salcianu 1.1.2.1 removeValues(predicate);
114 salcianu 1.1.2.1 }
115 salcianu 1.1.2.1
116 salcianu 1.1.2.1
117 salcianu 1.1.2.1 public boolean contains(Object key, Object value){
118 salcianu 1.1.2.1 HashSet set = (HashSet)hash.get(key);
119 salcianu 1.1.2.1 if(set==null) return false;
120 salcianu 1.1.2.1 return set.contains(value);
121 salcianu 1.1.2.1 }
122 salcianu 1.1.2.1
123 salcianu 1.1.2.1
124 salcianu 1.1.2.1 public boolean containsKey(Object key){
125 salcianu 1.1.2.1 return hash.containsKey(key);
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 isEmpty(){
130 salcianu 1.1.2.1 return hash.isEmpty();
131 salcianu 1.1.2.1 }
132 salcianu 1.1.2.1
133 salcianu 1.1.2.1
134 salcianu 1.1.2.1 public Set getValues(Object key){
135 salcianu 1.1.2.1 HashSet set = (HashSet)hash.get(key);
136 salcianu 1.1.2.1 if(set==null)
137 salcianu 1.1.2.1 return Collections.EMPTY_SET;
138 salcianu 1.1.2.1 return set;
139 salcianu 1.1.2.1 }
140 salcianu 1.1.2.1
141 salcianu 1.1.2.1
142 salcianu 1.1.2.1 public Set keys() {
143 salcianu 1.1.2.1 return hash.keySet();
144 salcianu 1.1.2.1 }
145 salcianu 1.1.2.1
146 salcianu 1.1.2.1
147 salcianu 1.1.2.1 public Set values() {
148 salcianu 1.1.2.1 Set vals = new HashSet();
149 salcianu 1.1.2.1 for(Iterator it = keys().iterator(); it.hasNext(); )
150 salcianu 1.1.2.1 vals.addAll(getValues(it.next()));
151 salcianu 1.1.2.1 return vals;
152 salcianu 1.1.2.1 }
153 salcianu 1.1.2.1
154 salcianu 1.1.2.1
155 salcianu 1.4 public boolean union(Relation rel) {
156 salcianu 1.4 if(rel==null) return false;
157 salcianu 1.4 boolean changed = false;
158 salcianu 1.1.2.1 for(Iterator it = rel.keys().iterator(); it.hasNext(); ) {
159 salcianu 1.1.2.1 Object o = it.next();
160 salcianu 1.4 if(addAll(o, rel.getValues(o)))
161 salcianu 1.4 changed = true;
162 salcianu 1.1.2.1 }
163 salcianu 1.4 return changed;
164 salcianu 1.1.2.1 }
165 salcianu 1.1.2.1
166 salcianu 1.1.2.1
167 salcianu 1.1.2.1 public boolean equals(Object o){
168 salcianu 1.1.2.1 if(o==null) return false;
169 salcianu 1.1.2.1 Relation r2 = (Relation)o;
170 salcianu 1.1.2.1 Set set1 = (Set) keys();
171 salcianu 1.1.2.1 Set set2 = (Set) r2.keys();
172 salcianu 1.1.2.1 if(!set1.equals(set2)) return false;
173 salcianu 1.1.2.1
174 salcianu 1.1.2.1 for(Iterator it = set1.iterator();it.hasNext(); ) {
175 salcianu 1.1.2.1 Object obj = it.next();
176 salcianu 1.1.2.1 Set set_a = (Set) getValues(obj);
177 salcianu 1.1.2.1 Set set_b = (Set) r2.getValues(obj);
178 salcianu 1.1.2.1 if(!set_a.equals(set_b)) return false;
179 salcianu 1.1.2.1 }
180 salcianu 1.1.2.1 return true;
181 salcianu 1.1.2.1 }
182 salcianu 1.1.2.1
183 salcianu 1.1.2.1
184 salcianu 1.1.2.1 // Private constructor for <code>clone</code>.
185 salcianu 1.1.2.1 private RelationImpl(Hashtable _hash){
186 salcianu 1.1.2.1 hash = _hash;
187 salcianu 1.1.2.1 }
188 salcianu 1.1.2.1
189 salcianu 1.1.2.1
190 salcianu 1.1.2.1 public Relation select(Collection selected_keys){
191 salcianu 1.1.2.1 Relation rel2 = new RelationImpl();
192 salcianu 1.1.2.1 for(Iterator it = keys().iterator(); it.hasNext(); ) {
193 salcianu 1.1.2.1 Object key = it.next();
194 salcianu 1.1.2.1 if(!selected_keys.contains(key)) continue;
195 salcianu 1.1.2.1 rel2.addAll(key, getValues(key));
196 salcianu 1.1.2.1 }
197 salcianu 1.1.2.1 return rel2;
198 salcianu 1.1.2.1 }
199 salcianu 1.1.2.1
200 salcianu 1.1.2.1
201 salcianu 1.1.2.1 public void forAllEntries(RelationEntryVisitor visitor){
202 salcianu 1.1.2.1 for(Iterator itk = hash.keySet().iterator(); itk.hasNext(); ) {
203 salcianu 1.1.2.1 Object key = itk.next();
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 visitor.visit(key, value);
207 salcianu 1.1.2.1 }
208 salcianu 1.1.2.1 }
209 salcianu 1.1.2.1 }
210 salcianu 1.1.2.1
211 salcianu 1.1.2.1 /** Creates a new, independent relation (the operations on
212 salcianu 1.1.2.1 the new relation won't affect the old one). */
213 salcianu 1.1.2.1 public Object clone(){
214 salcianu 1.1.2.1 Hashtable new_hash = new Hashtable();
215 cananian 1.5 for (Object entryO : hash.entrySet()){
216 cananian 1.5 Map.Entry entry = (Map.Entry) entryO;
217 salcianu 1.1.2.1 new_hash.put(entry.getKey(),((HashSet)entry.getValue()).clone());
218 salcianu 1.1.2.1 }
219 salcianu 1.1.2.1 return new RelationImpl(new_hash);
220 salcianu 1.1.2.1 }
221 salcianu 1.1.2.1
222 salcianu 1.1.2.1
223 salcianu 1.1.2.1 /** Pretty-print function for debug.
224 salcianu 1.1.2.1 <code>rel1.equals(rel2) <==> rel1.toString().equals(rel2.toString())</code> */
225 salcianu 1.1.2.1 public String toString(){
226 salcianu 1.1.2.1 StringBuffer buffer = new StringBuffer();
227 salcianu 1.1.2.1
228 salcianu 1.1.2.1 buffer.append("{");
229 salcianu 1.1.2.1
230 salcianu 1.1.2.1 Set keyset = (Set) keys();
231 salcianu 1.1.2.1 Object[] keys = Debug.sortedSet(hash.keySet());
232 salcianu 1.1.2.1 for(int i = 0 ; i < keys.length ; i++ ){
233 salcianu 1.1.2.1 Object key = keys[i];
234 salcianu 1.1.2.1 buffer.append("\n ");
235 salcianu 1.1.2.1 buffer.append(key);
236 salcianu 1.1.2.1 buffer.append(" -> ");
237 salcianu 1.1.2.1 buffer.append(Debug.stringImg(getValues(key)));
238 salcianu 1.1.2.1 }
239 salcianu 1.1.2.1
240 salcianu 1.1.2.1 buffer.append("\n }\n");
241 salcianu 1.1.2.1
242 salcianu 1.1.2.1 return buffer.toString();
243 salcianu 1.1.2.1 }
244 salcianu 1.1.2.1
245 salcianu 1.3 public Relation revert(final Relation result) {
246 salcianu 1.1.2.2 forAllEntries(new RelationEntryVisitor() {
247 salcianu 1.1.2.2 public void visit(Object key, Object value) {
248 salcianu 1.1.2.2 result.add(value, key);
249 salcianu 1.1.2.2 }
250 salcianu 1.1.2.2 });
251 salcianu 1.3 return result;
252 salcianu 1.1.2.2 }
253 salcianu 1.3
254 salcianu 1.3 public Relation convert(final Map map, final Relation result) {
255 salcianu 1.3 forAllEntries(new RelationEntryVisitor() {
256 salcianu 1.3 public void visit(Object key, Object value) {
257 salcianu 1.3 Object keyp = map.get(key);
258 salcianu 1.3 if(keyp == null) keyp = key;
259 salcianu 1.3 Object valuep = map.get(value);
260 salcianu 1.3 if(valuep == null) valuep = value;
261 salcianu 1.3 result.add(keyp, valuep);
262 salcianu 1.3 }
263 salcianu 1.3 });
264 salcianu 1.3 return result;
265 salcianu 1.3 }
266 salcianu 1.3
267 salcianu 1.1.2.1 }
268 salcianu 1.1.2.1
269 salcianu 1.1.2.1
270 salcianu 1.1.2.1
271 salcianu 1.1.2.1
272 salcianu 1.1.2.1
273 salcianu 1.1.2.1
274 salcianu 1.1.2.1
275 salcianu 1.1.2.1
276 salcianu 1.1.2.1
277 salcianu 1.1.2.1
278 salcianu 1.1.2.1
279 salcianu 1.1.2.1
280 salcianu 1.1.2.1
281 salcianu 1.1.2.1
282 salcianu 1.1.2.1
283 salcianu 1.1.2.1
284 salcianu 1.1.2.1
285 salcianu 1.1.2.1
286 salcianu 1.1.2.1
287 salcianu 1.1.2.1
288 salcianu 1.1.2.1
289 cananian 1.2