luau cyclic linked list

--!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