moveToFront
Class MoveToFrontCache<T>

java.lang.Object
  moveToFront.MoveToFrontCache<T>

Type Parameters:

T - - the type of the element stored in the move to front cache

public class MoveToFrontCache<T>
extends java.lang.Object

MoveToFront cache project, due Monday, Oct 28th, 6pm

Implementation of a move-to-front cache, used in move-to-front encoding, as described in http://en.wikipedia.org/wiki/Move-to-front_transform

The abstraction we use was first described in A Locally Adaptive Data Compression Scheme, although we are using -1 to represent a value that doesn't occur, and they use one more than the last valid index. They also start their index values at 1 rather than 0.

In summary, maintains a set of values, ordered according to when they were last accessed. An index of 0 indicates the most recently accessed value. Supports two operations: findOrAdd and get.

The findOrAdd method either finds a value in the cache (returning the position of the value in the cache), or if not found adds the value to the cache and returns -1. Either way, after the operation, the value is moved to the front of the cache.

The get method returns a value at a particular index, and updates the cache by moving that value to the front of the list.

MoveToFrontCache

public MoveToFrontCache()

Construct an empty move to front cache

decodeUsingMTF

public static <T> java.util.List<T> decodeUsingMTF(java.util.List<java.lang.Integer> encoding,
                                                   java.util.List<T> uniqueValues)

Decode a list of using a MTF cache. The encoding and uniqueValue lists are as generated by the encode method.

Parameters:

encoding - a list of the integer values encoding the positions of the values in the cache

uniqueValues - a list of the unique values that have been encoded and need to be put into the resulting list

Returns:

the decoded list of values

encodeUsingMTF

public static <T> void encodeUsingMTF(java.util.List<T> lst,
                                      java.util.List<java.lang.Integer> encoding,
                                      java.util.List<T> uniqueValues)

Encode a list of using a MTF cache. The list is encoded as follows. For each element, if this is the first time that element has been seen, add the element to the end of the uniqueValues list, add -1 to the end of the encoding list, and insert the value at the front of the moveToFront cache. If the element has been seen previously, add the index (0 for front) of the element in the cache to the end of the encoding list, and move the element to the front of the cache.

Type Parameters:

T - the type of the cache elements

Parameters:

lst - the list to be encoded; elements cannot be null, list must not be modified

encoding - initially empty, stores the integer values of the encoding

uniqueValues - initially empty, stores the unique values seen in the list, the order seen

findOrAdd

public int findOrAdd(T t)

Determine the position of t in the cache and move t to the front of the list. If not found, insert t at the front of the list and return -1. If found, move t to the front of the list and return the position of t in the original list (0 if it had been at the front of the list)

Parameters:

t - the value to find in or add to the cache

Returns:

the position where the value was found, or -1 if not found

Throws:

java.lang.NullPointerException - if t is null; Cache cannot contain null values;

get

public T get(int i)

Return the value at position i in the cache, and alter the cache by moving that element to the front of the cache.

Parameters:

i - the position of the element to be returned

Returns:

the value that was at position i when the method was called

Throws:

java.lang.IndexOutOfBoundsException - if index < 0 or >= number of elements in cache

Web Accessibility