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

--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/DefaultJungle.java	Sat Jan 07 18:02:53 2017 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/DefaultJungle.java	Sun Jan 08 12:23:48 2017 +0900
@@ -7,6 +7,7 @@
 import jp.ac.u_ryukyu.ie.cr.jungle.persistent.NullJournal;
 import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.DifferentialInterfaceTraverser;
 import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.InterfaceTraverser;
+import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.RedBlackTreeTraverser;
 import jp.ac.u_ryukyu.ie.cr.jungle.store.TreeContext;
 import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.DefaultTreeOperationLog;
 import jp.ac.u_ryukyu.ie.cr.jungle.store.logger.TreeOperationLog;
@@ -180,7 +181,7 @@

         };
         TreeNode rootNode = new EmptyTreeNode();
-        InterfaceTraverser traverser = new DefaultInterfaceTraverser(rootNode, true);
+        InterfaceTraverser traverser = new RedBlackTreeTraverser(rootNode);
         TreeContext tc = new DefaultTreeContext(rootNode, null, list, uuid, treeName, 0, traverser);
         JungleTree newTree = new RedBlackJungleTree(tc, uuid, journal.getWriter(), redBlackTreeEditor, balanceKey);
         if (trees.putIfAbsent(treeName, newTree) != null) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/RedBlackTreeTraverser.java	Sun Jan 08 12:23:48 2017 +0900
@@ -0,0 +1,137 @@
+package jp.ac.u_ryukyu.ie.cr.jungle.query.traverser;
+
+import jp.ac.u_ryukyu.ie.cr.jungle.data.list.List;
+import jp.ac.u_ryukyu.ie.cr.jungle.query.Query;
+import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator.DefaultNodeIterator;
+import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.nodeiterator.RedBlackTreeNodeIterator;
+import jp.ac.u_ryukyu.ie.cr.jungle.store.index.Index;
+import jp.ac.u_ryukyu.ie.cr.jungle.store.index.ParentIndex;
+import jp.ac.u_ryukyu.ie.cr.jungle.transaction.node.TreeNode;
+
+import java.util.Iterator;
+
+
+public class RedBlackTreeTraverser implements InterfaceTraverser {
+    private TreeNode root;
+
+    public RedBlackTreeTraverser(TreeNode root) {
+        this.root = root;
+    }
+
+    @Override
+    public Index getIndex() {
+        return null; //使わない 赤黒木は自身がIndexなので、特別なIndexは無い
+    }
+
+    @Override
+    public ParentIndex getParentIndex() {
+        return null; // 上に同じ、回転処理で構造が変わるため、自身の木構造でデータを表現しない、つまり親を知る必要はない
+    }
+
+    @Override
+    public void createIndex() { // 上に同じ Indexを張る必要はない
+    }
+
+    @Override
+    public void updateIndex(List<TreeNode> editedNodeList) { //上に同じ
+
+    }
+
+    @Override
+    public void updateIndex(TreeNode subTreeRoot) { //上に同じ
+
+    }
+
+    @Override
+    public Iterator<TreeNode> find(Query query) { //balanceKeyを使わない場合全探索なのでDefaultInterfaceTraverserと変わらない
+        Iterator<TreeNode> nodeIterator = new DefaultNodeIterator(root);
+        TreeNode firstMatchNode = null;
+        for (; nodeIterator.hasNext(); ) {
+            firstMatchNode = nextmatch(nodeIterator.next(), query);
+            if (firstMatchNode != null)
+                break;
+        }
+
+        final TreeNode finalFirstMatchNode = firstMatchNode;
+
+        return new Iterator<TreeNode>() {
+
+            TreeNode matchNode = finalFirstMatchNode;
+
+            @Override
+            public boolean hasNext() {
+                if (matchNode == null) {
+                    return false;
+                }
+                return true;
+            }
+
+            @Override
+            public TreeNode next() {
+                TreeNode currentPair = matchNode;
+                for (; nodeIterator.hasNext(); ) {
+                    matchNode = nextmatch(nodeIterator.next(), query);
+                    if (matchNode != null)
+                        return currentPair;
+                }
+                matchNode = null;
+                return currentPair;
+            }
+
+            @Override
+            public void remove() {
+            }
+
+        };
+    }
+
+    @Override
+    public Iterator<TreeNode> find(Query query, String key, String searchValue) {
+        Iterator<TreeNode> nodeIterator = new RedBlackTreeNodeIterator(root,key,searchValue);
+        TreeNode firstMatchNode = null;
+        for (; nodeIterator.hasNext(); ) {
+            firstMatchNode = nextmatch(nodeIterator.next(), query);
+            if (firstMatchNode != null)
+                break;
+        }
+
+        final TreeNode finalFirstMatchNode = firstMatchNode;
+
+        return new Iterator<TreeNode>() {
+
+            TreeNode matchNode = finalFirstMatchNode;
+
+            @Override
+            public boolean hasNext() {
+                if (matchNode == null) {
+                    return false;
+                }
+                return true;
+            }
+
+            @Override
+            public TreeNode next() {
+                TreeNode currentPair = matchNode;
+                for (; nodeIterator.hasNext(); ) {
+                    matchNode = nextmatch(nodeIterator.next(), query);
+                    if (matchNode != null)
+                        return currentPair;
+                }
+                matchNode = null;
+                return currentPair;
+            }
+
+            @Override
+            public void remove() {
+            }
+
+        };
+    }
+
+    private TreeNode nextmatch(TreeNode node, Query query) {
+        if (query.condition(node))
+            return node;
+        return null;
+    }
+}
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/query/traverser/nodeiterator/RedBlackTreeNodeIterator.java	Sun Jan 08 12:23:48 2017 +0900
@@ -0,0 +1,48 @@
+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.transaction.node.TreeNode;
+
+import java.nio.ByteBuffer;
+import java.util.Iterator;
+
+
+public class RedBlackTreeNodeIterator implements Iterator<TreeNode> {
+    private TreeNode next;
+    public RedBlackTreeNodeIterator(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();
+            return search(child,key,searchValueBf);
+        } else if  (targetValue.hashCode() - searchValueBf.hashCode() > 0){
+            Children children = target.getChildren();
+            TreeNode child = children.at(1).b();
+            return search(child,key,searchValueBf);
+        } else {
+            return target;
+        }
+    }
+
+    @Override
+    public boolean hasNext() {
+        return next != null;
+    }
+
+    @Override
+    public TreeNode next() {
+        TreeNode current = next;
+        next = null;
+        return current;
+    }
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/manager/RedBlackTreeTransactionManager.java	Sat Jan 07 18:02:53 2017 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/transaction/manager/RedBlackTreeTransactionManager.java	Sun Jan 08 12:23:48 2017 +0900
@@ -4,12 +4,12 @@
 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.query.traverser.InterfaceTraverser;
