This repository has no description
4.4 kB
157 lines
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5static int min3(int a, int b, int c) {
6 if (a < b) return a < c ? a : c;
7 return b < c ? b : c;
8}
9
10static int distance(const char *a, const char *b) {
11 size_t la = strlen(a), lb = strlen(b);
12 int *prev = calloc(lb + 1, sizeof(int));
13 if (!prev) exit(1);
14 for (size_t j = 0; j <= lb; j++) prev[j] = (int)j;
15 for (size_t i = 1; i <= la; i++) {
16 int corner = prev[0];
17 prev[0] = (int)i;
18 for (size_t j = 1; j <= lb; j++) {
19 int val = min3(prev[j] + 1, prev[j-1] + 1,
20 corner + (a[i-1] != b[j-1]));
21 corner = prev[j];
22 prev[j] = val;
23 }
24 }
25 int res = prev[lb];
26 free(prev);
27 return res;
28}
29
30/* Collapse whitespace and trim. Returns malloc'd string. */
31static char *normalize(const char *s) {
32 while (*s == ' ' || *s == '\t') s++;
33 size_t len = strlen(s);
34 char *out = malloc(len + 1);
35 if (!out) exit(1);
36 size_t o = 0;
37 int in_space = 0;
38 for (size_t i = 0; i < len; i++) {
39 if (s[i] == ' ' || s[i] == '\t') {
40 if (!in_space && o > 0) out[o++] = ' ';
41 in_space = 1;
42 } else {
43 out[o++] = s[i];
44 in_space = 0;
45 }
46 }
47 if (o > 0 && out[o-1] == ' ') o--;
48 out[o] = '\0';
49 return out;
50}
51
52static int fuzzy_match(const char *a, const char *b, double threshold) {
53 int dist = distance(a, b);
54 size_t la = strlen(a), lb = strlen(b);
55 size_t m = la > lb ? la : lb;
56 if (m == 0) return 1;
57 return (double)dist / (double)m <= threshold;
58}
59
60/* Dynamic line array */
61struct lines { char **l; size_t n, cap; };
62
63static void lines_init(struct lines *v) {
64 v->n = 0; v->cap = 64;
65 v->l = malloc(v->cap * sizeof(char *));
66 if (!v->l) exit(1);
67}
68
69static void lines_push(struct lines *v, char *s) {
70 if (v->n == v->cap) {
71 v->cap *= 2;
72 v->l = realloc(v->l, v->cap * sizeof(char *));
73 if (!v->l) exit(1);
74 }
75 v->l[v->n++] = s;
76}
77
78static void read_lines(const char *path, struct lines *v) {
79 FILE *f = fopen(path, "r");
80 if (!f) return;
81 char *line = NULL;
82 size_t cap = 0;
83 ssize_t len;
84 while ((len = getline(&line, &cap, f)) != -1) {
85 if (len > 0 && line[len-1] == '\n') line[len-1] = '\0';
86 lines_push(v, strdup(line));
87 }
88 free(line);
89 fclose(f);
90}
91
92int main(int argc, char **argv) {
93 if (argc == 3) {
94 printf("%d\n", distance(argv[1], argv[2]));
95 return 0;
96 }
97 if (argc == 5 && strcmp(argv[1], "-t") == 0) {
98 double t = atof(argv[2]);
99 return fuzzy_match(argv[3], argv[4], t) ? 0 : 1;
100 }
101 if (argc == 5 && strcmp(argv[1], "merge") == 0) {
102 double threshold = atof(argv[4]);
103
104 struct lines target, managed, known;
105 lines_init(&target);
106 lines_init(&managed);
107 lines_init(&known);
108
109 read_lines(argv[3], &target);
110 read_lines(argv[2], &managed);
111
112 /* Build normalized index of target lines */
113 for (size_t i = 0; i < target.n; i++) {
114 char *n = normalize(target.l[i]);
115 if (n[0]) lines_push(&known, n);
116 else free(n);
117 }
118
119 /* Find managed lines missing from target */
120 struct lines missing;
121 lines_init(&missing);
122
123 for (size_t i = 0; i < managed.n; i++) {
124 char *n = normalize(managed.l[i]);
125 if (!n[0]) { free(n); continue; }
126 int found = 0;
127 for (size_t j = 0; j < known.n; j++) {
128 if (fuzzy_match(n, known.l[j], threshold)) {
129 found = 1;
130 break;
131 }
132 }
133 if (!found) {
134 lines_push(&missing, managed.l[i]);
135 lines_push(&known, n);
136 } else {
137 free(n);
138 }
139 }
140
141 if (missing.n == 0) return 0;
142
143 FILE *f = fopen(argv[3], "a");
144 if (!f) { perror(argv[3]); return 1; }
145 fprintf(f, "\n");
146 for (size_t i = 0; i < missing.n; i++)
147 fprintf(f, "%s\n", missing.l[i]);
148 fclose(f);
149 return 0;
150 }
151
152 fprintf(stderr,
153 "usage: levenshtein-merge <a> <b>\n"
154 " levenshtein-merge -t <threshold> <a> <b>\n"
155 " levenshtein-merge merge <managed> <target> <threshold>\n");
156 return 2;
157}