/*
 *** search.c: 汎用探索エンジン・ライブラリ ***
 *	(2004/06/21 YH)
 * * 深さ優先、広さ優先の探索機能を汎用に実現したもの。
 * * 詳細は search.txt 参照。
 */

#include "search.h"

int default_check = 0;			// 1 ならデフォールトの経路チェックを起動する
int first_only = 0;			// 1 なら最初に見つかった解だけ返す。

#ifndef MAXLINK
#define MAXLINK 1000                    // パスノードの個数
#endif

#define	INFINITY	MAXLINK		// 解の長さの最大値
static int anslen, nans;		// 最短解の長さ、個数
static void *nodes[MAXLINK];		// 状態へのポインタ配列（内部使用）

struct LINK {				// リンク構造体
	struct LINK *path, *next;	// path は経路、next は探索リストへのポインタ
	void *node;			// 状態へのポインタ
	int path_length, ref_count;	// 経路の長さ、子の数
} links[MAXLINK], *head, *tail, *lfree, *answers;

static int l_assigned, l_active, l_max;	// 割り当てられたリンク数

/*
 *** 探索の内部処理関数群
 */

static struct LINK *
new_link(node, len)			// 新しいリンク構造体の割当て
	void *node; int len;
{
	struct LINK *link = lfree;
	if (link == NULL) {
		fprintf(stderr, "%s\n", "リンクが尽きたので終了します。");
		exit(1);
	}
	l_assigned++;
	l_active++;
	if (l_active > l_max) l_max = l_active;
	lfree = link->next;
	link->next = NULL;
	link->path = NULL;
	link->node = node;
	link->path_length = len;
	link->ref_count = 0;
	return(link);
}

static void
free_link(link)				// 使用済みリンク構造体の回収
	struct LINK *link;
{
	if (link == NULL) return;
	if (link->ref_count > 0) return;
	l_active--;
	link->next = lfree;
	lfree = link;
	for (link = link->path; link != NULL; link = link->path) {
		link->ref_count--;
		if (link->ref_count > 0) return;
		l_active--;
		link->next = lfree;
		lfree = link;
	}
}

static void
init_search(node)			// 探索処理の初期化
	void *node;			// node は初期状態へのポインタ
{
	int i;
	/* 自由リンク（未使用リンク）の設定 */
	for (i=0; i<MAXLINK; i++) links[i].next = links+(i+1);
	links[MAXLINK-1].next = NULL;
	lfree = links;

	anslen = INFINITY;
	answers = NULL;
	nans = 0;
	head = tail = new_link(node, 0);
	l_active = l_assigned = l_max = 0;
}

static void
newnode(parent, node, len, method)		// 探索リストへの新しいノードの追加
	struct LINK *parent; void *node; int len, method;
{
	struct LINK *link = new_link(node, len);
	link->path = parent;
	if (head == NULL) {
		tail = head = link;
	} else if (method == DEPTH_FIRST) {	// 深さ優先探索：リストの先頭に追加
		link->next = head;
		head = link;
	} else if (method == BREADTH_FIRST) {	// 広さ優先探索：リストの末尾に追加
		tail->next = link;
		tail = link;
	}
}

static void
newnodes(link, n, nodes, method)		// 現在のリンクの子ノードの登録
	struct LINK *link; int n; void **nodes; int method;
{
	int i, len = link->path_length+1;
	link->ref_count = n;
	for (i=0; i<n; i++) newnode(link, nodes[i], len, method);
}

static struct LINK *
popnode()					// 探索ノードの取り出し
{
	struct LINK *link = head;
	if (link == NULL) return(NULL);
	head = head->next;
	return(link);
}

static void
check_answer(link)				// 解答のチェック、解答リンクの生成
	struct LINK *link;
{
	struct LINK *answer = NULL, *lk = link;
	int len = link->path_length;
	if (len > anslen) {			// 最短解より長い解は捨てる(1)
		free_link(link);
		return;
	}
	if (len < anslen) {
		while (answers != NULL) {	// 最短解より長い解は捨てる(2)
			struct LINK *next = answers->next;
			free_link(answers);
			answers = next;
		}
		nans = 0;
		anslen = len;
	}
	while (lk != NULL) {			// 正順の解リストを作る
		struct LINK *a = new_link(lk->node, lk->path_length);
		a->path = answer;
		answer = a;
		lk = lk->path;
	}
	nans++;					// 新しい解の登録
	answer->next = answers;
	answers = answer;
	free_link(link);
}

static int
path_check(link)				// 経路上のノードかのチェック
	struct LINK *link;
{
	void *node = link->node;
	for (link = link->path; link != NULL; link = link->path)
		if (node == link->node) return(1);
	return(0);
}

int
search(initial_node, method)			// 共通の探索ルーチン
	void *initial_node;
{
	struct LINK *link;
	init_search(initial_node);

	while ((link = popnode()) != NULL) {
		int res = node_status(link->node, link->path_length, nodes), i;
		if (res == SUCCESS) {
			check_answer(link);
			if (first_only) return(1);
			continue;
		} else if ((res == FAILURE) || (link->path_length >= anslen)
				|| (default_check && path_check(link))) {
			free_link(link);
			continue;
		}
		newnodes(link, res, nodes, method);
	}
	return(nans);
}

int
answer_length() { return(anslen); }		// 解の長さ

void *
answer_path(n)					// 解 n の経路を状態ポインタ配列に返す。
	int n;
{
	struct LINK *ans = answers;
	int i;
	while (n > 1) {
		if (ans == NULL) break;
		n--;
		ans = ans->next;
	}
	if (ans == NULL) return(NULL);

	for (i=0; ans != NULL; i++, ans = ans->path) nodes[i] = ans->node;
	return(nodes);
}