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

#include "header.c"

Link link_array[MAX_LINKS];
int N_links;

/* should get rid of chosen_words eventually.  That info is in the
   chosen disjuncts */

Disjunct * chosen_disjuncts[MAX_SENTENCE];

void issue_link(Disjunct *ld, Disjunct * rd, int lw, int rw,
		Connector * lc, Connector * rc) {
    link_array[N_links].l = lw;
    link_array[N_links].r = rw;
    link_array[N_links].lc = lc;
    link_array[N_links].rc = rc;
    N_links++;

    chosen_disjuncts[lw] = ld;
    chosen_disjuncts[rw] = rd;
}

int magic(int lw, int rw, Connector *le, Connector *re) {
/* returns the count for this quadruple if there, 0 otherwise */
/* the only difference between this and table_lookup is that  */
/* the latter returns -1 when it's not there, this returns 0  */
/* This will fool list_links into working, even though the    */
/* search may be conducted in a different order.  If one of   */
/* these bogus answers is returned, even though it may be     */
/* wrong, we know that this entry in the table could not be   */
/* used in any of the correct parsings, so it's ok to give the*/
/* wrong answer.                                              */
    int c;
    
    c = table_lookup(lw, rw, le, re);
    if (c<0) {
	return 0;
    } else {
	return c;
    }
}

