local m=(require(script.Parent.Parent.Parent.Llama)).List local B=require(script.Parent.Set)local D=(require(script.Parent.Duple)).directSum local X={}local function h(m,B)local D=1 while D<#m and D<#B do if m[D]==B[D]then D=D+1 else return m[D]<B[D]end end if#m>=#B then return m[D]<B[D]else return m[D]<=B[D]end end local function Z(m,B)local D={}for B=1,math.min(B,#m),1 do D[B]=m[B]end return D end local function n(m,B)local D={}for B=B,#m,1 do D[#D+1]=m[B]end end local function V(m,B)if B==nil or#B==0 then return false end local D=math.floor(#B/2)if#B==1 then if m==B[1]then return 1 else return false end end if m<B[D]then return V(m,Z(B,D-1))elseif m>B[D]then return D+V(m,n(B,D+1))else return D end end local function Y(h,Z,n)if#Z~=#h then error("\067\097\114\100\105\110\097\108\105\116\121 \109\105\115\109\097\116\099\104 \098\101\116\119\101\101\110 \112\111\119\101\114 \097\114\114\097\121 \097\110\100 \115\121\109\098\111\108 \115\101\116\033",2)end if h==nil or#h==0 then local m={B.new({});{}}setmetatable(m,X)rawset(m,"\099\111\101\102\102",n)return m end local V=m.sort(D(h,Z),function(m,B)return B>m end)local Y={V[1][2]}local W={V[1][1]}for m=2,#V,1 do if V[m-1][1]~=V[m][1]then Y[#Y+1]=V[m][2]W[#W+1]=V[m][1]else Y[#Y]=Y[#Y]+V[m][2]end end local L={B.new(W),Y}setmetatable(L,X)rawset(L,"\099\111\101\102\102",n)return L end local function W(B,D)return Y(m.copy(D[1]),m.copy(D[2]),B*D.coeff)end local function L(m)local B=0 for D=1,#m[1],1 do B=B+m[2][D]end return B end local function p(B,D)local X=B[1]*D[1]local h={}for m=1,#X,1 do h[m]=0 end local Z=m.concat(B[1],X)local n=m.concat(B[2],h)local V=m.concat(D[1],X)local W=m.concat(D[2],h)return Y(Z,n,B.coeff),Y(V,W,D.coeff)end local function R(m,B)local D=m for B=2,B,1 do D=D*m end return D end local function q(m)local B={}local D={}if m.coeff==0 then return Y({},{},0)end for X=1,#m[2],1 do if m[2][X]~=0 then B[#B+1]=m[2][X]D[#D+1]=m[1][X]end end return Y(D,B,m.coeff)end local function j(B)local D=Y(m.copy(B[1]),m.copy(B[2]),B.coeff)return D end local function e(B,D,X)local h=V(D,B[1])if h==false then return j(B)else local D=m.copy(B[1])D[h]=X return Y(D,m.copy(B[2]),B.coeff)end end local function l(m,B)local D=j(m)local X=1 if m[1]==nil or m[2]==nil then return m.coeff end for B,h in pairs(B)do local Z=V(B,m[1])if Z~=false then X=X*R(h,m[2][Z])D[2][Z]=0 end end D.coeff=X*D.coeff return D end X.__add=function(B,D)local X=q(B)local h=q(D)if X[1]~=h[1]then error("\077\111\110\111\109\105\097\108 \115\121\109\098\111\108 \115\101\116 \109\105\115\109\097\116\099\104\033",2)elseif not m.equals(X[2],h[2])then error("\077\111\110\111\109\105\097\108 \100\101\103\114\101\101 \109\105\115\109\097\116\099\104\033",2)end return Y(B[1],B[2],B.coeff+D.coeff)end X.__mul=function(B,D)return Y(m.concat(B[1],D[1]),m.concat(B[2],D[2]),B.coeff*D.coeff)end X.__unm=function(B)return Y(m.copy(B[1]),m.copy(B[2]),-B.coeff)end X.__sub=function(m,B)return m+-B end X.__tostring=function(m)local B=tostring(m.coeff)for D=1,#m[1],1 do B=B..(tostring(m[1][D])..("\094"..tostring(m[2][D])))end return B end X.__eq=function(B,D)local X=q(B)local h=q(D)return X[1]==h[1]and m.equals(X[2],h[2])end X.__lt=function(B,D)if L(B)~=L(D)then return L(B)<L(D)else if L(B)==0 then return true end local X,Z=p(B,D)return h(m.reverse(X[2]),m.reverse(Z[2]))end end X.__le=function(m,B)return m==B or m<B end return{Monomial=X;new=Y,copy=j,replace=e;evaluate=l,scale=W,simplify=q}
local List = require(script.Parent.Parent.Parent.Llama).List

