changeset 3:5fa718b63cd5

finished treecms.memory basic implementation ( not tested yet. )
author shoshi
date Fri, 18 Feb 2011 02:14:10 +0900
parents 4a5ee88f02cf
children f5ed85be5640
files src/tree/MonoNode.java src/tree/MonoTree.java src/tree/Node.java src/tree/Tree.java src/treecms/api/Tree.java src/treecms/memory/OnMemoryForest.java src/treecms/memory/OnMemoryTree.java src/treecms/memory/OnMemoryTreeEditor.java src/treecms/merger/Merger.java src/treecms/merger/ReplaceMerger.java src/treecms/tree/util/PreorderTreewalker.java
diffstat 11 files changed, 153 insertions(+), 247 deletions(-) [+]
line wrap: on
line diff
--- a/src/tree/MonoNode.java	Wed Feb 16 21:08:32 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,48 +0,0 @@
-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;
-	}
-}
--- a/src/tree/MonoTree.java	Wed Feb 16 21:08:32 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,128 +0,0 @@
-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>();
-		}
-	}
-}
--- a/src/tree/Node.java	Wed Feb 16 21:08:32 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,15 +0,0 @@
-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);
-}
--- a/src/tree/Tree.java	Wed Feb 16 21:08:32 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,6 +0,0 @@
-package tree;
-
-public interface Tree
-{
-	Node getRoot();
-}
--- a/src/treecms/api/Tree.java	Wed Feb 16 21:08:32 2011 +0900
+++ b/src/treecms/api/Tree.java	Fri Feb 18 02:14:10 2011 +0900
@@ -2,6 +2,7 @@
 
 public interface Tree extends Node
 {
+	Node getRoot();
 	Node getNodeByUUID(String _uuid);
 	Node updateTree(Node _target,NodeData _newData);
 }
--- a/src/treecms/memory/OnMemoryForest.java	Wed Feb 16 21:08:32 2011 +0900
+++ b/src/treecms/memory/OnMemoryForest.java	Fri Feb 18 02:14:10 2011 +0900
@@ -1,9 +1,9 @@
 package treecms.memory;
 
 import java.util.Random;
+
 import java.util.UUID;
 import java.util.concurrent.ConcurrentHashMap;
-
 import treecms.api.Forest;
 import treecms.api.Node;
 import treecms.api.NodeID;
@@ -20,10 +20,15 @@
 	
 	public OnMemoryNode createNode(NodeID _id)
 	{
+		OnMemoryNode newNode;
 		if(_id == null){
-			return new OnMemoryNode(this,createID());
+			newNode = new OnMemoryNode(this,createID());
+		}else{
+			newNode = new OnMemoryNode(this,_id);
 		}
-		return new OnMemoryNode(this,_id);
+		m_table.put(newNode.getID(),newNode);
+		
+		return newNode;
 	}
 	
 	NodeID createID()
--- a/src/treecms/memory/OnMemoryTree.java	Wed Feb 16 21:08:32 2011 +0900
+++ b/src/treecms/memory/OnMemoryTree.java	Fri Feb 18 02:14:10 2011 +0900
@@ -1,21 +1,30 @@
 package treecms.memory;
 
 import java.util.LinkedList;
+import java.util.concurrent.ConcurrentHashMap;
+
 import treecms.api.Forest;
 import treecms.api.Node;
 import treecms.api.NodeData;
 import treecms.api.NodeID;
 import treecms.api.Tree;
+import treecms.tree.util.PreorderTreewalker;
 
 public class OnMemoryTree implements Tree
 {
 	OnMemoryNode m_root;
 	OnMemoryForest m_forest;
+	ConcurrentHashMap<String,OnMemoryNode> m_table;
 	
 	public OnMemoryTree(OnMemoryNode _newRoot,OnMemoryForest _forest)
 	{
 		m_root = _newRoot;
 		m_forest = _forest;
+		
+		m_table = new ConcurrentHashMap<String,OnMemoryNode>();
+		for(Node elem : new PreorderTreewalker(m_root)){
+			m_table.put(elem.getID().getUUID(),(OnMemoryNode)elem);
+		}
 	}
 	
 	@Override
@@ -45,7 +54,7 @@
 	@Override
 	public Node getNodeByUUID(String _uuid)
 	{
-		return null;
+		return m_table.get(_uuid);
 	}
 
 	@Override
@@ -74,6 +83,8 @@
 			clone.m_data.add(_target.m_data.list());
 			clone.m_data.set(_target.m_data.get());
 		}
+		
+		m_table.put(clone.getID().getUUID(),clone);
 		return clone;
 	}
 	
@@ -101,4 +112,10 @@
 		return null; //not found.
 	}
 
+	@Override
+	public Node getRoot()
+	{
+		return m_root;
+	}
+
 }
