Mercurial > hg > Members > shoshi > jungle > jungle-core

changeset 298:1f132728ae40

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement replaceNode and putAttribute for RedBlackTree
author tatsuki
date Thu, 05 Jan 2017 21:27:46 +0900
parents 1f929fe9c153
children 67ff36237722
files src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorAttributeTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorNodeTest.java src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java
diffstat 7 files changed, 212 insertions(+), 155 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java	Thu Jan 05 09:49:20 2017 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/Default/DefaultTreeNodeChildren.java	Thu Jan 05 21:27:46 2017 +0900
@@ -81,10 +81,10 @@
         return DefaultEither.newB(newNode);
     }
 
-
+    //まだ実装していない もともと赤黒木の編集用
     @Override
     public Either<Error, TreeNode> matchingChildDeleteAt(String key, ByteBuffer value) {
-        return null; // 未使用
+        return null;
     }
 
     @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java	Thu Jan 05 09:49:20 2017 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/ColorlessTreeNode.java	Thu Jan 05 21:27:46 2017 +0900
@@ -99,7 +99,7 @@
 
     @Override
     public RedBlackTreeNodeAttribute getAttributes() {
-        return new RedBlackTreeNodeAttribute(left(), right(), getAttrs(), key(), value());
+        return new RedBlackTreeNodeAttribute(this, getAttrs(), key(), value());
     }
 
     @Test
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java	Thu Jan 05 09:49:20 2017 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeAttribute.java	Thu Jan 05 21:27:46 2017 +0900
@@ -1,8 +1,10 @@
 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.TreeNodeAttributes;
+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;
 
@@ -19,11 +21,14 @@
     private final TreeMap<String, ByteBuffer> attrs;
     private final String balanceKey;
     private final ByteBuffer value;
+    private final ColorlessTreeNode node;
 
-    public RedBlackTreeNodeAttribute(TreeNode leftChild, TreeNode rightChild, TreeMap<String, ByteBuffer> attrs, String balanceKey, ByteBuffer value) {
+
+    public RedBlackTreeNodeAttribute(ColorlessTreeNode node, TreeMap<String, ByteBuffer> attrs, String balanceKey, ByteBuffer value) {
         this.attrs = attrs;
         this.balanceKey = balanceKey;
         this.value = value;
+        this.node = node;
     }
 
     @Override
@@ -32,8 +37,14 @@
     }
 
     @Override
