# HG changeset patch
# User tatsuki
# Date 1429604955 -32400
# Node ID 19dd02f1ee8e8639340cb5ec959bca1db308a44e
# Parent  c14ae14c57ae85a4d5424777a56f1bb5265d89bc
change getMethod and fix bug for emptyNode

diff -r c14ae14c57ae -r 19dd02f1ee8e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Mon Apr 20 08:00:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Tue Apr 21 17:29:15 2015 +0900
@@ -59,12 +59,6 @@
         return this;
     }
 
-
-    @Override
-    public Optional<V> get(K key) {
-        return Optional.ofNullable((V) getValue());
-    }
-
     @Override
     Rotate checkRotate(Rotate side) {
         return N;
diff -r c14ae14c57ae -r 19dd02f1ee8e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Mon Apr 20 08:00:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Tue Apr 21 17:29:15 2015 +0900
@@ -7,17 +7,19 @@
  */
 public abstract class Node<K, V> {
 
-    protected K key;
-    protected V value;
-    protected Node<K, V> right;
-    protected Node<K, V> left;
+    protected  final K key;
+    protected  final V value;
+    protected  final Node<K, V> right;
+    protected  final Node<K, V> left;
 
     public Node(K key, V value) {
         this.key = key;
         this.value = value;
+        this.left = null;
+        this.right = null;
     }
 
-    public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
+    public Node(K key, V value,final Node<K, V> left, final Node<K, V> right) {
         this.key = key;
         this.value = value;
         this.right = right;
@@ -28,31 +30,10 @@
         return left;
     }
 
-    public int compare(K parentKey) {
+    public int compare(final K parentKey) {
         return (parentKey.hashCode() - getKey().hashCode());
     }
 
-    public Optional<V> get(K key) {
-
-        Node<K, V> cur = this;
-
-        while (cur.isNotEmpty()) {
-            int result = cur.compare(key);
-
-            if (result > 0)
-                cur = cur.right();
-
-            else if (result < 0)
-                cur = cur.left();
-
-            else if (result == 0)
-                return Optional.ofNullable(cur.getValue());
-        }
-
-        return Optional.ofNullable(null);
-    }
-
-
     public Node<K, V> right() {
         return right;
     }
@@ -66,10 +47,22 @@
     }
 
 
-    public Node<K, V> put(K k, V value) {
+    public Optional<V> get(final K key) {
+        Node<K, V> cur = this;
+        while (cur.isNotEmpty()) {
+            final int result = cur.compare(key);
+            if (result > 0)
+                cur = cur.right();
+            else if (result < 0)
+                cur = cur.left();
+            else if (result == 0)
+                return Optional.ofNullable(cur.getValue());
+        }
+        return Optional.ofNullable(null);
+    }
 
+    public Node<K, V> put(K k, V value) {
         int result = compare(k);
-
         if (result > 0) {
             Node<K, V> node = right.put(k, value);
             node = createNode(key, this.value, left, node);
@@ -78,28 +71,22 @@
             Node node = left.put(k, value);
             return createNode(key, this.value, node, right).insBalance();
         }
-
         return createNode(key, value, left, right); // equals
-
     }
 
     public Tuple delete(K key, Node<K, V> parent) {
         if (this.isNotEmpty()) {
             int result = compare(key);
-            ;
-
             if (result > 0) {
                 Tuple node = right.delete(key, this);
                 if (parent == null || node == null)
                     return node;
                 return node.getNode().deleteBalance(parent, node.getRebuildFlag());
-
             } else if (result < 0) {
                 Tuple node = left.delete(key, this);
                 if (parent == null || node == null)
                     return node;
                 return node.getNode().deleteBalance(parent, node.getRebuildFlag());
-
             } else if (result == 0) {
                 Tuple node = replaceNode(parent); // equals
                 if (parent == null || node == null)
@@ -112,107 +99,75 @@
 
 
     public Tuple deleteSubTreeMaxNode(Node<K, V> parent) {
-
         Tuple node;
         if (right().isNotEmpty()) {//最大値のノードが取得できるまで潜る
             node = right().deleteSubTreeMaxNode(this);
             if (parent == null)
                 return node;
             return node.getNode().deleteBalance(parent, node.getRebuildFlag());
-
         }
-
-
         node = this.replaceNode(parent);
         if (parent == null)
             return node;
         return node.getNode().deleteBalance(parent, node.getRebuildFlag());
-
     }
 
     public Tuple deleteBalance(Node<K, V> parent, boolean flag) {
-
         if (flag && !isRed()) {
-
             if (0 > compare(parent.getKey())) { //自身がどちらの子かを調べる
                 boolean rightChild = parent.left().right().isRed();
                 boolean leftChild = parent.left().left().isRed();
 
-
                 if (!parent.isRed()) { //親が黒
-
                     if (!parent.left().isRed()) { //左の子が黒
-
                         if (!rightChild && !leftChild)
                             return rebuildThree(parent, Rotate.R);
-
                         if (rightChild)
                             return rebuildfive(parent, Rotate.R);
                         else if (leftChild)
                             return rebuildsix(parent, Rotate.R);
-
-
                     } else { //左の子が赤
                         return rebuildTwo(parent, Rotate.R);
                     }
-
                 } else { //親が赤
-
                     if (!rightChild && !leftChild)
                         return rebuildFour(parent, Rotate.R);
-
                     if (rightChild)
                         return rebuildfive(parent, Rotate.R);
                     else if (leftChild)
                         return rebuildsix(parent, Rotate.R);
-
                 }
-
             } else {
                 boolean rightChild = parent.right().right().isRed();
                 boolean leftChild = parent.right().left().isRed();
 
-
                 if (!parent.isRed()) { //親が黒
-
                     if (!parent.right().isRed()) { //左の子が黒
-
                         if (!rightChild && !leftChild)
                             return rebuildThree(parent, Rotate.L);
-
                         if (rightChild)
                             return rebuildsix(parent, Rotate.L);
                         else if (leftChild)
                             return rebuildfive(parent, Rotate.L);
-
-
                     } else { //左の子が赤
                         return rebuildTwo(parent, Rotate.L);
                     }
-
                 } else { //親が赤
-
                     if (!rightChild && !leftChild)
                         return rebuildFour(parent, Rotate.L);
-
                     if (rightChild)
                         return rebuildsix(parent, Rotate.L);
                     else if (leftChild)
                         return rebuildfive(parent, Rotate.L);
-
                 }
             }
-
         }
-
         Node newParent = null;
         if (0 > (compare(parent.getKey())))
             newParent = parent.createNode(parent.getKey(), parent.getValue(), parent.left(), this);
         else
             newParent = parent.createNode(parent.getKey(), parent.getValue(), this, parent.right());
-
         return new Tuple(newParent, false);
-
     }
 
     protected Tuple rebuildTwo(Node<K, V> parent, Rotate side) { // case2
@@ -241,7 +196,6 @@
                 rightNode = new EmptyNode<>();
             Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightNode);
             return new Tuple(newParent, true);
-
         } else {
             Node<K, V> leftNode;
             if (parent.left().isNotEmpty())
@@ -250,9 +204,7 @@
                 leftNode = new EmptyNode<>();
             Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftNode, this);
             return new Tuple(newParent, true);
-
         }
-
     }
 
     protected Tuple rebuildFour(Node<K, V> parent, Rotate side) { //case 4
@@ -265,26 +217,21 @@
             Node newParent = new BlackNode<K, V>(parent.getKey(), parent.getValue(), this, rightNode);
             return new Tuple(newParent, false);
         }
-
     }
 
     protected Tuple rebuildfive(Node<K, V> parent, Rotate side) { //case5
-
         if (side == Rotate.R) { // rotate Left
-
             Node<K, V> leftChild = new RedNode<K, V>(parent.left().getKey(), parent.left().getValue(), parent.left().left(), parent.left().right().left());
             Node<K, V> rightChild = parent.left().right().right();
             Node<K, V> leftSubTreeRoot = new BlackNode<K, V>(parent.left().right().getKey(), parent.left().right().getValue(), leftChild, rightChild);
             Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), leftSubTreeRoot, this);
             return this.rebuildsix(newParent, Rotate.R);
-
         } else {  // rotate Right 修正済み
             Node<K, V> leftChild = parent.right().left().left();
             Node<K, V> rightChild = new RedNode<K, V>(parent.right().getKey(), parent.right().getValue(), parent.right().left().right(), parent.right().right());
             Node<K, V> rightSubTreeRoot = new BlackNode<K, V>(parent.right().left().getKey(), parent.right().left().getValue(), leftChild, rightChild);
             Node<K, V> newParent = parent.createNode(parent.getKey(), parent.getValue(), this, rightSubTreeRoot);
             return this.rebuildsix(newParent, Rotate.L);
-
         }
     }
 
@@ -300,7 +247,6 @@
             Node newParent = parent.createNode(parent.left().getKey(), parent.left().getValue(), leftChild, rightChild);
             return new Tuple(newParent, false);
         }
-
     }
 
 
diff -r c14ae14c57ae -r 19dd02f1ee8e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Mon Apr 20 08:00:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Tue Apr 21 17:29:15 2015 +0900
@@ -1,17 +1,15 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
 
 
-import java.util.Iterator;
 import java.util.Optional;
 
-import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
 
 /**
  * Created by e115731 on 15/03/23.
  */
 public class TreeMap<K, V> {
-    Node<K, V> root;
-    int size;
+    final Node<K, V> root;
+    final int size;
 
     public TreeMap() {
         this.root = new EmptyNode();
@@ -28,9 +26,7 @@
         this.size = size;
     }
 
-    public Optional<V> get(K key) {
-        return root.get(key);
-    }
+    public Optional<V> get(final K key) {return root.get(key);}
 
     public TreeMap put(K key, V value) {
 
@@ -39,7 +35,7 @@
 
         if (isEmpty()) {
             Node<K, V> newRoot = new BlackNode(key, value, new EmptyNode(), new EmptyNode());
-            return new TreeMap<K, V>(newRoot, size++);
+            return new TreeMap<K, V>(newRoot, size + 1);
         }
 
         Node<K, V> newEntry = root.put(key, value);
@@ -49,16 +45,14 @@
 
 
     public boolean isEmpty() {
-        return root == null;
+        return !root.isNotEmpty();
     }
 
 
     public TreeMap<K,V> delete(K key) {
        Node node = root.delete(key,null).getNode();
-
         if (node == null)
             return this; // not key
-
         if (!node.isNotEmpty())
             return new TreeMap(new EmptyNode<>(),0);
         Node newRoot = new BlackNode(node.getKey(),node.getValue(),node.left(),node.right());
diff -r c14ae14c57ae -r 19dd02f1ee8e src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapTest.java
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapTest.java	Mon Apr 20 08:00:25 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapTest.java	Tue Apr 21 17:29:15 2015 +0900
@@ -18,6 +18,8 @@
         TreeMap<Integer, Integer> map5 = map4.put(4,4);
         for (int count = 100; count > 0; count--) {
             map = map.put(count, count);
+            map.checkBlackCount();
+            System.out.println("-------------------------------------------");
         }
 
         for (int count = 100; count > -10; count--) {