Iterating through nested dictionaries

Question

I want to write an iterator for my 'toy' Trie implementation.

Adding already works like this:

class Trie:
    def __init__(self):
        self.root = dict()
        pass
    def add(self, string, value):
        global nops
        current_dict = self.root
        for letter in string:
           nops += 1
           current_dict = current_dict.setdefault(letter, {})
        current_dict = current_dict.setdefault('value', value)              
        pass

The output of the adding looks like that:

trie = Trie()
trie.add("hello",1)
trie.add("world",2)
trie.add("worlds",12)
print trie.root
{'h': {'e': {'l': {'l': {'o': {'value': 1}}}}}, 'w': {'o': {'r': {'l': {'d': {'s': {'value': 12}, 'value': 2}}}}}}

I know, that I need a __iter__ and next method.

def __iter__(self):
    self.root.__iter__()
    pass

 def next(self):
    print self.root.next()

But AttributeError: 'dict' object has no attribute 'next'. How should I do it?

[Update] In the perfect world I would like the output to be one dict with all the words/entries with their corresponding values.

What do you want the result of iterating over your class to be? — ecatmur, Nov 14 '12 at 16:42
I think you forgot the initial `"""` at the beginning of your docstring. — jdotjdot, Nov 14 '12 at 16:47
A couple more things. (1) You never declare `s` in your initial code, so it does not run. You need to name the second argument `s` or have `for letter in string` instead. (2) In your sample results, `w o r l d s` should have value 12 according to your samples, not 2. — jdotjdot, Nov 14 '12 at 16:55
Thanks, I corrected these errors as well. The example is a different / minimal version of my code, so that's where the errors come from. — Framester, Nov 14 '12 at 17:13

ecatmur · Accepted Answer · 2012-11-14T16:58:10.443

Your __iter__ special method should return an iterator; that is, an object of a class that you can call next on. A toy iterator class would be something like:

class MyIterator:
    def __init__(self):
        self.i = 10
    def next(self):
        self.i -= 1
        if self.i == 0:
            raise StopIteration
        else:
            return self.i

Unless you have a natural object to call iter on, it's usually easier to make __iter__ a generator:

def __iter__(self):
    for i in range(10)
        yield i

Here's a stack-based generator iterator for your Trie:

    def __iter__(self):
        stack = [('', self.root)]
        while stack:
            prefix, d = stack.pop()
            for k, v in d.items():
                if k == 'value':
                    yield prefix, v
                else:
                    stack.append((prefix + k, v))

You could also try writing it recursively, although you'd need to use itertools.chain or yield from (only since Python 3.3).

score 0 · Answer 2 · answered Nov 14 '12 at 17:31

Assuming I understand correctly what you're looking for in your iterator, I'd do something along these lines (note added field in __init__:

class Trie:
    def __init__(self):
        self.root = dict()
        self.stack = ''

    def add(self, string, value):
        """map it to the given value."""
        global nops
        current_dict = self.root
        for letter in string:
           nops += 1
           current_dict = current_dict.setdefault(letter, {})
        current_dict = current_dict.setdefault('value', value)              
        pass

    def __iter__(self, input_dict=None):
        if not input_dict:
            input_dict = self.root

        if 'value' in input_dict:
            yield (self.stack, input_dict['value'])

        keys = [x for x in input_dict.keys() if x != 'value']
        for key in keys:
            self.stack += key
            for item in self.__iter__(input_dict[key]):
                yield item
            self.stack = self.stack[:-1]

That would give you:

trie = Trie()
trie.add("hello", 1)
trie.add("world", 2)
trie.add("worlds", 12)
print trie.root
print [x for x in trie]

# {'h': {'e': {'l': {'l': {'o': {'value': 1}}}}}, 'w': {'o': {'r': {'l': {'d': {'s': {'value': 12}, 'value': 2}}}}}}
# [('hello', 1), ('world', 2), ('worlds', 12)]

So, it is possible to do this recursively without itertools.chain or yield from.

Iterating through nested dictionaries

2 Answers2