package Projet;
import java.util.*;
import java.lang.Math;


public class Heuristique1 extends ProblemZ2
{
	private LinkedList<Vector2> states;
	private LinkedList<Vector2> exploredStates;
	private LinkedList<Vector2> toExploreState;
	private LinkedList<Vector2> nextIteration;
	private LinkedList<Vector2> actions;
	private LinkedList<Vector2> path;
	private Vector2 startingState;
	private Vector2 finalState;

	//Constructor
	public Heuristique1(Vector2 startingState, Vector2 finalState, LinkedList<Vector2> actions)
	{
		this.states = new LinkedList<Vector2>();
		this.exploredStates = new LinkedList<Vector2>();
		this.toExploreState = new LinkedList<Vector2>();
		this.nextIteration = new LinkedList<Vector2>();
		this.actions = new LinkedList<Vector2>();
		this.path = new LinkedList<Vector2>();
		this.startingState = startingState;
		this.finalState = finalState;
		this.states.add(startingState);
		this.toExploreState.add(startingState);
		this.actions = actions;
	}

	public LinkedList<Vector2> solveBFS(int maxIteration)
	{

		float computeLimit = 0;
		for(int j = 0 ; j < this.actions.size() ; j++)
			computeLimit += this.actions.get(j).magnitude();
		computeLimit += this.startingState.distance(this.finalState);

		int limit = (int) (Math.ceil(computeLimit));
				System.out.println(limit);
		for(int i = 1 ; i<= maxIteration ; i++)
		{
			while(this.toExploreState.size() != 0)
			{
				Vector2 e = this.toExploreState.get(0);

				//Check if final state
				if(e.equals(this.finalState))
				{
					while(e.parent() != null)
					{
						this.path.add(0,e);
						e = e.parent();
					}
					this.path.add(0,this.startingState);
					this.states.add(e);
					return this.path;
				}
			
				//Creates successors
				for(int j = 0 ; j < this.actions.size() ; j++)
				{
					Vector2 s = suc(e,this.actions.get(j));
					this.states.add(s);
					//System.out.println(this.toExploreState.contains(s));	
					if((!contains(this.exploredStates,s) && !contains(this.toExploreState,s)))
					{
						//If in circle, treat now, else at next dichotomy
						if(s.distance(this.finalState) <= limit)
						{
							this.toExploreState.add(s);
						}
						else
						{
							this.nextIteration.add(s);
						}
					}
				}
				this.exploredStates.add(e);
				this.toExploreState.remove(0);
			}
			//Dichotomy
			limit *= 2;
			this.toExploreState.addAll(this.nextIteration);
		}
		return null;
	}


}