# HG changeset patch # User tatsuki # Date 1485445501 -32400 # Node ID b8ddf62689ee08383d5b110f559ae5aa15a92dd6 # Parent de68d37fec8021504fa1c5a821fde895da29b91f redele pathIterator diff -r de68d37fec80 -r b8ddf62689ee src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/DefaultNodeAndPathIterator.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/DefaultNodeAndPathIterator.java Fri Jan 27 00:41:06 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,93 +0,0 @@ -package jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator; - -import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.DefaultNodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; -import jp.ac.u_ryukyu.ie.cr.jungle.util.Pair; - -import java.util.Iterator; -import java.util.Stack; - -/** - * Created by e115731 on 2017/01/25. - */ -public class DefaultNodeAndPathIterator implements Iterator> { - - private TreeNode root; - private TreeNode node; - private NodePath path = new DefaultNodePath(); - private int childNumber; - private TreeNodeChildren children; - private Stack nodeStack = new Stack<>(); - private Stack searchStack = new Stack<>(); - - /* - * get queryIndexCondition from query - * if already index exists, use index - * otherwise traverse tree and create index - * - * */ - public DefaultNodeAndPathIterator(TreeNode root) { - this.root = root; - this.node = root; - } - - @Override - public boolean hasNext() { - return node != null; - } - - @Override - public Pair next() { - TreeNode now = node; - NodePath currentPath = path; - if (node.getChildren().size() > 0) { - nodeStack.push(node); - children = node.getChildren(); - node = children.at(0).b(); - path = path.add(0); - childNumber = 1; - searchStack.push(childNumber); - } else if (node == root) { - node = null; // no more node - children = null; - return new Pair<>(now, currentPath); - } else if (children != null && children.size() > childNumber) { - childNumber = searchStack.pop(); - node = children.at(childNumber).b(); - path = path.add(childNumber); - searchStack.push(++childNumber); - } else { - node = nodeStack.pop(); - path = path.tail(); - children = node.getChildren(); - childNumber = searchStack.pop(); - for (; children.size() == childNumber; ) { - if (node == root) { - node = null; // no more node - children = null; - return new Pair<>(now, currentPath); - } - node = nodeStack.pop(); - path = path.tail(); - children = node.getChildren(); - childNumber = searchStack.pop(); - } - if (node != null && childNumber < children.size()) { - nodeStack.push(node); - node = children.at(childNumber).b(); - path = path.add(childNumber); - searchStack.push(++childNumber); - } - } - return new Pair<>(now, currentPath); - } - - @Override - public void remove() { - // TODO Auto-generated method stub - - } - -} diff -r de68d37fec80 -r b8ddf62689ee src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/JungleDifferentialTreeNodeAndPathIterator.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/JungleDifferentialTreeNodeAndPathIterator.java Fri Jan 27 00:41:06 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,87 +0,0 @@ -package jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator; - -import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.DefaultNodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; -import jp.ac.u_ryukyu.ie.cr.jungle.util.Pair; - -import java.util.Iterator; -import java.util.Stack; - - -public class JungleDifferentialTreeNodeAndPathIterator implements Iterator> { - - private TreeNode root; - private TreeNode node; - private TreeNode endNode; - int childNumber; - private TreeNodeChildren children; - private Stack nodeStack = new Stack<>(); - private Stack searchStack = new Stack<>(); - private NodePath path = new DefaultNodePath(); - - public JungleDifferentialTreeNodeAndPathIterator(TreeNode root, TreeNode endNode) { - this.root = root; - this.node = root; - this.endNode = endNode; - } - - @Override - public boolean hasNext() { - return node != null; - } - - @Override - public Pair next() { - TreeNode now = node; - NodePath currentPath = path; - if (node.getChildren().size() > 0 && node != endNode) { //ノードの下に子供がある - nodeStack.push(node); - children = node.getChildren(); - node = children.at(0).b(); - path = path.add(0); - childNumber = 1; - searchStack.push(childNumber); - } else if (node == root) { //ノードとルートがここで同じなら全探索が終わったので探索は終了する - node = null; // no more node - children = null; - return new Pair<>(now,currentPath); - } else if (children != null && children.size() > childNumber) { // ノードの次の子供を見る - childNumber = searchStack.pop(); - node = children.at(childNumber).b(); - path = path.add(childNumber); - searchStack.push(++childNumber); - } else { // これ以下のノードが無いので上に戻る - node = nodeStack.pop(); - path = path.tail(); - children = node.getChildren(); - childNumber = searchStack.pop(); - for (; children.size() == childNumber; ) { //ここで上に登る - if (node == root) { - node = null; // no more node - children = null; - return new Pair<>(now,currentPath); - } - node = nodeStack.pop(); - path = path.tail(); - children = node.getChildren(); - childNumber = searchStack.pop(); - } - if (node != null && childNumber < children.size()) { //登っている途中で未探索の子ノードを見つけた場合 - nodeStack.push(node); - node = children.at(childNumber).b(); - path = path.add(childNumber); - searchStack.push(++childNumber); - } - } - return new Pair<>(now,currentPath); - } - - @Override - public void remove() { - // TODO Auto-generated method stub - - } - -} \ No newline at end of file diff -r de68d37fec80 -r b8ddf62689ee src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/RedBlackTreeNodeAndPathIterator.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/RedBlackTreeNodeAndPathIterator.java Fri Jan 27 00:41:06 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,60 +0,0 @@ -package jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator; - -import jp.ac.u_ryukyu.ie.cr.jungle.core.Attributes; -import jp.ac.u_ryukyu.ie.cr.jungle.core.Children; -import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.DefaultNodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.util.Pair; - -import java.nio.ByteBuffer; -import java.util.Iterator; - -/** - * Created by e115731 on 2017/01/25. - */ -public class RedBlackTreeNodeAndPathIterator implements Iterator> { - - private TreeNode next; - private NodePath currentPath = new DefaultNodePath(); - - public RedBlackTreeNodeAndPathIterator(TreeNode root, String key, String searchValue) { - ByteBuffer searchValueBf = ByteBuffer.wrap(searchValue.getBytes()); - next = search(root, key, searchValueBf); - } - - private TreeNode search(TreeNode target, String key, ByteBuffer searchValueBf) { - if (target == null) - return null; - Attributes attribute = target.getAttributes(); - ByteBuffer targetValue = attribute.get(key); - - long b1 = targetValue.hashCode(); - long b2 = searchValueBf.hashCode(); - if (b1 - b2 < 0) { - Children children = target.getChildren(); - TreeNode child = children.at(0).b(); - currentPath = currentPath.add(0); - return search(child, key, searchValueBf); - } else if (b1 - b2 > 0) { - Children children = target.getChildren(); - TreeNode child = children.at(1).b(); - currentPath = currentPath.add(1); - return search(child, key, searchValueBf); - } else { - return target; - } - } - - @Override - public boolean hasNext() { - return next != null; - } - - @Override - public Pair next() { - TreeNode current = next; - next = null; - return new Pair(current, currentPath); - } -} diff -r de68d37fec80 -r b8ddf62689ee src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/trasnformer/replaceRootNodeAt.java --- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/trasnformer/replaceRootNodeAt.java Fri Jan 27 00:41:06 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/trasnformer/replaceRootNodeAt.java Fri Jan 27 00:45:01 2017 +0900 @@ -2,10 +2,10 @@ import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.LoggingNode; import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.OperationLog; -import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.util.DefaultEither; import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; public class ReplaceRootNodeAt implements NodeEditor {