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 887892 2013-11-24 13:43:45Z 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    public Comparator<? super K> comparator() {
132        return ((SortedMap<K, V>) normalMap).comparator();
133    }
134
135    public Comparator<? super V> valueComparator() {
136        return ((SortedMap<V, K>) reverseMap).comparator();
137    }
138
139    public K firstKey() {
140        return ((SortedMap<K, V>) normalMap).firstKey();
141    }
142
143    public K lastKey() {
144        return ((SortedMap<K, V>) normalMap).lastKey();
145    }
146
147    public K nextKey(final K key) {
148        if (isEmpty()) {
149            return null;
150        }
151        if (normalMap instanceof OrderedMap) {
152            return ((OrderedMap<K, ?>) normalMap).nextKey(key);
153        }
154        final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
155        final Iterator<K> it = sm.tailMap(key).keySet().iterator();
156        it.next();
157        if (it.hasNext()) {
158            return it.next();
159        }
160        return null;
161    }
162
163    public K previousKey(final K key) {
164        if (isEmpty()) {
165            return null;
166        }
167        if (normalMap instanceof OrderedMap) {
168            return ((OrderedMap<K, V>) normalMap).previousKey(key);
169        }
170        final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
171        final SortedMap<K, V> hm = sm.headMap(key);
172        if (hm.isEmpty()) {
173            return null;
174        }
175        return hm.lastKey();
176    }
177
178    //-----------------------------------------------------------------------
179    /**
180     * Obtains an ordered map iterator.
181     * <p>
182     * This implementation copies the elements to an ArrayList in order to
183     * provide the forward/backward behaviour.
184     *
185     * @return a new ordered map iterator
186     */
187    @Override
188    public OrderedMapIterator<K, V> mapIterator() {
189        return new BidiOrderedMapIterator<K, V>(this);
190    }
191
192    public SortedBidiMap<V, K> inverseSortedBidiMap() {
193        return inverseBidiMap();
194    }
195
196    public OrderedBidiMap<V, K> inverseOrderedBidiMap() {
197        return inverseBidiMap();
198    }
199
200    //-----------------------------------------------------------------------
201
202    public SortedMap<K, V> headMap(final K toKey) {
203        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).headMap(toKey);
204        return new ViewMap<K, V>(this, sub);
205    }
206
207    public SortedMap<K, V> tailMap(final K fromKey) {
208        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).tailMap(fromKey);
209        return new ViewMap<K, V>(this, sub);
210    }
211
212    public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
213        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).subMap(fromKey, toKey);
214        return new ViewMap<K, V>(this, sub);
215    }
216
217    @Override
218    public SortedBidiMap<V, K> inverseBidiMap() {
219        return (SortedBidiMap<V, K>) super.inverseBidiMap();
220    }
221
222    //-----------------------------------------------------------------------
223    /**
224     * Internal sorted map view.
225     */
226    protected static class ViewMap<K, V> extends AbstractSortedMapDecorator<K, V> {
227        /**
228         * Constructor.
229         * @param bidi  the parent bidi map
230         * @param sm  the subMap sorted map
231         */
232        protected ViewMap(final DualTreeBidiMap<K, V> bidi, final SortedMap<K, V> sm) {
233            // the implementation is not great here...
234            // use the normalMap as the filtered map, but reverseMap as the full map
235            // this forces containsValue and clear to be overridden
236            super(new DualTreeBidiMap<K, V>(sm, bidi.reverseMap, bidi.inverseBidiMap));
237        }
238
239        @Override
240        public boolean containsValue(final Object value) {
241            // override as default implementation uses reverseMap
242            return decorated().normalMap.containsValue(value);
243        }
244
245        @Override
246        public void clear() {
247            // override as default implementation uses reverseMap
248            for (final Iterator<K> it = keySet().iterator(); it.hasNext();) {
249                it.next();
250                it.remove();
251            }
252        }
253
254        @Override
255        public SortedMap<K, V> headMap(final K toKey) {
256            return new ViewMap<K, V>(decorated(), super.headMap(toKey));
257        }
258
259        @Override
260        public SortedMap<K, V> tailMap(final K fromKey) {
261            return new ViewMap<K, V>(decorated(), super.tailMap(fromKey));
262        }
263
264        @Override
265        public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
266            return new ViewMap<K, V>(decorated(), super.subMap(fromKey, toKey));
267        }
268
269        @Override
270        protected DualTreeBidiMap<K, V> decorated() {
271            return (DualTreeBidiMap<K, V>) super.decorated();
272        }
273
274        @Override
275        public K previousKey(final K key) {
276            return decorated().previousKey(key);
277        }
278
279        @Override
280        public K nextKey(final K key) {
281            return decorated().nextKey(key);
282        }
283    }
284
285    //-----------------------------------------------------------------------
286    /**
287     * Inner class MapIterator.
288     */
289    protected static class BidiOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> {
290
291        /** The parent map */
292        private final AbstractDualBidiMap<K, V> parent;
293
294        /** The iterator being decorated */
295        private ListIterator<Map.Entry<K, V>> iterator;
296
297        /** The last returned entry */
298        private Map.Entry<K, V> last = null;
299
300        /**
301         * Constructor.
302         * @param parent  the parent map
303         */
304        protected BidiOrderedMapIterator(final AbstractDualBidiMap<K, V> parent) {
305            super();
306            this.parent = parent;
307            iterator = new ArrayList<Map.Entry<K, V>>(parent.entrySet()).listIterator();
308        }
309
310        public boolean hasNext() {
311            return iterator.hasNext();
312        }
313
314        public K next() {
315            last = iterator.next();
316            return last.getKey();
317        }
318
319        public boolean hasPrevious() {
320            return iterator.hasPrevious();
321        }
322
323        public K previous() {
324            last = iterator.previous();
325            return last.getKey();
326        }
327
328        public void remove() {
329            iterator.remove();
330            parent.remove(last.getKey());
331            last = null;
332        }
333
334        public K getKey() {
335            if (last == null) {
336                throw new IllegalStateException(
337                        "Iterator getKey() can only be called after next() and before remove()");
338            }
339            return last.getKey();
340        }
341
342        public V getValue() {
343            if (last == null) {
344                throw new IllegalStateException(
345                        "Iterator getValue() can only be called after next() and before remove()");
346            }
347            return last.getValue();
348        }
349
350        public V setValue(final V value) {
351            if (last == null) {
352                throw new IllegalStateException(
353                        "Iterator setValue() can only be called after next() and before remove()");
354            }
355            if (parent.reverseMap.containsKey(value) &&
356                parent.reverseMap.get(value) != last.getKey()) {
357                throw new IllegalArgumentException(
358                        "Cannot use setValue() when the object being set is already in the map");
359            }
360            final V oldValue = parent.put(last.getKey(), value);
361            // Map.Entry specifies that the behavior is undefined when the backing map
362            // has been modified (as we did with the put), so we also set the value
363            // (especially needed for IBM JDK)
364            last.setValue(value);
365            return oldValue;
366        }
367
368        public void reset() {
369            iterator = new ArrayList<Map.Entry<K, V>>(parent.entrySet()).listIterator();
370            last = null;
371        }
372
373        @Override
374        public String toString() {
375            if (last != null) {
376                return "MapIterator[" + getKey() + "=" + getValue() + "]";
377            }
378            return "MapIterator[]";
379        }
380    }
381
382    // Serialization
383    //-----------------------------------------------------------------------
384    private void writeObject(final ObjectOutputStream out) throws IOException {
385        out.defaultWriteObject();
386        out.writeObject(normalMap);
387    }
388
389    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
390        in.defaultReadObject();
391        normalMap = new TreeMap<K, V>(comparator);
392        reverseMap = new TreeMap<V, K>(valueComparator);
393        @SuppressWarnings("unchecked") // will fail at runtime if the stream is incorrect
394        final Map<K, V> map = (Map<K, V>) in.readObject();
395        putAll(map);
396    }
397
398}