7. Advanced Java

Hier start het tweede deel van de cursus, waarin we enkele geavanceerdere Java-concepten bekijken. Het uiteindelijk doel is het behandelen van Java Collections en Streams, die een basis geven om complexere problemen efficiënt op te lossen, alsook het voorbereiden op het werken met recursie en backtracking.

We bekijken hier concepten uit Java, maar deze hebben vaak een equivalent in andere talen. Aan het begin van elk hoofdstuk lijsten we daarom ook kort op welke concepten uit andere programmeertalen hier het dichtst bij aanleunen.

Als je Java-kennis wat roestig is (of wanneer je meer ervaring hebt in een andere programmeertaal), kan je je Java-kennis even opfrissen aan de hand van deze pagina.

We maken vanaf nu ook niet langer gebruik van VSCode, maar schakelen over naar Jetbrains IntelliJ IDEA, een van de vaakst gebruikte professionele Java IDE’s. De gratis Community Edition volstaat voor dit vak, maar je kan als student ook een gratis licentie voor de Ultimate Edition aanvragen.

7.1 Records

In andere programmeertalen

De concepten in andere programmeertalen die het dichtst aanleunen bij Java records, pattern matching en sealed interfaces zijn

structs in C en C++ (pattern matching in C++ is nog niet beschikbaar, maar er wordt gewerkt aan dit toe te voegen aan de taal)
@dataclass en structured pattern matching in Python
(sealed) record types en pattern matching in C#

Wat zijn records

Wanneer we object-georiënteerd programmeren, maken we gebruik van encapsulatie: we maken de velden van een klasse gewoonlijk privaat, zodat ze worden afgeschermd van andere klassen. Op die manier kunnen we de interne representatie (de velden en hun types) makkelijk aanpassen: zolang de publieke methodes hetzelfde blijven, heeft zo’n aanpassing geen effect op de rest van het systeem.

Maar soms is encapsulatie niet echt nodig: sommige klassen zijn niet meer dan een bundeling van verschillende waarden. Welgekende voorbeelden zijn een coordinaat (bestaande uit een x- en y-attribuut), een geldbedrag (een bedrag en een munteenheid), een adres (straat, huisnummer, postcode, gemeente), etc. Ze bevatten vaak geen complex gedrag, en objecten van deze klassen hoeven ook niet aanpasbaar te zijn; je kan makkelijk een nieuw object maken met andere waarden. We noemen dit data-oriented programming. Voor dergelijke klassen heeft doorgedreven encapsulatie weinig zin.

Een record in Java is een eenvoudige klasse die gebruikt kan worden voor data-oriented programming. Een record-object dient voornamelijk als data-drager, waarbij verschillende objecten met dezelfde attribuut-waarden gewoonlijk volledig inwisselbaar (equivalent) zijn. De attributen van een record-object mogen daarom niet veranderen doorheen de tijd (het object is dus immutable).

Als voorbeeld definiëren we een coördinaat-klasse als een record, met 2 attributen: een x- en y-coördinaat.

public record Coordinate(double x, double y) {
}

Merk het verschil op met de definitie van een gewone klasse: de attributen van de record staan hier vlak na de klassenaam, en er is geen constructor nodig.

Objecten van een record maak je gewoon aan met new, zoals elk ander object:

Coordinate coord = new Coordinate(3, 5);
System.out.println(coord);
// => Coordinate[x=3.0, y=5.0]

Twee coördinaat-objecten met dezelfde x- en y-coordinaat worden als equivalent beschouwd, ook al zijn het twee verschillende objecten:

var coordinate1 = new Coordinate(3, 5);
var coordinate2 = new Coordinate(3, 5);
assertEquals(coordinate1, coordinate2);

Wanneer gebruik je een record

Er zijn meerdere situaties waarin het aangeraden is om een record te gebruiken, bijvoorbeeld:

wanneer je meerdere waarden (die logisch bij elkaar horen) wil bundelen:

record Address(String street,
               int houseNumber,
               int zipCode,
               String city,
               String country) {}

wanneer je een methode meerdere waarden wil laten teruggeven

record ElementFound(int index, int value) {}

public ElementFound findMaximum(ArrayList<Integer> values) { ... }

wanneer je een type wil definiëren dat overeenkomt met een ander, reeds bestaand datatype, maar met beperkingen.

record PositiveNumber(int number) {
  public PositiveNumber {
    if (number <= 0) throw new IllegalArgumentException("Number must be larger than 0");
  }
}

wanneer je een (immutable) datatype wil maken dat zonder probleem door meerdere threads gebruikt kan worden; dit komt later nog aan bod in het onderwerp Multithreading en concurrency.

Merk op dat bij records in de eerste plaats gaat over het creëren van een nieuw datatype, door (primitievere) data of andere records te bundelen, of beperkingen op te leggen aan mogelijke waarden. Je maakt dus als het ware een nieuw ‘primitief’ datatype, zoals int, double, of String. Dit in tegenstelling tot gewone klassen, waar encapsulatie en mogelijkheden om de toestand van een object aan te passen (mutatie-methodes) ook essentieel zijn.

Achter de schermen

Een record is eigenlijk een gewone klasse, waarbij de Java-compiler zelf enkele zaken voorziet:

een constructor, die de velden initialiseert;
methodes om de attributen op te vragen;
een toString-methode om een leesbare versie van het record uit te printen; en
een equals- en hashCode-methode, die ervoor zorgen dat objecten met dezelfde parameters als gelijk worden beschouwd.

De klasse is ook final, zodat er geen subklassen van gemaakt kunnen worden.

De coördinaat-record van hierboven is equivalent aan volgende klasse-definitie:

public final class Coordinate {
    private final double x;
    private final double y;

    public Coordinate(double x, double y) {
        this.x = x;
        this.y = y;
    }

    double x() { return this.x; }
    double y()  { return this.y; }

    public boolean equals(Object other) { /* ... */ }
    public int hashCode() { /* ... */ }

    public String toString() { /* ... */ }
}

Met de speciale syntax voor records kan je jezelf dus heel wat typwerk (en kans op fouten) besparen.

Methodes toevoegen aan een record

Je kan zelf extra methodes toevoegen aan een record op dezelfde manier als bij een gewone Java-klasse:

public record Coordinate(double x, double y) {

  public double distanceTo(Coordinate other) {
    double deltaX = other.x() - this.x();
    double deltaY = other.y() - this.y();
    return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
  }

}

Merk wel op dat, omdat de klasse immutable is, je in een methode geen nieuwe waarde kan toekennen aan de velden. Code als

  this.x = 5;

in een methode van een record is dus ongeldig, en leidt tot een foutmelding van de compiler.

Constructor van een record

Als je geen enkele constructor definieert, krijgt een record een standaard constructor met de opgegeven attributen als parameters (in dezelfde volgorde).

Maar je kan ook zelf een of meerdere constructoren definiëren voor een record, net zoals bij klassen (je krijgt dan geen default-constructor meer). Je moet in die constructoren zorgen dat alle attributen van het record geïnitialiseerd worden.

public record Coordinate(double x, double y) {
  public Coordinate(double x, double y) {
    this.x = x;
    this.y = y;
  }
  public Coordinate(double x) { // constructor for points on the x-axis
    this(x, 0);
  }
}

Er is ook een verkorte notatie, waarbij je de parameters niet meer moet herhalen (die staan immers al achter de naam van het record). Je hoeft met deze notatie ook de parameters niet toe te kennen aan de velden; dat gebeurt automatisch. Het belangrijkste nut hiervan is om de geldigheid van de waarden te controleren bij het aanmaken van een object:

public record Coordinate(double x, double y) {
  public Coordinate {
    if (x < 0) throw new IllegalArgumentException("x must be non-negative");
    if (y < 0) throw new IllegalArgumentException("y must be non-negative");
  }
}

Records en overerving

Zoals eerder al vermeld werd, komt een record overeen met een final klasse. Je kan er dus niet van overerven.

Een record zelf kan ook geen subklasse zijn van een andere klasse of record, maar kan wel interfaces implementeren.

Immutable

Een record is immutable (onveranderbaar): de attributen krijgen een waarde wanneer het object geconstrueerd wordt, en kunnen daarna nooit meer wijzigen. Als je een object wil met andere waarden, moet je dus een nieuw object maken.

Bijvoorbeeld, als we een translate methode willen maken voor Coordinate, dan kunnen we de x- en y-coordinaten niet aanpassen. We moeten een nieuw Coordinate-object maken, en dat teruggeven:

public record Coordinate(double x, double y) {
  public Coordinate translate(double deltaX, double deltaY) {
    // NIET:
    // this.x += deltaX;  <-- kan niet; de x-waarde mag niet meer gewijzigd worden

    // WEL: een nieuw object maken
    return new Coordinate(this.x + deltaX, this.y + deltaY);
  }
}

Let op! Als een van de velden van het record een object is dat zelf wél gewijzigd kan worden (bijvoorbeeld een array of ArrayList), dan kan je de data die geassocieerd wordt met het record dus wel nog wijzigen. Vermijd deze situatie! Bijvoorbeeld:

public record Song(String title, String artist) {}
public record Playlist(ArrayList<Song> songs) {}

var songs = new ArrayList<>(List.of(new Song("Hello", "Adele")));
var playlist1 = new Playlist(songs);
var playlist2 = new Playlist(new ArrayList<>(songs));
System.out.println(playlist1.equals(playlist2)); // => true: beide playlists bevatten dezelfde liedjes
songs.add(new Song("Bye bye bye", "NSYNC"));
System.out.println(playlist1.equals(playlist2)); // => false

Hier zijn twee record-objecten eerst gelijk, maar later niet meer. Dat schendt het principe dat, voor data-objecten, de identiteit van het object niet zou mogen uitmaken. De objecten zijn immers niet meer dan de aggregatie van de data die ze bevatten. Overal waar playlist1 gebruikt wordt, zou ook playlist2 gebruikt moeten kunnen worden en vice versa. Twee record-objecten die gelijk zijn, moeten altijd gelijk blijven, onafhankelijk van wat er later nog gebeurt. Gebruik dus bij voorkeur immutable data types in een record.

Pattern matching

Je kan records ook gebruiken in switch statements. Dit heet pattern matching, en is vooral nuttig wanneer je meerdere record-types hebt die eenzelfde interface implementeren. Bijvoorbeeld:

interface Shape {}
record Square(double side) implements Shape {}
record Circle(double radius) implements Shape {}
record Rectangle(Coordinate topLeft, Coordinate bottomRight) implements Shape {}

Je kan dan een switch expressie gebruiken, bijvoorbeeld om een methode te implementeren die de oppervlakte van een vorm berekent:

public double area(Shape shape) {
  return switch(shape) {
    case Square s -> s.side() * s.side();
    case Circle(double radius) -> Math.PI * radius * radius;
    case Rectangle(Coordinate(double topLeftX, double topLeftY), Coordinate bottomRight) ->
         (bottomRight.x() - topLeftX) * (bottomRight.y() - topLeftY);
    default -> throw new IllegalArgumentException("Unknown shape");
  };
}

Merk op dat je zowel kan matchen op het object als geheel (Square s in het voorbeeld hierboven), individuele argumenten (Circle(double radius) in het voorbeeld), en zelfs geneste patronen (Rectangle(Coordinate(double topLeftX, double topLeftY), Coordinate bottomRight)).

De switch-expressie hierboven is verschillend van het (oudere) switch-statement in Java:

er wordt -> gebruikt in plaats van :
er is geen break nodig op het einde van elke case
de switch-expressie geeft een waarde terug die kan toegekend worden aan een variabele, of gebruikt kan worden in een return-statement (zoals in het voorbeeld hierboven).

Tenslotte is er in een switch-expressie de mogelijkheid om een conditie toe te voegen door middel van een when-clausule:

public double area(Shape shape) {
  return switch(shape) {
    case Square s -> s.side() * s.side();
    case Circle(double radius) -> Math.PI * radius * radius;
    case Rectangle(Coordinate(double topLeftX, double topLeftY), Coordinate bottomRight)
         when topLeftX <= bottomRight.x() && topLeftY <= bottomRight.y() -> // <= when-clausule
         (bottomRight.x() - topLeftX) * (bottomRight.y() - topLeftY);
    default -> throw new IllegalArgumentException("Unknown or invalid shape");
  };
}

Op die manier kan je extra voorwaarden toevoegen om een case te laten matchen, bovenop het type van het element.

Sealed interfaces

Wanneer je alle klassen kent die een bepaalde interface zullen implementeren (of van een abstracte klasse zullen overerven), kan je van deze interface (of klasse) een sealed interface (of klasse) maken. Met een permits clausule kan je aangeven welke klassen de interface mogen implementeren:

public sealed interface Shape permits Square, Circle, Rectangle {}
record Square(double side) implements Shape {}
record Circle(double radius) implements Shape {}
record Rectangle(double length, double width) implements Shape {}

Indien je geen permits-clausule opgeeft, zijn enkel de klassen die in hetzelfde bestand staan toegestaan.

Omdat elk Java-bestand slechts 1 publieke top-level klasse (of interface/record) mag hebben, zal je vaak ook zien dat de records in de interface-definitie geplaatst worden:

public sealed interface Shape {
  record Square(double side) implements Shape {}
  record Circle(double radius) implements Shape {}
  record Rectangle(double length, double width) implements Shape {}
}

Zo staan ze allemaal samen in 1 bestand, en kan je ze overal in je code gebruiken via bv. Shape.Square.

Voor een sealed klasse of interface zoals Shape zal de compiler niet toelaten dat je er ergens anders een andere klasse van laat overerven:

record Triangle(double base, double height) implements Shape {} // <- compiler error

Omdat de compiler kan nagaan wat alle mogelijkheden zijn, kan je bij pattern matching op een sealed klasse in een switch statement ook de default case weglaten:

public double area(Shape shape) {
  return switch(shape) {
    case Square s -> s.side() * s.side();
    case Circle(double radius) -> Math.PI * radius * radius;
    case Rectangle(double width, double height) -> width * height;
  };
}

Omgekeerd zal de compiler je ook waarschuwen wanneer er een geval ontbreekt.

public double area(Shape shape) {
  return switch(shape) {
    case Square s -> s.side() * s.side();
    case Circle(double radius) -> Math.PI * radius * radius;
    // <= compiler error: ontbrekende case voor 'Rectangle'
  };
}

Oefeningen

Zie Oefeningen

Oefeningen

Klasse of record?

Geef enkele voorbeelden van types die volgens jou best als record gecodeerd worden, en ook enkele types die best als klasse gecodeerd worden.

Kan je, voor een van je voorbeelden, een situatie bedenken waarin je van record naar klasse zou gaan, en omgekeerd?

Antwoord

Records zijn vooral geschikt voor het bijhouden van stateless informatie (objecten zonder gedrag). Bijvoorbeeld: Money, ISBN, BookInfo, ProductDetails, …

Klassen zijn geschikt als de identiteit van het object van belang is en constant blijft, maar de state (data) doorheen de tijd kan wijzigen. Bijvoorbeeld: BankAccount, ShoppingCart, GameCharacter, OrderProcessor, …

Overgaan van de ene naar de andere vorm kan wanneer er gedrag toegevoegd of verwijderd wordt. Bijvoorbeeld, BookInfo zou een klasse kunnen worden indien we er (in de context van een bibliotheek) ook informatie over ontleningen in willen bijhouden. Omgekeerd kan BankAccount van klasse naar object gaan indien het enkel een voorstelling wordt van rekeninginformatie (rekeningnummer en naam van de houder bijvoorbeeld), en de balans en transacties naar een ander object (bv. TransactionHistory) verplaatst worden.

Sealed interface

Kan je een voorbeeld bedenken van een nuttig gebruik van een sealed interface?

Antwoord

Sealed interfaces zijn vooral nuttig om een uitgebreidere vorm van enum’s te maken, waar elke optie ook extra informatie met zich kan meedragen.

Bijvoorbeeld:

sealed interface PaymentMethod om een manier van betalen voor te stellen, met subtypes (records) CreditCard(cardName, cardNumber, expirationDate), PayPal(email), BankTransfer(iban), …
sealed interface Command wat een commando voorstelt dat uitgevoerd kan worden, met subtypes (records) CreateUser(name, email), DeleteUser(uuid), UpdateUser(uuid, newEmail), …

Email

Definieer (volgens de principes van TDD) een Email-record dat een geldig e-mailadres voorstelt. Het mail-adres wordt voorgesteld door een String.

Controleer de geldigheid van de String bij het aanmaken van een Email-object:

de String mag niet null zijn
de String moet exact één @-teken bevatten
de String moet eindigen op “.com” of “.be”

Note

De echte regels voor een geldig emailadres zijn uiteraard veel complexer. Zie bijvoorbeeld de voorbeelden van geldige e-mailadressen op deze Wikipedia-pagina.

Money

Maak (volgens de principes van TDD) een Money-record dat een geldbedrag (bijvoorbeeld 20) en een munteenheid (bijvoorbeeld “EUR”) bevat. Voeg ook methodes toe om twee geldbedragen op te tellen. Dit mag enkel wanneer de munteenheid van beiden gelijk is; zoniet moet er een exception gegooid worden.

Interval

Maak (volgens de principes van TDD) een Interval-record dat een periode tussen twee tijdstippen voorstelt, bijvoorbeeld voor een vergadering. Elk tijdstip wordt voorgesteld door een niet-negatieve long-waarde. Het eind-tijdstip mag niet voor het start-tijdstip liggen.

Voeg een methode toe om na te kijken of een interval overlapt met een ander interval. Intervallen worden beschouwd als half-open: twee aansluitende intervallen overlappen niet, bijvoorbeeld [15, 16) en [16, 17).

Rechthoek

Schrijf (volgens de principes van TDD) een record die een rechthoek voorstelt. Een rechthoek wordt gedefinieerd door 2 punten (linksboven en rechtsonder). Gebruik een Coordinaat-record om deze hoekpunten voor te stellen. Zorg ervoor dat enkel geldige rechthoeken aangemaakt kunnen worden (dus: het hoekpunt linksboven ligt zowel links als boven het hoekpunt rechtsonder).

Voeg extra methodes toe:

om de twee andere hoekpunten (linksonder en rechtsboven) op te vragen
om na te gaan of een gegeven punt zich binnen de rechthoek bevindt
om na te gaan of een rechthoek overlapt met een andere rechthoek. (Hint: bij twee overlappende rechthoeken ligt minstens één hoekpunt van de ene rechthoek binnen de andere)

Expressie-hierarchie

Maak een set van records om een wiskundige uitdrukking voor te stellen. Alle records moeten een sealed interface Expression implementeren.

De mogelijke expressies zijn:

een Literal: een constante getal-waarde (een double)
een Variable: een naam (een String), bijvoorbeeld “x”
een Sum: bevat twee expressies, een linker en een rechter
een Product: gelijkaardig aan Som, maar stelt een product voor
een Power: een expressie tot een constante macht

De veelterm $ 3x^2+5 $ kan dus voorgesteld worden als:

var poly = new Sum(
  new Product(
    new Literal(3),
    new Power(
      new Variable("x"),
      new Literal(2))),
  new Literal(5));

Maak nu een klasse ExpressionUtils met volgende statische methodes (de beschrijving volgt hieronder).

class ExpressionUtils {
  public static String prettyPrint(Expression expr) { ... }
  public static Expression simplify(Expression expr) { ... }
  public static double evaluate(Expression expr, ArrayList<Assignment> variableValues) { ... }
  public static Expression differentiate(Expression expr, Variable var) { ... }
}

Gebruik pattern matching (en TDD) voor elk van volgende opdrachten:

Schrijf de methode prettyPrint die de gegeven expressie omzet in een string, bijvoorbeeld prettyPrint(poly) geeft (3.0) * ((x)^2.0) + 5.0.
zorg ervoor dat er geen onnodige haakjes verschijnen in het resultaat van prettyPrint, door rekening te houden met de volgorde van de bewerkingen. (Hint: geef elke expressie een numerieke prioriteit)
de methode simplify moet de gegeven expressie te vereenvoudigen door enkele vereenvoudigingsregels toe te passen. Bijvoorbeeld, het vervangen van $3 + 7$ door $10$, vervangen van $x+0$, $x*1$, en $x^1$ door $x$; vervangen van $x * 0$ door $0$, …
de methode evaluate moet de gegeven expressie evalueren voor de gegeven waarden van de variabelen. Bijvoorbeeld, $ 3x^2+5 $ evalueren met $ x=7 $ geeft $152$. De parameter variableValues bevat een lijst van toekenningen van een waarde aan een variabele. Je moet de klasse Assignment eerst zelf nog maken (Hint: gebruik hiervoor ook een record).
de methode differentiate moet de afgeleide berekenen van de gegeven expressie in de gegeven variabele (bv. $ \frac{d}{dx} 3x^2+5x = 6x+5 $).

Denkvraag

Wat is het voor- en nadeel van het gebruik van pattern matching tegenover het gebruik van overerving en dynamische binding? Met andere woorden, wat is het verschil met bijvoorbeeld de methodes simplify(), evaluate(), … in de interface Expression zelf te definiëren, en ze te implementeren in elke subklasse?

7.2 Generics

In andere programmeertalen

De concepten in andere programmeertalen die het dichtst aanleunen bij Java generics zijn

templates in C++
generic types in Python (as type hints)
generics in C#

In dit hoofdstuk behandelen we generics. Die worden veelvuldig gebruikt in datastructuren, en een goed begrip ervan is dan ook essentieel.

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, telkens met een ander type van elementen in de lijst. We kunnen nu nog niet zeggen wat het type wordt van die elementen. 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 één en 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 maken, waar het bedoelde type van elementen wel duidelijk is, en ook wordt afgedwongen 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 hun elementen. Dat leidt tot veel onnodige en ongewenste code-duplicatie.

Met generics kan je een type gebruiken als parameter voor een klasse (of methode, zie later) om code-duplicatie zoals hierboven te vermijden. Dat ziet er dan als volgt uit (we gaan zodadelijk verder in op de details):

class ArrayList<T> { 
  private T[] elements;
  // ...
}

Generics geven je dus een combinatie van de beste eigenschappen van de twee opties die we overwogen hebben:

er moet slechts één implementatie gemaakt worden (zoals bij ArrayList hierboven), en
deze implementatie kan gebruikt worden om lijsten te maken waarbij het gegarandeerd is dat alle elementen een specifiek type hebben (zoals bij ArrayListOfStudents).

In de volgende secties vind je meer informatie over het gebruik van generics.

Deze klasse is geïnspireerd op de ArrayList-klasse die standaard in Java zit. ↩︎

7.2.1 Definiëren en gebruiken

Om een klasse generisch te maken, moet je een generische parameter (meestal aangegeven met een enkele letter) toevoegen, zoals de generische parameter T bij ArrayList<T>. In het algemeen zijn er slechts twee plaatsen in je code waar je een nieuwe generische parameter mag introduceren:

Bij de definitie van een klasse (of interface, record, …)
Bij de definitie van een methode (of constructor)

Een generische klasse definiëren

Om een generische klasse te definiëren (de eerste optie), zet je de type-parameter tussen < en > achter de naam van de klasse die je definieert. Vervolgens kan je die parameter (bijna¹) overal in die klasse gebruiken als type:

class MyGenericClass<E> {
  // je kan hier (bijna) overal E gebruiken als type
}

Bijvoorbeeld, volgende klasse is een nieuwe versie van de ArrayList-klasse van eerder, maar nu met type-parameter E (waar E staat voor ‘het type van de elementen’). Deze E wordt vervolgens gebruikt als type voor 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 (populaire letters zijn bijvoorbeeld E, R, T, U, V). 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) { /* ... */ }
}

Weetje

Je kan een generische klasse ook zien als een functie (soms een type constructor genoemd). Die functie geeft geen object terug op basis van een of meerdere parameters zoals je dat gewoon bent van een functie, bijvoorbeeld getPet : (Person p) → Animal, maar geeft een nieuw type (een nieuwe klasse) terug, gebaseerd op de type-parameters. Bijvoorbeeld, de generische klasse ArrayList<T> kan je beschouwen als een functie ArrayList : (Type T) → Type, die het type ArrayListOfStudents of ArrayListOfAnimals teruggeeft wanneer je ze oproept met respectievelijk T=Student of T=Animal. In plaats van ArrayListOfStudents schrijven we dat type als ArrayList<Student>.

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, op plaatsen waar je een lijst met enkel studenten verwacht, gebruik je ArrayList<Student> als type. 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); // <-- OK 👍
// students.add(animal); // <-- niet toegelaten (compiler error) 👍
Student firstStudent = students.get(0); // <-- OK 👍

Merk op hoe de compiler afdwingt en garandeert dat er enkel Student-objecten in deze lijst 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 kan immers automatisch afgeleid worden van het type van de variabele:

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

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 (A) dat dat voedsel eet:

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

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

De Food-klasse is enkel bedoeld om met Animal (en de subklassen van Animal) gebruikt te worden, bijvoorbeeld Food<Cat> en Food<Dog>. Maar niets houdt ons op dit moment tegen om ook een Food<Student of een Food<String> te maken. Daarenboven zal de compiler (terecht) ook een compilatiefout geven in de methode giveTo van Food: er wordt een Animal-specifieke methode opgeroepen (namelijk showLike) op de parameter animal, maar die heeft type A en dat kan eender wat zijn, bijvoorbeeld ook String. En String biedt natuurlijk geen methode showLike() aan.

We kunnen daarom aangeven dat type A een subtype moet zijn van Animal door bij de definitie van de generische parameter <A extends Animal> te schrijven. 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 A tot alle types die overerven van Animal (inclusief Animal zelf).

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

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

Note

Wanneer je deze materie later opnieuw doorneemt, heb je naast extends ook al gehoord van super en wildcards (?) — dit wordt later besproken. Het is belangrijk om op te merken dat je super en ? nooit kan gebruiken bij de definitie van een nieuwe generische parameter (de Java compiler laat dit niet toe). Dat kan enkel op de plaatsen waar je een generische klasse of methode gebruikt. Onthoud dus: op de plaatsen waar je een nieuwe parameter (een nieuwe ’letter’) introduceert, kan je enkel aangeven dat die een subtype van iets moet zijn met behulp van extends.

Een generische methode definiëren en gebruiken

In de voorbeelden hierboven hebben we steeds een hele klasse generisch gemaakt. Naast een generische klasse was er ook een tweede plaats om een generische parameter te definiëren, namelijk eentje die enkel in één methode gebruikt kan worden. Dat doe je door de parameter te declareren vóór het terugkeertype van die methode, opnieuw tussen < en >. Dat kan ook in een klasse die zelf geen type-parameters heeft.

Je kan die parameter dan gebruiken in de methode zelf, en ook in de types van de parameters en het terugkeertype (dus overal na de definitie ervan). Bijvoorbeeld, onderstaande methodes doSomething en doSomethingElse hebben beiden een generische parameter T. Die parameter hoort enkel bij elke individuele methode; beide generische types staan dus volledig los van elkaar. Ook NormalClass is geen generische klasse; enkel de twee methodes zijn generisch.

class NormalClass {
  public <T> int doSomething(ArrayList<T> elements) {
    // je kan overal in deze methode type T gebruiken
  }
  public static <T> ArrayList<T> doSomethingElse(ArrayList<T> elements, T element) {
    // deze T is onafhankelijk van die in doSomething
  }
}

Het is trouwens ook mogelijk om generische klassen en generische methodes te combineren:

class Foo<T> {
  public <U> ArrayList<U> doSomething(ArrayList<T> ts, ArrayList<U> us) {
    // code met T en U
  }
}

Type inference

Bij het gebruik van een generische methode zal de Java-compiler zelf proberen om de juiste types te vinden; dit heet type inference. Je kan de methode meestal gewoon oproepen zoals elke andere methode, en hoeft dus (in tegenstelling tot bij klassen) niet zelf aan te geven hoe de generische parameters geïnstantieerd worden.

ArrayList<Dog> dogs = ...
Dog dog = ...
var result = NormalClass.doSomethingElse(dogs, dog);
// result heeft type ArrayList<Dog>

In de uitzonderlijke gevallen waar type inference faalt, of wanneer je het type van de generische parameter expliciet wil maken, kan je die zelf opgeven als volgt:

ArrayList<Dog> dogs = ...
Dog dog = ...
var result = NormalClass.<Dog>doSomethingElse(animals, dog);

Merk op hoe we, tussen het . en de naam van de methode, de generische parameter <Dog> toevoegen.

Voorbeeld

Als voorbeeld definiëren we (in een niet-generische klasse AnimalHelper) een generische (statische) methode findHappyAnimals. Deze heeft 1 generische parameter T, en we leggen meteen ook op dat dat een subtype van Animal moet zijn (<T extends Animal>).

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 dat we het type T zowel gebruiken bij de animals-parameter als bij het terugkeertype van de methode. Zo kunnen we garanderen dat de teruggegeven lijst precies hetzelfde type elementen heeft als de lijst animals, zonder dat we al moeten vastleggen welk type dier (bv. Cat of Dog) dat precies is. Dus: als we een ArrayList<Cat> meegeven aan de methode, krijgen we ook een ArrayList<Cat> terug.

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

class AnimalHelper {
  // voorbeeld van een generisch record
  public record AnimalPair<T extends Animal>(T male, T female) {} 

  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) 👍

Merk hierboven op hoe, door de parameter T op verschillende plaatsen te gebruiken in de methode, deze methode enkel gebruikt kan worden om twee lijsten met dezelfde diersoorten te koppelen, en er meteen ook gegarandeerd wordt dat de AnimalPair-objecten die teruggegeven worden ook hetzelfde type dier bevatten.

Als het type T niet van belang is omdat het nergens terugkomt (niet in het terugkeertype van de methode, niet bij een andere parameter, en ook niet in de body van de methode), dan heb je strikt gezien geen generische methode nodig. Zoals we later bij het gebruik van wildcards zullen zien, kan je dan ook gewoon het wildcard-type <? extends X> gebruiken, of <?> indien het type niet begrensd moet worden. In plaats van

  public static <T extends Animal> void feedAll(ArrayList<T> animals) {
    // code die T nergens vermeldt
  }

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

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

Dit is nu geen generische methode meer (er wordt geen nieuwe generische parameter geïntroduceerd); de parameter animals maakt wel gebruik van een generisch type. Je leest deze methode-signatuur als ‘de methode feedAll neemt als parameter een lijst met elementen van een willekeurig (niet nader bepaald) subtype van Animal’.

Onthoud

Er zijn slechts 2 plaatsen waar je een nieuwe generische parameter (een ’letter’ zoals T of U) mag introduceren:

vlak na de naam van een klasse (of record, interface, …) die je definieert (class Foo<T> { ... }); of
vlak vóór het terugkeertype van een methode (public <T> void doSomething(...) { }).

Op alle andere plaatsen waar je naar een generische parameter verwijst (door de letter te gebruiken), moet je ervoor zorgen dat deze eerst gedefinieerd werd op één van deze twee plaatsen.

Meerdere type-parameters

De ArrayList<E>-klasse hierboven had één generische parameter (E). Een generische klasse of methode kan ook meerdere type-parameters hebben, bijvoorbeeld een tuple van 3 elementen van mogelijk verschillend type (we maken hier een record in plaats van een klasse):

record Tuple3<T1, T2, T3>(T1 first, T2 second, T3 third) {
  /* ... */
}

Bij het gebruik van deze klasse (bijvoorbeeld bij het aanmaken van een nieuw object) moet je dan voor elke parameter (T1, T2, en T3) een concreet type opgeven:

Tuple3<String, Integer, String> tuple = new Tuple3<>("John", 2025, "CS101");

Ook hier kan je met de verkorte notatie <> werken om jezelf niet te moeten herhalen.

Note

Het lijkt erg handig om zo’n Tuple-type overal in je code te gebruiken waar je drie objecten samen wil bundelen, maar dat wordt afgeraden. Niet omdat het drie generische parameters heeft (dat is perfect legitiem), maar wel omdat het niets zegt over de betekenis van de velden (wat zit er in ‘first’, ‘second’, ’third’?). Gebruik in plaats van een algemene Tuple-klasse veel liever een record waar je de individuele componenten een zinvolle naam geeft. Bijvoorbeeld: record Enrollment(String student, int year, String courseId) {} of record Point3D(double x, double y, double x) {}.

De generische parameter kan niet gebruikt worden in de statische velden, methodes, inner classes, … van de klasse. ↩︎

7.2.2 Generics en subtyping

Stel we hebben klassen Animal, Mammal, Cat, Dog, en Bird met volgende 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

Een van de basisregels van object-georiënteerd programmeren is dat overal waar een object van type X verwacht wordt, ook een object van een subtype van X toegelaten wordt. De Java compiler respecteert deze regel uiteraard. Volgende toekenningen zijn bijvoorbeeld toegelaten:

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

maar mammal = new Bird(); is bijvoorbeeld niet toegelaten, want Bird is geen subtype van Mammal.

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) 👍

Subtyping en generische 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>; dus overal waar een List-object verwacht wordt, mag 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 (via transitiviteit) is ArrayList<E> dus ook 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

Volgende code is geldig:

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

maar hetvolgende kan uiteraard niet:

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>"]

Het lijkt intuïtief misschien logisch dat ArrayList<Cat> ook een subtype moet zijn van ArrayList<Animal>. Een lijst van katten lijkt tenslotte toch een speciaal geval te zijn van een lijst van dieren? Maar dat is niet het geval.

ArrayList<Animal> = new ArrayList<Cat>(); // compileert niet

graph BT
id1(Niet correct)
style id1 fill:#f99,stroke:#600,stroke-width:4px
X0["ArrayList#lt;Cat>"] -- #times; --> Y0["ArrayList#lt;Animal>"]

Waarom niet? Stel dat ArrayList<Cat> toch een subtype zou zijn van ArrayList<Animal>. Dan zou volgende code ook geldig zijn:

ArrayList<Cat> cats = new ArrayList<Cat>();
ArrayList<Animal> animals = cats; // <- dit zou geldig zijn (maar is het niet!)
Dog dog = new Dog();
animals.add(dog); // <- OOPS: er zit nu een hond in de lijst van katten 🙁

Je zou dus honden kunnen toevoegen aan je lijst van katten zonder dat de compiler je waarschuwt, en dat is niet gewenst. Om die reden beschouwt Java ArrayList<Cat> dus niet als subtype van ArrayList<Animal>, ondanks dat Cat wél een subtype van Animal is.

Onthoud

Zelfs als klasse Sub een subtype is van klasse Super, dan is ArrayList<Sub> toch geen subtype van ArrayList<Super>.

Later zullen we zien hoe we hier met wildcards in sommige gevallen wel flexibeler mee kunnen omgaan.

Overerven van een generisch type

Hierboven gebruikten we vooral ArrayList als voorbeeld van een generische klasse. We hebben echter ook gezien dat je zelf generische klassen kan definiëren, en daarvan kan je uiteraard ook overerven.

Bij de definitie van een subklasse moet je voor de generische parameter van de superklasse een waarde (type) meegeven. Je kan ervoor kiezen om je subklasse zelf generisch te maken (dus een nieuwe generische parameter te introduceren), of om een vooraf bepaald type mee te geven. Bijvoorbeeld:

class Super<T> { ... }

class SubForAnimal<A extends Animal> extends Super<A> { ... }

class SubForCat extends SubAnimal<Cat> { ... }

De superklasse Super heeft een generische parameter T. De subklasse SubForAnimal definieert zelf een generische parameter A (hier met begrenzing), en gebruikt parameter A als type voor T uit de superklasse. De klasse SubForCat tenslotte definieert zelf geen nieuwe generische parameter, maar geeft het type Cat op als type voor parameter A uit diens superklasse.

Een interface kan je zien als een abstracte klasse waarvan alle methodes abstract zijn. Het defineert alle methodes die geïmplementeerd moeten worden, maar bevat zelf geen implementatie. ↩︎

7.2.3 Wildcards

We zagen eerder dat de types List<Dog> en List<Animal> niets met elkaar te maken hebben, ondanks het feit dat Dog een subtype is van Animal. Dat geldt in het algemeen voor generische types.

Als beide generische parameters hetzelfde type hebben, bestaat er wel een overervingsrelatie. Bijvoorbeeld, in volgende situatie:

class Shelter<T> { }
class AnimalShelter<A extends Animal> extends Shelter<A> { ... }

is AnimalShelter<Dog> wel degelijk een subtype van Shelter<Dog>, om dezelfde reden dat ArrayList<Dog> een subtype is van List<Dog>. Volgende toekenning en methode-oproep zijn dus toegelaten:

Shelter<Dog> shelter = new AnimalShelter<Dog>(); // OK! 👍

public void protectDog(Shelter<Dog> s) { ... }
AnimalShelter<Dog> animalShelter = new AnimalShelter<Dog>();
protectDog(animalShelter); // OK! 👍

Dat komt omdat AnimalShelter een subtype is van Shelter, en de generische parameter bij beiden hetzelfde is.

Als de generische parameters verschillend zijn, is er echter geen overervingsrelatie. Bijvoorveeld, tussen AnimalShelter<Cat> en Shelter<Animal> is er geen overervingsrelatie. Ook is Shelter<Cat> geen subtype van Shelter<Animal>. Het volgende is bijgevolg niet toegelaten:

Shelter<Animal> s = new AnimalShelter<Cat>(); // NIET toegelaten

public void protectAnimal(Shelter<Animal> s) { ... }
AnimalShelter<Cat> animalShelter = new AnimalShelter<Cat>(); // wel OK!
protectAnimal(animalShelter); // NIET toegelaten

In sommige situaties willen we wel zo’n overervingsrelatie kunnen maken. We bekijken daarvoor twee soorten relaties, namelijk covariantie en contravariantie.

Note

Opgelet: Zowel covariantie als contravariantie gaan enkel over het gebruik van generische klassen. Meer bepaald beïnvloeden ze wanneer twee generische klassen door de compiler als subtype van elkaar beschouwd worden. Dat staat los van de definitie van een generische klasse — die definities (en bijhorende begrenzing) blijven onveranderd!

Covariantie (extends)

Wat als we een methode copyFromTo willen schrijven die de dieren uit een gegeven (bron-)lijst toevoegt aan een andere (doel-)lijst van dieren? Bijvoorbeeld:

public static void copyFromTo(
    ArrayList<Animal> source,
    ArrayList<Animal> target) {
  for (Animal a : source) { target.add(a); }
}

ArrayList<Animal> animals = new ArrayList<>();
ArrayList<Cat> cats = /* ... */
ArrayList<Dog> dogs = /* ... */
/* ... */
copyFromTo(dogs, animals); // niet toegelaten 🙁
copyFromTo(cats, animals); // niet toegelaten 🙁

Volgens de regels die we hierboven gezien hebben, kunnen we deze methode niet gebruiken om de dieren uit een lijst van honden (ArrayList<Dog>) of katten (ArrayList<Cat>) te kopiëren naar een lijst van dieren (ArrayList<Animal>). Maar dat lijkt wel een zinnige operatie. Een oplossing kan zijn om verschillende versies van de methode te schrijven:

public static void copyFromCatsTo(
    ArrayList<Cat> source,
    ArrayList<Animal> target) {
  for (Cat cat : source) { target.add(cat); }
}
public static void copyFromDogsTo(
    ArrayList<Dog> source,
    ArrayList<Animal> target) {
  for (Dog dog : source) { target.add(dog); }
}
public static void copyFromBirdsTo(
    ArrayList<Bird> source,
    ArrayList<Animal> target) {
  for (Bird bird : source) { target.add(bird); }
}

Note

Merk op dat de oproep target.add(cat), alsook die met dog en bird, toegelaten is, omdat Cat, Dog en Bird subtypes zijn van Animal.

Maar dan lopen we opnieuw tegen het probleem van gedupliceerde code aan. Een eerste oplossing daarvoor is een generische methode, met een generische parameter die begrensd is (T extends Animal):

public static <T extends Animal> void copyFromTo_generic(
    ArrayList<T> source,
    ArrayList<Animal> target) {
  for (Animal a : source) { target.add(a); }
}

Dat werkt, maar de generische parameter T wordt slechts eenmaal gebruikt, namelijk bij de parameter ArrayList<T> source. In zo’n situatie kunnen we ook gebruik maken van het wildcard-type <? extends X>. We kunnen bovenstaande methode dus ook zonder generische parameter schrijven als volgt:

public static void copyFromTo_wildcard(
    ArrayList<? extends Animal> source,
    ArrayList<Animal> target) {
  for (Animal a : source) { target.add(a); }
}

Volgende code is nu toegelaten:

copyFromTo_wildcard(dogs, animals); // OK! 👍
copyFromTo_wildcard(cats, animals); // OK! 👍

Het type ArrayList<? extends Animal> staat dus voor “elke ArrayList waar het element-type een (niet nader bepaald) subtype is van Animal”. Je kan dit ook bekijken alsof het type ArrayList<? extends Animal> tegelijk staat voor de types ArrayList<Animal>, ArrayList<Mammal>, ArrayList<Cat>, ArrayList<Dog>, alsook een lijst van elk ander type dier.

Dit heet covariantie: omdat Cat een subtype is van Animal, is ArrayList<Cat> een subtype van ArrayList<? extends Animal>. De ‘co’ in covariantie wijst erop dat de overervingsrelatie tussen Cat en Animal in dezelfde richting loopt als die tussen ArrayList<Cat> en ArrayList<? extends Animal> (in tegenstelling tot contravariantie, wat zodadelijk aan bod komt). Dat zie je op de afbeelding hieronder:

graph BT
ALCat["ArrayList#lt;Cat>"]
ALextendsAnimal["ArrayList#lt;? extends Animal>"]
ALAnimal["ArrayList#lt;Animal>"]
ALAnimal --> ALextendsAnimal
ALCat --> ALextendsAnimal

Cat --> Animal

classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,Cat cat;
class ALAnimal,Animal,ALextendsAnimal animal;

Merk op dat ArrayList<Animal> ook een subtype is van ArrayList<? extends Animal>.

We kunnen ook de relatie met Mammal toevoegen aan het plaatje:

graph BT
ALCat["ArrayList#lt;Cat>"]
ALextendsAnimal["ArrayList#lt;? extends Animal>"]
ALextendsMammal["ArrayList#lt;? extends Mammal>"]
ALextendsCat["ArrayList#lt;? extends Cat>"]
ALAnimal["ArrayList#lt;Animal>"]
ALMammal["ArrayList#lt;Mammal>"]
ALAnimal --> ALextendsAnimal
ALextendsMammal --> ALextendsAnimal
ALMammal --> ALextendsMammal
ALextendsCat --> ALextendsMammal
ALCat --> ALextendsCat

Cat --> Mammal
Mammal --> Animal


classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,Cat,ALextendsCat cat;
class ALMammal,Mammal,ALextendsMammal mammal;
class ALAnimal,Animal,ALextendsAnimal animal;

Tenslotte kan je in Java ook <?> schrijven (bijvoorbeeld ArrayList<?>); dat is een verkorte notatie voor ArrayList<? extends Object>. Je interpreteert ArrayList<?> dus als een lijst van een willekeurig maar niet gekend type. Merk op dat ArrayList<?> dus niet hetzelfde is als ArrayList<Object>. Een ArrayList<Cat> is een subtype van ArrayList<?>, maar niet van ArrayList<Object>.

Hou er ook rekening mee dat elk voorkomen van ? voor een ander type staat (of kan staan). Hetvolgende kan dus niet:

public void copyMammalsFromTo(
      ArrayList<? extends Mammal> source,
      ArrayList<? extends Mammal> target) {
  for (Mammal m : source) { target.add(m); } // compileert niet! 🙁
}

omdat de eerste ArrayList<? extends Mammal> (source) bijvoorbeeld een ArrayList<Cat> kan zijn, en de tweede (target) een ArrayList<Dog>. Als je de types van beide parameters wil linken aan elkaar, moet je een generische methode gebruiken (zoals eerder gezien):

public <T extends Mammal> void copyMammalsFromTo(
    ArrayList<T> source,
    ArrayList<T> target) {
  for (Mammal m : source) { target.add(m); } // OK! 👍
}

Onderstaande code is ook ongeldig. Waarom?

ArrayList<?> lijst = new ArrayList<String>();
lijst.add("Hello");

Antwoord

De lijst-variabele is gedeclareerd als een ArrayList met elementen van een ongekend type. Op basis van het type van de variabele kan de compiler niet afleiden dat er Strings toegevoegd mogen worden aan de lijst (het zou evengoed een ArrayList van Animals kunnen zijn). Het feit dat lijst geinititialiseerd wordt met <String> doet hier niet terzake; enkel het type van de declaratie is van belang.

Onthoud

Het type ArrayList<? extends Mammal> staat tegelijk voor de types ArrayList<Mammal>, ArrayList<Cat>, ArrayList<Dog>, en elk ander type dat overerft van Mammal.

Contravariantie (super)

Wat als we een methode willen die de objecten uit een gegeven bronlijst van katten kopieert naar een doellijst van willekeurige dieren? Bijvoorbeeld:

public static void copyFromCatsTo(
      ArrayList<Cat> source,
      ArrayList<Animal> target) {
  for (Cat cat : source) { target.add(cat); }
}

ArrayList<Cat> cats = /* ... */

ArrayList<Cat> otherCats = new ArrayList<>();
ArrayList<Mammal> mammals = new ArrayList<>();
ArrayList<Animal> animals = new ArrayList<>();

copyFromTo(cats, otherCats); // niet toegelaten 🙁
copyFromTo(cats, mammals);   // niet toegelaten 🙁
copyFromTo(cats, animals);   // OK 👍

De eerste twee copyFromTo-regels zijn niet toegelaten, maar zouden opnieuw erg nuttig kunnen zijn. Co-variantie met extends helpt ook niet (target zou dan immers ook een ArrayList<Dog> kunnen zijn):

public static void copyFromCatsTo(
      ArrayList<Cat> source,
      ArrayList<? extends Animal> target) {
  for (Cat cat : source) { target.add(cat); } // ook niet toegelaten 🙁
}

En aparte methodes schrijven leidt opnieuw tot code-duplicatie:

public static void copyFromCatsToCats(
    ArrayList<Cat> source,
    ArrayList<Cat> target) {
  for (Cat cat : source) { target.add(a); }
}
public static void copyFromCatsToMammals(
    ArrayList<Cat> source,
    ArrayList<Mammal> target) {
  for (Cat cat : source) { target.add(a); }
}
public static void copyFromCatsToAnimals(
    ArrayList<Cat> source,
    ArrayList<Animal> target) {
  for (Cat cat : source) { target.add(a); }
}

Denkvraag

Zou het nuttig zijn om een methode copyFromCatsToBirds(ArrayList<Cat> source, ArrayList<Bird> target) te voorzien? Waarom (niet)?

De oplossing in dit geval is gebruik maken van het wildcard-type <? super T>. Het type ArrayList<? super Cat> staat dus voor “elke ArrayList waar het element-type een supertype is van Cat” (inclusief het type Cat zelf). Of nog: ArrayList<? super Cat> staat tegelijk voor de types ArrayList<Cat>, ArrayList<Mammal>, ArrayList<Animal>, en ArrayList<Object>, alsook elke andere ArrayList met een supertype van Cat als element-type.

We kunnen dus schrijven:

public static void copyFromCatsTo_wildcard(
    ArrayList<Cat> source,
    ArrayList<? super Cat> target) {
  for (Cat cat : source) { target.add(a); }
}

en kunnen nu hetvolgende uitvoeren:

copyFromCatsTo_wildcard(cats, otherCats); // OK 👍
copyFromCatsTo_wildcard(cats, mammals);   // OK 👍
copyFromCatsTo_wildcard(cats, animals);   // OK 👍

Dit heet contravariantie: hoewel Cat een subtype is van Animal, is ArrayList<? super Cat> een supertype vanArrayList<Animal>. De ‘contra’ in contravariantie wijst erop dat de overervingsrelatie tussen Cat en Animal in de omgekeerde richting loopt als die tussen ArrayList<? super Cat> en ArrayList<Animal>. Bekijk volgende figuur aandachtig:

graph BT
ALsuperCat["ArrayList#lt;? super Cat>"]
ALAnimal["ArrayList#lt;Animal>"]
ALCat["ArrayList#lt;Cat>"]
ALAnimal --> ALsuperCat
ALCat --> ALsuperCat

Cat --> Animal
classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,ALsuperCat,Cat cat;
class ALAnimal,Animal animal;

Als we ook ArrayList<Mammal>, ArrayList<? super Mammal>, en ArrayList<? super Animal> toevoegen aan het plaatje, ziet dat er als volgt uit:

graph BT
ALCat["ArrayList#lt;Cat>"]
ALsuperCat["ArrayList#lt;? super Cat>"]
ALsuperMammal["ArrayList#lt;? super Mammal>"]
ALsuperAnimal["ArrayList#lt;? super Animal>"]
ALMammal["ArrayList#lt;Mammal>"]
ALAnimal["ArrayList#lt;Animal>"]
ALCat --> ALsuperCat
ALAnimal --> ALsuperAnimal
ALMammal --> ALsuperMammal
ALsuperAnimal --> ALsuperMammal
ALsuperMammal --> ALsuperCat

Cat --> Mammal
Mammal --> Animal

classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,ALsuperCat,Cat cat;
class ALMammal,Mammal,ALsuperMammal mammal;
class ALAnimal,Animal,ALsuperAnimal animal;

Aan de hand van de kleuren kan je snel zien dat de overervingsrelatie links en rechts inderdaad omgekeerd verlopen.

Onthoud

Het type ArrayList<? super Mammal> staat tegelijk voor de types ArrayList<Mammal>, ArrayList<Animal>, ArrayList<Object>, en elk ander type dat een superklasse (of interface) is van Mammal.

Covariantie of contravariantie: PECS

Als we covariantie en contravariantie combineren, krijgen we volgend beeld (we focussen op de extends- en super-relatie vanaf Mammal):

graph BT
ALAnimal["ArrayList#lt;Animal>"]
ALMammal["ArrayList#lt;Mammal>"]
ALCat["ArrayList#lt;Cat>"]

ALsuperMammal["ArrayList#lt;? super Mammal>"]
ALextendsMammal["ArrayList#lt;? extends Mammal>"]

ALMammal --> ALextendsMammal
ALCat --> ALextendsMammal
ALAnimal --> ALsuperMammal
ALMammal --> ALsuperMammal

Cat --> Mammal
Mammal --> Animal

classDef cat fill:#f99,stroke:#333,stroke-width:4px;
classDef mammal fill:#9f9,stroke:#333,stroke-width:4px;
classDef animal fill:#99f,stroke:#333,stroke-width:4px;
class ALCat,Cat cat;
class ALMammal,Mammal,ALsuperMammal,ALextendsMammal mammal;
class ALAnimal,Animal animal;

Hier zien we dat ArrayList<? extends Mammal> (covariant) als subtypes ArrayList<Mammal> en ArrayList<Cat> heeft. Het contravariante ArrayList<? super Mammal> heeft óók ArrayList<Mammal> als subtype, maar ook ArrayList<Animal>.

Hoe weet je nu wanneer je wat gebruikt als type voor een parameter? Wanneer kies je <? extends T>, en wanneer <? super T>? Een goede vuistregel is het acroniem PECS, wat staat voor Producer Extends, Consumer Super. Dus:

Wanneer het object gebruikt wordt als een producent van T’s (met andere woorden, het object is een levancier van T-objecten voor jouw code, die ze vervolgens gebruikt), gebruik je <? extends T>. Dat is logisch: als jouw code met aangeleverde T’s omkan, dan kan jouw code ook om met de aanlevering van een subklasse van T (basisprincipe objectgeoriënteerd programmeren).
Wanneer het object gebruikt wordt als een consument van T’s (met andere woorden, het neemt T-objecten aan van jouw code), gebruik je <? super T>. Ook dat is logisch: een object dat beweert om te kunnen met elke superklasse van T moet zeker overweg kunnen met een T die jouw code aanlevert.
Wanneer het object zowel als consument als als producent gebruikt wordt, gebruik je gewoon <T> (dus geen co- of contra-variantie). Er is dan weinig tot geen flexibiliteit meer in het type.

Een voorbeeld om PECS toe te passen: we willen een methode copyFromTo die zo flexibel mogelijk is, om elementen uit een lijst van zoogdieren te kopiëren naar een andere lijst.

void copyMammalsFromTo(
    ??? source,
    ??? target) {
  for (Mammal m : source) {
    target.add(m);
  }
}

De source-lijst is de producent: daaruit halen we Mammal-objecten op. Daar gebruiken we dus extends:

void copyMammalsFromTo(
    List<? extends Mammal> source,
    ??? target) {
  for (Mammal m : source) {
    target.add(m);
  }
}

De target-lijst is de consument: daar sturen we Mammal-objecten naartoe. Daar gebruiken we dus super:

void copyMammalsFromTo(
    List<? extends Mammal> source,
    List<? super Mammal> target) {
  for (Mammal m : source) {
    target.add(m);
  }
}

Met deze methode kunnen we nu alle zinvolle operaties uitvoeren, terwijl de zinloze operaties tegengehouden worden door de compiler:

ArrayList<Cat> cats = /* ... */
ArrayList<Dog> dogs = /* ... */
ArrayList<Bird> birds = /* ... */
ArrayList<Mammal> mammals = /* ... */
ArrayList<Animal> animals = /* ... */

copyMammalsFromTo(cats, animals); // OK 👍
copyMammalsFromTo(cats, mammals); // OK 👍
copyMammalsFromTo(cats, cats); // OK 👍

copyMammalsFromTo(mammals, animals); // OK 👍

copyMammalsFromTo(cats, dogs);
// compiler error (Dog is geen supertype van Mammal) 👍

copyMammalsFromTo(birds, animals);
// compiler error (Bird is geen subtype van Mammal) 👍

Merk op dat het type Mammal in onze laatste versie van copyMammalsFromTo hierboven eigenlijk onnodig is. We kunnen de methode nog verder veralgemenen door er een generische methode van te maken, die werkt voor alle lijsten (niet enkel lijsten van zoogdieren):

<T> void copyFromTo(
    List<? extends T> source,
    List<? super T> target) {
  for (T element : source) {
    target.add(element);
  }
}

Met deze versie kunnen we nu bijvoorbeeld ook Birds kopiëren naar een lijst van dieren:

copyFromTo(birds, animals); // OK 👍

Opmerking

Wanneer een parameter zowel een producent (co-variant) als een consument (contra-variant) is, gebruik je geen wildcards. De generische parameter heet dan invariant. Bijvoorbeeld:

public static <T> void reverse(List<T> list) {
    int left = 0;
    int right = list.size() - 1;
    while (left < right) {
        // Producent (get)
        T temp = list.get(left);
        // Consumer (set)
        list.set(left, list.get(right));
        list.set(right, temp);
        left++;
        right--;
    }
}

Arrays en type erasure

In tegenstelling tot ArrayLists (en andere generische types), beschouwt Java arrays wél altijd als covariant. Dat betekent dat Cat[] een subtype is van Animal[]. Volgende code compileert dus (maar gooit een uitzondering bij het uitvoeren):

Animal[] cats = new Cat[2];
cats[0] = new Dog(); // compileert, maar faalt tijdens het uitvoeren

De reden hiervoor is, in het kort, dat informatie over generics gewist wordt bij het compileren van de code. Dit heet type erasure. In de gecompileerde code is een ArrayList<Animal> en ArrayList<Cat> dus exact hetzelfde. Er kan dus, tijdens de uitvoering, niet gecontroleerd worden of je steeds het juiste type gebruikt. Daarom moet de compiler dat doen, en die neemt het zekere voor het onzekere: alles wat mogelijk fout zou kunnen aflopen, wordt geweigerd.

Bij arrays wordt er wel type-informatie bijgehouden na het compileren, en kan dus tijdens de uitvoering nog gecontroleerd worden of je geen elementen met een ongeldig type toevoegt. De compiler hoeft het niet af te dwingen — maar het wordt wel nog steeds gecontroleerd tijdens de uitvoering, en kan leiden tot een exception.

Aandachtspunten

Enkel bij generische types!

Tenslotte nog een opmerking (op basis van vaak gemaakte fouten op examens). Co- en contra-variantie (extends, super, en wildcards dus) zijn enkel van toepassing op generische types. Alles wat we hierboven gezien hebben is dus enkel nuttig op plaatsen waar je een generisch type (List<T>, Food<T>, …) gebruikt voor een parameter, terugkeertype, variabele, …. Dergelijke types kan je met behulp van co-/contra-variantie en wildcards verrijken tot bijvoorbeeld List<? extends T>, Food<? super T>, … Maar je kan deze constructies niet gebruiken op plaatsen waar een gewoon type verwacht wordt, bijvoorbeeld bij een parameter of terugkeertype. Onderstaande regels code zijn dus allemaal ongeldig:

public void pet(? extends Mammal mammal) { ... } // ONGELDIG! ❌
public void pet(<? extends Mammal> mammal) { ... } // ONGELDIG! ❌
public void pet(<? super Cat> mammal) { ... } // ONGELDIG! ❌

Schrijf in dat geval gewoon

public void pet(Mammal mammal) { ... }

Deze methode kan óók al opgeroepen worden met een Cat-object, Dog-object, of elk ander type Mammal als argument. Je hebt hier geen co- of contra-variantie van generische types nodig; je maakt gewoon gebruik van overerving uit objectgeoriënteerd programmeren.

Onthoud

Wildcards (?), co-variantie (? extends) en contra-variantie (? super) zijn enkel van toepassing bij generische types! Je kan ze dus niet gebruiken als een op zichzelf staand type. Je kan ze ook niet gebruiken bij de definitie van een nieuwe generische parameter (voor een klasse of methode), maar enkel bij het gebruik ervan.

Bounds vs. co-/contravariantie en wildcards

Tot slot is het nuttig om nog eens te benadrukken dat er een verschil is tussen het begrenzen van een generische parameter (met extends) enerzijds, en het gebruik van co-variantie, contra-variantie en wildcards (? extends T, ? super T) anderzijds. Het feit dat extends in beide gevallen gebruikt wordt, kan misschien tot wat verwarring leiden.

Een begrenzing (via <T extends SomeClass>) beperkt welke types geldige waarden zijn voor de type-parameter T. Dus: elke keer wanneer je een concreet type wil meegeven in de plaats van T moet dat type voldoen aan bepaalde eisen. Je kan zo’n begrenzing enkel aangeven op de plaats waar je een nieuwe generische parameter (T) introduceert (dus bij een nieuwe klasse-definitie of methode-definitie). Bijvoorbeeld: class Food<T extends Animal> laat later enkel toe om Food<X> te schrijven als type wanneer X ook een subtype is van Animal.

Door co- en contra-variantie (met <? extends X> en <? super X>) te gebruiken verbreed je de toegelaten types. Een methode-parameter met als type Food<? extends Animal> laat een Food<Animal> toe als argument, maar ook een Food<Cat> of Food<Dog>. Omgekeerd zal een parameter met als type Food<? super Cat> een Food<Cat> toelaten, maar ook een Food<Animal>. Er wordt in beide gevallen dus meer toegelaten, wat meer flexibiliteit biedt.

Je kan co- en contravariantie toepassen op elke plaats waar je een generisch type gebruikt (en waar dat gepast is volgens de PECS regels). Het kan dus perfect zijn dat je de ene keer in je code eens Food<Cat> gebruikt, ergens anders Food<? extends Cat>, en nog ergens anders Food<? super Cat>. Bij begrenzing is dat niet zo; dat legt de grenzen eenmalig vast, en die moeten overal gerespecteerd worden waar het generisch type gebruikt wordt.

Onthoud

Een begrenzing (T extends X) is een eenmalige beperking op het type dat gebruikt kan worden als waarden voor een nieuw geïntroduceerde generische parameter. Dit kan enkel voorkomen in de definitie van een nieuwe generische parameter (bij een generische klasse of methode).

Co-en contravariantie (? extends X, ? super X) met wildcard ? versoepelen de types die aanvaard worden door de compiler. Ze komen enkel voor op plaatsen waar een generisch type gebruikt wordt.

Arrays met generisch type

Als je een array wil maken van een generisch type, laat de Java-compiler dat niet toe:

class MyClass<T> {
  private T[] array;
  public MyClass() {
    array = new T[10]; // <-- niet toegelaten ☹️
  }
}

De reden is opnieuw type erasure. Aangezien arrays covariant zijn, moet tijdens de uitvoering gecontroleerd kunnen worden of objecten die in de array terechtkomen een geschikt type hebben. Aangezien generische parameters verwijderd worden door de compiler, kan dat niet.

Een oplossing voor bovenstaand probleem is om een cast toe te voegen. Met een @SuppressWarning annotatie kan je de waarschuwing die door de compiler gegeven wordt negeren.

class MyClass<T> {
  private T[] array;

  @SuppressWarning("unchecked")
  public MyClass() {
    array = (T[])new Object[10]; // <-- ok! 👍
  }
}

Het is natuurlijk ook mogelijk om gewoon een ArrayList te gebruiken; dan heb je dit probleem niet.

class MyClass<T> {
  private ArrayList<T> list;

  public MyClass() {
    list = new ArrayList<>(); // <-- ok! 👍
  }
}

Oefeningen

Voor de tests maken we gebruik van assertJ.

Maybe-klasse

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();
}

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);
  }
}

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();
}

(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)?

Info

Java bevat een ingebouwd type gelijkaardig aan de Maybe-klasse uit deze oefening, namelijk Optional<T>.

Repository

Schrijf een generische klasse Repository die een repository van objecten voorstelt. De objecten hebben ook een ID. Zowel het type van objecten als het type van de ID moeten generische parameters zijn.

Definieer en implementeer volgende methodes (maak gebruik van een ArrayList):

add(id, obj): toevoegen van een object
findById(id): opvragen van een object aan de hand van de id
findAll(): opvragen van alle objecten in de repository
update(id, obj): vervangen van een object met gegeven id door het meegegeven object
remove(id): verwijderen van een object aan de hand van een id

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);
}

Subtyping: voertuigen

Vetrek van volgende klasse-hiërarchie en zeg van elk van volgende lijnen code of ze toegelaten worden door de Java compiler:

graph BT
Bike --> Vehicle
Motorized --> Vehicle
Car --> Motorized
Plane --> Motorized

/* 1 */  Motorized myCar = new Car();
/* 2 */  Vehicle yourPlane = new Plane();
/* 3 */  Collection<Vehicle> vehicles = new ArrayList<Vehicle>();
/* 4 */  vehicles.add(myCar);
/* 5 */  List<Car> cars = new ArrayList<Car>();
/* 6 */  List<Vehicle> carsAsVehicles = cars;

Antwoord

Alles behalve lijn 6 is toegelaten.

Covariantie

Maak een schema met de overervingsrelaties tussen

List<Cat>
List<? extends Cat>
ArrayList<Cat>
ArrayList<? extends Cat>
List<Animal>
List<? extends Animal>
ArrayList<Animal>
ArrayList<? extends Animal>

Antwoord

graph BT
ALC["ArrayList#lt;Cat>"] --> LC["List#lt;Cat>"]
ALC --> ALeC["ArrayList#lt;? extends Cat>"]
LC --> LeC["List#lt;? extends Cat>"]
ALeC --> LeC
ALeC --> ALeA["ArrayList#lt;? extends Animal>"]
ALA["ArrayList#lt;Animal>"] --> ALeA
ALA --> LA["List#lt;Animal>"]
LeC --> LeA["List#lt;? extends Animal>"]
ALeA --> LeA
LA --> LeA

ArrayList<Cat> is een subtype van List<Cat> en van ArrayList<? extends Cat>.
List<Cat> is een subtype van List<? extends Cat>
ArrayList<? extends Cat> is een subtype van List<? extends Cat> en van ArrayList<? extends Animal>
ArrayList<Animal> is een subtype van ArrayList<? extends Animal> en List<Animal>
List<? extends Cat>, ArrayList<? extends Animal> en List<Animal> zijn alledrie subtypes van List<? extends Animal>

Shop

Maak een klasse Shop die een winkel voorstelt die items (subklasse van StockItem) aankoopt. Een Shop-object wordt geparametriseerd met het type items dat aangekocht kan worden. We beschouwen hier Fruit en Electronics; daarmee kunnen we dus een fruitwinkel (Shop<Fruit>) en elektronica-winkel (Shop<Electronics>) maken.

Shop heeft twee methodes:

buy, die een lijst van items toevoegt aan de stock;
addStockToInventory, die de lijst van items in stock toevoegt aan de meegegeven inventaris-lijst.

Voor het fruit maak je een abstracte klasse Fruit, en subklassen Apple en Orange. Maak daarnaast nog een abstracte klasse Electronics, met als subklasse Smartphone.

Zorg dat onderstaande code (ongewijzigd) compileert en dat de test slaagt:

@Test
public void testGenerics() {
  Shop<Fruit> fruitShop = new Shop<>();
  Shop<Electronics> electronicsShop = new Shop<>();

  List<Apple> apples = List.of(new Apple(), new Apple());
  List<Fruit> oranges = List.of(new Orange(), new Orange(), new Orange());

  List<Smartphone> phones = List.of(new Smartphone(), new Smartphone());

  fruitShop.buy(apples);
  fruitShop.buy(oranges);

  electronicsShop.buy(phones);

  List<StockItem> inventory = new ArrayList<>();
  fruitShop.addStockToInventory(inventory);
  Assertions.assertThat(inventory).hasSize(5);

  electronicsShop.addStockToInventory(inventory);

  Assertions.assertThat(inventory).hasSize(7);
}

Functie compositie

Java bevat een ingebouwde interface java.util.function.Function<T, R>, wat een functie voorstelt met één parameter van type T, en een resultaat van type R. Deze interface voorziet 1 methode R apply(T value) om de functie uit te voeren.

Schrijf nu een generische methode compose die twee functie-objecten als parameters heeft, en als resultaat een nieuwe functie teruggeeft die de compositie voorstelt: eerst wordt de eerste functie uitgevoerd, en dan wordt de tweede functie uitgevoerd op het resultaat van de eerste.

Dus: voor functies

Function<A, B> f1 = ...
Function<B, C> f2 = ...

moet compose(f1, f2) een Function<A, C> teruggeven, die als resultaat f2.apply(f1.apply(a)) teruggeeft.

Pas de PECS-regel toe om ook functies te kunnen samenstellen die niet exact overeenkomen qua type. Bijvoorbeeld, volgende code moet compileren en de test moet slagen:

interface Ingredient {}
record Fruit() implements Ingredient {}
record PeeledFruit(Fruit fruit) implements Ingredient {}
record Chopped(Ingredient food) implements Ingredient {}

@Test
public void testCompose() {
    Function<Fruit, PeeledFruit> peelFruit = (var fruit) -> new PeeledFruit(fruit);
    Function<Ingredient, Chopped> chopIngredient = (var food) -> new Chopped(food);

    var makeFruitSalad = compose(peelFruit, chopIngredient);

    assertThat(makeFruitSalad.apply(new Fruit())).isEqualTo(new Chopped(new PeeledFruit(new Fruit())));
}

Game engine

Oud-examenvraag

Dit is een oud-examenvraag.

Vul de types en generische parameters aan op de 7 genummerde plaatsen zodat onderstaande code en main-methode compileert (behalve de laatste regel van de main-methode) en voldaan is aan volgende voorwaarden:

Elk actie-type kan enkel uitgevoerd worden door een bepaald karakter-type. Bijvoorbeeld: een FightAction kan enkel uitgevoerd worden door een karakter dat CanFight implementeert.
doAction mag enkel opgeroepen worden met een actie die uitgevoerd kan worden door alle karakters in de meegegeven lijst.

Als er op een bepaalde plaats geen type of generische parameter nodig is, vul je $\emptyset$ in.

Verklaar je keuze voor de combinatie van (5), (6), en (7).

interface Character {}
interface CanFight extends Character {}
record Warrior() implements CanFight {}
record Knight() implements CanFight {}
record Wizard() implements Character {}
interface Action<___/* 1 */___> {
    void execute(___/* 2 */____ character);
}
class FightAction implements Action<___/* 3 */_____> {
    @Override
    public void execute(___/* 4 */______ character) {
        System.out.println(character + " fights!");
    }
}
class GameEngine {
    public <___/* 5 */______> void doAction(
            List<___/* 6 */____> characters,
            Action<___/* 7 */____> action) {
        for (var character : characters) {
            action.execute(character);
        }
    }
}
public static void main(String[] args) {
    var engine = new GameEngine();
    Action<CanFight> fight = new FightAction();

    List<Warrior> warriors = List.of(new Warrior(), new Warrior());
    engine.doAction(warriors, fight);

    List<Wizard> wizards = List.of(new Wizard());
    engine.doAction(wizards, fight); // deze regel mag NIET compileren
}

Antwoord

1: C extends Character : acties kunnen enkel uitgevoerd worden door subtypes van Character
2: C: C is het type van Character dat de actie zal uitvoeren
3: CanFight: FightAction is enkel mogelijk voor characters die CanFight implementeren
4: CanFight: aangezien de generische paremeter C van superinterface Action geinitialiseerd werd met CanFight, moet hier ook CanFight gebruikt worden.
5: T extends Character: we noemen T het type van de objecten in de meegeven lijst; we hebben hier een begrenzing nodig (want we willen enkel subtypes van Character toelaten)
6: T: lijst van T’s, zoals verondersteld in 5
7: ? super T: de meegegeven actie moet een actie zijn die door alle T’s uitgevoerd kan worden (dus door T of een van de supertypes van T). Redenering met behulp van PECS: de meegegeven actie gebruikt/consumeert het character, dus super.

Alternatieve keuze voor 5/6/7:

5: T extends Character: we noemen T het type dat bij de actie hoort; we hebben hier een begrenzing nodig (want we willen enkel subtypes van Character toelaten)
6: ? extends T: lijst van T’s of subtypes ervan. Redenering met behulp van PECS: de lijst levert/produceert de characters, dus extends.
7: T: het type van de actie, zoals verondersteld in 5

Animal food

Dit is een uitdagende oefening, voor als je je kennis over generics echt wil testen.

Voeg generics (met grenzen/bounds) toe aan de code hieronder, zodat de code (behalve de laatste regel) compileert, en de compiler enkel toelaat om kattenvoer te geven aan katten, en hondenvoer aan honden:

public class AnimalFood {
    static class Animal {
        public void eat(Food food) {
            System.out.println(this.getClass().getSimpleName() + " says 'Yummie!'");
        }
    }
    static class Mammal extends Animal {
        public void drink(Milk milk) {
            this.eat(milk);
        }
    }
    static class Cat extends Mammal {}
    static class Kitten extends Cat {}
    static class Dog extends Mammal {}
    static class Food {}
    static class Milk extends Food {}

    static class Main {
        public static void main(String[] args) {
            Food catFood = new Food();
            Milk catMilk = new Milk();
            Food dogFood = new Food();
            Milk dogMilk = new Milk();

            Cat cat = new Cat();
            Dog dog = new Dog();
            Kitten kitten = new Kitten();

            cat.eat(catFood); // OK 👍
            cat.drink(catMilk); // OK 👍
            dog.eat(dogFood); // OK 👍
            dog.drink(dogMilk); // OK 👍
            kitten.eat(catFood); // OK 👍
            kitten.drink(catMilk); // OK 👍

            cat.eat(dogFood); // <- moet een compiler error geven! ❌
            kitten.eat(dogFood); // <- moet een compiler error geven! ❌
            kitten.drink(dogMilk); // <- moet een compiler error geven! ❌
        }
    }
}

(Hint: Begin met het type Food te parametriseren met een generische parameter die het Animal-type voorstelt dat dit voedsel eet.)

Self-type

Dit is een uitdagende oefening, voor als je je kennis over generics echt wil testen.

Heb je je al eens afgevraagd hoe assertThat(obj) uit AssertJ werkt? Afhankelijk van het type van obj dat je meegeeft, worden er andere assertions beschikbaar die door de compiler aanvaard worden:

// een List<String>
List<String> someListOfStrings = List.of("hello", "there", "how", "are", "you");
assertThat(someListOfStrings).isNotNull().hasSize(5).containsItem("hello");

// een String
String someString = "hello";
assertThat(someString).isNotNull().isEqualToIgnoringCase("hello");

// een Integer
int someInteger = 4;
assertThat(someInteger).isNotNull().isGreaterThan(4);

assertThat(someInteger).isNotNull().isEqualToIgnoringCase("hello"); // <= compileert niet ❌

Sommige assertions (zoals isNotNull) zijn echter generiek, en wil je slechts op 1 plaats implementeren. Probeer zelf een assertThat-methode te schrijven die werkt zoals bovenstaande, maar waar isNotNull slechts op 1 plaats geïmplementeerd is. De assertThat-methode moet een Assertion-object teruggeven, waarop de verschillende methodes gedefinieerd zijn afhankelijk van het type dat meegegeven wordt aan assertThat.

Hint 1: maak verschillende klassen, bijvoorbeeld ListAssertion, StringAssertion, IntegerAssertion die de type-specifieke methodes bevatten. Begin met isNotNull toe te voegen aan elk van die klassen (dus door de implementatie te kopiëren).
Hint 2: in een zogenaamde ‘fluent interface’ geeft elke operatie zoals isNotNull en hasSize het this-object op het einde terug (return this), zodat je oproepen na elkaar kan doen. Bijvoorbeeld .isNotNull().hasSize(5).
Hint 3: maak nu een abstracte klasse GenericAssertion die isNotNull bevat, en waarvan de andere assertions overerven. Verwijder de andere implementaties van isNotNull.
Hint 4: In isNotNull is geen informatie beschikbaar over het type dat gebruikt moet worden als terugkeertype van isNotNull. assertThat(someString).isNotNull() moet bijvoorbeeld opnieuw een StringAssertion teruggeven. Dat kan je oplossen met generics, en een abstracte methode die het juiste object teruggeeft.
Hint 5: Je zal een zogenaamd ‘self-type’ moeten gebruiken. Dat is een generische parameter die wijst naar de (sub)klasse zelf.
Hint 6: op deze pagina wordt uitgelegd hoe AssertJ dit doet. Probeer eerst zelf, zonder dit te lezen!

7.3 Collections

In andere programmeertalen

De concepten in andere programmeertalen die het dichtst aanleunen bij Java collections zijn

de Standard Template Library (STL) in C++
enkele ingebouwde types, alsook de collections module in Python
de collecties in System.Collections.Generic in C#

Totnogtoe hebben we enkel gewerkt met een Java array (vaste grootte), en met ArrayList (kan groter of kleiner worden). In dit hoofdstuk kijken we in meer detail naar ArrayList, en behandelen we ook verschillende andere collectie-types in Java. De meeste van die types vind je ook (soms onder een andere naam) terug in andere programmeertalen.

Je kan je afvragen waarom we andere collectie-types nodig hebben; uiteindelijk kan je (met genoeg werk) alles toch implementeren met een ArrayList? Dat klopt, maar de collectie-types verschillen in welke operaties snel zijn, en welke meer tijd vragen. Om dat wat preciezer te maken, kijken we eerst even naar de notie van tijdscomplexiteit.

Andere collectie-API’s

Behalve de Java Collections API zijn er ook externe bibliotheken met collectie-implementaties die je (bijvoorbeeld via Gradle) kan gebruiken in je projecten. De twee meest gekende voorbeelden zijn

Google Guava, en bijhorende documentatie
Apache Commons, en bijhorende documentatie

7.3.1 Tijdscomplexiteit

Tijdscomplexiteit is een essentieel begrip bij de analyse van algoritmes (en bijhorende gegevensstructuren). Met tijdscomplexiteit wordt gekwantificeerd hoe snel een algoritme zijn invoer verwerkt. Het is dus een eigenschap van een (implementatie van een) algoritme, naast bijvoorbeeld de correctheid en leesbaarheid van dat algoritme.

In tegenstelling tot wat je misschien zou denken, wordt er bij tijdscomplexiteit niet gekeken naar de tijd (in seconden). In plaats daarvan wordt het totale aantal operaties dat uitgevoerd wordt geteld. Daarenboven worden niet alle operaties geteld; er wordt een keuze gemaakt voor een verzameling basisoperaties. Het voordeel hiervan is dat, in tegenstelling tot de reële tijd, het aantal operaties niet afhankelijk is van de snelheid van de processor. Bijvoorbeeld, bij sorteeralgoritmes wordt soms de vergelijking tussen twee elementen als (enige) basisoperatie gebruikt, of soms elke operatie die een element uit de te sorteren rij opvraagt of aanpast. Het totale aantal uitgevoerde basisoperaties is dan (bij benadering) een maat voor de uitvoeringstijd van het algoritme, aangezien elke basisoperatie een bepaalde reële uitvoeringstijd heeft op een machine.

Voor de meeste algoritmes zal een grotere invoer leiden tot meer uit te voeren operaties (denk aan een lus die vaker herhaald wordt). Grotere invoer leidt dus tot meer operaties, en daardoor tot een langere uitvoeringstijd. Zo is het bijvoorbeeld niet meer dan logisch dat een hele lange lijst sorteren langer duurt dan een heel korte lijst sorteren. De grootte van de invoer wordt met $n$ aangeduid; de tijdscomplexiteit van het algoritme in functie van de invoergrootte met de functie $T(n)$.

Best, worst, average case

We maken bij tijdscomplexiteit onderscheid tussen:

Best case: een invoer (van een bepaalde grootte $ n $) die leidt tot de best mogelijke (kortste) uitvoeringstijd. Bijvoorbeeld, sommige sorteeralgoritmes doen minder werk (en zijn dus snel klaar) als de lijst al gesorteerd blijkt te zijn.
Worst case: een invoer (van een bepaalde grootte $ n $) die leidt tot de slechtst mogelijke (langste) uitvoeringstijd. Bijvoorbeeld, sommige sorteeralgoritmes hebben erg veel last met een omgekeerd gesorteerde lijst: ze moeten dan heel veel operaties uitvoeren om de lijst gesorteerd te krijgen.
Average case: een invoer (van een bepaalde grootte $ n $) waarover we niets weten en geen veronderstellingen kunnen of willen maken. Bijvoorbeeld, voor sorteeralgoritmes kan dit een willekeurige volgorde (permutatie) van de elementen zijn, zonder speciale structuur. De uitvoeringstijd in de average case zal ergens tussen die van de worst case en best case liggen.

Worst- en best-case zijn in veel gevallen redelijk eenvoudig te bepalen. De average case wordt vaak complexer.

Belangrijk om te onthouden is dat worst/best/average case dus niet gaan over een kleinere of grotere invoer, maar wel over hoe die invoer eruit ziet of gestructureerd is. Bijvoorbeeld, de best case voor een sorteeralgoritme is niet een lege lijst. Hoewel er in dat geval amper operaties uitgevoerd moeten worden, zegt dat niet veel: het is immers niet meer dan logisch dat een kleinere invoer ook minder tijd vraagt. Wat we wel willen weten is bijvoorbeeld wélke lijst (van alle mogelijke lijsten van lengte $n=1000$, bijvoorbeeld) het langst duurt om te sorteren met dat bepaald algoritme.

Voorbeeld: selection sort

Hieronder vind je een voorbeeld-implementatie van selection sort, een eenvoudig sorteeralgoritme. In elke iteratie van de lus wordt het reeds gesorteerde deel van de lijst (dat is het deel vóór index startUnsorted) uitgebreid met 1 element, namelijk het kleinste nog niet gesorteerde element. Dat element wordt gezocht met de hulpfunctie indexOfSmallest, dewelke de index van het kleinste element in de lijst teruggeeft vanaf een bepaalde index start. Dat kleinste element wordt vervolgens omgewisseld met het element op plaats startUnsorted. Dat zoeken en omwisselen blijven we doen tot de hele lijst gesorteerd is.

Bijvoorbeeld, in de vierde iteratie van de lus ziet de situatie er als volgt uit net voordat de swap-operatie uitgevoerd wordt:

block-beta
  columns 1
  block:before
    columns 8
    e0["A"] e1["B"] e2["C"] e3["H"] e4["F"] e5["G"] e6["E"] e7["D"]
    idx0["0"] idx1["1"] idx2["2"] idx3["startUnsorted=3"] idx4["4"] idx5["5"] idx6["6"] idx7["indexSmallest=7"]
  end

  classDef ok fill:#6c6,stroke:#393,color:#fff
  classDef min fill:#66c,stroke:#339,color:#fff
  classDef curr stroke-width:3
  classDef index fill:none,stroke:none,color:black,font-size:0.7rem
  class e0,e1,e2 ok
  class e7 min
  class e3 curr
  class idx0,idx1,idx2,idx3,idx4,idx5,idx6,idx7 index

En in de vijfde iteratie als volgt:

block-beta
  columns 1
  block:before
    columns 8
    e0["A"] e1["B"] e2["C"] e3["D"] e4["F"] e5["G"] e6["E"] e7["H"]
    idx0["0"] idx1["1"] idx2["2"] idx3["3"] idx4["startUnsorted=4"] idx5["5"] idx6["indexSmallest=6"] idx7["7"]
  end

  classDef ok fill:#6c6,stroke:#393,color:#fff
  classDef min fill:#66c,stroke:#339,color:#fff
  classDef curr stroke-width:3
  classDef index fill:none,stroke:none,color:black,font-size:0.7rem
  class e0,e1,e2,e3 ok
  class e6 min
  class e4 curr
  class idx0,idx1,idx2,idx3,idx4,idx5,idx6,idx7 index

public static <E extends Comparable<E>> void selectionSort(ArrayList<E> list) {
    for (int startUnsorted = 0; startUnsorted < list.size(); startUnsorted++) {
        int indexSmallest = indexOfSmallest(list, startUnsorted);
        Collections.swap(list, startUnsorted, indexSmallest);
    }
}
private static <E extends Comparable<E>> int indexOfSmallest(List<E> list, int start) {
    if (start >= list.size()) return -1;
    int indexSmallestSoFar = start;
    E smallestSoFar = list.get(start);
    for (int i = start+1; i < list.size(); i++) {
        E candidate = list.get(i);
        if (candidate.compareTo(smallestSoFar) < 0) {
            indexSmallestSoFar = i;
            smallestSoFar = candidate;
        }
    }
    return indexSmallestSoFar;
}

Note

Merk op hoe de functie het generische type <E extends Comparable<E>> gebruikt. Dat legt op dat de elementen (aangeduid met generische type E) bovendien de interface Comparable<E> moeten implementeren, waardoor ze met elkaar vergeleken kunnen worden via de compareTo-methode (gebruikt in indexOfSmallest). Ingebouwde Java-klassen zoals String, Integer, etc. implementeren Comparable, waardoor deze methode gebruikt kan worden om lijsten van Strings te sorteren. Als je deze methode wil gebruiken om objecten van je eigen klasse (bijvoorbeeld Person) te sorteren, zal je Person-klasse ook de interface Comparable moeten implementeren om aan te geven hoe personen met elkaar vergeleken moeten worden.

Basisoperaties tellen

Afhankelijk van het type algoritme kunnen we verschillende operaties als basisoperatie kiezen. Als we voor selection sort als enige basisoperatie de methode compareTo nemen, dan zal voor een lijst van lengte $n$:

tijdens de eerste iteratie het element op index 0 vergeleken worden met alle volgende $n-1$ elementen;
tijdens de tweede iteratie het element op index 1 vergeleken worden met alle volgende $n-2$ elementen;
etc.
tijdens iteratie $n-1$ het element op index $n-2$ vergeleken worden met het laatste element;
tijdens iteratie $n$ het element op index $n-1$ met geen enkel element vergeleken worden.

Er gebeuren in totaal dus $ T(n) = (n-1) + (n-2) + \ldots + 1 + 0 = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} $ vergelijkingen van elementen via compareTo.

Daaruit kunnen we ook afleiden dat, als we de invoer 10 keer groter maken, we $ \frac{T(10n)}{T(n)} = \frac{(10n)^2/2-10n/2}{n^2/2-n/2} = 100 + 90/(n-1) $ keer zoveel operaties uitvoeren. Als $ n $ voldoende groot is, zal de lijst 10 keer langer maken dus neerkomen op ongeveer 100 keer zoveel werk, en zal selection sort dus 100 keer trager zijn.

In de rest van dit hoofdstuk over datastructuren gaan we verder voornamelijk werken met één specifieke basisoperatie, namelijk het aantal keer dat een element uit het geheugen (of uit een array) bezocht (uitgelezen) worden.

Grote O-notatie

We kunnen het aantal basisoperaties exact berekenen, zoals hierboven voor selection sort. Dat is echter veel werk, en vaak hebben we dergelijke precisie niet nodig. Voor tijdscomplexiteit wordt er daarom veelal gebruik gemaakt van grote O-notatie. Dat is, informeel gezegd, de snelst stijgende term, zonder constanten. In het voorbeeld van selection sort hierboven is de snelst stijgende term van $ T(n) $ de kwadratische term. We noteren dat als $ T(n) \in \mathcal{O}(n^2) $ of soms gewoon $ T(n) = \mathcal{O}(n^2) $

Formeel betekent $ T(n) \in \mathcal{O}(f(n)) $ dat $ \exists c, n_0.\ \forall n > n_0.\ T(n)/f(n) \leq c $. Met andere woorden, zodra $ n $ groot genoeg is (groter dan een bepaalde $n_0$), is de verhouding $T(n)/f(n)$ begrensd door een constante, wat uitdrukt dat $T(n)$ niet sneller stijgt dan $f(n)$.

$ \mathcal{O}(n^2) $ is de complexiteitsklasse (de verzameling van alle functies die niet sneller dan kwadratisch stijgen), en we zeggen dat selection sort een kwadratische tijdscomplexiteit heeft.

Note

Er zijn nog andere notaties die vaak gebruikt worden in de context van tijdscomplexiteit, waaronder grote theta ($ \Theta $), grote omega ($ \Omega $), en tilde (~). Deze hebben allen een andere formele definitie. In de dagelijkse (informele) praktijk wordt vaak grote O gebruikt, zelfs als eigenlijk een van deze andere bedoeld wordt.

Vaak voorkomende complexiteitsklassen

Hieronder vind je een tabel met vaak voorkomende complexiteitsklassen. In de laatste kolom vind je de tijd die zo’n algoritme doet over een invoer van grootte $n=1000$, in de veronderstelling dat het een probleem van grootte $n=100$ kan oplossen in 1 milliseconde.

Klasse	Naam	$ T(1000) $ (als $ T(100) = 1 \textrm{ms} $)
$ \mathcal{O}(1) $	Constant	$1\ \textrm{ms} $
$ \mathcal{O}(\log n) $	Logaritmisch	$1.5\ \textrm{ms} $
$ \mathcal{O}(n) $	Lineair	$10\ \textrm{ms} $
$ \mathcal{O}(n \log n) $	Linearitmisch	$15\ \textrm{ms} $
$ \mathcal{O}(n^2) $	Kwadratisch	$100\ \textrm{ms} $
$ \mathcal{O}(n^3) $	Kubisch	$1000\ \textrm{ms} $
$ \mathcal{O}(2^n) $	Exponentieel	$ 2^{900}\ \textrm{ms} $ = $ 2.7 \times 10^{260}\ \textrm{jaar}$
$ \mathcal{O}(n!) $	Factorieel	$ \frac{1000!}{100!}\ \textrm{ms} $ = $ 1.4 \times 10^{2399}\ \textrm{jaar}$

Je ziet dat de constante tot en met linearitmische complexiteitsklassen zeer gunstig zijn. Kwadratisch en kubisch zijn te vermijden, omdat de tijd veel sneller toeneemt dan de grootte van de invoer. Exponentiële en factoriële algoritmes tenslotte zijn dramatisch en schalen bijzonder slecht naar grotere problemen. Backtracking-algoritmes (zie later) vallen vaak in deze laatste klassen, en kunnen dus zeer inefficiënt zijn voor grotere problemen.

We zullen deze tijdscomplexiteitsklassen gebruiken om (operaties op) datastructuren te vergelijken.

Onthoud

Tijdscomplexiteit met grote O geeft bij benadering aan hoe het aantal operaties dat een algoritme moet uitvoeren stijgt wanneer de grootte van de invoer stijgt.

7.3.2 Java Collections API

We kunnen nu de Java Collections-API verkennen. Deze API bestaat uit

interfaces (bv. Iterable, Collection, List, Set, SortedSet, Queue, Deque, Map, SortedMap, en NavigableMap)
implementaties van die interface (bv. ArrayList, LinkedList, Vector, Stack, ArrayDeque, PriorityQueue, HashSet, LinkedHashSet, TreeSet, en TreeMap)
algoritmes voor veel voorkomende operaties (bv. shuffle, sort, swap, reverse, …)

Je vindt een overzicht van de hele API op deze pagina.

We beginnen bij de basisinterface: Iterable.

Iterable en Iterator

Iterable maakt eigenlijk geen deel uit van de Java Collections API, maar is er wel sterk aan verwant. Een Iterable is namelijk een object dat meerdere objecten van hetzelfde type één voor één kan teruggeven. Er moet slechts 1 methode geïmplementeerd worden, namelijk iterator(), die een Iterator-object teruggeeft.

Een Iterator is een object met twee methodes:

hasNext(), wat aangeeft of er nog objecten zijn om terug te geven, en
next(), wat (als er nog objecten zijn) het volgende object teruggeeft.

Elke keer je next() oproept krijg je dus een ander object, tot hasNext() false teruggeeft. Vanaf dan krijg je een exception (NoSuchElementException). Een Iterator moet dus een toestand bijhouden, om te bepalen welke objecten al teruggegeven zijn en welke nog niet. Eens alle elementen teruggegeven zijn, en hasNext dus false teruggeeft, is de iterator ‘opgebruikt’. Als je daarna nog eens over de elementen wil itereren, moet je een nieuwe iterator aanmaken.

Elke klasse die Iterable implementeert, kan gebruikt worden in een ’enhanced for-statement’:

Iterable<E> iterable = ...
for (var element : iterable) {
  ... // code die element gebruikt
}

Achter de schermen wordt hierbij de iterator gebruikt. Het enhanced for-statement van hierboven is equivalent aan:

Iterable<E> iterable = ...
Iterator<E> iterator = iterable.iterator();
while (iterator.hasNext()) {
  E element = iterator.next();
  ... // code die element gebruikt
}

Alle collectie-types die een verzameling elementen voorstellen (dus alles behalve Map), implementeren deze interface. Dat betekent dus dat je elk van die collecties in een enhanced for-lus kan gebruiken. Je kan daarenboven ook zelf een nieuwe klasse maken die deze interface implementeert, en die vervolgens gebruikt kan worden in een enhanced for-loop. Dat doen we in deze oefening.

Collection

classDiagram
  Iterable <|-- Collection
  class Iterable["Iterable#lt;E>"] {
    <<interface>>
    iterator()
  }
  class Collection["Collection#lt;E>"] {
    <<interface>>
    size()
    isEmpty()
    contains()
    containsAll()
    add()
    addAll()
    remove()
    removeAll()
    clear()
    toArray()
  }
  style Collection fill:#cdf,stroke:#99f

Zoals je hierboven zag, kan een Iterable dus enkel elementen opsommen. De basisinterface Collection erft hiervan over maar is uitgebreider: het stelt een groep objecten voor. Er zit nog steeds bitter weinig structuur in een Collection:

de volgorde van de elementen in een Collection ligt niet vast
er kunnen wel of geen dubbels in een Collection zitten

De belangrijkste operaties die je op een Collection-object kan uitvoeren zijn

iterator(), geërfd van Iterable
size(): de grootte opvragen
isEmpty(): nagaan of de collectie leeg is
contains en containsAll: nakijken of een of meerdere elementen in de collectie zitten
add en addAll: een of meerdere elementen toevoegen
remove en removeAll: een of meerdere elementen verwijderen
clear: de collectie volledig leegmaken
toArray: alle elementen uit de collectie in een array plaatsen

Alle operaties die een collectie aanpassen (bv. add, addAll, remove, clear, …) zijn optioneel. Dat betekent dat sommige implementaties een UnsupportedOperationException kunnen gooien als je die methode oproept. Niet elke collectie hoeft dus alle operaties te ondersteunen.

7.3.3 Lijsten

classDiagram
  Iterable <|-- Collection
  Collection <|-- List
  class Iterable["Iterable#lt;E>"] { <<interface>> }
  class Collection["Collection#lt;E>"] { <<interface>> }
  class List["List#lt;E>"] {
    <<interface>>
    get(int index)
    add(int index, E element)
    set(int index, E element)
    remove(int index)
    indexOf(E element)
    lastIndexOf(E element)
    reversed()
    subList(int from, int to)
  }
  style List fill:#cdf,stroke:#99f

List

Een lijst is een collectie waar alle elementen een vaste plaats hebben. De elementen in een lijst zijn dus geordend (maar niet noodzakelijk gesorteerd). Een lijst wordt voorgesteld door de List interface, die Collection uitbreidt met operaties die kunnen werken met de plaats (index) van een object.

Bijvoorbeeld:

get(int index): het element op een specifieke plaats opvragen
add(int index, E element): een element invoegen op een specifieke plaats (en de latere elementen opschuiven)
set(int index, E element): het element op een specifieke plaats wijzigen
remove(int index): het element op de gegeven index verwijderen (en de latere elementen opschuiven)
indexOf(E element) en lastIndexOf(E): de eerste en laatste index zoeken waarop het gegeven element voorkomt
reversed(): geeft een lijst terug in de omgekeerde volgorde
subList(int from, int to): geeft een lijst terug die een deel (slice) van de oorspronkelijke lijst voorstelt

Merk op dat de laatste twee methodes (reversed en subList) een zogenaamde view teruggeven op de oorspronkelijke lijst. Het is dus geen nieuwe lijst, maar gewoon een andere manier om naar de oorspronkelijke lijst te kijken. Bijvoorbeeld, in onderstaande code:

List<String> alphabet = new ArrayList<>(List.of("A", "B", "C", "D", "E", "F"));
                                   // alphabet = [A, B, C, D, E, F]
List<String> rev = alphabet.reversed(); // rev = [F, E, D, C, B, A]
alphabet.set(5, "X");              // alphabet = [A, B, C, D, E, X]
System.out.println(rev);           //      rev = [X, E, D, C, B, A]
List<String> cde = alphabet.subList(2, 5); //    cde = [C, D, E]
cde.clear();                       //            cde = [       ]
System.out.println(alphabet);      // alphabet = [A, B,          X]
System.out.println(rev);           //      rev = [X,          B, A]

zie je dat

de lijst rev de aanpassing (het laatste element veranderen in X) in de oorspronkelijke lijst weerspiegelt
de sublist cde leegmaken deze elementen verwijdert uit de oorspronkelijke lijst, en ook uit de omgekeerde view op de lijst (rev)

De reden is dat zowel rev als cde enkel verwijzen naar de onderliggende lijst alphabet, en zelf geen elementen bevatten:

block-beta
  block:brev
    space:1
    rev
  end
  space
  block:alphabet
    columns 6
    A B C D E F
  end
  space
  block:bcde
    cde
    space:1
  end
  rev --> alphabet
  cde --> alphabet

  classDef node fill:#faa,stroke:#f00
  classDef ptr fill:#ddd,stroke:black
  classDef empty fill:none,stroke:none
  classDef val fill:#ffc,stroke:#f90
  class brev,bcde empty
  class alphabet node
  class rev,cde ptr
  class A,B,C,D,E,F val

Indien je wat Python kent: subList is dus een manier om functionaliteit gelijkaardig aan slices te verkrijgen in Java. Maar, in tegenstelling tot slices in Python, maakt subList geen kopie!

ArrayList

ArrayList is de eerste concrete implementatie van de List-interface die we bekijken. In een ArrayList wordt een array gebruikt om de elementen bij te houden.

Aangezien arrays in Java een vaste grootte hebben, kan je niet zomaar elementen toevoegen als de lijst vol is. Daarom wordt er een onderscheid gemaakt tussen de de grootte van de lijst (het aantal elementen dat er effectief inzit), en de capaciteit van de lijst (de lengte van de onderliggende array). Zolang de grootte kleiner is dan de capaciteit, gebeurt er niets speciaals. Op het moment dat de volledige capaciteit benut is, en er nog een element toegevoegd wordt, wordt een nieuwe (grotere) array gemaakt en worden alle huidige elementen daarin gekopieerd.

Het kopiëren van een lijst is een $ \mathcal{O}(n) $ operatie, met $ n$ het huidige aantal elementen in de lijst. Stel dat we kiezen om, elke keer wanneer we een element toevoegen, de array één extra plaats te geven. We moeten dan telkens alle vorige elementen kopiëren, en dat wordt al snel erg inefficiënt. Bijvoorbeeld, stel dat we met een lege array beginnen:

om het eerste element toe te voegen, moeten we niets kopiëren
om het tweede element toe te voegen, moeten we één element kopiëren (het eerste element uit de vorige array van lengte 1)
om het derde element toe te voegen, moeten we twee elementen kopieëren (het eerste en tweede element uit de vorige array van lengte 2)
om het vierde element toe te voegen 3 kopieën, enzovoort.

Eén voor één $n$ elementen toevoegen aan een initieel lege lijst zou dus neerkomen op $0+1+…+(n-1) = n(n-1)/2 = \mathcal{O}(n^2)$ kopieën (operaties). Dat is erg veel werk als $n$ groot wordt. Om die reden wordt de lengte van de array niet telkens met 1 verhoogd, maar meteen vermenigvuldigd met een constante (meestal 2, zodat de lengte van de array verdubbelt). Bijvoorbeeld, voor een lijst met capaciteit 3 en twee elementen:

block-beta
  columns 1
  block:before
    columns 12
    e0["A"] e1["B"] e2[" "] space:9
  end
  space
  block:after1
    columns 12
    ee0["A"] ee1["B"] ee2["C"] space:9
  end
  space
  block:after2
    columns 12
    eee0["A"] eee1["B"] eee2["C"] eee3["D"] eee4[" "] eee5[" "] space:6
  end
  space
  block:after3
    columns 12
    eeee0["A"] eeee1["B"] eeee2["C"] eeee3["D"] eeee4["E"] eeee5["F"] eeee6["G"] eeee7[" "] eeee8[" "] eeee9[" "] eeee10[" "] eeee11[" "]
  end
  before --"C toevoegen (behoud capaciteit)"--> after1
  after1 --"D toevoegen (verdubbel capaciteit)"--> after2
  after2 --"E, F, G toevoegen (verdubbel capaciteit)"--> after3

  classDef ok fill:#6c6,stroke:#393,color:#fff
  class e0,e1 ok
  class ee0,ee1,ee2 ok
  class eee0,eee1,eee2,eee3 ok
  class eeee0,eeee1,eeee2,eeee3,eeee4,eeee5,eeee6 ok

De meeste toevoegingen gebeuren dus in $\mathcal{O}(1)$, maar af en toe kost een toevoeging $\mathcal{O}(n)$ omdat alle elementen gekopieerd moeten worden naar de grotere array. Als de lijst op een gegeven moment $n$ elementen bevat, en de capaciteit telkens verdubbeld werd wanneer de vorige capaciteit bereikt werd, zijn er dus in totaal $n/2 + n/4 + … \leq n = \mathcal{O}(n)$ elementen gekopieerd. Gemiddeld werd elk van de $n$ elementen dus met tijdscomplexiteit $\mathcal{O}(n)/n = \mathcal{O}(1)$ toegevoegd¹.

Operatie	Complexiteit (best case)	Complexiteit (worst case)
Opvragen	$\mathcal{O}(1)$	$\mathcal{O}(1)$
Invoegen	$\mathcal{O}(1)$ (einde van lijst), of $\mathcal{O}(n)$ bij uitbreiden capaciteit	$\mathcal{O}(n)$ (begin van lijst)
Verwijderen	$\mathcal{O}(1)$ (laatste element)	$\mathcal{O}(n)$ (eerste element)
Zoeken	$\mathcal{O}(1)$ (gezochte element is eerste element)	$\mathcal{O}(n)$ (gezochte element is laatste)

LinkedList

Een gelinkte lijst (LinkedList) is een andere implementatie van de List interface. Hier wordt geen array gebruikt, maar wordt de lijst opgebouwd uit knopen (nodes). Elke knoop bevat

een waarde (value)
een verwijzing (next) naar de volgende knoop
(in een dubbel gelinkte lijst) een verwijzing (prev) naar de vorige knoop.

De LinkedList zelf bevat enkel een verwijzing naar de eerste knoop (first), en voor een dubbel gelinkte lijst ook nog een verwijzing naar de laatste knoop van de lijst (last). Vaak wordt ook het aantal elementen (size) bijgehouden.

Hieronder zie je een grafische voorstelling van een dubbel gelinkte lijst met 3 knopen:

block-beta
  block:bf
    columns 1
    space
    first
    space
  end
  space
  block:n0
    columns 1
    e0["A"]
    p0["next"]
    pp0["prev"]
  end
  space
  block:n1
    columns 1
    e1["B"]
    p1["next"]
    pp1["prev"]
  end
  space
  block:n2
    columns 1
    e2["C"]
    p2["next"]
    pp2["prev"]
  end
  space
  block:bl
    columns 1
    space
    last
    space
  end
  first --> n0
  last --> n2
  p0 --> n1
  p1 --> n2
  pp1 --> n0
  pp2 --> n1
  classDef node fill:#faa,stroke:#f00
  classDef ptr fill:#ddd,stroke:black
  classDef empty fill:none,stroke:none
  classDef val fill:#ffc,stroke:#f90
  class bf,bl empty
  class n0,n1,n2 node
  class pp0,p0,pp1,p1,pp2,p2,first,last ptr
  class e0,e1,e2 val

De tijdscomplexiteit van een (dubbel) gelinkte lijst is anders dan die van een ArrayList:

Operatie	Complexiteit (best case)	Complexiteit (worst case)
Opvragen	$\mathcal{O}(1)$ (begin of einde van de lijst)	$\mathcal{O}(n)$ (midden van de lijst)
Invoegen	$\mathcal{O}(1)$ (begin of einde van de lijst)	$\mathcal{O}(n)$ (midden van de lijst)
Verwijderen	$\mathcal{O}(1)$ (begin of einde van de lijst)	$\mathcal{O}(n)$ (midden van de lijst)
Zoeken	$\mathcal{O}(1)$ (begin of einde van de lijst)	$\mathcal{O}(n)$ (midden van de lijst)

Merk op dat we nooit elementen moeten kopiëren of verplaatsen in een gelinkte lijst, enkel referenties aanpassen. Het aanpassen van een referentie is steeds $\mathcal{O}(1)$. Maar: we moeten eerst op de juiste plaats (knoop) geraken in de lijst, en dat kost mogelijk $\mathcal{O}(n)$ werk: in een dubbel gelinkte lijst moeten we tot $n/2$ referenties volgen (beginnend bij first of last). Vandaar de $\mathcal{O}(n)$ in de laatste kolom in de tabel hierboven.

Een gelinkte lijst is dus de juiste keuze wanneer je verwacht dat je veel aanpassingen aan je lijst zal doen, en die aanpassingen vooral voor- of achteraan zullen plaatsvinden.

Lijsten aanmaken

Je kan natuurlijk steeds een lijst aanmaken door een nieuwe, lege lijst te maken en daaraan je elementen toe te voegen:

List<String> anArrayList = new ArrayList<>();
anArrayList.add("first");
anArrayList.add("second");
...

List<String> aLinkedList = new LinkedList<>();
aLinkedList.add("first");
...

Als je een lijst wil maken met gekende elementen (constanten), dan kan je ook de List.of()-methode gebruiken:

List<String> lst = List.of("first", "second", "third");

Hierbij moet je wel opletten dat de lijst die je zo maakt immutable is. Je kan aan de lijst die je zo gemaakt hebt dus later geen wijzigingen meer aanbrengen via add, remove, etc.:

List<String> lst = List.of("first", "second", "third");
lst.add("fourth"); // gooit UnsupportedOperationException

Als je toch een wijzigbare lijst wil maken, kan je een constructor gebruiken die de meegegeven lijst kopieert:

List<String> mutable = new ArrayList<>(List.of("first", "second", "third"));
mutable.add("fourth"); // OK

Meer operaties op lijsten

De List-interface zelf bevat al enkele nuttige operaties op lijsten. In de Collections-klasse (niet hetzelfde als de Collection-interface!) vind je nog een heleboel extra operaties die je kan uitvoeren op lijsten (of soms op collecties), bijvoorbeeld:

disjoint om na te gaan of twee collecties geen overlappende elementen hebben
sort om een lijst te sorteren
shuffle om een lijst willekeurig te permuteren
swap om twee elementen van plaats te verwisselen
frequency om te tellen hoe vaak een element voorkomt in een lijst
min en max om het grootste element in een collectie te zoeken
indexOfSubList om te zoeken of en waar een lijst voorkomt in een langere lijst
nCopies om een lijst te maken die bestaat uit een aantal keer hetzelfde element
fill om alle elementen in een lijst te vervangen door eenzelfde element
rotate om de elementen in een lijst cyclisch te roteren

Unmodifiable list

Soms wil je een gewone (wijzigbare) lijst teruggeven maar er zeker van zijn dat de lijst niet aangepast kan worden. Bijvoorbeeld, als je een lijst teruggeeft als resultaat van een methode:

class Library {
  private List<Book> borrowedBooks;
  public void borrow(Book book) { ... }
  public List<Book> getBorrowedBooks() {
    return this.borrowedBooks;
  }
}

We willen niet dat een gebruiker van de klasse die lijst zomaar kan aanpassen — dat moet via de borrow-methode gaan. We kunnen natuurlijk een nieuwe lijst teruggeven met een kopie van de elementen:

public List<Book> getBorrowedBooks() {
  return new ArrayList<>(this.borrowedBooks);
}

Maar dat kost $\mathcal{O}(n)$ werk om die elementen te kopiëren. Een alternatief is gebruik maken van Collections.unmodifiableList:

public List<Book> getBorrowedBooks() {
  return Collections.unmodifiableList(this.borrowedBooks);
}

Er wordt dan geen nieuwe lijst gemaakt, maar wel een ‘view’ op de originele lijst (net zoals we eerder gezien hebben bij reversed en subList). Het verschil is dat deze view nu geen wijzigingen toelaat; alle operaties die de lijst wijzigen, gooien een UnsupportedOperationException.

Dit heet geamortiseerde (amortized) tijdscomplexiteit. ↩︎

7.3.4 Wachtrijen

classDiagram
  Iterable <|-- Collection
  Collection <|-- Queue
  Queue <|-- Deque
  Deque <|-- LinkedList
  Queue <|-- PriorityQueue
  class Iterable["Iterable#lt;E>"] { <<interface>> }
  class Collection["Collection#lt;E>"] { <<interface>> }
  class Queue["Queue#lt;E>"] {
    <<interface>>
    add(E e)
    E element()
    offer(E e)
    E peek()
    E poll()
    E remove()
  }
  class Deque["Deque#lt;E>"] {
    <<interface>>
    addFirst(E e)
    addLast(E e)
    offerFirst(E e)
    offerLast(E e)
    E removeFirst()
    E removeLast()
    E pollFirst()
    E pollLast()
    E getFirst()
    E getLast()
    E peekFirst()
    E peekLast()
  }
  style Queue fill:#cdf,stroke:#99f
  style Deque fill:#cdf,stroke:#99f

Queue, Deque

Een Queue is een collectie die lijkt op een lijst. Het voornaamste verschil met een lijst is dat een queue specifiek dient om elk toegevoegd elementen er later terug uit te halen, en dat een queue niet toelaat om te werken met de positie (index) van een element. Het volgende element dat teruggegeven wordt uit de queue wordt het hoofd (head) van de queue genoemd, de andere elementen de staart (tail). Er bestaan operaties om het element aan het hoofd van de queue terug te geven en meteen te verwijderen (poll), alsook een andere operatie om het hoofd op te vragen zonder het meteen te verwijderen (peek). Als er geen elementen in de queue zitten, geven beiden null terug.

Sommige subtypes van Queue kunnen begrensd zijn qua capaciteit. Je kan dan geen elementen toevoegen als de queue vol is.

Elementen toevoegen aan een queue kan met add of offer. De add-methode gooit een exception als de queue vol is; offer geeft gewoon false terug. Ook voor poll en peek bestaan varianten (namelijk remove en element) die een exception gooien in plaats van null terug te geven als de queue leeg is.

De volgorde waarin elementen teruggegeven worden uit de queue bepaalt het soort queue:

een FIFO (first-in-first-out) queue geeft de elementen terug in de volgorde dat ze toegevoegd zijn: het eerst toegevoegde element wordt eerst teruggegeven
een LIFO (last-in-first-out) queue geeft steeds het laatst toegevoegde element als eerste terug. Dit wordt ook een stack genoemd.
een priority queue laat toe om aan elk toegevoegd element een prioriteit toe te kennen, en geeft de elementen terug volgens die prioriteit

Java voorziet ook een Deque interface. Dit staat voor double-ended queue en laat toe om elementen vooraan en achteraan toe te voegen aan en te verwijderen uit de deque. Deze interface erft over van Queue. Bovenop de methodes uit Queue worden methodes toegevoegd met suffix -First en -Last, bijvoorbeeld pollFirst() en offerLast(). De methodes uit Queue om elementen toe te voegen (offer(), add()) komen overeen met offerLast() en addLast(). De methodes uit Queue om elementen op te vragen (peek(), poll(), etc.) komen overeen met peekFirst(), pollFirst(), etc.

De basisimplementatie in Java, zowel voor de Queue als Deque interface, is de klasse LinkedList (een dubbel gelinkte lijst). In een (dubbel) gelinkte lijst is het immers heel eenvoudig en efficiënt ($\mathcal{O}(1)$) om een element vooraan of achteraan toe te voegen en te verwijderen. Afhankelijk van welke methodes je gebruikt, gebruik je een LinkedList dus als FIFO of LIFO queue.

FIFO queue

In een FIFO queue worden de elementen teruggegeven in de volgorde dat ze toegevoegd zijn:

block-beta
  columns 1
  block:before0
    AA["A"] BB["B"] space:1
  end
  space
  block:before
    A B C
  end
  space
  block:after
    BBB["B"] CCC["C"] space:1
  end
  before0 --> before
  before --> after

Note

Welke operaties gebruik je om een Deque (of LinkedList) als FIFO queue te gebruiken?

LIFO queue (stack)

In een LIFO queue, vaak ook stack genoemd, worden het laatst toegevoegde element eerst teruggegeven:

block-beta
  columns 1
  block:before0
    AA["A"] BB["B"] space:1
  end
  space
  block:before
    A B C
  end
  space
  block:after
    AAA["A"] BBB["B"] space:1
  end
  before0 --> before
  before --> after

Note

Welke operaties gebruik je om een Deque (of LinkedList) als LIFO/stack te gebruiken?

PriorityQueue

De PriorityQueue klasse implementeert een priority queue. De prioriteit van elementen wordt bepaald door:

ofwel de natuurlijke ordening indien de elementen de Comparable-interface implementeren;
ofwel door een Comparator-object dat meegegeven wordt bij het aanmaken van de priority queue.

Deze implementatie is zeer efficiënt voor de vaak voorkomende operaties. De worst-case tijdscomplexiteit om

het hoofd van de queue op te vragen is $\mathcal{O}(1)$
het hoofd van de queue te verwijderen uit de queue is $\mathcal{O}(\log n)$
een element aan de queue toe te voegen is $\mathcal{O}(\log n)$

Nagaan of de queue een element bevat, alsook een willekeurig element verwijderen, is $\mathcal{O}(n)$ — maar beiden zijn geen typisch gebruik van een queue.

7.3.5 Verzamelingen

classDiagram
  Iterable <|-- Collection
  Collection <|-- List
  Collection <|-- Queue
  Collection <|-- Set
  class Iterable["Iterable#lt;E>"] { <<interface>> }
  class Collection["Collection#lt;E>"] { <<interface>> }
  class List["List#lt;E>"] { <<interface>> }
  class Queue["Queue#lt;E>"] { <<interface>> }
  class Set["Set#lt;E>"] {
    <<interface>>
  }
  style Set fill:#cdf,stroke:#99f

Set

Alle collecties die we totnogtoe gezien hebben, kunnen dubbels bevatten. Bij een Set is dat niet het geval. Het is een abstractie voor een wiskundige verzameling: elk element komt hoogstens één keer voor. In een wiskundige verzameling is ook de volgorde van de elementen niet van belang. De Set interface legt geen volgorde van elementen vast, maar er bestaan sub-interfaces van Set (bijvoorbeeld SequencedSet en SortedSet) die wél toelaten dat de elementen een bepaalde volgorde hebben.

De Set interface voegt in feite geen nieuwe operaties toe aan de Collection-interface. Je kan elementen toevoegen, verwijderen, en nagaan of een element in de verzameling zit.

Het is leerrijk om even stil te staan bij hoe een set efficiënt geïmplementeerd kan worden. Immers, verzekeren dat er geen duplicaten inzitten vereist dat we gaan zoeken tussen de huidige elementen, en dat wordt al gauw een $\mathcal{O}(n)$ operatie. We bekijken twee implementaties van hoe dat efficiënter kan: HashSet en TreeSet.

HashSet

Een HashSet kan gebruikt worden om willekeurige objecten in een set bij te houden. De objecten worden bijgehouden in een hashtable (in essentie een gewone array). Om te voorkomen dat we een reeds bestaand element een tweede keer toevoegen, moeten we echter snel kunnen nagaan of het toe te voegen element al in de set voorkomt. De hele hashtable overlopen kost teveel tijd ($\mathcal{O}(n)$ met $n$ het aantal objecten in de set), dus dat moeten we verbeteren.

Een HashSet kan nagaan of een element bestaat, alsook een element toevoegen en verwijderen, in $\mathcal{O}(1)$. De sleutel om dat te doen is de hashCode() methode die ieder object in Java heeft. Die methode moet, voor elk object, een hashCode (een int) teruggeven, zodanig dat als twee objecten gelijk zijn volgens hun equals-methode, ook hun hashcodes gelijk zijn. Gewoonlijk zal je, als je equals zelf implementeert, ook hashCode moeten implementeren en omgekeerd. De hashCode moet niet uniek zijn: meerdere objecten mogen dezelfde hashCode hebben, ook al zijn ze niet gelijk (al kan dat tot een tragere werking van een HashSet leiden; zie verder). Hoe uniformer de hashCode verdeeld is over alle objecten, hoe beter.

Note

Java records voorzien standaard een zinvolle equals- en hashCode-methode die afhangt van de attributen van het record. Deze hoef je dus normaliter niet zelf te voorzien.

De hashCode wordt gebruikt om een index te bepalen in de onderliggende hashtable (array). De plaats in die hashtable is een bucket. Het element wordt opgeslagen in de bucket op die index. Als we later willen nagaan of een element al voorkomt in de hashtable, berekenen we opnieuw de index aan de hand van de hashCode en kijken we of het element zich effectief in de overeenkomstige bucket bevindt.

Idealiter geeft elk object dus een unieke hashCode, en zorgen die voor perfecte spreiding van alle objecten in de hashtable. Er zijn echter twee problemen in de praktijk:

twee verschillende objecten kunnen dezelfde hashCode hebben. Dat is een collision. Hiermee moeten we kunnen omgaan.
als er teveel elementen toegevoegd worden, moet de onderliggende hashtable dynamisch kunnen uitbreiden. Dat maakt dat elementen plots op een andere plaats (index) terecht kunnen komen als voorheen. Uitbreiden vraagt vaak rehashing, oftwel het opnieuw berekenen van de index (nu in een grotere hashtable) aan de hand van de hashcodes. De load factor van de hash table geeft aan hoe vol de hashtable mag zijn voor ze uitgebreid wordt. Bijvoorbeeld, een load factor van 0.75 betekent dat het aantal elementen in de hashtable tot 75% van het aantal buckets mag gaan.

Beide problemen zijn al goed onderzocht in de computerwetenschappen. We overlopen twee technieken voor het eerste probleem (collisions): chaining en probing.

Chaining

Bij chaining houden we in de hashtable niet rechtstreeks de elementen bij, maar wijzen we in elke bucket naar een afzonderlijke gelinkte lijst. Elke keer wanneer we een element toevoegen, voegen we een knoop toe aan de gelinkte lijst in de bucket. Wanneer we een element opvragen, doorlopen we de gelinkte lijst om na te gaan of het element daarin voorkomt. Als er veel collisions zijn, verliezen we zo natuurlijk het performantie-voordeel van de hashtable. Inderdaad, in extremis hebben alle objecten dezelfde hashcode, en bevat de hashtable slechts één gelinkte lijst met daarin alle elementen. Een goede hashfunctie, die elementen goed verspreidt over de verschillende buckets, is dus essentieel voor de performantie.

block-beta
  columns 5
  block:tab
    columns 1
    i0["0"]
    i1["1"]
    i2["2"]
  end
  space
  block:lls:3
    columns 1
    block:ll0
      columns 3
      block:ll00
        columns 2
        ll00v["obj1"]
        ll00p[" "]
      end
      space
      block:ll01
        columns 2
        ll01v["obj2"]
        ll01p[" "]
      end
    end
    space
    block:ll2
      columns 3
      block:ll20
        columns 2
        ll20v["obj3"]
        ll20p[" "]
      end
      space:2
    end
  end

  i0 --> ll00
  ll00p --> ll01
  i2 --> ll20

  classDef none fill:none,stroke:none
  class lls none

Probing (open addressing)

Een andere techniek om om te gaan met collisions is probing. Als we een element willen toevoegen op een index, en er al een (ander) element op die index staat, berekenen we (volgens een deterministische formule) een volgende index, en proberen we daar opnieuw. Dat doen we tot we een lege plaats tegenkomen, waar we het element kunnen bijhouden. Die volgende index kan bijvoorbeeld (heel eenvoudig) index+1 zijn, maar we kunnen ook complexere formules bedenken waarmee we naar een heel andere plaats in de lijst springen. Bij het opzoeken volgen we hetzelfde stramien: blijven zoeken tot we het element terugvinden, of een lege plaats tegenkomen. Een element verwijderen wordt nu wel wat complexer: we moeten ervoor zorgen dat we geen lege plaats veroorzaken in de sequentie van indices.

SortedSet en TreeSet

Naast Set bestaat ook de interface SortedSet. In tegenstelling tot een Set, kan een SortedSet geen willekeurige objecten bevatten. De objecten moeten een volgorde hebben (hetzij door Comparable te implementeren, hetzij door een Comparator-object mee te geven). De elementen worden steeds in gesorteerde volgorde opgeslagen en teruggegeven.

De TreeSet klasse is een implementatie van SortedSet die gebruik maakt van een gebalanceerde boomstructuur (een red-black tree — de werking daarvan is hier niet van belang).

Alle basisoperaties (add, remove, contains) hebben worst-case tijdscomplexiteit $\mathcal{O}(\log n)$; invoegen en verwijderen zijn best-case $\mathcal{O}(1)$. De oorsprong van het logaritme wordt duidelijk aan de hand van deze oefening.

Voorbeeld

Een voorbeeld van het gebruik van een set:

Set<String> mySet = new HashSet<>();
mySet.add("John");
mySet.add("Mary");

System.out.println(mySet); // => [John, Mary]

mySet.add("John"); // John zit al in de set

System.out.println(mySet); // => [Mary, John]

Merk op dat er geen garanties zijn over de volgorde van de elementen in de set. Als we dat wel willen, gebruiken we een SortedSet:

SortedSet<String> mySet = new TreeSet<>();
mySet.add("John");
mySet.add("Mary");

for (String el : mySet) {
  System.out.println(el);
}
// gegarandeerd in alfabetische volgorde:
//  John
//  Mary

7.3.6 Maps

Map (Dictionary)

De collecties hierboven stellen allemaal een groep elementen voor, en erven over van de Collection-interface. Een Map is iets anders. Hier worden sleutels bijgehouden, en bij elke sleutel hoort een waarde (een object). Denk aan een telefoonboek, waar bij elke naam (de sleutel) een telefoonnummer (de waarde) hoort, of een woordenboek waar bij elk woord (de sleutel) een definitie hoort (de waarde). Een andere naam voor een map is dan ook een dictionary. Sleutels mogen slechts één keer voorkomen; eenzelfde waarde mag wel onder meerdere sleutels opgeslagen worden.

De interface Map<K, V> heeft twee generische parameters: een (K) voor het type van de sleutels, een een (V) voor het type van de waarden. Elementen toevoegen aan een Map<K, V> gaat via de put(K key, V value)-methode. De waarde opvragen kan via de methode V get(K key). Verder zijn er methodes om na te gaan of een map een bepaalde sleutel of waarde bevat. Een Map is vaak geoptimaliseerd voor deze operaties; deze hebben vaak tijdscomplexiteit $\mathcal{O}(1)$ (hashtable-gebaseerde implementaties) of $\mathcal{O}(\log n)$ (boom-gebaseerde implementaties).

Er zijn verder ook drie manieren om een Map<K, V> als Collection te beschouwen:

de keySet: de verzameling sleutels (een Set<K>)
de values: de collectie waarden (een Collection<V>, want dubbels zijn mogelijk)
de entrySet: een verzameling (Set<Entry<K, V>>) van sleutel-waarde paren (de entries).

Belangrijk om te onthouden is dat een Map geoptimaliseerd is om waardes op te vragen aan de hand van hun sleutels.

HashMap

