Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

inscrutable

By: a guest on Jul 15th, 2009  |  syntax: C#  |  size: 14.62 KB  |  views: 70  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4.  
  5. namespace Treap
  6. {
  7.     public class Treap<TKey, TValue> : IDictionary<TKey, TValue> where TKey : IComparable<TKey>
  8.     {
  9.         private bool m_NodeIsEmpty = true;
  10.         KeyValuePair<TKey, TValue> m_NodeValue;
  11.         private int m_NodePriority;
  12.         private Treap<TKey, TValue> m_LeftNode;
  13.         private Treap<TKey, TValue> m_RightNode;
  14.  
  15.         public int Count
  16.         {
  17.             get
  18.             {
  19.                 if (m_NodeIsEmpty)
  20.                     return 0;
  21.  
  22.                 int retVal = 1;
  23.                 if (m_LeftNode != null)
  24.                     retVal += m_LeftNode.Count;
  25.                 if (m_RightNode != null)
  26.                     retVal += m_RightNode.Count;
  27.                 return retVal;
  28.             }
  29.         }
  30.  
  31.         public bool IsReadOnly { get { return false; } }
  32.  
  33.         public ICollection<TKey> Keys
  34.         {
  35.             get
  36.             {
  37.                 List<TKey> retval = new List<TKey>();
  38.  
  39.                 if (!m_NodeIsEmpty)
  40.                 {
  41.                     if (m_LeftNode != null)
  42.                         retval.AddRange(m_LeftNode.Keys);
  43.                     retval.Add(m_NodeValue.Key);
  44.                     if (m_RightNode != null)
  45.                         retval.AddRange(m_RightNode.Keys);
  46.                 }
  47.  
  48.                 return retval;
  49.             }
  50.         }
  51.  
  52.         public ICollection<TValue> Values
  53.         {
  54.             get
  55.             {
  56.                 List<TValue> retval = new List<TValue>();
  57.  
  58.                 if (!m_NodeIsEmpty)
  59.                 {
  60.                     if (m_LeftNode != null)
  61.                         retval.AddRange(m_LeftNode.Values);
  62.                     retval.Add(m_NodeValue.Value);
  63.                     if (m_RightNode != null)
  64.                         retval.AddRange(m_RightNode.Values);
  65.                 }
  66.  
  67.                 return retval;
  68.             }
  69.         }
  70.  
  71.         public Treap()
  72.         {
  73.             m_NodePriority = new Random().Next();
  74.         }
  75.  
  76.         private Treap(TKey key, TValue value)
  77.             : this()
  78.         {
  79.             m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
  80.             m_NodeIsEmpty = false;
  81.         }
  82.  
  83.         private Treap(Treap<TKey, TValue> initializer)
  84.         {
  85.             m_NodeIsEmpty = initializer.m_NodeIsEmpty;
  86.             m_NodeValue = initializer.m_NodeValue;
  87.             m_NodePriority = initializer.m_NodePriority;
  88.             m_LeftNode = initializer.m_LeftNode;
  89.             m_RightNode = initializer.m_RightNode;
  90.         }
  91.  
  92.         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
  93.         {
  94.             if(m_NodeIsEmpty)
  95.                 yield break;
  96.  
  97.             if (m_LeftNode != null)
  98.             {
  99.                 foreach (KeyValuePair<TKey, TValue> item in m_LeftNode)
  100.                     yield return item;
  101.             }
  102.  
  103.             yield return m_NodeValue;
  104.  
  105.             if (m_RightNode != null)
  106.             {
  107.                 foreach (KeyValuePair<TKey, TValue> item in m_RightNode)
  108.                     yield return item;
  109.             }
  110.         }
  111.  
  112.         IEnumerator IEnumerable.GetEnumerator()
  113.         {
  114.             return GetEnumerator();
  115.         }
  116.  
  117.         public bool Contains(KeyValuePair<TKey, TValue> item)
  118.         {
  119.             if (m_NodeIsEmpty)
  120.                 return false;
  121.  
  122.             if(m_NodeValue.Equals(item))
  123.                 return true;
  124.  
  125.             int compareResult = item.Key.CompareTo(m_NodeValue.Key);
  126.             if (m_LeftNode != null && compareResult < 0)
  127.                 return m_LeftNode.Contains(item);
  128.             if (m_RightNode != null && compareResult > 0)
  129.                 return m_RightNode.Contains(item);
  130.             return false;
  131.         }
  132.  
  133.         public bool ContainsKey(TKey key)
  134.         {
  135.             if (m_NodeIsEmpty)
  136.                 return false;
  137.  
  138.             int compareResult = key.CompareTo(m_NodeValue.Key);
  139.             if (m_LeftNode != null && compareResult < 0)
  140.                 return m_LeftNode.ContainsKey(key);
  141.             if (m_RightNode != null && compareResult > 0)
  142.                 return m_RightNode.ContainsKey(key);
  143.             if (compareResult == 0)
  144.                 return true;
  145.             return false;
  146.         }
  147.  
  148.         public bool TryGetValue(TKey key, out TValue value)
  149.         {
  150.             value = default(TValue);
  151.  
  152.             if(m_NodeIsEmpty)
  153.                 return false;
  154.  
  155.             int compareResult = key.CompareTo(m_NodeValue.Key);
  156.             if (compareResult < 0)
  157.             {
  158.                 if(m_LeftNode == null)
  159.                     return false;
  160.                 return m_LeftNode.TryGetValue(key, out value);
  161.             }
  162.             if (compareResult > 0)
  163.             {
  164.                 if(m_RightNode == null)
  165.                     return false;
  166.                 return m_RightNode.TryGetValue(key, out value);
  167.             }
  168.  
  169.             value = m_NodeValue.Value;
  170.             return true;
  171.         }
  172.  
  173.         public TValue this[TKey key]
  174.         {
  175.             get
  176.             {
  177.                 TValue retval;
  178.                 bool tryGetSuccess = TryGetValue(key, out retval);
  179.                 if (tryGetSuccess)
  180.                     return retval;
  181.                 throw new KeyNotFoundException();
  182.             }
  183.             set
  184.             {
  185.                 if (m_NodeIsEmpty)
  186.                 {
  187.                     m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
  188.                     m_NodeIsEmpty = false;
  189.                 }
  190.                 else
  191.                 {
  192.                     int compareResult = key.CompareTo(m_NodeValue.Key);
  193.                     if (compareResult < 0)
  194.                     {
  195.                         if (m_LeftNode == null)
  196.                             Add(key, value);
  197.                         else
  198.                             m_LeftNode[key] = value;
  199.                     }
  200.                     else if (compareResult > 0)
  201.                     {
  202.                         if (m_RightNode == null)
  203.                             Add(key, value);
  204.                         else
  205.                             m_RightNode[key] = value;
  206.                     }
  207.                     else // compareResult == 0
  208.                     {
  209.                         m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
  210.                     }
  211.                 }
  212.             }
  213.         }
  214.  
  215.         public void Add(KeyValuePair<TKey, TValue> item)
  216.         {
  217.             Add(item.Key, item.Value);
  218.         }
  219.  
  220.         public void Add(TKey key, TValue value)
  221.         {
  222.             if(m_NodeIsEmpty)
  223.             {
  224.                 m_NodeValue = new KeyValuePair<TKey, TValue>(key, value);
  225.                 m_NodeIsEmpty = false;
  226.                 return;
  227.             }
  228.  
  229.             int compareResult = key.CompareTo(m_NodeValue.Key);
  230.             if (compareResult < 0)
  231.             {
  232.                 if (m_LeftNode == null)
  233.                     m_LeftNode = new Treap<TKey, TValue>(key, value);
  234.                 else
  235.                     m_LeftNode.Add(key, value);
  236.                 if (m_LeftNode.m_NodePriority > m_NodePriority)
  237.                     RotateRight();
  238.             }
  239.             else if (compareResult > 0)
  240.             {
  241.                 if (m_RightNode == null)
  242.                     m_RightNode = new Treap<TKey, TValue>(key, value);
  243.                 else
  244.                     m_RightNode.Add(key, value);
  245.                 if (m_RightNode.m_NodePriority > m_NodePriority)
  246.                     RotateLeft();
  247.             }
  248.             else // compareResult == 0
  249.                 throw new ArgumentException("That key is already stored in the treap", "key");
  250.         }
  251.  
  252.         private void Add(Treap<TKey, TValue> item)
  253.         {
  254.             if(item.m_NodePriority>m_NodePriority)
  255.                 throw new ArgumentException("Can not add a higher priority sub-tree to a lower priority node", "item");
  256.  
  257.             Treap<TKey, TValue> orphanNode;
  258.             int compareResult = item.m_NodeValue.Key.CompareTo(m_NodeValue.Key);
  259.             if (compareResult < 0)
  260.             {
  261.                 if (m_LeftNode == null)
  262.                     m_LeftNode = item;
  263.                 else if (m_LeftNode.m_NodePriority >= item.m_NodePriority)
  264.                     m_LeftNode.Add(item);
  265.                 else
  266.                 {
  267.                     orphanNode = m_LeftNode;
  268.                     m_LeftNode = item;
  269.                     m_LeftNode.Add(orphanNode);
  270.                 }
  271.             }
  272.             else if (compareResult > 0)
  273.             {
  274.                 if (m_RightNode == null)
  275.                     m_RightNode = item;
  276.                 else if (m_RightNode.m_NodePriority >= item.m_NodePriority)
  277.                     m_RightNode.Add(item);
  278.                 else
  279.                 {
  280.                     orphanNode = m_RightNode;
  281.                     m_RightNode = item;
  282.                     m_RightNode.Add(orphanNode);
  283.                 }
  284.             }
  285.             else // compareResult == 0
  286.                 throw new ArgumentException("That key is already stored in the treap", "item");
  287.         }
  288.  
  289.         public bool Remove(KeyValuePair<TKey, TValue> item)
  290.         {
  291.             //Need the extra contains lookup to handle the case where TValue doesn't match
  292.             return Contains(item) && Remove(item.Key);
  293.         }
  294.  
  295.         public bool Remove(TKey key)
  296.         {
  297.             if (m_NodeIsEmpty)
  298.                 return false;
  299.  
  300.             int compareResult = key.CompareTo(m_NodeValue.Key);
  301.             if (compareResult < 0)
  302.             {
  303.                 if (m_LeftNode == null)
  304.                     return false;
  305.  
  306.                 bool removeResult = m_LeftNode.Remove(key);
  307.                 if (m_LeftNode.m_NodeIsEmpty)
  308.                     m_LeftNode = null;
  309.                 return removeResult;
  310.             }
  311.             if (compareResult > 0)
  312.             {
  313.                 if (m_RightNode == null)
  314.                     return false;
  315.  
  316.                 bool removeResult = m_RightNode.Remove(key);
  317.                 if (m_RightNode.m_NodeIsEmpty)
  318.                     m_RightNode = null;
  319.                 return removeResult;
  320.             }
  321.  
  322.             //We're removing this node.  With two child node, the higher priority one will
  323.             //be moved up to take this nodes place.  The lower priority node will be orphaned
  324.             //and will need to find a new home.  
  325.             Treap<TKey, TValue> orphanNode = null;
  326.             if (m_LeftNode != null && m_RightNode != null)
  327.                 orphanNode = m_LeftNode.m_NodePriority >= m_RightNode.m_NodePriority ? m_RightNode : m_LeftNode;
  328.  
  329.             if (m_LeftNode != null && (m_RightNode == null || m_LeftNode.m_NodePriority >= m_RightNode.m_NodePriority))
  330.             {
  331.                 //move up the left child
  332.                 m_NodeValue = m_LeftNode.m_NodeValue;
  333.                 m_NodePriority = m_LeftNode.m_NodePriority;
  334.                 m_RightNode = m_LeftNode.m_RightNode;
  335.                 m_LeftNode = m_LeftNode.m_LeftNode;
  336.             }
  337.             else if (m_RightNode != null && (m_LeftNode == null || m_RightNode.m_NodePriority > m_LeftNode.m_NodePriority))
  338.             {
  339.                 //move up the right child
  340.                 m_NodeValue = m_RightNode.m_NodeValue;
  341.                 m_NodePriority = m_RightNode.m_NodePriority;
  342.                 m_LeftNode = m_RightNode.m_LeftNode;
  343.                 m_RightNode = m_RightNode.m_RightNode;
  344.             }
  345.             else //m_LeftNode == null && m_RightNode == null
  346.             {
  347.                 //this node and everything below it is gone, we're an empty node now
  348.                 m_NodeValue = default(KeyValuePair<TKey, TValue>);
  349.                 m_NodeIsEmpty = true;
  350.             }
  351.  
  352.             if(orphanNode != null)
  353.                 Add(orphanNode);
  354.  
  355.             return true;
  356.         }
  357.  
  358.         public void Clear()
  359.         {
  360.             m_NodeValue = default(KeyValuePair<TKey, TValue>);
  361.             m_LeftNode = null;
  362.             m_RightNode = null;
  363.             m_NodeIsEmpty = true;
  364.         }
  365.  
  366.         public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
  367.         {
  368.             int currentStartIndex = arrayIndex;
  369.  
  370.             if(m_NodeIsEmpty)
  371.                 return;
  372.  
  373.             if(m_LeftNode != null)
  374.             {
  375.                 m_LeftNode.CopyTo(array, currentStartIndex);
  376.                 currentStartIndex += m_LeftNode.Count;
  377.             }
  378.  
  379.             array[currentStartIndex] = m_NodeValue;
  380.             currentStartIndex++;
  381.  
  382.             if (m_RightNode != null)
  383.             {
  384.                 m_RightNode.CopyTo(array, currentStartIndex);
  385.             }
  386.         }
  387.  
  388.         private void RotateRight()
  389.         {
  390.             //hold on to the current node in a temp object
  391.             Treap<TKey, TValue> tempNode = new Treap<TKey, TValue>(this);
  392.  
  393.             //copy in the data that will make up the new root value;
  394.             m_NodeValue = m_LeftNode.m_NodeValue;
  395.             m_NodePriority = m_LeftNode.m_NodePriority;
  396.  
  397.             //rearrange the linkages
  398.             m_LeftNode = tempNode.m_LeftNode.m_LeftNode;
  399.             m_RightNode = new Treap<TKey, TValue>(tempNode);
  400.             m_RightNode.m_LeftNode = tempNode.m_LeftNode.m_RightNode;
  401.         }
  402.  
  403.         private void RotateLeft()
  404.         {
  405.             //hold on to the current node in a temp object
  406.             Treap<TKey, TValue> tempNode = new Treap<TKey, TValue>(this);
  407.  
  408.             //copy in the data that will make up the new root value;
  409.             m_NodeValue = m_RightNode.m_NodeValue;
  410.             m_NodePriority = m_RightNode.m_NodePriority;
  411.  
  412.             //rearrange the linkages
  413.             m_RightNode = tempNode.m_RightNode.m_RightNode;
  414.             m_LeftNode = new Treap<TKey, TValue>(tempNode);
  415.             m_LeftNode.m_RightNode = tempNode.m_RightNode.m_LeftNode;
  416.         }
  417.  
  418.         internal bool IsValid()
  419.         {
  420.             if (m_LeftNode != null)
  421.             {
  422.                 if(m_LeftNode.m_NodePriority > m_NodePriority)
  423.                     return false;
  424.                 if (m_LeftNode.m_NodeValue.Key.CompareTo(m_NodeValue.Key) >= 0)
  425.                     return false;
  426.                 if (!m_LeftNode.IsValid())
  427.                     return false;
  428.             }
  429.  
  430.             if (m_RightNode != null)
  431.             {
  432.                 if (m_RightNode.m_NodePriority > m_NodePriority)
  433.                     return false;
  434.                 if (m_RightNode.m_NodeValue.Key.CompareTo(m_NodeValue.Key) <= 0)
  435.                     return false;
  436.                 if (!m_RightNode.IsValid())
  437.                     return false;
  438.             }
  439.                
  440.             return true;
  441.         }
  442.     }
  443. }
clone this paste RAW Paste Data