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 }