Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
public static class ImmutableListExtensions
{
public static ImmutableList<T> Filter<T>(this ImmutableList<T> source, Func<T, bool> predicate)
{
if (source == null) throw new ArgumentNullException("source");
if (predicate == null) throw new ArgumentNullException("predicate");
if (source.IsEmpty) return source;
return ImmutableList<T>.Create(source.Where(predicate));
}
public static ImmutableList<T> QuickSort<T>(this ImmutableList<T> list, Func<T, T, int> compare)
{
if (list == null) throw new ArgumentNullException("list");
if (compare == null) throw new ArgumentNullException("compare");
return list.IsEmpty ? list :
list.Tail.Filter(e => compare(e, list.Head) < 0).QuickSort(compare) +
ImmutableList<T>.Create(list.Head) +
list.Tail.Filter(e => compare(e, list.Head) >= 0).QuickSort(compare);
}
}
public abstract class ImmutableList<T> : IEnumerable<T>
{
public static readonly ImmutableList<T> Empty = new EmptyImmutableList<T>();
public static ImmutableList<T> Create(T element)
{
return new NonEmptyImmutableList<T>(element, Empty);
}
public static ImmutableList<T> Create(params T[] elements)
{
if (elements == null) throw new ArgumentNullException("elements");
return Create(elements, Empty);
}
public static ImmutableList<T> Create(IEnumerable<T> elements)
{
if (elements == null) throw new ArgumentNullException("elements");
return Create(elements, Empty);
}
private static ImmutableList<T> Create(IEnumerable<T> elements, ImmutableList<T> tail)
{
return NonEmptyImmutableList<T>.FromEnumerable(elements, tail);
}
public static ImmutableList<T> operator +(ImmutableList<T> headList, ImmutableList<T> tailList)
{
if (headList == null) throw new ArgumentNullException("headList");
if (tailList == null) throw new ArgumentNullException("tailList");
if (headList.IsEmpty) return tailList;
if (tailList.IsEmpty) return headList;
return Create(headList, tailList);
}
public abstract T Head { get; }
public abstract ImmutableList<T> Tail { get; }
public abstract bool IsEmpty { get; }
#region IEnumerable<T> Members
public IEnumerator<T> GetEnumerator()
{
var current = this;
while (!current.IsEmpty)
{
yield return current.Head;
current = current.Tail;
}
}
#endregion
#region IEnumerable Members
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
}
internal sealed class EmptyImmutableList<T> : ImmutableList<T>
{
public EmptyImmutableList() { }
public override T Head
{
get
{
throw new InvalidOperationException("an empty list has no head.");
}
}
public override ImmutableList<T> Tail
{
get
{
throw new InvalidOperationException("an empty list has no tail.");
}
}
public override bool IsEmpty { get { return true; } }
}
internal class NonEmptyImmutableList<T> : ImmutableList<T>
{
public static ImmutableList<T> FromEnumerable(IEnumerable<T> elements, ImmutableList<T> tail)
{
NonEmptyImmutableList<T> result = null, last = null;
foreach (var item in elements)
{
var newNode = new NonEmptyImmutableList<T>(item, Empty);
if (last == null)
{
result = last = newNode;
}
else
{
last.m_tail = newNode;
last = newNode;
}
}
if (last != null)
{
last.m_tail = tail;
}
return result ?? tail;
}
public NonEmptyImmutableList(T head, ImmutableList<T> tail)
{
this.m_head = head;
this.m_tail = tail;
}
private T m_head;
public override T Head { get { return this.m_head; } }
private ImmutableList<T> m_tail;
public override ImmutableList<T> Tail { get { return this.m_tail; } }
public override bool IsEmpty { get { return false; } }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.