Untitled

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