Java

Innhold

• Klasser og objekter
• Bruk av grensesnitt
• Java Collection Framework
• Lister
• Iteratorer

Kompilering og tolking

• Kildekoden i et Java-program lagres på i fil med endelse .java
• Kildekoden må inneholde deklarasjon av en klasse, f.eks.
  public class MinKlasse { ... }
  Navnet på klassen må være det samme som navnet til filen. Hvis klassen heter MinKlasse, så må filen hete MinKlasse.java.
• Javakompilatoren oversetter Java kildekode til Java bytekode. Bytekode er en lav-nivå representasjon av programmet, men den er ikke bundet til noen bestemt prosessor-type.
  
  Kommando for å kompilere et Java-program:
  javac MinKlasse.java
• Bytekoden blir liggende i en fil med endelse .class, i eksemplet over vil filen hete MinKlasse.class.
• Javatolkeren Leser Java bytekode og kjører den på den aktuelle maskinen du sitter ved. Kommando:
  
  
  java Minklasse
• Fordel: Java er arkitektur-nøytral. D.v.s. ikke bundet til en bestemt hardware-plattform, og kan kjøres på forskjellige plattformer uten å rekompileres. Eneste betingelse er at maskinen har en java-tolker.

Utviklingsmiljø

• Editor + kommandolinje, eller IDE (Integrated Development Environment)?
• Velg det dere er mest fortrolig med.
• MEN: Jeg vil sterkt anbefale dere at dere lærer dere og tar i bruk en IDE, f.eks. Netbeans eller Eclipse:
  1. Mer effektiv koding.
  2. Bedre oversikt.
  3. Automatisk tilgang dokumentasjon.
  4. Automatisk utfylling av argumenter, klassemetoder etc.
  5. Og til slutt, men kanskje viktigst: Alle IDE'er har en god debugger, som bla.a. gir dere en visuell oversikt over både programutførelse og tilstanden på datastrukturene. Gjør det mye enklere å forstå f.eks. rekursjon.

Arv

• Gjør det mulig å utvide eller spesialisere funksjonaliteten til et objekt.
• Fordeler:
  • Gjenbruk av kode.
  • Gjør det enklere å oppdatere/vedlikeholde kode i store applikasjoner.
• Suns API er bygget opp som et stort arvehirearki, med klassen Object på toppen.

Abstrakte klasser

Formålet med en abstrakte klasse er å bruke den som superklasse og gjennom arv tvinge subklassene til å til å implementere bestemte metoder.

En abstrakt metode er en metode som definerer funksjonalitet som alle klasser som arver må implementere (eller deklarere som abstrakt, men da blir klassen abstrakt også.....).

Klassen Oppgave skal beskrive en oppgave i en "to-do"-liste. Den er abstrakt - følgelig kan det ikke opprettes objekter av denne klassen.

package forelesning;

public abstract class Oppgave implements Comparable<Oppgave> {
     
    public boolean equals(Object o){
        if (o instanceof Oppgave){
            return toString().equals(o.toString());
        }
        else
           return false;  
    }

    public int hashCode() {        
        return toString().hashCode(); 
    }

    public int compareTo(Oppgave o){
        return toString().compareTo(o.toString());
    }
    
    public abstract String toString() ; 
}

Konkrete klasser

Klassene AlgDatOppgave og TelefonOppgaver er subklasser til klassen Oppgave. I tillegg til metodene som arves fra superklassen, inneholder begge klassene en implementasjon av toString-metoden, konstruktører og objektvariabler som beskriver egenskaper som beskriver disse oppgavetypene.

package forelesning;
public class AlgDatOppgave extends Oppgave{

    private String beskrivelse; 
    
    public AlgDatOppgave(String beskrivelse){
        this.beskrivelse = beskrivelse; 
    }
       
    public String hentBeskrivelse(){return beskrivelse;}
    
    public String toString() {
        return "algDat " + beskrivelse; 
    }
    
}

package forelesning;

public class TelefonOppgave extends Oppgave {
    private String navn; 
    private String nummer;

    public TelefonOppgave(String navn, String nummer){
        this.navn = navn; 
        this.nummer = nummer; 
    }
    
    public String hentNavn(){return navn; }
    public String hentNummer() {return nummer; }
        
    @Override
    public String toString() {
        return "ring " + navn;  
    }
}

Lage objekter av en klasse:

        TelefonOppgave ringKarl= new TelefonOppgave("Karl","46464646");
        TelefonOppgave ringNils = new TelefonOppgave("Nils", "91324354");
        AlgDatOppgave lagLenke = new AlgDatOppgave("Lag lenket liste");
        AlgDatOppgave lagIterator = new AlgDatOppgave("Lag iterator til lenket liste");
        AlgDatOppgave lagTrenode = new AlgDatOppgave("Lag trenode");
        

Grensesnitt (interface)

• Definerer hvilke tjenester (metoder ) et objekt skal tilby, men uten å implementere noen av metodene.
• Inneholder kun spesifikasjon av metoder og konstanter. Spesifikasjonen av en metode består av metodens returtype, navn og parametere.
• Hvis en klasse skal implementere grensesnittet må den angi dette i deklarasjonen ved å bruke nøkkelordet implements . For å kunne lage objekter av klassen, må den i tillegg implementere alle de spesifiserte metodene.
• Hvis en klasse har implementert et grensesnitt, har vi en forsikring om at objekter av denne klassen tilbyr bestemte tjenester, som vi kan bruke i forskjellige sammenhenger. For eksempel vet vi at det er mulig å sammenlikne objekter av en klasse som implementerer grensesnittet Comparable.

Java Collections Framework (JCF)

• En samling (collection) er et objekt som oppbevarer og organiserer andre objekter.
• Ulike problemstillinger gir opphav til ulike behov når det gjelder måten objektene organiseres på.
• Det er vanlig å definere hvordan elementene i en slik samling kan aksesseres / hvilke operasjoner som kan utføres på samlingen i et grensesnitt. Grensesnittet kan betraktes som en modell av hvordan objektene organiseres. En slik modell kalles også en abstrakt datatype(ADT).
• En ADT kan implementeres ved bruk av forskjellige datastrukturer. Den finnes ingen "beste" implementasjon, det vil si en implementasjon som er mer effektiv enn alle andre for alle operasjonene som skal kunne utføres på samlingen.
• JCF består av hirearkier av grensesnitt og klasser som ligger i pakkene java.util og java.util.concurrent.

Grensesnittet Collection

Beskriver grunnleggende funksjonalitet som vi forventer av alle samlinger unntatt maps. Metodene kan deles inn i 4 hovedkategorier.

• Legge til elementer
• Fjerne elementer
• Utføre søk
• Gjøre samlingens innhold tilgjengelig for videre prosessering

Lister

• Den kanskje mest brukte Java-samlingen
• Kan inneholde duplikater
• Kan indekseres, bruker har full kontroll over rekkefølgen til elementene og kan for eksempel bestemme hvor i listen et nytt element skal settes inn
• Flere implementasjoner av grensesnittet List
  • ArrayList: Grensesnittet List implementert ved bruk av tabell
  • LinkedList: Grensesnittet List implementert ved bruk av lenket liste

Legge inn objekter i liste

• Klassene i Collection-hirearkiet har en typeparameter som brukes til å spesifisere hva slags objekter som skal legges inn i samlingen.
• Fordelen med dette er blant annet at kompilatoren kan sjekke om det er typefeil i programmet og det blir enklere å hente objekter ut av samlingene.
• Her lages 3 ArrayList-objekter
  • telefonOppgaver - skal inneholde TelefonOppgave-objekter
  • algdatOppgaver - skal inneholde AlgDatOppgave-objekter
  • mandagOppgaver - kan inneholde alle slags oppgaver.

        ArrayList<TelefonOppgave> telefonOppgaver = new ArrayList<TelefonOppgave>(); 
        telefonOppgaver.add(ringNils);
        telefonOppgaver.add(ringKarl); 
        System.out.println(telefonOppgaver);
        
        ArrayList<AlgDatOppgave> algdatOppgaver = new ArrayList<AlgDatOppgave>(); 
        algdatOppgaver.add(lagIterator);
        algdatOppgaver.add(lagLenke);
        algdatOppgaver.add(lagTrenode);
        System.out.println(algdatOppgaver);
        
        
        ArrayList<Oppgave> mandagOppgaver = new ArrayList<Oppgave>(); 
        mandagOppgaver.addAll(algdatOppgaver);
        mandagOppgaver.add(ringNils);
        

Iteratorer

• En iterator er en objekt som implementerer grensesnittet Iterator.
• Hensikt: Oppnå en standard måte å aksessere elementene i en samling på.
• Uansett hva slags type samling du har med å gjøre og hvordan den er implementert, kan elementene prosesseres på samme måte.
• Samlingene kan prosesseres ved eksplisitt bruk av iteratoren, eller implisitt ved bruk av en foreach-setning.

Grensesnittete Iterable og Iterator

public interface Iterator<E>{
	boolean hasNext(); //returnerer sann hvis iterasjonen har fler elementer
	E next();          //returnerer neste element i iterasjonen 
	void remove;       //fjerner siste elemenet som ble returnert fra iteratoren
}
            

public interface Iterable<T>{
	Iterator <T> iterator(); //returnerer iterator over elemeneter av type T
}
		

Foreach

        for (TelefonOppgave o: telefonOppgaver){
            System.out.println(o);
        }
        

• Kan benyttes av alle objekter som implementerer grensesnittet Iterable, det vil si: alt som kan produsere en iterator.
• Tilfeller for alle samlinger i JCF, unntatt maps.
• Begrensninger:
  • Kan ikke bruke remove-metoden
  • Kan ikke prossessere to eller flere samlinger i parallell.

Eksplisitt bruk av iterator

Foreach-løkka er egentlig en kortform for følgende konstruksjon, hvor iteratoren brukes eksplisitt.

        for(Iterator<TelefonOppgave> it = telefonOppgaver.iterator();it.hasNext(); ){
            System.out.println(it.next());
        }
        

ConcurrentModificationException

• Hvis samlingen en iterator er opprettet for endrer struktur (for eksempel ved at elementer i samelingen legges til eller slettes), vil ikke iteratoren lenger kunne brukes.
• Metodene til iteratoren sjekker at samlingen ikke er endret siden forrige iterator-metodekall. Hvis endring oppdages (samlingen endret av en annen iterators remove-metode eller av samlingens egne metoder), kastes et unntak av typen ConcurrentModificationException.

Eksempel:

Vil fjerne alle telefonoppgavene fra listen over mandagens gjøremål:

Forsøk 1. Går ikke, ødelegger iteratoren:

        for(Oppgave o: mandagOppgaver){
            if(o instanceof TelefonOppgave){
                mandagOppgaver.remove(o);
            }
        }
        

Forsøk 2: Ingen forbedring:

        for (Iterator<Oppgave> it = mandagOppgaver.iterator(); it.hasNext(); ){
            Oppgave o = it.next();
            if(o instanceof TelefonOppgave){
                mandagOppgaver.remove(o);
            }
        }
        

Forsøk 3: Skal vi slette et eller flere elementer mens iteratoren er i bruk, må vi bruke iteratorens remove-metode:

        
        for (Iterator<Oppgave> it = mandagOppgaver.iterator(); it.hasNext(); ){
            Oppgave o = it.next();
            if(o instanceof TelefonOppgave){
                it.remove();            }
        }           
        

ListIterator

Lister har i tillegg til den "vanlige" iteratoren en metode som returnerer en ListIterator med utvidede muligheter.

Kan blant annet traversere listene baklengs:

        ListIterator<Oppgave> lit = mandagOppgaver.listIterator();
     
        while(lit.hasNext())
            System.out.println("Neste: " +lit.next());
       
        while(lit.hasPrevious())
            System.out.println("Forrige: " +lit.previous());
        

Et ekspriment

Det finnes flere implementasjoner av grensesnittet List i JCF. To av dem er ArrayList og LinkedList, som implementerer grensesnittet med henholdsvis tabell og lenket liste.

Vi tester hvor effektive implementasjonene er mhp:

• Innsetting av nytt element (add)
• Se på element på en bestemt plass i lista (get(i)
• Fjerne ett og ett element ved bruk av iteratorens remove-metode.
• Praktisk forsøk: tar tiden når operasjonene utføres mange ganger (stort datasett).

Datasettene

• Datasettene vi skal bruke er hentet fra http://www.geonames.org .
• cities1000.txt inneholder data for byer med over 1000 innbyggere (drøyt 80 000 byer)
• cities15000.txt inneholder data for byer med over 15000 innbyggere (drøyt 20 000 byer).

Testprogram

package p1;

public class By implements Comparable<By> {

    private int id;
    private String navn;
    private String land;
    private int innbyggertall;
    private double lengdegrad;
    private double breddegrad;

    public By(int id, String navn, String land, int innbyggertall, double lengdegrad, double breddegrad) {
        this.id = id;
        this.navn = navn;
        this.land = land;
        this.innbyggertall = innbyggertall;
        this.lengdegrad = lengdegrad;
        this.breddegrad = breddegrad;
    }

    public double hentLengdegrad() {
        return lengdegrad;
    }

    public double hentBreddegrad() {
        return breddegrad;
    }

    public String hentLand() {
        return land;
    }
    
    public int hentInnbyggertall() {
        return innbyggertall; 
    }
    
    @Override
    public String toString() {
        return "" + id + ", " +
                navn + ", " + land +
                ", " + innbyggertall +
                ", " + lengdegrad + ", " + breddegrad;
    }

    
    public int compareTo(By o) {
        return navn.compareTo(o.navn);
    }
    

    @Override
    public boolean equals(Object o){
        By b = (By) o; 
        
        return navn.equals(b.navn);            
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 53 * hash + (this.navn != null ? this.navn.hashCode() : 0);
        hash = 53 * hash + (this.land != null ? this.land.hashCode() : 0);
        return hash;
    }
}

package p1;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Collection;
import java.util.List;


public class ByLeser {
    
    private String filsti; 
    
    public ByLeser(String filsti){
        this.filsti = filsti; 
    }
    
    public void les(Collection<By> c){
        try {

            BufferedReader br = new BufferedReader(new FileReader(filsti)); 
           
            String linje = br.readLine();
            
            while(linje != null ){
                                
                String [] deler = linje.split("\t");
                By b = new By(Integer.parseInt(deler[0]),
                              deler[2],
                              deler[8], 
                              Integer.parseInt(deler[14]),
                              Double.parseDouble(deler[5]),
                              Double.parseDouble(deler[4]));
                //System.out.println(b);                
                c.add(b);
                
                linje = br.readLine(); 
            
            }
        } catch (Exception exception) {
            System.out.println(exception); 
        }        
    }
    
    
}

package p1;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class TestListeKlasser {

    public static void main(String[] args) {

        ArrayList<By> arrayByListe = new ArrayList<By>();
        LinkedList<By> lenketByListe = new LinkedList<By>();

        ByLeser leser = new ByLeser("cities15000.txt");

        /* ----------- 1. Innlesing - bruk av add-metoden ---------- */
        long startArrayList = System.currentTimeMillis();
        leser.les(arrayByListe);
        long sluttArrayList = System.currentTimeMillis();
        long diffArrayList = sluttArrayList - startArrayList;

        long startLinkedList = System.currentTimeMillis();
        leser.les(lenketByListe);
        long sluttLinkedList = System.currentTimeMillis();
        long diffLinkedList = sluttLinkedList - startLinkedList;


        System.out.println("\n\t *** 1. Innlesing: ***  ");
        System.out.println("\t\tArrayList:" + diffArrayList + ", size: " + arrayByListe.size());
        System.out.println("\t\tLinkedList:" + diffLinkedList + ", size: " + lenketByListe.size());


        /* ----------- 2.  Bruk av get-metoden ---------- */        
        int n=arrayByListe.size();         
        Random generator = new Random();
        
        startArrayList = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            int element = generator.nextInt(n); 
            By b = arrayByListe.get(element);
        }
        sluttArrayList = System.currentTimeMillis();
        diffArrayList = sluttArrayList - startArrayList;
        
        startLinkedList = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            int element = generator.nextInt(n); 
            By b = lenketByListe.get(element);
        }
        sluttLinkedList = System.currentTimeMillis();
        diffLinkedList = sluttLinkedList - startLinkedList;

        System.out.println("\n\t *** 2. get: ***  ");
        System.out.println("\t\tArrayList:" + diffArrayList );
        System.out.println("\t\tLinkedList:" + diffLinkedList);


        /* ----- 3.  Fjerne alle elementer ved hjelp av iterators remove ---------- */                
        startArrayList = System.currentTimeMillis();
        for (Iterator<By> it = arrayByListe.iterator(); it.hasNext();  ){
            it.next(); 
            it.remove();
        }
        sluttArrayList = System.currentTimeMillis();
        diffArrayList = sluttArrayList - startArrayList;
        
        startLinkedList = System.currentTimeMillis();
        for (Iterator<By> it = lenketByListe.iterator(); it.hasNext();  ){
            it.next(); 
            it.remove();
        }
        sluttLinkedList = System.currentTimeMillis();
        diffLinkedList = sluttLinkedList - startLinkedList;
        
        System.out.println("\n\t *** 3. remove: ***  ");
        System.out.println("\t\tArrayList:" + diffArrayList +" size: " + arrayByListe.size() );
        System.out.println("\t\tLinkedList:" + diffLinkedList +" size: " + arrayByListe.size());        
    }
}

Å sammenlikne objekter

• Vi er ofte interessert i å sammenlikne objekter av samme type, for eksempel for å sortere eller finne største/minste verdi i en tabell.
• Primitive datatyper (int, double) kan sammenliknes ved hjelp av sammenlikningssoperatorene. Dette går ikke for objekt-typer, de må sammenliknes ved hjelp av en metode. Vi må selv bestemme hva det skal bety at ett objekt sorterer før et annet av samme type.
• Grensesnittet Comparable inneholder spesifikasjonen av kun en metode, compareTo. Når en klasse implementerer Comparable , har vi en forsikring om at det er mulig å sammenlikne to objekter av denne klassen.
• Flere klasser i Javas standardbibliotek - blant annet String - implementerer Comparable.
• Andre klasser inneholder metoder som baserer seg på den naturlige ordningen som defineres av compareTo-metoden. Blant annet gjelder dette klasser i Java Collection Framework som brukes til å lage ordnede (sorterte) samlinger (f.eks. OrderedSet og OrderedMap og TreeSet). Det samme flere av de statiske metodene i klassen Collections

Grensesnittet Comparable

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

• Inneholder en metode som kan brukes til å sammenlikne ett objekt med et annet.
• Returnerer en verdi som er negativ, 0 eller positiv, avhengog av om argumentet er mindre enn, lik eller større enn det gitte objektet.
• Ordningen som spesifiseres når en klasse implementerer grensesnittet Comparable kalles gjerne den naturlige ordningen for denne klassen.
• Det er vanlig praksis å implementere compareTo-metoden slik at den er konsistent med equals-metoden, d.vs.
  x.equals(y) hvis og bare hvis x.compareTo(y) == 0
• Bostaven T er en typeparameter. Slik det står kan T i interfacet Comparable bety hvilken som helst objekt-type. Men når vi implementerer Comparable, så angir vi hvilken datatype interfacet implemeteres for ved å erstatte typeparameteren T med den aktuelle objekttypen.
• Hvis T er en hvilken som helst klasse, og T implementerer Comparable<T> sier vi at objekter av klassen T er sammenlignbare med seg selv.

