Java > Open Source Codes > org > apache > commons > collections > bidimap > DualTreeBidiMap


1 /*
2  * Copyright 2003-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.bidimap;
17
18 import java.io.IOException ;
19 import java.io.ObjectInputStream ;
20 import java.io.ObjectOutputStream ;
21 import java.io.Serializable ;
22 import java.util.ArrayList ;
23 import java.util.Comparator ;
24 import java.util.Iterator ;
25 import java.util.ListIterator ;
26 import java.util.Map ;
27 import java.util.SortedMap ;
28 import java.util.TreeMap ;
29
30 import org.apache.commons.collections.BidiMap;
31 import org.apache.commons.collections.OrderedBidiMap;
32 import org.apache.commons.collections.OrderedMap;
33 import org.apache.commons.collections.OrderedMapIterator;
34 import org.apache.commons.collections.ResettableIterator;
35 import org.apache.commons.collections.SortedBidiMap;
36 import org.apache.commons.collections.map.AbstractSortedMapDecorator;
37
38 /**
39  * Implementation of <code>BidiMap</code> that uses two <code>TreeMap</code> instances.
40  * <p>
41  * The setValue() method on iterators will succeed only if the new value being set is
42  * not already in the bidimap.
43  * <p>
44  * When considering whether to use this class, the {@link TreeBidiMap} class should
45  * also be considered. It implements the interface using a dedicated design, and does
46  * not store each object twice, which can save on memory use.
47  * <p>
48  * NOTE: From Commons Collections 3.1, all subclasses will use <code>TreeMap</code>
49  * and the flawed <code>createMap</code> method is ignored.
50  *
51  * @since Commons Collections 3.0
52  * @version $Id: DualTreeBidiMap.java,v 1.14 2004/06/11 23:27:37 scolebourne Exp $
53  *
54  * @author Matthew Hawthorne
55  * @author Stephen Colebourne
56  */
57 public class DualTreeBidiMap
58         extends AbstractDualBidiMap implements SortedBidiMap, Serializable {
59
60     /** Ensure serialization compatibility */
61     private static final long serialVersionUID = 721969328361809L;
62     /** The comparator to use */
63     protected final Comparator comparator;
64     
65     /**
66      * Creates an empty <code>DualTreeBidiMap</code>
67      */
68     public DualTreeBidiMap() {
69         super(new TreeMap (), new TreeMap ());
70         this.comparator = null;
71     }
72
73     /**
74      * Constructs a <code>DualTreeBidiMap</code> and copies the mappings from
75      * specified <code>Map</code>.
76      *
77      * @param map the map whose mappings are to be placed in this map
78      */
79     public DualTreeBidiMap(Map map) {
80         super(new TreeMap (), new TreeMap ());
81         putAll(map);
82         this.comparator = null;
83     }
84
85     /**
86      * Constructs a <code>DualTreeBidiMap</code> using the specified Comparator.
87      *
88      * @param comparator the Comparator
89      */
90     public DualTreeBidiMap(Comparator comparator) {
91         super(new TreeMap (comparator), new TreeMap (comparator));
92         this.comparator = comparator;
93     }
94
95     /**
96      * Constructs a <code>DualTreeBidiMap</code> that decorates the specified maps.
97      *
98      * @param normalMap the normal direction map
99      * @param reverseMap the reverse direction map
100      * @param inverseBidiMap the inverse BidiMap
101      */
102     protected DualTreeBidiMap(Map normalMap, Map reverseMap, BidiMap inverseBidiMap) {
103         super(normalMap, reverseMap, inverseBidiMap);
104         this.comparator = ((SortedMap ) normalMap).comparator();
105     }
106
107     /**
108      * Creates a new instance of this object.
109      *
110      * @param normalMap the normal direction map
111      * @param reverseMap the reverse direction map
112      * @param inverseMap the inverse BidiMap
113      * @return new bidi map
114      */
115     protected BidiMap createBidiMap(Map normalMap, Map reverseMap, BidiMap inverseMap) {
116         return new DualTreeBidiMap(normalMap, reverseMap, inverseMap);
117     }
118
119     //-----------------------------------------------------------------------
120 public Comparator comparator() {
121         return ((SortedMap ) maps[0]).comparator();
122     }
123
124     public Object firstKey() {
125         return ((SortedMap ) maps[0]).firstKey();
126     }
127
128     public Object lastKey() {
129         return ((SortedMap ) maps[0]).lastKey();
130     }
131
132     public Object nextKey(Object key) {
133         if (isEmpty()) {
134             return null;
135         }
136         if (maps[0] instanceof OrderedMap) {
137             return ((OrderedMap) maps[0]).nextKey(key);
138         }
139         SortedMap sm = (SortedMap ) maps[0];
140         Iterator it = sm.tailMap(key).keySet().iterator();
141         it.next();
142         if (it.hasNext()) {
143             return it.next();
144         }
145         return null;
146     }
147
148     public Object previousKey(Object key) {
149         if (isEmpty()) {
150             return null;
151         }
152         if (maps[0] instanceof OrderedMap) {
153             return ((OrderedMap) maps[0]).previousKey(key);
154         }
155         SortedMap sm = (SortedMap ) maps[0];
156         SortedMap hm = sm.headMap(key);
157         if (hm.isEmpty()) {
158             return null;
159         }
160         return hm.lastKey();
161     }
162
163     //-----------------------------------------------------------------------
164 /**
165      * Obtains an ordered map iterator.
166      * <p>
167      * This implementation copies the elements to an ArrayList in order to
168      * provide the forward/backward behaviour.
169      *
170      * @return a new ordered map iterator
171      */
172     public OrderedMapIterator orderedMapIterator() {
173         return new BidiOrderedMapIterator(this);
174     }
175
176     public SortedBidiMap inverseSortedBidiMap() {
177         return (SortedBidiMap) inverseBidiMap();
178     }
179
180     public OrderedBidiMap inverseOrderedBidiMap() {
181         return (OrderedBidiMap) inverseBidiMap();
182     }
183
184     //-----------------------------------------------------------------------
185 public SortedMap headMap(Object toKey) {
186         SortedMap sub = ((SortedMap ) maps[0]).headMap(toKey);
187         return new ViewMap(this, sub);
188     }
189
190     public SortedMap tailMap(Object fromKey) {
191         SortedMap sub = ((SortedMap ) maps[0]).tailMap(fromKey);
192         return new ViewMap(this, sub);
193     }
194
195     public SortedMap subMap(Object fromKey, Object toKey) {
196         SortedMap sub = ((SortedMap ) maps[0]).subMap(fromKey, toKey);
197         return new ViewMap(this, sub);
198     }
199     
200     //-----------------------------------------------------------------------
201 /**
202      * Internal sorted map view.
203      */
204     protected static class ViewMap extends AbstractSortedMapDecorator {
205         /** The parent bidi map. */
206         final DualTreeBidiMap bidi;
207         
208         /**
209          * Constructor.
210          * @param bidi the parent bidi map
211          * @param sm the subMap sorted map
212          */
213         protected ViewMap(DualTreeBidiMap bidi, SortedMap sm) {
214             // the implementation is not great here...
215 // use the maps[0] as the filtered map, but maps[1] as the full map
216 // this forces containsValue and clear to be overridden
217 super((SortedMap ) bidi.createBidiMap(sm, bidi.maps[1], bidi.inverseBidiMap));
218             this.bidi = (DualTreeBidiMap) map;
219         }
220         
221         public boolean containsValue(Object value) {
222             // override as default implementation jumps to [1]
223 return bidi.maps[0].containsValue(value);
224         }
225         
226         public void clear() {
227             // override as default implementation jumps to [1]
228 for (Iterator it = keySet().iterator(); it.hasNext();) {
229                 it.next();
230                 it.remove();
231             }
232         }
233         
234         public SortedMap headMap(Object toKey) {
235             return new ViewMap(bidi, super.headMap(toKey));
236         }
237
238         public SortedMap tailMap(Object fromKey) {
239             return new ViewMap(bidi, super.tailMap(fromKey));
240         }
241
242         public SortedMap subMap(Object fromKey, Object toKey) {
243             return new ViewMap(bidi, super.subMap(fromKey, toKey));
244         }
245     }
246
247     //-----------------------------------------------------------------------
248 /**
249      * Inner class MapIterator.
250      */
251     protected static class BidiOrderedMapIterator implements OrderedMapIterator, ResettableIterator {
252         
253         /** The parent map */
254         protected final AbstractDualBidiMap parent;
255         /** The iterator being decorated */
256         protected ListIterator iterator;
257         /** The last returned entry */
258         private Map.Entry last = null;
259         
260         /**
261          * Constructor.
262          * @param parent the parent map
263          */
264         protected BidiOrderedMapIterator(AbstractDualBidiMap parent) {
265             super();
266             this.parent = parent;
267             iterator = new ArrayList (parent.entrySet()).listIterator();
268         }
269         
270         public boolean hasNext() {
271             return iterator.hasNext();
272         }
273         
274         public Object next() {
275             last = (Map.Entry ) iterator.next();
276             return last.getKey();
277         }
278         
279         public boolean hasPrevious() {
280             return iterator.hasPrevious();
281         }
282         
283         public Object previous() {
284             last = (Map.Entry ) iterator.previous();
285             return last.getKey();
286         }
287         
288         public void remove() {
289             iterator.remove();
290             parent.remove(last.getKey());
291             last = null;
292         }
293         
294         public Object getKey() {
295             if (last == null) {
296                 throw new IllegalStateException ("Iterator getKey() can only be called after next() and before remove()");
297             }
298             return last.getKey();
299         }
300
301         public Object getValue() {
302             if (last == null) {
303                 throw new IllegalStateException ("Iterator getValue() can only be called after next() and before remove()");
304             }
305             return last.getValue();
306         }
307         
308         public Object setValue(Object value) {
309             if (last == null) {
310                 throw new IllegalStateException ("Iterator setValue() can only be called after next() and before remove()");
311             }
312             if (parent.maps[1].containsKey(value) &&
313                 parent.maps[1].get(value) != last.getKey()) {
314                 throw new IllegalArgumentException ("Cannot use setValue() when the object being set is already in the map");
315             }
316             return parent.put(last.getKey(), value);
317         }
318         
319         public void reset() {
320             iterator = new ArrayList (parent.entrySet()).listIterator();
321             last = null;
322         }
323         
324         public String toString() {
325             if (last != null) {
326                 return "MapIterator[" + getKey() + "=" + getValue() + "]";
327             } else {
328                 return "MapIterator[]";
329             }
330         }
331     }
332     
333     // Serialization
334 //-----------------------------------------------------------------------
335 private void writeObject(ObjectOutputStream out) throws IOException {
336         out.defaultWriteObject();
337         out.writeObject(maps[0]);
338     }
339
340     private void readObject(ObjectInputStream in) throws IOException , ClassNotFoundException {
341         in.defaultReadObject();
342         maps[0] = new TreeMap (comparator);
343         maps[1] = new TreeMap (comparator);
344         Map map = (Map ) in.readObject();
345         putAll(map);
346     }
347
348 }
349

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags