set.lua

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