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 972397 2015-11-14 15:01:49Z 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    @Override
135    public V get(final Object key) {
136        return normalMap.get(key);
137    }
138
139    @Override
140    public int size() {
141        return normalMap.size();
142    }
143
144    @Override
145    public boolean isEmpty() {
146        return normalMap.isEmpty();
147    }
148
149    @Override
150    public boolean containsKey(final Object key) {
151        return normalMap.containsKey(key);
152    }
153
154    @Override
155    public boolean equals(final Object obj) {
156        return normalMap.equals(obj);
157    }
158
159    @Override
160    public int hashCode() {
161        return normalMap.hashCode();
162    }
163
164    @Override
165    public String toString() {
166        return normalMap.toString();
167    }
168
169    // BidiMap changes
170    //-----------------------------------------------------------------------
171
172    @Override
173    public V put(final K key, final V value) {
174        if (normalMap.containsKey(key)) {
175            reverseMap.remove(normalMap.get(key));
176        }
177        if (reverseMap.containsKey(value)) {
178            normalMap.remove(reverseMap.get(value));
179        }
180        final V obj = normalMap.put(key, value);
181        reverseMap.put(value, key);
182        return obj;
183    }
184
185    @Override
186    public void putAll(final Map<? extends K, ? extends V> map) {
187        for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
188            put(entry.getKey(), entry.getValue());
189        }
190    }
191
192    @Override
193    public V remove(final Object key) {
194        V value = null;
195        if (normalMap.containsKey(key)) {
196            value = normalMap.remove(key);
197            reverseMap.remove(value);
198        }
199        return value;
200    }
201
202    @Override
203    public void clear() {
204        normalMap.clear();
205        reverseMap.clear();
206    }
207
208    @Override
209    public boolean containsValue(final Object value) {
210        return reverseMap.containsKey(value);
211    }
212
213    // BidiMap
214    //-----------------------------------------------------------------------
215    /**
216     * Obtains a <code>MapIterator</code> over the map.
217     * The iterator implements <code>ResetableMapIterator</code>.
218     * This implementation relies on the entrySet iterator.
219     * <p>
220     * The setValue() methods only allow a new value to be set.
221     * If the value being set is already in the map, an IllegalArgumentException
222     * is thrown (as setValue cannot change the size of the map).
223     *
224     * @return a map iterator
225     */
226    @Override
227    public MapIterator<K, V> mapIterator() {
228        return new BidiMapIterator<K, V>(this);
229    }
230
231    @Override
232    public K getKey(final Object value) {
233        return reverseMap.get(value);
234    }
235
236    @Override
237    public K removeValue(final Object value) {
238        K key = null;
239        if (reverseMap.containsKey(value)) {
240            key = reverseMap.remove(value);
241            normalMap.remove(key);
242        }
243        return key;
244    }
245
246    @Override
247    public BidiMap<V, K> inverseBidiMap() {
248        if (inverseBidiMap == null) {
249            inverseBidiMap = createBidiMap(reverseMap, normalMap, this);
250        }
251        return inverseBidiMap;
252    }
253
254    // Map views
255    //-----------------------------------------------------------------------
256    /**
257     * Gets a keySet view of the map.
258     * Changes made on the view are reflected in the map.
259     * The set supports remove and clear but not add.
260     *
261     * @return the keySet view
262     */
263    @Override
264    public Set<K> keySet() {
265        if (keySet == null) {
266            keySet = new KeySet<K>(this);
267        }
268        return keySet;
269    }
270
271    /**
272     * Creates a key set iterator.
273     * Subclasses can override this to return iterators with different properties.
274     *
275     * @param iterator  the iterator to decorate
276     * @return the keySet iterator
277     */
278    protected Iterator<K> createKeySetIterator(final Iterator<K> iterator) {
279        return new KeySetIterator<K>(iterator, this);
280    }
281
282    /**
283     * Gets a values view of the map.
284     * Changes made on the view are reflected in the map.
285     * The set supports remove and clear but not add.
286     *
287     * @return the values view
288     */
289    @Override
290    public Set<V> values() {
291        if (values == null) {
292            values = new Values<V>(this);
293        }
294        return values;
295    }
296
297    /**
298     * Creates a values iterator.
299     * Subclasses can override this to return iterators with different properties.
300     *
301     * @param iterator  the iterator to decorate
302     * @return the values iterator
303     */
304    protected Iterator<V> createValuesIterator(final Iterator<V> iterator) {
305        return new ValuesIterator<V>(iterator, this);
306    }
307
308    /**
309     * Gets an entrySet view of the map.
310     * Changes made on the set are reflected in the map.
311     * The set supports remove and clear but not add.
312     * <p>
313     * The Map Entry setValue() method only allow a new value to be set.
314     * If the value being set is already in the map, an IllegalArgumentException
315     * is thrown (as setValue cannot change the size of the map).
316     *
317     * @return the entrySet view
318     */
319    @Override
320    public Set<Map.Entry<K, V>> entrySet() {
321        if (entrySet == null) {
322            entrySet = new EntrySet<K, V>(this);
323        }
324        return entrySet;
325    }
326
327    /**
328     * Creates an entry set iterator.
329     * Subclasses can override this to return iterators with different properties.
330     *
331     * @param iterator  the iterator to decorate
332     * @return the entrySet iterator
333     */
334    protected Iterator<Map.Entry<K, V>> createEntrySetIterator(final Iterator<Map.Entry<K, V>> iterator) {
335        return new EntrySetIterator<K, V>(iterator, this);
336    }
337
338    //-----------------------------------------------------------------------
339    /**
340     * Inner class View.
341     */
342    protected static abstract class View<K, V, E> extends AbstractCollectionDecorator<E> {
343
344        /** Generated serial version ID. */
345        private static final long serialVersionUID = 4621510560119690639L;
346
347        /** The parent map */
348        protected final AbstractDualBidiMap<K, V> parent;
349
350        /**
351         * Constructs a new view of the BidiMap.
352         *
353         * @param coll  the collection view being decorated
354         * @param parent  the parent BidiMap
355         */
356        protected View(final Collection<E> coll, final AbstractDualBidiMap<K, V> parent) {
357            super(coll);
358            this.parent = parent;
359        }
360
361        @Override
362        public boolean equals(final Object object) {
363            return object == this || decorated().equals(object);
364        }
365
366        @Override
367        public int hashCode() {
368            return decorated().hashCode();
369        }
370
371        @Override
372        public boolean removeAll(final Collection<?> coll) {
373            if (parent.isEmpty() || coll.isEmpty()) {
374                return false;
375            }
376            boolean modified = false;
377            final Iterator<?> it = coll.iterator();
378            while (it.hasNext()) {
379                modified |= remove(it.next());
380            }
381            return modified;
382        }
383
384        /**
385         * {@inheritDoc}
386         * <p>
387         * This implementation iterates over the elements of this bidi map, checking each element in
388         * turn to see if it's contained in <code>coll</code>. If it's not contained, it's removed
389         * from this bidi map. As a consequence, it is advised to use a collection type for
390         * <code>coll</code> that provides a fast (e.g. O(1)) implementation of
391         * {@link Collection#contains(Object)}.
392         */
393        @Override
394        public boolean retainAll(final Collection<?> coll) {
395            if (parent.isEmpty()) {
396                return false;
397            }
398            if (coll.isEmpty()) {
399                parent.clear();
400                return true;
401            }
402            boolean modified = false;
403            final Iterator<E> it = iterator();
404            while (it.hasNext()) {
405                if (coll.contains(it.next()) == false) {
406                    it.remove();
407                    modified = true;
408                }
409            }
410            return modified;
411        }
412
413        @Override
414        public void clear() {
415            parent.clear();
416        }
417    }
418
419    //-----------------------------------------------------------------------
420    /**
421     * Inner class KeySet.
422     */
423    protected static class KeySet<K> extends View<K, Object, K> implements Set<K> {
424
425        /** Serialization version */
426        private static final long serialVersionUID = -7107935777385040694L;
427
428        /**
429         * Constructs a new view of the BidiMap.
430         *
431         * @param parent  the parent BidiMap
432         */
433        @SuppressWarnings("unchecked")
434        protected KeySet(final AbstractDualBidiMap<K, ?> parent) {
435            super(parent.normalMap.keySet(), (AbstractDualBidiMap<K, Object>) parent);
436        }
437
438        @Override
439        public Iterator<K> iterator() {
440            return parent.createKeySetIterator(super.iterator());
441        }
442
443        @Override
444        public boolean contains(final Object key) {
445            return parent.normalMap.containsKey(key);
446        }
447
448        @Override
449        public boolean remove(final Object key) {
450            if (parent.normalMap.containsKey(key)) {
451                final Object value = parent.normalMap.remove(key);
452                parent.reverseMap.remove(value);
453                return true;
454            }
455            return false;
456        }
457    }
458
459    /**
460     * Inner class KeySetIterator.
461     */
462    protected static class KeySetIterator<K> extends AbstractIteratorDecorator<K> {
463
464        /** The parent map */
465        protected final AbstractDualBidiMap<K, ?> parent;
466
467        /** The last returned key */
468        protected K lastKey = null;
469
470        /** Whether remove is allowed at present */
471        protected boolean canRemove = false;
472
473        /**
474         * Constructor.
475         * @param iterator  the iterator to decorate
476         * @param parent  the parent map
477         */
478        protected KeySetIterator(final Iterator<K> iterator, final AbstractDualBidiMap<K, ?> parent) {
479            super(iterator);
480            this.parent = parent;
481        }
482
483        @Override
484        public K next() {
485            lastKey = super.next();
486            canRemove = true;
487            return lastKey;
488        }
489
490        @Override
491        public void remove() {
492            if (canRemove == false) {
493                throw new IllegalStateException("Iterator remove() can only be called once after next()");
494            }
495            final Object value = parent.normalMap.get(lastKey);
496            super.remove();
497            parent.reverseMap.remove(value);
498            lastKey = null;
499            canRemove = false;
500        }
501    }
502
503    //-----------------------------------------------------------------------
504    /**
505     * Inner class Values.
506     */
507    protected static class Values<V> extends View<Object, V, V> implements Set<V> {
508
509        /** Serialization version */
510        private static final long serialVersionUID = 4023777119829639864L;
511
512        /**
513         * Constructs a new view of the BidiMap.
514         *
515         * @param parent  the parent BidiMap
516         */
517        @SuppressWarnings("unchecked")
518        protected Values(final AbstractDualBidiMap<?, V> parent) {
519            super(parent.normalMap.values(), (AbstractDualBidiMap<Object, V>) parent);
520        }
521
522        @Override
523        public Iterator<V> iterator() {
524            return parent.createValuesIterator(super.iterator());
525        }
526
527        @Override
528        public boolean contains(final Object value) {
529            return parent.reverseMap.containsKey(value);
530        }
531
532        @Override
533        public boolean remove(final Object value) {
534            if (parent.reverseMap.containsKey(value)) {
535                final Object key = parent.reverseMap.remove(value);
536                parent.normalMap.remove(key);
537                return true;
538            }
539            return false;
540        }
541    }
542
543    /**
544     * Inner class ValuesIterator.
545     */
546    protected static class ValuesIterator<V> extends AbstractIteratorDecorator<V> {
547
548        /** The parent map */
549        protected final AbstractDualBidiMap<Object, V> parent;
550
551        /** The last returned value */
552        protected V lastValue = null;
553
554        /** Whether remove is allowed at present */
555        protected boolean canRemove = false;
556
557        /**
558         * Constructor.
559         * @param iterator  the iterator to decorate
560         * @param parent  the parent map
561         */
562        @SuppressWarnings("unchecked")
563        protected ValuesIterator(final Iterator<V> iterator, final AbstractDualBidiMap<?, V> parent) {
564            super(iterator);
565            this.parent = (AbstractDualBidiMap<Object, V>) parent;
566        }
567
568        @Override
569        public V next() {
570            lastValue = super.next();
571            canRemove = true;
572            return lastValue;
573        }
574
575        @Override
576        public void remove() {
577            if (canRemove == false) {
578                throw new IllegalStateException("Iterator remove() can only be called once after next()");
579            }
580            super.remove(); // removes from maps[0]
581            parent.reverseMap.remove(lastValue);
582            lastValue = null;
583            canRemove = false;
584        }
585    }
586
587    //-----------------------------------------------------------------------
588    /**
589     * Inner class EntrySet.
590     */
591    protected static class EntrySet<K, V> extends View<K, V, Map.Entry<K, V>> implements Set<Map.Entry<K, V>> {
592
593        /** Serialization version */
594        private static final long serialVersionUID = 4040410962603292348L;
595
596        /**
597         * Constructs a new view of the BidiMap.
598         *
599         * @param parent  the parent BidiMap
600         */
601        protected EntrySet(final AbstractDualBidiMap<K, V> parent) {
602            super(parent.normalMap.entrySet(), parent);
603        }
604
605        @Override
606        public Iterator<Map.Entry<K, V>> iterator() {
607            return parent.createEntrySetIterator(super.iterator());
608        }
609
610        @Override
611        public boolean remove(final Object obj) {
612            if (obj instanceof Map.Entry == false) {
613                return false;
614            }
615            final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
616            final Object key = entry.getKey();
617            if (parent.containsKey(key)) {
618                final V value = parent.normalMap.get(key);
619                if (value == null ? entry.getValue() == null : value.equals(entry.getValue())) {
620                    parent.normalMap.remove(key);
621                    parent.reverseMap.remove(value);
622                    return true;
623                }
624            }
625            return false;
626        }
627    }
628
629    /**
630     * Inner class EntrySetIterator.
631     */
632    protected static class EntrySetIterator<K, V> extends AbstractIteratorDecorator<Map.Entry<K, V>> {
633
634        /** The parent map */
635        protected final AbstractDualBidiMap<K, V> parent;
636
637        /** The last returned entry */
638        protected Map.Entry<K, V> last = null;
639
640        /** Whether remove is allowed at present */
641        protected boolean canRemove = false;
642
643        /**
644         * Constructor.
645         * @param iterator  the iterator to decorate
646         * @param parent  the parent map
647         */
648        protected EntrySetIterator(final Iterator<Map.Entry<K, V>> iterator, final AbstractDualBidiMap<K, V> parent) {
649            super(iterator);
650            this.parent = parent;
651        }
652
653        @Override
654        public Map.Entry<K, V> next() {
655            last = new MapEntry<K, V>(super.next(), parent);
656            canRemove = true;
657            return last;
658        }
659
660        @Override
661        public void remove() {
662            if (canRemove == false) {
663                throw new IllegalStateException("Iterator remove() can only be called once after next()");
664            }
665            // store value as remove may change the entry in the decorator (eg.TreeMap)
666            final Object value = last.getValue();
667            super.remove();
668            parent.reverseMap.remove(value);
669            last = null;
670            canRemove = false;
671        }
672    }
673
674    /**
675     * Inner class MapEntry.
676     */
677    protected static class MapEntry<K, V> extends AbstractMapEntryDecorator<K, V> {
678
679        /** The parent map */
680        protected final AbstractDualBidiMap<K, V> parent;
681
682        /**
683         * Constructor.
684         * @param entry  the entry to decorate
685         * @param parent  the parent map
686         */
687        protected MapEntry(final Map.Entry<K, V> entry, final AbstractDualBidiMap<K, V> parent) {
688            super(entry);
689            this.parent = parent;
690        }
691
692        @Override
693        public V setValue(final V value) {
694            final K key = MapEntry.this.getKey();
695            if (parent.reverseMap.containsKey(value) &&
696                parent.reverseMap.get(value) != key) {
697                throw new IllegalArgumentException(
698                        "Cannot use setValue() when the object being set is already in the map");
699            }
700            parent.put(key, value);
701            return super.setValue(value);
702        }
703    }
704
705    /**
706     * Inner class MapIterator.
707     */
708    protected static class BidiMapIterator<K, V> implements MapIterator<K, V>, ResettableIterator<K> {
709
710        /** The parent map */
711        protected final AbstractDualBidiMap<K, V> parent;
712
713        /** The iterator being wrapped */
714        protected Iterator<Map.Entry<K, V>> iterator;
715
716        /** The last returned entry */
717        protected Map.Entry<K, V> last = null;
718
719        /** Whether remove is allowed at present */
720        protected boolean canRemove = false;
721
722        /**
723         * Constructor.
724         * @param parent  the parent map
725         */
726        protected BidiMapIterator(final AbstractDualBidiMap<K, V> parent) {
727            super();
728            this.parent = parent;
729            this.iterator = parent.normalMap.entrySet().iterator();
730        }
731
732        @Override
733        public boolean hasNext() {
734            return iterator.hasNext();
735        }
736
737        @Override
738        public K next() {
739            last = iterator.next();
740            canRemove = true;
741            return last.getKey();
742        }
743
744        @Override
745        public void remove() {
746            if (canRemove == false) {
747                throw new IllegalStateException("Iterator remove() can only be called once after next()");
748            }
749            // store value as remove may change the entry in the decorator (eg.TreeMap)
750            final V value = last.getValue();
751            iterator.remove();
752            parent.reverseMap.remove(value);
753            last = null;
754            canRemove = false;
755        }
756
757        @Override
758        public K getKey() {
759            if (last == null) {
760                throw new IllegalStateException(
761                        "Iterator getKey() can only be called after next() and before remove()");
762            }
763            return last.getKey();
764        }
765
766        @Override
767        public V getValue() {
768            if (last == null) {
769                throw new IllegalStateException(
770                        "Iterator getValue() can only be called after next() and before remove()");
771            }
772            return last.getValue();
773        }
774
775        @Override
776        public V setValue(final V value) {
777            if (last == null) {
778                throw new IllegalStateException(
779                        "Iterator setValue() can only be called after next() and before remove()");
780            }
781            if (parent.reverseMap.containsKey(value) &&
782                parent.reverseMap.get(value) != last.getKey()) {
783                throw new IllegalArgumentException(
784                        "Cannot use setValue() when the object being set is already in the map");
785            }
786            return parent.put(last.getKey(), value);
787        }
788
789        @Override
790        public void reset() {
791            iterator = parent.normalMap.entrySet().iterator();
792            last = null;
793            canRemove = false;
794        }
795
796        @Override
797        public String toString() {
798            if (last != null) {
799                return "MapIterator[" + getKey() + "=" + getValue() + "]";
800            }
801            return "MapIterator[]";
802        }
803    }
804
805}