A collection of useful data structures including a very complete linked list class that implements the full feature set of _collections.MutableSequence.

data_structures.py

# This is free and unencumbered software released into the public domain.
#
# Anyone is free to copy, modify, publish, use, compile, sell, or
# distribute this software, either in source code form or as a compiled
# binary, for any purpose, commercial or non-commercial, and by any
# means.
#
# In jurisdictions that recognize copyright laws, the author or authors
# of this software dedicate any and all copyright interest in the
# software to the public domain. We make this dedication for the benefit
# of the public at large and to the detriment of our heirs and
# successors. We intend this dedication to be an overt act of
# relinquishment in perpetuity of all present and future rights to this
# software under copyright law.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
#
# For more information, please refer to <http://unlicense.org/>


"""All code in this module is in the public domain unless otherwise noted.

A module holding classes either missing from Python.
Some classes, such as ChainMap, are simply missing from Python 2.x.
Many others are useful classes that are altogether missing when they
probably shouldn't be (such as `frozenmap`). Others are useful in building
other more complex datastructures. An example of this type of class
is the LinkedList class, which is useful in building more complex
structures.
"""

from __future__ import print_function, absolute_import, division
# from .py3_fixes import *

# from reprlib import recursive_repr as _recursive_repr

try:
    from future_builtins import *
except Exception as e:
    pass

import itertools as _itertools
import operator as _operator
import collections as _collections

import weakref as _weakref

__all__ = []


def _add_to__all__(val):
    # print(val)
    # print(val.__name__)
    __all__.append(val.__name__)
    return val



@_add_to__all__
class Node(object):

    """Node class for use in the LinkedList class implementation."""

    __slots__ = ('_container', '_prev', 'value', 'next', '__weakref__')

    def __init__(self, container=None, prev=None, value=None, next=None):
        """Initialize Node instance."""
        # "container" and "prev" are not True attributes, but properties. To be
        # safe, we set their underlying attributes to None, so that if/when
        # they are accessed in the properties' setter and getter methods,
        # nothing breaks.
        self._container = None
        self._prev = None

        self.container = container
        self.prev = prev
        self.value = value
        self.next = next

    def remove(self):
        """A convenience function to remove the node from its container.

        This is the same as calling "node.container.remove_node(node)" if the
        node's container is not set to None.
        """
        container = self.container
        if container is not None:
            container.remove_node(self)
        return self

    @property
    def container(self):
        """A (weak) reference to the container that contains this node.

        This may also be set to None if the node is not associated with any
        container.

        >>> ll = LinkedList()
        >>> n = Node()
        >>> n.container = ll
        >>> print(n.container)
        LinkedList()
        >>> n.container = None
        >>> print(n.container)
        None
        >>> n.container = 10
        Traceback (most recent call last):
            ...
        TypeError: cannot create weak reference to 'int' object
        """
        return None if self._container is None else self._container()

    @container.setter
    def container(self, value):
        """Setter for container property."""
        if value is None:
            self._container = None
        else:
            self._container = _weakref.ref(value)
        return value

    @property
    def prev(self):
        """A (weak) reference to the node that precedes this one in a list.

        >>> node = Node()
        >>> other = Node()
        >>> node.prev = other
        >>> node.prev is other
        True
        >>> node.prev = None
        >>> print(node.prev)
        None
        >>> node.prev = 10
        Traceback (most recent call last):
            ...
        TypeError: cannot create weak reference to 'int' object
        """
        return None if self._prev is None else self._prev()

    @prev.setter
    def prev(self, value):
        """Setter for prev property."""
        if value is None:
            self._prev = None
        else:
            self._prev = _weakref.ref(value)
        return value


