JBlam.Collections.CircularBuffer 0.0.1-testing

JBlam.Collections.CircularBuffer

A fixed-capacity circular buffer which can expose immutable lists.

Usage

using JBlam.Collections.Immutable;

// Create a circular buffer which retains at least 20 elements.
// The default capacity will be twice the "length" - so 40 elements in this example.
const int BufferLength = 20;
CircularBuffer<int> b = new(BufferLength);

// Items may be enqueued without explicitly managing the buffering.
for (int i = 0; i < 50; i++)
    b.Enqueue(i);

// The buffer snapshot is immutable; the lifetime does not need to be managed.
BufferList<int> snapshot = b.Current;

// Even if we cycle through the whole buffer, the snapshot is still valid.
// The underlying storage for the snapshot still exists.
for (int i = 0; i < 50; i++)
    b.Enqueue(1000 + i);
// List is indexable, sliceable, enumerable.
System.Diagnostics.Debug.Assert(snapshot[^1] == 49);
System.Diagnostics.Debug.Assert(snapshot.Count == BufferLength);
// The underlying storage is garbage collected like any other .NET object: it's eligible
// for collection when there are no more references to the snapshot.

Why?

The main motivation was to create observable fixed-size collections, with favourable memory footprint and insertion algorithmic complexity. In plain terms: make it easy to produce "latest n elements from this observable".

Why not System.Collections.Generic.Queue

The BufferList<T> snapshots are immutable; you can freely pass them around or using them in an observable. Queue<T> is mutable, so the collection contents may have changed before (or even during) observation.

Why not System.Collections.Immutable.ImmutableQueue

ImmutableQueue is two ImmutableStack instances (one forward, one backward); an ImmutableStack is a linked list, which has poor tradeoffs for memory allocation and enumeration algorithmic complexity.

BufferList snapshots are a "linked list" two buffers. The underlying storage is a plain array.

Why not a sequence of arrays

Generating each array snapshot re-allocates item storage, so the observation sequence is O(n²) in memory.

Implementation

A CircularBuffer maintains two arrays of length n; when the "head" buffer is full, the "tail" buffer is discarded, the "head" becomes the "tail", and a new "head" is allocated.

BufferList snapshots are a value-type referencing a ReadOnlyMemory<T> slice of the current "head" and "tail".

The parent CircularBuffer may continue to mutate the "unused" slice of its head buffer, outside the "read-only" slice which may have already been observed in a BufferList.