lru

package main.java;
import java.time.LocalTime;
import java.time.temporal.ChronoUnit;
import java.util.HashMap;
import java.util.UUID;


public class LruCache<T extends Object> {
	private HashMap<UUID, LinkedNode<T>> hashMap;
	private LinkedPointerList q;
	Object qLock = new Object();
	private int capacity = 10000000;	// default to 10 mil
	
	public LruCache(int capacity) {
		this.capacity = capacity;
		init();
	}
	
	public LruCache() {
		init();
	}
	
	private void init() {
		hashMap = new HashMap<UUID, LinkedNode<T>>();
		q = new LinkedPointerList();
		q.capacity = this.capacity;
	}
	
	/**
	 * Return the element matching id if in the cache, put in head and update timestamp.
	 * If it isn't in the cache, return null.
	 * @param id
	 * @return The element, if found in the cache, null otherwise.
	 */
	public T get(UUID id) {
		LinkedNode<T> node = hashMap.get(id);
		
		// if it's in the cache
		if (node != null) {
			
			// if ttl expired
			long diff = ChronoUnit.MILLIS.between(node.element.ts, LocalTime.now());
			if (diff > node.element.ttl) {
				synchronized(qLock) {
					hashMap.remove(id);
					q.remove(node);
					return null;
				}
			}
			
			// ttl is fine and we found it, so update timestamp, put in the head and return it.
			T data = node.element.data;
			synchronized(qLock) {
				q.updateHead(node);
				return data;
			}
		}
		
		// otherwise return null
		return null;
	}
	
	public void set(UUID id, long ttl, T data) {
		CacheElement<T> ce = new CacheElement<T>(id, LocalTime.now(), ttl, data);
		if (this.q.size + 1 > this.capacity) {
			
			// if there's exactly one element, just update head/tail and map
			if (q.size == 1) {
				synchronized(qLock) {
					LinkedNode<T> newNode = new LinkedNode<T>();
					newNode.element = ce;
					
					// update map
					hashMap.remove(q.head.element.id);
					hashMap.put(id, newNode);
					
					// update head/tail
					q.head = newNode;
					q.tail = newNode;
				}
				return;
			}
			
			// size > 1 but we reached capacity, so remove the tail
			synchronized(qLock) {
				// remove the tail
				LinkedNode<T> tail = q.tail;
				hashMap.remove(tail.element.id);
				tail.prev.next = null;
				q.tail = tail.prev;
				tail = null;
				
				LinkedNode<T> fetchedNode = q.head;
				hashMap.put(id, fetchedNode);
				this.q.size++;
			}
		}

		// we haven't reached capcity, so just add the new element to the head.
		synchronized(qLock) {
			try {
				LinkedNode<T> fetchedNode = q.add(ce);
				hashMap.put(id, fetchedNode);
				this.q.size++;
			} catch (QueueFullException qfe) {
				System.out.println(String.format("this shouldn't happen: {}", qfe.getMessage()));
			}
		}
	}

	class CacheElement<E extends Object> {
		protected UUID id;
		protected LocalTime ts;
		protected long ttl;
		protected E data;
		
		public CacheElement(UUID id, LocalTime ts, long ttl, E data) {
			this.id = id;
			this.ts = ts;
			this.ttl = ttl;
			this.data = data;
		}
	}
	
	class LinkedPointerList {
		protected int capacity = 0;
		protected int size = 0;
		protected LinkedNode<T> head;
		protected LinkedNode<T> tail;
		protected long ttl;
		
		public void updateHead(LinkedNode<T> node) {
			// update timestamp
			node.element.ts = LocalTime.now();
			
			// remove from current position and connect nodes on either side
			if (node.prev != null && node.next != null) {
				node.prev.next = node.next;
				node.next.prev = node.prev;
			}
			
			// update head
			this.head.prev = node;
			node.next = head;
			this.head = node;
		}

		public LinkedNode<T> add(CacheElement<T> ce) throws QueueFullException {
			LinkedNode<T> newNode = new LinkedNode<T>();
			newNode.element = ce;
			
			// if empty, set head and tail to element
			if (this.size == 0) {
				this.head = newNode;
				this.tail = newNode;
				return newNode;
			}
			
			// reached capacity already?
			if (size + 1 >= capacity) {
				throw new QueueFullException("hit capacity");
			}
			
			this.size++;
			
			// update head
			this.head.prev = newNode;
			newNode.next = head;
			this.head = newNode;
			
			return newNode;
		}
		
		public void remove(LinkedNode<T> node) {
			if (node.prev != null) {
				node.prev.next = node.next;
			}
			if (node.next != null) {
				node.next.prev = node.prev;
			}
			node = null;
		}
	}
	
	class LinkedNode<E extends Object> {
		protected LinkedNode<E> prev;
		protected LinkedNode<E> next;
		protected CacheElement<E> element;
	}
}

class QueueFullException extends Exception {
	public QueueFullException(String msg) {
		super(msg);
	}
}

lru test

package test.java;

import static org.junit.Assert.*;

import java.util.UUID;

import main.java.LruCache;

import org.junit.Test;

public class LruCacheTest {
	
	@Test
	public void test_lrucache_add_get() {
		LruCache<Integer> cache = new LruCache<Integer>();
		UUID id = UUID.randomUUID();
		int data = 3;
		
		// insert and get
		cache.set(id, 3000, data);
		int returned = cache.get(id);
		assertTrue(returned == 3);
		
		// insert and get
		cache.set(id, 3000, data);
		returned = cache.get(id);
		assertTrue(returned == 3);
	}
	
	@Test
	public void test_remove_from_empty() {
		LruCache<Integer> cache = new LruCache<Integer>();
		
		// get from empty cache
		Integer returned = cache.get(UUID.randomUUID());
		assertNull(returned);
	}
	
	@Test
	public void test_get_expired_entry() {
		LruCache<Integer> cache = new LruCache<Integer>();
		UUID id = UUID.randomUUID();
		int data = 3;
		
		// insert and get
		cache.set(id, 1000, data);
		
		// sleep for 1 ms longer than ttl
		try {
			Thread.sleep(1001);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		
		// returned value should be null due to expiry
		Integer returned = cache.get(id);
		assertNull(returned);
	}
	
	@Test
	public void test_capacity_met() {
		LruCache<Integer> cache = new LruCache<Integer>(1);
		UUID id1 = UUID.randomUUID();
		UUID id2 = UUID.randomUUID();
		int data1 = 3;
		int data2 = 4;
		
		// insert and expect to get id1
		cache.set(id1, 30000, data1);
		Integer returned = cache.get(id1);
		assertTrue(returned == 3);
		
		// insert id2 and should be able to get it back.
		cache.set(id2, 30000, data2);
		returned = cache.get(id2);
		assertTrue(returned == 4);
		
		// id1 should have been replaced with id2 since capacity reached.
		// and should no longer be available.
		returned = cache.get(id1);
		assertNull(returned);
	}
}