# HG changeset patch
# User shoshi
# Date 1297834055 -32400
# Node ID 7ecb9273581db487cd3100897309fa1ee46a9a15

hg init

diff -r 000000000000 -r 7ecb9273581d src/tree/MonoNode.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/MonoNode.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,48 @@
+package tree;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class MonoNode implements Node
+{
+	String m_str;
+	Set<Node> m_children = new HashSet<Node>();
+	MonoTree m_tree;
+	MonoTree.NodeID m_id;
+	
+	public MonoNode(MonoTree.NodeID _id,MonoTree _tree)
+	{
+		m_id = _id;
+		m_tree = _tree;
+	}
+	
+	@Override
+	public Node addChild(Node child)
+	{
+		return m_tree.addChild(this,child);
+	}
+
+	@Override
+	public Node addChildren(Set<Node> children)
+	{
+		return m_tree.addChildren(this,children);
+	}
+	
+	@Override
+	public Node set(String str)
+	{
+		return m_tree.set(this,str);
+	}
+
+	@Override
+	public String get()
+	{
+		return m_str;
+	}
+
+	@Override
+	public Set<Node> getChildren()
+	{
+		return m_children;
+	}
+}
diff -r 000000000000 -r 7ecb9273581d src/tree/MonoTree.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/MonoTree.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,128 @@
+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>();
+		}
+	}
+}
diff -r 000000000000 -r 7ecb9273581d src/tree/Node.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/Node.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,15 @@
+package tree;
+
+import java.util.Set;
+
+public interface Node
+{
+	//read operation
+	public String get();
+	public Set<Node> getChildren();
+	
+	//write operation
+	public Node set(String _str);
+	public Node addChild(Node _child);
+	public Node addChildren(Set<Node> _children);
+}
diff -r 000000000000 -r 7ecb9273581d src/tree/Tree.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/tree/Tree.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,6 @@
+package tree;
+
+public interface Tree
+{
+	Node getRoot();
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/api/Node.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/Node.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,23 @@
+package treecms.api;
+
+import java.util.Map;
+import java.util.Set;
+
+public interface Node extends Iterable<Node>
+{
+	public NodeID getID();
+	public Node createNode();
+	
+	public byte[] getAttribute(String _attr);
+	public Set<String> getAttributeKeys();
+	public Map<String,byte[]> getAttributeMap();
+	public Set<Node> getChildren();
+	public boolean isChild(Node _child);
+	
+	public Node addChild(Node _child);
+	public Node removeChild(Node _child);
+	public Node setAttributeMap(Map<String,byte[]> _map);
+	public Node addChildren(Set<Node> _child);
+	public Node clearChildren();
+	public Node setAttribute(String _attr,byte[] _value);
+}
\ No newline at end of file
diff -r 000000000000 -r 7ecb9273581d src/treecms/api/NodeID.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/NodeID.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,13 @@
+package treecms.api;
+
+public interface NodeID
+{
+	public NodeID create();
+	public NodeID update();
+	public String getUUID();
+	public String getVersion();
+	public String toString();
+	
+	public boolean isFamily(NodeID _id);
+	public boolean equals(NodeID _id);
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/api/Tree.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/Tree.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,6 @@
+package treecms.api;
+
+public interface Tree
+{
+	Node useContents();
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/api/TreeEditor.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/TreeEditor.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,16 @@
+package treecms.api;
+
+public interface TreeEditor extends Tree
+{
+	//commit local tree to remote tree
+	public boolean commit(boolean _force);
+	
+	//pull updates from remote tree
+	public boolean pull();
+	
+	//check that is remote tree modified.
+	public boolean check();
+	
+	//merge remote tree to local tree
+	public void merge();
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/tree/id/RandomNodeID.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/id/RandomNodeID.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,33 @@
+package treecms.tree.id;
+
+import treecms.api.NodeID;
+
+public abstract class RandomNodeID implements NodeID
+{
+	public abstract NodeID create();
+	public abstract NodeID update();
+	public abstract String getUUID();
+	public abstract String getVersion();
+	
+	@Override
+	public String toString()
+	{
+		return getUUID()+"@"+getVersion();
+	}
+	
+	public boolean isFamily(NodeID _id)
+	{
+		if(_id instanceof RandomNodeID && getUUID().equals(_id.getUUID())){
+			return true;
+		}
+		return false;
+	}
+	
+	public boolean equals(NodeID _id)
+	{
+		if(isFamily(_id) && getVersion().equals(_id.getVersion())){
+			return true;
+		}
+		return false;
+	}
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/tree/memory/OnMemoryNode.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/memory/OnMemoryNode.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,166 @@
+package treecms.tree.memory;
+
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
+import treecms.api.Node;
+import treecms.api.NodeID;
+
+public class OnMemoryNode implements Node
+{
+	NodeID m_id;
+	OnMemoryTree m_tree;
+	
+	HashSet<Node> m_children;
+	HashMap<String,byte[]> m_attrs;
+	
+	public OnMemoryNode(NodeID _id,OnMemoryTree _tree)
+	{
+		m_id = _id;
+		m_tree = _tree;
+		m_children = new HashSet<Node>();
+		m_attrs = new HashMap<String,byte[]>();
+	}
+
+	@Override
+	public Node createNode()
+	{
+		OnMemoryNode child = m_tree.createNode(null);
+		return child;
+	}
+
+	@Override
+	public NodeID getID()
+	{
+		return m_id;
+	}
+
+	@Override
+	public Iterator<Node> iterator()
+	{
+		return Collections.unmodifiableSet(m_children).iterator();
+	}
+
+	@Override
+	public Node addChild(Node _child)
+	{
+		OnMemoryTree.NodeData data = m_tree.extractData(this);
+		data.m_children.add(_child);
+		OnMemoryNode newNode = m_tree.clonetree(this,data);
+		if(newNode == null){
+			m_children.add(_child);
+			return this;
+		}
+		return newNode;
+	}
+
+	@Override
+	public Node addChildren(Set<Node> _children)
+	{
+		OnMemoryTree.NodeData data = m_tree.extractData(this);
+		data.m_children.addAll(_children);
+		OnMemoryNode newNode = m_tree.clonetree(this,data);
+		if(newNode == null){
+			m_children.addAll(_children);
+			return this;
+		}
+		return newNode;
+	}
+
+	@Override
+	public Node clearChildren()
+	{
+		OnMemoryTree.NodeData data = m_tree.extractData(this);
+		data.m_children.clear();
+		OnMemoryNode newNode = m_tree.clonetree(this,data);
+		if(newNode == null){
+			m_children.clear();
+			return this;
+		}
+		return newNode;
+	}
+	
+	@Override
+	public Node removeChild(Node _child)
+	{
+		OnMemoryTree.NodeData data = m_tree.extractData(this);
+		data.m_children.remove(_child);
+		OnMemoryNode newNode = m_tree.clonetree(this,data);
+		if(newNode == null){
+			m_children.remove(_child);
+			return this;
+		}
+		return newNode;
+	}
+	
+	@Override
+	public Node setAttribute(String _attr,byte[] _value)
+	{
+		OnMemoryTree.NodeData data = m_tree.extractData(this);
+		data.m_attrs.put(_attr,_value);
+		OnMemoryNode newNode = m_tree.clonetree(this,data);
+		if(newNode == null){
+			m_attrs.put(_attr,_value);
+			return this;
+		}
+		return newNode;
+	}
+	
+	@Override
+	public Node setAttributeMap(Map<String,byte[]> _map)
+	{
+		OnMemoryTree.NodeData data = m_tree.extractData(this);
+		data.m_attrs.putAll(_map);
+		OnMemoryNode newNode = m_tree.clonetree(this,data);
+		if(newNode == null){
+			m_attrs.putAll(_map);
+			return this;
+		}
+		return newNode;
+	}
+
+	@Override
+	public byte[] getAttribute(String _attr)
+	{
+		return m_attrs.get(_attr);
+	}
+
+	@Override
+	public Set<String> getAttributeKeys()
+	{
+		return m_attrs.keySet();
+	}
+
+	@Override
+	public Map<String, byte[]> getAttributeMap()
+	{
+		return Collections.unmodifiableMap(m_attrs);
+	}
+
+	@Override
+	public Set<Node> getChildren()
+	{
+		return Collections.unmodifiableSet(m_children);
+	}
+	
+	@Override
+	public String toString()
+	{
+		return m_id.toString();
+	}
+
+	@Override
+	public boolean isChild(Node _child)
+	{
+		return m_children.contains(_child);
+	}
+
+	@Override
+	public Node useContents()
+	{
+		return m_tree.useContents();
+	}
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/tree/memory/OnMemoryTree.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/memory/OnMemoryTree.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,177 @@
+package treecms.tree.memory;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Random;
+import java.util.Set;
+import java.util.UUID;
+import treecms.api.Node;
+import treecms.api.NodeID;
+import treecms.api.Tree;
+import treecms.tree.id.RandomNodeID;
+
+public class OnMemoryTree implements Tree
+{
+	public OnMemoryNode m_root;
+	
+	public static void main(String _args[])
+	{
+		OnMemoryTree tree = new OnMemoryTree();
+		
+		Node root = tree.useContents();
+		Node child1 = root.createNode();
+		child1.setAttribute("hogehoge","fugafuga".getBytes());
+		Node newRoot = root.addChild(child1);
+	}
+	
+	public OnMemoryTree()
+	{
+		m_root = createNode(null);
+	}
+	
+	@Override
+	public Node useContents()
+	{
+		return m_root;
+	}
+	
+	public synchronized OnMemoryNode clonetree(OnMemoryNode _target,NodeData _newData)
+	{
+		LinkedList<OnMemoryNode> path  = findAndClone(m_root,_target,_newData);
+		
+		if(path == null){
+			return null;
+		}
+		
+		//replace.
+		m_root = path.peekFirst();
+		return path.peekLast();
+	}
+	
+	public LinkedList<OnMemoryNode> findAndClone(OnMemoryNode _parent,OnMemoryNode _target,NodeData _newData)
+	{
+		if(_parent.getID().isFamily(_target.getID())){
+			//find.
+			OnMemoryNode clone = cloneNode(_target,_newData);
+			LinkedList<OnMemoryNode> path = new LinkedList<OnMemoryNode>();
+			path.add(clone);
+			return path;
+		}
+		
+		for(Node child : _parent.getChildren()){
+			LinkedList<OnMemoryNode> path = findAndClone((OnMemoryNode)child,_target,_newData);
+			if(path != null){
+				OnMemoryNode clone = cloneNode(_parent,null);
+				clone.removeChild(child);
+				clone.addChild(path.peekFirst());
+				path.addFirst(clone);
+				return path;
+			}
+		}
+		
+		return null;
+	}
+	
+	public OnMemoryNode cloneNode(OnMemoryNode _target,NodeData _newData)
+	{
+		OnMemoryNode node = createNode(_target.getID().update());
+		
+		if(_newData != null){
+			node.m_attrs.putAll(_newData.m_attrs);
+			node.m_children.addAll(_newData.m_children);
+			return node;
+		}
+		
+		node.m_attrs.putAll(_target.m_attrs);
+		node.m_children.addAll(_target.m_children);
+		return node;
+	}
+	
+	public NodeData extractData(OnMemoryNode _target)
+	{
+		NodeData data = new NodeData();
+		data.m_attrs.putAll(_target.getAttributeMap());
+		data.m_children.addAll(_target.getChildren());
+		return data;
+	}
+	
+	public OnMemoryNode createNode(NodeID _id)
+	{
+		OnMemoryNode newNode;
+		if(_id != null){
+			newNode = new OnMemoryNode(_id,this);
+		}else{
+			newNode = new OnMemoryNode(createID(),this);
+		}
+		return newNode;
+	}
+	
+	public NodeID createID()
+	{
+		return new RandomNodeIDImpl(null);
+	}
+	
+	class NodeData
+	{
+		Tree m_tree;
+		Set<Node> m_children;
+		Map<String,byte[]> m_attrs;
+		
+		public NodeData()
+		{
+			m_tree = null;
+			m_children = new HashSet<Node>();
+			m_attrs = new HashMap<String,byte[]>();
+		}
+	}
+	
+	class RandomNodeIDImpl extends RandomNodeID
+	{
+		private String m_uuid;
+		private Long m_version;
+		
+		public RandomNodeIDImpl(String _uuid)
+		{
+			if(_uuid != null){
+				m_uuid = _uuid;
+			}else{
+				m_uuid = UUID.randomUUID().toString();
+			}
+			
+			m_version = (new Random()).nextLong();
+		}
+		
+		@Override
+		public NodeID create()
+		{
+			return new RandomNodeIDImpl(null);
+		}
+
+		@Override
+		public String getUUID()
+		{
+			return m_uuid;
+		}
+
+		@Override
+		public String getVersion()
+		{
+			return Long.toHexString(m_version);
+		}
+		
+		@Override
+		public String toString()
+		{
+			return m_uuid + "@" + Long.toHexString(m_version);
+		}
+
+		@Override
+		public NodeID update()
+		{
+			RandomNodeIDImpl newID = new RandomNodeIDImpl(m_uuid);
+			return newID;
+		}
+	}
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/tree/memory/OnMemoryTreeEditor.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/memory/OnMemoryTreeEditor.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,48 @@
+package treecms.tree.memory;
+
+import treecms.api.TreeEditor;
+import treecms.api.Node;
+
+public class OnMemoryTreeEditor extends OnMemoryTree implements TreeEditor
+{
+	
+	public OnMemoryTreeEditor(OnMemoryTree _tree)
+	{
+		
+	}
+	
+	public Node copyNode(Node _node)
+	{
+		return null;
+	}
+
+	@Override
+	public boolean check()
+	{
+		return false;
+	}
+
+	@Override
+	public boolean commit(boolean force)
+	{
+		return false;
+	}
+
+	@Override
+	public void merge()
+	{
+		
+	}
+
+	@Override
+	public boolean pull()
+	{
+		return false;
+	}
+
+	@Override
+	public Node useContents()
+	{
+		return null;
+	}
+}
diff -r 000000000000 -r 7ecb9273581d src/treecms/util/PreOrderTreeWalker.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/util/PreOrderTreeWalker.java	Wed Feb 16 14:27:35 2011 +0900
@@ -0,0 +1,75 @@
+package treecms.util;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import treecms.api.Node;
+
+public class PreOrderTreeWalker implements Iterable<Node>
+{
+	private Node m_root;
+	
+	public PreOrderTreeWalker(Node _root)
+	{
+		m_root = _root;
+	}
+
+	@Override
+	public Iterator<Node> iterator()
+	{
+		return new PreOrderRecursiveIterator(m_root);
+	}
+
+	class PreOrderRecursiveIterator implements Iterator<Node>
+	{
+		private LinkedList<Node> nextList;
+		
+		public PreOrderRecursiveIterator(Node _root)
+		{
+			nextList = new LinkedList<Node>();
+			getChildren(_root, nextList);
+		}
+		
+		void getChildren(Node node, LinkedList<Node>list) {
+			list.add(node);
+			for(Node child : node.getChildren()){
+				getChildren(child,list);
+			}
+		}
+		
+		@Override
+		public boolean hasNext()
+		{
+			return !nextList.isEmpty();
+		}
+
+		@Override
+		public Node next()
+		{
+			return nextList.poll();
+		}
+
+		@Override
+		public void remove()
+		{
+			throw new UnsupportedOperationException("cant remove from itrerator");
+		}
+	}
+	
+	public LinkedList<Node> findPath(Node root, Node node) {
+		LinkedList<Node> list = new LinkedList<Node>();
+		list.addFirst(root);
+		findPath(root,node,list);
+		return list;
+	}
+
+	private boolean findPath(Node root, Node node, LinkedList<Node> list) {
+		if (root==node) return true;
+		for(Node child : node.getChildren()){
+			if (findPath(child,node,list)) {
+				list.addFirst(child);
+				return true;
+			}
+		}
+		return false; // backtrack
+	}
+}