source: git/Singular/tgb.cc @ f6f96e

spielwiese
Last change on this file since f6f96e was f6f96e, checked in by Michael Brickenstein <bricken@…>, 21 years ago
not much git-svn-id: file:///usr/local/Singular/svn/trunk@6536 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 52.9 KB
Line 
1
2// #define OM_CHECK 3
3// #define OM_TRACK 5
4// #define OM_KEEP  1
5// TODO:
6//       deg -> poly_crit
7//       "e"
8//       multiple rings
9//       shorten_tails und dessen Aufrufe pruefen wlength!!!
10#include "tgb.h"
11#define OM_KEEP 0
12#define LEN_VAR1
13
14#ifdef LEN_VAR1
15// erste Variante: Laenge: Anzahl der Monome
16int pSLength(poly p, int l) {
17  return l; }
18int kSBucketLength(kBucket* bucket) {return bucket_guess(bucket);}
19#endif
20
21#ifdef LEN_VAR2
22// 2. Variante: Laenge: Platz fuer die Koeff.
23int pSLength(poly p,int l)
24{
25  int s=0;
26  while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); }
27  return s;
28}
29int kSBucketLength(kBucket* b)
30{
31  int s=0;
32  int i;
33  for (i=MAX_BUCKET;i>=0;i--)
34  {
35    s+=pSLength(b->buckets[i],0);
36  }
37  return s;
38}
39#endif
40
41#ifdef LEN_VAR3
42// 3.Variante: Laenge: Platz fuer Leitk * Monomanzahl
43int pSLength(poly p,int l)
44{
45  int c=nSize(pGetCoeff(p));
46  return c*l /*pLength(p)*/;
47}
48int kSBucketLength(kBucket* b)
49{
50  int s=0;
51  int c=nSize(pGetCoeff(kBucketGetLm(b)))+1;
52  int i;
53  for (i=MAX_BUCKET;i>0;i--)
54  {
55    s+=b->buckets_length[i] /*pLength(b->buckets[i])*/;
56  }
57  return s*c;
58}
59#endif
60
61#ifdef LEN_VAR4
62// 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.)
63int pSLength(poly p, int l)
64{
65  int s=1;
66  int c=nSize(pGetCoeff(p));
67  pIter(p);
68  while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); }
69  return s*c;
70}
71int kSBucketLength(kBucket* b)
72{
73  int s=1;
74  int c=nSize(pGetCoeff(kBucketGetLm(b)));
75  int i;
76  for (i=MAX_BUCKET;i>0;i--)
77  {
78    if(b->buckets[i]==NULL) continue;
79    s+=pSLength(b->buckets[i],0);
80  }
81  return s*c;
82}
83#endif
84
85static int LObject_better_gen(const void* ap, const void* bp)
86{
87  LObject* a=*(LObject**)ap;
88  LObject* b=*(LObject**)bp;
89  return(pLmCmp(a->p,b->p));
90}
91static int red_object_better_gen(const void* ap, const void* bp)
92{
93
94
95  return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p));
96}
97static int pair_better_gen2(const void* ap,const void* bp){
98  return(-pair_better_gen(ap,bp));
99}
100static int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj){
101  int i;
102  long not_sev=~obj.sev;
103  poly p=obj.p;
104  for(i=0;i<=strat->sl;i++){
105    if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev))
106      return i;
107  }
108  return -1;
109}
110static int posInPairs (sorted_pair_node**  p, int pn, sorted_pair_node* qe,calc_dat* c,int an=0)
111{
112  if(pn==0) return 0;
113
114  int length=pn-1;
115  int i;
116  //int an = 0;
117  int en= length;
118
119  if (pair_better(qe,p[en],c))
120    return length+1;
121
122  while(1)
123    {
124      //if (an >= en-1)
125      if(en-1<=an)
126      {
127        if (pair_better(p[an],qe,c)) return an;
128        return en;
129      }
130      i=(an+en) / 2;
131        if (pair_better(p[i],qe,c))
132          en=i;
133      else an=i;
134    }
135}
136static BOOLEAN  ascending(int* i,int top){
137  if(top<1) return TRUE;
138  if(i[top]<i[top-1]) return FALSE;
139  return ascending(i,top-1);
140}
141
142sorted_pair_node**  merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,calc_dat* c){
143  int i;
144  int* a= (int*) omalloc(qn*sizeof(int));
145//   int mc;
146//   PrintS("Debug\n");
147//   for(mc=0;mc<qn;mc++)
148// {
149
150//     wrp(q[mc]->lcm_of_lm);
151//     PrintS("\n");
152// }
153//    PrintS("Debug they are in\n");
154//   for(mc=0;mc<pn;mc++)
155// {
156
157//     wrp(p[mc]->lcm_of_lm);
158//     PrintS("\n");
159// }
160  int lastpos=0;
161  for(i=0;i<qn;i++){
162    lastpos=posInPairs(p,pn,q[i],c, max(lastpos-1,0));
163    //   cout<<lastpos<<"\n";
164    a[i]=lastpos;
165
166  }
167  if((pn+qn)>c->max_pairs){
168    p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*));
169    c->max_pairs=2*(pn+qn);
170  }
171  for(i=qn-1;i>=0;i--){
172    size_t size;
173    if(qn-1>i)
174      size=(a[i+1]-a[i])*sizeof(sorted_pair_node*);
175    else
176      size=(pn-a[i])*sizeof(sorted_pair_node*); //as indices begin with 0
177    memmove (p+a[i]+(1+i), p+a[i], size);
178    p[a[i]+i]=q[i];
179  }
180  omfree(a);
181  return p;
182}
183
184
185static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,calc_dat* c){
186
187
188  poly p1=c->S->m[pos1];
189  poly p2=c->S->m[pos2];
190  ring r=c->r;
191 
192
193  if (pGetComp(p1) > 0 || pGetComp(p2) > 0)
194    return FALSE;
195  int i = 1;
196  poly m=NULL;
197  poly gcd1=c->gcd_of_terms[pos1];
198  poly gcd2=c->gcd_of_terms[pos2];
199 
200  if((gcd1!=NULL) && (gcd2!=NULL)) 
201    {
202      gcd1->next=gcd2; //may ordered incorrect
203      poly m=gcd_of_terms(gcd1,c->r);
204      gcd1->next=NULL;
205     
206    } 
207
208  if (m==NULL) 
209  {
210     loop
211      {
212        if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i))   return FALSE;
213        if (i == pVariables){
214          PrintS("trivial");
215          return TRUE;
216        }
217        i++;
218      }
219  }
220  else 
221  {
222    loop
223      {
224        if (pGetExp(p1, i)-pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i))   return FALSE;
225        if (i == pVariables){
226          pDelete(&m);
227          PrintS("trivial");
228          return TRUE;
229        }
230        i++;
231      }
232  }
233
234 
235
236 
237}
238
239BOOLEAN good_has_t_rep(int i, int j,calc_dat* c){
240  assume(i>=0);
241    assume(j>=0);
242  if (has_t_rep(i,j,c)) return TRUE;
243  poly lm=pOne();
244
245  pLcm(c->S->m[i], c->S->m[j], lm);
246  pSetm(lm);
247  assume(lm!=NULL);
248  int deciding_deg= pTotaldegree(lm);
249  int* i_con =make_connections(i,j,lm,c);
250  p_Delete(&lm,c->r);
251
252
253  for (int n=0;((n<c->n) && (i_con[n]>=0));n++){
254    if (i_con[n]==j){
255      now_t_rep(i,j,c);
256      omfree(i_con);
257
258      return TRUE;
259    }
260  }
261  omfree(i_con);
262
263  return FALSE;
264}
265BOOLEAN lenS_correct(kStrategy strat){
266  int i;
267  for(i=0;i<=strat->sl;i++){
268    if (strat->lenS[i]!=pLength(strat->S[i]))
269      return FALSE;
270  }
271  return TRUE;
272}
273
274static void notice_miss(int i, int j, calc_dat* c){
275  PrintS("-");
276 
277}
278
279static void cleanS(kStrategy strat){
280  int i=0;
281  LObject P;
282  while(i<=strat->sl){
283    P.p=strat->S[i];
284    P.sev=strat->sevS[i];
285    if(kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P)!=i){
286      deleteInS(i,strat);
287      //remember destroying poly
288    }
289    else i++;
290  }
291}
292static int bucket_guess(kBucket* bucket){
293  int sum=0;
294  int i;
295  for (i=MAX_BUCKET;i>=0;i--){
296    sum+=bucket->buckets_length[i];
297  }
298  return sum;
299}
300
301
302
303
304
305
306static int add_to_reductors(calc_dat* c, poly h, int len){
307  assume(lenS_correct(c->strat));
308 
309  int i;
310  if (c->is_char0)
311       i=simple_posInS(c->strat,h,pSLength(h,len),c->is_char0);
312  else
313    i=simple_posInS(c->strat,h,len,c->is_char0);
314 
315  LObject P; memset(&P,0,sizeof(P));
316  P.tailRing=c->r;
317  P.p=h; /*p_Copy(h,c->r);*/
318  P.FDeg=pFDeg(P.p,c->r);
319  if (!rField_is_Zp(c->r)){ 
320    pCleardenom(P.p);
321    pContent(P.p); //is a duplicate call, but belongs here
322  }
323 
324  else                     
325    pNorm(P.p);
326 
327 
328  c->strat->enterS(P,i,c->strat);
329 
330 
331
332  c->strat->lenS[i]=len;
333 
334  if(c->strat->lenSw)
335    c->strat->lenSw[i]=pSLength(P.p,len);
336  return i;
337 
338}
339static void length_one_crit(calc_dat* c, int pos, int len)
340{
341  if (len==1)
342  {
343    int i;
344    for ( i=0;i<pos;i++)
345    {
346      if (c->lengths[i]==1)
347        c->states[pos][i]=HASTREP;
348    }
349    for ( i=pos+1;i<c->n;i++){
350      if (c->lengths[i]==1)
351        c->states[i][pos]=HASTREP;
352    }
353    shorten_tails(c,c->S->m[pos]);
354  }
355}
356static sorted_pair_node* find_next_pair2(calc_dat* c, BOOLEAN go_higher){
357  clean_top_of_pair_list(c);
358  sorted_pair_node* s=pop_pair(c);
359
360
361  return s;
362}
363
364static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat, BOOLEAN is_char0)
365{
366  assume(old_pos>=new_pos);
367  poly p=strat->S[old_pos];
368  int ecart=strat->ecartS[old_pos];
369  long sev=strat->sevS[old_pos];
370  int s_2_r=strat->S_2_R[old_pos];
371  int length=strat->lenS[old_pos];
372  int length_w;
373  if(is_char0)
374    length_w=strat->lenSw[old_pos];
375  int i;
376  for (i=old_pos; i>new_pos; i--)
377  {
378    strat->S[i] = strat->S[i-1];
379    strat->ecartS[i] = strat->ecartS[i-1];
380    strat->sevS[i] = strat->sevS[i-1];
381    strat->S_2_R[i] = strat->S_2_R[i-1];
382  }
383  if (strat->lenS!=NULL)
384    for (i=old_pos; i>new_pos; i--)
385      strat->lenS[i] = strat->lenS[i-1];
386  if (strat->lenSw!=NULL)
387    for (i=old_pos; i>new_pos; i--)
388      strat->lenSw[i] = strat->lenSw[i-1];
389
390  strat->S[new_pos]=p;
391  strat->ecartS[new_pos]=ecart;
392  strat->sevS[new_pos]=sev;
393  strat->S_2_R[new_pos]=s_2_r;
394  strat->lenS[new_pos]=length;
395  if(is_char0)
396    strat->lenSw[new_pos]=length_w;
397  //assume(lenS_correct(strat));
398}
399static void replace_pair(int & i, int & j, calc_dat* c)
400{
401  c->soon_free=NULL;
402  int curr_deg;
403  poly lm=pOne();
404
405  pLcm(c->S->m[i], c->S->m[j], lm);
406  pSetm(lm);
407  int deciding_deg= pTotaldegree(lm);
408  int* i_con =make_connections(i,j,lm,c);
409  int z=0;
410
411  for (int n=0;((n<c->n) && (i_con[n]>=0));n++){
412    if (i_con[n]==j){
413      now_t_rep(i,j,c);
414      omfree(i_con);
415      p_Delete(&lm,c->r);
416      return;
417    }
418  }
419
420  int* j_con =make_connections(j,lm,c);
421  i= i_con[0];
422  j=j_con[0];
423  if(c->n>1){
424    if (i_con[1]>=0)
425      i=i_con[1];
426    else {
427      if (j_con[1]>=0)
428        j=j_con[1];
429    }
430  }
431  pLcm(c->S->m[i], c->S->m[j], lm);
432  pSetm(lm);
433  poly short_s;
434  curr_deg=pTotaldegree(lm);
435  int_pair_node* last=NULL;
436
437  for (int n=0;((n<c->n) && (j_con[n]>=0));n++){
438    for (int m=0;((m<c->n) && (i_con[m]>=0));m++){
439      pLcm(c->S->m[i_con[m]], c->S->m[j_con[n]], lm);
440      pSetm(lm);
441      if (pTotaldegree(lm)>=deciding_deg)
442      {
443        soon_t_rep(i_con[m],j_con[n],c);
444        int_pair_node* h= (int_pair_node*)omalloc(sizeof(int_pair_node));
445        if (last!=NULL)
446          last->next=h;
447        else
448          c->soon_free=h;
449        h->next=NULL;
450        h->a=i_con[m];
451        h->b=j_con[n];
452        last=h;
453      }
454      //      if ((comp_deg<curr_deg)
455      //  ||
456      //  ((comp_deg==curr_deg) &&
457      short_s=ksCreateShortSpoly(c->S->m[i_con[m]],c->S->m[j_con[n]],c->r);
458      if (short_s==NULL) {
459        i=i_con[m];
460        j=j_con[n];
461        now_t_rep(i_con[m],j_con[n],c);
462        p_Delete(&lm,c->r);
463        omfree(i_con);
464        omfree(j_con);
465
466        return;
467      }
468#ifdef QUICK_SPOLY_TEST
469      for (int dz=0;dz<=c->n;dz++){
470        if (dz==c->n) {
471          //have found not head reducing pair
472          i=i_con[m];
473          j=j_con[n];
474          p_Delete(&short_s,c->r);
475          p_Delete(&lm,c->r);
476          omfree(i_con);
477          omfree(j_con);
478
479          return;
480        }
481        if (p_LmDivisibleBy(c->S->m[dz],short_s,c->r)) break;
482      }
483#endif
484      int comp_deg(pTotaldegree(short_s));
485      p_Delete(&short_s,c->r);
486      if ((comp_deg<curr_deg))
487         
488      {
489        curr_deg=comp_deg;
490        i=i_con[m];
491        j=j_con[n];
492      }
493    }
494  }
495  p_Delete(&lm,c->r);
496  omfree(i_con);
497  omfree(j_con);
498  return;
499}
500
501
502static int* make_connections(int from, poly bound, calc_dat* c)
503{
504  ideal I=c->S;
505  int s=pTotaldegree(bound);
506  int* cans=(int*) omalloc(c->n*sizeof(int));
507  int* connected=(int*) omalloc(c->n*sizeof(int));
508  int cans_length=0;
509  connected[0]=from;
510  int connected_length=1;
511  long neg_bounds_short= ~p_GetShortExpVector(bound,c->r);
512  for (int i=0;i<c->n;i++){
513    if (c->T_deg[i]>s) continue;
514    if (i!=from){
515      if(p_LmShortDivisibleBy(I->m[i],c->short_Exps[i],bound,neg_bounds_short,c->r)){
516        cans[cans_length]=i;
517        cans_length++;
518      }
519    }
520  }
521  int not_yet_found=cans_length;
522  int con_checked=0;
523  int pos;
524  while((not_yet_found>0) && (con_checked<connected_length)){
525    pos=connected[con_checked];
526    for(int i=0;i<cans_length;i++){
527      if (cans[i]<0) continue;
528      if (has_t_rep(pos,cans[i],c))
529      {
530        connected[connected_length]=cans[i];
531        connected_length++;
532        cans[i]=-1;
533        --not_yet_found;
534      }
535    }
536    con_checked++;
537  }
538  if (connected_length<c->n){
539    connected[connected_length]=-1;
540  }
541  omfree(cans);
542  return connected;
543}
544static int* make_connections(int from, int to, poly bound, calc_dat* c)
545{
546  ideal I=c->S;
547  int s=pTotaldegree(bound);
548  int* cans=(int*) omalloc(c->n*sizeof(int));
549  int* connected=(int*) omalloc(c->n*sizeof(int));
550  cans[0]=to;
551  int cans_length=1;
552  connected[0]=from;
553  int last_cans_pos=-1;
554  int connected_length=1;
555  long neg_bounds_short= ~p_GetShortExpVector(bound,c->r);
556
557  int not_yet_found=cans_length;
558  int con_checked=0;
559  int pos;
560  BOOLEAN can_find_more=TRUE;
561  while(((not_yet_found>0) && (con_checked<connected_length))||can_find_more){
562    if ((con_checked<connected_length)&& (not_yet_found>0)){
563      pos=connected[con_checked];
564      for(int i=0;i<cans_length;i++){
565        if (cans[i]<0) continue;
566        if (has_t_rep(pos,cans[i],c))//||(trivial_syzygie(pos,cans[i],bound,c))
567{
568
569          connected[connected_length]=cans[i];
570          connected_length++;
571          cans[i]=-1;
572          --not_yet_found;
573
574          if (connected[connected_length-1]==to){
575            if (connected_length<c->n){
576              connected[connected_length]=-1;
577            }
578            omfree(cans);
579            return connected;
580          }
581        }
582      }
583      con_checked++;
584    }
585    else
586    {
587      for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++){
588        if (last_cans_pos==c->n){
589          if (connected_length<c->n){
590            connected[connected_length]=-1;
591          }
592          omfree(cans);
593          return connected;
594        }
595        if ((last_cans_pos==from)||(last_cans_pos==to))
596          continue;
597        if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r)){
598          cans[cans_length]=last_cans_pos;
599          cans_length++;
600          break;
601        }
602      }
603      not_yet_found++;
604      for (int i=0;i<con_checked;i++){
605        if (has_t_rep(connected[i],last_cans_pos,c)){
606
607          connected[connected_length]=last_cans_pos;
608          connected_length++;
609          cans[cans_length-1]=-1;
610
611          --not_yet_found;
612          if (connected[connected_length-1]==to){
613            if (connected_length<c->n){
614              connected[connected_length]=-1;
615            }
616
617            omfree(cans);
618            return connected;
619          }
620          break;
621        }
622      }
623    }
624  }
625  if (connected_length<c->n){
626    connected[connected_length]=-1;
627  }
628
629  omfree(cans);
630  return connected;
631}
632#ifdef HEAD_BIN
633static inline poly p_MoveHead(poly p, omBin b)
634{
635  poly np;
636  omTypeAllocBin(poly, np, b);
637  memmove(np, p, b->sizeW*sizeof(long));
638  omFreeBinAddr(p);
639  return np;
640}
641#endif
642
643
644static void initial_data(calc_dat* c, ideal I){
645  void* h;
646  poly hp;
647  int i,j;
648  c->easy_product_crit=0;
649  c->extended_product_crit=0;
650  c->is_char0=(rChar()==0);
651  c->reduction_steps=0;
652  c->last_index=-1;
653
654
655
656  c->Rcounter=0;
657
658  c->soon_free=NULL;
659
660
661  c->normal_forms=0;
662  c->current_degree=1;
663 
664  c->max_pairs=5*I->idelems();
665 
666  c->apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*c->max_pairs);
667  c->pair_top=-1;
668  int n=I->idelems();
669  for (i=0;i<n;i++){
670    wrp(I->m[i]);
671    PrintS("\n");
672  }
673    i=0;
674  c->n=0;
675  c->T_deg=(int*) omalloc(n*sizeof(int));
676 
677#ifdef HEAD_BIN
678  c->HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long));
679#endif
680  /* omUnGetSpecBin(&(c->HeadBin)); */
681  h=omalloc(n*sizeof(char*));
682  c->states=(char**) h;
683  h=omalloc(n*sizeof(int));
684  c->lengths=(int*) h;
685  h=omalloc(n*sizeof(int));
686        c->gcd_of_terms=(poly*) omalloc(n*sizeof(poly));
687  c->rep=(int*) h;
688  c->short_Exps=(long*) omalloc(n*sizeof(long));
689  c->S=idInit(n,1);
690  c->strat=new skStrategy;
691  c->strat->syzComp = 0;
692  initBuchMoraCrit(c->strat);
693  initBuchMoraPos(c->strat);
694  c->strat->initEcart = initEcartBBA;
695  c->strat->enterS = enterSBba;
696  c->strat->sl = -1;
697  i=n;
698  /* initS(c->S,NULL,c->strat); */
699/* intS start: */
700  i=((i+IDELEMS(c->S)+15)/16)*16;
701  c->strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/
702  c->strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long));
703  /*initsevS(i);*/
704  c->strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/
705  c->strat->fromQ=NULL;
706  c->strat->Shdl=idInit(1,1);
707  c->strat->S=c->strat->Shdl->m;
708  c->strat->lenS=(int*)omAlloc0(i*sizeof(int));
709  if(c->is_char0)
710    c->strat->lenSw=(int*)omAlloc0(i*sizeof(int));
711  else
712    c->strat->lenSw=NULL;
713  sorted_pair_node* si;
714  assume(n>0);
715  add_to_basis(I->m[0],-1,-1,c);
716
717  assume(c->strat->sl==c->strat->Shdl->idelems()-1);
718
719  for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
720   {
721//     add_to_basis(I->m[i],-1,-1,c);
722     si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
723      si->i=-1;
724      si->j=-1;
725      si->expected_length=pLength(I->m[i]);
726      si->deg=pTotaldegree(I->m[i]);
727      si->lcm_of_lm=I->m[i];
728
729//      c->apairs[n-1-i]=si;
730      c->apairs[n-i-1]=si;
731      ++(c->pair_top);
732   }
733}
734//very important: ILM
735
736//len should be weighted length in char 0
737static int simple_posInS (kStrategy strat, poly p,int len, BOOLEAN is_char0)
738{
739
740
741  if(strat->sl==-1) return 0;
742  polyset set=strat->S;
743  intset setL=strat->lenS;
744  if (is_char0) setL=strat->lenSw;
745  int length=strat->sl;
746  int i;
747  int an = 0;
748  int en= length;
749
750  if ((len>setL[length])
751      || ((len==setL[length]) && (pLmCmp(set[length],p)== -1)))
752    return length+1;
753
754  loop
755  {
756    if (an >= en-1)
757    {
758      if ((len<setL[an])
759          || ((len==setL[an]) && (pLmCmp(set[an],p) == 1))) return an;
760      return en;
761    }
762    i=(an+en) / 2;
763    if ((len<setL[i])
764        || ((len==setL[i]) && (pLmCmp(set[i],p) == 1))) en=i;
765    //else if ((len>setL[i])
766    //|| ((len==setL[i]) && (pLmCmp(set[i],p) == -1))) an=i;
767    else an=i;
768  }
769}
770/*2
771 *if the leading term of p
772 *divides the leading term of some S[i] it will be canceled
773 */
774static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k,
775                           kStrategy strat)
776{
777  assume(p_sev == pGetShortExpVector(p));
778  if (!pLmShortDivisibleBy(p,p_sev, strat->S[*at], ~ strat->sevS[*at])) return;
779  if (l>=strat->lenS[*at]) return;
780  PrintS("!");mflush();
781  //pDelete(&strat->S[*at]);
782  deleteInS((*at),strat);
783  (*at)--;
784  (*k)--;
785//  assume(lenS_correct(strat));
786}
787static sorted_pair_node** add_to_basis(poly h, int i_pos, int j_pos,calc_dat* c, int* ip)
788{
789
790  assume(h!=NULL);
791//  BOOLEAN corr=lenS_correct(c->strat);
792  BOOLEAN R_found=FALSE;
793  void* hp;
794
795  ++(c->n);
796  ++(c->S->ncols);
797  int i,j;
798  i=c->n-1;
799  sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i);
800  int spc=0;
801  c->T_deg=(int*) omrealloc(c->T_deg,c->n*sizeof(int));
802  c->T_deg[i]=pTotaldegree(h);
803  hp=omrealloc(c->rep, c->n *sizeof(int));
804  if (hp!=NULL){
805    c->rep=(int*) hp;
806  } else {
807    exit(1);
808  }
809  c->short_Exps=(long *) omrealloc(c->short_Exps ,c->n*sizeof(long));
810
811  hp=omrealloc(c->lengths, c->n *sizeof(int));
812  if (hp!=NULL){
813    c->lengths=(int*) hp;
814  } else {
815    exit(1);
816  }
817  c->lengths[i]=pLength(h);
818  hp=omrealloc(c->states, c->n * sizeof(char*));
819 
820    c->states=(char**) hp;
821  c->gcd_of_terms=(poly*) omrealloc(c->gcd_of_terms, c->n *sizeof(poly));
822  c->gcd_of_terms[i]=gcd_of_terms(h,c->r);
823  c->rep[i]=i;
824  hp=omalloc(i*sizeof(char));
825  if (hp!=NULL){
826    c->states[i]=(char*) hp;
827  } else {
828    exit(1);
829  }
830  hp=omrealloc(c->S->m,c->n*sizeof(poly));
831  if (hp!=NULL){
832    c->S->m=(poly*) hp;
833  } else {
834    exit(1);
835  }
836  c->S->m[i]=h;
837  c->short_Exps[i]=p_GetShortExpVector(h,c->r);
838  for (j=0;j<i;j++){
839    if (c->rep[j]==j){
840      //check product criterion
841
842      c->states[i][j]=UNCALCULATED;
843
844      //lies I[i] under I[j] ?
845      if(p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r)){
846        c->rep[j]=i;
847       
848        PrintS("R"); R_found=TRUE;
849
850        c->Rcounter++;
851        if((i_pos>=0) && (j_pos>=0)){
852       
853        }
854        for(int z=0;z<j;z++){
855          if(c->rep[z]!=z) continue;
856          if (c->states[j][z]==UNCALCULATED){
857            c->states[j][z]=UNIMPORTANT;
858          }
859        }
860        for(int z=j+1;z<i;z++){
861          if(c->rep[z]!=z) continue;
862          if (c->states[z][j]==UNCALCULATED){
863            c->states[z][j]=UNIMPORTANT;
864          }
865        }
866      }
867    }
868    else {
869      c->states[i][j]=UNIMPORTANT;
870    }
871    if ((c->lengths[i]==1) && (c->lengths[j]==1))
872      c->states[i][j]=HASTREP;
873    else if (pHasNotCF(c->S->m[i],c->S->m[j])){
874      c->easy_product_crit++;
875      c->states[i][j]=HASTREP;
876    }
877                        else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c)){
878                                        c->states[i][j]=HASTREP;
879                                        c->extended_product_crit++;
880                                        //PrintS("E");
881                        }
882    if (c->states[i][j]==UNCALCULATED){
883
884     
885      poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
886      if (short_s)
887      {
888        sorted_pair_node* s=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
889        s->i=max(i,j);
890        s->j=min(i,j);
891        s->expected_length=c->lengths[i]+c->lengths[j]-2;
892        s->deg=pTotaldegree(short_s);
893        poly lm=pOne();
894
895        pLcm(c->S->m[i], c->S->m[j], lm);
896        pSetm(lm);
897        s->lcm_of_lm=lm;
898          pDelete(&short_s);
899        //assume(lm!=NULL);
900        nodes[spc]=s;
901        spc++;
902      }
903      else
904      {
905        c->states[i][j]=HASTREP;
906      }
907    }
908  }
909
910  add_to_reductors(c, h, c->lengths[c->n-1]);
911  //i=posInS(c->strat,c->strat->sl,h,0 /*ecart*/);
912
913  if (c->lengths[c->n-1]==1)
914    shorten_tails(c,c->S->m[c->n-1]);
915  //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths
916
917  //for(i=c->strat->sl; i>0;i--)
918  //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
919  if (c->Rcounter>50) {
920    c->Rcounter=0;
921    cleanS(c->strat);
922  }
923  if(!ip){
924    qsort(nodes,spc,sizeof(sorted_pair_node*),pair_better_gen2);
925 
926   
927    c->apairs=merge(c->apairs,c->pair_top+1,nodes,spc,c);
928    c->pair_top+=spc;
929    clean_top_of_pair_list(c);
930    omfree(nodes);
931    return NULL;
932  }
933  {
934    *ip=spc;
935    return nodes;
936  }
937
938 
939
940}
941#if 0
942static poly redNF (poly h,kStrategy strat)
943{
944  int j = 0;
945  int z = 3;
946  unsigned long not_sev;
947
948  if (0 > strat->sl)
949  {
950    return h;
951  }
952  not_sev = ~ pGetShortExpVector(h);
953  loop
954    {
955      if (pLmShortDivisibleBy(strat->S[j], strat->sevS[j], h, not_sev))
956      {
957        //if (strat->interpt) test_int_std(strat->kIdeal);
958        /*- compute the s-polynomial -*/
959#ifdef KDEBUG
960        if (TEST_OPT_DEBUG)
961        {
962          PrintS("red:");
963          wrp(h);
964          PrintS(" with ");
965          wrp(strat->S[j]);
966        }
967#endif
968        h = ksOldSpolyRed(strat->S[j],h,strat->kNoether);
969#ifdef KDEBUG
970        if (TEST_OPT_DEBUG)
971        {
972          PrintS("\nto:");
973          wrp(h);
974          PrintLn();
975        }
976#endif
977        if (h == NULL) return NULL;
978        z++;
979        if (z>=10)
980        {
981          z=0;
982          pNormalize(h);
983        }
984        /*- try to reduce the s-polynomial -*/
985        j = 0;
986        not_sev = ~ pGetShortExpVector(h);
987      }
988      else
989      {
990        if (j >= strat->sl) return h;
991        j++;
992      }
993    }
994}
995#else
996
997static poly redNF2 (poly h,calc_dat* c , int &len)
998{
999  len=0;
1000  if (h==NULL) return NULL;
1001
1002  len=pLength(h);
1003  kStrategy strat=c->strat;
1004  if (0 > strat->sl)
1005  {
1006    return h;
1007  }
1008  int j;
1009  int len_upper_bound=len;
1010  LObject P(h);
1011  P.SetShortExpVector();
1012  P.bucket = kBucketCreate(currRing);
1013  // BOOLEAN corr=lenS_correct(strat);
1014  kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/);
1015  //int max_pos=simple_posInS(strat,P.p);
1016  loop
1017    {
1018//       if (corr){
1019
1020//      corr=lenS_correct(strat);
1021//      if(!corr){
1022//        PrintS("korupt");
1023//      }
1024//       }
1025      int compare_bound;
1026      compare_bound=bucket_guess(P.bucket);
1027      len_upper_bound=min(compare_bound,len_upper_bound);
1028      j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P);
1029      if (j>=0)
1030      {
1031        poly sec_copy=NULL;
1032        //pseudo code
1033        BOOLEAN must_expand=FALSE;
1034        BOOLEAN must_replace_in_basis=(len_upper_bound<strat->lenS[j]);//first test
1035        if (must_replace_in_basis)
1036        {
1037          //second test
1038          if (pLmEqual(P.p,strat->S[j]))
1039          {
1040            PrintS("b");
1041            sec_copy=kBucketClear(P.bucket);
1042            sec_copy=redTailShort(sec_copy, strat);
1043            kBucketInit(P.bucket,pCopy(sec_copy),pLength(sec_copy));
1044          }
1045          else
1046          {
1047            must_replace_in_basis=FALSE;
1048            if ((len_upper_bound==1)
1049                ||(len_upper_bound==2)
1050                ||(len_upper_bound<strat->lenS[j]/2))
1051            {
1052              PrintS("e");
1053              int dummy_len;
1054              kBucketClear(P.bucket,&sec_copy,&dummy_len);
1055              kBucketInit(P.bucket,pCopy(sec_copy),dummy_len
1056                                                  /*pLength(sec_copy)*/);
1057              must_expand=TRUE;
1058            }
1059          }
1060        }
1061//        must_expand=FALSE;
1062//        must_replace_in_basis=FALSE;
1063        nNormalize(pGetCoeff(P.p));
1064#ifdef KDEBUG
1065        if (TEST_OPT_DEBUG)
1066        {
1067          PrintS("red:");
1068          wrp(h);
1069          PrintS(" with ");
1070          wrp(strat->S[j]);
1071        }
1072#endif
1073        len_upper_bound=len_upper_bound+strat->lenS[j]-2;
1074        number coef=kBucketPolyRed(P.bucket,strat->S[j],
1075                                   strat->lenS[j]/*pLength(strat->S[j])*/,
1076                                   strat->kNoether);
1077        nDelete(&coef);
1078        h = kBucketGetLm(P.bucket);
1079
1080        if (must_replace_in_basis){
1081          int pos_in_c=-1;
1082          poly p=strat->S[j];
1083          int z;
1084
1085          int new_length=pLength(sec_copy);
1086          Print("%i",strat->lenS[j]-new_length);
1087          len_upper_bound=new_length +strat->lenS[j]-2;//old entries length
1088          int new_pos;
1089          if(c->is_char0)
1090            new_pos=simple_posInS(c->strat,sec_copy,
1091                                  pSLength(sec_copy,new_length),
1092                                  c->is_char0);//hac
1093          else
1094            new_pos=simple_posInS(c->strat,sec_copy,new_length,c->is_char0);//hack
1095          assume(new_pos<=j);
1096//          p=NULL;
1097          for (z=c->n;z;z--)
1098          {
1099            if(p==c->S->m[z-1])
1100            {
1101
1102
1103              pos_in_c=z-1;
1104
1105              break;
1106            }
1107          }
1108          if (z<=0){
1109            //not in c->S
1110            //LEAVE
1111            deleteInS(j,c->strat);
1112
1113            add_to_reductors(c,sec_copy,pLength(sec_copy));
1114          }
1115          else {
1116//shorten_tails may alter position (not the length, even not by recursion in GLOBAL case)
1117
1118            strat->S[j]=sec_copy;
1119            c->strat->lenS[j]=new_length;
1120            pDelete(&p);
1121
1122            //        replace_quietly(c,j,sec_copy);
1123            // have to do many additional things for consistency
1124            {
1125
1126
1127
1128
1129              int old_pos=j;
1130              new_pos=min(old_pos, new_pos);
1131              assume(new_pos<=old_pos);
1132
1133
1134              c->strat->lenS[old_pos]=new_length;
1135              if(c->strat->lenSw)
1136                c->strat->lenSw[old_pos]=pSLength(sec_copy,new_length);
1137              int i=0;
1138              for(i=new_pos;i<old_pos;i++){
1139                if (strat->lenS[i]<=new_length)
1140                  new_pos++;
1141                else
1142                  break;
1143              }
1144              if (new_pos<old_pos)
1145                move_forward_in_S(old_pos,new_pos,c->strat, c->is_char0);
1146
1147              c->S->m[pos_in_c]=sec_copy;
1148
1149              c->lengths[pos_in_c]=new_length;
1150              if (new_length==1)
1151              {
1152                int i;
1153                for ( i=0;i<pos_in_c;i++)
1154                {
1155                  if (c->lengths[i]==1)
1156                    c->states[pos_in_c][i]=HASTREP;
1157                }
1158                for ( i=z;i<c->n;i++){
1159                  if (c->lengths[i]==1)
1160                    c->states[i][pos_in_c]=HASTREP;
1161                }
1162                shorten_tails(c,sec_copy);
1163              }
1164            }
1165          }
1166        }
1167        if(must_expand){
1168
1169          add_to_reductors(c,sec_copy,pLength(sec_copy));
1170        }
1171        if (h==NULL) return NULL;
1172        P.p=h;
1173        P.t_p=NULL;
1174        P.SetShortExpVector();
1175#ifdef KDEBUG
1176        if (TEST_OPT_DEBUG)
1177        {
1178          PrintS("\nto:");
1179          wrp(h);
1180          PrintLn();
1181        }
1182#endif
1183      }
1184      else
1185      {
1186        kBucketClear(P.bucket,&(P.p),&len);
1187        kBucketDestroy(&P.bucket);
1188        pNormalize(P.p);
1189        return P.p;
1190      }
1191    }
1192}
1193
1194
1195static poly redTailShort(poly h, kStrategy strat){
1196
1197  int sl=strat->sl;
1198  int i;
1199  int len=pLength(h);
1200  for(i=0;i<=strat->sl;i++){
1201    if(strat->lenS[i]>2)
1202      break;
1203  }
1204  return(redNFTail(h,i-1,strat, len));
1205}
1206
1207static void line_of_extended_prod(int fixpos,calc_dat* c){
1208    if (c->gcd_of_terms[fixpos]==NULL)
1209  {
1210    c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r);
1211    if (c->gcd_of_terms[fixpos])
1212    {
1213      int i;
1214      for(i=0;i<fixpos;i++)
1215        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)))
1216{
1217          c->states[fixpos][i]=HASTREP;
1218          c->extended_product_crit++;
1219}     
1220      for(i=fixpos+1;i<c->n;i++)
1221        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)))
1222        {        c->states[i][fixpos]=HASTREP;
1223        c->extended_product_crit++;
1224        }
1225    }
1226  }
1227}
1228static void c_S_element_changed_hook(int pos, calc_dat* c){
1229  length_one_crit(c,pos, c->lengths[pos]);
1230  line_of_extended_prod(pos,c);
1231}
1232
1233static void go_on (calc_dat* c){
1234  //set limit of 1000 for multireductions, at the moment for
1235  //programming reasons
1236  int i=0;
1237  red_object* buf=(red_object*) omalloc(100*sizeof(red_object));
1238  int curr_deg=-1;
1239  while(i<100){
1240    sorted_pair_node* s=top_pair(c);
1241    if (!s) break;
1242    if(curr_deg>=0){
1243      if (s->deg >curr_deg) break;
1244    }
1245
1246    else curr_deg=s->deg;
1247    quick_pop_pair(c);
1248    if(s->i>=0){
1249      //replace_pair(s->i,s->j,c);
1250    if(s->i==s->j) {
1251      free_sorted_pair_node(s,c->r);
1252      continue;
1253        }
1254    }
1255    poly h;
1256    if(s->i>=0)
1257      h=ksOldCreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r);
1258    else
1259      h=s->lcm_of_lm;
1260    if(s->i>=0)
1261      now_t_rep(s->j,s->i,c);
1262    free_sorted_pair_node(s,c->r);
1263    if(!h) continue;
1264    int len=pLength(h);
1265    buf[i].p=h;
1266    buf[i].sev=pGetShortExpVector(h);
1267    buf[i].bucket = kBucketCreate(currRing);
1268    kBucketInit(buf[i].bucket,buf[i].p,len);
1269    i++;
1270  }
1271  c->normal_forms+=i;
1272  qsort(buf,i,sizeof(red_object),red_object_better_gen);
1273//    Print("\ncurr_deg:%i\n",curr_deg);
1274  Print("M[%i, ",i); 
1275  multi_reduction(buf, i, c);
1276  Print("%i]",i);
1277  int j;
1278 //  for(j=0;j<i;j++){
1279//     if(buf[j].p==NULL) PrintS("\n ZERO ALERT \n");
1280//     int z;
1281//      for(z=0;z<j;z++){
1282//       if (pLmEqual(buf[z].p, buf[j].p))
1283//      PrintS("\n Critical Warning!!!! \n");
1284     
1285//     }
1286//   }
1287  int* ibuf=(int*) omalloc(i*sizeof(int));
1288  sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(i*sizeof(sorted_pair_node**));
1289  for(j=0;j<i;j++){
1290 
1291 
1292    int len;
1293    poly p;
1294    kBucketClear(buf[j].bucket,&p, &len);
1295    kBucketDestroy(&buf[j].bucket);
1296    // delete buf[j];
1297    //remember to free res here
1298    p=redTailShort(p, c->strat);
1299    sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
1300   
1301  }
1302  int sum=0;
1303  for(j=0;j<i;j++){
1304    sum+=ibuf[j];
1305  }
1306  sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*));
1307  int partsum=0;
1308  for(j=0;j<i;j++){
1309    memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*));
1310    omfree(sbuf[j]);
1311    partsum+=ibuf[j];
1312  }
1313
1314  qsort(big_sbuf,sum,sizeof(sorted_pair_node*),pair_better_gen2);
1315  c->apairs=merge(c->apairs,c->pair_top+1,big_sbuf,sum,c);
1316  c->pair_top+=sum;
1317  clean_top_of_pair_list(c);
1318  omfree(big_sbuf);
1319  omfree(sbuf);
1320  omfree(ibuf);
1321  omfree(buf);
1322  return;
1323}
1324
1325static poly redNF (poly h,kStrategy strat, int &len)
1326{
1327  len=0;
1328  if (h==NULL) return NULL;
1329  int j;
1330
1331  len=pLength(h);
1332  if (0 > strat->sl)
1333  {
1334    return h;
1335  }
1336  LObject P(h);
1337  P.SetShortExpVector();
1338  P.bucket = kBucketCreate(currRing);
1339  kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/);
1340  //int max_pos=simple_posInS(strat,P.p);
1341  loop
1342    {
1343      j=kFindDivisibleByInS(strat->S,strat->sevS,strat->sl,&P);
1344      if (j>=0)
1345      {
1346        nNormalize(pGetCoeff(P.p));
1347#ifdef KDEBUG
1348        if (TEST_OPT_DEBUG)
1349        {
1350          PrintS("red:");
1351          wrp(h);
1352          PrintS(" with ");
1353          wrp(strat->S[j]);
1354        }
1355#endif
1356        number coef=kBucketPolyRed(P.bucket,strat->S[j],
1357                                   strat->lenS[j]/*pLength(strat->S[j])*/,
1358                                   strat->kNoether);
1359        nDelete(&coef);
1360        h = kBucketGetLm(P.bucket);
1361        if (h==NULL) return NULL;
1362        P.p=h;
1363        P.t_p=NULL;
1364        P.SetShortExpVector();
1365#ifdef KDEBUG
1366        if (TEST_OPT_DEBUG)
1367        {
1368          PrintS("\nto:");
1369          wrp(h);
1370          PrintLn();
1371        }
1372#endif
1373      }
1374      else
1375      {
1376        kBucketClear(P.bucket,&(P.p),&len);
1377        kBucketDestroy(&P.bucket);
1378        pNormalize(P.p);
1379        return P.p;
1380      }
1381    }
1382}
1383#endif
1384#ifdef REDTAIL_S
1385
1386static poly redNFTail (poly h,const int sl,kStrategy strat, int len)
1387{
1388  if (h==NULL) return NULL;
1389  pTest(h);
1390  if (0 > sl)
1391    return h;
1392  if (pNext(h)==NULL) return h;
1393
1394  int j;
1395  poly res=h;
1396  poly act=res;
1397  LObject P(pNext(h));
1398  pNext(res)=NULL;
1399  P.bucket = kBucketCreate(currRing);
1400  len--;
1401  h=P.p;
1402  if (len <=0) len=pLength(h);
1403  kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/);
1404  pTest(h);
1405  loop
1406    {
1407      P.p=h;
1408      P.t_p=NULL;
1409      P.SetShortExpVector();
1410      loop
1411        {
1412          j=kFindDivisibleByInS(strat->S,strat->sevS,sl,&P);
1413          if (j>=0)
1414          {
1415#ifdef REDTAIL_PROT
1416            PrintS("r");
1417#endif
1418            nNormalize(pGetCoeff(P.p));
1419#ifdef KDEBUG
1420            if (TEST_OPT_DEBUG)
1421            {
1422              PrintS("red tail:");
1423              wrp(h);
1424              PrintS(" with ");
1425              wrp(strat->S[j]);
1426            }
1427#endif
1428            number coef;
1429            pTest(strat->S[j]);
1430            coef=kBucketPolyRed(P.bucket,strat->S[j],
1431                                strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether);
1432            pMult_nn(res,coef);
1433            nDelete(&coef);
1434            h = kBucketGetLm(P.bucket);
1435            pTest(h);
1436            if (h==NULL)
1437            {
1438#ifdef REDTAIL_PROT
1439              PrintS(" ");
1440#endif
1441              return res;
1442            }
1443            pTest(h);
1444            P.p=h;
1445            P.t_p=NULL;
1446            P.SetShortExpVector();
1447#ifdef KDEBUG
1448            if (TEST_OPT_DEBUG)
1449            {
1450              PrintS("\nto tail:");
1451              wrp(h);
1452              PrintLn();
1453            }
1454#endif
1455          }
1456          else
1457          {
1458#ifdef REDTAIL_PROT
1459            PrintS("n");
1460#endif
1461            break;
1462          }
1463        } /* end loop current mon */
1464      poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
1465      act->next=tmp;pIter(act);
1466      poly tmp2=pHead(h);
1467      pNeg(tmp2);
1468      int ltmp2=1;
1469      pTest(tmp2);
1470      kBucket_Add_q(P.bucket, tmp2, &ltmp2);
1471
1472      h = kBucketGetLm(P.bucket);
1473      if (h==NULL)
1474      {
1475#ifdef REDTAIL_PROT
1476        PrintS(" ");
1477#endif
1478        return res;
1479      }
1480      pTest(h);
1481    }
1482}
1483#endif
1484
1485static void do_this_spoly_stuff(int i,int j,calc_dat* c){
1486  poly f=c->S->m[i];
1487  poly g=c->S->m[j];
1488  poly h=ksOldCreateSpoly(f, g, NULL, c->r);
1489  poly hr=NULL;
1490#ifdef FULLREDUCTIONS
1491  if (h!=NULL)
1492  {
1493    int len;
1494
1495    hr=redNF2(h,c,len);
1496//      hr=redNF(h,c->strat,len);
1497
1498    if (hr!=NULL)
1499#ifdef REDTAIL_S
1500      hr = redNFTail(hr,c->strat->sl,c->strat,len);
1501#else
1502    hr = redtailBba(hr,c->strat->sl,c->strat);
1503#endif
1504
1505  }
1506#else
1507  if (h!=NULL)
1508  {
1509    int len;
1510    hr=redNF2(h,c,len);
1511  }
1512#endif
1513  c->normal_forms++;
1514  if (hr==NULL)
1515  {
1516    notice_miss(i, j, c);
1517
1518  }
1519  else
1520  {
1521
1522#ifdef HEAD_BIN
1523    hr=p_MoveHead(hr,c->HeadBin);
1524#endif
1525    add_to_basis(hr, i,j,c);
1526  }
1527}
1528//try to fill, return FALSE iff queue is empty
1529
1530static int poly_crit(const void* ap1, const void* ap2){
1531  poly p1,p2;
1532  p1=*((poly*) ap1);
1533  p2=*((poly*)ap2);
1534
1535  int c=pLmCmp(p1,p2);
1536  if (c !=0) return c;
1537  int l1=pLength(p1);
1538  int l2=pLength(p2);
1539  if (l1<l2) return -1;
1540  if (l1>l2) return 1;
1541  return 0;
1542}
1543ideal t_rep_gb(ring r,ideal arg_I){
1544   Print("Idelems %i \n----------\n",IDELEMS(arg_I));
1545  ideal I_temp=idCopy(arg_I); //kInterRed(arg_I);
1546  ideal I=idCompactify(I_temp);
1547  qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit);
1548  idDelete(&I_temp);
1549  Print("Idelems %i \n----------\n",IDELEMS(I));
1550  calc_dat* c=(calc_dat*) omalloc(sizeof(calc_dat));
1551  c->r=currRing;
1552
1553  initial_data(c,I);
1554
1555  while(c->pair_top>=0)
1556    go_on(c);
1557   omfree(c->rep);
1558  for(int z=0;z<c->n;z++){
1559    omfree(c->states[z]);
1560  }
1561  omfree(c->states);
1562  omfree(c->lengths);
1563
1564
1565  omfree(c->short_Exps);
1566  omfree(c->T_deg);
1567  int i;
1568  for(i=0;i<c->n;i++){
1569    if(c->gcd_of_terms[i])
1570      pDelete(&(c->gcd_of_terms[i]));
1571  }
1572  omfree(c->gcd_of_terms);
1573
1574  omfree(c->apairs);
1575  printf("calculated %d NFs\n",c->normal_forms);
1576  printf("applied %i product crit, %i extended_product crit \n", c->easy_product_crit, c->extended_product_crit);
1577  I=c->S;
1578  IDELEMS(I)=c->n;
1579  omfree(c);
1580
1581  return(I);
1582}
1583static void now_t_rep(const int & arg_i, const int & arg_j, calc_dat* c){
1584  int i,j;
1585  if (arg_i==arg_j){
1586    return;
1587  }
1588  if (arg_i>arg_j){
1589    i=arg_j;
1590    j=arg_i;
1591  } else {
1592    i=arg_i;
1593    j=arg_j;
1594  }
1595  c->states[j][i]=HASTREP;
1596}
1597static void soon_t_rep(const int& arg_i, const int& arg_j, calc_dat* c)
1598{
1599  assume(0<=arg_i);
1600  assume(0<=arg_j);
1601  assume(arg_i<c->n);
1602  assume(arg_j<c->n);
1603  int i,j;
1604  if (arg_i==arg_j){
1605    return;
1606  }
1607  if (arg_i>arg_j){
1608    i=arg_j;
1609    j=arg_i;
1610  } else {
1611    i=arg_i;
1612    j=arg_j;
1613  }
1614  if (!
1615      (c->states[j][i]==HASTREP))
1616    c->states[j][i]=SOONTREP;
1617}
1618static BOOLEAN has_t_rep(const int & arg_i, const  int & arg_j, calc_dat* state){
1619  assume(0<=arg_i);
1620  assume(0<=arg_j);
1621  assume(arg_i<state->n);
1622  assume(arg_j<state->n);
1623  if (arg_i==arg_j)
1624  {
1625    return (TRUE);
1626  }
1627  if (arg_i>arg_j)
1628  {
1629    return (state->states[arg_i][arg_j]==HASTREP);
1630  } else
1631  {
1632    return (state->states[arg_j][arg_i]==HASTREP);
1633  }
1634}
1635static int pLcmDeg(poly a, poly b)
1636{
1637  int i;
1638  int n=0;
1639  for (i=pVariables; i; i--)
1640  {
1641    n+=max( pGetExp(a,i), pGetExp(b,i));
1642  }
1643  return n;
1644
1645}
1646
1647
1648
1649static void shorten_tails(calc_dat* c, poly monom)
1650{
1651  return;
1652// BOOLEAN corr=lenS_correct(c->strat);
1653  for(int i=0;i<c->n;i++)
1654  {
1655    //enter tail
1656    if (c->rep[i]!=i) continue;
1657    if (c->S->m[i]==NULL) continue;
1658    poly tail=c->S->m[i]->next;
1659    poly prev=c->S->m[i];
1660    BOOLEAN did_something=FALSE;
1661    while((tail!=NULL)&& (pLmCmp(tail, monom)>=0))
1662    {
1663      if (p_LmDivisibleBy(monom,tail,c->r))
1664      {
1665        did_something=TRUE;
1666        prev->next=tail->next;
1667        tail->next=NULL;
1668        p_Delete(& tail,c->r);
1669        tail=prev;
1670        //PrintS("Shortened");
1671        c->lengths[i]--;
1672      }
1673      prev=tail;
1674      tail=tail->next;
1675    }
1676    if (did_something)
1677    {
1678      int new_pos;
1679      if (c->is_char0) 
1680        simple_posInS(c->strat,c->S->m[i],pSLength(c->S->m[i],c->lengths[i]),c->is_char0);
1681      else     
1682        simple_posInS(c->strat,c->S->m[i],c->lengths[i],c->is_char0);
1683      int old_pos=-1;
1684      //assume new_pos<old_pos
1685      for (int z=0;z<=c->strat->sl;z++)
1686      {
1687        if (c->strat->S[z]==c->S->m[i])
1688        {
1689          old_pos=z;
1690          break;
1691        }
1692      }
1693      if (old_pos== -1)
1694        for (int z=new_pos-1;z>=0;z--)
1695        {
1696          if (c->strat->S[z]==c->S->m[i])
1697          {
1698            old_pos=z;
1699            break;
1700          }
1701        }
1702      assume(old_pos>=0);
1703      assume(new_pos<=old_pos);
1704      assume(pLength(c->strat->S[old_pos])==c->lengths[i]);
1705      c->strat->lenS[old_pos]=c->lengths[i];
1706      if (c->strat->lenSw)
1707        c->strat->lenSw[old_pos]=pSLength(c->S->m[i],c->lengths[i]);
1708
1709      if (new_pos<old_pos)
1710        move_forward_in_S(old_pos,new_pos,c->strat, c->is_char0);
1711
1712      length_one_crit(c,i,c->lengths[i]);
1713    }
1714  }
1715}
1716static sorted_pair_node* pop_pair(calc_dat* c){
1717  clean_top_of_pair_list(c);
1718
1719  if(c->pair_top<0) return NULL;
1720  else return (c->apairs[c->pair_top--]);
1721}
1722static sorted_pair_node* top_pair(calc_dat* c){
1723  super_clean_top_of_pair_list(c);//yeah, I know, it's odd that I use a different proc here
1724
1725  if(c->pair_top<0) return NULL;
1726  else return (c->apairs[c->pair_top]);
1727}
1728static sorted_pair_node* quick_pop_pair(calc_dat* c){
1729  if(c->pair_top<0) return NULL;
1730  else return (c->apairs[c->pair_top--]);
1731}
1732static BOOLEAN no_pairs(calc_dat* c){
1733  clean_top_of_pair_list(c);
1734  return (c->pair_top==-1);
1735}
1736
1737
1738static void super_clean_top_of_pair_list(calc_dat* c){
1739  while((c->pair_top>=0) && (c->apairs[c->pair_top]->i>=0) && (good_has_t_rep(c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,c))){
1740
1741    free_sorted_pair_node(c->apairs[c->pair_top],c->r);
1742    c->pair_top--;
1743
1744  }
1745}
1746static void clean_top_of_pair_list(calc_dat* c){
1747  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))){
1748
1749    free_sorted_pair_node(c->apairs[c->pair_top],c->r);
1750    c->pair_top--;
1751
1752  }
1753}
1754static BOOLEAN state_is(calc_state state, const int & arg_i, const  int & arg_j, calc_dat* c){
1755  assume(0<=arg_i);
1756  assume(0<=arg_j);
1757  assume(arg_i<c->n);
1758  assume(arg_j<c->n);
1759  if (arg_i==arg_j)
1760  {
1761    return (TRUE);
1762  }
1763  if (arg_i>arg_j)
1764  {
1765    return (c->states[arg_i][arg_j]==state);
1766  }
1767  else return(c->states[arg_j][arg_i]==state);
1768}
1769static void free_sorted_pair_node(sorted_pair_node* s, ring r){
1770  if (s->i>=0)
1771    p_Delete(&s->lcm_of_lm,r);
1772  omfree(s);
1773}
1774static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, calc_dat* c){
1775  if (a->deg<b->deg) return TRUE;
1776  if (a->deg>b->deg) return FALSE;
1777
1778  if (a->expected_length<b->expected_length) return TRUE;
1779  if (a->expected_length>b->expected_length) return FALSE;
1780  int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm);
1781  if (comp==1) return FALSE;
1782  if (-1==comp) return TRUE;
1783  if (a->i<b->i) return TRUE;
1784  if (a->j<b->j) return TRUE;
1785  return FALSE;
1786}
1787
1788static int pair_better_gen(const void* ap,const void* bp){
1789
1790  sorted_pair_node* a=*((sorted_pair_node**)ap);
1791  sorted_pair_node* b=*((sorted_pair_node**)bp);
1792  assume(a->i>a->j);
1793  assume(b->i>b->j);
1794  if (a->deg<b->deg) return -1;
1795  if (a->deg>b->deg) return 1;
1796
1797
1798  if (a->expected_length<b->expected_length) return -1;
1799  if (a->expected_length>b->expected_length) return 1;
1800 int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm);
1801 
1802  if (comp==1) return 1;
1803  if (-1==comp) return -1;
1804  if (a->i<b->i) return -1;
1805  if (a->j<b->j) return -1;
1806  return 0;
1807}
1808
1809
1810static poly gcd_of_terms(poly p, ring r){
1811  int max_g_0=0;
1812  assume(p!=NULL);
1813  int i;
1814  poly m=pOne();
1815  poly t;
1816  for (i=pVariables; i; i--)
1817  {
1818      pSetExp(m,i, pGetExp(p,i));
1819      if (max_g_0==0)
1820        if (pGetExp(m,i)>0)
1821          max_g_0=i;
1822  }
1823 
1824  t=p->next;
1825  while (t!=NULL){
1826   
1827    if (max_g_0==0) break;
1828    for (i=pVariables; i; i--)
1829    {
1830      pSetExp(m,i, min(pGetExp(t,i),pGetExp(m,i)));
1831      if (max_g_0==i)
1832        if (pGetExp(m,i)==0)
1833          max_g_0=0;
1834      if ((max_g_0==0) && (pGetExp(m,i)>0)){
1835        max_g_0=i;
1836      }
1837    }
1838                t=t->next;
1839  }
1840        for (i=pVariables;i;i--)
1841        {
1842                if(pGetExp(m,i)>0)
1843                        return m;
1844  }
1845        pDelete(&m);
1846  return NULL;
1847}
1848static BOOLEAN pHasNotCFExtended(poly p1, poly p2, poly m)
1849{
1850
1851  if (pGetComp(p1) > 0 || pGetComp(p2) > 0)
1852    return FALSE;
1853  int i = 1;
1854  loop
1855  {
1856    if ((pGetExp(p1, i)-pGetExp(m,i) >0) && (pGetExp(p2, i) -pGetExp(m,i)> 0))   return FALSE;
1857    if (i == pVariables)                                return TRUE;
1858    i++;
1859  }
1860}
1861
1862
1863//for impl reasons may return false if the the normal product criterion matches
1864static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, calc_dat* c){
1865  if(gcd1==NULL) return FALSE;
1866        if(gcd2==NULL) return FALSE;
1867        gcd1->next=gcd2; //may ordered incorrect
1868        poly m=gcd_of_terms(gcd1,c->r);
1869        gcd1->next=NULL;
1870        if (m==NULL) return FALSE;
1871
1872        BOOLEAN erg=pHasNotCFExtended(p1,p2,m);
1873        pDelete(&m);
1874        return erg;
1875}
1876static poly kBucketGcd(kBucket* b, ring r)
1877{
1878  int s=0;
1879  int i;
1880  poly m, n;
1881  BOOLEAN initialized=FALSE;
1882  for (i=MAX_BUCKET-1;i>=0;i--)
1883  { 
1884    if (b->buckets[i]!=NULL){
1885      if (!initialized){
1886        m=gcd_of_terms(b->buckets[i],r);
1887        initialized=TRUE;
1888        if (m==NULL) return NULL;
1889      }
1890      else
1891        {
1892          n=gcd_of_terms(b->buckets[i],r);
1893          if (n==NULL) {
1894            pDelete(&m);
1895            return NULL;   
1896          }
1897          n->next=m;
1898          poly t=gcd_of_terms(n,r);
1899          n->next=NULL;
1900          pDelete(&m);
1901          pDelete(&n);
1902          m=t;
1903          if (m==NULL) return NULL;
1904         
1905        }
1906    }
1907  }
1908  return m;
1909}
1910
1911
1912struct find_erg{
1913  poly expand;
1914  int expand_length;
1915  int to_reduce_u;
1916  int to_reduce_l;
1917  int reduce_by;//index of reductor
1918  BOOLEAN fromS;//else from los
1919
1920};
1921static int guess_quality(const red_object & p, calc_dat* c){
1922  //looks only on bucket
1923  if (c->is_char0) return kSBucketLength(p.bucket);
1924  return (bucket_guess(p.bucket));
1925}
1926static int quality_of_pos_in_strat_S(int pos, calc_dat* c){
1927  if (c->is_char0) return c->strat->lenSw[pos];
1928  return c->strat->lenS[pos];
1929}
1930static int quality(poly p, int len, calc_dat* c){
1931  if (c->is_char0) return pSLength(p,len);
1932  return pLength(p);
1933}
1934static void multi_reduction_lls_trick(red_object* los, int losl,calc_dat* c,find_erg & erg){
1935  erg.expand=NULL;
1936  BOOLEAN swap_roles; //from reduce_by, to_reduce_u if fromS
1937  if(erg.fromS){
1938    if(pLmEqual(c->strat->S[erg.reduce_by],los[erg.to_reduce_u].p))
1939    {
1940      int i;
1941      int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c);
1942      int best=erg.to_reduce_u+1;
1943      for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){
1944        int qc=guess_quality(los[i],c);
1945        if (qc<quality_a){
1946          best=i;
1947          quality_a=qc;
1948        }
1949      }
1950      if(best!=erg.to_reduce_u+1){
1951        red_object h=los[erg.to_reduce_u];
1952        los[erg.to_reduce_u]=los[best];
1953        los[best]=h;
1954        swap_roles=TRUE;
1955      }
1956      else{
1957       
1958        swap_roles=FALSE;
1959      }
1960 
1961    }
1962      else
1963    {
1964      if (erg.to_reduce_u>erg.to_reduce_l){
1965
1966        int i;
1967        int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c);
1968        int best=erg.to_reduce_u+1;
1969        for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){
1970          int qc=guess_quality(los[i],c);
1971          if (qc<quality_a){
1972            best=i;
1973            quality_a=qc;
1974          }
1975        }
1976        if(best!=erg.to_reduce_u+1){
1977          red_object h=los[erg.to_reduce_l];
1978          los[erg.to_reduce_l]=los[best];
1979          los[best]=h;
1980          erg.reduce_by=erg.to_reduce_l;
1981          erg.fromS=FALSE;
1982          erg.to_reduce_l++;
1983         
1984        }
1985      }
1986      else 
1987      {
1988        assume(erg.to_reduce_u==erg.to_reduce_l);
1989        int quality_a=quality_of_pos_in_strat_S(erg.reduce_by,c);
1990        int qc=guess_quality(los[erg.to_reduce_u],c);
1991        if(qc<quality_a){
1992          BOOLEAN exp=FALSE;
1993          if(qc<=2)
1994            exp=TRUE;
1995          else {
1996            if (qc<quality_a/2)
1997              exp=TRUE;
1998            else
1999              if(erg.reduce_by<c->n/4)
2000                exp=TRUE;
2001          }
2002          if (exp){
2003            poly clear_into;
2004           
2005            kBucketClear(los[erg.to_reduce_u].bucket,&clear_into,&erg.expand_length);
2006            erg.expand=pCopy(clear_into);
2007            kBucketInit(los[erg.to_reduce_u].bucket,clear_into,erg.expand_length);
2008            PrintS("e");
2009           
2010          }
2011        }
2012
2013       
2014      }
2015     
2016      swap_roles=FALSE;
2017      return;
2018      }
2019   
2020  }
2021  else{
2022    if(erg.reduce_by>erg.to_reduce_u){
2023      //then lm(rb)>= lm(tru) so =
2024      assume(erg.reduce_by==erg.to_reduce_u+1);
2025      int best=erg.reduce_by;
2026      int quality_a=guess_quality(los[erg.reduce_by],c);
2027      int i;
2028        for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--){
2029          int qc=guess_quality(los[i],c);
2030          if (qc<quality_a){
2031            best=i;
2032            quality_a=qc;
2033          }
2034        }
2035        if(best!=erg.reduce_by){
2036          red_object h=los[erg.reduce_by];
2037          los[erg.reduce_by]=los[best];
2038          los[best]=h;
2039        }
2040        swap_roles=FALSE;
2041        return;
2042       
2043         
2044    }
2045    else
2046    {
2047      assume(!pLmEqual(los[erg.reduce_by].p,los[erg.to_reduce_l].p));
2048      //further assume, that reduce_by is the above all other polys
2049      //with same leading term
2050      int il=erg.reduce_by;
2051      int quality_a =guess_quality(los[erg.reduce_by],c);
2052      int qc;
2053      while((il>0) && pLmEqual(los[il-1].p,los[il].p)){
2054        il--;
2055        qc=guess_quality(los[il],c);
2056        if (qc<quality_a){
2057          quality_a=qc;
2058          erg.reduce_by=il;
2059        }
2060      }
2061      swap_roles=FALSE;
2062    }
2063 
2064  }
2065  if(swap_roles){
2066    PrintS("b");
2067    poly clear_into;
2068    int dummy_len;
2069    int new_length;
2070    int bp=erg.to_reduce_u;//bucket_positon
2071    kBucketClear(los[bp].bucket,&clear_into,&new_length);
2072    poly p=c->strat->S[erg.reduce_by];
2073    int j=erg.reduce_by;
2074    int old_length=c->strat->lenS[j];// in view of S
2075    los[bp].p=p;
2076    kBucketInit(los[bp].bucket,p,old_length);
2077    int qal=quality(clear_into,new_length,c);
2078    int pos_in_c=-1;   
2079    int z;
2080    int new_pos;
2081    new_pos=simple_posInS(c->strat,clear_into,qal,c->is_char0);
2082    assume(new_pos<=j);
2083    for (z=c->n;z;z--)
2084    {
2085      if(p==c->S->m[z-1])
2086      {
2087        pos_in_c=z-1;
2088        break;
2089      }
2090    }
2091    if(pos_in_c>=0)
2092    {
2093      c->S->m[pos_in_c]=clear_into;
2094      c->lengths[pos_in_c]=new_length;
2095      c_S_element_changed_hook(pos_in_c,c);
2096    }
2097    c->strat->S[j]=clear_into;
2098    c->strat->lenS[j]=new_length;
2099    if(c->strat->lenSw)
2100      c->strat->lenS[j]=qal;
2101    if(c->is_char0)
2102    {
2103      pContent(clear_into);
2104      pCleardenom(clear_into);
2105    }
2106  else                     
2107    pNorm(clear_into);
2108    if (new_pos<j){
2109      move_forward_in_S(j,new_pos,c->strat,c->is_char0);
2110      erg.reduce_by=new_pos;
2111    }
2112  }
2113}
2114static void multi_reduction_find(red_object* los, int losl,calc_dat* c,int startf,find_erg & erg){
2115  kStrategy strat=c->strat;
2116
2117  assume(startf<=losl);
2118  assume((startf==losl-1)||(pLmCmp(los[startf].p,los[startf+1].p)==-1));
2119  int i=startf;
2120 
2121  int j;
2122  while(i>=0){
2123    assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)<=0));
2124    j=kFindDivisibleByInS_easy(strat,los[i]);
2125    if(j>=0){
2126     
2127      erg.to_reduce_u=i;
2128      erg.reduce_by=j;
2129      erg.fromS=TRUE;
2130      int i2;
2131      for(i2=i-1;i2>=0;i2--){
2132        if(!pLmEqual(los[i].p,los[i2].p))
2133          break;
2134      }
2135      erg.to_reduce_l=i2+1;
2136      assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1));
2137      return;
2138    }
2139    if (j<0){
2140     
2141      //not reduceable, try to use this for reducing higher terms
2142      int i2;
2143      i2=i;
2144      while((i2>0)&&(pLmEqual(los[i].p,los[i2-1].p)))
2145        i2--;
2146      if(i2!=i){
2147       
2148        erg.to_reduce_u=i-1;
2149        erg.to_reduce_l=i2;
2150        erg.reduce_by=i;
2151        erg.fromS=FALSE;
2152        assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1));
2153        return;
2154      }
2155 
2156      for (i2=i+1;i2<losl;i2++){
2157        if (p_LmShortDivisibleBy(los[i].p,los[i].sev,los[i2].p,~los[i2].sev,
2158                                c->r)){
2159          int i3=i2;
2160          while((i3+1<losl) && (pLmEqual(los[i2].p, los[i3+1].p)))
2161            i3++;
2162          erg.to_reduce_u=i3;
2163          erg.to_reduce_l=i2;
2164          erg.reduce_by=i;
2165          erg.fromS=FALSE;
2166          assume((i==losl-1)||(pLmCmp(los[i].p,los[i+1].p)==-1));
2167          return;
2168        }
2169//      else {assume(!p_LmDivisibleBy(los[i].p, los[i2].p,c->r));}
2170      }
2171
2172      i--;
2173    }
2174  }
2175  erg.reduce_by=-1;//error code
2176  return;
2177}
2178
2179 //  nicht reduzierbare eintraege in ergebnisliste schreiben
2180//   nullen loeschen
2181//   while(finde_groessten leitterm reduzierbar(c,erg)){
2182 
2183static int multi_reduction_clear_zeroes(red_object* los, int  losl, int l, int u)
2184{
2185
2186
2187  int deleted=0;
2188  int  i=l;
2189  int last=-1;
2190  while(i<=u)
2191  {
2192   
2193    if(los[i].p==NULL){
2194      kBucketDestroy(&los[i].bucket);
2195//      delete los[i];//here we assume los are constructed with new
2196      //destroy resources, must be added here   
2197     if (last>=0)
2198     {
2199       memmove(los+(int)(last+1-deleted),los+(last+1),sizeof(red_object)*(i-1-last));
2200     }
2201     last=i;
2202     deleted++;
2203    }
2204    i++;
2205  }
2206  if((last>=0)&&(last!=losl-1))
2207      memmove(los+(int)(last+1-deleted),los+last+1,sizeof(red_object)*(losl-1-last));
2208  return deleted;
2209 
2210}
2211
2212static void sort_region_down(red_object* los, int l, int u, calc_dat* c)
2213{
2214  qsort(los+l,u-l+1,sizeof(red_object),red_object_better_gen);
2215  int i;
2216
2217  for(i=l;i<=u;i++)
2218  {
2219    BOOLEAN moved=FALSE;
2220    int j;
2221    for(j=i;j;j--)
2222    {
2223      if(pLmCmp(los[j].p,los[j-1].p)==-1){
2224        red_object h=los[j];
2225        los[j]=los[j-1];
2226        los[j-1]=h;
2227        moved=TRUE;
2228      }
2229      else break;
2230    }
2231    if(!moved) return;
2232  }
2233}
2234
2235//assume that los is ordered ascending by leading term, all non zero
2236static void multi_reduction(red_object* los, int & losl, calc_dat* c)
2237{
2238 
2239  //initialize;
2240  assume(c->strat->sl>=0);
2241  assume(losl>0);
2242  int i;
2243  for(i=0;i<losl;i++){
2244    los[i].sev=pGetShortExpVector(los[i].p);
2245//SetShortExpVector();
2246    los[i].p=kBucketGetLm(los[i].bucket);
2247  }
2248
2249  kStrategy strat=c->strat;
2250  int curr_pos=losl-1;
2251
2252
2253//  nicht reduzierbare einträge in ergebnisliste schreiben
2254  // nullen loeschen
2255  while(curr_pos>=0){
2256    find_erg erg;
2257    multi_reduction_find(los, losl,c,curr_pos,erg);//last argument should be curr_pos
2258   //  PrintS("\n erg:\n");
2259//     Print("upper:%i\n",erg.to_reduce_u);
2260//     Print("lower:%i\n",erg.to_reduce_l);
2261//     Print("reduce_by:%i\n",erg.reduce_by);
2262//     Print("fromS:%i\n",erg.fromS);
2263    if(erg.reduce_by<0) break;
2264    multi_reduction_lls_trick(los,losl,c,erg);
2265    //erweitern? muß noch implementiert werden
2266    int i;
2267    int len;
2268    poly reductor;
2269    if(erg.fromS){
2270      reductor=strat->S[erg.reduce_by];
2271      len=strat->lenS[erg.reduce_by];
2272     
2273    }
2274    else 
2275    {
2276      //bucket aufloesen reduzieren, neu füllen
2277     
2278   
2279      int bn=kBucketCanonicalize(los[erg.reduce_by].bucket);
2280      reductor=los[erg.reduce_by].bucket->buckets[bn];
2281      len=los[erg.reduce_by].bucket->buckets_length[bn];
2282      if(c->is_char0)
2283        pContent(reductor);
2284 
2285    }
2286    for(i=erg.to_reduce_l;i<=erg.to_reduce_u;i++)
2287    {
2288   
2289      assume((erg.fromS)||(i!=erg.reduce_by));
2290      assume(reductor!=NULL);
2291       number coef=kBucketPolyRed(los[i].bucket,reductor,
2292                                  len,
2293                                  strat->kNoether);
2294       nDelete(&coef);
2295       los[i].p = kBucketGetLm(los[i].bucket);
2296       if(los[i].p!=NULL)
2297         if((i>0)&&(los[i-1].p!=NULL)&&(pLmEqual(los[i-1].p,los[i].p)))
2298             los[i].sev=los[i-1].sev;
2299         else
2300           los[i].sev=pGetShortExpVector(los[i].p);
2301       //better would be first sorting before sev
2302    }
2303 
2304                 
2305    int deleted=multi_reduction_clear_zeroes(los, losl, erg.to_reduce_l, erg.to_reduce_u);
2306    curr_pos=erg.to_reduce_u;
2307    losl -= deleted;
2308    curr_pos -= deleted;
2309
2310    //Print("deleted %i \n",deleted);
2311    sort_region_down(los, erg.to_reduce_l, erg.to_reduce_u-deleted, c);
2312//   sort_region_down(los, 0, losl-1, c);
2313    //  qsort(los,losl,sizeof(red_object),red_object_better_gen);
2314    if(erg.expand)
2315      add_to_reductors(c,erg.expand,erg.expand_length);
2316  }
2317  return;
2318}
Note: See TracBrowser for help on using the repository browser.