#define _GNU_SOURCE
#include <stdio.h>
#include <sys/time.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <sched.h>
#include <assert.h>

#define MAX_SIZE         32
#define MAX_PROC         128

/* n女王問題アルゴリズム */
typedef int (*nq_func) (int P, int myid, int n, int sym, int d);

/* 構造体 */

/* アルゴリズム */
struct nq_algorithm{
  int id;
  nq_func func;
  nq_func func2;
  char *desc;
};

/* workerに渡すデータ */
struct warg {
  int myid;
  int n;
  int sym;
  int d;
  int P;
  nq_func fw;
};

/* プロトタイプ宣言 */
int systhr_create(void * (*start_func)(void *), void *arg);
void assign_cpu(int cpu);
int p_helper(nq_func f, nq_func fw, int n, int P, int sym, int d);
void set_result(int r);
void *fworker_assign_cpu(void *arg);
double elapsed_time(struct timeval tp[2]);
void usage(char *filename);

/* 逐次実装 */
int nqueens_b(int P, int myid, int n, int sym, int d);

/* 並列実装（関数対）*/
int worker(int P, int myid, int n, int sym, int d);
int master(int P, int myid, int n, int sym, int d);


/* アルゴリズムリスト */
struct nq_algorithm algorithm[] =
{
  {1, nqueens_b, NULL,      "n-queens (bitmap version)"}, 
  /* 並列実装は、master 用と worker 用の2つの関数を登録 */
  {101, master, worker,    "Please implement it"}, 
};


/* main */
int main(int argc, char *argv[])
{
  struct timeval tp[2];
  double elapsed;
  struct nq_algorithm *nq;
  int p = 0, n = -1, al = 0, debug = 0, sym = 0, silent = 0;
  int s;
  int i;

  
  /* コマンドライン引数の解釈 */
  for(i = 1; i < argc; i++){
    if(strcmp(argv[i], "-d") == 0){
      /* 解を表示する */
      debug = 1;
    }else if(strcmp(argv[i], "-a") == 0){
      /* 探索アルゴリズムが指定される */
      i++;
      if(i == argc){
        printf("Specify the algorithm to use: %s\n", argv[i - 1]);
        return 0;
      }
      sscanf(argv[i], "%d", &al);
    }else if(strcmp(argv[i], "-p") == 0){
      /* ワーカスレッド数が指定される */
      i++;
      if(i == argc){
        printf("Specify the number of worker threads to use: %s\n", argv[i - 1]);
        return 0;
      }
      sscanf(argv[i], "%d", &p);
      /* スレッド数が不正ならば適当な値に変更して続ける */
      if(p < 1){
        printf("The number of threads must be 1 - %d: regarded as 1\n", MAX_PROC);
        p = 1;
      }else if(p > MAX_PROC){
        printf("The number of threads must be 1 - %d: regarded as %d\n", MAX_PROC, MAX_PROC);
        p = MAX_PROC;
      }
    }else if(argv[i][0] >= '0' && argv[i][0] <= '9'){
      /* サイズが指定される */
      sscanf(argv[i], "%d", &n);
      if(n < 1 || n > MAX_SIZE){
        printf("The size must be 1 - %d\n", MAX_SIZE);
        return 0;
      }
    }else if(strcmp(argv[i], "-h") == 0){
      /* ヘルプ */
      usage(argv[0]);
      return 0;
    }else if(strcmp(argv[i], "-t") == 0){
      /* 経過時間のみ表示する */
      silent = 1;
    }else if(strcmp(argv[i], "-s") == 0){
      /* 対称解を含めない */
      sym = 1;
    }else{
      /* 不明なパラメータ */
      printf("Invalid Parameter: %s\n", argv[i]);
      return 0;
    }
  }

  if (n == -1) {
    printf("Number of queens required\n");
    return 1;
  }

  /* 既定のプロセッサ数とアルゴリズム */
  if(al == 0){
    /* アルゴリズム未指定 */
    if(p <= 1){
      /* 逐次版の中で速いものを選んでおく */
      al = 1;
    }else{
      /* 並列版の中で速いものを選んでおく */
      al = 101;
    }
  }else{
    /* アルゴリズム指定済み */
    if(p == 0){
      /* スレッド数未指定 */
      if(al >= 101){
        /* 並列版アルゴリズム指定済み */
        /* デフォルトは P = 2 */
        p = 2;
      }
    }
  }

  /* アルゴリズムを指定する */
  nq = NULL;
  for(i = 0; i < sizeof(algorithm) / sizeof(struct nq_algorithm); i++){
    if(algorithm[i].id == al){
      nq = &algorithm[i];
      if(!silent) printf("*** %s ***\n", nq->desc);
      break;
    }
  }
  /* 該当するアルゴリズムなし */
  if(nq == NULL){
    printf("Invalid Parameter: -a %d\n", al);
    return 0;
  }

  if(!silent) printf("running queens %d\n", n);
     
  /* 時間測定開始 */
  gettimeofday(tp, 0);

  /* 計算開始 */
  if(al < 101){
    /* 逐次 */
    s = ((nq_func)nq->func)(0, 0, n, sym, debug);
  }else{
    /* 並列 */
    s = p_helper(nq->func, nq->func2, n, p, sym, debug);
  }

  /* 時間測定終了, 結果表示 */
  gettimeofday(tp+1, 0);
  elapsed = elapsed_time(tp);

  if(!silent){
    printf("%d answers\n", s);
    printf("Elapsed Time: %f sec.\n", elapsed);
  }else{
    printf("%f\n", elapsed);
  }
     
  return 0;
}

