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

namespace JungleDB {
	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);
		}

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


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

			public T Current{
				get {
					T 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<T>)this.appLines).Dispose ();
			}

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

		}
	}
}