org.apache.commons.collections.map
Class AbstractLinkedMap<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      org.apache.commons.collections.map.AbstractHashedMap<K,V>
          org.apache.commons.collections.map.AbstractLinkedMap<K,V>

All Implemented Interfaces:

Map<K,V>, IterableMap<K,V>, OrderedMap<K,V>

Direct Known Subclasses:

LinkedMap, LRUMap

public class AbstractLinkedMap<K,V>
extends AbstractHashedMap<K,V>
implements OrderedMap<K,V>

An abstract implementation of a hash-based map that links entries to create an ordered map and which provides numerous points for subclasses to override.

This class implements all the features necessary for a subclass linked hash-based map. Key-value entries are stored in instances of the LinkEntry class which can be overridden and replaced. The iterators can similarly be replaced, without the need to replace the KeySet, EntrySet and Values view classes.

Overridable methods are provided to change the default hashing behaviour, and to change how entries are added to and removed from the map. Hopefully, all you need for unusual subclasses is here.

This implementation maintains order by original insertion, but subclasses may work differently. The OrderedMap interface is implemented to provide access to bidirectional iteration and extra convenience methods.

The orderedMapIterator() method provides direct access to a bidirectional iterator. The iterators from the other views can also be cast to OrderedIterator if required.

All the available iterators can be reset back to the start by casting to ResettableIterator and calling reset().

The implementation is also designed to be subclassed, with lots of useful methods exposed.

Since:

Commons Collections 3.0

Version:

$Revision: 1.1.1.1 $ $Date: 2005/05/23 04:35:40 $

Author:

java util LinkedHashMap, Matt Hall, John Watkinson, Stephen Colebourne

Nested Class Summary

protected static class	AbstractLinkedMap.EntrySetIterator<K,V> EntrySet iterator.
protected static class	AbstractLinkedMap.KeySetIterator<K,V> KeySet iterator.
protected static class	AbstractLinkedMap.LinkEntry<K,V> LinkEntry that stores the data.
protected static class	AbstractLinkedMap.LinkIterator<K,V> Base Iterator that iterates in link order.
protected static class	AbstractLinkedMap.LinkMapIterator<K,V> MapIterator implementation.
protected static class	AbstractLinkedMap.ValuesIterator<K,V> Values iterator.

Nested classes/interfaces inherited from class org.apache.commons.collections.map.AbstractHashedMap

AbstractHashedMap.EntrySet<K,V>, AbstractHashedMap.HashEntry<K,V>, AbstractHashedMap.HashIterator<K,V>, AbstractHashedMap.HashMapIterator<K,V>, AbstractHashedMap.KeySet<K,V>, AbstractHashedMap.Values<K,V>

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K,V>

Field Summary

protected AbstractLinkedMap.LinkEntry<K,V>

header Header in the linked list

Fields inherited from class org.apache.commons.collections.map.AbstractHashedMap

data, DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD, entrySet, GETKEY_INVALID, GETVALUE_INVALID, keySet, loadFactor, MAXIMUM_CAPACITY, modCount, NO_NEXT_ENTRY, NO_PREVIOUS_ENTRY, NULL, REMOVE_INVALID, SETVALUE_INVALID, size, threshold, values

Constructor Summary

protected	AbstractLinkedMap() Constructor only used in deserialization, do not use otherwise.
protected	AbstractLinkedMap(int initialCapacity) Constructs a new, empty map with the specified initial capacity.
protected	AbstractLinkedMap(int initialCapacity, float loadFactor) Constructs a new, empty map with the specified initial capacity and load factor.
protected	AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold) Constructor which performs no validation on the passed in parameters.
protected	AbstractLinkedMap(Map<? extends K,? extends V> map) Constructor copying elements from another map.

Method Summary

