Changeset 9bb97e in git

Timestamp:

Feb 6, 2009, 9:12:35 PM (14 years ago)

Author:

Christian Eder

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

fcb80223d452f79f3b3e1a62b71d291a5fc64943

Parents:

b3e45f80f34104e744829011d4460dcee8e1e365

Message:

implementation of computeSPols, start of reduction and topReduction


git-svn-id: file:///usr/local/Singular/svn/trunk@11353 2c84dea3-7e68-4137-9b89-c4e89433aadc

Location:

kernel

Files:

• f5data.cc (modified) (5 diffs)
• f5data.h (modified) (4 diffs)
• f5gb.cc (modified) (18 diffs)
• f5gb.h (modified) (3 diffs)
• f5lists.cc (modified) (16 diffs)
• f5lists.h (modified) (9 diffs)

kernel/f5data.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5data.cc,v 1.2 2009-02-03 20:55:43 ederc Exp $ */
+/* $Id: f5data.cc,v 1.3 2009-02-06 20:12:35 ederc Exp $ */
 /*
 * ABSTRACT: lpolynomial definition 
@@ -30 +30 @@
 ================================================================
 */
-LPoly::LPoly(poly* t,int* i,poly* p) {
-    set(t,i,p);
+LPoly::LPoly(poly t,int i,poly p,bool d) {
+    set(t,i,p,d);
 }
 
-void LPoly::setPoly(poly* p)  {
-    polynomial = *p;
+void LPoly::setPoly(poly p)  {
+    polynomial = p;
 }
 
-void LPoly::setTerm(poly* t) {
-    term = *t;
+void LPoly::setTerm(poly t) {
+    term = t;
 }
 
-void LPoly::setIndex(int* i) {
-    index = *i;
+void LPoly::setIndex(int i) {
+    index = i;
 }
 
@@ -66 +66 @@
 }
 
-void LPoly::set(poly* t, int* i, poly* p) {
+void LPoly::set(poly t, int i, poly p, bool d) {
     this->setTerm(t);
     this->setIndex(i);
     this->setPoly(p);
+    this->setDel(d);
 }
 
@@ -98 +99 @@
 }
 
+poly* CPair::getAdT1() {
+    return &t1;
+}
+
+poly* CPair::getAdT2() {
+    return &t2;
+}
+
 poly CPair::getT2() {
     return t2;
+}
+
+LPoly* CPair::getAdLp1() {
+    return lp1;
+}
+
+LPoly* CPair::getAdLp2() {
+    return lp2;
 }
 
@@ -135 +152 @@
 ===================================
 */
-Rule::Rule(int* i, poly* t) {
+Rule::Rule(int i, poly t, LPoly* l) {
     index   =   i;
     term    =   t;
+    origin  =   l;
 }
 
 int Rule::getIndex() {
-    return *index;
+    return index;
 }
 
 poly Rule::getTerm() {
-    return *term;
+    return term;
 }
 

kernel/f5data.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5data.h,v 1.2 2009-02-03 20:55:43 ederc Exp $ */
+/* $Id: f5data.h,v 1.3 2009-02-06 20:12:35 ederc Exp $ */
 /*
 * ABSTRACT: labeled polynomial interface
@@ -33 +33 @@
         bool    del; //for deletion in TopReduction Subalgorithm
     public:
-                LPoly(poly*t,int* i,poly* p); 
-        void    setPoly(poly* p);
+                LPoly(poly t, int i, poly p, bool d = false); 
+        void    setPoly(poly p);
         poly    getPoly();
-        void    setTerm(poly* t);
+        void    setTerm(poly t);
         poly    getTerm();
-        void    setIndex(int* i);
+        void    setIndex(int i);
         int     getIndex();
         void    setDel(bool b);
         bool    getDel() const;
-        void    set(poly* t, int* i, poly* p);
+        void    set(poly t, int i, poly p, bool d);
         LPoly*  get();
 };
@@ -63 +63 @@
         long    getDeg();
         poly    getT1();
+        poly*   getAdT1();
+        LPoly*  getAdLp1();
         poly    getLp1Poly();
         poly    getLp1Term();
         int     getLp1Index();
         poly    getT2();
+        poly*   getAdT2();
+        LPoly*  getAdLp2();
         poly    getLp2Poly();
         poly    getLp2Term();
@@ -81 +85 @@
 class Rule {
     private:
-        int*    index;      // index of the labeled polynomial the rule comes from 
-        poly*   term;       // term of the labeled polynomial the rule comes from
+        int     index;      // index of the labeled polynomial the rule comes from 
+        poly    term;       // term of the labeled polynomial the rule comes from
         LPoly*  origin;     // pointer of the LPoly which generated this rule (needed in criterion2())
     public:
-                Rule(int* i, poly* term);
+                Rule(int i, poly term, LPoly* l);
         int     getIndex();
         poly    getTerm();

kernel/f5gb.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.cc,v 1.22 2009-02-04 19:27:11 ederc Exp $ */
+/* $Id: f5gb.cc,v 1.23 2009-02-06 20:12:35 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -26 +26 @@
 
 
+
 /*
 ====================================================================
@@ -61 +62 @@
 
 
+
 /*
 ==================================================
@@ -67 +69 @@
 ==================================================
 */
-LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE) {
+LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, int* reductionsToZero) {
+    int j;
     // tag the first element of index i-1 for criterion 1 
     LTagList* lTag  =   new LTagList(gPrev->getFirst());
@@ -73 +76 @@
     RTagList* rTag  =   new RTagList();
     gPrev->insert(ONE,i,f_i);
-    CList* critPairs    =   new CList();
-    critPairs           =   criticalPair(gPrev, critPairs, lTag, rTag);
-    
+    Print("1st gPrev: ");
+    pWrite(gPrev->getFirst()->getPoly());
+    Print("2nd gPrev: ");
+    pWrite(gPrev->getFirst()->getNext()->getPoly());    
+    CList* critPairs        =   new CList();
+    RList* rules            =   new RList();
+    CNode* critPairsMinDeg  =   new CNode();   
+    LNode* sPolys           =   new LNode();
+    // computation of critical pairs with checking of criterion 1 and criterion 2
+    critPairs               =   criticalPair(gPrev, critPairs, lTag, rTag);
+    LList* sPolyList        =   new LList();
+    // labeled polynomials which have passed reduction() and have to be added to list gPrev
+    LList* completed        =   new LList();
+    // the reduced labeled polynomials which are returned from subalgorithm reduction()
+    LNode* reducedLPolys     =   new LNode();
+    // while there are critical pairs to be further checked and deleted/computed
+    while(NULL != critPairs->getFirst()->getData()) { 
+        // critPairs->getMinDeg() deletes the first elements of minimal degree from
+        // critPairs, thus the while loop is not infinite.
+        critPairsMinDeg =   critPairs->getMinDeg();
+        // adds all to be reduced S-polynomials in the list sPolyList and adds 
+        // the corresponding rules to the list rules
+        // NOTE: inside there is a second check of criterion 2 if new rules are 
+        // added
+        computeSPols(critPairsMinDeg,rTag,rules,sPolyList,reductionsToZero);
+         
+        reducedLPolys   =   reduction(sPolyList, completed, gbPrev, reductionsToZero);
+    }
     return gPrev;
 }
+
 
 
@@ -91 +120 @@
     number nOne         =   nInit(1);
     LNode* first        =   gPrev->getFirst();
-    LNode* l            =   gPrev->getFirst()->getNext();
+    LNode* l            =   first->getNext();
     poly* u1            =   new poly(pInit());
     poly* u2            =   new poly(pInit());
@@ -110 +139 @@
         if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) && 
            !criterion2(u1, first, rTag) && !criterion2(u2, l, rTag)) {
-            Print("Criteria passed\n");
             // if they pass the test, add them to CList critPairs, having the LPoly with greater
             // label as first element in the CPair
@@ -126 +154 @@
         }
         else {
-            Print("Criteria not passed\n");
         }
         
@@ -135 +162 @@
         l   =   l->getNext();
     }
