<jupyter_start><jupyter_text>Dieses Notebook hängt vom Notebook `1-Splay-Trees.ipynb` ab.<jupyter_code>%run 1-Splay-Trees.ipynb<jupyter_output><empty_output><jupyter_text>Zusätzlich benötigen wir Funktionen aus den `collections` sowie aus den `functools`, die beide schon in Python-Distributionen enthalten sind.<jupyter_code>import collections
import functools<jupyter_output><empty_output><jupyter_text>Mengen auf Basis von Splay TreesWir benutzen nun die Splay Trees, um Mengen (`set`) in Python mit Ordnung zu unterstützen.Dazu bauen wir die hier gelisteten Methoden nach ([Permalink zur Datei, aus der dies generiert wird](https://github.com/python/cpython/blob/3.7/Objects/setobject.c "<NAME> et al. (2019): cpython/Objects/setobject.c, GitHub")):<jupyter_code>help(set)<jupyter_output>Help on class set in module builtins:

class set(object)
 |  set() -> new empty set object
 |  set(iterable) -> new set object
 |  
 |  Build an unordered collection of unique elements.
 |  
 |  Methods defined here:
 |  
 |  __and__(self, value, /)
 |      Return self&value.
 |  
 |  __contains__(...)
 |      x.__contains__(y) <==> y in x.
 |  
 |  __eq__(self, value, /)
 |      Return self==value.
 |  
 |  __ge__(self, value, /)
 |      Return self>=value.
 |  
 |  __getattribute__(self, name, /)
 |      Return getattr(self, name).
 |  
 |  __gt__(self, value, /)
 |      Return self>value.
 |  
 |  __iand__(self, value, /)
 |      Return self&=value.
 |  
 |  __init__(self, /, *args, **kwargs)
 |      Initialize self.  See help(type(self)) for accurate signature.
 |  
 |  __ior__(self, value, /)
 |      Return self|=value.
 |  
 |  __isub__(self, value, /)
 |      Return self-=value.
 |  
 |  __iter__(self, /)
 |      Implement iter(self).
 |  
 |  __ixor__(self, value, /)
 |      Re[...]<jupyter_text>Wir definieren dafür die Klasse `OrderedSet`.<jupyter_code>class OrderedSet:
    pass<jupyter_output><empty_output><jupyter_text>KonstruktionWenn wir das Konstruieren eines Sets aus einem `iterable` unterstützen wollen, begegnen wir dem Problem der Implementierung von Mengen modifizierbarer Objekte, zum Beispiel Mengen von Mengen.Sei $N$ eine Menge und $M$ ein modifizierbares Objekt, zum Beispiel eine Menge, und sei $M \in N$. Wie stellen wir sicher, dass $N$ geordnet bleibt, wenn $M$ geändert wird? Wir könnten verlangen, dass in $N$ ein Element, wann immer es preisgegeben wird, neu einsortiert werden muss. Abgesehen vom damit verbundenen Berechnungsaufwand ist dies aber nicht praktikabel, da auf $M$ auch Referenzen gehalten werden können, die nicht von $N$ abhängig sind, und somit $M$ geändert werden könnte, ohne dass $N$ davon erfährt. (Die $N$-seitige Überwachung aller gehaltenen Objekte wäre noch unpraktischer als das erneute Einsortieren.)Ein vergleichbares Problem ergibt sich übrigens auch bei den Hashtabellen in der Referenzimplementierung CPython. Hier kann keine Ordnungsbedingung verletzt werden, jedoch ist im Allgemeinen ein Objekt nach Änderung nicht mehr unter ihrem vorigen Hash zu finden. Der Python-Standard gibt daher vor, dass es strenggenommen keine Mengen von Mengen gibt – [es gibt nur Mengen von unmodifizierbaren Mengen](https://docs.python.org/3.7/library/stdtypes.htmlset "Python Software Foundation (2019): The Python Standard Library/Built-in Types/set, Python Documentation"), den `frozenset`s. Ebenso gibt es beispielsweise keine Mengen von Listen.Wir wollen auch die `frozenset`s geordnet haben und werden sie parallel mitimplementieren.<jupyter_code>class OrderedFrozenset:
    pass<jupyter_output><empty_output><jupyter_text>Wir übernehmen `_arb_lt`, `_arb_eq` und `_arb_gt` von `Node`, sodass wir direkt Zugriff darauf haben.<jupyter_code>OrderedSet._arb_lt = OrderedFrozenset._arb_lt = Node._arb_lt
OrderedSet._arb_eq = OrderedFrozenset._arb_eq = Node._arb_eq
OrderedSet._arb_gt = OrderedFrozenset._arb_gt = Node._arb_gt<jupyter_output><empty_output><jupyter_text>Konstruieren wir nun eine Menge aus einem `iterable`, so fügen wir die Elemente einzeln ein. Wir arbeiten direkt mit `Node`s, wrappen also nicht noch zusätzlich einen `SplayTree`. Wir überprüfen dabei die hinzuzufügenden Elemente darauf, ob sie in einer Menge existieren dürfen, indem wir überprüfen, ob sie eine `__hash__`-Methode haben.<jupyter_code>def __init__(self, iterable=[]):
    if isinstance(self, OrderedFrozenset) and hasattr(self, "_tree"):
        return  # frozenset was already created
    self._tree = None
    iterator   = iter(iterable)
    try:
        element = next(iterator)
        if not element.__hash__:
            raise TypeError(f"unhashable type: '{type(element).__name__}'")
        self._tree = Node(element, None, None)
        while True:
            element = next(iterator)
            if not element.__hash__:
                raise TypeError("unhashable type: " +
                                f"'{type(element).__name__}'")
            self._tree = self._tree.insert(element)
    except StopIteration:
        pass

OrderedSet.__init__ = OrderedFrozenset.__init__ = __init__
del __init__<jupyter_output><empty_output><jupyter_text>Lexikographische OrdnungWir müssen, wenn wir geordnete Mengen von geordneten Mengen unterstützen wollen, die totalen Ordnungen `` sowie die Operation `==` zwischen geordneten Mengen definieren – diese Operatoren werden von `_arb_lt` und verwandten Methoden und somit mittelbar von `splay` benutzt. Wir müssen dabei leider das Verhalten von `set` und `frozenset` verändern; für diese drücken `` die echte Ober- bzw. Teilmenge aus. Alternativ könnten wir in `_arb_lt` und verwandten Methoden vorher den Typ überprüfen und im Fall von `OrderedSet` und `OrderedFrozenset` nicht ``, sondern andere Methoden verwenden. Die damit verbundenen Performanceeinbußen sind jedoch nicht vertretbar.Eine totale Ordnung, die sich anbietet, ist die lexikographische Ordnung. Hier wird durch die Mengen iteriert und das erste ungleiche Wertepaar entscheidet die Ungleichheit. Wir definieren dafür zunächst die Iteration `__iter__`, um durch die Elemente in der Menge iterieren zu können.Dies erreichen wir, indem wir den Baum wie bei einer *Inorder*-Ausgabe durchlaufen, wobei wir zur Ausgabe das Keyword `yield` benutzen. Die Implementierung ist iterativ und hält sich einen eigenen Stapel, da dieser in seiner Größe weniger begrenzt ist als der Aufrufstapel, der sich bei einer rekursiven Implementierung aufbauen würde. Für diesen Stapel benutzen wir [`deque`](https://docs.python.org/3.7/library/collections.htmlcollections.deque "Python Software Foundation (2020): The Python Standard Library/Data Types/collections/deque, Python Documentation") (double-ended queue) aus den `collections` der Standard Library, da sich diese für größere Stapel besser eignet als die Liste.<jupyter_code>def __iter__(self):
    stack = collections.deque()
    tree  = self._tree
    while stack or tree is not None:
        if tree is not None:
            stack.append(tree)
            tree = tree.left
            continue
        tree = stack.pop()
        yield tree.payload
        tree = tree.right

OrderedSet.__iter__ = OrderedFrozenset.__iter__ = __iter__
del __iter__<jupyter_output><empty_output><jupyter_text>Nun können wir (für `<`) die Methode `__lt__` mit lexikographischer Ordnung definieren. Wir geben bei Typinkompatibilität `NotImplemented` zurück, woraus von Python zur Laufzeit gegebenenfalls ein `TypeError` gemacht wird. Wir iterieren durch die geordneten Mengen und können uns bei der ersten Verschiedenheit entscheiden. Die leere Menge ist kleiner als jede Menge außer der leeren.Wir können dies auch formal notieren, wenn wir mit $\mathrm{head}$ das erste und mit $\mathrm{tail}$ alle übrigen Elemente der geordneten Menge bezeichnen. Bei allen formalen Definitionen sprechen wir vereinfachend nur vom $\mathrm{OrderedSet}$, nicht vom $\mathrm{OrderedFrozenset}$.$$\mathrm{\_\_lt\_\_}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathbb{B}$$$$\mathrm{\_\_lt\_\_}(x, y) = \begin{cases}\mathrm{false} &\mathrm{falls}\ y = \{\}\\\mathrm{true} &\mathrm{falls}\ x = \{\} \land y \neq \{\}\\\mathrm{true} &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{false} &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\\\mathrm{\_\_lt\_\_}(\mathrm{tail}(x), \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$<jupyter_code>def __lt__(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        return NotImplemented
    x_iter, y_iter = iter(self), iter(other)
    while True:
        try:
            y_item = next(y_iter)
        except StopIteration:
            return False  # x is longer or equal
        try:
            x_item = next(x_iter)
        except StopIteration:
            return True  # x is shorter
        if self._arb_lt(x_item, y_item):
            return True
        if self._arb_gt(x_item, y_item):
            return False

OrderedSet.__lt__ = OrderedFrozenset.__lt__ = __lt__
del __lt__<jupyter_output><empty_output><jupyter_text>Ähnlich definieren wir `__gt__` für `>`. Formal heißt das:$$\mathrm{\_\_gt\_\_}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathbb{B}$$$$\mathrm{\_\_gt\_\_}(x, y) = \begin{cases}\mathrm{false} &\mathrm{falls}\ x = \{\}\\\mathrm{true} &\mathrm{falls}\ x \neq \{\} \land y = \{\}\\\mathrm{true} &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\\\mathrm{false} &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{\_\_gt\_\_}(\mathrm{tail}(x), \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$<jupyter_code>def __gt__(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        return NotImplemented
    x_iter, y_iter = iter(self), iter(other)
    while True:
        try:
            x_item = next(x_iter)
        except StopIteration:
            return False  # x is shorter or equal
        try:
            y_item = next(y_iter)
        except StopIteration:
            return True  # x is longer
        if self._arb_gt(x_item, y_item):
            return True
        if self._arb_lt(x_item, y_item):
            return False

OrderedSet.__gt__ = OrderedFrozenset.__gt__ = __gt__
del __gt__<jupyter_output><empty_output><jupyter_text>Für `__eq__` (`==`) müssen wir nur Element für Element vergleichen. Wir verändern hier auch nicht das Verhalten im Vergleich zu den Vorbildern `set` und `frozenset`. Hier ist  der Vergleich mit fremden Typen kein `NotImplemented`, sondern einfach die Ungleichheit. Wir können auch formal definieren, wobei wir mit $\dot{\lor}$ das *exklusive Oder* meinen:$$\mathrm{\_\_eq\_\_}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathbb{B}$$$$\mathrm{\_\_eq\_\_}(x, y) = \begin{cases}\mathrm{true} &\mathrm{falls}\ x = \{\} \land y = \{\}\\\mathrm{false} &\mathrm{falls}\ x = \{\}\ \dot{\lor}\ y = \{\}\\\mathrm{false} &\mathrm{falls}\ \mathrm{head}(x) \neq \mathrm{head}(y)\\\mathrm{\_\_eq\_\_}(\mathrm{tail}(x), \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$<jupyter_code>def __eq__(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        return False
    x_iter, y_iter = iter(self), iter(other)
    while True:
        try:
            x_item = next(x_iter)
        except StopIteration:
            try:  # assert y is also exhausted
                next(y_iter)
            except StopIteration:
                return True
            return False
        try:
            y_item = next(y_iter)
        except StopIteration:
            return False  # x was not exhausted
        if not self._arb_eq(x_item, y_item):
            return False

OrderedSet.__eq__ = OrderedFrozenset.__eq__ = __eq__
del __eq__<jupyter_output><empty_output><jupyter_text>`__ne__` für `!=` ist damit schon implizit definiert. HashenDer letzte Schritt, um `OrderedFrozenset`s in `OrderedSet`s haben zu können, ist die Unterstützung einer `__hash__`-Funktion für `OrderedFrozenset` (`OrderedSet` ist wegen seiner Veränderlichkeit bewusst **nicht** hashbar). Wir addieren dazu die Hashwerte aller Elemente, deren Hashbarkeit wir ja schon zur Zeit des Hinzufügens überprüft haben.<jupyter_code>def __hash__(self):
    return sum(hash(el) for el in self)

OrderedFrozenset.__hash__ = __hash__
del __hash__<jupyter_output><empty_output><jupyter_text>Um das Verhalten von Python abzubilden, werfen wir im Fall von `OrderedSet` einen `TypeError`, wenn versucht wird, eines zu hashen.<jupyter_code>def __hash__(self):
    raise TypeError(f"unhashable type: '{type(self).__name__}'")

OrderedSet.__hash__ = __hash__
del __hash__<jupyter_output><empty_output><jupyter_text>Operationen mit einem ElementWir implementieren im Folgenden die Methoden von `set` und `frozenset` für `OrderedSet` und `OrderedFrozenset`. Wir beginnen mit den Operationen mit einem einzelnen Element als Parameter. HinzufügenWir implementieren `add`, das Hinzufügen eines Elements, ähnlich wie beim `SplayTree`:<jupyter_code>def add(self, element):
    if not element.__hash__:
        raise TypeError(f"unhashable type: '{type(element).__name__}'")
    if self._tree is None:
        self._tree = Node(element, None, None)
    else:
        self._tree = self._tree.insert(element)

OrderedSet.add = add
del add<jupyter_output><empty_output><jupyter_text>EntfernenDas Gegenstück zu `add` ist `remove`, das Entfernen eines Elementes.<jupyter_code>def remove(self, element):
    if not element.__hash__:
        raise TypeError(f"unhashable type: '{type(element).__name__}'")
    if self._tree is None:
        raise KeyError(element)
    rc, self._tree = self._tree.remove(element)
    if not rc:
        raise KeyError(element)

OrderedSet.remove = remove
del remove<jupyter_output><empty_output><jupyter_text>Wir implementieren auch `discard`, welches ähnlich zu `remove` ist, aber keinen Fehler verursacht, falls das Element nicht vorhanden ist.<jupyter_code>def discard(self, element):
    if not element.__hash__:
        raise TypeError(f"unhashable type: '{type(element).__name__}'")
    if self._tree is not None:
        _, self._tree = self._tree.remove(element)

OrderedSet.discard = discard
del discard<jupyter_output><empty_output><jupyter_text>`add`, `remove` und `discard` sind **keine** Methoden von `OrderedFrozenset`, weil diese Operationen die Menge modifizieren! FindenEine nichtmodifizierende Operation mit einem Element als Parameter ist `__contains__` (`in`), die wir ebenfalls für `Node` schon implementiert haben.<jupyter_code>def __contains__(self, element):
    if not element.__hash__:
        raise TypeError(f"unhashable type: '{type(element).__name__}'")
    if self._tree is None:
        return False
    contains, self._tree = self._tree.contains(element)
    return contains

OrderedSet.__contains__ = OrderedFrozenset.__contains__ = __contains__
del __contains__<jupyter_output><empty_output><jupyter_text>Operationen ohne ParameterWir implementieren im Folgenden Operationen auf die geordnete Menge, die überhaupt keine Parameter haben. Wir beginnen wieder mit solchen, die die Menge verändern. KopierenWir implementieren `copy`, welches eine Kopie der Menge zurückgibt. Da die Funktion so kurz ist, schreiben wir die Funktionen für die beiden Methoden einzeln, statt den Typ von `self` zu überprüfen.<jupyter_code>OrderedSet.copy       = lambda self: OrderedSet(el for el in self)
OrderedFrozenset.copy = lambda self: OrderedFrozenset(el for el in self)<jupyter_output><empty_output><jupyter_text>Entfernen eines beliebigen ElementsWir implementieren `pop`, welches ein beliebiges Element entfernt und zurückgibt. Wir entfernen dabei das Minimum des Baums.<jupyter_code>def pop(self):
    if self._tree is None:
        raise KeyError("pop from an empty set")
    popped = self.minimum()
    self.remove(popped)
    return popped

OrderedSet.pop = pop
del pop<jupyter_output><empty_output><jupyter_text>LeerenWir implementieren auch `clear`, welches alle Elemente aus der Menge entfernt. Wir setzen einfach den Baum auf `None`.<jupyter_code>def clear(self):
    self._tree = None

OrderedSet.clear = clear
del clear<jupyter_output><empty_output><jupyter_text>LängeWir kehren zurück zu den Operationen, die auch für `OrderedFrozenset` erlaubt sind, und implementieren `__len__`, welches die Länge von Mengen berechnet und dann mit `len(some_ordered_set)` benutzt werden kann.<jupyter_code>def __len__(self):
    return sum(1 for i in self)

OrderedSet.__len__ = OrderedFrozenset.__len__ = __len__
del __len__<jupyter_output><empty_output><jupyter_text>DarstellungWir implementieren auch `__repr__`, welches eine String-Darstellung anbietet. Wir wollen zum Beispiel für die Elemente `a, b` die Darstellung `OrderedSet([a, b])` haben und implementieren:<jupyter_code>def __repr__(self):
    if self._tree is None:
        return f"{type(self).__name__}()"
    return f"{type(self).__name__}({list(self)})"

OrderedSet.__repr__ = OrderedFrozenset.__repr__ = __repr__
del __repr__<jupyter_output><empty_output><jupyter_text>Pickling`set` implementiert `__reduce__`, welches von der *pickle*-API aufgerufen wird. Diese API dient zur Serialisierung. Wir implementieren für diese API nicht `__reduce__`, sondern das simplere [`__getnewargs__`](https://docs.python.org/3/library/pickle.htmlobject.__getnewargs__ "Python Software Foundation (2020): The Python Standard Library/Data Persistence/object.__getnewargs__(), Python Documentation"), welches die Argumente, mit denen eine Rekonstruktion erreicht wird, zurückgibt. Wir geben den Mengeninhalt als Simpel aus einer Liste aus, sodass zum Beispiel für die Elemente `a, b` beim Deserialisieren  `OrderedSet(([a, b],))` aufgerufen wird.<jupyter_code>def __getnewargs__(self):
    return (list(self),)

OrderedSet.__getnewargs__ = OrderedFrozenset.__getnewargs__ = __getnewargs__
del __getnewargs__<jupyter_output><empty_output><jupyter_text>Minimum und MaximumWir implementieren noch die *zusätzliche* Methode `minimum`. Mit `__iter__` funktioniert zwar bereits das Built-in `min`, wir können dies mit einem Baum aber effizienter gestalten: Wir geben die Nutzlast des linkesten Knotens zurück. Für `Node` definieren wir<jupyter_code>def minimum(self):
    while self.left is not None:
        self = self.left
    return self.payload

Node.minimum = minimum
del minimum<jupyter_output><empty_output><jupyter_text>und für `OrderedSet` und `OrderedFrozenset`<jupyter_code>def minimum(self):
    if self._tree is None:
        raise ValueError("Set is empty")
    return self._tree.minimum()

OrderedSet.minimum = OrderedFrozenset.minimum = minimum
del minimum<jupyter_output><empty_output><jupyter_text>Wir implementieren auch `maximum`, bei der wir die Nutzlast des rechtesten Knotens zurückgeben.<jupyter_code>def maximum(self):
    while self.right is not None:
        self = self.right
    return self.payload

Node.maximum = maximum
del maximum<jupyter_output><empty_output><jupyter_text>und für die `Set`-Klassen<jupyter_code>def maximum(self):
    if self._tree is None:
        raise ValueError("Set is empty")
    return self._tree.maximum()

OrderedSet.maximum = OrderedFrozenset.maximum = maximum
del maximum<jupyter_output><empty_output><jupyter_text>Boolesche Operationen auf andere MengenWir implementieren im Folgenden Operationen auf andere Mengen, die einen Wahrheitswert als Ergebnis haben. `==` und `!=` hatten wir schon für die lexikographische Ordnung implementiert. TeilmengeWir haben `issubset`, `__le__` (`<=`, in der Mengenlehre $\subseteq$) und `__lt__` (`<`, in der Mengenlehre $\subset$ bzw. $\subsetneq$) zu implementieren. `issubset` arbeitet wie `__le__`, erlaubt aber einen beliebigen Parameter als Operand, statt nur Mengen. Wir werden die echte Teilmenge nicht unter dem Namen `<` implementieren können, weil wir diesen Operator für die lexikographische Ordnung benutzen. Wir werden dafür in Anlehnung an `issubset` die Methode `is_proper_subset` implementieren, die *keine* Methode von `set` oder `frozenset` ist.Für die unechte Teilmenge implementieren wir die Hilfsfunktion `_subseteq`, welches von geordneten Mengen $x, y$ die Relation $x \subseteq y$ überprüft. So brauchen wir für die eigentlichen Methoden nur `_subseteq` mit den entsprechenden Parametern aufrufen. Dies erspart besonders für die Obermenge Arbeit.Hier gehen wir für jedes Element aus $x$ so lange in $y$ weiter, bis die Elemente gleich sind. In diesem Fall gehen wir in beiden Mengen ein Element weiter. Ist ein Element aus $y$ größer, so kam ein Element aus $x$ nicht in $y$ vor, und wir verneinen die Relation $\subseteq$. Ist $x$ erschöpft, so waren alle Elemente in $y$. Ist $y$ erschöpft, so war mindestens ein Element von $x$ nicht in $y$. Formal können wir das auch schreiben als$$\mathrm{\_subseteq}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathbb{B}$$$$\mathrm{\_subseteq}(x, y) = \begin{cases}\mathrm{true} &\mathrm{falls}\ x = \{\}\\\mathrm{false} &\mathrm{falls}\ x \neq \{\} \land y = \{\}\\\mathrm{false} &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{\_subseteq}(x, \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\\\mathrm{\_subseteq}(\mathrm{tail}(x), \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$<jupyter_code>def _subseteq(self, x, y):
    x_iter, y_iter = iter(x), iter(y)
    while True:
        try:
            x_item = next(x_iter)
        except StopIteration:
            return True
        while True:
            try:
                y_item = next(y_iter)
            except StopIteration:
                return False
            if self._arb_lt(x_item, y_item):
                return False
            if self._arb_eq(x_item, y_item):
                break

OrderedSet._subseteq = OrderedFrozenset._subseteq = _subseteq
del _subseteq<jupyter_output><empty_output><jupyter_text>So können wir `issubset` implementieren, wo wir das andere Iterable gegebenenfalls in ein `OrderedFrozenset` bringen und so sortieren.<jupyter_code>def issubset(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other = OrderedFrozenset(other)
    return self._subseteq(self, other)

OrderedSet.issubset = OrderedFrozenset.issubset = issubset
del issubset<jupyter_output><empty_output><jupyter_text>Bei `__le__` erlauben wir für den anderen Operanden nur `OrderedSet` und `OrderedFrozenset`.<jupyter_code>def __le__(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        return NotImplemented
    return self._subseteq(self, other)

OrderedSet.__le__ = OrderedFrozenset.__le__ = __le__
del __le__<jupyter_output><empty_output><jupyter_text>Für `is_proper_subset` und später `is_proper_superset` definieren wir `_subsetneq`, welches $x \subset y$ überprüft. Hier halten wir uns die auf `False` initialisierte Variable `proper_subset`, mit deren Hilfe wir sicherstellen, dass $x$ eine echte Teilmenge von $y$ ist. Sie wird auf `True` gesetzt, sobald ein Element aus $y$ kleiner ist als aus $x$. Ist $x$ erschöpft und `proper_subset` nicht `True`, so prüfen wir, ob noch Elemente in $y$ sind, dann ist ebenfalls $x \subset y$.Formal schreiben wir zusätzlich `_subsetneq_help` mit zusätzlichem Parameter $p$ (proper). Zu Beginn ist dieser $\mathrm{false}$.$$\mathrm{\_subsetneq}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathbb{B}$$$$\mathrm{\_subsetneq}(x, y) = \mathrm{\_subsetneq\_help}(x, y, \mathrm{false})$$$$\mathrm{\_subsetneq\_help}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \times \mathbb{B} \to \mathbb{B}$$$$\mathrm{\_subsetneq\_help}(x, y, p) = \begin{cases}p &\mathrm{falls}\ y = \{\}\\\mathrm{true} &\mathrm{falls}\ x = \{\} \land y \neq \{\}\\\mathrm{false} &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{\_subsetneq\_help}(x, \mathrm{tail}(y), \mathrm{true}) &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\\\mathrm{\_subsetneq\_help}(\mathrm{tail}(x), \mathrm{tail}(y), p) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$<jupyter_code>def _subsetneq(self, x, y):
    x_iter, y_iter = iter(x), iter(y)
    proper_subset  = False
    while True:
        try:
            x_item = next(x_iter)
        except StopIteration:
            if not proper_subset:
                try:  # assert y is not exhausted
                    next(y_iter)
                except StopIteration:
                    return False
            return True
        while True:
            try:
                y_item = next(y_iter)
            except StopIteration:
                return False
            if self._arb_lt(x_item, y_item):
                return False
            if self._arb_gt(x_item, y_item):
                proper_subset = True
            else:
                break

OrderedSet._subsetneq = OrderedFrozenset._subsetneq = _subsetneq
del _subsetneq<jupyter_output><empty_output><jupyter_text>So können wir `is_proper_subset` ähnlich wie `issubset` implementieren.<jupyter_code>def is_proper_subset(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other = OrderedSet(other)
    return self._subsetneq(self, other)

OrderedSet.is_proper_subset       = is_proper_subset
OrderedFrozenset.is_proper_subset = is_proper_subset
del is_proper_subset<jupyter_output><empty_output><jupyter_text>ObermengeWir können für die Obermenge jetzt `_subseteq` und `_subsetneq` wiederverwenden und müssen nur die Parameter ändern. Analog zur den Operationen für die Untermenge haben wir `issuperset`…<jupyter_code>def issuperset(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other = OrderedSet(other)
    return self._subseteq(other, self)

OrderedSet.issuperset = OrderedFrozenset.issuperset = issuperset
del issuperset<jupyter_output><empty_output><jupyter_text>…`__ge__` (`>=`, in der Mengenlehre $\supseteq$)…<jupyter_code>def __ge__(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        return NotImplemented
    return self._subseteq(other, self)

OrderedSet.__ge__ = OrderedFrozenset.__ge__ = __ge__
del __ge__<jupyter_output><empty_output><jupyter_text>…und `is_proper_superset` statt `__gt__` (`>`, in der Mengenlehre $\supset$ bzw. $\supsetneq$).<jupyter_code>def is_proper_superset(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other = OrderedSet(other)
    return self._subsetneq(other, self)

OrderedSet.is_proper_superset       = is_proper_superset
OrderedFrozenset.is_proper_superset = is_proper_superset
del is_proper_superset<jupyter_output><empty_output><jupyter_text>Überprüfen, ob Mengen disjunkt sindWir implementieren zuletzt `isdisjoint`, das überprüft, ob zwei Mengen disjunkt sind, das heißt, ob sie keine gemeinsamen Elemente haben. Wir iterieren parallel durch die Mengen und überprüfen, dass wir jedes Element in nur einer Menge wiederfinden. Formal heißt das:$$\mathrm{isdisjoint}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathbb{B}$$$$\mathrm{isdisjoint}(x, y) = \begin{cases}\mathrm{true} &\mathrm{falls}\ \{\} \in \{x, y\}\\\mathrm{false} &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\\\mathrm{isdisjoint}(\mathrm{tail}(x), y) &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{isdisjoint}(x, \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\end{cases}$$<jupyter_code>def isdisjoint(self, other):
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other      = OrderedSet(other)
    x_iter, y_iter = iter(self), iter(other)
    try:
        y_item = next(y_iter)  # we need a y_item ready for first comparison
    except StopIteration:
        return True
    while True:
        try:
            x_item = next(x_iter)
        except StopIteration:
            return True
        while True:
            if self._arb_lt(x_item, y_item):
                break
            if self._arb_gt(x_item, y_item):
                try:
                    y_item = next(y_iter)
                except StopIteration:
                    return True
                continue
            return False

OrderedSet.isdisjoint = OrderedFrozenset.isdisjoint = isdisjoint
del isdisjoint<jupyter_output><empty_output><jupyter_text>Verknüpfung von MengenZuletzt implementieren wir die Operationen auf andere Mengen, die eine Menge als Ergebnis haben. Wir beginnen mit den einfacheren Vereinigungs- und Differenzmengen. VereinigungsmengeBei Vereinigungsmengen ($\cup$) fügen wir einfach alle Elemente hinzu. Zunächst definieren wir die Methode `union`. Bei Bedarf wandeln wir die Arbeitsmenge wieder in ein `Frozenset` um.<jupyter_code>def union(self, *others):
    union = OrderedSet(self)
    for other in others:
        for el in other:
            union.add(el)
    if isinstance(self, OrderedFrozenset):
        frozen       = OrderedFrozenset()
        frozen._tree = union._tree
        return frozen
    return union

OrderedSet.union = OrderedFrozenset.union = union
del union<jupyter_output><empty_output><jupyter_text>Für die Vereinigungsmenge gibt es auch `__or__` (`|`). Die beiden Methoden haben jedoch nicht ganz dasselbe Verhalten: `__or__` funktioniert nur mit Mengen, und operiert auf nur eine zusätzliche Menge; hingegen nimmt `union` beliebig viele iterable Sammlungen. Diese Überprüfungen benötigen wir später auch für `-`, `&` und `^`, weshalb wir eine Technik aus der funktionalen Programmierung benutzen, um uns Code zu ersparen, nämlich *Currying*. Dabei wird eine Funktion mit mehreren Argumenten als mehrere Funktionen mit je nur einem Argument behandelt. In unserem Fall schreiben wir eine generische Funktion mit den genannten Überprüfungen, die getrennt die Operation und auf der nächsten Ebene die Operanden nimmt – sie ist teilweise *gecurryt* und *uncurryt* umgekehrt wieder. Wir formulieren `_uncurry_reg_op` (regular operation), die die übergebene Funktion (z. B. `union`) in die Routine für den Operator (z. B. `|`) einsetzt.<jupyter_code>def _uncurry_reg_op(func):
    def reg_op(self, other):
        if isinstance(other, OrderedSet) \
                or isinstance(other, OrderedFrozenset):
            # this style is necessary when uncurrying a class function
            return func(self, other)
        else:
            return NotImplemented
    return reg_op

OrderedSet._uncurry_reg_op = OrderedFrozenset._uncurry_reg_op = _uncurry_reg_op
del _uncurry_reg_op<jupyter_output><empty_output><jupyter_text>Nun können wir für beide Klassen `__or__` setzen.<jupyter_code>OrderedSet.__or__       = OrderedSet._uncurry_reg_op(OrderedSet.union)
OrderedFrozenset.__or__ = OrderedFrozenset._uncurry_reg_op(
    OrderedFrozenset.union)<jupyter_output><empty_output><jupyter_text>Wir benötigen auch `__ror__` (reverse or), bei dem das Objekt selbst (`self`) an zweiter Stelle steht. Wir definieren dafür analog `_uncurry_rev_op` (reverse operation). Zwar verhält sich `|` kommutativ, sodass wir auch `_uncurry_reg_op` verwenden könnten, dies ist aber für `-` nicht der Fall, und so definieren wir gleich die generische Variante für alle umgekehrten Operationen.<jupyter_code>def _uncurry_rev_op(func):
    def rev_op(self, other):
        if isinstance(other, OrderedSet) \
                or isinstance(other, OrderedFrozenset):
            return func(other, self)
        else:
            return NotImplemented
    return rev_op

OrderedSet._uncurry_rev_op = OrderedFrozenset._uncurry_rev_op = _uncurry_rev_op
del _uncurry_rev_op<jupyter_output><empty_output><jupyter_text>Das Setzen von `__ror__` verläuft analog.<jupyter_code>OrderedSet.__ror__       = OrderedSet._uncurry_rev_op(OrderedSet.union)
OrderedFrozenset.__ror__ = OrderedFrozenset._uncurry_rev_op(
    OrderedFrozenset.union)<jupyter_output><empty_output><jupyter_text>*In-place* ist die `union` entsprechende Operation `update`. Hier operieren wir direkt auf `self`. Diese Methode ordnen wir nicht `OrderedFrozenset` zu, da die Menge überschrieben wird.<jupyter_code>def update(self, *others):
    for other in others:
        for el in other:
            self.add(el)

OrderedSet.update = update
del update<jupyter_output><empty_output><jupyter_text>Als Operator haben wir `__ior__` (`|=`). Hier definieren wir noch `_uncurry_inp_op` (in-place operation), weil wir dieses Codemuster wieder für die folgenden Operationen benötigen.<jupyter_code>def _uncurry_inp_op(func):
    def inp_op(self, other):
        if isinstance(other, OrderedSet) \
                or isinstance(other, OrderedFrozenset):
            func(self, other)
            return self
        else:
            return NotImplemented
    return inp_op

OrderedSet._uncurry_inp_op = _uncurry_inp_op
del _uncurry_inp_op<jupyter_output><empty_output><jupyter_text>So können wir `__ior__` setzen, natürlich nur für `OrderedSet`.<jupyter_code>OrderedSet.__ior__ = OrderedSet._uncurry_inp_op(OrderedSet.update)<jupyter_output><empty_output><jupyter_text>DifferenzmengeEs folgt die Differenzmenge ($\setminus$), für die wir einfach alle Elemente entfernen. Dafür haben wir `difference`.<jupyter_code>def difference(self, *others):
    difference = OrderedSet(self)
    for other in others:
        for el in other:
            if not el.__hash__:
                raise TypeError(f"unhashable type: '{type(el).__name__}'")
            difference.discard(el)
    if isinstance(self, OrderedFrozenset):
        frozen       = OrderedFrozenset()
        frozen._tree = difference._tree
        return frozen
    return difference

OrderedSet.difference = OrderedFrozenset.difference = difference
del difference<jupyter_output><empty_output><jupyter_text>Als Operatoren haben wir `__sub__` (`-`) und `__rsub__` (reverse).<jupyter_code>OrderedSet.__sub__        = OrderedSet._uncurry_reg_op(OrderedSet.difference)
OrderedFrozenset.__sub__  = OrderedFrozenset._uncurry_reg_op(
    OrderedFrozenset.difference)
OrderedSet.__rsub__       = OrderedSet._uncurry_rev_op(OrderedSet.difference)
OrderedFrozenset.__rsub__ = OrderedFrozenset._uncurry_rev_op(
    OrderedFrozenset.difference)<jupyter_output><empty_output><jupyter_text>In-place haben wir `difference_update`…<jupyter_code>def difference_update(self, *others):
    for other in others:
        for el in other:
            if not el.__hash__:
                raise TypeError(f"unhashable type: '{type(el).__name__}'")
            self.discard(el)

OrderedSet.difference_update = difference_update
del difference_update<jupyter_output><empty_output><jupyter_text>…und `__isub__` (`-=`).<jupyter_code>OrderedSet.__isub__ = OrderedSet._uncurry_inp_op(
    OrderedSet.difference_update)<jupyter_output><empty_output><jupyter_text>SchnittmengeKomplexer sind `intersection` und `__and__` (`&`). Wir definieren in der Methode zunächst die lokale binäre Relation `intersect`, die wir auch formal notieren. Wir iterieren durch die Mengen, wobei wir gleiche Elemente aufnehmen, und enden, wenn eine Menge ausgeschöpft ist.$$\mathrm{intersect}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathrm{OrderedSet}$$$$\mathrm{intersect}(x, y) = \begin{cases}\mathrm{OrderedSet}() &\mathrm{falls}\ \{\} \in \{x, y\}\\\mathrm{intersect}(\mathrm{tail}(x), y) &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{intersect}(x, \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\\\mathrm{OrderedSet}([\mathrm{head}(x)]) \cup \mathrm{intersect}(\mathrm{tail}(x), \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$Wir machen aus allen zu schneidenden Sammlungen `OrderedSet`s und *reduzieren* sie dann im funktionalen Sinne, das heißt, wir fassen sie anhand von `intersect` mithilfe von [`reduce`](https://docs.python.org/3.7/library/functools.htmlfunctools.reduce "Python Software Foundation (2020): The Python Standard Library/Functional Programming Modules/functools/reduce, Python Documentation") aus den `functools` der Standard Library zusammen. Wir können das tun, weil sich der Schnitt von Mengen assoziativ verhält.<jupyter_code>def intersection(self, *others):
    def intersect(x, y):
        intersection   = OrderedSet()
        x_iter, y_iter = iter(x), iter(y)
        try:
            x_item, y_item = next(x_iter), next(y_iter)
            while True:
                if self._arb_lt(x_item, y_item):
                    x_item = next(x_iter)
                    continue
                if self._arb_gt(x_item, y_item):
                    y_item = next(y_iter)
                    continue
                intersection.add(x_item)
                x_item, y_item = next(x_iter), next(y_iter)
        except StopIteration:
            return intersection
    if not others:
        return self.copy()  # otherwise we're returning self
    sets = [self] + [OrderedSet(other) if not isinstance(other, OrderedSet)
                     or isinstance(other, OrderedFrozenset) else other
                     for other in others]
    intersection = functools.reduce(intersect, sets)
    if isinstance(self, OrderedFrozenset):
        frozen       = OrderedFrozenset()
        frozen._tree = intersection._tree
        return frozen
    return intersection

OrderedSet.intersection = OrderedFrozenset.intersection = intersection
del intersection<jupyter_output><empty_output><jupyter_text>Für die Operatoren `__and__` und `__rand__` können wir wieder die Uncurry-Funktionen benutzen.<jupyter_code>OrderedSet.__and__        = OrderedSet._uncurry_reg_op(OrderedSet.intersection)
OrderedFrozenset.__and__  = OrderedFrozenset._uncurry_reg_op(
    OrderedFrozenset.intersection)
OrderedSet.__rand__       = OrderedSet._uncurry_rev_op(OrderedSet.intersection)
OrderedFrozenset.__rand__ = OrderedFrozenset._uncurry_rev_op(
    OrderedFrozenset.intersection)<jupyter_output><empty_output><jupyter_text>Schnittmenge in-placeVerwandt mit diesen Methoden sind `intersection_update` und `__iand__` (`&=`), die die Schnittmenge *in-place* berechnen, das heißt, sie überschreiben die Menge direkt. Hier definieren wir `intersect_update`, welches ähnlich zu `intersect` ist, nur eben in-place funktioniert, sodass die Menge selbst nicht kopiert werden muss. Wir können nicht konventionell durch die Menge iterieren, wenn wir sie unterdessen verändern, sodass wir die Möglichkeit des Splayens ausnutzen: Beim Entfernen eines Knotens ist die neue Wurzel gerade das nächstgrößere Element. Gehen wir regulär weiter, so können wir einfach das Minimum aus dem rechten Teilbaum hochsplayen.Gerade weil diese Methoden die Menge überschreiben, sind sie keine Methoden von `OrderedFrozenset`.<jupyter_code>def intersection_update(self, *others):
    def intersect_update(self, other):
        self._tree = self._tree._splay(self.minimum())
        other_iter = iter(other)
        try:
            other_item = next(other_iter)
            while True:
                if self._arb_lt(self._tree.payload, other_item):
                    if self._tree.right is None:
                        raise StopIteration
                    minimum = self._tree.left is None
                    self.remove(self._tree.payload)  # equivalent to moving on
                    if minimum and self._tree is not None:
                        # removal leads to using right subtree
                        # instead of next element
                        self._tree = self._tree._splay(self.minimum())
                    continue
                if self._arb_gt(self._tree.payload, other_item):
                    other_item = next(other_iter)
                    continue
                if self._tree.right is None:
                    return
                # equivalent to inserting and moving on
                self._tree = self._tree._splay(self._tree.right.minimum())
                other_item = next(other_iter)
        except StopIteration:
            # leave the rest
            self._tree = self._tree.left
    for other in others:
        if self._tree is None:
            return
        if not (isinstance(other, OrderedSet)
                or isinstance(other, OrderedFrozenset)) \
                or id(self) == id(other):  # don't iterate through self
            other = OrderedSet(other)
        intersect_update(self, other)

OrderedSet.intersection_update = intersection_update
del intersection_update<jupyter_output><empty_output><jupyter_text>Als Operator haben wir `__iand__`.<jupyter_code>OrderedSet.__iand__ = OrderedSet._uncurry_inp_op(
    OrderedSet.intersection_update)<jupyter_output><empty_output><jupyter_text>Symmetrische DifferenzFür die symmetrische Differenz ($\bigtriangleup$) brauchen wir out-of-place `symmetric_difference`, welches nur auf zwei Mengen definiert sein muss. Wir wiederholen das Verhalten der Schnittmenge, nur, dass gerade die Elemente reinkommen, die in der anderen Menge nicht vorhanden sind. Dies können wir auch formulieren als:$$\mathrm{symmetric\_difference}: \mathrm{OrderedSet} \times \mathrm{OrderedSet} \to \mathrm{OrderedSet}$$$$\mathrm{symmetric\_difference}(x, y) = \begin{cases}x \cup y &\mathrm{falls}\ \{\} \in \{x, y\}\\\mathrm{OrderedSet}([\mathrm{head}(x)]) \cup \mathrm{symmetric\_difference}(\mathrm{tail}(x), y) &\mathrm{falls}\ \mathrm{head}(x) < \mathrm{head}(y)\\\mathrm{OrderedSet}([\mathrm{head}(y)]) \cup \mathrm{symmetric\_difference}(x, \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) > \mathrm{head}(y)\\\mathrm{symmetric\_difference}(\mathrm{tail}(x), \mathrm{tail}(y)) &\mathrm{falls}\ \mathrm{head}(x) = \mathrm{head}(y)\end{cases}$$Um bei unserer iterativen Implementierung leichter mit der Frage umgehen zu können, welche Menge zuerst zu Ende war, halten wir uns die Ausnahme `OtherStopIteration`, die bedeutet, dass die andere Menge ($y$) zu Ende war.<jupyter_code>def symmetric_difference(self, other):
    class OtherStopIteration(StopIteration):
        pass
    if self._tree is None:
        return type(self)(other)
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other = OrderedSet(other)
    x_iter, y_iter = iter(self), iter(other)
    x_item         = next(x_iter)
    try:
        y_item = next(y_iter)
    except StopIteration:
        return self.copy()
    symmetric_difference = OrderedSet()
    try:
        try:
            while True:
                if self._arb_lt(x_item, y_item):
                    symmetric_difference.add(x_item)
                    try:
                        x_item = next(x_iter)
                    except StopIteration:
                        symmetric_difference.add(y_item)
                        raise StopIteration
                    continue
                if self._arb_gt(x_item, y_item):
                    symmetric_difference.add(y_item)
                    try:
                        y_item = next(y_iter)
                    except StopIteration:
                        symmetric_difference.add(x_item)
                        raise OtherStopIteration
                    continue
                x_item = next(x_iter)
                try:
                    y_item = next(y_iter)
                except StopIteration:
                    symmetric_difference.add(x_item)  # already updated
                    raise OtherStopIteration
        except OtherStopIteration:
            while True:
                symmetric_difference.add(next(x_iter))
    except StopIteration:
        try:
            while True:
                symmetric_difference.add(next(y_iter))
        except StopIteration:
            pass
    if isinstance(self, OrderedFrozenset):
        frozen       = OrderedFrozenset()
        frozen._tree = symmetric_difference._tree
        return frozen
    return symmetric_difference

OrderedSet.symmetric_difference       = symmetric_difference
OrderedFrozenset.symmetric_difference = symmetric_difference
del symmetric_difference<jupyter_output><empty_output><jupyter_text>Als Operation haben wir `__xor__` (`^`) und `__rxor__`.<jupyter_code>OrderedSet.__xor__        = OrderedSet._uncurry_reg_op(
    OrderedSet.symmetric_difference)
OrderedFrozenset.__xor__  = OrderedFrozenset._uncurry_reg_op(
    OrderedFrozenset.symmetric_difference)
OrderedSet.__rxor__       = OrderedSet._uncurry_rev_op(
    OrderedSet.symmetric_difference)
OrderedFrozenset.__rxor__ = OrderedFrozenset._uncurry_rev_op(
    OrderedFrozenset.symmetric_difference)<jupyter_output><empty_output><jupyter_text>Symmetrische Differenz in-placeWenn wir die symmetrische Differenz in-place, also überschreibend berechnen, benutzen wir stattdessen `SelfStopIteration`, da dies den Code verkürzt. Ansonsten gehen wir ähnlich vor. Wir nutzen wieder aus, dass beim Entfernen das nächste Element an der Wurzel steht.<jupyter_code>def symmetric_difference_update(self, other):
    class SelfStopIteration(StopIteration):
        pass
    if self._tree is None:
        return OrderedSet(other)
    if id(self) == id(other):
        self._tree = None
        return  # iteration through self is unstable
    if not (isinstance(other, OrderedSet)
            or isinstance(other, OrderedFrozenset)):
        other = OrderedSet(other)
    self._tree = self._tree._splay(self.minimum())
    other_iter = iter(other)
    try:
        other_item = next(other_iter)
        try:
            while True:
                if self._arb_lt(self._tree.payload, other_item):
                    if self._tree.right is None:
                        self.add(other_item)
                        raise SelfStopIteration
                    self._tree = self._tree._splay(self._tree.right.minimum())
                    continue
                if self._arb_gt(self._tree.payload, other_item):
                    root = self._tree.payload
                    self.add(other_item)
                    self._tree = self._tree._splay(root)
                    other_item = next(other_iter)
                    continue
                minimum = self._tree.left is None
                maximum = self._tree.right is None
                self.remove(self._tree.payload)
                if self._tree is None or maximum:
                    raise SelfStopIteration
                if minimum:
                    self._tree = self._tree._splay(self.minimum())
                other_item = next(other_iter)
        except SelfStopIteration:
            while True:
                self.add(next(other_iter))
    except StopIteration:
        return

OrderedSet.symmetric_difference_update = symmetric_difference_update
del symmetric_difference_update<jupyter_output><empty_output><jupyter_text>Als Operation haben wir `__ixor__` (`^=`).<jupyter_code>OrderedSet.__ixor__ = OrderedSet._uncurry_inp_op(
    OrderedSet.symmetric_difference_update)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09925288946595433, 'fraction_numerical': 0.0006811264128051765, 'mean_word_length': 3.6720365950676213, 'pattern_counts': {'":': 0, '<': 237, '<?xml version=': 0, '>': 240, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '56', 'dir': 'jupyter-structured-clean-dedup', 'id': '494156', 'license': 'MIT', 'n_tokens_mistral': 15236, 'n_tokens_neox': 15113, 'n_words': 3914, 'path': '2-Ordered-Sets.ipynb', 'repo_name': 'jakobn-ai/SplayPy-Paper', 'size': '46990'}