luau cyclic linked list
unknown
lua
a year ago
5.2 kB
8
Indexable
--!native --!strict export type Entry<T> = { value: T, remove: () -> () } type DoublyLinkedNode<T> = { next: DoublyLinkedNode<T>, previous: DoublyLinkedNode<T>, 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 } type CyclicDoublyLinkedListImplementation<T, V> = { _first: DoublyLinkedNode<T>?, _length: number } type CyclicDoublyLinkedListMetatable<T, V> = { __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> & CyclicDoublyLinkedListImplementation<unknown, unknown>, unknown> & CyclicDoublyLinkedListMetatable<List<unknown, unknown> & CyclicDoublyLinkedListImplementation<unknown, unknown>, unknown > export type CyclicDoublyLinkedList<T> = typeof(setmetatable( {} :: List<CyclicDoublyLinkedList<T>, T>, CyclicDoublyLinkedList :: CyclicDoublyLinkedListMetatable<List<unknown, unknown> & CyclicDoublyLinkedListImplementation<unknown, unknown>, unknown> )) function CyclicDoublyLinkedList.__newindex(self, index, value) if type(index) ~= 'number' then return rawset(CyclicDoublyLinkedList, index, value) end self:set(index, value) end function CyclicDoublyLinkedList.__index(self, index) if type(index) ~= 'number' then return rawget(CyclicDoublyLinkedList, index) end return self:get(index) end function CyclicDoublyLinkedList.__len(self) return self:length() end function CyclicDoublyLinkedList.__iter(self) 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 function traverseDoublyLinkedNodes<T>(node: DoublyLinkedNode<T>, index: number, amount: number): DoublyLinkedNode<T> 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 function CyclicDoublyLinkedList.add(self, element, index) 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 local traversedNode = traverseDoublyLinkedNodes(self._first :: DoublyLinkedNode<unknown>, convertToRangeIndex(index, length), length) newNode.next = traversedNode newNode.previous = traversedNode.previous traversedNode.previous.next = newNode traversedNode.previous = newNode if index == 1 then self._first = newNode end end function CyclicDoublyLinkedList.remove(self, index) local length = self._length if length == 0 then return false end index = convertToRangeIndex(index or length, length) local node = traverseDoublyLinkedNodes(self._first :: DoublyLinkedNode<unknown>, index :: number, length) node.entry.remove() return true end function CyclicDoublyLinkedList.set(self, index, element) 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 function CyclicDoublyLinkedList.get(self, index) 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 function CyclicDoublyLinkedList.length(self) return self._length end local List = {} List.Linked = {} List.Linked.Cyclic = {} function List.Linked.Cyclic.new<T>(...: T): CyclicDoublyLinkedList<T> local self = setmetatable(({ _length = 0 } :: List<CyclicDoublyLinkedList<T>, T> & CyclicDoublyLinkedListImplementation<List<CyclicDoublyLinkedList<T>, T>, T> ) :: List<CyclicDoublyLinkedList<T>, T>, CyclicDoublyLinkedList) for index, element in {...} do self:add(element) end return self end return List
Editor is loading...
Leave a Comment