changeset 14:8bf59f161b23

separete Node methods to NodeContext , NodeAttribute , NodeChildren
author misaka
date Tue, 17 May 2011 18:44:14 +0900
parents c8601b0fa8a3
children 22cd920986c5
files CHANGELOG src/treecms/api/Forest.java src/treecms/api/MonotonicTree.java src/treecms/api/MonotonicTreeNode.java src/treecms/api/Node.java src/treecms/api/NodeAttributes.java src/treecms/api/NodeAttributesImpl.java src/treecms/api/NodeChildren.java src/treecms/api/NodeContext.java src/treecms/api/NodeData.java src/treecms/api/SingleNode.java src/treecms/api/TreeNode.java src/treecms/memory/OnMemoryMonotonicTreeNode.java src/treecms/memory/OnMemoryNode.java src/treecms/memory/OnMemoryTreeNode.java src/treecms/test/GenericsTest.java src/treecms/tree/util/NodeChildrenImpl.java src/treecms/tree/util/NodePathFinder.java src/treecms/tree/util/PathNotFoundException.java src/treecms/tree/util/Predicate.java src/treecms/tree/util/PredicatedList.java src/treecms/tree/util/PreorderTreewalker.java
diffstat 22 files changed, 584 insertions(+), 895 deletions(-) [+]
line wrap: on
line diff
--- a/CHANGELOG	Wed May 11 22:08:20 2011 +0900
+++ b/CHANGELOG	Tue May 17 18:44:14 2011 +0900
@@ -26,6 +26,44 @@
 	
 開発メモ
 
+2011-05-17
+	NodeAttributes、NodeChildrenを作って分けた.
+	NodeAttributesはノードの要素を保持する。
+	NodeChildrenはノードの子供のリストを表す。
+	
+	Node extends NodeAttributes,NodeChildren
+	
+	SingleNode extends NodeBase , NodeAttributes , NodeChildren<SingleNode>
+	TreeNode extends NodeBase , NodeAttributes , NodeChildren<TreeNode>
+	
+	NodeChildrenをNodeChildren<T>にしようかと思っていまする。
+	この方法なら行けるかも?
+
+2011-05-16
+	replaceChildの実装を忘れていたので実装しよう。
+	書き換える必要があるのは Node,TreeNode,MonotonicTreeNode
+	の3つのインターフェイスかな
+	
+	現段階でNodeのメソッドは
+		属性関係が get,getAll,put,putAll,remove,removeAll,clear
+		子供関係が getChildren,addChild,addChildren,removeChild,removeChildren,replaceChildren,clearChildren
+		その他 getID
+		
+	やっぱり、子供ノード用の専用リストをつくりましょう。
+	NodeChildList
+		public List<Node> getList();
+		public boolean add(Node _n); //ノード追加
+		public boolean addAll(List<Node> _list); //ノードのリストを追加
+		public Node get(String _id); //NodeIDに当たるNodeの取得
+		public Node get(int _index); //_indexの場所にいるNodeの取得
+		public Node remove(String _id); //NodeIDを削除
+		public Node remove(int _index); //_indexの場所にいるNodeの削除
+		public boolean contains(String _id); //NodeIDがこのリストに含まれるかチェック
+		public boolean swap(String _id1,String _id2); //2つのNodeIDを入れ替える
+		public void clear(); //リストのクリア
+		
+	もう訳がわからない
+
 2011-05-11
 	クローンを伝搬させる方法で非破壊的編集の実装を書いている.
 
--- a/src/treecms/api/Forest.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/api/Forest.java	Tue May 17 18:44:14 2011 +0900
@@ -11,27 +11,27 @@
 	 * @param _id Nodeを示すNodeID.
 	 * @return NodeIDと一致するNodeがある場合は,Nodeのインスタンスを返し,見つからない場合はnullを返します.
 	 */
-	Node get(NodeID _id);
+	SingleNode get(NodeID _id);
 	
 	/**
 	 * 同じUUIDを持つNode中で最新のNodeを取得します.
 	 * @param _uuid NodeIDのUUID
 	 * @return UUIDと一致するNodeが見つからない場合はnullを返します.
 	 */
-	Node getTip(String _uuid);
+	SingleNode getTip(String _uuid);
 	
 	/**
 	 * 新しいNodeを作成します.このメソッドで作成されるNodeは新しいUUIDを持ちます.
 	 * @return 新しいNode
 	 */
-	Node create();
+	SingleNode create();
 	
 	/**
 	 * あるNodeを木として返します
 	 * @param _root
 	 * @return Tree あるNodeをルートとした木
 	 */
-	Tree getTree(Node _root);
+	Tree getTree(SingleNode _root);
 	
 	/**
 	 * 木を非破壊的に編集するMonotonicTreeを取得します
@@ -46,7 +46,7 @@
 	 * @param _data 新しいNodeが保持するNodeData
 	 * @return NodeDataを保持した新しいNode
 	 */
-	Node create(NodeData _data);
+	SingleNode create(NodeData<SingleNode> _data);
 	
 	/**
 	 * このForestの現在の最新のMainTreeを取得します
--- a/src/treecms/api/MonotonicTree.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/api/MonotonicTree.java	Tue May 17 18:44:14 2011 +0900
@@ -1,7 +1,5 @@
 package treecms.api;
 
-import treecms.tree.util.PathNotFoundException;
-
 /**
  * 木構造を非破壊的に更新する機能を提供します.TreeEditorはTreeを非破壊的に更新していき,commitすることでTreeに更新を適用します.
  * TreeEditor.getRootはcommitされていない状態のRootNodeを取得します.
@@ -39,25 +37,5 @@
 	 * この木構造のルートNodeを返します。
 	 * @return この木構造のルートNode
 	 */
