--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/TraverserTest.java	Fri Feb 01 00:55:02 2013 +0900
@@ -0,0 +1,112 @@
+package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverse;
+
+import java.nio.ByteBuffer;
+import org.junit.Assert;
+
+import fj.data.List;
+
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TraversableNodeWrapper;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.ClonableDefaultNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultEvaluator;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.Direction;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.Traversal;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.Traverser;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
+import junit.framework.TestCase;
+
+public abstract class TraverserTest extends TestCase
+{
+	public abstract Traverser instance();
+	
+	public void testTraverse()
+	{
+		int maxHeight = 3;
+		ClonableDefaultNode root = createTree(0,0,maxHeight,new DefaultNodePath());
+		
+		TraversableNodeWrapper<ClonableDefaultNode> traversable = new TraversableNodeWrapper<ClonableDefaultNode>(root);
+		Traverser traverser = instance();
+	
+		// generate all pattern.
+		List<DefaultNodePath> paths = generatePathPattern(new DefaultNodePath(),0,maxHeight);
+		
+		for(DefaultNodePath path : paths){
+			DefaultEvaluator evaluator = new DefaultEvaluator(path);
+			Either<Error,Traversal<TraversableNodeWrapper<ClonableDefaultNode>>> ret = traverser.traverse(traversable,evaluator);
+			if(ret.isA()){
+				Assert.fail();
+			}
+			
+			Traversal<TraversableNodeWrapper<ClonableDefaultNode>> traversal = ret.b();
+			TraversableNodeWrapper<ClonableDefaultNode> target = traversal.destination();
+			String expect = path.toString();
+			ByteBuffer value = target.getWrapped().getAttributes().get(key);
+			String actual = new String(value.array());
+			Assert.assertEquals(expect,actual);
+			
+			Pair<Integer,NodePath> pop;
+			NodePath estimatedPath = path;
+			DefaultNodePath currentPath = new DefaultNodePath();
+			
+			for(Direction<TraversableNodeWrapper<ClonableDefaultNode>> d : traversal){
+				pop = estimatedPath.pop();
+				estimatedPath = pop.right();
+				currentPath = currentPath.add(pop.left());
+				
+				value = d.getTarget().getWrapped().getAttributes().get(key);
+				String actualCurrentPathStr = new String(value.array());
+				String expectCurrentPathStr = currentPath.toString();
+				Assert.assertEquals(expectCurrentPathStr,actualCurrentPathStr);
+			}
+		}
+	}
+	
+	public List<DefaultNodePath> generatePathPattern(DefaultNodePath _cur,int _curHeight,int _maxHeight)
+	{
+		List<DefaultNodePath> paths = List.nil();
+		for(int p = 0;p <= _curHeight;p ++){
+			DefaultNodePath path = _cur.add(p);
+			if(_curHeight != _maxHeight - 1){
+				List<DefaultNodePath> newpaths = generatePathPattern(path,_curHeight+1,_maxHeight);
+				paths = paths.append(newpaths);
+			}
+			paths = paths.cons(path);
+		}
+		
+		return paths;
+	}
+	
+	public static String key = "KEY";
+	public static ByteBuffer value = ByteBuffer.wrap(key.getBytes());
+	public static ClonableDefaultNode factory = new ClonableDefaultNode(new DefaultNode());
+	
+	public ClonableDefaultNode createTree(int _curX,int _curY,int _maxHeight,NodePath _address)
+	{
+		ClonableDefaultNode parent = factory.createNewNode();
+		Either<Error,ClonableDefaultNode> either = parent.getAttributes().put(key,ByteBuffer.wrap(_address.toString().getBytes()));
+		if(either.isA()){
+			Assert.fail();
+		}
+		parent = either.b();
+		
+		if(_curY == _maxHeight){
+			return parent;
+		}
+		
+		for(int i = 0;i < _curY + 1;i ++){
+			ClonableDefaultNode ch = createTree(i,_curY + 1,_maxHeight,_address.add(i));
+			either = parent.getChildren().addNewChildAt(i,ch);
+			if(either.isA()){
+				Assert.fail();
+			}
+			
+			parent = either.b();
+		}
+		
+		return parent;
+	}
+}