import java.awt.*;

public class StadtArray
{
   Stadt[] stadt;
   int anzahl;
   
    /**
     * Konstruktor für Objekte der Klasse StadtArray.
     * Der Array enthaelt maximal 32 Staedte;
     */
    public StadtArray()
    {
        stadt = new Stadt[32];
        anzahl = 0; // Array ist zunaechst leer
    }

    /**
     * Methode zum Erzeugen einer Stadtliste mit 17 Staedten
     */
    public void erzeuge()
    {
    // Erstmal die Staedte in die Liste aufnehmen, aber noch nicht
    // zu einer Tour verbinden
       stadt[ 0] = new Stadt( 0,  1.23,  3.03,"Bohmte");
       stadt[ 1] = new Stadt( 1,  7.00,  2.61,"Espelkamp");
       stadt[ 2] = new Stadt( 2,  7.00,  4.09,"Luebbecke");
       stadt[ 3] = new Stadt( 3, 12.42,  5.68,"Minden");
       stadt[ 4] = new Stadt( 4, 13.58,  3.53,"Petershagen");       
       stadt[ 5] = new Stadt( 5, 11.08,  7.66,"Bad Oeynhausen");      
       stadt[ 6] = new Stadt( 6, 12.06,  9.21,"Vlotho");
       stadt[ 7] = new Stadt( 7,  8.11, 10.76,"Herford");
       stadt[ 8] = new Stadt( 8,  7.90,  1.85,"Hille");                 
       stadt[ 9] = new Stadt( 9,  1.69,  8.22,"Melle");
       stadt[10] = new Stadt(10,  2.12,  4.37,"Bad Essen");
       stadt[11] = new Stadt(11,  4.80,  4.97,"Pr. Oldendorf");
       stadt[12] = new Stadt(12,  7.00,  0.85,"Rahden");
       stadt[13] = new Stadt(13,  3.56,  1.55,"Stemwede");
       stadt[14] = new Stadt(14,  9.56, 11.78,"Bad Salzuflen");       
       stadt[15] = new Stadt(15,  5.22, 13.72,"Bielefeld");  
       stadt[16] = new Stadt(16,  6.28,  8.43,"Buende");         
       anzahl    = 17;
       
    // Jetzt die erste Tour erzeugen, indem die Staedte in der Reihenfolge
    // verbunden werden, wie sie in der Liste stehen
       for (int i=0; i < anzahl; i++)
          stadt[i].next = i+1;
       stadt[anzahl-1].next = 0;
    }
    
    private double entfernung(int s1, int s2)
    {
       double dx, dy, dx2, dy2;
       
       dx = stadt[s1].xPos - stadt[s2].xPos;
       dy = stadt[s1].yPos - stadt[s2].yPos;
       dx2 = dx * dx;
       dy2 = dy * dy;
       
       return Math.sqrt(dx2 + dy2);    
    }
   
    public int naechsteStadt(int s)  
    {
    // Wir setzen das Minimum auf einen unwirklich hohen Wert
       double entf, min = 100000;
       int    index = -1;
       
    // Dann fangen wir mit der ersten Stadt der Liste an
       int start = 0;
       
    // HIER BEGINNT DIE HAUPTSCHLEIFE
       while (start < anzahl)
       {
        // Wir suchen die erste Stadt, die noch nicht in der Tour ist.
           while ((start < anzahl) && stadt[start].inTour) start++;
           
           if (start >= anzahl) 
           {               
               break;
           }
           
        // Die Entfernung zu dieser Stadt wird als Minimum gespeichert
           entf = entfernung(s,start);
           if ((start != s) && (entf < min))
           {
               min = entf;
               index = start;
           }
           
        // Jetzt muessen wir die anderen Staedte untersuchen, die noch nicht in 
        // der Tour enthalten sind.
           start++;
        }           
        return index;
    }
    
    /**
     * Berechnung einer Tour nach dem nearest neighbour-Algorithmus
     */    
    public void nearestNeighbour()
    {
    // Wieder starten wir mit der ersten Stadt der Liste
       int s = 0;  
       
    // Jetzt muss anzahl-1 mal die jeweils naechste Stadt gesucht werden
       for (int i=0; i<anzahl-1; i++)
       {
          stadt[s].inTour = true;           // Stadt in Tour aufnehmen
          stadt[s].next = naechsteStadt(s); // Nachfolger der Stadt ermitteln
          s = stadt[s].next;                // zum Nachfolger gehen und weitermachen&hellip;
       }   
       stadt[s].inTour = true;              // Letzte Stadt der Liste in Tour aufnehmen
       stadt[s].next = 0;                   // und mit der ersten Stadt verbinden
    }
    
    
    public void paint(Graphics g)
    /**
     * Methode zum Anzeigen der Tour
     */
    {
      int next = 0;
      int x1,y1,x2,y2;
      
      do {
          stadt[next].paint(g);     // stadt[0] ist immer die erste Stadt
          x1 = stadt[next].xPos;
          y1 = stadt[next].yPos;
          next = stadt[next].next;  // wo ist die naechste Stadt der Tour?   
          x2 = stadt[next].xPos;
          y2 = stadt[next].yPos;
          g.drawLine(x1,y1,x2,y2);
      } 
      while (next != 0);            // sind wir schon wieder bei der ersten Stadt
                                    // angekommen?
    }
}