[PATCH 5/9] display_columns: add COL_DENSE to do unequal column layout

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 column.c          |   80 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 column.h          |    1 +
 t/t9002-column.sh |   22 ++++++++++++++
 3 files changed, 103 insertions(+), 0 deletions(-)

diff --git a/column.c b/column.c
index 15f74a5..69d42f8 100644
--- a/column.c
+++ b/column.c
@@ -18,6 +18,7 @@ struct column_data {
 
 	int rows, cols;
 	int *len;			/* cell length */
+	int *width;			/* index to the longest row in column */
 };
 
 /* return length of 's' in letters, ANSI escapes stripped */
@@ -62,6 +63,69 @@ static void layout(struct column_data *data, int *width)
 	data->rows = DIV_ROUND_UP(data->list->nr, data->cols);
 }
 
+static void compute_column_width(struct column_data *data)
+{
+	int i, x, y;
+	for (x = 0; x < data->cols; x++) {
+		data->width[x] = XY2LINEAR(data, x, 0);
+		for (y = 0; y < data->rows; y++) {
+			i = XY2LINEAR(data, x, y);
+			if (i >= data->list->nr)
+				continue;
+			if (data->len[data->width[x]] < data->len[i])
+				data->width[x] = i;
+		}
+	}
+}
+
+/*
+ * Shrink all columns by shortening them one row each time (and adding
+ * more columns along the way). Hopefully the longest cell will be
+ * moved to the next column, column is shrunk so we have more space
+ * for new columns. The process ends when the whole thing no longer
+ * fits in data->total_width.
+ */
+static void shrink_columns(struct column_data *data)
+{
+	int x, y, total_width, cols, rows;
+
+	data->width = xrealloc(data->width,
+			       sizeof(*data->width) * data->cols);
+	for (x = 0; x < data->cols; x++) {
+		data->width[x] = 0;
+		for (y = 0; y < data->rows; y++) {
+			int len1 = data->len[data->width[x]];
+			int len2 = data->len[XY2LINEAR(data, x, y)];
+			if (len1 < len2)
+				data->width[x] = y;
+		}
+	}
+
+	while (data->rows > 1) {
+		rows = data->rows;
+		cols = data->cols;
+
+		data->rows--;
+		data->cols = DIV_ROUND_UP(data->list->nr, data->rows);
+		if (data->cols != cols)
+			data->width = xrealloc(data->width, sizeof(*data->width) * data->cols);
+
+		compute_column_width(data);
+
+		total_width = strlen(data->indent);
+		for (x = 0; x < data->cols; x++) {
+			total_width += data->len[data->width[x]];
+			total_width += data->padding;
+		}
+		if (total_width > data->total_width) {
+			data->rows = rows;
+			data->cols = cols;
+			compute_column_width(data);
+			break;
+		}
+	}
+}
+
 struct string_list_item *add_to_columns(struct string_list *list, int mode,
 					const char *string)
 {
@@ -89,7 +153,18 @@ static int display_cell(struct column_data *data, int initial_width,
 	i = XY2LINEAR(data, x, y);
 	if (i >= data->list->nr)
 		return -1;
+
 	len = data->len[i];
+	if (data->width && data->len[data->width[x]] < initial_width) {
+		/*
+		 * empty_cell has initial_width chars, if real column
+		 * is narrower, increase len a bit so we fill less
+		 * space.
+		 */
+		len += initial_width - data->len[data->width[x]];
+		len -= data->padding;
+	}
+
 	if (MODE(data->mode) == COL_MODE_COLUMN)
 		newline = i + data->rows >= data->list->nr;
 	else
@@ -124,6 +199,9 @@ static void display_table(const struct string_list *list,
 
 	layout(&data, &initial_width);
 
+	if (mode & COL_DENSE)
+		shrink_columns(&data);
+
 	empty_cell = xmalloc(initial_width + 1);
 	memset(empty_cell, ' ', initial_width);
 	empty_cell[initial_width] = '\0';
@@ -134,6 +212,7 @@ static void display_table(const struct string_list *list,
 	}
 
 	free(data.len);
+	free(data.width);
 	free(empty_cell);
 }
 
@@ -221,6 +300,7 @@ static int parse_option(const char *arg, int len,
 		{ ENABLE, "auto",   -1 },
 		{ MODE,   "column", COL_MODE_COLUMN },
 		{ MODE,   "row",    COL_MODE_ROW },
+		{ OPTION, "dense",  COL_DENSE },
 	};
 	int i, set, name_len;
 
diff --git a/column.h b/column.h
index 4fb1004..48c6345 100644
--- a/column.h
+++ b/column.h
@@ -7,6 +7,7 @@
 #define COL_ENABLED      (1 << 4)
 #define COL_ENABLED_SET  (1 << 5)  /* Has COL_ENABLED been set? */
 #define COL_ANSI         (1 << 6)  /* Remove ANSI escapes from string length */
+#define COL_DENSE        (1 << 7)  /* Shrink columns when possible, making space for more columns */
 
 extern int term_columns(void);
 extern struct string_list_item *add_to_columns(struct string_list *list, int mode, const char *string);
diff --git a/t/t9002-column.sh b/t/t9002-column.sh
index f801190..07161a9 100755
--- a/t/t9002-column.sh
+++ b/t/t9002-column.sh
@@ -71,6 +71,17 @@ EOF
 	test_cmp expected actual
 '
 
+test_expect_success '20 columns, dense' '
+	cat >expected <<\EOF &&
+one   five  nine
+two   six   ten
+three seven eleven
+four  eight
+EOF
+	test-column --mode=column,dense < lista > actual &&
+	test_cmp expected actual
+'
+
 test_expect_success '20 columns, padding 2' '
 	cat >expected <<\EOF &&
 one     seven
@@ -110,4 +121,15 @@ EOF
 	test_cmp expected actual
 '
 
+test_expect_success '20 columns, row first, dense' '
+	cat >expected <<\EOF &&
+one   two    three
+four  five   six
+seven eight  nine
+ten   eleven
+EOF
+	test-column --mode=row,dense <lista >actual &&
+	test_cmp expected actual
+'
+
 test_done
-- 
1.7.4.74.g639db