diff env/lib/python3.9/site-packages/boltons/dictutils.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/boltons/dictutils.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,1085 @@
+# -*- coding: utf-8 -*-
+"""Python has a very powerful mapping type at its core: the :class:`dict`
+type. While versatile and featureful, the :class:`dict` prioritizes
+simplicity and performance. As a result, it does not retain the order
+of item insertion [1]_, nor does it store multiple values per key. It
+is a fast, unordered 1:1 mapping.
+
+The :class:`OrderedMultiDict` contrasts to the built-in :class:`dict`,
+as a relatively maximalist, ordered 1:n subtype of
+:class:`dict`. Virtually every feature of :class:`dict` has been
+retooled to be intuitive in the face of this added
+complexity. Additional methods have been added, such as
+:class:`collections.Counter`-like functionality.
+
+A prime advantage of the :class:`OrderedMultiDict` (OMD) is its
+non-destructive nature. Data can be added to an :class:`OMD` without being
+rearranged or overwritten. The property can allow the developer to
+work more freely with the data, as well as make more assumptions about
+where input data will end up in the output, all without any extra
+work.
+
+One great example of this is the :meth:`OMD.inverted()` method, which
+returns a new OMD with the values as keys and the keys as values. All
+the data and the respective order is still represented in the inverted
+form, all from an operation which would be outright wrong and reckless
+with a built-in :class:`dict` or :class:`collections.OrderedDict`.
+
+The OMD has been performance tuned to be suitable for a wide range of
+usages, including as a basic unordered MultiDict. Special
+thanks to `Mark Williams`_ for all his help.
+
+.. [1] As of 2015, `basic dicts on PyPy are ordered
+   <http://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html>`_,
+   and as of December 2017, `basic dicts in CPython 3 are now ordered
+   <https://mail.python.org/pipermail/python-dev/2017-December/151283.html>`_, as
+   well.
+.. _Mark Williams: https://github.com/markrwilliams
+
+"""
+
+try:
+    from collections.abc import KeysView, ValuesView, ItemsView
+except ImportError:
+    from collections import KeysView, ValuesView, ItemsView
+
+import itertools
+
+try:
+    from itertools import izip_longest
+except ImportError:
+    from itertools import zip_longest as izip_longest
+
+try:
+    from typeutils import make_sentinel
+    _MISSING = make_sentinel(var_name='_MISSING')
+except ImportError:
+    _MISSING = object()
+
+
+PREV, NEXT, KEY, VALUE, SPREV, SNEXT = range(6)
+
+
+__all__ = ['MultiDict', 'OMD', 'OrderedMultiDict', 'OneToOne', 'ManyToMany', 'subdict', 'FrozenDict']
+
+try:
+    profile
+except NameError:
+    profile = lambda x: x
+
+
+class OrderedMultiDict(dict):
+    """A MultiDict is a dictionary that can have multiple values per key
+    and the OrderedMultiDict (OMD) is a MultiDict that retains
+    original insertion order. Common use cases include:
+
+      * handling query strings parsed from URLs
+      * inverting a dictionary to create a reverse index (values to keys)
+      * stacking data from multiple dictionaries in a non-destructive way
+
+    The OrderedMultiDict constructor is identical to the built-in
+    :class:`dict`, and overall the API constitutes an intuitive
+    superset of the built-in type:
+
+    >>> omd = OrderedMultiDict()
+    >>> omd['a'] = 1
+    >>> omd['b'] = 2
+    >>> omd.add('a', 3)
+    >>> omd.get('a')
+    3
+    >>> omd.getlist('a')
+    [1, 3]
+
+    Some non-:class:`dict`-like behaviors also make an appearance,
+    such as support for :func:`reversed`:
+
+    >>> list(reversed(omd))
+    ['b', 'a']
+
+    Note that unlike some other MultiDicts, this OMD gives precedence
+    to the most recent value added. ``omd['a']`` refers to ``3``, not
+    ``1``.
+
+    >>> omd
+    OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)])
+    >>> omd.poplast('a')
+    3
+    >>> omd
+    OrderedMultiDict([('a', 1), ('b', 2)])
+    >>> omd.pop('a')
+    1
+    >>> omd
+    OrderedMultiDict([('b', 2)])
+
+    If you want a safe-to-modify or flat dictionary, use
+    :meth:`OrderedMultiDict.todict()`.
+
+    >>> from pprint import pprint as pp  # preserve printed ordering
+    >>> omd = OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)])
+    >>> pp(omd.todict())
+    {'a': 3, 'b': 2}
+    >>> pp(omd.todict(multi=True))
+    {'a': [1, 3], 'b': [2]}
+
+    With ``multi=False``, items appear with the keys in to original
+    insertion order, alongside the most-recently inserted value for
+    that key.
+
+    >>> OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)]).items(multi=False)
+    [('a', 3), ('b', 2)]
+
+    .. warning::
+
+       ``dict(omd)`` changed behavior `in Python 3.7
+       <https://bugs.python.org/issue34320>`_ due to changes made to
+       support the transition from :class:`collections.OrderedDict` to
+       the built-in dictionary being ordered. Before 3.7, the result
+       would be a new dictionary, with values that were lists, similar
+       to ``omd.todict(multi=True)`` (but only shallow-copy; the lists
+       were direct references to OMD internal structures). From 3.7
+       onward, the values became singular, like
+       ``omd.todict(multi=False)``. For reliable cross-version
+       behavior, just use :meth:`~OrderedMultiDict.todict()`.
+
+    """
+    def __init__(self, *args, **kwargs):
+        if len(args) > 1:
+            raise TypeError('%s expected at most 1 argument, got %s'
+                            % (self.__class__.__name__, len(args)))
+        super(OrderedMultiDict, self).__init__()
+
+        self._clear_ll()
+        if args:
+            self.update_extend(args[0])
+        if kwargs:
+            self.update(kwargs)
+
+    def _clear_ll(self):
+        try:
+            _map = self._map
+        except AttributeError:
+            _map = self._map = {}
+            self.root = []
+        _map.clear()
+        self.root[:] = [self.root, self.root, None]
+
+    def _insert(self, k, v):
+        root = self.root
+        cells = self._map.setdefault(k, [])
+        last = root[PREV]
+        cell = [last, root, k, v]
+        last[NEXT] = root[PREV] = cell
+        cells.append(cell)
+
+    def add(self, k, v):
+        """Add a single value *v* under a key *k*. Existing values under *k*
+        are preserved.
+        """
+        values = super(OrderedMultiDict, self).setdefault(k, [])
+        self._insert(k, v)
+        values.append(v)
+
+    def addlist(self, k, v):
+        """Add an iterable of values underneath a specific key, preserving
+        any values already under that key.
+
+        >>> omd = OrderedMultiDict([('a', -1)])
+        >>> omd.addlist('a', range(3))
+        >>> omd
+        OrderedMultiDict([('a', -1), ('a', 0), ('a', 1), ('a', 2)])
+
+        Called ``addlist`` for consistency with :meth:`getlist`, but
+        tuples and other sequences and iterables work.
+        """
+        self_insert = self._insert
+        values = super(OrderedMultiDict, self).setdefault(k, [])
+        for subv in v:
+            self_insert(k, subv)
+        values.extend(v)
+
+    def get(self, k, default=None):
+        """Return the value for key *k* if present in the dictionary, else
+        *default*. If *default* is not given, ``None`` is returned.
+        This method never raises a :exc:`KeyError`.
+
+        To get all values under a key, use :meth:`OrderedMultiDict.getlist`.
+        """
+        return super(OrderedMultiDict, self).get(k, [default])[-1]
+
+    def getlist(self, k, default=_MISSING):
+        """Get all values for key *k* as a list, if *k* is in the
+        dictionary, else *default*. The list returned is a copy and
+        can be safely mutated. If *default* is not given, an empty
+        :class:`list` is returned.
+        """
+        try:
+            return super(OrderedMultiDict, self).__getitem__(k)[:]
+        except KeyError:
+            if default is _MISSING:
+                return []
+            return default
+
+    def clear(self):
+        "Empty the dictionary."
+        super(OrderedMultiDict, self).clear()
+        self._clear_ll()
+
+    def setdefault(self, k, default=_MISSING):
+        """If key *k* is in the dictionary, return its value. If not, insert
+        *k* with a value of *default* and return *default*. *default*
+        defaults to ``None``. See :meth:`dict.setdefault` for more
+        information.
+        """
+        if not super(OrderedMultiDict, self).__contains__(k):
+            self[k] = None if default is _MISSING else default
+        return self[k]
+
+    def copy(self):
+        "Return a shallow copy of the dictionary."
+        return self.__class__(self.iteritems(multi=True))
+
+    @classmethod
+    def fromkeys(cls, keys, default=None):
+        """Create a dictionary from a list of keys, with all the values
+        set to *default*, or ``None`` if *default* is not set.
+        """
+        return cls([(k, default) for k in keys])
+
+    def update(self, E, **F):
+        """Add items from a dictionary or iterable (and/or keyword arguments),
+        overwriting values under an existing key. See
+        :meth:`dict.update` for more details.
+        """
+        # E and F are throwback names to the dict() __doc__
+        if E is self:
+            return
+        self_add = self.add
+        if isinstance(E, OrderedMultiDict):
+            for k in E:
+                if k in self:
+                    del self[k]
+            for k, v in E.iteritems(multi=True):
+                self_add(k, v)
+        elif callable(getattr(E, 'keys', None)):
+            for k in E.keys():
+                self[k] = E[k]
+        else:
+            seen = set()
+            seen_add = seen.add
+            for k, v in E:
+                if k not in seen and k in self:
+                    del self[k]
+                    seen_add(k)
+                self_add(k, v)
+        for k in F:
+            self[k] = F[k]
+        return
+
+    def update_extend(self, E, **F):
+        """Add items from a dictionary, iterable, and/or keyword
+        arguments without overwriting existing items present in the
+        dictionary. Like :meth:`update`, but adds to existing keys
+        instead of overwriting them.
+        """
+        if E is self:
+            iterator = iter(E.items())
+        elif isinstance(E, OrderedMultiDict):
+            iterator = E.iteritems(multi=True)
+        elif hasattr(E, 'keys'):
+            iterator = ((k, E[k]) for k in E.keys())
+        else:
+            iterator = E
+
+        self_add = self.add
+        for k, v in iterator:
+            self_add(k, v)
+
+    def __setitem__(self, k, v):
+        if super(OrderedMultiDict, self).__contains__(k):
+            self._remove_all(k)
+        self._insert(k, v)
+        super(OrderedMultiDict, self).__setitem__(k, [v])
+
+    def __getitem__(self, k):
+        return super(OrderedMultiDict, self).__getitem__(k)[-1]
+
+    def __delitem__(self, k):
+        super(OrderedMultiDict, self).__delitem__(k)
+        self._remove_all(k)
+
+    def __eq__(self, other):
+        if self is other:
+            return True
+        try:
+            if len(other) != len(self):
+                return False
+        except TypeError:
+            return False
+        if isinstance(other, OrderedMultiDict):
+            selfi = self.iteritems(multi=True)
+            otheri = other.iteritems(multi=True)
+            zipped_items = izip_longest(selfi, otheri, fillvalue=(None, None))
+            for (selfk, selfv), (otherk, otherv) in zipped_items:
+                if selfk != otherk or selfv != otherv:
+                    return False
+            if not(next(selfi, _MISSING) is _MISSING
+                   and next(otheri, _MISSING) is _MISSING):
+                # leftovers  (TODO: watch for StopIteration?)
+                return False
+            return True
+        elif hasattr(other, 'keys'):
+            for selfk in self:
+                try:
+                    other[selfk] == self[selfk]
+                except KeyError:
+                    return False
+            return True
+        return False
+
+    def __ne__(self, other):
+        return not (self == other)
+
+    def pop(self, k, default=_MISSING):
+        """Remove all values under key *k*, returning the most-recently
+        inserted value. Raises :exc:`KeyError` if the key is not
+        present and no *default* is provided.
+        """
+        try:
+            return self.popall(k)[-1]
+        except KeyError:
+            if default is _MISSING:
+                raise KeyError(k)
+        return default
+
+    def popall(self, k, default=_MISSING):
+        """Remove all values under key *k*, returning them in the form of
+        a list. Raises :exc:`KeyError` if the key is not present and no
+        *default* is provided.
+        """
+        super_self = super(OrderedMultiDict, self)
+        if super_self.__contains__(k):
+            self._remove_all(k)
+        if default is _MISSING:
+            return super_self.pop(k)
+        return super_self.pop(k, default)
+
+    def poplast(self, k=_MISSING, default=_MISSING):
+        """Remove and return the most-recently inserted value under the key
+        *k*, or the most-recently inserted key if *k* is not
+        provided. If no values remain under *k*, it will be removed
+        from the OMD.  Raises :exc:`KeyError` if *k* is not present in
+        the dictionary, or the dictionary is empty.
+        """
+        if k is _MISSING:
+            if self:
+                k = self.root[PREV][KEY]
+            else:
+                raise KeyError('empty %r' % type(self))
+        try:
+            self._remove(k)
+        except KeyError:
+            if default is _MISSING:
+                raise KeyError(k)
+            return default
+        values = super(OrderedMultiDict, self).__getitem__(k)
+        v = values.pop()
+        if not values:
+            super(OrderedMultiDict, self).__delitem__(k)
+        return v
+
+    def _remove(self, k):
+        values = self._map[k]
+        cell = values.pop()
+        cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
+        if not values:
+            del self._map[k]
+
+    def _remove_all(self, k):
+        values = self._map[k]
+        while values:
+            cell = values.pop()
+            cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
+        del self._map[k]
+
+    def iteritems(self, multi=False):
+        """Iterate over the OMD's items in insertion order. By default,
+        yields only the most-recently inserted value for each key. Set
+        *multi* to ``True`` to get all inserted items.
+        """
+        root = self.root
+        curr = root[NEXT]
+        if multi:
+            while curr is not root:
+                yield curr[KEY], curr[VALUE]
+                curr = curr[NEXT]
+        else:
+            for key in self.iterkeys():
+                yield key, self[key]
+
+    def iterkeys(self, multi=False):
+        """Iterate over the OMD's keys in insertion order. By default, yields
+        each key once, according to the most recent insertion. Set
+        *multi* to ``True`` to get all keys, including duplicates, in
+        insertion order.
+        """
+        root = self.root
+        curr = root[NEXT]
+        if multi:
+            while curr is not root:
+                yield curr[KEY]
+                curr = curr[NEXT]
+        else:
+            yielded = set()
+            yielded_add = yielded.add
+            while curr is not root:
+                k = curr[KEY]
+                if k not in yielded:
+                    yielded_add(k)
+                    yield k
+                curr = curr[NEXT]
+
+    def itervalues(self, multi=False):
+        """Iterate over the OMD's values in insertion order. By default,
+        yields the most-recently inserted value per unique key.  Set
+        *multi* to ``True`` to get all values according to insertion
+        order.
+        """
+        for k, v in self.iteritems(multi=multi):
+            yield v
+
+    def todict(self, multi=False):
+        """Gets a basic :class:`dict` of the items in this dictionary. Keys
+        are the same as the OMD, values are the most recently inserted
+        values for each key.
+
+        Setting the *multi* arg to ``True`` is yields the same
+        result as calling :class:`dict` on the OMD, except that all the
+        value lists are copies that can be safely mutated.
+        """
+        if multi:
+            return dict([(k, self.getlist(k)) for k in self])
+        return dict([(k, self[k]) for k in self])
+
+    def sorted(self, key=None, reverse=False):
+        """Similar to the built-in :func:`sorted`, except this method returns
+        a new :class:`OrderedMultiDict` sorted by the provided key
+        function, optionally reversed.
+
+        Args:
+            key (callable): A callable to determine the sort key of
+              each element. The callable should expect an **item**
+              (key-value pair tuple).
+            reverse (bool): Set to ``True`` to reverse the ordering.
+
+        >>> omd = OrderedMultiDict(zip(range(3), range(3)))
+        >>> omd.sorted(reverse=True)
+        OrderedMultiDict([(2, 2), (1, 1), (0, 0)])
+
+        Note that the key function receives an **item** (key-value
+        tuple), so the recommended signature looks like:
+
+        >>> omd = OrderedMultiDict(zip('hello', 'world'))
+        >>> omd.sorted(key=lambda i: i[1])  # i[0] is the key, i[1] is the val
+        OrderedMultiDict([('o', 'd'), ('l', 'l'), ('e', 'o'), ('l', 'r'), ('h', 'w')])
+        """
+        cls = self.__class__
+        return cls(sorted(self.iteritems(multi=True), key=key, reverse=reverse))
+
+    def sortedvalues(self, key=None, reverse=False):
+        """Returns a copy of the :class:`OrderedMultiDict` with the same keys
+        in the same order as the original OMD, but the values within
+        each keyspace have been sorted according to *key* and
+        *reverse*.
+
+        Args:
+            key (callable): A single-argument callable to determine
+              the sort key of each element. The callable should expect
+              an **item** (key-value pair tuple).
+            reverse (bool): Set to ``True`` to reverse the ordering.
+
+        >>> omd = OrderedMultiDict()
+        >>> omd.addlist('even', [6, 2])
+        >>> omd.addlist('odd', [1, 5])
+        >>> omd.add('even', 4)
+        >>> omd.add('odd', 3)
+        >>> somd = omd.sortedvalues()
+        >>> somd.getlist('even')
+        [2, 4, 6]
+        >>> somd.keys(multi=True) == omd.keys(multi=True)
+        True
+        >>> omd == somd
+        False
+        >>> somd
+        OrderedMultiDict([('even', 2), ('even', 4), ('odd', 1), ('odd', 3), ('even', 6), ('odd', 5)])
+
+        As demonstrated above, contents and key order are
+        retained. Only value order changes.
+        """
+        try:
+            superself_iteritems = super(OrderedMultiDict, self).iteritems()
+        except AttributeError:
+            superself_iteritems = super(OrderedMultiDict, self).items()
+        # (not reverse) because they pop off in reverse order for reinsertion
+        sorted_val_map = dict([(k, sorted(v, key=key, reverse=(not reverse)))
+                               for k, v in superself_iteritems])
+        ret = self.__class__()
+        for k in self.iterkeys(multi=True):
+            ret.add(k, sorted_val_map[k].pop())
+        return ret
+
+    def inverted(self):
+        """Returns a new :class:`OrderedMultiDict` with values and keys
+        swapped, like creating dictionary transposition or reverse
+        index.  Insertion order is retained and all keys and values
+        are represented in the output.
+
+        >>> omd = OMD([(0, 2), (1, 2)])
+        >>> omd.inverted().getlist(2)
+        [0, 1]
+
+        Inverting twice yields a copy of the original:
+
+        >>> omd.inverted().inverted()
+        OrderedMultiDict([(0, 2), (1, 2)])
+        """
+        return self.__class__((v, k) for k, v in self.iteritems(multi=True))
+
+    def counts(self):
+        """Returns a mapping from key to number of values inserted under that
+        key. Like :py:class:`collections.Counter`, but returns a new
+        :class:`OrderedMultiDict`.
+        """
+        # Returns an OMD because Counter/OrderedDict may not be
+        # available, and neither Counter nor dict maintain order.
+        super_getitem = super(OrderedMultiDict, self).__getitem__
+        return self.__class__((k, len(super_getitem(k))) for k in self)
+
+    def keys(self, multi=False):
+        """Returns a list containing the output of :meth:`iterkeys`.  See
+        that method's docs for more details.
+        """
+        return list(self.iterkeys(multi=multi))
+
+    def values(self, multi=False):
+        """Returns a list containing the output of :meth:`itervalues`.  See
+        that method's docs for more details.
+        """
+        return list(self.itervalues(multi=multi))
+
+    def items(self, multi=False):
+        """Returns a list containing the output of :meth:`iteritems`.  See
+        that method's docs for more details.
+        """
+        return list(self.iteritems(multi=multi))
+
+    def __iter__(self):
+        return self.iterkeys()
+
+    def __reversed__(self):
+        root = self.root
+        curr = root[PREV]
+        lengths = {}
+        lengths_sd = lengths.setdefault
+        get_values = super(OrderedMultiDict, self).__getitem__
+        while curr is not root:
+            k = curr[KEY]
+            vals = get_values(k)
+            if lengths_sd(k, 1) == len(vals):
+                yield k
+            lengths[k] += 1
+            curr = curr[PREV]
+
+    def __repr__(self):
+        cn = self.__class__.__name__
+        kvs = ', '.join([repr((k, v)) for k, v in self.iteritems(multi=True)])
+        return '%s([%s])' % (cn, kvs)
+
+    def viewkeys(self):
+        "OMD.viewkeys() -> a set-like object providing a view on OMD's keys"
+        return KeysView(self)
+
+    def viewvalues(self):
+        "OMD.viewvalues() -> an object providing a view on OMD's values"
+        return ValuesView(self)
+
+    def viewitems(self):
+        "OMD.viewitems() -> a set-like object providing a view on OMD's items"
+        return ItemsView(self)
+
+
+# A couple of convenient aliases
+OMD = OrderedMultiDict
+MultiDict = OrderedMultiDict
+
+
+class FastIterOrderedMultiDict(OrderedMultiDict):
+    """An OrderedMultiDict backed by a skip list.  Iteration over keys
+    is faster and uses constant memory but adding duplicate key-value
+    pairs is slower. Brainchild of Mark Williams.
+    """
+    def _clear_ll(self):
+        # TODO: always reset objects? (i.e., no else block below)
+        try:
+            _map = self._map
+        except AttributeError:
+            _map = self._map = {}
+            self.root = []
+        _map.clear()
+        self.root[:] = [self.root, self.root,
+                        None, None,
+                        self.root, self.root]
+
+    def _insert(self, k, v):
+        root = self.root
+        empty = []
+        cells = self._map.setdefault(k, empty)
+        last = root[PREV]
+
+        if cells is empty:
+            cell = [last, root,
+                    k, v,
+                    last, root]
+            # was the last one skipped?
+            if last[SPREV][SNEXT] is root:
+                last[SPREV][SNEXT] = cell
+            last[NEXT] = last[SNEXT] = root[PREV] = root[SPREV] = cell
+            cells.append(cell)
+        else:
+            # if the previous was skipped, go back to the cell that
+            # skipped it
+            sprev = last[SPREV] if (last[SPREV][SNEXT] is not last) else last
+            cell = [last, root,
+                    k, v,
+                    sprev, root]
+            # skip me
+            last[SNEXT] = root
+            last[NEXT] = root[PREV] = root[SPREV] = cell
+            cells.append(cell)
+
+    def _remove(self, k):
+        cells = self._map[k]
+        cell = cells.pop()
+        if not cells:
+            del self._map[k]
+            cell[PREV][SNEXT] = cell[SNEXT]
+
+        if cell[PREV][SPREV][SNEXT] is cell:
+            cell[PREV][SPREV][SNEXT] = cell[NEXT]
+        elif cell[SNEXT] is cell[NEXT]:
+            cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV]
+
+        cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
+
+    def _remove_all(self, k):
+        cells = self._map.pop(k)
+        while cells:
+            cell = cells.pop()
+            if cell[PREV][SPREV][SNEXT] is cell:
+                cell[PREV][SPREV][SNEXT] = cell[NEXT]
+            elif cell[SNEXT] is cell[NEXT]:
+                cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV]
+
+            cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV]
+        cell[PREV][SNEXT] = cell[SNEXT]
+
+    def iteritems(self, multi=False):
+        next_link = NEXT if multi else SNEXT
+        root = self.root
+        curr = root[next_link]
+        while curr is not root:
+            yield curr[KEY], curr[VALUE]
+            curr = curr[next_link]
+
+    def iterkeys(self, multi=False):
+        next_link = NEXT if multi else SNEXT
+        root = self.root
+        curr = root[next_link]
+        while curr is not root:
+            yield curr[KEY]
+            curr = curr[next_link]
+
+    def __reversed__(self):
+        root = self.root
+        curr = root[PREV]
+        while curr is not root:
+            if curr[SPREV][SNEXT] is not curr:
+                curr = curr[SPREV]
+                if curr is root:
+                    break
+            yield curr[KEY]
+            curr = curr[PREV]
+
+
+_OTO_INV_MARKER = object()
+_OTO_UNIQUE_MARKER = object()
+
+
+class OneToOne(dict):
+    """Implements a one-to-one mapping dictionary. In addition to
+    inheriting from and behaving exactly like the builtin
+    :class:`dict`, all values are automatically added as keys on a
+    reverse mapping, available as the `inv` attribute. This
+    arrangement keeps key and value namespaces distinct.
+
+    Basic operations are intuitive:
+
+    >>> oto = OneToOne({'a': 1, 'b': 2})
+    >>> print(oto['a'])
+    1
+    >>> print(oto.inv[1])
+    a
+    >>> len(oto)
+    2
+
+    Overwrites happens in both directions:
+
+    >>> oto.inv[1] = 'c'
+    >>> print(oto.get('a'))
+    None
+    >>> len(oto)
+    2
+
+    For a very similar project, with even more one-to-one
+    functionality, check out `bidict <https://github.com/jab/bidict>`_.
+    """
+    __slots__ = ('inv',)
+
+    def __init__(self, *a, **kw):
+        raise_on_dupe = False
+        if a:
+            if a[0] is _OTO_INV_MARKER:
+                self.inv = a[1]
+                dict.__init__(self, [(v, k) for k, v in self.inv.items()])
+                return
+            elif a[0] is _OTO_UNIQUE_MARKER:
+                a, raise_on_dupe = a[1:], True
+
+        dict.__init__(self, *a, **kw)
+        self.inv = self.__class__(_OTO_INV_MARKER, self)
+
+        if len(self) == len(self.inv):
+            # if lengths match, that means everything's unique
+            return
+
+        if not raise_on_dupe:
+            dict.clear(self)
+            dict.update(self, [(v, k) for k, v in self.inv.items()])
+            return
+
+        # generate an error message if the values aren't 1:1
+
+        val_multidict = {}
+        for k, v in self.items():
+            val_multidict.setdefault(v, []).append(k)
+
+        dupes = dict([(v, k_list) for v, k_list in
+                      val_multidict.items() if len(k_list) > 1])
+
+        raise ValueError('expected unique values, got multiple keys for'
+                         ' the following values: %r' % dupes)
+
+    @classmethod
+    def unique(cls, *a, **kw):
+        """This alternate constructor for OneToOne will raise an exception
+        when input values overlap. For instance:
+
+        >>> OneToOne.unique({'a': 1, 'b': 1})
+        Traceback (most recent call last):
+        ...
+        ValueError: expected unique values, got multiple keys for the following values: ...
+
+        This even works across inputs:
+
+        >>> a_dict = {'a': 2}
+        >>> OneToOne.unique(a_dict, b=2)
+        Traceback (most recent call last):
+        ...
+        ValueError: expected unique values, got multiple keys for the following values: ...
+        """
+        return cls(_OTO_UNIQUE_MARKER, *a, **kw)
+
+    def __setitem__(self, key, val):
+        hash(val)  # ensure val is a valid key
+        if key in self:
+            dict.__delitem__(self.inv, self[key])
+        if val in self.inv:
+            del self.inv[val]
+        dict.__setitem__(self, key, val)
+        dict.__setitem__(self.inv, val, key)
+
+    def __delitem__(self, key):
+        dict.__delitem__(self.inv, self[key])
+        dict.__delitem__(self, key)
+
+    def clear(self):
+        dict.clear(self)
+        dict.clear(self.inv)
+
+    def copy(self):
+        return self.__class__(self)
+
+    def pop(self, key, default=_MISSING):
+        if key in self:
+            dict.__delitem__(self.inv, self[key])
+            return dict.pop(self, key)
+        if default is not _MISSING:
+            return default
+        raise KeyError()
+
+    def popitem(self):
+        key, val = dict.popitem(self)
+        dict.__delitem__(self.inv, val)
+        return key, val
+
+    def setdefault(self, key, default=None):
+        if key not in self:
+            self[key] = default
+        return self[key]
+
+    def update(self, dict_or_iterable, **kw):
+        if isinstance(dict_or_iterable, dict):
+            for val in dict_or_iterable.values():
+                hash(val)
+                keys_vals = list(dict_or_iterable.items())
+        else:
+            for key, val in dict_or_iterable:
+                hash(key)
+                hash(val)
+                keys_vals = list(dict_or_iterable)
+        for val in kw.values():
+            hash(val)
+        keys_vals.extend(kw.items())
+        for key, val in keys_vals:
+            self[key] = val
+
+    def __repr__(self):
+        cn = self.__class__.__name__
+        dict_repr = dict.__repr__(self)
+        return "%s(%s)" % (cn, dict_repr)
+
+
+# marker for the secret handshake used internally to set up the invert ManyToMany
+_PAIRING = object()
+
+
+class ManyToMany(object):
+    """
+    a dict-like entity that represents a many-to-many relationship
+    between two groups of objects
+
+    behaves like a dict-of-tuples; also has .inv which is kept
+    up to date which is a dict-of-tuples in the other direction
+
+    also, can be used as a directed graph among hashable python objects
+    """
+    def __init__(self, items=None):
+        self.data = {}
+        if type(items) is tuple and items and items[0] is _PAIRING:
+            self.inv = items[1]
+        else:
+            self.inv = self.__class__((_PAIRING, self))
+            if items:
+                self.update(items)
+        return
+
+    def get(self, key, default=frozenset()):
+        try:
+            return self[key]
+        except KeyError:
+            return default
+
+    def __getitem__(self, key):
+        return frozenset(self.data[key])
+
+    def __setitem__(self, key, vals):
+        vals = set(vals)
+        if key in self:
+            to_remove = self.data[key] - vals
+            vals -= self.data[key]
+            for val in to_remove:
+                self.remove(key, val)
+        for val in vals:
+            self.add(key, val)
+
+    def __delitem__(self, key):
+        for val in self.data.pop(key):
+            self.inv.data[val].remove(key)
+            if not self.inv.data[val]:
+                del self.inv.data[val]
+
+    def update(self, iterable):
+        """given an iterable of (key, val), add them all"""
+        if type(iterable) is type(self):
+            other = iterable
+            for k in other.data:
+                if k not in self.data:
+                    self.data[k] = other.data[k]
+                else:
+                    self.data[k].update(other.data[k])
+            for k in other.inv.data:
+                if k not in self.inv.data:
+                    self.inv.data[k] = other.inv.data[k]
+                else:
+                    self.inv.data[k].update(other.inv.data[k])
+        elif callable(getattr(iterable, 'keys', None)):
+            for k in iterable.keys():
+                self.add(k, iterable[k])
+        else:
+            for key, val in iterable:
+                self.add(key, val)
+        return
+
+    def add(self, key, val):
+        if key not in self.data:
+            self.data[key] = set()
+        self.data[key].add(val)
+        if val not in self.inv.data:
+            self.inv.data[val] = set()
+        self.inv.data[val].add(key)
+
+    def remove(self, key, val):
+        self.data[key].remove(val)
+        if not self.data[key]:
+            del self.data[key]
+        self.inv.data[val].remove(key)
+        if not self.inv.data[val]:
+            del self.inv.data[val]
+
+    def replace(self, key, newkey):
+        """
+        replace instances of key by newkey
+        """
+        if key not in self.data:
+            return
+        self.data[newkey] = fwdset = self.data.pop(key)
+        for val in fwdset:
+            revset = self.inv.data[val]
+            revset.remove(key)
+            revset.add(newkey)
+
+    def iteritems(self):
+        for key in self.data:
+            for val in self.data[key]:
+                yield key, val
+
+    def keys(self):
+        return self.data.keys()
+
+    def __contains__(self, key):
+        return key in self.data
+
+    def __iter__(self):
+        return self.data.__iter__()
+
+    def __len__(self):
+        return self.data.__len__()
+
+    def __eq__(self, other):
+        return type(self) == type(other) and self.data == other.data
+
+    def __repr__(self):
+        cn = self.__class__.__name__
+        return '%s(%r)' % (cn, list(self.iteritems()))
+
+
+def subdict(d, keep=None, drop=None):
+    """Compute the "subdictionary" of a dict, *d*.
+
+    A subdict is to a dict what a subset is a to set. If *A* is a
+    subdict of *B*, that means that all keys of *A* are present in
+    *B*.
+
+    Returns a new dict with any keys in *drop* removed, and any keys
+    in *keep* still present, provided they were in the original
+    dict. *keep* defaults to all keys, *drop* defaults to empty, so
+    without one of these arguments, calling this function is
+    equivalent to calling ``dict()``.
+
+    >>> from pprint import pprint as pp
+    >>> pp(subdict({'a': 1, 'b': 2}))
+    {'a': 1, 'b': 2}
+    >>> subdict({'a': 1, 'b': 2, 'c': 3}, drop=['b', 'c'])
+    {'a': 1}
+    >>> pp(subdict({'a': 1, 'b': 2, 'c': 3}, keep=['a', 'c']))
+    {'a': 1, 'c': 3}
+
+    """
+    if keep is None:
+        keep = d.keys()
+    if drop is None:
+        drop = []
+
+    keys = set(keep) - set(drop)
+
+    return type(d)([(k, v) for k, v in d.items() if k in keys])
+
+
+class FrozenHashError(TypeError):
+    pass
+
+
+class FrozenDict(dict):
+    """An immutable dict subtype that is hashable and can itself be used
+    as a :class:`dict` key or :class:`set` entry. What
+    :class:`frozenset` is to :class:`set`, FrozenDict is to
+    :class:`dict`.
+
+    There was once an attempt to introduce such a type to the standard
+    library, but it was rejected: `PEP 416 <https://www.python.org/dev/peps/pep-0416/>`_.
+
+    Because FrozenDict is a :class:`dict` subtype, it automatically
+    works everywhere a dict would, including JSON serialization.
+
+    """
+    __slots__ = ('_hash',)
+
+    def updated(self, *a, **kw):
+        """Make a copy and add items from a dictionary or iterable (and/or
+        keyword arguments), overwriting values under an existing
+        key. See :meth:`dict.update` for more details.
+        """
+        data = dict(self)
+        data.update(*a, **kw)
+        return type(self)(data)
+
+    @classmethod
+    def fromkeys(cls, keys, value=None):
+        # one of the lesser known and used/useful dict methods
+        return cls(dict.fromkeys(keys, value))
+
+    def __repr__(self):
+        cn = self.__class__.__name__
+        return '%s(%s)' % (cn, dict.__repr__(self))
+
+    def __reduce_ex__(self, protocol):
+        return type(self), (dict(self),)
+
+    def __hash__(self):
+        try:
+            ret = self._hash
+        except AttributeError:
+            try:
+                ret = self._hash = hash(frozenset(self.items()))
+            except Exception as e:
+                ret = self._hash = FrozenHashError(e)
+
+        if ret.__class__ is FrozenHashError:
+            raise ret
+
+        return ret
+
+    def __copy__(self):
+        return self  # immutable types don't copy, see tuple's behavior
+
+    # block everything else
+    def _raise_frozen_typeerror(self, *a, **kw):
+        "raises a TypeError, because FrozenDicts are immutable"
+        raise TypeError('%s object is immutable' % self.__class__.__name__)
+
+    __setitem__ = __delitem__ = update = _raise_frozen_typeerror
+    setdefault = pop = popitem = clear = _raise_frozen_typeerror
+
+    del _raise_frozen_typeerror
+
+
+# end dictutils.py