org.apache.commons.collections
Class SequencedHashMap

java.lang.Object
  |
  +--org.apache.commons.collections.SequencedHashMap

All Implemented Interfaces:

Cloneable, Externalizable, Map, Serializable

Direct Known Subclasses:

LRUMap

public class SequencedHashMap

extends Object

implements Map, Cloneable, Externalizable

A map of objects whose mapping entries are sequenced based on the order in which they were added. This data structure has fast O(1) search time, deletion time, and insertion time.

Although this map is sequenced, it cannot implement List because of incompatible interface definitions. The remove methods in List and Map have different return values (see: List.remove(Object) and Map.remove(Object)).

This class is not thread safe. When a thread safe implementation is required, use Collections.synchronizedMap(Map) as it is documented, or use explicit synchronization controls.

Since:

2.0

Author:

Michael A. Smith, Daniel Rall, Henning P. Schmiedehausen

See Also:

Serialized Form

Constructor Summary

SequencedHashMap()
Construct a new sequenced hash map with default initial size and load factor.

SequencedHashMap(int initialSize)
Construct a new sequenced hash map with the specified initial size and default load factor.

SequencedHashMap(int initialSize, float loadFactor)
Construct a new sequenced hash map with the specified initial size and load factor.

SequencedHashMap(Map m)
Construct a new sequenced hash map and add all the elements in the specified map.

Method Summary

void	clear() Implements Map.clear().
Object	clone() Creates a shallow copy of this object, preserving the internal structure by copying only references.
boolean	containsKey(Object key) Implements Map.containsKey(Object).
boolean	containsValue(Object value) Implements Map.containsValue(Object).
Set	entrySet() Implements Map.entrySet().
boolean	equals(Object obj) Implements Map.equals(Object).
Object	get(int index) Returns the key at the specified index.
Object	get(Object o) Implements Map.get(Object).
Map.Entry	getFirst() Return the entry for the "oldest" mapping.
Object	getFirstKey() Return the key for the "oldest" mapping.
Object	getFirstValue() Return the value for the "oldest" mapping.
Map.Entry	getLast() Return the entry for the "newest" mapping.
Object	getLastKey() Return the key for the "newest" mapping.
Object	getLastValue() Return the value for the "newest" mapping.
Object	getValue(int index) Returns the value at the specified index.
int	hashCode() Implements Map.hashCode().
int	indexOf(Object key) Returns the index of the specified key.
boolean	isEmpty() Implements Map.isEmpty().
Iterator	iterator() Returns a key iterator.
Set	keySet() Implements Map.keySet().
int	lastIndexOf(Object key) Returns the last index of the specified key.
Object	put(Object key, Object value) Implements Map.put(Object, Object).
void	putAll(Map t) Adds all the mappings in the specified map to this map, replacing any mappings that already exist (as per Map.putAll(Map)).
void	readExternal(ObjectInput in) Deserializes this map from the given stream.
Object	remove(int index) Removes the element at the specified index.
Object	remove(Object key) Implements Map.remove(Object).
List	sequence() Returns a List view of the keys rather than a set view.
int	size() Implements Map.size().
String	toString() Provides a string representation of the entries within the map.
Collection	values() Implements Map.values().
void	writeExternal(ObjectOutput out) Serializes this map to the given stream.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

SequencedHashMap

public SequencedHashMap()

Construct a new sequenced hash map with default initial size and load factor.

SequencedHashMap

public SequencedHashMap(int initialSize)

Construct a new sequenced hash map with the specified initial size and default load factor.

Parameters:

initialSize - the initial size for the hash table

See Also:

HashMap.HashMap(int)

SequencedHashMap

public SequencedHashMap(int initialSize,
                        float loadFactor)

Construct a new sequenced hash map with the specified initial size and load factor.

Parameters:

initialSize - the initial size for the hash table

loadFactor - the load factor for the hash table.

See Also:

HashMap.HashMap(int,float)

SequencedHashMap

public SequencedHashMap(Map m)

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 putAll(Map).

Method Detail

clear

public void clear()

Implements Map.clear().

Specified by:

clear in interface Map

clone

public Object clone()
             throws CloneNotSupportedException

Creates a shallow copy of this object, preserving the internal structure by copying only references. The keys and values themselves are not clone()'d. The cloned object maintains the same sequence.

Overrides:

clone in class Object

Returns:

A clone of this instance.

Throws:

CloneNotSupportedException - if clone is not supported by a subclass.

containsKey

public boolean containsKey(Object key)

