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: /** Implementation of HashMap which guarantees a stable
031: * (between executions) order for its elements upon iteration.
032: *
033: * This is quite useful for maps of Locals, to avoid nondeterministic
034: * local-name drift. */
035: public class DeterministicHashMap extends HashMap {
036: Set<Object> keys = new TrustingMonotonicArraySet();
037:
038: /** Constructs a DeterministicHashMap with the given initial capacity. */
039: public DeterministicHashMap(int initialCapacity) {
040: super (initialCapacity);
041: }
042:
043: /** Constructs a DeterministicHashMap with the given initial capacity and load factor. */
044: public DeterministicHashMap(int initialCapacity, float loadFactor) {
045: super (initialCapacity, loadFactor);
046: }
047:
048: /** Inserts a mapping in this HashMap from <code>key</code> to <code>value</code>. */
049: public Object put(Object key, Object value) {
050: if (!containsKey(key))
051: keys.add(key);
052:
053: return super .put(key, value);
054: }
055:
056: /** Returns a backed list of entries for this HashMap (unsupported). */
057: public Collection entries() {
058: throw new UnsupportedOperationException();
059: }
060:
061: /** Removes the given object from this HashMap (unsupported). */
062: public Object remove(Object obj) {
063: throw new UnsupportedOperationException();
064: }
065:
066: /** Returns a backed list of keys for this HashMap (unsupported). */
067: public Set<Object> keySet() {
068: return keys;
069: }
070: }
071:
072: /** ArraySet which doesn't check that the elements that you insert
073: are previous uncontained. */
074:
075: class TrustingMonotonicArraySet extends AbstractSet {
076: private static final int DEFAULT_SIZE = 8;
077:
078: private int numElements;
079: private int maxElements;
080: private Object[] elements;
081:
082: public TrustingMonotonicArraySet() {
083: maxElements = DEFAULT_SIZE;
084: elements = new Object[DEFAULT_SIZE];
085: numElements = 0;
086: }
087:
088: /**
089: * Create a set which contains the given elements.
090: */
091:
092: public TrustingMonotonicArraySet(Object[] elements) {
093: this ();
094:
095: for (Object element : elements)
096: add(element);
097: }
098:
099: public void clear() {
100: numElements = 0;
101: }
102:
103: public boolean contains(Object obj) {
104: for (int i = 0; i < numElements; i++)
105: if (elements[i].equals(obj))
106: return true;
107:
108: return false;
109: }
110:
111: public boolean add(Object e) {
112: // Expand array if necessary
113: if (numElements == maxElements)
114: doubleCapacity();
115:
116: // Add element
117: elements[numElements++] = e;
118: return true;
119: }
120:
121: public int size() {
122: return numElements;
123: }
124:
125: public Iterator iterator() {
126: return new ArrayIterator();
127: }
128:
129: private class ArrayIterator implements Iterator {
130: int nextIndex;
131:
132: ArrayIterator() {
133: nextIndex = 0;
134: }
135:
136: public boolean hasNext() {
137: return nextIndex < numElements;
138: }
139:
140: public Object next() throws NoSuchElementException {
141: if (!(nextIndex < numElements))
142: throw new NoSuchElementException();
143:
144: return elements[nextIndex++];
145: }
146:
147: public void remove() throws NoSuchElementException {
148: if (nextIndex == 0)
149: throw new NoSuchElementException();
150: else {
151: removeElementAt(nextIndex - 1);
152: nextIndex = nextIndex - 1;
153: }
154: }
155: }
156:
157: private void removeElementAt(int index) {
158: throw new UnsupportedOperationException();
159: /*
160: // Handle simple case
161: if(index == numElements - 1)
162: {
163: numElements--;
164: return;
165: }
166:
167: // Else, shift over elements
168: System.arraycopy(elements, index + 1, elements, index, numElements - (index + 1));
169: numElements--; */
170: }
171:
172: private void doubleCapacity() {
173: int newSize = maxElements * 2;
174:
175: Object[] newElements = new Object[newSize];
176:
177: System.arraycopy(elements, 0, newElements, 0, numElements);
178: elements = newElements;
179: maxElements = newSize;
180: }
181:
182: public Object[] toArray() {
183: Object[] array = new Object[numElements];
184:
185: System.arraycopy(elements, 0, array, 0, numElements);
186: return array;
187: }
188: }
|