org.apache.commons.collections.map
Class LRUMap<K,V>

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

All Implemented Interfaces:

Serializable, Cloneable, Map<K,V>, BoundedMap<K,V>, IterableMap<K,V>, OrderedMap<K,V>

public class LRUMap<K,V>
extends AbstractLinkedMap<K,V>
implements BoundedMap<K,V>, Serializable, Cloneable

A Map implementation with a fixed maximum size which removes the least recently used entry if an entry is added when full.

The least recently used algorithm works on the get and put operations only. Iteration of any kind, including setting the value by iteration, does not change the order. Queries such as containsKey and containsValue or access via views also do not change the order.

The map implements OrderedMap and entries may be queried using the bidirectional OrderedMapIterator. The order returned is least recently used to most recently used. Iterators from map 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().

Since:

Commons Collections 3.0 (previously in main package v1.0)

Version:

$Revision: 1.1.1.1 $ $Date: 2005/05/23 04:35:57 $

Author:

James Strachan, Morgan Delagrange, Stephen Colebourne, Mike Pettypiece, Matt Hall, John Watkinson, Mario Ivankovits

See Also:

Serialized Form

Nested Class Summary

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

AbstractLinkedMap.EntrySetIterator<K,V>, AbstractLinkedMap.KeySetIterator<K,V>, AbstractLinkedMap.LinkEntry<K,V>, AbstractLinkedMap.LinkIterator<K,V>, AbstractLinkedMap.LinkMapIterator<K,V>, AbstractLinkedMap.ValuesIterator<K,V>

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

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

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

Map.Entry<K,V>

Field Summary

protected static int

DEFAULT_MAX_SIZE Default maximum size

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

header

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

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

Constructor Summary

LRUMap()
Constructs a new empty map with a maximum size of 100.

LRUMap(int maxSize)
Constructs a new, empty map with the specified maximum size.

LRUMap(int maxSize, boolean scanUntilRemovable)
Constructs a new, empty map with the specified maximum size.

LRUMap(int maxSize, float loadFactor)
Constructs a new, empty map with the specified initial capacity and load factor.

LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable)
Constructs a new, empty map with the specified initial capacity and load factor.

LRUMap(Map<? extends K,? extends V> map)
Constructor copying elements from another map.

LRUMap(Map<? extends K,? extends V> map, boolean scanUntilRemovable)
Constructor copying elements from another map.

Method Summary

protected void	addMapping(int hashIndex, int hashCode, K key, V value) Adds a new key-value mapping into this map.
Object	clone() Clones the map without cloning the keys or values.
protected void	doReadObject(ObjectInputStream in) Reads the data necessary for put() to work in the superclass.
protected void	doWriteObject(ObjectOutputStream out) Writes the data necessary for put() to work in deserialization.
V	get(Object key) Gets the value mapped to the key specified.
boolean	isFull() Returns true if this map is full and no new mappings can be added.
boolean	isScanUntilRemovable() Whether this LRUMap will scan until a removable entry is found when the map is full.
int	maxSize() Gets the maximum size of the map (the bound).
protected void	moveToMRU(AbstractLinkedMap.LinkEntry<K,V> entry) Moves an entry to the MRU position at the end of the list.
protected boolean	removeLRU(AbstractLinkedMap.LinkEntry<K,V> entry) Subclass method to control removal of the least recently used entry from the map.
protected void	reuseMapping(AbstractLinkedMap.LinkEntry<K,V> entry, int hashIndex, int hashCode, K key, V value) Reuses an entry by removing it and moving it to a new place in the map.
protected void	updateEntry(AbstractHashedMap.HashEntry<K,V> entry, V newValue) Updates an existing key-value mapping.

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

addEntry, clear, containsValue, createEntry, createEntrySetIterator, createKeySetIterator, createValuesIterator, entryAfter, entryBefore, firstKey, getEntry, init, lastKey, mapIterator, nextKey, orderedMapIterator, previousKey, removeEntry

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

