[BACK]Return to gradedset.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / Kan

Annotation of OpenXM/src/kan96xx/Kan/gradedset.c, Revision 1.2

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>