L?sningsforslag ukeoppg. 9:  25. - 29. okt (INF1000 - H?st 2010)

M?l
Forst? forskjellene mellom arrayer og HashMaper, og anvendelsesomr?dene for disse datastrukturene, og forst? hvordan innstikksortering fungerer.

Oppgaver til teoritimen

1. 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;
       }
   }
   

   a)  Ida19
   b)  Lars
       Ida
   c)  Lars:21
       Ida:24
   d)  true
   e)  1 - false
   f)  false
       true
   

   
   
   
2. 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
   

   import java.util.*;
   
   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 Bank2 {
       HashMap <String, Konto> kontoFraNavn = new HashMap <String, Konto>();
       HashMap <String, Konto> kontoer = new HashMap <String, Konto>();
   
       public static void main(String[] args) {
   	Bank2 b = new Bank2();
       }
   
       Bank2() {
           ?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);
   
           System.out.println("Antall kontoer: " + kontoer.size());
   	avsluttKonto(k);
   	System.out.println("Fins kontoen n??: " + kontoer.containsValue(k));
           System.out.println("Antall kontoer n?: " + kontoer.size());
       }
   
       void ?pneNyttKonto(int nr, String navn, int saldo) {
   	Konto k = new Konto(nr, navn, saldo);
   	kontoFraNavn.put(navn, k);
   	kontoer.put("" + nr, k);
       }
   
       Konto finnKontoFraNavn(String navn) {
   	return kontoFraNavn.get(navn);
       }
   
       Konto finnKontoFraNr(int kontonr) {
   	return kontoer.get("" + kontonr);
       }
   
       void avsluttKonto(Konto k) {
   	kontoFraNavn.remove("" + k.nr);
   	kontoer.remove("" + k.nr);
       }
   }
   
   KJ?REEKSEMPEL:
   Elins kontonr: 720020, saldo: 8000
   Kontonr. 530010 tilh?rer Nils
   Antall kontoer: 3
   Fins kontoen n??: false
   Antall kontoer n?: 2
   

   
   (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--;
   	    }
   	}
       }
   

   (L?sningsforslaget st?r i del (a) over)
   
   (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 189 i l?reboka for forskjellene mellom arrayer og HashMap-er.
   I store systemer passer det bedre ? ha personnummer som n?kkel eller noe annet som er unikt for hver verdi, i stedet for navn alene.  Verdi kan v?re et Person-objekt, som i sin tur kan ha en objektvariabel av type HashMap som refererer til alle kontoene for personen.  Hvis programmet trenger ? finne personer ut fra navn s? kan man likevel bruke navn som n?kkel i en tilleggs-HashMap, som f.eks. kan ha som verdi en HashMap over personene med det navnet.
   
   Arrayer passer best ? bruke n?r maks. antall elementer er kjent p? forh?nd, n?r vi trenger en gitt rekkef?lge p? dataene, og n?r indeksene er numeriske.  HashMap er bedre n?r maks. antall elementer er ukjent, eller man trenger ? sl? opp i dataene vha. "indekser" som er noe annet enn tall (f.eks. tekster), og n?r rekkef?lgen p? dataene ikke er avgj?rende.  Med HashMap m? dataene v?re objekter (pekere), ikke primitive typer, men det finnes objekt-typer for alle de primitive: Integer, Double, Character, Boolean.
   
   I Oblig 3 er det mest naturlig ? bruke arrayer, men man kan ogs? bruke HashMap: da kan f.eks. hele hybelnavnet v?re n?kkel.  Man trenger likevel lett tilgang til etasje- og rom-nr. s? disse kan evt. legges til som objektvariabler i Hybel.  En annen fremgangsm?te er ? ha Etasje som egen klasse og da kan denne ha en array (eller HashMap) med hyblene i etasjen.
   
   
   

3. HashMap med akronymer:  kap. 9, oppg. 2 (side 193)
   (a) Et akronym er en bokstavkombinasjon som uttrykker noe mer fullstending for eksempel FN = Forente nasjoner.  Lag et program som leser inn en rekke akronymer og deres tolkning fra fil (du finner en fil med akronymer p? bokas hjemmeside: akronymer.txt).  Legg akronymene og tolkningene i en HashMap med akronymet som n?kkel.

   Brukeren skal oppgi et akronym til programmet og f? tilbake en eller flere tolkninger av akronymet.  Det kan maksimalt v?re 10 tolkninger til hvert akronym.  Denne brukerdialogen skal g? i l?kke til brukeren svarer.

   Tips: Lag en klasse der objekter har f?lgende attributter: akronymet og en String-array med tolkninger, samt antall tolkninger.  Pekere til objekter av denne klassen legges i HashMap med akronymet som n?kkel.  Det kan v?re lurt ? lage en metode i denne klassen som legger til en ny tolkning, og som holder orden p? hvor mange tolkninger det er i ?yeblikket.

   API 	Application Programming Interface
   AV 	Audio/Video
   AV 	Authenticity Verification
   BASH 	Bourne Again Shell [Unix]
   EU 	Europaunionen
   FN 	Forente nasjoner
   ...osv...
   

   // Basert p? l?sningsforslaget i l?rebokens hjemmeside.
   /*
   * L?sning p? oppgave 2 i kapittel 9 : Akronymer
   * Programmet legges i en fil med navnet : AkronymerMain.java
   *
   * L?sningen bygger p? to klasser som begge fins i denne filen
   * Programmet forutsetter at alle akronymene st?r med store bokstaver
   * i datafilen, men brukeren trenger ikke taste de inn med store bokstaver.
   */
   
   import java.util.*; // for ? f? med HashMap
   import easyIO.*;    // for ? f? med fil- og brukerkommunikasjon
   
   class AkronymerMain {
       // initialiserer akronym-registeret
       HashMap<String, Akronym> akronymer = new HashMap<String, Akronym>();
   
       public static void main(String[] args) {
           // Oppretter et objekt av denne samme klassen for ? kunne kalle
           // objektmetoder fra denne klassemetoden vha. pekeren "am".
           AkronymerMain am = new AkronymerMain();
   
           // leser inn data fra fil og bygger opp register
           am.byggRegister();
   
           // g?r i dialog med bruker
           am.brukerdialog();
       }
   
       void byggRegister() {
           In fil = new In("akronymer.txt");
           while(!fil.endOfFile()) {
   
   	    // leser akronymet og tolkningen
   	    String akro = fil.inWord();
               String tolkning = fil.inLine().trim();
   
               // sjekker om akronymet er registrert tidligere
   	    if (akronymer.containsKey(akro)){
   
   		// vi skal n? legge til en ny tolkning
                   Akronym a = akronymer.get(akro);
                   a.add(tolkning);
   
               } else {
                   // vi lager et nytt Akronym-objekt
                   Akronym ny = new Akronym(akro,tolkning);
   
                   // vi legger det inn i akronym-registeret
                   akronymer.put(akro, ny);
               }
           }
           fil.close();
       }
   
       void brukerdialog() {
           In tastatur = new In();
           String svar;
           do {
               System.out.print("Skriv inn et akronym (avslutt med -): ");
               svar = tastatur.inLine();
               svar = svar.trim();
               svar = svar.toUpperCase();
               if (akronymer.containsKey(svar)) {
                  Akronym a = akronymer.get(svar);
                  a.skrivUt();
               } else if (!svar.equals("-")){
                  System.out.println(svar + " fins ikke i akronymregisteret.");
               }
           } while (!svar.equals("-"));
       }
   }
   
   class Akronym {
       int antall;
       String akronym;
       String[] tolkninger = new String[10];
   
       Akronym (String a, String t) {
           akronym = a;
           tolkninger[antall] = t;
           antall = 1;
       }
   
       void add(String t) {
   	if (antall < 10) {
               tolkninger[antall] = t;
               antall++;
           } else {
               System.out.println("For mange tolkninger av " + akronym);
           }
       }
   
       void skrivUt() {
          System.out.println(akronym + " kan bety:");
          for (int i = 0; i < antall; i++) {
              System.out.println("   " + tolkninger[i]);
           }
       }
   }
   

   
   

   (b) Utvid programmet slik at bruker f?r anledning til ? legge til en tolkning dersom den ikke finnes fra f?r.

            // Linje 68 i l?sningen (a) vist ovenfor:
            System.out.println(svar + " fins ikke i akronymregisteret.");
            // For ? l?se del (b) trenger vi bare legge til f?lgende to
            // linjer rett etter linje 68:
   	 System.out.print("LEGG INN TOLKNING: ");
   	 akronymer.put(svar, new Akronym(svar, tastatur.inLine()));
   

   
   
   
4. Innstikksortering av kontoer:  (l?reboka side 93)
   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
   

       /** Sorterer en Konto-array: Koden er basert p? sorter(String[] a) men
         * erstatter a[] med enten kontoer[] eller kontoer[].navn avhengig av om
         * man trenger objektet eller sorteringsnavn.  a.length -> antKontoer */
       public static void sorter(Konto[] kontoer, int antKontoer) {
   	for (int k = 0 ; k < antKontoer - 1; k++) {
   	    if (kontoer[k].navn.compareTo(kontoer[k + 1].navn) > 0 ) {
   		Konto tmp = kontoer[k + 1];
   		int i = k;
   		while (i >= 0 && (kontoer[i].navn.compareTo(tmp.navn) > 0)) {
   		    kontoer[i + 1] = kontoer[i];
   		    i--;
   		}
   		kontoer[i + 1] = tmp;
   	    }
   	}
       }
   
   

   Legger ogs? til f?lgende testkode p? slutten av konstrukt?ren til Bank:

   	// Kontosortering:
   	System.out.println("Sorterer kontoene p? navn...");
   	sorter(kontoer, antKontoer);
   	for (int i = 0; i < antKontoer; i++) {
   	    System.out.println("kontoer[" + i + "].navn = " + kontoer[i].navn
   			       + ", saldo: " + kontoer[i].saldo);
   	}
   
   KJ?REEKSEMPEL:
   Sorterer kontoene p? navn...
   kontoer[0].navn = Elin, saldo: 8000
   kontoer[1].navn = Nils, saldo: 4000
   kontoer[2].navn = Tina, saldo: 9000
   

Oppgaver til terminaltimen

1. HashMap og innstikksortering:
   (Samme oppgaver som i nr. 1, 2, og 3 for teoritimen).
   
   
   
2. Begynn med Oblig 4:
   Viktigste tema i obligen er HashMap-er, s? det kan v?re lurt ? l?se en enklere oppgave med HashMap f?r du g?r l?s p? Oblig 4, f.eks. oppgave nr. 2 eller 3 for teoritimen.

> javadoc -package Programnavn.java
> firefox index.html &