// solve.cpp 0.6
// author: elephant <elephant_AT_linux.net.cn>

// code for general searching

#define HEAP_SIZE (1024 * 1024 * 1)

#define LEFT(x) (x * 2 + 1)
#define RIGHT(x) (x * 2 + 2)
#define ROOT(x) ((x - 1) / 2)

#define MOVE_NOWAY -1
#define MOVE_INVALID -2

#define SOLV_IMPOSSIBLE -1
#define SOLV_NOMEMORY -2

struct NodeInfo
{
	NodeInfo() :f(0), is_open(-1) { }

	int f;
	int is_open;
};

int orderDown(NodeInfo *infos, int *opens, const int &open_used, int root)
{
	int r = opens[root];
	while (true)
	{
		int left = LEFT(root), right = RIGHT(root);
		if (right < open_used)
		{
			if ((infos[opens[left]].f <= infos[opens[right]].f)
				&& (infos[opens[left]].f < infos[r].f))
			{
				opens[root] = opens[left];
				infos[opens[root]].is_open = root;
				root = left;
			}
			else if ((infos[opens[right]].f <= infos[opens[left]].f)
				&& (infos[opens[right]].f < infos[r].f))
			{
				opens[root] = opens[right];
				infos[opens[root]].is_open = root;
				root = right;
			}
			else break;
		}
		else if (left < open_used)
		{
			if (infos[opens[left]].f < infos[r].f)
			{
				opens[root] = opens[left];
				infos[opens[root]].is_open = root;
				root = left;
			}
			else break;
		}
		else break;
	}
	opens[root] = r;
	infos[opens[root]].is_open = root;
	return root;
}

int orderUp(NodeInfo *infos, int *opens, const int &open_used, int leaf)
{
	int l = opens[leaf];
	while (leaf > 0)
	{
		int root = ROOT(leaf);
		if (infos[l].f < infos[opens[root]].f)
		{
			opens[leaf] = opens[root];
			infos[opens[leaf]].is_open = leaf;
			leaf = root;
		}
		else break;
	}
	opens[leaf] = l;
	infos[opens[leaf]].is_open = leaf;
	return leaf;
}

template <class Node>
int key(Node *nodes, const int &hash_size, const Node &n)
{
	int start = abs(n.hash()) % hash_size;
	int i;
	for (i = start; i < hash_size; i ++)
		if ((nodes[i] == n) || (nodes[i].isNull())) return i;
	for (i = 0; i < start; i ++)
		if ((nodes[i] == n) || (nodes[i].isNull())) return i;
	return -1;
}

template <class Node>
int solve(Node *nodes, int hash_size, Node s)
{
	NodeInfo *infos = new NodeInfo[hash_size];
	int hash_used = 0;
	int *opens = new int[HEAP_SIZE];
	int open_used = 0;

	int return_value = SOLV_IMPOSSIBLE;

	int k0 = key(nodes, hash_size, s);
	nodes[k0] = s;
	nodes[k0].from = -1;
	hash_used ++;
	infos[k0].f = s.h();
	infos[k0].is_open = 0;
	opens[0] = k0;
	open_used = 1;

	while (open_used > 0)
	{
		int k = opens[0];
		opens[0] = opens[open_used - 1];
		open_used --;
		if (open_used > 0) orderDown(infos, opens, open_used, 0);
		infos[k].is_open = -1;

		Node n = nodes[k];
		if (n.isTarget()) { return_value = k; goto solve_end; }

		for (int i = 0; i < n.possibleMoves(); i ++)
		{
			Node m = n;
			if (m.move(i) != 0) continue;
			int fm = infos[k].f - n.h() + 1 + m.h();
			int km = key(nodes, hash_size, m);
			if (km == -1) { return_value = SOLV_NOMEMORY; goto solve_end; }
			else if (nodes[km].isNull())
			{
				nodes[km] = m;
				nodes[km].from = k;
				infos[km].f = fm;
				infos[km].is_open = open_used;
				hash_used ++;
				if (hash_used >= hash_size * 0.9) { return_value = SOLV_NOMEMORY; goto solve_end; }
				if (open_used >= HEAP_SIZE) { return_value = SOLV_NOMEMORY; goto solve_end; }
				opens[open_used] = km;
				open_used ++;
				orderUp(infos, opens, open_used, open_used - 1);
// debug code begin
				if (hash_used % 1024 == 0)
				{
					printf("\rhash used: %d  open used: %d  ", hash_used, open_used);
					fflush(stdout);
				}
// debug code end
			}
			else if ((infos[km].is_open >= 0) && (fm < infos[km].f))
			{
				nodes[km].from = k;
				infos[km].f = fm;
				orderUp(infos, opens, open_used, infos[km].is_open);
			}
			else if ((infos[km].is_open == -1) && (fm < infos[km].f))
			{
				if (open_used >= HEAP_SIZE) { return_value = SOLV_NOMEMORY; goto solve_end; }
				nodes[km].from = k;
				infos[km].f = fm;
				infos[km].is_open = open_used;
				opens[open_used] = km;
				open_used ++;
				orderUp(infos, opens, open_used, open_used - 1);
			}
		}
	}

solve_end:
// debug code begin
	printf("\n\n");
// debug code end

	delete []infos;
	delete []opens;

	return return_value;
}