Annotation of OpenXM/src/kan96xx/Kan/gradedset.c, Revision 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