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