path: root/src/boxes.c

/* Simple box operations */

/* 
 * Copyright (C) 2005 Elijah Newren
 * [According to the ChangeLog, Anders, Havoc, and Rob were responsible
 * for the meta_rectangle_intersect() and meta_rectangle_equal()
 * functions that I copied from display.c]
 * Copyright (C) 2002 Anders Carlsson
 * Copyright (C) 2002 Red Hat, Inc.
 * Copyright (C) 2003 Rob Adams
 * 
 * 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
#include <stdio.h>      // For snprintf

/* PRINT_DEBUG may be useful to define when compiling the testboxes program if
 * any issues crop up.
 */
/* #define PRINT_DEBUG */

char*
meta_rectangle_to_string (const MetaRectangle *rect,
                          char                *output)
{
  /* 25 = 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.
   */
  snprintf (output, 25, "%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 = 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[27];
  char *cur = output;
  GList *tmp = region;
  while (tmp)
    {
      MetaRectangle *rect = tmp->data;
      snprintf (rect_string, 27, "[%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;
}

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));
}

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:
      /* No need to modify 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:
      /* No need to modify rect->x */
      break;
    }
  rect->width = new_width;
  
  /* Next, the y direction */
  adjust = 0;
  switch (gravity)
    {
    case NorthWestGravity:
    case NorthGravity:
    case NorthEastGravity:
      /* No need to modify 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:
      /* No need to modify 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;
#ifdef PRINT_DEBUG
  int num_contains, num_merged, num_part_contains, num_adjacent;
  num_contains = num_merged = num_part_contains = num_adjacent = 0;
#endif
  compare = region;
  g_assert (region);

#ifdef PRINT_DEBUG
  char spanning_region[1 + 28 * g_list_length (region)];
  char rect1_string[25];
  char rect2_string[25];
  printf ("Merging stats:\n");
  printf ("  Length of initial list: %d\n", g_list_length (region));
  printf ("  Initial rectangles: %s\n",
          meta_rectangle_region_to_string (region, ", ", spanning_region));
#endif

  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);

#ifdef PRINT_DEBUG
          printf ("    -- Comparing %s to %s --\n",
                  meta_rectangle_to_string (a, rect1_string),
                  meta_rectangle_to_string (b, rect2_string));
#endif

          /* If a contains b, just remove b */
          if (meta_rectangle_contains_rect (a, b))
            {
              delete_me = other;
#ifdef PRINT_DEBUG
              num_contains++;
              num_merged++;
#endif
            }
          /* If b contains a, just remove a */
          else if (meta_rectangle_contains_rect (a, b))
            {
              delete_me = compare;
#ifdef PRINT_DEBUG
              num_contains++;
              num_merged++;
#endif
            }
          /* 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;
#ifdef PRINT_DEBUG
                  num_part_contains++;
                  num_merged++;
#endif
                }
              /* 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;
#ifdef PRINT_DEBUG
                  num_adjacent++;
                  num_merged++;
#endif
                }
            }
          /* 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;
#ifdef PRINT_DEBUG
                  num_part_contains++;
                  num_merged++;
#endif
                }
              /* 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;
#ifdef PRINT_DEBUG
                  num_adjacent++;
                  num_merged++;
#endif
                }
            }

          other = other->next;

          /* Delete any rectangle in the list that is no longer wanted */
          if (delete_me != NULL)
            {
#ifdef PRINT_DEBUG
              MetaRectangle *bla = delete_me->data;
              printf ("    Deleting rect %s\n",
                      meta_rectangle_to_string (bla, rect1_string));
#endif

              /* 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);
            }

#ifdef PRINT_DEBUG
          char new_list[1 + 28 * g_list_length (region)];
          printf ("    After comparison, new list is: %s\n",
                  meta_rectangle_region_to_string (region, ", ", new_list));
#endif
        }

      compare = compare->next;
    }

#ifdef PRINT_DEBUG
  /* Note that I believe it will be the case that num_part_contains and
   * num_adjacent will alwyas be 0 while num_contains will be equal to
   * num_merged.  If so, this might be useful information to use to come up
   * with some kind of optimization for this funcation, given that there
   * exists someone who really wants to do that.
   */
  char final_list[1 + 28 * g_list_length (region)];
  printf ("  Num rectangles contained in others          : %d\n", 
          num_contains);
  printf ("  Num rectangles partially contained in others: %d\n", 
          num_part_contains);
  printf ("  Num rectangles adjacent to others           : %d\n", 
          num_adjacent);
  printf ("  Num rectangles merged with others           : %d\n",
          num_merged);
  printf ("  Final rectangles: %s\n",
          meta_rectangle_region_to_string (region, ", ", final_list));
#endif

  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,
  const int      left_expand,
  const int      right_expand,
  const int      top_expand,
  const int      bottom_expand)
{
  /* 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 Gnome (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.  If it ever does show up on
   * profiles (most likely because people start using large 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) just don't call this function that much.  Currently, it's called
   *     from a few places in constraints.c, and thus is called multiple
   *     times for every meta_window_constrain() call, which itself is
   *     called an awful lot.  However, the answer we provide is always the
   *     same unless the screen size, number of xineramas, or list of
   *     struts has changed.  I'm not aware of any case where screen size
   *     or number of xineramas changes without logging out.  struts change
   *     very rarely.  So we should be able to just save the appropriate
   *     info in the MetaWorkspace (or maybe MetaScreen), update it when
   *     the struts change, and then just use those precomputed values
   *     instead of calling this function so much.
   *
   * In terms of work, 1-3 would be hard (and I'm not entirely certain that
   * they would work) and 4 would be relatively easy.  4 would also provide
   * the greatest benefit.  Therefore, do 4 first.  Don't even think about
   * 1-3 or other micro-optimizations until you've done that one.
   */

  GList         *ret;
  GList         *tmp_list;
  const GSList  *strut_iter;
  MetaRectangle *temp_rect;

  /* The algorithm is basically as follows:
   *   Ignore directional expansions until the end
   *   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)
   *   Now do directional expansion of all rectangles in rectangle_set
   */

  temp_rect = g_new (MetaRectangle, 1);
  *temp_rect = *basic_rect;
  ret = g_list_prepend (NULL, temp_rect);
#ifdef PRINT_DEBUG
  char rect_string[25];
  printf("Initialized spanning set with %s.\n", 
         meta_rectangle_to_string (basic_rect, rect_string));
#endif

  strut_iter = all_struts;
  while (strut_iter)
    {
      GList *rect_iter; 
      MetaRectangle *strut = (MetaRectangle*) strut_iter->data;
#ifdef PRINT_DEBUG
      printf("Dealing with strut %s.\n", 
             meta_rectangle_to_string (strut, rect_string));
#endif
      tmp_list = ret;
      ret = NULL;
      rect_iter = tmp_list;
      while (rect_iter)
        {
          MetaRectangle *rect = (MetaRectangle*) rect_iter->data;
#ifdef PRINT_DEBUG
          printf("  Looking if we need to chop up %s.\n",
                 meta_rectangle_to_string (rect, rect_string));
#endif
          if (!meta_rectangle_overlap (rect, strut))
            {
            ret = g_list_prepend (ret, rect);
#ifdef PRINT_DEBUG
            printf("    No chopping of %s.\n",
                   meta_rectangle_to_string (rect, rect_string));
#endif
            }
          else
            {
              /* If there is area in rect left of strut */
              if (rect->x < strut->x)
                {
                  temp_rect = g_new (MetaRectangle, 1);
                  *temp_rect = *rect;
                  temp_rect->width = strut->x - rect->x;
                  ret = g_list_prepend (ret, temp_rect);
#ifdef PRINT_DEBUG
                  printf("    Added %s.\n",
                         meta_rectangle_to_string (temp_rect, rect_string));
#endif
                }
              /* If there is area in rect right of strut */
              if (rect->x + rect->width > strut->x + strut->width)
                {
                  int new_x;
                  temp_rect = g_new (MetaRectangle, 1);
                  *temp_rect = *rect;
                  new_x = strut->x + strut->width;
                  temp_rect->width = rect->x + rect->width - new_x;
                  temp_rect->x = new_x;
                  ret = g_list_prepend (ret, temp_rect);
#ifdef PRINT_DEBUG
                  printf("    Added %s.\n",
                         meta_rectangle_to_string (temp_rect, rect_string));
#endif
                }
              /* If there is area in rect above strut */
              if (rect->y < strut->y)
                {
                  temp_rect = g_new (MetaRectangle, 1);
                  *temp_rect = *rect;
                  temp_rect->height = strut->y - rect->y;
                  ret = g_list_prepend (ret, temp_rect);
#ifdef PRINT_DEBUG
                  printf("    Added %s.\n",
                         meta_rectangle_to_string (temp_rect, rect_string));
#endif
                }
              /* If there is area in rect below strut */
              if (rect->y + rect->height > strut->y + strut->height)
                {
                  int new_y;
                  temp_rect = g_new (MetaRectangle, 1);
                  *temp_rect = *rect;
                  new_y = strut->y + strut->height;
                  temp_rect->height = rect->y + rect->height - new_y;
                  temp_rect->y = new_y;
                  ret = g_list_prepend (ret, temp_rect);
#ifdef PRINT_DEBUG
                  printf("    Added %s.\n",
                         meta_rectangle_to_string (temp_rect, rect_string));
#endif
                }
              g_free (rect);
            }
          rect_iter = rect_iter->next;
        }
      g_list_free (tmp_list);
      strut_iter = strut_iter->next;
    }

  /* Now it's time to do the directional expansion */
  tmp_list = ret;
  while (tmp_list)
    {
      MetaRectangle *rect = (MetaRectangle*) tmp_list->data;
      rect->x      -= left_expand;
      rect->width  += (left_expand + right_expand);
      rect->y      -= top_expand;
      rect->height += (top_expand + bottom_expand);
      tmp_list = tmp_list->next;
    }

  /* 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;
}

void
meta_rectangle_free_spanning_set (GList *spanning_rects)
{
  g_list_foreach (spanning_rects, 
                  (void (*)(gpointer,gpointer))&g_free, /* ew, for ugly */
                  NULL);
  g_list_free (spanning_rects);
}

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;
}

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.
   */
  temp = spanning_rects;
  while (temp)
    {
      int factor = 1;
      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, set
       * factor to 0.
       */
      if ((fixed_directions & FIXED_DIRECTION_X) &&
          (compare_rect->x > rect->x || 
           compare_rect->x + compare_rect->width < rect->x + rect->width))
        factor = 0;
        
      /* If y is fixed and the entire height of rect doesn't fit in compare, set
       * factor to 0.
       */
      if ((fixed_directions & FIXED_DIRECTION_Y) &&
          (compare_rect->y > rect->y || 
           compare_rect->y + compare_rect->height < rect->y + rect->height))
        factor = 0;

      /* If compare can't hold the min_size window, set factor to 0 */
      if (compare_rect->width  < min_size->width ||
          compare_rect->height < min_size->height)
        factor = 0;

      /* Determine maximal overlap amount */
      maximal_overlap_amount_for_compare =
        MIN (rect->width,  compare_rect->width) *
        MIN (rect->height, compare_rect->height);
      maximal_overlap_amount_for_compare *= factor;

      /* 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;
        }

      temp = temp->next;
    }

  /* 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.
   */
  temp = spanning_rects;
  while (temp)
    {
      int factor = 1;
      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, set
       * factor to 0.
       */
      if ((fixed_directions & FIXED_DIRECTION_X) &&
          (compare_rect->x > rect->x || 
           compare_rect->x + compare_rect->width < rect->x + rect->width))
        factor = 0;
        
      /* If y is fixed and the entire height of rect doesn't fit in compare, set
       * factor to 0.
       */
      if ((fixed_directions & FIXED_DIRECTION_Y) &&
          (compare_rect->y > rect->y || 
           compare_rect->y + compare_rect->height < rect->y + rect->height))
        factor = 0;

      /* Determine maximal overlap amount */
      meta_rectangle_intersect (rect, compare_rect, &overlap);
      maximal_overlap_amount_for_compare = meta_rectangle_area (&overlap);
      maximal_overlap_amount_for_compare *= factor;

      /* 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;
        }

      temp = temp->next;
    }

  /* 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.
   */
  temp = spanning_rects;
  while (temp)
    {
      int factor = 1;
      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, set
       * factor to 0.
       */
      if ((fixed_directions & FIXED_DIRECTION_X) &&
          (compare_rect->x > rect->x || 
           compare_rect->x + compare_rect->width < rect->x + rect->width))
        factor = 0;
        
      /* If y is fixed and the entire height of rect doesn't fit in compare, set
       * factor to 0.
       */
      if ((fixed_directions & FIXED_DIRECTION_Y) &&
          (compare_rect->y > rect->y || 
           compare_rect->y + compare_rect->height < rect->y + rect->height))
        factor = 0;

      /* 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 comapre_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);

      /* If we'd have to move in the wrong direction, disqualify compare_rect */
      if (factor == 0)
        {
          maximal_overlap_amount_for_compare = 0;
          dist_to_compare = G_MAXINT;
        }

      /* 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;
        }

      temp = temp->next;
    }

  /* 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 also be equal to 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;
}