Při práci s více vlákny lze na narazit na mnoho problémů. Jedním z nich je jak zajistit, aby si jednotlivá vlákna navzájem nepřepisovala a zároveň nečetla sdílená data. Toto by mohlo vést k nekonzistenci takových dat, což by vedlo k chybné funkci programu.
Jedním z možných řešení této situace je jednoduše neumožnit přepisování sdílených dat. V Javě se jedná o vytváření tzv. immutable objektů (tříd). U immutable objektu není možné po jeho vytvoření měnit jeho vnitřní stav. V Javě je typickým představitelem immutable objektu třídy String, v případě primitivních datových typů se jedná o použití klíčového slova final
. Výhodou tohoto řešení je, že jakmile je objekt vytvořen, programátor nemusí hlídat jaká vlákna k němu přistupují (samozřejmě toto je výhoda i jednovláknových programech). Ví totiž, že se jeho stav měnit nebude a tedy nemůže dojít k nekonzistenci dat. Nevýhodou je vyšší paměťová a výpočetní náročnost. V případě potřeby změn dat je potřeba vytvořit nový objekt (copy-on-write). Viz třída String, kdy je například vytváření Stringu v iteraci neefektivní.
final
a zároveň jsou třídy těchto proměnných také immutable.
Za domácí úkol máte vytvořit immutable implementaci listu předepsaného v interface Pr2List (zkráceně list). Tento list je vlastně spojový seznam jak naznačuje i obrázek. Jedná se o druh listu běžně používaný například ve fukncionálních jazycích (Lisp, Scala …). Viz https://en.wikipedia.org/wiki/Cons. List typicky obsahuje odkaz na prvek který uchovává a na list, který obsahuje další prvky. Výjimkou je poslední prvek listu (nazývaný Nil), který reprezentuje zároveň prázný list. Zároveň také naimplementujte metody pro filtrování a mapování obsahu. Viz dále.
Jednotlivé metody listu si nyní projdeme, nezapomeňte si zároveň prostudovat javadoc:
append(T t)
- tato netoda přidá nový prvek do listu mezi poslední stávající prvek a Nil. (Nil zde nebereme jako typický prvek listu). Vrací instanci nového listu, který obsahuje i vkládaný prvek.
cons(T t)
- přidá prvek na začátek listu a vrátí list obohacený o nový prvek. Všimněte si, že tato je narozdíl od append
paměťově relativně nenáročná. Implementujte ji tak.
isEmpty()
- vrátí true pokud je list prázný, tedy pokud se jedná o Nil. Jinak vrací false.
size()
- vrátí počet prvků v listu. Pro Nil je size 0.
filter(Predicate<T> predicate)
- vrátí list bez prvků, které porušují zadaný predicate. Predicate je třída, používaná podobně jako například Comparator. Obsahuje jedinnou metodu, která dokáže pro každý prvek vrátit true anebo false.
map(Function<T, O> function)
- Pozor, nezaměňovat s datovou strukturou Map, pořád se používá list. S Mapou jako takovou je toto spojeno v trochu širším slova smyslu. Funkce map použije zadanou function, která pro každý prvek typu T vrací prvek typu O. map potom vrací nový list typu O, který obsahuje prvky vzniklé aplikací function na prvky původního listu.
head()
- vrátí první prvek v list
tail()
- vrátí list reprezentující zbytek listu, tedy všechno mimo head()
iterator()
- vrací Iterator pro list. Třída Iterator z definice není immutable. Pro ani v tomto úkolu nemusí být Iterator pro list immutable.
view()
- funkce view() souvisí s funkcemi filter
a map
. Viz níže.
map
a filter
se nově také objevili v kolekcích Javy 8. Samozřejmě společně s dalšími užitečnými metodami. Spolu s Lambda funkcemi velmi zjednodušují práci s kolekcemi.
Ukazuje se, že někdy při použití funkcí map
a filter
není třeba tyto hned aplikovat na všechny prvky listu, ale je výhodnější je vyhodnotit lazy. Představme si například situaci, kdy chceme z listu načíst první prvek, který splňuje daný predikát. Pak je zbytečné vyhodnotit vůči tomuto predikátu všechny prvky listu. V případě, že je list velký a víme, že někde blízko začátku se nachází vyhovující prvek, může se jednat o velkou časovou i paměťovou úsporu.
Funkce view()
vrátí takovou instanci listu, která si při volání funkcí map
a filter
bude pamatovat zadané function
a predicate
a bude je vyhodnocovat teprve až to bude potřeba a to jen na minimálním množství prvků. Nezapomeňte i správně implementovat Iterator
pro třídy reprezentující view
. Pozor: jestltiže na view
zavoláme tail()
, vrátí se opět view
reprezentující tail
se stejnými vlastnostmi jako měl původní view
.
Pro implementaci si stáhněte zdrojové kódy s příslušnými interface a factory třídou ListFactory
. Řešení vytvořte do balíčku cz.cvut.k36.pr2.hw.hw06.impl
. Odevzdávejte vámi vytvořené třídy potřebné k provozování listu, včetně implementované třídy ListFactory
. Neodevzdávejte interface Pr2List
, Predicate
a Function
.
ListFactory
implementujte tělo metody nil()
která bude vracet instanci prázdného listu.
Ukázkový kód práce s listem není záměrně k dispozici. Pro testování vašeho řešení si tento kód vytvořte.
Název testu | Stručný popis |
---|---|
polymorphismUse | Jestli jsou jednotlivé view, prázdný list a list s prvky řešeny pomocí polymorfismu. |
emptyListSize | Velikost prázdného listu. |
emptyListHead | Vyhození výjimky v head() u Nil. |
emptyListTail | Vyhození výjimky v tail() u Nil. |
emptyListAppendCons | Append a cons na Nil. |
emptyListIterator | Test hasNext funkce u iterátoru pro Nil. |
emptyListIteratorNext | Vyhození výjimky v iterátoru pro Nil (metoda next()). |
emptyListFilter | Volání filter() na Nil. |
emptyListMap | Volání map() na Nil. |
listWithItems | Test listu s několika prvky. Testují se metody: cons, isEmpty, head, tail, size. |
listWithItemsAppend | List s několika prvky, testují se různé následky po volání append(). |
listWithItemsIterator | List s několika prvky, průběh iteratoru. |
listWithItemsIteratorAfterLastNext | List s několika prvky, průběh iteratoru, vyhození výjimky při volání next() na posledním prvku. |
listWithItemsFilter | Volání filter na listu s prvky. I zde se kontroluje počet volání predikátu, nicméně volání filter() není lazy. |
listWithItemsMap | Volání map na list s prvky. I zde se kontroluje počet volání mapovací funkce, nicméně volání map() není lazy. |
viewSimple | Pro list s prvky se testuje výstup funkce view(). Funkce view() se musí pro čtení chovat stejně jako původní list. |
tailOfSimpleView | Pro list s prvky se testuje výstup funkcí view().tail(). Výstup musí být opět view(), testuje se na mapovací funkci. |
mapView | Pro list s prvky se testuje view().map(). Testuje se počet volání mapovací funkce pro různé volání. |
mapViewIterator | Pro list s prvky se testuje view().map().iterator(). Testuje se postupně pořet volání mapovací funkce. |
filterView | Pro list s prvky se testuje view().filter(). Testuje se počet volání predikátů pro různé volání. |
filterViewEmpty | Pro list s prvky se testuje view().filter() za předpokladu že žádný prvek listu nesplňuje predikát. Testuje se počet volání predikátů pro různé volání. |
filterViewEmptyHead | Pro list s prvky se testuje view().filter() za předpokladu že žádný prvek listu nesplňuje predikát. Testuje se vyhození výjimky pro head(). |
filterViewEmptyTail | Pro list s prvky se testuje view().filter() za předpokladu že žádný prvek listu nesplňuje predikát. Testuje se vyhození výjimky pro tail(). |
filterViewIterator | Pro list s prvky se testuje view().filter().iterator(). Testuje se počet volání predikátů při běhu iteratoru. |
complexView | Testuje se chování a počet volání funkcí/predikátů pro list s prvky, na který platí list.view().filter().map().map().filter() |
emptyListIteratorRemove | Vyhození správné výjimky, situace viz název testu. |
listWithItemsIteratorRemove | Vyhození správné výjimky, situace viz název testu. |
simpleViewIteratorRemove | Vyhození správné výjimky, situace viz název testu. |
filterViewIteratorRemove | Vyhození správné výjimky, situace viz název testu. |
mapViewIteratorRemove | Vyhození správné výjimky, situace viz název testu. |
simpleViewAppend | Vyhození správné výjimky, situace viz název testu. |
filterViewAppend | Vyhození správné výjimky, situace viz název testu. |
mapViewAppend | Vyhození správné výjimky, situace viz název testu. |
simpleViewCons | Vyhození správné výjimky, situace viz název testu. |
filterViewCons | Vyhození správné výjimky, situace viz název testu. |
mapViewCons | Vyhození správné výjimky, situace viz název testu. |