Muutamia yleishyödyllisiä tekniikoita

Tutustutaan seuraavaksi muutamaan ohjelmoinnissa varsin näppärään tekniikaan sekä luokkaan.

Säännölliset lausekkeet

Säännöllinen lauseke määrittelee joukon merkkijonoja tiiviissä muodossa. Säännöllisiä lausekkeita käytetään muunmuassa merkkijonojen oikeellisuuden tarkistamiseen. Merkkijonojen oikeellisuuden tarkastaminen tapahtuu luomalla säännöllinen lauseke, joka määrittelee merkkijonot, jotka ovat oikein.

Tarkastellaan ongelmaa, jossa täytyy tarkistaa, onko käyttäjän antama opiskelijanumero oikeanmuotoinen. Opiskelijanumero alkaa merkkijonolla "01", jota seuraa 7 numeroa väliltä 0–9.

Opiskelijanumeron oikeellisuuden voisi tarkistaa esimerkiksi käymällä opiskelijanumeroa esittävän merkkijonon läpi merkki merkiltä charAt-metodin avulla. Toinen tapa olisi tarkistaa että ensimmäinen merkki on "0", ja käyttää Integer.parseInt metodikutsua merkkijonon muuntamiseen numeroksi. Tämän jälkeen voisi tarkistaa että Integer.parseInt-metodin palauttama luku on pienempi kuin 20000000.

Oikeellisuuden tarkistus säännöllisten lausekkeiden avulla tapahtuu ensin sopivan säännöllisen lausekkeen määrittelyn. Tämän jälkeen käytetään String-luokan metodia matches, joka tarkistaa vastaako merkkijono parametrina annettua säännöllistä lauseketta. Opiskelijanumeron tapauksessa sopiva säännöllinen lauseke on "01[0-9]{7}", ja käyttäjän syöttämän opiskelijanumeron tarkistaminen käy seuraavasti:

System.out.print("Anna opiskelijanumero: ");
String numero = lukija.nextLine();

if (numero.matches("01[0-9]{7}")) {
    System.out.println("Muoto on oikea.");
} else {
    System.out.println("Muoto ei ole oikea.");
}

Käydään seuraavaksi läpi eniten käytettyjä säännöllisten lausekkeiden merkintöjä.

Vaihtoehtoisuus (pystyviiva)

Pystyviiva tarkoittaa, että säännöllisen lausekkeen osat ovat vaihtoehtoisia. Esimerkiksi lauseke 00|111|0000 määrittelee merkkijonot 00, 111 ja 0000. Metodi matches palauttaa arvon true jos merkkijono vastaa jotain määritellyistä vaihtoehdoista.

String merkkijono = "00";

if (merkkijono.matches("00|111|0000")) {
    System.out.println("Merkkijonosta löytyi joku kolmesta vaihtoehdosta");
} else {
    System.out.println("Merkkijonosta ei löytynyt yhtäkään vaihtoehdoista");
}

Merkkijonosta löytyi joku kolmesta vaihtoehdosta

Säännöllinen lauseke 00|111|0000 vaatii että merkkijono on täsmälleen määritellyn muotoinen: se ei määrittele "contains"-toiminnallisuutta.

String merkkijono = "1111";

if (merkkijono.matches("00|111|0000")) {
    System.out.println("Merkkijonosta löytyi joku kolmesta vaihtoehdosta");
} else {
    System.out.println("Merkkijonosta ei löytynyt yhtäkään vaihtoehdoista");
}

Merkkijonosta ei löytynyt yhtäkään vaihtoehdoista

Merkkijonon osaan rajattu vaikutus (sulut)

Sulkujen avulla voi määrittää, mihin säännöllisen lausekkeen osaan sulkujen sisällä olevat merkinnät vaikuttavat. Jos haluamme sallia merkkijonot 00000 ja 00001, voimme määritellä ne pystyviivan avulla muodossa 00000|00001. Sulkujen avulla voimme rajoittaa vaihtoehtoisuuden vain osaan merkkijonoa. Lauseke 0000(0|1) määrittelee merkkijonot 00000 ja 00001.

Vastaavasti säännöllinen lauseke auto(|n|a) määrittelee sanan auto yksikön nominatiivin (auto), genetiivin (auton), partitiivin (autoa) ja akkusatiivin (auto tai auton).

System.out.print("Kirjoita joku sanan auto yksikön taivutusmuoto: ");
String sana = lukija.nextLine();

if (sana.matches("auto(|n|a|ssa|sta|on|lla|lta|lle|na|ksi|tta)")) {
    System.out.println("Oikein meni! RRrakastan tätä kieltä!");
} else {
    System.out.println("Taivutusmuoto ei ole oikea.");
}

Toistomerkinnät

Usein halutaan, että merkkijonossa toistuu jokin tietty alimerkkijono. Säännöllisissä lausekkeissa on käytössä seuraavat toistomerkinnät:

• Merkintä * toisto 0... kertaa, esim
  

  String merkkijono = "trolololololo";
  
  if (merkkijono.matches("trolo(lo)*")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto on oikea.
  

• Merkintä + toisto 1... kertaa, esim
  

  String merkkijono = "trolololololo";
  
  if (merkkijono.matches("tro(lo)+")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto on oikea.
  

  String merkkijono = "nänänänänänänänä Bätmään!";
  
  if (merkkijono.matches("(nä)+ Bätmään!")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto on oikea.
  

• Merkintä ? toisto 0 tai 1 kertaa, esim
  

  String merkkijono = "You have to accidentally the whole meme";
  
  if (merkkijono.matches("You have to accidentally (delete )?the whole meme")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto on oikea.
  

• Merkintä {a} toisto a kertaa, esim
  

  String merkkijono = "1010";
  
  if (merkkijono.matches("(10){2}")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto on oikea.
  

• Merkintä {a,b} toisto a ... b kertaa, esim
  

  String merkkijono = "1";
  
  if (merkkijono.matches("1{2,4}")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto ei ole oikea.
  

• Merkintä {a,} toisto a ... kertaa, esim
  

  String merkkijono = "11111";
  
  if (merkkijono.matches("1{2,}")) {
      System.out.println("Muoto on oikea.");
  } else {
      System.out.println("Muoto ei ole oikea.");
  }
  

  Muoto on oikea.
  

Samassa säännöllisessä lausekkeessa voi käyttää myös useampia toistomerkintöjä. Esimerkiksi säännöllinen lauseke 5{3}(1|0)*5{3} määrittelee merkkijonot, jotka alkavat ja loppuvat kolmella vitosella. Välissä saa tulla rajaton määrä ykkösiä ja nollia.

Merkkiryhmät (hakasulut)

Merkkiryhmän avulla voi määritellä lyhyesti joukon merkkejä. Merkit kirjoitetaan hakasulkujen sisään, ja merkkivälin voi määrittää viivan avulla. Esimerkiksi merkintä [145] tarkoittaa samaa kuin (1|4|5) ja merkintä [2-36-9] tarkoittaa samaa kuin (2|3|6|7|8|9). Vastaavasti merkintä [a-c]* määrittelee säännöllisen lausekkeen, joka vaatii että merkkijono sisältää vain merkkejä a, b ja c.

Anna merkkijono: ti
Muoto on oikea.

Anna merkkijono: abc
Muoto ei ole oikea.

Anna merkkijono: aie
Muoto on oikea.

Anna merkkijono: ane
Muoto ei ole oikea.

Anna merkkijono: 17:23:05
Muoto on oikea.

Anna merkkijono: abc
Muoto ei ole oikea.

Anna merkkijono: 33:33:33
Muoto ei ole oikea.

Nykyään lähes kaikista ohjelmointikielistä löytyy tuki säännöllisille lausekkeille. Säännöllisten lausekkeiden teoriaa tarkastellaan muunmuassa kurssilla Laskennan mallit. Lisää säännöllisistä lausekkeista löydät esim. googlaamalla hakusanalla regular expressions java -- kannattaa myös lukea Codinghorror-blogin lyhyt artikkeli Regex use vs. Regex abuse.

Lueteltu tyyppi eli Enum

Jos tiedämme muuttujien mahdolliset arvot ennalta, voimme käyttää niiden esittämiseen enum-tyyppistä luokkaa eli lueteltua tyyppiä. Luetellut tyypit ovat oma luokkatyyppinsä rajapinnan ja normaalin luokan lisäksi. Lueteltu tyyppi määritellään avainsanalla enum. Esimerkiksi seuraava Maa-enumluokka määrittelee neljä vakioarvoa: RUUTU, PATA, RISTI ja HERTTA.

public enum Maa {
    RUUTU, PATA, RISTI, HERTTA
}

Yksinkertaisimmassa muodossaan enum luettelee pilkulla erotettuina määrittelemänsä vakioarvot. Lueteltujen tyyppien arvot eli vakiot on yleensä tapana kirjoittaa kokonaan isoin kirjaimin.

Enum luodaan (yleensä) omaan tiedostoon, samaan tapaan kuin luokka tai rajapinta. NetBeansissa Enumin saa luotua valitsemalla projektin kohdalla new/other/java/java enum.

Seuraavassa luokka Kortti jossa maa esitetään enumin avulla:

public class Kortti {

    private int arvo;
    private Maa maa;

    public Kortti(int arvo, Maa maa) {
        this.arvo = arvo;
        this.maa = maa;
    }

    @Override
    public String toString() {
        return maa + " " + arvo;
    }

    public Maa getMaa() {
        return maa;
    }

    public int getArvo() {
        return arvo;
    }
}

Korttia käytetään seuraavasti:

Kortti eka = new Kortti(10, Maa.HERTTA);

System.out.println(eka);

if (eka.getMaa() == Maa.PATA) {
    System.out.println("on pata");
} else {
    System.out.println("ei ole pata");
}

Tulostuu:

HERTTA 10
ei ole pata

Huomaamme, että enumin tunnukset tulostuvat mukavasti! Koska kortin maat ovat nyt tyyppiä Maa ei ylemmän esimerkin "järjenvastaiset" kummallisuudet, esim. "maan korottaminen toiseen potenssiin" onnistu. Oraclella on enum-tyyppiin liittyvä sivusto osoitteessa http://docs.oracle.com/javase/tutorial/java/javaOO/enum.html.

public enum Maa {
    RUUTU, PATA, RISTI, HERTTA
}

System.out.println(Maa.RUUTU.ordinal());
System.out.println(Maa.HERTTA.ordinal());

0
3

Lueteltujen tyyppien oliomuuttujat

Luetellut tyypit voivat sisältää oliomuuttujia. Oliomuuttujien arvot tulee asettaa luetellun tyypin määrittelevän luokan sisäisessä eli näkyvyysmääreen private omaavassa konstruktorissa. Enum-tyyppisillä luokilla ei saa olla public-konstruktoria.

Seuraavassa lueteltu tyyppi Vari, joka sisältää vakioarvot PUNAINEN, VIHREA ja SININEN. Vakioille on määritelty värikoodin kertova oliomuuttuja:

public enum Vari {
    // konstruktorin parametrit määritellään vakioarvoja lueteltaessa
    PUNAINEN("#FF0000"),
    VIHREA("#00FF00"),
    SININEN("#0000FF");

    private String koodi;        // oliomuuttuja

    private Vari(String koodi) { // konstruktori
        this.koodi = koodi;
    }

    public String getKoodi() {
        return this.koodi;
    }
}

Lueteltua tyyppiä Vari voidaan käyttää esimerkiksi seuraavasti:

System.out.println(Vari.VIHREA.getKoodi());

#00FF00

Iteraattori

Tarkastellaan seuraavaa luokkaa Kasi, joka mallintaa tietyssä korttipelissä pelaajan kädessä olevien korttien joukkoa:

public class Kasi {
    private List<Kortti> kortit;

    public Kasi() {
        this.kortit = new ArrayList<>();
    }

    public void lisaa(Kortti kortti) {
        this.kortit.add(kortti);
    }

    public void tulosta() {
        this.kortit.stream().forEach(kortti -> {
            System.out.println(kortti);
        });
    }
}

Luokan metodi tulosta tulostaa jokaisen kädessä olevan kortin.

ArrayList ja muut Collection-rajapinnan toteuttavat "oliosäiliöt" toteuttavat rajapinnan Iterable, ja ne voidaan käydä läpi myös käyttäen iteraattoria, eli olioa, joka on varta vasten tarkoitettu tietyn oliokokoelman läpikäyntiin. Seuraavassa on iteraattoria käyttävä versio korttien tulostamisesta:

public void tulosta() {
    Iterator<Kortti> iteraattori = kortit.iterator();

    while (iteraattori.hasNext()) {
        System.out.println(iteraattori.next());
    }
}

Iteraattori pyydetään kortteja sisältävältä listalta kortit. Iteraattori on ikäänkuin "sormi", joka osoittaa aina tiettyä listan sisällä olevaa olioa, ensin ensimmäistä ja sitten seuraavaa jne... kunnes "sormen" avulla on käyty jokainen olio läpi.

Iteraattori tarjoaa muutaman metodin. Metodilla hasNext() kysytään onko läpikäytäviä olioita vielä jäljellä. Jos on, voidaan iteraattorilta pyytää seuraavana vuorossa oleva olio metodilla next(). Metodi siis palauttaa seuraavana läpikäyntivuorossa olevan olion ja laittaa iteraattorin eli "sormen" osoittamaan seuraavana vuorossa olevaa läpikäytävää olioa.

Iteraattorin next-metodin palauttama olioviite voidaan ottaa toki talteen myös muuttujaan, eli metodi tulosta voitaisiin muotoilla myös seuraavasti.

public void tulosta(){
    Iterator<Kortti> iteraattori = kortit.iterator();

    while (iteraattori.hasNext()) {
        Kortti seuraavanaVuorossa = iteraattori.next();
        System.out.println(seuraavanaVuorossa);
    }
}

Tarkastellaan seuraavaksi yhtä iteraattorin käyttökohdetta. Motivoidaan käyttökohde ensin ongelmallisella lähestymistavalla. Yritämme tehdä virran avulla metodia, joka poistaa käsiteltävästä virrasta ne kortit, joiden arvo on annettua arvoa pienempi.

public class Kasi {
    // ...

    public void poistaHuonommat(int arvo) {
        this.kortit.stream().forEach(kortti -> {
            if (kortti.getArvo() < arvo) {
                kortit.remove(kortti);
            }
        });
    }
}

Metodin suoritus aiheuttaa ongelman.

Exception in thread "main" java.util.ConcurrentModificationException
at ...
Java Result: 1

Virheen syynä on se, että listan läpikäynti forEach-metodilla olettaa, ettei listaa muokata läpikäynnin yhteydessä. Listan muokkaaminen (eli tässä tapauksessa alkion poistaminen) aiheuttaa virheen -- voimme ajatella, että komento forEach menee tästä "sekaisin".

Jos listalta halutaan poistaa osa olioista läpikäynnin aikana osa, tulee tämä tehdä iteraattoria käyttäen. Iteraattori-olion metodia remove kutsuttaessa listalta poistetaan siististi se alkio jonka iteraattori palautti edellisellä metodin next kutsulla. Toimiva versio metodista seuraavassa:

public class Kasi {
    // ...

    public void poistaHuonommat(int arvo) {
        Iterator<Kortti> iteraattori = kortit.iterator();

        while (iteraattori.hasNext()) {
            if (iteraattori.next().getArvo() < arvo) {
                // poistetaan listalta olio jonka edellinen next-metodin kutsu palautti
                iteraattori.remove();
            }
        }
    }
}

Henkilo vilma = new Henkilo("Vilma", Koulutus.FT);
System.out.println(vilma);

Vilma, FT

Tyontekijat yliopisto = new Tyontekijat();
yliopisto.lisaa(new Henkilo("Petrus", Koulutus.FT));
yliopisto.lisaa(new Henkilo("Arto", Koulutus.FilYO));
yliopisto.lisaa(new Henkilo("Elina", Koulutus.FT));

yliopisto.tulosta();

yliopisto.irtisano(Koulutus.FilYO);

System.out.println("==");

yliopisto.tulosta();

Petrus, FT
Arto, FilYO
Elina, FT
==
Petrus, FT
Elina, FT

Kortti eka = new Kortti(2, Maa.RUUTU);
Kortti toka = new Kortti(14, Maa.PATA);
Kortti kolmas = new Kortti(12, Maa.HERTTA);

System.out.println(eka);
System.out.println(toka);
System.out.println(kolmas);

RUUTU 2
PATA A
HERTTA Q

Kasi kasi = new Kasi();

kasi.lisaa(new Kortti(2, Maa.RUUTU));
kasi.lisaa(new Kortti(14, Maa.PATA));
kasi.lisaa(new Kortti(12, Maa.HERTTA));
kasi.lisaa(new Kortti(2, Maa.PATA));

kasi.tulosta();

RUUTU 2
PATA A
HERTTA Q
PATA 2

Kasi kasi = new Kasi();

kasi.lisaa(new Kortti(2, Maa.RUUTU));
kasi.lisaa(new Kortti(14, Maa.PATA));
kasi.lisaa(new Kortti(12, Maa.HERTTA));
kasi.lisaa(new Kortti(2, Maa.PATA));

kasi.jarjesta();

kasi.tulosta();

RUUTU 2
PATA 2
HERTTA Q
PATA A

Kasi kasi1 = new Kasi();

kasi1.lisaa(new Kortti(2, Maa.RUUTU));
kasi1.lisaa(new Kortti(14, Maa.PATA));
kasi1.lisaa(new Kortti(12, Maa.HERTTA));
kasi1.lisaa(new Kortti(2, Maa.PATA));

Kasi kasi2 = new Kasi();

kasi2.lisaa(new Kortti(11, Maa.RUUTU));
kasi2.lisaa(new Kortti(11, Maa.PATA));
kasi2.lisaa(new Kortti(11, Maa.HERTTA));

int vertailu = kasi1.compareTo(kasi2);

if (vertailu < 0) {
    System.out.println("arvokkaampi käsi sisältää kortit");
    kasi2.tulosta();
} else if (vertailu > 0){
    System.out.println("arvokkaampi käsi sisältää kortit");
    kasi1.tulosta();
} else {
    System.out.println("kädet yhtä arvokkaat");
}

arvokkaampi käsi sisältää kortit
RUUTU J
PATA J
HERTTA J

import java.util.Comparator;

public class SamatMaatVierekkain implements Comparator<Kortti> {
    public int compare(Kortti k1, Kortti k2) {
        return k1.getMaa().ordinal() - k2.getMaa().ordinal();
    }
}

ArrayList<Kortti> kortit = new ArrayList<>();

kortit.add(new Kortti(3, Maa.PATA));
kortit.add(new Kortti(2, Maa.RUUTU));
kortit.add(new Kortti(14, Maa.PATA));
kortit.add(new Kortti(12, Maa.HERTTA));
kortit.add(new Kortti(2, Maa.PATA));

SamatMaatVierekkain samatMaatVierekkainJarjestaja = new SamatMaatVierekkain();
Collections.sort(kortit, samatMaatVierekkainJarjestaja);

kortit.stream().forEach(k -> System.out.println(k));

RUUTU 2
HERTTA Q
PATA 3
PATA A
PATA 2

Collections.sort(kortit, new SamatMaatVierekkain());

Collections.sort(kortit, (k1, k2) -> k1.getMaa().ordinal() - k2.getMaa().ordinal());

Kasi kasi = new Kasi();

kasi.lisaa(new Kortti(12, Maa.HERTTA));
kasi.lisaa(new Kortti(4, Maa.PATA));
kasi.lisaa(new Kortti(2, Maa.RUUTU));
kasi.lisaa(new Kortti(14, Maa.PATA));
kasi.lisaa(new Kortti(7, Maa.HERTTA));
kasi.lisaa(new Kortti(2, Maa.PATA));

kasi.jarjestaMaittain();

kasi.tulosta();

RUUTU 2
HERTTA 7
HERTTA Q
PATA 2
PATA 4
PATA A

Tiedostoon kirjoittaminen

Olemme aiemmin oppineet menetelmiä tekstitiedostojen ja muiden lähteiden lukemiseen. Tarkastellaan seuraavaksi tiedostoon kirjoittamista.

Luokka PrintWriter tarjoaa toiminnallisuuden tiedostoon kirjoittamiseen. Luokan PrintWriter konstruktorille annetaan parametrina kohdetiedoston sijaintia kuvaava merkkijono.

PrintWriter kirjoittaja = new PrintWriter("tiedosto.txt");
kirjoittaja.println("Hei tiedosto!"); // kirjoittaa tiedostoon merkkijonon "Hei tiedosto!" sekä rivinvaihdon
kirjoittaja.println("Lisää tekstiä");
kirjoittaja.print("Ja vielä lisää"); // kirjoittaa tiedostoon merkkijonon "ja vielä lisää" ilman rivinvaihtoa
kirjoittaja.close(); // sulkee tiedoston ja varmistaa että kirjoitettu teksti menee tiedostoon

Esimerkissä kirjoitetaan tiedostoon "tiedosto.txt" merkkijono "Hei tiedosto!", jota seuraa rivinvaihto, ja vielä hieman lisää tekstiä. Huomaa että tiedostoon kirjoitettaessa metodi print ei lisää rivinvaihtoja, vaan ne tulee lisätä itse. Metodi println lisää myös rivinvaihdot.

PrintWriter-luokan konstruktori heittää mahdollisesti poikkeuksen, joka tulee joko käsitellä tai siirtää kutsuvan metodin vastuulle. Metodi, jolle annetaan parametrina kirjoitettavan tiedoston nimi ja kirjoitettava sisältö voisi näyttää seuraavalta.

public class Tallentaja {

    public void kirjoitaTiedostoon(String tiedostonNimi, String teksti) throws Exception {
        PrintWriter kirjoittaja = new PrintWriter(tiedostonNimi);
        kirjoittaja.println(teksti);
        kirjoittaja.close();
    }
}

Yllä olevassa kirjoitaTiedostoon-metodissa luodaan ensin PrintWriter-olio, joka kirjoittaa parametrina annetussa sijainnissa sijaitsevaan tiedostoon tiedostonNimi. Tämän jälkeen kirjoitetaan tiedostoon println-metodilla. Konstruktorin mahdollisesti heittämä poikkeus tulee käsitellä joko try-catch-lohkolla tai siirtämällä poikkeuksen käsittelyvastuuta eteenpäin. Metodissa kirjoitaTiedostoon käsittelyvastuu on siirretty eteenpäin.

Luodaan main-metodi jossa kutsutaan Tallentaja-olion kirjoitaTiedostoon-metodia. Poikkeusta ei ole pakko käsitellä main-metodissakaan, vaan se voi ilmoittaa heittävänsä mahdollisesti poikkeuksen määrittelyllä throws Exception.

public static void main(String[] args) throws Exception {
    Tallentaja tallentaja = new Tallentaja();
    tallentaja.kirjoitaTiedostoon("paivakirja.txt", "Rakas päiväkirja, tänään oli kiva päivä.");
}

Yllä olevaa metodia kutsuttaessa luodaan tiedosto "paivakirja.txt" johon kirjoitetaan teksti "Rakas päiväkirja, tänään oli kiva päivä.". Jos tiedosto on jo olemassa, pyyhkiytyy vanhan tiedoston sisältö uutta kirjoittaessa.

Mikäli tiedostoja haluaa käsitellä siten, että kirjoitus tapahtuu olemassaolevan tiedoston perään, kannattaa kirjoituksessa käyttää FileWriter-luokkaa.

MuistavaSanakirja sanakirja = new MuistavaSanakirja();
sanakirja.lisaa("apina", "monkey");
sanakirja.lisaa("banaani", "banana");
sanakirja.lisaa("apina", "apfe");

System.out.println(sanakirja.kaanna("apina"));
System.out.println(sanakirja.kaanna("monkey"));
System.out.println(sanakirja.kaanna("ohjelmointi"));
System.out.println(sanakirja.kaanna("banana"));

monkey
apina
null
banaani

MuistavaSanakirja sanakirja = new MuistavaSanakirja();
sanakirja.lisaa("apina", "monkey");
sanakirja.lisaa("banaani", "banana");
sanakirja.lisaa("ohjelmointi", "programming");
sanakirja.poista("apina");
sanakirja.poista("banana");

System.out.println(sanakirja.kaanna("apina"));
System.out.println(sanakirja.kaanna("monkey"));
System.out.println(sanakirja.kaanna("banana"));
System.out.println(sanakirja.kaanna("banaani"));
System.out.println(sanakirja.kaanna("ohjelmointi"));

null
null
null
null
programming

apina:monkey
alla oleva:below
olut:beer

Scanner tiedostonLukija = new ...
while (tiedostonLukija.hasNextLine()) {
    String rivi = tiedostonLukija.nextLine();
    String[] osat = rivi.split(":");   // pilkotaan rivi :-merkkien kohdalta

    System.out.println(osat[0]);     // ennen :-merkkiä ollut osa rivistä
    System.out.println(osat[1]);     // :-merkin jälkeen ollut osa rivistä
}

MuistavaSanakirja sanakirja = new MuistavaSanakirja("src/sanat.txt");
boolean onnistui = sanakirja.lataa();

if (onnistui) {
    System.out.println("sanakirjan lataaminen onnistui");
}

System.out.println(sanakirja.kaanna("apina"));
System.out.println(sanakirja.kaanna("ohjelmointi"));
System.out.println(sanakirja.kaanna("alla oleva"));

sanakirjan lataaminen onnistui
monkey
null
below

tietokone:computer

computer:tietokone

MuistavaSanakirja sanakirja = new MuistavaSanakirja("src/sanat.txt");
sanakirja.lataa();

// käytä sanakirjaa

sanakirja.tallenna();

Vielä muutamia juttuja testaamisesta

Materiaalin aiemmissa osissa käsiteltiin yksikkötestausta: Yksikkötestauksella tarkoitetaan lähdekoodiin kuuluvien yksittäisten osien kuten luokkien ja niiden tarjoamien metodien testaamista. Luokkien ja metodien rakenteen suunnittelussa käytettävän ohjesäännön -- jokaisella metodilla ja luokalla tulee olla yksi selkeä vastuu -- noudattamisen tai siitä poikkeamisen huomaa testejä kirjoittaessa. Mitä useampi vastuu metodilla on, sitä monimutkaisempi testi on. Jos laaja sovellus on kirjoitettu yksittäiseen metodiin, on testien kirjoittaminen sitä varten erittäin haastavaa ellei jopa mahdotonta. Vastaavasti, jos sovellus on pilkottu selkeisiin luokkiin ja metodeihin, on testienkin kirjoittaminen suoraviivaista.

Yksikkötestien hyvyyttä voi miettiä testikattavuuden kannalta. Testikattavuudella tarkoitetaan sitä, kuinka hyvin testit käsittelevät ohjelman eri mahdollisuudet.

Alla olevassa esimerkissä testikattavuus ei ole kovin hyvä. Metodissa on kaksi vaihtoehtoista suorituspolkua, mutta testit tarkastelevat niistä vain toista.

public class Esimerkki {
    public static String testattava(int luku) {
        if (luku > 10) {
            return "alle kymmenen";
        } else {
            return "kymmenen tai yli";
        }
    }
}

public class EsimerkkiTest {

    @Test
    public void testaaAlleKymmenen() {
        assertEquals("alle kymmenen", Esimerkki.testattava(1));
    }
}

Yllä olevassa esimerkissä testin syöte ei myöskään ole ideaali. Mikäli ohjelmassa on ehto, kannattaa testissa tarkastella ehdon toimivuutta satunnaisen testisyötteen sijaan. Testeissä on hyvä tarkastella ns "corner caseja", eli niitä kohtia, joissa toiminnallisuuden pitäisi muuttua. Yllä olevaa metodi kannattaisi siis tarkastella ainakin syötteillä 9 ja 10.

public class EsimerkkiTest {

    @Test
    public void testaaAlleKymmenen() {
        assertEquals("alle kymmenen", Esimerkki.testattava(9));
    }

    @Test
    public void testaaAlleKymmenen() {
        assertEquals("kymmenen tai yli", Esimerkki.testattava(10));
    }
}

Yllä testit ovat kattavat ja käsittelevät oletetut corner caset.

System.out.println(Ohjelma.suorita(new Scanner("3\n2\n1\n-1\n")));

Pulloja: 6
Oppilaita: 3
Keskiarvo: 2.0

System.out.println(Ohjelma.suorita(new Scanner("1\n0\n-55\n-1\n")));

Pulloja: 1
Oppilaita: 2
Keskiarvo: 0.5

System.out.println(Ohjelma.suorita(new Scanner("-55\n-1\n")));

Pulloja: 0
Oppilaita: 0
Keskiarvoa ei voida laskea

Crowdsorcerer: Arvioi tehtäviä

Otetaan hetkeksi askel taaksepäin ja tarkastellaan taas itse tehtyjä tehtäviä. Ohjelmointikurssin yhdennessätoista osassa loimme vapaamuotoisen tehtävän Crowdsorcererin avulla. Nyt on hetki vertaisarviointiin -- arvioimme Crowdsorcereriin lähetettyjä tehtäviä! Anna vertaispalautetta kahdesta jonkun toisen kurssilaisen lähettämästä tehtävästä ja arvioi lopuksi itse tekemääsi tehtävää. Itse tekemäsi tehtävä näkyy vain jos olet tehnyt sen -- jos et tehnyt tehtävää, pääset arvioimaan yhden ylimääräisen tehtävän.

ArrayList ja Hajautustaulu

ArrayList ja Hajautustaulu ovat ohjemoinnissa hyvin yleisesti käytettyjä tietorakenteita. Tarkastellaan tässä niiden todellista toteutusta -- alla rakennetaan askeleittain ensin ArrayListiä imitoiva tietorakenne Lista, jota hyödynnetään sitten tietorakenteen Hajautustaulu tekemisessä.

Geneerinen tyyppi

Olemme listoihin tutustumisesta lähtien kertoneet erilaisille tietorakenteille niiden sisältämän arvon tyypin. Esimerkiksi String-tyyppisiä olioita sisältävä lista on esitelty muodossa ArrayList<String>. Tässä on kuitenkin ihmetyttänyt se, että miten ihmeessä listat ja muutkin tietorakenteet voivat sisältää erityyppisiä oliota.

Geneerisyys (generics) liittyy olioita säilövien luokkien tapaan säilöä vapaavalintaisen tyyppisiä olioita. Vapaavalintaisuus perustuu luokkien määrittelyssä käytettyyn geneeriseen tyyppiparametriin, jonka avulla voidaan määritellä olion luontivaiheessa valittavia tyyppejä. Luokan geneerisyys määritellään antamalla luokan nimen jälkeen haluttu määrä luokan tyyppiparametreja pienempi kuin ja suurempi kuin -merkkien väliin. Toteutetaan oma geneerinen luokka Lokero, johon voi asettaa yhden minkälaisen tahansa olion.

public class Lokero<T> {
    private T alkio;

    public void asetaArvo(T alkio) {
        this.alkio = alkio;
    }

    public T haeArvo() {
        return alkio;
    }
}

Määrittely public class Lokero<T> kertoo että luokalle Lokero tulee antaa konstruktorissa tyyppiparametri. Konstruktorikutsun jälkeen kaikki olion sisäiset muuttujat tulevat olemaan kutsun yhteydessä annettua tyyppiä. Luodaan merkkijonon tallentava lokero.

Lokero<String> merkkijono = new Lokero<>();
merkkijono.asetaArvo(":)");

System.out.println(merkkijono.haeArvo());

:)

Yllä olevalla ohjelmalla merkkijono-nimisen Lokero-olion ajonaikainen toteutus on seuraavanlainen.

public class Lokero<String> {
    private String alkio;

    public void asetaArvo(String alkio) {
        this.alkio = alkio;
    }

    public String haeArvo() {
        return alkio;
    }
}

Tyyppiparametria vaihtamalla voidaan luoda myös muuntyyppisiä olioita tallentavia Lokero-olioita. Esimerkiksi kokonaisluvun saa tallennettua seuraavasti.

Lokero<Integer> luku = new Lokero<>();
luku.asetaArvo(5);

System.out.println(luku.haeArvo());

5

Yllä olevalla esimerkillä luku-nimisen Lokeron toteutus olisi ajonaikaisesti taas seuraavanlainen.

public class Lokero<Integer> {
    private Integer alkio;

    public void asetaArvo(Integer alkio) {
        this.alkio = alkio;
    }

    public Integer haeArvo() {
        return alkio;
    }
}

Samalla tavalla ohjelmoija voisi toteuttaa esimerkiksi luokan Pari, mihin voi laittaa kaksi halutun tyyppistä oliota.

public class Pari<T, K> {
    private T eka;
    private K toka;

    public void asetaArvot(T eka, K toka) {
        this.eka = eka;
        this.toka = toka;
    }

    public T haeEka() {
        return this.eka;
    }

    public K haeToka() {
        return this.toka;
    }
}

Huomattava osa Javan tietorakenteista mahdollistaa eri tyyppisten muuttujien käytön. Esimerkiksi ArrayList saa yhden tyyppiparametrin, HashMap kaksi.

List<String> merkkijonot = new ArrayList<>();
Map<String, String> avainArvoParit = new HashMap<>();

Jatkossa kun näet esimerkiksi tyypin ArrayList<String> tiedät että sen sisäisessä rakenteessa on käytetty geneeristä tyyppiparametria. Sama periaate löytyy esimerkiksi rajapinnassa Comparable.

Listarakenne

Tarkastellaan erästä tapaa Javan tarjoaman ArrayList-tietorakenteen toteuttamiseen. Javan ArrayList hyödyntää sisäisesti taulukkoa, mikä on määritelty generisen tyyppiseksi -- tämän takia listalle saa lisätä käytännössä minkä tyyppisiä arvoja tahansa. Lista tarjoaa useita metodeja, joista tämän esimerkin kannalta oleellisia ovat add eli lisääminen, contains eli olemassaolon tarkastaminen, remove eli poistaminen sekä get, eli tietystä indeksistä hakeminen.

ArrayList<String> merkkijonot = new ArrayList<>();
System.out.println(merkkijonot.contains("Hei!"));
merkkijonot.add("Hei!");
System.out.println(merkkijonot.contains("Hei!"));
merkkijonot.remove("Hei!");
System.out.println(merkkijonot.contains("Hei!"));

false
true
false

Listan luominen

Luodaan luokka Lista. Listarakenne sisältää geneerisen taulukon -- eli taulukon, jonka alkioiden tyyppi määräytyy ajonaikaisesti tyyppiparametreista. Asetetaan taulukon alkukooksi 10.

public class Lista<T> {
    private T[] arvot;

    public Lista() {
        this.arvot = (T[]) new Object[10];
    }
}

Lista kapseloi taulukon. Alkutilanteessa jokainen taulukon indeksi sisältää null-viitteen.

Arvojen lisääminen listalle

Lisätään luokalle metodi public void lisaa(T arvo), mikä mahdollistaa arvojen lisäämisen listalle. Luodaan luokalle tätä varten erillinen kokonaislukumuuttuja, joka pitää kirjaa taulukon ensimmäisestä tyhjästä paikasta.

public class Lista<T> {

    private T[] arvot;
    private int arvoja;

    public Lista() {
        this.arvot = (T[]) new Object[10];
        this.arvoja = 0;
    }

    public void lisaa(T arvo) {
        this.arvot[this.arvoja] = arvo;
        this.arvoja++;
    }
}

Nyt arvojen lisääminen listalle onnistuu -- tai, ainakin listan luominen ja metodin kutsuminen onnistuu -- emme vielä voi testata ovatko arvot todellisuudessa listalla.

Lista<String> lista = new Lista<>();
lista.lisaa("hei");
lista.lisaa("maailma");

Arvojen lisääminen listalle, osa 2

Edellä kuvatussa lisaa-metodissa on pieni ongelma. Ongelma ilmenee kun seuraava ohjelmakoodi suoritetaan.

Lista<String> lista = new Lista<>();
for (int i = 0; i < 11; i++) {
    lista.lisaa("hei");
}

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at tietorakenteita.Lista.lisaa(Lista.java:14)
at tietorakenteita.Ohjelma.main(Ohjelma.java:8)

Listan koko ei kasva. Eräs ArrayList-luokan oleellisimmista toiminnallisuuksista on se, että sen koko kasvaa aina tarvittaessa -- ohjelmoijan ei siis tarvitse varoa listan täyttymistä.

Lisätään ohjelmaan listan koon kasvattamiseen liittyvä toiminnallisuus. Listan kokoa kasvatetaan aina jos täyteen listaan yritetään lisätä arvo. Kasvattaminen toteutetaan käytännössä siten, että luomme uuden taulukon, mihin vanhan taulukon arvot kopioidaan. Tämän jälkeen vanha taulukko jätetään heitteille, ja uudesta taulukosta tulee olion käyttämä taulukko.

Javan kuudennessa versiossa uuden taulukon koko lasketaan kaavalla vanhakoko * 3 / 2 + 1. Hyödynnetään samaa kaavaa omassa toteutuksessamme. Luodaan kasvattamista varten erillinen metodi kasvata, joka on vain luokan omien metodien käytössä (eli sillä on private-näkyvyys).

private void kasvata() {
    T[] uusi = (T[]) new Object[this.arvot.length * 3 / 2 + 1];
    for (int i = 0; i < this.arvot.length; i++) {
        uusi[i] = this.arvot[i];
    }
  
    this.arvot = uusi;
}

Toteutus luo uuden taulukon, jonka koko on noin 1.5-kertainen vanhaan taulukkoon verrattuna. Tämän jälkeen kaikki vanhan taulukon alkiot kopioidaan uuteen taulukkoon ja lopulta olion arvot-muuttujan -- eli taulukon -- arvoksi asetetaan uusi taulukko.

Muokataan vielä metodia lisaa siten, että taulukon kokoa kasvatetaan tarvittaessa.

public void lisaa(T arvo) {
    if(this.arvoja == this.arvot.length) {
        kasvata();
    }
  
    this.arvot[this.arvoja] = arvo;
    this.arvoja++;
}

Nyt arvoja voi lisätä listalle lähes rajattomasti.

Arvon olemassaolon tarkastaminen

Luodaan listalle seuraavaksi metodi public boolean sisaltaa(T arvo), minkä avulla voidaan tarkistaa onko alkio listalla. Hyödynnetään tässä tietoa siitä, että jokainen Javan olio -- riippumatta sen tyypistä -- perii Object-luokan (tai on Object-tyyppinen). Tämän takia jokaisella oliolla on metodi public boolean equals(Object object), jota voidaan käyttää yhtäsuuruuden tarkasteluun.

Luokan Lista muuttuja arvoja sisältää tiedon arvojen tämän hetkisestä lukumäärästä. Voimme siis toteuttaa sisaltaa-metodin siten, että tarkastelemme vain ne listan indeksit, joissa on arvoja.

public boolean sisaltaa(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (this.arvot[i].equals(arvo)) {
            return true;
        }
    }
  
    return false;
}

Edellä esitetty menetelmä olettaa, että käyttäjä ei lisää listalle null-viitettä. Jos haluamme, että käyttäjä saa lisätä listalle null-viitteen (ja null-viitteen olemassaoloa saa myös hakea), tulee ohjelmaa muokata hieman. Tällöin sisaltaa-metodin eräs mahdollinen toteutus olisi seuraava.

public boolean sisaltaa(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            return true;
        }
    }
  
    return false;
}

Yllä oleva esimerkki ei kuitenkaan toimi. Pohdi miksei ja mieti minkälaisella ratkaisulla saisit null-viitteiden käsittelyn toimimaan.

Ohjelmassa on nyt mahdollisuus listalla olevien alkioiden olemassaolon tarkasteluun.

Lista<String> lista = new Lista<>();
System.out.println(lista.sisaltaa("hei"));
lista.lisaa("hei");
System.out.println(lista.sisaltaa("hei"));

false
true

Arvon poistaminen

Toteuttamallemme listalle voi nyt lisätä arvoja, jonka lisäksi arvon olemassaolon voi tarkastaa. Toteutetaan vielä arvon poistaminen. Toteutetaan metodi public void poista(T arvo), joka poistaa listalta yhden arvo-arvoisen alkion.

Yksinkertainen toteutus olisi seuraava.

public void poista(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            this.arvot[i] = null;
            this.arvoja--;
            return true;
        }
    }
  
    return false;
}

