using System;
using System.Collections;

namespace CornedBee.Utility
{
	/// <summary>
	/// This class is a tree node for the tree.
	/// </summary>
	internal class TreeNode
	{
		/// <summary>
		/// The parent node.
		/// </summary>
		internal TreeNode parent = null;
		/// <summary>
		/// The left child node.
		/// </summary>
		internal TreeNode left = null;
		/// <summary>
		/// The right child node.
		/// </summary>
		internal TreeNode right = null;
		/// <summary>
		/// The height of this node's subtree.
		/// </summary>
		internal int height;

		/// <summary>
		/// The data. For dictionary trees, this is a KeyValuePair.
		/// </summary>
		internal object data;

		internal IComparable DataComp
		{
			get
			{
				return (IComparable)data;
			}
		}

		internal TreeNode(object d)
		{
			data = d;
		}
	}

	/// <summary>
	/// This class is a balanced binary tree.
	/// </summary>
	internal class BinaryTree : System.Collections.ICollection
	{
		/// <summary>
		/// Test Main for this class.
		/// </summary>
		/// <param name="args">Command line arguments.</param>
		private class TreeEnumerator : IEnumerator
		{
			private BinaryTree tree;
			private TreeNode node;

			public TreeEnumerator(BinaryTree t)
			{
				tree = t;
				Reset();
			}

			#region IEnumerator Members

			public void Reset()
			{
				node = null;
			}

			public object Current
			{
				get
				{
					return node.data;
				}
			}

			public bool MoveNext()
			{
				if(node == null)
				{
					if(tree.root == null)
					{
						return false;
					}
					else
					{
						node = tree.Minimum(tree.root);
						return true;
					}
				}
				else
				{
					node = tree.Next(node);
					return node != null;
				}
			}

			#endregion

		}


		private TreeNode root = null;
		private int count = 0;

		public BinaryTree()
		{
		}

		/// <summary>
		/// Gets the minimum node in n's subtree.
		/// </summary>
		/// <param name="n">The local root node.</param>
		/// <returns>The node with the smallest value.</returns>
		internal TreeNode Minimum(TreeNode n)
		{
			while(n.left != null)
			{
				n = n.left;
			}
			return n;
		}

		/// <summary>
		/// Gets the maximum node in n's subtree.
		/// </summary>
		/// <param name="n">The local root node.</param>
		/// <returns>The node with the largest value.</returns>
		internal TreeNode Maximum(TreeNode n)
		{
			while(n.right != null)
			{
				n = n.right;
			}
			return n;
		}

		/// <summary>
		/// Returns the next node in in-order traversal.
		/// </summary>
		/// <param name="n">The current node.</param>
		/// <returns>The node with the next largest value.</returns>
		internal TreeNode Next(TreeNode n)
		{
			if(n.right != null)
			{
				return Minimum(n.right);
			}
			else
			{
				TreeNode t = n.parent;
				while(t != null && n == t.right)
				{
					n = t;
					t = t.parent;
				}
				return t;
			}
		}

		/// <summary>
		/// Returns the previous node in in-order traversal.
		/// </summary>
		/// <param name="n">The current node.</param>
		/// <returns>The node with the next smallest value.</returns>
		internal TreeNode Previous(TreeNode n)
		{
			if(n.left != null)
			{
				return Maximum(n.left);
			}
			else
			{
				TreeNode t = n.parent;
				while(t != null && n == t.left)
				{
					n = t;
					t = t.parent;
				}
				return t;
			}
		}

		/// <summary>
		/// Recalculates the height of a node.
		/// </summary>
		/// <param name="node">The node for which to recalculate the height.</param>
		private void AdjustHeight(TreeNode node)
		{
			int lw = node.left == null ? -1 : node.left.height;
			int rw = node.right == null ? -1 : node.right.height;
			node.height = Math.Max(lw, rw) + 1;
		}

		/// <summary>
		/// Helper method for rebalancing. Does a right rotation.
		/// </summary>
		/// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
		private void RotateRight(ref TreeNode node)
		{
			TreeNode t = node.left;
			node.left = t.right;
			if(node.left != null)
				node.left.parent = node;
			t.right = node;
			if(t.right != null)
				t.right.parent = t;
			t.parent = node.parent;
			AdjustHeight(node);
			AdjustHeight(t);
			node = t;
		}

		/// <summary>
		/// Helper method for rebalancing. Does a left-right rotation.
		/// </summary>
		/// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
		private void RotateLeftRight(ref TreeNode node)
		{
			RotateLeft(ref node.left);
			RotateRight(ref node);
		}

