 \lstset
    {
    language=C++,
    frame=,
    framesep=8pt,
    backgroundcolor=\color{VeryLightGray},
    basicstyle=\small,
    keywordstyle=\rmfamily\color{DarkGray}\bfseries,
    identifierstyle=\rmfamily \color{RealGray},
    commentstyle=\rmfamily\color{LightGray}\itshape,
    stringstyle=\rmfamily\color{RealGray},
    showstringspaces=false,
    escapechar=\#,
    morekeywords={uint},
%    numbers=left,                   % where to put the line-numbers
%    numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
%    stepnumber=2,                   % the step between two line-numbers. If it's 1 each line will be numbered
%    numbersep=5pt                  % how fare the line-numbers are from the code
    }

\chapter{Implementace}
\label{kap_implementace}%
V této kapitole budou popsány detaily samotné implementace MBD. Nahlédneme
přímo do zdrojových souborů. V této souvislosti je nutné připomenout, že zde
uvedené výpisy zdrojového kódu mohou být v zájmu lepší čitelnosti zkráceny či
jinak upraveny. Jejich kompletní verzi je možné nalézt na CD přiloženém k této
publikaci.\\
\indent Fyzickým výsledkem celé práce je kromě zdrojových kódů program, který v
sobě mísí všechny zde popsané prvky. Jeho popis bude rovněž uveden v této
kapitole.


\section{Použité nástroje a filozofie programu}%
Vzhledem ke kritickým nárokům na výkon MBD, byl zvolen jazyk C++. K problému
bylo přistoupeno hybridním přístupem, kdy část programu je psaná pomocí
objektového postupu a část pomocí postupu strukturovaného - jde tedy o jakýsi mix C++ a
C. Tento přístup si vynutil samotný problém. Zmiňovaný \uv{mix} nejlépe
vyhovuje požadavkům MBD. Jak kód psaný čistě v C, tak i striktně v C++, by byl
poměrně neohrabaný.\\
\indent Aplikace nepoužívá žádné externí knihovny, které by nebyly součástí C++,
resp. C. Za zmínku stojí jistě mohutné použití šablon ze \emph{Standard
Template Library}, jde především o \emph{vector}, \emph{list} a
\emph{hash\_map}\footnote{ \emph{hash\_map} Není zatím součástí standardu, a tak
se podle upravené specifikace jazyka C++ firmou Microsoft nachází v prostoru
jmen \emph{stdext}}.

\subsection{Podporované platformy}%
Celý projekt byl stvořen pomocí vývojového prostředí\emph{Visual Studio 2005} a
je určen pouze pro 32bitovou platformu \emph{Windows}. Vzhledem k tomu, že
aplikace je psaná ve standardním C++ bez použití zásadních systémových
závislostí, neměl by jeho přenos na jiné platformy činit žádný
problém\footnote{Nicméně žádné pokusy s přenesením programu nebyly provedeny.}.
Stejný závěr lze učinit i v případě jeho přenesení na 64bitové systémy. V
programu je sice jedna závislost na 32bitové systémy, na kterou bude v dalším
textu upozorněno, ale její odstranění je snadné.


\section{Struktura programu}%
V programu se používají čtyři základní třídy: \emph{Node}, \emph{MBD},
\emph{MBDLIB} a \emph{PLA}. Jejich význam je stručně shrnutý v tabulce
\ref{imp_souhrn}, s tím že jejich detailní význam bude vyložen v pozdějších
oddílech.

\btab%
    \caption[Základní třídy programu]{ \textbf{Základní třídy programu.}}
    \label{imp_souhrn} \vskip 20pt%
    \begin{tabular}{cc}%
    \toprule
    Třída & \ttc{Popis}\\
    \midrule
    Node & reprezentace jednotlivých uzlů MBD\\
    MBD & reprezentace celého MBD\\
    MBDLIB & podpůrné a doplňující finkce k MBD\\
    PLA & reprezentace logické funkce zadané pomocí PLA souboru\\
    \bottomrule
    \end{tabular}
\etab

\subsection{Node}%
Třída Node slouží na uložení uzlů MBD. Jde o poměrně jednoduchou spíše pasivní
strukturu s velmi omezenou funkčností. Její definice je vidět na obrázku
\ref{imp_node}. Kde:

