Tehtävät
Neljännentoista osan tavoitteet

Tuntee käsitteet säännöllinen lauseke, lueteltu tyyppi, ja iteraattori, ja osaa käyttää näitä osana ohjelmia. Osaa kirjoittaa tiedostoon. Muistaa käsitteen yksikkötesti ja osaa kertoa hyvien ja huonojen yksikkötestien ominaisuuksista. Tietää miten paljon käytetyt ArrayList ja HashMap toimivat. Tietää aikaan perustuvan tavan tietorakenteiden tehokkuuden vertailuun. Tietää ohjelmoinnin jatkokurssin jälkeen otettavia kursseja.

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.

Harjoitellaan hieman säännöllisten lausekkeiden käyttöä. Tehtävissä haetut metodit tehdään luokkaan Tarkistin.

Viikonpäivä

Tee säännöllisen lausekkeen avulla metodi public boolean onViikonpaiva(String merkkijono), joka palauttaa true jos sen parametrina saama merkkijono on viikonpäivän lyhenne (ma, ti, ke, to, pe, la tai su).

Esimerkkitulostuksia metodia käyttävästä ohjelmasta:

Anna merkkijono: ti
Muoto on oikea.
Anna merkkijono: abc
Muoto ei ole oikea.

Vokaalitarkistus

Tee metodi public boolean kaikkiVokaaleja(String merkkijono) joka tarkistaa säännöllisen lausekkeen avulla ovatko parametrina olevan merkkijonon kaikki merkit vokaaleja.

Esimerkkitulostuksia metodia käyttävästä ohjelmasta:

Anna merkkijono: aie
Muoto on oikea.
Anna merkkijono: ane
Muoto ei ole oikea.

Kellonaika

Säännölliset lausekkeet sopivat tietynlaisiin tilanteisiin. Joissain tapaukseesa lausekkeista tulee liian monimutkaisia, ja merkkijonon "sopivuus" kannattaa tarkastaa muulla tyylillä tai voi olla tarkoituksenmukaista käyttää säännöllisiä lausekkeita vain osaan tarkastuksesta.

Tee metodi public boolean kellonaika(String merkkijono) ohjelma, joka tarkistaa säännöllisen lausekkeen avulla onko parametrina oleva merkkijono muotoa tt:mm:ss oleva kellonaika (tunnit, minuutit ja sekunnit kaksinumeroisina).

Esimerkkitulostuksia metodia käyttävästä ohjelmasta:

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.

Enumien vertailu

Ylläolevassa esimerkissä kahta enumia verrattiin yhtäsuuruusmerkkien avulla. Miksi tämä on ok?

Jokainen lueteltu arvo saa oman uniikin numerotunnuksen, ja niiden vertailu keskenään yhtäsuuruusmerkillä on ok. Kuten muutkin Javan luokat, myös luetellut arvot perivät Object-luokan ja sen equals-metodin. Luetelluilla luokilla myös equals-metodi vertailee tätä numerotunnusta.

Luetellun arvon numeraalisen tunnuksen saa selville metodille ordinal(). Metodi palauttaa käytännössä järjestysnumeron -- jos lueteltu arvo on esitelty ensimmäisenä, on sen järjestysnumero 0. Jos toisena, järjestysnumero on 1, jne.

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

Tehdään ohjelma pienen yrityksen henkilöstön hallintaan.

Koulutus

Tee pakkaukseen henkilosto lueteltu tyyppi eli enum Koulutus jolla on tunnukset FT (tohtori), FM (maisteri), LuK (kandidaatti), FilYO (ylioppilas).

Henkilo

Tee pakkaukseen henkilosto luokka Luokka Henkilo. Henkilölle annetaan konstruktorin parametrina annettava nimi ja koulutus. Henkilöllä on myös koulutuksen kertova metodi public Koulutus getKoulutus() sekä alla olevan esimerkin mukaista jälkeä tekevä toString-metodi.

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

Tyontekijat

Tee pakkaukseen henkilosto luokka Luokka Tyontekijat. Työntekijät-olio sisältää listan Henkilo-olioita. Luokalla on parametriton konstruktori ja seuraavat metodit:

  • public void lisaa(Henkilo lisattava) lisää parametrina olevan henkilön työntekijäksi
  • public void lisaa(List<Henkilo> lisattavat) lisää parametrina olevan listan henkilöitä työntekijöiksi
  • public void tulosta() tulostaa kaikki työntekijät
  • public void tulosta(Koulutus koulutus) tulostaa työntekijät joiden koulutus on sama kuin parametrissa määritelty koulutus

HUOM: Luokan Tyontekijat tulosta-metodit on toteutettava iteraattoria käyttäen!

Irtisanominen

Tee luokalle Tyontekijat metodi public void irtisano(Koulutus koulutus) joka poistaa Työntekijöiden joukosta kaikki henkilöt joiden koulutus on sama kuin metodin parametrina annettu.

HUOM: toteuta metodi iteraattoria käyttäen!

Seuraavassa esimerkki luokan käytöstä:

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

Tulostuu:

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

Tehtäväpohjan mukana on luokka, jonka oliot kuvaavat pelikortteja. Kortilla on arvo ja maa. Kortin arvo on esitetään numerona 2, 3, ..., 14 ja maa Risti, Ruutu, Hertta tai Pata. Ässä on siis arvo 14. Arvo esitetään kokonaislukuna ja maa enum-tyyppisenä oliona. Kortilla on myös metodi toString, jota käyttäen kortin arvo ja maa tulostuvat "ihmisystävällisesti".

Korttien luominen tapahtuu seuraavasti.

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);

Tulostuu:

RUUTU 2
PATA A
HERTTA Q

Tee kaikki toteutukset pakkaukseen kortit.

Kortti-luokasta Comparable

Tee Kortti-luokasta Comparable. Toteuta compareTo-metodi niin, että korttien järjestys on arvon mukaan nouseva. Jos verrattavien Korttien arvot ovat samat, verrataan niitä maan perusteella nousevassa järjestyksessä: risti ensin, ruutu toiseksi, hertta kolmanneksi, pata viimeiseksi.

Maiden järjestämisessä apua löytynee Enum-luokan ordinal-metodista.

Järjestyksessä pienin kortti siis olisi risti kakkonen ja suurin pataässä.

Käsi

Tee seuraavaksi luokka Kasi joka edustaa pelaajan kädessään pitämää korttien joukkoa. Tee kädelle seuraavat metodit:

  • public void lisaa(Kortti kortti) lisää käteen kortin
  • public void tulosta() tulostaa kädessä olevat kortit alla olevan esimerkin tyylillä
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();

Tulostuu:

RUUTU 2
PATA A
HERTTA Q
PATA 2

Käytä ArrayListiä korttien tallentamiseen.

Käden järjestäminen

Tee kädelle metodi public void jarjesta() jota kutsumalla käden sisällä olevat kortit menevät suuruusjärjestykseen. Järjestämisen jälkeen kortit tulostuvat järjestyksessä:

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

Tulostuu:

RUUTU 2
PATA 2
HERTTA Q
PATA A

Käsien vertailu

Eräässä korttipelissä kahdesta korttikädestä arvokkaampi on se, jonka sisältämien korttien arvon summa on suurempi. Tee luokasta Kasi vertailtava tämän kriteerin mukaan, eli laita luokka toteuttamaan rajapinta Comparable<Kasi>.

Esimerkkiohjelma, jossa vertaillaan käsiä:

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");
}

Tulostuu

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

Korttien järjestäminen eri kriteerein

Entä jos haluaisimme välillä järjestää kortit hieman eri tavalla, esim. kaikki saman maan kortit peräkkäin? Luokalla voi olla vain yksi compareTo-metodi, joten joudumme muunlaisia järjestyksiä saadaksemme turvautumaan muihin keinoihin.

