package stdx;

import java.util.*;

class CacheMap<KEY, VAL>{
	class Node implements Comparable<Node>{
		public KEY key;
		public VAL data;
		public int weight;

		public Node(KEY key, VAL data){
			this.key = key;
			this.data = data;
			this.weight = 0;
		}
		@Override
		public int compareTo(Node node){
			return node.weight - weight;
		}
	}

	int maxsz = 10000;
	HashMap<KEY, Node> datamap = new HashMap<KEY, Node>();

	void check(){
		int maxlen = Math.min(datamap.size() / 8, 10000);
		PriorityQueue<Node> queue = new PriorityQueue<Node>();

		Iterator<Node> it = datamap.values().iterator();

		for (int i = 0; i < maxlen; i++) queue.add(it.next());

		while (it.hasNext()){
			Node node = it.next();
			Node head = queue.peek();

			if (node.weight >= head.weight){
				node.weight = 0;
				continue;
			}

			queue.poll();
			queue.add(node);
			head.weight = 0;
		}

		for (int i = 0; i < maxlen; i++) datamap.remove(queue.poll().key);
	}
	public CacheMap(){
	}
	public CacheMap(int maxsz){
		this.maxsz = Math.max(maxsz, 100);
	}
	public int size(){
		synchronized(datamap){
			return datamap.size();
		}
	}
	public void clear(){
		synchronized (datamap){
			datamap.clear();
		}
	}
	public VAL get(KEY key){
		synchronized(datamap){
			Node node = datamap.get(key);

			if (node == null) return null;

			node.weight++;

			return node.data;
		}
	}
	public boolean isEmpty(){
		synchronized(datamap){
			return datamap.isEmpty();
		}
	}
	public void remove(KEY key){
		synchronized(datamap){
			datamap.remove(key);
		}
	}
	public void put(KEY key, VAL data){
		synchronized(datamap){
			Node node = datamap.get(key);

			if (node == null){
				if (datamap.size() >= maxsz) check();

				node = new Node(key, data);

				datamap.put(key, node);
			}
			else{
				node.data = data;
			}
		}
	}
}