Changeset 87beab7 in git

Timestamp:

Feb 11, 2009, 10:24:08 PM (14 years ago)

Author:

Christian Eder

Branches:

(u'spielwiese', '0d6b7fcd9813a1ca1ed4220cfa2b104b97a0a003')

Children:

34fcf813ea36a30ddd0d8107abf9a73b247be289

Parents:

c5d8ddb1112344ad68257ea0c296d5b17aee0433

Message:

lots of stuff debugged, lots of wrong loop terminations improved, still problems with reduction subalgorithms reduction(), topReduction() & findReductor()


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

Location:

kernel

Files:

• f5data.cc (modified) (6 diffs)
• f5data.h (modified) (4 diffs)
• f5gb.cc (modified) (25 diffs)
• f5gb.h (modified) (8 diffs)
• f5lists.cc (modified) (21 diffs)
• f5lists.h (modified) (14 diffs)

kernel/f5data.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5data.cc,v 1.4 2009-02-08 19:17:54 ederc Exp $ */
+/* $Id: f5data.cc,v 1.5 2009-02-11 21:24:07 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, Rule* r) {
+    set(t,i,p,r);
 }
 
@@ -46 +46 @@
 }
 
+void LPoly::setRule(Rule* r) {
+    _rule   =   r;
+}
+
 poly LPoly::getPoly() {
     return polynomial;
@@ -58 +62 @@
 }
 
-void LPoly::set(poly t, int i, poly p) {
+Rule* LPoly::getRule() {
+    return _rule;
+}
+void LPoly::set(poly t, int i, poly p, Rule* r) {
     this->setTerm(t);
     this->setIndex(i);
     this->setPoly(p);
+    this->setRule(r);
 }
 
@@ -143 +151 @@
 ===================================
 */
-Rule::Rule(int i, poly t, LPoly* l) {
+Rule::Rule(int i, poly t) {
     index   =   i;
     term    =   t;
-    origin  =   l;
 }
 
@@ -156 +163 @@
     return term;
 }
-
-LPoly* Rule::getOrigin() {
-    return origin;
-}
-
-void Rule::setOrigin(LPoly* l) {
-    origin  =   l;
-}
 #endif

kernel/f5data.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5data.h,v 1.4 2009-02-08 19:17:54 ederc Exp $ */
+/* $Id: f5data.h,v 1.5 2009-02-11 21:24:07 ederc Exp $ */
 /*
 * ABSTRACT: labeled polynomial interface
@@ -31 +31 @@
         int     index;          //index of signature
         poly    polynomial;     //standard polynomial data
+        Rule*   _rule;
     public:
-                LPoly(poly t, int i, poly p); 
+                LPoly(poly t, int i, poly p, Rule* r=NULL);
         void    setPoly(poly p);
         poly    getPoly();
@@ -39 +40 @@
         void    setIndex(int i);
         int     getIndex();
-        void    set(poly t, int i, poly p);
+        void    setRule(Rule* r);
+        Rule*   getRule();
+        void    set(poly t, int i, poly p, Rule* r);
         LPoly*  get();
 };
@@ -84 +87 @@
         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, LPoly* l);
+                Rule(int i, poly term);
         int     getIndex();
         poly    getTerm();
-        LPoly*  getOrigin();
-        void    setOrigin(LPoly* l);
 };
 #endif

kernel/f5gb.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.cc,v 1.25 2009-02-09 14:24:08 ederc Exp $ */
+/* $Id: f5gb.cc,v 1.26 2009-02-11 21:24:07 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -69 +69 @@
 ==================================================
 */
-LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE) {
+LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag) {
     int j;
-    // tag the first element of index i-1 for criterion 1 
-    LTagList* lTag  =   new LTagList(gPrev->getFirst());
-    // first element in rTag is NULL, this must be done due to possible later improvements
-    RTagList* rTag  =   new RTagList();
+    Print("%p\n",gPrev->getFirst());
+    pWrite(gPrev->getFirst()->getPoly());
     gPrev->insert(ONE,i,f_i);
     Print("1st gPrev: ");
     pWrite(gPrev->getFirst()->getPoly());
     Print("2nd gPrev: ");
-    pWrite(gPrev->getFirst()->getNext()->getPoly());    
+    Print("%p",gPrev->getFirst()->getNext());
+    //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();
+    critPairs               =   criticalPair(gPrev, critPairs, lTag, rTag, rules);
+    static LList* sPolyList        =   new LList();
     // labeled polynomials which have passed reduction() and have to be added to list gPrev
-    LList* completed        =   new LList();
+    static LList* completed        =   new LList();
+    Print("_____________________________________________________________________________%p\n",completed->getFirst()->getLPoly());
     // the reduced labeled polynomials which are returned from subalgorithm reduction()
-    LNode* reducedLPolys     =   new LNode();
+    static LList* reducedLPolys     =   new LList();
     // while there are critical pairs to be further checked and deleted/computed
     while(NULL != critPairs->getFirst()->getData()) { 
@@ -101 +100 @@
         // added
         computeSPols(critPairsMinDeg,rTag,rules,sPolyList);
-         
-        reducedLPolys   =   reduction(sPolyList, completed, gPrev, lTag, rTag, gbPrev);
-    }
+        
+        // DEBUG STUFF FOR SPOLYLIST
+        LNode* temp     =   sPolyList->getFirst();
+        while(NULL != temp->getLPoly()) {
+            Print("Spolylist element: ");
+            pWrite(temp->getPoly());
+            temp    =   temp->getNext();
+        } 
+        reducedLPolys   =   reduction(sPolyList, completed, gPrev, rules, lTag, rTag, gbPrev);
+    }
+    Print("HIER123\n");
+    Print("%p\n",rules->getFirst());
+    Print("%p\n",rTag->getFirst());
+    if(rules->getFirst() != rTag->getFirst()) {
+        Print("+++++++++++++++++++++++++++++++++++++NEW RULES+++++++++++++++++++++++++++++++++++++\n");
+        rTag->insert(rules->getFirst());
+    }
+    else {
+        Print("+++++++++++++++++++++++++++++++++++NO NEW RULES++++++++++++++++++++++++++++++++++++\n");
+    }
+    lTag->insert(gPrev->getFirst());
     return gPrev;
 }
@@ -116 +133 @@
 ================================================================
 */
-CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag) {
+CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules) {
     // initialization for usage in pLcm()
     number nOne         =   nInit(1);
@@ -143 +160 @@
         // testing both new labels by the F5 Criterion
         if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) && 
-           !criterion2(u1, first, rTag) && !criterion2(u2, l, rTag)) {
+           !criterion2(u1, first, rules, rTag) && !criterion2(u2, l, rules, rTag)) {
             // if they pass the test, add them to CList critPairs, having the LPoly with greater
             // label as first element in the CPair
@@ -182 +199 @@
         // save the monom t1*label_term(l) as it is tested various times in the following
     poly u1 = ppMult_qq(*t,l->getTerm());
-    while(NULL != testNode) {
+    while(NULL != testNode && NULL != testNode->getLPoly()) {
         if(pLmDivisibleByNoComp(testNode->getPoly(),u1)) {
             Print("Criterion 1 NOT passed!\n");
@@ -189 +206 @@
         //pWrite(testNode->getNext()->getPoly());
                 testNode    =   testNode->getNext();
+        Print("ADDRESS OF TEST NODE: %p\n",testNode);
+    Print("Hier\n");
     }
     Print("HIER DRIN CRITERION 1\n");
@@ -202 +221 @@
 =====================================
 */
-bool criterion2(poly* t, LNode* l, RTagList* rTag) {
+bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag) {
         Print("HIER DRIN CRITERION 2:=========================\n");
     // start at the previously added element to gPrev, as all other elements will have the same index for sure
-        RNode* testNode =   rTag->get(l->getIndex());
-    Print("ADDRESS TEST NODE: %p\n", testNode);
+        Print("%d\n",l->getIndex());
+    RNode* testNode =   new RNode();
+    if(NULL == rTag->getFirst()->getRule()) {
+        testNode    =   rules->getFirst();
+    }
+    else {
+        Print("%d\n",l->getIndex());
+        Print("%d\n",rTag->getFirst()->getRuleIndex());
+pWrite(rTag->getFirst()->getRuleTerm());
+        if(l->getIndex() > rTag->getFirst()->getRuleIndex()) {
+            testNode    =   rules->getFirst();
+            Print("TEST NODE: %p\n",testNode);
+        }
+        else {
+            testNode    =   rTag->get(l->getIndex());
+        }
+    }
         // save the monom t1*label_term(l) as it is tested various times in the following
     poly u1 = ppMult_qq(*t,l->getTerm());
-        Print("Poly u1: ");
         pWrite(u1);
     // first element added to rTag was NULL, check for this
-    while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule()->getOrigin() != l->getLPoly()) {
-        Print("----------------------------------------------------------------------------------------------------------------------------------------------------\n");
+    pWrite(l->getPoly());
+    //Print("%p\n",testNode->getRule());
+    Print("HIER !!!!\n");
+    // NOTE: testNode is possibly NULL as rTag->get() returns NULL for elements of index <=1!
+    while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != l->getRule() 
+          && l->getIndex() == testNode->getRuleIndex()) {
                 pWrite(ppMult_qq(*t,l->getTerm()));
                 pWrite(testNode->getRuleTerm());
@@ -220 +257 @@
             return true;
         }
-    Print("HIER AUCH DRIN?\n");
-                Print("TEST NODE ADDRESS: %p\n",testNode->getNext());
-                Print("TEST NODE LPOLY ADDRESS: %p\n",testNode->getNext()->getRule());
                 testNode    =   testNode->getNext();
     }
@@ -235 +269 @@
 =================================================================================================================
 */
-bool criterion2(poly* t, LPoly* l, RTagList* rTag, Rule* lastRuleTested) {
+bool criterion2(poly* t, LPoly* l, RList* rules, 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();
+        RNode* testNode =   rules->getFirst();
     // save the monom t1*label_term(l) as it is tested various times in the following
     poly u1 = ppMult_qq(*t,l->getTerm());
         // first element added to rTag was NULL, check for this
-        while(NULL != testNode && NULL != testNode->getRule() && testNode->getRule() != lastRuleTested) {
+        while(NULL != testNode->getRule() && l->getRule() != lastRuleTested) {
         if(pLmDivisibleBy(testNode->getRuleTerm(),ppMult_qq(*t,l->getTerm()))) {
             Print("Criterion 2 NOT passed!\n");
@@ -259 +293 @@
 */
 void computeSPols(CNode* first, RTagList* rTag, RList* rules, LList* sPolyList) { 
-    CNode* temp =   first;
-    poly zero   =   pInit();
+    CNode* temp         =   first;
+    static poly sp      =   pInit();
+    Print("###############################IN SPOLS##############################\n");
     while(NULL != temp->getData()) {
         // only if a new rule was added since the last test in subalgorithm criticalPair()
-        if(rules->getFirst() != rTag->getFirst()) {
+        //if(rules->getFirst() != rTag->getFirst()) {
             Print("IN SPOLS => NEW RULES AVAILABLE\n");
-            if(!criterion2(temp->getAdT1(),temp->getAdLp1(),rTag,temp->getLastRuleTested())) {
+            if(!criterion2(temp->getAdT1(),temp->getAdLp1(),rules,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())) {
+                    if(!criterion2(temp->getAdT2(),temp->getAdLp2(),rules,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");
+                        Print("BEGIN SPOLY1\n====================\n");
                         pWrite(sp);
-                        Print("END SPOLY\n====================\n");
-                        if(!pCmp(sp,zero)) {
+                        Print("END SPOLY1\n====================\n");
+                        if(NULL == sp) {
                             // as rules consist only of pointers we need to save the labeled
                             // S-polynomial also of a zero S-polynomial
@@ -286 +320 @@
                             Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
                                                         reductionsToZero++;
-                            rules->insert(temp->getLp1Index(),temp->getT1(),NULL);
-                            rTag->setFirst(rules->getFirst());
+                            rules->insert(temp->getLp1Index(),temp->getT1());
+                            // as sp = NULL, delete it
+                            delete(&sp);
                         }
                         else {
-                            sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp);
-                            rules->insert(temp->getLp1Index(),temp->getT1(),sPolyList->getFirst()->getLPoly());
-                            rTag->setFirst(rules->getFirst());
+                            rules->insert(temp->getLp1Index(),temp->getT1());
+                            sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
                         }
                         // 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");
+                    Print("BEGIN SPOLY2\n====================\n");
                     pWrite(sp);
-                    Print("END SPOLY\n====================\n");
-                    if(!pCmp(sp,zero)) {
+                    Print("END SPOLY2\n====================\n");
+                    if(NULL == sp) {
                         // zeroList->insert(temp->getAdT1(),temp->getLp1Index(),&sp);
                         // origin of rule can be set NULL as the labeled polynomial
@@ -313 +345 @@
                             Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
                         reductionsToZero++;
-                        rules->insert(temp->getLp1Index(),temp->getT1(),NULL);
-                        rTag->setFirst(rules->getFirst());
-
+                        rules->insert(temp->getLp1Index(),temp->getT1());
+                        // as sp = NULL, delete it
+                        delete(&sp);
                     }
                     else {
-                        sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp);
-                        rules->insert(temp->getLp1Index(),temp->getT1(),sPolyList->getFirst()->getLPoly());
-                        rTag->setFirst(rules->getFirst());
+                        rules->insert(temp->getLp1Index(),temp->getT1());
+                        sPolyList->insert(temp->getT1(),temp->getLp1Index(),sp,rules->getFirst()->getRule());
                     }
                     // 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
+    //pDelete(&sp);
     delete first;    
 }
@@ -341 +372 @@
 ========================================================================
 */
-LNode* reduction(LList* sPolyList, LList* completed, LList* gPrev, LTagList* lTag, RTagList* rTag, 
+LList* reduction(LList* &sPolyList, LList* &completed, LList* &gPrev, RList* &rules, LTagList* &lTag, RTagList* &rTag, 
                  ideal gbPrev) { 
+    Print("##########################################In REDUCTION!########################################\n");
     // temporary normal form and zero polynomial for testing
     poly tempNF =   pInit();
-    poly zero   =   pInit();  
+    TopRed* ret =   new TopRed();
     // compute only if there are any S-polynomials to be reduced
+    Print("LENGTH OF SPOLYLIST: %d\n",sPolyList->getLength());
     if(NULL != sPolyList->getFirst()->getLPoly()) {
         LNode* temp =   sPolyList->getFirst();
+        Print("HIER REDUCTION\n");
         while(NULL != temp->getLPoly()) {
-            poly test   =   temp->getPoly();
-            Print("ADDRESS BEFORE:  %p\n",&test);
             tempNF = kNF(gbPrev,currQuotient,temp->getPoly());  
+            pWrite(tempNF);
+            pWrite(temp->getPoly());
             temp->setPoly(tempNF);
-            Print("ADDRESS AFTER:  %p\n",&test);
-            Print("Nach NORMAL FORM: ");
             pWrite(temp->getPoly());
             // test if normal form is zero
-            if(0 == pLmCmp(temp->getPoly(),zero)) {
-            Print("HIER\n");
-                            Print("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ZERO REDUCTION~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
+            if(NULL == tempNF) {
                 reductionsToZero++;
                 // TODO: sPolyList -> delete first element of list as it is zero and done
-                
-                temp = temp->getNext();
                 // TODO: problem is that when deleting the first element, the origin of the 
                 // corresponding rule is deleted!
+                temp    =   temp->getNext();
                 //sPolyList->setFirst(temp);
+                Print("///////////////////////////////////////////////////////////////////////\n");
+                Print("%p\n",temp);
+                Print("%p\n",temp->getLPoly());
+                Print("///////////////////////////////////////////////////////////////////////\n");
             }
             else {
-            //Print("HIER\n");
-                topReduction(temp, completed, gPrev, lTag, rTag);
+                ret =   topReduction(temp, completed, gPrev, rules, lTag, rTag);
                 // 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;
+                completed   =   ret->getCompleted();
+            Print("~~~HIER~~~\n");
+                if(NULL != ret->getToDo()) {
+                    sPolyList->insertByLabel(ret->getToDo()->getFirst());
+                }
+            }
+        }
+    }
+    return ret->getCompleted();
 }    
 
@@ -391 +427 @@
 =====================================================================================
 */
-void topReduction(LNode* l, LList* completed, LList* gPrev, LTagList* lTag, RTagList* rTag) {
-    Print("In topREDUCTION!\n");
-    LRed* red   =   new LRed();
+TopRed* topReduction(LNode* l, LList* &completed, LList* &gPrev, RList* &rules, LTagList* &lTag, RTagList* &rTag) {
+    Print("##########################################In topREDUCTION!########################################\n");
+    LNode* red   =   new LNode();
     do {
-        red  =   findReductor(l, completed, gPrev, lTag, rTag, 
+        red  =   findReductor(l, completed, gPrev, rules, lTag, rTag, 
                               red->getGPrevRedCheck(), red->getCompletedRedCheck());
+            Print("HIER TOP RED\n");
         // no reductor found
         if(NULL == red) {
+            pWrite(l->getPoly());
             pNorm(l->getPoly());
+            pWrite(l->getPoly());
+            Print("________________________INSERT IN COMPLETED!____________________________\n");
             completed->insert(l->getLPoly());
-            
+            Print("%p\n",completed->getFirst()->getLPoly());
+            pWrite(completed->getFirst()->getPoly());
+            TopRed* ret =   new TopRed(completed,NULL);
+            return ret;
         }
         // reductor found
@@ -421 +464 @@
 =====================================================================
 */
-LRed* findReductor(LNode* l,LList* completed,LList* gPrev,LTagList* lTag,RTagList* rTag,
+LNode* findReductor(LNode* l,LList* &completed,LList* &gPrev, RList* &rules, LTagList* &lTag,RTagList* &rTag,
                     LNode* gPrevRedCheck, LNode* completedRedCheck) {
     number nOne     =   nInit(1);
@@ -429 +472 @@
     LNode* temp     =   new LNode();
     // setting starting point for search of reductors in gPrev
+    Print("----------------------------------------------------------------------------%p\n",completed->getFirst()->getLPoly());
     if(NULL != gPrevRedCheck) { 
         temp =   gPrevRedCheck;
@@ -436 +480 @@
     }
     // search only for reductors with the same index, as reductions with elements of lower
-    // index where already done in reduction() beforehand
+    // index were already done in reduction() beforehand
     while(NULL != temp->getLPoly() && temp->getIndex() == l->getIndex()) {
         // divides head term t?
+        Print("HIER FIND\n");
         if(pLmDivisibleByNoComp(temp->getPoly(),t)) {
             u       =   pDivide(t,pHead(temp->getPoly()));
@@ -452 +497 @@
             if(pLmCmp(u,l->getTerm()) != 0) {
                 // passing criterion 2?
+                if(!criterion2(&u,temp, rules, rTag)) {
+                    // passing criterion 1?
                 Print("HIER DRIN\n");
-                if(!criterion2(&u,temp,rTag)) {
-                    // passing criterion 1?
                     if(!criterion1(&u,temp,lTag)) {
                         // set tag findRedCheck such that you can start at this point when the 
                         // next time a reductor is searched for in findReductor()
-                        LRed* red      =   new LRed(u,temp->getIndex(),redPoly,temp->getNext(),completedRedCheck);
+                        LNode* red      =   new LNode(u,temp->getIndex(),redPoly,NULL,temp->getNext(),completedRedCheck);
                         return red;
                     }
@@ -473 +518 @@
     else {
         temp    =   completed->getFirst();
+        Print("HIER FIND\n");
+        Print("%p\n",temp->getLPoly());
     }
     // search only for reductors with the same index, as reductions with elements of lower
@@ -488 +535 @@
             if(pLmCmp(u,l->getTerm()) != 0) {
                 // passing criterion 2?
-                if(!criterion2(&u,temp,rTag)) {
+                if(!criterion2(&u,temp, rules, rTag)) {
                     // passing criterion 1?
                     if(!criterion1(&u,temp,lTag)) {
                         // set tag findRedCheck such that you can start at this point when the 
                         // next time a reductor is searched for in findReductor()
-                        LRed* red      =   new LRed(u,temp->getIndex(),redPoly,gPrevRedCheck,temp->getNext());
+                        LNode* red      =   new LNode(u,temp->getIndex(),redPoly,NULL,gPrevRedCheck,temp->getNext());
                         return red;
                     }
@@ -503 +550 @@
 
     // no reductor found
+    Print("HIER DU NULL!\n");
     return NULL;
 }
@@ -515 +563 @@
 ideal F5main(ideal id, ring r) {
     int i,j;
-    //static int* reductionsToZero   =   new int;
-    //*reductionsToZero       =   0;
+    int gbLength;
     // 1 polynomial for defining initial labels & further tests
     poly ONE = pOne();
+    // tag the first element of index i-1 for criterion 1 
+    LTagList* lTag  =   new LTagList();
+    Print("LTAG BEGINNING: %p\n",lTag->getFirst());
+    
+    // first element in rTag is first element of rules which is NULL RNode, 
+    // this must be done due to possible later improvements
+    RList* rules    =   new RList();
+    RTagList* rTag  =   new RTagList(rules->getFirst());
     i = 1;
-        poly* lcm = new poly;
-    // initialization for usage in pLcm()
-    *lcm = pOne();
-    pWrite(*lcm); 
-    // definition of one-polynomial as global constant ONE
-    //poly one = pInit();
-    //pSetCoeff(one, nInit(1));
-    //static poly ONE = one;
-    
     for(j=0; j<IDELEMS(id); j++) {
         if(NULL != id->m[j]) { 
@@ -539 +585 @@
         }
     } 
-    pLcm( id->m[0], id->m[1], *lcm);
-    Print("LCM NEU\n");
-    //*lcm = pHead(*lcm);
-    //pWrite(*lcm);
-    Print("\n\n"); 
-    id = kInterRed(id,0);  
-    qsortDegree(&id->m[0],&id->m[IDELEMS(id)-1]);
-    idShow(id);
     LList* gPrev    =   new LList(ONE, i, id->m[0]);
-    int gbLength    =   gPrev->getLength();
-    pWrite(id->m[0]);
-    poly p = pHead(id->m[0]);
-    pWrite(p);
-    poly q = pHead(id->m[2]);
-    pWrite(q);
-    
+    lTag->insert(gPrev->getFirst());
     // computing the groebner basis of the elements of index < actual index
+    gbLength    =   gPrev->getLength();
     Print("Laenge der bisherigen Groebner Basis: %d\n",gPrev->getLength());
     ideal gbPrev    =   idInit(gbLength,1);
@@ -564 +597 @@
 
     for(i=2; i<=IDELEMS(id); i++) {
-        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE);
+        gPrev   =   F5inc(i, id->m[i-1], gPrev, gbPrev, ONE, lTag, rules, rTag);
         // comuting new groebner basis gbPrev
         ideal gbAdd =   idInit(gPrev->getLength()-gbLength,1);

kernel/f5gb.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.h,v 1.23 2009-02-08 19:17:54 ederc Exp $ */
+/* $Id: f5gb.h,v 1.24 2009-02-11 21:24:07 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -35 +35 @@
 ==================================================
 */
-LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE);
+LList* F5inc(int i, poly f_i, LList* gPrev, ideal gbPrev, poly ONE, LTagList* lTag, RList* rules, RTagList* rTag);
 
 /*
@@ -44 +44 @@
 ================================================================
 */
-CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag);
+CList* criticalPair(LList* gPrev, CList* critPairs, LTagList* lTag, RTagList* rTag, RList* rules);
 
 /*
@@ -58 +58 @@
 =====================================
 */
-bool criterion2(poly* t, LNode* l, RTagList* rTag);
+bool criterion2(poly* t, LNode* l, RList* rules, RTagList* rTag);
 
 /*
@@ -65 +65 @@
 ==========================================================================================================
 */
-bool criterion2(poly* t, LPoly* l, RTagList* rTag, Rule* lastRuleTested);
+bool criterion2(poly* t, LPoly* l, RList* rules, Rule* lastRuleTested);
 
 /*
@@ -79 +79 @@
 ========================================================================
 */
-LNode* reduction(LList* sPolyList, LList* completed, LList* gPrev, LTagList* lTag, RTagList* rTag,
+LList* reduction(LList* &sPolyList, LList* &completed, LList* &gPrev, RList* &rules, LTagList* &lTag, RTagList* &rTag,
                  ideal gbPrev);
 
@@ -88 +88 @@
 =====================================================================================
 */
-void topReduction(LNode* l, LList* completed, LList* gPrev, LTagList* lTag, RTagList* rTag); 
+TopRed* topReduction(LNode* l, LList* &completed, LList* &gPrev, RList* &rules, LTagList* &lTag, RTagList* &rTag); 
 
 /*
@@ -95 +95 @@
 =====================================================================
 */
-LRed* findReductor(LNode* l,LList* completed,LList* gPrev,LTagList* lTag,RTagList* rTag,
+LNode* findReductor(LNode* l,LList* &completed,LList* &gPrev, RList* &rules, LTagList* &lTag,RTagList* &rTag,
                     LNode* gPrevRedCheck, LNode* completedRedCheck);
 
 /*
 ======================================
-main function of our f5 implementation
+main function of our F5 implementation
 ======================================
 */

kernel/f5lists.cc

@@ -27 +27 @@
 // generating new list elements (labeled / classical polynomial / LNode view)
 LNode::LNode() {
-    data = NULL;
-    next = NULL;
+    data                =   NULL;
+    next                =   NULL;
+    gPrevRedCheck       =   NULL;
+    completedRedCheck   =   NULL;
 }
  LNode::LNode(LPoly* lp) {
-    data = lp;
-    next = NULL;
+    data                =   lp;
+    next                =   NULL;
+    gPrevRedCheck       =   NULL;
+    completedRedCheck   =   NULL;
 }
        
 LNode::LNode(LPoly* lp, LNode* l) {
-    data = lp;
-    next = l;
-}
-LNode::LNode(poly t, int i, poly p) {
-    LPoly* lp = new LPoly(t,i,p);
-    data = lp;
-    next = NULL;
+Print("HIER LNODE\n");
+    data                =   lp;
+    next                =   l;
+    gPrevRedCheck       =   NULL;
+    completedRedCheck   =   NULL;
+}
+
+LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* CompCheck) {
+LPoly* lp = new LPoly(t,i,p,r);
+data                =   lp;
+next                =   NULL;
+gPrevRedCheck       =   gPCheck;
+completedRedCheck   =   CompCheck;
 }
        
-LNode::LNode(poly t, int i, poly p, LNode* l) {
-    LPoly* lp = new LPoly(t,i,p);
-    data = lp;
-    next = l;
+LNode::LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* CompCheck, LNode* l) {
+    LPoly* lp           =   new LPoly(t,i,p,r);
+    data                =   lp;
+    next                =   l;
+    gPrevRedCheck       =   gPCheck;
+    completedRedCheck   =   CompCheck;
 }
 
  LNode::LNode(LNode* ln) {
-    data = ln->getLPoly();
-    next = ln->getNext();
+    data                =   ln->getLPoly();
+    next                =   ln->getNext();
+    gPrevRedCheck       =   NULL;
+    completedRedCheck   =   NULL;
 }
         
 LNode::~LNode() {
     delete next;
+    delete gPrevRedCheck;
+    delete completedRedCheck;
     delete data;   
 }
@@ -63 +79 @@
 // insert new elements to the list always in front (labeled / classical polynomial view)
 LNode* LNode::insert(LPoly* lp) {
+    Print("HIER\n");
     LNode* newElement = new LNode(lp, this);
     return newElement;
 }
         
-LNode* LNode::insert(poly t, int i, poly p) {
-    LNode* newElement = new LNode(t, i, p, this);
+LNode* LNode::insert(poly t, int i, poly p, Rule* r) {
+    LNode* newElement = new LNode(t, i, p, r, NULL, NULL, this);
     return newElement;
 }
@@ -74 +91 @@
 // 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(poly t, int i, poly p) {
+LNode* LNode::insertByLabel(poly t, int i, poly p, Rule* r) {
     if(0 == pLmCmp(t,this->getTerm()) || -1 == pLmCmp(t,this->getTerm())) {
-        LNode* newElement   =   new LNode(t, i, p, this);
+        LNode* newElement   =   new LNode(t, i, p, r, this);
         return newElement;
     }
@@ -83 +100 @@
         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);
+                LNode* newElement   =   new LNode(t, i, p, r, temp->next);
                 temp->next          =   newElement;
                 return this;
@@ -91 +108 @@
             }
         }
-        LNode* newElement   =   new LNode(t, i, p, NULL);
+        LNode* newElement   =   new LNode(t, i, p, r, NULL);
         temp->next          =   newElement;
         return this;
@@ -126 +143 @@
 }
 
+Rule* LNode::getRule() {
+    return data->getRule();
+}
+
+LNode* LNode::getGPrevRedCheck() {
+    return gPrevRedCheck;
+}
+
+LNode* LNode::getCompletedRedCheck() {
+    return completedRedCheck;
+}
+
 // set the data from the LPoly saved in LNode
 void LNode::setPoly(poly p) {
@@ -137 +166 @@
 void LNode::setIndex(int i) {
     data->setIndex(i);
+}
+
+void LNode::setGPrevRedCheck(LNode* l) {
+    gPrevRedCheck   =   l;
+}
+
+void LNode::setCompletedRedCheck(LNode* l) {
+    completedRedCheck   =   l;
 }
 
@@ -171 +208 @@
 }
 
-LList::LList(poly t,int i,poly p) {
-    first   =   new LNode(t,i,p);
+LList::LList(poly t,int i,poly p,Rule* r) {
+    first   =   new LNode(t,i,p,r);
     length  =   1;
 } 
@@ -186 +223 @@
 }
 
-void LList::insert(poly t,int i, poly p) {
-    first = first->insert(t,i,p);
+void LList::insert(poly t,int i, poly p, Rule* r) {
+    first = first->insert(t,i,p,r);
     length++;
 }
 
-void LList::insertByLabel(poly t, int i, poly p) {
-    first = first->insertByLabel(t,i,p);
+void LList::insertByLabel(poly t, int i, poly p, Rule* r) {
+    first = first->insertByLabel(t,i,p,r);
+    length++;
+}
+
+void LList::insertByLabel(LNode* l) {
+    first = first->insertByLabel(l->getTerm(),l->getIndex(),l->getPoly(),l->getRule());
     length++;
 }
@@ -222 +264 @@
 }
 
-/*
-===================================
-functions working on the class LRed
-===================================
-*/
-LRed::LRed() {
-    data                =   NULL;
-    gPrevRedCheck       =   NULL;
-    completedRedCheck   =   NULL;
-}
-
-LRed::LRed(poly t,int i,poly p,LNode* g, LNode* c) {
-    LPoly* lp           =   new LPoly(t,i,p);
-    data                =   lp;
-    gPrevRedCheck       =   g;
-    completedRedCheck   =   c;
-}
-
-LPoly* LRed::getLPoly() {
-    return data;
-}
-
-LNode* LRed::getGPrevRedCheck() {
-    return gPrevRedCheck;
-}
-
-LNode* LRed::getCompletedRedCheck() {
-    return completedRedCheck;
-}
-
-// get the data from the LPoly saved in LNode
-poly LRed::getPoly() {
-    return data->getPoly();
-}
-
-poly LRed::getTerm() {
-    return data->getTerm();
-}
-
-int LRed::getIndex() {
-    return data->getIndex();
-}
-
-// set the data from the LPoly saved in LNode
-void LRed::setPoly(poly p) {
-    data->setPoly(p);
-}
-
-void LRed::setTerm(poly t) {
-    data->setTerm(t);
-}
-
-void LRed::setIndex(int i) {
-    data->setIndex(i);
-}
 
 
@@ -284 +271 @@
 =======================================
 */
+LTagNode::LTagNode() {
+    data    =   NULL;
+    next    =   NULL;
+}
 
 LTagNode::LTagNode(LNode* l) {
@@ -333 +324 @@
 =======================================
 */
+LTagList::LTagList() {
+    LTagNode* first =   new LTagNode();
+    length          =   0;
+}
 
 LTagList::LTagList(LNode* l) {
@@ -347 +342 @@
 LNode* LTagList::get(int idx) {
     return first->get(idx, length);
+}
+
+LNode* LTagList::getFirst() {
+    return first->getLNode();
+}
+
+
+/*
+=====================================
+functions working on the class TopRed
+=====================================
+*/
+
+TopRed::TopRed() {
+    _completed  =   NULL;
+    _toDo       =   NULL;
+}
+
+TopRed::TopRed(LList* c, LList* t) {
+    _completed  =   c;
+    _toDo       =   t;
+}
+
+LList* TopRed::getCompleted() {
+    return _completed;
+}
+
+LList* TopRed::getToDo() {
+    return _toDo;
 }
 
@@ -635 +659 @@
 }
 
-RNode* RNode::insert(int i, poly t, LPoly* l) {
-    Rule*   r           =   new Rule(i,t,l);
+RNode* RNode::insert(int i, poly t) {
+    Rule*   r           =   new Rule(i,t);
     RNode* newElement   =   new RNode(r);
     newElement->next    =   this;
@@ -658 +682 @@
 }
 
-LPoly* RNode::getRuleOrigin() {
-    return data->getOrigin();
-}
-
 /*
 ====================================
@@ -675 +695 @@
 }
 
-void RList::insert(int i, poly t, LPoly* l) {
-    first = first->insert(i,t,l);
+void RList::insert(int i, poly t) {
+    first = first->insert(i,t);
 }
 
@@ -734 +754 @@
 RNode* RTagNode::get(int idx, int length) {
     if(idx==1 || idx==0) {
+        // NOTE: We set this NULL as putting it the last element in the list, i.e. the element having
+        //       RNode* = NULL would cost lots of iterations at each step of F5inc, with increasing
+        //       length of the list this should be prevented
         return NULL;
     }
@@ -739 +762 @@
         int j;
         RTagNode* temp = this; 
-        for(j=1; j<=length-idx+1; j++) {
+    Print("\n\nHIER IN GET IDX\n");
+    Print("FOR LOOP: %d\n",length-idx+1);    
+    for(j=1; j<=length-idx+1; j++) {
             temp = temp->next;
         }
@@ -750 +775 @@
 }
 
+void RTagNode::print() {
+    RTagNode* temp  =   this;
+    Print("1. element: %d",getRNode()->getRule()->getIndex());
+    pWrite(getRNode()->getRule()->getTerm());
+    temp    =   temp->next;
+    int i   =   2;
+    while(NULL != temp->getRNode()) {
+        Print("%d. element: %d",i,getRNode()->getRule()->getIndex());
+        pWrite(getRNode()->getRule()->getTerm());
+        temp    =   temp->next;
+        i++;
+    }
+}
 /*
 =======================================
@@ -769 +807 @@
 void RTagList::insert(RNode* r) {
     first = first->insert(r);
-    length++;
+    Print("LENGTH:%d\n",length);
+    length = length +1;
+    Print("LENGTH:%d\n",length);
 }
 
@@ -783 +823 @@
     first->set(r);
 }
+
+void RTagList::print() {
+    first->print();
+}
+
+int RTagList::getLength() {
+    return length;
+}
 #endif

kernel/f5lists.h

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5lists.h,v 1.7 2009-02-08 19:17:54 ederc Exp $ */
+/* $Id: f5lists.h,v 1.8 2009-02-11 21:24:08 ederc Exp $ */
 /*
 * ABSTRACT: list interface
@@ -20 +20 @@
 class LNode;
 class LList;
-class LRed;
 class LTagNode;
 class LTagList;
@@ -38 +37 @@
 class LNode {
     private:
-        LPoly* data;
-        LNode* next;
+        LPoly*  data;
+        LNode*  next;
+        LNode*  gPrevRedCheck;
+        LNode*  completedRedCheck;
     public:
         // generating new list elements from the labeled / classical polynomial view
@@ -45 +46 @@
                 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, Rule* r=NULL, LNode* gPCheck=NULL, LNode* CompCheck=NULL);
+                LNode(poly t, int i, poly p, Rule* r, LNode* gPCheck, LNode* CompCheck, 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, Rule* r);
         // 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(poly t, int i, poly p);
+        LNode*  insertByLabel(poly t, int i, poly p, Rule* r);
         // deletes the first elements of the list with the same degree
         // get next from current LNode
@@ -66 +67 @@
         poly    getTerm();
         int     getIndex(); 
+        Rule*   getRule();
+        LNode*  getGPrevRedCheck();
+        LNode*  getCompletedRedCheck();
         // set the data from the LPoly saved in LNode
         void    setPoly(poly p);
         void    setTerm(poly t);
         void    setIndex(int i);
+        void    setGPrevRedCheck(LNode* l);
+        void    setCompletedRedCheck(LNode* l);
         // test if for any list element the polynomial part of the data is equal to *p
         bool    polyTest(poly* p);
@@ -88 +94 @@
                 LList();
                 LList(LPoly* lp);
-                LList(poly t,int i,poly p);
+                LList(poly t,int i,poly p, Rule* r = NULL);
                 ~LList();
         void    insert(LPoly* lp);
         // insertion in front of the list
-        void    insert(poly t,int i, poly p);
-        void    insertByLabel(poly t, int i, poly p);
+        void    insert(poly t,int i, poly p, Rule* r = NULL);
+        void    insertByLabel(poly t, int i, poly p, Rule* r = NULL);
+        void    insertByLabel(LNode* l);
         void    deleteByDeg();
         bool    polyTest(poly* p);
@@ -103 +110 @@
 
 
-/*
-=========================================
-class LRed (nodes for lists of Reductors)
-=========================================
-*/
-class LRed {
-    private:
-        LPoly* data;
-        LNode* gPrevRedCheck;
-        LNode* completedRedCheck;
-    public:
-        // generating new list elements from the labeled / classical polynomial view
-                LRed();
-                LRed(poly t, int i, poly p, LNode* g, LNode* c);
-                ~LRed();
-        // get the LPoly* out of LNode*
-        LPoly*  getLPoly();
-        // get the last reductor tested in subalgorithm findReductor() in f5gb.cc 
-        LNode*  getGPrevRedCheck();
-        LNode*  getCompletedRedCheck();
-        // get data from the labeled polynomial 
-        poly    getPoly();
-        poly    getTerm();
-        int     getIndex(); 
-        // set the data from the LPoly saved in LNode
-        void    setPoly(poly p);
-        void    setTerm(poly t);
-        void    setIndex(int i);
-};
-
 
 /*
@@ -144 +121 @@
         LTagNode*   next;
     public:
+        LTagNode();
         LTagNode(LNode* l);
         LTagNode(LNode* l, LTagNode* n);
@@ -164 +142 @@
         int         length;
     public:
+                LTagList();
                 LTagList(LNode* l);
                 ~LTagList();
@@ -169 +148 @@
         void    insert(LNode* l);
         LNode*  get(int idx);
+        LNode*  getFirst();
+};
+
+LNode*  getGPrevRedCheck();
+LNode*  getcompletedRedCheck();
+
+
+/*
+======================================================================================
+class TopRed(return values of subalgorithm TopRed in f5gb.cc), i.e. the first elements 
+             of the lists LList* completed & LList* sPolyList
+======================================================================================
+*/
+class TopRed {
+    private:
+        LList*  _completed;
+        LList*  _toDo;
+    public:
+                TopRed();
+                TopRed(LList* c, LList* t);
+        LList*  getCompleted();
+        LList*  getToDo();
 };
 
@@ -243 +244 @@
                 ~RNode();
         RNode*  insert(Rule* r);
-        RNode*  insert(int i, poly t, LPoly* l);
+        RNode*  insert(int i, poly t);
         RNode*  getNext();
         Rule*   getRule();
         int     getRuleIndex();
         poly    getRuleTerm();
-        LPoly*  getRuleOrigin();
 };
 
@@ -266 +266 @@
                 ~RList();
         void    insert(Rule* r);
-        void    insert(int i, poly t, LPoly* l);
+        void    insert(int i, poly t);
         RNode*  getFirst();
         Rule*   getRule();
@@ -292 +292 @@
         RNode*      get(int idx, int length);
         void        set(RNode*);
+        void        print();
 };
 
@@ -310 +311 @@
         // 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);
         void    setFirst(RNode* r);
+        void    print();
+        int     getLength();
 };
 #endif