Source code for bidict._orderedbidict

# Copyright 2009-2024 Joshua Bronson. All rights reserved.
# This Source Code Form is subject to the terms of the Mozilla Public
# License, v. 2.0. If a copy of the MPL was not distributed with this
# file, You can obtain one at

#                             * Code review nav *
#                        (see comments in
# ============================================================================
# ← Prev:   Current:                   <FIN>
# ============================================================================

"""Provide :class:`OrderedBidict`."""

from __future__ import annotations

import typing as t
from import Set

from ._base import BidictKeysView
from ._bidict import MutableBidict
from ._orderedbase import OrderedBidictBase
from ._typing import KT
from ._typing import VT

class OrderedBidict(OrderedBidictBase[KT, VT], MutableBidict[KT, VT]):
    """Mutable bidict type that maintains items in insertion order."""


        def inverse(self) -> OrderedBidict[VT, KT]: ...

        def inv(self) -> OrderedBidict[VT, KT]: ...

[docs] def clear(self) -> None: """Remove all items.""" super().clear() self._node_by_korv.clear() self._sntl.nxt = self._sntl.prv = self._sntl
def _pop(self, key: KT) -> VT: val = super()._pop(key) node = self._node_by_korv[key if self._bykey else val] self._dissoc_node(node) return val
[docs] def popitem(self, last: bool = True) -> tuple[KT, VT]: """*b.popitem() → (k, v)* If *last* is true, remove and return the most recently added item as a (key, value) pair. Otherwise, remove and return the least recently added item. :raises KeyError: if *b* is empty. """ if not self: raise KeyError('OrderedBidict is empty') node = getattr(self._sntl, 'prv' if last else 'nxt') korv = self._node_by_korv.inverse[node] if self._bykey: return korv, self._pop(korv) return self.inverse._pop(korv), korv
[docs] def move_to_end(self, key: KT, last: bool = True) -> None: """Move the item with the given key to the end if *last* is true, else to the beginning. :raises KeyError: if *key* is missing """ korv = key if self._bykey else self._fwdm[key] node = self._node_by_korv[korv] node.prv.nxt = node.nxt node.nxt.prv = node.prv sntl = self._sntl if last: lastnode = sntl.prv node.prv = lastnode node.nxt = sntl sntl.prv = lastnode.nxt = node else: firstnode = sntl.nxt node.prv = sntl node.nxt = firstnode sntl.nxt = firstnode.prv = node
# Override the keys() and items() implementations inherited from BidictBase, # which may delegate to the backing _fwdm dict, since this is a mutable ordered bidict, # and therefore the ordering of items can get out of sync with the backing mappings # after mutation. (Need not override values() because it delegates to .inverse.keys().)
[docs] def keys(self) -> t.KeysView[KT]: """A set-like object providing a view on the contained keys.""" return _OrderedBidictKeysView(self)
[docs] def items(self) -> t.ItemsView[KT, VT]: """A set-like object providing a view on the contained items.""" return _OrderedBidictItemsView(self)
# The following MappingView implementations use the __iter__ implementations # inherited from their superclass counterparts in, so they # continue to yield items in the correct order even after an OrderedBidict # is mutated. They also provide a __reversed__ implementation, which is not # provided by the superclasses. class _OrderedBidictKeysView(BidictKeysView[KT]): _mapping: OrderedBidict[KT, t.Any] def __reversed__(self) -> t.Iterator[KT]: return reversed(self._mapping) class _OrderedBidictItemsView(t.ItemsView[KT, VT]): _mapping: OrderedBidict[KT, VT] def __reversed__(self) -> t.Iterator[tuple[KT, VT]]: ob = self._mapping for key in reversed(ob): yield key, ob[key] # For better performance, make _OrderedBidictKeysView and _OrderedBidictItemsView delegate # to backing dicts for the methods they inherit from (Cannot delegate # for __iter__ and __reversed__ since they are order-sensitive.) See also: _OView = t.Union[t.Type[_OrderedBidictKeysView[KT]], t.Type[_OrderedBidictItemsView[KT, t.Any]]] _setmethodnames: t.Iterable[str] = ( '__lt__ __le__ __gt__ __ge__ __eq__ __ne__ __sub__ __rsub__ ' '__or__ __ror__ __xor__ __rxor__ __and__ __rand__ isdisjoint' ).split() def _override_set_methods_to_use_backing_dict(cls: _OView[KT], viewname: str) -> None: def make_proxy_method(methodname: str) -> t.Any: def method(self: _OrderedBidictKeysView[KT] | _OrderedBidictItemsView[KT, t.Any], *args: t.Any) -> t.Any: fwdm = self._mapping._fwdm if not isinstance(fwdm, dict): # dict view speedup not available, fall back to Set's implementation. return getattr(Set, methodname)(self, *args) fwdm_dict_view = getattr(fwdm, viewname)() fwdm_dict_view_method = getattr(fwdm_dict_view, methodname) if ( len(args) != 1 or not isinstance((arg := args[0]), self.__class__) or not isinstance(arg._mapping._fwdm, dict) ): return fwdm_dict_view_method(*args) # self and arg are both _OrderedBidictKeysViews or _OrderedBidictItemsViews whose bidicts are backed by # a dict. Use arg's backing dict's corresponding view instead of arg. Otherwise, e.g. `ob1.keys() # < ob2.keys()` would give "TypeError: '<' not supported between instances of '_OrderedBidictKeysView' and # '_OrderedBidictKeysView'", because both `dict_keys(ob1).__lt__(ob2.keys()) is NotImplemented` and # `dict_keys(ob2).__gt__(ob1.keys()) is NotImplemented`. arg_dict = arg._mapping._fwdm arg_dict_view = getattr(arg_dict, viewname)() return fwdm_dict_view_method(arg_dict_view) method.__name__ = methodname method.__qualname__ = f'{cls.__qualname__}.{methodname}' return method for name in _setmethodnames: setattr(cls, name, make_proxy_method(name)) _override_set_methods_to_use_backing_dict(_OrderedBidictKeysView, 'keys') _override_set_methods_to_use_backing_dict(_OrderedBidictItemsView, 'items') # * Code review nav * # ============================================================================ # ← Prev: Current: <FIN> # ============================================================================