source: git/kernel/tgb.cc @ 8f4e3f

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