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