Vaihtoehtoiset järjestämistavat toteutetaan erillisten vertailun suorittavien luokkien avulla. Korttien vaihtoehtoisten järjestyksen määräävän luokkien tulee toteuttaa Comparator<Kortti>-rajapinta. Järjestyksen määräävän luokan olio vertailee kahta parametrina saamaansa korttia. Metodeja on ainoastaan yksi compare(Kortti k1, Kortti k2), jonka tulee palauttaa negatiivinen arvo, jos kortti k1 on järjestyksessä ennen korttia k2, positiivinen arvo jos k2 on järjestyksessä ennen k1:stä ja 0 muuten.

Periaatteena on luoda jokaista järjestämistapaa varten oma vertailuluokka, esim. saman maan kortit vierekkäin vievän järjestyksen määrittelevä luokka:

import java.util.Comparator;

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

Maittainen järjestys on sama kuin kortin metodin compareTo maille määrittelemä järjestys eli ristit ensin, ruudut toiseksi, hertat kolmanneksi, padat viimeiseksi.

Järjestäminen tapahtuu edelleen luokan Collections metodin sort avulla. Metodi saa nyt toiseksi parametrikseen järjestyksen määräävän luokan olion:

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));

Tulostuu:

RUUTU 2
HERTTA Q
PATA 3
PATA A
PATA 2

Järjestyksen määrittelevä olio voidaan myös luoda suoraan sort-kutsun yhteydessä:

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

Mikäli luokkaa ei halua toteuttaa, järjestyksen voi antaa Collections-luokan sort-metodille myös lambda-lausekkeena.

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

Tarkempia ohjeita vertailuluokkien tekemiseen täällä

Tee nyt luokka Comparator-rajapinnan toteuttava luokka SamatMaatVierekkainArvojarjestykseen jonka avulla saat kortit muuten samanlaiseen järjestykseen kuin edellisessä esimerkissä paitsi, että saman maan kortit järjestyvät arvon mukaisesti.

Käden järjestäminen maittain

Lisää luokalle Kasi metodi public void jarjestaMaittain() jota kutsumalla käden sisällä olevat kortit menevät edellisen tehtävän vertailijan määrittelemään järjestykseen. Järjestämisen jälkeen kortit tulostuvat järjestyksessä:

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

Tulostuu:

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.

Tässä tehtävässä laajennetaan sanakirjaa siten, että sanat voidaan lukea tiedostosta ja kirjoittaa tiedostoon. Sanakirjan tulee myös osata kääntää molempiin suuntiin, suomesta vieraaseen kieleen sekä toiseen suuntaan (tehtävässä oletetaan hieman epärealistisesti, että suomen kielessä ja vieraassa kielessä ei ole yhtään samalla tavalla kirjoitettavaa sanaa). Tehtävänäsi on luoda sanakirja luokkaan MuistavaSanakirja. Toteuta luokka pakkaukseen sanakirja.

Muistiton perustoiminnallisuus

Tee sanakirjalle parametriton konstruktori sekä metodit:

  • public void lisaa(String sana, String kaannos)
  • lisää sanan sanakirjaan. Jokaisella sanalla on vain yksi käännös ja jos sama sana lisätään uudelleen, ei tapahdu mitään.
  • public String kaanna(String sana)
  • palauttaa käännöksen annetulle sanalle. Jos sanaa ei tunneta, palautetaan null.

Sanakirjan tulee tässä vaiheessa toimia seuraavasti:

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"));

Tulostuu

monkey
apina
null
banaani

Kuten tulostuksesta ilmenee, käännöksen lisäämisen jälkeen sanakirja osaa tehdä käännöksen molempiin suuntiin.

Huom: metodit lisaa ja kaanna eivät lue tiedostoa tai kirjoita tiedostoon! Myöskään konstruktori ei koske tiedostoon.

Sanojen poistaminen

Lisää sanakirjalle metodi public void poista(String sana) joka poistaa annetun sanan ja sen käännöksen sanakirjasta.

