org.rakeshv.utils
Class SimpleLRU<T>

java.lang.Object
  org.rakeshv.utils.SimpleLRU<T>

All Implemented Interfaces:

DataStructure<T>

public class SimpleLRU<T>
extends java.lang.Object
implements DataStructure<T>

A Least Recently Used implementation using an array and a Map.

Version:

$Id: SimpleLRU.java,v 1.5 2006/03/11 16:32:01 rakesh Exp $

Author:

Rakesh Vidyadharan 2002 March 2

See Also:

SharedObject,

Copyright 2002-2006 Rakesh Vidyadharan

Field Summary

private boolean	filled A flag to indicate that the lru has been filled.
private int	index A variable that holds the index into the lru at which a new instance is to be added.
private T[]	lru An array that is used to implement a LRU.
private java.util.HashMap<T,java.lang.Integer>	map A Map that is used to map the index (value) to the Object (key) that is being stored in the LRU.

Fields inherited from interface org.rakeshv.utils.DataStructure

DYNAMIC, FIFO, FIFO_IMPLEMENTATION, LRU, LRU_IMPLEMENTATION

Constructor Summary

SimpleLRU(int size)
Construct a new LRU of the specified size.

Method Summary

void	add(T object) Add the specified object to lru.
void	clear() Removes all the objects from the lru and the map.
T	get() Return the current Object in the lru.
T	remove() Removes the current Object designated for removal (located at index 0) from the lru and the associated mapping from map.
boolean	remove(T object) Removes the specified object from the lru.
int	size() Returns the size of the lru.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

lru

private T[] lru

An array that is used to implement a LRU.

map

private java.util.HashMap<T,java.lang.Integer> map

A Map that is used to map the index (value) to the Object (key) that is being stored in the LRU. It also serves as a fast means for accessing objects that are stored in the LRU.

index

private int index

A variable that holds the index into the lru at which a new instance is to be added. The index rolls around from the end of the lru to the beginning when the lru is full.

filled

private boolean filled

A flag to indicate that the lru has been filled. This will be set only once after the lru has been filled initially.

Constructor Detail

SimpleLRU

public SimpleLRU(int size)

Construct a new LRU of the specified size.

Method Detail

get

public T get()

Return the current Object in the lru. This is the object that will be replaced when the next call to add( Object ) is made.

Specified by:

get in interface DataStructure<T>

Returns:

The Object that is at the index within the lru. This will be null if the lru has not been filled yet.

add

public void add(T object)

Add the specified object to lru. Updates the index after adding the specified object to the next location in the lru. Sets filled to true when the index rolls around to the beginning of the lru for the first time.

Note: This method does not perform any synchronisation, and hence is not thread-safe. Client's must perform their own synchronisation if they so desire.

Specified by:

add in interface DataStructure<T>

Parameters:

object - The object to be added to the lru.

Throws:

java.lang.IllegalArgumentException - If a null value was specified for the object.

remove

public T remove()

Removes the current Object designated for removal (located at index 0) from the lru and the associated mapping from map.

Specified by:

remove in interface DataStructure<T>

Returns:

The Object that was removed.

remove

public boolean remove(T object)

Removes the specified object from the lru. The time to remove the specified object will be directly proportional to the size of the lru.

This operation can be heavy, since it involves reordering the lru. The following conditions apply:

1. Remove the matching object from the lru.
2. Move all succeeding objects in the lru up by one position.
3. Reset the index to point to the end of the lru or to the previous position depending upon whether the lru was filled or not.
4. Matching is performed using the equivalent matching rule (the Object.equals( Object )) operator as is implemented in the Map implementations.

If there are multiple instances of the same object in the lru, only the first matching object is removed.

Note: This method does not perform any synchronisation, and hence is not thread-safe. Client's must perform their own synchronisation if they so desire.

Specified by:

remove in interface DataStructure<T>

Parameters:

object - The object that is to be removed from the lru.

Returns:

Returns true if the specified object was found and removed from the lru.

clear

public void clear()

Removes all the objects from the lru and the map. The most efficient way to do it is to create a new instances of the lru array and the map, and consign the old instances to the garbage collector.

Note: This method does not perform any synchronisation, and hence is not thread-safe. Client's must perform their own synchronisation if they so desire.

Specified by:

clear in interface DataStructure<T>

size

public int size()

Returns the size of the lru. Returns the total size of the lru, if the lru has been filled, else returns the index value.

Specified by:

size in interface DataStructure<T>

Returns:

The size of the lru.