/*
 * 文節の境界を検出する。
 * 文中のextentの連結を評価して、スコアが高くなるようにextentを選んでいく。
 *
 * metawordの選択には幅優先探索を行う
 * 検索のノードがAstar_nodeでsearch_statが検索用のキュー
 *
 * anthy_eval_border() で指定された領域を文節に分割する
 *
 * Funded by IPA未踏ソフトウェア創造事業 2001 10/29
 * Copyright (C) 2000-2003 TABATA Yusuke, UGAWA Tomoharu
 */
#include <stdio.h>
#include <stdlib.h>

#include <alloc.h>
#include <splitter.h>
#include "wordborder.h"

/**/
#define ASTAR_MAX_DEPTH 8
#define ASTAR_NORMAL_DEPTH 4
#define ASTAR_HEAP_DEPTH 1024
#define ASTAR_EXPAND_LIMIT 4096

/* 検索のノード */
struct Astar_node {
  /* 今まで検索したextent */
  int nr_ex;
  struct extent *ex[ASTAR_MAX_DEPTH];

  /* このノードの状態 */
  int score;
  int from;
  int len;
  /**/
  int heap_score;
};

/*
 * グローバルな検索の状態
 *
 * ここでいうヒープというのは言語処理系のやつではなくて、
 * 2分木を含んだ配列で、要素番号nの子は2nと2n+1になっている。
 * 親は子ノードよりも大きいということをinvariant
 * とすることによりルートノードには最大の要素が存在する。
 */
struct search_stat {
  /* 現時点でもっともスコアの高いノード */
  struct Astar_node best;
  /* 検索の限界の深さ */
  int search_depth;
  /* 探索のヒープ */
  struct Astar_node **heap;
  /* ヒープの深さ */
  int nr_nodes;
  /**/
  int expand_count;
};

static allocator node_ator;


/** (句読点などは除く)文節の長さのバランスを計算 
 * 隣り合う文節の長さが近いほど自然な文であると仮定
 *
 *  -(Σ(文節長^2))*文節数 は
 * 全ての文節が同じ長さの時に
 *  -(文の長さ^2) となる。文節数に依存しないよう設定している。
 *
 * 文節長が長い場合はカットオフする
 */
static int
calc_balance(struct Astar_node *an)
{
  int i;
  int bal ,nr_seg;
  int total_len;

  bal = 0;
  nr_seg = 0;
  total_len = 0;

  for (i = 0; i < an->nr_ex; i++) {
    struct extent *ex = an->ex[i];
    /* もし、どのクラスにも属さない文字ならば、区切りとはみなさない */
    if (!ex->is_dummy_char) {
      int len = an->ex[i]->len;
      if (len > 5 * ex->mw_count) {
	/* 文節長が長い場合はカットオフする */
	len = 5 * ex->mw_count;
      }
      /* (len/mw_count)^2*mw_count */
      bal += len * len / ex->mw_count;
      nr_seg += ex->mw_count;
      total_len += len;
    }
  }
  bal *= SCORE_PER_LEN * nr_seg;
  if (total_len) {
    bal /= (total_len * total_len);
  } else {
    bal = 0;
  }

  return bal;
}

static void 
print_astar_node(struct splitter_context *sc,
		 struct Astar_node *an)
{
  int i;
  printf("A*node score=%d balance=(%d)\n", an->score, calc_balance(an));
  for (i = 0; i < an->nr_ex; i++) {
    if (an->ex[i]->best) {
      anthy_print_metaword(sc, an->ex[i]->best);
    } else {
      printf("no meta word.\n");
    }
  }
  printf("\n");
}

static struct Astar_node *
alloc_astar_node(void)
{
  struct Astar_node *a = anthy_smalloc(node_ator);
  a->nr_ex = 0;
  a->len = 0;
  return a;
}

/*
 * サーチによって決定されたmetawordによって
 * 各metawordの左端の文節境界をマークする
 */
static void 
mark_by_metaword(struct splitter_context *sc,
		 struct meta_word *mw)
{
  struct word_split_info_cache *info = sc->word_split_info;
  if (!mw) {
    return ;
  }
  switch (anthy_metaword_type_tab[mw->type].mark) {
  case MW_MARK_PAIR:
    mark_by_metaword(sc, mw->mw1);
    mark_by_metaword(sc, mw->mw2);
    break;
  case MW_MARK_OCHAIRE:
    mark_by_metaword(sc, mw->mw1);
    break;
  case MW_MARK_OCHAIRE_LEAF:
    info->seg_border[mw->from] = 1;
    if (mw->mw1) {
      mark_by_metaword(sc, mw->mw1);
    }
    break;
  case MW_MARK_WRAP:
    mark_by_metaword(sc, mw->mw1);
    break;
  case MW_MARK_WL:
    if (mw->wl) {
      info->seg_border[mw->wl->from] = 1;
    }
    break;
  case MW_MARK_LEFT_WL:
    if (mw->mw1->wl) {
      info->seg_border[mw->mw1->wl->from] = 1;
    }
    break;
  case MW_MARK_NONE:
  default:
    printf("try to mark unknown type of metaword (%d).\n",
	   anthy_metaword_type_tab[mw->type].mark);
  }
}

