From aab9ae5e8c60c10daae078e3944d808cb74bb448 Mon Sep 17 00:00:00 2001
From: Jonas Fonseca <fonseca@diku.dk>
Date: Sat, 21 Feb 2009 02:33:47 +0100
Subject: [PATCH] Add support for sorting tree entries by name, date or author

---
 NEWS  |  3 +++
 tig.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 87 insertions(+), 3 deletions(-)

diff --git a/NEWS b/NEWS
index 086bb79..15d898b 100644
--- a/NEWS
+++ b/NEWS
@@ -8,6 +8,9 @@ Improvements:
 
  - Add branch view for choosing which branch to display in the main
    view. Bound to 'H' by default.
+ - Tree view: sort entries by name, date or author. Toggling is bound to
+   'i' by default, with 'I' controlling whether or not to sort in
+   ascending order.
 
 Bug fixes:
 
diff --git a/tig.c b/tig.c
index 13d1c45..a4eae7d 100644
--- a/tig.c
+++ b/tig.c
@@ -831,6 +831,8 @@ run_io_load(const char **argv, const char *separators,
 	REQ_(TOGGLE_AUTHOR,	"Toggle author display"), \
 	REQ_(TOGGLE_REV_GRAPH,	"Toggle revision graph visualization"), \
 	REQ_(TOGGLE_REFS,	"Toggle reference display (tags/branches)"), \
+	REQ_(TOGGLE_SORT_ORDER,	"Toggle ascending/descending sort order"), \
+	REQ_(TOGGLE_SORT_FIELD,	"Toggle field to sort by"), \
 	\
 	REQ_GROUP("Misc") \
 	REQ_(PROMPT,		"Bring up the prompt"), \
@@ -1144,6 +1146,8 @@ static const struct keybinding default_keybindings[] = {
 	{ 'A',		REQ_TOGGLE_AUTHOR },
 	{ 'g',		REQ_TOGGLE_REV_GRAPH },
 	{ 'F',		REQ_TOGGLE_REFS },
+	{ 'I',		REQ_TOGGLE_SORT_ORDER },
+	{ 'i',		REQ_TOGGLE_SORT_FIELD },
 	{ ':',		REQ_PROMPT },
 	{ 'u',		REQ_STATUS_UPDATE },
 	{ '!',		REQ_STATUS_REVERT },
@@ -3283,6 +3287,11 @@ view_driver(struct view *view, enum request request)
 		toggle_view_option(&opt_show_refs, "reference display");
 		break;
 
+	case REQ_TOGGLE_SORT_FIELD:
+	case REQ_TOGGLE_SORT_ORDER:
+		report("Sorting is not yet supported for the %s view", view->name);
+		break;
+
 	case REQ_SEARCH:
 	case REQ_SEARCH_BACK:
 		search_view(view, request);
@@ -3345,6 +3354,42 @@ view_driver(struct view *view, enum request request)
  * View backend utilities
  */
 
+enum sort_field {
+	ORDERBY_NAME,
+	ORDERBY_DATE,
+	ORDERBY_AUTHOR,
+};
+
+struct sort_state {
+	const enum sort_field *fields;
+	size_t size, current;
+	bool reverse;
+};
+
+#define SORT_STATE(fields) { fields, ARRAY_SIZE(fields), 0 }
+#define get_sort_field(state) ((state).fields[(state).current])
+#define sort_order(state, result) ((state).reverse ? -(result) : (result))
+
+static void
+sort_view(struct view *view, enum request request, struct sort_state *state,
+	  int (*compare)(const void *, const void *))
+{
+	switch (request) {
+	case REQ_TOGGLE_SORT_FIELD:
+		state->current = (state->current + 1) % state->size;
+		break;
+
+	case REQ_TOGGLE_SORT_ORDER:
+		state->reverse = !state->reverse;
+		break;
+	default:
+		die("Not a sort request");
+	}
+
+	qsort(view->line, view->lines, sizeof(*view->line), compare);
+	redraw_view(view);
+}
+
 DEFINE_ALLOCATOR(realloc_authors, const char *, 256)
 
 /* Small author cache to reduce memory consumption. It uses binary
@@ -3843,20 +3888,51 @@ struct tree_entry {
 };
 
 static const char *
-tree_path(struct line *line)
+tree_path(const struct line *line)
 {
 	return ((struct tree_entry *) line->data)->name;
 }
 
-
 static int
-tree_compare_entry(struct line *line1, struct line *line2)
+tree_compare_entry(const struct line *line1, const struct line *line2)
 {
 	if (line1->type != line2->type)
 		return line1->type == LINE_TREE_DIR ? -1 : 1;
 	return strcmp(tree_path(line1), tree_path(line2));
 }
 
+static const enum sort_field tree_sort_fields[] = {
+	ORDERBY_NAME, ORDERBY_DATE, ORDERBY_AUTHOR
+};
+static struct sort_state tree_sort_state = SORT_STATE(tree_sort_fields);
+
+static int
+tree_compare(const void *l1, const void *l2)
+{
+	const struct line *line1 = (const struct line *) l1;
+	const struct line *line2 = (const struct line *) l2;
+	const struct tree_entry *entry1 = ((const struct line *) l1)->data;
+	const struct tree_entry *entry2 = ((const struct line *) l2)->data;
+
+	if (line1->type == LINE_TREE_HEAD)
+		return -1;
+	if (line2->type == LINE_TREE_HEAD)
+		return 1;
+
+	switch (get_sort_field(tree_sort_state)) {
+	case ORDERBY_DATE:
+		return sort_order(tree_sort_state, entry1->time - entry2->time);
+
+	case ORDERBY_AUTHOR:
+		return sort_order(tree_sort_state, strcmp(entry1->author, entry2->author));
+
+	case ORDERBY_NAME:
+	default:
+		return sort_order(tree_sort_state, tree_compare_entry(line1, line2));
+	}
+}
+
+
 static struct line *
 tree_entry(struct view *view, enum line_type type, const char *path,
 	   const char *mode, const char *id)
@@ -4080,6 +4156,11 @@ tree_request(struct view *view, enum request request, struct line *line)
 		}
 		return REQ_NONE;
 
+	case REQ_TOGGLE_SORT_FIELD:
+	case REQ_TOGGLE_SORT_ORDER:
+		sort_view(view, request, &tree_sort_state, tree_compare);
+		return REQ_NONE;
+
 	case REQ_PARENT:
 		if (!*opt_path) {
 			/* quit view if at top of tree */
-- 
2.32.0.93.g670b81a890