Innholdsoversikt for programutvikling

Collections — bruk av generiske datatyper

• Innledning
• Lister
  • Listeeksempel med generisk datatype
  • Bruke generiske datatyper eller ikke?
  • Anbefalinger for navnebruk på typeparametre
• Innpakningsklasser og autoboksing
• interface Collection<E>
• interface List<E>
• Iteratorer
• Vector-klassen versus ArrayList
• Ordning av objekter (for rekkefølge)
• Sortering
• Comparators
• Sortering av strenger
• Eksempel: Definere rekkefølge for Person-objekter
• Søking
• Mengder
• Sorterte mengder
• Objektsammenlikning
• Avbildning (Map)
• HashMap-klassen versus Hashtable
• Spesialoperasjoner for SortedMap

Innledning

Det som i datasammenheng menes med det engelske ordet 'collection', er en samling av elementer. Java-biblioteket har et interface Collection som skal representere dette begrepet. Dette interface sier ikke noe spesielt om hva slags objekter samlingen skal bestå av eller hvordan den skal være organisert. (Samlingen kan imidlertid ikke inneholde verdier av primitive datatyper, den kan bare inneholde objekter.) I interface Collection blir det bare listet opp noen metoder som skal kunne brukes på alle samlinger av den typen interfacet beskriver. Det er i hovedsak metoder for å sette inn og fjerne objekter, sjekke om objekter finnes, og for å gjennomløpe samlingen.

Det skilles mellom fire hovedtyper av samlinger, avhengig av om duplikater er tillatt eller ikke, og om det er noen form for ordning eller ikke av elementene. Typene er som følger:

Fra før av er vi kjent med samlinger av type array og liste. Array-typen er en av standard-datatypene i java, det vil si innebygget i selve språket. Lister har vi programmert selv. På både arrayer og lister har vi utført diverse typer operasjoner. Det kan være andre typer operasjoner som også kan være ønskelige å utføre i enkelte situasjoner. Bibliotek-klassen java.util.Arrays inneholder et stort antall static-metoder for utføring av standardoperasjoner på arrayer. Arrayene som operasjonene skal utføres på, settes inn som parametre i metodekallene.

Alle klasser og interface som har med samlinger (collections) å gjøre, befinner seg i pakken java.util. Det blir brukt interface for å beskrive begrepene som definerer de forskjellige typene samlinger. Følgende figur viser en oversikt over de interface'ene i java.util som vi skal se nærmere på.

Av figuren går det fram at Set, List og Queue er subinterface til Collection, som betyr at de definerer spesielle typer collection. SortedSet er i sin tur subinterface til Set og definerer en spesiell type mengde, nemlig ordnet (sortert) mengde. De to interfacene Map og SortedMap definerer strukturer som svarer til det matematiske begrepet avbildning eller tilordning, som gir en relasjon mellom (nøkkel)verdier (funksjonsargumenter) og tilhørende (funksjons)verdier, for eksempel mellom personer og deres bostedsadresse. (Matematisk sett gir dette en mange-til-en-relasjon: For hver nøkkelverdi er det tilordnet bare én bestemt verdi, men denne verdien kan bli tilordnet av flere forskjellige nøkkelverdier. Eksempler: hver person har bare én bestemt bostedsadresse, men på denne adressen kan det bo flere personer. En funksjon har bare én bestemt funksjonsverdi for hver argumentverdi, men det kan være flere forskjellige argumentverdier (x-verdier) som gir samme funksjonsverdi.)

I pakken java.util finnes det også klasser som gir en implementasjon av de interface som er vist på figuren ovenfor. For noen av dem finnes det flere forskjellige implementasjoner. For eksempel finnes klassene ArrayList og LinkedList som gir to forskjellige implementasjoner av listebegrepet. Disse kan vi altså bruke som alternativ til de listeklassene vi selv har implementert. Vår egen implementasjon var altså i og for seg unødvendig, men på den andre side er det svært nyttig å vite hva som egentlig foregår 'bak kulissene' når en bruker den ene eller den andre av en ferdigprogrammert implementasjon. Det er også slik at de nevnte implementasjonene, siden de ikke er tilpasset en bestemt datatype, inneholder en del operasjoner som vi ikke alltid trenger. Derfor kan det i mange situasjoner være vel så greit selv å programmere en liste som er 'skreddersydd' for den datatypen den skal inneholde. Alle klasser i java.util som implementerer noen av de nevnte interface, implementer også interface Serializable, slik at objektene kan lagres på fil, forutsatt at de objektene vi setter inn i dem også implementerer dette interface.

Lister

interface List definerer en liste som en ordnet samling (sekvens) av elementer. Ordnet betyr her at hvert element er tilordnet en indeksposisjon (fra 0 og oppover). En liste kan inneholde duplikater.

List er et subinterface til Collection og har derfor alle metoder i dette. I tillegg definerer det noen metoder som er spesifikke for lister. Det er blant annet metoder for

• posisjonell aksess (bestemt av indeks)
• søking (returnerer indeks)
• utvidet funksjonalitet ved gjennomløping
• hente ut subliste

Klassebiblioteket inneholder to klasser som implementerer listebegrepet:

ArrayList gir en array-implementasjon. Den underliggende array som inneholder elementene blir automatisk utvidet ved behov.

LinkedList gir en sammenkjedet implementasjon. Denne har i tillegg egne metoder for å hente ut, sette inn, eller fjerne element i den ene eller den andre enden, slik at lista kan brukes som stakk eller kø.

I mange tilfeller vil bruk av ArrayList være mest effektivt. Ut fra kjennskap til arrayer vet vi at det er tilfelle dersom vi gjør mye bruk av referanse til objekter ved hjelp av indekser. I en array kan en da gå rett inn på vedkommende indeksposisjon, mens man i en sammenkjedet liste må søke lineært forover eller bakover for å finne en gitt indeksposisjon. Men dersom vi har en liste der det er mye innsetting eller fjerning, er en sammenkjedet liste mer effektiv. Særlig vil dette være tilfelle dersom innsetting eller fjerning skjer i første halvdel av lista. I tilfelle array-implementasjon vil det da bli mye flytting av objekter. (Egentlig er det flytting av referanser til objekter det er snakk om.)

Listeeksempel

I notat Introduksjon til programmering, kapittel 10 Objektorientert programmering: polymorfisme, ble det gitt et eksempel på klassehierarki for utlånsobjekter. Koden for dette finnes i fila Utlaansobjekt.java. Til den abstrakte klassen Utlaansobjekt ble det definert flere subklasser, blant annet den ikke-abstrakte klassen Bok.

Vi tenker oss nå at vi skal opprette en liste av slike utlånsobjekter og velger å lage den i form av en LinkedList. For enkelhets skyld skal vi i dette eksemplet bare lage metoder for å sette inn et nytt objekt bakerst i lista, samt å hente ut objektet som er bakerst i lista. Ved bruk av metoder spesifisert i interface List kunne vi ha skrevet en klasse for dette på følgende måte:

import java.util.*;

class Mediatek
{
  private List register = new LinkedList();

  public void settInnUtlaansobjekt( Utlaansobjekt obj )
  {
    register.add( obj ) ;
  }

  public Utlaansobjekt hentSiste()
  {
    int antall = register.size();
    if ( antall > 0 )
      return (Utlaansobjekt) register.get( antall - 1 );
    else
      return null;
  }
}

Vi legger her merke til at ved bruk av List-metoden get, må vi foreta typekonvertering til den typen som vår metode skal returnere. Grunnen til dette er at returverdien fra get-metoden er av type Object. For øvrig ville det her ha lønt seg å deklarere lista register til å være av type LinkedList istedenfor av den generelle typen List, for da kunne vi gjort bruk av metoden getLast som i dette tilfelle ville vært mer effektiv, siden den gjør bruk av siste-pekeren til den sammenkjedete lista.

Vi tenker oss nå videre at vi vil lage et program der det er en samling utlånsobjekter som utelukkende består av bøker. I et slikt program kunne vi hatt følgende instruksjoner:

  //Et Mediatek som bare skal inneholde bøker
  Mediatek boksamling = new Mediatek();

  ...

  //Skal hente ut siste bok fra boklista:
  Bok siste = (Bok) boksamling.hentSiste();
  ...

Vi merker oss igjen at vi er nødt til å foreta den brysomme typekonverteringen. Selv om vi vet at det bare er Bok-objekter vi har satt inn, kan ikke kompilatoren vite det. For øvrig ville kompilatoren tillate at det også ble satt inn objekter av de andre subklassetypene til Utlaansobjekt, og dersom det hadde skjedd, ville vi under kjøring fått en ClassCastException i tilfelle vi prøvde å konvertere disse til type Bok.

Blant annet for at vi skal slippe slik brysom typekonvertering som vi har eksempler på ovenfor, og også slippe uforutsette kjørefeil på grunn av forsøk på typekonvertering mellom typer som ikke er kompatible, er det fra og med javaversjon 1.5 (også kalt 5.0) innført såkalte generiske eller parametriserte typer. Det går ut på at vi ved hjelp av en såkalt typeparameter spesifiserer hvilken datatype en samling objekter kan inneholde. I tillegg til at vi slipper den brysomme typekonverteringen, oppnår vi at det er typesjekking allerede når programmet blir kompilert, slik at det ikke blir mulig å sette inn i samlingen andre typer objekter enn den typen den er bestemt til å inneholde.

Listeeksempel med generisk datatype

Hensikten med generisk programmering, er å skrive kode som kan brukes om igjen for mange forskjellige typer objekter. Nedenfor er vår Mediatek-klasse skrevet om slik at den blir en generisk datatype. Den har da en typeparameter E for datatypen til de objektene den skal inneholde. Den blir dermed en generisk datatype med én enkelt formell typeparameter E.

 1 import java.util.*;
 2
 3
 4 class Mediatek<E>
 5 {
 6   private List<E> register = new LinkedList<E>();
 7
 8   public void settInnUtlaansobjekt( E obj )
 9   {
10     register.add( obj ) ;
11   }
12
13   public E hentSiste()
14   {
15     int antall = register.size();
16     if ( antall > 0 )
17       return register.get( antall - 1 );
18     else
19       return null;
20   }
21 }

I et tenkt program der vi skal bruke den generiske datatypen, må vi istedenfor den formelle typeparameteren skrive klassenavnet for den klassen som definerer objektene som vi vil bruke i det aktuelle tilfellet. Dersom vi for eksempel har til hensikt å sette inn Bok-objekter i mediateket vårt, kan vi nå skrive følgende instruksjoner:

  //Et Mediatek som bare skal inneholde bøker
  Mediatek<Bok> boksamling = new Mediatek<Bok>();

  ...

  //Skal hente ut siste bok fra boklista:
  Bok siste = boksamling.hentSiste();
  ...
  //Det er ikke nødvendig å foreta noen endringer i Bok-klassen
  //eller de andre klassene i hierarkiet som den tilhører.

Når vi oppretter Mediatek-objektet boksamling, må vi spesifisere ved hjelp av en aktuell typeparameter hvilken type objekter klassen skal inneholde.

Merknad

Fra og med javaversjon 7 er kompilatoren gitt større muligheter for å kunne finne ut hva datatypen er ut fra sammenhengen når det blir opprettet objekter av parametriserte typer. Istedenfor instruksjonen

  Mediatek<Bok> boksamling = new Mediatek<Bok>();

som er brukt ovenfor, er det i Java 7 tillatt å forenkle til

  Mediatek<Bok> boksamling = new Mediatek<>();

Paret <> av spissparenteser blir uformelt kalt for diamantoperatoren.

Bruke generiske datatyper eller ikke?

Selv om java 1.5 og seinere versjoner definerer de forskjellige komponentene som inngår i Collections-rammeverket til å være generiske datatyper, er det fortsatt anledning til å bruke det på den gamle måten, slik det ble gjort i det første eksemplet ovenfor. Objektene som samlingene inneholder blir da tolket til å være av type Object. Vi blir da nødt til å foreta slike typekonverteringer som ble gjort i det nevnte eksemplet. Ved å bruke generiske datatyper på samlinger (collections), oppnår vi følgende fordeler:

• Kompilatoren kan sjekke for riktig datatype alle operasjoner som tilføyer objekter til samlingen. Mulige feil oppdages allerede ved kompileringen.
• Typen til objekter som hentes ut fra samlingen er kjent av kompilatoren, typekonvertering er unødvendig.

På grunn av de nevnte fordelene blir det anbefalt at klassene i Collections-rammeverket brukes som generiske datatyper. Det blir gjort i beskrivelsene og eksemplene i det følgende.

Anbefalinger for navnebruk på typeparametre

Det anbefales at det som navn på en formell typeparameter brukes én enkelt stor bokstav. Dette øker lesbarheten av programmer ved å lage et klart skille mellom klassenavn og navn på typeparametre. Følgende bokstaver er de vanligste å bruke som formelle typeparametre:

• <T> — for Type
• <S> — for Type, når T allerede er i bruk
• <E> — for Element (mye brukt i Collections-rammeverket)
• <K> — for Key (nøkkel)
• <V> — for Value
• <N> — for Number

Som aktuell typeparameter når vi oppretter et objekt av en generisk datatype, kan vi bruke en hvilken som helst klasse, men vi kan ikke bruke primitive datatyper som for eksempel int.

Innpakningsklasser og autoboksing

Ordet 'boksing' har her ikke noe med boksesporten å gjøre, men med det å pakke noe inn i eller ut av en boks!

I Introduksjon til programmering, kapittel 5, ble det skrevet litt om Innpakningsklasser. Som nevnt ovenfor, er det i en samling definert av Collection-rammeverket bare tillatt å sette inn objekter, ikke verdier av primitive datatyper. Også i noen andre javasammenhenger er det bare tillatt å bruke objekter. Blant annet på grunn av dette er det for alle de primitive datatypene definert en tilsvarende klasse. Et objekt av klassen representerer den tilsvarende verdien av primitiv datatype, og denne, eller eventuelt en String-representasjon av den, må brukes som konstruktørparameter når vi oppretter objektet. Innpakningsklassene har navn som klart indikerer hvilken primitiv datatype de representerer. Det er klassene Integer, Long Float, Double, Short, Byte, Character og Boolean.

Innpakningsklassene er immutable, det vil si at når et objekt først er opprettet, så er det ikke mulig å endre det. (Tilsvarende er for øvrig tilfelle med String-objekter.) Innpakningsklassene er også final, det vil si at det er ikke mulig å definere subklasser av dem.

Vi kan altså ikke ha noen Collection bestående av primitive verdier. Dersom vi for eksempel ønsker å ha en liste med int-verdier, så må vi definere den som en List<Integer>, for eksempel ved

  List<Integer> heltallsliste = new ArrayList<>();

Jeg minner dessuten om at bruk av diamantoperatoren forutsetter at vi bruker javaversjon 7 eller nyere. Før javaversjon 5 var det slik at når vi skulle sette inn en verdi, for eksempel 3, i en slik liste, så måtte vi selv skrive kode for å opprette det nødvendige Integer-objektet:

  heltallsliste.add(new Integer(3));

Men fra og med javaversjon 5 er det i kompilatoren lagt inn automatikk for å opprette objekter av innpakningsklasser, slik at vi kan skrive

  heltallsliste.add(3);

Kompilatoren vil da oversette dette til koden som er skrevet ovenfor. Denne konverteringen kalles autoboksing.

Det motsatte er det også lagt inn automatikk for, på den måten at vi kan tilordne en Integer-verdi til en int-variabel:

  int n = heltallsliste.get(i);

Dette blir av kompilatoren automatisk oversatt til

  int n = heltallsliste.get(i).intValue();

Slik autoboksing og -utpakking virker til og med på aritmetiske uttrykk. Det er for eksempel tillatt å skrive slik som

  Integer i = 3;
  i++;

Vi kan nesten få inntrykk av at det er likegyldig om vi bruker primitiv datatype eller den tilsvarende innpakningstypen. Men det er en viktig forskjell iallfall når det gjelder testing på likhet. For å teste på likhet mellom verdier av primitiv type bruker vi likhetsoperatoren ==. Den kan vi også bruke for objekter. Men det som det da testes på, er om det blir referert til samme objektet, altså om pekerverdiene eller referansene er lik hverandre, det vil si om det blir referert til samme sted i maskinens memory. For eksempel ville følgende kode neppe gi det resultatet vi ønsket:

  Integer m = 100;
  Integer n = 100;
  .
  .
  if (m == n)
    ...

Det er imidlertid tillatt for en javakompilator å pakke inn like verdier i det samme objektet, slik at sammenlikningen ovenfor faktisk kunne gi riktig resultat. Men dette er noe vi ikke kan være sikre på. Løsningen er å konsekvent bruke equals-metoden dersom det er test på likhet av innhold vi ønsker å utføre. En svært vanlig feil er for øvrig å glemme dette når String-verdier skal sammenliknes for likhet (av innhold).

interface Collection<E>

Følgende kodelisting viser noe av innholdet i interface Collection<E>:

public interface Collection<E> extends Iterable<E>
{
    //Basic operations
    int size();
    boolean isEmpty();
    boolean contains(Object element);
    boolean add(E element);         //optional
    boolean remove(Object element); //optional
    Iterator<E> iterator();

    //Bulk operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c); //optional
    boolean removeAll(Collection<?> c);        //optional
    boolean retainAll(Collection<?> c);        //optional
    void clear(); //optional

    //Array operations
    Object[] toArray();
    <T> T[] toArray(T[] a);
}

Noe av symbolikken for de formelle typeparametrene som er brukt her har vi foreløpig ikke vært borti. Den blir forklart seinere, når vi får bruk for den. Metoder som det står
//optional bak, er det ikke nødvendig å implementere for klasser som implementerer interface Collection. Dersom vi prøver å gjøre kall på en slik metode og den ikke er implementert av vedkommende Collection-objekt, vil det bli kastet ut en UnsupportedOperationException. Alle klassene i javas klassebibliotek som implementerer interface Collection, implementerer alle metodene.

interface List<E>

Følgende kodelisting viser metoder interface List<E> har i tillegg til de som blir arvet fra interface Collection<E>.

public interface List<E> extends Collection<E>
{
    //Positional access
    E get(int index);
    E set(int index, E element);    //optional
    boolean add(E element);         //optional
    void add(int index, E element); //optional
    E remove(int index);            //optional
    abstract boolean addAll(int index,
        Collection<? extends E> c);  //optional

    //Search
    int indexOf(Object o);
    int lastIndexOf(Object o);

    //Iteration
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);

    //Range-view
    List<E> subList(int from, int to);
}

List<E> blir implementert av klassene LinkedList<E> og ArrayList<E>.

Iteratorer

En iterator blir brukt til gjennomløping av elementene i en samling. interface Iterator<E> spesifiserer følgende tre metoder:

  E next()
  boolean hasNext()
  void remove()

Vi kan tenke oss en iterator som en markør som er mellom elementer i samlingen. Når vi gjør kall på next, vil iteratoren hoppe over det neste elementet og returnere en peker til dette. Kall på remove vil fjerne elementet som sist ble returnert av next.

List-metoden iterator, som er spesifisert i interface Collection<E>, returnerer et Iterator-objekt av den beskrevne typen. I tillegg finnes det for List-objekter en iteratortype med tilleggsegenskaper. Denne er spesifisert av interface ListIterator<E> som er subinterface til Iterator<E>. Et slikt objekt blir returnert av List-metoden listIterator. En ListIterator tillater, i tillegg til det som blir arvet fra Iterator, gjennomløping i baklengs retning, samt å sette inn eller erstatte elementer under gjennomløpingen, uavhengig av i hvilken retning gjennomløpingen blir utført. (Siden baklengs gjennomløping er mulig, skjønner vi at den sammenkjedete lista definert av klassen LinkedList er en toveis-liste: objektene inneholder pekere til både neste og til foregående objekt.) Her følger en nærmere beskrivelse av disse tilleggsegenskapene til en ListIterator:

Baklengs gjennomløping:

Bruker previous og hasPrevious (istedenfor next og hasNext). Ved listeslutt (uavhengig av gjennomløpsretning): NoSuchElementException.

Innsetting:

add( <objekt> ) setter inn det nye objektet på et sted slik at neste kall på next vil bli uberørt av innsettingen. Neste kall på previous ville ha returnert det nye objektet.

Fjerning:

remove fjerner siste element som ble returnert av next eller previous. Ikke tillatt å utføre dersom add er blitt kalt etter siste kall på next eller previous. (Forsøk på dette resulterer i IllegalStateException.)

Erstatning:

set( <objekt> ) erstatter siste element returnert av next eller previous med det objekt som er parameter. (Ikke tillatt å utføre dersom remove i mellomtida er blitt kalt.)

Programeksempel 1

I programmet Listetest som er gjengitt nedenfor, blir det opprettet to lister a og b av type LinkedList<String>. I begge blir det lagt inn noen navn ved bruk av add-metoden. Deretter skjer følgende:
- Navnene i b blir flettet inn blant navnene i a, uten at b endres. Deretter skrives a ut.
- Annet hvert navn i b blir fjernet. Deretter skrives b ut.
- Alle (gjenværende) navn som forekommer i b blir fjernet fra a. Deretter skrives a ut.

I programmet legger vi spesielt merke til hvordan iteratorer blir brukt til å gjennomløpe listene. Ved kjøring viser programmet dialogboksen som er gjengitt på følgende bilde.

 1 import javax.swing.*;
 2 import java.util.*;
 3
 4 public class Listetest
 5 {
 6   public static void main(String[] args)
 7    {
 8       String output = "";
 9       List<String> a = new LinkedList<>();
10       a.add("Amelie");
11       a.add("Catherine");
12       a.add("Emanuelle");
13
14       List<String> b = new LinkedList<>();
15       b.add("Brigitte");
16       b.add("Denise");
17       b.add("Fantine");
18       b.add("Gilberte");
19
20       // fletter ordene fra b inn i a
21       ListIterator<String> aIter = a.listIterator();
22       Iterator<String> bIter = b.iterator();
23
24       while (bIter.hasNext()) //så lenge som b har flere elementer
25       {
26          if (aIter.hasNext()) //gå til neste i a, 
27             aIter.next();     //i tilfelle den har flere
28          aIter.add(bIter.next()); //går til neste element i b og 
29             //setter det inn foran neste element i a. (Neste kall på 
30             //aIter.next() vil være upåvirket av innsettingen.)
31       }
32
33       output += a.toString() + "\n";
34
35       // fjerner hvert annet ord fra b
36       bIter = b.iterator();
37       while (bIter.hasNext())
38       {
39          bIter.next(); // hopper over et element
40          if (bIter.hasNext())
41          {
42             bIter.next(); // hopper til neste element
43             bIter.remove(); // fjerner elementet (Fjerner fra lista 
44                       //det siste elementet som ble returnert ved 
45                       //kall på next-metoden.)
46          }
47       }
48
49       output += b.toString() + "\n";
50
51       // fjerner alle ordene i b fra a
52       a.removeAll(b);
53       output += a.toString();
54       JOptionPane.showMessageDialog( null, output );
55    }
56 }

Kommentar 1: Vector<E>-klassen versus ArrayList<E>

Klassen Vector<E> implementerer en array av objekter. Arrayen utvider seg selv etter behov. Vector<E>-klassen implementerer interface List<E>. Den har derfor samme funksjonalitet som en ArrayList<E>. Det er imidlertid en viktig forskjell: Alle metodene i Vector<E>-klassen er såkalt synkroniserte. Det innebærer at et Vector-objekt uten risiko kan være en fellesressurs for flere forskjellige programtråder. Men dersom Vector-objektet bare brukes av én programtråd — noe som er det langt vanligste — betyr dette at programmet vil gjøre mye unødvendig arbeid ved å synkronisere. Metodene i ArrayList<E>-klassen er i motsetning til dette ikke synkroniserte. Det blir derfor anbefalt alltid å bruke ArrayList<E> istedenfor Vector<E> i alle tilfeller der synkronisering ikke behøves. (Det vil blant annet si alle tilfeller der du selv ikke programmerer egne programtråder.)

Kommentar 2: Gjennomløping ved bruk av utvidet for-løkke

I notatet om arrayer er det forklart hvordan arrayer kan gjennomløpes ved bruk av såkalt utvidet for-løkke, forutsatt at vi bruker javaversjon 1.5 eller nyere. Tilsvarende type løkke er definert for alle typer collection. Det er for slike at den kanskje er mest aktuell å bruke. Generelt kan den for et Collection-objekt liste skrives slik:

  for ( Object o : liste )
    ...

Dersom vi kjenner datatypen til objektene i samlingen, kan vi selvsagt bruke den som datatype i løkka. Dersom vi for eksempel har en Collection<String> navneliste, kan vi skrive tilsvarende løkke slik:

  for ( String navn : navneliste )
    ...

Som for arrayer, har vi imidlertid den begrensning at denne typen løkke bare kan brukes dersom hele samlingen skal gjennomløpes.

Kommentar 3: Bruk av indekser i sammenkjedet liste

Som tidligere nevnt, er elementene i en liste tilordnet en indeksposisjon. Dette gjelder enten lista er implementert i form av en array, eller som en sammenkjedet liste. Derfor spesifiserer interface List<E> en metode

  E get(int index);

for aksess av element på grunnlag av indeksposisjon. Men for en sammenkjedet liste er denne metoden svært ineffektiv! Den vil ved hjelp av en iterator foreta et søk fra starten av lista og telle seg utover til den angitte indeksposisjon.

På grunn av dette bør du derfor heller aldri skrive kode på følgende form for å gjennomløpe en sammenkjedet liste:

  for ( int i = 0; i < liste.size(); i++ )
    <gjør et eller annet med> liste.get(i);

Denne koden er svært ineffektiv! Hvert kall på get vil nemlig starte et nytt søk fra starten av den sammenkjedete lista og søke seg utover til den angitte indeksposisjon. Eneste optimiseringen er at dersom indeksposisjonen er etter midten av lista, så vil søket bli foretatt bakfra istedenfor forfra.

Alt i alt bør du for sammenkjedete lister ikke bruke metoder som bruker indekser for angivelse av posisjon i lista. Dersom du har behov for å gå inn i en liste på grunnlag av indeksposisjon, så bruk heller en array eller en ArrayList, ikke en sammenkjedet liste.

Ordning av objekter (for rekkefølge)

For String-objekter er vi kjent med metoden compareTo for sammenlikning med hensyn på leksikografisk (alfabetisk) rekkefølge. Den virker på den måten at for String-objekter s1 og s2 så gir s1.compareTo(s2) et negativt heltall når s1 er foran s2, 0 når s1 og s2 er like, et positivt heltall når s1 er etter s2.

Metoden

  int compareTo(T o)

er spesifisert, som den eneste metoden, i interface Comparable<T>. String-klassen implementerer interface Comparable<String> og definerer derfor compareTo med String-parameter. Metoden virker imidlertid ikke riktig når det gjelder rekkefølgen av ord som begynner med liten eller stor forbokstav. Den virker heller ikke riktig for de norske bokstavene æ, ø, å og deres store varianter. Vi skal seinere se på hvordan dette kan håndteres.

Når en klasse implementerer Comparable, og dermed definerer compareTo for vedkommende type objekter, medfører det at alle objekter av denne klassen vil få en total ordning, det vil si kan ordnes i en bestemt rekkefølge. Denne kalles klassens naturlige ordning. Klassens compareTo- metode kalles dens naturlige sammenlikningsmetode. Det blir for øvrig sterkt anbefalt at en klasse som implementerer Comparable også implementerer metoden equals på en slik måte at

  (x.compareTo(y) == 0) == (x.equals(y)).

En annen klasse som implementerer Comparable, er Date-klassen for representasjon av tidspunkter. Den naturlige ordning for denne (bestemt av compareTo) er det samme som kronologisk rekkefølge. (En kort beskrivelse av Date-klassen og hvordan den kan brukes finner du i notatet Dato og tid.)

Sortering

Dersom objektene i en liste er av en klassetype som implementerer Comparable, kan lista sorteres. Klassen Collections (som er noe annet enn interface Collection!) inneholder en del static-metoder som opererer på samlinger, blant annet på lister. I denne finnes også en sorteringsmetode.

Nesten alle metodene i Collections har som første parameter den samlingen de skal operere på. De aller fleste av metodene opererer på listeobjekter, det vil si samlinger som implementerer interface List. Metodene min og max opererer på vilkårlige Collection-objekter.

Sorteringsmetoden til Collections-klassen heter sort og finnes i to versjoner. Den enkleste har som eneste parameter den lista den skal sortere. Metoden sorterer lista i naturlig rekkefølge, det vil si rekkefølgen bestemt av elementenes compareTo-metode. Sorteringsmetoden har to viktige egenskaper:

• Den er rask. (Garantert n log n.)
• Den er stabil. Det betyr at elementer som er like med hensyn på sorteringsnøkkelen ikke vil bytte rekkefølge. Dette er en viktig egenskap dersom en liste sorteres flere ganger etter hverandre og det brukes forskjellige sorteringsnøkler hver gang. Dersom det for eksempel først sorteres med hensyn på dato og deretter med hensyn på navn, så vil ikke sorteringen på navn ødelegge datorekkefølgen for objekter med samme navn.

Comparators

Som nevnt ovenfor, finnes Collections-klassens sort-metode i to versjoner, der den enkleste sorterer lista (som er den eneste parameteren til metoden) i objektenes naturlige rekkefølge, det vil si rekkefølgen bestemt av deres compareTo-metode. Men hva om vi ønsker å sortere objektene i en annen rekkefølge? Eller hva om vi ønsker å sortere objekter som ikke implementerer interface Comparable, det vil si som det ikke er definert compareTo-metode for?

I begge de nevnte tilfellene kan den andre versjonen av Collections-klassens sort-metode brukes. Den har, i tillegg til den lista som skal sorteres, en parameter av type Comparator. Comparator<T> er et interface som spesifiserer metoden

  int compare(T o1, T o2);

Denne skal sammenlikne sine to argumenter for rekkefølge og returnere et negativt heltall, 0, eller et positivt heltall avhengig av om det første argumentet kommer foran, likt med eller etter det andre argumentet i den ordningen (rekkefølgen) vi ønsker å definere. (Dersom et av argumentene ikke har riktig type i forhold til Comparator-objektet, kaster metoden ut en ClassCastException.)

Dette betyr at vi først må definere en klasse som implementerer interface Comparator på en slik måte at den definerte compare-metoden kan brukes på objektene våre. Ved kall på sort-metoden må vi bruke et objekt av denne klassen som parameter i tillegg til den lista som skal sorteres. Som eksempel på denne framgangsmåten skal vi seinere definere en rekkefølge for Person-objekter.

Vi legger merke til at det å definere compare-metoden er nesten det samme som å definere compareTo-metoden. Forskjellen er at compare mottar som argumenter begge objektene som skal sammenliknes. Også for compare-metoden blir det anbefalt at den blir implementert slik at

  (compare(x, y) == 0) == (x.equals(y))

Det blir derfor anbefalt at når man implementerer compare-metoden for en type objekter, så redefinerer man også equals-metoden (som for øvrig arves fra Object) på en slik måte at den nevnte betingelsen er oppfylt.

Det blir videre anbefalt at klasser som implementerer interface Comparator også implementerer interface Serializable. Grunnen til dette er at de kan bli brukt ved sortering av datastrukturer som er serialiserte. Dersom serialisering da skal virke riktig på vedkommende datastruktur, er det nødvendig at eventuell komparator som brukes også er serialisert.

Sortering av strenger

Det mest interessante for oss er kanskje sortering av strenger. String-klassens compareTo-metode som bestemmer den naturlige rekkefølgen virker imidlertid på den måten at alle ord som begynner med stor forbokstav vil komme foran ordene som begynner med liten forbokstav. For eksempel vil "Java" komme foran "applet". Dessuten virker compareTo ikke riktig for æ, ø, å og de store variantene av disse. compareTo baserer seg på rekkefølgen til Unicode-kodene for de forskjellige bokstavene. I denne rekkefølgen kommer for eksempel både stor og liten å foran æ og ø.

Løsningen er å bruke et Collator-objekt. Klassen Collator implementerer interface Comparator<Object>, det vil si definerer en compare-metode. For å få et Collator-objekt med en compare-metode som foretar riktig String-sammenlikning på den lokaliteten vi befinner oss (det vil si i Norge for oss), skal vi skrive

  Collator kollator = Collator.getInstance();

Det viser seg imidlertid at heller ikke dette objektet definerer en rekkefølge som er helt i samsvar med det som ser ut til å være riktig etter norske forhold. Det har den feil at små bokstaver settes foran tilsvarende store bokstaver i den rekkefølgen som blir definert. I indekser til norske bøker og i rekkefølgen for oppslagsord i norske leksika vil en finne at stor bokstav er plassert foran tilsvarende liten bokstav, altså omvendt av det som blir definert av det nevnte kollatorobjektet.

Det returnerte Collator-objektet er av subklassetypen RuleBasedCollator. Ved å skrive

  ( (RuleBasedCollator) Collator.getInstance() ).getRules();

får vi returnert den tekststrengen som definerer rekkefølgen. For å få den rekkefølgen vi ønsker, kan vi definere vår egen rekkefølge i form av en String og bruke denne som konstruktørparameter når vi oppretter et RuleBasedCollator-objekt:

  String rekkefølge = "<A,a<B,b<..."; //må ta med alle aktuelle tegn
  Collator kollator = null;
  try
  {
    kollator = new RuleBasedCollator( rekkefølge );
  }
  catch ( ParseException pe )
  {
    ...  // gal syntaks i definisjon av rekkefølge
  }

Alle tegn som ikke tas med i rekkefølge-strengen blir oppfattet å komme på slutten av ordningen.

Det er mulig å bestemme i hvilken grad et Collator-objekt skal skille på likhet ved sammenlikninger, for eksempel om det skal gjøres forskjell på stor og liten bokstav. Dette setter vi ved instruksjonen

  kollator.setStrength( grad );

der grad kan ha verdiene

  Collator.PRIMARY
  Collator.SECONDARY
  Collator.TERTIARY
  Collator.IDENTICAL

Forskjellene er som følger:

PRIMARY:

ignorerer aksenter og forskjell mellom store og små bokstaver

SECONDARY:

ignorerer forskjeller mellom store og små bokstaver, men ikke aksenter

TERTIARY:

default-verdien: ignorerer ikke noe

IDENTICAL:

ignorerer ikke noe, men er lokalitetsavhengig

Dersom vi ønsker å sortere List-objektet liste med en rekkefølge vi selv har definert, må vi altså først definere rekkefølge og opprette et Collator-objekt kollator som forklart ovenfor. Deretter kan vi skrive

  Collections.sort( liste, kollator );

Som et eksempel på dette skal vi ta for oss en liste av personer. Vi ønsker lista sortert med hensyn på personenes etter- og fornavn.

Eksempel: Definere rekkefølge for Person-objekter

Som eksempel på å bruke comparatorer til å definere rekkefølge for objekter og få sortert objektene med hensyn på den definerte rekkefølgen, skal vi ta for oss følgende problemstilling: Vi skal definere Person-objekter som blant annet skal inneholde fornavn og etternavn for personene. Vi ønsker å bruke Collections-klassens sort-metode for å få sortert en liste av Person-objekter med hensyn på etternavn og fornavn. Sorteringen skal virke riktig for store og små bokstaver, og for de norske bokstavene æ, ø, å (og deres store varianter), slik at vi kan få skrevet ut en personliste tilsvarende som denne:

Abel, Amalie
Abel, Niels Henrik
Abel, Ågot
Bråten, Øyvind
Bråten, Åse
Østerud, Per
Østerud, Øystein
Østerud, Åsta
Ærdal, Anne
Årset, Liv
Årset, Åge
Årset, Åsmumd

For enkelhets skyld skal vi i Person-objektene bare legge inn fornavn og etternavn. Objektene kan selvsagt i tillegg inneholde hva som helst annet av data. Poenget her er bare å vise hvordan vi kan få definert rekkefølge og få sortert objektene med hensyn på den definerte rekkefølgen. Person-klassen definerer vi rett fram som følger:

 1 public class Person
 2 {
 3   private String fornavn, etternavn;
 4
 5   public Person(String f, String n)
 6   {
 7     fornavn = f;
 8     etternavn = n;
 9   }
10
11   public String getEtternavn()
12   {
13     return etternavn;
14   }
15
16   public String getFornavn()
17   {
18     return fornavn;
19   }
20
21   public String toString()
22   {
23     return etternavn + ", " + fornavn;
24   }
25
26   public boolean equals(Person p)
27   {
28     return ( p.getEtternavn().equals( etternavn ) &&
29         p.getFornavn().equals( fornavn ) );
30   }
31 }

Neste skritt er å definere et Comparator<Person>-objekt som definerer rekkefølge for Person-objektene. Rekkefølgen skal være bestemt av rekkefølgen for etternavn og fornavn. Siden denne rekkefølgen også skal virke riktig for store og små bokstaver, samt for æ, ø og å, må vi for String-sammenlikning bruke et Collator-objekt som gir riktig rekkefølge for disse. Dette objektet oppretter vi inni Comparator-klassen vår, slik at vi kan bruke dets compare-metode for å avgjøre String-rekkefølge. Comparator-klassen vår kan dermed defineres på følgende måte:

 1 import java.util.*;
 2 import java.text.*;
 3 import javax.swing.JOptionPane;
 4 import java.io.Serializable;
 5
 6 //Gir rekkefølge for Person-objekter, alfabetisk 
 7 //på etternavn og fornavn.
 8 class Personsammenlikner implements Comparator<Person>, Serializable
 9 {
10   private String rekkefølge = "<\0<0<1<2<3<4<5<6<7<8<9" +
11           "<A,a<B,b<C,c<D,d<E,e<F,f<G,g<H,h<I,i<J,j" +
12           "<K,k<L,l<M,m<N,n<O,o<P,p<Q,q<R,r<S,s<T,t" +
13           "<U,u<V,v<W,w<X,x<Y,y<Z,z<Æ,æ<Ø,ø<Å=AA,å=aa;AA,aa";
14
15   private RuleBasedCollator kollator;
16
17   public Personsammenlikner()
18   {
19     try
20     {
21       kollator = new RuleBasedCollator(rekkefølge);
22     }
23     catch ( ParseException pe )
24     {
25       JOptionPane.showMessageDialog( null,
26               "Feil i rekkefølgestring for kollator!" );
27       System.exit( 0 );
28     }
29
30   }
31
32   public int compare(Person p1, Person p2)
33   {
34     String n1 = p1.getEtternavn();
35     String n2 = p2.getEtternavn();
36     String f1 = p1.getFornavn();
37     String f2 = p2.getFornavn();
38     int d = kollator.compare(n1, n2);
39     if (d != 0)
40       return d;
41     else
42       return kollator.compare(f1, f2);
43   }
44 }

De to klassene ovenfor er definert i filene Person.java og Personsammenlikner.java.

Java-fila Personliste.java definerer personliste og sorteringsmetode for denne, slik det er gjengitt nedenfor:

 1 import java.util.*;
 2 import java.io.*;
 3 import javax.swing.JOptionPane;
 4
 5 public class Personliste
 6 {
 7   private List<Person> liste = new LinkedList<>();
 8
 9   //Setter inn nytt Person-objekt bakerst i lista
10   public void settInn(Person p)
11   {
12     liste.add( p );
13   }
14
15   //Sorterer Person-objektene alfabetisk på etternavn og fornavn
16   public void sorter()
17   {
18     Collections.sort(liste, new Personsammenlikner());
19   }
20
21   //Returnerer liste over alle personnavn,
22   //sortert på etternavn og fornavn.
23   public String toString()
24   {
25     sorter();
26     String personer = "";
27     Iterator<Person> iterator = liste.iterator();
28     while (iterator.hasNext())
29     {
30       personer += iterator.next().toString() + "\n";
31     }
32     return personer;
33   }
34
35   public void skrivFil(String filnavn)
36   {
37     Collections.shuffle(liste); //stokker i vilkårlig rekkefølge
38
39     try (PrintWriter utfil = new PrintWriter(filnavn))
40     {
41       Iterator<Person> iterator = liste.iterator();
42       String navn = null;
43       while (iterator.hasNext())
44       {
45         navn = iterator.next().toString();
46         utfil.println(navn);
47       }
48     }
49     catch (IOException ioe)
50     {
51       JOptionPane.showMessageDialog(null, "Filproblem",
52           "Problem med å skrive fil " + filnavn,
53           JOptionPane.WARNING_MESSAGE);
54     }
55   }
56 }

Listeklassens toString-metode gjør kall på sorteringsmetoden før lista blir gjennomløpt, slik at navnene blir returnert i sortert rekkefølge. Metoden skrivFil, som lagrer navnelista på fil før programavslutning, stokker rekkefølgen før lagring, slik at ved ny programstart blir det lest inn en usortert navneliste. Lagringen skjer i form av en tekstfil med samme struktur som er vist ovenfor, altså på hver linje et etternavn og et fornavn, med komma bak etternavnet.

Fila Persontester.java definerer et enkelt vindu som kan brukes til å teste ut den definerte personlista. Ved oppstart blir det lest inn en liste med navn (i tilfelle en slik eksisterer og blir funnet av programmet). Nå er det imidlertid slik at de særnorske bokstavene æ, ø, å og deres store varianter har forskjellige koder avhengig av hvilket tegnsett som blir brukt. I Vest-Europa og USA er det for generelle brukerprogrammer vanlig å bruke tegnsettet ISO-8859-1, også kalt Western, eller Latin 1. Dette brukes av bl.a. TextPad. Det er også dette som er brukt i tekst og eksempler i denne notatserien. Det er et tegnsett som koder i én byte de 256 første unicodetegnene.

Et annet tegnsett som koder Unicode, er UTF-8. Det bruker et varierende antall byte på de forskjellige tegnene. Det har den fordelen at det er bakoverkompatibelt med ASCII-tegnsettet. Det brukes bl.a. som default-tegnsett av NetBeans. Men det er mulig å stille inn NetBeans til å bruke for eksempel ISO-8859-1. Det fører til minst trøbbel med bruk av filer som inneholder æ, ø og å. Lista med navn som skal leses inn av dette programmet er laget i begge de nevnte tegnsettene. Navnelistene finnes i de to filene navneliste.txt (som bruker ISO-8859-1) og navneliste_UTF-8.txt. For at programmet skal virke riktig, må man velge den fila som samsvarer med det tegnsettet som blir brukt ved kjøring av programmet. Filnavnet er i programmet hardkodet som et datafelt i vindusklassen Persontester. Ved oppstart blir følgende metode blir kalt opp for å lese navnefila:

 48   public void lesFil()
 49   {
 50     try (BufferedReader innfil = new BufferedReader(
 51           new FileReader(filnavn)))
 52     {
 53       String navn = null;
 54       do
 55       {
 56         navn = innfil.readLine();
 57         if (navn != null)
 58         {
 59           try (Scanner leser = new Scanner(navn))
 60           {
 61             leser.useDelimiter("[,\\s]+");
 62             String etternavn = null;
 63             if (leser.hasNext())
 64               etternavn = leser.next();
 65             String fornavn = null;
 66             if (leser.hasNext())
 67               fornavn = leser.next();
 68             if (etternavn != null && fornavn != null)
 69               liste.settInn(new Person(fornavn, etternavn));
 70           }
 71         }
 72       } while (navn != null);
 73     }
 74     catch (FileNotFoundException fnf)
 75     {
 76       JOptionPane.showMessageDialog(this, "Manglende fil",
 77           "Finner ikke fil " + filnavn,
 78           JOptionPane.WARNING_MESSAGE);
 79     }
 80     catch (IOException ioe)
 81     {
 82       JOptionPane.showMessageDialog(this,"Filproblem",
 83           "Problem med å lese fra fil " + filnavn,
 84           JOptionPane.WARNING_MESSAGE);
 85     }
 86   }

Driver for programmet er definert i klassen Personapplikasjon.java.

Følgende bilde viser programvinduet etter oppstart og etter at innlest navneliste er skrevet ut i sortert rekkefølge ved at det er klikket på knappen Vis liste.

Stokking

Klassen Collections inneholder som nevnt en del static-metoder som opererer på samlinger, de fleste av dem på lister. Metoden shuffle gjør det motsatte av det sort-metoden gjør. Objektene i den lista som brukes som aktuell parameter blir stokket om til en tilfeldig rekkefølge, tilsvarende det som skjer når vi stokker kortene i en kortstokk. Metoden kan være aktuell å bruke når man skal skrive programmer der noe skal skje på slump. Metoden ble brukt i programmet ovenfor for at navnene skulle komme i en tilfeldig rekkefølge i den fila som ble skrevet ut ved programslutt. Hensikten var å få konstatert at sorteringsmetoden virket som den skulle.

Rutinemessig datamanipulasjon

Collections-klassen inneholder tre metoder som utfører operasjoner som er av en enkel natur og som det er lett å programmere selv. Det gjelder:

• reverse: Reverserer elementenes rekkefølge i en liste.
• fill: Overskriver alle elementene i en liste med den spesifiserte verdien. Kan være nyttig ved (re)initialisering.
• copy: Kopierer elementene fra en liste (kilde) over i en annen liste (mål) ved å overskrive innholdet i denne, som må være minst like stor som kilde-lista.

Finne ekstremverdier

To andre metoder som er lette å programmere selv, er metodene min og max for å returnere minste eller største verdi blant en samling av elementer. De er tatt med ut fra bekvemmelighetshensyn overfor programmereren. Metodene min og max er blant de få metodene i Collections-klassen som kan brukes med vilkårlige Collection-objekter som parametre. De fleste andre metodene i Collections-klassen opererer på lister. Både min og max finnes i to varianter: Den ene varianten har bare et Collection-objekt som parameter. Den andre varianten har i tillegg en parameter av type Comparator. Det vil ved bruk av denne være compare-metoden i dette Comparator-objektet som blir brukt for å finne ekstremverdi. En aktuell Comparator å bruke vil være en Collator.

Søking

Sekvensiell søking

For å undersøke om et objekt finnes i en liste, kan vi bruke List-metoden
contains(objekt) (som returnerer true eller false). List-metoden
indexOf(objekt) returnerer listeindeks for (første forekomst av) objektet. Begge metodene baserer seg på equals-metoden for sammenlikning av objekter. Dersom vi også ønsker å hente ut fra lista det objektet vi søker etter, kan vi etter å ha funnet listeindeksen bruke listemetoden get(listeindeks). Objektet blir da ikke fjernet fra lista, vi bare henter det ut for inspeksjon eller endring. Dersom vi ønsker å fjerne objektet, kan vi bruke listemetoden remove(listeindeks), som returnerer objektet i tillegg til å fjerne det fra lista, eller listemetoden remove(objekt) som fjerner første forekomst av vedkommende objekt (i tilfelle det finnes i lista). Denne metoden returnerer true eller false avhengig av om den fant objektet eller ikke. Metoden set(indeks, element) erstatter elementet i den spesifiserte indeksposisjon med det elementet som er aktuell parameter til metoden. Det elementet som tidligere var i denne posisjon blir returnert fra metoden.

Binær søking

Fra tidligere kjenner vi algoritmen for binær søking. Den forutsetter at lista det søkes i er sortert på forhånd og at den er indeksert. Algoritmen går ut på at en først ser på elementet midt i lista. Ved sammenlikning av nøkkelverdier blir det avgjort om søkingen skal fortsette i venstre eller høyre halvdel. Også i dellista bestående av denne halvdelen ser en først midt i lista, og fortsetter så videre etter samme framgangsmåte. Dellista det søkes i blir dermed halvert for hvert skritt. Selv om lista i utgangspunktet er lang, skal det ikke mange halveringer til før den skrumper inn til ett element.

Siden binær søking forutsetter aksess på elementer på grunnlag av indeksering, er den bare implementert for listetypen ArrayList. (Den forutsetter at listeklassen implementerer interface RandomAccess.) Metoden kan kalles opp også for en LinkedList, men det vil da bli foretatt sekvensiell søking.

Metode for binærsøking finnes ikke i listeklassene, men i klassen Collections. I likhet med andre metoder som har å gjøre med sammenlikning for rekkefølge, finnes det også to versjoner av Collections-klassens metode binarySearch. Begge har som parameter den lista det skal søkes i og den verdien det skal søkes etter. En av versjonene av metoden har som ekstra parameter et Comparator-objekt som definerer rekkefølgen for objektene. Den versjonen av metoden som er uten Comparator-parameter, forutsetter at lista på forhånd er sortert i stigende rekkefølge på grunnlag av objektenes naturlige ordning (det vil si som bestemt av metoden compareTo). Den andre versjonen av metoden, som har Comparator-objekt som tilleggsparameter, forutsetter at lista er sortert i stigende rekkefølge etter ordningen definert av dette Comparator-objektet (det vil si som bestemt av objektets compare-metode). For å sikre at kravet om sortering er oppfylt, kan en før kallet på binarySearch gjøre kall på den av sort-metodene som er aktuell å bruke.

Returverdien er den samme for begge versjonene av binarySearch-metoden. Dersom det søkte elementet finnes, blir dets indeks returnert. Dersom det ikke finnes, er returverdien lik

  (-innsettingspunkt - 1)

der innsettingspunkt er definert som det sted der elementet skulle ha blitt satt inn i lista uten å ødelegge sorteringen, det vil si indeksen til det første elementet som er større enn det søkte elementet, eller liste.size() dersom alle elementene i lista er mindre enn det søkte elementet. Den nevnte returverdien ble valgt for å sikre at returverdien bare vil være >= 0 når det søkte elementet blir funnet. Dessuten vil den være til hjelp dersom vi ønsker å sette inn på sortert plass i lista det søkte elementet i tilfelle det ikke finnes. I så fall kan vi skrive slik:

  int pos = Collections.binarySearch(liste, element);
              //eventuelt også Comparator-parameter
  if (pos < 0)
    liste.add(-pos - 1, element);

Mengder

Begrepet mengde kjenner vi fra matematikk som en samling av elementer der hvert element bare kan forekomme én gang. I java blir dette definert av interface Set<E> som er et subinterface til Collection<E>. Set inneholder ingen nye metoder i tillegg til dem som blir arvet fra Collection. Men det pålegger restriksjoner om at duplikater er forbudt. Dette får konsekvenser for add-metoden. Denne legger det nye objektet inn i samlingen bare dersom det ikke finnes fra før. Den returnerer true eller false som signal på om objektet ble lagt inn eller ikke. To Set-objekter skal regnes som like dersom de inneholder nøyaktig de samme elementene. Metoden equals må derfor implementeres slik at dette er oppfylt. De viktigste operasjonene på Set-objekter er som følger:

Grunnleggende operasjoner:

size():

returnerer antall elementer.

isEmpty():

sjekker for tomhet.

add(E elem):

setter inn spesifisert element i tilfelle det ikke finnes fra før. Returverdi true eller false indikerer om det ble satt inn.

remove(Object elem):

fjerner spesifisert element i tilfelle det finnes. Returverdi true eller false indikerer om det fantes.

iterator():

returnerer et Iterator<E>-objekt som kan brukses til gjennomløping av mengden.

Mengdeoperasjoner

Disse operasjonene utfører standard algebraiske operasjoner svarende til dem som er definert for matematiske mengder. Følgende oversikt viser sammenhengen.

Anta at a og b er Set-objekter.

De fire første metodene returnerer true eller false, den siste er void. Metodene addAll, removeAll og retainAll vil erstatte a med den nevnte union, differensmengde eller snittmengde. Returverdien indikerer om a ble endret som følge av operasjonen.

Implementasjoner

Javas klassebibliotek inneholder tre forskjellige implementasjoner av interface Set<E>. Klassen HashSet<E> lagrer elementene i en såkalt hashtabell og gir den mest effektive implementasjonen, men den gir ingen garantier for rekkefølgen som elementene er lagret i. (Det vil si at ved gjennomløping av mengden kan en ikke vite noe om rekkefølgen for besøk av de enkelte elementene. Rekkefølgen kan dessuten endre seg over tid.) Dersom effektivitet ved gjennomløping er av stor betydning, er det grunn til å merke seg at effektiviteten er avhengig både av HashSet-objektets kapasitet og oppfyllingsgrad. I Java blir hashtabeller implementert som arrayer av sammenkjedete lister. Hver liste blir på engelsk kalt en bucket, altså en "bøtte". For å finne plassen til et element i hashtabellen, blir det på grunnlag av objektet beregnet en såkalt hashkode som så blir redusert modulo antall plasser i arrayen. Denne verdien bestemmer indeksen for hvilken "bøtte" objektet skal puttes i. Dersom vi ikke velger noen konkret verdi for startkapasitet for arrayen, vil den få en default-verdi på 16. (Antallet settes alltid lik en potens av 2.) Dersom du vet omtrent hvor mange elementer som vil bli satt inn i hashtabellen, kan du sette startkapasitet for antall "bøtter". Det anbefales å sette den mellom 75 % og 150 % av det forventede antall elementer. Tidligere ble det anbefalt å velge startkapasiteten lik et primtall. Denne anbefalingen blir ikke lenger gitt. Uansett hvilken verdi vi selv velger, vil den automatisk bli avrundet oppover til nærmeste potens av 2. For å sette en startkapasitet på k (heltallsverdi), kan vi skrive

  Set<Type> s = new HashSet<>( k );

Ved opprettelse av et HashSet vil det i tillegg til kapasiteten bli bestemt en verdi for det vi kan kalle lastefaktoren (engelsk: load factor). Default-verdien for denne er 0.75 og det er sjelden grunn til å endre den. Dersom forholdet mellom antall elementer i mengden og dens kapasitet overstiger lastefaktoren, vil mengden automatisk bli såkalt rehashet, det vil si at kapasiteten vil bli omtrent doblet.

Klassen TreeSet<E> implementerer Set-interface'et i form av et såkalt rød-svart-tre. Implementasjonen har den tilleggsegenskapen at elementene alltid er sortert. Men til gjengjeld har den vesentlig dårligere effektivitet. Dette har imidlertid liten betydning når antall elementer er forholdsvis beskjedent. Vi skal se nærmere på hvordan denne implementasjonen kan brukes etter å ha sett på et par eksempler på bruk av HashSet-klassen.

Den tredje klassen som implenterer Set-interface'et, LinkedHashSet<E>, lagrer elementene i en hashtabell, på samme måte som er tilfelle med HashSet. Men i tillegg inneholder den en toveis sammenkjedet liste som går gjennom elementene i den rekkefølge som de ble satt inn. Det er denne som brukes ved gjennomløping. Ved gjennomløping av mengden vil vi derfor få dem i samme rekkefølge som de ble satt inn. Denne rekkefølgen vil heller ikke endre seg dersom vi gjør forsøk på å sette inn på nytt et element som allerede finnes i mengden. Den opprinnelige rekkefølgen vil bli beholdt. Effektiviteten til implementasjonen er bare litt dårligere enn tilfelle er for HashSet, unntatt når det gjelder gjennomløping, der den faktisk har bedre effektivitet, siden effektiviteten bare er avhengig av hvor mange elementer som er satt inn. Den er ikke avhengig av oppfyllingsgraden, slik det er tilfelle med HashSet. Denne implementasjonen kan også brukes til å produsere en kopi av en gitt mengde, der kopien gir samme rekkefølge ved gjennomløping som ville være tilfelle ved originalen, uavhengig av hvilken implementasjon originalen har:

  void gjørEtEllerAnnet(Set m)
  {
    Set<Type> kopi = new LinkedHashSet<>(m);
    ...
  }

Dette er spesielt nyttig dersom en modul mottar en mengde som input, kopierer den, og seinere returnerer resultater med en rekkefølge som skal være bestemt av den rekkefølgen som input-mengden har.

Interface versus implementasjon

Enten det dreier seg om mengder eller andre strukturer, er det en god regel å tenke i retning av interface, som beskriver den struktur det er snakk om, heller enn å tenke på en konkret implementasjon. Valg av implementasjon har stort sett bare konsekvenser for effektiviteten. Den foretrukne måten å programmere på er å velge en implementasjon når en samling (eller en annen type objekt) blir opprettet og tilordne denne til en variabel av den tilsvarende interface-type. På denne måten blir ikke programmet avhengig av noen eventuelle tilleggsmetoder i en gitt implementasjon. Programmereren, eller eventuelt den som skal vedlikeholde programmet, står fritt i enkelt å bytte ut implementasjon, dersom dette ut fra effektivitetshensyn bør gjøres. Eneste endringen som behøves vil være å bytte konstruktør.

Eksempel

Skriv

  Set<Type> s = new HashSet<>();

istedenfor

  HashSet<Type> s = new HashSet<>();

Programeksempler: Finne og telle opp antall forskjellige ord i en tekstfil

Programmet SetTest som er gjengitt nedenfor leser tekstfila alice30.txt ord for ord ved hjelp av en Scanner. (Se notatet Splitte opp tekst i enkeltkomponenter angående bruk av Scanner.) Enkeltordene blir lagt inn i en mengde av type HashSet<String>. Siden ordene blir lagt inn i en mengde, vil det for hvert nytt ord bli testet om det finnes fra før av. Mengden vil bare komme til å inneholde forskjellige ord. Det blir dessuten målt hvor lang tid som brukes totalt på å legge inn ordene i mengden, inkludert sjekke om de finnes fra før.

Når alle ordene er lest og lagt inn i mengden, blir den gjennomløpt ved hjelp av en iterator og ordene blir skrevet ut i et tekstområde, 10 ord per linje. Dessuten blir totalt antall ord skrevet ut og total tid som ble brukt på å legge dem inn.

 1 import javax.swing.*;
 2 import java.awt.*;
 3 import java.util.*;
 4 import java.io.*;
 5
 6 public class SetTest extends JFrame
 7 {
 8   private JTextArea output;
 9
10   public SetTest()
11   {
12     super( "Eksempel på bruk av Set" );
13     output = new JTextArea( 20, 50 );
14     output.setEditable( false );
15     Container c = getContentPane();
16     JLabel overskrift = new JLabel(
17         "Antall forskjellige ord i fila alice30.txt" );
18     c.add( overskrift, "North" );
19     c.add( new JScrollPane( output ), "Center" );
20     setSize( 800, 500 );
21     setVisible( true );
22   }
23
24   public void tellOppOrd()
25   {
26     Set<String> ord = new HashSet<>(59999);//bruk HashSet eller TreeSet
27     long totaltid = 0;
28
29     try (BufferedReader in = new BufferedReader(
30             new FileReader("src/alice30.txt"));
31          Scanner ordleser = new Scanner(in))
32     {
33       while (ordleser.hasNext())
34       {
35         String nesteord = ordleser.next();
36         long kalltid = System.currentTimeMillis();
37         ord.add( nesteord );
38         kalltid = System.currentTimeMillis() - kalltid;
39         totaltid += kalltid;
40       }
41     }
42     catch (IOException e)
43     {
44       System.out.println("Feil " + e);
45     }
46
47     Iterator<String> iter = ord.iterator();
48     int ant = 0;
49     while (iter.hasNext())
50     {
51       output.append( iter.next() + "\t" );
52       if ( ++ant % 10 == 0 )
53         output.append( "\n" );
54     }
55     output.append( "\n" + ord.size()
56          + " forskjellige ord. " + totaltid + " millisekunder." );
57   }
58
59   public static void main(String[] args)
60   {
61     SetTest vindu = new SetTest();
62     vindu.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
63     vindu.tellOppOrd();
64   }
65 }

Følgende bilde viser et utsnitt av det tekstområdet som blir vist i programvinduet ved kjøring av programmet. (Du må sørge for å legge inn fila som programmet skal lese på riktig sted i forhold til den filadressen som programmet bruker for å åpne fila.)

Programmet SetTest2 er en modifikasjon av det foregående. I dette blir det brukt to mengder. Den ene skal inneholde alle ord som det finnes bare én forekomst av i fila, mens den andre skal inneholde alle ord som det er multiple forekomster av. En får lagt inn riktige data i mengdene på den måten at hvert nytt leste ord forsøkes lagt inn i den første mengden. Dersom dette ikke lykkes, betyr det at det finnes fra før. add-metoden vil da returnere false og ordet blir lagt inn i den andre mengden, selvsagt forutsatt at det ikke allerede finnes også i denne.

Når alt er lest, vil den første mengden inneholde alle forskjellige ord fra fila og den andre mengden vil inneholde alle ord som forekommer mer enn én gang. Disse blir så fjernet fra den første mengden ved bruk av removeAll-metoden til den første mengden, med den andre mengden som aktuell parameter.

Vi kan for øvrig legge merke til at det totalt er 3747 ord med bare én forekomst, 2162 ord med mer enn én forekomst. Summen av disse blir 5909 som er antall forskjellige ord som ble registrert av det første programmet.

Metoden tellOppOrd som foretar innlesing fra fil og innsetting av ordene i de to mengdene er gjengitt nedenfor.

31   public void tellOppOrd()
32   {
33     Set<String> singelforekomst = new HashSet<>(59999);
34                                    // bruk HashSet eller TreeSet
35     Set<String> duplikater = new HashSet<>();
36
37     try (BufferedReader in = new BufferedReader(
38             new FileReader("src/alice30.txt"));
39          Scanner ordleser = new Scanner(in))
40     {
41       while (ordleser.hasNext())
42       {
43         String ord = ordleser.next();
44         if ( !singelforekomst.add(ord) )
45           duplikater.add(ord);
46       }
47     }
48     catch (IOException e)
49     {
50       System.out.println("Feil " + e);
51     }
52
53     //Fjerner fra mengden singelforekomst de ord som det 
54     //er registrert flere forekomster av:
55     singelforekomst.removeAll(duplikater);
56     Iterator<String> singelIter = singelforekomst.iterator();
57     int ant = 0;
58     while (singelIter.hasNext())
59     {
60       singeloutput.append(singelIter.next() + "\t");
61       if ( ++ant % 10 == 0 )
62         singeloutput.append("\n");
63     }
64     singeloutput.append("\n" + singelforekomst.size() +
65         " forskjellige ord. " );
66
67     ant = 0;
68     Iterator<String> duploIterator = duplikater.iterator();
69     while (duploIterator.hasNext())
70     {
71       duplikatoutput.append(duploIterator.next() + "\t");
72       if ( ++ant % 10 == 0 )
73         duplikatoutput.append("\n");
74     }
75     duplikatoutput.append("\n" + duplikater.size() +
76         " forskjellige ord. ");
77   }

Følgende bilde viser utsnitt av de to tekstområdene som blir vist i programvinduet ved kjøring av programmet.

Sorterte mengder

Klassen TreeSet implementerer, slik som HashSet, mengdebegrepet. Men TreeSet har den forbedringen at mengden alltid er sortert. TreeSet implementerer interface SortedSet<E> som er subinterface til Set<E>. De generelle mengdeoperasjonene som blir arvet fra Set oppfører seg på sorterte mengder som på usorterte mengder med unntak av følgende:

• Iterator-objektet returnert av iterator() foretar gjennomløping av mengden i sortert rekkefølge (uavhengig av innsettingsrekkefølge og uten forutgående sortering).
• Arrayen returnert av toArray() inneholder mengdens elementer i sortert rekkefølge.

Når det gjelder toString-metoden, blir det av interface SortedSet ikke lagt noe krav på denne. Men TreeSet-klassens toString-metode returnerer elementene i sortert rekkefølge.

SortedSet spesifiserer tre forskjellige metoder på delintervall. Det er metodene subSet, headSet og tailSet.

subSet mottar som parametre objekter (ikke indekser!) for de to endepunktene. Disse må kunne sammenliknes for rekkefølge med objektene som er i mengden. subSet returnerer det vi kan tenke på som et halvåpent intervall, det vil si en mengde (av type SortedSet) som inkluderer objektet for nedre endepunkt, i tilfelle dette finnes i mengden, men ikke objektet for øvre endepunkt.

Objektsammenlikning

TreeSet forutsetter som default at elementene som blir satt inn i mengden er av en type som implementerer interface Comparable, det vil si som det er definert compareTo-metode for. Det er da denne som vil bli brukt til å avgjøre rekkefølge. Vi må derfor sørge for at klassene som definerer objektene våre implementerer interface Comparable slik at den definerte compareTo-metode gir den rekkefølge vi ønsker for objektene våre. Forsøk på å legge inn i mengden objekter som det ikke er definert compareTo-metode for, vil resultere i en ClassCastException.

Når det gjelder String-objekter, vet vi at compareTo-metoden ikke virker riktig for rekkefølgen av æ, ø, å og heller ikke riktig for rekkefølgen av ord som begynner med stor eller liten forbokstav. For å bøte på dette, kan vi, som forklart i forbindelse med sortering av lister, bruke et Comparator-objekt av type Collator som konstruktørparameter ved opprettelsen av TreeSet-objektet. Det vil da være compare-metoden til dette Comparator-objektet som vil bli brukt til å avgjøre rekkefølge i den sorterte mengden. Framgangsmåten blir dermed som følger:

Opprette Collator-objekt, enten ved instruksjonen

  Comparator komp = Collator.getInstance();

eller definere vår egen rekkefølge for komparatoren:

  String rekkefølge = "<\0<0<1< ...";
             //må her ta med alle bokstaver og tegn som
             //vi ønsker å definere rekkefølge for.

Oppretter komparator:

  Comparator komp = new RuleBasedCollator(rekkefølge);

Oppretter mengdeobjektet:

  SortedSet<String> ordbok = new TreeSet<>(komp);

På tilsvarende måte kan vi gå fram dersom vi ønsker å legge objekter som ikke implementerer interface Comparable inn i en sortert mengde. (Vi må da sørge for at compare-metoden til vedkommende Comparator-objekt er definert på en meningsfull måte for objektene våre.)

Eksempel

Anta at SortedSet<String>-objektet ordbok er opprettet som skissert ovenfor og at det er lagt inn tekststrenger i dette.

Antall ord mellom "først" og "sist", inkludert "først", men ekskludert "sist":

  int antall = ordbok.subSet("først", "sist").size();

Dersom de to argumentene i subSet har gal rekkefølge, blir det kastet ut en IllegalArgumentException.

Fjerne alle ord som begynner på "q" fra samme mengde ordbok:

  ordbok.subSet("q", "r").clear();

subSet-metoden erstatter ikke mengden den brukes på med vedkommende delmengde. Men dersom det blir gjort endringer på den delmengden som blir hentet ut, for eksempel ved å bruke clear(), så vil de samme endringene gjenspeile seg i den mengden som ligger under, det vil si som delmengden er hentet ut fra.

Hvordan hente ut et lukket intervall, det vil si et intervall som også inkluderer øvre grense?

Dersom øvre grense er String-objektet s, trenger vi da å vite hvilket String-objekt som følger etter s i den naturlige ordningen. Det er s + "\0", det vil si s tilføyd et nulltegn. Antall ord mellom "først" og "sist" i mengden ordbok, begge grenser inkludert, får vi derfor slik:

  int antall = ordbok.subSet("først", "sist" + "\0").size();

Tilsvarende for å få åpent intervall, det vil si intervall som ekskluderer begge endepunktene:

  int antall = ordbok.subSet("først" + "\0", "sist").size();

Splitting av en mengde

Metodene headSet og tailSet tar begge en parameter av den typen som mengden er definert til å inneholde. Metoden headSet returnerer delmengden fra starten og opp til, men ikke til og med det spesifiserte objektet. Metoden tailSet returnerer delmengden fra og med spesifisert objektet (dersom det finnes) og resten av det SortedSet-objekt som metoden kalles for. Ved bruk av disse to metodene kan vi derfor få en to-deling av en gitt mengde.

Eksempel

Vi antar at SortedSet<String>-objektet ordbok er opprettet og fylt med innhold som tidligere skissert. Vi skal splitte ordbok i delene: ord som begynner på A til M, og ord som begynner på N til Å:

  SortedSet<String> førstedel = ordbok.headSet("N");
  SortedSet<String> andredel = ordbok.tailSet("N");

Endepunktsoperasjoner

SortedSet-metodene first og last returnerer, som navnene indikerer, henholdsvis første og siste element i mengden. Disse operasjonene muliggjør dessuten å utføre en operasjon som ikke er tatt med i SortedSet:

• gå inn i det indre av en sortert mengde og derfra gjennomløpe den forover eller bakover

Gjennomløping forover fra startelementet er lett å få til (vi forutsetter som før at SortedSet<String>-objektet ordbok er opprettet og fylt med data):

  SortedSet<String> hale = ordbok.tailSet(startelement);
  Iterator<String> iter = hale.iterator();
  while (iter.hasNext())
  {
    String ord = iter.next();
    .
    .
  }

Gjennomløping i retning bakover fra startelementet er ikke så lett å få til. Men vi kan få tak i det foregående elementet ved å skrive følgende:

  String forløper = ordbok.headSet(startelement).last();

