Changeset a0350e9 in git


Ignore:
Timestamp:
Jan 15, 2009, 6:44:24 PM (15 years ago)
Author:
Christian Eder
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
2653d3c2809f0b96d6da699e54066fdb07623b92
Parents:
5ec4a8bc9c1e8e23c5f5f95235a4e4839659b682
Message:
added lists for critical pairs


git-svn-id: file:///usr/local/Singular/svn/trunk@11321 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
kernel
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • kernel/f5gb.cc

    r5ec4a8 ra0350e9  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.cc,v 1.15 2008-12-27 13:50:05 ederc Exp $ */
     4/* $Id: f5gb.cc,v 1.16 2009-01-15 17:44:23 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    2424#include "lpolynomial.h"
    2525#include "lists.h"
    26 
    27 
    28 /*
    29 ================================================
    30 computation of ONE polynomial as global variable
    31 ================================================
    32 */
    33 poly one_poly() {
    34     poly one = pInit();
    35     pSetCoeff(one,nInit(1));
    36     return one;
    37 }
    38 
    3926
    4027
    … …  
    8067==================================================
    8168*/
    82 LList* F5inc(long* i, poly* f_i, LList* g_prev) {
    83     poly one = pInit();
    84     pSetCoeff(one, nInit(1));
    85     static poly ONE = one;
    86     //poly ONE = pOne();
     69LList* F5inc(int* i, poly* f_i, LList* g_prev, poly* ONE) {
    8770    LList* g_curr       =   g_prev;
    88     LNode* prev_last    =   g_prev->getLast(); //tags the end of g_prev->only 1 list for g_prev & g_curr
    89     g_curr->append(&ONE,i,f_i);
     71    g_curr->insert(ONE,i,f_i);
    9072   
    9173    return g_curr;
    … …  
    9880*/
    9981ideal F5main(ideal id, ring r) {
    100    
    101     static poly ONE = pOne();
    102     long i,j;
    103 
     82    int i,j;
     83    const int idElems = IDELEMS(id);
     84    // 1 polynomial for defining initial labels & further tests
     85    static poly ONE = pOne();
     86   
     87   
    10488    // definition of one-polynomial as global constant ONE
    10589    //poly one = pInit();
    … …  
    122106    idShow(id);
    123107    i = 1;
    124     //lp->setIndex(&i);
    125     //lp->setTerm(&ONE);
    126     //lp->setPoly(&id->m[0]);
    127     LPoly* lp = new LPoly(&ONE,&i,&ONE);   
    128    
    129108    // only for debugging
    130     long k = 2;
    131     LList* g_prev = new LList(&ONE,&k,&id->m[2]);
    132     LNode* current;
    133     LPoly* lp2  = new LPoly(&ONE,&k,&ONE);   
     109    //LNode* current;
    134110    //LList* g_curr = new LList(lp);
    135     k = 134;
    136     g_prev->append(&ONE,&k,&id->m[3]);
    137     g_prev->append(&ONE,&k,&id->m[3]);
    138     g_prev->append(lp2);
    139     g_prev->append(lp2);
    140     g_prev->append(lp);
    141     g_prev->append(&ONE,&k,&id->m[1]);
    142     g_prev->append(&ONE,&k,&id->m[3]);
    143     g_prev->append(lp2);
    144     i = g_prev->getLength();
    145     Print("%ld\n\n",i);
    146     current = g_prev->getFirst();
    147     while(NULL != current) {
    148     Print("Index: %ld\n",*(current->getLPoly()->getIndex()));
    149     Print("Pointer comparison: %p , %p\n\n",g_prev->getFirst(),current);
    150     current = current->getNext();
    151     }
     111    //}
    152112    //for(i=2; i<IDELEMS(id); i++) {
    153113        //g_curr = F5inc(&i,&id->m[i],g_prev);

  • kernel/f5gb.h

    r5ec4a8 ra0350e9  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: f5gb.h,v 1.14 2008-12-27 13:50:05 ederc Exp $ */
     4/* $Id: f5gb.h,v 1.15 2009-01-15 17:44:23 ederc Exp $ */
    55/*
    66* ABSTRACT: f5gb interface
    … …  
    1212#include "lpolynomial.h"
    1313#include "lists.h"
    14 
    15 
    16 /*
    17 ================================================
    18 computation of ONE polynomial as global variable
    19 ================================================
    20 */
    21 poly one_poly();
    2214
    2315
    … …  
    4537==================================================
    4638*/
    47 LList* F5inc(const long i, LList* g_prev);
     39LList* F5inc(const int i, LList* g_prev);
    4840
    4941

  • kernel/lists.cc

    r5ec4a8 ra0350e9  
    2525*/
    2626
    27 // generating new list elements in the labeled / classical polynomial / LNode view
     27// generating new list elements (labeled / classical polynomial / LNode view)
    2828LNode::LNode(LPoly* lp) {
    2929    data = lp;
    … …  
    3131}
    3232       
    33 LNode::LNode(poly* t, long* i, poly* p) {
     33LNode::LNode(poly* t, int* i, poly* p) {
    3434    LPoly* lp = new LPoly(t,i,p);
    3535    data = lp;
    36     Print("Index angelegt?  %ld\n",*(data->getIndex()));
     36    Print("Index angelegt?  %d\n",*(data->getIndex()));
    3737    next = NULL;
    3838}
    … …  
    4848}
    4949       
    50 // append new elements to the list from the labeled / classical polynomial view
    51 LNode* LNode::append(LPoly* lp) {
    52     LNode* new_element = new LNode(lp);
    53     next = new_element;
    54     return new_element;
     50// insert new elements to the list always in front (labeled / classical polynomial view)
     51LNode* LNode::insert(LPoly* lp) {
     52    LNode* newElement = new LNode(lp);
     53    newElement->next = this;
     54    return newElement;
    5555}
    5656       
    57 LNode* LNode::append(poly* t, long* i, poly* p) {
    58     LNode* new_element = new LNode(t,i,p);
    59     next = new_element;
    60     return new_element;
     57LNode* LNode::insert(poly* t, int* i, poly* p) {
     58    LNode* newElement = new LNode(t,i,p);
     59    newElement->next = this;
     60    return newElement;
    6161}
    6262       
    … …  
    7777
    7878// test if for any list element the polynomial part of the data is equal to *p
    79 bool LNode:polyTest(poly* p) {
     79bool LNode::polyTest(poly* p) {
    8080    LNode* temp = new LNode(this);
    8181    while(NULL != temp) {
    … …  
    8888}
    8989
    90 LNode* LNode::operator++() {
    91     LNode* temp= new LNode(this);
    92     return temp->getNext();
    93 }
    94 
    95 
    9690
    9791/*
    … …  
    10397LList::LList(LPoly* lp) {
    10498    first   = new LNode(lp);
    105     last    = first;
    10699    length  = 1;
    107100}
    108101
    109 LList::LList(poly* t,long* i,poly* p) {
     102LList::LList(poly* t,int* i,poly* p) {
    110103    first   = new LNode(t,i,p);
    111     last    = first;
    112104    length  = 1;
    113105}
    … …  
    117109}
    118110
    119 void LList::append(LPoly* lp) {
    120     last = last->append(lp);
     111// insertion in front of the list
     112void LList::insert(LPoly* lp) {
     113    first = first->insert(lp);
    121114    length++;
    122115}
    123116
    124 void LList::append(poly* t,long* i, poly* p) {
    125     last = last->append(t,i,p);
     117void LList::insert(poly* t,int* i, poly* p) {
     118    first = first->insert(t,i,p);
    126119    length++;
    127120}
    … …  
    131124}
    132125
    133 long LList::getLength() const {
     126int LList::getLength() const {
    134127    return length;
    135128}
    … …  
    139132}
    140133
    141 LNode* LList::getLast() {
    142     return last;
     134
     135/*
     136=======================================
     137functions working on the class PrevNode
     138=======================================
     139*/
     140
     141PrevNode::PrevNode(LNode* l) {
     142    data = l;
     143    next = NULL;
     144}
     145       
     146PrevNode::~PrevNode() {
     147    delete next;
     148    delete data;   
     149}
     150       
     151PrevNode* PrevNode::append(LNode* l) {
     152    PrevNode* new_element = new PrevNode(l);
     153    next = new_element;
     154    return new_element;
     155}
     156
     157LNode* PrevNode::getLNode() {
     158    return this->data;
     159}
     160
     161LNode* PrevNode::getPrevLast(int i) {
     162    int j;
     163    PrevNode* temp = this;
     164    for(j=1;j<=i-1;j++) {
     165        temp = temp->next;
     166    }
     167    return temp->data;
     168}
     169
     170/*
     171=======================================
     172functions working on the class PrevList
     173=======================================
     174*/
     175
     176PrevList::PrevList(LNode* l) {
     177    PrevNode* first =   new PrevNode(l);
     178    last            =   first;   
     179}
     180
     181void PrevList::append(LNode* l) {
     182    last = last->append(l);
     183}
     184
     185LNode* PrevList::getPrevLast(int i) {
     186    switch(i) {
     187        case 0:     return NULL;
     188        case 1:     return first->getLNode();
     189        default:    first->getPrevLast(i);
     190    }
     191}
     192
     193/*
     194====================================
     195functions working on the class CNode
     196====================================
     197*/
     198
     199CNode::CNode(CPair* c) {
     200    data    =   c;   
     201    next    =   NULL;   
     202}
     203
     204CNode::~CNode() {
     205    delete next;
     206    delete data;
     207}
     208
     209// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
     210// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
     211// working only with linked, but not doubly linked lists due to memory usage we have to check the
     212// insertion around the first element separately from the insertion around all other elements in the list
     213CNode* CNode::insert(CPair* c) {
     214    if( c->getDeg() < this->data->getDeg() ) { // lower degree than the first list element
     215        CNode* newElement = new CNode(c);
     216        newElement->next = this;
     217        return newElement;
     218    }
     219    if( c->getDeg() == this->data->getDeg() ) { // same degree than the first list element
     220        if( c->getT1() <= this->data->getT1() ) {
     221            CNode* newElement   =   new CNode(c);
     222            newElement->next    =   this;
     223            return newElement;
     224        }
     225        else {
     226            CNode* temp = this;
     227            while(  temp->next != NULL ) {
     228                if( temp->next->data->getDeg() == c->getDeg() ) {
     229                    if( c->getT1() <= temp->next->data->getT1() ) {
     230                        temp = temp->next;
     231                    }
     232                    else {
     233                        CNode* newElement   =   new CNode(c);
     234                        newElement->next    =   temp->next;
     235                        temp->next          =   newElement;
     236                        return this;
     237                    }
     238                }
     239                else {
     240                    CNode* newElement   =   new CNode(c);
     241                    newElement->next    =   temp->next;
     242                    temp->next          =   newElement;
     243                    return this;
     244                }
     245            }
     246            CNode* newElement   =   new CNode(c);
     247            newElement->next    =   NULL;
     248            temp->next          =   newElement;
     249            return this;
     250        }
     251    } // outer if-clause
     252    if( c->getDeg() > this->data->getDeg() ) { // greater degree than the first list element
     253        CNode* temp =   this;
     254        while( temp->next != NULL) {   
     255            if( c->getDeg() < temp->next->data->getDeg() ) {
     256                CNode* newElement   =   new CNode(c);
     257                newElement->next    =   temp->next;
     258                temp->next          =   newElement;
     259                return this;
     260            }
     261            if( c->getDeg() == temp->next->data->getDeg() ) {
     262                if( c->getT1() <= temp->next->data->getT1() ) {
     263                    CNode* newElement   =   new CNode(c);
     264                    newElement->next    =   temp->next;
     265                    temp->next          =   newElement;
     266                    return this;
     267                }
     268                else {
     269                    temp = temp->next;
     270                    while(  temp->next != NULL ) {
     271                        if( temp->next->data->getDeg() == c->getDeg() ) {
     272                            if( c->getT1() <= temp->next->data->getT1() ) {
     273                                temp = temp->next;
     274                            }
     275                            else {
     276                                CNode* newElement   =   new CNode(c);
     277                                newElement->next    =   temp->next;
     278                                temp->next          =   newElement;
     279                                return this;
     280                            }
     281                        }
     282                        else {
     283                            CNode* newElement   =   new CNode(c);
     284                            newElement->next    =   temp->next;
     285                            temp->next          =   newElement;
     286                            return this;
     287                        }
     288                    }
     289                    CNode* newElement   =   new CNode(c);
     290                    newElement->next    =   NULL;
     291                    temp->next          =   newElement;
     292                    return this;
     293                }
     294            }
     295            if( c->getDeg() > temp->next->data->getDeg() ) {
     296                temp    =   temp->next;
     297            }
     298        }
     299        CNode* newElement   =   new CNode(c);
     300        newElement->next    =   NULL;
     301        temp->next          =   newElement;
     302        return this;
     303    }
     304}
     305
     306/*
     307====================================
     308functions working on the class CList
     309====================================
     310*/
     311
     312CList::CList(CPair* c) {
     313    first   = new CNode(c);
     314}
     315
     316CList::~CList() {
     317    delete first;
     318}
     319
     320// insert sorts the critical pairs firstly by increasing total degree, secondly by increasing label
     321// note: as all critical pairs have the same index here, the second sort is done on the terms of the labels
     322void CList::insert(CPair* c) {
     323    first = first->insert(c);
    143324}
    144325#endif

  • kernel/lists.h

    r5ec4a8 ra0350e9  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lists.h,v 1.2 2008-12-27 13:50:05 ederc Exp $ */
     4/* $Id: lists.h,v 1.3 2009-01-15 17:44:24 ederc Exp $ */
    55/*
    66* ABSTRACT: list interface
    … …  
    1111
    1212#ifdef HAVE_F5
    13 
    14 
    1513/*
    16 =======================
    17 =======================
    18 linked lists for LPolys
    19 =======================
    20 =======================
    21 */
    22 
    23 
    24 /*
    25 ===========================
    26 classes for lists of LPolys
    27 ===========================
     14============================
     15============================
     16classes for lists used in F5
     17============================
     18============================
    2819*/
    2920class LNode;
    3021class LList;
     22class PrevNode;
     23class PrevList;
     24class CNode;
     25class CList;
    3126
    3227
    … …  
    4338        // generating new list elements from the labeled / classical polynomial view
    4439                LNode(LPoly* lp);
    45                 LNode(poly* t, long* i, poly* p);
     40                LNode(poly* t, int* i, poly* p);
    4641                LNode(LNode* ln);
    4742                ~LNode();
    4843        // append new elements to the list from the labeled / classical polynomial view
    49         LNode*  append(LPoly* lp);
    50         LNode*  append(poly* t, long* i, poly* p);
     44        LNode*  insert(LPoly* lp);
     45        LNode*  insert(poly* t, int* i, poly* p);
    5146        // get next from current LNode
    5247        LNode*  getNext();
    … …  
    5853        // test if for any list element the polynomial part of the data is equal to *p
    5954        bool    polyTest(poly* p);
    60         LNode*  operator++();
    6155};
    6256
    … …  
    7064    private:
    7165        LNode*  first;
    72         LNode*  last;
    73         long    length;
     66        int     length;
    7467    public:
    7568                LList(LPoly* lp);
    76                 LList(poly* t,long* i,poly* p);
     69                LList(poly* t,int* i,poly* p);
    7770                ~LList();
    78         void    append(LPoly* lp);
    79         void    append(poly* t,long* i, poly* p);
     71        void    insert(LPoly* lp);
     72        // insertion in front of the list
     73        void    insert(poly* t,int* i, poly* p);
    8074        bool    polyTest(poly* p);
    81         long    getLength() const;
     75        int     getLength() const;
    8276        LNode*  getFirst();
    83         LNode*  getLast();
    8477};
    8578
    8679
    8780/*
    88 =======================
    89 =======================
    90 linked lists for CPairs
    91 =======================
    92 =======================
     81=============================================
     82PrevNode class (nodes for lists of gPrevLast)
     83=============================================
    9384*/
     85class PrevNode {
     86    private:
     87        LNode*      data;
     88        PrevNode*   next;
     89    public:
     90        PrevNode(LNode* l);
     91        ~PrevNode();
     92        PrevNode*   append(LNode* l);
     93        LNode*      getLNode();
     94        LNode*      getPrevLast(int i);
     95};
    9496
    9597
    9698/*
    97 ===========================
    98 classes for lists of CPairs
    99 ===========================
     99====================================================
     100class PrevList(lists of last node elements in gPrev)
     101====================================================
    100102*/
    101 class CNode;
    102 class CList;
     103class PrevList {
     104    private:
     105        PrevNode*   first;
     106        PrevNode*   last;
     107    public:
     108                PrevList(LNode* l);
     109                ~PrevList();
     110        void    append(LNode* l);
     111        LNode*  getPrevLast(int i);
     112};
    103113
    104114
    … …  
    110120class CNode {
    111121    private:
    112         LPoly* data;
     122        CPair* data;
    113123        CNode* next;
    114124    public:
    115         CNode(LPoly* lp, CNode* n) {
    116             data = lp;
    117             next = n;
    118         }
    119         ~CNode() {
    120             delete next;
    121             delete data;   
    122         }
    123         CNode* append(LPoly* lp) {
    124             CNode* new_element = new CNode(lp,NULL);
    125             next = new_element;
    126             return new_element;
    127         }
    128         LPoly* getLPoly() const {
    129             return data;
    130         }
     125                CNode(CPair* c);
     126                ~CNode();
     127        CNode*  insert(CPair* c);
     128        CNode*  getLPoly() const;
    131129};
    132130
    … …  
    140138    private:
    141139        CNode*  first;
    142         CNode*  last;
    143         long    length;
    144140    public:
    145         CList(LPoly* lp) {
    146             first = new CNode(lp,NULL);
    147             last = first;
    148             length = 1;
    149         }
    150         ~CList() {
    151             delete first;
    152         }
    153         void append(LPoly* lp) {
    154             last = last->append(lp);
    155             length++;
    156         }
    157         long getLength() const {
    158             return length;
    159         }
    160         CNode* getFirst() const {
    161             return first;
    162         }
    163         CNode* getLast() const {
    164             return last;
    165         }
     141                CList(CPair* c);
     142                ~CList();
     143        void    insert(CPair* c);
    166144};
    167145#endif

  • kernel/lpolynomial.cc

    r5ec4a8 ra0350e9  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lpolynomial.cc,v 1.4 2008-12-27 13:50:06 ederc Exp $ */
     4/* $Id: lpolynomial.cc,v 1.5 2009-01-15 17:44:24 ederc Exp $ */
    55/*
    66* ABSTRACT: lpolynomial definition
    … …  
    3030================================================================
    3131*/
    32 LPoly::LPoly(poly* t,long* i,poly* p) {
     32LPoly::LPoly(poly* t,int* i,poly* p) {
    3333    set(t,i,p);
    3434}
     35
    3536void LPoly::setPoly(poly* p)  {
    3637    polynomial = *p;
    … …  
    4142}
    4243
    43 void LPoly::setIndex(long* i) {
     44void LPoly::setIndex(int* i) {
    4445    index = *i;
    4546}
    46 
    4747
    4848void LPoly::setDel(bool b) {
    … …  
    5858}
    5959
    60 long* LPoly::getIndex() {
     60int* LPoly::getIndex() {
    6161    return &index;
    6262}
    … …  
    6666}
    6767
    68 void LPoly::set(poly* t, long* i, poly* p) {
     68void LPoly::set(poly* t, int* i, poly* p) {
    6969    this->setTerm(t);
    7070    this->setIndex(i);
    … …  
    7575    return this;
    7676}
     77
     78/*
     79====================================
     80functions working on the class CPair
     81====================================
     82*/
     83CPair::CPair(int degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2) {
     84   deg  =   degree;
     85   t1   =   term1;
     86   lp1  =   lpoly1;
     87   t2   =   term2;
     88   lp2  =   lpoly2;
     89}
     90
     91int CPair::getDeg() {
     92    return deg;
     93}
     94
     95poly CPair::getT1() {
     96    return t1;
     97}
     98
     99poly CPair::getT2() {
     100    return t2;
     101}
     102
     103poly CPair::getLp1Poly() {
     104    return *(lp1->getPoly());
     105}
     106
     107poly CPair::getLp2Poly() {
     108    return *(lp2->getPoly());
     109}
     110
     111poly CPair::getLp1Term() {
     112    return *(lp1->getTerm());
     113}
     114
     115poly CPair::getLp2Term() {
     116    return *(lp2->getTerm());
     117}
     118
     119int CPair::getLp1Index() {
     120    return *(lp1->getIndex());
     121}
     122
     123
     124int CPair::getLp2Index() {
     125    return *(lp2->getIndex());
     126}
     127
     128
    77129#endif

  • kernel/lpolynomial.h

    r5ec4a8 ra0350e9  
    22*  Computer Algebra System SINGULAR     *
    33****************************************/
    4 /* $Id: lpolynomial.h,v 1.4 2008-12-27 13:50:06 ederc Exp $ */
     4/* $Id: lpolynomial.h,v 1.5 2009-01-15 17:44:24 ederc Exp $ */
    55/*
    66* ABSTRACT: labeled polynomial interface
    … …  
    1010
    1111#ifdef HAVE_F5
     12/*
     13=========================================================
     14=========================================================
     15classes for labeled polynomials/pairs/S-polynomials in F5
     16=========================================================
     17=========================================================
     18*/
     19class LPoly;
     20class CPair;
    1221
    1322
    … …  
    2029    private:
    2130        poly    term; //term of signature
    22         long    index; //index of signature
     31        int     index; //index of signature
    2332        poly    polynomial; //standard polynomial data
    2433        bool    del; //for deletion in TopReduction Subalgorithm
    2534    public:
    26                 LPoly(poly*t,long* i,poly* p);
     35                LPoly(poly*t,int* i,poly* p);
    2736        void    setPoly(poly* p);
    2837        poly*   getPoly();
    2938        void    setTerm(poly* t);
    3039        poly*   getTerm();
    31         void    setIndex(long* i);
    32         long*   getIndex();
     40        void    setIndex(int* i);
     41        int*    getIndex();
    3342        void    setDel(bool b);
    3443        bool    getDel() const;
    35         void    set(poly* t, long* i, poly* p);
     44        void    set(poly* t, int* i, poly* p);
    3645        LPoly*  get();
    3746};
    … …  
    4352===============================
    4453*/
    45 struct CPair {
    46     LPoly*  cp1;   // first  component
    47     LPoly*  cp2;   // second component
     54class CPair {
     55    private:
     56        int     deg;    // total degree of the critical pair
     57        poly    t1;     // first term for label
     58        LPoly*  lp1;     // first labeled poly
     59        poly    t2;     // second term for label
     60        LPoly*  lp2;     // second labeled poly
     61    public:
     62                CPair(int degree, poly term1, LPoly* lpoly1, poly term2, LPoly* lpoly2);
     63        int     getDeg();
     64        poly    getT1();
     65        poly    getLp1Poly();
     66        poly    getLp1Term();
     67        int     getLp1Index();
     68        poly    getT2();
     69        poly    getLp2Poly();
     70        poly    getLp2Term();
     71        int     getLp2Index();
    4872};
    4973
Note: See TracChangeset for help on using the changeset viewer.