/* スレッド生成 */
int systhr_create(void * (*start_func)(void *), void *arg){
  int status = 0;
  pthread_t tid;
  pthread_attr_t attr;
  pthread_attr_init(&attr);
  status = pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
  if(status == 0) status = pthread_create(&tid, &attr, start_func, arg);
  if(status != 0) status = pthread_create(&tid, 0,     start_func, arg);
  return status;
}

/* 使用するCPUを指定する */
void assign_cpu(int cpu){
  /* Linuxワークステーション用の処理 */
  cpu_set_t cpu_set;
  /* 指定したCPUのみを集合に加える */
  CPU_ZERO(&cpu_set);
  CPU_SET(cpu, &cpu_set);
  /* 割り当て */
  sched_setaffinity(0, sizeof(cpu_set_t), &cpu_set);
}


/* 使用するCPUを指定 & start a worker thread */
void *fworker_assign_cpu(void *arg)
{
  struct warg *w = arg;
  assign_cpu(w->myid);
  w->fw(w->P,w->myid,w->n,w->sym,w->d);
  return NULL;
}

/* 並列処理の補助用 */
int p_helper(nq_func f, nq_func fworker, int n, int P, int sym, int d){
  int i, r;
  struct warg w[MAX_PROC];
  
  for(i=0;i<P;i++){  /* P 個の woker を起動し、ここのコアに貼り付ける */
    w[i].myid = i;
    w[i].n = n;
    w[i].sym = sym;
    w[i].d = d;
    w[i].P = P;
    w[i].fw = fworker;
    systhr_create(fworker_assign_cpu, w+i);
  }

  /* start the master thread */
  r = f(P, P, n, sym, d);

  return r;
}

/* 経過時間の計算 */
double elapsed_time(struct timeval tp[2])
{
  return tp[1].tv_sec-tp[0].tv_sec+1e-6*(tp[1].tv_usec-tp[0].tv_usec);
}


void usage(char *filename){
  int i;

  printf("Usage: %s [size] [options...]\n", filename);
  puts("Options:");
  puts("  -a <number>: choose the algorithm to use");
  for(i = 0; i < sizeof(algorithm) / sizeof(struct nq_algorithm); i++){
    printf("     %3d: %s\n", algorithm[i].id, algorithm[i].desc);
  }
  puts("  -d: list all solutions");
  puts("  -h: show this help");
  puts("  -s: exclude symmetric solutions (search unique solutions)");
  puts("  -t: only show elapsed time (if no error occured)");
  puts("  -p <number>: the number of worker threads to use");
}


/*------------ 以下、アルゴリズム実装 -------------------------*/

/*------------ 逐次版 --------------------------------------*/

void output_solution_b(int n, int *a)
{
  int i, j;
  const int E = 1<<n;
  for(i = 0; i < n; i++) {
    for (j = 1; j < E; j<<=1) {
      printf("%c ", a[i] & j ? 'Q' : '.');
    }
    printf("\n");
  }
  printf("\n");
}

/* ビットマップバージョン (-a 1) : 対称性の考慮はしていない（symフラグを無視する） */
int nqueens_b(int P, int myid, int n, int sym, int d)
{
  int nqueens_b_rec_print(const int n, int k, const int l, const int r, const int u, int *a);
  int nqueens_b_rec(const int n, int k, const int l, const int r, const int u);
  /* 単純な深さ優先探索 */
  if(d) { return nqueens_b_rec_print(n, 0, 0, 0, 0, alloca(n*sizeof(int))); }
  else  { return nqueens_b_rec(n, 0, 0, 0, 0); }
}

/* ビットマップバージョン (-a 2) の本体（再帰関数）の解出力バージョン */
int 
nqueens_b_rec_print(const int n, int k, const int l, const int r, const int u, int *a)
{
  if (n == k) { /* 解を発見 */
    output_solution_b(n, a);
    return 1;
  }
  else
  {
    int i, s = 0;
    const int E = 1<<n;
    const int ng = l | r | u;
    int ok = (~ng) & (E-1); /* ok の i ビット目が 1 なら、i 列目にクイーンをおいてもOK*/
    while(ok) {      
      i = ok & -ok;  /* 一番若い 1 を取ってくる */ 
      ok ^= i;
      a[k] = i;	  
      s += nqueens_b_rec_print(n, k + 1, (l | i) << 1, (r | i) >> 1, u | i, a);
    }
    return s;
  }
}


/* ビットマップバージョン (-a 2) の本体（再帰関数）の解出力なしバージョン */
int 
nqueens_b_rec(const int n, int k, const int l, const int r, const int u)
{
  if (n == k) { /* 答え */
    return 1;
  }
  else
  {
    int i, s = 0;
    const int E = 1<<n;
    const int ng = l | r | u;
    int ok = (~ng) & (E-1); /* ok の i ビット目が 1 なら、i 列目にクイーンをおいてもOK*/
    while(ok) {
      i = ok & -ok;  /* 一番若い 1 を取ってくる */
      ok ^= i;
      s += nqueens_b_rec(n, k + 1, (l | i) << 1, (r | i) >> 1, u | i);
    }
    return s;
  }
}



/*---------------------- parallel implementations ----------------------*/

// see http://www.yasugi.ai.kyutech.ac.jp/3p/k6.html#ms
//     http://www.yasugi.ai.kyutech.ac.jp/3p/ms.c

/* worker 用関数。繰り返し仕事をもらい処理する。*/
int worker(int P, int myid, int n, int sym, int d)
{
  return 0;
}

/* master 用関数。仕事を生成する*/
int master(int P, int myid, int n,  int sym, int d)
{
  return 0;
}