[easytag] Add tests for DLM function

[David King <davidk src gnome org>]

commit 4fcfe2136e8c36d3ca7f757bf453c07cf7742ebc
Author: David King <amigadave amigadave com>
Date:   Fri Nov 21 19:33:47 2014 +0000

    Add tests for DLM function
    
    Additionally, improve the metric reporting to report 0 as a minimum
    result fot the "similarity metric".

 Makefile.am      |   17 ++++++++++
 src/dlm.c        |   18 +++++++---
 src/dlm.h        |   14 ++++++--
 tests/test-dlm.c |   90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 129 insertions(+), 10 deletions(-)
---
diff --git a/Makefile.am b/Makefile.am
index 57fafa9..880b0bd 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -408,9 +408,26 @@ test-report perf-report full-report: $(check_PROGRAMS)
        }
 
 check_PROGRAMS = \
+       tests/test-dlm \
        tests/test-misc \
        tests/test-scan
 
+tests_test_dlm_CPPFLAGS = \
+       -I$(top_srcdir)/src \
+       -I$(top_builddir) \
+       $(DEPRECATED_CPPFLAGS)
+
+tests_test_dlm_CFLAGS = \
+       $(WARN_CFLAGS) \
+       $(EASYTAG_CFLAGS)
+
+tests_test_dlm_SOURCES = \
+       tests/test-dlm.c \
+       src/dlm.c
+
+tests_test_dlm_LDADD = \
+       $(EASYTAG_LIBS)
+
 tests_test_misc_CPPFLAGS = \
        -I$(top_srcdir)/src \
        -I$(top_srcdir)/src/tags \
diff --git a/src/dlm.c b/src/dlm.c
index bb4ffff..3c15cba 100644
--- a/src/dlm.c
+++ b/src/dlm.c
@@ -16,7 +16,6 @@
  * Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  */
 
-#include <glib.h>
 #include <string.h>
 
 #include "dlm.h"
@@ -27,10 +26,11 @@ static int dlm_minimum (int a, int b, int c, int d);
 /*
  * Compute the Damerau-Levenshtein Distance between utf-8 strings ds and dt.
  */
-int dlm (const gchar *ds, const gchar *dt)
+gint
+dlm (const gchar *ds, const gchar *dt)
 {
-    int i, j, n, m, metric;
-    int *d;
+    gsize n;
+    gsize m;
 
     /* Casefold for better matching of the strings. */
     gchar *s = g_utf8_casefold(ds, -1);
@@ -41,10 +41,15 @@ int dlm (const gchar *ds, const gchar *dt)
 
     if (n && m)
     {
+        gint *d;
+        gsize i;
+        gsize j;
+        gint metric;
+
         n++;
         m++;
 
-        d = (int *)g_malloc0(sizeof(int) * m * n);
+        d = (gint *)g_malloc0 (sizeof (gint) * m * n);
 
         for (i = 0; i < m; i++)
             d[i * n] = i;
@@ -69,7 +74,8 @@ int dlm (const gchar *ds, const gchar *dt)
         g_free(d);
 
         /* Count a "similarity value" */
-        metric = 1000 - (1000 * (metric * 2)) / (m + n);
+        /* Subtract the extra byte added to each string length earlier. */
+        metric = 1000 - (1000 * (metric * 2)) / (m + n - 2);
 
         g_free(t);
         g_free(s);
diff --git a/src/dlm.h b/src/dlm.h
index bd9292f..1c9e905 100644
--- a/src/dlm.h
+++ b/src/dlm.h
@@ -16,9 +16,15 @@
  * Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  */
 
-#ifndef __DLM_H__
-#define __DLM_H__
+#ifndef ET_DLM_H_
+#define ET_DLM_H_
 
-int dlm (const gchar *s, const gchar *t);
+#include <glib.h>
 
-#endif /* __DLM_H__ */
+G_BEGIN_DECLS
+
+gint dlm (const gchar *s, const gchar *t);
+
+G_END_DECLS
+
+#endif /* ET_DLM_H_ */
diff --git a/tests/test-dlm.c b/tests/test-dlm.c
new file mode 100644
index 0000000..29f214d
--- /dev/null
+++ b/tests/test-dlm.c
@@ -0,0 +1,90 @@
+/* EasyTAG - tag editor for audio files
+ * Copyright (C) 2014 David King <amigadave amigadave com>
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 51
+ * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "dlm.h"
+
+static void
+dlm_dlm (void)
+{
+    gsize i;
+
+    static const struct
+    {
+        const gchar *str1;
+        const gchar *str2;
+        const gint metric;
+    } strings[] = 
+    {
+        { "foo", "foo", 1000 },
+        { "foo", "bar", 0 },
+        { "bar", "baz", 667 },
+        { "bar", "bra", 667 },
+        { "bar", "ba", 600 },
+        { "ba", "bar", 600 },
+        { "foobarbaz", "foobarbaz", 1000 },
+        { "foobarbaz", "foobazbar", 778 },
+        { "foobarbaz", "zabraboof", 223 },
+        { "foobarbaz", "iiiiiiiii", 0 },
+        { "1234567890", "abcdefghij", 0 },
+        { "", "", -1 },
+        { "foo", "", -1 },
+        { "", "foo", -1 },
+    };
+
+    for (i = 0; i < G_N_ELEMENTS (strings); i++)
+    {
+        gint metric;
+
+        metric = dlm (strings[i].str1, strings[i].str2);
+        g_assert_cmpint (strings[i].metric, ==, metric);
+    }
+}
+
+static void
+dlm_perf_dlm (void)
+{
+    gsize i;
+    const gsize PERF_ITERATIONS = 500000;
+    gdouble time;
+
+    g_test_timer_start ();
+
+    for (i = 0; i < PERF_ITERATIONS; i++)
+    {
+        g_assert_cmpint (dlm ("foobarbaz", "zabraboof"), ==, 223);
+    }
+
+    time = g_test_timer_elapsed ();
+
+    g_test_minimized_result (time, "%6.1f seconds", time);
+}
+
+int
+main (int argc, char** argv)
+{
+    g_test_init (&argc, &argv, NULL);
+
+    g_test_add_func ("/dlm/dlm", dlm_dlm);
+
+    if (g_test_perf ())
+    {
+        g_test_add_func ("/dlm/perf/dlm", dlm_perf_dlm);
+    }
+
+    return g_test_run ();
+}