Joukon funktioiden esittelyt

Joukkoa DS (Disjoint Set) voidaan käsitellä yleisen joukon avulla tietämättä joukon oikeaa tyyppiä. Kuitenkin usein tarvitaan joukkoja jotka sisältävät jotakin määrätyntyyppistä tietoa. Mahdollisimman erityyppisten tilanteiden kattavuuden vuoksi tietorakennekirjastoa varten on toteutettu neljä erilaista tyypitettyä joukkotyyppiä : kokonaislukujoukko, jonka alkiot ovat int / integer - arvoja, liukulukujoukko (sisältää float / real – tyyppisiä alkioita), merkkijonojoukko (char* / string[ ]) ja osoitinjoukko (void* / pointer – tyyppisiä alkioita).

Tässä osassa on esitelty yleisen, kokonaisluku-, liukuluku- ja merkkijonojoukon funktiot. Osoitinpuusta enemmän osuudessa "Kirjaston laajentaminen". Funktioista / proseduureista esitellään aina ensiksi C-kieliset, sitten Pascal-kieliset versiot. Kaikkien funktioiden käytössä oletetaan että joukko on määritelty. Mikäli parametrina annettava joukko DS on määrittelemätön, on aliohjelmien toiminta määrittelemätöntä, lukuunottamatta tietenkin DSET_CREATE:a joka määrittelee joukon.

DSET_CREATE (DS, D)
DSET_FREE (DS)
DSET_TYPE (DS)
DSET_LESS (DS, x, y)
DSET_SAME (DS, x, y)
DSET_EMPTY (DS)
DSET_ASSIGN (DS1,DS2)
DSET_UNION (DS1,DS2)
DSET_INTERSECTION (DS1,DS2)
DSET_DIFFERENCE (DS1,DS2)
DSET_INSERT (DS,x)
DSET_DELETE (DS,x)
DSET_MEMBER (DS,x)
DSET_MIN (DS)
DSET_MAX (DS)
DSET_EQUAL (DS1,DS2)
DSET_PRINT (DS)

Yleisen joukon käsittely

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

Int / integer - joukon käsittely

Kokonaislukujoukon 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_DSET_XXX - aliohjelmat voidaan lyhentää IDS_XXX; INT_DSET_CREATE(DS):a voidaan siis kutsua myös IDS_CREATE(DS).

Float / real - joukon käsittely

Liukulukujoukon esittelyissä käytetään liukulukutyyppiä FLOAT_TYPE, samoista syistä kuin kokonaislukujoukon kohdalla. FLOAT_DSET_XXX voidaan lyhentää koodissa FDS_XXX.

Char* / string[ ] - joukon käsittely

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

DSET_CREATE (DS, D)
void DSET_CREATE (DSET DS, DESCRIPTOR D);

void INT_DSET_CREATE(DSET DS);

void FLOAT_DSET_CREATE(DSET DS);

void CHARP_DSET_CREATE(DSET DS);

void VOIDPTR_DSET_CREATE(DSET DS);

procedure DSET_CREATE (var DS:DSET; D:DESCRIPTOR);

procedure INT_DSET_CREATE (var DS:DSET);

procedure FLOAT_DSET_CREATE (var DS:DSET);

procedure CHARP_DSET_CREATE (var DS:DSET);

procedure VOIDPTR_DSET_CREATE (var DS:DSET);

Yleinen DSET_CREATE(DS, D) muodostaa tyhjän joukon DS, ja asettaa joukon kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDPTR_DESC}. Mikäli joukko DS ei ole tyhjä joukko, kaikki joukossa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan joukon DS.

Aikavaativuus : O(1)

DSET_INSERT (DS, x)
void DSET_INSERT (DSET DS, ELEMENT x);

void INT_DSET_INSERT (DSET DS, INT_TYPE x);

void FLOAT_DSET_INSERT (DSET DS, FLOAT_TYPE x);

void CHARP_DSET_INSERT (DSET DS, char* x);

void VOIDPTR_DSET_INSERT (DSET DS, void* x);

procedure DSET_INSERT(DS:DSET; x:ELEMENT);

