Programozó Páternoszter

Miután az 5 előadás verem{1-17}.cpp példáit reprodukáltuk, megrágtuk, elfogyasztottuk, majd kimásztunk az asztal alól, ahová unalmunkban közben be-beestünk, kicsit komolyabb fába vágtuk a fejszét: a Tömör a gyönyörben kifejlesztett C struktúrás LZW (bináris) fa építőnket több lépésben átírjuk C++-ba. Jó (K&R) szokás szerint továbbfejlesztések sorát készítjük majd el, e mostanival kezdjük a C++ sorozatot. Mikor vagy kész? Ha az 5. alőadás alapján készített progid lefordul és ugyanazt nyomja ki, mint a Labormérés otthon, avagy hogyan dolgozok fel egy pédát posztbeli teszteléskor a C változat.

Kezdjük! Az első változatot tehát úgy készítjük, hogy nézzük a C kódot és melegében írjuk át C++-ra (ennek megfelelően egyelőre nem használunk például referenciákat) egyszerűen csak egy osztállyal helyettesítjük a fa csomópontjait leíró struktúrát.

Az osztálynév nem a legszerencsésebb, lehetne LZWBinFaCsomopont is, de most a gyökér csomópont kitüntetett abban az értelemben, hogy számunkra ő lesz majd maga a fa, innen a név.

class LZWBinFa
{

    char betu;
    LZWBinFa *balNulla;
    LZWBinFa *jobbEgy;

public:
    LZWBinFa (char b = '/'):betu (b), balNulla (NULL), jobbEgy (NULL) {};
    ~LZWBinFa () {};

 A struktúrával teljesen analóg módon itt is megvan a két önhivatkozó tag, itt hogy '0'-val vagy '1'-el címkézve vettük fel az új (a gyermek) csomópontot, azt egy char-ban (betu) tároljuk (ennek kapcsán megnézheted a 3. hullám kapcsolódó 1 trófeását). Konstruktorunkat tipikusan majd ezzel a '0' vagy '1' címkével fogjuk hívni, de ha ezt nem adjuk meg, akkor a gyökér "jele" a '/' betű lesz feltételezve. Továbbá az újonan készített csomópontok gyerekekre mutató mutatóját úgy állítjuk be, hogy kezdetben nincsenek gyerekei a csomópontnak /balNulla (NULL), jobbEgy (NULL)/ Az alábbi kódcsiperben tehát a "gyoker" az az LZWBinFa csomópont objektum, amiben a "betu" értéke a '/' jel, azt is észrevehetjük, hogy lokális változóként vettük fel, nem kell majd szabadítani. Kezdetben erre a gyökérre állítjuk a "fa" mutatót, s majd ez mutatja mindig, hogy az algoritmus üzeme során hol vagyunk éppen a fában.

int
main ()
{
    char b;
    LZWBinFa gyoker, *fa = &gyoker;

    while (std::cin >> b)
    {
        if (b == '0')
        {
            // van '0'-s gyermeke az aktuális csomópontnak?
            if (!fa->nullasGyermek ()) // ha nincs, csinálunk
            {
                LZWBinFa *uj = new LZWBinFa ('0');
                fa->ujNullasGyermek (uj);
                fa = &gyoker;
            }
            else // ha van, arra lépünk
            {
                fa = fa->nullasGyermek ();
            }
        }

 A működés teljesen ugyanaz, csak kicsit egyszerűsödött a kód, s jobban is olvasható, mint a C változat. Egyszerűen meghagytuk a C program logikáját és a struktúra használata helyett beütöttük az újdonsült osztályunk használatát. A konstruktor és a new operátor használata is levett pár sort a meglévő kódból a vállunkról. Fordítsuk, futtassuk:

[norbi@sgu ~]$ g++  z.cpp -o z
[norbi@sgu ~]$ ./z <tesztminta.txt
------------1(3)
---------1(2)
------1(1)
---------0(2)
------------0(3)
---------------0(4)
---/(0)
---------1(2)
------0(1)
---------0(2)OK, ugyanaz.
Tekerj a továbbra a teljes forrásért és persze a folytatásért.

*: "Imádni fogják a légiót, egy emberként, tiszta szívből", www.imdb.com/title/tt0126388/

// z.cpp
//
// LZW fa építő C++ átizata a C valtozatbol
// Programozó Páternoszter
//
// Copyright (C) 2011, Bátfai Norbert, nbatfai@inf.unideb.hu, nbatfai@gmail.com
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
// Ez a program szabad szoftver; terjeszthetõ illetve módosítható a
// Free Software Foundation által kiadott GNU General Public License
// dokumentumában leírtak; akár a licenc 3-as, akár (tetszõleges) késõbbi
// változata szerint.
//
// Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz,
// de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA
// VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve.
// További részleteket a GNU General Public License tartalmaz.
//
// A felhasználónak a programmal együtt meg kell kapnia a GNU General
// Public License egy példányát; ha mégsem kapta meg, akkor
// tekintse meg a <http://www.gnu.org/licenses/> oldalon.
//
//
// Version history:
//
// 0.0.1, http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor
// 0.0.2, csomópontok mutatóinak NULLázása (nem fejtette meg senki :)
// 0.0.3, http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat
// 0.0.4, a C verzióból svn: bevezetes/C/ziv/z.c átírjuk C++-ra
//        http://progpater.blog.hu/2011/03/31/imadni_fogjatok_a_c_t_egy_emberkent_tiszta_szivbol
//

#include <iostream>

class LZWBinFa
{
public:
    LZWBinFa (char b = '/'):betu (b), balNulla (NULL), jobbEgy (NULL) {};
    ~LZWBinFa () {};
    LZWBinFa *nullasGyermek () {
        return balNulla;
    }
    LZWBinFa *egyesGyermek ()
    {
        return jobbEgy;
    }
    void ujNullasGyermek (LZWBinFa * gy)
    {
        balNulla = gy;
    }
    void ujEgyesGyermek (LZWBinFa * gy)
    {
        jobbEgy = gy;
    }
    void kiir (void)
    {
        melyseg = 0;
        kiir (this);
    }
    void szabadit (void)
    {
        szabadit (jobbEgy);
        szabadit (balNulla);
    }


private:
    char betu;
    LZWBinFa *balNulla;
    LZWBinFa *jobbEgy;

    LZWBinFa (const LZWBinFa &);
    LZWBinFa & operator=(const LZWBinFa &);

    int melyseg;

    void kiir (LZWBinFa * elem)
    {
        if (elem != NULL)
        {
            ++melyseg;
            kiir (elem->jobbEgy);
            // ez a postorder bejáráshoz képest
            // 1-el nagyobb mélység, ezért -1
            for (int i = 0; i < melyseg; ++i)
                std::cout << "---";
            std::cout << elem->betu << "(" << melyseg - 1 << ")" << std::endl;
            kiir (elem->balNulla);
            --melyseg;
        }
    }
    void szabadit (LZWBinFa * elem)
    {
        if (elem != NULL)
        {
            szabadit (elem->jobbEgy);
            szabadit (elem->balNulla);
            delete elem;
        }
    }

};

int
main ()
{
    char b;
    LZWBinFa gyoker, *fa = &gyoker;
    
    while (std::cin >> b)
    {
        if (b == '0')
        {
            // van '0'-s gyermeke az aktuális csomópontnak?
            if (!fa->nullasGyermek ()) // ha nincs, csinálunk
            {
                LZWBinFa *uj = new LZWBinFa ('0');
                fa->ujNullasGyermek (uj);
                fa = &gyoker;
            }
            else // ha van, arra lépünk
            {
                fa = fa->nullasGyermek ();
            }
        }
        else
        {
            if (!fa->egyesGyermek ())
            {
                LZWBinFa *uj = new LZWBinFa ('1');
                fa->ujEgyesGyermek (uj);
                fa = &gyoker;
            }
            else
            {
                fa = fa->egyesGyermek ();
            }
        }
    }

    gyoker.kiir ();
    gyoker.szabadit ();

    return 0;
}

 Érezni némi zavart az erőben, hiszen a mélység, ami a C-ben globális volt, most minden csomópontnak tagja... Persze ráfoghatnánk, hogy direkt így akartuk és az építés során minden új gyerek csomópont ilyen tagját a szülőé+1 értékre állíthatnánk. De ezt nem akarjuk, mert a fa szerkezetében ott a mélység, nem akarjuk majd külön csomópontonként tárolni. S ugye esetünkben a gyökérben lévő mélységben amúgy is a teljes fa mélységét tároljuk. Illetve az atomhackerek munkája nyomán (C-beli) globális nélkül is meg tudjuk majd írni a bejárást.

Lehúzunk majd még pár bőrt erről a példáról, de nem ma. Olyan objektum lenne jó, ami teljesen elrejtené a korábbi C-s progi logikáját (ami tk. az algoritmus, az LZW fa építésének logikája) mondjuk csak "<<" operátorral kéne belenyomni az inputról bejövő betűket az LZW fa objektumba, nem?