Creating a 3-dimensional OrderedDict with natural subscripting

defaultdict, ordereddictionary, python, python-2.7

Solution

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)]

Problem

I want a dictionary structure which has the following properties: - Doubly nested (so, 3-dimensional in so many words) - 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?

Original source