source: git/kernel/tgb.cc @ b3789a

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