⇒ Index (Frames) |  ⇒ Index (No Frames) |  ⇒ Package |  ⇒ Package Tree |  ⇒ Full Tree 
org.apache.commons.collections.map

Class LRUMap

java.lang.Object
|
+--org.apache.commons.collections.map.AbstractHashedMap
   |
   +--org.apache.commons.collections.map.AbstractLinkedMap
      |
      +--org.apache.commons.collections.map.LRUMap

All Implemented Interfaces:
Cloneable, BoundedMap, IterableMap, OrderedMap, Serializable


public class LRUMap
extends AbstractLinkedMap
implements BoundedMap, 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)
Authors:
James Strachan
Morgan Delagrange
Stephen Colebourne

Field Summary

static int

DEFAULT_MAX_SIZE

Default maximum size

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, float loadFactor)

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

LRUMap(Map map)

Constructor copying elements from another map.

Method Summary

void

addMapping(int hashIndex, int hashCode, Object key, Object value)

Adds a new key-value mapping into this map.

Object

clone()

Clones the map without cloning the keys or values.

void

doReadObject(ObjectInputStream in)

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

void

doWriteObject(ObjectOutputStream out)

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

Object

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.

int

maxSize()

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

void

moveToMRU(AbstractLinkedMap.LinkEntry entry)

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

boolean

removeLRU(AbstractLinkedMap.LinkEntry entry)

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

void

reuseMapping(AbstractLinkedMap.LinkEntry entry, int hashIndex, int hashCode, Object key, Object value)

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

void

updateEntry(AbstractHashedMap.HashEntry entry, Object newValue)

Updates an existing key-value mapping.

Field Details

DEFAULT_MAX_SIZE

protected static final int DEFAULT_MAX_SIZE

Default maximum size

Constructor Details

LRUMap

public LRUMap()

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


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:
- if the maximum size is less than one
- if the load factor is less than zero

LRUMap

public LRUMap(int maxSize)

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

Parameters:
maxSize - the maximum size of the map
Throws:
- if the maximum size is less than one

LRUMap

public LRUMap(Map map)

Constructor copying elements from another map.

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

Parameters:
map - the map to copy
Throws:
- if the map is null
- if the map is empty

Method Details

addMapping

protected void addMapping(int hashIndex, int hashCode, Object key, Object 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.

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

clone

public Object clone()

Clones the map without cloning the keys or values.

Returns:
a shallow clone

doReadObject

protected void doReadObject(ObjectInputStream in)

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

Parameters:
in

doWriteObject

protected void doWriteObject(ObjectOutputStream out)

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

Parameters:
out

get

public Object 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).

Parameters:
key - the key
Returns:
the mapped value, null if no match

isFull

public boolean isFull()

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

Returns:
true if the map is full

maxSize

public int maxSize()

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

Returns:
the maximum number of elements the map can hold

moveToMRU

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

removeLRU

protected boolean removeLRU(AbstractLinkedMap.LinkEntry 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
   }
 }
Note that the effect of not removing an LRU is for the Map to exceed the maximum size.

Parameters:
entry - the entry to be removed

reuseMapping

protected void reuseMapping(AbstractLinkedMap.LinkEntry entry, int hashIndex, int hashCode, Object key, Object value)

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

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

updateEntry

protected void updateEntry(AbstractHashedMap.HashEntry entry, Object newValue)

Updates an existing key-value mapping. This implementation moves the updated entry to the top of the list.

Parameters:
entry - the entry to update
newValue - the new value to store