Mercurial > wow > breuesk

annotate Lists.lua @ 7:241986f7066c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Comments
author John@Doomsday
date Tue, 06 Mar 2012 09:33:04 -0500
parents 6d460ff2135c
children b05fcb225c4a
rev   line source
John@0 1 -- lists consist of three things
John@0 2 -- 1) a base state - agreed on by one or more list holders
John@0 3 -- 2) change sets - incremental list changes (can be rolled forwards or
John@0 4 -- backwards)
John@0 5 -- 3) working state - not saved because it can be so easily calculated
John@0 6 --
John@0 7 -- A separate user list is held - lists index into this
John@0 8
John@0 9
John@0 10 -- TODO: rename player
John@5 11 -- TODO: list trimming
John@0 12
John@4 13 -- notes on list storage:
John@7 14 -- Using names as keys as I do now is atrocious.
John@4 15 -- It prevents insertions (twss) to the middle of the list because then it acts
John@4 16 -- as a side effect onto all the others. ie ABCD -> AXBCD would be phrased as
John@4 17 -- "insert X and shift down B,C,D" which sucks. BCD haven't really been affected
John@4 18 -- (yet) because their relative positions to the others are still intact - ie
John@4 19 -- they are still below A right where they belong. But really X hasn't done
John@4 20 -- anything to affect their relative standing.
John@4 21 --
John@4 22 -- Ok so we can't use names.
John@4 23 --
John@4 24 -- We can't use monotonic integers either because it suffers the same problem.
John@4 25 -- Also consider, randoming in someone to a list of ABCD. Say they roll spot 2.
John@4 26 -- What if someone else runs a separate raid and also randoms someone into slot
John@4 27 -- 2? How do you handle that conflict? Difficult. Also, consider this:
John@4 28 -- List of ABCD on night 1.
John@4 29 -- Admin 1 on night 2 rolls in 30 new people. ABCD's indexes are shuffled to be
John@4 30 -- between 1-35.
John@4 31 -- Admin 2 on night 3 rolls in 5 new ones and people ABCD and PQRST now all have
John@4 32 -- indexes between 1-9.
John@4 33 -- When these two are resolved against one another, do the 1-9 peopole end up on
John@4 34 -- top of the list compared to those other 30?
John@4 35 --
John@4 36 -- Solution:
John@4 37 -- Need a huge random space with purposely left gaps to leave plenty of room for
John@4 38 -- conflicts.
John@4 39 -- So if ABCD had randomed on a space of say, 10,000 and then were sorted into
John@4 40 -- order, then the next 30 could roll into that same space and have a proper
John@4 41 -- ordering. Then the next 5, etc.
John@4 42 --
John@4 43 -- Handling conflicts:
John@4 44 --
John@0 45
John@0 46 bsk.lists = {}
John@0 47 bsk.players = {}
John@0 48
John@0 49 local RaidList = {}
John@0 50 local ReserveList = {}
John@0 51 local activeList = 0 -- temporary
John@0 52
John@0 53 local tinsert = table.insert
John@0 54 local sformat = string.format
John@0 55 local getn = table.getn
John@0 56
John@0 57 function bsk:tcopy(to, from)
John@0 58 for k,v in pairs(from) do
John@0 59 if(type(v)=="table") then
John@0 60 to[k] = {}
John@0 61 bsk:tcopy(to[k], v);
John@0 62 else
John@0 63 to[k] = v;
John@0 64 end
John@0 65 end
John@0 66 end
John@0 67 local shallowCopy = function(t)
John@0 68 local u = { }
John@0 69 for k, v in pairs(t) do u[k] = v end
John@0 70 return setmetatable(u, getmetatable(t))
John@0 71 end
John@0 72
John@1 73 -- Debugging {{{
John@1 74 function bsk:PrintLists()
John@1 75 bsk:PrintTable(bsk.lists)
John@1 76 end
John@1 77 function bsk:PrintChanges()
John@1 78 bsk:PrintTable(bsk.db.profile.changes)
John@1 79 end
John@1 80 function bsk:PrintPlayers()
John@1 81 bsk:PrintTable(bsk.players)
John@1 82 end
John@0 83 function bsk:PrintTable(table, depth)
John@0 84 depth = depth or ""
John@0 85 if not table then return end
John@0 86 for i,v in pairs(table) do
John@0 87 if( type(v) == "string" ) then
John@0 88 self:Print(depth .. i .. " - " .. v)
John@0 89 elseif( type(v) == "number" ) then
John@0 90 self:Print(depth .. i .. " - " .. tostring(v))
John@0 91 elseif( type(v) == "table" ) then
John@0 92 self:Print(depth .. i .." - ")
John@0 93 self:PrintTable(v,depth.." ")
John@0 94 elseif( type(v) == "boolean" ) then
John@0 95 self:Print(depth .. i .. " - " .. tostring(v))
John@0 96 else
John@0 97 self:Print(depth .. i .. " - not sure how to print type: " .. type(v) )
John@0 98 end
John@0 99 end
John@0 100 end
John@0 101
John@0 102 --}}}
John@0 103
John@5 104 function bsk:CreateWorkingStateFromChanges(changes)
John@0 105 local playerBase = self.db.profile.players
John@0 106 local listBase = self.db.profile.listBase
John@0 107
John@0 108 -- copy the base to the working state
John@0 109 wipe(bsk.lists)
John@0 110 wipe(bsk.players)
John@0 111 bsk:tcopy(bsk.lists,listBase)
John@0 112 bsk:tcopy(bsk.players,playerBase)
John@0 113
John@0 114 -- now just go through the changes list applying each
John@5 115 for i,v in ipairs(changes) do
John@0 116 bsk:ProcessChange(v)
John@0 117 end
John@0 118 end
John@0 119
John@0 120 function bsk:CreateChange(change)
John@0 121 -- sanity
John@0 122 assert(change)
John@0 123 assert(change.action)
John@0 124 assert(change.arg)
John@0 125
John@0 126 bsk:StartChange(change)
John@0 127 bsk:CommitChange(change)
John@0 128 end
John@0 129
John@0 130 function bsk:StartChange(change)
John@0 131 local changes = self.db.profile.changes
John@0 132 change.time = time()
John@0 133 local n = getn(changes)
John@0 134 if n > 0 then
John@0 135 if changes[n].time >= change.time then
John@0 136 change.time = changes[n].time + 1
John@0 137 end
John@0 138 end
John@0 139 end
John@0 140
John@0 141 function bsk:CommitChange(change)
John@0 142 local changes = self.db.profile.changes
John@0 143 tinsert(changes,change)
John@0 144 -- TODO: broadcast change
John@0 145 end
John@0 146
John@0 147
John@0 148 -- timestamp logic:
John@0 149 -- use time() for comparisons - local clients use date() to make it pretty. only
John@0 150 -- dowisde - we can't have a server timestamp. Which kind of sucks, but it turns
John@0 151 -- out you can change timezones when you enter an instance server, so you really
John@0 152 -- never know what time it is.
John@0 153 -- There's unfortunately no hard-and-proven method for determining the true time
John@0 154 -- difference between local time and server time. You can't just query the two
John@0 155 -- and compare them because your server timezone can change (!) if you go into
John@0 156 -- an instance server with a different timezone. This is apparently a big
John@0 157 -- problem on Oceanic realms.
John@0 158 --
John@0 159 -- Timestamp handling (brainstorming how to deal with drift):
John@0 160 -- (not an issue) if someone sends you time in the future, update your offset so you won't
John@0 161 -- send out events in the "past" to that person
John@0 162 -- (not an issue - using local UTC now) on change-zone-event: check if you've changed timezones - might need update
John@0 163 -- each time you add a change, check the tail of the change list; if this is
John@0 164 -- less than that, you have a problem. Print a message. if this is equal, then
John@0 165 -- that's ok, just bump it by 1 second. This could happen in the case of, say,
John@0 166 -- spam-clicking the undo button or adding names to the list. The recipients
John@0 167 -- should be ok with this since they'll follow the same algorithm. The only
John@0 168 -- real chance for a problem is if two people click within the 1 second window?
John@0 169 -- if someone sends you a past event,
John@0 170 -- it's ok if it's newer than anything in the changes list
John@0 171 -- otherwise ... causality has been violated.
John@0 172 -- Whenever an admin signon event happens, have the admins each perform a
John@0 173 -- timestamp check. Issue warnings for anyone with a clock that's more than
John@0 174 -- X seconds out of sync with the others. Seriously, why isn't NTP a standard
John@0 175 -- setting on all operating systems ...
John@0 176
John@0 177 function bsk:ProcessChange(change)
John@0 178 if change.action == "AddPlayer" then
John@0 179 bsk:DoAddPlayer(change)
John@0 180 elseif change.action == "CreateList" then
John@0 181 bsk:DoCreateList(change)
John@0 182 elseif change.action == "AddPlayerToList" then
John@0 183 bsk:DoAddPlayerToList(change)
John@0 184 elseif change.action == "SuicidePlayer" then
John@0 185 bsk:DoSuicidePlayer(change)
John@0 186 else
John@0 187 bsk:Print("Unknown message encountered")
John@0 188 bsk:PrintTable(change)
John@0 189 assert(false)
John@0 190 end
John@0 191 end
John@0 192
John@1 193 -- Action and DoAction defs {{{
John@0 194 --
John@0 195 -- The actual actions for changes start here
John@0 196 --
John@0 197 -- Each action occurs as a pair of functions. The bsk:Action() function is from
John@0 198 -- a list admin's point of view. Each will check for admin status, then create a
John@0 199 -- change bundle, call the handler for that change (ie the DoAction func), and
John@0 200 -- then record/transmist the bundle. These are simple and repetitive functions.
John@0 201 --
John@0 202 -- The bsk:DoAction() function is tasked with executing the bundle and is what
John@0 203 -- non-admins and admins alike will call to transform their working state via a
John@0 204 -- change packet. Each Do() function will accept *only* a change packet, and
John@0 205 -- it's assumed that the change has been vetted elsewhere. These are very blunt
John@0 206 -- routines.
John@0 207 --
John@0 208 -- Note that "undo" has no special voodoo to it. It's basically a change that
John@0 209 -- reverses the prior change on the stack.
John@0 210
John@0 211 -- Players list
John@0 212 function bsk:DoAddPlayer(change)
John@0 213 assert(change)
John@0 214 assert(change.arg.guid)
John@0 215 local arg = change.arg
John@0 216 -- require admin
John@0 217 local players = bsk.players
John@0 218 local name = arg.name
John@0 219 local guid = arg.guid
John@0 220 assert(players[guid]==nil)
John@0 221 players[guid] = name
John@0 222 players.time=change.time
John@0 223 return true
John@0 224 end
John@0 225
John@0 226 function bsk:AddPlayer(name)
John@0 227 local players = bsk.players
John@0 228 local guid = UnitGUID(name)
John@0 229 -- TODO: check guid to be sure it's a player
John@0 230 if not guid then
John@0 231 self:Print(sformat("Could not add player %s - they must be in range or group",name))
John@0 232 return
John@0 233 end
John@0 234 if players[guid] and players[guid] ~= name then
John@0 235 self:Print(sformat("Namechange detected for %s - new is %s, please rename the existing entry", players[guid], name))
John@0 236 return
John@0 237 end
John@0 238 if players[guid] ~= nil then
John@0 239 self:Print(sformat("%s is already in the players list; disregarding", name))
John@0 240 return
John@0 241 end
John@0 242 local change = {action="AddPlayer",arg={name=name,guid=guid}}
John@0 243 if bsk:DoAddPlayer(change) then
John@0 244 bsk:CreateChange(change)
John@0 245 end
John@0 246 end
John@0 247
John@0 248 function bsk:DoCreateList(change)
John@0 249 -- TODO: this segment will probably be useful as bsk:SearchForListByName
John@0 250 local lists = bsk.lists
John@0 251 for i,v in pairs(lists) do
John@0 252 if v.name == change.arg.name then
John@0 253 self:Print(sformat("List %s already exists",v.name))
John@0 254 return false
John@0 255 end
John@0 256 end
John@0 257 tinsert(lists,{name=change.arg.name,time=change.time})
John@0 258 return true
John@0 259 end
John@0 260
John@0 261 function bsk:CreateList(name)
John@0 262 -- require admin
John@0 263 local change={action="CreateList",arg={name=name}}
John@0 264 bsk:StartChange(change)
John@0 265 self:Print("Creating ... " .. name)
John@0 266 if bsk:DoCreateList(change) then
John@0 267 bsk:CommitChange(change)
John@0 268 end
John@0 269 end
John@0 270
John@0 271 function bsk:DoAddPlayerToList(change)
John@0 272 local listIndex = change.arg.listIndex
John@0 273 local slist = change.arg.slist
John@0 274 local list = bsk.lists[listIndex]
John@0 275
John@0 276 if #slist == 1 then -- end of list insertion - just one person
John@0 277 tinsert(list,slist[1])
John@0 278 list.time = change.time
John@0 279 else
John@0 280 self:Print("Adding to middle of list is not yet supported")
John@0 281 return false
John@0 282 end
John@0 283 return true
John@0 284 end
John@0 285
John@0 286 function bsk:AddPlayerToList(name,list)
John@0 287 -- require admin
John@0 288 local listIndex = bsk:GetListIndex(list)
John@0 289 local slist = {name} -- TODO: support adding to elsewhere besides the end
John@0 290 local change = {action="AddPlayerToList",arg={name=name,listIndex=listIndex,slist=slist}}
John@0 291 bsk:StartChange(change)
John@0 292 if bsk:DoAddPlayerToList(change) then
John@0 293 bsk:CommitChange(change)
John@0 294 end
John@0 295 end
John@0 296
John@0 297 function bsk:DoRemovePlayer(change)
John@0 298
John@0 299 -- return true
John@0 300 end
John@0 301
John@0 302 function bsk:RemovePlayer(name)
John@0 303 -- from both players and lists
John@0 304 end
John@0 305
John@0 306 function bsk:DoSuicidePlayer(change)
John@0 307 local listIndex = change.arg.listIndex
John@0 308 local list = bsk.lists[listIndex]
John@0 309 local slist = shallowCopy(change.arg.list)
John@0 310 -- the goal here is to rotate the suicide list by 1
John@0 311 -- then we can just mash it on top of the intersection between the original
John@0 312 -- list and the working copy
John@0 313 local stemp = shallowCopy(change.arg.list)
John@0 314 local temp = table.remove(stemp,1) -- pop
John@0 315 tinsert(stemp,temp) -- push_back
John@0 316 --bsk:Print(sformat("Before suicide of %s on list %s",slist[1],list.name))
John@0 317 --bsk:PrintTable(list)
John@0 318 for i = 1, #list do
John@0 319 if list[i] == slist[1] then
John@0 320 table.remove(slist,1)
John@0 321 list[i] = stemp[1]
John@0 322 table.remove(stemp,1)
John@0 323 end
John@0 324 end
John@0 325 list.time=change.time
John@0 326 --bsk:Print("After")
John@0 327 --bsk:PrintTable(list)
John@0 328 return true
John@0 329 end
John@0 330
John@0 331 function bsk:SuicidePlayer(name,list)
John@0 332 -- require admin
John@0 333 bsk:PopulateRaidList()
John@0 334 local listIndex = bsk:GetListIndex(list)
John@1 335 local slist=bsk:GetSuicideList(name,bsk.lists[listIndex])
John@0 336 local change = {action="SuicidePlayer",arg={names=names,list=slist,listIndex=listIndex}}
John@0 337 bsk:StartChange(change)
John@0 338 if bsk:DoSuicidePlayer(change) then
John@0 339 bsk:CommitChange(change)
John@0 340 end
John@0 341 end
John@5 342
John@5 343 function bsk:TrimLists(time)
John@5 344 if not bsk:CheckListCausality() then
John@5 345 self:Print("Unable to trim lists due to violated causality")
John@5 346
John@5 347 return false
John@5 348 end
John@5 349
John@5 350 if type(time) ~= "number" then
John@5 351 time = tonumber(time)
John@5 352 end
John@5 353
John@5 354 -- bisect the changes list by "time"
John@5 355 local before = {}
John@5 356 for i,v in ipairs(self.db.profile.changes) do
John@5 357 if v.time <= time then
John@5 358 tinsert(before,v)
John@5 359 else
John@5 360 break
John@5 361 end
John@5 362 end
John@5 363
John@5 364 -- apply first half
John@5 365 bsk:CreateWorkingStateFromChanges(before)
John@5 366
John@5 367 -- save this state permanently; trim the changes permanently
John@5 368 bsk:tcopy(bsk.db.profile.players,bsk.players)
John@5 369 bsk:tcopy(bsk.db.profile.listBase,bsk.lists)
John@5 370 while bsk.db.profile.changes[1].time <= time do
John@5 371 table.remove(bsk.db.profile.changes,1)
John@5 372 end
John@5 373
John@5 374 -- using the trimmed list and the new bases, recreate the working state
John@5 375 bsk:CreateWorkingStateFromChanges(bsk.db.profile.changes)
John@5 376 end
John@5 377
John@1 378 --}}}
John@1 379 -- Higher order actions (ie calls other Doers){{{
John@1 380 function bsk:AddMissingPlayers()
John@1 381 bsk:PopulateRaidList()
John@1 382 local t = {}
John@1 383 for i,v in pairs(bsk.players) do
John@1 384 t[v] = true
John@1 385 end
John@1 386 for i,v in pairs(RaidList) do
John@2 387 if t[i] == nil then
John@2 388 bsk:Print(sformat("Player %s is missing from the players list - adding",i))
John@2 389 bsk:AddPlayer(i)
John@1 390 end
John@1 391 end
John@1 392 -- TODO: batch into a single op - no need to spam 25 messages in a row
John@1 393 end
John@3 394 function bsk:PopulateListRandom(index)
John@3 395 -- difference (raid+reserve)^list, then random shuffle that, then add
John@3 396 bsk:PopulateRaidList()
John@3 397 local list = bsk.lists[index]
John@3 398
John@3 399 local t = {}
John@3 400 --for i = 1,#list do
John@3 401 -- if not (RaidList(list[i]) or ReserveList(list[i])) then
John@3 402 -- tinsert(t,)
John@3 403 -- end
John@3 404 --end
John@3 405 end
John@1 406 --}}}
John@1 407
John@1 408 -- "Soft" actions- ie things that cause nonpermanent state {{{
John@1 409
John@1 410 -- reserves
John@1 411 function bsk:AddReserve(name)
John@1 412 ReserveList[name]=true
John@1 413 -- TODO: communicate to others. don't store this in any way.
John@1 414 end
John@1 415
John@1 416 function bsk:RemoveReserve(name)
John@1 417 ReserveList[name]=false
John@1 418 -- TODO: communicate to others. don't store this in any way.
John@1 419 end
John@1 420
John@1 421
John@1 422 --function bsk:GetActiveList()
John@1 423 -- return bsk.lists[1] -- todo!
John@1 424 --end
John@1 425
John@1 426 --}}}
John@0 427
John@0 428 -- The following code is from Xinhuan (wowace forum member)
John@0 429 -- Pre-create the unitID strings we will use
John@0 430 local pID = {}
John@0 431 local rID = {}
John@0 432 for i = 1, 4 do
John@0 433 pID[i] = format("party%d", i)
John@0 434 end
John@0 435 for i = 1, 40 do
John@0 436 rID[i] = format("raid%d", i)
John@0 437 end
John@0 438 function bsk:PopulateRaidList()
John@0 439 local inParty = GetNumPartyMembers()
John@0 440 local inRaid = GetNumRaidMembers()
John@0 441
John@0 442 wipe(RaidList)
John@0 443 if inRaid > 0 then
John@0 444 for i = 1, inRaid do
John@0 445 RaidList[UnitName(rID[i])]=true
John@0 446 end
John@0 447 elseif inParty > 0 then
John@0 448 for i = 1, inParty do
John@0 449 RaidList[UnitName(pID[i])]=true
John@0 450 end
John@0 451 -- Now add yourself as the last party member
John@0 452 RaidList[UnitName("player")]=true
John@0 453 else
John@0 454 -- You're alone
John@0 455 RaidList[UnitName("player")]=true
John@0 456 end
John@0 457 end
John@0 458
John@0 459 -- undo rules!
John@0 460 -- only the most recent event can be undone
John@0 461 -- ^^^ on a given list?
John@0 462 -- algorithm is easy, given "Suicide A B C"
John@0 463 -- just find A,B,C in the list and replace in order from the s message
John@0 464 -- while undo is allowed *per-list*, certain events in the stream will
John@0 465 -- prevent proper undo, such as add/delete player or add/delete list
John@0 466
John@0 467
John@1 468 function bsk:GetSuicideList(name,list)
John@1 469 --self:Print("Calculating changeset for "..name.." from list -")
John@1 470 --self:PrintTable(list)
John@1 471 local t = {}
John@1 472 local ret = {}
John@1 473 local pushing = false
John@1 474 for i = 1, #list do
John@1 475 if list[i] == name then
John@1 476 pushing = true
John@1 477 end
John@1 478 if pushing and (RaidList[list[i]] or ReserveList[list[i]]) then
John@1 479 tinsert(ret,list[i])
John@1 480 end
John@1 481 end
John@1 482 return ret
John@0 483 end
John@0 484
John@5 485 -- returns true if the events in the list are in time order
John@5 486 function bsk:CheckListCausality()
John@5 487 local t = nil
John@5 488 for i,v in ipairs(bsk.db.profile.changes) do
John@5 489 if t ~= nil then
John@5 490 if v.time <= t then
John@5 491 return false
John@5 492 end
John@5 493 end
John@5 494 t = v.time
John@5 495 end
John@5 496 return true
John@5 497 end
John@0 498
John@0 499 -- Support functions
John@0 500
John@0 501 function bsk:GetListIndex(name)
John@0 502 for i,v in pairs(bsk.lists) do
John@0 503 if v.name == name then
John@0 504 return i
John@0 505 end
John@0 506 end
John@0 507 assert(false)
John@0 508 end
John@1 509
John@3 510 local shuffleArray = function(array)
John@3 511 local arrayCount = #array
John@3 512 for i = arrayCount, 2, -1 do
John@3 513 local j = math.random(1, i)
John@3 514 array[i], array[j] = array[j], array[i]
John@3 515 end
John@3 516 return array
John@3 517 end
John@3 518