Spell Reviewer
- Joined
- Nov 18, 2012
- Messages
- 1,887
This is a merge of [Lua] - Lightweight Doubly-Linked List and [Lua] Linked List, regarding the further polishment of this resource that me, @Bribe and @Eikonium (mostly us) have discussed and dedicated to.
Lastest version:
Currently, I've witnessed some issues while testing:
When looped with forEach, it looped retrogradely. I guess it must be an issue with the insert function.
Refactoring forEach with a generic for loop is more ideal, since then it would able to to insert/remove nodes inside it. Also with the possibility to loop starting from a node anywhere in the list.
In
Edit: tested with this
Prints: C
F
E
D
The C is a normal behavior though.
Lastest version:
Lua:
--[[
Doubly-Linked List v1.5.4.1 by Wrda, Eikonium and Bribe, with special thanks to Jampion
------------------------------------------------------------------------------
A script that enables linking objects together with "previous" and "next"
syntax.
------------------------------------------------------------------------------
LinkedList API:
LinkedList.create() -> LinkedListHead
- Creates a new LinkedListHead that can have nodes inserted to itself.
list.head -> the head (internal implementation) of the list. [node.head] has the same result.
list.next -> next item in the same list. [list.next] is always the first node of the list.
Doesn't skip the head.
list.prev -> previous item in the same list. [list.prev] is always the last node of the list.
Doesn't skip the head.
list:insert([value : any, after : boolean]) -> LinkedListNode
- Inserts *before* the given LinkedList object unless "after" is true.
- If a value is passed, the system will attach it to the node as a generic "value"
- Returns the inserted node that was added to the list.
for node in LinkedList.loop(start : LinkedList [, finish : LinkedList , backwards : boolean]) do [stuff] end
- Shows how to iterate over all nodes in "list". Inclusive range.
- An example of how to iterate while skipping the first and last nodes of the list:
for node in list.next.next:loop(list.prev.prev) do print(node.value) end
API specific to LinkedListHead:
list.remove(node)
- Removes a node from list.
list.n
- The number of LinkedListNodes in the list.
fromList:merge(intoList : LinkedList [, mergeBefore : boolean])
- Removes all nodes of list "fromList" and adds them to the end of list "intoList" (or
at the beginning, if "mergeBefore" is true).
"fromList" needs to be the linked list head, but "into" can be anywhere in that list.
LinkedListNode API:
node:remove()
- Removes a node from whatever list it is a part of.
node:getNext()
- Gets the next node, ignoring the head.
node:getPrev()
- Gets the previous node, ignoring the head.
node.value
- Whatever value might have been assigned from list:insert([value])
]]
---@class LinkedList : table
---@field head LinkedListHead
---@field next LinkedList
---@field prev LinkedList
---@class LinkedListNode : LinkedList
---@field value any
---@class LinkedListHead : LinkedList
---@field n integer
LinkedList = {}
LinkedList.__index = LinkedList
---Creates a new LinkedList head node.
---@return LinkedListHead new_list_head
function LinkedList.create()
local head = {}
setmetatable(head, LinkedList)
head.next = head
head.prev = head
head.head = head
head.n = 0
return head
end
---Inserts *before* the given head/node, unless "backward" is true.
---@param value? any
---@param insertAfter? boolean
---@return LinkedListNode new_node
function LinkedList:insert(value, insertAfter)
local node = {} ---@type LinkedListNode
setmetatable(node, LinkedList)
local from = insertAfter and self.next or self
from.prev.next = node
node.prev = from.prev
from.prev = node
node.next = from
node.value = value
local head = from.head
node.head = head
head.n = head.n + 1
return node
end
---Removes a node from whatever list it is a part of.
function LinkedList:remove()
self.prev.next = self.next
self.next.prev = self.prev
self.head.n = self.head.n - 1
self:destroy()
end
---Nullify the linked list's inheritance (as a matter of principle).
function LinkedList:destroy()
setmetatable(self, nil)
end
--Gets the next node in the sequence of the list it is in, ignoring the head.
function LinkedList:getNext()
if self.next == self.head then
return self.head.next
end
return self.next
end
--Gets the previous node in the sequence of the list it is in, ignoring the head.
function LinkedList:getPrev()
if self.prev == self.head then
return self.head.prev
end
return self.prev
end
---Merges LinkedListHead "from" to a LinkedList "into"
---@param from LinkedListHead
---@param into LinkedList
---@param mergeBefore? boolean
function LinkedList.merge(from, into, mergeBefore)
local head = into.head
into = mergeBefore and into.next or into
for node in from:loop() do node.head = head end
head.n = head.n + from.n
from.n = 0
from.next.prev = into.prev
into.prev.next = from.next
into.prev = from.prev
from.prev.next = into
--reset the original list to a simple LinkedListHead
from.next = from
from.prev = from
end
---Loop a LinkedList from a starting node/head to a finish node/head in either direction.
---Inclusive range.
---@param start LinkedList
---@param finish? LinkedList
---@param backward? boolean
---@return function
function LinkedList.loop(start, finish, backward)
local head = start.head
if head.n == 0 then return end
local direction = backward and "prev" or "next"
local skip = start ~= head or start == finish
if not finish or finish == head then
return function()
if skip then
skip = nil
else
start = start[direction]
end
return start ~= head and start or nil
end
else
return function()
if start ~= finish or skip then
if skip and skip ~= 1 then
skip = start == finish and 1
else
start = start[direction]
if start == head then
start = start[direction]
end
end
return start
end
end
end
end
--End of LinkedList library
Lua:
do
--[[
Doubly-Linked List v1.0.0.0 by Wrda, Eikonium and Bribe
*****************************************************************************
* A script that allows the possibility to create a sequence of any object *
* linked together. *
*****************************************************************************
------------------------------------------------------------------------------
API:
LinkedList.create(head) -> listHead
- Creates or resets a table as a LinkedList head.
- Allows a user-specified head or generates a new one.
LinkedList.insert(list, node, func) -> listNode
- "node" can be an existing table, or a new table will be created to represent the
node. "list" can either be the head, or any point where you want the node to be
inserted. It will be inserted *after* the given head/node.
- If a func is passed, it will be called with LinkedList.forEach with the node as its
parameter.
- Returns the inserted node that was added to the list (if addition was successful).
LinkedList.remove(list, node) -> boolean
- Removes a node from whatever list it is a part of. A node cannot be a part of
more than one list at a time, so there is no need to pass the containing list as
an argument.
- Returns true if it was sucessful.
LinkedList.forEach(list, func) -> listNode or listHead
- Iterates the given list and calls func(node) on each node that is found in the
list. If no "func" is given, it will try to call the dynamic func. If the "func"
returns "true", the loop will break.
LinkedList.reset(list) -> boolean
- Removes all nodes from the given linked list.
- Returns true if sucessful.
Node API:
readonly node.next -> the next node in the list.
readonly node.prev -> the previous node in the list.
readonly node.head -> the doubly-linked list table.
node.func -> function called when loop(list) is invoked without a second
parameter.
List API:
readonly list.size -> the number of nodes in the list.
]]
---@class LinkedList:table
---@field create function
LinkedList = { __index = function(_, key) return rawget(LinkedList, key) end }
---@class listHead:LinkedList
---@field head listHead
---@field next listNode|listHead
---@field prev listNode|listHead
---@field protected n integer
---@field protected reset function
---@field protected forEach function
---@field insert function
---@class listNode:listHead
---@field remove function
---@field func function
---Creates or resets a table as a LinkedList head.
---@param head? table allows a user-specified head or generates a new one.
---@return listHead
function LinkedList.create(head)
head = head or {} ---@type listHead
setmetatable(head, LinkedList)
head.next = head
head.prev = head
head.head = head
head.n = 0
return head
end
---"node" can be an existing table, or a new table will be created to represent the
---node. "list" can either be the head, or any point where you want the node to be
---inserted. It will be inserted *after* the given head/node.
---
---If a func is passed, it will be called with LinkedList.forEach with the node as its
---parameter.
---Returns the inserted node that was added to the list (if addition was successful)
---@param list listNode|listHead
---@param node? listNode
---@param func? fun(node:listNode):boolean
---@return listNode node
function LinkedList.insert(list, node, func)
if node then
if type(node) == "table" then
if node.head then --A node cannot be added to more than one list and simply
node:remove() --resetting it will cause errors. Remove it first.
end
else
node, func = {}, node --User passed an func but not a node.
end
end
local head = list.head
if head then
node = node or {}
setmetatable(node, LinkedList)
list.next.prev = node
node.next = list.next
list.next = node
node.prev = list
node.head = head
head.n = head.n + 1
node.func = func
return node
end
end
---Removes a node from whatever list it is a part of. A node cannot be a part of
---more than one list at a time, so there is no need to pass the containing list as
---an argument.
---Returns true if removal was sucessful.
---@param node listNode
---@return boolean wasRemoved
function LinkedList.remove(node)
if node then
local head = node.head
if head and head ~= node then
node.prev.next = node.next
node.next.prev = node.prev
node.head = nil
head.n = head.n - 1
return true
end
end
end
---Shows how you can inline this to grant you more flexibility or performance.
---@param head listHead
---@param func fun(node:listNode):boolean
---@return listNode|listHead lastIterated
local function loop(head, func)
local node = head.next
while (node ~= head) do
if func(node) then break end
node = node.next
end
return node
end
---default loop callback
---@param node listNode
---@return boolean breakIfTrue
local function defaultFunc(node) return node.func and node.func(node) end
---Iterates the given list and calls func(node) on each node that is found in the
---list. If no "func" is given, it will try to call the dynamic func. If the "func"
---returns "true", the loop will break.
---@param list listHead
---@param func? fun(node:listNode):boolean
---@return listNode|listHead lastIterated
function LinkedList.forEach(list, func)
if list and list.head then
return loop(list, func or defaultFunc)
end
end
---Removes all nodes from the given linked list.
---Returns true if succesful.
---@param list listHead
---@return boolean wasDestroyed
function LinkedList.reset(list)
if list.head and list.head == list then
list:forEach(function(node) node.head = nil end)
list.next = list
list.prev = list
list.n = 0
return true
end
end
endWhen looped with forEach, it looped retrogradely. I guess it must be an issue with the insert function.
Refactoring forEach with a generic for loop is more ideal, since then it would able to to insert/remove nodes inside it. Also with the possibility to loop starting from a node anywhere in the list.
In
local function defaultFunc(node) return node.func and node.func(node) end, won't node.func always return true if node.func() is too? Or better, any value that isn't nil or false returned from node.func() is going to be true. Am I missing something?Edit: tested with this
Lua:
function test()
local t = CreateTrigger()
TriggerRegisterTimerEventSingle(t, 0.20)
TriggerAddAction(t, function()
try(function()
local l = LinkedList.create()
local a = LinkedList.insert(l, {value = "A"})
local b = LinkedList.insert(l, {value = "B"})
local c = LinkedList.insert(l, {value = "C"}, function(node) print(node.value) end)
LinkedList.forEach(l)
local l2 = LinkedList.create()
local a2 = LinkedList.insert(l2, {value = "D"})
local b2 = LinkedList.insert(l2, {value = "E"})
local c2 = LinkedList.insert(l2, {value = "F"})
LinkedList.forEach(l2, function(node) print(node.value) end)
end)
end)
end
onInit(test)F
E
D
The C is a normal behavior though.
Last edited:
