Changeset 66e7b5 in git for kernel/f5lists.cc


Ignore:
Timestamp:
Jan 29, 2009, 6:59:30 PM (14 years ago)
Author:
Christian Eder
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'f875bbaccd0831e36aaed09ff6adeb3eb45aeb94')
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
File:
1 edited

Legend:

Unmodified
Added
Removed

  • 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
Note: See TracChangeset for help on using the changeset viewer.