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 */ 020 package org.apache.directory.shared.ldap.util; 021 022 023 import java.io.Externalizable; 024 import java.io.IOException; 025 import java.io.ObjectInput; 026 import java.io.ObjectOutput; 027 import java.util.AbstractCollection; 028 import java.util.AbstractSet; 029 import java.util.ArrayList; 030 import java.util.Collection; 031 import java.util.Collections; 032 import java.util.ConcurrentModificationException; 033 import java.util.HashMap; 034 import java.util.Iterator; 035 import java.util.List; 036 import java.util.Map; 037 import java.util.NoSuchElementException; 038 import java.util.Set; 039 040 import 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 * @version $Revision: 919765 $ $Date: 2010-03-06 14:44:54 +0100 (Sat, 06 Mar 2010) $ 059 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 060 */ 061 public 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 unintuitive 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 final 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 public Object put( Object key, Object value ) 508 { 509 modCount++; 510 511 Object oldValue = null; 512 513 // lookup the entry for the specified key 514 Entry e = ( Entry ) entries.get( key ); 515 516 // check to see if it already exists 517 if ( e != null ) 518 { 519 // remove from list so the entry gets "moved" to the end of list 520 removeEntry( e ); 521 522 // update value in map 523 oldValue = e.setValue( value ); 524 525 // Note: We do not update the key here because its unnecessary. We 526 // only 527 // do comparisons using equals(Object) and we know the specified key 528 // and 529 // that in the map are equal in that sense. This may cause a problem 530 // if 531 // someone does not implement their hashCode() and/or equals(Object) 532 // method properly and then use it as a key in this map. 533 } 534 else 535 { 536 // add new entry 537 e = new Entry( key, value ); 538 entries.put( key, e ); 539 } 540 // assert(entry in map, but not list) 541 542 // add to list 543 insertEntry( e ); 544 545 return oldValue; 546 } 547 548 549 /** 550 * Implements {@link Map#remove(Object)}. 551 */ 552 public Object remove( Object key ) 553 { 554 Entry e = removeImpl( key ); 555 return ( e == null ) ? null : e.getValue(); 556 } 557 558 559 /** 560 * Fully remove an entry from the map, returning the old entry or null if 561 * there was no such entry with the specified key. 562 */ 563 private Entry removeImpl( Object key ) 564 { 565 Entry e = ( Entry ) entries.remove( key ); 566 if ( e == null ) 567 return null; 568 modCount++; 569 removeEntry( e ); 570 return e; 571 } 572 573 574 /** 575 * Adds all the mappings in the specified map to this map, replacing any 576 * mappings that already exist (as per {@link Map#putAll(Map)}). The order 577 * in which the entries are added is determined by the iterator returned 578 * from {@link Map#entrySet()} for the specified map. 579 * 580 * @param t 581 * the mappings that should be added to this map. 582 * @throws NullPointerException 583 * if <code>t</code> is <code>null</code> 584 */ 585 public void putAll( Map t ) 586 { 587 Iterator iter = t.entrySet().iterator(); 588 while ( iter.hasNext() ) 589 { 590 Map.Entry entry = ( Map.Entry ) iter.next(); 591 put( entry.getKey(), entry.getValue() ); 592 } 593 } 594 595 596 /** 597 * Implements {@link Map#clear()}. 598 */ 599 public void clear() 600 { 601 modCount++; 602 603 // remove all from the underlying map 604 entries.clear(); 605 606 // and the list 607 sentinel.next = sentinel; 608 sentinel.prev = sentinel; 609 } 610 611 612 /** 613 * Implements {@link Map#equals(Object)}. 614 */ 615 public boolean equals( Object obj ) 616 { 617 if ( obj == null ) 618 return false; 619 if ( obj == this ) 620 return true; 621 622 if ( !( obj instanceof Map ) ) 623 return false; 624 625 return entrySet().equals( ( ( Map ) obj ).entrySet() ); 626 } 627 628 629 /** 630 * Implements {@link Map#hashCode()}. 631 * @return the instance's hash code 632 */ 633 public int hashCode() 634 { 635 return entrySet().hashCode(); 636 } 637 638 639 /** 640 * Provides a string representation of the entries within the map. The 641 * format of the returned string may change with different releases, so this 642 * method is suitable for debugging purposes only. If a specific format is 643 * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and 644 * iterate over the entries in the map formatting them as appropriate. 645 */ 646 public String toString() 647 { 648 StringBuffer buf = new StringBuffer(); 649 buf.append( '[' ); 650 for ( Entry pos = sentinel.next; pos != sentinel; pos = pos.next ) 651 { 652 buf.append( pos.getKey() ); 653 buf.append( '=' ); 654 buf.append( pos.getValue() ); 655 if ( pos.next != sentinel ) 656 { 657 buf.append( ',' ); 658 } 659 } 660 buf.append( ']' ); 661 662 return buf.toString(); 663 } 664 665 666 /** 667 * Implements {@link Map#keySet()}. 668 */ 669 public Set keySet() 670 { 671 return new AbstractSet() 672 { 673 674 // required impls 675 public Iterator iterator() 676 { 677 return new OrderedIterator( KEY ); 678 } 679 680 681 public boolean remove( Object o ) 682 { 683 Entry e = SequencedHashMap.this.removeImpl( o ); 684 return ( e != null ); 685 } 686 687 688 // more efficient impls than abstract set 689 public void clear() 690 { 691 SequencedHashMap.this.clear(); 692 } 693 694 695 public int size() 696 { 697 return SequencedHashMap.this.size(); 698 } 699 700 701 public boolean isEmpty() 702 { 703 return SequencedHashMap.this.isEmpty(); 704 } 705 706 707 public boolean contains( Object o ) 708 { 709 return SequencedHashMap.this.containsKey( o ); 710 } 711 712 }; 713 } 714 715 716 /** 717 * Implements {@link Map#values()}. 718 */ 719 public Collection values() 720 { 721 return new AbstractCollection() 722 { 723 // required impl 724 public Iterator iterator() 725 { 726 return new OrderedIterator( VALUE ); 727 } 728 729 730 public boolean remove( Object value ) 731 { 732 // do null comparison outside loop so we only need to do it 733 // once. This 734 // provides a tighter, more efficient loop at the expense of 735 // slight 736 // code duplication. 737 if ( value == null ) 738 { 739 for ( Entry pos = sentinel.next; pos != sentinel; pos = pos.next ) 740 { 741 if ( pos.getValue() == null ) 742 { 743 SequencedHashMap.this.removeImpl( pos.getKey() ); 744 return true; 745 } 746 } 747 } 748 else 749 { 750 for ( Entry pos = sentinel.next; pos != sentinel; pos = pos.next ) 751 { 752 if ( value.equals( pos.getValue() ) ) 753 { 754 SequencedHashMap.this.removeImpl( pos.getKey() ); 755 return true; 756 } 757 } 758 } 759 760 return false; 761 } 762 763 764 // more efficient impls than abstract collection 765 public void clear() 766 { 767 SequencedHashMap.this.clear(); 768 } 769 770 771 public int size() 772 { 773 return SequencedHashMap.this.size(); 774 } 775 776 777 public boolean isEmpty() 778 { 779 return SequencedHashMap.this.isEmpty(); 780 } 781 782 783 public boolean contains( Object o ) 784 { 785 return SequencedHashMap.this.containsValue( o ); 786 } 787 }; 788 } 789 790 791 /** 792 * Implements {@link Map#entrySet()}. 793 */ 794 public Set entrySet() 795 { 796 return new AbstractSet() 797 { 798 // helper 799 private Entry findEntry( Object o ) 800 { 801 if ( o == null ) 802 return null; 803 if ( !( o instanceof Map.Entry ) ) 804 return null; 805 806 Map.Entry e = ( Map.Entry ) o; 807 Entry entry = ( Entry ) entries.get( e.getKey() ); 808 if ( entry != null && entry.equals( e ) ) 809 return entry; 810 else 811 return null; 812 } 813 814 815 // required impl 816 public Iterator iterator() 817 { 818 return new OrderedIterator( ENTRY ); 819 } 820 821 822 public boolean remove( Object o ) 823 { 824 Entry e = findEntry( o ); 825 if ( e == null ) 826 return false; 827 828 return SequencedHashMap.this.removeImpl( e.getKey() ) != null; 829 } 830 831 832 // more efficient impls than abstract collection 833 public void clear() 834 { 835 SequencedHashMap.this.clear(); 836 } 837 838 839 public int size() 840 { 841 return SequencedHashMap.this.size(); 842 } 843 844 845 public boolean isEmpty() 846 { 847 return SequencedHashMap.this.isEmpty(); 848 } 849 850 851 public boolean contains( Object o ) 852 { 853 return findEntry( o ) != null; 854 } 855 }; 856 } 857 858 // constants to define what the iterator should return on "next" 859 private static final int KEY = 0; 860 861 private static final int VALUE = 1; 862 863 private static final int ENTRY = 2; 864 865 private static final int REMOVED_MASK = 0x80000000; 866 867 private class OrderedIterator implements Iterator 868 { 869 /** 870 * Holds the type that should be returned from the iterator. The value 871 * should be either KEY, VALUE, or ENTRY. To save a tiny bit of memory, 872 * this field is also used as a marker for when remove has been called 873 * on the current object to prevent a second remove on the same element. 874 * Essentially, if this value is negative (i.e. the bit specified by 875 * REMOVED_MASK is set), the current position has been removed. If 876 * positive, remove can still be called. 877 */ 878 private int returnType; 879 880 /** 881 * Holds the "current" position in the iterator. When pos.next is the 882 * sentinel, we've reached the end of the list. 883 */ 884 private Entry pos = sentinel; 885 886 /** 887 * Holds the expected modification count. If the actual modification 888 * count of the map differs from this value, then a concurrent 889 * modification has occurred. 890 */ 891 private transient long expectedModCount = modCount; 892 893 894 /** 895 * Construct an iterator over the sequenced elements in the order in 896 * which they were added. The {@link #next()} method returns the type 897 * specified by <code>returnType</code> which must be either KEY, 898 * VALUE, or ENTRY. 899 */ 900 public OrderedIterator(int returnType) 901 { 902 // // Since this is a private inner class, nothing else should have 903 // // access to the constructor. Since we know the rest of the outer 904 // // class uses the iterator correctly, we can leave of the 905 // following 906 // // check: 907 // if(returnType >= 0 && returnType <= 2) { 908 // throw new IllegalArgumentException("Invalid iterator type"); 909 // } 910 911 // Set the "removed" bit so that the iterator starts in a state 912 // where 913 // "next" must be called before "remove" will succeed. 914 this.returnType = returnType | REMOVED_MASK; 915 } 916 917 918 /** 919 * Returns whether there is any additional elements in the iterator to 920 * be returned. 921 * 922 * @return <code>true</code> if there are more elements left to be 923 * returned from the iterator; <code>false</code> otherwise. 924 */ 925 public boolean hasNext() 926 { 927 return pos.next != sentinel; 928 } 929 930 931 /** 932 * Returns the next element from the iterator. 933 * 934 * @return the next element from the iterator. 935 * @throws NoSuchElementException 936 * if there are no more elements in the iterator. 937 * @throws ConcurrentModificationException 938 * if a modification occurs in the underlying map. 939 */ 940 public Object next() 941 { 942 if ( modCount != expectedModCount ) 943 { 944 throw new ConcurrentModificationException(); 945 } 946 if ( pos.next == sentinel ) 947 { 948 throw new NoSuchElementException(); 949 } 950 951 // clear the "removed" flag 952 returnType = returnType & ~REMOVED_MASK; 953 954 pos = pos.next; 955 switch ( returnType ) 956 { 957 case KEY: 958 return pos.getKey(); 959 case VALUE: 960 return pos.getValue(); 961 case ENTRY: 962 return pos; 963 default: 964 // should never happen 965 throw new Error( I18n.err( I18n.ERR_04425, returnType ) ); 966 } 967 968 } 969 970 971 /** 972 * Removes the last element returned from the {@link #next()} method 973 * from the sequenced map. 974 * 975 * @throws IllegalStateException 976 * if there isn't a "last element" to be removed. That is, 977 * if {@link #next()} has never been called, or if 978 * {@link #remove()} was already called on the element. 979 * @throws ConcurrentModificationException 980 * if a modification occurs in the underlying map. 981 */ 982 public void remove() 983 { 984 if ( ( returnType & REMOVED_MASK ) != 0 ) 985 { 986 throw new IllegalStateException( I18n.err( I18n.ERR_04426 ) ); 987 } 988 if ( modCount != expectedModCount ) 989 { 990 throw new ConcurrentModificationException(); 991 } 992 993 SequencedHashMap.this.removeImpl( pos.getKey() ); 994 995 // update the expected mod count for the remove operation 996 expectedModCount++; 997 998 // set the removed flag 999 returnType = returnType | REMOVED_MASK; 1000 } 1001 } 1002 1003 1004 // APIs maintained from previous version of SequencedHashMap for backwards 1005 // compatibility 1006 1007 /** 1008 * Creates a shallow copy of this object, preserving the internal structure 1009 * by copying only references. The keys and values themselves are not 1010 * <code>clone()</code>'d. The cloned object maintains the same sequence. 1011 * 1012 * @return A clone of this instance. 1013 * @throws CloneNotSupportedException 1014 * if clone is not supported by a subclass. 1015 */ 1016 public Object clone() throws CloneNotSupportedException 1017 { 1018 // yes, calling super.clone() silly since we're just blowing away all 1019 // the stuff that super might be doing anyway, but for motivations on 1020 // this, see: 1021 // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html 1022 SequencedHashMap map = ( SequencedHashMap ) super.clone(); 1023 1024 // create new, empty sentinel 1025 map.sentinel = createSentinel(); 1026 1027 // create a new, empty entry map 1028 // note: this does not preserve the initial capacity and load factor. 1029 map.entries = new HashMap(); 1030 1031 // add all the mappings 1032 map.putAll( this ); 1033 1034 // Note: We cannot just clone the hashmap and sentinel because we must 1035 // duplicate our internal structures. Cloning those two will not clone 1036 // all 1037 // the other entries they reference, and so the cloned hash map will not 1038 // be 1039 // able to maintain internal consistency because there are two objects 1040 // with 1041 // the same entries. See discussion in the Entry implementation on why 1042 // we 1043 // cannot implement a clone of the Entry (and thus why we need to 1044 // recreate 1045 // everything). 1046 1047 return map; 1048 } 1049 1050 1051 /** 1052 * Returns the Map.Entry at the specified index 1053 * 1054 * @throws ArrayIndexOutOfBoundsException 1055 * if the specified index is <code>< 0</code> or 1056 * <code>></code> the size of the map. 1057 */ 1058 private Map.Entry getEntry( int index ) 1059 { 1060 Entry pos = sentinel; 1061 1062 if ( index < 0 ) 1063 { 1064 throw new ArrayIndexOutOfBoundsException( I18n.err( I18n.ERR_04427, index ) ); 1065 } 1066 1067 // loop to one before the position 1068 int i = -1; 1069 while ( i < ( index - 1 ) && pos.next != sentinel ) 1070 { 1071 i++; 1072 pos = pos.next; 1073 } 1074 // pos.next is the requested position 1075 1076 // if sentinel is next, past end of list 1077 if ( pos.next == sentinel ) 1078 { 1079 throw new ArrayIndexOutOfBoundsException( I18n.err( I18n.ERR_04428, index, ( i + 1 ) ) ); 1080 } 1081 1082 return pos.next; 1083 } 1084 1085 1086 /** 1087 * Gets the key at the specified index. 1088 * 1089 * @param index 1090 * the index to retrieve 1091 * @return the key at the specified index, or null 1092 * @throws ArrayIndexOutOfBoundsException 1093 * if the <code>index</code> is <code>< 0</code> or 1094 * <code>></code> the size of the map. 1095 */ 1096 public Object get( int index ) 1097 { 1098 return getEntry( index ).getKey(); 1099 } 1100 1101 1102 /** 1103 * Gets the value at the specified index. 1104 * 1105 * @param index 1106 * the index to retrieve 1107 * @return the value at the specified index, or null 1108 * @throws ArrayIndexOutOfBoundsException 1109 * if the <code>index</code> is <code>< 0</code> or 1110 * <code>></code> the size of the map. 1111 */ 1112 public Object getValue( int index ) 1113 { 1114 return getEntry( index ).getValue(); 1115 } 1116 1117 1118 /** 1119 * Gets the index of the specified key. 1120 * 1121 * @param key 1122 * the key to find the index of 1123 * @return the index, or -1 if not found 1124 */ 1125 public int indexOf( Object key ) 1126 { 1127 Entry e = ( Entry ) entries.get( key ); 1128 if ( e == null ) 1129 { 1130 return -1; 1131 } 1132 int pos = 0; 1133 while ( e.prev != sentinel ) 1134 { 1135 pos++; 1136 e = e.prev; 1137 } 1138 return pos; 1139 } 1140 1141 1142 /** 1143 * Gets an iterator over the keys. 1144 * 1145 * @return an iterator over the keys 1146 */ 1147 public Iterator iterator() 1148 { 1149 return keySet().iterator(); 1150 } 1151 1152 1153 /** 1154 * Gets the last index of the specified key. 1155 * 1156 * @param key 1157 * the key to find the index of 1158 * @return the index, or -1 if not found 1159 */ 1160 public int lastIndexOf( Object key ) 1161 { 1162 // keys in a map are guaranteed to be unique 1163 return indexOf( key ); 1164 } 1165 1166 1167 /** 1168 * Returns a List view of the keys rather than a set view. The returned list 1169 * is unmodifiable. This is required because changes to the values of the 1170 * list (using {@link java.util.ListIterator#set(Object)}) will effectively 1171 * remove the value from the list and reinsert that value at the end of the 1172 * list, which is an unexpected side effect of changing the value of a list. 1173 * This occurs because changing the key, changes when the mapping is added 1174 * to the map and thus where it appears in the list. 1175 * <p> 1176 * An alternative to this method is to use {@link #keySet()} 1177 * 1178 * @see #keySet() 1179 * @return The ordered list of keys. 1180 */ 1181 public List sequence() 1182 { 1183 List l = new ArrayList( size() ); 1184 Iterator iter = keySet().iterator(); 1185 while ( iter.hasNext() ) 1186 { 1187 l.add( iter.next() ); 1188 } 1189 1190 return Collections.unmodifiableList( l ); 1191 } 1192 1193 1194 /** 1195 * Removes the element at the specified index. 1196 * 1197 * @param index 1198 * The index of the object to remove. 1199 * @return The previous value corresponding the <code>key</code>, or 1200 * <code>null</code> if none existed. 1201 * @throws ArrayIndexOutOfBoundsException 1202 * if the <code>index</code> is <code>< 0</code> or 1203 * <code>></code> the size of the map. 1204 */ 1205 public Object remove( int index ) 1206 { 1207 return remove( get( index ) ); 1208 } 1209 1210 1211 // per Externalizable.readExternal(ObjectInput) 1212 1213 /** 1214 * Deserializes this map from the given stream. 1215 * 1216 * @param in 1217 * the stream to deserialize from 1218 * @throws IOException 1219 * if the stream raises it 1220 * @throws ClassNotFoundException 1221 * if the stream raises it 1222 */ 1223 public void readExternal( ObjectInput in ) throws IOException, ClassNotFoundException 1224 { 1225 int size = in.readInt(); 1226 for ( int i = 0; i < size; i++ ) 1227 { 1228 Object key = in.readObject(); 1229 Object value = in.readObject(); 1230 put( key, value ); 1231 } 1232 } 1233 1234 1235 /** 1236 * Serializes this map to the given stream. 1237 * 1238 * @param out 1239 * the stream to serialize to 1240 * @throws IOException 1241 * if the stream raises it 1242 */ 1243 public void writeExternal( ObjectOutput out ) throws IOException 1244 { 1245 out.writeInt( size() ); 1246 for ( Entry pos = sentinel.next; pos != sentinel; pos = pos.next ) 1247 { 1248 out.writeObject( pos.getKey() ); 1249 out.writeObject( pos.getValue() ); 1250 } 1251 } 1252 1253 // add a serial version uid, so that if we change things in the future 1254 // without changing the format, we can still deserialize properly. 1255 private static final long serialVersionUID = 3380552487888102930L; 1256 1257 }