Drafter.RingBuffer (drafter v0.3.2)

A bounded circular buffer backed by an integer-keyed map.

Push and single-element access are O(1); a slice is O(k) in the length requested, without materializing the whole buffer. Once the buffer is full, each push overwrites the oldest entry.

Implements Enumerable, in oldest-to-newest order.

Examples

iex> buffer = Drafter.RingBuffer.new(3)
iex> buffer = Drafter.RingBuffer.push_many(buffer, [1, 2, 3, 4])
iex> Drafter.RingBuffer.to_list(buffer)
[2, 3, 4]
iex> Drafter.RingBuffer.count(buffer)
3
iex> Drafter.RingBuffer.last(buffer)
4
iex> Drafter.RingBuffer.at(buffer, 0)
2
iex> Drafter.RingBuffer.last_n(buffer, 2)
[3, 4]

Summary

Types

t()

Functions

at(buf, index)

The item at index, counting 0 as the oldest, or nil when out of range.

count(ring_buffer)

How many items the buffer currently holds, never more than max_size/1.

empty?(ring_buffer)

Whether the buffer holds no items.

last(buf)

The most recently pushed item, or nil when the buffer is empty.

last_n(buf, n)

The newest n items, oldest first, or all of them when the buffer holds fewer.

max_size(ring_buffer)

The buffer's capacity, as given to new/1 or resize/2.

new(max_size)

An empty buffer holding at most max_size items.

push(buf, item)

Append item, dropping the oldest item once the buffer is full.

push_many(buf, items)

Append every item in items, in order.

resize(buf, new_max)

A buffer with capacity new_max, keeping the newest items that still fit.

slice(buf, offset, length)

length items starting at offset, oldest first.

to_list(buf)

Every item, oldest first.

Types

t()

@type t() :: %Drafter.RingBuffer{
  count: non_neg_integer(),
  max_size: pos_integer(),
  store: %{required(non_neg_integer()) => term()},
  write_pos: non_neg_integer()
}

Functions

at(buf, index)

@spec at(t(), non_neg_integer()) :: term() | nil

The item at index, counting 0 as the oldest, or nil when out of range.

Examples

iex> buf = Drafter.RingBuffer.push_many(Drafter.RingBuffer.new(3), [1, 2, 3, 4])
iex> Drafter.RingBuffer.at(buf, 0)
2
iex> Drafter.RingBuffer.at(buf, 2)
4
iex> Drafter.RingBuffer.at(buf, 3)
nil

count(ring_buffer)

@spec count(t()) :: non_neg_integer()

How many items the buffer currently holds, never more than max_size/1.

Examples

iex> Drafter.RingBuffer.new(2) |> Drafter.RingBuffer.push_many([1, 2, 3]) |> Drafter.RingBuffer.count()
2

empty?(ring_buffer)

@spec empty?(t()) :: boolean()

Whether the buffer holds no items.

Examples

iex> Drafter.RingBuffer.empty?(Drafter.RingBuffer.new(3))
true

iex> Drafter.RingBuffer.new(3) |> Drafter.RingBuffer.push(:a) |> Drafter.RingBuffer.empty?()
false

last(buf)

@spec last(t()) :: term() | nil

The most recently pushed item, or nil when the buffer is empty.

Examples

iex> Drafter.RingBuffer.new(3) |> Drafter.RingBuffer.push_many([1, 2]) |> Drafter.RingBuffer.last()
2

iex> Drafter.RingBuffer.last(Drafter.RingBuffer.new(3))
nil

last_n(buf, n)

@spec last_n(t(), non_neg_integer()) :: [term()]

The newest n items, oldest first, or all of them when the buffer holds fewer.

Examples

iex> buf = Drafter.RingBuffer.push_many(Drafter.RingBuffer.new(5), [1, 2, 3, 4])
iex> Drafter.RingBuffer.last_n(buf, 2)
[3, 4]
iex> Drafter.RingBuffer.last_n(buf, 10)
[1, 2, 3, 4]
iex> Drafter.RingBuffer.last_n(buf, 0)
[]

max_size(ring_buffer)

@spec max_size(t()) :: pos_integer()

The buffer's capacity, as given to new/1 or resize/2.

Examples

iex> Drafter.RingBuffer.new(5) |> Drafter.RingBuffer.max_size()
5

new(max_size)

@spec new(pos_integer()) :: t()

An empty buffer holding at most max_size items.

max_size must be a positive integer; anything else raises FunctionClauseError.

Examples

iex> buf = Drafter.RingBuffer.new(3)
iex> Drafter.RingBuffer.count(buf)
0
iex> Drafter.RingBuffer.max_size(buf)
3

push(buf, item)

@spec push(t(), term()) :: t()

Append item, dropping the oldest item once the buffer is full.

Examples

iex> Drafter.RingBuffer.new(2) |> Drafter.RingBuffer.push(:a) |> Drafter.RingBuffer.push(:b) |> Drafter.RingBuffer.push(:c) |> Drafter.RingBuffer.to_list()
[:b, :c]

push_many(buf, items)

@spec push_many(t(), Enumerable.t()) :: t()

Append every item in items, in order.

Pushing more than max_size items keeps only the last max_size.

Examples

iex> Drafter.RingBuffer.new(3) |> Drafter.RingBuffer.push_many([1, 2, 3, 4]) |> Drafter.RingBuffer.to_list()
[2, 3, 4]

resize(buf, new_max)

@spec resize(t(), pos_integer()) :: t()

A buffer with capacity new_max, keeping the newest items that still fit.

Shrinking discards the oldest items; growing keeps everything.

Examples

iex> buf = Drafter.RingBuffer.push_many(Drafter.RingBuffer.new(5), [1, 2, 3, 4, 5])
iex> Drafter.RingBuffer.resize(buf, 2) |> Drafter.RingBuffer.to_list()
[4, 5]

iex> buf = Drafter.RingBuffer.push_many(Drafter.RingBuffer.new(2), [1, 2])
iex> Drafter.RingBuffer.resize(buf, 4) |> Drafter.RingBuffer.to_list()
[1, 2]

slice(buf, offset, length)

@spec slice(t(), non_neg_integer(), non_neg_integer()) :: [term()]

length items starting at offset, oldest first.

A slice that runs past the end is truncated rather than padded. offset must be non-negative; a negative one raises FunctionClauseError.

Examples

iex> buf = Drafter.RingBuffer.push_many(Drafter.RingBuffer.new(5), [1, 2, 3, 4, 5])
iex> Drafter.RingBuffer.slice(buf, 1, 3)
[2, 3, 4]
iex> Drafter.RingBuffer.slice(buf, 3, 10)
[4, 5]
iex> Drafter.RingBuffer.slice(buf, 0, 0)
[]

to_list(buf)

@spec to_list(t()) :: [term()]

Every item, oldest first.

Examples

iex> Drafter.RingBuffer.new(3) |> Drafter.RingBuffer.push_many([1, 2, 3, 4]) |> Drafter.RingBuffer.to_list()
[2, 3, 4]