Novi primer: ListaListi

[spa1-materijali.git] / kodovi / liste / ListaListi.java

/*
 * Primer klase koja u sebi sadrzi jednostruko povezanu listu, a u kojoj
 * svaki element takodje ima pokazivac na jos po jednu nezavisnu listu. *
 */

/**
 * Glavni program koji ilustruje koriscenje klase SadrzajOrmana.
 *
 */
public class ListaListi {
        public static void main(String[] args) {
                SadrzajGrupeOrmana so = new SadrzajGrupeOrmana();

                System.out.println(so);

                so.dodajOrman("donji 1");
                so.dodajPosudu("donji 1", "plitki tanjir");
                so.dodajPosudu("donji 1", "duboki tanjir");
                so.dodajPosudu("donji 1", "duboki tanjir");
                so.dodajPosudu("donji 1", "plitki tanjir");
                so.dodajPosudu("donji 1", "plitki tanjir");
                so.dodajPosudu("donji 1", "duboki tanjir");
                so.dodajPosudu("donji 1", "plitki tanjir");

                so.dodajOrman("donji 1");

                System.out.println(so);

                so.dodajPosudu("donji 2", "tiganj za palacinke");
                so.dodajPosudu("gornji", "casa");
                so.dodajPosudu("gornji", "casa");
                so.dodajPosudu("gornji", "solja");
                so.dodajPosudu("gornji", "slanik");

                System.out.println(so);

                System.out.println("Ukloni 'plitki tanjir':"
                                + so.ukloniPosudu("plitki tanjir"));
                System.out.println(so);

                System.out.println("Ukloni 'tiganj za palacinke':"
                                + so.ukloniPosudu("tiganj za palacinke"));
                System.out.println(so);

                System.out.println("Opet ukloni 'tiganj za palacinke':"
                                + so.ukloniPosudu("tiganj za palacinke"));
                System.out.println(so);
        }
}

/**
 * Klasa koja predstavlja sadrzaj jedne grupe ormana. Za svaki orman se pamti
 * njegov naziv i spisak posuda koje su u njemu. Svi ormani se moraju zvati
 * razlicito. Posude su predstavljene svojim nazivima.
 * 
 *
 */
class SadrzajGrupeOrmana {

        // pokazivac na prvi orman u listi
        private Orman prviOrman;

        /**
         * Klasa koja predstavlja pojedinacni orman.
         * 
         */
        class Orman {
                String naziv;
                Orman veza;
                Posuda sadrzaj;

                public Orman(String naziv) {
                        this.naziv = naziv;
                        this.veza = null;
                }

                public String toString() {
                        String rez = "[" + naziv + ":";
                        Posuda tek = sadrzaj;
                        if (tek != null) {
                                rez += " " + tek;
                                tek = tek.veza;
                                while (tek != null) {
                                        rez += ", " + tek;
                                        tek = tek.veza;
                                }
                        }
                        rez += " ]";
                        return rez;
                }
        }

        /**
         * Klasa predstavlja jednu posudu.
         */
        class Posuda {
                String naziv;
                Posuda veza;

                public Posuda(String posuda) {
                        this.naziv = posuda;
                        this.veza = null;
                }

                public String toString() {
                        return naziv;
                }
        }

        public String toString() {
                String rez = "Ormani:";
                Orman tek = prviOrman;
                while (tek != null) {
                        rez += " " + tek;
                        tek = tek.veza;
                }
                return rez;
        }

        /**
         * Dodaje novi orman u listu ormana, ako vec ne postoji
         */
        public void dodajOrman(String noviNaziv) {
                // dodajemo samo ako ne postoji
                if (!postojiOrman(noviNaziv)) {
                        Orman novi = new Orman(noviNaziv);
                        novi.veza = prviOrman;
                        prviOrman = novi;
                }
        }

        /**
         * Vraca da li trazeni orman vec postoji
         */
        public boolean postojiOrman(String trazeni) {
                Orman tekuci = prviOrman;
                while (tekuci != null) {
                        if (tekuci.naziv.equals(trazeni)) {
                                return true;
                        }
                        tekuci = tekuci.veza;
                }
                return false;
                // alternativno
                // return nadjiOrman(trazeni) != null;
        }

        // interni metod koji vraca pokazivac na odg. orman
        private Orman nadjiOrman(String orman) {
                Orman tekuci = prviOrman;
                while (tekuci != null) {
                        if (tekuci.naziv.equals(orman)) {
                                return tekuci;
                        }
                        tekuci = tekuci.veza;
                }
                return null;
        }

        /**
         * Dodaje posudu u orman. Ako orman nije postojao, bice dodat.
         */
        public void dodajPosudu(String orman, String posuda) {
                Orman cilj = nadjiOrman(orman);
                if (cilj == null) {
                        dodajOrman(orman);
                        cilj = nadjiOrman(orman);
                }
                // moze biti vise istih posuda
                // ne proveravamo nista
                Posuda nova = new Posuda(posuda);
                nova.veza = cilj.sadrzaj;
                cilj.sadrzaj = nova;
        }
        
        /**
         * Vraca da li se posuda sa datim nazivom nalazi u ormanu sa datim imenom.
         */
        public boolean postojiPosudaUOrmanu(String orman, String posuda) {
                Orman o = nadjiOrman(orman);
                return postojiPosudaUOrmanu(o, posuda);
        }

        // interni metod koji u sustini resava problem
        private boolean postojiPosudaUOrmanu(Orman or, String posuda) {
                if (or != null) {
                        Posuda trenutna = or.sadrzaj;
                        while (trenutna != null && !trenutna.naziv.equals(posuda)) {
                                trenutna = trenutna.veza;
                        }
                        return trenutna != null;
                }
                return false;
        }

        /**
         * Vraca orman u kome se nalazi trazena posuda. Ako ima vise ovakvih ormana
         * vratice se prvi u kome je nadjena trazena posuda. Ako nema ovakve posude
         * ni u jednom ormanu, metod vraca `null`.
         */
        public String nadjiOrmanSaPosudom(String posuda) {
                Orman trenutni = prviOrman;
                while (trenutni != null) {
                        if (postojiPosudaUOrmanu(trenutni, posuda)) {
                                return trenutni.naziv;
                        }
                        trenutni = trenutni.veza;
                }
                return null;
        }

        /**
         * Uklanja posudu iz datog ormana. Ako orman ostane prazan, uklanja i orman.
         */
        public boolean ukloniPosudu(String orman, String posuda) {
                Orman cilj = nadjiOrman(orman);

                return ukloniPosudu(cilj, posuda);
        }

        // interni metod koji prima pokazivac na unutrasnju strukturu
        private boolean ukloniPosudu(Orman ormanpok, String posuda) {
                boolean nadjena = false;
                if (ormanpok != null) {
                        // da li je prva?
                        if (ormanpok.sadrzaj != null
                                        && ormanpok.sadrzaj.naziv.equals(posuda)) {
                                ormanpok.sadrzaj = ormanpok.sadrzaj.veza;
                                nadjena = true;
                        } else {
                                // nije prva
                                Posuda preth = ormanpok.sadrzaj;
                                while (preth.veza != null && !preth.veza.naziv.equals(posuda)) {
                                        preth = preth.veza;
                                }
                                if (preth.veza != null) {
                                        preth.veza = preth.veza.veza;
                                        nadjena = true;
                                }
                        }
                }
                if (nadjena) {
                        // ako je bilo promene proveriti i orman
                        if (ormanpok.sadrzaj == null) {
                                ukloniOrman(ormanpok.naziv);
                        }
                }
                return nadjena;
        }

        /**
         * Uklanja posudu sa datim nazivom iz bilo kog ormana
         */
        public boolean ukloniPosudu(String posuda) {
                Orman tekuci = prviOrman;
                // pokusavamo da uklonimo iz svakog ormana
                // prekidamo ako uspemo
                while (tekuci != null && !ukloniPosudu(tekuci, posuda)) {
                        tekuci = tekuci.veza;
                }
                // ako smo prosli celu listu -> nismo uklonili nista
                return tekuci != null;
        }

        /**
         * Pokusava da uklani orman sa datim nazivom i vraca da
         * li je uspesno uklonjen.
         */
        public boolean ukloniOrman(String naziv) {
                // provera da li uopste ima ormana
                if (prviOrman == null) {
                        return false;
                }
                // proverimo da li je prvi
                if (prviOrman.naziv.equals(naziv)) {
                        prviOrman = prviOrman.veza;
                        return true;
                }
                // trazimo u ostatku
                Orman prethodni = prviOrman;
                while (prethodni.veza != null) {
                        if (prethodni.veza.naziv.equals(naziv)) {
                                prethodni.veza = prethodni.veza.veza;
                                return true;
                        }
                        prethodni = prethodni.veza;
                }
                return false;
        }
}