Pakan funktioiden esittelyt

Pakkaa voidaan käsitellä yleisen pakan operaatioiden avulla tietämättä pakan oikeaa tyyppiä, aivan kuten esimerkikiksi listan tapauksessa. Tietorakennekirjastoon on toteutettu neljä erilaista tyypitettyä pakkatyyppiä : kokonaislukupakka, joka sisältää int / integer - arvoja, liukulukupakka (sisältää float / real - tyyppistä tietoa), merkkijonopakka (char* / string[ ]) ja osoitinpakka (void* / pointer - tyyppistä tietoa).

Tässä osassa on esitelty yleisen-, kokonaisluku-, liukuluku- ja merkkijonopakan funktiot. Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että pakka on määritelty. Mikäli parametrina annettava pakka D on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin DEQUE_CREATE:a joka määrittelee pakan.

Pakka on tietorakenteena kuin lista jonka operaatiot kohdistuvat aina listan jompaan kumpaan päähän. Koska pakassa on kaksi paikkaa joihin operaatiot voidaan kohdistaa, on kirjastossa määritelty lueteltu tyyppi DEQUE_END, jolla on kaksi arvoa, top ja bottom. Voitaisiin siis esimerkiksi kutsua:DEQUE_ENQUEUE(D, top, x);

DEQUE_CREATE (D, desc)
DEQUE_ENQUEUE (D ,dir, x)
DEQUE_FRONT (D)
DEQUE_REAR (D)
DEQUE_DEQUEUE (D, dir)
DEQUE_PRINT (D)
DEQUE_FREE (D)
DEQUE_CONSTRUCT_RANDOM (D, count, min, max)
DEQUE_TYPE (D)
DEQUE_LESS (D, x, y)
DEQUE_SAME (D, x, y)
DEQUE_EMPTY (D)

Yleisen pakan käsittely

Yleisen pakan funktioita tarvitaan silloin, kun pitää käsitellä pakkaa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä pakkaa luotaessa määritellään pakan tyyppi kuvaajan DESCRIPTOR avulla. Funktio DEQUE_TYPE(D) palauttaa pakan D kuvaajan jota voidaan käyttää uutta samantyyppistä pakkaa luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten pakan alkioita vertaillaan, käsitellään ja tulostetaan.

Int / integer - pakan käsittely

Kokonaislukupakan esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on toteutuskohtaisesti määritelty. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (max. 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (2^32). Kaikki INT_DEQUE_XXX - aliohjelmat voidaan lyhentää ID_XXX; INT_DEQUE_CREATE(D) voidaan siis kutsua myös ID_CREATE(D).

Float / real - pakan käsittely

Liukulukupakan esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukupakan kohdalla. FLOAT_DEQUE_XXX voidaan lyhentää koodissa FD_XXX.

Char* / string[ ] - pakan käsittely

Merkkijonopakan tyyppinä on C:ssä char*, osoitin merkkijonoon. Pascalissa tyyppinä on string, jonka maksimipituus on vakio RANDOM_STR_MAX, cs:llä 16 merkkiä. Kaikki CHARP_DEQUE_XXX - aliohjelmat voidaan lyhentää koodissa CD_XXX.

Funktioiden esittelyt

DEQUE_CREATE (D, desc)
void DEQUE_CREATE (DEQUE D, DESCRIPTOR desc);

void INT_DEQUE_CREATE(DEQUE D);

void FLOAT_DEQUE_CREATE(DEQUE D);

void CHARP_DEQUE_CREATE(DEQUE D);

void VOIDPTR_DEQUE_CREATE(DEQUE D);

procedure DEQUE_CREATE (var D:DEQUE; desc:DESCRIPTOR);

procedure INT_DEQUE_CREATE (var D:DEQUE);

procedure FLOAT_DEQUE_CREATE (var D:DEQUE);

procedure CHARP_DEQUE_CREATE (var D:DEQUE);

procedure VOIDPTR_DEQUE_CREATE (var D:DEQUE);

Yleinen DEQUE_CREATE(D, desc) muodostaa tyhjän pakan D, ja asettaa pakan kuvaajaksi kuvaajan desc = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDP_DESC}. Mikäli pakka D ei ole tyhjä pakka, kaikki pakassa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan pakan D. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

DEQUE_ENQUEUE (D,dir, x)
void DEQUE_ENQUEUE (DEQUE D, dir DEQUE_END, ELEMENT x);

void INT_DEQUE_ENQUEUE(DEQUE D, dir DEQUE_END, INT_TYPE x);

void FLOAT_DEQUE_ENQUEUE(DEQUE D, dir DEQUE_END, FLOAT_TYPE x);

void CHARP_DEQUE_ENQUEUE(DEQUE D, dir DEQUE_END, CHARP_TYPE x);

