Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 304:b6118ca2c2c2
tmp
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/DefaultInterfaceTraverser.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/DefaultInterfaceTraverser.java Wed Jan 25 05:53:48 2017 +0900 @@ -89,6 +89,11 @@ } @Override + public Iterator<TreeNode> find(String key, String searchValue) { + return index.get(key, searchValue); + } + + @Override public Iterator<TreeNode> find(final Query query, final String key, String searchValue) { Iterator<TreeNode> nodeIterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/DifferentialInterfaceTraverser.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/DifferentialInterfaceTraverser.java Wed Jan 25 05:53:48 2017 +0900 @@ -89,6 +89,11 @@ } @Override + public Iterator<TreeNode> find(String key, String searchValue) { + return index.get(key, searchValue); + } + + @Override public Iterator<TreeNode> find(final Query query, final String key, String searchValue) { Iterator<TreeNode> nodeIterator; @@ -96,7 +101,7 @@ nodeIterator = index.get(key, searchValue); ; } else { - nodeIterator = new JungleDifferentialTreeNodeIterator(root,endNode); + nodeIterator = new JungleDifferentialTreeNodeIterator(root, endNode); } TreeNode firstMatchNode = null;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/InterfaceTraverser.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/InterfaceTraverser.java Wed Jan 25 05:53:48 2017 +0900 @@ -24,5 +24,7 @@ Iterator<TreeNode> find(Query query); + Iterator<TreeNode> find(String key, String searchValue); + Iterator<TreeNode> find(Query query, String key, String searchValue); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/RedBlackTreeTraverser.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/RedBlackTreeTraverser.java Wed Jan 25 05:53:48 2017 +0900 @@ -86,8 +86,13 @@ } @Override + public Iterator<TreeNode> find(String key, String searchValue) { + return new RedBlackTreeNodeIterator(root, key, searchValue); + } + + @Override public Iterator<TreeNode> find(Query query, String key, String searchValue) { - Iterator<TreeNode> nodeIterator = new RedBlackTreeNodeIterator(root,key,searchValue); + Iterator<TreeNode> nodeIterator = new RedBlackTreeNodeIterator(root, key, searchValue); TreeNode firstMatchNode = null; for (; nodeIterator.hasNext(); ) { firstMatchNode = nextmatch(nodeIterator.next(), query);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/DefaultNodeAndPathIterator.java Wed Jan 25 05:53:48 2017 +0900 @@ -0,0 +1,93 @@ +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<Pair<TreeNode, NodePath>> { + + private TreeNode root; + private TreeNode node; + private NodePath path = new DefaultNodePath(); + private int childNumber; + private TreeNodeChildren children; + private Stack<TreeNode> nodeStack = new Stack<>(); + private Stack<Integer> 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<TreeNode, NodePath> 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 + + } + +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/DefaultNodeIterator.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/DefaultNodeIterator.java Wed Jan 25 05:53:48 2017 +0900 @@ -8,9 +8,9 @@ public class DefaultNodeIterator implements Iterator<TreeNode> { - TreeNode root; - TreeNode node; - int childNumber; + private TreeNode root; + private TreeNode node; + private int childNumber; private TreeNodeChildren children; private Stack<TreeNode> nodeStack = new Stack<>(); private Stack<Integer> searchStack = new Stack<>();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/JungleDifferentialTreeNodeAndPathIterator.java Wed Jan 25 05:53:48 2017 +0900 @@ -0,0 +1,87 @@ +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<Pair<TreeNode, NodePath>> { + + private TreeNode root; + private TreeNode node; + private TreeNode endNode; + int childNumber; + private TreeNodeChildren children; + private Stack<TreeNode> nodeStack = new Stack<>(); + private Stack<Integer> 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<TreeNode, NodePath> 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
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/JungleDifferentialTreeNodeIterator.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/JungleDifferentialTreeNodeIterator.java Wed Jan 25 05:53:48 2017 +0900 @@ -6,9 +6,7 @@ import java.util.Iterator; import java.util.Stack; -/** - * Created by e115731 on 2017/01/07. - */ + public class JungleDifferentialTreeNodeIterator implements Iterator<TreeNode> { private TreeNode root;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/RedBlackTreeNodeAndPathIterator.java Wed Jan 25 05:53:48 2017 +0900 @@ -0,0 +1,58 @@ +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<Pair<TreeNode, NodePath>> { + + 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); + + if (targetValue.hashCode() - searchValueBf.hashCode() < 0) { + Children children = target.getChildren(); + TreeNode child = children.at(0).b(); + currentPath = currentPath.add(0); + return search(child, key, searchValueBf); + } else if (targetValue.hashCode() - searchValueBf.hashCode() > 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<TreeNode, NodePath> next() { + TreeNode current = next; + next = null; + return new Pair<TreeNode, NodePath>(current, currentPath); + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/logger/LoggingChildren.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/logger/LoggingChildren.java Wed Jan 25 05:53:48 2017 +0900 @@ -2,6 +2,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.core.Children; +import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.*; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.util.DefaultEither; @@ -53,8 +54,8 @@ } - public Either<Error, LoggingNode> redBlackTreeDeleteChildAt(String key, ByteBuffer value) { - NodeOperation deleteChildAt = new RedBlackTreeDeleteChildAtOperation(key, value); + public Either<Error, LoggingNode> redBlackTreeDeleteChildAt(int pos, NodePath path) { + NodeOperation deleteChildAt = new RedBlackTreeDeleteChildAtOperation(pos, path); return edit(deleteChildAt); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/operations/RedBlackTreeDeleteChildAtOperation.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/operations/RedBlackTreeDeleteChildAtOperation.java Wed Jan 25 05:53:48 2017 +0900 @@ -1,6 +1,7 @@ package jp.ac.u_ryukyu.ie.cr.jungle.store.operations; import jp.ac.u_ryukyu.ie.cr.jungle.store.Command; +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.Either; @@ -13,12 +14,12 @@ */ public class RedBlackTreeDeleteChildAtOperation implements NodeOperation { - private String key; - private ByteBuffer value; + private int pos; + private NodePath path; - public RedBlackTreeDeleteChildAtOperation(String key, ByteBuffer value) { - this.key = key; - this.value = value; + public RedBlackTreeDeleteChildAtOperation(int pos, NodePath path) { + this.pos = pos; + this.path = path; } @Override @@ -29,9 +30,10 @@ @Override public Either<Error, TreeNode> invoke(TreeNode target) { TreeNodeChildren children = target.getChildren(); - return children.matchingChildDeleteAt(key, value); + return children.matchingChildDeleteAt(pos, path); } + @Override public int getPosition() { return -2;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/trasnformer/RedBlackTreeDeleteChildAt.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/trasnformer/RedBlackTreeDeleteChildAt.java Wed Jan 25 05:53:48 2017 +0900 @@ -2,27 +2,26 @@ 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.store.nodepath.NodePath; 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; -import java.nio.ByteBuffer; - /** * Created by e115731 on 2017/01/04. */ public class RedBlackTreeDeleteChildAt implements NodeEditor { - private final String key; - private final ByteBuffer value; + private final int pos; + private final NodePath path; - public RedBlackTreeDeleteChildAt(String key, ByteBuffer value) { - this.key = key; - this.value = value; + public RedBlackTreeDeleteChildAt(int pos, NodePath path) { + this.pos = pos; + this.path = path; } public Either<Error, LoggingNode> _edit(LoggingNode logNode) { - Either<Error, LoggingNode> either = logNode.getChildren().redBlackTreeDeleteChildAt(key, value); + Either<Error, LoggingNode> either = logNode.getChildren().redBlackTreeDeleteChildAt(pos, path); if (either.isA()) { // error return either;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/RedBlackJungleTreeEditor.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/RedBlackJungleTreeEditor.java Wed Jan 25 05:53:48 2017 +0900 @@ -95,9 +95,9 @@ @Override public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos) { - // RedBlackTreeDeleteChildAt deleteChildAt = new RedBlackTreeDeleteChildAt(pos, path); 未実装 - // NodePath dummyPath = new DefaultNodePath(-2); - return null;//_edit(dummyPath, deleteChildAt); + RedBlackTreeDeleteChildAt deleteChildAt = new RedBlackTreeDeleteChildAt(pos, path); //未実装 + NodePath dummyPath = new DefaultNodePath(-2); + return _edit(dummyPath, deleteChildAt); } @Override @@ -105,8 +105,8 @@ if (!key.equals(balanceKey)) return DefaultEither.newA(INVALID_ARGUMENT); path = new DefaultNodePath(-2); //dummyのPathを作る これはtraverserを避けるために使う - RedBlackTreeDeleteChildAt deleteChildAt = new RedBlackTreeDeleteChildAt(key, value); - return edit(path, deleteChildAt); //未実装 + RedBlackTreeDeleteChildAt deleteChildAt = null;//new RedBlackTreeDeleteChildAt(key, value); + return edit(path, deleteChildAt); } @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java Wed Jan 25 05:53:48 2017 +0900 @@ -3,6 +3,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.data.list.List; import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.NodeEditorError; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeAttributes; @@ -83,7 +84,7 @@ //まだ実装していない もともと赤黒木の編集用 @Override - public Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value) { + public Either<Error, TreeNode> matchingChildDeleteAt(int pos , NodePath path) { return null; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Differencial/DifferencialTreeNodeChildren.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Differencial/DifferencialTreeNodeChildren.java Wed Jan 25 05:53:48 2017 +0900 @@ -1,6 +1,7 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.Differencial; +import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.NodeEditorError; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeAttributes; @@ -56,7 +57,7 @@ @Override - public Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value) { + public Either<Error, TreeNode> matchingChildDeleteAt(int pos , NodePath path) { return null; //未使用 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/TreeNodeChildren.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/TreeNodeChildren.java Wed Jan 25 05:53:48 2017 +0900 @@ -1,6 +1,7 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node; import jp.ac.u_ryukyu.ie.cr.jungle.core.Children; +import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; @@ -19,5 +20,5 @@ Either<Error, TreeNode> addNewChildAndPutAttribtue(int pos, String key, ByteBuffer value); - Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value); + Either<Error, TreeNode> matchingChildDeleteAt(int pos , NodePath path) ; } \ No newline at end of file
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Wed Jan 25 05:53:48 2017 +0900 @@ -1,7 +1,10 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; -import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.*; +import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.Rotate; +import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +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 org.junit.Test; import java.nio.ByteBuffer; @@ -25,7 +28,7 @@ this.leftChild = left; this.rightChild = right; if (value != null) - this.valueStr = new String(value.array()); + this.valueStr = new String(value.array()); } //test用 @@ -110,16 +113,22 @@ */ public abstract int checkDepth(int count, int minCount); - public RebuildNode delete(String insertKey, ByteBuffer deleteValue, ColorlessTreeNode parent, Rotate side) { + public RebuildNode delete(NodePath path, ColorlessTreeNode parent, Rotate side) { + RebuildNode rebuildNode; if (!this.empty()) { - RebuildNode rebuildNode; - long result = this.compare(deleteValue); - if (result > 0) { - rebuildNode = right().delete(insertKey, deleteValue, this, Rotate.R); - } else if (result < 0) { - rebuildNode = left().delete(insertKey, deleteValue, this, Rotate.L); + if (path.size() == 1) { + rebuildNode = replaceNode(parent); } else { - rebuildNode = replaceNode(parent); + Pair<Integer, NodePath> pair = path.pop(); + path = pair.right(); + int num = pair.left(); + if (num == 1) { + rebuildNode = right().delete(path, this, Rotate.R); + } else if (num == 0) { + rebuildNode = left().delete(path, this, Rotate.L); + } else { + return null; + } } if (parent == null || rebuildNode == null) return rebuildNode;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Wed Jan 25 05:53:48 2017 +0900 @@ -2,6 +2,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.Rotate; import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.NodeEditorError; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; @@ -12,7 +13,6 @@ import java.nio.ByteBuffer; import java.util.Iterator; -import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.JungleTreeError.INVALID_ARGUMENT; import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.TreeEditorError.DELETE_VALUE_NOT_FOUND; /** @@ -45,10 +45,10 @@ } @Override - public Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value) { - if (value == null) - return DefaultEither.newA(INVALID_ARGUMENT); - RebuildNode newNode = node.delete(key, value, null, Rotate.N); + public Either<Error, TreeNode> matchingChildDeleteAt(int pos , NodePath path) { + path = path.add(pos);//削除するpathを作る + path = path.pop().right();// -1をpathから外す + RebuildNode newNode = node.delete(path, null, Rotate.N); if (newNode == null) return DefaultEither.newA(DELETE_VALUE_NOT_FOUND); // 削除するノードが無かった場合 ColorlessTreeNode root = newNode.getNode();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/DefaultJungleTree.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/DefaultJungleTree.java Wed Jan 25 05:53:48 2017 +0900 @@ -18,6 +18,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.GetOldTreeError; +import java.util.Iterator; import java.util.Optional; import java.util.concurrent.atomic.AtomicReference; @@ -75,6 +76,11 @@ return path.addHead(-1); } + @Override + public Iterator<NodePath> getMathNodePath(String key, String value) { //未実装 + return null; + } + AtomicReference<TreeContext> getRepository(){ return repository; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/JungleTree.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/JungleTree.java Wed Jan 25 05:53:48 2017 +0900 @@ -10,6 +10,8 @@ import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; +import java.util.Iterator; + public interface JungleTree { public JungleTreeEditor getJungleTreeEditor(); @@ -31,5 +33,7 @@ public NodePath getNodePath(TreeNode node); + public Iterator<NodePath> getMathNodePath(String key, String value); + public JungleTreeEditor getLocalJungleTreeEditor(); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/RedBlackJungleTree.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/RedBlackJungleTree.java Wed Jan 25 05:53:48 2017 +0900 @@ -1,7 +1,11 @@ package jp.ac.u_ryukyu.ie.cr.jungle.tree; +import jp.ac.u_ryukyu.ie.cr.jungle.core.Attributes; import jp.ac.u_ryukyu.ie.cr.jungle.persistent.ChangeListWriter; +import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator.DefaultNodeAndPathIterator; +import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator.RedBlackTreeNodeAndPathIterator; import jp.ac.u_ryukyu.ie.cr.jungle.store.TreeContext; +import jp.ac.u_ryukyu.ie.cr.jungle.store.nodepath.NodePath; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.editor.jungleTreeEditor.JungleTreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.editor.jungleTreeEditor.RedBlackJungleTreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.editor.treeEditor.TreeEditor; @@ -9,8 +13,10 @@ import jp.ac.u_ryukyu.ie.cr.jungle.transaction.manager.TransactionManager; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree.ColorlessTreeNode; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Pair; import org.junit.Test; +import java.util.Iterator; import java.util.concurrent.atomic.AtomicReference; /** @@ -37,6 +43,72 @@ return new RedBlackJungleTreeEditor(root, balanceKey, txManager, treeEditor); } + /** + * もう少し最適化できると思う ノードのPathも返す検索をTraverserに実装する？ + */ + @Override + public Iterator<NodePath> getMathNodePath(String key, String value) { + if (!key.equals(balanceKey)) { + Iterator<Pair<TreeNode, NodePath>> iterator = new DefaultNodeAndPathIterator(getRootNode()); + + NodePath path = null; + + while (path == null && iterator.hasNext()) { + path = nextMatch(iterator.next(), key, value); + } + final NodePath finalPath = path; + return new Iterator<NodePath>() { + NodePath matchPath = finalPath; + + @Override + public boolean hasNext() { + return matchPath != null; + } + + + @Override + public NodePath next() { + NodePath currentPath = matchPath; + while (iterator.hasNext()) { + matchPath = nextMatch(iterator.next(), key, value); + } + + return currentPath; + } + }; + } else { + Iterator<Pair<TreeNode, NodePath>> iterator = new RedBlackTreeNodeAndPathIterator(getRootNode(), key, value); + + return new Iterator<NodePath>() { + NodePath path; + @Override + public boolean hasNext() { + if (!iterator.hasNext()) + return false; + Pair<TreeNode, NodePath> p = iterator.next(); + TreeNode node = p.left(); + if (node == null) + return false; + path = p.right(); + return true; + } + + @Override + public NodePath next() { + return path; + } + }; + } + } + private NodePath nextMatch(Pair<TreeNode, NodePath> p, String key, String value) { + TreeNode node = p.left(); + Attributes attribute = node.getAttributes(); + String v = attribute.getString(key); + if (v.equals(value)) + return p.right(); + return null; + } + @Test public void checkDepth() { ColorlessTreeNode root = (ColorlessTreeNode) getRootNode();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/persistent/PersistentJungleTree.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/persistent/PersistentJungleTree.java Wed Jan 25 05:53:48 2017 +0900 @@ -21,6 +21,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.GetOldTreeError; +import java.util.Iterator; import java.util.Optional; import java.util.concurrent.atomic.AtomicReference; @@ -141,4 +142,9 @@ } return path; } + + @Override + public Iterator<NodePath> getMathNodePath(String key, String value) { //未実装 + return null; + } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/transaction/NetworkDefaultJungleTree.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/transaction/NetworkDefaultJungleTree.java Wed Jan 25 05:53:48 2017 +0900 @@ -20,6 +20,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.GetOldTreeError; +import java.util.Iterator; import java.util.Optional; import java.util.concurrent.atomic.AtomicReference; @@ -146,4 +147,9 @@ } return path; } + + @Override + public Iterator<NodePath> getMathNodePath(String key, String value) { //未実装 + return null; + } }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorNodeTest.java Sun Jan 08 12:23:48 2017 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorNodeTest.java Wed Jan 25 05:53:48 2017 +0900 @@ -23,7 +23,7 @@ public class RedBlackTreeEditorNodeTest { - int testCount = 1000; + int testCount = 20; @Test public void RedBlackTreeEditorNode() { @@ -64,25 +64,38 @@ Assert.assertEquals(expectCount, nodeCount); ColorlessTreeNode rootNode2 = (ColorlessTreeNode) rootNode; //test用methodを使うためにcastしている - rootNode2.checkDepth(0, 0); //赤黒木のバランスが取れているかを調べる + //rootNode2.checkDepth(0, 0); //赤黒木のバランスが取れているかを調べる } System.out.println("------------------------------------------- delete -----------------------------------------------------------------------------------"); for (int count = 1; count <= testCount; count++) { JungleTreeEditor editor = tree.getJungleTreeEditor(); - ByteBuffer value = ByteBuffer.wrap(("value" + count).getBytes()); - Either<Error, JungleTreeEditor> either = editor.deleteChildAt(path, 0, key, value); + String value = "value" + count; + Iterator<NodePath> iterator = tree.getMathNodePath(key, value); + Assert.assertTrue(iterator.hasNext()); + path = iterator.next(); + Either<Error, JungleTreeEditor> either = editor.deleteChildAt(path, 0); Assert.assertFalse(either.isA()); editor = either.b(); either = editor.success(); Assert.assertFalse(either.isA()); ColorlessTreeNode rootNode = (ColorlessTreeNode) tree.getRootNode(); - Iterator<TreeNode> iterator = new DefaultNodeIterator(rootNode); + Iterator<TreeNode> nodeIterator = new DefaultNodeIterator(rootNode); int nodeCount = 0; - while (iterator.hasNext() && rootNode.getAttributes().get(key) != null) { //削除時間違えて他のノードを消してないかを調べる - ColorlessTreeNode node = (ColorlessTreeNode) iterator.next(); + int count1 = count + 1; + while (count1 <= testCount) { + String value1 = "value" + count1; + Iterator<NodePath> pathIteratpr = tree.getMathNodePath(key, value1); + Assert.assertTrue(pathIteratpr.hasNext()); + path = pathIteratpr.next(); + Assert.assertNotNull(path); + count1++; + } + + while (nodeIterator.hasNext() && rootNode.getAttributes().get(key) != null) { //削除時間違えて他のノードを消してないかを調べる + ColorlessTreeNode node = (ColorlessTreeNode) nodeIterator.next(); ByteBuffer seach = node.getAttributes().get(key); Assert.assertTrue(rootNode.get(seach)); nodeCount++;