Algorithm example for https://github.com/matplotlib/matplotlib/pull/4240

flatten_inheritance_dict.py

from nose.tools import assert_equal, assert_is_not, assert_raises


def flatten_inheritance_dict(child_dict, parent_key,
                             expand_parent=lambda x: x):
    """Return a flattened version of dictionary that inherits from a parent.

    Parameters
    ----------
    child_dict : dict
        Dictionary with a special key that points to a dictionary of defaults,
        or a value that can be expanded to a dictionary of defaults.
    parent_key : str
        The key that points to a list of parents.
    expand_parent : callable(parent) -> dict
        Function that returns a dictionary from the value corresponding to
        `parent_key`. By default, this simply returns the value.
    """
    if parent_key not in child_dict:
        return child_dict.copy()

    parents = child_dict[parent_key]
    if not isinstance(parents, (list, tuple)):
        msg = "Parent value must be list or tuple, but given {!r}"
        raise ValueError(msg.format(parents))

    # Expand any parents defined by `child_dict` into dictionaries.
    parents = (expand_parent(p) for p in parents)

    # Resolve any grand-parents defined by parents of `child_dict`
    parents = [flatten_inheritance_dict(p, parent_key, expand_parent)
               for p in parents]

    # Child will override parent values in `dict.update` so put it last.
    ordered_dicts = parents + [child_dict]

    # Copy first dictionary and update with subsequent dictionaries.
    output_dict = ordered_dicts[0].copy()
    for d in ordered_dicts[1:]:
        output_dict.update(d)

    # Since the parent data been resolved, remove parent references.
    del output_dict[parent_key]
    return output_dict


def test_empty_dict():
    child = {}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, child)


def test_no_parent():
    child = {'my-key': 'my-value'}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, child)
    # Verify that flatten_inheritance_dict always returns a copy.
    assert_is_not(flattened, child)


def test_non_list_raises():
    child = {'parents': 'parent-value'}
    with assert_raises(ValueError):
        flatten_inheritance_dict(child, 'parents')


def test_child_with_no_unique_values():
    parent = {'a': 1}
    child = {'parents': [parent]}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, parent)


def test_child_overrides_parent_value():
    parent = {'a': 'old-value'}
    child = {'parents': [parent], 'a': 'new-value'}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, {'a': 'new-value'})


def test_parents_with_distinct_values():
    child = {'parents': [{'a': 1}, {'b': 2}]}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, {'a': 1, 'b': 2})


def test_later_parent_overrides_former():
    child = {'parents': [{'a': 1}, {'a': 2}]}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, {'a': 2})


def test_grandparent():
    grandparent = {'a': 1}
    parent = {'parents': [grandparent]}
    child = {'parents': [parent]}
    flattened = flatten_inheritance_dict(child, 'parents')
    assert_equal(flattened, grandparent)


def test_custom_expand_parent():
    parent_map = {'a-pointer': {'a': 1}, 'b-pointer': {'b': 2}}

    def expand_parent(key):
        return parent_map[key]

    child = {'parents': ['a-pointer', 'b-pointer']}
    flattened = flatten_inheritance_dict(child, 'parents',
                                         expand_parent=expand_parent)
    assert_equal(flattened, {'a': 1, 'b': 2})


def test_circular_parents():
    parent_map = {'a-pointer': {'parents': ['b-pointer']},
                  'b-pointer': {'parents': ['a-pointer']}}

    def expand_parent(key):
        return parent_map[key]

    child = {'parents': ['a-pointer']}
    with assert_raises(RuntimeError):
        flatten_inheritance_dict(child, 'parents',
                                 expand_parent=expand_parent)