calculateNewCapacity, calculateThreshold, checkCapacity, containsKey, destroyEntry, ensureCapacity, entryHashCode, entryKey, entryNext, entrySet, entryValue, equals, getEntry, hash, hashCode, hashIndex, isEmpty, isEqualKey, isEqualValue, keySet, put, putAll, remove, removeMapping, reuseEntry, size, toString, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

clear, containsKey, containsValue, entrySet, equals, hashCode, isEmpty, keySet, put, putAll, remove, size, values

Field Detail

DEFAULT_MAX_SIZE

protected static final int DEFAULT_MAX_SIZE

Default maximum size

See Also:

Constant Field Values

Constructor Detail

LRUMap

public LRUMap()

Constructs a new empty map with a maximum size of 100.

LRUMap

public LRUMap(int maxSize)

Constructs a new, empty map with the specified maximum size.

Parameters:

maxSize - the maximum size of the map

Throws:

IllegalArgumentException - if the maximum size is less than one

LRUMap

public LRUMap(int maxSize,
              boolean scanUntilRemovable)

Constructs a new, empty map with the specified maximum size.

Parameters:

maxSize - the maximum size of the map

scanUntilRemovable - scan until a removeable entry is found, default false

Throws:

IllegalArgumentException - if the maximum size is less than one

Since:

Commons Collections 3.1

LRUMap

public LRUMap(int maxSize,
              float loadFactor)

Constructs a new, empty map with the specified initial capacity and load factor.

Parameters:

maxSize - the maximum size of the map, -1 for no limit,

loadFactor - the load factor

Throws:

IllegalArgumentException - if the maximum size is less than one

IllegalArgumentException - if the load factor is less than zero

LRUMap

public LRUMap(int maxSize,
              float loadFactor,
              boolean scanUntilRemovable)

Constructs a new, empty map with the specified initial capacity and load factor.

Parameters:

maxSize - the maximum size of the map, -1 for no limit,

loadFactor - the load factor

scanUntilRemovable - scan until a removeable entry is found, default false

Throws:

IllegalArgumentException - if the maximum size is less than one

IllegalArgumentException - if the load factor is less than zero

Since:

Commons Collections 3.1

LRUMap

public LRUMap(Map<? extends K,? extends V> map)

Constructor copying elements from another map.

The maximum size is set from the map's size.

Parameters:

map - the map to copy

Throws:

NullPointerException - if the map is null

IllegalArgumentException - if the map is empty

LRUMap

public LRUMap(Map<? extends K,? extends V> map,
              boolean scanUntilRemovable)

Constructor copying elements from another map.

The maximum size is set from the map's size.

Parameters:

map - the map to copy

scanUntilRemovable - scan until a removeable entry is found, default false

Throws:

NullPointerException - if the map is null

IllegalArgumentException - if the map is empty

Since:

Commons Collections 3.1

Method Detail

get

public V get(Object key)

Gets the value mapped to the key specified.

This operation changes the position of the key in the map to the most recently used position (first).

Specified by:

get in interface Map<K,V>

Overrides:

get in class AbstractHashedMap<K,V>

Parameters:

key - the key

Returns:

the mapped value, null if no match

moveToMRU

protected void moveToMRU(AbstractLinkedMap.LinkEntry<K,V> entry)

Moves an entry to the MRU position at the end of the list.

This implementation moves the updated entry to the end of the list.

Parameters:

entry - the entry to update

updateEntry

protected void updateEntry(AbstractHashedMap.HashEntry<K,V> entry,
                           V newValue)

Updates an existing key-value mapping.

This implementation moves the updated entry to the top of the list using moveToMRU(org.apache.commons.collections.map.AbstractLinkedMap.LinkEntry).

Overrides:

updateEntry in class AbstractHashedMap<K,V>

Parameters:

entry - the entry to update

newValue - the new value to store

addMapping

