Laborationer

Laboration 2: Implementering av en ADT

Målsättning

I denna laboration ska du själv implementera en länkad datastruktur. Detta ska ge dig en inblick i hur man bygger upp en abstrakt datatyp "från insidan". Du ska också få övning i att översätta den pseudokod som finns i boken till ett riktigt Java-program.

Uppgift

Din uppgift i denna laboration är att implementera den abstrakta datatypen ordered dictionary med hjälp av datastrukturen skip list. Till din hjälp finns ett antal färdiga testprogram som kontrollerar att skiplistan du skrivit gör vad den ska.

En ordered dictionary är en kombination av en vanlig dictionary och en ordnad sekvens. Detta innebär att man kan lägga till, söka och ta bort element med hjälp av en nyckel. Dessutom kan man stega igenom elementen i stigande nyckelordning. I vårt gränssnitt finns metoderna insert, find och remove som står för "dictionarydelen". Sekvensdelen når man genom metoden elements som returnerar ett objekt av Iterator-typ. Slutligen finns även hjälpmetoderna size och isEmpty.

Gränssnittet

Gränssnittet som skall implementeras ser ut på följande sätt:

import java.util.*;

public interface OrderedDictionary {                   
    public static final Object NO_SUCH_KEY = "NO_SUCH_KEY";

    public int size();                                   
    public boolean isEmpty();
    public void   insert( Comparable key, Object element );
    public Object remove( Comparable key );
    public Object find( Comparable key );

    public Iterator elements();
}
(denna definition finns på kurskatalogen i filen /info/grudat00/labbar/OrderedDictionary.java)

Lägg märke till att nyckeln är av typen Comparable. Comparable är ett gränssnitt som finns färdigt i Java och som implementeras av alla objekttyper som är naturligt jämförbara, t.ex. String. För att jämföra två nycklar behöver du därför bara anropa metoden compareTo från detta gränssnitt.

En annan "finess" i gränssnittet är objektet NO_SUCH_KEY. Detta är ett unikt objekt som returneras av find och remove när de inte hittar den sökta nyckeln (samma teknik används även i boken). Genom att variabeln både är static och final så kommer endast ett objekt att skapas. Det är egentligen likgiltigt vilken sorts objekt det är men här använder vi en sträng vilket underlättar t.ex. när man ska tyda felutskrifter.

I gränssnittet används den färdiga Iterator-typen för att sekvensiellt gå igenom elementen. Den färdiga Iterator innehåller dock även en remove-metod som du inte behöver implementera. För att kompilatorn ska acceptera din klass som en Iterator måste du definiera en remove-metod men du får göra denna som en s.k. dummy, d.v.s. en metod som inte gör någonting. Obs: blanda inte ihop detta med den remove-metod som finns i OrderedDictionary. Den ska implementeras!

Genomförandet

Du ska alltså implementera datastrukturen SkipList vilket innebär att du ska skriva en klass som uppfyller gränssnittet OrderedDictionary. Utgå från beskrivningen av SkipList i boken där algoritmerna för insättning och sökning finns beskrivna som pseudokod. Algoritmen för borttagning är nästan likadan som för sökning (använd gärna en hjälpmetod för den gemensamma delen) med tillägget att man plockar bort den funna noden på alla nivåer där den finns i datastrukturen.

För att implementera datastrukturen måste du definiera tre klasser:

  1. En klass som representerar själva SkipList. Denna klass ska implementera gränssnittet OrderedDictionary enligt ovan.
  2. En klass som representerar noderna som du internt använder för att bygga upp datastrukturen. Denna klass behöver inte nödvändigtvis innehålla några metoder. Det centrala är att instanserna innehåller länkarna åt alla fyra håll (uppåt, nedåt, framåt och bakåt).
  3. En klass för de Iterator-objekt som ska returneras av metoden elements. Denna klass ska innehålla definitionerna för metoderna i gränssnittet Iterator.
Det kan vara praktiskt att låta de två senare klasserna vara lokala klasser till SkipList.

När man implementerar en datastruktur är det viktigt att testa att den fungerar rätt enligt gränssnittet. För att göra det enklare för er har vi gjort iordning några testprogram som finns på kurskatalogen /info/grudat00/labbar/. Om du kallar din klass för SkipList så ska du kunna köra alla dessa program utan att ändra någonting i dem. Lägg märke till att de olika programmen testar olika delar av implementationen. Detta gör det möjligt att använda vissa testprogram innan allting är helt klart.

Lycka till!
Örjan