class kalendar
{	udalost**udalosti;//samotny kalendar implementujeme haldou
	public:
	udalost*extract_min();//Vybere prvni udalost z kalendare (a vrati pointer na ni)
	void pridej(udalost*);//Prida udalost do kalendare
	void posun(int poradi,int na_kdy);//Posune udalost v kalendari
}

class jadro
{	kalendar*kal;
	public:
	void priprav();//pripravi simulaci
	int proved_dalsi();//zajisti obslouzeni pristi udalosti. Vrati udaj o tom, zda obslouzeni probehlo (navratova hodnota -1), nebo simulace skoncila (v tom pripade vrati cas konce simulace)
}

class udalost
{	int cas;//cas udalosti
	public:
	virtual void obsluz_se()=0;//metoda zajistici obslouzeni udalosti bude definovana v synech.
}

class mravenec:public udalost
{	int kamlezu;//cislo ciloveho vrcholu (vrcholy grafu jsou cislovane)
	virtual void obsluz_se();//zajisti oblehnuti vrcholu (a vypravi brabence do sousednich vrcholu - dosud neobsazenych).
}

Nevíme jak Vy, ale nám by se začaly ježit vlasy hrůzou, kdybychom měli implementovat kalendář jako haldu pouze s využitím pole pointerů na události. Potřebujeme vědět, jak velké si toto pole vytvořit (což umíme shora omezit počtem vrcholů). Dále potřebujeme vědět, kolik vrcholů v haldě aktuálně je. Abychom mohli lomcovat událostmi v kalendáři, tyto musejí mít údaj o svém pořadí (jinak budeme mít sice pěknou datovou strukturu, ve které ale budeme neustále vyhledávat - s lineární složitostí). Taktéž bude třeba, aby nám kalendář (událostí) někdo připravil. Takže tuto třídu doplníme takto:

class kalendar
{	udalost**udalosti;//samotny kalendar implementujeme haldou, pole pointeru na udalost.
	int velikost;//kalendare (odhadnuty poctem vrcholu grafu)
	int aktualne;//aktualni pocet udalosti.
	public:
	kalendar(int velikost);//konstruktor
	udalost*extract_min();//Vybere prvni udalost z kalendare (a vrati pointer na ni)
	void pridej(udalost*);//Prida udalost do kalendare
	void posun(int poradi,int na_kdy);//Posune udalost v kalendari
}

Pokračujme dál: Kdopak nám inicializuje kalendář v jádru? Aha, zapomenutý konstruktor! Naopak, k čemu nám bude dobrá funkce priprav? Asi k ničemu. Změňme ji tedy na konstruktor:

class jadro
{	kalendar*kal;
	public:
	jadro (int velikost);//kalendare, co si pripravime
	int proved_dalsi();//zajisti obslouzeni pristi udalosti. Vrati udaj o tom, zda obslouzeni probehlo (navratova hodnota -1), nebo simulace skoncila (v tom pripade vrati cas konce simulace)
}

Ve zbytku návrhu zatím trhliny nejsou patrné. Nicméně důležité je konstatování "nejsou patrné", netvrdíme, že tam nejsou. Objektový návrh však má jistá úskalí. Konkrétně máme pracovat s grafem, který ale náš objektový návrh nepokrývá. Hodí se nám tedy vytvořit si ještě třídu graf reprezentující:

class graf
{	int *vzdalenosti;//seznam vzdalenosti jednotlivych vrcholu od startu. -1 bude nekonecno; vyuzivame, ze Dijkstruv algoritmus musi mit vsechny vzdalenosti nezaporne.
	int *pozice;//vrcholu se vzdalenosti !=-1 v halde kalendare <- a zacinam byt zvedavy, jak se sem tenhle udaj dostane, rekl bych, ze koukame na dalsi slabe misto objektoveho navrhu, ale jisty si tim jeste nejsem.
	int pocet;//vrcholu
	int*mat_sous;//matice sousednosti. Opet -1 je nehrana, nezaporna hodnota je delka hrany.
	public:
	graf(int vrcholu);//konstruktor - vytvori prazdny graf na danem poctu vrcholu
	pridej_hranu(int odkud, int kam, int delka);//prida hranu
	int soused(int koho, int kolikaty);// Bude vracet cisla sousednich vrcholu - projde matici sousednosti a bude hledat tolikatou jednicku, kolik je v promenne "kolikaty". Nebude to sice vrchol efektivity, ale stavaji se horsi veci. Pokud jsme prosli uz vsechny sousedy, vrati -1. Pokud bychom misto matice sousednosti pouzili seznam sousedu, slozitost by vyznamne klesla. Ale kdo se ma se seznamem sousedu implementovat!?
}

To je krásný objektový návrh, že? Ale kdo se bude starat o práci se vstupem a výstupem? Neuděláme si na to obslužnou třídu? Hurá, do toho:

class obsluha
{	public:
	void nacti_graf();
	void simuluj();
}

Hezké. Ale jak se budeme dostávat k údajům o grafu? A jak se dostaneme k simulačnímu jádru? Zkusíme si udělat globální proměnné. Pak do nás ovšem bude zadrátováno, že nedovedeme pracovat s více než jedním grafem. Jinak bychom museli graf vhodným způsobem zpřístupnit funkci, která hledá sousedy (současného vrcholu). Budeme tedy doufat, že nikoho nenapadne nutit nás provádět současně více simulací, případně že postačí jeden graf. A nyní tedy příslušné globální proměnné:

graf*g;
jadro*j;

Oboje si necháme zinicializovat funkcí nacti_graf -- a už se nám objektový návrh začíná divně rozlézat. Až budou probrány návrhové principy SOLID, dozvíme se, že S je mnemonikum za Single responsibility (kdy každá entita má mít jeden úkol). A my už funkci nacti_graf nutíme nejen načíst graf, ale i zinicializovat celou simulaci. Anebo -- co kdyby jádro zinicializovala funkce simuluj? To by bylo metodičtější.

Stačí to takhle?

Nevíme. Proto hurá do implementace. V tuto chvíli je snad patrné, že kdybychom zadali každou funkci k naprogramování někomu jinému, mohli bychom si dát nohy na stůl a deset či dvacet minut počkat, než bude hotovo. Ti, kdo nebudou vyrábět konstruktory, si pro účely ladění vytvoří pomocné (staticky inicializované) struktury (v tom smyslu, že je inicializují pokaždé týmiž daty). Až pak jednotlivé zdrojáky slepíme dohromady, kód by měl fungovat (pokud jsme objektový návrh provedli kvalitně). Tak již dosti řečí, s chutí do toho, půl je hotovo a pak.... -- však to znáte.

---

Začněme tím, že se zeptáme překladače, co si o našem návrhu myslí. Prvním problémem je, že nám chybějí na konci definic tříd středníky. To je ovšem detail, který rychle dáme do pořádku. Druhým problémem je, že udalost dříve používáme nežli definujeme (což také snadno dáme do pořádku), třetí problém je zapomenutý návratový typ u funkce pridej_hranu. Ten má být pochopitelně void. Nyní tedy máme objektový návrh popsán zdrojákem, který je aspoň syntakticky správně. Nyní se nám buďto všechny funkce povedou, nebo ne. Pro kontrolu začneme funkcí main (ať linker začne padat kvůli neimplementovaným metodám a my máme lepší přehled, co jsme ještě nenapsali).

Při psaní funkce main nás napadne, že není příliš důvodů dělat si instanci třídy obsluha a její dvě funkce definujeme tedy jako statické. Samotná funkce main by mohla vypadat asi takto:

int main()
{       obsluha::nacti_graf();
        obsluha::simuluj();
        return 0;
}

---

Nyní uděláme myšlenkový skok a pustíme se do implementace grafu.

graf::graf(int vrcholu)
{       pocet=vrcholu;//nastavime pocet vrcholu,
        mat_sous=malloc(pocet*pocet*sizeof(int));//udelame si misto na matici sousednosti,
        int i;
        for(i=0;i < pocet*pocet;mat_sous[i++]=1);//nastavime vsude nehrany.
        vzdalenosti=malloc(pocet*sizeof(int));
        pozice=malloc(pocet*sizeof(int));
        for(i=0;i < pocet;i++)
                vzdalenosti[i]=pozice[i]=-1;//inicializujeme vse -1, coz znamena nekonecno nebo neni v halde.
}

void graf::pridej_hranu(int odkud, int kam, int delka)
{       mat_sous[odkud*pocet+kam]=mat_sous[kam*pocet+odkud]=delka;
}//pozor, nekontrolujeme, zda odkud a kam nevybocuji z rozsahu! Ani nekontrolujeme, zda delka>=0 - to bychom tu mohli zkontrolovat, ale nemame jak oznamit, ze tohle nastavit odmitame. Mohli bychom tedy nejvys operaci neprovest (coz by bylo bordelarske). Graf je neorientovany, proto musime nastavit hranu tam i zpatky. Pro orientovany graf bychom vyplnili jen jeden prvek matice sousednosti.

