inscrutable

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;
        }
    }
}