{{page>courses:b6b36pjc:styles#common&noheader&nofooter}}
{{page>courses:b6b36pjc:styles#ukoly&noheader&nofooter}}

===== Trie 3 =====

Tento úkol navazuje na [[courses:b6b36pjc:ukoly:trie_2|předchozí domácí úkol]],
kde jste převedli trii jakožto strukturu na trii jakožto třídu a přidali
další užitečné metody. V tomto úkolu rozšíříte svoji trii o další
funkcionalitu, jmenovitě
  * iterátory
  * kopírující konstruktor a přiřazení
  * přesouvající konstruktor a přiřazení
  * ''trie::swap'' -- Prohodí obsah obou listů
  * operátor ''|'' -- Sjednocení dvou trií
  * operátor ''&'' -- Průnik dvou trií
  * porovnávací operátory: ''=='', ''!='', ''<'', ''%%<=%%'', ''>'', ''>=''

Potřebné hlavičkové soubory a testy jsou ke stažení
{{:courses:b6b36pjc:ukoly:trie-3.zip|zde}}.

==== Co odevzdat? ====

Jeden nebo více ''.cpp'' souborů, které implementují funkce deklarované
v souboru ''trie.hpp'' tak, aby testy procházely a neztrácela se paměť. Při práci
na úkolu soubor ''trie.hpp'' neměňte a nemusíte ho ani odevzdávat.

===== Rady =====
  * V inicializačním seznamu lze zavolat jiný konstruktor třídy.
  * Logika iterátoru je stejná, jako u třídy ''word_cursor'' v minulém úkolu

==== Průnik a sjednocení ====
Průnik a sjednocení nad trií se dají velmi snadno napsat rekurzivně a stále
platí, že testovací vstupy jsou schválně nechané dostatečně malé, aby s tím
nebyl problém.

==== Pořadí implementace ====
Pokud chytře zvolíte pořadí implementace nové funkcionality, značně si
zjednodušíte práci. Nějakou představu o vhodném pořadí byste měli mít ze 7.
cvičení, doplníme pouze, že si můžete v některých případech zjednodušit práci i
za pomoci iterátorů.

==== Definice metod vnořených tříd ====
Metody vnořených tříd (například ''trie::iterator'') se definují stejně jako
metody tříd, ale je potřeba si uvědomit, že k jejich plné identifikaci je
potřeba zmínit i (všechny) vnější třídy.
K této deklaraci
<code cpp>
class trie {
    class const_iterator {
        iterator& operator++();
    };
};
</code>
tedy patří tato definice
<code cpp>
trie::const_iterator& trie::const_iterator::operator++() {
    ...
}
</code>

==== Časově náročné testy ====
Mezi testy je i jeden časově náročný test, který je při normálním spuštění
vypnutý. Pokud ho chcete spustit, musíte zavolat výslednou binárku s argumentem
''[.long]'':

''trie3 [.long]''

Silně doporučujeme ho spouštět pouze v optimalizované binárce, tj. stavět v
//Release// módu nebo na příkazové řádce s parametrem ''-O3''.

==== Užitečné hlavičky ====
Implementaci relačních operací si můžete zjednodušit chytrým využitím hlavičky
[[http://en.cppreference.com/w/cpp/header/algorithm|<algorithm>]].