/*
 * wiggle - apply rejected patches
 *
 * Copyright (C) 2003 Neil Brown <neilb@cse.unsw.edu.au>
 *
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *    Author: Neil Brown
 *    Email: <neilb@suse.de>
 */

/*
 * calculate longest common sequence between two sequences
 *
 * Each sequence contains strings with
 *   hash start length
 * We produce a list of tripples: a b len
 * where A and B point to elements in the two sequences, and len is the number
 * of common elements there
 *
 * To help keep matches close together (important when matching a changed fragment
 * against a whole) we track the disagonal of the first and last match on any path.
 * When choosing the best of two paths, we choose the furthest reaching unless
 * the other has a match and it's absolute diagonal difference is significantly smaller.
 * 'Significant' if the reduction in difference exceeds the loss of progress by a
 * factor of 2.
 *
 */

#include	<malloc.h>
#include	"wiggle.h"
#include	<string.h>
#include	<stdlib.h>


struct v {
	int x;	/* x location of furthest reaching path of current cost */
	int md; /* diagonal location of midline crossing */
	int l;  /* number of continuous common sequences found so far */
};


static int find_common(struct file *a, struct file *b,
		       int *alop, int *ahip,
		       int *blop, int *bhip,
		       int mid,
		       struct v *v)
{
	/* examine matrix from alo to ahi and blo to bhi
	 * finding longest subsequence.
	 * return new {a,b}{lo,hi} either side of midline.
	 * i.e. alo+blo <= mid <= ahi+bhi
	 *  and alo,blo to ahi,bhi is a common (possibly empty) subseq
	 *
	 * v is scratch space each is indexable from
	 * alo-bhi to ahi-blo inclusive
	 */

	int klo, khi;
	int k;
	int alo = *alop;
	int ahi = *ahip;
	int blo = *blop;
	int bhi = *bhip;
	int x,y;

	int best = (ahi-alo)+(bhi-blo);
	int dist;

	klo = khi = alo-blo;
	v[klo].x = alo;
	v[klo].l = 0;

	while(1) {

		for (k=klo ; k <= khi ; k+= 2) {
			int snake = 0;
			struct v vnew = v[k];
			x = v[k].x;
			y = x-k;
			if (y > bhi) abort();
			while (x < ahi && y < bhi &&
			       match(&a->list[x], &b->list[y])
				) {
				x++;
				y++;
				snake=1;
			}
			vnew.x = x;
			vnew.l += snake;
			dist = (ahi-x)+(bhi-y);
			if (dist < best) best = dist;
			if (x+y >= mid &&
			    v[k].x+v[k].x-k <= mid) {
				vnew.md = k;
			}
			v[k] = vnew;

			if (dist == 0) {
				/* OK! We have arrived.
				 * We crossed the midpoint at or after v[k].xm,v[k].ym
				 */
				if (x != ahi) abort();
				x = (v[k].md+mid)/2;
				y = x-v[k].md;
				*alop = x;
				*blop = y;

				while (x < ahi && y < bhi &&
				       match(&a->list[x], &b->list[y])
					) {
					x++;
					y++;
				}

				*ahip = x;
				*bhip = y;

				return k;
			}
		}

		for (k=klo+1; k <= khi-1 ; k+= 2) {
			if (v[k-1].x+1 >= v[k+1].x ) {
				v[k] = v[k-1];
				v[k].x++;
			} else {
				v[k] = v[k+1];
			}
		}

		x = v[klo].x; y = x -(klo-1);
		dist = abs((ahi-x)-(bhi-y));
		if (dist <= best) {
			v[klo-1] = v[klo];
			klo --;
		} else
			while (dist > best) {
				klo ++;
				x = v[klo].x; y = x -(klo-1);
				dist = abs((ahi-x)-(bhi-y));
			}

		x = v[khi].x+1; y = x - (khi+1);
		dist = abs((ahi-x)-(bhi-y));
		if (dist <= best) {
			v[khi+1] = v[khi];
			v[khi+1].x++;
			khi ++;
		} else
			while (dist > best) {
				khi --;
				x = v[khi].x+1; y = x - (khi+1);
				dist = abs((ahi-x)-(bhi-y));
			}
	}
}

static struct csl *lcsl(struct file *a, int alo, int ahi,
		 struct file *b, int blo, int bhi,
		 struct csl *csl,
		 struct v *v)
{
	int len;
	int alo1 = alo;
	int ahi1 = ahi;
	int blo1 = blo;
	int bhi1 = bhi;
	struct csl *rv = NULL;
	int k;

	if (ahi <= alo || bhi <= blo)
		return csl;


	k = find_common(a,b,
			&alo1, &ahi1,
			&blo1, &bhi1,
			(ahi+bhi+alo+blo)/2,
			v);
	if (k != ahi-bhi) abort();

	len = v[k].l;

	if (csl == NULL) {
		rv = csl = malloc((len+1)*sizeof(*csl));
		csl->len = 0;
	}
	if (len) {
		csl = lcsl(a,alo,alo1,
			   b,blo,blo1,
			   csl, v);

		if (ahi1 > alo1) {
			/* need to add this common seq, possibly attach
			 * to last
			 */
			if (csl->len &&
			    csl->a+csl->len == alo1 &&
			    csl->b+csl->len == blo1) {
				csl->len += ahi1-alo1;
			} else {
				if (csl->len) csl++;
				csl->len = ahi1-alo1;
				csl->a = alo1;
				csl->b = blo1;
				csl[1].len = 0;
			}
		}
		csl = lcsl(a,ahi1,ahi,
			   b,bhi1,bhi,
			   csl,v);
	}
	if (rv) {
		if (csl->len)
			csl++;
		csl->a = ahi;
		csl->b = bhi;
#if 1
		if (rv+len != csl || csl->len != 0)
			abort(); /* number of runs was wrong */
#endif
		return rv;
	} else
		return csl;
}

/* If two common sequences are separated by only an add or remove,
 * and the first common ends the same as the middle text,
 * extend the second and contract the first in the hope that the
 * first might become empty.  This ameliorates against the greedyness
 * of the 'diff' algorithm.
 * We treat the final zero-length 'csl' as a common sequence which
 * can be extended so we much make sure to add a new zero-length csl
 * to the end.
 * Once this is done, repeat the process but extend the first
 * in favour of the second but only up to the last newline.  This
 * acknowledges that semantic units more often end with common
 * text ("return 0;\n}\n", "\n") than start with it.
 */
static void fixup(struct file *a, struct file *b, struct csl *list)
{
	struct csl *list1, *orig;
	int lasteol = -1;
	int found_end = 0;
	if (!list) return;
	orig = list;
	list1 = list+1;
	while (list->len) {
		if (list1->len == 0)
			found_end = 1;

		if ((list->a+list->len == list1->a &&
		     list->b+list->len != list1->b &&
		     /* text at b inserted */
		     match(&b->list[list->b+list->len-1],
			   &b->list[list1->b-1])
			    )
		    ||
		    (list->b+list->len == list1->b &&
		     list->a+list->len != list1->a &&
		     /* text at a deleted */
		     match(&a->list[list->a+list->len-1],
			   &a->list[list1->a-1])
			    )
			) {
#if 0
			printword(stderr, a->list[list1->a-1]);
			printf("fixup %d,%d %d : %d,%d %d\n",
			       list->a,list->b,list->len,
			       list1->a,list1->b,list1->len);
#endif
			if (ends_line(a->list[list->a+list->len-1])
			    && a->list[list->a+list->len-1].len==1
			    && lasteol == -1
				) {
#if 0
				printf("E\n");
#endif
				lasteol = list1->a-1;
			}
			list1->a--;
			list1->b--;
			list1->len++;
			list->len--;
			if (list->len == 0) {
				lasteol = -1;
				if (found_end) {
					*list = *list1;
					list1->a += list1->len;
					list1->b += list1->len;
					list1->len = 0;
				} else if (list > orig)
					list--;
				else {
					*list = *list1++;
/*					printf("C\n");*/
				}
			}
		} else {
			if (lasteol >= 0) {
/*				printf("seek %d\n", lasteol);*/
				while (list1->a <= lasteol && (list1->len>1 ||
							       (found_end && list1->len > 0))) {
					list1->a++;
					list1->b++;
					list1->len--;
					list->len++;
				}
				lasteol=-1;
			}
			*++list = *list1;
			if (found_end) {
				list1->a += list1->len;
				list1->b += list1->len;
				list1->len = 0;
			} else
				list1++;
		}
		if (list->len && list1 == list) abort();
	}
	// list[1] = list1[0];
}

