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