-- lists consist of three things
-- 1) a base state - agreed on by one or more list holders
-- 2) change sets - incremental list changes (can be rolled forwards or
-- backwards)
-- 3) working state - not saved because it can be so easily calculated
--
-- A separate user list is held - lists index into this


-- TODO: rename player
-- TODO: list trimming

-- notes on list storage:
-- Using names as keys as I do now is atrocious.
-- It prevents insertions (twss) to the middle of the list because then it acts
-- as a side effect onto all the others. ie ABCD -> AXBCD would be phrased as
-- "insert X and shift down B,C,D" which sucks. BCD haven't really been affected
-- (yet) because their relative positions to the others are still intact - ie
-- they are still below A right where they belong. But really X hasn't done
-- anything to affect their relative standing.
--
-- Ok so we can't use names.
--
-- We can't use monotonic integers either because it suffers the same problem.
-- Also consider, randoming in someone to a list of ABCD. Say they roll spot 2.
-- What if someone else runs a separate raid and also randoms someone into slot
-- 2? How do you handle that conflict? Difficult. Also, consider this:
-- List of ABCD on night 1.
-- Admin 1 on night 2 rolls in 30 new people. ABCD's indexes are shuffled to be
-- between 1-35.
-- Admin 2 on night 3 rolls in 5 new ones and people ABCD and PQRST now all have
-- indexes between 1-9.
-- When these two are resolved against one another, do the 1-9 peopole end up on
-- top of the list compared to those other 30? 
--
-- Solution:
-- Need a huge random space with purposely left gaps to leave plenty of room for
-- conflicts.
-- So if ABCD had randomed on a space of say, 10,000 and then were sorted into
-- order, then the next 30 could roll into that same space and have a proper
-- ordering. Then the next 5, etc.
--
-- Handling conflicts:
--
-- Executive decision: random on a range of [0,1], ie math.random
--                     then on an add-to-end event just do last + .1
--                     disallow random after any add-to-end event occurs
--                     because the list either elongates beyond 1 OR becomes
--                     ridiculously bottom heavy, thus meaning that randoms
--                     don't get an even distibution from then on (in fact
--                     they'll end up getting top favor)
--                     * if a stream contains a random-add after an add-to-end
--                     it is declared invalid. tough tits. it's just not a fair
--                     distribution at that point.

-- todo: list-of-lists must not use int indices. those will lead to peril.
bsk.lists = {}
bsk.persons = {}

local raidList = {}
local reserveList = {}
local activeListKey = 1 -- temporary
local personsReverse = {} 

local tinsert = table.insert
local sformat = string.format
local getn = table.getn

function bsk:tcopy(to, from)
  for k,v in pairs(from) do
    if(type(v)=="table") then
      to[k] = {}
      bsk:tcopy(to[k], v);
    else
      to[k] = v;
    end
  end
end
local shallowCopy = function(t)
  local u = { }
  for k, v in pairs(t) do u[k] = v end
  return setmetatable(u, getmetatable(t))
end

-- Debugging {{{
function bsk:PrettyPrintList(listIndex)
    local list = bsk.lists[listIndex]
    bsk:Print("List: " .. list.name .. " (" .. list.time .. ")")
    for i = 1,#list do
        bsk:Print("  " .. i .. " - " .. bsk.persons[list[i]].main)
    end
end
function bsk:PrettyPrintLists()
    for i,_ in pairs(bsk.lists) do
        bsk:PrettyPrintList(i)
    end
end
function bsk:PrintLists()
    bsk:PrintTable(bsk.lists)
end
function bsk:PrintChanges()
    bsk:PrintTable(bsk.db.profile.changes)
end
function bsk:PrintPersons()
    bsk:PrintTable(bsk.persons)
end
function bsk:PrintTable(table, depth)
    depth = depth or ""
    if not table then return end
    for i,v in pairs(table) do 
        if( type(v) == "string" ) then
            self:Print(depth .. i ..  " - " .. v) 
        elseif( type(v) == "number" ) then
            self:Print(depth .. i .. " - " .. tostring(v))
        elseif( type(v) == "table" ) then
            self:Print(depth .. i .." - ") 
            self:PrintTable(v,depth.."   ")
        elseif( type(v) == "boolean" ) then
            self:Print(depth .. i .. " - " .. tostring(v))
        else
            self:Print(depth .. i .. " - not sure how to print type: " .. type(v) )
        end
    end
end

--}}}

