Python: Turn List of Tuples into Dictionary of Nested Dictionaries
<p>so I have a bit of an issue on my hands. I have a list of tuples (made up of a level number and message) which will eventually become an HTML list. My issues is that before this happens, I would like to turn the tuples values into a dictionary of nested dictionaries. So here is the example:</p>

<pre><code># I have this list of tuples in format of (level_number, message)
tuple_list = [(1, 'line 1'), (2, 'line 2'), (3, 'line 3'), (1, 'line 4')]

# And I want to turn it into this
a_dict = {
    'line 1': {
        'line 2': {
            'line 3': {}
        }
    }, 
    'line 4': {}
}
</code></pre>

<p>Any help would be appreciated, as long as it is valid Python 3. Thanks!</p>

<p>As I pointed out in a comment, you should STRONGLY consider changing your incoming data structure if you have any control at all over it. A sequential list of tuples is definitely not ideal for what you're doing here. However it is possible if you treat it like a tree. Let's build a (sane) data structure to parse this with</p>

<pre><code>class Node(object):
    def __init__(self, name, level, parent=None):
        self.children = []
        self.name = name
        self.level = level
        self.parent = parent

    def make_child(self, othername, otherlevel):
        other = self.__class__(othername, otherlevel, self)
        self.children.append(other)
        return other
</code></pre>

<p>Now you should be able to iterate over your data structure in some sensible way</p>

<pre><code>def make_nodes(tuple_list):
    """Builds an ordered grouping of Nodes out of a list of tuples
    of the form (level, name). Returns the last Node.
    """

    curnode = Node("root", level=-float('inf'))
    # base Node who should always be first.

    for level, name in tuple_list:
        while curnode.level &gt;= level:
            curnode = curnode.parent
            # if we've done anything but gone up levels, go
            # back up the tree to the first parent who can own this
        curnode = curnode.make_child(name, level)
        # then make the node and move the cursor to it
    return curnode
</code></pre>

<p>Once your structure is complete, you can iterate on it. Doesn't much matter here if you go depth-first or breadth-first, so let's do a DFS just for ease of implementation.</p>

<pre><code>def parse_tree(any_node):
    """Given any node in a singly-rooted tree, returns a dictionary
    of the form requested in the question
    """

    def _parse_subtree(basenode):
        """Actually does the parsing, starting with the node given
        as its root.
        """

        if not basenode.children:
            # base case, if there are no children then return an empty dict
            return {}
        subresult = {}
        for child in basenode.children:
            subresult.update({child.name: _parse_subtree(child)})
        return subresult

    cursor = any_node
    while cursor.parent:
        cursor = cursor.parent
        # finds the root node
    result = {}
    for child in cursor.children:
        result[child.name] = _parse_subtree(child)
    return result
</code></pre>

<p>Then feed in your tuple list <em>et voila</em></p>

<pre><code>tuple_list = [(1, 'line 1'), (2, 'line 2'), (3, 'line 3'), (1, 'line 4')]

last_node = make_nodes(tuple_list)
result = parse_tree(last_node)
# {'line 1': {'line 2': {'line 3': {}}}, 'line 4': {}}
</code></pre>

python list python-3.x dictionary tuples