• Klassen Oppgave implementerer Comparable<Oppgave>, Oppgave-objekter er dermed sammenliknbare med seg selv.
• Den naturlige ordningen den samme som strengene som returneres fra toString-metoden.
• To Oppgave-objekter er like hvis objektenes toString-metode returnerer samme streng.
• compareTo-metoden er dermed konsistent med equals-metoden.

Mengder (Set)

• En mengde er en samling som i motsetning til lister ikke kan inneholde duplikater.
• To implementasjoner:
  • TreeSet: Elementene lagres i en trestruktur, sortert i henhold til elementenes verdi. Samlingens iterator gir elementene i sortert rekkefølge.
  • HashSet: Elementene lagres i en hash-tabell. Det vil si at elementene posisjon i tabellen bestemmes av en såkalt hash-funksjon basert på elementenes innhold. En god hash-funksjon genererer hashkoder med god spredning, noe som medfører at hashtabeller er svært effektive med hensyn på søk.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package p1;

import java.util.HashSet;
import java.util.TreeSet;

/**
 *
 * @author maa
 */
public class TestSet {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        String setning = "i dette eksemplet skal ordene lagres i alfabetisk rekkef��lge"; 
        
        String [] deler = setning.split(" "); 
        
        // Legger ordene inn i et TreeSet
        TreeSet<String> ord = new TreeSet<String>(); 
        for (String s: deler){
            if (!ord.add(s)) 
                System.out.println("Duplikat: " + s);
        }
        
        System.out.println("TreeSet: Antall ord: " + ord.size() +": " +  ord);

        //foreach
        for (String o: ord)
            System.out.println(o);
        
                
        // Legger ordene inn i et HashSet
        HashSet<String> ord2 = new HashSet<String>(); 
        for (String s: deler){
            ord2.add(s); 
        }        
        System.out.println("HashSet: Antall ord: " + ord2.size() +": " +  ord2);  
        
        
    }

}

Grensesnittet Comparator

• Det kan være at vi ønsker å sortere objektene i en samling med hensyn på en egenskap i en sammenheng, en annen egenskap i en annen sammenheng.
• Får da et problem med compareTo-metoden fordi en klasse kun kan inneholde en compareTo-metode. Løsningen er å bruke en eller flere såkalte komparatorer, det vil si vi lager en klasse som implementerer grensesnittet Comparator .

package p1;

import java.util.Comparator;


public class OrdLengdeKomparatorV1  implements Comparator<String>{

    public int compare(String o1, String o2) {
       int l1 = o1.length();
       int l2 = o2.length(); 
       
       return (l1<l2) ? -1 : (l1 == l2) ? 0 : 1; 
    }
}

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package p1;

import java.util.Comparator;

/**
 *
 * @author maa
 */
public class OrdLengdeKomparatorV2 implements Comparator<String>{

    public int compare(String o1, String o2) {
        int l1 = o1.length(); 
        int l2 = o2.length(); 
                        
        return (l1<l2) ? -1 : (l1>l2)?1:o1.compareTo(o2);        
    }
    
}

Maps

Grensesnittet Map beskriver en samling som kobler nøkler og data (verdi).

• HashMap: Nøkkel-verdi-par lagres i en hash-tabell.
• TreeMap: Nøkkel-verdi-par lagres i en trestruktur, sortert etter nøklenes ordning.

package p1;

import java.util.HashMap;
import java.util.TreeMap;

public class TestMap {

    public static void main(String[] args) {
        
        String setning = "jeg kom jeg s�� jeg gikk"; 
        String [] deler = setning.split(" ");
        
        //Frekvensopptelling: HashMap
        HashMap<String,Integer> map = new HashMap<String,Integer>(); 
        
        for (String s: deler ){
            Integer i = map.get(s);
            map.put(s, (i==null) ? 1: i+1);
        }
        
        System.out.println("Antall forskjellige ord: " + map.size() + "\n"+map); 
        
        //Sortert p�� n��kkel: TreeMap
        TreeMap<String, Integer> tmap = new TreeMap<String, Integer>(map);
        System.out.println("Antall forskjellige ord: " + tmap.size() + "\n"+tmap); 
        
    }

}