? src/\
? src/wm-tester/test-size-hints
Index: src/display.c
===================================================================
RCS file: /cvs/gnome/metacity/src/display.c,v
retrieving revision 1.198
diff -u -r1.198 display.c
--- src/display.c	13 Oct 2003 20:15:40 -0000	1.198
+++ src/display.c	12 Nov 2003 09:56:43 -0000
@@ -3772,7 +3772,13 @@
 
   g_return_val_if_fail (src1 != NULL, FALSE);
   g_return_val_if_fail (src2 != NULL, FALSE);
-  g_return_val_if_fail (dest != NULL, FALSE);
+
+  /* If dest is null, return fast. */
+  if (dest == NULL)
+      return (src1->x < src2->x + src2->width) &&
+             (src2->x < src1->x + src1->width) &&
+             (src1->y < src2->y + src2->height) &&
+             (src2->y < src1->y + src1->height);
 
   return_val = FALSE;
 
Index: src/keybindings.c
===================================================================
RCS file: /cvs/gnome/metacity/src/keybindings.c,v
retrieving revision 1.92
diff -u -r1.92 keybindings.c
--- src/keybindings.c	12 Oct 2003 06:25:38 -0000	1.92
+++ src/keybindings.c	12 Nov 2003 09:56:43 -0000
@@ -3290,7 +3290,7 @@
 
       while (above)
 	{
-	  MetaRectangle tmp, win_rect, above_rect;
+	  MetaRectangle win_rect, above_rect;
 
           if (above->mapped)
             {
@@ -3298,7 +3298,7 @@
               meta_window_get_outer_rect (above, &above_rect);
               
               /* Check if obscured */
-              if (meta_rectangle_intersect (&win_rect, &above_rect, &tmp))
+              if (meta_rectangle_intersect (&win_rect, &above_rect, NULL))
                 {
                   meta_window_raise (window);
                   return;
Index: src/place.c
===================================================================
RCS file: /cvs/gnome/metacity/src/place.c,v
retrieving revision 1.36
diff -u -r1.36 place.c
--- src/place.c	8 Nov 2003 05:47:37 -0000	1.36
+++ src/place.c	12 Nov 2003 09:56:43 -0000
@@ -39,34 +39,19 @@
   int from_origin_b;
   int ax, ay, bx, by;
 
-  /* we're interested in the frame position for cascading,
-   * not meta_window_get_position()
-   */
-  if (aw->frame)
-    {
-      ax = aw->frame->rect.x;
-      ay = aw->frame->rect.y;
-    }
-  else
-    {
-      ax = aw->rect.x;
-      ay = aw->rect.y;
-    }
-
-  if (bw->frame)
-    {
-      bx = bw->frame->rect.x;
-      by = bw->frame->rect.y;
-    }
-  else
-    {
-      bx = bw->rect.x;
-      by = bw->rect.y;
-    }
+  ax = META_WINDOW_FRAME_RECT(aw).x;
+  ay = META_WINDOW_FRAME_RECT(aw).y;
+  bx = META_WINDOW_FRAME_RECT(bw).x;
+  by = META_WINDOW_FRAME_RECT(bw).y;
   
   /* probably there's a fast good-enough-guess we could use here. */
+/*
   from_origin_a = sqrt (ax * ax + ay * ay);
   from_origin_b = sqrt (bx * bx + by * by);
+*/
+  /* Euclid norm is an overkill, this one's good enough: */
+  from_origin_a = ax + ay;
+  from_origin_b = bx + by;
     
   if (from_origin_a < from_origin_b)
     return -1;
@@ -132,8 +117,8 @@
   
   /* Find first cascade position that's not used. */
   
-  window_width = window->frame ? window->frame->rect.width : window->rect.width;
-  window_height = window->frame ? window->frame->rect.height : window->rect.height;
+  window_width = META_WINDOW_FRAME_RECT(window).width;
+  window_height = META_WINDOW_FRAME_RECT(window).height;
   
   cascade_stage = 0;
   tmp = sorted;
@@ -144,17 +129,8 @@
       
       w = tmp->data;
 
-      /* we want frame position, not window position */
-      if (w->frame)
-        {
-          wx = w->frame->rect.x;
-          wy = w->frame->rect.y;
-        }
-      else
-        {
-          wx = w->rect.x;
-          wy = w->rect.y;
-        }
+      wx = META_WINDOW_FRAME_RECT(w).x;
+      wy = META_WINDOW_FRAME_RECT(w).y;
       
       if (ABS (wx - cascade_x) < x_threshold &&
           ABS (wy - cascade_y) < y_threshold)
@@ -225,7 +201,7 @@
 }
 
 static int
-intcmp (const void* a, const void* b)
+intcmp (gconstpointer a, gconstpointer b)
 {
   const int *ai = a;
   const int *bi = b;
@@ -268,15 +244,17 @@
     *bottom = bottom_edge;
 }
 
-static gboolean
-rectangle_overlaps_some_window (MetaRectangle *rect,
-                                GList         *windows)
+static gint
+rectangle_overlaps_window_index (MetaRectangle *rect,
+                                 GList         *windows,
+				 gint          maxwindows)
 {
   GList *tmp;
   MetaRectangle dest;
+  int i = 0;
   
   tmp = windows;
-  while (tmp != NULL)
+  while (tmp != NULL && i < maxwindows)
     {
       MetaWindow *other = tmp->data;
       MetaRectangle other_rect;      
@@ -295,72 +273,54 @@
         case META_WINDOW_TOOLBAR:
         case META_WINDOW_MENU:
           meta_window_get_outer_rect (other, &other_rect);
-          
           if (meta_rectangle_intersect (rect, &other_rect, &dest))
-            return TRUE;
+            return i;
           break;
         }
       
       tmp = tmp->next;
+      i++;
     }
 
-  return FALSE;
+  return maxwindows;
 }
 
-static gint
-leftmost_cmp (gconstpointer a, gconstpointer b)
-{
-  MetaWindow *aw = (gpointer) a;
-  MetaWindow *bw = (gpointer) b;
-  int ax, bx;
-
-  /* we're interested in the frame position for cascading,
-   * not meta_window_get_position()
-   */
-  if (aw->frame)
-    ax = aw->frame->rect.x;
-  else
-    ax = aw->rect.x;
-
-  if (bw->frame)
-    bx = bw->frame->rect.x;
-  else
-    bx = bw->rect.x;
-
-  if (ax < bx)
-    return -1;
-  else if (ax > bx)
-    return 1;
-  else
-    return 0;
-}
-
-static gint
-topmost_cmp (gconstpointer a, gconstpointer b)
+static gboolean
+rectangle_overlaps_some_window (MetaRectangle *rect,
+                                GList         *windows)
 {
-  MetaWindow *aw = (gpointer) a;
-  MetaWindow *bw = (gpointer) b;
-  int ay, by;
+  GList *tmp;
+  MetaRectangle dest;
+  
+  tmp = windows;
+  while (tmp != NULL)
+    {
+      MetaWindow *other = tmp->data;
+      MetaRectangle other_rect;      
 
-  /* we're interested in the frame position for cascading,
-   * not meta_window_get_position()
-   */
-  if (aw->frame)
-    ay = aw->frame->rect.y;
-  else
-    ay = aw->rect.y;
+      switch (other->type)
+        {
+        case META_WINDOW_DOCK:
+        case META_WINDOW_SPLASHSCREEN:
+        case META_WINDOW_DESKTOP:
+        case META_WINDOW_DIALOG:
+        case META_WINDOW_MODAL_DIALOG:
+          break;
 
-  if (bw->frame)
-    by = bw->frame->rect.y;
-  else
-    by = bw->rect.y;
+        case META_WINDOW_NORMAL:
+        case META_WINDOW_UTILITY:
+        case META_WINDOW_TOOLBAR:
+        case META_WINDOW_MENU:
+          meta_window_get_outer_rect (other, &other_rect);
+          if (meta_rectangle_intersect (rect, &other_rect, &dest))
+            return TRUE;
+          break;
+        }
+      
+      tmp = tmp->next;
+    }
 
-  if (ay < by)
-    return -1;
-  else if (ay > by)
-    return 1;
-  else
-    return 0;
+  return FALSE;
 }
 
 static void
@@ -391,8 +351,41 @@
 	  (rect->y + rect->height <= work_area->y + work_area->height));
 }
 
