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

changeset 217:3b31dd5e5a28 OptionalTreeMap

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
delete use Taple fix
author tatsuki
date Tue, 01 Sep 2015 16:09:08 +0900
parents 9a410eddbfa4
children 7e1a59c2ede6
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
diffstat 6 files changed, 181 insertions(+), 143 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java	Tue Sep 01 05:04:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/BlackNode.java	Tue Sep 01 16:09:08 2015 +0900
@@ -14,9 +14,9 @@
 
 
     @Override
-    public Node<K, V> deleteNode() throws RotateParent {
+    public Taple deleteNode() {
         EmptyNode<K, V> emptyNode = new EmptyNode<>(key);
-        throw new RotateParent(emptyNode);
+        return new Taple<>(true, emptyNode);
     }
 
     @Override
@@ -85,20 +85,20 @@
 
     @Override
     @SuppressWarnings("unchecked")
-    public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent {
+    public Taple 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 Taple(true, newNode);
+            return new Taple(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 Taple(true, newNode);
+            return new Taple(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();
+                Taple<K, V> leftSubTreeNodeTaple = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+                if (leftSubTreeNodeTaple.rebuild()) {
+                    Node<K, V> leftSubTreeNode = leftSubTreeNodeTaple.getNode();
                     Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
                     return leftSubTreeNode.deleteBalance(newParent, ctr);
                 }
+                Node<K, V> leftSubTreeNode = leftSubTreeNodeTaple.getNode();
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
+                return new Taple(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();
-                    Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right());
-                    return node.deleteBalance(newParent, ctr);
-                }
+                    Taple<K, V> leftSubTreeNodeTaple = this.left().replaceNode(this, ctr);//右の子がいなかった場合、左の子を昇格させるだけで良い。
+                    if (leftSubTreeNodeTaple.rebuild()) {
+                        Node<K, V> node = leftSubTreeNodeTaple.getNode();
+                        Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right());
+                        return node.deleteBalance(newParent, ctr);
+                    }
+                    Node<K,V> leftSubTreeNode = leftSubTreeNodeTaple.getNode();
+                    newNode = createNode(this.left().getKey(), this.left().getValue(), leftSubTreeNode, this.right());
+                    return new Taple(false, newNode);
             }
         }
     }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java	Tue Sep 01 05:04:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/EmptyNode.java	Tue Sep 01 16:09:08 2015 +0900
@@ -44,13 +44,13 @@
     }
 
     @Override
