Compute the non-obscured normal window edges for edge resistance/snapping.

2005-11-06  Elijah Newren  <newren@gmail.com>

	Compute the non-obscured normal window edges for edge
	resistance/snapping.  Not yet used, but one more step is done.  :)

	* src/boxes.[ch]:

	(meta_rectangle_edge_cmp, meta_rectangle_find_onscreen_edges,
	  meta_rectangle_find_nonintersected_xinerama_edges):
	rename sort_edges to meta_rectangle_edge_cmp

	(meta_rectangle_remove_intersections_with_boxes_from_edges,
	  meta_rectangle_find_nonintersected_xinerama_edges):
	split out some common functionality from
	meta_rectangle_find_nonintersected_xinerama_edges() into the new
	meta_rectangle_remove_intersections_with_boxes_from_edges()

	* src/testboxes.c:

	(test_find_nonintersected_xinerama_edges):
	correct a couple tests

	* src/display.c

	(meta_display_begin_grab_op):
	add a call to meta_display_compute_resistance_and_snapping_edges()
	for moving/resizing operations

	(WINDOW_EDGE_RELEVANT):
	new macro for whether a window's edges should be considered
	relevant in computing window eges

	(meta_display_compute_resistance_and_snapping_edges):
	new function

6 files changed, 346 insertions, 46 deletions

diff --git a/ChangeLog b/ChangeLog
index 9ad0552b..6601fe86 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,8 +1,43 @@
+2005-11-06  Elijah Newren  <newren@gmail.com>
+
+	Compute the non-obscured normal window edges for edge
+	resistance/snapping.  Not yet used, but one more step is done.  :)
+
+	* src/boxes.[ch]:
+
+	(meta_rectangle_edge_cmp, meta_rectangle_find_onscreen_edges,
+	  meta_rectangle_find_nonintersected_xinerama_edges):
+	rename sort_edges to meta_rectangle_edge_cmp
+
+	(meta_rectangle_remove_intersections_with_boxes_from_edges,
+	  meta_rectangle_find_nonintersected_xinerama_edges):
+	split out some common functionality from
+	meta_rectangle_find_nonintersected_xinerama_edges() into the new
+	meta_rectangle_remove_intersections_with_boxes_from_edges()
+
+	* src/testboxes.c:
+
+	(test_find_nonintersected_xinerama_edges):
+	correct a couple tests
+
+	* src/display.c
+
+	(meta_display_begin_grab_op):
+	add a call to meta_display_compute_resistance_and_snapping_edges()
+	for moving/resizing operations
+
+	(WINDOW_EDGE_RELEVANT):
+	new macro for whether a window's edges should be considered
+	relevant in computing window eges
+
+	(meta_display_compute_resistance_and_snapping_edges):
+	new function
+
 2005-11-04  Elijah Newren  <newren@gmail.com>
 
-	Cache screen and xinerama edges for edge resistance/snapping at
-	the same time the workarea and on-screen/on-xinerama areas are
-	computed.
+	Compute screen and xinerama edges for edge resistance/snapping
+	when we compute the workarea and on-screen/on-xinerama areas, and
+	then cache them.
 
 	* src/workspace.[ch] (struct MetaWorkspace, meta_workspace_new,
 	  meta_workspace_free, meta_workspace_invalidate_work_area,
diff --git a/src/boxes.c b/src/boxes.c
index 8d524a38..8bc420e7 100644
--- a/src/boxes.c
+++ b/src/boxes.c
@@ -1156,8 +1156,8 @@ struts_are_disjoint (const GSList *struts)
 }
 
 /* To make things easily testable, provide a nice way of sorting edges */
-static gint
-sort_edges (gconstpointer a, gconstpointer b)
+gint
+meta_rectangle_edge_cmp (gconstpointer a, gconstpointer b)
 {
   const MetaEdge *a_edge_rect = (gconstpointer) a;
   const MetaEdge *b_edge_rect = (gconstpointer) b;
@@ -1450,6 +1450,71 @@ fix_up_edges (MetaRectangle *strut,        MetaEdge *edge,
     }
 }
 
+/* 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,
+  gboolean      rectangles_are_struts)
+{
+  const GSList *rect_iter;
+  const int opposing = rectangles_are_struts ? 1 : -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 side of a rect)
+               * should not be split.  For normal windows, these "opposing"
+               * edges occur when handle is -1.  Struts are weird, because
+               * we consider the left edge of a strut to be a right screen
+               * edge -- meaning that "opposing" edges occur when handle is
+               * 1.  To make this all work, we use 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,
@@ -1530,7 +1595,7 @@ meta_rectangle_find_onscreen_edges (const MetaRectangle *basic_rect,
     }
 
   /* Sort the list */
-  ret = g_list_sort (ret, sort_edges);
+  ret = g_list_sort (ret, meta_rectangle_edge_cmp);
 
   return ret;
 }
@@ -1547,7 +1612,6 @@ meta_rectangle_find_nonintersected_xinerama_edges (
    */
   GList *ret;
   const GList  *cur;
-  const GSList *strut_iter;
 
   /* Initialize the return list to be empty */
   ret = NULL;
@@ -1655,43 +1719,12 @@ meta_rectangle_find_nonintersected_xinerama_edges (
       cur = cur->next;
     }
 
-  /* Now remove all intersections of struts with the xinerama edge list */
-  strut_iter = all_struts;
-  while (strut_iter)
-    {
-      MetaRectangle *strut = strut_iter->data;
-      GList *edge_iter = ret;
-      while (edge_iter)
-        {
-          MetaEdge *edge = edge_iter->data;
-          MetaEdge overlap;
-          int      bla;
-
-          /* If this edge overlaps with this strut... */
-          if (rectangle_and_edge_intersection (strut, edge, &overlap, &bla))
-            {
-              /* Keep track of this edge so we can delete it below */
-              GList *delete_me = edge_iter;
-              edge_iter = edge_iter->next;
-
-              /* Split the edge and add the result to the beginning of ret */
-              ret = split_edge (ret, edge, &overlap);
-
-              /* Now free the edge... */
-              g_free (edge);
-              ret = g_list_delete_link (ret, delete_me);
-            }
-          else
-            edge_iter = edge_iter->next;
-
-          /* edge_iter was already advanced above */
-        }
-
-      strut_iter = strut_iter->next;
-    }
+  ret = meta_rectangle_remove_intersections_with_boxes_from_edges (ret, 
+                                                                   all_struts,
+                                                                   TRUE);
 
   /* Sort the list */
-  ret = g_list_sort (ret, sort_edges);
+  ret = g_list_sort (ret, meta_rectangle_edge_cmp);
 
   return ret;
 }
diff --git a/src/boxes.h b/src/boxes.h
index 00cc13cc..9d6fb56b 100644
--- a/src/boxes.h
+++ b/src/boxes.h
@@ -201,12 +201,34 @@ void meta_rectangle_find_linepoint_closest_to_point (double x1,    double y1,
                                                      double px,    double py,
                                                      double *valx, double *valy);
 
+/***************************************************************************/
+/*                                                                         */
+/* Switching gears to code for edges instead of just rectangles            */
+/*                                                                         */
+/***************************************************************************/
+
+/* Compare two edges, so that sorting functions can put a list of edges in
+ * canonical order.
+ */
+gint   meta_rectangle_edge_cmp (gconstpointer a, gconstpointer b);
+
+/* Removes an parts of edges in the given list that intersect any box in the
+ * given rectangle list.  Returns the result.
+ */
+GList* meta_rectangle_remove_intersections_with_boxes_from_edges (
+                                           GList *edges,
+                                           const GSList *rectangles,
+                                           gboolean      rectangles_are_struts);
+
 /* Finds all the edges of an onscreen region, returning a GList* of
  * MetaEdgeRect's.
  */
 GList* meta_rectangle_find_onscreen_edges (const MetaRectangle *basic_rect,
                                            const GSList        *all_struts);
 
+/* Finds edges between adjacent xineramas which are not covered by the given
+ * struts.
+ */
 GList* meta_rectangle_find_nonintersected_xinerama_edges (
                                            const GList         *xinerama_rects,
                                            const GSList        *all_struts);
diff --git a/src/display.c b/src/display.c
index 4d39a336..8286ca5d 100644
--- a/src/display.c
+++ b/src/display.c
@@ -120,6 +120,8 @@ static void    prefs_changed_callback    (MetaPreference pref,
 
 static void    sanity_check_timestamps   (MetaDisplay *display,
                                           Time         known_good_timestamp);
+static void    compute_resistance_and_snapping_edges (MetaDisplay *display);
+
 
 static void
 set_utf8_string_hint (MetaDisplay *display,
@@ -3370,6 +3372,18 @@ meta_display_begin_grab_op (MetaDisplay *display,
   g_assert (display->grab_window != NULL || display->grab_screen != NULL);
   g_assert (display->grab_op != META_GRAB_OP_NONE);
 
+  /* If this is a move or resize, cache the window edges for
+   * resistance/snapping
+   */
+  if (meta_grab_op_is_resizing (display->grab_op) || 
+      meta_grab_op_is_moving (display->grab_op))
+    {
+      meta_topic (META_DEBUG_WINDOW_OPS,
+                  "Computing edges to resist-movement or snap-to for %s.\n",
+                  window->desc);
+      compute_resistance_and_snapping_edges (display);
+    }
+
   /* Save the old stacking */
   if (GRAB_OP_IS_WINDOW_SWITCH (display->grab_op))
     {
@@ -3723,6 +3737,203 @@ meta_display_ungrab_focus_window_button (MetaDisplay *display,
   }
 }
 
+#define WINDOW_EDGES_RELEVANT(window, display) \
+  meta_window_should_be_showing (window) &&    \
+  window->screen == display->grab_screen &&    \
+  window         != display->grab_window &&    \
+  window->type   != META_WINDOW_DESKTOP &&     \
+  window->type   != META_WINDOW_MENU    &&     \
+  window->type   != META_WINDOW_SPLASHSCREEN
+
+static void
+compute_resistance_and_snapping_edges (MetaDisplay *display)
+{
+  GList *stacked_windows;
+  GList *cur_window_iter;
+  GList *edges;
+  /* Lists of window positions (rects) and their relative stacking positions */
+  int stack_position;
+  GSList *obscuring_windows, *obscuring_docks;
+  GSList *window_stacking, *dock_stacking;
+  /* The portions of the above lists that still remain at the stacking position
+   * in the layer that we are working on
+   */
+  GSList *rem_windows, *rem_docks, *rem_win_stacking, *rem_dock_stacking;
+
+  /*
+   * 1st: Get the list of relevant windows, from bottom to top
+   */
+  stacked_windows = 
+    meta_stack_list_windows (display->grab_screen->stack,
+                             display->grab_screen->active_workspace);
+
+  /*
+   * 2nd: we need to separate that stacked list into a list of normal
+   * windows that can obscure other edges, and a list of docks that can
+   * obscure the edges of other windows.  To make sure we only have windows
+   * obscuring those below it instead of going both ways, we also need to
+   * keep some counter lists.  Messy, I know.
+   */
+  obscuring_windows = obscuring_docks = window_stacking = dock_stacking = NULL;
+  cur_window_iter = stacked_windows;
+  stack_position = 0;
+  while (cur_window_iter != NULL)
+    {
+      MetaWindow *cur_window = cur_window_iter->data;
+      if (WINDOW_EDGES_RELEVANT (cur_window, display))
+        {
+          MetaRectangle *new_rect;
+          new_rect = g_new (MetaRectangle, 1);
+          meta_window_get_outer_rect (cur_window, new_rect);
+          if (cur_window->type != META_WINDOW_DOCK)
+            {
+              obscuring_windows = g_slist_prepend (obscuring_windows, new_rect);
+              window_stacking = 
+                g_slist_prepend (window_stacking, 
+                                 GINT_TO_POINTER (stack_position));
+            }
+          else
+            {
+              obscuring_docks = g_slist_prepend (obscuring_docks, new_rect);
+              dock_stacking = 
+                g_slist_prepend (dock_stacking, 
+                                 GINT_TO_POINTER (stack_position));
+            }
+        }
+
+      stack_position++;
+      cur_window_iter = cur_window_iter->next;
+    }
+  /* Put 'em in bottom to top order */
+  rem_windows       = g_slist_reverse (obscuring_windows);
+  rem_docks         = g_slist_reverse (obscuring_docks);
+  rem_win_stacking  = g_slist_reverse (window_stacking);
+  rem_dock_stacking = g_slist_reverse (dock_stacking);
+
+  /*
+   * 3rd: loop over the windows again, this time getting the edges from
+   * them and removing intersections with the relevant obscuring_windows &
+   * obscuring_docks.
+   */
+  edges = NULL;
+  stack_position = 0;
+  cur_window_iter = stacked_windows;
+  while (cur_window_iter != NULL)
+    {
+      MetaRectangle  cur_rect;
+      MetaWindow    *cur_window = cur_window_iter->data;
+      meta_window_get_outer_rect (cur_window, &cur_rect);
+
+      /* Check if we want to use this window's edges for edge
+       * resistance (note that dock edges are considered screen edges
+       * which are handled separately
+       */
+      if (WINDOW_EDGES_RELEVANT (cur_window, display) &&
+          cur_window->type != META_WINDOW_DOCK)
+        {
+          GList *new_edges;
+          MetaEdge *new_edge;
+          MetaRectangle reduced;
+
+          /* We don't care about snapping to any portion of the window that
+           * is offscreen (we also don't care about parts of edges covered
+           * by other windows or DOCKS, but that's handled below).
+           */
+          meta_rectangle_intersect (&cur_rect, 
+                                    &display->grab_screen->rect,
+                                    &reduced);
+
+          new_edges = NULL;
+
+          /* Add left edge */
+          new_edge = g_new (MetaEdge, 1);
+          new_edge->rect = reduced;
+          new_edge->rect.width = 0;
+          new_edge->side_type = META_DIRECTION_LEFT;
+          new_edge->edge_type = META_EDGE_WINDOW;
+          new_edges = g_list_prepend (new_edges, new_edge);
+
+          /* Add right edge */
+          new_edge = g_new (MetaEdge, 1);
+          new_edge->rect = reduced;
+          new_edge->rect.x += new_edge->rect.width;
+          new_edge->rect.width = 0;
+          new_edge->side_type = META_DIRECTION_RIGHT;
+          new_edge->edge_type = META_EDGE_WINDOW;
+          new_edges = g_list_prepend (new_edges, new_edge);
+          
+          /* Add top edge */
+          new_edge = g_new (MetaEdge, 1);
+          new_edge->rect = reduced;
+          new_edge->rect.height = 0;
+          new_edge->side_type = META_DIRECTION_TOP;
+          new_edge->edge_type = META_EDGE_WINDOW;
+          new_edges = g_list_prepend (new_edges, new_edge);
+
+          /* Add bottom edge */
+          new_edge = g_new (MetaEdge, 1);
+          new_edge->rect = reduced;
+          new_edge->rect.y += new_edge->rect.height;
+          new_edge->rect.height = 0;
+          new_edge->side_type = META_DIRECTION_BOTTOM;
+          new_edge->edge_type = META_EDGE_WINDOW;
+          new_edges = g_list_prepend (new_edges, new_edge);
+
+          /* Update the remaining windows to only those at a higher
+           * stacking position than this one.
+           */
+          while (rem_win_stacking && 
+                 stack_position >= (int)rem_win_stacking->data)
+            {
+              rem_windows      = rem_windows->next;
+              rem_win_stacking = rem_win_stacking->next;
+            }
+          while (rem_dock_stacking && 
+                 stack_position >= (int)rem_dock_stacking->data)
+            {
+              rem_docks         = rem_docks->next;
+              rem_dock_stacking = rem_dock_stacking->next;
+            }
+
+          /* Remove edge portions overlapped by rem_windows and rem_docks */
+          new_edges = 
+            meta_rectangle_remove_intersections_with_boxes_from_edges (
+              new_edges,
+              rem_windows,
+              FALSE);
+          new_edges = 
+            meta_rectangle_remove_intersections_with_boxes_from_edges (
+              new_edges,
+              rem_docks,
+              TRUE);
+
+          /* Save the new edges */
+          edges = g_list_concat (new_edges, edges);
+        }
+
+      stack_position++;
+      cur_window_iter = cur_window_iter->next;
+    }
+
+  /* Free the memory used by the obscuring windows/docks lists */
+  g_slist_free (window_stacking);
+  g_slist_free (dock_stacking);
+  /* FIXME: Shouldn't there be a helper function to make this one line of code
+   * to free a list instead of four ugly ones?
+   */
+  g_slist_foreach (obscuring_windows, 
+                   (void (*)(gpointer,gpointer))&g_free, /* ew, for ugly */
+                   NULL);
+  g_slist_free (obscuring_windows);
+  g_slist_foreach (obscuring_docks, 
+                   (void (*)(gpointer,gpointer))&g_free, /* ew, for ugly */
+                   NULL);
+  g_slist_free (obscuring_docks);
+
+  /* Sort the list */
+  edges = g_list_sort (edges, meta_rectangle_edge_cmp);
+}
+
 void
 meta_display_increment_event_serial (MetaDisplay *display)
 {
diff --git a/src/display.h b/src/display.h
index 5d587533..50512146 100644
--- a/src/display.h
+++ b/src/display.h
@@ -477,8 +477,6 @@ typedef enum
 {
   META_TAB_LIST_NORMAL,
   META_TAB_LIST_DOCKS
-  
-
 } MetaTabList;
 
 GList* meta_display_get_tab_list (MetaDisplay   *display,
diff --git a/src/testboxes.c b/src/testboxes.c
index 6a6a1649..77762907 100644
--- a/src/testboxes.c
+++ b/src/testboxes.c
@@ -1148,7 +1148,7 @@ test_find_nonintersected_xinerama_edges ()
   edges = get_xinerama_edges (1, 2);
   tmp = NULL;
   tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,   20, 0, 1080, right));
-  tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,   20, 0, 1080, left));
+  tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,   20, 0, 1180, left));
 #if 0
   #define FUDGE 50
   char big_buffer1[1 + (16+FUDGE)*38], big_buffer2[1 + 16*38];
@@ -1171,7 +1171,7 @@ test_find_nonintersected_xinerama_edges ()
   tmp = g_list_prepend (tmp, new_xinerama_edge ( 900,  600,  700, 0, top));
   tmp = g_list_prepend (tmp, new_xinerama_edge (   0,  600,  700, 0, top));
   tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,  675, 0,  425, right));
-  tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,  675, 0,  425, left));
+  tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,  675, 0,  525, left));
   verify_edge_lists_are_equal (edges, tmp);
   meta_rectangle_free_list_and_elements (tmp);
   meta_rectangle_free_list_and_elements (edges);
@@ -1183,6 +1183,7 @@ test_find_nonintersected_xinerama_edges ()
   tmp = NULL;
   tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,  600,  800, 0, bottom));
   tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,  600,  800, 0, top));
+  tmp = g_list_prepend (tmp, new_xinerama_edge ( 800,  600,  0, 600, right));
   verify_edge_lists_are_equal (edges, tmp);
   meta_rectangle_free_list_and_elements (tmp);
   meta_rectangle_free_list_and_elements (edges);