/*
 *** search.h: 汎用探索エンジン・ライブラリのヘッダ ***
 *	(2004/06/21 YH)
 *
 * * 以下には探索エンジンのユーザに関係のある定義類である。
 * * 探索エンジンの説明は search.txt に、
 *   本体は search.c にあるのでそれぞれを参照。
 */

#ifndef	_SEARCH_H
#define	_SEARCH_H

#include <stdio.h>
#include <stdlib.h>

/*
 *** 定数・変数（フラッグ） ***
 */

			/***** 探索の種類の指定（search() の第２引数） *****/
#define	DEPTH_FIRST	0	// 深さ優先探索
#define	BREADTH_FIRST	1	// 広さ優先探索

			/***** search() の返り値（の一部） *****/
#define	SUCCESS	(-1)		// 成功終了ノード
#define	FAILURE	0		// 失敗終了ノード

			/***** 探索の動作制御（オプション） *****/
extern int default_check;	// 1 ならループが生じたかのデフォールトチェックを行う。
extern int first_only;		// 1 なら最初に見つかった解だけを返す。

/*
 *** ユーザが呼び出す関数 ***
 */
extern int search();			// 探索の本体関数
	// 実際には下の depth_first, breadth_first マクロを使えばよい。
	// 使い方：
	//	n = search(initial_node, type);
	// 引数：
	//	initial_node	初期状態ノードへのポインタ
	//	type		DEPTH_FIRST（縦型探索）、BREADTH_FIRST（横型探索）のいずれか。
	// 返り値：
	//	解の個数（解がない： 0）

#define	depth_first(initial_node)	search(initial_node, DEPTH_FIRST)
#define	breadth_first(initial_node)	search(initial_node, BREADTH_FIRST)

extern int answer_length();		// 解の長さを返す関数
	// len = answer_length();
	//	len は最短解の長さ
extern void *answer_path();		// n 番目の解の経路を返す関数
	// nodes = answer_path(n);
	//	n 番目の解の経路（ノードポインタ配列）を nodes に返す。(n = 1, 2, 3, ...)
	//	配列の長さは上の len になる。

/*
 *** ユーザが定義する関数 ***
 */
extern int node_status();		// ノード情報を返す関数
	// 定義の仕方：
	//	int node_status(void *node, int len, void **nodes) { ...}
	//
	// 変数（仮引数）：
	//	node	調べるノードを表すデータ構造へのポインタ。
	//		汎用性のため、データ構造は特定せず、(void *) 型で受けている。
	//	len	node に至る経路の長さ（初期ノードの値は 0）。
	//	nodes	node の子ノードを収めるポインタ配列。
	//		node_status の中で、子の数の分だけ代入する。
	// 返り値：
	//	SUCCESS	このノードが目標状態（探索成功）
	//	FAILURE	探索が失敗（禁止状態、既訪状態、子ノードがないなど）
	//	n(>=1)	子ノードの個数。nodes に n 個の子ノードへのポインタを代入しておく。

#endif	//	_SEARCH_H