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