====== Kolekce ====== ==== 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 přednášky či Herout: Bohatství knihoven, str. 159, 162. === Rozhraní 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(Object o) Očekává se, že metoda ''compareTo(Object 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). | Pozor na nutnost přetypování formálního parametru ''o'' na potřebný datový typ! === Rozhraní 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(Object o1, Object o2) ==== Rozhraní kolekcí ==== === Rozhraní 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(Object o) // vlozeni prvku do kolekce boolean add(Collection c) // vlozeni vsech prvku z kolekce c void clear() // kompletni vymazani kolekce boolean remove(Object 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(Object 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 Object[] toArray(Object[] a) // prevod na pole konkretniho typu === Rozhraní List === Přidává metody usnadňující práci se seznamy, hlavně možnost indexace! Seznamy umožňují uložit tentýž prvek (metoda ''equals()'') vícekrát. void add(int index, Object o) // pridani prvku na index, ostatni prvky budou posunuty Object get(int index) // vraci prvek ulozeny na index Object set(int index, Object o) // zmena prvku na index, vraci ulozeny prvek Object remove(int index) // odstraneni prvku na index, posun indexu, vraci ulozeny prvek int indexOf(Object o) // vraci index prvniho nalezeneho prvku shodneho s o (equals()) int lastIndexOf(Object o) // vraci index posledniho nalezeneho prvku shodneho s o (equals()) List subList(int start, int end) // podseznam od start do end - 1 === 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''. ==== Seznamy ==== === Třída ArrayList === Nejoblíbenější implementace seznamu (= rozhraní ''List''). Rozdíl kapacita x velikost (''int size()''). Zajištění kapacity - konstruktorem ''ArrayList(int vychoziKapacita)'', kde parametrem je výchozí kapacita nebo metodou ''boolean ensureCapacity(int capacity)''. 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í. V Javě 1.5 a výše se využívá tzv. generics (šablony), kolekce mezi ně patří - datový typ, který se bude ukládat do kolekce musí být znám při překladu, jinak bude zobrazeno varování. Pokud typem bude ''Object'' nebo použijeme zástupný symbol ?, lze samozřejmě do kolekce uložit cokoliv. Více na http://java.sun.com/developer/technicalArticles/J2SE/generics/. === 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 seznamu, * potřebujeme pracovat se začátkem a koncem 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. // vlozeni prvku na zacatek/konec seznamu void addFirst(Object prvek) void addLast(Object prvek) // odebrani prvku ze zacatku/konce seznamu - vraci odebirany objekt Object removeFirst() Object removeLast() // vraceni prvku ze zacatku/konce seznamu Object getFirst() Object getLast() ==== Třída Collections ==== Obdoba třídy ''Arrays''. Poskytuje tytéž metody pro kolekce a další (min, max atp.) navíc. Je z balíku ''java.util''. Metody jsou statické, veřejně přístupné. Existují vždy ve variantě bez objektu /s objektem ''Comparator'' pro přirozené / absolutní řazení. Běžně používané metody následují. // naplneni kolekce hodnotou void fill(Collection c, Object o) // naplneni kolekce stejnou hodnotou // setrideni kolekce void sort(Collection c) void sort(Collection c, Comparator cmp) // binarni vyhledavani v setridene kolekci metodou sort() binarySearch(List list, Object key) binarySearch(List list, Object key, Comparator cmp) // nejvetsi / nejmensi prvek Object max(Collection c) Object max(Collection c, Comparator cmp) Object min(Collection c) Object min(Collection c, Comparator cmp) // zamichani kolekce void suffle(Collection c) void suffle(Collection c, Random rnd) // hledani podseznamu, -1 znamena nenalezeno int indexOfSubList(List list, List subList) int lastIndexOfSubList(List list, List subList) ==== Třída Iterator ==== Iterátor 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, new Integer(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í. ==== Množiny ==== 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. === Třída HashSet === Implementuje rozhraní ''Set'', které nepřidává žádné podstatné metody oproti ''Collection''. === 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. Rozhraní ''SortedSet'' navíc přidává následující metody. // prvni, posledni prvek Object first() Object last() // podmnoziny (dolniHranice je vzdy zahrnuta, horniHranice neni nikdy zahrnuta!) SortedSet headSet(Object horniHranice) SortedSet tailSet(Object dolniHranice) SortedSet subSet(Object dolniHranice, Object horniHranice) === 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 ==== Jiným názvem slovníky (dictionary), umožňují ukládat dvojice klíč-hodnota. Implementují rozhraní ''Map'' a POZOR neimplementují rozhraní ''Collection'', tj. nejsou s kolekcemi zaměnitelné! {{courses:a0b36pr2:tutorials:10:map.png|Rozhraní map a potomci}} Mapy jsou v Javě 1.5 a výše implementovány stejně jako ostatní kolekce pomocí ''generics'' a je třeba na to nezapomenout! === 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ý objekt pro uložení do kolekce ==== - 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!