På denne måten får vi gått ett skritt bakover fra et gitt utgangspunkt. Operasjonen kan repeteres gjentatte ganger (med forløper som nytt startelement) for å få til en gjennomløping, men det vil være svært ineffektivt.

Programeksempel

Vi skal ta for oss et program som kan lese inn en tekstfil og lagre de forskjellige ordene i en sortert mengde. Brukeren kan velge hvilken fil som skal behandles og dette kan foretas gjentatte ganger. Når fil er lest inn og ordene lagret i programmets datastruktur, kan brukeren velge mellom to operasjoner:

• telle opp og skrive ut alle ord mellom valgte grenser, grenseordene inkludert, i tilfelle disse finnes
• telle opp og skrive ut alle ord som begynner med valgt forbokstav (uten å skille mellom stor og liten forbokstav)

Programmet bruker en kollator, slik at det også virker riktig for æ, ø og å. Programmet består av filene Ordopptelling.java, Bokstavinput.java og Inputdialog.java og Ordtester.java. Nedenfor gjengis de metodene som har med bruken av mengdene å gjøre.

  8 //Denne versjonen behandler sortering av ord med æ, ø og å riktig.
  9 public class Ordopptelling extends JFrame
 10 {
 11    private JButton velgFil, intervall, forbokstav;
 12    private JTextArea utskrift;
 13    private JTextField filvalg;
 14    private SortedSet<String> ordbok;
 15    private JDialog ordleser, bokstavleser;
 16    private Knappelytter lytter;
 17    private RuleBasedCollator kollator;
 18    private String rekkefølge;
 19    private SortedSet<String> æøå;
 20
 21    public Ordopptelling()
 22    {
         .
         .
 51      //Definerer sorteringsrekkefølge:
 52      rekkefølge = "<\0<0<1<2<3<4<5<6<7<8<9" +
 53                   "<A,a<B,b<C,c<D,d<E,e<F,f<G,g<H,h<I,i<J,j" +
 54                  "<K,k<L,l<M,m<N,n<O,o<P,p<Q,q<R,r<S,s<T,t" +
 55                  "<U,u<V,v<W,w<X,x<Y,y<Z,z<Æ,æ<Ø,ø<Å;AA,Aa,å;aa";
 56      try
 57      {
 58        kollator = new RuleBasedCollator( rekkefølge );
 59             //for riktig sortering av norske ord
 60      }
 61      catch ( ParseException pe ) {
 62        JOptionPane.showMessageDialog(
 63            null, "Feil i rekkefølgestring for kollator!" );
 64        System.exit( 0 );
 65      }
 66      lagÆøå();
         .
         .
 83    }
 84
 85    //Lagrer bokstavene æ, ø og å i en mengde til internt bruk.
 86    private void lagÆøå()
 87    {
 88      æøå = new TreeSet<>( kollator );
 89      æøå.add( "Æ" );
 90      æøå.add( "æ" );
 91      æøå.add( "Ø" );
 92      æøå.add( "ø" );
 93      æøå.add( "å" );
 94      æøå.add( "Å" );
 95    }
 96
 97    //Lar brukeren velge fil vha. et JFileChooser-dialogvindu.
 98    public File hentFil()
 99    {
         .
         .
113    }
114
115    //Leser valgt fil og lagrer de forskjellige ordene
116    //i en sortert mengde.
117    public SortedSet<String> lagOrdbok( File fil )
118    {
119      SortedSet<String> s = new TreeSet<>( kollator );
120      if ( fil != null )
121      {
122        try (Scanner leser = new Scanner( fil, "ISO-8859-1" ))
123        {
124          while ( leser.hasNext() )
125          {
126            String ord = leser.next();
127            s.add( ord );
128          }
129          return s;
130        }
131        catch ( IOException ioe )
132        {
133          JOptionPane.showMessageDialog( this,
134              "Får ikke lest " + fil );
135          return null;
136        }
137      }
138      else
139      {
140        JOptionPane.showMessageDialog( this, "Ingen fil valgt." );
141        return null;
142      }
143    }
144
145    //Skriver ut og teller ordene mellom valgte grenser,
146    //grenseord inkludert.
147    public void visOrd( String nedre, String øvre )
148    {
149       if ( ordbok != null )
150       {
151         SortedSet<String> forekomster = null;
152         try
153         {
154            forekomster = ordbok.subSet( nedre, øvre + "\0" );
155         }
156         catch ( IllegalArgumentException ie )
157         {
158           JOptionPane.showMessageDialog( this,
159             "Gal rekkefølge på nedre og øvre grense!" );
160           return;
161         }
162         int antall = forekomster.size();
163         Iterator<String> iterator = forekomster.iterator();
164         utskrift.setText( antall + " ord:\n" );
165         while ( iterator.hasNext() )
166           utskrift.append( iterator.next() + "\n" );
167       }
168       else
169         utskrift.setText( "Ingen fil lest inn." );
170    }
171
172    //Skriver ut og teller alle ord med valgt forbokstav.
173    public void visOrd( char forbokstav )
174    {
175       if ( ordbok != null )
176       {
177         char neste = nesteBokstav( forbokstav );
178         char[] nedre = { forbokstav };
179         String første = (new String( nedre )).toUpperCase();
180         String siste = null;
181         if ( neste != '@' )
182         {
183           char[] øvre = { neste };
184           siste = (new String( øvre )).toUpperCase();
185         }
186         else
187           siste = "ååå";   //kommer etter alle tenkelige ord
188         SortedSet<String> forekomster = null;
189         try
190         {
191            forekomster = ordbok.subSet( første, siste );
192         }
193         catch ( IllegalArgumentException ie )
194         {
195           JOptionPane.showMessageDialog( this,
196             "Klarer ikke behandle denne bokstaven!" );
197           return;
198         }
199         int antall = forekomster.size();
200         Iterator<String> iterator = forekomster.iterator();
201         utskrift.setText( antall + " ord:\n" );
202         while ( iterator.hasNext() )
203           utskrift.append( iterator.next() + "\n" );
204       }
205       else
206         utskrift.setText( "Ingen fil lest inn." );
207    }
208
209    //Hjelpemetode som returnerer etterfølgeren til 
210    //den valgte bokstaven, '@' etter å.
211    public char nesteBokstav( char bokstav )
212    {
213      char[] b = { bokstav };
214      String s = new String( b );
215      if ( !æøå.contains( s ) && bokstav < 'z' )
216        return (char) (bokstav + 1);
217      else
218      {
219        switch ( bokstav )
220        {
221          case 'z':
222          case 'Z': return 'Æ';
223          case 'Æ':
224          case 'æ': return 'Ø';
225          case 'Ø':
226          case 'ø': return 'Å';
227          default: return '@'; //signaliserer at bokstav var å eller Å
228        }
229      }
230    }
231
       .
       .
258 }

Avbildning (Map)

Interface Map<K,V> definerer det som svarer til det vi i matematikk kjenner som en avbildning:

en tilordning som til hver nøkkelverdi (argument) tilordner nøyaktig én verdi ("funksjonsverdi").

Duplikater av nøkkelverdier er ikke tillatt. Til hver nøkkelverdi kan det bare tilordnes én verdi. Men på den andre side kan én og samme verdi ("funksjonsverdi") ha blitt tilordnet som verdi av mange forskjellige nøkkelverdier. (Vi har altså en mange-til-én-relasjon.) Datatypene for nøkkelverdiene og de tilordnede verdiene kan angis som typeparametre K og V.

Alt i alt kan vi altså se på en avbildning (Map) som en samling av (nøkkel, verdi)-par. Men merk at en Map ikke er en Collection. Vi kan derimot på tre forskjellige måter hente ut en Collection fra en Map. Følgende Map-metoder returnerer en Collection:

Set<Map.Entry<K,V>> entrySet():

returnerer mengden av (nøkkel, verdi)-par inneholdt i avbildningen. (Dette svarer til grafen i tilfelle en funksjon.)

Collection<V> values():

returnerer samlingen av verdier inneholdt i avbildningen. (Svarer til verdimengden til en funksjon, men er ikke en mengde, siden den kan inneholde duplikater ved at forskjellige nøkkelverdier er blitt tilordnet samme verdi.)

Set<K> keySet():

returnerer mengden av nøkkelverdier inneholdt i avbildningen. (Svarer til definisjonsmengden til en funksjon.)

Metoden

  put(K nøkkel, V verdi)

tilføyer det spesifiserte (nøkkel, verdi)-paret til avbildningen. Dersom det i samlingen allerde finnes et (nøkkel, verdi)-par med samme nøkkelverdi, så vil den verdien som vedkommende nøkkelverdi er tilordnet bli oppdatert med den nye verdien, og den gamle verdien vil bli returnert. (Returverdi null dersom nøkkelverdien ikke finnes fra før av.)

Metoden

  get(Object nøkkel)

returner verdien som er tilordnet den spesifiserte nøkkel. Returverdien er av type V, lik null dersom nøkkelen ikke finnes.

Implementasjoner

Pakken java.util inneholder tre klasser som implementerer interface Map: HashMap<K,V>, TreeMap<K,V>, og LinkedHashMap<K,V>. Disse har funksjonalitet og effektivitet som svarer nøyaktig til de analoge klassene HashSet, TreeSet, og LinkedHashSet som ble beskrevet i avsnittet om mengder.

Kommentar: HashMap versus Hashtable

Klassen Hashtable<K,V> forholder seg til klassen HashMap på tilsvarende måte som klassen Vector forholder seg til klassen ArrayList, se kommentar foran om forholdet mellom disse. Klassene Hashtable og Vector var begge med i den opprinnelige java-versjonen. Da Collections-rammeverket ble introdusert i javaversjon 1.2, ble både Hashtable og Vector tilpasset dette rammeverket: Vector ved at den implementerer interface List; Hashtable ved at den implementerer interface Map. Fra javaversjon 1.5 er klassene i tillegg tilpasset bruken av generiske datatyper. Tilsvarende som for Vector, så er alle metodene i Hashtable synkroniserte, med alt det innebærer av ekstra utførelse av kode som er unødvendig i de fleste tilfeller. På grunn av dette anbefales det å bruke et HashMap-objekt istedenfor et Hashtable-objekt i alle tilfeller der objektet ikke skal være fellesressurs for flere programtråder.

Gjennomløping

Eneste måten å få gjennomløpt en avbildning på, er å hente ut en av de tre mulige samlingene som er nevnt foran og gjennomløpe denne ved hjelp av en iterator.

Eksempel

Gjennomløping av nøkkelverdier:

  Map<Nøkkeltype,Verditype> m = ...;
  Set<Nøkkeltype> nøkler = m.keySet();
  Iterator<Nøkkeltype> iter = nøkler.iterator();
  while (iter.hasNext())
  {
    Nøkkeltype nøkkel = iter.next();
    .
    .
  }

Gjennomløping av (nøkkel, verdi)-par:

Gjennomløping av (nøkkel, verdi)-parene til en avbildning er litt spesielt. Disse er av type Map.Entry<K,V> som er definert som et indre static interface i interface Map<K,V>. Klasser som implementerer interface Map vil ha Map.Entry som en static indre klasse. (At en indre klasse er static betyr bare at et objekt av den typen den definerer ikke har noen referanse til objektet av den ytre klassen som den tilhører, slik at det ikke er noen tilgang til datafeltene og metodene i denne.) Klassen Map.Entry har metoder getKey og getValue som returnerer henholdsvis nøkkel og verdi for (nøkkel, verdi)-paret. En gjennomløping av (nøkkel, verdi)-parene kan vi derfor skrive slik:

  Map<Nøkkeltype,Verditype> m = ...;
  Set<Map.Entry<Nøkkeltype,Verditype>> verdipar = m.entrySet();
  Iterator<Map.Entry<Nøkkeltype,Verditype>> iter = verdipar.iterator();
  while (iter.hasNext())
  {
    Map.Entry<Nøkkeltype,Verditype> par = iter.next();
    Nøkkeltype nøkkel = par.getKey();
    Verditype verdi = par.getValue();
    .
    .
  }

Spesialoperasjoner for SortedMap

SortedMap<K,V> er Map-analogien til SortedSet. Som dette, har det operasjoner for å behandle delområder av hele samlingen. De aktuelle metodene er

public SortedMap<K,V> subMap(K fraNøkkel, K tilNøkkel)

Som i tilfelle SortedSet blir det returnert et "halvåpent" intervall.

public SortedMap<K,V> headMap(K tilNøkkel)

Returnerer objektene mindre enn tilNøkkel (som ikke er inkludert).

public SortedMap<K,V> tailMap(K fraNøkkel)

Returnerer objektene større enn eller lik fraNøkkel.

Som i tilfelle SortedSet, kan vi ved bruk av headMap og tailMap få til en todeling av en gitt avbildning.

Programeksempler

Programmet HashMapDemo åpner en tekstfil etter brukers valg. Fila leses ord for ord. Programmet skal registrere frekvensene for forekomstene av de forskjellige ordene. Det gjøres ved å legge (ord, frekvens)-par inn i en avbildning av type HashMap<String, Integer>. For hvert lest ord hentes frekvensen for dette ordet ut av avbildningen. Dersom ordet ikke finnes, legges det inn med frekvens 1. Når det finnes, økes frekvensen med 1. I avbildningen blir frekvensene lagret som Integer-objekter, men på grunn av mekanismen med autoboksing, se foran, kan vi legge dem inn og oppdatere dem som om det var int-verdier. Når alt er lest og registrert, blir resultatet skrevet ut i et tekstområde. Det skjer ved at mengden av (ord, frekvens)-par blir hentet ut av avbildningen og gjennomløpt ved hjelp av en iterator. For hvert par, av type Map.Entry<String, Integer>, blir ord (nøkkel) og frekvens (verdi) hentet ut hver for seg. Programmet består av vindusklassen HashMapDemo og driverklassen HashMapTest. Nedenfor er vindusklassen gjengitt.

  1 import javax.swing.*;
  2 import java.awt.*;
  3 import java.awt.event.*;
  4 import java.util.*;
  5 import java.io.*;
  6
  7 //Teller opp frekvenser for de forskjellige ord i valgt fil.
  8 public class HashMapDemo extends JFrame
  9 {
 10    private JButton velgFil;
 11    private JTextArea utskrift;
 12    private JTextField filvalg;
 13    private Knappelytter lytter;
 14
 15    public HashMapDemo()
 16    {
 17      super( "Opptelling av frekvenser ord" );
 18      velgFil = new JButton( "Velg fil" );
 19      utskrift = new JTextArea( 30, 30 );
 20      utskrift.setEditable( false );
 21      filvalg = new JTextField( 40 );
 22      filvalg.setEditable( false );
 23      JPanel knappepanel = new JPanel();
 24      knappepanel.add( velgFil );
 25      JPanel filpanel = new JPanel();
 26      filpanel.add( new JLabel( "Valgt fil" ) );
 27      filpanel.add( filvalg );
 28      JPanel senterpanel = new JPanel();
 29      senterpanel.setLayout(
 30              new BoxLayout(senterpanel, BoxLayout.PAGE_AXIS));
 31      senterpanel.add( filpanel );
 32      senterpanel.add( new JScrollPane( utskrift ) );
 33      Container c = getContentPane();
 34      c.add( knappepanel, BorderLayout.NORTH );
 35      c.add( senterpanel, BorderLayout.CENTER );
 36      lytter = new Knappelytter();
 37      velgFil.addActionListener( lytter );
 38      pack();
 39      setVisible( true );
 40    }
 41
 42    //Lar brukeren velg fil vha. et JFileChooser-dialogvindu.
 43    public File hentFil()
 44    {
 45      JFileChooser filvelger = new JFileChooser();
 46      filvelger.setCurrentDirectory( new File( "." ) );
 47      int resultat = filvelger.showOpenDialog( this );
 48      if ( resultat == JFileChooser.APPROVE_OPTION )
 49      {
 50        File f = filvelger.getSelectedFile();
 51        String fil = f.getPath();
 52        filvalg.setText( fil );
 53        return f;
 54      }
 55      else
 56        return null;
 57    }
 58
 59    //Leser valgt fil og registrerer frekvenser.
 60    public Map<String, Integer> frekvenser(File fil)
 61    {
 62      Map<String, Integer> forekomster = null;
 63      if ( fil != null )
 64      {
 65        forekomster = new HashMap<>();
 66        try (Scanner ordleser = new Scanner(fil))
 67        {
 68          ordleser.useDelimiter("[.,!;:*?`$\"\'/<>=\\(){}\\s]+");
 69          while (ordleser.hasNext())
 70          {
 71            String ord = ordleser.next();
 72            Integer frekvens = forekomster.get(ord);
 73            if (frekvens == null)  //første forekomst
 74              forekomster.put(ord, 1);
 75            else  //oppdaterer frekvens
 76              forekomster.put(ord, frekvens + 1);
 77          }
 78        }
 79        catch (IOException e)
 80        {
 81          JOptionPane.showMessageDialog( this,
 82                  "Problem med lesing av fil." );
 83        }
 84      }
 85      else
 86        JOptionPane.showMessageDialog( this, "Ingen fil valgt." );
 87      return forekomster;
 88    }
 89
 90    //Skriver ut ord og frekvenser for valgt fil.
 91    public void visFrekvenser( Map<String, Integer> frekvenser )
 92    {
 93       if ( frekvenser != null )
 94       {
 95         Iterator<Map.Entry<String,Integer>> iterator =
 96             frekvenser.entrySet().iterator();
 97         utskrift.setText( "Ord og frekvenser\n" );
 98         while ( iterator.hasNext() )
 99         {
100           Map.Entry<String,Integer> e = iterator.next();
101           utskrift.append( e.getKey() + ": " + e.getValue() + "\n" );
102         }
103         utskrift.setCaretPosition( 0 );
104       }
105       else
106         utskrift.setText( "Ingen fil lest inn." );
107    }
108
109    private class Knappelytter implements ActionListener
110    {
111      public void actionPerformed( ActionEvent e )
112      {
113        if ( e.getSource() == velgFil )
114        {
115          File fil = hentFil();
116          Map<String,Integer> forekomster = frekvenser(fil);
117          visFrekvenser( forekomster );
118        }
119      }
120    }
121 }

Bildet under viser en del av utskriften som vi får ved å bruke programmet på kildefila som definerer programvinduet.

Programmet TreeMapDemo gjør det samme som programmet HashMapDemo med den forskjell at ordene blir registrert og skrevet ut i alfabetisk rekkefølge. De nødvendige endringer er som følger:

Det må opprettes et Collator-objekt som gir riktig rekkefølge for ordene. Dette objektet blir brukt som konstruktørparameter når det blir opprettet et TreeMap<String, Integer>-objekt. Dette brukes istedenfor HashMap<String, Integer>-objektet i forrige program. Vindusklasse for programmet finnes i fila TreeMapDemo.java. Driverklasse ligger i fila TreeMapTest.java. Den del av programmet som har med avbildningen å gjøre er gjengitt nedenfor.

  1 import javax.swing.*;
  2 import java.awt.*;
  3 import java.awt.event.*;
  4 import java.util.*;
  5 import java.io.*;
  6 import java.text.*;
  7
  8 //Teller opp frekvenser for de forskjellige ord i valgt fil.
  9 //Utskrift i alfabetisk rekkefølge.
 10 public class TreeMapDemo extends JFrame
 11 {
 12   private JButton velgFil;
 13   private JTextArea utskrift;
 14   private JTextField filvalg;
 15   private Knappelytter lytter;
 16   private String rekkefølge;
 17   private Collator kollator;
 18
 19   public TreeMapDemo()
 20   {
        .
        .
 42     rekkefølge = "<\0<0<1<2<3<4<5<6<7<8<9" +
 43             "<A,a<B,b<C,c<D,d<E,e<F,f<G,g<H,h<I,i<J,j" +
 44             "<K,k<L,l<M,m<N,n<O,o<P,p<Q,q<R,r<S,s<T,t" +
 45             "<U,u<V,v<W,w<X,x<Y,y<Z,z<Æ,æ<Ø,ø<Å=AA,å=aa;AA,aa";
 46     try
 47     {
 48       kollator = new RuleBasedCollator( rekkefølge );
 49             //for riktig sortering av norske ord
 50     }
 51     catch ( ParseException pe )
 52     {
 53       JOptionPane.showMessageDialog( null,
 54               "Feil i rekkefølgestring for kollator!" );
 55       System.exit( 0 );
 56     }
 57     pack();
 58     setVisible( true );
 59   }
 60
 61   //Lar brukeren velg fil vha. et JFileChooser-dialogvindu.
 62   public File hentFil()
 63   {
        .
        .
 76   }
 77
 78   //Leser valgt fil og registrerer frekvenser.
 79   public Map<String,Integer> frekvenser( File fil )
 80   {
 81     Map<String,Integer> forekomster = null;
 82     if ( fil != null )
 83     {
 84       forekomster = new TreeMap<>( kollator );
 85       try (Scanner ordleser = new Scanner( fil ))
 86       {
 87         ordleser.useDelimiter("[.,!;:*?`$\"\'/<>=\\(){}\\s]+");
 88         while ( ordleser.hasNext() )
 89         {
 90           String ord = ordleser.next();
 91           Integer frekvens = forekomster.get( ord );
 92           if ( frekvens == null )  //første forekomst
 93             forekomster.put(ord, 1);
 94           else  //oppdaterer frekvens
 95             forekomster.put( ord, frekvens + 1);
 96         }
 97       }
 98       catch (IOException e)
 99       {
100         JOptionPane.showMessageDialog( this,
101                 "Problem med lesing fra fil." );
102       }
103     }
104     else
105       JOptionPane.showMessageDialog( this, "Ingen fil valgt." );
106     return forekomster;
107   }
108
109   //Skriver ut ord og frekvenser for valgt fil.
110   public void visFrekvenser( Map<String,Integer> frekvenser )
111   {
112     if ( frekvenser != null )
113     {
114       Iterator<Map.Entry<String,Integer>> iterator =
115           frekvenser.entrySet().iterator();
116       utskrift.setText( "Ord og frekvenser\n" );
117       while ( iterator.hasNext() )
118       {
119         Map.Entry<String,Integer> e = iterator.next();
120         utskrift.append( e.getKey() + ": " + e.getValue() + "\n" );
121       }
122       utskrift.setCaretPosition( 0 );
123     }
124     else
125       utskrift.setText( "Ingen fil lest inn." );
126   }
127
128   private class Knappelytter implements ActionListener
129   {
130     public void actionPerformed( ActionEvent e )
131     {
132       if ( e.getSource() == velgFil )
133       {
134         File fil = hentFil();
135         Map<String,Integer> forekomster = frekvenser( fil );
136         visFrekvenser( forekomster );
137       }
138     }
139   }
140 }

Bildet under viser en del av utskriften som programmet gir når det blir brukt på samme fil som foregående program ble brukt på, se bildet ovenfor.

Innholdsoversikt for programutvikling

Copyright © Kjetil Grønning og Eva Hadler Vihovde, revidert 2015