How to efficiently merge multiple list of different length into a tree dictonary in python

Question

given

[
  ('object-top-1','object-lvl1-1','object-lvl2-1'),
  ('object-top-2','object-lvl1-1','object-lvl2-2','object-lvl3-1')
  ('object-top-1','object-lvl1-1','object-lvl2-3'),
  ('object-top-2','object-lvl1-2','object-lvl2-4','object-lvl3-2','object-lvl4-1'),
]

and so on .. where all the tuples are of arbitrary length

Any way to efficiently convert them to

{'object-top-1': {
      'object-lvl1-1': {
                   'object-lvl2-1': {},
                   'object-lvl2-3':{}
                }
       },
 'object-top-2': {
       'object-lvl1-1':{
                'object-lvl2-2': { 
                     'object-lvl3-1' : {} 
                     }
                 }
       }
       'object-lvl1-2':{
                'object-lvl2-4': {
                         'object-lvl3-2' : { 
                              'object-lvl4-1': {}
                         }
                 }
        }
 }

I've been stuck trying to figure this out for quite some time now >.<

Thanks!

Answer 1

This will do it, and let's you add other values as well, instead of being limited to empty dicts at the leaves:

def insert_in_dictionary_tree_at_address(dictionary, address, value):
    if (len(address) == 0):
        pass
    elif (len(address) == 1):
        dictionary[address[0]] = value
    else:
        this = address[0]
        remainder = address[1:]
        if not dictionary.has_key(this):
            dictionary[this] = dict()
        insert_in_dictionary_tree_at_address(dictionary[this], remainder, value)

addresses = [
  ('object-top-1','object-lvl1-1','object-lvl2-1'),
  ('object-top-2','object-lvl1-1','object-lvl2-2','object-lvl3-1'),
  ('object-top-1','object-lvl1-1','object-lvl2-3'),
  ('object-top-2','object-lvl1-2','object-lvl2-4','object-lvl3-2','object-lvl4-1'),
]

dictionary = dict()

for address in addresses:
    insert_in_dictionary_tree_at_address(dictionary, address, dict())

def print_dictionary_tree(dictionary, prefix="    ", accumulated=""):
    next_accumulated = accumulated + prefix
    if type(dictionary) is dict and len(dictionary) > 0:
        for (key, value) in dictionary.items():
            print accumulated + str(key) + ":"
            print_dictionary_tree(value, prefix, accumulated + prefix)
    else:
        print accumulated + str(dictionary)\

print_dictionary_tree(dictionary)

Output:

object-top-1:
    object-lvl1-1:
        object-lvl2-1:
            {}
        object-lvl2-3:
            {}
object-top-2:
    object-lvl1-2:
        object-lvl2-4:
            object-lvl3-2:
                object-lvl4-1:
                    {}
    object-lvl1-1:
        object-lvl2-2:
            object-lvl3-1:
                {}

Answer 2

def treeify(seq):
    ret = {}
    for path in seq:
        cur = ret
        for node in path:
            cur = cur.setdefault(node, {})
    return ret

Example:

>>> pprint.pprint(treeify(L))
{'object-top-1': {'object-lvl1-1': {'object-lvl2-1': {}, 'object-lvl2-3': {}}},
 'object-top-2': {'object-lvl1-1': {'object-lvl2-2': {'object-lvl3-1': {}}},
                  'object-lvl1-2': {'object-lvl2-4': {'object-lvl3-2': {'object-lvl4-1': {}}}}}}

dict.setdefault is an underappreciated method.