-    Print("ENDE CRITPAIRS\n");
     return critPairs;
 }
+
+
 
 /*
@@ -151 +179 @@
     while(NULL != testNode) {
         if(pLmDivisibleByNoComp(pHead(testNode->getPoly()),u1)) {
+            Print("Criterion 1 NOT passed!\n");
             return true;
         }
@@ -157 +186 @@
     return false;
 }
+
+
 
 /*
@@ -169 +200 @@
     poly u1 = ppMult_qq(*t,l->getTerm());
     // first element added to rTag was NULL, check for this
-    Print("Hier1\n");
     while(NULL != testNode && testNode->getRule()->getOrigin() != l->getLPoly()) {
-        Print("Hier2\n");
         if(pLmDivisibleByNoComp(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
+            Print("Criterion 2 NOT passed!\n");
             return true;
         }
@@ -180 +210 @@
 }
 
-/*
-==========================================================================================================
-Criterion 2, i.e. Rewritten Criterion, for its second call in sPols(), with added lastRuleTested parameter
-==========================================================================================================
-*/
-bool criterion2(poly* t, LNode* l, RTagList* rTag, Rule* lastRuleTested) {
+
+
+/*
+=================================================================================================================
+Criterion 2, i.e. Rewritten Criterion, for its second call in computeSPols(), with added lastRuleTested parameter
+=================================================================================================================
+*/
+bool criterion2(poly* t, LPoly* l, RTagList* rTag, Rule* lastRuleTested) {
     // start at the previously added element to gPrev, as all other elements will have the same index for sure
     RNode* testNode =   rTag->getFirst();
@@ -191 +223 @@
     poly u1 = ppMult_qq(*t,l->getTerm());
     // first element added to rTag was NULL, check for this
-    Print("Hier1\n");
-    while(NULL != testNode && testNode->getRule()->getOrigin() != l->getLPoly()) {
-        Print("Hier2\n");
+    while(NULL != testNode && testNode->getRule() != lastRuleTested) {
         if(pLmDivisibleByNoComp(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
+            Print("Criterion 2 NOT passed!\n");
             return true;
         }
@@ -201 +232 @@
     return false;
 }
+
+
+
+/*
+==================================
+Computation of S-Polynomials in F5
+==================================
+*/
+void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, int* reductionsToZero) { 
+    CNode* temp =   first;
+    poly zero   =   pInit();
+    while(NULL != temp->getData()) {
+        // only if a new rule was added since the last test in subalgorithm criticalPair()
+        if(rules->getFirst() != rTag->getFirst()) {
+            Print("IN SPOLS => NEW RULES AVAILABLE\n");
+            if(!criterion2(temp->getAdT1(),temp->getAdLp1(),rTag,temp->getLastRuleTested())) {
+                // the second component is tested only when it has the actual index, otherwise there is
+                // no new rule to test since the last test in subalgorithm criticalPair()
+                if(temp->getLp2Index() == temp->getLp1Index()) {
+                    if(!criterion2(temp->getAdT2(),temp->getAdLp2(),rTag,temp->getLastRuleTested())) {
+                        // computation of S-polynomial
+                        poly sp =   pInit();
+                        sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
+                                         ppMult_qq(temp->getT2(),temp->getLp2Poly()));
+                        Print("BEGIN SPOLY\n====================\n");
+                        pWrite(sp);
+                        Print("END SPOLY\n====================\n");
+                        if(!pCmp(sp,zero)) {
+                            // as rules consist only of pointers we need to save the labeled
+                            // S-polynomial also of a zero S-polynomial
+                            //zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
+                            // origin of rule can be set NULL as the labeled polynomial
+                            // will never be used again as it is zero => no problems with 
+                            // further criterion2() tests and termination conditions
+                            *reductionsToZero++;
+                            rules->insert(temp->getLp1Index(),temp->getT1(),NULL);
+                        }
+                        else {
+                            sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp);
+                            rules->insert(temp->getLp1Index(),temp->getT1(),sPolyList->getFirst()->getLPoly());
+                        }
+                        // data is saved in sPolyList or zero => delete sp
+                        pDelete(&sp);
+                    }
+                }
+                else { // temp->getLp2Index() < temp->getLp1Index()
+                    // computation of S-polynomial
+                    poly sp =   pInit();
+                    sp      =   pSub(ppMult_qq(temp->getT1(),temp->getLp1Poly()),
+                                     ppMult_qq(temp->getT2(),temp->getLp2Poly()));
+                    Print("BEGIN SPOLY\n====================\n");
+                    pWrite(sp);
+                    Print("END SPOLY\n====================\n");
+                    if(!pCmp(sp,zero)) {
+                        // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
+                        // origin of rule can be set NULL as the labeled polynomial
+                        // will never be used again as it is zero => no problems with 
+                        // further criterion2() tests and termination conditions
+                        *reductionsToZero++;
+                        rules->insert(temp->getLp1Index(),temp->getT1(),NULL);
+                    }
+                    else {
+                        sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp);
+                        rules->insert(temp->getLp1Index(),temp->getT1(),sPolyList->getFirst()->getLPoly());
+                    }
+                    // data is saved in sPolyList or zero => delete sp
+                    pDelete(&sp);
+                }
+            }
+        }
+        temp    =   temp->getNext();
+    }
+    // these critical pairs can be deleted now as they are either useless for further computations or 
+    // already saved as an S-polynomial to be reduced in the following
+    delete first;    
+}
+
+
+
+/*
+========================================================================
+reduction including subalgorithm topReduction() using Faugere's criteria
+========================================================================
+*/
+LNode* reduction(LList* sPolyList, LList* completed, ideal gbPrev, int* reductionsToZero) { 
+    poly zero   =   pInit();
+    // compute only if there are any S-polynomials to be reduced
+    if(NULL != sPolyList->getFirst()->getLPoly()) {
+        LNode* temp =   sPolyList->getFirst();
+        while(NULL != temp->getLPoly()) {
+            temp->setPoly(kNF(gbPrev,currQuotient,temp->getPoly()));
+            Print("Nach NORMAL FORM: ");
+            pWrite(temp->getPoly());
+            // test if temp->getPoly() is zero polynomial
+            if(!pCmp(temp->getPoly(),zero)) {
+                *reductionsToZero++;
+                // TODO: sPolyList -> delete first element of list as it is zero and done
+            }
+            //completed   =   topReduction();
+            // in topReduction() the investigated first element of sPolyList will be deleted after its
+            // reduction has finished => the next to be investigated element is the newly first element
+            // in sPolyList => the while loop is finite
+            // first possible after implementation of topReduction(): temp = sPolyList->getFirst();
+            temp    =   temp->getNext();
+        }
+    }
+    return NULL;
+}    
+
+
+
+/*
+=====================================================================================
+top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
+the same index whereas the labels are taken into account
+=====================================================================================
+*/
+LNode* topReduction(LNode* l, LList* gPrev, LList* completed) {
+    LPoly* red  =   findReductor(l, gPrev, completed);
+    return NULL;
+}
+
+
+
+/*
+=====================================================================
+subalgorithm to find a possible reductor for the labeled polynomial l
+=====================================================================
+*/
+LPoly* findReductor(LNode* l, LList* gPrev, LList* completed) {
+    return NULL;
+}
+
+
 
 /*
@@ -209 +374 @@
 ideal F5main(ideal id, ring r) {
     int i,j;
+    int* reductionsToZero   =   new int;
+    *reductionsToZero       =   0;
     // 1 polynomial for defining initial labels & further tests
     poly ONE = pOne();
-    // list of rules
-    RList* rules    =   new RList();
     i = 1;
-    LList* gPrev    =   new LList( &ONE, &i, &id->m[0]);
-    poly* lcm = new poly;
+        poly* lcm = new poly;
     // initialization for usage in pLcm()
     *lcm = pOne();
@@ -242 +406 @@
     qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
     idShow(id);
+    LList* gPrev    =   new LList(ONE, i, id->m[0]);
+    pWrite(id->m[0]);
     poly p = pHead(id->m[0]);
     pWrite(p);
     poly q = pHead(id->m[2]);
     pWrite(q);
+    
+    // computing the groebner basis of the elements of index < actual index
+    Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
+    ideal gbPrev    =   idInit(gPrev->getLength(),1);
+    // initializing the groebner basis of elements of index < actual index
+    gbPrev->m[0]    =   gPrev->getFirst()->getPoly();
+    idShow(gbPrev);
+    idShow(currQuotient);
+
     for(i=2; i<=IDELEMS(id); i++) {
-        gPrev   =   F5inc(&i, &id->m[i-1], gPrev, &ONE);
+        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, reductionsToZero);
         Print("JA\n");
+        //TODO: idAdd for computing gbPrev with the actual index!
     } 
     // only for debugging
@@ -263 +439 @@
         //}
     //}
+    Print("\n\nNumber of zero-reductions:  %d\n",*reductionsToZero);
     return(id);
 

kernel/f5gb.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.h,v 1.21 2009-02-04 19:27:12 ederc Exp $ */
+/* $Id: f5gb.h,v 1.22 2009-02-06 20:12:35 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -35 +35 @@
 ==================================================
 */
-LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE);
+LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, int* reductionToZero);
 
 /*
@@ -65 +65 @@
 ==========================================================================================================
 */
-bool criterion2(poly* t, LNode* l, RTagList* rTag, Rule* lastRuleTested);
- 
+bool criterion2(poly* t, LPoly* l, RTagList* rTag, Rule* lastRuleTested);
+
+/*
+==================================
+Computation of S-Polynomials in F5
+==================================
+*/
+void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList, int* reductionsToZero);
+
+/*
+========================================================================
+reduction including subalgorithm topReduction() using Faugere's criteria
+========================================================================
+*/
+LNode* reduction(LList* sPolyList, LList* completed, ideal gbPrev, int* reductionsToZero);
+
+/*
+=====================================================================================
+top reduction in F5, i.e. reduction of a given S-polynomial by labeled polynomials of
+the same index whereas the labels are taken into account
+=====================================================================================
+*/
+LNode* topReduction(LNode* l, LList* gPrev, LList* completed); 
+
+/*
+=====================================================================
+subalgorithm to find a possible reductor for the labeled polynomial l
+=====================================================================
+*/
+LPoly* findReductor(LNode* l, LList* gPrev, LList* completed);
+
 /*
 ======================================

kernel/f5lists.cc

@@ -26 +26 @@
 
 // generating new list elements (labeled / classical polynomial / LNode view)
-LNode::LNode(LPoly* lp) {
+LNode::LNode() {
+    data = NULL;
+    next = NULL;
+}
+ LNode::LNode(LPoly* lp) {
     data = lp;
     next = NULL;
@@ -35 +39 @@
     next = l;
 }
-LNode::LNode(poly* t, int* i, poly* p) {
+LNode::LNode(poly t, int i, poly p) {
     LPoly* lp = new LPoly(t,i,p);
     data = lp;
@@ -41 +45 @@
 }
        
-LNode::LNode(poly* t, int* i, poly* p, LNode* l) {
+LNode::LNode(poly t, int i, poly p, LNode* l) {
     LPoly* lp = new LPoly(t,i,p);
     data = lp;
@@ -63 +67 @@
 }
         
-LNode* LNode::insert(poly* t, int* i, poly* p) {
+LNode* LNode::insert(poly t, int i, poly p) {
     LNode* newElement = new LNode(t, i, p, this);
     return newElement;
@@ -70 +74 @@
 // insert new elemets to the list w.r.t. increasing labels
 // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
-LNode* LNode::insertByLabel(LPoly* lp) {
-    if( lp->getTerm() <= this->data->getTerm() ) {
-        LNode* newElement   =   new LNode(lp, this);
+LNode* LNode::insertByLabel(poly t, int i, poly p) {
+    if(0 == pLmCmp(t,this->getTerm()) || -1 == pLmCmp(t,this->getTerm())) {
+        LNode* newElement   =   new LNode(t, i, p, this);
         return newElement;
     }
     else {
         LNode* temp = this;
-        while( NULL != temp->next ) {
-            if( lp->getTerm() <= temp->next->data->getTerm() ) {
-                LNode* newElement   =   new LNode(lp, temp->next);
+        while( NULL != temp->next->data ) {
+            if( 0 == pLmCmp(t,temp->next->getTerm()) || -1 == pLmCmp(t,temp->next->getTerm())) {
+                LNode* newElement   =   new LNode(t, i, p, temp->next);
                 temp->next          =   newElement;
                 return this;
@@ -87 +91 @@
             }
         }
-        LNode* newElement   =   new LNode(lp, NULL);
+        LNode* newElement   =   new LNode(t, i, p, NULL);
         temp->next          =   newElement;
         return this;
@@ -120 +124 @@
 int LNode::getIndex() {
     return data->getIndex();
+}
+
+bool LNode::getDel() {
+    return data->getDel();
+}
+
+// set the data from the LPoly saved in LNode
+void LNode::setPoly(poly p) {
+    data->setPoly(p);
+}
+
+void LNode::setTerm(poly t) {
+    data->setTerm(t);
+}
+
+void LNode::setIndex(int i) {
+    data->setIndex(i);
+}
+
+void LNode::setDel(bool d) {
+    data->setDel(d);
 }
 
@@ -144 +169 @@
 */
 
