local V=script.Parent local F=require(V:WaitForChild("\065\098\115\116\114\097\099\116\076\105\115\116"))local B="\067\097\110\110\111\116 \099\111\110\115\116\114\117\099\116 \076\105\110\107\101\100\076\105\115\116 \102\114\111\109 \116\121\112\101 \037\115\046"local n="\078\111 \102\105\114\115\116 \101\108\101\109\101\110\116 \101\120\105\115\116\115\046"local i="\078\111 \108\097\115\116 \101\108\101\109\101\110\116 \101\120\105\115\116\115\046"local s="\073\110\100\101\120 \'\037\115\' \105\115 \111\117\116 \111\102 \098\111\117\110\100\115\046"local D="\076\097\115\116 \105\110\100\101\120 \105\115 \115\109\097\108\108\101\114 \116\104\097\110 \102\105\114\115\116 \105\110\100\101\120\046"local E=F.new()E.__index=E function E.new(V)local F=setmetatable({},E)F.count=0 if V~=nil then local n=type(V)if n=="\116\097\098\108\101"then if type(V.Enumerator)=="\102\117\110\099\116\105\111\110"then for V,B in V:Enumerator()do F:addNode(B)end else for V,B in ipairs(V)do F:addNode(B)end end else error(string.format(B,n))end end return F end function E.addNode(B,V,F)B.count=B.count+1 if F~=nil then local n={value=V;next=F}if F==B.first then B.first=n else F.previous.next=n end F.previous=n else if B.first==nil then B.first={value=V}B.last=B.first else local F=B.last B.last={value=V;previous=F}F.next=B.last end end end function E.removeNode(F,V)F.count=F.count-1 if V==F.first then F.first=V.next end if V==F.last then F.last=V.previous end if V.previous~=nil then V.previous.next=V.next end if V.next~=nil then V.next.previous=V.previous end end function E.Enumerator(V)local F=0 local B=V.first return function()if B~=nil then F=F+1 local V=B.value B=B.next return F,V end end end function E.Count(V)return V.count end function E.Clear(V)V.first=nil V.last=nil V.count=0 end function E.Remove(F,V)local B=F.first while B~=nil do if B.value==V then F:removeNode(B)return true end B=B.next end return false end function E.RetainAll(F,V)local B=F.first local n=false while B~=nil do if not V:Contains(B.value)then F:removeNode(B)n=true end B=B.next end return n end function E.First(V)if V.first==nil then error(n)end return V.first.value end function E.Get(F,V)if V<1 or V>F.count then error(string.format(s,V))end local B=1 local n=F.first while n~=nil do if B==V then return n.value end B=B+1 n=n.next end end function E.IndexOf(B,V,F)if F==nil then F=1 elseif F<1 or F>B.count then error(string.format(s,F))end if B.count==0 then return 0 end local n=1 local i=B.first while i~=nil do if i.value==V and n>=F then return n end n=n+1 i=i.next end return 0 end function E.Last(V)if V.last==nil then error(i)end return V.last.value end function E.LastIndexOf(F,V)local B=F.count local n=F.last while n~=nil do if n.value==V then return B end B=B-1 n=n.previous end return 0 end function E.Sub(B,V,F)F=F or B.count if V<1 or V>B.count then error(string.format(s,V))end if F<1 or F>B.count then error(string.format(s,F))end if F<V then error(D)end local n=E.new()local i=1 local v=B.first while v~=nil do if i>=V then n:Push(v.value)end if i>=F then break end i=i+1 v=v.next end return n end function E.Delete(F,V)if V<1 or V>F.count then error(string.format(s,V))end local B=1 local n=F.first while n~=nil do if B==V then F:removeNode(n)return true end B=B+1 n=n.next end end function E.Insert(B,V,F)if V==B.count+1 then B:addNode(F)return true end if V<1 or V>B.count then error(string.format(s,V))end local n=1 local i=B.first while i~=nil do if n==V then B:addNode(F,i)return true end n=n+1 i=i.next end end function E.InsertAll(B,V,F)if V==B.count+1 then for V,F in F:Enumerator()do B:addNode(F)end return true end if V<1 or V>B.count then error(string.format(s,V))end local n=1 local i=B.first while i~=nil do if n==V then for V,F in F:Enumerator()do B:addNode(F,i)end return true end n=n+1 i=i.next end end function E.Pop(V)if V.last==nil then error(i)end local F=V.last.value V:removeNode(V.last)return F end function E.Push(F,V)F:addNode(V)return true end E.Add=E.Push function E.Set(B,V,F)if V<1 or V>B.count then error(string.format(s,V))end local n=1 local i=B.first while i~=nil do if n==V then local V=i.value==F i.value=F return not V end n=n+1 i=i.next end end function E.Shift(V)if V.first==nil then error(n)end local F=V.first.value V:removeNode(V.first)return F end function E.Unshift(F,V)F:addNode(V,F.first)return true end return E
--- A doubly-linked @{List} of items.
-- A List implementation that stores items as nodes that point backward and
-- forward to each other for traversal. This provides good insertion, and
-- deletion characteristics as well as access to the beginning and end of the
-- list, but does so at the expense of random access and search complexity.
--
-- Insertion, deletion, and access to the beginning and end are Θ(1). Access
-- elsewhere, and search are Θ(n).
--
-- LinkedList implements all optional @{List} and @{Collection} methods.
--
-- **Extends:** @{AbstractList}
--
-- **Implements:** @{List}, @{Collection}, @{Enumerable}
--
-- @classmod LinkedList

