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: _bidict.py      Current: _orderedbase.py   Next: _orderedbidict.py →12# ============================================================================13 14 15"""Provide :class:`OrderedBidictBase`."""16 17from __future__ import annotations18 19import typing as t20from weakref import ref as weakref21 22from ._base import BidictBase23from ._base import Unwrites24from ._bidict import bidict25from ._iter import iteritems26from ._typing import KT27from ._typing import MISSING28from ._typing import OKT29from ._typing import OVT30from ._typing import VT31from ._typing import MapOrItems32 33 34AT = t.TypeVar('AT')  # attr type35 36 37class WeakAttr(t.Generic[AT]):38    """Descriptor to automatically manage (de)referencing the given slot as a weakref.39 40    See https://docs.python.org/3/howto/descriptor.html#managed-attributes41    for an intro to using descriptors like this for managed attributes.42    """43 44    def __init__(self, *, slot: str) -> None:45        self.slot = slot46 47    def __set__(self, instance: t.Any, value: AT) -> None:48        setattr(instance, self.slot, weakref(value))49 50    def __get__(self, instance: t.Any, __owner: t.Any = None) -> AT:51        return t.cast(AT, getattr(instance, self.slot)())52 53 54class Node:55    """A node in a circular doubly-linked list56    used to encode the order of items in an ordered bidict.57 58    A weak reference to the previous node is stored59    to avoid creating strong reference cycles.60    Referencing/dereferencing the weakref is handled automatically by :class:`WeakAttr`.61    """62 63    prv: WeakAttr[Node] = WeakAttr(slot='_prv_weak')64    __slots__ = ('__weakref__', '_prv_weak', 'nxt')65 66    nxt: Node | WeakAttr[Node]  # Allow subclasses to use a WeakAttr for nxt too (see SentinelNode)67 68    def __init__(self, prv: Node, nxt: Node) -> None:69        self.prv = prv70        self.nxt = nxt71 72    def unlink(self) -> None:73        """Remove self from in between prv and nxt.74        Self's references to prv and nxt are retained so it can be relinked (see below).75        """76        self.prv.nxt = self.nxt77        self.nxt.prv = self.prv78 79    def relink(self) -> None:80        """Restore self between prv and nxt after unlinking (see above)."""81        self.prv.nxt = self.nxt.prv = self82 83 84class SentinelNode(Node):85    """Special node in a circular doubly-linked list86    that links the first node with the last node.87    When its next and previous references point back to itself88    it represents an empty list.89    """90 91    nxt: WeakAttr[Node] = WeakAttr(slot='_nxt_weak')92    __slots__ = ('_nxt_weak',)93 94    def __init__(self) -> None:95        super().__init__(self, self)96 97    def iternodes(self, *, reverse: bool = False) -> t.Iterator[Node]:98        """Iterator yielding nodes in the requested order."""99        attr = 'prv' if reverse else 'nxt'100        node = getattr(self, attr)101        while node is not self:102            yield node103            node = getattr(node, attr)104 105    def new_last_node(self) -> Node:106        """Create and return a new terminal node."""107        old_last = self.prv108        new_last = Node(old_last, self)109        old_last.nxt = self.prv = new_last110        return new_last111 112 113class OrderedBidictBase(BidictBase[KT, VT]):114    """Base class implementing an ordered :class:`BidirectionalMapping`."""115 116    _node_by_korv: bidict[t.Any, Node]117    _bykey: bool118 119    def __init__(self, arg: MapOrItems[KT, VT] = (), /, **kw: VT) -> None:120        """Make a new ordered bidirectional mapping.121        The signature behaves like that of :class:`dict`.122        Items passed in are added in the order they are passed,123        respecting the :attr:`~bidict.BidictBase.on_dup`124        class attribute in the process.125 126        The order in which items are inserted is remembered,127        similar to :class:`collections.OrderedDict`.128        """129        self._sntl = SentinelNode()130        self._node_by_korv = bidict()131        self._bykey = True132        super().__init__(arg, **kw)133 134    if t.TYPE_CHECKING:135 136        @property137        def inverse(self) -> OrderedBidictBase[VT, KT]: ...138 139        @property140        def inv(self) -> OrderedBidictBase[VT, KT]: ...141 142    def _make_inverse(self) -> OrderedBidictBase[VT, KT]:143        inv = t.cast(OrderedBidictBase[VT, KT], super()._make_inverse())144        inv._sntl = self._sntl145        inv._node_by_korv = self._node_by_korv146        inv._bykey = not self._bykey147        return inv148 149    def _assoc_node(self, node: Node, key: KT, val: VT) -> None:150        korv = key if self._bykey else val151        self._node_by_korv.forceput(korv, node)152 153    def _dissoc_node(self, node: Node) -> None:154        del self._node_by_korv.inverse[node]155        node.unlink()156 157    def _init_from(self, other: MapOrItems[KT, VT]) -> None:158        """See :meth:`BidictBase._init_from`."""159        super()._init_from(other)160        bykey = self._bykey161        korv_by_node = self._node_by_korv.inverse162        korv_by_node.clear()163        korv_by_node_set = korv_by_node.__setitem__164        self._sntl.nxt = self._sntl.prv = self._sntl165        new_node = self._sntl.new_last_node166        for k, v in iteritems(other):167            korv_by_node_set(new_node(), k if bykey else v)168 169    def _write(self, newkey: KT, newval: VT, oldkey: OKT[KT], oldval: OVT[VT], unwrites: Unwrites | None) -> None:170        """See :meth:`bidict.BidictBase._spec_write`."""171        super()._write(newkey, newval, oldkey, oldval, unwrites)172        assoc, dissoc = self._assoc_node, self._dissoc_node173        node_by_korv, bykey = self._node_by_korv, self._bykey174        if oldval is MISSING and oldkey is MISSING:  # no key or value duplication175            # {0: 1, 2: 3} | {4: 5} => {0: 1, 2: 3, 4: 5}176            newnode = self._sntl.new_last_node()177            assoc(newnode, newkey, newval)178            if unwrites is not None:179                unwrites.append((dissoc, newnode))180        elif oldval is not MISSING and oldkey is not MISSING:  # key and value duplication across two different items181            # {0: 1, 2: 3} | {0: 3} => {0: 3}182            #    n1, n2             =>   n1   (collapse n1 and n2 into n1)183            # oldkey: 2, oldval: 1, oldnode: n2, newkey: 0, newval: 3, newnode: n1184            if bykey:185                oldnode = node_by_korv[oldkey]186                newnode = node_by_korv[newkey]187            else:188                oldnode = node_by_korv[newval]189                newnode = node_by_korv[oldval]190            dissoc(oldnode)191            assoc(newnode, newkey, newval)192            if unwrites is not None:193                unwrites.extend((194                    (assoc, newnode, newkey, oldval),195                    (assoc, oldnode, oldkey, newval),196                    (oldnode.relink,),197                ))198        elif oldval is not MISSING:  # just key duplication199            # {0: 1, 2: 3} | {2: 4} => {0: 1, 2: 4}200            # oldkey: MISSING, oldval: 3, newkey: 2, newval: 4201            node = node_by_korv[newkey if bykey else oldval]202            assoc(node, newkey, newval)203            if unwrites is not None:204                unwrites.append((assoc, node, newkey, oldval))205        else:206            assert oldkey is not MISSING  # just value duplication207            # {0: 1, 2: 3} | {4: 3} => {0: 1, 4: 3}208            # oldkey: 2, oldval: MISSING, newkey: 4, newval: 3209            node = node_by_korv[oldkey if bykey else newval]210            assoc(node, newkey, newval)211            if unwrites is not None:212                unwrites.append((assoc, node, oldkey, newval))213 214    def __iter__(self) -> t.Iterator[KT]:215        """Iterator over the contained keys in insertion order."""216        return self._iter(reverse=False)217 218    def __reversed__(self) -> t.Iterator[KT]:219        """Iterator over the contained keys in reverse insertion order."""220        return self._iter(reverse=True)221 222    def _iter(self, *, reverse: bool = False) -> t.Iterator[KT]:223        nodes = self._sntl.iternodes(reverse=reverse)224        korv_by_node = self._node_by_korv.inverse225        if self._bykey:226            for node in nodes:227                yield korv_by_node[node]228        else:229            key_by_val = self._invm230            for node in nodes:231                val = korv_by_node[node]232                yield key_by_val[val]233 234 235#                             * Code review nav *236# ============================================================================237# ← Prev: _bidict.py      Current: _orderedbase.py   Next: _orderedbidict.py →238# ============================================================================239