package tree;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;
import java.util.Set;

public class MonoTree
{
	private MonoNode m_root;
	
	public MonoTree()
	{
		m_root = new MonoNode(new NodeID(),this);
	}
	
	public synchronized Node editTree(MonoNode _target,NodeData _newData)
	{
		LinkedList<MonoNode> path = findPath(m_root,_target,_newData);
		if(path != null){
			MonoNode newRoot = path.peekFirst();
			m_root = newRoot;
			
			return path.peekLast();
		}
		
		return null;
	}
	
	private LinkedList<MonoNode> findPath(MonoNode _parent,MonoNode _target,NodeData _newData)
	{
		if(_parent == _target){
			//find.
			LinkedList<MonoNode> path = new LinkedList<MonoNode>();
			MonoNode clone = cloneNode(_target,_newData);
			path.addFirst(clone);
			return path;
		}
		
		for(Node node : _parent.m_children){
			LinkedList<MonoNode> path = findPath((MonoNode)node,_target,_newData);
			if(path != null){
				MonoNode clone = cloneNode(_parent,null);
				clone.m_children.remove(node);
				clone.m_children.add(path.getFirst());
				path.addFirst(clone);
				return path;
			}
		}
		
		return null;
	}
	
	private MonoNode cloneNode(MonoNode _target,NodeData _data)
	{
		MonoNode clone = new MonoNode(new NodeID(),this);
		
		if(_data != null){
			clone.m_children.addAll(_data.children);
			clone.m_str = _data.str;
		}else{
			clone.m_children.addAll(_target.getChildren());
			clone.m_str = _target.get();
		}
		
		return clone;
	}
	
	private NodeData packData(MonoNode _target)
	{
		NodeData data = new NodeData();
		data.str = _target.get();
		data.children.addAll(_target.m_children);
		return data;
	}
	
	public Node addChild(MonoNode _target,Node _child)
	{
		NodeData data = packData(_target);
		data.children.add(_child);
		return editTree(_target,data);
	}
	
	public Node addChildren(MonoNode _target,Set<Node> _children)
	{
		NodeData data = packData(_target);
		data.children.addAll(_children);
		return editTree(_target,data);
	}
	
	public Node set(MonoNode _target,String _str)
	{
		NodeData data = packData(_target);
		data.str = _str;
		return editTree(_target,data);
	}
	
	class NodeID
	{
		String m_uuid;
		Long m_version;
		Random m_rand;
		
		public NodeID()
		{
			m_rand = new Random();
			m_uuid = Long.toHexString(m_rand.nextLong());
			m_version = m_rand.nextLong();
		}
		
		public String toString()
		{
			return m_uuid + "@" + m_version.toString();
		}
	}
	
	class NodeData
	{
		String str;
		Set<Node> children;
		
		public NodeData()
		{
			str = "";
			children = new HashSet<Node>();
		}
	}
}