using System.Collections;
using System;
using UnityEngine;
using System.Collections.Generic;


public abstract class  TreeMapNode<K,V>
{

	protected  K key = default(K);
	protected  V value = default(V);
	public TreeMapNode<K,V> right;
	public TreeMapNode<K,V> left;


	//  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 virtual TreeMapNode<K,V> lefts ()
	{
		return left;
	}
		

	public int compare(K compareKey, Comparer<K> ctr)  {
		int val = (int) ctr.Compare (compareKey, this.getKey ());
		return val;
	}
    
	public V get (K key, Comparer<K> ctr)
 	{
 		TreeMapNode<K,V> cur = this;
		while (cur.isNotEmpty ()) { // getでEmpty nodeを返している ? compareでKeyが０になっている
			int result = cur.compare (key, ctr);
			if (result > 0) {
				cur = cur.rights ();
			} else if (result < 0) {
				cur = cur.lefts ();
			} else if (result == 0) {
				if (cur != null) {
					return cur.getValue ();
				}
			}
		}
		return default(V);
	}



	public virtual 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<K> ctr) {

		if (!isNotEmpty ()) {
			return createNode (k, v, left, right);
		}

		int result = compare (k, ctr);
		if (result > 0) {
			TreeMapNode<K,V> node = right.put (k, v, ctr);
			node = createNode (key, this.value, left, node);
			return node.insBalance ();
		} else if (result < 0) {
			TreeMapNode<K,V> node = left.put (k, v,ctr);
			return createNode (key, this.value, node, right).insBalance ();
		}
		return createNode (key, v, left, right);
	}
		
	public rebuildNode<K,V> delete (K key, TreeMapNode<K,V> parent, Comparer<K> ctr, Rotate side)
	{
		if (this.isNotEmpty ()) {
			rebuildNode<K,V> rebuildNode = null;
			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 if (result == 0){
				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<K> 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<K> 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<K> 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<K> ctr);

	public abstract rebuildNode<K,V> deleteNode ();

	// test method
	public abstract int checkDepth (int count, int minCount);
}