1 - Úvodní cvičení

• pro vyučující: 01

Na cvičení můžete (ale nemusíte) využít projekt lab01 včetně třídy Stopwatch na měření času.

• 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.

• 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

• 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 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č?

• 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.

Zdroj: Wikipedia.

Pro řešení semestrálních prací v předmětu PR2 budeme používat verzovací systém 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).

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.

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

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 lab01.zip.

Další informace o Mavenu naleznete například na oficiálním webu.

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.

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.

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<T> 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<T> c) // odstraneni prvku, ktere jsou zaroven v kolekci c
boolean retainAll(Collection<T> c) // odstraneni prvku, ktere nejsou zaroven v kolekci c
 
// TESTY NA PRVKY
boolean contains(T o) // pravda, kdyz o je prvkem
boolean contains(Collection<T> c) // pravda, kdyz vsechny prvky c jsou prvkem
 
// ZISKANI ITERATORU
Iterator<T> iterator()
 
// PREVOD KOLEKCE NA POLE
Object[] toArray() // prevod na pole Objectu
T[] toArray(T[] a) // prevod na pole konkretniho typu

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)

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í.

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 ArrayListu.

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()

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:

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)

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.

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 dokumentaci.

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<Integer> c = new ArrayList<Integer>(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
    ...
  }

Iterator byste také měli preferovat před indexovaným přístupem (pokud je to možné), například v případě LinkedListu se může jednat o výrazné urychlení kódu.

Implementují rozhraní 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.

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.

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.

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.

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ě.

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.

Konkrétní implementace rozhraní Map, rychlost mapy záleží na kvalitě metody hashCode() prvku.

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

Pokud zamýšlíme vkládat třídu

1. 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.
2. 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!

1. 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.
2. 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ů.
3. 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:rurcz.zip.
4. Program doplňte o frekvenční charakteristiku a výpis od nejčetnějšího.