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