summaryrefslogtreecommitdiff
path: root/match/match.c
diff options
context:
space:
mode:
Diffstat (limited to 'match/match.c')
-rw-r--r--match/match.c66
1 files changed, 33 insertions, 33 deletions
diff --git a/match/match.c b/match/match.c
index 3c5ea0c..0080ee6 100644
--- a/match/match.c
+++ b/match/match.c
@@ -59,25 +59,25 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
59 /* initialization */ 59 /* initialization */
60 for(row=0; row<nrows; row++) 60 for(row=0; row<nrows; row++)
61 ix[row] = -1; 61 ix[row] = -1;
62 62
63 mdistEnd = mdist + nrows * ncols; 63 mdistEnd = mdist + nrows * ncols;
64 64
65 /* preliminary steps */ 65 /* preliminary steps */
66 if(nrows <= ncols) { 66 if(nrows <= ncols) {
67 dmin = nrows; 67 dmin = nrows;
68 68
69 for(row=0; row<nrows; row++) { 69 for(row=0; row<nrows; row++) {
70 /* find the smallest element in the row */ 70 /* find the smallest element in the row */
71 mdistTemp = mdist + row; 71 mdistTemp = mdist + row;
72 minValue = *mdistTemp; 72 minValue = *mdistTemp;
73 mdistTemp += nrows; 73 mdistTemp += nrows;
74 while(mdistTemp < mdistEnd) { 74 while(mdistTemp < mdistEnd) {
75 value = *mdistTemp; 75 value = *mdistTemp;
76 if(value < minValue) 76 if(value < minValue)
77 minValue = value; 77 minValue = value;
78 mdistTemp += nrows; 78 mdistTemp += nrows;
79 } 79 }
80 80
81 /* subtract the smallest element from each element of the row */ 81 /* subtract the smallest element from each element of the row */
82 mdistTemp = mdist + row; 82 mdistTemp = mdist + row;
83 while(mdistTemp < mdistEnd) { 83 while(mdistTemp < mdistEnd) {
@@ -85,7 +85,7 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
85 mdistTemp += nrows; 85 mdistTemp += nrows;
86 } 86 }
87 } 87 }
88 88
89 /* Steps 1 and 2a */ 89 /* Steps 1 and 2a */
90 for(row=0; row<nrows; row++) 90 for(row=0; row<nrows; row++)
91 for(col=0; col<ncols; col++) 91 for(col=0; col<ncols; col++)
@@ -97,25 +97,25 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
97 } 97 }
98 } else { 98 } else {
99 dmin = ncols; 99 dmin = ncols;
100 100
101 for(col=0; col<ncols; col++) { 101 for(col=0; col<ncols; col++) {
102 /* find the smallest element in the column */ 102 /* find the smallest element in the column */
103 mdistTemp = mdist + nrows*col; 103 mdistTemp = mdist + nrows*col;
104 columnEnd = mdistTemp + nrows; 104 columnEnd = mdistTemp + nrows;
105 105
106 minValue = *mdistTemp++; 106 minValue = *mdistTemp++;
107 while(mdistTemp < columnEnd) { 107 while(mdistTemp < columnEnd) {
108 value = *mdistTemp++; 108 value = *mdistTemp++;
109 if(value < minValue) 109 if(value < minValue)
110 minValue = value; 110 minValue = value;
111 } 111 }
112 112
113 /* subtract the smallest element from each element of the column */ 113 /* subtract the smallest element from each element of the column */
114 mdistTemp = mdist + nrows*col; 114 mdistTemp = mdist + nrows*col;
115 while(mdistTemp < columnEnd) 115 while(mdistTemp < columnEnd)
116 *mdistTemp++ -= minValue; 116 *mdistTemp++ -= minValue;
117 } 117 }
118 118
119 /* Steps 1 and 2a */ 119 /* Steps 1 and 2a */
120 for(col=0; col<ncols; col++) 120 for(col=0; col<ncols; col++)
121 for(row=0; row<nrows; row++) 121 for(row=0; row<nrows; row++)
@@ -127,8 +127,8 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
127 break; 127 break;
128 } 128 }
129 memset(crow, 0, sizeof(col_t)); 129 memset(crow, 0, sizeof(col_t));
130 } 130 }
131 131
132 /* move to step 2b */ 132 /* move to step 2b */
133 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 133 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
134} 134}
@@ -145,9 +145,9 @@ static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprim
145 SET1(ccol, col); 145 SET1(ccol, col);
146 break; 146 break;
147 } 147 }
148 } 148 }
149 } 149 }
150 150
151 /* move to step 3 */ 151 /* move to step 3 */
152 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 152 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
153} 153}
@@ -156,13 +156,13 @@ static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprim
156static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 156static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin)
157{ 157{
158 int col, ncc; 158 int col, ncc;
159 159
160 /* count covered columns */ 160 /* count covered columns */
161 ncc = 0; 161 ncc = 0;
162 for(col=0; col<ncols; col++) 162 for(col=0; col<ncols; col++)
163 if(GET1(ccol, col)) 163 if(GET1(ccol, col))
164 ncc++; 164 ncc++;
165 165
166 if(ncc == dmin) { 166 if(ncc == dmin) {
167 /* algorithm finished */ 167 /* algorithm finished */
168 buildixvector(ix, mstar, nrows, ncols); 168 buildixvector(ix, mstar, nrows, ncols);
@@ -170,7 +170,7 @@ static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprim
170 /* move to step 3 */ 170 /* move to step 3 */
171 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 171 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
172 } 172 }
173 173
174} 174}
175 175
176/********************************************************/ 176/********************************************************/
@@ -181,19 +181,19 @@ static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
181 181
182 zerosFound = 1; 182 zerosFound = 1;
183 while(zerosFound) { 183 while(zerosFound) {
184 zerosFound = 0; 184 zerosFound = 0;
185 for(col=0; col<ncols; col++) 185 for(col=0; col<ncols; col++)
186 if(!GET1(ccol,col)) 186 if(!GET1(ccol,col))
187 for(row=0; row<nrows; row++) 187 for(row=0; row<nrows; row++)
188 if((!GET1(crow, row)) && (mdist[row + nrows*col] == 0)) { 188 if((!GET1(crow, row)) && (mdist[row + nrows*col] == 0)) {
189 /* prime zero */ 189 /* prime zero */
190 SET2(mprime, row, col); 190 SET2(mprime, row, col);
191 191
192 /* find starred zero in current row */ 192 /* find starred zero in current row */
193 for(cstar=0; cstar<ncols; cstar++) 193 for(cstar=0; cstar<ncols; cstar++)
194 if(GET2(mstar, row, cstar)) 194 if(GET2(mstar, row, cstar))
195 break; 195 break;
196 196
197 if(cstar == ncols) { /* no starred zero found */ 197 if(cstar == ncols) { /* no starred zero found */
198 /* move to step 4 */ 198 /* move to step 4 */
199 step4(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin, row, col); 199 step4(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin, row, col);
@@ -206,19 +206,19 @@ static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
206 } 206 }
207 } 207 }
208 } 208 }
209 209
210 /* move to step 5 */ 210 /* move to step 5 */
211 step5(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 211 step5(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
212} 212}
213 213
214/********************************************************/ 214/********************************************************/
215static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin, int row, int col) 215static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin, int row, int col)
216{ 216{
217 int n, rstar, cstar, primeRow, primeCol; 217 int n, rstar, cstar, primeRow, primeCol;
218 218
219 /* generate temporary copy of mstar */ 219 /* generate temporary copy of mstar */
220 memcpy(nmstar, mstar, sizeof(mat_t)); 220 memcpy(nmstar, mstar, sizeof(mat_t));
221 221
222 /* star current zero */ 222 /* star current zero */
223 SET2(nmstar, row, col); 223 SET2(nmstar, row, col);
224 224
@@ -231,29 +231,29 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
231 while(rstar<nrows) { 231 while(rstar<nrows) {
232 /* unstar the starred zero */ 232 /* unstar the starred zero */
233 CLEAR2(nmstar, rstar, cstar); 233 CLEAR2(nmstar, rstar, cstar);
234 234
235 /* find primed zero in current row */ 235 /* find primed zero in current row */
236 primeRow = rstar; 236 primeRow = rstar;
237 for(primeCol=0; primeCol<ncols; primeCol++) 237 for(primeCol=0; primeCol<ncols; primeCol++)
238 if(GET2(mprime, primeRow, primeCol)) 238 if(GET2(mprime, primeRow, primeCol))
239 break; 239 break;
240 240
241 /* star the primed zero */ 241 /* star the primed zero */
242 SET2(nmstar, primeRow, primeCol); 242 SET2(nmstar, primeRow, primeCol);
243 243
244 /* find starred zero in current column */ 244 /* find starred zero in current column */
245 cstar = primeCol; 245 cstar = primeCol;
246 for(rstar=0; rstar<nrows; rstar++) 246 for(rstar=0; rstar<nrows; rstar++)
247 if(GET2(mstar, rstar, cstar)) 247 if(GET2(mstar, rstar, cstar))
248 break; 248 break;
249 } 249 }
250 250
251 /* use temporary copy as new mstar */ 251 /* use temporary copy as new mstar */
252 /* delete all primes, uncover all rows */ 252 /* delete all primes, uncover all rows */
253 memcpy(mstar, nmstar, sizeof(mat_t)); 253 memcpy(mstar, nmstar, sizeof(mat_t));
254 memset(mprime, 0, sizeof(mat_t)); 254 memset(mprime, 0, sizeof(mat_t));
255 memset(crow, 0, sizeof(col_t)); 255 memset(crow, 0, sizeof(col_t));
256 256
257 /* move to step 2a */ 257 /* move to step 2a */
258 step2a(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 258 step2a(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
259} 259}
@@ -275,23 +275,23 @@ static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime
275 found = 1; 275 found = 1;
276 } 276 }
277 } 277 }
278 278
279 /* where to go if nothing uncovered? */ 279 /* where to go if nothing uncovered? */
280 if (!found) 280 if (!found)
281 return; 281 return;
282 282
283 /* add h to each covered row */ 283 /* add h to each covered row */
284 for(row=0; row<nrows; row++) 284 for(row=0; row<nrows; row++)
285 if(GET1(crow, row)) 285 if(GET1(crow, row))
286 for(col=0; col<ncols; col++) 286 for(col=0; col<ncols; col++)
287 mdist[row + nrows*col] += h; 287 mdist[row + nrows*col] += h;
288 288
289 /* subtract h from each uncovered column */ 289 /* subtract h from each uncovered column */
290 for(col=0; col<ncols; col++) 290 for(col=0; col<ncols; col++)
291 if(!GET1(ccol,col)) 291 if(!GET1(ccol,col))
292 for(row=0; row<nrows; row++) 292 for(row=0; row<nrows; row++)
293 mdist[row + nrows*col] -= h; 293 mdist[row + nrows*col] -= h;
294 294
295 /* move to step 3 */ 295 /* move to step 3 */
296 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 296 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
297} 297}