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