    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}