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

changeset 221:9404bf19da41

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge TreeMap
author tatsuki
date Tue, 15 Sep 2015 00:39:25 +0900
parents c86d39eb19d1 (current diff) 7e1a59c2ede6 (diff)
children 143ca837d3b0
files src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Taple.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/TreeMap.java src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/rebuildNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/util/TreeMapOrd.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/UpdateQuery.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/Index.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/FJListAccessThread.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/FJTreeMapGetLoopThread.java
diffstat 13 files changed, 187 insertions(+), 485 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java	Tue Sep 01 16:27:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java	Tue Sep 15 00:39:25 2015 +0900
@@ -14,9 +14,9 @@
 
 
     @Override
-    public Node<K, V> deleteNode() throws RotateParent {
+    public rebuildNode deleteNode() {
         EmptyNode<K, V> emptyNode = new EmptyNode<>(key);
-        throw new RotateParent(emptyNode);
+        return new rebuildNode<>(true, emptyNode);
     }
 
     @Override
@@ -83,22 +83,22 @@
         return false;
     }
 
+    @Override
     @SuppressWarnings("unchecked")
-    @Override
-    public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent {
+    public rebuildNode replaceNode(Node<K, V> parent, Comparator ctr) {
         Node<K, V> newNode;
         if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
             return deleteNode();//黒が1つ減るので木のバランスを取る
         } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
             if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る
-                throw new RotateParent(newNode);
-            return newNode;
+                return new rebuildNode(true, newNode);
+            return new rebuildNode(false, newNode);
         } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right());
             if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る
-                throw new RotateParent(newNode);
-            return newNode;
+                return new rebuildNode(true, newNode);
+            return new rebuildNode(false, newNode);
         } else {//子ノードが左右にある場合 二回目はここには入らない
             //左の部分木の最大の値を持つNodeと自身を置き換える
             Node<K, V> cur = this.left();
@@ -106,24 +106,25 @@
                 cur = cur.right();
             }
             if (this.left().right().isNotEmpty()) { //左の部分木が右の子を持っているか
-                try {
-                    Node<K, V> leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
-                    return createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
-                } catch (RotateParent e) {
-                    Node<K, V> leftSubTreeNode = e.getParent();
+                rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+                if (leftSubTreeNodeRebuildNode.rebuild()) {
+                    Node<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
                     Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
                     return leftSubTreeNode.deleteBalance(newParent, ctr);
                 }
+                Node<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
+                return new rebuildNode(false, newNode);
             } else {
-                Node<K, V> leftSubTreeNode;
-                try {
-                    leftSubTreeNode = this.left().replaceNode(this, ctr);//右の子がいなかった場合、左の子を昇格させるだけで良い。
-                    return createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
-                } catch (RotateParent e) {
-                    Node<K, V> node = e.getParent();
+                rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.left().replaceNode(this, ctr);//右の子がいなかった場合、左の子を昇格させるだけで良い。
+                if (leftSubTreeNodeRebuildNode.rebuild()) {
+                    Node<K, V> node = leftSubTreeNodeRebuildNode.getNode();
                     Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right());
                     return node.deleteBalance(newParent, ctr);
                 }
+                Node<K,V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+                newNode = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
+                return new rebuildNode(false, newNode);
             }
         }
     }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java	Tue Sep 01 16:27:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java	Tue Sep 15 00:39:25 2015 +0900
@@ -44,13 +44,13 @@
     }
 
     @Override