void list_links(Disjunct *ld, Disjunct * rd, int lw, int rw,
                Connector *le, Connector *re, int index) {
    Disjunct * d;
    int leftcount, rightcount, total;
    int i, x, delta;
    int lml=0, lmr=0, rml=0, rmr=0;
    int lc, rc, lindex, rindex;
    int w, start_word, end_word;
    Match_node * m, *m1;

    if (rw == 1+lw) {
	assert((le == NULL) && (re == NULL) && (index == 0),
	       "Error encountered while extracting links.");
	return;
    }

    total = 0;
    if (le == NULL) {
	start_word = lw+1;
    } else {
	start_word = le->word;
    }
    if (re == NULL) {
	end_word = rw-1;
    } else {
	end_word = re->word;
    }

    for (w=start_word; w <= end_word; w++) {
	m1 = m = form_match_list(w, le, lw, re, rw); 
	for (; m!=NULL; m=m->next) {
	    d = m->d;
	    if ((le != NULL) && (d->left != NULL) && match(le, d->left)) {
		lml = le->multi;
		lmr = d->left->multi;
		leftcount = magic(lw, w, le->next, d->left->next);
		if (lml) leftcount += magic(lw, w, le, d->left->next);
		if (lmr) leftcount += magic(lw, w, le->next, d->left);
		if (lml&&lmr) leftcount += magic(lw, w, le, d->left);
	    } else {
		leftcount = 0;
	    }
	    if ((d->right != NULL) && (re != NULL) && match(d->right, re)) {
		rml = d->right->multi;
		rmr = re->multi;
		rightcount = magic(w, rw, d->right->next,re->next);
		if (rml) rightcount+= magic(w, rw, d->right, re->next);
		if (rmr) rightcount+= magic(w, rw, d->right->next, re);
		if (rml&&rmr) rightcount+= magic(w, rw, d->right, re);
	    } else {
		rightcount = 0;
	    }
	    i = leftcount * rightcount;
	    total += i;

	    if ((total-i <= index) && (total > index)) {
	        x = index-total+i;  /* 0 <= x < i */
		lindex = x / rightcount;
		rindex = x % rightcount;
		lc = 0;
		delta = magic(lw, w, le->next, d->left->next);
		lc += delta;
		if (lc > lindex) {
		    issue_link(ld, d,lw, w, le, d->left);
                  list_links(ld,d,lw,w,le->next,d->left->next,lindex-lc+delta);
		}
		if (lml) delta = magic(lw, w, le, d->left->next);
		else delta = 0;
		lc += delta;
		if ((lc-delta <= lindex) && (lc > lindex)) {
		    issue_link(ld,d,lw, w, le, d->left);
		    list_links(ld,d,lw, w, le, d->left->next, lindex-lc+delta);
		}
		if (lmr) delta = magic(lw, w, le->next, d->left);
		else delta=0;
		lc += delta;
		if ((lc-delta <=lindex) && lc > lindex) {
		    issue_link(ld,d,lw, w, le, d->left);
		    list_links(ld,d,lw, w, le->next, d->left, lindex-lc+delta);
		}
		if (lml&&lmr) delta = magic(lw, w, le, d->left);
		else delta = 0;
		lc += delta;
		if ((lc-delta <=lindex) && lc > lindex) {
		    issue_link(ld,d,lw, w, le, d->left);
		    list_links(ld,d,lw, w, le, d->left, lindex-lc+delta);
		}
		rc = 0;
		delta = magic(w, rw, d->right->next,re->next);
		rc += delta;
		if (rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		 list_links(d,rd,w,rw,d->right->next,re->next,rindex-rc+delta);
		}
		if (rml) delta = magic(w, rw, d->right, re->next);
		else delta = 0;
		rc += delta;
		if ((rc-delta <= rindex) && rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		    list_links(d,rd,w,rw, d->right, re->next,rindex-rc+delta);
		}
		if (rmr) delta = magic(w, rw, d->right->next, re);
		else delta = 0;
		rc += delta;
		if ((rc-delta <= rindex) && rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		    list_links(d,rd,w,rw, d->right->next, re,rindex-rc+delta);
		}
		if (rml&&rmr) delta = magic(w, rw, d->right, re);
		else delta = 0;
		rc += delta;
		if ((rc-delta <= rindex) && rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		    list_links(d,rd,w, rw, d->right, re,rindex-rc+delta);
		}
	    }

	    if (leftcount > 0) {
		i = leftcount * magic(w, rw, d->right, re);
	    } else {
		i = 0;
	    }
	    total += i;
	    if ((total-i <= index) && (total > index)) {
	        x = index-total+i;  /* 0 <= x < i */
		lindex = x % leftcount;
		rindex = x / leftcount;

/* same code as above */
		lc = 0;
		delta = magic(lw, w, le->next, d->left->next);
		lc += delta;
		if (lc > lindex) {
		    issue_link(ld,d,lw, w, le, d->left);
	          list_links(ld,d,lw,w,le->next,d->left->next,lindex-lc+delta);
		}
		if (lml) delta = magic(lw, w, le, d->left->next);
		else delta = 0;
		lc += delta;
		if ((lc-delta <= lindex) && (lc > lindex)) {
		    issue_link(ld,d,lw, w, le, d->left);
		    list_links(ld,d,lw,w, le, d->left->next, lindex-lc+delta);
		}
		if (lmr) delta = magic(lw, w, le->next, d->left);
		else delta=0;
		lc += delta;
		if ((lc-delta <=lindex) && lc > lindex) {
		    issue_link(ld,d,lw, w, le, d->left);
		    list_links(ld,d,lw, w, le->next, d->left, lindex-lc+delta);
		}
		if (lml&&lmr) delta = magic(lw, w, le, d->left);
		else delta = 0;
		lc += delta;
		if ((lc-delta <=lindex) && lc > lindex) {
		    issue_link(ld,d,lw, w, le, d->left);
		    list_links(ld,d,lw, w, le, d->left, lindex-lc+delta);
		}

/* end of same code as above */

		list_links(d,rd,w, rw, d->right, re,rindex);
	    }
	    if ((le == NULL) && (rightcount > 0)) {
		i = rightcount * magic(lw, w, le, d->left);
	    } else {
		i = 0;
	    }
	    total += i;
	    if ((total-i <= index) && (total > index)) {
	        x = index-total+i;  /* 0 <= x < i */
		rindex = x % rightcount;
		lindex = x / rightcount;

/* more same code as above */
		rc = 0;
		delta = magic(w, rw, d->right->next,re->next);
		rc += delta;
		if (rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		list_links(d,rd,w,rw,d->right->next,re->next,rindex-rc+delta);
		}
		if (rml) delta = magic(w, rw, d->right, re->next);
		else delta = 0;
		rc += delta;
		if ((rc-delta <= rindex) && rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		    list_links(d,rd,w, rw, d->right, re->next,rindex-rc+delta);
		}
		if (rmr) delta = magic(w, rw, d->right->next, re);
		else delta = 0;
		rc += delta;
		if ((rc-delta <= rindex) && rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		    list_links(d,rd,w, rw, d->right->next, re,rindex-rc+delta);
		}
		if (rml&&rmr) delta = magic(w, rw, d->right, re);
		else delta = 0;
		rc += delta;
		if ((rc-delta <= rindex) && rc > rindex) {
		    issue_link(d,rd,w, rw, d->right, re);
		    list_links(d,rd,w, rw, d->right, re,rindex-rc+delta);
		}

/* end more same code as above */

		list_links(ld,d,lw, w, le, d->left,lindex);
	    }
	}
	put_match_list(m1);
    }
}

void extract_links(int index) {
/* generate the list of all links of the indexth parsing of the sentence */
/* for this to work, the hash table must have already been built with a  */
/* call to count()                                                       */
    
    Disjunct * dis;
    int total, c=0;
    N_links = 0;
    total = 0;
    
    for (dis = sentence[0].d; dis != NULL; dis = dis->next) {
	if (dis->left == NULL) {
	    c = magic(0, N_words, dis->right, NULL);
	    total += c;
	    if (total > index) break;
	}	
    }
    list_links(dis, NULL, 0, N_words, dis->right, NULL, index-total+c);
}