    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 *      https://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.io.IOException;
    020import java.io.ObjectInputStream;
    021import java.io.ObjectOutputStream;
    022import java.io.Serializable;
    023import java.util.ArrayList;
    024import java.util.Comparator;
    025import java.util.Iterator;
    026import java.util.ListIterator;
    027import java.util.Map;
    028import java.util.SortedMap;
    029import java.util.TreeMap;
    030
    031import org.apache.commons.collections4.BidiMap;
    032import org.apache.commons.collections4.OrderedBidiMap;
    033import org.apache.commons.collections4.OrderedMap;
    034import org.apache.commons.collections4.OrderedMapIterator;
    035import org.apache.commons.collections4.ResettableIterator;
    036import org.apache.commons.collections4.SortedBidiMap;
    037import org.apache.commons.collections4.map.AbstractSortedMapDecorator;
    038
    039/**
    040 * Implements {@link BidiMap} with two {@link TreeMap} instances.
    041 * <p>
    042 * The setValue() method on iterators will succeed only if the new value being set is
    043 * not already in the bidi map.
    044 * </p>
    045 * <p>
    046 * When considering whether to use this class, the {@link TreeBidiMap} class should
    047 * also be considered. It implements the interface using a dedicated design, and does
    048 * not store each object twice, which can save on memory use.
    049 * </p>
    050 * <p>
    051 * NOTE: From Commons Collections 3.1, all subclasses will use {@link TreeMap}
    052 * and the flawed {@code createMap} method is ignored.
    053 * </p>
    054 *
    055 * @param <K> The type of the keys in this map
    056 * @param <V> The type of the values in this map
    057 * @since 3.0
    058 */
    059public class DualTreeBidiMap<K, V> extends AbstractDualBidiMap<K, V>
    060        implements SortedBidiMap<K, V>, Serializable {
    061
    062    /**
    063     * Inner class MapIterator.
    064     *
    065     * @param <K> The type of the keys.
    066     * @param <V> The type of the values.
    067     */
    068    protected static class BidiOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
    069
    070        /** The parent map */
    071        private final AbstractDualBidiMap<K, V> parent;
    072
    073        /** The iterator being decorated */
    074        private ListIterator<Map.Entry<K, V>> iterator;
    075
    076        /** The last returned entry */
    077        private Map.Entry<K, V> last;
    078
    079        /**
    080         * Constructs a new instance.
    081         *
    082         * @param parent  The parent map
    083         */
    084        protected BidiOrderedMapIterator(final AbstractDualBidiMap<K, V> parent) {
    085            this.parent = parent;
    086            iterator = new ArrayList<>(parent.entrySet()).listIterator();
    087        }
    088
    089        @Override
    090        public K getKey() {
    091            if (last == null) {
    092                throw new IllegalStateException(
    093                        "Iterator getKey() can only be called after next() and before remove()");
    094            }
    095            return last.getKey();
    096        }
    097
    098        @Override
    099        public V getValue() {
    100            if (last == null) {
    101                throw new IllegalStateException(
    102                        "Iterator getValue() can only be called after next() and before remove()");
    103            }
    104            return last.getValue();
    105        }
    106
    107        @Override
    108        public boolean hasNext() {
    109            return iterator.hasNext();
    110        }
    111
    112        @Override
    113        public boolean hasPrevious() {
    114            return iterator.hasPrevious();
    115        }
    116
    117        @Override
    118        public K next() {
    119            last = iterator.next();
    120            return last.getKey();
    121        }
    122
    123        @Override
    124        public K previous() {
    125            last = iterator.previous();
    126            return last.getKey();
    127        }
    128
    129        @Override
    130        public void remove() {
    131            iterator.remove();
    132            parent.remove(last.getKey());
    133            last = null;
    134        }
    135
    136        @Override
    137        public void reset() {
    138            iterator = new ArrayList<>(parent.entrySet()).listIterator();
    139            last = null;
    140        }
    141
    142        @Override
    143        public V setValue(final V value) {
    144            if (last == null) {
    145                throw new IllegalStateException(
    146                        "Iterator setValue() can only be called after next() and before remove()");
    147            }
    148            if (parent.reverseMap.containsKey(value) &&
    149                parent.reverseMap.get(value) != last.getKey()) {
    150                throw new IllegalArgumentException(
    151                        "Cannot use setValue() when the object being set is already in the map");
    152            }
    153            final V oldValue = parent.put(last.getKey(), value);
    154            // Map.Entry specifies that the behavior is undefined when the backing map
    155            // has been modified (as we did with the put), so we also set the value
    156            last.setValue(value);
    157            return oldValue;
    158        }
    159
    160        @Override
    161        public String toString() {
    162            if (last != null) {
    163                return "MapIterator[" + getKey() + "=" + getValue() + "]";
    164            }
    165            return "MapIterator[]";
    166        }
    167    }
    168
    169    /**
    170     * Internal sorted map view.
    171     *
    172     * @param <K> The type of the keys.
    173     * @param <V> The type of the values.
    174     */
    175    protected static class ViewMap<K, V> extends AbstractSortedMapDecorator<K, V> {
    176
    177        /**
    178         * Constructs a new instance.
    179         *
    180         * @param bidi  The parent bidi map
    181         * @param sm  The subMap sorted map
    182         */
    183        protected ViewMap(final DualTreeBidiMap<K, V> bidi, final SortedMap<K, V> sm) {
    184            // the implementation is not great here...
    185            // use the normalMap as the filtered map, but reverseMap as the full map
    186            // this forces containsValue and clear to be overridden
    187            super(new DualTreeBidiMap<>(sm, bidi.reverseMap, bidi.inverseBidiMap));
    188        }
    189
    190        @Override
    191        public void clear() {
    192            // override as default implementation uses reverseMap
    193            for (final Iterator<K> it = keySet().iterator(); it.hasNext();) {
    194                it.next();
    195                it.remove();
    196            }
    197        }
    198
    199        @Override
    200        public boolean containsValue(final Object value) {
    201            // override as default implementation uses reverseMap
    202            return decorated().normalMap.containsValue(value);
    203        }
    204
    205        @Override
    206        protected DualTreeBidiMap<K, V> decorated() {
    207            return (DualTreeBidiMap<K, V>) super.decorated();
    208        }
    209
    210        @Override
    211        public SortedMap<K, V> headMap(final K toKey) {
    212            return new ViewMap<>(decorated(), super.headMap(toKey));
    213        }
    214
    215        @Override
    216        public K nextKey(final K key) {
    217            return decorated().nextKey(key);
    218        }
    219
    220        @Override
    221        public K previousKey(final K key) {
    222            return decorated().previousKey(key);
    223        }
    224
    225        @Override
    226        public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
    227            return new ViewMap<>(decorated(), super.subMap(fromKey, toKey));
    228        }
    229
    230        @Override
    231        public SortedMap<K, V> tailMap(final K fromKey) {
    232            return new ViewMap<>(decorated(), super.tailMap(fromKey));
    233        }
    234    }
    235
    236    /** Ensure serialization compatibility */
    237    private static final long serialVersionUID = 721969328361809L;
    238
    239    /** The key comparator to use */
    240    private final Comparator<? super K> comparator;
    241
    242    /** The value comparator to use */
    243    private final Comparator<? super V> valueComparator;
    244
    245    /**
    246     * Creates an empty {@link DualTreeBidiMap}.
    247     */
    248    public DualTreeBidiMap() {
    249        super(new TreeMap<>(), new TreeMap<>());
    250        this.comparator = null;
    251        this.valueComparator = null;
    252    }
    253
    254    /**
    255     * Constructs a {@link DualTreeBidiMap} using the specified {@link Comparator}.
    256     *
    257     * @param keyComparator  The comparator
    258     * @param valueComparator  The values comparator to use
    259     */
    260    public DualTreeBidiMap(final Comparator<? super K> keyComparator, final Comparator<? super V> valueComparator) {
    261        super(new TreeMap<>(keyComparator), new TreeMap<>(valueComparator));
    262        this.comparator = keyComparator;
    263        this.valueComparator = valueComparator;
    264    }
    265
    266    /**
    267     * Constructs a {@link DualTreeBidiMap} and copies the mappings from
    268     * specified {@link Map}.
    269     *
    270     * @param map  The map whose mappings are to be placed in this map
    271     */
    272    public DualTreeBidiMap(final Map<? extends K, ? extends V> map) {
    273        super(new TreeMap<>(), new TreeMap<>());
    274        putAll(map);
    275        this.comparator = null;
    276        this.valueComparator = null;
    277    }
    278
    279    /**
    280     * Constructs a {@link DualTreeBidiMap} that decorates the specified maps.
    281     *
    282     * @param normalMap  The normal direction map
    283     * @param reverseMap  The reverse direction map
    284     * @param inverseBidiMap  The inverse BidiMap
    285     */
    286    protected DualTreeBidiMap(final Map<K, V> normalMap, final Map<V, K> reverseMap,
    287                              final BidiMap<V, K> inverseBidiMap) {
    288        super(normalMap, reverseMap, inverseBidiMap);
    289        this.comparator = ((SortedMap<K, V>) normalMap).comparator();
    290        this.valueComparator = ((SortedMap<V, K>) reverseMap).comparator();
    291    }
    292
    293    @Override
    294    public Comparator<? super K> comparator() {
    295        return ((SortedMap<K, V>) normalMap).comparator();
    296    }
    297
    298    /**
    299     * Creates a new instance of this object.
    300     *
    301     * @param normalMap  The normal direction map
    302     * @param reverseMap  The reverse direction map
    303     * @param inverseMap  The inverse BidiMap
    304     * @return new bidi map
    305     */
    306    @Override
    307    protected DualTreeBidiMap<V, K> createBidiMap(final Map<V, K> normalMap, final Map<K, V> reverseMap,
    308                                                  final BidiMap<K, V> inverseMap) {
    309        return new DualTreeBidiMap<>(normalMap, reverseMap, inverseMap);
    310    }
    311
    312    @Override
    313    public K firstKey() {
    314        return ((SortedMap<K, V>) normalMap).firstKey();
    315    }
    316
    317    @Override
    318    public SortedMap<K, V> headMap(final K toKey) {
    319        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).headMap(toKey);
    320        return new ViewMap<>(this, sub);
    321    }
    322
    323    @Override
    324    public SortedBidiMap<V, K> inverseBidiMap() {
    325        return (SortedBidiMap<V, K>) super.inverseBidiMap();
    326    }
    327
    328    /**
    329     * Defaults to {@link #inverseBidiMap()}.
    330     *
    331     * @return Defaults to {@link #inverseBidiMap()}.
    332     */
    333    public OrderedBidiMap<V, K> inverseOrderedBidiMap() {
    334        return inverseBidiMap();
    335    }
    336
    337    /**
    338     * Defaults to {@link #inverseBidiMap()}.
    339     *
    340     * @return Defaults to {@link #inverseBidiMap()}.
    341     */
    342    public SortedBidiMap<V, K> inverseSortedBidiMap() {
    343        return inverseBidiMap();
    344    }
    345
    346    @Override
    347    public K lastKey() {
    348        return ((SortedMap<K, V>) normalMap).lastKey();
    349    }
    350
    351    /**
    352     * Obtains an ordered map iterator.
    353     * <p>
    354     * This implementation copies the elements to an ArrayList in order to
    355     * provide the forward/backward behavior.
    356     * </p>
    357     *
    358     * @return A new ordered map iterator
    359     */
    360    @Override
    361    public OrderedMapIterator<K, V> mapIterator() {
    362        return new BidiOrderedMapIterator<>(this);
    363    }
    364
    365    @Override
    366    public K nextKey(final K key) {
    367        if (isEmpty()) {
    368            return null;
    369        }
    370        if (normalMap instanceof OrderedMap) {
    371            return ((OrderedMap<K, ?>) normalMap).nextKey(key);
    372        }
    373        final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
    374        final Iterator<K> it = sm.tailMap(key).keySet().iterator();
    375        it.next();
    376        if (it.hasNext()) {
    377            return it.next();
    378        }
    379        return null;
    380    }
    381
    382    @Override
    383    public K previousKey(final K key) {
    384        if (isEmpty()) {
    385            return null;
    386        }
    387        if (normalMap instanceof OrderedMap) {
    388            return ((OrderedMap<K, V>) normalMap).previousKey(key);
    389        }
    390        final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
    391        final SortedMap<K, V> hm = sm.headMap(key);
    392        if (hm.isEmpty()) {
    393            return null;
    394        }
    395        return hm.lastKey();
    396    }
    397
    398    /**
    399     * Deserializes an instance from an ObjectInputStream.
    400     *
    401     * @param in The source ObjectInputStream.
    402     * @throws IOException            Any of the usual Input/Output related exceptions.
    403     * @throws ClassNotFoundException A class of a serialized object cannot be found.
    404     */
    405    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
    406        in.defaultReadObject();
    407        normalMap = new TreeMap<>(comparator);
    408        reverseMap = new TreeMap<>(valueComparator);
    409        @SuppressWarnings("unchecked") // will fail at runtime if the stream is incorrect
    410        final Map<K, V> map = (Map<K, V>) in.readObject();
    411        putAll(map);
    412    }
    413
    414    @Override
    415    public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
    416        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).subMap(fromKey, toKey);
    417        return new ViewMap<>(this, sub);
    418    }
    419
    420    @Override
    421    public SortedMap<K, V> tailMap(final K fromKey) {
    422        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).tailMap(fromKey);
    423        return new ViewMap<>(this, sub);
    424    }
    425
    426    @Override
    427    public Comparator<? super V> valueComparator() {
    428        return ((SortedMap<V, K>) reverseMap).comparator();
    429    }
    430
    431    /**
    432     * Serializes this object to an ObjectOutputStream.
    433     *
    434     * @param out The target ObjectOutputStream.
    435     * @throws IOException thrown when an I/O errors occur writing to the target stream.
    436     */
    437    private void writeObject(final ObjectOutputStream out) throws IOException {
    438        out.defaultWriteObject();
    439        out.writeObject(normalMap);
    440    }
    441
    442}