+LList::LList() {
+    first   =   new LNode();
+    length  =   0;
+}
+
 LList::LList(LPoly* lp) {
-    first   = new LNode(lp);
-}
-
-LList::LList(poly* t,int* i,poly* p) {
-    first   = new LNode(t,i,p);
+    first   =   new LNode(lp);
+    length  =   1;
+}
+
+LList::LList(poly t,int i,poly p) {
+    first   =   new LNode(t,i,p);
+    length  =   1;
 } 
 
@@ -159 +191 @@
 void LList::insert(LPoly* lp) {
     first = first->insert(lp);
-}
-
-void LList::insert(poly* t,int* i, poly* p) {
+    length++;
+}
+
+void LList::insert(poly t,int i, poly p) {
     first = first->insert(t,i,p);
-}
-
-void LList::insertByLabel(LPoly* lp) {
-    first = first->insertByLabel(lp);
+    length++;
+}
+
+void LList::insertByLabel(poly t, int i, poly p) {
+    first = first->insertByLabel(t,i,p);
+    length++;
 }
 
@@ -183 +218 @@
 LNode* LList::getNext(LNode* l) {
     return l->getNext();
+}
+
+int LList::getLength() {
+    return length;
 }
 
@@ -299 +338 @@
             if(0 == pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term())) ||
                -1 == pLmCmp(u1,ppMult_qq(this->data->getT1(), this->data->getLp1Term()))) {
-                Print("Leck mich am Arsch: ");
                 pWrite(u1);
                 Print("Multi-Term in CritPairs Sortierung altes Element: ");
@@ -386 +424 @@
     CNode* temp = this;
     while( NULL != temp->data ) {
-        while( temp->next->data->getDeg() == this->data->getDeg() ) {
+        while(NULL != temp->next->data && temp->next->data->getDeg() == this->data->getDeg()) {
             temp = temp->next;
         }
         CNode* returnCNode  =   temp->next;    
-        temp->next          =   NULL;
+        // every CList should end with a (NULL,NULL) element for a similar behaviour 
+        // using termination conditions throughout the algorithm
+        temp->next          =   new CNode();
         return returnCNode;
     }
     return NULL;
+}
+
+CPair* CNode::getData() {
+    return data;
+}
+
+CNode* CNode::getNext() {
+    return next;
+}
+
+LPoly* CNode::getAdLp1() {
+    return this->data->getAdLp1();
+}
+
+LPoly* CNode::getAdLp2() {
+    return this->data->getAdLp2();
 }
 
@@ -424 +480 @@
 }
 
+poly* CNode::getAdT1() {
+    return this->data->getAdT1();
+}
+
 poly CNode::getT2() {
     return this->data->getT2();
+}
+
+poly* CNode::getAdT2() {
+    return this->data->getAdT2();
+}
+
+Rule* CNode::getLastRuleTested() {
+    return this->data->getLastRuleTested();
 }
 
@@ -472 +540 @@
 }
 
+CNode* CList::getFirst() {
+    return first;
+}
+
 // get the first elements from CList which by the above sorting have minimal degree
 // returns the pointer on the first element of those
@@ -510 +582 @@
 }
 
+RNode* RNode::insert(int i, poly t, LPoly* l) {
+    Rule*   r           =   new Rule(i,t,l);
+    RNode* newElement   =   new RNode(r);
+    newElement->next    =   this;
+    return newElement;
+}
+
 RNode* RNode::getNext() {
     return next;
@@ -537 +616 @@
 RList::RList(Rule* r) {
     first = new RNode(r);
+}
+
+void RList::insert(int i, poly t, LPoly* l) {
+    first = first->insert(i,t,l);
 }
 

kernel/f5lists.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5lists.h,v 1.5 2009-02-04 19:27:12 ederc Exp $ */
+/* $Id: f5lists.h,v 1.6 2009-02-06 20:12:35 ederc Exp $ */
 /*
 * ABSTRACT: list interface
@@ -41 +41 @@
     public:
         // generating new list elements from the labeled / classical polynomial view
+                LNode();
                 LNode(LPoly* lp);
                 LNode(LPoly* lp, LNode* l);
-                LNode(poly* t, int* i, poly* p);
-                LNode(poly* t, int* i, poly* p, LNode* l);
+                LNode(poly t, int i, poly p);
+                LNode(poly t, int i, poly p, LNode* l);
                 LNode(LNode* ln);
                 ~LNode();
         // insert new elements to the list in first place from the labeled / classical polynomial view
         LNode*  insert(LPoly* lp);
-        LNode*  insert(poly* t, int* i, poly* p);
+        LNode*  insert(poly t, int i, poly p);
         // insert new elements to the list with resp. to increasing labels
         // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
-        LNode*  insertByLabel(LPoly* lp);
+        LNode*  insertByLabel(poly t, int i, poly p);
         // deletes the first elements of the list with the same degree
         // get next from current LNode
@@ -63 +64 @@
         poly    getPoly();
         poly    getTerm();
-        int     getIndex();
+        int     getIndex(); 
+        bool    getDel();
+        // set the data from the LPoly saved in LNode
+        void    setPoly(poly p);
+        void    setTerm(poly t);
+        void    setIndex(int i);
+        void    setDel(bool d);
         // test if for any list element the polynomial part of the data is equal to *p
         bool    polyTest(poly* p);
@@ -78 +85 @@
     private:
         LNode*  first;
-    public:
+        int     length;
+    public:
+                LList();
                 LList(LPoly* lp);
-                LList(poly* t,int* i,poly* p);
+                LList(poly t,int i,poly p);
                 ~LList();
         void    insert(LPoly* lp);
         // insertion in front of the list
-        void    insert(poly* t,int* i, poly* p);
-        void    insertByLabel(LPoly* lp);
+        void    insert(poly t,int i, poly p);
+        void    insertByLabel(poly t, int i, poly p);
         void    deleteByDeg();
         bool    polyTest(poly* p);
         LNode*  getFirst(); 
         LNode*  getNext(LNode* l);
+        int     getLength();
 };
 
@@ -147 +157 @@
         CNode*  insert(CPair* c, CNode* last); 
         CNode*  getMinDeg();
+        CPair*  getData();
+        CNode*  getNext();
+        LPoly*  getAdLp1();
+        LPoly*  getAdLp2();
         poly    getLp1Poly();
         poly    getLp2Poly();
         poly    getLp1Term();
         poly    getLp2Term();
-        poly    getT1();   
+        poly    getT1(); 
+        poly*   getAdT1();  
         poly    getT2(); 
+        poly*   getAdT2();  
         int     getLp1Index();
         int     getLp2Index();
+        Rule*   getLastRuleTested();
         void    print();
 };
@@ -174 +191 @@
                 CList(CPair* c); 
                 ~CList(); 
+        CNode*  getFirst();
         void    insert(CPair* c);
         CNode*  getMinDeg();
@@ -194 +212 @@
                 ~RNode();
         RNode*  insert(Rule* r);
+        RNode*  insert(int i, poly t, LPoly* l);
         RNode*  getNext();
         Rule*   getRule();
@@ -215 +234 @@
                 ~RList();
         void    insert(Rule* r);
+        void    insert(int i, poly t, LPoly* l);
         RNode*  getFirst();
         Rule*   getRule();
@@ -257 +277 @@
         // declaration with first as parameter in LTagNode due to sorting of LTagList
         void    insert(RNode* r);
+        void    insert(int i, poly* t, LPoly* l);
         RNode*  getFirst();
         RNode*  get(int idx);