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