Yllä oleva lähestymistapa on kuitenkin ongelmallinen, sillä se jättää listalle "tyhjiä" kohtia -- olettaen, että uudet arvot lisätään aina listan loppuun.

Ongelman voi ratkaista useammalla tavalla, joista yksi on siirtää jokaista poistettua arvoa seuraavaa arvoa vasemmalle. Lisätään tämä toiminnallisuus ohjelmaan.

public void poista(T arvo) {
    boolean loytyi = false;
    for (int i = 0; i < this.arvoja; i++) {
        if (loytyi) {
            this.arvot[i - 1] = this.arvot[i];
        } else if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            this.arvoja--;
            loytyi = true;
        }
    }
}

Emme ole kovin tyytyväisiä edelliseen ratkaisuun, sillä siinä tehdään monta asiaa samaan aikaan. Metodissa sekä etsitään alkiota että siirretään alkioita. Pilkotaan toiminnallisuus kahteen erilliseen metodiin: private int arvonIndeksi(T arvo), joka etsii parametrina annetun arvon indeksin, sekä private void siirraVasemmalle(int indeksista), joka siirtää annetusta indeksistä lähtien alkioita yhden vasemmalle.

Toteutetaan ensin metodi private int arvonIndeksi(T arvo), joka etsii annetun arvon indeksin. Metodi palauttaa negatiivisen luvun mikäli arvoa ei löydy.

private int arvonIndeksi(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            return i;
        }
    }

    return -1;
}

Toteutetaan tämän jälkeen metodi private void siirraVasemmalle(int indeksistaLahtien), joka siirtää arvoja annetusta indeksistä lähtien vasemmalle.

private void siirraVasemmalle(int indeksistaLahtien) {
    for (int i = indeksistaLahtien; i < this.arvoja - 1; i++) {
        this.arvot[i] = this.arvot[i + 1];
    }
}

Nyt metodi poista voidaan toteuttaa edellisten avulla hieman selkokielisemmäksi.

public void poista(T arvo) {
    int arvonIndeksi = arvonIndeksi(arvo);
    if (arvonIndeksi < 0) {
        return; // ei löydy
    }

    siirraVasemmalle(arvonIndeksi);
    this.arvoja--;
}

Luokassa lista on vieläkin vähän toistoa. Metodi sisaltaa on hyvin samankaltainen metodin arvonIndeksi kanssa. Muokataan vielä metodia sisaltaa siten, että se toteutetaan metodin arvonIndeksi avulla.

public boolean sisaltaa(T arvo) {
    return arvonIndeksi(arvo) >= 0;
}

Nyt käytössämme on lista, joka tarjoaa metodit lisaa, sisaltaa, ja poista. Lista myös kasvaa tarvittaessa. Listan toteutusta voisi toki vielä kehittää esimerkiksi lisäämällä toiminnallisuuden, mikä pienentää listan kokoa jos arvojen määrä pienenee hyvin pieneksi.

