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