Package org.apache.commons.collections4.map

# Class AbstractLinkedMap<K,V>

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

Type Parameters:
  `K` - the type of the keys in this map
  `V` - the type of the values in this map

All Implemented Interfaces:
  `Map<K,V>`, `Get<K,V>`, `IterableGet<K,V>`, `IterableMap<K,V>`, `OrderedMap<K,V>`, `Put<K,V>`

Direct Known Subclasses:
  `LinkedMap`, `LRUMap`

public abstract 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 behavior, 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:
  3.0

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  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.

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

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

  ## Nested classes/interfaces inherited from class java.util.AbstractMap

  `AbstractMap.SimpleEntry<K extends Object,V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object,V extends Object>`

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

  `Map.Entry<K extends Object,V extends Object>`

- ## Field Summary

  ### Fields inherited from class org.apache.commons.collections4.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`

- ## Constructor Summary

  Constructors
  Modifier
  Constructor
  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.

- ## Method Summary

  Modifier and Type
  Method
  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()`
  Initialize 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.

  ### Methods inherited from class org.apache.commons.collections4.map.AbstractHashedMap

  `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`

  ### Methods inherited from class java.lang.Object

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

  ### Methods inherited from interface org.apache.commons.collections4.Get

  `containsKey, entrySet, get, isEmpty, keySet, remove, size, values`

  ### Methods inherited from interface java.util.Map

  `compute, computeIfAbsent, computeIfPresent, containsKey, entrySet, equals, forEach, get, getOrDefault, hashCode, isEmpty, keySet, merge, put, putAll, putIfAbsent, remove, remove, replace, replace, replaceAll, size, values`

  ### Methods inherited from interface org.apache.commons.collections4.Put

  `put, putAll`

- ## Constructor Details

  - ### AbstractLinkedMap

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

  - ### 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 negative

  - ### 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 negative
      `IllegalArgumentException` - if the load factor is less than zero

  - ### 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(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 Details

  - ### 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

  - ### 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>`
    Specified by:
      `clear` in interface `Put<K,V>`
    Overrides:
      `clear` in class `AbstractHashedMap<K,V>`
    See Also:
      - `Map.clear()`

  - ### containsValue

    public boolean containsValue(Object value)
    Checks whether the map contains the specified value.
    Specified by:
      `containsValue` in interface `Get<K,V>`
    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
    See Also:
      - `Map.containsValue(Object)`

  - ### createEntry

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

  - ### 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<K> 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

  - ### 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:
      3.1

  - ### 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:
      3.1

  - ### firstKey

    public K firstKey()
    Gets the first key in the map, which is the first inserted.
    Specified by:
      `firstKey` in interface `OrderedMap<K,V>`
    Returns:
      the eldest 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

  - ### getEntry

    protected AbstractLinkedMap.LinkEntry<K,V> getEntry(Object key)
    Description copied from class: `AbstractHashedMap`
    Gets the entry mapped to the key specified.

    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.

    Overrides:
      `getEntry` in class `AbstractHashedMap<K,V>`
    Parameters:
      `key` - the key
    Returns:
      the entry, null if no match

  - ### init

    protected void init()
    Initialize this subclass during construction.

    NOTE: As from v3.2 this method calls `createEntry(HashEntry, int, Object, Object)` to create the map entry object.

    Overrides:
      `init` in class `AbstractHashedMap<K,V>`

  - ### lastKey

    public K lastKey()
    Gets the last key in the map, which is the most recently inserted.
    Specified by:
      `lastKey` in interface `OrderedMap<K,V>`
    Returns:
      the most recently inserted key

  - ### mapIterator

    public OrderedMapIterator<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. It also avoids creating the Map.Entry object.

    Specified by:
      `mapIterator` in interface `IterableGet<K,V>`
    Specified by:
      `mapIterator` in interface `OrderedMap<K,V>`
    Overrides:
      `mapIterator` in class `AbstractHashedMap<K,V>`
    Returns:
      the map iterator

  - ### nextKey

    public K nextKey(Object 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(Object 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

  - ### 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