Programozó Páternoszter

Folytatjuk állatorvosi sorozatunkat, ha ezt olvasod, akkor feltételezhetően már túl vagy az alábbi, erősorrendben hivatkozott posztokon:

• a Tömör a gyönyörben kifejlesztettünk egy C struktúrás LZW (bináris) fa építőt
• mélyebben megismerkedhettél a kóddal a Labormérés otthon, avagy hogyan dolgozok fel egy példát posztban
• amit jó (K&R) szokás szerint továbbfejlesztések sorát át elkezdtünk átteni C++-ba

Ez a poszt is ebbe a sorozatba illeszkedik.

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?

Lássuk, mit is szeretnénk: 

int
main ()
{
    char b;
    LZWBinFa binFa;

    while (std::cin >> b)
    {
        binFa << b;
    }

    binFa.kiir ();
    binFa.szabadit ();

    return 0;
}

Ezt azért tehetjük meg, mert a LZWBinFa osztályban definiáltuk a << operátort: 

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

 Aminek kódja teljesen ugyanaz, mint az előző változat, csupán az osztálynév változott a csomópontot mostmár a "Csomopont" osztály absztrahálja. Ennek érdekessége, hogy definícióját beágyaztuk az LZWBinFa osztályba:

private:

    class Csomopont
    {
    public:
        Csomopont (char b = '/'):betu (b), balNulla (0), jobbEgy (0) {};
        ~Csomopont () {};
        Csomopont *nullasGyermek () {
            return balNulla;
        }
        Csomopont *egyesGyermek ()
        {
            return jobbEgy;
        }
        void ujNullasGyermek (Csomopont * gy)
        {
            balNulla = gy;
        }
        void ujEgyesGyermek (Csomopont * gy)
        {
            jobbEgy = gy;
        }
    private:
        friend class LZWBinFa;
        char betu;
        Csomopont *balNulla;
        Csomopont *jobbEgy;
        Csomopont (const Csomopont &);
        Csomopont & operator=(const Csomopont &);
    }; 

Növeltük az absztrakció mértékét a csomópont definiálásával, de a meglévő kódot csak kicsi lépésekben akarjuk módosítani, s most az LZWBinFa módszerei ezért dolgoznak a csomópont védett tagjaival, hogy ez mehessen, ezért a csomópont barátjának deklaráltuk a fát elvonatkoztató tartalmazó osztályt.

Tekerj a tovább linkre a folytatásért.

// z3.cpp
//
// LZW fa építő 3. C++ átirata 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, z.cpp: 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
// 0.0.5, z2.cpp: az fgv(*mut)-ok helyett fgv(&ref)
// 0.0.6, z3.cpp: Csomopont beágyazva
//        http://progpater.blog.hu/2011/04/01/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_2
//

#include <iostream>

class LZWBinFa
{
public:
    LZWBinFa (): fa(&gyoker) {}

    void operator<<(char b)
    {
        if (b == '0')
        {
            // van '0'-s gyermeke az aktuális csomópontnak?
            if (!fa->nullasGyermek ()) // ha nincs, csinálunk
            {
                Csomopont *uj = new Csomopont ('0');
                fa->ujNullasGyermek (uj);
                fa = &gyoker;
            }
            else // ha van, arra lépünk
            {
                fa = fa->nullasGyermek ();
            }
        }
        else
        {
            if (!fa->egyesGyermek ())
            {
                Csomopont *uj = new Csomopont ('1');
                fa->ujEgyesGyermek (uj);
                fa = &gyoker;
            }
            else
            {
                fa = fa->egyesGyermek ();
            }
        }
    }
    void kiir (void)
    {
        melyseg = 0;
        kiir (&gyoker);
    }
    void szabadit (void)
    {
        szabadit (gyoker.jobbEgy);
        szabadit (gyoker.balNulla);
    }

private:

    class Csomopont
    {
    public:
        Csomopont (char b = '/'):betu (b), balNulla (0), jobbEgy (0) {};
        ~Csomopont () {};
        Csomopont *nullasGyermek () {
            return balNulla;
        }
        Csomopont *egyesGyermek ()
        {
            return jobbEgy;
        }
        void ujNullasGyermek (Csomopont * gy)
        {
            balNulla = gy;
        }
        void ujEgyesGyermek (Csomopont * gy)
        {
            jobbEgy = gy;
        }
        
    private:
        friend class LZWBinFa;
        char betu;
        Csomopont *balNulla;
        Csomopont *jobbEgy;
        Csomopont (const Csomopont &);
        Csomopont & operator=(const Csomopont &);
    };

    Csomopont gyoker;
    Csomopont *fa;
    int melyseg;

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

    void kiir (Csomopont* 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 (Csomopont * elem)
    {
        if (elem != NULL)
        {
            szabadit (elem->jobbEgy);
            szabadit (elem->balNulla);
            delete elem;
        }
    }

};

int
main ()
{
    char b;
    LZWBinFa binFa;

    while (std::cin >> b)
    {
        binFa << b;
    }

    binFa.kiir ();
    binFa.szabadit ();

    return 0;
}