Tento úkol navazuje na 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í zde.

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.

• 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í 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.

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ů.

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

class trie {
    class const_iterator {
        iterator& operator++();
    };
};

trie::const_iterator& trie::const_iterator::operator++() {
    ...
}

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.

Implementaci relačních operací si můžete zjednodušit chytrým využitím hlavičky <algorithm>.