Woche 07
Generics, Polymorphie, Rekursion
Generics
Bisher haben wir spezielle Klassen für jeden Datentyp neu implementiert:
1 class IntListElement { 1 class CharListElement {
2 private IntListElement next; 2 private CharListElement next;
3 private int value; 3 private char value;
4 } 4 }
Redundant, mühsam und fehleranfällig
Generics
Mit generics ermöglichen wir “variable” Datentypen:
1 public class List<T> {
2 private ListElement head;
3
4 private class ListElement {
5 private ListElement next;
6 private T value;
7 }
8 }
List erwartet einen unbekannten “Typ-Parameter”
T wird zur Kompilierzeit entschieden
Generics
Generische Typen müssen Klassen/Interfaces sein, somit müssen für primitive Datentypen
Wrapperklassen benutzt werden:
1 List<Integer> intList = new List<Integer>();
2 List<Character> charList = new List<Character>();
3 List<Message> messageList = new List<Message>();
4
5 // kürzer:
6 List<Integer> intList = new List<>();
7
8 // unparametrisiert:
9 List objList = new List(); // == List<Object>
Generics
Wir können auch festlegen, dass T gewisse Voraussetzungen erfüllen muss, d.h. von bestimmten Klassen
erbt oder Interfaces implementiert.
1 public class ClassA<T extends ClassB> {
2 private T myT;
3
4 public ClassA(T myT) {
5 [Link] = myT;
6 }
7
8 public void doSomething() {
9 [Link]();
10 }
11 }
Generics
Für statische Methoden muss man den generischen Typ in der Methodensignatur definieren:
1 public static <T> List<T> arrayToList(T[] array) {
2 List<T> list = new List<>();
3 for (T t : array) {
4 [Link](t);
5 }
6 return list;
7 }
W07P01 - Generischer Stack
Bearbeite nun die Aufgabe W07P01 - Generischer Stack
Abstrakte Klassen und
Interfaces
Interfaces
Interfaces definieren eine Menge von Funktionalitäten, die eine Klasse bereitstellen muss.
1 public interface VectorOperations<T> {
2 // alle Methoden per default public
3 void add(T other);
4 void subtract(T other);
5 double scalarProduct(T other);
6 }
Interfaces
Variablen bei Interfaces sind immer public, static und final
1 public interface Distance<T> {
2 int MIN_DISTANCE = 0; // == public static final int MIN_DISTANCE = 0;
3
4 double distanceTo(T other);
5
6 static <T extends VectorOperations<T>> double getDistance(T a, T b) {
7 T vec = [Link](b);
8 return [Link]([Link](vec));
9 }
10 }
Interfaces
Klassen können mehrere Interfaces implementieren. Hierbei müssen alle Methoden aus allen Interfaces
implementiert werden.
1 public class Vector2 implements Distance<Vector2>,
2 VectorOperations<Vector2> {
3 public Integer[] values = new Integer[2];
4
5 @Override
6 public Vector2 add(Vector2 other) { ... }
7
8 @Override
9 public Vector2 subtract(Vector2 other) { ... }
10
11 @Override
12 public double scalarProduct(Vector2 other) { ... }
13
14 @Override
15 public double distanceTo(Vector2 other) { ... }
16 }
Interfaces
Klassen können mehrere Interfaces implementieren, jedoch nur von einer Klasse erben.
1 public class ClassB extends ClassA implements Interface1, Interface2 {
2 ...
3 }
Somit müssen auch generische Typen mehrere Interfaces implementieren können. Achtung: “&”-
Operator funktioniert nur wenn ein Interface rechts davon steht.
1 public class ClassB<T extends ClassB & Interface1 & Interface2> {
2 ...
3 }
Abstrakte Klassen
Um eine Basis mit nicht nur Methoden (=> Interfaces), sondern auch Membervariablen erstellen zu
können, gibt es abstrakte Klassen:
1 public abstract class VectorBase {
2 protected Integer[] values;
3 private int dimension;
4
5 public VectorBase(Integer[] values) {
6 [Link] = values;
7 dimension = [Link];
8 }
9
10 public abstract void normalized();
11
12 public int getDimension () {
13 return dimension;
14 }
15 }
Abstrakte Klassen können, wie Interfaces, nicht instanziiert werden, können jedoch sehr wohl
Konstruktoren besitzen!
Abstrakte Klassen
Eine konkrete Implementierung von Vector Base sieht dann so aus:
1 public class Vector2 extends VectorBase implements Distance<Vector2>,
2 VectorOperations<Vector2>
3 public Vector2() {
4 super(new Integer[2]);
5 }
6 @Override
7 public void normalized() { ... }
8
9 @Override
10 public void add(Vector2 other) { ... }
11 @Override
12 public void subtract(Vector2 other) { ... }
13 @Override
14 public double scalarProduct() { ... }
15
16 @Override
17 public double distanceTo(Vector2 other) { ... }
18 }
Polymorphie
Polymorphie
1 class Animal {}
2 class Mammal extends Animal {}
3 class Dog extends Mammal {}
4
5 public class Main {
6 public static void main(String[] args) {
7 Dog dog = new Dog();
8 Animal dogAnimal = dog;
9 Animal otherAnimal = new Animal();
10 [Link](dog instanceof Dog); // true
11 [Link](dog instanceof Animal); // true
12 [Link](dogAnimal instanceof Dog); // true
13 [Link](dogAnimal instanceof Animal); // true
14 [Link](otherAnimal instanceof Animal); // true
15 [Link](otherAnimal instanceof Dog); // false
16 }
17 }
Polymorphie
1 // statischer Typ: Animal, dynamischer Typ: Dog
2 Animal animal = new Dog();
3
4 // -----
5
6 Dog dog = new Dog();
7 Mammal mammal = dog;
8 Animal animal = dog;
9
10 [Link](new Trick());
11 [Link]([Link]);
12 [Link]();
13
14 // compile-fehler, Methode nicht verfügbar
15 [Link](new Trick());
Polymorphie
Polymorphie
Polymorphie
Polymorphie
1 // Mammal extends Animal
2 // Cat extends Mammal
3 // Dog extends Mammal
4 // Cow extends Mammal
5 Animal cat = new Cat();
6 Animal dog = new Dog();
7 Animal cow = new Cow();
8
9 [Link]();
10 [Link]();
11 [Link]();
Angenommen makeSound() ist in Animal, Mammal und allen drei Unterklassen definiert. Welche wird
tatsächlich aufgerufen?
Polymorphie
Method overloading: Gleiche Methodennamen, verschiedene Parametertypen - Auswahl der Methode
hängt vom statischen Typ des Parameters ab:
1 public class Main {
2 public static void main(String[] args) {
3 Dog dog = new Dog();
4 Cat cat = new Cat();
5 Animal dogAnimal = dog;
6
7 printAnimal(dog); // Dog
8 printAnimal(cat); // Animal
9 printAnimal(dogAnimal); // Animal
10 }
11 static void printAnimal(Animal animal) {
12 [Link]("Animal");
13 }
14 static void printAnimal(Dog dog) {
15 [Link]("Dog");
16 }
17 }
Polymorphie
Casts und instanceof:
1 if (animal instanceof Dog) {
2 Dog animalAsDog = (Dog) animal;
3 [Link](new Trick());
4 }
instanceof prüft den dynamischen Typ, ohne diesen Check wirft der Cast möglicherweise eine Exception.
Polymorphie
Regeln für Casts:
1. Upcast (von Subtyp zu Supertyp) immer implizit möglich
1 Dog d = new Dog;
2 Animal a = d;
2. Downcast (von Supertyp zu Subtyp) nur explizit möglich
1 Animal a = new Dog;
2 Dog d = (Dog) a;
3. Casts zwischen nicht verwandten Typen kompilieren (auch mit Cast) nicht
1 Cat c = new Dog(); // Fehler
2 Cat c = (Cat) new Dog(); // Fehler
W07P02 - Polymorphie
Bearbeite nun die Aufgabe W07P02 - Polymorphie.
Rekursion
ist ein Divide & Conquer Ansatz zum Lösen der Probleme.
Wenn ein Problem in kleinere Teilprobleme zerlegt werden kann, die später kombiniert werden, kann
man dies rekursiv lösen.
Methodenstruktur
1 recursiveFunc() {
2 if (checkForBaseCase) { // base case
3 Solve the problem directly without recursion;
4 } else { // recursive case
5 Divide the problem into smaller subproblems of the same type;
6 Call recursiveFunc() on each subproblem;
7 Combine the results from the subproblems;
8 }
9 }
Rekursives Denken
Jede Eingabe muss durch einen Fall abgedeckt sein
Basisfall oder Rekursiver Aufruf
Es muss einen Basisfall geben, der keine rekursiven Aufrufe macht.
Der rekursive Fall muss das Problem vereinfachen und Fortschritte in Richtung des Basisfalls
machen.
W07P03 - Rekursion
Bearbeite nun die w07P03 auf Artemis.
W07P04 - Potenzmenge
Bearbeite nun die W07P04 auf Artemis.