/*
 * Copyright (c) 2003 Nara Institute of Science and Technology
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name Nara Institute of Science and Technology may not be used to
 *    endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY Nara Institute of Science and Technology 
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 
 * PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE Nara Institute
 * of Science and Technology BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $Id: parse.c,v 1.57 2003/07/30 16:06:57 kazuma-t Exp $
 */

#include "chalib.h"
#include "literal.h"
#include "tokenizer.h"
#include "dartsdic.h"

#define PATH1_NUM		256

#define is_spc(c)    ((c)==' '||(c)=='\t')

cha_block_t *Cha_mrph_block;
path_t *Cha_path = NULL;
int Cha_path_num;

#define new_mrph() cha_block_new_item(Cha_mrph_block)
#define nth_mrph(n) ((mrph_t*)cha_block_get_item(Cha_mrph_block,(n)))
#define mrph_last_idx() (cha_block_num(Cha_mrph_block)-1)
#define pop_mrph() cha_block_pop(Cha_mrph_block)

/*
 * malloc_chars
 */
#define CHUNK_SIZE 512
#define CHA_MALLOC_SIZE (1024 * 64)
#define malloc_char(n)     malloc_chars(1, n)
#define malloc_short(n)    malloc_chars(2, n)
#define malloc_int(n)      malloc_chars(4, n)
#define free_chars()       malloc_chars(0, 0)
static void *
malloc_chars(int size, int nitems)
{
    static char *buffer_ptr[CHUNK_SIZE];
    static int buffer_ptr_num = 0;
    static int buffer_idx = CHA_MALLOC_SIZE;

    if (nitems == 0) {
	/*
	 * free 
	 */
	if (buffer_ptr_num > 0) {
	    while (buffer_ptr_num > 1)
		free(buffer_ptr[--buffer_ptr_num]);
	    buffer_idx = 0;
	}
	return NULL;
    } else {
	if (size > 1) {
	    /*
	     * size dz꤭ͤ 
	     */
	    buffer_idx += size - (buffer_idx & (size - 1));
	    nitems *= size;
	}

	if (buffer_idx + nitems >= CHA_MALLOC_SIZE) {
	    if (buffer_ptr_num == CHUNK_SIZE)
		cha_exit(1, "Can't allocate memory");
	    buffer_ptr[buffer_ptr_num++] = cha_malloc(CHA_MALLOC_SIZE);
	    buffer_idx = 0;
	}

	buffer_idx += nitems;
	return buffer_ptr[buffer_ptr_num - 1] + buffer_idx - nitems;
    }
}

static void *
malloc_free_block(void *ptr, int *nblockp, int size, int do_free)
{
    if (do_free) {
	/*
	 * free and malloc one block 
	 */
	if (*nblockp > 1) {
	    free(ptr);
	    *nblockp = 0;
	}
	if (*nblockp == 0)
	    ptr = malloc_free_block(ptr, nblockp, size, 0);
    } else {
	/*
	 * realloc one block larger 
	 */
	if (*nblockp == 0)
	    ptr = malloc(size * ++*nblockp);
	else {
	    ptr = realloc(ptr, size * ++*nblockp);
	}
    }

    return ptr;
}

#define malloc_path()  malloc_free_path(0)
#define free_path()    malloc_free_path(1)
static int
malloc_free_path(int do_free)
{
    static int nblock = 0;

    Cha_path = malloc_free_block((void *) Cha_path, &nblock,
				 sizeof(path_t) * CHA_PATH_NUM, do_free);

    return Cha_path == NULL;
}

static int
collect_mrphs_for_pos(int pos, int *head_path, int *p_idx)
{
    int i, j;

    j = 0;
    if (pos == 0) { /* new sentence */
	p_idx[j++] = 0;
    } else {
	for (i = *head_path; i < Cha_path_num; i++) {
	    if (Cha_path[i].end <= pos) {
		if (i == *head_path)
		    (*head_path)++;
		if (Cha_path[i].end == pos)
		    p_idx[j++] = i;
	    }
	}
    }
    p_idx[j] = -1;

    return j;
}

typedef struct _path_cost_t {
    int min_cost;
    short min_cost_no;
    short state;
    short num;
    int cost[PATH1_NUM];
    int pno[PATH1_NUM];
} path_cost_t;