		/// <summary>
		/// Helper method for rebalancing. Does a left rotation.
		/// </summary>
		/// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
		private void RotateLeft(ref TreeNode node)
		{
			TreeNode t = node.right;
			node.right = t.left;
			if(node.right != null)
				node.right.parent = node;
			t.left = node;
			t.parent = node.parent;
			if(t.left != null)
				t.left.parent = t;
			AdjustHeight(node);
			AdjustHeight(t);
			node = t;
		}

		/// <summary>
		/// Helper method for rebalancing. Does a right-left rotation.
		/// </summary>
		/// <param name="node">On entry the unbalanced node. On exit the node in its place.</param>
		private void RotateRightLeft(ref TreeNode node)
		{
			RotateRight(ref node.right);
			RotateLeft(ref node);
		}

		/// <summary>
		/// Recursive insertion of a node, including rebalancing.
		/// </summary>
		/// <param name="newN">The new node.</param>
		/// <param name="curN">The insertion location.</param>
		/// <returns>Whether the new node was passed to the left or the right. -1 is left, +1 right. 0 means this
		/// node has the same key as the new one.</returns>
		private int InternalAdd(TreeNode newN, ref TreeNode curN)
		{
			int comp = newN.DataComp.CompareTo(curN.data);
			if(comp < 0)
			{
				if(curN.left == null)
				{
					curN.left = newN;
					newN.parent = curN;
					++count;
				}
				else
				{
					int subcomp = InternalAdd(newN, ref curN.left);
					if(curN.right == null || curN.left.height - curN.right.height == 2)
					{
						if(subcomp < 0)
						{
							RotateRight(ref curN);
						}
						else
						{
							RotateLeftRight(ref curN);
						}
					}
				}
			}
			else if(comp > 0)
			{
				if(curN.right == null)
				{
					curN.right = newN;
					newN.parent = curN;
					++count;
				}
				else
				{
					int subcomp = InternalAdd(newN, ref curN.right);
					if(curN.left == null || curN.right.height - curN.left.height == 2)
					{
						if(subcomp > 0)
						{
							RotateLeft(ref curN);
						}
						else
						{
							RotateRightLeft(ref curN);
						}
					}
				}
			}
			else
			{
				return 0;
			}
			AdjustHeight(curN);
			return comp;
		}

		/// <summary>
		/// Finds the node that contains value.
		/// </summary>
		/// <param name="value">The value of the node to be found.</param>
		/// <returns>The node, or null.</returns>
		private TreeNode FindNode(object value)
		{
			TreeNode n = root;
			while(n != null)
			{
				int comp = n.DataComp.CompareTo(value);
				if(comp == 0)
				{
					break;
				}
				else if(comp < 0)
				{
					n = n.right;
				}
				else
				{
					n = n.left;
				}
			}
			return n;
		}

		/// <summary>
		/// Finds the balance of a node. The balance is the difference between
		/// the left and the right subheights.
		/// </summary>
		/// <param name="n">The node.</param>
		/// <returns>The balance. Positive means the right tree is heavier.</returns>
		private int Balance(TreeNode n)
		{
			int lh = n.left != null ? n.left.height : -1;
			int rh = n.right != null ? n.right.height : -1;
			return rh - lh;
		}

		/// <summary>
		/// Re-establishes the tree balance after a deletion.
		/// </summary>
		/// <param name="n">The current node to rebalance.</param>
		private void Rebalance(ref TreeNode n)
		{
			int bal = Balance(n);
			if(bal <= -2)
			{
				// Unbalanced to the left.
				int subbal = Balance(n.left);
				if(subbal < 0)
				{
					// Subtree leans left
					RotateRight(ref n);
				}
				else
				{
					// Subtree leans right
					RotateLeftRight(ref n);
				}
			}
			else if(bal >= 2)
			{
				// Unbalanced to the right.
				int subbal = Balance(n.right);
				if(subbal < 0)
				{
					// Subtree leans left
					RotateRightLeft(ref n);
				}
				else
				{
					// Subtree leans right
					RotateLeft(ref n);
				}
			}
			// Balance parent.
			if(n.parent != null)
				Rebalance(ref n.parent);
			else
				root = n;
		}

		#region ICollection Members

		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}

		public int Count
		{
			get
			{
				return count;
			}
		}

		public void CopyTo(Array array, int index)
		{
			throw new NotImplementedException();
		}