/*
 * ヒープのルートを取り除いたのでルートの方へ
 * 各ノードをずらす
 */
static void
rebalance_astar_heap_from_root(struct search_stat *ss, int n)
{
  int l, r;
  int ls, rs, ns;
  struct Astar_node *nn, *ln, *rn;
  l = 2 * (n + 1) - 1;
  r = 2 * (n + 1);
  ls = -2000000000;
  rs = -2000000000;
  ln = 0;
  rn = 0;
  ns = ss->heap[n]->heap_score;
  nn = ss->heap[n];
  if (l < ASTAR_HEAP_DEPTH) {
    ln = ss->heap[l];
  }
  if (r < ASTAR_HEAP_DEPTH) {
    rn = ss->heap[r];
  }
  if (ln) {
    ls = ln->heap_score;
  }
  if (rn) {
    rs = rn->heap_score;
  }
  if (ns > ls && ns > rs) {
    return ;
  }
  if (ls > rs) {
    ss->heap[n] = ln;
    ss->heap[l] = nn;
    rebalance_astar_heap_from_root(ss, l);
  } else {
    ss->heap[n] = rn;
    ss->heap[r] = nn;
    rebalance_astar_heap_from_root(ss, r);
  }
}

static void
eval_astar_node(struct Astar_node *an)
{
  int i, bonus;
  struct extent *ex;
  an->score = 0;

  if (an->nr_ex == 0) {
    return ;
  }

  for (i = 0; i < an->nr_ex; i++) {
    ex = an->ex[i];
    an->score += ex->score;
  }

  /* 後ろの文節に対する加点 */
  bonus = SCORE_PER_LEN / 20 * an->len;
  if (an->nr_ex == 1) {
    an->score += bonus;
  } else {
    an->score += bonus * (an->len - an->ex[0]->len) / an->len;
  }

  /* 文節バランスによる変化*/
  an->score += SCORE_PER_LEN;
  an->score -= calc_balance(an);

  /* 文節数による減点 */
  an->score -= an->nr_ex * SCORE_PER_LEN / 4;
}

static void
push_astar_node(struct search_stat *ss,
		struct Astar_node *an)
{
  int n, p;

  /* heapの深さを越えたのでメモリを解放 */
  if (ss->nr_nodes >= ASTAR_HEAP_DEPTH - 1) {
    anthy_sfree(node_ator, an);
    return ;
  }

  /* 評価を行う */
  eval_astar_node(an);

  /* 基本的には幅優先 */
  an->heap_score = ss->expand_count * 10;
  if (an->nr_ex) {
    /* 平均の長さが低いのは後回し */
    an->heap_score += SCORE_PER_LEN * an->len / an->nr_ex;
  }
  

  /* ヒープに積む */
  ss->heap[ss->nr_nodes] = an;
  ss->nr_nodes ++;

  /* leaf側からrebalance */
  n = ss->nr_nodes - 1;
  while (n) {
    p = (n - 1) / 2;
    if (ss->heap[p]->heap_score < ss->heap[n]->heap_score) {
      struct Astar_node *tmp;
      tmp = ss->heap[p];
      ss->heap[p] = ss->heap[n];
      ss->heap[n] = tmp;
    }
    n = p;
  }
}

static struct Astar_node *
pop_astar_node(struct search_stat *ss)
{
  struct Astar_node *n;
  n = ss->heap[0];
  if (!n) {
    return 0;
  }

  ss->nr_nodes--;
  ss->heap[0] = ss->heap[ss->nr_nodes];
  ss->heap[ss->nr_nodes] = 0;
  if (ss->nr_nodes) {
    /* root側からrebalance */
    rebalance_astar_heap_from_root(ss, 0);
  }
  return n;
}

static void
do_expand_astar_node(struct splitter_context *sc,
		     struct search_stat *ss,
		     struct Astar_node *an)
{
  /* anの右端はfrom */
  int from = an->from + an->len;
  int i;

  for (i = sc->char_count - from; i >= 1; i--) {
    struct Astar_node *n;
    struct extent *ex;
    ex = anthy_find_extent(sc, from, i, 0);
    if (!ex) {
      continue;
    }

    n = alloc_astar_node();
    *n = *an;
    n->ex[n->nr_ex] = ex;
    n->nr_ex++;
    n->len += i;
    push_astar_node(ss, n);
  }
}

