# HG changeset patch # User shoshi # Date 1300112678 -32400 # Node ID 12604eb6b615247f297fac2e3537bd9a3566d1c2 # Parent 87bba22e4fa2625c5b040b516f0da4a63348fe5a added javadoc diff -r 87bba22e4fa2 -r 12604eb6b615 CHANGELOG --- a/CHANGELOG Tue Mar 01 01:29:59 2011 +0900 +++ b/CHANGELOG Mon Mar 14 23:24:38 2011 +0900 @@ -1,5 +1,7 @@ ChangeLog. +2011-03-14 + added javadoc treecms.api 2011-02-28 added test case 2011-02-25 diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/api/Forest.java --- a/src/treecms/api/Forest.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/api/Forest.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,7 +1,36 @@ package treecms.api; +/** + * ForestはNodeの集合で、集合に対するアクセスを提供します．クライアントはNodeIDを用いてNodeの取得や作成を行うことが出来ます． + * @author shoshi + */ public interface Forest { + /** + * NodeIDで示されるNodeを取得します． + * @param _id Nodeを示すNodeID． + * @return NodeIDと一致するNodeがある場合は，Nodeのインスタンスを返し，見つからない場合はnullを返します． + */ Node get(NodeID _id); + + /** + * 同じUUIDを持つNode中で最新のNodeを取得します． + * @param _uuid NodeIDのUUID + * @return UUIDと一致するNodeが見つからない場合はnullを返します． + */ + Node getTip(String _uuid); + + /** + * 新しいNodeを作成します．このメソッドで作成されるNodeは新しいUUIDを持ちます． + * @return 新しいNode + */ Node create(); + + /** + * NodeDataを保持する新しいNodeを作成します．このメソッドで作成されるNodeは新しいUUIDを持ちます． + * このメソッドはNodeDataをNodeに割り当てるとき防御的コピーを行います． + * @param _data 新しいNodeが保持するNodeData + * @return NodeDataを保持した新しいNode + */ + Node create(NodeData _data); } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/api/Node.java --- a/src/treecms/api/Node.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/api/Node.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,8 +1,74 @@ package treecms.api; +import java.util.List; +import java.util.Map; + +/** + * 木構造の基本のデータ単位であるNodeを示します．Nodeは子供のリストとデータのマップを保持します．また，クライアントはノードが保持しているデータをNodeDataとして + * 取得することが出来ます． + * @author shoshi + */ public interface Node { + /** + * Nodeに対応するNodeIDを取得します． + * @return + */ public NodeID getID(); + + /** + * Nodeが保持するデータを取得します + * @return Nodeが保持するNodeData + */ public NodeData getData(); + + /** + * Nodeが属するForestを取得します． + * @return Nodeが属するForest + */ public Forest getForest(); + + /** + * 子供Nodeのリストを取得します．． + * @return 子供Nodeのリスト + */ + public List children(); + + /** + * このNodeが保持するデータをマップとしてすべて取得します． + * @return Nodeが保持するすべてのデータのマップ + */ + public Map getAll(); + + /** + * このNodeが保持する値の中で指定されたキーと対応する値を取得します． + * @param _key データに対応するキー + * @return キーと対応する値，見つからない場合はnull + */ + public byte[] get(byte[] _key); + + /** + * 指定されたリストに含まれるNodeを，すべて子供Nodeとして追加します． + * @param _children 追加される子供Nodeを保持するリスト + */ + public void addAll(List _children); + + /** + * 指定されたNodeを子供Nodeとして追加します． + * @param _child + */ + public void add(Node _child); + + /** + * キーとそれに対応する値を保存します．キーが重複した場合は上書きされます． + * @param _key キー + * @param _value 値 + */ + public void put(byte[] _key,byte[] _value); + + /** + * キーとそれに対応する値を複数保持するマップを引数としてとり，マップが保持する値をすべて追加します． + * @param _map 追加される値のマップ + */ + public void putAll(Map _map); } \ No newline at end of file diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/api/NodeData.java --- a/src/treecms/api/NodeData.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/api/NodeData.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,61 +1,149 @@ package treecms.api; import java.util.Collections; -import java.util.HashMap; -import java.util.LinkedList; import java.util.List; +import java.util.Map; import java.util.Set; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.CopyOnWriteArrayList; -public class NodeData +/** + * Nodeが保持するデータの集合です．Nodeを大きく変更するときや新しく作成される場合に使用されます． + * 通常このクラスのインスタンスをNodeから取得した場合，NodeDataインスタンスに変更（set,add）を加えても元のNodeに変更は反映されません． + * その様に実装してください． + * @author shoshi + */ +public final class NodeData { - LinkedList m_children; - HashMap m_attrs; + /** + * 子供Nodeのリスト + */ + private List m_children; + /** + * キーと対応する値のマップ + */ + private Map m_attrs; + + /** + * コンストラクタです．なにもしません + */ public NodeData() { - m_children = new LinkedList(); - m_attrs = new HashMap(); + this(null); } + /** + * コピーコンストラクタです．NodeDataの内容を防御的にコピーします． + * @param _data + */ + public NodeData(NodeData _data) + { + if(_data != null){ + m_children = new CopyOnWriteArrayList(_data.m_children); + m_attrs = new ConcurrentHashMap(_data.m_attrs); + return; + } + m_children = new CopyOnWriteArrayList(); + m_attrs = new ConcurrentHashMap(); + } + + /** + * 内部でコピーコンストラクタを呼び出します． + * @return このNodeDataのコピー + */ public NodeData deepCopy() { - NodeData copy = new NodeData(); - copy.m_children.addAll(m_children); - copy.m_attrs.putAll(m_attrs); - - return copy; + return new NodeData(this); } - public Set keys() + /** + * キーのセットを取得します． + * @return キーのセット + */ + public Set keySet() { return m_attrs.keySet(); } + /** + * キーに対応する値を取得します． + * @param _name + * @return キーに対応する値 + */ public byte[] get(byte[] _name) { return m_attrs.get(_name); } - public void set(byte[] _name,byte[] _value) + /** + * キーとそれに対応する値を追加します． + * @param _name キー + * @param _value 値 + */ + public void put(byte[] _name,byte[] _value) { m_attrs.put(_name,_value); } - public List list() + /** + * キーとそれに対応する値のマップ全体を追加します． + * @param _map + */ + public void putAll(Map _map) + { + m_attrs.putAll(_map); + } + + /** + * 子供Nodeのリストを取得します．
+ * この取得されたリストは編集できません．編集はadd,addAllより行ってください． + * @return 子供Nodeのリスト + */ + public List children() { return Collections.unmodifiableList(m_children); } - public void add(List _child) + /** + * 子供Nodeを追加します． + * @param _child + */ + public void add(Node _child) + { + m_children.add(_child); + } + + /** + * 子供Nodeリスト全部を子供Nodeとして追加します． + * @param _child + */ + public void addAll(List _child) { m_children.addAll(_child); } - public void del(List _child) + /** + * 指定されたNodeを子供Nodeのリストから削除します． + * @param _child + */ + public void remove(Node _child) + { + m_children.remove(_child); + } + + /** + * 指定されたNodeのリストに含まれるすべてのNodeを子供Nodeのリストから削除します． + * @param _child + */ + public void removeAll(List _child) { m_children.removeAll(_child); } + /** + * 子供Nodeのリストをクリアします．（すべて削除します．） + */ public void clear() { m_children.clear(); diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/api/NodeID.java --- a/src/treecms/api/NodeID.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/api/NodeID.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,13 +1,62 @@ package treecms.api; +/** + * Nodeに対応するNodeIDです．NodeIDはUUIDとバージョンから構成されており，同じUUIDを持つNodeIDはファミリーと定義します． + * 木構造で同じUUIDを持つNodeは同一のNodeと判断されます．また，一つの木構造に同じUUIDを持つNodeは存在しません． + * ファイルのバージョン管理と同じようなものと考えてください．その場合，UUIDがファイルのパスで，バージョンがファイルの更新日時です． + * @author shoshi + */ public interface NodeID { + /** + * 新しいNodeIDを作成します．新しいNodeIDは異なるUUIDを持ちます． + * @return 新しいUUIDを持つNodeID + */ public NodeID create(); + + /** + * このNodeIDが保持するUUIDを継承した，自分とバージョンの異なるNodeIDを生成します． + * @return UUIDを継承した新しいNodeID + */ public NodeID update(); + + /** + * UUIDを取得します． + * @return NodeIDが保持しているUUID + */ public String getUUID(); + + /** + * このNodeIDのバージョンを取得します． + * @return NodeIDのバージョン + */ public String getVersion(); + + /** + * このNodeIDが同一なUUIDを保持しているか比較します． + * @param _id + * @return 同一な場合はtrue，異なる場合はfalse + */ + public boolean isFamily(NodeID _id); + + /** + * このNodeIDの文字列表現を返します． + * このメソッドを実装する際に，文字列の表現方法はUUID＠Versionを採用してください． + * @return + */ public String toString(); - public boolean isFamily(NodeID _id); - public boolean equals(Object _id); + /** + * このNodeIDと指定されたNodeIDを比較します． + * @param _obj + * @return 同一な場合はtrue，異なる場合はfalse + */ + public boolean equals(Object _obj); + + /** + * このNodeIDのハッシュ値を返します．NodeIDはハッシュテーブルのキーとして使用されるとがあります． + * そのため，この関数は必ず実装してください． + * @return ハッシュ値 + */ + public int hashCode(); } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/api/Tree.java --- a/src/treecms/api/Tree.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/api/Tree.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,8 +1,14 @@ package treecms.api; +/** + * 木構造を表します． + * @author shoshi + */ public interface Tree extends Node { + /** + * この木構造のルートNodeを取得します． + * @return ルートNode + */ Node getRoot(); - Node getNodeByUUID(String _uuid); - Node updateTree(Node _target,NodeData _newData); } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/api/TreeEditor.java --- a/src/treecms/api/TreeEditor.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/api/TreeEditor.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,16 +1,43 @@ package treecms.api; +/** + * 木構造を非破壊的に更新する機能を提供します．TreeEditorはTreeを非破壊的に更新していき，commitすることでTreeに更新を適用します． + * TreeEditor.getRootはcommitされていない状態のRootNodeを取得します． + * この機能は分散リポジトリを参考に考案されました． + * @author shoshi + */ public interface TreeEditor extends Tree { - //commit local tree to remote tree + /** + * 非破壊的に更新した木構造を適用します． + * 更新する際に他の方法により木構造がすでに更新されていた場合，commitは失敗します。_forceがtrueの場合，強制的に置き換えます． + * @param _force 強制コミットフラグ + * @return 成功した場合true，失敗した場合false + */ public boolean commit(boolean _force); - //pull updates from remote tree + /** + * 監視している木構造をEditorにキャッシュします． + * @return キャッシュが成功した場合はtrue，失敗した場合はfalse + */ public boolean pull(); - //check that is remote tree modified. + /** + * 監視されている木構造が更新されていないかチェックします． + * @return 更新されていた場合はture，されていない場合はfalse + */ public boolean check(); - //merge remote tree to local tree + /** + * 監視している木構造をキャッシュにマージします． + */ public void merge(); + + /** + * 木構造を非破壊的に更新します． + * @param _target 更新する対象のNode + * @param _newData 新しいNodeに割り当てられるNodeData + * @return 更新された新しいNode + */ + public Node updateTree(Node _target,NodeData _newData); } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/memory/OnMemoryForest.java --- a/src/treecms/memory/OnMemoryForest.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/memory/OnMemoryForest.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,22 +1,24 @@ package treecms.memory; +import java.util.Map; import java.util.Random; - import java.util.UUID; import java.util.concurrent.ConcurrentHashMap; import treecms.api.Forest; import treecms.api.Node; import treecms.api.NodeData; import treecms.api.NodeID; -import treecms.tree.id.RandomNodeID; +import treecms.tree.id.AbstractRandomNodeID; public class OnMemoryForest implements Forest { - ConcurrentHashMap m_table; + Map m_table; + Map m_tipTable; public OnMemoryForest() { m_table = new ConcurrentHashMap(); + m_tipTable = new ConcurrentHashMap(); } public OnMemoryNode createNode(NodeID _id,NodeData _newData) @@ -24,13 +26,16 @@ NodeID newID = (_id != null) ? _id : createID(); NodeData newData = (_newData != null) ? _newData : new NodeData(); OnMemoryNode newNode = new OnMemoryNode(this,newID,newData); + m_table.put(newID,newNode); + m_tipTable.put(newID.getUUID(),newNode); + return newNode; } NodeID createID() { - return new RandomNodeIDImpl(null); + return new RandomNodeID(null); } @Override @@ -45,12 +50,12 @@ return createNode(null,null); } - class RandomNodeIDImpl extends RandomNodeID + class RandomNodeID extends AbstractRandomNodeID { String m_uuid; long m_version; - public RandomNodeIDImpl(String _uuid) + public RandomNodeID(String _uuid) { if(_uuid != null){ m_uuid = _uuid; @@ -63,13 +68,13 @@ @Override public NodeID create() { - return new RandomNodeIDImpl(null); + return new RandomNodeID(null); } @Override public NodeID update() { - return new RandomNodeIDImpl(m_uuid); + return new RandomNodeID(m_uuid); } @Override diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/memory/OnMemoryTree.java --- a/src/treecms/memory/OnMemoryTree.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/memory/OnMemoryTree.java Mon Mar 14 23:24:38 2011 +0900 @@ -51,56 +51,4 @@ return m_table.get(_uuid); } - @Override - public synchronized Node updateTree(Node _target,NodeData _newData) - { - LinkedList path = findAndClone(m_root,(OnMemoryNode)_target,_newData); - - if(path == null) - { - //not found. - return null; - } - - m_root = path.peekFirst(); - return path.peekLast(); - } - - OnMemoryNode cloneNode(OnMemoryNode _target,NodeData _newData) - { - OnMemoryNode clone = m_forest.createNode(_target.getID().update(),_newData); - m_table.put(clone.getID().getUUID(),clone); - return clone; - } - - LinkedList findAndClone(OnMemoryNode _parent,OnMemoryNode _target,NodeData _newData) - { - if(_parent.getID().isFamily(_target.getID())){ - //find. - LinkedList path = new LinkedList(); - OnMemoryNode clone = cloneNode((OnMemoryNode)_parent,_newData); - path.addFirst(clone); - return path; - } - - for(Node child : _parent.getData().list()){ - LinkedList path = findAndClone((OnMemoryNode)child,_target,_newData); - if(path != null){ - OnMemoryNode clone = cloneNode((OnMemoryNode)_parent,null); - clone.getData().list().remove(child); - clone.getData().list().add(path.peekFirst()); - path.addFirst(clone); - return path; - } - } - - return null; //not found. - } - - @Override - public Node getRoot() - { - return m_root; - } - } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/memory/OnMemoryTreeEditor.java --- a/src/treecms/memory/OnMemoryTreeEditor.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/memory/OnMemoryTreeEditor.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,5 +1,9 @@ package treecms.memory; +import java.util.LinkedList; + +import treecms.api.Node; +import treecms.api.NodeData; import treecms.api.TreeEditor; import treecms.merger.Merger; import treecms.merger.ReplaceMerger; @@ -47,4 +51,56 @@ Merger merger = new ReplaceMerger(); m_root = (OnMemoryNode)merger.merge(m_tree.m_root,m_root); } + + @Override + public synchronized Node updateTree(Node _target,NodeData _newData) + { + LinkedList path = findAndClone(m_root,(OnMemoryNode)_target,_newData); + + if(path == null) + { + //not found. + return null; + } + + m_root = path.peekFirst(); + return path.peekLast(); + } + + OnMemoryNode cloneNode(OnMemoryNode _target,NodeData _newData) + { + OnMemoryNode clone = m_forest.createNode(_target.getID().update(),_newData); + m_table.put(clone.getID().getUUID(),clone); + return clone; + } + + LinkedList findAndClone(OnMemoryNode _parent,OnMemoryNode _target,NodeData _newData) + { + if(_parent.getID().isFamily(_target.getID())){ + //find. + LinkedList path = new LinkedList(); + OnMemoryNode clone = cloneNode((OnMemoryNode)_parent,_newData); + path.addFirst(clone); + return path; + } + + for(Node child : _parent.getData().list()){ + LinkedList path = findAndClone((OnMemoryNode)child,_target,_newData); + if(path != null){ + OnMemoryNode clone = cloneNode((OnMemoryNode)_parent,null); + clone.getData().list().remove(child); + clone.getData().list().add(path.peekFirst()); + path.addFirst(clone); + return path; + } + } + + return null; //not found. + } + + @Override + public Node getRoot() + { + return m_root; + } } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/test/ForestTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/treecms/test/ForestTest.java Mon Mar 14 23:24:38 2011 +0900 @@ -0,0 +1,5 @@ +package treecms.test; + +public class ForestTest { + +} diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/test/NodeIDTest.java --- a/src/treecms/test/NodeIDTest.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/test/NodeIDTest.java Mon Mar 14 23:24:38 2011 +0900 @@ -34,7 +34,7 @@ @Test public void testUpdateID() { - + NodeID newID = m_newID.update(); + Assert.assertEquals(true,m_newID.isFamily(newID)); } - } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/test/TreeEditorTest.java --- a/src/treecms/test/TreeEditorTest.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/test/TreeEditorTest.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,29 +1,88 @@ package treecms.test; +import java.util.List; +import java.util.LinkedList; + +import junit.framework.Assert; + +import org.junit.Before; import org.junit.Test; - +import treecms.api.Forest; +import treecms.api.Node; +import treecms.api.NodeID; import treecms.api.Tree; import treecms.api.TreeEditor; +import treecms.tree.util.NodePathFinder; public class TreeEditorTest { Tree m_tree; TreeEditor m_editor; + Node root,ch1,ch2,ch11,ch21,ch22,ch223,cloned; + public TreeEditorTest(TreeEditor _editor,Tree _tree) { m_editor = _editor; m_tree = _tree; + + Forest forest = m_editor.getForest(); + root = m_editor.getRoot(); + + ch1 = forest.create(); + ch2 = forest.create(); + ch11 = forest.create(); + ch21 = forest.create(); + ch22 = forest.create(); + ch223 = forest.create(); //target + + LinkedList rootChildren = new LinkedList(); + rootChildren.add(ch1); + rootChildren.add(ch2); + root.getData().add(rootChildren); + + ch1.getData().add(ch11); + + LinkedList ch2Children = new LinkedList(); + ch2Children.add(ch21); + ch2Children.add(ch22); + ch2.getData().add(ch2Children); + + ch22.getData().add(ch223); + + //Edit + cloned = m_editor.updateTree(ch223,ch223.getData()); } @Test public void testEdit() { + NodePathFinder oldPath = new NodePathFinder(root,ch223); + NodePathFinder newPath = new NodePathFinder(m_editor.getRoot(),cloned); + List oldPathList = oldPath.list(); + List newPathList = newPath.list(); + //compare + for(int i = 0;i < oldPathList.size();i ++){ + Node node1 = oldPathList.get(i); + Node node2 = newPathList.get(i); + + Assert.assertEquals(true,node1.getID().isFamily(node2.getID())); + } } @Test - public void testCommit() + public void testForceCommit() + { + m_editor.commit(true); + NodeID rootID1 = m_editor.getRoot().getID(); + NodeID rootID2 = m_tree.getRoot().getID(); + + Assert.assertEquals(true,rootID1.equals(rootID2)); + } + + @Test + public void testCommitFailsWhenTreeWasUpdated() { } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/test/TreeTest.java --- a/src/treecms/test/TreeTest.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/test/TreeTest.java Mon Mar 14 23:24:38 2011 +0900 @@ -22,15 +22,6 @@ @Test public void testUpdateTree() { - /** - * Root - * + 1 - * + + 1-1 <- update this. - * + - * + 2 - * + 2-1 - */ - Node ch1 = m_tree.getForest().create(); Node ch2 = m_tree.getForest().create(); diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/cassandra/v1/CassandraForest.java --- a/src/treecms/tree/cassandra/v1/CassandraForest.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/tree/cassandra/v1/CassandraForest.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,6 +1,7 @@ package treecms.tree.cassandra.v1; import java.util.HashMap; + import java.util.Iterator; import java.util.LinkedList; import java.util.List; @@ -33,7 +34,7 @@ import treecms.api.Node; import treecms.api.NodeData; import treecms.api.NodeID; -import treecms.tree.id.RandomNodeID; +import treecms.tree.id.AbstractRandomNodeID; /** * implementation of TreeCMS with Cassandra backend. @@ -333,15 +334,15 @@ public NodeID createID(String _uuid,String _version) { - return new RandomNodeIDImpl(_uuid,_version); + return new RandomNodeID(_uuid,_version); } - class RandomNodeIDImpl extends RandomNodeID + class RandomNodeID extends AbstractRandomNodeID { String m_uuid; String m_version; - public RandomNodeIDImpl(String _uuid,String _version) + public RandomNodeID(String _uuid,String _version) { m_uuid = (_uuid != null) ? _uuid : UUID.randomUUID().toString(); m_version = (_version != null) ? _version : Long.toHexString((new Random()).nextLong()); @@ -350,13 +351,13 @@ @Override public NodeID create() { - return new RandomNodeIDImpl(null,null); + return new RandomNodeID(null,null); } @Override public NodeID update() { - return new RandomNodeIDImpl(m_uuid,null); + return new RandomNodeID(m_uuid,null); } @Override diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/cassandra/v1/CassandraNode.java --- a/src/treecms/tree/cassandra/v1/CassandraNode.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/tree/cassandra/v1/CassandraNode.java Mon Mar 14 23:24:38 2011 +0900 @@ -5,7 +5,7 @@ import treecms.api.NodeData; import treecms.api.NodeID; -public class CassandraNode implements Node +class CassandraNode implements Node { NodeID m_id; NodeData m_data; diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/cassandra/v1/CassandraTree.java --- a/src/treecms/tree/cassandra/v1/CassandraTree.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/tree/cassandra/v1/CassandraTree.java Mon Mar 14 23:24:38 2011 +0900 @@ -8,7 +8,7 @@ import treecms.api.NodeID; import treecms.api.Tree; -public class CassandraTree implements Tree +class CassandraTree implements Tree { CassandraNode m_root; CassandraForest m_forest; @@ -51,49 +51,4 @@ return m_table.get(_uuid); } - @Override - public synchronized Node updateTree(Node _target,NodeData _newData) - { - LinkedList path = findPath(m_root,(CassandraNode)_target,_newData); - - if(path == null) - { - //not found. - return null; - } - - - //clone - - - m_root = path.peekFirst(); - return path.peekLast(); - } - - CassandraNode cloneNode(CassandraNode _target,NodeData _newData) - { - CassandraNode clone = (CassandraNode)m_forest.createNode(_target.getID().update(),_newData); - m_table.put(clone.getID().getUUID(),clone); - return clone; - } - - LinkedList findPath(CassandraNode _parent,CassandraNode _target,NodeData _newData) - { - if(_parent.getID().isFamily(_target.getID())){ - //find. - LinkedList path = new LinkedList(); - path.addFirst(_target); - return path; - } - - for(Node child : _parent.getData().list()){ - LinkedList path = findPath((CassandraNode)child,_target,_newData); - if(path != null){ - path.addFirst(_parent); - return path; - } - } - - return null; //not found. - } } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/cassandra/v1/CassandraTreeEditor.java --- a/src/treecms/tree/cassandra/v1/CassandraTreeEditor.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/tree/cassandra/v1/CassandraTreeEditor.java Mon Mar 14 23:24:38 2011 +0900 @@ -1,10 +1,14 @@ package treecms.tree.cassandra.v1; +import java.util.LinkedList; + +import treecms.api.Node; +import treecms.api.NodeData; import treecms.api.TreeEditor; import treecms.merger.Merger; import treecms.merger.ReplaceMerger; -public class CassandraTreeEditor extends CassandraTree implements TreeEditor +class CassandraTreeEditor extends CassandraTree implements TreeEditor { public CassandraTreeEditor(CassandraTree _tree,CassandraForest _forest) { @@ -33,6 +37,51 @@ public void merge() { Merger merger = new ReplaceMerger(); + } + + @Override + public synchronized Node updateTree(Node _target,NodeData _newData) + { + LinkedList path = findPath(m_root,(CassandraNode)_target,_newData); + if(path == null) + { + //not found. + return null; + } + + + //clone + + + m_root = path.peekFirst(); + return path.peekLast(); + } + + CassandraNode cloneNode(CassandraNode _target,NodeData _newData) + { + CassandraNode clone = (CassandraNode)m_forest.createNode(_target.getID().update(),_newData); + m_table.put(clone.getID().getUUID(),clone); + return clone; + } + + LinkedList findPath(CassandraNode _parent,CassandraNode _target,NodeData _newData) + { + if(_parent.getID().isFamily(_target.getID())){ + //find. + LinkedList path = new LinkedList(); + path.addFirst(_target); + return path; + } + + for(Node child : _parent.getData().list()){ + LinkedList path = findPath((CassandraNode)child,_target,_newData); + if(path != null){ + path.addFirst(_parent); + return path; + } + } + + return null; //not found. } } diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/id/AbstractNodeID.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/treecms/tree/id/AbstractNodeID.java Mon Mar 14 23:24:38 2011 +0900 @@ -0,0 +1,41 @@ +package treecms.tree.id; + +import treecms.api.NodeID; + +public abstract class AbstractNodeID implements NodeID +{ + public abstract NodeID create(); + public abstract NodeID update(); + public abstract String getUUID(); + public abstract String getVersion(); + + public abstract boolean isFamily(NodeID _id); + + @Override + public String toString() + { + return (new StringBuffer(getUUID())).append('@').append(getVersion()).toString(); + } + + @Override + public int hashCode() + { + int hash = 17; + hash = 37*hash + getUUID().hashCode(); + hash = 37*hash + getVersion().hashCode(); + + return hash; + } + + @Override + public boolean equals(Object _id) + { + if(_id instanceof NodeID){ + NodeID target = (NodeID)_id; + if(isFamily(target) && getVersion().equals(target.getVersion())){ + return true; + } + } + return false; + } +} diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/id/AbstractRandomNodeID.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/treecms/tree/id/AbstractRandomNodeID.java Mon Mar 14 23:24:38 2011 +0900 @@ -0,0 +1,16 @@ +package treecms.tree.id; + +import treecms.api.NodeID; + +public abstract class AbstractRandomNodeID extends AbstractNodeID +{ + public abstract NodeID create(); + public abstract String getUUID(); + public abstract String getVersion(); + public abstract NodeID update(); + + public boolean isFamily(NodeID _id) + { + return (_id instanceof AbstractNodeID) ? getUUID().equals(_id.getUUID()) : false; + } +} diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/id/RandomNodeID.java --- a/src/treecms/tree/id/RandomNodeID.java Tue Mar 01 01:29:59 2011 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,39 +0,0 @@ -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(Object _id) - { - try{ - RandomNodeID target = (RandomNodeID)_id; - if(isFamily(target) && getVersion().equals(target.getVersion())){ - return true; - } - return false; - }catch(Exception _e){ - _e.printStackTrace(); - return false; - } - } -} diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/util/NodePathFinder.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/treecms/tree/util/NodePathFinder.java Mon Mar 14 23:24:38 2011 +0900 @@ -0,0 +1,73 @@ +package treecms.tree.util; + +import java.util.Collections; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import treecms.api.Node; + +/** + * あるNodeから対象となるNodeまでのパスのイテレータです． + * @author shoshi + */ +public class NodePathFinder implements Iterable +{ + private Node m_root; + private Node m_target; + private List m_path; + + /** + * コンストラクタです．コンストラクタが作成された時点でパスが検索されます． + * @param _root 木構造のトップです． + * @param _target パス検索の対象となるNodeです． + */ + public NodePathFinder(Node _root,Node _target) + { + m_root = _root; + m_target = _target; + m_path = Collections.unmodifiableList(findPath(m_root,m_target)); + } + + /** + * パスまでのイテレータを返します． + * イテレータはremoveメソッドをサポートしません． + */ + @Override + public Iterator iterator() + { + return m_path.iterator(); + } + + /** + * パスのリストを取得します．このパスのリストは編集できません． + * @return パスまでのリスト + */ + public List list() + { + return m_path; + } + + /** + * _fromから_targetまでのパスを再帰的に取得します + * @param _from 取得するパスの始まり + * @param _target 取得するパスの終わり + * @return _fromから_targetまでのリスト + */ + private LinkedList findPath(Node _from,Node _target) + { + if(_from.getID().isFamily(_target.getID())){ + LinkedList path = new LinkedList(); + path.add(_from); + return path; + } + + for(Node child : _from.children()){ + LinkedList path = findPath(child,_target); + if(path != null){ + path.add(_from); + } + } + + return null; + } +} diff -r 87bba22e4fa2 -r 12604eb6b615 src/treecms/tree/util/PreorderTreewalker.java --- a/src/treecms/tree/util/PreorderTreewalker.java Tue Mar 01 01:29:59 2011 +0900 +++ b/src/treecms/tree/util/PreorderTreewalker.java Mon Mar 14 23:24:38 2011 +0900 @@ -4,16 +4,28 @@ import java.util.Stack; import treecms.api.Node; +/** + * 順序付き深さ優先探索で木構造を走査します．また，走査したイテレータを返します． + * @author shoshi + */ public class PreorderTreewalker implements Iterable { private Node m_root; + /** + * コンストラクタです． + * @param _root 木構造のルートノード + */ public PreorderTreewalker(Node _root) { m_root = _root; } + /** + * イテレータを返します． + * @return 順序付き深さ優先探索でのイテレータ + */ @Override public Iterator iterator() { @@ -29,7 +41,7 @@ { m_depth = new Stack>>(); m_next = m_root; - m_depth.add(new Pair>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ！ + m_depth.add(new Pair>(m_next,m_next.children().iterator())); // ワケがわからないよ！ } @Override @@ -48,7 +60,7 @@ Iterator itr = context.m_right; if(itr.hasNext()){ m_next = itr.next(); - m_depth.add(new Pair>(m_next,m_next.getData().list().iterator())); // ワケがわからないよ！ + m_depth.add(new Pair>(m_next,m_next.children().iterator())); // ワケがわからないよ！ }else{ m_depth.pop(); while(!m_depth.isEmpty()){