From 5edec9a231541eaf06a7f87a92610b078a09dab9 Mon Sep 17 00:00:00 2001
From: John Hawthorn <john.hawthorn@gmail.com>
Date: Sat, 26 Jul 2014 02:27:31 -0700
Subject: Highlight matched characters

---
 fzy.c   | 26 +++++++++++++++++++++++---
 match.c | 37 ++++++++++++++++++++++++++++++++++---
 2 files changed, 57 insertions(+), 6 deletions(-)

diff --git a/fzy.c b/fzy.c
index e3b5a28..ac3d938 100644
--- a/fzy.c
+++ b/fzy.c
@@ -10,6 +10,7 @@
 
 /* from match.c */
 double match(const char *needle, const char *haystack);
+double match_positions(const char *needle, const char *haystack, size_t *positions);
 
 #define INITIAL_CAPACITY 1
 int choices_capacity = 0;
@@ -136,6 +137,27 @@ void clear(){
 	fprintf(ttyout, "%c%c0G", 0x1b, '[');
 }
 
+void draw_match(const char *choice, int selected){
+	int n = strlen(search);
+	size_t positions[n + 1];
+	for(int i = 0; i < n + 1; i++)
+		positions[i] = -1;
+
+	match_positions(search, choice, &positions[0]);
+
+	for(size_t i = 0, p = 0; choice[i] != '\0'; i++){
+		if(positions[p] == i){
+			fprintf(ttyout, "%c%c33m", 0x1b, '[');
+			p++;
+		}else{
+			fprintf(ttyout, "%c%c39;49m", 0x1b, '[');
+		}
+		fprintf(ttyout, "%c", choice[i]);
+	}
+	fprintf(ttyout, "\n");
+	fprintf(ttyout, "%c%c0m", 0x1b, '[');
+}
+
 void draw(){
 	int line = 0;
 	const char *prompt = "> ";
@@ -144,9 +166,7 @@ void draw(){
 	for(size_t i = 0; line < 10 && i < choices_available; i++){
 		if(i == current_selection)
 			fprintf(ttyout, "%c%c7m", 0x1b, '[');
-		else
-			fprintf(ttyout, "%c%c0m", 0x1b, '[');
-		fprintf(ttyout, "%s\n", choices[choices_sorted[i]]);
+		draw_match(choices[choices_sorted[i]], i == current_selection);
 		line++;
 	}
 	fprintf(ttyout, "%c%c%iA", 0x1b, '[', line + 1);
diff --git a/match.c b/match.c
index 7a6166e..3bf0e89 100644
--- a/match.c
+++ b/match.c
@@ -30,7 +30,7 @@ void mat_print(int *mat, int n, int m){
 #define max(a, b) (((a) > (b)) ? (a) : (b))
 typedef int score_t;
 
-double calculate_score(const char *needle, const char *haystack){
+double calculate_score(const char *needle, const char *haystack, size_t *positions){
 	if(!*haystack || !*needle)
 		return SCORE_MIN;
 
@@ -85,17 +85,48 @@ double calculate_score(const char *needle, const char *haystack){
 		}
 	}
 
+	/* backtrace to find the positions of optimal matching */
+	if(positions){
+		for(int i = n-1, j = m-1; i >= 0; i--){
+			int last = M[i][j];
+			for(; j >= 0 && M[i][j] == last; j--){
+				/*
+				 * There may be multiple paths which result in
+				 * the optimal weight.
+				 *
+				 * Since we don't exit the loop on the first
+				 * match, positions[i] may be assigned to
+				 * multiple times. Since we are decrementing i
+				 * and j, this favours the optimal path
+				 * occurring earlier in the string.
+				 */
+				if(tolower(needle[i]) == tolower(haystack[j])){
+					positions[i] = j;
+				}
+			}
+		}
+	}
+
 	return (float)(M[n-1][m-1]) / (float)(n * 2 + 1);
 }
 
-double match(const char *needle, const char *haystack){
+double match_positions(const char *needle, const char *haystack, size_t *positions){
 	if(!*needle){
 		return 1.0;
 	}else if(!is_subset(needle, haystack)){
 		return SCORE_MIN;
 	}else if(!strcasecmp(needle, haystack)){
+		if(positions){
+			int n = strlen(needle);
+			for(int i = 0; i < n; i++)
+				positions[i] = i;
+		}
 		return 1.0;
 	}else{
-		return calculate_score(needle, haystack);
+		return calculate_score(needle, haystack, positions);
 	}
 }
+
+double match(const char *needle, const char *haystack){
+	return match_positions(needle, haystack, NULL);
+}
-- 
cgit v1.2.3