implement Rectfind;
include "sys.m";
	sys: Sys;
include "draw.m";
	draw: Draw;
	Rect, Point: import draw;
include "tk.m";
include "bufio.m";
	bufio: Bufio;
	Iobuf: import bufio;

Rectfind: module {
	winrect: fn(wins: list of Rect, scr, lastrect: Rect, minsize: Point): Rect;
	findrects: fn(wins: list of Rect, scr: Rect): list of Rect;
	init: fn(nil: ref Draw->Context, argv: list of string);
};

Debug: con 0;
stderr: ref Sys->FD;
init(ctxt: ref Draw->Context, argv: list of string)
{
	sys = load Sys Sys->PATH;
	stderr = sys->fildes(2);
	draw = load Draw Draw->PATH;
	bufio = load Bufio Bufio->PATH;

	argv = tl argv;
	if (len argv != 2 && len argv != 6) {
		sys->fprint(stderr, "usage: rectfind minx miny [lastrect]\n");
		exit;
	}
	rl: list of Rect;
	stdin := bufio->fopen(sys->fildes(0), Sys->OREAD);
	while ((s := stdin.gets('\n')) != nil) {
		(n, toks) := sys->tokenize(s, " \t\n");
		if (n != 4) {
			sys->fprint(stderr, "rectfind: wrong r count #\n");
			exit;
		}
		r := l2r(toks);
		rl = r.canon() :: rl;
	}
	min := Point(int hd argv, int hd tl argv);
	lastrect := Rect((0, 0), (1, 1));
	if (len argv == 6) {
		argv = tl tl argv;
		lastrect = l2r(argv);
	}
	r := winrect(rl, ((0, 0), (500, 400)), lastrect, min);
	sys->print("green %-3d %-3d %-3d %-3d\n", r.min.x, r.min.y, r.max.x, r.max.y);
}

l2r(toks: list of string): Rect
{
	r: Rect;
	(r.min.x, toks) = (int hd toks, tl toks);
	(r.min.y, toks) = (int hd toks, tl toks);
	(r.max.x, toks) = (int hd toks, tl toks);
	(r.max.y, toks) = (int hd toks, tl toks);
	return r;
}

Delta: adt {
	d:		int;	# +1 or -1
	wid:		int;	# index into wr
	coord:	int;	# x/y coord
};

EW, NS: con iota;
Lay: adt {
	d: int;
	x: fn(l: self Lay, p: Point): int;
	y: fn(l: self Lay, p: Point): int;
	mkr: fn(l: self Lay, r: Rect): Rect;
};

winrect(wins: list of Rect, scr, lastrect: Rect, minsize: Point): Rect
{
	found := findrects(wins, scr);
	if (found != nil)
		return bestspace(found, wins, scr, minsize);
	return somespace(scr, lastrect, minsize);
}

bestspace(found, wins: list of Rect, scr: Rect, minsize: Point): Rect
{
	# first look for any spaces big enough to hold minsize;
	# choose top-left of those available.
	(ok, best) := findfit(found, minsize);
	if (ok)
		return (best.min, best.min.add(minsize));
	# no big enough space; try to avoid covering titlebars
	found = findrects(titlebarrects(wins), scr);
	(ok, best) = findfit(found, minsize);
	if (ok)
		return (best.min, best.min.add(minsize));
		
	# no big enough space found; find the largest area available
	# that will fit within minsize
	best = clipsize(hd found, minsize);
	area := best.dx() * best.dy();
	for (fl := tl found; fl != nil; fl = tl fl) {
		r := clipsize(hd fl, minsize);
		rarea := r.dx() * r.dy();
		if (rarea > area || (rarea == area && better(r, best)))
			(area, best) = (rarea, r);
	}
	sys->print("orange %s\n", r2s(best));
	best.max = best.min.add(minsize);
	return checkrect(best, scr);
}

findfit(found: list of Rect, minsize: Point): (int, Rect)
{
	best: Rect;
	ok := 0;
	sys->fprint(stderr, "finding best space (%d candidates)\n", len found);
	for (fl := found; fl != nil; fl = tl fl) {
		r := hd fl;
		sys->print("red %s\n", r2s(r));
		if (r.dx() < minsize.x || r.dy() < minsize.y)
			continue;
		if (!ok || better(r, best)) {
			best = r;
			ok++;
		}
	}
	return (ok, best);
}

