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    public OrderedBidiMap<V, K> inverseOrderedBidiMap() {
326        return inverseBidiMap();
327    }
328
329    public SortedBidiMap<V, K> inverseSortedBidiMap() {
330        return inverseBidiMap();
331    }
332
333    @Override
334    public K lastKey() {
335        return ((SortedMap<K, V>) normalMap).lastKey();
336    }
337
338    /**
339     * Obtains an ordered map iterator.
340     * <p>
341     * This implementation copies the elements to an ArrayList in order to
342     * provide the forward/backward behavior.
343     *
344     * @return a new ordered map iterator
345     */
346    @Override
347    public OrderedMapIterator<K, V> mapIterator() {
348        return new BidiOrderedMapIterator<>(this);
349    }
350
351    @Override
352    public K nextKey(final K key) {
353        if (isEmpty()) {
354            return null;
355        }
356        if (normalMap instanceof OrderedMap) {
357            return ((OrderedMap<K, ?>) normalMap).nextKey(key);
358        }
359        final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
360        final Iterator<K> it = sm.tailMap(key).keySet().iterator();
361        it.next();
362        if (it.hasNext()) {
363            return it.next();
364        }
365        return null;
366    }
367
368    @Override
369    public K previousKey(final K key) {
370        if (isEmpty()) {
371            return null;
372        }
373        if (normalMap instanceof OrderedMap) {
374            return ((OrderedMap<K, V>) normalMap).previousKey(key);
375        }
376        final SortedMap<K, V> sm = (SortedMap<K, V>) normalMap;
377        final SortedMap<K, V> hm = sm.headMap(key);
378        if (hm.isEmpty()) {
379            return null;
380        }
381        return hm.lastKey();
382    }
383
384    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
385        in.defaultReadObject();
386        normalMap = new TreeMap<>(comparator);
387        reverseMap = new TreeMap<>(valueComparator);
388        @SuppressWarnings("unchecked") // will fail at runtime if the stream is incorrect
389        final Map<K, V> map = (Map<K, V>) in.readObject();
390        putAll(map);
391    }
392
393    @Override
394    public SortedMap<K, V> subMap(final K fromKey, final K toKey) {
395        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).subMap(fromKey, toKey);
396        return new ViewMap<>(this, sub);
397    }
398
399    @Override
400    public SortedMap<K, V> tailMap(final K fromKey) {
401        final SortedMap<K, V> sub = ((SortedMap<K, V>) normalMap).tailMap(fromKey);
402        return new ViewMap<>(this, sub);
403    }
404
405    @Override
406    public Comparator<? super V> valueComparator() {
407        return ((SortedMap<V, K>) reverseMap).comparator();
408    }
409
410    // Serialization
411    private void writeObject(final ObjectOutputStream out) throws IOException {
412        out.defaultWriteObject();
413        out.writeObject(normalMap);
414    }
415
416}