Beschouw een collectie \(U\) van \(n\) data-elementen (items) die in het centrale geheugen opgeslagen zijn. Er is ook een snellere cache beschikbaar, waarin \(k<n\) items tegelijkertijd kunnen opgeslagen worden. Veronderstel dat de cache aanvankelijk \(k\) items bevat.

Gegeven is een reeks items \(D = d_1,d_2,\ldots,d_m\) van items uit \(U\) die achtereenvolgens opgevraagd worden. Voor elk moment moeten we beslissen welke items in de cache te bewaren. Wanneer item \(d_i\) opgevraagd wordt, hebben we zeer snelle toegang als het zich in de cache bevindt; anders moet het naar de cache gebracht worden en moet een ander item uit de cache verwijderd worden om plaats te maken voor \(d_i\). Dit wordt een uitzetting (of eviction) genoemd.

Het is de bedoeling een uitzettingsschema op te stellen dat voor een gegeven reeks opvragingen zo weinig mogelijk uitzettingen gebruikt.

Implementeer de interface Caching¹ in een klasse OptimalCaching. Implementeer hiervoor de methode ` List optimize(List items, Set cache);`. Deze methode neemt een collectie items als input en geeft een lijst terug die voor elke stap het item geeft dat uitgewezen moet worden, of `null` als het opgevraagde items al in de cache zit.

Elk item wordt geïdentificeerd door een Integer.

Opmerking: pas de lijst met items en de cache niet aan. Indien je dit wel doet, zullen de testen falen.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.