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