static int
classify_path(path_cost_t *pcost, int *p_idx, int con_tbl)
{
    int i, pno;
    int pcost_num = 0;

    pcost[0].state = -1;

    /*
     * ֤ͤǥѥʬह 
     */
    for (i = 0; (pno = p_idx[i]) >= 0; i++) {
	int con_cost, cost;
	int next_state;
	int pcostno;

	next_state = cha_check_automaton
	    (Cha_path[pno].state, con_tbl, Cha_con_cost_undef, &con_cost);
	if (con_cost == -1)
	    continue;

	cost = Cha_path[pno].cost + con_cost * Cha_con_cost_weight;

	/*
	 * ɤ pcost °뤫Ĵ٤ 
	 */
	for (pcostno = 0; pcostno < pcost_num; pcostno++)
	    if (next_state == pcost[pcostno].state)
		break;
	if (pcostno < pcost_num) {
	    /*
	     * tricky: when Cha_cost_width is -1, ">-1" means ">=0" 
	     */
	    if (cost - pcost[pcostno].min_cost > Cha_cost_width)
		continue;
	} else {
	    /*
	     *  pcost  
	     */
	    pcost_num++;
	    pcost[pcostno].num = 0;
	    pcost[pcostno].state = next_state;
	    pcost[pcostno].min_cost = INT_MAX;
	}

	/*
	 * pcost Ͽ 
	 */
	if (Cha_cost_width < 0) {
	    pcost[pcostno].min_cost = cost;
	    pcost[pcostno].pno[0] = pno;
	} else {
	    pcost[pcostno].cost[pcost[pcostno].num] = cost;
	    pcost[pcostno].pno[pcost[pcostno].num] = pno;
	    if (cost < pcost[pcostno].min_cost) {
		pcost[pcostno].min_cost = cost;
		pcost[pcostno].min_cost_no = pcost[pcostno].num;
	    }
	    pcost[pcostno].num++;
	}
    }
    return pcost_num;
}

static int
check_connect(int pos, int m_num, int *p_idx)
{
    path_cost_t pcost[PATH1_NUM];
    int pcost_num, pcostno;
    int mrph_cost;
    mrph_t *new_mrph;

    new_mrph = nth_mrph(m_num);

    pcost_num = classify_path(pcost, p_idx, new_mrph->con_tbl);
    if (pcost_num == 0)
	return TRUE;

    /*
     * ǥ 
     */
    if (new_mrph->is_undef) {
	mrph_cost = Cha_undef_info[new_mrph->is_undef - 1].cost
	    + Cha_undef_info[new_mrph->is_undef - 1].cost_step
	    * new_mrph->headword_len / 2;
    } else {
	mrph_cost = Cha_hinsi[new_mrph->posid].cost;
    }
    mrph_cost *= new_mrph->weight * Cha_mrph_cost_weight;

    for (pcostno = 0; pcostno < pcost_num; pcostno++) {
	if (Cha_cost_width < 0) {
	    Cha_path[Cha_path_num].best_path = pcost[pcostno].pno[0];
	} else {  /* ˤޤäƤѥȴФ */
	    int i;
	    int npath = 0;
	    int path[PATH1_NUM];
	    int cost_ceil = pcost[pcostno].min_cost + Cha_cost_width;

	    Cha_path[Cha_path_num].best_path = 
		pcost[pcostno].pno[pcost[pcostno].min_cost_no];
	    for (i = 0; i < pcost[pcostno].num; i++)
		if (pcost[pcostno].cost[i] <= cost_ceil)
		    path[npath++] = pcost[pcostno].pno[i];
	    path[npath++] = -1;
	    memcpy(Cha_path[Cha_path_num].path = malloc_int(npath),
		   path, sizeof(int) * npath);
	}

	Cha_path[Cha_path_num].cost = pcost[pcostno].min_cost + mrph_cost;
	Cha_path[Cha_path_num].mrph_p = m_num;
	Cha_path[Cha_path_num].state = pcost[pcostno].state;
	Cha_path[Cha_path_num].start = pos;
	Cha_path[Cha_path_num].end = pos + new_mrph->headword_len;

	if (++Cha_path_num % CHA_PATH_NUM == 0 && malloc_path())
	    return FALSE;
    }

    return TRUE;
}

#define DIC_BUFSIZ 256

static int
register_mrphs(darts_t* da, char *strings, long *indecies, int num)
{
    mrph_t *new_mrph;
    da_lex_t lex_data[DIC_BUFSIZ]; /* XXX */
    int i;

    for (i = 0; i < num; i++) {
	int nlex, j, len;
	nlex = da_get_lex(da, indecies[i], lex_data, &len);
	for (j = 0; j < nlex; j++) {
	    new_mrph = new_mrph();
	    new_mrph->headword = strings;
	    new_mrph->headword_len = len;
	    new_mrph->is_undef = 0;
	    new_mrph->darts = da;
	    memcpy(new_mrph, lex_data + j, sizeof(da_lex_t));
	}
    }

    return mrph_last_idx();
}

