Ukeoppgaver 27. april - 1. mai (INF1000 - Vår 2009)

HashMap (kap. 9.1 - 9.11), oppramstyper (kap. 8.16), innstikksortering (kap. 5.6), og litt om javadoc.

Mål
Forstå forskjellene mellom arrayer og HashMap; og få litt øvelse i bruk av enum, innstikksortering, og javadoc-kommentarer.

Oppgaver til teoritimen

HashMap: Hva skrives ut? (Se oversikten på side 188 i læreboka)

import java.util.*;
class Personer {
    public static void main(String[] args) {
	HashMap <String, Person> register = new HashMap <String, Person> ();

	Person p1 = new Person("Ida", 19);
	Person p2 = new Person("Lars", 21);

	register.put(p1.navn, p1);
	register.put(p2.navn, p2);

// a)
	Person p = register.get("Ida");
	System.out.println(p.navn + p.alder);

// b)
	for (String s : register.keySet()) {
	    System.out.println(s);
	}
// c)
	p1.alder = 24;
	for (Person p3 : register.values()) {
	    System.out.println(p3.navn + ":" + p3.alder);
	}
// d)
	if (register.containsValue(p2) && ! register.containsKey("Elin")) {
	    System.out.println(true);
	}
// e)
	register.remove("Lars");
	System.out.println(register.size() + " - " + register.isEmpty());
// f)
	System.out.println(register.remove("Ida") == null);
	System.out.println(register.remove("Ida") == null);
    }
}

class Person {
    String navn;
    int alder;

    Person(String navn, int alder) {
	this.navn = navn;
	this.alder = alder;
    }
}

Bank.java: Array vs. HashMap
(a) Følgende program viser et enkelt banksystem med en array kontoer[], og metoder for å finne en konto vha. navn til eieren og vha. kontonummer. Skriv om programmet slik at det bruker en HashMap i stedet for arrayen kontoer[]. I første omgang lager vi én HashMap, med personnavn som nøkkel og et Konto-objekt som verdi, deklarert slik:
HashMap <String, Konto> kontoFraNavn = new HashMap <String, Konto>();
Hvilke fordeler og ulemper får vi av å bruke HashMap her? Hva kan variabelen antKontoer erstattes med i programmet? (Anta foreløpig at personnavnene er unike og at hver person bare kan ha én konto i banken.)

class Konto {
    int nr; // kontonummer
    String navn; // eier
    int saldo;

    Konto(int nr, String navn, int saldo) {
	this.nr = nr;
	this.navn = navn;
	this.saldo = saldo;
    }

    void settInn(int innskudd) {
	saldo = saldo + innskudd;
    }
}

class Bank {
    Konto[] kontoer = new Konto[1000];
    int antKontoer = 0;

    public static void main(String[] args) {
	Bank b = new Bank();
    }

    Bank() {
        åpneNyttKonto(530010, "Nils", 4000);
        åpneNyttKonto(720020, "Elin", 8000);
        åpneNyttKonto(910030, "Tina", 9000);

        Konto k = finnKontoFraNavn("Elin");
        System.out.println("Elins kontonr: " + k.nr + ", saldo: " + k.saldo);

	k = finnKontoFraNr(530010);
	System.out.println("Kontonr. " + k.nr + " tilhører " + k.navn);
    }

    void åpneNyttKonto(int nr, String navn, int saldo) {
	Konto k = new Konto(nr, navn, saldo);
	kontoer[antKontoer] = k;
	antKontoer++;
    }

    Konto finnKontoFraNavn(String navn) {
	for (int i = 0; i < antKontoer; i++) {
	    if (kontoer[i].navn.equals(navn)) {
		return kontoer[i];
	    }
	}
	return null;
    }

    Konto finnKontoFraNr(int kontonr) {
	for (int i = 0; i < antKontoer; i++) {
	    if (kontoer[i].nr == kontonr) {
		return kontoer[i];
	    }
	}
	return null;
    }
}

KJØREEKSEMPEL:
Elins kontonr: 720020, saldo: 8000
Kontonr. 530010 tilhører Nils

(b) Lag en HashMap til, kalt kontoer, hvor du bruker som nøkkel kontonummeret konvertert til String, og fortsatt Konto-objektene som verdi. Vis at metoden finnKontoFraNr() blir enklere nå. Videre tenk deg at vi skal ha en metode for å fjerne en konto. Følgende kode viser hvordan det kan gjøres med arrayer. Hvor mange programsetninger trengs det når vi bruker én HashMap i stedet? Og med to?

    void avsluttKonto(Konto k) {
	// Fjerner en konto ved å finne indeksen til kontoen i arrayen
	// kontoer[] og flytte alle kontoene med høyere indeks en plass ned.
	boolean funnet = false;
	for (int i = 0; i < antKontoer && !funnet; i++) {
	    if (kontoer[i] == k) {
		funnet = true;
		for (int j = i; j < antKontoer - 1; j++) {
		    kontoer[j] = kontoer[j + 1];
		}
		antKontoer--;
	    }
	}
    }

(c) Disse oppgavene har begrensningen at personnavnene må være unike og at hver person bare kan ha én konto i banken. Hvordan ville man unngått disse begrensninger i et mer avansert system? Hvilke fordeler og ulemper ser du av å bruke HashMap-er i Oblig 3? (foreslå mulige nøkkel/verdi-kombinasjoner).
Hint: Se avsnitt 9.11 på side 189 i læreboka for forskjellene mellom arrayer og HashMap-er.

