Treaps in C#

///<summary>
///   An implementation of a treap data structure.
///
///   A treap is based upon a randomized binary Tree whose nodes have keys and
///   which also have priorities associated with them in a heap - hence the
///   name (tre)e h(eap).
///
///   A Tree is a `heap' if each node has a priority such that the priority of
///   each child is greater than the priority of its parent (trees that are heaps
///   can also called "priority queues", and are the basis of a heap sort).
///
///   The priorities are a means to randomize the Tree. Randomized trees are better
///   balanced (essentially meaning less depth) so that seach time is minimized.
///
///   Treaps were first introduced by Seidel and Aragon in <blockquote>
///   R. Seidel and C. R. Aragon. Randomized Binary Search Trees.
///   <em>Algorithmica</em>, 16(4/5):464-497, 1996. </blockquote>
///
///   Most methods run in O(log n) randomized time, where n is the number of keys in
///   the treap. The exceptions are clone() and toString() that run in time
///   proportional to the intCount of their output.
///
///   This code was was ultimately based upon the Java treap implementation by Stefan Nilsson
///   published in Dr. Dobb's Journal, pp. 40-44, Vol. 267, July 1997
///</summary>

using System.Collections;
using System.Text;
using System;

namespace TreapCS
{
	public class Treap : object
	{
		
		// random priority to keep the treap balanced
		private Random      rndPriority;
		// the number of key-and-value pairs contained in the treap
		private int         intCount;
		// used for quick comparisons
		private int         intHashCode;
		// identIfies the owner of the treap
		private string      strIdentIfier;
		// the treap
		private TreapNode   treapTree;
		private bool        boolKeyFound;
		private object      prevData;
		
		public Treap() 
        {
			rndPriority = new Random();
			intHashCode = rndPriority.Next();
		}
		
		public Treap(string strIdentIfier) 
        {
			rndPriority         = new Random();
			intHashCode         = rndPriority.Next();
			this.strIdentIfier  = strIdentIfier;
		}
		
		///<summary>
		/// Add
		/// args: ByVal key As IComparable, ByVal data As Object
		/// key is object that implements IComparable interface
		///</summary>
		public void Add (IComparable key, object data)
		{
			if(key == null || data == null)
				throw(new TreapException("Treap key and data must not be Nothing"));
			
			// create New node
			TreapNode node = new TreapNode();
			if(node == null)
				throw(new TreapException("Unable to create Treap Node"));
			
			node.Key    = key;
			node.Data   = data;

			// generate random priority
			node.Priority   = rndPriority.Next();
		
			// insert node into treapTree
            boolKeyFound    = false;
            treapTree = InsertNode(node, treapTree);
			if(boolKeyFound)
				throw(new TreapException("A Node with the same key already exists"));
			else
				intCount = intCount + 1;
		}
		
		///<summary>
		/// InsertNode
		/// inserts a node into the tree - note recursive method
		/// this method rebalances the tree using the priorities
		///
		/// Note: The lower the number, the higher the priority
		///<summary>
		private TreapNode InsertNode(TreapNode node, TreapNode tree)
		{
			if(tree == null)
				return node;
			
			int result = node.Key.CompareTo(tree.Key);
			
			if(result < 0)
			{
				tree.Left = InsertNode(node, tree.Left);
				if(tree.Left.Priority < tree.Priority)
					tree = tree.RotateRight();
			}
			else
            if(result > 0)
			{
				tree.Right = InsertNode(node, tree.Right);
				if(tree.Right.Priority < tree.Priority)
					tree = tree.RotateLeft();
			}
			else
			{
				prevData    = tree.Data;
				tree.Data   = node.Data;
			}
			
			return tree;
		}
		
		///<summary>
		/// GetData
		/// Gets the data associated with the specified key
		///<summary>
		public object GetData(IComparable key)
		{
			TreapNode treeNode = treapTree;
			int result;
			
			while(treeNode != null)
			{
				result = key.CompareTo(treeNode.Key);
				if(result == 0)
					return treeNode.Data;
				if(result < 0)
					treeNode = treeNode.Left;
				else
					treeNode = treeNode.Right;
			}
			
			throw(new TreapException("Treap key was not found"));
		}
		///<summary>
		/// GetMinKey
		/// Returns the minimum key value
		///<summary>
		public IComparable GetMinKey()
		{
			TreapNode treeNode = treapTree;
			
			if(treeNode == null)
				throw(new TreapException("Treap is empty"));
			
			while(treeNode.Left != null)
				treeNode = treeNode.Left;
			
			return treeNode.Key;
			
		}
		///<summary>
		/// GetMaxKey
		/// Returns the maximum key value
		///<summary>
		public IComparable GetMaxKey()
		{
			TreapNode treeNode = treapTree;
			
			if(treeNode == null)
				throw(new TreapException("Treap is empty"));
			
			while(treeNode.Right != null)
				treeNode = treeNode.Right;
			
			return treeNode.Key;
			
		}
		///<summary>
		/// GetMinValue
		/// Returns the object having the minimum key value
		///<summary>
		public object GetMinValue()
		{
			return GetData(GetMinKey());
		}
		///<summary>
		/// GetMaxValue
		/// Returns the object having the maximum key
		///<summary>
		public object GetMaxValue()
		{
			return GetData(GetMaxKey());
		}
		///<summary>
		/// GetEnumerator
		///<summary>
		public TreapEnumerator GetEnumerator()
		{
			return Elements(true);
		}
		///<summary>
		/// Keys
		/// If ascending is True, the keys will be returned in ascending order, else
		/// the keys will be returned in descending order.
		///<summary>
		public TreapEnumerator Keys()
		{
			return Keys(true);
		}
		public TreapEnumerator Keys(bool ascending)
		{
			return new TreapEnumerator(treapTree, true, ascending);
		}
		///<summary>
		/// Values
		/// .NET compatibility
		///<summary>
		public TreapEnumerator Values()
		{
			return Elements(true);
		}
		///<summary>
		/// Elements
		/// Returns an enumeration of the data objects.
		/// If ascending is true, the objects will be returned in ascending order,
		/// else the objects will be returned in descending order.
		///<summary>
		public TreapEnumerator Elements()
		{
			return Elements(true);
		}
		public TreapEnumerator Elements(bool ascending)
		{
			return new TreapEnumerator(treapTree, false, ascending);
		}
		///<summary>
		/// IsEmpty
		///<summary>
		public bool IsEmpty()
		{
			return (treapTree == null);
		}
		///<summary>
		/// Remove
		/// removes the key and Object
		///<summary>
		public void Remove (IComparable key)
		{
            if(key == null)
                throw(new TreapException("Treap key is null"));
            
            boolKeyFound = false;
			
			treapTree  = Delete(key, treapTree);
			
			if(boolKeyFound)
				intCount = intCount - 1;
		}
		///<summary>
		/// RemoveMin
		/// removes the node with the minimum key
		///<summary>
		public object RemoveMin()
		{
            if(treapTree == null)
                throw(new TreapException("Treap is null"));
            
            // start at top
			TreapNode treeNode = treapTree;
			TreapNode prevTreapNode;
			
			if(treeNode.Left == null)
				// remove top node by replacing with right
				treapTree = treeNode.Right;
			else
			{
				do
				{
					// find the minimum node
					prevTreapNode   = treeNode;
					treeNode        = treeNode.Left;
				} while(treeNode.Left != null);
				// remove left node by replacing with right node
				prevTreapNode.Left  = treeNode.Right;
			}
			
			intCount = intCount - 1;
			
			return treeNode.Data;
			
		}
		///<summary>
		/// RemoveMax
		/// removes the node with the maximum key
		///<summary>
		public object RemoveMax()
		{
            if(treapTree == null)
                throw(new TreapException("Treap is null"));
            
            // start at top
			TreapNode treeNode = treapTree;
			TreapNode prevTreapNode;
			
			if(treeNode.Right == null)
				// remove top node by replacing with left
				treapTree = treeNode.Left;
			else
			{
				do
				{
					// find the maximum node
					prevTreapNode = treeNode;
					treeNode = treeNode.Right;
				} while(treeNode.Right != null);
				// remove right node by replacing with left node
				prevTreapNode.Right = treeNode.Left;
			}
			
			intCount = intCount - 1;
			
			return treeNode.Data;
		}
		///<summary>
		/// Clear
		///<summary>
		public void Clear ()
		{
			treapTree   = null;
			intCount    = 0;
		}
		///<summary>
		/// Size
		///<summary>
		public int Size()
		{
			// number of keys
			return intCount;
		}
		///<summary>
		/// Delete
		/// deletes a node - note recursive function
		/// Deletes works by "bubbling down" the node until it is a leaf, and then
		/// pruning it off the tree
		///<summary>
		private TreapNode Delete(IComparable key, TreapNode tNode)
		{
			if(tNode == null)
				return null;
			
			int result = key.CompareTo(tNode.Key);
			
			if(result < 0)
				tNode.Left = Delete(key, tNode.Left);
			else
            if(result > 0)
                tNode.Right = Delete(key, tNode.Right);
			else
			{
				boolKeyFound    = true;
				prevData        = tNode.Data;
				tNode           = tNode.DeleteRoot();
			}
			
			return tNode;
		}
		///<summary>
		/// Equals
		///<summary>
		public override bool Equals(object obj)
		{
			if(obj == null)
				return false;
			
			if(!(obj is Treap ))
				return false;
			
			if(this == obj)
				return true;
			
			return (ToString().Equals(((Treap)(obj)).ToString()));
			
		}
		///<summary>
		/// HashCode
		///<summary>
		public override int GetHashCode()
		{
			return intHashCode;
		}
		///<summary>
		/// ToString
		///<summary>
		public override string ToString()
		{
			return strIdentIfier.ToString();
		}
	}
}