1 /* solve.c: solve cycles for the automapper
2 Copyright (C) 1999 Evin Robertson
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
18 The author can be reached at nitfol@deja.com
25 /* Rational number stuff - doesn't handle overflow conditions */
27 typedef struct rational rational;
33 static int gcd(int a, int b)
40 static int lcm(int a, int b)
42 return a * b / gcd(a, b);
45 static rational rational_reduce(rational r)
47 int g = gcd(r.num, r.den);
59 static BOOL rational_iszero(rational r)
64 static BOOL rational_isone(rational r)
66 return r.num == r.den;
69 static rational rational_int(int i)
77 static rational rational_add(rational a, rational b)
80 r.num = a.num * b.den + a.den * b.num;
81 r.den = a.den * b.den;
82 return rational_reduce(r);
85 static rational rational_sub(rational a, rational b)
88 r.num = a.num * b.den - a.den * b.num;
89 r.den = a.den * b.den;
90 return rational_reduce(r);
93 static rational rational_mult(rational a, rational b)
97 return rational_reduce(a);
100 static rational rational_div(rational a, rational b)
104 return rational_reduce(a);
109 typedef struct cycleequation cycleequation;
110 struct cycleequation {
120 typedef struct equation equation;
126 rational coefficient;
127 int count; /* Number of times variable is used */
130 typedef struct equalist equalist;
136 static equalist *equats = NULL;
138 void automap_add_cycle(cycleequation *cycle)
140 equation *newx = NULL;
141 equation *newy = NULL;
145 for(p = cycle; p; p=p->next) {
147 newnode.var = p->var;
148 newnode.min = p->min;
149 newnode.coefficient.den = 1;
150 newnode.coefficient.num = p->xcoefficient;
151 LEadd(newx, newnode);
153 newnode.coefficient.num = p->ycoefficient;
154 LEadd(newy, newnode);
158 LEadd(equats, newlist);
160 LEadd(equats, newlist);
165 void automap_delete_cycles(void)
168 for(p = equats; p; p=p->next)
174 /* Do Gauss-Jordan elimination. */
175 /* This could be done with lists instead of arrays with clever hash stuff, but
176 this is simpler, and the elimination stage takes O(n^3) anyway */
177 void automap_cycle_elimination(void)
181 equation *variablelist = NULL;
182 int width = 0, height = 0;
185 int row, column, i, n;
188 /* First, figure out how many variables we're dealing with */
189 for(p = equats; p; p=p->next) {
190 for(q = p->eq; q; q=q->next) {
191 for(v = variablelist; v; v=v->next)
195 LEadd(variablelist, *q);
202 if(height == 0 || width == 0)
205 /* An array implementation is easier to think about than a linked-list one */
206 array = (rational *) n_malloc(width * height * sizeof(rational));
210 for(p = equats; p; p=p->next) {
211 for(v = variablelist; v; v=v->next) {
212 for(q = p->eq; q; q=q->next)
215 *r++ = q ? q->coefficient : rational_int(0);
219 /* Do the actual elimination */
222 while(row < height && column < width) {
224 /* If zero, swap with a non-zero row */
225 if(rational_iszero(r[column])) {
227 for(i = row+1; i < height; i++) {
228 if(!rational_iszero(array[i * width + column])) {
229 n_memswap(&array[row * width], &array[i * width],
230 width * sizeof(*array));
235 if(!found) { /* Zeroed column; try next */
241 /* Divide row by leading coefficient */
243 for(n = 0; n < width; n++)
244 r[n] = rational_div(r[n], c);
246 /* Eliminate other entries in current column */
248 for(i = 0; i < height; i++) {
249 if(i != row && !rational_iszero(s[column])) {
251 for(n = 0; n < width; n++)
252 s[n] = rational_sub(s[n], rational_mult(r[n], c));
261 /* Delete the old lists */
262 automap_delete_cycles();
264 /* Count how many times each variable is used */
265 for(v = variablelist; v; v=v->next)
268 for(i = 0; i < height; i++) {
269 for(v = variablelist; v; v=v->next) {
270 if(!rational_iszero(*r))
276 /* Make new lists from the array */
278 for(i = 0; i < height; i++) {
279 equation *neweq = NULL;
280 for(v = variablelist; v; v=v->next) {
281 if(!rational_iszero(*r)) {
284 newnode.coefficient = *r;
285 LEadd(neweq, newnode);
292 LEadd(equats, newlist);
300 /* Find an edge to lengthen which would cause the least amount of lengthening
301 to edges in other cycles */
302 static equation *select_edge(equation *cycle, int *need_recalc)
304 equation *help = NULL; /* Increasing its length will help other cycles */
305 equation *solitary = NULL; /* Only in one cycle */
306 equation *nonharm = NULL; /* Increasing its length won't destroy things */
307 BOOL is_harmful_past = FALSE;
311 for(p = cycle; p; p=p->next) {
312 if(p->next && p->coefficient.num < 0) {
314 BOOL pastthis = FALSE;
315 BOOL is_found = FALSE;
316 BOOL is_harmful = FALSE;
317 BOOL is_past = FALSE;
318 BOOL is_help = FALSE;
319 BOOL is_compensator = FALSE;
320 for(t = equats; t; t=t->next) {
324 rational sum = rational_int(0);
325 equation *r, *foundme = NULL;
326 BOOL first_find = TRUE;
327 for(r = t->eq; r; r=r->next) {
329 int value = *(r->var) ? *(r->var) : *(r->min);
330 sum = rational_add(sum, rational_mult(r->coefficient,
331 rational_int(value)));
332 if(r->count == 1 && r->coefficient.num < 0)
333 is_compensator = TRUE;
334 if(r->var == p->var) {
338 is_past = pastthis && (is_past || !is_found);
340 if(r->coefficient.num > 0)
343 } else if(pastthis && foundme && -sum.num < *(r->min) && first_find
344 && foundme->coefficient.num < 0)
349 if(is_help && !is_harmful && !help)
353 } else if(!is_harmful || is_compensator) {
354 if(!nonharm || is_past) {
355 is_harmful_past = !is_past;
362 if(help) return help;
363 if(solitary) return solitary;
364 if(nonharm) { if(is_harmful_past) *need_recalc = 2; return nonharm; }
371 /* Fill variables with valid numbers. Assumes Gauss-Jordan elimination has
373 void automap_cycles_fill_values(void)
380 for(p = equats; p; p=p->next)
381 for(q = p->eq; q; q=q->next)
384 for(calccount = 0; calccount <= recalculate; calccount++) {
387 /* Last variable in each list is the dependant; all others are independant */
388 /* Fill independant variables with their minimums, then calculate the
389 dependant one; if it's less than its minimum, play with independants */
390 for(p = equats; p; p=p->next) {
391 rational sum = rational_int(0);
392 for(q = p->eq; q; q=q->next) {
393 if(q->next) { /* Independant */
394 int value = *(q->var) ? *(q->var) : *(q->min);
395 sum = rational_add(sum, rational_mult(q->coefficient,
396 rational_int(value)));
398 } else { /* Dependant */
399 int value = -sum.num;
400 if(!rational_isone(q->coefficient))
401 n_show_error(E_SYSTEM, "last coefficient not 1", q->coefficient.num);
403 n_show_error(E_SYSTEM, "unimplemented case denominator != 1", sum.den);
404 else if(value < *(q->min)) {
405 /* Edge is not long enough - try increasing lengths of another edge
406 in cycle to lengthen it */
407 equation *m = select_edge(p->eq, &recalculate);
410 rational oldval = rational_mult(m->coefficient,
411 rational_int(*(m->var)));
413 int diff = value - *(q->min);
414 sum = rational_sub(sum, oldval);
416 n_show_error(E_SYSTEM, "unimplemented case denominator != 1", oldval.den);
418 newval = rational_div(rational_int(diff), m->coefficient);
419 *(m->var) = newval.num;
420 sum = rational_add(sum, rational_mult(m->coefficient, newval));
423 if(value > *(q->min))
424 n_show_error(E_SYSTEM, "met more than needed", sum.num);
426 if(value < *(q->min))
427 n_show_error(E_SYSTEM, "failed to meet needs", sum.num);
429 sum = rational_add(sum, rational_mult(q->coefficient,
430 rational_int(*(q->var))));
431 if(!rational_iszero(sum))
432 n_show_error(E_SYSTEM, "doesn't add up", sum.num);
439 rational checksum = rational_int(0);
441 for(cq = p->eq; cq; cq=cq->next) {
442 checksum = rational_add(checksum,rational_mult(cq->coefficient,
443 rational_int(*(cq->var))));
445 if(checksum.num != sum.num || checksum.den != sum.den) {
446 n_show_error(E_SYSTEM, "correction for correction incorrect", checksum.num);
455 for(p = equats; p; p=p->next) {
456 rational sum = rational_int(0);
457 for(q = p->eq; q; q=q->next) {
458 if(*(q->var) < *(q->min))
459 n_show_error(E_SYSTEM, "variable less than minimum", *(q->var));
460 sum = rational_add(sum, rational_mult(q->coefficient,
461 rational_int(*(q->var))));
463 if(!rational_iszero(sum))
464 n_show_error(E_SYSTEM, "equation not equal", sum.num / sum.den);