/***
 * File neve: graf.java
 * Szerző: Szatmáry Botond
 * Utolsó módosítás: 1998. jun. 15.
 * Leírás: Egy irányított gráf osztályt valósít meg. Ez az osztály szolgál a
 * terminálok közötti hierarchikus rendszer leírására. A gráfok csúcsai a
 * csucs osztály egy-egy példánya. Minden a beléptetőrendszerben használt
 * gráfművelet megvalósítása itt történik.
 ***/

import java.io.*;
import java.util.*;

public class graf
{
  /*
   * a körök kiküszöböléséhez kell
   */
  private lista korker=new lista(100);
  /*
   * a feltöltetlen csúcsokat tartalmazza
   */
  private Vector rosszak=new Vector(100);
  private csucs gyoker, aktualis, felett;
  private BufferedWriter out;
  private BufferedReader in;

  /**
   * a BF algoritmushoz kellenek
   * private int csucsSzam; // a gráfban lévő csúcsok száma
   * private lista elek=new lista(100); // a gráfban lévő élek
   */
  private int csucsSzam; // a gráfban lévő csúcsok száma
  private lista elek=new lista(100); // a gráfban lévő élek

  /**
   *Konstrukror ... amikor file-ból töltjük fel a gráfot
   */
  public graf()
  {
  }
  /**
   * Konstuktor ... amikor új gráfot hozunk létre (nem file-ból)
   */
  public graf( String neve)
  {
    gyoker=new csucs(neve);
    aktualis=gyoker;
  }

  /**
   * Visszater a gráf gyökérevel.
   */
  public csucs getGyoker()
  {
    return gyoker;
  }
  
  /**
   * Új elemet illeszt be a gráfba.
   */
  public void ujelem( String neve, String azonosito, String csoport, lista kovetkezok, int x, int y, int emelet, String tol, String ig )
  {
    csucs p;
    if ( (p=Keres(gyoker,azonosito))==null )
      p=new csucs(neve,azonosito,csoport,x,y,emelet,tol,ig);
    else
      {
	// kiveszi azokat a p.kovetkezo-k közül, amelyek nem szerepelnek
	// a paraméterként kapott kovetkezok között
	p.kovetkezo.torol(p,kovetkezok);
	p.set(neve,azonosito,csoport,x,y,emelet,tol,ig);
      }
    for ( Enumeration e=kovetkezok.elements(); e.hasMoreElements(); )
      {
	String s=(String)e.nextElement();
	if ( (aktualis=Keres(gyoker,s))!=null )
	  {	
	    if ( !p.kovetkezo.benne(s) )
	      {
		p.kovetkezo.addElement(aktualis);
		aktualis.elozo.addElement(p);
	      }
	  }
	else // ha még nem volt, akkor létre kell hozni.
	     // a fa csak egymasra epítve jöhet létre.
	  {
	    csucs uj=new csucs(s);
	    p.kovetkezo.addElement(uj);
	    uj.elozo.addElement(p);
	  }
      }
  }

  /**
   * Új elemet illeszt be a gráfba. Itt String-ként kell megadni a következőket,
   * vesszővel elválasztva
   */
  public void ujelem( String neve, String azonosito, String csoport, String kovetkezok, int x, int y, int emelet, String tol, String ig )
  {
    lista k;
    k=new lista(30);

    int index=0;
    while ( index < kovetkezok.length() )
      {
	int kov=kovetkezok.indexOf(",",index);
	if ( kov==-1 ) kov=kovetkezok.length();
	k.addElement(kovetkezok.substring(index,kov));
	index=kov+1;
      }

    ujelem( neve, azonosito, csoport, k, x, y, emelet, tol, ig );
  }

  /**
   * Kitörli p csúcsot a gráfból.
   */
  public void torol( csucs p )
  {
    p.torolt=true;
  }

  /**
   * adott csúcstól (p) kezdve lefelé keres 'azonosito' azonosítójú csúcsot
   */
  private csucs keres( csucs p, String azonosito )
  {
    if ( p.azonosito.equals(azonosito) )
      return p;
    korker.addElement(p);

    boolean l=false;
    for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements() && !l; )
      {
	aktualis=(csucs)e.nextElement();
	if ( !korker.benne(aktualis.azonosito) )
	  l=((aktualis=keres(aktualis,azonosito))!=null);
      }

