changeset 145:72f454eb04ec

add parentIndex
author one
date Fri, 21 Nov 2014 08:11:24 +0900
parents ef183969bf31
children 371b6ddb78f2
files src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungle.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/App.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/ChangeSet.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultTreeEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/IndexTreeEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultChangeSet.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultJungleTreeEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTransactionManager.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/IndexJungleTreeEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/TransactionManager.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/util/TreeMapOrd.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/AddNewChildrenIndexEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DefaultIndexEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DeleteChildIndexEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DeleteIndexEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexEditor.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexManager.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/PutIndexEditor.java src/test/java/DefaultJungleTreeTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/GetOldTreeTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/functionaljava/FjTreeMapTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/AddChildrenIndexTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/AttributeIndexTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/DeleteChildrenIndexTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/IndexCommitTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/ParentIndexTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/query/SearchQueryTest.java
diffstat 31 files changed, 538 insertions(+), 305 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungle.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungle.java	Fri Nov 21 08:11:24 2014 +0900
@@ -14,15 +14,18 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.operations.TreeOperation;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultChangeSet;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeContext;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
+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 jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.TreeMapOrd;
 
 public class DefaultJungle implements Jungle
 {
@@ -30,10 +33,10 @@
 	private ConcurrentHashMap<String,JungleTree> trees;
 	private String uuid;
 	private TreeEditor editor;
-	
+	private Traverser traverser;
 	public static void main(String args[])
 	{
-		DefaultJungle j = new DefaultJungle(null,"hoge",new DefaultTreeEditor(new DefaultTraverser()));
+		DefaultJungle j = new DefaultJungle(null,"hoge",new DefaultTraverser());
 		JungleTree t = j.createNewTree("fuga");
 		
 		JungleTreeEditor e1 = t.getTreeEditor();
@@ -47,12 +50,13 @@
 		e1.success();
 	}
 	
-	public DefaultJungle(Journal journal,String uuid,TreeEditor editor)
+	public DefaultJungle(Journal journal,String uuid,Traverser traverser)
 	{
 		this.journal = new NullJournal();
 		this.trees = new ConcurrentHashMap<String,JungleTree>();
 		this.uuid = uuid;
-		this.editor = editor;
+		this.traverser = traverser;
+		this.editor = new DefaultTreeEditor(traverser);
 	}
 
 	@Override
@@ -83,9 +87,10 @@
 		
 		DefaultTreeNode root = new DefaultTreeNode();
 		TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index = TreeMap.empty(Ord.stringOrd);
-		ChangeSet set = new DefaultChangeSet(root,null,list,uuid,name,0,index);
+		TreeMap<TreeNode,TreeNode> parentIndex = TreeMap.empty(TreeMapOrd.treeNodeOrd);
+		ChangeSet set = new DefaultChangeSet(root,null,list,uuid,name,0,index,parentIndex);
 		DefaultTreeContext tc = new DefaultTreeContext(root,set);
-		JungleTree newTree = new DefaultJungleTree(tc,uuid,journal.getWriter(),editor);
+		JungleTree newTree = new DefaultJungleTree(tc,uuid,journal.getWriter(),editor,new IndexTreeEditor(traverser));
 		if(trees.putIfAbsent(name,newTree) != null){
 			return null;
 		}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,12 +1,12 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle;
 
 import fj.data.List;
-import fj.data.Option;
 import fj.data.TreeMap;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.persistent.ChangeListWriter;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.ChangeSet;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.operations.TreeOperation;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.AtomicReservableReference;
@@ -27,13 +27,15 @@
   private final AtomicReservableReference<TreeContext> repository;
   private final String uuid;
   private final ChangeListWriter writer;
-  private final TreeEditor editor;
-
-  public DefaultJungleTree(TreeContext tc, String uuid, ChangeListWriter writer, TreeEditor editor) {
+  private final TreeEditor treeEditor;
+  private final IndexTreeEditor indexTreeEditor;
+  
+  public DefaultJungleTree(TreeContext tc, String uuid, ChangeListWriter writer, TreeEditor editor, IndexTreeEditor indexTreeEditor) {
     this.repository = new AtomicReservableReference<TreeContext>(tc);
     this.uuid = uuid;
     this.writer = writer;
-    this.editor = editor;
+    this.treeEditor = editor;
+    this.indexTreeEditor = indexTreeEditor;
   }
 
   @Override
@@ -42,7 +44,8 @@
     DefaultTransactionManager txManager = new DefaultTransactionManager(writer, tc, repository, uuid);
     TreeNode root = tc.getTreeNode();
     TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index = getIndex();
-    return new DefaultJungleTreeEditor(root, txManager, editor, index);
+    TreeMap<TreeNode, TreeNode> parentIndex = getParentIndex();
+    return new DefaultJungleTreeEditor(root, txManager, treeEditor, index,parentIndex);
   }
 
   @Override
@@ -50,8 +53,16 @@
     TreeContext tc = repository.get();
     DefaultTransactionManager txManager = new DefaultTransactionManager(writer, tc, repository, uuid);
     TreeNode root = tc.getTreeNode();
-    TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = getIndex();
-    return new IndexJungleTreeEditor(root, txManager, editor, newIndex);
+    TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index = getIndex();
+    TreeMap<TreeNode, TreeNode> parentIndex = getParentIndex();
+    return new IndexJungleTreeEditor(root, txManager, indexTreeEditor, index, parentIndex);
+  }
+
+  @Override
+  public TreeMap<TreeNode, TreeNode> getParentIndex() {
+    TreeContext tc = repository.get();
+    ChangeSet cs = tc.getChangeSet();
+    return cs.getParentIndex();
   }
 
   @Override
@@ -112,7 +123,7 @@
     
     TreeContext oldTc = new DefaultTreeContext(root, cs);
     String oldTreeUuid = uuid + revision;
-    JungleTree oldTree = new DefaultJungleTree(oldTc,oldTreeUuid,writer,editor);
+    JungleTree oldTree = new DefaultJungleTree(oldTc,oldTreeUuid,writer,treeEditor,indexTreeEditor);
     return DefaultEither.newB(oldTree);
   }
   
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java	Fri Nov 21 08:11:24 2014 +0900
@@ -19,6 +19,7 @@
 	public JungleTreeEditor getLocalTreeEditor();
 	public TreeNode getRootNode();
 	public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex();
+	public TreeMap<TreeNode,TreeNode> getParentIndex();
 	public IndexJungleTreeEditor getIndexTreeEditor();
 	public Iterable<TreeOperation> getLog();
   public long revision();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/App.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/App.java	Fri Nov 21 08:11:24 2014 +0900
