Prioriteettijonon funktioiden esittelyt

Prioriteettijono on jono jonka alkioilla on tärkeysjärjestys. Vietäessä alkiota prioriteettijonoon määritellään alkion tärkeys (tästedes: prioriteetti), ja prioriteettijonosta 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ä sen oikeaa tyyppiä, aivan kuten esimerkiksi jonon tapauksessa. Tietorakennekirjastoon on toteutettu neljä erilaista tyypitettyä prioriteettijonotyyppiä : 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ä prioriteettijono on määritelty. Mikäli parametrina annettava prioriteettijono P on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin PRIQUEUE_CREATE:a joka määrittelee prioriteettijonon.

PRIQUEUE_CREATE (P, D)
PRIQUEUE_INSERT (P,x,pri)
PRIQUEUE_DELETEMIN (P)
PRIQUEUE_MIN (P)
PRIQUEUE_FREE (P)
PRIQUEUE_TYPE (P)
PRIQUEUE_LESS (P, x, y)
PRIQUEUE_SAME (P, x, y)
PRIQUEUE_EMPTY (P)

Yleisen prioriteettijonon käsittely

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

Int / integer - prioriteettijonon käsittely

Kokonaisluku-prioriteettijonon esittelyissä käytetään kokonaislukutyyppinä tyypinmäärittelyä INT_TYPE, joka on määritelty toteutuskohtaisesti. Tämä siksi, että esimerkiksi joissakin MS/DOS-ympäristössä toimivissa kääntäjissä int on 16-bittinen luku (enintään 2^16), mutta esim. cs:n gpc:ssä 32-bittinen (enintään 2^32). Kaikki INT_PRIQUEUE_XXX - aliohjelmat voidaan lyhentää IPQ_XXX; INT_PRIQUEUE_CREATE(P) voidaan siis kutsua myös IPQ_CREATE(P).

Float / real - prioriteettijonon käsittely

Liukuluku-prioriteettijonon esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE samoista syistä kuin kokonaisluku-prioriteettijonon kohdalla. FLOAT_PRIQUEUE_XXX voidaan lyhentää koodissa FPQ_XXX.

Char* / string[ ] - prioriteettijonon käsittely

Merkkijono-prioriteettijonon 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 CPQ_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 prioriteettijonon P, ja asettaa sen kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDPTR_DESC}. Mikäli prioriteettijono P ei ole tyhjä prioriteettijono, kaikki prioriteettijonossa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan prioriteettijonon P.

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 prioriteettijonoon P asettaen sille prioriteetin pri. Tyypitetyt operaatiot vievät prioriteettijonoon omaa tyyppiään olevan alkion.

Aikavaativuus : O(log 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);

Poistaa prioriteettijonosta P pieniprioriteettisimman alkion.

Aikavaativuus : O(log 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 prioriteettijonon P prioriteetiltään pienimmän alkion arvon.

Aikavaativuus : O(1)

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 prioriteettijonon P varaaman tilan ja asettaa prioriteettijonon P määrittelemättömäksi prioriteettijonoksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila. Jos void*- tai char*-prioriteettijonossa 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 prioriteettijonon P kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen prioriteettijono joudutaan luomaan. Uusi prioriteettijono Q, joka on samaa tyyppiä kuin prioriteettijono P luodaan komennolla PRIQUEUE_CREATE(Q, 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 prioriteettijonon 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 prioriteettijonon 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 TRUE (!=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 prioriteettijono P tyhjä prioriteettijono. C-kielessä palautusarvo on siis !=0, jos prioriteettijono on tyhjä, ja 0 mikäli prioriteettijono ei ole tyhjä. Pascalissa funktio palauttaa TRUE jos prioriteettijono on tyhjä ja FALSE, jos prioriteettijono ei ole tyhjä.

Aikavaativuus : O(1)