KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > util > ArraySet


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-1999 Raja Vallee-Rai
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */

19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */

25
26
27
28
29
30
31 package soot.util;
32
33 import java.util.*;
34
35 /**
36  * Provides an implementation of the Set object using java.util.Array
37  */

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 JavaDoc[] elements;
46
47     public ArraySet( int size )
48     {
49         maxElements = size;
50         elements = new Object JavaDoc[size];
51         numElements = 0;
52     }
53
54     public ArraySet()
55     {
56         this(DEFAULT_SIZE);
57     }
58
59     /**
60      * Create a set which contains the given elements.
61      */

62
63     public ArraySet(Object JavaDoc[] 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 JavaDoc 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     /** Add an element without checking whether it is already in the set.
86      * It is up to the caller to guarantee that it isn't. */

87     final public boolean addElement(Object JavaDoc e)
88     {
89         if(e==null) throw new RuntimeException JavaDoc( "oops" );
90         // Expand array if necessary
91
if(numElements == maxElements)
92                 doubleCapacity();
93
94         // Add element
95
elements[numElements++] = e;
96             return true;
97     }
98
99     final public boolean add(Object JavaDoc e)
100     {
101         if(e==null) throw new RuntimeException JavaDoc( "oops" );
102         if(contains(e))
103             return false;
104         else
105         {
106             // Expand array if necessary
107
if(numElements == maxElements)
108                     doubleCapacity();
109
110             // Add element
111
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 JavaDoc 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         // Handle simple case
172
if(index == numElements - 1)
173             {
174                 numElements--;
175                 return;
176             }
177
178         // Else, shift over elements
179
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 JavaDoc[] newElements = new Object JavaDoc[newSize];
189
190         System.arraycopy(elements, 0, newElements, 0, numElements);
191         elements = newElements;
192         maxElements = newSize;
193     }
194
195     final public Object JavaDoc[] toArray()
196     {
197         Object JavaDoc[] array = new Object JavaDoc[numElements];
198
199         System.arraycopy(elements, 0, array, 0, numElements);
200         return array;
201     }
202
203     final public Object JavaDoc[] toArray( Object JavaDoc[] array )
204     {
205         System.arraycopy(elements, 0, array, 0, numElements);
206         return array;
207     }
208
209     final public Object JavaDoc[] 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 JavaDoc[] elements;
221     
222         final public void clear()
223         {
224             numElements = 0;
225         }
226     
227         public Array()
228         {
229             elements = new Object JavaDoc[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 JavaDoc[] newElements = new Object JavaDoc[newSize];
239     
240             System.arraycopy(elements, 0, newElements, 0, numElements);
241             elements = newElements;
242             maxElements = newSize;
243         }
244     
245         final public void addElement(Object JavaDoc e)
246         {
247             // Expand array if necessary
248
if(numElements == maxElements)
249                     doubleCapacity();
250     
251             // Add element
252
elements[numElements++] = e;
253         }
254     
255         final public void insertElementAt(Object JavaDoc e, int index)
256         {
257             // Expaxpand array if necessary
258
if(numElements == maxElements)
259                     doubleCapacity();
260     
261             // Handle simple case
262
if(index == numElements)
263                 {
264                     elements[numElements++] = e;
265                     return;
266                 }
267     
268             // Shift things over
269
System.arraycopy(elements, index, elements, index + 1, numElements - index);
270                 elements[index] = e;
271                 numElements++;
272         }
273     
274         final public boolean contains(Object JavaDoc 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 JavaDoc elementAt(int index)
289         {
290             return elements[index];
291         }
292     
293         final public void removeElementAt(int index)
294         {
295             // Handle simple case
296
if(index == numElements - 1)
297                 {
298                     numElements--;
299                     return;
300                 }
301     
302             // Else, shift over elements
303
System.arraycopy(elements, index + 1, elements, index, numElements - (index + 1));
304                 numElements--;
305         }
306     }
307 }
308
Popular Tags