@_add_to__all__
class LinkedList(_collections.MutableSequence):

    """Basic (but very complete) linked list implementation.

    The class implements many methods beyond the standard mutable sequence
    methods. This is to make it easier and more efficient to work with nodes
    in a linked list instance, or to transfer nodes between instances.
    """

    def __init__(self, iterable=()):
        """Initialize LinkedList instance.

        Expects an iterable object it initialize its contents. May also be
        passed nothing to initialize empty.

        >>> LinkedList()
        LinkedList()
        >>> LinkedList([0, 1, 2, 3, 4])
        LinkedList([0, 1, 2, 3, 4])
        >>> LinkedList([[0, 1], [2, 3]])
        LinkedList([[0, 1], [2, 3]])
        >>> LinkedList([1])
        LinkedList([1])
        >>> LinkedList([True, False, 1, None])
        LinkedList([True, False, 1, None])
        """
        # TODO: Remove hidden _tail reference and implement as a circularly linked list?
        self._root = None
        self._tail = None
        self._cached_length = 0

        self.extend(iterable)

    @property
    def root(self):
        """Read only attribute referencing the root node of the linked list.

        Will return None when the list is empty.

        >>> ll = LinkedList([0, 1, 2, 3, 4])
        >>> ll.root is None
        False
        >>> ll.root.value == 0
        True
        >>> ll.clear()
        >>> ll.root is None
        True
        >>> ll.append('value') # List now has only one entry
        >>> ll.root is ll.tail
        True
        >>> ll.root = Node()
        Traceback (most recent call last):
            ...
        AttributeError: can't set attribute
        """
        return self._root

    @property
    def tail(self):
        """Read only attribute referencing the tail node of the linked list.

        Will return None when the list is empty.

        >>> ll = LinkedList([0, 1, 2, 3, 4])
        >>> ll.tail is None
        False
        >>> ll.tail.value == 4
        True
        >>> ll.clear()
        >>> ll.tail is None
        True
        >>> ll.tail = Node()
        Traceback (most recent call last):
            ...
        AttributeError: can't set attribute
        """
        return self._tail

    def __len__(self):
        """Return length of self."""
        return self._cached_length

    def __repr__(self, _fmt='{0.__class__.__name__}({1})'.format):
        """Return useful string representation of self."""
        return _fmt(self, list(self) or '')

    def _prep_slice(self, slc, iter_nodes=False):
        start = slc.start
        stop = slc.stop
        step = slc.step

        if start is not None and start < 0:
            start = len(self) + start

        if stop is not None and stop < 0:
            stop = len(self) + stop

        if step is not None and step < 0:
            step = abs(step)
            selfiter = reversed(self) if not iter_nodes else self.reverse_iter_nodes()
        else:
            selfiter = iter(self) if not iter_nodes else self.iter_nodes()

        return _itertools.islice(selfiter, start, stop, step)

    def clear(self):
        """Clear all items from the sequence in place.

        >>> original = ll = LinkedList([0, 1, 2, 3, 4])
        >>> ll.clear()
        >>> ll
        LinkedList()
        >>> len(ll)
        0
        >>> original is ll
        True
        """
        # Since Node objects use weak references, the nodes will clean
        # themselves up once all references to them disapear.
        self._root = self._tail = None
        self._cached_length = 0

    def sort(self, key=None, reverse=False):
        """Sort sequence in place.

        This is no more efficient than calling "sorted(linkedlist)".
        However, this method maintains the identity of the nodes in the list,
        so it is still useful.

        >>> original = ll = LinkedList([3, 4, 2, 0, 1])
        >>> print(ll)
        LinkedList([3, 4, 2, 0, 1])
        >>> node4 = ll.get_node(1)
        >>> node0 = ll.get_node(-2)
        >>> ll.sort()
        >>> print(ll)
        LinkedList([0, 1, 2, 3, 4])
        >>> original is ll
        True
        >>> # node identities are kept (i.e. no nodes are created/discarded)
        >>> node4 is ll.tail
        True
        >>> node0 is ll.root
        True
        """
        # TODO: test using custom key callables
        if key is not None:
            keyfunc = lambda node: key(node.value)
        else:
            keyfunc = _operator.attrgetter('value')

        sortednodes = sorted(self.iter_nodes(), key=keyfunc, reverse=reverse)
        # references to the nodes are in "sortednodes" so they won't get
        # garbage collected when we clear the LinkedList.
        self.clear()
        for node in sortednodes:
            self.insert_node(None, node)

    def __getitem__(self, index):
        """__getitem__ indexing.

        This operation is slow on linked lists and ought to be avoided.

        >>> ll = LinkedList(range(5))
        >>> ll[0]
        0
        >>> ll[-1]
        4
        >>> ll[2]
        2
        >>> ll[1:3]
        LinkedList([1, 2])
        >>> ll[::2]
        LinkedList([0, 2, 4])
        >>> ll[::-1]
        LinkedList([4, 3, 2, 1, 0])
        >>> ll[1::-1]
        LinkedList([3, 2, 1, 0])
        >>> ll[:10]
        LinkedList([0, 1, 2, 3, 4])
        >>> ll[10:]
        LinkedList()
        >>> llnew = ll[:]
        >>> llnew == ll  # the contents match
        True
        >>> llnew is ll  # but the identity does not
        False
        """
        if isinstance(index, slice):
            islc = self._prep_slice(index)
            return self.__class__(islc)
        else:
            return self.get_node(index).value

    def __lt__(self, other):
        """Less than comparison.

        >>> ll1 = LinkedList(range(6, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 < ll2) == (list(ll1) < list(ll2))
        True
        >>> (ll1 < ll1) == (list(ll1) < list(ll1))
        True
        >>> ll1 = LinkedList(range(20, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 < ll2) == (list(ll1) < list(ll2))
        True
        >>> (ll2 < ll1) == (list(ll2) < list(ll1))
        True
        """
        if not isinstance(other, self.__class__):
            return NotImplemented

        for si, oi in zip(self, other):
            if si >= oi:
                return False
        return True

    def __le__(self, other):
        """Less than or equal comparison.

        >>> ll1 = LinkedList(range(6, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 <= ll2) == (list(ll1) <= list(ll2))
        True
        >>> (ll1 <= ll1) == (list(ll1) <= list(ll1))
        True
        """
        if not isinstance(other, self.__class__):
            return NotImplemented
        return self < other or self == other

    def __eq__(self, other):
        """Equal comparison.

        >>> ll1 = LinkedList(range(6, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 == ll2) == (list(ll1) == list(ll2))
        True
        >>> (ll1 == ll1) == (list(ll1) == list(ll1))
        True
        """
        if not isinstance(other, self.__class__):
            return NotImplemented

        if len(self) != len(other):
            return False

        for si, oi in zip(self, other):
            if si != oi:
                return False
        return True  # if we have exhausted all items, then we must match

    def __ne__(self, other):
        """Not equal comparison.

        >>> ll1 = LinkedList(range(6, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 != ll2) == (list(ll1) != list(ll2))
        True
        >>> (ll1 != ll1) == (list(ll1) != list(ll1))
        True
        """
        result = self == other
        return result if result is NotImplemented else not result

    def __gt__(self, other):
        """Greater than comparison.

        >>> ll1 = LinkedList(range(6, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 > ll2) == (list(ll1) > list(ll2))
        True
        >>> (ll1 > ll1) == (list(ll1) > list(ll1))
        True
        """
        if not isinstance(other, self.__class__):
            return NotImplemented
        return not (self < other) and not (self == other)

    def __ge__(self, other):
        """Greater than or equal comparison.

        >>> ll1 = LinkedList(range(6, 0, -1))
        >>> ll2 = LinkedList(range(0, 6, 1))
        >>> (ll1 >= ll2) == (list(ll1) >= list(ll2))
        True
        >>> (ll1 >= ll1) == (list(ll1) >= list(ll1))
        True
        """
        if not isinstance(other, self.__class__):
            return NotImplemented
        return not (self < other) or (self == other)

    def __setitem__(self, index, value):
        """__setitem__ indexing.

        >>> ll = LinkedList(range(5))
        >>> ll
        LinkedList([0, 1, 2, 3, 4])
        >>> ll[2] = None
        >>> ll
        LinkedList([0, 1, None, 3, 4])
        """
        if isinstance(index, slice):
            if index.start is None and index.stop is None and index.step is None:
                self.clear()
                for v in value:
                    self.append(v)
                return
            else:
                raise NotImplementedError('complete slice assignment is not yet implemented')
        else:
            self.get_node(index).value = value

    def __delitem__(self, index):
        """delete item(s).

        >>> ll = LinkedList(range(10))
        >>> ll
        LinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
        >>> del ll[4]
        >>> ll
        LinkedList([0, 1, 2, 3, 5, 6, 7, 8, 9])
        >>> del ll[0:2]
        >>> ll
        LinkedList([2, 3, 5, 6, 7, 8, 9])
        >>> del ll[::2]
        >>> ll
        LinkedList([3, 6, 8])
        """
        if isinstance(index, slice):
            islc = self._prep_slice(index, iter_nodes=True)
            for n in islc:
                self.remove_node(n)
        else:
            self.pop(index)

    def insert(self, index, value):
        """Insert value at specified index.

        >>> ll = LinkedList(range(5))
        >>> l = list(ll)
        >>> ll.insert(2, None)
        >>> ll
        LinkedList([0, 1, None, 2, 3, 4])
        >>> l.insert(2, None)
        >>> list(ll) == l
        True
        """
        if index >= len(self):  # append to back
            self.insert_node(None, value=value)
        else:
            node = self.get_node(index)
            self.insert_node(node, value=value)

    # The default pop implementation indexes into the sequence twice (once to
    # retrieve the value and once to delete it). This would be overly expensive
    # for a linked list.
    def pop(self, index=-1):
        """Remove and return an item from the sequence.

        Defaults to removing the last item in the sequence.

        >>> ll = LinkedList(range(5))
        >>> ll.pop() # pop from back
        4
        >>> ll
        LinkedList([0, 1, 2, 3])
        >>> ll.pop(0) # pop from front
        0
        >>> ll
        LinkedList([1, 2, 3])
        >>> ll.pop(1) # pop from middle
        2
        >>> ll
        LinkedList([1, 3])
        """
        node = self.get_node(index)
        node = self.remove_node(node)
        return node.value

    def reverse(self):
        """Reverse sequence in place.

        >>> original = ll = LinkedList(range(5))
        >>> ll
        LinkedList([0, 1, 2, 3, 4])
        >>> ll.reverse()
        >>> ll
        LinkedList([4, 3, 2, 1, 0])
        >>> original is ll
        True
        >>> ll.reverse()
        >>> ll
        LinkedList([0, 1, 2, 3, 4])
        """
        if len(self) <= 1:
            return

        nl = list(self.reverse_iter_nodes())
        for i, n in enumerate(nl):
            if i - 1 >= 0:
                nl[i-1].next = nl[i]
                nl[i].prev = nl[i-1]
            if i + 1 < len(self):
                nl[i+1].prev = nl[i]
                nl[i].next = nl[i+1]

        nl[0].prev = nl[-1].next = None

        self._root = nl[0]
        self._tail = nl[-1]

    def remove(self, value):
        """Remove node with given value.

        Raises ValueError if value does not exist in container

        >>> ll = LinkedList([0, 1, 2, 3, 4])
        >>> ll.remove(2)
        >>> ll
        LinkedList([0, 1, 3, 4])
        >>> ll.remove(5)
        Traceback (most recent call last):
            ...
        ValueError: Value '5' not found in container
        """
        for node in self.iter_nodes():
            if node.value == value:
                self.remove_node(node)
                return
        raise ValueError("Value '{0!r}' not found in container".format(value))

    def __iter__(self):
        """Implement in place forward iteration.

        >>> ll = LinkedList(range(5))
        >>> tuple(ll)
        (0, 1, 2, 3, 4)
        >>> lliter = iter(ll)
        >>> list(lliter)
        [0, 1, 2, 3, 4]
        """
        for node in self.iter_nodes():
            yield node.value

    def __reversed__(self):
        """Implement in place reverse iteration.

        >>> ll = LinkedList(range(5))
        >>> ll
        LinkedList([0, 1, 2, 3, 4])
        >>> other = LinkedList(reversed(ll))
        >>> other
        LinkedList([4, 3, 2, 1, 0])
        >>> ll is other
        False
        """
        for node in self.reverse_iter_nodes():
            yield node.value

    def iter_nodes(self):
        """Iterate directly thru LinkedList nodes."""
        current = self._root
        while current is not None:
            # we save a reference to 'next' so that it is possible to remove
            # 'current' during iteration
            next = current.next
            yield current
            current = next

    def reverse_iter_nodes(self):
        """Reverse iterate directly thru LinkedList nodes."""
        current = self._tail
        while current is not None:
            # we save a reference to 'prev' so that it is possible to remove
            # 'current' during iteration
            prev = current.prev
            yield current
            current = prev

    def insert_node(self, before, node=None, value=None):
        """Directly insert node into LinkedList.

        Return the inserted node object.
        """
        if node is None:
            node = Node(value=value)
        elif node is before:
            raise ValueError('Cannot insert node before itself!')
        elif not isinstance(node, Node):
            raise ValueError('"node" parameter must either be None or a Node instance')

        if node.container is not None and node.container is not self:
            node.remove()

        # Special case of container being empty
        if not self:
            node.container = self
            node.prev = node.next = None
            self._root = self._tail = node
            self._cached_length += 1
            return node

        # NOTE: in case a node within this same container is simply being moved
        node.remove()

        # None is a special value to indicate that we want to append this node
        # to the end of the chain.
        if before is None:
            prev = self._tail
            next = self._tail.next
        elif isinstance(before, Node) and before.container is self:
            prev = before.prev
            next = before
        else:
            raise ValueError('"before" parameter must either be None or a Node in this container')

        node.container = self
        node.prev = prev
        node.next = next

        if prev is not None:
            prev.next = node
        if next is not None:
            next.prev = node

        if before is None:
            self._tail = node
        elif before is self._root:
            self._root = node

        self._cached_length += 1

        return node

    def remove_node(self, node):
        """Remove node from container.

        The return value is the node instance with its container, prev and next
        properties set to None.

        If the node is not a member of this container, None is returned.
        """
        if node.container is not self:
            return None

        # We place prev and next into local variables to avoid a race condition
        # since the Node class uses weak references.
        prev = node.prev
        next = node.next

        # reassign prev and/or next references if they exist
        if prev is not None:
            prev.next = node.next

        if next is not None:
            next.prev = node.prev

        # deal with the special cases of removing root and tail nodes
        if prev is None and next is not None:
            self._root = next
        elif prev is not None and next is None:
            self._tail = prev
        elif prev is None and next is None:
            self._root = self._tail = None

        node.container = node.prev = node.next = None

        self._cached_length -= 1

        return node

    def get_node(self, index):
        """Get the node object at the given index."""
        # Special case for empty list
        if len(self) == 0:
            if self._root is None and self._tail is None:
                raise IndexError('LinkedList index out of range; sequence is empty')
            else:
                raise RuntimeError('The list length cache is reported as being zero, but either root or tail (or both) is not None.')

        if index < 0:
            index = len(self) + index

        if index >= len(self) or index < 0:
            raise IndexError('LinkedList index out of range')

        # Special cases for root and tail, since accessing the front and the
        # back of a sequence are frequent operations.
        if index == 0:
            return self._root
        elif index == len(self)-1:
            return self._tail

        current = self._root
        count = 0
        while current is not None:
            if index == count:
                return current
            current = current.next
            count += 1
        # All index errors should be raised before this. Check into this.
        raise IndexError('How did I get here?.')


