Humángenom

// z3a5.cpp
//
// Együtt támadjuk meg: http://progpater.blog.hu/2011/04/14/egyutt_tamadjuk_meg
// LZW fa építő 3. C++ átirata a C valtozatbol (+mélység, atlag és szórás)
// 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 yout 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
// 0.0.6.1      z3a2.c: LZWBinFa már nem barátja a Csomopont-nak, mert annak tagjait nem használja direktben
// 0.0.6.2      Kis kommentezést teszünk bele 1. lépésként (hogy a kicsit lemaradt hallgatóknak is
//              könnyebb legyen, jól megtűzdeljük további olvasmányokkal)
//              http://progpater.blog.hu/2011/04/14/egyutt_tamadjuk_meg
//              (majd a 2. lépésben "beletesszük a d.c-t", majd s 3. lépésben a parancssorsor argok feldolgozását)
// 0.0.6.3      z3a2.c: Fejlesztgetjük a forrást: http://progpater.blog.hu/2011/04/17/a_tizedik_tizenegyedik_labor
// 0.0.6.4      SVN-beli, http://www.inf.unideb.hu/~nbatfai/p1/forrasok-SVN/bevezetes/vedes/
// 0.0.6.5      2012.03.20, z3a4.cpp: N betűk (hiányok), sorvégek, vezető komment figyelmen kívül: http://progpater.blog.hu/2012/03/20/a_vedes_elokeszitese
// 0.0.6.6      z3a5.cpp: mamenyaka kolléga észrevételére a több komment sor figyelmen kívül hagyása
//


import java.io.*;

/* Az LZWBinFa osztályban absztraháljuk az LZW algoritmus bináris fa építését. Az osztály
 definíciójába beágyazzuk a fa egy csomópontjának az absztrakt jellemzését, ez lesz a
 beágyazott Csomopont osztály. Miért ágyazzuk be? Mert külön nem szánunk neki szerepet, ezzel
 is jelezzük, hogy csak a fa részeként számiolunk vele.*/

class LZWBinFa
{               /* Szemben a bináris keresőfánkkal (BinFa osztály)
                   http://progpater.blog.hu/2011/04/12/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_3
                   itt (LZWBinFa osztály) a fa gyökere nem pointer, hanem a '/' betüt tartalmazó objektum,
                   lásd majd a védett tagok között lent: Csomopont gyoker;
                   A fa viszont már pointer, mindig az épülő LZW-fánk azon csomópontjára mutat, amit az
                   input feldolgozása során az LZW algoritmus logikája diktál:
                   http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor
                   Ez a konstruktor annyit csinál, hogy a fa mutatót ráállítja a gyökérre. (Mert ugye
                   labopon, blogon, előadásban tisztáztuk, hogy a tartalmazott tagok, most "Csomopont gyoker"
                   konstruktora előbb lefut, mint a tagot tartalmazó LZWBinFa osztály konstruktora, éppen a
                   következő, azaz a fa=gyoker OK.)
                 */
  public LZWBinFa ()
  {
    gyoker = new Csomopont ('/');
    fa = gyoker;
  }

  public void beolvas (char b)
  {
    // Mit kell betenni éppen, '0'-t?
    if (b == '0')
      {
    /* Van '0'-s gyermeke az aktuális csomópontnak?
       megkérdezzük Tőle, a "fa" mutató éppen reá mutat */
    if (fa.nullasGyermek () == null)    // ha nincs, hát akkor csinálunk
      {
        // elkészítjük, azaz páldányosítunk a '0' betű akt. parammal
        Csomopont uj = new Csomopont ('0');
        // az aktuális csomópontnak, ahol állunk azt üzenjük, hogy
        // jegyezze már be magának, hogy nullás gyereke mostantól van
        // küldjük is Neki a gyerek címét:
        fa.ujnullasGyermek (uj);
        // és visszaállunk a gyökérre (mert ezt diktálja az alg.)
        fa = gyoker;
      }
    else            // ha van, arra rálépünk
      {
        // azaz a "fa" pointer már majd a szóban forgó gyermekre mutat:
        fa = fa.nullasGyermek ();
      }
      }
    // Mit kell betenni éppen, vagy '1'-et?
    else
      {
    if (fa.egyesGyermek () == null)
      {
        Csomopont uj = new Csomopont ('1');
        fa.ujEgyesGyermek (uj);
        fa = gyoker;
      }
    else
      {
        fa = fa.egyesGyermek ();
      }
      }
  }
  /* A bejárással kapcsolatos függvényeink (túlterhelt kiir-ók, atlag, ratlag stb.) rekurzívak,
     tk. a rekurzív fabejárást valósítják meg (lásd a 3. előadás "Fabejárás" c. fóliáját és társait)

     (Ha a rekurzív függvénnyel általában gondod van => K&R könyv megfelelő része: a 3. ea. izometrikus
     részében ezt "letáncoltuk" :) és külön idéztük a K&R álláspontját :)
   */

  /* A változatosság kedvéért ezeket az osztálydefiníció (class LZWBinFa {...};) után definiáljuk,
     hogy kénytelen légy az LZWBinFa és a :: hatókör operátorral minősítve definiálni :) l. lentebb */
  public int getMelyseg ()
  {
    melyseg = maxMelyseg = 0;
    rmelyseg (gyoker);
    return maxMelyseg - 1;
  }
  public double getSzoras ()
  {
    atlag = getAtlag ();
    szorasosszeg = 0.0;
    melyseg = atlagdb = 0;

    rszoras (gyoker);

    if (atlagdb - 1 > 0)
      szoras = Math.sqrt (szorasosszeg / (atlagdb - 1));
    else
      szoras = Math.sqrt (szorasosszeg);

    return szoras;
  }
  public double getAtlag ()
  {
    melyseg = atlagosszeg = atlagdb = 0;
    ratlag (gyoker);
    atlag = ((double) atlagosszeg) / atlagdb;
    return atlag;
  }


  /* Vágyunk, hogy a felépített LZW fát ki tudjuk nyomni ilyenformán: std::cout << binFa;
     de mivel a << operátor is a sztenderd névtérben van, de a using namespace std-t elvből
     nem használjuk bevezető kurzusban, így ez a konstrukció csak az argfüggő névfeloldás miatt
     fordul le (B&L könyv 185. o. teteje) ám itt nem az a lényeg, hanem, hogy a cout ostream
     osztálybeli, így abban az osztályban kéne módosítani, hogy tudjon kiírni LZWBinFa osztálybelieket...
     e helyett a globális << operátort terheljük túl, */
  private class Csomopont
  {
    /* A paraméter nélküli konstruktor az elepértelmezett '/' "gyökér-betűvel" hozza
       létre a csomópontot, ilyet hívunk a fából, aki tagként tartalmazza a gyökeret.
       Máskülönben, ha valami betűvel hívjuk, akkor azt teszi a "betu" tagba, a két
       gyermekre mutató mutatót pedig nullra állítjuk, C++-ban a 0 is megteszi. */
    public Csomopont (char b)
    {
      betu = b;
    };

    // Aktuális csomópont, mondd meg nékem, ki a bal oldali gyermeked
    // (a C verzió logikájával műxik ez is: ha nincs, akkor a null megy vissza)
    public Csomopont nullasGyermek ()
    {
      return balnulla;
    }
    // Aktuális csomópon,t mondd meg nékem, ki a jobb oldali gyermeked?
    public Csomopont egyesGyermek ()
    {
      return jobbEgy;
    }
    // Aktuális csomópont, ímhol legyen a "gy" mutatta csomópont a bal oldali gyereked!
    public void ujnullasGyermek (Csomopont gy)
    {
      balnulla = gy;
    }
    // Aktuális csomópont, ímhol legyen a "gy" mutatta csomópont a jobb oldali gyereked!
    public void ujEgyesGyermek (Csomopont gy)
    {
      jobbEgy = gy;
    }
    // Aktuális csomópont: Te milyen betűt hordozol?
    // (a const kulcsszóval jelezzük, hogy nem bántjuk a példányt)
    public char getBetu ()
    {
      return betu;
    }

    // friend class LZWBinFa; /* mert ebben a valtozatban az LZWBinFa metódusai nem közvetlenül
    // a Csomopont tagjaival dolgoznak, hanem beállító/lekérdező üzenetekkel érik el azokat */

    // Milyen betűt hordoz a csomópont
    private char betu;
    // Melyik másik csomópont a bal oldali gyermeke? (a C változatból "örökölt" logika:
    // ha hincs ilyen csermek, akkor balnulla == null) igaz
    private Csomopont balnulla;
    private Csomopont jobbEgy;
  };

