Bruk av generiske datatyper

Generiske metoder
Begrensninger for typeparametre
Typerelasjoner
Jokertegn
Jokertegn med begrensninger
Mer om generiske metoder
Eksempel: Generisk implementasjon av liste
Typeutvisking
Bruk av refleksjon til å skrive generisk arraykode

Innledning

Bruk av generiske datatyper er omtalt i notatet Collections. Vi skal nå se nærmere på hvordan vi må gå fram i forbindelse med subklassetyper, samt programmering av generiske metoder. Vi skal også ta en titt "bak kulissene" og se nærmere på hvordan generiske typer egentlig blir håndtert av Javas kjøresystem. Ytterligere informasjon finnes i notatet Generics av Gilad Bracha, som er hovedkilden for framstillingen i dette notatet. En grundig framstilling av temaet finnes dessuten i læreboka Core Java, Volume 1, av Cay S. Horstmann og Gary Cornell.

Generiske metoder

Definering av generiske klasser er omtalt i notatet Collections — bruk av generiske datatyper. Vi bruker da en formell typeparameter sammen med klassenavnet, se eksemplet Listeeksempel med generisk datatype. Når vi instansierer en slik klasse, må vi istedenfor den formelle typeparameteren bruke en aktuell typeparameter som spesifiserer hvilken datatype som skal erstatte den formelle typeparameteren.

Det er også tillatt å definere generiske metoder. De har i likhet med generiske klasser en formell typeparameter, som i følgende eksempel.

class Arrayverktøy
{
  public static <T> T getMidtelement(T[] array)
  {
    return array[array.length/2];
  }
}

Merk deg at den formelle typeparameteren er plassert rett foran returverditypen (foran void i tilfelle metoden ikke skal returnere noen verdi). I eksemplet er den generiske metoden definert i en vanlig, ikke-generisk klasse. Men det er også tillatt å definere generiske metoder i generiske klasser.

Når vi gjør kall på generiske metoder, kan vi plassere den aktuelle datatypen i spissparenteser foran metodenavnet, som i følgende eksempel:

  String[] navn = {"Amelie", "Emmanuelle", "Gabrielle"};
  String midterst = Arrayverktøy.<String>getMidtelement(navn);

Men i dette tilfelle, og i de fleste andre tilfeller, kan vi droppe typeparameteren <String> fra metodekallet. Kompilatoren kan ut fra datatypen til den aktuelle (vanlige) parameteren i metodekallet kunne bestemme riktig datatype for returverdien. Metodekallet kunne vi derfor kort og godt ha skrevet slik:

  String midterst = Arrayverktøy.getMidtelement(navn);

Begrensninger for typeparametre

Noen ganger er det for generiske klasser og metoder nødvendig å sette restriksjoner på typeparametre. For å belyse dette, ser vi på følgende eksempel fra boka Core Java av Cay S. Horstmann og Gary Cornell, der vi ønsker å finne det minste elementet i en array:

class ArrayAlg
{
  public static <T> T min(T[] array)  //ikke helt riktig kode!
  {
    if (array == null)
      return null;
    T minst = array[0];
    for (int i = 1; i < array.length; i++)
      if (minst.compareTo(array[i]) > 0)
        minst = array[i];
    return minst;
  }
}

I denne koden er det imidlertid et problem. Variabelen minst er av type T, og slik koden er skrevet, kan vi som aktuell typeparameter for T bruke en hvilken som helst klasse. Men hvordan kan vi vite at den aktuelle klassen har en compareTo-metode? Det forutsetter nemlig at klassen implementerer interface Comparable. Dersom vi prøver å kompilere koden, vil det resultere i følgende feilmelding:

The method compareTo(T) is undefined for the type T.

Løsningen på det beskrevne problemet er å sette som restriksjon på typen T at den skal implementere interface Comparable. Det får vi gjort ved å sette en begrensning på typeparameteren T på følgende måte:

  public static <T extends Comparable> T min(T[] array)

Slik koden nå er skrevet, kan min-metoden bare bli kalt opp med arrayer av klasser som implementerer interface Comparable, slik som String, Date og en del andre. Når vi kompilerer koden, får vi imidlertid et par advarsler. For kodelinja

  public static <T extends Comparable> T min(T[] array)

får vi følgende advarsel:

found raw type: java.lang.Comparable
missing type arguments for generic class java.lang.Comparable<T>

og for kodelinja

      if (minst.compareTo(array[i]) > 0)

får vi følgende advarsel:

unchecked call to compareTo(T) as a member of
the raw type java.lang.Comparable

Angående hva som menes med raw type, så se lenger ute i notatet, om typeutvisking.

Advarslene får vi fordi interface Comparable i seg selv er en parametrisert type. Foreløpig skal vi ignorere advarslene. Når vi har lært om bruk av jokertegn, skal vi se på hvordan de kan fjernes.

Det er grunn til å undre seg over at det i koden for å sette begrensninger på typeparameteren blir brukt nøkkelordet extends istedenfor implements, siden Comparable er et interface. Skrivemåten

  <T extends Begrensningstype>

uttrykker at T skal være en subtype til den begrensende typen. Både T og den begrensende typen kan enten være en klasse eller et interface. Nøkkelordet extends ble valgt fordi det uttrykker på en brukbar måte begrepet subtype, og utviklerne av Java ønsket ikke å legge til noe nytt nøkkelord (slik som sub) til språket.