@@ -7,6 +7,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either;
@@ -20,7 +21,7 @@
 {
     public static void main( String[] args )
     {
-    	DefaultJungle jungle = new DefaultJungle(null,"sample",new DefaultTreeEditor(new DefaultTraverser()));
+    	DefaultJungle jungle = new DefaultJungle(null,"sample", new DefaultTraverser());
     	jungle.createNewTree("hoge");
     	JungleTree tree = jungle.getTreeByName("hoge");
     	JungleTreeEditor editor = tree.getTreeEditor();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/ChangeSet.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/ChangeSet.java	Fri Nov 21 08:11:24 2014 +0900
@@ -23,4 +23,5 @@
 	
 	public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex();
 	public Iterable<TreeOperation> getOperations();
+  public TreeMap<TreeNode, TreeNode> getParentIndex();
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultTreeEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultTreeEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -16,7 +16,6 @@
 public class DefaultTreeEditor implements TreeEditor
 {
 	private final Traverser traverser;
-	
 	public DefaultTreeEditor(Traverser traverser)
 	{
 		this.traverser = traverser;
@@ -50,7 +49,6 @@
 		// target
 		Direction<TreeNode> targetDirection = path.head();
 		TreeNode target = targetDirection.getTarget();
-		//EditableNodeWrapper<T> wrapper = new EditableNodeWrapper<T>(target);
 		Either<Error,LoggingNode> either = editor.edit(target);
 		if(either.isA()){
 			return DefaultEither.newA(either.a());
@@ -61,9 +59,12 @@
 		// top
 		int pos = targetDirection.getPosition();
 		TreeNode child = newWrap.getWrap();
+	
+		
 		for(Direction<TreeNode> parentDirection : path.tail()){
+		  
 			TreeNodeChildren chs =  parentDirection.getTarget().getChildren();
-					
+			
 			Either<Error,TreeNode> ret = chs.replaceNode(pos,child);
 			if(ret.isA()){
 				return DefaultEither.newA(ret.a());
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/IndexTreeEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -0,0 +1,116 @@
+package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl;
+
+
+import java.util.Iterator;
+
+import fj.data.List;
+import fj.data.TreeMap;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.LoggingNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.trasnformer.NodeEditor;
+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.DefaultEither;
+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;
+
+public class IndexTreeEditor {
+
+  private final Traverser traverser;
+
+  
+  public IndexTreeEditor(Traverser traverser)
+  {
+    this.traverser = traverser;
+  }
+  
+  
+  public Either<Error,Pair<LoggingNode, TreeMap<TreeNode, TreeNode>>> edit(TreeNode root,NodePath path,NodeEditor editor,TreeMap<TreeNode, TreeNode> parentIndex)
+  {
+    DefaultEvaluator e = new DefaultEvaluator(path);
+    Either<Error, Traversal> either = traverser.traverse(root,e);
+    
+    if(either.isA()){
+      return DefaultEither.newA(either.a());
+    }
+    
+    Traversal t = either.b();
+    Either<Error,Pair<LoggingNode, TreeMap<TreeNode, TreeNode>>> ret = clone(t,editor,parentIndex);
+    
+    return ret;
+  }
+  
+  private Either<Error,Pair<LoggingNode, TreeMap<TreeNode, TreeNode>>> clone(Traversal t,NodeEditor editor , TreeMap<TreeNode, TreeNode> parentIndex)
+  {
+    // copying nodes from bottom to root
+    TreeMap<TreeNode, TreeNode> newParentIndex = parentIndex;
+    List<Direction<TreeNode>> path = List.nil();
+    for (Direction<TreeNode> direction : t) {
+      path = path.cons(direction);
+    }
+
+    // target
+    Direction<TreeNode> targetDirection = path.head();
+    TreeNode target = targetDirection.getTarget();
+    Iterator<TreeNode> targetDeleteChildren = target.getChildren().iterator();
+    
+    for (;targetDeleteChildren.hasNext();) {
+      TreeNode targetDeleteChild = targetDeleteChildren.next();
+      newParentIndex = newParentIndex.delete(targetDeleteChild);
+    }
+    
+    
+    Either<Error, LoggingNode> either = editor.edit(target);
+    if (either.isA()) {
+      return DefaultEither.newA(either.a());
+    }
+
+    LoggingNode newWrap = either.b();
+
+    // top
+    int pos = targetDirection.getPosition();
+    TreeNode child = newWrap.getWrap();
+    Iterator<TreeNode> targetPutChildren = child.getChildren().iterator();
+
+    for (; targetPutChildren.hasNext();) {
+      TreeNode targetPutChild = targetPutChildren.next();
+      newParentIndex = newParentIndex.set(targetPutChild, child);
+    }
+
+    for (Direction<TreeNode> parentDirection : path.tail()) {
+
+      TreeNodeChildren chs = parentDirection.getTarget().getChildren();
+      
+      Iterator<TreeNode> deleteParentIndexChildren = chs.iterator();
+      for (;deleteParentIndexChildren.hasNext();) {
+        TreeNode deleteParentIndexChild = deleteParentIndexChildren.next();
+        newParentIndex = newParentIndex.delete(deleteParentIndexChild);
+      }
+      
+      Either<Error, TreeNode> ret = chs.replaceNode(pos, child);
+      if (ret.isA()) {
+        return DefaultEither.newA(ret.a());
+      }
+      
+      TreeNode newParent = ret.b();
+       Iterator<TreeNode> putParentIndexChildren = newParent.getChildren().iterator();
+      
+      for (;putParentIndexChildren.hasNext();) {
+        TreeNode putParentIndexChild = putParentIndexChildren.next();
+        newParentIndex = newParentIndex.set(putParentIndexChild, newParent);
+      }
+      
+      child = newParent;
+      pos = parentDirection.getPosition();
+    }
+
+    TreeNode newRoot = child;
+    LoggingNode logNode = editor.wrap(newRoot, newWrap.getOperationLog());
+    Pair<LoggingNode, TreeMap<TreeNode, TreeNode>> pair = new Pair<LoggingNode, TreeMap<TreeNode, TreeNode>>(logNode,newParentIndex);
+    return DefaultEither.newB(pair);
+  }
+   
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNode.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/TreeNode.java	Fri Nov 21 08:11:24 2014 +0900
@@ -2,7 +2,7 @@
 
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.core.AttributesContainer;
 
-public interface TreeNode extends AttributesContainer
+public interface TreeNode extends AttributesContainer 
 {
 	public TreeNodeChildren getChildren();
 	
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultChangeSet.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultChangeSet.java	Fri Nov 21 08:11:24 2014 +0900
@@ -18,8 +18,9 @@
 	private final String treeName;
 	private final long revision; 
 	private final TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
+	private final TreeMap<TreeNode,TreeNode> parentIndex;
 	
-	public DefaultChangeSet(TreeNode _node,ChangeSet _prev,ChangeList _log,String _uuid, String _treeName, long _revision, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index)
+	public DefaultChangeSet(TreeNode _node,ChangeSet _prev,ChangeList _log,String _uuid, String _treeName, long _revision, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode,TreeNode> parentIndex)
 	{
 		this.root = _node;
 		this.previous = _prev;
@@ -28,6 +29,7 @@
 		this.treeName = _treeName;
 		this.revision = _revision;
 		this.index = index;
+		this.parentIndex = parentIndex;
 	}
 	
 
@@ -78,4 +80,10 @@
 		return index;
 	}
 
+
+  @Override
+  public TreeMap<TreeNode, TreeNode> getParentIndex() {
+    return parentIndex;
+  }
+
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultJungleTreeEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultJungleTreeEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -33,25 +33,28 @@
 	private final TreeEditor editor;
 	private final TreeOperationLog log;
 	private final TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
+	private final TreeMap<TreeNode,TreeNode> parentIndex;
+	
 //	public DefaultJungleTreeEditor(TreeNode root)
 //	{
 //	    this(root,txManager,_editor,new DefaultTreeOperationLog());
 //	}
 
-	public DefaultJungleTreeEditor(TreeNode _root,TransactionManager _txManager,TreeEditor _editor,	TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index)
+	public DefaultJungleTreeEditor(TreeNode _root,TransactionManager _txManager,TreeEditor _editor,	TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode,TreeNode> parentIndex)
 	{
-		this(_root,_txManager,_editor,new DefaultTreeOperationLog(),index);
+		this(_root,_txManager,_editor,new DefaultTreeOperationLog(),index,parentIndex);
 	}
 	
 	
 	
-	public DefaultJungleTreeEditor(TreeNode newNode,TransactionManager _txManager,TreeEditor _editor,TreeOperationLog _log,	TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index)
+	public DefaultJungleTreeEditor(TreeNode newNode,TransactionManager _txManager,TreeEditor _editor,TreeOperationLog _log,	TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode,TreeNode> parentIndex)
 	{
 		this.root = newNode;
 		this.txManager = _txManager;
 		this.editor = _editor;
 		this.log = _log;
 		this.index = index;
+		this.parentIndex = parentIndex;
 	}
 	
 	private Either<Error,JungleTreeEditor> _edit(final NodePath _path,NodeEditor _e)
@@ -76,7 +79,7 @@
 		DefaultTreeOperationLog treeOperationLog = new DefaultTreeOperationLog(iterable,newLog.length());
 		TreeOperationLog newTreeOpLog = log.append(treeOperationLog);
 		
-		JungleTreeEditor newEditor = new DefaultJungleTreeEditor(newNode,txManager,editor,newTreeOpLog,index);
+		JungleTreeEditor newEditor = new DefaultJungleTreeEditor(newNode,txManager,editor,newTreeOpLog,index,parentIndex);
 		return DefaultEither.newB(newEditor);
 	}
 	
@@ -117,13 +120,13 @@
 	@Override
 	public Either<Error,JungleTreeEditor> success()
 	{
-		Either<Error,TransactionManager> either = txManager.commit(root,log,index);
+		Either<Error,TransactionManager> either = txManager.commit(root,log,index,parentIndex);
 		if(either.isA()){
 			return DefaultEither.newA(either.a());
 		}
 		
 		TransactionManager newTxManager = either.b();
-		JungleTreeEditor newTreeEditor = new DefaultJungleTreeEditor(root,newTxManager,editor,index);
+		JungleTreeEditor newTreeEditor = new DefaultJungleTreeEditor(root,newTxManager,editor,index,parentIndex);
 		
 		return DefaultEither.newB(newTreeEditor);
 	}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTransactionManager.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTransactionManager.java	Fri Nov 21 08:11:24 2014 +0900
@@ -36,7 +36,7 @@
 	}
 	
 	@Override
-	public Either<Error,TransactionManager> commit(TreeNode _newRoot,final TreeOperationLog _log, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index)
+	public Either<Error,TransactionManager> commit(TreeNode _newRoot,final TreeOperationLog _log, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode,TreeNode> parentIndex)
 	{
 		ChangeSet cs = tip.getChangeSet();
 		long currentRevision = cs.revision();
@@ -59,7 +59,7 @@
 
 		};
 		
-		DefaultChangeSet newCs = new DefaultChangeSet(_newRoot,cs,list,uuid, _treeName, nextRevision,index);
+		DefaultChangeSet newCs = new DefaultChangeSet(_newRoot,cs,list,uuid, _treeName, nextRevision,index,parentIndex);
 		DefaultTreeContext newContext = new DefaultTreeContext(_newRoot,newCs);
 		
 		@SuppressWarnings("rawtypes")
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNode.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTreeNode.java	Fri Nov 21 08:11:24 2014 +0900
@@ -50,5 +50,6 @@
 	{
 		return new DefaultTreeNode(children,attrs);
 	}
+
 	
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/IndexJungleTreeEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/IndexJungleTreeEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -6,7 +6,7 @@
 import fj.data.TreeMap;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.DefaultTreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.LoggingNode;
@@ -32,150 +32,134 @@
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexEditor;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.PutIndexEditor;
 
-public class IndexJungleTreeEditor implements JungleTreeEditor
-{
-	private final TransactionManager txManager;
-	private final TreeNode root;
-	private final TreeEditor editor;
-	private final TreeOperationLog log;
-	private TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
-	
-//	public DefaultJungleTreeEditor(TreeNode root)
-//	{
-//	    this(root,txManager,_editor,new DefaultTreeOperationLog());
-//	}
+public class IndexJungleTreeEditor implements JungleTreeEditor {
+  private final TransactionManager txManager;
+  private final TreeNode root;
+  private final IndexTreeEditor editor;
+  private final TreeOperationLog log;
+  private TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
+  private TreeMap<TreeNode, TreeNode> parentIndex;
+
+  public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex() {
+    return index;
+  }
+
+
 
-	public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex() {
-		return index;
-	}
+  public IndexJungleTreeEditor(TreeNode _root, TransactionManager _txManager, IndexTreeEditor treeEditor,
+      TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode, TreeNode> parentIndex) {
+    this(_root, _txManager, treeEditor, new DefaultTreeOperationLog(), index,parentIndex);
+  }
 
-	public void setIndex(
-			TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
-		this.index = index;
-	}
+  public IndexJungleTreeEditor(TreeNode newNode, TransactionManager _txManager, IndexTreeEditor _editor,
+      TreeOperationLog _log, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode, TreeNode> parentIndex) {
+    this.root = newNode;
+    this.txManager = _txManager;
+    this.editor = _editor;
+    this.log = _log;
+    this.index = index;
+    this.parentIndex = parentIndex;
+  }
 
-	public IndexJungleTreeEditor(TreeNode _root,TransactionManager _txManager,TreeEditor _editor, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index)
-	{
-		this(_root,_txManager,_editor,new DefaultTreeOperationLog(), index);
-	}
-	
-	public IndexJungleTreeEditor(TreeNode newNode,TransactionManager _txManager,TreeEditor _editor,TreeOperationLog _log, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index)
-	{
-		this.root = newNode;
-		this.txManager = _txManager;
-		this.editor = _editor;
-		this.log = _log;
-		this.index = index;
-	}
-	
-	private Either<Error,IndexJungleTreeEditor> _edit(final NodePath _path,NodeEditor _e, IndexEditor indexEditor)
-	{
-		Either<Error,LoggingNode> either = editor.edit(root,_path,_e);
-		if(either.isA()){
-			return DefaultEither.newA(either.a());
-		}
-		
-		LoggingNode newLogging = either.b();
-		OperationLog newLog = newLogging.getOperationLog();
-		TreeNode newNode = newLogging.getWrap();
-		
-		IterableConverter.Converter<TreeOperation,NodeOperation> converter = new IterableConverter.Converter<TreeOperation,NodeOperation>(){
-			@Override
-			public TreeOperation conv(NodeOperation _b){
-				return new DefaultTreeOperation(_path,_b);
-			}
-		};
-		
-		Iterable<TreeOperation> iterable = new IterableConverter<TreeOperation,NodeOperation>(newLog,converter);
-		DefaultTreeOperationLog treeOperationLog = new DefaultTreeOperationLog(iterable,newLog.length());
-		TreeOperationLog newTreeOpLog = log.append(treeOperationLog);
-		
-		Either<Error, IndexJungleTreeEditor> newEither = indexEditor.edit(newNode,txManager,editor,newTreeOpLog, index);
-		return newEither;
-	}
-	
-	@Override
-	public Either<Error,JungleTreeEditor> addNewChildAt(NodePath _path, int _pos)
-	{
-		AppendChildAt appendChildAt = new AppendChildAt(_pos);
-		AddNewChildrenIndexEditor indexEditor = new AddNewChildrenIndexEditor(_pos, _path);
-		Either<Error,IndexJungleTreeEditor> either = _edit(_path,appendChildAt,indexEditor);
-		Either<Error,JungleTreeEditor> newEither = DefaultEither.newB(either.b());
-		return newEither;
-	}
+  
+  public Either<Error, IndexJungleTreeEditor> _edit(final NodePath _path, NodeEditor _e, IndexEditor indexEditor) {
+    Either<Error,Pair<LoggingNode, TreeMap<TreeNode, TreeNode>>> either = editor.edit(root, _path, _e,parentIndex);
+    if (either.isA()) {
+      return DefaultEither.newA(either.a());
+    }
+
+    LoggingNode newLogging = either.b().left();
+    TreeMap<TreeNode,TreeNode> newParentIndex = either.b().right();
+    OperationLog newLog = newLogging.getOperationLog();
+    TreeNode newNode = newLogging.getWrap();
+
+    IterableConverter.Converter<TreeOperation, NodeOperation> converter = new IterableConverter.Converter<TreeOperation, NodeOperation>() {
+      @Override
+      public TreeOperation conv(NodeOperation _b) {
+        return new DefaultTreeOperation(_path, _b);
+      }
+    };
+
+    Iterable<TreeOperation> iterable = new IterableConverter<TreeOperation, NodeOperation>(newLog, converter);
+    DefaultTreeOperationLog treeOperationLog = new DefaultTreeOperationLog(iterable, newLog.length());
+    TreeOperationLog newTreeOpLog = log.append(treeOperationLog);
+    Either<Error, IndexJungleTreeEditor> newEither = indexEditor.edit(newNode, txManager, editor, newTreeOpLog, index, newParentIndex);
+    return newEither;
+  }
+
+  @Override
+  public Either<Error, JungleTreeEditor> addNewChildAt(NodePath _path, int _pos) {
+    AppendChildAt appendChildAt = new AppendChildAt(_pos);
+    AddNewChildrenIndexEditor indexEditor = new AddNewChildrenIndexEditor(_pos, _path);
+    Either<Error, IndexJungleTreeEditor> either = _edit(_path, appendChildAt, indexEditor);
+    Either<Error, JungleTreeEditor> newEither = DefaultEither.newB(either.b());
+    return newEither;
+  }
 
-	@Override
-	public Either<Error,JungleTreeEditor> deleteChildAt(NodePath _path, int _pos)
-	{
-		DeleteChildAt deleteChildAt = new DeleteChildAt(_pos);
-		DeleteChildIndexEditor indexEditor = new DeleteChildIndexEditor(_pos, _path);
-		Either<Error,IndexJungleTreeEditor> either = _edit(_path,deleteChildAt, indexEditor);
-		JungleTreeEditor editor = either.b();
-		Either<Error,JungleTreeEditor> newEither = DefaultEither.newB(editor);
-		return newEither;
-	}
+  @Override
+  public Either<Error, JungleTreeEditor> deleteChildAt(NodePath _path, int _pos) {
+    DeleteChildAt deleteChildAt = new DeleteChildAt(_pos);
+    DeleteChildIndexEditor indexEditor = new DeleteChildIndexEditor(_pos, _path);
+    Either<Error, IndexJungleTreeEditor> either = _edit(_path, deleteChildAt, indexEditor);
+    JungleTreeEditor editor = either.b();
+    Either<Error, JungleTreeEditor> newEither = DefaultEither.newB(editor);
+    return newEither;
+  }
 
-	@Override
-	public Either<Error,JungleTreeEditor> putAttribute(NodePath _path,String _key,ByteBuffer _value)
-	{
-		PutAttribute putAttribute = new PutAttribute(_key,_value);
-		PutIndexEditor indexEditor = new PutIndexEditor(_key,_value,_path);
-		Either<Error,IndexJungleTreeEditor> either = _edit(_path,putAttribute,indexEditor);
-		JungleTreeEditor editor = either.b();
-		Either<Error,JungleTreeEditor> newEither = DefaultEither.newB(editor);
-		return newEither;
-	}
+  @Override
+  public Either<Error, JungleTreeEditor> putAttribute(NodePath _path, String _key, ByteBuffer _value) {
+    PutAttribute putAttribute = new PutAttribute(_key, _value);
+    PutIndexEditor indexEditor = new PutIndexEditor(_key, _value, _path);
+    Either<Error, IndexJungleTreeEditor> either = _edit(_path, putAttribute, indexEditor);
+    JungleTreeEditor editor = either.b();
+    Either<Error, JungleTreeEditor> newEither = DefaultEither.newB(editor);
+    return newEither;
+  }
 
-	@Override
-	public Either<Error,JungleTreeEditor> deleteAttribute(NodePath _path, String _key)
-	{
-		DeleteAttribute deleteAttribute = new DeleteAttribute(_key);
-		DeleteIndexEditor indexEditor = new DeleteIndexEditor(_key,_path,root);
-		Either<Error,IndexJungleTreeEditor> either = _edit(_path,deleteAttribute,indexEditor);
-		Either<Error,JungleTreeEditor> newEither = DefaultEither.newB(either.b());
-		return newEither;
-	}
+  @Override
+  public Either<Error, JungleTreeEditor> deleteAttribute(NodePath _path, String _key) {
+    DeleteAttribute deleteAttribute = new DeleteAttribute(_key);
+    DeleteIndexEditor indexEditor = new DeleteIndexEditor(_key, _path, root);
+    Either<Error, IndexJungleTreeEditor> either = _edit(_path, deleteAttribute, indexEditor);
+    Either<Error, JungleTreeEditor> newEither = DefaultEither.newB(either.b());
+    return newEither;
+  }
 
-	@Override
-	public Either<Error,JungleTreeEditor> edit(NodePath _path,NodeEditor _editor)
-	{
-		DefaultIndexEditor indexEditor = new DefaultIndexEditor();
-		Either<Error,IndexJungleTreeEditor> either = _edit(_path,_editor,indexEditor);
-		JungleTreeEditor editor = either.b();
-		Either<Error,JungleTreeEditor> newEither = DefaultEither.newB(editor);
-		return newEither;
-	}
+  @Override
+  public Either<Error, JungleTreeEditor> edit(NodePath _path, NodeEditor _editor) {
+    DefaultIndexEditor indexEditor = new DefaultIndexEditor();
+    Either<Error, IndexJungleTreeEditor> either = _edit(_path, _editor, indexEditor);
+    JungleTreeEditor editor = either.b();
+    Either<Error, JungleTreeEditor> newEither = DefaultEither.newB(editor);
+    return newEither;
+  }
+
+  @Override
+  public Either<Error, JungleTreeEditor> success() {
+    Either<Error, TransactionManager> either = txManager.commit(root, log, index,parentIndex);
+    if (either.isA()) {
+      return DefaultEither.newA(either.a());
+    }
+
+    TransactionManager newTxManager = either.b(); 
+    JungleTreeEditor newTreeEditor = new IndexJungleTreeEditor(root, newTxManager, editor, index,parentIndex);
 
-	@Override
-	public Either<Error,JungleTreeEditor> success()
-	{
-		Either<Error,TransactionManager> either = txManager.commit(root,log,index);
-		if(either.isA()){
-			return DefaultEither.newA(either.a());
-		}
-		
-		TransactionManager newTxManager = either.b();
-		JungleTreeEditor newTreeEditor = new DefaultJungleTreeEditor(root,newTxManager,editor,index);
-		
-		return DefaultEither.newB(newTreeEditor);
-	}
+    return DefaultEither.newB(newTreeEditor);
+  }
+
+  @Override
+  public String getID() {
+    return txManager.getUUID();
+  }
 
-	@Override
-	public String getID()
-	{
-		return txManager.getUUID();
-	}
+  @Override
+  public String getRevision() {
+    return Long.toString(txManager.getRevision());
+  }
 
-	@Override
-	public String getRevision()
-	{
-		return Long.toString(txManager.getRevision());
-	}
+  @Override
+  public TreeNode getRoot() {
+    return root;
+  }
 
-	@Override
-	public TreeNode getRoot()
-	{
-		return root;
-	}
-	
 }
\ No newline at end of file
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/TransactionManager.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/TransactionManager.java	Fri Nov 21 08:11:24 2014 +0900
@@ -11,7 +11,7 @@
 
 public interface TransactionManager
 {
-	public Either<Error,TransactionManager> commit(TreeNode _newRoot,TreeOperationLog _log,	TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index);
+	public Either<Error,TransactionManager> commit(TreeNode _newRoot,TreeOperationLog _log,	TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,TreeMap<TreeNode,TreeNode> parentIndex);
 	public String getUUID();
 	public long getRevision();
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/util/TreeMapOrd.java	Fri Nov 21 08:11:24 2014 +0900
@@ -0,0 +1,25 @@
+package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util;
+
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
+import fj.F;
+import fj.Ord;
+import fj.P;
+import fj.P1;
+
+public class TreeMapOrd {
+
+  private TreeMapOrd(){
+    
+  }
+  
+  private static F<TreeNode, P1<String>> toP1 = new F<TreeNode, P1<String>> () {
+    @Override
+    public P1<String> f(TreeNode node) {
+      return P.p(node.toString());
+    }
+  };
+  
+  private static Ord<P1<String>> ord = Ord.p1Ord(Ord.stringOrd);
+  public static Ord<TreeNode> treeNodeOrd = ord.comap(toP1);
+  
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/AddNewChildrenIndexEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/AddNewChildrenIndexEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,17 +1,11 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index;
 
-import java.util.Iterator;
-
-import fj.F;
 import fj.Ord;
-import fj.P2;
 import fj.data.List;
-import fj.data.Option;
 import fj.data.TreeMap;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.TreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -23,101 +17,98 @@
 
 public class AddNewChildrenIndexEditor implements IndexEditor {
 
-	NodePath editNodePath;
+  NodePath editNodePath;
 
-	public AddNewChildrenIndexEditor(int pos, NodePath path) {
-		this.editNodePath = path.add(pos);
-	}
+  public AddNewChildrenIndexEditor(int pos, NodePath path) {
+    this.editNodePath = path.add(pos);
+  }
 
-	@Override
-	public Either<Error, IndexJungleTreeEditor> edit(
-			TreeNode root,
-			TransactionManager txManager,
-			TreeEditor editor,
-			TreeOperationLog log,
-			TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
+  @Override
+  public Either<Error, IndexJungleTreeEditor> edit(TreeNode root, TransactionManager txManager, IndexTreeEditor editor,
+      TreeOperationLog log, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,
+      TreeMap<TreeNode, TreeNode> parentIndex) {
 
-		TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = editIndex(index);
-		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root, txManager, editor, newIndex);
-		return DefaultEither.newB(newEditor);
-	}
+    TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = editIndex(index);
+    IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root, txManager, editor, newIndex,parentIndex);
+    return DefaultEither.newB(newEditor);
+  }
 
-	public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> editIndex(
-			TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
+  public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> editIndex(
+      TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
 
-		if (!index.isEmpty()) {
-			List<String> keyList = index.keys();
-			TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = TreeMap.empty(Ord.stringOrd);
-			TreeMap<String, List<Pair<TreeNode, NodePath>>> newInnerIndex = TreeMap.empty(Ord.stringOrd);
+    if (!index.isEmpty()) {
+      List<String> keyList = index.keys();
+      TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = TreeMap.empty(Ord.stringOrd);
+      TreeMap<String, List<Pair<TreeNode, NodePath>>> newInnerIndex = TreeMap.empty(Ord.stringOrd);
 
-			for (String indexKey : keyList) {
-				TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = index.get(indexKey).some();
-				List<String> innerIndexKeyList = innerIndex.keys();
+      for (String indexKey : keyList) {
+        TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = index.get(indexKey).some();
+        List<String> innerIndexKeyList = innerIndex.keys();
 
-				for (String innerIndexKey : innerIndexKeyList) {
-					List<Pair<TreeNode, NodePath>> pairList = innerIndex.get(innerIndexKey).some();
-					List<Pair<TreeNode, NodePath>> list = checkPath(pairList);
-					if (!list.isEmpty()){
-						//System.out.println(new String(list.head().left().getAttributes().get("KEY").array()));
-						newInnerIndex = newInnerIndex.set(innerIndexKey, list);
-					}
-				}
-				newIndex = newIndex.set(indexKey, newInnerIndex);
-			}
-			return newIndex;
-		} else {
-			return index;
-		}
-	}
+        for (String innerIndexKey : innerIndexKeyList) {
+          List<Pair<TreeNode, NodePath>> pairList = innerIndex.get(innerIndexKey).some();
+          List<Pair<TreeNode, NodePath>> list = checkPath(pairList);
+          if (!list.isEmpty()) {
+            // System.out.println(new
+            // String(list.head().left().getAttributes().get("KEY").array()));
+            newInnerIndex = newInnerIndex.set(innerIndexKey, list);
+          }
+        }
+        newIndex = newIndex.set(indexKey, newInnerIndex);
+      }
+      return newIndex;
+    } else {
+      return index;
+    }
+  }
+
+  public List<Pair<TreeNode, NodePath>> checkPath(List<Pair<TreeNode, NodePath>> pairList) {
 
-	public List<Pair<TreeNode, NodePath>> checkPath(List<Pair<TreeNode, NodePath>> pairList){
+    List<Pair<TreeNode, NodePath>> list = List.nil();
+    for (Pair<TreeNode, NodePath> pair : pairList) {
 
-		List<Pair<TreeNode, NodePath>> list = List.nil();
-		for (Pair<TreeNode, NodePath> pair : pairList) {
+      NodePath path = pair.right();
+      // System.out.println("oldPath = " + path.toString());
+      NodePath newPath = new DefaultNodePath();
 
-			NodePath path = pair.right();
-			//System.out.println("oldPath = " + path.toString());
-			NodePath newPath = new DefaultNodePath();
-			
-			
-			if (editNodePath.size() > path.size()) {
-				list = list.cons(pair);
-				continue;
-			}
+      if (editNodePath.size() > path.size()) {
+        list = list.cons(pair);
+        continue;
+      }
 
-			Pair<Integer, NodePath> editNodePathCopy = editNodePath.pop();
-			int loopCount = 0;
+      Pair<Integer, NodePath> editNodePathCopy = editNodePath.pop();
+      int loopCount = 0;
 
-			for (Integer pathInt : path) {
-				loopCount++;
+      for (Integer pathInt : path) {
+        loopCount++;
+
+        if (pathInt == -1)
+          continue;
 
-				if (pathInt == -1)
-					continue;
-				
-				if (editNodePathCopy.right().size() > 0) {
-					editNodePathCopy = editNodePathCopy.right().pop();
-					
-					if (loopCount == editNodePath.size() && editNodePathCopy.left() <= pathInt) {
-						newPath = newPath.add(pathInt + 1);
-						continue;
-					}
+        if (editNodePathCopy.right().size() > 0) {
+          editNodePathCopy = editNodePathCopy.right().pop();
+
+          if (loopCount == editNodePath.size() && editNodePathCopy.left() <= pathInt) {
+            newPath = newPath.add(pathInt + 1);
+            continue;
+          }
 
-					if (!(editNodePathCopy.left() == pathInt)) {
-						newPath = path;
-						break;
-					}
-				}
+          if (!(editNodePathCopy.left() == pathInt)) {
+            newPath = path;
+            break;
+          }
+        }
 
-				newPath = newPath.add(pathInt);
+        newPath = newPath.add(pathInt);
 
-			}
+      }
 
-			//System.out.println("newPath = " + newPath.toString());
-			Pair<TreeNode, NodePath> newPair = new Pair<TreeNode, NodePath>(pair.left(), newPath);
-			list = list.cons(newPair);
-		}
+      // System.out.println("newPath = " + newPath.toString());
+      Pair<TreeNode, NodePath> newPair = new Pair<TreeNode, NodePath>(pair.left(), newPath);
+      list = list.cons(newPair);
+    }
 
-		return list;
-	}
+    return list;
+  }
 
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DefaultIndexEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DefaultIndexEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -2,9 +2,8 @@
 
 import fj.data.List;
 import fj.data.TreeMap;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.TreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -17,8 +16,8 @@
 public class DefaultIndexEditor implements IndexEditor {
 
 	@Override
-	public Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager,TreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
-		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root,txManager,editor,log, index);
+	public Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager, IndexTreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index, TreeMap<TreeNode,TreeNode> parentIndex){
+		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root,txManager,editor,log, index, parentIndex);
 		Either<Error, IndexJungleTreeEditor> either = DefaultEither.newB(newEditor);
 		return either;
 	}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DeleteChildIndexEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DeleteChildIndexEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,17 +1,12 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index;
 
-import java.util.Iterator;
 
-import fj.F;
 import fj.Ord;
-import fj.P2;
 import fj.data.List;
-import fj.data.Option;
 import fj.data.TreeMap;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.TreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -30,15 +25,10 @@
 	}
 
 	@Override
-	public Either<Error, IndexJungleTreeEditor> edit(
-			TreeNode root,
-			TransactionManager txManager,
-			TreeEditor editor,
-			TreeOperationLog log,
-			TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
+	public Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager, IndexTreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index, TreeMap<TreeNode,TreeNode> parentIndex) {
 
 		TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = editIndex(index);
-		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root, txManager, editor, newIndex);
+		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root, txManager, editor, newIndex, parentIndex);
 		return DefaultEither.newB(newEditor);
 	}
 
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DeleteIndexEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/DeleteIndexEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -8,6 +8,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.TreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -32,12 +33,12 @@
 	}
 	
 	@Override
-	public Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager,TreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
+	public Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager, IndexTreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index, TreeMap<TreeNode,TreeNode> parentIndex) {
 		NodePath newPath = path.pop().right();
 		TreeNode target = getTarget(node, newPath);
 		String attribute = target.getAttributes().getString(key);
 		TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = editIndex(attribute, index);
-		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root,txManager,editor,log, newIndex);
+		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root,txManager,editor,log, newIndex, parentIndex);
 		Either<Error, IndexJungleTreeEditor> either = DefaultEither.newB(newEditor);
 		return either;
 	}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -5,6 +5,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.TreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -14,5 +15,5 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
 
 public interface IndexEditor {
-	Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager, TreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index);
+	Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager, IndexTreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index, TreeMap<TreeNode,TreeNode> parentIndex);
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexManager.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexManager.java	Fri Nov 21 08:11:24 2014 +0900
@@ -30,7 +30,8 @@
 		String uuid = cs.uuid();
 		String treeName = cs.getTreeName();
 		long revision = cs.revision();