# NOTE: A large portion of this is sourced from:
# https://github.com/python/cpython/blob/2.7/Lib/collections.py
# This code is licensed under the PSFL since it was initially taken verbatim
# from the Python standard library.
@_add_to__all__
class OrderedDict(dict, _collections.MutableMapping):

    """A dictionary that remembers insertion order.

    This is different from the stdlib collections.OrderedDict in that it allows for
    modification of the underlying order (essentially, restricted access
    to the underlying linked list).
    
    Also, its implementation in faily different; whereas the OrderedDict in collections
    optimizes for speed of retrieval of items by key, this implementation optimizes
    for space.
    """

    def __init__(self, *args, **kwargs):
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))

        super(OrderedDict, self).__init__()
        try:
            self.__llist
        except AttributeError:
            self.__llist = LinkedList()

        self.__update(*args, **kwargs)

    def __setitem__(self, key, value, _setitem=dict.__setitem__, _getitem=dict.__getitem__):
        """Set item in dictionary.

        New values are placed at the tail of the internal list.

        >>> od = OrderedDict()
        >>> od[0] = 1
        >>> od[2] = 3
        >>> od
        OrderedDict([(0, 1), (2, 3)])
        """
        try:
            _getitem(self, key).value = (key, value)
        except KeyError as e:
            # NOTE: append new keys to the tail of the list
            node = self.__llist.insert_node(before=None, value=(key, value))
            _setitem(self, key, node)

    def __getitem__(self, key, _getitem=dict.__getitem__):
        """Get item in dictionary.

        >>> od = OrderedDict([(0, 1), (2, 3)])
        >>> od[0] == 1
        True
        >>> od[2] == 3
        True
        """
        try:
            return _getitem(self, key).value[1]
        except KeyError as e:
            raise

    def __delitem__(self, key, _delitem=dict.__delitem__, _getitem=dict.__getitem__):
        """Delete item in dictionary.

        >>> od = OrderedDict([(0, 1), (2, 3)])
        >>> od
        OrderedDict([(0, 1), (2, 3)])
        >>> del od[0]
        >>> od
        OrderedDict([(2, 3)])
        """
        node = _getitem(self, key)
        node.remove()
        _delitem(self, key)

    def __iter__(self):
        """Iterate over keys in dictionary.

        >>> od = OrderedDict([(0, 1), (2, 3)])
        >>> list(iter(od))
        [0, 2]
        """
        return (item[0] for item in self.__llist)

    def __reversed__(self):
        """Iterate over keys in dictionary in reverse order.

        >>> od = OrderedDict([(0, 1), (2, 3)])
        >>> list(reversed(od))
        [2, 0]
        """
        return (item[0] for item in reversed(self.__llist))

    def __repr__(self, _fmt="{0.__class__.__name__!s}({1!s})".format):
        return _fmt(self, list(self.items()) or '')

    def item_at(self, index):
        """Get at item tuple at a certain index.

        Does not support slice indexing.

        >>> od = OrderedDict([(12, 24), (-1, -2), ('some key', 'some value')])
        >>> od.item_at(2)
        ('some key', 'some value')
        >>> od.item_at(-1)
        ('some key', 'some value')
        >>> od.item_at(2) == ('some key', od['some key'])
        True
        """
        return self.__llist[index]

    def move_key(self, key, index, _getitem=dict.__getitem__):
        """Change ordering of ``key`` to be at ``index``.

        >>> od = OrderedDict([(12, 24), (-1, -2), ('some key', 'some value')])
        >>> od.item_at(2)
        ('some key', 'some value')
        >>> od.move_key(12, len(od))  # any index beyond the end is treated as the end
        >>> od.item_at(2)
        (12, 24)
        >>> od
        OrderedDict([(-1, -2), ('some key', 'some value'), (12, 24)])
        >>> od.move_key(-1, -1)  # move to just before the end using a negative index
        >>> od.item_at(2)
        (12, 24)
        >>> od
        OrderedDict([('some key', 'some value'), (-1, -2), (12, 24)])
        """
        node = _getitem(self, key)

        self_len = len(self)
        if index < 0:
            index = self_len + index

        if index >= self_len:
            before = None
        else:
            before = self.__llist.get_node(index)

        self.__llist.insert_node(before=before, node=node)

    # NOTE: methods that can be sourced from elsewhere
    popitem = _collections.OrderedDict.popitem

    copy = _collections.OrderedDict.copy

    fromkeys = _collections.OrderedDict.fromkeys

    update = _collections.MutableMapping.update

    __update = update  # let subclasses override update without breaking __init__

    pop = _collections.MutableMapping.pop

    get = _collections.MutableMapping.get

    clear = _collections.MutableMapping.clear

    setdefault = _collections.MutableMapping.setdefault

    # NOTE: return views, not lists
    def keys(self):
        return _collections.KeysView(self)
    viewkeys = iterkeys = keys

    def values(self):
        return _collections.ValuesView(self)
    viewvalues = itervalues = values

    def items(self):
        return _collections.ItemsView(self)
    viewitems = iteritems = items


