// Beispiel Klasse fuer FluSuServlet
// WWW & Servlets
// Fachgruppe Softwaretechnik
// Uwe Poborski 14.04.99

// FlugGraph.java
// Darstellung eines Graphen von Flughaefen als Knoten und Fluegen als Kanten
// Darstellung von Flughafen als verkettete Liste mit Listen von Fluegen
// Darstellung von Fluegen als verkettete Liste mit Zielflughaefen
//
// Knoten und Kanten enthalten Gewichtungen und Farben
// fuer die Suche nach dem Algorythmus von Dykstra, 
// der von einen Knoten die optimalen Wege zu allen anderen Knoten findet
//
// zu erledigen:
//   Anschlusszeiten muessen beachtet werden (Weiterflug nicht vor Ankunft)
//   die Addition der Flugzeiten muss eine Optimierung mit Wartezeiten erlauben

// benoetigte Klassen:
//   GraphDatei
//   Flughafen
//   Flug
//   Flugzeug
//   ZeitAngabe

import java.io.*;

class FlugGraph
{
   static final int  FARBLOS  = 0,
                     GELBEFARBE  = 1,
                     ROTEFARBE   = 2,
                     GRUENEFARBE = 2;
   static final long  MAXG = 2147483647;

   protected Flughafen Graph = null,
                     Von = null,
                     Nach = null;
   public Flughafen Verbindung = null;
   public float GesPreis;
   public ZeitAngabe GesZeit = null,
                     ZeitzumUmsteigen = new ZeitAngabe(10);
      
   private boolean PreisOderZeit = false;
      
   public FlugGraph()
   {
   }
   
   public FlugGraph(String VonName, String NachName, boolean PoZ, String Pfad)
   {
      Graph = lesenGraph(Pfad);
      if (Graph != null)
      {
         Von = Graph.gibFlughafenMitName(VonName);
         Nach = Graph.gibFlughafenMitName(NachName);
         PreisOderZeit = PoZ;
      }
   }
   
   public Flughafen lesenGraph(String DateiName)
   {
      GraphDatei GD = new GraphDatei();
      GD.lesen(DateiName);
      return GD.HDatei.Flughaefen;
   }
   
   public void erstellVerbindung()
   {
      Flughafen KZ = Nach,
                WL = null;
      Flug PZ = null, VZ = null;
      if (KZ.Farbe == GRUENEFARBE)
      {
         GesZeit = new ZeitAngabe();
         GesPreis = 0.0f;
         WL = new Flughafen(Von.Name, Von.Kuerzel, Von.RelZeit);
         while (KZ != Von)
         {
            PZ = gibrotFlugNachFlughafen(KZ);
            if (PZ != null)
            {
               if (WL.Fluege == null)
                  WL.Fluege = new Flug(PZ.Nummer, PZ.Hafen, PZ.Maschine);
               else
                  WL.Fluege = WL.Fluege.eingefuegt(new Flug(PZ.Nummer, PZ.Hafen, PZ.Maschine));
               WL.Fluege.Anfang = PZ.Anfang;
               WL.Fluege.Ende = PZ.Ende;
               GesPreis += PZ.gibPreis(Flug.TC);
               GesZeit.addieren(PZ.gibDauer());
               if (VZ != null)
               {
                  ZeitAngabe ZA = new ZeitAngabe(VZ.Anfang);
                  ZA.subtrahieren(PZ.Ende);
                  GesZeit.addieren(ZA);
               }
            }
            VZ = PZ;   
            KZ = gibgruenenVorgaenger(KZ);
         }
      }
      Verbindung = WL;
   }
      
   public boolean suchen()
   {
      if (Von == null || Nach == null)
         return false;
      Flughafen KZ = null, NZ = null;
      Flug PZ = null;
      ZeitAngabe ZA = new ZeitAngabe();
      float Dist = 0;
      
      Von.Farbe = GELBEFARBE;
      Von.Distanz = 0;
      while ((KZ = kleinsterGelber()) != null)
      {
         KZ.Farbe = GRUENEFARBE;
         PZ = KZ.Fluege;
         while (PZ != null)
         {
            if (PZ.Farbe != GELBEFARBE)
            {
               NZ = PZ.Hafen;
               Dist = KZ.Distanz + PZ.gibGewicht(PreisOderZeit);
               if (NZ.Farbe == FARBLOS)
               {
                  PZ.Farbe = ROTEFARBE;
                  NZ.Farbe = GELBEFARBE;
                  NZ.Distanz = Dist;
               }
               else // if (NZ.Farbe == FARBLOS)
               {
                  if (NZ.Farbe == GELBEFARBE)
                  {
                     if (NZ.Distanz > Dist)
                     {
                        gibrotFlugNachFlughafen(NZ).Farbe = GELBEFARBE;
                        PZ.Farbe = ROTEFARBE;
                        NZ.Distanz = Dist;
                     }                           
                     else // if (NZ.Distanz > KZ.Distanz + PZ.gibGewicht(PreisOderZeit))
                        PZ.Farbe = GELBEFARBE;
                  } // if (NZ.Farbe == GELBEFARBE)
               } // if (NZ.Farbe == FARBLOS)
            }// if (PZ.Farbe != GELBEFARBE)               
            PZ = PZ.Naechster;
         } // while (PZ != null)
      } // while ((KZ = kleinsterGelber()) != null)
      if (Nach.Farbe == GRUENEFARBE)
         return true;
      else
         return false;
   }
   
   private Flughafen kleinsterGelber()
   {
      float D = MAXG;
      Flughafen KZ  = Graph,
                MZ = null;
      while (KZ != null)
      {
         if (KZ.Farbe == 1 && KZ.Distanz < D)
         {
            MZ = KZ;
            D = KZ.Distanz;
         }
         KZ = KZ.Naechster;
      }
      return MZ;
   }
   
   private Flug gibrotFlugNachFlughafen(Flughafen SuchHafen)
   {
      Flughafen KZ = Graph;
      Flug PZ = null;
      while (KZ != null)
      {
         if (KZ.Farbe == GRUENEFARBE)
         {
            PZ = KZ.Fluege;
            while (PZ != null)
            {
               if (PZ.Hafen == SuchHafen && PZ.Farbe == ROTEFARBE) 
                  return PZ;
               else
                  PZ = PZ.Naechster;                     
            }
         }
         KZ = KZ.Naechster;
      }                
      return null;
   }
   
   private Flughafen gibgruenenVorgaenger(Flughafen SuchHafen)
   {      
      Flughafen KZ = Graph;
      Flug PZ = null;
      while (KZ != null)
      {
         if (KZ.Farbe == GRUENEFARBE)
         {
            PZ = KZ.Fluege;
            while (PZ != null)
            {
               if (PZ.Hafen == SuchHafen && PZ.Farbe == ROTEFARBE) 
                  return KZ;
               else
                  PZ = PZ.Naechster;                     
            }
         }
         KZ = KZ.Naechster;
      }                
      return null;
   }
   
}