SaltyCrane Blog — Notes on JavaScript and web development

Recursive chained map lookups

Modify http://code.activestate.com/recipes/305268/ to support nested dictionaries. Warning: performance was not considered.

class ChainMap(dict):
    def __init__(self, *maps):
        self._maps = maps

    def __getitem__(self, key):
        for mapping in self._maps:
            try:
                return mapping[key]
            except KeyError:
                pass
        raise KeyError(key)


class DeepChainMap(dict):
    def __init__(self, *maps):
        self._maps = maps

    def __getitem__(self, key):
        values = []
        for mapping in self._maps:
            try:
                values.append(mapping[key])
            except KeyError:
                pass

        if not values:
            raise KeyError(key)

        first = values.pop(0)
        rv = first
        if isinstance(first, dict):
            values = [x for x in values if isinstance(x, dict)]
            if values:
                values.insert(0, first)
                rv = self.__class__(*values)
        return rv

    def __repr__(self):
        return '{0.__class__.__name__}({1})'.format(
            self, ', '.join(map(repr, self._maps)))


if __name__ == '__main__':
    base = {
        'a1': 'a1',
        'a2': 'a2',
        'a3': {
            'b1': 'b1',
            'b2': 'b2',
        },
    }
    ext1 = ChainMap({
        'a2': 'c2',
        'a3': {
            'b2': 'd2',
            'b4': 'd4',
        },
        'a4': 'c4',
    }, base)
    ext2 = DeepChainMap({
        'a2': 'c2',
        'a3': {
            'b2': 'd2',
            'b4': 'd4',
        },
        'a4': 'c4',
    }, base)
    # print ext1['a3']['b1']
    # # KeyError
    print ext2['a3']['b1']
    # b1

Alternative solution for alternative requirements

import copy


def derived_dict(base, override):
    newdict = copy.deepcopy(base)
    for k, v in override.iteritems():
        newvalue = v
        if isinstance(v, dict):
            try:
                base_value = newdict[k]
            except KeyError:
                pass
            else:
                if isinstance(base_value, dict):
                    newvalue = derived_dict(base_value, v)
        newdict[k] = newvalue
    return newdict


if __name__ == '__main__':
    from pprint import pprint

    wc = {
        'a1': 'a1',
        'a2': 'a2',
        'a3': {
            'b1': 'b1',
            'b2': 'b2',
        },
    }
    qa3 = derived_dict(
        wc, {
            'a2': 'c2',
            'a3': {
                'b2': 'd2',
                'b4': 'd4',
            },
            'a4': 'c4',
        }
    )
    pprint(wc)
    pprint(qa3)
class DerivedDictTestCase(unittest.TestCase):
    def test_it(self):
        base = {
            "base1": "base1",
            "base2": "base2",
            "base3": {
                "nested_base1": "nested_base1",
                "nested_base2": "nested_base2",
            }
        }
        newdict = derived_dict(
            base, {
                "base2": "override2",
                "base3": {
                    "nested_base2": "nested_override2",
                },
                "override4": "override4",
                "override5": {
                    "nested_override1": "nested_override1",
                }
            }
        )
        self.assertEqual(
            newdict, {
                'base1': 'base1',
                'base2': 'override2',
                'base3': {
                    'nested_base1': 'nested_base1',
                    'nested_base2': 'nested_override2',
                },
                'override4': 'override4',
                'override5': {
                    'nested_override1': 'nested_override1',
                }
            }
        )
        # Ensure base has not changed
        self.assertEqual(
            base, {
                "base1": "base1",
                "base2": "base2",
                "base3": {
                    "nested_base1": "nested_base1",
                    "nested_base2": "nested_base2",
                }
            }
        )

Comments