Given a structure such as the application menu layout described above, we
    may want to apply an operation to each entry to create a transformed
    version of the structure.

    For example, let's convert all entries in the application menu layout from
    above to upper-case:

    >>> pprint(apply_depth_first(menu_actions, lambda node, parents, nodes: node.upper()))
    [('FILE',
      ['LOAD', 'SAVE', ('QUIT', ['QUIT WITHOUT SAVING', 'SAVE AND QUIT'])]),
     ('EDIT', ['COPY', 'PASTE', ('FILL', ['DOWN', 'SERIES'])])]

    Here we used the `apply_depth_first` function to apply a `lambda` function
    to each entry to compute the upper-case value corresponding to each node/key.


    `as_dict`
    ---------

    To make traversing the structure easier, the output may be expressed as a
    nested `OrderedDict` structure.  For instance, let's apply the upper-case
    transformation from above, but this time with `as_dict=True`:

    >>> result = apply_depth_first(menu_actions, as_dict=True, \
    ...                            func=lambda node, parents, nodes: node.upper())

    >>> type(result)
    <class 'collections.OrderedDict'>

    Here we see that the result is an ordered dictionary.  Moreover, we can
    look up the transformed `"File"` entry based on the original key/node
    value.  Since an entry may contain children, each entry is wrapped as a
    `namedtuple` with `item` and `children` attributes.

    >>> type(result['File'])
    <class 'nested_structures.Node'>
    >>> result['File'].item
    'FILE'
    >>> type(result['File'].children)
    <class 'collections.OrderedDict'>

    If an entry has children, the `children` attribute is an `OrderedDict`.
    Otherwise, the `children` is set to `None`.

    Given the information from above, we can look up the `"Load"` child entry
    of the `"File"` entry.

    >>> result['File'].children['Load']
    Node(item='LOAD', children=None)

    Similarly, we can look up the `"Save and quit"` child entry of the `"Quit"`
    entry.

    >>> result['File'].children['Quit'].children['Save and quit']
    Node(item='SAVE AND QUIT', children=None)

    Note that this function *(i.e., `apply_depth_first`)* could be used to,
    e.g., create a menu GUI item for each entry in the structure.  This would
    decouple the description of the layout from the GUI framework used.

def apply_depth_first(nodes, func, depth=0, as_dict=False, parents=None):
    '''
    Given a structure such as the application menu layout described above, we
    may want to apply an operation to each entry to create a transformed
    version of the structure.

    For example, let's convert all entries in the application menu layout from
    above to upper-case:

    >>> pprint(apply_depth_first(menu_actions, lambda node, parents, nodes: node.upper()))
    [('FILE',
      ['LOAD', 'SAVE', ('QUIT', ['QUIT WITHOUT SAVING', 'SAVE AND QUIT'])]),
     ('EDIT', ['COPY', 'PASTE', ('FILL', ['DOWN', 'SERIES'])])]

    Here we used the `apply_depth_first` function to apply a `lambda` function
    to each entry to compute the upper-case value corresponding to each node/key.


    `as_dict`
    ---------

    To make traversing the structure easier, the output may be expressed as a
    nested `OrderedDict` structure.  For instance, let's apply the upper-case
    transformation from above, but this time with `as_dict=True`:

    >>> result = apply_depth_first(menu_actions, as_dict=True, \
    ...                            func=lambda node, parents, nodes: node.upper())

    >>> type(result)
    <class 'collections.OrderedDict'>

    Here we see that the result is an ordered dictionary.  Moreover, we can
    look up the transformed `"File"` entry based on the original key/node
    value.  Since an entry may contain children, each entry is wrapped as a
    `namedtuple` with `item` and `children` attributes.

    >>> type(result['File'])
    <class 'nested_structures.Node'>
    >>> result['File'].item
    'FILE'
    >>> type(result['File'].children)
    <class 'collections.OrderedDict'>

    If an entry has children, the `children` attribute is an `OrderedDict`.
    Otherwise, the `children` is set to `None`.

    Given the information from above, we can look up the `"Load"` child entry
    of the `"File"` entry.

    >>> result['File'].children['Load']
    Node(item='LOAD', children=None)

    Similarly, we can look up the `"Save and quit"` child entry of the `"Quit"`
    entry.

    >>> result['File'].children['Quit'].children['Save and quit']
    Node(item='SAVE AND QUIT', children=None)

    Note that this function *(i.e., `apply_depth_first`)* could be used to,
    e.g., create a menu GUI item for each entry in the structure.  This would
    decouple the description of the layout from the GUI framework used.
    '''
    if as_dict:
        items = OrderedDict()
    else:
        items = []

    if parents is None:
        parents = []

    node_count = len(nodes)
    for i, node in enumerate(nodes):
        first = (i == 0)
        last = (i == (node_count - 1))
        if isinstance(node, tuple):
            node, nodes = node
        else:
            nodes = []

        item = func(node, parents, nodes, first, last, depth)
        item_parents = parents + [node]
        if nodes:
            children = apply_depth_first(nodes, func,
                                         depth=depth + 1,
                                         as_dict=as_dict,
                                         parents=item_parents)
        else:
            children = None

        if as_dict:
            items[node] = Node(item, children)
        elif nodes:
            items.append((item, children))
        else:
            items.append(item)
    return items