KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > scalar > ArraySparseSet


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 package soot.toolkits.scalar;
28
29 import soot.util.*;
30 import java.util.*;
31
32
33
34
35
36
37
38 /**
39  * Reference implementation for a FlowSet. Items are stored in an Array.
40  */

41 public class ArraySparseSet extends AbstractFlowSet
42 {
43     static final int DEFAULT_SIZE = 8;
44     
45     int numElements;
46     int maxElements;
47     Object JavaDoc[] elements;
48
49     public ArraySparseSet()
50     {
51         maxElements = DEFAULT_SIZE;
52         elements = new Object JavaDoc[DEFAULT_SIZE];
53         numElements = 0;
54     }
55     
56     private ArraySparseSet(ArraySparseSet other)
57     {
58         numElements = other.numElements;
59         maxElements = other.maxElements;
60         elements = (Object JavaDoc[]) other.elements.clone();
61     }
62     
63     /** Returns true if flowSet is the same type of flow set as this. */
64     private boolean sameType(Object JavaDoc flowSet)
65     {
66         return (flowSet instanceof ArraySparseSet);
67     }
68
69     public Object JavaDoc clone()
70     {
71         return new ArraySparseSet(this);
72     }
73
74     public Object JavaDoc 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     /** Returns a unbacked list of elements in this set. */
95     public List toList()
96     {
97         Object JavaDoc[] copiedElements = new Object JavaDoc[numElements];
98         System.arraycopy(elements, 0, copiedElements, 0, numElements);
99         return Arrays.asList(copiedElements);
100     }
101
102   /* Expand array only when necessary, pointed out by Florian Loitsch
103    * March 08, 2002
104    */

105     public void add(Object JavaDoc e)
106     {
107       /* Expand only if necessary! and removes one if too:) */
108         // Add element
109
if(!contains(e)) {
110               // Expand array if necessary
111
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 JavaDoc[] newElements = new Object JavaDoc[newSize];
122                 
123         System.arraycopy(elements, 0, newElements, 0, numElements);
124         elements = newElements;
125         maxElements = newSize;
126     }
127
128     public void remove(Object JavaDoc 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   /* copy last element to the position of deleted element, and
142    * decrease the array size.
143    * pointed out by Florian Loitsch, March 2002
144    */

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         // For the special case that dest == other
158
if(dest == other)
159             {
160                 for(int i = 0; i < this.numElements; i++)
161                     dest.add(this.elements[i]);
162             }
163         
164         // Else, force that dest starts with contents of this
165
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 JavaDoc 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 JavaDoc 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         // Make sure that thisFlow is contained in otherFlow
250
for(int i = 0; i < size; i++)
251                 if(!other.contains(this.elements[i]))
252                     return false;
253
254             /* both arrays have the same size, no element appears twice in one
255              * array, all elements of ThisFlow are in otherFlow -> they are
256              * equal! we don't need to test again!
257         // Make sure that otherFlow is contained in ThisFlow
258             for(int i = 0; i < size; i++)
259                 if(!this.contains(other.elements[i]))
260                     return false;
261              */

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 JavaDoc[] array;
287         private int realSize;
288         
289         public SparseArrayList(Object JavaDoc[] array, int realSize)
290         {
291             this.array = array;
292             this.realSize = realSize;
293         }
294         
295         public Object JavaDoc get(int index)
296         {
297             return array[index];
298         }
299         
300         public Object JavaDoc set(int index, Object JavaDoc element)
301         {
302             throw new UnsupportedOperationException JavaDoc();
303         }
304         
305         public int size()
306         {
307             return realSize;
308         }
309         
310         public Object JavaDoc clone()
311         {
312             return array.clone();
313         }
314         
315     }
316
317 }
318
Popular Tags