+import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.RedBlackTreeTraverser;
 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.query.traverser.DefaultInterfaceTraverser;
 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;
@@ -61,7 +61,7 @@

         };

-        InterfaceTraverser traverser = new DefaultInterfaceTraverser(newRoot, true);
+        InterfaceTraverser traverser = new RedBlackTreeTraverser(newRoot);
         TreeContext newTreeContext = new DefaultTreeContext(newRoot, tip, list, uuid, _treeName, nextRevision, traverser);

         if (repository.compareAndSet(newTreeContext.prev(), newTreeContext)) {
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/test/java/jp/ac/u_ryukyu/ie/cr/jungle/traverse/RedBlackInterfaceTraverserTest.java	Sun Jan 08 12:23:48 2017 +0900
@@ -0,0 +1,45 @@
+package jp.ac.u_ryukyu.ie.cr.jungle.traverse;
+
+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.persistent.NullJournal;
+import jp.ac.u_ryukyu.ie.cr.jungle.query.traverser.InterfaceTraverser;
+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 junit.framework.Assert;
+import org.junit.Test;
+
+import java.nio.ByteBuffer;
+import java.util.Iterator;
+
+public class RedBlackInterfaceTraverserTest {
+    private String balanceKey = "key";
+
+    @Test
+    public void RedBlackInterfaceTraverserTests() {
+        Jungle jungle = new DefaultJungle(new NullJournal(), "hoge", new DefaultTraverser());
+        jungle.createNewRedBlackTree("RedBlackTree", balanceKey);
+        JungleTree tree = jungle.getTreeByName("RedBlackTree");
+        JungleTreeEditor editor = tree.getJungleTreeEditor();
+        NodePath path = new DefaultNodePath();
+        for (int nodeCount = 0; nodeCount < 100; nodeCount++) {
+            ByteBuffer value = ByteBuffer.wrap(("value" + nodeCount).getBytes());
+            Either<Error,JungleTreeEditor> either = editor.addNewChildAndPutAttribute(path, 0, balanceKey, value);
+            Assert.assertFalse(either.isA());
+            editor = either.b();
+        }
+        Either<Error,JungleTreeEditor> either = editor.success();
+        Assert.assertFalse(either.isA());
+        InterfaceTraverser traverser = tree.getTraverser(true);
+        Iterator<TreeNode> iterator = traverser.find((TreeNode node) -> {
+            return true;
+        },balanceKey,"value5");
+        Assert.assertTrue(iterator.hasNext());
+    }
+}