98 lines
1.7 KiB
Lua
98 lines
1.7 KiB
Lua
function deque()
|
|
local cap = 5
|
|
local elems = {}
|
|
for i = 0, cap - 1 do
|
|
elems[i] = nil
|
|
end
|
|
return {
|
|
start = 0,
|
|
size = 0,
|
|
cap = cap,
|
|
elems = elems,
|
|
pprint = pprint,
|
|
pop = pop,
|
|
prepend = prepend,
|
|
append = append,
|
|
popleft = popleft,
|
|
get = get,
|
|
set = set,
|
|
}
|
|
end
|
|
|
|
function pprint(self)
|
|
io.write(self.start .. "->" .. self.size .. ": ")
|
|
local i = self.start
|
|
for i = 0, self.cap - 1 do
|
|
io.write((self.elems[i] or "_") .. " ")
|
|
end
|
|
io.write("\n")
|
|
end
|
|
|
|
local function extend(self)
|
|
local copy = {}
|
|
for i = 0, self.size - 1 do
|
|
copy[i] = self.elems[(self.start + i) % self.size]
|
|
end
|
|
for i = self.size, 2 * self.size - 1 do
|
|
copy[i] = nil
|
|
end
|
|
self.elems = copy
|
|
self.start = 0
|
|
self.cap = self.cap * 2
|
|
end
|
|
|
|
function append(self, n)
|
|
if self.size == self.cap then
|
|
extend(self)
|
|
end
|
|
self.elems[(self.start + self.size) % self.cap] = n
|
|
self.size = self.size + 1
|
|
end
|
|
|
|
function pop(self)
|
|
if self.size > 0 then
|
|
local i = (self.start + self.size - 1) % self.cap
|
|
local v = self.elems[i]
|
|
self.elems[i] = nil
|
|
self.size = self.size - 1
|
|
return v
|
|
else
|
|
return nil
|
|
end
|
|
end
|
|
|
|
function prepend(self, n)
|
|
if self.size == self.cap then
|
|
extend(self)
|
|
end
|
|
self.size = self.size + 1
|
|
self.start = (self.start + self.cap - 1) % self.cap
|
|
self.elems[self.start] = n
|
|
end
|
|
|
|
function popleft(self)
|
|
if self.size > 0 then
|
|
local v = self.elems[self.start]
|
|
self.elems[self.start] = nil
|
|
self.start = (self.start + 1) % self.cap
|
|
self.size = self.size - 1
|
|
return v
|
|
else
|
|
return nil
|
|
end
|
|
end
|
|
|
|
function get(self, i)
|
|
if 0 <= i and i < self.size then
|
|
return self.elems[(self.start + i) % self.cap]
|
|
else
|
|
return nil
|
|
end
|
|
end
|
|
|
|
function set(self, i, n)
|
|
if 0 <= i and i < self.size then
|
|
self.elems[(self.start + i) % self.cap] = n
|
|
end
|
|
end
|