import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Timer;
import java.util.TimerTask;

/**
 * Cache implementation that allows for setting
 * of a fixed size and an expiry time for contents.
 * 
 * For thread safety reasons, methods that read or
 * change the cache are synchronized around the
 * object's monitor. Given that this is very quick
 * running code, it should not be an issue and avoids
 * the problem of trying to read items being removed
 * from the cache by another thread, etc.
 *
 * Consider this class public domain.
 * 
 * @author Robin Rawson-Tetley
 *
 */
public class RollingExpirableCache {
	
	protected static final long serialVersionUID = 0;
	
	/** 
	 * Send debug messages to stdout?
	 */
	private static final boolean DEBUG = true;
	
	/**
	 * How long to wait between checking the cache for
	 * items that have expired.
	 */
	private final static long REMOVE_INTERVAL = 30000;
	
	/**
	 * The cache store itself.
	 */
	private Hashtable<String, CacheItem> store = null;
	
	/**
	 * A copy of the cache, in sequential order.
	 * This allows us to quickly determine the
	 * oldest item in the cache.
	 */
	private ArrayList<CacheItem> sequential = null;
	
	/**
	 * Time before items expire from the cache
	 * (0 = never expire and remove oldest item to
	 * make way for newest when full). Default = 1 hour 
	 */
	private long expiry = 0;
	
	/**
	 * The number of objects allowed in the cache
	 */
	private int cacheSize = 500;
	
	/**
	 * A name identifying this cache for logging
	 */
	private String name = "RollingExpirableCache";
	
	/**
	 * Create a new cache with a default 1 hour expiry
	 * @param cacheSize The number of entries allowed in the cache
	 */
	public RollingExpirableCache(String name, int cacheSize) {
		this(name, cacheSize, 3600000); 
	}
	
	/**
	 * Create a new cache
	 * @param name A name for the cache
	 * @param cachesize The number of entries allowed in the cache
	 * @param expiry The time (in ms) to retain items in the cache
	 *        - 0 never expires any items
	 */
	public RollingExpirableCache(String name, int cacheSize, long expiry) {
		
		store = new Hashtable<String, CacheItem>(cacheSize);
		sequential = new ArrayList<CacheItem>(cacheSize);
		this.expiry = expiry;
		this.cacheSize = cacheSize;
		this.name = name;
		
		// Start a thread to reap expired items from the cache
		// if we're using expires
		if (expiry != 0) {
			Timer t = new Timer();
			TimerTask removeTask = new TimerTask() {
				public void run() {
					removeExpired();
				}
			};
			t.schedule(removeTask, REMOVE_INTERVAL, REMOVE_INTERVAL);
		}
	}
	
	/** 
	 * Generates a composite key for a cache item 
	 * from an array of objects. This is helpful for
	 * methods using the cache as there may be quite
	 * a few parameters.
	 * 
	 * @param items
	 * @return
	 */
	public String generateCacheKey(Object[] items) {
		StringBuffer k = new StringBuffer();
		for (int i = 0; i < items.length; i++)
			k.append(items[i].toString() + "_");
		return k.toString();
	}
	
	
	public synchronized Object get(String key) {
		
		// Get the object from the cache
		CacheItem c = store.get(key);
		if (c == null) {
			if (DEBUG) log("MISS: " + key);
			return null;
		}
		
		// Has it expired? If so, remove it from the
		// cache
		if (expiry != 0 && c.getExpiresAt() < System.currentTimeMillis()) {
			store.remove(key);
			sequential.remove(c);
			c.dispose();
			c = null;
			if (DEBUG) log("EXPIRED: " + key);
			return null;
		}
		
		if (DEBUG) log("HIT: " + key);
		return c.getObject();
	}

	public synchronized Object put(String key, Object value) {
		
		// Is the cache full? Remove oldest item if it is.
		if (sequential.size() >= cacheSize) {
			store.remove(sequential.get(0).getKey());
			sequential.get(0).dispose();
			sequential.remove(0);
			if (DEBUG) log("REMOVE OLDEST: " + key);
		}
		
		// Add the new item
		CacheItem c = new CacheItem(key, 
			System.currentTimeMillis() + expiry, value);
		store.put(c.getKey(), c);
		sequential.add(c);
		if (DEBUG) log("ADD: " + key);
		
		return value;
	}
	
	public void log(String m) {
		if (!DEBUG) return;
		System.out.println("[RollingExpirableCache:" + this.name + ":size=" + size() + "] " + m);
	}
	
	public synchronized int size() {
		return sequential.size();
	}
	
	public synchronized void removeExpired() {
		
		ArrayList<String> keys = new ArrayList<String>();
		ArrayList<Integer> indexes = new ArrayList<Integer>();
		
		// Do nothing if cache is empty
		if (sequential.size() == 0) return;
		
		// Build list of keys/idxs for removal
		for (int i = sequential.size()-1; i >= 0; i--) {
			CacheItem c = (CacheItem) sequential.get(i);
			if (c.getExpiresAt() <= System.currentTimeMillis()) {
				indexes.add(new Integer(i));
				keys.add(c.getKey());
			}
		}
		// Do the removal
		for (int i = 0; i < indexes.size(); i++) {
			sequential.get(indexes.get(i).intValue()).dispose();
			sequential.remove(indexes.get(i).intValue());
			store.remove(keys.get(i));
			if (DEBUG) log("TIMED EXPIRED: " + keys.get(i));
		}
	}
}

class CacheItem {
	
	private String key = null;
	private long expiresAt = 0;
	private Object object = null;
	
	public CacheItem(String key, long expiresAt, Object object) {
		this.key = key;
		this.expiresAt = expiresAt;
		this.object = object;
	}
	
	public void dispose() {
		key = null;
		object = null;
	}

	public long getExpiresAt() {
		return expiresAt;
	}

	public void setExpiresAt(long expiresAt) {
		this.expiresAt = expiresAt;
	}

	public String getKey() {
		return key;
	}

	public Object getObject() {
		return object;
	}

	public void setObject(Object object) {
		this.object = object;
	}
	
	public int hashCode() {
		return object.hashCode();
	}
	
	public boolean equals(Object o) {
		return object.equals(o);
	}
	
}