# Code for ChainMap sourced from Python 3.4 standard library
# https://github.com/python/cpython/blob/3.7/Lib/collections/__init__.py
# This code is licensed under the PSFL since it was initially taken verbatim
# from the Python standard library.
@_add_to__all__
class ChainMap(_collections.MutableMapping):
    ''' A ChainMap groups multiple dicts (or other mappings) together
    to create a single, updateable view.

    The underlying mappings are stored in a list.  That list is public and can
    accessed or updated using the *maps* attribute.  There is no other state.

    Lookups search the underlying mappings successively until a key is found.
    In contrast, writes, updates, and deletions only operate on the first
    mapping.

    '''

    def __init__(self, *maps):
        '''Initialize a ChainMap by setting *maps* to the given mappings.
        If no mappings are provided, a single empty dictionary is used.

        '''
        self.maps = list(maps) or [{}]          # always at least one map

    def __missing__(self, key):
        raise KeyError(key)

    def __getitem__(self, key):
        for mapping in self.maps:
            try:
                return mapping[key]             # can't use 'key in mapping' with defaultdict
            except KeyError:
                pass
        return self.__missing__(key)            # support subclasses that define __missing__

    def get(self, key, default=None):
        return self[key] if key in self else default

    def __len__(self):
        return len(set().union(*self.maps))     # reuses stored hash values if possible

    def __iter__(self):
        return iter(set().union(*self.maps))

    def __contains__(self, key):
        return any(key in m for m in self.maps)

    def __nonzero__(self):
        return any(self.maps)

    __bool__ = __nonzero__

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

    @classmethod
    def fromkeys(cls, iterable, *args):
        'Create a ChainMap with a single dict created from the iterable.'
        return cls(dict.fromkeys(iterable, *args))

    def copy(self):
        'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]'
        return self.__class__(self.maps[0].copy(), *self.maps[1:])

    __copy__ = copy

    def new_child(self, m=None):                # like Django's Context.push()
        '''
        New ChainMap with a new map followed by all previous maps. If no
        map is provided, an empty dict is used.
        '''
        if m is None:
            m = {}
        return self.__class__(m, *self.maps)

    @property
    def parents(self):                          # like Django's Context.pop()
        'New ChainMap from maps[1:].'
        return self.__class__(*self.maps[1:])

    def __setitem__(self, key, value):
        self.maps[0][key] = value

    def __delitem__(self, key):
        try:
            del self.maps[0][key]
        except KeyError:
            raise KeyError('Key not found in the first mapping: {!r}'.format(key))

    def popitem(self):
        'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.'
        try:
            return self.maps[0].popitem()
        except KeyError:
            raise KeyError('No keys found in the first mapping.')

    def pop(self, key, *args):
        'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].'
        try:
            return self.maps[0].pop(key, *args)
        except KeyError:
            raise KeyError('Key not found in the first mapping: {!r}'.format(key))

    def clear(self):
        'Clear maps[0], leaving maps[1:] intact.'
        self.maps[0].clear()

    def in_which(self, key):
        'Return an iterator/generator yielding the indices of all maps with the given key in self.maps.'
        for i, m in enumerate(self.maps):
            if key in m:
                yield i


