Programovanie (2) v Jave
1-INF-166, LS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · Testovač · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· DÚ10 je zverejnená, odovzdávajte do stredy 16.5. 22:00.
· Bonusový projekt odovzdávajte do pondelka 21.5. 22:00 na testovači. Predvádzanie projektov bude po prvom termíne skúšky v stredu 23.5. (t.j. začneme medzi 11:45 a 12:00 v H6). Ak vtedy nemôžete prísť, kontaktujte vyučujúce, dohodneme iný termín.
· Opravný/náhradný test bude v pondelok 28.5. o 10:00 v F1-108. V prípade záujmu sa prihláste v AISe.
· Na termíny skúšok sa zapisujte v AIS. Termíny: streda 23.5. (riadny), štvrtok 7.6. (riadny alebo 1. opravný), streda 20.6. (1. alebo 2. opravný) plus v prípade potreby ešte jeden termín v poslednom týždni skúškového. Prípadné konflikty nám dajte vedieť čím skôr. Ďalšie informácie na stránke Test a skúška.


Prednáška 29

Z Programovanie
Prejsť na: navigácia, hľadanie

Organizačné poznámky

  • DÚ7 do budúcej stredy, neodkladajte na poslednú chvíľu
  • Ďalšia rozcvička bude v stredu po Veľkej noci

Opakovanie: generické programovanie

  • V Jave môžeme definovať triedu alebo metódu, ktorá má špeciálny parameter určujúci typ dát, ktoré bude spracovávať, napr. zásobník s prvkami typu T.
   class Stack <T> {
        private Node<T> front;
        public void push(T data) {
            Node<T> p = new Node<T>(data, front);
            front = p;
        }

        public T pop() {
            T res = front.getData();
            front = front.getNext();
            return res;
        }
    }

Použitie zásobníka:

        Stack<Integer> s = new Stack<Integer>();
        s.push(new Integer(4));
        s.push(5);        
        Integer y = s.pop();
        int z = s.pop();

Výhody generickej verzie zásobníka:

  • V tom istom programe môžeme vytvoriť zásobníky veľa rôznych typov.
  • Kompilátor skontroluje, či vkladáme a vyberáme prvky správnych typov.

Opakovanie: Úvod do Java Collections

  • Dátové štruktúry a algoritmy na základnú prácu so skupinami dát.
  • Generické typy - môžeme vytvárať dátové štruktúry pre dáta rôznych typov.
  • Definované pomocou rozhraní, jedno rozhranie (interface) môže mať viacero implementácií.

Vybrané triedy:

Rozhranie Význam Implementácie
Collection skupina objektov
- Set množina, skupina bez opakujúcich sa objektov HashSet
-- SortedSet množina s definovaným usporiadaním prvkov TreeSet
- List postupnosť objektov s určitým poradím ArrayList, LinkedList
Map slovník, asociatívne pole, mapuje kľúče na hodnoty HashMap
- SortedMap slovník s definovaným usporiadaním kľúčov TreeMap


Základné operácie pre Collection:

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object element);

    boolean add(E element);  // optional
    boolean remove(Object element); // optional
    void clear(); // optional

    Iterator<E> iterator();

    Object[] toArray();
    <T> T[] toArray(T[] a);

   // a dalsie...
}

Prechádzanie cez prvky Collection

Použitie cyklu for-each:

    public static Integer sum(Collection<Integer> a) {
        int sum = 0;
        for(Integer x : a) {
            sum += x;
        }
        return sum;
    }
  • cyklus for-each sa dá použiť na ľubovoľný objekt triedy implementujúcej rozhranie Iterable, ktoré definuje metódu Iterator<T> iterator() (plus ďalšie nepovinné)

Použitie iterátora:

    public static Integer sum(Collection<Integer> a) {
        int sum = 0;
        for (Iterator<Integer> it = a.iterator(); it.hasNext();) {
            sum += it.next();
        }
        return sum;
    }
  • a.iterator() vráti objekt it implementujúci rozhranie Iterator
  • it.next() vráti ďalší prvok zo skupiny a, alebo hodí NoSuchElementException, ak už ďalší nie je
  • it.hasNext() vráti, či ešte je ďalší prvok
  • Užitočná predstava je, že iterátor vždy ukazuje na "medzeru" medzi dvoma prvkami (prípadne pred prvým alebo za posledným prvkom)
    • next() preskočí do ďalšej medzery a vráti preskočený prvok
  • Poradie, v akom prvky navštívime, nie je pre všeobecnú Collection definované
    • Iterátor pre SortedSet vracia prvky v utriedenom poradí od najmenšieho po najväčší.
    • Iterátor pre List vracia prvky v poradí, v akom sú v postupnosti (poli, zozname)

Pozn: Rozhranie List definuje ListIterator, ktorý rozširuje základný iterátor (pohyb oboma smermi, pridávanie prvkov atď, užitočné pre prácu s LinkListom).

Cvičenie Nasledujúci program má vypísať všetky kombinácie hodnôt zo zoznamov a a b (t.j. A1,A2,B1,B2,C1,C2), ale nefunguje správne a padá na java.util.NoSuchElementException. Prečo? Ako chybu opraviť?

import java.util.*;
public class Pokus {
    public static void main(String[] args) {
	LinkedList<String> a = new LinkedList<String>();
	a.add("A"); a.add("B"); a.add("C");

	LinkedList<Integer> b = new LinkedList<Integer>();
	b.add(1); b.add(2);

    	for (Iterator<String> i = a.iterator(); i.hasNext(); ) {
	    for (Iterator<Integer> j = b.iterator(); j.hasNext(); ) {
		System.out.println(i.next() + j.next());
	    }
	}
    }
}

Použitie Map

public interface Map<K,V> {

    V put(K key, V value);  // klucu key prirad hodnotu value, vrati predch. hodnotu pre key
    V get(Object key);      // hodnota pre kluc key alebo null
    V remove(Object key);   // zmaz kluc key a jeho hodnotu
    boolean containsKey(Object key);  // obsahuje kluc key?
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Vrátia Set alebo Collection, cez ktorý môžeme iterovať
    public Set<K> keySet();  
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();

    // Interface pre dvojice vo výsledku entrySet
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}

Príklad použitia Map:

  • vstup z konzoly rozložíme Scannerom na slová (kým užívateľ nezadá END) a počítame počet výskytov každého slova
import java.util.*;
public class Prog {
   public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        Scanner s = new Scanner(System.in);  // inicializujeme Scanner
        while (s.hasNext()) {        // kym neskonci vstup
            String word = s.next();  // nacitame slovo
            if (word.equals("END")) { // skoncili sme ak najdeme END
                break;
            }
            Integer freq = map.get(word);
            if(freq == null) {
                map.put(word, 1);
            } else {
                map.put(word, freq+1);
            }            
        }
        System.out.println("Pocet roznych slov: " + map.size());
        System.out.println(map);
  }
}

Príklad výstupu:

one two three one two two END
Pocet roznych slov:3
{two=3, one=2, three=1}

HashMap vypisuje prvky v ľubovoľnom poradí. Ak typ zmeníme na TreeMap, dostaneme utriedené podľa kľúča:

{one=2, three=1, two=3}

Ak chceme vypísať zoznam slov a ich frekvencií v inom formáte, použijeme for-each alebo iterátor (ďalšie možnosti na konci prednášky)

for(Map.Entry<String, Integer> e : map.entrySet()) {
      System.out.println("Slovo " + e.getKey()
                         + " sa vyskytuje " + e.getValue() 
                         + " krat");
}
for(Iterator<Map.Entry<String,Integer>> it=map.entrySet().iterator(); 
    it.hasNext(); ) {
       Map.Entry<String,Integer> e = it.next();
       System.out.println("Slovo " + e.getKey()
               + " sa vyskytuje " + e.getValue() 
               + " krat");
}
Slovo two sa vyskytuje 3 krat
Slovo one sa vyskytuje 2 krat
Slovo three sa vyskytuje 1 krat

Dôležité metódy z uložených objektov

Porovnávanie objektov na rovnosť: equals

  • Metódy z Collection contains(Object element), remove(Object element) a ďalšie potrebujú porovnávať objekty na rovnosť.
  • Operátor == porovnáva referencie, t.j. či sú dva objekty na tej istej adrese v pamäti
  • Collection používa namiesto toho metódu equals(Object obj) definovanú v triede Object
  • Metóda equals() v triede Object tiež porovnáva len referencie, ostatné triedy ju môžu prekryť
  • Napr. v triedach ako String, Integer,... definovaná na porovnávanie reťazcov, čísel,...
  • Rôzne triedy implementujúce Collection tiež väčšinou vedia porovnávať na rovnosť spúšťaním equals na jednotlivé prvky
  • Metódy nevieme spúšťať na null, napr. contains(Object o) vracia true práve vtedy, keď nejaký prvok e Collection spĺňa (o==null ? e==null : o.equals(e))
  • Prekrytá metóda equals by sa mala správať "rozumne", t.j. byť symetrická, tranzitívna a pod.

Porovnávanie objektov na nerovnosť: Comparable

  • SortedMap a SortedSet potrebujú vedieť porovnávať prvky podľa veľkosti
  • Používajú metódu compareTo definovanú v rozhraní Comparable (videli sme na minulej prednáške)
  • Ak naša trieda neimplementuje toto rozhranie alebo chceme použiť iné usporiadanie, môžeme použiť vlastný komparátor, objekt implementujúci rozhranie Comparator
import java.util.*;
public class SetSortedByAbsoluteValue {
    /** Trieda AbsoluteValueComparator porovnava Integery 
     * podla absolutnej hodnoty */
    static class AbsoluteValueComparator implements Comparator<Integer> {
	public int compare(Integer o1, Integer o2) {
	    Integer x1 = Math.abs(o1);
	    Integer x2 = Math.abs(o2);
	    return x1.compareTo(x2);
	}
    }
    public static void main(String[] args) {
	AbsoluteValueComparator comp = new AbsoluteValueComparator();
	TreeSet<Integer> set = new TreeSet<>(comp);
	set.add(-3); set.add(0); set.add(7); set.add(-10);
	for(Integer x : set) {  // vypise 0 -3 7 -10
	    System.out.print(" " + x);
	}
	System.out.println();
    }
}

Hešovacie funkcie: hashCode

  • HashSet a HashMap potrebujú vedieť prekódovať ľubovoľný objekt do pozície v poli
  • Používajú metódu int hashCode() definovanú v triede Object
  • Object jednoducho použije svoju adresu v pamäti ako svoj hashCode
  • Štandardné triedy prekrývajú hashCode
  • Ak prekryjete equals, treba prekryť aj hashCode, lebo ak sa dva prvky rovnajú v equals, majú mať rovnaký hashCode
    static class Name {
        String givenName;
        String lastName;
        @Override
        public int hashCode () {
            return givenName.hashCode() + 31*lastName.hashCode();
        }
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            Name other = (Name) obj;
            return this.givenName.equals(other.givenName) 
                   && this.lastName.equals(other.lastName);
        }
   }

Algoritmy

  • Triedy Collections a Arrays obsahujú statické metódy na prácu s Collections a poliami
  • Napr. sort, shuffle (náhodne preusporadaj), reverse, fill, copy, swap, binarySearch, min, max,...

Collections: Zhrnutie

  • Collections sú obrovská knižnica a veľmi užitočná
  • Neváhajte ich používať v programoch, nájdite si v dokumentácii metódy, ktoré sa vám hodia
  • Mali by ste ovládať (s pomocou ťaháka) aspoň základy práce s ArrayList, LinkedList, HashMap a s iterátormi
  • Pri spracovaní väčších dát pozor na to, že niektoré metódy sú pomalé
  • Pre prácu s Collections môže byť potrebné prekryť niektoré metódy z Object (equals, hashCode)
    • Ďalšie metódy z Object, ktoré sa často hodí prekryť sú clone a toString

Vnorené a anonymné triedy

  • Java umožňuje definovať triedu v inej triede alebo dokonca v metóde
    • To umožnuje ju uložiť tam, kde logicky patrí, kde sa používa a prípadne zamedziť prístup iným častiam programu
  • Tu len základný prehľad, viac detailov na Programovaní (3) alebo samoštúdium
  • Trieda definovaná v inej triede môže byť statická alebo nestatická

Statická vnorená trieda (static nested class)

  • Správa sa podobne ako keby bola definovaná mimo triedy
public class A {
   // premenné, metódy
   public static class B {
      // premenné, metódy
   }
   
   // použitie v triede A:
   B objekt = new B();
}

// použitie v inej triede:
A.B objekt = new A.B();

Vnútorná trieda, t.j. nestatická vnorená trieda (inner class)

  • Inštancie vnútornej triedy majú prístup k premenným vonkajšej triedy

Lokálna trieda (local class)

  • Podobne ako vnútorná trieda, ale definovaná vo vnútri metódy, priamo prístupná (pod svojim menom) len tam
  • Ale inštancie sa dajú použiť aj mimo metódy
    • V príklade nižšie metóda iterator obsahuje definíciu triedy MyIterator, ktorá implementuje rozhranie Iterator<Integer>
    • Metóda iterator vráti objekt triedy MyIterator metóde main a tá ho implicitne použije vo for cykle, aj keď metóda iterator už skončila
import java.util.Iterator;

public class MyArray implements Iterable<Integer> {
    private Integer [] array;

    /** Konstruktor vytvori pole dlzky n a naplni ho cislami 10,20,... */
    public MyArray(int n) {
        array = new Integer[n];
        for (int i = 0; i < n; i++) {
            array[i] = (i + 1) * 10;
        }
    }

    /** Metoda vrati iterator cez pole */
    public Iterator<Integer> iterator() {
        class MyIterator implements Iterator<Integer>  {
            private int index;  // poloha v poli
            private MyIterator() {  // konstruktor iniocializuje index
                index = 0;
            }
            public Integer next() {
                index++;
                return array[index - 1]; // mozeme pouzit premennu array z MyArray
            }
            public boolean hasNext() {
                return index < array.length;
            }
        }

        return new MyIterator();
    }

    public static void main(String[] args) {
        MyArray a = new MyArray(5);
        for (Integer x : a) {
            System.out.println(x);
        }
        // alebo ekvivalentne:
        for (Iterator<Integer>it = a.iterator(); it.hasNext();) {
            System.out.println(it.next());
        }
    }
}

Anonymná trieda (anonymous class)

  • Definuje sa v nejakej metóde, pričom sa jej ani nepriradí meno, iba sa vytvorí inštancia
  • Tu je metóda iterator z predchádzajúceho príkladu prepísaná s anonymnou triedou:
    /** Metoda vrati iterator cez pole */
    public Iterator<Integer> iterator() {
	return new Iterator<Integer>() { // zaciatok anonymnej triedy
	    private int index = 0;  // poloha v poli, priamo inicializovana
	    public Integer next() { 
		index++;
		return array[index-1]; 
	    }
	    public boolean hasNext() {
		return index < array.length;
	    }
	};  // bodkociarka za prikazom return
    }
  • Za príkaz new sme dali meno rozhrania (Iterator<Integer>), za tým prázdne zátvorky pre "konštruktor", potom definíciu triedy a bodkočiarku
  • Nie je možné písať konštruktory, ale môžeme inicializovať premenné, napr. private int index = 0;

Premenné a parametre z metódy v lokálnych a anonymných triedach

  • Lokálna alebo anonymná trieda môže používať aj lokálne premenné a parametre metódy, v ktorej sa nachádza
    • Ale pozor, iba ak sú definované ako final alebo sa do nich po inicializácii nič nepriradzuje
    • Ak však ide o referenciu na objekt alebo pole, obsah poľa resp. premenných objektu je možné meniť, nemení sa iba referencia
  • V nasledujúcej ukážke pridáme ďalší iterátor, ktorý sa neposúva o 1, ale o zadanú hodnotu jump
public class MyArray implements Iterable<Integer> {
    // sem prídu premenné a metódy z príkladu vyššie (konštruktor, iterator)

    public Iterator<Integer> jumpingIterator(Integer jump) {
        // jump = 3;  // s týmto príkazom by to neskompilovalo
	return new Iterator<Integer>() { // zaciatok anonymnej triedy
	    private int index = 0;  // poloha v poli, priamo inicializovana
	    public Integer next() { 
		index += jump;
		return array[index-jump]; 
	    }
	    public boolean hasNext() {
		return index < array.length;
	    }
	};  // bodkociarka za prikazom return
    }
    
    public static void main(String[] args) {
	MyArray a = new MyArray(5);
	Iterator<Integer> it = a.jumpingIterator(2);
	while(it.hasNext()) {
	    System.out.println(it.next());
	}
    }

Metóda forEach v Iterable, lambda výrazy

Rozhranie Iterable definuje aj metódu forEach, ktorá ako argument dostane objekt implementujúci generické rozhranie Consumer. Toto rozhranie má jedinú metódu accept vracajúcu void.

Pripomeňme si vypísanie našeho slovníka s frekvenciami výskytu slov pomocou for-each cyklu

for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println("Slovo " + e.getKey()
                       + " sa vyskytuje "
                       + e.getValue() + " krat");
}

Pomocou metódy forEach a anonymnej triedy ho prepíšeme takto:

Consumer<Map.Entry<String, Integer>> printAll
= new Consumer<Map.Entry<String, Integer>>() {
    public void accept(Map.Entry<String, Integer> e) {
         System.out.println("Slovo " + e.getKey()
                            + " sa vyskytuje "
                            + e.getValue() + " krat");
     }
};
map.entrySet().forEach(printAll);
  • Tento kód však nie je príliš prehľadný.
  • Namiesto anonymnej triedy s iba jednou metódou môžeme použiť lambda výraz (lambda expression)
  • Telo metódy bez zvyšku triedy napíšeme priamo kde treba, t.j. ho môžeme priradiť do premennej printAll alebo priamo ako argument metódy forEach.
map.entrySet()
.forEach(e -> System.out.println("Slovo " + e.getKey()
                                 + " sa vyskytuje "
                                 + e.getValue() + " krat"));

Map má tiež forEach, čo je ešte jednoduchšie:

map.forEach((key, value)
            -> System.out.println("Slovo " + key
                                  + " sa vyskytuje "
                                  + value + " krat"));

Vo všeobecnosti má lambda výraz tvar

(param1,param2) -> { 
  doSomething(param1, param2); 
  return somethingElse(param1, param2); 
}
(param1,param2) -> someExpression(param1, param2);   // vynecháme return
param -> someExpression(param)

V Jave je tiež možnosť vykonať viacero operácií špecifikovaných lambda výrazmi na postupnostiach nazývaných Stream.

Cvičenia

  • V našom príklade s počítaním frekvencií slov máme v štruktúre Map ako kľúče slová a hodnoty ich počty výskytov. Čo vypíšu nasledujúce dva kúsky kódu?
map.forEach((key, value) -> {
    if (key.length() > 2) {
        System.out.println("Slovo " + key
        + " sa vyskytuje "
        + value + " krat");
    }
});


ArrayList<String> words = new ArrayList<>();
map.forEach((key, value) -> {
    if (value > 1) {
       words.add(key);
    }
});
System.out.println(words);
  • V tejto prednáške sme videli príklad, ktorý udržiaval množinu utriedenú podľa absolútnej hodnoty čísla tak, že implementoval pomocnú statickú vnorenú triedu AbsoluteValueComparator. Prepíšte tento príklad tak, aby ste namiesto tejto triedy použili anonymnú triedu alebo lambda výraz.

Riešenie pre Comparator

Riadok s vytváraním premennej set zmeníme na:

TreeSet<Integer> set = new TreeSet<>((o1,o2)-> {
            Integer x1 = Math.abs(o1);
            Integer x2 = Math.abs(o2);
            return x1.compareTo(x2);
});

alebo ešte kratšie

TreeSet<Integer> set = new TreeSet<>((o1,o2)->
        ((Integer)Math.abs(o1)).compareTo(Math.abs(o2))
);

(potrebujeme pretypovať, lebo Math.abs vracia int, nie Integer.


Trieda AbsoluteValueComparator a riadok s vytváraním premennej comp sa vynechá. Ak aj na výpis použijeme lambda výraz a na pridanie prvkov do množiny metódu asList z triedy Arrays, celý program sa skráti takto:

import java.util.*;
public class MySet {
    public static void main(String[] args) {
        // vytvoríme SortedSet utriedený podľa absolútnej hodnoty
        SortedSet<Integer> set
            = new TreeSet<>((o1, o2)->
                            ((Integer)Math.abs(o1)).compareTo(Math.abs(o2))
                           );

        // pridáme doňho nejaké prvky
        set.addAll(Arrays.asList(-3, 0, 7, -10));
        // vypíšeme usporiadané podľa absolútnej hodnoty
        set.forEach(x -> System.out.print(" " + x));
        System.out.println();
    }
}

Ešte poznámky pre zvedavých: ak by sme chceli vynechať medzeru pred prvým číslom, môžeme skúsiť použiť premennú first, ktorá určuje, či ide o prvé číslo:

        boolean first = true;
        set.forEach(x -> {
                if(!first) System.out.print(" ");
                System.out.print(x);
                first = false;
            });

To však neskompiluje, lebo premennú first nemôžeme meniť (chyba local variables referenced from a lambda expression must be final or effectively final). Ako jednoduchý trik môžeme použiť pole booleanov dĺžky 1:

       boolean[] first = {true};
       set.forEach(x -> {
           if (!first[0]) System.out.print(" ");
           System.out.print(x);
           first[0] = false;
       });

Kompilátor je spokojný, lebo first je referencia na pole a tá sa nemení, mení sa len obsah poľa.