001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2002 Sable Research Group
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: public class IterableMap implements Map {
031: private HashMap<Object, Object> content_map, back_map;
032: private HashChain key_chain, value_chain;
033:
034: public IterableMap() {
035: this (7, 0.7f);
036: }
037:
038: public IterableMap(int initialCapacity) {
039: this (initialCapacity, 0.7f);
040: }
041:
042: public IterableMap(int initialCapacity, float loadFactor) {
043: content_map = new HashMap<Object, Object>(initialCapacity,
044: loadFactor);
045: back_map = new HashMap<Object, Object>(initialCapacity,
046: loadFactor);
047: key_chain = new HashChain();
048: value_chain = new HashChain();
049: }
050:
051: public void clear() {
052: Iterator kcit = key_chain.iterator();
053: while (kcit.hasNext())
054: content_map.remove(kcit.next());
055:
056: Iterator vcit = value_chain.iterator();
057: while (vcit.hasNext())
058: back_map.remove(vcit.next());
059:
060: key_chain.clear();
061: value_chain.clear();
062: }
063:
064: public Iterator iterator() {
065: return key_chain.iterator();
066: }
067:
068: public boolean containsKey(Object key) {
069: return key_chain.contains(key);
070: }
071:
072: public boolean containsValue(Object value) {
073: return value_chain.contains(value);
074: }
075:
076: public Set entrySet() {
077: return content_map.entrySet();
078: }
079:
080: public boolean equals(Object o) {
081: if (o == this )
082: return true;
083:
084: if ((o instanceof IterableMap) == false)
085: return false;
086:
087: IterableMap other = (IterableMap) o;
088:
089: if (key_chain.equals(other.key_chain) == false)
090: return false;
091:
092: // check that the other has our mapping
093: Iterator kcit = key_chain.iterator();
094: while (kcit.hasNext()) {
095: Object ko = kcit.next();
096:
097: if (other.content_map.get(ko) != content_map.get(ko))
098: return false;
099: }
100:
101: return true;
102: }
103:
104: public Object get(Object key) {
105: return content_map.get(key);
106: }
107:
108: public int hashCode() {
109: return content_map.hashCode();
110: }
111:
112: public boolean isEmpty() {
113: return key_chain.isEmpty();
114: }
115:
116: private transient Set<Object> keySet = null;
117: private transient Set<Object> valueSet = null;
118: private transient Collection<Object> values = null;
119:
120: public Set<Object> keySet() {
121: if (keySet == null) {
122: keySet = new AbstractSet() {
123: public Iterator iterator() {
124: return key_chain.iterator();
125: }
126:
127: public int size() {
128: return key_chain.size();
129: }
130:
131: public boolean contains(Object o) {
132: return key_chain.contains(o);
133: }
134:
135: public boolean remove(Object o) {
136: if (key_chain.contains(o) == false) {
137: return false;
138: }
139:
140: if (IterableMap.this .content_map.get(o) == null) {
141: IterableMap.this .remove(o);
142: return true;
143: }
144:
145: return (IterableMap.this .remove(o) != null);
146: }
147:
148: public void clear() {
149: IterableMap.this .clear();
150: }
151: };
152: }
153: return keySet;
154: }
155:
156: public Set<Object> valueSet() {
157: if (valueSet == null) {
158: valueSet = new AbstractSet() {
159: public Iterator iterator() {
160: return value_chain.iterator();
161: }
162:
163: public int size() {
164: return value_chain.size();
165: }
166:
167: public boolean contains(Object o) {
168: return value_chain.contains(o);
169: }
170:
171: public boolean remove(Object o) {
172: if (value_chain.contains(o) == false) {
173: return false;
174: }
175:
176: HashChain c = (HashChain) IterableMap.this .back_map
177: .get(o);
178: Iterator it = c.snapshotIterator();
179: while (it.hasNext()) {
180: Object ko = it.next();
181:
182: if (IterableMap.this .content_map.get(o) == null) {
183: IterableMap.this .remove(ko);
184: } else if (IterableMap.this .remove(ko) == null) {
185: return false;
186: }
187: }
188: return true;
189: }
190:
191: public void clear() {
192: IterableMap.this .clear();
193: }
194: };
195: }
196: return valueSet;
197: }
198:
199: public Object put(Object key, Object value) {
200: if (key_chain.contains(key)) {
201:
202: Object old_value = content_map.get(key);
203:
204: if (old_value == value)
205: return value;
206:
207: HashChain kc = (HashChain) back_map.get(old_value);
208: kc.remove(key);
209:
210: if (kc.isEmpty()) {
211: value_chain.remove(old_value);
212: back_map.remove(old_value);
213: }
214:
215: kc = (HashChain) back_map.get(value);
216: if (kc == null) {
217: kc = new HashChain();
218: back_map.put(value, kc);
219: value_chain.add(value);
220: }
221: kc.add(key);
222:
223: return old_value;
224:
225: } else {
226:
227: key_chain.add(key);
228: content_map.put(key, value);
229:
230: HashChain kc = (HashChain) back_map.get(value);
231: if (kc == null) {
232: kc = new HashChain();
233: back_map.put(value, kc);
234: value_chain.add(value);
235: }
236: kc.add(key);
237:
238: return null;
239: }
240: }
241:
242: public void putAll(Map t) {
243: Iterator kit = (t instanceof IterableMap) ? ((IterableMap) t).key_chain
244: .iterator()
245: : t.keySet().iterator();
246:
247: while (kit.hasNext()) {
248: Object key = kit.next();
249: put(key, t.get(key));
250: }
251: }
252:
253: public Object remove(Object key) {
254: if (key_chain.contains(key) == false)
255: return null;
256:
257: key_chain.remove(key);
258: Object value = content_map.remove(key);
259: HashChain c = (HashChain) back_map.get(value);
260: c.remove(key);
261: if (c.size() == 0)
262: back_map.remove(value);
263:
264: return value;
265: }
266:
267: public int size() {
268: return key_chain.size();
269: }
270:
271: public Collection<Object> values() {
272: if (values == null) {
273: values = new AbstractCollection() {
274: public Iterator iterator() {
275: return new Mapping_Iterator(
276: IterableMap.this .key_chain,
277: IterableMap.this .content_map);
278: }
279:
280: public int size() {
281: return key_chain.size();
282: }
283:
284: public boolean contains(Object o) {
285: return value_chain.contains(o);
286: }
287:
288: public void clear() {
289: IterableMap.this .clear();
290: }
291: };
292: }
293: return values;
294: }
295:
296: public class Mapping_Iterator implements Iterator {
297: private final Iterator it;
298: private HashMap<Object, Object> m;
299:
300: public Mapping_Iterator(HashChain c, HashMap<Object, Object> m) {
301: it = c.iterator();
302: this .m = m;
303: }
304:
305: public boolean hasNext() {
306: return it.hasNext();
307: }
308:
309: public Object next() throws NoSuchElementException {
310: return m.get(it.next());
311: }
312:
313: public void remove() throws UnsupportedOperationException {
314: throw new UnsupportedOperationException(
315: "You cannot remove from an Iterator on the values() for an IterableMap.");
316: }
317: }
318:
319: }
|