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