-    public Either<Error, TreeNode> put(String key, ByteBuffer value) {
-        return null;
+    public Either<Error, TreeNode> put(String key, ByteBuffer insertValue) {
+        if (key == null || insertValue == null) {
+            return DefaultEither.newA(NodeEditorError.NULL_VALUE_NOT_ALLOWED);
+        }
+
+        TreeMap<String, ByteBuffer> newMap = attrs.put(key, insertValue);
+        TreeNode newNode = node.createNode(newMap,balanceKey,value,node.left(),node.right());
+        return DefaultEither.newB(newNode);
     }
 
     @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java	Thu Jan 05 09:49:20 2017 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/node/redBlackTree/RedBlackTreeNodeChildren.java	Thu Jan 05 21:27:46 2017 +0900
@@ -1,6 +1,7 @@
 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.trasnformer.NodeEditorError;
 import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode;
 import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNodeChildren;
@@ -51,7 +52,7 @@
 
     @Override
     public Either<Error, TreeNode> addNewChildAndPutAttribtue(int pos, String key, ByteBuffer value) {
-        ColorlessTreeNode newNode = node.addNewChild(key,value);
+        ColorlessTreeNode newNode = node.addNewChild(key, value);
         if (newNode.isRed()) {
             ColorlessTreeNode newRoot = new BlackTreeNode(newNode);
             return DefaultEither.newB(newRoot);
@@ -69,7 +70,7 @@
         ColorlessTreeNode root = newNode.getNode();
         if (root.empty())
             return DefaultEither.newB(new EmptyTreeNode());
-        ColorlessTreeNode newRoot = new BlackTreeNode(root.getAttrs(),root.key(), root.value(), root.left(), root.right());
+        ColorlessTreeNode newRoot = new BlackTreeNode(root.getAttrs(), root.key(), root.value(), root.left(), root.right());
         return DefaultEither.newB(newRoot);
     }
 
@@ -81,9 +82,18 @@
 
     @Override
     public Either<Error, TreeNode> replaceNode(int pos, TreeNode replacement) {
-        return null;
-    } //使わない
+        if (!boundaryCheck(pos)) {
+            return DefaultEither.newA(NodeEditorError.INDEX_OUT_OF_BOUNDS);
+        }
 
+        ColorlessTreeNode newNode;
+        if (pos == 0) { //左のノードを入れ替える場合
+            newNode = node.createNode(attrs,node.key(),node.value(),(ColorlessTreeNode) replacement,node.right());
+        } else {
+            newNode = node.createNode(attrs,node.key(),node.value(),node.left(),(ColorlessTreeNode) replacement);
+        }
+        return DefaultEither.newB(newNode);
+    }
     @Override
     public Either<Error, TreeNode> moveChild(int pos, String move) {
         return null;
@@ -120,6 +130,26 @@
 
     @Override
     public Iterator<TreeNode> iterator() {
-        return null;
+        return new Iterator<TreeNode>() {
+
+            ColorlessTreeNode next = !node.left().empty() ? node.left() : node.right();
+
+            @Override
+            public boolean hasNext() {
+                return !next.empty();
+            }
+
+            @Override
+            public TreeNode next() {
+                TreeNode current = next;
+                if (next.equals(node.left())) {
+                    next = node.right();
+                    return current;
+                }
+                next = new EmptyTreeNode();
+                return current;
+            }
+
+        };
     }
-}
+}
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorAttributeTest.java	Thu Jan 05 21:27:46 2017 +0900
@@ -0,0 +1,61 @@
+package jp.ac.u_ryukyu.ie.cr.jungle.core.treeeditor.RedBlack;
+
+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.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.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;
+
+/**
+ * Created by e115731 on 2017/01/05.
+ */
+public class RedBlackTreeEditorAttributeTest {
+    @Test
+    public void RedBlackTreeEditorAttribute(){
+        String balanceKey = "balanceKey";
+        String key = "key";
+        Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
+        JungleTree tree = jungle.createNewRedBlackTree("TreeName", "balanceKey");
+        NodePath path = new DefaultNodePath();
+
+        for (int count = 1; count <= 10; count++) { //とりあえず木構造の構築
+            JungleTreeEditor editor = tree.getJungleTreeEditor();
+            ByteBuffer value = ByteBuffer.wrap(("value" + count).getBytes());
+            Either<Error, JungleTreeEditor> either = editor.addNewChildAndPutAttribute(path, 0, balanceKey, value);
+            Assert.assertFalse(either.isA());
+            editor = either.b();
+            either = editor.success();
+            Assert.assertFalse(either.isA());
+        }
+
+        JungleTreeEditor editor = tree.getJungleTreeEditor();
+        path = path.add(1);
+        ByteBuffer value = ByteBuffer.wrap(path.toString().getBytes());
+        Either<Error, JungleTreeEditor> either = editor.putAttribute(path, key, value);
+        Assert.assertFalse(either.isA()); //AttributeのPutが成功したかどうか
+        editor = either.b();
+        either = editor.success();
+        Assert.assertFalse(either.isA());
+
+        JungleTree oldTree = tree.getOldTree(tree.revision() - 1).b();
+        TreeNode oldRoot = oldTree.getRootNode();
+        TreeNode newRoot = tree.getRootNode();
+        Assert.assertNotEquals(newRoot,oldRoot);// とりあえずルートがちゃんと入れ替えられているかを調べる
+        TreeNode editedNode = tree.getNodeOfPath(path).b();
+        TreeNode editedOldNode = oldTree.getNodeOfPath(path).b();
+        String putValue = editedNode.getAttributes().getString(key);//編集したノードからputしたAttributeを取得
+        Assert.assertEquals(putValue,path.toString());
+        ByteBuffer nullValue = editedOldNode.getAttributes().get(key);//編集前のノードから値を取得 nullが取れる
+        Assert.assertNull(nullValue);
+
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorNodeTest.java	Thu Jan 05 21:27:46 2017 +0900
@@ -0,0 +1,97 @@
+package jp.ac.u_ryukyu.ie.cr.jungle.core.treeeditor.RedBlack;
+
+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;
+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;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+
+public class RedBlackTreeEditorNodeTest {
+
+    int testCount = 1000;
+
+    @Test
+    public void RedBlackTreeEditorNode() {
+        String key = "balanceKey";
+        Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
+        JungleTree tree = jungle.createNewRedBlackTree("TreeName", "balanceKey");
+        NodePath path = new DefaultNodePath();
+
+        for (int count = 1; count <= testCount; 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;
+            List<String> list = new LinkedList<>();
+            for (int i = 1; i <= count; i++) {
+                list.add(("value" + i));
+            }
+
+
+            while (iterator.hasNext()) { //ちゃんとノードの追加ができているか、全てのノードが木にあるかをを調べる
+                nodeCount++;
+                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); //赤黒木のバランスが取れているかを調べる
+        }
+
+        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);
+            Assert.assertFalse(either.isA());
+            editor = either.b();
+            either = editor.success();
+            Assert.assertFalse(either.isA());
+
+            ColorlessTreeNode rootNode = (ColorlessTreeNode) tree.getRootNode();
+            Iterator<TreeNode> iterator = new JungleNodeIterator(rootNode);
+            int nodeCount = 0;
+
+            while (iterator.hasNext() && rootNode.getAttributes().get(key) != null) { //削除時間違えて他のノードを消してないかを調べる
+                ColorlessTreeNode node = (ColorlessTreeNode) iterator.next();
+                ByteBuffer seach = node.getAttributes().get(key);
+                Assert.assertTrue(rootNode.get(seach));
+                nodeCount++;
+            }
+
+            int expectCount = testCount - count;
+            Assert.assertEquals(expectCount, nodeCount);
+        }
+
+
+    }
+}
--- a/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/core/treeeditor/RedBlack/RedBlackTreeEditorTest.java	Thu Jan 05 09:49:20 2017 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,142 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.jungle.core.treeeditor.RedBlack;
-
-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;
-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;
-import java.util.LinkedList;
-import java.util.List;
-
-public class RedBlackTreeEditorTest {
-
-    int testCount = 5000;
-
-    @Test
-    public void RedBlackTreeEditor() {
-
-        ByteBuffer b5 =  ByteBuffer.wrap(("value" + 5).getBytes());
-        ByteBuffer b6 =  ByteBuffer.wrap(("value" + 6).getBytes());
-        ByteBuffer b12 =  ByteBuffer.wrap(("value" + 12).getBytes());
-        ByteBuffer b8 =  ByteBuffer.wrap(("value" + 8).getBytes());
-
-        long h5 = b5.hashCode();
-        long h6 = b6.hashCode();
-        long h12 = b12.hashCode();
-        long result1 = h6 - h12;
-        long result2 = h5 - h12;
-
-        String key = "balanceKey";
-        Jungle jungle = new DefaultJungle(null, "hogehoge", new DefaultTraverser());
-        JungleTree tree = jungle.createNewRedBlackTree("TreeName", "balanceKey");
-        NodePath path = new DefaultNodePath();
-
-        for (int count = 1; count <= testCount; 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;
-            List<String> list = new LinkedList<>();
-            for (int i = 1; i <= count; i++) {
-                list.add(("value" + i));
-            }
-
-
-            while (iterator.hasNext()) {
-                nodeCount++;
-                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);
-        }
-
-        System.out.println("------------------------------------------- delete -----------------------------------------------------------------------------------");
-        for (int count = 1; count <= testCount; count++) {
-            System.out.println(count + "回目------------------------------------------------------------------------------------------------------------------------");
-
-            ColorlessTreeNode rootNode = (ColorlessTreeNode) tree.getRootNode();
-            JungleNodeIterator iterator = new JungleNodeIterator(rootNode);
-            int nodeCount = 0;
-
-            if (count == 2)
-                System.out.println("やばい");
-            System.out.println("------------------------------------------------delete 前------------------------------------------------------------------------");
-            while (iterator.hasNext() && rootNode.getAttributes().get(key) != null) {
-                ColorlessTreeNode node = (ColorlessTreeNode) iterator.next();
-                if (node.empty())
-                    System.out.println(node.empty());
-                if (node.key() == null)
-                    System.out.println("これはやばいですよ");
-                ByteBuffer seach = node.getAttributes().get(key);
-                int test = seach.hashCode();
-                String seachStr = node.getAttributes().getString(key);
-                System.out.println(seachStr);
-                Assert.assertTrue(rootNode.get(seach));
-                nodeCount++;
-            }
-
-
-            if (count == 2)
-                System.out.println("やばい");
-            JungleTreeEditor editor = tree.getJungleTreeEditor();
-            ByteBuffer value = ByteBuffer.wrap(("value" + count).getBytes());
-            Either<Error, JungleTreeEditor> either = editor.deleteChildAt(path, 0, key, value);
-            Assert.assertFalse(either.isA());
-            editor = either.b();
-            either = editor.success();
-            Assert.assertFalse(either.isA());
-
-            System.out.println("------------------------------------------------delete 後------------------------------------------------------------------------");
-            rootNode = (ColorlessTreeNode) tree.getRootNode();
-            iterator = new JungleNodeIterator(rootNode);
-            nodeCount = 0;
-
-            while (iterator.hasNext() && rootNode.getAttributes().get(key) != null) {
-                ColorlessTreeNode node = (ColorlessTreeNode) iterator.next();
-                if (node.empty())
-                    System.out.println(node.empty());
-                if (node.key() == null)
-                    System.out.println("これはやばいですよ");
-                System.out.println(node.getAttributes().getString(key));
-                ByteBuffer seach = node.getAttributes().get(key);
-                int test = seach.hashCode();
-                String seachStr= node.getAttributes().getString(key);
-                Assert.assertTrue(rootNode.get(seach));
-                nodeCount++;
-            }
-
-            int expectCount = testCount - count;
-            Assert.assertEquals(expectCount, nodeCount);
-        }
-
-
-    }
-}