Implement edge resistance when moving frames.

2 files changed, 264 insertions, 14 deletions

diff --git a/ChangeLog b/ChangeLog
index eb1e2c0..f712496 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+2009-08-26  Gary Wong  <gtw@gnu.org>
+
+	* frame.c (frame_motion_notify, frame_button_release): Implement
+	edge resistance when moving frames.
+	(build_edges, free_edges, h_edge_compare, v_edge_compare): New
+	functions.
+
 2009-08-25  Gary Wong  <gtw@gnu.org>
 
 	* frame.c (frame_motion_notify): Ignore single pixel movements, and
@@ -39,4 +46,3 @@
 	keyboard.h, managed.c, managed.h, root.c, root.h, utf8.c, utf8.h,
 	window-table.c, window-table.h, Makefile.am, configure.ac: New
 	files, and version 1.0 release.
-
diff --git a/frame.c b/frame.c
index 7a43802..7994978 100644
--- a/frame.c
+++ b/frame.c
@@ -24,6 +24,7 @@
 #include <config.h>
 
 #include <assert.h>
+#include <stdlib.h>
 #include <xcb/xcb.h>
 
 #include "gwm.h"
@@ -31,6 +32,8 @@
 #include "frame.h"
 #include "window-table.h"
 
+#define EDGE_RESIST 8
+
 static enum _window_operation {
     OP_NONE, OP_MOVE, OP_RESIZE
 } window_op;
