001: /*
002: * Copyright 2003-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.bidimap;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022: import java.util.ArrayList;
023: import java.util.Comparator;
024: import java.util.Iterator;
025: import java.util.ListIterator;
026: import java.util.Map;
027: import java.util.SortedMap;
028: import java.util.TreeMap;
029:
030: import org.apache.commons.collections.BidiMap;
031: import org.apache.commons.collections.OrderedBidiMap;
032: import org.apache.commons.collections.OrderedMap;
033: import org.apache.commons.collections.OrderedMapIterator;
034: import org.apache.commons.collections.ResettableIterator;
035: import org.apache.commons.collections.SortedBidiMap;
036: import org.apache.commons.collections.map.AbstractSortedMapDecorator;
037:
038: /**
039: * Implementation of <code>BidiMap</code> that uses two <code>TreeMap</code> instances.
040: * <p>
041: * The setValue() method on iterators will succeed only if the new value being set is
042: * not already in the bidimap.
043: * <p>
044: * When considering whether to use this class, the {@link TreeBidiMap} class should
045: * also be considered. It implements the interface using a dedicated design, and does
046: * not store each object twice, which can save on memory use.
047: * <p>
048: * NOTE: From Commons Collections 3.1, all subclasses will use <code>TreeMap</code>
049: * and the flawed <code>createMap</code> method is ignored.
050: *
051: * @since Commons Collections 3.0
052: * @version $Id: DualTreeBidiMap.java 155406 2005-02-26 12:55:26Z dirkv $
053: *
054: * @author Matthew Hawthorne
055: * @author Stephen Colebourne
056: */
057: public class DualTreeBidiMap extends AbstractDualBidiMap implements
058: SortedBidiMap, Serializable {
059:
060: /** Ensure serialization compatibility */
061: private static final long serialVersionUID = 721969328361809L;
062: /** The comparator to use */
063: protected final Comparator comparator;
064:
065: /**
066: * Creates an empty <code>DualTreeBidiMap</code>
067: */
068: public DualTreeBidiMap() {
069: super (new TreeMap(), new TreeMap());
070: this .comparator = null;
071: }
072:
073: /**
074: * Constructs a <code>DualTreeBidiMap</code> and copies the mappings from
075: * specified <code>Map</code>.
076: *
077: * @param map the map whose mappings are to be placed in this map
078: */
079: public DualTreeBidiMap(Map map) {
080: super (new TreeMap(), new TreeMap());
081: putAll(map);
082: this .comparator = null;
083: }
084:
085: /**
086: * Constructs a <code>DualTreeBidiMap</code> using the specified Comparator.
087: *
088: * @param comparator the Comparator
089: */
090: public DualTreeBidiMap(Comparator comparator) {
091: super (new TreeMap(comparator), new TreeMap(comparator));
092: this .comparator = comparator;
093: }
094:
095: /**
096: * Constructs a <code>DualTreeBidiMap</code> that decorates the specified maps.
097: *
098: * @param normalMap the normal direction map
099: * @param reverseMap the reverse direction map
100: * @param inverseBidiMap the inverse BidiMap
101: */
102: protected DualTreeBidiMap(Map normalMap, Map reverseMap,
103: 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,
117: BidiMap inverseMap) {
118: return new DualTreeBidiMap(normalMap, reverseMap, inverseMap);
119: }
120:
121: //-----------------------------------------------------------------------
122: public Comparator comparator() {
123: return ((SortedMap) maps[0]).comparator();
124: }
125:
126: public Object firstKey() {
127: return ((SortedMap) maps[0]).firstKey();
128: }
129:
130: public Object lastKey() {
131: return ((SortedMap) maps[0]).lastKey();
132: }
133:
134: public Object nextKey(Object key) {
135: if (isEmpty()) {
136: return null;
137: }
138: if (maps[0] instanceof OrderedMap) {
139: return ((OrderedMap) maps[0]).nextKey(key);
140: }
141: SortedMap sm = (SortedMap) maps[0];
142: Iterator it = sm.tailMap(key).keySet().iterator();
143: it.next();
144: if (it.hasNext()) {
145: return it.next();
146: }
147: return null;
148: }
149:
150: public Object previousKey(Object key) {
151: if (isEmpty()) {
152: return null;
153: }
154: if (maps[0] instanceof OrderedMap) {
155: return ((OrderedMap) maps[0]).previousKey(key);
156: }
157: SortedMap sm = (SortedMap) maps[0];
158: SortedMap hm = sm.headMap(key);
159: if (hm.isEmpty()) {
160: return null;
161: }
162: return hm.lastKey();
163: }
164:
165: //-----------------------------------------------------------------------
166: /**
167: * Obtains an ordered map iterator.
168: * <p>
169: * This implementation copies the elements to an ArrayList in order to
170: * provide the forward/backward behaviour.
171: *
172: * @return a new ordered map iterator
173: */
174: public OrderedMapIterator orderedMapIterator() {
175: return new BidiOrderedMapIterator(this );
176: }
177:
178: public SortedBidiMap inverseSortedBidiMap() {
179: return (SortedBidiMap) inverseBidiMap();
180: }
181:
182: public OrderedBidiMap inverseOrderedBidiMap() {
183: return (OrderedBidiMap) inverseBidiMap();
184: }
185:
186: //-----------------------------------------------------------------------
187: public SortedMap headMap(Object toKey) {
188: SortedMap sub = ((SortedMap) maps[0]).headMap(toKey);
189: return new ViewMap(this , sub);
190: }
191:
192: public SortedMap tailMap(Object fromKey) {
193: SortedMap sub = ((SortedMap) maps[0]).tailMap(fromKey);
194: return new ViewMap(this , sub);
195: }
196:
197: public SortedMap subMap(Object fromKey, Object toKey) {
198: SortedMap sub = ((SortedMap) maps[0]).subMap(fromKey, toKey);
199: return new ViewMap(this , sub);
200: }
201:
202: //-----------------------------------------------------------------------
203: /**
204: * Internal sorted map view.
205: */
206: protected static class ViewMap extends AbstractSortedMapDecorator {
207: /** The parent bidi map. */
208: final DualTreeBidiMap bidi;
209:
210: /**
211: * Constructor.
212: * @param bidi the parent bidi map
213: * @param sm the subMap sorted map
214: */
215: protected ViewMap(DualTreeBidiMap bidi, SortedMap sm) {
216: // the implementation is not great here...
217: // use the maps[0] as the filtered map, but maps[1] as the full map
218: // this forces containsValue and clear to be overridden
219: super ((SortedMap) bidi.createBidiMap(sm, bidi.maps[1],
220: bidi.inverseBidiMap));
221: this .bidi = (DualTreeBidiMap) map;
222: }
223:
224: public boolean containsValue(Object value) {
225: // override as default implementation jumps to [1]
226: return bidi.maps[0].containsValue(value);
227: }
228:
229: public void clear() {
230: // override as default implementation jumps to [1]
231: for (Iterator it = keySet().iterator(); it.hasNext();) {
232: it.next();
233: it.remove();
234: }
235: }
236:
237: public SortedMap headMap(Object toKey) {
238: return new ViewMap(bidi, super .headMap(toKey));
239: }
240:
241: public SortedMap tailMap(Object fromKey) {
242: return new ViewMap(bidi, super .tailMap(fromKey));
243: }
244:
245: public SortedMap subMap(Object fromKey, Object toKey) {
246: return new ViewMap(bidi, super .subMap(fromKey, toKey));
247: }
248: }
249:
250: //-----------------------------------------------------------------------
251: /**
252: * Inner class MapIterator.
253: */
254: protected static class BidiOrderedMapIterator implements
255: OrderedMapIterator, ResettableIterator {
256:
257: /** The parent map */
258: protected final AbstractDualBidiMap parent;
259: /** The iterator being decorated */
260: protected ListIterator iterator;
261: /** The last returned entry */
262: private Map.Entry last = null;
263:
264: /**
265: * Constructor.
266: * @param parent the parent map
267: */
268: protected BidiOrderedMapIterator(AbstractDualBidiMap parent) {
269: super ();
270: this .parent = parent;
271: iterator = new ArrayList(parent.entrySet()).listIterator();
272: }
273:
274: public boolean hasNext() {
275: return iterator.hasNext();
276: }
277:
278: public Object next() {
279: last = (Map.Entry) iterator.next();
280: return last.getKey();
281: }
282:
283: public boolean hasPrevious() {
284: return iterator.hasPrevious();
285: }
286:
287: public Object previous() {
288: last = (Map.Entry) iterator.previous();
289: return last.getKey();
290: }
291:
292: public void remove() {
293: iterator.remove();
294: parent.remove(last.getKey());
295: last = null;
296: }
297:
298: public Object getKey() {
299: if (last == null) {
300: throw new IllegalStateException(
301: "Iterator getKey() can only be called after next() and before remove()");
302: }
303: return last.getKey();
304: }
305:
306: public Object getValue() {
307: if (last == null) {
308: throw new IllegalStateException(
309: "Iterator getValue() can only be called after next() and before remove()");
310: }
311: return last.getValue();
312: }
313:
314: public Object setValue(Object value) {
315: if (last == null) {
316: throw new IllegalStateException(
317: "Iterator setValue() can only be called after next() and before remove()");
318: }
319: if (parent.maps[1].containsKey(value)
320: && parent.maps[1].get(value) != last.getKey()) {
321: throw new IllegalArgumentException(
322: "Cannot use setValue() when the object being set is already in the map");
323: }
324: return parent.put(last.getKey(), value);
325: }
326:
327: public void reset() {
328: iterator = new ArrayList(parent.entrySet()).listIterator();
329: last = null;
330: }
331:
332: public String toString() {
333: if (last != null) {
334: return "MapIterator[" + getKey() + "=" + getValue()
335: + "]";
336: } else {
337: return "MapIterator[]";
338: }
339: }
340: }
341:
342: // Serialization
343: //-----------------------------------------------------------------------
344: private void writeObject(ObjectOutputStream out) throws IOException {
345: out.defaultWriteObject();
346: out.writeObject(maps[0]);
347: }
348:
349: private void readObject(ObjectInputStream in) throws IOException,
350: ClassNotFoundException {
351: in.defaultReadObject();
352: maps[0] = new TreeMap(comparator);
353: maps[1] = new TreeMap(comparator);
354: Map map = (Map) in.readObject();
355: putAll(map);
356: }
357:
358: }
|