source: git/kernel/tgb.cc @ 625767

spielwiese
Last change on this file since 625767 was 625767, checked in by Michael Brickenstein <bricken@…>, 18 years ago
* bricken: + syz_comp support git-svn-id: file:///usr/local/Singular/svn/trunk@9138 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 77.5 KB
Line 
1//! \file tgb.cc
2//       multiple rings
3//       shorten_tails und dessen Aufrufe pruefen wlength!!!
4/****************************************
5*  Computer Algebra System SINGULAR     *
6****************************************/
7/* $Id: tgb.cc,v 1.88 2006-05-16 08:38:39 bricken Exp $ */
8/*
9* ABSTRACT: slimgb and F4 implementation
10*/
11//#include <vector>
12//using namespace std;
13#include "mod2.h"
14#include "tgb.h"
15#include "tgb_internal.h"
16#include "tgbgauss.h"
17#include "F4.h"
18#include "digitech.h"
19#include "gring.h"
20
21#include "longrat.h"
22#define SR_HDL(A) ((long)(A))
23static const int bundle_size=100;
24static const int delay_factor=3;
25int QlogSize(number n);
26#define ADD_LATER_SIZE 500
27#if 1
28static omBin lm_bin=NULL;
29
30static void simplify_poly(poly p, ring r) {
31     assume(r==currRing);
32     if (!rField_is_Zp(r))
33     {
34        pCleardenom(p);
35        pContent(p); //is a duplicate call, but belongs here
36     }
37     else
38       pNorm(p);
39}
40//static const BOOLEAN up_to_radical=TRUE;
41
42int slim_nsize(number n, ring r)
43{
44  if (rField_is_Zp(r))
45  {
46    return 1;
47  }
48  if (rField_is_Q(r))
49  {
50    return QlogSize(n);
51  }
52  else
53  {
54    return n_Size(n,r);
55  }
56}
57static BOOLEAN monomial_root(poly m, ring r){
58    BOOLEAN changed=FALSE;
59    int i;
60    for(i=1;i<=rVar(r);i++){
61        int e=p_GetExp(m,i,r);
62        if (e>1){
63            p_SetExp(m,i,1,r);
64            changed=TRUE;
65        }
66    }
67    if (changed) {
68        p_Setm(m,r);
69    }
70    return changed;
71}
72static BOOLEAN polynomial_root(poly h, ring r){
73  poly got=gcd_of_terms(h,r);
74  BOOLEAN changed=FALSE;
75  if((got!=NULL) &&(TEST_V_UPTORADICAL)) {
76    poly copy=p_Copy(got,r);
77    //p_wrp(got,c->r);
78    changed=monomial_root(got,r);
79    if (changed)
80    {
81         poly div_by=pDivide(copy, got);
82         poly iter=h;
83         while(iter){
84            pExpVectorSub(iter,div_by);
85            pIter(iter);
86         }
87         p_Delete(&div_by, r);
88         if (TEST_OPT_PROT)
89             PrintS("U");
90    }
91    p_Delete(&copy,r);
92  }
93  p_Delete(&got,r);
94  return changed;
95}
96static inline poly p_Init_Special(const ring r)
97{
98  return p_Init(r,lm_bin);
99}
100static inline poly pOne_Special(const ring r=currRing)
101{
102  poly rc = p_Init_Special(r);
103  pSetCoeff0(rc,r->cf->nInit(1));
104  return rc;
105}
106// zum Initialiseren: in t_rep_gb plazieren:
107
108#endif
109#define LEN_VAR3
110#define degbound(p) assume(pTotaldegree(p)<10)
111//#define inDebug(p) assume((debug_Ideal==NULL)||(kNF(debug_Ideal,NULL,p,0,0)==0))
112
113//die meisten Varianten stossen sich an coef_buckets
114
115
116
117#ifdef LEN_VAR1
118// erste Variante: Laenge: Anzahl der Monome
119inline int pSLength(poly p, int l) {
120  return l; }
121inline int kSBucketLength(kBucket* bucket, poly lm) {return bucket_guess(bucket);}
122#endif
123
124#ifdef LEN_VAR2
125// 2. Variante: Laenge: Platz fuer die Koeff.
126int pSLength(poly p,int l)
127{
128  int s=0;
129  while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); }
130  return s;
131}
132int kSBucketLength(kBucket* b, poly lm)
133{
134  int s=0;
135  int i;
136  for (i=MAX_BUCKET;i>=0;i--)
137  {
138    s+=pSLength(b->buckets[i],0);
139  }
140  return s;
141}
142#endif
143
144
145// 3.Variante: Laenge: Platz fuer Leitk * Monomanzahl
146
147
148
149
150int QlogSize(number n){
151
152    if (SR_HDL(n) & SR_INT){
153       long i=SR_TO_INT(n);
154       if (i==0) return 0;
155
156       unsigned long v;
157       v=(i>=0)?i:-i;
158       int r = 0;
159
160       while (v >>= 1)
161       {
162        r++;
163       }
164       return r+1;
165    }
166    //assume denominator is 0
167    return mpz_sizeinbase(&n->z,2);
168}
169
170
171#ifdef LEN_VAR3
172inline wlen_type pSLength(poly p,int l)
173{
174  int c;
175  number coef=pGetCoeff(p);
176  if (rField_is_Q(currRing)){
177    c=QlogSize(coef);
178  }
179  else
180    c=nSize(coef);
181  if (!(TEST_V_COEFSTRAT))
182      return c*l /*pLength(p)*/;
183  else {
184    wlen_type res=l;
185    res*=c;
186    res*=c;
187    return res;
188  }
189}
190//! TODO CoefBuckets berücksichtigen
191wlen_type kSBucketLength(kBucket* b, poly lm=NULL)
192{
193  int s=0;
194  int c;
195  number coef;
196  if(lm==NULL)
197    coef=pGetCoeff(kBucketGetLm(b));
198    //c=nSize(pGetCoeff(kBucketGetLm(b)));
199  else
200    coef=pGetCoeff(lm);
201    //c=nSize(pGetCoeff(lm));
202  if (rField_is_Q(currRing)){
203    c=QlogSize(coef);
204  }
205  else
206    c=nSize(coef);
207
208  int i;
209  for (i=b->buckets_used;i>=0;i--)
210  {
211    assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL));
212    s+=b->buckets_length[i] /*pLength(b->buckets[i])*/;
213  }
214  #ifdef HAVE_COEF_BUCKETS
215  assume(b->buckets[0]==kBucketGetLm(b));
216  if (b->coef[0]!=NULL){
217
218    if (rField_is_Q(currRing)){
219      int modifier=QlogSize(pGetCoeff(b->coef[0]));
220      c+=modifier;
221  }
222    else{
223      int modifier=nSize(pGetCoeff(b->coef[0]));
224      c*=modifier;}
225    }
226  #endif
227  if (!(TEST_V_COEFSTRAT)){
228  return s*c;
229  } else
230  {
231    wlen_type res=s;
232    res*=c;
233    res*=c;
234    return res;
235  }
236}
237#endif
238#ifdef LEN_VAR5
239inline wlen_type pSLength(poly p,int l)
240{
241  int c;
242  number coef=pGetCoeff(p);
243  if (rField_is_Q(currRing)){
244    c=QlogSize(coef);
245  }
246  else
247    c=nSize(coef);
248  wlen_type erg=l;
249  erg*=c;
250  erg*=c;
251  //PrintS("lenvar 5");
252  assume(erg>=0);
253  return erg; /*pLength(p)*/;
254}
255//! TODO CoefBuckets berücksichtigen
256wlen_type kSBucketLength(kBucket* b, poly lm=NULL)
257{
258  wlen_type s=0;
259  int c;
260  number coef;
261  if(lm==NULL)
262    coef=pGetCoeff(kBucketGetLm(b));
263    //c=nSize(pGetCoeff(kBucketGetLm(b)));
264  else
265    coef=pGetCoeff(lm);
266    //c=nSize(pGetCoeff(lm));
267  if (rField_is_Q(currRing)){
268    c=QlogSize(coef);
269  }
270  else
271    c=nSize(coef);
272
273  int i;
274  for (i=b->buckets_used;i>=0;i--)
275  {
276    assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL));
277    s+=b->buckets_length[i] /*pLength(b->buckets[i])*/;
278  }
279  #ifdef HAVE_COEF_BUCKETS
280  assume(b->buckets[0]==kBucketGetLm(b));
281  if (b->coef[0]!=NULL){
282
283    if (rField_is_Q(currRing)){
284      int modifier=QlogSize(pGetCoeff(b->coef[0]));
285      c+=modifier;
286  }
287    else{
288      int modifier=nSize(pGetCoeff(b->coef[0]));
289      c*=modifier;}
290    }
291  #endif
292  wlen_type erg=s;
293  erg*=c;
294  erg*=c;
295  return erg;
296}
297#endif
298
299#ifdef LEN_VAR4
300// 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.)
301int pSLength(poly p, int l)
302{
303  int s=1;
304  int c=nSize(pGetCoeff(p));
305  pIter(p);
306  while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); }
307  return s*c;
308}
309int kSBucketLength(kBucket* b)
310{
311  int s=1;
312  int c=nSize(pGetCoeff(kBucketGetLm(b)));
313  int i;
314  for (i=MAX_BUCKET;i>0;i--)
315  {
316    if(b->buckets[i]==NULL) continue;
317    s+=pSLength(b->buckets[i],0);
318  }
319  return s*c;
320}
321#endif
322static int do_pELength(poly p, slimgb_alg* c, int dlm=-1){
323  if(p==NULL) return 0;
324  int s=0;
325  poly pi=p;
326  if(dlm<0){
327    dlm=pTotaldegree(p,c->r);
328    s=1;
329    pi=p->next;
330  }
331
332  while(pi){
333    int d=pTotaldegree(pi,c->r);
334    if(d>dlm)
335      s+=1+d-dlm;
336    else
337      ++s;
338    pi=pi->next;
339  }
340  return s;
341}
342
343wlen_type pELength(poly p, ring r){
344  if(p==NULL) return 0;
345  int s=0;
346  poly pi=p;
347  int dlm;
348    dlm=pTotaldegree(p,r);
349    s=1;
350    pi=p->next;
351
352
353  while(pi){
354    int d=pTotaldegree(pi,r);
355    if(d>dlm)
356      s+=1+d-dlm;
357    else
358      ++s;
359    pi=pi->next;
360  }
361  return s;
362}
363
364int kEBucketLength(kBucket* b, poly lm,slimgb_alg* ca)
365{
366  int s=0;
367  if(lm==NULL){
368    lm=kBucketGetLm(b);
369  }
370  if(lm==NULL) return 0;
371  int d=pTotaldegree(lm,ca->r);
372  int i;
373  for (i=b->buckets_used;i>=0;i--)
374  {
375    if(b->buckets[i]==NULL) continue;
376    s+=do_pELength(b->buckets[i],ca,d);
377  }
378  return s;
379}
380
381static inline int pELength(poly p, slimgb_alg* c,int l){
382  if (p==NULL) return 0;
383  return do_pELength(p,c);
384}
385
386
387
388
389static inline wlen_type pQuality(poly p, slimgb_alg* c, int l=-1){
390
391  if(l<0)
392    l=pLength(p);
393  if(c->is_char0) {
394    if((pLexOrder) &&(!c->is_homog)){
395      int cs;
396      number coef=pGetCoeff(p);
397      if (rField_is_Q(currRing)){
398         cs=QlogSize(coef);
399      }
400      else
401     cs=nSize(coef);
402     wlen_type erg=cs;
403     //erg*=cs;//for quadratic
404     erg*=pELength(p,c,l);
405    //FIXME: not quadratic coeff size
406      //return cs*pELength(p,c,l);
407      return erg;
408    }
409    //Print("I am here");
410    wlen_type r=pSLength(p,l);
411    assume(r>=0);
412    return r;
413  }
414  if((pLexOrder) &&(!c->is_homog)) return pELength(p,c,l);
415  return l;
416}
417
418static inline int pTotaldegree_full(poly p){
419  int r=0;
420  while(p){
421    int d=pTotaldegree(p);
422    r=si_max(r,d);
423    pIter(p);
424  }
425  return r;
426}
427
428wlen_type red_object::guess_quality(slimgb_alg* c){
429    //works at the moment only for lenvar 1, because in different
430    //case, you have to look on coefs
431    wlen_type s=0;
432    if (c->is_char0){
433      //s=kSBucketLength(bucket,this->p);
434      if((pLexOrder) &&(!c->is_homog)){
435    int cs;
436    number coef;
437
438    coef=pGetCoeff(kBucketGetLm(bucket));
439    //c=nSize(pGetCoeff(kBucketGetLm(b)));
440
441    //c=nSize(pGetCoeff(lm));
442    if (rField_is_Q(currRing)){
443      cs=QlogSize(coef);
444    }
445    else
446      cs=nSize(coef);
447    #ifdef HAVE_COEF_BUCKETS
448    if (bucket->coef[0]!=NULL){
449      if (rField_is_Q(currRing)){
450        int modifier=QlogSize(pGetCoeff(bucket->coef[0]));
451        cs+=modifier;
452      }
453      else{
454        int modifier=nSize(pGetCoeff(bucket->coef[0]));
455        cs*=modifier;}
456    }
457    #endif
458    //FIXME:not quadratic
459    wlen_type erg=kEBucketLength(this->bucket,this->p,c);
460    //erg*=cs;//for quadratic
461    erg*=cs;
462    //return cs*kEBucketLength(this->bucket,this->p,c);
463    return erg;
464      }
465      s=kSBucketLength(bucket,NULL);
466    }
467    else
468    {
469      if((pLexOrder) &&(!c->is_homog))
470  //if (false)
471  s=kEBucketLength(this->bucket,this->p,c);
472      else s=bucket_guess(bucket);
473    }
474
475    return s;
476}
477
478
479
480static void finalize_reduction_step(reduction_step* r){
481  delete r;
482}
483static int LObject_better_gen(const void* ap, const void* bp)
484{
485  LObject* a=*(LObject**)ap;
486  LObject* b=*(LObject**)bp;
487  return(pLmCmp(a->p,b->p));
488}
489static int red_object_better_gen(const void* ap, const void* bp)
490{
491
492
493  return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p));
494}
495
496
497static int pLmCmp_func_inverted(const void* ap1, const void* ap2){
498    poly p1,p2;
499  p1=*((poly*) ap1);
500  p2=*((poly*)ap2);
501
502  return -pLmCmp(p1,p2);
503}
504
505int tgb_pair_better_gen2(const void* ap,const void* bp){
506  return(-tgb_pair_better_gen(ap,bp));
507}
508int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj){
509  int i;
510  long not_sev=~obj.sev;
511  poly p=obj.p;
512  for(i=0;i<=strat->sl;i++){
513    if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev))
514      return i;
515  }
516  return -1;
517}
518int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev){
519  int i;
520  long not_sev=~sev;
521  for(i=0;i<=strat->sl;i++){
522    if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev))
523      return i;
524  }
525  return -1;
526}
527static int posInPairs (sorted_pair_node**  p, int pn, sorted_pair_node* qe,slimgb_alg* c,int an=0)
528{
529  if(pn==0) return 0;
530
531  int length=pn-1;
532  int i;
533  //int an = 0;
534  int en= length;
535
536  if (pair_better(qe,p[en],c))
537    return length+1;
538
539  while(1)
540    {
541      //if (an >= en-1)
542      if(en-1<=an)
543      {
544        if (pair_better(p[an],qe,c)) return an;
545        return en;
546      }
547      i=(an+en) / 2;
548        if (pair_better(p[i],qe,c))
549          en=i;
550      else an=i;
551    }
552}
553
554static BOOLEAN  ascending(int* i,int top){
555  if(top<1) return TRUE;
556  if(i[top]<i[top-1]) return FALSE;
557  return ascending(i,top-1);
558}
559
560sorted_pair_node**  spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c){
561  int i;
562  int* a= (int*) omalloc(qn*sizeof(int));
563//   int mc;
564//   PrintS("Debug\n");
565//   for(mc=0;mc<qn;mc++)
566// {
567
568//     wrp(q[mc]->lcm_of_lm);
569//     PrintS("\n");
570// }
571//    PrintS("Debug they are in\n");
572//   for(mc=0;mc<pn;mc++)
573// {
574
575//     wrp(p[mc]->lcm_of_lm);
576//     PrintS("\n");
577// }
578  int lastpos=0;
579  for(i=0;i<qn;i++){
580    lastpos=posInPairs(p,pn,q[i],c, si_max(lastpos-1,0));
581    //   cout<<lastpos<<"\n";
582    a[i]=lastpos;
583
584  }
585  if((pn+qn)>c->max_pairs){
586    p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*));
587    c->max_pairs=2*(pn+qn);
588  }
589  for(i=qn-1;i>=0;i--){
590    size_t size;
591    if(qn-1>i)
592      size=(a[i+1]-a[i])*sizeof(sorted_pair_node*);
593    else
594      size=(pn-a[i])*sizeof(sorted_pair_node*); //as indices begin with 0
595    memmove (p+a[i]+(1+i), p+a[i], size);
596    p[a[i]+i]=q[i];
597  }
598  omfree(a);
599  return p;
600}
601
602
603static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c){
604
605
606  poly p1=c->S->m[pos1];
607  poly p2=c->S->m[pos2];
608
609
610  if (pGetComp(p1) > 0 || pGetComp(p2) > 0)
611    return FALSE;
612  int i = 1;
613  poly m=NULL;
614  poly gcd1=c->gcd_of_terms[pos1];
615  poly gcd2=c->gcd_of_terms[pos2];
616
617  if((gcd1!=NULL) && (gcd2!=NULL))
618    {
619      gcd1->next=gcd2; //may ordered incorrect
620      m=gcd_of_terms(gcd1,c->r);
621      gcd1->next=NULL;
622
623    }
624
625  if (m==NULL)
626  {
627     loop
628      {
629  if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i))   return FALSE;
630  if (i == pVariables){
631    //PrintS("trivial");
632    return TRUE;
633  }
634  i++;
635      }
636  }
637  else
638  {
639    loop
640      {
641  if (pGetExp(p1, i)-pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i))   return FALSE;
642  if (i == pVariables){
643    pDelete(&m);
644    //PrintS("trivial");
645    return TRUE;
646  }
647  i++;
648      }
649  }
650
651
652
653
654}
655
656//! returns position sets w as weight
657int find_best(red_object* r,int l, int u, int &w, slimgb_alg* c){
658  int best=l;
659  int i;
660  w=r[l].guess_quality(c);
661  for(i=l+1;i<=u;i++){
662    int w2=r[i].guess_quality(c);
663    if(w2<w){
664      w=w2;
665      best=i;
666    }
667
668  }
669 return best;
670}
671
672
673void red_object::canonicalize(){
674  kBucketCanonicalize(bucket);
675
676
677}
678BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c){
679  assume(i>=0);
680    assume(j>=0);
681  if (has_t_rep(i,j,c)) return TRUE;
682  //poly lm=pOne();
683  assume (c->tmp_lm!=NULL);
684  poly lm=c->tmp_lm;
685
686  pLcm(c->S->m[i], c->S->m[j], lm);
687  pSetm(lm);
688  assume(lm!=NULL);
689  //int deciding_deg= pTotaldegree(lm);
690  int* i_con =make_connections(i,j,lm,c);
691  //p_Delete(&lm,c->r);
692
693
694  for (int n=0;((n<c->n) && (i_con[n]>=0));n++){
695    if (i_con[n]==j){
696      now_t_rep(i,j,c);
697      omfree(i_con);
698
699      return TRUE;
700    }
701  }
702  omfree(i_con);
703
704  return FALSE;
705}
706BOOLEAN lenS_correct(kStrategy strat){
707  int i;
708  for(i=0;i<=strat->sl;i++){
709    if (strat->lenS[i]!=pLength(strat->S[i]))
710      return FALSE;
711  }
712  return TRUE;
713}
714
715
716static void cleanS(kStrategy strat, slimgb_alg* c){
717  int i=0;
718  LObject P;
719  while(i<=strat->sl){
720    P.p=strat->S[i];
721    P.sev=strat->sevS[i];
722    if(kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P)!=i)
723    {
724      deleteInS(i,strat);
725      //remember destroying poly
726      BOOLEAN found=FALSE;
727      int j;
728      for(j=0;j<c->n;j++)
729  if(c->S->m[j]==P.p)
730  {
731    found=TRUE;
732    break;
733  }
734      if (!found)
735  pDelete(&P.p);
736      //remember additional reductors
737    }
738    else i++;
739  }
740}
741static int bucket_guess(kBucket* bucket){
742  int sum=0;
743  int i;
744  for (i=bucket->buckets_used;i>=0;i--){
745    if(bucket->buckets[i])
746       sum+=bucket->buckets_length[i];
747  }
748  return sum;
749}
750
751
752
753
754
755
756static int add_to_reductors(slimgb_alg* c, poly h, int len, BOOLEAN simplified){
757  //inDebug(h);
758  assume(lenS_correct(c->strat));
759  assume(len==pLength(h));
760  int i;
761//   if (c->is_char0)
762//        i=simple_posInS(c->strat,h,pSLength(h,len),c->is_char0);
763//   else
764//     i=simple_posInS(c->strat,h,len,c->is_char0);
765
766  LObject P; memset(&P,0,sizeof(P));
767  P.tailRing=c->r;
768  P.p=h; /*p_Copy(h,c->r);*/
769  P.FDeg=pFDeg(P.p,c->r);
770  if (!(simplified)){
771      if (!rField_is_Zp(c->r)){
772        pCleardenom(P.p);
773        pContent(P.p); //is a duplicate call, but belongs here
774
775      }
776      else
777        pNorm(P.p);
778    pNormalize(P.p);
779  }
780  wlen_type pq=pQuality(h,c,len);
781  i=simple_posInS(c->strat,h,len,pq);
782  c->strat->enterS(P,i,c->strat,-1);
783
784
785
786  c->strat->lenS[i]=len;
787  assume(pLength(c->strat->S[i])==c->strat->lenS[i]);
788  if(c->strat->lenSw!=NULL)
789    c->strat->lenSw[i]=pq;
790
791  return i;
792
793}
794static void length_one_crit(slimgb_alg* c, int pos, int len)
795{
796  if (c->nc)
797    return;
798  if (len==1)
799  {
800    int i;
801    for ( i=0;i<pos;i++)
802    {
803      if (c->lengths[i]==1)
804        c->states[pos][i]=HASTREP;
805    }
806    for ( i=pos+1;i<c->n;i++){
807      if (c->lengths[i]==1)
808        c->states[i][pos]=HASTREP;
809    }
810    if (!c->nc)
811      shorten_tails(c,c->S->m[pos]);
812  }
813}
814
815
816static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat)
817{
818  assume(old_pos>=new_pos);
819  poly p=strat->S[old_pos];
820  int ecart=strat->ecartS[old_pos];
821  long sev=strat->sevS[old_pos];
822  int s_2_r=strat->S_2_R[old_pos];
823  int length=strat->lenS[old_pos];
824  assume(length==pLength(strat->S[old_pos]));
825  wlen_type length_w;
826  if(strat->lenSw!=NULL)
827    length_w=strat->lenSw[old_pos];
828  int i;
829  for (i=old_pos; i>new_pos; i--)
830  {
831    strat->S[i] = strat->S[i-1];
832    strat->ecartS[i] = strat->ecartS[i-1];
833    strat->sevS[i] = strat->sevS[i-1];
834    strat->S_2_R[i] = strat->S_2_R[i-1];
835  }
836  if (strat->lenS!=NULL)
837    for (i=old_pos; i>new_pos; i--)
838      strat->lenS[i] = strat->lenS[i-1];
839  if (strat->lenSw!=NULL)
840    for (i=old_pos; i>new_pos; i--)
841      strat->lenSw[i] = strat->lenSw[i-1];
842
843  strat->S[new_pos]=p;
844  strat->ecartS[new_pos]=ecart;
845  strat->sevS[new_pos]=sev;
846  strat->S_2_R[new_pos]=s_2_r;
847  strat->lenS[new_pos]=length;
848  if(strat->lenSw!=NULL)
849    strat->lenSw[new_pos]=length_w;
850  //assume(lenS_correct(strat));
851}
852
853static int* make_connections(int from, int to, poly bound, slimgb_alg* c)
854{
855  ideal I=c->S;
856  int* cans=(int*) omalloc(c->n*sizeof(int));
857  int* connected=(int*) omalloc(c->n*sizeof(int));
858  cans[0]=to;
859  int cans_length=1;
860  connected[0]=from;
861  int last_cans_pos=-1;
862  int connected_length=1;
863  long neg_bounds_short= ~p_GetShortExpVector(bound,c->r);
864
865  int not_yet_found=cans_length;
866  int con_checked=0;
867  int pos;
868
869  while(TRUE){
870    if ((con_checked<connected_length)&& (not_yet_found>0)){
871      pos=connected[con_checked];
872      for(int i=0;i<cans_length;i++){
873        if (cans[i]<0) continue;
874        //FIXME: triv. syz. does not hold on noncommutative, check it for modules
875        if ((has_t_rep(pos,cans[i],c)) ||((!rIsPluralRing(c->r))&&(trivial_syzygie(pos,cans[i],bound,c))))
876{
877
878          connected[connected_length]=cans[i];
879          connected_length++;
880          cans[i]=-1;
881          --not_yet_found;
882
883          if (connected[connected_length-1]==to){
884            if (connected_length<c->n){
885              connected[connected_length]=-1;
886            }
887            omfree(cans);
888            return connected;
889          }
890        }
891      }
892      con_checked++;
893    }
894    else
895    {
896      for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++){
897        if (last_cans_pos==c->n){
898          if (connected_length<c->n){
899            connected[connected_length]=-1;
900          }
901          omfree(cans);
902          return connected;
903        }
904        if ((last_cans_pos==from)||(last_cans_pos==to))
905          continue;
906        if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)){
907          cans[cans_length]=last_cans_pos;
908          cans_length++;
909          break;
910        }
911      }
912      not_yet_found++;
913      for (int i=0;i<con_checked;i++){
914        if (has_t_rep(connected[i],last_cans_pos,c)){
915
916          connected[connected_length]=last_cans_pos;
917          connected_length++;
918          cans[cans_length-1]=-1;
919
920          --not_yet_found;
921          if (connected[connected_length-1]==to){
922            if (connected_length<c->n){
923              connected[connected_length]=-1;
924            }
925
926            omfree(cans);
927            return connected;
928          }
929          break;
930        }
931      }
932    }
933  }
934  if (connected_length<c->n){
935    connected[connected_length]=-1;
936  }
937
938  omfree(cans);
939  return connected;
940}
941#ifdef HEAD_BIN
942static inline poly p_MoveHead(poly p, omBin b)
943{
944  poly np;
945  omTypeAllocBin(poly, np, b);
946  memmove(np, p, b->sizeW*sizeof(long));
947  omFreeBinAddr(p);
948  return np;
949}
950#endif
951
952static void replace_pair(int & i, int & j,slimgb_alg* c)
953{
954  if (i<0) return;
955  c->soon_free=NULL;
956  int syz_deg;
957  poly lm=pOne();
958
959  pLcm(c->S->m[i], c->S->m[j], lm);
960  pSetm(lm);
961
962  int* i_con =make_connections(i,j,lm,c);
963
964  for (int n=0;((n<c->n) && (i_con[n]>=0));n++){
965    if (i_con[n]==j){
966      now_t_rep(i,j,c);
967      omfree(i_con);
968      p_Delete(&lm,c->r);
969      return;
970    }
971  }
972
973  int* j_con =make_connections(j,i,lm,c);
974
975//   if(c->n>1){
976//     if (i_con[1]>=0)
977//       i=i_con[1];
978//     else {
979//       if (j_con[1]>=0)
980//         j=j_con[1];
981//     }
982 // }
983
984  int sugar=pTotaldegree(lm);
985  p_Delete(&lm, c->r);
986    if(c->T_deg_full)//Sugar
987    {
988      int t_i=c->T_deg_full[i]-c->T_deg[i];
989      int t_j=c->T_deg_full[j]-c->T_deg[j];
990      sugar+=si_max(t_i,t_j);
991      //Print("\n max: %d\n",max(t_i,t_j));
992    }
993
994
995
996
997
998  for (int m=0;((m<c->n) && (i_con[m]>=0));m++){
999    if(c->T_deg_full!=NULL){
1000        int s1=c->T_deg_full[i_con[m]]+syz_deg-c->T_deg[i_con[m]];
1001        if (s1>sugar) continue;
1002    }
1003    if (c->weighted_lengths[i_con[m]]<c->weighted_lengths[i])
1004        i=i_con[m];
1005    }
1006    for (int m=0;((m<c->n) && (j_con[m]>=0));m++){
1007        if (c->T_deg_full!=NULL){
1008        int s1=c->T_deg_full[j_con[m]]+syz_deg-c->T_deg[j_con[m]];
1009        if (s1>sugar) continue;}
1010        if (c->weighted_lengths[j_con[m]]<c->weighted_lengths[j])
1011            j=j_con[m];
1012    }
1013
1014     //can also try dependend search
1015  omfree(i_con);
1016  omfree(j_con);
1017  return;
1018}
1019
1020
1021static void add_later(poly p, char* prot, slimgb_alg* c){
1022    int i=0;
1023    //check, if it is already in the queue
1024
1025
1026    while(c->add_later->m[i]!=NULL){
1027        if (p_LmEqual(c->add_later->m[i],p,c->r))
1028            return;
1029        i++;
1030    }
1031    if (TEST_OPT_PROT)
1032        PrintS(prot);
1033    c->add_later->m[i]=p;
1034}
1035static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen)
1036{
1037
1038
1039  if(strat->sl==-1) return 0;
1040  if (strat->lenSw) return pos_helper(strat,p,(wlen_type) wlen,(wlen_set) strat->lenSw,strat->S);
1041  return pos_helper(strat,p,len,strat->lenS,strat->S);
1042
1043}
1044
1045/*2
1046 *if the leading term of p
1047 *divides the leading term of some S[i] it will be canceled
1048 */
1049static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k,
1050                           kStrategy strat)
1051{
1052  assume(p_sev == pGetShortExpVector(p));
1053  if (!pLmShortDivisibleBy(p,p_sev, strat->S[*at], ~ strat->sevS[*at])) return;
1054  if (l>=strat->lenS[*at]) return;
1055  if (TEST_OPT_PROT)
1056    PrintS("!");
1057  mflush();
1058  //pDelete(&strat->S[*at]);
1059  deleteInS((*at),strat);
1060  (*at)--;
1061  (*k)--;
1062//  assume(lenS_correct(strat));
1063}
1064
1065
1066
1067static int iq_crit(const void* ap,const void* bp){
1068
1069  sorted_pair_node* a=*((sorted_pair_node**)ap);
1070  sorted_pair_node* b=*((sorted_pair_node**)bp);
1071  assume(a->i>a->j);
1072  assume(b->i>b->j);
1073
1074
1075  if (a->deg<b->deg) return -1;
1076  if (a->deg>b->deg) return 1;
1077  int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm);
1078  if(comp!=0)
1079    return comp;
1080  if (a->expected_length<b->expected_length) return -1;
1081  if (a->expected_length>b->expected_length) return 1;
1082  if (a->j>b->j) return 1;
1083  if (a->j<b->j) return -1;
1084  return 0;
1085}
1086static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r){
1087    if (rField_is_Q(r)) return s1+s2;
1088    else return s1*s2;
1089}
1090static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c){
1091    if ((c->is_char0) && (pLexOrder) &&(!c->is_homog))  {
1092        int c1=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r);
1093        int c2=slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
1094        wlen_type el1=c->weighted_lengths[i]/c1;
1095        assume(el1!=0);
1096        assume(c->weighted_lengths[i] %c1==0);
1097        wlen_type el2=c->weighted_lengths[j]/c2;
1098        assume(el2!=0);
1099        assume(c->weighted_lengths[j] %c2==0);
1100        //should be * for function fields
1101        //return (c1+c2) * (el1+el2-2);
1102        wlen_type res=coeff_mult_size_estimate(c1,c2,c->r);
1103        res*=el1+el2-2;
1104        return res;
1105
1106    }
1107    if (c->is_char0) {
1108        //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+
1109        //    slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
1110        if(!(TEST_V_COEFSTRAT)){
1111        wlen_type cs=
1112            coeff_mult_size_estimate(
1113                slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r),
1114                slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r),c->r);
1115        return (wlen_type)(c->lengths[i]+c->lengths[j]-2)*
1116            (wlen_type)cs;}
1117            else {
1118
1119            wlen_type cs=
1120            coeff_mult_size_estimate(
1121                slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r),
1122                slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r),c->r);
1123            cs*=cs;
1124        return (wlen_type)(c->lengths[i]+c->lengths[j]-2)*
1125            (wlen_type)cs;
1126            }
1127    }
1128    if ((pLexOrder) &&(!c->is_homog)) {
1129
1130        return (c->weighted_lengths[i]+c->weighted_lengths[j]-2);
1131    }
1132    return c->lengths[i]+c->lengths[j]-2;
1133
1134}
1135sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip)
1136{
1137
1138  assume(h!=NULL);
1139  poly got=gcd_of_terms(h,c->r);
1140  if((got!=NULL) &&(TEST_V_UPTORADICAL)) {
1141    poly copy=p_Copy(got,c->r);
1142    //p_wrp(got,c->r);
1143    BOOLEAN changed=monomial_root(got,c->r);
1144    if (changed)
1145    {
1146         poly div_by=pDivide(copy, got);
1147         poly iter=h;
1148         while(iter){
1149            pExpVectorSub(iter,div_by);
1150            pIter(iter);
1151         }
1152         p_Delete(&div_by, c->r);
1153         PrintS("U");
1154    }
1155    p_Delete(&copy,c->r);
1156  }
1157
1158#define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))
1159//  BOOLEAN corr=lenS_correct(c->strat);
1160  BOOLEAN R_found=FALSE;
1161  void* hp;
1162
1163  ++(c->n);
1164  ++(c->S->ncols);
1165  int i,j;
1166  i=c->n-1;
1167  sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i);
1168  int spc=0;
1169  if(c->n>c->array_lengths){
1170    c->array_lengths=c->array_lengths*2;
1171    assume(c->array_lengths>=c->n);
1172    ENLARGE(c->T_deg, int);
1173    ENLARGE(c->tmp_pair_lm,poly);
1174    ENLARGE(c->tmp_spn,sorted_pair_node*);
1175
1176    ENLARGE(c->short_Exps,long);
1177    ENLARGE(c->lengths,int);
1178    #ifndef HAVE_BOOST
1179    ENLARGE(c->states, char*);
1180    #endif
1181    ENLARGE(c->gcd_of_terms,poly);
1182    //if (c->weighted_lengths!=NULL) {
1183    ENLARGE(c->weighted_lengths,wlen_type);
1184    //}
1185    //ENLARGE(c->S->m,poly);
1186
1187  }
1188  pEnlargeSet(&c->S->m,c->n-1,1);
1189  if (c->T_deg_full)
1190    ENLARGE(c->T_deg_full,int);
1191  c->T_deg[i]=pTotaldegree(h);
1192  if(c->T_deg_full){
1193    c->T_deg_full[i]=pTotaldegree_full(h);
1194  }
1195
1196
1197  c->tmp_pair_lm[i]=pOne_Special(c->r);
1198
1199
1200  c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1201
1202
1203  c->lengths[i]=pLength(h);
1204
1205  //necessary for correct weighted length
1206
1207   if (!rField_is_Zp(c->r)){
1208    pCleardenom(h);
1209    pContent(h); //is a duplicate call, but belongs here
1210
1211  }
1212  else
1213    pNorm(h);
1214  pNormalize(h);
1215
1216  c->weighted_lengths[i]=pQuality(h, c, c->lengths[i]);
1217  c->gcd_of_terms[i]=got;
1218  #ifdef HAVE_BOOST
1219    c->states.push_back(dynamic_bitset<>(i));
1220
1221  #else
1222  if (i>0)
1223    c->states[i]=(char*)  omalloc(i*sizeof(char));
1224  else
1225    c->states[i]=NULL;
1226  #endif
1227
1228  c->S->m[i]=h;
1229  c->short_Exps[i]=p_GetShortExpVector(h,c->r);
1230
1231#undef ENLARGE
1232  if (p_GetComp(h,currRing)<=c->syz_comp){
1233  for (j=0;j<i;j++){
1234
1235
1236    #ifndef HAVE_BOOST
1237    c->states[i][j]=UNCALCULATED;
1238    #endif
1239    assume(p_LmDivisibleBy(c->S->m[i],c->S->m[j],c->r)==
1240     p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r));
1241
1242
1243    if (_p_GetComp(c->S->m[i],c->r)!=_p_GetComp(c->S->m[j],c->r)){
1244      //c->states[i][j]=UNCALCULATED;
1245      //WARNUNG: be careful
1246      continue;
1247    } else
1248    if ((!c->nc) && (c->lengths[i]==1) && (c->lengths[j]==1)){
1249      c->states[i][j]=HASTREP;
1250
1251      }
1252    else if ((!(c->nc)) &&  (pHasNotCF(c->S->m[i],c->S->m[j])))
1253    {
1254      c->easy_product_crit++;
1255      c->states[i][j]=HASTREP;
1256      continue;
1257    }
1258    else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c))
1259    {
1260      c->states[i][j]=HASTREP;
1261      c->extended_product_crit++;
1262
1263      //PrintS("E");
1264    }
1265      //  if (c->states[i][j]==UNCALCULATED){
1266
1267    if ((TEST_V_FINDMONOM) &&(!c->nc)) {
1268        //PrintS("COMMU");
1269       //  if (c->lengths[i]==c->lengths[j]){
1270//             poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
1271//             if (short_s==NULL){
1272//                 c->states[i][j]=HASTREP;
1273//             } else
1274//             {
1275//                 p_Delete(&short_s, currRing);
1276//             }
1277//         }
1278        if (c->lengths[i]+c->lengths[j]==3){
1279
1280
1281             poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
1282            if (short_s==NULL){
1283                c->states[i][j]=HASTREP;
1284            } else
1285            {
1286                assume(pLength(short_s)==1);
1287                if (TEST_V_UPTORADICAL)
1288                   monomial_root(short_s,c->r);
1289                int iS=
1290                   kFindDivisibleByInS_easy(c->strat,short_s, p_GetShortExpVector(short_s,c->r));
1291                if (iS<0){
1292                    //PrintS("N");
1293                    if (TRUE) {
1294                    c->states[i][j]=HASTREP;
1295                    add_later(short_s,"N",c);
1296                    } else p_Delete(&short_s,currRing);
1297                }
1298                else {
1299                    if (c->strat->lenS[iS]>1){
1300                        //PrintS("O");
1301                        if (TRUE) {
1302                        c->states[i][j]=HASTREP;
1303                        add_later(short_s,"O",c);
1304                        } else p_Delete(&short_s,currRing);
1305                    }
1306                    else
1307                     p_Delete(&short_s, currRing);
1308                     c->states[i][j]=HASTREP;
1309                }
1310
1311
1312            }
1313        }
1314    }
1315      //    if (short_s)
1316      //    {
1317    assume(spc<=j);
1318    sorted_pair_node* s=c->tmp_spn[spc];//(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1319    s->i=si_max(i,j);
1320    s->j=si_min(i,j);
1321    assume(s->j==j);
1322    s->expected_length=pair_weighted_length(i,j,c);//c->lengths[i]+c->lengths[j]-2;
1323
1324    poly lm=c->tmp_pair_lm[spc];//=pOne_Special();
1325
1326    pLcm(c->S->m[i], c->S->m[j], lm);
1327    pSetm(lm);
1328    s->deg=pTotaldegree(lm);
1329
1330    if(c->T_deg_full)//Sugar
1331    {
1332      int t_i=c->T_deg_full[s->i]-c->T_deg[s->i];
1333      int t_j=c->T_deg_full[s->j]-c->T_deg[s->j];
1334      s->deg+=si_max(t_i,t_j);
1335      //Print("\n max: %d\n",max(t_i,t_j));
1336    }
1337    s->lcm_of_lm=lm;
1338    //          pDelete(&short_s);
1339    //assume(lm!=NULL);
1340    nodes[spc]=s;
1341    spc++;
1342
1343  // }
1344  //else
1345  //{
1346        //c->states[i][j]=HASTREP;
1347  //}
1348  }
1349  }//if syz_comp end
1350 
1351 
1352 
1353 
1354  assume(spc<=i);
1355  //now ideal quotient crit
1356  qsort(nodes,spc,sizeof(sorted_pair_node*),iq_crit);
1357
1358    sorted_pair_node** nodes_final=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i);
1359  int spc_final=0;
1360  j=0;
1361  while(j<spc)
1362  {
1363    int lower=j;
1364    int upper;
1365    BOOLEAN has=FALSE;
1366    for(upper=lower+1;upper<spc;upper++)
1367    {
1368
1369      if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm))
1370      {
1371  break;
1372      }
1373      if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c))
1374  has=TRUE;
1375
1376    }
1377    upper=upper-1;
1378    int z;
1379    assume(spc_final<=j);
1380    for(z=0;z<spc_final;z++)
1381    {
1382      if(p_LmDivisibleBy(nodes_final[z]->lcm_of_lm,nodes[lower]->lcm_of_lm,c->r))
1383      {
1384  has=TRUE;
1385  break;
1386      }
1387    }
1388
1389    if(has)
1390    {
1391      for(;lower<=upper;lower++)
1392      {
1393  //free_sorted_pair_node(nodes[lower],c->r);
1394  //omfree(nodes[lower]);
1395  nodes[lower]=NULL;
1396      }
1397      j=upper+1;
1398      continue;
1399    }
1400    else
1401    {
1402      nodes[lower]->lcm_of_lm=pCopy(nodes[lower]->lcm_of_lm);
1403      assume(_p_GetComp(c->S->m[nodes[lower]->i],c->r)==_p_GetComp(c->S->m[nodes[lower]->j],c->r));
1404      nodes_final[spc_final]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1405
1406      *(nodes_final[spc_final++])=*(nodes[lower]);
1407      //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1408      nodes[lower]=NULL;
1409      for(lower=lower+1;lower<=upper;lower++)
1410      {
1411  //  free_sorted_pair_node(nodes[lower],c->r);
1412  //omfree(nodes[lower]);
1413  nodes[lower]=NULL;
1414      }
1415      j=upper+1;
1416      continue;
1417    }
1418  }
1419
1420  //  Print("i:%d,spc_final:%d",i,spc_final);
1421
1422
1423
1424
1425  assume(spc_final<=spc);
1426  omfree(nodes);
1427  nodes=NULL;
1428
1429  add_to_reductors(c, h, c->lengths[c->n-1], TRUE);
1430  //i=posInS(c->strat,c->strat->sl,h,0 ecart);
1431  if (!(c->nc)){
1432    if (c->lengths[c->n-1]==1)
1433      shorten_tails(c,c->S->m[c->n-1]);
1434  }
1435  //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths
1436
1437  //for(i=c->strat->sl; i>0;i--)
1438  //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
1439  if (c->Rcounter>50) {
1440    c->Rcounter=0;
1441    cleanS(c->strat,c);
1442  }
1443  if(!ip){
1444    qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
1445
1446
1447    c->apairs=spn_merge(c->apairs,c->pair_top+1,nodes_final,spc_final,c);
1448    c->pair_top+=spc_final;
1449    clean_top_of_pair_list(c);
1450    omfree(nodes_final);
1451    return NULL;
1452  }
1453  {
1454    *ip=spc_final;
1455    return nodes_final;
1456  }
1457
1458
1459
1460}
1461
1462
1463static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n)
1464{
1465  m=nInit(1);
1466  if (h==NULL) return NULL;
1467
1468  assume(len==pLength(h));
1469  kStrategy strat=c->strat;
1470  if (0 > strat->sl)
1471  {
1472    return h;
1473  }
1474  int j;
1475
1476  LObject P(h);
1477  P.SetShortExpVector();
1478  P.bucket = kBucketCreate(currRing);
1479  // BOOLEAN corr=lenS_correct(strat);
1480  kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/);
1481  //wlen_set lenSw=(wlen_set) c->strat->lenS;
1482  //FIXME: plainly wrong
1483  //strat->lenS;
1484  //if (strat->lenSw!=NULL)
1485  //  lenSw=strat->lenSw;
1486  //int max_pos=simple_posInS(strat,P.p);
1487  loop
1488    {
1489
1490      j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P);
1491      if ((j>=0) && ((!n)||
1492        ((strat->lenS[j]<=n) &&
1493         ((strat->lenSw==NULL)||
1494         (strat->lenSw[j]<=n)))))
1495      {
1496
1497
1498        nNormalize(pGetCoeff(P.p));
1499#ifdef KDEBUG
1500        if (TEST_OPT_DEBUG)
1501        {
1502          PrintS("red:");
1503          wrp(h);
1504          PrintS(" with ");
1505          wrp(strat->S[j]);
1506        }
1507#endif
1508
1509        number coef=kBucketPolyRed(P.bucket,strat->S[j],
1510                                   strat->lenS[j]/*pLength(strat->S[j])*/,
1511                                   strat->kNoether);
1512  number m2=nMult(m,coef);
1513  nDelete(&m);
1514  m=m2;
1515        nDelete(&coef);
1516        h = kBucketGetLm(P.bucket);
1517
1518  if (h==NULL) {
1519    len=0;
1520    kBucketDestroy(&P.bucket);
1521    return
1522    NULL;}
1523        P.p=h;
1524        P.t_p=NULL;
1525        P.SetShortExpVector();
1526#ifdef KDEBUG
1527        if (TEST_OPT_DEBUG)
1528        {
1529          PrintS("\nto:");
1530          wrp(h);
1531          PrintLn();
1532        }
1533#endif
1534      }
1535      else
1536      {
1537        kBucketClear(P.bucket,&(P.p),&len);
1538        kBucketDestroy(&P.bucket);
1539        pNormalize(P.p);
1540  assume(len==(pLength(P.p)));
1541        return P.p;
1542      }
1543    }
1544}
1545
1546
1547
1548static poly redTailShort(poly h, kStrategy strat){
1549  if (h==NULL) return NULL;//n_Init(1,currRing);
1550  if (TEST_V_MODPSOLVSB){
1551    bit_reduce(pNext(h), strat->tailRing);
1552  }
1553  int sl=strat->sl;
1554  int i;
1555  int len=pLength(h);
1556  for(i=0;i<=strat->sl;i++){
1557    if((strat->lenS[i]>2) || ((strat->lenSw!=NULL) && (strat->lenSw[i]>2)))
1558      break;
1559  }
1560  return(redNFTail(h,i-1,strat, len));
1561}
1562
1563static void line_of_extended_prod(int fixpos,slimgb_alg* c){
1564    if (c->gcd_of_terms[fixpos]==NULL)
1565  {
1566    c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r);
1567    if (c->gcd_of_terms[fixpos])
1568    {
1569      int i;
1570      for(i=0;i<fixpos;i++)
1571        if((c->states[fixpos][i]!=HASTREP)&& (extended_product_criterion(c->S->m[fixpos],c->gcd_of_terms[fixpos], c->S->m[i],c->gcd_of_terms[i],c)))
1572{
1573          c->states[fixpos][i]=HASTREP;
1574    c->extended_product_crit++;
1575}
1576      for(i=fixpos+1;i<c->n;i++)
1577        if((c->states[i][fixpos]!=HASTREP)&& (extended_product_criterion(c->S->m[fixpos],c->gcd_of_terms[fixpos], c->S->m[i],c->gcd_of_terms[i],c)))
1578  {        c->states[i][fixpos]=HASTREP;
1579  c->extended_product_crit++;
1580  }
1581    }
1582  }
1583}
1584static void c_S_element_changed_hook(int pos, slimgb_alg* c){
1585  length_one_crit(c,pos, c->lengths[pos]);
1586  if (!c->nc)
1587    line_of_extended_prod(pos,c);
1588}
1589class poly_tree_node {
1590public:
1591  poly p;
1592  poly_tree_node* l;
1593  poly_tree_node* r;
1594  int n;
1595  poly_tree_node(int sn):l(NULL),r(NULL),n(sn){}
1596};
1597class exp_number_builder{
1598public:
1599  poly_tree_node* top_level;
1600  int n;
1601  int get_n(poly p);
1602  exp_number_builder():top_level(0),n(0){}
1603};
1604int exp_number_builder::get_n(poly p){
1605  poly_tree_node** node=&top_level;
1606  while(*node!=NULL){
1607    int c=pLmCmp(p,(*node)->p);
1608    if (c==0) return (*node)->n;
1609    if (c==-1) node=&((*node)->r);
1610    else
1611      node=&((*node)->l);
1612  }
1613  (*node)= new poly_tree_node(n);
1614  n++;
1615  (*node)->p=pLmInit(p);
1616  return (*node)->n;
1617}
1618
1619//mac_polys exp are smaller iff they are greater by monomial ordering
1620//corresponding to solving linear equations notation
1621
1622//! obsolete
1623struct int_poly_pair{
1624  poly p;
1625  int n;
1626};
1627
1628
1629//! obsolete
1630void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset){
1631    if(!k) return;
1632    t2ippa_rec(ip,ia,k->l,offset);
1633    ip[offset]=k->p;
1634    ia[k->n]=offset;
1635    ++offset;
1636
1637    t2ippa_rec(ip,ia,k->r,offset);
1638    delete k;
1639  }
1640
1641//! obsolete
1642void t2ippa(poly* ip,int* ia,exp_number_builder & e){
1643
1644  int o=0;
1645  t2ippa_rec(ip,ia,e.top_level,o);
1646}
1647int anti_poly_order(const void* a, const void* b){
1648  return -pLmCmp(((int_poly_pair*) a)->p,((int_poly_pair*) b)->p );
1649}
1650
1651BOOLEAN is_valid_ro(red_object & ro){
1652  red_object r2=ro;
1653  ro.validate();
1654  if ((r2.p!=ro.p)||(r2.sev!=ro.sev)) return FALSE;
1655  return TRUE;
1656}
1657
1658
1659
1660static void go_on (slimgb_alg* c){
1661  //set limit of 1000 for multireductions, at the moment for
1662  //programming reasons
1663  int i=0;
1664  c->average_length=0;
1665  for(i=0;i<c->n;i++){
1666    c->average_length+=c->lengths[i];
1667  }
1668  c->average_length=c->average_length/c->n;
1669  i=0;
1670  poly* p=(poly*) omalloc((PAR_N+1)*sizeof(poly));//nullterminated
1671
1672  int curr_deg=-1;
1673  while(i<PAR_N){
1674    sorted_pair_node* s=top_pair(c);//here is actually chain criterium done
1675
1676
1677    if (!s) break;
1678
1679    if(curr_deg>=0){
1680      if (s->deg >curr_deg) break;
1681    }
1682
1683    else curr_deg=s->deg;
1684    quick_pop_pair(c);
1685    if(s->i>=0){
1686      //be careful replace_pair use createShortSpoly which is not noncommutative
1687      now_t_rep(s->i,s->j,c);
1688    replace_pair(s->i,s->j,c);
1689
1690    if(s->i==s->j) {
1691      free_sorted_pair_node(s,c->r);
1692      continue;
1693    }
1694    now_t_rep(s->i,s->j,c);
1695    }
1696    poly h;
1697    if(s->i>=0){
1698      if (!c->nc)
1699  h=ksOldCreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r);
1700      else
1701  h= nc_CreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r);
1702    }
1703    else
1704      h=s->lcm_of_lm;
1705    // if(s->i>=0)
1706//       now_t_rep(s->j,s->i,c);
1707    number coef;
1708    int mlen=pLength(h);
1709    if (!c->nc){
1710      h=redNF2(h,c,mlen,coef,2);
1711      redTailShort(h,c->strat);
1712      nDelete(&coef);
1713    }
1714    free_sorted_pair_node(s,c->r);
1715    if(!h) continue;
1716    int len=pLength(h);
1717    p[i]=h;
1718
1719    i++;
1720  }
1721  p[i]=NULL;
1722//  pre_comp(p,i,c);
1723  if(i==0){
1724    omfree(p);
1725    return;
1726  }
1727  #ifdef TGB_RESORT_PAIRS
1728  c->replaced=new bool[c->n];
1729  c->used_b=FALSE;
1730  #endif
1731  red_object* buf=(red_object*) omalloc(i*sizeof(red_object));
1732  c->normal_forms+=i;
1733  int j;
1734  for(j=0;j<i;j++){
1735    buf[j].p=p[j];
1736    buf[j].sev=pGetShortExpVector(p[j]);
1737    buf[j].bucket = kBucketCreate(currRing);
1738
1739    int len=pLength(p[j]);
1740    kBucketInit(buf[j].bucket,buf[j].p,len);
1741    buf[j].initial_quality=buf[j].guess_quality(c);
1742    assume(buf[j].initial_quality>=0);
1743  }
1744  omfree(p);
1745  qsort(buf,i,sizeof(red_object),red_object_better_gen);
1746//    Print("\ncurr_deg:%i\n",curr_deg);
1747  if (TEST_OPT_PROT)
1748  {
1749    Print("%dM[%d,",curr_deg,i);
1750  }
1751#ifdef FIND_DETERMINISTIC
1752  c->modifiedS=(BOOLEAN*) omalloc((c->strat->sl+1)*sizeof(BOOLEAN));
1753  c->expandS=(poly*) omalloc((1)*sizeof(poly));
1754  c->expandS[0]=NULL;
1755  int z2;
1756  for(z2=0;z2<=c->strat->sl;z2++)
1757    c->modifiedS[z2]=FALSE;
1758#endif
1759  multi_reduction(buf, i, c);
1760  #ifdef TGB_RESORT_PAIRS
1761  if (c->used_b) {
1762    if (TEST_OPT_PROT)
1763        PrintS("B");
1764    int e;
1765    for(e=0;e<=c->pair_top;e++){
1766        if(c->apairs[e]->i<0) continue;
1767        assume(c->apairs[e]->j>=0);
1768        if ((c->replaced[c->apairs[e]->i])||(c->replaced[c->apairs[e]->j])) {
1769            sorted_pair_node* s=c->apairs[e];
1770            s->expected_length=pair_weighted_length(s->i,s->j,c);
1771        }
1772    }
1773    qsort(c->apairs,c->pair_top+1,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
1774  }
1775  #endif
1776#ifdef TGB_DEBUG
1777 {
1778   int k;
1779   for(k=0;k<i;k++)
1780   {
1781     assume(kFindDivisibleByInS_easy(c->strat,buf[k])<0);
1782     int k2;
1783     for(k2=0;k2<i;k2++)
1784     {
1785       if(k==k2) continue;
1786       assume((!(p_LmDivisibleBy(buf[k].p,buf[k2].p,c->r)))||(wrp(buf[k].p),Print(" k %d k2 %d ",k,k2),wrp(buf[k2].p),FALSE));
1787     }
1788   }
1789 }
1790#endif
1791  //resort S
1792#ifdef FIND_DETERMINISTIC
1793  for(z2=0;z2<=c->strat->sl;z2++)
1794  {
1795    if (c->modifiedS[z2])
1796    {
1797      wlen_type qual;
1798      int new_pos;
1799      if (c->strat->lenSw!=NULL)
1800          new_pos=simple_posInS(c->strat,c->strat->S[z2],strat->lenS[z2],strat->Sw[z2]);
1801      else
1802          new_pos=simple_posInS(c->strat,c->strat->S[z2],strat->lenS[z2],lenS[z2]);
1803
1804      if (new_pos<z2)
1805      {
1806         move_forward_in_S(z2,new_pos,c->strat);
1807      }
1808
1809      assume(new_pos<=z2);
1810    }
1811  }
1812  for(z2=0;c->expandS[z2]!=NULL;z2++)
1813  {
1814    add_to_reductors(c,c->expandS[z2],pLength(c->expandS[z2]));
1815    // PrintS("E");
1816  }
1817  omfree(c->modifiedS);
1818  c->modifiedS=NULL;
1819  omfree(c->expandS);
1820  c->expandS=NULL;
1821#endif
1822  if (TEST_OPT_PROT)
1823      Print("%i]",i);
1824
1825  int* ibuf=(int*) omalloc(i*sizeof(int));
1826  sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(i*sizeof(sorted_pair_node**));
1827  for(j=0;j<i;j++)
1828  {
1829    int len;
1830    poly p;
1831    buf[j].flatten();
1832    kBucketClear(buf[j].bucket,&p, &len);
1833    kBucketDestroy(&buf[j].bucket);
1834
1835    if (!c->nc) {
1836      if (TEST_OPT_REDTAIL){
1837      p=redNFTail(p,c->strat->sl,c->strat, 0);
1838      } else {
1839      p=redTailShort(p, c->strat);
1840      }
1841      }
1842    sbuf[j]=add_to_basis_ideal_quotient(p,c,ibuf+j);
1843    //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
1844  }
1845  int sum=0;
1846  for(j=0;j<i;j++){
1847    sum+=ibuf[j];
1848  }
1849  sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*));
1850  int partsum=0;
1851  for(j=0;j<i;j++)
1852  {
1853    memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*));
1854    omfree(sbuf[j]);
1855    partsum+=ibuf[j];
1856  }
1857
1858  qsort(big_sbuf,sum,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
1859  c->apairs=spn_merge(c->apairs,c->pair_top+1,big_sbuf,sum,c);
1860  c->pair_top+=sum;
1861  clean_top_of_pair_list(c);
1862  omfree(big_sbuf);
1863  omfree(sbuf);
1864  omfree(ibuf);
1865  omfree(buf);
1866#ifdef TGB_DEBUG
1867  int z;
1868  for(z=1;z<=c->pair_top;z++)
1869  {
1870    assume(pair_better(c->apairs[z],c->apairs[z-1],c));
1871  }
1872#endif
1873  if (TEST_OPT_PROT)
1874      Print("(%d)",c->pair_top+1);
1875  while(!(idIs0(c->add_later))){
1876    ideal add=c->add_later;
1877    idSkipZeroes(add);
1878    for(j=0;j<add->idelems();j++){
1879        assume(pLength(add->m[j])==1);
1880        p_SetCoeff(add->m[j],n_Init(1,currRing),currRing);
1881
1882    }
1883    ideal add2=kInterRed(add,NULL);
1884    id_Delete(&add,currRing);
1885    idSkipZeroes(add2);
1886    c->add_later=idInit(ADD_LATER_SIZE,c->S->rank);
1887    memset(c->add_later->m,0,ADD_LATER_SIZE*sizeof(poly));
1888//     for(i=0;i<add2->idelems();i++){
1889//       if (add2->m[i]!=NULL)
1890//           add_to_basis_ideal_quotient(add2->m[i],-1,-1,c,NULL);
1891//       add2->m[i]=NULL;
1892//     }
1893    int i=add2->idelems();
1894    int* ibuf=(int*) omalloc(i*sizeof(int));
1895  sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(i*sizeof(sorted_pair_node**));
1896
1897  for(j=0;j<i;j++)
1898  {
1899    int len;
1900    poly p;
1901    //buf[j].flatten();
1902    //kBucketClear(buf[j].bucket,&p, &len);
1903    //kBucketDestroy(&buf[j].bucket);
1904    p=add2->m[j];
1905    add2->m[j]=NULL;
1906
1907    sbuf[j]=add_to_basis_ideal_quotient(p,c,ibuf+j);
1908    //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
1909  }
1910  int sum=0;
1911  for(j=0;j<i;j++){
1912    sum+=ibuf[j];
1913  }
1914  sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*));
1915  int partsum=0;
1916  for(j=0;j<i;j++)
1917  {
1918    memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*));
1919    omfree(sbuf[j]);
1920    partsum+=ibuf[j];
1921  }
1922
1923  qsort(big_sbuf,sum,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
1924  c->apairs=spn_merge(c->apairs,c->pair_top+1,big_sbuf,sum,c);
1925  c->pair_top+=sum;
1926  clean_top_of_pair_list(c);
1927  omfree(big_sbuf);
1928  omfree(sbuf);
1929  omfree(ibuf);
1930  //omfree(buf);
1931    id_Delete(&add2, c->r);
1932  }
1933  #ifdef TGB_RESORT_PAIRS
1934  delete c->replaced;
1935  c->replaced=NULL;
1936  c->used_b=FALSE;
1937  #endif
1938  return;
1939}
1940
1941
1942
1943#ifdef REDTAIL_S
1944
1945static poly redNFTail (poly h,const int sl,kStrategy strat, int len)
1946{
1947  if (h==NULL) return NULL;
1948  pTest(h);
1949  if (0 > sl)
1950    return h;
1951  if (pNext(h)==NULL) return h;
1952
1953  int j;
1954  poly res=h;
1955  poly act=res;
1956  LObject P(pNext(h));
1957  pNext(res)=NULL;
1958  P.bucket = kBucketCreate(currRing);
1959  len--;
1960  h=P.p;
1961  if (len <=0) len=pLength(h);
1962  kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/);
1963  pTest(h);
1964  loop
1965  {
1966      P.p=h;
1967      P.t_p=NULL;
1968      P.SetShortExpVector();
1969      loop
1970      {
1971          j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P);
1972          if (j>=0)
1973          {
1974#ifdef REDTAIL_PROT
1975            PrintS("r");
1976#endif
1977            nNormalize(pGetCoeff(P.p));
1978#ifdef KDEBUG
1979            if (TEST_OPT_DEBUG)
1980            {
1981              PrintS("red tail:");
1982              wrp(h);
1983              PrintS(" with ");
1984              wrp(strat->S[j]);
1985            }
1986#endif
1987            number coef;
1988            pTest(strat->S[j]);
1989            coef=kBucketPolyRed(P.bucket,strat->S[j],
1990                                strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether);
1991            pMult_nn(res,coef);
1992            nDelete(&coef);
1993            h = kBucketGetLm(P.bucket);
1994            pTest(h);
1995            if (h==NULL)
1996            {
1997#ifdef REDTAIL_PROT
1998              PrintS(" ");
1999#endif
2000        kBucketDestroy(&P.bucket);
2001              return res;
2002            }
2003            pTest(h);
2004            P.p=h;
2005            P.t_p=NULL;
2006            P.SetShortExpVector();
2007#ifdef KDEBUG
2008            if (TEST_OPT_DEBUG)
2009            {
2010              PrintS("\nto tail:");
2011              wrp(h);
2012              PrintLn();
2013            }
2014#endif
2015          }
2016          else
2017          {
2018#ifdef REDTAIL_PROT
2019            PrintS("n");
2020#endif
2021            break;
2022          }
2023      } /* end loop current mon */
2024      //   poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
2025      //act->next=tmp;pIter(act);
2026      act->next=kBucketExtractLm(P.bucket);pIter(act);
2027      h = kBucketGetLm(P.bucket);
2028      if (h==NULL)
2029      {
2030#ifdef REDTAIL_PROT
2031        PrintS(" ");
2032#endif
2033  kBucketDestroy(&P.bucket);
2034        return res;
2035      }
2036      pTest(h);
2037  }
2038}
2039#endif
2040
2041
2042//try to fill, return FALSE iff queue is empty
2043
2044//transfers ownership of m to mat
2045void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m){
2046  assume(mat->mp[row]==NULL);
2047  mat->mp[row]=m;
2048#ifdef TGB_DEBUG
2049  mac_poly r=m;
2050  while(r){
2051    assume(r->exp<mat->columns);
2052    r=r->next;
2053  }
2054#endif
2055}
2056poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index){
2057  poly p=NULL;
2058  poly* set_this=&p;
2059  mac_poly r=mat->mp[row];
2060  mat->mp[row]=NULL;
2061  while(r)
2062  {
2063    (*set_this)=pLmInit(monoms[monom_index-1-r->exp]);
2064    pSetCoeff((*set_this),r->coef);
2065    set_this=&((*set_this)->next);
2066    mac_poly old=r;
2067    r=r->next;
2068    delete old;
2069
2070  }
2071  return p;
2072
2073}
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085static int poly_crit(const void* ap1, const void* ap2){
2086  poly p1,p2;
2087  p1=*((poly*) ap1);
2088  p2=*((poly*)ap2);
2089
2090  int c=pLmCmp(p1,p2);
2091  if (c !=0) return c;
2092  int l1=pLength(p1);
2093  int l2=pLength(p2);
2094  if (l1<l2) return -1;
2095  if (l1>l2) return 1;
2096  return 0;
2097}
2098slimgb_alg::slimgb_alg(ideal I, int syz_comp,BOOLEAN F4){
2099
2100  this->syz_comp=syz_comp;
2101  r=currRing;
2102  nc=rIsPluralRing(r);
2103
2104  is_homog=TRUE;
2105  {
2106    int hz;
2107    for(hz=0;hz<IDELEMS(I);hz++){
2108      assume(I->m[hz]!=NULL);
2109      int d=pTotaldegree(I->m[hz]);
2110      poly t=I->m[hz]->next;
2111      while(t)
2112      {
2113        if (d!=pTotaldegree(t,r))
2114        {
2115          is_homog=FALSE;
2116          break;
2117        }
2118        t=t->next;
2119      }
2120      if(!(is_homog)) break;
2121    }
2122  }
2123  //  Print("is homog:%d",c->is_homog);
2124  void* h;
2125  poly hp;
2126  int i,j;
2127  to_destroy=NULL;
2128  easy_product_crit=0;
2129  extended_product_crit=0;
2130  if (rField_is_Zp(r))
2131    is_char0=FALSE;
2132  else
2133    is_char0=TRUE;
2134  //not fully correct
2135  //(rChar()==0);
2136  F4_mode=F4;
2137  this->doubleSugar=TRUE;
2138  if ((!F4_mode)&&(!is_homog) &&(pLexOrder)){
2139    this->doubleSugar=TRUE;
2140  }
2141  else this->doubleSugar=FALSE;
2142  reduction_steps=0;
2143  last_index=-1;
2144
2145  F=NULL;
2146  F_minus=NULL;
2147
2148  Rcounter=0;
2149
2150  soon_free=NULL;
2151
2152  tmp_lm=pOne();
2153
2154  normal_forms=0;
2155  current_degree=1;
2156
2157  max_pairs=5*I->idelems();
2158
2159  apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*max_pairs);
2160  pair_top=-1;
2161
2162  int n=I->idelems();
2163  array_lengths=n;
2164
2165
2166  i=0;
2167  this->n=0;
2168  T_deg=(int*) omalloc(n*sizeof(int));
2169  if((!(is_homog)) &&(pLexOrder))
2170    T_deg_full=(int*) omalloc(n*sizeof(int));
2171  else
2172    T_deg_full=NULL;
2173  tmp_pair_lm=(poly*) omalloc(n*sizeof(poly));
2174  tmp_spn=(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*));
2175  lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long));
2176#ifdef HEAD_BIN
2177  HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long));
2178#endif
2179  /* omUnGetSpecBin(&(c->HeadBin)); */
2180  #ifndef HAVE_BOOST
2181  h=omalloc(n*sizeof(char*));
2182
2183  states=(char**) h;
2184  #endif
2185  h=omalloc(n*sizeof(int));
2186  lengths=(int*) h;
2187  weighted_lengths=(wlen_type*)omalloc(n*sizeof(wlen_type));
2188  gcd_of_terms=(poly*) omalloc(n*sizeof(poly));
2189
2190  short_Exps=(long*) omalloc(n*sizeof(long));
2191  if (F4_mode)
2192    S=idInit(n,I->rank);
2193  else
2194    S=idInit(1,I->rank);
2195  strat=new skStrategy;
2196  strat->syzComp = 0;
2197  initBuchMoraCrit(strat);
2198  initBuchMoraPos(strat);
2199  strat->initEcart = initEcartBBA;
2200  strat->tailRing=r;
2201  strat->enterS = enterSBba;
2202  strat->sl = -1;
2203  i=n;
2204  i=1;//some strange bug else
2205  /* initS(c->S,NULL,c->strat); */
2206  /* intS start: */
2207  // i=((i+IDELEMS(c->S)+15)/16)*16;
2208  strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/
2209  strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long));
2210  /*initsevS(i);*/
2211  strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/
2212  strat->fromQ=NULL;
2213  strat->Shdl=idInit(1,1);
2214  strat->S=strat->Shdl->m;
2215  strat->lenS=(int*)omAlloc0(i*sizeof(int));
2216  if((is_char0)||((pLexOrder) &&(!is_homog)))
2217    strat->lenSw=(wlen_type*)omAlloc0(i*sizeof(wlen_type));
2218  else
2219    strat->lenSw=NULL;
2220  sorted_pair_node* si;
2221  assume(n>0);
2222  add_to_basis_ideal_quotient(I->m[0],this,NULL);
2223
2224  assume(strat->sl==strat->Shdl->idelems()-1);
2225  if(!(F4_mode))
2226  {
2227    for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
2228    {
2229      //     add_to_basis(I->m[i],-1,-1,c);
2230      si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
2231      si->i=-1;
2232      si->j=-2;
2233      si->expected_length=pQuality(I->m[i],this,pLength(I->m[i]));
2234      si->deg=pTotaldegree(I->m[i]);
2235      if (!rField_is_Zp(r)){
2236        pCleardenom(I->m[i]);
2237      }
2238      si->lcm_of_lm=I->m[i];
2239
2240      //      c->apairs[n-1-i]=si;
2241      apairs[n-i-1]=si;
2242      ++(pair_top);
2243    }
2244  }
2245  else
2246  {
2247    for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
2248      add_to_basis_ideal_quotient(I->m[i],this,NULL);
2249  }
2250  for(i=0;i<I->idelems();i++)
2251  {
2252    I->m[i]=NULL;
2253  }
2254  idDelete(&I);
2255  add_later=idInit(ADD_LATER_SIZE,S->rank);
2256  memset(add_later->m,0,ADD_LATER_SIZE*sizeof(poly));
2257}
2258slimgb_alg::~slimgb_alg(){
2259  id_Delete(&add_later,r);
2260  int i,j;
2261  slimgb_alg* c=this;
2262  while(c->to_destroy)
2263  {
2264    pDelete(&(c->to_destroy->p));
2265    poly_list_node* old=c->to_destroy;
2266    c->to_destroy=c->to_destroy->next;
2267    omfree(old);
2268  }
2269  while(c->F)
2270  {
2271    for(i=0;i<c->F->size;i++){
2272      pDelete(&(c->F->mp[i].m));
2273    }
2274    omfree(c->F->mp);
2275    c->F->mp=NULL;
2276    mp_array_list* old=c->F;
2277    c->F=c->F->next;
2278    omfree(old);
2279  }
2280  while(c->F_minus)
2281  {
2282    for(i=0;i<c->F_minus->size;i++){
2283      pDelete(&(c->F_minus->p[i]));
2284    }
2285    omfree(c->F_minus->p);
2286    c->F_minus->p=NULL;
2287    poly_array_list* old=c->F_minus;
2288    c->F_minus=c->F_minus->next;
2289    omfree(old);
2290  }
2291  #ifndef HAVE_BOOST
2292  for(int z=1 /* zero length at 0 */;z<c->n;z++){
2293    omfree(c->states[z]);
2294  }
2295  omfree(c->states);
2296  #endif
2297
2298  omfree(c->lengths);
2299  omfree(c->weighted_lengths);
2300  for(int z=0;z<c->n;z++)
2301  {
2302    pDelete(&c->tmp_pair_lm[z]);
2303    omfree(c->tmp_spn[z]);
2304  }
2305  omfree(c->tmp_pair_lm);
2306  omfree(c->tmp_spn);
2307
2308  omfree(c->T_deg);
2309  if(c->T_deg_full)
2310    omfree(c->T_deg_full);
2311
2312  omFree(c->strat->ecartS);
2313  omFree(c->strat->sevS);
2314//   initsevS(i);
2315  omFree(c->strat->S_2_R);
2316
2317
2318  omFree(c->strat->lenS);
2319
2320  if(c->strat->lenSw)  omFree(c->strat->lenSw);
2321
2322
2323
2324
2325  for(i=0;i<c->n;i++){
2326    if(c->gcd_of_terms[i])
2327      pDelete(&(c->gcd_of_terms[i]));
2328  }
2329  omfree(c->gcd_of_terms);
2330
2331  omfree(c->apairs);
2332  if (TEST_OPT_PROT)
2333  {
2334    Print("calculated %d NFs\n",c->normal_forms);
2335    Print("applied %i product crit, %i extended_product crit \n", c->easy_product_crit, c->extended_product_crit);
2336  }
2337  int deleted_form_c_s=0;
2338
2339  for(i=0;i<=c->strat->sl;i++){
2340    if (!c->strat->S[i]) continue;
2341    BOOLEAN found=FALSE;
2342    for(j=0;j<c->n;j++){
2343      if (c->S->m[j]==c->strat->S[i]){
2344        found=TRUE;
2345        break;
2346      }
2347    }
2348    if(!found) pDelete(&c->strat->S[i]);
2349  }
2350//   for(i=0;i<c->n;i++){
2351//     if (c->rep[i]!=i){
2352// //       for(j=0;j<=c->strat->sl;j++){
2353// //   if(c->strat->S[j]==c->S->m[i]){
2354// //     c->strat->S[j]=NULL;
2355// //     break;
2356// //   }
2357// //       }
2358// //      PrintS("R_delete");
2359//       pDelete(&c->S->m[i]);
2360//     }
2361//   }
2362
2363
2364  for(i=0;i<c->n;i++)
2365  {
2366    assume(c->S->m[i]!=NULL);
2367    if (p_GetComp(c->S->m[i],currRing)>this->syz_comp) continue;
2368    for(j=0;j<c->n;j++)
2369    {
2370      if((c->S->m[j]==NULL)||(i==j))
2371        continue;
2372      assume(p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j],
2373             c->S->m[i],~c->short_Exps[i],
2374             c->r)==p_LmDivisibleBy(c->S->m[j],
2375             c->S->m[i],
2376             c->r));
2377      if (p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j],
2378          c->S->m[i],~c->short_Exps[i],
2379          c->r))
2380      {
2381        pDelete(&c->S->m[i]);
2382        break;
2383      }
2384    }
2385  }
2386  omfree(c->short_Exps);
2387
2388
2389  ideal I=c->S;
2390
2391  IDELEMS(I)=c->n;
2392
2393  idSkipZeroes(I);
2394  for(i=0;i<=c->strat->sl;i++)
2395    c->strat->S[i]=NULL;
2396  id_Delete(&c->strat->Shdl,c->r);
2397  pDelete(&c->tmp_lm);
2398  omUnGetSpecBin(&lm_bin);
2399  delete c->strat;
2400}
2401ideal t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode){
2402
2403  //  Print("QlogSize(0) %d, QlogSize(1) %d,QlogSize(-2) %d, QlogSize(5) %d\n", QlogSize(nlInit(0)),QlogSize(nlInit(1)),QlogSize(nlInit(-2)),QlogSize(nlInit(5)));
2404 
2405  if (TEST_OPT_PROT)
2406    if (F4_mode)
2407      PrintS("F4 Modus \n");
2408
2409  //debug_Ideal=arg_debug_Ideal;
2410  //if (debug_Ideal) PrintS("DebugIdeal received\n");
2411  // Print("Idelems %i \n----------\n",IDELEMS(arg_I));
2412  ideal I=idCompactify(arg_I);
2413   int i;
2414  if (idIs0(I)) return I;
2415  for(i=0;i<IDELEMS(I);i++)
2416  {
2417    assume(I->m[i]!=NULL);
2418    simplify_poly(I->m[i],currRing);
2419  }
2420 
2421
2422  qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit);
2423  //Print("Idelems %i \n----------\n",IDELEMS(I));
2424  //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg));
2425  //int syz_comp=arg_I->rank;
2426  slimgb_alg* c=new slimgb_alg(I, syz_comp,F4_mode);
2427
2428
2429  while(c->pair_top>=0)
2430  {
2431    if(F4_mode)
2432      go_on_F4(c);
2433    else
2434      go_on(c);
2435  }
2436  I=c->S;
2437  delete c;
2438  if (TEST_OPT_REDSB){
2439    ideal erg=kInterRed(I,NULL);
2440    assume(I!=erg);
2441    id_Delete(&I, currRing);
2442    return erg;
2443  }
2444  //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func);
2445  assume(I->rank>=idRankFreeModule(I));
2446  return(I);
2447}
2448void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c){
2449  int i,j;
2450  if (arg_i==arg_j){
2451    return;
2452  }
2453  if (arg_i>arg_j){
2454    i=arg_j;
2455    j=arg_i;
2456  } else {
2457    i=arg_i;
2458    j=arg_j;
2459  }
2460  c->states[j][i]=HASTREP;
2461}
2462
2463static BOOLEAN has_t_rep(const int & arg_i, const  int & arg_j, slimgb_alg* state){
2464  assume(0<=arg_i);
2465  assume(0<=arg_j);
2466  assume(arg_i<state->n);
2467  assume(arg_j<state->n);
2468  if (arg_i==arg_j)
2469  {
2470    return (TRUE);
2471  }
2472  if (arg_i>arg_j)
2473  {
2474    return (state->states[arg_i][arg_j]==HASTREP);
2475  } else
2476  {
2477    return (state->states[arg_j][arg_i]==HASTREP);
2478  }
2479}
2480static int pLcmDeg(poly a, poly b)
2481{
2482  int i;
2483  int n=0;
2484  for (i=pVariables; i; i--)
2485  {
2486    n+=si_max( pGetExp(a,i), pGetExp(b,i));
2487  }
2488  return n;
2489
2490}
2491
2492
2493
2494static void shorten_tails(slimgb_alg* c, poly monom)
2495{
2496  return;
2497// BOOLEAN corr=lenS_correct(c->strat);
2498  for(int i=0;i<c->n;i++)
2499  {
2500    //enter tail
2501
2502    if (c->S->m[i]==NULL) continue;
2503    poly tail=c->S->m[i]->next;
2504    poly prev=c->S->m[i];
2505    BOOLEAN did_something=FALSE;
2506    while((tail!=NULL)&& (pLmCmp(tail, monom)>=0))
2507    {
2508      if (p_LmDivisibleBy(monom,tail,c->r))
2509      {
2510        did_something=TRUE;
2511        prev->next=tail->next;
2512        tail->next=NULL;
2513        p_Delete(& tail,c->r);
2514        tail=prev;
2515        //PrintS("Shortened");
2516        c->lengths[i]--;
2517      }
2518      prev=tail;
2519      tail=tail->next;
2520    }
2521    if (did_something)
2522    {
2523      int new_pos;
2524      wlen_type q;
2525      q=pQuality(c->S->m[i],c,c->lengths[i]);
2526      new_pos=simple_posInS(c->strat,c->S->m[i],c->lengths[i],q);
2527
2528      int old_pos=-1;
2529      //assume new_pos<old_pos
2530      for (int z=0;z<=c->strat->sl;z++)
2531      {
2532        if (c->strat->S[z]==c->S->m[i])
2533        {
2534          old_pos=z;
2535          break;
2536        }
2537      }
2538      if (old_pos== -1)
2539        for (int z=new_pos-1;z>=0;z--)
2540        {
2541          if (c->strat->S[z]==c->S->m[i])
2542          {
2543            old_pos=z;
2544            break;
2545          }
2546        }
2547      assume(old_pos>=0);
2548      assume(new_pos<=old_pos);
2549      assume(pLength(c->strat->S[old_pos])==c->lengths[i]);
2550      c->strat->lenS[old_pos]=c->lengths[i];
2551      if (c->strat->lenSw)
2552        c->strat->lenSw[old_pos]=q;
2553
2554      if (new_pos<old_pos)
2555        move_forward_in_S(old_pos,new_pos,c->strat);
2556
2557      length_one_crit(c,i,c->lengths[i]);
2558    }
2559  }
2560}
2561static sorted_pair_node* pop_pair(slimgb_alg* c){
2562  clean_top_of_pair_list(c);
2563
2564  if(c->pair_top<0) return NULL;
2565  else return (c->apairs[c->pair_top--]);
2566}
2567sorted_pair_node* top_pair(slimgb_alg* c){
2568  super_clean_top_of_pair_list(c);//yeah, I know, it's odd that I use a different proc here
2569
2570  if(c->pair_top<0) return NULL;
2571  else return (c->apairs[c->pair_top]);
2572}
2573sorted_pair_node* quick_pop_pair(slimgb_alg* c){
2574  if(c->pair_top<0) return NULL;
2575  else return (c->apairs[c->pair_top--]);
2576}
2577
2578
2579
2580static void super_clean_top_of_pair_list(slimgb_alg* c){
2581  while((c->pair_top>=0)
2582  && (c->apairs[c->pair_top]->i>=0)
2583  && (good_has_t_rep(c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c)))
2584  {
2585
2586    free_sorted_pair_node(c->apairs[c->pair_top],c->r);
2587    c->pair_top--;
2588
2589  }
2590}
2591void clean_top_of_pair_list(slimgb_alg* c){
2592  while((c->pair_top>=0) && (c->apairs[c->pair_top]->i>=0) && (!state_is(UNCALCULATED,c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))){
2593
2594    free_sorted_pair_node(c->apairs[c->pair_top],c->r);
2595    c->pair_top--;
2596
2597  }
2598}
2599static BOOLEAN state_is(calc_state state, const int & arg_i, const  int & arg_j, slimgb_alg* c){
2600  assume(0<=arg_i);
2601  assume(0<=arg_j);
2602  assume(arg_i<c->n);
2603  assume(arg_j<c->n);
2604  if (arg_i==arg_j)
2605  {
2606    return (TRUE);
2607  }
2608  if (arg_i>arg_j)
2609  {
2610    return (c->states[arg_i][arg_j]==state);
2611  }
2612  else return(c->states[arg_j][arg_i]==state);
2613}
2614
2615
2616void free_sorted_pair_node(sorted_pair_node* s, ring r){
2617  if (s->i>=0)
2618    p_Delete(&s->lcm_of_lm,r);
2619  omfree(s);
2620}
2621static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c){
2622  if (a->deg<b->deg) return TRUE;
2623  if (a->deg>b->deg) return FALSE;
2624
2625
2626  int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm);
2627  if (comp==1) return FALSE;
2628  if (-1==comp) return TRUE;
2629  if (a->expected_length<b->expected_length) return TRUE;
2630  if (a->expected_length>b->expected_length) return FALSE;
2631  if (a->i+a->j<b->i+b->j) return TRUE;
2632   if (a->i+a->j>b->i+b->j) return FALSE;
2633  if (a->i<b->i) return TRUE;
2634  if (a->i>b->i) return FALSE;
2635  return TRUE;
2636}
2637
2638static int tgb_pair_better_gen(const void* ap,const void* bp){
2639
2640  sorted_pair_node* a=*((sorted_pair_node**)ap);
2641  sorted_pair_node* b=*((sorted_pair_node**)bp);
2642  assume((a->i>a->j) || (a->i < 0));
2643  assume((b->i>b->j) || (b->i < 0));
2644  if (a->deg<b->deg) return -1;
2645  if (a->deg>b->deg) return 1;
2646
2647
2648 
2649 int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm);
2650
2651  if (comp==1) return 1;
2652  if (-1==comp) return -1;
2653   if (a->expected_length<b->expected_length) return -1;
2654  if (a->expected_length>b->expected_length) return 1;
2655  if (a->i+a->j<b->i+b->j) return -1;
2656   if (a->i+a->j>b->i+b->j) return 1;
2657  if (a->i<b->i) return -1;
2658   if (a->i>b->i) return 1;
2659  return 0;
2660}
2661
2662
2663static poly gcd_of_terms(poly p, ring r){
2664  int max_g_0=0;
2665  assume(p!=NULL);
2666  int i;
2667  poly m=pOne();
2668  poly t;
2669  for (i=pVariables; i; i--)
2670  {
2671      pSetExp(m,i, pGetExp(p,i));
2672      if (max_g_0==0)
2673  if (pGetExp(m,i)>0)
2674    max_g_0=i;
2675  }
2676
2677  t=p->next;
2678  while (t!=NULL){
2679
2680    if (max_g_0==0) break;
2681    for (i=max_g_0; i; i--)
2682    {
2683      pSetExp(m,i, si_min(pGetExp(t,i),pGetExp(m,i)));
2684      if (max_g_0==i)
2685  if (pGetExp(m,i)==0)
2686    max_g_0=0;
2687      if ((max_g_0==0) && (pGetExp(m,i)>0)){
2688  max_g_0=i;
2689      }
2690    }
2691    t=t->next;
2692  }
2693
2694  if (max_g_0>0)
2695    return m;
2696  pDelete(&m);
2697  return NULL;
2698}
2699static inline BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m)
2700{
2701
2702  if (pGetComp(p1) > 0 || pGetComp(p2) > 0)
2703    return FALSE;
2704  int i = 1;
2705  loop
2706  {
2707    if ((pGetExp(p1, i)-pGetExp(m,i) >0) && (pGetExp(p2, i) -pGetExp(m,i)> 0))   return FALSE;
2708    if (i == pVariables)                                return TRUE;
2709    i++;
2710  }
2711}
2712
2713
2714//for impl reasons may return false if the the normal product criterion matches
2715static inline BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c){
2716  if (c->nc)
2717    return FALSE;
2718  if(gcd1==NULL) return FALSE;
2719        if(gcd2==NULL) return FALSE;
2720        gcd1->next=gcd2; //may ordered incorrect
2721        poly m=gcd_of_terms(gcd1,c->r);
2722        gcd1->next=NULL;
2723        if (m==NULL) return FALSE;
2724
2725        BOOLEAN erg=pHasNotCFExtended(p1,p2,m);
2726        pDelete(&m);
2727        return erg;
2728}
2729static poly kBucketGcd(kBucket* b, ring r)
2730{
2731  int s=0;
2732  int i;
2733  poly m, n;
2734  BOOLEAN initialized=FALSE;
2735  for (i=MAX_BUCKET-1;i>=0;i--)
2736  {
2737    if (b->buckets[i]!=NULL){
2738      if (!initialized){
2739  m=gcd_of_terms(b->buckets[i],r);
2740  initialized=TRUE;
2741  if (m==NULL) return NULL;
2742      }
2743      else
2744  {
2745    n=gcd_of_terms(b->buckets[i],r);
2746    if (n==NULL) {
2747      pDelete(&m);
2748      return NULL;
2749    }
2750    n->next=m;
2751    poly t=gcd_of_terms(n,r);
2752    n->next=NULL;
2753    pDelete(&m);
2754    pDelete(&n);
2755    m=t;
2756    if (m==NULL) return NULL;
2757
2758  }
2759    }
2760  }
2761  return m;
2762}
2763
2764
2765
2766
2767static inline int quality_of_pos_in_strat_S(int pos, slimgb_alg* c){
2768  if (c->strat->lenSw!=NULL) return c->strat->lenSw[pos];
2769  return c->strat->lenS[pos];
2770}
2771static inline int quality_of_pos_in_strat_S_mult_high(int pos, poly high, slimgb_alg* c)
2772  //meant only for nc
2773{
2774  poly m=pOne();
2775  pExpVectorDiff(m,high ,c->strat->S[pos]);
2776  poly product=nc_mm_Mult_p(m, pCopy(c->strat->S[pos]), c->r);
2777  int erg=pQuality(product,c);
2778  pDelete(&m);
2779  pDelete(&product);
2780  return erg;
2781}
2782
2783static void multi_reduction_lls_trick(red_object* los, int losl,slimgb_alg* c,find_erg & erg){
2784  erg.expand=NULL;
2785  BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS
2786  if(erg.fromS){
2787    if(pLmEqual(c->strat->S[erg.reduce_by],los[erg.to_reduce_u].p))
2788    {
2789      int i;
2790      int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c);
2791      int best=erg.to_reduce_u+1;
2792/*
2793      for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){
2794  int qc=los[i].guess_quality(c);
2795  if (qc<quality_a){
2796    best=i;
2797    quality_a=qc;
2798  }
2799      }
2800      if(best!=erg.to_reduce_u+1){*/
2801      int qc;
2802      best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c);
2803      if(qc<quality_a){
2804  los[best].flatten();
2805  int b_pos=kBucketCanonicalize(los[best].bucket);
2806  los[best].p=los[best].bucket->buckets[b_pos];
2807  qc=pQuality(los[best].bucket->buckets[b_pos],c);
2808  if(qc<quality_a){
2809    red_object h=los[erg.to_reduce_u];
2810    los[erg.to_reduce_u]=los[best];
2811    los[best]=h;
2812    swap_roles=TRUE;
2813  }
2814  else
2815    swap_roles=FALSE;
2816      }
2817      else{
2818
2819  swap_roles=FALSE;
2820      }
2821
2822    }
2823      else
2824    {
2825      if (erg.to_reduce_u>erg.to_reduce_l){
2826
2827  int i;
2828  int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c);
2829  if (c->nc)
2830    quality_a=quality_of_pos_in_strat_S_mult_high(erg.reduce_by, los[erg.to_reduce_u].p, c);
2831  int best=erg.to_reduce_u+1;
2832  int qc;
2833  best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c);
2834  assume(qc==los[best].guess_quality(c));
2835  if(qc<quality_a){
2836    los[best].flatten();
2837    int b_pos=kBucketCanonicalize(los[best].bucket);
2838    los[best].p=los[best].bucket->buckets[b_pos];
2839    qc==pQuality(los[best].bucket->buckets[b_pos],c);
2840    //(best!=erg.to_reduce_u+1)
2841    if(qc<quality_a){
2842    red_object h=los[erg.to_reduce_u];
2843    los[erg.to_reduce_u]=los[best];
2844    los[best]=h;
2845    erg.reduce_by=erg.to_reduce_u;
2846    erg.fromS=FALSE;
2847    erg.to_reduce_u--;
2848    }
2849  }
2850      }
2851      else
2852      {
2853  assume(erg.to_reduce_u==erg.to_reduce_l);
2854  wlen_type quality_a=
2855        quality_of_pos_in_strat_S(erg.reduce_by,c);
2856  wlen_type qc=los[erg.to_reduce_u].guess_quality(c);
2857  if (qc<0) PrintS("Wrong wlen_type");
2858  if(qc<quality_a){
2859    int best=erg.to_reduce_u;
2860    los[best].flatten();
2861    int b_pos=kBucketCanonicalize(los[best].bucket);
2862    los[best].p=los[best].bucket->buckets[b_pos];
2863    qc=pQuality(los[best].bucket->buckets[b_pos],c);
2864    assume(qc>=0);
2865    if(qc<quality_a){
2866      BOOLEAN exp=FALSE;
2867      if(qc<=2){
2868         //Print("\n qc is %lld \n",qc);
2869         exp=TRUE;
2870      }
2871
2872      else {
2873         if (qc<quality_a/2)
2874          exp=TRUE;
2875         else
2876       if(erg.reduce_by<c->n/4)
2877          exp=TRUE;
2878      }
2879      if (exp){
2880        poly clear_into;
2881        los[erg.to_reduce_u].flatten();
2882        kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length);
2883        erg.expand=pCopy(clear_into);
2884        kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length);
2885        if (TEST_OPT_PROT)
2886    PrintS("e");
2887
2888      }
2889    }
2890  }
2891
2892
2893      }
2894
2895      swap_roles=FALSE;
2896      return;
2897      }
2898
2899  }
2900  else{
2901    if(erg.reduce_by>erg.to_reduce_u){
2902      //then lm(rb)>= lm(tru) so =
2903      assume(erg.reduce_by==erg.to_reduce_u+1);
2904      int best=erg.reduce_by;
2905      wlen_type quality_a=los[erg.reduce_by].guess_quality(c);
2906      int qc;
2907      best=find_best(los,erg.to_reduce_l,erg.to_reduce_u,qc,c);
2908
2909      int i;
2910      if(qc<quality_a){
2911    red_object h=los[erg.reduce_by];
2912    los[erg.reduce_by]=los[best];
2913    los[best]=h;
2914  }
2915  swap_roles=FALSE;
2916  return;
2917
2918
2919    }
2920    else
2921    {
2922      assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p));
2923      assume(erg.to_reduce_u==erg.to_reduce_l);
2924      //further assume, that reduce_by is the above all other polys
2925      //with same leading term
2926      int il=erg.reduce_by;
2927      int quality_a =los[erg.reduce_by].guess_quality(c);
2928      int qc;
2929      while((il>0) && pLmEqual(los[il-1].p,los[il].p)){
2930  il--;
2931  qc=los[il].guess_quality(c);
2932  if (qc<quality_a){
2933    quality_a=qc;
2934    erg.reduce_by=il;
2935  }
2936      }
2937      swap_roles=FALSE;
2938    }
2939
2940  }
2941  if(swap_roles)
2942  {
2943    if (TEST_OPT_PROT)
2944      PrintS("b");
2945    poly clear_into;
2946    int dummy_len;
2947    int new_length;
2948    int bp=erg.to_reduce_u;//bucket_positon
2949    //kBucketClear(los[bp].bucket,&clear_into,&new_length);
2950    new_length=los[bp].clear_to_poly();
2951    clear_into=los[bp].p;
2952    poly p=c->strat->S[erg.reduce_by];
2953    int j=erg.reduce_by;
2954    int old_length=c->strat->lenS[j];// in view of S
2955    los[bp].p=p;
2956    kBucketInit(los[bp].bucket,p,old_length);
2957    wlen_type qal=pQuality(clear_into,c,new_length);
2958    int pos_in_c=-1;
2959    int z;
2960    int new_pos;
2961    new_pos=simple_posInS(c->strat,clear_into,new_length, qal);
2962    assume(new_pos<=j);
2963    for (z=c->n;z;z--)
2964    {
2965      if(p==c->S->m[z-1])
2966      {
2967  pos_in_c=z-1;
2968  break;
2969      }
2970    }
2971    if(pos_in_c>=0)
2972    {
2973      #ifdef TGB_RESORT_PAIRS
2974      c->used_b=TRUE;
2975      c->replaced[pos_in_c]=TRUE;
2976      #endif
2977      c->S->m[pos_in_c]=clear_into;
2978      c->lengths[pos_in_c]=new_length;
2979      c->weighted_lengths[pos_in_c]=qal;
2980      if (c->gcd_of_terms[pos_in_c]==NULL)
2981        c->gcd_of_terms[pos_in_c]=gcd_of_terms(clear_into,c->r);
2982      if (c->T_deg_full)
2983  c->T_deg_full[pos_in_c]=pTotaldegree_full(clear_into);
2984      c_S_element_changed_hook(pos_in_c,c);
2985    }
2986    c->strat->S[j]=clear_into;
2987    c->strat->lenS[j]=new_length;
2988
2989    assume(pLength(clear_into)==new_length);
2990    if(c->strat->lenSw!=NULL)
2991      c->strat->lenSw[j]=qal;
2992    if (!rField_is_Zp(c->r))
2993    {
2994      pContent(clear_into);
2995      pCleardenom(clear_into);//should be unnecessary
2996    }
2997    else
2998      pNorm(clear_into);
2999#ifdef FIND_DETERMINISTIC
3000    erg.reduce_by=j;
3001    //resort later see diploma thesis, find_in_S must be deterministic
3002    //during multireduction if spolys are only in the span of the
3003    //input polys
3004#else
3005
3006    if (new_pos<j)
3007    {
3008      move_forward_in_S(j,new_pos,c->strat);
3009      erg.reduce_by=new_pos;
3010    }
3011#endif
3012  }
3013}
3014static int fwbw(red_object* los, int i){
3015   int i2=i;
3016   int step=1;
3017
3018   BOOLEAN bw=FALSE;
3019   BOOLEAN incr=TRUE;
3020
3021   while(1)
3022   {
3023     if(!bw)
3024     {
3025       step=si_min(i2,step);
3026       if (step==0) break;
3027       i2-=step;
3028
3029       if(!pLmEqual(los[i].p,los[i2].p))
3030       {
3031   bw=TRUE;
3032   incr=FALSE;
3033       }
3034       else
3035       {
3036   if ((!incr) &&(step==1)) break;
3037       }
3038
3039
3040     }
3041     else
3042     {
3043
3044       step=si_min(i-i2,step);
3045       if (step==0) break;
3046       i2+=step;
3047       if(pLmEqual(los[i].p,los[i2].p)){
3048   if(step==1) break;
3049   else
3050   {
3051     bw=FALSE;
3052   }
3053       }
3054
3055     }
3056     if (incr)
3057       step*=2;
3058     else
3059     {
3060       if (step%2==1)
3061   step=(step+1)/2;
3062       else
3063   step/=2;
3064
3065     }
3066   }
3067   return i2;
3068}
3069static void canonicalize_region(red_object* los, int l, int u,slimgb_alg* c){
3070    assume(l<=u+1);
3071    int i;
3072    for(i=l;i<=u;i++){
3073        kBucketCanonicalize(los[i].bucket);
3074    }
3075
3076}
3077static void multi_reduction_find(red_object* los, int losl,slimgb_alg* c,int startf,find_erg & erg){
3078  kStrategy strat=c->strat;
3079
3080  assume(startf<=losl);
3081  assume((startf==losl-1)||(pLmCmp(los[startf].p,los[startf+1].p)==-1));
3082  int i=startf;
3083
3084  int j;
3085  while(i>=0){
3086    assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)<=0));
3087    assume(is_valid_ro(los[i]));
3088    j=kFindDivisibleByInS_easy(strat,los[i]);
3089    if(j>=0){
3090
3091      erg.to_reduce_u=i;
3092      erg.reduce_by=j;
3093      erg.fromS=TRUE;
3094      int i2=fwbw(los,i);
3095      assume(pLmEqual(los[i].p,los[i2].p));
3096      assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p)));
3097      assume(i>=i2);
3098
3099
3100      erg.to_reduce_l=i2;
3101      assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1));
3102      canonicalize_region(los,erg.to_reduce_u+1,startf,c);
3103      return;
3104    }
3105    if (j<0){
3106
3107      //not reduceable, try to use this for reducing higher terms
3108      int i2=fwbw(los,i);
3109      assume(pLmEqual(los[i].p,los[i2].p));
3110      assume((i2==0)||(!pLmEqual(los[i2].p,los[i2-1].p)));
3111      assume(i>=i2);
3112      if(i2!=i){
3113
3114
3115  erg.to_reduce_u=i-1;
3116  erg.to_reduce_l=i2;
3117  erg.reduce_by=i;
3118  erg.fromS=FALSE;
3119  assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1));
3120  canonicalize_region(los,erg.to_reduce_u+1,startf,c);
3121  return;
3122      }
3123
3124      i--;
3125    }
3126  }
3127  erg.reduce_by=-1;//error code
3128  return;
3129}
3130
3131 //  nicht reduzierbare eintraege in ergebnisliste schreiben
3132//   nullen loeschen
3133//   while(finde_groessten leitterm reduzierbar(c,erg)){
3134
3135static int multi_reduction_clear_zeroes(red_object* los, int  losl, int l, int u)
3136{
3137
3138
3139  int deleted=0;
3140  int  i=l;
3141  int last=-1;
3142  while(i<=u)
3143  {
3144
3145    if(los[i].p==NULL){
3146      kBucketDestroy(&los[i].bucket);
3147//      delete los[i];//here we assume los are constructed with new
3148      //destroy resources, must be added here
3149     if (last>=0)
3150     {
3151       memmove(los+(int)(last+1-deleted),los+(last+1),sizeof(red_object)*(i-1-last));
3152     }
3153     last=i;
3154     deleted++;
3155    }
3156    i++;
3157  }
3158  if((last>=0)&&(last!=losl-1))
3159      memmove(los+(int)(last+1-deleted),los+last+1,sizeof(red_object)*(losl-1-last));
3160  return deleted;
3161
3162}
3163
3164static void sort_region_down(red_object* los, int l, int u, slimgb_alg* c)
3165{
3166  qsort(los+l,u-l+1,sizeof(red_object),red_object_better_gen);
3167  int i;
3168
3169  for(i=l;i<=u;i++)
3170  {
3171    BOOLEAN moved=FALSE;
3172    int j;
3173    for(j=i;j;j--)
3174    {
3175      if(pLmCmp(los[j].p,los[j-1].p)==-1){
3176  red_object h=los[j];
3177  los[j]=los[j-1];
3178  los[j-1]=h;
3179  moved=TRUE;
3180      }
3181      else break;
3182    }
3183    if(!moved) return;
3184  }
3185}
3186
3187//assume that los is ordered ascending by leading term, all non zero
3188static void multi_reduction(red_object* los, int & losl, slimgb_alg* c)
3189{
3190  poly* delay=(poly*) omalloc(losl*sizeof(poly));
3191  int delay_s=0;
3192  //initialize;
3193  assume(c->strat->sl>=0);
3194  assume(losl>0);
3195  int i;
3196  wlen_type max_initial_quality=0;
3197
3198  for(i=0;i<losl;i++){
3199    los[i].sev=pGetShortExpVector(los[i].p);
3200//SetShortExpVector();
3201    los[i].p=kBucketGetLm(los[i].bucket);
3202    if (los[i].initial_quality>max_initial_quality)
3203        max_initial_quality=los[i].initial_quality;
3204    // else
3205//         Print("init2_qal=%lld;", los[i].initial_quality);
3206//     Print("initial_quality=%lld;",max_initial_quality);
3207  }
3208
3209  kStrategy strat=c->strat;
3210  int curr_pos=losl-1;
3211
3212
3213//  nicht reduzierbare einträge in ergebnisliste schreiben
3214  // nullen loeschen
3215  while(curr_pos>=0){
3216
3217    find_erg erg;
3218    multi_reduction_find(los, losl,c,curr_pos,erg);//last argument should be curr_pos
3219    if(erg.reduce_by<0) break;
3220
3221
3222
3223    erg.expand=NULL;
3224    int d=erg.to_reduce_u-erg.to_reduce_l+1;
3225
3226
3227    multi_reduction_lls_trick(los,losl,c,erg);
3228
3229
3230    int i;
3231    int len;
3232    //    wrp(los[erg.to_reduce_u].p);
3233    //Print("\n");
3234    multi_reduce_step(erg,los,c);
3235
3236
3237    if(!K_TEST_OPT_REDTHROUGH){
3238  for(i=erg.to_reduce_l;i<=erg.to_reduce_u;i++){
3239     if  (los[i].p!=NULL)  //the check (los[i].p!=NULL) might be invalid
3240     {
3241         //
3242         assume(los[i].initial_quality>0);
3243
3244               if(los[i].guess_quality(c)
3245                  >1.5*delay_factor*max_initial_quality){
3246                       if (TEST_OPT_PROT)
3247                           PrintS("v");
3248                       los[i].canonicalize();
3249                       if(los[i].guess_quality(c)
3250                           >delay_factor*max_initial_quality){
3251                               if (TEST_OPT_PROT)
3252                                   PrintS(".");
3253                               los[i].clear_to_poly();
3254                               //delay.push_back(los[i].p);
3255                               delay[delay_s]=los[i].p;
3256                               delay_s++;
3257
3258                               los[i].p=NULL;
3259
3260                      }
3261                  }
3262
3263            }
3264     }
3265  }
3266    int deleted=multi_reduction_clear_zeroes(los, losl, erg.to_reduce_l, erg.to_reduce_u);
3267    if(erg.fromS==FALSE)
3268      curr_pos=si_max(erg.to_reduce_u,erg.reduce_by);
3269    else
3270      curr_pos=erg.to_reduce_u;
3271    losl -= deleted;
3272    curr_pos -= deleted;
3273
3274    //Print("deleted %i \n",deleted);
3275    if ((TEST_V_UPTORADICAL) &&(!(erg.fromS)))
3276        sort_region_down(los,si_min(erg.to_reduce_l,erg.reduce_by),(si_max(erg.to_reduce_u,erg.reduce_by))-deleted,c);
3277    else
3278    sort_region_down(los, erg.to_reduce_l, erg.to_reduce_u-deleted, c);
3279
3280
3281    if(erg.expand)
3282    {
3283#ifdef FIND_DETERMINISTIC
3284      int i;
3285      for(i=0;c->expandS[i];i++);
3286      c->expandS=(poly*) omrealloc(c->expandS,(i+2)*sizeof(poly));
3287      c->expandS[i]=erg.expand;
3288      c->expandS[i+1]=NULL;
3289#else
3290      add_to_reductors(c,erg.expand,erg.expand_length);
3291#endif
3292    }
3293
3294  }
3295
3296
3297  sorted_pair_node** pairs=(sorted_pair_node**)
3298    omalloc(delay_s*sizeof(sorted_pair_node*));
3299  for(i=0;i<delay_s;i++){
3300
3301      poly p=delay[i];
3302      //if (rPar(c->r)==0)
3303      simplify_poly(p,c->r);
3304      sorted_pair_node* si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
3305      si->i=-1;
3306      si->j=-1;
3307       if (!rField_is_Zp(c->r)){
3308        if (!c->nc)
3309            p=redTailShort(p, c->strat);
3310        pCleardenom(p);
3311        pContent(p);
3312      }
3313      si->expected_length=pQuality(p,c,pLength(p));
3314      si->deg=pTotaldegree(p);
3315
3316      si->lcm_of_lm=p;
3317      pairs[i]=si;
3318  }
3319  qsort(pairs,delay_s,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
3320  c->apairs=spn_merge(c->apairs,c->pair_top+1,pairs,delay_s,c);
3321  c->pair_top+=delay_s;
3322  omfree(delay);
3323  return;
3324}
3325void red_object::flatten(){
3326  assume(p==kBucketGetLm(bucket));
3327}
3328void red_object::validate(){
3329  p=kBucketGetLm(bucket);
3330  if(p)
3331    sev=pGetShortExpVector(p);
3332}
3333int red_object::clear_to_poly(){
3334  flatten();
3335  int l;
3336  kBucketClear(bucket,&p,&l);
3337  return l;
3338}
3339
3340
3341
3342
3343
3344void reduction_step::reduce(red_object* r, int l, int u){}
3345void simple_reducer::do_reduce(red_object & ro){
3346  number coef;
3347  if (!c->nc)
3348    coef=kBucketPolyRed(ro.bucket,p,
3349       p_len,
3350       c->strat->kNoether);
3351  else
3352    nc_kBucketPolyRed_Z(ro.bucket, p, &coef);
3353  nDelete(&coef);
3354}
3355
3356
3357void simple_reducer::reduce(red_object* r, int l, int u){
3358  this->pre_reduce(r,l,u);
3359  int i;
3360//debug start
3361  int im;
3362
3363
3364  for(i=l;i<=u;i++){
3365
3366
3367
3368    this->do_reduce(r[i]);
3369
3370  }
3371  for(i=l;i<=u;i++){
3372
3373    kBucketSimpleContent(r[i].bucket);
3374    r[i].validate();
3375    #ifdef TGB_DEBUG
3376    #endif
3377  }
3378}
3379reduction_step::~reduction_step(){}
3380simple_reducer::~simple_reducer(){
3381  if(fill_back!=NULL)
3382  {
3383    kBucketInit(fill_back,p,p_len);
3384  }
3385  fill_back=NULL;
3386
3387}
3388
3389void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c){
3390  static int id=0;
3391  id++;
3392  unsigned long sev;
3393    BOOLEAN lt_changed=FALSE;
3394  int rn=erg.reduce_by;
3395  poly red;
3396  int red_len;
3397  simple_reducer* pointer;
3398  BOOLEAN work_on_copy=FALSE;
3399  if(erg.fromS){
3400    red=c->strat->S[rn];
3401    red_len=c->strat->lenS[rn];
3402    assume(red_len==pLength(red));
3403  }
3404  else
3405  {
3406    r[rn].flatten();
3407    kBucketClear(r[rn].bucket,&red,&red_len);
3408
3409    if (!rField_is_Zp(c->r))
3410    {
3411      pContent(red);
3412      pCleardenom(red);//should be unnecessary
3413
3414    }
3415    pNormalize(red);
3416
3417
3418    if ((!(erg.fromS))&&(TEST_V_UPTORADICAL)){
3419
3420         if (polynomial_root(red,c->r))
3421            lt_changed=TRUE;
3422            sev=p_GetShortExpVector(red,c->r);}
3423    red_len=pLength(red);
3424  }
3425  if (((TEST_V_MODPSOLVSB)&&(red_len>1))||((c->nc)||(erg.to_reduce_u-erg.to_reduce_l>5))){
3426    work_on_copy=TRUE;
3427    // poly m=pOne();
3428    poly m=c->tmp_lm;
3429    pSetCoeff(m,nInit(1));
3430    for(int i=1;i<=pVariables;i++)
3431      pSetExp(m,i,(pGetExp(r[erg.to_reduce_l].p, i)-pGetExp(red,i)));
3432    pSetm(m);
3433    poly red_cp;
3434    if (!c->nc)
3435      red_cp=ppMult_mm(red,m);
3436    else
3437      red_cp=nc_mm_Mult_p(m, pCopy(red), c->r);
3438    if(!erg.fromS){
3439      kBucketInit(r[rn].bucket,red,red_len);
3440    }
3441    //now reduce the copy
3442    //static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n)
3443
3444    if (!c->nc)
3445      redTailShort(red_cp,c->strat);
3446    //number mul;
3447    // red_len--;
3448//     red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length);
3449//     pSetCoeff(red_cp,nMult(red_cp->coef,mul));
3450//     nDelete(&mul);
3451//     red_len++;
3452    red=red_cp;
3453    red_len=pLength(red);
3454    // pDelete(&m);
3455
3456  }
3457  int i;
3458
3459
3460
3461  assume(red_len==pLength(red));
3462
3463  pointer=new simple_reducer(red,red_len,c);
3464
3465  if ((!work_on_copy) && (!erg.fromS))
3466    pointer->fill_back=r[rn].bucket;
3467  else
3468    pointer->fill_back=NULL;
3469  pointer->reduction_id=id;
3470  pointer->c=c;
3471
3472  pointer->reduce(r,erg.to_reduce_l, erg.to_reduce_u);
3473  if(work_on_copy) pDelete(&pointer->p);
3474  delete pointer;
3475  if (lt_changed){
3476    assume(!erg.fromS);
3477    r[erg.reduce_by].sev=sev;
3478  }
3479
3480};
3481
3482
3483
3484
3485void simple_reducer:: pre_reduce(red_object* r, int l, int u){}
3486
Note: See TracBrowser for help on using the repository browser.