\paragraph{var\_id} Proměnná, do níž je uložen \emph{identifikátor} vstupní proměnné, které
uzel náleží. Identifikátory se přiřazují proměnným podle jejich pořadí v PLA
souboru. Identifikátory $0$, $1$ a $2$ jsou vyhrazeny terminálním uzlům s
hodnotami $0$, $1$ a $X$.

\paragraph{node\_id} Unikátní identifikátor, který je každému uzlu přiřazen při jeho vzniku.
V současné implementaci je tato proměnná nepotřebná, protože z ryze praktických
důvodů se jako unikátní identifikátor používá 32bitový ukazatel na objekt uzlu.
Při přechodu na 64bitové systémy je nutné brát tento fakt na zřetel.

\paragraph{hi a lo} Odkazy na \emph{high} a \emph{low} podgrafy - reprezentují dvě
výstupní hrany uzlu.

\paragraph{parents} \emph{Vector} identifikátorů všech uzlů (rodičů), které na daný uzel
odkazují. MBD lze implementovat i bez této proměnné, ovšem její přítomnost velice
urychluje řadu složitějších operací\footnote{Např. prohazování proměnných.}.

\paragraph{Node} Dva konstruktory třídy. Jeden vytvoří uzel pouze s určeným identifikátorem
vstupní proměnné a druhý umožňuje zadat i odkazy na podgrafy.

\paragraph{is\_parent} Test, zda uzel se zadaným unikátním identifikátorem uzlu, je rodičem
uzlu.

\paragraph{rem\_parent} Funkce odstraní uzel se zadaným unikátním identifikátorem uzlu ze
seznamu rodičů \emph{parents}.

\newpage
\bfig
\begin{lstlisting}
class Node
{
public:
    uint var_id, node_id;
    Node* hi, *lo;
    Node_Parents parents;

    Node(uint vid);
    Node(uint vid, Node* hi, Node* lo)

    bool is_parent(uint n_id);
    bool rem_parent(uint n_id);
    bool is_term();
};
\end{lstlisting}
\caption[Definice třídy Node]{ \textbf{Definice třídy Node.}} \label{imp_node}
\efig
\paragraph{is\_term} Test, zda uzel je terminální. Kontrola se provádí jednoduchým testem hodnoty
identifikátoru, která musí být menší než 3, aby šlo o terminální uzel.

\subsection{MBD}%
Zásadní třída celého programu sloužící na uložení MBD. Kromě samotného popisu
dat disponuje i řadou metod, které nad těmito daty pracují. Její definice je na
obrázku \ref{imp_mbd}.

\paragraph{root} Ukazatel na kořen MBD. Je pouze jeden - MBD nepodporuje vícehodnotové
funkce.
\paragraph{term0} Ukazatel na terminální uzel s hodnotou $0$. V každé chvíli existuje
pouze jeden, který není nutné později redukovat.
\paragraph{term1} Ukazatel na terminální uzel s hodnotou $1$.
\paragraph{termX} Ukazatel na terminální uzel s hodnotou $X$.
\paragraph{input\_num} Počet vstupních proměnných logické funkce.
\paragraph{order2var} \emph{Vector} sloužící na převod pořadí$\rightarrow$proměnná. Na
poli s indexem $i$ se nalézá identifikátor proměnné, jež je $i$tá v pořadí.
\paragraph{var2order}\emph{Vector} sloužící na převod proměnná$\rightarrow$pořadí. Na
poli s indexem $i$ se nalézá pořadí proměnné, jejíž identifikátor je $i$. Jde o
inverzní vektor k předchozímu.
\paragraph{map}\emph{Hash\_map}, která slouží na ukládání uzlů podle určitého klíče.

\newpage
\bfig
\begin{lstlisting}
class MBD
{
public:
    Node* root;
    Node* term0,*term1,*termX;
    uint input_num;
    MBD_VAR_ORDERING order2var, var2order;
    NodeMap map;

    uint load_pla_row(PLA_Row& row);

    Node* get_node(uint vid, Node* lo, Node* hi);

    uint swap_vars(uint v1, uint v2);

    void save_to_dot(char* filename);

    void get_pla(PLA& pla);
    void get_pla(PLA& pla, Node* n);

    uint cleanup(Node* d);
    uint cleanup();

    MBD(uint inputs);
    MBD(uint inputs, MBD_VAR_ORDERING);

    ~MBD();
};

\end{lstlisting}
\caption[Definice třídy MBD]{ \textbf{Definice třídy MBD.} \uv{Ořezaná} verze
pouze s nejdůležitějšími metodami.} \label{imp_mbd} \efig


\paragraph{load\_pla\_row} Metoda načte do MBD jeden řádek z PLA souboru
- tedy jeden term. Slouží při načítání celé logické funkce.

\paragraph{get\_node} Kriticky důležitá metoda celé třídy.
Prakticky sama zajišťuje ukládání uzlů do \emph{hash\_mapy} a redukci MBD při
jeho načítání. Její deklarace je na obrázku \ref{imp_get_node}.

\paragraph{swap\_vars} Metoda sloužící na prohazování proměnných v MBD.
Vstupními parametry jsou pořadí jednotlivých proměnných, které musí spolu
sousedit.

\paragraph{save\_to\_dot} Metoda uloží MBD ve formátu dot. Více v kapitole \ref{kap_vizualizace}.

\paragraph{get\_pla} Metoda uloží MBD do struktury PLA. Pomocí parametru $n$ je
možné zadat kořen libovolného podgrafu, pro který se má struktura PLA uložit.
Při vytváření PLA je automaticky prováděna minimalizace.

\newpage
\bfig
\begin{lstlisting}
Node* MBD::get_node(uint vid, Node* lo, Node* hi)
{
    Node *t;
    NodeMap::const_iterator it;

    if (lo->node_id == hi->node_id) // redukce: 3. pravidlo
        return lo;

    if (map.end() != it = map.find(NodeKey(lo->node_id, hi->node_id, vid)))
    {
        // redukce: 2. pravidlo
        t = it->second.node;
    }
    else
    {
        // uzel je unikatni -> ulozeni do hash_mapy
        t = new Node(vid, hi, lo);

        lo->parents.push_back(t->node_id);
        hi->parents.push_back(t->node_id);

        map.insert( NodeMapPair(
                        NodeKey(lo->node_id, hi->node_id, vid), NodeVal(t))
                    );
    }

 return t;
}
\end{lstlisting}
\caption[Definice metody MBD::get\_node]{ \textbf{Definice metody
MBD::get\_node.}%
Metoda provádí redukci MBD při vytvoření každého uzlu. Uzly mapy se ukládají s
klíčem, který je tvořen ze tří hodnot: id proměnné; id uzlu, kam směřuje
hrana \emph{high}; id uzlu, kam směřuje hrana \emph{low}. Je-li požadavek na
vytvoření uzlu se stejným klíčem, nový uzel se nevytváří a vrací se starý.% (pravidlo 2.).
}
\label{imp_get_node}%
\efig%

\paragraph{cleanup} Metoda vyčistí MBD - tj. vymaže všechny uzly.
\paragraph{MBD} Dva konstruktory třídy. Jeden přijímá pouze počet vstupů, pomocí druhého
lze zadat i~pořadí vstupních proměnných.
\paragraph{$\sim$MBD} Destruktor třídy. Volá jen metodu \emph{cleanup()}.

\newpage
\bfig
\begin{lstlisting}
class MBDLIB
{
    uint static_ordering_method;
    uint x_subst_method;

public:
    // nacitani
    uint load_from_pla(char* filename, MBD** mbd, PLA** pla);
    uint load_from_pla(PLA* pla, MBD** mbd);

    void apply(MBD** dest, MBD* s1, MBD* s2, MBD_OP_Type op);
    Node* apply_OR(MBD* dest, Node* d1, Node* d2);
    uint reduce(MBD** mbd_dst, MBD* mbd_src);

    // razeni
    MBD_VAR_ORDERING ord_stat(PLA* pla);
    MBD_VAR_ORDERING ord_force(PLA* pla, MBD_VAR_ORDERING* io=NULL);
    MBD_VAR_ORDERING ord_random(PLA* pla);

    MBD_VAR_ORDERING order_vars_static(PLA* pla,
                                       MBD_VAR_ORDERING* io=NULL);
    uint order_vars_dynamic(MBD* io);

    uint get_span(PLA* pla, MBD_VAR_ORDERING& o);

    // minimalizace
    uint minimize_X(MBD** mbd);
};
\end{lstlisting}
\caption[Definice třídy MBDLIB]{ \textbf{Definice třídy MBDLIB.} }
\label{imp_mbdlib} \efig

