--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java	Sat Nov 22 15:25:09 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java	Tue Nov 25 17:52:41 2014 +0900
@@ -2,53 +2,101 @@
 
 import java.util.Iterator;
 
-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.store.NodePath;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator;
-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.util.Pair;
 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.IndexManager;
+import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.ParentIndex;
 
 public class InterfaceTraverser {
 
-  // InterfaceTraverser traverser;
   TreeNode node;
   Index index;
+  ParentIndex parentIndex;
+  boolean parentUpdateFlag;
   IndexManager indexManager;
+  boolean indexFlag;
 
-  public InterfaceTraverser(TreeNode _root, IndexManager indexManager) {
-    this.node = _root;
-    this.index = new Index();
-    this.indexManager = indexManager;
-  }
-
-  public InterfaceTraverser(TreeNode _root, Index  index,
-      IndexManager indexManager) {
+  public InterfaceTraverser(TreeNode _root, Index index, ParentIndex parentIndex, IndexManager indexManager,
+      boolean indexFlag) {
     this.node = _root;
     this.index = index;
     this.indexManager = indexManager;
-  }
-
-  public void commitIndex() {
-    indexManager.commit(index);
+    this.parentIndex = parentIndex;
+    if (parentIndex.isEmpty())
+      parentUpdateFlag = true;
+    else
+      parentUpdateFlag = false;
+    this.indexFlag = indexFlag;
   }
 
   public Index getIndex() {
     return index;
   }
 
+  public void commit() {
+    parentUpdateFlag = false;
+    indexManager.commit(index, parentIndex);
+  }
+
+  public ParentIndex getParentIndex() {
+    return parentIndex;
+  }
+
   public void setIndex(Index index) {
     this.index = index;
   }
 
+  public Iterator<TreeNode> emptyQuery() {
+
+    final PathNodeIterator itNode = new PathNodeIterator(node);
+    return new Iterator<TreeNode>() {
+
+      private TreeNode matchNode = nextmatch(itNode);
+
+      private TreeNode nextmatch(PathNodeIterator itNode) {
+
+        for (; itNode.hasNext();) {
+          TreeNode targetNode = itNode.next();
+          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);
+            if (parentUpdateFlag)
+              parentIndex = parentIndex.set(targetNode);
+          }
+        }
+        commit();
+        return null;
+      }
+
+      @Override
+      public boolean hasNext() {
+        if (matchNode == null) {
+          return false;
+        }
+        return true;
+      }
+
+      @Override
+      public TreeNode next() {
+        TreeNode currentPair = matchNode;
+        matchNode = nextmatch(itNode);
+        return currentPair;
+      }
+
+      @Override
+      public void remove() {
+      }
+
+    };
+
+  }
+
   /**
    * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う
    * 
@@ -58,63 +106,60 @@
    * @param searchValue
    * @return
    */
