===== U3: List - dvojitě zřetězený spojový seznam =====

V tomto úkolu budete implementovat jednoduchou
variantu dvojitě zřetězeného spojového seznamu ([[https://en.wikipedia.org/wiki/Doubly_linked_list|Doubly linked list]])
ve stylu standardní knihovny.

To znamená, že dostanete hlavičkový soubor definující třídu ''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.

Implementovaný spojový seznam je reprezentován uzly, které mají připravené odkazy pro předchozí a následující prvek seznamu.

Tato varianta je paměťově poměrně náročná, samotná implementace předpokládá kromě základní práce se seznamem hlavně implementaci prvků jazyka C%%++%%.

/* mezery kolem názvu způsobí zarovnání na střed */
{{ :courses:b6b36pcc:ukoly:list.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.

<note important>Implementujeme **neseřazený** spojový seznam. Postupné řazení seznamu je součástí jednotlivých funkcí, které budete implementovat.</note>

===== Co si v tomto úkolu vyzkoušíte =====

  * Práce se spojovým seznamem - vkládání, procházení seznamu a také mazání prvků
  * Složitější práci se spojovým seznamem, řazení
  * Základy definice metod tříd
  * Tvorbu obousměrných iterátorů a jejich použití
  * Definici kopírujícího a přesunujícího konstruktoru a přiřazení
  * Definici nejrůznějších operátorů
  * Algoritmus [[https://en.wikipedia.org/wiki/Merge_sort |Mergesort]] k řazení prvků spojového seznamu

===== Zadání =====

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ářů((Speciálně formátované komentáře, ze kterých lze automaticky
generovat HTML dokumentaci)).

Archiv s testy, hlavičkou ''list.hpp'' a ''CMakeLists.txt'' najdete
{{:courses:b6b36pcc:ukoly:list.zip|zde}}.

===== Co odevzdat? =====

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.

===== Hodnocení =====

<HTML><style>
.content table td, .content table th {
    padding: 0.20em 0.75em;
}
</style></HTML>

^ **Sekce**                             ^  Body ^
| Basic functionality (**stage1**)      |  1.50  |
| Iterators (**stage2**)                |  1.50  |
| Copy, move, compare (**stage3**)      |  1.50  |
| **Stage 4**                                   ||
| Reverse                               |  0.50  |
| Split                                 |  1.00  |
| Merge                                 |  1.00  |
| Sort                                  |  1.00  |
| Remove                                |  0.50  |
| **Stage 5**                                   ||
| Split: algorithmic complexity         |  0.50  |
| Merge: algorithmic complexity         |  0.50  |
| Sort: algorithmic complexity          |  0.50  |
| **Celkem**                            | **10.00**  |

===== Rady =====

Doporučujeme při práci postupovat stejně jako v předešlých úkolech. Testy Vám umožní postupnou práci na úkolu až do jeho finální podoby. Pozorně čtěte poznámky se zadáním jednotlivých metod, abyste se při další práci vyhnuli nedorozuměním a předělávání úkolu.

==== Užitečné hlavičky ====

Implementaci relačních operací (stage2, stage3) si můžete zjednodušit chytrým využitím hlavičky
[[http://en.cppreference.com/w/cpp/header/algorithm|<algorithm>]]. Jinak využití dalších hlaviček nedoporučujeme. Řadící algoritmus (stage4, funkce ''sort'') doporučujeme napsat samostatně tak, aby Váš program na závěr prošel testy na časovou složitost. 

==== Implementační poznámky a rady ====

Úkol navazuje na probírané učivo, proto doporučujeme se při řešení jednotlivých částí implementace vrátit k přednáškám a cvičením.

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.


==== Definice metod vnořených tříd ====
Metody vnořených tříd (například ''list::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
<code cpp>
class list {
    class const_iterator {
        const_iterator& operator++();
    };
};
</code>
tedy patří tato definice
<code cpp>
const_iterator::const_iterator& list::const_iterator::operator--() {
    ...
}
</code>

==== Č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:

<code>
./tests "[.long]"
</code>
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).