CODEWITHSUNDEEP
pythonnestedtrieordereddictionary
Vangelis Tasoulas
Vangelis Tasoulas

Reputation: 3189

Python complete ordering of a nested dict

I have some sort of trie composed of OrderedDicts (but in the wrong order) which looks like this:

    test = {
        'ab':{
            '1':{},
            '2':{
                '002':{},
                '001':{}}},
        'aa':{
            '02':{
                'ac':{},
                '01':{}, 
                'ca':{}, 
                'ab':{}},
            '01':{
                'b':{}, 
                'z':{
                    '0':{}, 
                    '1':{}}}}
    }

How can I get a complete ordering of this dict in all subsequent levels?

If I use collections.OrderedDict(sorted(test.iteritems())) I get it sorted only for the first level.

I feel that I need to create a function that it will somehow call itself recursively until the deepest level, but after I spent many hours trying different ways to solve the problem, I am still stuck here.

Eventually it has to look like this:

    test = {
        'aa':{
            '01':{
                'b':{}, 
                'z':{
                    '0':{}, 
                    '1':{}}},
            '02':{
                '01':{},
                'ab':{},
                'ac':{},
                'ca':{}}},

        'ab':{
            '1':{},
            '2':{
                '001':{},
                '002':{}}}
    }

Upvotes: 4

Views: 197

Answers (3)

Andrew Gelnar
Andrew Gelnar

Reputation: 653

from collections import OrderedDict as OD
def order(X):
    retval = OD()

    # The standard iterator of a dict is its keys.
    for k in sorted(X):
        # Incase it something we can't handle.
        if isinstance(X[k], dict):
            # I want my children dicts in order.
            retval[k] = order(X[k])
        else:
            retval[k] = X[k]

    return retval

Upvotes: 1

mhlester
mhlester

Reputation: 23251

With recursion, remember there are two cases: the branch, and the leaf. Be sure to account for both.

def make_ordered(d):
    if isinstance(d, dict):
        return OrderedDict(sorted((key, make_ordered(value)) for key, value in d.iteritems()))
    else:
        return d

Upvotes: 3

pajton
pajton

Reputation: 16226

If you can afford an extra dependency I would recommend blist package. It provides many sorted containers including sorteddict. Then your dictionary would just always stay sorted.

Check the sorteddict class docs for exact usage. The package itself is production quality and BSD licence, so not a problem to use in any proprietary code.

Upvotes: 1

Related Questions