--- a/env/lib/python3.7/site-packages/boltons/dictutils.py	Thu May 14 16:47:39 2020 -0400
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,1085 +0,0 @@
-# -*- 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