Úloha 4 - rozšíření množiny s binárním stromem

Evropský sociální fond

Praha & EU: Investujeme do vaší budoucnosti

Tato úloha vznikla za přispění fondu OPPA.

Upravte datovou strukturu BSTSET z předchozího úkolu. Nové vlastnosti:

BSTSET je nyní šablonou, která pracuje pro všechny datovy typy, které jdou porovnávat pomoci operátorů <, > a ==.
BSTSET umí odebírat prvky pomocí přetíženého operátoru ».
BSTSET má nyní iterátor, s jehož pomocí lze projít všechny prvky od nejmenšího k největšímu.
Operace vkládání a odebírání prvků z množiny BSTSET jsou kriticky časově závislé. Tyto dvě operace by měly být maximálně optimalizovány.
Oproti úkolu 3 vrací přetížený operátor () hodnotu 0 místo -1.

BSTSET by měla být šablonou (= template), se kterou lze pracovat stejně jako s šablonami kontejnerových tříd ze STL (tedy např. jako vector). Ze své podstaty umí pracovat pouze s prvky, které jdou vzájemně porovnávat. Pro správnou implementaci je plně dostačující, aby zpracovávané prvky šlo porovnávat pomocí operátorů < a >. Ukázka:

BSTSET<float> b;

Přetěžte operátor » pro BSTSET tak, aby pomocí něj šlo odebírat jednotlivé prvky. Ukázka:

b >> 3; // Snazi se vyjmout jeden prvek, ktery je roven datovemu typu int s hodnotou 3.
//  Pokud odebirany prvkek v mnozine neni, neprovede se nic.

Pozor! Odebírání je třeba provést bez memory leaků a efektivně tak, aby výsledná aplikace překonala časové kriterium.

Po vzoru šablon kontejnerových tříd ze STL bude mít i vaše šablona implementovaný iterátor. Bohatě postačí, když takový iterátor poskytne standardní chování:

for(BSTSET<float>::iterator i = b.begin(); b != b.end(); i++){
     cout << (*i) << endl;
}

Soustřeďte se na vkládání a odebírání prvků. Tyto dvě operace by měly být rychlé. Tento fakt bude kontrolován testerem, který bude měřit rychlost vašich řešení a porovnávat ji s řešením referenčním. Pokud nedosáhnete alespoň 120% času refenčního řešení, úloha bude testerem odmítnuta.

V sekci download jsou k dispozici testovací software (tester) a referenční řešení v binární podobě pro základní platformy. Tester přeloží předložený kód s parametry: -pedantic -pedantic-errors -Wall -Werror. Tyto volby způsobí, že překladač hlídá všechny detaily a pokud se při překladu objeví warning, je automaticky považován za chybu a překlad skončí. Pokud se podaří kód úspěšně přeložit, je pak porovnáván výstup aplikace s výstupem referenčního řešení. Jakákoliv odchylka, třeba i jedna mezera navíc, způsobí neplatnost testu! Během testování máte k dispozici všechny vstupy i informaci, kde došlo k nesrovnalostem. Pro domácí testování je ke stažení k dispozici i sada testovacích vstupů. Zde je třeba upozornit na rozdílnost platforem. V aplikace se používají floating point čísla, takže přesnost se může na různých platformách lišit. Výstupní hodnotu z testované a referenční aplikace se doporučuje porovnávat pouze v rámci jedné platformy!

Tester po skončení běhu napíše procentuální úspěšnost. Doporučuje se testovat na Solarisu, ale stejně tak by měl tester fungovat v jakémkoliv linuxu s nainstalovaným pythonem verze 2.4.6 a vyšším. K úspěšnému chodu je zapotřebí i nainstalovaný překladač g++. Po odevzdání bude váš kód testován stejným testerem, takže každý by měl předem vědět, jaký počet bodů dosáhl.

Pro spuštění testu stačí stáhnout a rozbalit adresář s testerem DU4-tester.tar. Poté v rozbaleném adresáři zavolejte příkaz make (na solarisu gmake) a řiďte se pokyny. V následujícím odstavci je popis testování, kdyby příkaz make (gmake) z nejakého důvodu nefungoval.

Tester vyžaduje dva parametry z příkazové řádky. Prvním je cesta k referenční aplikaci. Druhým parametrem je přímo testovaný zdrojový kód, v tomto případě to bude vždy DU4.cpp. Jako referenční aplikaci použijte tu správnou pro danou platformu. Pro solaris je to například refApp.solaris, pro 32 bitové linuxy refApp.linux_32 atd. Testování lze spustit příkazem:

