Annotation of OpenXM/src/kan96xx/Kan/gradedset.c, Revision 1.8
1.8 ! takayama 1: /* $OpenXM: OpenXM/src/kan96xx/Kan/gradedset.c,v 1.7 2005/06/16 06:54:55 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;
1.8 ! takayama 256: gnew->gb = g->gb; gnew->reduced = g->reduced;
1.1 maekawa 257: g = gnew;
258: }
259:
260: if (g->polys[grade]->lim <= index) {
261: /* enlarge the polySet */
262: if (Debug) printf("Enlarge the polySet.\n");
263: polysNew = newPolySet(index*2+1);
264: for (i=0; i<g->polys[grade]->lim; i++) {
265: polysNew->g[i] = g->polys[grade]->g[i];
1.4 takayama 266: polysNew->gh[i] = g->polys[grade]->gh[i];
1.6 takayama 267: polysNew->gmod[i] = g->polys[grade]->gmod[i];
1.5 takayama 268: polysNew->gen[i] = g->polys[grade]->gen[i];
1.1 maekawa 269: polysNew->del[i] = g->polys[grade]->del[i];
270: polysNew->syz[i] = g->polys[grade]->syz[i];
271: polysNew->mark[i] = g->polys[grade]->mark[i];
272: polysNew->serial[i] = g->polys[grade]->serial[i];
273: }
274: polysNew->size = g->polys[grade]->size;
275: g->polys[grade] = polysNew;
276: }
277:
278: g->polys[grade]->size = index+1;
279: g->polys[grade]->g[index] = fi;
1.4 takayama 280: g->polys[grade]->gh[index] = POLYNULL;
1.6 takayama 281: g->polys[grade]->gmod[index] = POLYNULL;
1.5 takayama 282: g->polys[grade]->gen[index] = 0;
1.1 maekawa 283: g->polys[grade]->del[index] = 0;
284: g->polys[grade]->syz[index] = syz;
285: g->polys[grade]->mark[index] = mark;
286: g->polys[grade]->serial[index] = serial;
287: if (g->maxGrade < grade+1) g->maxGrade = grade+1;
288:
289: /*printf("grade=%d, index=%d\n",grade,index);
1.3 takayama 290: outputGradedPolySet(g,0);*/
1.1 maekawa 291: return(g);
292: }
293:
294: void markRedundant(g,fi,grade,index,sugar)
1.3 takayama 295: struct gradedPolySet *g;
296: POLY fi;
297: int grade,index;
298: int sugar;
1.1 maekawa 299: {
300: int i,j;
301: struct polySet *ps;
302: int start;
303:
304: /* mark redundant */
305: if (sugar) start=0;else start=grade;
306: for (i=start; i<g->maxGrade; i++) {
307: ps = g->polys[i];
308: for (j=0; j<ps->size; j++) {
309: if (i == grade && j == index) {
310: }else if ((*isReducible)(ps->g[j],fi)) {
1.5 takayama 311: if (! ps->gen[j]) ps->del[j] = 1; /*?*/
1.1 maekawa 312: }
313: }
314: }
315: }
316:
317: void markRedundant0(g,grade,index)
1.3 takayama 318: struct gradedPolySet *g;
319: int grade,index;
1.1 maekawa 320: {
321: int i,j;
322: struct polySet *ps;
323: POLY fi;
324:
325: fi = g->polys[grade]->g[index];
326: /* mark redundant */
327: for (i=0; i<g->maxGrade; i++) {
328: ps = g->polys[i];
329: for (j=0; j<ps->size; j++) {
330: if (i == grade && j == index) {
331: }else if ((*isReducible)(ps->g[j],fi)) {
1.5 takayama 332: if (! ps->gen[j] ) ps->del[j] = 1; /*?*/
1.1 maekawa 333: }else if ((*isReducible)(fi,ps->g[j])) {
1.5 takayama 334: if (! g->polys[grade]->gen[index] ) g->polys[grade]->del[index] = 1; /*?*/
1.3 takayama 335: return;
1.1 maekawa 336: }
337: }
338: }
339: }
340:
341: struct gradedPairs *putPairInGradedPairs(struct gradedPairs *grP,
1.3 takayama 342: struct pair *top)
1.1 maekawa 343: {
344: if (grP == (struct gradedPairs *)NULL) {
345: grP = newGradedPairs(top->grade +1);
346: }
347: if (grP->lim <= top->grade) {
348: grP = enlargeGradedPairs(2*(top->grade)+1,grP);
349: }
350: insertPair(top,grP->pairs[top->grade]);
351: grP->maxGrade = max(grP->maxGrade,top->grade+1);
352: return(grP);
353: }
354:
355: void errorGradedSet(s)
1.3 takayama 356: char *s;
1.1 maekawa 357: {
358: fprintf(stderr,"Error in gradedset.c, red.c, gb.c: %s\n",s);
359: exit(23);
360: }
361:
362: void warningGradedSet(s)
1.3 takayama 363: char *s;
1.1 maekawa 364: {
365: fprintf(stderr,"Warning in gradedset.c, red.c, gb.c: %s\n",s);
366: }
367:
368:
369: void outputGradedPolySet(grG,needSyz)
1.3 takayama 370: struct gradedPolySet *grG;
371: int needSyz;
1.1 maekawa 372: {
373: int i,j;
374: struct polySet *set;
1.4 takayama 375: extern Ecart;
1.1 maekawa 376: printf("======== gradedPolySet ==========\n");
377: printf("maxGrade=%d\n",grG->maxGrade);
378: for (i=0; i<grG->maxGrade; i++) {
379: set = grG->polys[i];
380: printf("grade=%d, size=%d\n",i,set->size);
381: for (j=0; j<set->size; j++) {
382: printf("j=%d, del=%d, g=%s\n",j,set->del[j],POLYToString(set->g[j],'*',1));
1.4 takayama 383: if (Ecart) printf(" gh=%s\n",POLYToString(set->gh[j],'*',1));
1.1 maekawa 384: if (needSyz) {
1.3 takayama 385: printf("mark=%d,serial=%d, syz.cf=%s, syz.syz=%s\n",set->mark[j],
386: set->serial[j],POLYToString(set->syz[j]->cf,'*',1),
387: POLYToString(set->syz[j]->syz,'*',1));
1.1 maekawa 388: }else{
1.3 takayama 389: printf("mark=%d,serial=%d\n",set->mark[j],
390: set->serial[j]);
1.1 maekawa 391: }
392: }
393: }
394: printf("================================\n\n");
395: }
396:
397: int countGradedPolySet(grG)
1.3 takayama 398: struct gradedPolySet *grG;
1.1 maekawa 399: {
400: int i,j;
401: struct polySet *set;
402: int count = 0;
403: for (i=0; i<grG->maxGrade; i++) {
404: set = grG->polys[i];
405: count += set->size;
406: }
407: return(count);
408: }
409:
410:
411: void outputGradedPairs(grP)
1.3 takayama 412: struct gradedPairs *grP;
1.1 maekawa 413: {
414: int i,j;
415: struct pair *pair;
416: printf("============ gradedPairs ========\n");
417: printf("maxGrade=%d\n",grP->maxGrade);
418: for (i=0; i<grP->maxGrade; i++) {
419: pair = grP->pairs[i]->next;
420: printf("grade=%d\n",i);
421: while (pair != (struct pair *)NULL) {
422: printf("lcm=%s, \n",POLYToString(pair->lcm,'*',1));
423: printf("(grade,index): (%d,%d) and (%d,%d)\n",pair->ig,pair->ii,pair->jg,pair->ji);
424: printf("grade=%d\n",pair->grade);
425: pair = pair->next;
426: }
427: }
428: printf("============================\n\n");
429: }
430:
431: void outputNode(pair)
1.3 takayama 432: struct pair *pair;
1.1 maekawa 433: {
434: int i = 0;
435: printf("=== list === \n");
436: while (pair != (struct pair *)NULL) {
437: printf("lcm=%s, \n",POLYToString(pair->lcm,'*',1));
438: printf("(grade,index): (%d,%d) and (%d,%d)\n",pair->ig,pair->ii,pair->jg,pair->ji);
439: printf("grade=%d\n",pair->grade);
440: pair = pair->next;
441: i++;
442: if (i > 100) {
443: printf("Too long list. Type in ret.");
444: getchar(); getchar();
445: }
446: }
447: printf("=========\n");
448: }
449:
450:
451: int countPairs(grD)
1.3 takayama 452: struct gradedPairs *grD;
1.1 maekawa 453: {
454: int i;
455: int c;
456: struct pair *p;
457: c = 0;
458: for (i=0; i<grD->maxGrade; i++) {
459: p = grD->pairs[i];
460: p = p->next;
461: while (p != (struct pair *)NULL) {
462: c++;
463: p = p->next;
464: }
465: }
466: return(c);
467: }
468:
469: struct gradedPolySet *gradedPolySetCopy(grG)
1.3 takayama 470: struct gradedPolySet *grG;
1.1 maekawa 471: {
472: int i,j;
473: struct polySet *ps,*psOld;
474: struct gradedPolySet *newG;
475:
476: newG = newGradedPolySet(grG->maxGrade+1);
477: for (i=0; i<grG->maxGrade;i++) {
478: ps = newG->polys[i] = newPolySet((grG->polys[i]->size) +1);
479: psOld = grG->polys[i];
480: for (j=0; j<psOld->size; j++) {
481: ps->g[j] = psOld->g[j];
482: ps->del[j] = psOld->del[j];
483: ps->syz[j] = psOld->syz[j];
484: ps->mark[j] = psOld->mark[j];
485: ps->serial[j] = psOld->serial[j];
486: }
487: ps->size = psOld->size;
488: }
489: newG->maxGrade = grG->maxGrade;
490: return(newG);
491: }
492:
493: int deletePairByCriterion2B(struct gradedPairs *grD,POLY gt,
1.3 takayama 494: struct gradedPolySet *grG)
1.1 maekawa 495: {
496: int gmax,i;
497: struct pair *node;
498: int count;
499: POLY it;
500: POLY ij;
501: POLY jt;
502: int ig,ii,jg,ji;
503: count = 0;
504: gmax = grD->maxGrade;
505: for (i=0; i<gmax; i++) {
506: if ((grD->pairs[i])->next != (struct pair *)NULL) {
507: node = grD->pairs[i]->next;
508: while (node != (struct pair *)NULL) {
1.3 takayama 509: ig = node->ig; ii = node->ii;
510: jg = node->jg; ji = node->ji;
511: if ((*isReducible)(node->lcm,gt)) {
512: ig = node->ig; ii = node->ii;
513: jg = node->jg; ji = node->ji;
514: it = (*lcm)(grG->polys[ig]->g[ii],gt);
515: ij = (*lcm)(grG->polys[ig]->g[ii],grG->polys[jg]->g[ji]);
516: jt = (*lcm)(grG->polys[jg]->g[ji],gt);
517: if ((*mmLarger)(it,ij) != 2 &&
518: (*mmLarger)(it,jt) != 2 &&
519: (*mmLarger)(ij,jt) != 2) {
520: node = deletePair(node->prev);
521: count++;
522: }
523: }
524: node = node->next;
1.1 maekawa 525: }
526: }
527: }
528: return(count);
1.5 takayama 529: }
530:
531: int markGeneratorInG(struct gradedPolySet *g,int grade,int index)
532: {
533: g->polys[grade]->gen[index] = 1;
534: return 1;
1.6 takayama 535: }
536:
537: int clearGmod(struct gradedPolySet *gset) {
538: int grd,i;
539: struct polySet *set;
540: for (grd=0; grd < gset->maxGrade; grd++) {
541: set = gset->polys[grd];
542: for (i = 0; i<set->size; i++) {
543: set->gmod[i] = POLYNULL;
544: }
545: }
1.1 maekawa 546: }
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