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)}). * *
This class is not thread safe. When a thread safe implementation is
* required, wrap this class using {@link Collections#synchronizedMap(Map)},
* or use explicit synchronization controls.
*
* @author Michael A. Smith
* @author Daniel Rall
* @author Henning P. Schmiedehausen
*/
public class SequencedHashMap extends HashMap
{
/**
* {@link java.util.Map.Entry} that doubles as a node in the linked list
* of sequenced mappings.
**/
private static class Entry implements Map.Entry {
private final Object key_;
private Object value_;
Entry next = null;
Entry prev = null;
public Entry(Object key, Object value) {
this.key_ = key;
this.value_ = value;
}
public Object getKey() {
return this.key_;
}
public Object getValue() {
return this.value_;
}
public Object setValue(Object value) {
Object oldValue = this.value_;
this.value_ = value;
return oldValue;
}
public int hashCode() {
// per Map.Entry.hashCode() api docs
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;
Map.Entry other = (Map.Entry)obj;
// per Map.Entry.equals(Object api docs)
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() + "]";
}
}
private static final Entry createSentinel() {
Entry s = new Entry(null, null);
s.prev = s;
s.next = s;
return s;
}
private Entry sentinel;
private HashMap entries;
public SequencedHashMap() {
sentinel = createSentinel();
entries = new HashMap();
}
public SequencedHashMap(int initialSize) {
sentinel = createSentinel();
entries = new HashMap(initialSize);
}
public SequencedHashMap(int initialSize, float loadFactor) {
sentinel = createSentinel();
entries = new HashMap(initialSize, loadFactor);
}
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 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;
}
public int size() {
return entries.size();
}
public boolean isEmpty() {
return entries.isEmpty();
}
public boolean containsKey(Object key) {
return entries.containsKey(key);
}
public boolean containsValue(Object value) {
return entries.containsValue(value);
}
public Object get(Object o) {
// find entry for the specified key
Entry entry = (Entry)entries.get(o);
if(entry == null) return null;
return entry.getValue();
}
public Object put(Object key, Object value) {
Object oldValue = null;
Entry e = (Entry)entries.get(key);
if(e != null) {
// remove from list so the entry gets "moved" to the front of list
removeEntry(e);
// update value in map
oldValue = e.setValue(value);
} else {
// add new entry
e = new Entry(key, value);
entries.put(key, e);
}
// entry in map, but not list
// add to list
insertEntry(e);
return oldValue;
}
public Object remove(Object key) {
Entry e = (Entry)entries.remove(key);
if(e == null) return null;
removeEntry(e);
return e.getValue();
}
// use abstract map impl
//void putAll(Map t)
public void clear() {
entries.clear();
sentinel.next = sentinel;
sentinel.prev = sentinel;
}
public Set keySet() {
return new AbstractSet() {
// required impl
public Iterator iterator() { return new OrderedIterator(KEY); }
public boolean remove(Object o) {
return SequencedHashMap.this.remove(o) != 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);
}
};
}
public Collection values() {
return new AbstractCollection() {
// required impl
public Iterator iterator() { return new OrderedIterator(VALUE); }
public boolean remove(Object o) {
for(Entry pos = sentinel.next; pos != sentinel; pos = pos.next) {
if((pos.getValue() == null && o == null) ||
(pos.getValue() != null && pos.getValue().equals(o))) {
SequencedHashMap.this.remove(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);
}
};
}
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.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.remove(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;
}
};
}
private static final int KEY = 0;
private static final int VALUE = 1;
private static final int ENTRY = 2;
private class OrderedIterator implements Iterator {
private int returnType;
private Entry pos = sentinel;
boolean removable = false;
public OrderedIterator(int returnType) {
this.returnType = returnType;
}
public boolean hasNext() {
return pos.next != sentinel;
}
public Object next() {
if(pos.next == sentinel) {
throw new NoSuchElementException();
}
pos = pos.next;
removable = true;
switch(returnType) {
case KEY:
return pos.getKey();
case VALUE:
return pos.getValue();
case ENTRY:
return pos;
default:
throw new Error("bad iterator type");
}
}
public void remove() {
if(!removable) {
throw new IllegalStateException("remove() must follow next()");
}
SequencedHashMap.this.remove(pos.getKey());
}
}
// 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, values, and
* sequence are not clone()'d.
*
* @return A clone of this instance.
*/
public Object clone ()
{
// 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();
map.sentinel = createSentinel();
// note: this does not preserve the initial capacity and load factor.
map.entries = new HashMap();
map.putAll(this);
return map;
}
/**
* Returns the Map.Entry at the specified index
*
* @exception ArrayIndexOutOfBoundsException if the specified index is
* < 0 or > 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 && 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 index is
* < 0 or > 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 index is
* < 0 or > 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.
*
*
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 key, or
* null if none existed.
*
* @exception ArrayIndexOutOfBoundsException if the index is
* < 0 or > the size of the map.
*/
public Object remove (int index)
{
return remove(get(index));
}
}