Mercurial > hg > Members > tatsuki > bench > jungle-core

changeset 139:ec166c8ff079

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add findAll and findInSubTreeAll
author one
date Tue, 28 Oct 2014 06:35:34 +0900
parents b998fdc99bc0
children 99bda30ea72c
files src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.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/PutIndexEditor.java
diffstat 4 files changed, 336 insertions(+), 178 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java	Mon Oct 27 19:04:59 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java	Tue Oct 28 06:35:34 2014 +0900
@@ -1,23 +1,14 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser;
 
 import java.util.Iterator;
-import java.util.concurrent.atomic.AtomicReference;
 
 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.JungleTree;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.persistent.ChangeList;
-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.impl.TreeNode;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.AtomicReservableReference;
-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.IndexJungleTreeEditor;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.TreeContext;
 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;
@@ -25,207 +16,374 @@
 
 public class InterfaceTraverser {
 
-    //InterfaceTraverser traverser;
-    TreeNode node;
-    TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
-    IndexManager indexManager;
+  // InterfaceTraverser traverser;
+  TreeNode node;
+  TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
+  IndexManager indexManager;
+
+  public InterfaceTraverser(TreeNode _root, IndexManager indexManager) {
+    this.node = _root;
+    this.index = TreeMap.empty(Ord.stringOrd);
+    this.indexManager = indexManager;
+  }
+
+  public InterfaceTraverser(TreeNode _root, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,
+      IndexManager indexManager) {
+    this.node = _root;
+    this.index = index;
+    this.indexManager = indexManager;
+  }
+
+  public void commitIndex() {
+    indexManager.commit(index);
+  }
+
+  public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex() {
+    return index;
+  }
 
-    public InterfaceTraverser(TreeNode _root, IndexManager indexManager) {
-        this.node = _root;
-        this.index = TreeMap.empty(Ord.stringOrd);
-        this.indexManager = indexManager;
-    }
+  public void setIndex(TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
+    this.index = index;
+  }
 
-    public InterfaceTraverser(
-            TreeNode _root,
-            TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index,
-            IndexManager indexManager) {
-        this.node = _root;
-        this.index = index;
-        this.indexManager = indexManager;
-    }
+  /**
+   * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う
+   * 
+   * @param query
+   * @param subTree
+   * @param key
+   * @param searchValue
+   * @return
+   */
+  public Iterator<Pair<TreeNode, NodePath>> findInSubTree(Query query, Pair<TreeNode, NodePath> subTree, String key,
+      String searchValue) {
+    /*
+     * 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();
+
+      Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
 
-    public void commitIndex(){
-        indexManager.commit(index);
-    }
+      if (opList.isNone())
+        return null;// 空のIteratorを返す
+
+      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);
+
+      }
+
+      return filteredList.iterator();
+
+    } else {
+      final PathNodeIterator itNode = new PathNodeIterator(subTree.left());
+      return new Iterator<Pair<TreeNode, NodePath>>() {
+
+        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+
+        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
 
-    public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex() {
-        return index;
-    }
+          for (; itNode.hasNext();) {
+            Pair<TreeNode, NodePath> pathNode = itNode.next();
+            if (query.condition(pathNode.left()))
+              return pathNode;
+          }
+          return null;
+        }
 
-    public void setIndex(
-            TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
-        this.index = index;
+        @Override
+        public boolean hasNext() {
+          if (matchPair == 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 InterfaceTraverser getTraverser(JungleTree tree) {
-		return new InterfaceTraverser(tree.getRootNode(), tree.getIndex(),
-				tree.getIndexTreeEditor());
-	}*/
-
-    public void set(TreeNode root) {
-        this.node = root;
-    }
-
+  }
 
-    /**
-     * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う
-     * @param query
-     * @param subTree
-     * @param key
-     * @param searchValue
-     * @return
+  /**
+   * subTree以下のNodeに対してKeyに対応する値をindexを使って探索する
+   * 
+   * @param query
+   * @param subTree
+   * @param key
+   * @param searchValue
+   * @return
+   */
+  public Iterator<Pair<TreeNode, NodePath>> findInSubTreeAllValue(Query query, Pair<TreeNode, NodePath> subTree,
+      String key) {
+    /*
+     * indexからinnerIndexを取得 取得したinnerIndexが保有するKeyを取得
+     * そのKeyを保有するNodeとNodeのPathを取得する
+     * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、
+     * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
      */
-    public Iterator<Pair<TreeNode, NodePath>> findInSubTree(Query query, TreeNode subTree, String key, String searchValue){
-        /* 
-         * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、
-         * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
-         */
-        final PathNodeIterator itNode = new PathNodeIterator(subTree);
-        return new Iterator<Pair<TreeNode, NodePath>>() {
+
+    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);
+
+        }
+      }
+      return filteredList.iterator();
 
-            private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+    } else {
+      final PathNodeIterator itNode = new PathNodeIterator(subTree.left());
+      return new Iterator<Pair<TreeNode, NodePath>>() {
+
+        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+
+        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
 
-            private Pair<TreeNode, NodePath> nextmatch(
-                    PathNodeIterator itNode) {
+          for (; itNode.hasNext();) {
+            Pair<TreeNode, NodePath> pathNode = itNode.next();
+            if (query.condition(pathNode.left()))
+              return pathNode;
+          }
+          return null;
+        }
+
+        @Override
+        public boolean hasNext() {
+          if (matchPair == null) {
+            return false;
+          }
+          return true;
+        }
 
-                for (; itNode.hasNext();) {
-                    Pair<TreeNode, NodePath> pathNode = itNode.next();
-                    if (query.condition(pathNode.left()))
-                        return pathNode;
-                }
-                return null;
-            }
+        @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>> find(Query query, String key, String searchValue) {
+
+    if (index.get(key).isSome()) {
+
+      TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some();
+      Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
+
+      if (opList.isNone())
+        return null;// 空のIteratorを返す
+
+      final List<Pair<TreeNode, NodePath>> list = opList.some();
+      return list.iterator();
+
+    } else {
+
+      final PathNodeIterator itNode = new PathNodeIterator(node);
+      return new Iterator<Pair<TreeNode, NodePath>>() {
 
-            @Override
-            public boolean hasNext() {
-                if (matchPair == null) {
-                    //						index = itNode.getIndex();
-                    return false;
+        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);
+
                 }
-                return true;
-            }
+                index = index.set(key, innerIndex);
 
-            @Override
-            public Pair<TreeNode, NodePath> next() {
-                Pair<TreeNode, NodePath> currentPair = matchPair;
-                matchPair = nextmatch(itNode);
-                return currentPair;
-            }
-
-            @Override
-            public void remove() {
-                // TODO Auto-generated method stub
-
+              }
             }
 
-        };
-
-    }
-
-
-    public Iterator<Pair<TreeNode, NodePath>> find(Query query, String key,
-            String searchValue) {
-
-        if (index.get(key).isSome()) {
+            if (query.condition(pathNode.left()))
+              return pathNode;
+          }
+          return null;
+        }
 
-            TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index
-                    .get(key).some();
-            Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex
-                    .get(searchValue);
+        @Override
+        public boolean hasNext() {
+          if (matchPair == null) {
+            // index = itNode.getIndex();
+            return false;
+          }
+          return true;
+        }
 
-            if (opList.isNone())
-                return null;// 空のIteratorを返す
-
-            final List<Pair<TreeNode, NodePath>> list = opList.some();
-            return list.iterator();
-
-        } else {
+        @Override
+        public Pair<TreeNode, NodePath> next() {
+          Pair<TreeNode, NodePath> currentPair = matchPair;
+          matchPair = nextmatch(itNode);
+          return currentPair;
+        }
 
-            final PathNodeIterator itNode = new PathNodeIterator(node);
-            return new Iterator<Pair<TreeNode, NodePath>>() {
+        @Override
+        public void remove() {
+        }
 
-                private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+      };
+    }
+  }
 
-                private Pair<TreeNode, NodePath> nextmatch(
-                        PathNodeIterator itNode) {
+  
+  public Iterator<Pair<TreeNode, NodePath>> findAll(Query query, String key) {
 
-                    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 (index.get(key).isSome()) {
 
-                        if (value != null) {
-                            if (innerIndexOp.isNone()) {
+      TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some();
+      List<String> searchValues = innerIndex.keys();
+      List<Pair<TreeNode, NodePath>> valueList = List.nil();
 
-                                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);
+      for (String searchValue : searchValues) {
+        Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
 
-                            } else {
+        if (opList.isNone())
+          continue;
 
-                                TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = innerIndexOp
-                                        .some();
-                                Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex
-                                        .get(value);
+        List<Pair<TreeNode, NodePath>> list = opList.some();
+        valueList = valueList.append(list);
+      }
+      return valueList.iterator();
 
-                                if (opList.isNone()) {
+    } else {
 
-                                    List<Pair<TreeNode, NodePath>> list = List
-                                            .nil();
-                                    list = list.cons(pathNode);
-                                    innerIndex = innerIndex.set(value, list);
+      final PathNodeIterator itNode = new PathNodeIterator(node);
+      return new Iterator<Pair<TreeNode, NodePath>>() {
 
-                                } else {
+        private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode);
+
+        private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) {
 
-                                    List<Pair<TreeNode, NodePath>> list = opList
-                                            .some();
-                                    list = list.cons(pathNode);
-                                    innerIndex = innerIndex.set(value, list);
+          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);
 
-                                }
-                                index = index.set(key, innerIndex);
-
-                            }
-                        }
+            if (value != null) {
+              if (innerIndexOp.isNone()) {
 
-                        if (query.condition(pathNode.left()))
-                            return pathNode;
-                    }
-                    return null;
-                }
+                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);
 