-/* Find the leftmost, then topmost, empty area on the workspace
- * that can contain the new window.
+#define OVERLAP_MIN_THRESHOLD 1
+#define OVERLAP_MAX_THRESHOLD 20
+  
+/* Test a proposed area for fitness, and save it if is better
+ * than the best one so far.  Return true if is a perfect fit.
+ */
+static gboolean
+proposed_fit_is_perfect (/* proposed area */
+			 MetaRectangle *rect,
+			 MetaRectangle *work_area,
+			 MetaRectangle *best_rect,
+			 /* mru list of relevant windows */
+			 GList         *windows,
+			 /* best fitness sofar.  also gets updated if this one's better */
+			 int           *fitness) 
+{
+  int fit;
+  if (rect_fits_in_work_area (work_area, rect) &&
+      *fitness < (fit = rectangle_overlaps_window_index (rect,
+	                  windows, OVERLAP_MAX_THRESHOLD)))
+    {
+      best_rect->x = rect->x;
+      best_rect->y = rect->y;
+      *fitness = fit;
+      if (fit == OVERLAP_MAX_THRESHOLD)
+	/* If it does not overlap anything, it's perfect. */
+        return TRUE;
+    }
+  return FALSE;
+}
+
+/* Find a suitable area on the workspace for the new window.
+ * Right now it tries to find one that does not overlap as much
+ * recently used windows as possible.  And put the new window near
+ * recently used ones.
  *
  * Cool feature to have: if we can't fit the current window size,
  * try shrinking the window (within geometry constraints). But
@@ -402,7 +395,7 @@
 static gboolean
 find_first_fit (MetaWindow *window,
                 MetaFrameGeometry *fgeom,
-                /* visible windows on relevant workspaces */
+                /* mru list of visible windows on current workspace */
                 GList      *windows,
 		int*        xineramas_list,
 		int         n_xineramas,