local Set = require(script.Parent.Set)
local directSum = require(script.Parent.Duple).directSum

local Monomial = {}

local function lexicographicCompare(left, right)
    local i = 1

    while i < #left and i < #right do
        if left[i] == right[i] then
            i = i + 1
        else
            return left[i] < right[i]
        end
    end

    if #left >= #right then
        return left[i] < right[i]
    else
        return left[i] <= right[i]
    end
end

local function subarray(array, index)
    local result = {}

    for i = 1, math.min(index, #array) do
        result[i] = array[i]
    end

    return result
end

local function suparray(array, index)
    local result = {}

    for i = index, #array do
        result[#result+1] = array[i]
    end
end


local function binarySearch(element, array)
    if array == nil or #array == 0 then
        return false
    end

    local checkIndex = math.floor(#array / 2)

    if #array == 1 then
        if element == array[1] then
            return 1
        else
            return false
        end
    end

    if element < array[checkIndex] then
        return binarySearch(element, subarray(array, checkIndex - 1))
    elseif element > array[checkIndex] then
        return checkIndex + binarySearch(element, suparray(array, checkIndex + 1))
    else
        return checkIndex
    end
end

local function monomialFromArrayAndPreSet(preset, array, coeff)
    if #array ~= #preset then
        error("Cardinality mismatch between power array and symbol set!", 2)
    end

    if preset == nil or #preset == 0 then
        local result = { Set.new({}), {} }
        setmetatable(result, Monomial)
        rawset(result, "coeff", coeff)
        return result
    end

    local preresult = List.sort(directSum(preset, array), function(a, b) 
        return b > a
    end)

    local arrayResult = {preresult[1][2]}
    local presetResult = {preresult[1][1]}

    for i = 2, #preresult do
        if preresult[i - 1][1] ~= preresult[i][1] then
            arrayResult[#arrayResult+1] = preresult[i][2]
            presetResult[#presetResult+1] = preresult[i][1]
        else
            arrayResult[#arrayResult] = arrayResult[#arrayResult] + preresult[i][2]
        end
    end

    local result = {Set.new(presetResult), arrayResult}
    setmetatable(result, Monomial)
    rawset(result, "coeff", coeff)

    return result
end

local function monomialScale(c, monomial)
    return monomialFromArrayAndPreSet(List.copy(monomial[1]), List.copy(monomial[2]), c * monomial["coeff"])
end

local function monomialDegree(monomial)
    local result = 0

    for i = 1, #monomial[1] do
        result = result + monomial[2][i]
    end

    return result
end

local function monomialReRep(left, right)
    local symbolSet = left[1] * right[1]

    local zeroArray = {}

    for i = 1, #symbolSet do
        zeroArray[i] = 0
    end

    local leftPreSet = List.concat(left[1], symbolSet)
    local leftArray = List.concat(left[2], zeroArray)
    local rightPreSet = List.concat(right[1], symbolSet)
    local rightArray = List.concat(right[2], zeroArray)

    return monomialFromArrayAndPreSet(leftPreSet, leftArray, left["coeff"]), monomialFromArrayAndPreSet(rightPreSet, rightArray, right["coeff"])
end


local function integerPower(base, exponent)
    local result = base

    for _ = 2, exponent do
        result = result * base
    end

    return result
end

local function monomialSimplify(monomial)
    local exponentArray = {}
    local symbolPreSet = {}

    if monomial["coeff"] == 0 then
        return monomialFromArrayAndPreSet({},{},0)
    end

    for i = 1, #monomial[2] do
        if monomial[2][i] ~= 0 then
            exponentArray[#exponentArray+1] = monomial[2][i]
            symbolPreSet[#symbolPreSet+1] = monomial[1][i]
        end
    end

    return monomialFromArrayAndPreSet(symbolPreSet, exponentArray, monomial["coeff"])
end


local function monomialCopy(monomial)
    local result = monomialFromArrayAndPreSet(List.copy(monomial[1]), List.copy(monomial[2]), monomial["coeff"])

    return result
end

local function monomialReplace(monomial, symbolToReplace, symbol)
    local index = binarySearch(symbolToReplace, monomial[1])

    if index == false then
        return monomialCopy(monomial)
    else
        local result = List.copy(monomial[1])
        result[index] = symbol
        return monomialFromArrayAndPreSet(result, List.copy(monomial[2]), monomial["coeff"])
    end
end

local function monomialEvaluate(monomial, rules)
    local result = monomialCopy(monomial)
    local constant = 1

    if monomial[1] == nil or monomial[2] == nil then
        return monomial["coeff"]
    end

    for key, value in pairs(rules) do
        local index = binarySearch(key, monomial[1])
        if index ~= false then
            constant = constant * integerPower(value, monomial[2][index])
            result[2][index] = 0
        end
    end

    result["coeff"] = constant * result["coeff"]

    return result
end

Monomial.__add = function (left, right)
    local leftSimple = monomialSimplify(left)
    local rightSimple = monomialSimplify(right)

    if leftSimple[1] ~= rightSimple[1] then
        error("Monomial symbol set mismatch!", 2)
    elseif not List.equals(leftSimple[2], rightSimple[2]) then
        error("Monomial degree mismatch!", 2)
    end

    return monomialFromArrayAndPreSet(left[1], left[2], left["coeff"] + right["coeff"])
end

Monomial.__mul = function (left, right)
    return monomialFromArrayAndPreSet(List.concat(left[1], right[1]), List.concat(left[2], right[2]), left["coeff"] * right["coeff"])
end

Monomial.__unm = function (monomial)
    return monomialFromArrayAndPreSet(List.copy(monomial[1]), List.copy(monomial[2]), -monomial["coeff"])
end

Monomial.__sub = function (left, right)
    return left + -right
end

--[=[ unused
Monomial.__len = function (monomial)
    return #monomial[1]
end
]=]

Monomial.__tostring = function (monomial)
    local result = tostring(monomial["coeff"])

    for i = 1, #monomial[1] do
        result = result .. tostring(monomial[1][i]) .. "^" .. tostring(monomial[2][i])
    end

    return result
end

Monomial.__eq = function (left, right)
    local leftSimple = monomialSimplify(left)
    local rightSimple = monomialSimplify(right)

    return leftSimple[1] == rightSimple[1] and List.equals(leftSimple[2], rightSimple[2])
end

Monomial.__lt = function (left, right)
    if monomialDegree(left) ~= monomialDegree(right) then
        return monomialDegree(left) < monomialDegree(right)
    else
        if monomialDegree(left) == 0 then
            return true
        end
        local leftCopy, rightCopy = monomialReRep(left, right)
        return lexicographicCompare(List.reverse(leftCopy[2]), List.reverse(rightCopy[2]))
    end
end

Monomial.__le = function (left, right)
    return left == right or left < right
end

return {
    Monomial = Monomial,
    new = monomialFromArrayAndPreSet,
    copy = monomialCopy,
    replace = monomialReplace,
    evaluate = monomialEvaluate,
    scale = monomialScale,
    simplify = monomialSimplify
}