Net zoals bij Set kunnen we de Map-interface implementeren met een hashtable. Dat gebeurt in de HashMap klasse. Entries in een hashmap worden in een niet-gespecifieerde volgorde bijgehouden.

De werking van een hashmap is zeer gelijkaardig aan wat we besproken hebben bij HashSet hierboven. Meer zelfs, de implementatie van HashSet in Java maakt gebruik van een HashMap. Het belangrijkste verschil met de HashSet is dat we in een HashMap, naast de waarde, ook de sleutel moeten bewaren.

SortedMap en TreeMap

Een SortedMap is een map waarbij de sleutels (dus niet de waarden) gesorteerd worden bijgehouden (zoals bij een SortedSet).

De TreeMap klasse implementeert een SortedMap aan de hand van een boomstructuur.

Voorbeeld

Een voorbeeld van het gebruik van Map als een telefoonbook:

record Person(String name) {}
record PhoneNumber(int countryCode, String prefix, String number) {}

Person mary = new Person("Mary");
Person john = new Person("John");

Map<Person, PhoneNumber> phoneBook = new HashMap<>();
phoneBook.put(john, "0470123456");
phoneBook.put(mary, "0480999999");

Person somePerson = ...

String numberOrInfo;
if (phoneBook.containsKey(somePerson)) {
  // geeft `null` terug indien persoon niet gevonden
  numberOrInfo = phoneBook.get(somePerson);
} else {
  numberOrInfo = "1207"
}

// alternatief voor bovenstaande code:
var numberOrInfo = phoneBook.getOrDefault(somePerson, "1207");

Als we personen alfabetisch kunnen sorteren, kunnen we ook een SortedMap gebruiken. Als implementatie gebruiken we dan een TreeMap in plaats van HashMap, en moeten we een comparator meegeven die bepaalt hoe de elementen gesorteerd worden.

SortedMap<Person, String> phoneBook = new TreeMap<>(Comparator.comparing(Person::name));
phoneBook.put(john, "0470123456");
phoneBook.put(mary, "0480999999");

We zijn nu zeker dat we, bij het itereren over alle items, de personen in alfabetische volgorde terugkrijgen:

for (Map.Entry<Person, String> entry : phoneBook.entrySet()) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}
// => Person[name=John] 0470123456
//    Person[name=Mary] 0480999999

Oefeningen

De Collections API

IntRange

Schrijf eerst een klasse IntRangeIterator die Iterator<Integer> implementeert, en alle getallen teruggeeft tussen twee grensgetallen lowest en highest (beiden inclusief) die je meegeeft aan de constructor. Je houdt hiervoor enkel de onder- en bovengrens bij, alsook het volgende terug te geven getal.
Schrijf nu ook een record IntRange die Iterable<Integer> implementeert, en die een IntRangeIterator-object aanmaakt en teruggeeft. Je moet deze klasse nu als volgt kunnen gebruiken:

IntRange range = new IntRange(3, 6);
for (int x : range) {
  System.out.println(x);
}
// Uitvoer:
// 3
// 4
// 5
// 6

Note

Java laat niet toe om primitieve types als generische parameters te gebruiken. Voor elk primitief type bestaat er een wrapper-klasse, bijvoorbeeld Integer voor int. Daarom gebruiken we hierboven bijvoorbeeld Iterator<Integer> in plaats van Iterator<int>. Achter de schermen worden int-waarden automatisch omgezet in Integer-objecten en omgekeerd. Dat heet auto-boxing en -unboxing. Je kan beide types in je code grotendeels door elkaar gebruiken zonder problemen.

Lijsten

MyArrayList

Schrijf zelf een simpele klasse MyArrayList<E> die werkt zoals de ArrayList uit Java. Voorzie in je lijst een initiële capaciteit van 4, maar zonder elementen. Implementeer volgende operaties:

int size() die de grootte (het huidig aantal elementen in de lijst) teruggeeft
int capacity() die de huidige capaciteit (het aantal plaatsen in de array) van de lijst teruggeeft
E get(int index) om het element op positie index op te vragen (of een IndexOutOfBoundsException indien de index ongeldig is)
void add(E element) om een element achteraan toe te voegen (en de onderliggende array dubbel zo groot te maken indien nodig)
void remove(int index) om het element op plaats index te verwijderen (of een IndexOutOfBoundsException indien de index ongeldig is). De capaciteit moet niet terug dalen als er veel elementen verwijderd werden (dat gebeurt in Java ook niet).
E last() om het laatste element terug te krijgen (of een NoSuchElementException indien de lijst leeg is)

Hier vind je een test die een deel van dit gedrag controleert:

Testcode

@Test
public void test_my_arraylist() {
    MyArrayList<String> lst = new MyArrayList<>();
    // initial capacity and size
    assertThat(lst.capacity()).isEqualTo(4);
    assertThat(lst.size()).isEqualTo(0);

    // adding elements
    for (int i = 0; i < 4; i++) {
        lst.add("item" + i);
    }
    assertThat(lst.size()).isEqualTo(4);
    assertThat(lst.capacity()).isEqualTo(4);
    assertThat(lst.last()).isEqualTo("item3");

    // adding more elements
    for (int i = 4; i < 10; i++) {
        lst.add("item" + i);
    }
    assertThat(lst.size()).isEqualTo(10);
    assertThat(lst.capacity()).isEqualTo(16);
    assertThat(lst.last()).isEqualTo("item9");

    // remove an element
    lst.remove(3);
    assertThat(lst.size()).isEqualTo(9);
    assertThat(lst.capacity()).isEqualTo(16);
    assertThat(lst.get(3)).isEqualTo("item4");
    assertThatThrownBy(() -> lst.get(10)).isInstanceOf(IndexOutOfBoundsException.class);
}

Linked list

Schrijf zelf een klasse MyLinkedList<E> om een dubbel gelinkte lijst voor te stellen. Voorzie volgende operaties:

int size() om het aantal elementen terug te geven
void add(E element) om het gegeven element achteraan toe te voegen
E get(int index) om het element op positie index op te vragen
void remove(int index) om het element op positie index te verwijderen

Hieronder vind je enkele tests voor je klasse. Je zal misschien merken dat je implementatie helemaal juist krijgen niet zo eenvoudig is als het op het eerste zicht lijkt, zeker bij de remove-methode. Gebruik de visuele voorstelling van eerder, en ga na wat je moet doen om elk van de getekende knopen te verwijderen.

Testcode

@Test
public void add_first_element() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    lst.add("element0");
    assertThat(lst.size()).isEqualTo(1);
    assertThat(lst.get(0)).isEqualTo("element0");
}

@Test
public void add_more_elements() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    lst.add("element0");
    lst.add("element1");
    assertThat(lst.size()).isEqualTo(2);
    assertThat(lst.get(0)).isEqualTo("element0");
    assertThat(lst.get(1)).isEqualTo("element1");

    lst.add("element2");
    assertThat(lst.size()).isEqualTo(3);
    assertThat(lst.get(0)).isEqualTo("element0");
    assertThat(lst.get(1)).isEqualTo("element1");
    assertThat(lst.get(2)).isEqualTo("element2");
}

@Test
public void remove_elements() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    lst.add("element0");
    lst.add("element1");
    lst.add("element2");

    lst.remove(1);
    assertThat(lst.size()).isEqualTo(2);
    assertThat(lst.get(0)).isEqualTo("element0");
    assertThat(lst.get(1)).isEqualTo("element2");

    lst.remove(1);
    assertThat(lst.size()).isEqualTo(1);
    assertThat(lst.get(0)).isEqualTo("element0");
}

@Test
public void get_from_empty() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    assertThatIndexOutOfBoundsException().isThrownBy(() -> lst.get(0));
}

@Test
public void remove_from_empty() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    assertThatIndexOutOfBoundsException().isThrownBy(() -> lst.remove(0));
}

@Test
public void get_from_single() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    lst.add("element0");
    assertThat(lst.get(0)).isEqualTo("element0");
}

@Test
public void remove_from_single() {
    MyLinkedList<String> lst = new MyLinkedList<>();
    lst.add("element0");
    lst.remove(0);
    assertThat(lst.size()).isEqualTo(0);
}

Wachtrijen

MyFIFO

Implementeer zelf een klasse MyFIFO<E> die een FIFO queue voorstelt met beperkte capaciteit, en die gebruik maakt van een array om de elementen te bewaren. De capaciteit wordt opgegeven bij het aanmaken. Invoegen en terug verwijderen van elementen moet zeer efficiënt zijn ($\mathcal{O}(1)$). Implementeer volgende operaties:

size(): het aantal elementen in je queue
E poll(): het hoofd van je FIFO queue opvragen en verwijderen; geeft null terug indien de queue leeg is
boolean add(E): een element (niet-null) toevoegen aan je queue; geeft false terug indien er niet voldoende capaciteit is

Hieronder vind je enkele tests.

Testcode

@Test
public void empty_fifo_size_0() {
    MyFIFO<String> fifo = new MyFIFO<>(5);
    assertThat(fifo.size()).isEqualTo(0);
}

@Test
public void fifo_one_element() {
    MyFIFO<String> fifo = new MyFIFO<>(5);
    fifo.add("first");
    assertThat(fifo.size()).isEqualTo(1);
    assertThat(fifo.poll()).isEqualTo("first");
}

@Test
public void fifo_maximum_capacity() {
    MyFIFO<String> fifo = new MyFIFO<>(5);
    for (var e : List.of("first", "second", "third", "fourth", "fifth")) {
        assertThat(fifo.add(e)).isTrue();
    }
    assertThat(fifo.size()).isEqualTo(5);

    assertThat(fifo.add("sixth")).isFalse();
    assertThat(fifo.size()).isEqualTo(5);
}

@Test
public void fifo_poll_correct_order() {
    MyFIFO<String> fifo = new MyFIFO<>(5);
    for (var e : List.of("first", "second", "third", "fourth", "fifth")) {
        assertThat(fifo.add(e)).isTrue();
    }
    assertThat(fifo.poll()).isEqualTo("first");
    assertThat(fifo.poll()).isEqualTo("second");
    assertThat(fifo.poll()).isEqualTo("third");
    assertThat(fifo.size()).isEqualTo(2);
    assertThat(fifo.poll()).isEqualTo("fourth");
    assertThat(fifo.poll()).isEqualTo("fifth");
    assertThat(fifo.size()).isEqualTo(0);
}

Denkvraag

Wat zou je moeten doen om je MyFIFO-klasse dynamisch te laten groeien als er meer elementen aan toegevoegd worden?

Priority boarding

Hieronder is een record die een vliegtuigpassagier voorstelt.

record Passenger(String name, int priority) { }

Maak een klasse PriorityBoarding waar je een PriorityQueue gebruikt om passagiers te laten boarden. Passagiers mogen het vliegtuig betreden volgens oplopende prioriteit (prioriteit 1 mag voor 2), en bij gelijke prioriteit, in alfabetische volgorde (A mag voor B). Maak daarvoor twee operaties in je klasse:

checkin(Passenger p) om een passagier toe te voegen aan de lijst van passagiers die kunnen instappen
Passenger nextPassenger() die de volgende passagier teruggeeft die mag instappen, of null indien er geen passagiers meer zijn.

Hieronder vind je een test.

Hint: schrijf een Comparator. Je kan daarbij gebruik maken van de statische methodes uit de Comparator-interface.

Testcode

@Test
public void priority_example() {
    var p1 = new Passenger("Bob", 1);
    var p2 = new Passenger("Alex", 2);
    var p3 = new Passenger("Charlie", 3);
    var p4 = new Passenger("Donald", 3);

    var prio = new PriorityBoarding();
    prio.checkin(p4);
    prio.checkin(p1);
    prio.checkin(p3);
    prio.checkin(p2);

    assertThat(prio.nextPassenger()).isEqualTo(p1);
    assertThat(prio.nextPassenger()).isEqualTo(p2);
    assertThat(prio.nextPassenger()).isEqualTo(p3);
    assertThat(prio.nextPassenger()).isEqualTo(p4);
}

Sets

Unieke hashcode

Test uit hoe belangrijk het is dat de hashcodes van verschillende objecten in een HashSet goed verdeeld zijn aan de hand van de code hieronder. Deze code meet hoelang het duurt om een HashSet te vullen met 50000 objecten; de eerste keer met goed verspreide hashcodes, en de tweede keer een keer met steeds dezelfde hashcode. Voer uit; merk je een verschil?

import java.util.HashSet;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;

public class Timing {

    record DefaultHashcode(int i) {}
    record CustomHashcode(int i) {
        @Override
        public int hashCode() {
            return 4;
        }
    }

    public static void main(String[] args) {
        System.out.print("With default hashcode: ");
        test(DefaultHashcode::new);
        System.gc();
        System.out.print("With identical hashcode: ");
        test(CustomHashcode::new);
    }

    private static <T> void test(Function<Integer, T> ctor) {
        var set = new HashSet<T>();
        var start = System.nanoTime();
        for (int i = 0; i < 50_000; i++) {
            set.add(ctor.apply(i));
        }
        var end = System.nanoTime();
        System.out.println(set.size() + " elements added in " + TimeUnit.NANOSECONDS.toMillis(end - start) + "ms");
    }
}

Veranderende hashcode

Is het nodig dat de hashCode van een object hetzelfde blijft doorheen de levensduur van het object, of mag deze veranderen? Verklaar je antwoord.

Antwoord

Nee, deze mag niet veranderen. Mocht die wel veranderen, kan het zijn dat je een object niet meer terugvindt in een set, omdat er (door de veranderde hashcode) in een andere bucket gezocht wordt dan waar het object zich bevindt.

Voorbeeldcode

import java.util.HashSet;
import java.util.Set;

public class Demo {

    static class MyObject {
        public int hashCode = 1;

        @Override
        public int hashCode() {
            return hashCode;
        }
    }

    public static void main(String[] args) {
        Set<MyObject> set = new HashSet<>();

        MyObject obj = new MyObject();
        set.add(obj);
        System.out.println("Before changing hashcode");
        System.out.println("Contains: " + set.contains(obj));

        obj.hashCode++;

        System.out.println("After changing hashcode");
        System.out.println("Contains: " + set.contains(obj));
    }
}

Boomstructuur

flowchart TB
subgraph s0 ["d=0"]
direction LR
R
end
subgraph s1 ["d=1"]
direction LR
A
X10[" "]
X11[" "]
B
end
subgraph s2 ["d=2"]
direction LR
C
D
X20[" "]
X21[" "]
X22[" "]
end
subgraph s3 ["d=3"]
direction LR
X30[" "]
X31[" "]
E
X32[" "]
X33[" "]
X34[" "]
end
R --> A
R --> B
A --> C
A --> D
D --> E

classDef empty fill:none,stroke:none
classDef depth stroke:none
class X10,X11,X20,X21,X22,X30,X31,X32,X33,X34 empty
class s0,s1,s2,s3 depth

Stel dat je een binaire boom hebt: een boomstructuur hebt waar elke knoop in de boom maximaal 2 kinderen heeft, zoals het voorbeeld hierboven.

De diepte van een knoop is de afstand van die knoop tot de wortelknoop (bv. in de boom hierboven heeft knoop A diepte 1, knoop E diepte 3, en knoop R diepte 0).
De hoogte van de boom is de maximale diepte van alle knopen in de boom (of dus: de diepte van de knoop die het verst van de wortel ligt). In het voorbeeld ligt knoop E het verst (met diepte 3), dus de hoogte van deze boom is 3.

wat is de maximale hoogte van een binaire boom met $n$ knopen?
wat is het maximaal aantal elementen met diepte gelijk aan $d$ in een binaire boom?
wanneer heeft een binaire boom met $n$ knopen een minimale hoogte? Wat is die hoogte?

Antwoord

Om de maximale hoogte te bekomen, geven we elke knoop slechts 1 kind. We krijgen dan gewoon een lineaire ketting van $n$ knopen, en de hoogte daarvan is $n-1$.
Op diepte $d$ kunnen zich in totaal maximaal $2^d$ knopen bevinden.
De minimale hoogte bekomen we wanneer alle knopen precies 2 kinderen hebben (behalve de knopen op het diepste niveau). Veronderstellen we dus dat de boom $n$ elementen bevat en elke laag volledig opgevuld is, dan bevat die $$n = 2^0 + 2^1 + ... + 2^h = 2^{h+1} - 1 $$ knopen, met $h$ de hoogte van de boom. Daaruit leiden we af dat $ h = \log_2(n+1) - 1 \in \mathcal{O}(\log_2 n) $. Met andere woorden, de hoogte van de boom groeit logaritmisch in functie van het aantal elementen.

Scheduler

Maak een record Job met attributen time (je kan gewoon een double gebruiken) en een description (String). Maak ook een klasse Scheduler die een TreeSet gebruikt om volgende methodes te implementeren:

schedule(Job job) om de gegeven job toe te voegen aan de scheduler
List<Job> allJobs() om alle jobs (in volgorde van hun tijd) terug te krijgen
Job nextJob(double after) om de eerstvolgende job op of na het gegeven tijdstip terug te vinden. (Hint: bekijk eerst of er bruikbare methodes zijn in de klasse TreeSet.)

Hieronder vind je een test die deze methodes gebruikt.

@Test
public void test_scheduler() {
    var scheduler = new Scheduler();
    var job1 = new Job(1, "First job");
    var job2 = new Job(2, "Second job");
    var job3 = new Job(3, "Third job");

    scheduler.schedule(job3);
    scheduler.schedule(job1);
    scheduler.schedule(job2);

    assertThat(scheduler.allJobs()).containsExactly(job1, job2, job3);
    assertThat(scheduler.nextJob(2)).isEqualTo(job2);
    assertThat(scheduler.nextJob(2.5)).isEqualTo(job3);
}

Maps

Set implementeren met Map

Leg uit hoe je een HashSet zou kunnen implementeren gebruik makend van een HashMap. (Dit is ook wat Java (en Python) doen in de praktijk.)

Antwoord

Je gebruikt de elementen die je in de set wil opslaan als sleutel (key), en als waarde (value) neem je een willekeurig object. Als het element in de HashMap een geassocieerde waarde heeft, zit het in de set; anders niet.

Parking

Maak een klasse Parking die gebruikt wordt voor betalend parkeren. Kies een of meerdere datastructuren om volgende methodes te implementeren:

enterParking(String licensePlate): een auto rijdt de parking binnen
double amountToPay(String licensePlate): bereken het te betalen bedrag voor de gegeven auto (nummerplaat). De parking kost 2 euro per begonnen uur.
pay(String licensePlate): markeer dat de auto met de gegeven nummerplaat betaald heeft
boolean leaveParking(String licensePlate): geef terug of de gegeven auto de parking mag verlaten (betaald heeft), en verwijder de auto uit het systeem indien betaald werd.

Om te werken met huidige tijd en intervallen tussen twee tijdstippen, kan je gebruik maken van java.time.Instant.

@Test
public void test_parking() throws InterruptedException {
    Parking parking = new Parking();
    parking.enterParking("ABC123");
    Thread.sleep(Duration.ofSeconds(1));
    var amount = parking.amountToPay("ABC123");
    assertThat(amount).isEqualTo(2.0);
    assertThat(parking.leaveParking("ABC123")).isFalse();
    parking.pay("ABC123");
    assertThat(parking.leaveParking("ABC123")).isTrue();
}

MultiMap

Schrijf een klasse MultiMap die een map voorstelt, maar waar bij elke key een verzameling (Set) van waarden hoort in plaats van slechts één waarde. Gebruik een Map in je implementatie.

Hieronder vind je enkele tests, die ook aangeven welke methodes je moet voorzien.

public class MultiMapTest {

    @Test
    public void empty_multimap() {
        var mm = new MultiMap<Integer, String>();
        assertThat(mm.size()).isEqualTo(0);
    }

    @Test
    public void add_one_element() {
        var mm = new MultiMap<Integer, String>();
        mm.put(1, "first");
        assertThat(mm.size()).isEqualTo(1);
        assertThat(mm.get(1)).containsExactly("first");
    }

    @Test
    public void add_multiple_with_same_key() {
        var mm = new MultiMap<Integer, String>();
        mm.put(1, "first");
        mm.put(1, "second");
        mm.put(1, "third");
        mm.put(2, "fourth");
        mm.put(2, "fifth");
        assertThat(mm.size()).isEqualTo(2);
        assertThat(mm.get(1)).containsExactlyInAnyOrder("first", "second", "third");
        assertThat(mm.get(2)).containsExactlyInAnyOrder("fourth", "fifth");
    }

    @Test
    public void remove_one_value() {
        var mm = new MultiMap<Integer, String>();
        mm.put(1, "first");
        mm.put(1, "second");
        mm.put(1, "third");
        assertThat(mm.size()).isEqualTo(1);
        mm.remove(1, "second");
        assertThat(mm.size()).isEqualTo(1);
        assertThat(mm.get(1)).containsExactlyInAnyOrder("first", "third");
    }
}

7.4 Multithreading en concurrency

In andere programmeertalen

De concepten in andere programmeertalen die het dichtst aanleunen bij Java’s multithreading en concurrency primitieven zijn

pthreads in C
std::thread en aanverwanten in C++
de threading en multiprocessing modules in Python
de System.Threading namespace in C#

Wat en waarom?

We maken eerst onderscheid tussen de begrippen parallellisme en concurrency.

Bij parallellisme (soms ook multiprocessing genoemd) worden meerdere instructies gelijktijdig uitgevoerd. Dit vereist meerdere verwerkingseenheden (machines, CPU’s, CPU cores, …) waarop die instructies uitgevoerd kunnen worden. Parallellisme wordt interessant wanneer er veel instructies uitgevoerd moeten worden die onafhankelijk van elkaar kunnen gebeuren. Hoe meer afhankelijkheden er zijn, hoe meer er gecoördineerd moet worden, wat leidt tot meer overhead.

Bij concurrency (soms ook multitasking genoemd) zijn meerdere taken actief op een bepaald moment. Dat betekent dat een tweede taak al kan starten voordat de eerste afgelopen is. Het hoeft echter niet zo te zijn dat er ook gelijktijdig instructies voor elk van die taken uitgevoerd worden. Concurrency impliceert dus geen parallelisme: je kan concurrency hebben met slechts 1 single-core CPU. Er zijn meerdere mogelijkheden om concurrency te bereiken met slechts één CPU:

pre-emption: een externe scheduler (bijvoorbeeld in het besturingssysteem) beslist wanneer en voor hoelang een bepaalde taak de processor ter beschikking krijgt. Een voorbeeld hiervan is time slicing: het besturingssysteem onderbreekt elke taak na een bepaalde vaste tijd (of aantal instructies), om de controle vervolgens aan een andere taak te geven.
cooperative multitasking: een taak beslist zelf wanneer die de controle teruggeeft, bijvoorbeeld wanneer er gewacht moet worden op een ’trage’ operatie zoals het lezen van een bestand, het ontvangen van een inkomend netwerkpakket, …. Veel programmeertalen (maar niet Java) ondersteunen coöperatieve multitasking via coroutines en async/await keywords.

Het spreekt voor zich dat, op moderne (multi-core) machines, concurrency en parallelisme vaak gecombineerd worden. Er zijn dus meerdere taken actief, waarvan sommige ook tegelijkertijd uitgevoerd worden.

Multithreading tenslotte is een specifiek concurrency-mechanisme: er worden, binnen eenzelfde proces van het besturingssysteem, meerdere ’threads’ gestart om taken uit te voeren. Deze threads delen hetzelfde geheugen (namelijk dat van het proces), en kunnen daardoor dus efficiënter data uitwisselen dan wanneer elke taak als apart proces gestart zou worden. Op elk moment kunnen er dus meerdere threads bestaan, die (afhankelijk van of er ook parallellisme is in het systeem) al dan niet gelijktijdig instructies uitvoeren. Binnen een Java-programma is multithreading de voornaamste manier om zowel parallelisme als concurrency te bereiken.

IO-bound vs CPU-bound tasks

De taken die al dan niet gelijktijdig uitgevoerd moeten worden, kunnen onderverdeeld worden in zogenaamde CPU-bound en IO-bound taken.

Bij een CPU-bound taak wordt de uitvoeringstijd voornamelijk gedomineerd door de uitvoering van instructies (berekeningen), bijvoorbeeld algoritmes, beeldverwerking, simulaties, …. Hoe sneller de CPU, hoe sneller de taak dus afgewerkt kan worden.

Een IO-bound task daarentegen is vaak aan het wachten op externe gebeurtenissen (interrupts), zoals netwerk- of schijf-toegang, timers, gebruikersinvoer, … Een snellere CPU zal deze taak niet sneller doen gaan.

In het algemeen is parallellisme vooral nuttig wanneer er veel CPU-bound taken zijn. De totale tijd die nodig is om alle taken uit te voeren kan op die manier geminimaliseerd worden. Voor IO-bound tasks is parallelisme niet noodzakelijk een goede oplossing: de verschillende CPU’s zouden gelijktijdig aan het wachten zijn op externe interrupts. Het gebruik van concurrency kan hier wel soelaas bieden: terwijl één taak wacht op een externe gebeurtenis, kan een andere verder uitgevoerd worden.

Threads in Java

De basisklasse in Java om te werken met multithreading is de Thread-klasse. Typisch geef je een Runnable mee die uitgevoerd moet worden. Dat kan een object zijn, een lambda, of een method reference. Een aangemaakte thread start niet automatisch; om de uitvoering van de thread te starten, moet je de start-methode oproepen. Als je wil wachten tot de thread afgelopen is, kan dat via de join-methode. Deze blokkeert de uitvoering tot de uitvoering van de thread afloopt. Je kan ook een timeout meegeven aan join, met de maximale tijdsduur dat je wilt wachten. Als deze tijd voorbij is vooraleer de thread afloopt, wordt een InterruptedException gegooid.

Bijvoorbeeld: onderstaande code start een nieuwe thread, die een regel uitprint. Er zijn in het programma dus twee threads actief: (1) de thread die de nieuwe thread aanmaakt, start, en er vervolgens (maximaal 2 seconden) op wacht; en (2) de thread die de boodschap uitprint.

Note

Een exception in een thread komt niet terug terecht in de originele thread; deze kan dus ‘verloren’ gaan.

var t1 = new Thread(() -> {
    System.out.println("Hello from a new thread");
});
t1.start();
...
t1.join(Duration.ofSeconds(2));

Een standaard Java thread wordt uitgevoerd met een thread van het besturingssysteem (een platform thread, die typisch overeenkomt met een kernel thread). Zo krijg je dus, op machines die het ondersteunen, ook automatisch parallellisme in Java: meerdere threads kunnen effectief tegelijkertijd instructies uitvoeren. Een nadeel hiervan is dat het aantal threads beperkt is: elke platform-thread komt met een zekere overhead.

Sinds Java 21 beschikt Java ook over virtual threads. Dat zijn threads die beheerd worden door de Java Virtual Machine (JVM) zelf, en dus niet 1-1 overeenkomen met een platform thread. Je JVM zal een virtuele thread koppelen aan een platform thread, en deze terug ontkoppelen op het moment dat de virtuele thread moet wachten op een trage operatie. De platform thread is dan terug vrij, en kan gebruikt worden om een andere virtuele thread uit te voeren. Virtual threads zijn het Java-alternatief voor cooperative multitasking. Het teruggeven van de controle wordt echter afgehandeld door de onderliggende bibliotheken, dus als programmeur word je niet geconfronteerd met wachten op blokkerende operaties, of async/await keywords. Je schrijft je code dus gewoon zoals sequentiële code zonder rekening te houden met mogelijk blokkerende operaties. Virtuele threads hebben ook weinig overhead; je kan er zonder probleem duizenden van aanmaken zonder significante impact op de performantie.

We gaan het in de rest van dit hoofdstuk enkel hebben over de gewone (platform) threads, dus niet over virtual threads.

Synchronisatie

Wanneer meerdere threads (of processen) met gedeelde data werken, ontstaat er een nood aan synchronisatie. Het kan immers zijn dat beide threads dezelfde data lezen en/of aanpassen, waardoor de data inconsistent wordt. Dat wordt een race-conditie genoemd.

Race-conditie

Neem het voorbeeld hieronder: één thread verhoogt de waarde van een teller 10.000 keer, de andere verlaagt die 10.000 keer. Welke waarde van de teller verwacht je op het einde van de code?

class Counter {
  private int count = 0;
  public void increment() { count++; }
  public void decrement() { count--; }
  public int getCount() { return count; }
}

var counter = new Counter();

var inc = new Thread(() -> {
  for (int i = 0; i < 10_000; i++) counter.increment();
});
var dec = new Thread(() -> {
  for (int i = 0; i < 10_000; i++) counter.decrement();
});

inc.start(); dec.start();
inc.join(); dec.join();

System.out.println(counter.getCount());

Op mijn machine gaven drie uitvoeringen van dit programma achtereenvolgens de waarden -803, -5134, en 3041. Hoe kan dat? Er worden toch evenveel increments uitgevoerd als decrements, waardoor de teller terug op 0 moet uitkomen? De reden is dat het lezen en terug wegschrijven van de (verhoogde of verlaagde) variabele (i.e., count++ en count--) twee afzonderlijke operaties zijn, die door het onderlinge verschil in timing tussen de threads op verschillende momenten kunnen plaatsvinden. Bijvoorbeeld, stel dat count op een bepaald moment gelijk is aan 40; de inc-thread verhoogt de teller 2 keer, en de dec-thread verlaagt de teller 1 keer, in onderstaande volgorde:

Thread `inc`	Thread `dec`
lees count=40
	lees count=40
zet count=41
lees count=41
zet count=42
	zet count=39

De teller is nu niet 41 (wat de correcte waarde zou zijn na 2 verhogingen en 1 verlaging), maar 39. De twee verhogingen hebben dus geen enkel effect gehad. Door andere volgordes (interleavings) van beide threads kan je zo verschillende resultaten krijgen: count kan (in theorie) elke waarde tussen -10.000 en 10.000 hebben op het einde van het programma. We zeggen dat de Counter-klasse niet thread-safe is: ze kan niet correct gebruikt worden door meerdere threads zonder extra maatregelen.

Volatile variabelen

Bovenstaande code heeft ook nog een ander probleem: wanneer de code uitgevoerd wordt op meerdere CPU’s of cores, kan het kan zijn de count variabele enkel in het lokale geheugen van één CPU aangepast wordt (bv. een register, L1 cache, …), en nog niet meteen naar het (gedeelde) geheugen teruggeschreven wordt. Zelfs als de tweede thread de waarde van count pas uitleest nadat deze aangepast is door de eerste thread, kan het zijn dat die nog een oude waarde ziet:

Thread `inc`	Thread `dec`
lees count=40
zet count=41
lees count=41
zet count=42
	lees count=40
	zet count=39
schrijf count naar geheugen
	schrijf count naar geheugen

Om dit op te lossen, kan je in Java een variabele als volatile markeren. Dat garandeert dat alle aanpassingen aan die variabele meteen naar het centrale geheugen geschreven worden, en vermijdt bovenstaande situatie.

class Counter {
  private volatile int count = 0;
  public void increment() { count++; }
  public void decrement() { count--; }
  public int getCount() { return count; }
}

Een volatile variabele is dus een variabele waarvan alle threads steeds de laatste waarde zien. Technisch gezien komt volatile eigenlijk met een nog sterkere garantie: als thread B een volatile variabele leest die door thread A geschreven werd, zullen ook alle andere (niet-volatile) variabelen die B daarna leest, de waarde hebben die ze in thread A hadden voordat die thread de volatile variabele aanpaste. Met andere woorden, thread B ziet consistente waarden voor alle variabelen die een invloed gehad zouden kunnen hebben op de huidige waarde van de volatile variabele. Het schrijven en vervolgens lezen van een volatile variabele is dus een synchronisatie-punt tussen threads.

Bijvoorbeeld, stel dat t, u, v, en w vier variabelen zijn, waarvan enkel v als volatile gemarkeerd is. Alle variabelen hebben oorspronkelijk 0 als waarde. In de tabel hieronder is met een * aangegeven welke waarden in thread B gegarandeerd de meest recente waarden zijn. In het bijzonder zal variabele w niet noodzakelijk de laatste waarde hebben, omdat die door thread A na variabele v geschreven werd. Ook variabele u zal, vooraleer v gelezen wordt, niet noodzakelijk de meest recente waarde bevatten.

Thread A	Thread B
schrijf t=1
schrijf u=1
schrijf v=1 (volatile)
schrijf w=1
	lees u=?
	lees v=1 (volatile) *
	lees t=1 *
	lees u=1 *
	lees w=?

Merk wel op dat het gebruik van volatile de race-conditie van hierboven nog steeds niet oplost! Een variabele als volatile markeren heeft immers enkel invloed op de zichtbaarheid van die variabele. Het biedt geen garanties bij gelijktijdige aanpassingen door meerdere threads. Daarvoor hebben we synchronisatie nodig.

Synchronizatie-primitieven

Om race condities te voorkomen, moet je toegang tot gedeeld geheugen op een of andere manier synchroniseren. Meer specifiek wil je een sequentie van operaties atomisch kunnen maken: ze moeten worden uitgevoerd alsof ze één primitieve operatie zijn, die niet onderbroken kan worden door een andere thread. In het voorbeeld van hierboven wil je dus dat het lezen, verhogen, en wegschrijven van de teller steeds als één geheel uitgevoerd wordt, in plaats van als twee aparte operaties.

Java biedt meerdere synchronizatie-primitieven aan. Sommigen zitten ingebouwd in de taal (bv. volatile en synchronized; zie later), andere zitten in de packages java.util.concurrent en java.util.concurrent.locks. We bespreken er hier enkele.

Semafoor

Een Semaphore deelt een gegeven maximum aantal toestemmingen uit aan threads (via acquire()). Alle volgende threads die toestemming willen, moeten wachten tot een van de vorige toestemmingen terug ingeleverd wordt (via release()). Een binaire semafoor (met maximaal 1 toestemming) kan dienen als mutual exclusion lock (mutex). Een semafoor houdt (conceptueel) enkel een teller bij van het resterend aantal toestemmingen, en niet welke thread al toestemming heeft. Er is dan ook geen enkele garantie of verificatie dat een thread die release() oproept effectief zo’n toestemming verkregen had; het aantal beschikbare toestemmingen wordt gewoon terug verhoogd.

Een voorbeeld van het gebruik van een semafoor voor de implementatie van Counter:

class Counter {
    private volatile int count = 0;
    private final Semaphore sem = new Semaphore(1);

    public void increment() throws InterruptedException {
        sem.acquire();
        try {
            count++;
        } finally {
            sem.release();
        }
    }

    public void decrement() throws InterruptedException {
        sem.acquire();
        try {
            count--;
        } finally {
            sem.release();
        }
    }

    public int getCount() {
        return count;
    }
}

Met het gebruik van een semafoor voor synchronisatie krijg je ook automatisch zichtbaarheids-garanties; je kan het vrijgeven van de semafoor beschouwen als het schrijven naar een volatile variabele, en het verkrijgen van een toestemming als het lezen van een volatile variabele. Alle wijzigingen die gedaan worden voor het vrijgeven van de semafoor zijn dus zichtbaar voor alle threads die nadien een toestemming verkrijgen.

Lock

De Lock interface, en de implementaties ReentrantLock, stellen een mechanisme voor waarbij een thread de lock kan verkrijgen (lock()) en terug vrijgeven (unlock()). Hierbij wordt wél nagegaan dat enkel de thread die de lock verkregen heeft, de lock terug kan vrijgeven. ‘Re-entrant’ betekent dat een thread die reeds een lock heeft, verder mag gaan wanneer die een tweede keer lock() oproept (op hetzelfde lock-object).

Een voorbeeld van het gebruik van een ReentrantLock voor de implementatie van Counter:

class Counter {
    private volatile int count = 0;
    private final Lock lock = new ReentrantLock();

    public void increment() {
        lock.lock();
        try {
            count++;
        } finally {
            lock.unlock();
        }
    }

    public void decrement() {
        lock.lock();
        try {
            count--;
        } finally {
            lock.unlock();
        }
    }

    public int getCount() {
        return count;
    }
}

Net zoals bij een semafoor krijg je bij het gebruik van een lock ook automatisch zichtbaarheids-garanties; je kan ‘unlock()’ beschouwen als het schrijven naar een volatile variabele, en ’lock()’ als het lezen van een volatile variabele. Alle wijzigingen die gedaan worden voor het unlocken zijn dus zichtbaar voor alle threads die nadien lock uitvoeren.

AtomicInteger

Specifiek voor primitieve types biedt Java ook een verzameling atomische objecten aan, bijvoorbeeld AtomicInteger. Daarop zijn operaties gedefinieerd zoals incrementAndGet, updateAndGet, getAndAdd, …. Bovenstaande counter kan dus ook eenvoudig als volgt geïmplementeerd worden:

class Counter {
    private final AtomicInteger count = new AtomicInteger(0);

    public void increment() { count.incrementAndGet(); }
    public void decrement() { count.decrementAndGet(); }
    public int getCount() { return count.get(); }
}

Er zijn ook andere klassen, bijvoorbeeld AtomicLong, AtomicBoolean, AtomicIntegerArray, AtomicReferenceArray, … Deze klassen zijn efficiënt geïmplementeerd, en hebben dus de voorkeur wanneer er enkel gesynchroniseerd moet worden om een primitieve variabele of array aan te passen.

Synchronized

Het gebruiken van een lock is zo alomtegenwoordig dat, in Java, elk object als een lock gebruikt kan worden door middel van het synchronized keyword. Bijvoorbeeld:

class Counter {
    private volatile int count = 0;
    private final Object lock = new Object();

    public void increment() {
        synchronized (lock) {
            count++;
        }
    }