Kannattanee kerrata aiemmilta viikoilta materiaalia, mikä liittyy olioiden poistamiseen ArrayListista.

HUOM2: metodi poista ei kirjoita tiedostoon.

Sanakirjan tulee tässä vaiheessa toimia seuraavasti:

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"));

Tulostuu

null
null
null
null
programming

Poisto siis toimii myös molemmin puolin, alkuperäisen sanan tai sen käännöksen poistamalla, poistuu sanakirjasta tieto molempien suuntien käännöksestä

Lataaminen tiedostosta

Tee sanakirjalle konstruktori public MuistavaSanakirja(String tiedosto) ja metodi public boolean lataa(), joka lataa sanakirjan konstruktorin parametrina annetun nimisestä tiedostosta. Jos tiedoston avaaminen tai lukeminen ei onnistu, palauttaa metodi false ja muuten true.

Huom: parameterillinen konstruktori ainoastaan kertoo sanakirjalle käytetävän tiedoston nimen. Konstruktori ei lue tiedostoa, tiedoston lukeminen tapahtuu ainoastaan metodissa lataa.

Sanakirjatiedostossa yksi rivi sisältää sanan ja sen käännöksen merkillä ":" erotettuna. Tehtäväpohjan mukana tuleva testaamiseen tarkoitettu sanakirjatiedosto src/sanat.txt on sisällöltään seuraava:

apina:monkey
alla oleva:below
olut:beer

Lue sanakirjatiedosto rivi riviltä lukijan metodilla nextLine. Voit pilkkoa rivin String metodilla split seuraavasti:

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ä
}

Sanakirjaa käytetään seuraavasti:

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"));

Tulostuu

sanakirjan lataaminen onnistui
monkey
null
below

Tallennus tiedostoon

Tee sanakirjalle metodi public boolean tallenna(), jota kutsuttaessa sanakirjan sisältö kirjoitetaan konstruktorin parametrina annetun nimiseen tiedostoon. Jos tallennus ei onnistu, palauttaa metodi false ja muuten true. Sanakirjatiedostot tulee tallentaa ylläesitellyssä muodossa, eli ohjelman on osattava lukea itse kirjoittamiaan tiedostoja.

Huom1: mikään muu metodi kuin tallenna ei kirjoita tiedostoon. Jos teit edelliset kohdat oikein, sinun ei tulisi tarvita muuttaa mitään olemassaolevaa koodia.

Huom2: vaikka sanakirja osaa käännökset molempiin suuntiin, ei sanakirjatiedostoon tule kirjoittaa kuin toinen suunta. Eli jos sanakirja tietää esim. käännöksen tietokone = computer, tulee tallennuksessa olla rivi:

tietokone:computer

tai rivi

computer:tietokone

mutta ei molempia!

Talletus kannattanee hoitaa siten, että koko käännöslista kirjoitetaan uudelleen vanhan tiedoston päälle, eli materiaalissa esiteltyä append-metodia ei kannata käyttää.

Sanakirjan lopullista versiota on tarkoitus käyttää seuraavasti:

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

// käytä sanakirjaa

sanakirja.tallenna();

Eli käytön aluksi ladataan sanakirja tiedostosta ja lopussa tallennetaan se takaisin tiedostoon jotta sanakirjaan tehdyt muutokset pysyvät voimassa seuraavallekin käynnistyskerralle.

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.

Erään alakoulun luokka 4B keräsi viikon ajan pulloja leirikoulun rahoittamista varten. Kirjoita ohjelma, jolla voidaan luoda tilastoja kerätyistä pulloista, sekä ohjelmalle testit. Ohjelma tulee toteuttaa tehtäväpohjan luokan Ohjelma metodiin public static String suorita(Scanner lukija). Testit tulee toteuttaa tehtäväpohjan luokkaan OhjelmaTest.

