/***************************************************************************/
 /*                                                                         */
 /*      Copyright (C) 1991, 1992  Daniel Sleator and Davy Temperley        */
 /*  See file "README" for information about commercial use of this system  */
 /*                                                                         */
 /***************************************************************************/

/* stuff for transforming a dictionary entry into a disjunct list */

#include "header.c"

/*Temporary connectors used while converting expressions into disjunct lists */
typedef struct Tconnector_struct Tconnector;
struct Tconnector_struct{
    char multi;   /* TRUE if this is a multi-connector */
    char dir;     /* '-' for left and '+' for right */
    Tconnector * next;
    char * string;
};

typedef struct clause_struct Clause;
struct clause_struct {
    Clause * next;
    int cost;
    Tconnector * c;
};

Tconnector * copy_Tconnectors(Tconnector * c) {
/* This builds a new copy of the connector list pointed to by c.
   Strings, as usual, are not copied.
*/
    Tconnector *c1;
    if (c == NULL) return NULL;
    c1 = (Tconnector *) xalloc(sizeof(Tconnector));
    *c1 = *c;
    c1->next = copy_Tconnectors(c->next);
    return c1;
}

void free_Tconnectors(Tconnector *e) {
    Tconnector * n;
    for(;e != NULL; e=n) {
	n = e->next;
	xfree((char *)e, sizeof(Tconnector));
    }
}

void free_clause_list(Clause *c) {
    Clause *c1;
    while (c != NULL) {
	c1 = c->next;
	free_Tconnectors(c->c);
	xfree((char *)c, sizeof(Clause));
	c = c1;
    }
}

Clause * copy_clause(Clause * d) {
/* This builds a new copy of the clause pointed to by d (except for the
   next field which is set to NULL).  Strings, as usual, are not copied.
*/
    Clause * d1;
    if (d == NULL) return NULL;
    d1 = (Clause *) xalloc(sizeof(Clause));
    *d1 = *d;
    d1->next = NULL;
    d1->c = copy_Tconnectors(d->c);
    return d1;
}

Tconnector * Treverse(Tconnector *e) {
/* reverse the order of the list e.  destructive */
    Tconnector * head, *x;
    head = NULL;
    while (e != NULL) {
	x = e->next;
	e->next = head;
	head = e;
	e = x;
    }
    return head;
}    

Connector * reverse(Connector *e) {
/* reverse the order of the list e.  destructive */
    Connector * head, *x;
    head = NULL;
    while (e != NULL) {
	x = e->next;
	e->next = head;
	head = e;
	e = x;
    }
    return head;
}    

Tconnector * catenate(Tconnector * e1, Tconnector * e2) {
/* Builds a new list of connectors that is the catenation of e1 with e2.
   does not effect lists e1 or e2.   Order is maintained. */

    Tconnector * e, * head;
    head = NULL;
    for (;e1 != NULL; e1 = e1->next) {
	e = (Tconnector *) xalloc(sizeof(Tconnector));
	*e = *e1;
	e->next = head;
	head = e;
    }
    for (;e2 != NULL; e2 = e2->next) {
	e = (Tconnector *) xalloc(sizeof(Tconnector));
	*e = *e2;
	e->next = head;
	head = e;
    }
    return Treverse(head);
}

Tconnector * build_terminal(Exp * e) {
    /* build the connector for the terminal node n */
    Tconnector * c;
    c = (Tconnector *) xalloc(sizeof(Tconnector));
    c->string = e->u.string;
    c->multi = e->multi;
    c->dir = e->dir;
    c->next = NULL;
    return c;
}

Clause * build_clause(Exp *e) {
/* Build the clause for the expression e.  Does not change e */
    Clause *c=NULL, *c1, *c2, *c3, *c4, *c_head;
    E_list * e_list;

    assert(e != NULL, "build_clause called with null parameter");
    if (e->type == AND_type) {
	c1 = (Clause *) xalloc(sizeof (Clause));
	c1->c = NULL;
	c1->next = NULL;
	c1->cost = 0;
	for (e_list = e->u.l; e_list != NULL; e_list = e_list->next) {
	    c2 = build_clause(e_list->e);
	    c_head = NULL;
	    for (c3 = c1; c3 != NULL; c3 = c3->next) {
		for (c4 = c2; c4 != NULL; c4 = c4->next) {
		    c = (Clause *) xalloc(sizeof (Clause));
		    c->cost = c3->cost + c4->cost;
		    c->c = catenate(c3->c, c4->c);
		    c->next = c_head;
		    c_head = c;
		}
	    }
	    free_clause_list(c1);
	    free_clause_list(c2);
	    c1 = c_head;
	}
	c = c1;
    } else if (e->type == OR_type) {
	/* we'll catenate the lists of clauses */
	c = NULL;
	for (e_list = e->u.l; e_list != NULL; e_list = e_list->next) {
	    c1 = build_clause(e_list->e);
	    while(c1 != NULL) {
		c3 = c1->next;
		c1->next = c;
		c = c1;
		c1 = c3;
	    }
	}
    } else if (e->type == CONNECTOR_type) {
	c = (Clause *) xalloc(sizeof(Clause));
	c->c = build_terminal(e);
	c->cost = 0;
	c->next = NULL;
    } else {
	assert(FALSE, "an expression node with no type");
    }

    /* c now points to the list of clauses */

    for (c1=c; c1!=NULL; c1 = c1->next) {
	c1->cost += e->cost;
    }
    return c;
}

void print_connector_list(Connector * e) {
    for (;e != NULL; e=e->next) {
	printf("%s",e->string);
	if (e->label != NORMAL_LABEL) {
	    printf("%3d", e->label);
	} else {
	    printf("   ");
	}
	if (e->next != NULL) printf(" ");
    }
}

void print_Tconnector_list(Tconnector * e) {
    for (;e != NULL; e=e->next) {
	if (e->multi) printf("@");
	printf("%s",e->string);
	printf("%c", e->dir);
	if (e->next != NULL) printf(" ");
    }
}

void print_clause_list(Clause * c) {
    for (;c != NULL; c=c->next) {
	printf("  Clause: ");
	printf("(%2d)", c->cost);
	print_Tconnector_list(c->c);
	printf("\n");
    }
}

void print_disjunct_list(Disjunct * c) {
    for (;c != NULL; c=c->next) {
	printf("%10s: ", c->string);
	printf("(%2d)", c->cost);
	print_connector_list(c->left);
	printf(" <--> ");
	print_connector_list(c->right);
	printf("\n");
    }
}

Connector * extract_connectors(Tconnector *e, int c) {
/* Build a new list of connectors starting from the Tconnectors
   in the list pointed to by e.  Keep only those whose strings whose
   direction has the value c.
*/
    Connector *e1;
    if (e == NULL) return NULL;
    if (e->dir == c) {
	e1 = (Connector *) xalloc(sizeof(Connector));
	e1->next = extract_connectors(e->next,c);
	e1->multi = e->multi;
	e1->string = e->string;
	e1->label = NORMAL_LABEL;
	e1->priority = THIN_priority;
	e1->word = 0;
	return e1;
    } else {
	return extract_connectors(e->next,c);
    }
}	

Disjunct * build_disjunct(Clause * cl, char * string) {
/* build a disjunct list out of the clause list c */
/* string is the print name of word that generated this disjunct */
    Disjunct *dis, *ndis;
    dis = NULL;
    for (;cl != NULL; cl=cl->next) {
        ndis = (Disjunct *) xalloc(sizeof(Disjunct));
        ndis->left = reverse(extract_connectors(cl->c, '-'));
        ndis->right = reverse(extract_connectors(cl->c, '+'));
	ndis->string = string;
        ndis->cost = cl->cost;
        ndis->next = dis;
        dis = ndis;
    }
    return dis;
}

Disjunct * build_disjuncts_for_X_node(X_node * x) {
    Clause *c ;
    Disjunct * dis;
    c = build_clause(x->exp);
    dis = build_disjunct(c, x->string);
    free_clause_list(c);
    return dis;
}

Disjunct * build_disjuncts_for_dict_node(Dict_node *dn) {
/* still need this for counting the number of disjuncts */
    Clause *c ;
    Disjunct * dis;
/*                 print_expression(dn->exp);   */
/*                 printf("\n");                */
    c = build_clause(dn->exp);
/*                 print_clause_list(c);        */
    dis = build_disjunct(c, dn->string);
    free_clause_list(c);
    return dis;
}

#if FALSE

Disjunct * build_word_disjuncts(char * s) {
/* Looks up the word s in the dictionary.  Returns NULL if it's not there.
   If there, it builds the disjunct structure for the word, and returns
   a pointer to it.
*/
    Dict_node * dn;
    Disjunct * dis;

    dn = dictionary_lookup(s);

/*
    x = dn;
    printf("%s :", s);
    while (dn != NULL) {
       printf("%s \n", dn->string);
       print_expression(dn->node);
       dn = dn->right;
    }
    dn = x;
*/
    dis = NULL;

    while (dn != NULL) {
	dis = catenate_disjuncts(build_disjuncts_for_dict_node(dn), dis);
	dn = dn->right;
    }
                /*    print_disjunct_list(dis); */
    return dis;
}
#endif

X_node * build_word_expressions(char * s) {
/* Looks up the word s in the dictionary.  Returns NULL if it's not there.
   If there, it builds the list of expressions for the word, and returns
   a pointer to it.
*/
    Dict_node * dn;
    X_node * x, * y;

    dn = dictionary_lookup(s);

    x = NULL;
    while (dn != NULL) {
	y = (X_node *) xalloc(sizeof(X_node));
	y->next = x;
	x = y;
	x->exp = copy_Exp(dn->exp);
	x->string = dn->string;
	dn = dn->right;
    }
    return x;
}

void build_sentence_disjuncts(void) {
/* We've already built the sentence expressions.  This turns them into
   disjuncts.  
*/
    Disjunct * d;
    X_node * x;
    int w;
    for (w=0; w<N_words; w++) {
	d = NULL;
	for (x=sentence[w].x; x!=NULL; x = x->next){
	    d = catenate_disjuncts(build_disjuncts_for_X_node(x),d);
	}
	sentence[w].d = d;
    }
}