Untitled
unknown
lua
a year ago
4.6 kB
17
Indexable
--!native --!strict type DoublyLinkedNode = { next: DoublyLinkedNode, previous: DoublyLinkedNode, value: unknown } type List<T> = { add: (self: T, element: unknown, index: number?) -> (), remove: (self: T, index: number?) -> boolean, set: (self: T, index: number, element: unknown) -> boolean, get: (self: T, index: number?) -> unknown?, clear: (self: T) -> (), length: (self: T) -> number } type CyclicDoublyLinkedListImplementation<T> = { _first: DoublyLinkedNode?, _length: number } type CyclicDoublyLinkedListMetatable<T> = { __newindex: (self: T, index: number, value: unknown) -> (), __index: (self: T, index: number) -> unknown?, __len: (self: T) -> number, __iter: (self: T) -> () -> (number?, unknown) } local CyclicDoublyLinkedList = {} :: CyclicDoublyLinkedListMetatable<List<unknown> & CyclicDoublyLinkedListImplementation<unknown>> & List<List<unknown> & CyclicDoublyLinkedListImplementation<unknown>> export type CyclicDoublyLinkedList = typeof(setmetatable({} :: List<CyclicDoublyLinkedList>, CyclicDoublyLinkedList :: CyclicDoublyLinkedListMetatable<List<unknown> & CyclicDoublyLinkedListImplementation<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 or index > self._length then return nil end local currentIndex = index local currentNode = node index += 1 node = node.next return currentIndex, currentNode.value 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, index: number, amount: number): DoublyLinkedNode 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 newNode.value = element self._length += 1 local length = self._length if length == 1 then newNode.next = newNode newNode.previous = newNode self._first = newNode return end index = index or length local traversedNode = traverseDoublyLinkedNodes(self._first :: DoublyLinkedNode, convertToRangeIndex(index :: number, 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 first = self._first if not first then return false end local length = self._length self._length -= 1 if length == 1 then self._first = nil return true end index = convertToRangeIndex(index or length, length) local node = traverseDoublyLinkedNodes(first, index :: number, length) node.previous.next = node.next node.next.previous = node.previous if index == 1 then self._first = node.next end 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.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).value end function CyclicDoublyLinkedList.length(self) return self._length end local List = {} List.Linked = {} List.Linked.Cyclic = {} function List.Linked.Cyclic.new(...: unknown): CyclicDoublyLinkedList local self = setmetatable(({ _length = 0 } :: List<CyclicDoublyLinkedList> & CyclicDoublyLinkedListImplementation<unknown>) :: List<CyclicDoublyLinkedList>, CyclicDoublyLinkedList) for _, value in {...} do self:add(value) end return self end return List
Editor is loading...
Leave a Comment