package treecms.tree.util;

import java.io.IOException;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

public class CopyOnWriteTreeMap<K extends Comparable<K>,V>
{
	private volatile TreeNode<K,V> m_read;
	private volatile TreeNode<K,V> m_write;
	
	private final Object m_writeLock;
	public static void main(String _args[]) throws InterruptedException, IOException
	{
		System.in.read();
		
		final CopyOnWriteTreeMap<String,String> map = new CopyOnWriteTreeMap<String,String>();
		//final Map<String,String> map = Collections.synchronizedMap(new TreeMap<String,String>());
		final LinkedList<String> keys = new LinkedList<String>();
		
		Random r = new Random();
		for(int i = 0;i < 10000;i ++){
			String str = Long.toHexString(r.nextLong());
			keys.add(str);
		}
		
		ExecutorService service = Executors.newFixedThreadPool(5);
		
		Callable<Object> writer = new Callable<Object>(){
			@Override
			public Object call() throws Exception
			{
				long mill = System.currentTimeMillis();
				for(String str : keys){
					map.put(str,str);
				}
				System.out.println("Writer :"+ (System.currentTimeMillis() - mill));
				return null;
			}
		};
		
		Callable<Object> reader = new Callable<Object>(){
			@Override
			public Object call() throws Exception
			{
				long mill = System.currentTimeMillis();
				for(String str : keys){
					map.get(str);
				}
				System.out.println("Reader :"+ (System.currentTimeMillis() - mill));
				
				return null;
			}
		};
		
		service.submit(reader);
		service.submit(writer);
		service.submit(writer);
		service.submit(writer);
		service.submit(writer);
		service.submit(writer);
		
		service.shutdown();
		service.awaitTermination(Long.MAX_VALUE,TimeUnit.DAYS);
		
		System.in.read();
	}
	
	public CopyOnWriteTreeMap()
	{
		m_read = m_write = null;
		m_writeLock = new Object();
	}
	
	public V get(K _key)
	{
		if(m_read == null){
			return null;
		}
		
		TreeNode<K,V> tn = m_read;
		
		while(tn != null){
			K key = tn.key();
			int result = key.compareTo(_key);
			if(result == 0){
				//find
				return tn.value();
			}else if(result > 0){
				//go right
				TreeNode<K,V> r = tn.getRight();
				tn = r;
			}else{
				//go left
				TreeNode<K,V> l = tn.getLeft();
				tn = l;
			}
		}
		
		return null;
	}
	
	public void put(K _key,V _value) throws InterruptedException
	{
		TreeNode<K,V> cur;
		synchronized(m_writeLock){
			if(m_write == null){
				m_write = new TreeNode<K,V>(_key,_value);
				m_write.unlock();
				m_read = m_write;
				return;
			}
		
			m_write = m_write.copy();
			cur = m_write;
		}
		
		while(true){
			K key = cur.key(); 
			int result = key.compareTo(_key);
			
			if(result > 0){
				TreeNode<K,V> r = cur.getRight();
				if(r == null){
					r = new TreeNode<K,V>(_key,_value);
					cur.setRight(r);
					r.unlock();
					cur.unlock();
					break;
				}
				TreeNode<K,V> cp = r.copy();
				cur.setRight(cp);
				cur.unlock();
				cur = cp;
				
			}else if(result < 0){
				TreeNode<K,V> l = cur.getLeft();
				if(l == null){
					l = new TreeNode<K,V>(_key,_value);
					cur.setLeft(l);
					l.unlock();
					cur.unlock();
					break;
				}
				TreeNode<K,V> cp = l.copy();
				cur.setLeft(cp);
				cur.unlock();
				cur = cp;
			}else{
				cur.setValue(_value);
				cur.unlock();
				m_read = m_write;
				return;
			}
		}
		
		m_read = m_write;
	}
	
	private static class TreeNode<K,V>
	{
		TreeNode<K,V> m_left;
		TreeNode<K,V> m_right;
		
		private K m_key;
		private V m_value;
		private volatile boolean m_flag;
		private final CountDownLatch m_latch;
		
		public TreeNode(K _key,V _value)
		{
			this(_key,_value,null,null);
		}
		
		private TreeNode(K _key,V _value,TreeNode<K,V> _left,TreeNode<K,V> _right)
		{
			m_key = _key;
			m_value = _value;
			m_left = _left;
			m_right = _right;
			m_latch = new CountDownLatch(1);
			m_flag = true;
		}
		
		public K key()
		{
			return m_key;
		}
		
		public V value()
		{
			return m_value;
		}
		
		public void setValue(V _value)
		{
			m_value = _value;
		}
		
		public void setKey(K _key)
		{
			m_key = _key;
		}
	
		public void setLeft(TreeNode<K,V> _left)
		{
			m_left = _left;
		}
		
		public void setRight(TreeNode<K,V> _right)
		{
			m_right = _right;
		}
		
		public TreeNode<K,V> getLeft()
		{
			return m_left;
		}
		
		public TreeNode<K,V> getRight()
		{
			return m_right;
		}
		
		public void unlock() throws InterruptedException
		{
			m_flag = false;
			m_latch.countDown();
		}
		
		public TreeNode<K,V> copy() throws InterruptedException
		{
			if(m_flag){
				m_latch.await();
			}
			return new TreeNode<K,V>(m_key,m_value,m_left,m_right);
		}
	}
}