static int
lookup_dic(char *string, int len)
{
    int dic_no;
    long index_buffer[DIC_BUFSIZ]; /* XXX */

    for (dic_no = 0; dic_no < Da_ndicfile; dic_no++) {
	int num =
	    da_lookup(Da_dicfile[dic_no], string, len,
		      index_buffer, DIC_BUFSIZ);
	register_mrphs(Da_dicfile[dic_no], string, index_buffer, num);
    }

    return mrph_last_idx();
}

static int
register_undef_mrph(char *string, int len, int no)
{
    mrph_t *mrph = new_mrph();

    mrph->posid = Cha_undef_info[no].hinsi;
    mrph->dat_index = -1;
    mrph->inf_type = 0;
    mrph->inf_form = 0;
    mrph->weight = MRPH_DEFAULT_WEIGHT;
    mrph->con_tbl = Cha_undef_info[no].con_tbl;

    mrph->headword = string;
    mrph->headword_len = len;
    mrph->is_undef = no + 1;
    mrph->darts = NULL;

    return mrph_last_idx();
}

static int
set_undefword(char *string, int cursor, int head_mrph_idx, int tail_mrph_idx)
{
    int undef_len;
    int i;

    undef_len = cha_tok_char_type_len(Cha_tokenizer, cursor);

    for (i = head_mrph_idx; i <= tail_mrph_idx; i++) {
	/*
	 * ̤ƱĹñ줬ˤ̤ɲäʤ 
	 */
	if (Cha_con_cost_undef > 0 &&
	    nth_mrph(i)->headword_len == undef_len) {
	    undef_len = 0;
	    break;
	}
    }

    if (undef_len > 0) {
	int no;
	for (no = 0; no < Cha_undef_info_num; no++)
	    register_undef_mrph(string, undef_len, no);
    }

    return mrph_last_idx();
}

static int
register_bos_eos(void)
{
    mrph_t *mrph = new_mrph();

    memset(mrph, 0, sizeof(mrph_t));
    mrph->weight = MRPH_DEFAULT_WEIGHT;
    mrph->dat_index = -1;
    mrph->headword = "";

    return mrph_last_idx();
}

#define cursor_sep(c, l) \
     ((!cha_tok_is_jisx0208_latin(Cha_tokenizer,(c), (l))) ? \
        cha_tok_mblen_on_cursor(Cha_tokenizer, (c)) : \
        cha_tok_char_type_len(Cha_tokenizer, (c)))

/*
 * cha_parse_sentence() - ʸDzϤ
 *
 * return value:
 *     0 - ok
 *     1 - no result / too many morphs
 */
int
cha_parse_sentence(char *sentence, int len)
{
    int cursor, prev_cursor;
    int path_idx[PATH1_NUM], path_idx_num;
    int last_idx;
    int head_path;
    static int path0 = -1;

    cha_tok_parse(Cha_tokenizer, sentence, len + 1);
    cha_block_clear(Cha_mrph_block);

    free_chars();
    free_path();

    Cha_path[0].start = Cha_path[0].end = 0;
    Cha_path[0].path = &path0;
    Cha_path[0].cost = 0;
    Cha_path[0].mrph_p = 0;
    Cha_path[0].state = 0;
    head_path = 1;

    Cha_path_num = 1;
    register_bos_eos();

    for (cursor = prev_cursor = 0; cursor < len;
	cursor += cursor_sep(cursor, len - cursor),
	prev_cursor = cursor) {
	int mrph_idx, i;

        /* skip annotations and white space */
	while (cha_tok_anno_type(Cha_tokenizer, cursor) != 0 )
	  cursor += cha_tok_char_type_len(Cha_tokenizer, cursor);
	if (cursor >= len)
	  break;
	
	path_idx_num =
	    collect_mrphs_for_pos(prev_cursor, &head_path, path_idx);
	if (path_idx_num == 0)
	    continue;
	else if (path_idx_num < 0)
	    goto error_end;

	mrph_idx = mrph_last_idx() + 1;
	last_idx = lookup_dic(sentence + cursor, len - cursor);
	last_idx = set_undefword(sentence + cursor,
				 cursor, mrph_idx, last_idx);

	/* check the path between the preceding and current position  */
	for (i = mrph_idx; i <= last_idx; i++) {
	    if (check_connect(cursor, i, path_idx) == FALSE)
		goto error_end;
	}
    }

    /* end of sentense */
    last_idx = register_bos_eos();
    path_idx_num = collect_mrphs_for_pos(prev_cursor, &head_path, path_idx);
    if (check_connect(cursor, last_idx, path_idx) == FALSE)
        goto error_end;

    return 0;

  error_end:
    printf("Error: Too many morphs: %s\n", sentence);

    return 1;
}