    public void decrement() {
        synchronized (lock) {
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

Op deze manier beschikt elk Counter-object over een eigen object dat als lock gebruikt wordt. Het synchronized-block geeft aan dat dat lock nodig is om de code in het bijhorende blok uit te voeren, en de lock wordt automatisch terug vrijgegeven op het einde van dat block.

Omdat elk object in Java zo als lock gebruikt kan worden, hoeven we geen apart object aan te maken; we kunnen ook gewoon this gebruiken:

class Counter {
    private volatile int count = 0;

    public void increment() {
        synchronized (this) {
            count++;
        }
    }

    public void decrement() {
        synchronized (this) {
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

Tenslotte laat Java ook toe om een hele methode als synchronized te definiëren. Dat heeft hetzelfde effect als de code met synchronized(this) hierboven:

class Counter {
    private volatile int count = 0;

    public synchronized void increment() {
        count++;
    }

    public synchronized void decrement() {
        count--;
    }

    public int getCount() {
        return count;
    }
}

Code die gebruik maakt van synchronized heeft ook zichtbaarheids-garanties; je kan het einde van een synchronized-block beschouwen als het schrijven naar een volatile variabele (die hoort bij het object waarop gesynchroniseerd wordt), en het begin ervan als het lezen van die volatile variabele. Alle wijzigingen die gedaan worden voor of in een synchronized-blok of methode zijn dus zichtbaar voor alle threads die nadien een synchronized-blok of methode uitvoeren, tenminste als er gesynchroniseerd wordt op hetzelfde object. In onderstaande code is er dus geen garantie dat thread B de acties van thread A ziet:

Object lock1 = new Object();
Object lock2 = new Object();

// in thread A
synchronized(lock1) {
  // acties van A
}
// later...

// in thread B
synchronized(lock2) {
  // acties van B
}

Deadlocks

Threads die werken met locks kunnen in een deadlock geraken wanneer ze op elkaar wachten. Geen enkele thread kan dan vooruitgang maken. Bijvoorbeeld, in onderstaande code heeft de counter een apart read- en write-lock. Beide threads proberen om de twee locks te verkrijgen, maar in omgekeerde volgorde.

class Counter {
    public final Object readLock = new Object();
    public final Object writeLock = new Object();

    public volatile int value;
}

var counter = new Counter();
var inc = new Thread(() -> {
    for (int i = 0; i < 10_000; i++) {
        synchronized (counter.readLock) {
            synchronized (counter.writeLock) {
                counter.value++;
            }
        }
    }
});
var dec = new Thread(() -> {
    for (int i = 0; i < 10_000; i++) {
        synchronized (counter.writeLock) {
            synchronized (counter.readLock) {
                counter.value--;
            }
        }
    }
});

inc.start(); dec.start();
inc.join(); dec.join();

System.out.println(counter.value);

In sommige gevallen kan dat leiden tot een deadlock, namelijk wanneer een thread onderbroken wordt tussen het verkrijgen van beide locks:

Thread `inc`	Thread `dec`
acquire readLock
	acquire writeLock
	wait (forever) for readLock …
wait (forever) for writeLock…

Er is geen eenvoudige manier om deadlocks te vermijden, behalve de applicatie erg zorgvuldig te ontwerpen. Enkele technieken die hierbij kunnen helpen zijn:

niet meer locken dan strikt noodzakelijk
locks altijd in een welbepaalde volgorde verkrijgen
timeouts gebruiken

Immutability

Wanneer we praten over concurrency, is het een goed idee om ook immutability te vermelden. Een immutable object kan nooit van waarde wijzigen: eens aangemaakt blijven alle waardes hetzelfde. In de praktijk betekent dat dat alle velden van het object als final gedeclareerd worden.

Wanneer meerdere threads eenzelfde immutable object gebruiken, kunnen er per definitie geen race condities optreden; ook beschikt elke thread altijd over de laatste waarde (volatile is dus niet nodig). Wanneer mogelijk, gebruik je dus best immutable objecten in een applicatie met concurrency. Records zijn uiterst geschikt om eenvoudig dergelijke immutable objecten te maken, en gaan dus goed samen met concurrency!

Concurrent data structures

Zoals we hierboven gezien hebben, is niet elke klasse automatisch geschikt om (correct) door meerdere threads tegelijk gebruikt te worden. Ook de ingebouwde collectie-types (bv. ArrayList, LinkedList) zijn niet thread-safe. Je kan een thread-safe collectie verkrijgen door hulpfuncties in de Collections-klasse, bijvoorbeeld Collections.synchronizedList(unsafeList). Dat geeft een view op de gegeven collectie terug waarvan alle methodes synchronized zijn. Dat houdt in de praktijk dus in dat de collectie op elk moment slechts door 1 thread gebruikt kan worden. Bovendien, wanneer je itereert over de elementen in de collectie, bijvoorbeeld via een iterator of stream (zie later), moet het gebruik van die iterator ook in een sycnhronized blok staan (met de collectie als object), zodat de lijst niet aangepast kan worden tijdens het itereren. Omdat ook een foreach-lus een iterator gebruikt, moet die lus ook in een synchronized-blok staan:

List myList = Collections.synchronizedList(new ArrayList<E>());
...
synchronized(myList) {
  var it = myList.iterator();
  while (it.hasNext()) {
    ...
  }
}
...
synchronized(myList) {
  for (var element : myList) {
    ...
  }
}

Bovenop die manier om ‘gewone’ collecties thread-safe te maken, zijn er ook implementaties die specifiek ontworpen zijn voor concurrency. Bijvoorbeeld, een CopyOnWriteArrayList is een thread-safe lijst, geschikt voor wanneer er veel vaker gelezen wordt uit de lijst dan dat er naar geschreven wordt. Deze implementatie dan is efficiënter dan een gewone ArrayList die gesynchroniseerd wordt via de synchronizedList-hulpfunctie. Zoals de naam zegt wordt de onderliggende array nooit aangepast, maar wel volledig gekopieerd elke keer ernaar geschreven wordt. Het voordeel is dat lezen kan zonder enige synchronizatie, omdat de inhoud van de array zelf nooit meer aangepast wordt.

Er bestaat ook een ConcurrentHashMap, die een thread-safe Map implementeert. Ook hier is deze efficiënter dan een gesynchroniseerde Map, omdat nooit de hele datastructuur gelockt wordt.

High-level concurrency abstractions

Totnogtoe hebben we steeds zelf threads aangemaakt. Zoals eerder vermeld komt elke thread echter met een redelijk grote overhead, en wordt het al snel complex om bij te houden welke threads we hebben en hoeveel er zijn. We willen daarom de gebruikte threads makkelijk kunnen beheren.

Executor

Java biedt enkele hoog-niveau abstracties aan om te werken met threads. De basisklasse daarvoor is een Executor. Deze ontkoppelt de taak die uitgevoerd moet worden van de thread waarin die uitgevoerd wordt. Aan een Executor kan je dus Runnable’s (of lambda’s of method references) geven die uitgevoerd moeten worden, zonder zelf de threads te beheren. Er is ook een subinterface ExecutorService die enkele methodes toevoegt, bijvoorbeeld het afsluiten van een executor. Tenslotte is er de ScheduledExecutorService die methodes toevoegt om taken te plannen (bijvoorbeeld uitvoeren na een bepaalde tijd, eenmalig of herhaald).

Vaak willen we het aantal threads dat gebruikt wordt beperken, bijvoorbeeld tot ongeveer het aantal aanwezige processoren of cores. Dat kan met een ThreadPool: een verzameling van threads die, eenmaal aangemaakt, herbruikt kunnen worden. Er is een ThreadPoolExecutor die exact dat doet. Je kan die zelf aanmaken, maar dat kan makkelijker via hulpmethodes in de Executors klasse. Bijvoorbeeld:

var pool = Executors.newFixedThreadPool(5);
pool.submit(() -> someTask());
pool.submit(() -> someOtherTask());
...
pool.close(); // wacht tot alle taken afgelopen zijn.

maakt een ExecutorService aan met ten hoogste vijf threads. Nieuwe taken die aangeboden worden wanneer alle vijf threads bezig zijn met andere taken, belanden in een wachtrij tot ze aan de beurt zijn. Met de close-methode zorg je ervoor dat er geen nieuwe taken meer kunnen bijkomen, en wacht je tot alle bestaande taken afgelopen zijn.

Er zijn ook andere varianten die je kan aanmaken via de Executors-klasse, bijvoorbeeld

newCachedThreadPool: herbruikt threads indien voorhanden, en maakt anders een nieuwe thread aan. Threads zonder werk worden na een bepaalde tijd beëindigd.
newSingleThreadExecutor: een executor met slechts één thread die al het aangeboden werk (na elkaar) uitvoert.
newSingleThreadScheduledExecutor: zelf de als hierboven, maar dan met een ScheduledExecutor als resultaat. Hiermee kan je dus bijvoorbeeld taken op regelmatige tijdstippen uitvoeren.

Het aanmaken en vervolgens wachten op alle taken kan ook via een zogenaamd try-with-resources statement. Dat is een eenvoudige manier om te wachten op alle taken en ervoor te zorgen dat de pool altijd afgesloten wordt, ook als er exceptions gegooid worden. (Een try-with-resource statement kan in Java ook voor andere zaken gebruikt worden, in het bijzonder met resources die na gebruik terug gesloten moeten worden, bijvoorbeeld een bestand.)

try (var pool = Executors.newFixedThreadPool(5)) {
  pool.submit(() -> someTask());
  pool.submit(() -> someOtherTask());
}
// de pool is hier gesloten, en alle taken zijn uitgevoerd.

Fork-Join pool

Een fork-join pool is een specifiek type Executor voor taken die (recursief) nieuwe subtaken genereren. Deze subtaken worden dan mee opgenomen in de lijst van uit te voeren taken. Een fork-join pool is vooral nuttig wanneer de taken onafhankelijk van elkaar zijn, en achteraf gecombineerd worden. Er wordt gebruik gemaakt van work stealing: threads in de pool die niets meer te doen hebben, kunnen subtaken beginnen uitvoeren die gegenereerd werden door een andere thread.

We gaan hier niet verder in op het gebruik van een fork-join pool.

Testen van concurrent code

Het testen of bepaalde code thread-safe is, is allesbehalve eenvoudig. Ten eerste moeten we de tests uitvoeren met meerdere threads; concurrency-problemen zijn immers veelal onzichtbaar als er maar één thread in het spel is. Bovendien is een correct resultaat na één uitvoering van de test geen garantie dat de code ook correct is. Er kan immers een probleem zijn dat niet tot uiting kwam bij die specifieke uitvoering (met andere woorden, bij die specifieke interleaving van de threads), maar dat zich wel zou manifesteren bij een andere uitvoeringsvolgorde. De test meerdere keren herhalen kan in zo’n gevallen soelaas bieden.

In Java kunnen we gebruik maken van een library zoals jcstress. Deze library laat toe om testcode te schrijven die onder verschillende regimes uitgevoerd wordt, om zo de kans te vergroten dat thread safety problemen (bv. race-condities) aan het licht komen. De jcstress library wordt ook gebruikt om de concurrency-aspecten van de implementatie van de Java Virtual Machine zelf te testen.

jcstress toevoegen aan je project

Voeg volgende regel toe aan de plugins sectie van je build.gradle:

plugins {
    ...
    id 'io.github.reyerizo.gradle.jcstress' version '0.8.15'
}

Zorg ervoor dat IntelliJ je nieuwe Gradle-configuratie verwerkt (klik op het olifantje dat verschijnt).

In je project maak je nu een extra folder onder src, namelijk src/jcstress, en daaronder een folder src/jcstress/java. Voeg deze java folder toe als ‘Sources root’: rechtsklik op de java folder > Mark Directory As > Sources root. IntelliJ zou de folder nu blauw moeten kleuren.

Anatomie van een jcstress test

Een test in jcstress maakt geen gebruik van JUnit-annotaties (@Test etc), maar van een eigen set van annotaties. Hier vind je een voorbeeld en wat meer uitleg over de betekenis annotaties. We bespreken de belangrijkste annotaties ook hieronder, met als voorbeeld het testen van onze originele Counter-klasse.

package demo;

import org.openjdk.jcstress.annotations.*;
import org.openjdk.jcstress.infra.results.I_Result;

@JCStressTest
@Outcome(id="0", expect = Expect.ACCEPTABLE, desc = "Incremented and decremented atomically")
@Outcome(id="", expect = Expect.FORBIDDEN, desc = "Unexpected counter value")
@State
public class CounterTest {

    private final Counter counter = new Counter();
    private final int N = 5;

    @Actor
    public void incrementer() {
        for (int i = 0; i < N; i++) {
            counter.increment();
        }
    }

    @Actor
    public void decrementer() {
        for (int i = 0; i < N; i++) {
            counter.decrement();
        }
    }

    @Arbiter
    public void arbiter(I_Result result) {
        result.r1 = counter.getCount();
    }

}

We zien in de test hetvolgende:

De annotatie @JCStressTest duidt aan dat het om een jcstress-test gaat
De annotatie @State geeft aan in welke klasse we de te testen state-variabelen vinden; hier is dat de variabele counter, in de CounterTest klasse zelf. Het object met @State zal erg vaak aangemaakt worden, en moet voldoen aan bepaalde voorwaarden (bv. publieke constructor zonder argumenten).

We negeren @Outcome nog even, en kijken naar de actoren en arbiter:

Elke methode met @Actor staat voor de code die door één thread uitgevoerd wordt. Hier hebben we 2 verschillende actoren: eentje die de teller N keer verhoogt, en een andere die de teller N keer verlaagt. Het jcstress framework zal de actoren uitvoeren met zoveel mogelijk verschillende interleavings, in de hoop zo eventuele problemen bloot te leggen.
De methode met @Arbiter (gewoonlijk 1 per test) wordt uitgevoerd nadat alle actoren helemaal klaar zijn. De arbiter bezorgt de data waaraan we kunnen zien of er zich een probleem voorgedaan heeft. In dit geval kijken we naar de waarde van de counter na afloop van de verhogingen en verlagingen. We kennen die counter-waarde toe aan attribuut r1 van het resultaat-object. Dat heeft type I_Result, wat staat voor een resultaat met 1 integer (I). Er zijn ook andere types beschikbaar in de library, bv. II_Result (2 integers), DBI_Result (een double, een byte, en een integer), etc.

Letters in Result-type

Volgende letters worden gebruikt in de types van de Result-objecten:

I: int
Z: boolean
F: float
J: long
S: short
B: byte
C: char
D: double
L: object

Opmerking

Het is niet strikt noodzakelijk om een @Arbiter-methode te hebben. Je kan ook één van de @Actor-methodes een result-parameter geven en zonder arbiter werken.

Tenslotte bespreken we de @Outcome-annotaties. Die geven aan welke resultaat-objecten verwacht/acceptabel zijn en welke niet. In het voorbeeld hierboven:

Een resultaat met r1=0 is acceptabel; dat is wat we verwachten van een thread-safe counter. Dat geven we aan met @Outcome(id="0", expect = Expect.ACCEPTABLE, ...). Merk op dat de id parameter het verwachte resultaat (uit de I_Result parameter) voorstelt.
Elk ander resultaat is niet toegelaten: @Outcome(id="", expect = Expect.FORBIDDEN, ...).

Als we een resultaat met meerdere waarden zouden hebben (bv. een II_Result) dan specifiëren we de outcome bijvoorbeeld als @Outcome(id="0, 1", ...), wat overeenkomt met r1=0 en r1=1.

Tests uitvoeren

Je kan de tests uitvoeren via de jcstress taak in Gradle: ./gradlew jcstress.

Dit genereert uitvoer op de console, en ook een html-bestand in build/reports/jcstress. Daarin vinden we een tabel zoals onderstaande, die aangeeft hoe vaak elk resultaat bekomen werd:

We zien hieruit duidelijk dat onze counter niet thread-safe is: alle waarden van -5 tot 5 werden bekomen in sommige tests.

Oefeningen

Zie oefeningen.

Oefeningen

Volatile (1)

Waarom zou je niet elke variabele als volatile markeren?

Antwoord

Dat zou als voordeel hebben dat je meer zichtbaarheisgaranties hebt, maar dit komt wel met een belangrijke kost: veel performantie-optimalisaties die gebruik maken van een lokale cache worden zo teniet gedaan, en je programma wordt dus trager. Bovendien heb je met volatile variabelen nog steeds geen thread safety; je moet nog steeds synchronisatie toevoegen.

Volatile (2)

We zagen in de uitleg bij het synchroniseren met semaforen dat deze ook zichbaarheidsgaranties bieden, net zoals volatile. Is in onderstaand voorbeeld het volatile keyword dan nog nuttig? Waarom (niet)?

import java.util.concurrent.Semaphore;

class Counter {
    private volatile int count = 0;
    private final Semaphore sem = new Semaphore(1);

    public synchronized void increment() {
        try {
            sem.acquire();
            count++;
            sem.release();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public void decrement() {
        try {
            sem.acquire();
            count--;
            sem.release();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public int getCount() {
        return count;
    }
}

Antwoord

Ja, volatile is nog steeds nuttig. Niet voor de increment- en decrement-methodes en alle andere code die daarvan gebruik maakt (de semafoor geeft dezelfde garanties als volatile), maar wel voor het gebruik van count in de getCount-methode. Zonder volatile heb je geen garantie dat verschillende threads dezelfde/de meest recente waarde van de counter zouden uitlezen.

Volatile (3)

Welke zichtbaarheidsgaranties krijg je bij een volatile variabele met een lijst als type, bijvoorbeeld private volatile ArrayList<Element> myList?

Antwoord

De zichtbaarheidsgaranties gaan enkel over de referentie (pointer) naar de lijst, die in variabele myList zit. Met andere woorden: variabele myList wijzigen zodat die naar een andere lijst verwijst (myList = new ArrayList<>()) zal steeds meteen zichtbaar zijn voor andere threads. Maar: wijzigingen in de lijst zelf (bv. elementen toevoegen of van plaats veranderen) zijn niet automatisch zichtbaar voor andere threads.

Synchronized

Waarom zou je niet gewoon elke methode van een klasse synchronized maken?

Antwoord

Als je dat doet, verlies je mogelijk veel van de voordelen van multithreading. Er kan immers op elk moment slechts één thread met je object werken; al de rest moet wachten, zelfs wanneer al die threads enkel lees-operaties zouden uitvoeren en er dus geen reden is om synchronisatie te gebruiken. Bovendien volstaat dit niet om thread-safe te zijn (zie het voorbeeld met het gebruik van de iterators).

Counter + jcstress

Pas de jcstress-test uit het voorbeeld aan om de thread-safe Counter-implementatie uit oefening 2 te testen.

Ticketverkoop

Hieronder vind je een klasse voor een ticket-verkoop met bijhorende zitplaatsen (bijvoorbeeld van een bioscoopzaal, vliegtuig, …). Deze bevat ook een main-methode die deze klasse gebruikt.

De main-methode simuleert hoe het BookingSystem door meerdere klanten tegelijk gebruikt wordt. We maken hierbij gebruik van een CyclicBarrier: een ander synchronisatie-primitief, waarmee je kan wachten tot een aantal threads hetzelfde punt bereikt hebben voor ze verder mogen gaan. We gebruiken dit om de grote toestroom te simuleren bij het openen van de ticketverkoop, door elke thread (klant) te laten wachten tot ook alle andere threads (klanten) klaar staan. Bekijk ook de andere concurrency-aspecten van deze code, zoals het gebruik van een thread pool en synchronized list.

Opmerking: voor de eenvoud maakt het niet uit welke zitjes een klant krijgt.

Voer de huidige versie uit. Wat zie je?
Maak deze klasse thread-safe, zodat meerdere klanten tegelijk tickets kunnen boeken zonder dezelfde zitplaatsen toegewezen te krijgen. Doe dit op de simpelste manier die je kan bedenken (hint: synchronized). Wat is het effect op de uitvoeringstijd? (De main-methode moet je niet aanpassen)
Probeer daarna om de oplossing efficiënter (maar nog steeds thread-safe) te maken. (De main-methode moet je niet aanpassen)

import java.util.*;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.Executors;

public class BookingSystem {

    private final String[] seats = {"A", "B", "C", "D", "E", "F"};
    private int availableTickets = seats.length;
    private final Map<String, String> seatAssignments = new HashMap<>();

    public boolean isAssigned(String seat) {
        return seatAssignments.containsKey(seat);
    }

    private void generateTicket(String seat, String customer) {
        // simulate that creating a ticket takes some time
        try {
            Thread.sleep(100);
        } catch (InterruptedException ignored) {
        }
    }

    public List<String> bookSeats(String customer, int requestedSeats) {
        if (requestedSeats > availableTickets)
            throw new IllegalStateException("Not enough seats available");

        // simulate that preprocessing takes a lot of time
        try {
            Thread.sleep(2000);
        } catch (InterruptedException ignored) {
        }

        List<String> seatsForCustomer = new ArrayList<>();
        int seatIndex = 0;
        while (seatsForCustomer.size() < requestedSeats) {
            String seat = seats[seatIndex];
            if (!isAssigned(seat)) {
                generateTicket(seat, customer);
                seatAssignments.put(seat, customer);
                seatsForCustomer.add(seat);
            }
            seatIndex++;
        }
        availableTickets -= requestedSeats;
        return seatsForCustomer;
    }

    public static void main(String[] args) {
        var nbCustomers = 20;
        var bookingSystem = new BookingSystem();
        var assignedSeats = Collections.synchronizedList(new ArrayList<String>());
        try (var executor = Executors.newFixedThreadPool(nbCustomers)) {
            // wait until all customers are ready: simulates opening ticket sales
            var ticketSalesOpening = new CyclicBarrier(nbCustomers);
            for (int i = 0; i < nbCustomers; i++) {
                final var customer = "Customer %02d".formatted(i);
                executor.execute(() -> {
                    try {
                        ticketSalesOpening.await();
                        var seats = bookingSystem.bookSeats(customer, 1);
                        System.out.println(customer + ": " + seats);
                        assignedSeats.addAll(seats);
                    } catch (IllegalStateException e) {
                        // no tickets left for customer
                    } catch (BrokenBarrierException | InterruptedException e) {
                        e.printStackTrace();
                    }
                });
            }
        }
        var uniqueSeats = new HashSet<>(assignedSeats);
        System.out.println((assignedSeats.size() - uniqueSeats.size()) + " overbookings.");
    }
}

Thread-safe cache

Hieronder vind je een Downloader-klasse die een (in-memory) cache gebruikt. Als de te downloaden URL nog niet in de cache zit, wordt die gedownload. Anders wordt de inhoud uit de cache teruggegeven.

In plaats van een echte URL te downloaden, wordt een download hier gesimuleerd door 1 seconde te wachten

import java.util.HashMap;
import java.util.Map;

public class Downloader {

    private final Map<String, String> cache = new HashMap<>();

    public String get(String url) {
        if (!cache.containsKey(url)) {
            var contents = download(url);
            cache.put(url, contents);
        }
        return cache.get(url);
    }

    private static String download(String url) {
        try {
            System.out.println("Downloading " + url + " (" + Thread.currentThread() + ")");
            Thread.sleep(1000); // 1 seconde
            return "Contents of " + url;
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }
}

Wat kan er gebeuren er als twee threads dezelfde URL op hetzelfde moment willen opvragen uit eenzelfde Downloader-object?
Zou een ConcurrentHashMap gebruiken in plaats van een gewone HashMap dit probleem oplossen?
Maak de klasse thread-safe, maar nog steeds zo efficiënt mogelijk (zodat threads nooit onnodig moeten wachten).
Maak ook een Client-klasse met een main-methode, waarin 4 threads elk 100 keer een random URL opvragen (gebruik een thread pool).
In plaats van echte URL’s kan je gewoon strings gebruiken. Hieronder vind je een methode die een willekeurige String uit de lijst van url’s teruggeeft:
```
public static final String[] urls = { "abc", "def", "ghi", "jkl", "mno", "pqr", "stu", "vwx", "yz" };
public static String randomURL() {
    return urls[new Random().nextInt(urls.length)];
}
```
Denkvraag: wat zouden de gevolgen zijn van een cleanup-thread toe te voegen aan je Downloader-klasse, die elke 5 seconden de cache helemaal leegmaakt?

7.5 Streams

In andere programmeertalen

De concepten in andere programmeertalen die het dichtst aanleunen bij Java streams zijn

ranges in C++
iterators, generators en comprehensions in Python
LINQ in C#

Wat en waarom?

Streams vormen een krachtig concept om efficiënt data te verwerken. Ze vormen een abstractie voor sequentiële en parallele operaties op datasets, zoals filteren, transformeren, en aggregeren, zonder de onderliggende datastructuur te wijzigen. Bovendien maakt het gebruik van streams het mogelijk om declaratief te programmeren: je beschrijft op hoog niveau wát je met de dataset wilt doen, in plaats van stap voor stap te beschrijven hoe dat moet gebeuren.

Een snel voorbeeldje om dat wat concreter te maken is onderstaande code, die streams gebruikt om de gemiddelde leeftijd te berekenen van de eerste 20 meerderjarige Person-objecten in de lijst people (we gaan later dieper in op de details):

List<Person> people = ...
var average = people.stream()
                .mapToInt(Person::age)
                .filter(a -> a >= 18)
                .limit(20)
                .average();
System.out.println(average.getAsDouble());

Een stream zelf is geen datastructuur of collectie; een stream is een pijplijn — een ketting van operaties die uitgevoerd moeten worden op de data. Die operaties kunnen de data filteren, transformeren, groeperen, reduceren, … Een stream stelt dus één grote bewerking voor op de data, samengesteld uit meerdere operaties. Elke stream bestaat uit 3 delen:

één bron voor de data (een stroom van data, vandaar de naam). Die bron kan een datastructuur zijn (bv. een array, ArrayList, HashSet, …), maar ook andere bronnen zijn mogelijk (bijvoorbeeld een oneindige sequentie van getallen, zoals de natuurlijke getallen). In het voorbeeld hierboven is de lijst people de bron.
intermediaire operaties (mogelijk meerdere na elkaar) die de data verwerken (transformeren). Elke operatie neemt het resultaat van de vorige operatie (of de bron) en doet daar iets mee; het resultaat daarvan dient als invoer voor de volgende operatie. Zo krijg je een pijplijn waar de data doorheen stroomt terwijl ze bewerkt wordt. In het voorbeeld hierboven zijn mapToInt, filter en limit intermediaire operaties.
één terminale operatie: deze beëindigt de ketting en geeft het uiteindelijke resultaat terug. In het voorbeeld hierboven is average de terminale operatie.

graph LR
Source --> Op1 --> Op2 --> Op3 --> Terminal
style Source stroke:black,fill:#afa
style Terminal stroke:black,fill:#faa

Je kan een stream-pijplijn slechts éénmaal doorlopen. Als je na het uitvoeren van de operaties nog een sequentie van operaties wil uitvoeren op dezelfde bron-elementen, moet je een nieuwe stream maken.

Streams zijn ook lazy: er worden slechts zoveel elementen verwerkt als nodig om het resultaat te berekenen. Dat maakt dat de bron oneindig veel elementen mag aanleveren; zolang de rest van de pijplijn er slechts een eindig aantal nodig heeft, vormt dat geen probleem. Enkel de elementen die nuttig zijn om het resultaat te bekomen worden gebruikt. We zullen hier later nog op terugkomen.

Een zeer concrete situatie waarin streams nuttig zijn, is wanneer je van plan bent om code te schrijven met volgende vorm:

Collection<E> source = ...
Type1 result = ...
Type2 temp_var = ...
for (E element : source) {
  update temp_var
  if (condition) {
    update result
  }
}
return result;

Dit patroon komt zeer vaak voor in code. Neem, als eenvoudig voorbeeld om te starten, de situatie uit het voorbeeld hierboven: de gemiddelde leeftijd berekenen van de eerste 20 meerderjarige personen in een lijst. Zonder streams zou je dat waarschijnlijk ongeveer als volgt schrijven (merk op hoe dit het patroon van hierboven volgt):

List<Person> people = ...
double average = 0;
int count = 0;
for (var person : people) {
    if (person.age() >= 18) {
        average += person.age();
        count++;
        if (count >= 20)
          break;
    }
}
average /= count;
System.out.println(average);

De versie met streams ziet er helemaal anders uit — je schrijft zelf geen lussen, maar focust je op het beschrijven van de uit te voeren operaties. Hier ter vergelijking nogmaals de code met streams:

List<Person> people = ...
var average = people.stream()
                .mapToInt(Person::age)
                .filter(a -> a >= 18)
                .limit(20)
                .average();
System.out.println(average.getAsDouble());

Beide versies doen hetzelfde, maar in de tweede versie is het veel duidelijker wat de bedoeling is:

neem eerst van elke persoon de leeftijd (mapToInt)
kijk dan enkel naar de leeftijden >= 18 (filter)
kijk vervolgens enkel naar de eerste 20 van die leeftijden (limit)
neem tenslotte het gemiddelde (average).

Deze manier van programmeren ligt veel dichter bij bijvoorbeeld SQL:

SELECT AVG(age)
FROM (
    SELECT age FROM Person
    WHERE age >= 18
    LIMIT 20
) AS limited_people;

Weetje

In C# is LINQ het equivalent van streams. Dat is een taal die erg nauw aansluit bij SQL. Het voorbeeld van hierboven kan er in C# als volgt uitzien:

var averageAge = (
    from p in people
    where p.Age >= 18
    select p.Age
).Take(20).Average();

Lambda functies en methode-referenties

Bij het gebruik van streams zal je veelvuldig gebruik maken van methode-referenties en lambda-functies.

Wat?

Stel dat we een record Person hebben:

record Person(String firstName, String lastName, int age) {
  public boolean isAdult() {
    return this.age() >= 18;
  }
}

Met lambda-functies kun je in Java kort en bondig een functie schrijven. Die functie heeft geen naam te geven; je zal ze typisch dus maar één keer gebruiken. Een lambda-functie in Java, die de voor- en achternaam van een persoon aan elkaar plakt met een spatie, ziet er bijvoorbeeld als volgt uit:

(Person p) -> p.firstName() + " " + p.lastName()

De -> wijst op een lambda-functie. Links ervan staan de parameters, rechts de body van de methode.

Je kan zo’n lambda-functie bijvoorbeeld gebruiken om een Comparator te maken die een lijst van personen sorteert volgens hun voor- en achternaam:

var people = new java.util.ArrayList<>(List.of(
                new Person("Jane", "Doe", 17),
                new Person("John", "Doe", 18),
                new Person("Alex", "Jones", 20)));
        people.sort(Comparator.comparing((Person p) -> p.firstName() + " " + p.lastName()));
        System.out.println(people);

Je hoeft niet expliciet te zeggen welk type p heeft; Java kan dat vaak zelf afleiden. Hetvolgende kan dus ook:

people.sort(Comparator.comparing(p -> p.firstName() + " " + p.lastName()));

Methode-referenties zijn een manier om direct te verwijzen naar een reeds bestaande methode, in plaats van er een lambda voor te schrijven. Waar je een lambda van de vorm (Person p) -> p.age() zou gebruiken, kun je ook gewoon Person::age schrijven. De :: wijst op een methode-referentie. Links ervan staat de naam van de klasse, rechts de naam van de (bestaande) methode. Merk op dat er geen haakjes staan (dus niet Person::age()). Het is enkel een verwijzing naar de methode; de methode zelf wordt niet meteen opgeroepen.

Een methode-referentie is vooral handig als de lambda precies één methode-aanroep doet. Achter de schermen gebeurt hetzelfde, maar de code is nog compacter. Om de lijst van people te sorteren volgens leeftijd, kan je dus ook een methode-referentie gebruiken als volgt:

people.sort(Comparator.comparing(Person::age));

Types van lambda’s en methode-referenties

Omdat Java een sterk getypeerde taal is, moeten lambda-functies en methode-referenties ook een type hebben. Dat gebeurt door een interface te definiëren. Elke interface met daarin precies één methode kan automatisch gebruikt worden als type voor lambda-functies en methode-referenties (als de types overeen komen). Als het expliciet de bedoeling is om de interface daarvoor te gebruiken, kan je die interface ook met @FunctionalInterface annoteren; de compiler komt dan klagen als je later een extra methode zou proberen toe te voegen. Bijvoorbeeld:

@FunctionalInterface
interface PersonPredicate {
  boolean test(Person person);
}

public List<Person> selectPeople(List<Person> people, PersonPredicate predicate) {
    List<Person> result = new ArrayList<>();
    for (Person p : people) {
      if (predicate.test(p)) {
        result.add(p);
      }
    }
    return result;
}

var people = List.of(
      new Person("Jane", "Doe", 17),
      new Person("John", "Doe", 18),
      new Person("Alex", "Jones", 20));

In de code hierboven zie je de PersonPredicate-interface, geannoteerd met @FunctionalInterface. Deze definieert één methode die true of false teruggeeft voor een persoon. De methode selectPeople gebruikt deze interface om alle personen te selecteren die voldoen aan de meegegeven voorwaarde.

Note

De implementatie van selectPeople voldoet aan het patroon van code waarvoor streams een oplossing kunnen bieden. Inderdaad, deze operatie komt overeen met de filter-methode op streams.

We overlopen nu 5 manieren om de selectPeople methode te gebruiken. Een eerste manier is een klasse maken (bv. IsAdult) die de interface implementeert, en die nagaat of de persoon meerderjarig is. Dat werkt, maar is nogal omslachtig:

/* [1] */
class IsAdult implements PersonPredicate {
  @Override
  public boolean test(Person person) {
    return person.isAdult();
  }
}
System.out.println(selectPeople(people, new IsAdult()));
// => [Person[firstName=Alex, lastName=Jones, age=20], Person[firstName=John, lastName=Doe, age=18]]

Een tweede optie is om een anonieme klasse te gebruiken. In het voorbeeld hieronder is dat een anonieme klasse die nagaat of de achternaam van de persoon begint met “Do”. Ook dat blijft omslachtig:

/* [2] */
System.out.println(selectPeople(people, new PersonPredicate() {
    @Override
    public boolean test(Person person) {
        return person.lastName().startsWith("Do");
    }
}));
// => [Person[firstName=Jane, lastName=Doe, age=17], Person[firstName=John, lastName=Doe, age=18]]

Met lambda-functies kan je dergelijke code veel eenvoudiger schrijven. In [3] en [4] hieronder zie je hoe je een lambda-functie kan gebruiken die hetzelfde doet als de vorige voorbeelden, maar dan zonder een klasse te schrijven. Merk op dat het toegelaten is om de lambda-functies te gebruiken waar een PersonPredicate verwacht wordt. De lambda-functies zijn inderdaad functies die een Person-object als argument hebben, en een boolean teruggeven, en komen dus qua type overeen met de test-methode in PersonPredicate.

/* [3] */
System.out.println(selectPeople(people, p -> p.isAdult()));
// => [Person[firstName=Alex, lastName=Jones, age=20], Person[firstName=John, lastName=Doe, age=18]]

/* [4] */
System.out.println(selectPeople(people, p -> p.lastName().startsWith("Do")));
// => [Person[firstName=Jane, lastName=Doe, age=17], Person[firstName=John, lastName=Doe, age=18]]

Tenslotte kunnen we ook een methode-referentie gebruiken:

/* [5] */
System.out.println(selectPeople(people, Person::isAdult));

Dat is vooral nuttig als er al een methode bestaat, of als de implementatie van de methode te omslachtig is om als lambda te schrijven.

Voorgedefinieerde types voor functies

In plaats van zelf een interface zoals PersonPredicate te schrijven, kan je vaak beroep doen op een voorgedefinieerde functie-interface. Je vindt de lijst daarvan in de documentatie. We lijsten hier de belangrijkste functionele interfaces op die gebruikt worden in de context van streams:

Function<T, R>: een functie met 1 argument, die een T omzet in een R. Er zijn ook varianten voor primitieve resultaat-types, zoals ToIntFunction<T>, die een T omzet in een int. Bijvoorbeeld:
```
Function<Person, String> getLowercaseName = person -> person.name().toLowerCase();
ToIntFunction<Person> getAge = Person::age;
```
Predicate<T>: een functie met 1 argument van type T, die true of false teruggeeft. Ook hier bestaan varianten voor primitieve types, bijvoorbeeld IntPredicate. Bijvoorbeeld:
```
Predicate<Person> isAdult = person -> person.age() >= 18;
IntPredicate isNonNegative = i -> i >= 0;
```

BiFunction<T, U, R>: een functie met 2 argumenten, die een T en een U omzet in een R. Bijvoorbeeld:

BiFunction<Person, Integer, String> f = (person, nbPets) -> "Person " + person.name() + " has " + nbPets + " pets";

UnaryOperator<T>: een operator met 1 argument van type T, en een resultaat van type T. Dit is dus een speciaal geval van een Function, namelijk een Function<T, T>. Bijvoorbeeld:
```
UnaryOperator<String> indentOnce = s -> "  " + s;
```
BinaryOperator<T>: een functie met 2 argumenten, beide van type T, die een T teruggeeft. Dit is dus een speciaal geval van een BiFunction, namelijk een BiFunction<T, T, T>. Bijvoorbeeld:
```
BinaryOperator<String> joinWithSpace = (s1, s2) -> s1 + " " + s2;
```
Supplier<T>: een operatie zonder argumenten, die een T teruggeeft. Een invocatie van de supplier mag telkens hetzelfde of een ander object teruggeven. Een supplier kan dus gebruikt worden als generator. Bijvoorbeeld:
```
Supplier<String> constant = () -> "Hello";
Random rnd = new Random();
Supplier<Integer> randomInt = rnd::nextInt();
```
Consumer<T>: een operatie met 1 argument van type T, met een void return type. De consumer ‘verbruikt’ het meegegeven object, zonder een resultaat terug te geven. Bijvoorbeeld:
```
Consumer<Person> printPerson = (person) -> System.out.println(person.name() + " (age " + person.age() + ")");
```

BiConsumer<T, U>: een consumer met 2 argumenten van type T en U, die niets teruggeeft. Bijvoorbeeld:

BiConsumer<Person, Integer> printNTimes = (person, n) -> {
  for (int i = 0; i < n; i++)
    System.out.println(person.name() + " (age " + person.age() + ")");
};

Streams aanmaken

Een stream van T-objecten wordt aangeduid met de interface Stream<T>. Voor streams van primitieve types zijn er ook specifieke interfaces, bijvoorbeeld IntStream, DoubleStream, …

Om een stream aan te maken, start je steeds met een bron voor de data die verwerkt zal worden. Dat kan op verschillende manieren.

Je kan eenvoudig een stream maken van alle elementen in een collectie: elke collectie heeft een .stream() operatie die een stream teruggeeft van alle elementen. Dit is de meest courante manier om te werken met streams. Merk op dat een stream zelf geen datastructuur is, en dus ook geen elementen bevat. Een stream lijkt dus meer op een iterator (die de elementen uit de bron een voor een teruggeeft, maar deze niet zelf bevat) dan op een collectie.
```
people.stream()
```
Stream.of(T t1, T t2, ...) maakt een stream met als data exact de opgegeven objecten. Gelijkaardig kan je bijvoorbeeld ook IntStream.of(int i1, int i2, ...) gebruiken voor een stream van getallen.
```
Stream.of(person1, person2, person3)
```
Specifiek voor IntStream is er ook IntStream.range en IntStream.rangeClosed om een IntStream te maken van alle getallen in een bepaald bereik.
```
IntStream.range(2, 6)       // => 2, 3, 4, 5
IntStream.rangeClosed(2, 6) // => 2, 3, 4, 5, 6
```

Om een stream te maken van een array, gebruik je Arrays.stream(arr).

String[] names = { "Alice", "Bob", "Eve"};
Arrays.stream(names)

Stream.concat(s1, s2) maakt een nieuwe stream door twee streams samen te voegen: eerst komen alle elementen van de eerste stream, daarna die van de tweede stream. Opnieuw is er ook een gelijkaardige operatie op IntStream.
```
IntStream.concat(IntStream.range(2, 4), IntStream.range(10, 12)) // => 2, 3, 10, 11
```

Stream.generate(supplier) maakt een stream waarbij de elementen aangeleverd worden door de meegegeven Supplier. Die dient dus als generator voor nieuwe elementen.

Stream.generate(() -> "Hello") // => "Hello", "Hello", "Hello", "Hello", ...

Random rnd = new Random();
Stream.generate(() -> rnd.nextBoolean()) // => true, false, true, true, true, false, false, true, false, ...

Stream.iterate(seed, unaryOp) maakt een stream waarvan de elementen gegenereerd worden door unaryOp herhaald toe te passen, beginnend bij seed. De elementen van de stream zijn dus seed, unaryOp(seed), unaryOp(unaryOp(seed)), .... Dit is bijvoorbeeld een (oneindige) stream van alle strikt positieve getallen¹:
```
Stream.iterate(1, (n) -> n + 1) // => 1, 2, 3, 4, ...
```
Je kan ook een stream maken via een StreamBuilder, die je maakt via Stream.builder(). Dat laat toe om elementen één voor één toe te voegen (via add(...)), en daar uiteindelijk een stream van te maken via de build()-methode. Deze manier geeft je veel controle en is daardoor zeer flexibel, maar zal slechts zeer uitzonderlijk nodig zijn.
```
var builder = Stream.<String>builder();
builder.add(str1);
builder.add(str2);
var stream = builder.build(); // => str1, str2
```

Tussentijdse (intermediate) operaties

Tussentijdse (intermediate) operaties worden uitgevoerd op een stream, en geven een nieuwe stream terug. De elementen in de nieuwe stream zijn gebaseerd op die van de originele stream, na het toepassen van de operatie. Je kan de operaties dus na elkaar toepassen om een pijplijn te definiëren (dat is precies de bedoeling van een stream). Het voorbeeld van daarstraks toont 3 tussentijdse operaties die na elkaar toegepast worden: mapToInt, filter, en limit (average is een terminale operatie; zie later).

var average = people.stream()
                .mapToInt(Person::age)
                .filter(a -> a >= 18)
                .limit(20)
                .average();

We bespreken hier de meest voorkomende bewerkingen.

filter

De filter-operatie filtert sommige data-elementen uit de stream: enkel de elementen die voldoen aan het meegegeven predicaat worden verder doorgegeven. Bijvoorbeeld, onderstaande filter-operatie verwijdert alle klinkers uit een stream van letters:

Stream.of("A", "B", "C", "D", "E", "F").filter(l -> !"AEIOUY".contains(l)) // => B, C, D, F

block-beta
columns 1
block:in
  A  B  C  D  E  F
end
arrow<["filter"]>(down)
block:out
  space BB["B"] CC["C"] DD["D"] space FF["F"]
end
classDef str stroke:black,fill:orange
class in,out str

map, mapToInt, mapToLong, mapToDouble, mapToObject

De map-operatie transformeert elk elementen in een stream naar een ander element door een functie toe te passen op elk element. Bijvoorbeeld, onderstaande map-operatie zet alle strings om naar lowercase:

Stream.of("ALICE", "Bob", "ChaRLIe").map(String::toLowerCase) // => "alice", "bob", "charlie"

block-beta
columns 1
block:in
ALICE Bob ChaRLIe
end
arrow<["map"]>(down)
block:out
alice bob charlie
end
classDef str stroke:black,fill:orange
class in,out str

In tegenstelling tot de filter-operatie kan de map-operatie het type van de elementen in de stream veranderen. Bijvoorbeeld, onderstaande code vertrekt van een stream van Strings, en eindigt met een stream van Integer-objecten:

Stream.of("ALICE", "Bob", "ChaRLIe").map(String::toLowerCase).map(String::length) // => 5, 3, 7

block-beta
columns 1
block:in
ALICE Bob ChaRLIe
end
arrow<["map"]>(down)
block:out
alice bob charlie
end
arrow2<["map"]>(down)
block:out2
5 3 7
end
classDef str stroke:black,fill:orange
class in,out,out2 str

Er zijn ook specifieke map-operaties voor wanneer het resultaat een int, long, of double is. Bijvoorbeeld, mapToInt geeft een IntStream terug.

Stream.of("ALICE", "Bob", "ChaRLIe").mapToInt(String::length) // => 5, 3, 7

Bij een IntStream, LongStream en DoubleStream geeft de map-operatie altijd opnieuw een stream van hetzelfde type (IntStream, LongStream, of DoubleStream). Wanneer je de getallen in zo’n stream wil omzetten naar een object, kan dat met mapToObject:

IntStream.of(1, 2, 3).mapToObject(i -> "Number " + i) // => "Number 1", "Number 2", "Number 3"

limit en takeWhile

De limit-operatie beperkt de resultaat-stream tot de eerste $ n $ elementen van de bron-stream:

Stream.of("A", "B", "C", "D", "E", "F").limit(3) // => A, B, C

block-beta
columns 1
block:in
  A B C D E F
end
arrow<["limit"]>(down)
block:out
 AA["A"] BB["B"] CC["C"] space:3
end
classDef str stroke:black,fill:orange
class in,out str

Merk op dat de plaats van limit (zoals die van de meeste tussentijdse operaties trouwens) belangrijk is:

Stream.of("A", "B", "C", "D", "E", "F")
    .filter(l -> !"AEIOUY".contains(l))
    .limit(3)
// => B, C, D

is iets anders dan

Stream.of("A", "B", "C", "D", "E", "F")
    .limit(3)
    .filter(l -> !"AEIOUY".contains(l))
// => B, C

De eerste variant resulteert in de eerste 3 medeklinkers uit de oorspronkelijke stream (je filtert eerst alle klinkers eruit, en neemt dan de eerste 3 overblijvende elementen). In de tweede variant begin je met de eerste 3 letters, en filtert daaruit dan de klinkers weg.

Soms ken je het aantal elementen niet, maar wil je elementen blijven doorgeven zolang aan een bepaalde voorwaarde voldaan is. Dat kan met takeWhile. Merk op dat takeWhile niet hetzelfde is als filter: eenmaal de voorwaarde niet meer voldaan is, worden de volgende elementen niet meer bekeken, ook al zouden die opnieuw voldoen aan de voorwaarde.

Stream.of("Alpha", "Bravo", "Charlie", "Delta").takeWhile(s -> s.length < 6) // => "Alpha", "Bravo"

block-beta
columns 1
block:in
  Alpha Bravo Charlie Delta
end
arrow<["takeWhile"]>(down)
block:out
 AA["Alpha"] BB["Bravo"] space:2
end
classDef str stroke:black,fill:orange
class in,out str

skip en dropWhile

De skip-operatie doet het omgekeerde van limit: ze slaat de eerste $ n $ elementen over.

Stream.of("A", "B", "C", "D", "E", "F").skip(3) // => D, E, F

block-beta
columns 1
block:in
  A B C D E F
end
arrow<["skip"]>(down)
block:out
 space:3 DD["D"] EE["E"] FF["F"]
end
classDef str stroke:black,fill:orange
class in,out str

De dropWhile-operatie is het omgekeerde van takeWhile: ze negeert elementen zolang aan een gegeven voorwaarde voldaan is.

Stream.of("Alpha", "Bravo", "Charlie", "Delta").dropWhile(s -> s.length < 6) // => "Charlie", "Delta"

block-beta
columns 1
block:in
  Alpha Bravo Charlie Delta
end
arrow<["dropWhile"]>(down)
block:out
 space:2 CC["Charlie"] DD["Delta"]
end
classDef str stroke:black,fill:orange
class in,out str

distinct

De distinct-operatie filtert alle dubbele waarden uit de stream. Deze operatie is stateful: de waarden die reeds gezien zijn moeten bijgehouden worden.

Stream.of("A", "B", "A", "C", "A", "D").distinct() // => A, B, C, D

block-beta
columns 1
block:in
  A B A2["A"] C A3["A"] D
end
arrow<["distinct"]>(down)
block:out
 AA["A"] BB["B"] space CC["C"] space DD["D"]
end
classDef str stroke:black,fill:orange
class in,out str

sorted

De sorted-operatie sorteert de waarden in de stream. Deze operatie is stateful (de reeds geziene waarden moeten bijgehouden worden om ze gesorteerd terug te geven), en de operatie vereist ook dat de stream eindig is. Het sorteren kan immers pas uitgevoerd worden wanneer alle elementen gekend zijn.

Stream.of("C", "D", "A", "F", "E", "B").sorted() // => A, B, C, D, E, F

block-beta
columns 1
block:in
  C D A F E B
end
arrow<["sorted"]>(down)
block:out
 AA["A"] BB["B"] CC["C"] DD["D"] EE["E"] FF["F"]
end
classDef str stroke:black,fill:orange
class in,out str

peek

De peek-operatie doet eigenlijk niets: ze geeft alle elementen gewoon door, maar laat toe om een functie uit te voeren voor elk element. Deze operatie kan bijvoorbeeld handig zijn om te debuggen: je kan ze middenin een pijplijn toevoegen om te kijken welke elementen daar voorbijkomen.

Stream.of("A", "B", "C", "D", "E", "F")
   .limit(3)
   .peek(System.out::println) // => A, B, C
   .filter(l -> !"AEIOUY".contains(l))

block-beta
columns 1
block:in
  A B C D E F
end
arrow<["limit"]>(down)
block:out
 AA["A"] BB["B"] CC["C"] space:3
end
arrow2<["peek"]>(down)
block:out2
 AAA["A"] BBB["B"] CCC["C"] space:3
end
arrow3<["filter"]>(down)
block:out3
 space BBBB["B"] CCCC["C"] space:3
end
classDef str stroke:black,fill:orange
class in,out,out2,out3 str

flatMap

De flatMap operatie is gelijkaardig aan de map-operatie, maar wordt gebruikt wanneer het resultaat van de map-functie op één element opnieuw een stream geeft. Opnieuw bestaan er specifieke versies flatMapToInt, flatMapToLong, en flatMapToDouble voor wanneer het resultaat een IntStream, LongStream of DoubleStream moet worden.

We gebruiken de String::chars methode als voorbeeld; die geeft voor een String een IntStream terug met de char-values van elk karakter (denk: de ASCII of Unicode-waarde van elke letter).

Als we gewoon map zouden toepassen, krijgen we een stream van streams (hier: een stream van 3 streams, elk met 2 elementen):

Stream<IntStream> result = Stream.of("Aa", "Bb", "Cc").map(String::chars);
// => ['A', 'a'], ['B', 'b'], ['C', 'c']

block-beta
columns 1
block:in
  Aa Bb Cc
end
arrow<["map"]>(down)
block:out
 columns 3
 block:blockA
  columns 2
  A a
 end
 block:blockB
  columns 2
  B b
 end
 block:blockC
  columns 2
  C c
 end
end
classDef str stroke:black,fill:orange
classDef str2 stroke:red,fill:yellow
class in,out str
class blockA,blockB,blockC str2

Vaak is dat niet wat we willen: stel dat we één lange stream van char-waarden (ints) willen maken, met daarin de karakters van alle woorden uit de oorspronkelijke stream na elkaar. In dat geval gebruiken we flatMap (of, in dit geval, flatMapToInt omdat chars een IntStream teruggeeft):

IntStream result = Stream.of("Aa", "Bb", "Cc").flatMapToInt(String::chars); 
// => 'A', 'a', 'B', 'b', 'C', 'c'

block-beta
columns 1
block:in
  Aa Bb Cc
end
arrow<["flatMap"]>(down)
block:out
 columns 6
  A a
  B b
  C c
end
classDef str stroke:black,fill:orange
class in,out str

flatMap maakt dus in zekere zin een combinatie van een gewone map-operatie (die telkens een stream teruggeeft voor elk element), gevolgd door een concatenatie van al die resulterende streams. De naam komt van het feit dat de resulterende structuur een ‘flattened’ versie is, waarbij één niveau van nesting weggehaald werd: waar map een stream van streams oplevert (bv. Stream<IntStream>), krijgen we bij flatMap (of hier flatMapToInt) één gewone stream terug (hier een IntStream).

mapMulti

De mapMulti operatie kan je gebruiken wanneer elk object in de bronstream kan leiden tot meerdere objecten in de doelstream, net zoals bij flatMap. In tegenstelling tot flatMap, waar de mapping-operatie een stream moet teruggeven, werkt mapMulti anders. Je moet hier namelijk geen stream teruggeven. Aan mapMulti geef je een BiConsumer mee; dat is een functie met 2 argumenten (we noemen die hier value en output):

Het eerste argument (value) is het element uit de bronstream waarvoor de overeenkomstige elementen in de doelstream bepaald moeten worden
Het tweede argument (output) is een Consumer-functie: elk element wat je daaraan doorgeeft (via de accept-methode), komt terecht in de doelstream.

De functie die meegegeven wordt aan mapMulti moet dus alle objecten bepalen die voor het gegeven bronobject (value) in de doelstream terecht moeten komen, en die één voor één doorgeven aan output.

Een voorbeeld maakt dit hopelijk wat duidelijker. Stel dat we de lijst $ [1, 2, 3] $ willen omzetten in $ [1, 2, 2, 3, 3, 3] $: elk getal in de bronstream wordt even vaak als zijn waarde herhaald in de doelstream. We zouden dat met flatMap kunnen doen, door telkens een stream te maken van het juiste aantal elementen. Dat doen we hieronder door een oneindige stream te maken (via generate) van telkens hetzelfde element (value), en dan elk van die streams te beperken tot de eerste value elementen:

IntStream.range(1, 4) // => 1 2 3
         .flatMap( (value) -> IntStream.generate(() -> value).limit(value) ) // => 1 2 2 3 3 3

Dankzij de laziness van streams (zie later) moeten we niet bang zijn dat de oneindige stream zal leiden tot een oneindige uitvoeringstijd; het aantal elementen dat we gebruiken wordt beperkt door de limit-operatie, en er zullen er nooit meer dan dat gegenereerd worden.

De versie met mapMulti ziet er wat anders (en misschien vertrouwder) uit — hier kunnen we gewone imperatieve code (lussen) schrijven:

IntStream.range(1, 4) // => 1 2 3
          .mapMulti((value, output) -> {
              for (int i = 1; i <= value; i++) {
                  output.accept(value);
              }
          }) // => 1 2 2 3 3 3

block-beta
columns 1
block:in
  AA["1"] BB["2"] CC["3"]
end
arrow<["mapMulti"]>(down)
block:out
  A1["1"]
  B1["2"]
  B2["2"]
  C1["3"]
  C2["3"]
  C3["3"]
end
classDef str stroke:black,fill:orange
classDef aa stroke:black,fill:#afa
classDef cc stroke:black,fill:#aaf
class AA,A1 aa
class CC,C1,C2,C3 cc
class in,out str

Terminale (terminal) operaties

Een terminale operatie staat op het einde van de pijplijn, na alle tussentijdse operaties. Na een terminale operatie kunnen dus geen extra operaties meer uitgevoerd worden met de elementen uit de stream.

De voorbeelden hierboven hadden geen terminale operaties. Een stream zonder terminale operatie doet niets: er wordt geen enkel element verwerkt, en er wordt geen enkele tussentijdse operatie uitgevoerd. Het is de terminale operatie die alle verwerking in gang zet. De reden daarvoor is de laziness van streams.

Laziness (luiheid)

We zeiden eerder al dat streams lazy zijn. Dat houdt in dat de gedefinieerde operaties niet uitgevoerd worden, tenzij het echt niet anders kan.

Bekijk bijvoorbeeld onderstaande code:

var list = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

Stream<Integer> incrementAll = list.stream()
  .map(n -> {
    System.out.println("Processing " + n);
    return n + 1;
  })
  .limit(1);

// [1] hier werd nog niets uitgeprint

incrementAll
  .forEach(n -> {
    System.out.println("Got " + n);
});

// [2] print "Processing 1" en vervolgens "Got 2"

We maken een lijst van 10 getallen, voeren map uit op een stream van die getallen, en beperken het resultaat tot het eerste element. Aangekomen op punt [1] werd er, misschien verrassend, helemaal niets uitgeprint. Dat betekent dat de lambda-functie die $ n $ met 1 verhoogt ook niet uitgevoerd werd: er gebeurde helemaal niets met de getallen uit de lijst. We definiëren met streams enkel de pijplijn: wat moet er later eventueel gebeuren met de getallen?

Pas wanneer we op punt [2] komen, en de terminale operatie forEach (zie later) uitgevoerd werd, werd er voor de eerste keer “Processing 1” uitgeprint. Maar dan enkel voor het eerste element: door de limit-operatie is er geen nood aan het verwerken van het tweede, derde, … element, dus dat gebeurt ook nooit. De code hierboven verwerkt dus enkel het eerste element uit de lijst; met alle andere elementen wordt nooit iets gedaan.

Het is dus belangrijk om in het achterhoofd te houden dat stream-operaties enkel uitgevoerd worden wanneer dat noodzakelijk is, en pas op het allerlaatste moment (als gevolg van een terminale operatie). Dat is efficiënt, maar kan soms leiden tot verrassende situaties (zoals hierboven).

We bekijken nu enkele vaak voorkomende terminale operaties.

toList, toArray

De terminale operatie toList maakt een nieuwe lijst met daarin de elementen op het einde van de pijplijn, in de volgorde dat ze daar toekomen. Bijvoorbeeld:

List<String> result = Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .toList();
// => result == [b, c, d, f]

Gelijkaardig is er ook toArray. Deze maakt een Object[] array aan met daarin de elementen.

Object[] result = Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .toArray();

Door de beperkingen van generics in Java (i.e., je mag niet new T[n] schrijven voor een generisch type T) kan er enkel een Object[] array gemaakt worden, geen String[]. Indien je dat wel wil, moet je een functie meegeven om een lege array van het juiste type en de juiste lengte aan te maken, bijvoorbeeld:

String[] result = Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .toArray(n -> new String[n]); // OF: toArray(String[]::new);

count

Zoals de naam aangeeft, telt de count()-operatie het aantal elementen op het einde van de stream. Dat aantal wordt als een long teruggegeven, niet als int. Bijvoorbeeld:

long nbConsonants = Stream.of("A", "B", "C", "D", "E", "F")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .count();
// => nbConsonants == 4L

findFirst en findAny

De operaties findFirst en findAny geven respectievelijk het eerste en een niet nader bepaald element terug uit de stream. Merk op dat findAny niet ‘random’ is; er zijn gewoon geen garanties over welk element precies teruggegeven wordt. findAny is vooral nuttig bij parallelle streams (zie later).

Het resultaat van beide methodes is een Optional; die is leeg wanneer de stream leeg is, er er dus geen element is om terug te geven.

Optional<String> result = Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .findFirst();

// => result == Optional["B"]

Optional<String> result = Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> "XYZ".contains(l))
   .findAny();

// => result == Optional.empty

anyMatch, allMatch, noneMatch

Deze methodes geven true of false terug, afhankelijk van of respectievelijk ten minste één, elk, of geen enkel element in de stream voldoet aan de meegegeven voorwaarde.

Stream.of("Alpha", "Bravo", "Charlie", "Delta")
  .anyMatch(s -> s.startsWith("A")); // => true

Stream.of("Alpha", "Bravo", "Charlie", "Delta")
  .allMatch(s -> s.length() < 6); // => false

Stream.of("Alpha", "Bravo", "Charlie", "Delta")
  .noneMatch(s -> s.startsWith("X")); // => true

min en max

De min en max operatie vereisten een Comparator-object om elementen te vergelijken met elkaar. Ze geven een Optional terug met het kleinste respectievelijk grootste element, of de lege optional indien de stream geen elementen bevat.

Bijvoorbeeld, onderstaande code geeft het element terug waarin de letter ‘a’ het vaakst voorkomt. We maken dus een Comparator gebaseerd op het aantal ‘a’s in het woord. Om dat aantal te tellen, maken we opnieuw gebruik van een stream-pipeline, namelijk chars().filter().count():

Stream.of("Alpha", "Bravo", "Charlie", "Delta")
      .max(Comparator.comparing(s -> s.toLowerCase().chars().filter(c -> c == 'a').count())); // => Optional["alpha"]

Voor een IntStream, LongStream en DoubleStream hoef je geen Comparator mee te geven; daar worden uiteraard gewoon de getallen zelf vergeleken.

sum, average, summaryStatistics

De sum, average en summaryStatistics operaties zijn enkel beschikbaar op IntStream, LongStream en DoubleStream. De eerste twee geven, weinig verrassend, de som en het gemiddelde van de waarden terug.

De summaryStatistics operatie geeft een object terug met daarin

het aantal waarden (count)
de kleinste waarde (min)
de gemiddelde waarde (average)
de grootste waarde (max)
de totale waarde (sum)

Indien je meer dan één van die resultaten zoekt, is het dus efficiënter om deze methode te gebruiken dan de afzonderlijke operaties (die elk een nieuwe stream moeten doorlopen).

Een voorbeeld:

Stream.of("Alpha", "Bravo", "Charlie", "Delta")
      .mapToInt(String::length)
      .summaryStatistics();
// => IntSummaryStatistics{count=4, min=5, average=5.5, max=7, sum=22}

reduce

De reduce-operatie is een zeer veelzijdige operatie. Ze combineert alle elementen in de stream tot één nieuwe waarde (dit is dus bijna de definitie van een terminale operatie). We beschouwen hier de versie van reduce met twee argumenten, die een resultaat teruggeeft van hetzelfde type als de elementen in de stream:

een startwaarde identity van type T
een accumulator-functie accumulator (een BinaryOperator) die een vorige T combineert met de huidige T uit de stream, en de nieuwe T teruggeeft

Met andere woorden, de reduce-operatie op een stream heeft hetvolgende effect:

T result = identity;
for (T element : stream) {
  result = accumulator.apply(result, element);
}
return result;

Een andere manier om hiernaar te kijken is dat de accumulator een bewerking is die ingevoegd wordt tussen alle elementen van de stream; de linker-parameter van de accumulator is de waarde tot dan toe, en de rechterparameter de volgende waarde om mee in rekening te brengen. Bijvoorbeeld, we kunnen de som van alle elementen ook berekenen via reduce in plaats van via sum:

IntStream.rangeClosed(1, 5)                 // => 1, 2, 3, 4, 5
   .reduce(0, (sum, value) -> sum + value); // => (((((0 + 1) + 2) + 3) + 4) + 5) = 15

Of grafisch: drawing

Weetje: in sommige andere programmeertalen wordt reduce ook fold genoemd (en de Java-versie van reduce is meer specifiek foldLeft).

collect

De laatste terminale operatie die we bekijken is collect. Deze is gelijkaardig aan reduce, maar laat toe om de set van terminale operaties uit te breiden via Collector-objecten. Een Collector-object bevat 4 elementen:

een supplier-functie (type Supplier) die wordt gebruikt om een startwaarde (state) te verkrijgen, vergelijkbaar met de identity bij reduce
een accumulator-functie (type BiConsumer) die een nieuw data-element toevoegt aan het voorlopige resultaat (de state); vergelijkbaar met de accumulator van reduce
een combiner-functie (type BinaryOperator) die twee voorlopige resultaten kan combineren (vooral nuttig bij parallelle uitvoering; zie later)
een finisher-functie (type Function) die, op het einde, het voorlopige resultaat omzet naar het finale resultaat.

De supplier, accumulator, combiner en finisher werken conceptueel op de volgende manier:

var tempResult1 = collector.supplier();
for (T element : part 1 of stream) {
  collector.accumulator(tempResult1, element);
}
var tempResult2 = collector.supplier();
for (T element : part 2 of stream) {
  collector.accumulator(tempResult2, element);
}
var tempResult = collector.combiner(tempResult1, tempResult2);
return collector.finisher(tempResult);

Schematisch ziet dat er zo uit: drawing

Merk op dat, in tegenstelling tot de accumulator bij reduce, er bij die van een collector niets wordt teruggegeven; de verwachting is dat het tijdelijke resultaat zelf geüpdated wordt (en dus stateful is).

Info

De combiner is enkel nuttig indien er meerdere deelresultaten zijn. Dat is enkel het geval als de invoer-stream in meerdere delen opgedeeld kan worden. Gewoonlijk gebeurt dat enkel bij parallelle streams (zie later). Een gewone (sequentiële) stream heeft geen combiner nodig.

We geven één voorbeeld van een Collector-implementatie, namelijk een collector die (voor een stream van Strings) de Strings aan elkaar plakt tot één lange String, gescheiden door komma’s. De state van de collector is een object van de klasse JoiningState. Die state houdt de tot dan toe aan elkaar geplakte string bij (current), alsook of het eerste element nog toegevoegd moet worden (first).

class JoiningState {
    private boolean first = true;
    private String current = "";
    public void add(String s) {
        if (!first)
            current += ", ";
        current += s;
        first = false;
    }
    public JoiningState merge(JoiningState other) {
        var result = new JoiningState();
        result.current = this.current + (other.first ? "" : ", " + other.current);
        result.first = this.first && other.first;
        return result;
    }
    public String result() {
        return this.current;
    }
}

class StringJoiningCollector implements Collector<String, JoiningState, String> {

    @Override
    public Supplier<JoiningState> supplier() {
        return JoiningState::new;
    }

    @Override
    public BiConsumer<JoiningState, String> accumulator() {
        return (state, s) -> state.add(s);
    }

    @Override
    public BinaryOperator<JoiningState> combiner() {
        return (state1, state2) -> state1.merge(state2);
    }

    @Override
    public Function<JoiningState, String> finisher() {
        return JoiningState::result;
    }

    @Override
    public Set<Characteristics> characteristics() {
        return Set.of();
    }
}

We kunnen deze collector nu als volgt gebruiken:

Stream.of("Alpha", "Bravo", "Charlie", "Delta").collect(new StringJoiningCollector()); // => "Alpha, Bravo, Charlie, Delta"

Java bevat reeds enkele handige voorgedefinieerde collectors. Deze vind je in de Collectors-klasse. We bekijken er enkele.

Collectors.joining

Deze collector doet wat we hierboven zelf implementeerden: Strings aan elkaar plakken, gescheiden door een separator-string. We hadden onszelf dus wat werk kunnen besparen, en gewoon hetvolgende schrijven:

Stream.of("Alpha", "Bravo", "Charlie", "Delta").collect(Collectors.joining(", ")); // => "Alpha, Bravo, Charlie, Delta"

Collectors.toList, Collectors.toSet, Collectors.toCollection

Deze collectors doen wat de naam zegt: ze maken een List, Set, of Collection met daarin de elementen van de stream. De toList terminale operatie die we eerder zagen is gewoon een methode om makkelijk deze collector te gebruiken.

Bij toCollection ligt niet vast welk type collectie gemaakt moet worden; je moet zelf een functie meegeven om een lege collectie van het gewenste type te maken:

Stream.of("Alpha", "Bravo", "Charlie", "Delta").collect(Collectors.toCollection(() -> new LinkedList<>()));

Collectors.groupingBy

Deze collector groepeert de elementen in een Map, volgens de meegegeven functie om de key te bepalen:

Stream.of("Alpha", "Bravo", "Charlie", "Delta").collect(Collectors.groupingBy(String::length));
// => {5=["Alpha", "Bravo", "Delta"], 7=["Charlie"]}

Collectors.partitioningBy

Deze collector groepeert de elementen ook in een Map, maar nu met als key true of false, afhankelijk van of het object voldoet aan de meegegeven voorwaarde of niet:

Stream.of("Alpha", "Bravo", "Charlie", "Delta").collect(Collectors.partitioningBy(s -> s.length() < 6))
// => {false=["Charlie"], true=["Alpha", "Bravo", "Delta"]}

forEach

De forEach(fn) terminale operatie voert de meegegeven functie fn uit voor elk element dat het einde van de pijplijn bereikt. Een heel eenvoudig gebruik hiervan is het uitprinten van alle elementen via System.out.println:

Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .forEach(x -> System.out.println(x)); // => b, c, d, f
   // OF:  .forEach(System.out::println);

De forEach-operatie is dus zowat het streams-equivalent van de enhanced for-loop (for (var x : collection)) bij collecties.

Opgelet

Vermijd het gebruik een forEach om een variabele/lijst/… buiten de forEach-lambda aan te passen, zoals het toevoegen aan de result-lijst in onderstaand voorbeeld. Meestal is dit een antipattern, en is er een betere manier om hetzelfde resultaat te bekomen.

List<String> result = new ArrayList<>();
Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .forEach(x -> result.add(x)); // Niet doen! ❌

De betere manier hier is uiteraard

List<String> result = Stream.of("C", "D", "A", "F", "E", "B")
   .map(String::toLowerCase)
   .filter(l -> !"aeiouy".contains(l))
   .sorted()
   .toList();

Parallelle streams

Vaak kunnen operaties in een stream efficiënt in parallel gebeuren. Denk bijvoorbeeld aan map of filter: deze gebeuren element per element, en zijn dus onafhankelijk van wat er met de andere elementen gebeurt. Je kan in Java daarom ook een parallelle stream aanmaken. Deze zal, bij uitvoering, meerdere threads gebruiken (via een ForkJoinPool, zie vroeger) om de stream te verwerken.

Het is eenvoudig om een stream parallel te maken: dat kan via de parallel() intermediate operatie, of de parallelStream()-operatie op collecties. Er is ook een sequential() operatie die de stream sequentieel maakt. Merk op dat de mode waarin de stream zich bevindt op het moment van de terminale operatie bepaalt hoe de hele stream uitgevoerd wordt; je kan dus geen deel van de operaties parallel en een ander deel sequentieel uitvoeren.

We gaan niet in meer detail in op parallelle streams.

Nog meer streams? (optioneel)

In onderstaande presentatie zie je hoe er momenteel gewerkt wordt om streams nog uitbreidbaarder te maken. Via de Collector-API kan je, zoals we gezien hebben, zelf al nieuwe collectors toevoegen. Voor de tussentijdse operaties ben je in de huidige versie van de streams API echter beperkt tot de voorgedefinieerde tussentijdse operaties; maar je kan er veel meer bedenken. De oplossing die onderzocht wordt komt in de vorm van een Gatherer-interface.

Streams (en parallelle streams in het bijzonder) maken gebruik van Spliterators. Dat is een variant op een iterator, die (naast de elementen overlopen, zoals bij een gewone iterator) ook de elementen van een bron (bv. een collectie) in 2 delen kan splitsen. Bij parallelle streams zal dan elk van die delen afzonderlijk (in een aparte thread) verwerkt worden. Meer info over Spliterators vind je in onderstaande presentatie.

Omdat int maar een eindig aantal waarden kan hebben (de hoogste waarde is $ 2^{31}-1 $), zal deze stream ooit negatieve getallen beginnen produceren: …, 2147483646, 2147483647, -2147483648, -2147483647, …. De stream is wel nog steeds oneindig. ↩︎

Oefeningen

Alle oefeningen moeten opgelost worden zonder for- of while-lussen.

Personen

We gaan werken met een dataset van personen, onderverdeeld in volwassenen en kinderen:

interface Person { 
    String firstName();
    String lastName();
    int age();
    String zipCode();
}
record Adult(String firstName,
             String lastName,
             int age,
             String zipCode,
             List<Child> children) implements Person {}
record Child(String firstName,
             String lastName,
             int age,
             String zipCode) implements Person {}

De dataset vind je in het bestand Data.java, en ziet er als volgt uit:

public static final List<Adult> DATASET = List.of(
        new Adult("John", "Doe", 30, "12345", List.of(
                new Child("Alice", "Doe", 5, "12345"),
                new Child("Liam", "Doe", 7, "12345"))),
  ...
);

De dataset is dus een lijst van Adult-objecten, waar elk object (naast naam, leeftijd, postcode) ook een lijst van kinderen bevat.

Data.java

package streams.exercises.exercise1;

import java.util.Collections;
import java.util.List;

public class Data {
    public interface Person { String firstName(); String lastName(); int age(); String zipCode(); }
    public record Adult(String firstName, String lastName, int age, String zipCode, List<Child> children) implements Person {}
    public record Child(String firstName, String lastName, int age, String zipCode) implements Person {}

    public static final List<Adult> DATASET = List.of(
            new Adult("John", "Doe", 30, "12345", List.of(
                    new Child("Alice", "Doe", 5, "12345"),
                    new Child("Liam", "Doe", 7, "12345"))),
            new Adult("Jane", "Smith", 28, "23456", List.of(
                    new Child("Bob", "Smith", 3, "23456"),
                    new Child("Charlie", "Smith", 6, "23456"),
                    new Child("Daisy", "Smith", 8, "23456"))),
            new Adult("Michael", "Johnson", 35, "34567", List.of(
                    new Child("Daniel", "Johnson", 7, "34567"),
                    new Child("Sophia", "Johnson", 4, "34567"))),
            new Adult("Emily", "Davis", 32, "45678", List.of(
                    new Child("Emma", "Davis", 2, "45678"))),
            new Adult("David", "Wilson", 29, "56789", List.of(
                    new Child("Nora", "Wilson", 5, "56789"),
                    new Child("Evan", "Wilson", 10, "56789"))),
            new Adult("Sarah", "Martinez", 24, "67890", List.of(
                    new Child("Mia", "Martinez", 3, "67890"))),
            new Adult("Daniel", "Anderson", 31, "78901", List.of(
                    new Child("Olivia", "Anderson", 6, "78901"))),
            new Adult("Laura", "Taylor", 27, "89012", Collections.emptyList()),
            new Adult("James", "Thomas", 45, "90123", List.of(
                    new Child("Isaac", "Thomas", 9, "90123"),
                    new Child("Zoe", "Thomas", 13, "90123"),
                    new Child("Ava", "Thomas", 11, "90123"))),
            new Adult("Susan", "Jackson", 26, "01234", Collections.emptyList()),
            new Adult("Robert", "White", 50, "12345", List.of(
                    new Child("Tyler", "White", 14, "12345"))),
            new Adult("Linda", "Harris", 48, "23456", List.of(
                    new Child("Grace", "Harris", 8, "23456"))),
            new Adult("William", "Clark", 51, "34567", Collections.emptyList()),
            new Adult("Barbara", "Lewis", 34, "45678", List.of(
                    new Child("Jasper", "Lewis", 6, "45678"),
                    new Child("Lucy", "Lewis", 10, "45678"))),
            new Adult("Richard", "Robinson", 58, "56789", Collections.emptyList()),
            new Adult("Mary", "Walker", 60, "67890", List.of(
                    new Child("Ella", "Walker", 5, "67890"),
                    new Child("Ruby", "Walker", 7, "67890"))),
            new Adult("Joseph", "Perez", 29, "78901", Collections.emptyList()),
            new Adult("Karen", "Hall", 43, "89012", List.of(
                    new Child("Gavin", "Hall", 13, "89012"))),
            new Adult("Paul", "Young", 22, "90123", Collections.emptyList()),
            new Adult("Lisa", "Allen", 37, "01234", List.of(
                    new Child("Harper", "Allen", 9, "01234"))),
            new Adult("Kevin", "King", 33, "12345", Collections.emptyList()),
            new Adult("Nancy", "Wright", 29, "23456", List.of(
                    new Child("Mason", "Wright", 4, "23456"))),
            new Adult("George", "Scott", 40, "34567", Collections.emptyList()),
            new Adult("Betty", "Green", 30, "45678", Collections.emptyList()),
            new Adult("Steven", "Adams", 36, "56789", Collections.emptyList()));
}

In Main.java vind je al wat code voor de verschillende oefeningen. Ook de dataset is al geïmporteerd.

Main.java

package streams.exercises.exercise1;

import java.util.*;
import java.util.stream.Collectors;
import static streams.exercises.exercise1.Data.DATASET;

public class Main {
    public static void main(String[] args) {
        exercise01();
        exercise02();
        exercise03();
        exercise04();
        exercise05();
        exercise06();
        exercise07();
        exercise08();
        exercise09();
        exercise10();
        exercise11();
        exercise12();
        exercise13();
        exercise14();
        exercise15();
        exercise16();
    }

    private static void exercise01() {
        // TODO
        // je kan print gebruiken om het resultaat af te drukken, bv.
        print(DATASET.stream().findFirst());
    }

    private static void exercise02() {
        // TODO
    }

    private static void exercise03() {
        // TODO
    }

    private static void exercise04() {
        // TODO
    }

    private static void exercise05() {
        // TODO
    }

    private static void exercise06() {
        // TODO
    }

    private static void exercise07() {
        // TODO
    }

    private static void exercise08() {
        // TODO
    }

    private static void exercise09() {
        // TODO
    }

    private static void exercise10() {
        // TODO
    }

    private static void exercise11() {
        // TODO
    }

    private static void exercise12() {
        // TODO
    }

    private static void exercise13() {
        // TODO
    }

    private static void exercise14() {
        // TODO
    }

    private static void exercise15() {
        // TODO
    }

    private static void exercise16() {
        // TODO
    }

    // Hulpfunctie om het resultaat van een oefening te printen
    // Voegt ook de oefening (naam van de methode) toe.
    private static void print(Object value) {
        var s = Arrays.stream(Thread.currentThread().getStackTrace())
                      .dropWhile(m -> !m.getMethodName().startsWith("ex"))
                      .findFirst().get();
        if (value instanceof Optional<?> o) {
            if (o.isPresent())
                value = o.get();
            else
                value = "Nothing found.";
        } else if (value instanceof OptionalDouble o) {
            if (o.isPresent()) {
                value = o.getAsDouble();
            } else {
                value = "Nothing found.";
            }
        }
        System.out.println("\n- " + s.getMethodName() + ":\n" +
            value.toString().lines().map(l -> "  " + l).collect(Collectors.joining("\n")));
    }
}

Los volgende oefeningen op met streams.

Print alle namen van de volwassenen in de dataset.
Ga na dat alle volwassenen in de dataset inderdaad ouder dan 18 zijn.
Ga na of er minstens één volwassene in de dataset zit waarvan de voornaam “Joseph” is.
Geef enkele statistieken (minimum, maximum, gemiddelde) van de leeftijd van alle volwassenen in de dataset die ten minste 30 jaar oud zijn.
Zoek de volwassene met de langste achternaam.
Groepeer alle volwassenen in een Map volgens hun postcode.
Geef een String met de 5 oudste volwassenen terug, in het formaat “voornaam achternaam leeftijd”, gesorteerd volgens voornaam, 1 persoon per lijn.
Tel het totaal aantal kinderen in de dataset.
Tel het aantal volwassenen met kinderen in de dataset.
Geef het minimum en maximum aantal kinderen dat een volwassene heeft.
Zoek alle personen die precies 6 keer zo oud zijn als een van hun kinderen.
Maak een lijst van alle kind-objecten in de dataset.
Maak een gesorteerde lijst met alle unieke voornamen van alle kinderen in de dataset.
Bereken de gemiddelde leeftijd van alle kinderen in de dataset die een ouder hebben die ouder is dan 40.
Maak een lijst van alle personen (volwassenen + kinderen) in de dataset, gesorteerd volgens voornaam.
Bereken de gemiddelde leeftijd van alle personen (volwassenen + kinderen) in de dataset.

mapValues

Schrijf, gebruik makend van streams, een generische methode mapAllValues(map, function) die je kan gebruiken om een nieuwe Map te maken waarbij alle waarden vervangen zijn door de gegeven functie erop toe te passen. Bijvoorbeeld, in onderstaande code gebruiken we deze functie om alle String-values in de map te vervangen door hun lengte:

Map<String, String> myMap = Map.of("first", "333", "second", "55555"); // => {first="333", second="55555"}
Map<String, Integer> result = mapAllValues(myMap, String::length);
System.out.println(result); // => {first=3, second=5}

Hint: gebruik Collectors.toMap(...)

Denk ook na over geschikte grenzen voor je generische parameters (PECS). Ook hetvolgende zou moeten werken:

Map<String, String> myMap = Map.of("first", "333", "second", "55555");
Function<Object, Integer> fn = (x) -> x.toString().length();
Map<Object, Object> result = mapAllValues(myMap, fn);

Klasse	Naam	\( T(1000) \) (als \( T(100) = 1 \textrm{ms} \))
\( \mathcal{O}(1) \)	Constant	\(1\ \textrm{ms} \)
\( \mathcal{O}(\log n) \)	Logaritmisch	\(1.5\ \textrm{ms} \)
\( \mathcal{O}(n) \)	Lineair	\(10\ \textrm{ms} \)
\( \mathcal{O}(n \log n) \)	Linearitmisch	\(15\ \textrm{ms} \)
\( \mathcal{O}(n^2) \)	Kwadratisch	\(100\ \textrm{ms} \)
\( \mathcal{O}(n^3) \)	Kubisch	\(1000\ \textrm{ms} \)
\( \mathcal{O}(2^n) \)	Exponentieel	\( 2^{900}\ \textrm{ms} \) = \( 2.7 \times 10^{260}\ \textrm{jaar}\)
\( \mathcal{O}(n!) \)	Factorieel	\( \frac{1000!}{100!}\ \textrm{ms} \) = \( 1.4 \times 10^{2399}\ \textrm{jaar}\)

Operatie	Complexiteit (best case)	Complexiteit (worst case)
Opvragen	\(\mathcal{O}(1)\)	\(\mathcal{O}(1)\)
Invoegen	\(\mathcal{O}(1)\) (einde van lijst), of \(\mathcal{O}(n)\) bij uitbreiden capaciteit	\(\mathcal{O}(n)\) (begin van lijst)
Verwijderen	\(\mathcal{O}(1)\) (laatste element)	\(\mathcal{O}(n)\) (eerste element)
Zoeken	\(\mathcal{O}(1)\) (gezochte element is eerste element)	\(\mathcal{O}(n)\) (gezochte element is laatste)

Operatie	Complexiteit (best case)	Complexiteit (worst case)
Opvragen	\(\mathcal{O}(1)\) (begin of einde van de lijst)	\(\mathcal{O}(n)\) (midden van de lijst)
Invoegen	\(\mathcal{O}(1)\) (begin of einde van de lijst)	\(\mathcal{O}(n)\) (midden van de lijst)
Verwijderen	\(\mathcal{O}(1)\) (begin of einde van de lijst)	\(\mathcal{O}(n)\) (midden van de lijst)
Zoeken	\(\mathcal{O}(1)\) (begin of einde van de lijst)	\(\mathcal{O}(n)\) (midden van de lijst)

7. Advanced Java

Subsections of 7. Advanced Java

7.1 Records

Wat zijn records

Wanneer gebruik je een record

Achter de schermen

Methodes toevoegen aan een record

Constructor van een record

Records en overerving

Immutable

Pattern matching

Sealed interfaces

Oefeningen

Subsections of 7.1 Records

Oefeningen

Klasse of record?

Sealed interface

Email

Money

Interval

Rechthoek

Expressie-hierarchie

7.2 Generics

Subsections of 7.2 Generics

7.2.1 Definiëren en gebruiken

Een generische klasse definiëren

Een generische klasse gebruiken

Generische parameters begrenzen (bounds)

Een generische methode definiëren en gebruiken

Type inference

Voorbeeld

Meerdere type-parameters

7.2.2 Generics en subtyping

Subtyping en generische lijsten

Overerven van een generisch type

7.2.3 Wildcards

Covariantie (extends)

Contravariantie (super)

Covariantie of contravariantie: PECS

Arrays en type erasure

Aandachtspunten

Enkel bij generische types!

Bounds vs. co-/contravariantie en wildcards

Arrays met generisch type

Oefeningen

Maybe-klasse

Repository

SuccessOrFail

Subtyping: voertuigen

Covariantie

Shop

Functie compositie

Game engine

Animal food

Self-type

7.3 Collections

Andere collectie-API’s

Subsections of 7.3 Collections

7.3.1 Tijdscomplexiteit

Best, worst, average case

Voorbeeld: selection sort

Basisoperaties tellen

Grote O-notatie

Vaak voorkomende complexiteitsklassen

7.3.2 Java Collections API

Iterable en Iterator

Collection

7.3.3 Lijsten

List

ArrayList

LinkedList

Lijsten aanmaken

Meer operaties op lijsten

Unmodifiable list

7.3.4 Wachtrijen

Queue, Deque

FIFO queue

LIFO queue (stack)

PriorityQueue

7.3.5 Verzamelingen