python DU4-tester.py refApp.XXX DU4.cpp

Místo XXX si samozřejmě doplňte příslušnou platformu (Pro windows je přípona samozřejmě “exe”).

Pro testování přímo ve Windowsech je nutné nainstalovat cygwin se správnými součástmi. Po spuštění instalátoru vyberte nějaký mirror a nastavte dle instrukcí potřebné adresáře. (Pokud to lze, ponechte defaultní hodnoty.) Postupne byste se měli dostat na okno s výběrem instalačních součástí. Do vyhledávání zadejte postupně hesla g++, make, python. Pro instalaci vyberte balíčky tak, jak to je vídět na následujících obrázcích:

Po instalaci zkopírujte rozbalený DU2-tester do složky home/Vase_systemove_uzivatelske_jmeno, která se nachází v adresáři s nainstalovaným cygwinem. Poté spusťte cygwin a napište příkaz:

cd DU4-tester

Pak zkopírujte zdrojový kód domácího úkolu do složky testeru (do toho v adresáří home) a pojmenujte jej DU3.cpp. Pak stačí spustit test příkazem

make test_win

Pro záruku, že Váš kód bude při odevzdání přijat, otestujte jej také na solarisu, viz další sekce.

Vzdálené testování na serveru z OS Windows lze pomocí kombinace programů putty a WinSCP. Přes WinSCP lze na Solaris zkopírovat data a přes putty získáte vzdálený terminálový přístup. Jako adresu zadávejte např. sunray1.felk.cvut.cz, nebo sunray3.felk.cvut.cz. Uživatelské jméno a heslo byste měli znát.

Nejsnažší je použít příkazovou řádku a kombinaci příkazů ssh a scp. ssh slouží pro vzdálený přístup a scp pro kopírování. Přesuňte se do adresáře, kde máte uložen adresář DU1-tester. Pak zadejte příkaz

scp -r DU2-tester username@sunray1.felk.cvut.cz:

a po vyzvání buď potvrďte dotaz nebo rovnou zadejte heslo. Tímto byste měli mít celý adresář DU1-tester ve vašem domovském adresáři na Solarisu. Pro vzdálený přístup pak zavolejte příkaz

ssh username@sunray1.felk.cvut.cz

a opět zadejte heslo. Pro ukončení vzdáleného přístupu zadejte příkaz exit.

* Na solarisu používejte primárně příkkaz gmake. Příkaz gmake vypíše instrukce pro testování. Pokud tento postup selže, neprodleně to sdělte na adresu cernyvi@fel.cvut.cz. Můžete testovat i ručně viz předchozí sekce, ale předtím pro jistotu nastavte referenční řešení jako spustitelné (místo XXX si doplňte příslušnou platformu):

chmod +x refApp.XXX

Vývoj a testování domácího úkolu lze značně zjednodušit. Stačí si vytvořit zástupce nebo symbolický link na zdrojový kód, který může být umístěn například v projektovém adresáři vývojového prostředí. Tohoto zástupce nebo link umístěte do adresáře testeru a přejmenujte jej na DU2.cpp. Poté lze kód vyvíjet a testovat zároveň, aniž byste jej museli po každé změně kopírovat.

Editován je pouze soubor BSTSET.h, který také potom odevzdáváte!
Pro tento úkol jsou tři testy:
- Test 1 - vstupní hodnoty odpovídají ukázkovému vstupu jako na ilustračním obrázku.
- Test 2 - vstupní hodnoty jsou sadou náhodně generovaných čísel.
- Test 3 - test je defaultně vypnutý a slouží ke kontrole práce s pamětí. Funguje pouze na linuxu nebo MacOSX s nainstalovaným valgrindem (viz sekce Download) a kontroluje memory leaky. Spouští se příkazem:

python DU3-tester.py refApp.XXX DU3.cpp -valgrind

Pokud nemáte k dispozici linux můžete zkusit použít na kontrolu Vašeho kódu obdobný nástroj pro systém Windows - Dr. Memory (viz sekce Download), ale je to bez záruky.

Tester: du4-tester.zip

Domovská stránka valgrindu: http://valgrind.org/

Domovská stránka Dr. Memory: http://code.google.com/p/drmemory/