Queues and buffers

Circular buffer

CircularBuffer<T> holds at most Capacity items. With AllowOverwrite, adding to a full buffer removes the item at the other end:

var buffer = new CircularBuffer<int>(3) { AllowOverwrite = true };
buffer.AddLast(1);
buffer.AddLast(2);
buffer.AddLast(3);
Assert.Equal([1, 2, 3], buffer);

buffer.AddLast(4); // overwrites 1
Assert.Equal([2, 3, 4], buffer);

Without AllowOverwrite, adding to a full buffer throws an InvalidOperationException:

var buffer = new CircularBuffer<int>(2);
buffer.AddLast(1);
buffer.AddLast(2);

// Without AllowOverwrite, adding to a full buffer throws
Assert.Throws<InvalidOperationException>(() => buffer.AddLast(3));

// Remove items from either end
Assert.Equal(1, buffer.RemoveFirst());
buffer.AddLast(3);
Assert.Equal([2, 3], buffer);

• AddLast and AddFirst add an item at one end. When the buffer is full and AllowOverwrite is true, AddLast overwrites the first item and AddFirst the last one.
• RemoveFirst and RemoveLast remove and return an item, and throw an InvalidOperationException when the buffer is empty.
• The indexer reads an item by its position, from the first item. You can change Capacity after the buffer is created, to any value greater than 0 that holds the current items.
• CopyTo checks that the destination array has room for all the items before it writes any of them.

Use it for the last N log lines, measurements or events.

Double-ended queue

DoubleEndedQueue<T> grows as needed, and adds and removes items at both ends:

var queue = new DoubleEndedQueue<string>(capacity: 4); // Grows when needed
queue.AddLast("b");
queue.AddLast("c");
queue.AddFirst("a");

Assert.Equal(["a", "b", "c"], queue);
Assert.Equal("c", queue[2]);
Assert.Equal("a", queue.RemoveFirst());
Assert.Equal("c", queue.RemoveLast());

The constructor takes the initial capacity. RemoveFirst and RemoveLast throw an InvalidOperationException when the queue is empty.

Most recent items

LimitList<T> keeps at most a number of items, and drops the item at the other end when you add one to a full list:

// Keep the 3 most recent items
var recentFiles = new LimitList<string>(3);
recentFiles.AddFirst("a.txt");
recentFiles.AddFirst("b.txt");
recentFiles.AddFirst("c.txt");
recentFiles.AddFirst("d.txt"); // a.txt, the last item, is removed

Assert.Equal(["d.txt", "c.txt", "b.txt"], recentFiles);

AddFirst drops the last item, and AddLast drops the first one. Unlike CircularBuffer<T>, a full LimitList<T> never throws. It also supports Remove, RemoveAt, RemoveFirst, RemoveLast and setting an item by index.

LimitList<T> implements IList<T> and IReadOnlyList<T>. It stores the items in a ring buffer, so reading an item by index and adding or removing an item at either end take constant time. Insert on a full list drops the last item, except at index Count, where it behaves like AddLast and drops the first one. foreach uses a struct enumerator, so it does not allocate.

Append-only collection

AppendOnlyCollection<T> is a collection you can only add to. Adding is thread-safe, and reading — the indexer, Count, enumeration, Contains, Find and TryFind — needs no lock, even while other threads add items:

var log = new AppendOnlyCollection<string>();

// Add items from several threads, and read them at the same time
await Task.WhenAll(
    Task.Run(() => log.Add("from task 1")),
    Task.Run(() => log.Add("from task 2")));

Assert.HasCount(2, log);
Assert.True(log.Contains(item => item == "from task 1"));
Assert.Equal("from task 2", log.Find(item => item.EndsWith("2", StringComparison.Ordinal)));

Items cannot be removed: Clear and Remove throw a NotSupportedException.