-                @Override
-                public boolean hasNext() {
-                    if (matchPair == null) {
-                        // index = itNode.getIndex();
-                        return false;
-                    }
-                    return true;
-                }
+                if (opList.isNone()) {
+
+                  List<Pair<TreeNode, NodePath>> list = List.nil();
+                  list = list.cons(pathNode);
+                  innerIndex = innerIndex.set(value, list);
 
-                @Override
-                public Pair<TreeNode, NodePath> next() {
-                    Pair<TreeNode, NodePath> currentPair = matchPair;
-                    matchPair = nextmatch(itNode);
-                    return currentPair;
-                }
+                } else {
 
-                @Override
-                public void remove() {
-                    // TODO Auto-generated method stub
+                  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);
+          return currentPair;
+        }
+
+        @Override
+        public void remove() {
+        }
+
+      };
     }
+  }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java	Mon Oct 27 19:04:59 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java	Tue Oct 28 06:35:34 2014 +0900
@@ -40,7 +40,7 @@
 	public Pair<TreeNode, NodePath> next() {
 		TreeNode now = node;
 		NodePath currentPath = path;
-		System.out.println("path = " + currentPath.toString());
+	//	System.out.println("path = " + currentPath.toString());
 		if (node.getChildren().size() > 0) { // 
 			nodeStack.push(node);
 			path = path.add(0);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/AddNewChildrenIndexEditor.java	Mon Oct 27 19:04:59 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/AddNewChildrenIndexEditor.java	Tue Oct 28 06:35:34 2014 +0900
@@ -58,7 +58,7 @@
 					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()));
+						//System.out.println(new String(list.head().left().getAttributes().get("KEY").array()));
 						newInnerIndex = newInnerIndex.set(innerIndexKey, list);
 					}
 				}
@@ -76,7 +76,7 @@
 		for (Pair<TreeNode, NodePath> pair : pairList) {
 
 			NodePath path = pair.right();
-			System.out.println("oldPath = " + path.toString());
+			//System.out.println("oldPath = " + path.toString());
 			NodePath newPath = new DefaultNodePath();
 			
 			
@@ -112,7 +112,7 @@
 
 			}
 
-			System.out.println("newPath = " + newPath.toString());
+			//System.out.println("newPath = " + newPath.toString());
 			Pair<TreeNode, NodePath> newPair = new Pair<TreeNode, NodePath>(pair.left(), newPath);
 			list = list.cons(newPair);
 		}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/PutIndexEditor.java	Mon Oct 27 19:04:59 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/PutIndexEditor.java	Tue Oct 28 06:35:34 2014 +0900
@@ -58,7 +58,7 @@
 				list = list.cons(pathNode);
 				innerIndex = innerIndex.set(attribute, list);
 				TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> newIndex = index.set(key, innerIndex);
-				return index;
+				return newIndex;
 			} else {
 
 				TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = innerIndexOp.some();