Ohjelmalle syötetään ensin kunkin oppilaan keräämien pullojen lukumäärät, jotka on erotettu rivinvaihdoilla. Pullojen lukumäärien syöttämisen lopettaminen ilmoitetaan luvulla -1. Kun pullojen lukumäärät on syötetty, ohjelman tulee selvittää pulloja keränneiden oppilaiden lukumäärä, kerättyjen pullojen lukumäärä, sekä keskimääräinen kerättyjen pullojen lukumäärä. Metodin suorita tulee palauttaa merkkijono, joka sisältää ohjelman tulostuksen.

Syötteessä saattaa olla negatiivisia lukuja, jotka ovat virhesyötteitä -- näitä ei tule ottaa huomioon.

Alla esimerkkejä ohjelman toiminnasta.

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

Mikäli kerättyjä pulloja ei ole lainkaan, ilmoita ettei keskiarvoa voi laskea.

System.out.println(Ohjelma.suorita(new Scanner("-55\n-1\n")));
Pulloja: 0
Oppilaita: 0
Keskiarvoa ei voida laskea

Huom! Ohjelman toiminnallisuuden lisäksi tehtävässä tulee kirjoittaa ohjelmalle testit. Automaattisia testejä tehtävässä ei ole valmiina, eli palauta ohjelma kun sekä ohjelma että siihen toteuttamasi testit toimivat kattavasti. Otathan huomioon myös ns corner caset.

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.

Vertaisarviointi

Alla on kolme Crowdsorcereriin tehtyä tehtävää: kaksi jonkun kurssitoverisi lähettämää ja yksi itsearviointia varten. Niiden yhteydessä on muistin virkistykseksi ohjeistus, jonka pohjalta kyseiset tehtävänannot on tehty.

Tarkastele jokaisen tehtävän eri osia: tehtävänantoa, tehtäväpohjaa ja malliratkaisua sekä testaukseen käytettäviä syötteitä ja tulosteita. Arvioi niiden selkeyttä, vaikeutta ja sitä, kuinka hyvin ne vastaavat ohjeistukseensa.

Voit vaihtaa näkymää tehtäväpohjan ja mallivastauksen välillä painamalla lähdekoodin yläpalkin painikkeita. Palautteenannon avuksi on annettu väittämiä. Voit valita kuinka samaa mieltä niiden kanssa olet painamalla hymiöitä. Annathan myös sanallista palautetta sille varattuun kenttään! Lisää vielä tehtävää mielestäsi kuvaavia tageja ja paina Lähetä.

Anna arvio kummallekin vertaispalautetehtävälle ja lopuksi vielä omallesi.

Muista olla reilu ja ystävällinen. Hyvä palaute on rehellistä, mutta kannustavaa!

Voit halutessasi ladata arvioitavan tehtävän tehtäväpohjan ja malliratkaisun koneellesi, ja testata niiden käyttöä. Molemmat tulevat ZIP-paketeissa, jolloin sinun täytyy purkaa ne, ennen kuin voit avata ne NetBeansissä.

Suunnittele oma tehtävä

Keksi ohjelmointitehtävä. Tehtävän aihealuetta ei ole rajattu, eli tehtävä on hyvin vapaa. Saat käyttää tehtävässä listoja, hajautustauluja, taulukoita sekä Scanneria.

Huom! Tässä sinun täytyy todennäköisesti syöttää jokaiselle testitapaukselle useampi syöte. Useamman syötteen saat annettua, kun laitat rivinvaihdon \n jokaisen syötteen väliin.

Esimerkiksi jos haluat antaa testisyötteeksi "kissa", "koira", "lopeta", syötä input-kenttään teksti kissa\nkoira\nlopeta.

Muista merkitä malliratkaisurivit ohjelmaan -- näin ratkaisu ei tule suoraan käyttäjälle näkyvään tehtävänantoon.

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.

Edellä kuvatun kasvatusmenetelmän tehokkuudesta

