Rustam's techno-feed

A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. As it is fixed-size buffer, when it is full it starts to overwrite the oldest stored items with new ones. The logic is that recent data is more important then old one.

Circular buffer for plocessing n last samples

For example this circular buffer can be used when implementing Oscilloscope or other signal processing software. The software will have 2 working threads in a thread pool.
The first thread will continuously scan some input port and write received data to the buffer. The write event can occur for example every 5ms and every received sample is stored into the buffer.
The second (i.g. UI) thread will poll the buffer when it is needed and when it is ready to draw stored samples. It can occur, for instance, every 33ms to ensure 30fps.

There possible different implementations of the circular buffer depending on requirements. I’ll show my implementation.
In my implementation samples are stored in the buffer one by one, but several latest samples can be handled at the same time starting from the most recent item.

The buffer class is not thread-safe so inter-thread synchronization must be performed on higher levels. I decided to make reader of the buffer data responsible for synchronization.

See source code of generic CircularBuffer class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Avangardo.Signals
{
  /// <summary>
  /// Circular buffer of signal samples.
  /// </summary>
  /// <typeparam name="SampleT">Type of signal sample.</typeparam>
  /// <remarks>Circular buffer stores last <see cref="Count"/> samples of a signal.
  /// It can be used for signal filtering etc.</remarks>
  public sealed class CircularBuffer<SampleT>
  {
    #region Private fields

    /// <summary>
    /// Last samples of a signal.
    /// </summary>
    private SampleT[] samples;

    /// <summary>
    /// Number of samples currently stored in a buffer.
    /// </summary>
    /// <remarks><see cref="Count"/> can not be grater than buffer size.</remarks>
    private int count;

    /// <summary>
    /// Index of buffer item in which next sample will be inserted.
    /// </summary>
    /// <remarks>When <see cref="Index"/> becomes greater than <see cref="Size"/> then
    /// it returns again to 0.</remarks>
    private int index;

    /// <summary>
    /// Size of the buffer.
    /// </summary>
    private int size;

    #endregion

    #region Constructors

    /// <summary>
    /// Creates circular buffer of specified size.
    /// </summary>
    /// <param name="size"></param>
    public CircularBuffer(int size)
    {
      Utils.DebugUtils.CheckParam(size > 0, "Size");
      samples = new SampleT[size];
      this.size = size;
    }

    #endregion

    #region Public properties

    /// <summary>
    /// Gets number of samples currently stored in a buffer.
    /// </summary>
    /// <remarks>If <see cref="Count"/>=<see cref="Size"/> them buffer is full and old
    /// samples will be overriden with new ones.</remarks>
    public int Count
    {
      [DebuggerStepThrough]
      get { return count; }
    }

    /// <summary>
    /// Gets buffer size.
    /// </summary>
    public int Size
    {
      [DebuggerStepThrough]
      get { return size; }
    }

    #endregion

    #region Public methods

    /// <summary>
    /// Puts last sample to buffer.
    /// </summary>
    /// <param name="lastSample"></param>
    public void Put(SampleT lastSample)
    {
      samples[index] = lastSample;
      index++;
      if (count < size)
      {
        count++;
      }
      // Last element in buffer is filled - return to 0th element.
      if (index >= size)
      {
        index = 0;
      }
    }

    /// <summary>
    /// Processes last <see cref="number"/> samples starting from recently added.
    /// </summary>
    /// <param name="number">Number of samples to process.</param>
    /// <param name="handler">Delegate which will process samples.
    /// Parameters for the delegate are: sample and index of sample from the end.
    /// Last added sample has index 0.</param>
    /// </param>
    public void ProcessLastElements(int number, Action<SampleT, int> handler)
    {
      Utils.DebugUtils.CheckParam((number <= size) && (number >= 0), "number");
      Utils.DebugUtils.CheckParamIsNotNull(handler, "handler");
      int c = 0; int i = index;
      if (count < size)
      {
       Utils.DebugUtils.CheckParam(number <= count, "number");
      }

      while (c < number)
      {
        i--;
        if (i < 0)
        {
          i = size - 1;
        }
        handler(samples[i], c);
        c++;
      }
    }

    #endregion

  } // end of class
} // end of namespace

Let’s suppose that we are writing a signal processing application that continuously gets raw acceleration vector from sensor and we need to make data more “smoother”. To achieve this we can calculate Exponential Moving Average of last 5 added samples. The following method will add raw acceleration vector v to the buffer and then it will be replaced with Moving Average of 5 recent samples.

private void calcAvg(ref AccelerationVector v)
{
  buf.Put(v);
  if (buf.Count < 5)
  {
    return;
  }
  double x = 0, y = 0, z = 0;
  double[] coef = new double[] { 0.421, 0.263, 0.158, 0.105, 0.053 }; // sum=1
  buf.ProcessLastElements(5,
    (prev, index) =>
    {
      x += prev.X * coef[index];
      y += prev.Y * coef[index];
      z += prev.Z * coef[index];
    }
  );
  v.X = x; v.Y = y; v.Z = z;
}

coef array stores weights for Exponential Moving Average. The most recent sample (with index 0) will have the highest coefficient (0.421). The sum of all coefficients is equal to 1.

See also WiKi