TBARWIDTH: con 100;
TBARHEIGHT: con 20;
titlebarrects(rl: list of Rect): list of Rect
{
	nl: list of Rect;
	for (; rl != nil; rl = tl rl) {
		r := hd rl;
		tr := Rect((r.max.x - TBARWIDTH, r.min.y),
					(r.max.x, r.min.y + TBARHEIGHT));
		if (tr.min.x < r.min.x)
			tr.min.x = r.min.x;
		if (tr.max.y > r.max.y)
			tr.max.y = r.max.y;
		nl = tr :: nl;
	}
	return nl;
}

r2s(r: Rect): string
{
	return sys->sprint("%-3d %-3d %-3d %-3d", r.min.x, r.min.y, r.max.x, r.max.y);
}


somespace(scr, lastrect: Rect, minsize: Point): Rect
{
	#sys->print("picking arbitrary space\n");
	r := Rect(lastrect.min.add((20, 20)), lastrect.min.add(minsize));
	if (r.max.x > scr.max.x || r.max.y > scr.max.y)
		r = Rect(scr.min, scr.min.add(minsize));
	return r;
}

checkrect(r, scr: Rect): Rect
{
	# make sure it's all on screen
	if (r.max.x > scr.max.x) {
		dx := r.max.x - scr.max.x;
		r.max.x -= dx;
		r.min.x -= dx;
	}
	if (r.max.y > scr.max.y) {
		dy := r.max.y - scr.max.y;
		r.max.y -= dy;
		r.min.y -= dy;
	}

	# make sure origin is on screen.
	off := r.min.sub(scr.min);
	if (off.x > 0)
		off.x = 0;
	if (off.y > 0)
		off.y = 0;
	r = r.subpt(off);
	return r;
}

# return true if r1 is ``better'' placed than r2, all other things
# being equal.
# currently we choose top-most, left-most, in that order.
better(r1, r2: Rect): int
{
	return r1.min.y < r2.min.y ||
			(r1.min.y == r2.min.y && r1.min.x < r2.min.x);
}

clipsize(r: Rect, size: Point): Rect
{
	if (r.dx() > size.x)
		r.max.x = r.min.x + size.x;
	if (r.dy() > size.y)
		r.max.y = r.min.y + size.y;
	return r;
}

findrects(wins: list of Rect, scr: Rect): list of Rect
{
	n := len wins + 4;
	wr := array[n] of Rect;
	for (; wins != nil; wins = tl wins)
		wr[--n] = hd wins;
	scr2 := scr.inset(-1);
	# border sentinels
	wr[3] = Rect((scr.min.x,scr2.min.y), (scr.max.x, scr.min.y));		# top
	wr[2] = Rect((scr2.min.x, scr2.min.y), (scr.min.x, scr2.max.y));		# left
	wr[1] = Rect((scr.min.x, scr.max.y), (scr.max.x, scr2.max.y));		# bottom
	wr[0] = Rect((scr.max.x, scr2.min.y), (scr2.max.x, scr2.max.y));	# right
	found := sweep(wr, Lay(EW), nil);
	return sweep(wr, Lay(NS), found);
}

sweep(wr: array of Rect, lay: Lay, found: list of Rect): list of Rect
{
	# sweep through in the direction of lay,
	# adding and removing end points of rectangles
	# as we pass them, and maintaining list of current viable rectangles.
	maj := sortcoords(wr, lay);
	(cr, ncr) := (array[len wr * 2] of Delta, 0);
	rl: list of Rect;		# ordered by lay.y(min)
	for (i := 0; i < len maj; i++) {
		wid := maj[i].wid;
		if (maj[i].d > 0)
			ncr = addwin(cr, ncr, wid, lay.y(wr[wid].min), lay.y(wr[wid].max));
		else
			ncr = removewin(cr, ncr, wid, lay.y(wr[wid].min), lay.y(wr[wid].max));
		nrl: list of Rect = nil;
		count := 0;
		for (j := 0; j < ncr - 1; j++) {
			count += cr[j].d;
			(start, end) := (cr[j].coord, cr[j+1].coord);
			if (count == 0 && end > start) {
				nf: list of Rect;
				(rl, nrl, nf) = select(rl, nrl, maj[i].coord, start, end);
				for (; nf != nil; nf = tl nf)
					found = addfound(found, lay.mkr(hd nf));
			}
		}
		for (; rl != nil; rl = tl rl) {
			r := hd rl;
			r.max.x = maj[i].coord;
			found = addfound(found, lay.mkr(r));
		}
		for (; nrl != nil; nrl = tl nrl)
			rl = hd nrl :: rl;
		nrl = nil;
	}
	return found;
}