-    public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) { // not use method
-        return this;
+    public Taple<K, V> replaceNode(Node<K, V> parent, Comparator ctr) { // not use method
+        return new Taple<>(false, this);
     }
 
     @Override
-    protected Node<K,V> deleteNode() { //not use method
-        return this;
+    protected Taple<K, V> deleteNode() { //not use method
+        return new Taple<>(false, this);
     }
 
     @Override
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java	Tue Sep 01 05:04:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Node.java	Tue Sep 01 16:09:08 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 Taple delete(K key, Node<K, V> parent, Comparator ctr, Rotate side) {
         if (this.isNotEmpty()) {
+            Taple taple;
             int result = compare(key, ctr);
+            if (result > 0) {
+                taple = right.delete(key, this, ctr, Rotate.R);
+            } else if (result < 0) {
+                taple = left.delete(key, this, ctr, Rotate.L);
+            } else { //Equal
+                taple = replaceNode(parent, ctr);
+            }
+            if (parent == null)
+                return taple;
+            Node<K, V> node = taple.getNode();
+            if (taple.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 Taple<>(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 Taple deleteSubTreeMaxNode(Node<K, V> parent, Comparator ctr, Rotate side) {
+        Taple taple;
         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()) {//最大値のノードが取得できるまで潜る
+            taple = right().deleteSubTreeMaxNode(this, ctr, Rotate.R);
+        } else {
+            taple = this.replaceNode(parent, ctr);
+        }
+        if (parent == null)
+            return taple;
+
+        if (taple.rebuild()) {
+            node = taple.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(), taple.getNode());
         else
-            return parent.createNode(parent.getKey(), parent.getValue(), node, parent.right());
-
+            node = parent.createNode(parent.getKey(), parent.getValue(), taple.getNode(), parent.right());
+        return new Taple<>(false, node);
     }
 
-    public Node<K, V> deleteBalance(Node<K, V> parent, Comparator ctr) throws RotateParent {
+    public Taple<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 Taple<>(true, newNode);
+                        }
+                        if (rightChild) {
+                            newNode = rebuildfive(parent, Rotate.R);
+                            return new Taple<>(false, newNode);
+                        } else {
+                            newNode = rebuildsix(parent, Rotate.R);
+                            return new Taple<>(false, newNode);
+                        }
                     } else { //左の子が赤
-                        return rebuildTwo(parent, ctr, Rotate.R);
+                        newNode = rebuildTwo(parent, ctr, Rotate.R);
+                        return new Taple<>(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 Taple<>(false, newNode);
+                    }
+                    if (rightChild) {
+                        newNode = rebuildfive(parent, Rotate.R);
+                        return new Taple<>(false, newNode);
+                    } else {
+                        newNode = rebuildsix(parent, Rotate.R);
+                        return new Taple<>(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 Taple<>(true, newNode);
+                        }
+                        if (rightChild) {
+                            newNode = rebuildsix(parent, Rotate.L);
+                            return new Taple<>(false, newNode);
+                        } else {
+                            newNode = rebuildfive(parent, Rotate.L);
+                            return new Taple<>(false, newNode);
+                        }
                     } else { //左の子が赤
-                        return rebuildTwo(parent, ctr, Rotate.L);
+                        newNode = rebuildTwo(parent, ctr, Rotate.L);
+                        return new Taple<>(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 Taple<>(false, newNode);
+                    }
+                    if (rightChild) {
+                        newNode = rebuildsix(parent, Rotate.L);
+                        return new Taple<>(false, newNode);
+                    } else {
+                        newNode = rebuildfive(parent, Rotate.L);
+                        return new Taple<>(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 Taple<>(false, newNode);
+        } else {
+            newNode = parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
+            return new Taple<>(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);
+            Taple<K, V> taple = new Taple<>(false, leftSubTreeRoot);
+            Taple<K, V> leftNodeTaple = this.deleteBalance(taple.getNode(), ctr);
             Node<K, V> rightNode = node.right();
-            return parent.createNode(node.getKey(), node.getValue(), leftNode, rightNode);
+            return parent.createNode(node.getKey(), node.getValue(), leftNodeTaple.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);
+            Taple<K, V> rightSubTreeTaple = new Taple<>(false, rightSubTreeRoot);
+            Taple<K, V> rightNodeTaple = this.deleteBalance(rightSubTreeTaple.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, rightNodeTaple.getNode());
         }
     }
 
@@ -284,9 +299,9 @@
 
     abstract boolean isRed();
 
-    public abstract Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent;
+    public abstract Taple replaceNode(Node<K, V> parent, Comparator ctr);
 
-    protected abstract Node deleteNode() throws RotateParent;
+    protected abstract Taple deleteNode();
 
     @Test
     // test method
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java	Tue Sep 01 05:04:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/RedNode.java	Tue Sep 01 16:09:08 2015 +0900
@@ -29,8 +29,9 @@
     }
 
     @Override
-    protected Node<K, V> deleteNode() throws RotateParent {
-        return new EmptyNode<>(this.getKey());
+    protected Taple deleteNode() {
+        Node emptyNode = new EmptyNode<>(this.getKey());
+        return new Taple(false, emptyNode);
     }
 
     @Override
@@ -57,16 +58,16 @@
 
     @SuppressWarnings("unchecked")
     @Override
-    public Node<K, V> replaceNode(Node<K, V> parent, Comparator ctr) throws RotateParent {
+    public Taple 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 Taple(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 Taple(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);
+                Taple<K, V> leftSubTreeNodeTaple = this.left().deleteSubTreeMaxNode(null, ctr, Rotate.L);
+                if (leftSubTreeNodeTaple.rebuild()) {
+                    Node<K, V> node = leftSubTreeNodeTaple.getNode();
+                    Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), node, this.right());
+                    return node.deleteBalance(newParent, ctr);
                 }
+                Node<K, V> leftSubTreeNode = leftSubTreeNodeTaple.getNode();
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                return new Taple<>(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();
+                Taple<K, V> leftSubTreeNodeTaple = this.left().replaceNode(this, ctr);
+                if (leftSubTreeNodeTaple.rebuild()) {
+                    Node<K, V> node = leftSubTreeNodeTaple.getNode();
                     Node<K, V> newParent = createNode(this.left().getKey(), this.left().getValue(), node, this.right());
                     return node.deleteBalance(newParent, ctr);
                 }
+                Node<K, V> leftSubTreeNode = leftSubTreeNodeTaple.getNode();
+                newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
+                return new Taple<>(false, newNode);
             }
 
         }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/Taple.java	Tue Sep 01 16:09:08 2015 +0900
@@ -0,0 +1,24 @@
+package jp.ac.u_ryukyu.ie.cr.jungle.data.treemap;
+
+
+public class Taple<K,V> {
+    private final Boolean rebuild;
+    private final Node<K,V> node;
+
+    public Taple(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/jungle/data/treemap/TreeMap.java	Tue Sep 01 05:04:38 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/jungle/data/treemap/TreeMap.java	Tue Sep 01 16:09:08 2015 +0900
@@ -53,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;
+        Taple<K,V> rootTaple = root.delete(key, null, comparator, Rotate.N);
+        if (!rootTaple.notEmpty())
             return this; // not key
-        if (!node.isNotEmpty())
+        Node<K,V> root = rootTaple.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);
     }