[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.10

1.10    ! takayama    1: /* $OpenXM: OpenXM/src/kan96xx/Kan/gradedset.c,v 1.9 2005/07/03 11:08:53 ohara 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.10    ! takayama  376:   extern int 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>