package labyrinth;

import java.util.LinkedList;
import java.util.Stack;

import sun.misc.Queue;

public class Suche {

	LabyrinthLoader loader;
	MyCell[][] labyrinth;
	MyCell start;

	public Suche() {
		loader = new LabyrinthLoader();
		labyrinth = loader.getLabyrinth();
		start = loader.getStart();
		Tiefensuchen2(start);
	}

	/*
	 * Erläuterungen: Das Labyrinth ist ein zweidimensionales Array bestehend aus
	 * Zellen der Klasse MyCell. Von der Klasse MyCell können z.B. folgende Methoden
	 * verwendet werden: istWandOben() : liefert true zurück, wenn der Weg nach oben
	 * versperrt ist istWandLinks() : liefert true zurück, wenn der Weg nach links
	 * versperrt ist istBesucht() : liefert true zurück, wenn die Zelle bereits
	 * besucht wurde setBesucht() : markiert die aktuelle Zelle als besucht
	 * istZiel() : liefert true zurück, wenn die aktuelle Zelle das Ziel ist getX()
	 * : liefert die x-Koordinate der aktuellen Zelle im Labyrinth zurück gety() :
	 * liefert die y-Koordinate der aktuellen Zelle im Labyrinth zurück getPos() :
	 * liefert die Position (x- und y-Koordinate)der aktuellen Zelle im Labyrinth
	 * zurück (siehe Klasse Position)
	 *
	 */

	/*
	 * Hilfe zur Breitensuche:
	 *
	 * Zur Breitensuche ist eine Warteschlange (Queue) hilfreich In Java gibt es
	 * hierfür z.B. die vorbereitete Klasse Queue
	 *
	 * ES KANN ABER AUCH DIE KLASSE LINKEDLIST als Queue benutzt werden:
	 *
	 * Einige Methoden der Klasse LinkedList:
	 *
	 * offer(<Element>) oder auch add(<Element>): fügt ein neues Element an das Ende
	 * der Liste an poll() : liefert das erste Element in der Liste zurück und
	 * löscht es aus der Liste isEmpty() : liefert true zurück, wenn die Liste leer
	 * ist
	 *
	 */

	public void suchen() {
		LinkedList<MyCell> q = new LinkedList<MyCell>();
		 q.add(start);

		while (!q.isEmpty()) {
			MyCell b= q.poll();
			if(b.istZiel()) {
				return;
			}
			b.setBesucht();

			if (b.istWandOben() == false && b.getY()-1>= 0 && labyrinth[b.getX()][b.getY() - 1].istBesucht() == false ) {
				q.add(labyrinth[b.getX()][b.getY() - 1]);
			}
			if (b.istWandRechts() == false && b.getX()+1<= labyrinth.length && labyrinth[b.getX() + 1][b.getY()].istBesucht() == false) {
				q.add(labyrinth[b.getX() + 1][b.getY()]);
			}
			if (b.istWandUnten() == false && b.getY()+1<= labyrinth.length && labyrinth[b.getX()][b.getY() + 1].istBesucht() == false) {
				q.add(labyrinth[b.getX()][b.getY() + 1]);
			}
			if (b.istWandLinks() == false && b.getX()-1>= 0 && labyrinth[b.getX() - 1][b.getY()].istBesucht() == false) {
				q.add(labyrinth[b.getX() - 1][b.getY()]);
			}
			try {
				Thread.sleep(25);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}


		}

	}
	public void Tiefensuchen() {
		Stack<MyCell> q = new Stack<MyCell>();
		 q.add(start);

		while (!q.isEmpty()) {
			MyCell b= q.pop();
			if(b.istZiel()) {
				return;
			}
			b.setBesucht();

			if (b.istWandOben() == false && b.getY()-1>= 0 && labyrinth[b.getX()][b.getY() - 1].istBesucht() == false ) {
				q.push(labyrinth[b.getX()][b.getY() - 1]);
			}
			if (b.istWandRechts() == false && b.getX()+1<= labyrinth.length && labyrinth[b.getX() + 1][b.getY()].istBesucht() == false) {
				q.push(labyrinth[b.getX() + 1][b.getY()]);
			}
			if (b.istWandUnten() == false && b.getY()+1<= labyrinth.length && labyrinth[b.getX()][b.getY() + 1].istBesucht() == false) {
				q.push(labyrinth[b.getX()][b.getY() + 1]);
			}
			if (b.istWandLinks() == false && b.getX()-1>= 0 && labyrinth[b.getX() - 1][b.getY()].istBesucht() == false) {
				q.push(labyrinth[b.getX() - 1][b.getY()]);
			}
			try {
				Thread.sleep(25);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}


		}

	}
	public void Tiefensuchen2(MyCell b) {
		LinkedList<MyCell> q = new LinkedList<MyCell>();
		 q.add(b);
		while (!b.istZiel()) {


			b.setBesucht();

			if (b.istWandOben() == false && b.getY()-1>= 0 && labyrinth[b.getX()][b.getY() - 1].istBesucht() == false ) {
				q.add(labyrinth[b.getX()][b.getY() - 1]);
				this.Tiefensuchen2(labyrinth[b.getX()][b.getY() - 1]);
			}
			else if (b.istWandRechts() == false && b.getX()+1<= labyrinth.length && labyrinth[b.getX() + 1][b.getY()].istBesucht() == false) {
				q.add(labyrinth[b.getX() + 1][b.getY()]);
				this.Tiefensuchen2(labyrinth[b.getX() + 1][b.getY()]);
			}
			else if (b.istWandUnten() == false && b.getY()+1<= labyrinth.length && labyrinth[b.getX()][b.getY() + 1].istBesucht() == false) {
				q.add(labyrinth[b.getX()][b.getY() + 1]);
				this.Tiefensuchen2(labyrinth[b.getX()][b.getY() + 1]);
			}
			else if (b.istWandLinks() == false && b.getX()-1>= 0 && labyrinth[b.getX() - 1][b.getY()].istBesucht() == false) {
				q.add(labyrinth[b.getX() - 1][b.getY()]);
				this.Tiefensuchen2(labyrinth[b.getX() - 1][b.getY()]);
			}
			else {
				q.poll().Tiefensuchen2(b);
			}
			try {
				Thread.sleep(25);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}


		}
		return;

	}



	public static void main(String[] args) {
		new Suche();

	}

}