Index: kernel/f5gb.cc
===================================================================
--- kernel/f5gb.cc	(revision 5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b)
+++ kernel/f5gb.cc	(revision 66e7b51e7e2fb39132258de81dac745cfa224931)
@@ -2,5 +2,5 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.cc,v 1.18 2009-01-28 17:20:49 Singular Exp $ */
+/* $Id: f5gb.cc,v 1.19 2009-01-29 17:59:30 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -67,8 +67,9 @@
 ==================================================
 */
-LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE) {
+LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE, RList* rules, LTagList* lTag) {
     gPrev->insert(ONE,i,f_i);
-    CList* critPairs    =   criticalPair(gPrev);
-     
+    CList* critPairs    =   new CList();
+    critPairs           =   criticalPair(gPrev, critPairs, rules, lTag);
+    
     return gPrev;
 }
@@ -82,65 +83,54 @@
 ================================================================
 */
-CList* criticalPair(LList* gPrev) {
-    poly lcm   = pInit();
-    number n    = nInit(2);
-    nWrite(n);
-    pWrite(lcm);
+CList* criticalPair(LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag) {
     // initialization for usage in pLcm()
+    number nOne         =   nInit(1);
     LNode* first        =   gPrev->getFirst();
     LNode* l            =   gPrev->getFirst()->getNext();
-    poly t1, t2         =   pInit();
-    t1                  =   pHead(*first->getPoly());
-    poly u1             =   pOne();
-    poly u2             =   pOne();
-    CList*  critpairs   =   NULL;
+    poly* u1            =   new poly(pInit());
+    poly* u2            =   new poly(pInit());
+    poly* lcm           =   new poly(pInit());
     // computation of critical pairs
     while( NULL != l) {
         //pWrite( *(gPrev->getFirst()->getPoly()) );
         //pWrite( *(l->getPoly()) );
-        pLcm(*first->getPoly(), *l->getPoly(), t1);
-        pWrite(t1);
-        pWrite(u1);
-        pWrite(u2);
-        pSetCoeff0(lcm,n);
-        poly p = lcm; 
-        pWrite(p);
-        Print("%ld\n",pDeg(t1));
+        pLcm(first->getPoly(), l->getPoly(), *lcm);
+        pSetCoeff(*lcm,nOne);
         // computing factors u1 & u2 for new labels
-        u1  = pDivide(lcm, t1);
-        pWrite(u1);
-        pWrite(t1);
-        Print("%ld\n",pDeg(t1));
-        //pSetCoeff(u1,pGetCoeff(pOne()));
-        pWrite(u1);
-        t2  = pHead(*l->getPoly());
-        pWrite(t2);
-        // testing stuff
-        u1 = ppMult_qq(t1,t2);
-        pWrite(u1);
-        pWrite(t2);
-        Print("%ld\n",pDeg(u1));
-        Print("%ld\n",pDeg(t2));
-        u2  = pDivide(lcm, t2);
-        pSetCoeff(u2, pGetCoeff(pOne()));
-        pWrite(u2);
-        Print("%ld\n",pDeg(u2)); 
+        *u1 = pDivide(*lcm,pHead(first->getPoly()));
+        pSetCoeff(*u1,nOne);
+        *u2 = pDivide(*lcm, pHead(l->getPoly()));
+        pSetCoeff(*u2,nOne);
+        pWrite(*u2);
         // testing both new labels by the F5 Criterion
-        if(!criterion1(first, gPrev) &&
-           !criterion1(l, gPrev)) {
-            if(*first->getIndex() == *l->getIndex()) {
-                if(pMult(u1, *first->getTerm()) < pMult(u2, *l->getTerm())) {
-                    //if(!critPairs) {
-                        CPair* cp   =   new CPair(pDeg(lcm), u1, first->getLPoly(), u2, 
-                                        l->getLPoly());                   
-                    //}
-                }
-            }
-        }
-
-        Print("\n");
+        if(!criterion1(u1, first, lTag) && !criterion1(u2, l, lTag) && 
+           !criterion2(u1, first, rules) && !criterion2(u2, l, rules)) {
+            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
+            if(first->getIndex() == l->getIndex() && 
+            pMult(*u1, first->getTerm()) < pMult(*u2, l->getTerm())) {
+                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u2, 
+                                l->getLPoly(), *u1, first->getLPoly());                   
+                    critPairs->insert(cp);
+            }
+            else {
+                CPair* cp   =   new CPair(pDeg(ppMult_qq(*u2,pHead(l->getPoly()))), *u1, 
+                                first->getLPoly(), *u2, l->getLPoly());                   
+                    critPairs->insert(cp);
+            }
+        }
+        else {
+            Print("Criteria not passed\n");
+        }
+        
+        // for debugging
+        if(NULL != critPairs) {
+            critPairs->print(); 
+        }
         l   =   l->getNext();
     }
-    return NULL;
+    Print("ENDE CRITPAIRS\n");
+    return critPairs;
 }
 
@@ -150,19 +140,52 @@
 ========================================
 */
-bool criterion1(LNode* l, LList* gPrev) {
-    LNode* testNode =   l->getNext();
+bool criterion1(poly* t, LNode* l, LTagList* lTag) {
+    // start at the previously added element to gPrev, as all other elements will have the same index for sure
+    LNode* testNode =   lTag->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());
     while(NULL != testNode) {
-        while(*testNode->getIndex() == *l->getIndex()) {
+        //while(NULL != testNode && testNode->getIndex() == l->getIndex()) {
+        //    testNode = testNode->getNext();
+        //}
+        Print("%d\n", pLmDivisibleByNoComp(pHead(testNode->getPoly()),u1));
+        if(NULL != testNode && pLmDivisibleByNoComp(pHead(testNode->getPoly()),u1)) {
+            return true;
+        }
+        testNode    =   testNode->getNext();
+        
+    }
+    // 25/01/2009: TO DO -> change return value, until now no element is added to CList!
+    return false;
+}
+
+/*
+=====================================
+Criterion 2, i.e. Rewritten Criterion
+=====================================
+*/
+bool criterion2(poly* t, LNode* l, RList* rules) {
+    // start at the previously added element to gPrev, as all other elements will have the same index for sure
+    RNode* testNode =   rules->getFirst();
+    while(NULL != testNode->getRule()) {
+        while(NULL != testNode->getRule() && testNode->getRuleIndex() == l->getIndex()) {
             testNode = testNode->getNext();
         }
-    }
+        if(NULL != testNode->getRule() && 
+           pLmDivisibleByNoComp(ppMult_qq(*t,l->getTerm()),testNode->getRuleTerm())) {
+            return true;
+        }
+        testNode    =   testNode->getNext();
         
-
-    return true;
-}
+    }
+    // 25/01/2009: TO DO -> change return value, until now no element is added to CList!
+    
+    return false;
+}
+
 
 /*
 ==========================================================================
-MAIN:computes a gb of the ideal i in the ring r with our f5 implementation
+MAIN:computes a gb of the ideal i in the ring r with our F5 implementation
 ==========================================================================
 */
@@ -170,7 +193,10 @@
     int i,j;
     // 1 polynomial for defining initial labels & further tests
-    static poly ONE = pOne(); 
+    poly ONE = pOne();
+    // list of rules
+    RList* rules    =   new RList();
     i = 1;
-    LList* gPrev = new LList( &ONE, &i, &id->m[0]);
+    LList* gPrev    =   new LList( &ONE, &i, &id->m[0]);
+    LTagList* lTag  =   new LTagList(gPrev->getFirst());
     poly* lcm = new poly;
     // initialization for usage in pLcm()
@@ -205,5 +231,7 @@
     pWrite(q);
     for(i=2; i<=IDELEMS(id); i++) {
-        gPrev   =   F5inc( &i, &id->m[i-1], gPrev, &ONE );
+        gPrev   =   F5inc(&i, &id->m[i-1], gPrev, &ONE, rules, lTag);
+        lTag->insert(gPrev->getFirst());
+        Print("JA\n");
     } 
     // only for debugging
Index: kernel/f5gb.h
===================================================================
--- kernel/f5gb.h	(revision 5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b)
+++ kernel/f5gb.h	(revision 66e7b51e7e2fb39132258de81dac745cfa224931)
@@ -2,5 +2,5 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5gb.h,v 1.17 2009-01-28 17:20:53 Singular Exp $ */
+/* $Id: f5gb.h,v 1.18 2009-01-29 17:59:30 ederc Exp $ */
 /*
 * ABSTRACT: f5gb interface
@@ -35,5 +35,5 @@
 ==================================================
 */
-LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE);
+LList* F5inc(int* i, poly* f_i, LList* gPrev, poly* ONE, RList* rules, LTagList* lTag);
 
 /*
@@ -44,5 +44,5 @@
 ================================================================
 */
-CList* criticalPair(LList* gPrev);
+CList* criticalPair(LList* gPrev, CList* critPairs, RList* rules, LTagList* lTag);
 
 /*
@@ -51,5 +51,13 @@
 ========================================
 */
