A buffer is a simple data structure that allows you to add any number of elements, but it only retains the last n, where n is the capacity of the buffer.`
Here are some examples of where buffers are used:
- For storing the last number of log entries, when only a fixed number can be displayed.
- For calculating statistics on the last number of seen entries, such as a moving average.
- A buffer with two elements can be used to implement double buffering, or anything that requires a value and its previous value to be stored.
- Buffers can be used for online signal processing, for example implementing differentiators, integrators, or PID controllers.
There are only a handful of actions we need to support, shown below.
public interface IBuffer<T> : IEnumerable<T>
{
public int Count { get; }
public int Capacity { get; }
public void Insert(T item);
public void Clear();
}
A practical implementation will support more methods and properties, as we will see below.
Implementation using a ring buffer
Buffers are commonly implemented as ring buffers, where an array is used with front and back pointers that updated as items are added. When reading the contents, we start at the front pointer, increasing until we reached the back pointer (wrapping around if necessary).
public class RingBuffer<T> : IBuffer<T>
{
private const string ArgumentMustBePositive = "Argument must be positive.";
private int front;
private int back;
private readonly T[] items;
public int Count { get; private set; }
public int Capacity { get; }
public RingBuffer(int capacity)
{
if (capacity <= 0)
throw new ArgumentOutOfRangeException(nameof(capacity), ArgumentMustBePositive);
Capacity = capacity;
items = new T[capacity];
ResetPointers();
}
public void Insert(T item)
{
items[back] = item;
back++;
if (back == Capacity)
{
back = 0;
}
if (Count < Capacity)
{
Count++;
}
else
{
front++;
if (front == Capacity)
{
front = 0;
}
}
AssertCountInvariants();
}
public void Clear()
{
ReInitialize();
ResetPointers();
}
public IEnumerator<T> GetEnumerator()
{
if (front < back)
{
for (int i = front; i < back; i++)
{
yield return items[i];
}
}
else
{
for (int i = front; i < Capacity; i++)
{
yield return items[i];
}
for (int i = 0; i < back; i++)
{
yield return items[i];
}
}
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
/*
Not strictly necessary for value types. For reference types,
this prevents having ghost references to objects and
so leak memory.
*/
private void ReInitialize()
{
if (front < back)
{
for (int i = front; i < back; i++)
{
items[i] = default;
}
}
else
{
for (int i = front; i < Capacity; i++)
{
items[i] = default;
}
for (int i = 0; i < back; i++)
{
items[i] = default;
}
}
}
public void ResetPointers()
{
front = 0;
back = 0;
Count = 0;
AssertCountInvariants();
}
[AssertionMethod, Conditional(GLDebug.Debug)]
private void AssertCountInvariants()
{
GLDebug.Assert(Count <= Capacity);
if (front < back)
{
Debug.Assert(Count == back - front);
}
else
{
Debug.Assert(Count == Capacity - front + back);
}
}
private static Exception EmptyBufferInvalid()
=> new InvalidOperationException(BufferCantBeEmpty);
}
The AssertCountInvariants method is to assert invariants after we modified the buffer. This helps flush out implementation bugs. When copying an algorithm where the implementation is presumably correct, scaffolding such as this may look pointless. However, it is important to learn how to use this type of scaffolding when designing or implementing an algorithm, so I keep them in. Besides, implementations that appear in books and papers have more bugs than one would hope, and therefore you should add checks like this even in code you find elsewhere.
When clearing out the container, we set the array values back to their defaults, to prevent leaks when the items are reference types.
Variants
Zero-capacity buffers
In the implementation above, we always expect the capacity to be positive. This prevents us from having to check whether we can write the array element when we insert elements. If zero-capacity buffers are required, a separate class can be used instead.
public class ZeroCapacityBuffer<T> : IBuffer<T>
{
public int Count => 0;
public int Capacity => 0;
public T First => throw Buffer.EmptyBufferInvalid();
public T Last => throw Buffer.EmptyBufferInvalid();
/// <summary>
/// This method has no effect, since the capacity is 0.
/// </summary>
/*
Just like other buffers, it is not illegal to insert items
when we are at capacity. So we don't throw an exception; we
simply do nothing.
*/
public void Insert(T item) { }
//Nothing to do since there are no elements.
public void Clear() { }
public IEnumerator<T> GetEnumerator()
=> throw new NotImplementedException();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Capacity-two buffer
Using buffers with a capacity of two is a common case, so we may choose a (very slightly) more efficient implementation that does not use an array.
Keeping track of how many elements there are makes the code slightly complicated and annoying. We could avoid it with one or two tricks, for example, implementing the buffer so that it is always full. Often, this just moves the trickiness outside the class so the class user has to deal with it.
public sealed class FullCapacity2Buffer<T> : IBuffer<T>
{
private T item1;
private T item2;
private bool firstIsItem1;
public int Count { get; private set; }
public int Capacity => 2;
public T First
=> (Count == 0) ? throw Buffer.EmptyBufferInvalid() : FirstUnsafe;
public T Last
=> (Count == 0) ? throw Buffer.EmptyBufferInvalid() : LastUnsafe;
private T FirstUnsafe => firstIsItem1 ? item1 : item2;
private T LastUnsafe => firstIsItem1 ? item2 : item1;
public FullCapacity2Buffer() => Clear();
public IEnumerator<T> GetEnumerator()
{
if(Count > 0) yield return FirstUnsafe;
if(Count > 1) yield return LastUnsafe;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public void Insert(T item)
{
if (firstIsItem1)
{
item1 = item;
}
else
{
item2 = item;
}
if (Count < 2)
{
Count++;
}
firstIsItem1 = !firstIsItem1;
}
public void Clear()
{
Count = 0;
item1 = default;
item2 = default;
firstIsItem1 = false; //true after first insertion
}
}
Random-access ring-buffer
The ring buffer implementation above allows us to add two very useful features with little effort:
- random access to elements; and
- accessors to the first and last elements.
Here is how that looks:
public class RingBuffer<T> : IBuffer<T>
{
// ...
public T First
=> Count > 0
? this[0]
: throw Buffer.EmptyBufferInvalid();
public T Last
=> Count > 0
? this[Count - 1]
: throw Buffer.EmptyBufferInvalid();
public T this[int index]
{
get
{
ValidateIndex(index);
return items[GetRealIndex(index)];
}
set
{
ValidateIndex(index);
items[GetRealIndex(index)] = value;
}
}
private bool IndexInRange(int index) => 0 <= index && index < Count;
private int GetRealIndex(int index)
{
Debug.Assert(IndexInRange(index));
(index + front) % Capacity;
}
[AssertionMethod]
private void ValidateIndex(int index)
{
if (!IndexInRange(index))
throw new ArgumentOutOfRangeException(nameof(index));
}
Public methods check the index, and throw an exception when it is invalid. Thereafter, we don’t validate it again — instead, we assert it to be valid in case we made a mistake.
Buffer implemented with queue
If you don’t need random access, you can implement a buffer with a queue, which is much simpler. The queue has some additional overhead and may be less efficient, although there is no reason to worry about this unless it shows up as a problem when profiling.
public class BufferWithQueue<T> : IRingBuffer<T>
{
private readonly System.Collections.Generic.Queue<T> queue;
public int Count => queue.Count;
public int Capacity { get; }
public T First => queue.First();
public T Last => queue.Peek();
public BufferWithQueue(int capacity)
{
Capacity = capacity;
queue = new System.Collections.Generic.Queue<T>(capacity);
}
public void Insert(T item)
{
if (queue.Count == Capacity)
{
queue.Dequeue();
}
queue.Enqueue(item);
}
public void Clear() => queue.Clear();
public IEnumerator<T> GetEnumerator() => queue.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Resizeable buffer
To make a buffer that can be resized, you can use the appropriate fixed-sized buffers as shown below.
public class ResizeableBuffer<T> : IBuffer<T>
{
private IBuffer<T> buffer;
public int Count => buffer.Count;
public int Capacity => buffer.Capacity;
public T First => buffer.First;
public T Last => buffer.Last;
public ResizeableBuffer(int capacity)
=> buffer = new RingBuffer<T>(capacity);
public void Insert(T item) => buffer.Insert(item);
public void Clear() => buffer.Clear();
public IEnumerator<T> GetEnumerator() => buffer.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public void Resize(int newCapacity)
{
if (newCapacity < 0)
throw new ArgumentOutOfRangeException(nameof(newCapacity), "Argument must be positive");
if (newCapacity == 0)
{
buffer = new ZeroCapacityBuffer<T>();
return;
}
var newBuffer = new RingBuffer<T>(newCapacity);
foreach (var item in buffer.Take(newCapacity))
{
newBuffer.Insert(item);
}
buffer = newBuffer;
}
}
Using buffers
Recursive sequences
Sequences where each element is defined as a function of a few previous terms, can be implemented iteratively with a buffer. Here is how the Fibonacci sequence can be calculated:
public static int GetFibonacci(int n)
{
if (n < 0)
throw new ArgumentOutOfRangeException(nameof(n), "Can't be negative.");
if (n == 0 || n == 1) return 1;
var buffer = new RingBuffer<int>(2);
buffer.Insert(1);
buffer.Insert(1);
for (int i = 0; i < n - 2; i++)
{
buffer.Insert(buffer[0] + buffer[1]);
}
return buffer.Last;
}
Filtering
The example below shows how to use a buffer to apply a median filter to a list.
public class StatsExample
{
public static IEnumerable<float> MedianFilter(IEnumerable<float> list)
{
float Median(float a, float b, float c) =>
(a > b) ^ (a > c)
? a
: (b < a) ^ (b < c)
? b
: c;
int windowSize = 3;
var buffer = new RingBuffer<float>(windowSize);
foreach (float item in list)
{
buffer.Insert(item);
if (buffer.Count >= windowSize)
{
yield return Median(buffer[0], buffer[1], buffer[2]);
}
}
}
}
Change detection
It is common to execute code only when the value of variable changes. This is typically implemented by storing the previous value too. Using a change detector shown below can make the code cleaner and safer.
public class ChangeDetector<T>
{
private readonly IBuffer<T> buffer;
private readonly IEqualityComparer<T> comparer;
public event Action<T, T> OnValueChanged;
public T Value
{
get => buffer.Last;
set
{
buffer.Insert(value);
if (buffer.Count == 2 && !comparer.Equals(Value, PreviousValue))
{
OnValueChanged?.Invoke(Value, PreviousValue);
}
}
}
public T PreviousValue => buffer.First;
public ChangeDetector(IEqualityComparer<T> comparer = null)
{
this.comparer = comparer ?? EqualityComparer<T>.Default;
buffer = new RingBuffer<T>(2);
}
public void Clear() => buffer.Clear();
}
Here is an example of using this class:
public class ChangeDetectExample
{
private readonly ChangeDetector<int> guess = new();
public ChangeDetectExample()
=> guess.OnValueChanged += (value, previousValue) => Console.WriteLine($"You changed your guess from {previousValue} to {value}");
public void Run() => guess.Value = AskGuess();
public int AskGuess() => 0; /* Real implementation omitted */
}
Differentiator, integrator, and PID controller
The code below shows how to use buffers to implement a differentiator and integrator, and then to use those classes to implement a PID controller.
public sealed class Differentiator
{
private readonly IBuffer<float> buffer;
public float Value
{
get => buffer.Last;
set => buffer.Insert(value);
}
public float PreviousValue => buffer.First;
/*
Technically to be a derivative we need to divide by the time.
If we assume a constant sample rate, this is a constant, that
can be absorbed by the PID filter.
*/
public float Difference =>
buffer.Count == 2
? Value - PreviousValue
: throw new InvalidOperationException("Not enough values set to calculate a derivative");
public Differentiator() => buffer = new RingBuffer<float>(2);
}
public sealed class Integrator
{
private readonly IBuffer<float> buffer;
public float Value
{
get => buffer.Last;
set => buffer.Insert(value);
}
public float PreviousValue => buffer.First;
/*
Technically, we need to scale each interval by the time between
samples. We assume the sample rate is constant, and that it can
be absorbed by the factor in the PID controller.
*/
public float Sum => buffer.Sum();
public Integrator(int sumWindow) =>
buffer = new RingBuffer<float>(sumWindow);
}
public sealed class PidController
{
private readonly Differentiator differentiator;
private readonly Integrator integrator;
private readonly float differentiatorFactor;
private readonly float integrationFactor;
private readonly float proportionalFactor;
public float Value
{
get => differentiator.Value; //Could also use integrator
set
{
differentiator.Value = value;
integrator.Value = value;
}
}
public float FilteredValue =>
proportionalFactor * Value
+ differentiatorFactor * differentiator.Difference
+ integrationFactor * integrator.Sum;
public PidController(int integrationWindow, float proportionalFactor, float differentiatorFactor, float integrationFactor)
{
differentiator = new Differentiator();
integrator = new Integrator(integrationWindow);
this.proportionalFactor = proportionalFactor;
this.differentiatorFactor = differentiatorFactor;
this.integrationFactor = integrationFactor;
}
}
