Show More
@@ -103,14 +103,14 b' static int equatelines(struct line *a, i' | |||||
103 |
|
103 | |||
104 | /* clear the hash table */ |
|
104 | /* clear the hash table */ | |
105 | for (i = 0; i <= buckets; i++) { |
|
105 | for (i = 0; i <= buckets; i++) { | |
106 |
h[i].pos = |
|
106 | h[i].pos = -1; | |
107 | h[i].len = 0; |
|
107 | h[i].len = 0; | |
108 | } |
|
108 | } | |
109 |
|
109 | |||
110 | /* add lines to the hash table chains */ |
|
110 | /* add lines to the hash table chains */ | |
111 |
for (i = |
|
111 | for (i = 0; i < bn; i++) { | |
112 | /* find the equivalence class */ |
|
112 | /* find the equivalence class */ | |
113 |
for (j = b[i].hash & buckets; h[j].pos != |
|
113 | for (j = b[i].hash & buckets; h[j].pos != -1; | |
114 | j = (j + 1) & buckets) |
|
114 | j = (j + 1) & buckets) | |
115 | if (!cmp(b + i, b + h[j].pos)) |
|
115 | if (!cmp(b + i, b + h[j].pos)) | |
116 | break; |
|
116 | break; | |
@@ -128,7 +128,7 b' static int equatelines(struct line *a, i' | |||||
128 | /* match items in a to their equivalence class in b */ |
|
128 | /* match items in a to their equivalence class in b */ | |
129 | for (i = 0; i < an; i++) { |
|
129 | for (i = 0; i < an; i++) { | |
130 | /* find the equivalence class */ |
|
130 | /* find the equivalence class */ | |
131 |
for (j = a[i].hash & buckets; h[j].pos != |
|
131 | for (j = a[i].hash & buckets; h[j].pos != -1; | |
132 | j = (j + 1) & buckets) |
|
132 | j = (j + 1) & buckets) | |
133 | if (!cmp(a + i, b + h[j].pos)) |
|
133 | if (!cmp(a + i, b + h[j].pos)) | |
134 | break; |
|
134 | break; | |
@@ -137,7 +137,7 b' static int equatelines(struct line *a, i' | |||||
137 | if (h[j].len <= t) |
|
137 | if (h[j].len <= t) | |
138 | a[i].n = h[j].pos; /* point to head of match list */ |
|
138 | a[i].n = h[j].pos; /* point to head of match list */ | |
139 | else |
|
139 | else | |
140 |
a[i].n = |
|
140 | a[i].n = -1; /* too popular */ | |
141 | } |
|
141 | } | |
142 |
|
142 | |||
143 | /* discard hash tables */ |
|
143 | /* discard hash tables */ | |
@@ -151,12 +151,12 b' static int longest_match(struct line *a,' | |||||
151 | int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k; |
|
151 | int mi = a1, mj = b1, mk = 0, mb = 0, i, j, k; | |
152 |
|
152 | |||
153 | for (i = a1; i < a2; i++) { |
|
153 | for (i = a1; i < a2; i++) { | |
154 |
/* skip |
|
154 | /* skip all lines in b after the current block */ | |
155 |
for (j = a[i].n; j |
|
155 | for (j = a[i].n; j >= b2; j = b[j].n) | |
156 | ; |
|
156 | ; | |
157 |
|
157 | |||
158 | /* loop through all lines match a[i] in b */ |
|
158 | /* loop through all lines match a[i] in b */ | |
159 |
for (; j |
|
159 | for (; j >= b1; j = b[j].n) { | |
160 | /* does this extend an earlier match? */ |
|
160 | /* does this extend an earlier match? */ | |
161 | if (i > a1 && j > b1 && pos[j - 1].pos == i - 1) |
|
161 | if (i > a1 && j > b1 && pos[j - 1].pos == i - 1) | |
162 | k = pos[j - 1].len + 1; |
|
162 | k = pos[j - 1].len + 1; | |
@@ -166,7 +166,7 b' static int longest_match(struct line *a,' | |||||
166 | pos[j].len = k; |
|
166 | pos[j].len = k; | |
167 |
|
167 | |||
168 | /* best match so far? */ |
|
168 | /* best match so far? */ | |
169 | if (k > mk) { |
|
169 | if (k > mk || (k == mk && i <= mi)) { | |
170 | mi = i; |
|
170 | mi = i; | |
171 | mj = j; |
|
171 | mj = j; | |
172 | mk = k; |
|
172 | mk = k; |
@@ -52,6 +52,9 b' def showdiff(a, b):' | |||||
52 | pos += l |
|
52 | pos += l | |
53 | showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n") |
|
53 | showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\nx\n\nz\n") | |
54 | showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n") |
|
54 | showdiff("x\n\nx\n\nx\n\nx\n\nz\n", "x\n\nx\n\ny\n\nx\n\ny\n\nx\n\nz\n") | |
|
55 | # we should pick up abbbc. rather than bc.de as the longest match | |||
|
56 | showdiff("a\nb\nb\nb\nc\n.\nd\ne\n.\nf\n", | |||
|
57 | "a\nb\nb\na\nb\nb\nb\nc\n.\nb\nc\n.\nd\ne\nf\n") | |||
55 |
|
58 | |||
56 | print("done") |
|
59 | print("done") | |
57 |
|
60 |
General Comments 0
You need to be logged in to leave comments.
Login now