#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MALLOC malloc
#define FREE(X) free(X)
// #include <gc.h>
// #define MALLOC GC_MALLOC
// #define FREE(X)

/************************************************************
 * State
 ************************************************************/
typedef int stid;

/**************************************************
 * 履歴用状態リスト
 **************************************************/
typedef struct _SL{
  stid state;
  struct _SL *next;
} SL;


SL *newSL(){
  SL *tmppt;

  tmppt = MALLOC(sizeof(SL));
  tmppt->next = NULL;
  return tmppt;
}

SL *pushSL(stid state, SL *pt){
  SL *tmppt;

  tmppt = newSL();
  tmppt->state = state;
  tmppt->next = pt;
  return tmppt;
}

SL *popSL(SL *pt){
  SL *tmppt;

  tmppt = pt->next;
  FREE(pt);
  return tmppt;
}

bool memberSL(stid state, SL *pt){

  if(pt == NULL) return false;
  else if (pt->state == state) return true;
  else return memberSL(state, pt->next);
}

int lengthSL(SL *pt){

  if(pt == NULL){
    return 0;
  } else {
    return lengthSL(pt->next) + 1;
  }
}

void printSL(SL *pt){

  if(pt == NULL) printf(".\n");
  else {
    printf("-> [%d] ", pt->state);
    printSL(pt->next);
  }
}

/************************************************************
 * 探索用木生成
 ************************************************************/
int BF; // Branching Factor
int MD; // Max Depth

// treeSize(D)
// size of a model tree with branching factor BF and depth D
// \sum_{j=0}^D B^j

int treeSize(int d){

  if(d <= 0) return 1;
  else return 1 + BF * treeSize(d-1);
}

// treeDepth(N)
// depth of the node N in a model tree with branching factor BF
// (root = 0)
int treeDepth(stid n){

  if(n == 0) return 0;
  else return 1 + treeDepth((n - 1) / BF);
}

// firstChild(N)
// the first child of the node N in a model tree with branching factor BF
// (root = 0)
bool firstChild(stid *p, stid *c){
  int d;
  d = treeDepth(*p);
  if(d == MD) return false;
  if(d == 0) *c = 1;
  else *c = treeSize(d) + BF * (*p - treeSize(d - 1));
  return true;
}

SL *generateChildren(stid p){
  stid fc;
  stid i;
  SL *sp = NULL;

  if(firstChild(&p, &fc)){
    //    printState(p); printf(" - "); printState(fc); printf("\n");
    //    for(i = 0; i < BF; i++) sp = pushSL(fc + i, sp);
    for(i = BF ; i != 0; i--) {
      //      printState(fc + i - (stid) 1); printf("\n");
      sp = pushSL(fc + i - (stid) 1, sp);
    }
  }
  return sp;
}

/************************************************************
 * 探索アルゴリズム用リスト
 ************************************************************/
typedef struct _list {
  stid state;
  int value;
  SL *history;
  struct _list *next;
} list;
list *ol;

#define PRINTLIST printList

list *newList(){

  list *tmppt;

  tmppt = MALLOC(sizeof(list));
  tmppt->next = NULL;
  tmppt->value = -1;
  // tmppt->state[BMAX2]='\0';
  return tmppt;
}

list *popList(list *pt){
  list *tmppt;

  tmppt = pt->next;
  FREE(pt);
  return tmppt;
}

list *pushList(stid state, SL *hpt, list *pt){
  list *tmpst;

  tmpst = newList();
  tmpst->next = pt;
  tmpst->state = state;
  tmpst->history = hpt;
  return tmpst;
}

/* 課題 */
list *appendList(stid state, SL *hpt, list *pt){
   /* 再帰バージョン */
  list *tmpst;

  if(pt == NULL){ /* ptそのものがNULLのとき 最後の要素 停止条件 */
    tmpst = newList(); /* tmpst -> next は、NULLで初期化されている */
    tmpst->state = state;
    tmpst->history = hpt; /* hptは、この頂点までの経路情報　SL型 */
    return tmpst; /* 新要素のアドレス */
  } else { /* 再帰条件。returnされるアドレスを繋ぎなおしていることに注意 */
    pt->next = appendList(state, hpt, pt->next); /* pt -> next == NULLのとき、つまり最後の要素だけ、変更になる */
    return pt; /* 自分自身のアドレスをreturn */
  }



  /**************************************************/
}

int lengthList(list *pt){

  if(pt == NULL){
    return 0;
  } else {
    return lengthList(pt->next) + 1;
  }
}