Lista<String> lista = new Lista<>();
System.out.println(lista.sisaltaa("hei"));
lista.lisaa("hei");
System.out.println(lista.sisaltaa("hei"));
lista.poista("hei");
System.out.println(lista.sisaltaa("hei"));

false
true
false

Kohdasta hakeminen

Lisätään listalle vielä metodi public T arvo(int indeksi), joka palauttaa listan tietyssä indeksissä sijaitsevan arvon. Mikäli ohjelmoija hakee arvoa listan ulkopuolelta, heitetään virhe IndexOutOfBoundsException.

public T arvo(int indeksi) {
    if (indeksi < 0 || indeksi >= this.arvoja) {
        throw new ArrayIndexOutOfBoundsException("Indeksi " + indeksi + " alueen [0, " + this.arvoja + "[ ulkopuolella.");
    }

    return this.arvot[indeksi];
}

Metodi ei ole sellaisenaan kovin hyödyllinen, sillä ohjelmoijalla ei ole tietoa arvojen indekseistä. Muutetaan vielä metodi arvonIndeksi(T arvo) kaikkien käytettäväksi, eli vaihdetaan sen näkyvyysmääre private muotoon public.

public int arvonIndeksi(T arvo) {
    for (int i = 0; i < this.arvoja; i++) {
        if (arvo == this.arvot[i] || this.arvot[i].equals(arvo)) {
            return i;
        }
    }

    return -1;
}

