unknown
lua
a month ago
5.2 kB
3
Indexable
Never
```--!native
--!strict

export type Entry<T> = {
value: T,

remove: () -> ()
}

entry: Entry<T>
}

type List<T, V> = {
add: (self: T, element: V, index: number?) -> (),
remove: (self: T, index: number?) -> boolean,
set: (self: T, index: number, element: V) -> boolean,
get: (self: T, index: number?) -> V?,
clear: (self: T) -> (),

length: (self: T) -> number
}

_length: number
}

__newindex: (self: T, index: number, value: V) -> (),
__index: (self: T, index: number) -> V?,
__len: (self: T) -> number,
__iter: (self: T) -> ()  -> (number?, V)
}

-- such a mess because we dont have class-like structure types :/
local CyclicDoublyLinkedList = {} :: List<
List<unknown, unknown> &
unknown
>

))

if type(index) ~= 'number' then
end
self:set(index, value)
end

if type(index) ~= 'number' then
end

return self:get(index)
end

return self:length()
end

local node = self._first
local index = 1

return function()
if not node then
return nil
end

local currentIndex = index
local currentNode = node

index += 1
node = node.next

if node == self._first then
node = nil
end

return currentIndex, currentNode.entry
end
end

local function convertToRangeIndex(index: number, length: number): number
if length == 0 then
return 1
end

index %= length
return index == 0 and length or index
end

local previousDistance = amount - index
local nextDistance = index - 1

if previousDistance < nextDistance then
for _ = 1, previousDistance do
node = node.previous
end
else
for _ = 1, nextDistance do
node = node.next
end
end

return node
end

local newNode = {} :: DoublyLinkedNode<unknown>

self._length += 1
local length = self._length

local index = index or length :: number
newNode.entry = {
value = element,

remove = function()
local nextNode = newNode.next
assert(nextNode.previous == newNode, 'entry already removed')

self._length -= 1

if self._length == 0 then
self._first = nil
return
end

local previousNode = newNode.previous

previousNode.next = nextNode
nextNode.previous = previousNode

if newNode == self._first then
self._first = nextNode
end
end
}

if length == 1 then
newNode.next = newNode
newNode.previous = newNode

self._first = newNode
return
end

newNode.next = traversedNode
newNode.previous = traversedNode.previous

traversedNode.previous.next = newNode
traversedNode.previous = newNode

if index == 1 then
self._first = newNode
end
end

local length = self._length
if length == 0 then
return false
end

index = convertToRangeIndex(index or length, length)
node.entry.remove()

return true
end

local first = self._first
if not first then
return false
end

local node = traverseDoublyLinkedNodes(first, index, self._length)
node.entry.value = element
return true
end

local first = self._first
if not first then
return nil
end

local length = self._length
index = convertToRangeIndex(index or length, length)
return traverseDoublyLinkedNodes(first, index :: number, length).entry.value
end

return self._length
end

local List = {}