Edellä kuvattu menetelmä kopioi kasvatuksen yhteydessä jokaisen vanhan taulukon arvon uuteen taulukkoon. Jos taulukossa on esimerkiksi kaksi miljoonaa alkiota, kopiointi käy kaksi miljoonaa alkiota läpi.

Menetelmän tehokkuuteen -- ja parannusehdotuksiin -- paneudutaan muunmuassa kursseilla Tietorakenteet sekä Algoritmien suunnittelu ja analyysi.

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--;
}
Edellä kuvatun poistomenetelmän tehokkuudesta

Edellä kuvattu menetelmä kopioi poiston yhteydessä jokaisen poistettua alkiota seuraavan alkion vasemmalle. Pohdi toteutuksen tehokkuutta tilanteessa, missä listaa käytetään jonona.

Tämänkin menetelmän tehokkuuteen -- ja parannusehdotuksiin -- paneudutaan muunmuassa kursseilla Tietorakenteet sekä Algoritmien suunnittelu ja analyysi.

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;
}
Miksei hajautustaulua toteuteta listana?

Hajautustaulun toimintaperiaate perustuu siihen, että avain-arvo -parit jaetaan hajautusarvon perusteella pieniin joukkoihin. Tällöin avaimen perusteella haettaessa käydään läpi vain hyvin pieni joukko avain-arvo -pareja -- olettaen toki, että hajautusarvo on järkevä.

Jos hajautusarvo on aina sama -- esimerkiksi 1 -- vastaa hajautustaulun sisäinen toteutus listaa -- kaikki arvot ovat samalla listalla. Jos taas hajautusarvo on hyvin satunnainen, arvot hajautetaan mahdollisimman tasaisesti taulukon eri listoille.

Hajautustaulu toimii lisäksi siten, että hajautustaulun käyttämää taulukkoa kasvatetaan mikäli arvojen määrä on tarpeeksi iso (tyypillisesti noin 75% taulukon koosta). Tyypillisesti miljoonia avain-arvo -pareja sisältävän hajautustaulun taulukon yhdessä indeksissä on vain muutama avain-arvo -pari. Tämä tarkoittaa käytännössä sitä, että avain-arvo -parin olemassaolon selvittämiseen tarvitaan vain hajautusarvon laskeminen sekä muutaman olion tarkastelu -- tämä on paljon nopeampaa kuin listan läpikäynti.

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.

Toteuta edellistä esimerkkiä noudattaen luokat Lista ja Hajautustaulu pakkaukseen tietorakenteita. Kohdat on pisteytetty askeleittain, jotka ovat seuraavat:

Lista

  1. Listan luominen
  2. Arvojen lisääminen listalle (osat 1 ja 2)
  3. Listalla olevan arvon olemassaolon tarkastaminen
  4. Listalla olevan arvon poistaminen
  5. Listan indeksistä hakeminen ja listan koko

Hajautustaulu, osa 1

  1. Avain-arvo -paria kuvaavan luokan toteutus
  2. Hajautustaulun luominen
  3. Arvon hakeminen hajautustaulusta
  4. Hajautustauluun lisääminen (ei kasvatusta)

Hajautustaulu, osa 2

  1. Hajautustaulun koon kasvattaminen tarvittaessa
  2. Hajautustaulusta poistaminen

Sitä mukaa kun kehität listaa ja hajautustaulua, päivitä luokan Ohjelma metodia osiaToteutettu palauttamaan valmiiksi saamasi osan numero. Voit palauttaa tehtävän vaikket tekisikään kaikkia osia, jolloin saat pisteitä tehtävän niistä osista, jotka olet tehnyt.

Esimerkiksi, kun olet saanut listan luomisen, arvojen lisäämisen ja arvon poistamisen toimimaan, olet vaiheessa 3, jolloin metodin osiaToteutettu tulisi palautta arvo 3.

Loppurutistus

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

