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