struct csl *diff(struct file a, struct file b)
{
	struct v *v;
	struct csl *csl;
	v = malloc(sizeof(struct v)*(a.elcnt+b.elcnt+2));
	v += b.elcnt+1;

	csl = lcsl(&a, 0, a.elcnt,
		   &b, 0, b.elcnt,
		   NULL, v);
	free(v-(b.elcnt+1));
	fixup(&a, &b, csl);
	if (!csl) {
		csl = malloc(sizeof(*csl));
		csl->len = 0;
		csl->a = a.elcnt;
		csl->b = b.elcnt;
	}
	return csl;
}

struct csl *diff_partial(struct file a, struct file b,
			 int alo, int ahi, int blo, int bhi)
{
	struct v *v;
	struct csl *csl;
	v = malloc(sizeof(struct v)*(ahi-alo+bhi-blo+2));
	v += bhi-alo+1;

	csl = lcsl(&a, alo, ahi,
		   &b, blo, bhi,
		   NULL, v);
	free(v-(bhi-alo+1));
	fixup(&a, &b, csl);
	return csl;
}


#ifdef MAIN

main(int argc, char *argv[])
{
	struct file a, b;
	struct csl *csl;
	struct elmnt *lst = malloc(argc*sizeof(*lst));
	int arg;
	int alo, ahi, blo, bhi;
	struct v *v;
	int ln;

	arg = 1;
	a.elcnt = 0;
	a.list = lst;
	while (argv[arg] && strcmp(argv[arg],"--")) {
		lst->hash = 0;
		lst->start = argv[arg];
		lst->len = strlen(argv[arg]);
		a.elcnt++;
		lst++;
		arg++;
	}
	if (!argv[arg]) {
		printf("AARGH\n");
		exit(1);
	}
	arg++;
	b.elcnt = 0;
	b.list = lst;
	while (argv[arg] && strcmp(argv[arg],"--")) {
		lst->hash = 0;
		lst->start = argv[arg];
		lst->len = strlen(argv[arg]);
		b.elcnt++;
		lst++;
		arg++;
	}

	v = malloc(sizeof(struct v)*(a.elcnt+b.elcnt+2));
	v += b.elcnt+1;
	alo = blo = 0;
	ahi = a.elcnt;
	bhi = b.elcnt;
#if 0
	ln = find_common(&a, &b,
			 &alo, &ahi, &blo, &bhi,
			 (ahi+bhi)/2,
			 v);

	printf("ln=%d (%d,%d) -> (%d,%d)\n", ln,
	       alo,blo,ahi,bhi);
#else
	csl = lcsl(&a, 0, a.elcnt,
		   &b, 0, b.elcnt,
		   NULL, v);
	fixup(&a, &b, csl);
	while (csl && csl->len) {
		int i;
		printf("%d,%d for %d:\n", csl->a,csl->b,csl->len);
		for (i=0; i<csl->len; i++) {
			printf("  %.*s (%.*s)\n",
			       a.list[csl->a+i].len, a.list[csl->a+i].start,
			       b.list[csl->b+i].len, b.list[csl->b+i].start);
		}
		csl++;
	}
#endif

	exit(0);
}

#endif