V minulém dílu jsme implementovali spojový seznam. Námi vytvořená kolekce byla poměrně dobře použitelná, ale měla dva nedostatky – jeden týkající se znovupoužitelnosti a druhý výkonnostního rázu. Tyto neduhy si dnes vysvětlíme a kolekci patřičně upravíme.
Nedostatek první: malá znovupoužitelnost
Stávající implementace spojového seznamu umožňuje ukládat pouze hodnoty primitivního typu int. Kdybychom chtěli ukládat cokoliv jiného, tak bychom museli celý seznam přepsat pro daný typ.
Alternativou by mohlo být ukládání záznamů typu Object (jakožto implicitního předka všech objektů), ale pak bychom vždy museli objekt navrácený metodou get přetypovat na konkrétního potomka. Toto by bylo jednak nešikovné, druhak by to vedlo k chybám, kterým by jinak zabránila silná typová kontrola.
Generics
Javovská generika (generics), přidaná v Javě 1.5, řeší tento problém. Umožňují vytvářet parametrizované datové typy, kterým při jejich konstrukci (volání) předáme typový parametr označující třídu, se kterou mají pracovat.
Pokud bychom tedy chtěli do seznamu ukládat Integery, tak předáme patřičný typový parametr, pokud se o dva řádky níže rozhodneme pro nový seznam řetězců, předáme typ String. Takto parametrizovaný seznam bude mít také silnou typovou kontrolu – do seznamu řetězců nevložíme číslo (a naopak), stejně tak metoda get vždy vrátí objekt předaného typu.
Parametrizování třídy/rozhraní
Třídu/rozhraní parametrizujeme pomocí čárkou oddělených typových parametrů umístěných do špičatých závorek ihned za název třídy/rozhraní. Typový parametr je řetězec, který bude při kompilaci nahrazen předaným typem.
Pojmenování typového parametru
Pojmenovávání typových parametrů podléhá stejným pravidlům jako názvy proměnných (musí začínat písmenem, dolarem ($) nebo podtržítkem (_)). Dle konvence používáme pro jména typových parametrů pouze velká písmena (často pouze jedno velké písmeno).
Parametr v rozhraní ListIface
/**
* Rozhrani, jez definuje operace, ktere musi splnit kazda implementace seznamu
* @author Pavel Micka
*/
public interface ListIface<ENTITY> {
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
public void add(ENTITY i);
/**
* Vrati prvek na indexu i
* @param i index prvku
* @return prvek na indexu i
*/
public ENTITY get(int i);
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
*/
public void remove(int i);
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size();
}
Zde jsme předali rozhraní seznamu z minulého dílu typový parametr ENTITY. Všimněme si, že nyní metoda add obsahuje generický parametr volání a metoda get vrací objekt totožného typu. Pokud nyní toto rozhraní implementujeme, tak máme jistotu, že námi vytvořená třída bude akceptovat (a vracet) objekty libovolné předem specifikované třídy.
Typový parametr třídy MyLinkedList
/**
* Jednosmerne zretezeny spojovy seznam
* @author Pavel Micka
* @param <ENTITY> typovy parametr specifikujici ukladany typ
*/
public class MyLinkedList<ENTITY> implements ListIface<ENTITY> {
private Node first;
private Node last;
private int size;
/**
* Konstruktor spojoveho seznamu
*/
public MyLinkedList() {
this.size = 0;
}
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
public void add(ENTITY i) {
Node n = new Node(i);
if (size == 0) {
this.first = n;
this.last = n;
} else {
this.last.next = n;
this.last = n;
}
size++;
}
/**
* Vrati prvek na indexu i
* @param i index prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
* @return prvek na indexu i
*/
public ENTITY get(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
Node curr = first;
for (int j = 0; j < i; j++) {
curr = curr.next;
}
return curr.value;
}
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
*/
public void remove(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
if (i == 0) {
first = first.next;
} else {
Node curr = first;
for (int j = 0; j < i - 1; j++) { //najdeme predchozi
curr = curr.next;
}
curr.next = curr.next.next; //a mazany prvek vynechame
if (i == size - 1) { //pokud mazeme posledni
last = curr;
}
}
size--;
}
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size() {
return this.size;
}
/**
* Klasicka toString metoda, vraci textovou reprezentaci objektu
* @return textova reprezentace objektu
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node curr = first;
for (int i = 0; i < this.size; i++) {
builder.append(curr.value);
builder.append(" ");
curr = curr.next;
}
return builder.toString();
}
/**
* Vnitrni trida reprezentujici jeden uzel spojoveho seznamu
*/
private class Node {
private ENTITY value;
private Node next;
private Node(ENTITY value) {
this.value = value;
}
}
}
V hlavičce třídy jsme stejně jako u rozhraní specifikovali typový parametr. Tento parametr jsme rovnou poslali o úroveň výš do rozhraní, abychom specifikovali také jeho generický typ.
Generikum dále využíváme v metodách get a add a ve vnitřní třídě Node. Oproti původní implementaci jsme jím pouze nahradili příslušné výskyty primitivního typu int (který byl původně ukládán).
Volání
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
ListIface<Integer> l = new MyLinkedList<Integer>();
l.add(0);
l.add(10);
System.out.println(l.get(1)); //10
ListIface<String> l2 = new MyLinkedList<String>();
l2.add("pes");
System.out.println(l2.get(0)); //pes
//Neznamy (libovolny) typovy parametr rozsirujici tridu String
ListIface<? extends String> l3 = l2;
l3.get(0);
//Nepouziti typoveho parametru
ListIface l4 = new MyLinkedList();
l4.add(new Object());
}
V prvním volání vytváříme proměnnou typu ListIface s typovým parametrem Integer a přiřazujeme do ní odpovídající instanci seznamu. Tento seznam můžeme bezpečně používat jako kontejner na celá čísla. Další seznam (l2) funguje identicky, ale pro řetězce (String). Do seznamu l3 můžeme ukládat pouze typy, které rozšiřují třídu String a String samotný (pomiňme pro jednoduchost příkladu, že je třída String finální). Poslední možností je nepoužít při volání generika vůbec.
Generika umí více
Generika jsou mocnou zbraní, která umí výrazně více, než jsme si dnes ukázali. Lze vytvářet generické typy generických typů. Specifikovat nejen, že třída je potomkem jiné třídy, ale že také implementuje některá rozhraní. Dokonce můžeme řici, že se generický typ váže pouze k nadtypům nějaké třídy. V neposlední řadě můžeme dokonce typovat jednotlivá volání metod.
Tyto vlastnosti mají ale poměrně specifické použití, proto si je ukážeme až v případě, že na ně narazíme.
Co generika neumí
Generika ale bohužel nejsou všemocnou zbraní. Jejich omezení plyne ze skutečnosti, že jsou jakýmsi cukrem nad kompilátorem (v bytekódu neexistují).
Kompilátor pro nás emuluje v bytekódu generika stejným způsobem, jakým bychom jich docílili my, kdyby neexistovala (tj. používali bychom Javu 1.4 a starší). Místo generických typů dosadí třídu Object a na patřičných místech provádí přetypování na třídu, kterou vyžadujeme.
Z tohoto důvodu nemůžeme používat typové parametry za běhu programu (v daný okamžik již neexistují). Pokud bychom informaci o třídě typových parametrů přesto potřebovali, tak by bylo nejjednodušší dané typy předat konstruktoru (při konstrukci objektu je znát musíme) a tyto třídy si později vracet.
/**
* Demonstrace omezeni generik
* @author Pavel Micka
*/
public class Foo<BAR> {
public Class<?> getParameterClass(){
return BAR.class; //toto nelze udelat, typovy parametr jiz neexistuje
}
}
Nedostatek druhý: průchod seznamem
Druhým nedostatkem je, že pokud bychom chtěli vypsat všechny prvky, tak bychom museli n-krát volat metodu get. Tímto způsobem bychom při každém volání přeiterovali všechny předhozí prvky (metoda get nemá žádnou paměť, do které by ukládala, kde jsme byli minule). Spotřebovali bychom proto kroků, což je velké mrhání časem procesoru.
Iterátor
Z tohoto důvodu zavedeme do seznamu novou strukturu – iterátor. Iterátor si můžeme představit jako ukazovátko do seznamu, které si pamatuje pozici současného prvku. Iterátoru se můžeme zeptat, zda-li existuje v seznamu další prvek, a pokud ano, tak si jej můžeme vyžádat. Žádost o další prvek vyústí v přesun ukazovátka o jednu pozici dále. Tímto způsobem projde iterátor seznam v krocích.
Implementace
Iterátor přidáme spojovému seznamu prostřednictvím implementace rozhraní Iterable (dokumentace), čímž získáme navíc jednu velmi zajímavou vlastnost – naši kolekci budeme moci procházet pomocí for-each cyklu.
public interface ListIface<ENTITY> extends Iterable<ENTITY> {
.
.
.
}
V hlavičce našeho rozhraní ListIface předáme rozhraní Iterable typový parametr ENTITY, který zajistí, že metoda iterator bude vracet iterátor odpovídajícího typu (iterujícího přes objekty typu ENTITY).
Iterator
Třída Iterator má tři metody. Tou první je hasNext – dotaz na existenci dalšího prvku, druhou next – vracející další prvek a v neposlední řadě nepovinnou metodu remove, která odstraní současný prvek.
Iterátor, který vytvoříme, bude nejjednodušší možný – nebude implementovat metodu remove a nebude fail-fast.
Fail-fast implementace iterátoru by vyhodila výjimku v okamžiku, kdy by byl seznam změněn jinak než iterátorem (byl by např. smazán prvek, na který iterátor ukazuje – ten by pak totiž byl v nedefinovaném stavu).
/**
* Jednosmerne zretezeny spojovy seznam
* @author Pavel Micka
* @param <ENTITY> typovy parametr specifikujici ukladany typ
*/
public class MyLinkedList<ENTITY> implements ListIface<ENTITY> {
.
.
.
@Override
public Iterator iterator() {
return new LinkedListIterator();
}
/**
* Jednoduchy iterator pro spojovy seznam
* Neresi situaci, kdy je iteratoru pod rukou pozmena kolekce (tj. neni fail fast)
*/
private class LinkedListIterator implements Iterator<ENTITY> {
private Node currNode;
private boolean start;
public LinkedListIterator() {
this.currNode = null;
this.start = true;
}
@Override
public boolean hasNext() {
if (start) {
return first != null;
}
return currNode.next != null;
}
@Override
public ENTITY next() {
if (start) {
start = false;
currNode = first;
} else {
currNode = currNode.next;
}
return currNode.value;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove is not supported");
}
}
Metoda iterator, jak jsme si již řekli, vrací objekt iterátoru. Technicky vzato bychom jej mohli vytvořit jako anonymní třídu, ale to je v tomto případě spíše záležitost vkusu.
Samotný iterátor (typovaný kvůli návratové hodnotě metody next) obsahuje referenci na aktuální prvek a příznak start.
Start využijeme na počátku průchodu, protože for-each cyklus prochází seznam následujícím způsobem – nejprve se zeptá na existenci dalšího prvku voláním hasNext a pokud existuje, tak na něj přejde. V okamžiku prvního volání se tedy musí iterátor nacházet na pozici -1, což simulujeme právě zmíněným příznakem.
Metoda hasNext vrátí true, pokud existuje další uzel spojového seznamu, false v opačném případě. Next přejde na další uzel. Metoda remove pouze vyhodí výjimku (v kontraktu – textovém popisu metody rozhraní – je napsáno, že je tato fukcionalita volitelná).
Výsledný kód
Kód spojového seznamu, po zahrnutí generik a iterátoru vypadá následovně:
/**
* Jednosmerne zretezeny spojovy seznam
* @author Pavel Micka
* @param <ENTITY> typovy parametr specifikujici ukladany typ
*/
public class MyLinkedList<ENTITY> implements ListIface<ENTITY> {
private Node first;
private Node last;
private int size;
/**
* Konstruktor spojoveho seznamu
*/
public MyLinkedList() {
this.size = 0;
}
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
@Override
public void add(ENTITY i) {
Node n = new Node(i);
if (size == 0) {
this.first = n;
this.last = n;
} else {
this.last.next = n;
this.last = n;
}
size++;
}
/**
* Vrati prvek na indexu i
* @param i index prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
* @return prvek na indexu i
*/
@Override
public ENTITY get(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
Node curr = first;
for (int j = 0; j < i; j++) {
curr = curr.next;
}
return curr.value;
}
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
* @throws IndexOutOfBoundsException pokud je i vyssi nebo rovna delce seznamu
* @throws IllegalArgumentException pokud je i zaporne
*/
@Override
public void remove(int i) {
if (i >= size) {
throw new IndexOutOfBoundsException("Mimo meze index:" + i + ", size:" + this.size);
}
if (i < 0) {
throw new IllegalArgumentException("Index mensi nez 0");
}
if (i == 0) {
first = first.next;
} else {
Node curr = first;
for (int j = 0; j < i - 1; j++) { //najdeme predchozi
curr = curr.next;
}
curr.next = curr.next.next; //a mazany prvek vynechame
if (i == size - 1) { //pokud mazeme posledni
last = curr;
}
}
size--;
}
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
@Override
public int size() {
return this.size;
}
/**
* Klasicka toString metoda, vraci textovou reprezentaci objektu
* @return textova reprezentace objektu
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
Node curr = first;
for (int i = 0; i < this.size; i++) {
builder.append(curr.value);
builder.append(" ");
curr = curr.next;
}
return builder.toString();
}
@Override
public Iterator iterator() {
return new LinkedListIterator();
}
/**
* Jednoduchy iterator pro spojovy seznam
* Neresi situaci, kdy je iteratoru pod rukou pozmena kolekce (tj. neni fail fast)
*/
private class LinkedListIterator implements Iterator<ENTITY> {
private Node currNode;
private boolean start;
public LinkedListIterator() {
this.currNode = null;
this.start = true;
}
@Override
public boolean hasNext() {
if (start) {
return first != null;
}
return currNode.next != null;
}
@Override
public ENTITY next() {
if (start) {
start = false;
currNode = first;
} else {
currNode = currNode.next;
}
return currNode.value;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Remove is not supported");
}
}
/**
* Vnitrni trida reprezentujici jeden uzel spojoveho seznamu
*/
private class Node {
private ENTITY value;
private Node next;
private Node(ENTITY value) {
this.value = value;
}
}
}
/**
* Rozhrani, jez definuje operace, ktere musi splnit kazda implementace seznamu
* @author Pavel Micka
*/
public interface ListIface<ENTITY> extends Iterable<ENTITY> {
/**
* Vlozi na konec seznamu prvek
* @param i prvek k vlozeni
*/
public void add(ENTITY i);
/**
* Vrati prvek na indexu i
* @param i index prvku
* @return prvek na indexu i
*/
public ENTITY get(int i);
/**
* Smaze prvek na indexu i
* @param i index mazaneho prvku
*/
public void remove(int i);
/**
* Dotaz na delku seznamu
* @return delka seznamu
*/
public int size();
}
Volání
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
ListIface<Integer> l = new MyLinkedList<Integer>();
l.add(0);
l.add(10);
l.add(20);
l.add(30);
l.add(40);
System.out.println(l); //toString
for(Integer i : l){
System.out.print(i + " ");
}
}
0 10 20 30 40
0 10 20 30 40