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

changeset 98:95000ff9064d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Create Query
author one
date Tue, 09 Sep 2014 16:23:01 +0900
parents a1e20a440ddd
children 92d0c6e4655c
files src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/NodePath.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultNodePath.java 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/Query.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/CompareNode.java src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/BruteForceTraverserTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/DefaultTraverserTest.java
diffstat 10 files changed, 247 insertions(+), 18 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/NodePath.java	Mon Sep 08 17:03:08 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/NodePath.java	Tue Sep 09 16:23:01 2014 +0900
@@ -6,5 +6,6 @@
 {
 	public NodePath add(int _pos);
 	public Pair<Integer,NodePath> pop();
+	public NodePath tail();
 	public int size();
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultNodePath.java	Mon Sep 08 17:03:08 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/store/impl/DefaultNodePath.java	Tue Sep 09 16:23:01 2014 +0900
@@ -80,4 +80,11 @@
 			}
 		});
 	}
+
+	@Override
+	public NodePath tail() {
+		List<Integer> tail = path.reverse();
+		tail = tail.tail().reverse();
+		return new DefaultNodePath(tail);
+	}
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/BruteForceTraverser.java	Mon Sep 08 17:03:08 2014 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/BruteForceTraverser.java	Tue Sep 09 16:23:01 2014 +0900
@@ -1,29 +1,45 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser;
 
