# HG changeset patch # User shoshi # Date 1297843611 -32400 # Node ID bdde898e8ef901fbfadec9b0c92dfb62d959e9cf # Parent 7ecb9273581db487cd3100897309fa1ee46a9a15 add Forest diff -r 7ecb9273581d -r bdde898e8ef9 src/treecms/api/Forest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/treecms/api/Forest.java Wed Feb 16 17:06:51 2011 +0900 @@ -0,0 +1,7 @@ +package treecms.api; + +public interface Forest +{ + Node get(NodeID _id); + Tree tree(Node _newRoot); +} diff -r 7ecb9273581d -r bdde898e8ef9 src/treecms/api/Node.java --- a/src/treecms/api/Node.java Wed Feb 16 14:27:35 2011 +0900 +++ b/src/treecms/api/Node.java Wed Feb 16 17:06:51 2011 +0900 @@ -1,23 +1,8 @@ package treecms.api; -import java.util.Map; -import java.util.Set; - public interface Node extends Iterable { public NodeID getID(); - public Node createNode(); - - public byte[] getAttribute(String _attr); - public Set getAttributeKeys(); - public Map getAttributeMap(); - public Set getChildren(); - public boolean isChild(Node _child); - - public Node addChild(Node _child); - public Node removeChild(Node _child); - public Node setAttributeMap(Map _map); - public Node addChildren(Set _child); - public Node clearChildren(); - public Node setAttribute(String _attr,byte[] _value); + public NodeData getData(); + public NodeData newData(); } \ No newline at end of file diff -r 7ecb9273581d -r bdde898e8ef9 src/treecms/api/NodeID.java --- a/src/treecms/api/NodeID.java Wed Feb 16 14:27:35 2011 +0900 +++ b/src/treecms/api/NodeID.java Wed Feb 16 17:06:51 2011 +0900 @@ -9,5 +9,5 @@ public String toString(); public boolean isFamily(NodeID _id); - public boolean equals(NodeID _id); + public boolean equals(Object _id); } diff -r 7ecb9273581d -r bdde898e8ef9 src/treecms/api/Tree.java --- a/src/treecms/api/Tree.java Wed Feb 16 14:27:35 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ -package treecms.api; - -public interface Tree -{ - Node useContents(); -} diff -r 7ecb9273581d -r bdde898e8ef9 src/treecms/tree/id/RandomNodeID.java --- a/src/treecms/tree/id/RandomNodeID.java Wed Feb 16 14:27:35 2011 +0900 +++ b/src/treecms/tree/id/RandomNodeID.java Wed Feb 16 17:06:51 2011 +0900 @@ -23,11 +23,17 @@ return false; } - public boolean equals(NodeID _id) + public boolean equals(Object _id) { - if(isFamily(_id) && getVersion().equals(_id.getVersion())){ - return true; + try{ + RandomNodeID target = (RandomNodeID)_id; + if(isFamily(target) && getVersion().equals(target.getVersion())){ + return true; + } + return false; + }catch(Exception _e){ + _e.printStackTrace(); + return false; } - return false; } } diff -r 7ecb9273581d -r bdde898e8ef9 src/treecms/tree/memory/OnMemoryNode.java --- a/src/treecms/tree/memory/OnMemoryNode.java Wed Feb 16 14:27:35 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,166 +0,0 @@ -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 m_children; - HashMap m_attrs; - - public OnMemoryNode(NodeID _id,OnMemoryTree _tree) - { - m_id = _id; - m_tree = _tree; - m_children = new HashSet(); - m_attrs = new HashMap(); - } - - @Override - public Node createNode() - { - OnMemoryNode child = m_tree.createNode(null); - return child; - } - - @Override - public NodeID getID() - { - return m_id; - } - - @Override - public Iterator 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 _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 _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 getAttributeKeys() - { - return m_attrs.keySet(); - } - - @Override - public Map getAttributeMap() - { - return Collections.unmodifiableMap(m_attrs); - } - - @Override - public Set 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 7ecb9273581d -r bdde898e8ef9 src/treecms/tree/memory/OnMemoryTree.java --- a/src/treecms/tree/memory/OnMemoryTree.java Wed Feb 16 14:27:35 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,177 +0,0 @@ -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 path = findAndClone(m_root,_target,_newData); - - if(path == null){ - return null; - } - - //replace. - m_root = path.peekFirst(); - return path.peekLast(); - } - - public LinkedList findAndClone(OnMemoryNode _parent,OnMemoryNode _target,NodeData _newData) - { - if(_parent.getID().isFamily(_target.getID())){ - //find. - OnMemoryNode clone = cloneNode(_target,_newData); - LinkedList path = new LinkedList(); - path.add(clone); - return path; - } - - for(Node child : _parent.getChildren()){ - LinkedList 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 m_children; - Map m_attrs; - - public NodeData() - { - m_tree = null; - m_children = new HashSet(); - m_attrs = new HashMap(); - } - } - - 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 7ecb9273581d -r bdde898e8ef9 src/treecms/tree/memory/OnMemoryTreeEditor.java --- a/src/treecms/tree/memory/OnMemoryTreeEditor.java Wed Feb 16 14:27:35 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -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 7ecb9273581d -r bdde898e8ef9 src/treecms/util/PreOrderTreeWalker.java --- a/src/treecms/util/PreOrderTreeWalker.java Wed Feb 16 14:27:35 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,75 +0,0 @@ -package treecms.util; - -import java.util.Iterator; -import java.util.LinkedList; -import treecms.api.Node; - -public class PreOrderTreeWalker implements Iterable -{ - private Node m_root; - - public PreOrderTreeWalker(Node _root) - { - m_root = _root; - } - - @Override - public Iterator iterator() - { - return new PreOrderRecursiveIterator(m_root); - } - - class PreOrderRecursiveIterator implements Iterator - { - private LinkedList nextList; - - public PreOrderRecursiveIterator(Node _root) - { - nextList = new LinkedList(); - getChildren(_root, nextList); - } - - void getChildren(Node node, LinkedListlist) { - 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 findPath(Node root, Node node) { - LinkedList list = new LinkedList(); - list.addFirst(root); - findPath(root,node,list); - return list; - } - - private boolean findPath(Node root, Node node, LinkedList list) { - if (root==node) return true; - for(Node child : node.getChildren()){ - if (findPath(child,node,list)) { - list.addFirst(child); - return true; - } - } - return false; // backtrack - } -}