1implement Winplace; 2 3# 4# Copyright © 2003 Vita Nuova Holdings Limited 5# 6 7include "sys.m"; 8 sys: Sys; 9include "draw.m"; 10 draw: Draw; 11 Rect, Point: import draw; 12include "winplace.m"; 13 14Delta: adt { 15 d: int; # +1 or -1 16 wid: int; # index into wr 17 coord: int; # x/y coord 18}; 19 20EW, NS: con iota; 21Lay: adt { 22 d: int; 23 x: fn(l: self Lay, p: Point): int; 24 y: fn(l: self Lay, p: Point): int; 25 mkr: fn(l: self Lay, r: Rect): Rect; 26}; 27 28init() 29{ 30 sys = load Sys Sys->PATH; 31 draw = load Draw Draw->PATH; 32} 33 34place(wins: list of Rect, scr, lastrect: Rect, minsize: Point): Rect 35{ 36 found := find(wins, scr); 37 if(found != nil){ 38 # first look for any spaces big enough to hold minsize; 39 # choose top-left of those available. 40 (ok, best) := findfit(found, minsize); 41 if (ok){ 42 if(minsize.x == 0) 43 return best; 44 return (best.min, best.min.add(minsize)); 45 } 46 if(minsize.x == 0) 47 minsize = scr.size().div(2); 48 } 49 # no big enough space; try to avoid covering titlebars 50 tfound := find(titlebarrects(wins), scr); 51 (ok, best) := findfit(tfound, minsize); 52 if (ok) 53 return (best.min, best.min.add(minsize)); 54 tfound = nil; 55 56 # no areas available - just find somewhere. 57 if(found == nil) 58 return somespace(scr, lastrect, minsize); 59 60 # no big enough space found; find the largest area available 61 # that will fit within minsize 62 best = clipsize(hd found, minsize); 63 area := best.dx() * best.dy(); 64 for (fl := tl found; fl != nil; fl = tl fl) { 65 r := clipsize(hd fl, minsize); 66 rarea := r.dx() * r.dy(); 67 if (rarea > area || (rarea == area && better(r, best))) 68 (area, best) = (rarea, r); 69 } 70 best.max = best.min.add(minsize); 71 return checkrect(best, scr); 72} 73 74findfit(found: list of Rect, minsize: Point): (int, Rect) 75{ 76 best: Rect; 77 ok := 0; 78 for (fl := found; fl != nil; fl = tl fl) { 79 r := hd fl; 80 if (r.dx() < minsize.x || r.dy() < minsize.y) 81 continue; 82 if (!ok || better(r, best)) { 83 best = r; 84 ok++; 85 } 86 } 87 return (ok, best); 88} 89 90TBARWIDTH: con 100; 91TBARHEIGHT: con 20; 92titlebarrects(rl: list of Rect): list of Rect 93{ 94 nl: list of Rect; 95 for (; rl != nil; rl = tl rl) { 96 r := hd rl; 97 tr := Rect((r.max.x - TBARWIDTH, r.min.y), 98 (r.max.x, r.min.y + TBARHEIGHT)); 99 if (tr.min.x < r.min.x) 100 tr.min.x = r.min.x; 101 if (tr.max.y > r.max.y) 102 tr.max.y = r.max.y; 103 nl = tr :: nl; 104 } 105 return nl; 106} 107 108somespace(scr, lastrect: Rect, minsize: Point): Rect 109{ 110 r := Rect(lastrect.min, lastrect.min.add(minsize)).addpt((20, 20)); 111 if (r.max.x > scr.max.x || r.max.y > scr.max.y) 112 r = Rect(scr.min, scr.min.add(minsize)); 113 return r; 114} 115 116checkrect(r, scr: Rect): Rect 117{ 118 # make sure it's all on screen 119 if (r.max.x > scr.max.x) { 120 dx := r.max.x - scr.max.x; 121 r.max.x -= dx; 122 r.min.x -= dx; 123 } 124 if (r.max.y > scr.max.y) { 125 dy := r.max.y - scr.max.y; 126 r.max.y -= dy; 127 r.min.y -= dy; 128 } 129 130 # make sure origin is on screen. 131 off := r.min.sub(scr.min); 132 if (off.x > 0) 133 off.x = 0; 134 if (off.y > 0) 135 off.y = 0; 136 r = r.subpt(off); 137 return r; 138} 139 140# return true if r1 is ``better'' placed than r2, all other things 141# being equal. 142# currently we choose top-most, left-most, in that order. 143better(r1, r2: Rect): int 144{ 145 return r1.min.y < r2.min.y || 146 (r1.min.y == r2.min.y && r1.min.x < r2.min.x); 147} 148 149clipsize(r: Rect, size: Point): Rect 150{ 151 if (r.dx() > size.x) 152 r.max.x = r.min.x + size.x; 153 if (r.dy() > size.y) 154 r.max.y = r.min.y + size.y; 155 return r; 156} 157 158find(wins: list of Rect, scr: Rect): list of Rect 159{ 160 161 n := len wins + 4; 162 wr := array[n] of Rect; 163 for (; wins != nil; wins = tl wins) 164 wr[--n] = hd wins; 165 scr2 := scr.inset(-1); 166 # border sentinels 167 wr[3] = Rect((scr.min.x,scr2.min.y), (scr.max.x, scr.min.y)); # top 168 wr[2] = Rect((scr2.min.x, scr2.min.y), (scr.min.x, scr2.max.y)); # left 169 wr[1] = Rect((scr.min.x, scr.max.y), (scr.max.x, scr2.max.y)); # bottom 170 wr[0] = Rect((scr.max.x, scr2.min.y), (scr2.max.x, scr2.max.y)); # right 171 found := sweep(wr, Lay(EW), nil); 172 return sweep(wr, Lay(NS), found); 173} 174 175sweep(wr: array of Rect, lay: Lay, found: list of Rect): list of Rect 176{ 177 # sweep through in the direction of lay, 178 # adding and removing end points of rectangles 179 # as we pass them, and maintaining list of current viable rectangles. 180 maj := sortcoords(wr, lay); 181 (cr, ncr) := (array[len wr * 2] of Delta, 0); 182 rl: list of Rect; # ordered by lay.y(min) 183 for (i := 0; i < len maj; i++) { 184 wid := maj[i].wid; 185 if (maj[i].d > 0) 186 ncr = addwin(cr, ncr, wid, lay.y(wr[wid].min), lay.y(wr[wid].max)); 187 else 188 ncr = removewin(cr, ncr, wid, lay.y(wr[wid].min), lay.y(wr[wid].max)); 189 nrl: list of Rect = nil; 190 count := 0; 191 for (j := 0; j < ncr - 1; j++) { 192 count += cr[j].d; 193 (start, end) := (cr[j].coord, cr[j+1].coord); 194 if (count == 0 && end > start) { 195 nf: list of Rect; 196 (rl, nrl, nf) = select(rl, nrl, maj[i].coord, start, end); 197 for (; nf != nil; nf = tl nf) 198 found = addfound(found, lay.mkr(hd nf)); 199 } 200 } 201 for (; rl != nil; rl = tl rl) { 202 r := hd rl; 203 r.max.x = maj[i].coord; 204 found = addfound(found, lay.mkr(r)); 205 } 206 for (; nrl != nil; nrl = tl nrl) 207 rl = hd nrl :: rl; 208 nrl = nil; 209 } 210 return found; 211} 212 213addfound(found: list of Rect, r: Rect): list of Rect 214{ 215 if (r.max.x - r.min.x < 1 || 216 r.max.y - r.min.y < 1) 217 return found; 218 return r :: found; 219} 220 221select(rl, nrl: list of Rect, xcoord, start, end: int): (list of Rect, list of Rect, list of Rect) 222{ 223 found: list of Rect; 224 made := 0; 225 while (rl != nil) { 226 r := hd rl; 227 r.max.x = xcoord; 228 (rstart, rend) := (r.min.y, r.max.y); 229 if (rstart >= end) 230 break; 231 addit := 1; 232 if (rstart == start && rend == end) { 233 made = 1; 234 } else { 235 if (!made && rstart > start) { 236 nrl = ((xcoord, start), (xcoord, end)) :: nrl; 237 made = 1; 238 } 239 if (rend > end || rstart < start) { 240 found = r :: found; 241 if (rend > end) 242 rend = end; 243 if (rstart < start) 244 rstart = start; 245 if (rstart >= rend) 246 addit = 0; 247 (r.min.y, r.max.y) = (rstart, rend); 248 } 249 } 250 if (addit) 251 nrl = r :: nrl; 252 rl = tl rl; 253 } 254 if (!made) 255 nrl = ((xcoord, start), (xcoord, end)) :: nrl; 256 return (rl, nrl, found); 257} 258 259removewin(d: array of Delta, nd: int, wid: int, min, max: int): int 260{ 261 minidx := finddelta(d, nd, Delta(+1, wid, min)); 262 maxidx := finddelta(d, nd, Delta(-1, wid, max)); 263 if (minidx == -1 || maxidx == -1 || minidx == maxidx) { 264 sys->fprint(sys->fildes(2), 265 "bad delta find; minidx: %d; maxidx: %d; wid: %d; min: %d; max: %d\n", 266 minidx, maxidx, wid, min, max); 267 raise "panic"; 268 } 269 d[minidx:] = d[minidx + 1:maxidx]; 270 d[maxidx - 1:] = d[maxidx + 1:nd]; 271 return nd - 2; 272} 273 274addwin(d: array of Delta, nd: int, wid: int, min, max: int): int 275{ 276 (minidx, maxidx) := (findcoord(d, nd, min), findcoord(d, nd, max)); 277 d[maxidx + 2:] = d[maxidx:nd]; 278 d[maxidx + 1] = Delta(-1, wid, max); 279 d[minidx + 1:] = d[minidx:maxidx]; 280 d[minidx] = Delta(+1, wid, min); 281 return nd + 2; 282} 283 284finddelta(d: array of Delta, nd: int, df: Delta): int 285{ 286 idx := findcoord(d, nd, df.coord); 287 for (i := idx; i < nd && d[i].coord == df.coord; i++) 288 if (d[i].wid == df.wid && d[i].d == df.d) 289 return i; 290 for (i = idx - 1; i >= 0 && d[i].coord == df.coord; i--) 291 if (d[i].wid == df.wid && d[i].d == df.d) 292 return i; 293 return -1; 294} 295 296findcoord(d: array of Delta, nd: int, coord: int): int 297{ 298 (lo, hi) := (0, nd - 1); 299 while (lo <= hi) { 300 mid := (lo + hi) / 2; 301 if (coord < d[mid].coord) 302 hi = mid - 1; 303 else if (coord > d[mid].coord) 304 lo = mid + 1; 305 else 306 return mid; 307 } 308 return lo; 309} 310 311sortcoords(wr: array of Rect, lay: Lay): array of Delta 312{ 313 a := array[len wr * 2] of Delta; 314 j := 0; 315 for (i := 0; i < len wr; i++) { 316 a[j++] = (+1, i, lay.x(wr[i].min)); 317 a[j++] = (-1, i, lay.x(wr[i].max)); 318 } 319 sortdelta(a); 320 return a; 321} 322 323sortdelta(a: array of Delta) 324{ 325 n := len a; 326 for(m := n; m > 1; ) { 327 if(m < 5) 328 m = 1; 329 else 330 m = (5*m-1)/11; 331 for(i := n-m-1; i >= 0; i--) { 332 tmp := a[i]; 333 for(j := i+m; j <= n-1 && tmp.coord > a[j].coord; j += m) 334 a[j-m] = a[j]; 335 a[j-m] = tmp; 336 } 337 } 338} 339 340Lay.x(l: self Lay, p: Point): int 341{ 342 if (l.d == EW) 343 return p.x; 344 return p.y; 345} 346 347Lay.y(l: self Lay, p: Point): int 348{ 349 if (l.d == EW) 350 return p.y; 351 return p.x; 352} 353 354Lay.mkr(l: self Lay, r: Rect): Rect 355{ 356 if (l.d == EW) 357 return r; 358 return ((r.min.y, r.min.x), (r.max.y, r.max.x)); 359} 360