--- a/src/treecms/memory/OnMemoryTreeEditor.java	Wed Feb 16 21:08:32 2011 +0900
+++ b/src/treecms/memory/OnMemoryTreeEditor.java	Fri Feb 18 02:14:10 2011 +0900
@@ -1,76 +1,50 @@
 package treecms.memory;
 
-import treecms.api.Forest;
-import treecms.api.Node;
-import treecms.api.NodeData;
-import treecms.api.NodeID;
 import treecms.api.TreeEditor;
+import treecms.merger.Merger;
+import treecms.merger.ReplaceMerger;
 
-public class OnMemoryTreeEditor implements TreeEditor
+public class OnMemoryTreeEditor extends OnMemoryTree implements TreeEditor
 {
-	public OnMemoryTreeEditor(OnMemoryTree _tree)
-	{
-		
-	}
+	OnMemoryTree m_tree;
+	OnMemoryNode m_oldRoot;
 	
-	@Override
-	public Forest getForest()
+	public OnMemoryTreeEditor(OnMemoryForest _forest,OnMemoryTree _tree)
 	{
-		return null;
+		super(_tree.m_root,_forest);
+		m_oldRoot = m_root;
 	}
 	
 	@Override
-	public Node getNodeByUUID(String _uuid)
-	{
-		return null;
-	}
-
-	@Override
-	public Node updateTree(Node _target, NodeData _newData)
-	{
-		return null;
-	}
-
-	@Override
-	public NodeID getID()
-	{
-		return null;
-	}
-
-	@Override
-	public NodeData getData()
-	{
-		return null;
-	}
-
-	@Override
-	public NodeData newData()
-	{
-		return null;
-	}
-
-	@Override
 	public boolean commit(boolean _force)
 	{
+		if(!check() || _force){
+			m_tree.m_root = m_root;
+		}
 		return false;
 	}
 
 	@Override
 	public boolean pull()
 	{
-		return false;
+		m_root = m_tree.m_root;
+		return true;
 	}
 
 	@Override
 	public boolean check()
 	{
-		return false;
+		if(m_tree.m_root.getID().equals(m_oldRoot.getID())){
+			return false;
+		}
+		return true;
 	}
 
 	@Override
 	public void merge()
 	{
+		//call merger
+		Merger merger = new ReplaceMerger();
+		m_root = (OnMemoryNode)merger.merge(m_tree.m_root,m_root);
 	}
-
-
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/merger/Merger.java	Fri Feb 18 02:14:10 2011 +0900
@@ -0,0 +1,8 @@
+package treecms.merger;
+
+import treecms.api.Node;
+
+public interface Merger
+{
+	public Node merge(Node _from,Node _to);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/merger/ReplaceMerger.java	Fri Feb 18 02:14:10 2011 +0900
@@ -0,0 +1,11 @@
+package treecms.merger;
+
+import treecms.api.Node;
+
+public class ReplaceMerger implements Merger
+{
+	public Node merge(Node _from,Node _to)
+	{
+		return _from;
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/util/PreorderTreewalker.java	Fri Feb 18 02:14:10 2011 +0900
@@ -0,0 +1,87 @@
+package treecms.tree.util;
+
+import java.util.Iterator;
+import java.util.Stack;
+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 IteratorImpl();
+	}
+	
+	private class IteratorImpl implements Iterator<Node>
+	{
+		private Stack<Pair<Node,Iterator<Node>>> m_depth;
+		private Node m_next;
+		
+		public IteratorImpl()
+		{
+			m_depth = new Stack<Pair<Node,Iterator<Node>>>();
+			m_next = m_root;
+			m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ!
+		}
+
+		@Override
+		public boolean hasNext()
+		{
+			return (m_next != null) ? true : false;
+		}
+
+		@Override
+		public Node next()
+		{
+			Node next = m_next;
+			
+			//forward.
+			Pair<Node,Iterator<Node>> context = m_depth.peek();
+			Iterator<Node> itr = context.m_right;
+			if(itr.hasNext()){
+				m_next = itr.next();
+				m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ!
+			}else{
+				m_depth.pop();
+				while(!m_depth.isEmpty()){
+					Pair<Node,Iterator<Node>> back = m_depth.peek();
+					if(back.m_right.hasNext()){
+						m_next = back.m_right.next();
+						break;
+					}
+					m_depth.pop();
+				}
+				m_next = null;
+			}
+			
+			return next;
+		}
+
+		@Override
+		public void remove()
+		{
+			//not supported.
+		}
+	}
+	
+	private class Pair<L,R>
+	{
+		@SuppressWarnings("unused")
+		public L m_left;
+		public R m_right;
+		
+		public Pair(L _left,R _right)
+		{
+			m_left = _left;
+			m_right = _right;
+		}
+	}
+}