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