Recursive sorting function for list in Python
Question: I want to take a list like the following:

    
    
    groups = ["foo", "bar", "foo::fone", "foo::ftwo", "foo::ftwo::ffone"]
    

And convert it into a nested list, probably in the following format, but I'm
open to suggestions:

    
    
    groups_sorted = [{
                        "name":"foo",
                        "children": [
                                      {
                                        "name": "foo::fone",
                                        "children": [ ... ]
                                      }, ...
                                    ]
                     }, ...
                    ]
    

So that the list is sorted using a hierarchy split on `::`. I need each of the
`children` keys to be lists themselves as the original order of the list is
important.

I've played around for a few hours and been able to create a recursive
dictionary starting from a single top node, but I couldn't do the last bit.
Find my workings below:

    
    
    def children_of(node, candidates):
        children = []
        remainder = []
        for c in candidates:
            sub = node + "::"
            if c.startswith(sub):
                try:
                    c[len(sub):].index("::") # any more separators = not a child
                    remainder.append(c)
                except ValueError: # a child
                    children.append(c)    
            else: #not related
                remainder.append(c)
        return children, remainder
    
    def sortit(l):
        if l:
            el = l.pop(0)
            children, remainder = children_of(el,l)
            if children:    
                return { "name": el,
                         "children": [sortit([c]+remainder) for c in children]
                       }
            else:
                return { "name": el }
    

**Edit** : @Thijs van Dien's solution is really good but I need 2.6
compatibility which prevents me some using OrderDicts.


Answer: How about something like this instead?

    
    
    from collections import OrderedDict
    
    dic = OrderedDict()
    
    def insert(name):
        current_dic = dic
        current_name = ''
        for name_elem in name.split('::'):
            current_name += ('::' if current_name else '') + name_elem
            if not current_name in current_dic:
                current_dic[current_name] = OrderedDict()
            current_dic = current_dic[current_name]
    
    for group in ["foo", "bar", "foo::fone", "foo::ftwo", "foo::ftwo::ffone"]:
        insert(group)
    

That gives you the following structure:

    
    
    {'bar': {}, 'foo': {'foo::fone': {}, 'foo::ftwo': {'foo::ftwo::ffone': {}}}}
    

`OrderedDict` makes sure that order is preserved, so you don't need to use any
`list`. Also, you don't need to use recursion, as it is not recommended in
Python.

If you don't have `OrderedDict` in the standard library, because you're using
Python 2.6, you can install it:

    
    
    pip install ordereddict
    

Then change the import:

    
    
    from ordereddict import OrderedDict
    

Here's another solution that works only if you can assume that parents already
exist when you need them. Things go bad if you have duplicate groups, so you
need to adjust it for that yourself.

    
    
    children_of_name = dict([('', list())]) # Access root with empty string
    
    def insert(name):
        parent_name = '::'.join(name.split('::')[:-1])
        dic = dict([('name', name), ('children', list())])
        children_of_name[parent_name].append(dic)
        children_of_name[name] = dic['children']
    
    for group in ["foo", "bar", "foo::fone", "foo::ftwo", "foo::ftwo::ffone"]:
        insert(group)
    

It gives you the structure that you proposed:

    
    
    [{'children': [{'children': [], 'name': 'foo::fone'},
                   {'children': [{'children': [], 'name': 'foo::ftwo::ffone'}],
                    'name': 'foo::ftwo'}],
      'name': 'foo'},
     {'children': [], 'name': 'bar'}]
    

