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.util.Collection;
019: import java.util.Iterator;
020: import java.util.Map;
021: import java.util.Set;
022:
023: import org.apache.commons.collections.BidiMap;
024: import org.apache.commons.collections.MapIterator;
025: import org.apache.commons.collections.ResettableIterator;
026: import org.apache.commons.collections.collection.AbstractCollectionDecorator;
027: import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
028: import org.apache.commons.collections.keyvalue.AbstractMapEntryDecorator;
029:
030: /**
031: * Abstract <code>BidiMap</code> implemented using two maps.
032: * <p>
033: * An implementation can be written simply by implementing the
034: * <code>createMap</code> method.
035: *
036: * @see DualHashBidiMap
037: * @see DualTreeBidiMap
038: * @since Commons Collections 3.0
039: * @version $Id: AbstractDualBidiMap.java 155406 2005-02-26 12:55:26Z dirkv $
040: *
041: * @author Matthew Hawthorne
042: * @author Stephen Colebourne
043: */
044: public abstract class AbstractDualBidiMap implements BidiMap {
045:
046: /**
047: * Delegate map array. The first map contains standard entries, and the
048: * second contains inverses.
049: */
050: protected transient final Map[] maps = new Map[2];
051: /**
052: * Inverse view of this map.
053: */
054: protected transient BidiMap inverseBidiMap = null;
055: /**
056: * View of the keys.
057: */
058: protected transient Set keySet = null;
059: /**
060: * View of the values.
061: */
062: protected transient Collection values = null;
063: /**
064: * View of the entries.
065: */
066: protected transient Set entrySet = null;
067:
068: /**
069: * Creates an empty map, initialised by <code>createMap</code>.
070: * <p>
071: * This constructor remains in place for deserialization.
072: * All other usage is deprecated in favour of
073: * {@link #AbstractDualBidiMap(Map, Map)}.
074: */
075: protected AbstractDualBidiMap() {
076: super ();
077: maps[0] = createMap();
078: maps[1] = createMap();
079: }
080:
081: /**
082: * Creates an empty map using the two maps specified as storage.
083: * <p>
084: * The two maps must be a matching pair, normal and reverse.
085: * They will typically both be empty.
086: * <p>
087: * Neither map is validated, so nulls may be passed in.
088: * If you choose to do this then the subclass constructor must populate
089: * the <code>maps[]</code> instance variable itself.
090: *
091: * @param normalMap the normal direction map
092: * @param reverseMap the reverse direction map
093: * @since Commons Collections 3.1
094: */
095: protected AbstractDualBidiMap(Map normalMap, Map reverseMap) {
096: super ();
097: maps[0] = normalMap;
098: maps[1] = reverseMap;
099: }
100:
101: /**
102: * Constructs a map that decorates the specified maps,
103: * used by the subclass <code>createBidiMap</code> implementation.
104: *
105: * @param normalMap the normal direction map
106: * @param reverseMap the reverse direction map
107: * @param inverseBidiMap the inverse BidiMap
108: */
109: protected AbstractDualBidiMap(Map normalMap, Map reverseMap,
110: BidiMap inverseBidiMap) {
111: super ();
112: maps[0] = normalMap;
113: maps[1] = reverseMap;
114: this .inverseBidiMap = inverseBidiMap;
115: }
116:
117: /**
118: * Creates a new instance of the map used by the subclass to store data.
119: * <p>
120: * This design is deeply flawed and has been deprecated.
121: * It relied on subclass data being used during a superclass constructor.
122: *
123: * @return the map to be used for internal storage
124: * @deprecated For constructors, use the new two map constructor.
125: * For deserialization, populate the maps array directly in readObject.
126: */
127: protected Map createMap() {
128: return null;
129: }
130:
131: /**
132: * Creates a new instance of the subclass.
133: *
134: * @param normalMap the normal direction map
135: * @param reverseMap the reverse direction map
136: * @param inverseMap this map, which is the inverse in the new map
137: * @return the inverse map
138: */
139: protected abstract BidiMap createBidiMap(Map normalMap,
140: Map reverseMap, BidiMap inverseMap);
141:
142: // Map delegation
143: //-----------------------------------------------------------------------
144: public Object get(Object key) {
145: return maps[0].get(key);
146: }
147:
148: public int size() {
149: return maps[0].size();
150: }
151:
152: public boolean isEmpty() {
153: return maps[0].isEmpty();
154: }
155:
156: public boolean containsKey(Object key) {
157: return maps[0].containsKey(key);
158: }
159:
160: public boolean equals(Object obj) {
161: return maps[0].equals(obj);
162: }
163:
164: public int hashCode() {
165: return maps[0].hashCode();
166: }
167:
168: public String toString() {
169: return maps[0].toString();
170: }
171:
172: // BidiMap changes
173: //-----------------------------------------------------------------------
174: public Object put(Object key, Object value) {
175: if (maps[0].containsKey(key)) {
176: maps[1].remove(maps[0].get(key));
177: }
178: if (maps[1].containsKey(value)) {
179: maps[0].remove(maps[1].get(value));
180: }
181: final Object obj = maps[0].put(key, value);
182: maps[1].put(value, key);
183: return obj;
184: }
185:
186: public void putAll(Map map) {
187: for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
188: Map.Entry entry = (Map.Entry) it.next();
189: put(entry.getKey(), entry.getValue());
190: }
191: }
192:
193: public Object remove(Object key) {
194: Object value = null;
195: if (maps[0].containsKey(key)) {
196: value = maps[0].remove(key);
197: maps[1].remove(value);
198: }
199: return value;
200: }
201:
202: public void clear() {
203: maps[0].clear();
204: maps[1].clear();
205: }
206:
207: public boolean containsValue(Object value) {
208: return maps[1].containsKey(value);
209: }
210:
211: // BidiMap
212: //-----------------------------------------------------------------------
213: /**
214: * Obtains a <code>MapIterator</code> over the map.
215: * The iterator implements <code>ResetableMapIterator</code>.
216: * This implementation relies on the entrySet iterator.
217: * <p>
218: * The setValue() methods only allow a new value to be set.
219: * If the value being set is already in the map, an IllegalArgumentException
220: * is thrown (as setValue cannot change the size of the map).
221: *
222: * @return a map iterator
223: */
224: public MapIterator mapIterator() {
225: return new BidiMapIterator(this );
226: }
227:
228: public Object getKey(Object value) {
229: return maps[1].get(value);
230: }
231:
232: public Object removeValue(Object value) {
233: Object key = null;
234: if (maps[1].containsKey(value)) {
235: key = maps[1].remove(value);
236: maps[0].remove(key);
237: }
238: return key;
239: }
240:
241: public BidiMap inverseBidiMap() {
242: if (inverseBidiMap == null) {
243: inverseBidiMap = createBidiMap(maps[1], maps[0], this );
244: }
245: return inverseBidiMap;
246: }
247:
248: // Map views
249: //-----------------------------------------------------------------------
250: /**
251: * Gets a keySet view of the map.
252: * Changes made on the view are reflected in the map.
253: * The set supports remove and clear but not add.
254: *
255: * @return the keySet view
256: */
257: public Set keySet() {
258: if (keySet == null) {
259: keySet = new KeySet(this );
260: }
261: return keySet;
262: }
263:
264: /**
265: * Creates a key set iterator.
266: * Subclasses can override this to return iterators with different properties.
267: *
268: * @param iterator the iterator to decorate
269: * @return the keySet iterator
270: */
271: protected Iterator createKeySetIterator(Iterator iterator) {
272: return new KeySetIterator(iterator, this );
273: }
274:
275: /**
276: * Gets a values view of the map.
277: * Changes made on the view are reflected in the map.
278: * The set supports remove and clear but not add.
279: *
280: * @return the values view
281: */
282: public Collection values() {
283: if (values == null) {
284: values = new Values(this );
285: }
286: return values;
287: }
288:
289: /**
290: * Creates a values iterator.
291: * Subclasses can override this to return iterators with different properties.
292: *
293: * @param iterator the iterator to decorate
294: * @return the values iterator
295: */
296: protected Iterator createValuesIterator(Iterator iterator) {
297: return new ValuesIterator(iterator, this );
298: }
299:
300: /**
301: * Gets an entrySet view of the map.
302: * Changes made on the set are reflected in the map.
303: * The set supports remove and clear but not add.
304: * <p>
305: * The Map Entry setValue() method only allow a new value to be set.
306: * If the value being set is already in the map, an IllegalArgumentException
307: * is thrown (as setValue cannot change the size of the map).
308: *
309: * @return the entrySet view
310: */
311: public Set entrySet() {
312: if (entrySet == null) {
313: entrySet = new EntrySet(this );
314: }
315: return entrySet;
316: }
317:
318: /**
319: * Creates an entry set iterator.
320: * Subclasses can override this to return iterators with different properties.
321: *
322: * @param iterator the iterator to decorate
323: * @return the entrySet iterator
324: */
325: protected Iterator createEntrySetIterator(Iterator iterator) {
326: return new EntrySetIterator(iterator, this );
327: }
328:
329: //-----------------------------------------------------------------------
330: /**
331: * Inner class View.
332: */
333: protected static abstract class View extends
334: AbstractCollectionDecorator {
335:
336: /** The parent map */
337: protected final AbstractDualBidiMap parent;
338:
339: /**
340: * Constructs a new view of the BidiMap.
341: *
342: * @param coll the collection view being decorated
343: * @param parent the parent BidiMap
344: */
345: protected View(Collection coll, AbstractDualBidiMap parent) {
346: super (coll);
347: this .parent = parent;
348: }
349:
350: public boolean removeAll(Collection coll) {
351: if (parent.isEmpty() || coll.isEmpty()) {
352: return false;
353: }
354: boolean modified = false;
355: Iterator it = iterator();
356: while (it.hasNext()) {
357: if (coll.contains(it.next())) {
358: it.remove();
359: modified = true;
360: }
361: }
362: return modified;
363: }
364:
365: public boolean retainAll(Collection coll) {
366: if (parent.isEmpty()) {
367: return false;
368: }
369: if (coll.isEmpty()) {
370: parent.clear();
371: return true;
372: }
373: boolean modified = false;
374: Iterator it = iterator();
375: while (it.hasNext()) {
376: if (coll.contains(it.next()) == false) {
377: it.remove();
378: modified = true;
379: }
380: }
381: return modified;
382: }
383:
384: public void clear() {
385: parent.clear();
386: }
387: }
388:
389: //-----------------------------------------------------------------------
390: /**
391: * Inner class KeySet.
392: */
393: protected static class KeySet extends View implements Set {
394:
395: /**
396: * Constructs a new view of the BidiMap.
397: *
398: * @param parent the parent BidiMap
399: */
400: protected KeySet(AbstractDualBidiMap parent) {
401: super (parent.maps[0].keySet(), parent);
402: }
403:
404: public Iterator iterator() {
405: return parent.createKeySetIterator(super .iterator());
406: }
407:
408: public boolean contains(Object key) {
409: return parent.maps[0].containsKey(key);
410: }
411:
412: public boolean remove(Object key) {
413: if (parent.maps[0].containsKey(key)) {
414: Object value = parent.maps[0].remove(key);
415: parent.maps[1].remove(value);
416: return true;
417: }
418: return false;
419: }
420: }
421:
422: /**
423: * Inner class KeySetIterator.
424: */
425: protected static class KeySetIterator extends
426: AbstractIteratorDecorator {
427:
428: /** The parent map */
429: protected final AbstractDualBidiMap parent;
430: /** The last returned key */
431: protected Object lastKey = null;
432: /** Whether remove is allowed at present */
433: protected boolean canRemove = false;
434:
435: /**
436: * Constructor.
437: * @param iterator the iterator to decorate
438: * @param parent the parent map
439: */
440: protected KeySetIterator(Iterator iterator,
441: AbstractDualBidiMap parent) {
442: super (iterator);
443: this .parent = parent;
444: }
445:
446: public Object next() {
447: lastKey = super .next();
448: canRemove = true;
449: return lastKey;
450: }
451:
452: public void remove() {
453: if (canRemove == false) {
454: throw new IllegalStateException(
455: "Iterator remove() can only be called once after next()");
456: }
457: Object value = parent.maps[0].get(lastKey);
458: super .remove();
459: parent.maps[1].remove(value);
460: lastKey = null;
461: canRemove = false;
462: }
463: }
464:
465: //-----------------------------------------------------------------------
466: /**
467: * Inner class Values.
468: */
469: protected static class Values extends View implements Set {
470:
471: /**
472: * Constructs a new view of the BidiMap.
473: *
474: * @param parent the parent BidiMap
475: */
476: protected Values(AbstractDualBidiMap parent) {
477: super (parent.maps[0].values(), parent);
478: }
479:
480: public Iterator iterator() {
481: return parent.createValuesIterator(super .iterator());
482: }
483:
484: public boolean contains(Object value) {
485: return parent.maps[1].containsKey(value);
486: }
487:
488: public boolean remove(Object value) {
489: if (parent.maps[1].containsKey(value)) {
490: Object key = parent.maps[1].remove(value);
491: parent.maps[0].remove(key);
492: return true;
493: }
494: return false;
495: }
496: }
497:
498: /**
499: * Inner class ValuesIterator.
500: */
501: protected static class ValuesIterator extends
502: AbstractIteratorDecorator {
503:
504: /** The parent map */
505: protected final AbstractDualBidiMap parent;
506: /** The last returned value */
507: protected Object lastValue = null;
508: /** Whether remove is allowed at present */
509: protected boolean canRemove = false;
510:
511: /**
512: * Constructor.
513: * @param iterator the iterator to decorate
514: * @param parent the parent map
515: */
516: protected ValuesIterator(Iterator iterator,
517: AbstractDualBidiMap parent) {
518: super (iterator);
519: this .parent = parent;
520: }
521:
522: public Object next() {
523: lastValue = super .next();
524: canRemove = true;
525: return lastValue;
526: }
527:
528: public void remove() {
529: if (canRemove == false) {
530: throw new IllegalStateException(
531: "Iterator remove() can only be called once after next()");
532: }
533: super .remove(); // removes from maps[0]
534: parent.maps[1].remove(lastValue);
535: lastValue = null;
536: canRemove = false;
537: }
538: }
539:
540: //-----------------------------------------------------------------------
541: /**
542: * Inner class EntrySet.
543: */
544: protected static class EntrySet extends View implements Set {
545:
546: /**
547: * Constructs a new view of the BidiMap.
548: *
549: * @param parent the parent BidiMap
550: */
551: protected EntrySet(AbstractDualBidiMap parent) {
552: super (parent.maps[0].entrySet(), parent);
553: }
554:
555: public Iterator iterator() {
556: return parent.createEntrySetIterator(super .iterator());
557: }
558:
559: public boolean remove(Object obj) {
560: if (obj instanceof Map.Entry == false) {
561: return false;
562: }
563: Map.Entry entry = (Map.Entry) obj;
564: Object key = entry.getKey();
565: if (parent.containsKey(key)) {
566: Object value = parent.maps[0].get(key);
567: if (value == null ? entry.getValue() == null : value
568: .equals(entry.getValue())) {
569: parent.maps[0].remove(key);
570: parent.maps[1].remove(value);
571: return true;
572: }
573: }
574: return false;
575: }
576: }
577:
578: /**
579: * Inner class EntrySetIterator.
580: */
581: protected static class EntrySetIterator extends
582: AbstractIteratorDecorator {
583:
584: /** The parent map */
585: protected final AbstractDualBidiMap parent;
586: /** The last returned entry */
587: protected Map.Entry last = null;
588: /** Whether remove is allowed at present */
589: protected boolean canRemove = false;
590:
591: /**
592: * Constructor.
593: * @param iterator the iterator to decorate
594: * @param parent the parent map
595: */
596: protected EntrySetIterator(Iterator iterator,
597: AbstractDualBidiMap parent) {
598: super (iterator);
599: this .parent = parent;
600: }
601:
602: public Object next() {
603: last = new MapEntry((Map.Entry) super .next(), parent);
604: canRemove = true;
605: return last;
606: }
607:
608: public void remove() {
609: if (canRemove == false) {
610: throw new IllegalStateException(
611: "Iterator remove() can only be called once after next()");
612: }
613: // store value as remove may change the entry in the decorator (eg.TreeMap)
614: Object value = last.getValue();
615: super .remove();
616: parent.maps[1].remove(value);
617: last = null;
618: canRemove = false;
619: }
620: }
621:
622: /**
623: * Inner class MapEntry.
624: */
625: protected static class MapEntry extends AbstractMapEntryDecorator {
626:
627: /** The parent map */
628: protected final AbstractDualBidiMap parent;
629:
630: /**
631: * Constructor.
632: * @param entry the entry to decorate
633: * @param parent the parent map
634: */
635: protected MapEntry(Map.Entry entry, AbstractDualBidiMap parent) {
636: super (entry);
637: this .parent = parent;
638: }
639:
640: public Object setValue(Object value) {
641: Object key = MapEntry.this .getKey();
642: if (parent.maps[1].containsKey(value)
643: && parent.maps[1].get(value) != key) {
644: throw new IllegalArgumentException(
645: "Cannot use setValue() when the object being set is already in the map");
646: }
647: parent.put(key, value);
648: final Object oldValue = super .setValue(value);
649: return oldValue;
650: }
651: }
652:
653: /**
654: * Inner class MapIterator.
655: */
656: protected static class BidiMapIterator implements MapIterator,
657: ResettableIterator {
658:
659: /** The parent map */
660: protected final AbstractDualBidiMap parent;
661: /** The iterator being wrapped */
662: protected Iterator iterator;
663: /** The last returned entry */
664: protected Map.Entry last = null;
665: /** Whether remove is allowed at present */
666: protected boolean canRemove = false;
667:
668: /**
669: * Constructor.
670: * @param parent the parent map
671: */
672: protected BidiMapIterator(AbstractDualBidiMap parent) {
673: super ();
674: this .parent = parent;
675: this .iterator = parent.maps[0].entrySet().iterator();
676: }
677:
678: public boolean hasNext() {
679: return iterator.hasNext();
680: }
681:
682: public Object next() {
683: last = (Map.Entry) iterator.next();
684: canRemove = true;
685: return last.getKey();
686: }
687:
688: public void remove() {
689: if (canRemove == false) {
690: throw new IllegalStateException(
691: "Iterator remove() can only be called once after next()");
692: }
693: // store value as remove may change the entry in the decorator (eg.TreeMap)
694: Object value = last.getValue();
695: iterator.remove();
696: parent.maps[1].remove(value);
697: last = null;
698: canRemove = false;
699: }
700:
701: public Object getKey() {
702: if (last == null) {
703: throw new IllegalStateException(
704: "Iterator getKey() can only be called after next() and before remove()");
705: }
706: return last.getKey();
707: }
708:
709: public Object getValue() {
710: if (last == null) {
711: throw new IllegalStateException(
712: "Iterator getValue() can only be called after next() and before remove()");
713: }
714: return last.getValue();
715: }
716:
717: public Object setValue(Object value) {
718: if (last == null) {
719: throw new IllegalStateException(
720: "Iterator setValue() can only be called after next() and before remove()");
721: }
722: if (parent.maps[1].containsKey(value)
723: && parent.maps[1].get(value) != last.getKey()) {
724: throw new IllegalArgumentException(
725: "Cannot use setValue() when the object being set is already in the map");
726: }
727: return parent.put(last.getKey(), value);
728: }
729:
730: public void reset() {
731: iterator = parent.maps[0].entrySet().iterator();
732: last = null;
733: canRemove = false;
734: }
735:
736: public String toString() {
737: if (last != null) {
738: return "MapIterator[" + getKey() + "=" + getValue()
739: + "]";
740: } else {
741: return "MapIterator[]";
742: }
743: }
744: }
745:
746: }
|