+import java.util.Iterator;
+
 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.Query;
 
 public class BruteForceTraverser {
-	List<Pair<NodePath,TreeNode>> pathNodes;
+	BruteForceTraverser traverser;
+	TreeNode node;
 	TreeMap<String,TreeNode> nodeIndex;
 	TreeMap<String,String> attributeIndex;	
 	
-	BruteForceTraverser(TreeNode _root){
-		pathNodes = this.traverse(_root,new DefaultNodePath(),-1);
+	public BruteForceTraverser(TreeNode _root){
+		node = _root;
+		//pathNodes = this.traverse(_root,new DefaultNodePath(),-1);
+	}
+	
+	public BruteForceTraverser getTraverser(JungleTree tree){
+		return new BruteForceTraverser(tree.getRootNode());
 	}
 	
-	public List<Pair<NodePath,TreeNode>> traverse(TreeNode _node ,NodePath _path ,int _pos){
+
+	/*public IteratorPathNode traverse(TreeNode _node ,NodePath _path ,int _pos){
 		
 		Children  children = _node.getChildren();
-		List<Pair<NodePath,TreeNode>> list = List.nil();
+		Either<Error,TreeNode> either = children.at(0);
+		IteratorPathNode list = new IteratorPathNodeImpl();
 		int pathCount = _pos;
 		if(children.size() == 0){
-			list = list.cons(new Pair<NodePath,TreeNode>(_path.add(_pos),_node));
+			list = list.add(new Pair<TreeNode, NodePath>(node, _path.add(_pos)));
 			return list;
 		}
 		
@@ -32,25 +48,28 @@
 				pathCount++;
 			}
 			
-			list = list.cons(new Pair<NodePath,TreeNode>(_path.add(_pos),_node));
+			list = list.add(new Pair<TreeNode,NodePath>(_node, _path.add(_pos)));
 		return list;
 	}
 	
-	public List<Pair<NodePath,TreeNode>> search(String _key, String _Attribute){
-		List<Pair<NodePath,TreeNode>> pathNode = List.nil();
-		for(Pair<NodePath,TreeNode> searchNode : pathNodes){
-			if(searchNode.right().getAttributes().get(_key).equals(_Attribute))
-				pathNode = pathNode.cons(searchNode);
-		}
-		return pathNode;
-	}
-	
-	public int count(String _key, String _attribute){
-		return this.search(_key,_attribute).length();
+	public int count(Query _query, String _key, String _attribute){
+		return this.find(_query,_key,_attribute);
 	}
 	
 	public List<Pair<NodePath,TreeNode>> distinct(String _key ,String... _attribute){
 		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();
+	}
+	
 
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/IteratorPathNode.java	Tue Sep 09 16:23:01 2014 +0900
@@ -0,0 +1,11 @@
+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>> {
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/IteratorPathNodeImpl.java	Tue Sep 09 16:23:01 2014 +0900
@@ -0,0 +1,38 @@
+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/Query.java	Tue Sep 09 16:23:01 2014 +0900
@@ -0,0 +1,7 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
+
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
+
+public interface Query {
+	boolean condition(TreeNode _node);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java	Tue Sep 09 16:23:01 2014 +0900
@@ -0,0 +1,23 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
+
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
+
+public class SearchQuery implements Query {
+	
+	private String attribute;
+	private String key;
+	public SearchQuery(String _key, String _attribute){
+		key = _key;
+		attribute = _attribute;
+	}
+	@Override
+	public boolean condition(TreeNode _node) {
+		String str = new String(_node.getAttributes().get(key).array());
+		System.out.println(str);
+		if(str.equals(attribute))
+			return true;
+		return false;
+	}
+
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/CompareNode.java	Tue Sep 09 16:23:01 2014 +0900
@@ -0,0 +1,29 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.test;
+
+import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTree;
+import fj.data.HashMap;
+import fj.data.List;
+
+public class CompareNode {
+	public List<MuchNode> compare(JungleTree tree1, JungleTree tree2){
+		List<PathNode> pNodes1 = traverser.traverse(tree1);
+		List<PathNode> pNodes2 = traverser.traverse(tree2);
+		HashMap<ByteBuffer,PathNode> map = new HashMap<ByteBuffer,PathNode>(null, null);
+		List<MuchNode> muchNodes = new List<MuchNode>(null);
+		for(PathNode pathNode : pNodes1){
+			Either<Error,ByteBuffer> either = get(pathNode.getNode());
+			if(either.isA())
+				continue;
+			map.put(either.B(),pathNode);
+		}
+		for(PathNode pathNode : pNodes2){
+			Either<Error,ByteBuffer> either = get(pathNode.getNode());
+			if(either.isA())
+				continue;
+			if(!map.containskey(either.B()))
+				continue;
+			muchNodes.add(tree1,pathNode.getPath(),pathNode.getNode(),tree2,map.get(either.B().getPath()),map.get(either.B().getNode()));
+		}
+		return muchNodes;
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/BruteForceTraverserTest.java	Tue Sep 09 16:23:01 2014 +0900
@@ -0,0 +1,75 @@
+package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverse;
+
+import java.nio.ByteBuffer;
+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.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.traverser.BruteForceTraverser;
+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.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.tatsuki.jungle.query.Query;
+import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.SearchQuery;
+import junit.framework.TestCase;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import fj.data.List;
+
+public abstract class BruteForceTraverserTest extends TestCase{
+	public abstract BruteForceTraverser instance(TreeNode node);
+
+	@Test
+	public void test1()	{
+		int maxHeight = 3;
+		Pair<TreeNode, NodePath> test = null;
+		TreeNode root = createTree(0,0,maxHeight,new DefaultNodePath());
+		BruteForceTraverser traverser = instance(root);
+		Iterator<Pair<TreeNode, NodePath>> itNode = traverser.find(new SearchQuery("KEY","<-1>"));
+		for(;itNode.hasNext(); ){
+			test = itNode.next();
+		
+		}
+		String str = new String(test.left().getAttributes().get("KEY").array());
+		Assert.assertEquals(str,"<-1>");
+	}
+	
+	public static String key = "KEY";
+	public static ByteBuffer value = ByteBuffer.wrap(key.getBytes());
+	public static DefaultTreeNode factory = new DefaultTreeNode();
+	
+	public static TreeNode createTree(int _curX,int _curY,int _maxHeight,NodePath _address)
+	{
+		TreeNode parent = factory.createNewNode();
+		Either<Error,TreeNode> either = parent.getAttributes().put(key,ByteBuffer.wrap(_address.toString().getBytes()));
+		if(either.isA()){
+			Assert.fail();
+		}
+		parent = either.b();
+		
+		if(_curY == _maxHeight){
+			return parent;
+		}
+		
+		for(int i = 0;i < _curY + 1;i ++){
+			TreeNode ch = createTree(i,_curY + 1,_maxHeight,_address.add(i));
+			either = parent.getChildren().addNewChildAt(i,ch);
+			if(either.isA()){
+				Assert.fail();
+			}
+			
+			parent = either.b();
+		}
+		
+		return parent;
+	}
+
+}
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/DefaultTraverserTest.java	Mon Sep 08 17:03:08 2014 +0900
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/DefaultTraverserTest.java	Tue Sep 09 16:23:01 2014 +0900
@@ -1,7 +1,13 @@
 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverse;
 
+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.traverser.BruteForceTraverser;
 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.Pair;
 import junit.framework.TestCase;
 import junit.framework.TestSuite;
 
@@ -11,9 +17,11 @@
 	{
 		TestSuite suite = new TestSuite();
 		suite.addTestSuite(TraverserTestImpl.class);
+		suite.addTestSuite(BruteForceTraverserTestImpl.class);
 		return suite;
 	}
 	
+	
 	public static class TraverserTestImpl extends TraverserTest
 	{
 
@@ -24,4 +32,15 @@
 		}
 		
 	}
+	
+	public static class BruteForceTraverserTestImpl extends BruteForceTraverserTest
+	{
+
+		@Override
+		public BruteForceTraverser instance(TreeNode root)
+		{
+			return new BruteForceTraverser(root);
+		}
+		
+	}
 }