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.map; 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.AbstractCollection; 024 import java.util.AbstractSet; 025 import java.util.Collection; 026 import java.util.Iterator; 027 import java.util.Map; 028 import java.util.NoSuchElementException; 029 import java.util.Set; 030 031 import org.apache.commons.collections.IterableMap; 032 import org.apache.commons.collections.MapIterator; 033 import org.apache.commons.collections.ResettableIterator; 034 import org.apache.commons.collections.iterators.EmptyIterator; 035 import org.apache.commons.collections.iterators.EmptyMapIterator; 036 037 /** 038 * A <code>Map</code> implementation that stores data in simple fields until 039 * the size is greater than 3. 040 * <p> 041 * This map is designed for performance and can outstrip HashMap. 042 * It also has good garbage collection characteristics. 043 * <ul> 044 * <li>Optimised for operation at size 3 or less. 045 * <li>Still works well once size 3 exceeded. 046 * <li>Gets at size 3 or less are about 0-10% faster than HashMap, 047 * <li>Puts at size 3 or less are over 4 times faster than HashMap. 048 * <li>Performance 5% slower than HashMap once size 3 exceeded once. 049 * </ul> 050 * The design uses two distinct modes of operation - flat and delegate. 051 * While the map is size 3 or less, operations map straight onto fields using 052 * switch statements. Once size 4 is reached, the map switches to delegate mode 053 * and only switches back when cleared. In delegate mode, all operations are 054 * forwarded straight to a HashMap resulting in the 5% performance loss. 055 * <p> 056 * The performance gains on puts are due to not needing to create a Map Entry 057 * object. This is a large saving not only in performance but in garbage collection. 058 * <p> 059 * Whilst in flat mode this map is also easy for the garbage collector to dispatch. 060 * This is because it contains no complex objects or arrays which slow the progress. 061 * <p> 062 * Do not use <code>Flat3Map</code> if the size is likely to grow beyond 3. 063 * <p> 064 * <strong>Note that Flat3Map is not synchronized and is not thread-safe.</strong> 065 * If you wish to use this map from multiple threads concurrently, you must use 066 * appropriate synchronization. The simplest approach is to wrap this map 067 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 068 * exceptions when accessed by concurrent threads without synchronization. 069 * 070 * @since Commons Collections 3.0 071 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 072 * 073 * @author Stephen Colebourne 074 */ 075 public class Flat3Map implements IterableMap, Serializable, Cloneable { 076 077 /** Serialization version */ 078 private static final long serialVersionUID = -6701087419741928296L; 079 080 /** The size of the map, used while in flat mode */ 081 private transient int size; 082 /** Hash, used while in flat mode */ 083 private transient int hash1; 084 /** Hash, used while in flat mode */ 085 private transient int hash2; 086 /** Hash, used while in flat mode */ 087 private transient int hash3; 088 /** Key, used while in flat mode */ 089 private transient Object key1; 090 /** Key, used while in flat mode */ 091 private transient Object key2; 092 /** Key, used while in flat mode */ 093 private transient Object key3; 094 /** Value, used while in flat mode */ 095 private transient Object value1; 096 /** Value, used while in flat mode */ 097 private transient Object value2; 098 /** Value, used while in flat mode */ 099 private transient Object value3; 100 /** Map, used while in delegate mode */ 101 private transient AbstractHashedMap delegateMap; 102 103 /** 104 * Constructor. 105 */ 106 public Flat3Map() { 107 super(); 108 } 109 110 /** 111 * Constructor copying elements from another map. 112 * 113 * @param map the map to copy 114 * @throws NullPointerException if the map is null 115 */ 116 public Flat3Map(Map map) { 117 super(); 118 putAll(map); 119 } 120 121 //----------------------------------------------------------------------- 122 /** 123 * Gets the value mapped to the key specified. 124 * 125 * @param key the key 126 * @return the mapped value, null if no match 127 */ 128 public Object get(Object key) { 129 if (delegateMap != null) { 130 return delegateMap.get(key); 131 } 132 if (key == null) { 133 switch (size) { 134 // drop through 135 case 3: 136 if (key3 == null) return value3; 137 case 2: 138 if (key2 == null) return value2; 139 case 1: 140 if (key1 == null) return value1; 141 } 142 } else { 143 if (size > 0) { 144 int hashCode = key.hashCode(); 145 switch (size) { 146 // drop through 147 case 3: 148 if (hash3 == hashCode && key.equals(key3)) return value3; 149 case 2: 150 if (hash2 == hashCode && key.equals(key2)) return value2; 151 case 1: 152 if (hash1 == hashCode && key.equals(key1)) return value1; 153 } 154 } 155 } 156 return null; 157 } 158 159 /** 160 * Gets the size of the map. 161 * 162 * @return the size 163 */ 164 public int size() { 165 if (delegateMap != null) { 166 return delegateMap.size(); 167 } 168 return size; 169 } 170 171 /** 172 * Checks whether the map is currently empty. 173 * 174 * @return true if the map is currently size zero 175 */ 176 public boolean isEmpty() { 177 return (size() == 0); 178 } 179 180 //----------------------------------------------------------------------- 181 /** 182 * Checks whether the map contains the specified key. 183 * 184 * @param key the key to search for 185 * @return true if the map contains the key 186 */ 187 public boolean containsKey(Object key) { 188 if (delegateMap != null) { 189 return delegateMap.containsKey(key); 190 } 191 if (key == null) { 192 switch (size) { // drop through 193 case 3: 194 if (key3 == null) return true; 195 case 2: 196 if (key2 == null) return true; 197 case 1: 198 if (key1 == null) return true; 199 } 200 } else { 201 if (size > 0) { 202 int hashCode = key.hashCode(); 203 switch (size) { // drop through 204 case 3: 205 if (hash3 == hashCode && key.equals(key3)) return true; 206 case 2: 207 if (hash2 == hashCode && key.equals(key2)) return true; 208 case 1: 209 if (hash1 == hashCode && key.equals(key1)) return true; 210 } 211 } 212 } 213 return false; 214 } 215 216 /** 217 * Checks whether the map contains the specified value. 218 * 219 * @param value the value to search for 220 * @return true if the map contains the key 221 */ 222 public boolean containsValue(Object value) { 223 if (delegateMap != null) { 224 return delegateMap.containsValue(value); 225 } 226 if (value == null) { // drop through 227 switch (size) { 228 case 3: 229 if (value3 == null) return true; 230 case 2: 231 if (value2 == null) return true; 232 case 1: 233 if (value1 == null) return true; 234 } 235 } else { 236 switch (size) { // drop through 237 case 3: 238 if (value.equals(value3)) return true; 239 case 2: 240 if (value.equals(value2)) return true; 241 case 1: 242 if (value.equals(value1)) return true; 243 } 244 } 245 return false; 246 } 247 248 //----------------------------------------------------------------------- 249 /** 250 * Puts a key-value mapping into this map. 251 * 252 * @param key the key to add 253 * @param value the value to add 254 * @return the value previously mapped to this key, null if none 255 */ 256 public Object put(Object key, Object value) { 257 if (delegateMap != null) { 258 return delegateMap.put(key, value); 259 } 260 // change existing mapping 261 if (key == null) { 262 switch (size) { // drop through 263 case 3: 264 if (key3 == null) { 265 Object old = value3; 266 value3 = value; 267 return old; 268 } 269 case 2: 270 if (key2 == null) { 271 Object old = value2; 272 value2 = value; 273 return old; 274 } 275 case 1: 276 if (key1 == null) { 277 Object old = value1; 278 value1 = value; 279 return old; 280 } 281 } 282 } else { 283 if (size > 0) { 284 int hashCode = key.hashCode(); 285 switch (size) { // drop through 286 case 3: 287 if (hash3 == hashCode && key.equals(key3)) { 288 Object old = value3; 289 value3 = value; 290 return old; 291 } 292 case 2: 293 if (hash2 == hashCode && key.equals(key2)) { 294 Object old = value2; 295 value2 = value; 296 return old; 297 } 298 case 1: 299 if (hash1 == hashCode && key.equals(key1)) { 300 Object old = value1; 301 value1 = value; 302 return old; 303 } 304 } 305 } 306 } 307 308 // add new mapping 309 switch (size) { 310 default: 311 convertToMap(); 312 delegateMap.put(key, value); 313 return null; 314 case 2: 315 hash3 = (key == null ? 0 : key.hashCode()); 316 key3 = key; 317 value3 = value; 318 break; 319 case 1: 320 hash2 = (key == null ? 0 : key.hashCode()); 321 key2 = key; 322 value2 = value; 323 break; 324 case 0: 325 hash1 = (key == null ? 0 : key.hashCode()); 326 key1 = key; 327 value1 = value; 328 break; 329 } 330 size++; 331 return null; 332 } 333 334 /** 335 * Puts all the values from the specified map into this map. 336 * 337 * @param map the map to add 338 * @throws NullPointerException if the map is null 339 */ 340 public void putAll(Map map) { 341 int size = map.size(); 342 if (size == 0) { 343 return; 344 } 345 if (delegateMap != null) { 346 delegateMap.putAll(map); 347 return; 348 } 349 if (size < 4) { 350 for (Iterator it = map.entrySet().iterator(); it.hasNext();) { 351 Map.Entry entry = (Map.Entry) it.next(); 352 put(entry.getKey(), entry.getValue()); 353 } 354 } else { 355 convertToMap(); 356 delegateMap.putAll(map); 357 } 358 } 359 360 /** 361 * Converts the flat map data to a map. 362 */ 363 private void convertToMap() { 364 delegateMap = createDelegateMap(); 365 switch (size) { // drop through 366 case 3: 367 delegateMap.put(key3, value3); 368 case 2: 369 delegateMap.put(key2, value2); 370 case 1: 371 delegateMap.put(key1, value1); 372 } 373 374 size = 0; 375 hash1 = hash2 = hash3 = 0; 376 key1 = key2 = key3 = null; 377 value1 = value2 = value3 = null; 378 } 379 380 /** 381 * Create an instance of the map used for storage when in delegation mode. 382 * <p> 383 * This can be overridden by subclasses to provide a different map implementation. 384 * Not every AbstractHashedMap is suitable, identity and reference based maps 385 * would be poor choices. 386 * 387 * @return a new AbstractHashedMap or subclass 388 * @since Commons Collections 3.1 389 */ 390 protected AbstractHashedMap createDelegateMap() { 391 return new HashedMap(); 392 } 393 394 /** 395 * Removes the specified mapping from this map. 396 * 397 * @param key the mapping to remove 398 * @return the value mapped to the removed key, null if key not in map 399 */ 400 public Object remove(Object key) { 401 if (delegateMap != null) { 402 return delegateMap.remove(key); 403 } 404 if (size == 0) { 405 return null; 406 } 407 if (key == null) { 408 switch (size) { // drop through 409 case 3: 410 if (key3 == null) { 411 Object old = value3; 412 hash3 = 0; 413 key3 = null; 414 value3 = null; 415 size = 2; 416 return old; 417 } 418 if (key2 == null) { 419 Object old = value3; 420 hash2 = hash3; 421 key2 = key3; 422 value2 = value3; 423 hash3 = 0; 424 key3 = null; 425 value3 = null; 426 size = 2; 427 return old; 428 } 429 if (key1 == null) { 430 Object old = value3; 431 hash1 = hash3; 432 key1 = key3; 433 value1 = value3; 434 hash3 = 0; 435 key3 = null; 436 value3 = null; 437 size = 2; 438 return old; 439 } 440 return null; 441 case 2: 442 if (key2 == null) { 443 Object old = value2; 444 hash2 = 0; 445 key2 = null; 446 value2 = null; 447 size = 1; 448 return old; 449 } 450 if (key1 == null) { 451 Object old = value2; 452 hash1 = hash2; 453 key1 = key2; 454 value1 = value2; 455 hash2 = 0; 456 key2 = null; 457 value2 = null; 458 size = 1; 459 return old; 460 } 461 return null; 462 case 1: 463 if (key1 == null) { 464 Object old = value1; 465 hash1 = 0; 466 key1 = null; 467 value1 = null; 468 size = 0; 469 return old; 470 } 471 } 472 } else { 473 if (size > 0) { 474 int hashCode = key.hashCode(); 475 switch (size) { // drop through 476 case 3: 477 if (hash3 == hashCode && key.equals(key3)) { 478 Object old = value3; 479 hash3 = 0; 480 key3 = null; 481 value3 = null; 482 size = 2; 483 return old; 484 } 485 if (hash2 == hashCode && key.equals(key2)) { 486 Object old = value3; 487 hash2 = hash3; 488 key2 = key3; 489 value2 = value3; 490 hash3 = 0; 491 key3 = null; 492 value3 = null; 493 size = 2; 494 return old; 495 } 496 if (hash1 == hashCode && key.equals(key1)) { 497 Object old = value3; 498 hash1 = hash3; 499 key1 = key3; 500 value1 = value3; 501 hash3 = 0; 502 key3 = null; 503 value3 = null; 504 size = 2; 505 return old; 506 } 507 return null; 508 case 2: 509 if (hash2 == hashCode && key.equals(key2)) { 510 Object old = value2; 511 hash2 = 0; 512 key2 = null; 513 value2 = null; 514 size = 1; 515 return old; 516 } 517 if (hash1 == hashCode && key.equals(key1)) { 518 Object old = value2; 519 hash1 = hash2; 520 key1 = key2; 521 value1 = value2; 522 hash2 = 0; 523 key2 = null; 524 value2 = null; 525 size = 1; 526 return old; 527 } 528 return null; 529 case 1: 530 if (hash1 == hashCode && key.equals(key1)) { 531 Object old = value1; 532 hash1 = 0; 533 key1 = null; 534 value1 = null; 535 size = 0; 536 return old; 537 } 538 } 539 } 540 } 541 return null; 542 } 543 544 /** 545 * Clears the map, resetting the size to zero and nullifying references 546 * to avoid garbage collection issues. 547 */ 548 public void clear() { 549 if (delegateMap != null) { 550 delegateMap.clear(); // should aid gc 551 delegateMap = null; // switch back to flat mode 552 } else { 553 size = 0; 554 hash1 = hash2 = hash3 = 0; 555 key1 = key2 = key3 = null; 556 value1 = value2 = value3 = null; 557 } 558 } 559 560 //----------------------------------------------------------------------- 561 /** 562 * Gets an iterator over the map. 563 * Changes made to the iterator affect this map. 564 * <p> 565 * A MapIterator returns the keys in the map. It also provides convenient 566 * methods to get the key and value, and set the value. 567 * It avoids the need to create an entrySet/keySet/values object. 568 * It also avoids creating the Map Entry object. 569 * 570 * @return the map iterator 571 */ 572 public MapIterator mapIterator() { 573 if (delegateMap != null) { 574 return delegateMap.mapIterator(); 575 } 576 if (size == 0) { 577 return EmptyMapIterator.INSTANCE; 578 } 579 return new FlatMapIterator(this); 580 } 581 582 /** 583 * FlatMapIterator 584 */ 585 static class FlatMapIterator implements MapIterator, ResettableIterator { 586 private final Flat3Map parent; 587 private int nextIndex = 0; 588 private boolean canRemove = false; 589 590 FlatMapIterator(Flat3Map parent) { 591 super(); 592 this.parent = parent; 593 } 594 595 public boolean hasNext() { 596 return (nextIndex < parent.size); 597 } 598 599 public Object next() { 600 if (hasNext() == false) { 601 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY); 602 } 603 canRemove = true; 604 nextIndex++; 605 return getKey(); 606 } 607 608 public void remove() { 609 if (canRemove == false) { 610 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID); 611 } 612 parent.remove(getKey()); 613 nextIndex--; 614 canRemove = false; 615 } 616 617 public Object getKey() { 618 if (canRemove == false) { 619 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); 620 } 621 switch (nextIndex) { 622 case 3: 623 return parent.key3; 624 case 2: 625 return parent.key2; 626 case 1: 627 return parent.key1; 628 } 629 throw new IllegalStateException("Invalid map index"); 630 } 631 632 public Object getValue() { 633 if (canRemove == false) { 634 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); 635 } 636 switch (nextIndex) { 637 case 3: 638 return parent.value3; 639 case 2: 640 return parent.value2; 641 case 1: 642 return parent.value1; 643 } 644 throw new IllegalStateException("Invalid map index"); 645 } 646 647 public Object setValue(Object value) { 648 if (canRemove == false) { 649 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); 650 } 651 Object old = getValue(); 652 switch (nextIndex) { 653 case 3: 654 parent.value3 = value; 655 case 2: 656 parent.value2 = value; 657 case 1: 658 parent.value1 = value; 659 } 660 return old; 661 } 662 663 public void reset() { 664 nextIndex = 0; 665 canRemove = false; 666 } 667 668 public String toString() { 669 if (canRemove) { 670 return "Iterator[" + getKey() + "=" + getValue() + "]"; 671 } else { 672 return "Iterator[]"; 673 } 674 } 675 } 676 677 /** 678 * Gets the entrySet view of the map. 679 * Changes made to the view affect this map. 680 * The Map Entry is not an independent object and changes as the 681 * iterator progresses. 682 * To simply iterate through the entries, use {@link #mapIterator()}. 683 * 684 * @return the entrySet view 685 */ 686 public Set entrySet() { 687 if (delegateMap != null) { 688 return delegateMap.entrySet(); 689 } 690 return new EntrySet(this); 691 } 692 693 /** 694 * EntrySet 695 */ 696 static class EntrySet extends AbstractSet { 697 private final Flat3Map parent; 698 699 EntrySet(Flat3Map parent) { 700 super(); 701 this.parent = parent; 702 } 703 704 public int size() { 705 return parent.size(); 706 } 707 708 public void clear() { 709 parent.clear(); 710 } 711 712 public boolean remove(Object obj) { 713 if (obj instanceof Map.Entry == false) { 714 return false; 715 } 716 Map.Entry entry = (Map.Entry) obj; 717 Object key = entry.getKey(); 718 boolean result = parent.containsKey(key); 719 parent.remove(key); 720 return result; 721 } 722 723 public Iterator iterator() { 724 if (parent.delegateMap != null) { 725 return parent.delegateMap.entrySet().iterator(); 726 } 727 if (parent.size() == 0) { 728 return EmptyIterator.INSTANCE; 729 } 730 return new EntrySetIterator(parent); 731 } 732 } 733 734 /** 735 * EntrySetIterator and MapEntry 736 */ 737 static class EntrySetIterator implements Iterator, Map.Entry { 738 private final Flat3Map parent; 739 private int nextIndex = 0; 740 private boolean canRemove = false; 741 742 EntrySetIterator(Flat3Map parent) { 743 super(); 744 this.parent = parent; 745 } 746 747 public boolean hasNext() { 748 return (nextIndex < parent.size); 749 } 750 751 public Object next() { 752 if (hasNext() == false) { 753 throw new NoSuchElementException(AbstractHashedMap.NO_NEXT_ENTRY); 754 } 755 canRemove = true; 756 nextIndex++; 757 return this; 758 } 759 760 public void remove() { 761 if (canRemove == false) { 762 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID); 763 } 764 parent.remove(getKey()); 765 nextIndex--; 766 canRemove = false; 767 } 768 769 public Object getKey() { 770 if (canRemove == false) { 771 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); 772 } 773 switch (nextIndex) { 774 case 3: 775 return parent.key3; 776 case 2: 777 return parent.key2; 778 case 1: 779 return parent.key1; 780 } 781 throw new IllegalStateException("Invalid map index"); 782 } 783 784 public Object getValue() { 785 if (canRemove == false) { 786 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); 787 } 788 switch (nextIndex) { 789 case 3: 790 return parent.value3; 791 case 2: 792 return parent.value2; 793 case 1: 794 return parent.value1; 795 } 796 throw new IllegalStateException("Invalid map index"); 797 } 798 799 public Object setValue(Object value) { 800 if (canRemove == false) { 801 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); 802 } 803 Object old = getValue(); 804 switch (nextIndex) { 805 case 3: 806 parent.value3 = value; 807 case 2: 808 parent.value2 = value; 809 case 1: 810 parent.value1 = value; 811 } 812 return old; 813 } 814 815 public boolean equals(Object obj) { 816 if (canRemove == false) { 817 return false; 818 } 819 if (obj instanceof Map.Entry == false) { 820 return false; 821 } 822 Map.Entry other = (Map.Entry) obj; 823 Object key = getKey(); 824 Object value = getValue(); 825 return (key == null ? other.getKey() == null : key.equals(other.getKey())) && 826 (value == null ? other.getValue() == null : value.equals(other.getValue())); 827 } 828 829 public int hashCode() { 830 if (canRemove == false) { 831 return 0; 832 } 833 Object key = getKey(); 834 Object value = getValue(); 835 return (key == null ? 0 : key.hashCode()) ^ 836 (value == null ? 0 : value.hashCode()); 837 } 838 839 public String toString() { 840 if (canRemove) { 841 return getKey() + "=" + getValue(); 842 } else { 843 return ""; 844 } 845 } 846 } 847 848 /** 849 * Gets the keySet view of the map. 850 * Changes made to the view affect this map. 851 * To simply iterate through the keys, use {@link #mapIterator()}. 852 * 853 * @return the keySet view 854 */ 855 public Set keySet() { 856 if (delegateMap != null) { 857 return delegateMap.keySet(); 858 } 859 return new KeySet(this); 860 } 861 862 /** 863 * KeySet 864 */ 865 static class KeySet extends AbstractSet { 866 private final Flat3Map parent; 867 868 KeySet(Flat3Map parent) { 869 super(); 870 this.parent = parent; 871 } 872 873 public int size() { 874 return parent.size(); 875 } 876 877 public void clear() { 878 parent.clear(); 879 } 880 881 public boolean contains(Object key) { 882 return parent.containsKey(key); 883 } 884 885 public boolean remove(Object key) { 886 boolean result = parent.containsKey(key); 887 parent.remove(key); 888 return result; 889 } 890 891 public Iterator iterator() { 892 if (parent.delegateMap != null) { 893 return parent.delegateMap.keySet().iterator(); 894 } 895 if (parent.size() == 0) { 896 return EmptyIterator.INSTANCE; 897 } 898 return new KeySetIterator(parent); 899 } 900 } 901 902 /** 903 * KeySetIterator 904 */ 905 static class KeySetIterator extends EntrySetIterator { 906 907 KeySetIterator(Flat3Map parent) { 908 super(parent); 909 } 910 911 public Object next() { 912 super.next(); 913 return getKey(); 914 } 915 } 916 917 /** 918 * Gets the values view of the map. 919 * Changes made to the view affect this map. 920 * To simply iterate through the values, use {@link #mapIterator()}. 921 * 922 * @return the values view 923 */ 924 public Collection values() { 925 if (delegateMap != null) { 926 return delegateMap.values(); 927 } 928 return new Values(this); 929 } 930 931 /** 932 * Values 933 */ 934 static class Values extends AbstractCollection { 935 private final Flat3Map parent; 936 937 Values(Flat3Map parent) { 938 super(); 939 this.parent = parent; 940 } 941 942 public int size() { 943 return parent.size(); 944 } 945 946 public void clear() { 947 parent.clear(); 948 } 949 950 public boolean contains(Object value) { 951 return parent.containsValue(value); 952 } 953 954 public Iterator iterator() { 955 if (parent.delegateMap != null) { 956 return parent.delegateMap.values().iterator(); 957 } 958 if (parent.size() == 0) { 959 return EmptyIterator.INSTANCE; 960 } 961 return new ValuesIterator(parent); 962 } 963 } 964 965 /** 966 * ValuesIterator 967 */ 968 static class ValuesIterator extends EntrySetIterator { 969 970 ValuesIterator(Flat3Map parent) { 971 super(parent); 972 } 973 974 public Object next() { 975 super.next(); 976 return getValue(); 977 } 978 } 979 980 //----------------------------------------------------------------------- 981 /** 982 * Write the map out using a custom routine. 983 */ 984 private void writeObject(ObjectOutputStream out) throws IOException { 985 out.defaultWriteObject(); 986 out.writeInt(size()); 987 for (MapIterator it = mapIterator(); it.hasNext();) { 988 out.writeObject(it.next()); // key 989 out.writeObject(it.getValue()); // value 990 } 991 } 992 993 /** 994 * Read the map in using a custom routine. 995 */ 996 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { 997 in.defaultReadObject(); 998 int count = in.readInt(); 999 if (count > 3) { 1000 delegateMap = createDelegateMap(); 1001 } 1002 for (int i = count; i > 0; i--) { 1003 put(in.readObject(), in.readObject()); 1004 } 1005 } 1006 1007 //----------------------------------------------------------------------- 1008 /** 1009 * Clones the map without cloning the keys or values. 1010 * 1011 * @return a shallow clone 1012 * @since Commons Collections 3.1 1013 */ 1014 public Object clone() { 1015 try { 1016 Flat3Map cloned = (Flat3Map) super.clone(); 1017 if (cloned.delegateMap != null) { 1018 cloned.delegateMap = (HashedMap) cloned.delegateMap.clone(); 1019 } 1020 return cloned; 1021 } catch (CloneNotSupportedException ex) { 1022 throw new InternalError(); 1023 } 1024 } 1025 1026 /** 1027 * Compares this map with another. 1028 * 1029 * @param obj the object to compare to 1030 * @return true if equal 1031 */ 1032 public boolean equals(Object obj) { 1033 if (obj == this) { 1034 return true; 1035 } 1036 if (delegateMap != null) { 1037 return delegateMap.equals(obj); 1038 } 1039 if (obj instanceof Map == false) { 1040 return false; 1041 } 1042 Map other = (Map) obj; 1043 if (size != other.size()) { 1044 return false; 1045 } 1046 if (size > 0) { 1047 Object otherValue = null; 1048 switch (size) { // drop through 1049 case 3: 1050 if (other.containsKey(key3) == false) { 1051 return false; 1052 } 1053 otherValue = other.get(key3); 1054 if (value3 == null ? otherValue != null : !value3.equals(otherValue)) { 1055 return false; 1056 } 1057 case 2: 1058 if (other.containsKey(key2) == false) { 1059 return false; 1060 } 1061 otherValue = other.get(key2); 1062 if (value2 == null ? otherValue != null : !value2.equals(otherValue)) { 1063 return false; 1064 } 1065 case 1: 1066 if (other.containsKey(key1) == false) { 1067 return false; 1068 } 1069 otherValue = other.get(key1); 1070 if (value1 == null ? otherValue != null : !value1.equals(otherValue)) { 1071 return false; 1072 } 1073 } 1074 } 1075 return true; 1076 } 1077 1078 /** 1079 * Gets the standard Map hashCode. 1080 * 1081 * @return the hash code defined in the Map interface 1082 */ 1083 public int hashCode() { 1084 if (delegateMap != null) { 1085 return delegateMap.hashCode(); 1086 } 1087 int total = 0; 1088 switch (size) { // drop through 1089 case 3: 1090 total += (hash3 ^ (value3 == null ? 0 : value3.hashCode())); 1091 case 2: 1092 total += (hash2 ^ (value2 == null ? 0 : value2.hashCode())); 1093 case 1: 1094 total += (hash1 ^ (value1 == null ? 0 : value1.hashCode())); 1095 } 1096 return total; 1097 } 1098 1099 /** 1100 * Gets the map as a String. 1101 * 1102 * @return a string version of the map 1103 */ 1104 public String toString() { 1105 if (delegateMap != null) { 1106 return delegateMap.toString(); 1107 } 1108 if (size == 0) { 1109 return "{}"; 1110 } 1111 StringBuffer buf = new StringBuffer(128); 1112 buf.append('{'); 1113 switch (size) { // drop through 1114 case 3: 1115 buf.append((key3 == this ? "(this Map)" : key3)); 1116 buf.append('='); 1117 buf.append((value3 == this ? "(this Map)" : value3)); 1118 buf.append(','); 1119 case 2: 1120 buf.append((key2 == this ? "(this Map)" : key2)); 1121 buf.append('='); 1122 buf.append((value2 == this ? "(this Map)" : value2)); 1123 buf.append(','); 1124 case 1: 1125 buf.append((key1 == this ? "(this Map)" : key1)); 1126 buf.append('='); 1127 buf.append((value1 == this ? "(this Map)" : value1)); 1128 } 1129 buf.append('}'); 1130 return buf.toString(); 1131 } 1132 1133 }