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