Implements Map.containsKey(Object).

Specified by:

containsKey in interface Map

containsValue

public boolean containsValue(Object value)

Implements Map.containsValue(Object).

Specified by:

containsValue in interface Map

entrySet

public Set entrySet()

Implements Map.entrySet().

Specified by:

entrySet in interface Map

equals

public boolean equals(Object obj)

Implements Map.equals(Object).

Specified by:

equals in interface Map

Overrides:

equals in class Object

get

public Object get(int index)

Returns the key at the specified index.

Throws:

ArrayIndexOutOfBoundsException - if the index is < 0 or > the size of the map.

get

public Object get(Object o)

Implements Map.get(Object).

Specified by:

get in interface Map

getFirst

public Map.Entry getFirst()

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 entrySet().iterator().next(), but this method provides an optimized implementation.

Returns:

The first entry in the sequence, or null if the map is empty.

getFirstKey

public Object getFirstKey()

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 getFirst().getKey(), but this method provides a slightly optimized implementation.

Returns:

The first key in the sequence, or null if the map is empty.

getFirstValue

public Object getFirstValue()

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 getFirst().getValue(), but this method provides a slightly optimized implementation.

Returns:

The first value in the sequence, or null if the map is empty.

getLast

public Map.Entry getLast()

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:

    Object obj = null;
    Iterator iter = entrySet().iterator();
    while(iter.hasNext()) {
      obj = iter.next();
    }
    return (Map.Entry)obj;
  

However, the implementation of this method ensures an O(1) lookup of the last key rather than O(n).

Returns:

The last entry in the sequence, or null if the map is empty.

getLastKey

public Object getLastKey()

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 getLast().getKey(), but this method provides a slightly optimized implementation.

Returns:

The last key in the sequence, or null if the map is empty.

getLastValue

public Object getLastValue()

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 getLast().getValue(), but this method provides a slightly optimized implementation.

Returns:

The last value in the sequence, or null if the map is empty.

getValue

public Object getValue(int index)

Returns the value at the specified index.

Throws:

ArrayIndexOutOfBoundsException - if the index is < 0 or > the size of the map.

hashCode

public int hashCode()

Implements Map.hashCode().

Specified by:

hashCode in interface Map

Overrides:

hashCode in class Object

indexOf

public int indexOf(Object key)

Returns the index of the specified key.

isEmpty

public boolean isEmpty()

Implements Map.isEmpty().

Specified by:

isEmpty in interface Map

iterator

public Iterator iterator()

Returns a key iterator.

keySet

public Set keySet()

Implements Map.keySet().

Specified by:

keySet in interface Map

lastIndexOf

public int lastIndexOf(Object key)

Returns the last index of the specified key.

put

public Object put(Object key,
                  Object value)

Implements Map.put(Object, Object).

Specified by:

put in interface Map

putAll

public void putAll(Map t)

Adds all the mappings in the specified map to this map, replacing any mappings that already exist (as per Map.putAll(Map)). The order in which the entries are added is determined by the iterator returned from Map.entrySet() for the specified map.

Specified by:

putAll in interface Map

Parameters:

t - the mappings that should be added to this map.

Throws:

NullPointerException - if t is null

readExternal

public void readExternal(ObjectInput in)
                  throws IOException,
                         ClassNotFoundException

Deserializes this map from the given stream.

Specified by:

readExternal in interface Externalizable

Parameters:

in - the stream to deserialize from

Throws:

IOException - if the stream raises it

ClassNotFoundException - if the stream raises it

remove

public Object remove(int index)

Removes the element at the specified index.

Parameters:

index - The index of the object to remove.

Returns:

The previous value coressponding the key, or null if none existed.

Throws:

ArrayIndexOutOfBoundsException - if the index is < 0 or > the size of the map.

remove

public Object remove(Object key)

Implements Map.remove(Object).

Specified by:

remove in interface Map

sequence

public List sequence()

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 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 keySet()

Returns:

The ordered list of keys.

See Also:

keySet()

size

public int size()

Implements Map.size().

Specified by:

size in interface Map

toString

public String toString()

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 entrySet().iterator() and iterate over the entries in the map formatting them as appropriate.

Overrides:

toString in class Object

values

public Collection values()

Implements Map.values().

Specified by:

values in interface Map

writeExternal

public void writeExternal(ObjectOutput out)
                   throws IOException

Serializes this map to the given stream.

Specified by:

writeExternal in interface Externalizable

Parameters:

out - the stream to serialize to

Throws:

IOException - if the stream raises it