3. sada domácich zadaní

Najneskorší termín odovzdania: 11.3.2018 (nedeľa) o 21:00
Odovzdávaný súbor: SpajanyZoznam.java

Doplňujúce požiadavky:

  • riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
  • zdrojový kód správne naformátujte (CTRL+SHIFT+F),
  • komentovaný zdrojový kód

Obe metódy musia pracovať v čase O(n) a pamäťou O(1), kde n je počet hodnôt (uzlov) v spájanom zozname. Ak metódy budú potrebovať viac ako jeden prechod spájaným zoznamom, bodový zisk bude znížený o 30%.

Metódy pridajNaZaciatok a toString nemodifikujte, keďže sú využívané evaluátorom.

Zduplikuj (3 body)

Do triedy SpajanyZoznam pridajte metódu zduplikuj(double dh, double hh), ktorá za každý výskyt čísla v intervale <dh, hh> hodnota vloží jeho duplikát. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.

Príklad:

  • zo zoznamu s hodnotami [5, 7, 1, 9, 3, 30, 6, 4] po volaní zduplikuj(6, 20) vznikne zoznam s hodnotami [5, 7, 7, 1, 9, 9, 3, 30, 6, 6, 4].
public void zduplikuj(double dh, double hh)
[$[Get Code]]

Intervalový filter (3 body)

Do triedy SpajanyZoznam pridajte metódu filtruj(double dh, double hh), ktorá zo spájaného zoznamu odstráni všetky uzly, ktorých hodnota neleží v intervale <dh, hh>. Vzájomné poradie ostatných uzlov (hodnôt) v zozname musí ostať zachované.

Príklad:

  • zo zoznamu s hodnotami [5, 7, 1, 9, 3, 30, 6, 4] po volaní filtruj(6, 20) vznikne zoznam s hodnotami [7, 9, 6],
public void filtruj(double dh, double hh)
[$[Get Code]]
/**
 * Trieda zapuzdrujuca spajany zoznam a manipulaciu s nim
 */
public class SpajanyZoznam {

        /**
         * Sukromna trieda reprezentujuca jeden uzol spajaneho zoznamu
         */
        private static class Uzol {
                double hodnota;
                Uzol dalsi;
        }

        /**
         * Referencia na prvy uzol spajaneho zoznamu
         */
        private Uzol prvy = null;

        /**
         * Prida novu hodnotu na zaciatok spajaneho zoznamu
         *
         * @param hodnota
         *            pridavana hodnota
         */
        public void pridajNaZaciatok(double hodnota) {
                Uzol pridavany = new Uzol();
                pridavany.hodnota = hodnota;
                pridavany.dalsi = prvy;
                prvy = pridavany;
        }

        @Override
        public String toString() {
                String vysledok = "[";
                Uzol aktualny = prvy;
                while (aktualny != null) {
                        if (aktualny != prvy)
                                vysledok += ", ";

                        vysledok += aktualny.hodnota;
                        aktualny = aktualny.dalsi;
                }

                return vysledok + "]";
        }

        public void zduplikuj(double dh, double hh) {
                // TODO
        }

        public void filtruj(double dh, double hh) {
                // TODO        
        }

        public static void vlozNahodneHodnoty(SpajanyZoznam zoznam, int pocet) {
                for (int i = 0; i < pocet; i++) {
                        zoznam.pridajNaZaciatok((int) (500 - Math.random() * 1000) / 10.0);
                }
        }

        public static void main(String[] args) {
                // Demo
                System.out.println("zduplikuj:");
                SpajanyZoznam zoznam = new SpajanyZoznam();
                vlozNahodneHodnoty(zoznam, 20);
                System.out.println("Pred: " + zoznam);
                zoznam.zduplikuj(10, 20);
                System.out.println("Po  : " + zoznam);

                System.out.println();

                System.out.println("filtruj:");
                zoznam = new SpajanyZoznam();
                vlozNahodneHodnoty(zoznam, 20);
                System.out.println("Pred: " + zoznam);
                zoznam.filtruj(10, 20);
                System.out.println("Po  : " + zoznam);
        }
}
[$[Get Code]]