@@ -413,31 +406,21 @@
 {
   /* This algorithm is limited - it just brute-force tries
    * to fit the window in a small number of locations that are aligned
-   * with existing windows. It tries to place the window on
-   * the bottom of each existing window, and then to the right
-   * of each existing window, aligned with the left/top of the
-   * existing window in each of those cases.
+   * with existing windows.
+   * It tries to place the window on the four directions of each existing
+   * window, with some alignment.
    */  
-  int retval;
-  GList *below_sorted;
-  GList *right_sorted;
   GList *tmp;
-  MetaRectangle rect;
+  MetaRectangle rect, best_rect;
   MetaRectangle work_area;
+  int fitness;
   int i;
-  
-  retval = FALSE;
 
-  /* Below each window */
-  below_sorted = g_list_copy (windows);
-  below_sorted = g_list_sort (below_sorted, leftmost_cmp);
-  below_sorted = g_list_sort (below_sorted, topmost_cmp);  
-
-  /* To the right of each window */
-  right_sorted = g_list_copy (windows);
-  right_sorted = g_list_sort (right_sorted, topmost_cmp);
-  right_sorted = g_list_sort (right_sorted, leftmost_cmp);
-  
+  meta_topic (META_DEBUG_PLACEMENT, "Fitting window %s with thresholds min=%d max=%d\n",
+	      window->desc, OVERLAP_MIN_THRESHOLD, OVERLAP_MAX_THRESHOLD);
+
+  fitness = -1;
+
   rect.width = window->rect.width;
   rect.height = window->rect.height;
   
@@ -459,31 +442,11 @@
     }
 
   /* try each xinerama in the natural ordering in turn */
