====== 1 - Úvodní cvičení ====== * pro vyučující: [[courses:a0b36pr2:internal:tutorialinstruction:01:start|]] Úkoly na příští cvičení: * Nastudujte si základy práce s verzovacím systémem Git * Vyberte si téma [[courses:a0b36pr2:semester-project/start|semestrální práce]]. Toto téma pak napište na vaší wiki na FEL Gitlabu. * Vytvořte projekt (v Mavenu) vaší semestrální práce a nahrajte ho do gitu. V tomto projektu bude základní struktura souborů. Nezapomeňte na push, samotný commit nestačí. * POZOR: Tento úkol nepodceňujte. Za jeho splnění je 0 bodů, nicméně za každý den prodlení se odečítá 1 bod! ===== Úkoly na cvičení ===== Na cvičení můžete (ale nemusíte) využít projekt {{:courses:a0b36pr2:labs:lab01.zip|lab01}} včetně třídy ''Stopwatch'' na měření času. ==== Pole ==== * Vytvořte datovou třídu reprezentující nosné rakety (nosiče, orbital launcher). Pro jednoduchost uvažujte pouze dvě vlastnosti nosné rakety -- jméno a nosnost (payload) v kilogramech. Zatím neimplementujte metody equals() a hashCode(). * Tuto třídu rozšiřte o implementaci interface Comparable, které bude řadit sestupně podle nosnosti. * Vytvořte pole obsahující nosiče uvedené v tabulce (viz níže). Položky budou v poli ve stejném pořadí jako v tabulce. * Vyzkoušejte si řazení pomocí metody Arrays.sort(). * Vytvořte externí Comparator řadící podle názvu nosiče (A -> Z) a vyzkoušejte si opět řazení pomocí Arrays.sort(). * Totéž proveďte s daty uloženými v Listu a pomocí metod ze třídy Collections. ==== ArrayList vs LinkedList ==== * Vyzkoušejte si přidat 10 000 000 prvků do ArrayListu a LinkedListu a porovnejte časovou náročnost. * Vyzkoušejte si časovou náročnost průchodu ArrayListu a LinkedListu pomocí indexovaného přístup. * Vyzkoušejte si časovou náročnost průchodu ArrayListu a LinkedListu pomocí for-each konstruktu. * Naplňte ArrayList a LinkedList různými daty. Následně: * odeberte polovinu dat při indexovaném průchodu * odeberte polovinu dat za využití for-each iteratoru * porovnejte časovou náročnost a náročnost zápisu programu ==== Množiny (Set) ==== * Zkuste vložit nosič Saturn V opakovaně do množiny. Před každým vložením vytvořte pokaždé objekt reprezentující tuto [[https://en.wikipedia.org/wiki/Saturn_V|legendární raketu]]. Co se stane a proč? * Implementujte metody equals() a hashCode() jenom podle nosnosti. Následně zkuste vložit do množiny nosiče Energia a Mars Colonial Transporter. K čemu došlo a proč? ==== Mapy ==== * Zkuste si data z tabulky uložit přímo do mapy, která bude mapovat název (String) na nostnost (Integer). Jaké má tento přístup výhody a nevýhody. ==== Tabulka nosičů ==== ^ Název ^ Nosnost (Kg) ^ | Saturn V | 118 000 | | SLS | 130 000 | | N1 | 90 000 | | Falcon 9 | 18 785 | | Ariane 5 | 21 000 | | Energia | 100 000 | | Mars Colonial Transporter | 100 000 | | UR-500 Proton | 23 000 | Zdroj: [[https://en.wikipedia.org/wiki/Comparison_of_orbital_launchers_families|Wikipedia]]. ===== Verzovací systém Git ===== Pro řešení semestrálních prací v předmětu PR2 budeme používat verzovací systém [[http://git-scm.com/|Git]]. Verzovací systém umožňuje udržovat historii vývoje projektu, což může být výhodné, jestliže např. potřebujeme získat kus kódu který jsme smazali apod. Toto také usnadňuje zálohování projektu. Zároveň také umožňujě komfortní práci více programátorů na jednom projektu. Existují různé verzovací systémy, Git patří mezi rozšířenější (jsou pomocí něj spravovány zdrojové kódy Linuxového jádra). Repozitář Linuxového jádra (a mnoho dalších) je pro čtení volně přístupný. Podívat se na něj můžete na adrese [[https://github.com/torvalds/linux]]. Jedná se pravděpodobně o jeden z největších repozitářů na světě. V době psaní tohoto přístpěvku v něm bylo úctyhodných 495 tisíc commtů. Pozor pokud byste si ho chtěli stáhnout, připravte si na disku cca 2 GiB volného místa. Verzovací systémy uchovávají zdrojové kódy projektu společně s historií jejich vývoje v tzv. repozitáři. Jednotlivé změny v historii se nazývají revize (někdy také "commit"). Vývojář má typicky aktuální zdrojové kódy stažené na svém počítači, kde v nich provádí změny. Ve chvíli, kdy je se změnami spokojen, změny tzv. commitne. Verzovací systém v té chvíli vytvoří novou revizi, kde je uchována informace o tom, co se změnilo (modifikace souborů, přidání nových, smazání atd.). Ve většině případů musí také vývojář zadat také zprávu, která popisuje daný commit. Tyto změny jsou nahrány na server, kde se provede aktualizace repozitáře a kde si je můžou jiní vývojáři stáhnout. Pokud více vývojářů pošle vytvoří svoje commity, musí je v době nahrávání na server sloučit (merge). V některých případech lze merge provést automaticky (byly editovány odlišné soubory), v jiných případech musí vývojář provést sloučení ručně. K tomu mu mohou pomoci další nástroje. Verzovací systémy se dělí na dvě skupiny: centralizované (např. SVN, CVS) a distribuované (např. Git, Mercurial). Centralizované verzovací systémy se vyznačují tím, že repozitář projektu je uchováván na serveru a uživatelé (vývojáři) mají na svém počítači stažený pouze zdrojový kód platný pro některou z revizí. Každý commit je tedy zároveň i nahrání změn na server. U distribuovaných systémů oproti tomu mají uživatelé stažený celý repozitář na svém počítači. Commit se pak ukládá pouze lokálně a na server je nahraný až při tzv. push operaci. Oproti tomu, synchronizace se serverem (stažení commitů jiných uživatelů) se provádí pomocí pull operace. Pro nastudování Gitu a nastavení Gitlabu doporučujeme využít [[https://sites.google.com/a/fel.cvut.cz/gitlab-informace/|příslušný návod]]. Demo GITu: [[https://try.github.io]] ===== Apache Maven ===== [[https://maven.apache.org/|Maven]] je tzv. build nástroj především pro jazyk Java. Jeho cílem je usnadnit správu projektů v Javě a jejich kompilaci. Samotný Maven je rozšiřitelný pomocí pluginů. Základním souborem pro Maven je soubor 'pom.xml' (pom je zkratka pro Project Object Model). V tomto souboru se ve formátu xml nacházejí informace o projektu včetně využívaných knihoven apod. Maven má předem danou adresářovou strukturu, která popisuje jaké soubory mají být kam umístěny. Základní struktura je tato ^ pom.xml | soubor pom.xml | ^ ./src/main/java/ | adresář se zdrojovými kódy | ^ ./src/test/java/ | adresář se zdrojovými kódy testů | ^ ./target/ | adresář se zkompilovanými soubory, vytváří si Maven sám | ==== Dependence ==== Pokud začnete používat Maven na menším projektu, nejčastější motivací pravděpodobně bude systém dependencí. Jedná se o způsob, jak k projektu snadno přidat externí knihovny. Každá knihovna je popsána pomocí trojice atributů (stejně jako každý Maven projekt): * ArtifactId * GroupId * Version Pokud tyto atributy přidáme do souboru 'pom.xml', Maven tyto knihovny automaticky vyhledá a stáhne. Zároveň také stáhne všechny, knihovny, na kterých je požadovaná knihovna závislá. Vyzkoušejte si na ukázkovém projektu {{:courses:a0b36pr2:labs:lab01.zip|}}. Další informace o Mavenu naleznete například na [[https://maven.apache.org/guides/getting-started/maven-in-five-minutes.html|oficiálním webu]]. ===== Rozšíření práce s poli ===== Pole jsou známa od počátku programovacích jazyků. Mezi hlavní výhody patří rychlý přístup k prvkům pole pomocí indexu. Operaci výběru lze provést v konstantním čase. Dále je to typová jednota a v Javě též možnost uchovávat prvky primitivních datových typů. Nevýhodou klasických polí je hlavně nemožnost změny velikosti a absence podpůrných metod, například pro vyhledávání prvků podle hodnoty. === Třída Arrays === Rozšíření práce s poli, v balíku ''java.util'' - poskytuje následující metody: public static List asList(); // prevede pole na kolekci typu List, vhodna napr. pro vypisy public static boolean equals(); // porovnani poli public static void fill(); // naplneni pole konst. hodnotou public static void sort(); // setrideni pole public static binarySearch(); // binarni vyhledavani v setridenem poli metodou sort() Metody jsou přetíženy pro základní datové typy a pro typ Object (viz dokumentace). Pro použití metody ''Arrays.equals()'' pro strukturované datové typy je nutné zastínit metodu ''equals()'', kterou dědí všechny objekty ze třídy ''Object''. Přitom je nutné dodržet podmínky: reflexivita, symetrie, tranzitivita (jedná se o relaci ekvivalence) a dále konzistenci a nerovnost s null. Též je třeba zastínit metodu ''hashCode()'' zděděnou od ''Object'', protože pokud ''equals()'' vrací ''true'' pro dva objekty, pak by jejich ''hashCode()'' měl být stejný. Podrobněji viz ''Bloch, Joshua. Effective java. Pearson Education India, 2008.'' Item 7. ===== Kolekce ===== === Collection === Rozhraní poskytující metody pro práci s prvky kolekcí. Je základem rozhraní ''List'' a ''Set''. Mezi nejdůležitější metody patří následující. // VLASTNOSTI boolean isEmpty() // pravda, kdyz je kolekce prazdna int size() // pocet prvku v kolekci // VKLADANI, RUSENI PRVKU boolean add(T o) // vlozeni prvku do kolekce boolean add(Collection c) // vlozeni vsech prvku z kolekce c void clear() // kompletni vymazani kolekce boolean remove(T o) // odstraneni prvku o (pokud je v kolekci vicekrat, odstrani se nahodne jeden) boolean remove(Collection c) // odstraneni prvku, ktere jsou zaroven v kolekci c boolean retainAll(Collection c) // odstraneni prvku, ktere nejsou zaroven v kolekci c // TESTY NA PRVKY boolean contains(T o) // pravda, kdyz o je prvkem boolean contains(Collection c) // pravda, kdyz vsechny prvky c jsou prvkem // ZISKANI ITERATORU Iterator iterator() // PREVOD KOLEKCE NA POLE Object[] toArray() // prevod na pole Objectu T[] toArray(T[] a) // prevod na pole konkretniho typu ==== List ==== List (česky seznam) je datová struktura, který uchovává vložené prvky v pořadí v jakém byly vloženy (nicméně jejich pořadí se dá změnit). Také umožňuje uložit tentýž prvek (metoda ''equals()'') vícekrát. Přestože List obecně umožňuje indexovaný přístup, ne vždy je toto vhodné (například v případě LinkedListu) === Třída ArrayList === Nejoblíbenější implementace listu. Je založena na vnitřním poli v kterém jsou uchovávány vložené objekty. Předpokládejme, že máme ''ArrayList'' plný, tedy velikost je rovna kapacitě. Pokud přidáme další prvek dojde k vytvoření nového vnitřního pole o velikosti 1,5 násobku původní velikosti a překopírování hodnot do nového pole. Toto zaručí, že vložení jednoho prvku je v průměrném případě lineární. === Třída LinkedList === Tato třída implementuje rozhraní ''List'' pomocí obousměrně zřetězeného seznamu. Vhodná, pokud * provádíme časté změny v prostředku seznamu, * potřebujeme pracovat se začátkem seznamu. Naopak nevhodná je tato třída pro přímý (indexovaný) přístup k prvkům seznamu, protože indexovaný přístup je lineární vzhledem k velikosti indexu nikoli konstantní jako je tomu u ''ArrayList''u. Implementuje rozhraní ''Collection'' a ''List'' a dále nabízí metody pro práci s prvním a posledním prvkem seznamu (z rozhraní ''Queue''). // vlozeni prvku na zacatek/konec seznamu void addFirst(T prvek) void addLast(T prvek) // odebrani prvku ze zacatku/konce seznamu - vraci odebirany objekt T removeFirst() T removeLast() // vraceni prvku ze zacatku/konce seznamu T getFirst() T getLast() === Comparable === Slouží pro implementaci přirozeného řazení - objekt má jediné kritérium, podle kterého se řadí - metodou Arrays.sort(). Pro všechy základní datové typy je tato metoda přetížena, pro objektové datové typy ji musíme napsat (viz příklad). balík: java.lang metody: public int compareTo(T o) Očekává se, že metoda ''compareTo(T o)'' bude vracet: |-1, či jiné záporné číslo | Tento objekt je menší než druhý objekt (předaný jako parametrem). | |0 | Objekty jsou si rovny. | |1, či jiné kladné číslo | Tento objekt je větší než druhý objekt (předaný jako parametrem). | === Comparator === Slouží k implementaci absolutního řazení nebo řazení v případech, kdy nelze jednoduše implementovat rozhraní Comparable (např. hotová třída, do které nemůžeme zasahovat, nebo jde o objekty, které chceme řadit podle různých kritérií. Např. Studenty budeme jednou řadit podle data narození, jindy podle jména a jindy podle studijního průměru). Opět se využívá přetížených metod třídy ''Arrays'' - všechny přijímají jako poslední parametr objekt implementující rozhraní ''java.util.Comparator''. balik: java.util metody: int compare(T o1, T o2) === Rozhraní Set === Podpora pro implementaci množin. Množiny neumožňují uložit tentýž prvek (metoda ''equals()'') vícekrát. Rozhraní nepřináší žádné podstatné metody navíc k metodám rodičovského rozhraní ''Collection''. ==== Třída Collections ==== Obdoba třídy ''Arrays''. Poskytuje tytéž metody pro kolekce a další (min, max atp.) navíc. Metody jsou statické, veřejně přístupné. Seznam metod lze nalézt v [[http://docs.oracle.com/javase/8/docs/api/java/util/Collections.html|dokumentaci]]. ==== Třída Iterator ==== [[http://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html|Iterator]] zajišťuje přístup k prvkům ve všech kolekcích (vč. ''Map''). Jedná se o postupný průchod kolekcí. Iterátory jsou vždy na jedno použití! Nový iterátor vždy ukazuje před první prvek! // deklarace kolekce a naplneni Collection c = new ArrayList(10); Collections.fill(c, 1); // ziskani iteraoru a pruchod koleci s odstranovanim prvku for (Iterator it = c.iterator(); it.hasNext(); ) { it.next(); it.remove() } Pozor na metodu ''remove()'': * nesmí být volána dříve než metoda ''next()'', jinak je vyhozena výjimka ''IllegalStateException'' - metoda ''remove()'' maže právě vrácený prvek, * nevrací referenci na mazaný objekt, jako metoda ''remove()'' z rozhraní ''Collection''. Stejně tak je třeba testovat, zda v kolekci existuje ještě další prvek metodou ''hasNext()'', pokud by neexistoval a přesto jsme zavolali ''next()'', bude vyhozena výjimka ''NoSuchElementException''. Pro kolekce implementující ''List'' existuje ''ListIterator'', který umožňuje obousměrný průchod kolekcí. Interátory se často používají pomocí for each zápisu: //kod pro pruchod kolekce for (Iterator it = c.iterator(); it.hasNext(); ) { Object o = it.next(); //operace s o ... } //ekvivalentni zapis pomoci for each for (Object o : c) { //operace s o ... } Všimněte si, že při použití for each je iterátor skrytý a programátor ho nemůže použít. To na jednu stranu omezuje naše možnosti, na druhou stranu to snižuje možnost chyby. Tento zápis je také možno použít pro průchod polem. Jedná se o doporučený postup jak procházet kolekce a měli byste ho použít pokud nemáte explicitní důvod používat Iterator přímo (například odebírání prvků během průchodu apod.). Iterator byste také měli preferovat před indexovaným přístupem (pokud je to možné), například v případě ''LinkedList''u se může jednat o výrazné urychlení kódu. ==== Množiny ==== Implementují rozhraní ''[[http://docs.oracle.com/javase/8/docs/api/java/util/Set.html|Set]]''. Prvek se v množině může vyskytovat pouze jednou, při opětovném pokusu o přidání vrátí metoda ''boolean add(Object prvek)'' ''false''. Narozdíl od seznamů nelze s množinami pracovat pomocí indexů. Pro průchody je třeba využívat iterátory. Další často využívanou metodou je metoda ''contains'', která testuje jestli se prvek v množině již nachází. Typická implementace je pak třída ''HashSet''. === Rozhraní SortedSet a třída TreeSet === Toto rozhraní a tato třída udržuje prvky v kolekci seřazeny (''TreeSet'' - ve stromové struktuře). Pro řazení se využívá buď přirozeného řazení metodou ''compareTo'', tj. prvky musí implementovat rozhraní ''Comparable'' nebo je třeba vytvořit objekto komparátoru, který se předá kolekci jako poslední parametr konstruktoru. === Vztah množiny a podmnožiny === Množinu i podmnožiny lze modifikovat bez vyhození výjimky (narozdíl od seznamů, kde modifikace původního seznamu a následná práce s podseznamem vede k vyhození výjimky). U seřazené množiny není možné přidat prvek menší(větší) než nejmenší(největší) prvek v podmnožině - kvůli správnému zařazení do nadmnožiny - vede na výjimku ''IllegalArgumentException''. ==== Mapy ==== V některých jazycích se používají pod názvem dictionary, umožňují ukládat dvojice klíč-hodnota. Implementují rozhraní ''Map'' a neimplementují rozhraní ''Collection'', často se však uvádí společně s kolekcemi, protože slouží k podobnému účelu. {{courses:a0b36pr2:tutorials:10:map.png|Rozhraní map a potomci}} === Rozhraní Map === Základní rozhraní, poskytuje nejběžnější metody. // VLASTNOSTI boolean isEmpty() // pravda, kdyz je mapa prazdna int size() // pocet prvku v mape // VKLADANI, RUSENI PRVKU Object put(Object klic, Object hodnota) // vlozeni prvku do mapy void putAll(Map m) // vlozeni vsech prvku z mapy m void clear() // kompletni vymazani kolekce Object remove(Object klic) // odstraneni prvku s danym klicem // TESTY NA PRVKY boolean containsKey(Object key) // pravda, kdyz klic je klicem boolean containsValue(Object hodnota) // pravda, kdyz vsechny mapa obsahuje hodnotu // ZISKANI PRVKU Object get(Object klic) // vrati hodnotu odpovidajici klici // PREVOD MAPY NA KOLEKCI Set keySet() // mnozina klicu Set entrySet() // mnozina dvojic klic-hodnota Collection values() // kolekce hodnot (moznost opakovani!) Metody převádějící mapu na jinou kolekci vždy vytvářejí pohled - mělkou kopii! Zvláštností při práci s pohledy (kolekcemi vycházejícími z rozhraní ''Collection'') je, že použití metod jako ''removeAll()'', ''retainAll'' atp. z rozhraní ''Collection'' projeví i v mapě. == Práce s mapou == U klíčů se očekává se vhodná implementace metod ''equals()'' a ''hashCode()''. V případě použití metody ''containsValue()'' je tytéž metody nutné implementovat i pro hodnoty. Nelze získat iterátor pro průchod mapou! Je několik možností jak to obejít - iterátor pro množinu klíčů, hodnot nebo lépe iterátor pro množinu dvojic klíč-hodnota. Dvojice klíč-hodnota je reprezentována instancí rozhraní Map.Entry, které poskytuje následující metody. Object getKey() // vrati klic Object getValue() // vrati hodnotu Object setValue(Object novaHodnota) // nastavi novou hodnotu (modifikace mapy) a vrati starou hodnotu Opět se jedná o práci s pohledem, platí vše co bylo o pohledech řečeno. === Třída HashMap === Konkrétní implementace rozhraní ''Map'', rychlost mapy záleží na kvalitě metody ''hashCode()'' prvku. === Rozhraní SortedMap a třída TreeMap === Obdoba ''SortedSet'' a ''TreeSet''. Seřazená mapa, umožňuje vytvářet pohledy v intervalu klíčů, pracovat s nejnižšším/nejvyšším prvkem. Porovnávání v třídě ''TreeMap'' může být přirozené, pak prvky musí implementovat rozhraní ''Comparable'' nebo lze využít komparátoru, který se předá konstruktoru mapy ''TreeMap(Comparator cmp)''. Object firstKey() // vrati hodnotu patrici k prvnimu klici Object lastKey() // vrati hodnotu patrici k poslednimu klici SortedMap headMap(Object klicHorniHranice) // pohled na mapu od zacatku az do klicHorniHranice, vyjma klicHorniHranice SortedMap tailMap(Object klicDolniHranice) // pohled na mapu od klicDolniHranice vcetne az do konce mapy SortedMap tailMap(Object klicDolniHranice, Object klicHorniHranice) // spojeni predchozcich ==== Vhodná třída pro uložení do kolekce ==== Pokud zamýšlíme vkládat třídu - Vhodná implementace metody ''hashCode()''. V Javě se typicky používá zřetězení pro kolekce založené na hashích tak, aby nedocházelo k jevu clusterování (většina prvků spadne do několika málo bucketů, většina je volné, řetězy jsou dlouhé - lineárni časová složitost vzhledem k velikosti kolekce). Teorie hashovacích funkcí a jejich návrh je ale samozřejmě mimo rámec tohoto předmětu. Jako základní doporučení lze využít Herout: Bohatství knihoven str. 166. - Implementace metody ''equals()'' tak aby se jednalo o ekvivalenci a navíc byla konzistentní a žádná instance se nerovnala ''null''. Shrnutí: Třída vhodná pro uložení do kolekce by měla mít neměnné instance, změna se realizuje náhradou novou instancí, měla by mít překryté metody ''equals()'' a ''hashCode'' a také ''toString()'', která bude vracet smysluplné informace o instanci. Též by měla implementovat rozhraní ''Comparable'' pro přirozené řazení. Nakonec bychom si měli dát pozor na možnost výskytu výjimek třídy ''RuntimeException'' a potomků - na takové výjimky nás neupozorní kompilátor! ==== Příklady na procvičení ==== - Implementujte třídu Student se jménem, příjmením, RČ a studijním průměrem. Vytvořte pár studentů a vložte je do seznamu a množiny. Porovnejte obě kolekce. - Implementujte třídu School, reprezentující střední školu se 4 ročníky studentů a s metodami pro vložení, výber, vypsání seznamu studentů po ročnících a celé školy. Vše abecedně či podle studijních průměrů. - Napište program, který přečte textový soubor a vypíše abecedně všechna slova v textu. Vyzkoušejte jej pro text hry R.U.R:{{courses:a0b36pr2:tutorials:10:rurcz.zip|}}. - Program doplňte o frekvenční charakteristiku a výpis od nejčetnějšího.