liste, dodata jos dva programa

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

import org.svetovid.io.SvetovidIOException;

/**
 * Primer razlicitih operacija nad listama. Program je predstavljen kao
 * interaktivni meni radi boljeg ilustrovanja operacija i njihovog ucinka.
 */
public class ListePrimeriOperacija {
        static ListaBrojevaBr lista;

        public static void main(String[] args) {
                // inicijalizujemo listu
                lista = new ListaBrojevaBr();

                char menu = 'a';

                while (menu != 'Q') {
                        System.out.println();
                        System.out.println("Ilustracija rada sa listama brojeva");
                        System.out.println("======================================");
                        System.out.println("s-Stampa");
                        System.out.println("u-Unos liste");
                        System.out.println("k-Stampanje k-tog elementa");
                        System.out.println("d-dodavanje elementa na pocetak");
                        System.out.println("o-dodavanje elementa na k-to mesto");
                        System.out.println("i-Izbacivanje br iz liste");
                        System.out.println("v-Izbacivanje svih br iz liste");
                        System.out.println("e-Izbacivanje k-tog elementa");
                        System.out.println("m-Minimalni broj u listi");
                        System.out.println("p-Pretraga elementa u listi");
                        System.out.println();
                        System.out.println("q-Kraj rada (Quit)");
                        menu = Svetovid.in.readChar();
                        menu = Character.toUpperCase(menu);
                        switch (menu) {
                        case 'S':
                                lista.stampajNaEkran();
                                break;
                        case 'U':
                                unosBrojeva();
                                break;
                        case 'D':
                                int broj = Svetovid.in.readInt("Broj koji dodajete:");
                                lista.dodajNaPocetak(broj);
                                break;
                        case 'O':
                                broj = Svetovid.in.readInt("Broj koji dodajete:");
                                int pos = Svetovid.in.readInt("Pozicija na koju dodajete:");
                                lista.dodaj(broj, pos);
                                break;
                        case 'I':
                                izbacivanjeEl();
                                break;
                        case 'V':
                                izbacivanjeElSvi();
                                break;
                        case 'E':
                                izbacivanjeK();
                                break;
                        case 'K':
                                stampajK(lista);
                                break;
                        case 'M':
                                Svetovid.out.println("Minimum liste je:" + lista.minimum());
                                break;
                        case 'P':
                                pretraga();
                                break;
                        default:
                                break;
                        }
                        if (menu != 'Q') {
                                Svetovid.out.println(" -- enter za povratak u meni --");
                                Svetovid.in.readLine();
                        }
                }
        }

        static void unosBrojeva() {
                System.out.println("unesite n (broj brojeva): ");
                int n = Svetovid.in.readInt();
                System.out.println("unesite brojeve");
                for (int i = 0; i < n; i++) {
                        int br = Svetovid.in.readInt();
                        lista.dodajNaPocetak(br);
                }
        }

        static void pretraga() {
                int broj = Svetovid.in.readInt("Unesite broj koji trazite:");
                if (lista.uListi(broj)) {
                        Svetovid.out.println("Broj postoji u listi");
                } else {
                        Svetovid.out.println("Broj ne postoji u listi");
                }
        }

        static void stampajK(ListaBrojevaBr lista2) {
                int broj = Svetovid.in
                                .readInt("Unesite redni broj elementa koji zelite:");
                try {
                        Svetovid.out.println("Element na mestu " + broj + " je "
                                        + lista.element(broj));
                } catch (Exception e) {
                        Svetovid.out.println("Greska: " + e.getMessage());
                }

        }

        static void izbacivanjeK() {
                int broj = Svetovid.in.readInt("Unesite poziciju koju treba izbaciti:");
                if (lista.izbaciK(broj)) {
                        Svetovid.out.println("Pozicija je izbacena iz liste");
                } else {
                        Svetovid.out.println("Pozicija ne postoji u listi");
                }
        }

        static void izbacivanjeElSvi() {
                int broj = Svetovid.in.readInt("Unesite broj koji treba izbaciti:");

                Svetovid.out.println("Izbaceno je " + lista.izbaciIzListeSve(broj)
                                + "brojeva");

        }

        static void izbacivanjeEl() {
                int broj = Svetovid.in.readInt("Unesite broj koji treba izbaciti:");
                if (lista.izbaciIzListe(broj)) {
                        Svetovid.out.println("Broj je izbacen iz liste");
                } else {
                        Svetovid.out.println("Broj ne postoji u listi");
                }
        }

}

/**
 * Povezana lista brojeva sa operacijama nad njom i brojace elemenata. Lista u
 * svakom momentu moze da efikasno vrati broj elemenata u njoj.
 */
class ListaBrojevaBr {
        class Element {
                int info;
                Element veza;

                public Element(int br) {
                        this.info = br;
                        this.veza = null;
                }

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

        // pokazivac na prvi element liste
        Element prvi;

        // interni brojac koji pomaze kod nekih operacija
        int brojElemenata;

        /** Kreira praznu listu brojeva. */
        public ListaBrojevaBr() {
                this.prvi = null;
                this.brojElemenata = 0;
        }

        /** vraca broj elemenata u listi */
        public int velicina() {
                return brojElemenata;
        }

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

        public void dodajNaPocetak(int br) {
                Element novi = new Element(br);
                novi.veza = prvi;
                prvi = novi;
                brojElemenata++;
        }

        public void stampajNaEkran() {
                if (prvi == null) {
                        Svetovid.out.println("Lista je prazna");
                } else {
                        Svetovid.out.println("Sadrzaj liste duzine:"+velicina());
                        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;
        }

        /**
         * Vraca vrednost k-tog elementa. Prvi element liste je na mestu 0, drugi na
         * mestu 1 i tako dalje. Ne postoje elementi na negativnim pozicijama. U
         * slucaju nepostojeceg indeksa baca IndexOutOfBounds izuzetak.
         * 
         * @throws IndexOutOfBoundsException
         */
        public int element(int k) {
                if (k < 0) {
                        throw new IndexOutOfBoundsException(
                                        "Ne postoje elementi na negativnim pozicijama!");
                }

                if (k < brojElemenata) {
                        Element tekuci = prvi;
                        int br = 0;
                        while (br < k) {
                                tekuci = tekuci.veza;
                                br++;
                        }
                        return tekuci.info;
                } else {
                        throw new IndexOutOfBoundsException("Lista je kraca od "
                                        + k);
                }
        }

        // alternativna verzija procedure koja bi radila ako nemamo brojElemenata
        // kao polje
        public int elementB(int k) {
                if (k < 0) {
                        throw new IndexOutOfBoundsException(
                                        "Ne postoje elementi na negativnim pozicijama!");
                }

                Element tekuci = prvi;
                int brojac = 0;

                while (tekuci != null && k > brojac) {
                        tekuci = tekuci.veza;
                        brojac++;
                }

                if (tekuci != null) {
                        return tekuci.info;
                } else {
                        throw new IndexOutOfBoundsException("Lista je kraca od "
                                        + k);
                }
        }

        /** Vraca minimum liste. U slucaju prazne liste vratice maksimalni Integer. */
        public int minimum() {
                int min = Integer.MAX_VALUE;

                Element tekuci = prvi;
                while (tekuci != null) {
                        if (tekuci.info < min) {
                                min = tekuci.info;
                        }
                        tekuci = tekuci.veza;
                }

                return min;
        }

        /** Vraca da li broj br postoji u listi. */
        public boolean uListi(int br) {
                Element tekuci = prvi;
                while (tekuci != null && tekuci.info != br) {
                        tekuci = tekuci.veza;
                }

                // ako smo dosli do kraja liste i nismo ga nasli
                // tekuci ce biti jednako null
                return tekuci != null;
        }

        /**
         * Dodaje broj 'br' na poziciju 'pos'. Ako je pozicija negativna, broj ce
         * biti dodat na prvo mesto. Ako je pozicija veza od broja elemenata, broj
         * ce biti dodat na poslednje mesto.
         * 
         * @param br
         *            broj koji se dodaje u listu
         * @param pos
         *            pozicija na koju se broj dodaje
         */
        public void dodaj(int br, int pos) {
                Element novi = new Element(br);

                // proverimo i popravimo pos po potrebi
                if (pos < 0)
                        pos = 0;
                if (pos > brojElemenata) {
                        pos = brojElemenata;
                }

                // dodavanje na pocetak je jednostavno
                if (pos == 0) {
                        novi.veza = prvi;
                        prvi = novi;
                        brojElemenata++;
                } else {
                        // inace nam treba prethodni element
                        Element prethodni = prvi;
                        int brojac = 0;
                        while (prethodni != null && brojac < pos - 1) {
                                prethodni = prethodni.veza;
                                brojac++;
                        }
                        novi.veza = prethodni.veza;
                        prethodni.veza = novi;
                        brojElemenata++;
                }
        }

        /**
         * Izbacuje broj 'br' iz liste, naravno ako postoji i vraca da li je
         * operacija uspesno obavljena.
         */
        public boolean izbaciIzListe(int br) {
                // proverimo da li je prvi element
                if (prvi != null && prvi.info == br) {
                        prvi = prvi.veza;
                        return true;
                } else {
                        /* trazimo u ostatku liste */
                        Element tekuci, prethodni;
                        tekuci = prvi;
                        prethodni = null;
                        while (tekuci != null && tekuci.info != br) {
                                /*
                                 * 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 broj,
                                 * prevezemo listu oko elementa
                                 */
                                prethodni.veza = tekuci.veza;
                                brojElemenata--;
                                return true;
                        } else {
                                return false;
                        }
                }
        }

        /**
         * Izbacuje sve brojeve 'br' iz liste, naravno ako postoje i vraca koliko ih
         * je bilo.
         */
        public int izbaciIzListeSve(int br) {
                int brojac = 0;

                /* uklanjamo sa pocetka koliko je potrebno */
                while (prvi != null && prvi.info == br) {
                        prvi = prvi.veza;
                        brojac++;
                }

                Element tekuci, prethodni;
                /* trazimo u ostatku liste */
                if (prvi != null) {
                        tekuci = prvi;
                        while (tekuci.veza != null) {
                                /* idemo korak po korak do poslednjeg elementa liste */
                                prethodni = tekuci;
                                tekuci = tekuci.veza;
                                if (tekuci.info == br) {
                                        /* prevezemo listu oko elementa */
                                        prethodni.veza = tekuci.veza;
                                        brojac++;
                                        /*
                                         * vracamo se jedan korak da bi u novom krugu proverili i
                                         * ovaj element
                                         */
                                        tekuci = prethodni;
                                }
                        }
                }
                brojElemenata -= brojac;
                return brojac;
        }

        /**
         * Izbacuje K-ti element iz liste. Vraca da li je uspesno izbacen. Ako je
         * lista prekratka vratice false.
         */
        public boolean izbaciK(int k) {
                if (k >= brojElemenata) {
                        return false;
                }
                if (k < 0) {
                        return false;
                }
                // da li izbacujemo prvog?
                if (k == 0) {
                        prvi = prvi.veza;
                } else {
                        // brojimo do elementa pre onog koji izbacujemo
                        Element prethodni = prvi;
                        int brojac = 0;

                        while (k - 1 > brojac) {
                                prethodni = prethodni.veza;
                                brojac++;
                        }
                        // prevezemo oko k
                        prethodni.veza = prethodni.veza.veza;
                }
                brojElemenata--;
                return true;
        }

}