using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace ConsoleApplication1
{
public sealed class Treap<T>
{
private readonly Func<T, T, int> Comparer;
private readonly Treap<T> Left;
private readonly T Value;
private readonly Treap<T> Right;
// book keeping
private readonly Random Rnd;
private readonly int Height; // not needed, only used to ensure that our tree is mostly balanced
private readonly int Priority;
public readonly int Count;
public Treap(Func<T, T, int> comparer)
{
this.Comparer = comparer;
this.Priority = Int32.MinValue;
this.Rnd = new Random();
}
private Treap(Func<T, T, int> comparer, Treap<T> left, T value, Treap<T> right, int priority)
{
this.Comparer = comparer;
this.Left = left;
this.Right = right;
this.Value = value;
this.Height = Math.Max(left.Height, right.Height) + 1;
this.Count = left.Count + right.Count + 1;
this.Rnd = left.Rnd;
this.Priority = priority;
}
private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
{
return new Treap<T>(Comparer, left, value, right, priority);
}
private Treap<T> Make(Treap<T> left, T value, Treap<T> right)
{
return Make(left, value, right, Rnd.Next(Int32.MinValue, Int32.MaxValue));
}
private bool IsEmpty { get { return Count == 0; } }
public Treap<T> Insert(T v)
{
if (IsEmpty)
{
return Make(this, v, this);
}
else
{
int compare = Comparer(v, Value);
if (compare < 0)
{
return Make(Left.Insert(v), Value, Right, Priority).HeapifyLeft();
}
else if (compare > 0)
{
return Make(Left, Value, Right.Insert(v), Priority).HeapifyRight();
}
else
{
return this;
}
}
}
public Treap<T> HeapifyLeft()
{
if (this.Priority < Left.Priority)
{
return RotateRight();
}
return this;
}
public Treap<T> HeapifyRight()
{
if (this.Priority < Right.Priority)
{
return RotateLeft();
}
return this;
}
/// <summary>
/// Left tree rotation.
/// </summary>
/// <remarks>
/// q Right Rotation p
/// / \ --------------+ / \
/// p c a q
/// / \ Left Rotation / \
/// a b +------------- b c
/// </remarks>
private Treap<T> RotateLeft()
{
if (this.IsEmpty || this.Right.IsEmpty)
{
return this;
}
T p = this.Value;
int pPriority = this.Priority;
T q = this.Right.Value;
int qPriority = this.Right.Priority;
Treap<T> a = this.Left;
Treap<T> b = this.Right.Left;
Treap<T> c = this.Right.Right;
return Make(Make(a, p, b, pPriority), q, c, qPriority);
}
/// <summary>
/// Right tree rotation
/// </summary>
/// <remarks>
/// q Right Rotation p
/// / \ --------------+ / \
/// p c a q
/// / \ Left Rotation / \
/// a b +------------- b c
/// </remarks>
private Treap<T> RotateRight()
{
if (this.IsEmpty || this.Left.IsEmpty)
{
return this;
}
T q = this.Value;
int qPriority = this.Priority;
T p = this.Left.Value;
int pPriority = this.Left.Priority;
Treap<T> a = this.Left.Left;
Treap<T> b = this.Left.Right;
Treap<T> c = this.Right;
return Make(a, p, Make(b, q, c, qPriority), pPriority);
}
}
}