  /* Mindig a fa "LZW algoritmus logikája szerinti aktuális" csomópontjára mutat */
  Csomopont fa;
  // technikai
  private int melyseg, atlagosszeg, atlagdb;
  private double szorasosszeg;
  /* Kiírja a csomópontot az os csatornára. A rekurzió kapcsán lásd a korábbi K&R-es utalást... */
  public void kiir (Csomopont elem, FileWriter file) throws IOException
  {

    // Nem létező csomóponttal nem foglalkozunk... azaz ez a rekurzió leállítása
    if (elem != null)
      {
    ++melyseg;
    kiir (elem.egyesGyermek (), file);

    // ez a postorder bejáráshoz képest
    // 1-el nagyobb mélység, ezért -1
    for (int i = 0; i < melyseg; ++i)
      file.write ("---");
    file.write (elem.getBetu () + "(" + (melyseg - 1) + ")" + "\n");
    kiir (elem.nullasGyermek (), file);
    --melyseg;

      }
  }

  // ha esetleg egyszer majd kiterjesztjük az osztályt, mert
// akarunk benne valami újdonságot csinálni, vagy meglévő tevékenységet máshogy... stb.
// akkor ezek látszanak majd a gyerek osztályban is

  /* A fában tagként benne van egy csomópont, ez erősen ki van tüntetve, Ő a gyökér: */
  public Csomopont gyoker;
  protected int maxMelyseg;
  protected double atlag, szoras;

  protected void rmelyseg (Csomopont elem)
  {
    if (elem != null)
      {
    ++melyseg;
    if (melyseg > maxMelyseg)
      maxMelyseg = melyseg;
    rmelyseg (elem.egyesGyermek ());
    // ez a postorder bejáráshoz képest
    // 1-el nagyobb mélység, ezért -1
    rmelyseg (elem.nullasGyermek ());
    --melyseg;
      }
  }
  protected void ratlag (Csomopont elem)
  {
    if (elem != null)
      {
    ++melyseg;
    ratlag (elem.egyesGyermek ());
    ratlag (elem.nullasGyermek ());
    --melyseg;
    if (elem.egyesGyermek () == null && elem.nullasGyermek () == null)
      {
        ++atlagdb;
        atlagosszeg += melyseg;
      }
      }
  }
  protected void rszoras (Csomopont elem)
  {
    if (elem != null)
      {
    ++melyseg;
    rszoras (elem.egyesGyermek ());
    rszoras (elem.nullasGyermek ());
    --melyseg;
    if (elem.egyesGyermek () == null && elem.nullasGyermek () == null)
      {
        ++atlagdb;
        szorasosszeg += ((melyseg - atlag) * (melyseg - atlag));
      }
      }
  }

}

// Néhány függvényt az osztálydefiníció után definiálunk, hogy lássunk ilyet is ... :)
// Nem erőltetjük viszont a külön fájlba szedést, mert a sablonosztályosított tovább
// fejlesztésben az linkelési gondot okozna, de ez a téma már kivezet a laborteljesítés
// szükséges feladatából: http://progpater.blog.hu/2011/04/12/imadni_fogjak_a_c_t_egy_emberkent_tiszta_szivbol_3

// Egyébként a melyseg, atlag és szoras fgv.-ek a kiir fgv.-el teljesen egy kaptafa.
// teszt pl.: http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat
// [norbi@sgu ~]$ echo "01111001001001000111"|./z3a2
// ------------1(3)
// ---------1(2)
// ------1(1)
// ---------0(2)
// ------------0(3)
// ---------------0(4)
// ---/(0)
// ---------1(2)
// ------0(1)
// ---------0(2)
// depth = 4
// mean = 2.75
// var = 0.957427
// a laborvédéshez majd ezt a tesztelést használjuk:
// http://

/* Ez volt eddig a main, de most komplexebb kell, mert explicite bejövő, kimenő fájlokkal kell dolgozni
int
main ()
{
    char b;
    LZWBinFa binFa;

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

    //std::cout << binFa.kiir (); // így rajzolt ki a fát a korábbi verziókban de, hogy izgalmasabb legyen
    // a példa, azaz ki lehessen tolni az LZWBinFa-t kimeneti csatornára:

    std::cout << binFa; // ehhez kell a globális operator<< túlterhelése, lásd fentebb

    std::cout << "depth = " << binFa.getMelyseg () << std::endl;
    std::cout << "mean = " << binFa.getAtlag () << std::endl;
    std::cout << "var = " << binFa.getSzoras () << std::endl;

    binFa.szabadit ();

    return 0;
}
*/

/* A parancssor arg. kezelést egyszerűen bedolgozzuk a 2. hullám kapcsolódó feladatából:
 http://progpater.blog.hu/2011/03/12/hey_mikey_he_likes_it_ready_for_more_3
 de mivel nekünk sokkal egyszerűbb is elég, alig hagyunk meg belőle valamit...
 */
public class Humangenom
{
  public static void usage ()
  {
    System.out.println ("Usage: lzwtree in_file out_file");
  }

  public static void main (String args[])
  {
    // http://progpater.blog.hu/2011/03/12/hey_mikey_he_likes_it_ready_for_more_3
    // alapján a parancssor argok ottani elegáns feldolgozásából kb. ennyi marad:
    // "*((*++argv)+1)"...

    // a kiírás szerint ./lzwtree in_file -o out_file alakra kell mennie, ez 4 db arg:
    if (args.length != 2)
      {
    // ha nem annyit kapott a program, akkor felhomályosítjuk erről a júzetr:
    usage ();
    // és jelezzük az operációs rendszer felé, hogy valami gáz volt...
    return;
      }

    // "Megjegyezzük" a bemenő fájl nevét
    // a -o kapcsoló jön?

    FileReader beFile;
    FileWriter kiFile;
    // ha igen, akkor az 5. előadásból kimásoljuk a fájlkezelés C++ változatát:
    char b;         // ide olvassik majd a bejövő fájl bájtjait
    LZWBinFa binFa = new LZWBinFa ();   // s nyomjuk majd be az LZW fa objektumunkba
    try
    {
      beFile = new FileReader (args[0]);
      try
      {
    while (beFile.ready ())
      {
        b = (char) beFile.read ();
        if (b == 0x0a)
          break;
      }
      }
      catch (IOException e)
      {
      }
      boolean kommentben = false;
      try
      {
    while (beFile.ready ())
      {
        b = (char) beFile.read ();
        if (b == 0x3e)
          {         // > karakter
        kommentben = true;
        continue;
          }

        if (b == 0x0a)
          {         // újsor
        kommentben = false;
        continue;
          }

        if (kommentben)
          continue;

        if (b == 0x4e)  // N betű
          continue;

        // egyszerűen a korábbi d.c kódját bemásoljuk
        // laboron többször lerajzoltuk ezt a bit-tologatást:
        // a b-ben lévő bájt bitjeit egyenként megnézzük
        int szo = (int) b;
        for (int i = 0; i < 8; ++i)
          {
        // maszkolunk eddig..., most már simán írjuk az if fejébe a legmagasabb helyiértékű bit vizsgálatát
        // csupa 0 lesz benne a végén pedig a vizsgált 0 vagy 1, az if megmondja melyik:
        if ((int) (szo / Math.pow (2, 7 - i)) == 1)
          {
            // ha a vizsgált bit 1, akkor az '1' betűt nyomjuk az LZW fa objektumunkba
            binFa.beolvas ('1');
            szo -= Math.pow (2, 7 - i);
          }
        else
          // különben meg a '0' betűt:
          binFa.beolvas ('0');
          }

      }
      }
      catch (IOException e)
      {
      }
    }
    catch (FileNotFoundException ex)
    {
      System.out.println (args[0] + " nem letezik");
      return;
    }

    // fejlesztgetjük a forrást: http://progpater.blog.hu/2011/04/17/a_tizedik_tizenegyedik_labor
    try
    {
      kiFile = new FileWriter (args[1]);
      // a bemenetet binárisan olvassuk, de a kimenő fájlt már karakteresen írjuk, hogy meg tudjuk
      // majd nézni... :) l. az említett 5. ea. C . C++ gyökkettes átírási példáit


      //std::cout << binFa.kiir (); // így rajzolt ki a fát a korábbi verziókban de, hogy izgalmasabb legyen
      // a példa, azaz ki lehessen tolni az LZWBinFa-t kimeneti csatornára:
      binFa.kiir (binFa.gyoker, kiFile);
      // ehhez kell a globális operator<< túlterhelése, lásd fentebb
      // (jó ez az OO, mert mi ugye nem igazán erre gondoltunk, amikor írtuk, mégis megy, hurrá)

      kiFile.write ("depth = " + binFa.getMelyseg () + "\n");
      kiFile.write ("mean = " + binFa.getAtlag () + "\n");
      kiFile.write ("var = " + binFa.getSzoras () + "\n");

      kiFile.close ();
      beFile.close ();
    }
    catch (IOException ex)
    {
    }
  }
}