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