\subsection{MBDLIB}%
Třída funguje jako knihovna metod na provádění složitějších operací s MBD. Jsou
zde funkce jako APPLY, metody na určení pořadí vstupních proměnných a
minimalizaci. Pochopitelně, že je sporné, zda ta či ona funkce má být ve třídě
MBD nebo v MBDLIB. Současné rozdělení metod mezi oběma třídami vyplynulo z
potřeb, které se během práce objevily, a ze zkušeností, které byly v průběhu
času získány. Definice třídy je na obrázku \ref{imp_mbdlib}. Popis proměnných a
metod následuje.


\paragraph{static\_ordering\_method} Proměnná, jež uchovává typ statické metody,
která se použije před načtením logické funkce. Jsou zde čtyři možnosti:

\begin{itemize}
\item \emph{NONE}: Použije se přirozené pořadí z PLA souboru.
\item \emph{Random}: Pořadí se náhodně vygeneruje.
\item \emph{FORCE}: Pořadí určí technika FORCE.
\item \emph{STAT}: Pořadí najde algoritmus STAT.
\end{itemize}

\paragraph{x\_subst\_method} Uchovává typ přesměrování hran vedoucích do terminálního
uzlu s hodnotou $X$.
\paragraph{load\_from\_pla} Funkce načte MBD z PLA souboru/struktury. Je možné načítat buď přímo ze
souboru nebo z PLA objektu. Pokud se nějaká funkce načítá vícekrát, pak je možné
ji jednou načíst ze souboru do PLA a pro další načítání použít v paměti
uloženou strukturu PLA.
\paragraph{apply} Implementace operace APPLY. Ze dvou vstupních MBD vytvoří pomocí zadané
logické funkce jeden výstupní. V současné době je podporován pouze logický
součet.
\paragraph{apply\_OR} Implementace operace APPLY s logickým součtem. Jde o základní funkci
potřebnou při načítání MBD. Přesnější informace o načítání MBD budou popsány v
dalších oddílech této kapitoly.
\paragraph{reduce} Metoda provádí redukci načteného MBD podle pravidel
popsaných v kapitole \ref{kap_bdd}.

\paragraph{ord\_stat} Metoda určí pořadí vstupních proměnných technikou STAT.
\paragraph{ord\_force} Metoda určí pořadí vstupních proměnných technikou FORCE.
\paragraph{ord\_random} Metoda vygeneruje náhodné pořadí vstupních proměnných.

\paragraph{order\_vars\_static} Podle toho, jaký typ řazení je nastaven v
proměnné \emph{static\_ordering\_method}, provede tato metoda řazení proměnných
- tj. zavolá jednu z předchozích funkcí.

\paragraph{order\_vars\_dynamic} Implementace dynamické metody řazení
\emph{swap\_down}. Podrobnosti jsou v kapitole \ref{kap_razeni}.

\paragraph{get\_span} Metoda získá ze zadaného PLA a pořadí proměnných veličinu
\emph{span}. Používá se ve funkci \emph{ord\_force()} - více v kapitole
\ref{kap_razeni}.

\paragraph{minimize\_X} Metoda provádí přesměrování hran vedoucích do
terminálního uzlu s hodnotou $X$. Způsob přesměrování určuje hodnota proměnné
\emph{x\_subst\_method}.


\subsection{PLA}%
Pro úplnost je uvedena i třída PLA, která reprezentuje logickou strukturu PLA
souboru. Je mezičlánkem při načítání a ukládání logických funkcí do a z MBD.
Definice třídy je na obrázku~\ref{imp_pla}.

\paragraph{input\_num} Proměnná uchovává počet vstupních proměnných.
\paragraph{output\_num} Proměnná uchovává počet výstupních hodnot.
\paragraph{PLA} Dva konstruktory třídy. Do jednoho je možné zadat počet
vstupních proměnných a~výstupních hodnot.
\paragraph{load} Metodou slouží k načítání PLA ze souboru.
\paragraph{save} Metodou slouží k ukládání PLA do souboru.
\paragraph{get\_histogram} Metoda získá z MBD četnost výskytu literálů proměnných.
Využívá se ve statické metodě řazení vstupních proměnných STAT.
\paragraph{get\_stats} Metoda získá z PLA jednoduchou statistiku: celkový počet
literálů a celkový počet termů.

\bfig
\begin{lstlisting}
class PLA
{
public:
    uint input_num, output_num;
    vector<PLA_Row> rows;

    PLA();
    PLA(uint i_n, uint o_n);

    uint load(char* filename);
    uint save(char* filename);
    uint get_histogram(PLA_Input_Var_Histogram& hst);
    uint get_stats(PLA_Stats&);

    void or_pla(PLA& pla);
    void and_var(uint var, uint val);
};
\end{lstlisting}%
\caption[Definice třídy PLA]{ \textbf{Definice třídy PLA.} }%
\label{imp_pla}%
\efig

%
%\section{Doplňující informace}%
%Účelem tohoto oddílu je prozradit více o některých detailech implementace a
%seznámit s problémem, který vzniká při reprezentaci funkce pomocí MBD.

%\subsection{Načítání MBD}
%Zásadním a jedním vůbec z největších problému, který je nutné při impelementaci
%MBD vyřešit, je načítání MBD. V každé literatuře je vznik MBD (BDD) popsán
%pomocí Shannonovy expanze. Bohužel, takový přístup je v praxi nepoužitelný.
%Jednak je jeho časová složitost velká\footnote{$O(2^n)$}, ale také jeho
%implementace by byla velmi složitá.\\
%\indent Pro účely této práce byl zvolen přístup založený na operaci APPLY.
%Každý term se nejprve samostatně převede do vlastního MBD. Ty se pak cyklicky
%spojují dohromady pomocí operace APPLY s logickým součtem. Pochopitelně, že
%časová složitost je totožná s časovou složitostí Shannonovy expanze, ovšem
%implementačně jde o velmi jednoduchý úkol.

%\subsection{Problém překrývajících se termů}
%Při načítání funkcí s DCsetem do jednoho diagramu, se může objevit problém,
%který by se dal nazvat jako \uv{překrývající se termy}.\\
%
%\noindent Máme-li funkci $f(x_0,x_1,x_2)$, která se skládá z $f_{on}=x_0$ a
%$f_{dc}=x_1x_2$, pak jeden z těchto termů zastíní při načtení funkce do MBD ten
%druhý. Při načítání MBD se totiž obě funkce chovají jako dvě plně určené
%logické funkce ($f=f_{on}+f_{dc}$), jediný rozdíl je v tom, že poslední hrana
%termu z $f_{dc}$ vede do uzlu s hodnotou $X$ místo $1$. Tento rozdíl však MBD
%nebere v úvahu. V současné verzi je možné z překrývajících se termů vybrat
%pouze jeden, s tím, že druhý úplně zanikne. Bohužel, samotná struktura MBD jiné
%řešení nenabízí.\\
%\indent Jedinou možností je analyzovat logickou funkci na vstupu, nalézt
%průniky mezi termy z $f_{on}$ a $f_{dc}$ a odstranit je - tj. rozdělit některé
%termy, aby průniky neobsahovaly. Pokud chceme upřednostnit termy z $f_{dc}$,
%pak průniky vyjmeme z $f_{on}$. Celou operaci demonstruje s využitím map
%obrázek \ref{imp_x_prekryv}.
%
%
%\bfig
%    \includegraphics[height=4cm]{img/mbd-prek.png}
%    \hskip 1.5cm
%    \includegraphics[height=4cm]{img/mbd-prek-reseni.png}
%    \caption[Řešení překrývání termů z $f_{on}$ a $f_{dc}$]{ \textbf{Řešení překrývání
%    termů z $f_{on}$ a $f_{dc}$}. Obrázek \emph{a)} ukazuje mapu funkce $f(x_0,x_1,x_2)$,
%    kde $f_{on}=x_0$ a $f_{dc}=x_1x_2$ (zvýrazněno šedivě). Tímto způsobem \emph{vidí}
%    MBD logickou funkci. Průnik $f_{on}$ a $f_{dc}$ je v $f_{p}=x_0x_1x_2$.
%    Obrázek \emph{b)} zobrazuje vyloučení průniku z $f_{on}$, který se rozpadne na
%    $f_{on}=x_0\bar{x_1}+x_0x_1\bar{x_2}$. Termům z $f_{dc}$ byla dána přednost,
%    tak se zde nic neměnilo.
%    }
%    \label{imp_x_prekryv}
%\efig

%\section{Aplikace}
%BLA BLA BLA BLA


%\section{Závěr}
%BLA BLA BLA BLA