function bsk:UpdatePersonsReverse()
    for i,v in pairs(bsk.persons) do
        if i ~= "time" then
            personsReverse[v.main] = i
        end
    end
end

function bsk:CreateWorkingStateFromChanges(changes)
    local personsBase = self.db.profile.persons
    local listBase = self.db.profile.listBase

    -- copy the base to the working state
    wipe(bsk.lists)
    wipe(bsk.persons)
    wipe(personsReverse)

    bsk:tcopy(bsk.lists,listBase)
    bsk:tcopy(bsk.persons,personsBase)

    -- now just go through the changes list applying each
    for i,v in ipairs(changes) do
        bsk:ProcessChange(v)
    end

    -- update the persons reverse list
    bsk:UpdatePersonsReverse()
end

function bsk:CreateChange(change)
    -- sanity
    assert(change)
    assert(change.action)
    assert(change.arg)

    bsk:StartChange(change)
    bsk:CommitChange(change)
end

function bsk:StartChange(change)
    local changes = self.db.profile.changes
    change.time = time()
    local n = getn(changes)
    if n > 0 then
        if changes[n].time >= change.time then
            change.time = changes[n].time + 1
        end
    end
end

function bsk:CommitChange(change)
    local changes = self.db.profile.changes
    tinsert(changes,change)
    -- TODO: broadcast change
end


-- timestamp logic:
-- use time() for comparisons - local clients use date() to make it pretty. only
-- dowisde - we can't have a server timestamp. Which kind of sucks, but it turns
-- out you can change timezones when you enter an instance server, so you really
-- never know what time it is.
-- There's unfortunately no hard-and-proven method for determining the true time
-- difference between local time and server time. You can't just query the two
-- and compare them because your server timezone can change (!) if you go into
-- an instance server with a different timezone. This is apparently a big
-- problem on Oceanic realms.
--
--  Timestamp handling (brainstorming how to deal with drift):
--  (not an issue) if someone sends you time in the future, update your offset so you won't
--  send out events in the "past" to that person
--  (not an issue - using local UTC now) on change-zone-event: check if you've changed timezones - might need update
--  each time you add a change, check the tail of the change list; if this is
--  less than that, you have a problem. Print a message. if this is equal, then
--  that's ok, just bump it by 1 second. This could happen in the case of, say,
--  spam-clicking the undo button or adding names to the list. The recipients
--  should be ok with this since they'll follow the same algorithm. The only
--  real chance for a problem is if two people click within the 1 second window?
--  if someone sends you a past event,
--          it's ok if it's newer than anything in the changes list
--          otherwise ... causality has been violated.
--  Whenever an admin signon event happens, have the admins each perform a
--  timestamp check. Issue warnings for anyone with a clock that's more than
--  X seconds out of sync with the others. Seriously, why isn't NTP a standard
--  setting on all operating systems ...

function bsk:ProcessChange(change)
    if change.action == "AddPerson" then
        bsk:DoAddPerson(change)
    elseif change.action == "CreateList" then
        bsk:DoCreateList(change)
    elseif change.action == "AddPersonToList" then
        bsk:DoAddPersonToList(change)
    elseif change.action == "SuicidePerson" then
        bsk:DoSuicidePerson(change)
    else
        bsk:Print("Unknown message encountered")
        bsk:PrintTable(change)
        assert(false)
    end 
end

-- Action and DoAction defs {{{
--
-- The actual actions for changes start here
--
-- Each action occurs as a pair of functions. The bsk:Action() function is from
-- a list admin's point of view. Each will check for admin status, then create a
-- change bundle, call the handler for that change (ie the DoAction func), and
-- then record/transmist the bundle. These are simple and repetitive functions.
--
-- The bsk:DoAction() function is tasked with executing the bundle and is what
-- non-admins and admins alike will call to transform their working state via a
-- change packet. Each Do() function will accept *only* a change packet, and
-- it's assumed that the change has been vetted elsewhere. These are very blunt
-- routines.
--
-- Note that "undo" has no special voodoo to it. It's basically a change that
-- reverses the prior change on the stack.

-- persons list
function bsk:DoAddPerson(change)
    assert(change)
    assert(change.arg.id)
    local arg = change.arg
    -- require admin
    local persons = bsk.persons
    local name = arg.name
    local id = arg.id
    assert(persons[id]==nil)
    persons[id] = {main=name}
    persons.time=change.time
    personsReverse[name] = id
    return true
end

function bsk:AddPerson(name)
    local persons = bsk.persons
    local guid = UnitGUID(name)
    -- TODO: check guid to be sure it's a player
    if not guid then
        self:Print(sformat("Could not add player %s - they must be in range or group",name))
        return
    end
    local id = string.sub(guid,6) -- skip at least 0x0580 ...
    id = id:gsub("^0*(.*)","%1") -- nom all leading zeroes remaining
    
    if persons[id] and persons[id] ~= name then
        self:Print(sformat("Namechange detected for %s - new is %s, please rename the existing entry", persons[id], name))
        return
    end
    if persons[id] ~= nil then
        self:Print(sformat("%s is already in the persons list; disregarding", name))
        return
    end
    local change = {action="AddPerson",arg={name=name,id=id}}
    if bsk:DoAddPerson(change) then
        bsk:CreateChange(change)
    end
end

function bsk:DoCreateList(change)
    -- TODO: this segment will probably be useful as bsk:SearchForListByName
    local lists = bsk.lists
    for i,v in pairs(lists) do
        if v.name == change.arg.name then
            self:Print(sformat("List %s already exists",v.name))
            return false
        end
    end
    tinsert(lists,{name=change.arg.name,time=change.time})
    return true
end

function bsk:CreateList(name)
    -- require admin
    local change={action="CreateList",arg={name=name}}
    bsk:StartChange(change)
    self:Print("Creating ... " .. name)
    if bsk:DoCreateList(change) then
        bsk:CommitChange(change)
    end
end

-- TODO: break into AddPersonToListEnd and AddPersonToListRandom
function bsk:DoAddPersonToList(change)
    local listIndex = change.arg.listIndex
    local slist = change.arg.slist
    local list = bsk.lists[listIndex]

    if #slist == 1 then -- end of list insertion - just one person
        tinsert(list,slist[1])
        list.time = change.time
    else
        self:Print("Adding to middle of list is not yet supported")
        return false
    end
    return true
end

function bsk:AddPersonToList(name,list)
    -- require admin
    local listIndex = bsk:GetListIndex(list)
    local id = personsReverse[name]
    bsk:Print(sformat("Adding %s (%s) to list %s (%s)", name, id, list, listIndex))
    local slist = {id} -- TODO: support adding to elsewhere besides the end
    local change = {action="AddPersonToList",arg={id=id,listIndex=listIndex,slist=slist}}
    bsk:StartChange(change)
    if bsk:DoAddPersonToList(change) then
        bsk:CommitChange(change)
    end
end

function bsk:DoRemovePerson(change)

    -- return true
end

function bsk:RemovePerson(name)
    -- from both persons and lists
end

function bsk:DoSuicidePerson(change)
    local listIndex = change.arg.listIndex
    local list = bsk.lists[listIndex]
    local slist = shallowCopy(change.arg.list)
    -- the goal here is to rotate the suicide list by 1
    -- then we can just mash it on top of the intersection between the original
    -- list and the working copy
    local stemp = shallowCopy(change.arg.list)
    local temp = table.remove(stemp,1) -- pop
    tinsert(stemp,temp) -- push_back
    --bsk:Print(sformat("Before suicide of %s on list %s",slist[1],list.name))
    --bsk:PrintTable(list)
    for i = 1, #list do
        if list[i] == slist[1] then
            table.remove(slist,1)
            list[i] = stemp[1]
            table.remove(stemp,1)
        end
    end
    list.time=change.time
    --bsk:Print("After")
    --bsk:PrintTable(list)
    return true
end

function bsk:SuicidePerson(name,list)
    -- require admin
    bsk:PopulateRaidList()
    local listIndex = bsk:GetListIndex(list)
    local slist=bsk:GetSuicideList(name,bsk.lists[listIndex])
    local change = {action="SuicidePerson",arg={names=names,list=slist,listIndex=listIndex}}
    bsk:StartChange(change)
    if bsk:DoSuicidePerson(change) then
       bsk:CommitChange(change)
    end
end

function bsk:TrimLists(time)
    if not bsk:CheckListCausality() then
        self:Print("Unable to trim lists due to violated causality")

        return false
    end

    if type(time) ~= "number" then
        time = tonumber(time)
    end

    -- bisect the changes list by "time"
    local before = {}
    for i,v in ipairs(self.db.profile.changes) do
        if v.time <= time then
            tinsert(before,v)
        else
            break
        end
    end

    -- apply first half
    bsk:CreateWorkingStateFromChanges(before)

    -- save this state permanently; trim the changes permanently
    bsk:tcopy(bsk.db.profile.persons,bsk.persons)
    bsk:tcopy(bsk.db.profile.listBase,bsk.lists)
    while bsk.db.profile.changes ~= nil and bsk.db.profile.changes[1] ~= nil and bsk.db.profile.changes[1].time <= time do
        table.remove(bsk.db.profile.changes,1)
    end

    -- using the trimmed list and the new bases, recreate the working state
    bsk:CreateWorkingStateFromChanges(bsk.db.profile.changes)
end

--}}}
-- Higher order actions (ie calls other Doers){{{
function bsk:AddMissingPersons()
    bsk:PopulateRaidList() 
    local t = {}
    for _,v in pairs(bsk.persons) do
        t[v.main] = true
        -- TODO: also add alts here
    end
    for i,_ in pairs(raidList) do
        if t[i] == nil then
            bsk:Print(sformat("Person %s is missing from the persons list - adding",i))
            bsk:AddPerson(i)
        end
    end
    -- TODO: batch into a single op - no need to spam 25 messages in a row
end
function bsk:PopulateListRandom(index)
    -- difference (raid+reserve)^list, then random shuffle that, then add
    bsk:PopulateRaidList()
    local list = bsk.lists[index]

    local t = {}
    --for i = 1,#list do
    --    if not (raidList(list[i]) or reserveList(list[i])) then
    --        tinsert(t,)
    --    end
    --end
end
--}}}

