INF1000 - Høst 2012

Ukeoppgaver 9: 17. - 23. okt (INF1000 - Høst 2012)

Hashmap, sortering, oppramstyper og litt om Javadoc (kap. 9 i "Rett på Java" 3. utg.)

Mål
Mer om HashMap, litt om sortering, oppramstyper og Javadoc.

Oppgave merket med nøkkelsymbol er plukket ut som spesielt representativ for de viktigste temaene fra ukens forelesning, og alle bør ha som minimumsmål å løse denne selvstendig.

Oppgaver

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 stedet for 2D-arryaer i Oblig 3? (foreslå mulige nøkkel/verdi-kombinasjoner).

Hint: Se avsnitt 9.11 på side 191 i læreboka for forskjellene mellom arrayer og HashMap-er.

Mer om HashMap: (som oppgave 4 i kap. 9, side 197)
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.

Innstikksortering av kontoer: (læreboka side 95)
Ta utgangspunkt i følgende program (som sorterer en heltalls-array og en String-array); og lag en metode som sorterer arrayen kontoer[] fra oppgave nr. 2 (a) ovenfor alfabetisk på personnavn. 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 nr. 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.  Dette er en redigert utgave av
    metoden ovenfor som jobber med String-array i stedet for int-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, 12, 8, 1, 10 };
	Innstikksort.sorter(a);
	for (int i = 0; i < a.length; i++) {
	    System.out.println("a[" + i + "] = " + a[i]);
	}

	String[] navn = { "Ola", "Kari", "Arne", "Eli" };
	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] = 3
a[2] = 8
a[3] = 10
a[4] = 12
navn[0] = Arne
navn[1] = Eli
navn[2] = Kari
navn[3] = Ola

Javadoc
Du kan finne offisielle eksempler på javadoc-kommentarer her og her. Se på noen av disse eksemplene, og skriv lignende kommentarer i din Oblig 3 eller 4. 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, og åpne til slutt den genererte index.html-filen i en browser for å se på resultatet:
```
> javadoc -package Programnavn.java
> firefox index.html &
```
Kort og Kortstokk
Programmer enum Type, som kan være Hjerter, Ruter, Spar eller Kløver. Programmer også public enum Kort, som inneholder en Type og et tall mellom 1-13, og en klasse Kortstokk. Kortstokken skal ta vare på 52 Kort i en beholder (f.eks et array). Programmer en "dealer" som har en kortstokk og skal ha metoder for å kontrollere at alle spillekortene er i Kortstokken og denne skal returnere true hvis kortstokken kan brukes og false hvis kort mangler. Videre skal Dealeren ha metoder for å stokke kortstokken - dette skal da bytte om på rekkefølgen i Kortstokkens beholder (tips bruk Random.nextInt(52) for å finne ut hvilken plass) og for å dele ut kortene. Dette skal i første omgang bare skrive ut rekkefølgen av kortene til skjerm. Lag en metode i Kortstokk som oppretter sine kort og en metode bruk. Bruk random for å finne ut om noen kort blei tapt (og evt hvilke) under bruk. I såfall må du sette dette kortets plass i beholderen tom.

* STJERNEOPPGAVER

* Innstikksortering
a) Skriv en metode for å sorterte tall med innstikksortering. Innstikksortering kan du lese om i Rett på Java s. 95 (3.utgave). Test programmet ditt på en heltallsarray av passende størrelse.

b) Hvilke endringer må gjøres i metoden over for å kunne sortere strenger? Gjør disse endringene og test programmet ditt på ordene fra filen names.txt (hentet fra inf1010, v12, ob4).

Hint: String har en metode int compareTo(). Slå opp i API-et og les om denne.

c) Hvilke endringer må til for at du skal kunne sortere (andre) objekter? Skriv en klasse Person som skal kunne sammenlignes og sorter en array av Person-objekter.

Hint: skriv en compareTo() - metode i klassen Person.
* Dobbel-sortert utskrift av HashMap (veldig vanskelig!)
NB! Denne oppgaven er litt kunstig, vanligvis bruker man ikke HashMap som eneste datastruktur for å lagre data som skal sorteres. Lag en metode "void skrivSortert(HashMap register)" som skriver ut innholdet i HashMap-en fra oppgave nr. 1 (h11) ovenfor 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.

Tibakemelding om dette oppgavesettet kan du skrive i bloggen eller sende på mail til siriamj[a] ifi.uio.no