org.clapper.util.misc
Class LRUMap<K,V>

java.lang.Object
  java.util.AbstractMap<K,V>
      org.clapper.util.misc.LRUMap<K,V>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, java.util.Map<K,V>

public class LRUMap<K,V>
extends java.util.AbstractMap<K,V>
implements java.lang.Cloneable, java.io.Serializable

An LRUMap implements a Map of a fixed maximum size that enforces a least recently used discard policy. When the LRUMap is full (i.e., contains the maximum number of entries), any attempt to insert a new entry causes one of the least recently used entries to be discarded.

Note:

• The put() method "touches" (or "refreshes") an object, making it "new" again, even if it simply replaces the value for an existing key.
• The get() method also refreshes the retrieved object, but the iterator(), containsValue() and containsKey() methods do not refresh the objects in the cache.
• This implementation is not synchronized. If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. Unlike other Map implementations, even a simple get() operation structurally modifies an LRUMap. Synchronization can be accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap() method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

  Map m = Collections.synchronizedMap (new LRUMap (...));

There are other, similar implementations. For instance, see the LRUMap class in the Apache Jakarta Commons Collection API. (This leads to the obvious question: Why write another one? The primary answer is that I did not want to add another third-party library dependency. Plus, I wanted to experiment with this algorithm.)

Version:

$Revision: 6735 $

Author:

Copyright © 2004-2007 Brian M. Clapper

See Also:

Serialized Form

Nested Class Summary

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

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

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

java.util.Map.Entry<K,V>

Field Summary

static int	DEFAULT_INITIAL_CAPACITY The default initial capacity, if one isn't specified to the constructor
static float	DEFAULT_LOAD_FACTOR The default load factor, if one isn't specified to the constructor

Constructor Summary

LRUMap(int maxCapacity)
Construct a new empty map with a default capacity and load factor, and the specified maximum capacity.

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

LRUMap(int initialCapacity, int maxCapacity)
Construct a new empty map with the specified initial capacity, a default load factor, and the specified maximum capacity.

LRUMap(LRUMap<? extends K,? extends V> map)
Constructs a new map with the same mappings and parameters as the given LRUMap.

Method Summary

void	addRemovalListener(ObjectRemovalListener listener, boolean automaticOnly) Add an EventListener that will be called whenever an object is removed from the cache.
void	clear() Remove all mappings from this map.
protected java.lang.Object	clone() Returns a shallow copy of this instance.
boolean	containsKey(java.lang.Object key) Determine whether this map contains a mapping for a given key.
boolean	containsValue(java.lang.Object value) Determine whether this map contains a given value.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Get a set view of the mappings in this map.
V	get(java.lang.Object key) Retrieve an object from the map.
int	getInitialCapacity() Get the initial capacity of this LRUMap.
float	getLoadFactor() Get the load factor for this LRUMap.
int	getMaximumCapacity() Get the maximum capacity of this LRUMap.
boolean	isEmpty() Determine whether this map is empty or not.
java.util.Set<K>	keySet() Return a Set view of the keys in the map.
V	put(K key, V value) Associates the specified value with the specified key in this map.
void	putAll(java.util.Map<? extends K,? extends V> map) Copies all of the mappings from a specified map to this one.
V	remove(java.lang.Object key) Removes the mapping for a key, if there is one.
boolean	removeRemovalListener(ObjectRemovalListener listener) Remove an EventListener from the set of listeners to be invoked when an object is removed from the cache.
int	setMaximumCapacity(int newCapacity) Set or change the maximum capacity of this LRUMap.
int	size() Get the number of entries in the map.
java.util.Collection<V>	values() Returns a collection view of the values contained in this map.

Methods inherited from class java.util.AbstractMap

equals, hashCode, toString

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_LOAD_FACTOR

public static final float DEFAULT_LOAD_FACTOR

The default load factor, if one isn't specified to the constructor

See Also:

Constant Field Values

DEFAULT_INITIAL_CAPACITY

public static final int DEFAULT_INITIAL_CAPACITY

The default initial capacity, if one isn't specified to the constructor

See Also:

Constant Field Values

Constructor Detail

LRUMap

public LRUMap(int maxCapacity)

Construct a new empty map with a default capacity and load factor, and the specified maximum capacity.

Parameters:

maxCapacity - the maximum number of entries permitted in the map. Must not be negative.

LRUMap

public LRUMap(int initialCapacity,
              int maxCapacity)

Construct a new empty map with the specified initial capacity, a default load factor, and the specified maximum capacity.

Parameters:

initialCapacity - the initial capacity

maxCapacity - the maximum number of entries permitted in the map. Must not be negative.

LRUMap

public LRUMap(int initialCapacity,
              float loadFactor,
              int maxCapacity)

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

Parameters:

initialCapacity - the initial capacity

loadFactor - the load factor

maxCapacity - the maximum number of entries permitted in the map. Must not be negative.

LRUMap

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

Constructs a new map with the same mappings and parameters as the given LRUMap. The initial capacity and load factor is the same as for the parent HashMap class. The insertion order of the keys is preserved.

Parameters:

map - the map whose mappings are to be copied

Method Detail

addRemovalListener

public void addRemovalListener(ObjectRemovalListener listener,
                               boolean automaticOnly)

Add an EventListener that will be called whenever an object is removed from the cache. If automaticOnly is true, then the listener is only notified for objects that are removed automatically when the cache needs to be cleared to make room for new objects. If automaticOnly is false, then the listener is notified whenever an object is removed for any reason, include a call to the remove() method.

