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

/**
 * Demonstracija upotrebe dve klase koje garantuju da ce njihove liste imati
 * samo razlicite elemente u sebi.
 */
public class ListeRazlicitihElemenata {

        static void listaRazlicitih() {
                ListaRazlicitihStringova list = new ListaRazlicitihStringova();
                list.dodaj("mango");
                list.dodaj("mango");
                list.dodaj("ananas");
                list.dodaj("mango");
                list.dodaj("nar");
                list.dodaj("banana");
                list.dodaj("jabuka");

                System.out.println(list);

                System.out.println("u listi mango:" + list.uListi("mango"));
                System.out.println("u listi krastavac:" + list.uListi("krastavac"));

                System.out.println();

                System.out.println("izbaci krastavac:" + list.izbaci("krastavac"));
                System.out.println("izbaci mango:" + list.izbaci("mango"));
                System.out.println(list);
        }

        static void listaSortiranihRazlicitih() {
                SortiranaListaRazlicitihStringova solist = new SortiranaListaRazlicitihStringova();
                solist.dodaj("mango");
                solist.dodaj("mango");
                solist.dodaj("ananas");
                solist.dodaj("mango");
                solist.dodaj("nar");
                solist.dodaj("banana");
                solist.dodaj("jabuka");

                System.out.println(solist);

                System.out.println("u listi mango:" + solist.uListi("mango"));
                System.out.println("u listi krastavac:" + solist.uListi("krastavac"));

                System.out.println();

                System.out.println("izbaci krastavac:" + solist.izbaci("krastavac"));
                System.out.println("izbaci mango:" + solist.izbaci("mango"));
                System.out.println(solist);

        }

        public static void main(String[] args) {
                System.out.println("Lista sa razlicitim elementima:");
                listaRazlicitih();

                System.out.println();

                System.out.println("Lista sa sortiranim razlicitim elementima:");
                listaSortiranihRazlicitih();
        }

}

/**
 * Povezana lista stringova u kojoj su svi stringovi razliciti.
 */
class ListaRazlicitihStringova {
        class Element {
                String info;
                Element veza;

                public Element(String s) {
                        this.info = s;
                        this.veza = null;
                }

                public String toString() {
                        return info + "";
                }
        }

        // pokazivac na prvi element liste
        Element prvi;

        /** Kreira praznu listu stringova. */
        public ListaRazlicitihStringova() {
                this.prvi = null;
        }

        /** Vraca da li je lista prazna */
        public boolean jePrazna() {
                return prvi == null;
        }

        public void stampajNaEkran() {
                if (prvi == null) {
                        Svetovid.out.println("Lista je prazna");
                } else {
                        Svetovid.out.println("Sadrzaj liste:");
                        Element tekuci = prvi;
                        while (tekuci != null) {
                                System.out.println(tekuci.info);
                                tekuci = tekuci.veza;
                        }
                        System.out.println();
                }
        }

        public String toString() {
                String rez = "Lista: [ ";
                Element tekuci = prvi;
                while (tekuci != null) {
                        rez += tekuci.info + " ";
                        tekuci = tekuci.veza;
                }
                rez += "]";
                return rez;
        }

        public void dodaj(String s) {
                if (!uListi(s)) {
                        Element novi = new Element(s);
                        novi.veza = prvi;
                        prvi = novi;
                }
        }

        /** Vraca da li String {@code s} postoji u listi. */
        public boolean uListi(String s) {
                Element tekuci = prvi;
                while (tekuci != null && tekuci.info.compareTo(s) < 0) {
                        tekuci = tekuci.veza;
                }

                // da li smo trenutno na elementu
                return tekuci != null && tekuci.info.equals(s);
        }

        /**
         * Izbacuje string 's' iz liste, naravno ako postoji i vraca da li je
         * operacija uspesno obavljena.
         */
        public boolean izbaci(String s) {
                // proverimo da li je prvi element
                if (prvi != null && prvi.info.equals(s)) {
                        prvi = prvi.veza;
                        return true;
                } else {
                        /* trazimo u ostatku liste */
                        Element tekuci, prethodni;
                        tekuci = prvi;
                        prethodni = null;
                        while (tekuci != null && !tekuci.info.equals(s)) {
                                /*
                                 * dok ne dodjemo do kraja liste ili ne nadjemo broj
                                 */
                                prethodni = tekuci;
                                tekuci = tekuci.veza;
                        }
                        if (tekuci != null) {
                                /*
                                 * znaci da nismo na kraju liste, odnosno da smo nasli element,
                                 * prevezemo listu oko elementa
                                 */
                                prethodni.veza = tekuci.veza;
                                return true;
                        } else {
                                return false;
                        }
                }
        }

}

/**
 * Sortirana povezana lista stringova u kojoj su svi stringovi razliciti.
 */
class SortiranaListaRazlicitihStringova {
        class Element {
                String info;
                Element veza;

                public Element(String s) {
                        this.info = s;
                        this.veza = null;
                }

                public String toString() {
                        return info + "";
                }
        }

        // pokazivac na prvi element liste
        Element prvi;

        /** Kreira praznu listu stringova. */
        public SortiranaListaRazlicitihStringova() {
                this.prvi = null;
        }

        /** Vraca da li je lista prazna */
        public boolean jePrazna() {
                return prvi == null;
        }

        public void stampajNaEkran() {
                if (prvi == null) {
                        Svetovid.out.println("Lista je prazna");
                } else {
                        Svetovid.out.println("Sadrzaj liste:");
                        Element tekuci = prvi;
                        while (tekuci != null) {
                                System.out.println(tekuci.info);
                                tekuci = tekuci.veza;
                        }
                        System.out.println();
                }
        }

        public String toString() {
                String rez = "Lista: [ ";
                Element tekuci = prvi;
                while (tekuci != null) {
                        rez += tekuci.info + " ";
                        tekuci = tekuci.veza;
                }
                rez += "]";
                return rez;
        }

        public void dodaj(String s) {
                if (prvi == null || prvi.info.compareTo(s) > 0) {
                        Element novi = new Element(s);
                        novi.veza = prvi;
                        prvi = novi;
                } else {
                        if (!prvi.info.equals(s)) {
                                Element prethodni = prvi;

                                while (prethodni.veza != null
                                                && prethodni.veza.info.compareTo(s) < 0) {
                                        prethodni = prethodni.veza;
                                }
                                if (prethodni.veza == null || !prethodni.veza.info.equals(s)) {
                                        Element novi = new Element(s);
                                        novi.veza = prethodni.veza;
                                        prethodni.veza = novi;
                                }
                        }
                }
        }

        /** Vraca da li String {@code s} postoji u listi. */
        public boolean uListi(String s) {
                Element tekuci = prvi;
                while (tekuci != null && tekuci.info.compareTo(s) < 0) {
                        tekuci = tekuci.veza;
                }

                // da li smo trenutno na elementu
                return tekuci != null && tekuci.info.equals(s);
        }

        /**
         * Izbacuje string 's' iz liste, naravno ako postoji i vraca da li je
         * operacija uspesno obavljena.
         */
        public boolean izbaci(String s) {
                // proverimo da li je prvi element
                if (prvi != null && prvi.info.equals(s)) {
                        prvi = prvi.veza;
                        return true;
                } else {
                        /* trazimo u ostatku liste */
                        Element tekuci, prethodni;
                        tekuci = prvi;
                        prethodni = null;
                        while (tekuci != null && tekuci.info.compareTo(s) < 0) {
                                /*
                                 * dok ne dodjemo do kraja liste ili ne nadjemo string
                                 */
                                prethodni = tekuci;
                                tekuci = tekuci.veza;
                        }
                        if (tekuci != null && tekuci.info.equals(s)) {
                                /*
                                 * znaci da nismo na kraju liste, odnosno da smo nasli element,
                                 * prevezemo listu oko elementa
                                 */
                                prethodni.veza = tekuci.veza;
                                return true;
                        } else {
                                return false;
                        }
                }
        }

}