1 19 20 25 26 27 28 29 30 31 package soot.util; 32 33 import java.util.*; 34 35 38 39 public class ArraySet extends AbstractSet 40 { 41 private static final int DEFAULT_SIZE = 8; 42 43 private int numElements; 44 private int maxElements; 45 private Object [] elements; 46 47 public ArraySet( int size ) 48 { 49 maxElements = size; 50 elements = new Object [size]; 51 numElements = 0; 52 } 53 54 public ArraySet() 55 { 56 this(DEFAULT_SIZE); 57 } 58 59 62 63 public ArraySet(Object [] elements) 64 { 65 this(); 66 67 for(int i = 0; i < elements.length; i++) 68 add(elements[i]); 69 } 70 71 final public void clear() 72 { 73 numElements = 0; 74 } 75 76 final public boolean contains(Object obj) 77 { 78 for(int i = 0; i < numElements; i++) 79 if(elements[i].equals(obj)) 80 return true; 81 82 return false; 83 } 84 85 87 final public boolean addElement(Object e) 88 { 89 if(e==null) throw new RuntimeException ( "oops" ); 90 if(numElements == maxElements) 92 doubleCapacity(); 93 94 elements[numElements++] = e; 96 return true; 97 } 98 99 final public boolean add(Object e) 100 { 101 if(e==null) throw new RuntimeException ( "oops" ); 102 if(contains(e)) 103 return false; 104 else 105 { 106 if(numElements == maxElements) 108 doubleCapacity(); 109 110 elements[numElements++] = e; 112 return true; 113 } 114 } 115 116 final public boolean addAll(Collection s) { 117 boolean ret = false; 118 if( !(s instanceof ArraySet) ) return super.addAll(s); 119 ArraySet as = (ArraySet) s; 120 for( int i = 0; i < as.elements.length; i++ ) 121 ret = add( as.elements[i] ) | ret; 122 return ret; 123 } 124 125 final public int size() 126 { 127 return numElements; 128 } 129 130 final public Iterator iterator() 131 { 132 return new ArrayIterator(); 133 } 134 135 private class ArrayIterator implements Iterator 136 { 137 int nextIndex; 138 139 ArrayIterator() 140 { 141 nextIndex = 0; 142 } 143 144 final public boolean hasNext() 145 { 146 return nextIndex < numElements; 147 } 148 149 final public Object next() throws NoSuchElementException 150 { 151 if(!(nextIndex < numElements)) 152 throw new NoSuchElementException(); 153 154 return elements[nextIndex++]; 155 } 156 157 final public void remove() throws NoSuchElementException 158 { 159 if(nextIndex == 0) 160 throw new NoSuchElementException(); 161 else 162 { 163 removeElementAt(nextIndex - 1); 164 nextIndex = nextIndex - 1; 165 } 166 } 167 } 168 169 final private void removeElementAt(int index) 170 { 171 if(index == numElements - 1) 173 { 174 numElements--; 175 return; 176 } 177 178 System.arraycopy(elements, index + 1, elements, index, numElements - (index + 1)); 180 numElements--; 181 } 182 183 184 final private void doubleCapacity() 185 { 186 int newSize = maxElements * 2; 187 188 Object [] newElements = new Object [newSize]; 189 190 System.arraycopy(elements, 0, newElements, 0, numElements); 191 elements = newElements; 192 maxElements = newSize; 193 } 194 195 final public Object [] toArray() 196 { 197 Object [] array = new Object [numElements]; 198 199 System.arraycopy(elements, 0, array, 0, numElements); 200 return array; 201 } 202 203 final public Object [] toArray( Object [] array ) 204 { 205 System.arraycopy(elements, 0, array, 0, numElements); 206 return array; 207 } 208 209 final public Object [] getUnderlyingArray() 210 { 211 return elements; 212 } 213 214 class Array 215 { 216 private final int DEFAULT_SIZE = 8; 217 218 private int numElements; 219 private int maxElements; 220 private Object [] elements; 221 222 final public void clear() 223 { 224 numElements = 0; 225 } 226 227 public Array() 228 { 229 elements = new Object [DEFAULT_SIZE]; 230 maxElements = DEFAULT_SIZE; 231 numElements = 0; 232 } 233 234 final private void doubleCapacity() 235 { 236 int newSize = maxElements * 2; 237 238 Object [] newElements = new Object [newSize]; 239 240 System.arraycopy(elements, 0, newElements, 0, numElements); 241 elements = newElements; 242 maxElements = newSize; 243 } 244 245 final public void addElement(Object e) 246 { 247 if(numElements == maxElements) 249 doubleCapacity(); 250 251 elements[numElements++] = e; 253 } 254 255 final public void insertElementAt(Object e, int index) 256 { 257 if(numElements == maxElements) 259 doubleCapacity(); 260 261 if(index == numElements) 263 { 264 elements[numElements++] = e; 265 return; 266 } 267 268 System.arraycopy(elements, index, elements, index + 1, numElements - index); 270 elements[index] = e; 271 numElements++; 272 } 273 274 final public boolean contains(Object e) 275 { 276 for(int i = 0; i < numElements; i++) 277 if(elements[i].equals(e)) 278 return true; 279 280 return false; 281 } 282 283 final public int size() 284 { 285 return numElements; 286 } 287 288 final public Object elementAt(int index) 289 { 290 return elements[index]; 291 } 292 293 final public void removeElementAt(int index) 294 { 295 if(index == numElements - 1) 297 { 298 numElements--; 299 return; 300 } 301 302 System.arraycopy(elements, index + 1, elements, index, numElements - (index + 1)); 304 numElements--; 305 } 306 } 307 } 308 | Popular Tags |