# HG changeset patch # User one # Date 1410421106 -32400 # Node ID c297f0015d9e548cbe611fd4140456d891b34980 # Parent 9a7b7af838e044d656401111a5527d231d7e7aa5 create Update query diff -r 9a7b7af838e0 -r c297f0015d9e src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/DefaultJungleTree.java Thu Sep 11 16:38:26 2014 +0900 @@ -55,6 +55,11 @@ @Override public InterfaceTraverser getTraverser() { - return new InterfaceTraverser(getRootNode()); + return new InterfaceTraverser(getRootNode(), index, getTreeEditor()); + } + + @Override + public Pair,TreeMap> getIndex() { + return index; } } diff -r 9a7b7af838e0 -r c297f0015d9e src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/JungleTree.java Thu Sep 11 16:38:26 2014 +0900 @@ -1,8 +1,10 @@ package jp.ac.u_ryukyu.ie.cr.shoshi.jungle; +import fj.data.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.InterfaceTraverser; +import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair; public interface JungleTree { @@ -10,4 +12,5 @@ public InterfaceTraverser getTraverser(); public JungleTreeEditor getLocalTreeEditor(); public TreeNode getRootNode(); + public Pair,TreeMap> getIndex(); } diff -r 9a7b7af838e0 -r c297f0015d9e src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultJungleTreeEditor.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultJungleTreeEditor.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/transaction/DefaultJungleTreeEditor.java Thu Sep 11 16:38:26 2014 +0900 @@ -137,6 +137,6 @@ @Override public TreeNode getRoot() { - return null; + return root; } } diff -r 9a7b7af838e0 -r c297f0015d9e 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 Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java Thu Sep 11 16:38:26 2014 +0900 @@ -2,96 +2,114 @@ 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.JungleTreeEditor; 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.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.PathNodeIterator; -import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.SearchQuery; +import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.UpdateQuery; public class InterfaceTraverser { InterfaceTraverser traverser; + TreeNode node; - TreeMap nodeIndex; - TreeMap attributeIndex; - - public InterfaceTraverser(TreeNode _root) { - node = _root; - //pathNodes = this.traverse(_root,new DefaultNodePath(),-1); + TreeMap nodeIndex; + TreeMap attributeIndex; + JungleTreeEditor editor; + + public InterfaceTraverser(TreeNode _root, + Pair, TreeMap> index, + JungleTreeEditor editor) { + this.node = _root; + this.nodeIndex = index.left(); + this.attributeIndex = index.right(); + this.editor = editor; } - + public InterfaceTraverser getTraverser(JungleTree tree) { - return new InterfaceTraverser(tree.getRootNode()); + return new InterfaceTraverser(tree.getRootNode(), tree.getIndex(), + tree.getTreeEditor()); } - - /*public IteratorPathNode traverse(TreeNode _node ,NodePath _path ,int _pos){ - - Children children = _node.getChildren(); - Either either = children.at(0); - IteratorPathNode list = new IteratorPathNodeImpl(); - int pathCount = _pos; - if(children.size() == 0){ - list = list.add(new Pair(node, _path.add(_pos))); - return list; - } - - for(TreeNode child : children){ - list = list.append(traverse(child,_path,pathCount)); - pathCount++; + public void set(TreeNode root){ + this.node = root; + } + /* + * public IteratorPathNode traverse(TreeNode _node ,NodePath _path ,int + * _pos){ + * + * Children children = _node.getChildren(); Either either = + * children.at(0); IteratorPathNode list = new IteratorPathNodeImpl(); int + * pathCount = _pos; if(children.size() == 0){ list = list.add(new + * Pair(node, _path.add(_pos))); return list; } + * + * for(TreeNode child : children){ list = + * list.append(traverse(child,_path,pathCount)); pathCount++; } + * + * list = list.add(new Pair(_node, _path.add(_pos))); + * return list; } + * + * public int count(Query _query, String _key, String _attribute){ return + * this.find(_query,_key,_attribute); } + * + * public List> distinct(String _key ,String... + * _attribute){ return null; } + */ + public JungleTreeEditor update(final UpdateQuery query) { + Iterator> findNode = find(query); + //do { + for (; findNode.hasNext();) { + Either either = editor.putAttribute(findNode.next().right(), "KEY", query.getUpdateAttribute()); + if (either.isA()) + ;// wait delay write + editor = either.b(); } - - list = list.add(new Pair(_node, _path.add(_pos))); - return list; - } - - public int count(Query _query, String _key, String _attribute){ - return this.find(_query,_key,_attribute); + //} while (editor.success().isA()); + + return editor; } - - public List> distinct(String _key ,String... _attribute){ - return null; - } - */ - public Iterator> find(final Query query) { + + public Iterator> find(final SearchQuery query) { final PathNodeIterator itNode = new PathNodeIterator(node); - + return new Iterator>() { - private Pair matchPair = nextmatch(itNode); + private Pair matchPair = nextmatch(itNode); + + private Pair nextmatch(PathNodeIterator itNode) { + for (; itNode.hasNext();) { + Pair pathNode = itNode.next(); + if (query.condition(pathNode.left())) + return pathNode; + } + return null; + } - private Pair nextmatch(PathNodeIterator itNode) { - for (;itNode.hasNext();) { - Pair pathNode = itNode.next(); - if (query.condition(pathNode.left())) - return pathNode; - } - return null; - } - - @Override - public boolean hasNext() { - return matchPair != null; - } + @Override + public boolean hasNext() { + return matchPair != null; + } - @Override - public Pair next() { - Pair currentPair = matchPair; - matchPair = nextmatch(itNode); - return currentPair; - } + @Override + public Pair next() { + Pair currentPair = matchPair; + matchPair = nextmatch(itNode); + return currentPair; + } - @Override - public void remove() { - // TODO Auto-generated method stub - - } + @Override + public void remove() { + // TODO Auto-generated method stub + + } }; } - } diff -r 9a7b7af838e0 -r c297f0015d9e 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 Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/PathNodeIterator.java Thu Sep 11 16:38:26 2014 +0900 @@ -9,57 +9,75 @@ 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> { +public class PathNodeIterator implements Iterator> { - NodePath path; + NodePath path; TreeNode root; TreeNode node; int childNumber; - private TreeNodeChildren children; - private Stack nodeStack = new Stack(); - + private TreeNodeChildren children; + private Stack nodeStack = new Stack(); + private Stack searchStack = new Stack(); + public PathNodeIterator(TreeNode root) { - this.root = root; - path = new DefaultNodePath(); - node = root; + this.root = root; + path = new DefaultNodePath(); + node = root; + } - @Override public boolean hasNext() { - return node != null; + return node != null; } @Override public Pair 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(now,currentPath); + TreeNode now = node; + NodePath currentPath = path; + if (node.getChildren().size() > 0) { + nodeStack.push(node); + path = path.add(0); + children = node.getChildren(); + node = children.at(0).b(); + childNumber = 1; + searchStack.push(childNumber); + } else if (children != null && children.size() > childNumber) { + childNumber = searchStack.pop(); + node = children.at(childNumber).b(); + path = path.tail().add(childNumber); + searchStack.push(++childNumber); + } else { + path = path.tail(); + node = nodeStack.pop(); + children = node.getChildren(); + childNumber = searchStack.pop(); + for (; children.size() == childNumber;) { + path = path.tail(); + node = nodeStack.pop(); + children = node.getChildren(); + childNumber = searchStack.pop(); + if (node == root) { + node = null; // no more node + children = null; + return new Pair(now, currentPath); + } + } + if (node != null && childNumber < children.size()) { + path = path.add(childNumber); + nodeStack.push(node); + node = children.at(childNumber).b(); + searchStack.push(++childNumber); + } + } + System.out.println(path.toString()); + return new Pair(now, currentPath); } + @Override + public void remove() { + // TODO Auto-generated method stub - @Override - public void remove() { - // TODO Auto-generated method stub - - } - + } + } diff -r 9a7b7af838e0 -r c297f0015d9e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/Query.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/Query.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/Query.java Thu Sep 11 16:38:26 2014 +0900 @@ -4,5 +4,4 @@ public interface Query { boolean condition(TreeNode _node); - } diff -r 9a7b7af838e0 -r c297f0015d9e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java Thu Sep 11 16:38:26 2014 +0900 @@ -2,7 +2,7 @@ import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; -public class SearchQuery implements Query { +public class SearchQuery /*implements Query*/ { private String attribute; private String key; @@ -10,14 +10,13 @@ key = _key; attribute = _attribute; } - @Override + //@Override public boolean condition(TreeNode _node) { String str = new String(_node.getAttributes().get(key).array()); - System.out.println(str); + //System.out.println(str); if(str.equals(attribute)) return true; return false; } - } diff -r 9a7b7af838e0 -r c297f0015d9e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/UpdateQuery.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/UpdateQuery.java Thu Sep 11 16:38:26 2014 +0900 @@ -0,0 +1,20 @@ +package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query; + +import java.nio.ByteBuffer; + + +public class UpdateQuery extends SearchQuery /*implements Query*/ { + + + private String updateAttribute; + + public UpdateQuery(String key, String attribute , String updateAttribute){ + super(key, attribute); + this.updateAttribute = updateAttribute; + } + + public ByteBuffer getUpdateAttribute(){ + updateAttribute.getBytes(); + return ByteBuffer.wrap(updateAttribute.getBytes()); + } +} diff -r 9a7b7af838e0 -r c297f0015d9e src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/BruteForceTraverserTest.java --- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/BruteForceTraverserTest.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/BruteForceTraverserTest.java Thu Sep 11 16:38:26 2014 +0900 @@ -3,43 +3,57 @@ import java.nio.ByteBuffer; import java.util.Iterator; +import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.JungleTreeEditor; 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.InterfaceTraverser; -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 jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.UpdateQuery; import junit.framework.TestCase; import org.junit.Assert; import org.junit.Test; -import fj.data.List; - public abstract class BruteForceTraverserTest extends TestCase{ public abstract InterfaceTraverser instance(TreeNode node); @Test - public void test1() { + public void testSearch() { int maxHeight = 3; Pair test = null; TreeNode root = createTree(0,0,maxHeight,new DefaultNodePath()); InterfaceTraverser traverser = instance(root); - Iterator> itNode = traverser.find(new SearchQuery("KEY","<-1>")); + Iterator> itNode = traverser.find(new SearchQuery("KEY","<-1,0,0>")); for(;itNode.hasNext(); ){ test = itNode.next(); - } String str = new String(test.left().getAttributes().get("KEY").array()); - Assert.assertEquals(str,"<-1>"); + Assert.assertEquals(str,"<-1,0,0>"); + } + + @Test + public void testUpdate() { + int maxHeight = 3; + Pair test = null; + TreeNode root = createTree(0,0,maxHeight,new DefaultNodePath()); + InterfaceTraverser traverser = instance(root); + Iterator> itNode = traverser.find(new SearchQuery("KEY","<-1,0,0>")); + for(;itNode.hasNext(); ){ + test = itNode.next(); + } + JungleTreeEditor editor = traverser.update(new UpdateQuery("KEY", "<-1,0,0>", "tatsuki")); + traverser.set(editor.getRoot()); + Iterator> checkNode = traverser.find(new SearchQuery("KEY","tatsuki")); + for(;checkNode.hasNext(); ){ + test = checkNode.next(); + } + String str = new String(test.left().getAttributes().get("KEY").array()); + Assert.assertEquals(str,"tatsuki"); } public static String key = "KEY"; @@ -48,6 +62,7 @@ public static TreeNode createTree(int _curX,int _curY,int _maxHeight,NodePath _address) { + System.out.println(_address.toString()); TreeNode parent = factory.createNewNode(); Either either = parent.getAttributes().put(key,ByteBuffer.wrap(_address.toString().getBytes())); if(either.isA()){ diff -r 9a7b7af838e0 -r c297f0015d9e src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/DefaultTraverserTest.java --- a/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/DefaultTraverserTest.java Thu Sep 11 03:10:03 2014 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverse/DefaultTraverserTest.java Thu Sep 11 16:38:26 2014 +0900 @@ -3,7 +3,9 @@ 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.DefaultTreeEditor; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; +import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.transaction.DefaultJungleTreeEditor; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.InterfaceTraverser; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.DefaultTraverser; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser.Traverser; @@ -39,7 +41,7 @@ @Override public InterfaceTraverser instance(TreeNode root) { - return new InterfaceTraverser(root); + return new InterfaceTraverser(root, new Pair(null,null),new DefaultJungleTreeEditor(root,null,new DefaultTreeEditor(new DefaultTraverser()),null)); } }