-	public Node getRoot();
-	
-	/**
-	 * 木構造を非破壊的に更新します.変更の対象となるNodeが木構造内に見つからない場合,PathNotFoundExceptionがスローされます.
-	 * @param _target 更新する対象のNode
-	 * @param _newData 新しいNodeに割り当てられるNodeData
-	 * @return 更新された新しいNode
-	 * @throws PathNotFoundException パスが見つからない場合
-	 */
-	public Node updateTree(Node _target,NodeData _newData) throws PathNotFoundException;
-	
-	/**
-	 * 木構造を非破壊的に更新します.Nodeへのパスが既知な場合このメソッドを使用できます。
-	 * このメソッドは使用時にパスの正当性を検証します。見つからない場合PathNotFoundExceptionがスローされます
-	 * @param _target
-	 * @param _newData
-	 * @param _path
-	 * @return 更新された新しいNode
-	 * @throws PathNotFoundException 
-	 */
-	public Node updateTree(Node _target,NodeData _newData,Node[] _path) throws PathNotFoundException;
+	public SingleNode getRoot();
 }
--- a/src/treecms/api/MonotonicTreeNode.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/api/MonotonicTreeNode.java	Tue May 17 18:44:14 2011 +0900
@@ -1,44 +1,12 @@
 package treecms.api;
 
-import java.nio.ByteBuffer;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
 /**
  * NodeのDoubleLinkedな実装です.SingleLinkedとは違いNodeの親情報まで保持します.
  * TreeNodeとは違い、この実装は木を非破壊的に編集します.
  * @author shoshi
  */
-public interface MonotonicTreeNode
+public interface MonotonicTreeNode extends Node<MonotonicTreeNode>
 {
-	/*
-	 * 属性関連のメソッド
-	 */
-	public ByteBuffer get(ByteBuffer _key);
-	public Map<ByteBuffer,ByteBuffer> getAll();
-	public void put(ByteBuffer _key,ByteBuffer _value);
-	public void putAll(Map<ByteBuffer,ByteBuffer> _map);
-	public void remove(ByteBuffer _key);
-	public void removeAll(Set<ByteBuffer> _keys);
-	public void clear();
-	
-	/*
-	 * 子供関連のメソッド 
-	 */
-	public Iterator<MonotonicTreeNode> getChildren();
-	public void addChild(MonotonicTreeNode _n);
-	public void addChildren(List<MonotonicTreeNode> _list);
-	public void removeChild(MonotonicTreeNode _n);
-	public void removeChildren(List<MonotonicTreeNode> _list);
-	public void clearChildren();
-	
-	/*
-	 * 親関連のメソッド
-	 */
-	public NodeID getID();
-	public Forest getForest();
 	public MonotonicTreeNode getParent();
-	public Node getNode();
+	public SingleNode getNode();
 }
