Informatik II - Ãœbung 6

Pascal Schärli

WelcomeToMyCrib@pascscha.ch

30.10.2020

Nachbesprechung

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static List add(List list, int value) {
    return new List(value, list);
}
val  =
next =

1

val  =
next =

21

val  =
next =

4

null

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static int size(List list) {
    if (list == null) return 0;
    return size(list.next) + 1;
}
val  =
next =

1

val  =
next =

21

val  =
next =

4

null

size(list.next) + 1

size(list.next) + 1

size(list.next) + 1

0

2 + 1 = 3

1 + 1 = 2

0 + 1 = 1

[List A]

[List B]

[List C]

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static int sum(List list) {
    if (list == null) return 0;
    return list.value + sum(list.next);
}
val  =
next =

1

val  =
next =

21

val  =
next =

4

null

sum(list.next) + val

sum(list.next) + val

sum(list.next) + val

0

25 + 1 = 26

4 + 21 = 25

0 + 4 = 4

[List A]

[List B]

[List C]

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static List last(List list) {
    if (list == null) return null;
    if (list.next == null) return list;
    return last(list.next);
}
val  =
next =

1

val  =
next =

21

val  =
next =

4

null

[List A]

[List B]

[List C]

last(list.next)

last(list.next)

return list

[List C]

[List C]

[List C]

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static List sublist(List list, int index) throws IndexOutOfBoundsException {
    if (list == null || index < 0) throw new IndexOutOfBoundsException();
    if (index == 0) return list;
    return sublist(list.next, index - 1);
}

val  =
next =

1

val  =
next =

21

val  =
next =

4

null

[List A]

[List B]

[List C]

sublist(list.next, 0)

return list

[List B]

[List B]

sublist(list,1)

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static int valueAt(List list, int index) throws IndexOutOfBoundsException {
    if (list == null || index < 0) throw new IndexOutOfBoundsException();
    if (index == 0) return list.value;
    return valueAt(list.next, index - 1);
}
val  =
next =

1

val  =
next =

21

val  =
next =

4

null

[List A]

[List B]

[List C]

valueAt(list.next, 0)

return list.value

21

21

valueAt(list,1)

Pascal Schärli 30.10.2020

Einfach verkettete Liste

public static int index(List list, int value) throws NoSuchElementException {
    if (list == null) throw new NoSuchElementException();
    if (list.value == value) return 0;
    return 1 + index(list.next, value);
}
val  =
next =

1

val  =
next =

21

val  =
next =

4

null

[List A]

[List B]

[List C]

index(list,4)

1+index(list.next,4)

1+index(list.next,4)

return 0

1 + 1 = 2

1 + 0 = 1

0

Pascal Schärli 30.10.2020

Modifizierung von Listen

public static void append(List list, int value) throws IllegalArgumentException {
    if (list == null) throw new IllegalArgumentException();
    Lists.last(list).next = new List(value, null);
}

Pascal Schärli 30.10.2020

Modifizierung von Listen

public static void concat(List head, List tail) throws IllegalArgumentException {
    if (head == null) throw new IllegalArgumentException();
    Lists.last(head).next = tail;
}

Pascal Schärli 30.10.2020

Modifizierung von Listen

public static void insertAt(List list, int index, int value) throws IndexOutOfBoundsException {
    if (list == null || index < 0) throw new IndexOutOfBoundsException();
    if (index == 0) {
       list.next = new List(value, list.next);
    } else {
       insertAt(list.next, index - 1, value);
   }
}

Pascal Schärli 30.10.2020

Modifizierung von Listen

public static void insertAt(List list, int index, List newList) throws IndexOutOfBoundsException {
    if (newList == null) return;
    if (list == null || index < 0) throw new IndexOutOfBoundsException();
    if (index == 0) {
       Lists.last(newList).next = list.next;
       list.next = newList;
    } else {
        insertAt(list.next, index - 1, newList);
    }
}

Pascal Schärli 30.10.2020

Modifizierung von Listen

public static List remove(List list, int index) throws IndexOutOfBoundsException {
    if (list == null || index < 0) throw new IndexOutOfBoundsException();
    if (index == 0) return list.next;
    list.next = remove(list.next, index - 1);
    return list;
}

Pascal Schärli 30.10.2020

Sortieren von Listen

