Recursively create hierarchical hash from Mongo collection in Ruby

Question

I am trying to create a hash that looks like this:

{"difficulty"=>{"easy"=>{}, "normal"=>{}, "hard"=>{}}, "terrain"=>{"snow"=>{"sleet"=>{}, "powder"=>{}}, "jungle"=>{}, "city"=>{}}}

From a MongoDB collection which is and enumerable list of hashes that looks like this:

{
"_id" : "globalSettings",
"groups" : [
    "difficulty",
    "terrain"
],
"parent" : null,
"settings" : {
    "maxEnemyCount" : 10,
    "maxDamageInflicted" : 45,
    "enemyHealthPoints" : 40,
    "maxEnemySpeed" : 25,
    "maxPlayerSpeed" : 32,
    "lightShader" : "diffuse",
    "fogDepth" : 12,
    "terrainModifier" : 9
}
},
{
"_id" : "difficulty",
"groups" : [
    "easy",
    "normal",
    "hard"
],
"parent" : "globalSettings",
"settings" : {

}
}
{
"_id" : "terrain",
"groups" : [
    "snow",
    "jungle",
    "city"
],
"parent" : "globalSettings",
"settings" : {
}
}
{
"_id" : "snow",
"groups" : [
    "sleet",
    "powder"
],
"parent" : "terrain",
"settings" : {
    "fogDepth" : 4
}
}
{
"_id" : "jungle",
"groups" : [ ],
"parent" : "terrain",
"settings" : {
    "terrainModifier" : 6
}
}
{
"_id" : "city",
"groups" : [ ],
"parent" : "terrain",
"settings" : {
    "lightShader" : "bumpedDiffuse"
}
}
{
"_id" : "easy",
"groups" : [ ],
"parent" : "difficulty",
"settings" : {
    "maxEnemyCount" : 5
}
}
{
"_id" : "normal",
"groups" : [ ],
"parent" : "difficulty",
"settings" : {

}
}
{
"_id" : "hard",
"groups" : [ ],
"parent" : "difficulty",
"settings" : {
    "maxEnemyCount" : 20
}
}
{
"_id" : "sleet",
"groups" : [ ],
"parent" : "snow",
"settings" : {
    "fogDepth" : 2
}
}
{
"_id" : "powder",
"groups" : [ ],
"parent" : "snow",
"settings" : {
    "terrainModifier" : 2
}
}

Every time I try to write the function, I get stuck when setting the parent of the group. How do I recurse, yet keep track of the path of hierarchy?

The closest I've come is with this:

def dbCurse(nodes, parent = nil)
  withParent, withoutParent = nodes.partition { |n| n['parent'] == parent }
  withParent.map do |node|
    newNode={}
    newNode[node["_id"]]={}
    newNode[node["_id"]].merge(node["_id"] => dbCurse(withoutParent, node['_id']))
  end
end

which gives me a crazy mix of arrays and hashes:

{"globalSettings"=>[{"difficulty"=>[{"easy"=>[]}, {"normal"=>[]}, {"hard"=>[]}]}, {"terrain"=>[{"snow"=>[{"sleet"=>[]}, {"powder"=>[]}]}, {"jungle"=>[]}, {"city"=>[]}]}]}

I think the arrays are getting mixed in there from the #map but I'm not sure how to get rid of them to get the clean hash of hashes I show at the top of my question.

Thank you, David

Answer 1

So looking at your sample input, I'm going to make a core assumption:

The order of the hash objects in the input list are somewhat well-defined. Namely, that if the globalSettings hash refers to the group difficulty, then the next object in the list with _id == 'difficulty' and parent == 'globalSettings' is the correct match.

If this is true, then you can write a function that accepts a description of what you're looking for (i.e., the object with _id == 'difficulty' and parent == 'globalSettings') along with a reference to where you want that data stored, which can then recurse using deeper references.

def doit(obj_list, work = {})
  work.each do |key, data|
    # fetch the node
    node_i = obj_list.index { |n| n['_id'] == key && n['parent'] == data[:parent] } or next
    node = obj_list.delete_at(node_i)

    # for each group of this node, create a new hash
    # under this node's output pointer and queue it for parsing
    new_work = {}
    node['groups'].each do |group|
      data[:output][group] = {}
      new_work[group] = { parent: key, output: data[:output][group] }
    end

    # get the group data for this node
    doit(obj_list, new_work)
  end
end

input_data = JSON.parse(IO.read './input.json')
output_data = {}
doit( input_data, 'globalSettings' => { parent: nil, output: output_data } )

The trick here is that I'm handing the recursive call to doit the names of the next objects that I'm looking for from the list (using the current object's group list) and pairing each of those desired names with their parent and a reference to where I want the function to put the found data. Each recursive call to doit will use deeper and deeper references into the original output hash.