Creating a 3-dimensional OrderedDict with natural subscripting

Question

I want a dictionary structure which has the following properties:

1. Doubly nested (so, 3-dimensional in so many words)
2. Remembers the order of things added to it for each level

So, if I add items to it like so:

# d = something dict-ish
d['a']['b']['c'] = 'd'
d['a'][1][2] = 3
d['f']['g']['e'] = 'g'
d['f'][5][6] = 7
d['a']['foo']['bar'] = 'hello world'

The result of the following comprehension:

[(i, j, k, d[i][j][k]) for i in d for j in d[i] for k in d[i][j]]

Will be:

[('a', 'b', 'c', 'd'), ('a', 1, 2, 3), ('a', 'foo', 'bar', 'hello world'), ('f', 'g', 'e', 'g'), ('f', 5, 6, 7)]

I've tried using a defaultdict to enforce this structure for new keys so I don't have to type it the long way, like so:

# long way
d = OrderedDict()
d['a'] = OrderedDict([('b', OrderedDict([('c', 'd')]))])
d['a'][1] = OrderedDict([(2,3)])

# tried to use defaultdict
d = defaultdict(lambda: defaultdict(lambda: OrderedDict()))
d['a']['b']['c'] = 'd'
d['a'][1][2] = 3

But the defaultdict doesn't remember the order of the top two levels. I'm not sure how to merge the behavior, so obviously the top two levels are yielding defaultdict behavior because I have declared d to be as such. How can I achieve the structure I want?

Answer 1

All you need is to subclass OrderedDict and add a __missing__ function:

from collections import OrderedDict

class DefaultOrderedDict(OrderedDict):
    def __missing__(self, key):
        self[key] = type(self)()
        return self[key]

The default dict type will call a __missing__ method if present before raising a KeyError, which is what the defaultdict type makes use of.

See the dict documentation (scroll down to the d[key] description):

New in version 2.5: If a subclass of dict defines a method __missing__(), if the key key is not present, the d[key] operation calls that method with the key key as argument. The d[key] operation then returns or raises whatever is returned or raised by the __missing__(key) call if the key is not present. No other operations or methods invoke __missing__(). If __missing__() is not defined, KeyError is raised. __missing__() must be a method; it cannot be an instance variable.

Demo:

>>> d = DefaultOrderedDict()
>>> d['a']['b']['c'] = 'd'
>>> d['a'][1][2] = 3
>>> d['f']['g']['e'] = 'g'
>>> d['f'][5][6] = 7
>>> d['a']['foo']['bar'] = 'hello world'
>>> [(i, j, k, d[i][j][k]) for i in d for j in d[i] for k in d[i][j]]
[('a', 'b', 'c', 'd'), ('a', 1, 2, 3), ('a', 'foo', 'bar', 'hello world'), ('f', 'g', 'e', 'g'), ('f', 5, 6, 7)]