    if ( l )
      return aktualis;
    else
      return null;
  }
  /**
   * adott csúcstól (p) kezve lefelé keres x,y koordinata alapján csúcsot
   */
  private void keresxy( csucs p, int x, int y )
  {
    if ( p.x<=x && p.x+p.dx>=x && p.y<=y && p.y+p.dy>=y )
      {
	felett=p;
      }
    korker.addElement(p);

    for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements(); )
      {
	aktualis=(csucs)e.nextElement();
	if ( !aktualis.torolt && !korker.benne(aktualis.azonosito) )
	  keresxy(aktualis,x,y);
      }
  }

  //  Ezen keresztul lehet a keres metodust meghivni. Kiküszöböli a köröket.
  /**
   * Adott csúcstól (p) kezdve lefelé Keres 'azonosito' azonosítójú csúcsot.
   * null-al tér vissza, ha nincs ilyen csúcs. 
  */
  public csucs Keres( csucs p, String azonosito )
  {
    korker.removeAllElements();
    return keres(p,azonosito);
  }
  /**
   * A gyökértol kezve lefelé Keres 'azonosito' azonositoju csucsot.
   * null-al ter vissza, ha nincs ilyen csucs.
   */
  public csucs Keres( String azonosito )
  {
    return Keres(gyoker,azonosito);
  }
  /**
   * A 'p' csucstol kezve lefelé Keres x,y koordinata alapjan csucsot.
   * null-al ter vissza, ha nincs ilyen csucs.
   */
  public csucs Keres( csucs p, int x, int y )
  {
    felett=null;
    korker.removeAllElements();
    keresxy(p,x,y);
    return felett;
  }
  /**
   * A gyökértol kezve lefelé Keres x,y koordinata alapjan csucsot.
   * null-al ter vissza, ha nincs ilyen csucs.
   */
  public csucs Keres( int x, int y )
  {
    return Keres(gyoker,x,y);
  }

  /**
   * kiirja a kepernyore a gráf összes csucsat valamilyen order bejarassal
   * lefelé (következő) haladva
   */
  private void kiir( csucs p )
  {
    p.kiir(); // ez itt a csucs kiir metodusa!!!
    korker.addElement(p);

    for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements(); )
      {
	aktualis=(csucs)e.nextElement();
	if ( !aktualis.torolt && !korker.benne(aktualis.azonosito) )
	  kiir(aktualis);
      }
  }

  //  Ezen keresztül lehet a kiir metodust meghivni. Kiküszöböli a köröket.
  /**
   * Kiirja a kepernyore a gráf összes csúcsat valamilyen order bejarassal.
   */
  public void Kiir( csucs p )
  {
    korker.removeAllElements();
    kiir(p);
  }

  /**
   * Visszater a gráf csúcsait tartalmazo listaval.
   */
  public lista csucsok()
  {
    korker.removeAllElements();
    kiir(gyoker);
    return korker;
  }

  /**
   * elmenteshez kell
   */
  private void csucs_ki( csucs p )
  {
    korker.addElement(p);
    try
      {
	// kiirodik a neve
	out.write("#");
	out.write(p.neve,0,p.neve.length());
	out.write("#");

	// kiirodik az azonosítója
	out.write(p.azonosito,0,p.azonosito.length());
	out.write("#");

	// kiirodik a csoportja
	out.write(p.csoport,0,p.csoport.length());
	out.write("#");

	// kiirodik az előző csúcsok azonosítója
	for ( Enumeration e=p.elozo.elements(); e.hasMoreElements(); )
	  {
	    aktualis=(csucs)e.nextElement();
	    if ( !aktualis.torolt )
	      {
		out.write(aktualis.azonosito,0,aktualis.azonosito.length());
		if ( e.hasMoreElements() )
		  out.write(",");
	      }
	  }
	out.write("#");

	// kiirodik a következő csúcsok azonosítója
	for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements(); )
	  {
	    aktualis=(csucs)e.nextElement();
	    if ( !aktualis.torolt )
	      {
		out.write(aktualis.azonosito,0,aktualis.azonosito.length());
		if ( e.hasMoreElements() )
		  out.write(",");
	      }
	  }
	out.write("#");

	// kiirodik az x koordinataja
	Integer x=new Integer(p.x);
	out.write(x.toString(),0,x.toString().length());
	out.write("#");

	// kiirodik az y koordinataja
	Integer y=new Integer(p.y);
	out.write(y.toString(),0,y.toString().length());
	out.write("#");

	// kiirodik az emelet
	Integer emelet=new Integer(p.emelet);
	out.write(emelet.toString(),0,emelet.toString().length());
	out.write("#");

	// kiirodik a 'tol'
	out.write(p.tol,0,p.tol.length());
	out.write("#");

	// kiirodik az 'ig'
	out.write(p.ig,0,p.ig.length());
	out.write("#");
	
	out.newLine();
      }
    catch ( IOException e )
      {
	System.err.println(e);
      }
    for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements(); )
      {
	aktualis=(csucs)e.nextElement();
	if ( !korker.benne(aktualis.azonosito) )
	  csucs_ki(aktualis);
      }
  }

  /**
   * Elmenti 'neve' neven file-ba a gráfot.
   */
  public void ment( String neve )
  {
    korker.removeAllElements();
    try
      {
	out=new BufferedWriter( new FileWriter(neve) );
	out.write(gyoker.azonosito,0,gyoker.azonosito.length());
	out.newLine();
	csucs_ki(this.gyoker);
	out.close();
      }
    catch (IOException e)
      {
	System.err.println(e);
      }
  }

  /**
   * Felepiti a gráfot adott file-bol. Csak ures gráfra szabad hasznalni.
   */
  public boolean beolvas( String file )  // Misi belenyult
  {
    // beolvassa a nevet
    // csúcsok adatait olvassa, beilleszti
    try
      {
	String sor;
	in=new BufferedReader( new FileReader(file) );
	sor=in.readLine();
	gyoker=new csucs(sor);
	sor=in.readLine();
	while ( sor!=null ) // ezek itt mar a benne levo csúcsok
	  {
	    // neve
	    int nev_vege=sor.indexOf("#",1);
	    String neve=sor.substring(1,nev_vege);

	    // azonosító
	    int azon_vege=sor.indexOf("#",nev_vege+1);
	    csucs p;
	    if ( (p=Keres(gyoker,sor.substring(nev_vege+1,azon_vege)))==null )
	      p=new csucs(sor.substring(nev_vege+1,azon_vege));
	    lista elozoek, kovetkezok;
	    elozoek=new lista(30);
	    kovetkezok=new lista(30);

	    // csoport
	    int csoport_vege=sor.indexOf("#",azon_vege+1);
	    String csoport=sor.substring(azon_vege+1,csoport_vege);

	    // előzők
	    int elozo_vege=sor.indexOf("#",csoport_vege+1);

	    // következők
	    int kov_vege=sor.indexOf("#",elozo_vege+1);
	    int kov1=elozo_vege+1;
	    int t1=sor.indexOf(",",kov1);
	    int t2=sor.indexOf("#",kov1);
	    int kov2=t1<t2?t1:t2;
	    if ( kov2==-1 ) kov2=t2;
	    while ( kov2!=-1 && kov2<=kov_vege )
	      {
		String s=sor.substring(kov1,kov2);
		if ( !s.equals("") )
		  kovetkezok.addElement(s);

		kov1=kov2+1;
		t1=sor.indexOf(",",kov1);
		t2=sor.indexOf("#",kov1);
		kov2=t1<t2?t1:t2;
		if ( kov2==-1 ) kov2=t2;
	      }

	    // x koordinata
	    int x_vege=sor.indexOf("#",kov_vege+1);
	    int x=Integer.parseInt(sor.substring(kov_vege+1,x_vege));

	    // y koordinata
	    int y_vege=sor.indexOf("#",x_vege+1);
	    int y=Integer.parseInt(sor.substring(x_vege+1,y_vege));

	    // emelet
	    int e_vege=sor.indexOf("#",y_vege+1);
	    int emelet=Integer.parseInt(sor.substring(y_vege+1,e_vege));

	    // tol
	    int tol_vege=sor.indexOf("#",e_vege+1);
	    String tol=sor.substring(e_vege+1,tol_vege);

	    // ig
	    int ig_vege=sor.indexOf("#",tol_vege+1);
	    String ig=sor.substring(tol_vege+1,ig_vege);

	    // uj csúcs
	    ujelem(neve,p.azonosito,csoport,kovetkezok,x,y,emelet,tol,ig);
	    sor=in.readLine();
	  }
	return true;
      }
    catch (Exception e)
      {
	//System.err.println(e);
	return false;  // Misi belnyult
      }
  }

  /**
   * ellenőrzi, hogy minden csúcshoz (p alatt) normális érték van-e rendelve
   */
  private void helyes( csucs p )
  {
    if ( !p.helyes() ) // csúcs helyes eljarasa!!!
      rosszak.addElement(p.azonosito);
    
    korker.addElement(p);

    for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements(); )
      {
	aktualis=(csucs)e.nextElement();
	if ( !aktualis.torolt && !korker.benne(aktualis.azonosito) )
	  helyes(aktualis);
      }
  }

  //  Ezen keresztül lehet elerni a helyes metodust. Kiküszöböli a köröket.
  /**
   * Ellenőrzi, hogy minden csúcshoz (p alatt) normális érték van-e rendelve.
   */
  public Vector Helyes( csucs p )
  {
    korker.removeAllElements();
    rosszak.removeAllElements();
    helyes(p);
    return rosszak;
  }

  /**
   * Eldönti, hogy adott csúcsba tovább mehet-e az adott személy 
   * (ismerve a csoportját, honnan jön ... )
   */
  public boolean mehet( String honnan, String hova, String csoport )
  {
    csucs hv=Keres(gyoker,hova);
    Calendar cal=new GregorianCalendar();
    cal.setTime( new Date() );
    String ido=cal.get(Calendar.HOUR)+":"+cal.get(Calendar.MINUTE);
    if ( ido.compareTo(hv.tol)<0 || ido.compareTo(hv.ig)>0 )
      return false; // itt lehet gond, mert ez lexigrafikusan hasonlit össze

    if ( hv.elozo.benne(honnan) )
      if ( csoport.equals(hv.csoport) || hv.csoport.equals("all") || 
	   ( hv.csoport.equals("diak") && csoport.equals("tanar")) )
	{
	  hv.tortenet.addElement(csoport+"--"+ido);
	  return true;
	}
      else
	return false;
    else
      return false;
  }

  /**
   * Bellman-Ford algoritmus min. utkereseshez. Algoritmusok konyv 450-...
   */

  /**
   * az összes csúcson beállítja a min. utkereseshez a kezdeti allapotokat,
   * megszamolja a csúcsokat, legyartja az eleket
   */
  private void efk( csucs p )
  {
    p.utinit(); // ez itt beállítja a kezdeti értékeit a csúcsnak
    ++csucsSzam;
    korker.addElement(p);

    for ( Enumeration e=p.kovetkezo.elements(); e.hasMoreElements(); )
      {
	aktualis=(csucs)e.nextElement();
	elek.addElement(new el(p,aktualis));
	if ( !aktualis.torolt && !korker.benne(aktualis.azonosito) )
	  efk(aktualis);
      }
  }

  /**
   * Ezen keresztül lehet az efk-t meghívni. Körbefutás elkerüléséért.
   * Az összes csúcson beállítja a min. Útkereséshez a kezdeti állapotokat,
   * megszámolja a csúcsokat, legyártja az éleket.
   */
  public void EFK( csucs p )
  {
    korker.removeAllElements();
    csucsSzam=0;
    efk(getGyoker());
    p.d=0;
  }

  /**
   * Közelít eljárás. Minimumot választ.
   */
  public void kozelit( csucs u, csucs v )
  {
    if ( v.d > u.d + 1 ) // itt 1 a ket csúcs kozotti csúcs súlya
      {
	v.d=u.d+1;
	v.pi=u;
      }
  }

  /**
   * Bellman-Ford algoritmus.
   */
  public lista BF( csucs honnan, csucs hova )
  {
    EFK(honnan);
    el e;
   
    for ( int i=0; i<csucsSzam; ++i )
      for ( Enumeration ee=elek.elements(); ee.hasMoreElements(); )
	{
	  e=(el)ee.nextElement();
	  kozelit(e.p1,e.p2);
	}

    csucs p=hova;
    lista v=new lista(30);
    while ( !p.azonosito.equals(honnan.azonosito) )
      {
	v.insertElementAt(p,0);
	p=p.pi;
      }
    v.insertElementAt(p,0);
    return v;
  }
}

/**
 * Ket csúcsot köt össze, él osztály.
 */
class el
{
  csucs p1,p2;

  public el( csucs p1, csucs p2 )
  {
    this.p1=p1;
    this.p2=p2;
  }
}