Mercurial > hg > Members > tatsuki > TreeMap

changeset 1:969798e3d330

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change state pattern
author tatsuki
date Thu, 26 Mar 2015 12:10:56 +0900
parents 79ea730fa2f1
children d8f78957698f
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/Rotate.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 7 files changed, 334 insertions(+), 84 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/BlackNode.java	Thu Mar 26 12:10:56 2015 +0900
@@ -0,0 +1,65 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
+
+import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
+
+
+public class BlackNode<K, V> extends Node<K, V> {
+
+
+    public BlackNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+        super(key, value, left, right);
+    }
+
+    @Override
+    public Node clone() {
+        return new BlackNode<K, V>(key, value, left, right);
+    }
+
+    @Override
+    public Node<K,V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+        return new BlackNode<K, V>(key, value, left, right);
+    }
+
+
+    @Override
+    Node balance() {
+        Rotate spin = left.firstCheckColor(L);
+
+        if (spin == R) {
+            Node<K, V> leftChild = new BlackNode<K,V>(left.left().getKey(), left.left().getValue(), left.left().left(), left.left().right());
+            Node<K,V> rightChild = new BlackNode<K,V>(getKey(), getValue(), left.right(), right);
+            return new RedNode<K,V>(left.getKey(), left.getValue(), leftChild, rightChild);
+
+        } else if (spin == LR) {
+            Node<K,V> leftChild = new BlackNode<K,V>(left.getKey(), left.getValue(), left.left(), left.right().left());
+            Node<K,V> rightChild = new BlackNode<K,V>(getKey(), getValue(), left.right().right(), right);
+            return new RedNode<K,V>(left.right().getKey(), left.right().getValue(), leftChild, rightChild);
+
+        }
+
+        spin = right.firstCheckColor(R);
+        if (spin == L) {
+            Node<K, V> leftChild = new BlackNode<K,V>(getKey(), getValue(), left, right.left());
+            Node<K, V> rightChild = new BlackNode<K,V>(right.right().getKey(), (V) right.right().getValue(), right.right().left(), right.right().right());
+            return new RedNode<K,V>(right.getKey(), right.getValue(), leftChild, rightChild);
+
+        } else if (spin == RL) {
+            Node<K, V> leftChild = new BlackNode<K,V>(getKey(), getValue(), left, right.left());
+            Node<K, V> rightChild = new BlackNode<K,V>(right.right().getKey(), right.right().getValue(), right.right().left(), right.right().right());
+            return new RedNode<K,V>(right.getKey(), right.getValue(), leftChild, rightChild);
+
+        }
+
+        return this;
+    }
+
+    @Override
+    Rotate firstCheckColor(Rotate side) {
+        return N;
+    }
+
+    @Override
+    boolean secondCheckColor() {
+        return false;
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/EmptyNode.java	Thu Mar 26 12:10:56 2015 +0900
@@ -0,0 +1,50 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
+
+import java.util.Optional;
+
+import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
+
+/**
+ * Created by e115731 on 15/03/25.
+ */
+public class EmptyNode<K, V> extends Node<K, V> {
+
+    public EmptyNode() {
+        super(null, null);
+    }
+
+    @Override
+    public Node<K, V> clone() {
+        return new EmptyNode<K, V>();
+    }
+
+    @Override
+    public Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+        return new RedNode<K, V>(key, value, new EmptyNode<K, V>(), new EmptyNode<K, V>());
+    }
+
+    @Override
+    public Node<K, V> put(Comparable<? super K> k, V value) {
+        return new RedNode(k, value, new EmptyNode<K, V>(), new EmptyNode<K, V>());
+    }
+
+    @Override
+    Node balance() {
+        return clone();
+    }
+
+    @Override
+    public Optional<V> get(Comparable<? super K> key) {
+        return Optional.ofNullable((V) getValue());
+    }
+
+    @Override
+    Rotate firstCheckColor(Rotate side) {
+        return N;
+    }
+
+    @Override
+    boolean secondCheckColor() {
+        return false;
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Node.java	Thu Mar 26 12:10:56 2015 +0900
@@ -0,0 +1,85 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
+
+import java.util.*;
+
+/**
+ * Created by e115731 on 15/03/23.
+ */
+public abstract class Node<K, V> {
+
+    protected K key;
+    protected V value;
+    protected Node<K, V> right;
+    protected Node<K, V> left;
+
+    public Node(K key, V value) {
+        this.key = key;
+        this.value = value;
+    }
+
+    public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
+        this.key = key;
+        this.value = value;
+        this.right = right;
+        this.left = left;
+    }
+
+    public Node<K, V> left() {
+        return left;
+    }
+
+    public Optional<V> get(Comparable<? super K> key) {
+
+        int result = key.compareTo(getKey());
+        if (result > 0)
+            return right().get(key);
+
+        else if (result < 0)
+            return left().get(key);
+
+        else if (result == 0)
+            return Optional.ofNullable((V) getValue());
+
+        return Optional.ofNullable(null);
+    }
+
+    public Node<K, V> right() {
+        return right;
+    }
+
+    public K getKey() {
+        return key;
+    }
+
+    public V getValue() {
+        return value;
+    }
+
+
+    public Node<K, V> put(Comparable<? super K> k, V value) {
+
+        int result = k.compareTo(this.key);
+
+        if (result > 0) {
+            Node<K, V> node = right.put(k, value);
+            node = createNode(key, this.value, left, node);
+            return node.balance();
+        } else if (result < 0) {
+            Node node = left.put(k, value);
+            return createNode(key, this.value, node, right).balance();
+        }
+
+        return createNode(key, value, left, right); // equals
+
+    }
+
+    public abstract Node clone();
+
+    public abstract Node<K, V> createNode(K key, V value, Node<K, V> left, Node<K, V> right);
+
+    abstract Node<K, V> balance();
+
+    abstract Rotate firstCheckColor(Rotate side);
+
+    abstract boolean secondCheckColor();
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/RedNode.java	Thu Mar 26 12:10:56 2015 +0900
@@ -0,0 +1,61 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
+
+import static jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Rotate.*;
+
+/**
+ * Created by e115731 on 15/03/25.
+ */
+public class RedNode<K, V> extends Node<K, V> {
+
+
+    public RedNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+        super(key, value, left, right);
+    }
+
+
+    @Override
+    public Node<K,V> clone() {
+        return new RedNode<K,V>(key, value, left, right);
+    }
+
+    @Override
+    public Node<K,V> createNode(K key, V value, Node<K, V> left, Node<K, V> right) {
+        return new RedNode<K,V>(key, value, left, right);
+    }
+
+    @Override
+    protected Node<K,V> balance() {
+        return this;
+    }
+
+    @Override
+    Rotate firstCheckColor(Rotate side) {
+
+        if (side == L) {
+            if (left.secondCheckColor())
+                return R;
+
+            else if (right.secondCheckColor())
+                return LR;
+
+            return N;
+        } else {
+
+            if (left.secondCheckColor())
+                return RL;
+
+            else if (right.secondCheckColor())
+                return L;
+
+            return N;
+        }
+
+    }
+
+    @Override
+    boolean secondCheckColor() {
+        return true;
+    }
+
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/Rotate.java	Thu Mar 26 12:10:56 2015 +0900
@@ -0,0 +1,8 @@
+package jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap;
+
+/**
+ * Created by e115731 on 15/03/23.
+ */
+public enum Rotate {
+    R, L, RL, LR, N;
+}
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Tue Mar 24 16:59:09 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/TreeMap/TreeMap.java	Thu Mar 26 12:10:56 2015 +0900
@@ -1,46 +1,36 @@
 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> {
-    Entry<K, V> root;
+    Node<K, V> root;
     int size;
 
-    public static void main(String args[]) {
-        java.util.TreeMap<Integer, Integer> map = new java.util.TreeMap<Integer, Integer>();
-        for (int count = 0; count < 100; count++) {
-            map.put(count, count);
-        }
-    }
-
     public TreeMap() {
         this.root = null;
         this.size = 0;
     }
 
-    public TreeMap(Entry<K, V> root, int size) {
+
+    public Node getRoot() {
+        return root;
+    }
+
+    public TreeMap(Node<K, V> root, int size) {
         this.root = root;
         this.size = size;
     }
 
-    public V get(K key) {
-        Entry cur = root;
-        Comparable<? super K> k = (Comparable<? super K>) key;
-        do {
-            int result = k.compareTo((K) cur.getKey());
-            if (result > 0)
-                cur = cur.right();
+    public Optional<V> get(K key) {
+        return root.get((Comparable<? super K>) key);
 
-            else if (result < 0)
-                cur = cur.left();
-
-            else if (result == 0)
-                return (V)cur.getValue();
-
-        }while(cur != null);
-        return null;
     }
 
     public TreeMap put(K key, V value) {
@@ -49,71 +39,33 @@
             throw new NullPointerException();
 
         if (isEmpty()) {
-            Entry<K, V> newRoot = new Entry<K, V>(Color.BLACK, key, value);
-            return new TreeMap(newRoot, size++);
+            Node<K, V> newRoot = new BlackNode(key, value, new EmptyNode(), new EmptyNode());
+            return new TreeMap<K, V>(newRoot, size++);
         }
 
-        Comparable<? super K> k = (Comparable<? super K>) key;
-
-        Entry newEntry = insert(k, value, root);
-        Entry root = new Entry(Color.BLACK, newEntry.getKey(), newEntry.getValue(),newEntry.left(),newEntry.right());
-        return new TreeMap(root, 0);
+        Node<K, V> newEntry = root.put((Comparable<? super K>) key, value);
+        Node<K, V> newRoot = new BlackNode(newEntry.getKey(), newEntry.getValue(), newEntry.left(), newEntry.right());
+        return new TreeMap(newRoot, 0);
     }
 
-    private Entry insert(Comparable<? super K> key, V value, Entry cur) {
-        int result = key.compareTo((K) cur.getKey());
-
-        if (result > 0) {
-            if (cur.right() == null) {
-                Entry right = new Entry(Color.RED, key, value);
-                return new Entry(cur.getColor(), cur.getKey(), cur.getValue(), cur.left(), right);
-
-            }
-            return balance(cur.left(), cur, insert(key, value, cur.right()));
-        } else if (result < 0) {
-            if (cur.left() == null) {
-                Entry left = new Entry(Color.RED, key, value);
-                return new Entry(cur.getColor(), cur.getKey(), cur.getValue(), left, cur.right());
-
-            }
-            return balance(insert(key, value, cur.left()), cur, cur.right());
-
-        } else // equal
-            return new Entry(cur.getColor(), key, value, cur.left(), cur.right());
-
-    }
-
-    private Entry balance(Entry left, Entry cur, Entry right) {
-        if (cur.getColor() == Color.BLACK && colorRedcheck(left) && colorRedcheck(left.left())) { // rotate right
-            Entry<K, V> leftChild = new Entry<K, V>(Color.BLACK, (K) left.left().getKey(), (V) left.left().getValue(), left.left().left(), left.left().right());
-            Entry<K, V> rightChild = new Entry<K, V>(Color.BLACK, (K) cur.getKey(), (V) cur.getValue(), left.right(), right);
-            return new Entry<K, V>(Color.RED, (K) left.getKey(), (V) left.getValue(), leftChild, rightChild);
-
-        } else if (cur.getColor() == Color.BLACK && colorRedcheck(left) && colorRedcheck(left.right())) { // rotate left right
-            Entry<K, V> leftChild = new Entry<K, V>(Color.BLACK, (K) left.getKey(), (V) left.getValue(), left.left(), left.right().left());
-            Entry<K, V> rightChild = new Entry<K, V>(Color.BLACK, (K) cur.getKey(), (V) cur.getValue(), left.right().right(), right);
-            return new Entry<K, V>(Color.RED, (K) left.right().getKey(), (V) left.right().getValue(), leftChild, rightChild);
-
-        } else if (cur.getColor() == Color.BLACK && colorRedcheck(right) && colorRedcheck(right.left())) { //rotate right left
-            Entry<K, V> leftChild = new Entry<K, V>(Color.BLACK, (K) cur.getKey(), (V) cur.getValue(), left, right.left().left());
-            Entry<K, V> rightChild = new Entry<K, V>(Color.BLACK, (K) right.getKey(), (V) right.getValue(), right.left().right(), right.right());
-            return new Entry<K, V>(Color.RED, (K) right.left().getKey(), (V) right.left().getValue(), leftChild, rightChild);
-
-        } else if (cur.getColor() == Color.BLACK && colorRedcheck(right) && colorRedcheck(right.right())) { //rotate left
-            Entry<K, V> leftChild = new Entry<K, V>(Color.BLACK, (K) cur.getKey(), (V) cur.getValue(), left, right.left());
-            Entry<K, V> rightChild = new Entry<K, V>(Color.BLACK, (K) right.right().getKey(), (V) right.right().getValue(), right.right().left(), right.right().right());
-            return new Entry<K, V>(Color.RED, (K) right.getKey(), (V) right.getValue(), leftChild, rightChild);
-
-        }
-        return new Entry(cur.getColor(),cur.getKey(),cur.getValue(),left,right);
-    }
-
-    private boolean colorRedcheck(Entry e) {
-        return e != null && e.getColor() == Color.RED;
-    }
 
     public boolean isEmpty() {
         return root == null;
     }
 
+    public Iterator<K> keys() {
+
+        return new Iterator<K>() {
+
+            @Override
+            public boolean hasNext() {
+                return false;
+            }
+
+            @Override
+            public K next() {
+                return null;
+            }
+        };
+    }
 }
--- a/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapTest.java	Tue Mar 24 16:59:09 2015 +0900
+++ b/src/main/java/jp/ac/u_ryukyu/ie/cr/tatsuki/test/TreeMapTest.java	Thu Mar 26 12:10:56 2015 +0900
@@ -1,18 +1,47 @@
 package jp.ac.u_ryukyu.ie.cr.tatsuki.test;
 
+import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.Node;
 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
 
+import java.util.Optional;
+
 /**
  * Created by e115731 on 15/03/24.
  */
 public class TreeMapTest {
     public static void main(String args[]) {
         TreeMap<Integer, Integer> map = new TreeMap();
-        for (int count = 0; count < 1000000; count++) {
+        TreeMap<Integer, Integer> map1 = map.put(0,0);
+        TreeMap<Integer, Integer> map2 = map1.put(1,1);
+        TreeMap<Integer, Integer> map3 = map2.put(2,2);
+        TreeMap<Integer, Integer> map4 = map3.put(3,3);
+        TreeMap<Integer, Integer> map5 = map4.put(4,4);
+        for (int count = 100; count > 0; count--) {
             map = map.put(count, count);
         }
 
-        System.out.println(map.get(999));
+        for (int count = 100; count > -10; count--) {
+
+            Optional<Integer> op = map.get(count);
+            if (op.isPresent())
+                System.out.println(op.get());
+        }
+
         System.out.println("end");
     }
 }
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+