-		DefaultChangeSet newCs = new DefaultChangeSet(root, prev, cl, uuid, treeName, revision, index);
+		TreeMap<TreeNode, TreeNode> parentIndex = cs.getParentIndex();
+ 		DefaultChangeSet newCs = new DefaultChangeSet(root, prev, cl, uuid, treeName, revision, index, parentIndex);
 		DefaultTreeContext newTs = new DefaultTreeContext(root, newCs);
 		reservation.set(newTs);
 	}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/PutIndexEditor.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/PutIndexEditor.java	Fri Nov 21 08:11:24 2014 +0900
@@ -8,6 +8,7 @@
 import fj.data.TreeMap;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.TreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.logger.TreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -36,11 +37,11 @@
 	}
 
 	@Override
-	public Either<Error, IndexJungleTreeEditor> edit(TreeNode root,TransactionManager txManager,TreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
+	public Either<Error, IndexJungleTreeEditor>edit(TreeNode root,TransactionManager txManager, IndexTreeEditor editor,TreeOperationLog log,TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index, TreeMap<TreeNode,TreeNode> parentIndex) {
 		NodePath newPath = path.pop().right();
 		TreeNode target = getTarget(root, newPath);
 		TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = editIndex(target, path, key, attribute,index);
-		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root,txManager,editor,log, newIndex);
+		IndexJungleTreeEditor newEditor = new IndexJungleTreeEditor(root,txManager,editor,log, newIndex, parentIndex);
 		Either<Error, IndexJungleTreeEditor> either = DefaultEither.newB(newEditor);
 		return either;
 	}
