Annotation of OpenXM/src/kan96xx/Kan/gradedset.c, Revision 1.4
1.4 ! takayama 1: /* $OpenXM: OpenXM/src/kan96xx/Kan/gradedset.c,v 1.3 2001/05/04 01:06:23 takayama Exp $ */
1.1 maekawa 2: #include <stdio.h>
3: #include "datatype.h"
4: #include "extern2.h"
5: #include "gradedset.h"
6:
7: #define INITSIZE 2 /* 2 is for debug */
8: static int Debug=0;
9:
10: struct polySet *newPolySet(n)
1.3 takayama 11: int n;
1.1 maekawa 12: {
13: struct polySet *g;
14: int i;
15: g = (struct polySet *)sGC_malloc(sizeof(struct polySet));
16: g->g = (POLY *)sGC_malloc(sizeof(POLY)*(n+1));
1.4 ! takayama 17: g->gh = (POLY *)sGC_malloc(sizeof(POLY)*(n+1));
1.1 maekawa 18: g->del = (int *)sGC_malloc(sizeof(int)*(n+1));
19: g->syz = (struct syz0 **)sGC_malloc(sizeof(struct syz0 *)*(n+1));
20: g->mark = (int *)sGC_malloc(sizeof(int)*(n+1));
21: g->serial = (int *)sGC_malloc(sizeof(int)*(n+1));
22: if (g->g == (POLY *)NULL || g->del == (int *)NULL ||
1.4 ! takayama 23: g->gh == (POLY *)NULL ||
1.1 maekawa 24: g->syz == (struct syz0 **)NULL || g->mark == (int *)NULL ||
25: g->serial == (int *)NULL) {
26: errorGradedSet("No more memory.");
27: }
28: g->lim = n;
29: g->size = 0;
30: for (i=0; i<n; i++) g->del[i] = g->mark[i] = 0;
31: if (Debug) printf("newPolySet(%d)\n",n);
32: return(g);
33: }
34:
35: struct pair *newPair(prev)
1.3 takayama 36: struct pair *prev;
1.1 maekawa 37: {
38: struct pair *g;
39: int i;
40: g = (struct pair *) sGC_malloc(sizeof(struct pair));
41: if (g == (struct pair *)NULL) errorGradedSet("No more memory.");
42: g->lcm = ZERO;
43: g->ig = g->ii = -1;
44: g->jg = g->ji = -1;
45: g->next = (struct pair *)NULL;
46: g->prev = (struct pair *)NULL;
47: g->del = 0;
48: return(g);
49: }
50:
51: struct gradedPolySet *newGradedPolySet(n)
1.3 takayama 52: int n;
1.1 maekawa 53: {
54: struct gradedPolySet *g;
55: g = (struct gradedPolySet *)sGC_malloc(sizeof(struct gradedPolySet));
56: if (g == (struct gradedPolySet *)NULL) errorGradedSet("No more memory.");
57: g->polys = (struct polySet **)sGC_malloc(sizeof(struct polySet *)*(n+1));
58: if (g->polys == (struct polySet **)NULL)
59: errorGradedSet("No more memory.");
60: g->maxGrade = 0;
61: g->lim = n;
62: return(g);
63: }
64:
65: struct gradedPairs *newGradedPairs(n)
1.3 takayama 66: int n;
1.1 maekawa 67: {
68: struct gradedPairs *g;
69: int i;
70: g = (struct gradedPairs *)sGC_malloc(sizeof(struct gradedPairs));
71: if (g == (struct gradedPairs *)NULL) errorGradedSet("No more memory.");
72: g->pairs = (struct pair **)sGC_malloc(sizeof(struct pair *)*(n+1));
73: if (g->pairs == (struct pair **)NULL) errorGradedSet("No more memory.");
74: for (i=0; i<n; i++) {
75: g->pairs[i] = newPair((struct pair *)NULL);
76: }
77: g->lim = n;
78: g->maxGrade = 0;
79: return(g);
80: }
81:
82: struct syz0 *newSyz0() {
83: struct syz0 *r;
84: r = (struct syz0 *)sGC_malloc(sizeof(struct syz0));
85: if (r == (struct syz0 *)NULL) errorGradedSet("newSyz0(): No memory.");
86: r->cf = ZERO; r->syz = ZERO;
87: return(r);
88: }
89:
90: struct pair *pairCopy(node)
1.3 takayama 91: struct pair *node;
1.1 maekawa 92: {
93: struct pair *r;
94: r = newPair(node->prev);
95: *r = *node;
96: return(r);
97: }
98:
99: struct gradedPairs *enlargeGradedPairs(size,grD)
1.3 takayama 100: int size;
101: struct gradedPairs *grD;
1.1 maekawa 102: {
103: struct gradedPairs *new;
104: int i;
105: new = newGradedPairs(size);
106: for (i=0; i<grD->lim; i++) {
107: new->pairs[i] = grD->pairs[i];
108: }
109: return(new);
110: }
111:
112: void insertPair(inode,before)
1.3 takayama 113: struct pair *inode;
114: struct pair *before;
1.1 maekawa 115: {
116: struct pair *q;
117: inode = pairCopy(inode);
118: if (before == (struct pair *)NULL)
119: errorGradedSet("insertPair(): *before must be a pair.");
120: q = before->next;
121: before->next = inode;
122: inode->prev = before;
123: inode->next = q;
124: if (q != (struct pair *)NULL) {
125: q->prev = inode;
126: }
127: }
128:
129: struct pair *deletePair(p)
1.3 takayama 130: struct pair *p;
1.1 maekawa 131: {
132: struct pair *q;
133: struct pair *r;
134: if (p == (struct pair *)NULL)
135: errorGradedSet("deletePair(): *p must be a pair.");
136: if (p->next == (struct pair *)NULL) return((struct pair *)NULL);
137: q = p->next->next;
138: r = p->next;
139: p->next = q;
140: if (q != (struct pair *)NULL) {
141: q->prev = p;
142: }
143: return(r);
144: }
145:
146: struct pair *getPair_org(grD)
1.3 takayama 147: struct gradedPairs *grD;
1.1 maekawa 148: {
149: int gmax,i;
150: struct pair *pair;
151: gmax = grD->maxGrade;
152: for (i=0; i<gmax; i++) {
153: if ((grD->pairs[i])->next != (struct pair *)NULL) {
154: pair = deletePair(grD->pairs[i]);
155: return(pair);
156: }
157: }
158: return((struct pair *)NULL);
159: }
160:
161: struct pair *getPair(grD)
1.3 takayama 162: struct gradedPairs *grD;
1.1 maekawa 163: {
164: int gmax,i;
165: struct pair *pair;
166: POLY minp;
167: struct pair *node,*minnode;
168: gmax = grD->maxGrade;
169: for (i=0; i<gmax; i++) {
170: if ((grD->pairs[i])->next != (struct pair *)NULL) {
171: node = grD->pairs[i]->next;
172: minp = node->lcm;
173: minnode = node;
174: node = node->next;
175: while (node != (struct pair *)NULL) {
1.3 takayama 176: if ((*mmLarger)(minp,node->lcm) >= 1) {
177: minnode = node;
178: minp = minnode->lcm;
179: }
180: node = node->next;
1.1 maekawa 181: }
182: pair = deletePair(minnode->prev);
183: return(pair);
184: }
185: }
186: return((struct pair *)NULL);
187: }
188:
189: void whereInG(g,fi,gradep,indexp,sugar)
1.3 takayama 190: struct gradedPolySet *g;
191: POLY fi;
192: int *gradep;
193: int *indexp;
194: int sugar;
1.1 maekawa 195: {
196: if (sugar) {
197: if (*gradep < 0 ) {
198: /* if sugar and *gradep < 0, then compute the grade.
1.3 takayama 199: Otherwise, grade is given by the caller. */
1.1 maekawa 200: *gradep = grade_sugar(fi);
201: }
202: }else{
203: *gradep = (*grade)(fi);
204: }
205:
206: if (*gradep < 0) {
207: warningGradedSet("whereInG(): the grade is -1.");
208: return;
209: }
210: if (*gradep >= g->maxGrade) {
211: *indexp = 0;
212: return;
213: }
214: *indexp = g->polys[*gradep]->size;
215: return;
216: }
217:
218: struct gradedPolySet *putPolyInG(g,fi,grade,index,syz,mark,serial)
1.3 takayama 219: struct gradedPolySet *g;
220: POLY fi;
221: int grade;
222: int index;
223: struct syz0 *syz;
224: int mark;
225: int serial;
1.1 maekawa 226: {
227: int i,j;
228: struct polySet *polysNew;
229: struct gradedPolySet *gnew;
230: struct polySet *ps;
231:
232: /*printf("--------------------\n");
1.3 takayama 233: outputGradedPolySet(g,0);*/
1.1 maekawa 234:
235: if (grade < 0) {
236: warningGradedSet("putPolyInG(): the grade is -1. The element is ignored.");
237: return(g);
238: }
239: if (grade >= g->lim) {
240: /* enlarge the gradedPolySet. */
241: if (Debug) printf("Enlarge the gradedPolySet.\n");
242: gnew = newGradedPolySet(grade*2+1);
243: for (i=0; i<g->lim; i++) {
244: gnew->polys[i] = g->polys[i];
245: }
246: for (i=g->lim; i<gnew->lim; i++) {
247: gnew->polys[i] = newPolySet(INITSIZE);
248: }
249: gnew->maxGrade = g->maxGrade;
250: g = gnew;
251: }
252:
253: if (g->polys[grade]->lim <= index) {
254: /* enlarge the polySet */
255: if (Debug) printf("Enlarge the polySet.\n");
256: polysNew = newPolySet(index*2+1);
257: for (i=0; i<g->polys[grade]->lim; i++) {
258: polysNew->g[i] = g->polys[grade]->g[i];
1.4 ! takayama 259: polysNew->gh[i] = g->polys[grade]->gh[i];
1.1 maekawa 260: polysNew->del[i] = g->polys[grade]->del[i];
261: polysNew->syz[i] = g->polys[grade]->syz[i];
262: polysNew->mark[i] = g->polys[grade]->mark[i];
263: polysNew->serial[i] = g->polys[grade]->serial[i];
264: }
265: polysNew->size = g->polys[grade]->size;
266: g->polys[grade] = polysNew;
267: }
268:
269: g->polys[grade]->size = index+1;
270: g->polys[grade]->g[index] = fi;
1.4 ! takayama 271: g->polys[grade]->gh[index] = POLYNULL;
1.1 maekawa 272: g->polys[grade]->del[index] = 0;
273: g->polys[grade]->syz[index] = syz;
274: g->polys[grade]->mark[index] = mark;
275: g->polys[grade]->serial[index] = serial;
276: if (g->maxGrade < grade+1) g->maxGrade = grade+1;
277:
278: /*printf("grade=%d, index=%d\n",grade,index);
1.3 takayama 279: outputGradedPolySet(g,0);*/
1.1 maekawa 280: return(g);
281: }
282:
283: void markRedundant(g,fi,grade,index,sugar)
1.3 takayama 284: struct gradedPolySet *g;
285: POLY fi;
286: int grade,index;
287: int sugar;
1.1 maekawa 288: {
289: int i,j;
290: struct polySet *ps;
291: int start;
292:
293: /* mark redundant */
294: if (sugar) start=0;else start=grade;
295: for (i=start; i<g->maxGrade; i++) {
296: ps = g->polys[i];
297: for (j=0; j<ps->size; j++) {
298: if (i == grade && j == index) {
299: }else if ((*isReducible)(ps->g[j],fi)) {
1.3 takayama 300: ps->del[j] = 1;
1.1 maekawa 301: }
302: }
303: }
304: }
305:
306: void markRedundant0(g,grade,index)
1.3 takayama 307: struct gradedPolySet *g;
308: int grade,index;
1.1 maekawa 309: {
310: int i,j;
311: struct polySet *ps;
312: POLY fi;
313:
314: fi = g->polys[grade]->g[index];
315: /* mark redundant */
316: for (i=0; i<g->maxGrade; i++) {
317: ps = g->polys[i];
318: for (j=0; j<ps->size; j++) {
319: if (i == grade && j == index) {
320: }else if ((*isReducible)(ps->g[j],fi)) {
1.3 takayama 321: ps->del[j] = 1;
1.1 maekawa 322: }else if ((*isReducible)(fi,ps->g[j])) {
1.3 takayama 323: g->polys[grade]->del[index] = 1;
324: return;
1.1 maekawa 325: }
326: }
327: }
328: }
329:
330: struct gradedPairs *putPairInGradedPairs(struct gradedPairs *grP,
1.3 takayama 331: struct pair *top)
1.1 maekawa 332: {
333: if (grP == (struct gradedPairs *)NULL) {
334: grP = newGradedPairs(top->grade +1);
335: }
336: if (grP->lim <= top->grade) {
337: grP = enlargeGradedPairs(2*(top->grade)+1,grP);
338: }
339: insertPair(top,grP->pairs[top->grade]);
340: grP->maxGrade = max(grP->maxGrade,top->grade+1);
341: return(grP);
342: }
343:
344: void errorGradedSet(s)
1.3 takayama 345: char *s;
1.1 maekawa 346: {
347: fprintf(stderr,"Error in gradedset.c, red.c, gb.c: %s\n",s);
348: exit(23);
349: }
350:
351: void warningGradedSet(s)
1.3 takayama 352: char *s;
1.1 maekawa 353: {
354: fprintf(stderr,"Warning in gradedset.c, red.c, gb.c: %s\n",s);
355: }
356:
357:
358: void outputGradedPolySet(grG,needSyz)
1.3 takayama 359: struct gradedPolySet *grG;
360: int needSyz;
1.1 maekawa 361: {
362: int i,j;
363: struct polySet *set;
1.4 ! takayama 364: extern Ecart;
1.1 maekawa 365: printf("======== gradedPolySet ==========\n");
366: printf("maxGrade=%d\n",grG->maxGrade);
367: for (i=0; i<grG->maxGrade; i++) {
368: set = grG->polys[i];
369: printf("grade=%d, size=%d\n",i,set->size);
370: for (j=0; j<set->size; j++) {
371: printf("j=%d, del=%d, g=%s\n",j,set->del[j],POLYToString(set->g[j],'*',1));
1.4 ! takayama 372: if (Ecart) printf(" gh=%s\n",POLYToString(set->gh[j],'*',1));
1.1 maekawa 373: if (needSyz) {
1.3 takayama 374: printf("mark=%d,serial=%d, syz.cf=%s, syz.syz=%s\n",set->mark[j],
375: set->serial[j],POLYToString(set->syz[j]->cf,'*',1),
376: POLYToString(set->syz[j]->syz,'*',1));
1.1 maekawa 377: }else{
1.3 takayama 378: printf("mark=%d,serial=%d\n",set->mark[j],
379: set->serial[j]);
1.1 maekawa 380: }
381: }
382: }
383: printf("================================\n\n");
384: }
385:
386: int countGradedPolySet(grG)
1.3 takayama 387: struct gradedPolySet *grG;
1.1 maekawa 388: {
389: int i,j;
390: struct polySet *set;
391: int count = 0;
392: for (i=0; i<grG->maxGrade; i++) {
393: set = grG->polys[i];
394: count += set->size;
395: }
396: return(count);
397: }
398:
399:
400: void outputGradedPairs(grP)
1.3 takayama 401: struct gradedPairs *grP;
1.1 maekawa 402: {
403: int i,j;
404: struct pair *pair;
405: printf("============ gradedPairs ========\n");
406: printf("maxGrade=%d\n",grP->maxGrade);
407: for (i=0; i<grP->maxGrade; i++) {
408: pair = grP->pairs[i]->next;
409: printf("grade=%d\n",i);
410: while (pair != (struct pair *)NULL) {
411: printf("lcm=%s, \n",POLYToString(pair->lcm,'*',1));
412: printf("(grade,index): (%d,%d) and (%d,%d)\n",pair->ig,pair->ii,pair->jg,pair->ji);
413: printf("grade=%d\n",pair->grade);
414: pair = pair->next;
415: }
416: }
417: printf("============================\n\n");
418: }
419:
420: void outputNode(pair)
1.3 takayama 421: struct pair *pair;
1.1 maekawa 422: {
423: int i = 0;
424: printf("=== list === \n");
425: while (pair != (struct pair *)NULL) {
426: printf("lcm=%s, \n",POLYToString(pair->lcm,'*',1));
427: printf("(grade,index): (%d,%d) and (%d,%d)\n",pair->ig,pair->ii,pair->jg,pair->ji);
428: printf("grade=%d\n",pair->grade);
429: pair = pair->next;
430: i++;
431: if (i > 100) {
432: printf("Too long list. Type in ret.");
433: getchar(); getchar();
434: }
435: }
436: printf("=========\n");
437: }
438:
439:
440: int countPairs(grD)
1.3 takayama 441: struct gradedPairs *grD;
1.1 maekawa 442: {
443: int i;
444: int c;
445: struct pair *p;
446: c = 0;
447: for (i=0; i<grD->maxGrade; i++) {
448: p = grD->pairs[i];
449: p = p->next;
450: while (p != (struct pair *)NULL) {
451: c++;
452: p = p->next;
453: }
454: }
455: return(c);
456: }
457:
458: struct gradedPolySet *gradedPolySetCopy(grG)
1.3 takayama 459: struct gradedPolySet *grG;
1.1 maekawa 460: {
461: int i,j;
462: struct polySet *ps,*psOld;
463: struct gradedPolySet *newG;
464:
465: newG = newGradedPolySet(grG->maxGrade+1);
466: for (i=0; i<grG->maxGrade;i++) {
467: ps = newG->polys[i] = newPolySet((grG->polys[i]->size) +1);
468: psOld = grG->polys[i];
469: for (j=0; j<psOld->size; j++) {
470: ps->g[j] = psOld->g[j];
471: ps->del[j] = psOld->del[j];
472: ps->syz[j] = psOld->syz[j];
473: ps->mark[j] = psOld->mark[j];
474: ps->serial[j] = psOld->serial[j];
475: }
476: ps->size = psOld->size;
477: }
478: newG->maxGrade = grG->maxGrade;
479: return(newG);
480: }
481:
482: int deletePairByCriterion2B(struct gradedPairs *grD,POLY gt,
1.3 takayama 483: struct gradedPolySet *grG)
1.1 maekawa 484: {
485: int gmax,i;
486: struct pair *node;
487: int count;
488: POLY it;
489: POLY ij;
490: POLY jt;
491: int ig,ii,jg,ji;
492: count = 0;
493: gmax = grD->maxGrade;
494: for (i=0; i<gmax; i++) {
495: if ((grD->pairs[i])->next != (struct pair *)NULL) {
496: node = grD->pairs[i]->next;
497: while (node != (struct pair *)NULL) {
1.3 takayama 498: ig = node->ig; ii = node->ii;
499: jg = node->jg; ji = node->ji;
500: if ((*isReducible)(node->lcm,gt)) {
501: ig = node->ig; ii = node->ii;
502: jg = node->jg; ji = node->ji;
503: it = (*lcm)(grG->polys[ig]->g[ii],gt);
504: ij = (*lcm)(grG->polys[ig]->g[ii],grG->polys[jg]->g[ji]);
505: jt = (*lcm)(grG->polys[jg]->g[ji],gt);
506: if ((*mmLarger)(it,ij) != 2 &&
507: (*mmLarger)(it,jt) != 2 &&
508: (*mmLarger)(ij,jt) != 2) {
509: node = deletePair(node->prev);
510: count++;
511: }
512: }
513: node = node->next;
1.1 maekawa 514: }
515: }
516: }
517: return(count);
518: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gradedset.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / src / kan96xx / Kan