		public object SyncRoot
		{
			get
			{
				throw new NotImplementedException();
			}
		}

		#endregion

		#region IEnumerable Members

		public IEnumerator GetEnumerator()
		{
			return new TreeEnumerator(this);
		}

		#endregion

		internal object Get(object value)
		{
			TreeNode n = FindNode(value);
			if(n != null)
				return n.data;
			return null;
		}

		public void Remove(object value)
		{
			TreeNode n = FindNode(value);
			if(n != null)
			{
				--count;
				TreeNode r;
				if(n.left == null || n.right == null)
				{
					r = n;
				}
				else
				{
					r = Next(n);
					n.data = r.data;
				}
				n = (r.left == null) ? r.right : r.left;
				if(n != null)
					n.parent = r.parent;
				if(r.parent == null)
				{
					root = n;
				}
				else
				{
					if(r == r.parent.left)
						r.parent.left = n;
					else
						r.parent.right = n;
				}
				// Node unlinked, GC will collect it.
				// Now rebalance the tree.
				// r.parent might be null, but then the tree contained only one or two elements.
				// Which means it doesn't need rebalancing anyway.
				if(r.parent != null)
				{
					Rebalance(ref r.parent);
				}
			}
		}

		public bool Contains(object value)
		{
			return FindNode(value) != null;
		}

		public void Clear()
		{
			// This should suffice.
			root = null;
		}

