001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-1999 Raja Vallee-Rai
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.util;
027:
028: import java.util.*;
029:
030: /**
031: * Provides an implementation of the Set object using java.util.Array
032: */
033:
034: public class ArraySet extends AbstractSet {
035: private static final int DEFAULT_SIZE = 8;
036:
037: private int numElements;
038: private int maxElements;
039: private Object[] elements;
040:
041: public ArraySet(int size) {
042: maxElements = size;
043: elements = new Object[size];
044: numElements = 0;
045: }
046:
047: public ArraySet() {
048: this (DEFAULT_SIZE);
049: }
050:
051: /**
052: * Create a set which contains the given elements.
053: */
054:
055: public ArraySet(Object[] elements) {
056: this ();
057:
058: for (Object element : elements)
059: add(element);
060: }
061:
062: final public void clear() {
063: numElements = 0;
064: }
065:
066: final public boolean contains(Object obj) {
067: for (int i = 0; i < numElements; i++)
068: if (elements[i].equals(obj))
069: return true;
070:
071: return false;
072: }
073:
074: /** Add an element without checking whether it is already in the set.
075: * It is up to the caller to guarantee that it isn't. */
076: final public boolean addElement(Object e) {
077: if (e == null)
078: throw new RuntimeException("oops");
079: // Expand array if necessary
080: if (numElements == maxElements)
081: doubleCapacity();
082:
083: // Add element
084: elements[numElements++] = e;
085: return true;
086: }
087:
088: final public boolean add(Object e) {
089: if (e == null)
090: throw new RuntimeException("oops");
091: if (contains(e))
092: return false;
093: else {
094: // Expand array if necessary
095: if (numElements == maxElements)
096: doubleCapacity();
097:
098: // Add element
099: elements[numElements++] = e;
100: return true;
101: }
102: }
103:
104: final public boolean addAll(Collection s) {
105: boolean ret = false;
106: if (!(s instanceof ArraySet))
107: return super .addAll(s);
108: ArraySet as = (ArraySet) s;
109: for (Object element : as.elements)
110: ret = add(element) | ret;
111: return ret;
112: }
113:
114: final public int size() {
115: return numElements;
116: }
117:
118: final public Iterator iterator() {
119: return new ArrayIterator();
120: }
121:
122: private class ArrayIterator implements Iterator {
123: int nextIndex;
124:
125: ArrayIterator() {
126: nextIndex = 0;
127: }
128:
129: final public boolean hasNext() {
130: return nextIndex < numElements;
131: }
132:
133: final public Object next() throws NoSuchElementException {
134: if (!(nextIndex < numElements))
135: throw new NoSuchElementException();
136:
137: return elements[nextIndex++];
138: }
139:
140: final public void remove() throws NoSuchElementException {
141: if (nextIndex == 0)
142: throw new NoSuchElementException();
143: else {
144: removeElementAt(nextIndex - 1);
145: nextIndex = nextIndex - 1;
146: }
147: }
148: }
149:
150: final private void removeElementAt(int index) {
151: // Handle simple case
152: if (index == numElements - 1) {
153: numElements--;
154: return;
155: }
156:
157: // Else, shift over elements
158: System.arraycopy(elements, index + 1, elements, index,
159: numElements - (index + 1));
160: numElements--;
161: }
162:
163: final private void doubleCapacity() {
164: int newSize = maxElements * 2;
165:
166: Object[] newElements = new Object[newSize];
167:
168: System.arraycopy(elements, 0, newElements, 0, numElements);
169: elements = newElements;
170: maxElements = newSize;
171: }
172:
173: final public Object[] toArray() {
174: Object[] array = new Object[numElements];
175:
176: System.arraycopy(elements, 0, array, 0, numElements);
177: return array;
178: }
179:
180: final public Object[] toArray(Object[] array) {
181: System.arraycopy(elements, 0, array, 0, numElements);
182: return array;
183: }
184:
185: final public Object[] getUnderlyingArray() {
186: return elements;
187: }
188:
189: class Array {
190: private final int DEFAULT_SIZE = 8;
191:
192: private int numElements;
193: private int maxElements;
194: private Object[] elements;
195:
196: final public void clear() {
197: numElements = 0;
198: }
199:
200: public Array() {
201: elements = new Object[DEFAULT_SIZE];
202: maxElements = DEFAULT_SIZE;
203: numElements = 0;
204: }
205:
206: final private void doubleCapacity() {
207: int newSize = maxElements * 2;
208:
209: Object[] newElements = new Object[newSize];
210:
211: System.arraycopy(elements, 0, newElements, 0, numElements);
212: elements = newElements;
213: maxElements = newSize;
214: }
215:
216: final public void addElement(Object e) {
217: // Expand array if necessary
218: if (numElements == maxElements)
219: doubleCapacity();
220:
221: // Add element
222: elements[numElements++] = e;
223: }
224:
225: final public void insertElementAt(Object e, int index) {
226: // Expaxpand array if necessary
227: if (numElements == maxElements)
228: doubleCapacity();
229:
230: // Handle simple case
231: if (index == numElements) {
232: elements[numElements++] = e;
233: return;
234: }
235:
236: // Shift things over
237: System.arraycopy(elements, index, elements, index + 1,
238: numElements - index);
239: elements[index] = e;
240: numElements++;
241: }
242:
243: final public boolean contains(Object e) {
244: for (int i = 0; i < numElements; i++)
245: if (elements[i].equals(e))
246: return true;
247:
248: return false;
249: }
250:
251: final public int size() {
252: return numElements;
253: }
254:
255: final public Object elementAt(int index) {
256: return elements[index];
257: }
258:
259: final public void removeElementAt(int index) {
260: // Handle simple case
261: if (index == numElements - 1) {
262: numElements--;
263: return;
264: }
265:
266: // Else, shift over elements
267: System.arraycopy(elements, index + 1, elements, index,
268: numElements - (index + 1));
269: numElements--;
270: }
271: }
272: }
|