Data preparation

[Rainrider]

Hello,

i'm working on a library for raid encounter/dungeon related achievements. The idea is to be able to get the achievements for a given encounter by the encounterID (as by ENCOUNTER_START) or the mapID (as by GetCurrentMapAreaID()).

I'm pulling the data through the encounter journal and the achievements API and currently the raw data has the following format (for now raid data only):

[6] = {
    {
        {
            ["map"] = 1026,
            ["name"] = "Hellfire Assault",
            ["category"] = 15231,
            ["encounter"] = 1426,
            ["achievements"] = {
            },
            ["instance"] = 669,
        }, -- [1]
        {
            ["map"] = 1026,
            ["name"] = "Iron Reaver",
            ["category"] = 15231,
            ["encounter"] = 1425,
            ["achievements"] = {
            },
            ["instance"] = 669,
        }, -- [2]
    },
},

The nesting is by game expansion (6 is for Warlords of Draenor), then instance, then encounter. I keep it structured like that so that the boss and instance order are preserved. I think that way it would be easier to keep it in source version control and verify the data by a human.

However this presents look-up speed problems. So the question is how I should prepare the data for further use based on the above mentioned use scenarios while still being able to meaningfully keep the whole under version control (the preparation output should always have the same data order)?

[MunkDev]

Instead of using integers as table keys, use the names or encounter IDs. Table lookup by using keys instead of iteration is extremely fast, comparatively. Now, I'm not sure about the confinements of the data you're working with, but remember to utilize the keys in a table as much as you can. If you have a function that returns the name of the instance, it will be much faster to get the instance name and use that key in the table to get your data instead of iterating across nested tables to find the encounter you're looking for.

Here's an example:

[6] = {
    ["Hellfire Citadel"] = {
        ["Info"] = {
            ["map"] = 1026,
            ["instance"] = 669,
            ["category"] = 15231,
        },
        ["Hellfire Assault"] = {
            ["encounter"] = 1426,
            ["achievements"] = {
            },
        },
        ["Iron Reaver"] = {
            ["encounter"] = 1425,
            ["achievements"] = {
            },
        },
    },
},
 
local raid = data[raidID]
local map = raid and raid.Info.map
local encounter = raid and raid[encounterID]
local achievements = encounter and encounter.achievements

[Rainrider]

This would present a problem with version control as Lua does not guarantee the keys order for associative arrays. A diff would show a lot of changes when someone re-generates the data, even without any new data at all.

I think it would be possible to parse the file containing the data and write the prepared version to a new file as this would keep the relative order. But I don't know how to do that as I suppose I will be regex heavy, which is not exactly my strong side.

As for the structure of the prepared data, I share your opinion. For my current use scenario it could be compressed to just:

[1026] = {
    ["instance"] = 669,
    [1426] = {}, -- Hellfire Assault
    [1425] = {}, -- Iron Reaver
}

as I don't need the category once I populate the achievement tables (which I can do on the raw data).

So, if processing it on the file level is the recommended way here, I need something that could produce the above table format while maintaining the same keys order.

[Banknorris]

The solution I use for this "problem" (most of times it happens because I want to open a saved variables file in a text editor and find table keys ordered) is to put those keys nested into array indexes. So instead of:

table = {
      ["map"] = 1026,
      ["name"] = "Hellfire Assault",
      ["category"] = 15231,
      ["encounter"] = 1426,
      ["achievements"] = {},
      ["instance"] = 669,
}

you would have:

table = {
      [1] = {
              ["map"] = 1026,
          },
      [2] = {
              ["name"] = "Hellfire Assault",
          },
      [3] = {
              ["category"] = 15231,
          },
      [4] = {
              ["encounter"] = 1426,
          },
      [5] = {
              ["achievements"] = {},
          },
      [6] = {
              ["instance"] = 669,
          },
}

The problem is that you need to use things like table[3]["category"] instead of table["category"]. You can use metamethods to hide the key index. I personally don't do this but it is possible.

--put all possible keys in this list
local key_index = {["map"]=1, ["name"]=2, ["category"]=3, ["encounter"]=4, ["achievements"]=5, ["instance"]=6}
 
local mt = {["__index"]    = function(t,k)   return rawget(t,key_index[k]) [k]     end,
            ["__newindex"] = function(t,k,v) return rawset(t,key_index[k],{[k]=v}) end}
 
local table = {
            {["map"] = 1026},
            {["name"] = "Hellfire Assault"}
        }
--without metamethods
print(table["name"]) --nil (error)
print(table[2]["name"]) --"Hellfire Assault"
 
setmetatable(table,mt) --now you can omite the key index when accessing data
 
print(table["name"]) --"Hellfire Assault", this is actually table[2]["name"]
 
table["category"] = 15231
print(table["category"]) --15231, this is actually table[3]["category"]

[Rainrider]

This is not a solution to my problem. Firstly you add a further nesting, which means one more table look-up and secondly you add two further function calls through the metatables. I want to go in the opposite direction.

I currently have a data extraction addon, that generates the raw data and a library in the planning which will use the prepared data. I need a tool to parse the raw data and generate the prepared one so that it is fast to access and it keeps the relative order of the raw set (meaning the instance order and the encounter order should be preserved).

I'd appreciate it if someone shares their experience and points me to a proper approach or even share their tools for that. I will share the extraction addon once I verify its results (which will be by the end of the week I hope).

[semlar]

You haven't mentioned how you're exporting this data from the game, but the code from your first post is presumably from a saved variables file because of the way it's commented.

You will not be able to write an associative array to your saved variables in a way that maintains the order of your keys, but you can create a text box in-game that you can copy your database out of and format that however you want.

Since associative arrays inherently have no order, you'll need to index your keys with a second table if you want to be able to arrange them in a specific way for your output.

From your example earlier:

[1026] = {
    ["instance"] = 669,
    [1426] = {}, -- Hellfire Assault
    [1425] = {}, -- Iron Reaver
}

Would have its order stored in a second table which would be used to sort the keys when you're generating your output for the text box:

[1026] = {
    [1] = 1426, -- Hellfire Assault
    [2] = 1425, -- Iron Reaver
}

This can also be done in the same table, provided you do it in a way that doesn't cause conflicts:

[1026] = {
    ['instance'] = 669,
    ['1426'] = {}, -- Hellfire Assault
    ['1425'] = {}, -- Iron Reaver
    [1] = '1426', -- Hellfire Assault
    [2] = '1425', -- Iron Reaver
}

[MunkDev]

Accurately reproducing the order of an associative array can be done by using a custom pairs function that sorts the table keys before returning the key and value to you. You can use this function to move the keys into their respective table as a value and then append the output of the data with tinsert. I'm dumping all my table shenanigans here in case you have need of the other stuff too:

---------------------------------------------------------------
-- Table.lua: Extra table functions for various uses
---------------------------------------------------------------
-- These table functions are used to perform special operations
-- that are not natively supported by the Lua standard library.
---------------------------------------------------------------
local _, db = ...
local Table = {}
---------------------------------------------------------------
db.Table = Table
---------------------------------------------------------------
---------------------------------------------------------------
-- Copy: Recursive table duplicator, creates a deep copy
---------------------------------------------------------------
Table.Copy = function(src)
    local srcType = type(src)
    local copy
    if srcType == "table" then
        copy = {}
        for key, value in next, src, nil do
            copy[Copy(key)] = Copy(value)
        end
        setmetatable(copy, Copy(getmetatable(src)))
    end
    return copy or src
end
---------------------------------------------------------------
---------------------------------------------------------------
-- Flip: Flips the table associations. (only for unique values)
---------------------------------------------------------------
Table.Flip = function(src)
    local srcType = type(src)
    local copy
    if srcType == "table" then
        copy = {}
        for key, value in pairs(src) do
            if not copy[value] then
                copy[value] = key
            else
                return src
            end
        end
    end
    return copy or src