Det er tillatt for typevariable (og for jokertegn, som er omtalt lengre nede) å ha multiple typegrenser. Vi kan for eksempel skrive

  T extends Comparable & Serializable

Vi bruker altså ampersandtegn (&) som skille mellom de begrensende typene, dette fordi komma blir brukt som skille mellom typevariable.

Tilsvarende som det er tilfelle ved arv, kan vi i opplistingen av de begrensende typene ha så mange typer beskrevet ved et interface-navn som vi bare vil, men vi kan bare ha én type beskrevet ved et klassenavn, og dersom vi har en slik, så må denne være den første som er listet opp.

Typerelasjoner

Når det gjelder typerelasjoner, må vi skille mellom to forskjellige situasjoner:

typerelasjoner mellom objekter som vi setter inn i én og samme liste, og
typerelasjoner mellom to eller flere lister av hver sin generiske type, altså relasjoner mellom selve listetypene.

For relasjoner mellom objekter som vi setter inn i én og samme liste, gjelder de vanlige reglene for polymorfisme: et subklasseobjekt kan også oppfattes å være objekt av sin superklassetype. Det medfører at i en liste av type List<Type>, kan vi i tillegg til å kunne sette inn objekter av type Type, også sette inn objekter av en hvilken som helst subklassetype til Type. Dersom vi for eksempel har definert en abstrakt klasse Utlaansobjekt og til denne definert de ikke-abstrakte subklassene Bok, CD og DVD, så kan vi i en liste av type List<Utlaansobjekt> legge inn objekter av de tre typene Bok, CD og DVD. I en liste av type List<Object> kan vi sette inn objekter av en hvilken som helst type.

Når det gjelder relasjoner mellom lister av forskjellig generisk type, er det ikke fullt så enkelt som vi ut fra rein intuisjon kanskje skulle tro. Siden for eksempel datatypen String er en subtype til typen Object, ville vi intuitivt forvente oss at den generiske typen List<String> er en subtype til List<Object>. Men det er faktisk ikke tilfelle! For å belyse hvorfor, tenker vi oss følgende instruksjoner:

  List<String> navneliste = new ArrayList<>();
  List<Object> objektliste = navneliste;  //Ikke tillatt og
                                          //vil gi kompileringsfeil!

Dersom den andre instruksjonen var tillatt, ville variablene navneliste og objektliste nå referert til samme liste, og vi kunne satt inn et Object-objekt på første plass i objektliste:

  objektliste.add(0, new Object());

Om vi nå hadde hentet ut første element fra navneliste:

  navneliste.get(0);

hadde vi ingen garanti for at det var av type String, noe som jo strider imot definisjonen av navneliste. På grunn av dette får vi kompileringsfeil. Generelt vil kompilatoren ikke tillate oss å gjøre noe som kan komme i konflikt med typesikkerheten.

Noen ganger er det imidlertid slik at vi med samme metode ønsker å kunne behandle lister av forskjellig generisk type, men slik at alle typene tilhører samme klassehierarki. Spørsmålet blir da hvordan vi skal spesifisere typene ved bruk av typeparametre for å få til det vi ønsker. Løsningen er å bruke såkalte jokertegn (engelsk: wildcards).

Jokertegn

Som innledende eksempel tenker vi oss at vi skal lage en rutine som kan brukes til å skrive ut innholdet av en samling, uavhengig av hvilken type objekter samlingen inneholder. Uten bruk av opplegget med generiske typer kunne vi skrevet en slik rutine på denne måten:

  public void printCollection(Collection c)
  {
    Iterator i = c.iterator();
    while (i.hasNext())
      System.out.println(i.next());
  }

Siden alle typer objekter er en eller annen subtype til Object, kunne vi kanskje tenke oss at når vi bruker generiske typer, så kunne en tilsvarende rutine skrives slik:

  public void printCollection(Collection<Object> c)
  {
    Iterator<Object> i = c.iterator();
    while (i.hasNext())
      System.out.println(i.next());
  }

Koden er korrekt - vi hadde ikke fått noe kompileringsfeil. Men problemet er at vi bare hadde kunnet bruke den for samlinger av type Collection<Object>. Som vi så ovenfor, er denne typen ikke noen supertype for alle typer samlinger! Men hva er det da som er supertypen til alle typer samlinger? Den skrives som Collection<?> (kan uttales som "collection av ukjent") og kan oppfattes som en samling med elementtype som passer til hva som helst. En slik type kalles en jokertegntype. (Et jokertegn er et symbol som skal erstattes av et eller flere "virkelige" tegn.) Rutinen vår kan vi derfor skrive slik:

  public void printCollection(Collection<?> c)
  {
    Iterator<?> i = c.iterator();
    while (i.hasNext())
      System.out.println(i.next());
  }

Med den nye typen utvidet for-løkke kunne vi også skrevet den slik:

  public void printCollection(Collection<?> c)
  {
    for (Object e : c)
      System.out.println(e);
  }

Når rutinen er skrevet på en av disse to måtene, er det mulig å gjøre kall på den med en hvilken som helst type samling som parameter.

Jokertegn med begrensninger

Vi tenker oss følgende situasjon: Vi har definert et klassehierarki for diverse typer utlånsobjekter. En skisse for dette er gjengitt nedenfor og finnes i fila Utlaansobjekt.java. (Denne er litt endret i forhold til den som ble brukt i notatet Introduksjon til programmering, kapittel 10 Objektorientert programmering: polymorfisme, og som det er referet til i notatet Collections — bruk av generiske datatyper.)

  1 //Utlaansobjekt.java
  2 import java.util.Date;
  3
  4 //abstrakt klasse som inneholder datafelter og metoder 
  5 //som alle utlånsobjekter skal ha
  6 abstract class Utlaansobjekt
  7 {
  8   private Date inn;  //definert i java.util
  9   private int lånetid;
 10   private boolean ute = false;
 11   private String tittel;
 12
 13   public Utlaansobjekt(int tid, String t)
 14   {
 15     lånetid = tid;
 16     tittel = t;
 17   }
 18
 19   //redefinerer som abstrakt toString-metode arvet fra klasse Object
 20   abstract public String toString();  //obs: ingen implementasjon.
 21   //skal returnere relevante data. 
 22   //Må implementeres i ikke-abstrakte subklasser.
 23
 24   //abstrakt metode for innlevering
 25   abstract public void returner();
 26
 27   //abstrakt metode for utlån fra dato d
 28   abstract public void lånUt( Date d );
 29
 30   //abstrakt metode for utskrift av info
 31   abstract public String ventetid();
 32
 33   public String getTittel()
 34   {
 35     return tittel;
 36   }
 37
 38   //andre nødvendige set- og get-metoder
 39
 40 } //slutt på klasse Utlaansobjekt
 41
 42
 43 //Klassedefinisjon for utlånsobjekt av type bok.
 44 //Må implementere alle abstrakte metoder som blir 
 45 //arvet fra superklassen
 46 class Bok extends Utlaansobjekt
 47 {
 48   private String forfatter;
 49
 50   public Bok( String f, String t, int p )
 51   {
 52     super( p, t );
 53     forfatter = f;
 54   }
 55
 56   public String toString()
 57   {
 58     return forfatter + ": " + getTittel();
 59   }
 60
 61   public void returner()
 62   {
 63     //implementasjon av arvet abstrakt metode
 64   }
 65
 66   public void lånUt( Date d )
 67   {
 68     //implementasjon av arvet abstrakt metode
 69   }
 70
 71   public String ventetid()
 72   {
 73     String output = "";
 74     //implementasjon av arvet abstrakt metode
 75     return output;
 76   }
 77 }  //slutt på klasse Bok
 78
 79
 80 //abstrakt klasse som inneholder det som alle utlånsobjekter 
 81 //av type cd og dvd skal ha felles i tillegg til
 82 // det som blir arvet fra superklassen Utlaansobjekt
 83 abstract class AV extends Utlaansobjekt
 84 {
 85   private int spilletid;
 86
 87   public AV( int t, int p, String tt )
 88   {
 89     super( p, tt );
 90     spilletid = t;
 91   }
 92
 93   public String toString()
 94   {
 95     return "Tittel: " + getTittel() + "\nSpilletid: " + spilletid;
 96   }
 97
 98   public void lånUt( Date d )
 99   {
100     //implementasjon av arvet abstrakt metode
101   }
102
103   public void returner()
104   {
105     //implementasjon av arvet abstrakt metode
106   }
107
108   //Arvet abstrakt metode ventetid er ikke implementert. 
109   //AV er derfor en abstrakt klasse og må spesifiseres som 
110   //abstrakt med nøkkelordet abstract.
111 }  //slutt på klasse AV
112
113
114 //Klassedefinisjon for utlånsobjekt av type cd.
115 //Må implementere alle abstrakte metoder som den arver.
116 class CD extends AV
117 {
118   private String artist;
119   private String verk;
120
121   public CD( String a, String v, int spt, int lt, String tt )
122   {
123     super( spt, lt, tt );
124     artist = a;
125     verk = v;
126   }
127
128   public String toString()
129   {
130     return artist + ": " + verk + " " + super.toString();
131   }
132
133   public String ventetid()
134   {
135     String output = "";
136     //implementasjon av arvet abstrakt metode
137     return output;
138   }
139 }  //slutt på klasse CD
140
141
142 //Klassedefinisjon for utlånsobjekt av type dvd.
143 //Må implementere alle abstrakte metoder som den arver.
144 class DVD extends AV
145 {
146   protected String produksjonsland;
147
148   public DVD( String t, String land, int spt, int lt )
149   {
150     super( spt, lt, t );
151     produksjonsland = land;
152   }
153
154   public String toString()
155   {
156     return super.toString() + "\nProduksjonsland: " + produksjonsland;
157   }
158
159   public String ventetid()
160   {
161     String output = "";
162     //implementasjon av arvet abstrakt metode
163     return output;
164   }
165 }  //slutt på klasse DVD

Vi tenker oss nå videre at vi skal lage en klasse Arkiv som inneholder en liste for hver av de tre konkrete typene av utlånsobjekt Bok, CD og DVD:

 1 import java.util.*;
 2 import javax.swing.JTextArea;
 3
 4 public class Arkiv
 5 {
 6   private List<Bok> bokregister;
 7   private List<CD> cdregister;
 8   private List<DVD> dvdregister;
 9
10   public Arkiv()
11   {
12     bokregister = new LinkedList<>();
13     cdregister = new LinkedList<>();
14     dvdregister = new LinkedList<>();
15   }

        //... Resten av klassen

77 }

Vi tenker oss videre at vi ønsker å ha en metode som kan gjennomløpe hver av listene. Avhengig av hvilken liste som blir brukt som aktuell parameter, skal metoden gjennomløpe lista og skrive ut listeinnholdet på det tekstområdet som også er parameter til metoden. Intuitivt skulle vi kanskje tro at en slik metode kunne skrives på denne måten:

  public void listAlle(List<Utlaansobjekt> liste, JTextArea utskrift)
  {
    Iterator<Utlaansobjekt> iter = liste.iterator();
    while (iter.hasNext())
    {
      Utlaansobjekt obj = iter.next();
      utskrift.append(obj.toString() + "\n");
    }
  }

Problemet med denne er imidlertid at den i følge javas typeregler bare kan ha listeparameter av nøyaktig type List<Utlaansobjekt>. Den kan for eksempel ikke ha parameter av type List<Bok>. Dette er jo uheldig, siden Bok er en type Utlaansobjekt. Det vi ønsker oss er en metode som kan brukes på lister av alle typer Utlaansobjekt. En slik metode kan skrives på denne måten:

 
  public void listAlle(List<? extends Utlaansobjekt> liste, JTextArea utskrift)
  {
    Iterator<? extends Utlaansobjekt> iter = liste.iterator();
    while (iter.hasNext())
    {
      Utlaansobjekt obj = iter.next();
      utskrift.append(obj.toString() + "\n");
    }
  }

Vi har altså erstattet datatypen List<Utlaansobjekt> med datatypen List<? extends Utlaansobjekt>. Metoden vil dermed akseptere lister med objekter av en hvilken som helst subklassetype til Utlaansobjekt, for eksempel en liste av type List<Bok>, slik at vi for eksempel kan skrive en metode

  public void listAlleBøker(JTextArea t)
  {
    listAlle(bokregister, t);
  }

Tilsvarende kan gjøres for cdregister og dvdregister.

Typen <? extends Utlaansobjekt> er eksempel på det som kalles begrenset jokertegn. Spørsmålstegnet ? står for en eller annen ukjent type, slik vi har sett eksempel på ovenfor. Men i dette tilfelle er det et krav at den ukjente typen skal være en subtype til Utlaansobjekt, eller eventuelt Utlaansobjekt selv. Typen Utlaansobjekt er det som i dette tilfelle kalles den øvre grensa for jokertegnet.

Det er også mulig å angi nedre grense for jokertegn. Dersom vi for eksempel bruker typebetegnelsen List<? super Bok>, vil vi begrense de mulige aktuelle typene til List<Bok>, List<Utlaansobjekt> og List<Object>.

Mer om generiske metoder

Slik klassehierarkiet for utlånsobjekter er definert ovenfor, har alle typer objekter en tittel. Den blir returnert av metoden getTittel. Alle de tre listene for objekter kan derfor gjennomløpes for å søke etter et objekt med gitt tittel. Vi tenker oss derfor nå at vi skal lage en metode for dette. Metoden skal kunne kalles opp med alle våre tre lister som aktuell parameter, i tillegg til parameter for søkt tittel. Søkemetoden skal returnere (første) objektet som har den tittel som parameteren angir. Typen for dette objektet vil imidlertid avhenge av hvilken av de tre listene det søkes i: For bokregisteret blir det type Bok, for cdregisteret blir det type CD, mens det for dvdregisteret blir type DVD. I slike tilfeller, der typen for returverdien avhenger av typen til en eller flere av parametrene, eller der det er typeavhengighet mellom parametrene innbyrdes, bruker vi generiske metoder. (Se generell omtale av slike metoder ovenfor.) I vårt tilfelle skal returverditypen være lik den type objekt som vedkommende liste av utlånsobjekter inneholder, og denne typen er en subtype til Utlaansobjekt. Metoden kan derfor skrives slik:

  public <T extends Utlaansobjekt> T finnObjekt(List<T> register, String tittel)
  {
    Iterator<T> iter = register.iterator();
    while (iter.hasNext())
    {
      T obj = iter.next();
      if (obj.getTittel().equals(tittel))
      {
        return obj;
      }
    }
    return null;
  }

For å søke etter bøker, kan vi nå skrive en metode som ser ut slik:

  public Bok finnBok(String tittel)
  {
    return finnObjekt(bokregister, tittel);
  }

Tilsvarende kan gjøres for cd-er og dvd-er.

Subtyper av parametriserte typer

Vi skal nå se nærmere på eksemplet der vi hadde en metode for å finne minste element i en array. Metoden begynte på denne måte:

  public static <T extends Comparable> T min(T[] array) ...

Metoden kompilerer med et par advarsler. Advarselene kommer av at interface Comparable i seg selv er en parametrisert type:

public interface Comparable<T>
{
  public int compareTo(T o);
}

Typevariabelen T indikerer her typen til parameteren o i compareTo-metoden. For eksempel har vi at String-klassen implementerer Comparable<String>, og dens compareTo-metode er deklarert som

  public int compareTo(String anotherString) { ... }

Den aktuelle parameteren har dermed riktig type.

For vår min-metode vil det være bedre å skrive den formelle typeparameteren på denne måten:

  public static <T extends Comparable<T>> T min(T[] array) ...

Når metoden er skrevet slik, kompilerer den uten advarsel. Den vil også virke fint i de aller fleste tilfelle. Dersom vi for eksempel vil finne minste element i en String-array, vil T være av type String, og String er en subtype til Comparable<String> (siden String-klassen implementerer Comparable<String>). Men det kan likevel oppstå problemer med den nye versjonen av min-metoden vår! Et eksempel på det er følgende (som er hentet fra læreboka Core Java): Klassen GregorianCalendar er en subklasse til Calendar. (En liten omtale av den finnes i notatet Dato og tid.) Klassen Calendar implementerer Comparable<Calendar>. Siden GregorianCalendar er subklasse til Calendar, vil dermed også den implementere Comparable<Calendar>, men den implementerer ikke Comparable<GregorianCalendar>! En array av type GregorianCalendar[] blir derfor ikke godtatt som aktuell parameter i et kall på vår metode min. Prøver vi oss på det, får vi en feilmelding under kompileringen. Men det finnes en løsning også på dette problemet. Det er å bruke jokertegn med nedre grense på denne måten:

  public static <T extends Comparable<? super T>> T min(T[] array) ...

Denne koden ser unektelig nokså kryptisk og uforståelig ut. Ser vi nærmere på den, ser vi at typen T skal ha en superklasse som implementerer Comparable. Siden GregorianCalendar har en slik superklasse, nemlig Calendar, så er kravet oppfylt for den. Med denne siste deklarasjonen av metoden min, får vi ingen feilmeldinger når vi prøver oss med GregorianCalendar som aktuell type.

Bruke jokertegn eller generisk metode?

Noen ganger er det mulig å skrive en metode enten som en generisk metode, eller isteden som en vanlig metode, men med bruk av jokertegn i datatypen for en eller flere av metodeparametrene. Som eksempel på dette, tar vi igjen for oss Arkiv-metoden listAlle beskrevet ovenfor. Metoden kan gjenomløpe og skrive ut innholdet i en hvilken som helst liste med utlånsobjekter av de typene vi har definert. Samme metode kunne vi skrevet som en generisk metode på denne måte:

  public <T extends Utlaansobjekt> void listAlle(List<T> liste,
                                                            JTextArea utskrift)
  {
    Iterator<T> iter = liste.iterator();
    while (iter.hasNext())
    {
      T obj = iter.next();
      utskrift.append(obj.toString() + "\n");
    }
  }

Vi legger her merke til at typeparameteren T brukes bare i polymorfismesammenheng; dens eneste rolle er å spesifisere hvilken aktuell datatype som er tillatt brukt på forskjellige steder i programkoden. Det er ingen returverdi som er avhengig av hvilken aktuell type T har, og det er heller ingen typeavhengighet mellom de to parametrene til metoden. I slike tilfeller blir det anbefalt at man heller bruker jokertegn, slik det ble gjort i den opprinnelige versjonen av metoden.

Eksempel: Generisk implementasjon av liste

Som eksempel på generisk programmering skal vi ta for oss den heltallslista som ble brukt som eksempel da vi tok for oss serialisering av objekter for å kunne lagre dem på fil. Vi setter oss som oppgave å endre klassene som definerer lista slik at det blir en generisk liste, det vil si en liste som vi kan putte objekter av forskjellige datatyper inn i. Det eneste vi må forutsette er at objektene kan sammenliknes for rekkefølge, siden listeklassen vår inneholdt en metode for å sortere lista, og også en metode for å sette inn et objekt på sortert plass. Dette betyr i praksis at objektene må være av en klassetype som implementerer interface Comparable<E>, slik at det er definert en compareTo-metode for dem. Vi ønsker også som før å kunne lagre objektene på fil. De må derfor være av en type som implementerer interface Serializable. For øvrig kan vi i listeklassen ikke referere til konkrete datatyper som vi gjorde for den opprinnelige lista, der det konkret dreide seg om heltall av type int.

Som det er kommentert tidligere, er det en god regel når det gjelder datastrukturer å tenke i retning av interface som beskriver den struktur det er snakk om, heller enn å tenke på en konkret implementasjon. Implementasjon av vedkommende struktur kan som regel gjøres på flere forskjellige måter. Vi velger derfor her å starte med et interface som beskriver den lista vi skal implementere. Siden lista skal være generisk, må dette komme til uttrykk også i det interface som beskriver den. Det kan se ut på følgende måte:

 1 import java.io.Serializable;
 2
 3 public interface Liste<E extends Comparable<E> & Serializable>
 4 {
 5   public E finn(E e);
 6
 7   public boolean fjern(E e);
 8
 9   public void settInnForrest(E e);
10
11   public void settInnBakerst(E e);
12
13   public void settInnSortert(E e);
14
15   public void sorter();
16
17   public void dubliser();
18
19   public void slett();
20
21   public Liste<E> reversertKopi();
22
23   public void reverser();
24
25   public E[] tilArray(E[] a);
26 }

