---@class linked-table ---@field _left table ---@field _right table local mt = {} mt.__index = mt mt._size = 0 local HEAD = {''} local TAIL = {''} function mt:has(node) return self._left[node] ~= nil end function mt:isValidNode(node) if node == nil or node == HEAD or node == TAIL then return false end return true end function mt:pushAfter(node, afterWho) if not self:isValidNode(node) then return false end if self:has(node) then return false end local right = self._right[afterWho] if not right then return false end self._right[afterWho] = node self._right[node] = right self._left[right] = node self._left[node] = afterWho self._size = self._size + 1 return true end function mt:pushBefore(node, beforeWho) if node == nil then return false end local left = self._left[beforeWho] if not left then return false end return self:pushAfter(node, left) end function mt:pop(node) if not self:isValidNode(node) then return false end local left = self._left[node] if not left then return false end local right = self._right[node] self._right[left] = right self._left[right] = left self._right[node] = nil self._left[node] = nil self._size = self._size - 1 return true end function mt:pushHead(node) return self:pushAfter(node, HEAD) end function mt:pushTail(node) return self:pushBefore(node, TAIL) end function mt:getAfter(node) if node == nil then node = HEAD end local right = self._right[node] if right == TAIL then return nil end return right end function mt:getHead() return self:getAfter(HEAD) end function mt:getBefore(node) if node == nil then node = TAIL end local left = self._left[node] if left == HEAD then return nil end return left end function mt:getTail() return self:getBefore(TAIL) end function mt:popHead() return self:pop(self:getHead()) end function mt:popTail() return self:pop(self:getTail()) end function mt:replace(old, new) if not self:isValidNode(old) or not self:isValidNode(new) then return false end local left = self._left[old] if not left then return false end local right = self._right[old] self._right[left] = new self._right[new] = right self._left[right] = new self._left[new] = left self._right[old] = nil self._left[old] = nil return true end function mt:getSize() return self._size end function mt:pairs(start, revert) if revert then if start == nil then start = self._left[TAIL] end local next = start return function () local current = next if current == HEAD then return nil end next = self._left[current] return current end else if start == nil then start = self._right[HEAD] end local next = start return function () local current = next if current == TAIL then return nil end next = self._right[current] return current end end end function mt:dump(start, revert) local t = {} for node in self:pairs(start, revert) do t[#t+1] = tostring(node) end return table.concat(t, ' ') end function mt:reset() self._left = { [TAIL] = HEAD } self._right = { [HEAD] = TAIL } self._size = 0 end return function () local self = setmetatable({}, mt) self:reset() return self end