-  public Iterator<Pair<TreeNode, NodePath>> findInSubTree(Query query, Pair<TreeNode, NodePath> subTree, String key,
-      String searchValue) {
+  public Iterator<TreeNode> findInSubTree(Query query, TreeNode subTree, String key, String searchValue) {
     /*
      * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、
      * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
      */
-
-    if (index.get(key).isSome()) {
+    List<TreeNode> nodeList = index.get(key, searchValue);
+    if (nodeList != null) {
 
-      TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some();
-
-      Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
+      if (nodeList.isEmpty())
+        return new NulIterator<TreeNode>();// 空のIteratorを返す
 
-      if (opList.isNone())
-        return new NulIterator<Pair<TreeNode, NodePath>>();// 空のIteratorを返す
+      // ここでNode以下にあるか調べる
+      List<TreeNode> filteredList = List.nil();
 
-      List<Pair<TreeNode, NodePath>> list = opList.some();
-      NodePath targetNodePath = subTree.right();
-      List<Pair<TreeNode, NodePath>> filteredList = List.nil();
-
-      for (Pair<TreeNode, NodePath> pair : list) {
-        NodePath compareNodePath = pair.right();
-        if (targetNodePath.compare(compareNodePath))
-          filteredList = filteredList.cons(pair);
+      for (TreeNode targetNode : nodeList) {
+        TreeNode parent = targetNode;
+        while (parent != null) {
+          parent = parentIndex.get(parent);
+          if (parent.equals(subTree))
+            filteredList = filteredList.cons(targetNode);
+        }
       }
 
       return filteredList.iterator();
 
     } else {
       final PathNodeIterator itNode = new PathNodeIterator(subTree);
-      return new Iterator<Pair<TreeNode, NodePath>>() {
+      return new Iterator<TreeNode>() {
 
-        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+        private TreeNode matchNode = nextmatch(itNode);
 
-        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
+        private TreeNode nextmatch(PathNodeIterator itNode) {
 
           for (; itNode.hasNext();) {
-            Pair<TreeNode, NodePath> pathNode = itNode.next();
-            if (query.condition(pathNode.left()))
-              return pathNode;
+            TreeNode targetNode = itNode.next();
+            if (query.condition(targetNode))
+              return targetNode;
           }
           return null;
         }
 
         @Override
         public boolean hasNext() {
-          if (matchPair == null) {
+          if (matchNode == null) {
             return false;
           }
           return true;
         }
 
         @Override
-        public Pair<TreeNode, NodePath> next() {
-          Pair<TreeNode, NodePath> currentPair = matchPair;
-          matchPair = nextmatch(itNode);
-          return currentPair;
+        public TreeNode next() {
+          TreeNode currentNode = matchNode;
+          matchNode = nextmatch(itNode);
+          return currentNode;
         }
 
         @Override
@@ -134,50 +179,40 @@
    * @param searchValue
    * @return
    */
-  public Iterator<Pair<TreeNode, NodePath>> findInSubTreeAllValue(Query query, Pair<TreeNode, NodePath> subTree,
-      String key) {
+  public Iterator<TreeNode> findInSubTreeAllValue(Query query, TreeNode subTree, String key) {
     /*
      * indexからinnerIndexを取得 取得したinnerIndexが保有するKeyを取得
      * そのKeyを保有するNodeとNodeのPathを取得する
      * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、
      * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
      */
-
-    if (index.get(key).isSome()) {
-
-      TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some();
-      List<String> searchValues = innerIndex.keys();
-      List<Pair<TreeNode, NodePath>> filteredList = List.nil();
-      NodePath targetNodePath = subTree.right();
-
-      for (String searchValue : searchValues) {
-        Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
-
-        if (opList.isNone())
-          continue;
-
-        List<Pair<TreeNode, NodePath>> list = opList.some();
-        for (Pair<TreeNode, NodePath> pair : list) {
-          NodePath compareNodePath = pair.right();
-          if (targetNodePath.compare(compareNodePath))
-            filteredList = filteredList.cons(pair);
-
+    Iterator<TreeNode> NodeIterator = index.getAll(key);
+    if (NodeIterator != null) {
+      List<TreeNode> filteredList = List.nil();
+      for (; NodeIterator.hasNext();) {
+        TreeNode targetNode = NodeIterator.next();
+        TreeNode parent = targetNode;
+        while (parent != null) {
+          parent = parentIndex.get(parent);
+          if (parent.equals(subTree))
+            filteredList = filteredList.cons(targetNode);
         }
       }
       return filteredList.iterator();
 
     } else {
+
       final PathNodeIterator itNode = new PathNodeIterator(subTree);
-      return new Iterator<Pair<TreeNode, NodePath>>() {
+      return new Iterator<TreeNode>() {
 
-        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+        private TreeNode matchPair = nextmatch(itNode);
 
-        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
+        private TreeNode nextmatch(PathNodeIterator itNode) {
 
           for (; itNode.hasNext();) {
-            Pair<TreeNode, NodePath> pathNode = itNode.next();
-            if (query.condition(pathNode.left()))
-              return pathNode;
+            TreeNode targetNode = itNode.next();
+            if (query.condition(targetNode))
+              return targetNode;
           }
           return null;
         }
@@ -191,9 +226,62 @@
         }
 
         @Override
-        public Pair<TreeNode, NodePath> next() {
-          Pair<TreeNode, NodePath> currentPair = matchPair;
+        public TreeNode next() {
+          TreeNode currentNode = matchPair;
           matchPair = nextmatch(itNode);
+          return currentNode;
+        }
+
+        @Override
+        public void remove() {
+        }
+
+      };
+    }
+  }
+
+  public Iterator<TreeNode> find(Query query, String key, String searchValue) {
+
+    List<TreeNode> nodeList = index.get(key, searchValue);
+    if (nodeList != null) {
+      return nodeList.iterator();
+    } else {
+
+      final PathNodeIterator itNode = new PathNodeIterator(node);
+      return new Iterator<TreeNode>() {
+
+        private TreeNode matchNode = nextmatch(itNode);
+
+        private TreeNode nextmatch(PathNodeIterator itNode) {
+
+          for (; itNode.hasNext();) {
+            TreeNode targetNode = itNode.next();
+            String value = targetNode.getAttributes().getString(key);
+            if (indexFlag) {
+              if (value != null)
+                index = index.set(key, value, targetNode);
+            }
+            if (parentUpdateFlag)
+              parentIndex = parentIndex.set(targetNode);
+            if (query.condition(targetNode))
+              return targetNode;
+          }
+          commit();
+          return null;
+        }
+
+        @Override
+        public boolean hasNext() {
+          if (matchNode == null) {
+            return false;
+          }
+          return true;
+        }
+
+        @Override
+        public TreeNode next() {
+          TreeNode currentPair = matchNode;
+          matchNode = nextmatch(itNode);
           return currentPair;
         }
 
@@ -205,179 +293,50 @@
     }
   }
 
-  public Iterator<Pair<TreeNode, NodePath>> find(Query query, String key, String searchValue) {
-
-    if (index.get(key).isSome()) {
+  public Iterator<TreeNode> findAll(Query query, String key) {
 
-      TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some();
-      Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
+    Iterator<TreeNode> nodeList = index.getAll(key);
+    if (nodeList != null) {
 
-      if (opList.isNone())
-        return new NulIterator<Pair<TreeNode, NodePath>>();// 空のIteratorを返す
-
-      final List<Pair<TreeNode, NodePath>> list = opList.some();
-      return list.iterator();
+      return nodeList;
 
     } else {
-      Pair<TreeNode, NodePath> pair = new Pair<TreeNode, NodePath>(node, new DefaultNodePath());
-      final PathNodeIterator itNode = new PathNodeIterator(pair);
-      return new Iterator<Pair<TreeNode, NodePath>>() {
+
+      final PathNodeIterator itNode = new PathNodeIterator(node);
+      return new Iterator<TreeNode>() {
 
-        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+        private TreeNode matchNode = nextmatch(itNode);
 
-        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
+        private TreeNode nextmatch(PathNodeIterator itNode) {
 
           for (; itNode.hasNext();) {
-            Pair<TreeNode, NodePath> pathNode = itNode.next();
-            String value = pathNode.left().getAttributes().getString(key);
-            Option<TreeMap<String, List<Pair<TreeNode, NodePath>>>> innerIndexOp = index.get(key);
-
-            if (value != null) {
-              if (innerIndexOp.isNone()) {
-
-                TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = TreeMap.empty(Ord.stringOrd);
-                List<Pair<TreeNode, NodePath>> list = List.nil();
-                list = list.cons(pathNode);
-                innerIndex = innerIndex.set(value, list);
-                index = index.set(key, innerIndex);
-
-              } else {
-
-                TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = innerIndexOp.some();
-                Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(value);
-
-                if (opList.isNone()) {
-
-                  List<Pair<TreeNode, NodePath>> list = List.nil();
-                  list = list.cons(pathNode);
-                  innerIndex = innerIndex.set(value, list);
-
-                } else {
-
-                  List<Pair<TreeNode, NodePath>> list = opList.some();
-                  list = list.cons(pathNode);
-                  innerIndex = innerIndex.set(value, list);
-
-                }
-                index = index.set(key, innerIndex);
-
-              }
+            TreeNode targetNode = itNode.next();
+            String value = targetNode.getAttributes().getString(key);
+            if (indexFlag) {
+              if (value != null)
+                index = index.set(key, value, targetNode);
             }
-
-            if (query.condition(pathNode.left()))
-              return pathNode;
+            if (parentUpdateFlag)
+              parentIndex = parentIndex.set(targetNode);
+            if (query.condition(targetNode))
+              return targetNode;
           }
+          commit();
           return null;
         }
 
         @Override
         public boolean hasNext() {
-          if (matchPair == null) {
-            // index = itNode.getIndex();
+          if (matchNode == null) {
             return false;
           }
           return true;
         }
 
         @Override
-        public Pair<TreeNode, NodePath> next() {
-          Pair<TreeNode, NodePath> currentPair = matchPair;
-          matchPair = nextmatch(itNode);
-          return currentPair;
-        }
-
-        @Override
-        public void remove() {
-        }
-
-      };
-    }
-  }
-
-  public Iterator<Pair<TreeNode, NodePath>> findAll(Query query, String key) {
-
-    if (index.get(key).isSome()) {
-
-      TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some();
-      List<String> searchValues = innerIndex.keys();
-      List<Pair<TreeNode, NodePath>> valueList = List.nil();
-
-      for (String searchValue : searchValues) {
-        Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
-
-        if (opList.isNone())
-          continue;
-
-        List<Pair<TreeNode, NodePath>> list = opList.some();
-        valueList = valueList.append(list);
-      }
-      return valueList.iterator();
-
-    } else {
-      Pair<TreeNode, NodePath> pair = new Pair<TreeNode, NodePath>(node, new DefaultNodePath());
-      final PathNodeIterator itNode = new PathNodeIterator(pair);
-      return new Iterator<Pair<TreeNode, NodePath>>() {
-
-        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
-
-        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
-
-          for (; itNode.hasNext();) {
-            Pair<TreeNode, NodePath> pathNode = itNode.next();
-            String value = pathNode.left().getAttributes().getString(key);
-            Option<TreeMap<String, List<Pair<TreeNode, NodePath>>>> innerIndexOp = index.get(key);
-
-            if (value != null) {
-              if (innerIndexOp.isNone()) {
-
-                TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = TreeMap.empty(Ord.stringOrd);
-                List<Pair<TreeNode, NodePath>> list = List.nil();
-                list = list.cons(pathNode);
-                innerIndex = innerIndex.set(value, list);
-                index = index.set(key, innerIndex);
-
-              } else {
-
-                TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = innerIndexOp.some();
-                Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(value);
-
-                if (opList.isNone()) {
-
-                  List<Pair<TreeNode, NodePath>> list = List.nil();
-                  list = list.cons(pathNode);
-                  innerIndex = innerIndex.set(value, list);
-
-                } else {
-
-                  List<Pair<TreeNode, NodePath>> list = opList.some();
-                  list = list.cons(pathNode);
-                  innerIndex = innerIndex.set(value, list);
-
-                }
-                index = index.set(key, innerIndex);
-
-              }
-            }
-
-            if (query.condition(pathNode.left()))
-              return pathNode;
-          }
-          return null;
-        }
-
-        @Override
-        public boolean hasNext() {
-          if (matchPair == null) {
-            // index = itNode.getIndex();
-            return false;
-          }
-          return true;
-        }
-
-        @Override
-        public Pair<TreeNode, NodePath> next() {
-          Pair<TreeNode, NodePath> currentPair = matchPair;
-          matchPair = nextmatch(itNode);
+        public TreeNode next() {
+          TreeNode currentPair = matchNode;
+          matchNode = nextmatch(itNode);
           return currentPair;
         }