Den siste metoden, public E[] tilArray(E[] a), hadde vi ikke i den opprinnelige listeklassen, der det isteden var en metode som skrev ut heltallene som lista inneholdt på et tekstområde som ble mottatt. Siden datatypen for objektene i lista nå er ukjent, må vi gjøre det på en annen måte. En måte å gjøre det på er å ha en metode som returnerer en array som inneholder alle objektene i lista. Et program som bruker lista kan gjennomløpe arrayen for å skrive dem ut, for eksempel ved å gjøre kall på objektenes toString-metode. Her er en link til fila som inneholder koden ovenfor: Liste.java.

Listeimplementasjonen

I den opprinnelige implementasjonen ble det definert en klasse Heltallsnode for listeobjektene. Av data inneholdt klassen et heltall og en nestepeker. Nå skal lista inneholde objekter av en ukjent type. Vi kan ikke forutsette at det i disse objektene finnes noen nestepeker. Løsningen må derfor bli å definere en nodeklasse som inneholder et objekt av den ukjente typen og en nestepeker. Vi har valgt å definere denne klassen som en privat indre klasse i listeklassen, og siden det ikke inni nodeklassen er noe behov for å referere til noe som ligger i den omgivende klassen, kan den være static, og et skall for listeklassen kan se ut på følgende måte:

  1 import java.io.Serializable;
  2 import java.lang.reflect.Array;
  3
  4 public class KjedetListe<E extends Comparable<E> & Serializable>
  5         implements Liste<E>, Serializable
  6 {
  7   private Node<E> hode;
  8
  9   public KjedetListe()
 10   {
 11     hode = null;
 12   }

      <Metoder>

167   private static class Node<E> implements Serializable
168   {
169     E element;
170     Node<E> neste;
171
172     public Node(E e)
173     {
174       element = e;
175     }
176   }
177 }

Siden vi ønsker at listeobjektet skal kunne lagres på fil, må vi spesifisere at både listeklassen og nodeklassen implementerer interface Serializable. Importeringen av java.lang.reflect.Array skal vi komme tilbake til seinere.

Noen av listemetodene er greie å implementere på grunnlag av den gamle koden. De lar seg nokså direkte oversette ved å bytte ut den gamle nodetypen med den nye. Disse metodene er gjengitt nedenfor uten nærmere kommentarer.

 14   //Returnerer første forekomst av e
 15   public E finn(E e)
 16   {
 17    Node<E> hjelp = hode;
 18     while (hjelp != null && !hjelp.element.equals(e))
 19       hjelp = hjelp.neste;
 20     return hjelp.element;
 21   }
 22
 23   //Fjerner første forekomst av e
 24   public boolean fjern(E e)
 25   {
 26     if (hode == null) //tom liste
 27       return false;
 28     if (hode.element.equals(e))
 29     {
 30       hode = hode.neste;
 31       return true;
 32     }
 33     Node<E> hjelp = hode;
 34     while (hjelp.neste != null)
 35     {
 36       if (hjelp.neste.element.equals(e))
 37       {
 38         hjelp.neste = hjelp.neste.neste;
 39         return true;
 40       }
 41       hjelp = hjelp.neste;
 42     }
 43     return false;
 44   }
 45
 46   //setter inn forrest ny node med mottatt verdi
 47   public void settInnForrest(E e)
 48   {
 49     Node<E> ny = new Node(e);
 50     ny.neste = hode;
 51     hode = ny;
 52   }
 53
 54   //setter inn bakerst ny node med mottatt verdi
 55   public void settInnBakerst(E e)
 56   {
 57     Node<E> ny = new Node(e);
 58     if (hode == null) //tom liste
 59       hode = ny;
 60     else
 61     {
 62       Node<E> hjelp = hode;
 63       while (hjelp.neste != null) //plasserer hjelp på siste node
 64         hjelp = hjelp.neste;
 65
 66       hjelp.neste = ny;
 67     }
 68   }

Når vi kommer til metoden for å sette inn ny node på sortert plass, må vi istedenfor for å bruke sammenlikningsoperatoren for hele tall bruke objektenes compareTo-metode på riktig måte. Koden for denne metoden blir derfor seende ut som følger:

 70   //setter inn mottatt verdi i ny node som plasseres 
 71   //på riktig plass i sortert liste
 72   public void settInnSortert(E e)
 73   {
 74     Node<E> ny = new Node(e);
 75     if ( hode == null ) //tom liste
 76       hode = ny;
 77     else if(hode.element.compareTo(e) > 0)
 78       settInnForrest(e);
 79     else
 80     {
 81       Node<E> hjelp = hode;
 82       while (hjelp.neste != null &&
 83               hjelp.neste.element.compareTo(e) < 0)
 84         hjelp = hjelp.neste;
 85
 86       ny.neste = hjelp.neste;
 87       hjelp.neste = ny;
 88     }
 89   }

Når denne innsettingsmetoden er på plass, kan vi oversette den gamle sorteringsmetoden nokså direkte ved å gjøre kall på innsettingsmetoden:

 91   // sorterer lista
 92   public void sorter()
 93   {
 94     Node<E> hjelp = hode;
 95     KjedetListe<E> l = new KjedetListe<>();
 96
 97     while(hjelp != null)
 98     {
 99       l.settInnSortert(hjelp.element);
100       hjelp = hjelp.neste;
101     }
102     hode = l.hode;
103   }

