source: git/kernel/f5lists.cc @ 61944d0

spielwiese
Last change on this file since 61944d0 was 61944d0, checked in by Christian Eder, 15 years ago
solved problems in reduction() in topReduction() considering both criteria and computation of new polynomials git-svn-id: file:///usr/local/Singular/svn/trunk@11473 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 22.2 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    gPrevRedCheck       =   NULL;
32}
33 LNode::LNode(LPoly* lp) {
34    data                =   lp;
35    next                =   NULL;
36    gPrevRedCheck       =   NULL;
37}
38       
39LNode::LNode(LPoly* lp, LNode* l) {
40//Print("HIER LNODE\n");
41    data                =   lp;
42    next                =   l;
43    gPrevRedCheck       =   NULL;
44}
45
46LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck) {
47LPoly* lp           =   new LPoly(t,i,p,r);
48data                =   lp;
49next                =   NULL;
50gPrevRedCheck       =   gPCheck;
51}
52       
53LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* l) {
54    LPoly* lp           =   new LPoly(t,i,p,r);
55    data                =   lp;
56    next                =   l;
57    gPrevRedCheck       =   gPCheck;
58}
59
60 LNode::LNode(LNode* ln) {
61    data                =   ln->getLPoly();
62    next                =   ln->getNext();
63    gPrevRedCheck       =   NULL;
64}
65       
66LNode::~LNode() {
67    //delete next;
68    delete gPrevRedCheck;
69    delete data;   
70}
71       
72// insert new elements to the list always at the end (labeled / classical polynomial view)
73// needed for list gPrev
74LNode* LNode::insert(LPoly* lp) {
75    //Print("INSERTION: \n");
76    //Print("LAST GPREV: ");
77    //pWrite(this->getPoly());
78LNode* newElement   =   new LNode(lp, NULL);
79    this->next          =   newElement;
80    return newElement;
81}
82       
83LNode* LNode::insert(poly t, int i, poly p, Rule* r) {
84    LNode* newElement   =   new LNode(t, i, p, r, NULL, NULL);
85    this->next          =   newElement;
86    return newElement;
87}
88
89// insert new elements to the list always in front (labeled / classical polynomial view)
90// needed for sPolyList
91LNode* LNode::insertSP(LPoly* lp) {
92    LNode* newElement   =   new LNode(lp, this);
93    return newElement;
94}
95       
96LNode* LNode::insertSP(poly t, int i, poly p, Rule* r) {
97    LNode* newElement   =   new LNode(t, i, p, r, NULL, this);
98    return newElement;
99}
100// insert new elemets to the list w.r.t. increasing labels
101// only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
102LNode* LNode::insertByLabel(poly t, int i, poly p, Rule* r) {
103    if(NULL == this || NULL == data) {
104        LNode* newElement   =   new LNode(t, i, p, r, this);
105        return newElement;
106    }
107    else {
108        if(-1 == pLmCmp(t,this->getTerm())) {
109            LNode* newElement   =   new LNode(t, i, p, r, this);
110            return newElement;
111        }
112        else {
113            LNode* temp = this;
114            while(NULL != temp->next && NULL != temp->next->data) {
115                if(-1 == pLmCmp(t,temp->next->getTerm())) {
116                    LNode* newElement   =   new LNode(t, i, p, r, temp->next);
117                    temp->next          =   newElement;
118                    return this;
119                }
120                else {
121                    temp = temp->next;
122                    //Print("%p\n",temp);
123                    //Print("%p\n",temp->data);
124                   
125                    //Print("%p\n",temp->next);
126                }
127            }
128        //Print("HIER\n");
129            LNode* newElement   =   new LNode(t, i, p, r, temp->next);
130            temp->next          =   newElement;
131            return this;
132        }
133    }
134}
135
136// deletes the first elements of the list with the same degree
137// only used for the S-polys, which are already sorted by increasing degree by CList
138LNode*  LNode::deleteByDeg() {
139    return this;
140}
141
142// get next from current LNode
143LNode* LNode::getNext() {
144    return next;
145}
146
147// get the LPoly* out of LNode*
148LPoly* LNode::getLPoly() {
149    return data;
150}
151
152// get the data from the LPoly saved in LNode
153poly LNode::getPoly() {
154    return data->getPoly();
155}
156
157poly LNode::getTerm() {
158    return data->getTerm();
159}
160
161int LNode::getIndex() {
162    return data->getIndex();
163}
164
165Rule* LNode::getRule() {
166    return data->getRule();
167}
168
169LNode* LNode::getGPrevRedCheck() {
170    return gPrevRedCheck;
171}
172
173// set the data from the LPoly saved in LNode
174void LNode::setPoly(poly p) {
175    data->setPoly(p);
176}
177
178void LNode::setTerm(poly t) {
179    data->setTerm(t);
180}
181
182void LNode::setIndex(int i) {
183    data->setIndex(i);
184}
185
186void LNode::setGPrevRedCheck(LNode* l) {
187    gPrevRedCheck   =   l;
188}
189
190void LNode::setNext(LNode* l) {
191    next    =   l;
192}
193
194// test if for any list element the polynomial part of the data is equal to *p
195bool LNode::polyTest(poly* p) {
196    LNode* temp = new LNode(this);
197    while(NULL != temp) {
198        if(pComparePolys(temp->getPoly(),*p)) {
199            return 1;
200        }
201        temp = temp->next;
202    }
203    return 0;
204}
205
206LNode* LNode::getNext(LNode* l) {
207    return l->next;
208}
209
210// for debugging
211void LNode::print() {
212    LNode* temp = this;
213    Print("___________________List of S-polynomials______________________:\n");
214    Print("%p\n",this);
215    while(NULL != temp && NULL != temp->data) {
216        Print("HIER\n");
217        Print("Index: %d\n",temp->getIndex());
218        Print("Term: ");
219        pWrite(temp->getTerm());
220        Print("Poly: ");
221        pWrite(temp->getPoly());
222        Print("\n");
223        temp = temp->next;
224    }
225}
226
227
228/*
229====================================
230functions working on the class LList
231====================================
232*/
233
234LList::LList() {
235    first   =   new LNode();
236    last    =   first;
237    length  =   0;
238}
239
240LList::LList(LPoly* lp) {
241    first   =   new LNode(lp);
242    last    =   first;
243    length  =   1;
244}
245
246LList::LList(poly t,int i,poly p,Rule* r) {
247    first   =   new LNode(t,i,p,r);
248    last    =   first;
249    length  =   1;
250} 
251
252LList::~LList() {
253    delete first;
254}
255
256// insertion at the end of the list, needed for gPrev
257void LList::insert(LPoly* lp) {
258    last = last->insert(lp);
259    //Print("NEW LAST GPREV: ");
260    //pWrite(last->getPoly());
261    length++;
262    //Print("LENGTH %d\n",length);
263}
264
265void LList::insert(poly t,int i, poly p, Rule* r) {
266    last = last->insert(t,i,p,r);
267    length++;
268    //Print("LENGTH %d\n",length);
269}
270
271// insertion in front of the list, needed for sPolyList
272void LList::insertSP(LPoly* lp) {
273    first = first->insertSP(lp);
274    length++;
275    //Print("LENGTH %d\n",length);
276}
277
278void LList::insertSP(poly t,int i, poly p, Rule* r) {
279    first = first->insertSP(t,i,p,r);
280    length++;
281    //Print("LENGTH %d\n",length);
282}
283
284
285void LList::insertByLabel(poly t, int i, poly p, Rule* r) {
286    first = first->insertByLabel(t,i,p,r);
287    length++;
288    //Print("LENGTH %d\n",length);
289}
290
291void LList::insertByLabel(LNode* l) {
292    first = first->insertByLabel(l->getTerm(),l->getIndex(),l->getPoly(),l->getRule());
293    length++;
294    //Print("LENGTH %d\n",length);
295}
296
297void LList::deleteByDeg() {
298    first = first->deleteByDeg();
299}
300
301bool LList::polyTest(poly* p) {
302    return first->polyTest(p);
303}
304
305LNode* LList::getFirst() {
306    return first;
307}
308
309LNode* LList::getLast() {
310    return last;
311}
312
313int LList::getLength() {
314    return length;
315}
316
317void LList::setFirst(LNode* l) {
318    LNode* temp =   first;
319    temp->setNext(NULL);
320    first       =   l;
321    length--;
322}
323
324void LList::print() {
325    first->print();
326}
327
328/*
329=======================================
330functions working on the class LTagNode
331=======================================
332*/
333LTagNode::LTagNode() {
334    data    =   NULL;
335    next    =   NULL;
336}
337
338LTagNode::LTagNode(LNode* l) {
339    data = l;
340    next = NULL;
341}
342       
343LTagNode::LTagNode(LNode* l, LTagNode* n) {
344    data = l;
345    next = n;
346}
347
348 LTagNode::~LTagNode() {
349    delete next;
350    delete data;   
351}
352       
353// declaration with first as parameter due to sorting of LTagList
354LTagNode* LTagNode::insert(LNode* l) {
355    LTagNode* newElement  = new LTagNode(l, this);
356    return newElement;
357}
358
359LNode* LTagNode::getLNode() {
360    return this->data;
361}
362
363LTagNode* LTagNode::getNext() {
364    return next;
365}
366
367// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
368//       Thus given actual index i and idx being the index of the LPoly under investigation
369//       the element on position length-idx is the right one
370LNode* LTagNode::get(int idx, int length) {
371    if(idx == 1) {
372        return NULL;
373    }
374    else {
375        int j;
376        LTagNode* temp = this; // last
377        for(j=1;j<=length-idx+1;j++) {
378            temp = temp->next;
379        }
380        return temp->data;
381    }
382}
383
384
385/*
386=======================================
387functions working on the class LTagList
388=======================================
389*/
390LTagList::LTagList() {
391    LTagNode* first =   new LTagNode();
392   
393    length          =   0;
394}
395
396LTagList::LTagList(LNode* l) {
397    LTagNode* first =   new LTagNode(l);
398    length          =   1;
399}
400
401// declaration with first as parameter in LTagNode due to sorting of LTagList
402void LTagList::insert(LNode* l) {
403    first   =   first->insert(l);
404    length++;
405}
406
407void LTagList::setFirstCurrentIdx(LNode* l) {
408    firstCurrentIdx =   l;
409}
410
411LNode* LTagList::get(int idx) {
412    return first->get(idx, length);
413}
414
415LNode* LTagList::getFirst() {
416    return first->getLNode();
417}
418
419LNode* LTagList::getFirstCurrentIdx() {
420    return firstCurrentIdx;
421}
422
423/*
424=====================================
425functions working on the class TopRed
426=====================================
427*/
428
429TopRed::TopRed() {
430    _completed  =   NULL;
431    _toDo       =   NULL;
432}
433
434TopRed::TopRed(LList* c, LList* t) {
435    _completed  =   c;
436    _toDo       =   t;
437}
438
439LList* TopRed::getCompleted() {
440    return _completed;
441}
442
443LList* TopRed::getToDo() {
444    return _toDo;
445}
446
447/*
448====================================
449functions working on the class CNode
450====================================
451*/
452
453CNode::CNode() {
454    data    =   NULL;   
455    next    =   NULL;   
456}
457
458CNode::CNode(CPair* c) {
459    data    =   c;   
460    next    =   NULL;   
461}
462
463CNode::CNode(CPair* c, CNode* n) {
464    data    =   c;   
465    next    =   n;   
466}
467
468CNode::~CNode() {
469    delete next;
470    delete data;
471}
472
473// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
474// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
475// working only with linked, but not doubly linked lists due to memory usage we have to check the
476// insertion around the first element separately from the insertion around all other elements in the list
477CNode* CNode::insert(CPair* c, CNode* last) {
478    if(NULL == this->data) {
479        CNode* newElement   =   new CNode(c, this);
480        return newElement;
481    }
482    else {
483        poly u1 = ppMult_qq(c->getT1(),c->getLp1Term());
484        if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
485            CNode* newElement   =   new CNode(c, this);
486            return newElement;
487        }
488        if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
489            if(1 != pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term()))) {
490                //pWrite(u1);
491                //Print("Multi-Term in CritPairs Sortierung altes Element: ");
492                //pWrite(ppMult_qq(this->data->getT1(),this->data->getLp1Term()));
493                CNode* newElement   =   new CNode(c, this);
494                return newElement;
495            }
496            else {
497                //Print("Insert Deg\n");
498                CNode* temp = this;
499                while(  NULL != temp->next->data ) {
500                    if(temp->next->data->getDeg() == c->getDeg() ) { 
501                        if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
502                            temp = temp->next;
503                        }
504                        else {
505                            CNode* newElement   =   new CNode(c, temp->next);
506                            temp->next          =   newElement;
507                            return this;
508                        } 
509                    }
510                    else {
511                        CNode* newElement   =   new CNode(c, temp->next);
512                        temp->next          =   newElement;
513                        return this;
514                    }
515                }
516                CNode* newElement   =   new CNode(c, last);
517                temp->next          =   newElement;
518                return this;
519            }
520        } // outer if-clause
521        if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
522            CNode* temp =   this;
523            while( NULL != temp->next->data ) {   
524                if( c->getDeg() < temp->next->data->getDeg() ) {
525                    CNode* newElement   =   new CNode(c, temp->next);
526                    temp->next          =   newElement;
527                    return this;
528                }
529                if( c->getDeg() == temp->next->data->getDeg() ) {
530                    if(1 != pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) { 
531                        CNode* newElement   =   new CNode(c, temp->next);
532                        temp->next          =   newElement;
533                        return this;
534                    }
535                    else {
536                        temp = temp->next;
537                        while(  NULL != temp->next->data ) {
538                            if( temp->next->data->getDeg() == c->getDeg() ) { 
539                                if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),
540                                               temp->next->data->getLp1Term()))) {
541                                    temp = temp->next;
542                                }
543                                else {
544                                    CNode* newElement   =   new CNode(c, temp->next);
545                                    temp->next          =   newElement;
546                                    return this;
547                                } 
548                            }
549                            else {
550                                CNode* newElement   =   new CNode(c, temp->next);
551                                temp->next          =   newElement;
552                                return this;
553                            }
554                        }
555                        CNode* newElement   =   new CNode(c, last);
556                        temp->next          =   newElement;
557                        return this;
558                    }
559                }
560                if( c->getDeg() > temp->next->data->getDeg() ) {
561                    temp    =   temp->next;
562                }
563            }
564            CNode* newElement   =   new CNode(c, last);
565            temp->next          =   newElement;
566            return this;
567        }
568    }
569}
570
571// get the first elements from CList which by the above sorting have minimal degree
572CNode* CNode::getMinDeg() {
573    CNode* temp = this;
574    while( NULL != temp->data ) {
575        while(NULL != temp->next->data && temp->next->data->getDeg() == this->data->getDeg()) {
576            temp = temp->next;
577        }
578        CNode* returnCNode  =   temp->next;   
579        // every CList should end with a (NULL,NULL) element for a similar behaviour
580        // using termination conditions throughout the algorithm
581        temp->next          =   new CNode();
582        return returnCNode;
583    }
584    return NULL;
585}
586
587CPair* CNode::getData() {
588    return data;
589}
590
591CNode* CNode::getNext() {
592    return next;
593}
594
595LPoly* CNode::getAdLp1() {
596    return this->data->getAdLp1();
597}
598
599LPoly* CNode::getAdLp2() {
600    return this->data->getAdLp2();
601}
602
603poly CNode::getLp1Poly() {
604    return this->data->getLp1Poly();
605}
606
607poly CNode::getLp2Poly() {
608    return this->data->getLp2Poly();
609}
610
611poly CNode::getLp1Term() {
612    return this->data->getLp1Term();
613}
614
615poly CNode::getLp2Term() {
616    return this->data->getLp2Term();
617}
618
619int CNode::getLp1Index() {
620    return this->data->getLp1Index();
621}
622
623int CNode::getLp2Index() {
624    return this->data->getLp2Index();
625}
626
627poly CNode::getT1() {
628    return this->data->getT1();
629}
630
631poly* CNode::getAdT1() {
632    return this->data->getAdT1();
633}
634
635poly CNode::getT2() {
636    return this->data->getT2();
637}
638
639poly* CNode::getAdT2() {
640    return this->data->getAdT2();
641}
642
643Rule* CNode::getTestedRule() {
644    return this->data->getTestedRule();
645}
646
647// for debugging
648void CNode::print() {
649    CNode* temp = this;
650    Print("___________________List of critical pairs______________________:\n");
651    while(NULL != temp->data) {
652        Print("LP1 Index: %d\n",temp->getLp1Index());
653        Print("T1: ");
654        pWrite(temp->getT1());
655        Print("LP1 Term: ");
656        pWrite(temp->getLp1Term());
657        Print("LP1 Poly: ");
658        pWrite(temp->getLp1Poly());
659        Print("LP2 Index: %d\n",temp->getLp2Index());
660        Print("T2: ");
661        pWrite(temp->getT2());
662        Print("LP2 Term: ");
663        pWrite(temp->getLp2Term());
664        Print("LP2 Poly: ");
665        pWrite(temp->getLp2Poly());
666        Print("\n");
667        temp = temp->next;
668    }
669}
670
671/*
672====================================
673functions working on the class CList
674====================================
675*/
676// for initialization of CLists, last element alwas has data=NULL and next=NULL
677CList::CList() {
678    first   =   new CNode();
679    last    =   first;
680}
681
682CList::CList(CPair* c) {
683    first   =   new CNode(c);
684    last    =   first;
685}
686
687CList::~CList() {
688    delete first;
689}
690
691// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
692// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
693void CList::insert(CPair* c) {
694    first = first->insert(c, last);
695}
696
697CNode* CList::getFirst() {
698    return first;
699}
700
701// get the first elements from CList which by the above sorting have minimal degree
702// returns the pointer on the first element of those
703CNode* CList::getMinDeg() {
704    CNode* temp     =   first;
705    first           =   first->getMinDeg();
706    return temp;
707}
708
709void CList::print() {
710    first->print();
711}
712
713/*
714====================================
715functions working on the class RNode
716====================================
717*/
718RNode::RNode() {
719    data    =   NULL;
720    next    =   NULL;
721}
722
723RNode::RNode(Rule* r) {
724    data    =   r;
725    next    =   NULL;
726}
727
728RNode::~RNode() {
729    delete  next;
730    delete  data;
731}
732
733RNode* RNode::insert(Rule* r) {
734    RNode* newElement   =   new RNode(r);
735    newElement->next    =   this;
736    return newElement;
737}
738
739RNode* RNode::insert(int i, poly t) {
740    Rule*   r           =   new Rule(i,t);
741    RNode* newElement   =   new RNode(r);
742    newElement->next    =   this;
743    return newElement;
744}
745
746RNode* RNode::getNext() {
747    return next;
748}   
749
750Rule* RNode::getRule() {
751    return data;
752}
753
754int RNode::getRuleIndex() {
755    return data->getIndex();
756}
757
758poly RNode::getRuleTerm() {
759    return data->getTerm();
760}
761
762/*
763====================================
764functions working on the class RList
765====================================
766*/
767RList::RList() {
768    first = new RNode();
769}
770
771RList::RList(Rule* r) {
772    first = new RNode(r);
773}
774
775void RList::insert(int i, poly t) {
776    first = first->insert(i,t);
777}
778
779void RList::insert(Rule* r) {
780    first = first->insert(r);
781}
782
783RNode* RList::getFirst() {
784    return first;
785}
786
787Rule* RList::getRule() {
788    return this->getRule();
789}
790
791/*
792=======================================
793functions working on the class RTagNode
794=======================================
795*/
796
797RTagNode::RTagNode() {
798    data = NULL;
799    next = NULL;
800}
801 
802RTagNode::RTagNode(RNode* r) {
803    data = r;
804    next = NULL;
805}
806       
807RTagNode::RTagNode(RNode* r, RTagNode* n) {
808    data = r;
809    next = n;
810}
811
812 RTagNode::~RTagNode() {
813    delete next;
814    delete data;   
815}
816       
817// declaration with first as parameter due to sorting of RTagList
818RTagNode* RTagNode::insert(RNode* r) {
819    //Print("Hier1\n");
820    RTagNode* newElement  = new RTagNode(r, this);
821    //Print("Hier2\n");
822    return newElement;
823}
824
825RNode* RTagNode::getRNode() {
826    return this->data;
827}
828
829// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
830//       Thus given actual index i and idx being the index of the LPoly under investigation
831//       the element on position length-idx+1 is the right one
832RNode* RTagNode::get(int idx, int length) {
833    if(idx==1 || idx==0) {
834        // NOTE: We set this NULL as putting it the last element in the list, i.e. the element having
835        //       RNode* = NULL would cost lots of iterations at each step of F5inc, with increasing
836        //       length of the list this should be prevented
837        return NULL;
838    }
839    else {
840        int j;
841        RTagNode* temp = this; 
842    //Print("\n\nHIER IN GET IDX\n");
843    //Print("FOR LOOP: %d\n",length-idx+1);   
844    for(j=1; j<=length-idx+1; j++) {
845            temp = temp->next;
846        }
847        return temp->data;
848    }
849}
850
851void RTagNode::set(RNode* r) {
852    this->data  =   r;
853}
854
855void RTagNode::print() {
856    RTagNode* temp  =   this;
857    Print("1. element: %d",getRNode()->getRule()->getIndex());
858    //pWrite(getRNode()->getRule()->getTerm());
859    temp    =   temp->next;
860    int i   =   2;
861    while(NULL != temp->getRNode()) {
862        Print("%d. element: %d",i,getRNode()->getRule()->getIndex());
863        //pWrite(getRNode()->getRule()->getTerm());
864        temp    =   temp->next;
865        i++;
866    }
867}
868/*
869=======================================
870functions working on the class LTagList
871=======================================
872*/
873
874RTagList::RTagList() {
875    RTagNode* first =   new RTagNode();
876    length          =   0;
877}
878
879RTagList::RTagList(RNode* r) {
880    RTagNode* first =   new RTagNode(r);
881    length          =   1;
882}
883
884// declaration with first as parameter in LTagNode due to sorting of LTagList
885void RTagList::insert(RNode* r) {
886    first = first->insert(r);
887    //Print("LENGTH:%d\n",length);
888    length = length +1;
889    //Print("LENGTH:%d\n",length);
890}
891
892RNode* RTagList::getFirst() {
893    return first->getRNode();
894}
895
896RNode* RTagList::get(int idx) {
897    return first->get(idx, length);
898}
899
900void RTagList::setFirst(RNode* r) {
901    first->set(r);
902}
903
904void RTagList::print() {
905    first->print();
906}
907
908int RTagList::getLength() {
909    return length;
910}
911#endif
Note: See TracBrowser for help on using the repository browser.