int soused(int koho,int kolikaty)
{       int i=0;
        while((kolikaty>0||mat_sous[koho*pocet+i]==-1)&&i<pocet)
        {       if(mat_sous[koho*pocet+i]!=-1)//vede hrana
                        kolikaty--;
                i++;
        }//preskakej "kolikaty" hran a skonci na dalsi (hrane) - nebo za koncem grafu
        if(i>=pocet)    return -1;//Tolikata hrana uz neni
        return i;//Jinak vrat index hrany.
}

class obsluha
{       public:
        static void nacti_graf();
        static void simuluj();
};

Zbyvá nám kalendar, jadro, mravenec a obsluha (která bude pomerně snadná). Pustíme se tedy do kalendare (ten bude netriviální).

kalendar::kalendar(int velikost)
{       int i;
        this.velikost=velikost;
        aktualne=0;
        udalosti=new udalost[velikost];
        for(i=0;i<velikost;udalost[i++]=NULL);
}

udalost*kalendar::extract_min()
{       udalost*vratit;
        if(aktualne==0) return NULL;//Dale vime, ze udalosti jsou.
        vratit=udalosti[0];
        udalosti[0]=udalosti[--aktualne];
        udalosti[aktualne]=NULL;
        zabublej(0);
        return vratit;
}

A hned vidíme, že kalendář bude třeba osadit funkcí zabublej. Tu uděláme privátní. Jako argument bude brát pozici, kde se má zabublat. Jelikož do haldy budeme i přidávat, bude třeba i metoda vybublej. Při jejich implementaci najíždíme na další slabé místo naší implementace: Událost má sice čas, ale ten je privátní. Dobrá, změníme jej na veřejný.

A narážíme na další slabé místo: Vrcholy mají údaj o své pozici. Ve chvíli, kdy haldu přetřásáme, musíme vrcholy informovat, že jimi šíbujeme! Přidáme tedy události abstraktní metodu pozice (kterou implementuje až mravenec tak, že updatuje údaj o pozici vrcholu, do kterého leze). V programu nám začíná tikat problém - budeme muset doimplementovat funkci pozice třídě mravenec (a než se k ní dostaneme, zapomeneme na to). Nicméně překladač nás upozorní (že takhle by to nešlo). Musíme též upravit funkci extract_min, kde jsme na notifikaci události (že změnila pozici) pochopitelně ani nepomysleli. To spraví přibližně tento řádek:
udalosti[0].pozice(0);
(přidaný před volání metody zabublej).

A jedeme na jádro, to jsme si navrhli jako velmi lehkotonážní. Konstruktor spraví zavolání konstruktoru kalendáře (aspoň doufejme, dokud to do sebe nezapadne, nikdy nevíme). Funkce proved_dalsi extrahuje minimum z kalendáře, podívá se, zda přišel NULL, v takovém případě vrátí délku simulace, v opačném případě (přijde-li událost) si poznamenáme její čas (abychom jej mohli případně později vrátit) a událost necháme obsloužit.

Hurá na mravence! A vidíme další drobný problém. Mravenci musí někdo nastavit údaj o tom, kam leze. Nejlepší tedy asi bude přidat mu konstruktor. A také jsme jaksi zapomneli, že funkce obsluz_se by měla být veřejná.

