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

{{:pjc:3_loga_velikost_100.jpg|}}

**Evropský sociální fond**

**Praha & EU: Investujeme do vaší budoucnosti**

Tato úloha vznikla za přispění fondu [[http://www.prahafondy.eu/cz/oppa.html|OPPA]]. 

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

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.

==== Šablona ====

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;

==== Odebírání prvků ====

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.

==== Iterátor ====

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;
  }

==== Časová závislost ====

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.

===== Testování =====

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").

==== Testování na OS Windows ====

Pro testování přímo ve Windowsech je nutné nainstalovat [[http://cygwin.com/setup.exe|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:

{{:pjc:g_1.jpg|}}

{{:pjc:make1.jpg|}}

{{:pjc:python1.jpg|}}

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ý přístup z OS Windows ====


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.

==== Vzdálený přístup z OS Linux nebo Mac OS ====

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.

==== Doporučení pro testování ====

* 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.

===== Novinky v testování =====

  * **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.


===== Download =====


Tester: {{:pjc:04:du4-tester.zip|}}

Domovská stránka valgrindu: [[http://valgrind.org/|]]

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