using System;
using System.Collections;
using System.Collections.Generic;
namespace Treap
{
public class Treap<TKey, TValue> : IDictionary<TKey, TValue> where TKey : IComparable<TKey>
{
private bool m_NodeIsEmpty = true;
KeyValuePair<TKey, TValue> m_NodeValue;
private int m_NodePriority;
private Treap<TKey, TValue> m_LeftNode;
private Treap<TKey, TValue> m_RightNode;
public int Count
{
get
{
if (m_NodeIsEmpty)
return 0;
int retVal = 1;
if (m_LeftNode != null)
retVal += m_LeftNode.Count;
if (m_RightNode != null)
retVal += m_RightNode.Count;
return retVal;
}
}
public bool IsReadOnly { get { return false; } }
public ICollection<TKey> Keys
{
get
{
List<TKey> retval = new List<TKey>();
if (!m_NodeIsEmpty)
{
if (m_LeftNode != null)
retval.AddRange(m_LeftNode.Keys);
retval.Add(m_NodeValue.Key);
if (m_RightNode != null)
retval.AddRange(m_RightNode.Keys);
}
return retval;
}
}
public ICollection<TValue> Values
{
get
{
List<TValue> retval = new List<TValue>();
if (!m_NodeIsEmpty)
{
if (m_LeftNode != null)
retval.AddRange(m_LeftNode.Values);
retval.Add(m_NodeValue.Value);
if (m_RightNode != null)
retval.AddRange(m_RightNode.Values);
}
return retval;
}
}
public Treap()
{
m_NodePriority = new Random().Next();
}
private Treap(TKey key, TValue value)
: this()
{
m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
m_NodeIsEmpty = false;
}
private Treap(Treap<TKey, TValue> initializer)
{
m_NodeIsEmpty = initializer.m_NodeIsEmpty;
m_NodeValue = initializer.m_NodeValue;
m_NodePriority = initializer.m_NodePriority;
m_LeftNode = initializer.m_LeftNode;
m_RightNode = initializer.m_RightNode;
}
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
if(m_NodeIsEmpty)
yield break;
if (m_LeftNode != null)
{
foreach (KeyValuePair<TKey, TValue> item in m_LeftNode)
yield return item;
}
yield return m_NodeValue;
if (m_RightNode != null)
{
foreach (KeyValuePair<TKey, TValue> item in m_RightNode)
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
public bool Contains(KeyValuePair<TKey, TValue> item)
{
if (m_NodeIsEmpty)
return false;
if(m_NodeValue.Equals(item))
return true;
int compareResult = item.Key.CompareTo(m_NodeValue.Key);
if (m_LeftNode != null && compareResult < 0)
return m_LeftNode.Contains(item);
if (m_RightNode != null && compareResult > 0)
return m_RightNode.Contains(item);
return false;
}
public bool ContainsKey(TKey key)
{
if (m_NodeIsEmpty)
return false;
int compareResult = key.CompareTo(m_NodeValue.Key);
if (m_LeftNode != null && compareResult < 0)
return m_LeftNode.ContainsKey(key);
if (m_RightNode != null && compareResult > 0)
return m_RightNode.ContainsKey(key);
if (compareResult == 0)
return true;
return false;
}
public bool TryGetValue(TKey key, out TValue value)
{
value = default(TValue);
if(m_NodeIsEmpty)
return false;
int compareResult = key.CompareTo(m_NodeValue.Key);
if (compareResult < 0)
{
if(m_LeftNode == null)
return false;
return m_LeftNode.TryGetValue(key, out value);
}
if (compareResult > 0)
{
if(m_RightNode == null)
return false;
return m_RightNode.TryGetValue(key, out value);
}
value = m_NodeValue.Value;
return true;
}
public TValue this[TKey key]
{
get
{
TValue retval;
bool tryGetSuccess = TryGetValue(key, out retval);
if (tryGetSuccess)
return retval;
throw new KeyNotFoundException();
}
set
{
if (m_NodeIsEmpty)
{
m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
m_NodeIsEmpty = false;
}
else
{
int compareResult = key.CompareTo(m_NodeValue.Key);
if (compareResult < 0)
{
if (m_LeftNode == null)
Add(key, value);
else
m_LeftNode[key] = value;
}
else if (compareResult > 0)
{
if (m_RightNode == null)
Add(key, value);
else
m_RightNode[key] = value;
}
else // compareResult == 0
{
m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
}
}
}
}
public void Add(KeyValuePair<TKey, TValue> item)
{
Add(item.Key, item.Value);
}
public void Add(TKey key, TValue value)
{
if(m_NodeIsEmpty)
{
m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
m_NodeIsEmpty = false;
return;
}
int compareResult = key.CompareTo(m_NodeValue.Key);
if (compareResult < 0)
{
if (m_LeftNode == null)
m_LeftNode = new Treap<TKey, TValue>(key, value);
else
m_LeftNode.Add(key, value);
if (m_LeftNode.m_NodePriority > m_NodePriority)
RotateRight();
}
else if (compareResult > 0)
{
if (m_RightNode == null)
m_RightNode = new Treap<TKey, TValue>(key, value);
else
m_RightNode.Add(key, value);
if (m_RightNode.m_NodePriority > m_NodePriority)
RotateLeft();
}
else // compareResult == 0
throw new ArgumentException("That key is already stored in the treap", "key");
}
private void Add(Treap<TKey, TValue> item)
{
if(item.m_NodePriority>m_NodePriority)
throw new ArgumentException("Can not add a higher priority sub-tree to a lower priority node", "item");
Treap<TKey, TValue> orphanNode;
int compareResult = item.m_NodeValue.Key.CompareTo(m_NodeValue.Key);
if (compareResult < 0)
{
if (m_LeftNode == null)
m_LeftNode = item;
else if (m_LeftNode.m_NodePriority >= item.m_NodePriority)
m_LeftNode.Add(item);
else
{
orphanNode = m_LeftNode;
m_LeftNode = item;
m_LeftNode.Add(orphanNode);
}
}
else if (compareResult > 0)
{
if (m_RightNode == null)
m_RightNode = item;
else if (m_RightNode.m_NodePriority >= item.m_NodePriority)
m_RightNode.Add(item);
else
{
orphanNode = m_RightNode;
m_RightNode = item;
m_RightNode.Add(orphanNode);
}
}
else // compareResult == 0
throw new ArgumentException("That key is already stored in the treap", "item");
}
public bool Remove(KeyValuePair<TKey, TValue> item)
{
//Need the extra contains lookup to handle the case where TValue doesn't match
return Contains(item) && Remove(item.Key);
}
public bool Remove(TKey key)
{
if (m_NodeIsEmpty)
return false;
int compareResult = key.CompareTo(m_NodeValue.Key);
if (compareResult < 0)
{
if (m_LeftNode == null)
return false;
bool removeResult = m_LeftNode.Remove(key);
if (m_LeftNode.m_NodeIsEmpty)
m_LeftNode = null;
return removeResult;
}
if (compareResult > 0)
{
if (m_RightNode == null)
return false;
bool removeResult = m_RightNode.Remove(key);
if (m_RightNode.m_NodeIsEmpty)
m_RightNode = null;
return removeResult;
}
//We're removing this node. With two child node, the higher priority one will
//be moved up to take this nodes place. The lower priority node will be orphaned
//and will need to find a new home.
Treap<TKey, TValue> orphanNode = null;
if (m_LeftNode != null && m_RightNode != null)
orphanNode = m_LeftNode.m_NodePriority >= m_RightNode.m_NodePriority ? m_RightNode : m_LeftNode;
if (m_LeftNode != null && (m_RightNode == null || m_LeftNode.m_NodePriority >= m_RightNode.m_NodePriority))
{
//move up the left child
m_NodeValue = m_LeftNode.m_NodeValue;
m_NodePriority = m_LeftNode.m_NodePriority;
m_RightNode = m_LeftNode.m_RightNode;
m_LeftNode = m_LeftNode.m_LeftNode;
}
else if (m_RightNode != null && (m_LeftNode == null || m_RightNode.m_NodePriority > m_LeftNode.m_NodePriority))
{
//move up the right child
m_NodeValue = m_RightNode.m_NodeValue;
m_NodePriority = m_RightNode.m_NodePriority;
m_LeftNode = m_RightNode.m_LeftNode;
m_RightNode = m_RightNode.m_RightNode;
}
else //m_LeftNode == null && m_RightNode == null
{
//this node and everything below it is gone, we're an empty node now
m_NodeValue = default(KeyValuePair<TKey, TValue>);
m_NodeIsEmpty = true;
}
if(orphanNode != null)
Add(orphanNode);
return true;
}
public void Clear()
{
m_NodeValue = default(KeyValuePair<TKey, TValue>);
m_LeftNode = null;
m_RightNode = null;
m_NodeIsEmpty = true;
}
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
{
int currentStartIndex = arrayIndex;
if(m_NodeIsEmpty)
return;
if(m_LeftNode != null)
{
m_LeftNode.CopyTo(array, currentStartIndex);
currentStartIndex += m_LeftNode.Count;
}
array[currentStartIndex] = m_NodeValue;
currentStartIndex++;
if (m_RightNode != null)
{
m_RightNode.CopyTo(array, currentStartIndex);
}
}
private void RotateRight()
{
//hold on to the current node in a temp object
Treap<TKey, TValue> tempNode = new Treap<TKey, TValue>(this);
//copy in the data that will make up the new root value;
m_NodeValue = m_LeftNode.m_NodeValue;
m_NodePriority = m_LeftNode.m_NodePriority;
//rearrange the linkages
m_LeftNode = tempNode.m_LeftNode.m_LeftNode;
m_RightNode = new Treap<TKey, TValue>(tempNode);
m_RightNode.m_LeftNode = tempNode.m_LeftNode.m_RightNode;
}
private void RotateLeft()
{
//hold on to the current node in a temp object
Treap<TKey, TValue> tempNode = new Treap<TKey, TValue>(this);
//copy in the data that will make up the new root value;
m_NodeValue = m_RightNode.m_NodeValue;
m_NodePriority = m_RightNode.m_NodePriority;
//rearrange the linkages
m_RightNode = tempNode.m_RightNode.m_RightNode;
m_LeftNode = new Treap<TKey, TValue>(tempNode);
m_LeftNode.m_RightNode = tempNode.m_RightNode.m_LeftNode;
}
internal bool IsValid()
{
if (m_LeftNode != null)
{
if(m_LeftNode.m_NodePriority > m_NodePriority)
return false;
if (m_LeftNode.m_NodeValue.Key.CompareTo(m_NodeValue.Key) >= 0)
return false;
if (!m_LeftNode.IsValid())
return false;
}
if (m_RightNode != null)
{
if (m_RightNode.m_NodePriority > m_NodePriority)
return false;
if (m_RightNode.m_NodeValue.Key.CompareTo(m_NodeValue.Key) <= 0)
return false;
if (!m_RightNode.IsValid())
return false;
}
return true;
}
}
}