source: git/kernel/f5lists.cc @ 66e7b5

fieker-DuValspielwiese
Last change on this file since 66e7b5 was 66e7b5, checked in by Christian Eder, 15 years ago
subalgorithms criticalPairs, criterion1 and criterion2 added git-svn-id: file:///usr/local/Singular/svn/trunk@11343 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 15.7 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 "lpolynomial.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(LPoly* lp) {
29    data = lp;
30    next = NULL;
31}
32       
33LNode::LNode(LPoly* lp, LNode* l) {
34    data = lp;
35    next = l;
36}
37LNode::LNode(poly* t, int* i, poly* p) {
38    LPoly* lp = new LPoly(t,i,p);
39    data = lp;
40    next = NULL;
41}
42       
43LNode::LNode(poly* t, int* i, poly* p, LNode* l) {
44    LPoly* lp = new LPoly(t,i,p);
45    data = lp;
46    next = l;
47}
48
49 LNode::LNode(LNode* ln) {
50    data = ln->getLPoly();
51    next = ln->getNext();
52}
53       
54LNode::~LNode() {
55    delete next;
56    delete data;   
57}
58       
59// insert new elements to the list always in front (labeled / classical polynomial view)
60LNode* LNode::insert(LPoly* lp) {
61    LNode* newElement = new LNode(lp, this);
62    return newElement;
63}
64       
65LNode* LNode::insert(poly* t, int* i, poly* p) {
66    LNode* newElement = new LNode(t, i, p, this);
67    return newElement;
68}
69       
70// insert new elemets to the list w.r.t. increasing labels
71// only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
72LNode* LNode::insertByLabel(LPoly* lp) {
73    if( lp->getTerm() <= this->data->getTerm() ) {
74        LNode* newElement   =   new LNode(lp, this);
75        return newElement;
76    }
77    else {
78        LNode* temp = this;
79        while( NULL != temp->next ) {
80            if( lp->getTerm() <= temp->next->data->getTerm() ) {
81                LNode* newElement   =   new LNode(lp, temp->next);
82                temp->next          =   newElement;
83                return this;
84            }
85            else {
86                temp = temp->next;
87            }
88        }
89        LNode* newElement   =   new LNode(lp, NULL);
90        temp->next          =   newElement;
91        return this;
92    }
93}
94
95// deletes the first elements of the list with the same degree
96// only used for the S-polys, which are already sorted by increasing degree by CList
97LNode*  LNode::deleteByDeg() {
98    return this;
99}
100
101// get next from current LNode
102LNode* LNode::getNext() {
103    return next;
104}
105       
106// get the LPoly* out of LNode*
107LPoly* LNode::getLPoly() {
108    return data;
109}
110
111// get the data from the LPoly saved in LNode
112poly LNode::getPoly() {
113    return data->getPoly();
114}
115
116poly LNode::getTerm() {
117    return data->getTerm();
118}
119
120int LNode::getIndex() {
121    return data->getIndex();
122}
123
124// test if for any list element the polynomial part of the data is equal to *p
125bool LNode::polyTest(poly* p) {
126    LNode* temp = new LNode(this);
127    while(NULL != temp) {
128        if(pComparePolys(temp->getPoly(),*p)) {
129            return 1;
130        }
131        temp = temp->next;
132    }
133    return 0;
134}
135
136LNode* LNode::getNext(LNode* l) {
137    return l->next;
138}
139
140/*
141====================================
142functions working on the class LList
143====================================
144*/
145
146LList::LList(LPoly* lp) {
147    first   = new LNode(lp);
148}
149
150LList::LList(poly* t,int* i,poly* p) {
151    first   = new LNode(t,i,p);
152} 
153
154LList::~LList() {
155    delete first;
156}
157
158// insertion in front of the list
159void LList::insert(LPoly* lp) {
160    first = first->insert(lp);
161}
162
163void LList::insert(poly* t,int* i, poly* p) {
164    first = first->insert(t,i,p);
165}
166
167void LList::insertByLabel(LPoly* lp) {
168    first = first->insertByLabel(lp);
169}
170
171void LList::deleteByDeg() {
172    first = first->deleteByDeg();
173}
174
175bool LList::polyTest(poly* p) {
176    return first->polyTest(p);
177}
178
179LNode* LList::getFirst() {
180    return first;
181}
182
183LNode* LList::getNext(LNode* l) {
184    return l->getNext();
185}
186
187/*
188=======================================
189functions working on the class LTagNode
190=======================================
191*/
192
193LTagNode::LTagNode(LNode* l) {
194    data = l;
195    next = NULL;
196}
197       
198LTagNode::LTagNode(LNode* l, LTagNode* n) {
199    data = l;
200    next = n;
201}
202
203 LTagNode::~LTagNode() {
204    delete next;
205    delete data;   
206}
207       
208// declaration with first as parameter due to sorting of LTagList
209LTagNode* LTagNode::insert(LNode* l) {
210    LTagNode* newElement  = new LTagNode(l, this);
211    return newElement;
212}
213
214LNode* LTagNode::getLNode() {
215    return this->data;
216}
217
218// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
219//       Thus given actual index i and idx being the index of the LPoly under investigation
220//       the element on position length-idx is the right one
221LNode* LTagNode::get(int idx, int length) {
222    if(idx == 1) {
223        return NULL;
224    }
225    else {
226        int j;
227        LTagNode* temp = this; // last
228        for(j=1;j<=length-idx+1;j++) {
229            temp = temp->next;
230        }
231        return temp->data;
232    }
233}
234
235
236/*
237=======================================
238functions working on the class LTagList
239=======================================
240*/
241
242LTagList::LTagList(LNode* l) {
243    LTagNode* first =   new LTagNode(l);
244    length          =   1;
245}
246
247// declaration with first as parameter in LTagNode due to sorting of LTagList
248void LTagList::insert(LNode* l) {
249    first   =   first->insert(l);
250    length++;
251}
252
253LNode* LTagList::get(int idx) {
254    return first->get(idx, length);
255}
256
257/*
258====================================
259functions working on the class CNode
260====================================
261*/
262
263CNode::CNode() {
264    data    =   NULL;   
265    next    =   NULL;   
266}
267
268CNode::CNode(CPair* c) {
269    data    =   c;   
270    next    =   NULL;   
271}
272
273CNode::CNode(CPair* c, CNode* n) {
274    data    =   c;   
275    next    =   n;   
276}
277
278CNode::~CNode() {
279    delete next;
280    delete data;
281}
282
283// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
284// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
285// working only with linked, but not doubly linked lists due to memory usage we have to check the
286// insertion around the first element separately from the insertion around all other elements in the list
287CNode* CNode::insert(CPair* c, CNode* last) {
288    if(NULL == this->data) {
289        CNode* newElement   =   new CNode(c, this);
290        return newElement;
291    }
292    else {
293        poly u1 = ppMult_qq(c->getT1(),c->getLp1Term());
294        if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
295            CNode* newElement   =   new CNode(c, this);
296            return newElement;
297        }
298        if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
299            if(0 == pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term())) ||
300               -1 == pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term()))) {
301                Print("Leck mich am Arsch: ");
302                pWrite(u1);
303                Print("Multi-Term in CritPairs Sortierung altes Element: ");
304                pWrite(ppMult_qq(this->data->getT1(),this->data->getLp1Term()));
305                CNode* newElement   =   new CNode(c, this);
306                return newElement;
307            }
308            else {
309                Print("Insert Deg\n");
310                CNode* temp = this;
311                while(  NULL != temp->next->data ) {
312                    if(temp->next->data->getDeg() == c->getDeg() ) { 
313                        if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
314                            temp = temp->next;
315                        }
316                        else {
317                            CNode* newElement   =   new CNode(c, temp->next);
318                            temp->next          =   newElement;
319                            return this;
320                        } 
321                    }
322                    else {
323                        CNode* newElement   =   new CNode(c, temp->next);
324                        temp->next          =   newElement;
325                        return this;
326                    }
327                }
328                CNode* newElement   =   new CNode(c, last);
329                temp->next          =   newElement;
330                return this;
331            }
332        } // outer if-clause
333        if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
334            CNode* temp =   this;
335            while( NULL != temp->next->data ) {   
336                if( c->getDeg() < temp->next->data->getDeg() ) {
337                    CNode* newElement   =   new CNode(c, temp->next);
338                    temp->next          =   newElement;
339                    return this;
340                }
341                if( c->getDeg() == temp->next->data->getDeg() ) {
342                    if(0 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term())) || 
343                       -1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) { 
344                        CNode* newElement   =   new CNode(c, temp->next);
345                        temp->next          =   newElement;
346                        return this;
347                    }
348                    else {
349                        temp = temp->next;
350                        while(  NULL != temp->next->data ) {
351                            if( temp->next->data->getDeg() == c->getDeg() ) { 
352                                if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),
353                                               temp->next->data->getLp1Term()))) {
354                                    temp = temp->next;
355                                }
356                                else {
357                                    CNode* newElement   =   new CNode(c, temp->next);
358                                    temp->next          =   newElement;
359                                    return this;
360                                } 
361                            }
362                            else {
363                                CNode* newElement   =   new CNode(c, temp->next);
364                                temp->next          =   newElement;
365                                return this;
366                            }
367                        }
368                        CNode* newElement   =   new CNode(c, last);
369                        temp->next          =   newElement;
370                        return this;
371                    }
372                }
373                if( c->getDeg() > temp->next->data->getDeg() ) {
374                    temp    =   temp->next;
375                }
376            }
377            CNode* newElement   =   new CNode(c, last);
378            temp->next          =   newElement;
379            return this;
380        }
381    }
382}
383
384// get the first elements from CList which by the above sorting have minimal degree
385CNode* CNode::getMinDeg() {
386    CNode* temp = this;
387    while( NULL != temp->data ) {
388        while( temp->next->data->getDeg() == this->data->getDeg() ) {
389            temp = temp->next;
390        }
391        CNode* returnCNode  =   temp->next;   
392        temp->next          =   NULL;
393        return returnCNode;
394    }
395    return NULL;
396}
397
398poly CNode::getLp1Poly() {
399    return this->data->getLp1Poly();
400}
401
402poly CNode::getLp2Poly() {
403    return this->data->getLp2Poly();
404}
405
406poly CNode::getLp1Term() {
407    return this->data->getLp1Term();
408}
409
410poly CNode::getLp2Term() {
411    return this->data->getLp2Term();
412}
413
414int CNode::getLp1Index() {
415    return this->data->getLp1Index();
416}
417
418int CNode::getLp2Index() {
419    return this->data->getLp2Index();
420}
421
422poly CNode::getT1() {
423    return this->data->getT1();
424}
425
426poly CNode::getT2() {
427    return this->data->getT2();
428}
429
430// for debugging
431void CNode::print() {
432    CNode* temp = this;
433    Print("List of critical pairs:\n");
434    while(NULL != temp->data) {
435        Print("Leck mich am Arsch: ");
436        Print("Index: %d\n",temp->getLp1Index());
437        Print("T1: ");
438        pWrite(temp->getT1());
439        Print("Lp1 Term: ");
440        pWrite(temp->getLp1Term());
441        Print("%d\n",temp->getLp2Index());
442        pWrite(temp->getT2());
443        pWrite(temp->getLp2Term());
444        Print("\n");
445        temp = temp->next;
446    }
447}
448
449/*
450====================================
451functions working on the class CList
452====================================
453*/
454// for initialization of CLists, last element alwas has data=NULL and next=NULL
455CList::CList() {
456    first   =   new CNode();
457    last    =   first;
458}
459
460CList::CList(CPair* c) {
461    first   =   new CNode(c);
462    last    =   first;
463}
464
465CList::~CList() {
466    delete first;
467}
468
469// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
470// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
471void CList::insert(CPair* c) {
472    first = first->insert(c, last);
473}
474
475// get the first elements from CList which by the above sorting have minimal degree
476// returns the pointer on the first element of those
477CNode* CList::getMinDeg() {
478    CNode* temp     =   first;
479    first           =   first->getMinDeg();
480    return temp;
481}
482
483void CList::print() {
484    first->print();
485}
486
487/*
488====================================
489functions working on the class RNode
490====================================
491*/
492RNode::RNode() {
493    data    =   NULL;
494    next    =   NULL;
495}
496
497RNode::RNode(Rule* r) {
498    data    =   r;
499    next    =   NULL;
500}
501
502RNode::~RNode() {
503    delete  next;
504    delete  data;
505}
506
507RNode* RNode::insert(Rule* r) {
508    RNode* newElement   =   new RNode(r);
509    newElement->next    =   this;
510    return newElement;
511}
512
513RNode* RNode::getNext() {
514    return next;
515}   
516
517Rule* RNode::getRule() {
518    return data;
519}
520
521int RNode::getRuleIndex() {
522    return data->getIndex();
523}
524
525poly RNode::getRuleTerm() {
526    return data->getTerm();
527}
528
529/*
530====================================
531functions working on the class RList
532====================================
533*/
534RList::RList() {
535    first = new RNode();
536}
537
538RList::RList(Rule* r) {
539    first = new RNode(r);
540}
541
542void RList::insert(Rule* r) {
543    first = first->insert(r);
544}
545
546RNode* RList::getFirst() {
547    return first;
548}
549
550Rule* RList::getRule() {
551    return this->getRule();
552}
553
554/*
555=======================================
556functions working on the class RTagNode
557=======================================
558*/
559
560RTagNode::RTagNode(RNode* r) {
561    data = r;
562    next = NULL;
563}
564       
565RTagNode::RTagNode(RNode* r, RTagNode* n) {
566    data = r;
567    next = n;
568}
569
570 RTagNode::~RTagNode() {
571    delete next;
572    delete data;   
573}
574       
575// declaration with first as parameter due to sorting of LTagList
576RTagNode* RTagNode::insert(RNode* r) {
577    Print("Hier1\n");
578    RTagNode* newElement  = new RTagNode(r, this);
579    Print("Hier2\n");
580    return newElement;
581}
582
583RNode* RTagNode::getRNode() {
584    return this->data;
585}
586
587// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
588//       Thus given actual index i and idx being the index of the LPoly under investigation
589//       the element on position length-idx+1 is the right one
590RNode* RTagNode::get(int idx, int length) {
591    if(idx == 1) {
592        return NULL;
593    }
594    else {
595        int j;
596        RTagNode* temp = this; 
597        for(j=1;j<=length-idx+1;j++) {
598            temp = temp->next;
599        }
600        return temp->data;
601    }
602}
603
604
605/*
606=======================================
607functions working on the class LTagList
608=======================================
609*/
610
611RTagList::RTagList(RNode* r) {
612    RTagNode* first =   new RTagNode(r);
613    length          =   1;
614}
615
616// declaration with first as parameter in LTagNode due to sorting of LTagList
617void RTagList::insert(RNode* r) {
618    first = first->insert(r);
619    length++;
620}
621
622RNode* RTagList::get(int idx) {
623    return first->get(idx, length);
624}
625#endif
Note: See TracBrowser for help on using the repository browser.