Skip to content

Instantly share code, notes, and snippets.

@airstruck
Created December 17, 2016 10:23
Show Gist options
  • Save airstruck/f9a4cecef9558961daf9932baeca0441 to your computer and use it in GitHub Desktop.
Save airstruck/f9a4cecef9558961daf9932baeca0441 to your computer and use it in GitHub Desktop.
local function check (self)
if not self.isDirty then
return self
end
self.length = 0
local item = self.firstItem
while item do
self.length = self.length + 1
self.items[self.length] = item
item = self.itemAfter[item]
end
self.isDirty = false
return self
end
local function getItems (self)
return check(self).items
end
local function getLength (self)
return check(self).length
end
local function nextItem (items, index)
local item = items[index]
if item then
return index + 1, item
end
end
local function each (self, func, ...)
if not func then
return nextItem, self:getItems(), 1
end
local items = self:getItems()
for i = 1, self.length do
func(items[i], ...)
end
end
local function push (self, item)
self.length = self.length + 1
self.items[self.length] = item
if not self.firstItem then
self.firstItem = item
end
if self.lastItem then
self.itemAfter[self.lastItem] = item
self.itemBefore[item] = self.lastItem
end
self.lastItem = item
self.has[item] = true
end
local function unshift (self, item)
self.isDirty = true
local next = self.firstItem
if next then
self.itemAfter[item] = next
self.itemBefore[next] = item
end
self.firstItem = item
if not self.lastItem then
self.lastItem = item
end
self.has[item] = true
end
local function pop (self)
local item = self.lastItem
self:remove(item)
return item
end
local function shift (self)
local item = self.firstItem
self:remove(item)
return item
end
local function insert (self, item, neighbor, before)
if self.has[item] then
self:remove(item)
end
if not (neighbor and self.has[neighbor]) then
if before then
unshift(self, item)
else
push(self, item)
end
else
if before and self.firstItem == neighbor then
unshift(self, item)
elseif (not before) and self.lastItem == neighbor then
push(self, item)
elseif before then
self.isDirty = true
local prev = self.itemBefore[neighbor]
self.itemAfter[prev] = item
self.itemBefore[item] = prev
self.itemAfter[item] = neighbor
self.itemBefore[neighbor] = item
self.has[item] = true
else
self.isDirty = true
local next = self.itemAfter[neighbor]
self.itemAfter[item] = next
self.itemBefore[next] = item
self.itemAfter[neighbor] = item
self.itemBefore[item] = neighbor
self.has[item] = true
end
end
return self
end
local function remove (self, item)
if not (item and self.has[item]) then
return self
end
local prev, next = self.itemBefore[item], self.itemAfter[item]
if prev then
self.itemAfter[prev] = next
else
self.firstItem = self.itemAfter[item]
end
if next then
self.itemBefore[next] = prev
self.isDirty = true
else
self.lastItem = self.itemBefore[item]
self.length = self.length - 1
end
self.itemAfter[item] = nil
self.itemBefore[item] = nil
self.has[item] = nil
return self
end
return function (items)
local t = {
insert = insert,
remove = remove,
getItems = getItems,
getLength = getLength,
each = each,
push = push,
unshift = unshift,
pop = pop,
shift = shift,
items = items or {},
itemAfter = {},
itemBefore = {},
has = {},
length = 0,
isDirty = false,
firstItem = false,
lastItem = false,
}
for i = 1, #t.items do
insert(t, t.items[i])
end
return t
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment