Very basic edge resistance stuff starting to work. Only for moves,

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

	Very basic edge resistance stuff starting to work.  Only for
	moves, debugging threshold ridiculously huge for easier testing,
	snap-moving disabled, yadda yadda yadda IT ISN'T READY YET.

	* src/display.c:

	(find_index_of_edge_near_position):
	new binary-search-esque function

	(apply_edge_resistance):
	new function, only very basics implemented so far (with a
	ridiculously huge threshold just for testing)

	(cache_edges):
	remove an extraneous debugging warning that I missed earlier

	* src/display.[ch]:

	(meta_display_apply_edge_resistance):
	new public function, doing work through calls to
	apply_edge_resistance() currently

	* src/window.c:

	(update_move):
	temporarily disable snap moving, call
	meta_display_apply_edge_resistance() to get some basic edge
	resistance working

4 files changed, 294 insertions, 8 deletions

diff --git a/ChangeLog b/ChangeLog
index 68611951..176432e3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,34 @@
+2005-11-08  Elijah Newren  <newren@gmail.com>
+
+	Very basic edge resistance stuff starting to work.  Only for
+	moves, debugging threshold ridiculously huge for easier testing,
+	snap-moving disabled, yadda yadda yadda IT ISN'T READY YET.
+
+	* src/display.c:
+
+	(find_index_of_edge_near_position):
+	new binary-search-esque function
+
+	(apply_edge_resistance):
+	new function, only very basics implemented so far (with a
+	ridiculously huge threshold just for testing)
+
+	(cache_edges):
+	remove an extraneous debugging warning that I missed earlier
+
+	* src/display.[ch]:
+
+	(meta_display_apply_edge_resistance):
+	new public function, doing work through calls to
+	apply_edge_resistance() currently
+
+	* src/window.c:
+
+	(update_move):
+	temporarily disable snap moving, call
+	meta_display_apply_edge_resistance() to get some basic edge
+	resistance working
+
 2005-11-07  Elijah Newren  <newren@gmail.com>
 
 	* src/boxes.[ch]:
diff --git a/src/display.c b/src/display.c
index 16a86ab0..1f97327f 100644
--- a/src/display.c
+++ b/src/display.c
@@ -3768,6 +3768,217 @@ meta_display_ungrab_focus_window_button (MetaDisplay *display,
   }
 }
 
+/***** Begin gobs of edge_resistance functions *****/
+
+static int
+find_index_of_edge_near_position (GArray   *edges,
+                                  int       position,
+                                  gboolean  want_interval_min,
+                                  gboolean  horizontal)
+{
+
+  /* This is basically like a binary search, except that we're trying to
+   * find a range instead of an exact value.  So, if we have in our array
+   *   Value: 3  27 316 316 316 505 522 800 1213
+   *   Index: 0   1   2   3   4   5   6   7    8
+   * and we call this function with position=500 & want_interval_min=TRUE
+   * then we should get 5 (because 505 is the first value bigger than 500).
+   * If we call this function with position=805 and want_interval_min=FALSE
+   * then we should get 7 (because 800 is the last value smaller than 800).
+   * A couple more, to make things clear:
+   *    position  want_interval_min  correct_answer
+   *         316               TRUE               2
+   *         316              FALSE               4
+   *           2              FALSE              -1
+   *        2000               TRUE               9
+   */
+  int low, high, mid;
+  int compare;
+  MetaEdge *edge;
+
+  /* Initialize mid, edge, & compare in the off change that the array only
+   * has one element.
+   */
+  mid  = 0;
+  edge = g_array_index (edges, MetaEdge*, mid);
+  compare = horizontal ? edge->rect.x : edge->rect.y;
+
+  /* Begin the search... */
+  low  = 0;
+  high = edges->len - 1;
+  while (low < high)
+    {
+      mid = low + (high - low)/2;
+      edge = g_array_index (edges, MetaEdge*, mid);
+      compare = horizontal ? edge->rect.x : edge->rect.y;
+
+      if (compare == position)
+        break;
+
+      if (compare > position)
+        high = mid - 1;
+      else
+        low = mid + 1;
+    }
+
+  /* mid should now be _really_ close to the index we want, so we start
+   * linearly searching.  However, note that we don't know if mid is less
+   * than or greater than what we need and it's possible that there are
+   * several equal values equal to what we were searching for and we ended
+   * up in the middle of them instead of at the end.  So we may need to
+   * move mid multiple locations over.
+   */
+  if (want_interval_min)
+    {
+      while (compare >= position && mid > 0)
+        {
+          mid--;
+          edge = g_array_index (edges, MetaEdge*, mid);
+          compare = horizontal ? edge->rect.x : edge->rect.y;
+        }
+      while (compare < position && mid < (int)edges->len - 1)
+        {
+          mid++;
+          edge = g_array_index (edges, MetaEdge*, mid);
+          compare = horizontal ? edge->rect.x : edge->rect.y;
+        }
+
+      /* Special case for no values in array big enough */
+      if (compare < position)
+        return edges->len;
+
+      /* Return the found value */
+      return mid;
+    }
+  else
+    {
+      while (compare <= position && mid < (int)edges->len - 1)
+        {
+          mid++;
+          edge = g_array_index (edges, MetaEdge*, mid);
+          compare = horizontal ? edge->rect.x : edge->rect.y;
+        }
+      while (compare > position && mid > 0)
+        {
+          mid--;
+          edge = g_array_index (edges, MetaEdge*, mid);
+          compare = horizontal ? edge->rect.x : edge->rect.y;
+        }
+
+      /* Special case for no values in array small enough */
+      if (compare > position)
+        return -1;
+
+      /* Return the found value */
+      return mid;
+    }
+}
+
+static int
+apply_edge_resistance (int                  old_pos,
+                       int                  new_pos,
+                       const MetaRectangle *new_rect,
+                       GArray              *edges,
+                       gboolean             xdir)
+{
+  int i, begin, end;
+  gboolean increasing = new_pos > old_pos;
+  int      increment = increasing ? 1 : -1;
+
+  /* ridiculously huge for testing */
+  const int EDGE_RESISTANCE_THRESHOLD = 96;
+
+  if (old_pos == new_pos)
+    return new_pos;
+
+  begin = find_index_of_edge_near_position (edges, old_pos,  increasing, xdir);
+  end   = find_index_of_edge_near_position (edges, new_pos, !increasing, xdir);
+
+  i = begin;
+  while ((increasing  && i <= end) ||
+         (!increasing && i >= end))
+    {
+      gboolean  edges_align;
+      MetaEdge *edge = g_array_index (edges, MetaEdge*, i);
+      int       compare = xdir ? edge->rect.x : edge->rect.y;
+
+      /* Find out if this edge is relevant */
+      edges_align = xdir ? 
+        meta_rectangle_vert_overlap (&edge->rect, new_rect) :
+        meta_rectangle_horiz_overlap (&edge->rect, new_rect);
+
+      /* If the edge is relevant and we haven't moved at least
+       * EDGE_RESISTANCE_THRESHOLD pixels past this edge, stop movement at
+       * this edge.
+       */
+      if (edges_align && ABS (compare - new_pos) < EDGE_RESISTANCE_THRESHOLD)
+        return compare;
+
+      /* Go to the next edge in the range */
+      i += increment;
+    }
+
+  return new_pos;
+}
+
+/* This function takes the position (including any frame) of the window and
+ * a proposed new position (ignoring edge resistance/snapping), and then
+ * applies edge resistance to EACH edge (separately) updating new_outer.
+ * It returns true if new_outer is modified, false otherwise.
+ *
+ * display->grab_edge_resistance_data MUST already be setup or calling this
+ * function will cause a crash.
+ */
+gboolean meta_display_apply_edge_resistance (MetaDisplay         *display,
+                                             const MetaRectangle *old_outer,
+                                             MetaRectangle       *new_outer)
+{
+  /* FIXME: I need to know and use
+   *   a) whether this is mouse or keyboard resize (if keyboard resize, a
+   *      set amount can just be ignored and adds to the "buildup"
+   *      parameter)
+   *   b) if the user wants to auto-snap instead of just edge-resist
+   */
+  MetaEdgeResistanceData *edge_data;
+  MetaRectangle           modified_rect;
+  gboolean                modified;
+  int new_left, new_right, new_top, new_bottom;
+
+  g_assert (display->grab_edge_resistance_data != NULL);
+  edge_data = display->grab_edge_resistance_data;
+
+  /* Now, do the edge resistance application */
+  new_left   = apply_edge_resistance (BOX_LEFT (*old_outer),
+                                      BOX_LEFT (*new_outer),
+                                      new_outer,
+                                      edge_data->left_edges,
+                                      TRUE);
+  new_right  = apply_edge_resistance (BOX_RIGHT (*old_outer),
+                                      BOX_RIGHT (*new_outer),
+                                      new_outer,
+                                      edge_data->right_edges,
+                                      TRUE);
+  new_top    = apply_edge_resistance (BOX_TOP (*old_outer),
+                                      BOX_TOP (*new_outer),
+                                      new_outer,
+                                      edge_data->top_edges,
+                                      FALSE);
+  new_bottom = apply_edge_resistance (BOX_BOTTOM (*old_outer),
+                                      BOX_BOTTOM (*new_outer),
+                                      new_outer,
+                                      edge_data->bottom_edges,
+                                      FALSE);
+
+  /* Determine whether anything changed, and save the changes */
+  modified_rect = meta_rect (new_left, 
+                             new_top,
+                             new_right - new_left,
+                             new_bottom - new_top);
+  modified = !meta_rectangle_equal (new_outer, &modified_rect);
+  *new_outer = modified_rect;
+  return modified;
+}
+
 static void
 cleanup_edges (MetaDisplay *display)
 {
@@ -3879,8 +4090,6 @@ cache_edges (MetaDisplay *display,
         }
     }
 
