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