Tässä tehtävässä nivotaan yhteen aiemmin harjoiteltuja hajautustauluja, tiedoston lukemista sekä tehdään pieni askel koneoppimisen suuntaan. Koneoppiminen on tietojenkäsittelytieteen osa-alue, missä tutkitaan ja rakennetaan ohjelmia, jotka voivat oppia muunmuassa niille annetusta datasta.

Käytössämme oleva data (kansiossa src oleva tiedosto arviot.txt) sisältää yli 8000 englanninkielistä elokuva-arviota, joihin on valmiiksi lisätty tunnearvio. Tunnearviot on annettu skaalalla nollasta neljään, missä arvot ovat seuraavat:

  • 0 - negatiivinen
  • 1 - hieman negatiivinen
  • 2 - neutraali
  • 3 - hieman positiivinen
  • 4 - positiivinen

Teemme seuraavaksi ohjelman, joka pyrkii arvioimaan liittyykö tekstimuotoiseen elokuva-arvioon negatiivinen, positiivinen vai neutraali tunne.

Sanojen lukumäärä

Toteuta tehtäväpohjassa annettuun luokkaan TunteikkaatArviot metodi public int sanojenLukumaara(String sana). Metodin tulee kertoa sille parametrina annetun merkkijonon sana esiintymislukumäärä luokan konstruktorille annetussa merkkijonolistassa.

Kannattanee tässä jo miettiä minkälainen tietorakenne olisi hyvä sanojen lukumäärän tallentamiseen. Saat merkkijonoon liittyvät yksittäiset sanat selville esimerkiksi String-luokan split-metodin avulla:

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

Voit kokeilla ohjelmasi toimintaa esimerkiksi seuraavalla koodilla:

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"));

Ylläoleva esimerkki tuottaa seuraavanlaisen tulostuksen.

338
2538
172
2
1
0

Huom! Käsittele pienellä ja isolla kirjoitetut sanat samoina sanoina!

Yksittäisen sanan tunne

Tehtäväpohjassa annetut tiedostot arviot-lyhyt-1.txt, arviot-lyhyt-2.txt ja arviot.txt sisältävät elokuva-arvioita. Tiedostojen muoto on seuraavanlainen, missä jokaisen rivin ensimmäinen arvo on arvioon liitetty tunnearvo skaalalla nollasta neljään. Tätä seuraa konkreettinen tekstimuotoinen arvio. Esimerkiksi:

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 .
  

Yllä on kuvattu neljän eri elokuvan saamat arviot, sekä niihin liitetyt tunnearvot. Ensimmäinen arvio on hieman negatiivinen, kaksi seuraavaa hieman positiivisia, ja viimeinen on negatiivinen.

Toteuta tässä osiossa metodiin public double sananTunne(String sana) toiminnallisuus, joka palauttaa parametrina annetulle sanalle keskimääräisen tunnearvon.

Keskimääräinen tunnearvo lasketaan niiden arvioiden keskiarvona, joissa sana esiintyy. Jos sana esiintyy useaan kertaan arviossa, tulee arvio ottaa useampaan kertaan huomioon. Jos sanaan ei esiinny kertaakaan, palauta neutraali arvo, eli 2.0.

Ylläolevassa esimerkissä sana "it" esiintyy kahdesti, kummassakin lauseessa arvio on 3. Sanan "it" keskimääräiseksi tunnearvoksi tulee siis (3+3) / 2 = 3. Vastaavasti sana "that" esiintyy kolmesti, ja tunnearvoksi tulee (3+3+0) / 3 = 2.

Voit kokeilla ohjelmasi toimintaa esimerkiksi seuraavalla koodilla:

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"));

Ylläoleva esimerkki tuottaa seuraavanlaisen tulostuksen.

0.8235294117647058
2.0260047281323876
2.645348837209302
2.5
2.0

Toteuta lisäksi myös metodi public String sananTunneMerkkijonona(String sana), joka tarkastelee sanaan liittyvää tunnearvoa ja palauttaa tunnearvoon liittyvän merkkijonon. Jos tunnearvo on pienempi tai yhtäsuuri kuin 1.9, tulee palauttaa merkkijono "negatiivinen". Jos taas tunnearvo on pienempi tai yhtäsuuri kuin 2.1, tulee palauttaa merkkijono "neutraali". Muulloin palautetaan merkkijono "positiivinen".

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

