001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections; 018 019 import java.io.Externalizable; 020 import java.io.IOException; 021 import java.io.ObjectInput; 022 import java.io.ObjectOutput; 023 import java.util.AbstractCollection; 024 import java.util.AbstractSet; 025 import java.util.ArrayList; 026 import java.util.Collection; 027 import java.util.ConcurrentModificationException; 028 import java.util.HashMap; 029 import java.util.Iterator; 030 import java.util.List; 031 import java.util.Map; 032 import java.util.NoSuchElementException; 033 import java.util.Set; 034 035 import org.apache.commons.collections.list.UnmodifiableList; 036 037 /** 038 * A map of objects whose mapping entries are sequenced based on the order in 039 * which they were added. This data structure has fast <i>O(1)</i> search 040 * time, deletion time, and insertion time. 041 * <p> 042 * Although this map is sequenced, it cannot implement 043 * {@link java.util.List} because of incompatible interface definitions. 044 * The remove methods in List and Map have different return values 045 * (see: {@link java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}). 046 * <p> 047 * This class is not thread safe. When a thread safe implementation is 048 * required, use {@link java.util.Collections#synchronizedMap(Map)} as it is documented, 049 * or use explicit synchronization controls. 050 * 051 * @deprecated Replaced by LinkedMap and ListOrderedMap in map subpackage. Due to be removed in v4.0. 052 * @see org.apache.commons.collections.map.LinkedMap 053 * @see org.apache.commons.collections.map.ListOrderedMap 054 * @since Commons Collections 2.0 055 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 056 * 057 * @author Michael A. Smith 058 * @author Daniel Rall 059 * @author Henning P. Schmiedehausen 060 * @author Stephen Colebourne 061 */ 062 public class SequencedHashMap implements Map, Cloneable, Externalizable { 063 064 /** 065 * {@link java.util.Map.Entry} that doubles as a node in the linked list 066 * of sequenced mappings. 067 */ 068 private static class Entry implements Map.Entry, KeyValue { 069 // Note: This class cannot easily be made clonable. While the actual 070 // implementation of a clone would be simple, defining the semantics is 071 // difficult. If a shallow clone is implemented, then entry.next.prev != 072 // entry, which is unintuitive and probably breaks all sorts of assumptions 073 // in code that uses this implementation. If a deep clone is 074 // implemented, then what happens when the linked list is cyclical (as is 075 // the case with SequencedHashMap)? It's impossible to know in the clone 076 // when to stop cloning, and thus you end up in a recursive loop, 077 // continuously cloning the "next" in the list. 078 079 private final Object key; 080 private Object value; 081 082 // package private to allow the SequencedHashMap to access and manipulate 083 // them. 084 Entry next = null; 085 Entry prev = null; 086 087 public Entry(Object key, Object value) { 088 this.key = key; 089 this.value = value; 090 } 091 092 // per Map.Entry.getKey() 093 public Object getKey() { 094 return this.key; 095 } 096 097 // per Map.Entry.getValue() 098 public Object getValue() { 099 return this.value; 100 } 101 102 // per Map.Entry.setValue() 103 public Object setValue(Object value) { 104 Object oldValue = this.value; 105 this.value = value; 106 return oldValue; 107 } 108 109 public int hashCode() { 110 // implemented per api docs for Map.Entry.hashCode() 111 return ((getKey() == null ? 0 : getKey().hashCode()) ^ (getValue() == null ? 0 : getValue().hashCode())); 112 } 113 114 public boolean equals(Object obj) { 115 if (obj == null) 116 return false; 117 if (obj == this) 118 return true; 119 if (!(obj instanceof Map.Entry)) 120 return false; 121 122 Map.Entry other = (Map.Entry) obj; 123 124 // implemented per api docs for Map.Entry.equals(Object) 125 return ( 126 (getKey() == null ? other.getKey() == null : getKey().equals(other.getKey())) 127 && (getValue() == null ? other.getValue() == null : getValue().equals(other.getValue()))); 128 } 129 public String toString() { 130 return "[" + getKey() + "=" + getValue() + "]"; 131 } 132 } 133 134 /** 135 * Construct an empty sentinel used to hold the head (sentinel.next) and the 136 * tail (sentinel.prev) of the list. The sentinel has a <code>null</code> 137 * key and value. 138 */ 139 private static final Entry createSentinel() { 140 Entry s = new Entry(null, null); 141 s.prev = s; 142 s.next = s; 143 return s; 144 } 145 146 /** 147 * Sentinel used to hold the head and tail of the list of entries. 148 */ 149 private Entry sentinel; 150 151 /** 152 * Map of keys to entries 153 */ 154 private HashMap entries; 155 156 /** 157 * Holds the number of modifications that have occurred to the map, 158 * excluding modifications made through a collection view's iterator 159 * (e.g. entrySet().iterator().remove()). This is used to create a 160 * fail-fast behavior with the iterators. 161 */ 162 private transient long modCount = 0; 163 164 /** 165 * Construct a new sequenced hash map with default initial size and load 166 * factor. 167 */ 168 public SequencedHashMap() { 169 sentinel = createSentinel(); 170 entries = new HashMap(); 171 } 172 173 /** 174 * Construct a new sequenced hash map with the specified initial size and 175 * default load factor. 176 * 177 * @param initialSize the initial size for the hash table 178 * 179 * @see HashMap#HashMap(int) 180 */ 181 public SequencedHashMap(int initialSize) { 182 sentinel = createSentinel(); 183 entries = new HashMap(initialSize); 184 } 185 186 /** 187 * Construct a new sequenced hash map with the specified initial size and 188 * load factor. 189 * 190 * @param initialSize the initial size for the hash table 191 * 192 * @param loadFactor the load factor for the hash table. 193 * 194 * @see HashMap#HashMap(int,float) 195 */ 196 public SequencedHashMap(int initialSize, float loadFactor) { 197 sentinel = createSentinel(); 198 entries = new HashMap(initialSize, loadFactor); 199 } 200 201 /** 202 * Construct a new sequenced hash map and add all the elements in the 203 * specified map. The order in which the mappings in the specified map are 204 * added is defined by {@link #putAll(Map)}. 205 */ 206 public SequencedHashMap(Map m) { 207 this(); 208 putAll(m); 209 } 210 211 /** 212 * Removes an internal entry from the linked list. This does not remove 213 * it from the underlying map. 214 */ 215 private void removeEntry(Entry entry) { 216 entry.next.prev = entry.prev; 217 entry.prev.next = entry.next; 218 } 219 220 /** 221 * Inserts a new internal entry to the tail of the linked list. This does 222 * not add the entry to the underlying map. 223 */ 224 private void insertEntry(Entry entry) { 225 entry.next = sentinel; 226 entry.prev = sentinel.prev; 227 sentinel.prev.next = entry; 228 sentinel.prev = entry; 229 } 230 231 // per Map.size() 232 233 /** 234 * Implements {@link Map#size()}. 235 */ 236 public int size() { 237 // use the underlying Map's size since size is not maintained here. 238 return entries.size(); 239 } 240 241 /** 242 * Implements {@link Map#isEmpty()}. 243 */ 244 public boolean isEmpty() { 245 // for quick check whether the map is entry, we can check the linked list 246 // and see if there's anything in it. 247 return sentinel.next == sentinel; 248 } 249 250 /** 251 * Implements {@link Map#containsKey(Object)}. 252 */ 253 public boolean containsKey(Object key) { 254 // pass on to underlying map implementation 255 return entries.containsKey(key); 256 } 257 258 /** 259 * Implements {@link Map#containsValue(Object)}. 260 */ 261 public boolean containsValue(Object value) { 262 // unfortunately, we cannot just pass this call to the underlying map 263 // because we are mapping keys to entries, not keys to values. The 264 // underlying map doesn't have an efficient implementation anyway, so this 265 // isn't a big deal. 266 267 // do null comparison outside loop so we only need to do it once. This 268 // provides a tighter, more efficient loop at the expense of slight 269 // code duplication. 270 if (value == null) { 271 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 272 if (pos.getValue() == null) 273 return true; 274 } 275 } else { 276 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 277 if (value.equals(pos.getValue())) 278 return true; 279 } 280 } 281 return false; 282 } 283 284 /** 285 * Implements {@link Map#get(Object)}. 286 */ 287 public Object get(Object o) { 288 // find entry for the specified key object 289 Entry entry = (Entry) entries.get(o); 290 if (entry == null) 291 return null; 292 293 return entry.getValue(); 294 } 295 296 /** 297 * Return the entry for the "oldest" mapping. That is, return the Map.Entry 298 * for the key-value pair that was first put into the map when compared to 299 * all the other pairings in the map. This behavior is equivalent to using 300 * <code>entrySet().iterator().next()</code>, but this method provides an 301 * optimized implementation. 302 * 303 * @return The first entry in the sequence, or <code>null</code> if the 304 * map is empty. 305 */ 306 public Map.Entry getFirst() { 307 // sentinel.next points to the "first" element of the sequence -- the head 308 // of the list, which is exactly the entry we need to return. We must test 309 // for an empty list though because we don't want to return the sentinel! 310 return (isEmpty()) ? null : sentinel.next; 311 } 312 313 /** 314 * Return the key for the "oldest" mapping. That is, return the key for the 315 * mapping that was first put into the map when compared to all the other 316 * objects in the map. This behavior is equivalent to using 317 * <code>getFirst().getKey()</code>, but this method provides a slightly 318 * optimized implementation. 319 * 320 * @return The first key in the sequence, or <code>null</code> if the 321 * map is empty. 322 */ 323 public Object getFirstKey() { 324 // sentinel.next points to the "first" element of the sequence -- the head 325 // of the list -- and the requisite key is returned from it. An empty list 326 // does not need to be tested. In cases where the list is empty, 327 // sentinel.next will point to the sentinel itself which has a null key, 328 // which is exactly what we would want to return if the list is empty (a 329 // nice convenient way to avoid test for an empty list) 330 return sentinel.next.getKey(); 331 } 332 333 /** 334 * Return the value for the "oldest" mapping. That is, return the value for 335 * the mapping that was first put into the map when compared to all the 336 * other objects in the map. This behavior is equivalent to using 337 * <code>getFirst().getValue()</code>, but this method provides a slightly 338 * optimized implementation. 339 * 340 * @return The first value in the sequence, or <code>null</code> if the 341 * map is empty. 342 */ 343 public Object getFirstValue() { 344 // sentinel.next points to the "first" element of the sequence -- the head 345 // of the list -- and the requisite value is returned from it. An empty 346 // list does not need to be tested. In cases where the list is empty, 347 // sentinel.next will point to the sentinel itself which has a null value, 348 // which is exactly what we would want to return if the list is empty (a 349 // nice convenient way to avoid test for an empty list) 350 return sentinel.next.getValue(); 351 } 352 353 /** 354 * Return the entry for the "newest" 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. The behavior is equivalent to: 357 * 358 * <pre> 359 * Object obj = null; 360 * Iterator iter = entrySet().iterator(); 361 * while(iter.hasNext()) { 362 * obj = iter.next(); 363 * } 364 * return (Map.Entry)obj; 365 * </pre> 366 * 367 * However, the implementation of this method ensures an O(1) lookup of the 368 * last key rather than O(n). 369 * 370 * @return The last entry in the sequence, or <code>null</code> if the map 371 * is empty. 372 */ 373 public Map.Entry getLast() { 374 // sentinel.prev points to the "last" element of the sequence -- the tail 375 // of the list, which is exactly the entry we need to return. We must test 376 // for an empty list though because we don't want to return the sentinel! 377 return (isEmpty()) ? null : sentinel.prev; 378 } 379 380 /** 381 * Return the key for the "newest" mapping. That is, return the key for the 382 * mapping that was last put into the map when compared to all the other 383 * objects in the map. This behavior is equivalent to using 384 * <code>getLast().getKey()</code>, but this method provides a slightly 385 * optimized implementation. 386 * 387 * @return The last key in the sequence, or <code>null</code> if the map is 388 * empty. 389 */ 390 public Object getLastKey() { 391 // sentinel.prev points to the "last" element of the sequence -- the tail 392 // of the list -- and the requisite key is returned from it. An empty list 393 // does not need to be tested. In cases where the list is empty, 394 // sentinel.prev will point to the sentinel itself which has a null key, 395 // which is exactly what we would want to return if the list is empty (a 396 // nice convenient way to avoid test for an empty list) 397 return sentinel.prev.getKey(); 398 } 399 400 /** 401 * Return the value for the "newest" mapping. That is, return the value for 402 * the mapping that was last put into the map when compared to all the other 403 * objects in the map. This behavior is equivalent to using 404 * <code>getLast().getValue()</code>, but this method provides a slightly 405 * optimized implementation. 406 * 407 * @return The last value in the sequence, or <code>null</code> if the map 408 * is empty. 409 */ 410 public Object getLastValue() { 411 // sentinel.prev points to the "last" element of the sequence -- the tail 412 // of the list -- and the requisite value is returned from it. An empty 413 // list does not need to be tested. In cases where the list is empty, 414 // sentinel.prev will point to the sentinel itself which has a null value, 415 // which is exactly what we would want to return if the list is empty (a 416 // nice convenient way to avoid test for an empty list) 417 return sentinel.prev.getValue(); 418 } 419 420 /** 421 * Implements {@link Map#put(Object, Object)}. 422 */ 423 public Object put(Object key, Object value) { 424 modCount++; 425 426 Object oldValue = null; 427 428 // lookup the entry for the specified key 429 Entry e = (Entry) entries.get(key); 430 431 // check to see if it already exists 432 if (e != null) { 433 // remove from list so the entry gets "moved" to the end of list 434 removeEntry(e); 435 436 // update value in map 437 oldValue = e.setValue(value); 438 439 // Note: We do not update the key here because its unnecessary. We only 440 // do comparisons using equals(Object) and we know the specified key and 441 // that in the map are equal in that sense. This may cause a problem if 442 // someone does not implement their hashCode() and/or equals(Object) 443 // method properly and then use it as a key in this map. 444 } else { 445 // add new entry 446 e = new Entry(key, value); 447 entries.put(key, e); 448 } 449 // assert(entry in map, but not list) 450 451 // add to list 452 insertEntry(e); 453 454 return oldValue; 455 } 456 457 /** 458 * Implements {@link Map#remove(Object)}. 459 */ 460 public Object remove(Object key) { 461 Entry e = removeImpl(key); 462 return (e == null) ? null : e.getValue(); 463 } 464 465 /** 466 * Fully remove an entry from the map, returning the old entry or null if 467 * there was no such entry with the specified key. 468 */ 469 private Entry removeImpl(Object key) { 470 Entry e = (Entry) entries.remove(key); 471 if (e == null) 472 return null; 473 modCount++; 474 removeEntry(e); 475 return e; 476 } 477 478 /** 479 * Adds all the mappings in the specified map to this map, replacing any 480 * mappings that already exist (as per {@link Map#putAll(Map)}). The order 481 * in which the entries are added is determined by the iterator returned 482 * from {@link Map#entrySet()} for the specified map. 483 * 484 * @param t the mappings that should be added to this map. 485 * 486 * @throws NullPointerException if <code>t</code> is <code>null</code> 487 */ 488 public void putAll(Map t) { 489 Iterator iter = t.entrySet().iterator(); 490 while (iter.hasNext()) { 491 Map.Entry entry = (Map.Entry) iter.next(); 492 put(entry.getKey(), entry.getValue()); 493 } 494 } 495 496 /** 497 * Implements {@link Map#clear()}. 498 */ 499 public void clear() { 500 modCount++; 501 502 // remove all from the underlying map 503 entries.clear(); 504 505 // and the list 506 sentinel.next = sentinel; 507 sentinel.prev = sentinel; 508 } 509 510 /** 511 * Implements {@link Map#equals(Object)}. 512 */ 513 public boolean equals(Object obj) { 514 if (obj == null) 515 return false; 516 if (obj == this) 517 return true; 518 519 if (!(obj instanceof Map)) 520 return false; 521 522 return entrySet().equals(((Map) obj).entrySet()); 523 } 524 525 /** 526 * Implements {@link Map#hashCode()}. 527 */ 528 public int hashCode() { 529 return entrySet().hashCode(); 530 } 531 532 /** 533 * Provides a string representation of the entries within the map. The 534 * format of the returned string may change with different releases, so this 535 * method is suitable for debugging purposes only. If a specific format is 536 * required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and 537 * iterate over the entries in the map formatting them as appropriate. 538 */ 539 public String toString() { 540 StringBuffer buf = new StringBuffer(); 541 buf.append('['); 542 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 543 buf.append(pos.getKey()); 544 buf.append('='); 545 buf.append(pos.getValue()); 546 if (pos.next != sentinel) { 547 buf.append(','); 548 } 549 } 550 buf.append(']'); 551 552 return buf.toString(); 553 } 554 555 /** 556 * Implements {@link Map#keySet()}. 557 */ 558 public Set keySet() { 559 return new AbstractSet() { 560 561 // required impls 562 public Iterator iterator() { 563 return new OrderedIterator(KEY); 564 } 565 public boolean remove(Object o) { 566 Entry e = SequencedHashMap.this.removeImpl(o); 567 return (e != null); 568 } 569 570 // more efficient impls than abstract set 571 public void clear() { 572 SequencedHashMap.this.clear(); 573 } 574 public int size() { 575 return SequencedHashMap.this.size(); 576 } 577 public boolean isEmpty() { 578 return SequencedHashMap.this.isEmpty(); 579 } 580 public boolean contains(Object o) { 581 return SequencedHashMap.this.containsKey(o); 582 } 583 584 }; 585 } 586 587 /** 588 * Implements {@link Map#values()}. 589 */ 590 public Collection values() { 591 return new AbstractCollection() { 592 // required impl 593 public Iterator iterator() { 594 return new OrderedIterator(VALUE); 595 } 596 public boolean remove(Object value) { 597 // do null comparison outside loop so we only need to do it once. This 598 // provides a tighter, more efficient loop at the expense of slight 599 // code duplication. 600 if (value == null) { 601 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 602 if (pos.getValue() == null) { 603 SequencedHashMap.this.removeImpl(pos.getKey()); 604 return true; 605 } 606 } 607 } else { 608 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 609 if (value.equals(pos.getValue())) { 610 SequencedHashMap.this.removeImpl(pos.getKey()); 611 return true; 612 } 613 } 614 } 615 616 return false; 617 } 618 619 // more efficient impls than abstract collection 620 public void clear() { 621 SequencedHashMap.this.clear(); 622 } 623 public int size() { 624 return SequencedHashMap.this.size(); 625 } 626 public boolean isEmpty() { 627 return SequencedHashMap.this.isEmpty(); 628 } 629 public boolean contains(Object o) { 630 return SequencedHashMap.this.containsValue(o); 631 } 632 }; 633 } 634 635 /** 636 * Implements {@link Map#entrySet()}. 637 */ 638 public Set entrySet() { 639 return new AbstractSet() { 640 // helper 641 private Entry findEntry(Object o) { 642 if (o == null) 643 return null; 644 if (!(o instanceof Map.Entry)) 645 return null; 646 647 Map.Entry e = (Map.Entry) o; 648 Entry entry = (Entry) entries.get(e.getKey()); 649 if (entry != null && entry.equals(e)) 650 return entry; 651 else 652 return null; 653 } 654 655 // required impl 656 public Iterator iterator() { 657 return new OrderedIterator(ENTRY); 658 } 659 public boolean remove(Object o) { 660 Entry e = findEntry(o); 661 if (e == null) 662 return false; 663 664 return SequencedHashMap.this.removeImpl(e.getKey()) != null; 665 } 666 667 // more efficient impls than abstract collection 668 public void clear() { 669 SequencedHashMap.this.clear(); 670 } 671 public int size() { 672 return SequencedHashMap.this.size(); 673 } 674 public boolean isEmpty() { 675 return SequencedHashMap.this.isEmpty(); 676 } 677 public boolean contains(Object o) { 678 return findEntry(o) != null; 679 } 680 }; 681 } 682 683 // constants to define what the iterator should return on "next" 684 private static final int KEY = 0; 685 private static final int VALUE = 1; 686 private static final int ENTRY = 2; 687 private static final int REMOVED_MASK = 0x80000000; 688 689 private class OrderedIterator implements Iterator { 690 /** 691 * Holds the type that should be returned from the iterator. The value 692 * should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}. To 693 * save a tiny bit of memory, this field is also used as a marker for when 694 * remove has been called on the current object to prevent a second remove 695 * on the same element. Essentially, if this value is negative (i.e. the 696 * bit specified by {@link #REMOVED_MASK} is set), the current position 697 * has been removed. If positive, remove can still be called. 698 */ 699 private int returnType; 700 701 /** 702 * Holds the "current" position in the iterator. When pos.next is the 703 * sentinel, we've reached the end of the list. 704 */ 705 private Entry pos = sentinel; 706 707 /** 708 * Holds the expected modification count. If the actual modification 709 * count of the map differs from this value, then a concurrent 710 * modification has occurred. 711 */ 712 private transient long expectedModCount = modCount; 713 714 /** 715 * Construct an iterator over the sequenced elements in the order in which 716 * they were added. The {@link #next()} method returns the type specified 717 * by <code>returnType</code> which must be either {@link #KEY}, {@link 718 * #VALUE}, or {@link #ENTRY}. 719 */ 720 public OrderedIterator(int returnType) { 721 //// Since this is a private inner class, nothing else should have 722 //// access to the constructor. Since we know the rest of the outer 723 //// class uses the iterator correctly, we can leave of the following 724 //// check: 725 //if(returnType >= 0 && returnType <= 2) { 726 // throw new IllegalArgumentException("Invalid iterator type"); 727 //} 728 729 // Set the "removed" bit so that the iterator starts in a state where 730 // "next" must be called before "remove" will succeed. 731 this.returnType = returnType | REMOVED_MASK; 732 } 733 734 /** 735 * Returns whether there is any additional elements in the iterator to be 736 * returned. 737 * 738 * @return <code>true</code> if there are more elements left to be 739 * returned from the iterator; <code>false</code> otherwise. 740 */ 741 public boolean hasNext() { 742 return pos.next != sentinel; 743 } 744 745 /** 746 * Returns the next element from the iterator. 747 * 748 * @return the next element from the iterator. 749 * 750 * @throws NoSuchElementException if there are no more elements in the 751 * iterator. 752 * 753 * @throws ConcurrentModificationException if a modification occurs in 754 * the underlying map. 755 */ 756 public Object next() { 757 if (modCount != expectedModCount) { 758 throw new ConcurrentModificationException(); 759 } 760 if (pos.next == sentinel) { 761 throw new NoSuchElementException(); 762 } 763 764 // clear the "removed" flag 765 returnType = returnType & ~REMOVED_MASK; 766 767 pos = pos.next; 768 switch (returnType) { 769 case KEY : 770 return pos.getKey(); 771 case VALUE : 772 return pos.getValue(); 773 case ENTRY : 774 return pos; 775 default : 776 // should never happen 777 throw new Error("bad iterator type: " + returnType); 778 } 779 780 } 781 782 /** 783 * Removes the last element returned from the {@link #next()} method from 784 * the sequenced map. 785 * 786 * @throws IllegalStateException if there isn't a "last element" to be 787 * removed. That is, if {@link #next()} has never been called, or if 788 * {@link #remove()} was already called on the element. 789 * 790 * @throws ConcurrentModificationException if a modification occurs in 791 * the underlying map. 792 */ 793 public void remove() { 794 if ((returnType & REMOVED_MASK) != 0) { 795 throw new IllegalStateException("remove() must follow next()"); 796 } 797 if (modCount != expectedModCount) { 798 throw new ConcurrentModificationException(); 799 } 800 801 SequencedHashMap.this.removeImpl(pos.getKey()); 802 803 // update the expected mod count for the remove operation 804 expectedModCount++; 805 806 // set the removed flag 807 returnType = returnType | REMOVED_MASK; 808 } 809 } 810 811 // APIs maintained from previous version of SequencedHashMap for backwards 812 // compatibility 813 814 /** 815 * Creates a shallow copy of this object, preserving the internal structure 816 * by copying only references. The keys and values themselves are not 817 * <code>clone()</code>'d. The cloned object maintains the same sequence. 818 * 819 * @return A clone of this instance. 820 * 821 * @throws CloneNotSupportedException if clone is not supported by a 822 * subclass. 823 */ 824 public Object clone() throws CloneNotSupportedException { 825 // yes, calling super.clone() silly since we're just blowing away all 826 // the stuff that super might be doing anyway, but for motivations on 827 // this, see: 828 // http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html 829 SequencedHashMap map = (SequencedHashMap) super.clone(); 830 831 // create new, empty sentinel 832 map.sentinel = createSentinel(); 833 834 // create a new, empty entry map 835 // note: this does not preserve the initial capacity and load factor. 836 map.entries = new HashMap(); 837 838 // add all the mappings 839 map.putAll(this); 840 841 // Note: We cannot just clone the hashmap and sentinel because we must 842 // duplicate our internal structures. Cloning those two will not clone all 843 // the other entries they reference, and so the cloned hash map will not be 844 // able to maintain internal consistency because there are two objects with 845 // the same entries. See discussion in the Entry implementation on why we 846 // cannot implement a clone of the Entry (and thus why we need to recreate 847 // everything). 848 849 return map; 850 } 851 852 /** 853 * Returns the Map.Entry at the specified index 854 * 855 * @throws ArrayIndexOutOfBoundsException if the specified index is 856 * <code>< 0</code> or <code>></code> the size of the map. 857 */ 858 private Map.Entry getEntry(int index) { 859 Entry pos = sentinel; 860 861 if (index < 0) { 862 throw new ArrayIndexOutOfBoundsException(index + " < 0"); 863 } 864 865 // loop to one before the position 866 int i = -1; 867 while (i < (index - 1) && pos.next != sentinel) { 868 i++; 869 pos = pos.next; 870 } 871 // pos.next is the requested position 872 873 // if sentinel is next, past end of list 874 if (pos.next == sentinel) { 875 throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1)); 876 } 877 878 return pos.next; 879 } 880 881 /** 882 * Gets the key at the specified index. 883 * 884 * @param index the index to retrieve 885 * @return the key at the specified index, or null 886 * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is 887 * <code>< 0</code> or <code>></code> the size of the map. 888 */ 889 public Object get(int index) { 890 return getEntry(index).getKey(); 891 } 892 893 /** 894 * Gets the value at the specified index. 895 * 896 * @param index the index to retrieve 897 * @return the value at the specified index, or null 898 * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is 899 * <code>< 0</code> or <code>></code> the size of the map. 900 */ 901 public Object getValue(int index) { 902 return getEntry(index).getValue(); 903 } 904 905 /** 906 * Gets the index of the specified key. 907 * 908 * @param key the key to find the index of 909 * @return the index, or -1 if not found 910 */ 911 public int indexOf(Object key) { 912 Entry e = (Entry) entries.get(key); 913 if (e == null) { 914 return -1; 915 } 916 int pos = 0; 917 while (e.prev != sentinel) { 918 pos++; 919 e = e.prev; 920 } 921 return pos; 922 } 923 924 /** 925 * Gets an iterator over the keys. 926 * 927 * @return an iterator over the keys 928 */ 929 public Iterator iterator() { 930 return keySet().iterator(); 931 } 932 933 /** 934 * Gets the last index of the specified key. 935 * 936 * @param key the key to find the index of 937 * @return the index, or -1 if not found 938 */ 939 public int lastIndexOf(Object key) { 940 // keys in a map are guaranteed to be unique 941 return indexOf(key); 942 } 943 944 /** 945 * Returns a List view of the keys rather than a set view. The returned 946 * list is unmodifiable. This is required because changes to the values of 947 * the list (using {@link java.util.ListIterator#set(Object)}) will 948 * effectively remove the value from the list and reinsert that value at 949 * the end of the list, which is an unexpected side effect of changing the 950 * value of a list. This occurs because changing the key, changes when the 951 * mapping is added to the map and thus where it appears in the list. 952 * 953 * <p>An alternative to this method is to use {@link #keySet()} 954 * 955 * @see #keySet() 956 * @return The ordered list of keys. 957 */ 958 public List sequence() { 959 List l = new ArrayList(size()); 960 Iterator iter = keySet().iterator(); 961 while (iter.hasNext()) { 962 l.add(iter.next()); 963 } 964 965 return UnmodifiableList.decorate(l); 966 } 967 968 /** 969 * Removes the element at the specified index. 970 * 971 * @param index The index of the object to remove. 972 * @return The previous value corresponding the <code>key</code>, or 973 * <code>null</code> if none existed. 974 * 975 * @throws ArrayIndexOutOfBoundsException if the <code>index</code> is 976 * <code>< 0</code> or <code>></code> the size of the map. 977 */ 978 public Object remove(int index) { 979 return remove(get(index)); 980 } 981 982 // per Externalizable.readExternal(ObjectInput) 983 984 /** 985 * Deserializes this map from the given stream. 986 * 987 * @param in the stream to deserialize from 988 * @throws IOException if the stream raises it 989 * @throws ClassNotFoundException if the stream raises it 990 */ 991 public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { 992 int size = in.readInt(); 993 for (int i = 0; i < size; i++) { 994 Object key = in.readObject(); 995 Object value = in.readObject(); 996 put(key, value); 997 } 998 } 999 1000 /** 1001 * Serializes this map to the given stream. 1002 * 1003 * @param out the stream to serialize to 1004 * @throws IOException if the stream raises it 1005 */ 1006 public void writeExternal(ObjectOutput out) throws IOException { 1007 out.writeInt(size()); 1008 for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 1009 out.writeObject(pos.getKey()); 1010 out.writeObject(pos.getValue()); 1011 } 1012 } 1013 1014 // add a serial version uid, so that if we change things in the future 1015 // without changing the format, we can still deserialize properly. 1016 private static final long serialVersionUID = 3380552487888102930L; 1017 1018 }