-    public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) { // not use method
-        return this;
+    public rebuildNode<K, V> replaceNode(Node<K, V> parent, Comparator ctr) { // not use method
+        return new rebuildNode<>(false, this);
     }
 
     @Override
-    protected Node<K,V> deleteNode() { //not use method
-        return this;
+    protected rebuildNode<K, V> deleteNode() { //not use method
+        return new rebuildNode<>(false, this);
     }
 
     @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java	Tue Sep 01 16:27:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java	Tue Sep 15 00:39:25 2015 +0900
@@ -80,72 +80,60 @@
     }
 
     @SuppressWarnings("unchecked")
-    public Node<K, V> delete(K key, Node<K, V> parent, Comparator ctr, Rotate side) throws RotateParent {
+    public rebuildNode delete(K key, Node<K, V> parent, Comparator ctr, Rotate side) {
         if (this.isNotEmpty()) {
+            rebuildNode rebuildNode;
             int result = compare(key, ctr);
+            if (result > 0) {
+                rebuildNode = right.delete(key, this, ctr, Rotate.R);
+            } else if (result < 0) {
+                rebuildNode = left.delete(key, this, ctr, Rotate.L);
+            } else { //Equal
+                rebuildNode = replaceNode(parent, ctr);
+            }
+            if (parent == null)
+                return rebuildNode;
+            Node<K, V> node = rebuildNode.getNode();
+            if (rebuildNode.rebuild()) {
+                return node.deleteBalance(parent, ctr);
+            }
 
-            try {
-                Node<K, V> node = null;
-                if (result > 0) {
-                    node = right.delete(key, this, ctr, Rotate.R);
-                    if (node == null)
-                        return null;
-                    if (parent == null)
-                        return node;
-                } else if (result < 0) {
-                    node = left.delete(key, this, ctr, Rotate.L);
-                    if (node == null)
-                        return null;
-                    if (parent == null)
-                        return node;
-                } else if (result == 0) {
-                    node = replaceNode(parent, ctr);
-                    if (parent == null)// equals
-                        return node;
-                    if (side == Rotate.R)
-                        return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
-                    else
-                        return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
-                }
-                if (side == Rotate.L)
-                    return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
-                else
-                    return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
-            } catch (RotateParent e) {
-                Node<K, V> node = e.getParent();
-                if (parent != null)
-                    return node.deleteBalance(parent, ctr);
-                return node;
-            }
+            Node<K, V> newParent;
+            if (side == Rotate.L)
+                newParent = parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
+            else
+                newParent = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
+
+            return new rebuildNode<>(false, newParent);
         }
-        return null; // no key
+        return null;
     }
 
     @SuppressWarnings("unchecked")
-    public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent, Comparator ctr, Rotate side) throws RotateParent {
+    public rebuildNode deleteSubTreeMaxNode(Node<K, V> parent, Comparator ctr, Rotate side) {
+        rebuildNode rebuildNode;
         Node<K, V> node;
-        try {
-            if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
-                node = right().deleteSubTreeMaxNode(this, ctr, Rotate.R);
-            } else {
-                node = this.replaceNode(parent, ctr);
-            }
-        } catch (RotateParent e) {
-            node = e.getParent();
-            if (parent == null)
-                throw e;
+        if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
+            rebuildNode = right().deleteSubTreeMaxNode(this, ctr, Rotate.R);
+        } else {
+            rebuildNode = this.replaceNode(parent, ctr);
+        }
+        if (parent == null)
+            return rebuildNode;
+
+        if (rebuildNode.rebuild()) {
+            node = rebuildNode.getNode();
             return node.deleteBalance(parent, ctr);
         }
-        if (parent == null)
-            return node;
         if (side == Rotate.R)
-            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), node);
+            node = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), rebuildNode.getNode());
         else
-            return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
-
+            node = parent.createNode(parent.getKey(), parent.getValue(), rebuildNode.getNode(), parent.right());
+        return new rebuildNode<>(false, node);
     }
 
-    public Node<K, V> deleteBalance(Node<K, V> parent, Comparator ctr) throws RotateParent {
+    public rebuildNode<K, V> deleteBalance(Node<K, V> parent, Comparator ctr) {
+        Node<K, V> newNode = null;
         if (!isRed()) {
             if (0 > compare(parent.getKey(), ctr)) { //自身がどちらの子かを調べる
                 boolean rightChild = parent.left().right().isRed();
@@ -153,22 +141,33 @@
 
                 if (!parent.isRed()) { //親が黒
                     if (!parent.left().isRed()) { //左の子が黒
-                        if (!rightChild && !leftChild)
-                            throw new RotateParent(rebuildThree(parent, Rotate.R));
-                        if (rightChild)
-                            return rebuildfive(parent, Rotate.R);
-                        else
-                            return rebuildsix(parent, Rotate.R);
+                        if (!rightChild && !leftChild) {
+                            newNode = rebuildThree(parent, Rotate.R);
+                            return new rebuildNode<>(true, newNode);
+                        }
+                        if (rightChild) {
+                            newNode = rebuildfive(parent, Rotate.R);
+                            return new rebuildNode<>(false, newNode);
+                        } else {
+                            newNode = rebuildsix(parent, Rotate.R);
+                            return new rebuildNode<>(false, newNode);
+                        }
                     } else { //左の子が赤
-                        return rebuildTwo(parent, ctr, Rotate.R);
+                        newNode = rebuildTwo(parent, ctr, Rotate.R);
+                        return new rebuildNode<>(false, newNode);
                     }
                 } else { //親が赤
-                    if (!rightChild && !leftChild)
-                        return rebuildFour(parent, Rotate.R);
-                    if (rightChild)
-                        return rebuildfive(parent, Rotate.R);
-                    else
-                        return rebuildsix(parent, Rotate.R);
+                    if (!rightChild && !leftChild) {
+                        newNode = rebuildFour(parent, Rotate.R);
+                        return new rebuildNode<>(false, newNode);
+                    }
+                    if (rightChild) {
+                        newNode = rebuildfive(parent, Rotate.R);
+                        return new rebuildNode<>(false, newNode);
+                    } else {
+                        newNode = rebuildsix(parent, Rotate.R);
+                        return new rebuildNode<>(false, newNode);
+                    }
                 }
             } else {
                 boolean rightChild = parent.right().right().isRed();
@@ -176,44 +175,60 @@
 
                 if (!parent.isRed()) { //親が黒
                     if (!parent.right().isRed()) { //左の子が黒
-                        if (!rightChild && !leftChild)
-                            throw new RotateParent(rebuildThree(parent, Rotate.L));
-                        if (rightChild)
-                            return rebuildsix(parent, Rotate.L);
-                        else
-                            return rebuildfive(parent, Rotate.L);
+                        if (!rightChild && !leftChild) {
+                            newNode = rebuildThree(parent, Rotate.L);
+                            return new rebuildNode<>(true, newNode);
+                        }
+                        if (rightChild) {
+                            newNode = rebuildsix(parent, Rotate.L);
+                            return new rebuildNode<>(false, newNode);
+                        } else {
+                            newNode = rebuildfive(parent, Rotate.L);
+                            return new rebuildNode<>(false, newNode);
+                        }
                     } else { //左の子が赤
-                        return rebuildTwo(parent, ctr, Rotate.L);
+                        newNode = rebuildTwo(parent, ctr, Rotate.L);
+                        return new rebuildNode<>(false, newNode);
                     }
                 } else { //親が赤
-                    if (!rightChild && !leftChild)
-                        return rebuildFour(parent, Rotate.L);
-                    if (rightChild)
-                        return rebuildsix(parent, Rotate.L);
-                    else
-                        return rebuildfive(parent, Rotate.L);
+                    if (!rightChild && !leftChild) {
+                        newNode = rebuildFour(parent, Rotate.L);
+                        return new rebuildNode<>(false, newNode);
+                    }
+                    if (rightChild) {
+                        newNode = rebuildsix(parent, Rotate.L);
+                        return new rebuildNode<>(false, newNode);
+                    } else {
+                        newNode = rebuildfive(parent, Rotate.L);
+                        return new rebuildNode<>(false, newNode);
+                    }
                 }
             }
         }
-        if (0 > (compare(parent.getKey(), ctr)))
-            return parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
-        else
-            return parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
+        if (0 > (compare(parent.getKey(), ctr))) {
+            newNode = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
+            return new rebuildNode<>(false, newNode);
+        } else {
+            newNode = parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
+            return new rebuildNode<>(false, newNode);
+        }
     }
 
-    protected Node<K, V> rebuildTwo(Node<K, V> parent, Comparator ctr, Rotate side) throws RotateParent { // case2
+    protected Node<K, V> rebuildTwo(Node<K, V> parent, Comparator ctr, Rotate side) { // case2
         if (side == Rotate.L) { // rotate Left
             Node<K, V> node = parent.right();
             Node<K, V> leftSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), this, node.left()); // check
-            Node<K, V> leftNode = this.deleteBalance(leftSubTreeRoot, ctr);
+            rebuildNode<K, V> rebuildNode = new rebuildNode<>(false, leftSubTreeRoot);
+            rebuildNode<K, V> leftNodeRebuildNode = this.deleteBalance(rebuildNode.getNode(), ctr);
             Node<K, V> rightNode = node.right();
-            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
+            return parent.createNode(node.getKey(), node.getValue(), leftNodeRebuildNode.getNode(), rightNode);
         } else {  // rotate Right
             Node<K, V> node = parent.left();
             Node<K, V> rightSubTreeRoot = node.createNode(parent.getKey(), parent.getValue(), node.right(), this);
-            Node<K, V> rightNode = this.deleteBalance(rightSubTreeRoot, ctr);
+            rebuildNode<K, V> rightSubTreeRebuildNode = new rebuildNode<>(false, rightSubTreeRoot);
+            rebuildNode<K, V> rightNodeRebuildNode = this.deleteBalance(rightSubTreeRebuildNode.getNode(), ctr);
             Node<K, V> leftNode = node.left();
-            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
+            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNodeRebuildNode.getNode());
         }
     }
 
@@ -284,9 +299,9 @@
 
     abstract boolean isRed();
 
-    public abstract Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent;
+    public abstract rebuildNode replaceNode(Node<K, V> parent, Comparator ctr);
 
-    protected abstract Node deleteNode() throws RotateParent;
+    protected abstract rebuildNode deleteNode();
 
     @Test
     // test method
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java	Tue Sep 01 16:27:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java	Tue Sep 15 00:39:25 2015 +0900
@@ -29,8 +29,9 @@
     }
 
     @Override
-    protected Node<K, V> deleteNode() throws RotateParent {
-        return new EmptyNode<>(this.getKey());
+    protected rebuildNode deleteNode() {
+        Node emptyNode = new EmptyNode<>(this.getKey());
+        return new rebuildNode(false, emptyNode);
     }
 
     @Override
@@ -55,18 +56,18 @@
         return true;
     }
 
+    @SuppressWarnings("unchecked")
     @Override
-    @SuppressWarnings("unchecked")
-    public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent {
+    public rebuildNode replaceNode(Node<K, V> parent, Comparator ctr) {
         Node<K, V> newNode;
         if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
             return deleteNode();
         } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right());
-            return newNode;
+            return new rebuildNode(false, newNode);
         } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right());
-            return newNode;
+            return new rebuildNode(false, newNode);
         } else {//子ノードが左右にある場合
             //左の部分木の最大の値を持つNodeと自身を置き換える
             Node<K, V> cur = this.left();
@@ -74,27 +75,26 @@
             while (cur.right().isNotEmpty()) {
                 cur = cur.right();
             }
-            Node<K, V> leftSubTreeNode;
             if (this.left().right().isNotEmpty()) {
-                try {
-                    leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);
-                    newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
-                    return newNode;
-                } catch (RotateParent e) {
-                    leftSubTreeNode = e.getParent();
-                    Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
-                    return leftSubTreeNode.deleteBalance(newParent, ctr);
+                rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);
+                if (leftSubTreeNodeRebuildNode.rebuild()) {
+                    Node<K, V> node = leftSubTreeNodeRebuildNode.getNode();
+                    Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.right());
+                    return node.deleteBalance(newParent, ctr);
                 }
+                Node<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                return new rebuildNode<>(false, newNode);
             } else {
-                try {
-                    leftSubTreeNode = this.left().replaceNode(this, ctr);
-                    newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
-                    return newNode;
-                } catch (RotateParent e) {
-                    Node<K, V> node = e.getParent();
+                rebuildNode<K, V> leftSubTreeNodeRebuildNode = this.left().replaceNode(this, ctr);
+                if (leftSubTreeNodeRebuildNode.rebuild()) {
+                    Node<K, V> node = leftSubTreeNodeRebuildNode.getNode();
                     Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right());
                     return node.deleteBalance(newParent, ctr);
                 }
+                Node<K, V> leftSubTreeNode = leftSubTreeNodeRebuildNode.getNode();
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                return new rebuildNode<>(false, newNode);
             }
 
         }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RotateParent.java	Tue Sep 01 16:27:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RotateParent.java	Tue Sep 15 00:39:25 2015 +0900
@@ -1,5 +1,8 @@
 package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap;
 
