Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Circular Buffer in 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
@hsandt
Copy link

hsandt commented Jul 25, 2018

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.

@hsandt
Copy link

hsandt commented Jan 27, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment