Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Two fixes for two silly bugs.
/// <summary>
/// A list that can be used by readers as a true immutable read-only list
/// and that supports relatively efficient "append to the end" and "remove
/// from the front" operations, by sharing the underlying array whenever
/// possible. Implemented as a class so it can be used to "CAS" when making
/// changes in order to allow lockless immutability.
/// Caution: multithreaded append operations are not safe, also not when
/// using CAS.
/// </summary>
public class ImmutableAppendOnlyList<T> : IReadOnlyList<T>
{
private delegate void RangeCopier(IEnumerable<T> source, T[] dest, int destOffset, int count);
private readonly T[] _values;
private readonly int _head;
private readonly int _count;
private ImmutableAppendOnlyList(T[] values, int head, int count)
{
_values = values;
_head = head;
_count = count;
}
/// <summary>
/// A "new" empty instance of a list.
/// </summary>
public static readonly ImmutableAppendOnlyList<T> Empty = new ImmutableAppendOnlyList<T>(new T[0], 0, 0);
/// <summary>
/// Creates a new list with the given items as the initial content.
/// </summary>
public static ImmutableAppendOnlyList<T> CreateFrom(IEnumerable<T> items)
{
if (items == null)
return Empty;
var values = items.ToArray();
return values.Length == 0 ? Empty : new ImmutableAppendOnlyList<T>(values, 0, values.Length);
}
/// <summary>
/// Creates a new list with the given initial capacity.
/// </summary>
public static ImmutableAppendOnlyList<T> Create(int initialCapacity)
{
return initialCapacity > 0 ? new ImmutableAppendOnlyList<T>(new T[initialCapacity], 0, 0) : Empty;
}
/// <summary>
/// Returns the item at the given index.
/// </summary>
public T this[int itemIndex]
{
get
{
if ((uint)itemIndex >= (uint)_count)
throw new IndexOutOfRangeException("itemIndex");
return _values[_head + itemIndex];
}
}
/// <summary>
/// Returns the number of items in the list.
/// </summary>
public int Count
{
get { return _count; }
}
/// <summary>
/// Returns whether the collection is empty, i.e. contains no items
/// </summary>
public bool IsEmpty
{
get { return _count == 0; }
}
/// <summary>
/// Returns an enumerator over the items in the collection.
/// </summary>
public IEnumerator<T> GetEnumerator()
{
for (var i = _head; i < _count; i++)
yield return _values[i];
}
/// <summary>
/// Returns an enumerator over the items in the collection.
/// </summary>
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return ((IReadOnlyList<T>)this).GetEnumerator();
}
/// <summary>
/// Returns a new list with the given item appended to the end.
/// </summary>
public ImmutableAppendOnlyList<T> Append(T item)
{
var newCount = _count + 1;
var tail = _head + _count;
if (tail == _values.Length)
{
var newArray = GrowTo((newCount) * 2);
newArray[_count] = item;
return new ImmutableAppendOnlyList<T>(newArray, 0, newCount);
}
_values[tail] = item;
return new ImmutableAppendOnlyList<T>(_values, _head, newCount);
}
/// <summary>
/// Returns a new list with the given set of items appended to the end.
/// </summary>
public ImmutableAppendOnlyList<T> AppendRange(IEnumerable<T> items)
{
var nToAdd = 0;
RangeCopier copier = CopyEnumerable;
if (items != null)
{
var collectionType = items.GetType();
if (collectionType.IsArray)
{
nToAdd = ((T[])items).Length;
copier = CopyArray;
}
else if (typeof(System.Collections.ICollection).IsAssignableFrom(collectionType))
{
nToAdd = ((System.Collections.ICollection)items).Count;
if (typeof(List<T>).IsAssignableFrom(collectionType))
copier = CopyList;
}
else
nToAdd = items.Count();
}
if (nToAdd == 0)
return this;
var newCount = _count + nToAdd;
var tail = _head + _count;
if (tail + nToAdd > _values.Length)
{
var newArray = GrowTo(_count + nToAdd * 2);
copier(items, newArray, _count, nToAdd);
return new ImmutableAppendOnlyList<T>(newArray, 0, newCount);
}
copier(items, _values, tail, nToAdd);
return new ImmutableAppendOnlyList<T>(_values, _head, newCount);
}
/// <summary>
/// Returns a new list from which the first element is removed.
/// </summary>
public ImmutableAppendOnlyList<T> RemoveFront()
{
return _count == 1
? Empty
: new ImmutableAppendOnlyList<T>(_values, _head + 1, _count - 1);
}
/// <summary>
/// Returns a new list from which the first element is removed, where
/// this element is provided as output in <paramref name="removed"/>.
/// </summary>
public ImmutableAppendOnlyList<T> RemoveFront(out T removed)
{
removed = _values[_head];
return _count == 1
? Empty
: new ImmutableAppendOnlyList<T>(_values, _head + 1, _count - 1);
}
/// <summary>
/// Returns a new list from which the given number of first elements
/// are removed.
/// </summary>
public ImmutableAppendOnlyList<T> RemoveFront(int nToRemove)
{
return nToRemove >= _count
? Empty
: new ImmutableAppendOnlyList<T>(_values, _head + nToRemove, _count - 1);
}
/// <summary>
/// Returns a new list from which the given number of first elements
/// are removed and stored as output in the given list.
/// </summary>
public ImmutableAppendOnlyList<T> RemoveFront(int nToRemove, List<T> removed)
{
var remove = nToRemove > _count ? _count : nToRemove;
if (removed != null)
removed.AddRange(_values.Skip(_head).Take(remove));
return remove == _count
? Empty
: new ImmutableAppendOnlyList<T>(_values, _head + nToRemove, _count - 1);
}
/// <summary>
/// Returns a new list from which all first elements that meet the
/// given predicate are removed and stored as output in the given list.
/// </summary>
public ImmutableAppendOnlyList<T> RemoveUntil(Predicate<T> shouldRemove, List<T> removed)
{
var newHead = _head;
var tail = _head + _count;
while (shouldRemove(_values[newHead]) && newHead < tail)
newHead++;
return newHead == _head
? this
: RemoveFront(newHead - _head, removed);
}
private T[] GrowTo(int newLength)
{
//newLength = Memory.Bits.NextPowerOf2(newLength);
var newArray = new T[newLength];
Array.Copy(_values, _head, newArray, 0, _count);
return newArray;
}
private static void CopyArray(IEnumerable<T> source, T[] dest, int destOffset, int count)
{
Array.Copy((T[])source, 0, dest, destOffset, count);
}
private static void CopyList(IEnumerable<T> source, T[] dest, int destOffset, int count)
{
((List<T>)source).CopyTo(0, dest, destOffset, count);
}
private static void CopyEnumerable(IEnumerable<T> source, T[] dest, int destOffset, int count)
{
// We want to guard against the source enumerable changing from
// under us. We do not add more than the given count, and throw
// if there is less.
using (var enumerator = source.GetEnumerator())
{
for (int i = 0; i < count; i++)
{
enumerator.MoveNext(); // should throw if we attempt to advance past the end.
dest[destOffset++] = enumerator.Current;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment