Letný semester, prednáška č. 4

Oznamy

• Počas najbližších cvičení, čiže v stredu 10. marca od 11:30 do 13:00 bude prebiehať prvý test. Bude pozostávať z troch úloh zameraných na látku z prvých troch týždňov, ktorých riešenia bude potrebné odovzdávať na testovač. Po dobu riešenia testu je potrebná účasť na stretnutí „Cvičenia” v MS Teams.
• V stredu tiež budú zverejnené dve nebodované úlohy k štvrtým cvičeniam, zamerané na látku z dnešnej prednášky. Ďalšie podobne zamerané úlohy budú zverejnené na cvičeniach budúci týždeň.
• Prvú domácu úlohu je potrebné odovzdať najneskôr do začiatku budúcej prednášky, čiže do pondelka 15. marca, 9:00.

Výnimky

Mechanizmus výnimiek (angl. exceptions) slúži v Jave na spracovanie chýb a iných výnimočných udalostí, ktoré môžu počas vykonávania programu nastať. Doposiaľ sme v našich programoch takéto situácie viac-menej ignorovali – napríklad sme obvykle predpokladali, že vstup vždy spĺňa požadované podmienky, že súbor, z ktorého sa pokúšame čítať, vždy existuje, atď. Dôvodom bola predovšetkým prílišná prácnosť ošetrovania chýb pomocou podmienok a neprehľadnosť programov, ktoré takéto podmienky obsahujú.

Uvažujme napríklad nasledujúci jednoduchý program, ktorý zo vstupu načíta prirodzené číslo n nasledované n celými číslami, ktoré postupne poukladá do poľa dĺžky n. Následne číta zo vstupu postupnosť indexov v rozmedzí 0 až n-1 a po každom načítaní indexu i zvýši hodnotu a[i] o jedna. Načítavanie vstupu sa ukončí po načítaní reťazca "KONIEC".

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int a[] = new int[n];
    for (int i = 0; i <= n - 1; i++) {
        a[i] += scanner.nextInt();
    }
    String next = scanner.next();
    while (!next.equals("KONIEC")) {
        a[Integer.parseInt(next)]++;
        next = scanner.next();
    }
}

Vykonávanie tohto programu môže skončiť chybou viacerými rôznymi spôsobmi: používateľ napríklad môže namiesto niektorého čísla zadať nečíselný reťazec; číslo n môže ďalej zadať ako záporné, čím vznikne chyba pri pokuse o alokovanie poľa; niektorý z ním zadaných indexov do poľa tiež nemusí byť v požadovanom rozmedzí. Po pokuse o ošetrenie týchto chýb pomocou podmienok dostávame nasledujúci horibilný program.

/** Nasledujuci kod je ukazkou toho, ako sa osetrovanie chyb v Jave NEMA robit. */

/** Metoda, ktora zisti, ci je retazec nebielych znakov reprezentaciou celeho cisla. */
private static boolean isInteger(String s) {
    Scanner stringScanner = new Scanner(s);
    return stringScanner.hasNextInt();
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = 0;
    if (scanner.hasNextInt()) {
        n = scanner.nextInt();
        if (n < 0) {
            System.err.println("Pocet prvkov pola nemoze byt zaporny.");
            System.exit(2);
        }
    } else {
        System.err.println("Vstup sa nezacina cislom.");
        System.exit(1);
    }
    int a[] = new int[n];
    for (int i = 0; i <= n - 1; i++) {
        if (scanner.hasNextInt()) {
            a[i] += scanner.nextInt();
        } else {
            System.err.println("Niektory z prvkov pola nebol zadany ako cele cislo.");
            System.exit(3);
        }
    }
    String next = scanner.next();
    while (!next.equals("KONIEC")) {
        if (isInteger(next)) {
            int i = Integer.parseInt(next);
            if (i >= 0 && i <= n - 1) {
                a[i]++;
            } else {
                System.err.println("Niektory z indexov do pola je mimo povoleneho rozmedzia.");
                System.exit(5);
            }
        } else {
            System.err.println("Niektory z indexov do pola nebol zadany ako cele cislo.");
            System.exit(4);
        }
        next = scanner.next();
    }
}

Vidíme, že už aj pri takto jednoduchej úlohe dostávame pomerne rozsiahly program, v ktorom väčšinu kódu zaberá práve spracovanie chýb. Ešte nepríjemnejšou je však skutočnosť, že ošetrovanie chýb je potrebné implementovať v mieste programu, kde táto chyba vznikla. To vedie k prelínaniu podstatných častí programu s časťami, ktoré slúžia iba na spracovanie chýb, v dôsledku čoho sa kód stáva veľmi neprehľadným. Z uvedených dôvodov sme až doposiaľ podobné chybové udalosti väčšinou ignorovali.

V praxi je ale nutné podobné chyby náležite poošetrovať – nie je totiž napríklad prípustné, aby textový editor spadol zakaždým, keď sa jeho používateľ pokúsi otvoriť súbor s neexistujúcim názvom. Výnimky poskytujú spôsob, ako spracovanie chybových udalostí realizovať podstatne efektívnejším spôsobom, než v ukážke vyššie. Medzi ich základné prednosti totiž patria:

• Možnosť oddelenia kódu na spracovanie chýb od zvyšku kódu.
• Možnosť jednoduchým spôsobom ponechať spracovanie chyby na volajúcu metódu v prípade, že sa to javí ako vhodnejšie riešenie.
• Možnosť využívať pri spracúvaní chýb prostriedky objektovo orientovaného programovania.

Mechanizmus výnimiek v Jave

Pod výnimkou (angl. exception) sa v Jave rozumie inštancia špeciálnej triedy Exception, prípadne jej nadtriedy Throwable, reprezentujúca nejakú výnimočnú udalosť. Trieda Exception má pritom množstvo podtried reprezentujúcich rôzne typy chybových udalostí.

• Výnimka môže počas vykonávania nejakej metódy f vzniknúť buď tak, že ju vyhodí JVM (napríklad pri delení nulou alebo pri prístupe k neexistujúcemu prvku poľa), alebo tak, že ju vyhodí sama táto metóda pomocou príkazu throw (detaily nižšie).
• Vzniknutá výnimka môže byť priamo odchytená a ošetrená v rámci danej metódy f. V opačnom prípade je vykonávanie metódy ukončené a výnimka je posunutá metóde g, ktorá metódu f volala (posunieme sa teda v zásobníku volaní metód o úroveň nižšie).
• V metóde g sa na celú situáciu dá pozerať tak, akoby výnimka vznikla pri vykonávaní príkazu, v rámci ktorého sa volala metóda f. Opäť teda môže byť výnimka buď odchytená a ošetrená, alebo rovnakým spôsobom predaná metóde, ktorá volala metódu g (aj v takom prípade hovoríme, že metóda g vyhodila výnimku, hoci reálne výnimka vznikla už v metóde f).
• Takto sa v zásobníku volaní metód pokračuje nižšie a nižšie, až kým je nájdená metóda, ktorá danú výnimku odchytí a spracuje.
• Ak sa takáto metóda na zásobníku volaní nenájde – čiže je výnimka vyhodená aj metódou main na jeho dne – typicky dôjde k ukončeniu vykonávania programu a k vypísaniu informácií o výnimke (vrátane zásobníka volaní metód) na štandardný chybový výstup; ide tu ale o zjednodušenie.

Chytanie a ošetrovanie výnimiek

Odchytenie a spracovanie výnimky možno v Jave realizovať nasledujúcim spôsobom:

• Kód, v ktorom môže výnimka nastať, obalíme do bloku try.
• Kód spracúvajúci výnimku umiestnime do bezprostredne nasledujúceho bloku catch. Za samotným kľúčovým slovom catch nasleduje jeden argument reprezentujúci výnimku, ktorá sa má odchytiť. Napríklad blok catch (Exception e) odchytí ľubovoľnú výnimku, ktorá je inštanciou triedy Exception (alebo nejakej jej podtriedy).
• Kedykoľvek nastane v bloku try výnimka, okamžite sa vykonávanie tohto bloku ukončí. Ak je vzniknutá výnimka kompatibilná s argumentom bloku catch, pokračuje sa blokom catch a výnimka sa považuje za odchytenú. (Ak výnimka s týmto argumentom nie je kompatibilná, bude správanie rovnaké ako pri absencii bloku try.)

Príklad: Uvažujme program, ktorý prečíta zo vstupného súboru vstup.txt prirodzené číslo n a za ním n celých čísel. Napokon vypíše na konzolu súčet načítaných čísel. V takomto programe môže nastať výnimka predovšetkým z dvoch dôvodov: súbor vstup.txt nemusí existovať alebo môže nastať iná chyba pri pokuse o vytvorenie inštancie triedy Scanner; nemusí byť dodržaný požadovaný formát vstupného súboru a môže tak vzniknúť výnimka pri volaní metódy nextInt triedy Scanner. Kód teda môžeme obaliť do bloku try a prípadnú výnimku môžeme spracovať napríklad jednoduchým výpisom textu "Nieco sa pokazilo." do štandardného chybového výstupu. Všetok kód nasledujúci za blokom catch sa vykoná bez ohľadu na to, či výnimka nastala alebo nenastala.