void VOIDPTR_DEQUE_ENQUEUE(DEQUE D, DEQUE_END dir, void* x);

procedure DEQUE_ENQUEUE (D:DEQUE; dir:DEQUE_END; x:ELEMENT);

procedure INT_DEQUE_ENQUEUE (D:DEQUE; dir:DEQUE_END; x:INT_TYPE);

procedure FLOAT_DEQUE_ENQUEUE (D:DEQUE; dir:DEQUE_END; x:FLOAT_TYPE);

procedure CHARP_DEQUE_ENQUEUE (D:DEQUE; dir:DEQUE_END; x:CHARP_TYPE);

procedure VOIDPTR_DEQUE_ENQUEUE (D:DEQUE; dir:DEQUE_END; x:pointer);

Lisää alkion x pakkaan D. Parametri dir (top,bottom) määrää kumpaan pakan päähän operaatio kohdistuu. Tyypitetyt operaatiot vievät pakkaan omaa tyyppiään olevan alkion. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

DEQUE_ FRONT (D)
ELEMENT DEQUE_FRONT (DEQUE D);

INT_TYPE INT_DEQUE_FRONT (DEQUE D);

FLOAT_TYPE FLOAT_DEQUE_FRONT (DEQUE D);

CHARP_TYPE CHARP_DEQUE_FRONT (DEQUE D);

void* VOIDPTR_DEQUE_FRONT(DEQUE D)

function DEQUE_FRONT (D:DEQUE) : ELEMENT;

function INT_DEQUE_FRONT(D:DEQUE) : INT_TYPE;

function FLOAT_DEQUE_FRONT(D:DEQUE) : FLOAT_TYPE;

function CHARP_DEQUE_FRONT(D:DEQUE) : CHARP_TYPE;

function VOIDPTR_DEQUE_FRONT(D:DEQUE) : pointer;

Palauttaa pakan D ensimmäisen alkion arvon. Yleinen pakka palauttaa ELEMENT-tyypin, tyypitetyt funktiot palauttavat pakan omaa tyyppiä olevan arvon. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

DEQUE REAR (D)
ELEMENT DEQUE_REAR (DEQUE D);

INT_TYPE INT_DEQUE_REAR (DEQUE D);

FLOAT_TYPE FLOAT_DEQUE_REAR (DEQUE D);

CHARP_TYPE CHARP_DEQUE_REAR (DEQUE D);

void* VOIDPTR_DEQUE_REAR(DEQUE D)

function DEQUE_REAR (D:DEQUE) : ELEMENT;

function INT_DEQUE_REAR(D:DEQUE) : INT_TYPE;

function FLOAT_DEQUE_REAR(D:DEQUE) : FLOAT_TYPE;

function CHARP_DEQUE_REAR(D:DEQUE) : CHARP_TYPE;

function VOIDPTR_DEQUE_REAR(D:DEQUE) : pointer;

Palauttaa pakan D viimeisen alkion arvon. Yleinen pakka palauttaa ELEMENT-tyypin, tyypitetyt funktiot palauttavat pakan omaa tyyppiä olevan arvon. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

DEQUE_DEQUEUE (D, dir)
void DEQUE_DEQUEUE (DEQUE D, dir DEQUE_END);

void INT_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir);

void FLOAT_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir);

void CHARP_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir);

void VOIDPTR_DEQUE_DEQUEUE(DEQUE D, DEQUE_END dir);

procedure DEQUE_DEQUEUE (D:DEQUE;dir:DEQUE_END);

procedure INT_DEQUE_DEQUEUE (D:DEQUE;dir:DEQUE_END);

procedure FLOAT_DEQUE_DEQUEUE (D:DEQUE;dir:DEQUE_END);

procedure CHARP_DEQUE_DEQUEUE (D:DEQUE;dir:DEQUE_END);

procedure VOIDPTR_DEQUE_DEQUEUE (D:DEQUE;dir:DEQUE_END);

Poistaa pakasta D alkion. Parametri dir (top,bottom) määrää kumpaan pakan päähän operaatio kohdistuu. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)

DEQUE_PRINT (D)
void DEQUE_PRINT (DEQUE D);

procedure DEQUE_PRINT (D:DEQUE);

Tulostaa pakan D kuvaajassa määritellyllä tavalla. Esimerkki 1 : Pascal / C

Aikavaativuus : O(n)

DEQUE_FREE (D)
void DEQUE_FREE (DEQUE D);

void INT_DEQUE_FREE(DEQUE D);

void FLOAT_DEQUE_FREE(DEQUE D);

void CHARP_DEQUE_FREE(DEQUE D);

void VOIDPTR_DEQUE_FREE(DEQUE D);

procedure DEQUE_FREE (var D:DEQUE);

procedure INT_DEQUE_FREE (var D:DEQUE);

procedure FLOAT_DEQUE_FREE (var D:DEQUE);

procedure CHARP_DEQUE_FREE (var D:DEQUE);

procedure VOIDPTR_DEQUE_FREE (var D:DEQUE);

Vapauttaa kaiken pakan D varaaman tilan ja asettaa pakan D määrittelemättömäksi pakaksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila. Jos void*- tai char*-pakassa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi pakan tuhoamisen jälkeen, täytyy ennen DEQUE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta. Esimerkki 1 : Pascal / C

Aikavaativuus : O(n)

Seuraavat aliohjelmat eivät ole välttämättömiä pakan käytön kannalta, mutta helpottavat ohjelmien tekemistä ja testaamista:

DEQUE_CONSTRUCT_RANDOM (D, count, min, max)
void DEQUE_CONSTRUCT_RANDOM (DEQUE D, int count, INT_TYPE min, INT_TYPE max);

procedure DEQUE_CONSTRUCT_RANDOM (D:DEQUE; count:integer; min,max:INT_TYPE);

Muodostaa pakan D, jossa on count-määrä alkioita. Pakka täytyy olla alustettu jonkin tyyppiseksi pakaksi (XXX_DEQUE_CREATE(D)). Mikäli pakka on kokonaislukupakka, min on pakan alkioiden minimiarvo ja max maksimi, liukulukupakalla samoin. Merkkijonopakalla DEQUE_CONSTRUCT_RANDOM (D, count, min, max) vie pakkaan count kappaletta merkkijonoja, jotka sisältävät min..max merkkiä. C:ssä merkkijonon pituus on kuitenkin vähintään 1 ('\0'-merkki), Pascalissa pituus voi olla 0 merkkiä. Merkkijonot koostuvat pelkästään pienistä kirjaimista väliltä 'a'..'z'. Merkkijonon maksimipituus on rajoitettu vakion RANDOM_STR_MAX suuruiseksi, ainakin cs:n toteutuksessa 16 merkkiä. DEQUE_CONSTRUCT_RANDOM (D, 10, 2, 4) arpoo siis kokonaislukupakalle 10 kappaletta kokonaislukuja, jotka saavat arvoja 2..4, liukulukupakalle 10 kpl. liukulukuja välillä 2.00 - 4.00, merkkijonopakalle 10 merkkijonoa välillä 'aa'..'zzzz'. Esimerkki 1 : Pascal / C

Aikavaativuus : O(count)

DEQUE_TYPE (D)
DESCRIPTOR DEQUE_TYPE (DEQUE D);

function DEQUE_TYPE (D:DEQUE) : DESCRIPTOR;

Palauttaa pakan D kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen pakka joudutaan luomaan. Uusi pakka E, joka on samaa tyyppiä kuin pakka D, luodaan komennolla DEQUE_CREATE(E, DEQUE_TYPE(D));.

Aikavaativuus : O(1)

DEQUE_LESS (D, x, y)

DEQUE_SAME (D, x, y)
int DEQUE_LESS (DEQUE D, ELEMENT x, ELEMENT y);

int DEQUE_SAME (DEQUE D, ELEMENT x, ELEMENT y);

function DEQUE_LESS (D:DEQUE; x,y:ELEMENT) : boolean;

function DEQUE_SAME (D:DEQUE; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko pakan D määräämää tyyppiä olevat elementit x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä (LESS). Elementtien x ja y pitää olla samaa tyyppiä kuin pakan D alkiot (muttei niiden ole pakko olla pakan D alkioita). Jos x=y, niin DEQUE_SAME palauttaa siis TRUE (!=0), ja jos x<y niin DEQUE_LESS palauttaa TRUE (!=0). Merkkijonopakassa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

DEQUE_EMPTY (D)
int DEQUE_EMPTY (DEQUE D);

int INT_DEQUE_EMPTY(DEQUE D);

int FLOAT_DEQUE_EMPTY(DEQUE D);

int CHARP_DEQUE_EMPTY(DEQUE D);

int VOIDPTR_DEQUE_EMPTY(DEQUE D);

function DEQUE_EMPTY (D:DEQUE) : boolean;

function INT_DEQUE_EMPTY (D:DEQUE) : boolean;

function FLOAT_DEQUE_EMPTY (D:DEQUE) : boolean;

function CHARP_DEQUE_EMPTY (D:DEQUE) : boolean;

function VOIDPTR_DEQUE_EMPTY (D:DEQUE) : boolean;

Palauttaa tiedon siitä onko pakka D tyhjä pakka. C-kielessä palautusarvo on siis !=0, jos pakka on tyhjä, ja 0 mikäli pakka ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos pakka on tyhjä ja FALSE, jos pakka ei ole tyhjä. Esimerkki 1 : Pascal / C

Aikavaativuus : O(1)