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