iteration through nested dictionaries

Question

I'm trying to implement simple tree class which is inherited from dictionary. Here my code:

class tree(dict):
    def __init__(self, hsymbol="/"):
        self.hsymbol = hsymbol
    def __setitem__(self, key, value):
        if key[0] == self.hsymbol : key = key[1:]
        parts = key.split(self.hsymbol, 1)
        if len(parts) == 2:
            if parts[0] not in self: self[parts[0]] = tree(hsymbol = self.hsymbol)
            self[parts[0]].__setitem__(parts[1], value)
        else:
            super(tree, self).__setitem__(key, value)

    def __getitem__(self, key):
        if key[0] == self.hsymbol : key = key[1:]
        parts = key.split(self.hsymbol, 1)
        if len(parts) == 2:
            if parts[0] not in self: raise KeyError(parts[0])
            return self[parts[0]][parts[1]]
        else:
            if key not in self: raise KeyError(parts[0])
            return super(tree, self).__getitem__(key)
    def __contains__(self,key):
        if key[0] == self.hsymbol : key = key[1:]
        parts = key.split(self.hsymbol, 1)
        if len(parts) == 2:
            if not super(tree, self).__contains__(parts[0]): return False
            return parts[1] in self[parts[0]]
        else:
            if not super(tree, self).__contains__(key): return False
            return True
    def __delitem__(self, key):
        if key[0] == self.hsymbol : key = key[1:]
        parts = key.split(self.hsymbol, 1)
        if len(parts) == 2:
            if parts[0] not in self: raise KeyError(parts[0])
            self[parts[0]].__delitem__(parts[1])
        else:
            if key not in list(self): raise KeyError(parts[0])
            super(tree,self).__delitem__(key)
    def keys(self,parent=""):
        #if parent is None: parent = self.hsymbol
        names = []
        for name in super(tree, self).keys():
            if isinstance(self[name], tree):
                names += self[name].keys(parent=parent+self.hsymbol+name)
            else:
                names.append(parent+self.hsymbol+name)
        return names

So everything works quite well, although I'm not sure about keys function realization:

>>> t=tree()
>>> t['/user/Johnson/incoming'] = 2200
>>> t['/user/Johnson/family'] = 4
>>> t['/user/Johnson/play'] = False
>>> t['/user/Smith/incoming'] = 12000
>>> t['/user/Smith/family'] = 1
>>> t['/user/Smith/play'] = True
>>> t['user/Smith/incoming']
12000    
>>> print t
{'user': {'Smith': {'play': True, 'incoming': 12000, 'family': 1}, 'Johnson': {'play': False, 'incoming': 2200, 'family': 4}}}
>>> print t.keys()
['/user/Smith/play', '/user/Smith/incoming', '/user/Smith/family', '/user/Johnson/play', '/user/Johnson/incoming', '/user/Johnson/family']
>>> t
{'user': {'Smith': {'play': True, 'incoming': 12000, 'family': 1}, 'Johnson': {'play': False, 'incoming': 2200, 'family': 4}}}

...but not an iteration through it:

>>> for k in t:
...  print k
... 
user
>>> 

How can I get something like this?

/user/Smith/play
/user/Smith/incoming
/user/Smith/family
/user/Johnson/play
/user/Johnson/incoming
/user/Johnson/family

Pretty sure that it must be __iter__ and next attributes of tree class, but I haven't figured out how to write it yet.

I've searched over Stack Overflow with no luck:

• python recursive iteration nested dictionaries

• python class inherited from dictionary iteration through nested dictionaries

• python iteration through nested dictionaries

Answer 1

Yes, you need __iter__ (an iterator will have a next() automatically).

Following your existing logic:

def __iter__(self, parent=""):
    for name in super(tree, self).keys():
        if isinstance(self[name], tree):
            for item in self[name].__iter__(parent=parent+self.hsymbol+name):
                yield item
        else:
            yield parent+self.hsymbol+name

Unlike your current keys() implementation, this only walks the tree on an as-needed basis: If a client only needs the first two keys, it only calls next() twice, and so the iterator only proceeds past two yields.

(I might suggest implementing keys as simply return list(iter(self)) -- that way you have the lazy approach available for those that want to avoid the inefficiency of unnecessarily walking a full tree, and the non-lazy approach otherwise).