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