--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/main/csharp/jp.ac.u-ryukyu.ie.cr/jungle/data/treemap/TreeMapNode.cs	Tue Jun 21 17:11:12 2016 +0900
@@ -0,0 +1,338 @@
+using System.Collections;
+using System;
+using UnityEngine;
+
+
+public abstract class  TreeMapNode<K,V>
+{
+// K,Vがnullableではないので受け付けない
+	// ジェネリックの扱いがJavaとちがうー＞特にnullの扱いが面倒。
+	protected  K key;
+	protected  V value;
+	protected TreeMapNode<K,V> right;
+	protected TreeMapNode<K,V> left;
+
+	void Start(){
+		key = default(K);
+		value = default(V);
+	}
+
+	//  Use this for initialization
+	public TreeMapNode (K key, V value)
+	{
+		this.key = key;
+		this.value = value;
+	}
+
+	public TreeMapNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right)
+	{
+		this.key = key;
+		this.value = value;
+		this.right = right;
+		this.left = left;
+	}
+
+	public TreeMapNode<K,V> lefts ()
+	{
+		return left;
+	}
+		
+
+	public int compare(K compareKey, Comparer ctr)  {
+		return ctr.Compare(compareKey, this.getKey());
+	}
+    
+	public V get (K key, Comparer ctr)
+ 	{
+ 		TreeMapNode<K,V> cur = this;
+		int result = cur.compare (key, ctr);
+		while (cur.isNotEmpty ()) {
+			if (result > 0) {
+				cur = cur.rights ();
+				Debug.Log (cur);
+			} else if (result < 0) {
+				cur = cur.lefts ();
+			} else if (result == 0) {
+				if (cur != null) {
+					return cur.getValue ();
+				}
+			}
+		}
+		return default(V); // Optional<V>.ofNullable (null);
+	}
+
+
+
+	public TreeMapNode<K,V> rights () {
+		return right;
+	}
+
+	public K getKey () {
+		return key;
+	}
+
+	public V getValue () {
+		return value;
+	}
+
+	// may be to use Comparer??
+	public TreeMapNode<K,V> put (K k, V v,Comparer ctr) {
+
+		if (!isNotEmpty ()) {
+			return createNode (k, value, left, right);
+		}
+
+		int result = compare (k,ctr);
+		if (result > 0) {
+			TreeMapNode<K,V> node = right.put (k, value,ctr);
+			node = createNode (key, this.value, left, node);
+			return node.insBalance ();
+		} else if (result < 0) {
+			TreeMapNode<K,V> node = left.put (k, value,ctr);
+			return createNode (key, this.value, node, right).insBalance ();
+		}
+		return createNode (key, value, left, right);
+	}
+		
+	public rebuildNode<K,V> delete (K key, TreeMapNode<K,V> parent, Comparer ctr, Rotate side)
+	{
+		if (this.isNotEmpty ()) {
+			rebuildNode<K,V> rebuildNode;
+			int result = compare(key, ctr);
+			if (result > 0) {
+				rebuildNode = right.delete (key, this, ctr, Rotate.R);
+			} else if (result < 0) {
+				rebuildNode = left.delete (key, this, ctr, Rotate.L);
+			} else {
+				rebuildNode = replaceNode (parent, ctr);
+			}
+			if (parent == null) {
+				return rebuildNode;
+			}
+			TreeMapNode<K,V> node = rebuildNode.getNode ();
+			if (rebuildNode.rebuilds ()) {
+				// ここのエラーは後で
+				return node.deleteBalance (parent, ctr);
+			}
+			TreeMapNode<K,V> newParent;
+			if (side == Rotate.L) {
+				newParent = parent.createNode (parent.getKey (), parent.getValue (), node, parent.rights ());
+			} else {
+				newParent = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), node);
+			}
+			return new rebuildNode<K,V> (false, newParent);
+		}
+		return null;
+	}
+
+	public rebuildNode<K,V> deleteSubTreeMaxNode (TreeMapNode<K, V> parent, Comparer ctr, Rotate side)
+	{
+		rebuildNode<K,V> rebuildNode;
+		TreeMapNode<K, V> node;
+		if (rights ().isNotEmpty ()) {// 最大値のノードが取得できるまで潜る
+			rebuildNode = rights ().deleteSubTreeMaxNode (this, ctr, Rotate.R);
+		} else {
+			rebuildNode = this.replaceNode (parent, ctr);
+		}
+		if (parent == null)
+			return rebuildNode;
+
+		if (rebuildNode.rebuilds ()) {
+			node = rebuildNode.getNode ();
+			return node.deleteBalance (parent, ctr);
+		}
+		if (side == Rotate.R)
+			node = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), rebuildNode.getNode ());
+		else
+			node = parent.createNode (parent.getKey (), parent.getValue (), rebuildNode.getNode (), parent.rights ());
+		return new rebuildNode<K,V> (false, node);
+	}
+
+
+	public rebuildNode<K, V> deleteBalance (TreeMapNode<K, V> parent, Comparer ctr)
+	{
+		TreeMapNode<K, V> newNode = null;
+		if (!isRed ()) {
+			if (0 > compare (parent.getKey (), ctr)) {
+				bool rightChild = parent.lefts ().rights ().isRed ();
+				bool leftChild = parent.lefts ().lefts ().isRed ();
+
+				if (!parent.isRed ()) {
+					if (!parent.lefts ().isRed ()) {
+						if (!rightChild && !leftChild) {
+							newNode = rebuildThree (parent, Rotate.R);
+							return new rebuildNode<K,V> (true, newNode);
+						}
+						if (rightChild) {
+							newNode = rebuildfive (parent, Rotate.R);
+							return new rebuildNode<K,V> (false, newNode);
+						} else {
+							newNode = rebuildsix (parent, Rotate.R);
+							return new rebuildNode<K,V> (false, newNode);
+						}
+					} else { // 左の子が赤
+						newNode = rebuildTwo (parent, ctr, Rotate.R);
+						return new rebuildNode<K,V> (false, newNode);
+					}
+				} else { // 親が赤
+					if (!rightChild && !leftChild) {
+						newNode = rebuildFour (parent, Rotate.R);
+						return new rebuildNode<K,V> (false, newNode);
+					}
+					if (rightChild) {
+						newNode = rebuildfive (parent, Rotate.R);
+						return new rebuildNode<K,V> (false, newNode);
+					} else {
+						newNode = rebuildsix (parent, Rotate.R);
+						return new rebuildNode<K,V> (false, newNode);
+					}
+				}
+			} else {
+				bool rightChild = parent.rights ().rights ().isRed ();
+				bool leftChild = parent.rights ().lefts ().isRed ();
+
+				if (!parent.isRed ()) { // 親が黒
+					if (!parent.rights ().isRed ()) { // 左の子が黒
+						if (!rightChild && !leftChild) {
+							newNode = rebuildThree (parent, Rotate.L);
+							return new rebuildNode<K,V> (true, newNode);
+						}
+						if (rightChild) {
+							newNode = rebuildsix (parent, Rotate.L);
+							return new rebuildNode<K,V> (false, newNode);
+						} else {
+							newNode = rebuildfive (parent, Rotate.L);
+							return new rebuildNode<K,V> (false, newNode);
+						}
+					} else { // 左の子が赤
+						newNode = rebuildTwo (parent, ctr, Rotate.L);
+						return new rebuildNode<K,V> (false, newNode);
+					}
+				} else { // 親が赤
+					if (!rightChild && !leftChild) {
+						newNode = rebuildFour (parent, Rotate.L);
+						return new rebuildNode<K,V> (false, newNode);
+					}
+					if (rightChild) {
+						newNode = rebuildsix (parent, Rotate.L);
+						return new rebuildNode<K,V> (false, newNode);
+					} else {
+						newNode = rebuildfive (parent, Rotate.L);
+						return new rebuildNode<K,V> (false, newNode);
+					}
+				}
+			}
+		}
+		if (0 > (compare (parent.getKey (), ctr))) {
+			newNode = parent.createNode (parent.getKey (), parent.getValue (), parent.lefts (), this);
+			return new rebuildNode<K,V> (false, newNode);
+		} else {
+			newNode = parent.createNode (parent.getKey (), parent.getValue (), this, parent.rights ());
+			return new rebuildNode<K,V> (false, newNode);
+		}
+	}
+
+	protected TreeMapNode<K, V> rebuildTwo (TreeMapNode<K, V> parent, Comparer ctr, Rotate side)
+	{ //  case2
+		if (side == Rotate.L) { //  rotate Left
+			TreeMapNode<K, V> node = parent.rights ();
+			TreeMapNode<K, V> leftSubTreeRoot = node.createNode (parent.getKey (), parent.getValue (), this, node.lefts ()); //  check
+			rebuildNode<K, V> rebuildNode = new rebuildNode<K,V> (false, leftSubTreeRoot);
+			rebuildNode<K, V> leftNodeRebuildNode = this.deleteBalance (rebuildNode.getNode (), ctr);
+			TreeMapNode<K, V> rightNode = node.rights ();
+			return parent.createNode (node.getKey (), node.getValue (), leftNodeRebuildNode.getNode (), rightNode);
+		} else {  //  rotate Right
+			TreeMapNode<K, V> node = parent.lefts ();
+			TreeMapNode<K, V> rightSubTreeRoot = node.createNode (parent.getKey (), parent.getValue (), node.rights (), this);
+			rebuildNode<K, V> rightSubTreeRebuildNode = new rebuildNode<K,V> (false, rightSubTreeRoot);
+			rebuildNode<K, V> rightNodeRebuildNode = this.deleteBalance (rightSubTreeRebuildNode.getNode (), ctr);
+			TreeMapNode<K, V> leftNode = node.lefts ();
+			return parent.createNode (node.getKey (), node.getValue (), leftNode, rightNodeRebuildNode.getNode ());
+		}
+	}
+
+	protected TreeMapNode<K, V> rebuildThree (TreeMapNode<K, V> parent, Rotate side)
+	{ //  case3 再帰
+		if (side == Rotate.L) {
+			TreeMapNode<K, V> rightNode;
+			if (parent.rights ().isNotEmpty ())
+				rightNode = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts (), parent.rights ().rights ()); //  check
+			else
+				rightNode = new EmptyNode<K,V> ();
+			return parent.createNode (parent.getKey (), parent.getValue (), this, rightNode);
+		} else {
+			TreeMapNode<K, V> leftNode;
+			if (parent.lefts ().isNotEmpty ())
+				leftNode = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ()); //  check
+			else
+				leftNode = new EmptyNode<K,V> ();
+			return parent.createNode (parent.getKey (), parent.getValue (), leftNode, this);
+		}
+	}
+
+	protected TreeMapNode<K, V> rebuildFour (TreeMapNode<K, V> parent, Rotate side)
+	{ // case 4
+		if (side == Rotate.R) {
+			TreeMapNode<K, V> leftNode = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ());
+			return new BlackNode<K,V> (parent.getKey (), parent.getValue (), leftNode, this);
+		} else {
+			TreeMapNode<K, V> rightNode = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts (), parent.rights ().rights ());
+			return new BlackNode<K,V> (parent.getKey (), parent.getValue (), this, rightNode);
+		}
+	}
+
+	protected TreeMapNode<K, V> rebuildfive (TreeMapNode<K, V> parent, Rotate side)
+	{ // case5
+		if (side == Rotate.R) { //  rotate Left
+			TreeMapNode<K, V> leftChild = new RedNode<K,V> (parent.lefts ().getKey (), parent.lefts ().getValue (), parent.lefts ().lefts (), parent.lefts ().rights ().lefts ());
+			TreeMapNode<K, V> rightChild = parent.lefts ().rights ().rights ();
+			TreeMapNode<K, V> leftSubTreeRoot = new BlackNode<K,V> (parent.lefts ().rights ().getKey (), parent.lefts ().rights ().getValue (), leftChild, rightChild);
+			TreeMapNode<K, V> newParent = parent.createNode (parent.getKey (), parent.getValue (), leftSubTreeRoot, this);
+			return this.rebuildsix (newParent, Rotate.R);
+		} else {  //  rotate Right 修正済み
+			TreeMapNode<K, V> leftChild = parent.rights ().lefts ().lefts ();
+			TreeMapNode<K, V> rightChild = new RedNode<K,V> (parent.rights ().getKey (), parent.rights ().getValue (), parent.rights ().lefts ().rights (), parent.rights ().rights ());
+			TreeMapNode<K, V> rightSubTreeRoot = new BlackNode<K,V> (parent.rights ().lefts ().getKey (), parent.rights ().lefts ().getValue (), leftChild, rightChild);
+			TreeMapNode<K, V> newParent = parent.createNode (parent.getKey (), parent.getValue (), this, rightSubTreeRoot);
+			return this.rebuildsix (newParent, Rotate.L);
+		}
+	}
+
+	protected TreeMapNode<K, V> rebuildsix (TreeMapNode<K, V> parent, Rotate side)
+	{ // case6
+		if (side == Rotate.L) { //  rotate Left
+			TreeMapNode<K, V> leftChild = parent.rights ().createNode (parent.getKey (), parent.getValue (), this, parent.rights ().lefts ()); // check
+			TreeMapNode<K, V> rightChild = new BlackNode<K,V> (parent.rights ().rights ().getKey (), parent.rights ().rights ().getValue (), parent.rights ().rights ().lefts (), parent.rights ().rights ().rights ());
+			return parent.createNode (parent.rights ().getKey (), parent.rights ().getValue (), leftChild, rightChild);
+		} else {  //  rotate Right
+			TreeMapNode<K, V> leftChild = new BlackNode<K,V> (parent.lefts ().lefts ().getKey (), parent.lefts ().lefts ().getValue (), parent.lefts ().lefts ().lefts (), parent.lefts ().lefts ().rights ());
+			TreeMapNode<K, V> rightChild = parent.lefts ().createNode (parent.getKey (), parent.getValue (), parent.lefts ().rights (), this);
+			return parent.createNode (parent.lefts ().getKey (), parent.lefts ().getValue (), leftChild, rightChild);
+		}
+	}
+
+
+
+
+
+
+
+
+	public abstract bool isNotEmpty ();
+
+	public abstract TreeMapNode<K,V> createNode (K key, V value, TreeMapNode<K,V> left, TreeMapNode<K,V> right);
+
+	public abstract TreeMapNode<K,V> insBalance ();
+
+
+	public abstract Rotate checkRotate (Rotate side);
+
+	public abstract bool isRed ();
+
+	public abstract rebuildNode<K,V> replaceNode (TreeMapNode<K,V> parent, Comparer ctr);
+
+	public abstract rebuildNode<K,V> deleteNode ();
+
+	// test method
+	public abstract int checkDepth (int count, int minCount);
+}