1 19 20 25 26 27 package soot.toolkits.scalar; 28 29 import soot.util.*; 30 import java.util.*; 31 32 33 34 35 36 37 38 41 public class ArraySparseSet extends AbstractFlowSet 42 { 43 static final int DEFAULT_SIZE = 8; 44 45 int numElements; 46 int maxElements; 47 Object [] elements; 48 49 public ArraySparseSet() 50 { 51 maxElements = DEFAULT_SIZE; 52 elements = new Object [DEFAULT_SIZE]; 53 numElements = 0; 54 } 55 56 private ArraySparseSet(ArraySparseSet other) 57 { 58 numElements = other.numElements; 59 maxElements = other.maxElements; 60 elements = (Object []) other.elements.clone(); 61 } 62 63 64 private boolean sameType(Object flowSet) 65 { 66 return (flowSet instanceof ArraySparseSet); 67 } 68 69 public Object clone() 70 { 71 return new ArraySparseSet(this); 72 } 73 74 public Object emptySet() 75 { 76 return new ArraySparseSet(); 77 } 78 79 public void clear() 80 { 81 numElements = 0; 82 } 83 84 public int size() 85 { 86 return numElements; 87 } 88 89 public boolean isEmpty() 90 { 91 return numElements == 0; 92 } 93 94 95 public List toList() 96 { 97 Object [] copiedElements = new Object [numElements]; 98 System.arraycopy(elements, 0, copiedElements, 0, numElements); 99 return Arrays.asList(copiedElements); 100 } 101 102 105 public void add(Object e) 106 { 107 108 if(!contains(e)) { 110 if(numElements == maxElements) 112 doubleCapacity(); 113 elements[numElements++] = e; 114 } 115 } 116 117 private void doubleCapacity() 118 { 119 int newSize = maxElements * 2; 120 121 Object [] newElements = new Object [newSize]; 122 123 System.arraycopy(elements, 0, newElements, 0, numElements); 124 elements = newElements; 125 maxElements = newSize; 126 } 127 128 public void remove(Object obj) 129 { 130 int i = 0; 131 while (i < this.numElements) { 132 if (elements[i].equals(obj)) 133 { 134 elements[i] = elements[--numElements]; 135 return; 136 } else 137 i++; 138 } 139 } 140 141 145 private void removeElementAt(int index) 146 { 147 elements[index] = elements[--numElements]; 148 } 149 150 public void union(FlowSet otherFlow, FlowSet destFlow) 151 { 152 if (sameType(otherFlow) && 153 sameType(destFlow)) { 154 ArraySparseSet other = (ArraySparseSet) otherFlow; 155 ArraySparseSet dest = (ArraySparseSet) destFlow; 156 157 if(dest == other) 159 { 160 for(int i = 0; i < this.numElements; i++) 161 dest.add(this.elements[i]); 162 } 163 164 else { 166 if(this != dest) 167 copy(dest); 168 169 for(int i = 0; i < other.numElements; i++) 170 dest.add(other.elements[i]); 171 } 172 } else 173 super.union(otherFlow, destFlow); 174 } 175 176 public void intersection(FlowSet otherFlow, FlowSet destFlow) 177 { 178 if (sameType(otherFlow) && 179 sameType(destFlow)) { 180 ArraySparseSet other = (ArraySparseSet) otherFlow; 181 ArraySparseSet dest = (ArraySparseSet) destFlow; 182 ArraySparseSet workingSet; 183 184 if(dest == other || dest == this) 185 workingSet = new ArraySparseSet(); 186 else { 187 workingSet = dest; 188 workingSet.clear(); 189 } 190 191 for(int i = 0; i < this.numElements; i++) 192 { 193 if(other.contains(this.elements[i])) 194 workingSet.add(this.elements[i]); 195 } 196 197 if(workingSet != dest) 198 workingSet.copy(dest); 199 } else 200 super.intersection(otherFlow, destFlow); 201 } 202 203 public void difference(FlowSet otherFlow, FlowSet destFlow) 204 { 205 if (sameType(otherFlow) && 206 sameType(destFlow)) { 207 ArraySparseSet other = (ArraySparseSet) otherFlow; 208 ArraySparseSet dest = (ArraySparseSet) destFlow; 209 ArraySparseSet workingSet; 210 211 if(dest == other || dest == this) 212 workingSet = new ArraySparseSet(); 213 else { 214 workingSet = dest; 215 workingSet.clear(); 216 } 217 218 for(int i = 0; i < this.numElements; i++) 219 { 220 if(!other.contains(this.elements[i])) 221 workingSet.add(this.elements[i]); 222 } 223 224 if(workingSet != dest) 225 workingSet.copy(dest); 226 } else 227 super.difference(otherFlow, destFlow); 228 } 229 230 public boolean contains(Object obj) 231 { 232 for(int i = 0; i < numElements; i++) 233 if(elements[i].equals(obj)) 234 return true; 235 236 return false; 237 } 238 239 public boolean equals(Object otherFlow) 240 { 241 if (sameType(otherFlow)) { 242 ArraySparseSet other = (ArraySparseSet) otherFlow; 243 244 if(other.numElements != this.numElements) 245 return false; 246 247 int size = this.numElements; 248 249 for(int i = 0; i < size; i++) 251 if(!other.contains(this.elements[i])) 252 return false; 253 254 262 263 return true; 264 } else 265 return super.equals(otherFlow); 266 } 267 268 public void copy(FlowSet destFlow) 269 { 270 if (sameType(destFlow)) { 271 ArraySparseSet dest = (ArraySparseSet) destFlow; 272 273 while(dest.maxElements < this.maxElements) 274 dest.doubleCapacity(); 275 276 dest.numElements = this.numElements; 277 278 System.arraycopy(this.elements, 0, 279 dest.elements, 0, this.numElements); 280 } else 281 super.copy(destFlow); 282 } 283 284 private static class SparseArrayList extends AbstractList 285 { 286 private Object [] array; 287 private int realSize; 288 289 public SparseArrayList(Object [] array, int realSize) 290 { 291 this.array = array; 292 this.realSize = realSize; 293 } 294 295 public Object get(int index) 296 { 297 return array[index]; 298 } 299 300 public Object set(int index, Object element) 301 { 302 throw new UnsupportedOperationException (); 303 } 304 305 public int size() 306 { 307 return realSize; 308 } 309 310 public Object clone() 311 { 312 return array.clone(); 313 } 314 315 } 316 317 } 318 | Popular Tags |