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

public class TreeMap<K, V> {
	TreeMapNode<K, V> root;
	Comparer<K> comparator;


	public TreeMap(IComparer icompere) {
		this.root = new EmptyNode<K, V> ();
	}

	public TreeMap() {
		this.root = new EmptyNode<K, V> ();
		this.comparator =  Comparer<K>.Default;
	}

	public TreeMap(TreeMapNode<K, V> root) {
		this.root = root;
	}

	public TreeMap(TreeMapNode<K, V> root, Comparer<K> comparator) {
		this.root = root;
		this.comparator = comparator;
	}

	public TreeMapNode<K, V> getRoot() {
		return root;
	}

	public V get(K key) {
		return root.get(key, this.comparator);
	}

	public TreeMap<K, V> put(K key, V value) {
		if(isEmpty()) {
			TreeMapNode<K, V> newRoot = new BlackNode<K, V> (key, value, new EmptyNode<K, V> (), new EmptyNode<K, V> ());
			return new TreeMap<K, V> (newRoot, this.comparator);
		}

		TreeMapNode<K, V> newEntry = root.put (key, value, this.comparator);
		TreeMapNode<K, V> newRoots = new BlackNode<K, V> (newEntry.getKey (), newEntry.getValue (), newEntry.lefts (), newEntry.rights ());
		return new TreeMap<K, V> (newRoots, this.comparator);
	}
		
	public bool isEmpty() {
		return !root.isNotEmpty ();
	}

	public TreeMap<K, V> delete(K key) {
		if (key.Equals(default(K))) {
			return this;
		}
		rebuildNode<K, V> rootRebuildNode = root.delete (key, null, this.comparator, Rotate.N);
		if (!rootRebuildNode.notEmpty ()) {
			return this;
		}
		TreeMapNode<K, V> roots = rootRebuildNode.getNode ();
		if (!root.isNotEmpty ()) {
			return new TreeMap<K, V> (new EmptyNode<K, V> (), this.comparator);
		}
		TreeMapNode<K, V> newRoot = new BlackNode<K, V> (roots.getKey (), roots.getValue (), roots.lefts (), roots.rights ());
		return new TreeMap<K, V> (newRoot, this.comparator);
	}
	// like to iterator and IEmurator.
	public IEnumerator<K> keys() {
		return new iterators<K> ();
	}


	public void checkDepth() {
		root.checkDepth (0, 0);
		Debug.Log ("-----------------------------------");
	}

	public class iterators<K> : IEnumerator<K> {
		Stack<TreeMapNode<K,V>> nodeStack = new Stack<TreeMapNode<K,V>>();
		TreeMapNode<K,V> currentNode = new TreeMap<K,V>().getRoot();
		public List<K> appLines { get; set; }
		private int position;


		public bool MoveNext() {
						return currentNode != null;
					}
			

		public K Current{
			get {
				K key = currentNode.getKey ();
				if (currentNode.lefts ().isNotEmpty ()) {
					nodeStack.Push (currentNode);
					currentNode = currentNode.lefts ();
					return key;
				} else if (currentNode.rights ().isNotEmpty ()) {
					currentNode = currentNode.rights ();
					return key;
				} else if (nodeStack.Count == 0) {
					currentNode = null;
					return key;
				}
				do {
					currentNode = nodeStack.Pop ().rights ();
					if (currentNode.isNotEmpty ()) {
						return key;
					}
				}while (nodeStack.Count != 0);
				return key;
			}
		}

		object IEnumerator.Current
		{
			get { return appLines; }
		}

		public void Dispose() {
			((IEnumerator<K>)this.appLines).Dispose ();
		}

		public void Reset() {
			((IEnumerator<K>)this.appLines).Reset();
		}

	}
}