protected void	addEntry(AbstractHashedMap.HashEntry<K,V> entry, int hashIndex) Adds an entry into this map, maintaining insertion order.
void	clear() Clears the map, resetting the size to zero and nullifying references to avoid garbage collection issues.
boolean	containsValue(Object value) Checks whether the map contains the specified value.
protected AbstractHashedMap.HashEntry<K,V>	createEntry(AbstractHashedMap.HashEntry<K,V> next, int hashCode, K key, V value) Creates an entry to store the data.
protected Iterator<Map.Entry<K,V>>	createEntrySetIterator() Creates an entry set iterator.
protected Iterator	createKeySetIterator() Creates a key set iterator.
protected Iterator<V>	createValuesIterator() Creates a values iterator.
protected AbstractLinkedMap.LinkEntry<K,V>	entryAfter(AbstractLinkedMap.LinkEntry<K,V> entry) Gets the after field from a LinkEntry.
protected AbstractLinkedMap.LinkEntry<K,V>	entryBefore(AbstractLinkedMap.LinkEntry<K,V> entry) Gets the before field from a LinkEntry.
K	firstKey() Gets the first key in the map, which is the most recently inserted.
protected AbstractLinkedMap.LinkEntry<K,V>	getEntry(int index) Gets the key at the specified index.
protected void	init() Initialise this subclass during construction.
K	lastKey() Gets the last key in the map, which is the first inserted.
MapIterator<K,V>	mapIterator() Gets an iterator over the map.
K	nextKey(K key) Gets the next key in sequence.
OrderedMapIterator<K,V>	orderedMapIterator() Gets a bidirectional iterator over the map.
K	previousKey(K key) Gets the previous key in sequence.
protected void	removeEntry(AbstractHashedMap.HashEntry<K,V> entry, int hashIndex, AbstractHashedMap.HashEntry<K,V> previous) Removes an entry from the map and the linked list.

Methods inherited from class org.apache.commons.collections.map.AbstractHashedMap

addMapping, calculateNewCapacity, calculateThreshold, checkCapacity, clone, containsKey, destroyEntry, doReadObject, doWriteObject, ensureCapacity, entryHashCode, entryKey, entryNext, entrySet, entryValue, equals, get, getEntry, hash, hashCode, hashIndex, isEmpty, isEqualKey, isEqualValue, keySet, put, putAll, remove, removeMapping, reuseEntry, size, toString, updateEntry, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

containsKey, entrySet, equals, get, hashCode, isEmpty, keySet, put, putAll, remove, size, values

Field Detail

header

protected transient AbstractLinkedMap.LinkEntry<K,V> header

Header in the linked list

Constructor Detail

AbstractLinkedMap

protected AbstractLinkedMap()

Constructor only used in deserialization, do not use otherwise.

AbstractLinkedMap

protected AbstractLinkedMap(int initialCapacity,
                            float loadFactor,
                            int threshold)

Constructor which performs no validation on the passed in parameters.

Parameters:

initialCapacity - the initial capacity, must be a power of two

loadFactor - the load factor, must be > 0.0f and generally < 1.0f

threshold - the threshold, must be sensible

AbstractLinkedMap

protected AbstractLinkedMap(int initialCapacity)

Constructs a new, empty map with the specified initial capacity.

Parameters:

initialCapacity - the initial capacity

Throws:

IllegalArgumentException - if the initial capacity is less than one

AbstractLinkedMap

protected AbstractLinkedMap(int initialCapacity,
                            float loadFactor)

Constructs a new, empty map with the specified initial capacity and load factor.

Parameters:

initialCapacity - the initial capacity

loadFactor - the load factor

Throws:

IllegalArgumentException - if the initial capacity is less than one

IllegalArgumentException - if the load factor is less than zero

AbstractLinkedMap

protected AbstractLinkedMap(Map<? extends K,? extends V> map)

Constructor copying elements from another map.

Parameters:

map - the map to copy

Throws:

NullPointerException - if the map is null

Method Detail

init

protected void init()

Initialise this subclass during construction.

Overrides:

init in class AbstractHashedMap<K,V>

containsValue

public boolean containsValue(Object value)

Checks whether the map contains the specified value.

Specified by:

containsValue in interface Map<K,V>

Overrides:

containsValue in class AbstractHashedMap<K,V>

Parameters:

value - the value to search for

Returns:

true if the map contains the value

clear

public void clear()

Clears the map, resetting the size to zero and nullifying references to avoid garbage collection issues.

Specified by:

clear in interface Map<K,V>

Overrides:

clear in class AbstractHashedMap<K,V>

firstKey

public K firstKey()

Gets the first key in the map, which is the most recently inserted.

Specified by:

firstKey in interface OrderedMap<K,V>

Returns:

the most recently inserted key

lastKey

public K lastKey()

Gets the last key in the map, which is the first inserted.

Specified by:

lastKey in interface OrderedMap<K,V>

Returns:

the eldest key

nextKey

public K nextKey(K key)

Gets the next key in sequence.

