\chapter{Algoritmy pracující s reprezentací}

Nyní se podíváme na algoritmy, které čtou nebo vytvářejí reprezentaci
adresářového stromu.

Protože v mnoha případech budeme pracovat se soubory jako s proudem dat,
zavedeme si jednoduché značení -- pokud chceme načíst $n$ bajtů z proudu $f$ do
proměnné $x$, výslednou operaci označíme $x \fget{n} f$. V případě, že chceme
načíst \VarInt, použijeme analogicky značení $x \fget{\VarInt} f$. V případě
zápisu do souboru $f$ prohodíme směr šipky.

\section{Čtení a zápis záznamů}

Nejprve si ukážeme, jakým způsobem budeme číst a zapisovat jednotlivé
sloupečky. Postup vyplývá přímočaře ze specifikace formátu souboru.

\begin{procedure}{NačtiSloupeček}
\algin{Vstupní soubor $f$, sloupeček $c = (id, k)$}
\: Pokud $k = \VarInt$: \cmt{Jedná se o číslo?}
\:: $d \fget{\VarInt} f$
\:: $k = \norm d$
\: Jinak:
\:: Pokud $k = {?}$: \cmt{Data variabilní délky?}
\::: $k \fget{\VarInt} f$
\:: $d \fget{k} f$ \cmt{Načteme data podle délky $k$}
\algout{Data sloupečku $id \to (k, d)$}
\end{procedure}

Zápis sloupečku je analogický k jeho čtení. Přečtení a zápis jednoho sloupečku
přečte $\O(k)$ bajtů a kromě toho provede konstantní množství práce.

Přečtení jednoho celého záznamu znovu vyplývá přímo z formátu uložené
reprezentace. Zde vidíme obecný algoritmus, který vrací množinu dat $D$, kde
klíč je $id$ a hodnota je dvojice $(k, d)$, kde $d$ jsou samotná data a $k$ je
jejich délka.

\begin{procedure}{NačtiZáznam}
\algin{Vstupní soubor $f$, seznamy sloupečků $C$ a nepovinných sloupečků $O$}
\: $n \fget{\VarInt} f$ \cmt{Načteme délku celého záznamu}
\: Pro každou položku $c = (id, k) \in C$:
\:: Do $D$ přidej $\textsc{NačtiSloupeček}(f, c)$
\:: $n \= n - k$
\: $i \= 0$
\: Pokud $O \neq \emptyset$:
\:: $q \fget{\lceil |O|/8 \rceil} f$ \cmt{Načteme bitové pole nepovinných sloupečků}
%\: Jinak pokud $n > 0$:
%\:: Do $D$ přidej $\textsc{NačtiSloupeček}(f, (?, n))$ \cmt{Načteme zbylá data jako neznámá}
\: Pro každou položku $c = (id, k) \in O$:
\:: Pokud $i$-tý nejnižší bit $q$ je 1:
\::: Do $D$ přidej $\textsc{NačtiSloupeček}(f, c)$
\::: $n \= n - k$
\:: $i \= i+1$
\algout{Množina dat $D$}
\end{procedure}

Celkový čas, který zabereme touto operací, je $\O(n + I(|C|+|O|))$. Člen $n$
dostáváme, protože čteme $\O(n)$ bajtů z $f$. Dále závisí na použití datové
struktury na reprezentaci množiny dat, $I(x)$ je čas strávený na vložení dat do
množiny a $F(x)$ je její vyhledání.

%Uložení neznámých dat se nám bude hodit v případě, kdy máme v záznamu suffix
%povinných sloupečků, případně všechny nepovinné sloupečky, jenž pro aktuální
%zpracovávání nepotřebujeme.

Zápis záznamu je podobný jeho čtení, avšak je složitější. Protože délku záznamu
$n$ ukládáme jako \VarInt, závisí $\norm n$ na délce zbytku záznamu. Proto je
potřeba si $n$ spočítat předem. Protože při výpočtu $n$ zkoumáme nepovinné
sloupečky, můžeme při tom i rovnou spočítat $q$.

\begin{procedure}{SpočtiDélkuAMasku}
\algin{Seznam sloupečků $C$, seznam nepovinných sloupečků $O$, množina dat $D$}
\: $n \= \lceil |O|/8 \rceil, q \= 0^{\lceil |O|/8 \rceil}$ \cmt{Připočteme délku bitmasky $q$}
\: Pro každé $c = (id, k_0) \in C$:
\:: pro $id \to (k, \dots) \in D$: \cmt{Najdeme data sloupečku $c$}
\::: $n \= n + k$
\::: Pokud $k_0 = ?$:
\:::: $n \= n + \norm{k}$ \cmt{Pro data variabilní délky započteme i $\norm{k}$}
\: $i \= 0$
\: Pro každé $c = (id, k_0) \in O$:
\:: Pokud $id \to (k, \dots) \in D$: \cmt{Existují data nepovinného sloupečku?}
\::: Nastav $i$-tý nejmenší bit $q$ na 1
\::: $n \= n + k$
\::: Pokud $k_0 = ?$: $n \= n + \norm{k}$
\:: $i \= i + 1$
%\: Pokud $(?, k, \dots) \in D$: \cmt{Máme i neznámá data?}
%\:: $n \= n + k$ \cmt{Přičteme i délku neznámých dat}
\algout{Délka záznamu $n$, bitové pole $q$}
\end{procedure}