De fire neste metodene er også greie å oversette. De blir seende ut som følger:

105   //setter inn en kopi av hver node i lista
106   public void dubliser()
107   {
108     Node<E> hjelp = hode;
109     while (hjelp != null)
110     {
111       Node<E> ny = new Node(hjelp.element);
112       ny.neste = hjelp.neste;
113       hjelp.neste = ny;
114       hjelp = hjelp.neste.neste;
115     }
116   }
117
118   //sletter alle nodene i lista
119   public void slett()
120   {
121     hode = null;
122   }
123
124   //returnerer et listeobjekt som er en kopi
125   //av denne liste, men med nodene i reversert rekkefølge
126   public Liste<E> reversertKopi()
127   {
128     KjedetListe<E> kopi = new KjedetListe<>();
129     Node<E> hjelp = hode;
130     while (hjelp != null)
131     {
132       kopi.settInnForrest(hjelp.element);
133       hjelp = hjelp.neste;
134     }
135     return kopi;
136   }
137
138   //reverserer nodenes rekkefølge
139   public void reverser()
140   {
141     hode = ((KjedetListe) reversertKopi()).hode;
142   }

Den mest utfordende metoden å få til er den som skal returnere listeinnholdet lagt inn i en array. Denne arrayen må opprettes inni metoden. Datatypen for objektene som arrayen skal inneholde er en generisk type, altså ukjent. Problemet er at det ikke er mulig å opprette generiske objekter eller arrayer. Vi kan altså ikke skrive kode slik som

  E element = new E();  //Gir kompileringsfeil!

eller

  E[] array = new E[antall];  //Gir kompileringsfeil!

Det er heller ikke tillatt å bruke typeparametre ved testing på datatype. Vi kan altså ikke skrive slik som

  if (element instanceof E)  //gir kompileringsfeil!
    ...

For å skjønne hvorfor det er slik, er det nyttig å kjenne litt mere til hva som skjer "bak kulissene" når vi bruker generiske klasser og metoder. Vi ser derfor nærmere på det før vi tar for oss den nevnte metoden.

Typeutvisking

Javas kjøresystem kjenner ikke til objekter av generisk type — alle objektene tilhører ordinære klassetyper. Grunnen til at det er gjort slik, er at det finnes svært mye javakode som er skrevet før generiske typer ble introdusert i javaversjon 5. (Slik, gammel kode blir på engelsk kalt 'legacy code'.) Det var ønskelig at generiske klasser kunne samhandle med kode som var skrevet tidligere. For å få til dette, blir det under kompilering av generisk kode foretatt en oversettelse til kode med ordinære klasser. Typeinformasjonen om hvilken aktuell datatype som er brukt som erstatning for formelle typeparametre blir brukt under kompileringsprosessen for å sjekke om datatypene blir brukt på korrekt måte, men deretter blir all slik typeinformasjon fjernet. Den er derfor ikke tilgjengelig under kjøring. De instruksjonene som er listet opp ovenfor som ikke tillatt, er nettopp slikt som blir utført under kjøring, og da er altså ikke typeinformasjonen for generisk kode tilgjengelig.

Hver gang vi definerer en generisk type, blir det samtidig automatisk opprettet en tilsvarende såkalt råtype (engelsk: raw type). Denne har samme navn som den generiske typen, bare med den forskjell at typeparametre er fjernet. Typeparametene er visket ut og erstattet av sine tilsvarende øvre eller nedre grensetyper. Dersom det ikke foreligger noen begrensende type, så vil det bli brukt type Object. Og dersom vi har en generisk type med flere grenser, så er det den første av disse som blir brukt som erstatningstype. For eksempel så vil råtypen for skallet som er skissert ovenfor for listeklassen vår se ut som dette:

public class KjedetListe implements Serializable
{
  private Node hode;

  public KjedetListe()
  {
    hode = null;
  }

  <Metoder>

  private static class Node implements Serializable
  {
    Comparable element;
    Node neste;

    public Node(Comparable e)
    {
      element = e;
    }
  }
}

Bruk av refleksjon til å skrive generisk arraykode

Vi går så tilbake til implementasjonen av metoden

  public E[] tilArray(E[] resultat);

Vi kan altså ikke skrive kode tilsvarende som

  E[] array = new E[antall];  //Gir kompileringsfeil!

Et alternativ som enkelte ganger virker, er isteden å skrive slik:

  E[] array = (E[]) new Object[antall];

Dette gir ingen kompileringsfeil, men en usjekket kompileringsadvarsel. Denne skyldes at kompilatoren ikke er sikker på om typekonverteringen lar seg utføre under kjøring. I vårt tilfelle skal E være av type Comparable. Prøver vi å kjøre programmet med den nevnte koden, så resulterer det i en ClassCastException med følgende forklaring:

  java.lang.Object; cannot be cast to java.lang.Comparable;

Altså må vi finne på noe bedre. Redningen er i finne i klassen Array i pakken java.lang.reflect. I denne finnes metoden

  public static Object newInstance(Class componentType,
                   int length) throws NegativeArraySizeException

