From 16fbbd41c4a6d4435217daeaa9db4a51b35205b7 Mon Sep 17 00:00:00 2001 From: Doni Pracner Date: Thu, 7 May 2015 20:07:59 +0200 Subject: [PATCH] Skup, verzija 1.1.0. - dodato napraviNiz - dodat javadoc za sve metode - ubaceno tretiranje null parametara kao praznog skupa za neke metode - null sad eksplicitno ne moze biti element skupa --- kodovi/skup/Skup.java | 229 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 211 insertions(+), 18 deletions(-) diff --git a/kodovi/skup/Skup.java b/kodovi/skup/Skup.java index fbb525c..4937293 100644 --- a/kodovi/skup/Skup.java +++ b/kodovi/skup/Skup.java @@ -1,23 +1,46 @@ +import java.lang.reflect.Array; + /** * Tip podataka skup - predstavlja kolekciju razlicitih objekata zadatog tipa. - * + * Svi metodi garantuju da ce svi elementi u skupu biti razlicitu u skladu sa + * svojim {@code equals} metodom. Specijalno {@code null} ne moze biti element + * skupa. Skup je interno realizovan preko kruzne liste sa zaglavljem. + * + *

* Pomocni materijal na kursu SPA1, DMI, PMF, UNS www.dmi.rs + *

* - * v1.0.0 - * - * @param - tip podataka koji ce biti skladisten u instanci ove klase. + *

+ * v1.1.0 + *

+ * + * @param + * tip podataka koji ce biti skladisten u instanci ove klase. */ public class Skup { + /** + * Pojedinacni element u skupu, sadrzi pokazivac na sledeci element i + * informaciju o podatku koji se cuva. + * + */ class Element { T info; Element veza; + /** + * Kreira nov prazan element. + */ public Element() { - this.info = null; - this.veza = null; + this(null); } + /** + * Kreira element u kome se cuva prosledjeni {@code podatak} + * + * @param podatak + * informacija koja ce biti sacuvana u ovom elementu. + */ public Element(T podatak) { this.info = podatak; this.veza = null; @@ -27,9 +50,16 @@ public class Skup { Element zaglavlje; + // brojac elemenata u skupu + int brojac; + + /** + * Kreira nov prazan skup. + */ public Skup() { zaglavlje = new Element(); zaglavlje.veza = zaglavlje; + brojac = 0; } public String toString() { @@ -46,7 +76,36 @@ public class Skup { return rezultat + " }"; } + /** + * Vraca velicinu, odnosno broj elemenata skupa. + * + * @return broj elemenata skupa + */ + public int velicina() { + return brojac; + } + + /** + * Vraca da li je skup prazan, odnosno da li u njemu ima elemenata. + * + * @return da li u skupu ima elemenata + */ + public boolean jePrazan() { + return brojac > 0; + } + + /** + * Vraca da li dati element pripada skupu, a u skladu sa jednakoscu + * definisanom u metodu {@code equals} odgovarajuce klase. + * + * @param clan + * podatak za koji se proverava da li je vec u skupu. + * @return da li element vec postoji u skupu + */ public boolean pripada(T clan) { + if (clan == null) + return false; + zaglavlje.info = clan; Element tekuci = zaglavlje.veza; while (!tekuci.info.equals(clan)) { @@ -55,19 +114,46 @@ public class Skup { return tekuci != zaglavlje; } + /** + * Dodaje prosledjeni podatak u skup, ukoliko vec nije postoao i vraca da li + * ova operacija dodala element u skup. Jednakost elemenata se posmatra na + * osnovu metoda {@code equals} odgovarajuce klase. Specijalno {@code null} + * ne moze biti element skupa i bice vraceno false posto element nije + * ubacen, iako takav element nije postojao u skupu. + * + * @param clan + * podatak koji se zeli ubaciti u skup + * @return da li je element uspesno ubacen + */ public boolean ubaci(T clan) { + // ne mozemo ubaciti null element + if (clan == null) + return false; if (!pripada(clan)) { Element novi = new Element(); novi.info = clan; novi.veza = zaglavlje.veza; zaglavlje.veza = novi; + brojac++; return true; } else { return false; } } + /** + * Izbacuje prosledjeni podatak iz skupa, ukoliko on je bio u skupu. + * Jednakost elemenata se posmatra na osnovu metoda {@code equals} + * odgovarajuce klase. + * + * @param clan + * podatak koji se zeli izbaciti iz skupa + * @return da li je element uspesno izbacen + */ public boolean izbaci(T clan) { + // ne mozemo ubaciti null element + if (clan == null) + return false; zaglavlje.info = clan; Element prethodni = zaglavlje; while (!prethodni.veza.info.equals(clan)) { @@ -75,13 +161,25 @@ public class Skup { } if (prethodni.veza != zaglavlje) { prethodni.veza = prethodni.veza.veza; + brojac--; return true; } else { return false; } } + /** + * Dodaje sve elemente prosledjenog skupa u ovaj skup, odnosno one koji vec + * nisu bili u skupu. Jednakost elemenata se posmatra na osnovu metoda + * {@code equals} odgovarajuce klase. + * + * @param skup + * skup iz koga se zele ubaciti svi elementi u ovaj skup + */ public void ubaciSve(Skup skup) { + if (skup == null) + return; + Element tekuci = skup.zaglavlje.veza; while (tekuci != skup.zaglavlje) { ubaci(tekuci.info); @@ -89,6 +187,19 @@ public class Skup { } } + /** + * Vraca novi skup koji je jednak uniji ovog skupa i prosledjenog + * skupa.Tacnije poziv {@code a.unija(b)} je matematicki ekvivalentan sa: + * + * 
+	 * a ∪ b
+	 *
+ * + * + * @param drugi + * skup sa kojim se pravi unija + * @return novi skup koji je unija ovog i prosledjenog skupa + */ public Skup unija(Skup drugi) { Skup rezultat = new Skup(); rezultat.ubaciSve(this); @@ -96,31 +207,85 @@ public class Skup { return rezultat; } + /** + * Vraca novi skup koji predstavlja presek ovog i prosledjenog skupa.Tacnije + * poziv {@code a.presek(b)} je matematicki ekvivalentan sa: + * + * 
+	 * a ∩ b
+	 *
+ * + * Specijalno ako je drugi skup {@code null} bice tumacen kao prazan skup, + * odnosno i rezultat ce biti prazan skup. + * + * @param drugi + * skup sa kojim se pravi presek. + * @return presek ova dva skupa + */ public Skup presek(Skup drugi) { Skup rezultat = new Skup(); - Element tekuci = zaglavlje.veza; - while (tekuci != zaglavlje) { - if (drugi.pripada(tekuci.info)) { - rezultat.ubaci(tekuci.info); + if (drugi != null) { + Element tekuci = zaglavlje.veza; + while (tekuci != zaglavlje) { + if (drugi.pripada(tekuci.info)) { + rezultat.ubaci(tekuci.info); + } + tekuci = tekuci.veza; } - tekuci = tekuci.veza; } return rezultat; } - + + /** + * Vraca novi skup koji predstavlja razliku ovog i prosledjenog skupa. + * Tacnije od ovog skupa ce biti oduzeti elementi prosledjenog, tj poziv + * {@code a.razlika(b)} je matematicki ekvivalentan sa: + * + * 
+	 * a \ b
+	 *
+ * + * Specijalno ako je drugi skup {@code null} bice tumacen kao prazan skup, + * odnosno rezultat ce biti jednak ovom skupu. + * + * @param drugi + * skup koji se oduzima + * @return razlika ovog skupa i prosledjenog + */ public Skup razlika(Skup drugi) { Skup rezultat = new Skup(); - Element tekuci = zaglavlje.veza; - while (tekuci != zaglavlje) { - if (!drugi.pripada(tekuci.info)) { - rezultat.ubaci(tekuci.info); + if (drugi != null) { + Element tekuci = zaglavlje.veza; + + while (tekuci != zaglavlje) { + if (!drugi.pripada(tekuci.info)) { + rezultat.ubaci(tekuci.info); + } + tekuci = tekuci.veza; } - tekuci = tekuci.veza; - } + } else + rezultat.ubaciSve(this); return rezultat; } + /** + * Vraca da li je ovaj skup podskup prosledjenog skupa. Tacnije poziv + * {@code a.podskup(b)} je matematicki ekvivalentan sa: + * + * 
+	 * a ⊆ b
+	 *
+ * + * Specijalno ako je drugi skup {@code null} bice tumacen kao prazan skup, + * odnosno i rezultat ce biti {@code true} samo ako je i ovaj skup prazan. + * + * @param drugi + * skup za koji se proverava da li je ovaj podskup + * @return da li je ovaj skup podskup prosledjenog skupa + */ public boolean podskupOd(Skup drugi) { + if (drugi == null) + return brojac == 0; Element tekuci = zaglavlje.veza; while (tekuci != zaglavlje) { if (!drugi.pripada(tekuci.info)) { @@ -130,4 +295,32 @@ public class Skup { } return true; } + + /** + * Vraca niz koji se sastoji od elemenata koji su trenutno u skupu. Ukoliko + * je u pitanju prazan skup vratice {@code null}, tako da je pozeljno + * proveriti pre poziva metoda da li je skup velicine 0, ili naknadno + * proveravati da li je dobijena vrednost null. + * + * @return niz koji predstavlja elemente skupa, ili null ako je skup prazan + */ + public T[] napraviNiz() { + if (brojac > 0) { + // zbog prisustva opstih tipova, niz se pravi na komplikovaniji + // nacin nego inace + @SuppressWarnings("unchecked") + T[] rez = (T[]) Array + .newInstance(zaglavlje.info.getClass(), brojac); + + int i = 0; + Element tekuci = zaglavlje.veza; + while (tekuci != zaglavlje) { + rez[i++] = tekuci.info; + tekuci = tekuci.veza; + } + return rez; + } else { + return null; + } + } } -- 2.17.1