source: git/kernel/f5lists.cc @ 76cfef

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