Skip to content

Circular Buffer

A fixed-capacity buffer that is read oldest first: writes fail when it is full, reads fail when it is empty, and an overwrite drops the oldest item to make room.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: circular_buffer.nomi
//# A circular buffer: a fixed number of slots, read oldest first, where a
//# forced write replaces the oldest item.

/// A buffer of at most `capacity` items, read oldest first. It is a value:
/// each operation returns the buffer after it.
pub opaque struct Buffer<T>
    capacity: Int
    items:    List<T>
end

/// Why an operation cannot be done.
pub enum Error
    Full
    Empty
end

impl Buffer<T>
    /// An empty buffer that holds at most `capacity` items.
    pub fn new(capacity: Int) -> Buffer<T>
        {capacity:, items: []}
    end

    /// `buffer` with `item` after its newest, or `Full` when it holds
    /// `capacity` items already.
    pub fn write(buffer: Buffer<T>, item: T) -> Result<Buffer<T>, Error>
        if Buffer.is_full(buffer) then
            Err(.Full)
        else
            Ok({..buffer, items: [.., item]})
        end
    end

    /// `buffer` with `item` after its newest, dropping the oldest item first
    /// when it is full.
    pub fn overwrite(buffer: Buffer<T>, item: T) -> Buffer<T>
        kept = if Buffer.is_full(buffer) then
            Iter.drop(buffer.items, 1) |> Iter.to_list()
        else
            buffer.items
        end

        {..buffer, items: [..kept, item]}
    end

    /// The oldest item and the buffer without it, or `Empty`.
    pub fn read(buffer: Buffer<T>) -> Result<(T, Buffer<T>), Error>
        case buffer.items
            [oldest, ..rest] -> Ok((oldest, {..buffer, items: rest}))
            []               -> Err(.Empty)
        end
    end

    /// `buffer` with no items, at the same capacity.
    pub fn clear(buffer: Buffer<T>) -> Buffer<T>
        {..buffer, items: []}
    end

    fn is_full(buffer: Buffer<T>) -> Bool
        Iter.count(buffer.items) == buffer.capacity
    end
end

// FILE: circular_buffer_test.nomi
import circular_buffer.Buffer

/// One canonical operation and what it should do: a write that succeeds or
/// fails, a read of a given item or one that fails, a clear, an overwrite.
enum Step
    Write Int
    WriteFails Int
    Read Int
    ReadFails
    Clear
    Overwrite Int
end

/// Runs each step's operation on a buffer of `capacity`, in turn, and
/// returns the steps as they happened. A run that does what every step says
/// returns the steps it was given.
fn replay(capacity: Int, steps: List<Step>) -> List<Step>
    (_buffer, happened) =
        steps
        |> Iter.map_reduce(Buffer.new(capacity), fn buffer, step ->
            case step
                .Write(item) or .WriteFails(item) ->
                    case Buffer.write(buffer, item)
                        Ok(written) -> (written, Step.Write(item))
                        Err(_)      -> (buffer, .WriteFails(item))
                    end

                .Read(_) or .ReadFails ->
                    case Buffer.read(buffer)
                        Ok((item, rest)) -> (rest, .Read(item))
                        Err(_)           -> (buffer, .ReadFails)
                    end

                .Clear ->
                    (Buffer.clear(buffer), .Clear)

                .Overwrite(item) ->
                    (Buffer.overwrite(buffer, item), .Overwrite(item))
            end
        end)

    happened
end

test "circular buffer"
    [
        ("reading empty buffer should fail", 1, [Step.ReadFails]),
        ("can read an item just written",    1, [.Write(1), .Read(1)]),
        ("each item may only be read once",  1, [.Write(1), .Read(1), .ReadFails]),
        (
            "items are read in the order they are written",
            2,
            [.Write(1), .Write(2), .Read(1), .Read(2)],
        ),
        ("full buffer can't be written to", 1, [.Write(1), .WriteFails(2)]),
        (
            "a read frees up capacity for another write",
            1,
            [.Write(1), .Read(1), .Write(2), .Read(2)],
        ),
        (
            "read position is maintained even across multiple writes",
            3,
            [.Write(1), .Write(2), .Read(1), .Write(3), .Read(2), .Read(3)],
        ),
        ("items cleared out of buffer can't be read", 1, [.Write(1), .Clear, .ReadFails]),
        ("clear frees up capacity for another write", 1, [.Write(1), .Clear, .Write(2), .Read(2)]),
        ("clear does nothing on empty buffer",        1, [.Clear, .Write(1), .Read(1)]),
        (
            "overwrite acts like write on non-full buffer",
            2,
            [.Write(1), .Overwrite(2), .Read(1), .Read(2)],
        ),
        (
            "overwrite replaces the oldest item on full buffer",
            2,
            [.Write(1), .Write(2), .Overwrite(3), .Read(2), .Read(3)],
        ),
        (
            "overwrite replaces the oldest item remaining in buffer following a read",
            3,
            [
                .Write(1),
                .Write(2),
                .Write(3),
                .Read(1),
                .Write(4),
                .Overwrite(5),
                .Read(3),
                .Read(4),
                .Read(5),
            ],
        ),
        (
            "initial clear does not affect wrapping around",
            2,
            [
                .Clear,
                .Write(1),
                .Write(2),
                .Overwrite(3),
                .Overwrite(4),
                .Read(3),
                .Read(4),
                .ReadFails,
            ],
        ),
    ]
    |> subtests (description, capacity, steps), description
        assert replay(capacity, steps) == steps
    end
end
  • Buffer<T> is a value, an opaque struct of its capacity and its items oldest first. Each operation returns the buffer after it: write a Result<Buffer<T>, Error>, read a Result<(T, Buffer<T>), Error> with the item and the rest, and clear and overwrite a Buffer<T>, since they cannot fail. There is no array and no read or write position to wrap around: the items are a List, and the ring is what the operations promise, not how the items are stored.
  • The errors are an Error enum, Full and Empty.
  • The operations are functions of impl Buffer<T>, called Buffer.write(buffer, 1) after import circular_buffer.Buffer. Each names the block’s T in its signature and declares no type parameter of its own, so a call takes T from its buffer, or, for Buffer.new(capacity), from the type the result is expected to have. is_full is private to the block.
  • The canonical cases are lists of operations, each with whether it should succeed. The test file turns each into a Step (Write(1), WriteFails(2), Read(1), ReadFails, Clear, Overwrite(3)), and replay runs the steps on a buffer and returns the steps as they happened. A buffer that behaves returns the steps it was given, so each row asserts replay(capacity, steps) == steps, and a failure shows the list with the step that went another way.
  • replay is one Iter.map_reduce whose state is the buffer and whose output is each step as it happened. A failed write or read keeps the buffer as it was.
  • The 14 canonical cases are one subtests table named by the description column. The first row qualifies its first step, Step.Write(1), and the steps after it are bare.