Want more features on Pastebin? Sign Up, it's FREE!
Guest

Juliet

By: a guest on Mar 13th, 2010  |  syntax: C#  |  size: 4.51 KB  |  views: 105  |  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.Generic;
  3. using System.Linq;
  4. using System.Diagnostics;
  5.  
  6. namespace ConsoleApplication1
  7. {
  8.     public sealed class Treap<T>
  9.     {
  10.         private readonly Func<T, T, int> Comparer;
  11.         private readonly Treap<T> Left;
  12.         private readonly T Value;
  13.         private readonly Treap<T> Right;
  14.  
  15.         // book keeping
  16.         private readonly Random Rnd;
  17.         private readonly int Height; // not needed, only used to ensure that our tree is mostly balanced
  18.         private readonly int Priority;
  19.         public readonly int Count;
  20.  
  21.         public Treap(Func<T, T, int> comparer)
  22.         {
  23.             this.Comparer = comparer;
  24.             this.Priority = Int32.MinValue;
  25.             this.Rnd = new Random();
  26.         }
  27.  
  28.         private Treap(Func<T, T, int> comparer, Treap<T> left, T value, Treap<T> right, int priority)
  29.         {
  30.             this.Comparer = comparer;
  31.             this.Left = left;
  32.             this.Right = right;
  33.             this.Value = value;
  34.  
  35.             this.Height = Math.Max(left.Height, right.Height) + 1;
  36.             this.Count = left.Count + right.Count + 1;
  37.             this.Rnd = left.Rnd;
  38.             this.Priority = priority;
  39.         }
  40.  
  41.         private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
  42.         {
  43.             return new Treap<T>(Comparer, left, value, right, priority);
  44.         }
  45.  
  46.         private Treap<T> Make(Treap<T> left, T value, Treap<T> right)
  47.         {
  48.             return Make(left, value, right, Rnd.Next(Int32.MinValue, Int32.MaxValue));
  49.         }
  50.  
  51.         private bool IsEmpty { get { return Count == 0; } }
  52.  
  53.         public Treap<T> Insert(T v)
  54.         {
  55.             if (IsEmpty)
  56.             {
  57.                 return Make(this, v, this);
  58.             }
  59.             else
  60.             {
  61.                 int compare = Comparer(v, Value);
  62.                 if (compare < 0)
  63.                 {
  64.                     return Make(Left.Insert(v), Value, Right, Priority).HeapifyLeft();
  65.                 }
  66.                 else if (compare > 0)
  67.                 {
  68.                     return Make(Left, Value, Right.Insert(v), Priority).HeapifyRight();
  69.                 }
  70.                 else
  71.                 {
  72.                     return this;
  73.                 }
  74.             }
  75.         }
  76.  
  77.         public Treap<T> HeapifyLeft()
  78.         {
  79.             if (this.Priority < Left.Priority)
  80.             {
  81.                 return RotateRight();
  82.             }
  83.             return this;
  84.         }
  85.  
  86.         public Treap<T> HeapifyRight()
  87.         {
  88.             if (this.Priority < Right.Priority)
  89.             {
  90.                 return RotateLeft();
  91.             }
  92.             return this;
  93.         }
  94.  
  95.         /// <summary>
  96.         /// Left tree rotation.
  97.         /// </summary>
  98.         /// <remarks>
  99.         ///       q      Right Rotation       p
  100.         ///     /   \    --------------+    /   \
  101.         ///    p     c                     a     q
  102.         ///   / \        Left Rotation          / \
  103.         ///  a   b       +-------------        b   c
  104.         /// </remarks>
  105.         private Treap<T> RotateLeft()
  106.         {
  107.             if (this.IsEmpty || this.Right.IsEmpty)
  108.             {
  109.                 return this;
  110.             }
  111.  
  112.             T p = this.Value;
  113.             int pPriority = this.Priority;
  114.  
  115.             T q = this.Right.Value;
  116.             int qPriority = this.Right.Priority;
  117.  
  118.             Treap<T> a = this.Left;
  119.             Treap<T> b = this.Right.Left;
  120.             Treap<T> c = this.Right.Right;
  121.             return Make(Make(a, p, b, pPriority), q, c, qPriority);
  122.         }
  123.  
  124.         /// <summary>
  125.         /// Right tree rotation
  126.         /// </summary>
  127.         /// <remarks>
  128.         ///       q      Right Rotation       p
  129.         ///     /   \    --------------+    /   \
  130.         ///    p     c                     a     q
  131.         ///   / \        Left Rotation          / \
  132.         ///  a   b       +-------------        b   c
  133.         /// </remarks>
  134.         private Treap<T> RotateRight()
  135.         {
  136.             if (this.IsEmpty || this.Left.IsEmpty)
  137.             {
  138.                 return this;
  139.             }
  140.  
  141.             T q = this.Value;
  142.             int qPriority = this.Priority;
  143.  
  144.             T p = this.Left.Value;
  145.             int pPriority = this.Left.Priority;
  146.  
  147.             Treap<T> a = this.Left.Left;
  148.             Treap<T> b = this.Left.Right;
  149.             Treap<T> c = this.Right;
  150.             return Make(a, p, Make(b, q, c, qPriority), pPriority);
  151.         }
  152.     }
  153. }
clone this paste RAW Paste Data