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