1 61 package org.enhydra.shark.utilities; 62 63 import java.io.Externalizable ; 64 import java.io.ObjectInput ; 65 import java.io.ObjectOutput ; 66 import java.io.IOException ; 67 68 import java.util.Collection ; 69 import java.util.Collections ; 70 import java.util.HashMap ; 71 import java.util.Iterator ; 72 import java.util.AbstractCollection ; 73 import java.util.AbstractSet ; 74 import java.util.ArrayList ; 75 import java.util.List ; 76 import java.util.Map ; 77 import java.util.Set ; 78 import java.util.NoSuchElementException ; 79 import java.util.ConcurrentModificationException ; 80 81 100 public class SequencedHashMap implements Map , Cloneable , Externalizable { 101 102 106 private static class Entry implements Map.Entry { 107 117 private final Object key; 118 private Object value; 119 120 Entry next = null; 123 Entry prev = null; 124 125 public Entry(Object key, Object value) { 126 this.key = key; 127 this.value = value; 128 } 129 130 public Object getKey() { 132 return this.key; 133 } 134 135 public Object getValue() { 137 return this.value; 138 } 139 140 public Object setValue(Object value) { 142 Object oldValue = this.value; 143 this.value = value; 144 return oldValue; 145 } 146 147 public int hashCode() { 148 return ((getKey() == null ? 0 : getKey().hashCode()) ^ 150 (getValue()==null ? 0 : getValue().hashCode())); 151 } 152 153 public boolean equals(Object obj) { 154 if(obj == null) return false; 155 if(obj == this) return true; 156 if(!(obj instanceof Map.Entry )) return false; 157 158 Map.Entry other = (Map.Entry )obj; 159 160 return((getKey() == null ? 162 other.getKey() == null : 163 getKey().equals(other.getKey())) && 164 (getValue() == null ? 165 other.getValue() == null : 166 getValue().equals(other.getValue()))); 167 } 168 public String toString() { 169 return "[" + getKey() + "=" + getValue() + "]"; 170 } 171 } 172 173 178 private static final Entry createSentinel() { 179 Entry s = new Entry(null, null); 180 s.prev = s; 181 s.next = s; 182 return s; 183 } 184 185 188 private Entry sentinel; 189 190 193 private HashMap entries; 194 195 201 private transient long modCount = 0; 202 203 207 public SequencedHashMap() { 208 sentinel = createSentinel(); 209 entries = new HashMap (); 210 } 211 212 220 public SequencedHashMap(int initialSize) { 221 sentinel = createSentinel(); 222 entries = new HashMap (initialSize); 223 } 224 225 235 public SequencedHashMap(int initialSize, float loadFactor) { 236 sentinel = createSentinel(); 237 entries = new HashMap (initialSize, loadFactor); 238 } 239 240 245 public SequencedHashMap(Map m) { 246 this(); 247 putAll(m); 248 } 249 250 254 private void removeEntry(Entry entry) { 255 entry.next.prev = entry.prev; 256 entry.prev.next = entry.next; 257 } 258 259 263 private void insertEntry(Entry entry) { 264 entry.next = sentinel; 265 entry.prev = sentinel.prev; 266 sentinel.prev.next = entry; 267 sentinel.prev = entry; 268 } 269 270 272 275 public int size() { 276 return entries.size(); 278 } 279 280 283 public boolean isEmpty() { 284 return sentinel.next == sentinel; 287 } 288 289 292 public boolean containsKey(Object key) { 293 return entries.containsKey(key); 295 } 296 297 300 public boolean containsValue(Object value) { 301 306 if(value == null) { 310 for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 311 if(pos.getValue() == null) return true; 312 } 313 } else { 314 for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 315 if(value.equals(pos.getValue())) return true; 316 } 317 } 318 return false; 319 } 320 321 324 public Object get(Object o) { 325 Entry entry = (Entry)entries.get(o); 327 if(entry == null) return null; 328 329 return entry.getValue(); 330 } 331 332 342 public Map.Entry getFirst() { 343 return (isEmpty()) ? null : sentinel.next; 347 } 348 349 359 public Object getFirstKey() { 360 return sentinel.next.getKey(); 367 } 368 369 379 public Object getFirstValue() { 380 return sentinel.next.getValue(); 387 } 388 389 409 public Map.Entry getLast() { 410 return (isEmpty()) ? null : sentinel.prev; 414 } 415 416 426 public Object getLastKey() { 427 return sentinel.prev.getKey(); 434 } 435 436 446 public Object getLastValue() { 447 return sentinel.prev.getValue(); 454 } 455 456 459 public Object put(Object key, Object value) { 460 modCount++; 461 462 Object oldValue = null; 463 464 Entry e = (Entry)entries.get(key); 466 467 if(e != null) { 469 removeEntry(e); 471 472 oldValue = e.setValue(value); 474 475 } else { 481 e = new Entry(key, value); 483 entries.put(key, e); 484 } 485 487 insertEntry(e); 489 490 return oldValue; 491 } 492 493 496 public Object remove(Object key) { 497 Entry e = removeImpl(key); 498 return (e == null) ? null : e.getValue(); 499 } 500 501 505 private Entry removeImpl(Object key) { 506 Entry e = (Entry)entries.remove(key); 507 if(e == null) return null; 508 modCount++; 509 removeEntry(e); 510 return e; 511 } 512 513 523 public void putAll(Map t) { 524 Iterator iter = t.entrySet().iterator(); 525 while(iter.hasNext()) { 526 Map.Entry entry = (Map.Entry )iter.next(); 527 put(entry.getKey(), entry.getValue()); 528 } 529 } 530 531 534 public void clear() { 535 modCount++; 536 537 entries.clear(); 539 540 sentinel.next = sentinel; 542 sentinel.prev = sentinel; 543 } 544 545 548 public boolean equals(Object obj) { 549 if(obj == null) return false; 550 if(obj == this) return true; 551 552 if(!(obj instanceof Map )) return false; 553 554 return entrySet().equals(((Map )obj).entrySet()); 555 } 556 557 560 public int hashCode() { 561 return entrySet().hashCode(); 562 } 563 564 571 public String toString() { 572 StringBuffer buf = new StringBuffer (); 573 buf.append('['); 574 for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 575 buf.append(pos.getKey()); 576 buf.append('='); 577 buf.append(pos.getValue()); 578 if(pos.next != sentinel) { 579 buf.append(','); 580 } 581 } 582 buf.append(']'); 583 584 return buf.toString(); 585 } 586 587 590 public Set keySet() { 591 return new AbstractSet () { 592 593 public Iterator iterator() { return new OrderedIterator(KEY); } 595 public boolean remove(Object o) { 596 Entry e = SequencedHashMap.this.removeImpl(o); 597 return (e != null); 598 } 599 600 public void clear() { 602 SequencedHashMap.this.clear(); 603 } 604 public int size() { 605 return SequencedHashMap.this.size(); 606 } 607 public boolean isEmpty() { 608 return SequencedHashMap.this.isEmpty(); 609 } 610 public boolean contains(Object o) { 611 return SequencedHashMap.this.containsKey(o); 612 } 613 614 }; 615 } 616 617 620 public Collection values() { 621 return new AbstractCollection () { 622 public Iterator iterator() { return new OrderedIterator(VALUE); } 624 public boolean remove(Object value) { 625 if(value == null) { 629 for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 630 if(pos.getValue() == null) { 631 SequencedHashMap.this.removeImpl(pos.getKey()); 632 return true; 633 } 634 } 635 } else { 636 for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 637 if(value.equals(pos.getValue())) { 638 SequencedHashMap.this.removeImpl(pos.getKey()); 639 return true; 640 } 641 } 642 } 643 644 return false; 645 } 646 647 public void clear() { 649 SequencedHashMap.this.clear(); 650 } 651 public int size() { 652 return SequencedHashMap.this.size(); 653 } 654 public boolean isEmpty() { 655 return SequencedHashMap.this.isEmpty(); 656 } 657 public boolean contains(Object o) { 658 return SequencedHashMap.this.containsValue(o); 659 } 660 }; 661 } 662 663 666 public Set entrySet() { 667 return new AbstractSet () { 668 private Entry findEntry(Object o) { 670 if(o == null) return null; 671 if(!(o instanceof Map.Entry )) return null; 672 673 Map.Entry e = (Map.Entry )o; 674 Entry entry = (Entry)entries.get(e.getKey()); 675 if(entry != null && entry.equals(e)) return entry; 676 else return null; 677 } 678 679 public Iterator iterator() { 681 return new OrderedIterator(ENTRY); 682 } 683 public boolean remove(Object o) { 684 Entry e = findEntry(o); 685 if(e == null) return false; 686 687 return SequencedHashMap.this.removeImpl(e.getKey()) != null; 688 } 689 690 public void clear() { 692 SequencedHashMap.this.clear(); 693 } 694 public int size() { 695 return SequencedHashMap.this.size(); 696 } 697 public boolean isEmpty() { 698 return SequencedHashMap.this.isEmpty(); 699 } 700 public boolean contains(Object o) { 701 return findEntry(o) != null; 702 } 703 }; 704 } 705 706 private static final int KEY = 0; 708 private static final int VALUE = 1; 709 private static final int ENTRY = 2; 710 private static final int REMOVED_MASK = 0x80000000; 711 712 private class OrderedIterator implements Iterator { 713 722 private int returnType; 723 724 728 private Entry pos = sentinel; 729 730 735 private transient long expectedModCount = modCount; 736 737 743 public OrderedIterator(int returnType) { 744 752 this.returnType = returnType | REMOVED_MASK; 755 } 756 757 764 public boolean hasNext() { 765 return pos.next != sentinel; 766 } 767 768 779 public Object next() { 780 if(modCount != expectedModCount) { 781 throw new ConcurrentModificationException (); 782 } 783 if(pos.next == sentinel) { 784 throw new NoSuchElementException (); 785 } 786 787 returnType = returnType & ~REMOVED_MASK; 789 790 pos = pos.next; 791 switch(returnType) { 792 case KEY: 793 return pos.getKey(); 794 case VALUE: 795 return pos.getValue(); 796 case ENTRY: 797 return pos; 798 default: 799 throw new Error ("bad iterator type: " + returnType); 801 } 802 803 } 804 805 816 public void remove() { 817 if((returnType & REMOVED_MASK) != 0) { 818 throw new IllegalStateException ("remove() must follow next()"); 819 } 820 if(modCount != expectedModCount) { 821 throw new ConcurrentModificationException (); 822 } 823 824 SequencedHashMap.this.removeImpl(pos.getKey()); 825 826 expectedModCount++; 828 829 returnType = returnType | REMOVED_MASK; 831 } 832 } 833 834 837 847 public Object clone () throws CloneNotSupportedException { 848 SequencedHashMap map = (SequencedHashMap)super.clone(); 853 854 map.sentinel = createSentinel(); 856 857 map.entries = new HashMap (); 860 861 map.putAll(this); 863 864 872 return map; 873 } 874 875 881 private Map.Entry getEntry(int index) { 882 Entry pos = sentinel; 883 884 if(index < 0) { 885 throw new ArrayIndexOutOfBoundsException (index + " < 0"); 886 } 887 888 int i = -1; 890 while(i < (index-1) && pos.next != sentinel) { 891 i++; 892 pos = pos.next; 893 } 894 896 if(pos.next == sentinel) { 898 throw new ArrayIndexOutOfBoundsException (index + " >= " + (i + 1)); 899 } 900 901 return pos.next; 902 } 903 904 910 public Object get (int index) 911 { 912 return getEntry(index).getKey(); 913 } 914 915 921 public Object getValue (int index) 922 { 923 return getEntry(index).getValue(); 924 } 925 926 929 public int indexOf (Object key) 930 { 931 Entry e = (Entry)entries.get(key); 932 int pos = 0; 933 while(e.prev != sentinel) { 934 pos++; 935 e = e.prev; 936 } 937 return pos; 938 } 939 940 943 public Iterator iterator () 944 { 945 return keySet().iterator(); 946 } 947 948 951 public int lastIndexOf (Object key) 952 { 953 return indexOf(key); 955 } 956 957 971 public List sequence() 972 { 973 List l = new ArrayList (size()); 974 Iterator iter = keySet().iterator(); 975 while(iter.hasNext()) { 976 l.add(iter.next()); 977 } 978 979 return Collections.unmodifiableList(l); 980 } 981 982 992 public Object remove (int index) 993 { 994 return remove(get(index)); 995 } 996 997 999 1006 public void readExternal( ObjectInput in ) 1007 throws IOException , ClassNotFoundException 1008 { 1009 int size = in.readInt(); 1010 for(int i = 0; i < size; i++) { 1011 Object key = in.readObject(); 1012 Object value = in.readObject(); 1013 put(key, value); 1014 } 1015 } 1016 1017 1023 public void writeExternal( ObjectOutput out ) throws IOException { 1024 out.writeInt(size()); 1025 for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { 1026 out.writeObject(pos.getKey()); 1027 out.writeObject(pos.getValue()); 1028 } 1029 } 1030 1031 private static final long serialVersionUID = 3380552487888102930L; 1034 1035} 1036 | Popular Tags |