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

changeset 99:92d0c6e4655c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactoring to IteratorPathNode
author one
date Wed, 10 Sep 2014 18:54:52 +0900
parents 95000ff9064d
children 9a7b7af838e0
files src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/BruteForceTraverser.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/IteratorPathNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/IteratorPathNodeImpl.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/query/Query.java
diffstat 5 files changed, 106 insertions(+), 66 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/BruteForceTraverser.java	Tue Sep 09 16:23:01 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/BruteForceTraverser.java	Wed Sep 10 18:54:52 2014 +0900
@@ -5,15 +5,10 @@
 import fj.data.List;
 import fj.data.TreeMap;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTree;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.core.Children;
 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.TreeNode;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultTreeNode;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either;
 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
-import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.IteratorPathNode;
-import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.IteratorPathNodeImpl;
+import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query;
 
 public class BruteForceTraverser {
@@ -22,12 +17,12 @@
 	TreeMap<String,TreeNode> nodeIndex;
 	TreeMap<String,String> attributeIndex;	
 	
-	public BruteForceTraverser(TreeNode _root){
+	public BruteForceTraverser(TreeNode _root) {
 		node = _root;
 		//pathNodes = this.traverse(_root,new DefaultNodePath(),-1);
 	}
 	
-	public BruteForceTraverser getTraverser(JungleTree tree){
+	public BruteForceTraverser getTraverser(JungleTree tree) {
 		return new BruteForceTraverser(tree.getRootNode());
 	}
 	
@@ -60,15 +55,43 @@
 		return null;
 	}
 	*/
-	public Iterator<Pair<TreeNode, NodePath>> find(Query _query){
-		IteratorPathNode itNode = new IteratorPathNodeImpl(node);
-		List<Pair<TreeNode, NodePath>> list = List.nil();;
-		for(;itNode.hasNext();){
-			Pair<TreeNode, NodePath> pathNode = itNode.next();
-			if(_query.condition(pathNode.left()))
-				list = list.cons(pathNode);//list.reverse();//= list.cons();
-		}	
-		return list.iterator();
+	public Iterator<Pair<TreeNode, NodePath>> find(final Query query) {
+		final PathNodeIterator itNode = new PathNodeIterator(node);
+		
+		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();
+                    if (query.condition(pathNode.left()))
+                        return pathNode;
+                }   
+                return null;
+            }
+            
+            @Override
+            public boolean hasNext() {
+                // TODO Auto-generated method stub
+                return matchPair != null;
+            }
+
+            @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
+                
+            }
+
+		};
+
 	}
 	
 
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/IteratorPathNode.java	Tue Sep 09 16:23:01 2014 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,11 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
-
-import java.util.Iterator;
-
-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.util.Pair;
-
-public interface IteratorPathNode extends Iterator<Pair<TreeNode,NodePath>> {
-
-}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/IteratorPathNodeImpl.java	Tue Sep 09 16:23:01 2014 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,38 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
-
-import java.util.Stack;
-
-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.TreeNode;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
-
-public class IteratorPathNodeImpl implements IteratorPathNode {
-
-	Stack<Pair<TreeNode, NodePath>> pathNodeStack = new Stack<Pair<TreeNode, NodePath>>();
-	public IteratorPathNodeImpl(TreeNode _root){
-		pathNodeStack.push(new Pair<TreeNode, NodePath>(_root, new DefaultNodePath()));
-	}
-
-
-	@Override
-	public boolean hasNext() {
-		if(pathNodeStack.empty())
-			return false;
-		return true;
-	}
-
-	@Override
-	public Pair<TreeNode, NodePath> next() {
-		Pair<TreeNode, NodePath> pathNode = pathNodeStack.pop();
-		if(pathNode.left().getChildren().size() == 0)
-			return pathNode;
-		int count = 0;
-		for(TreeNode child : pathNode.left().getChildren()){
-			pathNodeStack.push(new Pair<TreeNode,NodePath>(child,pathNode.right().add(count)));
-			count++;
-		}
-		return pathNode;
-	}
-	
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java	Wed Sep 10 18:54:52 2014 +0900
@@ -0,0 +1,65 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
+
+import java.util.Iterator;
+import java.util.Stack;
+
+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.TreeNode;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren;
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
+
+public class PathNodeIterator implements Iterator<Pair<TreeNode,NodePath>> {
+
+    NodePath path;
+	TreeNode root;
+	TreeNode node;
+	int childNumber;
+    private TreeNodeChildren children;
+    private Stack<TreeNode> nodeStack = new Stack<TreeNode>();
+    
+	public PathNodeIterator(TreeNode root) {
+	    this.root = root;
+	    path = new DefaultNodePath();
+	    node = root;
+	}
+
+
+	@Override
+	public boolean hasNext() {
+	    return node != null;
+	}
+
+	@Override
+	public Pair<TreeNode, NodePath> next() {
+	    TreeNode now = node;
+	    NodePath currentPath = path;
+	    if (node.getChildren().size() > 0) {
+	        nodeStack.push(node);
+	        currentPath = path.add(0);
+	        children = node.getChildren();
+	        node = children.at(0).b();
+	        childNumber = 1;
+	    } else if (node == root) {
+            node = null; // no more node
+            children = null;
+        } else if (children != null && children.size() > childNumber) {
+	        childNumber++;
+	        node = children.at(childNumber).b();
+	        currentPath = path.add(childNumber);
+	    } else {
+	        path = path.tail();
+	        node = nodeStack.pop();
+	        children = node.getChildren();
+	    }
+	    return new Pair<TreeNode,NodePath>(now,currentPath);
+	}
+
+
+    @Override
+    public void remove() {
+        // TODO Auto-generated method stub
+        
+    }
+	
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/Query.java	Tue Sep 09 16:23:01 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/Query.java	Wed Sep 10 18:54:52 2014 +0900
@@ -4,4 +4,5 @@
 
 public interface Query {
 	boolean condition(TreeNode _node);
+	
 }