+/**
+ * Generic Exception not support
+ **/
 public class RotateParent extends Exception {
 
     Node parent;
@@ -10,4 +13,4 @@
     public Node getParent() {
         return parent;
     }
-}
+}
\ No newline at end of file
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/TreeMap.java	Tue Sep 01 16:27:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/TreeMap.java	Tue Sep 15 00:39:25 2015 +0900
@@ -11,7 +11,7 @@
 
 public class TreeMap<K, V> {
     final Node<K, V> root;
-    Comparator comparator;
+    final Comparator comparator;
 
     public TreeMap() {
         this.root = new EmptyNode<>();
@@ -33,20 +33,15 @@
     }
 
     public Optional<V> get(final K key) {
-        return root.get(key, comparator);
+        return root.get(key, this.comparator);
     }
 
     public TreeMap<K, V> put(K key, V value) {
-
-        if (key == null || value == null)  // null check
-            throw new NullPointerException();
-
         if (isEmpty()) {
             Node<K, V> newRoot = new BlackNode<>(key, value, new EmptyNode<>(), new EmptyNode<>());
             return new TreeMap<>(newRoot, this.comparator);
         }
-
-        Node<K, V> newEntry = root.put(key, value, comparator);
+        Node<K, V> newEntry = root.put(key, value, this.comparator);
         Node<K, V> newRoot = new BlackNode<>(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right());
         return new TreeMap<>(newRoot, this.comparator);
     }
@@ -58,17 +53,15 @@
 
 
     public TreeMap<K, V> delete(K key) {
-        Node<K, V> node = null;
-        try {
-            node = root.delete(key, null, comparator, Rotate.N);
-        } catch (RotateParent rotateParent) {
-            System.out.println("no call this scope");
-        }
-        if (node == null)
+        if (key == null)
+            return this;
+        rebuildNode<K,V> rootRebuildNode = root.delete(key, null, comparator, Rotate.N);
+        if (!rootRebuildNode.notEmpty())
             return this; // not key
-        if (!node.isNotEmpty())
+        Node<K,V> root = rootRebuildNode.getNode();
+        if (!root.isNotEmpty())
             return new TreeMap<>(new EmptyNode<>(), this.comparator);
-        Node<K, V> newRoot = new BlackNode<>(node.getKey(), node.getValue(), node.left(), node.right());
+        Node<K, V> newRoot = new BlackNode<>(root.getKey(), root.getValue(), root.left(), root.right());
         return new TreeMap<>(newRoot, this.comparator);
     }
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/rebuildNode.java	Tue Sep 15 00:39:25 2015 +0900
@@ -0,0 +1,24 @@
+package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap;
+
+
+public class rebuildNode<K,V> {
+    private final Boolean rebuild;
+    private final Node<K,V> node;
+
+    public rebuildNode(Boolean l, Node<K, V> node){
+        this.rebuild = l;
+        this.node = node;
+    }
+
+    public boolean rebuild(){
+        return rebuild;
+    }
+
+    public Node<K,V> getNode(){
+        return node;
+    }
+
+    public Boolean notEmpty(){
+        return node != null;
+    }
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/util/TreeMapOrd.java	Tue Sep 01 16:27:25 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,25 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util;
-
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
-import fj.F;
-import fj.Ord;
-import fj.P;
-import fj.P1;
-
-public class TreeMapOrd {
-
-  private TreeMapOrd(){
-    
-  }
-  
-  private static F<TreeNode, P1<String>> toP1 = new F<TreeNode, P1<String>> () {
-    @Override
-    public P1<String> f(TreeNode node) {
-      return P.p(node.toString());
-    }
-  };
-  
-  private static Ord<P1<String>> ord = Ord.p1Ord(Ord.stringOrd);
-  public static Ord<TreeNode> treeNodeOrd = ord.comap(toP1);
-  
-}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/SearchQuery.java	Tue Sep 01 16:27:25 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,47 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
-
-import fj.data.List;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
-import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
-
-public class SearchQuery {
-	
-	private Query query;
-	private List<String> indexidAttributesList = List.nil();
-	
-	public Query getQuery() {
-        return query;
-    }
-
-    public void setQuery(Query query) {
-        this.query = query;
-    }
-
-    public List<String> getIndexidAttributesList() {
-        return indexidAttributesList;
-    }
-
-    public void setIndexidAttributesList(List<String> indexidAttributesList) {
-        this.indexidAttributesList = indexidAttributesList;
-    }
-
-    public SearchQuery(Query query){
-	    this.query = query;
-	}
-	
-	public boolean condition(TreeNode node) {
-	    return query.condition(node);
-	    
-//		 for example query String 
-//		str = new String(_node.getAttributes().get(key).array());
-//		//System.out.println(str);
-//		if(str.equals(attribute))
-//			return true;
-//		return false;
-	}
-
-    public List<Pair<String, String>> indexCondition() {
-        return null;//query.indexCondition();
-    }
-
-}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/query/UpdateQuery.java	Tue Sep 01 16:27:25 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,20 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
-
-import java.nio.ByteBuffer;
-
-
-public class UpdateQuery extends SearchQuery /*implements Query*/ {
-
-	
-	private String updateAttribute;
-	
-	public UpdateQuery(String key, String attribute , String updateAttribute){
-		super(null);
-		this.updateAttribute = updateAttribute;
-	}
-
-	public ByteBuffer getUpdateAttribute(){
-		updateAttribute.getBytes();
-		return ByteBuffer.wrap(updateAttribute.getBytes());
-	}
-}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/store/index/Index.java	Tue Sep 01 16:27:25 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,155 +0,0 @@
-//package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index;
-//
-//import java.util.Iterator;
-//
-//import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator;
-//import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
-//import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.TreeMapOrd;
-//import fj.Ord;
-//import fj.P2;
-//import fj.data.Option;
-//import fj.data.TreeMap;
-//
-//public class Index {
-//
-//  TreeMap<String, TreeMap<String, TreeMap<TreeNode, TreeNode>>> indexList;
-//
-//  public Index() {
-//   indexList = TreeMap.empty(Ord.stringOrd);    
-//  }
-//
-//  public Index(TreeMap<String, TreeMap<String, TreeMap<TreeNode, TreeNode>>> indexList) {
-//    this.indexList = indexList;
-//  }
-//
-//  public Index set(String key, String value, TreeNode node) {
-//    
-//    Option<TreeMap<String, TreeMap<TreeNode, TreeNode>>> indexOp = indexList.get(key);
-//    if (indexOp.isNone()) {
-//      TreeMap<String, TreeMap<TreeNode, TreeNode>> index = TreeMap.empty(Ord.stringOrd);
-//      TreeMap<TreeNode, TreeNode> nodeMap = TreeMap.empty(TreeMapOrd.treeNodeOrd);
-//      nodeMap = nodeMap.set(node, node);
-//      TreeMap<String, TreeMap<TreeNode, TreeNode>> newIndex = index.set(value, nodeMap);
-//      indexList = indexList.set(key, newIndex);
-//      return this;
-//    }
-//
-//    TreeMap<String, TreeMap<TreeNode, TreeNode>> index = indexOp.some();
-//    Option<TreeMap<TreeNode, TreeNode>> nodeMapOp = index.get(value);
-//
-//    TreeMap<TreeNode, TreeNode> newNodeMap;
-//    if (nodeMapOp.isSome()) {
-//      TreeMap<TreeNode, TreeNode> nodeMap = nodeMapOp.some();
-//      newNodeMap = nodeMap.set(node, node);
-//    } else {
-//      TreeMap<TreeNode, TreeNode> nodeMap = TreeMap.empty(TreeMapOrd.treeNodeOrd);
-//      newNodeMap = nodeMap.set(node, node);
-//    }
-//    TreeMap<String, TreeMap<TreeNode, TreeNode>> newIndex = index.set(value, newNodeMap);
-//    indexList = indexList.set(key, newIndex);
-//
-//    return this;
-//  }
-//
-//  // public Index delete(String key, String value, TreeNode node) {
-//  // Option<TreeMap<String, List<TreeNode>>> indexOp = indexList.get(key);
-//  // if (indexOp.isNone())
-//  // return this;
-//  //
-//  // TreeMap<String, List<TreeNode>> index = indexOp.some();
-//  // TreeMap<String, List<TreeNode>> newIndex = index;
-//  // Option<List<TreeNode>> nodeListOp = index.get(value);
-//  // if (nodeListOp.isSome()) {
-//  // List<TreeNode> nodeList = nodeListOp.some();
-//  // List<TreeNode> newNodeList = List.nil();
-//  // for (TreeNode indexingNode : nodeList) {
-//  // if (indexingNode.equals(node))
-//  // newNodeList = newNodeList.cons(indexingNode);
-//  // }
-//  //
-//  // newIndex = index.set(value, newNodeList);
-//  // } else {
-//  // return this;
-//  // }
-//  // TreeMap<String, TreeMap<String, List<TreeNode>>> newIndexList =
-//  // indexList.set(key, newIndex);
-//  // return new Index(newIndexList);
-//  // }
-//
-//  public Iterator<TreeNode> get(String key, String value) {
-//
-//    Option<TreeMap<String, TreeMap<TreeNode, TreeNode>>> indexOp = indexList.get(key);
-//    if (indexOp.isNone())
-//      return new NulIterator<TreeNode>();
-//
-//    TreeMap<String, TreeMap<TreeNode, TreeNode>> index = indexOp.some();
-//    Option<TreeMap<TreeNode, TreeNode>> nodeMapOp = index.get(value);
-//
-//    if (nodeMapOp.isNone())
-//      return new NulIterator<TreeNode>();
-//
-//    Iterator<P2<TreeNode, TreeNode>> mapIterator = nodeMapOp.some().iterator();
-//    return new Iterator<TreeNode>() {
-//
-//      @Override
-//      public boolean hasNext() {
-//        return mapIterator.hasNext();
-//      }
-//
-//      @Override
-//      public TreeNode next() {
-//        return mapIterator.next()._1();
-//      }
-//
-//    };
-//  }
-//
-//  public Iterator<TreeNode> getAll(String key) {
-//
-//    Option<TreeMap<String, TreeMap<TreeNode, TreeNode>>> indexOp = indexList.get(key);
-//    if (indexOp.isNone())
-//      return null;
-//
-//    final TreeMap<String, TreeMap<TreeNode, TreeNode>> index = indexOp.some();
-//    if (!index.isEmpty())
-//      return new NulIterator<TreeNode>();
-//
-//    return new Iterator<TreeNode>() {
-//
-//      Iterator<P2<String, TreeMap<TreeNode, TreeNode>>> treeMapIterator = index.iterator();
-//      Iterator<P2<TreeNode, TreeNode>> nodeIterator = new NulIterator<P2<TreeNode, TreeNode>>();
-//      TreeNode node;
-//
-//      @Override
-//      public boolean hasNext() {
-//
-//        if (nodeIterator.hasNext()) {
-//          node = nodeIterator.next()._1();
-//          return true;
-//        }
-//
-//        for (; treeMapIterator.hasNext();) {
-//          TreeMap<TreeNode, TreeNode> nodeMap = treeMapIterator.next()._2();
-//          nodeIterator = nodeMap.iterator();
-//          if (nodeIterator.hasNext()) {
-//            node = nodeIterator.next()._1();
-//            return true;
-//          }
-//        }
-//        return false;
-//      }
-//
-//      @Override
-//      public TreeNode next() {
-//        return node;
-//      }
-//
-//    };
-//
-//  }
-//
-//  public TreeMap<String, TreeMap<String, TreeMap<TreeNode, TreeNode>>> getIndex() {
-//    return indexList;
-//  }
-//
-//}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/FJListAccessThread.java	Tue Sep 01 16:27:25 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,42 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.test;
-
-
-import fj.data.List;
-import fj.data.Option;
-
-import java.util.Iterator;
-
-/**
- * Created by e115731 on 15/03/21.
- */
-public class FJListAccessThread extends AbstractTreeMapThread {
-    Option<List<String>> list;
-    private long findCount;
-    boolean loop = true;
-
-    public FJListAccessThread(Option<List<String>> list) {
-        this.list = list;
-    }
-
-    @Override
-    public long getFindCount() {
-        System.out.println("thread count = " + findCount);
-        return findCount;
-    }
-
-    @Override
-    public void set(boolean loop) {
-        this.loop = loop;
-    }
-
-    @Override
-    public void run() {
-        while (loop) {
-            Iterator<String> it = list.some().iterator();
-            for (; it.hasNext(); ) {
-                String str = it.next();
-            }
-            findCount++;
-        }
-    }
-}
\ No newline at end of file
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/jungle/test/FJTreeMapGetLoopThread.java	Tue Sep 01 16:27:25 2015 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,45 +0,0 @@
-package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.test;
-
-import fj.P2;
-import fj.data.Option;
-import fj.data.TreeMap;
-
-import java.util.Iterator;
-
-/**
- * Created by e115731 on 15/03/17.
- */
-public class FJTreeMapGetLoopThread extends AbstractTreeMapThread {
-
-    TreeMap<String, String> map;
-    private long findCount;
-    boolean loop = true;
-
-    public FJTreeMapGetLoopThread(TreeMap map) {
-        this.map = map;
-    }
-
-    @Override
-    public long getFindCount() {
-        System.out.println("thread count = " + findCount);
-        return findCount;
-    }
-
-    @Override
-    public void set(boolean loop) {
-        this.loop = loop;
-    }
-
-    @Override
-    public void run() {
-        while (loop) {
-            String op = map.getLoop("50");
-            if (op  != null)
-                findCount++;
-            else
-                System.out.println("faild");
-
-
-        }
-    }
-}