KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > util > DeterministicHashMap


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.util;
28
29 import soot.util.*;
30 import java.util.*;
31
32 /** Implementation of HashMap which guarantees a stable
33  * (between executions) order for its elements upon iteration.
34  *
35  * This is quite useful for maps of Locals, to avoid nondeterministic
36  * local-name drift. */
37 public class DeterministicHashMap extends HashMap
38 {
39     Set keys = new TrustingMonotonicArraySet();
40     
41     /** Constructs a DeterministicHashMap with the given initial capacity. */
42     public DeterministicHashMap(int initialCapacity)
43     {
44         super(initialCapacity);
45     }
46
47     /** Constructs a DeterministicHashMap with the given initial capacity and load factor. */
48     public DeterministicHashMap(int initialCapacity, float loadFactor)
49     {
50         super(initialCapacity, loadFactor);
51     }
52     
53     /** Inserts a mapping in this HashMap from <code>key</code> to <code>value</code>. */
54     public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value)
55     {
56         if(!containsKey(key))
57             keys.add(key);
58     
59         return super.put(key, value);
60     }
61
62     /** Returns a backed list of entries for this HashMap (unsupported). */
63     public Collection entries()
64     {
65         throw new UnsupportedOperationException JavaDoc();
66     }
67     
68     /** Removes the given object from this HashMap (unsupported). */
69     public Object JavaDoc remove(Object JavaDoc obj)
70     {
71         throw new UnsupportedOperationException JavaDoc();
72     }
73     
74     /** Returns a backed list of keys for this HashMap (unsupported). */
75     public Set keySet()
76     {
77         return keys;
78     }
79 }
80
81 /** ArraySet which doesn't check that the elements that you insert
82     are previous uncontained. */
83
84 class TrustingMonotonicArraySet extends AbstractSet
85 {
86     private static final int DEFAULT_SIZE = 8;
87
88     private int numElements;
89     private int maxElements;
90     private Object JavaDoc[] elements;
91
92     public TrustingMonotonicArraySet()
93     {
94         maxElements = DEFAULT_SIZE;
95         elements = new Object JavaDoc[DEFAULT_SIZE];
96         numElements = 0;
97     }
98
99     /**
100      * Create a set which contains the given elements.
101      */
102
103     public TrustingMonotonicArraySet(Object JavaDoc[] elements)
104     {
105         this();
106
107         for(int i = 0; i < elements.length; i++)
108             add(elements[i]);
109     }
110
111     public void clear()
112     {
113         numElements = 0;
114     }
115
116     public boolean contains(Object JavaDoc obj)
117     {
118         for(int i = 0; i < numElements; i++)
119             if(elements[i].equals(obj))
120                 return true;
121
122         return false;
123     }
124
125     public boolean add(Object JavaDoc e)
126     {
127         // Expand array if necessary
128 if(numElements == maxElements)
129                 doubleCapacity();
130
131         // Add element
132 elements[numElements++] = e;
133             return true;
134     }
135
136     public int size()
137     {
138         return numElements;
139     }
140
141     public Iterator iterator()
142     {
143         return new ArrayIterator();
144     }
145
146     private class ArrayIterator implements Iterator
147     {
148         int nextIndex;
149
150         ArrayIterator()
151         {
152             nextIndex = 0;
153         }
154
155         public boolean hasNext()
156         {
157             return nextIndex < numElements;
158         }
159
160         public Object JavaDoc next() throws NoSuchElementException
161         {
162             if(!(nextIndex < numElements))
163                 throw new NoSuchElementException();
164
165             return elements[nextIndex++];
166         }
167
168         public void remove() throws NoSuchElementException
169         {
170             if(nextIndex == 0)
171                 throw new NoSuchElementException();
172             else
173             {
174                 removeElementAt(nextIndex - 1);
175                 nextIndex = nextIndex - 1;
176             }
177         }
178     }
179
180     private void removeElementAt(int index)
181     {
182         throw new UnsupportedOperationException JavaDoc();
183         /*
184         // Handle simple case
185             if(index == numElements - 1)
186             {
187                 numElements--;
188                 return;
189             }
190
191         // Else, shift over elements
192             System.arraycopy(elements, index + 1, elements, index, numElements - (index + 1));
193             numElements--; */
194     }
195
196
197     private void doubleCapacity()
198     {
199         int newSize = maxElements * 2;
200
201         Object JavaDoc[] newElements = new Object JavaDoc[newSize];
202
203         System.arraycopy(elements, 0, newElements, 0, numElements);
204         elements = newElements;
205         maxElements = newSize;
206     }
207
208     public Object JavaDoc[] toArray()
209     {
210         Object JavaDoc[] array = new Object JavaDoc[numElements];
211
212         System.arraycopy(elements, 0, array, 0, numElements);
213         return array;
214     }
215 }
216
217
218
Popular Tags