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 }