Changeset 66e7b5 in git


Ignore:
Timestamp:
Jan 29, 2009, 6:59:30 PM (14 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')
Children:
5d0556d9643aab314fbe86e3ef4cbcd69d864661
Parents:
5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b
Message:
subalgorithms criticalPairs, criterion1 and criterion2 added


git-svn-id: file:///usr/local/Singular/svn/trunk@11343 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
kernel
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r5376a6 r66e7b5  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.cc,v 1.18 2009-01-28 17:20:49 Singular Exp $ */
     4/* $Id: f5gb.cc,v 1.19 2009-01-29 17:59:30 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    6767==================================================
    6868*/
    69 LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE) {
     69LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE, RList* rules, LTagList* lTag) {
    7070    gPrev->insert(ONE,i,f_i);
    71     CList* critPairs    =   criticalPair(gPrev);
    72      
     71    CList* critPairs    =   new CList();
     72    critPairs           =   criticalPair(gPrev, critPairs, rules, lTag);
     73   
    7374    return gPrev;
    7475}
    … …  
    8283================================================================
    8384*/
    84 CList* criticalPair(LList* gPrev) {
    85     poly lcm   = pInit();
    86     number n    = nInit(2);
    87     nWrite(n);
    88     pWrite(lcm);
     85CList* criticalPair(LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag) {
    8986    // initialization for usage in pLcm()
     87    number nOne         =   nInit(1);
    9088    LNode* first        =   gPrev->getFirst();
    9189    LNode* l            =   gPrev->getFirst()->getNext();
    92     poly t1, t2         =   pInit();
    93     t1                  =   pHead(*first->getPoly());
    94     poly u1             =   pOne();
    95     poly u2             =   pOne();
    96     CList*  critpairs   =   NULL;
     90    poly* u1            =   new poly(pInit());
     91    poly* u2            =   new poly(pInit());
     92    poly* lcm           =   new poly(pInit());
    9793    // computation of critical pairs
    9894    while( NULL != l) {
    9995        //pWrite( *(gPrev->getFirst()->getPoly()) );
    10096        //pWrite( *(l->getPoly()) );
    101         pLcm(*first->getPoly(), *l->getPoly(), t1);
    102         pWrite(t1);
    103         pWrite(u1);
    104         pWrite(u2);
    105         pSetCoeff0(lcm,n);
    106         poly p = lcm;
    107         pWrite(p);
    108         Print("%ld\n",pDeg(t1));
     97        pLcm(first->getPoly(), l->getPoly(), *lcm);
     98        pSetCoeff(*lcm,nOne);
    10999        // computing factors u1 & u2 for new labels
    110         u1  = pDivide(lcm, t1);
    111         pWrite(u1);
    112         pWrite(t1);
    113         Print("%ld\n",pDeg(t1));
    114         //pSetCoeff(u1,pGetCoeff(pOne()));
    115         pWrite(u1);
    116         t2  = pHead(*l->getPoly());
    117         pWrite(t2);
    118         // testing stuff
    119         u1 = ppMult_qq(t1,t2);
    120         pWrite(u1);
    121         pWrite(t2);
    122         Print("%ld\n",pDeg(u1));
    123         Print("%ld\n",pDeg(t2));
    124         u2  = pDivide(lcm, t2);
    125         pSetCoeff(u2, pGetCoeff(pOne()));
    126         pWrite(u2);
    127         Print("%ld\n",pDeg(u2));
     100        *u1 = pDivide(*lcm,pHead(first->getPoly()));
     101        pSetCoeff(*u1,nOne);
     102        *u2 = pDivide(*lcm, pHead(l->getPoly()));
     103        pSetCoeff(*u2,nOne);
     104        pWrite(*u2);
    128105        // testing both new labels by the F5 Criterion
    129         if(!criterion1(first, gPrev) &&
    130            !criterion1(l, gPrev)) {
    131             if(*first->getIndex() == *l->getIndex()) {
    132                 if(pMult(u1, *first->getTerm()) < pMult(u2, *l->getTerm())) {
    133                     //if(!critPairs) {
    134                         CPair* cp   =   new CPair(pDeg(lcm), u1, first->getLPoly(), u2,
    135                                         l->getLPoly());                   
    136                     //}
    137                 }
    138             }
    139         }
    140 
    141         Print("\n");
     106        if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) &&
     107           !criterion2(u1, first, rules) && !criterion2(u2, l, rules)) {
     108            Print("Criteria passed\n");
     109            // if they pass the test, add them to CList critPairs, having the LPoly with greater
     110            // label as first element in the CPair
     111            if(first->getIndex() == l->getIndex() &&
     112            pMult(*u1, first->getTerm()) < pMult(*u2, l->getTerm())) {
     113                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u2,
     114                                l->getLPoly(), *u1, first->getLPoly());                   
     115                    critPairs->insert(cp);
     116            }
     117            else {
     118                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u1,
     119                                first->getLPoly(), *u2, l->getLPoly());                   
     120                    critPairs->insert(cp);
     121            }
     122        }
     123        else {
     124            Print("Criteria not passed\n");
     125        }
     126       
     127        // for debugging
     128        if(NULL != critPairs) {
     129            critPairs->print();
     130        }
    142131        l   =   l->getNext();
    143132    }
    144     return NULL;
     133    Print("ENDE CRITPAIRS\n");
     134    return critPairs;
    145135}
    146136
    … …  
    150140========================================
    151141*/
    152 bool criterion1(LNode* l, LList* gPrev) {
    153     LNode* testNode =   l->getNext();
     142bool criterion1(poly* t, LNode* l, LTagList* lTag) {
     143    // start at the previously added element to gPrev, as all other elements will have the same index for sure
     144    LNode* testNode =   lTag->get(l->getIndex());
     145    // save the monom t1*label_term(l) as it is tested various times in the following
     146    poly u1 = ppMult_qq(*t,l->getTerm());
    154147    while(NULL != testNode) {
    155         while(*testNode->getIndex() == *l->getIndex()) {
     148        //while(NULL != testNode && testNode->getIndex() == l->getIndex()) {
     149        //    testNode = testNode->getNext();
     150        //}
     151        Print("%d\n", pLmDivisibleByNoComp(pHead(testNode->getPoly()),u1));
     152        if(NULL != testNode && pLmDivisibleByNoComp(pHead(testNode->getPoly()),u1)) {
     153            return true;
     154        }
     155        testNode    =   testNode->getNext();
     156       
     157    }
     158    // 25/01/2009: TO DO -> change return value, until now no element is added to CList!
     159    return false;
     160}
     161
     162/*
     163=====================================
     164Criterion 2, i.e. Rewritten Criterion
     165=====================================
     166*/
     167bool criterion2(poly* t, LNode* l, RList* rules) {
     168    // start at the previously added element to gPrev, as all other elements will have the same index for sure
     169    RNode* testNode =   rules->getFirst();
     170    while(NULL != testNode->getRule()) {
     171        while(NULL != testNode->getRule() && testNode->getRuleIndex() == l->getIndex()) {
    156172            testNode = testNode->getNext();
    157173        }
    158     }
     174        if(NULL != testNode->getRule() &&
     175           pLmDivisibleByNoComp(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
     176            return true;
     177        }
     178        testNode    =   testNode->getNext();
    159179       
    160 
    161     return true;
    162 }
     180    }
     181    // 25/01/2009: TO DO -> change return value, until now no element is added to CList!
     182   
     183    return false;
     184}
     185
    163186
    164187/*
    165188==========================================================================
    166 MAIN:computes a gb of the ideal i in the ring r with our f5 implementation
     189MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
    167190==========================================================================
    168191*/
    … …  
    170193    int i,j;
    171194    // 1 polynomial for defining initial labels & further tests
    172     static poly ONE = pOne();
     195    poly ONE = pOne();
     196    // list of rules
     197    RList* rules    =   new RList();
    173198    i = 1;
    174     LList* gPrev = new LList( &ONE, &i, &id->m[0]);
     199    LList* gPrev    =   new LList( &ONE, &i, &id->m[0]);
     200    LTagList* lTag  =   new LTagList(gPrev->getFirst());
    175201    poly* lcm = new poly;
    176202    // initialization for usage in pLcm()
    … …  
    205231    pWrite(q);
    206232    for(i=2; i<=IDELEMS(id); i++) {
    207         gPrev   =   F5inc( &i, &id->m[i-1], gPrev, &ONE );
     233        gPrev   =   F5inc(&i, &id->m[i-1], gPrev, &ONE, rules, lTag);
     234        lTag->insert(gPrev->getFirst());
     235        Print("JA\n");
    208236    }
    209237    // only for debugging

  • kernel/f5gb.h

    r5376a6 r66e7b5  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.17 2009-01-28 17:20:53 Singular Exp $ */
     4/* $Id: f5gb.h,v 1.18 2009-01-29 17:59:30 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    3535==================================================
    3636*/
    37 LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE);
     37LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE, RList* rules, LTagList* lTag);
    3838
    3939/*
    … …  
    4444================================================================
    4545*/
    46 CList* criticalPair(LList* gPrev);
     46CList* criticalPair(LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag);
    4747
    4848/*
    … …  
    5151========================================
    5252*/
    53 bool criterion1(LNode* l, LList* gPrev);
     53bool criterion1(poly* t, LNode* l, LTagList* lTag);
     54
     55/*
     56=====================================
     57Criterion 2, i.e. Rewritten Criterion
     58=====================================
     59*/
     60bool criterion2(poly* t, LNode* l, RList* rules);
     61
    5462/*
    5563======================================

  • kernel/f5lists.cc

    r5376a6 r66e7b5  
    3131}
    3232       
     33LNode::LNode(LPoly* lp, LNode* l) {
     34    data = lp;
     35    next = l;
     36}
    3337LNode::LNode(poly* t, int* i, poly* p) {
    3438    LPoly* lp = new LPoly(t,i,p);
    … …  
    3741}
    3842       
    39 LNode::LNode(LNode* ln) {
     43LNode::LNode(poly* t, int* i, poly* p, LNode* l) {
     44    LPoly* lp = new LPoly(t,i,p);
     45    data = lp;
     46    next = l;
     47}
     48
     49 LNode::LNode(LNode* ln) {
    4050    data = ln->getLPoly();
    4151    next = ln->getNext();
    … …  
    4959// insert new elements to the list always in front (labeled / classical polynomial view)
    5060LNode* LNode::insert(LPoly* lp) {
    51     LNode* newElement = new LNode(lp);
    52     newElement->next = this;
     61    LNode* newElement = new LNode(lp, this);
    5362    return newElement;
    5463}
    5564       
    5665LNode* LNode::insert(poly* t, int* i, poly* p) {
    57     LNode* newElement = new LNode(t,i,p);
    58     newElement->next = this;
     66    LNode* newElement = new LNode(t, i, p, this);
    5967    return newElement;
    6068}
    … …  
    6472LNode* LNode::insertByLabel(LPoly* lp) {
    6573    if( lp->getTerm() <= this->data->getTerm() ) {
    66         LNode* newElement   =   new LNode(lp);
    67         newElement->next    =   this;
     74        LNode* newElement   =   new LNode(lp, this);
    6875        return newElement;
    6976    }
    … …  
    7279        while( NULL != temp->next ) {
    7380            if( lp->getTerm() <= temp->next->data->getTerm() ) {
    74                 LNode* newElement   =   new LNode(lp);
    75                 newElement->next    =   temp->next;
     81                LNode* newElement   =   new LNode(lp, temp->next);
    7682                temp->next          =   newElement;
    7783                return this;
    … …  
    8187            }
    8288        }
    83         LNode* newElement   =   new LNode(lp);
     89        LNode* newElement   =   new LNode(lp, NULL);
    8490        temp->next          =   newElement;
    85         newElement->next    =   NULL;
    8691        return this;
    8792    }
    … …  
    105110
    106111// get the data from the LPoly saved in LNode
    107 poly* LNode::getPoly() {
     112poly LNode::getPoly() {
    108113    return data->getPoly();
    109114}
    110115
    111 poly* LNode::getTerm() {
     116poly LNode::getTerm() {
    112117    return data->getTerm();
    113118}
    114119
    115 int* LNode::getIndex() {
     120int LNode::getIndex() {
    116121    return data->getIndex();
    117122}
    … …  
    121126    LNode* temp = new LNode(this);
    122127    while(NULL != temp) {
    123         if(pComparePolys(*(temp->getPoly()),*p)) {
     128        if(pComparePolys(temp->getPoly(),*p)) {
    124129            return 1;
    125130        }
    … …  
    182187/*
    183188=======================================
    184 functions working on the class PrevNode
    185 =======================================
    186 */
    187 
    188 PrevNode::PrevNode(LNode* l) {
     189functions working on the class LTagNode
     190=======================================
     191*/
     192
     193LTagNode::LTagNode(LNode* l) {
    189194    data = l;
    190195    next = NULL;
    191196}
    192197       
    193 PrevNode::~PrevNode() {
     198LTagNode::LTagNode(LNode* l, LTagNode* n) {
     199    data = l;
     200    next = n;
     201}
     202
     203 LTagNode::~LTagNode() {
    194204    delete next;
    195205    delete data;   
    196206}
    197207       
    198 PrevNode* PrevNode::append(LNode* l) {
    199     PrevNode* new_element = new PrevNode(l);
    200     next = new_element;
    201     return new_element;
    202 }
    203 
    204 LNode* PrevNode::getLNode() {
     208// declaration with first as parameter due to sorting of LTagList
     209LTagNode* LTagNode::insert(LNode* l) {
     210    LTagNode* newElement  = new LTagNode(l, this);
     211    return newElement;
     212}
     213
     214LNode* LTagNode::getLNode() {
    205215    return this->data;
    206216}
    207217
    208 LNode* PrevNode::getPrevLast(int i) {
    209     int j;
    210     PrevNode* temp = this;
    211     for(j=1;j<=i-1;j++) {
    212         temp = temp->next;
    213     }
    214     return temp->data;
    215 }
    216 
    217 /*
    218 =======================================
    219 functions working on the class PrevList
    220 =======================================
    221 */
    222 
    223 PrevList::PrevList(LNode* l) {
    224     PrevNode* first =   new PrevNode(l);
    225     last            =   first;   
    226 }
    227 
    228 void PrevList::append(LNode* l) {
    229     last = last->append(l);
    230 }
    231 
    232 LNode* PrevList::getPrevLast(int i) {
    233     switch(i) {
    234         case 0:     return NULL;
    235         case 1:     return first->getLNode();
    236         default:    first->getPrevLast(i);
    237     }
     218// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
     219//       Thus given actual index i and idx being the index of the LPoly under investigation
     220//       the element on position length-idx is the right one
     221LNode* LTagNode::get(int idx, int length) {
     222    if(idx == 1) {
     223        return NULL;
     224    }
     225    else {
     226        int j;
     227        LTagNode* temp = this; // last
     228        for(j=1;j<=length-idx+1;j++) {
     229            temp = temp->next;
     230        }
     231        return temp->data;
     232    }
     233}
     234
     235
     236/*
     237=======================================
     238functions working on the class LTagList
     239=======================================
     240*/
     241
     242LTagList::LTagList(LNode* l) {
     243    LTagNode* first =   new LTagNode(l);
     244    length          =   1;
     245}
     246
     247// declaration with first as parameter in LTagNode due to sorting of LTagList
     248void LTagList::insert(LNode* l) {
     249    first   =   first->insert(l);
     250    length++;
     251}
     252
     253LNode* LTagList::get(int idx) {
     254    return first->get(idx, length);
    238255}
    239256
    … …  
    243260====================================
    244261*/
     262
     263CNode::CNode() {
     264    data    =   NULL;   
     265    next    =   NULL;   
     266}
    245267
    246268CNode::CNode(CPair* c) {
    247269    data    =   c;   
    248270    next    =   NULL;   
     271}
     272
     273CNode::CNode(CPair* c, CNode* n) {
     274    data    =   c;   
     275    next    =   n;   
    249276}
    250277
    … …  
    258285// working only with linked, but not doubly linked lists due to memory usage we have to check the
    259286// insertion around the first element separately from the insertion around all other elements in the list
    260 CNode* CNode::insert(CPair* c) {
    261     if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
    262         CNode* newElement = new CNode(c);
    263         newElement->next = this;
     287CNode* CNode::insert(CPair* c, CNode* last) {
     288    if(NULL == this->data) {
     289        CNode* newElement   =   new CNode(c, this);
    264290        return newElement;
    265291    }
    266     if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
    267         if( c->getT1() <= this->data->getT1() ) {
    268             CNode* newElement   =   new CNode(c);
    269             newElement->next    =   this;
     292    else {
     293        poly u1 = ppMult_qq(c->getT1(),c->getLp1Term());
     294        if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
     295            CNode* newElement   =   new CNode(c, this);
    270296            return newElement;
    271297        }
    272         else {
    273             CNode* temp = this;
    274             while(  NULL != temp->next ) {
    275                 if( temp->next->data->getDeg() == c->getDeg() ) {
    276                     if( c->getT1() <= temp->next->data->getT1() ) {
    277                         temp = temp->next;
     298        if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
     299            if(0 == pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term())) ||
     300               -1 == pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term()))) {
     301                Print("Leck mich am Arsch: ");
     302                pWrite(u1);
     303                Print("Multi-Term in CritPairs Sortierung altes Element: ");
     304                pWrite(ppMult_qq(this->data->getT1(),this->data->getLp1Term()));
     305                CNode* newElement   =   new CNode(c, this);
     306                return newElement;
     307            }
     308            else {
     309                Print("Insert Deg\n");
     310                CNode* temp = this;
     311                while(  NULL != temp->next->data ) {
     312                    if(temp->next->data->getDeg() == c->getDeg() ) {
     313                        if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
     314                            temp = temp->next;
     315                        }
     316                        else {
     317                            CNode* newElement   =   new CNode(c, temp->next);
     318                            temp->next          =   newElement;
     319                            return this;
     320                        }
    278321                    }
    279322                    else {
    280                         CNode* newElement   =   new CNode(c);
    281                         newElement->next    =   temp->next;
     323                        CNode* newElement   =   new CNode(c, temp->next);
    282324                        temp->next          =   newElement;
    283325                        return this;
    284                     } 
     326                    }
    285327                }
    286                 else {
    287                     CNode* newElement   =   new CNode(c);
    288                     newElement->next    =   temp->next;
     328                CNode* newElement   =   new CNode(c, last);
     329                temp->next          =   newElement;
     330                return this;
     331            }
     332        } // outer if-clause
     333        if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
     334            CNode* temp =   this;
     335            while( NULL != temp->next->data ) {   
     336                if( c->getDeg() < temp->next->data->getDeg() ) {
     337                    CNode* newElement   =   new CNode(c, temp->next);
    289338                    temp->next          =   newElement;
    290339                    return this;
    291340                }
     341                if( c->getDeg() == temp->next->data->getDeg() ) {
     342                    if(0 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term())) ||
     343                       -1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
     344                        CNode* newElement   =   new CNode(c, temp->next);
     345                        temp->next          =   newElement;
     346                        return this;
     347                    }
     348                    else {
     349                        temp = temp->next;
     350                        while(  NULL != temp->next->data ) {
     351                            if( temp->next->data->getDeg() == c->getDeg() ) {
     352                                if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),
     353                                               temp->next->data->getLp1Term()))) {
     354                                    temp = temp->next;
     355                                }
     356                                else {
     357                                    CNode* newElement   =   new CNode(c, temp->next);
     358                                    temp->next          =   newElement;
     359                                    return this;
     360                                }
     361                            }
     362                            else {
     363                                CNode* newElement   =   new CNode(c, temp->next);
     364                                temp->next          =   newElement;
     365                                return this;
     366                            }
     367                        }
     368                        CNode* newElement   =   new CNode(c, last);
     369                        temp->next          =   newElement;
     370                        return this;
     371                    }
     372                }
     373                if( c->getDeg() > temp->next->data->getDeg() ) {
     374                    temp    =   temp->next;
     375                }
    292376            }
    293             CNode* newElement   =   new CNode(c);
    294             newElement->next    =   NULL;
     377            CNode* newElement   =   new CNode(c, last);
    295378            temp->next          =   newElement;
    296379            return this;
    297380        }
    298     } // outer if-clause
    299     if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
    300         CNode* temp =   this;
    301         while( NULL != temp->next ) {   
    302             if( c->getDeg() < temp->next->data->getDeg() ) {
    303                 CNode* newElement   =   new CNode(c);
    304                 newElement->next    =   temp->next;
    305                 temp->next          =   newElement;
    306                 return this;
    307             }
    308             if( c->getDeg() == temp->next->data->getDeg() ) {
    309                 if( c->getT1() <= temp->next->data->getT1() ) {
    310                     CNode* newElement   =   new CNode(c);
    311                     newElement->next    =   temp->next;
    312                     temp->next          =   newElement;
    313                     return this;
    314                 }
    315                 else {
    316                     temp = temp->next;
    317                     while(  NULL != temp->next ) {
    318                         if( temp->next->data->getDeg() == c->getDeg() ) {
    319                             if( c->getT1() <= temp->next->data->getT1() ) {
    320                                 temp = temp->next;
    321                             }
    322                             else {
    323                                 CNode* newElement   =   new CNode(c);
    324                                 newElement->next    =   temp->next;
    325                                 temp->next          =   newElement;
    326                                 return this;
    327                             }
    328                         }
    329                         else {
    330                             CNode* newElement   =   new CNode(c);
    331                             newElement->next    =   temp->next;
    332                             temp->next          =   newElement;
    333                             return this;
    334                         }
    335                     }
    336                     CNode* newElement   =   new CNode(c);
    337                     newElement->next    =   NULL;
    338                     temp->next          =   newElement;
    339                     return this;
    340                 }
    341             }
    342             if( c->getDeg() > temp->next->data->getDeg() ) {
    343                 temp    =   temp->next;
    344             }
    345         }
    346         CNode* newElement   =   new CNode(c);
    347         newElement->next    =   NULL;
    348         temp->next          =   newElement;
    349         return this;
    350381    }
    351382}
    … …  
    354385CNode* CNode::getMinDeg() {
    355386    CNode* temp = this;
    356     while( NULL != temp ) {
    357         if( temp->next->data->getDeg() == this->data->getDeg() ) {
     387    while( NULL != temp->data ) {
     388        while( temp->next->data->getDeg() == this->data->getDeg() ) {
    358389            temp = temp->next;
    359390        }
    … …  
    365396}
    366397
     398poly CNode::getLp1Poly() {
     399    return this->data->getLp1Poly();
     400}
     401
     402poly CNode::getLp2Poly() {
     403    return this->data->getLp2Poly();
     404}
     405
     406poly CNode::getLp1Term() {
     407    return this->data->getLp1Term();
     408}
     409
     410poly CNode::getLp2Term() {
     411    return this->data->getLp2Term();
     412}
     413
     414int CNode::getLp1Index() {
     415    return this->data->getLp1Index();
     416}
     417
     418int CNode::getLp2Index() {
     419    return this->data->getLp2Index();
     420}
     421
     422poly CNode::getT1() {
     423    return this->data->getT1();
     424}
     425
     426poly CNode::getT2() {
     427    return this->data->getT2();
     428}
     429
     430// for debugging
     431void CNode::print() {
     432    CNode* temp = this;
     433    Print("List of critical pairs:\n");
     434    while(NULL != temp->data) {
     435        Print("Leck mich am Arsch: ");
     436        Print("Index: %d\n",temp->getLp1Index());
     437        Print("T1: ");
     438        pWrite(temp->getT1());
     439        Print("Lp1 Term: ");
     440        pWrite(temp->getLp1Term());
     441        Print("%d\n",temp->getLp2Index());
     442        pWrite(temp->getT2());
     443        pWrite(temp->getLp2Term());
     444        Print("\n");
     445        temp = temp->next;
     446    }
     447}
    367448
    368449/*
    … …  
    371452====================================
    372453*/
     454// for initialization of CLists, last element alwas has data=NULL and next=NULL
     455CList::CList() {
     456    first   =   new CNode();
     457    last    =   first;
     458}
     459
    373460CList::CList(CPair* c) {
    374     first   = new CNode(c);
     461    first   =   new CNode(c);
     462    last    =   first;
    375463}
    376464
    … …  
    382470// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
    383471void CList::insert(CPair* c) {
    384     first = first->insert(c);
     472    first = first->insert(c, last);
    385473}
    386474
    … …  
    393481}
    394482
     483void CList::print() {
     484    first->print();
     485}
    395486
    396487/*
    … …  
    399490====================================
    400491*/
     492RNode::RNode() {
     493    data    =   NULL;
     494    next    =   NULL;
     495}
     496
    401497RNode::RNode(Rule* r) {
    402498    data    =   r;
    … …  
    415511}
    416512
     513RNode* RNode::getNext() {
     514    return next;
     515}   
     516
     517Rule* RNode::getRule() {
     518    return data;
     519}
     520
     521int RNode::getRuleIndex() {
     522    return data->getIndex();
     523}
     524
     525poly RNode::getRuleTerm() {
     526    return data->getTerm();
     527}
     528
    417529/*
    418530====================================
    … …  
    420532====================================
    421533*/
     534RList::RList() {
     535    first = new RNode();
     536}
     537
    422538RList::RList(Rule* r) {
    423539    first = new RNode(r);
    … …  
    427543    first = first->insert(r);
    428544}
     545
     546RNode* RList::getFirst() {
     547    return first;
     548}
     549
     550Rule* RList::getRule() {
     551    return this->getRule();
     552}
     553
     554/*
     555=======================================
     556functions working on the class RTagNode
     557=======================================
     558*/
     559
     560RTagNode::RTagNode(RNode* r) {
     561    data = r;
     562    next = NULL;
     563}
     564       
     565RTagNode::RTagNode(RNode* r, RTagNode* n) {
     566    data = r;
     567    next = n;
     568}
     569
     570 RTagNode::~RTagNode() {
     571    delete next;
     572    delete data;   
     573}
     574       
     575// declaration with first as parameter due to sorting of LTagList
     576RTagNode* RTagNode::insert(RNode* r) {
     577    Print("Hier1\n");
     578    RTagNode* newElement  = new RTagNode(r, this);
     579    Print("Hier2\n");
     580    return newElement;
     581}
     582
     583RNode* RTagNode::getRNode() {
     584    return this->data;
     585}
     586
     587// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
     588//       Thus given actual index i and idx being the index of the LPoly under investigation
     589//       the element on position length-idx+1 is the right one
     590RNode* RTagNode::get(int idx, int length) {
     591    if(idx == 1) {
     592        return NULL;
     593    }
     594    else {
     595        int j;
     596        RTagNode* temp = this;
     597        for(j=1;j<=length-idx+1;j++) {
     598            temp = temp->next;
     599        }
     600        return temp->data;
     601    }
     602}
     603
     604
     605/*
     606=======================================
     607functions working on the class LTagList
     608=======================================
     609*/
     610
     611RTagList::RTagList(RNode* r) {
     612    RTagNode* first =   new RTagNode(r);
     613    length          =   1;
     614}
     615
     616// declaration with first as parameter in LTagNode due to sorting of LTagList
     617void RTagList::insert(RNode* r) {
     618    first = first->insert(r);
     619    length++;
     620}
     621
     622RNode* RTagList::get(int idx) {
     623    return first->get(idx, length);
     624}
    429625#endif

  • kernel/f5lists.h

    r5376a6 r66e7b5  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5lists.h,v 1.1 2009-01-27 10:38:08 Singular Exp $ */
     4/* $Id: f5lists.h,v 1.2 2009-01-29 17:59:30 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    2020class LNode;
    2121class LList;
    22 class PrevNode;
    23 class PrevList;
     22class LTagNode;
     23class LTagList;
    2424class CNode;
    2525class CList;
    2626class RList;
    2727class RNode;
    28 
    29 /*
    30 =======================================
    31 LNode class (nodes for lists of LPolys)
     28class RTagNode;
     29class RTagList;
     30
     31
     32/*
     33=======================================
     34class LNode (nodes for lists of LPolys)
    3235=======================================
    3336*/
    … …  
    3942        // generating new list elements from the labeled / classical polynomial view
    4043                LNode(LPoly* lp);
     44                LNode(LPoly* lp, LNode* l);
    4145                LNode(poly* t, int* i, poly* p);
     46                LNode(poly* t, int* i, poly* p, LNode* l);
    4247                LNode(LNode* ln);
    4348                ~LNode();
    … …  
    5661        LPoly*  getLPoly();
    5762        // get the data from the LPoly saved in LNode
    58         poly*   getPoly();
    59         poly*   getTerm();
    60         int*    getIndex();
     63        poly    getPoly();
     64        poly    getTerm();
     65        int     getIndex();
    6166        // test if for any list element the polynomial part of the data is equal to *p
    6267        bool    polyTest(poly* p);
    … …  
    8994
    9095/*
    91 =============================================
    92 PrevNode class (nodes for lists of gPrevLast)
    93 =============================================
    94 */
    95 class PrevNode {
     96==============================================
     97class LtagNode (nodes for lists of LPoly tags)
     98==============================================
     99*/
     100class LTagNode {
    96101    private:
    97102        LNode*      data;
    98         PrevNode*   next;
    99     public:
    100         PrevNode(LNode* l);
    101         ~PrevNode();
    102         PrevNode*   append(LNode* l);
     103        LTagNode*   next;
     104    public:
     105        LTagNode(LNode* l);
     106        LTagNode(LNode* l, LTagNode* n);
     107        ~LTagNode();
     108        // declaration with first as parameter due to sorting of LTagList
     109        LTagNode*   insert(LNode* l);
    103110        LNode*      getLNode();
    104         LNode*      getPrevLast(int i);
    105 };
    106 
    107 
    108 /*
    109 ====================================================
    110 class PrevList(lists of last node elements in gPrev)
    111 ====================================================
    112 */
    113 class PrevList {
    114     private:
    115         PrevNode*   first;
    116         PrevNode*   last;
    117     public:
    118                 PrevList(LNode* l);
    119                 ~PrevList();
    120         void    append(LNode* l);
    121         LNode*  getPrevLast(int i);
     111        LNode*      get(int i, int length);
     112};
     113
     114
     115/*
     116=========================================================================
     117class LTagList(lists of LPoly tags, i.e. first elements of a given index)
     118=========================================================================
     119*/
     120class LTagList {
     121    private:
     122        LTagNode*   first;
     123        int         length;
     124    public:
     125                LTagList(LNode* l);
     126                ~LTagList();
     127        // declaration with first as parameter in LTagNode due to sorting of LTagList
     128        void    insert(LNode* l);
     129        LNode*  get(int idx);
    122130};
    123131
    … …  
    133141        CNode* next;
    134142    public:
     143                CNode();
    135144                CNode(CPair* c);
     145                CNode(CPair* c, CNode* n);
    136146                ~CNode();
    137         CNode*  insert(CPair* c);
     147        CNode*  insert(CPair* c, CNode* last);
    138148        CNode*  getMinDeg();
    139         //CNode*  getLPoly() const;
     149        poly    getLp1Poly();
     150        poly    getLp2Poly();
     151        poly    getLp1Term();
     152        poly    getLp2Term();
     153        poly    getT1();   
     154        poly    getT2();
     155        int     getLp1Index();
     156        int     getLp2Index();
     157        void    print();
    140158};
    141159
    … …  
    149167    private:
    150168        CNode*  first;
    151     public:
     169        // last alway has data=NULL and next=NULL, for initialization purposes used
     170        CNode*  last;
     171    public:
     172                // for initialization of CLists, last element alwas has data=NULL and next=NULL
     173                CList();
    152174                CList(CPair* c);
    153175                ~CList();
    154176        void    insert(CPair* c);
    155177        CNode*  getMinDeg();
    156 
     178        void    print();
    157179};
    158180
    … …  
    168190        RNode*  next;
    169191    public:
     192                RNode();
    170193                RNode(Rule* r);
    171194                ~RNode();
    172195        RNode*  insert(Rule* r);
     196        RNode*  getNext();
     197        Rule*   getRule();
     198        int     getRuleIndex();
     199        poly    getRuleTerm();
    173200};
    174201
    … …  
    181208    private:
    182209        RNode*  first;
    183     public:
     210        // last alway has data=NULL and next=NULL, for initialization purposes used
     211        RNode*  last;
     212    public:
     213                RList();
    184214                RList(Rule* r);
    185215                ~RList();
    186216        void    insert(Rule* r);
     217        RNode*  getFirst();
     218        Rule*   getRule();
     219};
     220
     221
     222
     223/*
     224=============================================
     225class RtagNode (nodes for lists of Rule tags)
     226=============================================
     227*/
     228class RTagNode {
     229    private:
     230        RNode*      data;
     231        RTagNode*   next;
     232    public:
     233        RTagNode(RNode* r);
     234        RTagNode(RNode* r, RTagNode* n);
     235        ~RTagNode();
     236        // declaration with first as parameter due to sorting of LTagList
     237        RTagNode*   insert(RNode* r);
     238        RNode*      getRNode();
     239        RNode*      get(int idx, int length);
     240};
     241
     242
     243/*
     244========================================================================
     245class RTagList(lists of Rule tags, i.e. first elements of a given index)
     246========================================================================
     247*/
     248class RTagList {
     249    private:
     250        RTagNode*   first;
     251        int         length;
     252    public:
     253                RTagList(RNode* r);
     254                ~RTagList();
     255        // declaration with first as parameter in LTagNode due to sorting of LTagList
     256        void    insert(RNode* r);
     257        RNode*  get(int idx);
    187258};
    188259#endif

  • kernel/lpolynomial.cc

    r5376a6 r66e7b5  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lpolynomial.cc,v 1.7 2009-01-28 17:21:07 Singular Exp $ */
     4/* $Id: lpolynomial.cc,v 1.8 2009-01-29 17:59:30 ederc Exp $ */
    55/*
    66* ABSTRACT: lpolynomial definition
    … …  
    5050}
    5151
    52 poly* LPoly::getPoly() {
    53     return &polynomial;
     52poly LPoly::getPoly() {
     53    return polynomial;
    5454}
    5555
    56 poly* LPoly::getTerm() {
    57     return &term;
     56poly LPoly::getTerm() {
     57    return term;
    5858}
    5959
    60 int* LPoly::getIndex() {
    61     return &index;
     60int LPoly::getIndex() {
     61    return index;
    6262}
    6363
    … …  
    8282*/
    8383CPair::CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2) {
    84    deg  =   degree;
    85    t1   =   term1;
    86    lp1  =   lpoly1;
    87    t2   =   term2;
    88    lp2  =   lpoly2;
     84   deg              =   degree;
     85   t1               =   term1;
     86   lp1              =   lpoly1;
     87   t2               =   term2;
     88   lp2              =   lpoly2;
     89   lastRuleTested   =   NULL;
    8990}
    9091
    … …  
    102103
    103104poly CPair::getLp1Poly() {
    104     return *(lp1->getPoly());
     105    return lp1->getPoly();
    105106}
    106107
    107108poly CPair::getLp2Poly() {
    108     return *(lp2->getPoly());
     109    return lp2->getPoly();
    109110}
    110111
    111112poly CPair::getLp1Term() {
    112     return *(lp1->getTerm());
     113    return lp1->getTerm();
    113114}
    114115
    115116poly CPair::getLp2Term() {
    116     return *(lp2->getTerm());
     117    return lp2->getTerm();
    117118}
    118119
    119120int CPair::getLp1Index() {
    120     return *(lp1->getIndex());
     121    return lp1->getIndex();
    121122}
    122123
    123 
    124124int CPair::getLp2Index() {
    125     return *(lp2->getIndex());
     125    return lp2->getIndex();
    126126}
    127127
     128Rule* CPair::getLastRuleTested() {
     129    return lastRuleTested;
     130}
    128131
    129132/*

  • kernel/lpolynomial.h

    r5376a6 r66e7b5  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lpolynomial.h,v 1.6 2009-01-25 17:13:06 ederc Exp $ */
     4/* $Id: lpolynomial.h,v 1.7 2009-01-29 17:59:30 ederc Exp $ */
    55/*
    66* ABSTRACT: labeled polynomial interface
    … …  
    88#ifndef LPOLYNOMIAL_HEADER
    99#define LPOLYNOMIAL_HEADER
    10 
    1110#ifdef HAVE_F5
    1211/*
    … …  
    3635                LPoly(poly*t,int* i,poly* p);
    3736        void    setPoly(poly* p);
    38         poly*   getPoly();
     37        poly    getPoly();
    3938        void    setTerm(poly* t);
    40         poly*   getTerm();
     39        poly    getTerm();
    4140        void    setIndex(int* i);
    42         int*    getIndex();
     41        int     getIndex();
    4342        void    setDel(bool b);
    4443        bool    getDel() const;
    … …  
    4645        LPoly*  get();
    4746};
    48 
    49 
    50 /*
    51 ===================================
    52 structure of labeled critical pairs
    53 ===================================
    54 */
    55 class CPair {
    56     private:
    57         long    deg;    // total degree of the critical pair
    58         poly    t1;     // first term for label
    59         LPoly*  lp1;     // first labeled poly
    60         poly    t2;     // second term for label
    61         LPoly*  lp2;     // second labeled poly
    62     public:
    63                 CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
    64         long    getDeg();
    65         poly    getT1();
    66         poly    getLp1Poly();
    67         poly    getLp1Term();
    68         int     getLp1Index();
    69         poly    getT2();
    70         poly    getLp2Poly();
    71         poly    getLp2Term();
    72         int     getLp2Index();
    73 };
    74 
    7547
    7648/*
    … …  
    8860        poly    getTerm();
    8961};
     62
     63
     64/*
     65===================================
     66structure of labeled critical pairs
     67===================================
     68*/
     69class CPair {
     70    private:
     71        long    deg;            // total degree of the critical pair
     72        poly    t1;             // first term for label
     73        LPoly*  lp1;            // first labeled poly
     74        poly    t2;             // second term for label
     75        LPoly*  lp2;            // second labeled poly
     76        Rule*   lastRuleTested; // already tested by rules up to lastRuleTested
     77    public:
     78                CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
     79        long    getDeg();
     80        poly    getT1();
     81        poly    getLp1Poly();
     82        poly    getLp1Term();
     83        int     getLp1Index();
     84        poly    getT2();
     85        poly    getLp2Poly();
     86        poly    getLp2Term();
     87        int     getLp2Index();
     88        Rule*   getLastRuleTested();
     89};
     90
    9091#endif
    9192#endif
Note: See TracChangeset for help on using the changeset viewer.