/*
 * ノードを展開する 
 *  本当の展開はdo_expand_astar_nodeで行う
 */
static void
expand_astar_node(struct splitter_context *sc,
		  struct search_stat *ss,
		  struct Astar_node *an, int to)
{
  int t = an->from + an->len;

  /* 右端のノードに到達したので、深い探索に切替える */
  if (t == to) {
    ss->search_depth = ASTAR_MAX_DEPTH;
  }

  if (an->nr_ex < ss->search_depth && t <= to) {
    do_expand_astar_node(sc, ss, an);
  }

  if (anthy_splitter_debug_flags() & SPLITTER_DEBUG_AN) {
    print_astar_node(sc, an);
  }
  /* 今までの最高スコアを更新 */
  if (an->score > ss->best.score) {
    ss->best = *an;
  }

  /* 展開済のノードを解放 */
  anthy_sfree(node_ator, an);
}

/** search_statを初期化する、一文節を決定するごとに呼ばれる */
static void
init_search_stat(struct search_stat *ss)
{
  int i;

  ss->heap =
    malloc(sizeof(struct Astar_node *) * ASTAR_HEAP_DEPTH);
  for (i = 0; i < ASTAR_HEAP_DEPTH; i++) {
    ss->heap[i] = 0;
  }
  ss->nr_nodes = 0;
  ss->best.score = 0;
  ss->search_depth = ASTAR_NORMAL_DEPTH;
}

/* search_statを解放する、一文節を決定するごとに呼ばれる */
static void
free_search_stat(struct search_stat *ss)
{
  int i;
  for (i = 0; i < ASTAR_HEAP_DEPTH; i++) {
    if (ss->heap[i]){
      anthy_sfree(node_ator, ss->heap[i]);
    }
  }
  ss->nr_nodes = 0;
  free (ss->heap);
}

static void
mark_by_extent(struct splitter_context *sc,
	       struct extent *ex)
{
  mark_by_metaword(sc, ex->best);
}

/*
 * 一文節の境界を見付ける
 * 返り値はその見付けた文節の右端のインデックス
 */
static int
do_split(struct splitter_context *sc,
	 int from, int to)
{
  struct search_stat ss;
  struct Astar_node *a;

  /* 検索の初期化 */
  init_search_stat(&ss);

  /* 最初のnodeを積む */
  a = alloc_astar_node();
  a->from = from;
  push_astar_node(&ss, a);

  /* 検索を行う */
  for (ss.expand_count = ASTAR_EXPAND_LIMIT;
       ss.expand_count > 0; ss.expand_count--) {
    a = pop_astar_node(&ss);
    if (!a) {
      /* ノ−ドが尽きた */
      goto out;
    }
    /* 展開する */
    expand_astar_node(sc, &ss, a, to);
  }
 out:

  /* 検索のためのデータを解放する */
  free_search_stat(&ss);

  if (ss.best.score == 0) {
    /* 検索に失敗したので一番右までできたことにしてしまう */
    return to;
  }

  /*print_astar_node(sc, &ss->best);
    anthy_print_metaword(sc, ss.best.ex[0]->best);*/
  /* もっともスコアの高いextentで文節区切りをマークする */
  if (ss.best.ex[0]->best) {
    mark_by_extent(sc, ss.best.ex[0]);
  }
  return from + ss.best.ex[0]->len;
}

/** 一つのextentを評価する
 */
static void
eval_extent(struct extent *ex)
{
  struct meta_word *mw, *max = NULL;
  int best_score = 0;

  /* 同じextentの中で最大のscoreのmeta_wordを見付ける */
  for (mw = ex->mw; mw; mw = mw->same_extent) {
    if (mw->can_use == ok) {
      int score;
      /**/
      score = mw->score;
      score -= mw->mw_count * SCORE_PER_LEN / 32;
      /**/
      if (!max || (best_score < score)) {
	best_score = score;
	max = mw;
      }
    }
  }

  /* extentのscoreを決める */
  if (max) {
    /* metawordがあれば，もっともスコアの高いmetawordのスコアを採用する */
    ex->score = best_score;
    ex->mw_count = max->mw_count;
  } else {
    /* metawordがなければ，長さ分のスコアを付ける */
    ex->score = SCORE_PER_LEN * ex->len;
  }
  ex->best = max;
}

/* 
 * 全てのextentを評価する
 */
