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