protected void addMapping(int hashIndex,
                          int hashCode,
                          K key,
                          V value)

Adds a new key-value mapping into this map.

This implementation checks the LRU size and determines whether to discard an entry or not using removeLRU(org.apache.commons.collections.map.AbstractLinkedMap.LinkEntry).

From Commons Collections 3.1 this method uses isFull() rather than accessing size and maxSize directly. It also handles the scanUntilRemovable functionality.

Overrides:

addMapping in class AbstractHashedMap<K,V>

Parameters:

hashIndex - the index into the data array to store at

hashCode - the hash code of the key to add

key - the key to add

value - the value to add

reuseMapping

protected void reuseMapping(AbstractLinkedMap.LinkEntry<K,V> entry,
                            int hashIndex,
                            int hashCode,
                            K key,
                            V value)

Reuses an entry by removing it and moving it to a new place in the map.

This method uses AbstractLinkedMap.removeEntry(org.apache.commons.collections.map.AbstractHashedMap.HashEntry, int, org.apache.commons.collections.map.AbstractHashedMap.HashEntry), AbstractHashedMap.reuseEntry(org.apache.commons.collections.map.AbstractHashedMap.HashEntry, int, int, K, V) and AbstractLinkedMap.addEntry(org.apache.commons.collections.map.AbstractHashedMap.HashEntry, int).

Parameters:

entry - the entry to reuse

hashIndex - the index into the data array to store at

hashCode - the hash code of the key to add

key - the key to add

value - the value to add

removeLRU

protected boolean removeLRU(AbstractLinkedMap.LinkEntry<K,V> entry)

Subclass method to control removal of the least recently used entry from the map.

This method exists for subclasses to override. A subclass may wish to provide cleanup of resources when an entry is removed. For example:

 protected boolean removeLRU(LinkEntry entry) {
   releaseResources(entry.getValue());  // release resources held by entry
   return true;  // actually delete entry
 }
 

Alternatively, a subclass may choose to not remove the entry or selectively keep certain LRU entries. For example:

 protected boolean removeLRU(LinkEntry entry) {
   if (entry.getKey().toString().startsWith("System.")) {
     return false;  // entry not removed from LRUMap
   } else {
     return true;  // actually delete entry
   }
 }
 

The effect of returning false is dependent on the scanUntilRemovable flag. If the flag is true, the next LRU entry will be passed to this method and so on until one returns false and is removed, or every entry in the map has been passed. If the scanUntilRemovable flag is false, the map will exceed the maximum size.

NOTE: Commons Collections 3.0 passed the wrong entry to this method. This is fixed in version 3.1 onwards.

Parameters:

entry - the entry to be removed

isFull

public boolean isFull()

Returns true if this map is full and no new mappings can be added.

Specified by:

isFull in interface BoundedMap<K,V>

Returns:

true if the map is full

maxSize

public int maxSize()

Gets the maximum size of the map (the bound).

Specified by:

maxSize in interface BoundedMap<K,V>

Returns:

the maximum number of elements the map can hold

isScanUntilRemovable

public boolean isScanUntilRemovable()

Whether this LRUMap will scan until a removable entry is found when the map is full.

Returns:

true if this map scans

Since:

Commons Collections 3.1

clone

public Object clone()

Clones the map without cloning the keys or values.

Overrides:

clone in class AbstractHashedMap<K,V>

Returns:

a shallow clone

doWriteObject

protected void doWriteObject(ObjectOutputStream out)
                      throws IOException

Writes the data necessary for put() to work in deserialization.

Overrides:

doWriteObject in class AbstractHashedMap<K,V>

Parameters:

out - the output stream

Throws:

IOException

doReadObject

protected void doReadObject(ObjectInputStream in)
                     throws IOException,
                            ClassNotFoundException

Reads the data necessary for put() to work in the superclass.

Overrides:

doReadObject in class AbstractHashedMap<K,V>

Parameters:

in - the input stream

Throws:

IOException

ClassNotFoundException