local module = script.Parent
local AbstractList = require(module:WaitForChild("AbstractList"))

local ErrorConstruct = "Cannot construct LinkedList from type %s."
local ErrorFirst = "No first element exists."
local ErrorLast = "No last element exists."
local ErrorBounds = "Index '%s' is out of bounds."
local ErrorOrder = "Last index is smaller than first index."

local LinkedList = AbstractList.new()

LinkedList.__index = LinkedList

--- Creates a new LinkedList.
-- Creates a LinkedList copy of the provided @{Collection} or array-indexed
-- table if one is provided, otherwise creates an empty LinkedList.
--
-- @param collection the @{Collection} or table to copy
-- @return the new LinkedList
-- @static
function LinkedList.new(collection)
	local self = setmetatable({}, LinkedList)
	self.count = 0
	if collection ~= nil then
		local typeCollection = type(collection)
		if typeCollection == "table" then
			if type(collection.Enumerator) == "function" then
				-- If there's an Enumerator, assume it acts as a collection
				for _, value in collection:Enumerator() do
					self:addNode(value)
				end
			else -- Otherwise its just a table (we can't know otherwise)
				for _, value in ipairs(collection) do
					self:addNode(value)
				end
			end
		else
			error(string.format(ErrorConstruct, typeCollection))
		end
	end
	return self
end

--- Adds a new node to the LinkedList.
-- Inserts the node infront of the node provided or at the end of the
-- LinkedList if none is provided.
--
-- @param value the value to add a new node for
-- @param node the node to insert before
-- @access private
function LinkedList:addNode(value, node)
	self.count = self.count + 1
	if node ~= nil then -- If node is provided we add insert at that location
		local new = { value = value, next = node } -- Node now comes after
		if node == self.first then
			self.first = new -- If node was the first, new is now first
		else
			node.previous.next = new
		end
		node.previous = new -- Whatever was before node now points to new
	else -- If node is not provided we add to the end
		if self.first == nil then -- If the list is empty (first not set)
			self.first = { value = value }
			self.last = self.first -- Last and first are the same
		else
			local last = self.last -- Otherwise reference the previous last
			self.last = { value = value, previous = last }
			last.next = self.last -- Point forward from previous last
		end
	end
end

--- Remove a node from the LinkedList.
--
-- @param node the node to remove
-- @access private
function LinkedList:removeNode(node)
	self.count = self.count - 1
	if node == self.first then -- If node is first we must move first
		self.first = node.next -- Nil is okay (nothing there)
	end
	if node == self.last then -- Node could be both first and last
		self.last = node.previous
	end
	if node.previous ~= nil then -- Nil matters (we're going to access members)
		node.previous.next = node.next -- Close the gap left
	end
	if node.next ~= nil then
		node.next.previous = node.previous -- We simply remove list refrences
	end -- The node may be in use (enumeration), and will be GCed later
end

--- Creates an enumerator for the LinkedList.
-- The enumerator can be used directly in a generic for loop similar to pairs
-- or ipairs.
--
-- @return the enumerator generator
-- @from @{Enumerable}
function LinkedList:Enumerator()
	local index = 0
	local node = self.first -- Start at the beginning
	return function() -- We only need the generator (stateful iterator)
		if node ~= nil then -- If node is nil we're done
			index = index + 1
			local value = node.value
			node = node.next
			return index, value
		end
	end
end

--- Gets the number of items in the LinkedList.
--
-- @return the number of items
-- @from @{Collection}
function LinkedList:Count()
	return self.count
end

--- Removes everything from the LinkedList.
--
-- @from @{Collection}
function LinkedList:Clear()
	self.first = nil -- We no longer need references, but we need not destroy
	self.last = nil -- The nodes will only be held if in use (enumeration)
	self.count = 0
end

--- Removes the specified item from the LinkedList.
-- Removes only a single item. If there are multiple of the same item, it
-- removes only the first encountered.
--
-- When an item is removed any others are shifted to fill the gap left at
-- the index of removal.
--
-- @param item the item to remove from the LinkedList
-- @return true if the LinkedList changed as a result, false otherwise
-- @from @{Collection}
function LinkedList:Remove(item)
	local node = self.first
	while node ~= nil do -- There's no next node
		if node.value == item then
			self:removeNode(node)
			return true -- The LinkedList has been changed
		end
		node = node.next
	end
	return false -- Nothing changed
end

--- Removes all items except those provided from the LinkedList.
-- Retains only the items contained in the specified @{Collection}. If there are
-- duplicates they are all kept.
--
-- @param items the @{Collection} of items to retain in this LinkedList
-- @return true if the LinkedList changed as a result, false otherwise
-- @from @{Collection}
function LinkedList:RetainAll(items)
	local node = self.first
	local changed = false -- We can't report a change immediately
	while node ~= nil do -- There's no next node
		if not items:Contains(node.value) then -- If this isn't being retained
			self:removeNode(node)
			changed = true
		end
		node = node.next
	end
	return changed
end

--- Gets the item at the beginning of the LinkedList.
--
-- @return the first item in the LinkedList
-- @raise if the LinkedList is empty
-- @from @{List}
function LinkedList:First()
	if self.first == nil then
		error(ErrorFirst)
	end
	return self.first.value
end

--- Gets the item at the specified index in the LinkedList.
--
-- @param index the index to get
-- @return the item in the LinkedList at the specified index
-- @raise if the index is out of bounds of the LinkedList
-- @from @{List}
function LinkedList:Get(index)
	if index < 1 or index > self.count then
		error(string.format(ErrorBounds, index))
	end
	local currentIndex = 1
	local node = self.first
	while node ~= nil do
		if currentIndex == index then -- We just want to get to the correct node
			return node.value
		end
		currentIndex = currentIndex + 1
		node = node.next
	end
end

--- Determines the index of a specific item in the LinkedList.
-- Starts from a specified index or from the beginning if none is provided.
--
-- @param item the item to locate
-- @param index the index to start looking from
-- @return the index of the item in the LinkedList if found, 0 otherwise
-- @raise if the index is out of bounds of the LinkedList
-- @from @{List}
function LinkedList:IndexOf(item, index)
	if index == nil then
		index = 1 -- If index isn't provided, start at the beginning
	elseif index < 1 or index > self.count then -- If it is, check the bounds
		error(string.format(ErrorBounds, index))
	end
	if self.count == 0 then
		return 0 -- If we're empty, its not here
	end
	local currentIndex = 1
	local node = self.first
	while node ~= nil do -- There's no next node
		if node.value == item and currentIndex >= index then
			return currentIndex
		end
		currentIndex = currentIndex + 1
		node = node.next
	end
	return 0 -- It wasn't here
end

--- Gets the item at the end of the LinkedList.
--
-- @return the last item in the LinkedList
-- @raise if the LinkedList is empty
-- @from @{List}
function LinkedList:Last()
	if self.last == nil then
		error(ErrorLast)
	end
	return self.last.value
end

--- Determines the last index of a specific item in the LinkedList.
-- Only returns the very last occurrence of the item in the LinkedList.
--
-- @param item the item to locate
-- @return the index of the item in the LinkedList if found, 0 otherwise
-- @from @{List}
function LinkedList:LastIndexOf(item)
	local currentIndex = self.count
	local node = self.last
	while node ~= nil do -- There's no previous node
		if node.value == item then
			return currentIndex
		end
		currentIndex = currentIndex - 1
		node = node.previous
	end
	return 0 -- It wasn't here
end

--- Creates a new sub-list of this LinkedList.
-- Creates the list that is the portion of this LinkedList between the
-- specified indices or from the first specified index to the end if only one
-- index is specified.
--
-- @param first the index to start at
-- @param last the index to end at
-- @return the new LinkedList
-- @raise
-- * if the first index is out of bounds
-- * if the last index is out of bounds
-- * if the last index is smaller than the first index
-- @from @{List}
function LinkedList:Sub(first, last)
	last = last or self.count -- If last isn't provided, go to the end
	if first < 1 or first > self.count then
		error(string.format(ErrorBounds, first))
	end
	if last < 1 or last > self.count then
		error(string.format(ErrorBounds, last))
	end
	if last < first then
		error(ErrorOrder)
	end
	local sub = LinkedList.new()
	local index = 1
	local node = self.first
	while node ~= nil do -- There's no next node
		if index >= first then -- Wait until we're at first
			sub:Push(node.value)
		end
		if index >= last then -- If we just added last we're done
			break
		end
		index = index + 1
		node = node.next
	end
	return sub
end

--- Removes the item at the specified index from the LinkedList.
-- Shifts other elements to fill the gap left at the index of removal.
--
-- @param index the index of the item to remove from the LinkedList
-- @return true always since the LinkedList is always changed
-- @raise if the index is out of bounds of the LinkedList
-- @from @{List}
function LinkedList:Delete(index)
	if index < 1 or index > self.count then
		error(string.format(ErrorBounds, index))
	end
	local currentIndex = 1
	local node = self.first
	while node ~= nil do -- There's no next node
		if currentIndex == index then
			self:removeNode(node)
			return true -- The LinkedList changed
		end
		currentIndex = currentIndex + 1
		node = node.next
	end
end

--- Inserts the item into the LinkedList at the specified index.
-- Shifts other elements to make space at the index of insertion.
--
-- @param index the index to insert the item in the LinkedList
-- @param item the item to add
-- @return true always since the LinkedList is always changed
-- @raise if the index is out of bounds of the LinkedList
-- @from @{List}
function LinkedList:Insert(index, item)
	if index == self.count + 1 then -- If we're adding to the end
		self:addNode(item)
		return true -- The LinkedList changed
	end
	if index < 1 or index > self.count then
		error(string.format(ErrorBounds, index))
	end
	local currentIndex = 1
	local node = self.first
	while node ~= nil do -- There's no next node
		if currentIndex == index then
			self:addNode(item, node)
			return true -- The LinkedList changed
		end
		currentIndex = currentIndex + 1
		node = node.next
	end
end

--- Inserts multiple items into the LinkedList at the specified index.
-- Inserts all items from the provided Collection in the order they are
-- enumerated. Shifts other elements to make space at the index of insertion.
--
-- @param index the index to insert the items in the LinkedList
-- @param items the Collection of items to add to this LinkedList
-- @return true always since the LinkedList is always changed
-- @raise if the index is out of bounds of the LinkedList
-- @from @{List}
function LinkedList:InsertAll(index, items)
	if index == self.count + 1 then -- If we're addeing to the end
		for _, value in items:Enumerator() do
			self:addNode(value)
		end
		return true -- The LinkedList changed
	end
	if index < 1 or index > self.count then
		error(string.format(ErrorBounds, index))
	end
	local currentIndex = 1
	local node = self.first
	while node ~= nil do -- There's no next node
		if currentIndex == index then
			for _, value in items:Enumerator() do
				self:addNode(value, node)
			end
			return true -- The LinkedList changed
		end
		currentIndex = currentIndex + 1
		node = node.next
	end
end

--- Gets an item from the end and removes that item from the LinkedList.
--
-- @return the item in the LinkedList
-- @raise if the LinkedList is empty
-- @from @{List}
function LinkedList:Pop()
	if self.last == nil then
		error(ErrorLast)
	end
	local last = self.last.value
	self:removeNode(self.last)
	return last
end

--- Adds an item to the end of the LinkedList.
--
-- @param item the item to add
-- @return true always since the LinkedList is always changed
-- @from @{List}
function LinkedList:Push(item)
	self:addNode(item)
	return true -- The LinkedList changed
end

--- Adds an item to the LinkedList.
--
-- @param item the item to add
-- @return true always since the LinkedList is always changed
-- @function Add
-- @from @{Collection}
LinkedList.Add = LinkedList.Push

--- Sets the element at the specified index.
--
-- @param index the index to set
-- @param	item the item to set at the index
-- @return true if the LinkedList changed as a result, false otherwise
-- @raise if the index is out of bounds of the LinkedList
-- @from @{List}
function LinkedList:Set(index, item)
	if index < 1 or index > self.count then
		error(string.format(ErrorBounds, index))
	end
	local currentIndex = 1
	local node = self.first
	while node ~= nil do -- There's no next node
		if currentIndex == index then
			local same = node.value == item -- Has this element changed?
			node.value = item
			return not same -- If it changed return true
		end
		currentIndex = currentIndex + 1
		node = node.next
	end
end

--- Gets an item from the beginning and removes that item from the LinkedList.
-- Shifts other elements to fill the gap left.
--
-- @return the item in the LinkedList
-- @raise if the LinkedList is empty
-- @from @{List}
function LinkedList:Shift()
	if self.first == nil then
		error(ErrorFirst)
	end
	local first = self.first.value
	self:removeNode(self.first)
	return first
end

--- Adds an item to the beginning of the LinkedList.
-- Shifts other elements to make space.
--
-- @param item the item to add
-- @return true always since the LinkedList is always changed
-- @from @{List}
function LinkedList:Unshift(item)
	self:addNode(item, self.first)
	return true -- The LinkedList changed
end

return LinkedList
