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