void printList(list *pt){

  if(pt != NULL){
    printf("-> [%d] ", pt->state);
    printList(pt->next);
  } else {
    printf("-> NULL\n");
  }
}

void printListLength(list *pt){

  printf(" %d\n", lengthList(pt));
}

/************************************************************
 * 探索アルゴリズム
 ************************************************************/

/**************************************************
 深さ優先探索 (Depth First Search)
 **************************************************/
SL *dfs(stid start, stid goal){
  int i;
  stid curstate;
  SL *nextstateset;
  SL *curhpt;

// 探索管理用リスト Lを初期状態だけのリストにする
  ol = NULL;
  ol = pushList(start, NULL, ol);

// while Lが空リストでない
  while(ol != NULL){
    PRINTLIST(ol);  // 探索管理用リストをプリント

    /* Lの先頭要素を取り出して、curstateに代入 */
    curstate = ol->state;
    curhpt = pushSL(curstate, ol->history);
    ol = popList(ol);
    if(curstate == goal) return(curhpt);

    nextstateset = generateChildren(curstate);
    while(nextstateset != NULL){
      if(memberSL(nextstateset->state, curhpt)==false){
        ol = pushList(nextstateset->state, curhpt, ol);
      }
      nextstateset=popSL(nextstateset);
    }
  }
  return(NULL);
}


/**************************************************
 幅優先探索 (Breadth First Search)
 **************************************************/
SL *bfs(stid start, stid goal){
  int i;
  stid curstate;
  SL *nextstateset;
  SL *curhpt;

// 探索管理用リスト Lを初期状態だけのリストにする
  ol = NULL;
  ol = pushList(start, NULL, ol);

// while Lが空リストでない
  while(ol != NULL){
    PRINTLIST(ol);  // 探索管理用リストをプリント

    /* Lの先頭要素を取り出して、curstateに代入 */
    curstate = ol->state;
    curhpt = pushSL(curstate, ol->history);
    ol = popList(ol);
    if(curstate == goal) return(curhpt);

    nextstateset = generateChildren(curstate);
    while(nextstateset != NULL){
      if(memberSL(nextstateset->state, curhpt)==false){
/*      ol = pushList(nextstateset->state, curhpt, ol); */
        ol = appendList(nextstateset->state, curhpt, ol);
      }
      nextstateset=popSL(nextstateset);
    }
  }
  return(NULL);
}

/**************************************************
 深さ制限探索 (Depth-limited Search)
 **************************************************/

SL *dls(stid start, stid goal, int limit){
  /**************************************************/
}

/**************************************************
 反復深化探索 (Iterative Deepening Search)
 **************************************************/
SL *ids(stid start, stid goal){
  int cutdepth;
  SL *result;

  cutdepth = 1;
  printf("==================== cut depth = %2d ====================\n",
         cutdepth);

  while((result = dls(start, goal, cutdepth++)) == NULL){
    printf("==================== cut depth = %2d ====================\n",
           cutdepth);
  }
  return(result);
}

/**********************************************************************
 Main
 **********************************************************************/

typedef struct _searchfunc {
  char *comment;
  SL *(*func)(stid, stid);
} searchfunc;

searchfunc searchtable[] = {
  {"Depth First Search", dfs},
  {"Breadth First Search", bfs},
  {"Iterative Deepening Search", ids},
  {NULL, NULL}
};

void help(char *cmdname){
  int i;

  fprintf(stderr, "Usage: %s BranchingFactor MaxDepth Goal [search_algorithm]\n", cmdname);
  for(i = 0; searchtable[i].comment!=NULL; i++){
    fprintf(stderr, "  %d : %s\n", i, searchtable[i].comment);
  }
}

int main(int argc, char *argv[]){
  stid start, goal;
  SL *sp;
  int maxalg, curalg;

  for(maxalg = 0; searchtable[maxalg].comment!=NULL; maxalg++);

  // 引数の個数のチェックと探索方法(第5引数,デフォールトは 0)の設定
  if( (argc != 4 && argc != 5) ||
      (curalg= argc == 5 ? atoi(argv[4]) : 0) < 0 ||
      maxalg <= curalg) {
    help(argv[0]);
    exit(0);
  }

  // 初期状態(0), 木のサイズ(分岐数,深さ)と目標状態の設定
  start = 0;
  BF = atoi(argv[1]);
  MD = atoi(argv[2]);
  goal = atoi(argv[3]);

  // 探索の実施
  sp = (searchtable[curalg].func)(start, goal);
  printf("Path %d : ", lengthSL(sp));
  printSL(sp);
}
STEP 1.2 幅優先探索と反復深化探索 2016

STEP 1.2　幅優先探索と反復深化探索 2016
