1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
2
3 /* Simple box operations */
4
5 /*
6 * Copyright (C) 2005, 2006 Elijah Newren
7 * [meta_rectangle_intersect() is copyright the GTK+ Team according to Havoc,
8 * see gdkrectangle.c. As far as Havoc knows, he probably wrote
9 * meta_rectangle_equal(), and I'm guessing it's (C) Red Hat. So...]
10 * Copyright (C) 1995-2000 GTK+ Team
11 * Copyright (C) 2002 Red Hat, Inc.
12 *
13 * This program is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU General Public License as
15 * published by the Free Software Foundation; either version 2 of the
16 * License, or (at your option) any later version.
17 *
18 * This program is distributed in the hope that it will be useful, but
19 * WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * General Public License for more details.
22 *
23 * You should have received a copy of the GNU General Public License
24 * along with this program; if not, see <http://www.gnu.org/licenses/>.
25 */
26
27 #include "boxes.h"
28 #include "util.h"
29 #include <X11/Xutil.h> /* Just for the definition of the various gravities */
30
31 char*
meta_rectangle_to_string(const MetaRectangle * rect,char * output)32 meta_rectangle_to_string (const MetaRectangle *rect,
33 char *output)
34 {
35 /* 25 chars: 2 commas, space, plus, trailing \0 + 5 for each digit.
36 * Should be more than enough space. Note that of this space, the
37 * trailing \0 will be overwritten for all but the last rectangle.
38 */
39 g_snprintf (output, RECT_LENGTH, "%d,%d +%d,%d",
40 rect->x, rect->y, rect->width, rect->height);
41
42 return output;
43 }
44
45 char*
meta_rectangle_region_to_string(GList * region,const char * separator_string,char * output)46 meta_rectangle_region_to_string (GList *region,
47 const char *separator_string,
48 char *output)
49 {
50 /* 27 chars: 2 commas, 2 square brackets, space, plus, trailing \0 + 5
51 * for each digit. Should be more than enough space. Note that of this
52 * space, the trailing \0 will be overwritten for all but the last
53 * rectangle.
54 */
55 char rect_string[RECT_LENGTH];
56
57 GList *tmp = region;
58 char *cur = output;
59
60 if (region == NULL)
61 g_snprintf (output, 10, "(EMPTY)");
62
63 while (tmp)
64 {
65 MetaRectangle *rect = tmp->data;
66 g_snprintf (rect_string, RECT_LENGTH, "[%d,%d +%d,%d]",
67 rect->x, rect->y, rect->width, rect->height);
68 cur = g_stpcpy (cur, rect_string);
69 tmp = tmp->next;
70 if (tmp)
71 cur = g_stpcpy (cur, separator_string);
72 }
73
74 return output;
75 }
76
77 char*
meta_rectangle_edge_to_string(const MetaEdge * edge,char * output)78 meta_rectangle_edge_to_string (const MetaEdge *edge,
79 char *output)
80 {
81 /* 25 chars: 2 commas, space, plus, trailing \0 + 5 for each digit.
82 * Should be more than enough space. Note that of this space, the
83 * trailing \0 will be overwritten for all but the last rectangle.
84 *
85 * Plus 2 for parenthesis, 4 for 2 more numbers, 2 more commas, and
86 * 2 more spaces, for a total of 10 more.
87 */
88 g_snprintf (output, EDGE_LENGTH, "[%d,%d +%d,%d], %2d, %2d",
89 edge->rect.x, edge->rect.y, edge->rect.width, edge->rect.height,
90 edge->side_type, edge->edge_type);
91
92 return output;
93 }
94
95 char*
meta_rectangle_edge_list_to_string(GList * edge_list,const char * separator_string,char * output)96 meta_rectangle_edge_list_to_string (GList *edge_list,
97 const char *separator_string,
98 char *output)
99 {
100 /* 27 chars: 2 commas, 2 square brackets, space, plus, trailing \0 + 5 for
101 * each digit. Should be more than enough space. Note that of this
102 * space, the trailing \0 will be overwritten for all but the last
103 * rectangle.
104 *
105 * Plus 2 for parenthesis, 4 for 2 more numbers, 2 more commas, and
106 * 2 more spaces, for a total of 10 more.
107 */
108 char rect_string[EDGE_LENGTH];
109
110 char *cur = output;
111 GList *tmp = edge_list;
112
113 if (edge_list == NULL)
114 g_snprintf (output, 10, "(EMPTY)");
115
116 while (tmp)
117 {
118 MetaEdge *edge = tmp->data;
119 MetaRectangle *rect = &edge->rect;
120 g_snprintf (rect_string, EDGE_LENGTH, "([%d,%d +%d,%d], %2d, %2d)",
121 rect->x, rect->y, rect->width, rect->height,
122 edge->side_type, edge->edge_type);
123 cur = g_stpcpy (cur, rect_string);
124 tmp = tmp->next;
125 if (tmp)
126 cur = g_stpcpy (cur, separator_string);
127 }
128
129 return output;
130 }
131
132 MetaRectangle
meta_rect(int x,int y,int width,int height)133 meta_rect (int x, int y, int width, int height)
134 {
135 MetaRectangle temporary;
136 temporary.x = x;
137 temporary.y = y;
138 temporary.width = width;
139 temporary.height = height;
140
141 return temporary;
142 }
143
144 int
meta_rectangle_area(const MetaRectangle * rect)145 meta_rectangle_area (const MetaRectangle *rect)
146 {
147 g_return_val_if_fail (rect != NULL, 0);
148 return rect->width * rect->height;
149 }
150
151 gboolean
meta_rectangle_intersect(const MetaRectangle * src1,const MetaRectangle * src2,MetaRectangle * dest)152 meta_rectangle_intersect (const MetaRectangle *src1,
153 const MetaRectangle *src2,
154 MetaRectangle *dest)
155 {
156 int dest_x, dest_y;
157 int dest_w, dest_h;
158 int return_val;
159
160 g_return_val_if_fail (src1 != NULL, FALSE);
161 g_return_val_if_fail (src2 != NULL, FALSE);
162 g_return_val_if_fail (dest != NULL, FALSE);
163
164 return_val = FALSE;
165
166 dest_x = MAX (src1->x, src2->x);
167 dest_y = MAX (src1->y, src2->y);
168 dest_w = MIN (src1->x + src1->width, src2->x + src2->width) - dest_x;
169 dest_h = MIN (src1->y + src1->height, src2->y + src2->height) - dest_y;
170
171 if (dest_w > 0 && dest_h > 0)
172 {
173 dest->x = dest_x;
174 dest->y = dest_y;
175 dest->width = dest_w;
176 dest->height = dest_h;
177 return_val = TRUE;
178 }
179 else
180 {
181 dest->width = 0;
182 dest->height = 0;
183 }
184
185 return return_val;
186 }
187
188 gboolean
meta_rectangle_equal(const MetaRectangle * src1,const MetaRectangle * src2)189 meta_rectangle_equal (const MetaRectangle *src1,
190 const MetaRectangle *src2)
191 {
192 return ((src1->x == src2->x) &&
193 (src1->y == src2->y) &&
194 (src1->width == src2->width) &&
195 (src1->height == src2->height));
196 }
197
198 void
meta_rectangle_union(const MetaRectangle * rect1,const MetaRectangle * rect2,MetaRectangle * dest)199 meta_rectangle_union (const MetaRectangle *rect1,
200 const MetaRectangle *rect2,
201 MetaRectangle *dest)
202 {
203 int dest_x, dest_y;
204 int dest_w, dest_h;
205
206 dest_x = rect1->x;
207 dest_y = rect1->y;
208 dest_w = rect1->width;
209 dest_h = rect1->height;
210
211 if (rect2->x < dest_x)
212 {
213 dest_w += dest_x - rect2->x;
214 dest_x = rect2->x;
215 }
216 if (rect2->y < dest_y)
217 {
218 dest_h += dest_y - rect2->y;
219 dest_y = rect2->y;
220 }
221 if (rect2->x + rect2->width > dest_x + dest_w)
222 dest_w = rect2->x + rect2->width - dest_x;
223 if (rect2->y + rect2->height > dest_y + dest_h)
224 dest_h = rect2->y + rect2->height - dest_y;
225
226 dest->x = dest_x;
227 dest->y = dest_y;
228 dest->width = dest_w;
229 dest->height = dest_h;
230 }
231
232 gboolean
meta_rectangle_overlap(const MetaRectangle * rect1,const MetaRectangle * rect2)233 meta_rectangle_overlap (const MetaRectangle *rect1,
234 const MetaRectangle *rect2)
235 {
236 g_return_val_if_fail (rect1 != NULL, FALSE);
237 g_return_val_if_fail (rect2 != NULL, FALSE);
238
239 return !((rect1->x + rect1->width <= rect2->x) ||
240 (rect2->x + rect2->width <= rect1->x) ||
241 (rect1->y + rect1->height <= rect2->y) ||
242 (rect2->y + rect2->height <= rect1->y));
243 }
244
245 gboolean
meta_rectangle_vert_overlap(const MetaRectangle * rect1,const MetaRectangle * rect2)246 meta_rectangle_vert_overlap (const MetaRectangle *rect1,
247 const MetaRectangle *rect2)
248 {
249 return (rect1->y < rect2->y + rect2->height &&
250 rect2->y < rect1->y + rect1->height);
251 }
252
253 gboolean
meta_rectangle_horiz_overlap(const MetaRectangle * rect1,const MetaRectangle * rect2)254 meta_rectangle_horiz_overlap (const MetaRectangle *rect1,
255 const MetaRectangle *rect2)
256 {
257 return (rect1->x < rect2->x + rect2->width &&
258 rect2->x < rect1->x + rect1->width);
259 }
260
261 gboolean
meta_rectangle_could_fit_rect(const MetaRectangle * outer_rect,const MetaRectangle * inner_rect)262 meta_rectangle_could_fit_rect (const MetaRectangle *outer_rect,
263 const MetaRectangle *inner_rect)
264 {
265 return (outer_rect->width >= inner_rect->width &&
266 outer_rect->height >= inner_rect->height);
267 }
268
269 gboolean
meta_rectangle_contains_rect(const MetaRectangle * outer_rect,const MetaRectangle * inner_rect)270 meta_rectangle_contains_rect (const MetaRectangle *outer_rect,
271 const MetaRectangle *inner_rect)
272 {
273 return
274 inner_rect->x >= outer_rect->x &&
275 inner_rect->y >= outer_rect->y &&
276 inner_rect->x + inner_rect->width <= outer_rect->x + outer_rect->width &&
277 inner_rect->y + inner_rect->height <= outer_rect->y + outer_rect->height;
278 }
279
280 void
meta_rectangle_resize_with_gravity(const MetaRectangle * old_rect,MetaRectangle * rect,int gravity,int new_width,int new_height)281 meta_rectangle_resize_with_gravity (const MetaRectangle *old_rect,
282 MetaRectangle *rect,
283 int gravity,
284 int new_width,
285 int new_height)
286 {
287 /* FIXME: I'm too deep into this to know whether the below comment is
288 * still clear or not now that I've moved it out of constraints.c.
289 * boxes.h has a good comment, but I'm not sure if the below info is also
290 * helpful on top of that (or whether it has superfluous info).
291 */
292
293 /* These formulas may look overly simplistic at first but you can work
294 * everything out with a left_frame_with, right_frame_width,
295 * border_width, and old and new client area widths (instead of old total
296 * width and new total width) and you come up with the same formulas.
297 *
298 * Also, note that the reason we can treat NorthWestGravity and
299 * StaticGravity the same is because we're not given a location at
300 * which to place the window--the window was already placed
301 * appropriately before. So, NorthWestGravity for this function
302 * means to just leave the upper left corner of the outer window
303 * where it already is, and StaticGravity for this function means to
304 * just leave the upper left corner of the inner window where it
305 * already is. But leaving either of those two corners where they
306 * already are will ensure that the other corner is fixed as well
307 * (since frame size doesn't change)--thus making the two
308 * equivalent.
309 */
310
311 /* First, the x direction */
312 switch (gravity)
313 {
314 case NorthWestGravity:
315 case WestGravity:
316 case SouthWestGravity:
317 rect->x = old_rect->x;
318 break;
319
320 case NorthGravity:
321 case CenterGravity:
322 case SouthGravity:
323 /* FIXME: Needing to adjust new_width kind of sucks, but not doing so
324 * would cause drift.
325 */
326 new_width -= (old_rect->width - new_width) % 2;
327 rect->x = old_rect->x + (old_rect->width - new_width)/2;
328 break;
329
330 case NorthEastGravity:
331 case EastGravity:
332 case SouthEastGravity:
333 rect->x = old_rect->x + (old_rect->width - new_width);
334 break;
335
336 case StaticGravity:
337 default:
338 rect->x = old_rect->x;
339 break;
340 }
341 rect->width = new_width;
342
343 /* Next, the y direction */
344 switch (gravity)
345 {
346 case NorthWestGravity:
347 case NorthGravity:
348 case NorthEastGravity:
349 rect->y = old_rect->y;
350 break;
351
352 case WestGravity:
353 case CenterGravity:
354 case EastGravity:
355 /* FIXME: Needing to adjust new_height kind of sucks, but not doing so
356 * would cause drift.
357 */
358 new_height -= (old_rect->height - new_height) % 2;
359 rect->y = old_rect->y + (old_rect->height - new_height)/2;
360 break;
361
362 case SouthWestGravity:
363 case SouthGravity:
364 case SouthEastGravity:
365 rect->y = old_rect->y + (old_rect->height - new_height);
366 break;
367
368 case StaticGravity:
369 default:
370 rect->y = old_rect->y;
371 break;
372 }
373 rect->height = new_height;
374 }
375
376 /* Not so simple helper function for get_minimal_spanning_set_for_region() */
377 static GList*
merge_spanning_rects_in_region(GList * region)378 merge_spanning_rects_in_region (GList *region)
379 {
380 /* NOTE FOR ANY OPTIMIZATION PEOPLE OUT THERE: Please see the
381 * documentation of get_minimal_spanning_set_for_region() for performance
382 * considerations that also apply to this function.
383 */
384
385 GList* compare;
386 compare = region;
387
388 if (region == NULL)
389 {
390 g_warning ("Region to merge was empty! Either you have a some "
391 "pathological STRUT list or there's a bug somewhere!");
392
393 return NULL;
394 }
395
396 while (compare && compare->next)
397 {
398 MetaRectangle *a = compare->data;
399 GList *other = compare->next;
400
401 g_assert (a->width > 0 && a->height > 0);
402
403 while (other)
404 {
405 MetaRectangle *b = other->data;
406 GList *delete_me = NULL;
407
408 g_assert (b->width > 0 && b->height > 0);
409
410 /* If a contains b, just remove b */
411 if (meta_rectangle_contains_rect (a, b))
412 {
413 delete_me = other;
414 }
415 /* If b contains a, just remove a */
416 else if (meta_rectangle_contains_rect (b, a))
417 {
418 delete_me = compare;
419 }
420 /* If a and b might be mergeable horizontally */
421 else if (a->y == b->y && a->height == b->height)
422 {
423 /* If a and b overlap */
424 if (meta_rectangle_overlap (a, b))
425 {
426 int new_x = MIN (a->x, b->x);
427 a->width = MAX (a->x + a->width, b->x + b->width) - new_x;
428 a->x = new_x;
429 delete_me = other;
430 }
431 /* If a and b are adjacent */
432 else if (a->x + a->width == b->x || a->x == b->x + b->width)
433 {
434 int new_x = MIN (a->x, b->x);
435 a->width = MAX (a->x + a->width, b->x + b->width) - new_x;
436 a->x = new_x;
437 delete_me = other;
438 }
439 }
440 /* If a and b might be mergeable vertically */
441 else if (a->x == b->x && a->width == b->width)
442 {
443 /* If a and b overlap */
444 if (meta_rectangle_overlap (a, b))
445 {
446 int new_y = MIN (a->y, b->y);
447 a->height = MAX (a->y + a->height, b->y + b->height) - new_y;
448 a->y = new_y;
449 delete_me = other;
450 }
451 /* If a and b are adjacent */
452 else if (a->y + a->height == b->y || a->y == b->y + b->height)
453 {
454 int new_y = MIN (a->y, b->y);
455 a->height = MAX (a->y + a->height, b->y + b->height) - new_y;
456 a->y = new_y;
457 delete_me = other;
458 }
459 }
460
461 other = other->next;
462
463 /* Delete any rectangle in the list that is no longer wanted */
464 if (delete_me != NULL)
465 {
466 /* Deleting the rect we compare others to is a little tricker */
467 if (compare == delete_me)
468 {
469 compare = compare->next;
470 other = compare->next;
471 a = compare->data;
472 }
473
474 /* Okay, we can free it now */
475 g_free (delete_me->data);
476 region = g_list_delete_link (region, delete_me);
477 }
478
479 }
480
481 compare = compare->next;
482 }
483
484 return region;
485 }
486
487 /* Simple helper function for get_minimal_spanning_set_for_region()... */
488 static gint
compare_rect_areas(gconstpointer a,gconstpointer b)489 compare_rect_areas (gconstpointer a, gconstpointer b)
490 {
491 const MetaRectangle *a_rect = (gconstpointer) a;
492 const MetaRectangle *b_rect = (gconstpointer) b;
493
494 int a_area = meta_rectangle_area (a_rect);
495 int b_area = meta_rectangle_area (b_rect);
496
497 return b_area - a_area; /* positive ret value denotes b > a, ... */
498 }
499
500 /* This function is trying to find a "minimal spanning set (of rectangles)"
501 * for a given region.
502 *
503 * The region is given by taking basic_rect, then removing the areas
504 * covered by all the rectangles in the all_struts list, and then expanding
505 * the resulting region by the given number of pixels in each direction.
506 *
507 * A "minimal spanning set (of rectangles)" is the best name I could come
508 * up with for the concept I had in mind. Basically, for a given region, I
509 * want a set of rectangles with the property that a window is contained in
510 * the region if and only if it is contained within at least one of the
511 * rectangles.
512 *
513 * The GList* returned will be a list of (allocated) MetaRectangles.
514 * The list will need to be freed by calling
515 * meta_rectangle_free_spanning_set() on it (or by manually
516 * implementing that function...)
517 */
518 GList*
meta_rectangle_get_minimal_spanning_set_for_region(const MetaRectangle * basic_rect,const GSList * all_struts,gboolean skip_middle_struts)519 meta_rectangle_get_minimal_spanning_set_for_region (
520 const MetaRectangle *basic_rect,
521 const GSList *all_struts,
522 gboolean skip_middle_struts)
523 {
524 /* NOTE FOR OPTIMIZERS: This function *might* be somewhat slow,
525 * especially due to the call to merge_spanning_rects_in_region() (which
526 * is O(n^2) where n is the size of the list generated in this function).
527 * This is made more onerous due to the fact that it involves a fair
528 * number of memory allocation and deallocation calls. However, n is 1
529 * for default installations of Gnome (because partial struts aren't used
530 * by default and only partial struts increase the size of the spanning
531 * set generated). With one partial strut, n will be 2 or 3. With 2
532 * partial struts, n will probably be 4 or 5. So, n probably isn't large
533 * enough to make this worth bothering. Further, it is only called from
534 * workspace.c:ensure_work_areas_validated (at least as of the time of
535 * writing this comment), which in turn should only be called if the
536 * strut list changes or the screen or monitor size changes. If it ever
537 * does show up on profiles (most likely because people start using
538 * ridiculously huge numbers of partial struts), possible optimizations
539 * include:
540 *
541 * (1) rewrite merge_spanning_rects_in_region() to be O(n) or O(nlogn).
542 * I'm not totally sure it's possible, but with a couple copies of
543 * the list and sorting them appropriately, I believe it might be.
544 * (2) only call merge_spanning_rects_in_region() with a subset of the
545 * full list of rectangles. I believe from some of my preliminary
546 * debugging and thinking about it that it is possible to figure out
547 * apriori groups of rectangles which are only merge candidates with
548 * each other. (See testboxes.c:get_screen_region() when which==2
549 * and track the steps of this function carefully to see what gave
550 * me the hint that this might work)
551 * (3) figure out how to avoid merge_spanning_rects_in_region(). I think
552 * it might be possible to modify this function to make that
553 * possible, and I spent just a little while thinking about it, but n
554 * wasn't large enough to convince me to care yet.
555 * (4) Some of the stuff Rob mentioned at http://mail.gnome.org/archives\
556 * /metacity-devel-list/2005-November/msg00028.html. (Sorry for the
557 * URL splitting.)
558 */
559
560 GList *ret;
561 GList *tmp_list;
562 const GSList *strut_iter;
563 MetaRectangle *temp_rect;
564
565 /* The algorithm is basically as follows:
566 * Initialize rectangle_set to basic_rect
567 * Foreach strut:
568 * Foreach rectangle in rectangle_set:
569 * - Split the rectangle into new rectangles that don't overlap the
570 * strut (but which are as big as possible otherwise)
571 * - Remove the old (pre-split) rectangle from the rectangle_set,
572 * and replace it with the new rectangles generated from the
573 * splitting
574 */
575
576 temp_rect = g_new (MetaRectangle, 1);
577 *temp_rect = *basic_rect;
578 ret = g_list_prepend (NULL, temp_rect);
579
580 strut_iter = all_struts;
581 for (strut_iter = all_struts; strut_iter; strut_iter = strut_iter->next)
582 {
583 GList *rect_iter;
584 MetaStrut *strut = (MetaStrut *) strut_iter->data;
585 MetaRectangle *strut_rect = &strut->rect;
586
587 if (skip_middle_struts && strut->edge == META_EDGE_MONITOR)
588 {
589 if ((strut->side == META_SIDE_LEFT &&
590 strut_rect->x != basic_rect->x) ||
591 (strut->side == META_SIDE_RIGHT &&
592 strut_rect->x + strut_rect->width != basic_rect->width) ||
593 (strut->side == META_SIDE_TOP &&
594 strut_rect->y != basic_rect->y) ||
595 (strut->side == META_SIDE_BOTTOM &&
596 strut_rect->y + strut_rect->height != basic_rect->height))
597 {
598 continue;
599 }
600 }
601
602 tmp_list = ret;
603 ret = NULL;
604 rect_iter = tmp_list;
605 while (rect_iter)
606 {
607 MetaRectangle *rect = (MetaRectangle*) rect_iter->data;
608 if (!meta_rectangle_overlap (rect, strut_rect))
609 ret = g_list_prepend (ret, rect);
610 else
611 {
612 /* If there is area in rect left of strut */
613 if (BOX_LEFT (*rect) < BOX_LEFT (*strut_rect))
614 {
615 temp_rect = g_new (MetaRectangle, 1);
616 *temp_rect = *rect;
617 temp_rect->width = BOX_LEFT (*strut_rect) - BOX_LEFT (*rect);
618 ret = g_list_prepend (ret, temp_rect);
619 }
620 /* If there is area in rect right of strut */
621 if (BOX_RIGHT (*rect) > BOX_RIGHT (*strut_rect))
622 {
623 int new_x;
624 temp_rect = g_new (MetaRectangle, 1);
625 *temp_rect = *rect;
626 new_x = BOX_RIGHT (*strut_rect);
627 temp_rect->width = BOX_RIGHT(*rect) - new_x;
628 temp_rect->x = new_x;
629 ret = g_list_prepend (ret, temp_rect);
630 }
631 /* If there is area in rect above strut */
632 if (BOX_TOP (*rect) < BOX_TOP (*strut_rect))
633 {
634 temp_rect = g_new (MetaRectangle, 1);
635 *temp_rect = *rect;
636 temp_rect->height = BOX_TOP (*strut_rect) - BOX_TOP (*rect);
637 ret = g_list_prepend (ret, temp_rect);
638 }
639 /* If there is area in rect below strut */
640 if (BOX_BOTTOM (*rect) > BOX_BOTTOM (*strut_rect))
641 {
642 int new_y;
643 temp_rect = g_new (MetaRectangle, 1);
644 *temp_rect = *rect;
645 new_y = BOX_BOTTOM (*strut_rect);
646 temp_rect->height = BOX_BOTTOM (*rect) - new_y;
647 temp_rect->y = new_y;
648 ret = g_list_prepend (ret, temp_rect);
649 }
650 g_free (rect);
651 }
652 rect_iter = rect_iter->next;
653 }
654 g_list_free (tmp_list);
655 }
656
657 /* Sort by maximal area, just because I feel like it... */
658 ret = g_list_sort (ret, compare_rect_areas);
659
660 /* Merge rectangles if possible so that the list really is minimal */
661 ret = merge_spanning_rects_in_region (ret);
662
663 return ret;
664 }
665
666 GList*
meta_rectangle_expand_region(GList * region,const int left_expand,const int right_expand,const int top_expand,const int bottom_expand)667 meta_rectangle_expand_region (GList *region,
668 const int left_expand,
669 const int right_expand,
670 const int top_expand,
671 const int bottom_expand)
672 {
673 return meta_rectangle_expand_region_conditionally (region,
674 left_expand,
675 right_expand,
676 top_expand,
677 bottom_expand,
678 0,
679 0);
680 }
681
682 GList*
meta_rectangle_expand_region_conditionally(GList * region,const int left_expand,const int right_expand,const int top_expand,const int bottom_expand,const int min_x,const int min_y)683 meta_rectangle_expand_region_conditionally (GList *region,
684 const int left_expand,
685 const int right_expand,
686 const int top_expand,
687 const int bottom_expand,
688 const int min_x,
689 const int min_y)
690 {
691 GList *tmp_list = region;
692 while (tmp_list)
693 {
694 MetaRectangle *rect = (MetaRectangle*) tmp_list->data;
695 if (rect->width >= min_x)
696 {
697 rect->x -= left_expand;
698 rect->width += (left_expand + right_expand);
699 }
700 if (rect->height >= min_y)
701 {
702 rect->y -= top_expand;
703 rect->height += (top_expand + bottom_expand);
704 }
705 tmp_list = tmp_list->next;
706 }
707
708 return region;
709 }
710
711 void
meta_rectangle_expand_to_avoiding_struts(MetaRectangle * rect,const MetaRectangle * expand_to,const MetaDirection direction,const GSList * all_struts)712 meta_rectangle_expand_to_avoiding_struts (MetaRectangle *rect,
713 const MetaRectangle *expand_to,
714 const MetaDirection direction,
715 const GSList *all_struts)
716 {
717 const GSList *strut_iter;
718
719 /* If someone wants this function to handle more fine-grained
720 * direction expanding in the future (e.g. only left, or fully
721 * horizontal plus upward), feel free. But I'm hard-coding for both
722 * horizontal directions (exclusive-)or both vertical directions.
723 */
724 g_assert ((direction == META_DIRECTION_HORIZONTAL) ^
725 (direction == META_DIRECTION_VERTICAL ));
726
727 if (direction == META_DIRECTION_HORIZONTAL)
728 {
729 rect->x = expand_to->x;
730 rect->width = expand_to->width;
731 }
732 else
733 {
734 rect->y = expand_to->y;
735 rect->height = expand_to->height;
736 }
737
738
739 /* Run over all struts */
740 for (strut_iter = all_struts; strut_iter; strut_iter = strut_iter->next)
741 {
742 MetaStrut *strut = (MetaStrut*) strut_iter->data;
743
744 /* Skip struts that don't overlap */
745 if (!meta_rectangle_overlap (&strut->rect, rect))
746 continue;
747
748 if (direction == META_DIRECTION_HORIZONTAL)
749 {
750 if (strut->side == META_SIDE_LEFT)
751 {
752 int offset = BOX_RIGHT(strut->rect) - BOX_LEFT(*rect);
753 rect->x += offset;
754 rect->width -= offset;
755 }
756 else if (strut->side == META_SIDE_RIGHT)
757 {
758 int offset = BOX_RIGHT (*rect) - BOX_LEFT(strut->rect);
759 rect->width -= offset;
760 }
761 /* else ignore the strut */
762 }
763 else /* direction == META_DIRECTION_VERTICAL */
764 {
765 if (strut->side == META_SIDE_TOP)
766 {
767 int offset = BOX_BOTTOM(strut->rect) - BOX_TOP(*rect);
768 rect->y += offset;
769 rect->height -= offset;
770 }
771 else if (strut->side == META_SIDE_BOTTOM)
772 {
773 int offset = BOX_BOTTOM(*rect) - BOX_TOP(strut->rect);
774 rect->height -= offset;
775 }
776 /* else ignore the strut */
777 }
778 } /* end loop over struts */
779 } /* end meta_rectangle_expand_to_avoiding_struts */
780
781 gboolean
meta_rectangle_could_fit_in_region(const GList * spanning_rects,const MetaRectangle * rect)782 meta_rectangle_could_fit_in_region (const GList *spanning_rects,
783 const MetaRectangle *rect)
784 {
785 const GList *temp;
786 gboolean could_fit;
787
788 temp = spanning_rects;
789 could_fit = FALSE;
790 while (!could_fit && temp != NULL)
791 {
792 could_fit = could_fit || meta_rectangle_could_fit_rect (temp->data, rect);
793 temp = temp->next;
794 }
795
796 return could_fit;
797 }
798
799 gboolean
meta_rectangle_contained_in_region(const GList * spanning_rects,const MetaRectangle * rect)800 meta_rectangle_contained_in_region (const GList *spanning_rects,
801 const MetaRectangle *rect)
802 {
803 const GList *temp;
804 gboolean contained;
805
806 temp = spanning_rects;
807 contained = FALSE;
808 while (!contained && temp != NULL)
809 {
810 contained = contained || meta_rectangle_contains_rect (temp->data, rect);
811 temp = temp->next;
812 }
813
814 return contained;
815 }
816
817 gboolean
meta_rectangle_overlaps_with_region(const GList * spanning_rects,const MetaRectangle * rect)818 meta_rectangle_overlaps_with_region (const GList *spanning_rects,
819 const MetaRectangle *rect)
820 {
821 const GList *temp;
822 gboolean overlaps;
823
824 temp = spanning_rects;
825 overlaps = FALSE;
826 while (!overlaps && temp != NULL)
827 {
828 overlaps = overlaps || meta_rectangle_overlap (temp->data, rect);
829 temp = temp->next;
830 }
831
832 return overlaps;
833 }
834
835
836 void
meta_rectangle_clamp_to_fit_into_region(const GList * spanning_rects,FixedDirections fixed_directions,MetaRectangle * rect,const MetaRectangle * min_size)837 meta_rectangle_clamp_to_fit_into_region (const GList *spanning_rects,
838 FixedDirections fixed_directions,
839 MetaRectangle *rect,
840 const MetaRectangle *min_size)
841 {
842 const GList *temp;
843 const MetaRectangle *best_rect = NULL;
844 int best_overlap = 0;
845
846 /* First, find best rectangle from spanning_rects to which we can clamp
847 * rect to fit into.
848 */
849 for (temp = spanning_rects; temp; temp = temp->next)
850 {
851 MetaRectangle *compare_rect = temp->data;
852 int maximal_overlap_amount_for_compare;
853
854 /* If x is fixed and the entire width of rect doesn't fit in compare,
855 * skip this rectangle.
856 */
857 if ((fixed_directions & FIXED_DIRECTION_X) &&
858 (compare_rect->x > rect->x ||
859 compare_rect->x + compare_rect->width < rect->x + rect->width))
860 continue;
861
862 /* If y is fixed and the entire height of rect doesn't fit in compare,
863 * skip this rectangle.
864 */
865 if ((fixed_directions & FIXED_DIRECTION_Y) &&
866 (compare_rect->y > rect->y ||
867 compare_rect->y + compare_rect->height < rect->y + rect->height))
868 continue;
869
870 /* If compare can't hold the min_size window, skip this rectangle. */
871 if (compare_rect->width < min_size->width ||
872 compare_rect->height < min_size->height)
873 continue;
874
875 /* Determine maximal overlap amount */
876 maximal_overlap_amount_for_compare =
877 MIN (rect->width, compare_rect->width) *
878 MIN (rect->height, compare_rect->height);
879
880 /* See if this is the best rect so far */
881 if (maximal_overlap_amount_for_compare > best_overlap)
882 {
883 best_rect = compare_rect;
884 best_overlap = maximal_overlap_amount_for_compare;
885 }
886 }
887
888 /* Clamp rect appropriately */
889 if (best_rect == NULL)
890 {
891 g_warning ("No rect whose size to clamp to found!");
892
893 /* If it doesn't fit, at least make it no bigger than it has to be */
894 if (!(fixed_directions & FIXED_DIRECTION_X))
895 rect->width = min_size->width;
896 if (!(fixed_directions & FIXED_DIRECTION_Y))
897 rect->height = min_size->height;
898 }
899 else
900 {
901 rect->width = MIN (rect->width, best_rect->width);
902 rect->height = MIN (rect->height, best_rect->height);
903 }
904 }
905
906 void
meta_rectangle_clip_to_region(const GList * spanning_rects,FixedDirections fixed_directions,MetaRectangle * rect)907 meta_rectangle_clip_to_region (const GList *spanning_rects,
908 FixedDirections fixed_directions,
909 MetaRectangle *rect)
910 {
911 const GList *temp;
912 const MetaRectangle *best_rect = NULL;
913 int best_overlap = 0;
914
915 if (!rect)
916 return;
917
918 /* First, find best rectangle from spanning_rects to which we will clip
919 * rect into.
920 */
921 for (temp = spanning_rects; temp; temp = temp->next)
922 {
923 MetaRectangle *compare_rect = temp->data;
924 MetaRectangle overlap;
925 int maximal_overlap_amount_for_compare;
926
927 /* If x is fixed and the entire width of rect doesn't fit in compare,
928 * skip the rectangle.
929 */
930 if ((fixed_directions & FIXED_DIRECTION_X) &&
931 (compare_rect->x > rect->x ||
932 compare_rect->x + compare_rect->width < rect->x + rect->width))
933 continue;
934
935 /* If y is fixed and the entire height of rect doesn't fit in compare,
936 * skip the rectangle.
937 */
938 if ((fixed_directions & FIXED_DIRECTION_Y) &&
939 (compare_rect->y > rect->y ||
940 compare_rect->y + compare_rect->height < rect->y + rect->height))
941 continue;
942
943 /* Determine maximal overlap amount */
944 if (!meta_rectangle_intersect (rect, compare_rect, &overlap))
945 continue;
946 maximal_overlap_amount_for_compare = meta_rectangle_area (&overlap);
947
948 /* See if this is the best rect so far */
949 if (maximal_overlap_amount_for_compare > best_overlap)
950 {
951 best_rect = compare_rect;
952 best_overlap = maximal_overlap_amount_for_compare;
953 }
954 }
955
956 /* Clip rect appropriately */
957 if (best_rect == NULL)
958 {
959 g_warning ("No rect to clip to found!");
960 }
961 else
962 {
963 /* Extra precaution with checking fixed direction shouldn't be needed
964 * due to logic above, but it shouldn't hurt either.
965 */
966 if (!(fixed_directions & FIXED_DIRECTION_X))
967 {
968 /* Find the new left and right */
969 int new_x = MAX (rect->x, best_rect->x);
970 rect->width = MIN ((rect->x + rect->width) - new_x,
971 (best_rect->x + best_rect->width) - new_x);
972 rect->x = new_x;
973 }
974
975 /* Extra precaution with checking fixed direction shouldn't be needed
976 * due to logic above, but it shouldn't hurt either.
977 */
978 if (!(fixed_directions & FIXED_DIRECTION_Y))
979 {
980 /* Clip the top, if needed */
981 int new_y = MAX (rect->y, best_rect->y);
982 rect->height = MIN ((rect->y + rect->height) - new_y,
983 (best_rect->y + best_rect->height) - new_y);
984 rect->y = new_y;
985 }
986 }
987 }
988
989 void
meta_rectangle_shove_into_region(const GList * spanning_rects,FixedDirections fixed_directions,MetaRectangle * rect)990 meta_rectangle_shove_into_region (const GList *spanning_rects,
991 FixedDirections fixed_directions,
992 MetaRectangle *rect)
993 {
994 const GList *temp;
995 const MetaRectangle *best_rect = NULL;
996 int best_overlap = 0;
997 int shortest_distance = G_MAXINT;
998
999 /* First, find best rectangle from spanning_rects to which we will shove
1000 * rect into.
1001 */
1002
1003 for (temp = spanning_rects; temp; temp = temp->next)
1004 {
1005 MetaRectangle *compare_rect = temp->data;
1006 int maximal_overlap_amount_for_compare;
1007 int dist_to_compare;
1008
1009 /* If x is fixed and the entire width of rect doesn't fit in compare,
1010 * skip this rectangle.
1011 */
1012 if ((fixed_directions & FIXED_DIRECTION_X) &&
1013 (compare_rect->x > rect->x ||
1014 compare_rect->x + compare_rect->width < rect->x + rect->width))
1015 continue;
1016
1017 /* If y is fixed and the entire height of rect doesn't fit in compare,
1018 * skip this rectangle.
1019 */
1020 if ((fixed_directions & FIXED_DIRECTION_Y) &&
1021 (compare_rect->y > rect->y ||
1022 compare_rect->y + compare_rect->height < rect->y + rect->height))
1023 continue;
1024
1025 /* Determine maximal overlap amount between rect & compare_rect */
1026 maximal_overlap_amount_for_compare =
1027 MIN (rect->width, compare_rect->width) *
1028 MIN (rect->height, compare_rect->height);
1029
1030 /* Determine distance necessary to put rect into compare_rect */
1031 dist_to_compare = 0;
1032 if (compare_rect->x > rect->x)
1033 dist_to_compare += compare_rect->x - rect->x;
1034 if (compare_rect->x + compare_rect->width < rect->x + rect->width)
1035 dist_to_compare += (rect->x + rect->width) -
1036 (compare_rect->x + compare_rect->width);
1037 if (compare_rect->y > rect->y)
1038 dist_to_compare += compare_rect->y - rect->y;
1039 if (compare_rect->y + compare_rect->height < rect->y + rect->height)
1040 dist_to_compare += (rect->y + rect->height) -
1041 (compare_rect->y + compare_rect->height);
1042
1043 /* See if this is the best rect so far */
1044 if ((maximal_overlap_amount_for_compare > best_overlap) ||
1045 (maximal_overlap_amount_for_compare == best_overlap &&
1046 dist_to_compare < shortest_distance))
1047 {
1048 best_rect = compare_rect;
1049 best_overlap = maximal_overlap_amount_for_compare;
1050 shortest_distance = dist_to_compare;
1051 }
1052 }
1053
1054 /* Shove rect appropriately */
1055 if (best_rect == NULL)
1056 {
1057 g_warning ("No rect to shove into found!");
1058 }
1059 else
1060 {
1061 /* Extra precaution with checking fixed direction shouldn't be needed
1062 * due to logic above, but it shouldn't hurt either.
1063 */
1064 if (!(fixed_directions & FIXED_DIRECTION_X))
1065 {
1066 /* Shove to the right, if needed */
1067 if (best_rect->x > rect->x)
1068 rect->x = best_rect->x;
1069
1070 /* Shove to the left, if needed */
1071 if (best_rect->x + best_rect->width < rect->x + rect->width)
1072 rect->x = (best_rect->x + best_rect->width) - rect->width;
1073 }
1074
1075 /* Extra precaution with checking fixed direction shouldn't be needed
1076 * due to logic above, but it shouldn't hurt either.
1077 */
1078 if (!(fixed_directions & FIXED_DIRECTION_Y))
1079 {
1080 /* Shove down, if needed */
1081 if (best_rect->y > rect->y)
1082 rect->y = best_rect->y;
1083
1084 /* Shove up, if needed */
1085 if (best_rect->y + best_rect->height < rect->y + rect->height)
1086 rect->y = (best_rect->y + best_rect->height) - rect->height;
1087 }
1088 }
1089 }
1090
1091 void
meta_rectangle_find_linepoint_closest_to_point(double x1,double y1,double x2,double y2,double px,double py,double * valx,double * valy)1092 meta_rectangle_find_linepoint_closest_to_point (double x1,
1093 double y1,
1094 double x2,
1095 double y2,
1096 double px,
1097 double py,
1098 double *valx,
1099 double *valy)
1100 {
1101 /* I'll use the shorthand rx, ry for the return values, valx & valy.
1102 * Now, we need (rx,ry) to be on the line between (x1,y1) and (x2,y2).
1103 * For that to happen, we first need the slope of the line from (x1,y1)
1104 * to (rx,ry) must match the slope of (x1,y1) to (x2,y2), i.e.:
1105 * (ry-y1) (y2-y1)
1106 * ------- = -------
1107 * (rx-x1) (x2-x1)
1108 * If x1==x2, though, this gives divide by zero errors, so we want to
1109 * rewrite the equation by multiplying both sides by (rx-x1)*(x2-x1):
1110 * (ry-y1)(x2-x1) = (y2-y1)(rx-x1)
1111 * This is a valid requirement even when x1==x2 (when x1==x2, this latter
1112 * equation will basically just mean that rx must be equal to both x1 and
1113 * x2)
1114 *
1115 * The other requirement that we have is that the line from (rx,ry) to
1116 * (px,py) must be perpendicular to the line from (x1,y1) to (x2,y2). So
1117 * we just need to get a vector in the direction of each line, take the
1118 * dot product of the two, and ensure that the result is 0:
1119 * (rx-px)*(x2-x1) + (ry-py)*(y2-y1) = 0.
1120 *
1121 * This gives us two equations and two unknowns:
1122 *
1123 * (ry-y1)(x2-x1) = (y2-y1)(rx-x1)
1124 * (rx-px)*(x2-x1) + (ry-py)*(y2-y1) = 0.
1125 *
1126 * This particular pair of equations is always solvable so long as
1127 * (x1,y1) and (x2,y2) are not the same point (and note that anyone who
1128 * calls this function that way is braindead because it means that they
1129 * really didn't specify a line after all). However, the caller should
1130 * be careful to avoid making (x1,y1) and (x2,y2) too close (e.g. like
1131 * 10^{-8} apart in each coordinate), otherwise roundoff error could
1132 * cause issues. Solving these equations by hand (or using Maple(TM) or
1133 * Mathematica(TM) or whatever) results in slightly messy expressions,
1134 * but that's all the below few lines do.
1135 */
1136
1137 double diffx, diffy, den;
1138 diffx = x2 - x1;
1139 diffy = y2 - y1;
1140 den = diffx * diffx + diffy * diffy;
1141
1142 *valx = (py * diffx * diffy + px * diffx * diffx +
1143 y2 * x1 * diffy - y1 * x2 * diffy) / den;
1144 *valy = (px * diffx * diffy + py * diffy * diffy +
1145 x2 * y1 * diffx - x1 * y2 * diffx) / den;
1146 }
1147
1148 /***************************************************************************/
1149 /* */
1150 /* Switching gears to code for edges instead of just rectangles */
1151 /* */
1152 /***************************************************************************/
1153
1154 gboolean
meta_rectangle_edge_aligns(const MetaRectangle * rect,const MetaEdge * edge)1155 meta_rectangle_edge_aligns (const MetaRectangle *rect, const MetaEdge *edge)
1156 {
1157 /* The reason for the usage of <= below instead of < is because we are
1158 * interested in in-the-way-or-adject'ness. So, a left (i.e. vertical
1159 * edge) occupying y positions 0-9 (which has a y of 0 and a height of
1160 * 10) and a rectangle with top at y=10 would be considered to "align" by
1161 * this function.
1162 */
1163 switch (edge->side_type)
1164 {
1165 case META_SIDE_LEFT:
1166 case META_SIDE_RIGHT:
1167 return BOX_TOP (*rect) <= BOX_BOTTOM (edge->rect) &&
1168 BOX_TOP (edge->rect) <= BOX_BOTTOM (*rect);
1169 case META_SIDE_TOP:
1170 case META_SIDE_BOTTOM:
1171 return BOX_LEFT (*rect) <= BOX_RIGHT (edge->rect) &&
1172 BOX_LEFT (edge->rect) <= BOX_RIGHT (*rect);
1173 default:
1174 g_assert_not_reached ();
1175 }
1176 }
1177
1178 static GList*
get_rect_minus_overlap(const GList * rect_in_list,MetaRectangle * overlap)1179 get_rect_minus_overlap (const GList *rect_in_list,
1180 MetaRectangle *overlap)
1181 {
1182 MetaRectangle *temp;
1183 MetaRectangle *rect = rect_in_list->data;
1184 GList *ret = NULL;
1185
1186 if (BOX_LEFT (*rect) < BOX_LEFT (*overlap))
1187 {
1188 temp = g_new (MetaRectangle, 1);
1189 *temp = *rect;
1190 temp->width = BOX_LEFT (*overlap) - BOX_LEFT (*rect);
1191 ret = g_list_prepend (ret, temp);
1192 }
1193 if (BOX_RIGHT (*rect) > BOX_RIGHT (*overlap))
1194 {
1195 temp = g_new (MetaRectangle, 1);
1196 *temp = *rect;
1197 temp->x = BOX_RIGHT (*overlap);
1198 temp->width = BOX_RIGHT (*rect) - BOX_RIGHT (*overlap);
1199 ret = g_list_prepend (ret, temp);
1200 }
1201 if (BOX_TOP (*rect) < BOX_TOP (*overlap))
1202 {
1203 temp = g_new (MetaRectangle, 1);
1204 temp->x = overlap->x;
1205 temp->width = overlap->width;
1206 temp->y = BOX_TOP (*rect);
1207 temp->height = BOX_TOP (*overlap) - BOX_TOP (*rect);
1208 ret = g_list_prepend (ret, temp);
1209 }
1210 if (BOX_BOTTOM (*rect) > BOX_BOTTOM (*overlap))
1211 {
1212 temp = g_new (MetaRectangle, 1);
1213 temp->x = overlap->x;
1214 temp->width = overlap->width;
1215 temp->y = BOX_BOTTOM (*overlap);
1216 temp->height = BOX_BOTTOM (*rect) - BOX_BOTTOM (*overlap);
1217 ret = g_list_prepend (ret, temp);
1218 }
1219
1220 return ret;
1221 }
1222
1223 static GList*
replace_rect_with_list(GList * old_element,GList * new_list)1224 replace_rect_with_list (GList *old_element,
1225 GList *new_list)
1226 {
1227 GList *ret;
1228 g_assert (old_element != NULL);
1229
1230 if (!new_list)
1231 {
1232 /* If there is no new list, just remove the old_element */
1233 ret = g_list_remove_link (old_element, old_element);
1234 }
1235 else
1236 {
1237 /* Fix up the prev and next pointers everywhere */
1238 ret = new_list;
1239 if (old_element->prev)
1240 {
1241 old_element->prev->next = new_list;
1242 new_list->prev = old_element->prev;
1243 }
1244 if (old_element->next)
1245 {
1246 GList *tmp = g_list_last (new_list);
1247 old_element->next->prev = tmp;
1248 tmp->next = old_element->next;
1249 }
1250 }
1251
1252 /* Free the old_element and return the appropriate "next" point */
1253 g_free (old_element->data);
1254 g_list_free_1 (old_element);
1255 return ret;
1256 }
1257
1258 /* Make a copy of the strut list, make sure that copy only contains parts
1259 * of the old_struts that intersect with the region rect, and then do some
1260 * magic to make all the new struts disjoint (okay, we we break up struts
1261 * that aren't disjoint in a way that the overlapping part is only included
1262 * once, so it's not really magic...).
1263 */
1264 static GList*
get_disjoint_strut_rect_list_in_region(const GSList * old_struts,const MetaRectangle * region)1265 get_disjoint_strut_rect_list_in_region (const GSList *old_struts,
1266 const MetaRectangle *region)
1267 {
1268 GList *strut_rects;
1269 GList *tmp;
1270
1271 /* First, copy the list */
1272 strut_rects = NULL;
1273 while (old_struts)
1274 {
1275 MetaRectangle *cur = &((MetaStrut*)old_struts->data)->rect;
1276 MetaRectangle *copy = g_new (MetaRectangle, 1);
1277 *copy = *cur;
1278 if (meta_rectangle_intersect (copy, region, copy))
1279 strut_rects = g_list_prepend (strut_rects, copy);
1280 else
1281 g_free (copy);
1282
1283 old_struts = old_struts->next;
1284 }
1285
1286 /* Now, loop over the list and check for intersections, fixing things up
1287 * where they do intersect.
1288 */
1289 tmp = strut_rects;
1290 while (tmp)
1291 {
1292 GList *compare;
1293
1294 MetaRectangle *cur = tmp->data;
1295
1296 compare = tmp->next;
1297 while (compare)
1298 {
1299 MetaRectangle *comp = compare->data;
1300 MetaRectangle overlap;
1301
1302 if (meta_rectangle_intersect (cur, comp, &overlap))
1303 {
1304 /* Get a list of rectangles for each strut that don't overlap
1305 * the intersection region.
1306 */
1307 GList *cur_leftover = get_rect_minus_overlap (tmp, &overlap);
1308 GList *comp_leftover = get_rect_minus_overlap (compare, &overlap);
1309
1310 /* Add the intersection region to cur_leftover */
1311 MetaRectangle *overlap_allocated = g_new (MetaRectangle, 1);
1312 *overlap_allocated = overlap;
1313 cur_leftover = g_list_prepend (cur_leftover, overlap_allocated);
1314
1315 /* Fix up tmp, compare, and cur -- maybe struts too */
1316 if (strut_rects == tmp)
1317 {
1318 strut_rects = replace_rect_with_list (tmp, cur_leftover);
1319 tmp = strut_rects;
1320 }
1321 else
1322 tmp = replace_rect_with_list (tmp, cur_leftover);
1323 compare = replace_rect_with_list (compare, comp_leftover);
1324
1325 if (compare == NULL)
1326 break;
1327
1328 cur = tmp->data;
1329 }
1330
1331 compare = compare->next;
1332 }
1333
1334 tmp = tmp->next;
1335 }
1336
1337 return strut_rects;
1338 }
1339
1340 gint
meta_rectangle_edge_cmp_ignore_type(gconstpointer a,gconstpointer b)1341 meta_rectangle_edge_cmp_ignore_type (gconstpointer a, gconstpointer b)
1342 {
1343 const MetaEdge *a_edge_rect = (gconstpointer) a;
1344 const MetaEdge *b_edge_rect = (gconstpointer) b;
1345 int a_compare, b_compare;
1346
1347 /* Edges must be both vertical or both horizontal, or it doesn't make
1348 * sense to compare them.
1349 */
1350 g_assert ((a_edge_rect->rect.width == 0 && b_edge_rect->rect.width == 0) ||
1351 (a_edge_rect->rect.height == 0 && b_edge_rect->rect.height == 0));
1352
1353 a_compare = b_compare = 0; /* gcc-3.4.2 sucks at figuring initialized'ness */
1354
1355 if (a_edge_rect->side_type == META_SIDE_LEFT ||
1356 a_edge_rect->side_type == META_SIDE_RIGHT)
1357 {
1358 a_compare = a_edge_rect->rect.x;
1359 b_compare = b_edge_rect->rect.x;
1360 if (a_compare == b_compare)
1361 {
1362 a_compare = a_edge_rect->rect.y;
1363 b_compare = b_edge_rect->rect.y;
1364 }
1365 }
1366 else if (a_edge_rect->side_type == META_SIDE_TOP ||
1367 a_edge_rect->side_type == META_SIDE_BOTTOM)
1368 {
1369 a_compare = a_edge_rect->rect.y;
1370 b_compare = b_edge_rect->rect.y;
1371 if (a_compare == b_compare)
1372 {
1373 a_compare = a_edge_rect->rect.x;
1374 b_compare = b_edge_rect->rect.x;
1375 }
1376 }
1377 else
1378 g_assert ("Some idiot wanted to sort sides of different types.\n");
1379
1380 return a_compare - b_compare; /* positive value denotes a > b ... */
1381 }
1382
1383 /* To make things easily testable, provide a nice way of sorting edges */
1384 gint
meta_rectangle_edge_cmp(gconstpointer a,gconstpointer b)1385 meta_rectangle_edge_cmp (gconstpointer a, gconstpointer b)
1386 {
1387 const MetaEdge *a_edge_rect = (gconstpointer) a;
1388 const MetaEdge *b_edge_rect = (gconstpointer) b;
1389
1390 int a_compare, b_compare;
1391
1392 a_compare = a_edge_rect->side_type;
1393 b_compare = b_edge_rect->side_type;
1394
1395 if (a_compare == b_compare)
1396 return meta_rectangle_edge_cmp_ignore_type (a, b);
1397
1398 return a_compare - b_compare; /* positive value denotes a > b ... */
1399 }
1400
1401 /* Determine whether two given edges overlap */
1402 static gboolean
edges_overlap(const MetaEdge * edge1,const MetaEdge * edge2)1403 edges_overlap (const MetaEdge *edge1,
1404 const MetaEdge *edge2)
1405 {
1406 if (edge1->rect.width == 0 && edge2->rect.width == 0)
1407 {
1408 return meta_rectangle_vert_overlap (&edge1->rect, &edge2->rect) &&
1409 edge1->rect.x == edge2->rect.x;
1410 }
1411 else if (edge1->rect.height == 0 && edge2->rect.height == 0)
1412 {
1413 return meta_rectangle_horiz_overlap (&edge1->rect, &edge2->rect) &&
1414 edge1->rect.y == edge2->rect.y;
1415 }
1416 else
1417 {
1418 return FALSE;
1419 }
1420 }
1421
1422 static gboolean
rectangle_and_edge_intersection(const MetaRectangle * rect,const MetaEdge * edge,MetaEdge * overlap,int * handle_type)1423 rectangle_and_edge_intersection (const MetaRectangle *rect,
1424 const MetaEdge *edge,
1425 MetaEdge *overlap,
1426 int *handle_type)
1427 {
1428 const MetaRectangle *rect2 = &edge->rect;
1429 MetaRectangle *result = &overlap->rect;
1430 gboolean intersect = TRUE;
1431
1432 /* We don't know how to set these, so set them to invalid values */
1433 overlap->edge_type = -1;
1434 overlap->side_type = -1;
1435
1436 /* Figure out what the intersection is */
1437 result->x = MAX (rect->x, rect2->x);
1438 result->y = MAX (rect->y, rect2->y);
1439 result->width = MIN (BOX_RIGHT (*rect), BOX_RIGHT (*rect2)) - result->x;
1440 result->height = MIN (BOX_BOTTOM (*rect), BOX_BOTTOM (*rect2)) - result->y;
1441
1442 /* Find out if the intersection is empty; have to do it this way since
1443 * edges have a thickness of 0
1444 */
1445 if ((result->width < 0 || result->height < 0) ||
1446 (result->width == 0 && result->height == 0))
1447 {
1448 result->width = 0;
1449 result->height = 0;
1450 intersect = FALSE;
1451 }
1452 else
1453 {
1454 /* Need to figure out the handle_type, a somewhat weird quantity:
1455 * 0 - overlap is in middle of rect
1456 * -1 - overlap is at the side of rect, and is on the opposite side
1457 * of rect than the edge->side_type side
1458 * 1 - overlap is at the side of rect, and the side of rect it is
1459 * on is the edge->side_type side
1460 */
1461 switch (edge->side_type)
1462 {
1463 case META_SIDE_LEFT:
1464 if (result->x == rect->x)
1465 *handle_type = 1;
1466 else if (result->x == BOX_RIGHT (*rect))
1467 *handle_type = -1;
1468 else
1469 *handle_type = 0;
1470 break;
1471 case META_SIDE_RIGHT:
1472 if (result->x == rect->x)
1473 *handle_type = -1;
1474 else if (result->x == BOX_RIGHT (*rect))
1475 *handle_type = 1;
1476 else
1477 *handle_type = 0;
1478 break;
1479 case META_SIDE_TOP:
1480 if (result->y == rect->y)
1481 *handle_type = 1;
1482 else if (result->y == BOX_BOTTOM (*rect))
1483 *handle_type = -1;
1484 else
1485 *handle_type = 0;
1486 break;
1487 case META_SIDE_BOTTOM:
1488 if (result->y == rect->y)
1489 *handle_type = -1;
1490 else if (result->y == BOX_BOTTOM (*rect))
1491 *handle_type = 1;
1492 else
1493 *handle_type = 0;
1494 break;
1495 default:
1496 g_assert_not_reached ();
1497 }
1498 }
1499 return intersect;
1500 }
1501
1502 /* Add all edges of the given rect to cur_edges and return the result. If
1503 * rect_is_internal is false, the side types are switched (LEFT<->RIGHT and
1504 * TOP<->BOTTOM).
1505 */
1506 static GList*
add_edges(GList * cur_edges,const MetaRectangle * rect,gboolean rect_is_internal)1507 add_edges (GList *cur_edges,
1508 const MetaRectangle *rect,
1509 gboolean rect_is_internal)
1510 {
1511 MetaEdge *temp_edge;
1512 int i;
1513
1514 for (i=0; i<4; i++)
1515 {
1516 temp_edge = g_new (MetaEdge, 1);
1517 temp_edge->rect = *rect;
1518 switch (i)
1519 {
1520 case 0:
1521 temp_edge->side_type =
1522 rect_is_internal ? META_SIDE_LEFT : META_SIDE_RIGHT;
1523 temp_edge->rect.width = 0;
1524 break;
1525 case 1:
1526 temp_edge->side_type =
1527 rect_is_internal ? META_SIDE_RIGHT : META_SIDE_LEFT;
1528 temp_edge->rect.x += temp_edge->rect.width;
1529 temp_edge->rect.width = 0;
1530 break;
1531 case 2:
1532 temp_edge->side_type =
1533 rect_is_internal ? META_SIDE_TOP : META_SIDE_BOTTOM;
1534 temp_edge->rect.height = 0;
1535 break;
1536 case 3:
1537 temp_edge->side_type =
1538 rect_is_internal ? META_SIDE_BOTTOM : META_SIDE_TOP;
1539 temp_edge->rect.y += temp_edge->rect.height;
1540 temp_edge->rect.height = 0;
1541 break;
1542 default:
1543 break;
1544 }
1545 temp_edge->edge_type = META_EDGE_SCREEN;
1546 cur_edges = g_list_prepend (cur_edges, temp_edge);
1547 }
1548
1549 return cur_edges;
1550 }
1551
1552 /* Remove any part of old_edge that intersects remove and add any resulting
1553 * edges to cur_list. Return cur_list when finished.
1554 */
1555 static GList*
split_edge(GList * cur_list,const MetaEdge * old_edge,const MetaEdge * remove)1556 split_edge (GList *cur_list,
1557 const MetaEdge *old_edge,
1558 const MetaEdge *remove)
1559 {
1560 MetaEdge *temp_edge;
1561 switch (old_edge->side_type)
1562 {
1563 case META_SIDE_LEFT:
1564 case META_SIDE_RIGHT:
1565 g_assert (meta_rectangle_vert_overlap (&old_edge->rect, &remove->rect));
1566 if (BOX_TOP (old_edge->rect) < BOX_TOP (remove->rect))
1567 {
1568 temp_edge = g_new (MetaEdge, 1);
1569 *temp_edge = *old_edge;
1570 temp_edge->rect.height = BOX_TOP (remove->rect)
1571 - BOX_TOP (old_edge->rect);
1572 cur_list = g_list_prepend (cur_list, temp_edge);
1573 }
1574 if (BOX_BOTTOM (old_edge->rect) > BOX_BOTTOM (remove->rect))
1575 {
1576 temp_edge = g_new (MetaEdge, 1);
1577 *temp_edge = *old_edge;
1578 temp_edge->rect.y = BOX_BOTTOM (remove->rect);
1579 temp_edge->rect.height = BOX_BOTTOM (old_edge->rect)
1580 - BOX_BOTTOM (remove->rect);
1581 cur_list = g_list_prepend (cur_list, temp_edge);
1582 }
1583 break;
1584 case META_SIDE_TOP:
1585 case META_SIDE_BOTTOM:
1586 g_assert (meta_rectangle_horiz_overlap (&old_edge->rect, &remove->rect));
1587 if (BOX_LEFT (old_edge->rect) < BOX_LEFT (remove->rect))
1588 {
1589 temp_edge = g_new (MetaEdge, 1);
1590 *temp_edge = *old_edge;
1591 temp_edge->rect.width = BOX_LEFT (remove->rect)
1592 - BOX_LEFT (old_edge->rect);
1593 cur_list = g_list_prepend (cur_list, temp_edge);
1594 }
1595 if (BOX_RIGHT (old_edge->rect) > BOX_RIGHT (remove->rect))
1596 {
1597 temp_edge = g_new (MetaEdge, 1);
1598 *temp_edge = *old_edge;
1599 temp_edge->rect.x = BOX_RIGHT (remove->rect);
1600 temp_edge->rect.width = BOX_RIGHT (old_edge->rect)
1601 - BOX_RIGHT (remove->rect);
1602 cur_list = g_list_prepend (cur_list, temp_edge);
1603 }
1604 break;
1605 default:
1606 g_assert_not_reached ();
1607 }
1608
1609 return cur_list;
1610 }
1611
1612 /* Split up edge and remove preliminary edges from strut_edges depending on
1613 * if and how rect and edge intersect.
1614 */
1615 static void
fix_up_edges(MetaRectangle * rect,MetaEdge * edge,GList ** strut_edges,GList ** edge_splits,gboolean * edge_needs_removal)1616 fix_up_edges (MetaRectangle *rect, MetaEdge *edge,
1617 GList **strut_edges, GList **edge_splits,
1618 gboolean *edge_needs_removal)
1619 {
1620 MetaEdge overlap;
1621 int handle_type;
1622
1623 if (!rectangle_and_edge_intersection (rect, edge, &overlap, &handle_type))
1624 return;
1625
1626 if (handle_type == 0 || handle_type == 1)
1627 {
1628 /* Put the result of removing overlap from edge into edge_splits */
1629 *edge_splits = split_edge (*edge_splits, edge, &overlap);
1630 *edge_needs_removal = TRUE;
1631 }
1632
1633 if (handle_type == -1 || handle_type == 1)
1634 {
1635 /* Remove the overlap from strut_edges */
1636 /* First, loop over the edges of the strut */
1637 GList *tmp = *strut_edges;
1638 while (tmp)
1639 {
1640 MetaEdge *cur = tmp->data;
1641 /* If this is the edge that overlaps, then we need to split it */
1642 if (edges_overlap (cur, &overlap))
1643 {
1644 GList *delete_me = tmp;
1645
1646 /* Split this edge into some new ones */
1647 *strut_edges = split_edge (*strut_edges, cur, &overlap);
1648
1649 /* Delete the old one */
1650 tmp = tmp->next;
1651 g_free (cur);
1652 *strut_edges = g_list_delete_link (*strut_edges, delete_me);
1653 }
1654 else
1655 tmp = tmp->next;
1656 }
1657 }
1658 }
1659
1660 /* This function removes intersections of edges with the rectangles from the
1661 * list of edges.
1662 */
1663 GList*
meta_rectangle_remove_intersections_with_boxes_from_edges(GList * edges,const GSList * rectangles)1664 meta_rectangle_remove_intersections_with_boxes_from_edges (
1665 GList *edges,
1666 const GSList *rectangles)
1667 {
1668 const GSList *rect_iter;
1669 const int opposing = 1;
1670
1671 /* Now remove all intersections of rectangles with the edge list */
1672 rect_iter = rectangles;
1673 while (rect_iter)
1674 {
1675 MetaRectangle *rect = rect_iter->data;
1676 GList *edge_iter = edges;
1677 while (edge_iter)
1678 {
1679 MetaEdge *edge = edge_iter->data;
1680 MetaEdge overlap;
1681 int handle;
1682 gboolean edge_iter_advanced = FALSE;
1683
1684 /* If this edge overlaps with this rect... */
1685 if (rectangle_and_edge_intersection (rect, edge, &overlap, &handle))
1686 {
1687
1688 /* "Intersections" where the edges touch but are opposite
1689 * sides (e.g. a left edge against the right edge) should not
1690 * be split. Note that the comments in
1691 * rectangle_and_edge_intersection() say that opposing edges
1692 * occur when handle is -1, BUT you need to remember that we
1693 * treat the left side of a window as a right edge because
1694 * it's what the right side of the window being moved should
1695 * be-resisted-by/snap-to. So opposing is really 1. Anyway,
1696 * we just keep track of it in the opposing constant set up
1697 * above and if handle isn't equal to that, then we know the
1698 * edge should be split.
1699 */
1700 if (handle != opposing)
1701 {
1702 /* Keep track of this edge so we can delete it below */
1703 GList *delete_me = edge_iter;
1704 edge_iter = edge_iter->next;
1705 edge_iter_advanced = TRUE;
1706
1707 /* Split the edge and add the result to beginning of edges */
1708 edges = split_edge (edges, edge, &overlap);
1709
1710 /* Now free the edge... */
1711 g_free (edge);
1712 edges = g_list_delete_link (edges, delete_me);
1713 }
1714 }
1715
1716 if (!edge_iter_advanced)
1717 edge_iter = edge_iter->next;
1718 }
1719
1720 rect_iter = rect_iter->next;
1721 }
1722
1723 return edges;
1724 }
1725
1726 /* This function is trying to find all the edges of an onscreen region. */
1727 GList*
meta_rectangle_find_onscreen_edges(const MetaRectangle * basic_rect,const GSList * all_struts)1728 meta_rectangle_find_onscreen_edges (const MetaRectangle *basic_rect,
1729 const GSList *all_struts)
1730 {
1731 GList *ret;
1732 GList *fixed_strut_rects;
1733 GList *edge_iter;
1734 const GList *strut_rect_iter;
1735
1736 /* The algorithm is basically as follows:
1737 * Make sure the struts are disjoint
1738 * Initialize the edge_set to the edges of basic_rect
1739 * Foreach strut:
1740 * Put together a preliminary new edge from the edges of the strut
1741 * Foreach edge in edge_set:
1742 * - Split the edge if it is partially contained inside the strut
1743 * - If the edge matches an edge of the strut (i.e. a strut just
1744 * against the edge of the screen or a not-next-to-edge-of-screen
1745 * strut adjacent to another), then both the edge from the
1746 * edge_set and the preliminary edge for the strut will need to
1747 * be split
1748 * Add any remaining "preliminary" strut edges to the edge_set
1749 */
1750
1751 /* Make sure the struts are disjoint */
1752 fixed_strut_rects =
1753 get_disjoint_strut_rect_list_in_region (all_struts, basic_rect);
1754
1755 /* Start off the list with the edges of basic_rect */
1756 ret = add_edges (NULL, basic_rect, TRUE);
1757
1758 strut_rect_iter = fixed_strut_rects;
1759 while (strut_rect_iter)
1760 {
1761 MetaRectangle *strut_rect = (MetaRectangle*) strut_rect_iter->data;
1762
1763 /* Get the new possible edges we may need to add from the strut */
1764 GList *new_strut_edges = add_edges (NULL, strut_rect, FALSE);
1765
1766 edge_iter = ret;
1767 while (edge_iter)
1768 {
1769 MetaEdge *cur_edge = edge_iter->data;
1770 GList *splits_of_cur_edge = NULL;
1771 gboolean edge_needs_removal = FALSE;
1772
1773 fix_up_edges (strut_rect, cur_edge,
1774 &new_strut_edges, &splits_of_cur_edge,
1775 &edge_needs_removal);
1776
1777 if (edge_needs_removal)
1778 {
1779 /* Delete the old edge */
1780 GList *delete_me = edge_iter;
1781 edge_iter = edge_iter->next;
1782 g_free (cur_edge);
1783 ret = g_list_delete_link (ret, delete_me);
1784
1785 /* Add the new split parts of the edge */
1786 ret = g_list_concat (splits_of_cur_edge, ret);
1787 }
1788 else
1789 {
1790 edge_iter = edge_iter->next;
1791 }
1792
1793 /* edge_iter was already advanced above */
1794 }
1795
1796 ret = g_list_concat (new_strut_edges, ret);
1797 strut_rect_iter = strut_rect_iter->next;
1798 }
1799
1800 /* Sort the list */
1801 ret = g_list_sort (ret, meta_rectangle_edge_cmp);
1802
1803 /* Free the fixed struts list */
1804 g_list_free_full (fixed_strut_rects, g_free);
1805
1806 return ret;
1807 }
1808
1809 GList*
meta_rectangle_find_nonintersected_monitor_edges(const MetaRectangle * screen_rect,const GList * monitor_rects,const GSList * all_struts)1810 meta_rectangle_find_nonintersected_monitor_edges (
1811 const MetaRectangle *screen_rect,
1812 const GList *monitor_rects,
1813 const GSList *all_struts)
1814 {
1815 /* This function cannot easily be merged with
1816 * meta_rectangle_find_onscreen_edges() because real screen edges
1817 * and strut edges both are of the type "there ain't anything
1818 * immediately on the other side"; monitor edges are different.
1819 */
1820 GList *ret;
1821 const GList *cur;
1822 GSList *temp_rects;
1823
1824 /* Initialize the return list to be empty */
1825 ret = NULL;
1826
1827 /* start of ret with all the edges of monitors that are adjacent to
1828 * another monitor.
1829 */
1830 cur = monitor_rects;
1831 while (cur)
1832 {
1833 MetaRectangle *cur_rect = cur->data;
1834 MetaEdge *new_edge;
1835
1836 if (BOX_LEFT(*cur_rect) != BOX_LEFT(*screen_rect))
1837 {
1838 new_edge = g_new (MetaEdge, 1);
1839 new_edge->rect = meta_rect (BOX_LEFT (*cur_rect), BOX_TOP (*cur_rect), 0, cur_rect->height);
1840 new_edge->side_type = META_SIDE_LEFT;
1841 new_edge->edge_type = META_EDGE_MONITOR;
1842 ret = g_list_prepend (ret, new_edge);
1843 }
1844 if (BOX_RIGHT(*cur_rect) != BOX_RIGHT(*screen_rect))
1845 {
1846 new_edge = g_new (MetaEdge, 1);
1847 new_edge->rect = meta_rect (BOX_RIGHT (*cur_rect), BOX_TOP (*cur_rect), 0, cur_rect->height);
1848 new_edge->side_type = META_SIDE_RIGHT;
1849 new_edge->edge_type = META_EDGE_MONITOR;
1850 ret = g_list_prepend (ret, new_edge);
1851 }
1852 if (BOX_TOP(*cur_rect) != BOX_TOP(*screen_rect))
1853 {
1854 new_edge = g_new (MetaEdge, 1);
1855 new_edge->rect = meta_rect (BOX_LEFT (*cur_rect), BOX_TOP (*cur_rect), cur_rect->width, 0);
1856 new_edge->side_type = META_SIDE_TOP;
1857 new_edge->edge_type = META_EDGE_MONITOR;
1858 ret = g_list_prepend (ret, new_edge);
1859 }
1860 if (BOX_BOTTOM(*cur_rect) != BOX_BOTTOM(*screen_rect))
1861 {
1862 new_edge = g_new (MetaEdge, 1);
1863 new_edge->rect = meta_rect (BOX_LEFT (*cur_rect), BOX_BOTTOM (*cur_rect), cur_rect->width, 0);
1864 new_edge->side_type = META_SIDE_BOTTOM;
1865 new_edge->edge_type = META_EDGE_MONITOR;
1866 ret = g_list_prepend (ret, new_edge);
1867 }
1868
1869 cur = cur->next;
1870 }
1871
1872 temp_rects = NULL;
1873 for (; all_struts; all_struts = all_struts->next)
1874 temp_rects = g_slist_prepend (temp_rects,
1875 &((MetaStrut*)all_struts->data)->rect);
1876 ret = meta_rectangle_remove_intersections_with_boxes_from_edges (ret,
1877 temp_rects);
1878 g_slist_free (temp_rects);
1879
1880 /* Sort the list */
1881 ret = g_list_sort (ret, meta_rectangle_edge_cmp);
1882
1883 return ret;
1884 }
1885