/*
 * 
 * Datei:   Verarbeitung.java
 * 
 * ---------------------------------
 * 
 * Datum:           $Date: 2004/05/12 11:02:53 $
 * Autor:           Simon Tiffert 
 * Prüfungsnummer:  40
 * Firma:           T-Systems
 * eMail-Adresse:   simon.tiffert@t-systems.com
 * Version:         $Revision: 1.17 $
 * 
 * ---------------------------------
 * 
 */

package main.verarbeitung;

/**
 * Die Klasse Verarbeitung sucht einen Weg von Rösselsprüngen in der
 * angegebenen Matrix. Dazu wird die Matrix übergeben, in der die
 * einzelnen Schritte gespeichert werden.<br>
 * Hier ist der Kernalgorithmus des Programms zu finden, der das 
 * Problem löst.
 * 
 * @version $Revision: 1.17 $
 * @author Simon Tiffert
 */
public class Verarbeitung
{
  /** Feld für Matrix */
  private Matrix matrix;

  /**
   * Der Konstruktor speichert die Matrix und ruft die Rösselsprünge 
   * auf. Dabei wird abgefangen, ob die Rekursion erfolgreich war und 
   * ein Weg gefunden wurde.
   * 
   * @param matrix Zentrale Datenstruktur mit Matrix
   * @throws MatrixNotInitialisedException Matrix nicht initialisiert
   */
  public Verarbeitung(Matrix matrix)
    throws MatrixNotInitialisedException
  {
    // zentrale Datenstruktur
    this.matrix = matrix;

    // Überprüft, ob die Matrix initialisiert wurde.
    // Wenn die Verarbeitung als Modul eingebunden wird, könnte es
    // dort zu Problemen kommen
    if (!matrix.isInitialisiert())
    {
      throw new MatrixNotInitialisedException();
    }

    // Rekursiver Aufruf des Kernalgorithmus, mit Überprüfung, ob ein 
    // Weg gefunden wurde
    if (roesselSprung(1,
      matrix.getStartpunkt().getY(),
      matrix.getStartpunkt().getX()))
    {
      // markiere den Weg als gefunden
      matrix.setWegGefunden();
    }
  }

  /**
   * Diese Funktion führt das Backtracking durch.
   * Dabei wird über Rösselsprünge festgelegt, in welchen Richtungen
   * das nächste Feld gesucht wird.
   * 
   * @param zaehler Rekursionstiefe sowie aktuelle Sprunganzahl
   * @param y y-Wert der aktuellen Position
   * @param x x-Wert der aktuellen Position
   * @return ob die Rekursion erfolgreich war
   */
  private boolean roesselSprung(int zaehler, int y, int x)
  {
    // überprüfen, ob der aktuelle Punkt innerhalb der Matrix ist
    if (!matrix.isInMatrix(y, x))
    {
      return false;
    }

    // überprüfen, ob der aktuelle Punkt besetzt ist 
    if (matrix.getWert(y, x) != 0)
    {
      return false;
    }

    // setze auf die aktuelle Position den Wert von zaehler
    matrix.setWert(y, x, zaehler);

    // wenn zaehler die Maximalanzahl erreicht hat, ist die Rekursion 
    // fertig und kann mit true abgebrochen werden
    if (zaehler == matrix.getFeldAnzahl())
    {
      return true;
    }

    // Rekursionskern:

    // Richtung NNO - Nordnordost
    if (roesselSprung(zaehler + 1, y - 2, x + 1))
    {
      return true;
    }

    // Richtung ONO - Ostnordost
    if (roesselSprung(zaehler + 1, y - 1, x + 2))
    {
      return true;
    }

    // Richtung OSO - Ostsüdost
    if (roesselSprung(zaehler + 1, y + 1, x + 2))
    {
      return true;
    }

    // Richtung SSO - Südsüdost
    if (roesselSprung(zaehler + 1, y + 2, x + 1))
    {
      return true;
    }

    // Richtung SSW - Südsüdwest 
    if (roesselSprung(zaehler + 1, y + 2, x - 1))
    {
      return true;
    }

    // Richtung WSW - Westsüdwest
    if (roesselSprung(zaehler + 1, y + 1, x - 2))
    {
      return true;
    }

    // Richtung WNW - Westnordwest
    if (roesselSprung(zaehler + 1, y - 1, x - 2))
    {
      return true;
    }

    //  Richtung NNW - Nordnordost
    if (roesselSprung(zaehler + 1, y - 2, x - 1))
    {
      return true;
    }

    // es wurde kein Weg gefunden, somit besetze die aktuelle Position
    // wieder mit 0, sodass das Feld wieder als freies Feld erkannt 
    // wird.
    matrix.setWert(y, x, 0);

    // Es wurde keine Richtung gefunden    
    return false;
  }

}
