2-Ordered-Sets.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>.container{width:100%;}</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%HTML\n",
    "<style>.container{width:100%;}</style>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dieses Notebook hängt vom Notebook `1-Splay-Trees.ipynb` ab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>.container{width:100%;}</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%run 1-Splay-Trees.ipynb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zusätzlich benötigen wir Funktionen aus den `collections` sowie aus den `functools`, die beide schon in Python-Distributionen enthalten sind."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "import functools"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mengen auf Basis von Splay Trees\n",
    "\n",
    "Wir benutzen nun die Splay Trees, um Mengen (`set`) in Python mit Ordnung zu unterstützen.\n",
    "\n",
    "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 \"R. D. Hettinger et al. (2019): cpython/Objects/setobject.c, GitHub\")):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on class set in module builtins:\n",
      "\n",
      "class set(object)\n",
      " |  set() -> new empty set object\n",
      " |  set(iterable) -> new set object\n",
      " |  \n",
      " |  Build an unordered collection of unique elements.\n",
      " |  \n",
      " |  Methods defined here:\n",
      " |  \n",
      " |  __and__(self, value, /)\n",
      " |      Return self&value.\n",
      " |  \n",
      " |  __contains__(...)\n",
      " |      x.__contains__(y) <==> y in x.\n",
      " |  \n",
      " |  __eq__(self, value, /)\n",
      " |      Return self==value.\n",
      " |  \n",
      " |  __ge__(self, value, /)\n",
      " |      Return self>=value.\n",
      " |  \n",
      " |  __getattribute__(self, name, /)\n",
      " |      Return getattr(self, name).\n",
      " |  \n",
      " |  __gt__(self, value, /)\n",
      " |      Return self>value.\n",
      " |  \n",
      " |  __iand__(self, value, /)\n",
      " |      Return self&=value.\n",
      " |  \n",
      " |  __init__(self, /, *args, **kwargs)\n",
      " |      Initialize self.  See help(type(self)) for accurate signature.\n",
      " |  \n",
      " |  __ior__(self, value, /)\n",
      " |      Return self|=value.\n",
      " |  \n",
      " |  __isub__(self, value, /)\n",
      " |      Return self-=value.\n",
      " |  \n",
      " |  __iter__(self, /)\n",
      " |      Implement iter(self).\n",
      " |  \n",
      " |  __ixor__(self, value, /)\n",
      " |      Return self^=value.\n",
      " |  \n",
      " |  __le__(self, value, /)\n",
      " |      Return self<=value.\n",
      " |  \n",
      " |  __len__(self, /)\n",
      " |      Return len(self).\n",
      " |  \n",
      " |  __lt__(self, value, /)\n",
      " |      Return self<value.\n",
      " |  \n",
      " |  __ne__(self, value, /)\n",
      " |      Return self!=value.\n",
      " |  \n",
      " |  __or__(self, value, /)\n",
      " |      Return self|value.\n",
      " |  \n",
      " |  __rand__(self, value, /)\n",
      " |      Return value&self.\n",
      " |  \n",
      " |  __reduce__(...)\n",
      " |      Return state information for pickling.\n",
      " |  \n",
      " |  __repr__(self, /)\n",
      " |      Return repr(self).\n",
      " |  \n",
      " |  __ror__(self, value, /)\n",
      " |      Return value|self.\n",
      " |  \n",
      " |  __rsub__(self, value, /)\n",
      " |      Return value-self.\n",
      " |  \n",
      " |  __rxor__(self, value, /)\n",
      " |      Return value^self.\n",
      " |  \n",
      " |  __sizeof__(...)\n",
      " |      S.__sizeof__() -> size of S in memory, in bytes\n",
      " |  \n",
      " |  __sub__(self, value, /)\n",
      " |      Return self-value.\n",
      " |  \n",
      " |  __xor__(self, value, /)\n",
      " |      Return self^value.\n",
      " |  \n",
      " |  add(...)\n",
      " |      Add an element to a set.\n",
      " |      \n",
      " |      This has no effect if the element is already present.\n",
      " |  \n",
      " |  clear(...)\n",
      " |      Remove all elements from this set.\n",
      " |  \n",
      " |  copy(...)\n",
      " |      Return a shallow copy of a set.\n",
      " |  \n",
      " |  difference(...)\n",
      " |      Return the difference of two or more sets as a new set.\n",
      " |      \n",
      " |      (i.e. all elements that are in this set but not the others.)\n",
      " |  \n",
      " |  difference_update(...)\n",
      " |      Remove all elements of another set from this set.\n",
      " |  \n",
      " |  discard(...)\n",
      " |      Remove an element from a set if it is a member.\n",
      " |      \n",
      " |      If the element is not a member, do nothing.\n",
      " |  \n",
      " |  intersection(...)\n",
      " |      Return the intersection of two sets as a new set.\n",
      " |      \n",
      " |      (i.e. all elements that are in both sets.)\n",
      " |  \n",
      " |  intersection_update(...)\n",
      " |      Update a set with the intersection of itself and another.\n",
      " |  \n",
      " |  isdisjoint(...)\n",
      " |      Return True if two sets have a null intersection.\n",
      " |  \n",
      " |  issubset(...)\n",
      " |      Report whether another set contains this set.\n",
      " |  \n",
      " |  issuperset(...)\n",
      " |      Report whether this set contains another set.\n",
      " |  \n",
      " |  pop(...)\n",
      " |      Remove and return an arbitrary set element.\n",
      " |      Raises KeyError if the set is empty.\n",
      " |  \n",
      " |  remove(...)\n",
      " |      Remove an element from a set; it must be a member.\n",
      " |      \n",
      " |      If the element is not a member, raise a KeyError.\n",
      " |  \n",
      " |  symmetric_difference(...)\n",
      " |      Return the symmetric difference of two sets as a new set.\n",
      " |      \n",
      " |      (i.e. all elements that are in exactly one of the sets.)\n",
      " |  \n",
      " |  symmetric_difference_update(...)\n",
      " |      Update a set with the symmetric difference of itself and another.\n",
      " |  \n",
      " |  union(...)\n",
      " |      Return the union of sets as a new set.\n",
      " |      \n",
      " |      (i.e. all elements that are in either set.)\n",
      " |  \n",
      " |  update(...)\n",
      " |      Update a set with the union of itself and others.\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Static methods defined here:\n",
      " |  \n",
      " |  __new__(*args, **kwargs) from builtins.type\n",
      " |      Create and return a new object.  See help(type) for accurate signature.\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Data and other attributes defined here:\n",
      " |  \n",
      " |  __hash__ = None\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(set)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir definieren dafür die Klasse `OrderedSet`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class OrderedSet:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Konstruktion\n",
    "\n",
    "Wenn 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.\n",
    "\n",
    "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.)\n",
    "\n",
    "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.html#set \"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.\n",
    "\n",
    "Wir wollen auch die `frozenset`s geordnet haben und werden sie parallel mitimplementieren."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "class OrderedFrozenset:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir übernehmen `_arb_lt`, `_arb_eq` und `_arb_gt` von `Node`, sodass wir direkt Zugriff darauf haben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet._arb_lt = OrderedFrozenset._arb_lt = Node._arb_lt\n",
    "OrderedSet._arb_eq = OrderedFrozenset._arb_eq = Node._arb_eq\n",
    "OrderedSet._arb_gt = OrderedFrozenset._arb_gt = Node._arb_gt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __init__(self, iterable=[]):\n",
    "    if isinstance(self, OrderedFrozenset) and hasattr(self, \"_tree\"):\n",
    "        return  # frozenset was already created\n",
    "    self._tree = None\n",
    "    iterator   = iter(iterable)\n",
    "    try:\n",
    "        element = next(iterator)\n",
    "        if not element.__hash__:\n",
    "            raise TypeError(f\"unhashable type: '{type(element).__name__}'\")\n",
    "        self._tree = Node(element, None, None)\n",
    "        while True:\n",
    "            element = next(iterator)\n",
    "            if not element.__hash__:\n",
    "                raise TypeError(\"unhashable type: \" +\n",
    "                                f\"'{type(element).__name__}'\")\n",
    "            self._tree = self._tree.insert(element)\n",
    "    except StopIteration:\n",
    "        pass\n",
    "\n",
    "OrderedSet.__init__ = OrderedFrozenset.__init__ = __init__\n",
    "del __init__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Lexikographische Ordnung\n",
    "\n",
    "Wir müssen, wenn wir geordnete Mengen von geordneten Mengen unterstützen wollen, die totalen Ordnungen `<` und `>` 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 `<` und `>` 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 `<` und `>`, sondern andere Methoden verwenden. Die damit verbundenen Performanceeinbußen sind jedoch nicht vertretbar.\n",
    "\n",
    "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.\n",
    "\n",
    "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.html#collections.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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __iter__(self):\n",
    "    stack = collections.deque()\n",
    "    tree  = self._tree\n",
    "    while stack or tree is not None:\n",
    "        if tree is not None:\n",
    "            stack.append(tree)\n",
    "            tree = tree.left\n",
    "            continue\n",
    "        tree = stack.pop()\n",
    "        yield tree.payload\n",
    "        tree = tree.right\n",
    "\n",
    "OrderedSet.__iter__ = OrderedFrozenset.__iter__ = __iter__\n",
    "del __iter__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "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}$.\n",
    "\n",
    "$$\\mathrm{\\_\\_lt\\_\\_}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{\\_\\_lt\\_\\_}(x, y) = \\begin{cases}\n",
    "\\mathrm{false} &\\mathrm{falls}\\ y = \\{\\}\\\\\n",
    "\\mathrm{true} &\\mathrm{falls}\\ x = \\{\\} \\land y \\neq \\{\\}\\\\\n",
    "\\mathrm{true} &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_\\_lt\\_\\_}(\\mathrm{tail}(x), \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __lt__(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        return NotImplemented\n",
    "    x_iter, y_iter = iter(self), iter(other)\n",
    "    while True:\n",
    "        try:\n",
    "            y_item = next(y_iter)\n",
    "        except StopIteration:\n",
    "            return False  # x is longer or equal\n",
    "        try:\n",
    "            x_item = next(x_iter)\n",
    "        except StopIteration:\n",
    "            return True  # x is shorter\n",
    "        if self._arb_lt(x_item, y_item):\n",
    "            return True\n",
    "        if self._arb_gt(x_item, y_item):\n",
    "            return False\n",
    "\n",
    "OrderedSet.__lt__ = OrderedFrozenset.__lt__ = __lt__\n",
    "del __lt__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ähnlich definieren wir `__gt__` für `>`. Formal heißt das:\n",
    "\n",
    "$$\\mathrm{\\_\\_gt\\_\\_}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{\\_\\_gt\\_\\_}(x, y) = \\begin{cases}\n",
    "\\mathrm{false} &\\mathrm{falls}\\ x = \\{\\}\\\\\n",
    "\\mathrm{true} &\\mathrm{falls}\\ x \\neq \\{\\} \\land y = \\{\\}\\\\\n",
    "\\mathrm{true} &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_\\_gt\\_\\_}(\\mathrm{tail}(x), \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __gt__(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        return NotImplemented\n",
    "    x_iter, y_iter = iter(self), iter(other)\n",
    "    while True:\n",
    "        try:\n",
    "            x_item = next(x_iter)\n",
    "        except StopIteration:\n",
    "            return False  # x is shorter or equal\n",
    "        try:\n",
    "            y_item = next(y_iter)\n",
    "        except StopIteration:\n",
    "            return True  # x is longer\n",
    "        if self._arb_gt(x_item, y_item):\n",
    "            return True\n",
    "        if self._arb_lt(x_item, y_item):\n",
    "            return False\n",
    "\n",
    "OrderedSet.__gt__ = OrderedFrozenset.__gt__ = __gt__\n",
    "del __gt__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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:\n",
    "\n",
    "$$\\mathrm{\\_\\_eq\\_\\_}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{\\_\\_eq\\_\\_}(x, y) = \\begin{cases}\n",
    "\\mathrm{true} &\\mathrm{falls}\\ x = \\{\\} \\land y = \\{\\}\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ x = \\{\\}\\ \\dot{\\lor}\\ y = \\{\\}\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ \\mathrm{head}(x) \\neq \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_\\_eq\\_\\_}(\\mathrm{tail}(x), \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __eq__(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        return False\n",
    "    x_iter, y_iter = iter(self), iter(other)\n",
    "    while True:\n",
    "        try:\n",
    "            x_item = next(x_iter)\n",
    "        except StopIteration:\n",
    "            try:  # assert y is also exhausted\n",
    "                next(y_iter)\n",
    "            except StopIteration:\n",
    "                return True\n",
    "            return False\n",
    "        try:\n",
    "            y_item = next(y_iter)\n",
    "        except StopIteration:\n",
    "            return False  # x was not exhausted\n",
    "        if not self._arb_eq(x_item, y_item):\n",
    "            return False\n",
    "\n",
    "OrderedSet.__eq__ = OrderedFrozenset.__eq__ = __eq__\n",
    "del __eq__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`__ne__` für `!=` ist damit schon implizit definiert.\n",
    "\n",
    "### Hashen\n",
    "\n",
    "Der 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __hash__(self):\n",
    "    return sum(hash(el) for el in self)\n",
    "\n",
    "OrderedFrozenset.__hash__ = __hash__\n",
    "del __hash__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Um das Verhalten von Python abzubilden, werfen wir im Fall von `OrderedSet` einen `TypeError`, wenn versucht wird, eines zu hashen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __hash__(self):\n",
    "    raise TypeError(f\"unhashable type: '{type(self).__name__}'\")\n",
    "\n",
    "OrderedSet.__hash__ = __hash__\n",
    "del __hash__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operationen mit einem Element\n",
    "\n",
    "Wir 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.\n",
    "\n",
    "### Hinzufügen\n",
    "\n",
    "Wir implementieren `add`, das Hinzufügen eines Elements, ähnlich wie beim `SplayTree`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(self, element):\n",
    "    if not element.__hash__:\n",
    "        raise TypeError(f\"unhashable type: '{type(element).__name__}'\")\n",
    "    if self._tree is None:\n",
    "        self._tree = Node(element, None, None)\n",
    "    else:\n",
    "        self._tree = self._tree.insert(element)\n",
    "\n",
    "OrderedSet.add = add\n",
    "del add"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Entfernen\n",
    "\n",
    "Das Gegenstück zu `add` ist `remove`, das Entfernen eines Elementes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def remove(self, element):\n",
    "    if not element.__hash__:\n",
    "        raise TypeError(f\"unhashable type: '{type(element).__name__}'\")\n",
    "    if self._tree is None:\n",
    "        raise KeyError(element)\n",
    "    rc, self._tree = self._tree.remove(element)\n",
    "    if not rc:\n",
    "        raise KeyError(element)\n",
    "\n",
    "OrderedSet.remove = remove\n",
    "del remove"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir implementieren auch `discard`, welches ähnlich zu `remove` ist, aber keinen Fehler verursacht, falls das Element nicht vorhanden ist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def discard(self, element):\n",
    "    if not element.__hash__:\n",
    "        raise TypeError(f\"unhashable type: '{type(element).__name__}'\")\n",
    "    if self._tree is not None:\n",
    "        _, self._tree = self._tree.remove(element)\n",
    "\n",
    "OrderedSet.discard = discard\n",
    "del discard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`add`, `remove` und `discard` sind **keine** Methoden von `OrderedFrozenset`, weil diese Operationen die Menge modifizieren!\n",
    "\n",
    "### Finden\n",
    "\n",
    "Eine nichtmodifizierende Operation mit einem Element als Parameter ist `__contains__` (`in`), die wir ebenfalls für `Node` schon implementiert haben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __contains__(self, element):\n",
    "    if not element.__hash__:\n",
    "        raise TypeError(f\"unhashable type: '{type(element).__name__}'\")\n",
    "    if self._tree is None:\n",
    "        return False\n",
    "    contains, self._tree = self._tree.contains(element)\n",
    "    return contains\n",
    "\n",
    "OrderedSet.__contains__ = OrderedFrozenset.__contains__ = __contains__\n",
    "del __contains__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operationen ohne Parameter\n",
    "\n",
    "Wir implementieren im Folgenden Operationen auf die geordnete Menge, die überhaupt keine Parameter haben. Wir beginnen wieder mit solchen, die die Menge verändern.\n",
    "\n",
    "### Kopieren\n",
    "\n",
    "Wir 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.copy       = lambda self: OrderedSet(el for el in self)\n",
    "OrderedFrozenset.copy = lambda self: OrderedFrozenset(el for el in self)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Entfernen eines beliebigen Elements\n",
    "\n",
    "Wir implementieren `pop`, welches ein beliebiges Element entfernt und zurückgibt. Wir entfernen dabei das Minimum des Baums."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pop(self):\n",
    "    if self._tree is None:\n",
    "        raise KeyError(\"pop from an empty set\")\n",
    "    popped = self.minimum()\n",
    "    self.remove(popped)\n",
    "    return popped\n",
    "\n",
    "OrderedSet.pop = pop\n",
    "del pop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Leeren\n",
    "\n",
    "Wir implementieren auch `clear`, welches alle Elemente aus der Menge entfernt. Wir setzen einfach den Baum auf `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def clear(self):\n",
    "    self._tree = None\n",
    "\n",
    "OrderedSet.clear = clear\n",
    "del clear"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Länge\n",
    "\n",
    "Wir 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __len__(self):\n",
    "    return sum(1 for i in self)\n",
    "\n",
    "OrderedSet.__len__ = OrderedFrozenset.__len__ = __len__\n",
    "del __len__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Darstellung\n",
    "\n",
    "Wir 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:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __repr__(self):\n",
    "    if self._tree is None:\n",
    "        return f\"{type(self).__name__}()\"\n",
    "    return f\"{type(self).__name__}({list(self)})\"\n",
    "\n",
    "OrderedSet.__repr__ = OrderedFrozenset.__repr__ = __repr__\n",
    "del __repr__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pickling\n",
    "\n",
    "`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.html#object.__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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __getnewargs__(self):\n",
    "    return (list(self),)\n",
    "\n",
    "OrderedSet.__getnewargs__ = OrderedFrozenset.__getnewargs__ = __getnewargs__\n",
    "del __getnewargs__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimum und Maximum\n",
    "\n",
    "Wir 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"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum(self):\n",
    "    while self.left is not None:\n",
    "        self = self.left\n",
    "    return self.payload\n",
    "\n",
    "Node.minimum = minimum\n",
    "del minimum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "und für `OrderedSet` und `OrderedFrozenset`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minimum(self):\n",
    "    if self._tree is None:\n",
    "        raise ValueError(\"Set is empty\")\n",
    "    return self._tree.minimum()\n",
    "\n",
    "OrderedSet.minimum = OrderedFrozenset.minimum = minimum\n",
    "del minimum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir implementieren auch `maximum`, bei der wir die Nutzlast des rechtesten Knotens zurückgeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum(self):\n",
    "    while self.right is not None:\n",
    "        self = self.right\n",
    "    return self.payload\n",
    "\n",
    "Node.maximum = maximum\n",
    "del maximum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "und für die `Set`-Klassen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximum(self):\n",
    "    if self._tree is None:\n",
    "        raise ValueError(\"Set is empty\")\n",
    "    return self._tree.maximum()\n",
    "\n",
    "OrderedSet.maximum = OrderedFrozenset.maximum = maximum\n",
    "del maximum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolesche Operationen auf andere Mengen\n",
    "\n",
    "Wir implementieren im Folgenden Operationen auf andere Mengen, die einen Wahrheitswert als Ergebnis haben. `==` und `!=` hatten wir schon für die lexikographische Ordnung implementiert.\n",
    "\n",
    "### Teilmenge\n",
    "\n",
    "Wir 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.\n",
    "\n",
    "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.\n",
    "\n",
    "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\n",
    "\n",
    "$$\\mathrm{\\_subseteq}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{\\_subseteq}(x, y) = \\begin{cases}\n",
    "\\mathrm{true} &\\mathrm{falls}\\ x = \\{\\}\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ x \\neq \\{\\} \\land y = \\{\\}\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_subseteq}(x, \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_subseteq}(\\mathrm{tail}(x), \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _subseteq(self, x, y):\n",
    "    x_iter, y_iter = iter(x), iter(y)\n",
    "    while True:\n",
    "        try:\n",
    "            x_item = next(x_iter)\n",
    "        except StopIteration:\n",
    "            return True\n",
    "        while True:\n",
    "            try:\n",
    "                y_item = next(y_iter)\n",
    "            except StopIteration:\n",
    "                return False\n",
    "            if self._arb_lt(x_item, y_item):\n",
    "                return False\n",
    "            if self._arb_eq(x_item, y_item):\n",
    "                break\n",
    "\n",
    "OrderedSet._subseteq = OrderedFrozenset._subseteq = _subseteq\n",
    "del _subseteq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So können wir `issubset` implementieren, wo wir das andere Iterable gegebenenfalls in ein `OrderedFrozenset` bringen und so sortieren."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def issubset(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other = OrderedFrozenset(other)\n",
    "    return self._subseteq(self, other)\n",
    "\n",
    "OrderedSet.issubset = OrderedFrozenset.issubset = issubset\n",
    "del issubset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bei `__le__` erlauben wir für den anderen Operanden nur `OrderedSet` und `OrderedFrozenset`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __le__(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        return NotImplemented\n",
    "    return self._subseteq(self, other)\n",
    "\n",
    "OrderedSet.__le__ = OrderedFrozenset.__le__ = __le__\n",
    "del __le__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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$.\n",
    "\n",
    "Formal schreiben wir zusätzlich `_subsetneq_help` mit zusätzlichem Parameter $p$ (proper). Zu Beginn ist dieser $\\mathrm{false}$.\n",
    "\n",
    "$$\\mathrm{\\_subsetneq}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{\\_subsetneq}(x, y) = \\mathrm{\\_subsetneq\\_help}(x, y, \\mathrm{false})$$\n",
    "$$\\mathrm{\\_subsetneq\\_help}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\times \\mathbb{B} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{\\_subsetneq\\_help}(x, y, p) = \\begin{cases}\n",
    "p &\\mathrm{falls}\\ y = \\{\\}\\\\\n",
    "\\mathrm{true} &\\mathrm{falls}\\ x = \\{\\} \\land y \\neq \\{\\}\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_subsetneq\\_help}(x, \\mathrm{tail}(y), \\mathrm{true}) &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\\\\\n",
    "\\mathrm{\\_subsetneq\\_help}(\\mathrm{tail}(x), \\mathrm{tail}(y), p) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _subsetneq(self, x, y):\n",
    "    x_iter, y_iter = iter(x), iter(y)\n",
    "    proper_subset  = False\n",
    "    while True:\n",
    "        try:\n",
    "            x_item = next(x_iter)\n",
    "        except StopIteration:\n",
    "            if not proper_subset:\n",
    "                try:  # assert y is not exhausted\n",
    "                    next(y_iter)\n",
    "                except StopIteration:\n",
    "                    return False\n",
    "            return True\n",
    "        while True:\n",
    "            try:\n",
    "                y_item = next(y_iter)\n",
    "            except StopIteration:\n",
    "                return False\n",
    "            if self._arb_lt(x_item, y_item):\n",
    "                return False\n",
    "            if self._arb_gt(x_item, y_item):\n",
    "                proper_subset = True\n",
    "            else:\n",
    "                break\n",
    "\n",
    "OrderedSet._subsetneq = OrderedFrozenset._subsetneq = _subsetneq\n",
    "del _subsetneq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So können wir `is_proper_subset` ähnlich wie `issubset` implementieren."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_proper_subset(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other = OrderedSet(other)\n",
    "    return self._subsetneq(self, other)\n",
    "\n",
    "OrderedSet.is_proper_subset       = is_proper_subset\n",
    "OrderedFrozenset.is_proper_subset = is_proper_subset\n",
    "del is_proper_subset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Obermenge\n",
    "\n",
    "Wir 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`…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def issuperset(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other = OrderedSet(other)\n",
    "    return self._subseteq(other, self)\n",
    "\n",
    "OrderedSet.issuperset = OrderedFrozenset.issuperset = issuperset\n",
    "del issuperset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "…`__ge__` (`>=`, in der Mengenlehre $\\supseteq$)…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def __ge__(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        return NotImplemented\n",
    "    return self._subseteq(other, self)\n",
    "\n",
    "OrderedSet.__ge__ = OrderedFrozenset.__ge__ = __ge__\n",
    "del __ge__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "…und `is_proper_superset` statt `__gt__` (`>`, in der Mengenlehre $\\supset$ bzw. $\\supsetneq$)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_proper_superset(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other = OrderedSet(other)\n",
    "    return self._subsetneq(other, self)\n",
    "\n",
    "OrderedSet.is_proper_superset       = is_proper_superset\n",
    "OrderedFrozenset.is_proper_superset = is_proper_superset\n",
    "del is_proper_superset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Überprüfen, ob Mengen disjunkt sind\n",
    "\n",
    "Wir 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:\n",
    "\n",
    "$$\\mathrm{isdisjoint}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathbb{B}$$\n",
    "$$\\mathrm{isdisjoint}(x, y) = \\begin{cases}\n",
    "\\mathrm{true} &\\mathrm{falls}\\ \\{\\} \\in \\{x, y\\}\\\\\n",
    "\\mathrm{false} &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\\\\\n",
    "\\mathrm{isdisjoint}(\\mathrm{tail}(x), y) &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{isdisjoint}(x, \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\n",
    "\\end{cases}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isdisjoint(self, other):\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other      = OrderedSet(other)\n",
    "    x_iter, y_iter = iter(self), iter(other)\n",
    "    try:\n",
    "        y_item = next(y_iter)  # we need a y_item ready for first comparison\n",
    "    except StopIteration:\n",
    "        return True\n",
    "    while True:\n",
    "        try:\n",
    "            x_item = next(x_iter)\n",
    "        except StopIteration:\n",
    "            return True\n",
    "        while True:\n",
    "            if self._arb_lt(x_item, y_item):\n",
    "                break\n",
    "            if self._arb_gt(x_item, y_item):\n",
    "                try:\n",
    "                    y_item = next(y_iter)\n",
    "                except StopIteration:\n",
    "                    return True\n",
    "                continue\n",
    "            return False\n",
    "\n",
    "OrderedSet.isdisjoint = OrderedFrozenset.isdisjoint = isdisjoint\n",
    "del isdisjoint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Verknüpfung von Mengen\n",
    "\n",
    "Zuletzt implementieren wir die Operationen auf andere Mengen, die eine Menge als Ergebnis haben. Wir beginnen mit den einfacheren Vereinigungs- und Differenzmengen.\n",
    "\n",
    "### Vereinigungsmenge\n",
    "\n",
    "Bei 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def union(self, *others):\n",
    "    union = OrderedSet(self)\n",
    "    for other in others:\n",
    "        for el in other:\n",
    "            union.add(el)\n",
    "    if isinstance(self, OrderedFrozenset):\n",
    "        frozen       = OrderedFrozenset()\n",
    "        frozen._tree = union._tree\n",
    "        return frozen\n",
    "    return union\n",
    "\n",
    "OrderedSet.union = OrderedFrozenset.union = union\n",
    "del union"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _uncurry_reg_op(func):\n",
    "    def reg_op(self, other):\n",
    "        if isinstance(other, OrderedSet) \\\n",
    "                or isinstance(other, OrderedFrozenset):\n",
    "            # this style is necessary when uncurrying a class function\n",
    "            return func(self, other)\n",
    "        else:\n",
    "            return NotImplemented\n",
    "    return reg_op\n",
    "\n",
    "OrderedSet._uncurry_reg_op = OrderedFrozenset._uncurry_reg_op = _uncurry_reg_op\n",
    "del _uncurry_reg_op"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nun können wir für beide Klassen `__or__` setzen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__or__       = OrderedSet._uncurry_reg_op(OrderedSet.union)\n",
    "OrderedFrozenset.__or__ = OrderedFrozenset._uncurry_reg_op(\n",
    "    OrderedFrozenset.union)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _uncurry_rev_op(func):\n",
    "    def rev_op(self, other):\n",
    "        if isinstance(other, OrderedSet) \\\n",
    "                or isinstance(other, OrderedFrozenset):\n",
    "            return func(other, self)\n",
    "        else:\n",
    "            return NotImplemented\n",
    "    return rev_op\n",
    "\n",
    "OrderedSet._uncurry_rev_op = OrderedFrozenset._uncurry_rev_op = _uncurry_rev_op\n",
    "del _uncurry_rev_op"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Setzen von `__ror__` verläuft analog."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__ror__       = OrderedSet._uncurry_rev_op(OrderedSet.union)\n",
    "OrderedFrozenset.__ror__ = OrderedFrozenset._uncurry_rev_op(\n",
    "    OrderedFrozenset.union)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update(self, *others):\n",
    "    for other in others:\n",
    "        for el in other:\n",
    "            self.add(el)\n",
    "\n",
    "OrderedSet.update = update\n",
    "del update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _uncurry_inp_op(func):\n",
    "    def inp_op(self, other):\n",
    "        if isinstance(other, OrderedSet) \\\n",
    "                or isinstance(other, OrderedFrozenset):\n",
    "            func(self, other)\n",
    "            return self\n",
    "        else:\n",
    "            return NotImplemented\n",
    "    return inp_op\n",
    "\n",
    "OrderedSet._uncurry_inp_op = _uncurry_inp_op\n",
    "del _uncurry_inp_op"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So können wir `__ior__` setzen, natürlich nur für `OrderedSet`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__ior__ = OrderedSet._uncurry_inp_op(OrderedSet.update)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Differenzmenge\n",
    "\n",
    "Es folgt die Differenzmenge ($\\setminus$), für die wir einfach alle Elemente entfernen. Dafür haben wir `difference`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "def difference(self, *others):\n",
    "    difference = OrderedSet(self)\n",
    "    for other in others:\n",
    "        for el in other:\n",
    "            if not el.__hash__:\n",
    "                raise TypeError(f\"unhashable type: '{type(el).__name__}'\")\n",
    "            difference.discard(el)\n",
    "    if isinstance(self, OrderedFrozenset):\n",
    "        frozen       = OrderedFrozenset()\n",
    "        frozen._tree = difference._tree\n",
    "        return frozen\n",
    "    return difference\n",
    "\n",
    "OrderedSet.difference = OrderedFrozenset.difference = difference\n",
    "del difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als Operatoren haben wir `__sub__` (`-`) und `__rsub__` (reverse)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__sub__        = OrderedSet._uncurry_reg_op(OrderedSet.difference)\n",
    "OrderedFrozenset.__sub__  = OrderedFrozenset._uncurry_reg_op(\n",
    "    OrderedFrozenset.difference)\n",
    "OrderedSet.__rsub__       = OrderedSet._uncurry_rev_op(OrderedSet.difference)\n",
    "OrderedFrozenset.__rsub__ = OrderedFrozenset._uncurry_rev_op(\n",
    "    OrderedFrozenset.difference)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In-place haben wir `difference_update`…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def difference_update(self, *others):\n",
    "    for other in others:\n",
    "        for el in other:\n",
    "            if not el.__hash__:\n",
    "                raise TypeError(f\"unhashable type: '{type(el).__name__}'\")\n",
    "            self.discard(el)\n",
    "\n",
    "OrderedSet.difference_update = difference_update\n",
    "del difference_update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "…und `__isub__` (`-=`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__isub__ = OrderedSet._uncurry_inp_op(\n",
    "    OrderedSet.difference_update)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Schnittmenge\n",
    "\n",
    "Komplexer 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.\n",
    "\n",
    "$$\\mathrm{intersect}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathrm{OrderedSet}$$\n",
    "$$\\mathrm{intersect}(x, y) = \\begin{cases}\n",
    "\\mathrm{OrderedSet}() &\\mathrm{falls}\\ \\{\\} \\in \\{x, y\\}\\\\\n",
    "\\mathrm{intersect}(\\mathrm{tail}(x), y) &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{intersect}(x, \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\\\\\n",
    "\\mathrm{OrderedSet}([\\mathrm{head}(x)]) \\cup \\mathrm{intersect}(\\mathrm{tail}(x), \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$\n",
    "\n",
    "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.html#functools.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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection(self, *others):\n",
    "    def intersect(x, y):\n",
    "        intersection   = OrderedSet()\n",
    "        x_iter, y_iter = iter(x), iter(y)\n",
    "        try:\n",
    "            x_item, y_item = next(x_iter), next(y_iter)\n",
    "            while True:\n",
    "                if self._arb_lt(x_item, y_item):\n",
    "                    x_item = next(x_iter)\n",
    "                    continue\n",
    "                if self._arb_gt(x_item, y_item):\n",
    "                    y_item = next(y_iter)\n",
    "                    continue\n",
    "                intersection.add(x_item)\n",
    "                x_item, y_item = next(x_iter), next(y_iter)\n",
    "        except StopIteration:\n",
    "            return intersection\n",
    "    if not others:\n",
    "        return self.copy()  # otherwise we're returning self\n",
    "    sets = [self] + [OrderedSet(other) if not isinstance(other, OrderedSet)\n",
    "                     or isinstance(other, OrderedFrozenset) else other\n",
    "                     for other in others]\n",
    "    intersection = functools.reduce(intersect, sets)\n",
    "    if isinstance(self, OrderedFrozenset):\n",
    "        frozen       = OrderedFrozenset()\n",
    "        frozen._tree = intersection._tree\n",
    "        return frozen\n",
    "    return intersection\n",
    "\n",
    "OrderedSet.intersection = OrderedFrozenset.intersection = intersection\n",
    "del intersection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für die Operatoren `__and__` und `__rand__` können wir wieder die Uncurry-Funktionen benutzen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__and__        = OrderedSet._uncurry_reg_op(OrderedSet.intersection)\n",
    "OrderedFrozenset.__and__  = OrderedFrozenset._uncurry_reg_op(\n",
    "    OrderedFrozenset.intersection)\n",
    "OrderedSet.__rand__       = OrderedSet._uncurry_rev_op(OrderedSet.intersection)\n",
    "OrderedFrozenset.__rand__ = OrderedFrozenset._uncurry_rev_op(\n",
    "    OrderedFrozenset.intersection)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Schnittmenge in-place\n",
    "\n",
    "Verwandt 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.\n",
    "\n",
    "Gerade weil diese Methoden die Menge überschreiben, sind sie keine Methoden von `OrderedFrozenset`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection_update(self, *others):\n",
    "    def intersect_update(self, other):\n",
    "        self._tree = self._tree._splay(self.minimum())\n",
    "        other_iter = iter(other)\n",
    "        try:\n",
    "            other_item = next(other_iter)\n",
    "            while True:\n",
    "                if self._arb_lt(self._tree.payload, other_item):\n",
    "                    if self._tree.right is None:\n",
    "                        raise StopIteration\n",
    "                    minimum = self._tree.left is None\n",
    "                    self.remove(self._tree.payload)  # equivalent to moving on\n",
    "                    if minimum and self._tree is not None:\n",
    "                        # removal leads to using right subtree\n",
    "                        # instead of next element\n",
    "                        self._tree = self._tree._splay(self.minimum())\n",
    "                    continue\n",
    "                if self._arb_gt(self._tree.payload, other_item):\n",
    "                    other_item = next(other_iter)\n",
    "                    continue\n",
    "                if self._tree.right is None:\n",
    "                    return\n",
    "                # equivalent to inserting and moving on\n",
    "                self._tree = self._tree._splay(self._tree.right.minimum())\n",
    "                other_item = next(other_iter)\n",
    "        except StopIteration:\n",
    "            # leave the rest\n",
    "            self._tree = self._tree.left\n",
    "    for other in others:\n",
    "        if self._tree is None:\n",
    "            return\n",
    "        if not (isinstance(other, OrderedSet)\n",
    "                or isinstance(other, OrderedFrozenset)) \\\n",
    "                or id(self) == id(other):  # don't iterate through self\n",
    "            other = OrderedSet(other)\n",
    "        intersect_update(self, other)\n",
    "\n",
    "OrderedSet.intersection_update = intersection_update\n",
    "del intersection_update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als Operator haben wir `__iand__`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__iand__ = OrderedSet._uncurry_inp_op(\n",
    "    OrderedSet.intersection_update)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Symmetrische Differenz\n",
    "\n",
    "Fü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:\n",
    "\n",
    "$$\\mathrm{symmetric\\_difference}: \\mathrm{OrderedSet} \\times \\mathrm{OrderedSet} \\to \\mathrm{OrderedSet}$$\n",
    "$$\\mathrm{symmetric\\_difference}(x, y) = \\begin{cases}\n",
    "x \\cup y &\\mathrm{falls}\\ \\{\\} \\in \\{x, y\\}\\\\\n",
    "\\mathrm{OrderedSet}([\\mathrm{head}(x)]) \\cup \\mathrm{symmetric\\_difference}(\\mathrm{tail}(x), y) &\\mathrm{falls}\\ \\mathrm{head}(x) < \\mathrm{head}(y)\\\\\n",
    "\\mathrm{OrderedSet}([\\mathrm{head}(y)]) \\cup \\mathrm{symmetric\\_difference}(x, \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) > \\mathrm{head}(y)\\\\\n",
    "\\mathrm{symmetric\\_difference}(\\mathrm{tail}(x), \\mathrm{tail}(y)) &\\mathrm{falls}\\ \\mathrm{head}(x) = \\mathrm{head}(y)\n",
    "\\end{cases}$$\n",
    "\n",
    "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. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "def symmetric_difference(self, other):\n",
    "    class OtherStopIteration(StopIteration):\n",
    "        pass\n",
    "    if self._tree is None:\n",
    "        return type(self)(other)\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other = OrderedSet(other)\n",
    "    x_iter, y_iter = iter(self), iter(other)\n",
    "    x_item         = next(x_iter)\n",
    "    try:\n",
    "        y_item = next(y_iter)\n",
    "    except StopIteration:\n",
    "        return self.copy()\n",
    "    symmetric_difference = OrderedSet()\n",
    "    try:\n",
    "        try:\n",
    "            while True:\n",
    "                if self._arb_lt(x_item, y_item):\n",
    "                    symmetric_difference.add(x_item)\n",
    "                    try:\n",
    "                        x_item = next(x_iter)\n",
    "                    except StopIteration:\n",
    "                        symmetric_difference.add(y_item)\n",
    "                        raise StopIteration\n",
    "                    continue\n",
    "                if self._arb_gt(x_item, y_item):\n",
    "                    symmetric_difference.add(y_item)\n",
    "                    try:\n",
    "                        y_item = next(y_iter)\n",
    "                    except StopIteration:\n",
    "                        symmetric_difference.add(x_item)\n",
    "                        raise OtherStopIteration\n",
    "                    continue\n",
    "                x_item = next(x_iter)\n",
    "                try:\n",
    "                    y_item = next(y_iter)\n",
    "                except StopIteration:\n",
    "                    symmetric_difference.add(x_item)  # already updated\n",
    "                    raise OtherStopIteration\n",
    "        except OtherStopIteration:\n",
    "            while True:\n",
    "                symmetric_difference.add(next(x_iter))\n",
    "    except StopIteration:\n",
    "        try:\n",
    "            while True:\n",
    "                symmetric_difference.add(next(y_iter))\n",
    "        except StopIteration:\n",
    "            pass\n",
    "    if isinstance(self, OrderedFrozenset):\n",
    "        frozen       = OrderedFrozenset()\n",
    "        frozen._tree = symmetric_difference._tree\n",
    "        return frozen\n",
    "    return symmetric_difference\n",
    "\n",
    "OrderedSet.symmetric_difference       = symmetric_difference\n",
    "OrderedFrozenset.symmetric_difference = symmetric_difference\n",
    "del symmetric_difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als Operation haben wir `__xor__` (`^`) und `__rxor__`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__xor__        = OrderedSet._uncurry_reg_op(\n",
    "    OrderedSet.symmetric_difference)\n",
    "OrderedFrozenset.__xor__  = OrderedFrozenset._uncurry_reg_op(\n",
    "    OrderedFrozenset.symmetric_difference)\n",
    "OrderedSet.__rxor__       = OrderedSet._uncurry_rev_op(\n",
    "    OrderedSet.symmetric_difference)\n",
    "OrderedFrozenset.__rxor__ = OrderedFrozenset._uncurry_rev_op(\n",
    "    OrderedFrozenset.symmetric_difference)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Symmetrische Differenz in-place\n",
    "\n",
    "Wenn 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "def symmetric_difference_update(self, other):\n",
    "    class SelfStopIteration(StopIteration):\n",
    "        pass\n",
    "    if self._tree is None:\n",
    "        return OrderedSet(other)\n",
    "    if id(self) == id(other):\n",
    "        self._tree = None\n",
    "        return  # iteration through self is unstable\n",
    "    if not (isinstance(other, OrderedSet)\n",
    "            or isinstance(other, OrderedFrozenset)):\n",
    "        other = OrderedSet(other)\n",
    "    self._tree = self._tree._splay(self.minimum())\n",
    "    other_iter = iter(other)\n",
    "    try:\n",
    "        other_item = next(other_iter)\n",
    "        try:\n",
    "            while True:\n",
    "                if self._arb_lt(self._tree.payload, other_item):\n",
    "                    if self._tree.right is None:\n",
    "                        self.add(other_item)\n",
    "                        raise SelfStopIteration\n",
    "                    self._tree = self._tree._splay(self._tree.right.minimum())\n",
    "                    continue\n",
    "                if self._arb_gt(self._tree.payload, other_item):\n",
    "                    root = self._tree.payload\n",
    "                    self.add(other_item)\n",
    "                    self._tree = self._tree._splay(root)\n",
    "                    other_item = next(other_iter)\n",
    "                    continue\n",
    "                minimum = self._tree.left is None\n",
    "                maximum = self._tree.right is None\n",
    "                self.remove(self._tree.payload)\n",
    "                if self._tree is None or maximum:\n",
    "                    raise SelfStopIteration\n",
    "                if minimum:\n",
    "                    self._tree = self._tree._splay(self.minimum())\n",
    "                other_item = next(other_iter)\n",
    "        except SelfStopIteration:\n",
    "            while True:\n",
    "                self.add(next(other_iter))\n",
    "    except StopIteration:\n",
    "        return\n",
    "\n",
    "OrderedSet.symmetric_difference_update = symmetric_difference_update\n",
    "del symmetric_difference_update"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Als Operation haben wir `__ixor__` (`^=`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "OrderedSet.__ixor__ = OrderedSet._uncurry_inp_op(\n",
    "    OrderedSet.symmetric_difference_update)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}