public
Last active

  • Download Gist
Deque-PushFront-PeekFront-PopFront.cs
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
using System;
 
public interface IDeque<T>
{
IDeque<T> PushFront(T value);
T PeekFront();
IDeque<T> PopFront();
int Height { get; }
}
 
internal class Empty<T> : IDeque<T>
{
public IDeque<T> PushFront(T value)
{
return new Deque<T>(value, Deque<T>.Empty, Deque<T>.Empty);
}
 
public T PeekFront()
{
throw new InvalidOperationException();
}
 
public IDeque<T> PopFront()
{
return this;
}
 
int IDeque<T>.Height { get { return 0; } }
}
 
public class Deque<T> : IDeque<T>
{
public Deque(T value, IDeque<T> left, IDeque<T> right)
{
this.Value = value;
this.Left = left;
this.Right = right;
}
 
public T Value { get; private set; }
public IDeque<T> Left { get; private set; }
public IDeque<T> Right { get; private set; }
 
int IDeque<T>.Height { get { return 1 + Math.Max(this.Left.Height, this.Right.Height); } }
 
public bool IsLeftmost
{
get { return this.Left is Empty<T>; }
}
 
public IDeque<T> PushFront(T value)
{
if (this.IsLeftmost)
{
return new Deque<T>(this.Value,
new Deque<T>(value, Deque<T>.Empty, Deque<T>.Empty),
this.Right).TryRebalance();
}
else
{
return new Deque<T>(this.Value,
this.Left.PushFront(value),
this.Right).TryRebalance();
}
// NB: ideally, the node creation and re-balancing would be done in one single step!
}
 
public T PeekFront()
{
if (this.IsLeftmost)
{
return this.Value;
}
else
{
return this.Left.PeekFront();
}
}
 
public IDeque<T> PopFront()
{
if (this.IsLeftmost)
{
return this.Right;
}
else
{
return new Deque<T>(this.Value,
this.Left.PopFront(),
this.Right).TryRebalance();
}
// NB: ideally, the node creation and re-balancing would be done in one single step!
}
 
private IDeque<T> TryRebalance()
{
var balance = this.Right.Height - this.Left.Height;
if (balance > 1)
{
return this.TryRotateLeft();
}
else if (balance < -1)
{
return this.TryRotateRight();
}
else
{
return this;
}
}
 
private IDeque<T> TryRotateLeft()
{
if (this.Right is Deque<T>)
{
var right = this.Right as Deque<T>;
return new Deque<T>(right.Value,
new Deque<T>(this.Value, this.Left, right.Left),
right.Right);
}
else
{
return this;
}
}
 
private IDeque<T> TryRotateRight()
{
if (this.Left is Deque<T>)
{
var left = this.Left as Deque<T>;
return new Deque<T>(left.Value,
left.Left,
new Deque<T>(this.Value, left.Right, this.Right));
}
else
{
return this;
}
}
 
public static readonly IDeque<T> Empty = new Empty<T>();
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.