-bool criterion1(LNode* l, LList* gPrev);
+bool criterion1(poly* t, LNode* l, LTagList* lTag);
+
+/*
+=====================================
+Criterion 2, i.e. Rewritten Criterion
+=====================================
+*/
+bool criterion2(poly* t, LNode* l, RList* rules);
+
 /*
 ======================================
Index: kernel/f5lists.cc
===================================================================
--- kernel/f5lists.cc	(revision 5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b)
+++ kernel/f5lists.cc	(revision 66e7b51e7e2fb39132258de81dac745cfa224931)
@@ -31,4 +31,8 @@
 }
        
+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);
@@ -37,5 +41,11 @@
 }
        
-LNode::LNode(LNode* ln) {
+LNode::LNode(poly* t, int* i, poly* p, LNode* l) {
+    LPoly* lp = new LPoly(t,i,p);
+    data = lp;
+    next = l;
+}
+
+ LNode::LNode(LNode* ln) {
     data = ln->getLPoly();
     next = ln->getNext();
@@ -49,12 +59,10 @@
 // insert new elements to the list always in front (labeled / classical polynomial view)
 LNode* LNode::insert(LPoly* lp) {
-    LNode* newElement = new LNode(lp);
-    newElement->next = this;
+    LNode* newElement = new LNode(lp, this);
     return newElement;
 }
         
 LNode* LNode::insert(poly* t, int* i, poly* p) {
-    LNode* newElement = new LNode(t,i,p);
-    newElement->next = this;
+    LNode* newElement = new LNode(t, i, p, this);
     return newElement;
 }
@@ -64,6 +72,5 @@
 LNode* LNode::insertByLabel(LPoly* lp) {
     if( lp->getTerm() <= this->data->getTerm() ) {
-        LNode* newElement   =   new LNode(lp);
-        newElement->next    =   this;
+        LNode* newElement   =   new LNode(lp, this);
         return newElement;
     }
@@ -72,6 +79,5 @@
         while( NULL != temp->next ) {
             if( lp->getTerm() <= temp->next->data->getTerm() ) {
-                LNode* newElement   =   new LNode(lp);
-                newElement->next    =   temp->next;
+                LNode* newElement   =   new LNode(lp, temp->next);
                 temp->next          =   newElement;
                 return this;
@@ -81,7 +87,6 @@
             }
         }
-        LNode* newElement   =   new LNode(lp);
+        LNode* newElement   =   new LNode(lp, NULL);
         temp->next          =   newElement;
-        newElement->next    =   NULL;
         return this;
     }
@@ -105,13 +110,13 @@
 
 // get the data from the LPoly saved in LNode
-poly* LNode::getPoly() {
+poly LNode::getPoly() {
     return data->getPoly();
 }
 
-poly* LNode::getTerm() {
+poly LNode::getTerm() {
     return data->getTerm();
 }
 
-int* LNode::getIndex() {
+int LNode::getIndex() {
     return data->getIndex();
 }
@@ -121,5 +126,5 @@
     LNode* temp = new LNode(this);
     while(NULL != temp) {
-        if(pComparePolys(*(temp->getPoly()),*p)) {
+        if(pComparePolys(temp->getPoly(),*p)) {
             return 1;
         }
@@ -182,58 +187,70 @@
 /*
 =======================================
-functions working on the class PrevNode
-=======================================
-*/
-
-PrevNode::PrevNode(LNode* l) {
+functions working on the class LTagNode
+=======================================
+*/
+
+LTagNode::LTagNode(LNode* l) {
     data = l;
     next = NULL;
 }
        
-PrevNode::~PrevNode() {
+LTagNode::LTagNode(LNode* l, LTagNode* n) {
+    data = l;
+    next = n;
+}
+
+ LTagNode::~LTagNode() {
     delete next;
     delete data;   
 }
        
-PrevNode* PrevNode::append(LNode* l) {
-    PrevNode* new_element = new PrevNode(l);
-    next = new_element;
-    return new_element;
-}
-
-LNode* PrevNode::getLNode() {
+// declaration with first as parameter due to sorting of LTagList
+LTagNode* LTagNode::insert(LNode* l) {
+    LTagNode* newElement  = new LTagNode(l, this);
+    return newElement;
+}
+
+LNode* LTagNode::getLNode() {
     return this->data;
 }
 
-LNode* PrevNode::getPrevLast(int i) {
-    int j;
-    PrevNode* temp = this;
-    for(j=1;j<=i-1;j++) {
-        temp = temp->next;
-    }
-    return temp->data;
-}
-
-/*
-=======================================
-functions working on the class PrevList
-=======================================
-*/
-
-PrevList::PrevList(LNode* l) {
-    PrevNode* first =   new PrevNode(l);
-    last            =   first;    
-}
-
-void PrevList::append(LNode* l) {
-    last = last->append(l);
-}
-
-LNode* PrevList::getPrevLast(int i) {
-    switch(i) {
-        case 0:     return NULL;
-        case 1:     return first->getLNode();
-        default:    first->getPrevLast(i);
-    }
+// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
+//       Thus given actual index i and idx being the index of the LPoly under investigation
+//       the element on position length-idx is the right one
+LNode* LTagNode::get(int idx, int length) {
+    if(idx == 1) {
+        return NULL;
+    }
+    else {
+        int j;
+        LTagNode* temp = this; // last
+        for(j=1;j<=length-idx+1;j++) {
+            temp = temp->next;
+        }
+        return temp->data;
+    }
+}
+
+
+/*
+=======================================
+functions working on the class LTagList
+=======================================
+*/
+
+LTagList::LTagList(LNode* l) {
+    LTagNode* first =   new LTagNode(l);
+    length          =   1;
+}
+
+// declaration with first as parameter in LTagNode due to sorting of LTagList
+void LTagList::insert(LNode* l) {
+    first   =   first->insert(l);
+    length++;
+}
+
+LNode* LTagList::get(int idx) {
+    return first->get(idx, length);
 }
 
@@ -243,8 +260,18 @@
 ====================================
 */
+
+CNode::CNode() {
+    data    =   NULL;   
+    next    =   NULL;    
+}
 
 CNode::CNode(CPair* c) {
     data    =   c;   
     next    =   NULL;    
+}
+
+CNode::CNode(CPair* c, CNode* n) {
+    data    =   c;   
+    next    =   n;    
 }
 
@@ -258,94 +285,98 @@
 // working only with linked, but not doubly linked lists due to memory usage we have to check the 
 // insertion around the first element separately from the insertion around all other elements in the list
-CNode* CNode::insert(CPair* c) {
-    if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
-        CNode* newElement = new CNode(c);
-        newElement->next = this;
+CNode* CNode::insert(CPair* c, CNode* last) {
+    if(NULL == this->data) {
+        CNode* newElement   =   new CNode(c, this);
         return newElement;
     }
-    if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
-        if( c->getT1() <= this->data->getT1() ) {
-            CNode* newElement   =   new CNode(c);
-            newElement->next    =   this;
+    else {
+        poly u1 = ppMult_qq(c->getT1(),c->getLp1Term());
+        if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
+            CNode* newElement   =   new CNode(c, this);
             return newElement;
         }
-        else {
-            CNode* temp = this;
-            while(  NULL != temp->next ) {
-                if( temp->next->data->getDeg() == c->getDeg() ) { 
-                    if( c->getT1() <= temp->next->data->getT1() ) {
-                        temp = temp->next;
+        if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
+            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: ");
+                pWrite(ppMult_qq(this->data->getT1(),this->data->getLp1Term()));
+                CNode* newElement   =   new CNode(c, this);
+                return newElement;
+            }
+            else {
+                Print("Insert Deg\n");
+                CNode* temp = this;
+                while(  NULL != temp->next->data ) {
+                    if(temp->next->data->getDeg() == c->getDeg() ) { 
+                        if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) {
+                            temp = temp->next;
+                        }
+                        else {
+                            CNode* newElement   =   new CNode(c, temp->next);
+                            temp->next          =   newElement;
+                            return this;
+                        } 
                     }
                     else {
-                        CNode* newElement   =   new CNode(c);
-                        newElement->next    =   temp->next;
+                        CNode* newElement   =   new CNode(c, temp->next);
                         temp->next          =   newElement;
                         return this;
-                    } 
+                    }
                 }
-                else {
-                    CNode* newElement   =   new CNode(c);
-                    newElement->next    =   temp->next;
+                CNode* newElement   =   new CNode(c, last);
+                temp->next          =   newElement;
+                return this;
+            }
+        } // outer if-clause
+        if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
+            CNode* temp =   this;
+            while( NULL != temp->next->data ) {   
+                if( c->getDeg() < temp->next->data->getDeg() ) {
+                    CNode* newElement   =   new CNode(c, temp->next);
                     temp->next          =   newElement;
                     return this;
                 }
+                if( c->getDeg() == temp->next->data->getDeg() ) {
+                    if(0 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term())) || 
+                       -1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),temp->next->data->getLp1Term()))) { 
+                        CNode* newElement   =   new CNode(c, temp->next);
+                        temp->next          =   newElement;
+                        return this;
+                    }
+                    else {
+                        temp = temp->next;
+                        while(  NULL != temp->next->data ) {
+                            if( temp->next->data->getDeg() == c->getDeg() ) { 
+                                if(1 == pLmCmp(u1,ppMult_qq(temp->next->data->getT1(),
+                                               temp->next->data->getLp1Term()))) {
+                                    temp = temp->next;
+                                }
+                                else {
+                                    CNode* newElement   =   new CNode(c, temp->next);
+                                    temp->next          =   newElement;
+                                    return this;
+                                } 
+                            }
+                            else {
+                                CNode* newElement   =   new CNode(c, temp->next);
+                                temp->next          =   newElement;
+                                return this;
+                            }
+                        }
+                        CNode* newElement   =   new CNode(c, last);
+                        temp->next          =   newElement;
+                        return this;
+                    }
+                }
+                if( c->getDeg() > temp->next->data->getDeg() ) {
+                    temp    =   temp->next;
+                }
             }
-            CNode* newElement   =   new CNode(c);
-            newElement->next    =   NULL;
+            CNode* newElement   =   new CNode(c, last);
             temp->next          =   newElement;
             return this;
         }
-    } // outer if-clause
-    if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
-        CNode* temp =   this;
-        while( NULL != temp->next ) {   
-            if( c->getDeg() < temp->next->data->getDeg() ) {
-                CNode* newElement   =   new CNode(c);
-                newElement->next    =   temp->next;
-                temp->next          =   newElement;
-                return this;
-            }
-            if( c->getDeg() == temp->next->data->getDeg() ) {
-                if( c->getT1() <= temp->next->data->getT1() ) {
-                    CNode* newElement   =   new CNode(c);
-                    newElement->next    =   temp->next;
-                    temp->next          =   newElement;
-                    return this;
-                }
-                else {
-                    temp = temp->next;
-                    while(  NULL != temp->next ) {
-                        if( temp->next->data->getDeg() == c->getDeg() ) { 
-                            if( c->getT1() <= temp->next->data->getT1() ) {
-                                temp = temp->next;
-                            }
-                            else {
-                                CNode* newElement   =   new CNode(c);
-                                newElement->next    =   temp->next;
-                                temp->next          =   newElement;
-                                return this;
-                            } 
-                        }
-                        else {
-                            CNode* newElement   =   new CNode(c);
-                            newElement->next    =   temp->next;
-                            temp->next          =   newElement;
-                            return this;
-                        }
-                    }
-                    CNode* newElement   =   new CNode(c);
-                    newElement->next    =   NULL;
-                    temp->next          =   newElement;
-                    return this;
-                }
-            }
-            if( c->getDeg() > temp->next->data->getDeg() ) {
-                temp    =   temp->next;
-            }
-        }
-        CNode* newElement   =   new CNode(c);
-        newElement->next    =   NULL;
-        temp->next          =   newElement;
-        return this;
     }
 }
@@ -354,6 +385,6 @@
 CNode* CNode::getMinDeg() {
     CNode* temp = this;
-    while( NULL != temp ) {
-        if( temp->next->data->getDeg() == this->data->getDeg() ) {
+    while( NULL != temp->data ) {
+        while( temp->next->data->getDeg() == this->data->getDeg() ) {
             temp = temp->next;
         }
@@ -365,4 +396,54 @@
 }
 
+poly CNode::getLp1Poly() {
+    return this->data->getLp1Poly();
+}
+
+poly CNode::getLp2Poly() {
+    return this->data->getLp2Poly();
+}
+
+poly CNode::getLp1Term() {
+    return this->data->getLp1Term();
+}
+
+poly CNode::getLp2Term() {
+    return this->data->getLp2Term();
+}
+
+int CNode::getLp1Index() {
+    return this->data->getLp1Index();
+}
+
+int CNode::getLp2Index() {
+    return this->data->getLp2Index();
+}
+
+poly CNode::getT1() {
+    return this->data->getT1();
+}
+
+poly CNode::getT2() {
+    return this->data->getT2();
+}
+
+// for debugging
+void CNode::print() {
+    CNode* temp = this;
+    Print("List of critical pairs:\n");
+    while(NULL != temp->data) {
+        Print("Leck mich am Arsch: ");
+        Print("Index: %d\n",temp->getLp1Index());
+        Print("T1: ");
+        pWrite(temp->getT1());
+        Print("Lp1 Term: ");
+        pWrite(temp->getLp1Term());
+        Print("%d\n",temp->getLp2Index());
+        pWrite(temp->getT2());
+        pWrite(temp->getLp2Term());
+        Print("\n");
+        temp = temp->next;
+    }
+}
 
 /*
@@ -371,6 +452,13 @@
 ====================================
 */
+// for initialization of CLists, last element alwas has data=NULL and next=NULL
+CList::CList() {
+    first   =   new CNode();
+    last    =   first;
+}
+
 CList::CList(CPair* c) {
-    first   = new CNode(c);
+    first   =   new CNode(c);
+    last    =   first;
 }
 
@@ -382,5 +470,5 @@
 // note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
 void CList::insert(CPair* c) {
-    first = first->insert(c);
+    first = first->insert(c, last);
 }
 
@@ -393,4 +481,7 @@
 }
 
+void CList::print() {
+    first->print();
+}
 
 /*
@@ -399,4 +490,9 @@
 ====================================
 */
+RNode::RNode() {
+    data    =   NULL;
+    next    =   NULL;
+}
+
 RNode::RNode(Rule* r) {
     data    =   r;
@@ -415,4 +511,20 @@
 }
 
+RNode* RNode::getNext() {
+    return next;
+}    
+
+Rule* RNode::getRule() {
+    return data;
+}
+
+int RNode::getRuleIndex() {
+    return data->getIndex();
+}
+
+poly RNode::getRuleTerm() {
+    return data->getTerm();
+}
+
 /*
 ====================================
@@ -420,4 +532,8 @@
 ====================================
 */
+RList::RList() {
+    first = new RNode();
+}
+
 RList::RList(Rule* r) {
     first = new RNode(r);
@@ -427,3 +543,83 @@
     first = first->insert(r);
 }
+
+RNode* RList::getFirst() {
+    return first;
+}
+
+Rule* RList::getRule() {
+    return this->getRule();
+}
+
+/*
+=======================================
+functions working on the class RTagNode
+=======================================
+*/
+
+RTagNode::RTagNode(RNode* r) {
+    data = r;
+    next = NULL;
+}
+       
+RTagNode::RTagNode(RNode* r, RTagNode* n) {
+    data = r;
+    next = n;
+}
+
+ RTagNode::~RTagNode() {
+    delete next;
+    delete data;   
+}
+       
+// declaration with first as parameter due to sorting of LTagList
+RTagNode* RTagNode::insert(RNode* r) {
+    Print("Hier1\n");
+    RTagNode* newElement  = new RTagNode(r, this);
+    Print("Hier2\n");
+    return newElement;
+}
+
+RNode* RTagNode::getRNode() {
+    return this->data;
+}
+
+// NOTE: We insert at the beginning of the list and length = i-1, where i is the actual index.
+//       Thus given actual index i and idx being the index of the LPoly under investigation
+//       the element on position length-idx+1 is the right one
+RNode* RTagNode::get(int idx, int length) {
+    if(idx == 1) {
+        return NULL;
+    }
+    else {
+        int j;
+        RTagNode* temp = this; 
+        for(j=1;j<=length-idx+1;j++) {
+            temp = temp->next;
+        }
+        return temp->data;
+    }
+}
+
+
+/*
+=======================================
+functions working on the class LTagList
+=======================================
+*/
+
+RTagList::RTagList(RNode* r) {
+    RTagNode* first =   new RTagNode(r);
+    length          =   1;
+}
+
+// declaration with first as parameter in LTagNode due to sorting of LTagList
+void RTagList::insert(RNode* r) {
+    first = first->insert(r);
+    length++;
+}
+
+RNode* RTagList::get(int idx) {
+    return first->get(idx, length);
+}
 #endif
Index: kernel/f5lists.h
===================================================================
--- kernel/f5lists.h	(revision 5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b)
+++ kernel/f5lists.h	(revision 66e7b51e7e2fb39132258de81dac745cfa224931)
@@ -2,5 +2,5 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: f5lists.h,v 1.1 2009-01-27 10:38:08 Singular Exp $ */
+/* $Id: f5lists.h,v 1.2 2009-01-29 17:59:30 ederc Exp $ */
 /*
 * ABSTRACT: list interface
@@ -20,14 +20,17 @@
 class LNode;
 class LList;
-class PrevNode;
-class PrevList;
+class LTagNode;
+class LTagList;
 class CNode;
 class CList;
 class RList;
 class RNode;
-
-/*
-=======================================
-LNode class (nodes for lists of LPolys)
+class RTagNode;
+class RTagList;
+
+
+/*
+=======================================
+class LNode (nodes for lists of LPolys)
 =======================================
 */
@@ -39,5 +42,7 @@
         // generating new list elements from the labeled / classical polynomial view
                 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(LNode* ln);
                 ~LNode();
@@ -56,7 +61,7 @@
         LPoly*  getLPoly();
         // get the data from the LPoly saved in LNode
-        poly*   getPoly();
-        poly*   getTerm();
-        int*    getIndex();
+        poly    getPoly();
+        poly    getTerm();
+        int     getIndex();
         // test if for any list element the polynomial part of the data is equal to *p
         bool    polyTest(poly* p);
@@ -89,35 +94,38 @@
 
 /*
-=============================================
-PrevNode class (nodes for lists of gPrevLast)
-=============================================
-*/
-class PrevNode {
+==============================================
+class LtagNode (nodes for lists of LPoly tags)
+==============================================
+*/
+class LTagNode {
     private:
         LNode*      data;
-        PrevNode*   next;
-    public:
-        PrevNode(LNode* l);
-        ~PrevNode();
-        PrevNode*   append(LNode* l);
+        LTagNode*   next;
+    public:
+        LTagNode(LNode* l);
+        LTagNode(LNode* l, LTagNode* n);
+        ~LTagNode();
+        // declaration with first as parameter due to sorting of LTagList
+        LTagNode*   insert(LNode* l);
         LNode*      getLNode();
-        LNode*      getPrevLast(int i);
-};
-
-
-/*
-====================================================
-class PrevList(lists of last node elements in gPrev)
-====================================================
-*/
-class PrevList {
-    private:
-        PrevNode*   first;
-        PrevNode*   last;
-    public:
-                PrevList(LNode* l);
-                ~PrevList();
-        void    append(LNode* l);
-        LNode*  getPrevLast(int i);
+        LNode*      get(int i, int length);
+};
+
+
+/*
+=========================================================================
+class LTagList(lists of LPoly tags, i.e. first elements of a given index)
+=========================================================================
+*/
+class LTagList {
+    private:
+        LTagNode*   first;
+        int         length;
+    public:
+                LTagList(LNode* l);
+                ~LTagList();
+        // declaration with first as parameter in LTagNode due to sorting of LTagList
+        void    insert(LNode* l);
+        LNode*  get(int idx);
 };
 
@@ -133,9 +141,19 @@
         CNode* next;
     public:
+                CNode();
                 CNode(CPair* c);
+                CNode(CPair* c, CNode* n);
                 ~CNode(); 
-        CNode*  insert(CPair* c); 
+        CNode*  insert(CPair* c, CNode* last); 
         CNode*  getMinDeg();
-        //CNode*  getLPoly() const; 
+        poly    getLp1Poly();
+        poly    getLp2Poly();
+        poly    getLp1Term();
+        poly    getLp2Term();
+        poly    getT1();   
+        poly    getT2(); 
+        int     getLp1Index();
+        int     getLp2Index();
+        void    print();
 };
 
@@ -149,10 +167,14 @@
     private:
         CNode*  first;
-    public:
+        // last alway has data=NULL and next=NULL, for initialization purposes used
+        CNode*  last;
+    public:
+                // for initialization of CLists, last element alwas has data=NULL and next=NULL
+                CList(); 
                 CList(CPair* c); 
                 ~CList(); 
         void    insert(CPair* c);
         CNode*  getMinDeg();
-
+        void    print();
 };
 
@@ -168,7 +190,12 @@
         RNode*  next;
     public:
+                RNode();
                 RNode(Rule* r);
                 ~RNode();
         RNode*  insert(Rule* r);
+        RNode*  getNext();
+        Rule*   getRule();
+        int     getRuleIndex();
+        poly    getRuleTerm();
 };
 
@@ -181,8 +208,52 @@
     private:
         RNode*  first;
-    public:
+        // last alway has data=NULL and next=NULL, for initialization purposes used
+        RNode*  last;
+    public:
+                RList();
                 RList(Rule* r);
                 ~RList();
         void    insert(Rule* r);
+        RNode*  getFirst();
+        Rule*   getRule();
+};
+
+
+
+/*
+=============================================
+class RtagNode (nodes for lists of Rule tags)
+=============================================
+*/
+class RTagNode {
+    private:
+        RNode*      data;
+        RTagNode*   next;
+    public:
+        RTagNode(RNode* r);
+        RTagNode(RNode* r, RTagNode* n);
+        ~RTagNode();
+        // declaration with first as parameter due to sorting of LTagList
+        RTagNode*   insert(RNode* r);
+        RNode*      getRNode();
+        RNode*      get(int idx, int length);
+};
+
+
+/*
+========================================================================
+class RTagList(lists of Rule tags, i.e. first elements of a given index)
+========================================================================
+*/
+class RTagList {
+    private:
+        RTagNode*   first;
+        int         length;
+    public:
+                RTagList(RNode* r);
+                ~RTagList();
+        // declaration with first as parameter in LTagNode due to sorting of LTagList
+        void    insert(RNode* r);
+        RNode*  get(int idx);
 };
 #endif
Index: kernel/lpolynomial.cc
===================================================================
--- kernel/lpolynomial.cc	(revision 5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b)
+++ kernel/lpolynomial.cc	(revision 66e7b51e7e2fb39132258de81dac745cfa224931)
@@ -2,5 +2,5 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: lpolynomial.cc,v 1.7 2009-01-28 17:21:07 Singular Exp $ */
+/* $Id: lpolynomial.cc,v 1.8 2009-01-29 17:59:30 ederc Exp $ */
 /*
 * ABSTRACT: lpolynomial definition 
@@ -50,14 +50,14 @@
 }
 
-poly* LPoly::getPoly() {
-    return &polynomial;
+poly LPoly::getPoly() {
+    return polynomial;
 }
 
-poly* LPoly::getTerm() {
-    return &term;
+poly LPoly::getTerm() {
+    return term;
 }
 
-int* LPoly::getIndex() {
-    return &index;
+int LPoly::getIndex() {
+    return index;
 }
 
@@ -82,9 +82,10 @@
 */
 CPair::CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2) {
-   deg  =   degree;
-   t1   =   term1;
-   lp1  =   lpoly1;
-   t2   =   term2;
-   lp2  =   lpoly2;
+   deg              =   degree;
+   t1               =   term1;
+   lp1              =   lpoly1;
+   t2               =   term2;
+   lp2              =   lpoly2;
+   lastRuleTested   =   NULL;
 }
 