--- a/src/test/java/DefaultJungleTreeTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/DefaultJungleTreeTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -6,6 +6,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either;
@@ -18,7 +19,7 @@
 {
 	public Jungle instance()
 	{
-		Jungle j = new DefaultJungle(null,"hogehoge",new DefaultTreeEditor(new DefaultTraverser()));
+		Jungle j = new DefaultJungle(null,"hogehoge",new  DefaultTraverser());
 		return j;
 	}
 	
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/GetOldTreeTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/core/GetOldTreeTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,5 +1,6 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.core;
 
+
 import java.nio.ByteBuffer;
 
 import org.junit.Test;
@@ -10,6 +11,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either;
@@ -20,12 +22,12 @@
 
   @Test
   public void getOldTreeTest() {
-    Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTreeEditor(new DefaultTraverser()));
+    Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
     jungle.createNewTree("tree");
     JungleTree tree = jungle.getTreeByName("tree");
     JungleTreeEditor editor = tree.getTreeEditor();
     DefaultNodePath path = new DefaultNodePath();
-
+   
     for (int num = 0; num < 10; num++) {
       JungleTreeEditor addChildEditor = editor.addNewChildAt(path, num).b();
       JungleTreeEditor putAttributeEditor = addChildEditor.putAttribute(path.add(num), "test", ByteBuffer.wrap("tatsuki".getBytes())).b();
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/functionaljava/FjTreeMapTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/functionaljava/FjTreeMapTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,39 +1,65 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.functionaljava;
 
 
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
 
-import org.apache.commons.collections.map.StaticBucketMap;
 import org.junit.Assert;
 import org.junit.Test;
 
+
 import fj.F;
 import fj.Ord;
+import fj.P;
+import fj.P1;
 import fj.data.List;
 import fj.data.Option;
 import fj.data.TreeMap;
 
 public class FjTreeMapTest<A> {
-	
-	@Test
-	public void testTreeMap()	{
+
+  F<TreeNode, P1<String>> toP3 = new F<TreeNode, P1<String>> () {
+
+    @Override
+    public P1<String> f(TreeNode node) {
+      return P.p(node.toString());
+    }
+
+  };
+
+  
+  @Test
+  public void testTreeMap() {
 
-		List<Integer> list = List.nil();
-		list = list.cons(1).cons(2).cons(3);
-		System.out.println(list.toString());
-		list.length();
-		TreeMap<String,String> map = TreeMap.empty(Ord.stringOrd);
-		TreeMap<String, String> newMap = map.set("name","tatsuki");
-		Option<String> op = newMap.get("name");
-		if (op.isNone()) {
-			
-		}
-		String str = op.some();
-		
-		TreeMap<String, String> newMap2 = map.set("name","kanagawa");
-		String str2 = newMap2.get("name").some();
-		Assert.assertEquals(str,"tatsuki");
-		Assert.assertEquals(str2,"kanagawa");
-	}
-	
+     Ord<P1<String>> aaa = Ord.p1Ord(Ord.stringOrd);
+     Ord<TreeNode> test = aaa.comap(toP3);
+     TreeMap<TreeNode, TreeNode> treeMap = TreeMap.empty(test);
+     TreeNode node1 = new DefaultTreeNode();
+     TreeNode node2 = new DefaultTreeNode();
+     treeMap = treeMap.set(node1,node2);
+     System.out.println(node1.toString());
+     System.out.println(node2.toString());
+     System.out.println(node1.toString());
+     System.out.println(node2.toString());
+     Option<TreeNode> nodee = treeMap.get(node1);
+     TreeNode node = nodee.some();
+     System.out.println(node.toString());
+    List<Integer> list = List.nil();
+    list = list.cons(1).cons(2).cons(3);
+    System.out.println(list.toString());
+    list.length();
+    TreeMap<String, String> map = TreeMap.empty(Ord.stringOrd);
+    TreeMap<String, String> newMap = map.set("name", "tatsuki");
+    Option<String> op = newMap.get("name");
+    if (op.isNone()) {
+
+    }
+    String str = op.some();
+
+    TreeMap<String, String> newMap2 = map.set("name", "kanagawa");
+    String str2 = newMap2.get("name").some();
+    Assert.assertEquals(str, "tatsuki");
+    Assert.assertEquals(str2, "kanagawa");
+  }
 
 }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/AddChildrenIndexTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/AddChildrenIndexTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,5 +1,7 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.index;
 
+
+
 import java.nio.ByteBuffer;
 import java.util.Iterator;
 
@@ -16,6 +18,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -30,7 +33,7 @@
 
 	@Test
 	public void DeleteChildrenTest(){
-		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTreeEditor(new DefaultTraverser()));
+		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTraverser());
 		jungle.createNewTree("tree");
 		JungleTree tree = jungle.getTreeByName("tree");
 		createTree(tree);
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/AttributeIndexTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/AttributeIndexTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -1,5 +1,7 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.index;
 
+
+
 import java.nio.ByteBuffer;
 
 import org.junit.Test;
@@ -10,6 +12,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
@@ -24,7 +27,7 @@
 
 	@Test
 	public void PutAttributeIndexTest(){
-		DefaultJungle jungle = new DefaultJungle(null,"hoge",new DefaultTreeEditor(new DefaultTraverser()));
+		DefaultJungle jungle = new DefaultJungle(null,"hoge",new DefaultTraverser());
 		JungleTree tree = jungle.createNewTree("fuga");
 		IndexJungleTreeEditor editor = tree.getIndexTreeEditor();
 		TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> emptyIndex = editor.getIndex();
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/DeleteChildrenIndexTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/DeleteChildrenIndexTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -16,6 +16,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.IndexJungleTreeEditor;
@@ -30,7 +31,7 @@
 
 	@Test
 	public void DeleteChildrenTest(){
-		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTreeEditor(new DefaultTraverser()));
+		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTraverser());
 		jungle.createNewTree("tree");
 		JungleTree tree = jungle.getTreeByName("tree");
 		createTree(tree);
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/IndexCommitTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/IndexCommitTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -9,6 +9,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
@@ -20,7 +21,6 @@
 
 import java.nio.ByteBuffer;
 
-
 import org.junit.Test;
 
 import fj.data.List;
@@ -32,7 +32,7 @@
 	@Test
 	public void IndexCommitTest() throws InterruptedException {
 		
-		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTreeEditor(new DefaultTraverser()));
+		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTraverser());
 		jungle.createNewTree("tree");
 		JungleTree tree = jungle.getTreeByName("tree");
 		createTree(tree);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/index/ParentIndexTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -0,0 +1,55 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.index;