Note that when this map announces the removal of an object, it passes an ObjectRemovalEvent that contains a java.util.Map.Entry object that wraps the actual object that was removed. That way, both the key and the value are available for the removed object.

Parameters:

listener - the listener to add

automaticOnly - see above

See Also:

removeRemovalListener(org.clapper.util.misc.ObjectRemovalListener)

removeRemovalListener

public boolean removeRemovalListener(ObjectRemovalListener listener)

Remove an EventListener from the set of listeners to be invoked when an object is removed from the cache.

Parameters:

listener - the listener to add

Returns:

true if the listener was in the list and was removed, false otherwise

See Also:

addRemovalListener(org.clapper.util.misc.ObjectRemovalListener, boolean)

clear

public void clear()

Remove all mappings from this map.

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

containsKey

public boolean containsKey(java.lang.Object key)

Determine whether this map contains a mapping for a given key. Note that this implementation of containsKey() does not refresh the object in the cache.

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

Parameters:

key - the key to find

Returns:

true if the key is in the map, false if not

containsValue

public boolean containsValue(java.lang.Object value)

Determine whether this map contains a given value. Note that this implementation of containsValue() does not refresh the objects in the cache.

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class java.util.AbstractMap<K,V>

Parameters:

value - the value to find

Returns:

true if the value is in the map, false if not

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Get a set view of the mappings in this map. Each element in this set is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

Returns:

the entry set

get

public V get(java.lang.Object key)

Retrieve an object from the map. Retrieving an object from an LRU map "refreshes" the object so that it is among the most recently used objects.

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

Parameters:

key - the object's key in the map.

Returns:

the associated object, or null if not found

getInitialCapacity

public int getInitialCapacity()

Get the initial capacity of this LRUMap.

Returns:

the initial capacity, as passed to the constructor

See Also:

getLoadFactor(), getMaximumCapacity()

getLoadFactor

public float getLoadFactor()

Get the load factor for this LRUMap.

Returns:

the load factor, as passed to the constructor

See Also:

getInitialCapacity(), getMaximumCapacity()

getMaximumCapacity

public int getMaximumCapacity()

Get the maximum capacity of this LRUMap.

Returns:

the maximum capacity, as passed to the constructor

See Also:

setMaximumCapacity(int), getLoadFactor(), getInitialCapacity()

isEmpty

public boolean isEmpty()

Determine whether this map is empty or not.

Specified by:

isEmpty in interface java.util.Map<K,V>

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

Returns:

true if the map has no mappings, false otherwise

keySet

public java.util.Set<K> keySet()

Return a Set view of the keys in the map. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set does supports element removal, which removes the corresponding mapping from this map; however, the Iterator returned by the set currently does not support element removal. The set does not support the add or addAll operations.

Specified by:

keySet in interface java.util.Map<K,V>

Overrides:

keySet in class java.util.AbstractMap<K,V>

Returns:

the set of keys in this map

put

public V put(K key,
             V value)

Associates the specified value with the specified key in this map. If the key already has a value in this map, the existing value is replaced by the new value, and the old value is replaced. If the key already exists in the map, it is moved to the end of the key insertion order list.

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

Parameters:

key - the key with which the specified value is to be associated

value - the value to associate with the specified key

Returns:

the previous value associated with the key, or null if (a) there was no previous value, or (b) the previous value was a null

putAll

public void putAll(java.util.Map<? extends K,? extends V> map)

Copies all of the mappings from a specified map to this one. These mappings replace any mappings that this map had for any of the keys.

Specified by:

putAll in interface java.util.Map<K,V>

Overrides:

putAll in class java.util.AbstractMap<K,V>

Parameters:

map - the map whose mappings are to be copied

remove

public V remove(java.lang.Object key)

Removes the mapping for a key, if there is one.

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

Parameters:

key - the key to remove

Returns:

the previous value associated with the key, or null if (a) there was no previous value, or (b) the previous value was a null

setMaximumCapacity

public int setMaximumCapacity(int newCapacity)

Set or change the maximum capacity of this LRUMap. If the maximum capacity is reduced to less than the map's current size, then the map is reduced in size by discarding the oldest entries.

Parameters:

newCapacity - the new maximum capacity

Returns:

the old maximum capacity

See Also:

getMaximumCapacity()

size

public int size()

Get the number of entries in the map. Note that this value can temporarily exceed the maximum capacity of the map. See the class documentation for details.

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

Returns:

the number of entries in the map

values

public java.util.Collection<V> values()

Returns a collection view of the values contained in this map. The returned collection is a "thin" view of the values contained in this map. The collection contains proxies for the actual disk-resident values; the values themselves are not loaded until a Collection method such as contains() is called.

The collection is backed by the map, so changes to the map are reflected in the set. If the map is modified while an iteration over the set is in progress, the results of the iteration are undefined.

The set does not support any of the add() methods.

Warning:: The toArray() methods can be dangerous, since they will attempt to load every value from the data file into an in-memory array.

Specified by:

values in interface java.util.Map<K,V>

Overrides:

values in class java.util.AbstractMap<K,V>

Returns:

a collection view of the values contained in this map.

See Also:

keySet(), values()

clone

protected java.lang.Object clone()
                          throws java.lang.CloneNotSupportedException

Returns a shallow copy of this instance. The keys and values themselves are not cloned.

Overrides:

clone in class java.util.AbstractMap<K,V>

Returns:

a shallow copy of this map

Throws:

java.lang.CloneNotSupportedException - not cloneable