Last active

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

(Naïve) implementation of immutable double-ended queues (deques) based on balanced binary trees.

View Deque+Empty.cs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
using System;
 
partial class Deque<T>
{
private sealed class Empty<T> : IDeque<T>
{
public IDeque<T> PushFront(T value)
{
return new Deque<T>(value, Deque<T>.Empty, Deque<T>.Empty);
}
T IDeque<T>.PeekFront()
{
throw new InvalidOperationException();
}
IDeque<T> IDeque<T>.PopFront()
{
return this;
}
int IDeque<T>.Height { get { return 0; } }
}
}
View Deque+Empty.cs
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
using System;
 
public sealed partial 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>();
}
View Deque+Empty.cs
1 2 3 4 5 6 7
public interface IDeque<T>
{
IDeque<T> PushFront(T value);
T PeekFront();
IDeque<T> PopFront();
int Height { get; }
}
Owner

This gist is referred in the Stack Overflow question, Implement an immutable deque as a balanced binary tree?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.