-  meta_warning ("%d %d %d %d\n", num_left, num_right, num_top, num_bottom);
-
   /*
    * 2nd: Allocate the edges
    */
@@ -4147,6 +4356,8 @@ compute_resistance_and_snapping_edges (MetaDisplay *display)
   g_list_free (edges);
 }
 
+/***** End gobs of edge_resistance functions *****/
+
 void
 meta_display_increment_event_serial (MetaDisplay *display)
 {
diff --git a/src/display.h b/src/display.h
index 3784d466..6a438127 100644
--- a/src/display.h
+++ b/src/display.h
@@ -449,6 +449,10 @@ void meta_display_grab_focus_window_button   (MetaDisplay *display,
 void meta_display_ungrab_focus_window_button (MetaDisplay *display,
                                               MetaWindow  *window);
 
+gboolean meta_display_apply_edge_resistance  (MetaDisplay         *display,
+                                              const MetaRectangle *old_outer,
+                                              MetaRectangle       *new_outer);
+
 /* make a request to ensure the event serial has changed */
 void     meta_display_increment_event_serial (MetaDisplay *display);
 
diff --git a/src/window.c b/src/window.c
index d6ec5868..730462b1 100644
--- a/src/window.c
+++ b/src/window.c
@@ -6377,6 +6377,7 @@ update_move (MetaWindow  *window,
   int dx, dy;
   int new_x, new_y;
   int old_x, old_y;
+  MetaRectangle old_outer, new_outer;
   int shake_threshold;
   
   window->display->grab_latest_motion_x = x;
@@ -6486,6 +6487,50 @@ update_move (MetaWindow  *window,
 
   meta_window_get_position (window, &old_x, &old_y);
 
+  /* Don't allow movement in the maximized directions */
+  if (window->maximized_horizontally)
+    new_x = old_x;
+  if (window->maximized_vertically)
+    new_y = old_y;
+
+  /* Do any edge resistance/snapping */
+  meta_window_get_outer_rect (window, &old_outer);
+  new_outer = old_outer;
+  new_outer.x += (new_x - old_x);
+  new_outer.y += (new_y - old_y);
+
+  if (meta_display_apply_edge_resistance (window->display,
+                                          &old_outer,
+                                          &new_outer))
+    {
+      /* meta_display_apply_edge_resistance independently applies
+       * resistance to both the right and left edges of new_outer as both
+       * could meet areas of resistance.  But we don't want a resize, so we
+       * just have both edges move according to the stricter of the
+       * resistances.  Same thing goes for top & bottom edges.
+       */
+      int left_change, right_change, smaller_x_change;
+      int top_change, bottom_change, smaller_y_change;
+
+      left_change  = BOX_LEFT (new_outer)  - BOX_LEFT (old_outer);
+      right_change = BOX_RIGHT (new_outer) - BOX_RIGHT (old_outer);
+      if (ABS (left_change) < ABS (right_change))
+        smaller_x_change = left_change;
+      else
+        smaller_x_change = right_change;
+
+      top_change    = BOX_TOP (new_outer)    - BOX_TOP (old_outer);
+      bottom_change = BOX_BOTTOM (new_outer) - BOX_BOTTOM (old_outer);
+      if (ABS (top_change) < ABS (bottom_change))
+        smaller_y_change = top_change;
+      else
+        smaller_y_change = bottom_change;
+
+      new_x = old_x + smaller_x_change;
+      new_y = old_y + smaller_y_change;
+    }
+
+#if 0
   if (mask & ShiftMask)
     {
       /* snap to edges */
@@ -6495,12 +6540,7 @@ update_move (MetaWindow  *window,
       if (new_y != old_y)
         new_y = meta_window_find_nearest_horizontal_edge (window, new_y);
     }
-
-  /* Don't allow movement in the maximized directions */
-  if (window->maximized_horizontally)
-    new_x = old_x;
-  if (window->maximized_vertically)
-    new_y = old_y;
+#endif
 
   if (window->display->grab_wireframe_active)
     meta_window_update_wireframe (window, new_x, new_y,