public abstract class AbstractLinkedMap<K,V> extends AbstractHashedMap<K,V> implements OrderedMap<K,V>
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.
Modifier and Type | Class and Description |
---|---|
protected static class |
AbstractLinkedMap.EntrySetIterator<K,V>
EntrySet iterator.
|
protected static class |
AbstractLinkedMap.KeySetIterator<K>
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<V>
Values iterator.
|
AbstractHashedMap.EntrySet<K,V>, AbstractHashedMap.HashEntry<K,V>, AbstractHashedMap.HashIterator<K,V>, AbstractHashedMap.HashMapIterator<K,V>, AbstractHashedMap.KeySet<K>, AbstractHashedMap.Values<V>
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_THRESHOLD, GETKEY_INVALID, GETVALUE_INVALID, MAXIMUM_CAPACITY, NO_NEXT_ENTRY, NO_PREVIOUS_ENTRY, NULL, REMOVE_INVALID, SETVALUE_INVALID
Modifier | Constructor and Description |
---|---|
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.
|
Modifier and Type | Method and Description |
---|---|
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 AbstractLinkedMap.LinkEntry<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<K> |
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 first inserted.
|
protected AbstractLinkedMap.LinkEntry<K,V> |
getEntry(int index)
Gets the key at the specified index.
|
protected AbstractLinkedMap.LinkEntry<K,V> |
getEntry(Object key)
Gets the entry mapped to the key specified.
|
protected void |
init()
Initialise this subclass during construction.
|
K |
lastKey()
Gets the last key in the map, which is the most recently inserted.
|
OrderedMapIterator<K,V> |
mapIterator()
Gets an iterator over the map.
|
K |
nextKey(Object key)
Gets the next key in sequence.
|
K |
previousKey(Object 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.
|
addMapping, calculateNewCapacity, calculateThreshold, checkCapacity, clone, containsKey, convertKey, destroyEntry, doReadObject, doWriteObject, ensureCapacity, entryHashCode, entryKey, entryNext, entrySet, entryValue, equals, get, hash, hashCode, hashIndex, isEmpty, isEqualKey, isEqualValue, keySet, put, putAll, remove, removeMapping, reuseEntry, size, toString, updateEntry, values
containsKey, remove, size
finalize, getClass, notify, notifyAll, wait, wait, wait
protected AbstractLinkedMap()
protected AbstractLinkedMap(int initialCapacity, float loadFactor, int threshold)
initialCapacity
- the initial capacity, must be a power of twoloadFactor
- the load factor, must be > 0.0f and generally < 1.0fthreshold
- the threshold, must be sensibleprotected AbstractLinkedMap(int initialCapacity)
initialCapacity
- the initial capacityIllegalArgumentException
- if the initial capacity is negativeprotected AbstractLinkedMap(int initialCapacity, float loadFactor)
initialCapacity
- the initial capacityloadFactor
- the load factorIllegalArgumentException
- if the initial capacity is negativeIllegalArgumentException
- if the load factor is less than zeroprotected AbstractLinkedMap(Map<? extends K,? extends V> map)
map
- the map to copyNullPointerException
- if the map is nullprotected void init()
NOTE: As from v3.2 this method calls
AbstractHashedMap.createEntry(HashEntry, int, Object, Object)
to create
the map entry object.
init
in class AbstractHashedMap<K,V>
public boolean containsValue(Object value)
containsValue
in interface Map<K,V>
containsValue
in interface Get<K,V>
containsValue
in class AbstractHashedMap<K,V>
value
- the value to search forMap.containsValue(Object)
public void clear()
public K firstKey()
firstKey
in interface OrderedMap<K,V>
public K lastKey()
lastKey
in interface OrderedMap<K,V>
public K nextKey(Object key)
nextKey
in interface OrderedMap<K,V>
key
- the key to get afterprotected AbstractLinkedMap.LinkEntry<K,V> getEntry(Object key)
AbstractHashedMap
This method exists for subclasses that may need to perform a multi-step process accessing the entry. The public methods in this class don't use this method to gain a small performance boost.
getEntry
in class AbstractHashedMap<K,V>
key
- the keypublic K previousKey(Object key)
previousKey
in interface OrderedMap<K,V>
key
- the key to get beforeprotected AbstractLinkedMap.LinkEntry<K,V> getEntry(int index)
index
- the index to retrieveIndexOutOfBoundsException
- if the index is invalidprotected void addEntry(AbstractHashedMap.HashEntry<K,V> entry, int hashIndex)
This implementation adds the entry to the data storage table and to the end of the linked list.
addEntry
in class AbstractHashedMap<K,V>
entry
- the entry to addhashIndex
- the index into the data array to store atprotected AbstractLinkedMap.LinkEntry<K,V> createEntry(AbstractHashedMap.HashEntry<K,V> next, int hashCode, K key, V value)
This implementation creates a new LinkEntry instance.
createEntry
in class AbstractHashedMap<K,V>
next
- the next entry in sequencehashCode
- the hash code to usekey
- the key to storevalue
- the value to storeprotected void removeEntry(AbstractHashedMap.HashEntry<K,V> entry, int hashIndex, AbstractHashedMap.HashEntry<K,V> previous)
This implementation removes the entry from the linked list chain, then calls the superclass implementation.
removeEntry
in class AbstractHashedMap<K,V>
entry
- the entry to removehashIndex
- the index into the data structureprevious
- the previous entry in the chainprotected AbstractLinkedMap.LinkEntry<K,V> entryBefore(AbstractLinkedMap.LinkEntry<K,V> entry)
before
field from a LinkEntry
.
Used in subclasses that have no visibility of the field.entry
- the entry to query, must not be nullbefore
field of the entryNullPointerException
- if the entry is nullprotected AbstractLinkedMap.LinkEntry<K,V> entryAfter(AbstractLinkedMap.LinkEntry<K,V> entry)
after
field from a LinkEntry
.
Used in subclasses that have no visibility of the field.entry
- the entry to query, must not be nullafter
field of the entryNullPointerException
- if the entry is nullpublic OrderedMapIterator<K,V> mapIterator()
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. It also avoids creating the Map.Entry object.
mapIterator
in interface IterableGet<K,V>
mapIterator
in interface OrderedMap<K,V>
mapIterator
in class AbstractHashedMap<K,V>
protected Iterator<Map.Entry<K,V>> createEntrySetIterator()
createEntrySetIterator
in class AbstractHashedMap<K,V>
protected Iterator<K> createKeySetIterator()
createKeySetIterator
in class AbstractHashedMap<K,V>
protected Iterator<V> createValuesIterator()
createValuesIterator
in class AbstractHashedMap<K,V>
Copyright © 2001–2015 The Apache Software Foundation. All rights reserved.