public class Dijkstra
{
  private List knoten = new List();
  private List rand = new List();
  private Graph mygraph;
  //länge??

  public Dijkstra(Graph pgraph)
  {
    mygraph = pgraph;
  }

  public List starter(GraphNode pstart, GraphNode ziel)
  {
    DijkstraNode start = new DijkstraNode(pstart, 0.0, pstart);
    if(pstart != ziel)
    {
      mygraph.resetMarks();
      kuerzesterWeg(start, ziel);
    }
    //knoten auslesen
    return wegauslesen(pstart, ziel);
  }

  private void kuerzesterWeg(DijkstraNode startKn, GraphNode zielKn)
  {
    while(!mygraph.allNodesMarked())
    {
      startKn.getvorgängerKn().mark();                                            // markiere Vorgängerknoten
      knoten.append(startKn);
      List nachbar = mygraph.getNeighbours(startKn.getknoten());                  // Nachbarliste des Knotens
      nachbar.toFirst();
      while(nachbar.hasAccess())
      {
        if(!((GraphNode) nachbar.getObject()).isMarked())                         // Nachbar unmarkiert?
        {
          double weight = startKn.getgewicht() + gewicht(startKn.getknoten(),(GraphNode) nachbar.getObject());   // Gesamtgewicht
          DijkstraNode DN = new DijkstraNode(((GraphNode) nachbar.getObject()), weight, startKn.getknoten()) ;     // neuer Dijkstranode
          rand = sort_insert(rand,DN);                                            // nach Gewicht sortiert eingefügt in den Rand
          System.out.println("sortiert eingefügt: " + DN.getknoten().getName() + " mit dem Gewicht: " + weight);
          ((GraphNode) nachbar.getObject()).mark();
        }
        nachbar.next();
      }
      rand.toFirst();
      if(rand.hasAccess())
      {
        DijkstraNode helfer = new DijkstraNode((DijkstraNode) rand.getObject());      // DijkstraNode mit dem kleinsten Gewicht aus dem Rand holen
        rand.remove();                                                                // und aus dem Rand löschen
        System.out.println("rekursiver Aufruf: " + helfer.getknoten().getName());
        kuerzesterWeg(helfer, zielKn);                                                // rekursiver Aufruf
      }
    }
  }

  private List wegauslesen(GraphNode start, GraphNode ziel)
  {
    List weg = new List();
    DijkstraNode dntemp = new DijkstraNode(ziel, 0.0, start);
    GraphNode gntemp = new GraphNode("");
    knoten.toLast();
    while(knoten.hasAccess() || ziel == start)
    {
      dntemp = (DijkstraNode) knoten.getObject();
      gntemp = (GraphNode)dntemp.getknoten();
      if(gntemp.getName().equals(ziel.getName()))
      {
        weg.toFirst();
        weg.insert(gntemp);
        ziel = dntemp.getvorgängerKn();
      }
      knoten.remove();
      knoten.toLast();
    }
    return weg;
  }
  
  
  private double gewicht(GraphNode startKn, GraphNode zielKn)
  {
    if(startKn!=zielKn)
    {
      double gewicht = mygraph.getEdgeWeight(startKn,zielKn);
      return gewicht;
    }
    return 0;
  }
  
  
  private List sort_insert(List prand, DijkstraNode pDN)
  {
    prand.toFirst();            //  springe an den Anfang der Liste
    boolean eingefuegt = false;
    
    if(prand.isEmpty())        // Falls die Liste leer ist
    {
      prand.append(pDN);      System.out.println("1.objekt im rand");
      eingefuegt = true;
    }
    else                      // falls die Liste nicht leer ist
    {
      while (!eingefuegt && prand.hasAccess())
      {
        DijkstraNode aktuelleDN = (DijkstraNode) prand.getObject();
        if(pDN.getknoten() == aktuelleDN.getknoten())
        {
          System.out.println("2 knoten gleich");
          if(pDN.getgewicht() > aktuelleDN.getgewicht())
          {
            eingefuegt = true;     // wenn der schon vorhandene DN ein kleineres Gewicht hat, brauch man nix mehr tun
            System.out.println("vorhandener Knoten hat kleineres Gewicht");
          }
          else
          {
            prand.remove();       // andernfalls: vorhandenen DN löschen und später pDN sortiert einfügen
            System.out.println("vorhandener Knoten gelöscht");
          }
        }
        prand.next();
      }
      
      prand.toFirst();
      
      while (!eingefuegt && prand.hasAccess())  //solange nicht eingefügt und nicht am Ende der Liste
      {
        DijkstraNode aktuelleDN = (DijkstraNode) prand.getObject();
        if (pDN.getgewicht() < aktuelleDN.getgewicht())
              //Falls das übergebene Gewicht kleiner als das Aktuelle (in der Liste) ist
        {
          prand.insert(pDN);   //füge die neue DijkstraNode vor der aktuellen ein
          eingefuegt = true;  // schon eingefügt
          System.out.println("neuer DN eingefügt");
        }
        else  //falls das übergebene Gewicht größer als das aktuelle ist
        prand.next();   //gehe eine Position weiter in der Liste
      }
    }
    System.out.println("jetzt sollte er was zurückgeben");
    return prand;
  }
  
  
}