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.
AbstractLinkedMap
protected AbstractLinkedMap()
Constructor only used in deserialization, do not use otherwise.
AbstractLinkedMap
protected AbstractLinkedMap(Map map)
Constructor copying elements from another map.
map
- the map to copy
AbstractLinkedMap
protected AbstractLinkedMap(int initialCapacity)
Constructs a new, empty map with the specified initial capacity.
initialCapacity
- the initial capacity
AbstractLinkedMap
protected AbstractLinkedMap(int initialCapacity,
float loadFactor)
Constructs a new, empty map with the specified initial capacity and
load factor.
initialCapacity
- the initial capacityloadFactor
- the load factor
AbstractLinkedMap
protected AbstractLinkedMap(int initialCapacity,
float loadFactor,
int threshold)
Constructor which performs no validation on the passed in parameters.
initialCapacity
- the initial capacity, must be a power of twoloadFactor
- the load factor, must be > 0.0f and generally <321.0fthreshold
- the threshold, must be sensible
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.
- addEntry in interface AbstractHashedMap
entry
- the entry to addhashIndex
- 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.
- clear in interface AbstractHashedMap
containsValue
public boolean containsValue(Object value)
Checks whether the map contains the specified value.
- containsValue in interface AbstractHashedMap
value
- the value to search for
- 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.
- createEntry in interface AbstractHashedMap
next
- the next entry in sequencehashCode
- the hash code to usekey
- the key to storevalue
- the value to store
- the newly created entry
createEntrySetIterator
protected Iterator createEntrySetIterator()
Creates an entry set iterator.
Subclasses can override this to return iterators with different properties.
- createEntrySetIterator in interface AbstractHashedMap
- the entrySet iterator
createKeySetIterator
protected Iterator createKeySetIterator()
Creates a key set iterator.
Subclasses can override this to return iterators with different properties.
- createKeySetIterator in interface AbstractHashedMap
- the keySet iterator
createValuesIterator
protected Iterator createValuesIterator()
Creates a values iterator.
Subclasses can override this to return iterators with different properties.
- createValuesIterator in interface AbstractHashedMap
- 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.
entry
- the entry to query, must not be null
- the
after
field of the entry
- 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.
entry
- the entry to query, must not be null
- the
before
field of the entry
- Commons Collections 3.1
firstKey
public Object firstKey()
Gets the first key in the map, which is the most recently inserted.
- firstKey in interface OrderedMap
- the most recently inserted key
getEntry
protected AbstractLinkedMap.LinkEntry getEntry(int index)
Gets the key at the specified index.
index
- the index to retrieve
- the key at the specified index
init
protected void init()
Initialise this subclass during construction.
- init in interface AbstractHashedMap
lastKey
public Object lastKey()
Gets the last key in the map, which is the first inserted.
- lastKey in interface OrderedMap
- 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.
- mapIterator in interface IterableMap
- mapIterator in interface AbstractHashedMap
- the map iterator
nextKey
public Object nextKey(Object key)
Gets the next key in sequence.
- nextKey in interface OrderedMap
key
- the key to get after
- 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.
- orderedMapIterator in interface OrderedMap
- the map iterator
previousKey
public Object previousKey(Object key)
Gets the previous key in sequence.
- previousKey in interface OrderedMap
key
- the key to get before
- 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.
- removeEntry in interface AbstractHashedMap
entry
- the entry to removehashIndex
- the index into the data structureprevious
- the previous entry in the chain