001: /*******************************************************************************
002: * Copyright (c) 2006, 2007 BEA Systems, Inc.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * wharley@bea.com - initial API and implementation
010: * (originally in org.eclipse.jdt.apt.core)
011: *******************************************************************************/package org.eclipse.jdt.internal.compiler.apt.util;
012:
013: import java.util.Collections;
014: import java.util.HashMap;
015: import java.util.HashSet;
016: import java.util.Map;
017: import java.util.Set;
018:
019: /**
020: * Manage a Map<T1, Set<T2>>, with reverse links so that it is possible to
021: * efficiently find all T1s that have a particular T2 associated with them.
022: * Access to the map is synchronized, so that it is possible to read and
023: * write simultaneously from multiple threads.
024: * <p>
025: * The map permits the null value for keys nor for value elements.
026: * <p>
027: * Design invariants preserved by all operations on this map are as follows:
028: * <ul>
029: * <li> If a key exists, it has at least one value associated with it; that is,
030: * for all k such that null != containsKey(k), getValues(k) returns a non-empty
031: * set.</li>
032: * <li> If a value exists, it has at least one key associated with it; that is,
033: * for all v such that null != containsValue(v), getKeys(v) returns a non-empty
034: * set.</li>
035: */
036: public class ManyToMany<T1, T2> {
037:
038: private final Map<T1, Set<T2>> _forward = new HashMap<T1, Set<T2>>();
039: private final Map<T2, Set<T1>> _reverse = new HashMap<T2, Set<T1>>();
040: private boolean _dirty = false;
041:
042: /**
043: * Empty all maps. If the maps previously contained entries,
044: * this will set the dirty bit.
045: * @return true if the maps contained any entries prior to being cleared
046: */
047: public synchronized boolean clear() {
048: boolean hadContent = !_forward.isEmpty() || !_reverse.isEmpty();
049: _reverse.clear();
050: _forward.clear();
051: _dirty |= hadContent;
052: return hadContent;
053: }
054:
055: /**
056: * Sets the dirty bit to false. Internal operations do not use the dirty
057: * bit; clearing it will not affect behavior of the map. It's just there
058: * for the convenience of callers who don't want to keep track of every
059: * put() and remove().
060: */
061: public synchronized void clearDirtyBit() {
062: _dirty = false;
063: }
064:
065: /**
066: * Equivalent to keySet().contains(key).
067: * @return true if the map contains the specified key.
068: */
069: public synchronized boolean containsKey(T1 key) {
070: return _forward.containsKey(key);
071: }
072:
073: /**
074: * Is there a key that is mapped to the specified value?
075: * Search within the forward map.
076: * @return true if such a key exists
077: */
078: public synchronized boolean containsKeyValuePair(T1 key, T2 value) {
079: Set<T2> values = _forward.get(key);
080: if (null == values) {
081: return false;
082: }
083: return values.contains(value);
084: }
085:
086: /**
087: * Equivalent to values().contains(value).
088: * @return true if the map contains the specified value (regardless
089: * of what key it might be associated with).
090: */
091: public synchronized boolean containsValue(T2 value) {
092: return _reverse.containsKey(value);
093: }
094:
095: /**
096: * Search the reverse map for all keys that have been associated with
097: * a particular value.
098: * @return the set of keys that are associated with the specified value,
099: * or an empty set if the value does not exist in the map.
100: */
101: public synchronized Set<T1> getKeys(T2 value) {
102: Set<T1> keys = _reverse.get(value);
103: if (null == keys) {
104: return Collections.emptySet();
105: }
106: return new HashSet<T1>(keys);
107: }
108:
109: /**
110: * Search the forward map for all values associated with a particular key.
111: * Returns a copy of the set of values.
112: * @return a copy of the set of values that are associated with the
113: * specified key, or an empty set if the key does not exist in the map.
114: */
115: public synchronized Set<T2> getValues(T1 key) {
116: Set<T2> values = _forward.get(key);
117: if (null == values) {
118: return Collections.emptySet();
119: }
120: return new HashSet<T2>(values);
121: }
122:
123: /**
124: * @return a copy of the set of all keys (that is, all items of type T1).
125: * If the maps are empty, the returned set will be empty, not null. The
126: * returned set can be modified by the caller without affecting the map.
127: * @see #getValueSet()
128: */
129: public synchronized Set<T1> getKeySet() {
130: Set<T1> keys = new HashSet<T1>(_forward.keySet());
131: return keys;
132: }
133:
134: /**
135: * @return a copy of the set of all values (that is, all items of type T2).
136: * If the maps are empty, the returned set will be empty, not null. The
137: * returned set can be modified by the caller without affecting the map.
138: * @see #getKeySet()
139: */
140: public synchronized Set<T2> getValueSet() {
141: Set<T2> values = new HashSet<T2>(_reverse.keySet());
142: return values;
143: }
144:
145: /**
146: * Return the state of the dirty bit. All operations that change the state
147: * of the maps, including @see #clear(), set the dirty bit if any content actually
148: * changed. The only way to clear the dirty bit is to call @see #clearDirtyBit().
149: * @return true if the map content has changed since it was created or since
150: * the last call to clearDirtyBit().
151: * @see #clearDirtyBit()
152: */
153: public synchronized boolean isDirty() {
154: return _dirty;
155: }
156:
157: /**
158: * Check whether <code>key</code> has an association to any values other
159: * than <code>value</code> - that is, whether the same key has been added
160: * with multiple values. Equivalent to asking whether the intersection of
161: * <code>getValues(key)</code> and the set containing <code>value</code> is
162: * non-empty.
163: * @return true iff <code>key</code> is in the map and is associated
164: * with values other than <code>value</code>.
165: * @see #valueHasOtherKeys(Object, Object)
166: */
167: public synchronized boolean keyHasOtherValues(T1 key, T2 value) {
168: Set<T2> values = _forward.get(key);
169: if (values == null)
170: return false;
171: int size = values.size();
172: if (size == 0)
173: return false;
174: else if (size > 1)
175: return true;
176: else
177: // size == 1
178: return !values.contains(value);
179: }
180:
181: /**
182: * Associate the specified value with the key. Adds the entry
183: * to both the forward and reverse maps. Adding the same value
184: * twice to a particular key has no effect. Because this is a
185: * many-to-many map, adding a new value for an existing key does
186: * not change the existing association, it adds a new one.
187: * @param key can be null
188: * @param value can be null
189: * @return true if the key/value pair did not exist prior to being added
190: */
191: public synchronized boolean put(T1 key, T2 value) {
192: // Add to forward map
193: Set<T2> values = _forward.get(key);
194: if (null == values) {
195: values = new HashSet<T2>();
196: _forward.put(key, values);
197: }
198: boolean added = values.add(value);
199: _dirty |= added;
200:
201: // Add to reverse map
202: Set<T1> keys = _reverse.get(value);
203: if (null == keys) {
204: keys = new HashSet<T1>();
205: _reverse.put(value, keys);
206: }
207: keys.add(key);
208:
209: assert checkIntegrity();
210: return added;
211: }
212:
213: /**
214: * Remove a particular key-value association. This is the inverse
215: * of put(key, value). If the key does not exist, or the value
216: * does not exist, or the association does not exist, this call
217: * has no effect.
218: * @return true if the key/value pair existed in the map prior to removal
219: */
220: public synchronized boolean remove(T1 key, T2 value) {
221: Set<T2> values = _forward.get(key);
222: if (values == null) {
223: assert checkIntegrity();
224: return false;
225: }
226: boolean removed = values.remove(value);
227: if (values.isEmpty()) {
228: _forward.remove(key);
229: }
230: if (removed) {
231: _dirty = true;
232: // it existed, so we need to remove from reverse map as well
233: Set<T1> keys = _reverse.get(value);
234: keys.remove(key);
235: if (keys.isEmpty()) {
236: _reverse.remove(value);
237: }
238: }
239: assert checkIntegrity();
240: return removed;
241: }
242:
243: /**
244: * Remove the key and its associated key/value entries.
245: * Calling removeKey(k) is equivalent to calling remove(k,v)
246: * for every v in getValues(k).
247: * @return true if the key existed in the map prior to removal
248: */
249: public synchronized boolean removeKey(T1 key) {
250: // Remove all back-references to key.
251: Set<T2> values = _forward.get(key);
252: if (null == values) {
253: // key does not exist in map.
254: assert checkIntegrity();
255: return false;
256: }
257: for (T2 value : values) {
258: Set<T1> keys = _reverse.get(value);
259: if (null != keys) {
260: keys.remove(key);
261: if (keys.isEmpty()) {
262: _reverse.remove(value);
263: }
264: }
265: }
266: // Now remove the forward references from key.
267: _forward.remove(key);
268: _dirty = true;
269: assert checkIntegrity();
270: return true;
271: }
272:
273: /**
274: * Remove the value and its associated key/value entries.
275: * Calling removeValue(v) is equivalent to calling remove(k,v)
276: * for every k in getKeys(v).
277: * @return true if the value existed in the map prior to removal.
278: */
279: public synchronized boolean removeValue(T2 value) {
280: // Remove any forward references to value
281: Set<T1> keys = _reverse.get(value);
282: if (null == keys) {
283: // value does not exist in map.
284: assert checkIntegrity();
285: return false;
286: }
287: for (T1 key : keys) {
288: Set<T2> values = _forward.get(key);
289: if (null != values) {
290: values.remove(value);
291: if (values.isEmpty()) {
292: _forward.remove(key);
293: }
294: }
295: }
296: // Now remove the reverse references from value.
297: _reverse.remove(value);
298: _dirty = true;
299: assert checkIntegrity();
300: return true;
301: }
302:
303: /**
304: * Check whether <code>value</code> has an association from any keys other
305: * than <code>key</code> - that is, whether the same value has been added
306: * with multiple keys. Equivalent to asking whether the intersection of
307: * <code>getKeys(value)</code> and the set containing <code>key</code> is
308: * non-empty.
309: * @return true iff <code>value</code> is in the map and is associated
310: * with keys other than <code>key</code>.
311: * @see #keyHasOtherValues(Object, Object)
312: */
313: public synchronized boolean valueHasOtherKeys(T2 value, T1 key) {
314: Set<T1> keys = _reverse.get(key);
315: if (keys == null)
316: return false;
317: int size = keys.size();
318: if (size == 0)
319: return false;
320: else if (size > 1)
321: return true;
322: else
323: // size == 1
324: return !keys.contains(key);
325: }
326:
327: /**
328: * Check the integrity of the internal data structures. This is intended to
329: * be called within an assert, so that if asserts are disabled the integrity
330: * checks will not cause a performance impact.
331: * @return true if everything is okay.
332: * @throws IllegalStateException if there is a problem.
333: */
334: private boolean checkIntegrity() {
335: // For every T1->T2 mapping in the forward map, there should be a corresponding
336: // T2->T1 mapping in the reverse map.
337: for (Map.Entry<T1, Set<T2>> entry : _forward.entrySet()) {
338: Set<T2> values = entry.getValue();
339: if (values.isEmpty()) {
340: throw new IllegalStateException(
341: "Integrity compromised: forward map contains an empty set"); //$NON-NLS-1$
342: }
343: for (T2 value : values) {
344: Set<T1> keys = _reverse.get(value);
345: if (null == keys || !keys.contains(entry.getKey())) {
346: throw new IllegalStateException(
347: "Integrity compromised: forward map contains an entry missing from reverse map: " + value); //$NON-NLS-1$
348: }
349: }
350: }
351: // And likewise in the other direction.
352: for (Map.Entry<T2, Set<T1>> entry : _reverse.entrySet()) {
353: Set<T1> keys = entry.getValue();
354: if (keys.isEmpty()) {
355: throw new IllegalStateException(
356: "Integrity compromised: reverse map contains an empty set"); //$NON-NLS-1$
357: }
358: for (T1 key : keys) {
359: Set<T2> values = _forward.get(key);
360: if (null == values || !values.contains(entry.getKey())) {
361: throw new IllegalStateException(
362: "Integrity compromised: reverse map contains an entry missing from forward map: " + key); //$NON-NLS-1$
363: }
364: }
365: }
366: return true;
367: }
368:
369: }
|