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     */
017    package org.apache.commons.collections.bidimap;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.ObjectOutputStream;
022    import java.io.Serializable;
023    import java.util.ArrayList;
024    import java.util.Comparator;
025    import java.util.Iterator;
026    import java.util.ListIterator;
027    import java.util.Map;
028    import java.util.SortedMap;
029    import java.util.TreeMap;
030    
031    import org.apache.commons.collections.BidiMap;
032    import org.apache.commons.collections.OrderedBidiMap;
033    import org.apache.commons.collections.OrderedMap;
034    import org.apache.commons.collections.OrderedMapIterator;
035    import org.apache.commons.collections.ResettableIterator;
036    import org.apache.commons.collections.SortedBidiMap;
037    import org.apache.commons.collections.map.AbstractSortedMapDecorator;
038    
039    /**
040     * Implementation of <code>BidiMap</code> that uses two <code>TreeMap</code> 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 <code>TreeMap</code>
050     * and the flawed <code>createMap</code> method is ignored.
051     * 
052     * @since Commons Collections 3.0
053     * @version $Id: DualTreeBidiMap.java 646777 2008-04-10 12:33:15Z niallp $
054     * 
055     * @author Matthew Hawthorne
056     * @author Stephen Colebourne
057     */
058    public class DualTreeBidiMap
059            extends AbstractDualBidiMap implements SortedBidiMap, Serializable {
060    
061        /** Ensure serialization compatibility */
062        private static final long serialVersionUID = 721969328361809L;
063        /** The comparator to use */
064        protected final Comparator comparator;
065        
066        /**
067         * Creates an empty <code>DualTreeBidiMap</code>
068         */
069        public DualTreeBidiMap() {
070            super(new TreeMap(), new TreeMap());
071            this.comparator = null;
072        }
073    
074        /** 
075         * Constructs a <code>DualTreeBidiMap</code> and copies the mappings from
076         * specified <code>Map</code>.  
077         *
078         * @param map  the map whose mappings are to be placed in this map
079         */
080        public DualTreeBidiMap(Map map) {
081            super(new TreeMap(), new TreeMap());
082            putAll(map);
083            this.comparator = null;
084        }
085    
086        /** 
087         * Constructs a <code>DualTreeBidiMap</code> using the specified Comparator.
088         *
089         * @param comparator  the Comparator
090         */
091        public DualTreeBidiMap(Comparator comparator) {
092            super(new TreeMap(comparator), new TreeMap(comparator));
093            this.comparator = comparator;
094        }
095    
096        /** 
097         * Constructs a <code>DualTreeBidiMap</code> that decorates the specified maps.
098         *
099         * @param normalMap  the normal direction map
100         * @param reverseMap  the reverse direction map
101         * @param inverseBidiMap  the inverse BidiMap
102         */
103        protected DualTreeBidiMap(Map normalMap, Map reverseMap, BidiMap inverseBidiMap) {
104            super(normalMap, reverseMap, inverseBidiMap);
105            this.comparator = ((SortedMap) normalMap).comparator();
106        }
107    
108        /**
109         * Creates a new instance of this object.
110         * 
111         * @param normalMap  the normal direction map
112         * @param reverseMap  the reverse direction map
113         * @param inverseMap  the inverse BidiMap
114         * @return new bidi map
115         */
116        protected BidiMap createBidiMap(Map normalMap, Map reverseMap, BidiMap inverseMap) {
117            return new DualTreeBidiMap(normalMap, reverseMap, inverseMap);
118        }
119    
120        //-----------------------------------------------------------------------
121        public Comparator comparator() {
122            return ((SortedMap) maps[0]).comparator();
123        }
124    
125        public Object firstKey() {
126            return ((SortedMap) maps[0]).firstKey();
127        }
128    
129        public Object lastKey() {
130            return ((SortedMap) maps[0]).lastKey();
131        }
132    
133        public Object nextKey(Object key) {
134            if (isEmpty()) {
135                return null;
136            }
137            if (maps[0] instanceof OrderedMap) {
138                return ((OrderedMap) maps[0]).nextKey(key);
139            }
140            SortedMap sm = (SortedMap) maps[0];
141            Iterator it = sm.tailMap(key).keySet().iterator();
142            it.next();
143            if (it.hasNext()) {
144                return it.next();
145            }
146            return null;
147        }
148    
149        public Object previousKey(Object key) {
150            if (isEmpty()) {
151                return null;
152            }
153            if (maps[0] instanceof OrderedMap) {
154                return ((OrderedMap) maps[0]).previousKey(key);
155            }
156            SortedMap sm = (SortedMap) maps[0];
157            SortedMap hm = sm.headMap(key);
158            if (hm.isEmpty()) {
159                return null;
160            }
161            return hm.lastKey();
162        }
163    
164        //-----------------------------------------------------------------------
165        /**
166         * Obtains an ordered map iterator.
167         * <p>
168         * This implementation copies the elements to an ArrayList in order to
169         * provide the forward/backward behaviour.
170         * 
171         * @return a new ordered map iterator
172         */
173        public OrderedMapIterator orderedMapIterator() {
174            return new BidiOrderedMapIterator(this);
175        }
176    
177        public SortedBidiMap inverseSortedBidiMap() {
178            return (SortedBidiMap) inverseBidiMap();
179        }
180    
181        public OrderedBidiMap inverseOrderedBidiMap() {
182            return (OrderedBidiMap) inverseBidiMap();
183        }
184    
185        //-----------------------------------------------------------------------
186        public SortedMap headMap(Object toKey) {
187            SortedMap sub = ((SortedMap) maps[0]).headMap(toKey);
188            return new ViewMap(this, sub);
189        }
190    
191        public SortedMap tailMap(Object fromKey) {
192            SortedMap sub = ((SortedMap) maps[0]).tailMap(fromKey);
193            return new ViewMap(this, sub);
194        }
195    
196        public SortedMap subMap(Object fromKey, Object toKey) {
197            SortedMap sub = ((SortedMap) maps[0]).subMap(fromKey, toKey);
198            return new ViewMap(this, sub);
199        }
200        
201        //-----------------------------------------------------------------------
202        /**
203         * Internal sorted map view.
204         */
205        protected static class ViewMap extends AbstractSortedMapDecorator {
206            /** The parent bidi map. */
207            final DualTreeBidiMap bidi;
208            
209            /**
210             * Constructor.
211             * @param bidi  the parent bidi map
212             * @param sm  the subMap sorted map
213             */
214            protected ViewMap(DualTreeBidiMap bidi, SortedMap sm) {
215                // the implementation is not great here...
216                // use the maps[0] as the filtered map, but maps[1] as the full map
217                // this forces containsValue and clear to be overridden
218                super((SortedMap) bidi.createBidiMap(sm, bidi.maps[1], bidi.inverseBidiMap));
219                this.bidi = (DualTreeBidiMap) map;
220            }
221            
222            public boolean containsValue(Object value) {
223                // override as default implementation jumps to [1]
224                return bidi.maps[0].containsValue(value);
225            }
226            
227            public void clear() {
228                // override as default implementation jumps to [1]
229                for (Iterator it = keySet().iterator(); it.hasNext();) {
230                    it.next();
231                    it.remove();
232                }
233            }
234            
235            public SortedMap headMap(Object toKey) {
236                return new ViewMap(bidi, super.headMap(toKey));
237            }
238    
239            public SortedMap tailMap(Object fromKey) {
240                return new ViewMap(bidi, super.tailMap(fromKey));
241            }
242    
243            public SortedMap subMap(Object fromKey, Object toKey) {
244                return new ViewMap(bidi, super.subMap(fromKey, toKey));
245            }
246        }
247    
248        //-----------------------------------------------------------------------
249        /**
250         * Inner class MapIterator.
251         */
252        protected static class BidiOrderedMapIterator implements OrderedMapIterator, ResettableIterator {
253            
254            /** The parent map */
255            protected final AbstractDualBidiMap parent;
256            /** The iterator being decorated */
257            protected ListIterator iterator;
258            /** The last returned entry */
259            private Map.Entry last = null;
260            
261            /**
262             * Constructor.
263             * @param parent  the parent map
264             */
265            protected BidiOrderedMapIterator(AbstractDualBidiMap parent) {
266                super();
267                this.parent = parent;
268                iterator = new ArrayList(parent.entrySet()).listIterator();
269            }
270            
271            public boolean hasNext() {
272                return iterator.hasNext();
273            }
274            
275            public Object next() {
276                last = (Map.Entry) iterator.next();
277                return last.getKey();
278            }
279            
280            public boolean hasPrevious() {
281                return iterator.hasPrevious();
282            }
283            
284            public Object previous() {
285                last = (Map.Entry) iterator.previous();
286                return last.getKey();
287            }
288            
289            public void remove() {
290                iterator.remove();
291                parent.remove(last.getKey());
292                last = null;
293            }
294            
295            public Object getKey() {
296                if (last == null) {
297                    throw new IllegalStateException("Iterator getKey() can only be called after next() and before remove()");
298                }
299                return last.getKey();
300            }
301    
302            public Object getValue() {
303                if (last == null) {
304                    throw new IllegalStateException("Iterator getValue() can only be called after next() and before remove()");
305                }
306                return last.getValue();
307            }
308            
309            public Object setValue(Object value) {
310                if (last == null) {
311                    throw new IllegalStateException("Iterator setValue() can only be called after next() and before remove()");
312                }
313                if (parent.maps[1].containsKey(value) &&
314                    parent.maps[1].get(value) != last.getKey()) {
315                    throw new IllegalArgumentException("Cannot use setValue() when the object being set is already in the map");
316                }
317                return parent.put(last.getKey(), value);
318            }
319            
320            public void reset() {
321                iterator = new ArrayList(parent.entrySet()).listIterator();
322                last = null;
323            }
324            
325            public String toString() {
326                if (last != null) {
327                    return "MapIterator[" + getKey() + "=" + getValue() + "]";
328                } else {
329                    return "MapIterator[]";
330                }
331            }
332        }
333        
334        // Serialization
335        //-----------------------------------------------------------------------
336        private void writeObject(ObjectOutputStream out) throws IOException {
337            out.defaultWriteObject();
338            out.writeObject(maps[0]);
339        }
340    
341        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
342            in.defaultReadObject();
343            maps[0] = new TreeMap(comparator);
344            maps[1] = new TreeMap(comparator);
345            Map map = (Map) in.readObject();
346            putAll(map);
347        }
348    
349    }