org.apache.commons.collections.map

Class AbstractLinkedMap

public class AbstractLinkedMap extends AbstractHashedMap implements OrderedMap

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: 158688 $ $Date: 2005-03-22 22:14:15 +0000 (Tue, 22 Mar 2005) $

Author: java util LinkedHashMap Stephen Colebourne

Nested Class Summary
protected static classAbstractLinkedMap.EntrySetIterator
EntrySet iterator.
protected static classAbstractLinkedMap.KeySetIterator
KeySet iterator.
protected static classAbstractLinkedMap.LinkEntry
LinkEntry that stores the data.
protected abstract static classAbstractLinkedMap.LinkIterator
Base Iterator that iterates in link order.
protected static classAbstractLinkedMap.LinkMapIterator
MapIterator implementation.
protected static classAbstractLinkedMap.ValuesIterator
Values iterator.
Field Summary
protected AbstractLinkedMap.LinkEntryheader
Header in the linked list
Constructor Summary
protected AbstractLinkedMap()
Constructor only used in deserialization, do not use otherwise.
protected AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold)
Constructor which performs no validation on the passed in parameters.
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(Map map)
Constructor copying elements from another map.
Method Summary
protected voidaddEntry(HashEntry entry, int hashIndex)
Adds an entry into this map, maintaining insertion order.
voidclear()
Clears the map, resetting the size to zero and nullifying references to avoid garbage collection issues.
booleancontainsValue(Object value)
Checks whether the map contains the specified value.
protected HashEntrycreateEntry(HashEntry next, int hashCode, Object key, Object value)
Creates an entry to store the data.
protected IteratorcreateEntrySetIterator()
Creates an entry set iterator.
protected IteratorcreateKeySetIterator()
Creates a key set iterator.
protected IteratorcreateValuesIterator()
Creates a values iterator.
protected AbstractLinkedMap.LinkEntryentryAfter(AbstractLinkedMap.LinkEntry entry)
Gets the after field from a LinkEntry.
protected AbstractLinkedMap.LinkEntryentryBefore(AbstractLinkedMap.LinkEntry entry)
Gets the before field from a LinkEntry.
ObjectfirstKey()
Gets the first key in the map, which is the most recently inserted.
protected AbstractLinkedMap.LinkEntrygetEntry(int index)
Gets the key at the specified index.
protected voidinit()
Initialise this subclass during construction.
ObjectlastKey()
Gets the last key in the map, which is the first inserted.
MapIteratormapIterator()
Gets an iterator over the map.
ObjectnextKey(Object key)
Gets the next key in sequence.
OrderedMapIteratororderedMapIterator()
Gets a bidirectional iterator over the map.
ObjectpreviousKey(Object key)
Gets the previous key in sequence.
protected voidremoveEntry(HashEntry entry, int hashIndex, HashEntry previous)
Removes an entry from the map and the linked list.

Field Detail

header

protected transient AbstractLinkedMap.LinkEntry 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 map)
Constructor copying elements from another map.

Parameters: map the map to copy

Throws: NullPointerException if the map is null

Method Detail

addEntry

protected void addEntry(HashEntry 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.

Parameters: entry the entry to add hashIndex the index into the data array to store at

clear

public void clear()
Clears the map, resetting the size to zero and nullifying references to avoid garbage collection issues.

containsValue

public boolean containsValue(Object value)
Checks whether the map contains the specified value.

Parameters: value the value to search for

Returns: true if the map contains the value

createEntry

protected HashEntry createEntry(HashEntry next, int hashCode, Object key, Object value)
Creates an entry to store the data.

This implementation creates a new LinkEntry instance.

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

createEntrySetIterator

protected Iterator createEntrySetIterator()
Creates an entry set iterator. Subclasses can override this to return iterators with different properties.

Returns: the entrySet iterator

createKeySetIterator

protected Iterator createKeySetIterator()
Creates a key set iterator. Subclasses can override this to return iterators with different properties.

Returns: the keySet iterator

createValuesIterator

protected Iterator createValuesIterator()
Creates a values iterator. Subclasses can override this to return iterators with different properties.

Returns: the values iterator

entryAfter

protected AbstractLinkedMap.LinkEntry entryAfter(AbstractLinkedMap.LinkEntry 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

entryBefore

protected AbstractLinkedMap.LinkEntry entryBefore(AbstractLinkedMap.LinkEntry 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

firstKey

public Object firstKey()
Gets the first key in the map, which is the most recently inserted.

Returns: the most recently inserted key

getEntry

protected AbstractLinkedMap.LinkEntry 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

init

protected void init()
Initialise this subclass during construction.

NOTE: As from v3.2 this method calls AbstractLinkedMap to create the map entry object.

lastKey

public Object lastKey()
Gets the last key in the map, which is the first inserted.

Returns: the eldest key

mapIterator

public MapIterator 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.

Returns: the map iterator

nextKey

public Object nextKey(Object key)
Gets the next key in sequence.

Parameters: key the key to get after

Returns: the next key

orderedMapIterator

public OrderedMapIterator 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.

Returns: the map iterator

previousKey

public Object previousKey(Object key)
Gets the previous key in sequence.

Parameters: key the key to get before

Returns: the previous key

removeEntry

protected void removeEntry(HashEntry entry, int hashIndex, HashEntry 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.

Parameters: entry the entry to remove hashIndex the index into the data structure previous the previous entry in the chain

Copyright © 2001-2008 Apache Software Foundation. All Rights Reserved.