org.apache.commons.collections.map

Class AbstractLinkedMap

Implemented Interfaces:
IterableMap, Map, IterableMap, OrderedMap
Known Direct Subclasses:
LinkedMap, LRUMap

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.

Version:
$Revision: 1.12 $ $Date: 2004/05/26 21:56:05 $

Authors:
java util LinkedHashMap
Stephen Colebourne

Since:
Commons Collections 3.0

Nested Class Summary

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

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

AbstractHashedMap.EntrySet, AbstractHashedMap.EntrySetIterator, AbstractHashedMap.HashEntry, AbstractHashedMap.HashIterator, AbstractHashedMap.HashMapIterator, AbstractHashedMap.KeySet, AbstractHashedMap.KeySetIterator, AbstractHashedMap.Values, AbstractHashedMap.ValuesIterator

Field Summary

protected AbstractLinkedMap.LinkEntry
header
Header in the linked list

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

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

Constructor Summary

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

Method Summary

protected void
addEntry(AbstractHashedMap.HashEntry 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
createEntry(AbstractHashedMap.HashEntry next, int hashCode, Object key, Object value)
Creates an entry to store the data.
protected Iterator
createEntrySetIterator()
Creates an entry set iterator.
protected Iterator
createKeySetIterator()
Creates a key set iterator.
protected Iterator
createValuesIterator()
Creates a values iterator.
protected AbstractLinkedMap.LinkEntry
entryAfter(AbstractLinkedMap.LinkEntry entry)
Gets the after field from a LinkEntry.
protected AbstractLinkedMap.LinkEntry
entryBefore(AbstractLinkedMap.LinkEntry entry)
Gets the before field from a LinkEntry.
Object
firstKey()
Gets the first key in the map, which is the most recently inserted.
protected AbstractLinkedMap.LinkEntry
getEntry(int index)
Gets the key at the specified index.
protected void
init()
Initialise this subclass during construction.
Object
lastKey()
Gets the last key in the map, which is the first inserted.
MapIterator
mapIterator()
Gets an iterator over the map.
Object
nextKey(Object key)
Gets the next key in sequence.
OrderedMapIterator
orderedMapIterator()
Gets a bidirectional iterator over the map.
Object
previousKey(Object key)
Gets the previous key in sequence.
protected void
removeEntry(AbstractHashedMap.HashEntry entry, int hashIndex, AbstractHashedMap.HashEntry previous)
Removes an entry from the map and the linked list.

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

addEntry, addMapping, calculateNewCapacity, calculateThreshold, checkCapacity, clear, clone, containsKey, containsValue, convertKey, createEntry, createEntrySetIterator, createKeySetIterator, createValuesIterator, destroyEntry, doReadObject, doWriteObject, ensureCapacity, entryHashCode, entryKey, entryNext, entrySet, entryValue, equals, get, getEntry, hash, hashCode, hashIndex, init, isEmpty, isEqualKey, isEqualValue, keySet, mapIterator, put, putAll, remove, removeEntry, removeMapping, reuseEntry, size, toString, updateEntry, values

Field Details

header

protected AbstractLinkedMap.LinkEntry header
Header in the linked list

Constructor Details

AbstractLinkedMap

protected AbstractLinkedMap()
Constructor only used in deserialization, do not use otherwise.


AbstractLinkedMap

protected AbstractLinkedMap(Map map)
Constructor copying elements from another map.

Parameters:
map - the map to copy


AbstractLinkedMap

protected AbstractLinkedMap(int initialCapacity)
Constructs a new, empty map with the specified initial capacity.

Parameters:
initialCapacity - the initial capacity


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


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 <321.0f
threshold - the threshold, must be sensible

Method Details

addEntry

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

Overrides:
addEntry in interface AbstractHashedMap

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.
Overrides:
clear in interface AbstractHashedMap


containsValue

public boolean containsValue(Object value)
Checks whether the map contains the specified value.
Overrides:
containsValue in interface AbstractHashedMap

Parameters:
value - the value to search for

Returns:
true if the map contains the value


createEntry

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

This implementation creates a new LinkEntry instance.

Overrides:
createEntry in interface AbstractHashedMap

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.
Overrides:
createEntrySetIterator in interface AbstractHashedMap

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 interface AbstractHashedMap

Returns:
the keySet iterator


createValuesIterator

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

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

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

Since:
Commons Collections 3.1


firstKey

public Object firstKey()
Gets the first key in the map, which is the most recently inserted.
Specified by:
firstKey in interface OrderedMap

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


init

protected void init()
Initialise this subclass during construction.
Overrides:
init in interface AbstractHashedMap


lastKey

public Object lastKey()
Gets the last key in the map, which is the first inserted.
Specified by:
lastKey in interface OrderedMap

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.

Specified by:
mapIterator in interface IterableMap
Overrides:
mapIterator in interface AbstractHashedMap

Returns:
the map iterator


nextKey

public Object nextKey(Object key)
Gets the next key in sequence.
Specified by:
nextKey in interface OrderedMap

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.

Specified by:
orderedMapIterator in interface OrderedMap

Returns:
the map iterator


previousKey

public Object previousKey(Object key)
Gets the previous key in sequence.
Specified by:
previousKey in interface OrderedMap

Parameters:
key - the key to get before

Returns:
the previous key


removeEntry

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

Overrides:
removeEntry in interface AbstractHashedMap

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


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