import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Simplest LRU (Least Recently Used) cache based on ConcurrentHashMap
 * LFU (Least Frequently Used) can be very similar to this too.
 * Just a sample; see discussion at {@link http://issues.apache.org/jira/browse/SOLR-665}
 * 
 * @author Fuad Efendi (fuad@efendi.ca)
 * 
 * @param <K>
 * @param <V>
 */

public class SimplestConcurrentLRUCache<K, V> {

	protected ConcurrentHashMap<K, ValueWrapper<V>> map;
	protected int maxEntries;

	public SimplestConcurrentLRUCache(int maxEntries) {
		map = new ConcurrentHashMap<K, ValueWrapper<V>>();
		this.maxEntries = maxEntries;
	}

	public V put(K key, V value) {
		ValueWrapper<V> wrapper = map.put(key, new ValueWrapper<V>(value));
		checkRemove();
		return value;
	}

	void checkRemove() {
		if (map.size() <= maxEntries)
			return;
		Map.Entry<K, ValueWrapper<V>> eldestEntry = null;
		
		// Many people say this loop is bottleneck.
		// However, in LinkedHaspMap the same 'bottleneck' happens: evenly distributed several get() calls...
		// And even more: we are forced to synchronize get() for LinkedHashMap...
		// Here we do it in a single place, and it is unsynchronized. Could be improved:
		for (Map.Entry<K, ValueWrapper<V>> entry : map.entrySet()) {
			long popularity = entry.getValue().popularity;
			if (eldestEntry == null || eldestEntry.getValue().popularity > popularity) {
				eldestEntry = entry;
			}
		}
		
		map.remove(eldestEntry.getKey(), eldestEntry.getValue());
	}

	public V get(Object key) {
		ValueWrapper<V> wrapper = map.get(key);
		return wrapper == null ? null : wrapper.getValue();
	}

	public final static class ValueWrapper<V> {
		static volatile long popularityCounter;
		volatile long popularity;
		V value;

		ValueWrapper(V value) {
			this.value = value;
			popularity = popularityCounter++;
		}

		public boolean equals(Object o) {
			if (!(o instanceof ValueWrapper)) {
				return false;
			}
			return (value == null ? ((ValueWrapper) o).value == null : value.equals(((ValueWrapper) o).value));
		}

		public int hashCode() {
			return value.hashCode();
		}

		public V getValue() {
			popularity = popularityCounter++;
			return value;
		}

	}

}