Index: uspace/lib/gui/grid.c
===================================================================
--- uspace/lib/gui/grid.c	(revision 6d5e378b28e2c858f3813b5d4d57fa46f709d753)
+++ uspace/lib/gui/grid.c	(revision ccb5165d35609490f8ef4d150295fdf1e827c01f)
@@ -1,4 +1,5 @@
 /*
  * Copyright (c) 2012 Petr Koupy
+ * Copyright (c) 2013 Martin Decky
  * All rights reserved.
  *
@@ -38,33 +39,58 @@
 #include <malloc.h>
 #include <surface.h>
-
 #include "window.h"
 #include "grid.h"
 
-static void paint_internal(widget_t *w)
-{
-	grid_t *grid = (grid_t *) w;
-
+typedef struct {
+	sysarg_t min;
+	sysarg_t max;
+	sysarg_t val;
+} constraints_t;
+
+static void paint_internal(widget_t *widget)
+{
+	grid_t *grid = (grid_t *) widget;
+	
 	surface_t *surface = window_claim(grid->widget.window);
 	if (!surface) {
 		window_yield(grid->widget.window);
-	}
-
-	for (sysarg_t y = w->vpos; y <  w->vpos + w->height; ++y) {
-		for (sysarg_t x = w->hpos; x < w->hpos + w->width; ++x) {
+		return;
+	}
+	
+	// FIXME: Replace with (accelerated) rectangle fill
+	for (sysarg_t y = widget->vpos; y < widget->vpos + widget->height; y++) {
+		for (sysarg_t x = widget->hpos; x < widget->hpos + widget->width; x++)
 			surface_put_pixel(surface, x, y, grid->background);
-		}
-	}
-
+	}
+	
 	window_yield(grid->widget.window);
 }
 
-static widget_t **widget_at(grid_t *grid, size_t row, size_t col)
-{
-	if (row < grid->rows && col < grid->cols) {
+static grid_cell_t *grid_cell_at(grid_t *grid, size_t col, size_t row)
+{
+	if ((col < grid->cols) && (row < grid->rows))
 		return grid->layout + (row * grid->cols + col);
-	} else {
-		return NULL;
-	}
+	
+	return NULL;
+}
+
+static grid_cell_t *grid_coords_at(grid_t *grid, sysarg_t hpos, sysarg_t vpos)
+{
+	for (size_t c = 0; c < grid->cols; c++) {
+		for (size_t r = 0; r < grid->rows; r++) {
+			grid_cell_t *cell = grid_cell_at(grid, c, r);
+			if (cell) {
+				widget_t *widget = cell->widget;
+				
+				if ((widget) && (hpos >= widget->hpos) &&
+				    (vpos >= widget->vpos) &&
+				    (hpos < widget->hpos + widget->width) &&
+				    (vpos < widget->vpos + widget->height))
+					return cell;
+			}
+		}
+	}
+	
+	return NULL;
 }
 
@@ -78,7 +104,6 @@
 {
 	grid_t *grid = (grid_t *) widget;
-
+	
 	deinit_grid(grid);
-
 	free(grid);
 }
@@ -86,5 +111,69 @@
 static void grid_reconfigure(widget_t *widget)
 {
-	/* no-op */
+	/* No-op */
+}
+
+static void adjust_constraints(constraints_t *cons, size_t run,
+    sysarg_t dim_min, sysarg_t dim_max)
+{
+	assert(run > 0);
+	
+	sysarg_t dim_min_part = dim_min / run;
+	sysarg_t dim_min_rem = dim_min % run;
+	
+	sysarg_t dim_max_part = dim_max / run;
+	sysarg_t dim_max_rem = dim_max % run;
+	
+	for (size_t i = 0; i < run; i++) {
+		sysarg_t dim_min_cur = dim_min_part;
+		sysarg_t dim_max_cur = dim_max_part;
+		
+		if (i == run - 1) {
+			dim_min_cur += dim_min_rem;
+			dim_max_cur += dim_max_rem;
+		}
+		
+		/*
+		 * We want the strongest constraint
+		 * for the minimum.
+		 */
+		if (cons[i].min < dim_min_cur)
+			cons[i].min = dim_min_cur;
+		
+		/*
+		 * The comparison is correct, we want
+		 * the weakest constraint for the
+		 * maximum.
+		 */
+		if (cons[i].max < dim_max_cur)
+			cons[i].max = dim_max_cur;
+	}
+}
+
+static void solve_constraints(constraints_t *cons, size_t run, sysarg_t sum)
+{
+	/* Initial solution */
+	sysarg_t cur_sum = 0;
+	
+	for (size_t i = 0; i < run; i++) {
+		cons[i].val = cons[i].min;
+		cur_sum += cons[i].val;
+	}
+	
+	/* Iterative improvement */
+	while (cur_sum < sum) {
+		sysarg_t delta = (sum - cur_sum) / run;
+		if (delta == 0)
+			break;
+		
+		cur_sum = 0;
+		
+		for (size_t i = 0; i < run; i++) {
+			if (cons[i].val + delta < cons[i].max)
+				cons[i].val += delta;
+			
+			cur_sum += cons[i].val;
+		}
+	}
 }
 
@@ -93,61 +182,114 @@
 {
 	grid_t *grid = (grid_t *) widget;
-
+	
 	widget_modify(widget, hpos, vpos, width, height);
 	paint_internal(widget);
-
-	sysarg_t cell_width = width / grid->cols;
-	sysarg_t cell_height = height / grid->rows;
-
-	list_foreach(widget->children, link) {
-		widget_t *child = list_get_instance(link, widget_t, link);
-
-		sysarg_t widget_hpos = 0;
-		sysarg_t widget_vpos = 0;
-		sysarg_t widget_width = 0;
-		sysarg_t widget_height = 0;
-
-		size_t r = 0;
-		size_t c = 0;
-		for (r = 0; r < grid->rows; ++r) {
-			bool found = false;
-			for (c = 0; c < grid->cols; ++c) {
-				widget_t **cell = widget_at(grid, r, c);
-				if (cell && *cell == child) {
-					found = true;
-					break;
+	
+	/* Compute column widths */
+	constraints_t *widths =
+	    (constraints_t *) calloc(grid->cols, sizeof(constraints_t));
+	if (widths) {
+		/* Constrain widths */
+		for (size_t c = 0; c < grid->cols; c++) {
+			widths[c].min = 0;
+			
+			for (size_t r = 0; r < grid->rows; r++) {
+				grid_cell_t *cell = grid_cell_at(grid, c, r);
+				if (!cell)
+					continue;
+				
+				widget_t *widget = cell->widget;
+				if (widget)
+					adjust_constraints(&widths[c], cell->cols,
+					    widget->width_min, widget->width_max);
+			}
+		}
+		
+		solve_constraints(widths, grid->cols, width);
+	}
+	
+	/* Compute row heights */
+	constraints_t *heights =
+	    (constraints_t *) calloc(grid->rows, sizeof(constraints_t));
+	if (heights) {
+		/* Constrain heights */
+		for (size_t r = 0; r < grid->rows; r++) {
+			heights[r].min = 0;
+			
+			for (size_t c = 0; c < grid->cols; c++) {
+				grid_cell_t *cell = grid_cell_at(grid, c, r);
+				if (!cell)
+					continue;
+				
+				widget_t *widget = cell->widget;
+				if (widget) {
+					adjust_constraints(&heights[r], cell->rows,
+					    widget->height_min, widget->height_max);
 				}
 			}
-			if (found) {
-				break;
+		}
+		
+		solve_constraints(heights, grid->rows, height);
+	}
+	
+	/* Rearrange widgets */
+	if ((widths) && (heights)) {
+		sysarg_t cur_vpos = vpos;
+		
+		for (size_t r = 0; r < grid->rows; r++) {
+			sysarg_t cur_hpos = hpos;
+			
+			for (size_t c = 0; c < grid->cols; c++) {
+				grid_cell_t *cell = grid_cell_at(grid, c, r);
+				if (!cell)
+					continue;
+				
+				widget_t *widget = cell->widget;
+				if (widget) {
+					sysarg_t cur_width = 0;
+					sysarg_t cur_height = 0;
+					
+					for (size_t cd = 0; cd < cell->cols; cd++)
+						cur_width += widths[c + cd].val;
+					
+					for (size_t rd = 0; rd < cell->rows; rd++)
+						cur_height += heights[r + rd].val;
+					
+					if ((cur_width > 0) && (cur_height > 0)) {
+						sysarg_t wwidth = cur_width;
+						sysarg_t wheight = cur_height;
+						
+						/*
+						 * Make sure the widget is respects its
+						 * maximal constrains.
+						 */
+						
+						if ((widget->width_max > 0) &&
+						    (wwidth > widget->width_max))
+							wwidth = widget->width_max;
+						
+						if ((widget->height_max > 0) &&
+						    (wheight > widget->height_max))
+							wheight = widget->height_max;
+						
+						widget->rearrange(widget, cur_hpos, cur_vpos,
+						    wwidth, wheight);
+					}
+					
+					
+				}
+				
+				cur_hpos += widths[c].val;
 			}
-		}
-
-		widget_hpos = cell_width * c + hpos;
-		widget_vpos = cell_height * r + vpos;
-
-		for (size_t _c = c; _c < grid->cols; ++_c) {
-			widget_t **cell = widget_at(grid, r, _c);
-			if (cell && *cell == child) {
-				widget_width += cell_width;
-			} else {
-				break;
-			}
-		}
-
-		for (size_t _r = r; _r < grid->rows; ++_r) {
-			widget_t **cell = widget_at(grid, _r, c);
-			if (cell && *cell == child) {
-				widget_height += cell_height;
-			} else {
-				break;
-			}
-		}
-
-		if (widget_width > 0 && widget_height > 0) {
-			child->rearrange(child,
-			    widget_hpos, widget_vpos, widget_width, widget_height);
-		}
-	}
+			
+			cur_vpos += heights[r].val;
+		}
+	}
+	
+	if (widths)
+		free(widths);
+	
+	if (heights)
+		free(heights);
 }
 
@@ -155,8 +297,10 @@
 {
 	paint_internal(widget);
+	
 	list_foreach(widget->children, link) {
 		widget_t *child = list_get_instance(link, widget_t, link);
 		child->repaint(child);
 	}
+	
 	window_damage(widget->window);
 }
@@ -164,5 +308,5 @@
 static void grid_handle_keyboard_event(widget_t *widget, kbd_event_t event)
 {
-	/* no-op */
+	/* No-op */
 }
 
@@ -170,55 +314,69 @@
 {
 	grid_t *grid = (grid_t *) widget;
-
-	if ((widget->height / grid->rows) == 0) {
-		return;
-	}
-	if ((widget->width / grid->cols) == 0) {
-		return;
-	}
-
-	sysarg_t row = (event.vpos - widget->vpos) / (widget->height / grid->rows);
-	sysarg_t col = (event.hpos - widget->hpos) / (widget->width / grid->cols);
-
-	widget_t **cell = widget_at(grid, row, col);
-	if (cell && *cell) {
-		(*cell)->handle_position_event(*cell, event);
-	}
-}
-
-static void grid_add(grid_t *grid, widget_t *widget,
-    size_t row, size_t col, size_t rows, size_t cols)
-{
-	assert(row + rows <= grid->rows);
-	assert(col + cols <= grid->cols);
-
+	
+	grid_cell_t *cell = grid_coords_at(grid, event.hpos, event.vpos);
+	if ((cell) && (cell->widget))
+		cell->widget->handle_position_event(cell->widget, event);
+}
+
+static bool grid_add(struct grid *grid, widget_t *widget, size_t col,
+    size_t row, size_t cols, size_t rows)
+{
+	if ((cols == 0) || (rows == 0) || (col + cols > grid->cols) ||
+	    (row + rows > grid->rows))
+		return false;
+	
+	grid_cell_t *cell = grid_cell_at(grid, col, row);
+	if (!cell)
+		return false;
+	
+	/*
+	 * Check whether the cell is not occupied by an
+	 * extension of a different cell.
+	 */
+	if ((!cell->widget) && (cell->cols > 0) && (cell->rows > 0))
+		return false;
+	
 	widget->parent = (widget_t *) grid;
+	
 	list_append(&widget->link, &grid->widget.children);
 	widget->window = grid->widget.window;
-
-	for (size_t r = row; r < row + rows; ++r) {
-		for (size_t c = col; c < col + cols; ++c) {
-			widget_t **cell = widget_at(grid, r, c);
-			if (cell) {
-				*cell = widget;
+	
+	/* Mark cells in layout */
+	for (size_t r = row; r < row + rows; r++) {
+		for (size_t c = col; c < col + cols; c++) {
+			if ((r == row) && (c == col)) {
+				cell->widget = widget;
+				cell->cols = cols;
+				cell->rows = rows;
+			} else {
+				grid_cell_t *extension = grid_cell_at(grid, c, r);
+				if (extension) {
+					extension->widget = NULL;
+					extension->cols = 1;
+					extension->rows = 1;
+				}
 			}
 		}
 	}
-}
-
-bool init_grid(grid_t *grid,
-    widget_t *parent, size_t rows, size_t cols, pixel_t background)
-{
-	assert(rows > 0);
-	assert(cols > 0);
-
-	widget_t **layout = (widget_t **) malloc(rows * cols * sizeof(widget_t *));
-	if (!layout) {
+	
+	return true;
+}
+
+bool init_grid(grid_t *grid, widget_t *parent, size_t cols, size_t rows,
+    pixel_t background)
+{
+	if ((cols == 0) || (rows == 0))
 		return false;
-	}
-	memset(layout, 0, rows * cols * sizeof(widget_t *));
-
+	
+	grid->layout =
+	    (grid_cell_t *) calloc(cols * rows, sizeof(grid_cell_t));
+	if (!grid->layout)
+		return false;
+	
+	memset(grid->layout, 0, cols * rows * sizeof(grid_cell_t));
+	
 	widget_init(&grid->widget, parent);
-
+	
 	grid->widget.destroy = grid_destroy;
 	grid->widget.reconfigure = grid_reconfigure;
@@ -227,27 +385,24 @@
 	grid->widget.handle_keyboard_event = grid_handle_keyboard_event;
 	grid->widget.handle_position_event = grid_handle_position_event;
-
+	
 	grid->add = grid_add;
 	grid->background = background;
+	grid->cols = cols;
 	grid->rows = rows;
-	grid->cols = cols;
-	grid->layout = layout;
-
+	
 	return true;
 }
 
-grid_t *create_grid(widget_t *parent, size_t rows, size_t cols, pixel_t background)
+grid_t *create_grid(widget_t *parent, size_t cols, size_t rows, pixel_t background)
 {
 	grid_t *grid = (grid_t *) malloc(sizeof(grid_t));
-	if (!grid) {
+	if (!grid)
 		return NULL;
-	}
-
-	if (init_grid(grid, parent, rows, cols, background)) {
+	
+	if (init_grid(grid, parent, cols, rows, background))
 		return grid;
-	} else {
-		free(grid);
-		return NULL;
-	}
+	
+	free(grid);
+	return NULL;
 }
 