public static List insertSorted(List list, int value) {
   if (list == null){
       return new List(value, null);
   }
   else if (value < list.value){
       return new List(value, list);
   }
   else {
       list.next = insertSorted(list.next, value);
       return list;
   }
}
public static List sort(List list) {
    if (list == null){
        return null;
    }
    List nextSorted = sort(list.next);
    return insertSorted(nextSorted, list.value);
}

Pascal Schärli 30.10.2020

Vorlesung

Pascal Schärli 30.10.2020

Klassenhierarchie

  • In Java ist es möglich, dass eine Klasse von einer anderen Klasse "erbt".
     
  • Die erbende Klasse erbt somit alle Funktionen und Attribute und kann diese noch erweitern.
     
  • Dies ermöglicht es gewisse Typen und Strukturen besser zu modellieren.

Pascal Schärli 30.10.2020

Klassenhierarchie

 public class Fahrzeug{
    int radzahl;

    public Fahrzeug(int radzahl){
        this.radzahl = radzahl;
    }
 }
 public class Auto extends Fahrzeug{
    protected float hubraum;
    
    public Auto(float hubraum){
        super(4);
        this.hubraum = hubraum;
    }

    public float getHubraum(){
        return hubraum;
    }
    
    public void setHubraum(float hubraum){
        if(hubraum>0) this.hubraum = hubraum;
    }
 
 }
 public class Lastwagen extends Auto{
    float capacity;
    
    public Lastwagen(float hubraum,
                     float capacity){
        super(hubraum);
        this.capacity = capacity;
    }
 }
 public class Fahrrad extends Fahrzeug{
    
    public Fahrrad(){
        super(2);
    }
 }

Fahrzeug

Auto

Lastwagen

Fahrrad

Pascal Schärli 30.10.2020

Klassenhierarchie

Fahrzeug myFahrrad = new Fahrrad();

System.out.println(myFahrrad.radzahl);
		
myFahrrad.setHubraum(300); 

Fahrzeug myLastwagen = new Lastwagen(80000,50);

System.out.println(myLastwagen.radzahl);
		
myLastwagen.setHubraum(300); 

Output: 4
Output: 2

Compile Error:

The method setHubraum(int) is undefined for the type Fahrzeug

Compile Error:

The method setHubraum(int) is undefined for the type Fahrzeug

Fahrzeug

Auto

Lastwagen

Fahrrad

Pascal Schärli 30.10.2020

Klassenhierarchie

  • Warum können wir den Hubraum von myLastwagen nicht bestimmen, obwohl es ein Objekt vom Typ Lastwagen ist?
     
  • Beim Erstellen von myLastwagen haben wir gesagt, dass es vom Typ Fahrzeug ist:

     
  • myLastwagen hat also alle Attribute von einem Lastwagen, man kann sie einfach nicht abrufen.
     
  • \(\Rightarrow\) Type Casts
Fahrzeug myLastwagen = new Lastwagen(80000,50);
((Lastwagen)myLastwagen).setHubraum(300);

Pascal Schärli 30.10.2020

Type Casts

Fahrzeug myLastwagen = new Lastwagen(80000,50);

System.out.println(myLastwagen.radzahl);
        
((Lastwagen)myLastwagen).setHubraum(300); 

Fahrzeug myFahrrad = new Fahrrad();

System.out.println(myFahrrad.radzahl);
		
((Lastwagen)myFahrrad).setHubraum(300);

Runtime Error:

Exception in thread "main" java.lang.ClassCastException: Fahrzeug cannot be cast to Lastwagen

Fahrzeug

Auto

Lastwagen

Fahrrad

Pascal Schärli 30.10.2020

Zusammenfassung

  1. Falls ihr auf ein Attribut zugreifen möchtet, welches nicht existiert oder nicht abrufbar ist, gibt es einen Compile Error


     
  2. Falls ihr einen Cast machen wollt, welcher nicht funktioniert, gibt es einen Runtimer Error 
Fahrzeug myLastwagen = new Lastwagen(80000, 50);

myLastwagen.setHubraum(300);
Fahrzeug myFahrrad = new Fahrrad();

((Lastwagen)myFahrrad).setHubraum(300);

Fahrzeug

Auto

Lastwagen

Fahrrad

Pascal Schärli 30.10.2020

Beispiele

class Mensch { ... }
class ETHStudent extends Student { String legiNr; }
class ITETStudent extends ETHStudent { ... }
class Student extends Mensch { ... }
Student tim = new ETHStudent();
Objekt obj           = tim;
Mensch mensch        = tim;
Student student      = tim;
ETHStudent ethStud   = (ETHStudent) tim;
ITETStudent itetStud = (ITETStudent) tim;

Java denkt es ist ein Student

Wir wissen, es ist ein ETHStudent

ohne cast

mit cast

Runtime Error

zuweisung möglich ohne Cast

zuweisung möglich ohne Cast

zuweisung möglich mit Cast

Runtime Error

jede Java Klasse erbt von Object

Pascal Schärli 30.10.2020

Beispiele

class Mensch { ... }
class ETHStudent extends Student { String legiNr; }
class ITETStudent extends ETHStudent { ... }
class Student extends Mensch { ... }
ITETStudent tim = new ITETStudent();
Mensch mensch        = tim;
Student student      = tim;
ETHStudent ethStud   = tim;
ITETStudent itetStud = tim;

System.out.println(mensch.legiNr);
System.out.println(student.legiNr);
System.out.println(ethStud.legiNr);
System.out.println(itetStud.legiNr);

Compile Error

Compile Error

Kein Compile Error

Kein Compile Error

haben legiNr

Pascal Schärli 30.10.2020

Compile Error

instanceof

  • Falsche Type-Casts können zu Runtime-Error führen.
  • Wie können wir das verhindern?
  • instanceof Operator gibt zurück, ob ein Objekt gecasted werden kann.
Student tim = new ETHStudent();

System.out.println(tim instanceof Mensch);
System.out.println(tim instanceof Student);
System.out.println(tim instanceof ETHStudent);
System.out.println(tim instanceof ITETStudent);

true
true
true
false

Output:

Pascal Schärli 30.10.2020

Abstrakte Klassen

  • Manchmal macht es Sinn für bestimmte Klassen bloss zu definieren was sie können muss und noch nicht wie sie implementiert wird.
     
  • Beispiel: Stacks
    • Jeder Stack hat bestimmte Funktionen (pop / peek / push)
    • Es gibt aber verschiedene möglichkeiten einen Stack zu implementieren (LinkedList, Array, ...)
  • Zwei Arten:
    • abstract
    • interface

Pascal Schärli 30.10.2020

Abstrakte Klassen - abstract

  • In einer Abstrakten Klasse kann man Methoden implementieren, aber auch nur deklarieren.
     
  • Man kann keine Abstrakten Objekte instanzieren (weil man sonst unimplementierte Methoden aufrufen könnte)
public abstract class AbstractStack {
    // declare abstract functions
    public abstract int push();
    public abstract int pop();
    public abstract int peek();
    public abstract int size();
    
    // already implement some functions
    public boolean isEmpty(){
    	return size() == 0;
    }
}
public class Stack extends AbstractStack {
    // declare abstract functions
    public int push(){/*TODO*/}
    public int pop(){/*TODO*/}
    public int peek(){/*TODO*/}
    public int size(){/*TODO*/}
}

Pascal Schärli 30.10.2020

Abstrakte Klassen - interface

  • Interfaces funktionieren gleich wie abstrakte Klassen
     
  • Ein Interface ist eine Schnittstelle zwischen Benutzung un
     
  • Man darf keine Funktionen mehr implementieren, nur noch deklarieren
     
  • Vorteil: Eine Klasse kann mehrere Interfaces implementieren, aber nur von einer Klassen erben (extends)

Pascal Schärli 30.10.2020

public class C implements I1,I1 extends A{
	// [...]
}

Factories

  • Julia und Carina arbeiten mit Bäumen.
  • Um gleichzeitig daran zu arbeiten implementiert Carina den Baum und Julia schreibt das Programm.
  • Sie entscheiden sich: Sie verwenden einen ArrayTree
  • Nach der Hälfte der Zeit merkt Carina, dass ein ListTree besser geeignet wäre.
  • Carina sagt Julia, sie solle doch schnell alle Verwendungen von ArrayTree zu ListTree ändern.

Carina

Julia

Benutze ArrayTree

Meinung geändert, benutze ListTree

Pascal Schärli 30.10.2020

Factories

  • Um solche Katastrophen zu verhindern benutzen wir Interfaces und Factories
  • Julia benutzt eine "TreeFactory" um Bäume zu erstellen, welche dieses Interface implementieren.