Lista<String> lista = new Lista<>();
System.out.println(lista.sisaltaa("hei"));
lista.lisaa("hei");
System.out.println(lista.sisaltaa("hei"));
int indeksi = lista.arvonIndeksi("hei");
System.out.println(indeksi);
System.out.println(lista.arvo(indeksi));
lista.poista("hei");
System.out.println(lista.sisaltaa("hei"));

false
true
0
hei
false

Listan koko

Lisätään listalle vielä metodi listan koon tarkastamiseen. Listan koon saa selville muuttujasta arvoja.

public int koko() {
    return this.arvoja;
}

Nyt listan alkioiden läpikäynti onnistuu mm. for-lauseella.

Lista<String> lista = new Lista<>();
lista.lisaa("hei");
lista.lisaa("maailma");

for(int i = 0; i < lista.koko(); i++) {
    System.out.println(lista.arvo(i)); 
}

hei
maailma

Hajautustaulu

Hajautustaulu on toteutettu taulukkona, missä jokainen alkio sisältää listan. Listalle tallennetaan (avain,arvo)-pareja. Käyttäjä voi hakea hajautustaulusta arvoja avaimen perusteella, ja toisaalta käyttäjä voi lisätä hajautustauluun avain-arvo -pareja. Kukin avain voi esiintyä hajautustaulussa korkeintaan kerran.

Hajautustaulun toiminta perustuu avaimen hajautusarvoon. Kun hajautustauluun lisätään (avain,arvo)-pari, lasketaan avaimeen liittyvä hajautusarvo. Hajautusarvo määrää hajautustaulun sisäisen taulukon indeksin, missä olevaan listaan (avain,arvo)-pari lisätään.

Hahmotellaan hajautustaulun toimintaa.

Avain-arvo -pari

Luodaan ensin avain-arvo -paria kuvaava luokka Pari. Haluamme tehdä hajautustaulusta mahdollisimman yleiskäyttöisen, joten avaimen ja arvon tyyppi määrätään ajonaikaisesti. Pari sisältää avaimen ja arvon sekä niihin liittyvät get- ja set-metodit.

public class Pari<K, V> {

    private K avain;
    private V arvo;

    public Pari(K avain, V arvo) {
        this.avain = avain;
        this.arvo = arvo;
    }

    public K getAvain() {
        return avain;
    }

    public void setAvain(K avain) {
        this.avain = avain;
    }

    public V getArvo() {
        return arvo;
    }

    public void setArvo(V arvo) {
        this.arvo = arvo;
    }
}

Avain-arvo -parien luominen on suoraviivaista.

Pari<String, Integer> pari = new Pari<>("yksi", 1);
System.out.println(pari.getAvain() + " -> " + pari.getArvo());

yksi -> 1

Hajautustaulun luominen

Hajautustaulu sisältää taulukon listoja. Jokainen listan arvo on edellä kuvattu pari, joka sisältää avain-arvo -parin. Hajautustaululla on lisäksi tieto arvojen lukumäärästä.

public class Hajautustaulu<K, V> {

    private Lista<Pari<K, V>>[] arvot;
    private int arvoja;

    public Hajautustaulu() {
        this.arvot = new Lista[32];
        this.arvoja = 0;
    }
}

Arvon hakeminen

