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