Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 293:5f8250bc62c3
implement RedBlackTree add
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/RedBlackJungleTreeEditor.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/RedBlackJungleTreeEditor.java Wed Jan 04 03:50:31 2017 +0900 @@ -5,6 +5,7 @@ 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.logger.TreeOperationLog; +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.store.operations.DefaultTreeOperation; import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.NodeOperation; @@ -80,6 +81,7 @@ */ @Override public Either<Error, JungleTreeEditor> addNewChildAndPutAttribute(NodePath path, int pos, String key, ByteBuffer value) { + path = new DefaultNodePath(-2); AppendChildAndPutAttribute appendChildAndPutAttribute = new AppendChildAndPutAttribute(key,value,pos); return _edit(path,appendChildAndPutAttribute); } @@ -87,6 +89,7 @@ @Override public Either<Error, JungleTreeEditor> addNewChildAt(NodePath path, int _pos) { ByteBuffer value = ByteBuffer.wrap("defaultValue".getBytes()); + path = new DefaultNodePath(-2); return addNewChildAndPutAttribute(path, 0, balanceKey, value); } @@ -129,7 +132,15 @@ @Override public Either<Error, JungleTreeEditor> success() { - return null; + Either<Error, TransactionManager> either = txManager.commit(root, log, editedNodeList); + if (either.isA()) { + return DefaultEither.newA(either.a()); + } + + TransactionManager newTxManager = either.b(); + JungleTreeEditor newTreeEditor = new RedBlackJungleTreeEditor(root,balanceKey, newTxManager, editor); + + return DefaultEither.newB(newTreeEditor); } @Override
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/manager/RedBlackTreeTransactionManager.java Wed Jan 04 03:50:31 2017 +0900 @@ -0,0 +1,96 @@ +package jp.ac.u_ryukyu.ie.cr.jungle.transaction.manager; + +import jp.ac.u_ryukyu.ie.cr.jungle.data.list.List; +import jp.ac.u_ryukyu.ie.cr.jungle.persistent.ChangeList; +import jp.ac.u_ryukyu.ie.cr.jungle.persistent.ChangeListWriter; +import jp.ac.u_ryukyu.ie.cr.jungle.store.TreeContext; +import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.TreeOperationLog; +import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.TreeOperation; +import jp.ac.u_ryukyu.ie.cr.jungle.transaction.context.DefaultTreeContext; +import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; +import jp.ac.u_ryukyu.ie.cr.jungle.traverser.InterfaceTraverser; +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.DefaultError; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; + +import java.util.Iterator; +import java.util.concurrent.atomic.AtomicReference; + +/** + * Created by e115731 on 2017/01/04. + */ +public class RedBlackTreeTransactionManager implements TransactionManager { + private final AtomicReference<TreeContext> repository; + private final TreeContext tip; + private final ChangeListWriter writer; + private final String uuid; + + public RedBlackTreeTransactionManager(ChangeListWriter _writer, TreeContext _tip, AtomicReference<TreeContext> _repository, String _uuid) { + repository = _repository; + tip = _tip; + writer = _writer; + uuid = _uuid; + } + + + @Override + public Either<Error, TransactionManager> commit(TreeNode newRoot, final TreeOperationLog _log, List<TreeNode> editNodeList) { + long currentRevision = tip.revision(); + long nextRevision = currentRevision + 1; + + final String _treeName = tip.getTreeName(); + ChangeList list = new ChangeList() { + @Override + public Iterator<TreeOperation> iterator() { + return _log.iterator(); + } + + @Override + public String getTreeName() { + return _treeName; + } + + @Override + public TreeOperationLog getLog() { + return _log; + } + + @Override + public String uuid() { + return uuid; + } + + }; + + InterfaceTraverser traverser = new InterfaceTraverser(newRoot, true); + TreeContext newTreeContext = new DefaultTreeContext(newRoot, tip, list, uuid, _treeName, nextRevision, traverser); + + if (repository.compareAndSet(newTreeContext.prev(), newTreeContext)) { + TransactionManager txManager = new DefaultTransactionManager(writer, newTreeContext, repository, uuid); + return DefaultEither.newB(txManager); + } + + return DefaultEither.newA((Error) new DefaultError()); + } + + @Override + public Either<Error, TransactionManager> flashCommit(TreeNode _newRoot, TreeOperationLog _log) { + return null;//commit(_newRoot, _log); + } + + @Override + public boolean setAppendedNode(TreeNode appendedNode) { + return false; //使わない + } + + @Override + public String getUUID() { + return uuid; + } + + @Override + public long getRevision() { + return tip.revision(); + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java Wed Jan 04 03:50:31 2017 +0900 @@ -30,7 +30,6 @@ private boolean boundaryCheck(int _pos) { int size = children.length(); return size >= _pos && _pos >= 0; - } @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/BlackTreeNode.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/BlackTreeNode.java Wed Jan 04 03:50:31 2017 +0900 @@ -1,48 +1,40 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; -import jp.ac.u_ryukyu.ie.cr.jungle.data.list.List; +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.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeAttributes; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; 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 org.junit.Test; import java.nio.ByteBuffer; import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.TreeNodeError.NOT_USE_METHOD; public class BlackTreeNode extends ColorlessTreeNode { - private TreeMap<String, ByteBuffer> attrs; - private static final List<TreeNode> NIL_LIST = new List<>(); - public BlackTreeNode(String balanceKey, ByteBuffer value) { - this(new TreeMap<>(), balanceKey, value, new EmptyTreeNode(), new EmptyTreeNode()); - } - - public BlackTreeNode(String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { - this(new TreeMap<>(), balanceKey, value, left, right); + public BlackTreeNode(ColorlessTreeNode node) { + this(node.getAttrs(), node.key(),node.value(),node.left(),node.right()); } public BlackTreeNode(TreeMap<String, ByteBuffer> _attrs, String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { - super(balanceKey,value,left,right); - this.attrs = _attrs; + super(_attrs, balanceKey, value, left, right); } @Override - public TreeNodeChildren getChildren() { - return new RedTreeNodeChildren(this, attrs); + public RedBlackTreeNodeChildren getChildren() { + return new RedBlackTreeNodeChildren(this, getAttrs()); + } + + @Override + public RedBlackTreeNodeAttribute getAttributes() { + return new RedBlackTreeNodeAttribute(left(), right(), getAttrs()); } @Override public ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode right) { - return null; - } - - @Override - public TreeNodeAttributes getAttributes() { - return new RedBlackTreeNodeAttribute(left(), right(), attrs); + return new BlackTreeNode(newChild.getAttrs(),newChild.key(),newChild.value(),left,right); } @Override @@ -51,7 +43,7 @@ } public TreeNode clone() { - return new BlackTreeNode(attrs, key(), value(), left(), right()); + return new BlackTreeNode(getAttrs(), key(), value(), left(), right()); } @Override @@ -75,7 +67,50 @@ } @Override - public boolean empty(){ + public boolean empty() { return false; } + + @Override + public Rotate checkRotate(Rotate side) { + return Rotate.N; + } + + @Override + protected ColorlessTreeNode insBalance() { + Rotate spin = left().checkRotate(Rotate.L); + if (spin == Rotate.R) { + ColorlessTreeNode newLeftChild = new BlackTreeNode(left().left().getAttrs(), left().left().key(), left().left().value(), left().left().left(), left().left().right()); + ColorlessTreeNode newRightChild = new BlackTreeNode(getAttrs(), key(), value(), left().right(), right()); + return new RedTreeNode(left().getAttrs(), left().key(), left().value(), newLeftChild, newRightChild); + } else + if (spin == Rotate.LR) { + ColorlessTreeNode newLeftChild = new BlackTreeNode(left().getAttrs(), left().key(), left().value(), left().left(), left().right().left()); + ColorlessTreeNode newRightChild = new BlackTreeNode(getAttrs(), key(), value(), left().right().right(), right()); + return new RedTreeNode(left().right().getAttrs(), left().right().key(), left().right().value(), newLeftChild, newRightChild); + } + + spin = right().checkRotate(Rotate.R); + if (spin == Rotate.L) { + ColorlessTreeNode newLeftChild = new BlackTreeNode(getAttrs(), key(), value(), left(), right().left()); + ColorlessTreeNode newRightChild = new BlackTreeNode(right().right().getAttrs(), right().right().key(), right().right().value(), right().right().left(), right().right().right()); + return new RedTreeNode(right().getAttrs(), right().key(), right().value(), newLeftChild, newRightChild); + } else + if (spin == Rotate.RL) { + ColorlessTreeNode newLeftChild = new BlackTreeNode(getAttrs(), key(), value(), left(), right().left().left()); + ColorlessTreeNode newRightChild = new BlackTreeNode(right().getAttrs(), right().key(), right().value(), right().left().right(), right().right()); + return new RedTreeNode(right().left().getAttrs(), right().left().key(), right().left().value(), newLeftChild, newRightChild); + } + return this; + } + + @Override + @Test + public int checkDepth(int count, int minCount) { // test method + count++; + minCount = left().checkDepth(count, minCount); + minCount = right().checkDepth(count, minCount); + return minCount; + } + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Wed Jan 04 03:50:31 2017 +0900 @@ -1,7 +1,9 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; +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.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; +import org.junit.Test; import java.nio.ByteBuffer; @@ -12,10 +14,11 @@ private String balanceKey; private ByteBuffer value; + private TreeMap<String, ByteBuffer> attrs; private ColorlessTreeNode leftChild; private ColorlessTreeNode rightChild; - - public ColorlessTreeNode (String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { + public ColorlessTreeNode (TreeMap<String,ByteBuffer> attrs, String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { + this.attrs = attrs; this.balanceKey = balanceKey; this.value = value; this.leftChild = left; @@ -38,8 +41,15 @@ return value; } + public TreeMap<String,ByteBuffer> getAttrs(){ + return attrs; + } + @Override - public abstract TreeNodeChildren getChildren(); + public abstract RedBlackTreeNodeChildren getChildren(); + + @Override + public abstract RedBlackTreeNodeAttribute getAttributes(); public abstract ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode right); @@ -47,14 +57,37 @@ public abstract boolean empty(); + public ColorlessTreeNode addNewChild(ColorlessTreeNode newChild) { if (this.empty()) { return createNode(newChild, leftChild,rightChild); } - // int compare = this.compareTo() - // if () + int compare = this.compareTo(newChild); + if (compare > 0) { + ColorlessTreeNode newNode = rightChild.addNewChild(newChild); + newNode = createNode(this, left(),newNode); + return newNode.insBalance(); + } else if (compare < 0) { + ColorlessTreeNode newNode = leftChild.addNewChild(newChild); + newNode = createNode(this, newNode,right()); + return newNode.insBalance(); + } else { + return null; + } + } - return null; - } + protected abstract ColorlessTreeNode insBalance(); + + public abstract Rotate checkRotate(Rotate side); + + @Test + /** + * test用のmethod + * rootを木から取得して + * ColorlessTreeNodeにキャストして呼び出す + */ + public abstract int checkDepth(int count, int minCount); + + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/EmptyTreeNode.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/EmptyTreeNode.java Wed Jan 04 03:50:31 2017 +0900 @@ -1,25 +1,30 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; +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.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeAttributes; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; +import org.junit.Assert; +import org.junit.Test; + +import java.nio.ByteBuffer; + public class EmptyTreeNode extends ColorlessTreeNode { public EmptyTreeNode() { - super(null, null, null, null); + super(null,null, null, null, null); } @Override - public TreeNodeChildren getChildren() { - return new RedTreeNodeChildren(this,null); + public RedBlackTreeNodeChildren getChildren() { + return new RedBlackTreeNodeChildren(this,null); } @Override - public TreeNodeAttributes getAttributes() { + public RedBlackTreeNodeAttribute getAttributes() { return null; //使わない } @@ -52,10 +57,33 @@ public boolean empty(){ return true; } + + @Override + protected ColorlessTreeNode insBalance() { + return this; + } + + @Override + public Rotate checkRotate(Rotate side) { + return Rotate.N; + } + @Override public ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode right) { - TreeNodeChildren children = newChild.getChildren(); - //children.addNewChildAt(); - return null;//new RedTreeNode(attrs, key, value, left, right); + TreeMap<String,ByteBuffer> attrs = getAttrs() != null ? getAttrs() : new TreeMap<String,ByteBuffer>(); + String key = newChild.key(); + ByteBuffer value = newChild.value(); + return new RedTreeNode(attrs, key, value, new EmptyTreeNode(), new EmptyTreeNode()); + } + + @Override + @Test + public int checkDepth(int count, int minCount) { // test method + if (count < minCount | minCount == 0) + minCount = count; + System.out.println("depth = " + count); + + Assert.assertTrue(count <= 2 * minCount); + return minCount; } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java Wed Jan 04 03:50:31 2017 +0900 @@ -14,7 +14,11 @@ * Created by e115731 on 2017/01/03. */ public class RedBlackTreeNodeAttribute implements TreeNodeAttributes{ + + private final TreeMap<String, ByteBuffer> attrs; + public RedBlackTreeNodeAttribute(TreeNode leftChild, TreeNode rightChild, TreeMap<String, ByteBuffer> attrs) { + this.attrs = attrs; } @Override @@ -51,4 +55,5 @@ public Iterator<String> getFilteringKey(List<String> filter) { return null; } + }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Wed Jan 04 03:50:31 2017 +0900 @@ -0,0 +1,109 @@ +package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; + +import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; +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; +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; +import java.util.Iterator; + +/** + * Created by e115731 on 2017/01/03. + */ +public class RedBlackTreeNodeChildren implements TreeNodeChildren { + + private final ColorlessTreeNode node; + private final TreeMap<String, ByteBuffer> attrs; + + public RedBlackTreeNodeChildren(ColorlessTreeNode node, TreeMap<String, ByteBuffer> attrs) { + this.node = node; + this.attrs = attrs; + } + + private boolean boundaryCheck(int _pos) { + int size = size(); + return size >= _pos && _pos >= 0; + } + + + /** + * 赤黒木ではノード単体の追加は行わない + * なので下2つのaddNewChildAtは使われない + * ここをなんとかしたかった + */ + @Override + public Either<Error, TreeNode> addNewChildAt(int pos) { + return null; + } + + @Override + public Either<Error, TreeNode> addNewChildAt(int pos, TreeNode newChild) { + return null; + } + + + @Override + public Either<Error, TreeNode> addNewChildAndPutAttribtue(int pos, String key, ByteBuffer value) { + ColorlessTreeNode newChild = new RedTreeNode(key, value); + ColorlessTreeNode newNode = node.addNewChild(newChild); + if (newNode.isRed()) { + ColorlessTreeNode newRoot = new BlackTreeNode(newNode); + return DefaultEither.newB(newRoot); + } + return DefaultEither.newB(newNode); + } + + + @Override + public Either<Error, TreeNode> deleteChildAt(int pos) { + return null; + } + + @Override + public Either<Error, TreeNode> replaceNode(int pos, TreeNode replacement) { + return null; + } + + @Override + public Either<Error, TreeNode> moveChild(int pos, String move) { + return null; + } + + @Override + public Either<Error, TreeNode> at(int pos) { + if (!boundaryCheck(pos)) { + return DefaultEither.newA(NodeEditorError.INDEX_OUT_OF_BOUNDS); + } + if (pos == 0) { + if (!node.left().empty()) { + ColorlessTreeNode child = node.left(); + return DefaultEither.newB(child); + } else { + ColorlessTreeNode child = node.right(); + return DefaultEither.newB(child); + } + } else { + ColorlessTreeNode child = node.right(); + return DefaultEither.newB(child); + } + } + + @Override + public int size() { + int childrenCount = 0; + if (!node.right().empty()) + childrenCount++; + if (!node.left().empty()) + childrenCount++; + return childrenCount; + } + + @Override + public Iterator<TreeNode> iterator() { + return null; + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNode.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNode.java Wed Jan 04 03:50:31 2017 +0900 @@ -1,39 +1,30 @@ package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; -import jp.ac.u_ryukyu.ie.cr.jungle.data.list.List; +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.transaction.node.TreeNode; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeAttributes; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren; 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 org.junit.Test; import java.nio.ByteBuffer; import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.TreeNodeError.NOT_USE_METHOD; public class RedTreeNode extends ColorlessTreeNode { - private TreeMap<String, ByteBuffer> attrs; - - private static final List<TreeNode> NIL_LIST = new List<>(); public RedTreeNode(String balanceKey, ByteBuffer value) { this(new TreeMap<>(), balanceKey, value, new EmptyTreeNode(), new EmptyTreeNode()); } - public RedTreeNode(String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { - this(new TreeMap<>(), balanceKey, value, left, right); - } - public RedTreeNode(TreeMap<String, ByteBuffer> _attrs, String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { - super(balanceKey, value, left, right); - this.attrs = _attrs; + super(_attrs,balanceKey, value, left, right); } @Override - public TreeNodeChildren getChildren() { - return new RedTreeNodeChildren(this, attrs); + public RedBlackTreeNodeChildren getChildren() { + return new RedBlackTreeNodeChildren(this, getAttrs()); } @Override @@ -41,12 +32,12 @@ String key = newChild.key(); ByteBuffer value = newChild.value(); //newChild.getAttributes(). - return new RedTreeNode(attrs, key, value, left, right); + return new RedTreeNode(getAttrs(), key, value, left, right); } @Override - public TreeNodeAttributes getAttributes() { - return new RedBlackTreeNodeAttribute(left(), right(), attrs); + public RedBlackTreeNodeAttribute getAttributes() { + return new RedBlackTreeNodeAttribute(left(), right(), getAttrs()); } @Override @@ -55,7 +46,7 @@ } public TreeNode clone() { - return new BlackTreeNode(attrs, key(), value(), left(), right()); + return new BlackTreeNode(getAttrs(), key(), value(), left(), right()); } @Override @@ -79,8 +70,42 @@ } @Override - public boolean empty(){ + public boolean empty() { return false; } + @Override + protected ColorlessTreeNode insBalance() { + return this; + } + + @Override + public Rotate checkRotate(Rotate side) { + if (side == Rotate.L) { + if (left().isRed()) + return Rotate.R; + else + if (right().isRed()) + return Rotate.LR; + return Rotate.N; + } else { + if (left().isRed()) + return Rotate.RL; + else + if (right().isRed()) + return Rotate.L; + return Rotate.N; + } + } + + + @Override + @Test + public int checkDepth(int count, int minCount) { // test method + count++; + minCount = left().checkDepth(count, minCount); + minCount = right().checkDepth(count, minCount); + return minCount; + } + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNodeChildren.java Tue Jan 03 21:27:55 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,80 +0,0 @@ -package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; - -import jp.ac.u_ryukyu.ie.cr.jungle.data.treemap.TreeMap; -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.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; -import java.util.Iterator; - -/** - * Created by e115731 on 2017/01/03. - */ -public class RedTreeNodeChildren implements TreeNodeChildren { - - private final ColorlessTreeNode node; - private final TreeMap<String, ByteBuffer> attrs; - - public RedTreeNodeChildren(ColorlessTreeNode node, TreeMap<String, ByteBuffer> attrs) { - this.node = node; - this.attrs = attrs; - } - - - /** - * 赤黒木ではノード単体の追加は行わない - * なので下2つのaddNewChildAtは使われない - * ここをなんとかしたかった - */ - @Override - public Either<Error, TreeNode> addNewChildAt(int pos) { - return null; - } - - @Override - public Either<Error, TreeNode> addNewChildAt(int pos, TreeNode newChild) { - return null; - } - - - @Override - public Either<Error, TreeNode> addNewChildAndPutAttribtue(int pos, String key, ByteBuffer value) { - ColorlessTreeNode newChild = new RedTreeNode(key,value); - ColorlessTreeNode newNode = node.addNewChild(newChild); - return DefaultEither.newB(newNode); - } - - - @Override - public Either<Error, TreeNode> deleteChildAt(int pos) { - return null; - } - - @Override - public Either<Error, TreeNode> replaceNode(int pos, TreeNode replacement) { - return null; - } - - @Override - public Either<Error, TreeNode> moveChild(int pos, String move) { - return null; - } - - @Override - public Either<Error, TreeNode> at(int pos) { - return null; - } - - @Override - public int size() { - return 0; - } - - @Override - public Iterator<TreeNode> iterator() { - return null; - } -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/RedBlackJungleTree.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/tree/RedBlackJungleTree.java Wed Jan 04 03:50:31 2017 +0900 @@ -5,9 +5,11 @@ 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; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.manager.DefaultTransactionManager; +import jp.ac.u_ryukyu.ie.cr.jungle.transaction.manager.RedBlackTreeTransactionManager; 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 org.junit.Test; import java.util.concurrent.atomic.AtomicReference; @@ -30,9 +32,16 @@ ChangeListWriter writer = super.getWriter(); String uuid = super.getUuid(); TreeEditor treeEditor = super.getTreeEditor(); - TransactionManager txManager = new DefaultTransactionManager(writer, tc, repository, uuid); + TransactionManager txManager = new RedBlackTreeTransactionManager(writer, tc, repository, uuid); TreeNode root = tc.getRoot(); return new RedBlackJungleTreeEditor(root, balanceKey, txManager, treeEditor); } + + @Test + public void checkDepth() { + ColorlessTreeNode root = (ColorlessTreeNode) getRootNode(); + root.checkDepth(0, 0); + System.out.println("-----------------------------------"); + } }
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java Tue Jan 03 21:27:55 2017 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java Wed Jan 04 03:50:31 2017 +0900 @@ -2,23 +2,52 @@ import jp.ac.u_ryukyu.ie.cr.jungle.DefaultJungle; import jp.ac.u_ryukyu.ie.cr.jungle.Jungle; +import jp.ac.u_ryukyu.ie.cr.jungle.query.JungleNodeIterator; 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.editor.jungleTreeEditor.JungleTreeEditor; +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.traverser.DefaultTraverser; import jp.ac.u_ryukyu.ie.cr.jungle.tree.JungleTree; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Either; +import jp.ac.u_ryukyu.ie.cr.jungle.util.Error.Error; +import org.junit.Assert; import org.junit.Test; +import java.nio.ByteBuffer; + public class RedBlackTreeEditorTest { + + String key = "balanceKey"; + @Test public void RedBlackTreeEditor() { Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); JungleTree tree = jungle.createNewRedBlackTree("TreeName", "balanceKey"); - JungleTreeEditor editor = tree.getJungleTreeEditor(); NodePath path = new DefaultNodePath(); - //Either<Error, JungleTreeEditor> either = editor.addNewChildAt(path, 0); - // Assert.assertFalse(either.isA()); - // editor = either.b(); - // editor.addNewChildAt(path,0); + + for (int count = 1; count <= 10000; count++) { + JungleTreeEditor editor = tree.getJungleTreeEditor(); + ByteBuffer value = ByteBuffer.wrap(("value" + count).getBytes()); + Either<Error, JungleTreeEditor> either = editor.addNewChildAndPutAttribute(path, 0, key, value); + Assert.assertFalse(either.isA()); + editor = either.b(); + either = editor.success(); + Assert.assertFalse(either.isA()); + + TreeNode rootNode = tree.getRootNode(); + JungleNodeIterator iterator = new JungleNodeIterator(rootNode); + int nodeCount = 0; + while (iterator.hasNext()) { + nodeCount++; + iterator.next(); + } + int expectCount = count; + Assert.assertEquals(expectCount, nodeCount); + + ColorlessTreeNode rootNode2 = (ColorlessTreeNode)rootNode; //test用methodを使うためにcastしている + rootNode2.checkDepth(0,0); + } } }