1
2
3 #include "kernel/mod2.h"
4
5 #include "coeffs/numbers.h"
6
7 #include "polys/monomials/ring.h"
8 #include "polys/monomials/p_polys.h"
9 #include "polys/kbuckets.h"
10
11 #include "kernel/ideals.h"
12 #include "kernel/polys.h"
13 #include "kernel/GBEngine/kutil.h"
14 #include "kernel/GBEngine/janet.h"
15
16
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 #include <stdarg.h>
21 #include <time.h>
22
23 #if (defined(__CYGWIN__))
24 #include <ctype.h>
25 #endif
26
27
28 //------GLOBALS-------
29 STATIC_VAR int /*m_s,v_s,vectorized,VarN1,*/offset;
30 STATIC_VAR jList *T,*Q;
31 STATIC_VAR TreeM *G;
32 // static Poly *phD;
33 STATIC_VAR NodeM *FreeNodes;
34 STATIC_VAR int degree_compatible;
35 STATIC_VAR int (*ListGreatMove)(jList *,jList *,poly);
36 STATIC_VAR int Mask[8]={0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};
37
38 //#define DebugPrint
39
40 //#define pow_(x) pTotaldegree((x))
41 //#define pow_(x) p_Deg((x,currRing))
42 VAR pFDegProc jDeg;
43 #define pow_(x) jDeg((x),currRing)
44
45 #if 0
46 void Debug()
47 {
48 LCI it=T->root;
49
50 PrintS("T==================================\n");
51 while (it)
52 {
53 pWrite(it->info->root);
54 it=it->next;
55 }
56
57 it=Q->root;
58
59 PrintS("Q==================================\n");
60 while (it)
61 {
62 if (it->info->root) pWrite(it->info->root);
63 else
64 {
65 Print("%d.........",it->info->prolonged);
66 pWrite(it->info->history);
67 }
68 it=it->next;
69 }
70 PrintS("===================================\n");
71 }
72 #endif
73
ReducePolyLead(Poly * x,Poly * y)74 int ReducePolyLead(Poly *x,Poly *y)
75 {
76 if (!x->root || !y->root)
77 return 0;
78
79 /* poly b1=pMDivide(x->root,y->root);
80
81 number gcd=n_Gcd(pGetCoeff(x->root),pGetCoeff(y->root),currRing->cf);
82
83 number a1=nDiv(pGetCoeff(y->root),gcd);
84 pGetCoeff(b1)=nDiv(pGetCoeff(x->root),gcd);
85
86 x->root=pMult_nn(x->root,a1);
87 nDelete(&a1);
88
89 x->root=pMinus_mm_Mult_qq(x->root,b1,y->root);
90
91 pDelete(&b1);
92 */
93 #if 1
94 if (x->root_b==NULL)
95 {
96 if (x->root_l<=0) x->root_l=pLength(x->root);
97 x->root_b=kBucketCreate(currRing);
98 kBucketInit(x->root_b,x->root,x->root_l);
99 }
100 number coef;
101 if (y->root_l<=0) y->root_l=pLength(y->root);
102 coef=kBucketPolyRed(x->root_b,y->root,y->root_l,NULL);
103 nDelete(&coef);
104 x->root=kBucketGetLm(x->root_b);
105 if (x->root==NULL)
106 {
107 kBucketDestroy(&x->root_b);
108 x->root_b=NULL;
109 x->root_l=0;
110 }
111 #else
112 x->root=ksOldSpolyRed(y->root,x->root,NULL);
113 #endif
114 // if (x->root) p_SimpleContent(x->root,5,currRing);
115
116 return 1;
117 }
118
ReducePoly(Poly * x,poly from,Poly * y)119 int ReducePoly(Poly *x,poly from,Poly *y)
120 {
121 if (!x->root || !y->root)
122 return 0;
123
124 /* poly b1=pMDivide(from,y->root);
125
126 number gcd=n_Gcd(pGetCoeff(from),pGetCoeff(y->root),currRing->cf);
127
128 number a1=nDiv(pGetCoeff(y->root),gcd);
129 pGetCoeff(b1)=nDiv(pGetCoeff(from),gcd);
130
131 x->root=pMult_nn(x->root,a1);
132 nDelete(&a1);*/
133
134 // x->root=pMinus_mm_Mult_qq(x->root,b1,y->root);
135 // pDelete(&b1);
136
137 ksOldSpolyTail(y->root,x->root,from,NULL,currRing);
138 y->root_l=0;
139
140 return 1;
141 }
142
PNF(Poly * p,TreeM * F)143 void PNF(Poly *p, TreeM *F)
144 {
145 if (p->root==NULL) return;
146
147 Poly *f;
148 BOOLEAN done=FALSE;
149 poly temp=p->root;
150
151 // if (TEST_OPT_PROT) { PrintS("r"); mflush(); }
152 int count=0;
153 poly pp=p->root;
154 int old_size=nSize(pGetCoeff(pp));
155 p->root_l=0;
156 while(temp->next)
157 {
158 f=is_div_(F,temp->next);
159 if (f)
160 {
161 if (ReducePoly(p,temp,f)) //temp->next
162 {
163 count++;
164 //if (TEST_OPT_PROT) { PrintS("-"); mflush(); }
165 if ((f!=NULL)
166 && (count>20)
167 && (nSize(pGetCoeff(pp))>old_size)
168 )
169 {
170 p_SimpleContent(pp,1,currRing);
171 //p_Content(pp,currRing);
172 count=0;
173 // old_size=nSize(pGetCoeff(pp));
174 }
175 }
176 done=TRUE;
177 }
178 else
179 temp=temp->next;
180 }
181
182 if (done) p_ContentForGB(p->root,currRing);
183 //if (done) p_SimpleContent(p->root,-1,currRing);
184 pTest(p->root);
185 }
186
NFL(Poly * p,TreeM * F)187 void NFL(Poly *p, TreeM *F)
188 {
189 Poly *f;
190 // int g1,f1,gg;
191
192 if ((f=is_div_(F,p->lead))==NULL) return;
193
194 int pX=pow_(p->lead);
195 int phX=pow_(p->history);
196
197 if (pX!=phX)
198 {
199 int phF=pow_(f->history);
200 if (pX >= (phX+phF))
201 {
202 pDelete(&p->root);
203 //p->root=NULL;
204 return;
205 }
206
207 /* poly p2=pInit();
208 pLcm(p->history,f->history,p2);
209 pSetm(p2);
210
211 if (pLmCmp(p->root,p2) > 0)
212 {
213 pLmDelete(&p2);
214 pDelete(&p->root);
215 //p->root=NULL;
216 return;
217 }
218
219 pLmDelete(&p2);
220 */
221 /* for(int i=0, gg=0 ; i<currRing->N;i++)
222 if ((g1=pGetExp(p->history,i+1)) > (f1=pGetExp(f->history,i+1)))
223 gg+=g1;
224 else gg+=f1;
225
226 if (pX > gg)
227 {
228 pDelete(&p->root);
229 //x->root=NULL;
230 return;
231 }
232 */
233 int pF=pow_(f->lead);
234
235 if ((pX == pF) && (pF == phF))
236 {
237 pLmFree(&f->history);
238 if (p->history!=NULL)
239 f->history=p_Copy_noCheck(p->history,currRing); /* cf of p->history is NULL */
240 }
241 }
242
243 //if (TEST_OPT_PROT) { PrintS("R"); mflush(); }
244 int /*old_size, */count;
245 count=0;
246 while(f && p->root)
247 {
248 // PrintS("R");
249 // if (TEST_OPT_PROT) { PrintS("R"); mflush(); }
250 #if 0
251 old_size=nSize(pGetCoeff(p->root));
252 #endif
253 if (ReducePolyLead(p,f) == 0) break;
254 if (p->root!=NULL)
255 {
256 count++;
257 #if 0
258 if ((count>4) && (3<nSize(pGetCoeff(p->root)))
259 && (nSize(pGetCoeff(p->root))>old_size))
260 {
261 p_SimpleContent(p->root,old_size,currRing);
262 count=0;
263 }
264 #else
265 if (count>50)
266 {
267 kBucketClear(p->root_b,&p->root,&p->root_l);
268 p_SimpleContent(p->root,2,currRing);
269 kBucketInit(p->root_b,p->root,p->root_l);
270 count=0;
271 //PrintS(".");
272 }
273 #endif
274 f=is_div_(F,p->root);
275 }
276 }
277 #if 1
278 if (p->root_b!=NULL)
279 {
280 kBucketClear(p->root_b,&p->root,&p->root_l);
281 kBucketDestroy(&p->root_b);
282 p->root_b=NULL;
283 }
284 #endif
285
286 if (!p->root)
287 return;
288
289 InitHistory(p);
290 InitProl(p);
291 InitLead(p);
292 p->changed=1;
293
294 p_ContentForGB(p->root,currRing);
295 //p_SimpleContent(p->root,-1i,currRing);
296 pTest(p->root);
297 }
298
ValidatePoly(Poly * x,TreeM *)299 int ValidatePoly(Poly *x, TreeM */*F*/)
300 {
301 Poly /*f,*/*g;
302 // int g1,f1;
303
304 if (x->root) return 1;
305
306 g=is_present(T,x->history); //it's a prolongation - do we have a parent ?
307
308 if (!g) return 0; //if not - kill him !
309
310 poly lmX=pMDivide(x->lead,g->root);
311 pSetCoeff0(lmX,nInit(1));
312
313 /* if ((f=is_div_(F,lmX)) != NULL)
314 {
315 int pX=pow_(lmX);
316 int phX=pow_(x->history);
317
318 if (pX!=phX)
319 {
320 int phF=pow_(f->history);
321 if (pX >= (phX+phF))
322 {
323 pLmDelete(&lmX);
324 //x->root=NULL;
325 return 0;
326 }
327
328 for(int i=0, gg=0 ; i<currRing->N;i++)
329 if ((g1=pGetExp(x->history,i+1)) > (f1=pGetExp(f->history,i+1)))
330 gg+=g1;
331 else
332 gg+=f1;
333
334 if (pX > gg)
335 {
336 pLmDelete(&lmX);
337 return 0;
338 }
339 int pF=pow_(f->root);
340
341 if ((pX == pF) && (pF == phF))
342 f->history=x->history;
343 }
344 }
345
346 pLmDelete(&lmX);
347
348 */
349 x->root=pCopy(g->root);
350 x->root_l=g->root_l;
351
352 x->root=pMult(x->root,lmX);
353
354 pTest(x->root);
355
356 x->prolonged=-1;
357
358 return 1;
359 }
360
NewPoly(poly p)361 Poly *NewPoly(poly p)
362 {
363 Poly *beg=(Poly *)GCM(sizeof(Poly));
364
365 beg->root=p;//(p == NULL ? pInit() : p);
366 beg->root_b=NULL;
367 beg->root_l=0;
368 beg->history=NULL;//pInit();
369 beg->lead=NULL;
370 beg->mult=(char *)GCMA(sizeof(char)*2*offset);
371
372 for (int i=0; i < currRing->N; i++)
373 {
374 ClearMult(beg,i);
375 ClearProl(beg,i);
376 };
377
378 beg->prolonged=-1;
379
380 return beg;
381 }
382
DestroyPoly(Poly * x)383 void DestroyPoly(Poly *x)
384 {
385 pDelete(&x->root);
386 pLmFree(&x->history);
387 if (x->lead!=NULL) pLmFree(&x->lead);
388 GCF(x->mult);
389 GCF(x);
390 }
391
ControlProlong(Poly * x)392 void ControlProlong(Poly *x)
393 {
394 for (int i = 0; i< offset; i++)
395 {
396 (x->mult+offset)[i]&=~((x->mult)[i]);
397 // if (!GetMult(x,i) && !GetProl(x,i))
398 // ProlVar(x,i);
399 }
400 }
401
InitHistory(Poly * p)402 void InitHistory(Poly *p)
403 {
404 if (p->history) pLmFree(&p->history);
405 p->history=pLmInit(p->root);
406 p->changed=0;
407 }
408
InitLead(Poly * p)409 void InitLead(Poly *p)
410 {
411 if (p->lead!=NULL) pLmFree(&p->lead);
412 p->lead=pLmInit(p->root);
413 p->prolonged=-1;
414 }
415
InitProl(Poly * p)416 void InitProl(Poly *p)
417 {
418 memset(p->mult+offset,0,sizeof(char)*offset);
419 }
420
GetMult(Poly * x,int i)421 int GetMult(Poly *x,int i)
422 {
423 return x->mult[i/8] & Mask[i%8];
424 }
425
SetMult(Poly * x,int i)426 void SetMult(Poly *x,int i)
427 {
428 x->mult[i/8] |= Mask[i%8];
429 }
430
ClearMult(Poly * x,int i)431 void ClearMult(Poly *x,int i)
432 {
433 x->mult[i/8] &= ~Mask[i%8];
434 }
435
GetProl(Poly * x,int i)436 int GetProl(Poly *x, int i)
437 {
438 return (x->mult+offset)[i/8] & Mask[i%8];
439 }
440
SetProl(Poly * x,int i)441 void SetProl(Poly *x, int i)
442 {
443 (x->mult+offset)[i/8] |= Mask[i%8];
444 }
445
ClearProl(Poly * x,int i)446 void ClearProl(Poly *x, int i)
447 {
448 (x->mult+offset)[i/8] &= ~Mask[i%8];
449 }
450
LengthCompare(poly p1,poly p2)451 int LengthCompare(poly p1,poly p2)
452 {
453 do
454 {
455 if (p1 == NULL) return 1;
456 if (p2 == NULL) return 0;
457 pIter(p1);
458 pIter(p2);
459 }while(p1 && p2);
460 return 1;
461 }
462
ProlCompare(Poly * item1,Poly * item2)463 int ProlCompare(Poly *item1, Poly *item2)
464 {
465 switch(pLmCmp(item1->lead,item2->lead))
466 {
467 case -1:
468 return 1;
469
470 case 1:
471 return 0;
472
473 default:
474 if ((item1->root_l<=0)||(item2->root_l<=0))
475 return LengthCompare(item1->root,item2->root);
476 return item1->root_l<=item2->root_l;
477 }
478 }
479
ProlVar(Poly * temp,int i)480 void ProlVar(Poly *temp,int i)
481 {
482 Poly *Pr;
483
484 if (!GetProl(temp,i) && !GetMult(temp,i))
485 {
486 Pr=NewPoly();
487 SetProl(temp,i);
488
489 Pr->prolonged=i;
490 Pr->history=pLmInit(temp->history);
491 Pr->lead=pLmInit(temp->lead);
492 pIncrExp(Pr->lead,i+1);
493 pSetm(Pr->lead);
494 InitProl(temp);
495
496 Pr->changed=0;
497 // pTest(Pr->root);
498 InsertInCount(Q,Pr);
499 }
500 }
501
DestroyListNode(ListNode * x)502 void DestroyListNode(ListNode *x)
503 {
504 DestroyPoly(x->info);
505 GCF(x);
506 }
507
CreateListNode(Poly * x)508 ListNode* CreateListNode(Poly *x)
509 {
510 ListNode* ret=(ListNode *)GCM(sizeof(ListNode));
511 ret->info=x;
512 ret->next=NULL;
513 return ret;
514 }
515
516
FindMinList(jList * L)517 Poly *FindMinList(jList *L)
518 {
519 LI min=&(L->root);
520 LI l;
521 LCI xl;
522 Poly *x;
523
524 if (degree_compatible)
525 {
526 while ((*min) && ((*min)->info->root == NULL))
527 min=&((*min)->next);
528 }
529
530 if (!(*min)) return NULL;
531
532 l=&((*min)->next);
533
534 while (*l)
535 {
536 if ((*l)->info->root != NULL)
537 {
538 if (ProlCompare((*l)->info,(*min)->info))
539 min=l;
540 }
541
542 l=&((*l)->next);
543 }
544 x=(*min)->info;
545 xl=*min;
546 *min=(*min)->next;
547 GCF(xl);
548
549 return x;
550 }
551
InsertInList(jList * x,Poly * y)552 void InsertInList(jList *x,Poly *y)
553 {
554 ListNode *ins;
555 LI ix=&(x->root);
556
557 while (*ix)
558 {
559 if (pLmCmp(y->lead,(*ix)->info->lead) == -1)
560 ix=(ListNode **)&((*ix)->next);
561 else
562 break;
563 }
564
565 ins=CreateListNode(y);
566 ins->next=(ListNode *)(*ix);
567 *ix=ins;
568 return;
569 }
570
InsertInCount(jList * x,Poly * y)571 void InsertInCount(jList *x,Poly *y)
572 {
573 ListNode *ins;
574 LI ix=&(x->root);
575
576 ins=CreateListNode(y);
577 ins->next=(ListNode *)(*ix);
578 *ix=ins;
579 return;
580 }
581
ListGreatMoveOrder(jList * A,jList * B,poly x)582 int ListGreatMoveOrder(jList *A,jList *B,poly x)
583 {
584 LCI y=A->root;
585
586 if (!y || pLmCmp(y->info->lead,x) < 0) return 0;
587
588 while(y && pLmCmp(y->info->lead,x) >= 0)
589 {
590 InsertInCount(B,y->info);
591 A->root=y->next;
592 GCF(y);
593 y=A->root;
594 }
595
596 return 1;
597 }
598
ListGreatMoveDegree(jList * A,jList * B,poly x)599 int ListGreatMoveDegree(jList *A,jList *B,poly x)
600 {
601 LCI y=A->root;
602 int pow_x=pow_(x);
603
604 if (!y || pow_(y->info->lead) <= pow_x) return 0;
605
606 while(y && pow_(y->info->lead) > pow_x)
607 {
608 InsertInCount(B,y->info);
609 A->root=y->next;
610 GCF(y);
611 y=A->root;
612 }
613
614 return 1;
615 }
616
CountList(jList * Q)617 int CountList(jList *Q)
618 {
619 int i=0;
620 LCI y=Q->root;
621
622 while(y)
623 {
624 i++;
625 y=y->next;
626 }
627
628 return i;
629 }
630
NFListQ()631 void NFListQ()
632 {
633 LCI ll;
634 int p,p1;
635 LI l;
636
637 do
638 {
639 if (!Q->root) break;
640
641 ll=Q->root;
642
643 p=pow_(Q->root->info->lead);
644
645 while (ll)
646 {
647 int ploc=pow_(ll->info->lead);
648 if (ploc < p) p=ploc;
649 ll=ll->next;
650 }
651
652 p1=1;
653
654 l=&(Q->root);
655
656 while (*l)
657 {
658 // PrintS("*");
659 int ploc=pow_((*l)->info->lead);
660
661 if (ploc == p)
662 {
663 if (!ValidatePoly((*l)->info,G))
664 {
665 ll=(*l);
666 *l=(*l)->next;
667 DestroyListNode(ll);
668 continue;
669 };
670
671 (*l)->info->changed=0;
672 // PrintS("!");
673 NFL((*l)->info,G);
674 // PrintS("$");
675 if (!(*l)->info->root)
676 {
677 ll=(*l);
678 *l=(*l)->next;
679 DestroyListNode(ll);
680 continue;
681 };
682 p1=0;
683 }
684
685 l=&((*l)->next);
686 }
687 }while(p1);
688 // PrintLn();
689 }
690
691
ForEachPNF(jList * x,int i)692 void ForEachPNF(jList *x,int i)
693 {
694 LCI y=x->root;
695
696 while(y)
697 {
698 if (pow_(y->info->root) == i) PNF(y->info,G);
699 y=y->next;
700 }
701 }
702
ForEachControlProlong(jList * x)703 void ForEachControlProlong(jList *x)
704 {
705 LCI y=x->root;
706
707 while(y)
708 {
709 ControlProlong(y->info);
710 y=y->next;
711 }
712 }
713
DestroyList(jList * x)714 void DestroyList(jList *x)
715 {
716 LCI y=x->root,z;
717
718 while(y)
719 {
720 z=y->next;
721 DestroyPoly(y->info);
722 GCF(y);
723 y=z;
724 }
725
726 GCF(x);
727 }
728
is_present(jList * F,poly x)729 Poly* is_present(jList *F,poly x)
730 {
731 LCI iF=F->root;
732 while(iF)
733 if (pLmCmp(iF->info->root,x) == 0)
734 return iF->info;
735 else iF=iF->next;
736
737 return NULL;
738 }
739
GB_length()740 int GB_length()
741 {
742 LCI iT=T->root;
743 int l=0;
744
745 while(iT)
746 {
747 if (pow_(iT->info->lead) == pow_(iT->info->history))
748 ++l;
749 iT=iT->next;
750 }
751
752 return l;
753 }
754
755 STATIC_VAR Poly *temp_l;
756
create()757 NodeM* create()
758 {
759 NodeM *y;
760
761 if (FreeNodes == NULL)
762 {
763 y=(NodeM *)GCM(sizeof(NodeM));
764 }
765 else
766 {
767 y=FreeNodes;
768 FreeNodes=FreeNodes->left;
769 }
770
771 y->left=y->right=NULL;
772 y->ended=NULL;
773 return y;
774 }
775
DestroyFreeNodes()776 void DestroyFreeNodes()
777 {
778 NodeM *y;
779
780 while((y=FreeNodes)!=NULL)
781 {
782 FreeNodes=FreeNodes->left;
783 GCF(y);
784 }
785 }
786
787 #if 0
788 static void go_right(NodeM *current,poly_function disp)
789 {
790 if (current)
791 {
792 go_right(current->left,disp);
793 if (current->ended) disp(current->ended);
794 go_right(current->right,disp);
795 }
796 }
797
798 void ForEach(TreeM *t,poly_function disp)
799 {
800 go_right(t->root,disp);
801 }
802 #endif
803
DestroyTree(NodeM * G)804 void DestroyTree(NodeM *G)
805 {
806 if (G)
807 {
808 DestroyTree(G->left);
809 DestroyTree(G->right);
810 G->left=FreeNodes;
811 FreeNodes=G;
812 }
813 }
814
Define(TreeM ** G)815 void Define(TreeM **G)
816 {
817 *G=(TreeM *)GCM(sizeof(TreeM));
818 (*G)->root=create();
819 }
820
sp_div(poly m1,poly m2,int from)821 int sp_div(poly m1,poly m2,int from)
822 {
823
824 if (pow_(m2) == 0 && pow_(m1)) return 0;
825
826 for(int k=from; k < currRing->N; k++)
827 if (pGetExp(m1,k+1) < pGetExp(m2,k+1)) return 0;
828
829 return 1;
830 }
831
div_l(poly item,NodeM * x,int from)832 void div_l(poly item, NodeM *x,int from)
833 {
834 if (x && !temp_l)
835 {
836 div_l(item,x->left,from);
837 if ((x->ended) && sp_div(item,x->ended->root,from))
838 {
839 temp_l=x->ended;
840 return;
841 };
842 div_l(item,x->right,from);
843 }
844 }
845
is_div_upper(poly item,NodeM * x,int from)846 Poly* is_div_upper(poly item, NodeM *x,int from)
847 {
848 temp_l=NULL;
849 div_l(item,x,from);
850 return temp_l;
851 }
852
is_div_(TreeM * tree,poly item)853 Poly* is_div_(TreeM *tree, poly item)
854 {
855 int power_tmp,i,i_con=currRing->N-1;
856 NodeM *curr=tree->root;
857
858 if (!curr) return NULL;
859 if (pow_(item) == 0) return NULL;
860
861 for ( ; i_con>=0 && !pGetExp(item,i_con+1) ; i_con--)
862 ;
863
864 for (i=0; i <= i_con ; i++)
865 {
866 power_tmp=pGetExp(item,i+1);
867
868 while (power_tmp)
869 {
870 if (curr->ended) return curr->ended;
871
872 if (!curr->left)
873 {
874 if (curr->right)
875 return is_div_upper(item,curr->right,i); //??????
876 return NULL;
877 }
878
879 curr=curr->left;
880 power_tmp--;
881 }
882
883 if (curr->ended) return curr->ended;
884
885 if (!curr->right) return NULL;
886
887 curr=curr->right;
888 }
889
890 if (curr->ended) return curr->ended;
891 else return NULL;
892 }
893
ClearMultiplicative(NodeM * xx,int i)894 static void ClearMultiplicative(NodeM *xx,int i)
895 {
896 if (!xx) return;
897
898 while (xx->left)
899 {
900 ClearMultiplicative(xx->right, i);
901 xx = xx->left;
902 }
903 if ((xx->ended) && (GetMult(xx->ended,i)))
904 {
905 ClearMult(xx->ended,i);
906 ProlVar(xx->ended,i);
907 }
908 else
909 ClearMultiplicative(xx->right,i);
910 }
911 //======================================================
insert_(TreeM ** tree,Poly * item)912 void insert_(TreeM **tree, Poly *item)
913 {
914 int power_tmp,i,i_con=currRing->N-1;
915 NodeM *curr=(*tree)->root;
916
917 for ( ; (i_con>=0) && !pGetExp(item->root,i_con+1) ; i_con--)
918 SetMult(item,i_con);
919
920 for (i = 0; i<= i_con; i++)
921 //<=
922 {
923 power_tmp=pGetExp(item->root,i+1);
924
925 ClearMult(item,i);
926
927 while (power_tmp)
928 {
929 if (!curr->left)
930 {
931 SetMult(item,i);
932 ClearMultiplicative(curr->right,i);
933 curr->left=create();
934 };
935 curr=curr->left;
936 power_tmp--;
937 };
938
939 if (i<i_con)
940 {
941 if (!curr->left) SetMult(item,i);
942 if (!curr->right) curr->right=create();
943 curr=curr->right;
944
945 ProlVar(item,i);
946 }
947 }
948
949 curr->ended=item;
950 }
951
Initialization(char * Ord)952 void Initialization(char *Ord)
953 {
954 offset=(currRing->N % 8 == 0) ? (currRing->N/8)*8 : (currRing->N/8+1)*8;
955 if (strstr(Ord,"dp\0") || strstr(Ord,"Dp\0"))
956 {
957 degree_compatible=1;
958 jDeg=p_Deg;
959 ListGreatMove=ListGreatMoveDegree;
960 }
961 else
962 {
963 degree_compatible=0;
964 jDeg=p_Totaldegree;
965 ListGreatMove=ListGreatMoveOrder;
966 }
967
968 Define(&G);
969 }
970
971 STATIC_VAR Poly *h/*,*f*/;
972
973 #if 0
974 void insert_in_G(Poly *x)
975 {
976 insert_(&G,x);
977 }
978 #endif
979
980 void T2G();
981
982 #if 0
983 void Q2TG()
984 {
985 LCI t;
986 Poly *x;
987
988 while (Q->root)
989 {
990 t=Q->root;
991 x=t->info;
992 insert_(&G,x);
993 InsertInList(T,x);
994 Q->root=t->next;
995 GCF(t);
996 }
997 }
998 #endif
999
ComputeBasis(jList * _lT,jList * _lQ)1000 int ComputeBasis(jList *_lT,jList *_lQ)
1001 {
1002 // int gb_l,i,ret_value=1;
1003
1004 T=_lT; Q=_lQ;
1005
1006 // Debug();
1007
1008 while((h=FindMinList(Q))!=NULL)
1009 {
1010 // PrintS("New element\n");
1011 // Debug();
1012
1013 if (!degree_compatible)
1014 {
1015 if (!ValidatePoly(h,G))
1016 {
1017 DestroyPoly(h);
1018 continue;
1019 }
1020
1021 h->changed=0;
1022
1023 NFL(h,G);
1024
1025 if (!h->root)
1026 {
1027 DestroyPoly(h);
1028 continue;
1029 }
1030 }
1031
1032 if (h->root)
1033 {
1034 if (pIsConstant(h->root))
1035 {
1036 WarnS("Constant in basis\n");
1037 return 0;
1038 }
1039
1040 if (h->changed && ListGreatMove(T,Q,h->root))
1041 {
1042 // PrintS("<-\n");
1043 DestroyTree(G->root);
1044 G->root=create();
1045 T2G();
1046 }
1047 }
1048
1049 // PrintS("PNF\n");
1050 PNF(h,G);
1051 // Print("{%d}\n",pow_(h->root));
1052 insert_(&G,h);
1053 InsertInList(T,h);
1054
1055 // PrintS("For each PNF\n");
1056 if (degree_compatible)
1057 ForEachPNF(T,pow_(h->root));
1058
1059 // PrintS("Control of prolongations\n");
1060 if (h->changed)
1061 ForEachControlProlong(T);
1062 else
1063 ControlProlong(h);
1064
1065 // Debug();
1066
1067 // PrintS("NFListQ\n");
1068 if (degree_compatible)
1069 NFListQ();
1070 //Debug();
1071 }
1072
1073 // gb_l=GB_length();
1074
1075 Print("Length of Janet basis: %d\n",CountList(T));
1076 // Print("Length of Groebner basis: %d\n",gb_l);
1077
1078 DestroyTree(G->root);
1079 GCF(G);
1080 DestroyFreeNodes();
1081
1082 return 1;
1083 }
1084
T2G()1085 void T2G()
1086 {
1087 LCI i=T->root;
1088 while (i)
1089 {
1090 insert_(&G,i->info);
1091 i=i->next;
1092 }
1093 }
1094