@@ -40,6 +43,127 @@ static enum size_which {
 static int dx, dy, var_x, fixed_x, var_y, fixed_y, init_x, init_y, moved;
 static struct gwm_window *feedback;
 
+static struct h_edge {
+    int x_min, x_max;
+    int y;
+} *t_edges, *b_edges;
+
+static struct v_edge {
+    int x;
+    int y_min, y_max;
+} *l_edges, *r_edges;
+
+static int num_t_edges, num_b_edges, num_l_edges, num_r_edges;
+
+static int h_edge_compare( const void *v0, const void *v1 ) {
+
+    const struct h_edge *e0 = v0, *e1 = v1;
+
+    return e0->y - e1->y;
+}
+
+static int v_edge_compare( const void *v0, const void *v1 ) {
+
+    const struct v_edge *e0 = v0, *e1 = v1;
+
+    return e0->x - e1->x;
+}
+
+static void build_edges( int screen ) {
+
+    struct gwm_window *window, **windowp, **end;
+    
+    assert( !t_edges );
+    assert( !b_edges );
+    assert( !l_edges );
+    assert( !r_edges );
+
+    t_edges = malloc( ( windows.used + 1 ) * sizeof *t_edges );
+    b_edges = malloc( ( windows.used + 1 ) * sizeof *b_edges );
+    l_edges = malloc( ( windows.used + 1 ) * sizeof *l_edges );
+    r_edges = malloc( ( windows.used + 1 ) * sizeof *r_edges );
+
+    t_edges[ 0 ].x_min = b_edges[ 0 ].x_min = 0;
+    t_edges[ 0 ].x_max = b_edges[ 0 ].x_max =
+	screens[ screen ]->width_in_pixels;
+    t_edges[ 0 ].y = screens[ screen ]->height_in_pixels;
+    b_edges[ 0 ].y = 0;
+    
+    l_edges[ 0 ].x = screens[ screen ]->width_in_pixels;
+    r_edges[ 0 ].x = 0;
+    l_edges[ 0 ].y_min = r_edges[ 0 ].y_min = 0;
+    l_edges[ 0 ].y_max = r_edges[ 0 ].y_max =
+	screens[ screen ]->height_in_pixels;
+    
+    num_t_edges = num_b_edges = num_l_edges = num_r_edges = 1;
+
+    end = windows.values + windows.used;
+    for( windowp = windows.values; windowp < end; windowp++ )
+	if( ( window = *windowp )->type == WINDOW_FRAME &&
+	    window->screen == screen ) {
+	    int t = window->u.frame.y,
+		b = window->u.frame.y + window->u.frame.height +
+		( FRAME_X_BORDER << 1 ),
+		l = window->u.frame.x,
+		r = window->u.frame.x + window->u.frame.width +
+		( FRAME_X_BORDER << 1 );
+
+	    if( t >= screens[ screen ]->height_in_pixels || b <= 0 ||
+		l >= screens[ screen ]->width_in_pixels || r <= 0 )
+		continue; /* window is entirely off screen; ignore */
+	    
+	    if( t >= 0 ) {
+		t_edges[ num_t_edges ].x_min = l;
+		t_edges[ num_t_edges ].x_max = r;
+		t_edges[ num_t_edges ].y = t;
+		num_t_edges++;
+	    }
+	    
+	    if( b <= screens[ screen ]->height_in_pixels ) {
+		b_edges[ num_b_edges ].x_min = l;
+		b_edges[ num_b_edges ].x_max = r;
+		b_edges[ num_b_edges ].y = b;
+		num_b_edges++;
+	    }
+	    
+	    if( l >= 0 ) {
+		l_edges[ num_l_edges ].x = l;
+		l_edges[ num_l_edges ].y_min = t;
+		l_edges[ num_l_edges ].y_max = b;
+		num_l_edges++;
+	    }
+	    
+	    if( r <= screens[ screen ]->width_in_pixels ) {
+		r_edges[ num_r_edges ].x = r;
+		r_edges[ num_r_edges ].y_min = t;
+		r_edges[ num_r_edges ].y_max = b;
+		num_r_edges++;
+	    }
+	}
+
+    qsort( t_edges, num_t_edges, sizeof *t_edges, h_edge_compare );
+    qsort( b_edges, num_b_edges, sizeof *b_edges, h_edge_compare );
+    qsort( l_edges, num_l_edges, sizeof *l_edges, v_edge_compare );
+    qsort( r_edges, num_r_edges, sizeof *r_edges, v_edge_compare );
+}
+
+static void free_edges( void ) {
+
+    assert( t_edges );
+    assert( b_edges );
+    assert( l_edges );
+    assert( r_edges );
+    
+    free( t_edges );
+    t_edges = NULL;
+    free( b_edges );
+    b_edges = NULL;
+    free( l_edges );
+    l_edges = NULL;
+    free( r_edges );
+    r_edges = NULL;
+}
+
 static void recalc_size( struct gwm_window *window, int x, int y,
 			 xcb_timestamp_t t ) {
 
@@ -245,28 +369,146 @@ static void frame_motion_notify( struct gwm_window *window,
 
     if( !moved ) {
 	/* Ignore single pixel movements. */
-	if( abs( ev->root_x - init_x ) > 1 || abs( ev->root_y - init_y ) > 1 )
+	if( abs( ev->root_x - init_x ) > 1 || abs( ev->root_y - init_y ) > 1 ) {
 	    moved = TRUE;
-	else
+
+	    build_edges( window->screen );
+	} else
 	    return;
     }
     
-    /* FIXME Detect and account for window and screen edges. */
-
     switch( window_op ) {
+	int old_t, old_b, old_l, old_r, new_t, new_b, new_l, new_r;
+	
     case OP_MOVE:
-	values[ 0 ] = ev->root_x - dx - FRAME_X_BORDER;
-	values[ 1 ] = ev->root_y - dy - FRAME_X_BORDER;
-	xcb_configure_window( c, window->w, XCB_CONFIG_WINDOW_X |
-			      XCB_CONFIG_WINDOW_Y, values );
+	old_t = window->u.frame.y;
+	old_b = old_t + window->u.frame.height + ( FRAME_X_BORDER << 1 );
+	old_l = window->u.frame.x;
+	old_r = old_l + window->u.frame.width + ( FRAME_X_BORDER << 1 );
+	new_t = ev->root_y - dy - FRAME_X_BORDER;
+	new_b = new_t + window->u.frame.height + ( FRAME_X_BORDER << 1 );
+	new_l = ev->root_x - dx - FRAME_X_BORDER;
+	new_r = new_l + window->u.frame.width + ( FRAME_X_BORDER << 1 );
+
+	if( !( ev->state & XCB_MOD_MASK_CONTROL ) ) {
+	    int dx = 0, dy = 0;
+	    
+	    if( new_t < old_t ) {
+		/* Trying to move up; look for bottom edges with
+		   new_t < y <= new_t + EDGE_RESIST. */
+		int i0 = 0, i1 = num_b_edges - 1, i;
+
+		while( i1 > i0 + 1 ) {
+		    int i_mid = ( i0 + i1 ) >> 1;
+
+		    if( b_edges[ i_mid ].y <= new_t )
+			i0 = i_mid;
+		    else
+			i1 = i_mid;
+		}
+
+		while( i0 < num_b_edges && b_edges[ i0 ].y <= new_t )
+		    i0++;
+		
+		for( i = i0; i < num_b_edges && b_edges[ i ].y <=
+			 new_t + EDGE_RESIST; i++ )
+		    if( b_edges[ i ].x_min < new_r &&
+			b_edges[ i ].x_max > new_l )
+			dy = b_edges[ i ].y - new_t;
+	    } else if( new_b > old_b ) {
+		/* Trying to move down; look for top edges with
+		   new_b > y >= new_b - EDGE_RESIST. */
+		int i0 = 0, i1 = num_t_edges - 1, i;
+
+		while( i1 > i0 + 1 ) {
+		    int i_mid = ( i0 + i1 ) >> 1;
+
+		    if( t_edges[ i_mid ].y >= new_b )
+			i1 = i_mid;
+		    else
+			i0 = i_mid;
+		}
+
+		while( i1 >= 0 && t_edges[ i1 ].y >= new_b )
+		    i1--;
+		
+		for( i = i1; i >= 0 && t_edges[ i ].y >=
+			 new_b - EDGE_RESIST; i-- )
+		    if( t_edges[ i ].x_min < new_r &&
+			t_edges[ i ].x_max > new_l )
+			dy = t_edges[ i ].y - new_b;
+	    }
+	    
+	    new_t += dy;
+	    new_b += dy;
+	    
+	    if( new_l < old_l ) {
+		/* Trying to move left; look for right edges with
+		   new_l < x <= new_l + EDGE_RESIST. */
+		int i0 = 0, i1 = num_r_edges - 1, i;
+
+		while( i1 > i0 + 1 ) {
+		    int i_mid = ( i0 + i1 ) >> 1;
+
+		    if( r_edges[ i_mid ].x <= new_l )
+			i0 = i_mid;
+		    else
+			i1 = i_mid;
+		}
+
+		while( i0 < num_r_edges && r_edges[ i0 ].x <= new_l )
+		    i0++;
+		
+		for( i = i0; i < num_r_edges && r_edges[ i ].x <=
+			 new_l + EDGE_RESIST; i++ )
+		    if( r_edges[ i ].y_min < new_b &&
+			r_edges[ i ].y_max > new_t )
+			dx = r_edges[ i ].x - new_l;
+	    } else if( new_r > old_r ) {
+		/* Trying to move right; look for left edges with
+		   new_r > x >= new_r - EDGE_RESIST. */
+		int i0 = 0, i1 = num_l_edges - 1, i;
+
+		while( i1 > i0 + 1 ) {
+		    int i_mid = ( i0 + i1 ) >> 1;
+
+		    if( l_edges[ i_mid ].x >= new_r )
+			i1 = i_mid;
+		    else
+			i0 = i_mid;
+		}
+
+		while( i1 >= 0 && l_edges[ i1 ].x >= new_r )
+		    i1--;
+		
+		for( i = i1; i >= 0 && l_edges[ i ].x >=
+			 new_r - EDGE_RESIST; i-- )
+		    if( l_edges[ i ].y_min < new_b &&
+			l_edges[ i ].y_max > new_t )
+			dx = l_edges[ i ].x - new_r;
+	    }
+
+	    new_l += dx;
+	    new_r += dx;
+	}
 
-	/* We're supposed to send the client a synthetic ConfigureNotify,
-	   but if we actually moved the window, then we'll do that from
-	   our own ConfigureNotify handler. */
+	if( new_t != old_t || new_l != old_l ) {
+	    values[ 0 ] = new_l;
+	    values[ 1 ] = new_t;
+	    xcb_configure_window( c, window->w, XCB_CONFIG_WINDOW_X |
+				  XCB_CONFIG_WINDOW_Y, values );
+	    
+	    /* We're supposed to send the client a synthetic ConfigureNotify,
+	       but if we actually moved the window, then we'll do that from
+	       our own ConfigureNotify handler. */
+	}
 	
 	break;
 
     case OP_RESIZE:
+	/* FIXME Implement edge resistance when resizing, too.  This is a
+	   bit harder than moving, because size constraints might prevent
+	   us from sizing exactly to an edge. */
 	recalc_size( window, ev->root_x, ev->root_y, ev->time );
 	break;
 
@@ -280,8 +522,10 @@ static void frame_button_release( struct gwm_window *window,
 
     if( !final_release( ev ) )
 	return;
-    
-    if( window_op && !moved ) {
+
+    if( moved )
+	free_edges();
+    else if( window_op ) {
 	uint32_t n = XCB_STACK_MODE_OPPOSITE;
 	
 	xcb_configure_window( c, window->w, XCB_CONFIG_WINDOW_STACK_MODE,