codekingpro/portable-devtools

1# Copyright 2009-2024 Joshua Bronson. All rights reserved.2#3# This Source Code Form is subject to the terms of the Mozilla Public4# License, v. 2.0. If a copy of the MPL was not distributed with this5# file, You can obtain one at http://mozilla.org/MPL/2.0/.6 7 8#                             * Code review nav *9#                        (see comments in __init__.py)10# ============================================================================11# ← Prev: _orderedbase.py   Current: _orderedbidict.py                   <FIN>12# ============================================================================13 14 15"""Provide :class:`OrderedBidict`."""16 17from __future__ import annotations18 19import typing as t20from collections.abc import Set21 22from ._base import BidictKeysView23from ._bidict import MutableBidict24from ._orderedbase import OrderedBidictBase25from ._typing import KT26from ._typing import VT27 28 29class OrderedBidict(OrderedBidictBase[KT, VT], MutableBidict[KT, VT]):30    """Mutable bidict type that maintains items in insertion order."""31 32    if t.TYPE_CHECKING:33 34        @property35        def inverse(self) -> OrderedBidict[VT, KT]: ...36 37        @property38        def inv(self) -> OrderedBidict[VT, KT]: ...39 40    def clear(self) -> None:41        """Remove all items."""42        super().clear()43        self._node_by_korv.clear()44        self._sntl.nxt = self._sntl.prv = self._sntl45 46    def _pop(self, key: KT) -> VT:47        val = super()._pop(key)48        node = self._node_by_korv[key if self._bykey else val]49        self._dissoc_node(node)50        return val51 52    def popitem(self, last: bool = True) -> tuple[KT, VT]:53        """*b.popitem() → (k, v)*54 55        If *last* is true,56        remove and return the most recently added item as a (key, value) pair.57        Otherwise, remove and return the least recently added item.58 59        :raises KeyError: if *b* is empty.60        """61        if not self:62            raise KeyError('OrderedBidict is empty')63        node = getattr(self._sntl, 'prv' if last else 'nxt')64        korv = self._node_by_korv.inverse[node]65        if self._bykey:66            return korv, self._pop(korv)67        return self.inverse._pop(korv), korv68 69    def move_to_end(self, key: KT, last: bool = True) -> None:70        """Move the item with the given key to the end if *last* is true, else to the beginning.71 72        :raises KeyError: if *key* is missing73        """74        korv = key if self._bykey else self._fwdm[key]75        node = self._node_by_korv[korv]76        node.prv.nxt = node.nxt77        node.nxt.prv = node.prv78        sntl = self._sntl79        if last:80            lastnode = sntl.prv81            node.prv = lastnode82            node.nxt = sntl83            sntl.prv = lastnode.nxt = node84        else:85            firstnode = sntl.nxt86            node.prv = sntl87            node.nxt = firstnode88            sntl.nxt = firstnode.prv = node89 90    # Override the keys() and items() implementations inherited from BidictBase,91    # which may delegate to the backing _fwdm dict, since this is a mutable ordered bidict,92    # and therefore the ordering of items can get out of sync with the backing mappings93    # after mutation. (Need not override values() because it delegates to .inverse.keys().)94    def keys(self) -> t.KeysView[KT]:95        """A set-like object providing a view on the contained keys."""96        return _OrderedBidictKeysView(self)97 98    def items(self) -> t.ItemsView[KT, VT]:99        """A set-like object providing a view on the contained items."""100        return _OrderedBidictItemsView(self)101 102 103# The following MappingView implementations use the __iter__ implementations104# inherited from their superclass counterparts in collections.abc, so they105# continue to yield items in the correct order even after an OrderedBidict106# is mutated. They also provide a __reversed__ implementation, which is not107# provided by the collections.abc superclasses.108class _OrderedBidictKeysView(BidictKeysView[KT]):109    _mapping: OrderedBidict[KT, t.Any]110 111    def __reversed__(self) -> t.Iterator[KT]:112        return reversed(self._mapping)113 114 115class _OrderedBidictItemsView(t.ItemsView[KT, VT]):116    _mapping: OrderedBidict[KT, VT]117 118    def __reversed__(self) -> t.Iterator[tuple[KT, VT]]:119        ob = self._mapping120        for key in reversed(ob):121            yield key, ob[key]122 123 124# For better performance, make _OrderedBidictKeysView and _OrderedBidictItemsView delegate125# to backing dicts for the methods they inherit from collections.abc.Set. (Cannot delegate126# for __iter__ and __reversed__ since they are order-sensitive.) See also: https://bugs.python.org/issue46713127_OView = t.Union[t.Type[_OrderedBidictKeysView[KT]], t.Type[_OrderedBidictItemsView[KT, t.Any]]]128_setmethodnames: t.Iterable[str] = (129    '__lt__ __le__ __gt__ __ge__ __eq__ __ne__ __sub__ __rsub__ '130    '__or__ __ror__ __xor__ __rxor__ __and__ __rand__ isdisjoint'131).split()132 133 134def _override_set_methods_to_use_backing_dict(cls: _OView[KT], viewname: str) -> None:135    def make_proxy_method(methodname: str) -> t.Any:136        def method(self: _OrderedBidictKeysView[KT] | _OrderedBidictItemsView[KT, t.Any], *args: t.Any) -> t.Any:137            fwdm = self._mapping._fwdm138            if not isinstance(fwdm, dict):  # dict view speedup not available, fall back to Set's implementation.139                return getattr(Set, methodname)(self, *args)140            fwdm_dict_view = getattr(fwdm, viewname)()141            fwdm_dict_view_method = getattr(fwdm_dict_view, methodname)142            if (143                len(args) != 1144                or not isinstance((arg := args[0]), self.__class__)145                or not isinstance(arg._mapping._fwdm, dict)146            ):147                return fwdm_dict_view_method(*args)148            # self and arg are both _OrderedBidictKeysViews or _OrderedBidictItemsViews whose bidicts are backed by149            # a dict. Use arg's backing dict's corresponding view instead of arg. Otherwise, e.g. `ob1.keys()150            # < ob2.keys()` would give "TypeError: '<' not supported between instances of '_OrderedBidictKeysView' and151            # '_OrderedBidictKeysView'", because both `dict_keys(ob1).__lt__(ob2.keys()) is NotImplemented` and152            # `dict_keys(ob2).__gt__(ob1.keys()) is NotImplemented`.153            arg_dict = arg._mapping._fwdm154            arg_dict_view = getattr(arg_dict, viewname)()155            return fwdm_dict_view_method(arg_dict_view)156 157        method.__name__ = methodname158        method.__qualname__ = f'{cls.__qualname__}.{methodname}'159        return method160 161    for name in _setmethodnames:162        setattr(cls, name, make_proxy_method(name))163 164 165_override_set_methods_to_use_backing_dict(_OrderedBidictKeysView, 'keys')166_override_set_methods_to_use_backing_dict(_OrderedBidictItemsView, 'items')167 168 169#                             * Code review nav *170# ============================================================================171# ← Prev: _orderedbase.py   Current: _orderedbidict.py                   <FIN>172# ============================================================================173