Pakan funktioiden esittelyt

Pakkaa voidaan käsitellä yleisen pakan 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), merkkipakkapakka (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 tyyppi DEQUE_END, ja tälle
kaksi arvoa, top ja bottom. Voitaisiin siis esimerkiksi kutsua:DEQUE_ENQUEUE(D, top, x);

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ää 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ää IE_XXX; INT_DEQUE_CREATE(D) voidaan siis kutsua myös IE_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 FE_XXX.

Char* / string[ ] - pakan käsittely

Merkkijonopakan tyyppinä on C:ssä char*, osoitin merkkipakkaan. Pascalissa tyyppinä on string, jonka maksimipituus on vakio RANDOM_STR_MAX, cs:llä 16 merkkiä. Kaikki CHARP_DEQUE_XXX - aliohjelmat voidaan lyhentää koodissa CE_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.

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, tyypitettyjen listojen funktiota palauttavat pakan omaa tyyppiä olevan arvon.

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, tyypitettyjen listojen funktiota palauttavat pakan omaa tyyppiä olevan arvon.

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. 

Aikavaativuus : O(1)

DEQUE_PRINT (D)

void DEQUE_PRINT (DEQUE D);

procedure DEQUE_PRINT (D:DEQUE);

Tulostaa pakan D kuvaajassa määritellyllä tavalla. Tyypitetyillä funktioilla ei ole eroa tämän toiminnan kanssa.

Aikavaativuus : O(n)

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

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 : Pascal / C

Aikavaativuus : O(n)

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  : 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 M, joka on samaa tyyppiä kuin pakka D, luodaan komennolla DEQUE_CREATE(M, 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 FALSE (!=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ä.

Aikavaativuus : O(1)