001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.api.util; 021 022 023import java.io.Externalizable; 024import java.io.IOException; 025import java.io.ObjectInput; 026import java.io.ObjectOutput; 027import java.util.AbstractCollection; 028import java.util.AbstractSet; 029import java.util.ArrayList; 030import java.util.Collection; 031import java.util.Collections; 032import java.util.ConcurrentModificationException; 033import java.util.HashMap; 034import java.util.Iterator; 035import java.util.List; 036import java.util.Map; 037import java.util.NoSuchElementException; 038import java.util.Set; 039 040import org.apache.directory.api.i18n.I18n; 041 042 043/** 044 * A map of objects whose mapping entries are sequenced based on the order in 045 * which they were added. This data structure has fast <i>O(1)</i> search time, 046 * deletion time, and insertion time. 047 * <p> 048 * Although this map is sequenced, it cannot implement {@link java.util.List} 049 * because of incompatible interface definitions. The remove methods in List and 050 * Map have different return values (see: {@link java.util.List#remove(Object)} 051 * and {@link java.util.Map#remove(Object)}). 052 * <p> 053 * This class is not thread safe. When a thread safe implementation is required, 054 * use {@link java.util.Collections#synchronizedMap(Map)} as it is documented, 055 * or use explicit synchronization controls. 056 * 057 * @since Commons Collections 2.0 058 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 059 */ 060@SuppressWarnings("rawtypes") 061public class SequencedHashMap implements Map, Cloneable, Externalizable 062{ 063 // add a serial version uid, so that if we change things in the future 064 // without changing the format, we can still deserialize properly. 065 private static final long serialVersionUID = 3380552487888102930L; 066 067 // constants to define what the iterator should return on "next" 068 private static final int KEY = 0; 069 070 private static final int VALUE = 1; 071 072 private static final int ENTRY = 2; 073 074 private static final int REMOVED_MASK = 0x80000000; 075 076 /** 077 * Sentinel used to hold the head and tail of the list of entries. 078 */ 079 private transient MapEntry sentinel; 080 081 /** 082 * Map of keys to entries 083 */ 084 private HashMap entries; 085 086 /** 087 * Holds the number of modifications that have occurred to the map, 088 * excluding modifications made through a collection view's iterator (e.g. 089 * entrySet().iterator().remove()). This is used to create a fail-fast 090 * behavior with the iterators. 091 */ 092 private transient long modCount = 0; 093 094 /** 095 * {@link java.util.Map.Entry} that doubles as a node in the linked list of 096 * sequenced mappings. 097 */ 098 private static final class MapEntry implements Map.Entry, KeyValue 099 { 100 // Note: This class cannot easily be made clonable. While the actual 101 // implementation of a clone would be simple, defining the semantics is 102 // difficult. If a shallow clone is implemented, then entry.next.prev != 103 // entry, which is un-intuitive and probably breaks all sorts of 104 // assumptions 105 // in code that uses this implementation. If a deep clone is 106 // implemented, then what happens when the linked list is cyclical (as 107 // is 108 // the case with SequencedHashMap)? It's impossible to know in the clone 109 // when to stop cloning, and thus you end up in a recursive loop, 110 // continuously cloning the "next" in the list. 111 112 private final Object key; 113 114 private Object value; 115 116 // package private to allow the SequencedHashMap to access and 117 // manipulate 118 // them. 119 MapEntry next = null; 120 121 MapEntry prev = null; 122 123 124 MapEntry( Object key, Object value ) 125 { 126 this.key = key; 127 this.value = value; 128 } 129 130 131 // per Map.Entry.getKey() 132 @Override 133 public Object getKey() 134 { 135 return this.key; 136 } 137 138 139 // per Map.Entry.getValue() 140 @Override 141 public Object getValue() 142 { 143 return this.value; 144 } 145 146 147 // per Map.Entry.setValue() 148 @Override 149 public Object setValue( Object newValue ) 150 { 151 Object oldValue = this.value; 152 this.value = newValue; 153 return oldValue; 154 } 155 156 157 /** 158 * Compute the instance's hash code 159 * @return the instance's hash code 160 */ 161 @Override 162 public int hashCode() 163 { 164 // implemented per api docs for Map.Entry.hashCode() 165 return ( getKey() == null ? 0 : getKey().hashCode() ) ^ ( getValue() == null ? 0 : getValue().hashCode() ); 166 } 167 168 169 @Override 170 public boolean equals( Object obj ) 171 { 172 if ( obj == null ) 173 { 174 return false; 175 } 176 177 if ( obj == this ) 178 { 179 return true; 180 } 181 182 if ( !( obj instanceof Map.Entry ) ) 183 { 184 return false; 185 } 186 187 Map.Entry other = ( Map.Entry ) obj; 188 189 // implemented per api docs for Map.Entry.equals(Object) 190 return ( getKey() == null ? other.getKey() == null : getKey().equals( other.getKey() ) ) && ( getValue() == null ? other 191 .getValue() == null 192 : getValue().equals( other.getValue() ) ); 193 } 194 195 196 @Override 197 public String toString() 198 { 199 return "[" + getKey() + "=" + getValue() + "]"; 200 } 201 } 202 203 204 /** 205 * Construct a new sequenced hash map with default initial size and load 206 * factor. 207 */ 208 public SequencedHashMap() 209 { 210 sentinel = createSentinel(); 211 entries = new HashMap(); 212 } 213 214 215 /** 216 * Construct a new sequenced hash map with the specified initial size and 217 * default load factor. 218 * 219 * @param initialSize 220 * the initial size for the hash table 221 * @see HashMap#HashMap(int) 222 */ 223 public SequencedHashMap( int initialSize ) 224 { 225 sentinel = createSentinel(); 226 entries = new HashMap( initialSize ); 227 } 228 229 230 /** 231 * Construct a new sequenced hash map with the specified initial size and 232 * load factor. 233 * 234 * @param initialSize 235 * the initial size for the hash table 236 * @param loadFactor 237 * the load factor for the hash table. 238 * @see HashMap#HashMap(int,float) 239 */ 240 public SequencedHashMap( int initialSize, float loadFactor ) 241 { 242 sentinel = createSentinel(); 243 entries = new HashMap( initialSize, loadFactor ); 244 } 245 246 247 /** 248 * Construct a new sequenced hash map and add all the elements in the 249 * specified map. The order in which the mappings in the specified map are 250 * added is defined by {@link #putAll(Map)}. 251 * 252 * @param m The original map 253 */ 254 public SequencedHashMap( Map m ) 255 { 256 this(); 257 putAll( m ); 258 } 259 260 261 /** 262 * Construct an empty sentinel used to hold the head (sentinel.next) and the 263 * tail (sentinel.prev) of the list. The sentinel has a <code>null</code> 264 * key and value. 265 * 266 * @return The created sentinel 267 */ 268 private static MapEntry createSentinel() 269 { 270 MapEntry s = new MapEntry( null, null ); 271 s.prev = s; 272 s.next = s; 273 return s; 274 } 275 276 277 /** 278 * Removes an internal entry from the linked list. This does not remove it 279 * from the underlying map. 280 * 281 * @param entry The entry to remove 282 */ 283 private void removeEntry( MapEntry entry ) 284 { 285 entry.next.prev = entry.prev; 286 entry.prev.next = entry.next; 287 } 288 289 290 /** 291 * Inserts a new internal entry to the tail of the linked list. This does 292 * not add the entry to the underlying map. 293 * 294 * @param entry The entry to insert 295 */ 296 private void insertEntry( MapEntry entry ) 297 { 298 entry.next = sentinel; 299 entry.prev = sentinel.prev; 300 sentinel.prev.next = entry; 301 sentinel.prev = entry; 302 } 303 304 305 // per Map.size() 306 307 /** 308 * Implements {@link Map#size()}. 309 */ 310 @Override 311 public int size() 312 { 313 // use the underlying Map's size since size is not maintained here. 314 return entries.size(); 315 } 316 317 318 /** 319 * Implements {@link Map#isEmpty()}. 320 */ 321 @Override 322 public boolean isEmpty() 323 { 324 // for quick check whether the map is entry, we can check the linked 325 // list 326 // and see if there's anything in it. 327 return sentinel.next == sentinel; 328 } 329 330 331 /** 332 * Implements {@link Map#containsKey(Object)}. 333 */ 334 @Override 335 public boolean containsKey( Object key ) 336 { 337 // pass on to underlying map implementation 338 return entries.containsKey( key ); 339 } 340 341 342 /** 343 * Implements {@link Map#containsValue(Object)}. 344 */ 345 @Override 346 public boolean containsValue( Object value ) 347 { 348 // unfortunately, we cannot just pass this call to the underlying map 349 // because we are mapping keys to entries, not keys to values. The 350 // underlying map doesn't have an efficient implementation anyway, so 351 // this 352 // isn't a big deal. 353 354 // do null comparison outside loop so we only need to do it once. This 355 // provides a tighter, more efficient loop at the expense of slight 356 // code duplication. 357 if ( value == null ) 358 { 359 for ( MapEntry pos = sentinel.next; pos != sentinel; pos = pos.next ) 360 { 361 if ( pos.getValue() == null ) 362 { 363 return true; 364 } 365 } 366 } 367 else 368 { 369 for ( MapEntry pos = sentinel.next; pos != sentinel; pos = pos.next ) 370 { 371 if ( value.equals( pos.getValue() ) ) 372 { 373 return true; 374 } 375 } 376 } 377 return false; 378 } 379 380 381 /** 382 * Implements {@link Map#get(Object)}. 383 */ 384 @Override 385 public Object get( Object o ) 386 { 387 // find entry for the specified key object 388 MapEntry entry = ( MapEntry ) entries.get( o ); 389 390 if ( entry == null ) 391 { 392 return null; 393 } 394 395 return entry.getValue(); 396 } 397 398 399 /** 400 * Return the entry for the "oldest" mapping. That is, return the Map.Entry 401 * for the key-value pair that was first put into the map when compared to 402 * all the other pairings in the map. This behavior is equivalent to using 403 * <code>entrySet().iterator().next()</code>, but this method provides an 404 * optimized implementation. 405 * 406 * @return The first entry in the sequence, or <code>null</code> if the 407 * map is empty. 408 */ 409 public Map.Entry getFirst() 410 { 411 // sentinel.next points to the "first" element of the sequence -- the 412 // head 413 // of the list, which is exactly the entry we need to return. We must 414 // test 415 // for an empty list though because we don't want to return the 416 // sentinel! 417 return isEmpty() ? null : sentinel.next; 418 } 419 420 421 /** 422 * Return the key for the "oldest" mapping. That is, return the key for the 423 * mapping that was first put into the map when compared to all the other 424 * objects in the map. This behavior is equivalent to using 425 * <code>getFirst().getKey()</code>, but this method provides a slightly 426 * optimized implementation. 427 * 428 * @return The first key in the sequence, or <code>null</code> if the map 429 * is empty. 430 */ 431 public Object getFirstKey() 432 { 433 // sentinel.next points to the "first" element of the sequence -- the 434 // head 435 // of the list -- and the requisite key is returned from it. An empty 436 // list 437 // does not need to be tested. In cases where the list is empty, 438 // sentinel.next will point to the sentinel itself which has a null key, 439 // which is exactly what we would want to return if the list is empty (a 440 // nice convenient way to avoid test for an empty list) 441 return sentinel.next.getKey(); 442 } 443 444 445 /** 446 * Return the value for the "oldest" mapping. That is, return the value for 447 * the mapping that was first put into the map when compared to all the 448 * other objects in the map. This behavior is equivalent to using 449 * <code>getFirst().getValue()</code>, but this method provides a 450 * slightly optimized implementation. 451 * 452 * @return The first value in the sequence, or <code>null</code> if the 453 * map is empty. 454 */ 455 public Object getFirstValue() 456 { 457 // sentinel.next points to the "first" element of the sequence -- the 458 // head 459 // of the list -- and the requisite value is returned from it. An empty 460 // list does not need to be tested. In cases where the list is empty, 461 // sentinel.next will point to the sentinel itself which has a null 462 // value, 463 // which is exactly what we would want to return if the list is empty (a 464 // nice convenient way to avoid test for an empty list) 465 return sentinel.next.getValue(); 466 } 467 468 469 /** 470 * Return the entry for the "newest" mapping. That is, return the Map.Entry 471 * for the key-value pair that was first put into the map when compared to 472 * all the other pairings in the map. The behavior is equivalent to: 473 * 474 * <pre> 475 * Object obj = null; 476 * Iterator iter = entrySet().iterator(); 477 * while ( iter.hasNext() ) 478 * { 479 * obj = iter.next(); 480 * } 481 * return ( Map.Entry ) obj; 482 * </pre> 483 * 484 * However, the implementation of this method ensures an O(1) lookup of the 485 * last key rather than O(n). 486 * 487 * @return The last entry in the sequence, or <code>null</code> if the map 488 * is empty. 489 */ 490 public Map.Entry getLast() 491 { 492 // sentinel.prev points to the "last" element of the sequence -- the 493 // tail 494 // of the list, which is exactly the entry we need to return. We must 495 // test 496 // for an empty list though because we don't want to return the 497 // sentinel! 498 return isEmpty() ? null : sentinel.prev; 499 } 500 501 502 /** 503 * Return the key for the "newest" mapping. That is, return the key for the 504 * mapping that was last put into the map when compared to all the other 505 * objects in the map. This behavior is equivalent to using 506 * <code>getLast().getKey()</code>, but this method provides a slightly 507 * optimized implementation. 508 * 509 * @return The last key in the sequence, or <code>null</code> if the map 510 * is empty. 511 */ 512 public Object getLastKey() 513 { 514 // sentinel.prev points to the "last" element of the sequence -- the 515 // tail 516 // of the list -- and the requisite key is returned from it. An empty 517 // list 518 // does not need to be tested. In cases where the list is empty, 519 // sentinel.prev will point to the sentinel itself which has a null key, 520 // which is exactly what we would want to return if the list is empty (a 521 // nice convenient way to avoid test for an empty list) 522 return sentinel.prev.getKey(); 523 } 524 525 526 /** 527 * Return the value for the "newest" mapping. That is, return the value for 528 * the mapping that was last put into the map when compared to all the other 529 * objects in the map. This behavior is equivalent to using 530 * <code>getLast().getValue()</code>, but this method provides a slightly 531 * optimized implementation. 532 * 533 * @return The last value in the sequence, or <code>null</code> if the map 534 * is empty. 535 */ 536 public Object getLastValue() 537 { 538 // sentinel.prev points to the "last" element of the sequence -- the 539 // tail 540 // of the list -- and the requisite value is returned from it. An empty 541 // list does not need to be tested. In cases where the list is empty, 542 // sentinel.prev will point to the sentinel itself which has a null 543 // value, 544 // which is exactly what we would want to return if the list is empty (a 545 // nice convenient way to avoid test for an empty list) 546 return sentinel.prev.getValue(); 547 } 548 549 550 /** 551 * Implements {@link Map#put(Object, Object)}. 552 */ 553 @SuppressWarnings("unchecked") 554 @Override 555 public Object put( Object key, Object value ) 556 { 557 modCount++; 558 559 Object oldValue = null; 560 561 // lookup the entry for the specified key 562 MapEntry e = ( MapEntry ) entries.get( key ); 563 564 // check to see if it already exists 565 if ( e != null ) 566 { 567 // remove from list so the entry gets "moved" to the end of list 568 removeEntry( e ); 569 570 // update value in map 571 oldValue = e.setValue( value ); 572 573 // Note: We do not update the key here because its unnecessary. We 574 // only 575 // do comparisons using equals(Object) and we know the specified key 576 // and 577 // that in the map are equal in that sense. This may cause a problem 578 // if 579 // someone does not implement their hashCode() and/or equals(Object) 580 // method properly and then use it as a key in this map. 581 } 582 else 583 { 584 // add new entry 585 e = new MapEntry( key, value ); 586 entries.put( key, e ); 587 } 588 // assert(entry in map, but not list) 589 590 // add to list 591 insertEntry( e ); 592 593 return oldValue; 594 } 595 596 597 /** 598 * Implements {@link Map#remove(Object)}. 599 */ 600 @Override 601 public Object remove( Object key ) 602 { 603 MapEntry e = removeImpl( key ); 604 return ( e == null ) ? null : e.getValue(); 605 } 606 607 608 /** 609 * Fully remove an entry from the map, returning the old entry or null if 610 * there was no such entry with the specified key. 611 * 612 * @param key The key to retreive 613 * @return The removed entry 614 */ 615 private MapEntry removeImpl( Object key ) 616 { 617 MapEntry e = ( MapEntry ) entries.remove( key ); 618 619 if ( e == null ) 620 { 621 return null; 622 } 623 624 modCount++; 625 removeEntry( e ); 626 627 return e; 628 } 629 630 631 /** 632 * Adds all the mappings in the specified map to this map, replacing any 633 * mappings that already exist (as per {@link Map#putAll(Map)}). The order 634 * in which the entries are added is determined by the iterator returned 635 * from {@link Map#entrySet()} for the specified map. 636 * 637 * @param t 638 * the mappings that should be added to this map. 639 * @throws NullPointerException 640 * if <code>t</code> is <code>null</code> 641 */ 642 @Override 643 public void putAll( Map t ) 644 { 645 Iterator iter = t.entrySet().iterator(); 646 while ( iter.hasNext() ) 647 { 648 Map.Entry entry = ( Map.Entry ) iter.next(); 649 put( entry.getKey(), entry.getValue() ); 650 } 651 } 652 653 654 /** 655 * Implements {@link Map#clear()}. 656 */ 657 @Override 658 public void clear() 659 { 660 modCount++; 661 662 // remove all from the underlying map 663 entries.clear(); 664 665 // and the list 666 sentinel.next = sentinel; 667 sentinel.prev = sentinel; 668 } 669 670 671 /** 672 * Implements {@link Map#equals(Object)}. 673 */ 674 @Override 675 public boolean equals( Object obj ) 676 { 677 if ( obj == null ) 678 { 679 return false; 680 } 681 682 if ( obj == this ) 683 { 684 return true; 685 } 686 687 if ( !( obj instanceof Map ) ) 688 { 689 return false; 690 } 691 692 return entrySet().equals( ( ( Map ) obj ).entrySet() ); 693 } 694 695 696 /** 697 * Implements {@link Map#hashCode()}. 698 * @return the instance's hash code 699 */ 700 @Override 701 public int hashCode() 702 { 703 return entrySet().hashCode(); 704 } 705 706 707 /** 708 * Provides a string representation of the entries within the map. The 709 * format of the returned string may change with different releases, so this 710 * method is suitable for debugging purposes only. If a specific format is 711 * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and 712 * iterate over the entries in the map formatting them as appropriate. 713 */ 714 @Override 715 public String toString() 716 { 717 StringBuilder buf = new StringBuilder(); 718 buf.append( '[' ); 719 720 for ( MapEntry pos = sentinel.next; pos != sentinel; pos = pos.next ) 721 { 722 buf.append( pos.getKey() ); 723 buf.append( '=' ); 724 buf.append( pos.getValue() ); 725 726 if ( pos.next != sentinel ) 727 { 728 buf.append( ',' ); 729 } 730 } 731 732 buf.append( ']' ); 733 734 return buf.toString(); 735 } 736 737 738 /** 739 * Implements {@link Map#keySet()}. 740 */ 741 @Override 742 public Set keySet() 743 { 744 return new AbstractSet() 745 { 746 747 // required impls 748 @Override 749 public Iterator iterator() 750 { 751 return new OrderedIterator( KEY ); 752 } 753 754 755 @Override 756 public boolean remove( Object o ) 757 { 758 MapEntry e = SequencedHashMap.this.removeImpl( o ); 759 760 return e != null; 761 } 762 763 764 // more efficient impls than abstract set 765 @Override 766 public void clear() 767 { 768 SequencedHashMap.this.clear(); 769 } 770 771 772 @Override 773 public int size() 774 { 775 return SequencedHashMap.this.size(); 776 } 777 778 779 @Override 780 public boolean isEmpty() 781 { 782 return SequencedHashMap.this.isEmpty(); 783 } 784 785 786 @Override 787 public boolean contains( Object o ) 788 { 789 return SequencedHashMap.this.containsKey( o ); 790 } 791 792 }; 793 } 794 795 796 /** 797 * Implements {@link Map#values()}. 798 */ 799 @Override 800 public Collection values() 801 { 802 return new AbstractCollection() 803 { 804 // required impl 805 @Override 806 public Iterator iterator() 807 { 808 return new OrderedIterator( VALUE ); 809 } 810 811 812 @Override 813 public boolean remove( Object value ) 814 { 815 // do null comparison outside loop so we only need to do it 816 // once. This 817 // provides a tighter, more efficient loop at the expense of 818 // slight 819 // code duplication. 820 if ( value == null ) 821 { 822 for ( MapEntry pos = sentinel.next; pos != sentinel; pos = pos.next ) 823 { 824 if ( pos.getValue() == null ) 825 { 826 SequencedHashMap.this.removeImpl( pos.getKey() ); 827 return true; 828 } 829 } 830 } 831 else 832 { 833 for ( MapEntry pos = sentinel.next; pos != sentinel; pos = pos.next ) 834 { 835 if ( value.equals( pos.getValue() ) ) 836 { 837 SequencedHashMap.this.removeImpl( pos.getKey() ); 838 return true; 839 } 840 } 841 } 842 843 return false; 844 } 845 846 847 // more efficient impls than abstract collection 848 @Override 849 public void clear() 850 { 851 SequencedHashMap.this.clear(); 852 } 853 854 855 @Override 856 public int size() 857 { 858 return SequencedHashMap.this.size(); 859 } 860 861 862 @Override 863 public boolean isEmpty() 864 { 865 return SequencedHashMap.this.isEmpty(); 866 } 867 868 869 @Override 870 public boolean contains( Object o ) 871 { 872 return SequencedHashMap.this.containsValue( o ); 873 } 874 }; 875 } 876 877 878 /** 879 * Implements {@link Map#entrySet()}. 880 */ 881 @Override 882 public Set entrySet() 883 { 884 return new AbstractSet() 885 { 886 // helper 887 private MapEntry findEntry( Object o ) 888 { 889 if ( o == null ) 890 { 891 return null; 892 } 893 894 if ( !( o instanceof Map.Entry ) ) 895 { 896 return null; 897 } 898 899 Map.Entry e = ( Map.Entry ) o; 900 MapEntry entry = ( MapEntry ) entries.get( e.getKey() ); 901 902 if ( entry != null && entry.equals( e ) ) 903 { 904 return entry; 905 } 906 else 907 { 908 return null; 909 } 910 } 911 912 913 // required impl 914 @Override 915 public Iterator iterator() 916 { 917 return new OrderedIterator( ENTRY ); 918 } 919 920 921 @Override 922 public boolean remove( Object o ) 923 { 924 MapEntry e = findEntry( o ); 925 926 if ( e == null ) 927 { 928 return false; 929 } 930 931 return SequencedHashMap.this.removeImpl( e.getKey() ) != null; 932 } 933 934 935 // more efficient impls than abstract collection 936 @Override 937 public void clear() 938 { 939 SequencedHashMap.this.clear(); 940 } 941 942 943 @Override 944 public int size() 945 { 946 return SequencedHashMap.this.size(); 947 } 948 949 950 @Override 951 public boolean isEmpty() 952 { 953 return SequencedHashMap.this.isEmpty(); 954 } 955 956 957 @Override 958 public boolean contains( Object o ) 959 { 960 return findEntry( o ) != null; 961 } 962 }; 963 } 964 965 private final class OrderedIterator implements Iterator 966 { 967 /** 968 * Holds the type that should be returned from the iterator. The value 969 * should be either KEY, VALUE, or ENTRY. To save a tiny bit of memory, 970 * this field is also used as a marker for when remove has been called 971 * on the current object to prevent a second remove on the same element. 972 * Essentially, if this value is negative (i.e. the bit specified by 973 * REMOVED_MASK is set), the current position has been removed. If 974 * positive, remove can still be called. 975 */ 976 private int returnType; 977 978 /** 979 * Holds the "current" position in the iterator. When pos.next is the 980 * sentinel, we've reached the end of the list. 981 */ 982 private MapEntry pos = sentinel; 983 984 /** 985 * Holds the expected modification count. If the actual modification 986 * count of the map differs from this value, then a concurrent 987 * modification has occurred. 988 */ 989 private long expectedModCount = modCount; 990 991 992 /** 993 * Construct an iterator over the sequenced elements in the order in 994 * which they were added. The {@link #next()} method returns the type 995 * specified by <code>returnType</code> which must be either KEY, 996 * VALUE, or ENTRY. 997 * 998 * @param returnType The type (KEY,VALUE, ENTRY) 999 */ 1000 OrderedIterator( int returnType ) 1001 { 1002 // Set the "removed" bit so that the iterator starts in a state 1003 // where "next" must be called before "remove" will succeed. 1004 this.returnType = returnType | REMOVED_MASK; 1005 } 1006 1007 1008 /** 1009 * Returns whether there is any additional elements in the iterator to 1010 * be returned. 1011 * 1012 * @return <code>true</code> if there are more elements left to be 1013 * returned from the iterator; <code>false</code> otherwise. 1014 */ 1015 @Override 1016 public boolean hasNext() 1017 { 1018 return pos.next != sentinel; 1019 } 1020 1021 1022 /** 1023 * Returns the next element from the iterator. 1024 * 1025 * @return the next element from the iterator. 1026 * @throws NoSuchElementException 1027 * if there are no more elements in the iterator. 1028 * @throws ConcurrentModificationException 1029 * if a modification occurs in the underlying map. 1030 */ 1031 @Override 1032 public Object next() 1033 { 1034 if ( modCount != expectedModCount ) 1035 { 1036 throw new ConcurrentModificationException(); 1037 } 1038 if ( pos.next == sentinel ) 1039 { 1040 throw new NoSuchElementException(); 1041 } 1042 1043 // clear the "removed" flag 1044 returnType = returnType & ~REMOVED_MASK; 1045 1046 pos = pos.next; 1047 switch ( returnType ) 1048 { 1049 case KEY: 1050 return pos.getKey(); 1051 case VALUE: 1052 return pos.getValue(); 1053 case ENTRY: 1054 return pos; 1055 default: 1056 // should never happen 1057 throw new Error( I18n.err( I18n.ERR_17030_BAD_ITERATOR_TYPE, returnType ) ); 1058 } 1059 1060 } 1061 1062 1063 /** 1064 * Removes the last element returned from the {@link #next()} method 1065 * from the sequenced map. 1066 * 1067 * @throws IllegalStateException 1068 * if there isn't a "last element" to be removed. That is, 1069 * if {@link #next()} has never been called, or if 1070 * {@link #remove()} was already called on the element. 1071 * @throws ConcurrentModificationException 1072 * if a modification occurs in the underlying map. 1073 */ 1074 @Override 1075 public void remove() 1076 { 1077 if ( ( returnType & REMOVED_MASK ) != 0 ) 1078 { 1079 throw new IllegalStateException( I18n.err( I18n.ERR_17031_REMOVE_FOLLOW_NEXT ) ); 1080 } 1081 if ( modCount != expectedModCount ) 1082 { 1083 throw new ConcurrentModificationException(); 1084 } 1085 1086 SequencedHashMap.this.removeImpl( pos.getKey() ); 1087 1088 // update the expected mod count for the remove operation 1089 expectedModCount++; 1090 1091 // set the removed flag 1092 returnType = returnType | REMOVED_MASK; 1093 } 1094 } 1095 1096 1097 // APIs maintained from previous version of SequencedHashMap for backwards 1098 // compatibility 1099 1100 /** 1101 * Creates a shallow copy of this object, preserving the internal structure 1102 * by copying only references. The keys and values themselves are not 1103 * <code>clone()</code>'d. The cloned object maintains the same sequence. 1104 * 1105 * @return A clone of this instance. 1106 * @throws CloneNotSupportedException 1107 * if clone is not supported by a subclass. 1108 */ 1109 @Override 1110 public Object clone() throws CloneNotSupportedException 1111 { 1112 // yes, calling super.clone() silly since we're just blowing away all 1113 // the stuff that super might be doing anyway, but for motivations on 1114 // this, see: 1115 // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html 1116 SequencedHashMap map = ( SequencedHashMap ) super.clone(); 1117 1118 // create new, empty sentinel 1119 map.sentinel = createSentinel(); 1120 1121 // create a new, empty entry map 1122 // note: this does not preserve the initial capacity and load factor. 1123 map.entries = new HashMap(); 1124 1125 // add all the mappings 1126 map.putAll( this ); 1127 1128 // Note: We cannot just clone the hashmap and sentinel because we must 1129 // duplicate our internal structures. Cloning those two will not clone 1130 // all 1131 // the other entries they reference, and so the cloned hash map will not 1132 // be 1133 // able to maintain internal consistency because there are two objects 1134 // with 1135 // the same entries. See discussion in the Entry implementation on why 1136 // we 1137 // cannot implement a clone of the Entry (and thus why we need to 1138 // recreate 1139 // everything). 1140 1141 return map; 1142 } 1143 1144 1145 /** 1146 * Returns the Map.Entry at the specified index 1147 * 1148 * @param index The index we are looking for 1149 * @return The found entry 1150 * @throws ArrayIndexOutOfBoundsException 1151 * if the specified index is <code>< 0</code> or 1152 * <code>></code> the size of the map. 1153 */ 1154 private Map.Entry getEntry( int index ) 1155 { 1156 MapEntry pos = sentinel; 1157 1158 if ( index < 0 ) 1159 { 1160 throw new ArrayIndexOutOfBoundsException( I18n.err( I18n.ERR_17032_BELOW_ZERO, index ) ); 1161 } 1162 1163 // loop to one before the position 1164 int i = -1; 1165 while ( i < ( index - 1 ) && pos.next != sentinel ) 1166 { 1167 i++; 1168 pos = pos.next; 1169 } 1170 // pos.next is the requested position 1171 1172 // if sentinel is next, past end of list 1173 if ( pos.next == sentinel ) 1174 { 1175 throw new ArrayIndexOutOfBoundsException( I18n.err( I18n.ERR_17033_ABOVE_OR_EQUAL, index, i + 1 ) ); 1176 } 1177 1178 return pos.next; 1179 } 1180 1181 1182 /** 1183 * Gets the key at the specified index. 1184 * 1185 * @param index 1186 * the index to retrieve 1187 * @return the key at the specified index, or null 1188 * @throws ArrayIndexOutOfBoundsException 1189 * if the <code>index</code> is <code>< 0</code> or 1190 * <code>></code> the size of the map. 1191 */ 1192 public Object get( int index ) 1193 { 1194 return getEntry( index ).getKey(); 1195 } 1196 1197 1198 /** 1199 * Gets the value at the specified index. 1200 * 1201 * @param index 1202 * the index to retrieve 1203 * @return the value at the specified index, or null 1204 * @throws ArrayIndexOutOfBoundsException 1205 * if the <code>index</code> is <code>< 0</code> or 1206 * <code>></code> the size of the map. 1207 */ 1208 public Object getValue( int index ) 1209 { 1210 return getEntry( index ).getValue(); 1211 } 1212 1213 1214 /** 1215 * Gets the index of the specified key. 1216 * 1217 * @param key 1218 * the key to find the index of 1219 * @return the index, or -1 if not found 1220 */ 1221 public int indexOf( Object key ) 1222 { 1223 MapEntry e = ( MapEntry ) entries.get( key ); 1224 if ( e == null ) 1225 { 1226 return -1; 1227 } 1228 int pos = 0; 1229 while ( e.prev != sentinel ) 1230 { 1231 pos++; 1232 e = e.prev; 1233 } 1234 return pos; 1235 } 1236 1237 1238 /** 1239 * Gets an iterator over the keys. 1240 * 1241 * @return an iterator over the keys 1242 */ 1243 public Iterator iterator() 1244 { 1245 return keySet().iterator(); 1246 } 1247 1248 1249 /** 1250 * Gets the last index of the specified key. 1251 * 1252 * @param key 1253 * the key to find the index of 1254 * @return the index, or -1 if not found 1255 */ 1256 public int lastIndexOf( Object key ) 1257 { 1258 // keys in a map are guaranteed to be unique 1259 return indexOf( key ); 1260 } 1261 1262 1263 /** 1264 * Returns a List view of the keys rather than a set view. The returned list 1265 * is unmodifiable. This is required because changes to the values of the 1266 * list (using {@link java.util.ListIterator#set(Object)}) will effectively 1267 * remove the value from the list and reinsert that value at the end of the 1268 * list, which is an unexpected side effect of changing the value of a list. 1269 * This occurs because changing the key, changes when the mapping is added 1270 * to the map and thus where it appears in the list. 1271 * <p> 1272 * An alternative to this method is to use {@link #keySet()} 1273 * 1274 * @see #keySet() 1275 * @return The ordered list of keys. 1276 */ 1277 @SuppressWarnings("unchecked") 1278 public List sequence() 1279 { 1280 List l = new ArrayList( size() ); 1281 Iterator iter = keySet().iterator(); 1282 while ( iter.hasNext() ) 1283 { 1284 l.add( iter.next() ); 1285 } 1286 1287 return Collections.unmodifiableList( l ); 1288 } 1289 1290 1291 /** 1292 * Removes the element at the specified index. 1293 * 1294 * @param index 1295 * The index of the object to remove. 1296 * @return The previous value corresponding the <code>key</code>, or 1297 * <code>null</code> if none existed. 1298 * @throws ArrayIndexOutOfBoundsException 1299 * if the <code>index</code> is <code>< 0</code> or 1300 * <code>></code> the size of the map. 1301 */ 1302 public Object remove( int index ) 1303 { 1304 return remove( get( index ) ); 1305 } 1306 1307 1308 // per Externalizable.readExternal(ObjectInput) 1309 1310 /** 1311 * Deserializes this map from the given stream. 1312 * 1313 * @param in 1314 * the stream to deserialize from 1315 * @throws IOException 1316 * if the stream raises it 1317 * @throws ClassNotFoundException 1318 * if the stream raises it 1319 */ 1320 @Override 1321 public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException 1322 { 1323 int size = in.readInt(); 1324 for ( int i = 0; i < size; i++ ) 1325 { 1326 Object key = in.readObject(); 1327 Object value = in.readObject(); 1328 put( key, value ); 1329 } 1330 } 1331 1332 1333 /** 1334 * Serializes this map to the given stream. 1335 * 1336 * @param out 1337 * the stream to serialize to 1338 * @throws IOException 1339 * if the stream raises it 1340 */ 1341 @Override 1342 public void writeExternal( ObjectOutput out ) throws IOException 1343 { 1344 out.writeInt( size() ); 1345 for ( MapEntry pos = sentinel.next; pos != sentinel; pos = pos.next ) 1346 { 1347 out.writeObject( pos.getKey() ); 1348 out.writeObject( pos.getValue() ); 1349 } 1350 } 1351}