Oefeningen
De Collections API
IntRange
- Schrijf eerst een klasse
IntRangeIterator
dieIterator<Integer>
implementeert, en alle getallen teruggeeft tussen twee grensgetallenlowest
enhighest
(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
dieIterable<Integer>
implementeert, en die eenIntRangeIterator
-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) teruggeeftint capacity()
die de huidige capaciteit (het aantal plaatsen in de array) van de lijst teruggeeftE get(int index)
om het element op positieindex
op te vragen (of eenIndexOutOfBoundsException
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 eenIndexOutOfBoundsException
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 eenNoSuchElementException
indien de lijst leeg is)
Hier vind je een test die een deel van dit gedrag controleert:
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 gevenvoid add(E element)
om het gegeven element achteraan toe te voegenE get(int index)
om het element op positieindex
op te vragenvoid remove(int index)
om het element op positieindex
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.
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 queueE poll()
: het hoofd van je FIFO queue opvragen en verwijderen; geeft null terug indien de queue leeg isboolean add(E)
: een element (niet-null) toevoegen aan je queue; geeft false terug indien er niet voldoende capaciteit is
Hieronder vind je enkele tests.
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 instappenPassenger nextPassenger()
die de volgende passagier teruggeeft die mag instappen, ofnull
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.
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.
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?
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 schedulerList<Job> allJobs()
om alle jobs (in volgorde van hun tijd) terug te krijgenJob 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 klasseTreeSet
.)
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.)
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 binnendouble 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 heeftboolean 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");
}
}