Specified by:

nextKey in interface OrderedMap<K,V>

Parameters:

key - the key to get after

Returns:

the next key

previousKey

public K previousKey(K key)

Gets the previous key in sequence.

Specified by:

previousKey in interface OrderedMap<K,V>

Parameters:

key - the key to get before

Returns:

the previous key

getEntry

protected AbstractLinkedMap.LinkEntry<K,V> getEntry(int index)

Gets the key at the specified index.

Parameters:

index - the index to retrieve

Returns:

the key at the specified index

Throws:

IndexOutOfBoundsException - if the index is invalid

addEntry

protected void addEntry(AbstractHashedMap.HashEntry<K,V> entry,
                        int hashIndex)

Adds an entry into this map, maintaining insertion order.

This implementation adds the entry to the data storage table and to the end of the linked list.

Overrides:

addEntry in class AbstractHashedMap<K,V>

Parameters:

entry - the entry to add

hashIndex - the index into the data array to store at

createEntry

protected AbstractHashedMap.HashEntry<K,V> createEntry(AbstractHashedMap.HashEntry<K,V> next,
                                                       int hashCode,
                                                       K key,
                                                       V value)

Creates an entry to store the data.

This implementation creates a new LinkEntry instance.

Overrides:

createEntry in class AbstractHashedMap<K,V>

Parameters:

next - the next entry in sequence

hashCode - the hash code to use

key - the key to store

value - the value to store

Returns:

the newly created entry

removeEntry

protected void removeEntry(AbstractHashedMap.HashEntry<K,V> entry,
                           int hashIndex,
                           AbstractHashedMap.HashEntry<K,V> previous)

Removes an entry from the map and the linked list.

This implementation removes the entry from the linked list chain, then calls the superclass implementation.

Overrides:

removeEntry in class AbstractHashedMap<K,V>

Parameters:

entry - the entry to remove

hashIndex - the index into the data structure

previous - the previous entry in the chain

entryBefore

protected AbstractLinkedMap.LinkEntry<K,V> entryBefore(AbstractLinkedMap.LinkEntry<K,V> entry)

Gets the before field from a LinkEntry. Used in subclasses that have no visibility of the field.

Parameters:

entry - the entry to query, must not be null

Returns:

the before field of the entry

Throws:

NullPointerException - if the entry is null

Since:

Commons Collections 3.1

entryAfter

protected AbstractLinkedMap.LinkEntry<K,V> entryAfter(AbstractLinkedMap.LinkEntry<K,V> entry)

Gets the after field from a LinkEntry. Used in subclasses that have no visibility of the field.

Parameters:

entry - the entry to query, must not be null

Returns:

the after field of the entry

Throws:

NullPointerException - if the entry is null

Since:

Commons Collections 3.1

mapIterator

public MapIterator<K,V> mapIterator()

Gets an iterator over the map. Changes made to the iterator affect this map.

A MapIterator returns the keys in the map. It also provides convenient methods to get the key and value, and set the value. It avoids the need to create an entrySet/keySet/values object.

Specified by:

mapIterator in interface IterableMap<K,V>

Overrides:

mapIterator in class AbstractHashedMap<K,V>

Returns:

the map iterator

orderedMapIterator

public OrderedMapIterator<K,V> orderedMapIterator()

Gets a bidirectional iterator over the map. Changes made to the iterator affect this map.

A MapIterator returns the keys in the map. It also provides convenient methods to get the key and value, and set the value. It avoids the need to create an entrySet/keySet/values object.

Specified by:

orderedMapIterator in interface OrderedMap<K,V>

Returns:

the map iterator

createEntrySetIterator

protected Iterator<Map.Entry<K,V>> createEntrySetIterator()

Creates an entry set iterator. Subclasses can override this to return iterators with different properties.

Overrides:

createEntrySetIterator in class AbstractHashedMap<K,V>

Returns:

the entrySet iterator

createKeySetIterator

protected Iterator createKeySetIterator()

Creates a key set iterator. Subclasses can override this to return iterators with different properties.

Overrides:

createKeySetIterator in class AbstractHashedMap<K,V>

Returns:

the keySet iterator

createValuesIterator

protected Iterator<V> createValuesIterator()

Creates a values iterator. Subclasses can override this to return iterators with different properties.

Overrides:

createValuesIterator in class AbstractHashedMap<K,V>

Returns:

the values iterator