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
endok circular buffer (14 cases)
test result: ok. 14 passed, 0 failed
How it’s written
Section titled “How it’s written”Buffer<T>is a value, an opaque struct of its capacity and its items oldest first. Each operation returns the buffer after it:writeaResult<Buffer<T>, Error>,readaResult<(T, Buffer<T>), Error>with the item and the rest, andclearandoverwriteaBuffer<T>, since they cannot fail. There is no array and no read or write position to wrap around: the items are aList, and the ring is what the operations promise, not how the items are stored.- The errors are an
Errorenum,FullandEmpty. - The operations are functions of
impl Buffer<T>, calledBuffer.write(buffer, 1)afterimport circular_buffer.Buffer. Each names the block’sTin its signature and declares no type parameter of its own, so a call takesTfrom its buffer, or, forBuffer.new(capacity), from the type the result is expected to have.is_fullis 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)), andreplayruns 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 assertsreplay(capacity, steps) == steps, and a failure shows the list with the step that went another way. replayis oneIter.map_reducewhose 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
subteststable named by the description column. The first row qualifies its first step,Step.Write(1), and the steps after it are bare.