import java.io.*;
import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        try {
            Scanner scanner = new Scanner(new File("vstup.txt"));
            int n = scanner.nextInt();
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += scanner.nextInt();
            }
            System.out.println("Sucet je: " + sum + ".");
            scanner.close();
        } catch (Exception e) {
            System.err.println("Nieco sa pokazilo.");
        }
        System.out.println("Aj po odchytenej vynimke pokracujem dalej a vypisem tento text...");
    }
}

Namiesto výpisu textu "Nieco sa pokazilo." by sme napríklad mohli vypísať aj informácie o vzniknutej výnimke použitím metódy

e.printStackTrace();

Uvedené riešenie má ale dva menšie nedostatky:

• V prípade vyhodenia výnimky nikdy nedôjde uzatvoreniu vstupného súboru, pretože vykonávanie bloku try sa preruší ešte predtým, než príde na rad príslušný príkaz. O niečo vhodnejšou alternatívou by bolo presunutie príkazu na zatvorenie scanner-a až za koniec bloku try; ale aj vtedy by sa mohlo stať, že sa tento príkaz nevykoná kvôli nejakej výnimke, ktorá nebola odchytená (napríklad inštancia typu Throwable, alebo výnimka vyhodená v bloku catch). Riešením je pridať za bloky catch blok finally, ktorý sa vykoná bez ohľadu na to, či nastala výnimka a či sa nám ju podarilo odchytiť (dokonca sa vykoná aj v prípade, že sa v try bloku úspešne vykonal príkaz return).

import java.io.*;
import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        Scanner scanner = null;
        try {
            scanner = new Scanner(new File("vstup.txt"));
            int n = scanner.nextInt();
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += scanner.nextInt();
            }
            System.out.println("Sucet je: " + sum + ".");
        } catch (Exception e) {
            System.err.println("Nieco sa pokazilo.");
        } finally {
            if (scanner != null) {
                scanner.close();
            }
        }
        System.out.println("Aj po odchytenej vynimke pokracujem dalej a vypisem tento text...");
    }
}

• Nerozlišujeme medzi dvoma najpravdepodobnejšími príčinami vyhodenia výnimky: medzi chybou nejakým spôsobom súvisiacou s manipuláciou so súborom vstup.txt a medzi chybou spôsobenou zlým formátom vstupu. To sa dá napraviť s využitím skutočnosti, že výnimky pre rôzne udalosti sú typicky rôzneho typu (vždy ale ide o inštancie podtried Throwable a zvyčajne aj Exception). V prvom prípade sa vyhodí výnimka, ktorá je inštanciou triedy IOException z balíka java.io alebo nejakej jej podtriedy (napríklad FileNotFoundException). V druhom prípade pôjde o výnimku typu NoSuchElementException z balíka java.util, vyhodenú metódou nextInt triedy Scanner. Za blok try môžeme pridať aj viacero blokov catch pre viacero typov výnimiek. V prípade, že je niektorá výnimka „kompatibilná” s viacerými takýmito blokmi, bude odchytená prvým z nich.

import java.io.*;
import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        Scanner scanner = null;
        try {
            scanner = new Scanner(new File("vstup.txt"));
            int n = scanner.nextInt();
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += scanner.nextInt();
            }
            System.out.println("Sucet je: " + sum + ".");
        } catch (IOException e) {
            System.err.println("Chyba suvisiaca s pristupom k suboru vstup.txt.");
        } catch (NoSuchElementException e) {
            System.err.println("Zly format vstupneho suboru.");
        } catch (Exception e) {
            // Takto spracovat vynimku, o ktorej nic netusime, nie je uplne najlepsi napad (takze len na ukazku).
            System.err.println("Nejaka ina vynimka.");   
        } finally {
            if (scanner != null) {
                scanner.close();
            }
        }
        System.out.println("Aj po odchytenej vynimke pokracujem dalej a vypisem tento text...");
    }
}

• Pokiaľ používateľ zadá číslo n ako záporné, správa sa program rovnako ako keby bolo n rovné nule. Možno vhodnejšie by ale aj v takom prípade bolo vyhodiť chybu, ktorá by používateľa upozornila na to, že zadal zlý vstup. Túto fukncionalitu doplníme neskôr, pretože budeme potrebovať vedieť hádzať „úplne nové” výnimky.

Hierarchia výnimiek

V Jave existuje množstvo tried pre rôzne druhy výnimiek. Malá časť hierarchie týchto tried je znázornená na nasledujúcom obrázku.

Všetky výnimky v Jave dedia od triedy Throwable. Tá má dve podtriedy:

• Exception, od ktorej dedí väčšina „bežných” výnimiek.
• Error, od ktorej dedia triedy reprezentujúce závažné, v rámci aplikácie ťažko predpovedateľné systémové chyby (napríklad nedostatok pamäte). Jednou z najznámejších podtried triedy Error je StackOverflowError.

Podtriedy triedy Exception možno ďalej rozdeliť na dve základné kategórie:

• RuntimeException a jej podtriedy. Výnimky tohto typu obvykle reprezentujú rozličné programátorské chyby, ako napríklad prístup k neexistujúcemu prvku poľa (ArrayIndexOutOfBoundsException), delenie nulou (ArithmeticException), použitie kódu „očakávajúceho” objekt na referenciu null (NullPointerException), atď. Do tejto kategórie patria aj výnimky typu NoSuchElementException, hoci tie sme v príklade vyššie možno trochu zneužili na ošetrenie zlého formátu vstupného súboru. Vo všeobecnosti platí, že výnimky tohto typu by buď nemali vôbec nastať (programátorské chyby, ktoré je nutné odladiť), alebo by mali byť ošetrené priamo v metóde, v ktorej vzniknú (ako napríklad NoSuchElementException v našom príklade vyššie).
• Zvyšné podtriedy triedy Exception. Tie často reprezentujú neočakávateľné udalosti, ktorým sa na rozdiel od výnimiek typu RuntimeException nedá úplne vyhnúť (napríklad FileNotFoundException a jej nadtrieda IOException). Dobre napísaný program by sa mal vedieť z výnimiek tohto typu zotaviť (nie je napríklad dobré ukončiť program vždy, keď sa mu nepodarí otvoriť súbor).

S týmto rozdelením podľa druhov chýb reprezentovaných jednotlivými výnimkami súvisí aj nasledujúca nutnosť:

• Výnimka ľubovoľného typu okrem RuntimeException, Error a ich podtried musí byť v metóde, v ktorej môže vzniknúť, vždy buď odchytená, alebo v opačnom prípade ich musí táto metóda deklarovať vo svojej hlavičke ako neodchytené. Napríklad:

void f() throws FileNotFoundException, UnsupportedEncodingException {
    // ...
}

• Popri vykonaní príkazu return je totiž vyhodenie výnimky ďalším možným spôsobom ukončenia vykonávania volanej metódy. Preto musí byť táto možnosť v hlavičke metódy explicitne špecifikovaná rovnako ako napríklad návratový typ.
• Pri inštanciách triedy RuntimeException a jej podtried sa od tejto požiadavky upúšťa, pretože – ako bolo spomenuté vyššie – ide väčšinou o programátorské chyby, ktoré je nutné odladiť, alebo sú tieto výnimky odchytené priamo v metóde, v ktorej vzniknú. Pri inštanciách triedy Error a jej podtried zas často ide o systémové chyby, zotavenie z ktorých principiálne nie je možné. Často je teda najlepším riešením ukončiť samotný program.

Hádzanie výnimiek a výnimky nových typov

Vyhodenie novej výnimky možno pre inštanciu e triedy Throwable alebo jej podtried realizovať príkazom

throw e;

Najčastejšie sa pritom throw aplikuje na novovytvorenú inštanciu nejakej triedy, napríklad

throw new IOException();

alebo

throw new IOException("Sprava");

Pre úplne nové typy chybových udalostí sa vo všeobecnosti neodporúča používať výnimky existujúcich typov. Naopak je vhodnejšie napísať novú podtriedu triedy Exception reprezentujúcu výnimky požadovaného typu a následne pomocou throw vyhadzovať inštancie tejto triedy. Napríklad pre účely nášho ukážkového programu vyššie môžeme napísať triedu výnimiek NegativeElementCountException, ktorej inštancie budeme vyhadzovať zakaždým, keď používateľ zadá ako počet čísel zápornú hodnotu. Táto trieda môže vyzerať napríklad nasledovne.

public class NegativeElementCountException extends Exception {
    Integer number;

    public NegativeElementCountException() {
        number = null;  // Netreba
    }

    public NegativeElementCountException(int number) {
        this.number = number;
    }

    @Override
    public String getMessage() {
        if (number != null) {
            return "Zaporny pocet cisel: " + number + ".";
        } else {
            return "Zaporny pocet cisel.";
        }
    }
}

Použitie tejto výnimky v samotnom programe potom môže vyzerať napríklad takto.

import java.io.*;
import java.util.*;

public class Trieda {

    public static void main(String[] args) {
        Scanner scanner = null;
        try {
            scanner = new Scanner(new File("vstup.txt"));
            int n = scanner.nextInt();
            if (n < 0) {
                throw new NegativeElementCountException(n);
            }
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += scanner.nextInt();
            }
            System.out.println("Sucet je: " + sum + ".");
        } catch (IOException e) {
            System.err.println("Chyba suvisiaca s pristupom k suboru vstup.txt.");
        } catch (NoSuchElementException e) {
            System.err.println("Zly format vstupneho suboru.");
        } catch (NegativeElementCountException e) {
            System.err.println(e);
        } finally {
            if (scanner != null) {
                scanner.close();
            }
        }
        System.out.println("Aj po odchytenej vynimke pokracujem dalej a vypisem tento text...");
    }
}

Generické programovanie

V minulom semestri sme videli viacero abstraktných dátových typov a dátových štruktúr, ako napríklad zásobník alebo rad hodnôt typu T, či binárny strom uchovávajúci v uzloch hodnoty typu T. Typ T mohol byť často ľubovoľný, inokedy sa naň kládli určité podmienky (napríklad pri binárnych vyhľadávacích stromoch mohla byť takouto podmienkou existencia úplného usporiadania na T). Zakaždým sme ale boli schopní napísať implementácie týchto dátových štruktúr iba pre jeden pevne zvolený typ; v C++ sme síce pomocou typedef tento typ vedeli rýchlo meniť, ale mohli sme sa dostať do problémov v situáciách, keď sme potrebovali pracovať s dvoma inštanciami tej istej dátovej štruktúry pre dva rozdielne typy.

Pri využití nástrojov objektovo orientovaného programovania sa ponúka jedno rýchle východisko z tejto situácie: mohli by sme napríklad napísať zásobník, rad, alebo strom uchovávajúci inštancie triedy Object – inštanciami triedy Object sú totiž úplne všetky objekty. Aj tento prístup má ale svoje veľké nevýhody: napríklad pri zásobníku reťazcov by sme museli všetky objetky vyberané zo zásobníka pretypovať na String, čo by bolo nielen prácne, ale aj náchylné na chyby (niekto napríklad mohol omylom vložiť na zásobník objekt, ktorý nie je inštanciou triedy String). Ukážeme si teraz elegantnejšie riešenie podobných situácií pomocou generického programovania, ktoré umožňuje parametrizovať triedy a metódy typovými parametrami. Tento nástroj vo veľkej miere využívajú aj dátové štruktúry zo štandardnej knižnice tried jazyka Java.

Generické triedy

Triedu, ktorá závisí od typového parametra T – takzvanú generickú triedu – možno v Jave napísať takto:

public class GenerickaTrieda<T> {
    // ...
}

Trieda môže závisieť aj od viacerých typových parametrov, napríklad:

public class GenerickaTrieda<T1, T2, T3, T4> {
    // ...
}

Vo vnútri generickej triedy možno v nestatickom kontexte s typovými parametrami pracovať podobne, ako keby išlo o bežnú triedu (pri určitých obmedzeniach; nemožno napríklad tvoriť nové inštancie typového parametra). Napríklad:

import java.util.*;

public class GenerickaTrieda<T> {
    private T[] a;

    public GenerickaTrieda(T[] a) {
        this.a = Arrays.copyOf(a, a.length);
    }

    // ...
}

Pri vytváraní inštancií generickej triedy za typový parameter dosadíme typový argument, ktorým môže byť ľubovoľný neprimitívny typ (čiže napríklad trieda alebo rozhranie):

Integer a[] = {1, 2, 3, 4, 5};
GenerickaTrieda<Integer> g = new GenerickaTrieda<Integer>(a);

alebo skrátene

Integer a[] = {1, 2, 3, 4, 5};
GenerickaTrieda<Integer> g = new GenerickaTrieda<>(a);

• Zápis <> (takzvaný diamant) možno použiť kedykoľvek je typový argument zrejmý z kontextu (využíva sa tu mechanizmus automatickej inferencie typov).

Pre každú konkrétnu triedu KonkretnaTrieda teda máme typ GenerickaTrieda<KonkretnaTrieda>, ktorý sa chová podobne ako trieda (možno z neho tvoriť inštancie a pod., ale existujú určité drobné obmedzenia jeho použitia).

• Ak je pritom KonkretnaTrieda podtriedou triedy InaKonkretnaTrieda, tak každý objekt typu KonkretnaTrieda je súčasne aj inštanciou triedy InaKonkretnaTrieda. Táto relácia sa neprenáša na typy GenerickaTrieda<KonkretnaTrieda> a GenerickaTrieda<InaKonkretnaTrieda>.
• Napríklad inštanciu typu GenerickaTrieda<Integer> teda nemožno použiť v situácii, keď sa očakáva inštancia typu GenerickaTrieda<Object>.
• Aj generická trieda ale môže dediť od inej triedy, rovnako ako každá iná trieda:

class Trieda1 {
    
}

class Trieda2<T> extends Trieda1 {  
    // OK, v tele triedy mozeme pouzivat typovy parameter T.
} 

class Trieda3<T> extends Trieda2<T> {  
    // OK, pre kazde T je instancia parametrizovanej triedy Trieda3<T> sucasne aj instanciou Trieda2<T>.
}

class Trieda4<T> extends Trieda2<Integer> {  
    // OK, pre vsetky T je instancia Trieda4<T> sucasne aj instanciou Trieda2<Integer>.
    // Parameter T pre Trieda4 nijak nesuvisi s parametrom T pre Trieda2.
}

class Trieda5 extends Trieda2<Integer> {
    // OK.
}

class Trieda6 extends Trieda2<T> {
    // CHYBA: nie je jasne, co je T.
}

• Podobne ako generické triedy možno tvoriť aj generické rozhrania.

Príklad: uzol binárneho stromu ako generická trieda

Základ generickej triedy Node<T> reprezentujúcej uzol binárneho stromu uchovávajúci inštanciu value nejakej triedy T môže vyzerať napríklad nasledovne.

public class Node<T> {
    private T value;
    private Node<T> left, right;

    public Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        String leftString = "";
        String rightString = "";
        if (left != null) {
            leftString = "(" + left.toString() + ") ";
        }
        if (right != null) {
            rightString = " (" + right.toString() + ")";
        }
        return leftString + this.value + rightString;
    }
}

• Trieda Node<T> teda poskytuje konštruktor, ktorý ako parameter berie uchovávanú inštanciu triedy T a referencie na ľavého a pravého syna.
• Trieda taktiež implementuje metódu toString, ktorá vráti „infixovú textovú reprezentáciu” stromu.

Program využívajúci triedu Node<T> môže vyzerať napríklad takto:

public static void main(String[] args) {
    Node<Integer> integerRoot = new Node<>(4,
            new Node<>(3,
                    new Node<>(9, null, null),
                    new Node<>(2, null, new Node<>(5, null, null))),
            new Node<>(0, null, null));
    Node<String> stringRoot = new Node<>("koren",
            new Node<>("lavy syn korena",
                    new Node<>("nieco", null, null),
                    new Node<>("nieco ine", null, new Node<>("nieco este ine", null, null))),
            new Node<>("pravy syn korena", null, null));
    System.out.println(integerRoot);
    System.out.println(stringRoot);
}

Generické metódy

Podobne ako generické triedy možno tvoriť aj jednotlivé generické metódy, pri ktorých sa typové parametre píšu pred návratový typ. Tieto parametre sú „viditeľné” iba v rámci danej metódy. Pri volaní metódy možno za tieto parametre buď explicitne dosadiť konkrétne triedy, alebo sa o to postará automatický mechanizmus inferencie typov.

Príklad: nasledujúca generická statická metóda createFullTree vytvorí plný binárny strom danej výšky height, ktorého uzly všetky obsahujú rovnakú inštanciu value triedy dosadenej ako argument za typový parameter T.

public class Trieda {

    public static <T> Node<T> createFullTree(int height, T value) {
        if (height == 0) {
            return new Node<>(value, null, null);
        } else {
            return new Node<>(value, createFullTree(height - 1, value), createFullTree(height - 1, value));
        }
    }

    public static void main(String[] args) {
        Node<Integer> root1 = Trieda.<Integer>createFullTree(4, 0);
        Node<String> root2 = createFullTree(4, "retazec");  // Skrateny zapis spoliehajuci sa na automaticku inferenciu typu
        System.out.println(root1);
        System.out.println(root2);
    }
}

Ohraničené typové parametre

Často nastáva situácia, keď typový parameter nemôže byť úplne ľubovoľný, ale musí spĺňať určité podmienky. Predpokladajme napríklad, že by sme do našej generickej triedy Node<T> chceli pridať metódu, ktorá nájde najmenší prvok typu T uložený v niektorom z uzlov podstromu, ktorého je daný uzol koreňom. Takáto úloha dáva zmysel iba vtedy, keď je na T definované úplné usporiadanie – čiže keď možno inštancie triedy T navzájom porovnávať. V štandardných triedach jazyka Java býva táto možnosť vyjadrená tým, že daná trieda T implementuje rozhranie Comparable<T>.

Trieda T implementujúca Comparable<U> pre nejakú – vo všeobecnosti aj inú – triedu U, musí poskytovať metódu

public int CompareTo(U o);

ktorá vráti záporné číslo, nulu, alebo kladné číslo podľa toho, či je inštancia this triedy T menšia, rovná, alebo väčšia ako inštancia o triedy U. To samozrejme dáva najväčší zmysel, keď je U to isté ako T – v takom prípade je možné inštancie triedy T porovnávať medzi sebou. Triedy T implementujúce rozhranie Comparable<T> vždy poskytujú metódu

public int CompareTo(T o);

s významom opísaným vyššie.

Chceli by sme teda obmedziť typový parameter pre generickú triedu Node<T> tak, aby zaň mohla byť dosadená iba inštancia triedy T implementujúcej rozhranie Comparable<T>. To možno urobiť pomocou takzvaného ohraničeného typového parametra. Pre ľubovoľnú triedu AnyClass a pre ľubovoľné rozhranie AnyInterface možno typový parameter písať ako

<T extends AnyClass>

resp.

<T extends AnyInterface>

čím sa vyjadrí, že typový parameter T musí byť podtriedou triedy AnyClass resp. musí implementovať rozhranie AnyInterface (aj pri rozhraniach sa naozaj píše slovo extends).

Upravená trieda pre uzol binárneho stromu tak môže vyzerať napríklad nasledovne.

public class Node<T extends Comparable<T>> {
    private T value;
    private Node<T> left, right;

    public Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        String leftString = "";
        String rightString = "";
        if (left != null) {
            leftString = "(" + left.toString() + ") ";
        }
        if (right != null) {
            rightString = " (" + right.toString() + ")";
        }
        return leftString + this.value + rightString;
    }

    public T minValue() {
        T result = value;
        if (left != null && result.compareTo(left.minValue()) > 0) {
            result = left.minValue();
        }
        if (right != null && result.compareTo(right.minValue()) > 0) {
            result = right.minValue();
        }
        return result;
    }
}

public class Trieda {

    public static <T extends Comparable<T>> Node<T> createFullTree(int height, T value) {
        if (height == 0) {
            return new Node<>(value, null, null);
        } else {
            return new Node<>(value, createFullTree(height - 1, value), createFullTree(height - 1, value));
        }
    }

    public static void main(String[] args) {
        // ...
        System.out.println(root.minValue());
    }
}

Divoké karty

Vieme už, že ak je trieda SubClass podtriedou triedy SuperClass, tak napríklad inštancia parametrizovanej triedy Node<SubClass> už nebude inštanciou parametrizovanej triedy Node<SuperClass>. Hoci teda každý uzol prvého typu svojím spôsobom reprezentuje aj uzol druhého typu, nemožno v situácii, keď sa požaduje inštancia typu Node<SuperClass> použiť inštanciu typu Node<SubClass>. Keby sme teda napríklad chceli napísať (bežnú negenerickú) metódu f, ktorá berie ako argument uzol binárneho stromu uchovávajúci inštanciu triedy SuperClass, alebo niektorej jej podtriedy, nestačilo by napísať metódu

public static void f(Node<SuperClass> root) {
    // ...
}

Keby sme totiž skúsili zavolať túto metódu s parametrom typu Node<SubClass>, program by neskompiloval. Riešením v takýchto situáciách je použitie tzv. divokej karty (angl. wildcard) reprezentovanej symbolom „?”. Napríklad Node<? extends SuperClass> root reprezentuje parameter ľubovoľného z typov Node<SomeClass>, kde SomeClass je podtriedou SuperClass kompatibilnou s ohraničením typového parametra danej generickej triedy. Rovnako ako s nadtriedami môžeme použiť túto notáciu aj s rozhraniami, ktoré majú byť implementované.

public static void f(Node<? extends SuperClass> root) {
    SuperClass minValue = root.minValue();  
    // ...
}

Spolu s takýmito „zhora ohraničenými” divokými kartami možno používať aj „zdola ohraničené” divoké karty v tvare <T super SubClass>, ktorými sa vyjadrí požiadavka, že T je ľubovoľná nadtrieda triedy SubClass kompatibilná s ohraničením typového parametra danej generickej triedy. Podobne možno používať aj „neohraničenú” divokú kartu <?> vyjadrujúcu ľubovoľnú triedu kompatibilnú s ohraničením typového parametra danej generickej triedy (pre generickú triedu Node<T extends Comparable> je teda napríklad parameter Node<?> root ekvivalentný parametru Node<? extends Comparable> root).

Úvod do Java Collections

V štandardných knižniciach jazyka Java možno nájsť viacero generických tried reprezentujúcich rôzne užitočné dátové štruktúry. Tieto triedy sú spoločne známe ako Java Collections, sú poväčšine definované v balíku java.util a vyznačujú sa predovšetkým tým, že implementujú generické rozhranie Collection<E> reprezentujúce nejakú skupinu objektov. Je užitočné tieto triedy poznať a v čo najväčšej miere ich používať. Na tejto prednáške si iba v rýchlosti predstavíme niektoré z nich; podrobnejšie sa nimi budeme zaoberať na nasledujúcej prednáške. Nebudeme tu uvádzať obsiahle zoznamy metód poskytovaných jednotlivými týmito triedami – tieto informácie možno ľahko dohľadať v dokumentácii – a namiesto toho sa zakaždým sústredíme iba na krátku ukážku ich použitia.

Trieda ArrayList

Generická trieda ArrayList<E> reprezentuje dynamické pole prvkov typu E. Toto pole mení svoju veľkosť podľa momentálnej potreby.

• Prvok na koniec poľa 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.
• Dĺžku poľa vracia metóda size.

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) + " ");
        }
    }
}

Rozhranie List a trieda LinkedList

Veľká časť metód poskytovaných inštanciami triedy ArrayList je deklarovaná v rozhraní List, ktoré je implementované triedami reprezentujúcimi nejaký typ zoznamu. Popri triede ArrayList<E> je ďalšou triedou implementujúcou toto rozhranie trieda LinkedList<E> reprezentujúca obojsmerne spájaný zoznam.

• Keďže implementuje rovnaké rozhranie List<E> ako ArrayList<E>, možno na prácu s ním používať podobné metódy. Dokonca je často užitočné zvoliť za typ vstupného argumentu metódy očakávajúcej zoznam priamo rozhranie List; v takom prípade možno metódu volať ako pre ArrayList, tak aj pre LinkedList.
• Treba však pamätať na to, že odlišná implementácia tried ArrayList a LinkedList má za následok aj rozdiely v efektívnosti jednotlivých vykonávaných operácií. V spájanom zozname je oproti poľu podstatne efektívnejšie pridávanie prvkov na jeho začiatok alebo koniec, podobne aj ich odoberanie (LinkedList tu oproti rozhraniu List a triede ArrayList poskytuje aj niekoľko metód navyše). Naopak omnoho menej efektívny je prístup k prvku na danej pozícii pomocou metódy get.
• Vypísanie všetkých prvkov spájaného zoznamu by sme teda v princípe mohli realizovať aj rovnako ako pre polia:

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

Omnoho efektívnejšie je ale použitie iterátora (o tom viac nabudúce):

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

Prípadne tiež možno použiť ekvivalentnú konštrukciu

LinkedList<Integer> list = new LinkedList<>();
// ...
for (Integer x : list) {
    System.out.print(x + " ");
}

Niektoré ďalšie dátové štruktúry

Java Collections obsahuje aj množstvo ďalších tried a rozhraní. Napríklad:

• Rozhranie Set<E> pre množiny a jeho implementácie ako napríklad HashSet<E>.
• Rozhranie Map<K,V> pre zobrazenia (resp. slovníky alebo asociatívne polia), pri ktorých sú kľúče typu K zobrazované na hodnoty typu V. Implementáciou tohto rozhrania je napríklad trieda HashMap<K,V>.
• Trieda Stack<E> reprezentujúca zásobník a rozhranie Queue<E> pre rad, ktoré okrem iného implementuje aj trieda LinkedList<E>.
• ...

Odkazy

• Java tutoriál: Exceptions
• Java tutoriál: Generics
• Java tutoriál: Collections