Huom! Käsittele pienellä ja isolla kirjoitetut sanat samoina sanoina! String-luokan metodeista toLowerCase ja toUpperCase on tässä hyötyä.

Lauseen tunne

Toteuta seuraavaksi metodi public double lauseenTunne(String lause), joka palauttaa lauseen tunteen. Laske lauseen tunnearvo lauseeseen liittyvien sanojen tunnearvojen keskiarvona.

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

Toteuta vielä lopuksi metodi public String lauseenTunneMerkkijonona(string lause), joka palauttaa lauseen tunteen merkkijonomuodossa. Käytä tässä samaa muunnosta kuin edellisessä osassa.

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

Huom! Kuten edellä, käsittele pienellä ja isolla kirjoitetut sanat samoina sanoina!

Tehtäväpohjassa on mukana versio klassisesta Pong-pelistä. Tehtävänäsi on tutustua peliin ja toteuttaa pakkauksessa pong.ai olevaan luokkaan MunPongAly tekoäly, joka vähintäänkin voittaa esimerkkinä annetun luokan FollowingPongAi.

Sovelluksen käytettävyys

Tärkein sovelluksen testaamisen liittyvä ihmisryhmä on sovelluksen käyttäjät. Käyttäjät toimivat ohjelman parissa ja huomaavat toiminnassa esiintyviä puutteita.

Sovelluksen käytettävyyteen liittyy useita erilaisia näkökulmia, joista osa on standardoitu. Käytettävyyden kannalta oleellisia ominaisuuksia ovat muunmuassa:

  • Tavoitteiden saavuttaminen. Ohjelmiston käyttäjillä on tavoitteita, joita ohjelmiston avulla halutaan saavuttaa. Miten hyvin ohjelmisto auttaa käyttäjiä saavuttamaan tavoitteensa? Miten tehokkaasti käyttäjät saavuttavat tavoitteensa? Joutuvatko he käyttämään liikaa aikaa tavoitteiden saavuttamiseen? Voisiko tätä helpottaa sovelluksen suunnittelussa?
  • Tyytyväisyys sovelluksen toimintaan. Miten tyytyväisiä käyttäjät ovat sovelluksen toimintaan? Onko sovelluksen käyttö sujuvaa?
  • Ohjelmiston käytön oppiminen. Kuinka nopeasti ohjelmiston käyttö on opittavissa? Minkälaisia ohjeita sovelluksen käyttö vaatii? Tarjoaako ohjelmisto näitä ohjeita? Kuinka hyvin käyttäjä muistaa miten sovellusta käytetään?
  • Virhealttius. Kuinka paljon käyttäjä tekee virheitä sovellusta käyttäessään? Voisiko virheiden määrää vähentää?

Käytettävyyden lisäksi sovelluksissa oleellista on myös saavutettavuus, millä tarkoitetaan erilaisten käyttäjäryhmien huomiointia sovelluksen rakentamisessa. Näitä käsitellään tarkemmin Human-Computer Interaction -teeman kursseilla (Ihmisen ja tietokoneen välinen vuorovaikutus).

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.

Mitä seuraavaksi?

Tämän kurssin jälkeen on hyvä ottaa kurssit Tietokantojen perusteet sekä Tietorakenteet ja algoritmit. Kurssin tietokantojen perusteet jälkeen kannattaa ottaa kurssi Ohjelmistotekniikan menetelmät. Jos kurssia Tietokoneen toiminta ei ole vielä suorittanut, myös sen ottaminen on suositeltavaa. Muistathan, että kurssin Tietorakenteet ja algoritmit esitietovaatimuksena on kurssi Johdatus yliopistomatematiikkaan.

Sisällysluettelo