diff options
| author | Perberos <[email protected]> | 2011-12-01 23:52:01 -0300 |
|---|---|---|
| committer | Perberos <[email protected]> | 2011-12-01 23:52:01 -0300 |
| commit | 28a029a4990d2a84f9d6a0b890eba812ea503998 (patch) | |
| tree | 7a69477d0dd6bf351801fa9698d95224e4fe47b6 /src/core/boxes.c | |
| download | marco-28a029a4990d2a84f9d6a0b890eba812ea503998.tar.bz2 marco-28a029a4990d2a84f9d6a0b890eba812ea503998.tar.xz | |
moving from https://github.com/perberos/mate-desktop-environment
Diffstat (limited to 'src/core/boxes.c')
| -rw-r--r-- | src/core/boxes.c | 1926 |
1 files changed, 1926 insertions, 0 deletions
diff --git a/src/core/boxes.c b/src/core/boxes.c new file mode 100644 index 00000000..2ae5f06a --- /dev/null +++ b/src/core/boxes.c @@ -0,0 +1,1926 @@ +/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */ + +/* Simple box operations */ + +/* + * Copyright (C) 2005, 2006 Elijah Newren + * [meta_rectangle_intersect() is copyright the GTK+ Team according to Havoc, + * see gdkrectangle.c. As far as Havoc knows, he probably wrote + * meta_rectangle_equal(), and I'm guessing it's (C) Red Hat. So...] + * Copyright (C) 1995-2000 GTK+ Team + * Copyright (C) 2002 Red Hat, Inc. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#include "boxes.h" +#include "util.h" +#include <X11/Xutil.h> /* Just for the definition of the various gravities */ + +char* +meta_rectangle_to_string (const MetaRectangle *rect, + char *output) +{ + /* 25 chars: 2 commas, space, plus, trailing \0 + 5 for each digit. + * Should be more than enough space. Note that of this space, the + * trailing \0 will be overwritten for all but the last rectangle. + */ + g_snprintf (output, RECT_LENGTH, "%d,%d +%d,%d", + rect->x, rect->y, rect->width, rect->height); + + return output; +} + +char* +meta_rectangle_region_to_string (GList *region, + const char *separator_string, + char *output) +{ + /* 27 chars: 2 commas, 2 square brackets, space, plus, trailing \0 + 5 + * for each digit. Should be more than enough space. Note that of this + * space, the trailing \0 will be overwritten for all but the last + * rectangle. + */ + char rect_string[RECT_LENGTH]; + + GList *tmp = region; + char *cur = output; + + if (region == NULL) + g_snprintf (output, 10, "(EMPTY)"); + + while (tmp) + { + MetaRectangle *rect = tmp->data; + g_snprintf (rect_string, RECT_LENGTH, "[%d,%d +%d,%d]", + rect->x, rect->y, rect->width, rect->height); + cur = g_stpcpy (cur, rect_string); + tmp = tmp->next; + if (tmp) + cur = g_stpcpy (cur, separator_string); + } + + return output; +} + +char* +meta_rectangle_edge_to_string (const MetaEdge *edge, + char *output) +{ + /* 25 chars: 2 commas, space, plus, trailing \0 + 5 for each digit. + * Should be more than enough space. Note that of this space, the + * trailing \0 will be overwritten for all but the last rectangle. + * + * Plus 2 for parenthesis, 4 for 2 more numbers, 2 more commas, and + * 2 more spaces, for a total of 10 more. + */ + g_snprintf (output, EDGE_LENGTH, "[%d,%d +%d,%d], %2d, %2d", + edge->rect.x, edge->rect.y, edge->rect.width, edge->rect.height, + edge->side_type, edge->edge_type); + + return output; +} + +char* +meta_rectangle_edge_list_to_string (GList *edge_list, + const char *separator_string, + char *output) +{ + /* 27 chars: 2 commas, 2 square brackets, space, plus, trailing \0 + 5 for + * each digit. Should be more than enough space. Note that of this + * space, the trailing \0 will be overwritten for all but the last + * rectangle. + * + * Plus 2 for parenthesis, 4 for 2 more numbers, 2 more commas, and + * 2 more spaces, for a total of 10 more. + */ + char rect_string[EDGE_LENGTH]; + + char *cur = output; + GList *tmp = edge_list; + + if (edge_list == NULL) + g_snprintf (output, 10, "(EMPTY)"); + + while (tmp) + { + MetaEdge *edge = tmp->data; + MetaRectangle *rect = &edge->rect; + g_snprintf (rect_string, EDGE_LENGTH, "([%d,%d +%d,%d], %2d, %2d)", + rect->x, rect->y, rect->width, rect->height, + edge->side_type, edge->edge_type); + cur = g_stpcpy (cur, rect_string); + tmp = tmp->next; + if (tmp) + cur = g_stpcpy (cur, separator_string); + } + + return output; +} + +MetaRectangle +meta_rect (int x, int y, int width, int height) +{ + MetaRectangle temporary; + temporary.x = x; + temporary.y = y; + temporary.width = width; + temporary.height = height; + + return temporary; +} + +int +meta_rectangle_area (const MetaRectangle *rect) +{ + g_return_val_if_fail (rect != NULL, 0); + return rect->width * rect->height; +} + +gboolean +meta_rectangle_intersect (const MetaRectangle *src1, + const MetaRectangle *src2, + MetaRectangle *dest) +{ + int dest_x, dest_y; + int dest_w, dest_h; + int return_val; + + g_return_val_if_fail (src1 != NULL, FALSE); + g_return_val_if_fail (src2 != NULL, FALSE); + g_return_val_if_fail (dest != NULL, FALSE); + + return_val = FALSE; + + dest_x = MAX (src1->x, src2->x); + dest_y = MAX (src1->y, src2->y); + dest_w = MIN (src1->x + src1->width, src2->x + src2->width) - dest_x; + dest_h = MIN (src1->y + src1->height, src2->y + src2->height) - dest_y; + + if (dest_w > 0 && dest_h > 0) + { + dest->x = dest_x; + dest->y = dest_y; + dest->width = dest_w; + dest->height = dest_h; + return_val = TRUE; + } + else + { + dest->width = 0; + dest->height = 0; + } + + return return_val; +} + +gboolean +meta_rectangle_equal (const MetaRectangle *src1, + const MetaRectangle *src2) +{ + return ((src1->x == src2->x) && + (src1->y == src2->y) && + (src1->width == src2->width) && + (src1->height == src2->height)); +} + +void +meta_rectangle_union (const MetaRectangle *rect1, + const MetaRectangle *rect2, + MetaRectangle *dest) +{ + int dest_x, dest_y; + int dest_w, dest_h; + + dest_x = rect1->x; + dest_y = rect1->y; + dest_w = rect1->width; + dest_h = rect1->height; + + if (rect2->x < dest_x) + { + dest_w += dest_x - rect2->x; + dest_x = rect2->x; + } + if (rect2->y < dest_y) + { + dest_h += dest_y - rect2->y; + dest_y = rect2->y; + } + if (rect2->x + rect2->width > dest_x + dest_w) + dest_w = rect2->x + rect2->width - dest_x; + if (rect2->y + rect2->height > dest_y + dest_h) + dest_h = rect2->y + rect2->height - dest_y; + + dest->x = dest_x; + dest->y = dest_y; + dest->width = dest_w; + dest->height = dest_h; +} + +gboolean +meta_rectangle_overlap (const MetaRectangle *rect1, + const MetaRectangle *rect2) +{ + g_return_val_if_fail (rect1 != NULL, FALSE); + g_return_val_if_fail (rect2 != NULL, FALSE); + + return !((rect1->x + rect1->width <= rect2->x) || + (rect2->x + rect2->width <= rect1->x) || + (rect1->y + rect1->height <= rect2->y) || + (rect2->y + rect2->height <= rect1->y)); +} + +gboolean +meta_rectangle_vert_overlap (const MetaRectangle *rect1, + const MetaRectangle *rect2) +{ + return (rect1->y < rect2->y + rect2->height && + rect2->y < rect1->y + rect1->height); +} + +gboolean +meta_rectangle_horiz_overlap (const MetaRectangle *rect1, + const MetaRectangle *rect2) +{ + return (rect1->x < rect2->x + rect2->width && + rect2->x < rect1->x + rect1->width); +} + +gboolean +meta_rectangle_could_fit_rect (const MetaRectangle *outer_rect, + const MetaRectangle *inner_rect) +{ + return (outer_rect->width >= inner_rect->width && + outer_rect->height >= inner_rect->height); +} + +gboolean +meta_rectangle_contains_rect (const MetaRectangle *outer_rect, + const MetaRectangle *inner_rect) +{ + return + inner_rect->x >= outer_rect->x && + inner_rect->y >= outer_rect->y && + inner_rect->x + inner_rect->width <= outer_rect->x + outer_rect->width && + inner_rect->y + inner_rect->height <= outer_rect->y + outer_rect->height; +} + +void +meta_rectangle_resize_with_gravity (const MetaRectangle *old_rect, + MetaRectangle *rect, + int gravity, + int new_width, + int new_height) +{ + /* FIXME: I'm too deep into this to know whether the below comment is + * still clear or not now that I've moved it out of constraints.c. + * boxes.h has a good comment, but I'm not sure if the below info is also + * helpful on top of that (or whether it has superfluous info). + */ + + /* These formulas may look overly simplistic at first but you can work + * everything out with a left_frame_with, right_frame_width, + * border_width, and old and new client area widths (instead of old total + * width and new total width) and you come up with the same formulas. + * + * Also, note that the reason we can treat NorthWestGravity and + * StaticGravity the same is because we're not given a location at + * which to place the window--the window was already placed + * appropriately before. So, NorthWestGravity for this function + * means to just leave the upper left corner of the outer window + * where it already is, and StaticGravity for this function means to + * just leave the upper left corner of the inner window where it + * already is. But leaving either of those two corners where they + * already are will ensure that the other corner is fixed as well + * (since frame size doesn't change)--thus making the two + * equivalent. + */ + + /* First, the x direction */ + int adjust = 0; + switch (gravity) + { + case NorthWestGravity: + case WestGravity: + case SouthWestGravity: + rect->x = old_rect->x; + break; + + case NorthGravity: + case CenterGravity: + case SouthGravity: + /* FIXME: Needing to adjust new_width kind of sucks, but not doing so + * would cause drift. + */ + new_width -= (old_rect->width - new_width) % 2; + rect->x = old_rect->x + (old_rect->width - new_width)/2; + break; + + case NorthEastGravity: + case EastGravity: + case SouthEastGravity: + rect->x = old_rect->x + (old_rect->width - new_width); + break; + + case StaticGravity: + default: + rect->x = old_rect->x; + break; + } + rect->width = new_width; + + /* Next, the y direction */ + adjust = 0; + switch (gravity) + { + case NorthWestGravity: + case NorthGravity: + case NorthEastGravity: + rect->y = old_rect->y; + break; + + case WestGravity: + case CenterGravity: + case EastGravity: + /* FIXME: Needing to adjust new_height kind of sucks, but not doing so + * would cause drift. + */ + new_height -= (old_rect->height - new_height) % 2; + rect->y = old_rect->y + (old_rect->height - new_height)/2; + break; + + case SouthWestGravity: + case SouthGravity: + case SouthEastGravity: + rect->y = old_rect->y + (old_rect->height - new_height); + break; + + case StaticGravity: + default: + rect->y = old_rect->y; + break; + } + rect->height = new_height; +} + +/* Not so simple helper function for get_minimal_spanning_set_for_region() */ +static GList* +merge_spanning_rects_in_region (GList *region) +{ + /* NOTE FOR ANY OPTIMIZATION PEOPLE OUT THERE: Please see the + * documentation of get_minimal_spanning_set_for_region() for performance + * considerations that also apply to this function. + */ + + GList* compare; + compare = region; + + if (region == NULL) + { + meta_warning ("Region to merge was empty! Either you have a some " + "pathological STRUT list or there's a bug somewhere!\n"); + return NULL; + } + + while (compare && compare->next) + { + MetaRectangle *a = compare->data; + GList *other = compare->next; + + g_assert (a->width > 0 && a->height > 0); + + while (other) + { + MetaRectangle *b = other->data; + GList *delete_me = NULL; + + g_assert (b->width > 0 && b->height > 0); + + /* If a contains b, just remove b */ + if (meta_rectangle_contains_rect (a, b)) + { + delete_me = other; + } + /* If b contains a, just remove a */ + else if (meta_rectangle_contains_rect (a, b)) + { + delete_me = compare; + } + /* If a and b might be mergeable horizontally */ + else if (a->y == b->y && a->height == b->height) + { + /* If a and b overlap */ + if (meta_rectangle_overlap (a, b)) + { + int new_x = MIN (a->x, b->x); + a->width = MAX (a->x + a->width, b->x + b->width) - new_x; + a->x = new_x; + delete_me = other; + } + /* If a and b are adjacent */ + else if (a->x + a->width == b->x || a->x == b->x + b->width) + { + int new_x = MIN (a->x, b->x); + a->width = MAX (a->x + a->width, b->x + b->width) - new_x; + a->x = new_x; + delete_me = other; + } + } + /* If a and b might be mergeable vertically */ + else if (a->x == b->x && a->width == b->width) + { + /* If a and b overlap */ + if (meta_rectangle_overlap (a, b)) + { + int new_y = MIN (a->y, b->y); + a->height = MAX (a->y + a->height, b->y + b->height) - new_y; + a->y = new_y; + delete_me = other; + } + /* If a and b are adjacent */ + else if (a->y + a->height == b->y || a->y == b->y + b->height) + { + int new_y = MIN (a->y, b->y); + a->height = MAX (a->y + a->height, b->y + b->height) - new_y; + a->y = new_y; + delete_me = other; + } + } + + other = other->next; + + /* Delete any rectangle in the list that is no longer wanted */ + if (delete_me != NULL) + { + /* Deleting the rect we compare others to is a little tricker */ + if (compare == delete_me) + { + compare = compare->next; + other = compare->next; + a = compare->data; + } + + /* Okay, we can free it now */ + g_free (delete_me->data); + region = g_list_delete_link (region, delete_me); + } + + } + + compare = compare->next; + } + + return region; +} + +/* Simple helper function for get_minimal_spanning_set_for_region()... */ +static gint +compare_rect_areas (gconstpointer a, gconstpointer b) +{ + const MetaRectangle *a_rect = (gconstpointer) a; + const MetaRectangle *b_rect = (gconstpointer) b; + + int a_area = meta_rectangle_area (a_rect); + int b_area = meta_rectangle_area (b_rect); + + return b_area - a_area; /* positive ret value denotes b > a, ... */ +} + +/* This function is trying to find a "minimal spanning set (of rectangles)" + * for a given region. + * + * The region is given by taking basic_rect, then removing the areas + * covered by all the rectangles in the all_struts list, and then expanding + * the resulting region by the given number of pixels in each direction. + * + * A "minimal spanning set (of rectangles)" is the best name I could come + * up with for the concept I had in mind. Basically, for a given region, I + * want a set of rectangles with the property that a window is contained in + * the region if and only if it is contained within at least one of the + * rectangles. + * + * The GList* returned will be a list of (allocated) MetaRectangles. + * The list will need to be freed by calling + * meta_rectangle_free_spanning_set() on it (or by manually + * implementing that function...) + */ +GList* +meta_rectangle_get_minimal_spanning_set_for_region ( + const MetaRectangle *basic_rect, + const GSList *all_struts) +{ + /* NOTE FOR OPTIMIZERS: This function *might* be somewhat slow, + * especially due to the call to merge_spanning_rects_in_region() (which + * is O(n^2) where n is the size of the list generated in this function). + * This is made more onerous due to the fact that it involves a fair + * number of memory allocation and deallocation calls. However, n is 1 + * for default installations of Mate (because partial struts aren't used + * by default and only partial struts increase the size of the spanning + * set generated). With one partial strut, n will be 2 or 3. With 2 + * partial struts, n will probably be 4 or 5. So, n probably isn't large + * enough to make this worth bothering. Further, it is only called from + * workspace.c:ensure_work_areas_validated (at least as of the time of + * writing this comment), which in turn should only be called if the + * strut list changes or the screen or xinerama size changes. If it ever + * does show up on profiles (most likely because people start using + * ridiculously huge numbers of partial struts), possible optimizations + * include: + * + * (1) rewrite merge_spanning_rects_in_region() to be O(n) or O(nlogn). + * I'm not totally sure it's possible, but with a couple copies of + * the list and sorting them appropriately, I believe it might be. + * (2) only call merge_spanning_rects_in_region() with a subset of the + * full list of rectangles. I believe from some of my preliminary + * debugging and thinking about it that it is possible to figure out + * apriori groups of rectangles which are only merge candidates with + * each other. (See testboxes.c:get_screen_region() when which==2 + * and track the steps of this function carefully to see what gave + * me the hint that this might work) + * (3) figure out how to avoid merge_spanning_rects_in_region(). I think + * it might be possible to modify this function to make that + * possible, and I spent just a little while thinking about it, but n + * wasn't large enough to convince me to care yet. + * (4) Some of the stuff Rob mentioned at http://mail.gnome.org/archives\ + * /marco-devel-list/2005-November/msg00028.html. (Sorry for the + * URL splitting.) + */ + + GList *ret; + GList *tmp_list; + const GSList *strut_iter; + MetaRectangle *temp_rect; + + /* The algorithm is basically as follows: + * Initialize rectangle_set to basic_rect + * Foreach strut: + * Foreach rectangle in rectangle_set: + * - Split the rectangle into new rectangles that don't overlap the + * strut (but which are as big as possible otherwise) + * - Remove the old (pre-split) rectangle from the rectangle_set, + * and replace it with the new rectangles generated from the + * splitting + */ + + temp_rect = g_new (MetaRectangle, 1); + *temp_rect = *basic_rect; + ret = g_list_prepend (NULL, temp_rect); + + strut_iter = all_struts; + for (strut_iter = all_struts; strut_iter; strut_iter = strut_iter->next) + { + GList *rect_iter; + MetaRectangle *strut_rect = &((MetaStrut*)strut_iter->data)->rect; + + tmp_list = ret; + ret = NULL; + rect_iter = tmp_list; + while (rect_iter) + { + MetaRectangle *rect = (MetaRectangle*) rect_iter->data; + if (!meta_rectangle_overlap (rect, strut_rect)) + ret = g_list_prepend (ret, rect); + else + { + /* If there is area in rect left of strut */ + if (BOX_LEFT (*rect) < BOX_LEFT (*strut_rect)) + { + temp_rect = g_new (MetaRectangle, 1); + *temp_rect = *rect; + temp_rect->width = BOX_LEFT (*strut_rect) - BOX_LEFT (*rect); + ret = g_list_prepend (ret, temp_rect); + } + /* If there is area in rect right of strut */ + if (BOX_RIGHT (*rect) > BOX_RIGHT (*strut_rect)) + { + int new_x; + temp_rect = g_new (MetaRectangle, 1); + *temp_rect = *rect; + new_x = BOX_RIGHT (*strut_rect); + temp_rect->width = BOX_RIGHT(*rect) - new_x; + temp_rect->x = new_x; + ret = g_list_prepend (ret, temp_rect); + } + /* If there is area in rect above strut */ + if (BOX_TOP (*rect) < BOX_TOP (*strut_rect)) + { + temp_rect = g_new (MetaRectangle, 1); + *temp_rect = *rect; + temp_rect->height = BOX_TOP (*strut_rect) - BOX_TOP (*rect); + ret = g_list_prepend (ret, temp_rect); + } + /* If there is area in rect below strut */ + if (BOX_BOTTOM (*rect) > BOX_BOTTOM (*strut_rect)) + { + int new_y; + temp_rect = g_new (MetaRectangle, 1); + *temp_rect = *rect; + new_y = BOX_BOTTOM (*strut_rect); + temp_rect->height = BOX_BOTTOM (*rect) - new_y; + temp_rect->y = new_y; + ret = g_list_prepend (ret, temp_rect); + } + g_free (rect); + } + rect_iter = rect_iter->next; + } + g_list_free (tmp_list); + } + + /* Sort by maximal area, just because I feel like it... */ + ret = g_list_sort (ret, compare_rect_areas); + + /* Merge rectangles if possible so that the list really is minimal */ + ret = merge_spanning_rects_in_region (ret); + + return ret; +} + +GList* +meta_rectangle_expand_region (GList *region, + const int left_expand, + const int right_expand, + const int top_expand, + const int bottom_expand) +{ + return meta_rectangle_expand_region_conditionally (region, + left_expand, + right_expand, + top_expand, + bottom_expand, + 0, + 0); +} + +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) +{ + GList *tmp_list = region; + while (tmp_list) + { + MetaRectangle *rect = (MetaRectangle*) tmp_list->data; + if (rect->width >= min_x) + { + rect->x -= left_expand; + rect->width += (left_expand + right_expand); + } + if (rect->height >= min_y) + { + rect->y -= top_expand; + rect->height += (top_expand + bottom_expand); + } + tmp_list = tmp_list->next; + } + + return region; +} + +void +meta_rectangle_expand_to_avoiding_struts (MetaRectangle *rect, + const MetaRectangle *expand_to, + const MetaDirection direction, + const GSList *all_struts) +{ + const GSList *strut_iter; + + /* If someone wants this function to handle more fine-grained + * direction expanding in the future (e.g. only left, or fully + * horizontal plus upward), feel free. But I'm hard-coding for both + * horizontal directions (exclusive-)or both vertical directions. + */ + g_assert ((direction == META_DIRECTION_HORIZONTAL) ^ + (direction == META_DIRECTION_VERTICAL )); + + if (direction == META_DIRECTION_HORIZONTAL) + { + rect->x = expand_to->x; + rect->width = expand_to->width; + } + else + { + rect->y = expand_to->y; + rect->height = expand_to->height; + } + + + /* Run over all struts */ + for (strut_iter = all_struts; strut_iter; strut_iter = strut_iter->next) + { + MetaStrut *strut = (MetaStrut*) strut_iter->data; + + /* Skip struts that don't overlap */ + if (!meta_rectangle_overlap (&strut->rect, rect)) + continue; + + if (direction == META_DIRECTION_HORIZONTAL) + { + if (strut->side == META_SIDE_LEFT) + { + int offset = BOX_RIGHT(strut->rect) - BOX_LEFT(*rect); + rect->x += offset; + rect->width -= offset; + } + else if (strut->side == META_SIDE_RIGHT) + { + int offset = BOX_RIGHT (*rect) - BOX_LEFT(strut->rect); + rect->width -= offset; + } + /* else ignore the strut */ + } + else /* direction == META_DIRECTION_VERTICAL */ + { + if (strut->side == META_SIDE_TOP) + { + int offset = BOX_BOTTOM(strut->rect) - BOX_TOP(*rect); + rect->y += offset; + rect->height -= offset; + } + else if (strut->side == META_SIDE_BOTTOM) + { + int offset = BOX_BOTTOM(*rect) - BOX_TOP(strut->rect); + rect->height -= offset; + } + /* else ignore the strut */ + } + } /* end loop over struts */ +} /* end meta_rectangle_expand_to_avoiding_struts */ + +void +meta_rectangle_free_list_and_elements (GList *filled_list) +{ + g_list_foreach (filled_list, + (void (*)(gpointer,gpointer))&g_free, /* ew, for ugly */ + NULL); + g_list_free (filled_list); +} + +gboolean +meta_rectangle_could_fit_in_region (const GList *spanning_rects, + const MetaRectangle *rect) +{ + const GList *temp; + gboolean could_fit; + + temp = spanning_rects; + could_fit = FALSE; + while (!could_fit && temp != NULL) + { + could_fit = could_fit || meta_rectangle_could_fit_rect (temp->data, rect); + temp = temp->next; + } + + return could_fit; +} + +gboolean +meta_rectangle_contained_in_region (const GList *spanning_rects, + const MetaRectangle *rect) +{ + const GList *temp; + gboolean contained; + + temp = spanning_rects; + contained = FALSE; + while (!contained && temp != NULL) + { + contained = contained || meta_rectangle_contains_rect (temp->data, rect); + temp = temp->next; + } + + return contained; +} + +gboolean +meta_rectangle_overlaps_with_region (const GList *spanning_rects, + const MetaRectangle *rect) +{ + const GList *temp; + gboolean overlaps; + + temp = spanning_rects; + overlaps = FALSE; + while (!overlaps && temp != NULL) + { + overlaps = overlaps || meta_rectangle_overlap (temp->data, rect); + temp = temp->next; + } + + return overlaps; +} + + +void +meta_rectangle_clamp_to_fit_into_region (const GList *spanning_rects, + FixedDirections fixed_directions, + MetaRectangle *rect, + const MetaRectangle *min_size) +{ + const GList *temp; + const MetaRectangle *best_rect = NULL; + int best_overlap = 0; + + /* First, find best rectangle from spanning_rects to which we can clamp + * rect to fit into. + */ + for (temp = spanning_rects; temp; temp = temp->next) + { + MetaRectangle *compare_rect = temp->data; + int maximal_overlap_amount_for_compare; + + /* If x is fixed and the entire width of rect doesn't fit in compare, + * skip this rectangle. + */ + if ((fixed_directions & FIXED_DIRECTION_X) && + (compare_rect->x > rect->x || + compare_rect->x + compare_rect->width < rect->x + rect->width)) + continue; + + /* If y is fixed and the entire height of rect doesn't fit in compare, + * skip this rectangle. + */ + if ((fixed_directions & FIXED_DIRECTION_Y) && + (compare_rect->y > rect->y || + compare_rect->y + compare_rect->height < rect->y + rect->height)) + continue; + + /* If compare can't hold the min_size window, skip this rectangle. */ + if (compare_rect->width < min_size->width || + compare_rect->height < min_size->height) + continue; + + /* Determine maximal overlap amount */ + maximal_overlap_amount_for_compare = + MIN (rect->width, compare_rect->width) * + MIN (rect->height, compare_rect->height); + + /* See if this is the best rect so far */ + if (maximal_overlap_amount_for_compare > best_overlap) + { + best_rect = compare_rect; + best_overlap = maximal_overlap_amount_for_compare; + } + } + + /* Clamp rect appropriately */ + if (best_rect == NULL) + { + meta_warning ("No rect whose size to clamp to found!\n"); + + /* If it doesn't fit, at least make it no bigger than it has to be */ + if (!(fixed_directions & FIXED_DIRECTION_X)) + rect->width = min_size->width; + if (!(fixed_directions & FIXED_DIRECTION_Y)) + rect->height = min_size->height; + } + else + { + rect->width = MIN (rect->width, best_rect->width); + rect->height = MIN (rect->height, best_rect->height); + } +} + +void +meta_rectangle_clip_to_region (const GList *spanning_rects, + FixedDirections fixed_directions, + MetaRectangle *rect) +{ + const GList *temp; + const MetaRectangle *best_rect = NULL; + int best_overlap = 0; + + /* First, find best rectangle from spanning_rects to which we will clip + * rect into. + */ + for (temp = spanning_rects; temp; temp = temp->next) + { + MetaRectangle *compare_rect = temp->data; + MetaRectangle overlap; + int maximal_overlap_amount_for_compare; + + /* If x is fixed and the entire width of rect doesn't fit in compare, + * skip the rectangle. + */ + if ((fixed_directions & FIXED_DIRECTION_X) && + (compare_rect->x > rect->x || + compare_rect->x + compare_rect->width < rect->x + rect->width)) + continue; + + /* If y is fixed and the entire height of rect doesn't fit in compare, + * skip the rectangle. + */ + if ((fixed_directions & FIXED_DIRECTION_Y) && + (compare_rect->y > rect->y || + compare_rect->y + compare_rect->height < rect->y + rect->height)) + continue; + + /* Determine maximal overlap amount */ + meta_rectangle_intersect (rect, compare_rect, &overlap); + maximal_overlap_amount_for_compare = meta_rectangle_area (&overlap); + + /* See if this is the best rect so far */ + if (maximal_overlap_amount_for_compare > best_overlap) + { + best_rect = compare_rect; + best_overlap = maximal_overlap_amount_for_compare; + } + } + + /* Clip rect appropriately */ + if (best_rect == NULL) + meta_warning ("No rect to clip to found!\n"); + else + { + /* Extra precaution with checking fixed direction shouldn't be needed + * due to logic above, but it shouldn't hurt either. + */ + if (!(fixed_directions & FIXED_DIRECTION_X)) + { + /* Find the new left and right */ + int new_x = MAX (rect->x, best_rect->x); + rect->width = MIN ((rect->x + rect->width) - new_x, + (best_rect->x + best_rect->width) - new_x); + rect->x = new_x; + } + + /* Extra precaution with checking fixed direction shouldn't be needed + * due to logic above, but it shouldn't hurt either. + */ + if (!(fixed_directions & FIXED_DIRECTION_Y)) + { + /* Clip the top, if needed */ + int new_y = MAX (rect->y, best_rect->y); + rect->height = MIN ((rect->y + rect->height) - new_y, + (best_rect->y + best_rect->height) - new_y); + rect->y = new_y; + } + } +} + +void +meta_rectangle_shove_into_region (const GList *spanning_rects, + FixedDirections fixed_directions, + MetaRectangle *rect) +{ + const GList *temp; + const MetaRectangle *best_rect = NULL; + int best_overlap = 0; + int shortest_distance = G_MAXINT; + + /* First, find best rectangle from spanning_rects to which we will shove + * rect into. + */ + + for (temp = spanning_rects; temp; temp = temp->next) + { + MetaRectangle *compare_rect = temp->data; + int maximal_overlap_amount_for_compare; + int dist_to_compare; + + /* If x is fixed and the entire width of rect doesn't fit in compare, + * skip this rectangle. + */ + if ((fixed_directions & FIXED_DIRECTION_X) && + (compare_rect->x > rect->x || + compare_rect->x + compare_rect->width < rect->x + rect->width)) + continue; + + /* If y is fixed and the entire height of rect doesn't fit in compare, + * skip this rectangle. + */ + if ((fixed_directions & FIXED_DIRECTION_Y) && + (compare_rect->y > rect->y || + compare_rect->y + compare_rect->height < rect->y + rect->height)) + continue; + + /* Determine maximal overlap amount between rect & compare_rect */ + maximal_overlap_amount_for_compare = + MIN (rect->width, compare_rect->width) * + MIN (rect->height, compare_rect->height); + + /* Determine distance necessary to put rect into compare_rect */ + dist_to_compare = 0; + if (compare_rect->x > rect->x) + dist_to_compare += compare_rect->x - rect->x; + if (compare_rect->x + compare_rect->width < rect->x + rect->width) + dist_to_compare += (rect->x + rect->width) - + (compare_rect->x + compare_rect->width); + if (compare_rect->y > rect->y) + dist_to_compare += compare_rect->y - rect->y; + if (compare_rect->y + compare_rect->height < rect->y + rect->height) + dist_to_compare += (rect->y + rect->height) - + (compare_rect->y + compare_rect->height); + + /* See if this is the best rect so far */ + if ((maximal_overlap_amount_for_compare > best_overlap) || + (maximal_overlap_amount_for_compare == best_overlap && + dist_to_compare < shortest_distance)) + { + best_rect = compare_rect; + best_overlap = maximal_overlap_amount_for_compare; + shortest_distance = dist_to_compare; + } + } + + /* Shove rect appropriately */ + if (best_rect == NULL) + meta_warning ("No rect to shove into found!\n"); + else + { + /* Extra precaution with checking fixed direction shouldn't be needed + * due to logic above, but it shouldn't hurt either. + */ + if (!(fixed_directions & FIXED_DIRECTION_X)) + { + /* Shove to the right, if needed */ + if (best_rect->x > rect->x) + rect->x = best_rect->x; + + /* Shove to the left, if needed */ + if (best_rect->x + best_rect->width < rect->x + rect->width) + rect->x = (best_rect->x + best_rect->width) - rect->width; + } + + /* Extra precaution with checking fixed direction shouldn't be needed + * due to logic above, but it shouldn't hurt either. + */ + if (!(fixed_directions & FIXED_DIRECTION_Y)) + { + /* Shove down, if needed */ + if (best_rect->y > rect->y) + rect->y = best_rect->y; + + /* Shove up, if needed */ + if (best_rect->y + best_rect->height < rect->y + rect->height) + rect->y = (best_rect->y + best_rect->height) - rect->height; + } + } +} + +void +meta_rectangle_find_linepoint_closest_to_point (double x1, + double y1, + double x2, + double y2, + double px, + double py, + double *valx, + double *valy) +{ + /* I'll use the shorthand rx, ry for the return values, valx & valy. + * Now, we need (rx,ry) to be on the line between (x1,y1) and (x2,y2). + * For that to happen, we first need the slope of the line from (x1,y1) + * to (rx,ry) must match the slope of (x1,y1) to (x2,y2), i.e.: + * (ry-y1) (y2-y1) + * ------- = ------- + * (rx-x1) (x2-x1) + * If x1==x2, though, this gives divide by zero errors, so we want to + * rewrite the equation by multiplying both sides by (rx-x1)*(x2-x1): + * (ry-y1)(x2-x1) = (y2-y1)(rx-x1) + * This is a valid requirement even when x1==x2 (when x1==x2, this latter + * equation will basically just mean that rx must be equal to both x1 and + * x2) + * + * The other requirement that we have is that the line from (rx,ry) to + * (px,py) must be perpendicular to the line from (x1,y1) to (x2,y2). So + * we just need to get a vector in the direction of each line, take the + * dot product of the two, and ensure that the result is 0: + * (rx-px)*(x2-x1) + (ry-py)*(y2-y1) = 0. + * + * This gives us two equations and two unknowns: + * + * (ry-y1)(x2-x1) = (y2-y1)(rx-x1) + * (rx-px)*(x2-x1) + (ry-py)*(y2-y1) = 0. + * + * This particular pair of equations is always solvable so long as + * (x1,y1) and (x2,y2) are not the same point (and note that anyone who + * calls this function that way is braindead because it means that they + * really didn't specify a line after all). However, the caller should + * be careful to avoid making (x1,y1) and (x2,y2) too close (e.g. like + * 10^{-8} apart in each coordinate), otherwise roundoff error could + * cause issues. Solving these equations by hand (or using Maple(TM) or + * Mathematica(TM) or whatever) results in slightly messy expressions, + * but that's all the below few lines do. + */ + + double diffx, diffy, den; + diffx = x2 - x1; + diffy = y2 - y1; + den = diffx * diffx + diffy * diffy; + + *valx = (py * diffx * diffy + px * diffx * diffx + + y2 * x1 * diffy - y1 * x2 * diffy) / den; + *valy = (px * diffx * diffy + py * diffy * diffy + + x2 * y1 * diffx - x1 * y2 * diffx) / den; +} + +/***************************************************************************/ +/* */ +/* Switching gears to code for edges instead of just rectangles */ +/* */ +/***************************************************************************/ + +gboolean +meta_rectangle_edge_aligns (const MetaRectangle *rect, const MetaEdge *edge) +{ + /* The reason for the usage of <= below instead of < is because we are + * interested in in-the-way-or-adject'ness. So, a left (i.e. vertical + * edge) occupying y positions 0-9 (which has a y of 0 and a height of + * 10) and a rectangle with top at y=10 would be considered to "align" by + * this function. + */ + switch (edge->side_type) + { + case META_SIDE_LEFT: + case META_SIDE_RIGHT: + return BOX_TOP (*rect) <= BOX_BOTTOM (edge->rect) && + BOX_TOP (edge->rect) <= BOX_BOTTOM (*rect); + case META_SIDE_TOP: + case META_SIDE_BOTTOM: + return BOX_LEFT (*rect) <= BOX_RIGHT (edge->rect) && + BOX_LEFT (edge->rect) <= BOX_RIGHT (*rect); + default: + g_assert_not_reached (); + } +} + +static GList* +get_rect_minus_overlap (const GList *rect_in_list, + MetaRectangle *overlap) +{ + MetaRectangle *temp; + MetaRectangle *rect = rect_in_list->data; + GList *ret = NULL; + + if (BOX_LEFT (*rect) < BOX_LEFT (*overlap)) + { + temp = g_new (MetaRectangle, 1); + *temp = *rect; + temp->width = BOX_LEFT (*overlap) - BOX_LEFT (*rect); + ret = g_list_prepend (ret, temp); + } + if (BOX_RIGHT (*rect) > BOX_RIGHT (*overlap)) + { + temp = g_new (MetaRectangle, 1); + *temp = *rect; + temp->x = BOX_RIGHT (*overlap); + temp->width = BOX_RIGHT (*rect) - BOX_RIGHT (*overlap); + ret = g_list_prepend (ret, temp); + } + if (BOX_TOP (*rect) < BOX_TOP (*overlap)) + { + temp = g_new (MetaRectangle, 1); + temp->x = overlap->x; + temp->width = overlap->width; + temp->y = BOX_TOP (*rect); + temp->height = BOX_TOP (*overlap) - BOX_TOP (*rect); + ret = g_list_prepend (ret, temp); + } + if (BOX_BOTTOM (*rect) > BOX_BOTTOM (*overlap)) + { + temp = g_new (MetaRectangle, 1); + temp->x = overlap->x; + temp->width = overlap->width; + temp->y = BOX_BOTTOM (*overlap); + temp->height = BOX_BOTTOM (*rect) - BOX_BOTTOM (*overlap); + ret = g_list_prepend (ret, temp); + } + + return ret; +} + +static GList* +replace_rect_with_list (GList *old_element, + GList *new_list) +{ + GList *ret; + g_assert (old_element != NULL); + + if (!new_list) + { + /* If there is no new list, just remove the old_element */ + ret = g_list_remove_link (old_element, old_element); + } + else + { + /* Fix up the prev and next pointers everywhere */ + ret = new_list; + if (old_element->prev) + { + old_element->prev->next = new_list; + new_list->prev = old_element->prev; + } + if (old_element->next) + { + GList *tmp = g_list_last (new_list); + old_element->next->prev = tmp; + tmp->next = old_element->next; + } + } + + /* Free the old_element and return the appropriate "next" point */ + g_free (old_element->data); + g_list_free_1 (old_element); + return ret; +} + +/* Make a copy of the strut list, make sure that copy only contains parts + * of the old_struts that intersect with the region rect, and then do some + * magic to make all the new struts disjoint (okay, we we break up struts + * that aren't disjoint in a way that the overlapping part is only included + * once, so it's not really magic...). + */ +static GList* +get_disjoint_strut_rect_list_in_region (const GSList *old_struts, + const MetaRectangle *region) +{ + GList *strut_rects; + GList *tmp; + + /* First, copy the list */ + strut_rects = NULL; + while (old_struts) + { + MetaRectangle *cur = &((MetaStrut*)old_struts->data)->rect; + MetaRectangle *copy = g_new (MetaRectangle, 1); + *copy = *cur; + if (meta_rectangle_intersect (copy, region, copy)) + strut_rects = g_list_prepend (strut_rects, copy); + else + g_free (copy); + + old_struts = old_struts->next; + } + + /* Now, loop over the list and check for intersections, fixing things up + * where they do intersect. + */ + tmp = strut_rects; + while (tmp) + { + GList *compare; + + MetaRectangle *cur = tmp->data; + + compare = tmp->next; + while (compare) + { + MetaRectangle *comp = compare->data; + MetaRectangle overlap; + + if (meta_rectangle_intersect (cur, comp, &overlap)) + { + /* Get a list of rectangles for each strut that don't overlap + * the intersection region. + */ + GList *cur_leftover = get_rect_minus_overlap (tmp, &overlap); + GList *comp_leftover = get_rect_minus_overlap (compare, &overlap); + + /* Add the intersection region to cur_leftover */ + MetaRectangle *overlap_allocated = g_new (MetaRectangle, 1); + *overlap_allocated = overlap; + cur_leftover = g_list_prepend (cur_leftover, overlap_allocated); + + /* Fix up tmp, compare, and cur -- maybe struts too */ + if (strut_rects == tmp) + { + strut_rects = replace_rect_with_list (tmp, cur_leftover); + tmp = strut_rects; + } + else + tmp = replace_rect_with_list (tmp, cur_leftover); + compare = replace_rect_with_list (compare, comp_leftover); + + if (compare == NULL) + break; + + cur = tmp->data; + } + + compare = compare->next; + } + + tmp = tmp->next; + } + + return strut_rects; +} + +gint +meta_rectangle_edge_cmp_ignore_type (gconstpointer a, gconstpointer b) +{ + const MetaEdge *a_edge_rect = (gconstpointer) a; + const MetaEdge *b_edge_rect = (gconstpointer) b; + int a_compare, b_compare; + + /* Edges must be both vertical or both horizontal, or it doesn't make + * sense to compare them. + */ + g_assert ((a_edge_rect->rect.width == 0 && b_edge_rect->rect.width == 0) || + (a_edge_rect->rect.height == 0 && b_edge_rect->rect.height == 0)); + + a_compare = b_compare = 0; /* gcc-3.4.2 sucks at figuring initialized'ness */ + + if (a_edge_rect->side_type == META_SIDE_LEFT || + a_edge_rect->side_type == META_SIDE_RIGHT) + { + a_compare = a_edge_rect->rect.x; + b_compare = b_edge_rect->rect.x; + if (a_compare == b_compare) + { + a_compare = a_edge_rect->rect.y; + b_compare = b_edge_rect->rect.y; + } + } + else if (a_edge_rect->side_type == META_SIDE_TOP || + a_edge_rect->side_type == META_SIDE_BOTTOM) + { + a_compare = a_edge_rect->rect.y; + b_compare = b_edge_rect->rect.y; + if (a_compare == b_compare) + { + a_compare = a_edge_rect->rect.x; + b_compare = b_edge_rect->rect.x; + } + } + else + g_assert ("Some idiot wanted to sort sides of different types.\n"); + + return a_compare - b_compare; /* positive value denotes a > b ... */ +} + +/* To make things easily testable, provide a nice way of sorting edges */ +gint +meta_rectangle_edge_cmp (gconstpointer a, gconstpointer b) +{ + const MetaEdge *a_edge_rect = (gconstpointer) a; + const MetaEdge *b_edge_rect = (gconstpointer) b; + + int a_compare, b_compare; + + a_compare = a_edge_rect->side_type; + b_compare = b_edge_rect->side_type; + + if (a_compare == b_compare) + return meta_rectangle_edge_cmp_ignore_type (a, b); + + return a_compare - b_compare; /* positive value denotes a > b ... */ +} + +/* Determine whether two given edges overlap */ +static gboolean +edges_overlap (const MetaEdge *edge1, + const MetaEdge *edge2) +{ + if (edge1->rect.width == 0 && edge2->rect.width == 0) + { + return meta_rectangle_vert_overlap (&edge1->rect, &edge2->rect) && + edge1->rect.x == edge2->rect.x; + } + else if (edge1->rect.height == 0 && edge2->rect.height == 0) + { + return meta_rectangle_horiz_overlap (&edge1->rect, &edge2->rect) && + edge1->rect.y == edge2->rect.y; + } + else + { + return FALSE; + } +} + +static gboolean +rectangle_and_edge_intersection (const MetaRectangle *rect, + const MetaEdge *edge, + MetaEdge *overlap, + int *handle_type) +{ + const MetaRectangle *rect2 = &edge->rect; + MetaRectangle *result = &overlap->rect; + gboolean intersect = TRUE; + + /* We don't know how to set these, so set them to invalid values */ + overlap->edge_type = -1; + overlap->side_type = -1; + + /* Figure out what the intersection is */ + result->x = MAX (rect->x, rect2->x); + result->y = MAX (rect->y, rect2->y); + result->width = MIN (BOX_RIGHT (*rect), BOX_RIGHT (*rect2)) - result->x; + result->height = MIN (BOX_BOTTOM (*rect), BOX_BOTTOM (*rect2)) - result->y; + + /* Find out if the intersection is empty; have to do it this way since + * edges have a thickness of 0 + */ + if ((result->width < 0 || result->height < 0) || + (result->width == 0 && result->height == 0)) + { + result->width = 0; + result->height = 0; + intersect = FALSE; + } + else + { + /* Need to figure out the handle_type, a somewhat weird quantity: + * 0 - overlap is in middle of rect + * -1 - overlap is at the side of rect, and is on the opposite side + * of rect than the edge->side_type side + * 1 - overlap is at the side of rect, and the side of rect it is + * on is the edge->side_type side + */ + switch (edge->side_type) + { + case META_SIDE_LEFT: + if (result->x == rect->x) + *handle_type = 1; + else if (result->x == BOX_RIGHT (*rect)) + *handle_type = -1; + else + *handle_type = 0; + break; + case META_SIDE_RIGHT: + if (result->x == rect->x) + *handle_type = -1; + else if (result->x == BOX_RIGHT (*rect)) + *handle_type = 1; + else + *handle_type = 0; + break; + case META_SIDE_TOP: + if (result->y == rect->y) + *handle_type = 1; + else if (result->y == BOX_BOTTOM (*rect)) + *handle_type = -1; + else + *handle_type = 0; + break; + case META_SIDE_BOTTOM: + if (result->y == rect->y) + *handle_type = -1; + else if (result->y == BOX_BOTTOM (*rect)) + *handle_type = 1; + else + *handle_type = 0; + break; + default: + g_assert_not_reached (); + } + } + return intersect; +} + +/* Add all edges of the given rect to cur_edges and return the result. If + * rect_is_internal is false, the side types are switched (LEFT<->RIGHT and + * TOP<->BOTTOM). + */ +static GList* +add_edges (GList *cur_edges, + const MetaRectangle *rect, + gboolean rect_is_internal) +{ + MetaEdge *temp_edge; + int i; + + for (i=0; i<4; i++) + { + temp_edge = g_new (MetaEdge, 1); + temp_edge->rect = *rect; + switch (i) + { + case 0: + temp_edge->side_type = + rect_is_internal ? META_SIDE_LEFT : META_SIDE_RIGHT; + temp_edge->rect.width = 0; + break; + case 1: + temp_edge->side_type = + rect_is_internal ? META_SIDE_RIGHT : META_SIDE_LEFT; + temp_edge->rect.x += temp_edge->rect.width; + temp_edge->rect.width = 0; + break; + case 2: + temp_edge->side_type = + rect_is_internal ? META_SIDE_TOP : META_SIDE_BOTTOM; + temp_edge->rect.height = 0; + break; + case 3: + temp_edge->side_type = + rect_is_internal ? META_SIDE_BOTTOM : META_SIDE_TOP; + temp_edge->rect.y += temp_edge->rect.height; + temp_edge->rect.height = 0; + break; + } + temp_edge->edge_type = META_EDGE_SCREEN; + cur_edges = g_list_prepend (cur_edges, temp_edge); + } + + return cur_edges; +} + +/* Remove any part of old_edge that intersects remove and add any resulting + * edges to cur_list. Return cur_list when finished. + */ +static GList* +split_edge (GList *cur_list, + const MetaEdge *old_edge, + const MetaEdge *remove) +{ + MetaEdge *temp_edge; + switch (old_edge->side_type) + { + case META_SIDE_LEFT: + case META_SIDE_RIGHT: + g_assert (meta_rectangle_vert_overlap (&old_edge->rect, &remove->rect)); + if (BOX_TOP (old_edge->rect) < BOX_TOP (remove->rect)) + { + temp_edge = g_new (MetaEdge, 1); + *temp_edge = *old_edge; + temp_edge->rect.height = BOX_TOP (remove->rect) + - BOX_TOP (old_edge->rect); + cur_list = g_list_prepend (cur_list, temp_edge); + } + if (BOX_BOTTOM (old_edge->rect) > BOX_BOTTOM (remove->rect)) + { + temp_edge = g_new (MetaEdge, 1); + *temp_edge = *old_edge; + temp_edge->rect.y = BOX_BOTTOM (remove->rect); + temp_edge->rect.height = BOX_BOTTOM (old_edge->rect) + - BOX_BOTTOM (remove->rect); + cur_list = g_list_prepend (cur_list, temp_edge); + } + break; + case META_SIDE_TOP: + case META_SIDE_BOTTOM: + g_assert (meta_rectangle_horiz_overlap (&old_edge->rect, &remove->rect)); + if (BOX_LEFT (old_edge->rect) < BOX_LEFT (remove->rect)) + { + temp_edge = g_new (MetaEdge, 1); + *temp_edge = *old_edge; + temp_edge->rect.width = BOX_LEFT (remove->rect) + - BOX_LEFT (old_edge->rect); + cur_list = g_list_prepend (cur_list, temp_edge); + } + if (BOX_RIGHT (old_edge->rect) > BOX_RIGHT (remove->rect)) + { + temp_edge = g_new (MetaEdge, 1); + *temp_edge = *old_edge; + temp_edge->rect.x = BOX_RIGHT (remove->rect); + temp_edge->rect.width = BOX_RIGHT (old_edge->rect) + - BOX_RIGHT (remove->rect); + cur_list = g_list_prepend (cur_list, temp_edge); + } + break; + default: + g_assert_not_reached (); + } + + return cur_list; +} + +/* Split up edge and remove preliminary edges from strut_edges depending on + * if and how rect and edge intersect. + */ +static void +fix_up_edges (MetaRectangle *rect, MetaEdge *edge, + GList **strut_edges, GList **edge_splits, + gboolean *edge_needs_removal) +{ + MetaEdge overlap; + int handle_type; + + if (!rectangle_and_edge_intersection (rect, edge, &overlap, &handle_type)) + return; + + if (handle_type == 0 || handle_type == 1) + { + /* Put the result of removing overlap from edge into edge_splits */ + *edge_splits = split_edge (*edge_splits, edge, &overlap); + *edge_needs_removal = TRUE; + } + + if (handle_type == -1 || handle_type == 1) + { + /* Remove the overlap from strut_edges */ + /* First, loop over the edges of the strut */ + GList *tmp = *strut_edges; + while (tmp) + { + MetaEdge *cur = tmp->data; + /* If this is the edge that overlaps, then we need to split it */ + if (edges_overlap (cur, &overlap)) + { + GList *delete_me = tmp; + + /* Split this edge into some new ones */ + *strut_edges = split_edge (*strut_edges, cur, &overlap); + + /* Delete the old one */ + tmp = tmp->next; + g_free (cur); + *strut_edges = g_list_delete_link (*strut_edges, delete_me); + } + else + tmp = tmp->next; + } + } +} + +/* This function removes intersections of edges with the rectangles from the + * list of edges. + */ +GList* +meta_rectangle_remove_intersections_with_boxes_from_edges ( + GList *edges, + const GSList *rectangles) +{ + const GSList *rect_iter; + const int opposing = 1; + + /* Now remove all intersections of rectangles with the edge list */ + rect_iter = rectangles; + while (rect_iter) + { + MetaRectangle *rect = rect_iter->data; + GList *edge_iter = edges; + while (edge_iter) + { + MetaEdge *edge = edge_iter->data; + MetaEdge overlap; + int handle; + gboolean edge_iter_advanced = FALSE; + + /* If this edge overlaps with this rect... */ + if (rectangle_and_edge_intersection (rect, edge, &overlap, &handle)) + { + + /* "Intersections" where the edges touch but are opposite + * sides (e.g. a left edge against the right edge) should not + * be split. Note that the comments in + * rectangle_and_edge_intersection() say that opposing edges + * occur when handle is -1, BUT you need to remember that we + * treat the left side of a window as a right edge because + * it's what the right side of the window being moved should + * be-resisted-by/snap-to. So opposing is really 1. Anyway, + * we just keep track of it in the opposing constant set up + * above and if handle isn't equal to that, then we know the + * edge should be split. + */ + if (handle != opposing) + { + /* Keep track of this edge so we can delete it below */ + GList *delete_me = edge_iter; + edge_iter = edge_iter->next; + edge_iter_advanced = TRUE; + + /* Split the edge and add the result to beginning of edges */ + edges = split_edge (edges, edge, &overlap); + + /* Now free the edge... */ + g_free (edge); + edges = g_list_delete_link (edges, delete_me); + } + } + + if (!edge_iter_advanced) + edge_iter = edge_iter->next; + } + + rect_iter = rect_iter->next; + } + + return edges; +} + +/* This function is trying to find all the edges of an onscreen region. */ +GList* +meta_rectangle_find_onscreen_edges (const MetaRectangle *basic_rect, + const GSList *all_struts) +{ + GList *ret; + GList *fixed_strut_rects; + GList *edge_iter; + const GList *strut_rect_iter; + + /* The algorithm is basically as follows: + * Make sure the struts are disjoint + * Initialize the edge_set to the edges of basic_rect + * Foreach strut: + * Put together a preliminary new edge from the edges of the strut + * Foreach edge in edge_set: + * - Split the edge if it is partially contained inside the strut + * - If the edge matches an edge of the strut (i.e. a strut just + * against the edge of the screen or a not-next-to-edge-of-screen + * strut adjacent to another), then both the edge from the + * edge_set and the preliminary edge for the strut will need to + * be split + * Add any remaining "preliminary" strut edges to the edge_set + */ + + /* Make sure the struts are disjoint */ + fixed_strut_rects = + get_disjoint_strut_rect_list_in_region (all_struts, basic_rect); + + /* Start off the list with the edges of basic_rect */ + ret = add_edges (NULL, basic_rect, TRUE); + + strut_rect_iter = fixed_strut_rects; + while (strut_rect_iter) + { + MetaRectangle *strut_rect = (MetaRectangle*) strut_rect_iter->data; + + /* Get the new possible edges we may need to add from the strut */ + GList *new_strut_edges = add_edges (NULL, strut_rect, FALSE); + + edge_iter = ret; + while (edge_iter) + { + MetaEdge *cur_edge = edge_iter->data; + GList *splits_of_cur_edge = NULL; + gboolean edge_needs_removal = FALSE; + + fix_up_edges (strut_rect, cur_edge, + &new_strut_edges, &splits_of_cur_edge, + &edge_needs_removal); + + if (edge_needs_removal) + { + /* Delete the old edge */ + GList *delete_me = edge_iter; + edge_iter = edge_iter->next; + g_free (cur_edge); + ret = g_list_delete_link (ret, delete_me); + + /* Add the new split parts of the edge */ + ret = g_list_concat (splits_of_cur_edge, ret); + } + else + { + edge_iter = edge_iter->next; + } + + /* edge_iter was already advanced above */ + } + + ret = g_list_concat (new_strut_edges, ret); + strut_rect_iter = strut_rect_iter->next; + } + + /* Sort the list */ + ret = g_list_sort (ret, meta_rectangle_edge_cmp); + + /* Free the fixed struts list */ + meta_rectangle_free_list_and_elements (fixed_strut_rects); + + return ret; +} + +GList* +meta_rectangle_find_nonintersected_xinerama_edges ( + const GList *xinerama_rects, + const GSList *all_struts) +{ + /* This function cannot easily be merged with + * meta_rectangle_find_onscreen_edges() because real screen edges + * and strut edges both are of the type "there ain't anything + * immediately on the other side"; xinerama edges are different. + */ + GList *ret; + const GList *cur; + GSList *temp_rects; + + /* Initialize the return list to be empty */ + ret = NULL; + + /* start of ret with all the edges of xineramas that are adjacent to + * another xinerama. + */ + cur = xinerama_rects; + while (cur) + { + MetaRectangle *cur_rect = cur->data; + const GList *compare = xinerama_rects; + while (compare) + { + MetaRectangle *compare_rect = compare->data; + + /* Check if cur might be horizontally adjacent to compare */ + if (meta_rectangle_vert_overlap(cur_rect, compare_rect)) + { + MetaSide side_type; + int y = MAX (cur_rect->y, compare_rect->y); + int height = MIN (BOX_BOTTOM (*cur_rect) - y, + BOX_BOTTOM (*compare_rect) - y); + int width = 0; + int x; + + if (BOX_LEFT (*cur_rect) == BOX_RIGHT (*compare_rect)) + { + /* compare_rect is to the left of cur_rect */ + x = BOX_LEFT (*cur_rect); + side_type = META_SIDE_LEFT; + } + else if (BOX_RIGHT (*cur_rect) == BOX_LEFT (*compare_rect)) + { + /* compare_rect is to the right of cur_rect */ + x = BOX_RIGHT (*cur_rect); + side_type = META_SIDE_RIGHT; + } + else + /* These rectangles aren't adjacent after all */ + x = INT_MIN; + + /* If the rectangles really are adjacent */ + if (x != INT_MIN) + { + /* We need a left edge for the xinerama on the right, and + * a right edge for the xinerama on the left. Just fill + * up the edges and stick 'em on the list. + */ + MetaEdge *new_edge = g_new (MetaEdge, 1); + + new_edge->rect = meta_rect (x, y, width, height); + new_edge->side_type = side_type; + new_edge->edge_type = META_EDGE_XINERAMA; + + ret = g_list_prepend (ret, new_edge); + } + } + + /* Check if cur might be vertically adjacent to compare */ + if (meta_rectangle_horiz_overlap(cur_rect, compare_rect)) + { + MetaSide side_type; + int x = MAX (cur_rect->x, compare_rect->x); + int width = MIN (BOX_RIGHT (*cur_rect) - x, + BOX_RIGHT (*compare_rect) - x); + int height = 0; + int y; + + if (BOX_TOP (*cur_rect) == BOX_BOTTOM (*compare_rect)) + { + /* compare_rect is to the top of cur_rect */ + y = BOX_TOP (*cur_rect); + side_type = META_SIDE_TOP; + } + else if (BOX_BOTTOM (*cur_rect) == BOX_TOP (*compare_rect)) + { + /* compare_rect is to the bottom of cur_rect */ + y = BOX_BOTTOM (*cur_rect); + side_type = META_SIDE_BOTTOM; + } + else + /* These rectangles aren't adjacent after all */ + y = INT_MIN; + + /* If the rectangles really are adjacent */ + if (y != INT_MIN) + { + /* We need a top edge for the xinerama on the bottom, and + * a bottom edge for the xinerama on the top. Just fill + * up the edges and stick 'em on the list. + */ + MetaEdge *new_edge = g_new (MetaEdge, 1); + + new_edge->rect = meta_rect (x, y, width, height); + new_edge->side_type = side_type; + new_edge->edge_type = META_EDGE_XINERAMA; + + ret = g_list_prepend (ret, new_edge); + } + } + + compare = compare->next; + } + cur = cur->next; + } + + temp_rects = NULL; + for (; all_struts; all_struts = all_struts->next) + temp_rects = g_slist_prepend (temp_rects, + &((MetaStrut*)all_struts->data)->rect); + ret = meta_rectangle_remove_intersections_with_boxes_from_edges (ret, + temp_rects); + g_slist_free (temp_rects); + + /* Sort the list */ + ret = g_list_sort (ret, meta_rectangle_edge_cmp); + + return ret; +} |