-  i = 0;
-  while (i < n_xineramas)
+  for (i = 0; i < n_xineramas; i++)
     {
       meta_window_get_work_area_for_xinerama (window, xineramas_list[i], &work_area);
 
-      center_tile_rect_in_area (&rect, &work_area);
-
-      if (rect_fits_in_work_area (&work_area, &rect) &&
-          !rectangle_overlaps_some_window (&rect, windows))
-        {
-          *new_x = rect.x;
-          *new_y = rect.y;
-          if (fgeom)
-            {
-              *new_x += fgeom->left_width;
-              *new_y += fgeom->top_height;
-            }
-      
-          retval = TRUE;
-          
-          goto out;
-        }
-
-      /* try below each window */
-      tmp = below_sorted;
+      tmp = windows;
       while (tmp != NULL)
         {
           MetaWindow *w = tmp->data;
@@ -491,67 +454,60 @@
 
           meta_window_get_outer_rect (w, &outer_rect);
       
+	  /* try below the window */
           rect.x = outer_rect.x;
           rect.y = outer_rect.y + outer_rect.height;
-      
-          if (rect_fits_in_work_area (&work_area, &rect) &&
-              !rectangle_overlaps_some_window (&rect, below_sorted))
-            {
-              *new_x = rect.x;
-              *new_y = rect.y;
-              if (fgeom)
-                {
-                  *new_x += fgeom->left_width;
-                  *new_y += fgeom->top_height;
-                }
-          
-              retval = TRUE;
-          
-              goto out;
-            }
+	  if (proposed_fit_is_perfect(&rect, &work_area, &best_rect,
+		                      windows, &fitness))
+	    goto out;
 
-          tmp = tmp->next;
-        }
-
-      /* try to the right of each window */
-      tmp = right_sorted;
-      while (tmp != NULL)
-        {
-          MetaWindow *w = tmp->data;
-          MetaRectangle outer_rect;
-     
-          meta_window_get_outer_rect (w, &outer_rect);
-     
+	  /* try to the right of the window */
           rect.x = outer_rect.x + outer_rect.width;
           rect.y = outer_rect.y;
-     
-          if (rect_fits_in_work_area (&work_area, &rect) &&
-              !rectangle_overlaps_some_window (&rect, right_sorted))
-            {
-              *new_x = rect.x;
-              *new_y = rect.y;
-              if (fgeom)
-                {
-                  *new_x += fgeom->left_width;
-                  *new_y += fgeom->top_height;
-                }
-         
-              retval = TRUE;
-         
-              goto out;
-            }
+	  if (proposed_fit_is_perfect(&rect, &work_area, &best_rect,
+		                      windows, &fitness))
+	    goto out;
+
+	  /* try above the window */
+          rect.x = outer_rect.x;
+          rect.y = outer_rect.y - rect.height;
+	  if (proposed_fit_is_perfect(&rect, &work_area, &best_rect,
+		                      windows, &fitness))
+	    goto out;
+
+	  /* try to the left of the window */
+          rect.x = outer_rect.x - rect.width-1;
+          rect.y = outer_rect.y;
+	  if (proposed_fit_is_perfect(&rect, &work_area, &best_rect,
+		                      windows, &fitness))
+	    goto out;
 
           tmp = tmp->next;
         }
-      
-      ++i;
+
+      /* try top left cell in a grid */
+      center_tile_rect_in_area (&rect, &work_area);
+      if (proposed_fit_is_perfect(&rect, &work_area, &best_rect,
+		                  windows, &fitness))
+	goto out;
     }
   
  out:
 
-  g_list_free (below_sorted);
-  g_list_free (right_sorted);
-  return retval;
+  if (fitness >= OVERLAP_MIN_THRESHOLD)
+  {
+    meta_topic (META_DEBUG_PLACEMENT, "Fitness %d found\n", fitness);
+    *new_x = best_rect.x;
+    *new_y = best_rect.y;
+    if (fgeom)
+      {
+        *new_x += fgeom->left_width;
+        *new_y += fgeom->top_height;
+      }
+    return TRUE;
+  }
+  meta_topic (META_DEBUG_PLACEMENT, "No suitable fit found\n");
+  return FALSE;
 }
 
 void
@@ -566,7 +522,6 @@
   const MetaXineramaScreenInfo *xi;
   int* xineramas_list = NULL;
   int  n_xineramas;
-  int  i;
   int placed_on = -1;
   
   /* frame member variables should NEVER be used in here, only
@@ -674,7 +629,7 @@
           w = parent->rect.width;
 
           /* center of parent */
-          x = x + w / 2;
+          x += w / 2;
           /* center of child over center of parent */
           x -= window->rect.width / 2;
 
@@ -704,6 +659,9 @@
         }
     }
 
+  /* Warning, this is a round trip! */
+  xi = meta_screen_get_current_xinerama (window->screen);
+  
   /* FIXME UTILITY with transient set should be stacked up
    * on the sides of the parent window or something.
    */
@@ -715,9 +673,6 @@
       /* Center on screen */
       int w, h;
 
-      /* Warning, this function is a round trip! */
-      xi = meta_screen_get_current_xinerama (window->screen);
-
       w = xi->width;
       h = xi->height;
 
@@ -738,11 +693,12 @@
    * for placement purposes)
    */
   {
-    GSList *all_windows;
-    GSList *tmp;
+    GList *all_windows;
+    GList *tmp;
     
-    all_windows = meta_display_list_windows (window->display);
+    all_windows = window->screen->active_workspace->mru_list;
 
+    /* FIXME  appending n items takes O(n^2), workround to do in O(n) (hint: tail) */
     tmp = all_windows;
     while (tmp != NULL)
       {
@@ -751,15 +707,12 @@
         if (!w->minimized &&
             w != window && 
             meta_window_shares_some_workspace (window, w))
-          windows = g_list_prepend (windows, w);
+          windows = g_list_append (windows, w);
 
         tmp = tmp->next;
       }
   }
 