--- a/src/treecms/api/Node.java	Wed May 11 22:08:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,139 +0,0 @@
-package treecms.api;
-
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.nio.ByteBuffer;
-
-/**
- * 木構造の基本のデータ単位であるNodeを示します.Nodeは子供のリストとデータのマップを保持します.また,クライアントはノードが保持しているデータをNodeDataとして
- * 取得することが出来ます.
- * 
- * NodeはSingleLinkで子供Nodeへのパスしか保持していません、どのNodeが親かどうか判断するのは不可能です.
- * このようにしたのは,非破壊的木構造を実装するに当たり,編集対象のNodeの親を検索するのが困難であるからです.
- * DoubleLinkな実装はTree/MonotonicTreeで行います.
- * 
- * また,重複した子供を追加することは出来ません,このインターフェイスを実装するクラスはそのように実装します.
- * @author shoshi
- */
-public interface Node
-{
-	/**
-	 * Nodeに対応するNodeIDを取得します.
-	 * @return Nodeに対応するNodeID
-	 */
-	public NodeID getID();
-	
-	/**
-	 * Nodeが保持するデータを取得します.クライアントはこのメソッドを用いて取得されるNodeDataを用いてNodeの内容を<b>変更できません</b>。
-	 * 変更を加えた場合は無視されるか、例外が発生します.
-	 * @return Nodeが保持するNodeData
-	 */
-	public NodeData getData();
-	
-	/**
-	 * Nodeが属するForestを取得します.
-	 * @return Nodeが属するForest
-	 */
-	public Forest getForest();
-	
-	/*
-	 * 属性関連のメソッド
-	 * get,getAll,put,putAll,remove,removeAll,clear
-	 */
-	
-	/**
-	 * このNodeが保持する値の中で指定されたキーと対応する値を取得します.
-	 * @param _key データに対応するキー
-	 * @return キーと対応する値,見つからない場合はnull
-	 */
-	public ByteBuffer get(ByteBuffer _key);
-	
-	/**
-	 * このNodeが保持するデータをマップとしてすべて取得します.
-	 * @return Nodeが保持するすべてのデータのマップ
-	 */
-	public Map<ByteBuffer,ByteBuffer> getAll();
-	
-	/**
-	 * キーとそれに対応する値を保存します.キーが重複した場合は上書きされます.
-	 * @param _key キー
-	 * @param _value 値
-	 */
-	public void put(ByteBuffer _key,ByteBuffer _value);
-	
-	/**
-	 * キーとそれに対応する値を複数保持するマップを引数としてとり,マップが保持する値をすべて追加します.
-	 * @param _map 追加される値のマップ
-	 */
-	public void putAll(Map<ByteBuffer,ByteBuffer> _map);
-	
-	/**
-	 * キーとそれに対応する値を削除します。
-	 * @param _key キー
-	 */
-	public void remove(ByteBuffer _key);
-	
-	/**
-	 * Keyの集合すべてを削除します.
-	 * @param _key
-	 */
-	public void removeAll(Set<ByteBuffer> _key);
-	
-	/**
-	 * Keyの集合全てを削除します.
-	 */
-	public void clear();
-	
-	/*
-	 * 子供関連
-	 * getChildren,addChild,addChildren,removeChild,removeChildren,clearChildren
-	 */
-	
-	/**
-	 * 子供のIteratorを取得します.このIteratorは編集するためのメソッドは実装しません.
-	 * 呼び出した場合は例外は発生します.
-	 * @return 子供NodeのIterator
-	 */
-	public Iterator<Node> getChildren();
-	
-	/**
-	 * 指定されたNodeを子供Nodeとして追加します.
-	 * @param _child
-	 */
-	public void addChild(Node _child);
-	
-	/**
-	 * 指定されたリストに含まれるNodeを,すべて子供Nodeとして追加します.
-	 * @param _children 追加される子供Nodeを保持するリスト
-	 */
-	public void addChildren(List<Node> _children);
-	
-	/**
-	 * 指定されたNodeを削除します。
-	 * @param _child
-	 */
-	public void removeChild(Node _child);
-	
-	/**
-	 * 指定した子供を全て削除します.
-	 * @param _children 削除される子供
-	 */
-	public void removeChildren(List<Node> _children);
-	
-	/**
-	 * 全ての子供を削除します. 
-	 */
-	public void clearChildren();
-	
-	/**
-	 * このNodeのクローンを作成します.
-	 * 
-	 * クローンされたNodeはNodeIDとデータを受け継ぎます.クローンする際にデータに変更を加えることが出来ます.
-	 * 変更を加える必要がない場合はnullを_dataに引数として渡します.
-	 * 
-	 * @param _data クローンされるNodeに適用されるNodeData
-	 */
-	public Node cloneNode(NodeData _data);
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/NodeAttributes.java	Tue May 17 18:44:14 2011 +0900
@@ -0,0 +1,19 @@
+package treecms.api;
+
+import java.nio.ByteBuffer;
+import java.util.Map;
+import java.util.Set;
+
+
+public interface NodeAttributes
+{
+	public Map<ByteBuffer,ByteBuffer> asMap();
+	public Set<ByteBuffer> getKeySet();
+	public void put(ByteBuffer _name,ByteBuffer _value);
+	public void putAll(NodeAttributes _attrs);
+	public ByteBuffer get(ByteBuffer _name);
+	public NodeAttributes getAll();
+	public void remove(ByteBuffer _name);
+	public void removeAll(Set<ByteBuffer> _keySet);
+	public void clearAttributes();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/NodeAttributesImpl.java	Tue May 17 18:44:14 2011 +0900
@@ -0,0 +1,80 @@
+package treecms.api;
+
+import java.nio.ByteBuffer;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+public class NodeAttributesImpl implements NodeAttributes
+{
+	private Map<ByteBuffer,ByteBuffer> m_attrs;
+	
+	public NodeAttributesImpl()
+	{
+		m_attrs = new HashMap<ByteBuffer,ByteBuffer>();
+	}
+	
+	public NodeAttributesImpl(NodeAttributesImpl _attrs)
+	{
+		super();
+		m_attrs.putAll(_attrs.m_attrs);
+	}
+	
+	@Override
+	public Set<ByteBuffer> getKeySet()
+	{
+		return m_attrs.keySet();
+	}
+
+	@Override
+	public void put(ByteBuffer _name, ByteBuffer _value)
+	{
+		m_attrs.put(_name,_value);
+	}
+
+	@Override
+	public void putAll(NodeAttributes _attrs)
+	{
+		m_attrs.putAll(_attrs.asMap());
+	}
+	
+	@Override
+	public Map<ByteBuffer,ByteBuffer> asMap()
+	{
+		return Collections.unmodifiableMap(m_attrs);
+	}
+
+	@Override
+	public ByteBuffer get(ByteBuffer _name)
+	{
+		return m_attrs.get(_name);
+	}
+
+	@Override
+	public NodeAttributes getAll()
+	{
+		return this;
+	}
+
+	@Override
+	public void remove(ByteBuffer _name)
+	{
+		m_attrs.remove(_name);
+	}
+
+	@Override
+	public void removeAll(Set<ByteBuffer> _keySet)
+	{
+		for(ByteBuffer _key : _keySet){
+			remove(_key);
+		}
+	}
+
+	@Override
+	public void clearAttributes()
+	{
+		m_attrs.clear();
+	}
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/NodeChildren.java	Tue May 17 18:44:14 2011 +0900
@@ -0,0 +1,20 @@
+package treecms.api;
+
+import java.util.List;
+import java.util.Set;
+
+public interface NodeChildren<T extends Node<T>>
+{
+	public List<T> getList();
+	public Set<String> getUUIDSet();
+	public boolean add(T _child);
+	public boolean addAll(NodeChildren<T> _children);
+	public T get(String _uuid);
+	public T get(int _index);
+	public T remove(String _uuid);
+	public T remove(int _index);
+	public T replace(T _newChild);
+	public boolean contains(String _id);
+	public boolean swap(String _uuid1,String _uuid2);
+	public void clearChildren();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/NodeContext.java	Tue May 17 18:44:14 2011 +0900
@@ -0,0 +1,7 @@
+package treecms.api;
+
+public interface NodeContext
+{
+	public NodeID getID();
+	public Forest getForest();
+}
--- a/src/treecms/api/NodeData.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/api/NodeData.java	Tue May 17 18:44:14 2011 +0900
@@ -1,15 +1,11 @@
 package treecms.api;
 
 import java.nio.ByteBuffer;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
-import org.apache.commons.collections.list.SetUniqueList;
+
+import treecms.tree.util.NodeChildrenImpl;
 
 /**
  * Node が保持するデータのスナップショットです.Node を大きく変更するときや新しく作成される場合に使用されます.
@@ -20,169 +16,140 @@
  * getID,getForest を呼び出すと UnsupportedOperationException をスローします.
  * @author shoshi
  */
-public final class NodeData implements Node
+public class NodeData<T extends Node<T>> implements NodeAttributes , NodeChildren<T>
 {
-	/**
-	 * 子供 Node の List
-	 * 子供 Node の List は重複する Node を許可しない.
-	 */
-	private List<Node> m_children;
-	
-	/**
-	 * Key と対応する Value の Map
-	 */
-	private Map<ByteBuffer,ByteBuffer> m_attrs;
-	
-	/**
-	 * コンストラクタです.なにもしません
-	 */
-	public NodeData()
-	{
-		this(null);
-	}
+	private NodeChildrenImpl<T> m_children;
+	private NodeAttributesImpl m_attrs;
 	
-	/**
-	 * コピーコンストラクタです.
-	 * NodeData の内容を防御的にコピーします.
-	 * @param _data
-	 */
-	public NodeData(NodeData _data)
+	public NodeData(NodeChildren<T> _children,NodeAttributes _attrs)
+	{
+		m_children = new NodeChildrenImpl<T>();
+		m_attrs = new NodeAttributesImpl();
+	}
+
+	@Override
+	public List<T> getList()
 	{
-		if(_data != null){
-			// SetUniqueList を使用することにより,List の重複要素を許可しない.
-			m_children = SetUniqueList.decorate(_data.m_children);
-			m_attrs = new HashMap<ByteBuffer,ByteBuffer>(_data.m_attrs);
-			return;
-		}
-		m_children = SetUniqueList.decorate(new ArrayList<Node>());
-		m_attrs = new HashMap<ByteBuffer,ByteBuffer>();
+		return m_children.getList();
+	}
+
+	@Override
+	public Set<String> getUUIDSet()
+	{
+		return m_children.getUUIDSet();
+	}
+
+	@Override
+	public boolean add(T _child)
+	{
+		return m_children.add(_child);
 	}
-	
-	/**
-	 * 内部でコピーコンストラクタを呼び出します.
-	 * @return この NodeData のコピー
-	 */
-	public NodeData deepCopy()
+
+	@Override
+	public boolean addAll(NodeChildren<T> _children)
+	{
+		return m_children.addAll(_children);
+	}
+
+	@Override
+	public T get(String _uuid)
 	{
-		return new NodeData(this);
+		return m_children.get(_uuid);
 	}
-	
+
 	@Override
-	public NodeID getID()
+	public T get(int _index)
 	{
-		//このクラスはデータのみ保持する.
-		return null;
+		return m_children.get(_index);
+	}
+
+	@Override
+	public T remove(String _uuid)
+	{
+		return m_children.remove(_uuid);
 	}
 
 	@Override
-	public NodeData getData()
+	public T remove(int _index)
+	{
+		return m_children.remove(_index);
+	}
+
+	@Override
+	public T replace(T _newChild)
 	{
-		return new NodeData(this);
+		return m_children.replace(_newChild);
+	}
+
+	@Override
+	public boolean contains(String _id)
+	{
+		return m_children.contains(_id);
+	}
+
+	@Override
+	public boolean swap(String _uuid1, String _uuid2)
+	{
+		return m_children.swap(_uuid1, _uuid2);
 	}
 
 	@Override
-	public Forest getForest()
+	public void clearChildren()
 	{
-		//このクラスはデータのみ保持する.
-		return null;
+		m_children.clearChildren();
+	}
+
+	@Override
+	public Map<ByteBuffer, ByteBuffer> asMap()
+	{
+		return m_attrs.asMap();
 	}
-	
-	/*
-	 * 属性関連
-	 */
-	
-	public Set<ByteBuffer> keySet()
+
+	@Override
+	public Set<ByteBuffer> getKeySet()
+	{
+		return m_attrs.getKeySet();
+	}
+
+	@Override
+	public void put(ByteBuffer _name, ByteBuffer _value)
 	{
-		return m_attrs.keySet();
+		m_attrs.put(_name,_value);
 	}
-	
+
+	@Override
+	public void putAll(NodeAttributes _attrs) 
+	{
+		m_attrs.putAll(_attrs);
+	}
+
 	@Override
 	public ByteBuffer get(ByteBuffer _name)
 	{
 		return m_attrs.get(_name);
 	}
-	
+
 	@Override
-	public Map<ByteBuffer,ByteBuffer> getAll()
-	{
-		return Collections.unmodifiableMap(this.m_attrs);
-	}
-	
-	@Override
-	public void put(ByteBuffer _name,ByteBuffer _value)
+	public NodeAttributes getAll()
 	{
-		m_attrs.put(_name,_value);
+		return m_attrs.getAll();
 	}
-	
-	@Override
-	public void putAll(Map<ByteBuffer,ByteBuffer> _map)
-	{
-		m_attrs.putAll(_map);
-	}
-	
+
 	@Override
 	public void remove(ByteBuffer _name)
 	{
 		m_attrs.remove(_name);
 	}
-	
+
 	@Override
 	public void removeAll(Set<ByteBuffer> _keySet)
 	{
-		for(ByteBuffer _key : _keySet){
-			m_attrs.remove(_key);
-		}
-	}
-	
-	@Override
-	public void clear()
-	{
-		m_attrs.clear();
+		m_attrs.removeAll(_keySet);
 	}
-	
-	/*
-	 * 子供関連
-	 */
-	
-	@Override
-	public Iterator<Node> getChildren()
-	{
-		return Collections.unmodifiableList(m_children).iterator();
-	}
-	
-	@Override
-	public void addChild(Node _child)
-	{
-		m_children.add(_child);
-	}
-	
+
 	@Override
-	public void addChildren(List<Node> _child)
-	{
-		m_children.addAll(_child);
-	}
-	
-	@Override
-	public void removeChild(Node _child)
-	{
-		m_children.remove(_child);
-	}
-	
-	@Override
-	public void removeChildren(List<Node> _child)
+	public void clearAttributes()
 	{
-		m_children.removeAll(_child);
-	}
-	
-	@Override
-	public void clearChildren()
-	{
-		m_children.clear();
-	}
-	
-	@Override
-	public Node cloneNode(NodeData _data)
-	{
-		throw new UnsupportedOperationException();
+		m_attrs.clearAttributes();
 	}
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/api/SingleNode.java	Tue May 17 18:44:14 2011 +0900
@@ -0,0 +1,5 @@
+package treecms.api;
+
+public interface SingleNode extends Node<SingleNode>
+{
+}
--- a/src/treecms/api/TreeNode.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/api/TreeNode.java	Tue May 17 18:44:14 2011 +0900
@@ -1,11 +1,5 @@
 package treecms.api;
 
-import java.nio.ByteBuffer;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
 /**
  * DoubleLinkedなNodeの実装です.SingleLinkedなNodeの実装と違い,親の情報を保持します.
  * 非破壊的木構造の実装では,Nodeは子どもの情報しか持っていません.これは,一つのNodeに対して複数の親が存在するためです.
@@ -17,34 +11,8 @@
  * また,TreeNodeを編集したときは非破壊的に編集されず、破壊的に編集されます.
  * @author shoshi
  */
-public interface TreeNode
+public interface TreeNode extends Node<TreeNode>
 {
-	/*
-	 * 属性関連のメソッド
-	 */
-	public ByteBuffer get(ByteBuffer _key);
-	public Map<ByteBuffer,ByteBuffer> getAll();
-	public void put(ByteBuffer _key,ByteBuffer _value);
-	public void putAll(Map<ByteBuffer,ByteBuffer> _map);
-	public void remove(ByteBuffer _key);
-	public void removeAll(Set<ByteBuffer> _keys);
-	public void clear();
-	
-	/*
-	 * 子供関連のメソッド 
-	 */
-	public Iterator<TreeNode> getChildren();
-	public void addChild(TreeNode _n);
-	public void addChildren(List<TreeNode> _list);
-	public void removeChild(TreeNode _n);
-	public void removeChildren(List<TreeNode> _list);
-	public void clearChildren();
-	
-	/*
-	 * 親関連のメソッド
-	 */
-	public NodeID getID();
-	public Forest getForest();
 	public TreeNode getParent();
-	public Node getNode();
+	public TreeNode getNode();
 }
--- a/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryMonotonicTreeNode.java	Tue May 17 18:44:14 2011 +0900
@@ -127,10 +127,17 @@
 	 * _fromがnullの場合は,自身が編集元であることを示します.
 	 * @param _from 編集元のOnMemoryMonotonicTreeNode
 	 */
-	public void transmit(OnMemoryNode _from)
+	public void transmit(OnMemoryNode _orig,OnMemoryNode _edit)
 	{
 		Node clone = m_node.cloneNode(null);
-		m_node.removeChild(_from);
+		clone.replaceChild(_orig,_edit);
+		
+		if(m_parent != null){
+			m_parent.transmit(m_node,(OnMemoryNode)clone);
+			return;
+		}
+		
+		//なにかしたい
 	}
 	
 	/*
--- a/src/treecms/memory/OnMemoryNode.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryNode.java	Tue May 17 18:44:14 2011 +0900
@@ -1,11 +1,5 @@
 package treecms.memory;
 
-import java.nio.ByteBuffer;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
 import treecms.api.Forest;
 import treecms.api.Node;
 import treecms.api.NodeData;
@@ -15,12 +9,10 @@
  * オンメモリ上でのNodeの実装です。 
  * @author shoshi
  */
-class OnMemoryNode implements Node
+class OnMemoryNode extends NodeData implements Node
 {
 	private OnMemoryForest m_forest;
-	
 	private NodeID m_id;
-	private NodeData m_data;
 	
 	/**
 	 * コンストラクタ
@@ -30,21 +22,11 @@
 	 */
 	public OnMemoryNode(OnMemoryForest _forest,NodeID _id,NodeData _newData)
 	{
+		super(_newData);
 		m_id = _id;
 		m_forest = _forest;
-		m_data = (_newData != null) ? _newData.deepCopy() : new NodeData();
 	}
-	
-	/*
-	 * Nodeの情報関連
-	 */
-	
-	@Override
-	public Forest getForest()
-	{
-		return m_forest;
-	}
-	
+
 	@Override
 	public NodeID getID()
 	{
@@ -54,113 +36,18 @@
 	@Override
 	public NodeData getData()
 	{
-		return m_data.deepCopy();
-	}
-	
-	/*
-	 * 子供関連のメソッド
-	 */
-	
-	@Override
-	public Iterator<Node> getChildren()
-	{
-		//Iteratorが変更不可なので、そのまま渡しても構わない
-		return m_data.getChildren();
-	}
-
-	@Override
-	public void addChild(Node _child)
-	{
-		m_data.addChild(_child);
-	}
-	
-	@Override
-	public void addChildren(List<Node> _child)
-	{
-		m_data.addChildren(_child);
-	}
-	
-	@Override
-	public void removeChild(Node _child)
-	{
-		m_data.removeChild(_child);
-	}
-	
-	@Override
-	public void removeChildren(List<Node> _children)
-	{
-		m_data.removeChildren(_children);
-	}
-	
-	@Override
-	public void clearChildren()
-	{
-		m_data.clearChildren();
-	}
-
-	/*
-	 * 要素関連のメソッド
-	 */
-
-	@Override
-	public ByteBuffer get(ByteBuffer _key)
-	{
-		return m_data.get(_key);
+		return new NodeData(this);
 	}
 
 	@Override
-	public Map<ByteBuffer,ByteBuffer> getAll()
-	{
-		return m_data.getAll();
-	}
-
-	@Override
-	public void put(ByteBuffer _key, ByteBuffer _value)
+	public Forest getForest()
 	{
-		m_data.put(_key,_value);
-	}
-
-	@Override
-	public void putAll(Map<ByteBuffer, ByteBuffer> _map)
-	{
-		m_data.putAll(_map);
+		return m_forest;
 	}
 
 	@Override
-	public void remove(ByteBuffer _key)
-	{
-		m_data.remove(_key);
-	}
-	
-	@Override
-	public void removeAll(Set<ByteBuffer> _keySet)
-	{
-		m_data.removeAll(_keySet);
-	}
-	
-	@Override
-	public void clear()
+	public Node cloneNode(NodeData _newData)
 	{
-		m_data.clear();
-	}
-	
-	@Override
-	public int hashCode()
-	{
-		return m_id.hashCode();
-	}
-	
-	@Override
-	public String toString()
-	{
-		return getID().toString();
-	}
-	
-	@Override
-	public Node cloneNode(NodeData _data)
-	{
-		NodeData newData = (_data != null) ? _data : m_data;
-		Node clone = m_forest.createNode(m_id.update(),newData);
-		return clone;
+		return m_forest.createNode(m_id,_newData);
 	}
 }
--- a/src/treecms/memory/OnMemoryTreeNode.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/memory/OnMemoryTreeNode.java	Tue May 17 18:44:14 2011 +0900
@@ -78,7 +78,7 @@
 		 * m_node(対象ノード)のリストにはNodeが格納されており、TreeNodeのリストを取得するためにはTreeNodeで要素を構成する必要がある.
 		 */
 		LinkedList<TreeNode> ret = new LinkedList<TreeNode>();
-		for(Iterator<Node> it = m_node.getChildren();it.hasNext();){
+		for(Iterator<Node> it = m_node.getList().iterator();it.hasNext();){
 			OnMemoryNode n = (OnMemoryNode)it.next();
 			ret.add(new OnMemoryTreeNode(n,this));
 		}
@@ -87,13 +87,13 @@
 	}
 	
 	@Override
-	public void addChild(TreeNode _child)
+	public void add(TreeNode _child)
 	{
-		m_node.addChild(_child.getNode());
+		m_node.add(_child.getNode());
 	}
 
 	@Override
-	public void addChildren(List<TreeNode> _children)
+	public void addAll(NodeChildren _children)
 	{
 		/*
 		 * TreeNodeのリストからNodeのリストへ変換する
@@ -104,7 +104,7 @@
 			res.add(tn.getNode());
 		}
 		
-		m_node.addChildren(res);
+		m_node.addAll(res);
 	}
 	
 	@Override
--- a/src/treecms/test/GenericsTest.java	Wed May 11 22:08:20 2011 +0900
+++ b/src/treecms/test/GenericsTest.java	Tue May 17 18:44:14 2011 +0900
@@ -19,7 +19,7 @@
 interface Foo
 {
 	public Foo get();
-	public List<Foo> list();
+	public List<Foo> list(Foo _f);
 }
 
 interface Hoge extends Foo
@@ -27,6 +27,5 @@
 	@Override
 	public Hoge get();
 	
-	@Override
-	public List<Foo> list();
+	public List<Foo> list(Hoge _h);
 }
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/treecms/tree/util/NodeChildrenImpl.java	Tue May 17 18:44:14 2011 +0900
@@ -0,0 +1,282 @@
+package treecms.tree.util;
+
+import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.List;
+import treecms.api.Node;
+import treecms.api.NodeAttributes;
+import treecms.api.NodeChildren;
+
+/**
+ * 子供ノードを格納するため専用のリストです.java.util.List<T>は継承しておりません.
+ * 子供ノードのリストには リスト内に同じUUIDを持つNodeが存在 してはいけません.
+ * @author shoshi
+ */
+public class NodeChildrenImpl<T extends Node<T>> implements NodeAttributes , NodeChildren<T>
+{
+	private List<T> m_list;
+	private Set<String> m_set;
+	
+	public NodeChildrenImpl()
+	{
+		m_list = new ArrayList<T>();
+		m_set = new HashSet<String>();
+	}
+	
+	public NodeChildrenImpl(NodeChildrenImpl<T> _list)
+	{
+		this();
+		
+		if(_list != null){
+			addAll(_list);
+		}
+	}
+	
+	public List<T> getList()
+	{
+		return Collections.unmodifiableList(m_list);
+	}
+	
+	public Set<String> getUUIDSet()
+	{
+		return Collections.unmodifiableSet(m_set);
+	}
+	
+	@Override
+	public T replace(T _newChild)
+	{
+		String uuid = _newChild.getID().getUUID();
+		int size = m_list.size();
+		for(int i = 0;i < size;i ++){
+			T n = m_list.get(i);
+			if(uuid.equals(n.getID().getUUID())){
+				//_newChildと同一なUUIDを見つけた
+				return m_list.set(i,_newChild);
+			}
+		}
+		//見つからなかった
+		return null;
+	}
+	
+	/**
+	 * このリストに新しく子供を追加します.
+	 * @param _n
+	 * @return 追加に成功した場合true
+	 */
+	public boolean add(T _n)
+	{
+		if(m_set.contains(_n.getID().getUUID())){
+			return false;
+		}
+		
+		m_set.add(_n.getID().getUUID());
+		m_list.add(_n);
+		return true;
+	}
+	
+	/**
+	 * _listに含まれている子供がすべてこのリストに含まれない場合にのみ、要素をすべて追加します。
+	 * @param _list
+	 * @return 追加に成功した場合true
+	 */
+	public boolean addAll(NodeChildren<T> _list)
+	{
+		if(Collections.disjoint(m_set,_list.getUUIDSet())){
+			//共通要素がない
+			m_set.addAll(_list.getUUIDSet());
+			m_list.addAll(_list.getList());
+		}
+		return false;
+	}
+	
+	/**
+	 * 指定されたNodeID
+	 * @param _id
+	 * @return 子供ノード
+	 */
+	public T get(String _uuid)
+	{
+		for(T n : m_list){
+			String uuid = n.getID().getUUID();
+			if(uuid.equals(_uuid)){
+				return n;
+			}
+		}
+		
+		return null;
+	}
+	
+	/**
+	 * 指定された_indexの場所に位置する子供を削除します
+	 * @param _index
+	 * @return 消される子供ノード
+	 */
+	public T get(int _index)
+	{
+		return m_list.get(_index);
+	}
+	
+	/**
+	 * 指定されたUUIDを持つ子どもを削除します
+	 * @param _id
+	 * @return 削除される子供ノード
+	 */
+	public T remove(String _uuid)
+	{
+		int size = m_list.size();
+		
+		for(int i = 0;i < size;i ++){
+			String uuid = m_list.get(i).getID().getUUID();
+			if(uuid.equals(_uuid)){
+				//NodeIDのUUIDが一致した
+				return m_list.remove(i);
+			}
+		}
+		
+		return null;
+	}
+	
+	/**
+	 * 指定された場所の子供ノードを削除します
+	 * @param _index
+	 * @return 削除された子供ノード
+	 */
+	public T remove(int _index)
+	{
+		return m_list.remove(_index);
+	}
+	
+	/**
+	 * このリストに指定されたUUIDを持つNodeがあるか確認します
+	 * @param _id
+	 * @return 存在する場合true
+	 */
+	public boolean contains(String _uuid)
+	{
+		return m_set.contains(_uuid);
+	}
+	
+	/**
+	 * 指定された二つのUUID(_uuid1,_uuid2)がリスト上に存在する場合、その二つの順番を入れ替えます
+	 * @param _uuid1 String
+	 * @param _uuid2 String
+	 * @return 成功した場合はtrue,NodeIDが見つからなかった場合はfalse
+	 */
+	public boolean swap(String _uuid1,String _uuid2)
+	{
+		/*
+		 * 二つのNodeIDの位置を求める
+		 */
+		int index1 = -1;
+		int index2 = -1;
+		
+		int size = m_list.size();
+		for(int i = 0;i < size && (index1 == -1 || index2 == 1);i ++){
+			String uuid = m_list.get(i).getID().getUUID();
+			if(uuid.equals(_uuid1)){
+				index1 = i;
+				continue;
+			}
+			
+			if(uuid.equals(_uuid2)){
+				index2 = i;
+				continue;
+			}
+		}
+		
+		/*
+		 * Collection.swapを使って入れ替える
+		 */
+		if(index1 != -1 && index2 != -1){
+			Collections.swap(m_list,index1,index2);
+			return true;
+		}
+		
+		//NodeIDがリスト上になかった
+		return false;
+	}
+	
+	/**
+	 * 子供ノードのリストをクリアします
+	 */
+	public void clearChildren()
+	{
+		m_set.clear();
+		m_list.clear();
+	}
+	
+	@Override
+	public boolean equals(Object _o)
+	{
+		NodeChildrenImpl<T> list = (NodeChildrenImpl<T>)_o;
+		return m_list.equals(list.m_list);
+	}
+	
+	@Override
+	public int hashCode()
+	{
+		int result = 17;
+		result = 37*result + m_list.hashCode();
+		result = 37*result + m_set.hashCode();
+		return result;
+	}
+
+	@Override
+	public Map<ByteBuffer, ByteBuffer> asMap() {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public Set<ByteBuffer> getKeySet() {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public void put(ByteBuffer _name, ByteBuffer _value) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public void putAll(NodeAttributes _attrs) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public ByteBuffer get(ByteBuffer _name) {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public NodeAttributes getAll() {
+		// TODO Auto-generated method stub
+		return null;
+	}
+
+	@Override
+	public void remove(ByteBuffer _name) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public void removeAll(Set<ByteBuffer> _keySet) {
+		// TODO Auto-generated method stub
+		
+	}
+
+	@Override
+	public void clearAttributes() {
+		// TODO Auto-generated method stub
+		
+	}
+
+}
--- a/src/treecms/tree/util/NodePathFinder.java	Wed May 11 22:08:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,74 +0,0 @@
-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<Node>
-{
-	private Node m_root;
-	private Node m_target;
-	private List<Node> m_path;
-	
-	/**
-	 * コンストラクタです.コンストラクタが作成された時点でパスが検索されます.
-	 * @param _root 木構造のトップです.
-	 * @param _target パス検索の対象となるNodeです.
-	 */
-	public NodePathFinder(Node _root,Node _target) throws PathNotFoundException
-	{
-		m_root = _root;
-		m_target = _target;
-		List<Node> path = findPath(m_root,m_target);
-		m_path = Collections.unmodifiableList(path);
-	}
-
-	/**
-	 * パスまでのイテレータを返します.
-	 * イテレータはremoveメソッドをサポートしません.
-	 */
-	@Override
-	public Iterator<Node> iterator()
-	{
-		return m_path.iterator();
-	}
-	
-	/**
-	 * パスのリストを取得します.このパスのリストは編集できません.
-	 * @return パスまでのリスト
-	 */
-	public List<Node> list()
-	{
-		return m_path;
-	}
-
-	/**
-	 * _fromから_targetまでのパスを再帰的に取得します
-	 * @param _from 取得するパスの始まり
-	 * @param _target 取得するパスの終わり
-	 * @return _fromから_targetまでのリスト
-	 */
-	private LinkedList<Node> findPath(Node _from,Node _target)
-	{
-		if(_from.getID().isFamily(_target.getID())){
-			LinkedList<Node> path = new LinkedList<Node>();
-			path.addFirst(_from);
-			return path;
-		}
-		
-		for(Node child : _from.children()){
-			LinkedList<Node> path = findPath(child,_target);
-			if(path != null){
-				path.addFirst(_from);
-			}
-		}
-		
-		return null;
-	}
-}
--- a/src/treecms/tree/util/PathNotFoundException.java	Wed May 11 22:08:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,31 +0,0 @@
-package treecms.tree.util;
-
-import treecms.api.Node;
-
-/**
- * あるNodeからNodeまでのパスが検索したが見つからない場合に発生します. 
- * @author shoshi
- */
-public class PathNotFoundException extends Exception
-{
-	private static final long serialVersionUID = 6372927818478170944L;
-
-	/**
-	 * コンストラクタです.
-	 * @param _from 木構造のルートNode
-	 * @param _to 検索する対象のNode
-	 */
-	public PathNotFoundException(Node _from,Node _to)
-	{
-		super("Path Not Found from "+_from.getID()+" to "+_to.getID());
-	}
-	
-	/**
-	 * コンストラクタです。
-	 * @param _message メッセージ
-	 */
-	public PathNotFoundException(String _message)
-	{
-		super(_message);
-	}
-}
--- a/src/treecms/tree/util/Predicate.java	Wed May 11 22:08:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,8 +0,0 @@
-package treecms.tree.util;
-
-public interface Predicate<E>
-{
-	boolean evaluateGet(int index);
-	boolean evaluateAdd(int index,E _target);
-	boolean evaluateRemove(int index);
-}
--- a/src/treecms/tree/util/PredicatedList.java	Wed May 11 22:08:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,185 +0,0 @@
-package treecms.tree.util;
-
-import java.util.Collection;
-import java.util.Iterator;
-import java.util.List;
-import java.util.ListIterator;
-
-public class PredicatedList<E> implements List<E>
-{
-	private Predicate<E> m_predicate;
-	private List<E> m_list;
-	
-	public PredicatedList(List<E> _list,Predicate<E> _predicate)
-	{
-		if(_list == null || _predicate == null){
-			throw new NullPointerException();
-		}
-		
-		m_list = _list;
-		m_predicate = _predicate;
-	}
-
-	@Override
-	public boolean add(E _item)
-	{
-		if(m_predicate.evaluateAdd(_item)){
-			return m_list.add(_item);
-		}
-		return false;
-	}
-
-	@Override
-	public void add(int _index,E _item)
-	{
-		if(m_predicate.evaluateAdd(_index,_item)){
-			m_list.add(_index,_item);
-		}
-	}
-
-	@Override
-	public boolean addAll(Collection<? extends E> _c)
-	{
-		boolean eval = false;
-		for(E i : _c){
-			eval = m_predicate.evaluate(i);
-			if(!eval){
-				return false;
-			}
-		}
-		
-		return m_list.addAll(_c);
-	}
-
-	@Override
-	public boolean addAll(int _index, Collection<? extends E> _c)
-	{
-		boolean eval = false;
-		for(E i : _c){
-			eval = m_predicate.evaluate(i);
-			if(!eval){
-				return false;
-			}
-		}
-		
-		return m_list.addAll(_index,_c);
-	}
-
-	@Override
-	public void clear()
-	{
-		m_list.clear();
-	}
-
-	@Override
-	public boolean contains(Object _obj)
-	{
-		return m_list.contains(_obj);
-	}
-
-	@Override
-	public boolean containsAll(Collection<?> _c)
-	{
-		return m_list.containsAll(_c);
-	}
-
-	@Override
-	public E get(int _index)
-	{
-		return m_list.get(_index);
-	}
-
-	@Override
-	public int indexOf(Object _obj)
-	{
-		return m_list.indexOf(_obj);
-	}
-
-	@Override
-	public boolean isEmpty()
-	{
-		return m_list.isEmpty();
-	}
-
-	@Override
-	public Iterator<E> iterator()
-	{
-		return m_list.iterator();
-	}
-
-	@Override
-	public int lastIndexOf(Object _obj)
-	{
-		return m_list.lastIndexOf(_obj);
-	}
-
-	@Override
-	public ListIterator<E> listIterator()
-	{
-		return m_list.listIterator();
-	}
-
-	@Override
-	public ListIterator<E> listIterator(int _index)
-	{
-		return m_list.listIterator(_index);
-	}
-
-	@Override
-	public boolean remove(Object _obj)
-	{
-		return m_list.remove(_obj);
-	}
-
-	@Override
-	public E remove(int _index)
-	{
-		return m_list.remove(_index);
-	}
-
-	@Override
-	public boolean removeAll(Collection<?> _c)
-	{
-		return m_list.removeAll(_c);
-	}
-
-	@Override
-	public boolean retainAll(Collection<?> _c)
-	{
-		return m_list.retainAll(_c);
-	}
-
-	@Override
-	public E set(int _index,E _element)
-	{
-		if(m_predicate.evaluate(_element)){
-			
-		}
-		return null;
-	}
-
-	@Override
-	public int size() {
-		// TODO Auto-generated method stub
-		return 0;
-	}
-
-	@Override
-	public List<E> subList(int fromIndex, int toIndex) {
-		// TODO Auto-generated method stub
-		return null;
-	}
-
-	@Override
-	public Object[] toArray() {
-		// TODO Auto-generated method stub
-		return null;
-	}
-
-	@Override
-	public <T> T[] toArray(T[] a) {
-		// TODO Auto-generated method stub
-		return null;
-	}
-
-}
--- a/src/treecms/tree/util/PreorderTreewalker.java	Wed May 11 22:08:20 2011 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,99 +0,0 @@
-package treecms.tree.util;
-
-import java.util.Iterator;
-import java.util.Stack;
-import treecms.api.Node;
-
-/**
- * 順序付き深さ優先探索で木構造を走査します.また,走査したイテレータを返します.
- * @author shoshi
- */
-public class PreorderTreewalker implements Iterable<Node>
-{
-	private Node m_root;
-	
-	/**
-	 * コンストラクタです.
-	 * @param _root 木構造のルートノード
-	 */
-	public PreorderTreewalker(Node _root)
-	{
-		m_root = _root;
-	}
-	
-	
-	/**
-	 * イテレータを返します.
-	 * @return 順序付き深さ優先探索でのイテレータ
-	 */
-	@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.children().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.children().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;
-		}
-	}
-}