@_add_to__all__
class frozenmap(_collections.Mapping, _collections.Hashable):

    """An immutable, hashable map class.

    It is analagous to the builtin frozenset. In order for frozenmap to work,
    both keys AND values must be hashable. Instances of frozenmap can only
    compare equal to other instances of frozenmap containing the same items;
    other mapping types with the same items do not compare equal.
    """

    def __init__(self, *args, **kwargs):
        """Initialize self.

        >>> # keys AND values need not be hashable for frozenmap instances to be created
        >>> class NoHash(object): __hash__ = None  # unhashable class
        >>> nh = NoHash()
        >>> f1 = frozenmap({'unhashable': nh, 'hashable': 1})
        >>> # we can use keyword arguments just like a dictionary
        >>> f2 = frozenmap(unhashable=nh, hashable=1)
        >>> # we can use an iterable of pairs just like a dictionary
        >>> f2 = frozenmap([('unhashable', nh), ('hashable', 1)])
        """
        # NOTE: Don't worry about unhashable values yet
        self._map = dict(*args, **kwargs)

    def __repr__(self):
        """Return representation of self.

        >>> frozenmap({123:456})
        frozenmap({123: 456})
        >>> frozenmap()
        frozenmap()
        """
        return '{0.__class__.__name__}({1})'.format(self, self._map or '')

    def __getitem__(self, key):
        """Get value associated with "key" in self."""
        return self._map[key]

    def __iter__(self):
        """Iterate thru keys of self."""
        return iter(self._map)

    def __len__(self):
        """Return length of self."""
        return len(self._map)

    def __hash__(self):
        """Hash implementation.

        >>> f1 = frozenmap({'k':'v', 'key':'value', '1':2})
        >>> f2 = frozenmap(k2='v2', key2='value2', twelve=22)
        >>> f3 = frozenmap(f1)
        >>> f1 == f2
        False
        >>> hash(f1) == hash(f2)
        False
        >>> f1 == f3
        True
        >>> hash(f1) == hash(f3)
        True
        >>> f1 is f3
        False
        """
        stype = type(self)
        itemset = frozenset(self.items())
        return hash(stype) ^ hash(itemset)

    def __eq__(self, other):
        """Implement equals comparison operation."""
        return isinstance(other, frozenmap) and self._map == other._map


if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=True)