Spočítat $n$ a $q$ tedy umíme provést v čase $\O(n + F(|C|+|O|)$. $F$ značí
složitost vyhledání dat v $D$. Protože při zapisování nepotřebujeme vkládat do
$D$ sloupečky, jen je pro jejich zápis vyhledáváme, platí stejná složitost i
pro zápis.

Obecně se tedy pro reprezentaci $D$ dá využít hešovací tabulka. V takovém
případě bude $I$ i $F$ průměrně konstantní složitost. Pokud navíc bude počet
sloupečků nulové délky nejvýše konstantně mnoho, dostaneme se pro čtení a zápis
jednoho záznamu na optimální složitost $\O(n)$.

\subsection*{Implementační detaily}

Náš program je mnohem konkrétnější -- pouze některé sloupečky mohou být
nepovinné a předem očekáváme množinu všech možných sloupečků $\cal C$.

Celá množina dat bude jedna velká statická struktura, obsahující ukazatele na
všechna možná data. Výjimkou budou čísla uložena přímo. Data variabilní délky
budou kromě ukazatele obsahovat informaci o jejich délce.

Pro zaznamenaní, které nepovinné sloupečky daný záznam obsahuje, se
použije bitové pole s jednotlivými bity přímo určenými daným datům.

Každý specifikovaný sloupeček (povinný i nepovinný) si kromě svého typu a $id$
bude pamatovat offset na datovou a délkovou položku ve struktuře, přičemž pro
čísla a data fixní délky bude délková položka prázdná. Navíc nepovinné
sloupečky si budou pamatovat číslo bitu odpovídající bitové masce ve struktuře.

Při čtení a zápisu záznamu dostane procedura ukazatel na strukturu. Pro přístup
či zápis se poté spočítá místo v paměti, určené pro čtení nebo zápis, pomocí
ukazatele na strukturu plus offset.

Navíc v případě, když ke čtení záznamu dostaneme $c \notin \cal C$, v jeho
specifikaci si budeme pamatovat jeho typ a informaci, že je neznámý. Poté se
při jeho čtení přeskočí zápis do reprezentace.

S touto implementací je časová složitost $F$ i $I$ konstantní worst case.
Naopak paměťová složitost je $\O(n + |\cal C|)$, i když v reprezentaci
použijeme jen malou podmnožinu $\cal C$. Proto se tato reprezentace hodí pouze
pro malé $|\cal C|$.

\section{Čtení reprezentace}

Naše reprezentace je velmi optimalizovaná na jednoduché čtení. V ní je celý
adresářový strom zaznamenaný v preorder uspořádání. Navíc každá důležitá
informace je vždy dostupná předem.

Díky tomuto stačí na datech akorát provést jeden lineární sken. Paměťové nároky
jsou proto kromě pamatování potřebné části stromu (v mnoha případech stačí si
pamatovat aktuální větev) velmi nízké -- potřebujeme si ještě pamatovat akorát
seznam povinných a nepovinných sloupečků, případně nějaká metadata navíc.

Nyní se pojďme podívat na typické přečtení a následné zpracování reprezentace.
Označíme si $N$ jako délku celého souboru.

Na začátku zpracujeme hlavičku, jejíž délka je $H$.  Nejprve algoritmus ze
vstupního souboru $f$ přečte magické číslo. Tím se přesvědčí, že opravdu
pracuje se správným formátem reprezentace adresářového stromu.

Poté jednoduchou smyčkou začne číst a zpracovávat metadata podle jejich
konkrétní sémantiky:

\begin{shortalgo}
\: $id \fget{4} f$
\: Pokud $id = 0$: konec
\: $n \fget{\VarInt} f$
\: $m \fget{n} f$
\: Zpracuj metadata $(id, m)$
\: Vrať se na začátek
\end{shortalgo}

Po seznamu metadat ihned následuje specifikace povinných i nepovinných
sloupečků $C$ a $O$. Jejich čtení je totožné, lze proto pro jejich načtení
použít stejný cyklus:

\begin{shortalgo}
\: $I \fget{4} f$
\: Pokud $I = 0$: konec
\: $type \= I[30\dots31]$ \cmt{Uložíme horní dva bity jako typ dat}
\: $id \= I[0\dots28]$
\: Pokud $type = 00$: \cmt{Fixní délka}
\:: $n \fget{\VarInt} f$
\:: Do seznamu sloupečků přidej $(id, n)$
\: Pokud $type = 01$:
\:: Do seznamu sloupečků přidej $(id, \VarInt)$ \cmt{Číslo ve \VarInt}
\: Pokud $type = 10$:
\:: Do seznamu sloupečků přidej $(id, ?)$ \cmt{Variabilní délka}
\: Vrať se na začátek
\end{shortalgo}

Celé přečtení hlavičky tedy umíme provést jedním lineárním skenem $f$ a
strávime nad tím optimální čas $\O(H)$. V tomto okamžiku máme zpracovaná
všechna metadata i $C, O$. Můžeme tedy začít zpracovávat samotný adresářový
strom.

Ukážeme si obecný postup, jak zpracovat libovolný podstrom prohledáváním do
hloubky, jehož kořenem je aktuálně přečtený záznam. Budeme již předpokládat, že
máme proceduru \textsc{ZpracujZáznam}, jenž načte jeden záznam a převede jej do
reprezentace, která se nám v danou chvíli nejvíce hodí.

\begin{algo}{ZpracujPodstrom}
\algin{Aktuálně přečtený kořen podstromu $x$, další konkrétnější data}
\algout{Velikost podstromu $V$, další konkrétnější data}
\: $V \= |T(x)|$
\: Proveď konkrétnější zpracování před rekurzí
\: Dokud $V > 1$:
\:: $y \= \textsc{ZpracujZáznam}$
\:: $p(y) \= x$ \cmt{Pokud potřebujeme, zapamatujeme si otce}
\:: $V_y, \dots \= \textsc{ZpracujPodstrom}(y, \dots)$
\:: Proveď konkrétnější zpracování mezi rekurzí
\:: $V \= V - V_y$
\: Proveď konkrétnější zpracování po rekurzi
\: Vrať $|T(x)|, \dots$
\end{algo}

Zpracování celého stromu pak započneme zpracováním jeho kořene, tedy prvního
záznamu, a zavoláním \textsc{ZpracujPodstrom} na něm. Složitost tohoto
algoritmu poté závisí na konkrétním zpracovávání. Stále však získáváme velmi
hezkou vlastnost, že soubor s reprezentací čteme jen jednou jako proud dat.

\subsection*{Implementační detaily čtení hlavičky}

Už při čtení sloupečků jsme nepracovali obecně, nýbrž jsme očekávali množinu
známých sloupečků $\cal C$. Pro naše účely navíc máme všechny identifikátory
sekvenční. Proto $\cal C$ reprezentujeme jako pole, jehož prvky jsou
reprezentované stejným způsobem, avšak délka bude nedefinovaná.

Pokud některé $id$ neznamenají nic, nebo se přestaly používat, v poli máme
záznam, že toto $id$ je neplatné.

Při čtení povinných či nepovinných sloupečků poté přistoupíme k danému indexu v
poli. Pokud je platná, danou specifikaci zkopírujeme a nastavíme jí délku podle
informace v souboru. Jinak vytvoříme generickou specifikaci se správným typem a
délkou a označíme ji jako neznámou.

\section{Sestavení reprezentace}

Nyní již umíme libovolnou reprezentaci stromu přečíst a zpracovat, přičemž to
celé umíme provést proudově. Na druhou stranu, sestavení této reprezentace
takto jednoduché není.

Výslednou reprezentaci potřebujeme mít uspořádanou pre-order. Avšak v případě,
že existuje sloupeček, jehož obsah je závislý na podstromu, potřebujeme nejprve
zpracovat jeho podstrom. Z toho vyplývají dvě možnosti, jak postupovat:

\begin{enumerate}
\item Budeme si pamatovat celý podstrom. Jakmile je celý zpracovaný, projdeme
jej v pre-order uspořádání a v něm jej uložíme.
\item Podstrom uložíme v pořadí zpracovaných vrcholů a následně jej externě
přeuspořádáme do správného uspořádání.
\end{enumerate}

První možnost bohužel v nepřipadá v úvahu. Disky mohou stále být řádově mnohem
větší, než RAM, tudíž celý adresářový strom může být potenciálně tak rozsáhlý,
že by se nám jeho reprezentace nemusela vejít do RAM.

Druhá možnost zase znamená, že se nám nepodaří celou reprezentaci uložit jedním
průchodem. To navíc také implikuje, že si budeme navíc muset pamatovat
pre-order pořadí každého vrcholu.

Skutečně, pro naše konkrétní požadavky máme alespoň dvě závislosti kořene na
jeho podstromu -- hešování adresářů a informace o velikosti podstromu.

Při sestavování proto rozdělíme celý algoritmus na dva hlavní kroky. První krok
zpracuje všechny nezávislé sloupečky a vypočítá pre-order uspořádání. Druhý
krok poté spočítá heše adresářů a případně další závislé hodnoty.

\subsection{Hešování obyčejných souborů}

Tento krok je jediný, který pracuje s reálným adresářovým stromem.