Oppramstyper: "enum" (side 158)
Lag en oppramstype for måneder (jan, feb,..) og et program som ber bruker taste inn månedsnummer (1, 2,..) og gir månedsnavnet som svar. Hint: Se følgende eksempel fra side 158 i læreboka (også gitt på side 2 i lysarkene uke 8):

enum Farge {
    rød, grønn, blå, gul;
}

class EnumEks {
    public static void main(String[] args) {
	Farge f = Farge.rød;
	System.out.println("Farge f er:" + f);

	for (Farge ff: Farge.values()) {
	    System.out.println("ff:" + ff + ", nummer:" + ff.ordinal());
	}
    }
} // end class EnumEks

KJØREEKSEMPEL:
Farge f er:rød
ff:rød, nummer:0
ff:grønn, nummer:1
ff:blå, nummer:2
ff:gul, nummer:3

Innstikksortering av kontoer: (læreboka side 93; lysark uke 8 s. 36)
Ta utgangspunkt i programmet fra side 25 og 36 i lysarkene uke 8 (gjengitt under) som sorterer en heltalls-array og en String-array, og lag en metode som sorterer arrayen kontoer[] fra punkt 2 (a) alfabetisk på navn. Etter et kall på metoden skal f.eks. kontoer[0] være Elins konto, kontoer[1] Nils sin, osv. Metoden skal ha to inn-parametre: Konto[] kontoer, og int antKontoer; og skal kunne sortere et vilkårlig antall kontoer. Utvid programmet i punkt 2 (a) med et kall på metoden for å sjekke at den fungerer.

class Innstikksort {

    /** Sorterer en heltallsarray */
    public static void sorter(int[] a) {
	for (int k = 0 ; k < a.length - 1; k++) {

	    if (a[k] > a[k + 1]) {
		// a[k + 1] står på feil plass, ta den ut:
		int tmp = a[k + 1];
                int i = k;

		// Skyv a[i] mot høyre ett hakk til
		// vi finner riktig plass til tmp:
		while (i >= 0 && a[i] > tmp) {
		    a[i + 1] = a[i];
		    i--;
		}
		// Sett tmp inn på riktig plass:
		a[i + 1] = tmp;
	    }
	}
    }

    /** Sorterer en String-array */
    public static void sorter(String[] a) {
	for (int k = 0 ; k < a.length - 1; k++) {
	    if (a[k].compareTo(a[k + 1]) > 0 ) {
		String tmp = a[k + 1];
		int i = k;
		while (i >= 0 && (a[i].compareTo(tmp) > 0)) {
		    a[i + 1] = a[i];
		    i--;
		}
		a[i + 1] = tmp;
	    }
	}
    }
}

/** Test av innstikksortering */
class TestInnstikksort {
    public static void main(String[] args) {

	int[] a = { 3, 1, 7, 14, 2, 156, 77 };
	Innstikksort.sorter(a);
	for (int i = 0; i < a.length; i++) {
	    System.out.println("a[" + i + "] = " + a[i]);
	}

	String[] navn = { "Ola", "Kari", "Arne", "Jo" };
	Innstikksort.sorter(navn);
	for (int i = 0; i < navn.length; i++) {
	    System.out.println("navn[" + i + "] = " + navn[i]);
	}
    }
}

KJØREEKSEMPEL:
a[0] = 1
a[1] = 2
a[2] = 3
a[3] = 7
a[4] = 14
a[5] = 77
a[6] = 156
navn[0] = Arne
navn[1] = Jo
navn[2] = Kari
navn[3] = Ola

Oppgaver til terminaltimen

HashMap, enum, og innstikksortering:
(Samme oppgaver som i punkt 2 - 4 for teoritimen).
Fortsett å jobbe med din Oblig 3. Se tipsene fra seminaret og Marits objekter.pdf.
Mer om HashMap-er: (som oppgave 4 i kap. 9, side 195)
Finn fram en oppgave du har løst vha. arrayer, og bytt ut noen av arrayene med HashMap-er. Hvilke deler av programmet blir enklere nå, evt. vanskeligere? Bruk gjerne din egen Oblig 2 eller 3.
Javadoc: (lysark uke 8, side 39 - 44)
Se eksemplene på javadoc-kommentarer her eller på side 39 i lysarkene uke 8 og skriv lignende kommentarer i din Oblig 3. Javadoc-kommentarer startes med /** og avsluttes med */, og plasseres i linjen(e) rett før klassen, metoden, eller objektvariabelen man ønsker å kommentere. Kjør deretter javadoc-kommandoen som vist på side 40 i lysarkene:
```
> javadoc -package Programnavn.java
> opera index.html &
```
Åpne til slutt den genererte index.html-filen i en browser for å se på resultatet. (NB! Javadoc er ikke et krav i Oblig 3, men du kan godt begynne å eksperimentere med det allerede nå!).
Ukens nøtt: Dobbel-sortert utskrift av HashMap (veldig vanskelig!)
Lag en metode "void skrivSortert(HashMap <String, Person> register)" som skriver ut innholdet i HashMap-en fra punkt 1 for teoritimen sortert på alder. Utskriften skal vise alder og navn for personene, og hvis det er flere med samme alder skal disse skrives ut sortert på navn. For å teste metoden lager du et objekt av klassen Personer og kaller metoden din via dette objektet, etter å ha lagt inn 5 personer i HashMap-en: Ida 19, Lars 21, Elin 21, Nils 19, og Anna 19.

Løsningsforslag
Løsningsforslagene viser én av mange mulige måter å løse disse oppgavene på.