source: git/kernel/GBEngine/f5lists.cc @ 4f8fd1d

spielwiese
Last change on this file since 4f8fd1d was 4f8fd1d, checked in by Frédéric Chapoton <chapoton@…>, 17 months ago
trying to add a codespell linter for kernel/
  • Property mode set to 100644
File size: 29.6 KB
RevLine 
[9f7665]1
2
3
[89f4843]4#include "kernel/mod2.h"
[71f00c5]5
[ae5177]6#ifdef HAVE_F5
[89f4843]7#include "kernel/GBEngine/kutil.h"
8#include "kernel/structs.h"
9#include "kernel/polys.h"
10#include "polys/monomials/p_polys.h"
11#include "kernel/ideals.h"
12#include "kernel/GBEngine/kstd1.h"
13#include "kernel/GBEngine/khstd.h"
14#include "polys/kbuckets.h"
15#include "polys/weight.h"
16#include "misc/intvec.h"
17#include "kernel/polys.h"
18#include "kernel/GBEngine/f5gb.h"
19#include "kernel/GBEngine/f5data.h"
20#include "kernel/GBEngine/f5lists.h"
[71f00c5]21
[ab76b4]22/**
23 * functions working on the class PNode
24 */
25PNode::PNode(poly p, PNode* n) {
26  data  = p;
27  next  = n;
28}
29
30poly PNode::getPoly() {
31  return this->data;
32}
33
34PNode* PNode::getNext() {
35  return this->next;
36}
37PNode* PNode::insert(poly p) {
38  poly q = pOne();
[a9c298]39  q = pCopy(p);
[ab76b4]40  PNode* temp = this;
41  if(NULL == temp) {
42    PNode* pn = new PNode(q,temp);
43    return pn;
44  }
45  if(1 == pLmCmp(q,temp->getPoly())) {
46    PNode* pn = new PNode(q,temp);
47    return pn;
48  }
49  if(0 == pLmCmp(q,temp->getPoly())) {
50    return this;
51  }
52  if(-1 == pLmCmp(q,temp->getPoly())) {
53    while(NULL != temp->getNext() && -1 == pLmCmp(q,temp->getNext()->getPoly())) {
54      temp = temp->getNext();
55    }
56    if(NULL == temp->getNext() || 1 == pLmCmp(q,temp->getNext()->getPoly())) {
57      PNode* pn = new PNode(q,temp->getNext());
58      temp->next = pn;
59      return this;
60    }
61    if(0 == pLmCmp(q,temp->getNext()->getPoly())) {
62      return this;
63    }
64  }
65}
66/*
67PNode* PNode::insert(poly p) {
68  PNode* pn = new PNode(p,this);
69  return pn;
70}
71*/
72/**
73 * functions working on the class PList
74 */
75PList::PList() {
76  first = NULL;
77}
78
79
80void PList::insert(poly p) {
81  first = first->insert(p);
82}
[a9c298]83
[ab76b4]84
85/*
86PNode* PList::insert(poly p) {
87  PNode* temp = first;
88  PNode* pn   = new PNode(p,temp);
89  first       = pn;
90  return first;
91}
92*/
93bool PList::check(poly p) {
94  PNode* temp = first;
95  //Print("\nCHECK: \n");
96  //pWrite(p);
97  //Print("-----\n");
98  while(NULL != temp) {
99    //pWrite(temp->getPoly());
100    //pWrite(p);
[4f8fd1d]101    //Print("COMPARE: %d\n",pLmEqual(p,temp->getPoly()));
[ab76b4]102    if(1 == pLmEqual(p,temp->getPoly())) {
103      //Print("YES!\n");
104      //pWrite(pHead(temp->getPoly()));
105      //Print("YES!\n");
106      return 1;
107    }
108    temp = temp->getNext();
109  }
110  //Print("NOTHING!\n");
111  return 0;
112}
113
114void PList::print() {
115  Print("-----LIST-----\n");
116  PNode* temp = first;
117  while(NULL != temp) {
118    pWrite(temp->getPoly());
119    temp = temp->getNext();
120  }
121}
[71f00c5]122/*
123====================================
124functions working on the class LNode
125====================================
126*/
127
[a0350e9]128// generating new list elements (labeled / classical polynomial / LNode view)
[9bb97e]129LNode::LNode() {
[87beab7]130    data                =   NULL;
131    next                =   NULL;
[9bb97e]132}
[a05c71]133LNode::LNode(LPolyOld* lp) {
[87beab7]134    data                =   lp;
135    next                =   NULL;
[71f00c5]136}
[a9c298]137
[a05c71]138LNode::LNode(LPolyOld* lp, LNode* l) {
[598870]139//Print("HIER LNODE\n");
[87beab7]140    data                =   lp;
141    next                =   l;
[66e7b5]142}
[87beab7]143
[a05c71]144LNode::LNode(poly t, int i, poly p, RuleOld* r) {
145LPolyOld* lp           =   new LPolyOld(t,i,p,r);
[87beab7]146data                =   lp;
147next                =   NULL;
[71f00c5]148}
[a9c298]149
[a05c71]150LNode::LNode(poly t, int i, poly p, RuleOld* r, LNode* l) {
151    LPolyOld* lp           =   new LPolyOld(t,i,p,r);
[87beab7]152    data                =   lp;
153    next                =   l;
[66e7b5]154}
155
[9cb4078]156LNode::LNode(LNode* ln) {
[a05c71]157    data                =   ln->getLPolyOld();
[87beab7]158    next                =   ln->getNext();
[71f00c5]159}
[a9c298]160
[71f00c5]161LNode::~LNode() {
[416ea2]162    //delete next;
[55a828]163    //Print("DELETE LNODE\n");
[a9c298]164    delete data;
[71f00c5]165}
[338842d]166
167void LNode::deleteAll() {
168    while(NULL != next) {
[55a828]169        //Print("%p\n",next);
170        //pWrite(next->data->getPoly());
[338842d]171        next->deleteAll();
172    }
173    delete data;
174}
175
[d51339]176// insert new elements to the list always at the end (labeled / classical polynomial view)
177// needed for list gPrev
[a05c71]178inline LNode* LNode::insert(LPolyOld* lp) {
[598870]179    //Print("LAST GPREV: ");
180    //pWrite(this->getPoly());
[e3b5ed]181    if(NULL == this) {
182        LNode* newElement   =   new LNode(lp,this);
183        return newElement;
184    }
185    else {
186        LNode* newElement   =   new LNode(lp, NULL);
187        this->next          =   newElement;
188        return newElement;
189    }
[71f00c5]190}
[a9c298]191
[a05c71]192inline LNode* LNode::insert(poly t, int i, poly p, RuleOld* r) {
[e3b5ed]193    if(NULL == this) {
194        LNode* newElement   =   new LNode(t,i,p,r,this);
195        return newElement;
196    }
197    else {
198        LNode* newElement   =   new LNode(t, i, p, r, NULL);
199        this->next          =   newElement;
200        return newElement;
201    }
[71f00c5]202}
[416ea2]203
[d51339]204// insert new elements to the list always in front (labeled / classical polynomial view)
205// needed for sPolyList
[a05c71]206inline LNode* LNode::insertSP(LPolyOld* lp) {
[d51339]207    LNode* newElement   =   new LNode(lp, this);
[c9193a]208    //Print("INSERTED IN SPOLYLIST: ");
209    //pWrite(lp->getTerm());
[d51339]210    return newElement;
211}
[a9c298]212
[a05c71]213inline LNode* LNode::insertSP(poly t, int i, poly p, RuleOld* r) {
[338842d]214    LNode* newElement   =   new LNode(t, i, p, r, this);
[c9193a]215     //Print("INSERTED IN SPOLYLIST: ");
216  //pWrite(t);
[8066e80]217return newElement;
[416ea2]218}
[4f8fd1d]219// insert new elements to the list w.r.t. increasing labels
[cce6ed3]220// only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
[a05c71]221inline LNode* LNode::insertByLabel(poly t, int i, poly p, RuleOld* r) {
[c9193a]222    //Print("ADDING SOLYS TO THE LIST\n");
223    //Print("new element: ");
224    //pWrite(t);
[c4158f]225       if(NULL == this) { // || NULL == data) {
[338842d]226        LNode* newElement   =   new LNode(t, i, p, r, this);
[cce6ed3]227        return newElement;
228    }
229    else {
[c9193a]230         //Print("tested element1: ");
231    //pWrite(this->getTerm());
[61944d0]232        if(-1 == pLmCmp(t,this->getTerm())) {
[c9193a]233            //Print("HIERDRIN\n");
[338842d]234            LNode* newElement   =   new LNode(t, i, p, r, this);
[c9193a]235            //Print("%p\n",this);
236            //Print("%p\n",newElement->next);
[70c15e]237            return newElement;
238        }
239        else {
240            LNode* temp = this;
241            while(NULL != temp->next && NULL != temp->next->data) {
[c9193a]242                //Print("tested element: ");
243                //pWrite(temp->getTerm());
[8066e80]244 if(-1 == pLmCmp(t,temp->next->getTerm())) {
[338842d]245                    LNode* newElement   =   new LNode(t, i, p, r, temp->next);
[70c15e]246                    temp->next          =   newElement;
247                    return this;
248                }
249                else {
250                    temp = temp->next;
[598870]251                    //Print("%p\n",temp);
252                    //Print("%p\n",temp->data);
[a9c298]253
[598870]254                    //Print("%p\n",temp->next);
[70c15e]255                }
[cce6ed3]256            }
[598870]257        //Print("HIER\n");
[338842d]258            LNode* newElement   =   new LNode(t, i, p, r, temp->next);
[70c15e]259            temp->next          =   newElement;
260            return this;
[cce6ed3]261        }
262    }
263}
264
[f16a76d]265inline LNode* LNode::insertFirst(LNode* l) {
266    l->next =   this;
267    return l;
268}
269
[e90881]270inline LNode* LNode::insertByLabel(LNode* l) {
[f16a76d]271    //Print("ADDING SOLYS TO THE LIST\n");
[e90881]272    //Print("new element: ");
273    //pWrite(t);
274       if(NULL == this) { // || NULL == data) {
275        l->next =   this;
276        return l;
277    }
278    else {
279         //Print("tested element1: ");
280    //pWrite(this->getTerm());
281        if(-1 == pLmCmp(l->getTerm(),this->getTerm())) {
282            //Print("HIERDRIN\n");
283            l->next =   this;
284            //Print("%p\n",this);
285            //Print("%p\n",newElement->next);
286            return l;
287        }
288        else {
289            LNode* temp = this;
290            while(NULL != temp->next && NULL != temp->next->data) {
291                //Print("tested element: ");
292                //pWrite(temp->getTerm());
293                if(-1 == pLmCmp(l->getTerm(),temp->next->getTerm())) {
294                    l->next     =   temp->next;
295                    temp->next  =   l;
296                    return this;
297                }
298                else {
299                    temp = temp->next;
300                    //Print("%p\n",temp);
301                    //Print("%p\n",temp->data);
[a9c298]302
[e90881]303                    //Print("%p\n",temp->next);
304                }
305            }
306        //Print("HIER\n");
307            l->next     =   temp->next;
308            temp->next  =   l;
309            return this;
310        }
311    }
312}
313
[cce6ed3]314// deletes the first elements of the list with the same degree
[0179d5]315// only used for the S-polys, which are already sorted by increasing degree by CListOld
[cce6ed3]316LNode*  LNode::deleteByDeg() {
317    return this;
318}
319
[71f00c5]320// get next from current LNode
321LNode* LNode::getNext() {
322    return next;
323}
[d51339]324
[a05c71]325// get the LPolyOld* out of LNode*
326LPolyOld* LNode::getLPolyOld() {
[71f00c5]327    return data;
328}
329
[a05c71]330// get the data from the LPolyOld saved in LNode
[66e7b5]331poly LNode::getPoly() {
[71f00c5]332    return data->getPoly();
333}
334
[66e7b5]335poly LNode::getTerm() {
[cce6ed3]336    return data->getTerm();
337}
338
[66e7b5]339int LNode::getIndex() {
[cce6ed3]340    return data->getIndex();
341}
342
[a05c71]343RuleOld* LNode::getRuleOld() {
344    return data->getRuleOld();
[87beab7]345}
346
[a05c71]347void LNode::setRuleOld(RuleOld* r) {
348    return data->setRuleOld(r);
[c3efd3b]349}
350
[e90881]351bool LNode::getDel() {
352    return data->getDel();
353}
354
[a05c71]355// set the data from the LPolyOld saved in LNode
[9bb97e]356void LNode::setPoly(poly p) {
357    data->setPoly(p);
358}
359
360void LNode::setTerm(poly t) {
361    data->setTerm(t);
362}
363
364void LNode::setIndex(int i) {
365    data->setIndex(i);
366}
367
[61944d0]368void LNode::setNext(LNode* l) {
369    next    =   l;
370}
371
[e90881]372void LNode::setDel(bool d) {
373    data->setDel(d);
374}
375
[71f00c5]376// test if for any list element the polynomial part of the data is equal to *p
[a0350e9]377bool LNode::polyTest(poly* p) {
[71f00c5]378    LNode* temp = new LNode(this);
379    while(NULL != temp) {
[66e7b5]380        if(pComparePolys(temp->getPoly(),*p)) {
[71f00c5]381            return 1;
382        }
383        temp = temp->next;
384    }
385    return 0;
386}
387
[cce6ed3]388LNode* LNode::getNext(LNode* l) {
389    return l->next;
390}
[71f00c5]391
[d51339]392// for debugging
[f9b0bd]393void LNode::print()
394{
[d51339]395    LNode* temp = this;
[f9b0bd]396    PrintS("___________________List of S-polynomials______________________:\n");
[70c15e]397    while(NULL != temp && NULL != temp->data) {
[d51339]398        Print("Index: %d\n",temp->getIndex());
[f9b0bd]399        PrintS("Term: ");
[61944d0]400        pWrite(temp->getTerm());
[f9b0bd]401        PrintS("Poly: ");
[61944d0]402        pWrite(temp->getPoly());
[d51339]403        temp = temp->next;
404    }
[f9b0bd]405    PrintS("_______________________________________________________________\n");
[d51339]406}
407
[e90881]408int LNode::count(LNode* l) {
409    int nonDel  =   0;
410    LNode* temp =   l;
411    while(NULL != temp) {
412        if(!temp->getDel()) {
413            nonDel++;
414            temp    =   temp->next;
415        }
416        else {
417            temp    =   temp->next;
418        }
419    }
420    return nonDel;
421}
[d51339]422
[71f00c5]423/*
424====================================
425functions working on the class LList
426====================================
427*/
428
[9bb97e]429LList::LList() {
[c4158f]430    first   =   last    =   NULL;;
[9bb97e]431    length  =   0;
432}
433
[a05c71]434LList::LList(LPolyOld* lp) {
[9bb97e]435    first   =   new LNode(lp);
[416ea2]436    last    =   first;
[9bb97e]437    length  =   1;
[71f00c5]438}
439
[a05c71]440LList::LList(poly t,int i,poly p,RuleOld* r) {
[87beab7]441    first   =   new LNode(t,i,p,r);
[416ea2]442    last    =   first;
[9bb97e]443    length  =   1;
[a9c298]444}
[71f00c5]445
446LList::~LList() {
[338842d]447    LNode* temp;
448    while(first) {
449        temp    =   first;
450        first   =   first->getNext();
451        delete  temp;
[55a828]452        //Print("%p\n",first);
[338842d]453    }
[71f00c5]454}
455
[d51339]456// insertion at the end of the list, needed for gPrev
[a05c71]457void LList::insert(LPolyOld* lp) {
[d51339]458    last = last->insert(lp);
[e3b5ed]459    if(NULL == first) {
460        first   =   last;
461    }
[598870]462    //Print("NEW LAST GPREV: ");
463    //pWrite(last->getPoly());
[e3b5ed]464    //Print("%p\n",first);
465    //pWrite(first->getPoly());
[9bb97e]466    length++;
[598870]467    //Print("LENGTH %d\n",length);
[71f00c5]468}
469
[a05c71]470void LList::insert(poly t,int i, poly p, RuleOld* r) {
[d51339]471    last = last->insert(t,i,p,r);
[e3b5ed]472    if(NULL == first) {
473        first   =   last;
474    }
[d51339]475    length++;
[598870]476    //Print("LENGTH %d\n",length);
[d51339]477}
478
479// insertion in front of the list, needed for sPolyList
[a05c71]480void LList::insertSP(LPolyOld* lp) {
[d51339]481    first = first->insertSP(lp);
[87beab7]482    length++;
[598870]483    //Print("LENGTH %d\n",length);
[87beab7]484}
485
[a05c71]486void LList::insertSP(poly t,int i, poly p, RuleOld* r) {
[d51339]487    first = first->insertSP(t,i,p,r);
[416ea2]488    length++;
[598870]489    //Print("LENGTH %d\n",length);
[416ea2]490}
491
[d51339]492
[a05c71]493void LList::insertByLabel(poly t, int i, poly p, RuleOld* r) {
[87beab7]494    first = first->insertByLabel(t,i,p,r);
[9bb97e]495    length++;
[598870]496    //Print("LENGTH %d\n",length);
[71f00c5]497}
498
[f16a76d]499void LList::insertFirst(LNode* l) {
500    first = first->insertFirst(l);
501    length++;
502    //Print("LENGTH %d\n",length);
503}
504
[87beab7]505void LList::insertByLabel(LNode* l) {
[e90881]506    first = first->insertByLabel(l);
[9bb97e]507    length++;
[598870]508    //Print("LENGTH %d\n",length);
[71f00c5]509}
510
[cce6ed3]511void LList::deleteByDeg() {
512    first = first->deleteByDeg();
513}
514
515bool LList::polyTest(poly* p) {
516    return first->polyTest(p);
[71f00c5]517}
518
519LNode* LList::getFirst() {
520    return first;
521}
522
[416ea2]523LNode* LList::getLast() {
524    return last;
525}
526
[9bb97e]527int LList::getLength() {
528    return length;
529}
530
[fcb8022]531void LList::setFirst(LNode* l) {
[61944d0]532    LNode* temp =   first;
533    temp->setNext(NULL);
[fcb8022]534    first       =   l;
[416ea2]535    length--;
[fcb8022]536}
537
[d51339]538void LList::print() {
539    first->print();
540}
[fcb8022]541
[e90881]542int LList::count(LNode* l) {
543    return first->count(l);
544}
[a0350e9]545/*
546=======================================
[66e7b5]547functions working on the class LTagNode
[a0350e9]548=======================================
549*/
[87beab7]550LTagNode::LTagNode() {
551    data    =   NULL;
552    next    =   NULL;
553}
[a0350e9]554
[66e7b5]555LTagNode::LTagNode(LNode* l) {
[a0350e9]556    data = l;
557    next = NULL;
558}
[a9c298]559
[66e7b5]560LTagNode::LTagNode(LNode* l, LTagNode* n) {
561    data = l;
562    next = n;
563}
564
565 LTagNode::~LTagNode() {
[a9c298]566    delete data;
[a0350e9]567}
[a9c298]568
[66e7b5]569// declaration with first as parameter due to sorting of LTagList
570LTagNode* LTagNode::insert(LNode* l) {
571    LTagNode* newElement  = new LTagNode(l, this);
572    return newElement;
[a0350e9]573}
574
[66e7b5]575LNode* LTagNode::getLNode() {
[a0350e9]576    return this->data;
577}
578
[d51339]579LTagNode* LTagNode::getNext() {
580    return next;
581}
582
[66e7b5]583// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
[a05c71]584//       Thus given actual index i and idx being the index of the LPolyOld under investigation
[66e7b5]585//       the element on position length-idx is the right one
586LNode* LTagNode::get(int idx, int length) {
587    if(idx == 1) {
588        return NULL;
589    }
590    else {
591        int j;
592        LTagNode* temp = this; // last
593        for(j=1;j<=length-idx+1;j++) {
594            temp = temp->next;
595        }
596        return temp->data;
[a0350e9]597    }
598}
599
[66e7b5]600
[a0350e9]601/*
602=======================================
[66e7b5]603functions working on the class LTagList
[a0350e9]604=======================================
605*/
[87beab7]606LTagList::LTagList() {
607    LTagNode* first =   new LTagNode();
[a9c298]608
[87beab7]609    length          =   0;
610}
[a0350e9]611
[66e7b5]612LTagList::LTagList(LNode* l) {
613    LTagNode* first =   new LTagNode(l);
614    length          =   1;
[a0350e9]615}
616
[6b0aa2]617LTagList::~LTagList() {
618    LTagNode* temp;
619    while(first) {
620        temp    =   first;
621        first   =   first->getNext();
622        delete  temp;
623        //Print("%p\n",first);
624    }
625}
626
[66e7b5]627// declaration with first as parameter in LTagNode due to sorting of LTagList
628void LTagList::insert(LNode* l) {
629    first   =   first->insert(l);
630    length++;
[a0350e9]631}
632
[d51339]633void LTagList::setFirstCurrentIdx(LNode* l) {
634    firstCurrentIdx =   l;
635}
636
[66e7b5]637LNode* LTagList::get(int idx) {
638    return first->get(idx, length);
[a0350e9]639}
640
[87beab7]641LNode* LTagList::getFirst() {
642    return first->getLNode();
643}
644
[d51339]645LNode* LTagList::getFirstCurrentIdx() {
646    return firstCurrentIdx;
647}
[87beab7]648
649/*
650=====================================
651functions working on the class TopRed
652=====================================
653*/
654
655TopRed::TopRed() {
656    _completed  =   NULL;
657    _toDo       =   NULL;
658}
659
660TopRed::TopRed(LList* c, LList* t) {
661    _completed  =   c;
662    _toDo       =   t;
663}
664
665LList* TopRed::getCompleted() {
666    return _completed;
667}
668
669LList* TopRed::getToDo() {
670    return _toDo;
671}
672
[a0350e9]673/*
674====================================
675functions working on the class CNode
676====================================
677*/
678
[66e7b5]679CNode::CNode() {
[a9c298]680    data    =   NULL;
681    next    =   NULL;
[66e7b5]682}
683
[0179d5]684CNode::CNode(CPairOld* c) {
[a9c298]685    data    =   c;
686    next    =   NULL;
[a0350e9]687}
688
[0179d5]689CNode::CNode(CPairOld* c, CNode* n) {
[a9c298]690    data    =   c;
691    next    =   n;
[66e7b5]692}
693
[a0350e9]694CNode::~CNode() {
695    delete data;
696}
697
698// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
699// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
[a9c298]700// working only with linked, but not doubly linked lists due to memory usage we have to check the
[a0350e9]701// insertion around the first element separately from the insertion around all other elements in the list
[0179d5]702CNode* CNode::insert(CPairOld* c) {
[7c81165]703    if(NULL == this) {
[66e7b5]704        CNode* newElement   =   new CNode(c, this);
[a0350e9]705        return newElement;
706    }
[66e7b5]707    else {
708        poly u1 = ppMult_qq(c->getT1(),c->getLp1Term());
709        if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
710            CNode* newElement   =   new CNode(c, this);
[a0350e9]711            return newElement;
712        }
[66e7b5]713        if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
[fcb8022]714            if(1 != pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term()))) {
[598870]715                //pWrite(u1);
716                //Print("Multi-Term in CritPairs Sortierung altes Element: ");
717                //pWrite(ppMult_qq(this->data->getT1(),this->data->getLp1Term()));
[66e7b5]718                CNode* newElement   =   new CNode(c, this);
719                return newElement;
720            }
721            else {
[598870]722                //Print("Insert Deg\n");
[66e7b5]723                CNode* temp = this;
[7c81165]724                while(  NULL != temp->next) {
[a9c298]725                    if(temp->next->data->getDeg() == c->getDeg() ) {
[66e7b5]726                        if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
727                            temp = temp->next;
728                        }
729                        else {
730                            CNode* newElement   =   new CNode(c, temp->next);
731                            temp->next          =   newElement;
732                            return this;
[a9c298]733                        }
[a0350e9]734                    }
735                    else {
[66e7b5]736                        CNode* newElement   =   new CNode(c, temp->next);
[a0350e9]737                        temp->next          =   newElement;
738                        return this;
[66e7b5]739                    }
[a0350e9]740                }
[7c81165]741                CNode* newElement   =   new CNode(c, NULL);
[a0350e9]742                temp->next          =   newElement;
743                return this;
744            }
[66e7b5]745        } // outer if-clause
746        if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
747            CNode* temp =   this;
[a9c298]748            while( NULL != temp->next ) {
[66e7b5]749                if( c->getDeg() < temp->next->data->getDeg() ) {
750                    CNode* newElement   =   new CNode(c, temp->next);
[a0350e9]751                    temp->next          =   newElement;
752                    return this;
753                }
[66e7b5]754                if( c->getDeg() == temp->next->data->getDeg() ) {
[a9c298]755                    if(1 != pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
[66e7b5]756                        CNode* newElement   =   new CNode(c, temp->next);
757                        temp->next          =   newElement;
758                        return this;
759                    }
760                    else {
761                        temp = temp->next;
[7c81165]762                        while(  NULL != temp->next ) {
[a9c298]763                            if( temp->next->data->getDeg() == c->getDeg() ) {
[66e7b5]764                                if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),
765                                               temp->next->data->getLp1Term()))) {
766                                    temp = temp->next;
767                                }
768                                else {
769                                    CNode* newElement   =   new CNode(c, temp->next);
770                                    temp->next          =   newElement;
771                                    return this;
[a9c298]772                                }
[a0350e9]773                            }
774                            else {
[66e7b5]775                                CNode* newElement   =   new CNode(c, temp->next);
[a0350e9]776                                temp->next          =   newElement;
777                                return this;
[66e7b5]778                            }
[a0350e9]779                        }
[7c81165]780                        CNode* newElement   =   new CNode(c, NULL);
[66e7b5]781                        temp->next          =   newElement;
782                        return this;
[a0350e9]783                    }
[66e7b5]784                }
785                if( c->getDeg() > temp->next->data->getDeg() ) {
786                    temp    =   temp->next;
[a0350e9]787                }
788            }
[7c81165]789            CNode* newElement   =   new CNode(c, NULL);
[66e7b5]790            temp->next          =   newElement;
791            return this;
[a0350e9]792        }
793    }
794}
795
[ab76b4]796
797CNode* CNode::insertWithoutSort(CPairOld* cp) {
798    CNode* newElement = new CNode(cp);
799    newElement->next  = this;
800    return newElement;
801}
802
803
[0179d5]804// get the first elements from CListOld which by the above sorting have minimal degree
[cce6ed3]805CNode* CNode::getMinDeg() {
806    CNode* temp = this;
[7c81165]807    while(NULL != temp) {
808        while(NULL != temp->next && temp->next->data->getDeg() == this->data->getDeg()) {
[cce6ed3]809            temp = temp->next;
810        }
[a9c298]811        CNode* returnCNode  =   temp->next;
812        // every CListOld should end with a (NULL,NULL) element for a similar behaviour
[9bb97e]813        // using termination conditions throughout the algorithm
[7c81165]814        temp->next          =   NULL;
[cce6ed3]815        return returnCNode;
816    }
817    return NULL;
818}
819
[0179d5]820CPairOld* CNode::getData() {
[9bb97e]821    return data;
822}
823
824CNode* CNode::getNext() {
825    return next;
826}
827
[a05c71]828LPolyOld* CNode::getAdLp1() {
[9bb97e]829    return this->data->getAdLp1();
830}
831
[a05c71]832LPolyOld* CNode::getAdLp2() {
[9bb97e]833    return this->data->getAdLp2();
834}
835
[66e7b5]836poly CNode::getLp1Poly() {
837    return this->data->getLp1Poly();
838}
839
840poly CNode::getLp2Poly() {
841    return this->data->getLp2Poly();
842}
843
844poly CNode::getLp1Term() {
845    return this->data->getLp1Term();
846}
847
848poly CNode::getLp2Term() {
849    return this->data->getLp2Term();
850}
851
852int CNode::getLp1Index() {
853    return this->data->getLp1Index();
854}
855
856int CNode::getLp2Index() {
857    return this->data->getLp2Index();
858}
859
860poly CNode::getT1() {
861    return this->data->getT1();
862}
863
[9bb97e]864poly* CNode::getAdT1() {
865    return this->data->getAdT1();
866}
867
[66e7b5]868poly CNode::getT2() {
869    return this->data->getT2();
870}
871
[9bb97e]872poly* CNode::getAdT2() {
873    return this->data->getAdT2();
874}
875
[418bd6]876bool CNode::getDel() {
877  return data->getDel();
878}
879
[a05c71]880RuleOld* CNode::getTestedRuleOld() {
881    return this->data->getTestedRuleOld();
[9bb97e]882}
883
[66e7b5]884// for debugging
[f9b0bd]885void CNode::print()
886{
[66e7b5]887    CNode* temp = this;
[f9b0bd]888    PrintS("___________________List of critical pairs______________________:\n");
889    while(NULL != temp)
890    {
[f16a76d]891        pWrite(ppMult_qq(temp->getT1(),temp->getLp1Term()));
[d51339]892        Print("LP1 Index: %d\n",temp->getLp1Index());
[f9b0bd]893        PrintS("T1: ");
[66e7b5]894        pWrite(temp->getT1());
[1534d9]895        Print("%p\n",temp->getT1());
[f9b0bd]896        PrintS("LP1 Term: ");
[66e7b5]897        pWrite(temp->getLp1Term());
[f9b0bd]898        PrintS("LP1 Poly: ");
[d51339]899        pWrite(temp->getLp1Poly());
900        Print("LP2 Index: %d\n",temp->getLp2Index());
[f9b0bd]901        PrintS("T2: ");
[66e7b5]902        pWrite(temp->getT2());
[1534d9]903        Print("%p\n",temp->getT2());
[f9b0bd]904        PrintS("LP2 Term: ");
[66e7b5]905        pWrite(temp->getLp2Term());
[f9b0bd]906        PrintS("LP2 Poly: ");
[d51339]907        pWrite(temp->getLp2Poly());
[f9b0bd]908        PrintLn();
[66e7b5]909        temp = temp->next;
910    }
911}
[cce6ed3]912
[a0350e9]913/*
914====================================
[0179d5]915functions working on the class CListOld
[a0350e9]916====================================
917*/
[4f8fd1d]918// for initialization of CListOlds, last element always has data=NULL and next=NULL
[0179d5]919CListOld::CListOld() {
[7c81165]920    first   =   NULL;
[66e7b5]921}
922
[0179d5]923CListOld::CListOld(CPairOld* c) {
[66e7b5]924    first   =   new CNode(c);
[a0350e9]925}
926
[0179d5]927CListOld::~CListOld() {
[9cb4078]928    CNode* temp;
[7c81165]929    while(NULL != first) {
[9cb4078]930        temp    =   first;
931        first   =   first->getNext();
932        delete  temp;
933    }
[a0350e9]934}
935
936// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
937// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
[0179d5]938void CListOld::insert(CPairOld* c) {
[7c81165]939    first = first->insert(c);
[71f00c5]940}
[cce6ed3]941
[ab76b4]942void CListOld::insertWithoutSort(CPairOld* c) {
943    first = first->insertWithoutSort(c);
944}
945
[0179d5]946CNode* CListOld::getFirst() {
[9bb97e]947    return first;
948}
949
[0179d5]950// get the first elements from CListOld which by the above sorting have minimal degree
[cce6ed3]951// returns the pointer on the first element of those
[0179d5]952CNode* CListOld::getMinDeg() {
[cce6ed3]953    CNode* temp     =   first;
954    first           =   first->getMinDeg();
955    return temp;
956}
957
[0179d5]958void CListOld::print() {
[66e7b5]959    first->print();
960}
[cce6ed3]961
962/*
963====================================
964functions working on the class RNode
965====================================
966*/
[66e7b5]967RNode::RNode() {
[55a828]968    //Print("HIER RNODE CONSTRUCTOR\n");
[66e7b5]969    data    =   NULL;
970    next    =   NULL;
971}
972
[a05c71]973RNode::RNode(RuleOld* r) {
[cce6ed3]974    data    =   r;
975    next    =   NULL;
976}
977
978RNode::~RNode() {
[a05c71]979    //Print("DELETE RuleOld\n");
[cce6ed3]980    delete  data;
981}
982
[a05c71]983RNode* RNode::insert(RuleOld* r) {
[cce6ed3]984    RNode* newElement   =   new RNode(r);
985    newElement->next    =   this;
986    return newElement;
987}
988
[87beab7]989RNode* RNode::insert(int i, poly t) {
[55a828]990    //Print("IN INSERT: ");
991    //pWrite(t);
[a05c71]992    RuleOld*   r           =   new RuleOld(i,t);
993    //Print("ADDRESS OF RuleOld: %p\n",r);
[9bb97e]994    RNode* newElement   =   new RNode(r);
[55a828]995    //Print("ADDRESS OF RNODE: %p\n",newElement);
[a05c71]996    //Print("ADDRESS OF RNODE DATA: %p\n",newElement->getRuleOld());
[f6c7c9b]997    newElement->next    =   this;
998    return newElement;
[787685]999}
1000
1001
[a05c71]1002RNode* RNode::insertOrdered(RuleOld* r) {
[a9c298]1003    RNode* newElement   =   new RNode(r);
[787685]1004    RNode* temp         =   this;
1005    if(NULL == temp) {
1006        newElement->next =   temp;
1007        return newElement;
1008    }
[a05c71]1009    if(1 == pLmCmp(newElement->getRuleOldTerm(),temp->getRuleOldTerm())) {
[787685]1010        newElement->next =   temp;
1011        return newElement;
[1534d9]1012    }
1013    else {
[a05c71]1014        while(NULL != temp && 1 ==  pLmCmp(temp->getRuleOldTerm(),newElement->getRuleOldTerm())) {
[787685]1015            temp    =   temp->getNext();
[1534d9]1016        }
[787685]1017        newElement->next =   temp;
1018        return this;
[1534d9]1019    }
[9bb97e]1020}
1021
[787685]1022
[66e7b5]1023RNode* RNode::getNext() {
1024    return next;
[a9c298]1025}
[66e7b5]1026
[a05c71]1027RuleOld* RNode::getRuleOld() {
[66e7b5]1028    return data;
1029}
1030
[a05c71]1031int RNode::getRuleOldIndex() {
[66e7b5]1032    return data->getIndex();
1033}
1034
[a05c71]1035poly RNode::getRuleOldTerm() {
[66e7b5]1036    return data->getTerm();
1037}
1038
[6b0aa2]1039void RNode::print() {
1040    RNode* temp  =   this;
1041    while(NULL != temp) {
[a05c71]1042        pWrite(temp->getRuleOldTerm());
1043        Print("%d\n\n",temp->getRuleOldIndex());
[6b0aa2]1044        temp    =   temp->getNext();
1045    }
1046}
1047
[cce6ed3]1048/*
1049====================================
1050functions working on the class RList
1051====================================
1052*/
[66e7b5]1053RList::RList() {
[1534d9]1054    first = NULL;
[66e7b5]1055}
1056
[a05c71]1057RList::RList(RuleOld* r) {
[cce6ed3]1058    first = new RNode(r);
1059}
1060
[338842d]1061RList::~RList() {
[9cb4078]1062    RNode* temp;
[55a828]1063    //Print("%p\n",first);
[1534d9]1064    while(first) {
[9cb4078]1065        temp    =   first;
1066        first   =   first->getNext();
[55a828]1067        //Print("1 %p\n",first);
1068        //if(first) {
[a05c71]1069            //Print("1' %p\n",first->getRuleOld());
[55a828]1070            //Print("2 %p\n",first->getNext());
[a05c71]1071            //Print("3 %p\n",first->getNext()->getRuleOld());
1072            //Print("3 %p\n",first->getNext()->getRuleOldTerm());
[55a828]1073        //}
[9cb4078]1074        delete  temp;
1075    }
[55a828]1076    //Print("FERTIG\n");
[a9c298]1077}
[338842d]1078
[87beab7]1079void RList::insert(int i, poly t) {
1080    first = first->insert(i,t);
[9bb97e]1081}
1082
[a05c71]1083void RList::insert(RuleOld* r) {
[cce6ed3]1084    first = first->insert(r);
1085}
[66e7b5]1086
[a05c71]1087void RList::insertOrdered(RuleOld* r) {
[787685]1088    first   =   first->insertOrdered(r);
1089}
1090
[66e7b5]1091RNode* RList::getFirst() {
1092    return first;
1093}
1094
[a05c71]1095RuleOld* RList::getRuleOld() {
1096    return this->getRuleOld();
[66e7b5]1097}
1098
[6b0aa2]1099void RList::print() {
1100    first->print();
1101}
1102
[66e7b5]1103/*
1104=======================================
1105functions working on the class RTagNode
1106=======================================
1107*/
1108
[a41f3aa]1109RTagNode::RTagNode() {
1110    data = NULL;
1111    next = NULL;
1112}
[a9c298]1113
[66e7b5]1114RTagNode::RTagNode(RNode* r) {
1115    data = r;
1116    next = NULL;
1117}
[a9c298]1118
[66e7b5]1119RTagNode::RTagNode(RNode* r, RTagNode* n) {
[a9c298]1120
[66e7b5]1121    data = r;
1122    next = n;
1123}
1124
[338842d]1125RTagNode::~RTagNode() {
[a9c298]1126    delete data;
[66e7b5]1127}
[a9c298]1128
[fcb8022]1129// declaration with first as parameter due to sorting of RTagList
[66e7b5]1130RTagNode* RTagNode::insert(RNode* r) {
[598870]1131    //Print("Hier1\n");
[66e7b5]1132    RTagNode* newElement  = new RTagNode(r, this);
[598870]1133    //Print("Hier2\n");
[66e7b5]1134    return newElement;
1135}
1136
1137RNode* RTagNode::getRNode() {
[df638fb]1138    //Print("%p\n", this);
1139    //Print("%p\n",this->data);
[66e7b5]1140    return this->data;
1141}
1142
[9cb4078]1143RTagNode* RTagNode::getNext() {
1144    return next;
1145}
1146
[66e7b5]1147// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
[a05c71]1148//       Thus given actual index i and idx being the index of the LPolyOld under investigation
[66e7b5]1149//       the element on position length-idx+1 is the right one
1150RNode* RTagNode::get(int idx, int length) {
[a41f3aa]1151    if(idx==1 || idx==0) {
[87beab7]1152        // NOTE: We set this NULL as putting it the last element in the list, i.e. the element having
1153        //       RNode* = NULL would cost lots of iterations at each step of F5inc, with increasing
1154        //       length of the list this should be prevented
[66e7b5]1155        return NULL;
1156    }
1157    else {
1158        int j;
[a9c298]1159        RTagNode* temp = this;
[598870]1160    //Print("\n\nHIER IN GET IDX\n");
[a9c298]1161    //Print("FOR LOOP: %d\n",length-idx+1);
[87beab7]1162    for(j=1; j<=length-idx+1; j++) {
[66e7b5]1163            temp = temp->next;
1164        }
1165        return temp->data;
1166    }
1167}
1168
[fcb8022]1169void RTagNode::set(RNode* r) {
1170    this->data  =   r;
1171}
[66e7b5]1172
[ae5177]1173
[87beab7]1174void RTagNode::print() {
1175    RTagNode* temp  =   this;
[e6d283f]1176    if(NULL != temp && NULL != temp->getRNode()) {
[a05c71]1177        Print("1. element: %d,  ",getRNode()->getRuleOld()->getIndex());
1178        pWrite(getRNode()->getRuleOld()->getTerm());
[87beab7]1179        temp    =   temp->next;
[e6d283f]1180        int i   =   2;
1181        while(NULL != temp->getRNode() && NULL != temp) {
[a05c71]1182            Print("%d. element: %d,  ",i,getRNode()->getRuleOld()->getIndex());
1183            pWrite(getRNode()->getRuleOld()->getTerm());
[e6d283f]1184            temp    =   temp->next;
1185            i++;
1186        }
[87beab7]1187    }
1188}
[ae5177]1189
[66e7b5]1190/*
1191=======================================
1192functions working on the class LTagList
1193=======================================
1194*/
1195
[a41f3aa]1196RTagList::RTagList() {
1197    RTagNode* first =   new RTagNode();
1198    length          =   0;
1199}
1200
[66e7b5]1201RTagList::RTagList(RNode* r) {
1202    RTagNode* first =   new RTagNode(r);
1203    length          =   1;
1204}
1205
[338842d]1206RTagList::~RTagList() {
[9cb4078]1207    RTagNode* temp;
[c4158f]1208    while(first) {
[9cb4078]1209        temp    =   first;
1210        first   =   first->getNext();
1211        delete  temp;
1212    }
[338842d]1213}
1214
[66e7b5]1215// declaration with first as parameter in LTagNode due to sorting of LTagList
1216void RTagList::insert(RNode* r) {
1217    first = first->insert(r);
[598870]1218    //Print("LENGTH:%d\n",length);
[87beab7]1219    length = length +1;
[598870]1220    //Print("LENGTH:%d\n",length);
[66e7b5]1221}
1222
[8978fd]1223RNode* RTagList::getFirst() {
1224    return first->getRNode();
1225}
1226
[66e7b5]1227RNode* RTagList::get(int idx) {
1228    return first->get(idx, length);
1229}
[fcb8022]1230
1231void RTagList::setFirst(RNode* r) {
1232    first->set(r);
1233}
[87beab7]1234
1235void RTagList::print() {
1236    first->print();
1237}
1238
1239int RTagList::getLength() {
1240    return length;
1241}
[71f00c5]1242#endif
Note: See TracBrowser for help on using the repository browser.