package atomicstryker.minions.common.pathfinding;

import java.util.ArrayList;

import net.minecraft.src.World;

/**
 * Runnable worker class for finding an AstarPath
 * is prone to crashes when no path can be found.
 * 
 * @author AtomicStryker
 */

public class AStarWorker extends Thread
{
	private AStarPath boss;
	private boolean isRunning = false;
	
	public ArrayList closedNodes = new ArrayList();
	private AStarNode startNode;
	private AStarNode targetNode;
	private boolean searchMode;
	private World worldObj;

	private long startingTime;
	private int checkedCubes = 0;

	public int maxCheckedCubes = 1000;
	public int maxSize = 20;
	public int maxSizeSq = maxSize*maxSize;
	public int maxSizeSqMinusOne = maxSizeSq-1;

	private AStarNode[] openList = new AStarNode[maxSizeSq];
	private int addedItems = 1;
	
	public AStarWorker(AStarPath creator)
	{
		boss = creator;
	}

	@Override
	public void run()
	{
		if (isRunning) return;
		isRunning = true;
		
		ArrayList result = null;
		result = getPath(startNode, targetNode, searchMode);

		if (result == null)
		{
			boss.OnNoPathAvailable();
		}
		else
		{
			boss.OnFoundPath(result);
		}
	}

	public void setup(World winput, AStarNode start, AStarNode end, boolean mode)
	{
		worldObj = winput;
		startNode = start;
		targetNode = end;
		searchMode = mode;
	}

	public void resetSearch()
	{
		closedNodes = new ArrayList();
		checkedCubes = 0;
		openList = new AStarNode[maxSizeSq+1];
		addedItems = 1;
	}

	public ArrayList getPath(int startx, int starty, int startz, int destx, int desty, int destz, boolean searchMode)
	{
		AStarNode starter = new AStarNode(startx, starty, startz, 0);
		AStarNode finish = new AStarNode(destx, desty, destz, -1);;

		return getPath(starter, finish, searchMode);
	}

	public ArrayList getPath(AStarNode start, AStarNode end, boolean searchMode)
	{
		openList[1] = start;
		startingTime = System.currentTimeMillis();

		targetNode = end;
		start.f_distanceToGoal = AStarStatic.getDistanceBetweenNodes(start, targetNode);

		AStarNode current = start;

		while(!current.equals(end))
		{			
			deleteLowestValueInHeap();
			closedNodes.add(current);

			checkPossibleLadder(current);
			getNextCandidates(current, searchMode);

			if (addedItems == 0 || addedItems == maxSizeSqMinusOne || Thread.interrupted() || checkedCubes >= maxCheckedCubes)
			{
				//System.out.println("Path search stopped, checkedCubes: "+checkedCubes+", interrupted: "+Thread.interrupted());
				return null;
			}

			current = openList[1];
		}

		ArrayList foundpath = new ArrayList();
		foundpath.add(current);
		while (current != start)
		{
			foundpath.add(current.parent);
			current = current.parent;
		}
		
		return foundpath;
	}

	private void addToBinaryHeap(AStarNode input)
	{
		addedItems++;
		if (addedItems >= maxSizeSqMinusOne)
		{
			Thread.yield();
			return;
		}
		
		openList[addedItems] = input;
		sortBinaryHeap();

		checkedCubes++;
	}

	private void sortBinaryHeap()
	{
		sortBinaryHeapFromValue(addedItems);
	}

	private void sortBinaryHeapFromValue(int m)
	{
		AStarNode swap;
		while (m > 1)
		{
			if (openList[m].f_distanceToGoal <= openList[m/2].f_distanceToGoal)
			{
				swap = openList[m/2];
				openList[m/2] = openList[m];
				openList[m] = swap;
				m = m/2;
			}
			else
			{
				break;
			}
		}
	}

	private void deleteLowestValueInHeap()
	{
		AStarNode swap;
		openList[1] = openList[addedItems];
		addedItems --;

		int v = 1;
		int u;
		for(;;)
		{
			u = v;
			if (2*u+1 <= addedItems)
			{
				if (openList[u].f_distanceToGoal >= openList[2*u].f_distanceToGoal)
				{
					v = 2*u;
				}
				if (openList[v].f_distanceToGoal >= openList[2*u+1].f_distanceToGoal)
				{
					v = 2*u+1;
				}
			}
			else if(2*u <= addedItems)
			{
				if (openList[u].f_distanceToGoal >= openList[2*u].f_distanceToGoal)
				{
					v = 2*u;
				}
			}

			if (u != v)
			{
				swap = openList[u];
				openList[u] = openList[v];
				openList[v] = swap;
			}
			else
			{
				break;
			}
		}
	}

	private void checkPossibleLadder(AStarNode parent)
	{
		int x = parent.x;
		int y = parent.y;
		int z = parent.z;

		if (AStarStatic.isLadder(worldObj.getBlockId(x, y, z)))
		{

			AStarNode ladder = null;
			if (AStarStatic.isLadder(worldObj.getBlockId(x, y+1, z)))
			{
				ladder = new AStarNode(x, y+1, z, parent.g_BlockDistToStart+1, parent);
				ladder.f_distanceToGoal = AStarStatic.getDistanceBetweenNodes(ladder, targetNode);

				if (!tryToFindExistingHeapNode(parent, ladder))
				{
					addToBinaryHeap(ladder);
				}
			}
			if (AStarStatic.isLadder(worldObj.getBlockId(x, y-1, z)))
			{
				ladder = new AStarNode(x, y-1, z, parent.g_BlockDistToStart+1, parent);
				ladder.f_distanceToGoal = AStarStatic.getDistanceBetweenNodes(ladder, targetNode);

				if (!tryToFindExistingHeapNode(parent, ladder))
				{
					addToBinaryHeap(ladder);
				}
			}
		}
	}

	public void getNextCandidates(AStarNode parent, boolean searchMode)
	{
		int x = parent.x;
		int y = parent.y;
		int z = parent.z;
		int dist = parent.g_BlockDistToStart;

		int[][] c = searchMode ? AStarStatic.candidates_allowdrops : AStarStatic.candidates;

		AStarNode check;
		for (int i = 0; i < c.length; i++)
		{
			check = new AStarNode(x+c[i][0], y+c[i][1], z+c[i][2], dist+c[i][3], parent);
			check.f_distanceToGoal = AStarStatic.getDistanceBetweenNodes(check, targetNode);

			if (closedNodes.contains(check))
			{
				((AStarNode) closedNodes.get(closedNodes.indexOf(check))).updateDistance(check.g_BlockDistToStart, parent);
			}
			else if (!tryToFindExistingHeapNode(parent, check))
			{
				if (AStarStatic.isViable(worldObj, check, c[i][1]))
				{
					addToBinaryHeap(check);
				}
			}
		}
	}

	private boolean tryToFindExistingHeapNode(AStarNode parent, AStarNode checkedOne)
	{
		for (int i = 1; i <= addedItems; i++)
		{
			if (openList[i] != null && openList[i].equals(checkedOne))
			{
				if (openList[i].updateDistance(checkedOne.g_BlockDistToStart, parent))
				{
					sortBinaryHeapFromValue(i);
					return true;
				}
				else
				{
					return false;
				}
			}
		}

		return false;
	}
}