Nagy házi feladatok

A tárgyban két nagy házi feladatot kell elkészíteni. Ezeknek feltöltési határidejei az ütemtervben és a portálra bejelentkezve is láthatóak. Az első házinál a feladat kötött, egy összetettebb tároló osztály elkészítése. A második feladat a listából szabadon választott.

Referenciaszámlálást nem csak azért használunk, hogy tudjuk, hivatkozik-e még okos pointer egy objektumra, vagy fel lehet-e szabadítani. Arra is jó lehet, hogy a fölösleges másolásokat elkerüljük. Ha több objektum ugyanazzal az értékkel rendelkezik, akkor nincs értelme több másolatot is tartani a memóriában az értékről, hanem az objektumok osztozhatnak az érték egy közös reprezentációján. Így nem csak memóriát, hanem időt is spórolhatunk.

Erre is példa a szokásos állatorvosi lovunk, a sztring:

MyString a, b, c;
a = b = c = "helló világ";

1. Megosztás nélkül

2. Megosztással

3. Referenciaszámlálással

Ha nem osztjuk meg a karaktertömböket az egyes sztring objektumok között (1. ábra), a pazarlás nyilvánvaló. Ezért azt szeretnénk, ha a sztringek közös tömbbel rendelkezénének (2. ábra). Ez azonban így nem működhet, mert azt is kell tudnunk, hogy hány sztring használja ugyanazt a tömböt. Ezért jön a referenciaszámlálás a képbe (3. ábra). Fontos megfigyelni, hogy a referenciaszámlálók itt sem a sztring objektumokban, hanem a sztringértékeket tároló objektumokban vannak, mert az egyes tömböket hivatkozó objektumokat kell számolni. Ez egy erős csatolást jelent a karaktertömb és a referenciaszámláló között, ezért azokat érdemes egy objektumba tenni.

A legalapvetőbb sztringműveletek így néznek ki:

• Új sztring létrehozásakor új karaktertömb kell.
• Meglévő sztring lemásolásakor a szöveget nem kell lemásolni, csak megnövelni a referenciaszámlálóját.
• Sztring megszűnésekor a hivatkozott sztringérték referenciaszámlálóját csökkenteni kell. Ha nulla lett, akkor a sztringérték is törölhető.

Ez a kép addig ilyen szép, amíg nem engedjük meg a sztring osztály használóinak, hogy módosítsák a sztringeket. Ha ilyet is lehet, akkor nagyon kell vigyázni a közös másolatokkal:

MyString x = "hello";
MyString y = x;
y[0] = 'c';
std::cout << x;     /* hello */
std::cout << y;     /* cello */

Ebben a kódban az y sztringet módosítjuk, amitől az x sztringnek nem szabad megváltoznia. Konstans objektum indexelésénél nem lehet ilyen gond, a nem konstans sztring viszont változhat indexelés után, ezért indexelés hatására a sztringérték objektumot le kell másolni, ha több sztring dolgozik rajta. (Ha csak egy, akkor nincs ilyen gond.) Ezt úgy hívják, hogy „copy-on-write”, és az operációs rendszerekben gyakran alkalmazott módszer.

A feladat

A fentiek alapján implementáld a MyString osztályt, és írj hozzá rövid tesztprogramot, amelyben minden függvényét legalább egyszer használod!

• Beadandó a több modulra osztott forráskód: mystring.cpp, mystring.h és test.cpp. A feltöltött ZIP-nek ezt a három fájlt kell tartalmaznia. Ha más .cpp fájlok vannak benne, azokat is a projekt részének tekinti a rendszer.
• A sztring legyen másolható és értékadható. Valósítsd meg a mozgató konstruktort és értékadást is! Ne használj STL-t, std::string-et sem! Ha nullával lezárt karaktertömbökkel dolgozol, akkor viszont a C-s sztringkezelő függvényeket (pl. strcpy) mindenképp!
• Valósítsd meg a következő műveleteket: létrehozás alapértelmezett konstruktorral, létrehozás karaktertömbből, két sztring összefűzése (+ és +=), sztring és karakter összefűzése (+ és +=), kiírás és beolvasás (<< és >>), hossz lekérdezése, indexelés.
• Írj mindent ≥C++11-esen, amit csak lehet!

Értékelési szempontok:

• Ne „látszódjanak ki” implementációs részletek, kívülről ne lehessen érzékelni a referenciaszámlálást.
• Robusztus működés – ne lehessen memóriakezelési vagy egyéb hibába „kergetni” az osztályt a publikus interfészen keresztül.
• Memóriakezelés helyessége.
• OOP elvek betartása.
• A feladatkiírás pontos követése.
• Nyelvi eszközök rendeltetésszerű használata.
• A megoldás egyszerűsége. Ne erőltesd bele a megoldásodba olyan eszközök haszálatát, amikre nincsen szükség.

Vigyázat: memóriahiba (túlindexelés, szivárgás, stb.) esetén a program egyáltalán nem elfogadható. Vagyis ha a Valgrind hibát jelez a programra, akkor biztosan rossz. Ez határidő után is érvényes, félév végén is érvényes.

A feladathoz szorgalmi feladatrészek is tartoznak, amelyek a linkre kattintva érhetőek el. Figyelem: jobb ötlet előbb az alap részt megcsinálni, és csak utána foglalkozni a szorgalmikkal. Az alap beadásban még ne legyen benne a szorgalmi rész! Ha a lenti szorgalmi feladatokat is csinálod, azokra a megoldást külön add be!

A második feladat szabadon választott. A lényeg csak annyi, hogy a program C++11-ben íródjon, és ahol alkalmasak, használja a félévben bemutatott nyelvi elemeket és elveket. Itt szabadon használható az STL is, sőt minél több, annál jobb. Ez egyben elfogadási kritérium is. Nem modern C++ a kód, ha

• kézi erőforráskezelést végez (new, delete... okos pointerek!),
• újraimplementál szabványos tárolókat, STL algoritmusokat,
• funktor osztályokat tartalmaz lambda kifejezések helyett,
• stb.

Az alább felsorolt listában eltérő méretű, nehézségű feladatok is találhatóak. Olyat válassz, amelyikre lesz időd, és amelyik tetszik! Az értékelés itt is 0-5 pontos skálán történik, a program „modern C++-sága” alapján (≥C++11 elemek előnyben részesítése), illetve általános OOP és Clean Code irányelvek betartása alapján.

Ötlet: rendezőalgoritmusok

Van ez a fura hangú videó: https://www.youtube.com/watch?v=kPRA0W1kECg „sound of sorting algorithms”. Itt a kirajzolás a lényeg most, nem a hangja. Folyamatosan látszik a képernyőn a tömbök rendezés közbeni állapota.

Ezt meg lehetne valósítani a következő trükkel C++-ban. Van egy csomó teljesen generikus rendezőalgoritmusunk, amik mindig átvesznek valami tömböt (T*) és annak méretét. A tömb tartalmazhat bármit, int, double, std::string, aminek van < operátora. Ezek lehetnének olyan objektumok is, amelyek értékadáskor, összehasonlításkor automatikusan rajzolnak a képernyőre: így a rendezés automatikusan kirajzolódna, a rendező algoritmus tudta nélkül.

A tömb létrehozásakor persze meg kellene adni a tömbelemek helyét (koordináták a képernyőn) és értékét (oszlopok magassága). Az egyes elemek értékadásakor csak az oszlopmagasság változik, a koordináták nem, így lehetséges, hogy a tömbelemek helyükön maradnak. De ez az = operátor helyes átdefiniálásával (melyik adattag másolódik, melyik nem, és persze közben animáció!) megoldható. Közben nem csak animáció történhet, hanem a cserék (értékadások) és összehasonlítások számát is figyelhetik ezek az objektumok.

Ötlet: gonosz akasztófa

A program kívülről egy szokványos akasztófaprogramnak néz ki: a felhasználó betűket tippel, és megtudja, hogy a gép által gondolt szóban hol vannank olyan betűk.

Azonban most a gép nem kötelezi el magát egyetlen egy szó mellett sem. A felhasználó tippjei alapján mindig úgy szűkíti a szóba jöhető szavak halmazát, hogy a legkevesebb segítséget adjon a felhasználónak. Ez nem azt jelenti, hogy minden betűre azt mondja, hogy nincs – néha úgy segít kevesebbet, ha látszólag sokat segít. Pl. ha a szóba jöhető szavak listája: „aroma, adoma, apuka, strand, start, zizeg, zokni”, és a felhasználó az „a” betűt tippeli, akkor a programnak érdemes „a...a”-t mutatnia a felhasználónak. Akkor még mindig három szó marad, szemben azzal, mintha „..a..”-t vagy „.....”-t mondott volna neki.

Ennek a feladatnak a lényege az, hogy minél több tárolót és algoritmust újrahasznosítson a program az STL-ből.

Ötlet: BCD aritmetika, BigNum

Készíts osztályt, amely nem korlátozott ábrázolási tartományú egész aritmetikát valósít meg – vagyis képes tetszőlegesen nagy, mondjuk 1000 (de akár még több) számjegyű egész számokkal is számolni. A program legyen képes a négy alapművelet elvégzésére – amelyekkel alkotott kifejezéseket a billentyűzetről vagy fájlból vár. (Ezek lehetnek fordított lengyel jelöléssel adottak is.)

Ügyelj a helyes OOP tervezésre, főleg a SOLID elvekből az S-re: „single responsibility principle”! Írd meg külön a tárolót, és arra építve az aritmetikai műveleteket!

A regexes feladatokhoz

Vigyázz, az std::regex osztályt csak a legújabb fordítók és könyvtárak ismerik. A 4.8-as GCC, és az ahhoz járó könyvtár még nem tartalmazza.

Ötlet: regex golf

Írj egy játékot! https://regex.alf.nu/, std::regex.

Ötlet: regex megjelenítő

Hasonlóan kell működnie, mint a regexpal-nek: http://regexpal.com/. A kimenet lehet szöveges, grafikus, vagy akár HTML kód is.

Ötlet: regex puzzle megoldó

A bemenet egy regex keresztrejtvény, a kimenet a megoldása.

Ötlet: forráskód színező

Adott C/C++ forráskódot színezve jelenít meg, szöveges, grafikus kijelzőn, vagy generált HTML kódban. Érdemes tanulmányozni a GeSHi és a SyntaxHighlighter működését, hogy hogyan lehet ezt regexekkel megcsinálni.

Ötlet: függvényrajzoló

Az osztályhierarchiákról szóló előadás, és a kapcsolódó labort kiegészítő feladatgyűjtemény bemutat egy függvényrajzoló programot (amely apró szakaszokból rakja össze a függvényt). Az utolsó előadás pedig azt mutatja be, hogyan lehet egy négy alapműveletből álló kifejezést szintaktikailag elemezni. Rakd össze ezt a két programot egy olyan programmá, amelynek be lehet írni négy alaműveletes függvényeket, és ki tudja rajzolni azt választásod szerint egy SVG fájlba vagy a képernyőre! Közben használd az ebben a tárgyban tanultakat; pl. C++11 szintaktikát, okos pointereket a kifejezésfa tárolásához, kivételkezelést a kiértékelhetetlen függvényeknél.

Ennél pontosabb specifikáció itt sincs. Ha megtetszik a feladat, tetszőlegesen bővítheted a programot: pl. megoldhatod, hogy meg lehessen adni az ábrázolt tartományt, hogy automatikusan méretezze a képet, hogy több függvényt is lehessen egy rajzon ábrázolni, hogy legyen hatványozás operátor, hogy legyenek beépített sin(), cos(), sqrt() függvények, és így tovább.

Ötlet: szálbiztos tároló

Írj olyan várakozási sort, amelynek összes művelete szálbiztos! A tároló függvényeinek a feladata megoldani azt, hogy egyszerre több szálból is lehessen hívni őket, és ez semmilyen körülmények között ne okozhassa az adatszerkezet meghibásodását (szinkronizációs problémák miatt).

Vigyázat: ehhez előre kell tanulnod; a szálakról csak a félév legvégén lesz szó.

Bónusz: legyen a tároló iterálható! Amíg a tárolótól kért iterátorok (és azok másolatai) léteznek, addig ne engedjen elemet törölni (hogy többször végig lehessen iterálni az elemeken). Beszúrni természetesen lehet addig, de a többször iterálva mindig ugyanazok az elemek látszódjanak csak, akkor is, ha közben beszúrás történt! (Megoldható ez?)

Ötlet: folyamok (streams)

A láncolt lista egy eleme egy érték és egy pointer a következő elemre. A folyam egy eleme egy érték és egy függvény, amely megadja a következő elem pointerét. (Mindkét esetben null pointer jelképezi az üres tárolót, és így a következő elem pointere is akkor null, ha már nincs következő elem.) A kettő között az egyetlen különbség az, hogy míg a láncolt listánál a listaelemekben ténylegesen eltárolódik a következő elem címe, a folyamokban nem, mert azokban csak egy függvényhívás után kapjuk meg az elemet.

Emiatt a folyamoknál nem kell a memóriában tartani az összes elemet, mint a listáknál. A listáknál a pointer a következő elem memóriacímét tárolja, a folyamoknál a tárolt függvény csak egy ígéretként jelenik meg: ha kell, akkor előállítható a következő elem is. Végtelen láncolt listát nem lehet csinálni (mert nincs végtelen memória), végtelen folyamot viszont igen (pl. az összes pozitív egész számot tartalmazó folyam), mert mindig csak akkor jön létre a következő elem, amikor szükség van rá. Ha nem hívjuk meg a függvényt, akkor soha.

Ez a gondolkodásmód sok feladatnál nagyon elegáns megoldáshoz vezet. Ha szükségünk van az ezredik prímszámra, akkor 1) fogjuk az összes pozitív, egész szám „listáját”, 2) kiszűrjük belőle a prímeket (alapfeladat: „lista” szűrése predikátum szerint), 3) kivesszük az így kapott „listából” az ezredik elemet (alapfeladat: „lista” n-edik eleme). Ehhez nem kell tudnunk, hogy az ezredik prímszám mennyire nagy, az első lépésben előállított „lista” lehet végtelen nagy! Ha igazi listákkal dolgoznánk, az nem lehetne végtelen.

Ugyanígy Eratoszthenész szitáját is lehet csinálni. Fogni kell az összes 1-nél nagyobb szám „listáját” (2, 3, ...), és szitázni azt. A szitázás művelete azt jelenti, hogy az első szám megmarad, de a „lista” többi részéből az első szám többszöröseit törölni kell, és ezt a maradék részt szitázni is kell. Tehát 2, és a maradékból a párosok szűrve, és az szitázva. A maradék így: a 3 marad, a többiből a 3 többszöröseit szűrni, és azt is szitázni stb. Így előáll a prímszámok végtelen hosszú „listája”.

Írj egy ilyen programot! Használj benne lambda függvényeket, okos pointereket! Mielőtt megírod a folyam osztályt, próbáld ki ezeket az algoritmusokat egy saját készítésű, egyszerű, láncolt listára is!

Ötlet: CodeHunt

Írd meg egy C++-os CodeHunt (https://www.codehunt.com/) játék motorját!

Ezt meg lehet oldani dinamikus linkeléssel. Linuxban a dlopen(), dlclose(), dlsym() stb. függvényekkel megoldható, hogy a programhoz futás közben hozzákapcsoljunk egy .so fájlt, és természetesen az is, hogy futás közben eldobjuk azt. (Így működnek a plugin-ek is.) A működés valahogy így nézne ki:

• A felhasználó megadja a forráskódot, amire tippel.
• Ezt a program kimenti egy fájlba (temp.c).
• Lefordítja (temp.so).
• Betölti a függvényt (dlopen(), dlsym()).
• Lefuttatja a megfelelő tesztadatokkal.
• Bezárja a .so-t (dlclose()).
• Kiértékeli a visszatérési értékét, és pontozza az eredményt.

Természetesen ez nem biztonságos (a játékos által írt függvény elszállása a program elszállásához is vezet, ahogyan régebben a hibás Flash plugin is magával rántotta a böngészőt), de ez most nem lényeges. Ahogyan a szép grafika és a sok feladvány sem. Kifejezetten a program motorja a lényeg.

Ötlet: gráf tárolása

Írj osztályt gráf tárolására, legalább kétféleképpen! Csúcsokat és éleket kell tárolni, azaz legalább két tároló kell. Milyen tárolók? Hogy írod le közöttük a kapcsolatot?

Válaszd el a gráf algoritmusait (szélességi bejárás stb.) a gráf konkrét felhasználásától! Legyenek algoritmusokkal paraméterezhető bejáró, törlő stb. függvények!

Ötlet: Funkcionális programozás

A legtöbb funkcionális(an is használható) nyelvben, ahol listákkal dolgozunk, az algoritmusok teljes listákat vesznek át paraméterként, és listákat adnak vissza. Pl. pozitív számok kiválogatása egy listából:

/* php */
function positive($l) {
    return array_filter($l, function($a) {
        return $a > 0;
    });
}

/* scheme */
(define (positive l)
    (filter
        (lambda (a)
                (> a 0))
        l))

Ezzel szemben a C++ algoritmusai iterátorpárokat várnak, és új listák létrehozása helyett meglévőeket módosítanak, és általában az előállított eredménynek előzetesen a hívó kell helyet biztosítson.

Írj egy sablonokból álló függvénykönyvtárat, amely a funkcionális stílust támogatja: legyenek mindenkhol listák a paraméterek, és a visszatérési értékek! Megvalósított algoritmusokat innen szemezgethetsz: C++ STL algorithm.

Ötlet: Egyszerű Scheme interpreter

Írj egyszerű Scheme (Lisp) interpretert! Megvalósítandó részhalmaz:

(+ 5 7)         ; 12

(define a 5)
(+ a 7)         ; 12

(define (sqr x) (* x x))
(sqr 5)         ; 25

(define x 7)
x               ; 7
(sqr 5)         ; 25 (nem 49!)

(define (fact n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))
(fact 6)        ; 720

Ötlet: Logo interpreter

Egyszerűbb teknőcgrafika interpreter.

Ötlet: forráskód vizualizáló

Mint a Sourcecode Visualizer. Valamely nyelv egy kis(!) részhalmazához, forráskódrészlethez (függvénytörzs). Vigyázat, szintaktikai elemzőt kell írni!

Ötlet: UML Rajzoló

Hasonló, mint a PlantText. Néhány fajta UML diagramhoz, pl. Graphviz kimenettel.

Ötlet: Indexelő tömbök

Az indexelő tömbök alapötlete, hogy egy adatokat tároló tömb mellé létrehozunk egy ugyanakkora, egészeket tartalmazó tömböt is. Rendezés esetén az eredeti tömböt, abban az elemek sorrendjét változatlanul hagyjuk: csak az indexelő tömbben cserélgetjük ki az integereket. Ez sokkal gyorsabb lehet, mint az eredeti tömbön dolgozni. Tovább a módszer lehetőséget ad arra is, hogy egyszerre egynél többféle rendezettséget is fenntartsunk.

A feladatod egy olyan tömb osztályt csinálni, amely tetszőleges adatokat tárol, és mellé tetszőleges számú indexelő tömböt is fel tud venni! A tömbhöz lehessen hozzáadni elemeket: push_back; ilyenkor természetesen az indexelő tömbök is nyúljanak. Lehessen a tömb végéről törölni: pop_back. Definiálhatsz más műveleteket is, pl. adott (közbenső) elem törlése; ügyelj arra, hogy a törlés hatására az indexelő tömböknek nem csak zsugorodni kell, hanem a bennük lévő indexek változhatnak is.

Az indexelési sorrendeket jelöljék egész számok; legyen 0 a jele a fizikai sorrendnek, 1-től fölfelé pedig a felhasználó által megadottaknak. Lehessen kérni új indexelési sorrendet! Lehessen tetszőlegesen váltani ezek között a sorrendek között, és a tömb indexelő operátora mindig a kiválasztott sorrend szerinti nézetet mutassa! Egy új indexelési sorrend megadásakor az objektum várjon egy rendezőfüggvényt (mint pl. az std::less), amelyet jegyezzen is meg, hogy később a rendezettséget fenn tudja tartani.

A hozzáadás és a törlés, vagyis a push_back() és pop_back() függvények a fizikai sorrendet kell figyelembe vegyék. Így biztosítható az, hogy a pop_back() a legutóbb hozzáadott elemet törli. Másképp a „back”-nek nem lenne értelme.

Ötlet: intruzív okos pointer

Az előadáson bemutatott, referenciaszámlálós okos pointernek van egy hátránya, mégpedig az, hogy megduplázza a dinamikusan foglalt objektumok számát. Minden kezelt objektum mellé dinamikusan foglalni kell egy egész számot is. Mivel azonban minden kezelt objektumhoz pontosan egy referenciaszámláló kell tartozzon, a számlálót tehetjük máshova is: egyszerűen bele az objektumba. Ezt a megoldást úgy nevezik, hogy intruzív (intrusive) okos pointer.

A „minden referenciaszámlált objektum rendelkezik egy referenciaszámlálóval” gondolatot a legegyszerűbb úgy megvalósítani, ha létrehozunk egy RefCounted alaposztályt, és a kezelt objektumok számára előírjuk azt, hogy ebből az alaposztályból származzanak le. Az okos pointereknek így nem kell külön int-et foglalni, hanem azt használhatják, ami benne van az objektumban.

A feladatod ezt az okos pointert megvalósítani. Tedd az alábbiakat:

• Valósítsd meg a RefCounted alaposztályt, amelyben a referenciaszámláló van. Figyelj arra, hogy az ebből öröklődő osztályokból példányosított objektumok másolása nem szabad magával vonja a referenciaszámláló másolását! Egy példán keresztül: ha egy dinamikusan foglalt X-re két okos pointer mutat, akkor az X másolatára ettől még nem fog két okos pointer mutatni, sőt lehet nem is dinamikusan van foglalva.
• Valósítsd meg a RefCounted osztályból leszármazó objektumokat kezelő SharedPtr okos pointert!
• Mi a helyzet, ha egy leszármazott osztálynak ugyanolyan nevű adattagja van, mint ahogyan a referenciaszámláló adattagot elnevezted? Oldd meg ezt a problémát!
• A referenciaszámlálót csak az okos pointereknek kell látniuk, senki másnak. Se a külső függvényeknek, osztályoknak, de még a leszármazottaknak se.
• Ha B osztálynak őse A, akkor a B*→A* konverzió automatikus. Ezért egy SharedPtr<A> = SharedPtr<B> értékadásnak is működnie kell.
• Hasonló a helyzet a const-okkal.
• Oldd meg azt is, hogy konstans objektumok memóriakezelése is megvalósulhasson! Hasonlóan ehhez:

  std::shared_ptr<const std::string> sp(new const std::string("hello"));
  std::cout << *sp;

• Írj a make_shared() mintájára make_refcounted() függvényt is!
• Készíts teszteket (unit test), amelyben kimerítően ellenőrzöd az okos pointer működését!

Ötlet: nemintruzív okos pointer objektumméretet figyelembe vevő heurisztikával

Az std::make_shared() függvény nagy bravúrja, hogy a létrehozott objektumot, és a referenciaszámláláshoz szükséges unsigned int változót közös memóriaterületen képes létrehozni: egyszerre lefoglalva őket, egyetlen memóriafoglalással. Így ez a művelet gyorsabb, minta külön foglalnánk le az objektumot, és külön a referenciaszámlálót. Vagyis az alábbi két kódrészlet a használat szempontjából nagyjából egyformán jó, de a második gyorsabb:

Obj *p = new Obj;
std::shared_ptr<Obj> s1(p);

std::shared_ptr<Obj> s2 = std::make_shared<Obj>();

Ez csak akkor tud gond lenni, ha az objektum túl nagy. Mert ebben az esetben nagy lehet a pazarlás: előfordulhat, hogy az objektum már nem létezik (nem mutat már rá okos pointer, és ezért a destruktora meghívódott), de a memóriaterületet még mindig meg kell tartani, mert a referenciaszámláló(k)ra még szükség van. Ilyenkor célravezetőbb lehet a nagy objektumot külön memóriaterületen létrehozni.

Készíts olyan okos pointert, amelyik mindkét működést megvalósítja! A hozzá tartozó make_shared függvény vegye figyelembe azt, mekkora objektumot kell létrehozni! Ha nagyot, azt foglalja külön memóriaterülen, ha kicsit, akkor egyben a referenciaszámlálóval! (A külön referenciaszámlálóra akkor is szükség lehet, amikor nem a make_shared foglalja az objektumot.)

(Ez egy viszonylag nehéz feladat. Nézd hozzá át az std::weak pointer osztályról szóló előadásrészletet, és az std::optional osztályhoz kapcsolódó feladatot is!)

Ötlet: HTML DOM okos pointerekkel

A weboldalakon használt HTML kódban, az egymásba ágyazott, formázásokat megadó tag-ek egy n-ágú fát alkotnak.

<body>
<p>Szöveg szöveg szöveg szöveg.</p>
<ul id="mylist">
    <li>Felsorolás 1</li>
    <li>Felsorolás 2</li>
</ul>
<p>Szöveg szöveg.</p>
</body>

kód reprezentáció

fa reprezentáció

Szöveg szöveg szöveg szöveg.

• Felsorolás 1
• Felsorolás 2

Szöveg szöveg.

eredmény

A HTML fa egyes csomópontjait JavaScript kódból elérhetjük és manipulálhatjuk. Egy adott csomópontot legegyszerűbb ID alapján megkeresni, pl. így:

document.getElementById('mylist').style = 'background-color: #f00;';

Ebben a feladatban egy C++ objektum reprezentációt kell készítened az adatokhoz.

• Hozz létre egy Node ősosztályt, és származtasd ebből a különféle típusú csomópontokat: Body, Paragraph, UnorderedList és ListItem!
• Alakítsd a Node osztályt egy heterogén kollekcióvá, ahol a gyerekek Node-ok vektoraként tárolódnak! A tartalmazott szöveggel nem feltétlenül kell foglalkoznod, elég ha a felépítése csomópontok típusa szerint megfelelő.
• Építsd fel a fent látható fát! A heterogén kollekció miatt dinamikus memóriakezelést kell alkalmaznod. Ki végzi a felszabadítást? Használj okos pointert a fa gyökeréhez, és a gyerekekhez is!
• Írd ki a fát, hogy lásd a szerkezetét: root->print()! Minden Node esetén így működik a kiírás: 1) nyitó tag, pl. <ul>, 2) gyerekek kiírása, 3) bezáró tag. Az eredmény ilyesmi kell legyen:

  <body><p></p><ul><li><li></ul><p></p></body>