static void
eval_extent_all(struct splitter_context *sc)
{
  int from, len;
  for (from = 0; from < sc->char_count; from++) {
    /*
     * 長さ1のextentが無いと，制約によっては検索が進めなくなるので
     * まず，長さ1のextentを強制的に作る
     */
    anthy_find_extent(sc, from, 1, 1);

    /*
     * 全部のextentに対して計算
     */
    for (len = 1; len <= sc->char_count - from; len++) {
      struct extent *ex = anthy_find_extent(sc, from, len, 0);
      if (ex) {
	eval_extent(ex);
      }
    }
  }
}

/* 文節境界の制約を充足しない文節を除去する */
static void
seg_constraint_check_all(struct splitter_context *sc,
			 int from, int to)
{
  int i, j;
  for (i = from; i < to; i++) {
    struct word_list *wl;
    for (wl = sc->word_split_info->cnode[i].wl;
	 wl; wl = wl->next) {
      wl->can_use = ok;
      /* wlのカバーする範囲に文節の境界があればng */
      for (j = 1; j < wl->len; j++) {
	if (sc->ce[i + j].seg_border) {
	  wl->can_use = ng;
	}
      }
    }
  }
}

/*
 * 再帰的にmetawordが使用可能かチェックする
 */
static void
metaword_constraint_check(struct splitter_context *sc,
			  struct meta_word *mw)
{
  struct word_split_info_cache *info = sc->word_split_info;
  if (mw->can_use != unchecked) {
    return ;
  }
  switch(anthy_metaword_type_tab[mw->type].check){
  case MW_CHECK_WL_STR:
    if (!mw->wl) {
      int i;
      mw->can_use = ok;
      for (i = 1; i < mw->len; i++) {
	if (sc->ce[i + mw->from].seg_border) {
	  mw->can_use = ng;
	}
      }
    }
    /* break無し */
  case MW_CHECK_WL_SINGLE:
    if (!mw->wl || mw->wl->can_use == ok) {
      mw->can_use = ok;
    } else {
      mw->can_use = ng;
    }
    break;
  case MW_CHECK_WL_WRAP:
    metaword_constraint_check(sc, mw->mw1);
    mw->can_use = mw->mw1->can_use;
    break;
  case MW_CHECK_BORDER:
    if (info->seg_border[mw->mw1->from + mw->mw1->len]) {
      /* ちょうど境目にマークが入ってる */
      mw->can_use = ng;
      break;
    }
    /* break無し */
  case MW_CHECK_PAIR:
    metaword_constraint_check(sc, mw->mw1);
    metaword_constraint_check(sc, mw->mw2);
    if (mw->mw1->can_use == ok && mw->mw2->can_use == ok) {
      mw->can_use = ok;
    }
    break;
  case MW_CHECK_OCHAIRE:
    {
      int i;
      struct meta_word* mw1;
      for (mw1 = mw; mw1; mw1 = mw1->mw1) {
	mw1->can_use = ok;
      }
      for (i = mw->from + 1; i < mw->from + mw->len; i++) {
	if (sc->ce[i].seg_border) {
	  for (mw1 = mw; mw1; mw1 = mw1->mw1) {
	    mw1->can_use = ng;
	  }
	  break;
	}
      }
    }
    break;
  case MW_CHECK_NONE:
    break;
  default:;
    printf("try to check unknown type of metaword (%d).\n", mw->type);
  }
}

/*
 * word_listの情報を基にmetawordが使用できるかチェックする
 */
static void
metaword_constraint_check_all(struct splitter_context *sc,
			      int from, int to)
{
  int i;
  struct word_split_info_cache *info;
  info = sc->word_split_info;

  /* まずuncheckedにする */
  for (i = from; i < to; i ++) {
    struct meta_word *mw;
    for (mw = info->cnode[i].mw;
	 mw; mw = mw->next) {
      mw->can_use = unchecked;
    }
  }

  /* 次に合成されたmetawordについてチェック */
  for (i = from; i < to; i ++) {
    struct meta_word *mw;
    for (mw = info->cnode[i].mw; mw; mw = mw->next) {
      metaword_constraint_check(sc, mw);
    }
  }
}

/*
 * ここから文節境界をマークする
 */
void
anthy_eval_border(struct splitter_context *sc, int from, int to)
{
  node_ator = anthy_create_allocator(sizeof(struct Astar_node), 0);
  /* 文節候補のうち使えるもののみ選択 */
  seg_constraint_check_all(sc, from, to);
  metaword_constraint_check_all(sc, from, to);

  /* extentを評価する */
  eval_extent_all(sc);

  do{
    from = do_split(sc, from, to);
    if (anthy_splitter_debug_flags() & SPLITTER_DEBUG_1) {
      break;
    }
  } while (from < to);
  anthy_free_allocator(node_ator);
}
