Created
September 2, 2009 02:50
-
-
Save JeffreyZhao/179520 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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