-  /* Warning, this is a round trip! */
-  xi = meta_screen_get_current_xinerama (window->screen);
-  
   /* "Origin" placement algorithm */
   x = xi->x_origin;
   y = xi->y_origin;
@@ -778,9 +731,12 @@
    * automaximized later) will go onto an empty xinerama if one is
    * available.
    */
+  /* FIXME --be use heuristics above in find_first_fit here too */
   if (window->has_maximize_func && window->decorated &&
       !window->fullscreen)
     {
+      int i;
+
       if (window->frame)
         {
           x = fgeom->left_width;
@@ -901,9 +857,9 @@
   /* if they don't overlap, then either a is above b
    * or b is above a
    */
-  if ((a->y + a->height) < b->y)
+  if ((a->y + a->height) <= b->y)
     return FALSE;
-  else if ((b->y + b->height) < a->y)
+  else if ((b->y + b->height) <= a->y)
     return FALSE;
   else
     return TRUE;
@@ -913,9 +869,9 @@
 rects_overlap_horizontally (const MetaRectangle *a,
                             const MetaRectangle *b)
 {
-  if ((a->x + a->width) < b->x)
+  if ((a->x + a->width) <= b->x)
     return FALSE;
-  else if ((b->x + b->width) < a->x)
+  else if ((b->x + b->width) <= a->x)
     return FALSE;
   else
     return TRUE;
Index: src/screen.c
===================================================================
RCS file: /cvs/gnome/metacity/src/screen.c,v
retrieving revision 1.111
diff -u -r1.111 screen.c
--- src/screen.c	12 Oct 2003 06:25:38 -0000	1.111
+++ src/screen.c	12 Nov 2003 09:56:43 -0000
@@ -1279,9 +1279,10 @@
       
       if (meta_rectangle_intersect (&screen_info, rect, &dest))
         {
-          if (dest.width * dest.height > xinerama_score)
+	  int score;
+          if ((score = dest.width * dest.height) > xinerama_score)
             {
-              xinerama_score = dest.width * dest.height;
+              xinerama_score = score;
               best_xinerama = i;
             }
         }
@@ -1440,14 +1441,14 @@
                                       MetaRectangle *rect,
                                       int            which_xinerama)
 {
-  MetaRectangle dest, screen_rect;
+  MetaRectangle screen_rect;
   
   screen_rect.x = screen->xinerama_infos[which_xinerama].x_origin;
   screen_rect.y = screen->xinerama_infos[which_xinerama].y_origin;
   screen_rect.width = screen->xinerama_infos[which_xinerama].width;
   screen_rect.height = screen->xinerama_infos[which_xinerama].height;
   
-  if (meta_rectangle_intersect (&screen_rect, rect, &dest))
+  if (meta_rectangle_intersect (&screen_rect, rect, NULL))
     return TRUE;
 
   return FALSE;
Index: src/window.h
===================================================================
RCS file: /cvs/gnome/metacity/src/window.h,v
retrieving revision 1.96
diff -u -r1.96 window.h
--- src/window.h	13 Oct 2003 20:15:40 -0000	1.96
+++ src/window.h	12 Nov 2003 09:56:43 -0000
@@ -308,6 +308,13 @@
 #define META_WINDOW_ALLOWS_HORIZONTAL_RESIZE(w) (META_WINDOW_ALLOWS_RESIZE_EXCEPT_HINTS (w) && (w)->size_hints.min_width < (w)->size_hints.max_width)
 #define META_WINDOW_ALLOWS_VERTICAL_RESIZE(w)   (META_WINDOW_ALLOWS_RESIZE_EXCEPT_HINTS (w) && (w)->size_hints.min_height < (w)->size_hints.max_height)
 
+
+/* Sometimes we're interested in the frame position,
+ * not meta_window_get_position()
+ */
+#define META_WINDOW_FRAME_RECT(w)    ((w)->frame ? (w)->frame->rect : (w)->rect)
+
+
 MetaWindow* meta_window_new                (MetaDisplay *display,
                                             Window       xwindow,
                                             gboolean     must_be_viewable);
