changeset 11:ef442c796b20

change method name exitNode to isNotEmpty and checkColor to isRed
author tatsuki
date Fri, 17 Apr 2015 18:06:05 +0900
parents 6304463eefbf
children 73e915f29b42
files src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java
diffstat 4 files changed, 38 insertions(+), 38 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Fri Apr 17 14:16:36 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Fri Apr 17 18:06:05 2015 +0900
@@ -30,7 +30,7 @@
 
 
     @Override
-    protected boolean exitNode() {
+    protected boolean isNotEmpty() {
         return true;
     }
 
@@ -79,7 +79,7 @@
     }
 
     @Override
-    boolean checkColor() {
+    boolean isRed() {
         return false;
     }
 
@@ -93,18 +93,18 @@
     public Node replaceNode(Node<K, V> parent) {
 
         Node<K, V> newNode = null;
-        if (!this.left().exitNode() && !this.right().exitNode()) { //自身を削除する
+        if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
             return deleteNode();//黒が1つ減るので木のバランスを取る
 
-        } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる
+        } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = createNode(left().getKey(), left().getValue(), left().left(), left().right());
-            if (!this.left().checkColor()) //昇格させる木のrootが黒だったらバランスを取る
+            if (!this.left().isRed()) //昇格させる木のrootが黒だったらバランスを取る
                 newNode.setRebuildFlag(true);
             return newNode;
 
-        } else if (!this.left().exitNode() && this.right().exitNode()) { //右の部分木を昇格させる
+        } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = createNode(right().getKey(), right().getValue(), right().left(), right().right());
-            if (!this.right().checkColor()) //昇格させる木のrootが黒だったらバランスを取る
+            if (!this.right().isRed()) //昇格させる木のrootが黒だったらバランスを取る
                 newNode.setRebuildFlag(true);
             return newNode;
 
@@ -112,12 +112,12 @@
             //左の部分木の最大の値を持つNodeと自身を置き換える
             Node<K, V> cur = this.left();
 
-            while (cur.right().exitNode()) { //左の部分期の最大値を持つNodeを取得する
+            while (cur.right().isNotEmpty()) { //左の部分期の最大値を持つNodeを取得する
                 cur = cur.right();
             }
 
 
-            if (this.left().right().exitNode()) { //左の部分木が右の子を持っているか
+            if (this.left().right().isNotEmpty()) { //左の部分木が右の子を持っているか
                 Node<K, V> leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);//最大値を削除した左の部分木を返す。rootはthisと同じ。
                 Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
                 newNode = leftSubTreeNode.deleteBalance(newParent);
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Fri Apr 17 14:16:36 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Fri Apr 17 18:06:05 2015 +0900
@@ -29,7 +29,7 @@
 
 
     @Override
-    protected boolean exitNode() {
+    protected boolean isNotEmpty() {
         return false;
     }
 
@@ -71,7 +71,7 @@
     }
 
     @Override
-    boolean checkColor() {
+    boolean isRed() {
         return false;
     }
 
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Fri Apr 17 14:16:36 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Fri Apr 17 18:06:05 2015 +0900
@@ -39,7 +39,7 @@
 
         Node<K, V> cur = this;
 
-        while (cur.exitNode()) {
+        while (cur.isNotEmpty()) {
             int result = compare(key);
 
             if (result > 0)
@@ -87,7 +87,7 @@
     }
 
     public Node<K, V> delete(K key, Node<K, V> parent) {
-        if (this.exitNode()) {
+        if (this.isNotEmpty()) {
             int result = compare(key);;
 
             if (result > 0) {
@@ -116,7 +116,7 @@
     public Node<K, V> deleteSubTreeMaxNode(Node<K, V> parent) {
 
         Node<K, V> node;
-        if (right().exitNode()) {//最大値のノードが取得できるまで潜る
+        if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
             node = right().deleteSubTreeMaxNode(this);
             if (parent == null)
                 return node;
@@ -134,16 +134,16 @@
 
     public Node deleteBalance(Node<K, V> parent){
 
-        if (rebuildFlag && !checkColor()) {
+        if (rebuildFlag && !isRed()) {
 
             if (0 > compare(parent.getKey())) { //自身がどちらの子かを調べる
-                boolean rightChild = parent.left().right().checkColor();
-                boolean leftChild = parent.left().left().checkColor();
+                boolean rightChild = parent.left().right().isRed();
+                boolean leftChild = parent.left().left().isRed();
 
 
-                if (!parent.checkColor()) { //親が黒
+                if (!parent.isRed()) { //親が黒
 
-                    if (!parent.left().checkColor()) { //左の子が黒
+                    if (!parent.left().isRed()) { //左の子が黒
 
                         if (!rightChild && !leftChild)
                             return rebuildThree(parent, Rotate.R);
@@ -171,13 +171,13 @@
                 }
 
             } else {
-                boolean rightChild = parent.right().right().checkColor();
-                boolean leftChild = parent.right().left().checkColor();
+                boolean rightChild = parent.right().right().isRed();
+                boolean leftChild = parent.right().left().isRed();
 
 
-                if (!parent.checkColor()) { //親が黒
+                if (!parent.isRed()) { //親が黒
 
-                    if (!parent.right().checkColor()) { //左の子が黒
+                    if (!parent.right().isRed()) { //左の子が黒
 
                         if (!rightChild && !leftChild)
                             return rebuildThree(parent, Rotate.L);
@@ -234,7 +234,7 @@
     protected Node rebuildThree(Node<K, V> parent, Rotate side) { // case3 再起
         if (side == Rotate.L) {
             Node<K, V> rightNode;
-            if (parent.right().exitNode())
+            if (parent.right().isNotEmpty())
                 rightNode = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left(), parent.right().right()); // check
             else
                 rightNode = new EmptyNode<>();
@@ -244,7 +244,7 @@
 
         } else {
             Node<K, V> leftNode;
-            if (parent.left().exitNode())
+            if (parent.left().isNotEmpty())
                 leftNode = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right()); // check
             else
                 leftNode = new EmptyNode<>();
@@ -305,7 +305,7 @@
     }
 
 
-    protected abstract boolean exitNode();
+    protected abstract boolean isNotEmpty();
 
     public abstract Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right);
 
@@ -313,7 +313,7 @@
 
     abstract Rotate checkRotate(Rotate side);
 
-    abstract boolean checkColor();
+    abstract boolean isRed();
 
     public abstract Node replaceNode(Node<K, V> parent);
 
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Fri Apr 17 14:16:36 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Fri Apr 17 18:06:05 2015 +0900
@@ -14,7 +14,7 @@
 
 
     @Override
-    protected boolean exitNode() {
+    protected boolean isNotEmpty() {
         return true;
     }
 
@@ -37,19 +37,19 @@
     Rotate checkRotate(Rotate side) {
 
         if (side == L) {
-            if (left.checkColor())
+            if (left.isRed())
                 return R;
 
-            else if (right.checkColor())
+            else if (right.isRed())
                 return LR;
 
             return N;
         } else {
 
-            if (left.checkColor())
+            if (left.isRed())
                 return RL;
 
-            else if (right.checkColor())
+            else if (right.isRed())
                 return L;
 
             return N;
@@ -58,7 +58,7 @@
     }
 
     @Override
-    boolean checkColor() {
+    boolean isRed() {
         return true;
     }
 
@@ -66,14 +66,14 @@
     public Node replaceNode(Node<K, V> parent) {
 
         Node<K, V> newNode = null;
-        if (!this.left().exitNode() && !this.right().exitNode()) { //自身を削除する
+        if (!this.left().isNotEmpty() && !this.right().isNotEmpty()) { //自身を削除する
             return deleteNode();
 
-        } else if (this.left().exitNode() && !this.right().exitNode()) { //左の部分木を昇格させる
+        } else if (this.left().isNotEmpty() && !this.right().isNotEmpty()) { //左の部分木を昇格させる
             newNode = left().createNode(left().getKey(), left().getValue(), left().left(), left().right());
             return newNode;
 
-        } else if (!this.left().exitNode() && this.right().exitNode()) { //右の部分木を昇格させる
+        } else if (!this.left().isNotEmpty() && this.right().isNotEmpty()) { //右の部分木を昇格させる
             newNode = right().createNode(right().getKey(), right().getValue(), right().left(), right().right());
             return newNode;
 
@@ -81,13 +81,13 @@
             //左の部分木の最大の値を持つNodeと自身を置き換える
             Node<K, V> cur = this.left();
 
-            while (cur.right().exitNode()) {
+            while (cur.right().isNotEmpty()) {
                 cur = cur.right();
             }
 
             Node<K, V> leftSubTreeNode = new EmptyNode<>();
 
-            if (this.left().right().exitNode()) {
+            if (this.left().right().isNotEmpty()) {
                 leftSubTreeNode = this.left().deleteSubTreeMaxNode(null);
                 newNode = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right());
                 return leftSubTreeNode.deleteBalance(newNode);