source: git/kernel/f5lists.cc @ ba5e9e

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