Toinen projekti
Abstraktit tietotyypit
Abstrakti tietotyyppi (abstract data type, ADT) määritellään sen mahdollisten arvojen ja niitä käsittelevien operaatioiden avulla. Näkökulma on tyypin käyttäjän: hän käyttää tyyppiä sen tarjoamien operaatioiden kautta eikä hänen tarvitse tietää, miten tyyppi on toteutettu.
Huomautus: abstraktia tietotyyppiä ei pidä sekoittaa abstraktiin tyyppiin tai abstraktiin luokkaan. Niitä ei käsitellä tällä kurssilla.
Tyypin käyttäjä näkee operaatiot, ei toteutusta
int-tyyppiä voi ajatella abstraktina tietotyyppinä. Ohjelmoija käsittelee kokonaislukuja esimerkiksi yhteen-, vähennys-, kerto- ja jakolaskulla tietämättä, miten niiden bittiesitys on toteutettu. Toteutuksessa voitaisiin käyttää esimerkiksi kahden komplementtia tai BCD-koodausta, mutta tyypin käyttäjän ei tarvitse välittää siitä.
Tyypin operaatioiden pitää sopia sen arvoihin. Liikennevalotyypin arvot voisivat olla punainen, keltainen ja vihreä, ja ne voisi esittää enum-tyypillä. Värien yhteenlasku ei ole mielekäs operaatio, mutta valon vaihtaminen seuraavaan väriin voi olla.
Pino on toinen esimerkki abstraktista tietotyypistä. Sen arvot ovat pinoon talletetut alkiot, ja keskeiset operaatiot ovat push (lisää alkio päällimmäiseksi) ja pop (poista päällimmäinen alkio). Lisäksi tarvitaan pinon luominen ja tyhjyyden testaaminen.
Olemme toteuttaneet pinoa muistuttavan korttipinon linkitettynä listana. Käyttäjän ei tarvitse tietää tätä: pinon voisi toteuttaa myös taulukolla tai vektorilla, kunhan julkiset operaatiot säilyvät samoina. ADT erottaa siis käyttötavan toteutustavasta.
Tiedon piilotus ja kapselointi
Abstraktit tietotyypit liittyvät läheisesti modulaarisuuteen. Moduulit ja luokat mahdollistavat julkisen rajapinnan tarjoamisen ja toteutuksen yksityiskohtien piilottamisen.
Tiedon piilotus (information hiding) tarkoittaa toteutuksen yksityiskohtien piilottamista tai niihin pääsyn rajoittamista. Julkisessa rajapinnassa käyttäjälle riittävät operaation nimi ja kuvaus siitä, mitä se tekee, mitä parametrit tarkoittavat ja mitä paluuarvo kertoo. Kirjastofunktioitakin käytetään yleensä niiden toteutusta tuntematta. Kuvaava nimi, kuten print, voi piilottaa taakseen monimutkaisenkin toiminnan.
Kapselointi (encapsulation) tarkoittaa datan ja sitä käsittelevien operaatioiden kokoamista yhteen. Esimerkiksi pinoa toteuttava luokka sisältää pinon tiedot ja sen julkiset metodit. Luokat ja moduulit ovat tapoja toteuttaa kapselointia.
Abstraktit tietotyypit, modulaarisuus, kapselointi ja tiedon piilotus liittyvät siis toisiinsa, vaikka kukin käsite tarkastelee asiaa hieman eri näkökulmasta.
Fraction-luokka abstraktina tietotyyppinä
Hakemiston examples/07/fraction esimerkissä on murtolukuja käsittelevä Fraction-luokka. Se on abstrakti tietotyyppi ja samalla esimerkki operaattorien kuormittamisesta. Luokan attribuutit ovat osoittaja (numerator_) ja nimittäjä (denominator_). Yhtäsuuruusvertailu-, yhteenlasku- ja kertolaskuoperaattorit on kuormitettu.
Kuormitettuja laskuoperaattoreita voi käyttää samaan tapaan kuin valmiiden tyyppien operaattoreita:
Fraction frac1(2, 3); // 2/3
Fraction frac2(3, 4); // 3/4
Fraction frac3 = frac1 + frac2;Operaattorifunktiota voi kutsua myös tavallisen metodikutsun tapaan:
frac3 = frac1.operator+(frac2);Tässä frac1 on olio, johon metodikutsu kohdistuu, frac2 on parametri ja palautettu arvo sijoitetaan muuttujaan frac3. Metodiksi toteutettu operaattori edellyttää, että vasen operandi on Fraction-olio. Operaattorin voisi toteuttaa myös vapaana funktiona, mutta tässä esimerkissä metoditoteutus riittää. Kuormitettuja operaattoreita voi yhdistellä tavallisiin lausekkeisiin.
Tulostusoperaattorin kuormittaminen
Myös tulostusoperaattori << on kuormitettu, jotta ohjelmoijan määrittelemää tyyppiä voi tulostaa samaan tapaan kuin valmiita tyyppejä:
Fraction frac(2, 3);
cout << "Murtoluvun frac arvo on " << frac << endl;Tulostusoperaattori toimii eri tavalla kuin luokan laskuoperaattorit. << on ostream-luokan toimintaan liittyvä operaattori, ja cout on tulostusvirta. Tulostettavan Fraction-olion pitää siksi olla operaattorifunktion toinen operandi. Luonteva toteutus on itsenäinen funktio, ei Fraction-luokan metodi.
Tulostusfunktio tarvitsee murtoluvun osoittajan ja nimittäjän. Koska ne ovat yksityisiä attribuutteja, luokka tarjoaa niiden lukemiseen metodit getNumerator ja getDenominator. Funktio saa parametreinaan tulostusvirran ja murtolukuolion ja palauttaa saman tulostusvirran. Paluuarvo mahdollistaa ketjuttamisen, kuten esimerkin tulostuslauseessa.
Lukuoperaattori >> voitaisiin kuormittaa vastaavalla tavalla. Esimerkissä sitä ei tehdä, vaan murtoluvun lukeminen hoidetaan pääohjelmassa, jotta nimittäjäksi ei hyväksytä nollaa.
Murtolukujen supistaminen
Fraction-luokassa on myös yksityiset metodit gcd ja reduce. reduce supistaa murtoluvun mahdollisimman yksinkertaiseen muotoon. Tätä tarvitaan esimerkiksi yhtäsuuruusvertailussa sekä yhteen- ja kertolaskun tuloksen käsittelyssä.
Supistuksessa osoittaja ja nimittäjä jaetaan niiden suurimmalla yhteisellä tekijällä (greatest common divisor, gcd). Suurin yhteinen tekijä etsitään esimerkissä rekursiivisella gcd-metodilla.
Esimerkki havainnollistaa, että itse määriteltyä luokkaa ja sen olioita voidaan käyttää pitkälti samaan tapaan kuin kielen valmiita tietotyyppejä. Luokka ei kuitenkaan ole täydellinen: +-operaattorin kuormittaminen ei automaattisesti kuormita operaattoria +=. Lisäharjoituksena voit toteuttaa myös +=-operaattorin.
Muista: abstraktin tietotyypin käyttäjän pitäisi pystyä käyttämään sitä julkisen rajapinnan kautta tuntematta sen sisäistä toteutusta.