V tomto úkolu budete implementovat oboustranně spojený spojový seznam, viz Wikipedia, ve stylu standardní knihovny. To znamená, že dostanete hlavičkový soubor definující třídu pjc::list, 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 list tak, aby všechny testy prošly.

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.

Seznam metod, které musíte implementovat najdete v hlavičce list.hpp. Co jednotlivé metody mají dělat pak najdete v téže hlavičce, ve formátu tzv. Doxygen komentářů¹⁾.

Archiv s testy, hlavičkou list.hpp a CMakeLists.txt najdete zde.

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

Doporučujeme o listu přemýšlet a pohybovat se v něm podobně jako ve stromu, to jest rekurzivně. Prakticky to znamená, že by se člověk při průchodu listu neměl orientovat dle velikosti, ale dle struktury – to že jsme v prvním uzlu se pozná tak, že platí prev == nullptr a naopak poslední uzel se pozná dle toho tak, že platí next == nullptr. Ostatní uzly jsou prostě někde v listu a není důležité, kde přesně.

Stejně tak vám doporučujeme vždy aktualizovat ukazatele prvků v listu, i v případě, že to není striktně potřeba. Například když smažete poslední uzel v listu, tak krom přesunutí ukazatele tail doporučujeme vynulovat i ukazatel next předposledního (nově posledního) uzlu listu.

Implementaci si můžete zjednodušit vhodným použití funkcí z dvou hlaviček, <utility> a <algorithm>.

• Při operacích, které modifikují oba listy, silně doporučujeme pracovat přímo s uzly obou listů, ne pouze s prvky uloženými v nich.
• Obvykle se očekává, že merge je stabilní, ale v tomto úkolu to není testováno.
• 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²⁾.
• Když je deklarace třídy v nějakém namespace, musí v něm být i definice.
• Pokud máte problém s komplexitou metody split, zkontrolujte, zda nemáte stejný problém, jako je předveden na 6. cvičení v sekci další příklady, konkrétně tracker_in_a_jar.

Jako sort doporučujeme Merge sort. Pro spojové seznamy je velmi vhodný, protože umožňuje seřadit celý list bez přesouvání prvků samotných a nepotřebuje mnoho extra paměti.

Vaše implementace by měla být tzv. "stabilní", ale přímo v testech to nekontrolujeme, pouze testujeme, zda se asymptotická složitost vaší implementace jeví rozumná.

Metody vnořených tříd (například list::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 list {
    class iterator {
        iterator& operator--();
    };
};

tedy patří tato definice

list::iterator& list::iterator::operator--() {
    ...
}

Specifikace list::iterator obsahuje i operátor přetypování, tj. operator const_iterator() const. V definici je potřeba plně specifikovat všechny typy, takže ve výsledku k němu patří tato definice

list::iterator::operator list::const_iterator() const {
   ...
}

Nezapomeňte, že iterátory listu jsou tzv. BiDirectional, a tudíž musí být možné iterátor přesunout zpátky k předchozímu prvku. Toto platí i pro iterátor vzniklý voláním funkce list::end.

Dávejte si pozor na přístup ke smazané paměti, protože jakmile nějaký kus paměti uvolníte, už k němu nesmíte přistoupit. To znamená, že například při mazání listu je potřeba nejdříve přesunout hlavu, a až pak smazat první prvek.

Malá ilustrace (node je celá struktura reprezentující uzel v listu a šipky jsou ukazatele):

Začneme se správně zkonstruovaným listem, který má 4 prvky.

          head
           |
           |
      _____V__     ________      ________      ________
     / node  |    / node  |     / node  |     / node  |
     |------ |    |------ |     |------ |     |------ |
     | value |    | value |     | value |     | value |
     | next  | -->| next  |  -->| next  |  -->| next  | --|
 |-- | prev  |<-- | prev  |<--  | prev  |<--  | prev  |   |
 |   |--------    |--------     |--------     |--------   |
 ----------------------> nullptr <-------------------------

Pokud smažeme uzel, na který ukazuje head, dostaneme se do tohoto stavu:

          head
           |
           |
      _____V__     ________      ________      ________
     / nod/  |    / node  |     / node  |     / node  |
     |\--/-- |    |------ |     |------ |     |------ |
     | \/lue |    | value |     | value |     | value |
     | /\xt  |    | next  |  -->| next  |  -->| next  | --|
     |/pre\  |<-- | prev  |<--  | prev  |<--  | prev  |   |
     |--------    |--------     |--------     |--------   |
                        nullptr <--------------------------

A z něho už nemůžeme pokračovat s mazáním, protože nemůžeme přistoupit k hodnotě head.next. Správně musíme nejdříve posunout hlavu:

                      head
                       |
                       |
      ________     ____V___      ________      ________
     / node  |    / node  |     / node  |     / node  |
     |------ |    |------ |     |------ |     |------ |
     | value |    | value |     | value |     | value |
     | next  | -->| next  |  -->| next  |  -->| next  | --|
 |-- | prev  |<-- | prev  |<--  | prev  |<--  | prev  |   |
 |   |--------    |--------     |--------     |--------   |
 ----------------------> nullptr <-------------------------

A pak teprve můžeme smazat první uzel.

                       head
                        |
                        |
      _______     ______V_      ________      ________
     / nod/ |    / node  |     / node  |     / node  |
     |\--/--|    |------ |     |------ |     |------ |
     | \/lue|    | value |     | value |     | value |
     | /\xt |    | next  |  -->| next  |  -->| next  | --|
     |/pre\ | |- | prev  |<--  | prev  |<--  | prev  |   |
     |------- |  |--------     |--------     |--------   |
              --------> nullptr <-------------------------

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