5.2 Generics

Vooraleer we de discussie over datastructuren kunnen starten, is het nuttig om eerst te kijken naar generics, aangezien generics veelvuldig gebruikt worden in datastructuren.

Je vindt alle startcode voor dit hoofdstuk op deze GitHub-repository.

Wat en waarom?

Generics zijn een manier om klassen en methodes te voorzien van type-parameters. Bijvoorbeeld, neem de volgende klasse ArrayList¹:

class ArrayList {
  private Object[] elements;
  public void add(Object element) { /* ... */  }
  public Object get(int index) { /* ... */  }
}

Stel dat we deze klasse makkelijk willen kunnen herbruiken. Dan moeten we ze algemeen houden, en kunnen we nu nog niet zeggen wat het type is van de elementen van de lijst. Gaan er Student-objecten in de lijst terechtkomen? Of Animal-objecten? Dat weten we nog niet. We kiezen daarom voor Object, het meest algemene type in Java.

Maar dat betekent ook dat je nu objecten van verschillende, niet-gerelateerde types kan opnemen in dezelfde lijst, hoewel dat niet de bedoeling is. Stel bijvoorbeeld dat je een lijst van studenten wil bijhouden, dan houdt de compiler je niet tegen om ook andere types van objecten toe te voegen:

ArrayList students = new ArrayList();

Student student = new Student();
students.add(student);

Animal animal = new Animal();
students.add(animal); // <-- compiler vindt dit OK

Om dat tegen te gaan, zou je afzonderlijke klassen ArrayListOfStudents, ArrayListOfAnimals, … kunnen schrijven waar het bedoelde type van elementen wel duidelijk is, en ook afgedwongen wordt door de compiler. Bijvoorbeeld:

class ArrayListOfStudents {
  private Student[] elements;
  public void add(Student element) { /* ... */  }
  public Student get(int index) { /* ... */  }
}

class ArrayListOfAnimals {
  private Animal[] elements;
  public void add(Animal element) { /* ... */  }
  public Animal get(int index) { /* ... */  }
}

Met deze implementaties is het probleem hierboven opgelost:

ArrayListOfStudents students = new ArrayListOfStudents();
students.add(student); // OK
students.add(animal);  // compiler error

De prijs die we hiervoor betalen is echter dat we nu veel quasi-identieke implementaties moeten maken, die enkel verschillen in het type van de elementen. Dat leidt tot veel onnodige en ongewenste code-duplicatie.

Een generische klasse definiëren

Met generics kan je een type gebruiken als parameter voor een klasse om deze code-duplicatie vermijden. Met andere woorden, je kan een generische klasse ook zien als een soort functie (soms een type constructor genoemd) die een een nieuw type (een nieuwe klasse) maakt, gebaseerd op één of meerdere gegeven types.

Generics geven je dus een combinatie van beide opties: er moet slechts 1 implementatie gemaakt worden (zoals bij ArrayList hierboven), en deze implementatie kan gebruikt worden om lijsten met een specifiek element-type te maken (zoals bij ArrayListOfStudents).

De type-parameter staat tussen < en >, en je kan deze type-parameter vervolgens gebruiken in heel de klasse. Bijvoorbeeld, volgende klasse is een nieuwe versie van de ArrayList-klasse van hierboven, maar nu met type-parameter E. De type-parameter wordt vervolgens gebruikt als type van de elements-array, de parameter van de add-method, en het resultaat-type van de get-method:

class ArrayList<E> {
  private E[] elements;
  public void add(E element) { /* ... */  }
  public E get(int index) { /* ... */  }
}

Je zal heel vaak zien dat generische type-parameters slechts bestaan uit 1 letter (bijvoorbeeld E, T, of U). Dat is geen vereiste: onderstaande code mag ook, en is volledig equivalent aan die van hierboven. De reden waarom vaak met individuele letters gewerkt wordt, is om duidelijk te maken dat het over een type-parameter gaat, en niet over een bestaande klasse.

class ArrayList<Element> {
  private Element[] elements;
  public void add(Element element) { /* ... */ }
  public Element get(int index) { /* ... */ }
}

Een generische klasse gebruiken

Bij het gebruik van een generische klasse (bijvoorbeeld ArrayList<E> van hierboven) moet je een concreet type opgeven voor de type-parameter (E). Bijvoorbeeld, als je een lijst met enkel studenten wil, gebruik je ArrayList<Student>. Je kan dan de klasse gebruiken op dezelfde manier als de ArrayListOfStudents klasse van hierboven:

ArrayList<Student> students = new ArrayList<Student>();
Student someStudent = new Student();
students.add(someStudent);
// students.add(animal); // <-- niet toegelaten (compiler error)
Student firstStudent = students.get(0);

Merk op hoe de compiler afdwingt en garandeert dat er enkel Student-objecten in terecht kunnen komen.

Om wat typwerk te besparen, laat Java in veel gevallen ook toe om het type weg te laten bij het instantiëren, met behulp van <>. Dat type is immers al bepaald door het type van de variabele:

ArrayList<Student> students = new ArrayList<>(); // <- je hoeft geen tweede keer <Student> te typen

Meerdere type-parameters

De ArrayList-klasse hierboven had één generische parameter (E). Een klasse kan ook meerdere type-parameters hebben, bijvoorbeeld een tuple van 3 elementen van mogelijk verschillend type:

class Tuple3<T1, T2, T3> {
  private T1 first;
  private T2 second;
  private T3 third;
  public T1 getFirst() { return first; }
  /* ... */
}

Bij het aanmaken moet je dan voor elke parameter een type opgeven:

Tuple3<String, Integer, Student> tuple = new Tuple3<>("John", 23, student);

Generische parameters begrenzen (bounds)

Een type-parameter <E> zoals we die tot nu toe gezien hebben kan om het even welk type voorstellen. Soms willen we dat niet, en willen we beperkingen opleggen. Stel bijvoorbeeld dat we volgende klasse-hierarchie hebben:

abstract class Animal {
  /* ... */
  abstract void showLike();
}
class Cat extends Animal {
  /* ... */
  void showLike() { System.out.println("Purring"); }
}
class Dog extends Animal {
  /* ... */
  void showLike() { System.out.println("Wagging tail"); }
}

graph BT
Cat --> Animal
Dog --> Animal

We maken nu een generische klasse Food, geparametriseerd met het type dier (T) dat dat voedsel eet:

class Food<T> {
  public void giveTo(T animal) {
    /* ... */
    animal.showLike(); // <= compiler error :(
  }
}

Food<Cat> catFood = new Food<>();       // OK
Food<String> stringFood = new Food<>(); // ook OK? :(

Deze klasse is enkel bedoeld om met (subklassen van) Animal gebruikt te worden. Maar het is ook mogelijk om een Food<String> te maken. Verder zal de compiler ook weigeren om in de methode giveTo een Animal-specifieke methode op te roepen (bv. showLike), omdat de parameter animal type T heeft, en dat kan eender wat zijn.

We kunnen aangeven dat type T een subtype moet zijn van Animal via <T extends Animal>. Je zal dan niet langer Food<String> mogen schrijven, aangezien String geen subklasse is van Animal. We begrenzen dus de mogelijke types die gebruikt kunnen worden voor de type-parameter T.

class Food<T extends Animal> {
  public void giveTo(T animal) {
    /* ... */
    animal.showLike(); // <= OK!
  }
}

Food<Cat> catFood = new Food<>();       // nog steeds OK
Food<String> stringFood = new Food<>(); // <-- compiler error

Generische methodes

Hierboven hebben we steeds een hele klasse generisch gemaakt. In sommige gevallen kan het ook nuttig zijn om een generische methode te definiëren. Dat kan ook in een klasse die zelf geen type-parameters heeft:

class AnimalHelper {
  public static <T extends Animal> ArrayList<T> findHappyAnimals(ArrayList<T> animals) { /* ... */ }
}

ArrayList<Cat> cats = new ArrayList<>();
/* ... */
ArrayList<Cat> happyCats = AnimalHelper.findHappyAnimals(cats);

Merk op hoe we, door het type T te gebruiken in zowel de parameter als het terugkeertype, kunnen garanderen dat de teruggegeven lijst precies hetzelfde type elementen heeft als de parameter, zonder dat we in de methode findHappyAnimals moeten weten welk type dier dat precies is.

Op dezelfde manier kan je ook het type van meerdere parameters (en eventueel het terugkeertype) aan elkaar verbinden. In het voorbeeld hieronder zie je een methode die paren kan maken tussen dieren; de methode kan gebruikt worden voor elk type dier, maar maakt enkel paren van dezelfde soort. Je ziet meteen ook een voorbeeld van een generisch record-type AnimalPair.

class AnimalHelper {
  public record AnimalPair<T extends Animal>(T male, T female) {} // <= voorbeeld van een generisch record
  public static <T extends Animal> ArrayList<AnimalPair<T>> makePairs(ArrayList<T> males, ArrayList<T> females) { /* ... */ }
}

ArrayList<Cat> maleCats = ...
ArrayList<Cat> femaleCats = ...
ArrayList<Dog> femaleDogs = ...
ArrayList<AnimalPair<Cat>> pairedCats = makePairs(maleCats, femaleCats); // OK

ArrayList<AnimalPair<Animal>> pairedMix = makePairs(maleCats, femaleDogs); // niet OK (compiler error)

Als het type T niet van belang is, omdat het niet terugkomt in het terugkeertype van de methode of een andere parameter, heb je geen genersiche methode nodig. Je kan dan ook gewoon het wildcard-type ? extends X gebruiken, of gewoon ? indien het type niet begrensd moet worden (zie later). In plaats van

  public static <T extends Animal> void feedAll(ArrayList<T> animals) { /* ... */ }

kan je dus ook de generische parameter weglaten, en hetvolgende schrijven:

  public static void feedAll(ArrayList<? extends Animal> animals) { /* ... */ }

Je leest deze methode-signatuur als ‘de methode feedAll neemt als parameter een lijst met elementen van een niet nader bepaald subtype van Animal’.

Oefeningen (1)

Voor de tests maken we gebruik van assertJ.

Maybe-klasse

1. Schrijf een generische klasse (of record) Maybe die een object voorstelt dat nul of één waarde van een bepaald type kan bevatten. Dat type wordt bepaald door een generische parameter. Je kan Maybe-objecten enkel aanmaken via de statische methodes some en none. Hieronder vind je twee tests:

@Test
public void maybeWithValue() {
    Maybe<String> maybe = Maybe.some("Yes");
    assertThat(maybe.hasValue()).isTrue();
    assertThat(maybe.getValue()).isEqualTo("Yes");
}

@Test
public void maybeWithoutValue() {
    Maybe<String> maybe = Maybe.none();
    assertThat(maybe.hasValue()).isFalse();
    assertThat(maybe.getValue()).isNull();
}

2. Maak de print-methode hieronder ook generisch, zodat deze niet enkel werkt voor een Maybe<String> maar ook voor andere types dan String.

class MaybePrint {
  public static void print(Maybe<String> maybe) {
    if (maybe.hasValue()) {
      System.out.println("Contains a value: " + maybe.getValue());
    } else {
      System.out.println("No value :(");
    }
  }

  public static void main(String[] args) {
    Maybe<String> maybeAString = Maybe.some("yes");
    Maybe<String> maybeAnotherString = Maybe.none();

    print(maybeAString);
    print(maybeAnotherString);
  }
}

3. Voeg aan Maybe een generische methode map toe die een java.util.function.Function<T, R>-object als parameter heeft, en die een nieuw Maybe-object teruggeeft, met daarin het resultaat van de functie toegepast op het element als er een element is, of een leeg Maybe-object in het andere geval. Zie de tests hieronder voor een voorbeeld van hoe deze map-functie gebruikt wordt:

@Test
public void maybeMapWithValue() {
    Maybe<String> maybe = Maybe.some("Hello");
    Maybe<Integer> result = maybe.map((str) -> str.length());
    assertThat(result.hasValue()).isTrue();
    assertThat(result.getValue()).isEqualTo(5);
}

@Test
public void maybeMapWithValue2() {
    Maybe<String> maybe = Maybe.some("Hello");
    Maybe<String> result = maybe.map((str) -> str + "!");
    assertThat(result.hasValue()).isTrue();
    assertThat(result.getValue()).isEqualTo("Hello!");
}

@Test
public void maybeMapWithoutValue() {
    Maybe<String> maybe = Maybe.none();
    Maybe<Integer> result = maybe.map((str) -> str.length());
    assertThat(result.hasValue()).isFalse();
}

4. (optioneel) Herschrijf Maybe als een sealed interface met twee record-subklassen None en Some. Geef een voorbeeld van hoe je deze klasse gebruikt met pattern matching. Kan je ervoor zorgen dat je getValue() nooit kan oproepen als er geen waarde is (compiler error)?

(extra) SuccessOrFail

Schrijf een generische klasse (of record) SuccessOrFail die een object voorstelt dat precies één element bevat. Dat element heeft 1 van 2 mogelijke types (die types zijn generische parameters). Het eerste type stelt het type van een succesvol resultaat voor; het tweede type is dat van een fout. Je kan objecten enkel aanmaken via de statische methodes success en fail. Een voorbeeld van tests voor die klasse vind je hieronder:

@Test
public void success() {
    SuccessOrFail<String, Exception> result = SuccessOrFail.success("This is the result");
    assertThat(result.isSuccess()).isTrue();
    assertThat(result.successValue()).isEqualTo("This is the result");
}

@Test
public void failure() {
    SuccessOrFail<String, Exception> result = SuccessOrFail.fail(new IllegalStateException());
    assertThat(result.isSuccess()).isFalse();
    assertThat(result.failValue()).isInstanceOf(IllegalStateException.class);
}

Generics en behavioral subtyping (substitutie-principe)

Stel we hebben klassen Animal, Mammal, Cat, Dog, en Bird met een overervingsrelatie:

class Animal { /* ... */ }
class Mammal extends Animal { /* ... */ }
class Cat extends Mammal { /* ... */ }
class Dog extends Mammal { /* ... */ }
class Bird extends Animal { /* ... */ }

graph BT
Cat --> Mammal
Dog --> Mammal
Mammal --> Animal
Bird --> Animal

Het behavioral subtyping-principe (soms ook het Liskov substitutie-principe genoemd) zegt dat overal waar een object van type T verwacht wordt, ook een object van een subtype van T toegelaten wordt. De Java compiler zal deze regel respecteren. Bijvoorbeeld, volgende toekenningen maken gebruik van dit principe, en zijn dus toegelaten:

Animal animal = new Cat();
Mammal mammal = new Dog();
animal = new Bird();

maar mammal = new Bird(); is bijvoorbeeld niet toegelaten.

In onderstaande code is de eerste oproep toegelaten (cat heeft type Cat, en dat is een subtype van Mammal), maar de tweede niet (cat is geen Dog) en de derde ook niet (Cat is geen subtype van Bird):

static void pet(Mammal mammal) { /* ... */ }
static void bark(Dog dog) { /* ... */ }
static void layEgg(Bird bird) { /* ... */ }

Cat cat = new Cat();
pet(cat);    // <- toegelaten (voldoet aan principe)
bark(cat);   // <- niet toegelaten (compiler error)
layEgg(cat); // <- niet toegelaten (compiler error)

Toegepast op lijsten

Een lijst in Java is een geordende groep van elementen van hetzelfde type. List<E> is de interface² die aan de basis ligt van alle lijsten. ArrayList<E> is een klasse die een lijst implementeert met behulp van een array. ArrayList<E> is een subtype van List<E>; volgens het principe kan dus, overal waar een List-object verwacht wordt, ook een ArrayList gebruikt worden. Later (in het hoofdstuk rond Collections) zullen we ook zien dat er een interface Collection<E> bestaat, wat een willekeurige groep van elementen voorstelt: niet enkel een lijst, maar bijvoorbeeld ook verzamelingen (Set) of wachtrijen (Queue). List<E> is een subtype van Collection<E>. Bijgevolg is ook ArrayList<E> een subtype van Collection<E>.

In code ziet deze situatie er als volgt uit:

interface Collection<E> {
  public void add(E element);
  public int size();
  /* ... */
}
interface List<E> extends Collection<E> {
  public E get(int index);
  /* ... */
}
class ArrayList<E> implements List<E> {
  private E[] elements;
  /* ... */
}
interface Set<E> extends Collection<E> { /* ... */ }
interface Queue<E> extends Collection<E> { /* ... */ }

graph BT
Y1["Set#lt;E>"] --> Z0
X0["ArrayList#lt;E>"] --> Y0["List#lt;E>"] --> Z0["Collection#lt;E>"]
Y2["Queue#lt;E>"] --> Z0
style Y1 fill:#eee,stroke:#aaa,color:#888
style Y2 fill:#eee,stroke:#aaa,color:#888

List<Cat> cats = new ArrayList<Cat>();
Collection<Dog> dogs = new ArrayList<Dog>();
List<Animal> animals = new ArrayList<Animal>();

Collection<Dog> dogs = new ArrayList<Cat>(); // compileert niet

graph BT
X1["ArrayList#lt;Cat>"] --> Y1["List#lt;Cat>"] --> Z1["Collection#lt;Cat>"]
X2["ArrayList#lt;Dog>"] --> Y2["List#lt;Dog>"] --> Z2["Collection#lt;Dog>"]
X3["ArrayList#lt;Animal>"] --> Y3["List#lt;Animal>"] --> Z3["Collection#lt;Animal>"]