Det ser ikke umiddelbart innlysende ut at vi kan bruke denne til å få generert en ny array av den typen vi trenger, men det kan vi faktisk. Som inngangsparametre trenger metoden informasjon om komponenttypen og antall plasser for den arrayen den skal opprette og returnere. Her kommer forklaringen på at det i vår metode er en parameter av type E[], kalt resultat. Eneste oppgaven den har er nettopp å gi komponenttypen for den arrayen metoden skal opprette og returnere. Når vi har både den og antall komponenter, kan vi få opprettet den ønskede arrayen ved å skrive følgende instruksjon:

    E[] array = (E[]) Array.newInstance(
            resultat.getClass().getComponentType(), antall);

For å få tak i antall komponenter, må vi rett og slett gjennomløpe den sammenkjedete lista og telle opp antall noder. Fullstendig kode for metoden blir da som følger:

144   //returnerer en array som inneholder alle elementene i lista,
145   //i samme rekkefølge som de har i lista
146   public E[] tilArray(E[] resultat)
147   {
148     int antall = 0;
149     Node<E> hjelp = hode;
150     while (hjelp != null)
151     {
152       antall++;
153       hjelp = hjelp.neste;
154     }
155     E[] array = (E[]) Array.newInstance(
156             resultat.getClass().getComponentType(), antall);
157     hjelp = hode;
158     int indeks = 0;
159     while (hjelp != null)
160     {
161       array[indeks++] = hjelp.element;
162       hjelp = hjelp.neste;
163     }
164     return array;
165   }

Dermed er den generiske listeklassen ferdig. Her er en link til javafila: KjedetListe.java.

Testvindu

Vindusklassen som tester ut listeklassen het i det opprinnelige programmet Listevindu. I denne er det ikke nødvendig å gjøre så store endringer. Men iallfall må vi skifte datatype og konstruktør for lista. Istedenfor type Heltallsliste bruker vi nå den generiske typen Liste<Integer>. Vi bruker altså interface-typen som datatype, slik det tidligere er anbefalt. Ved opprettelsen av listeobjektet bruker vi diamantoperatoren og navnet på klassen som implementerer interface'et:

    heltallsliste = new KjedetListe<>();

Også ved innlesing av listeobjektet fra fil må vi konvertere til den riktige typen:

    heltallsliste = (Liste<Integer>) innfil.readObject();

Den reviderte metoden for innlesing fra fil ser dermed ut som følger:

 94   private void lesFil()
 95   {
 96     try (ObjectInputStream innfil = new ObjectInputStream(
 97             new FileInputStream( "src/liste.data" )))
 98     {
 99       heltallsliste = (Liste<Integer>) innfil.readObject();
100     }
101     catch(ClassNotFoundException cnfe)
102     {
103       lista.setText(cnfe.getMessage());
104       lista.append("\nOppretter tom liste.\n");
105       heltallsliste = new KjedetListe<>();
106     }
107     catch(FileNotFoundException fne)
108     {
109       lista.setText("Finner ikke datafil. Oppretter tom liste.\n");
110       heltallsliste = new KjedetListe<>();
111     }
112     catch(IOException ioe)
113     {
114       lista.setText("Innlesingsfeil. Oppretter tom liste.\n");
115       heltallsliste = new KjedetListe<>();
116     }
117   }

En annen metode som vi trenger å endre, er den som skriver ut listeinnholdet på et tekstområde. Opprinnelig så ble tekstområdet sendt som parameter til en metode i listeklassen, og så var det denne som fylte tekstområdet med innhold. Som nevnt under implementasjonen av den nye listeklassen, kan vi ikke gjøre det slik nå, siden listeklassen ikke kjenner den aktuelle datatypen for verdiene som skal skrives ut. Isteden implementerte vi i listeklassen metoden tilArray som returnerte en array med alle objektene i lista. Denne må vi nå gjøre bruk av. Utskriftsmetoden blir dermed seende ut som følger:

190   public void skrivListe()
191   {
192     lista.setText("");
193     Integer[] liste = new Integer[2];
194     liste = heltallsliste.tilArray(liste);
195     if (liste.length == 0)
196       lista.append("Tom liste.");
197     for (int i = 0; i < liste.length; i++)
198     {
199       lista.append(liste[i].toString() + " ");
200       if ((i + 1) % 10 == 0)
201         lista.append("\n");
202     }
203   }

I denne metoden lurer du sikkert på hva som er hensikten med instruksjonen

193     Integer[] liste = new Integer[2];

Hensikten er ikke noe annet enn å bruke arrayen liste som parameter i kallet på tilArray og dermed kunne informere metoden tilArray om hva som er datatypen for elementene i den arrayen som metoden skal opprette og returnere. Som forklart foran under implementasjonen av metoden så er det nødvendig.

For øvrig er det bare noen mindre endringer som er nødvendige å gjøre i vindusklassen. Men siden du sannsynligvis kan en del mer om utforming av grafiske grensesnitt når du leser dette, så har jeg også valgt å forbedre vinduets layout. Den nye vindusklassen er kalt Listetester. Et bilde av vinduet, med noen verdier innsatt i lista, er vist nedenfor. Her er en link til kildefila for vindusklassen: Listetester.java. Og her er link til driverklasse: Listetest.java.

Innholdsoversikt for programutvikling