-- "Soft" actions- ie things that cause nonpermanent state {{{

-- reserves
function bsk:AddReserve(name)
    reserveList[name]=true
    -- TODO: communicate to others. don't store this in any way.
end

function bsk:RemoveReserve(name)
    reserveList[name]=false
    -- TODO: communicate to others. don't store this in any way.
end


--function bsk:GetActiveList()
--    return bsk.lists[1] -- todo!
--end

--}}}

-- The following code is from Xinhuan (wowace forum member)
-- Pre-create the unitID strings we will use
local pID = {}
local rID = {}
for i = 1, 4 do
    pID[i] = format("party%d", i)
end
for i = 1, 40 do
    rID[i] = format("raid%d", i)
end
function bsk:PopulateRaidList()
    local inParty = GetNumPartyMembers()
    local inRaid = GetNumRaidMembers()

    wipe(raidList)
    if inRaid > 0 then
        for i = 1, inRaid do
            raidList[UnitName(rID[i])]=true
        end
    elseif inParty > 0 then
        for i = 1, inParty do
            raidList[UnitName(pID[i])]=true
        end
        -- Now add yourself as the last party member
        raidList[UnitName("player")]=true
    else
        -- You're alone
        raidList[UnitName("player")]=true
    end
end

-- undo rules!
-- only the most recent event can be undone
-- ^^^ on a given list?
-- algorithm is easy, given "Suicide A B C"
-- just find A,B,C in the list and replace in order from the s message
-- while undo is allowed *per-list*, certain events in the stream will
-- prevent proper undo, such as add/delete player or add/delete list


function bsk:GetSuicideList(name,list)
    --self:Print("Calculating changeset for "..name.." from list -")
    --self:PrintTable(list)
    local t = {}
    local ret = {}
    local pushing = false
    for i = 1, #list do
        if list[i] == name then
            pushing = true
        end
        if pushing and (raidList[list[i]] or reserveList[list[i]]) then
            tinsert(ret,list[i])
        end
    end
    return ret
end

-- returns true if the events in the list are in time order
function bsk:CheckListCausality()
    local t = nil
    for i,v in ipairs(bsk.db.profile.changes) do
        if t ~= nil then
            if v.time <= t then
                return false
            end
        end
        t = v.time
    end
    return true
end

-- Support functions

function bsk:GetListIndex(name)
    for i,v in pairs(bsk.lists) do
        if v.name == name then
            return i
        end
    end
    assert(false)
end

local shuffleArray = function(array)
    local arrayCount = #array
    for i = arrayCount, 2, -1 do
        local j = math.random(1, i)
        array[i], array[j] = array[j], array[i]
    end
    return array
end