“Op elk potje past een dekseltje” luidt het spreekwoord. Dit wordt vooral gebruikt bij iemand die tegenslag in de liefde ondervindt, om hem of haar een hart onder de riem te steken en zodoende de hoop op het vinden van een geschikte levenspartner in stand te houden.

In deze opgave zetten we dit spreekwoord om in de praktijk: gegeven een verzameling potjes en een verzameling deksels, stellen we een verzameling van koppels op. Voor elk potje is er minstens één passend dekseltje en omgekeerd, maar helaas zijn deze door elkaar geraakt. Natuurlijk zouden we voor elk potje alle deksels kunnen overlopen om zo een passend koppel te vormen, maar we willen graag sneller te werk gaan. We zouden bijvoorbeeld beide verzamelingen kunnen sorteren met een efficiënt algoritme (twee keer gemiddelde tijdscomplexiteit \(\Theta(s \times log(s))\) met \(s\) het aantal potjes en deksels) en ze dan gewoon twee-aan-twee koppelen. Eén probleem: je kan een potje niet zomaar met andere potjes vergelijken, en een deksel niet met andere deksels.

Om dit probleem efficiënt op te lossen halen we onze inspiratie bij het quicksort algoritme. We kunnen namelijk als spil een potje uitkiezen en hiermee de deksels verdelen in drie groepen:

De deksels die te klein zijn voor het gekozen referentiepotje.
De deksels die precies op dit potje passen (zo is er steeds minstens één).
Alle deksels die te groot zijn voor dit potje.

Vervolgens nemen we een deksel uit de tweede groep om ook de potjes op dezelfde manier op te splitsen. Na het uitvoeren van deze twee complementaire stappen hebben we reeds een of meerdere allemaal even grote potjes en deksels gevonden die precies op elkaar passen, en bovendien hebben we de resterende potjes onderverdeeld in kleine en grote exemplaren, die we recursief verder kunnen opsplitsen volgens dezelfde strategie.

Aan jullie om dit algoritme zorgvuldig uit te werken en te implementeren. Net zoals bij het originele quicksort algoritme maak je best geen nieuwe lijsten voor de drie groepen, maar partitioneer je de lijst in place door de potjes en deksels te herordenen via opeenvolgende verwisselingen. Merk op dat je de gegeven lijsten met potjes en dekseltjes niet kan aanpassen (zie verder), je zal hier dus eenmalig een kopie van moeten maken bij de aanvang van je algoritme (het is trouwens een goede gewoonte om argumenten niet te wijzigen indien de interface hier niet om vraagt).

Implementeer de interface Matcher¹ met een klasse genaamd MyMatcher. Hiervoor voorzie je de methode public List<Pair> match(List<Jar> jars, List<Lid> lids). Gegeven twee even lange lijsten jars en lids met respectievelijk potjes en dekseltjes, geef je een (opnieuw even lange) lijst van koppels terug. Elk koppel (van gegeven klasse Pair²) bevat een passend potje en deksel. Elk gegeven potje en dekseltje komt precies eenmaal voor in één enkel koppel in de uitvoer. De gegeven lijsten mogen (en kunnen) niet gewijzigd worden.

Merk tenslotte nog op dat Jar en Lid binnenklassen zijn van de interface Matcher, en respectievelijk Comparable<Lid> en Comparable<Jar> implementeren. Je kan dus potjes met deksels vergelijken, en deksels met potjes, maar geen potjes met potjes of deksels met deksels.

Enkele testen om lokaal uit te voeren vind je zoals steeds in de SimpleTest testklasse³.

Handig om te weten:

Er zit een swap⁴ methode in Collections.