source: git/kernel/f5lists.h @ 418bd6

spielwiese
Last change on this file since 418bd6 was 418bd6, checked in by Christian Eder, 15 years ago
added idea for termination of F5: split critical pairs in "useful" and "useless" ones, check later on if there are "useful" ones left, else terminate the algorithm. git-svn-id: file:///usr/local/Singular/svn/trunk@12147 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 9.9 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id: f5lists.h,v 1.25 2009-10-01 13:40:16 ederc Exp $ */
5/*
6* ABSTRACT: list interface
7*/
8#include "f5data.h"
9#ifndef F5LISTS_HEADER
10#define F5LISTS_HEADER
11
12#ifdef HAVE_F5
13/*
14============================
15============================
16classes for lists used in F5
17============================
18============================
19*/
20class LNode;
21class LList;
22class LTagNode;
23class LTagList;
24class CNode;
25class CListOld;
26class RList;
27class RNode;
28class RTagNode;
29class RTagList;
30
31
32/*
33=======================================
34class LNode (nodes for lists of LPolyOlds)
35=======================================
36*/
37class LNode {
38    private:
39        LPolyOld*  data;
40        LNode*  next;
41    public:
42        // generating new list elements from the labeled / classical polynomial view
43                LNode();
44                LNode(LPolyOld* lp);
45                LNode(LPolyOld* lp, LNode* l);
46                LNode(poly t, int i, poly p, RuleOld* r=NULL);
47                LNode(poly t, int i, poly p, RuleOld* r, LNode* l);
48                LNode(LNode* ln);
49                ~LNode();
50        void    deleteAll();
51        // insert new elements to the list at the end from the labeled / classical polynomial view
52        // needed for gPrev
53        LNode*  insert(LPolyOld* lp);
54        LNode*  insert(poly t, int i, poly p, RuleOld* r);
55        LNode*  insertByDeg(LPolyOld* lp);
56        // insert new elements to the list in front from the labeled / classical polynomial view
57        // needed for sPolyList
58        LNode*  insertSP(LPolyOld* lp);
59        LNode*  insertSP(poly t, int i, poly p, RuleOld* r);
60        // insert new elements to the list with resp. to increasing labels
61        // only used for the S-polys to be reduced (TopReduction building new S-polys with higher label)
62        LNode*  insertByLabel(poly t, int i, poly p, RuleOld* r);
63        LNode*  insertByLabel(LNode* l);
64        LNode*  insertFirst(LNode* l);
65        // deletes the first elements of the list with the same degree
66        // get next & prev from current LNode
67        LNode*  getNext();
68        LNode*  getPrev();
69        // only used for the S-polys, which are already sorted by increasing degree by CListOld
70        LNode*  deleteByDeg();
71        // get the LPolyOld* out of LNode*
72        LPolyOld*  getLPolyOld();
73        // get the data from the LPolyOld saved in LNode
74        poly    getPoly();
75        poly    getTerm();
76        int     getIndex(); 
77        RuleOld*   getRuleOld();
78        bool    getDel();
79        // set the data from the LPolyOld saved in LNode
80        void    setPoly(poly p);
81        void    setTerm(poly t);
82        void    setIndex(int i);
83        void    setNext(LNode* l);
84        void    setRuleOld(RuleOld* r);
85        void    setDel(bool d);
86        // test if for any list element the polynomial part of the data is equal to *p
87        bool    polyTest(poly* p);
88        LNode*  getNext(LNode* l);
89        void    print();
90        int     count(LNode* l);
91};
92
93
94/*
95============================
96class LList(lists of LPolyOlds)
97============================
98*/
99class LList {
100    private:
101        LNode*  first;
102        LNode*  last;
103        int     length;
104    public:
105                LList();
106                LList(LPolyOld* lp);
107                LList(poly t,int i,poly p, RuleOld* r = NULL);
108                ~LList();
109        // insertion at the end of the list
110        // needed for gPrev
111        void    insert(LPolyOld* lp);
112        void    insert(poly t,int i, poly p, RuleOld* r = NULL);
113        void    insertByDeg(LPolyOld* lp);
114        // insertion in front of the list
115        // needed for sPolyList
116        void    insertSP(LPolyOld* lp);
117        void    insertSP(poly t,int i, poly p, RuleOld* r = NULL);
118        void    insertByLabel(poly t, int i, poly p, RuleOld* r = NULL);
119        void    insertByLabel(LNode* l);
120        void    insertFirst(LNode* l);
121        void    deleteByDeg();
122        bool    polyTest(poly* p);
123        LNode*  getFirst();
124        LNode*  getLast();
125        int     getLength();
126        void    setFirst(LNode* l);
127        void    print();
128        int     count(LNode* l);
129};
130
131
132
133/*
134==============================================
135class LtagNode (nodes for lists of LPolyOld tags)
136==============================================
137*/
138class LTagNode {
139    private:
140        LNode*      data;
141        LTagNode*   next;
142    public:
143        LTagNode();
144        LTagNode(LNode* l);
145        LTagNode(LNode* l, LTagNode* n);
146        ~LTagNode();
147        // declaration with first as parameter due to sorting of LTagList
148        LTagNode*   insert(LNode* l);
149        LNode*      getLNode();
150        LTagNode*   getNext();
151        LNode*      get(int i, int length);
152};
153
154
155/*
156=========================================================================
157class LTagList(lists of LPolyOld tags, i.e. first elements of a given index)
158=========================================================================
159*/
160class LTagList {
161    private:
162        LTagNode*   first;
163        LNode*      firstCurrentIdx;
164        int         length;
165    public:
166                LTagList();
167                LTagList(LNode* l);
168                ~LTagList();
169        // declaration with first as parameter in LTagNode due to sorting of LTagList
170        void    insert(LNode* l);
171        void    setFirstCurrentIdx(LNode* l);
172        LNode*  get(int idx);
173        LNode*  getFirst();
174        LNode*  getFirstCurrentIdx();
175};
176
177LNode*  getGPrevRedCheck();
178LNode*  getcompletedRedCheck();
179
180
181/*
182======================================================================================
183class TopRed(return values of subalgorithm TopRed in f5gb.cc), i.e. the first elements
184             of the lists LList* completed & LList* sPolyList
185======================================================================================
186*/
187class TopRed {
188    private:
189        LList*  _completed;
190        LList*  _toDo;
191    public:
192                TopRed();
193                TopRed(LList* c, LList* t);
194        LList*  getCompleted();
195        LList*  getToDo();
196};
197
198
199/*
200=======================================
201class CNode (nodes for lists of CPairOlds)
202=======================================
203*/
204class CNode {
205    private:
206        CPairOld* data;
207        CNode* next;
208    public:
209                CNode();
210                CNode(CPairOld* c);
211                CNode(CPairOld* c, CNode* n);
212                ~CNode(); 
213        CNode*  insert(CPairOld* c); 
214        CNode*  getMinDeg();
215        CPairOld*  getData();
216        CNode*  getNext();
217        LPolyOld*  getAdLp1();
218        LPolyOld*  getAdLp2();
219        poly    getLp1Poly();
220        poly    getLp2Poly();
221        poly    getLp1Term();
222        poly    getLp2Term();
223        poly    getT1(); 
224        poly*   getAdT1(); 
225        poly    getT2(); 
226        poly*   getAdT2(); 
227        int     getLp1Index();
228        int     getLp2Index();
229        bool    getDel();
230        RuleOld*   getTestedRuleOld();
231        void    print();
232};
233
234
235/*
236============================
237class CListOld(lists of CPairOlds)
238============================
239*/
240class CListOld {
241    private:
242        CNode*  first;
243    public:
244                // for initialization of CListOlds, last element alwas has data=NULL and next=NULL
245                CListOld(); 
246                CListOld(CPairOld* c); 
247                ~CListOld(); 
248        CNode*  getFirst();
249        void    insert(CPairOld* c);
250        CNode*  getMinDeg();
251        void    print();
252};
253
254
255/*
256======================================
257class RNode (nodes for lists of RuleOlds)
258======================================
259*/
260class RNode {
261    private:
262        RuleOld*   data;
263        RNode*  next;
264    public:
265                RNode();
266                RNode(RuleOld* r);
267                ~RNode();
268        RNode*  insert(RuleOld* r);
269        RNode*  insert(int i, poly t);
270        RNode*  insertOrdered(RuleOld* r);
271        RNode*  getNext();
272        RuleOld*   getRuleOld();
273        int     getRuleOldIndex();
274        poly    getRuleOldTerm();
275        void    print();
276};
277
278/*
279============================
280class RList (lists of RuleOlds)
281============================
282*/
283class RList {
284    private:
285        RNode*  first;
286        // last alway has data=NULL and next=NULL, for initialization purposes used
287        RNode*  last;
288    public:
289                RList();
290                RList(RuleOld* r);
291                ~RList();
292        void    insert(RuleOld* r);
293        void    insert(int i, poly t);
294        void    insertOrdered(RuleOld* r);
295        RNode*  getFirst();
296        RuleOld*   getRuleOld();
297        void    print();
298};
299
300
301
302/*
303=============================================
304class RtagNode (nodes for lists of RuleOld tags)
305=============================================
306*/
307class RTagNode {
308    private:
309        RNode*      data;
310        RTagNode*   next;
311    public:
312                    RTagNode();
313                    RTagNode(RNode* r);
314                    RTagNode(RNode* r, RTagNode* n);
315                    ~RTagNode();
316        // declaration with first as parameter due to sorting of LTagList
317        RTagNode*   insert(RNode* r);
318        RNode*      getRNode();
319        RTagNode*   getNext();
320        RNode*      get(int idx, int length);
321        void        set(RNode*);
322        void        print();
323};
324
325
326/*
327========================================================================
328class RTagList(lists of RuleOld tags, i.e. first elements of a given index)
329========================================================================
330*/
331class RTagList {
332    private:
333        RTagNode*   first;
334        int         length;
335    public:
336                RTagList();
337                RTagList(RNode* r);
338                ~RTagList();
339        // declaration with first as parameter in LTagNode due to sorting of LTagList
340        void    insert(RNode* r);
341        RNode*  getFirst();
342        RNode*  get(int idx);
343        void    setFirst(RNode* r);
344        void    print();
345        int     getLength();
346};
347#endif
348#endif
Note: See TracBrowser for help on using the repository browser.