Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement