# HG changeset patch
# User one
# Date 1419525834 -32400
# Node ID 3cd075a445bfb416c0d1e765f9cd3435686074ee
# Parent  6615db346bf5900968a38309d7f1b349a9e3f249
create parent index order o(n^2) → log(n)

diff -r 6615db346bf5 -r 3cd075a445bf src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTransactionManager.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTransactionManager.java	Wed Dec 24 14:33:17 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultTransactionManager.java	Fri Dec 26 01:43:54 2014 +0900
@@ -1,10 +1,6 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction;
 
-import java.io.BufferedWriter;
-import java.io.File;
-import java.io.FileWriter;
-import java.io.IOException;
-import java.io.PrintWriter;
+
 import java.util.Iterator;
 
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.persistent.ChangeList;
@@ -65,6 +61,7 @@
 
     IndexManager indexManager = new IndexManager(repository.getReservation());
     InterfaceTraverser traverser = new InterfaceTraverser(_newRoot, indexManager, false);
+    System.out.println("not use Index");
     traverser.createIndex();
     Index index = traverser.getIndex();
     ParentIndex parentIndex = traverser.getParentIndex();
diff -r 6615db346bf5 -r 3cd075a445bf src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java	Wed Dec 24 14:33:17 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java	Fri Dec 26 01:43:54 2014 +0900
@@ -1,5 +1,10 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser;
 
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.io.PrintWriter;
 import java.util.Iterator;
 
 import fj.data.List;
@@ -8,6 +13,7 @@
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.Index;
+import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexCreater;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexManager;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.ParentIndex;
 
@@ -56,18 +62,21 @@
 
   public void createIndex() {
 
-    final PathNodeIterator itNode = new PathNodeIterator(node);
-    for (; itNode.hasNext();) {
-      TreeNode targetNode = itNode.next();
-      if (parentUpdateFlag)
-        parentIndex = parentIndex.set(targetNode);
-      List<String> keys = targetNode.getAttributes().getKeys();
-      for (String key : keys) {
-        String value = targetNode.getAttributes().getString(key);
-        if (value != null)
-          index = index.set(key, value, targetNode);
-      }
+    long t1 = System.currentTimeMillis();
+    IndexCreater creater = new IndexCreater(node);
+    long t2 = System.currentTimeMillis();
+    System.out.println("createIndex time = " + (t2 - t1));
+    File file = new File("./time/createParentIndex");
+    try {
+      PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(file,true)));
+      pw.println((t2 - t1));
+      pw.close();
+    } catch (IOException e) {
+      // TODO Auto-generated catch block
+      e.printStackTrace();
     }
+    index = creater.getIndex();
+    parentIndex = creater.getParentIndex();
   }
 
   /**
@@ -235,7 +244,7 @@
                 index = index.set(key, value, targetNode);
             }
             if (parentUpdateFlag)
-              parentIndex = parentIndex.set(targetNode);
+      //        parentIndex = parentIndex.set(targetNode);
             if (query.condition(targetNode))
               return targetNode;
           }
@@ -291,7 +300,7 @@
                 index = index.set(key, value, targetNode);
             }
             if (parentUpdateFlag)
-              parentIndex = parentIndex.set(targetNode);
+     //         parentIndex = parentIndex.set(targetNode);
             if (query.condition(targetNode))
               return targetNode;
           }
diff -r 6615db346bf5 -r 3cd075a445bf src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java	Wed Dec 24 14:33:17 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java	Fri Dec 26 01:43:54 2014 +0900
@@ -34,7 +34,7 @@
 	@Override
 	public TreeNode next() {
 		TreeNode now = node;
-		if (node.getChildren().size() > 0) { // 
+		if (node.getChildren().size() > 0) { 
 			nodeStack.push(node);
 			children = node.getChildren();
 			node = children.at(0).b();
diff -r 6615db346bf5 -r 3cd075a445bf src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexCreater.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/IndexCreater.java	Fri Dec 26 01:43:54 2014 +0900
@@ -0,0 +1,82 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index;
+
+import java.util.Stack;
+
+import fj.data.List;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren;
+
+public class IndexCreater {
+
+  TreeNode root;
+  TreeNode node;
+  int childNumber;
+  private TreeNodeChildren children;
+  private Stack<TreeNode> nodeStack = new Stack<TreeNode>();
+  private Stack<Integer> searchStack = new Stack<Integer>();
+  ParentIndex parentIndex = new ParentIndex();
+  Index index = new Index();
+
+  public IndexCreater(TreeNode rootNode) {
+    this.root = rootNode;
+    this.node = rootNode;
+    while (node != null) {
+      TreeNode targetNode = node;
+      if (node.getChildren().size() > 0) {
+        nodeStack.push(node);
+        TreeNode parent = node;
+        children = node.getChildren();
+        node = children.at(0).b();
+        parentIndex.set(parent, node);
+        childNumber = 1;
+        searchStack.push(childNumber);
+      } else if (node == root) {
+        node = null; // no more node
+        children = null;
+        return ;
+      } else if (children != null && children.size() > childNumber) {
+        childNumber = searchStack.pop();
+        TreeNode parent = nodeStack.pop();
+        nodeStack.push(parent);
+        node = children.at(childNumber).b();
+        parentIndex.set(parent, node);
+        searchStack.push(++childNumber);
+      } else {
+        node = nodeStack.pop();
+        children = node.getChildren();
+        childNumber = searchStack.pop();
+        for (; children.size() == childNumber;) {
+          if (node == root) {
+            node = null; // no more node
+            children = null;
+            return ;
+          }
+          node = nodeStack.pop();
+          children = node.getChildren();
+          childNumber = searchStack.pop();
+        }
+        if (node != null && childNumber < children.size()) {
+          nodeStack.push(node);
+          TreeNode parent = node;
+          node = children.at(childNumber).b();
+          parentIndex.set(parent, node);
+          searchStack.push(++childNumber);
+        }
+      }
+      List<String> keys = targetNode.getAttributes().getKeys();
+      for (String key : keys) {
+        String value = targetNode.getAttributes().getString(key);
+        if (value != null)
+          index = index.set(key, value, targetNode);
+      }
+    }
+  }
+
+  public Index getIndex() {
+    return index;
+  }
+
+  public ParentIndex getParentIndex() {
+    return parentIndex;
+  }
+}
diff -r 6615db346bf5 -r 3cd075a445bf src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/ParentIndex.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/ParentIndex.java	Wed Dec 24 14:33:17 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/ParentIndex.java	Fri Dec 26 01:43:54 2014 +0900
@@ -41,12 +41,8 @@
     return null;
   }
 
-  public ParentIndex set(TreeNode parent) {
-    Iterator<TreeNode> childrenIterator = parent.getChildren().iterator();
-    for (; childrenIterator.hasNext();) {
-      TreeNode child = childrenIterator.next();
-      parentIndex = parentIndex.set(child, parent);
-    }
+  public ParentIndex set(TreeNode parent ,TreeNode child) {
+    parentIndex = parentIndex.set(child, parent);
     return this;
   }