Letný semester, prednáška č. 5

Oznamy

• Dnes po prednáške bude zverejnené zadanie druhej domácej úlohy, ktorú bude potrebné odovzdať do pondelka 29. marca, 9:00 (čiže do začiatku siedmej prednášky).
• Na stredajších cvičeniach bude – okrem niekoľkých nebodovaných úloh zameraných na látku z tejto a minulej prednášky – zverejnené aj zadanie druhej bonusovej úlohy s odovzdávaním do stredy 24. marca, 11:30 (čiže najneskôr do začiatku šiestych cvičení).

Java Collections

Detailnejšie teraz preskúmame štandardné dátové štruktúry implementované v balíku java.util a známe pod súhrnným názvom Java Collections. Na nasledujúcom obrázku je znázornený diagram niekoľkých spomedzi najdôležitejších tried a rozhraní, ktoré sú súčasťou Java Collections. Plná šípka v tomto diagrame reprezentuje dedenie (aj medzi rozhraniami) a prerušovaná šípka znázorňuje implementáciu rozhrania triedou.

Rozhranie Collection

Veľká časť tried pre dátové štruktúry, ktoré sú súčasťou Java Collections – presnejšie triedy reprezentujúce zoskupenia objektov nejakého typu E – implementuje generické rozhranie Collection<E>. Metódy tohto rozhrania sú tak napríklad poskytované implementáciami zoznamov, či množín. Medzi najdôležitejšie spomedzi metód deklarovaných v rozhraní Collection<E> patria nasledujúce:

• Metóda boolean contains​(Object o) vráti true práve vtedy, keď dané zoskupenie objektov obsahuje objekt o.
• Metóda boolean add​(E e) pridá inštanciu e typu E do zoskupenia objektov a vráti booleovskú hodnotu podľa toho, či po vykonaní tejto operácie bolo dané zoskupenie zmenené (napríklad u zoznamov by to tak malo byť vždy; naopak množina sa nezmení v prípade, že je do nej pridaný prvok, ktorý už obsahuje). Pri jednotlivých implementáciách rozhrania Collection<E> môže byť správanie tejto metódy bližšie určené: napríklad u zoznamov sa typicky pridávajú prvky na koniec. Táto metóda je označená ako nepovinná, čo znamená, že niektoré implementácie rozhrania Collection<E> ju môžu implementovať iba ako vyhodenie výnimky typu UnsupportedOperationException.
• Metóda boolean remove​(Object o) odoberie zo zoskupenia jeden výskyt argumentu o. Opäť ide o nepovinnú metódu, ktorej správanie môže byť v jednotlivých implementáciách rozhrania bližšie špecifikované. (Napríklad pri zoznamoch väčšinou býva užitočnejšia iná verzia metódy remove, ktorá odoberie prvok na danom indexe; táto sa ale v rozhraní pre všeobecné zoskupenia objektov nedeklaruje.)
• Metóda int size() vráti veľkosť daného zoskupenia objektov.
• Metóda boolean isEmpty() zistí, či je dané zoskupenie objektov prázdne.
• Metóda Iterator<E> iterator() vráti tzv. iterátor, ktorý možno použiť na postupné prechádzanie cez všetky prvky daného zoskupenia. Ide tu o dôležitý koncept, pri ktorom sa ešte bližšie pristavíme nižšie.

Použitie metódy equals

Je ešte potrebné ujasniť si, čo napríklad pri metóde contains znamená, že zoskupenie obsahuje objekt o, prípadne kedy sa pri metóde remove nejaký objekt považuje za výskyt jej argumentu. V obdivoch prípadoch sa na porovnávanie objektov používa metóda equals, ktorá porovná dva objekty na rovnosť. S touto metódou sme sa už stretli napríklad pri reťazcoch alebo pri „baliacich” triedach. Ide však o metódu, ktorá je podobne ako toString definovaná už v triede Object – jej východzou implementáciou je porovnávanie referencií pomocou operátora == – a v iných triedach môže byť prekrytá prirodzenejšou implementáciou. Viacero štandardných tried (napr. String a Integer) túto metódu vhodným spôsobom prekrýva.

• Programátor prekrytej metódy equals by mal vždy zabezpečiť, aby išlo o reláciu ekvivalencie (reflexívnu, symetrickú a súčasne tranzitívnu reláciu).
• Súčasne by sa výstupy metódy equals pre danú dvojicu objektov nemali meniť v čase. To v praxi znamená, že prekrývanie metódy equals má význam hlavne pri triedach, ktorých inštancie reprezentujú nemodifikovateľné dáta. Napríklad String metódu equals zdedenú od triedy Object vhodným spôsobom prekrýva, ale StringBuilder nie.
• Dátové štruktúry, ktoré sú súčasťou Java Collections, sa na tieto vlastnosti metódy equals spoliehajú – iba za ich splnenia je teda garantované, že sa budú správať očakávaným spôsobom.

Príklad: nasledujúca trieda reprezentuje bod v rovine, pričom dva body sa považujú za rovné kedykoľvek sa rovnajú obidve ich súradnice.

public class Point {
    private double x, y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        return o.getClass() == this.getClass() && ((Point) o).x == x && ((Point) o).y == y;
    }
}

public class Trieda {

    public static void main(String[] args) {
        Point p1 = new Point(1, 2);
        Point p2 = new Point(1, 2);
        System.out.println(p1 == p2);       // false
        System.out.println(p1.equals(p2));  // true
    }
}

Zoznamy

Triedy pre zoznamy sú implementáciami rozhrania List<E>.

• Prvok na koniec zoznamu pridáva metóda add, prvok na danej pozícii dostaneme metódou get, metóda set mení prvok na danej pozícii na určenú hodnotu a dĺžku zoznamu vracia metóda size.

Dvoma najdôležitejšími triedami implementujúcimi rozhranie List<E> sú:

• Trieda ArrayList<E> reprezentujúca zoznamy implementované pomocou dynamických polí, ktoré dokážu automaticky meniť objem alokovanej pamäte.

Príklad:

import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i <= 9; i++) {
            a.add(i);
        }
        for (int i = 0; i <= a.size() - 1; i++) {
            a.set(i, i + 1);
        }
        for (int i = 0; i <= a.size() - 1; i++) {
            System.out.print(a.get(i) + " ");
        }
    }
}

• Trieda LinkedList<E> reprezentujúca obojsmerne spájaný zoznam.

Každá z týchto dvoch implementácií zoznamov je zameraná na iné operácie, ktoré sú v nej efektívnejšie – z minulého semestra napríklad vieme, že prístup k prvku na konkrétnej pozícii zoznamu je omnoho efektívnejší u polí, zato pri spájaných zoznamoch sa rýchlejšie pridávajú a odoberajú nové prvky (napríklad) na začiatku alebo konci.

Rad a objostranný rad

• Trieda LinkedList<E> okrem rozhrania List<E> implementuje aj rozhranie Queue<E> reprezentujúce rady (fronty). Na koniec radu pridávame metódou add rovnako ako u zoznamov; metóda remove (bez parametrov) vyberie a vráti na výstupe prvok zo začiatku radu; metóda peek vráti prvok na začiatku radu bez toho, aby ho z radu vybrala.
• Okrem toho trieda LinkedList<E> implementuje aj rozhranie Deque<E> (z angl. double-ended queue) pre obojstranné rady, v ktorých možno prvky pridávať a vyberať z obidvoch strán. Toto rozhranie okrem iného deklaruje metódy push a pop umožňujúce pracovať s ním ako so zásobníkom.
• Javovské spájané zoznamy typu LinkedList<E> teda možno použiť aj ako rad, aj ako zásobník.

Množiny a použitie metódy hashCode

Triedy pre množiny sú implementáciami rozhrania Set<E> a pri práci s nimi sú podstatné predovšetkým metódy add, contains a remove. Najdôležitejšou implementáciou množín je trieda HashSet<E>:

• Ide o implementáciu množín pomocou hešovania.
• Pri hešovaní sa využíva metóda hashCode vracajúca pre daný objekt nejakú celočíselnú hodnotu, na základe ktorej sa pre tento objekt počíta index do hešovacej tabuľky. Táto metóda je podobne ako metóda equals definovaná už v triede Object a viaceré štandardné triedy ju prekrývajú. Napríklad String vráti ako výstup tejto metódy číslo, ktoré vznikne sčítaním hodnôt jednotlivých znakov prenásobených rôznymi mocninami čísla 31.
• Opäť by malo ísť o metódu, ktorá pre ľubovoľný objekt zakaždým vráti rovnakú hodnotu, takže jej prekrývanie má obyčajne zmysel hlavne pri triedach, ktorých inštancie reprezentujú nemodifikovateľné dáta.
• Ďalšou požiadavkou je, aby pre ľubovoľnú dvojicu objektov, pre ktoré vráti metóda equals hodnotu true, vrátila metóda hashCode rovnaké výstupy. To znamená, že metódu hashCode je žiadúce prekryť kedykoľvek je prekrytá metóda equals.
• Pre dvojice objektov, pre ktoré equals vráti hodnotu false, metóda hashCode nemusí vrátiť rôzne hodnoty – implementácia by sa ale mala snažiť o čo najmenšiu pravdepodobnosť takejto situácie, aby boli prvky v hešovacej tabuľke rozdelené čo najrovnomernejšie.

Príklad:

public class Name {
    private String givenName;
    private String lastName;

    public Name(String givenName, String lastName) {
        this.givenName = givenName;
        this.lastName = lastName;
    }

    public String getGivenName() {
        return givenName;
    }

    public String getLastName() {
        return lastName;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        return o.getClass() == this.getClass() && ((Name) o).givenName.equals(givenName)
                && ((Name) o).lastName.equals(lastName);
    }

    @Override
    public int hashCode() {
        return givenName.hashCode() + 31 * lastName.hashCode();
    }
}

import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Set<Name> set = new HashSet<>();
        while (scanner.hasNext()) {
            String command = scanner.next();
            String givenName = scanner.next();
            String lastName = scanner.next();
            switch (command) {
                case "ADD":
                    set.add(new Name(givenName, lastName));
                    break;
                case "CONTAINS":
                    System.out.println(set.contains(new Name(givenName, lastName)));
                    break;
                case "REMOVE":
                    set.remove(new Name(givenName, lastName));
                    break;
            }
        }
    }
}

Cvičenie: zakomentujte v kóde triedy Name prekrytú metódu hashCode a nájdite príklad vstupu, pre ktorý sa v metóde main na konzolu vypíšu neočakávané výsledky.

Iterátory

Všetky triedy implementujúce rozhranie Collection<E> implementujú aj rozhranie Iterable<E>. Rozhranie Iterable<T> pritom deklaruje jedinú povinnú metódu Iterator<T> iterator(), ktorej výstupom je iterátor – objekt umožňujúci postupne prechádzať cez nejakú sadu prvkov typu T. Pri triedach implementujúcich Collection<E> je výstupom metódy iterator() iterátor, pomocou ktorého možno postupne prechádzať cez všetky prvky daného zoskupenia objektov.

• Zoznamy iterátor prechádza od začiatku po koniec.
• Napríklad pri množinách typu HashSet ale nie je určené žiadne špeciálne poradie, v ktorom iterátor prechádza cez ich prvky.

Samotným iterátorom cez prvky typu E je pritom inštancia ľubovoľnej triedy implementujúcej rozhranie Iterator<E>. To deklaruje predovšetkým nasledujúce tri metódy:

• Metóda E next() vráti nasledujúci spomedzi prvkov, cez ktoré iterátor prechádza. Ak už žiaden ďalší prvok neexistuje, vyhodí výnimku typu NoSuchElementException.
• Metóda boolean hasNext() vráti true, ak ešte existuje nejaký ďalší prvok – čiže v prípade, že nasledujúce volanie metódy next nevyhodí výnimku.
• Nepovinná metóda default void remove() z prechádzaného zoskupenia odoberie prvok, ktorý bol dosiaľ posledným výstupom metódy next. Túto metódu nemusia implementovať všetky triedy implementujúce rozhranie Iterator<E> – v takom prípade sa pri pokuse o jej volanie použije východzia implementácia spočívajúca vo vyhodení výnimky typu UnsupportedOperationException.

Iterátor si teda možno predstaviť tak, že v každom momente svojej existencie ukazuje na medzeru medzi nejakými dvoma prechádzanými prvkami (resp. na pozíciu pred prvým alebo za posledným prvkom). Po zavolaní metódy next iterátor preskočí ďalší prvok a tento prvok vráti na výstupe.

Iterátory sú užitočné napríklad v situáciách, keď je potrebné prejsť všetky prvky nejakého zoskupenia, avšak samotné toto zoskupenie nepotrebujeme výraznejšie meniť (inak ako metódou remove iterátora). Počas iterovania samozrejme môžeme meniť dáta uložené v prechádzaných objektoch; obmedzenie sa týka iba modifikácie referencií na objekty v zoskupení uložených.

Príklad: Vypísanie všetkých prvkov spájaného zoznamu celých čísel list môžeme pomocou iterátora realizovať napríklad nasledovne:

LinkedList<Integer> list = new LinkedList<>();

// ...

for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    System.out.print(it.next() + " ");
}

Takýto cyklus je pre spájané zoznamy omnoho efektívnejší ako cyklus

for (int i = 0; i <= list.size() - 1; i++) {
    System.out.print(list.get(i) + " ");
}

v ktorom je potrebné pre všetky i vykonať pomalú operáciu get(i). Pre ArrayList je naopak efektívnosť oboch cyklov porovnateľná.

Rozhranie List<E> okrem metódy iterator deklaruje aj metódu listIterator, ktorá vráti „vylepšený” iterátor implementujúci rozhranie ListIterator<E>. Takýto iterátor umožňuje pohybovať sa po zozname obidvoma smermi.

Cyklus for each a iterátory

Cez prvky inštancií iterable tried implementujúcich rozhranie Iterable<T> možno, podobne ako pri poliach, prechádzať pomocou cyklu for each:

for (T x : iterable) {
    // ...
}

V takom prípade je (na rozdiel od polí) tento cyklus ekvivalentný cyklu

for (Iterator<T> it = iterable.iterator(); it.hasNext(); ) {
    T x = it.next();
    // ...
}

(za predpokladu, že it je identifikátor rôzny od všetkých identifikátorov použitých v pôvodnom programe).

Zobrazenia

Rozhranie Map<K, V> reprezentuje zobrazenia, ktoré priraďujú nejakej množine kľúčov (angl. keys) typu K ich obrazy (resp. hodnoty, angl. values) typu V. Najdôležitejšou implementáciou tohto rozhrania je trieda HashMap založená na hešovaní. Kľúčom aj jeho obrazom tu môže byť aj null. Podobne ako HashSet využíva táto trieda metódy hashCode a equals pre jednotlivé kľúče. Niektoré poskytované metódy:

• Metóda public V get​(Object key) vráti obraz kľúča key pri danom zobrazení, ak je definovaný; v opačnom prípade vráti null.
• Metóda public V put​(K key, V value) nastaví obraz kľúča key na hodnotu value.
• Metóda public boolean containsKey​(Object key) zistí, či je key kľúčom, t. j. či je preň definovaný obraz v danom zobrazení.
• Metóda public Set<K> keySet() vráti množinu všetkých kľúčov.
• Metóda public int size() vráti počet všetkých dvojíc kľúč/obraz v danom zobrazení.
• ...

Príklad: nasledujúci program spočíta počty výskytov slov v nejakom vstupnom texte (a na konci ich vypíše v nejakom ľubovoľnom poradí).

import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String word = scanner.next();
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        System.out.println("Pocet roznych slov: " + map.size() + ".");
        for (String word : map.keySet()) {  
            System.out.println("Pocet vyskytov slova \"" + word + "\": " + map.get(word) + ".");
        }
    }
}

Usporiadané množiny a zobrazenia na nich

Java Collections obsahuje aj rozhrania SortedSet<E> resp. SortedMap<K, V> rozširujúce rozhrania Set<E> resp. Map<K, V>. Ide o reprezentácie úplne usporiadaných množín resp. zobrazení s úplným usporiadaním množiny kľúčov. Najdôležitejšími implementáciami týchto rozhraní sú triedy TreeSet<E> resp. TreeMap<K, V>.

• V základnom variante – to jest pri použití konštruktora triedy TreeSet alebo TreeMap bez parametrov – sa predpokladá, že všetky dvojice prvkov, ktoré budú pridávané do množiny resp. budú zohrávať úlohu kľúčov pri zobrazení, sú navzájom porovnateľné pomocou metódy compareTo (použije sa teda tzv. prirodzené usporiadanie prvkov). Typicky sa teda TreeSet<E> a TreeMap<K, V> používajú v prípade, keď typ E resp. K implementuje rozhranie Comparable<E> resp. Comparable<K>. Nie je to ale striktne vyžadované: pomocou konštruktora bez parametrov technicky môžeme vytvoriť napríklad aj inštanciu typu TreeSet<Object>. Akonáhle však do takejto množiny pridáme dvojicu neporovnateľných objektov, dôjde k vyhodeniu výnimky typu ClassCastException.
• Od prirodzeného usporiadania sa tu vyžaduje, aby bolo konzistentné s metódou equals. Pre všetky dvojice objektov e1, e2 daného typu by teda mal mať logický výraz e1.compareTo(e2) == 0 vždy tú istú booleovskú hodnotu ako e1.equals(e2). Štandardné triedy implementujúce rozhranie Comparable, ako napríklad Integer alebo String, túto požiadavku spĺňajú.
• Pri iterovaní cez usporiadanú množinu, ako aj cez množinu kľúčov zobrazenia typu SortedMap, sa prvky prechádzajú vo vzostupnom poradí (čo môže byť užitočné napríklad aj v našom príklade s počítaním výskytov slov).

Komparátory

Alternatívne možno pri triedach TreeSet<E> a TreeMap<K, V> namiesto prirodzeného usporiadania prvkov použiť aj novodefinované usporiadanie (bez ohľadu na to, či na prvkoch daného typu existuje alebo neexistuje prirodzené usporiadanie). V takom prípade vytvoríme inštanciu TreeSet<E> resp. TreeMap<K, V> pomocou konštruktora, ktorý ako argument berie tzv. komparátor prvkov typu E resp. K (alebo ich nadtried).

Pod komparátorom prvkov typu T rozumieme ľubovoľnú inštanciu triedy implementujúcej rozhranie Comparator<T>.

• Toto rozhranie vyžaduje povinnú implementáciu jedinej metódy – a to metódy int compare​(T o1, T o2) na porovnanie dvojice prvkov typu T.
• Výstupom tejto metódy má byť záporné číslo, nula, resp. kladné číslo podľa toho, či je prvý argument menší, rovnako veľký, alebo väčší ako druhý argument.
• Od programátora sa vyžaduje splnenie zvyčajných vlastností úplného usporiadania alebo aspoň úplného predusporiadania (detaily možno nájsť v dokumentácii). Pri použití v súvislosti s Java Collections sa rovnako ako pri prirodzenom usporiadaní obvykle vyžaduje konzistencia s metódou equals.

Príklad:

import java.util.*;

public class OppositeComparator implements Comparator<Integer> {

    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<>(new OppositeComparator());
        set.add(0);
        set.add(1);
        set.add(2);
        set.add(3);
        for (Integer x : set) {
            System.out.print(x + " ");  // Vypise 3 2 1 0
        }
    }
}

Trieda Collections

Trieda Collections obsahuje viacero užitočných statických metód na prácu s Java Collections (ide o akúsi obdobu triedy Arrays pre polia). Sú v nej definované napríklad:

• Metódy sort na utriedenie zoznamu (v dvoch verziách: s použitím prirodzeného usporiadania v prípade, že typ E prvkov zoznamu implementuje Comparable<E>, ako aj s použitím komparátora).
• Metódy shuffle na náhodné premiešanie zoznamu.
• Metódu reverse na otočenie zoznamu.
• ...