====== Úloha k procvičení 6 - Immutable funkcionální list ======

<note important>Tato úloha je domací úkol z letního semestru 2013. Od té doby nebyla revidována ani nebyly opraveny potenciální nedostatky v zadání.</note>

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. [[https://en.wikipedia.org/wiki/Immutable_object|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 [[http://docs.oracle.com/javase/7/docs/api/java/lang/String.html|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 ([[https://en.wikipedia.org/wiki/Copy-on-write|copy-on-write]]). Viz třída String, kdy je například vytváření Stringu v iteraci neefektivní.

<note tip>V Javě lze zaručit, že je třída immutable pokud jsou všechny její proměnné uvedeny klíčovým slovem ''final'' a zároveň jsou třídy těchto proměnných také immutable.</note>

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.

{{https://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Cons-cells.svg/685px-Cons-cells.svg.png}}

<note warning>Při implementaci řešení nepoužívejte žádné kolekce z Java frameworku ani od jiné třetí strany.</note>

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.

<note tip>Funkce ''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.</note>

==== view() ====
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 [[https://en.wikipedia.org/wiki/Lazy_evaluation|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''.

==== Implementace úlohy ====
Pro implementaci si stáhněte {{:courses:a0b36pr2:opt:opt06.zip|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''.

<note important>
Poznámky k implementaci:
  * Vypadá to, že upload system zvládá Javu 7, klidně ji tedy použijte :-).
  * Prázdný list, list s položkami a jednotlivé view reprezentujte pomocí polymorfismu.
  * Do třídy ''ListFactory'' implementujte tělo metody ''nil()'' která bude vracet instanci prázdného listu.
  * Nezapomeňte implementovat výjimky popsané v dokumentaci u **všech** implementovaných interface. Text u výjimek není kontrolovaný, nicméně zamyslete se, jaký popis by tam byl nejvhodnější.
</note>

<note tip>Zamyslete se nad implementací. Většina implementovaných metod ve vzorovém řešení se vejde na jeden řádek. Jako nápovědu můžete využít fakt, že ve vzorovém řešení není ani jeden cyklus.</note>

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.

==== Stručný popis testů ====
^ 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.|