/* Copyright 2004 The Apache Software Foundation | |
* | |
* Licensed under the Apache License, Version 2.0 (the "License"); | |
* you may not use this file except in compliance with the License. | |
* You may obtain a copy of the License at | |
* | |
* http://www.apache.org/licenses/LICENSE-2.0 | |
* | |
* Unless required by applicable law or agreed to in writing, software | |
* distributed under the License is distributed on an "AS IS" BASIS, | |
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
* See the License for the specific language governing permissions and | |
* limitations under the License. | |
*/ | |
package org.apache.xmlbeans.impl.common; | |
import java.io.Externalizable; | |
import java.io.ObjectInput; | |
import java.io.ObjectOutput; | |
import java.io.IOException; | |
import java.util.Collection; | |
import java.util.Collections; | |
import java.util.HashMap; | |
import java.util.Iterator; | |
import java.util.AbstractCollection; | |
import java.util.AbstractSet; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Set; | |
import java.util.NoSuchElementException; | |
import java.util.ConcurrentModificationException; | |
// from commons-collection | |
/** | |
* A map of objects whose mapping entries are sequenced based on the order in | |
* which they were added. This data structure has fast <I>O(1)</I> search | |
* time, deletion time, and insertion time. | |
* | |
* <P>Although this map is sequenced, it cannot implement {@link | |
* java.util.List} because of incompatible interface definitions. The remove | |
* methods in List and Map have different return values (see: {@link | |
* java.util.List#remove(Object)} and {@link java.util.Map#remove(Object)}). | |
* | |
* <P>This class is not thread safe. When a thread safe implementation is | |
* required, use {@link Collections#synchronizedMap(Map)} as it is documented, | |
* or use explicit synchronization controls. | |
* | |
* @author <a href="mailto:mas@apache.org">Michael A. Smith</A> | |
* @author <a href="mailto:dlr@collab.net">Daniel Rall</a> | |
* @author <a href="mailto:hps@intermeta.de">Henning P. Schmiedehausen</a> | |
*/ | |
public class SequencedHashMap implements Map, Cloneable, Externalizable { | |
/** | |
* {@link java.util.Map.Entry} that doubles as a node in the linked list | |
* of sequenced mappings. | |
**/ | |
private static class Entry implements Map.Entry { | |
// Note: This class cannot easily be made clonable. While the actual | |
// implementation of a clone would be simple, defining the semantics is | |
// difficult. If a shallow clone is implemented, then entry.next.prev != | |
// entry, which is unintuitive and probably breaks all sorts of assumptions | |
// in code that uses this implementation. If a deep clone is | |
// implementated, then what happens when the linked list is cyclical (as is | |
// the case with SequencedHashMap)? It's impossible to know in the clone | |
// when to stop cloning, and thus you end up in a recursive loop, | |
// continuously cloning the "next" in the list. | |
private final Object key; | |
private Object value; | |
// package private to allow the SequencedHashMap to access and manipulate | |
// them. | |
Entry next = null; | |
Entry prev = null; | |
public Entry(Object key, Object value) { | |
this.key = key; | |
this.value = value; | |
} | |
// per Map.Entry.getKey() | |
public Object getKey() { | |
return this.key; | |
} | |
// per Map.Entry.getValue() | |
public Object getValue() { | |
return this.value; | |
} | |
// per Map.Entry.setValue() | |
public Object setValue(Object value) { | |
Object oldValue = this.value; | |
this.value = value; | |
return oldValue; | |
} | |
public int hashCode() { | |
// implemented per api docs for Map.Entry.hashCode() | |
return ((getKey() == null ? 0 : getKey().hashCode()) ^ | |
(getValue() == null ? 0 : getValue().hashCode())); | |
} | |
public boolean equals(Object obj) { | |
if (obj == null) return false; | |
if (obj == this) return true; | |
if (!(obj instanceof Map.Entry)) return false; | |
Map.Entry other = (Map.Entry)obj; | |
// implemented per api docs for Map.Entry.equals(Object) | |
return ((getKey() == null ? | |
other.getKey() == null : | |
getKey().equals(other.getKey())) && | |
(getValue() == null ? | |
other.getValue() == null : | |
getValue().equals(other.getValue()))); | |
} | |
public String toString() { | |
return "[" + getKey() + "=" + getValue() + "]"; | |
} | |
} | |
/** | |
* Construct an empty sentinel used to hold the head (sentinel.next) and the | |
* tail (sentinel.prev) of the list. The sentinal has a <code>null</code> | |
* key and value. | |
**/ | |
private static final Entry createSentinel() { | |
Entry s = new Entry(null, null); | |
s.prev = s; | |
s.next = s; | |
return s; | |
} | |
/** | |
* Sentinel used to hold the head and tail of the list of entries. | |
**/ | |
private Entry sentinel; | |
/** | |
* Map of keys to entries | |
**/ | |
private HashMap entries; | |
/** | |
* Holds the number of modifications that have occurred to the map, | |
* excluding modifications made through a collection view's iterator | |
* (e.g. entrySet().iterator().remove()). This is used to create a | |
* fail-fast behavior with the iterators. | |
**/ | |
private transient long modCount = 0; | |
/** | |
* Construct a new sequenced hash map with default initial size and load | |
* factor. | |
**/ | |
public SequencedHashMap() { | |
sentinel = createSentinel(); | |
entries = new HashMap(); | |
} | |
/** | |
* Construct a new sequenced hash map with the specified initial size and | |
* default load factor. | |
* | |
* @param initialSize the initial size for the hash table | |
* | |
* @see HashMap#HashMap(int) | |
**/ | |
public SequencedHashMap(int initialSize) { | |
sentinel = createSentinel(); | |
entries = new HashMap(initialSize); | |
} | |
/** | |
* Construct a new sequenced hash map with the specified initial size and | |
* load factor. | |
* | |
* @param initialSize the initial size for the hash table | |
* | |
* @param loadFactor the load factor for the hash table. | |
* | |
* @see HashMap#HashMap(int,float) | |
**/ | |
public SequencedHashMap(int initialSize, float loadFactor) { | |
sentinel = createSentinel(); | |
entries = new HashMap(initialSize, loadFactor); | |
} | |
/** | |
* Construct a new sequenced hash map and add all the elements in the | |
* specified map. The order in which the mappings in the specified map are | |
* added is defined by {@link #putAll(Map)}. | |
**/ | |
public SequencedHashMap(Map m) { | |
this(); | |
putAll(m); | |
} | |
/** | |
* Removes an internal entry from the linked list. This does not remove | |
* it from the underlying map. | |
**/ | |
private void removeEntry(Entry entry) { | |
entry.next.prev = entry.prev; | |
entry.prev.next = entry.next; | |
} | |
/** | |
* Inserts a new internal entry to the tail of the linked list. This does | |
* not add the entry to the underlying map. | |
**/ | |
private void insertEntry(Entry entry) { | |
entry.next = sentinel; | |
entry.prev = sentinel.prev; | |
sentinel.prev.next = entry; | |
sentinel.prev = entry; | |
} | |
// per Map.size() | |
/** | |
* Implements {@link Map#size()}. | |
*/ | |
public int size() { | |
// use the underlying Map's size since size is not maintained here. | |
return entries.size(); | |
} | |
/** | |
* Implements {@link Map#isEmpty()}. | |
*/ | |
public boolean isEmpty() { | |
// for quick check whether the map is entry, we can check the linked list | |
// and see if there's anything in it. | |
return sentinel.next == sentinel; | |
} | |
/** | |
* Implements {@link Map#containsKey(Object)}. | |
*/ | |
public boolean containsKey(Object key) { | |
// pass on to underlying map implementation | |
return entries.containsKey(key); | |
} | |
/** | |
* Implements {@link Map#containsValue(Object)}. | |
*/ | |
public boolean containsValue(Object value) { | |
// unfortunately, we cannot just pass this call to the underlying map | |
// because we are mapping keys to entries, not keys to values. The | |
// underlying map doesn't have an efficient implementation anyway, so this | |
// isn't a big deal. | |
// do null comparison outside loop so we only need to do it once. This | |
// provides a tighter, more efficient loop at the expense of slight | |
// code duplication. | |
if (value == null) { | |
for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { | |
if (pos.getValue() == null) return true; | |
} | |
} | |
else { | |
for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { | |
if (value.equals(pos.getValue())) return true; | |
} | |
} | |
return false; | |
} | |
/** | |
* Implements {@link Map#get(Object)}. | |
*/ | |
public Object get(Object o) { | |
// find entry for the specified key object | |
Entry entry = (Entry)entries.get(o); | |
if (entry == null) return null; | |
return entry.getValue(); | |
} | |
/** | |
* Return the entry for the "oldest" mapping. That is, return the Map.Entry | |
* for the key-value pair that was first put into the map when compared to | |
* all the other pairings in the map. This behavior is equivalent to using | |
* <code>entrySet().iterator().next()</code>, but this method provides an | |
* optimized implementation. | |
* | |
* @return The first entry in the sequence, or <code>null</code> if the | |
* map is empty. | |
**/ | |
public Map.Entry getFirst() { | |
// sentinel.next points to the "first" element of the sequence -- the head | |
// of the list, which is exactly the entry we need to return. We must test | |
// for an empty list though because we don't want to return the sentinel! | |
return (isEmpty()) ? null : sentinel.next; | |
} | |
/** | |
* Return the key for the "oldest" mapping. That is, return the key for the | |
* mapping that was first put into the map when compared to all the other | |
* objects in the map. This behavior is equivalent to using | |
* <code>getFirst().getKey()</code>, but this method provides a slightly | |
* optimized implementation. | |
* | |
* @return The first key in the sequence, or <code>null</code> if the | |
* map is empty. | |
**/ | |
public Object getFirstKey() { | |
// sentinel.next points to the "first" element of the sequence -- the head | |
// of the list -- and the requisite key is returned from it. An empty list | |
// does not need to be tested. In cases where the list is empty, | |
// sentinel.next will point to the sentinel itself which has a null key, | |
// which is exactly what we would want to return if the list is empty (a | |
// nice convient way to avoid test for an empty list) | |
return sentinel.next.getKey(); | |
} | |
/** | |
* Return the value for the "oldest" mapping. That is, return the value for | |
* the mapping that was first put into the map when compared to all the | |
* other objects in the map. This behavior is equivalent to using | |
* <code>getFirst().getValue()</code>, but this method provides a slightly | |
* optimized implementation. | |
* | |
* @return The first value in the sequence, or <code>null</code> if the | |
* map is empty. | |
**/ | |
public Object getFirstValue() { | |
// sentinel.next points to the "first" element of the sequence -- the head | |
// of the list -- and the requisite value is returned from it. An empty | |
// list does not need to be tested. In cases where the list is empty, | |
// sentinel.next will point to the sentinel itself which has a null value, | |
// which is exactly what we would want to return if the list is empty (a | |
// nice convient way to avoid test for an empty list) | |
return sentinel.next.getValue(); | |
} | |
/** | |
* Return the entry for the "newest" mapping. That is, return the Map.Entry | |
* for the key-value pair that was first put into the map when compared to | |
* all the other pairings in the map. The behavior is equivalent to: | |
* | |
* <pre> | |
* Object obj = null; | |
* Iterator iter = entrySet().iterator(); | |
* while(iter.hasNext()) { | |
* obj = iter.next(); | |
* } | |
* return (Map.Entry)obj; | |
* </pre> | |
* | |
* However, the implementation of this method ensures an O(1) lookup of the | |
* last key rather than O(n). | |
* | |
* @return The last entry in the sequence, or <code>null</code> if the map | |
* is empty. | |
**/ | |
public Map.Entry getLast() { | |
// sentinel.prev points to the "last" element of the sequence -- the tail | |
// of the list, which is exactly the entry we need to return. We must test | |
// for an empty list though because we don't want to return the sentinel! | |
return (isEmpty()) ? null : sentinel.prev; | |
} | |
/** | |
* Return the key for the "newest" mapping. That is, return the key for the | |
* mapping that was last put into the map when compared to all the other | |
* objects in the map. This behavior is equivalent to using | |
* <code>getLast().getKey()</code>, but this method provides a slightly | |
* optimized implementation. | |
* | |
* @return The last key in the sequence, or <code>null</code> if the map is | |
* empty. | |
**/ | |
public Object getLastKey() { | |
// sentinel.prev points to the "last" element of the sequence -- the tail | |
// of the list -- and the requisite key is returned from it. An empty list | |
// does not need to be tested. In cases where the list is empty, | |
// sentinel.prev will point to the sentinel itself which has a null key, | |
// which is exactly what we would want to return if the list is empty (a | |
// nice convient way to avoid test for an empty list) | |
return sentinel.prev.getKey(); | |
} | |
/** | |
* Return the value for the "newest" mapping. That is, return the value for | |
* the mapping that was last put into the map when compared to all the other | |
* objects in the map. This behavior is equivalent to using | |
* <code>getLast().getValue()</code>, but this method provides a slightly | |
* optimized implementation. | |
* | |
* @return The last value in the sequence, or <code>null</code> if the map | |
* is empty. | |
**/ | |
public Object getLastValue() { | |
// sentinel.prev points to the "last" element of the sequence -- the tail | |
// of the list -- and the requisite value is returned from it. An empty | |
// list does not need to be tested. In cases where the list is empty, | |
// sentinel.prev will point to the sentinel itself which has a null value, | |
// which is exactly what we would want to return if the list is empty (a | |
// nice convient way to avoid test for an empty list) | |
return sentinel.prev.getValue(); | |
} | |
/** | |
* Implements {@link Map#put(Object, Object)}. | |
*/ | |
public Object put(Object key, Object value) { | |
modCount++; | |
Object oldValue = null; | |
// lookup the entry for the specified key | |
Entry e = (Entry)entries.get(key); | |
// check to see if it already exists | |
if (e != null) { | |
// remove from list so the entry gets "moved" to the end of list | |
removeEntry(e); | |
// update value in map | |
oldValue = e.setValue(value); | |
// Note: We do not update the key here because its unnecessary. We only | |
// do comparisons using equals(Object) and we know the specified key and | |
// that in the map are equal in that sense. This may cause a problem if | |
// someone does not implement their hashCode() and/or equals(Object) | |
// method properly and then use it as a key in this map. | |
} | |
else { | |
// add new entry | |
e = new Entry(key, value); | |
entries.put(key, e); | |
} | |
// assert(entry in map, but not list) | |
// add to list | |
insertEntry(e); | |
return oldValue; | |
} | |
/** | |
* Implements {@link Map#remove(Object)}. | |
*/ | |
public Object remove(Object key) { | |
Entry e = removeImpl(key); | |
return (e == null) ? null : e.getValue(); | |
} | |
/** | |
* Fully remove an entry from the map, returning the old entry or null if | |
* there was no such entry with the specified key. | |
**/ | |
private Entry removeImpl(Object key) { | |
Entry e = (Entry)entries.remove(key); | |
if (e == null) return null; | |
modCount++; | |
removeEntry(e); | |
return e; | |
} | |
/** | |
* Adds all the mappings in the specified map to this map, replacing any | |
* mappings that already exist (as per {@link Map#putAll(Map)}). The order | |
* in which the entries are added is determined by the iterator returned | |
* from {@link Map#entrySet()} for the specified map. | |
* | |
* @param t the mappings that should be added to this map. | |
* | |
* @exception NullPointerException if <code>t</code> is <code>null</code> | |
**/ | |
public void putAll(Map t) { | |
Iterator iter = t.entrySet().iterator(); | |
while (iter.hasNext()) { | |
Map.Entry entry = (Map.Entry)iter.next(); | |
put(entry.getKey(), entry.getValue()); | |
} | |
} | |
/** | |
* Implements {@link Map#clear()}. | |
*/ | |
public void clear() { | |
modCount++; | |
// remove all from the underlying map | |
entries.clear(); | |
// and the list | |
sentinel.next = sentinel; | |
sentinel.prev = sentinel; | |
} | |
/** | |
* Implements {@link Map#equals(Object)}. | |
*/ | |
public boolean equals(Object obj) { | |
if (obj == null) return false; | |
if (obj == this) return true; | |
if (!(obj instanceof Map)) return false; | |
return entrySet().equals(((Map)obj).entrySet()); | |
} | |
/** | |
* Implements {@link Map#hashCode()}. | |
*/ | |
public int hashCode() { | |
return entrySet().hashCode(); | |
} | |
/** | |
* Provides a string representation of the entries within the map. The | |
* format of the returned string may change with different releases, so this | |
* method is suitable for debugging purposes only. If a specific format is | |
* required, use {@link #entrySet()}.{@link Set#iterator() iterator()} and | |
* iterate over the entries in the map formatting them as appropriate. | |
**/ | |
public String toString() { | |
StringBuffer buf = new StringBuffer(); | |
buf.append('['); | |
for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { | |
buf.append(pos.getKey()); | |
buf.append('='); | |
buf.append(pos.getValue()); | |
if (pos.next != sentinel) { | |
buf.append(','); | |
} | |
} | |
buf.append(']'); | |
return buf.toString(); | |
} | |
/** | |
* Implements {@link Map#keySet()}. | |
*/ | |
public Set keySet() { | |
return new AbstractSet() { | |
// required impls | |
public Iterator iterator() { | |
return new OrderedIterator(KEY); | |
} | |
public boolean remove(Object o) { | |
Entry e = SequencedHashMap.this.removeImpl(o); | |
return (e != null); | |
} | |
// more efficient impls than abstract set | |
public void clear() { | |
SequencedHashMap.this.clear(); | |
} | |
public int size() { | |
return SequencedHashMap.this.size(); | |
} | |
public boolean isEmpty() { | |
return SequencedHashMap.this.isEmpty(); | |
} | |
public boolean contains(Object o) { | |
return SequencedHashMap.this.containsKey(o); | |
} | |
}; | |
} | |
/** | |
* Implements {@link Map#values()}. | |
*/ | |
public Collection values() { | |
return new AbstractCollection() { | |
// required impl | |
public Iterator iterator() { | |
return new OrderedIterator(VALUE); | |
} | |
public boolean remove(Object value) { | |
// do null comparison outside loop so we only need to do it once. This | |
// provides a tighter, more efficient loop at the expense of slight | |
// code duplication. | |
if (value == null) { | |
for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { | |
if (pos.getValue() == null) { | |
SequencedHashMap.this.removeImpl(pos.getKey()); | |
return true; | |
} | |
} | |
} | |
else { | |
for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { | |
if (value.equals(pos.getValue())) { | |
SequencedHashMap.this.removeImpl(pos.getKey()); | |
return true; | |
} | |
} | |
} | |
return false; | |
} | |
// more efficient impls than abstract collection | |
public void clear() { | |
SequencedHashMap.this.clear(); | |
} | |
public int size() { | |
return SequencedHashMap.this.size(); | |
} | |
public boolean isEmpty() { | |
return SequencedHashMap.this.isEmpty(); | |
} | |
public boolean contains(Object o) { | |
return SequencedHashMap.this.containsValue(o); | |
} | |
}; | |
} | |
/** | |
* Implements {@link Map#entrySet()}. | |
*/ | |
public Set entrySet() { | |
return new AbstractSet() { | |
// helper | |
private Entry findEntry(Object o) { | |
if (o == null) return null; | |
if (!(o instanceof Map.Entry)) return null; | |
Map.Entry e = (Map.Entry)o; | |
Entry entry = (Entry)entries.get(e.getKey()); | |
if (entry != null && entry.equals(e)) | |
return entry; | |
else | |
return null; | |
} | |
// required impl | |
public Iterator iterator() { | |
return new OrderedIterator(ENTRY); | |
} | |
public boolean remove(Object o) { | |
Entry e = findEntry(o); | |
if (e == null) return false; | |
return SequencedHashMap.this.removeImpl(e.getKey()) != null; | |
} | |
// more efficient impls than abstract collection | |
public void clear() { | |
SequencedHashMap.this.clear(); | |
} | |
public int size() { | |
return SequencedHashMap.this.size(); | |
} | |
public boolean isEmpty() { | |
return SequencedHashMap.this.isEmpty(); | |
} | |
public boolean contains(Object o) { | |
return findEntry(o) != null; | |
} | |
}; | |
} | |
// constants to define what the iterator should return on "next" | |
private static final int KEY = 0; | |
private static final int VALUE = 1; | |
private static final int ENTRY = 2; | |
private static final int REMOVED_MASK = 0x80000000; | |
private class OrderedIterator implements Iterator { | |
/** | |
* Holds the type that should be returned from the iterator. The value | |
* should be either {@link #KEY}, {@link #VALUE}, or {@link #ENTRY}. To | |
* save a tiny bit of memory, this field is also used as a marker for when | |
* remove has been called on the current object to prevent a second remove | |
* on the same element. Essientially, if this value is negative (i.e. the | |
* bit specified by {@link #REMOVED_MASK} is set), the current position | |
* has been removed. If positive, remove can still be called. | |
**/ | |
private int returnType; | |
/** | |
* Holds the "current" position in the iterator. When pos.next is the | |
* sentinel, we've reached the end of the list. | |
**/ | |
private Entry pos = sentinel; | |
/** | |
* Holds the expected modification count. If the actual modification | |
* count of the map differs from this value, then a concurrent | |
* modification has occurred. | |
**/ | |
private transient long expectedModCount = modCount; | |
/** | |
* Construct an iterator over the sequenced elements in the order in which | |
* they were added. The {@link #next()} method returns the type specified | |
* by <code>returnType</code> which must be either {@link #KEY}, {@link | |
* #VALUE}, or {@link #ENTRY}. | |
**/ | |
public OrderedIterator(int returnType) { | |
//// Since this is a private inner class, nothing else should have | |
//// access to the constructor. Since we know the rest of the outer | |
//// class uses the iterator correctly, we can leave of the following | |
//// check: | |
//if(returnType >= 0 && returnType <= 2) { | |
// throw new IllegalArgumentException("Invalid iterator type"); | |
//} | |
// Set the "removed" bit so that the iterator starts in a state where | |
// "next" must be called before "remove" will succeed. | |
this.returnType = returnType | REMOVED_MASK; | |
} | |
/** | |
* Returns whether there is any additional elements in the iterator to be | |
* returned. | |
* | |
* @return <code>true</code> if there are more elements left to be | |
* returned from the iterator; <code>false</code> otherwise. | |
**/ | |
public boolean hasNext() { | |
return pos.next != sentinel; | |
} | |
/** | |
* Returns the next element from the iterator. | |
* | |
* @return the next element from the iterator. | |
* | |
* @exception NoSuchElementException if there are no more elements in the | |
* iterator. | |
* | |
* @exception ConcurrentModificationException if a modification occurs in | |
* the underlying map. | |
**/ | |
public Object next() { | |
if (modCount != expectedModCount) { | |
throw new ConcurrentModificationException(); | |
} | |
if (pos.next == sentinel) { | |
throw new NoSuchElementException(); | |
} | |
// clear the "removed" flag | |
returnType = returnType & ~REMOVED_MASK; | |
pos = pos.next; | |
switch (returnType) { | |
case KEY: | |
return pos.getKey(); | |
case VALUE: | |
return pos.getValue(); | |
case ENTRY: | |
return pos; | |
default: | |
// should never happen | |
throw new Error("bad iterator type: " + returnType); | |
} | |
} | |
/** | |
* Removes the last element returned from the {@link #next()} method from | |
* the sequenced map. | |
* | |
* @exception IllegalStateException if there isn't a "last element" to be | |
* removed. That is, if {@link #next()} has never been called, or if | |
* {@link #remove()} was already called on the element. | |
* | |
* @exception ConcurrentModificationException if a modification occurs in | |
* the underlying map. | |
**/ | |
public void remove() { | |
if ((returnType & REMOVED_MASK) != 0) { | |
throw new IllegalStateException("remove() must follow next()"); | |
} | |
if (modCount != expectedModCount) { | |
throw new ConcurrentModificationException(); | |
} | |
SequencedHashMap.this.removeImpl(pos.getKey()); | |
// update the expected mod count for the remove operation | |
expectedModCount++; | |
// set the removed flag | |
returnType = returnType | REMOVED_MASK; | |
} | |
} | |
// APIs maintained from previous version of SequencedHashMap for backwards | |
// compatibility | |
/** | |
* Creates a shallow copy of this object, preserving the internal structure | |
* by copying only references. The keys and values themselves are not | |
* <code>clone()</code>'d. The cloned object maintains the same sequence. | |
* | |
* @return A clone of this instance. | |
* | |
* @exception CloneNotSupportedException if clone is not supported by a | |
* subclass. | |
*/ | |
public Object clone() throws CloneNotSupportedException { | |
// yes, calling super.clone() silly since we're just blowing away all | |
// the stuff that super might be doing anyway, but for motivations on | |
// this, see: | |
// http://www.javaworld.com/javaworld/jw-01-1999/jw-01-object.html | |
SequencedHashMap map = (SequencedHashMap)super.clone(); | |
// create new, empty sentinel | |
map.sentinel = createSentinel(); | |
// create a new, empty entry map | |
// note: this does not preserve the initial capacity and load factor. | |
map.entries = new HashMap(); | |
// add all the mappings | |
map.putAll(this); | |
// Note: We cannot just clone the hashmap and sentinel because we must | |
// duplicate our internal structures. Cloning those two will not clone all | |
// the other entries they reference, and so the cloned hash map will not be | |
// able to maintain internal consistency because there are two objects with | |
// the same entries. See discussion in the Entry implementation on why we | |
// cannot implement a clone of the Entry (and thus why we need to recreate | |
// everything). | |
return map; | |
} | |
/** | |
* Returns the Map.Entry at the specified index | |
* | |
* @exception ArrayIndexOutOfBoundsException if the specified index is | |
* <code>< 0</code> or <code>></code> the size of the map. | |
**/ | |
private Map.Entry getEntry(int index) { | |
Entry pos = sentinel; | |
if (index < 0) { | |
throw new ArrayIndexOutOfBoundsException(index + " < 0"); | |
} | |
// loop to one before the position | |
int i = -1; | |
while (i < (index - 1) && pos.next != sentinel) { | |
i++; | |
pos = pos.next; | |
} | |
// pos.next is the requested position | |
// if sentinel is next, past end of list | |
if (pos.next == sentinel) { | |
throw new ArrayIndexOutOfBoundsException(index + " >= " + (i + 1)); | |
} | |
return pos.next; | |
} | |
/** | |
* Returns the key at the specified index. | |
* | |
* @exception ArrayIndexOutOfBoundsException if the <code>index</code> is | |
* <code>< 0</code> or <code>></code> the size of the map. | |
*/ | |
public Object get(int index) { | |
return getEntry(index).getKey(); | |
} | |
/** | |
* Returns the value at the specified index. | |
* | |
* @exception ArrayIndexOutOfBoundsException if the <code>index</code> is | |
* <code>< 0</code> or <code>></code> the size of the map. | |
*/ | |
public Object getValue(int index) { | |
return getEntry(index).getValue(); | |
} | |
/** | |
* Returns the index of the specified key. | |
*/ | |
public int indexOf(Object key) { | |
Entry e = (Entry)entries.get(key); | |
int pos = 0; | |
while (e.prev != sentinel) { | |
pos++; | |
e = e.prev; | |
} | |
return pos; | |
} | |
/** | |
* Returns a key iterator. | |
*/ | |
public Iterator iterator() { | |
return keySet().iterator(); | |
} | |
/** | |
* Returns the last index of the specified key. | |
*/ | |
public int lastIndexOf(Object key) { | |
// keys in a map are guarunteed to be unique | |
return indexOf(key); | |
} | |
/** | |
* Returns a List view of the keys rather than a set view. The returned | |
* list is unmodifiable. This is required because changes to the values of | |
* the list (using {@link java.util.ListIterator#set(Object)}) will | |
* effectively remove the value from the list and reinsert that value at | |
* the end of the list, which is an unexpected side effect of changing the | |
* value of a list. This occurs because changing the key, changes when the | |
* mapping is added to the map and thus where it appears in the list. | |
* | |
* <P>An alternative to this method is to use {@link #keySet()} | |
* | |
* @see #keySet() | |
* @return The ordered list of keys. | |
*/ | |
public List sequence() { | |
List l = new ArrayList(size()); | |
Iterator iter = keySet().iterator(); | |
while (iter.hasNext()) { | |
l.add(iter.next()); | |
} | |
return Collections.unmodifiableList(l); | |
} | |
/** | |
* Removes the element at the specified index. | |
* | |
* @param index The index of the object to remove. | |
* @return The previous value coressponding the <code>key</code>, or | |
* <code>null</code> if none existed. | |
* | |
* @exception ArrayIndexOutOfBoundsException if the <code>index</code> is | |
* <code>< 0</code> or <code>></code> the size of the map. | |
*/ | |
public Object remove(int index) { | |
return remove(get(index)); | |
} | |
// per Externalizable.readExternal(ObjectInput) | |
/** | |
* Deserializes this map from the given stream. | |
* | |
* @param in the stream to deserialize from | |
* @throws IOException if the stream raises it | |
* @throws ClassNotFoundException if the stream raises it | |
*/ | |
public void readExternal(ObjectInput in) | |
throws IOException, ClassNotFoundException { | |
int size = in.readInt(); | |
for (int i = 0; i < size; i++) { | |
Object key = in.readObject(); | |
Object value = in.readObject(); | |
put(key, value); | |
} | |
} | |
/** | |
* Serializes this map to the given stream. | |
* | |
* @param out the stream to serialize to | |
* @throws IOException if the stream raises it | |
*/ | |
public void writeExternal(ObjectOutput out) throws IOException { | |
out.writeInt(size()); | |
for (Entry pos = sentinel.next; pos != sentinel; pos = pos.next) { | |
out.writeObject(pos.getKey()); | |
out.writeObject(pos.getValue()); | |
} | |
} | |
// add a serial version uid, so that if we change things in the future | |
// without changing the format, we can still deserialize properly. | |
private static final long serialVersionUID = 3380552487888102930L; | |
} |