Java > Open Source Codes > org > apache > commons > collections > bidimap > AbstractDualBidiMap


1 /*
2  * Copyright 2003-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.bidimap;
17
18 import java.util.Collection ;
19 import java.util.Iterator ;
20 import java.util.Map ;
21 import java.util.Set ;
22
23 import org.apache.commons.collections.BidiMap;
24 import org.apache.commons.collections.MapIterator;
25 import org.apache.commons.collections.ResettableIterator;
26 import org.apache.commons.collections.collection.AbstractCollectionDecorator;
27 import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
28 import org.apache.commons.collections.keyvalue.AbstractMapEntryDecorator;
29
30 /**
31  * Abstract <code>BidiMap</code> implemented using two maps.
32  * <p>
33  * An implementation can be written simply by implementing the
34  * <code>createMap</code> method.
35  *
36  * @see DualHashBidiMap
37  * @see DualTreeBidiMap
38  * @since Commons Collections 3.0
39  * @version $Id: AbstractDualBidiMap.java,v 1.14 2004/06/22 21:54:35 scolebourne Exp $
40  *
41  * @author Matthew Hawthorne
42  * @author Stephen Colebourne
43  */
44 public abstract class AbstractDualBidiMap implements BidiMap {
45
46     /**
47      * Delegate map array. The first map contains standard entries, and the
48      * second contains inverses.
49      */
50     protected transient final Map [] maps = new Map [2];
51     /**
52      * Inverse view of this map.
53      */
54     protected transient BidiMap inverseBidiMap = null;
55     /**
56      * View of the keys.
57      */
58     protected transient Set keySet = null;
59     /**
60      * View of the values.
61      */
62     protected transient Collection values = null;
63     /**
64      * View of the entries.
65      */
66     protected transient Set entrySet = null;
67
68     /**
69      * Creates an empty map, initialised by <code>createMap</code>.
70      * <p>
71      * This constructor remains in place for deserialization.
72      * All other usage is deprecated in favour of
73      * {@link #AbstractDualBidiMap(Map, Map)}.
74      */
75     protected AbstractDualBidiMap() {
76         super();
77         maps[0] = createMap();
78         maps[1] = createMap();
79     }
80
81     /**
82      * Creates an empty map using the two maps specified as storage.
83      * <p>
84      * The two maps must be a matching pair, normal and reverse.
85      * They will typically both be empty.
86      * <p>
87      * Neither map is validated, so nulls may be passed in.
88      * If you choose to do this then the subclass constructor must populate
89      * the <code>maps[]</code> instance variable itself.
90      *
91      * @param normalMap the normal direction map
92      * @param reverseMap the reverse direction map
93      * @since Commons Collections 3.1
94      */
95     protected AbstractDualBidiMap(Map normalMap, Map reverseMap) {
96         super();
97         maps[0] = normalMap;
98         maps[1] = reverseMap;
99     }
100
101     /**
102      * Constructs a map that decorates the specified maps,
103      * used by the subclass <code>createBidiMap</code> implementation.
104      *
105      * @param normalMap the normal direction map
106      * @param reverseMap the reverse direction map
107      * @param inverseBidiMap the inverse BidiMap
108      */
109     protected AbstractDualBidiMap(Map normalMap, Map reverseMap, BidiMap inverseBidiMap) {
110         super();
111         maps[0] = normalMap;
112         maps[1] = reverseMap;
113         this.inverseBidiMap = inverseBidiMap;
114     }
115
116     /**
117      * Creates a new instance of the map used by the subclass to store data.
118      * <p>
119      * This design is deeply flawed and has been deprecated.
120      * It relied on subclass data being used during a superclass constructor.
121      *
122      * @return the map to be used for internal storage
123      * @deprecated For constructors, use the new two map constructor.
124      * For deserialization, populate the maps array directly in readObject.
125      */
126     protected Map createMap() {
127         return null;
128     }
129
130     /**
131      * Creates a new instance of the subclass.
132      *
133      * @param normalMap the normal direction map
134      * @param reverseMap the reverse direction map
135      * @param inverseMap this map, which is the inverse in the new map
136      * @return the inverse map
137      */
138     protected abstract BidiMap createBidiMap(Map normalMap, Map reverseMap, BidiMap inverseMap);
139
140     // Map delegation
141 //-----------------------------------------------------------------------
142 public Object get(Object key) {
143         return maps[0].get(key);
144     }
145
146     public int size() {
147         return maps[0].size();
148     }
149
150     public boolean isEmpty() {
151         return maps[0].isEmpty();
152     }
153
154     public boolean containsKey(Object key) {
155         return maps[0].containsKey(key);
156     }
157
158     public boolean equals(Object obj) {
159         return maps[0].equals(obj);
160     }
161
162     public int hashCode() {
163         return maps[0].hashCode();
164     }
165
166     public String toString() {
167         return maps[0].toString();
168     }
169
170     // BidiMap changes
171 //-----------------------------------------------------------------------
172 public Object put(Object key, Object value) {
173         if (maps[0].containsKey(key)) {
174             maps[1].remove(maps[0].get(key));
175         }
176         if (maps[1].containsKey(value)) {
177             maps[0].remove(maps[1].get(value));
178         }
179         final Object obj = maps[0].put(key, value);
180         maps[1].put(value, key);
181         return obj;
182     }
183     
184     public void putAll(Map map) {
185         for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
186             Map.Entry entry = (Map.Entry ) it.next();
187             put(entry.getKey(), entry.getValue());
188         }
189     }
190
191     public Object remove(Object key) {
192         Object value = null;
193         if (maps[0].containsKey(key)) {
194             value = maps[0].remove(key);
195             maps[1].remove(value);
196         }
197         return value;
198     }
199
200     public void clear() {
201         maps[0].clear();
202         maps[1].clear();
203     }
204
205     public boolean containsValue(Object value) {
206         return maps[1].containsKey(value);
207     }
208
209     // BidiMap
210 //-----------------------------------------------------------------------
211 /**
212      * Obtains a <code>MapIterator</code> over the map.
213      * The iterator implements <code>ResetableMapIterator</code>.
214      * This implementation relies on the entrySet iterator.
215      * <p>
216      * The setValue() methods only allow a new value to be set.
217      * If the value being set is already in the map, an IllegalArgumentException
218      * is thrown (as setValue cannot change the size of the map).
219      *
220      * @return a map iterator
221      */
222     public MapIterator mapIterator() {
223         return new BidiMapIterator(this);
224     }
225     
226     public Object getKey(Object value) {
227         return maps[1].get(value);
228     }
229
230     public Object removeValue(Object value) {
231         Object key = null;
232         if (maps[1].containsKey(value)) {
233             key = maps[1].remove(value);
234             maps[0].remove(key);
235         }
236         return key;
237     }
238
239     public BidiMap inverseBidiMap() {
240         if (inverseBidiMap == null) {
241             inverseBidiMap = createBidiMap(maps[1], maps[0], this);
242         }
243         return inverseBidiMap;
244     }
245     
246     // Map views
247 //-----------------------------------------------------------------------
248 /**
249      * Gets a keySet view of the map.
250      * Changes made on the view are reflected in the map.
251      * The set supports remove and clear but not add.
252      *
253      * @return the keySet view
254      */
255     public Set keySet() {
256         if (keySet == null) {
257             keySet = new KeySet(this);
258         }
259         return keySet;
260     }
261
262     /**
263      * Creates a key set iterator.
264      * Subclasses can override this to return iterators with different properties.
265      *
266      * @param iterator the iterator to decorate
267      * @return the keySet iterator
268      */
269     protected Iterator createKeySetIterator(Iterator iterator) {
270         return new KeySetIterator(iterator, this);
271     }
272
273     /**
274      * Gets a values view of the map.
275      * Changes made on the view are reflected in the map.
276      * The set supports remove and clear but not add.
277      *
278      * @return the values view
279      */
280     public Collection values() {
281         if (values == null) {
282             values = new Values(this);
283         }
284         return values;
285     }
286
287     /**
288      * Creates a values iterator.
289      * Subclasses can override this to return iterators with different properties.
290      *
291      * @param iterator the iterator to decorate
292      * @return the values iterator
293      */
294     protected Iterator createValuesIterator(Iterator iterator) {
295         return new ValuesIterator(iterator, this);
296     }
297
298     /**
299      * Gets an entrySet view of the map.
300      * Changes made on the set are reflected in the map.
301      * The set supports remove and clear but not add.
302      * <p>
303      * The Map Entry setValue() method only allow a new value to be set.
304      * If the value being set is already in the map, an IllegalArgumentException
305      * is thrown (as setValue cannot change the size of the map).
306      *
307      * @return the entrySet view
308      */
309     public Set entrySet() {
310         if (entrySet == null) {
311             entrySet = new EntrySet(this);
312         }
313         return entrySet;
314     }
315     
316     /**
317      * Creates an entry set iterator.
318      * Subclasses can override this to return iterators with different properties.
319      *
320      * @param iterator the iterator to decorate
321      * @return the entrySet iterator
322      */
323     protected Iterator createEntrySetIterator(Iterator iterator) {
324         return new EntrySetIterator(iterator, this);
325     }
326
327     //-----------------------------------------------------------------------
328 /**
329      * Inner class View.
330      */
331     protected static abstract class View extends AbstractCollectionDecorator {
332         
333         /** The parent map */
334         protected final AbstractDualBidiMap parent;
335         
336         /**
337          * Constructs a new view of the BidiMap.
338          *
339          * @param coll the collection view being decorated
340          * @param parent the parent BidiMap
341          */
342         protected View(Collection coll, AbstractDualBidiMap parent) {
343             super(coll);
344             this.parent = parent;
345         }
346
347         public boolean removeAll(Collection coll) {
348             if (parent.isEmpty() || coll.isEmpty()) {
349                 return false;
350             }
351             boolean modified = false;
352             Iterator it = iterator();
353             while (it.hasNext()) {
354                 if (coll.contains(it.next())) {
355                     it.remove();
356                     modified = true;
357                 }
358             }
359             return modified;
360         }
361
362         public boolean retainAll(Collection coll) {
363             if (parent.isEmpty()) {
364                 return false;
365             }
366             if (coll.isEmpty()) {
367                 parent.clear();
368                 return true;
369             }
370             boolean modified = false;
371             Iterator it = iterator();
372             while (it.hasNext()) {
373                 if (coll.contains(it.next()) == false) {
374                     it.remove();
375                     modified = true;
376                 }
377             }
378             return modified;
379         }
380         
381         public void clear() {
382             parent.clear();
383         }
384     }
385     
386     //-----------------------------------------------------------------------
387 /**
388      * Inner class KeySet.
389      */
390     protected static class KeySet extends View implements Set {
391         
392         /**
393          * Constructs a new view of the BidiMap.
394          *
395          * @param parent the parent BidiMap
396          */
397         protected KeySet(AbstractDualBidiMap parent) {
398             super(parent.maps[0].keySet(), parent);
399         }
400
401         public Iterator iterator() {
402             return parent.createKeySetIterator(super.iterator());
403         }
404         
405         public boolean contains(Object key) {
406             return parent.maps[0].containsKey(key);
407         }
408
409         public boolean remove(Object key) {
410             if (parent.maps[0].containsKey(key)) {
411                 Object value = parent.maps[0].remove(key);
412                 parent.maps[1].remove(value);
413                 return true;
414             }
415             return false;
416         }
417     }
418     
419     /**
420      * Inner class KeySetIterator.
421      */
422     protected static class KeySetIterator extends AbstractIteratorDecorator {
423         
424         /** The parent map */
425         protected final AbstractDualBidiMap parent;
426         /** The last returned key */
427         protected Object lastKey = null;
428         /** Whether remove is allowed at present */
429         protected boolean canRemove = false;
430         
431         /**
432          * Constructor.
433          * @param iterator the iterator to decorate
434          * @param parent the parent map
435          */
436         protected KeySetIterator(Iterator iterator, AbstractDualBidiMap parent) {
437             super(iterator);
438             this.parent = parent;
439         }
440         
441         public Object next() {
442             lastKey = super.next();
443             canRemove = true;
444             return lastKey;
445         }
446         
447         public void remove() {
448             if (canRemove == false) {
449                 throw new IllegalStateException ("Iterator remove() can only be called once after next()");
450             }
451             Object value = parent.maps[0].get(lastKey);
452             super.remove();
453             parent.maps[1].remove(value);
454             lastKey = null;
455             canRemove = false;
456         }
457     }
458
459     //-----------------------------------------------------------------------
460 /**
461      * Inner class Values.
462      */
463     protected static class Values extends View implements Set {
464         
465         /**
466          * Constructs a new view of the BidiMap.
467          *
468          * @param parent the parent BidiMap
469          */
470         protected Values(AbstractDualBidiMap parent) {
471             super(parent.maps[0].values(), parent);
472         }
473
474         public Iterator iterator() {
475             return parent.createValuesIterator(super.iterator());
476         }
477         
478         public boolean contains(Object value) {
479             return parent.maps[1].containsKey(value);
480         }
481
482         public boolean remove(Object value) {
483             if (parent.maps[1].containsKey(value)) {
484                 Object key = parent.maps[1].remove(value);
485                 parent.maps[0].remove(key);
486                 return true;
487             }
488             return false;
489         }
490     }
491     
492     /**
493      * Inner class ValuesIterator.
494      */
495     protected static class ValuesIterator extends AbstractIteratorDecorator {
496         
497         /** The parent map */
498         protected final AbstractDualBidiMap parent;
499         /** The last returned value */
500         protected Object lastValue = null;
501         /** Whether remove is allowed at present */
502         protected boolean canRemove = false;
503         
504         /**
505          * Constructor.
506          * @param iterator the iterator to decorate
507          * @param parent the parent map
508          */
509         protected ValuesIterator(Iterator iterator, AbstractDualBidiMap parent) {
510             super(iterator);
511             this.parent = parent;
512         }
513         
514         public Object next() {
515             lastValue = super.next();
516             canRemove = true;
517             return lastValue;
518         }
519         
520         public void remove() {
521             if (canRemove == false) {
522                 throw new IllegalStateException ("Iterator remove() can only be called once after next()");
523             }
524             super.remove(); // removes from maps[0]
525 parent.maps[1].remove(lastValue);
526             lastValue = null;
527             canRemove = false;
528         }
529     }
530
531     //-----------------------------------------------------------------------
532 /**
533      * Inner class EntrySet.
534      */
535     protected static class EntrySet extends View implements Set {
536         
537         /**
538          * Constructs a new view of the BidiMap.
539          *
540          * @param parent the parent BidiMap
541          */
542         protected EntrySet(AbstractDualBidiMap parent) {
543             super(parent.maps[0].entrySet(), parent);
544         }
545
546         public Iterator iterator() {
547             return parent.createEntrySetIterator(super.iterator());
548         }
549         
550         public boolean remove(Object obj) {
551             if (obj instanceof Map.Entry == false) {
552                 return false;
553             }
554             Map.Entry entry = (Map.Entry ) obj;
555             Object key = entry.getKey();
556             if (parent.containsKey(key)) {
557                 Object value = parent.maps[0].get(key);
558                 if (value == null ? entry.getValue() == null : value.equals(entry.getValue())) {
559                     parent.maps[0].remove(key);
560                     parent.maps[1].remove(value);
561                     return true;
562                 }
563             }
564             return false;
565         }
566     }
567     
568     /**
569      * Inner class EntrySetIterator.
570      */
571     protected static class EntrySetIterator extends AbstractIteratorDecorator {
572         
573         /** The parent map */
574         protected final AbstractDualBidiMap parent;
575         /** The last returned entry */
576         protected Map.Entry last = null;
577         /** Whether remove is allowed at present */
578         protected boolean canRemove = false;
579         
580         /**
581          * Constructor.
582          * @param iterator the iterator to decorate
583          * @param parent the parent map
584          */
585         protected EntrySetIterator(Iterator iterator, AbstractDualBidiMap parent) {
586             super(iterator);
587             this.parent = parent;
588         }
589         
590         public Object next() {
591             last = new MapEntry((Map.Entry ) super.next(), parent);
592             canRemove = true;
593             return last;
594         }
595         
596         public void remove() {
597             if (canRemove == false) {
598                 throw new IllegalStateException ("Iterator remove() can only be called once after next()");
599             }
600             // store value as remove may change the entry in the decorator (eg.TreeMap)
601 Object value = last.getValue();
602             super.remove();
603             parent.maps[1].remove(value);
604             last = null;
605             canRemove = false;
606         }
607     }
608
609     /**
610      * Inner class MapEntry.
611      */
612     protected static class MapEntry extends AbstractMapEntryDecorator {
613
614         /** The parent map */
615         protected final AbstractDualBidiMap parent;
616         
617         /**
618          * Constructor.
619          * @param entry the entry to decorate
620          * @param parent the parent map
621          */
622         protected MapEntry(Map.Entry entry, AbstractDualBidiMap parent) {
623             super(entry);
624             this.parent = parent;
625         }
626         
627         public Object setValue(Object value) {
628             Object key = MapEntry.this.getKey();
629             if (parent.maps[1].containsKey(value) &&
630                 parent.maps[1].get(value) != key) {
631                 throw new IllegalArgumentException ("Cannot use setValue() when the object being set is already in the map");
632             }
633             parent.put(key, value);
634             final Object oldValue = super.setValue(value);
635             return oldValue;
636         }
637     }
638     
639     /**
640      * Inner class MapIterator.
641      */
642     protected static class BidiMapIterator implements MapIterator, ResettableIterator {
643         
644         /** The parent map */
645         protected final AbstractDualBidiMap parent;
646         /** The iterator being wrapped */
647         protected Iterator iterator;
648         /** The last returned entry */
649         protected Map.Entry last = null;
650         /** Whether remove is allowed at present */
651         protected boolean canRemove = false;
652         
653         /**
654          * Constructor.
655          * @param parent the parent map
656          */
657         protected BidiMapIterator(AbstractDualBidiMap parent) {
658             super();
659             this.parent = parent;
660             this.iterator = parent.maps[0].entrySet().iterator();
661         }
662         
663         public boolean hasNext() {
664             return iterator.hasNext();
665         }
666         
667         public Object next() {
668             last = (Map.Entry ) iterator.next();
669             canRemove = true;
670             return last.getKey();
671         }
672         
673         public void remove() {
674             if (canRemove == false) {
675                 throw new IllegalStateException ("Iterator remove() can only be called once after next()");
676             }
677             // store value as remove may change the entry in the decorator (eg.TreeMap)
678 Object value = last.getValue();
679             iterator.remove();
680             parent.maps[1].remove(value);
681             last = null;
682             canRemove = false;
683         }
684         
685         public Object getKey() {
686             if (last == null) {
687                 throw new IllegalStateException ("Iterator getKey() can only be called after next() and before remove()");
688             }
689             return last.getKey();
690         }
691
692         public Object getValue() {
693             if (last == null) {
694                 throw new IllegalStateException ("Iterator getValue() can only be called after next() and before remove()");
695             }
696             return last.getValue();
697         }
698         
699         public Object setValue(Object value) {
700             if (last == null) {
701                 throw new IllegalStateException ("Iterator setValue() can only be called after next() and before remove()");
702             }
703             if (parent.maps[1].containsKey(value) &&
704                 parent.maps[1].get(value) != last.getKey()) {
705                 throw new IllegalArgumentException ("Cannot use setValue() when the object being set is already in the map");
706             }
707             return parent.put(last.getKey(), value);
708         }
709         
710         public void reset() {
711             iterator = parent.maps[0].entrySet().iterator();
712             last = null;
713             canRemove = false;
714         }
715         
716         public String toString() {
717             if (last != null) {
718                 return "MapIterator[" + getKey() + "=" + getValue() + "]";
719             } else {
720                 return "MapIterator[]";
721             }
722         }
723     }
724     
725 }
726

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags