Mercurial > hg > Members > tatsuki > TreeMap

changeset 16:19dd02f1ee8e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change getMethod and fix bug for emptyNode
author tatsuki
date Tue, 21 Apr 2015 17:29:15 +0900
parents c14ae14c57ae
children ab026848665a
files 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/TreeMap.java src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapTest.java
diffstat 4 files changed, 29 insertions(+), 93 deletions(-) [+]
line wrap: on
line diff
--- 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;
--- 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);
         }
-
     }
 
 
--- 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());
--- 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--) {