procedure INT_DSET_INSERT(DS:DSET; x:INT_TYPE);

procedure FLOAT_DSET_INSERT(DS:DSET; x:FLOAT_TYPE);

procedure CHARP_DSET_INSERT(DS:DSET; x:CHARP_TYPE);

procedure VOIDPTR_DSET_INSERT(DS:DSET; x:pointer);

Lisää joukkoon DS elementin x. Jos elementti on jo joukossa, ei tee mitään. Tyypitetyt operaatiot vievät joukkoon omaa tyyppiään olevan alkion.

Aikavaativuus : O(log n)

DSET_MEMBER(DS, x)
int DSET_MEMBER(DSET DS, ELEMENT x);

int INT_DSET_MEMBER(DSET DS, INT_TYPE x);

int FLOAT_DSET_MEMBER(DSET DS, FLOAT_TYPE x);

int CHARP_DSET_MEMBER(DSET DS, char* x);

int VOIDPTR_DSET_MEMBER(DSET DS, void* x);

function DSET_MEMBER (DS:DSET; x:ELEMENT):boolean;

function INT_DSET_MEMBER(DS:DSET;x:INT_TYPE):boolean;

function FLOAT_DSET_MEMBER(DS:DSET;x:FLOAT_TYPE):boolean;

function CHARP_DSET_MEMBER(DS:DSET;x:CHARP_TYPE):boolean;

function VOIDPTR_DSET_MEMBER(DS:DSET;x:CHARP_TYPE):boolean;

Palauttaa tiedon siitä löytyykö joukosta DS elementti x. Jos elementti löytyy, palauttaa arvon TRUE (!=0), muuten arvon FALSE (0).

Aikavaativuus : O(log n)

DSET_DELETE (DS, x)
void DSET_DELETE (DSET DS, ELEMENT x);

void INT_DSET_DELETE (DSET DS, INT_TYPE x);

void FLOAT_DSET_DELETE (DSET DS, FLOAT_TYPE x);

void CHARP_DSET_DELETE (DSET DS, char* x);

void VOIDPTR_DSET_DELETE (DSET DS, void* x);

procedure DSET_DELETE (DS:DSET, x:ELEMENT);

procedure INT_DSET_DELETE (DS:DSET, x:INT_TYPE);

procedure FLOAT_DSET_DELETE (DS:DSET, x:FLOAT_TYPE);

procedure CHARP_DSET_DELETE (DS:DSET, x:CHARP_TYPE);

procedure VOIDPTR_DSET_DELETE (DS:DSET, x:pointer);

Poistaa joukosta DS elementin x. Jos elementtiä ei ole joukossa, ei tee mitään.

Aikavaativuus : O(log n)

DSET_MIN(DS)
ELEMENT DSET_MIN (DSET DS);

INT_TYPE INT_DSET_MIN (DSET DS);

FLOAT_TYPE FLOAT_DSET_MIN (DSET DS)

char* CHARP_DSET_MIN (DSET DS)

void* VOIDPTR_DSET_MIN (DSET DS)

function DSET_MIN(DS:DSET):ELEMENT;

function INT_DSET_MIN(DS:DSET):INT_TYPE;

function FLOAT_DSET_MIN(DS:DSET):FLOAT_TYPE;

function CHARP_DSET_MIN(DS:DSET):CHARP_TYPE;

function VOIDPTR_DSET_MIN(DS:DSET):pointer;

Palauttaa joukon DS pienimmän alkion. Yleinen funktio DSET_MIN(DS) palauttaa ELEMENT-tyyppiä olevan alkion ja tyypitetyt funktiot omaa tyyppiään olevan alkion.

Aikavaativuus : O(log n)

DSET_MAX(DS)

ELEMENT DSET_MAX (DSET DS)

INT_TYPE INT_DSET_MAX (DSET DS)

FLOAT_TYPE FLOAT_DSET_MAX (DSET DS)

char* CHARP_DSET_MAX (DSET DS)

void* VOIDPTR_DSET_MAX (DSET DS)

function DSET_MAX(DS:DSET):ELEMENT;

function INT_DSET_MAX(DS:DSET):INT_TYPE;

