Cache

/*******************************************************************************
 * Copyright (c) 2013 Ted Meyer.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * 
 * Contributors:
 *     Ted Meyer - being a generally kickass person
 ******************************************************************************/
package edu.wpi.tmathmeyer.struct.cache;

import java.util.HashMap;

public class Cache<K, V> {
  int maxSize;
	HashMap<K,ListItem<K,V>> map = new HashMap<K, ListItem<K,V>>();
	
	
	ListItem<K,V> newest = new ListItem<K,V>();
	ListItem<K,V> oldest = newest;
	
	public Cache(int maxSize){
		this.maxSize = maxSize;
	}
	
	public void insert(K k, V v){
		ListItem<K,V> kv = new ListItem<K,V>();
		kv.key = k;
		kv.value = v;
		map.put(k, kv);
		newest.child = kv;
		newest = kv;
		
		if (map.size() > this.maxSize){
			ListItem<K,V> condemned = this.oldest;
			this.oldest.child.parent = null;
			this.map.remove(condemned.key);
		}
	}
	
	public void remove(K k){
		ListItem<K,V> con = map.get(k);
		ListItem<K,V> below = con.child;
		ListItem<K,V> above = con.parent;
		below.parent = above;
		above.child = below;
		map.remove(k);
	}
	
	public V get(K k){
		ListItem<K,V> con = map.get(k);
		ListItem<K,V> below = con.child;
		ListItem<K,V> above = con.parent;
		below.parent = above;
		above.child = below;
		con.child = null;
		con.parent = this.newest;
		this.newest = con;
		return this.mostRecent();
	} 
	
	public V mostRecent(){
		return this.newest.value;
	}
	
	public V leastRecent(){
		return oldest.value;
	}
}


class ListItem<K,V> {
	public ListItem<K,V> parent;
	public ListItem<K,V> child;
	public V value;
	public K key;
}