end
---------------------------------------------------------------
---------------------------------------------------------------
-- Compare: Recursive table comparator, checks if identical
---------------------------------------------------------------
Table.Compare = function(t1, t2)
    if t1 == t2 then
        return true
    elseif t1 and not t2 or t2 and not t1 then
        return false
    end
    if type(t1) ~= "table" then
        return false
    end
    local mt1, mt2 = getmetatable(t1), getmetatable(t2)
    if not Compare(mt1,mt2) then
        return false
    end
    for k1, v1 in pairs(t1) do
        local v2 = t2[k1]
        if not Compare(v1,v2) then
            return false
        end
    end
    for k2, v2 in pairs(t2) do
        local v1 = t1[k2]
        if not Compare(v1,v2) then
            return false
        end
    end
    return true
end
---------------------------------------------------------------
---------------------------------------------------------------
-- PairsByKeys: Sort by non-numeric key, handy for string keys
-- Accurately reproduces the order of an associative array.
---------------------------------------------------------------
Table.PairsByKeys = function(t, f)
    local a = {}
    for n in pairs(t) do tinsert(a, n) end
    table.sort(a, f)
    local i = 0      -- iterator variable
    local function iter()   -- iterator function
        i = i + 1
        if a[i] == nil then return nil
        else return a[i], t[a[i]]
        end
    end
    return iter
end
---------------------------------------------------------------

[Resike]

Here is a bit better solution for your last string table iteration:

local function spairs(t, order)
    local keys = { }
    for k in pairs(t) do
        keys[#keys + 1] = k
    end
    if order then
        table.sort(keys, function(a, b)
            return order(t, a, b)
        end)
    else
        table.sort(keys)
    end
    local i = 0
    return function()
        i = i + 1
        if keys[i] then
            return keys[i], t[keys[i]]
        end
    end
end

You can use it the same way as pairs or ipairs.

[Rainrider]

The extraction addon can be found under https://github.com/Rainrider/ExtractAchievements

There are still some edge cases I have to figure out. It also lacks data validation for the most part and some of it will have to happen manually. Draenor, Pandaria and Cataclysm are partially verified (some exceptions for Cataclysm are still not handled, but I have the list). By partially I mean all bosses get at least one achievement except those that have none. If those are the correct ones and if all achievements are included, has to be verified manually (to an extent, I'll include some more checks for "lone" achievements).

[Rainrider]

I need to write the prepared data to a new file. I think one could read the file containing the raw data sequentially and write its contents in the same order. It should read the lines between two corresponding curly brackets and "shuffle" their contents so that:

1. the value of the "map" key becomes a key with a new table as a vlaue (if a table for the same map isn't already open)
2. copy the line `["instance"] = number`, as it is (if a table for the same map isn't already open)
3. make the value of the "encounter" key a key with a new table as a value
4. copy the "achievements" table as the value of the "encounter" key in the output file.
5. copy the value of the "name" key as a comment after the the achievements table in the output file
6. close the map table if a new mapID or a new tier is encountered.

Would this be the best way to go for what I would like to do, or am I overcomplicating it?

[Nimhfree]

The only real problem you pose is attempting to keep the data in the data file ordered. What I would do it generate the data yourself, and create an ordered data file. Once you have generated it, you need not generate it again. If you have an automatic update system that records new information you put that into a different table that would then separately process (outside of the game) to introduce into your master ordered data file. I would keep the master data in as much of a normalized form as possible. Then, in game, when your addon loads you can process this data to create the fast access tables that get to your data by map ID/encounter/etc.

[semlar]

Actually, you could probably keep the data consistently formatted in your saved variables file if you stored your table inside of a giant string.

You'd still have to use additional tables in memory to keep track of the order of your indexes, but you could write out the saved variables in a human-readable format and use loadstring to unpack it in-game.

It would be a ridiculously complicated method just to support diffs, especially when it should be fairly simple to make the addon keep track of what's been added or changed.

[Rainrider]

Originally Posted by semlar [...]especially when it should be fairly simple to make the addon keep track of what's been added or changed.

Could you please give me some hints in that direction?

@Nimhfree
That is what I would like to do. However I would need to regenerate the data on every new tier and every new expansion, because some of the achievements become Feats of Strength, which means changes may occur in the middle, not just at the end. This is also part of the reason I want the data to be diff'able.

I also stumbled on another problem: there are two different versions of the same dungeons (e.g. Deadmines is once a classic dungeon and also one in Mists of Pandaria), however both use the same encounter, instance and map IDs. How would a user be able to differentiate between them so that they send an unambiguous request to the library?

[semlar]

Originally Posted by Rainrider Could you please give me some hints in that direction?

There are multiple ways to track changes, and how you do it depends on your goals.

You could store a copy of the state of the database when you log in and compare it to the database when you log out or the next time you log in. This would only tell you what has changed since the last time you logged in.

You could create a blank table that you insert changes into and write to the SV file on log out; similar to the first solution it would only be temporary.

You could create a saved variable table which stores a record with the timestamp every time you make a change to the database, which would allow you to generate something like a changelog but it would take up as much space as the database itself. This is probably the one I would go with if I didn't want to write a script to compare the files outside the game for some reason.

Originally Posted by Rainrider I also stumbled on another problem: there are two different versions of the same dungeons (e.g. Deadmines is once a classic dungeon and also one in Mists of Pandaria), however both use the same encounter, instance and map IDs. How would a user be able to differentiate between them so that they send an unambiguous request to the library?

I believe all you need to differentiate between 2 instances are their instance ID and difficulty.

[Nimhfree]

Originally Posted by Rainrider Could you please give me some hints in that direction? @Nimhfree That is what I would like to do. However I would need to regenerate the data on every new tier and every new expansion, because some of the achievements become Feats of Strength, which means changes may occur in the middle, not just at the end. This is also part of the reason I want the data to be diff'able. <SNIP>

I will describe a bit of how my addon Grail works. I have entries for each quest arranged by questId in numeric order. Here is an example. Each of the entries is a set of codes, so in the following the K represents quest level, the L the required level, the A: the NPC that gives the quest, etc.

G[35685]='K1000 L100 A:75028 T:75028 P:35683 E18912'
G[35686]='K0930 L092 A:75127 T:82610 P:35063+35064 E18546'

This information is loaded and then processed so I create a number of tables that allow me to access information quickly. Grail is VERY large, but it is fast because everything is cached for quick access. For example, the P: codes represent prerequisites. They are analyzed so any change in the status of a prerequisite causes any quest relying on it to have its status invalidated (so it can be recomputed).

Now, when the player is accepting or turning in quests, Grail makes sure its database has the name of the quest, and the NPC id (and location in the world) for the quest giver or the turnin NPC. If it does not, Grail records into its saved variables the missing information. If a user sends this saved variables file to me I can process it.

I have a separate process (outside of WoW) that reads saved variable files and compares the new data to my master list of quests. It can then update that master list (keeping all the quests in numeric order, and all the codes in my preferred order (solely for ease of use/diffing)).

And the final bit is upon startup Grail will clean the saved variables file based on the information in the database. So the thought it as Grail's database is updated with new releases, the missing/incorrect information Grail has recorded for a user will be removed properly.

So, what you would need to do is determine what information you want to record for each of your achievements, and how to use the Blizzard API to compare your data to what the game has, such that you can record changes. This would allow players I'm dungeons to have new things automatically recorded, and assuming the changes get sent to you, you can incorporate them into new addon versions. And you need to write some tool that allows you to take these user-submitted saved variable files and merge them into your master data.

[Rainrider]

I'll take a look at Grail, thank you very much for sharing