Skip to content

@stakx /Deque+Empty.cs
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
(Naïve) implementation of immutable double-ended queues (deques) based on balanced binary trees.
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; } }
}
}
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>();
}
public interface IDeque<T>
{
IDeque<T> PushFront(T value);
T PeekFront();
IDeque<T> PopFront();
int Height { get; }
}
@stakx
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.