addfound(found: list of Rect, r: Rect): list of Rect
{
	if (r.max.x - r.min.x < 1 ||
			r.max.y - r.min.y < 1)
		return found;
	return r :: found;
}

select(rl, nrl: list of Rect, xcoord, start, end: int): (list of Rect, list of Rect, list of Rect)
{
	found: list of Rect;
	made := 0;
	while (rl != nil) {
		r := hd rl;
		r.max.x = xcoord;
		(rstart, rend) := (r.min.y, r.max.y);
		if (rstart >= end)
			break;
		addit := 1;
		if (rstart == start && rend == end) {
			made = 1;
		} else {
			if (!made && rstart > start) {
				nrl = ((xcoord, start), (xcoord, end)) :: nrl;
				made = 1;
			}
			if (rend > end || rstart < start) {
				found = r :: found;
				if (rend > end)
					rend = end;
				if (rstart < start)
					rstart = start;
				if (rstart >= rend)
					addit = 0;
				(r.min.y, r.max.y) = (rstart, rend);
			}
		}
		if (addit)
			nrl = r :: nrl;
		rl = tl rl;
	}
	if (!made)
		nrl = ((xcoord, start), (xcoord, end)) :: nrl;
	return (rl, nrl, found);
}

removewin(d: array of Delta, nd: int, wid: int, min, max: int): int
{
	minidx := finddelta(d, nd, Delta(+1, wid, min));
	maxidx := finddelta(d, nd, Delta(-1, wid, max));
	if (minidx == -1 || maxidx == -1 || minidx == maxidx) {
		sys->fprint(sys->fildes(2),
				"bad delta find; minidx: %d; maxidx: %d; wid: %d; min: %d; max: %d\n",
				minidx, maxidx, wid, min, max);
		sys->raise("panic");
	}
	d[minidx:] = d[minidx + 1:maxidx];
	d[maxidx - 1:] = d[maxidx + 1:nd];
	return nd - 2;
}

addwin(d: array of Delta, nd: int, wid: int, min, max: int): int
{
	(minidx, maxidx) := (findcoord(d, nd, min), findcoord(d, nd, max));
	d[maxidx + 2:] = d[maxidx:nd];
	d[maxidx + 1] = Delta(-1, wid, max);
	d[minidx + 1:] = d[minidx:maxidx];
	d[minidx] = Delta(+1, wid, min);
	return nd + 2;
}

finddelta(d: array of Delta, nd: int, df: Delta): int
{
	idx := findcoord(d, nd, df.coord);
	for (i := idx; i < nd && d[i].coord == df.coord; i++)
		if (d[i].wid == df.wid && d[i].d == df.d)
			return i;
	for (i = idx - 1; i >= 0 && d[i].coord == df.coord; i--)
		if (d[i].wid == df.wid && d[i].d == df.d)
			return i;
	return -1;
}

findcoord(d: array of Delta, nd: int, coord: int): int
{
	(lo, hi) := (0, nd - 1);
	while (lo <= hi) {
		mid := (lo + hi) / 2;
		if (coord < d[mid].coord)
			hi = mid - 1;
		else if (coord > d[mid].coord)
			lo = mid + 1;
		else
			return mid;
	}
	return lo;
}

sortcoords(wr: array of Rect, lay: Lay): array of Delta
{
	a := array[len wr * 2] of Delta;
	j := 0;
	for (i := 0; i < len wr; i++) {
		a[j++] = (+1, i, lay.x(wr[i].min));
		a[j++] = (-1, i, lay.x(wr[i].max));
	}
	sortdelta(a);
	return a;
}

sortdelta(a: array of Delta)
{
	n := len a;
	for(m := n; m > 1; ) {
		if(m < 5)
			m = 1;
		else
			m = (5*m-1)/11;
		for(i := n-m-1; i >= 0; i--) {
			tmp := a[i];
			for(j := i+m; j <= n-1 && tmp.coord > a[j].coord; j += m)
				a[j-m] = a[j];
			a[j-m] = tmp;
		}
	}
}

Lay.x(l: self Lay, p: Point): int
{
	if (l.d == EW)
		return p.x;
	return p.y;
}

Lay.y(l: self Lay, p: Point): int
{
	if (l.d == EW)
		return p.y;
	return p.x;
}

Lay.mkr(l: self Lay, r: Rect): Rect
{
	if (l.d == EW)
		return r;
	return ((r.min.y, r.min.x), (r.max.y, r.max.x));
}