changeset 20:3d9be68ef707

add checkDepth
author tatsuki
date Wed, 29 Apr 2015 16:02:10 +0900
parents fae4951660b4
children a2242522c2cd
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 src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java
diffstat 6 files changed, 43 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Wed Apr 29 15:40:51 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Wed Apr 29 16:02:10 2015 +0900
@@ -1,5 +1,7 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
 
+import org.junit.Test;
+
 import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
 
 
@@ -18,12 +20,13 @@
     }
 
     @Override
-    protected int checkBlackCount(int count) { // test method
+    @Test
+    protected int checkDepth(int count, int minCount) { // test method
         count++;
-        left().checkBlackCount(count);
-        right().checkBlackCount(count);
+        minCount = left().checkDepth(count, minCount);
+        minCount = right().checkDepth(count, minCount);
         count--;
-        return count;
+        return minCount;
     }
 
 
@@ -109,7 +112,7 @@
             }
             if (this.left().right().isNotEmpty()) { //左の部分木が右の子を持っているか
                 try {
-                    Node leftSubTreeNode = this.left().deleteSubTreeMaxNode(null,Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
+                    Node leftSubTreeNode = this.left().deleteSubTreeMaxNode(null, Rotate.L);//最大値を削除した左の部分木を返す。rootはthisと同じ。
                     Node<K, V> newParent = createNode(cur.getKey(), cur.getValue(), leftSubTreeNode, this.right()); //rootをcurと入れ替えることでNodeの削除は完了する
                     return newParent;
                 } catch (RotateParent e) {
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Wed Apr 29 15:40:51 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Wed Apr 29 16:02:10 2015 +0900
@@ -1,8 +1,9 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
 
-import java.util.Optional;
+import org.junit.Assert;
+import org.junit.Test;
 
-import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
+import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.N;
 
 /**
  * Created by e115731 on 15/03/25.
@@ -70,9 +71,14 @@
     }
 
     @Override
-    protected int checkBlackCount(int count) { // test method
-        System.out.println("blackCount = " + count);
-        return count;
+    @Test
+    protected int checkDepth(int count,int minCount) { // test method
+        if (count < minCount | minCount == 0)
+            minCount = count;
+        System.out.println("depth = " + count);
+
+        Assert.assertTrue(count <=  2 * minCount);
+        return minCount;
     }
 
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Wed Apr 29 15:40:51 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Wed Apr 29 16:02:10 2015 +0900
@@ -1,11 +1,14 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
 
-import java.util.*;
+import org.junit.Test;
+
+import java.util.Optional;
+
 
 /**
  * Created by e115731 on 15/03/23.
  */
-public abstract class Node<K, V> {
+public abstract class Node<K, V>  {
 
     protected K key;
     protected V value;
@@ -288,5 +291,6 @@
 
     protected abstract Node deleteNode() throws RotateParent;
 
-    protected abstract int checkBlackCount(int count); // test method
+    @Test
+    protected abstract int checkDepth (int count , int minCount); // test method
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Wed Apr 29 15:40:51 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Wed Apr 29 16:02:10 2015 +0900
@@ -1,5 +1,7 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
 
+import org.junit.Test;
+
 import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
 
 /**
@@ -102,9 +104,12 @@
 
 
     @Override
-    protected int checkBlackCount(int count) { // test method
-        left().checkBlackCount(count);
-        right().checkBlackCount(count);
-        return count;
+    @Test
+    protected int checkDepth(int count,int minCount) { // test method
+        count ++;
+        minCount = left().checkDepth(count, minCount);
+        minCount = right().checkDepth(count, minCount);
+        count --;
+        return minCount;
     }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Wed Apr 29 15:40:51 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Wed Apr 29 16:02:10 2015 +0900
@@ -1,6 +1,8 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
 
 
+import org.junit.Test;
+
 import java.util.Optional;
 
 
@@ -59,8 +61,9 @@
         return new TreeMap(newRoot,0);
     }
 
+    @Test
     public void checkBlackCount(){
-        root.checkBlackCount(0);
+        root.checkBlackCount(0,0);
         System.out.println("-----------------------------------");
     }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Wed Apr 29 15:40:51 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapDelete.java	Wed Apr 29 16:02:10 2015 +0900
@@ -2,20 +2,22 @@
 
 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.RotateParent;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
+import org.junit.Test;
 
 import java.util.ArrayList;
 import java.util.Collections;
-import java.util.Optional;
-import java.util.Random;
 
 /**
  * Created by e115731 on 15/04/04.
  */
 public class TreeMapDelete {
+
+    @Test
     public static void main(String args[]) throws RotateParent {
         TreeMap<Integer, Integer> map = new TreeMap();
         for (int count = 1; count < 3000; count++) {
             map = map.put(count, count);
+            map.checkBlackCount();
         }
 
         ArrayList<Integer> list = new ArrayList();