10_theorie.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "02395950",
   "metadata": {},
   "source": [
    "# Sichtbarkeitsmodifikatoren und Generische Programmierung\n",
    "\n",
    "#### Patrick Schnider, Marcel Lüthi</br>Departement Mathematik und Informatik, Universität Basel"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e814204c",
   "metadata": {},
   "source": [
    "In diesem Arbeitsblatt schauen wir uns folgendes an:\n",
    "\n",
    "1. Wir arbeiten mit unserer Listenklasse weiter. Dabei setzen wir passende Zugriffsmodifikatoren und diskutieren, warum wir gewisse Teile vom Code vor Zugriff schützen wollen.\n",
    "2. Wir diskutieren eine Limitierung unserer Listenklasse und verwenden die Typenhierarchie um diese zu mindern.\n",
    "3. Danach führen wir Generics anhand eines Tuples ein, das Thema für das kommende Selbststudium."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea85a956",
   "metadata": {},
   "source": [
    "### Teil 1: Zugriffsmodifikatoren"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa8f3923",
   "metadata": {},
   "source": [
    "##### Übung\n",
    "\n",
    "* Sie finden nachstehend den vollständigen Code für unsere LinkedList Implementation. Setzten Sie vor Jedes Interface, jede Klasse und jede Methode ein passendes Sichtbarkeitsattribut (oder lassen Sie es weg, falls die default-Sichtbarkeit die richtige Wahl ist). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e560019",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "interface List {\n",
    "    \n",
    "    /**\n",
    "      * Appends an element to the end of the list\n",
    "      */\n",
    "    void add(double element);\n",
    "    \n",
    "    /**\n",
    "      * returns the number of elements in the list\n",
    "      */\n",
    "    int size();\n",
    "    \n",
    "    /**\n",
    "      * gets the element at position i\n",
    "      */\n",
    "    double get(int index);\n",
    "    \n",
    "    /**\n",
    "      * sets the element at position i\n",
    "      */\n",
    "    void set(int index, double element);\n",
    "    \n",
    "    /**\n",
    "      * Returns an array representation of the given list;\n",
    "      */\n",
    "    double[] toArray();\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "466ac4e4",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class Node {\n",
    "    double value;\n",
    "    Node next;\n",
    "    \n",
    "    Node(double value) {\n",
    "        this.value = value;\n",
    "        this.next = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8dcbd621",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class LinkedList implements List {\n",
    "    \n",
    "    Node first;\n",
    "    Node last;\n",
    "    \n",
    "    int size;\n",
    "    \n",
    "    // Erzeugt eine ArrayList mit gegebener Kapazität\n",
    "    LinkedList() {\n",
    "        this.first = null;\n",
    "        this.last = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    \n",
    "    // Fügt ein neues Element am Ende der Liste an. \n",
    "    void add(double element) {\n",
    "        Node newNode = new Node(element);\n",
    "        if (first == null) {\n",
    "            first = newNode;\n",
    "            last = newNode;\n",
    "        } else {\n",
    "            last.next = newNode;\n",
    "            last = newNode;\n",
    "        }        \n",
    "        size = size + 1;\n",
    "    }\n",
    "    \n",
    "    int size() { \n",
    "        return size;\n",
    "    }\n",
    "    \n",
    "\n",
    "    \n",
    "    double[] toArray() {\n",
    "        double[] array = new double[size];\n",
    "        \n",
    "        Node current = first;\n",
    "        for (int i = 0; i < size; i = i + 1) {\n",
    "            array[i] = current.value;\n",
    "            current = current.next;\n",
    "        }\n",
    "        \n",
    "        return array;\n",
    "    }\n",
    "\n",
    "    double get(int index) {\n",
    "        Node curr = first;\n",
    "        for (int i = 0; i < index; i = i + 1) {\n",
    "            curr = curr.next;\n",
    "        }\n",
    "        return curr.value;\n",
    "        \n",
    "    }\n",
    "\n",
    "    void set(int index, double element) {\n",
    "        Node curr = first;\n",
    "        for (int i = 0; i < index; i = i + 1) {\n",
    "            curr = curr.next;\n",
    "        }\n",
    "        curr.value = element;\n",
    "        \n",
    "    }\n",
    "\n",
    "    \n",
    "        \n",
    "    // Gibt die Liste aus\n",
    "    @Override\n",
    "    String toString() { \n",
    "        if (first == null) {\n",
    "            return \"[]\";\n",
    "        } else {\n",
    "            StringBuffer sb = new StringBuffer();\n",
    "            sb.append(\"[\");\n",
    "            for (Node current = first; current != last; current = current.next) {\n",
    "                sb.append(current.value);\n",
    "                sb.append(\",\");\n",
    "            }\n",
    "            sb.append(last.value);\n",
    "            sb.append(\"]\");\n",
    "            return sb.toString();\n",
    "        }\n",
    "    }\n",
    "\n",
    "\n",
    "    @Override\n",
    "    boolean equals(Object other) {\n",
    "        if (!(other instanceof LinkedList)) {\n",
    "            return false;\n",
    "        }\n",
    "        LinkedList otherLL = (LinkedList) other;\n",
    "        \n",
    "        if (otherLL.size() != this.size()) { \n",
    "            return false;\n",
    "        }\n",
    "\n",
    "        \n",
    "        Node currThis = first;\n",
    "        Node currOther = otherLL.first;\n",
    "\n",
    "        while (currThis != null) {\n",
    "            if (currThis.value != currOther.value) {\n",
    "                return false;\n",
    "            }\n",
    "            currThis = currThis.next;\n",
    "            currOther = currOther.next;\n",
    "        }\n",
    "        return true;\n",
    "        \n",
    "    }\n",
    "    \n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ed280f9",
   "metadata": {},
   "source": [
    "Wir testen unsere Implementation, indem wir die bereits implementierten Funktionen `ListTools.addNumbersInRange` und `ListTools.computeAverageValue` nutzen. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b04a9f86",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class ListTools {\n",
    "\n",
    "    static void addNumbersInRange(List l, double from, double to, int size) {\n",
    "        double dist = (to - from) / size;\n",
    "        for (int i = 0; i <= size; i = i + 1) {\n",
    "            double current = from + i * dist;\n",
    "            l.add(current);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    static double computeAverageValue(List numbers) {\n",
    "        double sum = 0.0;\n",
    "        for (int i = 0; i < numbers.size(); i = i + 1) {\n",
    "            sum += numbers.get(i);\n",
    "        }\n",
    "        return sum / numbers.size();\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "236a876c",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class LinkedListTest {\n",
    "    \n",
    "    static void main(String[] args) {\n",
    "        LinkedList list = new LinkedList();\n",
    "        ListTools.addNumbersInRange(list, 0, 10, 20);\n",
    "        System.out.println(list);\n",
    "        System.out.println(\"average \" + ListTools.computeAverageValue(list));\n",
    "        \n",
    "        // Das Folgende funktioniert nur, wenn die entsprechenden Sichtbarkeitsattribute in der Klasse Node aud public gesetzt werden.\n",
    "        Node start = new Node(17);\n",
    "        start.next = list.first;\n",
    "        list.first = start;\n",
    "        System.out.println(list);\n",
    "    }    \n",
    "}\n",
    "\n",
    "LinkedListTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23045d30-dadf-4323-be3e-ef77f2af9c48",
   "metadata": {},
   "source": [
    "### Ein (konstruiertes) Beispiel\n",
    "\n",
    "Nehmen Sie an, wir möchten eine natürliche Zahl $x$ schreiben als $2^ky$, wobei $y$ ungerade sein soll. Wir können dafür ein Objekt erzeugen, das die Werte $k$ und $y$ enthält. Der Kostruktor des Objekts soll hierbei eine beliebige natürliche Zahl ins korrekte Format umwandeln.\n",
    "\n",
    "#### Miniübung\n",
    "\n",
    "Implementieren Sie die Methode ```convert```. Welches Sichtbarkeitsattribut wählen Sie dafür?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a4cae470-3ed9-45ab-a9f3-26b6f7508e27",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class EvenParts {\n",
    "\n",
    "    int k;\n",
    "    int y;\n",
    "    \n",
    "    public EvenParts(int n) {\n",
    "        int[] ky = convert(n);\n",
    "        this.k = ky[0];\n",
    "        this.y = ky[1];\n",
    "    }\n",
    "    \n",
    "    // Implementation missing\n",
    "\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a225996-aab0-4c5a-ac15-7afbfa55b80d",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class EvenPartsTest {\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        EvenParts a = new EvenParts(20);\n",
    "        EvenParts b = new EvenParts(16);\n",
    "        System.out.println(\"(\" + a.k + \",\" + a.y + \") and (\" + b.k + \",\" + b.y + \")\");\n",
    "    }\n",
    "\n",
    "}\n",
    "\n",
    "EvenPartsTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a79d023f",
   "metadata": {},
   "source": [
    "### Teil 2: Eine flexiblere Listenklasse"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbe16e5c",
   "metadata": {},
   "source": [
    "#### Diskussion\n",
    "\n",
    "In obiger Implementation können wir in der Liste nur Elemente vom Typ `double` nutzen.\n",
    "\n",
    "Wie gehen wir vor, wenn wir nun auch eine Liste mit Elementen vom Typ `String` möchten?\n",
    "\n",
    "Kennen Sie eine bessere Methode als den Code zu kopieren und anzupassen?</br>\n",
    "(Hinweis: Alle Klassen in Java sind hierarchisch angeordnet)?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0dc504a0",
   "metadata": {},
   "source": [
    "#### Mögliche Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fbc8484b",
   "metadata": {},
   "source": [
    "Eine mögliche Implementation nutzt die Java Klassenhierarchie aus. Wir ersetzen einfach den konkreten Typ `double` mit `Object`.\n",
    "\n",
    "(Wir nutzen in diesem Beispiel eine Implementierung unserer Liste mit eingeschränkter Funktionalität.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4eda6bb6",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "public interface List {\n",
    "    \n",
    "    /**\n",
    "      * Appends an element to the end of the list\n",
    "      */\n",
    "    public void add(Object element);\n",
    "    \n",
    "    /**\n",
    "      * returns the number of elements in the list\n",
    "      */\n",
    "    public int size();\n",
    "    \n",
    "    /**\n",
    "      * gets the element at position i\n",
    "      */\n",
    "    public Object get(int index);    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d877b145",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class Node {\n",
    "    Object value;\n",
    "    Node next;\n",
    "    \n",
    "    Node(Object value) {\n",
    "        this.value = value;\n",
    "        this.next = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f3b2204b",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "public class LinkedList implements List {\n",
    "    \n",
    "    private Node first;\n",
    "    private Node last;\n",
    "    \n",
    "    private int size;\n",
    "    \n",
    "    // Erzeugt eine ArrayList mit gegebener Kapazität\n",
    "    public LinkedList() {\n",
    "        this.first = null;\n",
    "        this.last = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    \n",
    "    // Fügt ein neues Element am Ende der Liste an. \n",
    "    public void add(Object element) {\n",
    "        Node newNode = new Node(element);\n",
    "        if (first == null) {\n",
    "            first = newNode;\n",
    "            last = newNode;\n",
    "        } else {\n",
    "            last.next = newNode;\n",
    "            last = newNode;\n",
    "        }        \n",
    "        size = size + 1;\n",
    "    }\n",
    "    \n",
    "    public int size() { \n",
    "        return size;\n",
    "    }\n",
    "    \n",
    "\n",
    "\n",
    "    public Object get(int index) {\n",
    "        Node curr = first;\n",
    "        for (int i = 0; i < index; i = i + 1) {\n",
    "            curr = curr.next;\n",
    "        }\n",
    "        return curr.value;\n",
    "        \n",
    "    }\n",
    "   \n",
    "        \n",
    "    // Gibt die Liste aus\n",
    "    @Override\n",
    "    public String toString() { \n",
    "        if (first == null) {\n",
    "            return \"[]\";\n",
    "        } else {\n",
    "            StringBuffer sb = new StringBuffer();\n",
    "            sb.append(\"[\");\n",
    "            for (Node current = first; current != last; current = current.next) {\n",
    "                sb.append(current.value);\n",
    "                sb.append(\",\");\n",
    "            }\n",
    "            sb.append(last.value);\n",
    "            sb.append(\"]\");\n",
    "            return sb.toString();\n",
    "        }\n",
    "    }\n",
    "        \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ce6beddc",
   "metadata": {
    "scrolled": true,
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class ListTest {\n",
    "    public static void main(String[] args) {\n",
    "        LinkedList l = new LinkedList();\n",
    "        l.add(5);\n",
    "        l.add(10);\n",
    "        System.out.println(l);\n",
    "\n",
    "    \n",
    "        //int i = l.get(0);\n",
    "        //System.out.println(i);\n",
    "\n",
    "        //l.add(\"foobar\");\n",
    "        //System.out.println(l);\n",
    "    }\n",
    "}\n",
    "\n",
    "ListTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81617c73",
   "metadata": {},
   "source": [
    "#### Diskussion:\n",
    "\n",
    "* Welche Nachteile hat diese Implementation?\n",
    "* Können Sie mit dieser Implementation auch Elemente von unterschiedlichem Typ speichern?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9dcf53c8",
   "metadata": {},
   "source": [
    "### Teil 3: Generics"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75933d91",
   "metadata": {},
   "source": [
    "Generics sind ein Sprachkonstrukt, mit welchem wir die obigen Probleme lösen können. Wir können die genaue Typen definieren, die vom Compiler zur Kompilationszeit geprüft werden können, ohne, dass wir Code duplizieren müssen. Die Idee ist, dass wir Typparameter einführen, die Typen parametrisieren. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de4418aa",
   "metadata": {},
   "source": [
    "Zur Illustration dieses Konzepts definieren wir uns eine Klasse Tupel, die zwei Elemente von fixem, aber flexibel wählbarem Typ repräsentiert. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8de2ae61",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class Tuple<T, S> {\n",
    "    private T first;\n",
    "    private S second;\n",
    "    \n",
    "    // Implementation missing\n",
    "    \n",
    "    @Override \n",
    "    public String toString() { \n",
    "        return \"(\" +first + \",\" + second+ \")\";\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "038d49e5",
   "metadata": {},
   "source": [
    "Wir können dieses wie folgt anwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "19e2dc95",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class TupleTest {\n",
    "    public static void main(String[] args) {\n",
    "        // Implementation missing\n",
    "\n",
    "    }\n",
    "}\n",
    "TupleTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27b1a69f",
   "metadata": {},
   "source": [
    "### Aufgaben\n",
    "\n",
    "* Können Sie einen Wert vom Typ `Tuple<Integer, Integer>` einer Variable vom Typ `Tuple<String, String>` zuweisen?\n",
    "* Was passiert, wenn Sie beim Konstruieren der Klasse einen Wert vom falschen Typ übergeben?\n",
    "* Können Sie auch Tuple vom primitiven Typ `int` erzeugen?\n",
    "* Schauen Sie sich die [API Dokumentation](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedList.html) der Klasse `LinkedList` an. Nutzt diese Typparameter? \n",
    "\n",
    "### Zusätzliche Aufgaben\n",
    "\n",
    "* Passen Sie den nachstehenden Code für das Interface `List` und die Klasse `LinkedList` (inklusive `Node`) so an, dass diese einen Typparameter `E` nutzt, der den Typ der Elemente repräsentiert.\n",
    "* Können Sie mit dieser Implementation in derselben Liste Elemente von unterschiedlichem Typ speichern?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51ffa36f",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "public interface List {\n",
    "    \n",
    "    /**\n",
    "      * Appends an element to the end of the list\n",
    "      */\n",
    "    public void add(Object element);\n",
    "    \n",
    "    /**\n",
    "      * returns the number of elements in the list\n",
    "      */\n",
    "    public int size();\n",
    "    \n",
    "    /**\n",
    "      * gets the element at position i\n",
    "      */\n",
    "    public Object get(int index);    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8df3594f",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class Node {\n",
    "    Object value;\n",
    "    Node next;\n",
    "    \n",
    "    Node(Object value) {\n",
    "        this.value = value;\n",
    "        this.next = null;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5c3c0980",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "public class LinkedList implements List {\n",
    "    \n",
    "    private Node first;\n",
    "    private Node last;\n",
    "    \n",
    "    private int size;\n",
    "    \n",
    "    // Erzeugt eine ArrayList mit gegebener Kapazität\n",
    "    public LinkedList() {\n",
    "        this.first = null;\n",
    "        this.last = null;\n",
    "        this.size = 0;\n",
    "    }\n",
    "    \n",
    "    \n",
    "    // Fügt ein neues Element am Ende der Liste an. \n",
    "    public void add(Object element) {\n",
    "        Node newNode = new Node(element);\n",
    "        if (first == null) {\n",
    "            first = newNode;\n",
    "            last = newNode;\n",
    "        } else {\n",
    "            last.next = newNode;\n",
    "            last = newNode;\n",
    "        }        \n",
    "        size = size + 1;\n",
    "    }\n",
    "    \n",
    "    public int size() { \n",
    "        return size;\n",
    "    }\n",
    "    \n",
    "\n",
    "\n",
    "    public Object get(int index) {\n",
    "        Node curr = first;\n",
    "        for (int i = 0; i < index; i = i + 1) {\n",
    "            curr = curr.next;\n",
    "        }\n",
    "        return curr.value;\n",
    "        \n",
    "    }\n",
    "   \n",
    "        \n",
    "    // Gibt die Liste aus\n",
    "    @Override\n",
    "    public String toString() { \n",
    "        if (first == null) {\n",
    "            return \"[]\";\n",
    "        } else {\n",
    "            StringBuffer sb = new StringBuffer();\n",
    "            sb.append(\"[\");\n",
    "            for (Node current = first; current != last; current = current.next) {\n",
    "                sb.append(current.value);\n",
    "                sb.append(\",\");\n",
    "            }\n",
    "            sb.append(last.value);\n",
    "            sb.append(\"]\");\n",
    "            return sb.toString();\n",
    "        }\n",
    "    }\n",
    "        \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2a6bfdc",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": [
    "class ListTest {\n",
    "    public static void main(String[] args) {\n",
    "        LinkedList<Integer> l = new LinkedList<Integer>();\n",
    "        l.add(new Integer(5));\n",
    "        l.add(new Integer(10));\n",
    "        System.out.println(l);\n",
    "    }\n",
    "}\n",
    "\n",
    "ListTest.main(new String[0]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d7f364dc",
   "metadata": {
    "vscode": {
     "languageId": "java"
    }
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java [conda env:ijava]",
   "language": "java",
   "name": "conda-env-ijava-java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "17.0.3-internal+0-adhoc..src"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}