From d26df6ba7fcc562bcc4114a892e88d7f41533682 Mon Sep 17 00:00:00 2001
From: Love Hornquist Astrand <lha@h5l.org>
Date: Tue, 22 Nov 2011 12:18:37 -0800
Subject: [PATCH] export sl_did_you_mean that uses
 OptimalStringAlignmentDistance to propose an alternative

---
 lib/sl/sl.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/sl/sl.h |  2 ++
 2 files changed, 86 insertions(+)

diff --git a/lib/sl/sl.c b/lib/sl/sl.c
index 7888952b1..798979a10 100644
--- a/lib/sl/sl.c
+++ b/lib/sl/sl.c
@@ -396,3 +396,87 @@ sl_slc_help (SL_cmd *cmds, int argc, char **argv)
 	}
     }
 }
+
+/* OptimalStringAlignmentDistance */
+
+static int
+osad(const char *s1, const char *s2)
+{
+    size_t l1 = strlen(s1), l2 = strlen(s2), i, j;
+    int *row0, *row1, *row2, *tmp, cost;
+
+    row0 = calloc(sizeof(int), l2 + 1);
+    row1 = calloc(sizeof(int), l2 + 1);
+    row2 = calloc(sizeof(int), l2 + 1);
+
+    for (j = 0; j < l2 + 1; j++)
+        row1[j] = j;
+
+    for (i = 0; i < l1; i++) {
+
+        row2[0] = i + 1;
+
+        for (j = 0; j < l2; j++) {
+
+	    row2[j + 1] = row1[j] + (s1[i] != s2[j]); /* substitute */
+	    
+	    if (row2[j + 1] > row1[j + 1] + 1) /* delete */
+		row2[j + 1] = row1[j + 1] + 1;
+	    if (row2[j + 1] > row2[j] + 1) /* insert */
+		row2[j + 1] = row2[j] + 1;
+	    if (j > 0 && i > 0 && s1[i - 1] != s2[j - 1] && s1[i - 1] == s2[j] && s1[i] == s2[j - 1] && row2[j + 1] < row0[j - 1]) /* transposition */
+	        row2[j + 1] = row0[j - 1] + 1;
+	}
+
+	tmp = row0;
+	row0 = row1;
+	row1 = row2;
+	row2 = tmp;
+    }
+
+    cost = row1[l2];
+
+    free(row0);
+    free(row1);
+    free(row2);
+
+    return cost;
+}
+
+void
+sl_did_you_mean(SL_cmd *cmds, const char *match)
+{
+    int *metrics, best_match = INT_MAX, print = 0;
+    SL_cmd *c;
+    size_t n;
+
+    for (n = 0, c = cmds; c->name; c++, n++)
+        ;
+    metrics = calloc(n, sizeof(metrics[0]));
+    if (metrics == NULL)
+        return;
+
+    for (n = 0; cmds[n].name; n++) {
+        metrics[n] = osad(match, cmds[n].name);
+	if (metrics[n] < best_match)
+	    best_match = metrics[n];
+    }
+    if (best_match == INT_MAX) {
+        free(metrics);
+        fprintf(stderr, "What kind of command is %s", match);
+        return;
+    }
+
+    fprintf(stderr, "%s is not a known command, did you mean:", match);
+    for (n = 0; cmds[n].name; n++) {
+      if (metrics[n] == best_match) {
+	  fprintf(stderr, "%s %s", print ? "," : "", cmds[n].name);
+	  print = 1;
+      }
+    }
+    fprintf(stderr, ".\n");
+
+    free(metrics);
+
+    return;
+}
diff --git a/lib/sl/sl.h b/lib/sl/sl.h
index 09225b0a5..affdb6e1a 100644
--- a/lib/sl/sl.h
+++ b/lib/sl/sl.h
@@ -61,6 +61,8 @@ int sl_make_argv(char*, int*, char***);
 void sl_apropos (SL_cmd *cmd, const char *topic);
 SL_cmd *sl_match (SL_cmd *cmds, char *cmd, int exactp);
 void sl_slc_help (SL_cmd *cmds, int argc, char **argv);
+void sl_did_you_mean(SL_cmd *cmds, const char *match);
+
 
 #ifdef __cplusplus
 }
-- 
2.11.4.GIT