view Lists.lua @ 42:72055fc7e115

A lot of work to reign in namespacing (inspiration: WIM)
author John@Doomsday
date Thu, 15 Mar 2012 08:47:41 -0400
parents dc9bfacca238
children 4109683c3172
line wrap: on
line source
-- 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: switch all action functions to use identifiers rather than names
-- TODO: collaborative list trimming
-- TODO: collapse slists into delimited strings for space (premature optimization?)
-- TODO: organize working state data a little more carefully - hard to keep
-- track of all the arrays that are floating out there
-- TODO: players list, drop the "main" sub-entry for people with no alts

-- holy crap long notes {{{
-- 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.
--                     * actually, fuck it. I'll give them an unlock command and
--                     let them screw over their lists :)
--}}}

-- there are some dep chains here. for instance, to have a raidIdP value, a
-- person must have a persons value which leads to a personName2id which
-- leads to a raidIdP
local bsk = bsk
local _G=_G
local table=table
local string=string
local tinsert = table.insert
local sformat = string.format
local getn = table.getn
local wipe = wipe
local pairs=pairs
local ipairs=ipairs
local tonumber=tonumber
local tostring=tostring
local time=time
local date=date
local math=math
local type=type
local assert=assert
local getmetatable=getmetatable
local setmetatable=setmetatable
setfenv(1,bsk)

lists = {}
persons = {}

raidNameP = {} -- "name" is present in raid
raidIdP = {} -- "id" is present in raid
reserveIdP = {} -- "reserve id present"
local personName2id = {} -- given "name" get that person's id


function SelfDestruct()
    lists = {}
    persons = {}
    db.profile.persons = {}
    db.profile.changes = {}
    db.profile.lists = {}
    raidNameP = {}
    raidIdP = {}
    reserveIdP = {}
    personName2id = {}
end
function tcopy(to, from)
  for k,v in pairs(from) do
    if(type(v)=="table") then
      to[k] = {}
      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 PrettyPrintList(listIndex)
    local list = lists[listIndex]
    bsk:Print("List: " .. list.name .. " (" .. listIndex .. ") - last modified " .. date("%m/%d/%y %H:%M:%S", list.time) .. " (",list.time,")" )
    for i = 1,#list do
        bsk:Print("  " .. i .. " - " .. persons[list[i].id].main)
    end
end
function PrettyPrintLists()
    for i,_ in pairs(lists) do
        PrettyPrintList(i)
    end
end
function PrintLists()
    PrintTable(lists)
end
function PrintChanges()
    PrintTable(db.profile.changes)
end
function PrintPersons()
    PrintTable(persons)
end
function PrintAPI(object)
    for i,v in pairs(object) do
        if type(v) == "function" then
            bsk:Print("function "..i.."()")
        end
    end
end
function PrintTable(table, depth)
    depth = depth or ""
    if not table then return end
    if #depth > 3*5 then bsk:Print(depth.."Recursion too deep - stopping"); return end
    for i,v in pairs(table) do 
        if( type(v) == "string" ) then
            bsk:Print(depth .. i ..  " - " .. v) 
        elseif( type(v) == "number" ) then
            bsk:Print(depth .. i .. " - " .. tostring(v))
        elseif( type(v) == "table" ) then
            bsk:Print(depth .. i .." - ") 
            PrintTable(v,depth.."   ")
        elseif( type(v) == "boolean" ) then
            bsk:Print(depth .. i .. " - " .. tostring(v))
        elseif( type(v) == "function" ) then
            bsk:Print(depth .. "function " .. i .. "()")
        else
            bsk:Print(depth .. i .. " - not sure how to print type: " .. type(v) )
        end
    end
end

function PrintRaidAndReserve()
    bsk:Print("RaidNameP")
    PrintTable(raidNameP)
    bsk:Print("RaidIdP")
    PrintTable(raidIdP)
    bsk:Print("ReserveP")
    PrintTable(reserveIdP)
    bsk:Print("personName2id")
    PrintTable(personName2id)
end
--}}}

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

-- Czohange processing {{{
function CreateWorkingStateFromChanges(changes)
    local personsBase = db.profile.persons
    local lists = db.profile.lists

    -- copy the base to the working state
    wipe(lists)
    wipe(persons)
    wipe(personName2id)

    tcopy(lists,lists)
    tcopy(persons,personsBase)

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

    -- update the persons reverse list
    UpdatePersonsReverse()
end

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

    StartChange(change)
    CommitChange(change)
end

function StartChange(change)
    local changes = 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 CommitChange(change)
    local changes = db.profile.changes
    tinsert(changes,change)
    -- TODO: broadcast change
end

function ProcessChange(change)
    if change.action == "AddPerson" then
        DoAddPerson(change)
    elseif change.action == "RenameList" then
        DoRenameList(change)
    elseif change.action == "CreateList" then
        DoCreateList(change)
    elseif change.action == "DeleteList" then
        DoDeleteList(change)
    elseif change.action == "AddToListEnd" then
        DoAddPersonToListEnd(change)
    elseif change.action == "AddToListRand" then
        DoAddPersonToListRandom(change)
    elseif change.action == "RemovePerson" then
        DoRemovePerson(change)
    elseif change.action == "RemovePersonFromList" then
        DoRemovePersonFromList(change)
    elseif change.action == "SuicidePerson" then
        DoSuicidePerson(change)
    else
        bsk:Print("Unknown message encountered")
        PrintTable(change)
        assert(false)
    end 
end

--}}}
--
-- holy crap long winded {{{
-- 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 ...
--}}}

-- Action and DoAction defs {{{
-- Action Discussion {{{
-- The actual actions for changes start here
--
-- Each action occurs as a pair of functions. The 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 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.--}}}
function DoAddPerson(change)--{{{
    assert(change)
    assert(change.arg.id)
    -- require admin
    local persons = persons
    local name = change.arg.name
    local id = change.arg.id
    assert(persons[id]==nil)
    persons[id] = {main=name,class=change.arg.class}
    persons.time=change.time
    personName2id[name] = id
    return true
end--}}}
function AddPerson(name)--{{{
    local persons = persons
    local guid = _G.UnitGUID(name)
    -- TODO: check guid to be sure it's a player
    if not guid then
        bsk:Print(sformat("Could not add player %s - they must be in range or group",name))
        return
    end
    local _,englishClass = _G.UnitClass(name)
    --bsk:Print("Person " .. name .. " is class " .. englishClass)
    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
        bsk:Print(sformat("Namechange detected for %s - new is %s, please rename the existing entry", persons[id].main, name))
        return
    end
    if persons[id] ~= nil then
        bsk:Print(sformat("%s is already in the persons list; disregarding", name))
        return
    end
    local change = {action="AddPerson",arg={name=name,id=id,class=englishClass}}
    if DoAddPerson(change) then
        CreateChange(change)
    end
end--}}}
function DoCreateList(change)--{{{
    --if GetListIndex(change.arg.name) then
    --    bsk:Print(sformat("List %s already exists",v.name))
    --    return false
    --end
    lists[change.arg.id]={name=change.arg.name,time=change.time}
    return true
end--}}}
function CreateList(name)--{{{
    -- require admin
    local change={action="CreateList",arg={name=name}}
    StartChange(change)
    change.arg.id=change.time -- use the creation timestamp as the list's index. it's as unique as anything...
    bsk:Print("Creating ... " .. name)
    if DoCreateList(change) then
        CommitChange(change)
    end
end--}}}
function DoAddPersonToListEnd(change)--{{{
    local list = lists[change.arg.listIndex]
    local index
    if getn(list) > 0 then
        index = list[#list].index + 0.1
    else
        index = 0.1
    end
    local entry = {index=index, id=change.arg.id}

    tinsert(list,entry)
    list.time = change.time
    list.closedRandom = true

    return true
end--}}}
function AddPersonToListEnd(name,listName)--{{{
    -- require admin
    local listIndex = GetListIndex(listName)
    local id = personName2id[name]
    if IdIsInList(id,lists[listIndex]) then
        bsk:Print(sformat("Person %s is already on the reqeuested list",name))
        return false
    end
    bsk:Print(sformat("Adding %s (%s) to list %s (%s)", name, id, listName, listIndex))
    local change = {action="AddToListEnd",arg={id=id,listIndex=listIndex}}
    StartChange(change)
    if DoAddPersonToListEnd(change) then
        CommitChange(change)
    end
end--}}}
function DoAddPersonToListRandom(change)--{{{
    local list = lists[change.arg.listIndex]
    local entry = {index=change.arg.roll, id=change.arg.id}

    tinsert(list,entry)
    table.sort(list,function(a,b) return a.index < b.index end)
    list.time = change.time

    return true
end--}}}
function AddPersonToListRandom(name,listName)--{{{
    -- require admin
    local listIndex = GetListIndex(listName)
    if lists[listIndex].closedRandom then
        bsk:Print("Cannot add person to list by random roll because an add-to-end operation has already occurred")
        return false
    end
    local id = personName2id[name]
    if IdIsInList(id,lists[listIndex]) then
        bsk:Print(sformat("Person %s is already on the reqeuested list",name))
        return false
    end
    local roll = math.random()
    bsk:Print(sformat("Adding %s (%s) to list %s (%s) with roll (%f)", name, id, listName, listIndex, roll))
    local change = {action="AddToListRand",arg={id=id,listIndex=listIndex,roll=roll}}
    StartChange(change)
    if DoAddPersonToListRandom(change) then
        CommitChange(change)
    end
end--}}}
function DoRemovePerson(change)--{{{
    local person = persons[change.arg.id]
    personName2id[person.main] = nil
    persons[change.arg.id] = nil
    persons.time = change.time
    return true
end--}}}
function RemovePerson(name)--{{{
    local id = personName2id[name]
    if not id then
        bsk:Print(sformat("%s is not in the persons list, please check your spelling", name))
        return false
    end
    local listsTheyreOn = {}
    -- check if they're active on any loot list
    for i,v in pairs(lists) do
        if IdIsInList(id,v) then
            tinsert(listsTheyreOn,v.name)
            break
        end
    end
    if getn(listsTheyreOn) > 0 then
        bsk:Print(sformat("Cannot remove person %s because they are on one or more lists (%s)",name,table.concat(listsTheyreOn,", ")))
        return false
    end
    local change = {action="RemovePerson",arg={id=id}}
    StartChange(change)
    if DoRemovePerson(change) then
        CommitChange(change)
    end
end--}}}
function DoSuicidePerson(change)--{{{
    local list = lists[change.arg.listIndex]
    local affected = shallowCopy(change.arg.affect)
    -- 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 replacement = shallowCopy(change.arg.affect)
    local temp = table.remove(replacement,1) -- pop
    tinsert(replacement,temp) -- push_back
    --bsk:Print(sformat("Before suicide of %s on list %s",slist[1],list.name))
    --PrintTable(list)
    for i = 1, #list do
        if list[i].id == affected[1] then
            table.remove(affected,1)
            list[i].id = replacement[1]
            table.remove(replacement,1)
        end
    end
    list.time=change.time
    return true
end--}}}
function SuicidePerson(name,listName)--{{{
    -- require admin
    PopulateRaidList()
    local listIndex = GetListIndex(listName)
    local id = personName2id[name]
    local affect=GetSuicideList(id,lists[listIndex])
    local change = {action="SuicidePerson",arg={affect=affect,listIndex=listIndex}}
    StartChange(change)
    if DoSuicidePerson(change) then
       CommitChange(change)
    end
end--}}}
function DoRenameList(change)--{{{
    lists[change.arg.listIndex].name = change.arg.name
    lists[change.arg.listIndex].time = change.time
    return true
end--}}}
function RenameList(listName,newListName)--{{{
    -- require admin
    local listIndex = GetListIndex(listName)
    local change = {action="RenameList",arg={listIndex=listIndex,name=newListName}}
    StartChange(change)
    if DoRenameList(change) then
       CommitChange(change)
    end
end--}}}
function DoDeleteList(change)--{{{
    lists[change.arg.listIndex] = nil
    return true
end--}}}
function DeleteList(listName)--{{{
    local listIndex = GetListIndex(listName)
    local change = {action="DeleteList",arg={listIndex=listIndex}}
    StartChange(change)
    if DoDeleteList(change) then
       CommitChange(change)
    end
end--}}}
function DoRemovePersonFromList(change)--{{{
    local list = lists[change.arg.listIndex]

    for i,v in ipairs(list) do
        if v.id == change.arg.id then
            table.remove(list,i)
            break
        end
    end
    table.sort(list,function(a,b) return a.index < b.index end)
    list.time = change.time
    return true
end--}}}
function RemovePersonFromList(name,listName)--{{{
    local listIndex = GetListIndex(listName)
    local pid = personName2id[name]
    -- todo: check that they're on the list in the first place
    local change = {action="RemovePersonFromList",arg={id=pid,listIndex=listIndex}}
    StartChange(change)
    if DoRemovePersonFromList(change) then
       CommitChange(change)
    end
end
--}}}
--}}}
-- Higher order actions (ie calls other standard actions){{{

function TrimLists(time)
    if not CheckListCausality() then
        bsk:Print("Unable to trim changelist 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(db.profile.changes) do
        if v.time <= time then
            tinsert(before,v)
        else
            break
        end
    end

    -- apply first half
    CreateWorkingStateFromChanges(before)

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

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

function AddMissingPersons()
    PopulateRaidList() 
    local t = {}
    for id,_ in pairs(persons) do
        t[id] = true
    end
    for name,_ in pairs(raidNameP) do
        if personName2id[name] == nil then
            bsk:Print(sformat("Person %s is missing from the persons list - adding",name))
            AddPerson(name)
        end
    end
    -- TODO: batch into a single op - no need to spam 25 messages in a row
end

function PopulateListRandom(listIndex)
    -- difference (raid+reserve)-list, then random shuffle that, then add
    PopulateRaidList()
    local list = lists[listIndex]

    local t = {} -- after loops, contains intersection of IDs present between raid and reserve
    for i,v in pairs(raidIdP) do
        if v then t[i] = true end 
    end
    for i,v in pairs(reserveIdP) do
        if v then t[i] = true end 
    end

    -- now remove from t all of the people already present on the list
    if list then
        for i = 1,#list do
            if t[list[i].id] then
                t[list[i].id] = false
            end
        end
    end

    -- add all remaining
    for i,v in pairs(t) do
        if v then
            AddPersonToListRandom(persons[i].main,list.name) -- TODO: APTLR keys off of string names. probably need to change this.
        end
    end
end

function NukePerson(name) -- delete from all lists and then from persons
    local pid = personName2id[name]
    for i,v in pairs(lists) do
        RemovePersonFromList(name,v.name)
    end
    RemovePerson(name)
end
--}}}
-- "Soft" actions- ie things that cause nonpermanent state {{{

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

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


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

--}}}

-- The following (adapted) 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] = sformat("party%d", i)
end
for i = 1, 40 do
    rID[i] = sformat("raid%d", i)
end
function PopulateRaidList()
    local inParty = _G.GetNumPartyMembers()
    local inRaid = _G.GetNumRaidMembers()
    local add = function(unitNameArg) 
        local name = _G.UnitName(unitNameArg)
        raidNameP[name]=true
        if personName2id[name] ~= nil then
            raidIdP[personName2id[name]]=true 
        end
    end

    wipe(raidNameP)
    wipe(raidIdP)
    if inRaid > 0 then
        for i = 1, inRaid do
            add(rID[i])
        end
    elseif inParty > 0 then
        for i = 1, inParty do
            add(pID[i])
        end
        -- Now add yourself as the last party member
        add("player")
    else
        -- You're alone
        add("player")
    end
    --PrintTable(raidNameP)
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 GetSuicideList(id,list)
    --bsk:Print("Calculating changeset for "..name.." from list -")
    --PrintTable(list)
    local t = {}
    local ret = {}
    local pushing = false
    for i = 1, #list do
        if list[i].id == id then
            pushing = true
        end
        if pushing and (raidIdP[list[i].id] or reserveIdP[list[i].id]) then
            tinsert(ret,list[i].id)
        end
    end
    --bsk:Print("GSL")
    --PrintTable(ret)
    --bsk:Print("GSL")
    return ret
end

function IdIsInList(id,listRef)
    for i = 1,#listRef do
        if id == listRef[i].id then
            return true
        end
    end
    return false
end

-- returns true if the events in the list are in time order
function CheckListCausality()
    local t = nil
    for i,v in ipairs(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 GetListIndex(name)
    for i,v in pairs(lists) do
        if v.name == name then
            return i
        end
    end
    return nil
end