ManyToMany


1   /*******************************************************************************
2    * Copyright (c) 2006 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   *******************************************************************************/
11  package org.eclipse.jdt.apt.core.internal.util;
12  
13  import java.util.Collections  ;
14  import java.util.HashMap  ;
15  import java.util.HashSet  ;
16  import java.util.Map  ;
17  import java.util.Set  ;
18  
19  /**
20   * Manage a Map<T1, Set<T2>>, with reverse links so that it is possible to
21   * efficiently find all T1s that have a particular T2 associated with them.
22   * Access to the map is synchronized, so that it is possible to read and
23   * write simultaneously from multiple threads.  Set semantics are preserved
24   * in both directions, so there is no distinction between calling this a
25   * Map<T1, Set<T2>> versus a Map<T2, Set<T1>>.  It is symmetric.
26   * <p>
27   * The map permits the null value for keys and for value elements. 
28   * <p>
29   * Design invariants preserved by all operations on this map are as follows:
30   * <ul>
31   * <li> If a key exists, it has at least one value associated with it; that is,
32   * for all k such that null != containsKey(k), getValues(k) returns a non-empty
33   * set.</li>
34   * <li> If a value exists, it has at least one key associated with it; that is,
35   * for all v such that null != containsValue(v), getKeys(v) returns a non-empty
36   * set.</li>
37   */
38  public class ManyToMany<T1, T2> {
39      
40      private final Map  <T1, Set  <T2>> _forward = new HashMap  <T1, Set  <T2>>();
41      private final Map  <T2, Set  <T1>> _reverse = new HashMap  <T2, Set  <T1>>();
42      private boolean _dirty = false;
43      
44      /**
45       * Empty all maps.  If the maps previously contained entries, 
46       * this will set the dirty bit.
47       * @return true if the maps contained any entries prior to being cleared
48       */
49      public synchronized boolean clear() {
50          boolean hadContent = !_forward.isEmpty() || !_reverse.isEmpty();
51          _reverse.clear();
52          _forward.clear();
53          _dirty |= hadContent;
54          return hadContent;
55      }
56      
57      /**
58       * Sets the dirty bit to false.  Internal operations do not use the dirty 
59       * bit; clearing it will not affect behavior of the map.  It's just there
60       * for the convenience of callers who don't want to keep track of every
61       * put() and remove().
62       */
63      public synchronized void clearDirtyBit() {
64          _dirty = false;
65      }
66      
67      /**
68       * Equivalent to keySet().contains(key).
69       * @return true if the map contains the specified key.
70       */
71      public synchronized boolean containsKey(T1 key) {
72          return _forward.containsKey(key);
73      }
74      
75      /**
76       * Is there a key that is mapped to the specified value?
77       * Search within the forward map.
78       * @return true if such a key exists
79       */
80      public synchronized boolean containsKeyValuePair(T1 key, T2 value) {
81          Set  <T2> values = _forward.get(key);
82          if (null == values) {
83              return false;
84          }
85          return values.contains(value);
86      }
87      
88      /**
89       * Equivalent to values().contains(value).
90       * @return true if the map contains the specified value (regardless
91       * of what key it might be associated with).
92       */
93      public synchronized boolean containsValue(T2 value) {
94          return _reverse.containsKey(value);
95      }
96      
97      /**
98       * Search the reverse map for all keys that have been associated with
99       * a particular value.
100      * @return the set of keys that are associated with the specified value,
101      * or an empty set if the value does not exist in the map.
102      */
103     public synchronized Set  <T1> getKeys(T2 value) {
104         Set  <T1> keys = _reverse.get(value);
105         if (null == keys) {
106             return Collections.emptySet();
107         }
108         return new HashSet  <T1>(keys);
109     }
110     
111     /**
112      * Search the forward map for all values associated with a particular key.
113      * Returns a copy of the set of values.
114      * @return a copy of the set of values that are associated with the 
115      * specified key, or an empty set if the key does not exist in the map.
116      */
117     public synchronized Set  <T2> getValues(T1 key) {
118         Set  <T2> values = _forward.get(key);
119         if (null == values) {
120             return Collections.emptySet();
121         }
122         return new HashSet  <T2>(values);
123     }
124 
125     /**
126      * @return a copy of the set of all keys (that is, all items of type T1).
127      * If the maps are empty, the returned set will be empty, not null.  The
128      * returned set can be modified by the caller without affecting the map.
129      * @see #getValueSet()
130      */
131     public synchronized Set  <T1> getKeySet() {
132         Set  <T1> keys = new HashSet  <T1>(_forward.keySet());
133         return keys;
134     }
135     
136     /**
137      * @return a copy of the set of all values (that is, all items of type T2).
138      * If the maps are empty, the returned set will be empty, not null.  The
139      * returned set can be modified by the caller without affecting the map.
140      * @see #getKeySet()
141      */
142     public synchronized Set  <T2> getValueSet() {
143         Set  <T2> values = new HashSet  <T2>(_reverse.keySet());
144         return values;
145     }
146     
147     /**
148      * Return the state of the dirty bit.  All operations that change the state
149      * of the maps, including @see #clear(), set the dirty bit if any content actually
150      * changed.  The only way to clear the dirty bit is to call @see #clearDirtyBit().
151      * @return true if the map content has changed since it was created or since
152      * the last call to clearDirtyBit().
153      * @see #clearDirtyBit()
154      */
155     public synchronized boolean isDirty() {
156         return _dirty;
157     }
158     
159     /**
160      * Check whether <code>key</code> has an association to any values other
161      * than <code>value</code> - that is, whether the same key has been added
162      * with multiple values.  Equivalent to asking whether the intersection of
163      * <code>getValues(key)</code> and the set containing <code>value</code> is 
164      * non-empty. 
165      * @return true iff <code>key</code> is in the map and is associated 
166      * with values other than <code>value</code>. 
167      * @see #valueHasOtherKeys(Object, Object)
168      */
169     public synchronized boolean keyHasOtherValues(T1 key, T2 value) {
170         Set  <T2> values = _forward.get(key);
171         if (values == null)
172             return false;
173         int size = values.size();
174         if (size == 0)
175             return false;
176         else if (size > 1)
177             return true;
178         else // size == 1
179             return !values.contains(value);
180     }
181 
182     /**
183      * Associate the specified value with the key.  Adds the entry
184      * to both the forward and reverse maps.  Adding the same value
185      * twice to a particular key has no effect.  Because this is a
186      * many-to-many map, adding a new value for an existing key does
187      * not change the existing association, it adds a new one.
188      * @param key can be null
189      * @param value can be null
190      * @return true if the key/value pair did not exist prior to being added
191      */
192     public synchronized boolean put(T1 key, T2 value) {
193         // Add to forward map
194         Set  <T2> values = _forward.get(key);
195         if (null == values) {
196             values = new HashSet  <T2>();
197             _forward.put(key, values);
198         }
199         boolean added = values.add(value);
200         _dirty |= added;
201         
202         // Add to reverse map
203         Set  <T1> keys = _reverse.get(value);
204         if (null == keys) {
205             keys = new HashSet  <T1>();
206             _reverse.put(value, keys);
207         }
208         keys.add(key);
209         
210         assert checkIntegrity();
211         return added;
212     }
213     
214     /**
215      * Remove a particular key-value association.  This is the inverse
216      * of put(key, value).  If the key does not exist, or the value
217      * does not exist, or the association does not exist, this call
218      * has no effect.
219      * @return true if the key/value pair existed in the map prior to removal
220      */
221     public synchronized boolean remove(T1 key, T2 value) {
222         Set  <T2> values = _forward.get(key);
223         if (values == null) {
224             assert checkIntegrity();
225             return false;
226         }
227         boolean removed = values.remove(value);
228         if (values.isEmpty()) {
229             _forward.remove(key);
230         }
231         if (removed) {
232             _dirty = true;
233             // it existed, so we need to remove from reverse map as well
234             Set  <T1> keys = _reverse.get(value);
235             keys.remove(key);
236             if (keys.isEmpty()) {
237                 _reverse.remove(value);
238             }
239         }
240         assert checkIntegrity();
241         return removed;
242     }
243 
244     /**
245      * Remove the key and its associated key/value entries.
246      * Calling removeKey(k) is equivalent to calling remove(k,v) 
247      * for every v in getValues(k).
248      * @return true if the key existed in the map prior to removal
249      */
250     public synchronized boolean removeKey(T1 key) {
251         // Remove all back-references to key.
252         Set  <T2> values = _forward.get(key);
253         if (null == values) {
254             // key does not exist in map.
255             assert checkIntegrity();
256             return false;
257         }
258         for (T2 value : values) {
259             Set  <T1> keys = _reverse.get(value);
260             if (null != keys) {
261                 keys.remove(key);
262                 if (keys.isEmpty()) {
263                     _reverse.remove(value);
264                 }
265             }
266         }
267         // Now remove the forward references from key.
268         _forward.remove(key);
269         _dirty = true;
270         assert checkIntegrity();
271         return true;
272     }
273     
274     /**
275      * Remove the value and its associated key/value entries.
276      * Calling removeValue(v) is equivalent to calling remove(k,v)
277      * for every k in getKeys(v).
278      * @return true if the value existed in the map prior to removal.
279      */
280     public synchronized boolean removeValue(T2 value) {
281         // Remove any forward references to value
282         Set  <T1> keys = _reverse.get(value);
283         if (null == keys) {
284             // value does not exist in map.
285             assert checkIntegrity();
286             return false;
287         }
288         for (T1 key : keys) {
289             Set  <T2> values = _forward.get(key);
290             if (null != values) {
291                 values.remove(value);
292                 if (values.isEmpty()) {
293                     _forward.remove(key);
294                 }
295             }
296         }
297         // Now remove the reverse references from value.
298         _reverse.remove(value);
299         _dirty = true;
300         assert checkIntegrity();
301         return true;
302     }
303     
304     /**
305      * Check whether <code>value</code> has an association from any keys other
306      * than <code>key</code> - that is, whether the same value has been added
307      * with multiple keys.  Equivalent to asking whether the intersection of
308      * <code>getKeys(value)</code> and the set containing <code>key</code> is 
309      * non-empty. 
310      * @return true iff <code>value</code> is in the map and is associated 
311      * with keys other than <code>key</code>. 
312      * @see #keyHasOtherValues(Object, Object)
313      */
314     public synchronized boolean valueHasOtherKeys(T2 value, T1 key) {
315         Set  <T1> keys = _reverse.get(key);
316         if (keys == null)
317             return false;
318         int size = keys.size();
319         if (size == 0)
320             return false;
321         else if (size > 1)
322             return true;
323         else // 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  ("Integrity compromised: forward map contains an empty set"); //$NON-NLS-1$
341             }
342             for (T2 value : values) {
343                 Set  <T1> keys = _reverse.get(value);
344                 if (null == keys || !keys.contains(entry.getKey())) {
345                     throw new IllegalStateException  ("Integrity compromised: forward map contains an entry missing from reverse map: " + value); //$NON-NLS-1$
346                 }
347             }
348         }
349         // And likewise in the other direction.
350         for (Map.Entry  <T2, Set  <T1>> entry : _reverse.entrySet()) {
351             Set  <T1> keys = entry.getValue();
352             if (keys.isEmpty()) {
353                 throw new IllegalStateException  ("Integrity compromised: reverse map contains an empty set"); //$NON-NLS-1$
354             }
355             for (T1 key : keys) {
356                 Set  <T2> values = _forward.get(key);
357                 if (null == values || !values.contains(entry.getKey())) {
358                     throw new IllegalStateException  ("Integrity compromised: reverse map contains an entry missing from forward map: " + key); //$NON-NLS-1$
359                 }
360             }
361         }
362         return true;
363     }
364 
365 }
366
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags