Hi all,
I have been making lots of interesting procedural generation gizmos recently. Some of these need more advanced data structures than a simple Lua table access, such as a Queue… or in my case, a Deque. If you have never heard of a deque, it is short for “double-ended queue.” Insertions and deletions from the front and back of the table are completed in constant time O(1).
Here is my implementation for those who are interested:
----------------------------------------------------------------------
-- DEQUE
----------------------------------------------------------------------
local util = {}
util.deque = {}
function util.deque.new()
return { front = 0, back = -1 }
end
function util.deque.is_empty(deque)
return deque.front > deque.back
end
function util.deque.front(deque)
return deque[deque.front]
end
function util.deque.back(deque)
return deque[deque.back]
end
function util.deque.push_front(deque, value)
deque.front = deque.front - 1
deque[deque.front] = value
end
function util.deque.pop_front(deque)
if deque.front <= deque.back then
local result = deque[deque.front]
deque[deque.front] = nil
deque.front = deque.front + 1
return result
end
end
function util.deque.push_back(deque, value)
deque.back = deque.back + 1
deque[deque.back] = value
end
function util.deque.pop_back(deque)
if deque.front <= deque.back then
local result = deque[deque.back]
deque[deque.back] = nil
deque.back = deque.back - 1
return result
end
end
return util
Decided to post the code in case it helps someone in the future. Happy Defolding.
