Mercurial > hg > Members > shoshi > jungle > jungle-core
changeset 295:1a5f3d3f3437
add RedBlackTree delete un fix
line wrap: on
line diff
--- a/memo.txt Wed Jan 04 05:17:13 2017 +0900 +++ b/memo.txt Wed Jan 04 19:12:26 2017 +0900 @@ -1,3 +1,15 @@ +2017/1/3 + + Indexの差分Updateを実装した + Nodeのdeleteにはまだ対応していないので、後で修正する + 各EditorにdeleteChild(path,int,key,value)を入れた + これは赤黒木の削除に使うためである + 他のEditorには実装していないので論文が落ち着いたら実装する + 処理的には pathとintで指定したNodeがkeyとvalueのペアを持っていれば削除する + ぐらいでいきたい + redBlackTreeのEditorのinterfaceをどうするか？ + DifferenceTreeとRedBlackTreeをJungleNetWorkに実装する必要がある + 今はDefaultJungleにしか実装されていない Thu Nov 17 18:36:13 JST 2016 差分List
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/benchMark/JungleTreeCreater.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/benchMark/JungleTreeCreater.java Wed Jan 04 19:12:26 2017 +0900 @@ -56,8 +56,8 @@ int count = 1; //深さを決めるために使う。 int currentNodeCount = 1; for (; count < maxNodeCount; i++) { - count = count + (currentNodeCount * 3); - currentNodeCount = currentNodeCount * 3; + count = count + (currentNodeCount * 2); + currentNodeCount = currentNodeCount * 2; } return i; }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/DefaultJungle.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/DefaultJungle.java Wed Jan 04 19:12:26 2017 +0900 @@ -153,7 +153,7 @@ } @Override - public JungleTree createNewRedBlackTree(String name, String balanceKey) { + public JungleTree createNewRedBlackTree(String treeName, String balanceKey) { ChangeList list = new ChangeList() { @Override public Iterator<TreeOperation> iterator() { @@ -168,7 +168,7 @@ @Override public String getTreeName() { - return name; + return treeName; } @Override @@ -179,29 +179,27 @@ }; TreeNode rootNode = new EmptyTreeNode(); InterfaceTraverser traverser = new InterfaceTraverser(rootNode, true); - TreeContext tc = new DefaultTreeContext(rootNode, null, list, uuid, name, 0, traverser); + TreeContext tc = new DefaultTreeContext(rootNode, null, list, uuid, treeName, 0, traverser); JungleTree newTree = new RedBlackJungleTree(tc, uuid, journal.getWriter(), redBlackTreeEditor, balanceKey); - if (trees.putIfAbsent(name, newTree) != null) { + if (trees.putIfAbsent(treeName, newTree) != null) { return null; } return newTree; } - - @Override - public Iterator<String> getTreeNames() { - Enumeration<String> treeNames = trees.keys(); - return new Iterator<String>() { + @Override public Iterator<String> getTreeNames () { + Enumeration<String> treeNames = trees.keys(); + return new Iterator<String>() { - @Override - public boolean hasNext() { - return treeNames.hasMoreElements(); - } + @Override + public boolean hasNext() { + return treeNames.hasMoreElements(); + } - @Override - public String next() { - return treeNames.nextElement(); - } - }; + @Override + public String next() { + return treeNames.nextElement(); + } + }; + } } -}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/Jungle.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/Jungle.java Wed Jan 04 19:12:26 2017 +0900 @@ -21,4 +21,5 @@ public Iterator<String> getTreeNames(); public JungleTree createNewRedBlackTree(String treeName, String balanceKey); + }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/list/List.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/list/List.java Wed Jan 04 19:12:26 2017 +0900 @@ -32,7 +32,8 @@ public List<T> add(int num, T attribute) { Node<T> newHead = head.add(0, num, attribute); - if (newHead == null) return this; + if (newHead == null) + return this; return new List<>(newHead); } @@ -46,7 +47,8 @@ int count = 0; Node<T> currentNode = head.getNext(); while (currentNode != null) { - if (count == index) return currentNode.getAttribute(); + if (count == index) + return currentNode.getAttribute(); currentNode = currentNode.getNext(); count++; } @@ -95,19 +97,22 @@ public List<T> delete(int num) { Node<T> newNode = head.delete(0, num); - if (newNode == null) return this; + if (newNode == null) + return this; return new List<>(newNode); } public List<T> delete(T node) { Node<T> newNode = head.delete(node); - if (newNode == null) return this; + if (newNode == null) + return this; return new List<>(newNode); } public List<T> replace(int num, T attribute) { Node<T> newHead = head.replaceNode(0, num, attribute); - if (newHead == null) return this; + if (newHead == null) + return this; return new List<>(newHead); } @@ -137,8 +142,10 @@ Iterator<T> iterator = iterator(); while (true) { pathString += iterator.next(); - if (iterator.hasNext()) pathString += ","; - else break; + if (iterator.hasNext()) + pathString += ","; + else + break; } pathString += ">"; return pathString;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/logger/LoggingChildren.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/logger/LoggingChildren.java Wed Jan 04 19:12:26 2017 +0900 @@ -10,70 +10,69 @@ import java.nio.ByteBuffer; -public class LoggingChildren -{ - private final TreeNode wrap; - private final OperationLog log; - - public LoggingChildren(TreeNode _wrap,OperationLog _log) - { - wrap = _wrap; - log = _log; - } +public class LoggingChildren { + private final TreeNode wrap; + private final OperationLog log; + + public LoggingChildren(TreeNode _wrap, OperationLog _log) { + wrap = _wrap; + log = _log; + } + + public int size() { + Children children = wrap.getChildren(); + return children.size(); + } - public int size() - { - Children children = wrap.getChildren(); - return children.size(); - } - - public Either<Error,LoggingNode> edit(NodeOperation _op) - { - Either<Error,TreeNode> either = _op.invoke(wrap); - if(either.isA()){ - return DefaultEither.newA(either.a()); - } - - TreeNode newWrap = either.b(); - OperationLog newLog = log.add(_op); - LoggingNode newLoggingNode = new LoggingNode(newWrap,newLog); - return DefaultEither.newB(newLoggingNode); - } - - public Either<Error,LoggingNode> addNewChildAt(final int _pos) - { - NodeOperation addNewChildAt = new AppendChildAtOperation(_pos); - return edit(addNewChildAt); - } + public Either<Error, LoggingNode> edit(NodeOperation _op) { + Either<Error, TreeNode> either = _op.invoke(wrap); + if (either.isA()) { + return DefaultEither.newA(either.a()); + } + + TreeNode newWrap = either.b(); + OperationLog newLog = log.add(_op); + LoggingNode newLoggingNode = new LoggingNode(newWrap, newLog); + return DefaultEither.newB(newLoggingNode); + } + + public Either<Error, LoggingNode> addNewChildAt(final int _pos) { + NodeOperation addNewChildAt = new AppendChildAtOperation(_pos); + return edit(addNewChildAt); + } - public Either<Error,LoggingNode> addNewChildAndPutAttribute(int pos, String key, ByteBuffer value) { - NodeOperation addnewChildAndPutAttribute = new AddNewChildAndPutAttribute(pos, key, value); - return edit(addnewChildAndPutAttribute); - } + public Either<Error, LoggingNode> addNewChildAndPutAttribute(int pos, String key, ByteBuffer value) { + NodeOperation addnewChildAndPutAttribute = new AddNewChildAndPutAttribute(pos, key, value); + return edit(addnewChildAndPutAttribute); + } - public Either<Error,LoggingNode> deleteChildAt(final int _pos) - { - NodeOperation deleteChildAt = new DeleteChildAtOperation(_pos); - return edit(deleteChildAt); - } + public Either<Error, LoggingNode> deleteChildAt(final int pos) { + NodeOperation deleteChildAt = new DeleteChildAtOperation(pos); + return edit(deleteChildAt); + } - public Either<Error,LoggingNode> moveChild(String move, int childNum) { - NodeOperation moveChild = new ChildMoveOperation(move,childNum); - return edit(moveChild); - } + public Either<Error, LoggingNode> redBlackTreeDeleteChildAt(String key, ByteBuffer value) { + NodeOperation deleteChildAt = new RedBlackTreeDeleteChildAtOperation(key, value); + return edit(deleteChildAt); + + } + + public Either<Error, LoggingNode> moveChild(String move, int childNum) { + NodeOperation moveChild = new ChildMoveOperation(move, childNum); + return edit(moveChild); + } - public Either<Error,LoggingNode> at(int _pos) - { - Children children = wrap.getChildren(); - Either<Error,TreeNode> either = children.at(_pos); - if(either.isA()){ - return DefaultEither.newA(either.a()); - } - - TreeNode node = either.b(); - LoggingNode logNode = new LoggingNode(node); - return DefaultEither.newB(logNode); - } + public Either<Error, LoggingNode> at(int _pos) { + Children children = wrap.getChildren(); + Either<Error, TreeNode> either = children.at(_pos); + if (either.isA()) { + return DefaultEither.newA(either.a()); + } + + TreeNode node = either.b(); + LoggingNode logNode = new LoggingNode(node); + return DefaultEither.newB(logNode); + } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/operations/AddNewChildAndPutAttribute.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/operations/AddNewChildAndPutAttribute.java Wed Jan 04 19:12:26 2017 +0900 @@ -11,9 +11,9 @@ public class AddNewChildAndPutAttribute implements NodeOperation { - private String key; - private ByteBuffer value; - private int pos; + private final String key; + private final ByteBuffer value; + private final int pos; public AddNewChildAndPutAttribute(int pos, String key, ByteBuffer value) { this.key = key;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/operations/RedBlackTreeDeleteChildAtOperation.java Wed Jan 04 19:12:26 2017 +0900 @@ -0,0 +1,49 @@ +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.transaction.node.TreeNode; +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 java.nio.ByteBuffer; + +/** + * Created by e115731 on 2017/01/04. + */ +public class RedBlackTreeDeleteChildAtOperation implements NodeOperation { + + private String key; + private ByteBuffer value; + + public RedBlackTreeDeleteChildAtOperation(String key, ByteBuffer value) { + this.key = key; + this.value = value; + } + + @Override + public Command getCommand() { + return Command.APPEND_CHILD_AND_PUT_ATTRIBUTE; + } + + @Override + public Either<Error, TreeNode> invoke(TreeNode target) { + TreeNodeChildren children = target.getChildren(); + return children.matchingChildDeleteAt(key, value); + } + + @Override + public int getPosition() { + return -2; + } + + @Override + public String getKey() { + return null; + } + + @Override + public ByteBuffer getValue() { + return null; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/store/trasnformer/RedBlackTreeDeleteChildAt.java Wed Jan 04 19:12:26 2017 +0900 @@ -0,0 +1,48 @@ +package jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer; + +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.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; + + public RedBlackTreeDeleteChildAt(String key, ByteBuffer value) { + this.key = key; + this.value = value; + } + + public Either<Error, LoggingNode> _edit(LoggingNode logNode) { + Either<Error, LoggingNode> either = logNode.getChildren().redBlackTreeDeleteChildAt(key, value); + if (either.isA()) { + // error + return either; + } + return DefaultEither.newB(either.b()); + } + + @Override + public Either<Error, LoggingNode> edit(TreeNode _e) { + LoggingNode logNode = wrap(_e); + return _edit(logNode); + } + + public LoggingNode wrap(TreeNode node) { + return new LoggingNode(node); + } + + @Override + public LoggingNode wrap(TreeNode newRoot, TreeNode editedNode, OperationLog operationLog) { + return new LoggingNode(newRoot, editedNode, operationLog); + } + +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/DefaultJungleTreeEditor.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/DefaultJungleTreeEditor.java Wed Jan 04 19:12:26 2017 +0900 @@ -93,6 +93,11 @@ } @Override + public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos, String Key, ByteBuffer value) { + return null; //未実装 + } + + @Override public Either<Error, JungleTreeEditor> putAttribute(NodePath _path, String _key, ByteBuffer _value) { PutAttribute putAttribute = new PutAttribute(_key, _value); return _edit(_path, putAttribute);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/DifferenceJungleTreeEditor.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/DifferenceJungleTreeEditor.java Wed Jan 04 19:12:26 2017 +0900 @@ -111,6 +111,11 @@ } @Override + public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos, String Key, ByteBuffer value) { + return null; //未実装 + } + + @Override public Either<Error, JungleTreeEditor> putAttribute(NodePath _path, String _key, ByteBuffer _value) { PutAttribute putAttribute = new PutAttribute(_key, _value); return _edit(_path, putAttribute);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/JungleTreeEditor.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/JungleTreeEditor.java Wed Jan 04 19:12:26 2017 +0900 @@ -15,6 +15,8 @@ public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos); + public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos, String Key, ByteBuffer value); + public Either<Error, JungleTreeEditor> putAttribute(NodePath path, String key, ByteBuffer value); public Either<Error, JungleTreeEditor> deleteAttribute(NodePath path, String key);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/RedBlackJungleTreeEditor.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/editor/jungleTreeEditor/RedBlackJungleTreeEditor.java Wed Jan 04 19:12:26 2017 +0900 @@ -10,8 +10,7 @@ import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.DefaultTreeOperation; import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.NodeOperation; import jp.ac.u_ryukyu.ie.cr.jungle.store.operations.TreeOperation; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.AppendChildAndPutAttribute; -import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.NodeEditor; +import jp.ac.u_ryukyu.ie.cr.jungle.store.trasnformer.*; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.editor.treeEditor.TreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.manager.TransactionManager; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; @@ -22,6 +21,7 @@ import java.nio.ByteBuffer; +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.JungleTreeError.NOT_USE_METHOD; @@ -33,16 +33,16 @@ private final List<TreeNode> editedNodeList; private final String balanceKey; - public RedBlackJungleTreeEditor(TreeNode _root, String balanceKey, TransactionManager _txManager, TreeEditor _editor) { - this(_root, balanceKey, _txManager, _editor, new DefaultTreeOperationLog(), new List<>()); + public RedBlackJungleTreeEditor(TreeNode root, String balanceKey, TransactionManager txManager, TreeEditor editor) { + this(root, balanceKey, txManager, editor, new DefaultTreeOperationLog(), new List<>()); } - public RedBlackJungleTreeEditor(TreeNode newNode, String balanceKey, TransactionManager _txManager, TreeEditor _editor, TreeOperationLog _log, List<TreeNode> editedNodeList) { + public RedBlackJungleTreeEditor(TreeNode newNode, String balanceKey, TransactionManager txManager, TreeEditor editor, TreeOperationLog log, List<TreeNode> editedNodeList) { this.root = newNode; - this.txManager = _txManager; - this.editor = _editor; - this.log = _log; + this.txManager = txManager; + this.editor = editor; + this.log = log; this.editedNodeList = editedNodeList; this.balanceKey = balanceKey; } @@ -82,8 +82,8 @@ @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); + AppendChildAndPutAttribute appendChildAndPutAttribute = new AppendChildAndPutAttribute(key, value, pos); + return _edit(path, appendChildAndPutAttribute); } @Override @@ -94,26 +94,38 @@ } @Override - public Either<Error, JungleTreeEditor> deleteChildAt(NodePath _path, int _pos) { - //DeleteChildAt deleteChildAt = new DeleteChildAt(_pos); - //return _edit(_path, deleteChildAt); - return null; + 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); + } + + @Override + public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos, String key, ByteBuffer value) { + 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); //未実装 } @Override public Either<Error, JungleTreeEditor> putAttribute(NodePath _path, String _key, ByteBuffer _value) { - //PutAttribute putAttribute = new PutAttribute(_key, _value); - // return _edit(_path, putAttribute); - return null; + if (_key.equals(balanceKey)) + return DefaultEither.newA(INVALID_ARGUMENT); + PutAttribute putAttribute = new PutAttribute(_key, _value); + return _edit(_path, putAttribute); } @Override public Either<Error, JungleTreeEditor> deleteAttribute(NodePath _path, String _key) { - // DeleteAttribute deleteAttribute = new DeleteAttribute(_key); - // return _edit(_path, deleteAttribute); - return null; + if (_key.equals(balanceKey)) + return DefaultEither.newA(INVALID_ARGUMENT); + DeleteAttribute deleteAttribute = new DeleteAttribute(_key); + return _edit(_path, deleteAttribute); } + @Override public Either<Error, JungleTreeEditor> moveChild(NodePath path, int childNum, String move) { return DefaultEither.newA(NOT_USE_METHOD); //赤黒木だから使わない @@ -138,7 +150,7 @@ } TransactionManager newTxManager = either.b(); - JungleTreeEditor newTreeEditor = new RedBlackJungleTreeEditor(root,balanceKey, newTxManager, editor); + JungleTreeEditor newTreeEditor = new RedBlackJungleTreeEditor(root, balanceKey, newTxManager, editor); return DefaultEither.newB(newTreeEditor); }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/manager/DefaultTransactionManager.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/manager/DefaultTransactionManager.java Wed Jan 04 19:12:26 2017 +0900 @@ -66,8 +66,8 @@ Index index = tip.getIndex(); ParentIndex parentIndex = tip.getParentIndex(); InterfaceTraverser traverser = new InterfaceTraverser(newRoot, index, parentIndex, true); - //traverser.updateIndex(editNodeList); - traverser.createIndex(); + traverser.updateIndex(editNodeList); + //traverser.createIndex(); TreeContext newTreeContext = new DefaultTreeContext(newRoot, tip, list, uuid, _treeName, nextRevision, traverser); if (repository.compareAndSet(newTreeContext.prev(), newTreeContext)) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java Wed Jan 04 19:12:26 2017 +0900 @@ -81,6 +81,12 @@ return DefaultEither.newB(newNode); } + + @Override + public Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value) { + return null; // 未使用 + } + @Override public int size() { return children.length();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Differencial/DifferencialTreeNodeChildren.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Differencial/DifferencialTreeNodeChildren.java Wed Jan 04 19:12:26 2017 +0900 @@ -54,6 +54,12 @@ return DefaultEither.newB(node); } + + @Override + public Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value) { + return null; //未使用 + } + @Override public int size() { return children.size();
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/TreeNodeChildren.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/TreeNodeChildren.java Wed Jan 04 19:12:26 2017 +0900 @@ -6,12 +6,18 @@ import java.nio.ByteBuffer; -public interface TreeNodeChildren extends Children -{ - public Either<Error,TreeNode> addNewChildAt(int pos); - public Either<Error,TreeNode> deleteChildAt(int pos); - public Either<Error,TreeNode> addNewChildAt(int pos,TreeNode newChild); - public Either<Error,TreeNode> replaceNode(int pos,TreeNode replacement); - Either<Error,TreeNode> moveChild(int pos, String move); - Either<Error,TreeNode> addNewChildAndPutAttribtue(int pos, String key,ByteBuffer value); +public interface TreeNodeChildren extends Children { + public Either<Error, TreeNode> addNewChildAt(int pos); + + public Either<Error, TreeNode> deleteChildAt(int pos); + + public Either<Error, TreeNode> addNewChildAt(int pos, TreeNode newChild); + + public Either<Error, TreeNode> replaceNode(int pos, TreeNode replacement); + + Either<Error, TreeNode> moveChild(int pos, String move); + + Either<Error, TreeNode> addNewChildAndPutAttribtue(int pos, String key, ByteBuffer value); + + Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value); } \ No newline at end of file
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/BlackTreeNode.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/BlackTreeNode.java Wed Jan 04 19:12:26 2017 +0900 @@ -29,12 +29,12 @@ @Override public RedBlackTreeNodeAttribute getAttributes() { - return new RedBlackTreeNodeAttribute(left(), right(), getAttrs()); + return new RedBlackTreeNodeAttribute(left(), right(), getAttrs(),key(),value()); } @Override - public ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode right) { - return new BlackTreeNode(newChild.getAttrs(),newChild.key(),newChild.value(),left,right); + public ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right) { + return new BlackTreeNode(newAttrs,insertKey,insertValue,left,right); } @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java Wed Jan 04 19:12:26 2017 +0900 @@ -17,7 +17,8 @@ private TreeMap<String, ByteBuffer> attrs; private ColorlessTreeNode leftChild; private ColorlessTreeNode rightChild; - public ColorlessTreeNode (TreeMap<String,ByteBuffer> attrs, 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; @@ -27,11 +28,15 @@ public ColorlessTreeNode left() { return leftChild; - }; + } + + ; public ColorlessTreeNode right() { return rightChild; - }; + } + + ; public String key() { return balanceKey; @@ -41,7 +46,7 @@ return value; } - public TreeMap<String,ByteBuffer> getAttrs(){ + public TreeMap<String, ByteBuffer> getAttrs() { return attrs; } @@ -51,30 +56,35 @@ @Override public abstract RedBlackTreeNodeAttribute getAttributes(); - public abstract ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode right); + public abstract ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right); public abstract boolean isRed(); public abstract boolean empty(); + private int compare(ByteBuffer value) { + return value().hashCode() - value.hashCode(); + } - public ColorlessTreeNode addNewChild(ColorlessTreeNode newChild) { + public ColorlessTreeNode addNewChild(String insertKey, ByteBuffer insertValue) { if (this.empty()) { - return createNode(newChild, leftChild,rightChild); + TreeMap<String, ByteBuffer> newAttrs = new TreeMap<>(); + return createNode(newAttrs, insertKey, insertValue, leftChild, rightChild); } - int compare = this.compareTo(newChild); - if (compare > 0) { - ColorlessTreeNode newNode = rightChild.addNewChild(newChild); - newNode = createNode(this, left(),newNode); + int result = this.compare(insertValue); + if (result > 0) { + ColorlessTreeNode newNode = rightChild.addNewChild(insertKey, insertValue); + newNode = createNode(getAttrs(), key(), value(), 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; - } + } else + if (result < 0) { + ColorlessTreeNode newNode = leftChild.addNewChild(insertKey, insertValue); + newNode = createNode(getAttrs(), key(), value(), newNode, right()); + return newNode.insBalance(); + } else { + return null; + } } protected abstract ColorlessTreeNode insBalance(); @@ -86,8 +96,32 @@ * test用のmethod * rootを木から取得して * ColorlessTreeNodeにキャストして呼び出す - */ - public abstract int checkDepth(int count, int minCount); + */ public abstract int checkDepth(int count, int minCount); + public RebuildNode delete(String insertKey, ByteBuffer insertValue, ColorlessTreeNode parent, Rotate side) { + if (!this.empty()) { + RebuildNode rebuildNode; + int result = this.compare(insertValue); + if (result > 0) { + rebuildNode = right().delete(insertKey, insertValue, this, Rotate.R); + } else + if (result < 0) { + rebuildNode = left().delete(insertKey, insertValue, this, Rotate.L); + } else { + rebuildNode = replaceNode(parent); + if (parent == null || rebuildNode == null) + return rebuildNode; + ColorlessTreeNode node = rebuildNode.getNode(); + if (rebuildNode.rebuild()) { + // return node.deleteBalance(parent); + } + } return null; + } + return null; + } + + protected RebuildNode replaceNode(ColorlessTreeNode parent) { + return null; + } }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/EmptyTreeNode.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/EmptyTreeNode.java Wed Jan 04 19:12:26 2017 +0900 @@ -11,16 +11,15 @@ import java.nio.ByteBuffer; - public class EmptyTreeNode extends ColorlessTreeNode { public EmptyTreeNode() { - super(null,null, null, null, null); + super(null, null, null, null, null); } @Override public RedBlackTreeNodeChildren getChildren() { - return new RedBlackTreeNodeChildren(this,null); + return new RedBlackTreeNodeChildren(this, null); } @Override @@ -49,12 +48,12 @@ } @Override - public boolean isRed(){ + public boolean isRed() { return false; } @Override - public boolean empty(){ + public boolean empty() { return true; } @@ -69,11 +68,10 @@ } @Override - public ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode 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()); + public ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right) { + if (newAttrs == null) + newAttrs = new TreeMap<>(); + return new RedTreeNode(newAttrs, insertKey, insertValue, new EmptyTreeNode(), new EmptyTreeNode()); } @Override
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RebuildNode.java Wed Jan 04 19:12:26 2017 +0900 @@ -0,0 +1,26 @@ +package jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.redBlackTree; + +/** + * Created by e115731 on 2017/01/04. + */ +public class RebuildNode { + private final Boolean rebuild; + private final ColorlessTreeNode node; + + public RebuildNode(Boolean rebuild, ColorlessTreeNode node) { + this.rebuild = rebuild; + this.node = node; + } + + public boolean rebuild(){ + return rebuild; + } + + public ColorlessTreeNode getNode(){ + return node; + } + + public Boolean empty(){ + return node.empty(); + } +}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java Wed Jan 04 19:12:26 2017 +0900 @@ -9,16 +9,21 @@ import java.nio.ByteBuffer; import java.util.Iterator; import java.util.List; +import java.util.Optional; /** * Created by e115731 on 2017/01/03. */ -public class RedBlackTreeNodeAttribute implements TreeNodeAttributes{ +public class RedBlackTreeNodeAttribute implements TreeNodeAttributes { private final TreeMap<String, ByteBuffer> attrs; + private final String balanceKey; + private final ByteBuffer value; - public RedBlackTreeNodeAttribute(TreeNode leftChild, TreeNode rightChild, TreeMap<String, ByteBuffer> attrs) { + public RedBlackTreeNodeAttribute(TreeNode leftChild, TreeNode rightChild, TreeMap<String, ByteBuffer> attrs, String balanceKey, ByteBuffer value) { this.attrs = attrs; + this.balanceKey = balanceKey; + this.value = value; } @Override @@ -33,12 +38,23 @@ @Override public ByteBuffer get(String key) { + if (key == null) { + return null; + } + if (key.equals(balanceKey)) + return value; + + Optional<ByteBuffer> op = attrs.get(key); + if (op.isPresent()) { + return op.get(); + } return null; } @Override public String getString(String key) { - return null; + ByteBuffer value = get(key); + return new String(value.array()); } @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java Wed Jan 04 19:12:26 2017 +0900 @@ -1,5 +1,6 @@ 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.store.trasnformer.NodeEditorError; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; @@ -11,6 +12,8 @@ import java.nio.ByteBuffer; import java.util.Iterator; +import static jp.ac.u_ryukyu.ie.cr.jungle.util.Error.JungleTreeError.INVALID_ARGUMENT; + /** * Created by e115731 on 2017/01/03. */ @@ -38,18 +41,17 @@ @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); + ColorlessTreeNode newNode = node.addNewChild(key,value); if (newNode.isRed()) { ColorlessTreeNode newRoot = new BlackTreeNode(newNode); return DefaultEither.newB(newRoot); @@ -57,6 +59,14 @@ return DefaultEither.newB(newNode); } + @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); + return null; + } + @Override public Either<Error, TreeNode> deleteChildAt(int pos) { @@ -66,12 +76,12 @@ @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) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNode.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedTreeNode.java Wed Jan 04 19:12:26 2017 +0900 @@ -19,7 +19,7 @@ } public RedTreeNode(TreeMap<String, ByteBuffer> _attrs, String balanceKey, ByteBuffer value, ColorlessTreeNode left, ColorlessTreeNode right) { - super(_attrs,balanceKey, value, left, right); + super(_attrs, balanceKey, value, left, right); } @Override @@ -28,16 +28,13 @@ } @Override - public ColorlessTreeNode createNode(ColorlessTreeNode newChild, ColorlessTreeNode left, ColorlessTreeNode right) { - String key = newChild.key(); - ByteBuffer value = newChild.value(); - //newChild.getAttributes(). - return new RedTreeNode(getAttrs(), key, value, left, right); + public ColorlessTreeNode createNode(TreeMap<String, ByteBuffer> newAttrs, String insertKey, ByteBuffer insertValue, ColorlessTreeNode left, ColorlessTreeNode right) { + return new RedTreeNode(newAttrs, insertKey, insertValue, left, right); } @Override public RedBlackTreeNodeAttribute getAttributes() { - return new RedBlackTreeNodeAttribute(left(), right(), getAttrs()); + return new RedBlackTreeNodeAttribute(left(), right(), getAttrs(), key(), value()); } @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/traverser/InterfaceTraverser.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/traverser/InterfaceTraverser.java Wed Jan 04 19:12:26 2017 +0900 @@ -17,7 +17,6 @@ private TreeNode root; private Index index; private ParentIndex parentIndex; - private boolean parentUpdateFlag; private boolean useIndex; public InterfaceTraverser(TreeNode root, boolean indexFlag) { @@ -35,9 +34,6 @@ return index; } - public void commit() { - parentUpdateFlag = false; - } public ParentIndex getParentIndex() { return parentIndex;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/core/NetworkDefaultJungle.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/core/NetworkDefaultJungle.java Wed Jan 04 19:12:26 2017 +0900 @@ -2,19 +2,19 @@ import jp.ac.u_ryukyu.ie.cr.jungle.Jungle; -import jp.ac.u_ryukyu.ie.cr.jungle.tree.JungleTree; 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.Journal; import jp.ac.u_ryukyu.ie.cr.jungle.store.TreeContext; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.editor.treeEditor.TreeEditor; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.DefaultTreeOperationLog; 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.editor.treeEditor.TreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.Default.DefaultTreeNode; +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.tree.JungleTree; import jp.ac.u_ryukyu.ie.cr.jungleNetwork.transaction.NetworkDefaultJungleTree; import java.util.Enumeration;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/persistent/PersistentJungle.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/persistent/PersistentJungle.java Wed Jan 04 19:12:26 2017 +0900 @@ -2,17 +2,17 @@ import jp.ac.u_ryukyu.ie.cr.jungle.Jungle; -import jp.ac.u_ryukyu.ie.cr.jungle.tree.JungleTree; 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.store.TreeContext; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.editor.treeEditor.TreeEditor; -import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode; import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.DefaultTreeOperationLog; 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.editor.treeEditor.TreeEditor; import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.Default.DefaultTreeNode; +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.tree.JungleTree; import java.util.Enumeration; import java.util.Iterator;
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/persistent/PersistentJungleTreeEditor.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/persistent/PersistentJungleTreeEditor.java Wed Jan 04 19:12:26 2017 +0900 @@ -91,6 +91,11 @@ } @Override + public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos, String Key, ByteBuffer value) { + return null; //未実装 + } + + @Override public Either<Error, JungleTreeEditor> moveChild(NodePath path,int childNum, String move) { MoveChild movechild = new MoveChild(move, childNum); return _edit(path,movechild);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/transaction/NetworkDefaultJungleTreeEditor.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungleNetwork/transaction/NetworkDefaultJungleTreeEditor.java Wed Jan 04 19:12:26 2017 +0900 @@ -114,6 +114,11 @@ } @Override + public Either<Error, JungleTreeEditor> deleteChildAt(NodePath path, int pos, String Key, ByteBuffer value) { + return null; //未実装 + } + + @Override public Either<Error,JungleTreeEditor> putAttribute(NodePath _path,String _key,ByteBuffer _value) { PutAttribute putAttribute = new PutAttribute(_key,_value);
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java Wed Jan 04 05:17:13 2017 +0900 +++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java Wed Jan 04 19:12:26 2017 +0900 @@ -2,6 +2,7 @@ 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.core.Attributes; 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; @@ -16,13 +17,14 @@ import org.junit.Test; import java.nio.ByteBuffer; +import java.util.LinkedList; +import java.util.List; public class RedBlackTreeEditorTest { - String key = "balanceKey"; - @Test public void RedBlackTreeEditor() { + String key = "balanceKey"; Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser()); JungleTree tree = jungle.createNewRedBlackTree("TreeName", "balanceKey"); NodePath path = new DefaultNodePath(); @@ -39,15 +41,30 @@ TreeNode rootNode = tree.getRootNode(); JungleNodeIterator iterator = new JungleNodeIterator(rootNode); int nodeCount = 0; + List<String> list = new LinkedList<>(); + for (int i = 1; i <= count ; i ++) { + list.add(("value" + i)); + } + + while (iterator.hasNext()) { nodeCount++; - iterator.next(); + TreeNode n = iterator.next(); + Attributes attribute = n.getAttributes(); + String str = attribute.getString(key); + int index = list.indexOf(str); + list.remove(index); } + + Assert.assertEquals(list.size(),0); int expectCount = count; Assert.assertEquals(expectCount, nodeCount); ColorlessTreeNode rootNode2 = (ColorlessTreeNode)rootNode; //test用methodを使うためにcastしている rootNode2.checkDepth(0,0); } + + JungleTreeEditor editor = tree.getJungleTreeEditor(); + editor.deleteChildAt(path,0); } }