Toteutetaan ensin metodi public V hae(K avain), jota käytetään arvon hakemiseen avaimen perusteella. Metodissa lasketaan ensin avaimen hajautusarvo ja päätellään sen perusteella hajautustaulun sisäisen taulukon indeksi, mistä arvoja haetaan. Mikäli kyseisessä indeksissä ei ole listaa, ei indeksiin ole lisätty vielä yhtäkään avain-arvo -paria, eikä avaimelle ole tallennettu arvoa. Tällöin palautetaan null. Muussa tapauksessa taulukon indeksissä oleva lista käydään läpi, ja avaimen yhtäsuuruutta vertaillaan jokaiseen listan avain-arvo -parin avaimeen. Mikäli joku listalla olevista avaimista vastaa avainta, jonka perusteella arvoa haetaan, palautetaan kyseinen arvo. Muulloin avainta (ja siihen liittyvää arvoa) ei löydy, ja palautetaan arvo null.

public V hae(K avain) {
    int hajautusArvo = Math.abs(avain.hashCode() % this.arvot.length);
    if (this.arvot[hajautusArvo] == null) {
        return null;
    }
  
    Lista<Pari<K, V>> arvotIndeksissa = this.arvot[hajautusArvo];

    for (int i = 0; i < arvotIndeksissa.koko(); i++) {
        if (arvotIndeksissa.arvo(i).getAvain().equals(avain)) {
            return arvotIndeksissa.arvo(i).getArvo();
        }
    }
  
    return null;
}

Hajautustauluun lisääminen, osa 1

Toteutetaan hajautustauluun lisäämisen käytettävän metodin public void lisaa(K avain, V arvo) ensimmäinen versio. Ensimmäisessä versiossa hajautustaulun sisältämän taulukon kokoa ei kasvateta lisäyksen yhteydessä.

Metodi laskee ensin avaimelle hajautusarvon ja päättelee hajautusarvon perusteella hajautustaulun sisäisen taulukon indeksin. Jos taulukon kyseisessä indeksissä ei ole arvoa, taulukon indeksiin lisätään lista. Tämän jälkeen taulukon indeksissä oleva lista käydään läpi ja sieltä etsitään avain-arvo -paria, jonka avain vastaa lisättävän avain-arvo -parin avainta. Mikäli vastaava avain löytyy, päivitetään olemassaolevan avain-arvo -parin arvo vastaamaan uutta avainta. Muulloin listaan lisätään uusi avain-arvo -pari -- tällöin myös hajautustaulussa olevien arvojen lukumäärää kasvatetaan yhdellä.

public void lisaa(K avain, V arvo) {
    int hajautusArvo = Math.abs(avain.hashCode() % arvot.length);
    if (arvot[hajautusArvo] == null) {
        arvot[hajautusArvo] = new Lista<>();
    }

    Lista<Pari<K, V>> arvotIndeksissa = arvot[hajautusArvo];

    int indeksi = -1;
    for (int i = 0; i < arvotIndeksissa.koko(); i++) {
        if (arvotIndeksissa.arvo(i).getAvain().equals(avain)) {
            indeksi = i;
            break;
        }
    }

    if (indeksi < 0) {
        arvotIndeksissa.lisaa(new Pari<>(avain, arvo));
        this.arvoja++;
    } else {
        arvotIndeksissa.arvo(indeksi).setArvo(arvo);
    }
}

Metodi on melko monimutkainen. Pilkotaan se pienempiin osiin -- ensimmäisen osan vastuulla on avaimeen liittyvän listan hakeminen ja toisen osan vastuulla on avaimen indeksin etsiminen listalta.

private Lista<Pari<K, V>> haeAvaimeenLittyvaLista(K avain) {
    int hajautusArvo = Math.abs(avain.hashCode() % arvot.length);
    if (arvot[hajautusArvo] == null) {
        arvot[hajautusArvo] = new Lista<>();
    }

    return arvot[hajautusArvo];
}
  
private int haeAvaimenIndeksi(Lista<Pari<K, V>> lista, K avain) {
    for (int i = 0; i < lista.koko(); i++) {
        if (lista.arvo(i).getAvain().equals(avain)) {
            return i;
        }
    }

    return -1;
}

Nyt metodi public void lisaa(K avain, V arvo) voidaan toteuttaa hieman selkeämmin.

public void lisaa(K avain, V arvo) {
    Lista<Pari<K, V>> arvotIndeksissa = haeAvaimeenLittyvaLista(avain);
    int indeksi = haeAvaimenIndeksi(arvotIndeksissa, avain);
  
    if (indeksi < 0) {
        arvotIndeksissa.lisaa(new Pari<>(avain, arvo));
        this.arvoja++;
    } else {
        arvotIndeksissa.arvo(indeksi).setArvo(arvo);
    }
}

Hajautustauluun lisääminen, osa 2

Edellä kuvattu hajautustauluun lisääminen toimii osittain. Toiminnallisuuden suurin puute on se, että taulukon kokoa ei kasvateta kun arvojen määrä kasvaa liian suureksi. Lisätään ohjelmaan kasvatustoiminnallisuus, mikä tuplaa hajautustaulun sisäisen taulukon koon. Kasvatustoiminnallisuuden tulee myös sijoittaa jokainen hajautustaulussa olevan taulukon arvo uuteen taulukkoon.

Hahmotellaan kasvatustoiminnallisuuden alku. Kasvatustoiminnallisuudessa luodaan uusi taulukko, jonka koko on edelliseen verrattuna kaksinkertainen. Tämän jälkeen alkuperäinen taulukko käydään indeksi indeksiltä läpi ja olemassaolevat avain-arvo -parit kopioidaan uuteen taulukkoon. Lopulta alkuperäinen taulukko korvataan uudella taulukolla.

Alla on hahmoteltu metodin toimintaa. Kopiointia ei ole vielä toteutettu.

private void kasvata() {
    // luodaan uusi taulukko
    Lista<Pari<K, V>>[] uusi = new Lista[this.arvot.length * 2];

    for (int i = 0; i < this.arvot.length; i++) {
        // kopioidaan vanhan taulukon arvot uuteen

    }

    // korvataan vanha taulukko uudella
    this.arvot = uusi;
}

Hahmotellaan seuraavaksi metodia, joka kopioi alkuperäisen taulukon yhden indeksin sisältämän listan arvot uuteen taulukkoon. Kopioinnin yhteydessä jokaisen kopioitavan avain-arvo -parin sijainti taulukossa lasketaan uudelleen -- tämä tehdään, sillä taustalla olevan taulukon koko kasvaa ja avain-arvot -parit halutaan sijoittaa taulukkoon mahdollisimman tasaisesti.

private void kopioi(Lista<Pari<K, V>>[] uusi, int indeksista) {
    for (int i = 0; i < this.arvot[indeksista].koko(); i++) {
        Pari<K, V> arvo = this.arvot[indeksista].arvo(i);
  
        int hajautusarvo = Math.abs(arvo.getAvain().hashCode() % uusi.length);
        if(uusi[hajautusarvo] == null) {
            uusi[hajautusarvo] = new Lista<>();
        }
  
        uusi[hajautusarvo].lisaa(arvo);
    }
}

Nyt kopioi-metodia voidaan kutsua kasvata-metodista.

private void kasvata() {
    // luodaan uusi taulukko
    Lista<Pari<K, V>>[] uusi = new Lista[this.arvot.length * 2];

    for (int i = 0; i < this.arvot.length; i++) {
        // kopioidaan vanhan taulukon arvot uuteen
        kasvata(uusi, indeksista);
    }

    // korvataan vanha taulukko uudella
    this.arvot = uusi;
}

Metodissa on pieni virhe. Selvitä mistä virheessä on kyse ja korjaa se.

Lisätään lopuksi kasvatustoiminnallisuus osaksi lisäystoiminnallisuutta. Hajautustaulun kokoa kasvatetaan aina jos hajautustaulussa olevien avain-arvo -parien määrä on yli 75% taulukon koosta.

public void lisaa(K avain, V arvo) {
    Lista<Pari<K, V>> arvotIndeksissa = haeAvaimeenLittyvaLista(avain);
    int indeksi = haeAvaimenIndeksi(arvotIndeksissa, avain);

    if (indeksi < 0) {
        arvotIndeksissa.lisaa(new Pari<>(avain, arvo));
        this.arvoja++;
    } else {
        arvotIndeksissa.arvo(indeksi).setArvo(arvo);
    }

    if (1.0 * this.arvoja / this.arvot.length > 0.75) {
        kasvata();
    }
}