• Ellenőrizd a ~Node() destruktorokkal, hogy mindegyik csomópont felszabadul-e a program futtatásának végén!

A JavaScript document.getElementById() metódusával lehet egy csomópontot megkeresni név (id) szerint a fában. Ez a keresés nem túl hatékony, ha be kell járni hozzá a teljes a fát. Ezért érdemes egy std::map-et vagy egy std::unordered_map-et használni, amely az ID-vel rendelkező csomópontokat tartalmazza. Ezért kell a std::shared_ptr, mivel némely csomópontok több tárolóban is benne vannak, a fában és a map-ben is.

• Hozd létre a map-ed, és tedd bele a névvel rendelkező csomópontokat!
• Keress rá név szerint egy csomópontra, és írd ki annak tartalmát! Például: nodes_by_id["mylist"]->print();

JavaScriptben egy adott csomópont törléséhez az ő szülő csomópontját kell megkérnünk a művelet elvégzéséhez, mivel az tartalmazza őt gyerekként. Ez ott így néz ki kódban:

var mylist = document.getElementById('mylist');
mylist.parentNode.removeChild(mylist);

Írj ehhez hasonló kódot C++-ban! Ehhez egy adott csomópontnak ismernie kell a szülőjét egy parentNode pointeren keresztül, amelyet a fa felépítésekor kell kezelni. Milyen okos pointer kell ehhez?

Valósíts meg okos pointerek segítségével további függvényeket, amelyekkel a fa kívülről bejárható! Pl. previousSibling(), nextSibling(), amelyek a szomszédos csomópontokat adnak vissza (vagy null pointert, ha a lista végén lévő elemre hívják őket).

Ötlet: Reguláris kifejezésből állapotgép

A reguláris kifejezések állapotgéppel feldolgozhatóak: https://www.youtube.com/watch?v=GwsU2LPs85U. Írj C++ programot, amelyik ilyen átalakítást végez! Tehát egy megadott reguláris kifejezésből felépít egy állapotgépet, amelyikkel aztán meg tudja mondani egy sztringről, hogy illeszkedik-e rá.

A felépített állapotgépet természetesen a programban reprezentálnod kell valahogy – tervezz ehhez szükséges osztályokat, tárolókat!

Ötlet: Játékok, modellezési feladatok

A Prog1 tárgy házi feladat ötleteket tartalmazó oldala rengeteg további ötletet tartalmaz. Ezek közül azok választhatók, amelyek nem egyszerűsödnek le túlzottan az STL használhatósága miatt.