===== U3: Trie - prefixový strom =====
V tomto úkolu budete implementovat jednoduchou
variantu prefixového stromu ([[https://en.wikipedia.org/wiki/Trie|Trie]])
ve stylu standardní knihovny.
To znamená, že dostanete hlavičkový soubor
definující třídu ''trie'', včetně jejího rozhraní, a sadu testů, které
ověří, zda vaše implementace funguje tak, jak má. Váš úkol pak bude
naimplementovat jednotlivé metody třídy ''trie'' tak, aby všechny testy
prošly.
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.
/* mezery kolem názvu způsobí zarovnání na střed */
{{ :courses:b6b36pjc:ukoly:trie.png }}
Pro usnadnění implementace jsou testy rozděleny do 5 částí, které na sobě
staví, a z nichž každá testuje jinou část vaší implementace. Díky tomu
můžete pracovat dle testů bez toho, aby se na vás vyvalily chyby, které
zatím ani nemůžete opravit.
==== Zadání ====
Seznam metod, které musíte implementovat najdete v hlavičce ''trie.hpp''.
Co jednotlivé metody mají dělat pak najdete v téže hlavičce, ve formátu tzv. Doxygen
komentářů((Speciálně formátované komentáře, ze kterých lze automaticky
generovat HTML dokumentaci)).
Archiv s testy, hlavičkou ''trie.hpp'' a ''CMakeLists.txt'' najdete
{{:courses:b6b36pcc:ukoly:trie.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.
==== Hodnocení ====
^ **Sekce** ^ Body ^
| Basic functionality (**stage1**) | 3.00 |
| Iterators (**stage2**) | 3.25 |
| Copy, move, compare (**stage3**) | 1.75 |
| **Stage 4** ||
| Get prefixes | 1.00 |
| Search by prefix | 1.25 |
| Union | 1.00 |
| Intersection | 1.00 |
| **Stage 5** ||
| Intersection: algorithmic complexity | 1.00 |
| Swap: algorithmic complexity | 1.00 |
| Erase destroys nodes | 0.75 |
| **Celkem** | **15.00** |
===== 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ů.
==== 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.
#include
#include
int main() {
std::string s = "Hello world";
const char* sptr = s.c_str();
while (*sptr) {
std::cout << *sptr << '\n';
sptr++;
}
}
==== 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 stage1 žádné hlavičky ze standardní knihovny nedoporučujeme. Implementaci
iterátorů (stage2) a funkcí ze stage4 (''get_prefixes'', ''search_by_prefix'',
sjednocení, průnik) si můžete zjednodušit vhodným použitím funkcí ze dvou
hlaviček, [[https://en.cppreference.com/w/cpp/header/utility|]] a
[[https://en.cppreference.com/w/cpp/header/algorithm|]].
Implementaci relačních operací (stage3) si můžete zjednodušit chytrým využitím hlavičky
[[http://en.cppreference.com/w/cpp/header/algorithm|]].
==== Implementační poznámky a rady ====
* 90 % složitosti stage3 (iterátory) se schovává v posunu na další prvek, ale pokud si ho dobře rozmyslíte (a nakreslíte), není to s ním tak zlé.
* V inicializačním seznamu (//initializer list//) lze zavolat jiný konstruktor třídy.
* Funkcionalita v jednotlivých částech a jejich pořadí není náhodné. Pokud se vám některá funkcionalita zdá hrozně složitá, rozmyslete si, jestli si její implementaci nemůžete zjednodušit vhodným využitím již existující funkcionality((Některé případy jsou i na cvičení)).
==== 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.
==== Definice metod vnořených tříd ====
Metody vnořených tříd (například ''trie::const_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 {
const_iterator& operator++();
};
};
tedy patří tato definice
const_iterator::const_iterator& trie::const_iterator::operator--() {
...
}
==== Časově náročné testy (5. krok) ====
Testy v 5. kroku jsou časově náročné, a je potřeba je spouštět pouze
pokud byly zkompilovány s optimalizacemi. Jsou proto schovány za tagem
''[.long]''. V případě, že používáte CMake+CTest, pak se vám automaticky
dají do sady testů, pokud jste konfigurovali build buďto v ''Release'',
nebo v ''RelWithDebInfo''. V ostatních případech si je musíte spustit
manuálně, například takto:
./tests "[.long]"
Silně doporučujeme ho spouštět pouze v optimalizované binárce, tj.
konfigurovat v //Release// módu.
TIP: Obzvlášť na linuxu (a asi i Macu) doporučujeme psát kolem tagů uvozovky,
protože hranaté závorky jsou interpretované shellem jako pattern souboru (tedy
např. ''vector.[ch]pp'' se rozvine na ''vector.cpp vector.hpp'', pokud oba soubory existují).
Pokud žádný takový soubor neexistuje, některé shelly skončí s chybou (zsh),
jiné to pak vezmou tak, jak to je, bez rozbalování (bash).