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 }