Skup v1.1.1

[spa1-materijali.git] / kodovi / skup / Skup.java

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.
 * 
 * <p>
 * Pomocni materijal na kursu SPA1, DMI, PMF, UNS www.dmi.rs
 * </p>
 * 
 * <p>
 * <strong>v1.1.1</strong>
 * </p>
 * 
 * @param <T>
 *            tip podataka koji ce biti skladisten u instanci ove klase.
 */
public class Skup<T> {

        /**
         * 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(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;
                }

        }

        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() {
                String rezultat = "Skup {";
                Element tekuci = zaglavlje.veza;
                if (tekuci != zaglavlje) {
                        rezultat += " " + tekuci.info;
                        tekuci = tekuci.veza;
                }
                while (tekuci != zaglavlje) {
                        rezultat += ", " + tekuci.info;
                        tekuci = tekuci.veza;
                }
                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)) {
                        tekuci = tekuci.veza;
                }
                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)) {
                        prethodni = prethodni.veza;
                }
                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<T> skup) {
                if (skup == null)
                        return;

                Element tekuci = skup.zaglavlje.veza;
                while (tekuci != skup.zaglavlje) {
                        ubaci(tekuci.info);
                        tekuci = tekuci.veza;
                }
        }

        /**
         * Vraca novi skup koji je jednak uniji ovog skupa i prosledjenog
         * skupa.Tacnije poziv {@code a.unija(b)} je matematicki ekvivalentan sa:
         * 
         * <pre>
         * a &cup; b
         * </pre>
         * 
         * 
         * @param drugi
         *            skup sa kojim se pravi unija
         * @return novi skup koji je unija ovog i prosledjenog skupa
         */
        public Skup<T> unija(Skup<T> drugi) {
                Skup<T> rezultat = new Skup<T>();
                rezultat.ubaciSve(this);
                rezultat.ubaciSve(drugi);
                return rezultat;
        }

        /**
         * Vraca novi skup koji predstavlja presek ovog i prosledjenog skupa.Tacnije
         * poziv {@code a.presek(b)} je matematicki ekvivalentan sa:
         * 
         * <pre>
         * a &cap; b
         * </pre>
         * 
         * 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<T> presek(Skup<T> drugi) {
                Skup<T> rezultat = new Skup<T>();
                if (drugi != null) {
                        Element tekuci = zaglavlje.veza;
                        while (tekuci != zaglavlje) {
                                if (drugi.pripada(tekuci.info)) {
                                        rezultat.ubaci(tekuci.info);
                                }
                                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:
         * 
         * <pre>
         * a \ b
         * </pre>
         * 
         * 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<T> razlika(Skup<T> drugi) {
                Skup<T> rezultat = new Skup<T>();
                if (drugi != null) {
                        Element tekuci = zaglavlje.veza;

                        while (tekuci != zaglavlje) {
                                if (!drugi.pripada(tekuci.info)) {
                                        rezultat.ubaci(tekuci.info);
                                }
                                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:
         * 
         * <pre>
         * a &sube; b
         * </pre>
         * 
         * 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<T> drugi) {
                if (drugi == null)
                        return brojac == 0;
                Element tekuci = zaglavlje.veza;
                while (tekuci != zaglavlje) {
                        if (!drugi.pripada(tekuci.info)) {
                                return false;
                        }
                        tekuci = tekuci.veza;
                }
                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;
                }
        }
}