Poistaminen

Lisätään hajautustauluun vielä toiminnallisuus avain-arvo -parin poistamiseen avaimen perusteella. Poistotoiminnallisuus palauttaa null-arvon mikäli arvoa ei löydy, muuten metodi palauttaa poistettavaan avaimeen liittyvän arvon.

Voimme hyödyntää valmiiksi toteuttamiamme metodeja poistotoiminnallisuudessa. Selitä itsellesi (ääneen) alla olevan metodin konkreettinen toiminta.

public V poista(K avain) {
    Lista≪Pari<K, V>> arvotIndeksissa = haeAvaimeenLittyvaLista(avain);
    if (arvotIndeksissa == null || arvotIndeksissa.koko() == 0) {
        return null;
    }

    int indeksi = haeAvaimenIndeksi(arvotIndeksissa, avain);
    if (indeksi < 0) {
        return null;
    }

    Pari<K, V> pari = arvotIndeksissa.arvo(indeksi);
    arvotIndeksissa.poista(pari);
    return pari.getArvo();
}

Hakemisen tehokkuudesta

Tarkastellaan vielä hakemisen tehokkuutta listasta ja hajautustaulusta. Tehokkuusmittauksia voi tehdä metodin System.nanotime() palauttaman nanosekunteja kuvaavan arvon avulla. Ohjelma luo ensin miljoona alkiota hajautustauluun ja listaan, jonka jälkeen hajautustaulusta ja listasta etsitään tuhatta satunnaista arvoa. Noin 50% arvoista löytyy listalta ja hajautustaulusta.

Lista<String> lista = new Lista<>();
Hajautustaulu<String, String> taulu = new Hajautustaulu<>();

for (int i = 0; i < 1000000; i++) {
    lista.lisaa("" + i);
    taulu.lisaa("" + i, "" + i);
}

Lista<String> haettavat = new Lista<>();
Random arpoja = new Random();
for (int i = 0; i < 1000; i++) {
    haettavat.lisaa("" + arpoja.nextInt(2000000));
}

long listanHakuAloitus = System.nanoTime();
for (int i = 0; i < haettavat.koko(); i++) {
    lista.sisaltaa(haettavat.arvo(i));            
}
long listanHakuLopetus = System.nanoTime();
  
long hajautustaulunHakuAloitus = System.nanoTime();
for (int i = 0; i < haettavat.koko(); i++) {
    taulu.hae(haettavat.arvo(i));            
}
long hajautustaulunHakuLopetus = System.nanoTime();

  
long listanHaku = listanHakuLopetus - listanHakuAloitus;
System.out.println("Lista: haku kesti noin " + listanHaku / 1000000 + " millisekuntia (" +
    listanHaku + " nanosekuntia.)");
  
long hajautustaulunHaku = hajautustaulunHakuLopetus - hajautustaulunHakuAloitus;
System.out.println("Hajautustaulu: haku kesti noin " + hajautustaulunHaku / 1000000 +
    " millisekuntia (" + hajautustaulunHaku + " nanosekuntia.)");

Lista: haku kesti noin 6284 millisekuntia (6284420580 nanosekuntia.)
Hajautustaulu: haku kesti noin 0 millisekuntia (805106 nanosekuntia.)

Edellä kuvatut ja kursseilla käyttämämme listat ja hajautustaulut poikkeavat toki sisäiseltä toteutukselta hieman toisistaan. Ohjelmointikielten tarjoamissa tietorakenteissa on hieman enemmän erilaisia optimointeja -- näihinkin palataan myöhemmillä kursseilla. Tämän kurssin puitteissa riittää em. tietorakenteiden käyttöosaaminen sekä jonkintasoinen ymmärrys niiden tehokkuuseroista sekä käyttötapauksista.

Loppurutistus

Kurssi on melkein ohi. Tehdään lopuksi vielä muutamia laajempia tehtäviä. Lisää tehtäviä löytyy (kohta julkaistavasta) kertausosiosta.

String merkkijono = "hei kaikki siellä";
String[] palat = merkkijono.split(" ");

List<String> rivit = lueRivit("src/arviot.txt");
TunteikkaatArviot arviot = new TunteikkaatArviot(rivit);
System.out.println(arviot.sanojenLukumaara("what"));
System.out.println(arviot.sanojenLukumaara("is"));
System.out.println(arviot.sanojenLukumaara("love"));
System.out.println(arviot.sanojenLukumaara("chuck"));
System.out.println(arviot.sanojenLukumaara("norris"));
System.out.println(arviot.sanojenLukumaara("mikkihiiri"));

338
2538
172
2
1
0

1 Simply put , there should have been a more compelling excuse to pair Susan Sarandon and Goldie Hawn .
3 Definitely in the guilty pleasure B-movie category , Reign of Fire is so incredibly inane that it is laughingly enjoyable .
3 It 's an experience in understanding a unique culture that is presented with universal appeal .
0 The French director has turned out nearly 21\/2 hours of unfocused , excruciatingly tedious cinema that , half an hour in , starts making water torture seem appealing .
  

List<String> rivit = lueRivit("src/arviot.txt");
TunteikkaatArviot arviot = new TunteikkaatArviot(rivit);
System.out.println(arviot.sananTunne("poor"));
System.out.println(arviot.sananTunne("is"));
System.out.println(arviot.sananTunne("love"));
System.out.println(arviot.sananTunne("damme"));
System.out.println(arviot.sananTunne("norris"));

0.8235294117647058
2.0260047281323876
2.645348837209302
2.5
2.0

List<String> rivit = lueRivit("src/arviot.txt");
TunteikkaatArviot arviot = new TunteikkaatArviot(rivit);
System.out.println(arviot.sananTunneMerkkijonona("poor"));
System.out.println(arviot.sananTunneMerkkijonona("is"));
System.out.println(arviot.sananTunneMerkkijonona("love"));
System.out.println(arviot.sananTunneMerkkijonona("damme"));
System.out.println(arviot.sananTunneMerkkijonona("norris"));

negatiivinen
neutraali
positiivinen
positiivinen
neutraali

List<String> rivit = lueRivit("src/arviot.txt");
TunteikkaatArviot arviot = new TunteikkaatArviot(rivit);

System.out.println(arviot.lauseenTunne("unicorn is a mythical creature"));
System.out.println(arviot.lauseenTunne("chuck norris made a happy meal cry"));
System.out.println(arviot.lauseenTunne("the movie was an utter and complete failure"));

2.181146685022733
2.104368086244505
1.73662040170538

List<String> rivit = lueRivit("src/arviot.txt");
TunteikkaatArviot arviot = new TunteikkaatArviot(rivit);

System.out.println(arviot.lauseenTunneMerkkijonona("unicorn is a mythical creature"));
System.out.println(arviot.lauseenTunneMerkkijonona("chuck norris made a happy meal cry"));
System.out.println(arviot.lauseenTunneMerkkijonona("the movie was an utter and complete failure"));

positiivinen
positiivinen
negatiivinen

Sovellukset ohjelmointiympäristön ulkopuolella

Sovelluksemme ovat tähän mennessä toimineet vain ohjelmointiympäristössä. Tämä ei kuitenkaan ole käytännössä totta, sillä ohjelman käynnistäminen ohjelmointiympäristössä vastaa melko vahvasti sen käynnistämistä ohjelmointiympäristön ulkopuolella. Voimme määritellä luokan, jossa olevaa metodia public static void main käytetään ohjelman käynnistämiseen.

Oracle tarjoaa -työvälineen sovellusten paketointia varten. Osoitteessa https://docs.oracle.com/javase/8/docs/technotes/guides/deploy/packager.html on ohjeita välineen käyttöön.

Edellä mainittuja ohjeita seuraamalla voit tehdä luomistasi ohjelmista versiot, joita voit jakaa myös muille. Tietojenkäsittelytieteen opinnoissa kuten Tietokantojen perusteissa (TKT-10004) keskitytään myös verkossa toimivien sovellusten luomiseen. Juuri käymäsi kurssi on eräs esitietovaatimus näihin kursseihin.