+
+import java.util.Iterator;
+
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.DefaultJungle;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.Jungle;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTree;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
+import junit.framework.Assert;
+
+import org.junit.Test;
+
+import fj.data.Option;
+import fj.data.TreeMap;
+
+public class ParentIndexTest {
+
+  @Test
+  public void testParentIndex() {
+    Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
+    jungle.createNewTree("tree");
+    JungleTree tree = jungle.getTreeByName("tree");
+    JungleTreeEditor editor = tree.getIndexTreeEditor();
+    DefaultNodePath path = new DefaultNodePath();
+    editor = editor.addNewChildAt(path, 0).b();
+    for (int num = 0; num < 5; num++) {
+      editor = editor.addNewChildAt(path.add(0), num).b().success().b();
+    }
+    TreeMap<TreeNode, TreeNode> parentIndex = tree.getParentIndex();
+
+    TreeNode node = tree.getRootNode();
+    for (int num = 0; node.getChildren().size() != 0; num++) {
+      Iterator<TreeNode> children = node.getChildren().iterator();
+      for (; children.hasNext();) {
+        TreeNode child = children.next();
+        TreeNode parent = parentIndex.get(child).some();
+        Assert.assertEquals(parent, node);
+      }
+      node = node.getChildren().at(num).b();
+    }
+
+    JungleTree oldTree = tree.getOldTree(tree.revision() - 1).b();
+    TreeNode oldRoot = oldTree.getRootNode();
+    TreeNode oldNode = oldRoot.getChildren().at(0).b();
+    Option<TreeNode> oldParentOp = parentIndex.get(oldNode);
+    Assert.assertTrue(oldParentOp.isNone());
+    TreeMap<TreeNode, TreeNode> oldTreeParentIndex = oldTree.getParentIndex();
+    oldParentOp = oldTreeParentIndex.get(oldNode);
+    Assert.assertTrue(oldParentOp.isSome());
+        
+  }
+}
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/query/SearchQueryTest.java	Thu Nov 13 22:04:14 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/tatsuki/query/SearchQueryTest.java	Fri Nov 21 08:11:24 2014 +0900
@@ -12,6 +12,7 @@
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultTreeEditor;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.IndexTreeEditor;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser;
@@ -32,7 +33,7 @@
 
 	@Test
 	public void SearchQueryTest() {
-		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTreeEditor(new DefaultTraverser()));
+		Jungle jungle = new DefaultJungle(null, "hogehoge",new DefaultTraverser());
 		jungle.createNewTree("tree");
 		JungleTree tree = jungle.getTreeByName("tree");
 		createTree(tree);