1 files changed, 359 insertions, 0 deletions
diff --git a/appl/lib/winplace.b b/appl/lib/winplace.b
new file mode 100644
index 00000000..ed454737
--- /dev/null
+++ b/appl/lib/winplace.b
@@ -0,0 +1,359 @@
+implement Winplace;
+
+#
+# Copyright © 2003 Vita Nuova Holdings Limited
+#
+
+include "sys.m";
+	sys: Sys;
+include "draw.m";
+	draw: Draw;
+	Rect, Point: import draw;
+include "winplace.m";
+
+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;
+};
+
+init()
+{
+	sys = load Sys Sys->PATH;
+	draw = load Draw Draw->PATH;
+}
+
+place(wins: list of Rect, scr, lastrect: Rect, minsize: Point): Rect
+{
+	found := find(wins, scr);
+	if(found != nil){
+		# first look for any spaces big enough to hold minsize;
+		# choose top-left of those available.
+		(ok, best) := findfit(found, minsize);
+		if (ok){
+			if(minsize.x == 0)
+				return best;
+			return (best.min, best.min.add(minsize));
+		}
+		if(minsize.x == 0)
+			minsize = scr.size().div(2);
+	}
+	# no big enough space; try to avoid covering titlebars
+	tfound := find(titlebarrects(wins), scr);
+	(ok, best) := findfit(tfound, minsize);
+	if (ok)
+		return (best.min, best.min.add(minsize));
+	tfound = nil;
+
+	# no areas available - just find somewhere.
+	if(found == nil)
+		return somespace(scr, lastrect, 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);
+	}
+	best.max = best.min.add(minsize);
+	return checkrect(best, scr);
+}
+
+findfit(found: list of Rect, minsize: Point): (int, Rect)
+{
+	best: Rect;
+	ok := 0;
+	for (fl := found; fl != nil; fl = tl fl) {
+		r := hd fl;
+		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;
+}
+
+somespace(scr, lastrect: Rect, minsize: Point): Rect
+{
+	r := Rect(lastrect.min, lastrect.min.add(minsize)).addpt((20, 20));
+	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;
+}
+
+find(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);
+		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));
+}