Prioriteettijonon funktioiden esittelyt

Prioriteettijono on jono jonka alkioilla on tärkeysjärjestys. Vietäessä alkiota jonoon määritellään alkion tärkeys (tästedes:
prioriteetti), ja jonosta poistetaan aina parhaan prioriteetin omaava alkio.Kirjastossa on määritelty tyyppi PRIORITYTYPE, joka on alustavasti liukulukutyyppiä float. Prioriteettijonoa voidaan käsitellä yleisen prioriteettijonon avulla tietämättä jonon oikeaa tyyppiä, aivan kuten esimerkiksi jonon tapauksessa. Tietorakennekirjastoon on toteutettu neljä erilaista tyypitettyä jonotyyppiä : kokonaisluku-prioriteettijono, joka sisältää int / integer - arvoja, liukuluku-prioriteettijono (sisältää float / real - tyyppistä tietoa), merkkijono-prioriteettijono (char* / string[ ]) ja osoitin-prioriteettijono (void* / pointer - tyyppistä tietoa).

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

Yleisen jonon käsittely

Yleisen jonon funktioita tarvitaan silloin, kun pitää käsitellä jonoa, jonka tyyppiä ei vielä ohjelmaa kirjoitettaessa tiedetä. Yleistä jonoa luotaessa määritellään jonon tyyppi kuvaajan DESCRIPTOR avulla. Funktio PRIQUEUE_TYPE(P) palauttaa jonon P kuvaajan jota voidaan käyttää jonoa luotaessa. Kuvaaja sisältää kaiken tiedon siitä miten jonon alkioita vertaillaan, käsitellään ja tulostetaan. Kuvaajasta ja yleisen jonon alkioiden tyypistä ELEMENT enemmän luvussa "Tietorakenteiden kuvaukset".

Int / integer - jonon käsittely

Kokonaislukujonon 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_PRIQUEUE_XXX - aliohjelmat voidaan lyhentää IQ_XXX; INT_PRIQUEUE_CREATE(P) voidaan siis kutsua myös IQ_CREATE(P).

Float / real - jonon käsittely

Liukulukujonon esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukujonon kohdalla. FLOAT_PRIQUEUE_XXX voidaan lyhentää koodissa FQ_XXX.

Char* / string[ ] - jonon käsittely

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

Funktioiden esittelyt

PRIQUEUE_CREATE (P, D)

void PRIQUEUE_CREATE (PRIQUEUE P, DESCRIPTOR D);

void INT_PRIQUEUE_CREATE(PRIQUEUE P);

void FLOAT_PRIQUEUE_CREATE(PRIQUEUE P);

void CHARP_PRIQUEUE_CREATE(PRIQUEUE P);

void VOIDPTR_PRIQUEUE_CREATE(PRIQUEUE P);

procedure PRIQUEUE_CREATE (var P:PRIQUEUE; D:DESCRIPTOR);

procedure INT_PRIQUEUE_CREATE (var P:PRIQUEUE);

procedure FLOAT_PRIQUEUE_CREATE (var P:PRIQUEUE);

procedure CHARP_PRIQUEUE_CREATE (var P:PRIQUEUE);

procedure VOIDPTR_PRIQUEUE_CREATE (var P:PRIQUEUE);

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

Aikavaativuus : O(1)

PRIQUEUE_INSERT(P,x,pri)

void PRIQUEUE_INSERT (PRIQUEUE P, ELEMENT X, PRIORITYTYPE pri);

void INT_PRIQUEUE_INSERT (PRIQUEUE P, INT_TYPE x, PRIORITYTYPE pri);

void FLOAT_PRIQUEUE_INSERT (PRIQUEUE P, FLOAT_TYPE x, PRIORITYTYPE pri);

void CHARP_PRIQUEUE_INSERT (PRIQUEUE P, CHARP_TYPE x, PRIORITYTYPE pri);

void VOIDPTR_PRIQUEUE_INSERT (PRIQUEUE P, *void x, PRIORITYTYPE pri);        

procedure PRIQUEUE_INSERT (P:PRIQUEUE;x:ELEMENT;pri:PRIORITYTYPE);

procedure INT_PRIQUEUE_INSERT (P:PRIQUEUE;x:INT_TYPE;pri:PRIORITYTYPE);

procedure FLOAT_PRIQUEUE_INSERT (P:PRIQUEUE;x:FLOAT_TYPE;pri:PRIORITYTYPE);

procedure CHARP_PRIQUEUE_INSERT (P:PRIQUEUE;x:CHARP_TYPE;pri:PRIORITYTYPE);

procedure VOIDPTR_PRIQUEUE_INSERT (P:PRIQUEUE;x:pointer;pri:PRIORITYTYPE);

Lisää alkion x jonoon asettaen sille prioriteetin (pri). Tyypitetyt operaatiot vievät pinoon omaa tyyppiään olevan alkion. 

Aikavaativuus : O(n)

PRIQUEUE_DELETEMIN (P)

void PRIQUEUE_DELETEMIN (PRIQUEUE P);

void INT_PRIQUEUE_DELETEMIN (PRIQUEUE P);

void FLOAT_PRIQUEUE_DELETEMIN (PRIQUEUE P);

void CHARP_PRIQUEUE_DELETEMIN (PRIQUEUE P);

void VOIDPTR_PRIQUEUE_DELETEMIN (PRIQUEUE P);

procedure PRIQUEUE_DELETEMIN (P:PRIQUEUE);

procedure PRIQUEUE_DELETEMIN (P:PRIQUEUE);

procedure PRIQUEUE_DELETEMIN (P:PRIQUEUE);

procedure PRIQUEUE_DELETEMIN (P:PRIQUEUE);

Poistaa jonosta alkion prioriteetin mukaisesti. 

Aikavaativuus : O(n)

PRIQUEUE_MIN(P)

ELEMENT PRIQUEUE_MIN (PRIQUEUE P);

INT_TYPE INT_PRIQUEUE_MIN (PRIQUEUE P);

FLOAT_TYPE FLOAT_PRIQUEUE_MIN (PRIQUEUE P);

CHARP_TYPE CHARP_PRIQUEUE_MIN (PRIQUEUE P);

*void VOIDPTR_PRIQUEUE_MIN (PRIQUEUE P);

function PRIQUEUE_MIN (P:PRIQUEUE):ELEMENT;

function INT_PRIQUEUE_MIN (P:PRIQUEUE):INT_TYPE;

function FLOAT_PRIQUEUE_MIN (P:PRIQUEUE):FLOAT_TYPE;

function CHARP_PRIQUEUE_MIN (P:PRIQUEUE):CHARP_TYPE;

function VOIDPTR_PRIQUEUE_MIN (P:PRIQUEUE):pointer;

Palauttaa prioriteettijonosta "pienimmän" (prioriteetti) alkion arvon.     

Aikavaativuus : O(n)

PRIQUEUE_FREE (P)

void PRIQUEUE_FREE (PRIQUEUE P);

void INT_PRIQUEUE_FREE (PRIQUEUE P);

void FLOAT_PRIQUEUE_FREE (PRIQUEUE P);

void CHARP_PRIQUEUE_FREE (PRIQUEUE P);

void VOIDPTR_PRIQUEUE_FREE(PRIQUEUE P);

procedure PRIQUEUE_FREE (var P:PRIQUEUE);

procedure INT_PRIQUEUE_FREE (var P:PRIQUEUE);

procedure FLOAT_PRIQUEUE_FREE (var P:PRIQUEUE);

procedure CHARP_PRIQUEUE_FREE (var P:PRIQUEUE);

procedure VOIDPTR_PRIQUEUE_FREE (var P:PRIQUEUE);

Vapauttaa kaiken jonon P varaaman tilan ja asettaa jonon P määrittelemättömäksi jonoksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila. Jos void*- tai char*-jonossa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi jonon tuhoamisen jälkeen, täytyy ennen PRIQUEUE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta. 

Aikavaativuus : O(n)

PRIQUEUE_TYPE (P)

DESCRIPTOR PRIQUEUE_TYPE (PRIQUEUE P);

function PRIQUEUE_TYPE (P:PRIQUEUE) : DESCRIPTOR;

Palauttaa jonon P kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen jono joudutaan luomaan. Uusi jono M, joka on samaa tyyppiä kuin jono P, luodaan komennolla PRIQUEUE_CREATE(M, PRIQUEUE_TYPE(P));.

Aikavaativuus : O(1)

PRIQUEUE_LESS (P, x, y)

PRIQUEUE_SAME (P, x, y)

int PRIQUEUE_LESS (PRIQUEUE P, ELEMENT x, ELEMENT y);

int PRIQUEUE_SAME (PRIQUEUE P, ELEMENT x, ELEMENT y);

function PRIQUEUE_LESS (P:PRIQUEUE; x,y:ELEMENT) : boolean;

function PRIQUEUE_SAME (P:PRIQUEUE; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko jonon P 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 jonon P alkiot (muttei niiden ole pakko olla jonon P alkioita). Jos x=y, niin PRIQUEUE_SAME palauttaa siis TRUE (0), ja jos x<y niin PRIQUEUE_LESS palauttaa FALSE (!=0). Merkkijonojonossa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : yksinkertaisille tyypeille O(1)

PRIQUEUE_EMPTY (P)

int PRIQUEUE_EMPTY (PRIQUEUE P);

int INT_PRIQUEUE_EMPTY (PRIQUEUE P);

int FLOAT_PRIQUEUE_EMPTY (PRIQUEUE P);

int CHARP_PRIQUEUE_EMPTY (PRIQUEUE P);

int VOIDPTR_PRIQUEUE_EMPTY(PRIQUEUE P);

function PRIQUEUE_EMPTY (P:PRIQUEUE) : boolean;

function INT_PRIQUEUE_EMPTY (P:PRIQUEUE) : boolean;

function FLOAT_PRIQUEUE_EMPTY (P:PRIQUEUE) : boolean;

function CHARP_PRIQUEUE_EMPTY (P:PRIQUEUE) : boolean;

function VOIDPTR_PRIQUEUE_EMPTY (P:PRIQUEUE) : boolean;

Palauttaa tiedon siitä onko jono P tyhjä jono. C-kielessä palautusarvo on siis !=0, jos jono on tyhjä, ja 0 mikäli jono ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos jono on tyhjä ja FALSE, jos jono ei ole tyhjä.

Aikavaativuus : O(1)