Náš enthusiasmus dělá divy, ale naše radost (nad tím, že moc práce už nezbývá) byla předčasná. Nacházíme další (a ne úplně příjemné) slabé místo objektového návrhu. Mravenec se potřebuje probourat ke kalendáři událostí, ke kterému se ale nedostane. Oproti objektovému návrhu z přednášky jsem totiž jedné každé události nepřidal pointer na kalendář. Jak z pasti? Všimneme si, že pointer na jádro je globální proměnná a tudy to asi budeme mít do kalendáře nejblíže. Osadíme tedy jádro wrappery pridej a posun (které akorát vyvolají příslušnou událost v kalendáři. A hned je tu další neplecha. Graf má údaje privátní (vzdálenosti, pozice a matici sousednosti) a my bychom s nimi rádi pracovali právě odsud. S tím ale rychle něco uděláme. Pro urychlení je nastavíme jako veřejné, metodické řešení by bylo udělat si funkce dej_... a nastav_...

A vidíme další problém: Údaj o pozici vrcholu (v haldě) má být v poli pozice objektu graf. Tam se ale nikdo s těmito údaji nezapisuje. To budeme muset opravit (při bublání).

Nyní zbývá na pohled už jen drobnost, ve skutečnosti však důležitá část programu. Povšimněme si, že třída obsluha bude rozhodovat o tom, jak reprezentujeme vstup. Pro začátek budeme načítat (ze standardního vstupu - který si ale samozřejmě přesměrujeme ze souboru) údaj o počtu vrcholů, o počtu hran a následovat bude 3*m čísel ve formátu odkud vede hrana, kam vede hrana a jakou má délku. Kdybychom chtěli vstup poněkud kultivovat, funkce nacti_graf() by jen načítala číslo složitějším způsobem. Rovnou předpokládáme, že všechna čísla budou nezáporná (protože indexy vrcholů mají být nezáporné a délky hran taktéž. Dále si všimněme, že funkce simuluj zase může snadno rozhodovat o grafické prezentaci výsledků. Vytvoříme-li si tedy pro ně vhodný interface, může se program chovat rozličnými způsoby (podle toho, co tyto funkce přesně provedou). To je další velká výhoda objektového návrhu. My funkci simuluj navrhneme tak, aby na konci simulace vypsala čas (konce) simulace, tedy vzdálenost do nejvzdálenějšího vrcholu (z vrcholu 0).
Zdrojak

---

Nyní je čas pustit se do ladění. Správně bychom měli vytvořit tzv. jednotkové testy. Ty mají otestovat korektnost jednotlivých funkcí. Při programování pak jen koukáme, kolik testů nám padá, a až jejich počet dosáhne nuly, lze se oprávněně domnívat, že program (jako celek) může zvolna začít fungovat. My budeme samozřejmě nedočkaví, zkusíme program spustit na testovací data, budeme doufat, že se nám podaří chyby odhalit pohledem, čímž (zbytečně) protopíme množství času - než si opravdu ty jednotkové testy napíšeme.

Nicméně dosti rozjímání, ještě je před námi třída obsluha. Hurá do ní.

Zdroják se jeví jako hotový, hurá do kompilace. Po nějakém snažení a pár úpravičkách - konkrétně po přesunu údaje o pozici události v haldě do rodiče a učísnutí interfacu (volat se bude virtuální metoda zmena_pozice, které řekneme, na kterou pozici se událost šoupe, rodičovská funkce jen zaznamená údaj o pozici do atributu pozice, v synovi (abychom nemuseli volat rodičovskou funkci) kromě toho ještě upravíme údaj v grafu (u příslušného vrcholu).

Nyní se zdroják jeví jako kompilovatelný, je čas na pokusy. Ale už je pozdě, takže testy provedu později. To mi jistě půjde skvěle, když mezi tím stihnu zapomenout, co jsem dělal. Takhle to ale vypadá, když se člověk neřídí radami, které dává svým studentům. :-D

Zdroják, který se již základním způsobem jeví jako funkční.

----------------------------------------------------------------------
FIXME!!! Zde okomentovat chyby zjistene pri ladeni a dalsi zmeny kodu -
pridani debugovacich informaci.
----------------------------------------------------------------------

Příklad grafu

Závěr: Byl náš původní objektový návrh dobrý, nebo špatný? Na otázku je poměrně těžké odpovědět. Při implementaci bylo třeba udělat některé změny (takže bezchybný rozhodně nebyl). Nicméně jsme kód dotlačili do funkčního stavu (tedy aspoň doufejme), takže použitelný byl. Sice je pravdou, že kdybychom Dijkstrův algoritmus implementovali bez objektů přímo (ve funkci main), kód by byl kratší. To je pravda. Z druhé strany je otázkou, zda by byl vůbec laditelný. A co by se stalo, kdybychom změnili formátu vstupu a výstupu. Nejspíše bychom bez objektového návrhu mohli začít opět znovu. A taktéž bychom měli významný problém, kdybychom místo Dijkstrova algoritmu měli implementovat něco úplně jiného. Takhle, pokud bychom měli implementovat výtahy, místo mravence zdědíme událost do tříd výtah, člověk a případně dalších (které se budou podílet na obsluze událostí), nastavíme nové atributy (které budeme potřebovat), místo grafu přidáme reprezentaci baráku (ve kterém jezdíme) a bude hotovo.