function FLOAT_DSET_MAX(DS:DSET):FLOAT_TYPE;

function CHARP_DSET_MAX(DS:DSET):CHARP_TYPE;

function VOIDPTR_DSET_MAX(DS:DSET):pointer;

Palauttaa joukon DS suurimman alkion. Yleinen funktio DSET_MAX(DS) palauttaa ELEMENT-tyyppiä olevan alkion ja tyypitetyt funktiot omaa tyyppiään olevan alkion.

Aikavaativuus : O(log n)

DSET_ASSIGN(DS1,DS2)
void DSET_ASSIGN(DSET DS1, DSET DS2);

void INT_DSET_ASSIGN(DSET DS1, DSET DS2);

void FLOAT_DSET_ASSIGN(DSET DS1, DSET DS2);

void CHARP_DSET_ASSIGN(DSET DS1, DSET DS2);

void VOIDPTR_DSET_ASSIGN(DSET DS1, DSET DS2);

procedure DSET_ASSIGN(DS1:DSET;DS2:DSET);

procedure INT_DSET_ASSIGN(DS1:DSET;DS2:DSET);

procedure FLOAT_DSET_ASSIGN(DS1:DSET;DS2:DSET);

procedure CHARP_DSET_ASSIGN(DS1:DSET;DS2:DSET);

procedure VOIDPTR_DSET_ASSIGN(DS1:DSET;DS2:DSET);

Kopioi joukkoon DS1 kaikki joukon DS2 alkiot. Joukon DS1 tyypiksi tulee joukon DS2 tyyppi. Jos joukko DS1 ei ole tyhjä, entiset tiedot tuhoutuvat!

Aikavaativuus : O(n)

DSET_UNION(DS1,DS2)

DSET DSET_UNION (DSET DS1, DSET DS2);

DSET INT_DSET_UNION(DSET DS1, DSET DS2);

DSET FLOAT_DSET_UNION(DSET DS1, DSET DS2);

DSET CHARP_DSET_UNION(DSET DS1, DSET DS2);

DSET VOIDPTR_DSET_UNION(DSET DS1, DSET DS2);

function DSET_UNION(DS1:DSET;DS2:DSET):DSET;

function INT_DSET_UNION(DS1:DSET;DS2:DSET):DSET;

function FLOAT_DSET_UNION(DS1:DSET;DS2:DSET):DSET;

function CHARP_DSET_UNION(DS1:DSET;DS2:DSET):DSET;

function VOIDPTR_DSET_UNION(DS1:DSET;DS2:DSET):DSET;

Palauttaa joukkojen DS1 ja DS2 yhdisteen muuttamatta kuitenkaan alkuperäisiä joukkoja. Palautettava joukko on joukon DS1 tyyppiä.

Aikavaativuus : O(n)

DSET_DIFFERENCE(DS1,DS2)

DSET DSET_DIFFERENCE(DSET DS1, DSET DS2);

DSET INT_DSET_DIFFERENCE(DSET DS1, DSET DS2);

DSET FLOAT_DSET_DIFFERENCE(DSET DS1, DSET DS2);

DSET CHARP_DSET_DIFFERENCE(DSET DS1, DSET DS2);

DSET VOIDPTR_DSET_DIFFERENCE(DSET DS1, DSET DS2);

function DSET_DIFFERENCE(DS1:DSET;DS2:DSET):DSET;

function INT_DSET_DIFFERENCE(DS1:DSET;DS2:DSET):DSET;

function FLOAT_DSET_DIFFERENCE(DS1:DSET;DS2:DSET):DSET;

function CHARP_DSET_DIFFERENCE(DS1:DSET;DS2:DSET):DSET;

function VOIDPTR_DSET_DIFFERENCE(DS1:DSET;DS2:DSET):DSET;

Palauttaa joukkojen DS1 ja DS2 erotuksen muuttamatta kuitenkaan alkuperäisiä joukkoja, ts. DS1 pois DS2. Palautettava joukko on joukon DS1 tyyppiä.

Aikavaativuus : O(n)

DSET_INTERSECTION(DS1,DS2)

DSET DSET_INTERSECTION(DSET DS1, DSET DS2);

function DSET_INTERSECTION(DSET DS1, DSET DS2):DSET;

Palauttaa joukkojen DS1 ja DS2 leikkauksen muuttamatta kuitenkaan alkuperäisiä joukkoja. Palautettava joukko on joukon DS1 tyyppiä.

Aikavaativuus : O(n)

DSET_EQUAL(DS1,DS2)
int DSET_EQUAL (DSET DS1, DSET DS2)

int INT_DSET_EQUAL(DSET DS1, DSET DS2);

int FLOAT_DSET_EQUAL(DSET DS1, DSET DS2);

int CHARP_DSET_EQUAL(DSET DS1, DSET DS2);

int VOIDPTR_DSET_EQUAL(DSET DS1, DSET DS2);

funtion DSET_EQUAL (DS1:DSET;DS2:DSET):boolean;

funtion INT_DSET_EQUAL (DS1:DSET;DS2:DSET):boolean;

funtion FLOAT_DSET_EQUAL (DS1:DSET;DS2:DSET):boolean;

funtion CHARP_DSET_EQUAL (DS1:DSET;DS2:DSET):boolean;

funtion VOIDPTR_DSET_EQUAL (DS1:DSET;DS2:DSET):boolean;

Palauttaa tiedon siitä, ovatko joukot DS1 ja DS2 samat, siis sisältävätkö ne samat alkiot. Mikäli joukoissa on täsmälleen samat alkiot, palauttaa TRUE (!=0), mutta jos joukot eroavat toisistaan ollenkaan, FALSE (0).

Aikavaativuus : O(n)

DSET_PRINT (DS)
void DSET_PRINT(DSET DS)

procedure DSET_PRINT (DS:DSET);

Tulostaa ruudulle joukon alkiot välilyönneillä erotettuina.

Aikavaativuus : O(n)

DSET_FREE (DS)
void DSET_FREE (DSET DS);

procedure DSET_FREE (var DS:DSET);

Vapauttaa kaiken joukon DS varaaman tilan ja asettaa joukon DS määrittelemättömäksi joukoksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila. Esimerkki : Pascal / C

Aikavaativuus : O(n)

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

DSET_TYPE (DS)
DESCRIPTOR DSET_TYPE (DSET DS);

function DSET_TYPE (DS:DSET) : DESCRIPTOR;

Palauttaa joukon DS kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen joukko joudutaan luomaan. Uusi joukko M, joka on samaa tyyppiä kuin joukko DS, luodaan komennolla DSET_CREATE(M, DSET_TYPE(DS));.

Aikavaativuus : O(1)

DSET_LESS (DS, x, y)

DSET_SAME (DS, x, y)
int DSET_LESS (DSET DS, ELEMENT x, ELEMENT y);

int DSET_SAME (DSET DS, ELEMENT x, ELEMENT y);

function DSET_LESS (DS:DSET; x,y:ELEMENT) : boolean;

function DSET_SAME (DS:DSET; x,y:ELEMENT) : boolean;

Palauttavat tiedon siitä ovatko joukon DS kuvaajan 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 joukon DS alkiot (muttei niiden ole pakko olla joukon DS alkioita). Jos x=y, niin DSET_SAME palauttaa siis TRUE (!=0), ja jos x<y niin DSET_LESS palauttaa FALSE (0). Merkkijonojoukossa vertaillaan merkkijonojen välistä aakkosjärjestystä.

Aikavaativuus : O(1)

DSET_EMPTY (DS)
int DSET_EMPTY (DSET DS);

int INT_DSET_EMPTY(DSET DS);

int FLOAT_DSET_EMPTY(DSET DS);

int CHARP_DSET_EMPTY(DSET DS);

int VOIDPTR_DSET_EMPTY(DSET DS);

function DSET_EMPTY (DS:DSET) : boolean;

function INT_DSET_EMPTY (DS:DSET) : boolean;

function FLOAT_DSET_EMPTY (DS:DSET) : boolean;

function CHARP_DSET_EMPTY (DS:DSET) : boolean;

function VOIDPTR_DSET_EMPTY (DS:DSET) : boolean;

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

Aikavaativuus : O(1)