		public void Add(object value)
		{
			TreeNode n = new TreeNode(value);
			if(root == null)
			{
				root = n;
				++count;
			}
			else
			{
				InternalAdd(n, ref root);
			}
		}
	}

	/// <summary>
	/// A set is a collection that is optimized for fast "Contains" calls.
	/// </summary>
	public interface ISet : ICollection
	{
		/// <summary>
		/// Adds an object to the set.
		/// </summary>
		/// <param name="value">The value to add.</param>
		public void Add(object value);

		/// <summary>
		/// Removes an object from the set. Does nothing if
		/// the value isn't in the set.
		/// </summary>
		/// <param name="value">The value to remove.</param>
		public void Remove(object value);

		/// <summary>
		/// Tests if an object is in the set.
		/// </summary>
		/// <param name="value">The value to look for.</param>
		/// <returns>True if the object is in the set.</returns>
		public bool Contains(object value);

		/// <summary>
		/// Completly clears the set.
		/// </summary>
		public void Clear();
	}

	/// <summary>
	/// An implementation of ISet based on a binary tree.
	/// Contains performance is O(log n).
	/// </summary>
	public class TreeSet : ISet
	{
		BinaryTree impl = new BinaryTree();
		IComparer comp;

		internal class DataWrapper : IComparable
		{
			internal IComparer comparer;
			internal object data;

			public DataWrapper(object value, IComparer comp)
			{
				data = value;
				comparer = comp;
				if(comparer == null)
					comparer = Comparer.Default;
			}

			#region IComparable Members

			public int CompareTo(object obj)
			{
				if(!(obj is DataWrapper))
					throw new ArgumentException("Not a DataWrapper", "obj");
				DataWrapper wrap = (DataWrapper)obj;
				return comparer.Compare(data, wrap.data);
			}

			#endregion
		}

		internal class EnumWrapper : IEnumerator
		{
			private IEnumerator inner;

			public EnumWrapper(IEnumerator e)
			{
				inner = e;
			}

			#region IEnumerator Members

			public void Reset()
			{
				inner.Reset();
			}

			public object Current
			{
				get
				{
					DataWrapper wrap = (DataWrapper)inner.Current;
					return wrap.data;
				}
			}

			public bool MoveNext()
			{
				return inner.MoveNext();
			}

			#endregion

		}

		/// <summary>
		/// Creates a new TreeSet.
		/// </summary>
		public TreeSet()
		{
			comp = null;
		}

		/// <summary>
		/// Creates a new TreeSet using a custom comparer.
		/// </summary>
		/// <param name="c">The comparer to use for sorting.</param>
		public TreeSet(IComparer c)
		{
			comp = c;
		}

		#region ISet Members

		public void Add(object value)
		{
			impl.Add(new DataWrapper(value, comp));
		}

		public void Remove(object value)
		{
			impl.Remove(new DataWrapper(value, comp));
		}

		public bool Contains(object value)
		{
			return impl.Contains(new DataWrapper(value, comp));
		}

		public void Clear()
		{
			impl.Clear();
		}

		#endregion

		#region ICollection Members

		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}

		public int Count
		{
			get
			{
				return impl.Count;
			}
		}

		public void CopyTo(Array array, int index)
		{
			throw new NotImplementedException();
		}

		public object SyncRoot
		{
			get
			{
				throw new NotImplementedException();
			}
		}

		#endregion

		#region IEnumerable Members

		public IEnumerator GetEnumerator()
		{
			return new EnumWrapper(impl.GetEnumerator());
		}

		#endregion
	}

	/// <summary>
	/// Binary-Tree-based dictionary.
	/// </summary>
	public class TreeDictionary : IDictionary
	{
		BinaryTree impl = new BinaryTree();
		IComparer comp;

		public TreeDictionary()
		{
			comp = Comparer.Default;
		}

		public TreeDictionary(IComparer c)
		{
			comp = c;
		}

		public class KeyValuePair : DictionaryEntry, IComparable
		{
			internal object key;
			internal object value;
			internal IComparer comp;

			public KeyValuePair(object k, object v)
			{
				comp = Comparer.Default;
				key = k;
				value = v;
			}

			public KeyValuePair(object k, object v, IComparer comp)
			{
				this.comp = comp;
				key = k;
				value = v;
			}

			public object Key
			{
				get
				{
					return key;
				}
				set
				{
					throw new NotSupportedException("Keys cannot be modified.");
				}
			}

			public object Value
			{
				get
				{
					return value;
				}
				set
				{
					this.value = value;
				}
			}

			#region IComparable Members

			public int CompareTo(object obj)
			{
				if(!(obj is KeyValuePair))
					throw new ArgumentException("not a KeyValuePair", "obj");

				KeyValuePair kvp = (KeyValuePair)obj;
				return comp.Compare(key, kvp.key);
			}

			#endregion

		}

		internal class DictEnum : IDictionaryEnumerator
		{
			internal IEnumerator inner;

			public DictEnum(IEnumerator e)
			{
				inner = e;
			}

			#region IDictionaryEnumerator Members

			internal KeyValuePair Get()
			{
				return (KeyValuePair)inner.Current;
			}

			public object Key
			{
				get
				{
					return Get().Key;
				}
			}

			public object Value
			{
				get
				{
					return Get().Value;
				}
			}

			public DictionaryEntry Entry
			{
				get
				{
					return Get();
				}
			}

			#endregion

			#region IEnumerator Members

			public void Reset()
			{
				inner.Reset();
			}

			public object Current
			{
				get
				{
					return Entry;
				}
			}

			public bool MoveNext()
			{
				return inner.MoveNext();
			}

			#endregion

		}

		#region IDictionary Members

		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}

		public IDictionaryEnumerator GetEnumerator()
		{
			return new DictEnum(impl.GetEnumerator());
		}

		public object this[object key]
		{
			get
			{
				object o = impl.Get(new KeyValuePair(key, null, comp));
				if(o == null)
					return null;
				return ((KeyValuePair)o).Value;
			}
			set
			{
				object o = impl.Get(new KeyValuePair(key, null, comp));
				if(o == null)
				{
					impl.Add(new KeyValuePair(key, value, comp));
				}
				else
				{
					((KeyValuePair)o).Value = value;
				}
			}
		}

		public void Remove(object key)
		{
			impl.Remove(new KeyValuePair(key, null, comp));
		}

		public bool Contains(object key)
		{
			return impl.Contains(new KeyValuePair(key, null, comp));
		}

		public void Clear()
		{
			impl.Clear();
		}

		public ICollection Values
		{
			get
			{
				throw new NotImplementedException();
			}
		}

		public void Add(object key, object value)
		{
			impl.Add(new KeyValuePair(key, value, comp));
		}

		public ICollection Keys
		{
			get
			{
				throw new NotImplementedException();
			}
		}

		public bool IsFixedSize
		{
			get
			{
				return false;
			}
		}

		#endregion

		#region ICollection Members

		public bool IsSynchronized
		{
			get
			{
				return false;
			}
		}

		public int Count
		{
			get
			{
				return impl.Count;
			}
		}

		public void CopyTo(Array array, int index)
		{
			throw new NotImplementedException();
		}

		public object SyncRoot
		{
			get
			{
				throw new NotImplementedException();
			}
		}

		#endregion

		#region IEnumerable Members

		IEnumerator System.Collections.IEnumerable.GetEnumerator()
		{
			return new DictEnum(impl.GetEnumerator());
		}

		#endregion

	}

}