@@ -102,28 +103,30 @@
 
 poly CPair::getLp1Poly() {
-    return *(lp1->getPoly());
+    return lp1->getPoly();
 }
 
 poly CPair::getLp2Poly() {
-    return *(lp2->getPoly());
+    return lp2->getPoly();
 }
 
 poly CPair::getLp1Term() {
-    return *(lp1->getTerm());
+    return lp1->getTerm();
 }
 
 poly CPair::getLp2Term() {
-    return *(lp2->getTerm());
+    return lp2->getTerm();
 }
 
 int CPair::getLp1Index() {
-    return *(lp1->getIndex());
+    return lp1->getIndex();
 }
 
-
 int CPair::getLp2Index() {
-    return *(lp2->getIndex());
+    return lp2->getIndex();
 }
 
+Rule* CPair::getLastRuleTested() {
+    return lastRuleTested;
+}
 
 /*
Index: kernel/lpolynomial.h
===================================================================
--- kernel/lpolynomial.h	(revision 5376a6afb7e0e9c5e8ba37a9e7964552e94edc3b)
+++ kernel/lpolynomial.h	(revision 66e7b51e7e2fb39132258de81dac745cfa224931)
@@ -2,5 +2,5 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: lpolynomial.h,v 1.6 2009-01-25 17:13:06 ederc Exp $ */
+/* $Id: lpolynomial.h,v 1.7 2009-01-29 17:59:30 ederc Exp $ */
 /*
 * ABSTRACT: labeled polynomial interface
@@ -8,5 +8,4 @@
 #ifndef LPOLYNOMIAL_HEADER
 #define LPOLYNOMIAL_HEADER
-
 #ifdef HAVE_F5
 /*
@@ -36,9 +35,9 @@
                 LPoly(poly*t,int* i,poly* p); 
         void    setPoly(poly* p);
-        poly*   getPoly();
+        poly    getPoly();
         void    setTerm(poly* t);
-        poly*   getTerm();
+        poly    getTerm();
         void    setIndex(int* i);
-        int*    getIndex();
+        int     getIndex();
         void    setDel(bool b);
         bool    getDel() const;
@@ -46,31 +45,4 @@
         LPoly*  get();
 };
-
-
-/*
-===================================
-structure of labeled critical pairs
-===================================
-*/
-class CPair {
-    private:
-        long    deg;    // total degree of the critical pair
-        poly    t1;     // first term for label
-        LPoly*  lp1;     // first labeled poly
-        poly    t2;     // second term for label
-        LPoly*  lp2;     // second labeled poly
-    public:
-                CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
-        long    getDeg();
-        poly    getT1();
-        poly    getLp1Poly();
-        poly    getLp1Term();
-        int     getLp1Index();
-        poly    getT2();
-        poly    getLp2Poly();
-        poly    getLp2Term();
-        int     getLp2Index();
-};
-
 
 /*
@@ -88,4 +60,33 @@
         poly    getTerm();
 };
+
+
+/*
+===================================
+structure of labeled critical pairs
+===================================
+*/
+class CPair {
+    private:
+        long    deg;            // total degree of the critical pair
+        poly    t1;             // first term for label
+        LPoly*  lp1;            // first labeled poly
+        poly    t2;             // second term for label
+        LPoly*  lp2;            // second labeled poly
+        Rule*   lastRuleTested; // already tested by rules up to lastRuleTested
+    public:
+                CPair(long degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
+        long    getDeg();
+        poly    getT1();
+        poly    getLp1Poly();
+        poly    getLp1Term();
+        int     getLp1Index();
+        poly    getT2();
+        poly    getLp2Poly();
+        poly    getLp2Term();
+        int     getLp2Index();
+        Rule*   getLastRuleTested();
+};
+
 #endif
 #endif