interface Tree{
    public Tree leftChild();
    public Tree rightChild();
    public int getValue();
    public int setValue();    
}
public class TreeFactory {
    public static Tree makeTree(){
        return new ListTree();
    }
}

Tree Interface

Tree Factory

public class FancyCode {
	public Tree important(){
        Tree myRoot = new ArrayTree();
        myRoot.setValue(4);
        return myRoot;
    }
}

Julias Code Vorher

Pascal Schärli 30.10.2020

public class FancyCode {
	public Tree important(){
        Tree myRoot = TreeFactory.makeTree();
        myRoot.setValue(4);
        return myRoot;
    }
}

Julias Code Jetzt

Pascal Schärli 30.10.2020

Pascal Schärli 30.10.2020

Ist die Zuweisung Schoggi lindt = (Schoggi)chopfab; möglich?

Die Antwort ist wie auch schon während der Übungsstunde gesagt nein, es gibt aber einen Compile-Error und nicht einen Runtime-Error. Java weiss, dass chopfab ein Bier ist und somit auf einem anderen "Ast" als Schoggi, somit kann es bereits beim kompilieren wissen, dass es niemals möglich wäre das zu einer Schoggi zu casten und es gibt daher schon beim Kompilieren einen Fehler.

Fehler bei meiner Kahoot Lösung

Pascal Schärli 30.10.2020

Fehler bei meiner Kahoot Lösung

Bier b1 = new Bier();
Preis b2 = new Bier();
Preis p = new Preis();
Preis s1 = new Schoggi();
Schoggi s2 = new Schoggi();

Schoggi mySchoggi1 = (Schoggi)b1; // Compile error
Schoggi mySchoggi2 = (Schoggi)b2; // Runtime error, da Java nicht weiss, dass es ein Bier ist
Schoggi mySchoggi3 = (Schoggi)p;  // Runtime error
Schoggi mySchoggi4 = (Schoggi)s1; // Funktioniert
Schoggi mySchoggi5 = (Schoggi)s;  // Funktioniert, cast wäre nicht nötig

Vorbesprechung

Pascal Schärli 30.10.2020

Klassen, Schnittstellen und Typumwandlungen

interface A { }
abstract class B implements A { }
interface C extends A { }
class D extends B implements C { }
class E extends B { }
class F implements C { }

Ihr habt die folgende Klassenhierarchie gegeben:

  1. Zeichnet die Abhängigkeiten in einem Graph auf
  2. Welche Typen kann man mit new instanzieren?
  3. Ganz viele Cast-/Instanzierungsbeispiele, analog zu hier:

Link

Pascal Schärli 30.10.2020

Schnittstellen und Implementierungen

  1. Vervollständigt die Fabrikmethode, gebt einen ListStack zurück:



     
  2. Ergänzt das Interface IStack, so dass es noch eine empty() Funktion hat (Inklusive Java-Doc)
     
  3. Implementiert diese Funktion in der ListStack Klasse
     
  4. Schreibt einen Public Test um die Funktion zu testen
public class StackFactory {
    public static IStack create() {
        // TODO
        return null;
    }
}

Pascal Schärli 30.10.2020

Polymorphie

  • Erstellt das FIle ListUtils.java und implementiert dort die Klasse ListUtils, welche die Funktionen vom Interface IListUtils implementiert. (Musterlösung U5A3)
  • Erstellt die Fabrikmethode in ListUtilsFactory.java
  • Implementiert die Funktion area in den Files Rectangle.java sowie Triangle.java
  • Implementiert die Funktion smallerThan im File GeometricObject.java, welches prüft ob die eigene Fläche kleiner ist als die vom Ãœbergabeargument
  • Implementiert die Funktion sort im File ListUtils.java (Musterlösung U5A3)

Pascal Schärli 30.10.2020

Stacks und Optimierungen

  • Für "fortgeschrittene" - Ihr seid alle genug fortgeschritten ;)

  • Kreiert die Klasse ChunkedStack im File "ChunkedStack.java".

  • Stack, welcher als Mischung vom ListStack und ArrayStack ist:
    Array →  Array → Array → null

  • Was ist schneller – ChunkedStack oder ListStack?
    Wie wächst der Aufwand für size in Abhängigkeit der Listengrösse?

  • Kann man size auch besser implementieren?

Pascal Schärli 30.10.2020

Viel Spass!

Pascal Schärli 30.10.2020