Circular Buffer in Lua

circular_buffer.lua

-- circular buffer factory for lua


local function rotate_indice(i, n)
    return ((i - 1) % n) + 1
end

local circular_buffer = {}

local function circular_buffer:filled()
    return #(self.history) == self.max_length
end

local function circular_buffer:push(value)
    if self:filled() then
        local value_to_be_removed = self.history[self.oldest]
        self.history[self.oldest] = value
        self.oldest = self.oldest == self.max_length and 1 or self.oldest + 1
    else
        self.history[#(self.history) + 1] = value
    end
end

circular_buffer.metatable = {}

-- positive values index from newest to oldest (starting with 1)
-- negative values index from oldest to newest (starting with -1)
local function circular_buffer.metatable:__index(i)
    local history_length = #(self.history)
    if i == 0 or math.abs(i) > history_length then
        return nil
    elseif i >= 1 then
        local i_rotated = rotate_indice(self.oldest - i, history_length)
        return self.history[i_rotated]
    elseif i <= -1 then
        local i_rotated = rotate_indice(i + 1 + self.oldest, history_length)
        return self.history[i_rotated]
    end
end

local function circular_buffer.metatable:__len()
    return #(self.history)
end

local function circular_buffer.new(max_length)
    if type(max_length) ~= 'number' or max_length <= 1 then
        error("Buffer length must be a positive integer")
    end

    local instance = {
        history = {},
        oldest = 1,
        max_length = max_length,
        push = circular_buffer.push,
        filled = circular_buffer.filled,
    }
    setmetatable(instance, circular_buffer.metatable)
    return instance
end

return circular_buffer

Thanks for the snippet! I had to change calculation a little to make it work though:

-- positive values index from newest to oldest (starting with 1)
-- negative values index from oldest to newest (starting with -1)
local function circular_buffer.metatable:__index(i)
    local history_length = #(self.history)
    if i == 0 or math.abs(i) > history_length then
        return nil
    elseif i >= 1 then
        local i_rotated = rotate_indice(self.oldest - 1 - i, history_length)  # here
        return self.history[i_rotated]
    elseif i <= -1 then
        local i_rotated = rotate_indice(self.oldest - i, history_length)  # and here
        return self.history[i_rotated]
    end
end

Actually I'm using the reverse convention that [1] gives the oldest element and [-1] gives the last because I'm simulating a fixed size queue, but with your convention that would be something like that.

For reference, here the current version of my circular buffer (new_class is just a helper create a callable that will create an instance with metatable):
https://github.com/hsandt/pico-boots/blob/0b4bc3022ac61a726ecf8cd8d868d38acbd013e3/src/engine/core/datastruct.lua

I tested it with unit tests:
https://github.com/hsandt/pico-boots/blob/0b4bc3022ac61a726ecf8cd8d868d38acbd013e3/src/engine/core/datastruct_utest.lua

Would be nice if you could add a license like MIT/BSD in header.