source: git/kernel/f5lists.cc @ 963eeb

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