Trie: Prefixový strom

V tomto úkolu budete implementovat jednoduchou variantu prefixového stromu (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.

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ářů1).

Archiv s testy, hlavičkou trie.hpp a CMakeLists.txt najdete 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) 4.00
Iterators (stage2) 4.25
Copy, move, compare (stage3) 3.00
Stage 4
Get prefixes 1.25
Search by prefix 2.00
Union 1.25
Intersection 1.25
Stage 5
Intersection: algorithmic complexity 1.00
Swap: algorithmic complexity 1.00
Erase destroys nodes 1.00
Celkem 20.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 <string>
#include <iostream>
 
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, <utility> a <algorithm>.

Implementaci relačních operací (stage3) si můžete zjednodušit chytrým využitím hlavičky <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í funkcionality2).

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

1)
Speciálně formátované komentáře, ze kterých lze automaticky generatovat HTML dokumentaci
2)
Některé případy jsou i na cvičení
courses/b6b36pjc/ukoly/trie.txt · Last modified: 2020/10/09 20:42 by richta