ManyToMany


1   /*******************************************************************************
2    * Copyright (c) 2006, 2007 BEA Systems, Inc.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *    wharley@bea.com - initial API and implementation 
10   *                      (originally in org.eclipse.jdt.apt.core)
11   *******************************************************************************/
12  package org.eclipse.jdt.internal.compiler.apt.util;
13  
14  import java.util.Collections  ;
15  import java.util.HashMap  ;
16  import java.util.HashSet  ;
17  import java.util.Map  ;
18  import java.util.Set  ;
19  
20  /**
21   * Manage a Map<T1, Set<T2>>, with reverse links so that it is possible to
22   * efficiently find all T1s that have a particular T2 associated with them.
23   * Access to the map is synchronized, so that it is possible to read and
24   * write simultaneously from multiple threads.
25   * <p>
26   * The map permits the null value for keys nor for value elements. 
27   * <p>
28   * Design invariants preserved by all operations on this map are as follows:
29   * <ul>
30   * <li> If a key exists, it has at least one value associated with it; that is,
31   * for all k such that null != containsKey(k), getValues(k) returns a non-empty
32   * set.</li>
33   * <li> If a value exists, it has at least one key associated with it; that is,
34   * for all v such that null != containsValue(v), getKeys(v) returns a non-empty
35   * set.</li>
36   */
37  public class ManyToMany<T1, T2> {
38      
39      private final Map  <T1, Set  <T2>> _forward = new HashMap  <T1, Set  <T2>>();
40      private final Map  <T2, Set  <T1>> _reverse = new HashMap  <T2, Set  <T1>>();
41      private boolean _dirty = false;
42      
43      /**
44       * Empty all maps.  If the maps previously contained entries, 
45       * this will set the dirty bit.
46       * @return true if the maps contained any entries prior to being cleared
47       */
48      public synchronized boolean clear() {
49          boolean hadContent = !_forward.isEmpty() || !_reverse.isEmpty();
50          _reverse.clear();
51          _forward.clear();
52          _dirty |= hadContent;
53          return hadContent;
54      }
55      
56      /**
57       * Sets the dirty bit to false.  Internal operations do not use the dirty 
58       * bit; clearing it will not affect behavior of the map.  It's just there
59       * for the convenience of callers who don't want to keep track of every
60       * put() and remove().
61       */
62      public synchronized void clearDirtyBit() {
63          _dirty = false;
64      }
65      
66      /**
67       * Equivalent to keySet().contains(key).
68       * @return true if the map contains the specified key.
69       */
70      public synchronized boolean containsKey(T1 key) {
71          return _forward.containsKey(key);
72      }
73      
74      /**
75       * Is there a key that is mapped to the specified value?
76       * Search within the forward map.
77       * @return true if such a key exists
78       */
79      public synchronized boolean containsKeyValuePair(T1 key, T2 value) {
80          Set  <T2> values = _forward.get(key);
81          if (null == values) {
82              return false;
83          }
84          return values.contains(value);
85      }
86      
87      /**
88       * Equivalent to values().contains(value).
89       * @return true if the map contains the specified value (regardless
90       * of what key it might be associated with).
91       */
92      public synchronized boolean containsValue(T2 value) {
93          return _reverse.containsKey(value);
94      }
95      
96      /**
97       * Search the reverse map for all keys that have been associated with
98       * a particular value.
99       * @return the set of keys that are associated with the specified value,
100      * or an empty set if the value does not exist in the map.
101      */
102     public synchronized Set  <T1> getKeys(T2 value) {
103         Set  <T1> keys = _reverse.get(value);
104         if (null == keys) {
105             return Collections.emptySet();
106         }
107         return new HashSet  <T1>(keys);
108     }
109     
110     /**
111      * Search the forward map for all values associated with a particular key.
112      * Returns a copy of the set of values.
113      * @return a copy of the set of values that are associated with the 
114      * specified key, or an empty set if the key does not exist in the map.
115      */
116     public synchronized Set  <T2> getValues(T1 key) {
117         Set  <T2> values = _forward.get(key);
118         if (null == values) {
119             return Collections.emptySet();
120         }
121         return new HashSet  <T2>(values);
122     }
123 
124     /**
125      * @return a copy of the set of all keys (that is, all items of type T1).
126      * If the maps are empty, the returned set will be empty, not null.  The
127      * returned set can be modified by the caller without affecting the map.
128      * @see #getValueSet()
129      */
130     public synchronized Set  <T1> getKeySet() {
131         Set  <T1> keys = new HashSet  <T1>(_forward.keySet());
132         return keys;
133     }
134     
135     /**
136      * @return a copy of the set of all values (that is, all items of type T2).
137      * If the maps are empty, the returned set will be empty, not null.  The
138      * returned set can be modified by the caller without affecting the map.
139      * @see #getKeySet()
140      */
141     public synchronized Set  <T2> getValueSet() {
142         Set  <T2> values = new HashSet  <T2>(_reverse.keySet());
143         return values;
144     }
145     
146     /**
147      * Return the state of the dirty bit.  All operations that change the state
148      * of the maps, including @see #clear(), set the dirty bit if any content actually
149      * changed.  The only way to clear the dirty bit is to call @see #clearDirtyBit().
150      * @return true if the map content has changed since it was created or since
151      * the last call to clearDirtyBit().
152      * @see #clearDirtyBit()
153      */
154     public synchronized boolean isDirty() {
155         return _dirty;
156     }
157     
158     /**
159      * Check whether <code>key</code> has an association to any values other
160      * than <code>value</code> - that is, whether the same key has been added
161      * with multiple values.  Equivalent to asking whether the intersection of
162      * <code>getValues(key)</code> and the set containing <code>value</code> is 
163      * non-empty. 
164      * @return true iff <code>key</code> is in the map and is associated 
165      * with values other than <code>value</code>. 
166      * @see #valueHasOtherKeys(Object, Object)
167      */
168     public synchronized boolean keyHasOtherValues(T1 key, T2 value) {
169         Set  <T2> values = _forward.get(key);
170         if (values == null)
171             return false;
172         int size = values.size();
173         if (size == 0)
174             return false;
175         else if (size > 1)
176             return true;
177         else // 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 // size == 1
323             return !keys.contains(key);
324     }
325 
326     /**
327      * Check the integrity of the internal data structures.  This is intended to
328      * be called within an assert, so that if asserts are disabled the integrity
329      * checks will not cause a performance impact.
330      * @return true if everything is okay.
331      * @throws IllegalStateException if there is a problem.
332      */
333     private boolean checkIntegrity() {
334         // For every T1->T2 mapping in the forward map, there should be a corresponding
335         // T2->T1 mapping in the reverse map.
336         for (Map.Entry  <T1, Set  <T2>> entry : _forward.entrySet()) {
337             Set  <T2> values = entry.getValue();
338             if (values.isEmpty()) {
339                 throw new IllegalStateException  ("Integrity compromised: forward map contains an empty set"); //$NON-NLS-1$
340             }
341             for (T2 value : values) {
342                 Set  <T1> keys = _reverse.get(value);
343                 if (null == keys || !keys.contains(entry.getKey())) {
344                     throw new IllegalStateException  ("Integrity compromised: forward map contains an entry missing from reverse map: " + value); //$NON-NLS-1$
345                 }
346             }
347         }
348         // And likewise in the other direction.
349         for (Map.Entry  <T2, Set  <T1>> entry : _reverse.entrySet()) {
350             Set  <T1> keys = entry.getValue();
351             if (keys.isEmpty()) {
352                 throw new IllegalStateException  ("Integrity compromised: reverse map contains an empty set"); //$NON-NLS-1$
353             }
354             for (T1 key : keys) {
355                 Set  <T2> values = _forward.get(key);
356                 if (null == values || !values.contains(entry.getKey())) {
357                     throw new IllegalStateException  ("Integrity compromised: reverse map contains an entry missing from forward map: " + key); //$NON-NLS-1$
358                 }
359             }
360         }
361         return true;
362     }
363 
364 }
365
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags