==== Úkol 3 (Trie) ====

Tento úkol spočívá v implementaci jednoduché 
varianty prefixového stromu ([[https://en.wikipedia.org/wiki/Trie|Trie]])
ve stylu standardní knihovny. Varianta, kterou budete implementovat, reprezentuje
každý znak jedním uzlem a má připravené odkazy pro každého možného potomka.

Tato varianta je zbytečně paměťově náročná, ale jednoduchá k implementaci.

/*
Pokud chceme vlastni obrazek, generujici dot:

digraph G {
  "" -> "A"
  "A" -> "B"
  "B"[color=green penwidth=5]
  "C" [color=green penwidth=5]
  "V" [color=green penwidth=5]
  "P" [color=green penwidth=5]
  "" -> "P"
  "P" -> "J"
  "J" -> "C"
  "J" -> "V"
}
*/


V tomto úkolu začneme vytvořením struktury ''trie'', která zastřešuje interní
data skládající se z uzlů reprezentovaných ''trie_node''. Jejich popis najdete níže.

<code cpp>
// Assume only basic ASCII characters
static const size_t num_chars = 128;

struct trie_node {
    trie_node* children[num_chars] = {};
    trie_node* parent = nullptr;
    char payload = 0;
    bool is_terminal = false;
};

struct trie {
    trie_node* root = nullptr;
    size_t size = 0;
};
</code>
  * ''trie::root'' je ukazatel na kořenový uzel stromu
  * ''trie::size'' je počet unikátních slov, které trie obsahuje
  * ''trie_node::children'' je pole ukazatelů na přímé následovníky daného uzlu
  * ''trie_node::parent'' je ukazatel na přímého předka daného uzlu
  * ''trie_node::payload'' je znak, který tento uzel reprezentuje
  * ''trie_node::is_terminal'' označuje, jestli v tomto uzlu končí slovo


Potřebné hlavičkové soubory a testy ke stažení
{{:courses:b6b36pjc:ukoly:trie-1.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.

===== Rady =====
Testy jsou schválně dělané tak, aby bylo možné se ve stromu pohybovat pomocí
rekurze. Tedy se vám ani při naivní implementaci nestane, že vám dojde místo
na stacku, a doporučujeme tedy při implementaci různých operací přemýšlet
rekurzivně.

Stejně tak doporučujeme implementovat plnění všech dat do uzlů. V tomto úkolu se
bez toho obejdete, ale ty následující je budou využívat a je snadnější to udělat
napoprvé.

==== Rekurzivní průchod std::string ====
Funkce pracující s trií dostávají jako argument ''std::string const&''. Abyste
si nemuseli vždy předávat referenci na ''std::string'' a index, kde zrovna
v průchodu jste, můžete si ze ''std::string'' vzít ukazatel na C-style
řetězec.

Následující kód projde a vypíše celý řetězec ze ''std::string'' bez použití délky.
Podobným způsobem se můžete posouvat v řetězci uvnitř trie.
<code cpp>
#include <string>
#include <iostream>

int main() {
    std::string s = "Hello world";
    const char* sptr = s.c_str();
    while (*sptr) {
        std::cout << *sptr << '\n';
        sptr++;
    }
}
</code>

==== Přístup ke smazané paměti ====
Dávejte si pozor na přístup ke smazané paměti, protože jakmile jednou kus paměti
uvolníte, všechna data v ní jsou pro vás ztracena. To znamená, že například při
mazání trie je potřeba každému uzlu nejdříve smazat potomky, a až potom uzel samotný.

==== Užitečné hlavičky ====
Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme.