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