Changeset 410ea0f in git


Ignore:
Timestamp:
May 27, 2011, 4:18:06 PM (13 years ago)
Author:
Hans Schoenemann <hannes@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', '648d28f488f6ff08f5607ff229b9ad9e4a5b93c2')
Children:
db83bf13b62d944de021f52de5ae04b7ffd0390e
Parents:
a41623dd1e56318466dc81751481d37d19489c7b
Message:
format

git-svn-id: file:///usr/local/Singular/svn/trunk@14250 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed
  • kernel/tgb.cc

    ra41623 r410ea0f  
    3232#define BUCKETS_FOR_NORO_RED 1
    3333#define SR_HDL(A) ((long)(A))
    34 static const int bundle_size=100;
    35 static const int bundle_size_noro=10000;
    36 static const int delay_factor=3;
    37 int QlogSize(number n);
     34static const int bundle_size = 100;
     35static const int bundle_size_noro = 10000;
     36static const int delay_factor = 3;
     37int QlogSize (number n);
    3838#define ADD_LATER_SIZE 500
    3939#if 1
    40 static omBin lm_bin=NULL;
    41 
    42 static void simplify_poly(poly p, ring r)
    43 {
    44      assume(r==currRing);
    45      if (!rField_is_Zp(r))
    46      {
    47         p_Cleardenom(p,r);
    48         //p_Content(p,r); //is a duplicate call, but belongs here
    49      }
    50      else
    51        pNorm(p);
    52 }
     40static omBin lm_bin = NULL;
     41
     42static void
     43simplify_poly (poly p, ring r)
     44{
     45  assume (r == currRing);
     46  if (!rField_is_Zp (r))
     47  {
     48    p_Cleardenom (p, r);
     49    //p_Content(p,r); //is a duplicate call, but belongs here
     50  }
     51  else
     52    pNorm (p);
     53}
     54
    5355//static const BOOLEAN up_to_radical=TRUE;
    5456
    55 int slim_nsize(number n, ring r)
    56 {
    57   if (rField_is_Zp(r))
     57int
     58slim_nsize (number n, ring r)
     59{
     60  if (rField_is_Zp (r))
    5861  {
    5962    return 1;
    6063  }
    61   if (rField_is_Q(r))
    62   {
    63     return QlogSize(n);
     64  if (rField_is_Q (r))
     65  {
     66    return QlogSize (n);
    6467  }
    6568  else
    6669  {
    67     return n_Size(n,r);
    68   }
    69 }
    70 static BOOLEAN monomial_root(poly m, ring r)
    71 {
    72     BOOLEAN changed=FALSE;
    73     int i;
    74     for(i=1;i<=rVar(r);i++)
    75     {
    76         int e=p_GetExp(m,i,r);
    77         if (e>1)
    78         {
    79             p_SetExp(m,i,1,r);
    80             changed=TRUE;
    81         }
    82     }
    83     if (changed) {
    84         p_Setm(m,r);
    85     }
    86     return changed;
    87 }
    88 static BOOLEAN polynomial_root(poly h, ring r)
    89 {
    90   poly got=gcd_of_terms(h,r);
    91   BOOLEAN changed=FALSE;
    92   if((got!=NULL) &&(TEST_V_UPTORADICAL)) {
    93     poly copy=p_Copy(got,r);
     70    return n_Size (n, r);
     71  }
     72}
     73
     74static BOOLEAN
     75monomial_root (poly m, ring r)
     76{
     77  BOOLEAN changed = FALSE;
     78  int i;
     79  for (i = 1; i <= rVar (r); i++)
     80  {
     81    int e = p_GetExp (m, i, r);
     82    if (e > 1)
     83    {
     84      p_SetExp (m, i, 1, r);
     85      changed = TRUE;
     86    }
     87  }
     88  if (changed)
     89  {
     90    p_Setm (m, r);
     91  }
     92  return changed;
     93}
     94
     95static BOOLEAN
     96polynomial_root (poly h, ring r)
     97{
     98  poly got = gcd_of_terms (h, r);
     99  BOOLEAN changed = FALSE;
     100  if ((got != NULL) && (TEST_V_UPTORADICAL))
     101  {
     102    poly copy = p_Copy (got, r);
    94103    //p_wrp(got,c->r);
    95     changed=monomial_root(got,r);
     104    changed = monomial_root (got, r);
    96105    if (changed)
    97106    {
    98          poly div_by=pDivide(copy, got);
    99          poly iter=h;
    100          while(iter)
    101          {
    102             pExpVectorSub(iter,div_by);
    103             pIter(iter);
    104          }
    105          p_Delete(&div_by, r);
    106          if (TEST_OPT_PROT)
    107              PrintS("U");
    108     }
    109     p_Delete(&copy,r);
    110   }
    111   p_Delete(&got,r);
     107      poly div_by = pDivide (copy, got);
     108      poly iter = h;
     109      while (iter)
     110      {
     111        pExpVectorSub (iter, div_by);
     112        pIter (iter);
     113      }
     114      p_Delete (&div_by, r);
     115      if (TEST_OPT_PROT)
     116        PrintS ("U");
     117    }
     118    p_Delete (&copy, r);
     119  }
     120  p_Delete (&got, r);
    112121  return changed;
    113122}
    114 static inline poly p_Init_Special(const ring r)
    115 {
    116   return p_Init(r,lm_bin);
    117 }
    118 static inline poly pOne_Special(const ring r=currRing)
    119 {
    120   poly rc = p_Init_Special(r);
    121   pSetCoeff0(rc,n_Init(1,r));
     123
     124static inline poly
     125p_Init_Special (const ring r)
     126{
     127  return p_Init (r, lm_bin);
     128}
     129
     130static inline poly
     131pOne_Special (const ring r = currRing)
     132{
     133  poly rc = p_Init_Special (r);
     134  pSetCoeff0 (rc, n_Init (1, r));
    122135  return rc;
    123136}
     137
    124138// zum Initialiseren: in t_rep_gb plazieren:
    125139
     
    133147#ifdef LEN_VAR1
    134148// erste Variante: Laenge: Anzahl der Monome
    135 static inline int pSLength(poly p, int l) { return l; }
    136 static inline int kSBucketLength(kBucket* bucket, poly lm)
    137   {return bucket_guess(bucket);}
     149static inline int
     150pSLength (poly p, int l)
     151{
     152  return l;
     153}
     154
     155static inline int
     156kSBucketLength (kBucket * bucket, poly lm)
     157{
     158  return bucket_guess (bucket);
     159}
    138160#endif
    139161
    140162#ifdef LEN_VAR2
    141163// 2. Variante: Laenge: Platz fuer die Koeff.
    142 int pSLength(poly p,int l)
    143 {
    144   int s=0;
    145   while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); }
     164int
     165pSLength (poly p, int l)
     166{
     167  int s = 0;
     168  while (p != NULL)
     169  {
     170    s += nSize (pGetCoeff (p));
     171    pIter (p);
     172  }
    146173  return s;
    147174}
    148 int kSBucketLength(kBucket* b, poly lm)
    149 {
    150   int s=0;
     175
     176int
     177kSBucketLength (kBucket * b, poly lm)
     178{
     179  int s = 0;
    151180  int i;
    152   for (i=MAX_BUCKET;i>=0;i--)
    153   {
    154     s+=pSLength(b->buckets[i],0);
     181  for (i = MAX_BUCKET; i >= 0; i--)
     182  {
     183    s += pSLength (b->buckets[i], 0);
    155184  }
    156185  return s;
     
    158187#endif
    159188
    160 int QlogSize(number n)
    161 {
    162     if (SR_HDL(n) & SR_INT)
    163     {
    164        long i=SR_TO_INT(n);
    165        if (i==0) return 0;
    166 
    167        unsigned long v;
    168        v=(i>=0)?i:-i;
    169        int r = 0;
    170 
    171        while (v >>= 1)
    172        {
    173         r++;
    174        }
    175        return r+1;
    176     }
    177     //assume denominator is 0
    178     return mpz_sizeinbase(n->z,2);
     189int
     190QlogSize (number n)
     191{
     192  if (SR_HDL (n) & SR_INT)
     193  {
     194    long i = SR_TO_INT (n);
     195    if (i == 0)
     196      return 0;
     197
     198    unsigned long v;
     199    v = (i >= 0) ? i : -i;
     200    int r = 0;
     201
     202    while (v >>= 1)
     203    {
     204      r++;
     205    }
     206    return r + 1;
     207  }
     208  //assume denominator is 0
     209  return mpz_sizeinbase (n->z, 2);
    179210}
    180211
    181212#ifdef LEN_VAR3
    182 static inline wlen_type pSLength(poly p,int l)
     213static inline wlen_type
     214pSLength (poly p, int l)
    183215{
    184216  wlen_type c;
    185   number coef=pGetCoeff(p);
    186   if (rField_is_Q(currRing))
    187   {
    188     c=QlogSize(coef);
     217  number coef = pGetCoeff (p);
     218  if (rField_is_Q (currRing))
     219  {
     220    c = QlogSize (coef);
    189221  }
    190222  else
    191     c=nSize(coef);
     223    c = nSize (coef);
    192224  if (!(TEST_V_COEFSTRAT))
    193       return (wlen_type)c*(wlen_type)l /*pLength(p)*/;
     225    return (wlen_type) c *(wlen_type) l /*pLength(p) */ ;
    194226  else
    195227  {
    196     wlen_type res=l;
    197     res*=c;
    198     res*=c;
     228    wlen_type res = l;
     229    res *= c;
     230    res *= c;
    199231    return res;
    200232  }
    201233}
     234
    202235//! TODO CoefBuckets bercksichtigen
    203 wlen_type kSBucketLength(kBucket* b, poly lm=NULL)
    204 {
    205   int s=0;
     236wlen_type
     237kSBucketLength (kBucket * b, poly lm = NULL)
     238{
     239  int s = 0;
    206240  wlen_type c;
    207241  number coef;
    208   if(lm==NULL)
    209     coef=pGetCoeff(kBucketGetLm(b));
    210     //c=nSize(pGetCoeff(kBucketGetLm(b)));
     242  if (lm == NULL)
     243    coef = pGetCoeff (kBucketGetLm (b));
     244  //c=nSize(pGetCoeff(kBucketGetLm(b)));
    211245  else
    212     coef=pGetCoeff(lm);
    213     //c=nSize(pGetCoeff(lm));
    214   if (rField_is_Q(currRing))
    215   {
    216     c=QlogSize(coef);
     246    coef = pGetCoeff (lm);
     247  //c=nSize(pGetCoeff(lm));
     248  if (rField_is_Q (currRing))
     249  {
     250    c = QlogSize (coef);
    217251  }
    218252  else
    219     c=nSize(coef);
     253    c = nSize (coef);
    220254
    221255  int i;
    222   for (i=b->buckets_used;i>=0;i--)
    223   {
    224     assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL));
    225     s+=b->buckets_length[i] /*pLength(b->buckets[i])*/;
    226   }
    227   #ifdef HAVE_COEF_BUCKETS
    228   assume(b->buckets[0]==kBucketGetLm(b));
    229   if (b->coef[0]!=NULL)
    230   {
    231     if (rField_is_Q(currRing))
    232     {
    233       int modifier=QlogSize(pGetCoeff(b->coef[0]));
    234       c+=modifier;
     256  for (i = b->buckets_used; i >= 0; i--)
     257  {
     258    assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
     259    s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
     260  }
     261#ifdef HAVE_COEF_BUCKETS
     262  assume (b->buckets[0] == kBucketGetLm (b));
     263  if (b->coef[0] != NULL)
     264  {
     265    if (rField_is_Q (currRing))
     266    {
     267      int modifier = QlogSize (pGetCoeff (b->coef[0]));
     268      c += modifier;
    235269    }
    236270    else
    237271    {
    238       int modifier=nSize(pGetCoeff(b->coef[0]));
    239       c*=modifier;
    240     }
    241   }
    242   #endif
     272      int modifier = nSize (pGetCoeff (b->coef[0]));
     273      c *= modifier;
     274    }
     275  }
     276#endif
    243277  if (!(TEST_V_COEFSTRAT))
    244278  {
    245     return s*c;
     279    return s * c;
    246280  }
    247281  else
    248282  {
    249     wlen_type res=s;
    250     res*=c;
    251     res*=c;
     283    wlen_type res = s;
     284    res *= c;
     285    res *= c;
    252286    return res;
    253287  }
     
    255289#endif
    256290#ifdef LEN_VAR5
    257 static inline wlen_type pSLength(poly p,int l)
     291static inline wlen_type
     292pSLength (poly p, int l)
    258293{
    259294  int c;
    260   number coef=pGetCoeff(p);
    261   if (rField_is_Q(currRing))
    262   {
    263     c=QlogSize(coef);
     295  number coef = pGetCoeff (p);
     296  if (rField_is_Q (currRing))
     297  {
     298    c = QlogSize (coef);
    264299  }
    265300  else
    266     c=nSize(coef);
    267   wlen_type erg=l;
    268   erg*=c;
    269   erg*=c;
     301    c = nSize (coef);
     302  wlen_type erg = l;
     303  erg *= c;
     304  erg *= c;
    270305  //PrintS("lenvar 5");
    271   assume(erg>=0);
    272   return erg; /*pLength(p)*/;
    273 }
     306  assume (erg >= 0);
     307  return erg; /*pLength(p) */ ;
     308}
     309
    274310//! TODO CoefBuckets bercksichtigen
    275 wlen_type kSBucketLength(kBucket* b, poly lm=NULL)
    276 {
    277   wlen_type s=0;
     311wlen_type
     312kSBucketLength (kBucket * b, poly lm = NULL)
     313{
     314  wlen_type s = 0;
    278315  int c;
    279316  number coef;
    280   if(lm==NULL)
    281     coef=pGetCoeff(kBucketGetLm(b));
    282     //c=nSize(pGetCoeff(kBucketGetLm(b)));
     317  if (lm == NULL)
     318    coef = pGetCoeff (kBucketGetLm (b));
     319  //c=nSize(pGetCoeff(kBucketGetLm(b)));
    283320  else
    284     coef=pGetCoeff(lm);
    285     //c=nSize(pGetCoeff(lm));
    286   if (rField_is_Q(currRing))
    287   {
    288     c=QlogSize(coef);
     321    coef = pGetCoeff (lm);
     322  //c=nSize(pGetCoeff(lm));
     323  if (rField_is_Q (currRing))
     324  {
     325    c = QlogSize (coef);
    289326  }
    290327  else
    291     c=nSize(coef);
     328    c = nSize (coef);
    292329
    293330  int i;
    294   for (i=b->buckets_used;i>=0;i--)
    295   {
    296     assume((b->buckets_length[i]==0)||(b->buckets[i]!=NULL));
    297     s+=b->buckets_length[i] /*pLength(b->buckets[i])*/;
    298   }
    299   #ifdef HAVE_COEF_BUCKETS
    300   assume(b->buckets[0]==kBucketGetLm(b));
    301   if (b->coef[0]!=NULL)
    302   {
    303     if (rField_is_Q(currRing))
    304     {
    305       int modifier=QlogSize(pGetCoeff(b->coef[0]));
    306       c+=modifier;
     331  for (i = b->buckets_used; i >= 0; i--)
     332  {
     333    assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
     334    s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
     335  }
     336#ifdef HAVE_COEF_BUCKETS
     337  assume (b->buckets[0] == kBucketGetLm (b));
     338  if (b->coef[0] != NULL)
     339  {
     340    if (rField_is_Q (currRing))
     341    {
     342      int modifier = QlogSize (pGetCoeff (b->coef[0]));
     343      c += modifier;
    307344    }
    308345    else
    309346    {
    310       int modifier=nSize(pGetCoeff(b->coef[0]));
    311       c*=modifier;}
    312     }
    313   #endif
    314   wlen_type erg=s;
    315   erg*=c;
    316   erg*=c;
     347      int modifier = nSize (pGetCoeff (b->coef[0]));
     348      c *= modifier;
     349    }
     350  }
     351#endif
     352  wlen_type erg = s;
     353  erg *= c;
     354  erg *= c;
    317355  return erg;
    318356}
     
    321359#ifdef LEN_VAR4
    322360// 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.)
    323 int pSLength(poly p, int l)
    324 {
    325   int s=1;
    326   int c=nSize(pGetCoeff(p));
    327   pIter(p);
    328   while (p!=NULL) { s+=nSize(pGetCoeff(p));pIter(p); }
    329   return s*c;
    330 }
    331 int kSBucketLength(kBucket* b)
    332 {
    333   int s=1;
    334   int c=nSize(pGetCoeff(kBucketGetLm(b)));
     361int
     362pSLength (poly p, int l)
     363{
     364  int s = 1;
     365  int c = nSize (pGetCoeff (p));
     366  pIter (p);
     367  while (p != NULL)
     368  {
     369    s += nSize (pGetCoeff (p));
     370    pIter (p);
     371  }
     372  return s * c;
     373}
     374
     375int
     376kSBucketLength (kBucket * b)
     377{
     378  int s = 1;
     379  int c = nSize (pGetCoeff (kBucketGetLm (b)));
    335380  int i;
    336   for (i=MAX_BUCKET;i>0;i--)
    337   {
    338     if(b->buckets[i]==NULL) continue;
    339     s+=pSLength(b->buckets[i],0);
    340   }
    341   return s*c;
     381  for (i = MAX_BUCKET; i > 0; i--)
     382  {
     383    if (b->buckets[i] == NULL)
     384      continue;
     385    s += pSLength (b->buckets[i], 0);
     386  }
     387  return s * c;
    342388}
    343389#endif
    344390//BUG/TODO this stuff will fail on internal Schreyer orderings
    345 static BOOLEAN elength_is_normal_length(poly p, slimgb_alg* c)
    346 {
    347     ring r=c->r;
    348     if (p_GetComp(p,r)!=0) return FALSE;
    349     if (c->lastDpBlockStart<=pVariables)
    350     {
    351         int i;
    352         for(i=1;i<c->lastDpBlockStart;i++)
    353         {
    354             if (p_GetExp(p,i,r)!=0)
    355             {
    356                 break;
    357             }
    358         }
    359         if (i>=c->lastDpBlockStart) {
    360         //wrp(p);
    361         //PrintS("\n");
    362         return TRUE;
    363         }
    364         else return FALSE;
     391static BOOLEAN
     392elength_is_normal_length (poly p, slimgb_alg * c)
     393{
     394  ring r = c->r;
     395  if (p_GetComp (p, r) != 0)
     396    return FALSE;
     397  if (c->lastDpBlockStart <= pVariables)
     398  {
     399    int i;
     400    for (i = 1; i < c->lastDpBlockStart; i++)
     401    {
     402      if (p_GetExp (p, i, r) != 0)
     403      {
     404        break;
     405      }
     406    }
     407    if (i >= c->lastDpBlockStart)
     408    {
     409      //wrp(p);
     410      //PrintS("\n");
     411      return TRUE;
    365412    }
    366413    else
     414      return FALSE;
     415  }
     416  else
    367417    return FALSE;
    368418}
    369419
    370 static BOOLEAN lies_in_last_dp_block(poly p, slimgb_alg* c)
    371 {
    372     ring r=c->r;
    373     if (p_GetComp(p,r)!=0) return FALSE;
    374     if (c->lastDpBlockStart<=pVariables)
    375     {
    376         int i;
    377         for(i=1;i<c->lastDpBlockStart;i++)
    378         {
    379             if (p_GetExp(p,i,r)!=0)
    380             {
    381                 break;
    382             }
    383         }
    384         if (i>=c->lastDpBlockStart) {
    385         //wrp(p);
    386         //PrintS("\n");
    387         return TRUE;
    388         }
    389         else return FALSE;
     420static BOOLEAN
     421lies_in_last_dp_block (poly p, slimgb_alg * c)
     422{
     423  ring r = c->r;
     424  if (p_GetComp (p, r) != 0)
     425    return FALSE;
     426  if (c->lastDpBlockStart <= pVariables)
     427  {
     428    int i;
     429    for (i = 1; i < c->lastDpBlockStart; i++)
     430    {
     431      if (p_GetExp (p, i, r) != 0)
     432      {
     433        break;
     434      }
     435    }
     436    if (i >= c->lastDpBlockStart)
     437    {
     438      //wrp(p);
     439      //PrintS("\n");
     440      return TRUE;
    390441    }
    391442    else
     443      return FALSE;
     444  }
     445  else
    392446    return FALSE;
    393447}
    394448
    395 static int get_last_dp_block_start(ring r)
    396 {
    397     //ring r=c->r;
    398     int last_block;
    399 
    400     if (rRing_has_CompLastBlock(r))
    401     {
    402         last_block=rBlocks(r) - 3;
    403     }
    404     else
    405     {last_block=rBlocks(r)-2;}
    406     assume(last_block>=0);
    407     if (r->order[last_block]==ringorder_dp)
    408         return r->block0[last_block];
    409     return pVariables+1;
    410 }
    411 
    412 static wlen_type do_pELength(poly p, slimgb_alg* c, int dlm=-1)
    413 {
    414   if(p==NULL) return 0;
    415   wlen_type s=0;
    416   poly pi=p;
    417   if(dlm<0)
    418   {
    419     dlm=c->pTotaldegree(p);
    420     s=1;
    421     pi=p->next;
    422   }
    423 
    424   while(pi)
    425   {
    426     int d=c->pTotaldegree(pi);
    427     if(d>dlm)
    428       s+=1+d-dlm;
     449static int
     450get_last_dp_block_start (ring r)
     451{
     452  //ring r=c->r;
     453  int last_block;
     454
     455  if (rRing_has_CompLastBlock (r))
     456  {
     457    last_block = rBlocks (r) - 3;
     458  }
     459  else
     460  {
     461    last_block = rBlocks (r) - 2;
     462  }
     463  assume (last_block >= 0);
     464  if (r->order[last_block] == ringorder_dp)
     465    return r->block0[last_block];
     466  return pVariables + 1;
     467}
     468
     469static wlen_type
     470do_pELength (poly p, slimgb_alg * c, int dlm = -1)
     471{
     472  if (p == NULL)
     473    return 0;
     474  wlen_type s = 0;
     475  poly pi = p;
     476  if (dlm < 0)
     477  {
     478    dlm = c->pTotaldegree (p);
     479    s = 1;
     480    pi = p->next;
     481  }
     482
     483  while (pi)
     484  {
     485    int d = c->pTotaldegree (pi);
     486    if (d > dlm)
     487      s += 1 + d - dlm;
    429488    else
    430489      ++s;
    431     pi=pi->next;
     490    pi = pi->next;
    432491  }
    433492  return s;
    434493}
    435494
    436 wlen_type pELength(poly p, slimgb_alg* c, ring r)
    437 {
    438   if(p==NULL) return 0;
    439   wlen_type s=0;
    440   poly pi=p;
     495wlen_type
     496pELength (poly p, slimgb_alg * c, ring r)
     497{
     498  if (p == NULL)
     499    return 0;
     500  wlen_type s = 0;
     501  poly pi = p;
    441502  int dlm;
    442   dlm=c->pTotaldegree(p);
    443   s=1;
    444   pi=p->next;
    445 
    446   while(pi)
    447   {
    448     int d=c->pTotaldegree(pi);
    449     if(d>dlm)
    450       s+=1+d-dlm;
     503  dlm = c->pTotaldegree (p);
     504  s = 1;
     505  pi = p->next;
     506
     507  while (pi)
     508  {
     509    int d = c->pTotaldegree (pi);
     510    if (d > dlm)
     511      s += 1 + d - dlm;
    451512    else
    452513      ++s;
    453     pi=pi->next;
     514    pi = pi->next;
    454515  }
    455516  return s;
    456517}
    457518
    458 wlen_type kEBucketLength(kBucket* b, poly lm,int sugar,slimgb_alg* ca)
    459 {
    460   wlen_type s=0;
    461   if(lm==NULL)
    462   {
    463     lm=kBucketGetLm(b);
    464   }
    465   if(lm==NULL) return 0;
    466   if(elength_is_normal_length(lm,ca))
    467   {
    468     return bucket_guess(b);
    469   }
    470   int d=ca->pTotaldegree(lm);
    471   #if 0
    472   assume(sugar>=d);
    473   s=1+(bucket_guess(b)-1)*(sugar-d+1);
     519wlen_type
     520kEBucketLength (kBucket * b, poly lm, int sugar, slimgb_alg * ca)
     521{
     522  wlen_type s = 0;
     523  if (lm == NULL)
     524  {
     525    lm = kBucketGetLm (b);
     526  }
     527  if (lm == NULL)
     528    return 0;
     529  if (elength_is_normal_length (lm, ca))
     530  {
     531    return bucket_guess (b);
     532  }
     533  int d = ca->pTotaldegree (lm);
     534#if 0
     535  assume (sugar >= d);
     536  s = 1 + (bucket_guess (b) - 1) * (sugar - d + 1);
    474537  return s;
    475   #else
     538#else
    476539
    477540  //int d=pTotaldegree(lm,ca->r);
    478541  int i;
    479   for (i=b->buckets_used;i>=0;i--)
    480   {
    481     if(b->buckets[i]==NULL) continue;
    482 
    483     if ((ca->pTotaldegree(b->buckets[i])<=d) &&(elength_is_normal_length(b->buckets[i],ca)))
    484     {
    485         s+=b->buckets_length[i];
     542  for (i = b->buckets_used; i >= 0; i--)
     543  {
     544    if (b->buckets[i] == NULL)
     545      continue;
     546
     547    if ((ca->pTotaldegree (b->buckets[i]) <= d)
     548        && (elength_is_normal_length (b->buckets[i], ca)))
     549    {
     550      s += b->buckets_length[i];
    486551    }
    487552    else
    488553    {
    489     s+=do_pELength(b->buckets[i],ca,d);
     554      s += do_pELength (b->buckets[i], ca, d);
    490555    }
    491556  }
    492557  return s;
    493   #endif
    494 }
    495 
    496 static inline int pELength(poly p, slimgb_alg* c,int l)
    497 {
    498   if (p==NULL) return 0;
    499   if ((l>0) &&(elength_is_normal_length(p,c)))
     558#endif
     559}
     560
     561static inline int
     562pELength (poly p, slimgb_alg * c, int l)
     563{
     564  if (p == NULL)
     565    return 0;
     566  if ((l > 0) && (elength_is_normal_length (p, c)))
    500567    return l;
    501   return do_pELength(p,c);
    502 }
    503 
    504 static inline wlen_type pQuality(poly p, slimgb_alg* c, int l=-1)
    505 {
    506   if(l<0)
    507     l=pLength(p);
    508   if(c->isDifficultField) {
    509     if(c->eliminationProblem)
     568  return do_pELength (p, c);
     569}
     570
     571static inline wlen_type
     572pQuality (poly p, slimgb_alg * c, int l = -1)
     573{
     574  if (l < 0)
     575    l = pLength (p);
     576  if (c->isDifficultField)
     577  {
     578    if (c->eliminationProblem)
    510579    {
    511580      wlen_type cs;
    512       number coef=pGetCoeff(p);
    513       if (rField_is_Q(currRing))
    514       {
    515          cs=QlogSize(coef);
     581      number coef = pGetCoeff (p);
     582      if (rField_is_Q (currRing))
     583      {
     584        cs = QlogSize (coef);
    516585      }
    517586      else
    518         cs=nSize(coef);
    519      wlen_type erg=cs;
    520      if(TEST_V_COEFSTRAT)
    521         erg*=cs;
    522      //erg*=cs;//for quadratic
    523      erg*=pELength(p,c,l);
    524     //FIXME: not quadratic coeff size
     587        cs = nSize (coef);
     588      wlen_type erg = cs;
     589      if (TEST_V_COEFSTRAT)
     590        erg *= cs;
     591      //erg*=cs;//for quadratic
     592      erg *= pELength (p, c, l);
     593      //FIXME: not quadratic coeff size
    525594      //return cs*pELength(p,c,l);
    526595      return erg;
    527596    }
    528597    //PrintS("I am here");
    529     wlen_type r=pSLength(p,l);
    530     assume(r>=0);
     598    wlen_type r = pSLength (p, l);
     599    assume (r >= 0);
    531600    return r;
    532601  }
    533   if(c->eliminationProblem) return pELength(p,c,l);
     602  if (c->eliminationProblem)
     603    return pELength (p, c, l);
    534604  return l;
    535605}
    536606
    537 static inline int pTotaldegree_full(poly p)
    538 {
    539   int r=0;
    540   while(p)
    541   {
    542     int d=pTotaldegree(p);
    543     r=si_max(r,d);
    544     pIter(p);
     607static inline int
     608pTotaldegree_full (poly p)
     609{
     610  int r = 0;
     611  while (p)
     612  {
     613    int d = pTotaldegree (p);
     614    r = si_max (r, d);
     615    pIter (p);
    545616  }
    546617  return r;
    547618}
    548619
    549 wlen_type red_object::guess_quality(slimgb_alg* c)
    550 {
    551     //works at the moment only for lenvar 1, because in different
    552     //case, you have to look on coefs
    553     wlen_type s=0;
    554     if (c->isDifficultField)
    555     {
    556       //s=kSBucketLength(bucket,this->p);
    557       if(c->eliminationProblem)
    558       {
    559     wlen_type cs;
    560     number coef;
    561 
    562     coef=pGetCoeff(kBucketGetLm(bucket));
    563     //c=nSize(pGetCoeff(kBucketGetLm(b)));
    564 
    565     //c=nSize(pGetCoeff(lm));
    566     if (rField_is_Q(currRing))
    567     {
    568       cs=QlogSize(coef);
    569     }
     620wlen_type
     621red_object::guess_quality (slimgb_alg * c)
     622{
     623  //works at the moment only for lenvar 1, because in different
     624  //case, you have to look on coefs
     625  wlen_type s = 0;
     626  if (c->isDifficultField)
     627  {
     628    //s=kSBucketLength(bucket,this->p);
     629    if (c->eliminationProblem)
     630    {
     631      wlen_type cs;
     632      number coef;
     633
     634      coef = pGetCoeff (kBucketGetLm (bucket));
     635      //c=nSize(pGetCoeff(kBucketGetLm(b)));
     636
     637      //c=nSize(pGetCoeff(lm));
     638      if (rField_is_Q (currRing))
     639      {
     640        cs = QlogSize (coef);
     641      }
     642      else
     643        cs = nSize (coef);
     644#ifdef HAVE_COEF_BUCKETS
     645      if (bucket->coef[0] != NULL)
     646      {
     647        if (rField_is_Q (currRing))
     648        {
     649          int modifier = QlogSize (pGetCoeff (bucket->coef[0]));
     650          cs += modifier;
     651        }
     652        else
     653        {
     654          int modifier = nSize (pGetCoeff (bucket->coef[0]));
     655          cs *= modifier;
     656        }
     657      }
     658#endif
     659      //FIXME:not quadratic
     660      wlen_type erg = kEBucketLength (this->bucket, this->p, this->sugar, c);
     661      //erg*=cs;//for quadratic
     662      erg *= cs;
     663      if (TEST_V_COEFSTRAT)
     664        erg *= cs;
     665      //return cs*kEBucketLength(this->bucket,this->p,c);
     666      return erg;
     667    }
     668    s = kSBucketLength (bucket, NULL);
     669  }
     670  else
     671  {
     672    if (c->eliminationProblem)
     673      //if (false)
     674      s = kEBucketLength (this->bucket, this->p, this->sugar, c);
    570675    else
    571       cs=nSize(coef);
    572     #ifdef HAVE_COEF_BUCKETS
    573     if (bucket->coef[0]!=NULL)
    574     {
    575       if (rField_is_Q(currRing))
    576       {
    577         int modifier=QlogSize(pGetCoeff(bucket->coef[0]));
    578         cs+=modifier;
    579       }
    580       else
    581       {
    582         int modifier=nSize(pGetCoeff(bucket->coef[0]));
    583         cs*=modifier;}
    584     }
    585     #endif
    586     //FIXME:not quadratic
    587     wlen_type erg=kEBucketLength(this->bucket,this->p,this->sugar,c);
    588     //erg*=cs;//for quadratic
    589     erg*=cs;
    590     if (TEST_V_COEFSTRAT)
    591         erg*=cs;
    592     //return cs*kEBucketLength(this->bucket,this->p,c);
    593     return erg;
    594       }
    595       s=kSBucketLength(bucket,NULL);
    596     }
    597     else
    598     {
    599       if(c->eliminationProblem)
    600   //if (false)
    601   s=kEBucketLength(this->bucket,this->p,this->sugar,c);
    602       else s=bucket_guess(bucket);
    603     }
    604     return s;
    605 }
    606 
    607 #if 0 //currently unused
    608 static void finalize_reduction_step(reduction_step* r)
     676      s = bucket_guess (bucket);
     677  }
     678  return s;
     679}
     680
     681#if 0                           //currently unused
     682static void
     683finalize_reduction_step (reduction_step * r)
    609684{
    610685  delete r;
    611686}
    612687#endif
    613 #if 0 //currently unused
    614 static int LObject_better_gen(const void* ap, const void* bp)
    615 {
    616   LObject* a=*(LObject**)ap;
    617   LObject* b=*(LObject**)bp;
    618   return(pLmCmp(a->p,b->p));
    619 }
    620 #endif
    621 static int red_object_better_gen(const void* ap, const void* bp)
    622 {
    623   return(pLmCmp(((red_object*) ap)->p,((red_object*) bp)->p));
    624 }
    625 
    626 #if 0 //currently unused
    627 static int pLmCmp_func_inverted(const void* ap1, const void* ap2)
    628 {
    629   poly p1,p2;
    630   p1=*((poly*) ap1);
    631   p2=*((poly*)ap2);
    632   return -pLmCmp(p1,p2);
    633 }
    634 #endif
    635 
    636 int tgb_pair_better_gen2(const void* ap,const void* bp)
    637 {
    638   return(-tgb_pair_better_gen(ap,bp));
    639 }
    640 int kFindDivisibleByInS_easy(kStrategy strat,const red_object & obj)
     688#if 0                           //currently unused
     689static int
     690LObject_better_gen (const void *ap, const void *bp)
     691{
     692  LObject *a = *(LObject **) ap;
     693  LObject *b = *(LObject **) bp;
     694  return (pLmCmp (a->p, b->p));
     695}
     696#endif
     697static int
     698red_object_better_gen (const void *ap, const void *bp)
     699{
     700  return (pLmCmp (((red_object *) ap)->p, ((red_object *) bp)->p));
     701}
     702
     703#if 0                           //currently unused
     704static int
     705pLmCmp_func_inverted (const void *ap1, const void *ap2)
     706{
     707  poly p1, p2;
     708  p1 = *((poly *) ap1);
     709  p2 = *((poly *) ap2);
     710  return -pLmCmp (p1, p2);
     711}
     712#endif
     713
     714int
     715tgb_pair_better_gen2 (const void *ap, const void *bp)
     716{
     717  return (-tgb_pair_better_gen (ap, bp));
     718}
     719
     720int
     721kFindDivisibleByInS_easy (kStrategy strat, const red_object & obj)
    641722{
    642723  int i;
    643   long not_sev=~obj.sev;
    644   poly p=obj.p;
    645   for(i=0;i<=strat->sl;i++)
    646   {
    647     if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev))
     724  long not_sev = ~obj.sev;
     725  poly p = obj.p;
     726  for (i = 0; i <= strat->sl; i++)
     727  {
     728    if (pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
    648729      return i;
    649730  }
    650731  return -1;
    651732}
    652 int kFindDivisibleByInS_easy(kStrategy strat,poly p, long sev)
     733
     734int
     735kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev)
    653736{
    654737  int i;
    655   long not_sev=~sev;
    656   for(i=0;i<=strat->sl;i++)
    657   {
    658     if (pLmShortDivisibleBy(strat->S[i],strat->sevS[i],p,not_sev))
     738  long not_sev = ~sev;
     739  for (i = 0; i <= strat->sl; i++)
     740  {
     741    if (pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
    659742      return i;
    660743  }
    661744  return -1;
    662745}
    663 static int posInPairs (sorted_pair_node**  p, int pn, sorted_pair_node* qe,slimgb_alg* c,int an=0)
    664 {
    665   if(pn==0) return 0;
    666 
    667   int length=pn-1;
     746
     747static int
     748posInPairs (sorted_pair_node ** p, int pn, sorted_pair_node * qe,
     749            slimgb_alg * c, int an = 0)
     750{
     751  if (pn == 0)
     752    return 0;
     753
     754  int length = pn - 1;
    668755  int i;
    669756  //int an = 0;
    670   int en= length;
    671 
    672   if (pair_better(qe,p[en],c))
    673     return length+1;
    674 
    675   while(1)
    676     {
    677       //if (an >= en-1)
    678       if(en-1<=an)
    679       {
    680         if (pair_better(p[an],qe,c)) return an;
    681         return en;
    682       }
    683       i=(an+en) / 2;
    684         if (pair_better(p[i],qe,c))
    685           en=i;
    686       else an=i;
    687     }
    688 }
    689 
    690 static BOOLEAN  ascending(int* i,int top)
    691 {
    692   if(top<1) return TRUE;
    693   if(i[top]<i[top-1]) return FALSE;
    694   return ascending(i,top-1);
    695 }
    696 
    697 sorted_pair_node**  spn_merge(sorted_pair_node** p, int pn,sorted_pair_node **q, int qn,slimgb_alg* c)
     757  int en = length;
     758
     759  if (pair_better (qe, p[en], c))
     760    return length + 1;
     761
     762  while (1)
     763  {
     764    //if (an >= en-1)
     765    if (en - 1 <= an)
     766    {
     767      if (pair_better (p[an], qe, c))
     768        return an;
     769      return en;
     770    }
     771    i = (an + en) / 2;
     772    if (pair_better (p[i], qe, c))
     773      en = i;
     774    else
     775      an = i;
     776  }
     777}
     778
     779static BOOLEAN
     780ascending (int *i, int top)
     781{
     782  if (top < 1)
     783    return TRUE;
     784  if (i[top] < i[top - 1])
     785    return FALSE;
     786  return ascending (i, top - 1);
     787}
     788
     789sorted_pair_node **
     790spn_merge (sorted_pair_node ** p, int pn, sorted_pair_node ** q, int qn,
     791           slimgb_alg * c)
    698792{
    699793  int i;
    700   int* a= (int*) omalloc(qn*sizeof(int));
     794  int *a = (int *) omalloc (qn * sizeof (int));
    701795//   int mc;
    702796//   PrintS("Debug\n");
     
    712806//     PrintS("\n");
    713807// }
    714   int lastpos=0;
    715   for(i=0;i<qn;i++)
    716   {
    717     lastpos=posInPairs(p,pn,q[i],c, si_max(lastpos-1,0));
     808  int lastpos = 0;
     809  for (i = 0; i < qn; i++)
     810  {
     811    lastpos = posInPairs (p, pn, q[i], c, si_max (lastpos - 1, 0));
    718812    //   cout<<lastpos<<"\n";
    719     a[i]=lastpos;
    720   }
    721   if((pn+qn)>c->max_pairs)
    722   {
    723     p=(sorted_pair_node**) omrealloc(p,2*(pn+qn)*sizeof(sorted_pair_node*));
    724     c->max_pairs=2*(pn+qn);
    725   }
    726   for(i=qn-1;i>=0;i--)
     813    a[i] = lastpos;
     814  }
     815  if ((pn + qn) > c->max_pairs)
     816  {
     817    p =
     818      (sorted_pair_node **) omrealloc (p,
     819                                       2 * (pn +
     820                                            qn) *
     821                                       sizeof (sorted_pair_node *));
     822    c->max_pairs = 2 * (pn + qn);
     823  }
     824  for (i = qn - 1; i >= 0; i--)
    727825  {
    728826    size_t size;
    729     if(qn-1>i)
    730       size=(a[i+1]-a[i])*sizeof(sorted_pair_node*);
     827    if (qn - 1 > i)
     828      size = (a[i + 1] - a[i]) * sizeof (sorted_pair_node *);
    731829    else
    732       size=(pn-a[i])*sizeof(sorted_pair_node*); //as indices begin with 0
    733     memmove (p+a[i]+(1+i), p+a[i], size);
    734     p[a[i]+i]=q[i];
    735   }
    736   omfree(a);
     830      size = (pn - a[i]) * sizeof (sorted_pair_node *); //as indices begin with 0
     831    memmove (p + a[i] + (1 + i), p + a[i], size);
     832    p[a[i] + i] = q[i];
     833  }
     834  omfree (a);
    737835  return p;
    738836}
    739837
    740 static BOOLEAN trivial_syzygie(int pos1,int pos2,poly bound,slimgb_alg* c)
    741 {
    742   poly p1=c->S->m[pos1];
    743   poly p2=c->S->m[pos2];
    744 
    745   if (pGetComp(p1) > 0 || pGetComp(p2) > 0)
     838static BOOLEAN
     839trivial_syzygie (int pos1, int pos2, poly bound, slimgb_alg * c)
     840{
     841  poly p1 = c->S->m[pos1];
     842  poly p2 = c->S->m[pos2];
     843
     844  if (pGetComp (p1) > 0 || pGetComp (p2) > 0)
    746845    return FALSE;
    747846  int i = 1;
    748   poly m=NULL;
    749   poly gcd1=c->gcd_of_terms[pos1];
    750   poly gcd2=c->gcd_of_terms[pos2];
    751 
    752   if((gcd1!=NULL) && (gcd2!=NULL))
    753   {
    754     gcd1->next=gcd2; //may ordered incorrect
    755     m=gcd_of_terms(gcd1,c->r);
    756     gcd1->next=NULL;
    757   }
    758   if (m==NULL)
    759   {
    760      loop
    761       {
    762   if (pGetExp(p1, i)+ pGetExp(p2, i) > pGetExp(bound,i))   return FALSE;
    763   if (i == pVariables)
    764   {
    765     //PrintS("trivial");
     847  poly m = NULL;
     848  poly gcd1 = c->gcd_of_terms[pos1];
     849  poly gcd2 = c->gcd_of_terms[pos2];
     850
     851  if ((gcd1 != NULL) && (gcd2 != NULL))
     852  {
     853    gcd1->next = gcd2;          //may ordered incorrect
     854    m = gcd_of_terms (gcd1, c->r);
     855    gcd1->next = NULL;
     856  }
     857  if (m == NULL)
     858  {
     859    loop
     860    {
     861      if (pGetExp (p1, i) + pGetExp (p2, i) > pGetExp (bound, i))
     862        return FALSE;
     863      if (i == pVariables)
     864      {
     865        //PrintS("trivial");
     866        return TRUE;
     867      }
     868      i++;
     869    }
     870  }
     871  else
     872  {
     873    loop
     874    {
     875      if (pGetExp (p1, i) - pGetExp (m, i) + pGetExp (p2, i) >
     876          pGetExp (bound, i))
     877      {
     878        pDelete (&m);
     879        return FALSE;
     880      }
     881      if (i == pVariables)
     882      {
     883        pDelete (&m);
     884        //PrintS("trivial");
     885        return TRUE;
     886      }
     887      i++;
     888    }
     889  }
     890}
     891
     892//! returns position sets w as weight
     893int
     894find_best (red_object * r, int l, int u, wlen_type & w, slimgb_alg * c)
     895{
     896  int best = l;
     897  int i;
     898  w = r[l].guess_quality (c);
     899  for (i = l + 1; i <= u; i++)
     900  {
     901    wlen_type w2 = r[i].guess_quality (c);
     902    if (w2 < w)
     903    {
     904      w = w2;
     905      best = i;
     906    }
     907  }
     908  return best;
     909}
     910
     911void
     912red_object::canonicalize ()
     913{
     914  kBucketCanonicalize (bucket);
     915}
     916
     917BOOLEAN
     918good_has_t_rep (int i, int j, slimgb_alg * c)
     919{
     920  assume (i >= 0);
     921  assume (j >= 0);
     922  if (has_t_rep (i, j, c))
    766923    return TRUE;
    767   }
    768   i++;
    769       }
    770   }
    771   else
    772   {
    773     loop
    774       {
    775   if (pGetExp(p1, i)-pGetExp(m,i) + pGetExp(p2, i) > pGetExp(bound,i))  {
    776     pDelete(&m);
    777     return FALSE;}
    778   if (i == pVariables)
    779   {
    780     pDelete(&m);
    781     //PrintS("trivial");
    782     return TRUE;
    783   }
    784   i++;
    785       }
    786   }
    787 }
    788 
    789 //! returns position sets w as weight
    790 int find_best(red_object* r,int l, int u, wlen_type &w, slimgb_alg* c)
    791 {
    792   int best=l;
     924  //poly lm=pOne();
     925  assume (c->tmp_lm != NULL);
     926  poly lm = c->tmp_lm;
     927
     928  pLcm (c->S->m[i], c->S->m[j], lm);
     929  pSetm (lm);
     930  assume (lm != NULL);
     931  //int deciding_deg= pTotaldegree(lm);
     932  int *i_con = make_connections (i, j, lm, c);
     933  //p_Delete(&lm,c->r);
     934
     935  for (int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
     936  {
     937    if (i_con[n] == j)
     938    {
     939      now_t_rep (i, j, c);
     940      omfree (i_con);
     941      return TRUE;
     942    }
     943  }
     944  omfree (i_con);
     945
     946  return FALSE;
     947}
     948
     949BOOLEAN
     950lenS_correct (kStrategy strat)
     951{
    793952  int i;
    794   w=r[l].guess_quality(c);
    795   for(i=l+1;i<=u;i++)
    796   {
    797     wlen_type w2=r[i].guess_quality(c);
    798     if(w2<w)
    799     {
    800       w=w2;
    801       best=i;
    802     }
    803   }
    804  return best;
    805 }
    806 
    807 void red_object::canonicalize()
    808 {
    809   kBucketCanonicalize(bucket);
    810 }
    811 
    812 BOOLEAN good_has_t_rep(int i, int j,slimgb_alg* c)
    813 {
    814   assume(i>=0);
    815     assume(j>=0);
    816   if (has_t_rep(i,j,c)) return TRUE;
    817   //poly lm=pOne();
    818   assume (c->tmp_lm!=NULL);
    819   poly lm=c->tmp_lm;
    820 
    821   pLcm(c->S->m[i], c->S->m[j], lm);
    822   pSetm(lm);
    823   assume(lm!=NULL);
    824   //int deciding_deg= pTotaldegree(lm);
    825   int* i_con =make_connections(i,j,lm,c);
    826   //p_Delete(&lm,c->r);
    827 
    828   for (int n=0;((n<c->n) && (i_con[n]>=0));n++)
    829   {
    830     if (i_con[n]==j)
    831     {
    832       now_t_rep(i,j,c);
    833       omfree(i_con);
    834       return TRUE;
    835     }
    836   }
    837   omfree(i_con);
    838 
    839   return FALSE;
    840 }
    841 BOOLEAN lenS_correct(kStrategy strat)
    842 {
    843   int i;
    844   for(i=0;i<=strat->sl;i++)
    845   {
    846     if (strat->lenS[i]!=pLength(strat->S[i]))
     953  for (i = 0; i <= strat->sl; i++)
     954  {
     955    if (strat->lenS[i] != pLength (strat->S[i]))
    847956      return FALSE;
    848957  }
     
    851960
    852961
    853 static void cleanS(kStrategy strat, slimgb_alg* c)
    854 {
    855   int i=0;
     962static void
     963cleanS (kStrategy strat, slimgb_alg * c)
     964{
     965  int i = 0;
    856966  LObject P;
    857   while(i<=strat->sl)
    858   {
    859     P.p=strat->S[i];
    860     P.sev=strat->sevS[i];
     967  while (i <= strat->sl)
     968  {
     969    P.p = strat->S[i];
     970    P.sev = strat->sevS[i];
    861971    //int dummy=strat->sl;
    862972    //if(kFindDivisibleByInS(strat,&dummy,&P)!=i)
    863     if (kFindDivisibleByInS_easy(strat,P.p,P.sev)!=i)
    864     {
    865       deleteInS(i,strat);
     973    if (kFindDivisibleByInS_easy (strat, P.p, P.sev) != i)
     974    {
     975      deleteInS (i, strat);
    866976      //remember destroying poly
    867       BOOLEAN found=FALSE;
     977      BOOLEAN found = FALSE;
    868978      int j;
    869       for(j=0;j<c->n;j++)
    870       {
    871         if(c->S->m[j]==P.p)
    872         {
    873           found=TRUE;
    874           break;
    875         }
     979      for (j = 0; j < c->n; j++)
     980      {
     981        if (c->S->m[j] == P.p)
     982        {
     983          found = TRUE;
     984          break;
     985        }
    876986      }
    877987      if (!found)
    878         pDelete(&P.p);
     988        pDelete (&P.p);
    879989      //remember additional reductors
    880990    }
    881     else i++;
    882   }
    883 }
    884 static int bucket_guess(kBucket* bucket)
    885 {
    886   int sum=0;
     991    else
     992      i++;
     993  }
     994}
     995
     996static int
     997bucket_guess (kBucket * bucket)
     998{
     999  int sum = 0;
    8871000  int i;
    888   for (i=bucket->buckets_used;i>=0;i--)
    889   {
    890     if(bucket->buckets[i])
    891        sum+=bucket->buckets_length[i];
     1001  for (i = bucket->buckets_used; i >= 0; i--)
     1002  {
     1003    if (bucket->buckets[i])
     1004      sum += bucket->buckets_length[i];
    8921005  }
    8931006  return sum;
    8941007}
    8951008
    896 static int add_to_reductors(slimgb_alg* c, poly h, int len, int ecart, BOOLEAN simplified)
     1009static int
     1010add_to_reductors (slimgb_alg * c, poly h, int len, int ecart,
     1011                  BOOLEAN simplified)
    8971012{
    8981013  //inDebug(h);
    899   assume(lenS_correct(c->strat));
    900   assume(len==pLength(h));
     1014  assume (lenS_correct (c->strat));
     1015  assume (len == pLength (h));
    9011016  int i;
    9021017//   if (c->isDifficultField)
     
    9051020//     i=simple_posInS(c->strat,h,len,c->isDifficultField);
    9061021
    907   LObject P; memset(&P,0,sizeof(P));
    908   P.tailRing=c->r;
    909   P.p=h; /*p_Copy(h,c->r);*/
    910   P.ecart=ecart;
    911   P.FDeg=pFDeg(P.p,c->r);
     1022  LObject P;
     1023  memset (&P, 0, sizeof (P));
     1024  P.tailRing = c->r;
     1025  P.p = h;                      /*p_Copy(h,c->r); */
     1026  P.ecart = ecart;
     1027  P.FDeg = pFDeg (P.p, c->r);
    9121028  if (!(simplified))
    9131029  {
    914       if (!rField_is_Zp(c->r))
    915       {
    916         p_Cleardenom(P.p,c->r);
    917         //p_Content(P.p,c->r ); //is a duplicate call, but belongs here
    918 
    919       }
    920       else
    921         pNorm(P.p);
    922     pNormalize(P.p);
    923   }
    924   wlen_type pq=pQuality(h,c,len);
    925   i=simple_posInS(c->strat,h,len,pq);
    926   c->strat->enterS(P,i,c->strat,-1);
    927 
    928   c->strat->lenS[i]=len;
    929   assume(pLength(c->strat->S[i])==c->strat->lenS[i]);
    930   if(c->strat->lenSw!=NULL)
    931     c->strat->lenSw[i]=pq;
     1030    if (!rField_is_Zp (c->r))
     1031    {
     1032      p_Cleardenom (P.p, c->r);
     1033      //p_Content(P.p,c->r ); //is a duplicate call, but belongs here
     1034
     1035    }
     1036    else
     1037      pNorm (P.p);
     1038    pNormalize (P.p);
     1039  }
     1040  wlen_type pq = pQuality (h, c, len);
     1041  i = simple_posInS (c->strat, h, len, pq);
     1042  c->strat->enterS (P, i, c->strat, -1);
     1043
     1044  c->strat->lenS[i] = len;
     1045  assume (pLength (c->strat->S[i]) == c->strat->lenS[i]);
     1046  if (c->strat->lenSw != NULL)
     1047    c->strat->lenSw[i] = pq;
    9321048
    9331049  return i;
    9341050}
    9351051
    936 static void length_one_crit(slimgb_alg* c, int pos, int len)
     1052static void
     1053length_one_crit (slimgb_alg * c, int pos, int len)
    9371054{
    9381055  if (c->nc)
    9391056    return;
    940   if (len==1)
     1057  if (len == 1)
    9411058  {
    9421059    int i;
    943     for ( i=0;i<pos;i++)
    944     {
    945       if (c->lengths[i]==1)
    946         c->states[pos][i]=HASTREP;
    947     }
    948     for ( i=pos+1;i<c->n;i++)
    949     {
    950       if (c->lengths[i]==1)
    951         c->states[i][pos]=HASTREP;
     1060    for (i = 0; i < pos; i++)
     1061    {
     1062      if (c->lengths[i] == 1)
     1063        c->states[pos][i] = HASTREP;
     1064    }
     1065    for (i = pos + 1; i < c->n; i++)
     1066    {
     1067      if (c->lengths[i] == 1)
     1068        c->states[i][pos] = HASTREP;
    9521069    }
    9531070    if (!c->nc)
    954       shorten_tails(c,c->S->m[pos]);
    955   }
    956 }
    957 
    958 static void move_forward_in_S(int old_pos, int new_pos,kStrategy strat)
    959 {
    960   assume(old_pos>=new_pos);
    961   poly p=strat->S[old_pos];
    962   int ecart=strat->ecartS[old_pos];
    963   long sev=strat->sevS[old_pos];
    964   int s_2_r=strat->S_2_R[old_pos];
    965   int length=strat->lenS[old_pos];
    966   assume(length==pLength(strat->S[old_pos]));
     1071      shorten_tails (c, c->S->m[pos]);
     1072  }
     1073}
     1074
     1075static void
     1076move_forward_in_S (int old_pos, int new_pos, kStrategy strat)
     1077{
     1078  assume (old_pos >= new_pos);
     1079  poly p = strat->S[old_pos];
     1080  int ecart = strat->ecartS[old_pos];
     1081  long sev = strat->sevS[old_pos];
     1082  int s_2_r = strat->S_2_R[old_pos];
     1083  int length = strat->lenS[old_pos];
     1084  assume (length == pLength (strat->S[old_pos]));
    9671085  wlen_type length_w;
    968   if(strat->lenSw!=NULL)
    969     length_w=strat->lenSw[old_pos];
     1086  if (strat->lenSw != NULL)
     1087    length_w = strat->lenSw[old_pos];
    9701088  int i;
    971   for (i=old_pos; i>new_pos; i--)
    972   {
    973     strat->S[i] = strat->S[i-1];
    974     strat->ecartS[i] = strat->ecartS[i-1];
    975     strat->sevS[i] = strat->sevS[i-1];
    976     strat->S_2_R[i] = strat->S_2_R[i-1];
    977   }
    978   if (strat->lenS!=NULL)
    979     for (i=old_pos; i>new_pos; i--)
    980       strat->lenS[i] = strat->lenS[i-1];
    981   if (strat->lenSw!=NULL)
    982     for (i=old_pos; i>new_pos; i--)
    983       strat->lenSw[i] = strat->lenSw[i-1];
    984 
    985   strat->S[new_pos]=p;
    986   strat->ecartS[new_pos]=ecart;
    987   strat->sevS[new_pos]=sev;
    988   strat->S_2_R[new_pos]=s_2_r;
    989   strat->lenS[new_pos]=length;
    990   if(strat->lenSw!=NULL)
    991     strat->lenSw[new_pos]=length_w;
     1089  for (i = old_pos; i > new_pos; i--)
     1090  {
     1091    strat->S[i] = strat->S[i - 1];
     1092    strat->ecartS[i] = strat->ecartS[i - 1];
     1093    strat->sevS[i] = strat->sevS[i - 1];
     1094    strat->S_2_R[i] = strat->S_2_R[i - 1];
     1095  }
     1096  if (strat->lenS != NULL)
     1097    for (i = old_pos; i > new_pos; i--)
     1098      strat->lenS[i] = strat->lenS[i - 1];
     1099  if (strat->lenSw != NULL)
     1100    for (i = old_pos; i > new_pos; i--)
     1101      strat->lenSw[i] = strat->lenSw[i - 1];
     1102
     1103  strat->S[new_pos] = p;
     1104  strat->ecartS[new_pos] = ecart;
     1105  strat->sevS[new_pos] = sev;
     1106  strat->S_2_R[new_pos] = s_2_r;
     1107  strat->lenS[new_pos] = length;
     1108  if (strat->lenSw != NULL)
     1109    strat->lenSw[new_pos] = length_w;
    9921110  //assume(lenS_correct(strat));
    9931111}
    9941112
    995 static void move_backward_in_S(int old_pos, int new_pos,kStrategy strat)
    996 {
    997   assume(old_pos<=new_pos);
    998   poly p=strat->S[old_pos];
    999   int ecart=strat->ecartS[old_pos];
    1000   long sev=strat->sevS[old_pos];
    1001   int s_2_r=strat->S_2_R[old_pos];
    1002   int length=strat->lenS[old_pos];
    1003   assume(length==pLength(strat->S[old_pos]));
     1113static void
     1114move_backward_in_S (int old_pos, int new_pos, kStrategy strat)
     1115{
     1116  assume (old_pos <= new_pos);
     1117  poly p = strat->S[old_pos];
     1118  int ecart = strat->ecartS[old_pos];
     1119  long sev = strat->sevS[old_pos];
     1120  int s_2_r = strat->S_2_R[old_pos];
     1121  int length = strat->lenS[old_pos];
     1122  assume (length == pLength (strat->S[old_pos]));
    10041123  wlen_type length_w;
    1005   if(strat->lenSw!=NULL)
    1006     length_w=strat->lenSw[old_pos];
     1124  if (strat->lenSw != NULL)
     1125    length_w = strat->lenSw[old_pos];
    10071126  int i;
    1008   for (i=old_pos; i<new_pos; i++)
    1009   {
    1010     strat->S[i] = strat->S[i+1];
    1011     strat->ecartS[i] = strat->ecartS[i+1];
    1012     strat->sevS[i] = strat->sevS[i+1];
    1013     strat->S_2_R[i] = strat->S_2_R[i+1];
    1014   }
    1015   if (strat->lenS!=NULL)
    1016     for (i=old_pos; i<new_pos; i++)
    1017       strat->lenS[i] = strat->lenS[i+1];
    1018   if (strat->lenSw!=NULL)
    1019     for (i=old_pos; i<new_pos; i++)
    1020       strat->lenSw[i] = strat->lenSw[i+1];
    1021 
    1022   strat->S[new_pos]=p;
    1023   strat->ecartS[new_pos]=ecart;
    1024   strat->sevS[new_pos]=sev;
    1025   strat->S_2_R[new_pos]=s_2_r;
    1026   strat->lenS[new_pos]=length;
    1027   if(strat->lenSw!=NULL)
    1028     strat->lenSw[new_pos]=length_w;
     1127  for (i = old_pos; i < new_pos; i++)
     1128  {
     1129    strat->S[i] = strat->S[i + 1];
     1130    strat->ecartS[i] = strat->ecartS[i + 1];
     1131    strat->sevS[i] = strat->sevS[i + 1];
     1132    strat->S_2_R[i] = strat->S_2_R[i + 1];
     1133  }
     1134  if (strat->lenS != NULL)
     1135    for (i = old_pos; i < new_pos; i++)
     1136      strat->lenS[i] = strat->lenS[i + 1];
     1137  if (strat->lenSw != NULL)
     1138    for (i = old_pos; i < new_pos; i++)
     1139      strat->lenSw[i] = strat->lenSw[i + 1];
     1140
     1141  strat->S[new_pos] = p;
     1142  strat->ecartS[new_pos] = ecart;
     1143  strat->sevS[new_pos] = sev;
     1144  strat->S_2_R[new_pos] = s_2_r;
     1145  strat->lenS[new_pos] = length;
     1146  if (strat->lenSw != NULL)
     1147    strat->lenSw[new_pos] = length_w;
    10291148  //assume(lenS_correct(strat));
    10301149}
    10311150
    1032 static int* make_connections(int from, int to, poly bound, slimgb_alg* c)
    1033 {
    1034   ideal I=c->S;
    1035   int* cans=(int*) omalloc(c->n*sizeof(int));
    1036   int* connected=(int*) omalloc(c->n*sizeof(int));
    1037   cans[0]=to;
    1038   int cans_length=1;
    1039   connected[0]=from;
    1040   int last_cans_pos=-1;
    1041   int connected_length=1;
    1042   long neg_bounds_short= ~p_GetShortExpVector(bound,c->r);
    1043 
    1044   int not_yet_found=cans_length;
    1045   int con_checked=0;
     1151static int *
     1152make_connections (int from, int to, poly bound, slimgb_alg * c)
     1153{
     1154  ideal I = c->S;
     1155  int *cans = (int *) omalloc (c->n * sizeof (int));
     1156  int *connected = (int *) omalloc (c->n * sizeof (int));
     1157  cans[0] = to;
     1158  int cans_length = 1;
     1159  connected[0] = from;
     1160  int last_cans_pos = -1;
     1161  int connected_length = 1;
     1162  long neg_bounds_short = ~p_GetShortExpVector (bound, c->r);
     1163
     1164  int not_yet_found = cans_length;
     1165  int con_checked = 0;
    10461166  int pos;
    10471167
    1048   while(TRUE)
    1049   {
    1050     if ((con_checked<connected_length)&& (not_yet_found>0))
    1051     {
    1052       pos=connected[con_checked];
    1053       for(int i=0;i<cans_length;i++)
    1054       {
    1055         if (cans[i]<0) continue;
    1056         //FIXME: triv. syz. does not hold on noncommutative, check it for modules
    1057         if ((has_t_rep(pos,cans[i],c)) ||((!rIsPluralRing(c->r))&&(trivial_syzygie(pos,cans[i],bound,c))))
    1058 {
    1059           connected[connected_length]=cans[i];
    1060           connected_length++;
    1061           cans[i]=-1;
    1062           --not_yet_found;
    1063 
    1064           if (connected[connected_length-1]==to)
    1065           {
    1066             if (connected_length<c->n)
    1067             {
    1068               connected[connected_length]=-1;
    1069             }
    1070             omfree(cans);
    1071             return connected;
    1072           }
    1073         }
     1168  while (TRUE)
     1169  {
     1170    if ((con_checked < connected_length) && (not_yet_found > 0))
     1171    {
     1172      pos = connected[con_checked];
     1173      for (int i = 0; i < cans_length; i++)
     1174      {
     1175        if (cans[i] < 0)
     1176          continue;
     1177        //FIXME: triv. syz. does not hold on noncommutative, check it for modules
     1178        if ((has_t_rep (pos, cans[i], c))
     1179            || ((!rIsPluralRing (c->r))
     1180                && (trivial_syzygie (pos, cans[i], bound, c))))
     1181        {
     1182          connected[connected_length] = cans[i];
     1183          connected_length++;
     1184          cans[i] = -1;
     1185          --not_yet_found;
     1186
     1187          if (connected[connected_length - 1] == to)
     1188          {
     1189            if (connected_length < c->n)
     1190            {
     1191              connected[connected_length] = -1;
     1192            }
     1193            omfree (cans);
     1194            return connected;
     1195          }
     1196        }
    10741197      }
    10751198      con_checked++;
     
    10771200    else
    10781201    {
    1079       for(last_cans_pos++;last_cans_pos<=c->n;last_cans_pos++)
    1080       {
    1081         if (last_cans_pos==c->n)
    1082         {
    1083           if (connected_length<c->n)
    1084           {
    1085             connected[connected_length]=-1;
    1086           }
    1087           omfree(cans);
    1088           return connected;
    1089         }
    1090         if ((last_cans_pos==from)||(last_cans_pos==to))
    1091           continue;
    1092         if(p_LmShortDivisibleBy(I->m[last_cans_pos],c->short_Exps[last_cans_pos],bound,neg_bounds_short,c->r))
    1093         {
    1094           cans[cans_length]=last_cans_pos;
    1095           cans_length++;
    1096           break;
    1097         }
     1202      for (last_cans_pos++; last_cans_pos <= c->n; last_cans_pos++)
     1203      {
     1204        if (last_cans_pos == c->n)
     1205        {
     1206          if (connected_length < c->n)
     1207          {
     1208            connected[connected_length] = -1;
     1209          }
     1210          omfree (cans);
     1211          return connected;
     1212        }
     1213        if ((last_cans_pos == from) || (last_cans_pos == to))
     1214          continue;
     1215        if (p_LmShortDivisibleBy
     1216            (I->m[last_cans_pos], c->short_Exps[last_cans_pos], bound,
     1217             neg_bounds_short, c->r))
     1218        {
     1219          cans[cans_length] = last_cans_pos;
     1220          cans_length++;
     1221          break;
     1222        }
    10981223      }
    10991224      not_yet_found++;
    1100       for (int i=0;i<con_checked;i++)
    1101       {
    1102         if (has_t_rep(connected[i],last_cans_pos,c))
    1103         {
    1104           connected[connected_length]=last_cans_pos;
    1105           connected_length++;
    1106           cans[cans_length-1]=-1;
    1107           --not_yet_found;
    1108           if (connected[connected_length-1]==to)
    1109           {
    1110             if (connected_length<c->n)
    1111             {
    1112               connected[connected_length]=-1;
    1113             }
    1114             omfree(cans);
    1115             return connected;
    1116           }
    1117           break;
    1118         }
    1119       }
    1120     }
    1121   }
    1122   if (connected_length<c->n)
    1123   {
    1124     connected[connected_length]=-1;
    1125   }
    1126   omfree(cans);
     1225      for (int i = 0; i < con_checked; i++)
     1226      {
     1227        if (has_t_rep (connected[i], last_cans_pos, c))
     1228        {
     1229          connected[connected_length] = last_cans_pos;
     1230          connected_length++;
     1231          cans[cans_length - 1] = -1;
     1232          --not_yet_found;
     1233          if (connected[connected_length - 1] == to)
     1234          {
     1235            if (connected_length < c->n)
     1236            {
     1237              connected[connected_length] = -1;
     1238            }
     1239            omfree (cans);
     1240            return connected;
     1241          }
     1242          break;
     1243        }
     1244      }
     1245    }
     1246  }
     1247  if (connected_length < c->n)
     1248  {
     1249    connected[connected_length] = -1;
     1250  }
     1251  omfree (cans);
    11271252  return connected;
    11281253}
     1254
    11291255#ifdef HEAD_BIN
    1130 static inline poly p_MoveHead(poly p, omBin b)
     1256static inline poly
     1257p_MoveHead (poly p, omBin b)
    11311258{
    11321259  poly np;
    1133   omTypeAllocBin(poly, np, b);
    1134   memmove(np, p, b->sizeW*sizeof(long));
    1135   omFreeBinAddr(p);
     1260  omTypeAllocBin (poly, np, b);
     1261  memmove (np, p, b->sizeW * sizeof (long));
     1262  omFreeBinAddr (p);
    11361263  return np;
    11371264}
    11381265#endif
    11391266
    1140 static void replace_pair(int & i, int & j,slimgb_alg* c)
    1141 {
    1142   if (i<0) return;
    1143   c->soon_free=NULL;
     1267static void
     1268replace_pair (int &i, int &j, slimgb_alg * c)
     1269{
     1270  if (i < 0)
     1271    return;
     1272  c->soon_free = NULL;
    11441273  int syz_deg;
    1145   poly lm=pOne();
    1146 
    1147   pLcm(c->S->m[i], c->S->m[j], lm);
    1148   pSetm(lm);
    1149 
    1150   int* i_con =make_connections(i,j,lm,c);
    1151 
    1152   for (int n=0;((n<c->n) && (i_con[n]>=0));n++)
    1153   {
    1154     if (i_con[n]==j)
    1155     {
    1156       now_t_rep(i,j,c);
    1157       omfree(i_con);
    1158       p_Delete(&lm,c->r);
     1274  poly lm = pOne ();
     1275
     1276  pLcm (c->S->m[i], c->S->m[j], lm);
     1277  pSetm (lm);
     1278
     1279  int *i_con = make_connections (i, j, lm, c);
     1280
     1281  for (int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
     1282  {
     1283    if (i_con[n] == j)
     1284    {
     1285      now_t_rep (i, j, c);
     1286      omfree (i_con);
     1287      p_Delete (&lm, c->r);
    11591288      return;
    11601289    }
    11611290  }
    11621291
    1163   int* j_con =make_connections(j,i,lm,c);
     1292  int *j_con = make_connections (j, i, lm, c);
    11641293
    11651294//   if(c->n>1)
     
    11721301//         j=j_con[1];
    11731302//     }
    1174  // }
    1175 
    1176   int sugar=syz_deg=c->pTotaldegree(lm);
    1177 
    1178   p_Delete(&lm, c->r);
    1179     if(c->T_deg_full)//Sugar
    1180     {
    1181       int t_i=c->T_deg_full[i]-c->T_deg[i];
    1182       int t_j=c->T_deg_full[j]-c->T_deg[j];
    1183       sugar+=si_max(t_i,t_j);
    1184       //Print("\n max: %d\n",max(t_i,t_j));
    1185     }
    1186 
    1187   for (int m=0;((m<c->n) && (i_con[m]>=0));m++)
    1188   {
    1189     if(c->T_deg_full!=NULL)
    1190     {
    1191         int s1=c->T_deg_full[i_con[m]]+syz_deg-c->T_deg[i_con[m]];
    1192         if (s1>sugar) continue;
    1193     }
    1194     if (c->weighted_lengths[i_con[m]]<c->weighted_lengths[i])
    1195         i=i_con[m];
    1196     }
    1197     for (int m=0;((m<c->n) && (j_con[m]>=0));m++)
    1198     {
    1199         if (c->T_deg_full!=NULL)
    1200         {
    1201         int s1=c->T_deg_full[j_con[m]]+syz_deg-c->T_deg[j_con[m]];
    1202         if (s1>sugar) continue;}
    1203         if (c->weighted_lengths[j_con[m]]<c->weighted_lengths[j])
    1204             j=j_con[m];
    1205     }
    1206 
    1207      //can also try dependend search
    1208   omfree(i_con);
    1209   omfree(j_con);
     1303  // }
     1304
     1305  int sugar = syz_deg = c->pTotaldegree (lm);
     1306
     1307  p_Delete (&lm, c->r);
     1308  if (c->T_deg_full)            //Sugar
     1309  {
     1310    int t_i = c->T_deg_full[i] - c->T_deg[i];
     1311    int t_j = c->T_deg_full[j] - c->T_deg[j];
     1312    sugar += si_max (t_i, t_j);
     1313    //Print("\n max: %d\n",max(t_i,t_j));
     1314  }
     1315
     1316  for (int m = 0; ((m < c->n) && (i_con[m] >= 0)); m++)
     1317  {
     1318    if (c->T_deg_full != NULL)
     1319    {
     1320      int s1 = c->T_deg_full[i_con[m]] + syz_deg - c->T_deg[i_con[m]];
     1321      if (s1 > sugar)
     1322        continue;
     1323    }
     1324    if (c->weighted_lengths[i_con[m]] < c->weighted_lengths[i])
     1325      i = i_con[m];
     1326  }
     1327  for (int m = 0; ((m < c->n) && (j_con[m] >= 0)); m++)
     1328  {
     1329    if (c->T_deg_full != NULL)
     1330    {
     1331      int s1 = c->T_deg_full[j_con[m]] + syz_deg - c->T_deg[j_con[m]];
     1332      if (s1 > sugar)
     1333        continue;
     1334    }
     1335    if (c->weighted_lengths[j_con[m]] < c->weighted_lengths[j])
     1336      j = j_con[m];
     1337  }
     1338
     1339  //can also try dependend search
     1340  omfree (i_con);
     1341  omfree (j_con);
    12101342  return;
    12111343}
    12121344
    1213 static void add_later(poly p, const char* prot, slimgb_alg* c)
    1214 {
    1215     int i=0;
    1216     //check, if it is already in the queue
    1217 
    1218     while(c->add_later->m[i]!=NULL)
    1219     {
    1220         if (p_LmEqual(c->add_later->m[i],p,c->r))
    1221             return;
    1222         i++;
    1223     }
    1224     if (TEST_OPT_PROT)
    1225         PrintS(prot);
    1226     c->add_later->m[i]=p;
    1227 }
    1228 static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen)
    1229 {
    1230   if(strat->sl==-1) return 0;
    1231   if (strat->lenSw) return pos_helper(strat,p,(wlen_type) wlen,(wlen_set) strat->lenSw,strat->S);
    1232   return pos_helper(strat,p,len,strat->lenS,strat->S);
     1345static void
     1346add_later (poly p, const char *prot, slimgb_alg * c)
     1347{
     1348  int i = 0;
     1349  //check, if it is already in the queue
     1350
     1351  while (c->add_later->m[i] != NULL)
     1352  {
     1353    if (p_LmEqual (c->add_later->m[i], p, c->r))
     1354      return;
     1355    i++;
     1356  }
     1357  if (TEST_OPT_PROT)
     1358    PrintS (prot);
     1359  c->add_later->m[i] = p;
     1360}
     1361
     1362static int
     1363simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen)
     1364{
     1365  if (strat->sl == -1)
     1366    return 0;
     1367  if (strat->lenSw)
     1368    return pos_helper (strat, p, (wlen_type) wlen, (wlen_set) strat->lenSw,
     1369                       strat->S);
     1370  return pos_helper (strat, p, len, strat->lenS, strat->S);
    12331371}
    12341372
     
    12371375 *divides the leading term of some S[i] it will be canceled
    12381376 */
    1239 static inline void clearS (poly p, unsigned long p_sev,int l, int* at, int* k,
    1240                            kStrategy strat)
    1241 {
    1242   assume(p_sev == pGetShortExpVector(p));
    1243   if (!pLmShortDivisibleBy(p,p_sev, strat->S[*at], ~ strat->sevS[*at])) return;
    1244   if (l>=strat->lenS[*at]) return;
     1377static inline void
     1378clearS (poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat)
     1379{
     1380  assume (p_sev == pGetShortExpVector (p));
     1381  if (!pLmShortDivisibleBy (p, p_sev, strat->S[*at], ~strat->sevS[*at]))
     1382    return;
     1383  if (l >= strat->lenS[*at])
     1384    return;
    12451385  if (TEST_OPT_PROT)
    1246     PrintS("!");
    1247   mflush();
     1386    PrintS ("!");
     1387  mflush ();
    12481388  //pDelete(&strat->S[*at]);
    1249   deleteInS((*at),strat);
     1389  deleteInS ((*at), strat);
    12501390  (*at)--;
    12511391  (*k)--;
     
    12531393}
    12541394
    1255 static int iq_crit(const void* ap,const void* bp)
    1256 {
    1257   sorted_pair_node* a=*((sorted_pair_node**)ap);
    1258   sorted_pair_node* b=*((sorted_pair_node**)bp);
    1259   assume(a->i>a->j);
    1260   assume(b->i>b->j);
    1261 
    1262   if (a->deg<b->deg) return -1;
    1263   if (a->deg>b->deg) return 1;
    1264   int comp=pLmCmp(a->lcm_of_lm, b->lcm_of_lm);
    1265   if(comp!=0)
     1395static int
     1396iq_crit (const void *ap, const void *bp)
     1397{
     1398  sorted_pair_node *a = *((sorted_pair_node **) ap);
     1399  sorted_pair_node *b = *((sorted_pair_node **) bp);
     1400  assume (a->i > a->j);
     1401  assume (b->i > b->j);
     1402
     1403  if (a->deg < b->deg)
     1404    return -1;
     1405  if (a->deg > b->deg)
     1406    return 1;
     1407  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
     1408  if (comp != 0)
    12661409    return comp;
    1267   if (a->expected_length<b->expected_length) return -1;
    1268   if (a->expected_length>b->expected_length) return 1;
    1269   if (a->j>b->j) return 1;
    1270   if (a->j<b->j) return -1;
     1410  if (a->expected_length < b->expected_length)
     1411    return -1;
     1412  if (a->expected_length > b->expected_length)
     1413    return 1;
     1414  if (a->j > b->j)
     1415    return 1;
     1416  if (a->j < b->j)
     1417    return -1;
    12711418  return 0;
    12721419}
    1273 static wlen_type coeff_mult_size_estimate(int s1, int s2, ring r)
    1274 {
    1275     if (rField_is_Q(r)) return s1+s2;
    1276     else return s1*s2;
    1277 }
    1278 static wlen_type pair_weighted_length(int i, int j, slimgb_alg* c)
    1279 {
    1280     if ((c->isDifficultField) && (c->eliminationProblem))  {
    1281         int c1=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r);
    1282         int c2=slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
    1283         wlen_type el1=c->weighted_lengths[i]/c1;
    1284         assume(el1!=0);
    1285         assume(c->weighted_lengths[i] %c1==0);
    1286         wlen_type el2=c->weighted_lengths[j]/c2;
    1287         assume(el2!=0);
    1288         assume(c->weighted_lengths[j] %c2==0);
    1289         //should be * for function fields
    1290         //return (c1+c2) * (el1+el2-2);
    1291         wlen_type res=coeff_mult_size_estimate(c1,c2,c->r);
    1292         res*=el1+el2-2;
    1293         return res;
    1294 
    1295     }
    1296     if (c->isDifficultField) {
    1297         //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+
    1298         //    slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
    1299         if(!(TEST_V_COEFSTRAT))
    1300         {
    1301         wlen_type cs=
    1302             coeff_mult_size_estimate(
    1303                 slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r),
    1304                 slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r),c->r);
    1305         return (wlen_type)(c->lengths[i]+c->lengths[j]-2)*
    1306             (wlen_type)cs;}
    1307             else
    1308             {
    1309 
    1310             wlen_type cs=
    1311             coeff_mult_size_estimate(
    1312                 slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r),
    1313                 slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r),c->r);
    1314             cs*=cs;
    1315         return (wlen_type)(c->lengths[i]+c->lengths[j]-2)*
    1316             (wlen_type)cs;
    1317             }
    1318     }
    1319     if (c->eliminationProblem) {
    1320 
    1321         return (c->weighted_lengths[i]+c->weighted_lengths[j]-2);
    1322     }
    1323     return c->lengths[i]+c->lengths[j]-2;
    1324 
    1325 }
    1326 sorted_pair_node** add_to_basis_ideal_quotient(poly h, slimgb_alg* c, int* ip)
    1327 {
    1328   p_Test(h,c->r);
    1329   assume(h!=NULL);
    1330   poly got=gcd_of_terms(h,c->r);
    1331   if((got!=NULL) &&(TEST_V_UPTORADICAL)) {
    1332     poly copy=p_Copy(got,c->r);
     1420
     1421static wlen_type
     1422coeff_mult_size_estimate (int s1, int s2, ring r)
     1423{
     1424  if (rField_is_Q (r))
     1425    return s1 + s2;
     1426  else
     1427    return s1 * s2;
     1428}
     1429
     1430static wlen_type
     1431pair_weighted_length (int i, int j, slimgb_alg * c)
     1432{
     1433  if ((c->isDifficultField) && (c->eliminationProblem))
     1434  {
     1435    int c1 = slim_nsize (p_GetCoeff (c->S->m[i], c->r), c->r);
     1436    int c2 = slim_nsize (p_GetCoeff (c->S->m[j], c->r), c->r);
     1437    wlen_type el1 = c->weighted_lengths[i] / c1;
     1438    assume (el1 != 0);
     1439    assume (c->weighted_lengths[i] % c1 == 0);
     1440    wlen_type el2 = c->weighted_lengths[j] / c2;
     1441    assume (el2 != 0);
     1442    assume (c->weighted_lengths[j] % c2 == 0);
     1443    //should be * for function fields
     1444    //return (c1+c2) * (el1+el2-2);
     1445    wlen_type res = coeff_mult_size_estimate (c1, c2, c->r);
     1446    res *= el1 + el2 - 2;
     1447    return res;
     1448
     1449  }
     1450  if (c->isDifficultField)
     1451  {
     1452    //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+
     1453    //    slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
     1454    if (!(TEST_V_COEFSTRAT))
     1455    {
     1456      wlen_type cs =
     1457        coeff_mult_size_estimate (slim_nsize
     1458                                  (p_GetCoeff (c->S->m[i], c->r), c->r),
     1459                                  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
     1460                                              c->r), c->r);
     1461      return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
     1462    }
     1463    else
     1464    {
     1465
     1466      wlen_type cs =
     1467        coeff_mult_size_estimate (slim_nsize
     1468                                  (p_GetCoeff (c->S->m[i], c->r), c->r),
     1469                                  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
     1470                                              c->r), c->r);
     1471      cs *= cs;
     1472      return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
     1473    }
     1474  }
     1475  if (c->eliminationProblem)
     1476  {
     1477
     1478    return (c->weighted_lengths[i] + c->weighted_lengths[j] - 2);
     1479  }
     1480  return c->lengths[i] + c->lengths[j] - 2;
     1481
     1482}
     1483
     1484sorted_pair_node **
     1485add_to_basis_ideal_quotient (poly h, slimgb_alg * c, int *ip)
     1486{
     1487  p_Test (h, c->r);
     1488  assume (h != NULL);
     1489  poly got = gcd_of_terms (h, c->r);
     1490  if ((got != NULL) && (TEST_V_UPTORADICAL))
     1491  {
     1492    poly copy = p_Copy (got, c->r);
    13331493    //p_wrp(got,c->r);
    1334     BOOLEAN changed=monomial_root(got,c->r);
     1494    BOOLEAN changed = monomial_root (got, c->r);
    13351495    if (changed)
    13361496    {
    1337          poly div_by=pDivide(copy, got);
    1338          poly iter=h;
    1339          while(iter)
    1340          {
    1341             pExpVectorSub(iter,div_by);
    1342             pIter(iter);
    1343          }
    1344          p_Delete(&div_by, c->r);
    1345          PrintS("U");
    1346     }
    1347     p_Delete(&copy,c->r);
     1497      poly div_by = pDivide (copy, got);
     1498      poly iter = h;
     1499      while (iter)
     1500      {
     1501        pExpVectorSub (iter, div_by);
     1502        pIter (iter);
     1503      }
     1504      p_Delete (&div_by, c->r);
     1505      PrintS ("U");
     1506    }
     1507    p_Delete (&copy, c->r);
    13481508  }
    13491509
     
    13511511//  BOOLEAN corr=lenS_correct(c->strat);
    13521512  int sugar;
    1353   int ecart=0;
     1513  int ecart = 0;
    13541514  ++(c->n);
    13551515  ++(c->S->ncols);
    1356   int i,j;
    1357   i=c->n-1;
    1358   sorted_pair_node** nodes=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i);
    1359   int spc=0;
    1360   if(c->n>c->array_lengths)
    1361   {
    1362     c->array_lengths=c->array_lengths*2;
    1363     assume(c->array_lengths>=c->n);
    1364     ENLARGE(c->T_deg, int);
    1365     ENLARGE(c->tmp_pair_lm,poly);
    1366     ENLARGE(c->tmp_spn,sorted_pair_node*);
    1367 
    1368     ENLARGE(c->short_Exps,long);
    1369     ENLARGE(c->lengths,int);
    1370     #ifndef HAVE_BOOST
    1371     #ifndef USE_STDVECBOOL
    1372 
    1373     ENLARGE(c->states, char*);
    1374     #endif
    1375     #endif
    1376     ENLARGE(c->gcd_of_terms,poly);
     1516  int i, j;
     1517  i = c->n - 1;
     1518  sorted_pair_node **nodes =
     1519    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
     1520  int spc = 0;
     1521  if (c->n > c->array_lengths)
     1522  {
     1523    c->array_lengths = c->array_lengths * 2;
     1524    assume (c->array_lengths >= c->n);
     1525    ENLARGE (c->T_deg, int);
     1526    ENLARGE (c->tmp_pair_lm, poly);
     1527    ENLARGE (c->tmp_spn, sorted_pair_node *);
     1528
     1529    ENLARGE (c->short_Exps, long);
     1530    ENLARGE (c->lengths, int);
     1531#ifndef HAVE_BOOST
     1532#ifndef USE_STDVECBOOL
     1533
     1534    ENLARGE (c->states, char *);
     1535#endif
     1536#endif
     1537    ENLARGE (c->gcd_of_terms, poly);
    13771538    //if (c->weighted_lengths!=NULL) {
    1378     ENLARGE(c->weighted_lengths,wlen_type);
     1539    ENLARGE (c->weighted_lengths, wlen_type);
    13791540    //}
    13801541    //ENLARGE(c->S->m,poly);
    13811542  }
    1382   pEnlargeSet(&c->S->m,c->n-1,1);
     1543  pEnlargeSet (&c->S->m, c->n - 1, 1);
    13831544  if (c->T_deg_full)
    1384     ENLARGE(c->T_deg_full,int);
    1385   sugar=c->T_deg[i]=c->pTotaldegree(h);
    1386   if(c->T_deg_full)
    1387   {
    1388     sugar=c->T_deg_full[i]=c->pTotaldegree_full(h);
    1389     ecart=sugar-c->T_deg[i];
    1390     assume(ecart>=0);
    1391   }
    1392   c->tmp_pair_lm[i]=pOne_Special(c->r);
    1393 
    1394   c->tmp_spn[i]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
    1395 
    1396   c->lengths[i]=pLength(h);
     1545    ENLARGE (c->T_deg_full, int);
     1546  sugar = c->T_deg[i] = c->pTotaldegree (h);
     1547  if (c->T_deg_full)
     1548  {
     1549    sugar = c->T_deg_full[i] = c->pTotaldegree_full (h);
     1550    ecart = sugar - c->T_deg[i];
     1551    assume (ecart >= 0);
     1552  }
     1553  c->tmp_pair_lm[i] = pOne_Special (c->r);
     1554
     1555  c->tmp_spn[i] = (sorted_pair_node *) omalloc (sizeof (sorted_pair_node));
     1556
     1557  c->lengths[i] = pLength (h);
    13971558
    13981559  //necessary for correct weighted length
    13991560
    1400   if (!rField_is_Zp(c->r))
    1401   {
    1402     p_Cleardenom(h, c->r);
     1561  if (!rField_is_Zp (c->r))
     1562  {
     1563    p_Cleardenom (h, c->r);
    14031564    //p_Content(h,c->r); //is a duplicate call, but belongs here
    14041565  }
    14051566  else
    1406     pNorm(h);
    1407   pNormalize(h);
    1408 
    1409   c->weighted_lengths[i]=pQuality(h, c, c->lengths[i]);
    1410   c->gcd_of_terms[i]=got;
    1411   #ifdef HAVE_BOOST
    1412     c->states.push_back(dynamic_bitset<>(i));
    1413 
    1414   #else
    1415   #ifdef USE_STDVECBOOL
    1416 
    1417     c->states.push_back(vector<bool>(i));
    1418 
    1419   #else
    1420   if (i>0)
    1421     c->states[i]=(char*)  omalloc(i*sizeof(char));
     1567    pNorm (h);
     1568  pNormalize (h);
     1569
     1570  c->weighted_lengths[i] = pQuality (h, c, c->lengths[i]);
     1571  c->gcd_of_terms[i] = got;
     1572#ifdef HAVE_BOOST
     1573  c->states.push_back (dynamic_bitset <> (i));
     1574
     1575#else
     1576#ifdef USE_STDVECBOOL
     1577
     1578  c->states.push_back (vector < bool > (i));
     1579
     1580#else
     1581  if (i > 0)
     1582    c->states[i] = (char *) omalloc (i * sizeof (char));
    14221583  else
    1423     c->states[i]=NULL;
    1424   #endif
    1425   #endif
    1426 
    1427   c->S->m[i]=h;
    1428   c->short_Exps[i]=p_GetShortExpVector(h,c->r);
     1584    c->states[i] = NULL;
     1585#endif
     1586#endif
     1587
     1588  c->S->m[i] = h;
     1589  c->short_Exps[i] = p_GetShortExpVector (h, c->r);
    14291590
    14301591#undef ENLARGE
    1431   if (p_GetComp(h,currRing)<=c->syz_comp)
    1432   {
    1433   for (j=0;j<i;j++)
    1434   {
    1435 
    1436 
    1437     #ifndef HAVE_BOOST
    1438     c->states[i][j]=UNCALCULATED;
    1439     #endif
    1440     assume(p_LmDivisibleBy(c->S->m[i],c->S->m[j],c->r)==
    1441      p_LmShortDivisibleBy(c->S->m[i],c->short_Exps[i],c->S->m[j],~(c->short_Exps[j]),c->r));
    1442 
    1443     if (_p_GetComp(c->S->m[i],c->r)!=_p_GetComp(c->S->m[j],c->r))
    1444     {
    1445       //c->states[i][j]=UNCALCULATED;
    1446       //WARNUNG: be careful
    1447       continue;
    1448     }
    1449     else
    1450     if ((!c->nc) && (c->lengths[i]==1) && (c->lengths[j]==1))
    1451     {
    1452       c->states[i][j]=HASTREP;
    1453     }
    1454     else if (( (!c->nc) || (c->is_homog && rIsSCA(c->r) ) ) &&  (pHasNotCF(c->S->m[i],c->S->m[j])))
     1592  if (p_GetComp (h, currRing) <= c->syz_comp)
     1593  {
     1594    for (j = 0; j < i; j++)
     1595    {
     1596
     1597
     1598#ifndef HAVE_BOOST
     1599      c->states[i][j] = UNCALCULATED;
     1600#endif
     1601      assume (p_LmDivisibleBy (c->S->m[i], c->S->m[j], c->r) ==
     1602              p_LmShortDivisibleBy (c->S->m[i], c->short_Exps[i], c->S->m[j],
     1603                                    ~(c->short_Exps[j]), c->r));
     1604
     1605      if (_p_GetComp (c->S->m[i], c->r) != _p_GetComp (c->S->m[j], c->r))
     1606      {
     1607        //c->states[i][j]=UNCALCULATED;
     1608        //WARNUNG: be careful
     1609        continue;
     1610      }
     1611      else if ((!c->nc) && (c->lengths[i] == 1) && (c->lengths[j] == 1))
     1612      {
     1613        c->states[i][j] = HASTREP;
     1614      }
     1615      else if (((!c->nc) || (c->is_homog && rIsSCA (c->r)))
     1616               && (pHasNotCF (c->S->m[i], c->S->m[j])))
    14551617//     else if ((!(c->nc)) &&  (pHasNotCF(c->S->m[i],c->S->m[j])))
    1456     {
    1457       c->easy_product_crit++;
    1458       c->states[i][j]=HASTREP;
    1459       continue;
    1460     }
    1461     else if(extended_product_criterion(c->S->m[i],c->gcd_of_terms[i],c->S->m[j],c->gcd_of_terms[j],c))
    1462     {
    1463       c->states[i][j]=HASTREP;
    1464       c->extended_product_crit++;
    1465       //PrintS("E");
    1466     }
     1618      {
     1619        c->easy_product_crit++;
     1620        c->states[i][j] = HASTREP;
     1621        continue;
     1622      }
     1623      else
     1624        if (extended_product_criterion
     1625            (c->S->m[i], c->gcd_of_terms[i], c->S->m[j], c->gcd_of_terms[j],
     1626             c))
     1627      {
     1628        c->states[i][j] = HASTREP;
     1629        c->extended_product_crit++;
     1630        //PrintS("E");
     1631      }
    14671632      //  if (c->states[i][j]==UNCALCULATED)
    14681633      //  {
    14691634
    1470     if ((TEST_V_FINDMONOM) &&(!c->nc)) {
    1471         //PrintS("COMMU");
    1472        //  if (c->lengths[i]==c->lengths[j])
    1473        //  {
     1635      if ((TEST_V_FINDMONOM) && (!c->nc))
     1636      {
     1637        //PrintS("COMMU");
     1638        //  if (c->lengths[i]==c->lengths[j])
     1639        //  {
    14741640//             poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
    14751641//             if (short_s==NULL)
     
    14821648//             }
    14831649//         }
    1484         if (c->lengths[i]+c->lengths[j]==3)
    1485         {
    1486 
    1487 
    1488              poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
    1489             if (short_s==NULL)
    1490             {
    1491                 c->states[i][j]=HASTREP;
    1492             }
    1493             else
    1494             {
    1495                 assume(pLength(short_s)==1);
    1496                 if (TEST_V_UPTORADICAL)
    1497                    monomial_root(short_s,c->r);
    1498                 int iS=
    1499                    kFindDivisibleByInS_easy(c->strat,short_s, p_GetShortExpVector(short_s,c->r));
    1500                 if (iS<0)
    1501                 {
    1502                     //PrintS("N");
    1503                     if (TRUE)
    1504                     {
    1505                       c->states[i][j]=HASTREP;
    1506                       add_later(short_s,"N",c);
    1507                     }
    1508                     else
    1509                       p_Delete(&short_s,currRing);
    1510                 }
    1511                 else
    1512                 {
    1513                     if (c->strat->lenS[iS]>1)
    1514                     {
    1515                         //PrintS("O");
    1516                         if (TRUE) {
    1517                         c->states[i][j]=HASTREP;
    1518                         add_later(short_s,"O",c);
    1519                         }
    1520                         else p_Delete(&short_s,currRing);
    1521                     }
    1522                     else
    1523                      p_Delete(&short_s, currRing);
    1524                      c->states[i][j]=HASTREP;
    1525                 }
    1526 
    1527 
    1528             }
    1529         }
    1530     }
     1650        if (c->lengths[i] + c->lengths[j] == 3)
     1651        {
     1652
     1653
     1654          poly short_s = ksCreateShortSpoly (c->S->m[i], c->S->m[j], c->r);
     1655          if (short_s == NULL)
     1656          {
     1657            c->states[i][j] = HASTREP;
     1658          }
     1659          else
     1660          {
     1661            assume (pLength (short_s) == 1);
     1662            if (TEST_V_UPTORADICAL)
     1663              monomial_root (short_s, c->r);
     1664            int iS =
     1665              kFindDivisibleByInS_easy (c->strat, short_s,
     1666                                        p_GetShortExpVector (short_s, c->r));
     1667            if (iS < 0)
     1668            {
     1669              //PrintS("N");
     1670              if (TRUE)
     1671              {
     1672                c->states[i][j] = HASTREP;
     1673                add_later (short_s, "N", c);
     1674              }
     1675              else
     1676                p_Delete (&short_s, currRing);
     1677            }
     1678            else
     1679            {
     1680              if (c->strat->lenS[iS] > 1)
     1681              {
     1682                //PrintS("O");
     1683                if (TRUE)
     1684                {
     1685                  c->states[i][j] = HASTREP;
     1686                  add_later (short_s, "O", c);
     1687                }
     1688                else
     1689                  p_Delete (&short_s, currRing);
     1690              }
     1691              else
     1692                p_Delete (&short_s, currRing);
     1693              c->states[i][j] = HASTREP;
     1694            }
     1695
     1696
     1697          }
     1698        }
     1699      }
    15311700      //    if (short_s)
    15321701      //    {
    1533     assume(spc<=j);
    1534     sorted_pair_node* s=c->tmp_spn[spc];//(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
    1535     s->i=si_max(i,j);
    1536     s->j=si_min(i,j);
    1537     assume(s->j==j);
    1538     s->expected_length=pair_weighted_length(i,j,c);//c->lengths[i]+c->lengths[j]-2;
    1539 
    1540     poly lm=c->tmp_pair_lm[spc];//=pOne_Special();
    1541 
    1542     pLcm(c->S->m[i], c->S->m[j], lm);
    1543     pSetm(lm);
    1544     p_Test(lm,c->r);
    1545     s->deg=c->pTotaldegree(lm);
    1546 
    1547     if(c->T_deg_full)//Sugar
    1548     {
    1549       int t_i=c->T_deg_full[s->i]-c->T_deg[s->i];
    1550       int t_j=c->T_deg_full[s->j]-c->T_deg[s->j];
    1551       s->deg+=si_max(t_i,t_j);
    1552       //Print("\n max: %d\n",max(t_i,t_j));
    1553     }
    1554     p_Test(lm,c->r);
    1555     s->lcm_of_lm=lm;
    1556     //          pDelete(&short_s);
    1557     //assume(lm!=NULL);
    1558     nodes[spc]=s;
    1559     spc++;
    1560 
    1561   // }
    1562   //else
    1563   //{
    1564         //c->states[i][j]=HASTREP;
    1565   //}
    1566   }
    1567   }//if syz_comp end
    1568 
    1569   assume(spc<=i);
     1702      assume (spc <= j);
     1703      sorted_pair_node *s = c->tmp_spn[spc];    //(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
     1704      s->i = si_max (i, j);
     1705      s->j = si_min (i, j);
     1706      assume (s->j == j);
     1707      s->expected_length = pair_weighted_length (i, j, c);      //c->lengths[i]+c->lengths[j]-2;
     1708
     1709      poly lm = c->tmp_pair_lm[spc];    //=pOne_Special();
     1710
     1711      pLcm (c->S->m[i], c->S->m[j], lm);
     1712      pSetm (lm);
     1713      p_Test (lm, c->r);
     1714      s->deg = c->pTotaldegree (lm);
     1715
     1716      if (c->T_deg_full)        //Sugar
     1717      {
     1718        int t_i = c->T_deg_full[s->i] - c->T_deg[s->i];
     1719        int t_j = c->T_deg_full[s->j] - c->T_deg[s->j];
     1720        s->deg += si_max (t_i, t_j);
     1721        //Print("\n max: %d\n",max(t_i,t_j));
     1722      }
     1723      p_Test (lm, c->r);
     1724      s->lcm_of_lm = lm;
     1725      //          pDelete(&short_s);
     1726      //assume(lm!=NULL);
     1727      nodes[spc] = s;
     1728      spc++;
     1729
     1730      // }
     1731      //else
     1732      //{
     1733      //c->states[i][j]=HASTREP;
     1734      //}
     1735    }
     1736  }                             //if syz_comp end
     1737
     1738  assume (spc <= i);
    15701739  //now ideal quotient crit
    1571   qsort(nodes,spc,sizeof(sorted_pair_node*),iq_crit);
    1572 
    1573     sorted_pair_node** nodes_final=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*i);
    1574   int spc_final=0;
    1575   j=0;
    1576   while(j<spc)
    1577   {
    1578     int lower=j;
     1740  qsort (nodes, spc, sizeof (sorted_pair_node *), iq_crit);
     1741
     1742  sorted_pair_node **nodes_final =
     1743    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
     1744  int spc_final = 0;
     1745  j = 0;
     1746  while (j < spc)
     1747  {
     1748    int lower = j;
    15791749    int upper;
    1580     BOOLEAN has=FALSE;
    1581     for(upper=lower+1;upper<spc;upper++)
    1582     {
    1583       if(!pLmEqual(nodes[lower]->lcm_of_lm,nodes[upper]->lcm_of_lm))
    1584       {
    1585   break;
    1586       }
    1587       if (has_t_rep(nodes[upper]->i,nodes[upper]->j,c))
    1588   has=TRUE;
    1589     }
    1590     upper=upper-1;
     1750    BOOLEAN has = FALSE;
     1751    for (upper = lower + 1; upper < spc; upper++)
     1752    {
     1753      if (!pLmEqual (nodes[lower]->lcm_of_lm, nodes[upper]->lcm_of_lm))
     1754      {
     1755        break;
     1756      }
     1757      if (has_t_rep (nodes[upper]->i, nodes[upper]->j, c))
     1758        has = TRUE;
     1759    }
     1760    upper = upper - 1;
    15911761    int z;
    1592     assume(spc_final<=j);
    1593     for(z=0;z<spc_final;z++)
    1594     {
    1595       if(p_LmDivisibleBy(nodes_final[z]->lcm_of_lm,nodes[lower]->lcm_of_lm,c->r))
    1596       {
    1597   has=TRUE;
    1598   break;
    1599       }
    1600     }
    1601 
    1602     if(has)
    1603     {
    1604       for(;lower<=upper;lower++)
    1605       {
    1606   //free_sorted_pair_node(nodes[lower],c->r);
    1607   //omfree(nodes[lower]);
    1608   nodes[lower]=NULL;
    1609       }
    1610       j=upper+1;
     1762    assume (spc_final <= j);
     1763    for (z = 0; z < spc_final; z++)
     1764    {
     1765      if (p_LmDivisibleBy
     1766          (nodes_final[z]->lcm_of_lm, nodes[lower]->lcm_of_lm, c->r))
     1767      {
     1768        has = TRUE;
     1769        break;
     1770      }
     1771    }
     1772
     1773    if (has)
     1774    {
     1775      for (; lower <= upper; lower++)
     1776      {
     1777        //free_sorted_pair_node(nodes[lower],c->r);
     1778        //omfree(nodes[lower]);
     1779        nodes[lower] = NULL;
     1780      }
     1781      j = upper + 1;
    16111782      continue;
    16121783    }
    16131784    else
    16141785    {
    1615       p_Test(nodes[lower]->lcm_of_lm,c->r);
    1616       nodes[lower]->lcm_of_lm=pCopy(nodes[lower]->lcm_of_lm);
    1617       assume(_p_GetComp(c->S->m[nodes[lower]->i],c->r)==_p_GetComp(c->S->m[nodes[lower]->j],c->r));
    1618       nodes_final[spc_final]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
    1619 
    1620       *(nodes_final[spc_final++])=*(nodes[lower]);
     1786      p_Test (nodes[lower]->lcm_of_lm, c->r);
     1787      nodes[lower]->lcm_of_lm = pCopy (nodes[lower]->lcm_of_lm);
     1788      assume (_p_GetComp (c->S->m[nodes[lower]->i], c->r) ==
     1789              _p_GetComp (c->S->m[nodes[lower]->j], c->r));
     1790      nodes_final[spc_final] =
     1791        (sorted_pair_node *) omalloc (sizeof (sorted_pair_node));
     1792
     1793      *(nodes_final[spc_final++]) = *(nodes[lower]);
    16211794      //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
    1622       nodes[lower]=NULL;
    1623       for(lower=lower+1;lower<=upper;lower++)
    1624       {
    1625   //  free_sorted_pair_node(nodes[lower],c->r);
    1626   //omfree(nodes[lower]);
    1627   nodes[lower]=NULL;
    1628       }
    1629       j=upper+1;
     1795      nodes[lower] = NULL;
     1796      for (lower = lower + 1; lower <= upper; lower++)
     1797      {
     1798        //  free_sorted_pair_node(nodes[lower],c->r);
     1799        //omfree(nodes[lower]);
     1800        nodes[lower] = NULL;
     1801      }
     1802      j = upper + 1;
    16301803      continue;
    16311804    }
     
    16341807  //  Print("i:%d,spc_final:%d",i,spc_final);
    16351808
    1636   assume(spc_final<=spc);
    1637   omfree(nodes);
    1638   nodes=NULL;
    1639 
    1640   add_to_reductors(c, h, c->lengths[c->n-1], ecart,TRUE);
     1809  assume (spc_final <= spc);
     1810  omfree (nodes);
     1811  nodes = NULL;
     1812
     1813  add_to_reductors (c, h, c->lengths[c->n - 1], ecart, TRUE);
    16411814  //i=posInS(c->strat,c->strat->sl,h,0 ecart);
    16421815  if (!(c->nc))
    16431816  {
    1644     if (c->lengths[c->n-1]==1)
    1645       shorten_tails(c,c->S->m[c->n-1]);
     1817    if (c->lengths[c->n - 1] == 1)
     1818      shorten_tails (c, c->S->m[c->n - 1]);
    16461819  }
    16471820  //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths
     
    16491822  //for(i=c->strat->sl; i>0;i--)
    16501823  //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
    1651   if (c->Rcounter>50) {
    1652     c->Rcounter=0;
    1653     cleanS(c->strat,c);
     1824  if (c->Rcounter > 50)
     1825  {
     1826    c->Rcounter = 0;
     1827    cleanS (c->strat, c);
    16541828  }
    16551829
     
    16571831  // for SCA:
    16581832  // here write at the end of nodes_final[spc_final,...,spc_final+lmdeg-1]
    1659   if(rIsSCA(c->r))
    1660   {
    1661     const poly pNext = pNext(h);
    1662 
    1663     if(pNext != NULL)
     1833  if (rIsSCA (c->r))
     1834  {
     1835    const poly pNext = pNext (h);
     1836
     1837    if (pNext != NULL)
    16641838    {
    16651839      // for additional polynomials
    1666       const unsigned int m_iFirstAltVar = scaFirstAltVar(c->r);
    1667       const unsigned int m_iLastAltVar  = scaLastAltVar(c->r);
    1668 
    1669       int N = // c->r->N;
    1670               m_iLastAltVar - m_iFirstAltVar + 1; // should be enough
     1840      const unsigned int m_iFirstAltVar = scaFirstAltVar (c->r);
     1841      const unsigned int m_iLastAltVar = scaLastAltVar (c->r);
     1842
     1843      int N =                   // c->r->N;
     1844        m_iLastAltVar - m_iFirstAltVar + 1;     // should be enough
    16711845      // TODO: but we may also use got = gcd({m}_{m\in f}))!
    16721846
    1673        poly* array_arg=(poly*)omalloc(N*sizeof(poly)); // !
    1674        int j = 0;
    1675 
    1676 
    1677       for( unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++ )
    1678       // for all x_v | Ann(lm(h))
    1679       if( p_GetExp(h, v, c->r) ) // TODO: use 'got' here!
    1680       {
    1681         assume(p_GetExp(h, v, c->r)==1);
    1682 
    1683         poly p = sca_pp_Mult_xi_pp(v, pNext, c->r); // x_v * h;
    1684 
    1685         if(p != NULL) // if (x_v * h != 0)
    1686           array_arg[j++] = p;
    1687       } // for all x_v | Ann(lm(h))
    1688 
    1689       c->introduceDelayedPairs(array_arg, j);
    1690 
    1691       omfree(array_arg); // !!!
     1847      poly *array_arg = (poly *) omalloc (N * sizeof (poly));   // !
     1848      int j = 0;
     1849
     1850
     1851      for (unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++)
     1852        // for all x_v | Ann(lm(h))
     1853        if (p_GetExp (h, v, c->r))      // TODO: use 'got' here!
     1854        {
     1855          assume (p_GetExp (h, v, c->r) == 1);
     1856
     1857          poly p = sca_pp_Mult_xi_pp (v, pNext, c->r);  // x_v * h;
     1858
     1859          if (p != NULL)        // if (x_v * h != 0)
     1860            array_arg[j++] = p;
     1861        }                       // for all x_v | Ann(lm(h))
     1862
     1863      c->introduceDelayedPairs (array_arg, j);
     1864
     1865      omfree (array_arg);       // !!!
    16921866    }
    16931867//     PrintS("Saturation - done!!!\n");
     
    16961870
    16971871
    1698   if(!ip)
    1699   {
    1700     qsort(nodes_final,spc_final,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
    1701 
    1702 
    1703     c->apairs=spn_merge(c->apairs,c->pair_top+1,nodes_final,spc_final,c);
    1704     c->pair_top+=spc_final;
    1705     clean_top_of_pair_list(c);
    1706     omfree(nodes_final);
     1872  if (!ip)
     1873  {
     1874    qsort (nodes_final, spc_final, sizeof (sorted_pair_node *),
     1875           tgb_pair_better_gen2);
     1876
     1877
     1878    c->apairs =
     1879      spn_merge (c->apairs, c->pair_top + 1, nodes_final, spc_final, c);
     1880    c->pair_top += spc_final;
     1881    clean_top_of_pair_list (c);
     1882    omfree (nodes_final);
    17071883    return NULL;
    17081884  }
    17091885  {
    1710     *ip=spc_final;
     1886    *ip = spc_final;
    17111887    return nodes_final;
    17121888  }
    17131889}
    17141890
    1715 static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n)
    1716 {
    1717   m=nInit(1);
    1718   if (h==NULL) return NULL;
    1719 
    1720   assume(len==pLength(h));
    1721   kStrategy strat=c->strat;
     1891static poly
     1892redNF2 (poly h, slimgb_alg * c, int &len, number & m, int n)
     1893{
     1894  m = nInit (1);
     1895  if (h == NULL)
     1896    return NULL;
     1897
     1898  assume (len == pLength (h));
     1899  kStrategy strat = c->strat;
    17221900  if (0 > strat->sl)
    17231901  {
     
    17261904  int j;
    17271905
    1728   LObject P(h);
    1729   P.SetShortExpVector();
    1730   P.bucket = kBucketCreate(currRing);
     1906  LObject P (h);
     1907  P.SetShortExpVector ();
     1908  P.bucket = kBucketCreate (currRing);
    17311909  // BOOLEAN corr=lenS_correct(strat);
    1732   kBucketInit(P.bucket,P.p,len /*pLength(P.p)*/);
     1910  kBucketInit (P.bucket, P.p, len /*pLength(P.p) */ );
    17331911  //wlen_set lenSw=(wlen_set) c->strat->lenS;
    17341912  //FIXME: plainly wrong
     
    17391917  loop
    17401918  {
    1741       //int dummy=strat->sl;
    1742       j=kFindDivisibleByInS_easy(strat,P.p,P.sev);
    1743       //j=kFindDivisibleByInS(strat,&dummy,&P);
    1744       if ((j>=0) && ((!n)||
    1745         ((strat->lenS[j]<=n) &&
    1746          ((strat->lenSw==NULL)||
    1747          (strat->lenSw[j]<=n)))))
    1748       {
    1749         nNormalize(pGetCoeff(P.p));
     1919    //int dummy=strat->sl;
     1920    j = kFindDivisibleByInS_easy (strat, P.p, P.sev);
     1921    //j=kFindDivisibleByInS(strat,&dummy,&P);
     1922    if ((j >= 0) && ((!n) ||
     1923                     ((strat->lenS[j] <= n) &&
     1924                      ((strat->lenSw == NULL) || (strat->lenSw[j] <= n)))))
     1925    {
     1926      nNormalize (pGetCoeff (P.p));
    17501927#ifdef KDEBUG
    1751         if (TEST_OPT_DEBUG)
    1752         {
    1753           PrintS("red:");
    1754           wrp(h);
    1755           PrintS(" with ");
    1756           wrp(strat->S[j]);
    1757         }
    1758 #endif
    1759 
    1760         number coef=kBucketPolyRed(P.bucket,strat->S[j],
    1761                                    strat->lenS[j]/*pLength(strat->S[j])*/,
    1762                                    strat->kNoether);
    1763   number m2=nMult(m,coef);
    1764   nDelete(&m);
    1765   m=m2;
    1766         nDelete(&coef);
    1767         h = kBucketGetLm(P.bucket);
    1768 
    1769   if (h==NULL) {
    1770     len=0;
    1771     kBucketDestroy(&P.bucket);
    1772     return
    1773     NULL;}
    1774         P.p=h;
    1775         P.t_p=NULL;
    1776         P.SetShortExpVector();
     1928      if (TEST_OPT_DEBUG)
     1929      {
     1930        PrintS ("red:");
     1931        wrp (h);
     1932        PrintS (" with ");
     1933        wrp (strat->S[j]);
     1934      }
     1935#endif
     1936
     1937      number coef = kBucketPolyRed (P.bucket, strat->S[j],
     1938                                    strat->lenS[j] /*pLength(strat->S[j]) */ ,
     1939                                    strat->kNoether);
     1940      number m2 = nMult (m, coef);
     1941      nDelete (&m);
     1942      m = m2;
     1943      nDelete (&coef);
     1944      h = kBucketGetLm (P.bucket);
     1945
     1946      if (h == NULL)
     1947      {
     1948        len = 0;
     1949        kBucketDestroy (&P.bucket);
     1950        return NULL;
     1951      }
     1952      P.p = h;
     1953      P.t_p = NULL;
     1954      P.SetShortExpVector ();
    17771955#ifdef KDEBUG
    1778         if (TEST_OPT_DEBUG)
    1779         {
    1780           PrintS("\nto:");
    1781           wrp(h);
    1782           PrintLn();
    1783         }
    1784 #endif
    1785       }
    1786       else
    1787       {
    1788         kBucketClear(P.bucket,&(P.p),&len);
    1789         kBucketDestroy(&P.bucket);
    1790         pNormalize(P.p);
    1791   assume(len==(pLength(P.p)));
    1792         return P.p;
    1793       }
    1794     }
    1795 }
    1796 
    1797 static poly redTailShort(poly h, kStrategy strat)
    1798 {
    1799   if (h==NULL) return NULL;//n_Init(1,currRing);
     1956      if (TEST_OPT_DEBUG)
     1957      {
     1958        PrintS ("\nto:");
     1959        wrp (h);
     1960        PrintLn ();
     1961      }
     1962#endif
     1963    }
     1964    else
     1965    {
     1966      kBucketClear (P.bucket, &(P.p), &len);
     1967      kBucketDestroy (&P.bucket);
     1968      pNormalize (P.p);
     1969      assume (len == (pLength (P.p)));
     1970      return P.p;
     1971    }
     1972  }
     1973}
     1974
     1975static poly
     1976redTailShort (poly h, kStrategy strat)
     1977{
     1978  if (h == NULL)
     1979    return NULL;                //n_Init(1,currRing);
    18001980  if (TEST_V_MODPSOLVSB)
    18011981  {
    1802     bit_reduce(pNext(h), strat->tailRing);
     1982    bit_reduce (pNext (h), strat->tailRing);
    18031983  }
    18041984  int i;
    1805   int len=pLength(h);
    1806   for(i=0;i<=strat->sl;i++)
    1807   {
    1808     if((strat->lenS[i]>2) || ((strat->lenSw!=NULL) && (strat->lenSw[i]>2)))
     1985  int len = pLength (h);
     1986  for (i = 0; i <= strat->sl; i++)
     1987  {
     1988    if ((strat->lenS[i] > 2)
     1989        || ((strat->lenSw != NULL) && (strat->lenSw[i] > 2)))
    18091990      break;
    18101991  }
    1811   return(redNFTail(h,i-1,strat, len));
    1812 }
    1813 
    1814 static void line_of_extended_prod(int fixpos,slimgb_alg* c)
    1815 {
    1816     if (c->gcd_of_terms[fixpos]==NULL)
    1817   {
    1818     c->gcd_of_terms[fixpos]=gcd_of_terms(c->S->m[fixpos],c->r);
     1992  return (redNFTail (h, i - 1, strat, len));
     1993}
     1994
     1995static void
     1996line_of_extended_prod (int fixpos, slimgb_alg * c)
     1997{
     1998  if (c->gcd_of_terms[fixpos] == NULL)
     1999  {
     2000    c->gcd_of_terms[fixpos] = gcd_of_terms (c->S->m[fixpos], c->r);
    18192001    if (c->gcd_of_terms[fixpos])
    18202002    {
    18212003      int i;
    1822       for(i=0;i<fixpos;i++)
    1823         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)))
    1824 {
    1825           c->states[fixpos][i]=HASTREP;
    1826     c->extended_product_crit++;
    1827 }
    1828       for(i=fixpos+1;i<c->n;i++)
    1829         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)))
    1830   {        c->states[i][fixpos]=HASTREP;
    1831   c->extended_product_crit++;
    1832   }
    1833     }
    1834   }
    1835 }
    1836 static void c_S_element_changed_hook(int pos, slimgb_alg* c)
    1837 {
    1838   length_one_crit(c,pos, c->lengths[pos]);
     2004      for (i = 0; i < fixpos; i++)
     2005        if ((c->states[fixpos][i] != HASTREP)
     2006            &&
     2007            (extended_product_criterion
     2008             (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i],
     2009              c->gcd_of_terms[i], c)))
     2010        {
     2011          c->states[fixpos][i] = HASTREP;
     2012          c->extended_product_crit++;
     2013        }
     2014      for (i = fixpos + 1; i < c->n; i++)
     2015        if ((c->states[i][fixpos] != HASTREP)
     2016            &&
     2017            (extended_product_criterion
     2018             (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i],
     2019              c->gcd_of_terms[i], c)))
     2020        {
     2021          c->states[i][fixpos] = HASTREP;
     2022          c->extended_product_crit++;
     2023        }
     2024    }
     2025  }
     2026}
     2027
     2028static void
     2029c_S_element_changed_hook (int pos, slimgb_alg * c)
     2030{
     2031  length_one_crit (c, pos, c->lengths[pos]);
    18392032  if (!c->nc)
    1840     line_of_extended_prod(pos,c);
    1841 }
    1842 class poly_tree_node {
     2033    line_of_extended_prod (pos, c);
     2034}
     2035
     2036class poly_tree_node
     2037{
    18432038public:
    18442039  poly p;
    1845   poly_tree_node* l;
    1846   poly_tree_node* r;
     2040  poly_tree_node *l;
     2041  poly_tree_node *r;
    18472042  int n;
    1848   poly_tree_node(int sn):l(NULL),r(NULL),n(sn)
    1849   {}
     2043    poly_tree_node (int sn):l (NULL), r (NULL), n (sn)
     2044  {
     2045  }
    18502046};
    1851 class exp_number_builder{
     2047class exp_number_builder
     2048{
    18522049public:
    1853   poly_tree_node* top_level;
     2050  poly_tree_node * top_level;
    18542051  int n;
    1855   int get_n(poly p);
    1856   exp_number_builder():top_level(0),n(0)
    1857   {}
     2052  int get_n (poly p);
     2053    exp_number_builder ():top_level (0), n (0)
     2054  {
     2055  }
    18582056};
    1859 int exp_number_builder::get_n(poly p)
    1860 {
    1861   poly_tree_node** node=&top_level;
    1862   while(*node!=NULL)
    1863   {
    1864     int c=pLmCmp(p,(*node)->p);
    1865     if (c==0) return (*node)->n;
    1866     if (c==-1) node=&((*node)->r);
     2057int
     2058exp_number_builder::get_n (poly p)
     2059{
     2060  poly_tree_node **node = &top_level;
     2061  while (*node != NULL)
     2062  {
     2063    int c = pLmCmp (p, (*node)->p);
     2064    if (c == 0)
     2065      return (*node)->n;
     2066    if (c == -1)
     2067      node = &((*node)->r);
    18672068    else
    1868       node=&((*node)->l);
    1869   }
    1870   (*node)= new poly_tree_node(n);
     2069      node = &((*node)->l);
     2070  }
     2071  (*node) = new poly_tree_node (n);
    18712072  n++;
    1872   (*node)->p=pLmInit(p);
     2073  (*node)->p = pLmInit (p);
    18732074  return (*node)->n;
    18742075}
     
    18782079
    18792080//! obsolete
    1880 struct int_poly_pair{
     2081struct int_poly_pair
     2082{
    18812083  poly p;
    18822084  int n;
     
    18852087
    18862088//! obsolete
    1887 void t2ippa_rec(poly* ip,int* ia, poly_tree_node* k, int &offset)
    1888 {
    1889     if(!k) return;
    1890     t2ippa_rec(ip,ia,k->l,offset);
    1891     ip[offset]=k->p;
    1892     ia[k->n]=offset;
    1893     ++offset;
    1894 
    1895     t2ippa_rec(ip,ia,k->r,offset);
    1896     delete k;
    1897   }
     2089void
     2090t2ippa_rec (poly * ip, int *ia, poly_tree_node * k, int &offset)
     2091{
     2092  if (!k)
     2093    return;
     2094  t2ippa_rec (ip, ia, k->l, offset);
     2095  ip[offset] = k->p;
     2096  ia[k->n] = offset;
     2097  ++offset;
     2098
     2099  t2ippa_rec (ip, ia, k->r, offset);
     2100  delete k;
     2101}
    18982102
    18992103//! obsolete
    1900 void t2ippa(poly* ip,int* ia,exp_number_builder & e)
    1901 {
    1902 
    1903   int o=0;
    1904   t2ippa_rec(ip,ia,e.top_level,o);
    1905 }
    1906 int anti_poly_order(const void* a, const void* b)
    1907 {
    1908   return -pLmCmp(((int_poly_pair*) a)->p,((int_poly_pair*) b)->p );
    1909 }
    1910 
    1911 BOOLEAN is_valid_ro(red_object & ro)
    1912 {
    1913   red_object r2=ro;
    1914   ro.validate();
    1915   if ((r2.p!=ro.p)||(r2.sev!=ro.sev)) return FALSE;
     2104void
     2105t2ippa (poly * ip, int *ia, exp_number_builder & e)
     2106{
     2107
     2108  int o = 0;
     2109  t2ippa_rec (ip, ia, e.top_level, o);
     2110}
     2111
     2112int
     2113anti_poly_order (const void *a, const void *b)
     2114{
     2115  return -pLmCmp (((int_poly_pair *) a)->p, ((int_poly_pair *) b)->p);
     2116}
     2117
     2118BOOLEAN
     2119is_valid_ro (red_object & ro)
     2120{
     2121  red_object r2 = ro;
     2122  ro.validate ();
     2123  if ((r2.p != ro.p) || (r2.sev != ro.sev))
     2124    return FALSE;
    19162125  return TRUE;
    19172126}
    1918 int terms_sort_crit(const void* a, const void* b)
    1919 {
    1920   return -pLmCmp(*((poly*) a),*((poly*) b));
    1921 }
    1922 #if 0 // currently unused
    1923 static void unify_terms(poly* terms,int & sum)
    1924 {
    1925   if (sum==0) return;
    1926   int last=0;
    1927   int curr=1;
    1928   while(curr<sum)
    1929   {
    1930     if (!(pLmEqual(terms[curr],terms[last])))
    1931     {
    1932       terms[++last]=terms[curr];
     2127
     2128int
     2129terms_sort_crit (const void *a, const void *b)
     2130{
     2131  return -pLmCmp (*((poly *) a), *((poly *) b));
     2132}
     2133
     2134#if 0                           // currently unused
     2135static void
     2136unify_terms (poly * terms, int &sum)
     2137{
     2138  if (sum == 0)
     2139    return;
     2140  int last = 0;
     2141  int curr = 1;
     2142  while (curr < sum)
     2143  {
     2144    if (!(pLmEqual (terms[curr], terms[last])))
     2145    {
     2146      terms[++last] = terms[curr];
    19332147    }
    19342148    ++curr;
    19352149  }
    1936   sum=last+1;
    1937 }
    1938 #endif
    1939 #if 0 // currently unused
    1940 static void export_mat(number* number_array,int pn, int tn,const char* format_str, int mat_nr)
     2150  sum = last + 1;
     2151}
     2152#endif
     2153#if 0                           // currently unused
     2154static void
     2155export_mat (number * number_array, int pn, int tn, const char *format_str,
     2156            int mat_nr)
    19412157{
    19422158  char matname[20];
    1943   sprintf(matname,format_str,mat_nr);
    1944   FILE* out=fopen(matname,"w");
    1945   int i,j;
    1946   fprintf(out,"mat=[\n");
    1947   for(i=0;i<pn;i++)
    1948   {
    1949     fprintf(out,"[\n");
    1950     for(j=0;j<tn;j++)
    1951     {
    1952       if (j>0)
    1953       {
    1954         fprintf(out,", ");
    1955       }
    1956       fprintf(out,"%i",npInt(number_array[i*tn+j],currRing));
    1957     }
    1958     if (i<pn-1)
    1959       fprintf(out,"],\n");
     2159  sprintf (matname, format_str, mat_nr);
     2160  FILE *out = fopen (matname, "w");
     2161  int i, j;
     2162  fprintf (out, "mat=[\n");
     2163  for (i = 0; i < pn; i++)
     2164  {
     2165    fprintf (out, "[\n");
     2166    for (j = 0; j < tn; j++)
     2167    {
     2168      if (j > 0)
     2169      {
     2170        fprintf (out, ", ");
     2171      }
     2172      fprintf (out, "%i", npInt (number_array[i * tn + j], currRing));
     2173    }
     2174    if (i < pn - 1)
     2175      fprintf (out, "],\n");
    19602176    else
    1961       fprintf(out,"],\n");
    1962   }
    1963   fprintf(out,"]\n");
    1964   fclose(out);
     2177      fprintf (out, "],\n");
     2178  }
     2179  fprintf (out, "]\n");
     2180  fclose (out);
    19652181}
    19662182#endif
     
    19702186#ifdef USE_NORO
    19712187#ifndef NORO_CACHE
    1972 static void linalg_step_modp(poly *p, poly* p_out, int& pn, poly* terms,int tn, slimgb_alg* c)
    1973 {
    1974   static int export_n=0;
    1975   assume(terms[tn-1]!=NULL);
    1976   assume(rField_is_Zp(c->r));
     2188static void
     2189linalg_step_modp (poly * p, poly * p_out, int &pn, poly * terms, int tn,
     2190                  slimgb_alg * c)
     2191{
     2192  static int export_n = 0;
     2193  assume (terms[tn - 1] != NULL);
     2194  assume (rField_is_Zp (c->r));
    19772195  //I don't do deletes, copies of number_types ...
    1978   const number_type zero=0;//npInit(0);
    1979   int array_size=pn*tn;
    1980   number_type* number_array=(number_type*) omalloc(pn*tn*sizeof(number_type));
     2196  const number_type zero = 0;   //npInit(0);
     2197  int array_size = pn * tn;
     2198  number_type *number_array =
     2199    (number_type *) omalloc (pn * tn * sizeof (number_type));
    19812200  int i;
    1982   for(i=0;i<array_size;i++)
    1983   {
    1984     number_array[i]=zero;
    1985   }
    1986   for(i=0;i<pn;i++)
    1987   {
    1988     poly h=p[i];
     2201  for (i = 0; i < array_size; i++)
     2202  {
     2203    number_array[i] = zero;
     2204  }
     2205  for (i = 0; i < pn; i++)
     2206  {
     2207    poly h = p[i];
    19892208    //int base=tn*i;
    1990     write_poly_to_row(number_array+tn*i,h,terms,tn,c->r);
     2209    write_poly_to_row (number_array + tn * i, h, terms, tn, c->r);
    19912210
    19922211  }
    19932212#if 0
    19942213  //export matrix
    1995   export_mat(number_array,pn,tn,"mat%i.py",++export_n);
    1996 #endif
    1997   int rank=pn;
    1998   simplest_gauss_modp(number_array,rank,tn);
    1999   int act_row=0;
    2000   int p_pos=0;
    2001   for(i=0;i<pn;i++)
    2002   {
    2003     poly h=NULL;
     2214  export_mat (number_array, pn, tn, "mat%i.py", ++export_n);
     2215#endif
     2216  int rank = pn;
     2217  simplest_gauss_modp (number_array, rank, tn);
     2218  int act_row = 0;
     2219  int p_pos = 0;
     2220  for (i = 0; i < pn; i++)
     2221  {
     2222    poly h = NULL;
    20042223    int j;
    2005     int base=tn*i;
    2006     number* row=number_array+base;
    2007     h=row_to_poly(row,terms,tn,c->r);
    2008 
    2009    if (h!=NULL)
    2010    {
    2011      p_out[p_pos++]=h;
    2012    }
    2013   }
    2014   pn=p_pos;
     2224    int base = tn * i;
     2225    number *row = number_array + base;
     2226    h = row_to_poly (row, terms, tn, c->r);
     2227
     2228    if (h != NULL)
     2229    {
     2230      p_out[p_pos++] = h;
     2231    }
     2232  }
     2233  pn = p_pos;
    20152234  //assert(p_pos==rank)
    2016   while(p_pos<pn)
    2017   {
    2018     p_out[p_pos++]=NULL;
     2235  while (p_pos < pn)
     2236  {
     2237    p_out[p_pos++] = NULL;
    20192238  }
    20202239#if 0
    2021   export_mat(number_array,pn,tn,"mat%i.py",++export_n);
    2022 #endif
    2023 }
    2024 #endif
    2025 #endif
    2026 static void mass_add(poly* p, int pn,slimgb_alg* c)
    2027 {
    2028     int j;
    2029     int* ibuf=(int*) omalloc(pn*sizeof(int));
    2030     sorted_pair_node*** sbuf=(sorted_pair_node***) omalloc(pn*sizeof(sorted_pair_node**));
    2031     for(j=0;j<pn;j++)
    2032     {
    2033       p_Test(p[j],c->r);
    2034       sbuf[j]=add_to_basis_ideal_quotient(p[j],c,ibuf+j);
    2035     }
    2036     int sum=0;
    2037     for(j=0;j<pn;j++)
    2038     {
    2039       sum+=ibuf[j];
    2040     }
    2041     sorted_pair_node** big_sbuf=(sorted_pair_node**) omalloc(sum*sizeof(sorted_pair_node*));
    2042     int partsum=0;
    2043     for(j=0;j<pn;j++)
    2044     {
    2045       memmove(big_sbuf+partsum, sbuf[j],ibuf[j]*sizeof(sorted_pair_node*));
    2046       omfree(sbuf[j]);
    2047       partsum+=ibuf[j];
    2048     }
    2049 
    2050     qsort(big_sbuf,sum,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
    2051     c->apairs=spn_merge(c->apairs,c->pair_top+1,big_sbuf,sum,c);
    2052     c->pair_top+=sum;
    2053     clean_top_of_pair_list(c);
    2054     omfree(big_sbuf);
    2055     omfree(sbuf);
    2056     omfree(ibuf);
    2057     //omfree(buf);
    2058   #ifdef TGB_DEBUG
    2059     int z;
    2060     for(z=1;z<=c->pair_top;z++)
    2061     {
    2062       assume(pair_better(c->apairs[z],c->apairs[z-1],c));
    2063     }
    2064   #endif
     2240  export_mat (number_array, pn, tn, "mat%i.py", ++export_n);
     2241#endif
     2242}
     2243#endif
     2244#endif
     2245static void
     2246mass_add (poly * p, int pn, slimgb_alg * c)
     2247{
     2248  int j;
     2249  int *ibuf = (int *) omalloc (pn * sizeof (int));
     2250  sorted_pair_node ***sbuf =
     2251    (sorted_pair_node ***) omalloc (pn * sizeof (sorted_pair_node **));
     2252  for (j = 0; j < pn; j++)
     2253  {
     2254    p_Test (p[j], c->r);
     2255    sbuf[j] = add_to_basis_ideal_quotient (p[j], c, ibuf + j);
     2256  }
     2257  int sum = 0;
     2258  for (j = 0; j < pn; j++)
     2259  {
     2260    sum += ibuf[j];
     2261  }
     2262  sorted_pair_node **big_sbuf =
     2263    (sorted_pair_node **) omalloc (sum * sizeof (sorted_pair_node *));
     2264  int partsum = 0;
     2265  for (j = 0; j < pn; j++)
     2266  {
     2267    memmove (big_sbuf + partsum, sbuf[j],
     2268             ibuf[j] * sizeof (sorted_pair_node *));
     2269    omfree (sbuf[j]);
     2270    partsum += ibuf[j];
     2271  }
     2272
     2273  qsort (big_sbuf, sum, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
     2274  c->apairs = spn_merge (c->apairs, c->pair_top + 1, big_sbuf, sum, c);
     2275  c->pair_top += sum;
     2276  clean_top_of_pair_list (c);
     2277  omfree (big_sbuf);
     2278  omfree (sbuf);
     2279  omfree (ibuf);
     2280  //omfree(buf);
     2281#ifdef TGB_DEBUG
     2282  int z;
     2283  for (z = 1; z <= c->pair_top; z++)
     2284  {
     2285    assume (pair_better (c->apairs[z], c->apairs[z - 1], c));
     2286  }
     2287#endif
    20652288
    20662289}
     
    20682291#ifdef NORO_CACHE
    20692292#ifndef NORO_NON_POLY
    2070 void NoroCache::evaluateRows()
     2293void
     2294NoroCache::evaluateRows ()
    20712295{
    20722296  //after that can evaluate placeholders
    20732297  int i;
    2074   buffer=(number*) omalloc(nIrreducibleMonomials*sizeof(number));
    2075   for(i=0;i<root.branches_len;i++)
    2076   {
    2077     evaluateRows(1,root.branches[i]);
    2078   }
    2079   omfree(buffer);
    2080   buffer=NULL;
    2081 }
    2082 void NoroCache::evaluateRows(int level, NoroCacheNode* node)
    2083 {
    2084   assume(level>=0);
    2085   if (node==NULL) return;
    2086   if (level<pVariables)
    2087   {
    2088     int i,sum;
    2089     for(i=0;i<node->branches_len;i++)
    2090     {
    2091       evaluateRows(level+1,node->branches[i]);
     2298  buffer = (number *) omalloc (nIrreducibleMonomials * sizeof (number));
     2299  for (i = 0; i < root.branches_len; i++)
     2300  {
     2301    evaluateRows (1, root.branches[i]);
     2302  }
     2303  omfree (buffer);
     2304  buffer = NULL;
     2305}
     2306
     2307void
     2308NoroCache::evaluateRows (int level, NoroCacheNode * node)
     2309{
     2310  assume (level >= 0);
     2311  if (node == NULL)
     2312    return;
     2313  if (level < pVariables)
     2314  {
     2315    int i, sum;
     2316    for (i = 0; i < node->branches_len; i++)
     2317    {
     2318      evaluateRows (level + 1, node->branches[i]);
    20922319    }
    20932320  }
    20942321  else
    20952322  {
    2096     DataNoroCacheNode* dn=(DataNoroCacheNode*) node;
    2097     if (dn->value_len!=backLinkCode)
    2098     {
    2099       poly p=dn->value_poly;
    2100       #ifndef NORO_SPARSE_ROWS_PRE
    2101       dn->row=new DenseRow();
    2102       DenseRow* row=dn->row;
    2103       memset(buffer,0,sizeof(number)*nIrreducibleMonomials);
    2104 
    2105       if (p==NULL) {row->array=NULL;row->begin=0;row->end=0; return;}
    2106       int i=0;
     2323    DataNoroCacheNode *dn = (DataNoroCacheNode *) node;
     2324    if (dn->value_len != backLinkCode)
     2325    {
     2326      poly p = dn->value_poly;
     2327#ifndef NORO_SPARSE_ROWS_PRE
     2328      dn->row = new DenseRow ();
     2329      DenseRow *row = dn->row;
     2330      memset (buffer, 0, sizeof (number) * nIrreducibleMonomials);
     2331
     2332      if (p == NULL)
     2333      {
     2334        row->array = NULL;
     2335        row->begin = 0;
     2336        row->end = 0;
     2337        return;
     2338      }
     2339      int i = 0;
    21072340      int idx;
    2108       number* a=buffer;
    2109       while(p)
    2110       {
    2111         DataNoroCacheNode* ref=getCacheReference(p);
    2112 
    2113         idx=ref->term_index;
    2114         assume(idx>=0);
    2115         a[idx]=p_GetCoeff(p,currRing);
    2116         if (i==0) row->begin=idx;
    2117         i++;
    2118         pIter(p);
    2119       }
    2120       row->end=idx+1;
    2121       assume(row->end>row->begin);
    2122       int len=row->end-row->begin;
    2123       row->array=(number*) omalloc((len)*sizeof(number));
    2124       memcpy(row->array,a+row->begin,len*sizeof(number));
    2125       #else
    2126       assume(dn->value_len==pLength(dn->value_poly));
    2127       dn->row=new SparseRow(dn->value_len);
    2128       SparseRow* row=dn->row;
    2129       int i=0;
    2130       while(p)
    2131       {
    2132         DataNoroCacheNode* ref=getCacheReference(p);
    2133 
    2134         int idx=ref->term_index;
    2135         assume(idx>=0);
    2136         row->idx_array[i]=idx;
    2137         row->coef_array[i]=p_GetCoeff(p,currRing);
    2138         i++;
    2139         pIter(p);
    2140       }
    2141       if (i!=dn->value_len)
    2142       {
    2143         PrintS("F4 calc wrong, as poly len was wrong\n");
    2144       }
    2145       assume(i==dn->value_len);
    2146       #endif
    2147     }
    2148   }
    2149 }
    2150 
    2151 void NoroCache::evaluatePlaceHolder(number* row,std::vector<NoroPlaceHolder>& place_holders)
     2341      number *a = buffer;
     2342      while (p)
     2343      {
     2344        DataNoroCacheNode *ref = getCacheReference (p);
     2345
     2346        idx = ref->term_index;
     2347        assume (idx >= 0);
     2348        a[idx] = p_GetCoeff (p, currRing);
     2349        if (i == 0)
     2350          row->begin = idx;
     2351        i++;
     2352        pIter (p);
     2353      }
     2354      row->end = idx + 1;
     2355      assume (row->end > row->begin);
     2356      int len = row->end - row->begin;
     2357      row->array = (number *) omalloc ((len) * sizeof (number));
     2358      memcpy (row->array, a + row->begin, len * sizeof (number));
     2359#else
     2360      assume (dn->value_len == pLength (dn->value_poly));
     2361      dn->row = new SparseRow (dn->value_len);
     2362      SparseRow *row = dn->row;
     2363      int i = 0;
     2364      while (p)
     2365      {
     2366        DataNoroCacheNode *ref = getCacheReference (p);
     2367
     2368        int idx = ref->term_index;
     2369        assume (idx >= 0);
     2370        row->idx_array[i] = idx;
     2371        row->coef_array[i] = p_GetCoeff (p, currRing);
     2372        i++;
     2373        pIter (p);
     2374      }
     2375      if (i != dn->value_len)
     2376      {
     2377        PrintS ("F4 calc wrong, as poly len was wrong\n");
     2378      }
     2379      assume (i == dn->value_len);
     2380#endif
     2381    }
     2382  }
     2383}
     2384
     2385void
     2386NoroCache::evaluatePlaceHolder (number * row,
     2387                                std::vector < NoroPlaceHolder >
     2388                                &place_holders)
    21522389{
    21532390  int i;
    2154   int s=place_holders.size();
    2155   for(i=0;i<s;i++)
    2156   {
    2157     DataNoroCacheNode* ref=place_holders[i].ref;
    2158     number coef=place_holders[i].coef;
    2159     if (ref->value_len==backLinkCode)
    2160     {
    2161       row[ref->term_index]=npAddM(row[ref->term_index],coef);
     2391  int s = place_holders.size ();
     2392  for (i = 0; i < s; i++)
     2393  {
     2394    DataNoroCacheNode *ref = place_holders[i].ref;
     2395    number coef = place_holders[i].coef;
     2396    if (ref->value_len == backLinkCode)
     2397    {
     2398      row[ref->term_index] = npAddM (row[ref->term_index], coef);
    21622399    }
    21632400    else
    21642401    {
    2165       #ifndef NORO_SPARSE_ROWS_PRE
    2166       DenseRow* ref_row=ref->row;
    2167       if (ref_row==NULL) continue;
    2168       number* ref_begin=ref_row->array;
    2169       number* ref_end=ref_row->array+(ref_row->end-ref_row->begin);
    2170       number* my_pos=row+ref_row->begin;
     2402#ifndef NORO_SPARSE_ROWS_PRE
     2403      DenseRow *ref_row = ref->row;
     2404      if (ref_row == NULL)
     2405        continue;
     2406      number *ref_begin = ref_row->array;
     2407      number *ref_end = ref_row->array + (ref_row->end - ref_row->begin);
     2408      number *my_pos = row + ref_row->begin;
    21712409      //TODO npisOne distinction
    2172       if (!(npIsOne(coef)))
    2173       {
    2174         while(ref_begin!=ref_end)
    2175         {
    2176 
    2177           *my_pos=npAddM(*my_pos,npMult(coef,*ref_begin));
    2178           ++ref_begin;
    2179           ++my_pos;
    2180         }
     2410      if (!(npIsOne (coef)))
     2411      {
     2412        while (ref_begin != ref_end)
     2413        {
     2414
     2415          *my_pos = npAddM (*my_pos, npMult (coef, *ref_begin));
     2416          ++ref_begin;
     2417          ++my_pos;
     2418        }
    21812419      }
    21822420      else
    21832421      {
    2184         while(ref_begin!=ref_end)
    2185         {
    2186 
    2187           *my_pos=npAddM(*my_pos,*ref_begin);
    2188           ++ref_begin;
    2189           ++my_pos;
    2190         }
    2191       }
    2192 
    2193     #else
    2194     SparseRow* ref_row=ref->row;
    2195     if (ref_row==NULL) continue;
    2196     int n=ref_row->len;
    2197     int j;
    2198     int* idx_array=ref_row->idx_array;
    2199     number* coef_array=ref_row->coef_array;
    2200     for(j=0;j<n;j++)
    2201     {
    2202       int idx=idx_array[j];
    2203       number ref_coef=coef_array[j];
    2204       row[idx]=npAddM(row[idx],npMult(coef,ref_coef));
    2205     }
    2206     #endif
    2207   }
     2422        while (ref_begin != ref_end)
     2423        {
     2424
     2425          *my_pos = npAddM (*my_pos, *ref_begin);
     2426          ++ref_begin;
     2427          ++my_pos;
     2428        }
     2429      }
     2430
     2431#else
     2432      SparseRow *ref_row = ref->row;
     2433      if (ref_row == NULL)
     2434        continue;
     2435      int n = ref_row->len;
     2436      int j;
     2437      int *idx_array = ref_row->idx_array;
     2438      number *coef_array = ref_row->coef_array;
     2439      for (j = 0; j < n; j++)
     2440      {
     2441        int idx = idx_array[j];
     2442        number ref_coef = coef_array[j];
     2443        row[idx] = npAddM (row[idx], npMult (coef, ref_coef));
     2444      }
     2445#endif
     2446    }
    22082447  }
    22092448}
     
    22132452
    22142453#ifndef NORO_NON_POLY
    2215 MonRedRes noro_red_mon(poly t, BOOLEAN force_unique, NoroCache* cache,slimgb_alg* c)
     2454MonRedRes
     2455noro_red_mon (poly t, BOOLEAN force_unique, NoroCache * cache, slimgb_alg * c)
    22162456{
    22172457  MonRedRes res_holder;
    22182458
    22192459  //wrp(t);
    2220   res_holder.changed=TRUE;
     2460  res_holder.changed = TRUE;
    22212461  if (force_unique)
    22222462  {
    2223     DataNoroCacheNode* ref=cache->getCacheReference(t);
    2224     if (ref!=NULL)
    2225     {
    2226       res_holder.len=ref->value_len;
    2227       if (res_holder.len==NoroCache::backLinkCode)
    2228       {
    2229         res_holder.len=1;
    2230       }
    2231       res_holder.coef=p_GetCoeff(t,c->r);
    2232       res_holder.p=ref->value_poly;
    2233       res_holder.ref=ref;
    2234       res_holder.onlyBorrowed=TRUE;
    2235       res_holder.changed=TRUE;
    2236       p_Delete(&t,c->r);
     2463    DataNoroCacheNode *ref = cache->getCacheReference (t);
     2464    if (ref != NULL)
     2465    {
     2466      res_holder.len = ref->value_len;
     2467      if (res_holder.len == NoroCache::backLinkCode)
     2468      {
     2469        res_holder.len = 1;
     2470      }
     2471      res_holder.coef = p_GetCoeff (t, c->r);
     2472      res_holder.p = ref->value_poly;
     2473      res_holder.ref = ref;
     2474      res_holder.onlyBorrowed = TRUE;
     2475      res_holder.changed = TRUE;
     2476      p_Delete (&t, c->r);
    22372477      return res_holder;
    22382478    }
     
    22412481  {
    22422482    BOOLEAN succ;
    2243     poly cache_lookup=cache->lookup(t,succ, res_holder.len);//don't own this yet
     2483    poly cache_lookup = cache->lookup (t, succ, res_holder.len);        //don't own this yet
    22442484    if (succ)
    22452485    {
    2246       if (cache_lookup==t)
    2247       {
    2248       //know they are equal
    2249       //res_holder.len=1;
    2250 
    2251         res_holder.changed=FALSE;
    2252         res_holder.p=t;
    2253         res_holder.coef=npInit(1);
    2254 
    2255         res_holder.onlyBorrowed=FALSE;
    2256         return res_holder;
    2257       }
    2258 
    2259       res_holder.coef=p_GetCoeff(t,c->r);
    2260       p_Delete(&t,c->r);
    2261 
    2262       res_holder.p=cache_lookup;
    2263 
    2264       res_holder.onlyBorrowed=TRUE;
     2486      if (cache_lookup == t)
     2487      {
     2488        //know they are equal
     2489        //res_holder.len=1;
     2490
     2491        res_holder.changed = FALSE;
     2492        res_holder.p = t;
     2493        res_holder.coef = npInit (1);
     2494
     2495        res_holder.onlyBorrowed = FALSE;
     2496        return res_holder;
     2497      }
     2498
     2499      res_holder.coef = p_GetCoeff (t, c->r);
     2500      p_Delete (&t, c->r);
     2501
     2502      res_holder.p = cache_lookup;
     2503
     2504      res_holder.onlyBorrowed = TRUE;
    22652505      return res_holder;
    22662506
     
    22682508  }
    22692509
    2270   unsigned long sev=p_GetShortExpVector(t,currRing);
    2271   int i=kFindDivisibleByInS_easy(c->strat,t,sev);
    2272   if (i>=0)
    2273   {
    2274     number coef_bak=p_GetCoeff(t,c->r);
    2275 
    2276     p_SetCoeff(t,npInit(1),c->r);
    2277     assume(npIsOne(p_GetCoeff(c->strat->S[i],c->r)));
    2278     number coefstrat=p_GetCoeff(c->strat->S[i],c->r);
    2279 
    2280       //poly t_copy_mon=p_Copy(t,c->r);
    2281     poly exp_diff=cache->temp_term;
    2282     p_ExpVectorDiff(exp_diff,t,c->strat->S[i],c->r);
    2283     p_SetCoeff(exp_diff,npNeg(nInvers(coefstrat)),c->r);
    2284       // nInvers may be npInvers or nvInvers
    2285     p_Setm(exp_diff,c->r);
    2286     assume(c->strat->S[i]!=NULL);
    2287       //poly t_to_del=t;
     2510  unsigned long sev = p_GetShortExpVector (t, currRing);
     2511  int i = kFindDivisibleByInS_easy (c->strat, t, sev);
     2512  if (i >= 0)
     2513  {
     2514    number coef_bak = p_GetCoeff (t, c->r);
     2515
     2516    p_SetCoeff (t, npInit (1), c->r);
     2517    assume (npIsOne (p_GetCoeff (c->strat->S[i], c->r)));
     2518    number coefstrat = p_GetCoeff (c->strat->S[i], c->r);
     2519
     2520    //poly t_copy_mon=p_Copy(t,c->r);
     2521    poly exp_diff = cache->temp_term;
     2522    p_ExpVectorDiff (exp_diff, t, c->strat->S[i], c->r);
     2523    p_SetCoeff (exp_diff, npNeg (nInvers (coefstrat)), c->r);
     2524    // nInvers may be npInvers or nvInvers
     2525    p_Setm (exp_diff, c->r);
     2526    assume (c->strat->S[i] != NULL);
     2527    //poly t_to_del=t;
    22882528    poly res;
    2289     res=pp_Mult_mm(pNext(c->strat->S[i]),exp_diff,c->r);
    2290 
    2291     res_holder.len=c->strat->lenS[i]-1;
    2292     res=noro_red_non_unique(res,res_holder.len,cache,c);
    2293 
    2294     DataNoroCacheNode* ref=cache->insert(t,res,res_holder.len);
    2295     p_Delete(&t,c->r);
    2296       //p_Delete(&t_copy_mon,c->r);
    2297       //res=pMult_nn(res,coef_bak);
    2298     res_holder.changed=TRUE;
    2299     res_holder.p=res;
    2300     res_holder.coef=coef_bak;
    2301     res_holder.onlyBorrowed=TRUE;
    2302     res_holder.ref=ref;
     2529    res = pp_Mult_mm (pNext (c->strat->S[i]), exp_diff, c->r);
     2530
     2531    res_holder.len = c->strat->lenS[i] - 1;
     2532    res = noro_red_non_unique (res, res_holder.len, cache, c);
     2533
     2534    DataNoroCacheNode *ref = cache->insert (t, res, res_holder.len);
     2535    p_Delete (&t, c->r);
     2536    //p_Delete(&t_copy_mon,c->r);
     2537    //res=pMult_nn(res,coef_bak);
     2538    res_holder.changed = TRUE;
     2539    res_holder.p = res;
     2540    res_holder.coef = coef_bak;
     2541    res_holder.onlyBorrowed = TRUE;
     2542    res_holder.ref = ref;
    23032543    return res_holder;
    23042544  }
    23052545  else
    23062546  {
    2307     number coef_bak=p_GetCoeff(t,c->r);
    2308     number one=npInit(1);
    2309     p_SetCoeff(t,one,c->r);
    2310     res_holder.len=1;
     2547    number coef_bak = p_GetCoeff (t, c->r);
     2548    number one = npInit (1);
     2549    p_SetCoeff (t, one, c->r);
     2550    res_holder.len = 1;
    23112551    if (!(force_unique))
    23122552    {
    2313       res_holder.ref=cache->insert(t,t,res_holder.len);
    2314       p_SetCoeff(t,coef_bak,c->r);
     2553      res_holder.ref = cache->insert (t, t, res_holder.len);
     2554      p_SetCoeff (t, coef_bak, c->r);
    23152555      //return t;
    23162556
    23172557      //we need distinction
    2318       res_holder.changed=FALSE;
    2319       res_holder.p=t;
    2320 
    2321       res_holder.coef=npInit(1);
    2322       res_holder.onlyBorrowed=FALSE;
     2558      res_holder.changed = FALSE;
     2559      res_holder.p = t;
     2560
     2561      res_holder.coef = npInit (1);
     2562      res_holder.onlyBorrowed = FALSE;
    23232563      return res_holder;
    23242564    }
    23252565    else
    23262566    {
    2327       res_holder.ref=cache->insertAndTransferOwnerShip(t,c->r);
    2328       res_holder.coef=coef_bak;
    2329       res_holder.onlyBorrowed=TRUE;
    2330       res_holder.changed=FALSE;
    2331       res_holder.p=t;
     2567      res_holder.ref = cache->insertAndTransferOwnerShip (t, c->r);
     2568      res_holder.coef = coef_bak;
     2569      res_holder.onlyBorrowed = TRUE;
     2570      res_holder.changed = FALSE;
     2571      res_holder.p = t;
    23322572      return res_holder;
    23332573    }
     
    23392579#ifndef NORO_NON_POLY
    23402580//len input and out: Idea: reverse addition
    2341 poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c)
    2342 {
    2343   assume(len==pLength(p));
    2344   poly orig_p=p;
    2345   if (p==NULL) {
    2346     len=0;
     2581poly
     2582noro_red_non_unique (poly p, int &len, NoroCache * cache, slimgb_alg * c)
     2583{
     2584  assume (len == pLength (p));
     2585  poly orig_p = p;
     2586  if (p == NULL)
     2587  {
     2588    len = 0;
    23472589    return NULL;
    23482590  }
    2349   kBucket_pt bucket=kBucketCreate(currRing);
    2350   kBucketInit(bucket,NULL,0);
    2351   poly unchanged_head=NULL;
    2352   poly unchanged_tail=NULL;
    2353   int unchanged_size=0;
    2354 
    2355   while(p)
    2356   {
    2357     poly t=p;
    2358     pIter(p);
    2359     pNext(t)=NULL;
     2591  kBucket_pt bucket = kBucketCreate (currRing);
     2592  kBucketInit (bucket, NULL, 0);
     2593  poly unchanged_head = NULL;
     2594  poly unchanged_tail = NULL;
     2595  int unchanged_size = 0;
     2596
     2597  while (p)
     2598  {
     2599    poly t = p;
     2600    pIter (p);
     2601    pNext (t) = NULL;
    23602602#ifndef NDEBUG
    2361     number coef_debug=p_GetCoeff(t,currRing);
    2362 #endif
    2363     MonRedRes red=noro_red_mon(t,FALSE,cache,c);
    2364     if ((!(red.changed))&&(!(red.onlyBorrowed)))
     2603    number coef_debug = p_GetCoeff (t, currRing);
     2604#endif
     2605    MonRedRes red = noro_red_mon (t, FALSE, cache, c);
     2606    if ((!(red.changed)) && (!(red.onlyBorrowed)))
    23652607    {
    23662608      unchanged_size++;
    2367       assume(npIsOne(red.coef));
    2368       assume(p_GetCoeff(red.p,currRing)==coef_debug);
     2609      assume (npIsOne (red.coef));
     2610      assume (p_GetCoeff (red.p, currRing) == coef_debug);
    23692611      if (unchanged_head)
    23702612      {
    2371         pNext(unchanged_tail)=red.p;
    2372         pIter(unchanged_tail);
     2613        pNext (unchanged_tail) = red.p;
     2614        pIter (unchanged_tail);
    23732615      }
    23742616      else
    23752617      {
    2376         unchanged_tail=red.p;
    2377         unchanged_head=red.p;
     2618        unchanged_tail = red.p;
     2619        unchanged_head = red.p;
    23782620      }
    23792621    }
    23802622    else
    23812623    {
    2382       assume(red.len==pLength(red.p));
     2624      assume (red.len == pLength (red.p));
    23832625      if (red.onlyBorrowed)
    23842626      {
    2385         if (npIsOne(red.coef))
    2386         {
    2387           t=p_Copy(red.p,currRing);
    2388         }
    2389         else
    2390         t=pp_Mult_nn(red.p,red.coef,currRing);
     2627        if (npIsOne (red.coef))
     2628        {
     2629          t = p_Copy (red.p, currRing);
     2630        }
     2631        else
     2632          t = pp_Mult_nn (red.p, red.coef, currRing);
    23912633      }
    23922634      else
    23932635      {
    2394         if (npIsOne(red.coef))
    2395         t=red.p;
    2396         else
    2397          t=p_Mult_nn(red.p,red.coef,currRing);
    2398       }
    2399       kBucket_Add_q(bucket,t,&red.len);
    2400     }
    2401   }
    2402   poly res=NULL;
    2403   len=0;
    2404   kBucket_Add_q(bucket,unchanged_head,&unchanged_size);
    2405   kBucketClear(bucket,&res,&len);
    2406   kBucketDestroy(&bucket);
     2636        if (npIsOne (red.coef))
     2637          t = red.p;
     2638        else
     2639          t = p_Mult_nn (red.p, red.coef, currRing);
     2640      }
     2641      kBucket_Add_q (bucket, t, &red.len);
     2642    }
     2643  }
     2644  poly res = NULL;
     2645  len = 0;
     2646  kBucket_Add_q (bucket, unchanged_head, &unchanged_size);
     2647  kBucketClear (bucket, &res, &len);
     2648  kBucketDestroy (&bucket);
    24072649  return res;
    24082650}
     
    24322674//len input and out: Idea: reverse addition
    24332675#ifndef NORO_NON_POLY
    2434 std::vector<NoroPlaceHolder> noro_red(poly p, int &len, NoroCache* cache,slimgb_alg* c)
    2435 {
    2436   std::vector<NoroPlaceHolder> res;
    2437    while(p)
    2438    {
    2439       poly t=p;
    2440       pIter(p);
    2441       pNext(t)=NULL;
    2442 
    2443       MonRedRes red=noro_red_mon(t,TRUE,cache,c);
    2444       assume(red.onlyBorrowed);
    2445       assume(red.coef);
    2446       assume(red.ref);
    2447       NoroPlaceHolder h;
    2448       h.ref=red.ref;
    2449       h.coef=red.coef;
    2450       assume(!((h.ref->value_poly==NULL) &&(h.ref->value_len!=0)));
    2451       if (h.ref->value_poly)
    2452         res.push_back(h);
    2453     }
    2454     return res;
     2676std::vector < NoroPlaceHolder > noro_red (poly p, int &len, NoroCache * cache,
     2677                                          slimgb_alg * c)
     2678{
     2679  std::vector < NoroPlaceHolder > res;
     2680  while (p)
     2681  {
     2682    poly t = p;
     2683    pIter (p);
     2684    pNext (t) = NULL;
     2685
     2686    MonRedRes red = noro_red_mon (t, TRUE, cache, c);
     2687    assume (red.onlyBorrowed);
     2688    assume (red.coef);
     2689    assume (red.ref);
     2690    NoroPlaceHolder h;
     2691    h.ref = red.ref;
     2692    h.coef = red.coef;
     2693    assume (!((h.ref->value_poly == NULL) && (h.ref->value_len != 0)));
     2694    if (h.ref->value_poly)
     2695      res.push_back (h);
     2696  }
     2697  return res;
    24552698}
    24562699#endif
     
    24592702#ifdef USE_NORO
    24602703#ifndef NORO_CACHE
    2461 void noro_step(poly*p,int &pn,slimgb_alg* c)
    2462 {
    2463   poly* reduced=(poly*) omalloc(pn*sizeof(poly));
     2704void
     2705noro_step (poly * p, int &pn, slimgb_alg * c)
     2706{
     2707  poly *reduced = (poly *) omalloc (pn * sizeof (poly));
    24642708  int j;
    2465   int* reduced_len=(int*) omalloc(pn*sizeof(int));
    2466   int reduced_c=0;
     2709  int *reduced_len = (int *) omalloc (pn * sizeof (int));
     2710  int reduced_c = 0;
    24672711  //if (TEST_OPT_PROT)
    24682712  //  PrintS("reduced system:\n");
     
    24702714  NoroCache cache;
    24712715#endif
    2472   for(j=0;j<pn;j++)
    2473   {
    2474 
    2475     poly h=p[j];
    2476     int h_len=pLength(h);
     2716  for (j = 0; j < pn; j++)
     2717  {
     2718
     2719    poly h = p[j];
     2720    int h_len = pLength (h);
    24772721
    24782722    number coef;
    24792723#ifndef NORO_CACHE
    2480     h=redNF2(p_Copy(h,c->r),c,h_len,coef,0);
     2724    h = redNF2 (p_Copy (h, c->r), c, h_len, coef, 0);
    24812725#else
    2482     h=noro_red(p_Copy(h,c->r),h_len,&cache,c);
    2483     assume(pLength(h)==h_len);
    2484 #endif
    2485     if (h!=NULL)
     2726    h = noro_red (p_Copy (h, c->r), h_len, &cache, c);
     2727    assume (pLength (h) == h_len);
     2728#endif
     2729    if (h != NULL)
    24862730    {
    24872731#ifndef NORO_CACHE
    24882732
    2489       h=redNFTail(h,c->strat->sl,c->strat,h_len);
    2490       h_len=pLength(h);
    2491 #endif
    2492       reduced[reduced_c]=h;
    2493       reduced_len[reduced_c]=h_len;
     2733      h = redNFTail (h, c->strat->sl, c->strat, h_len);
     2734      h_len = pLength (h);
     2735#endif
     2736      reduced[reduced_c] = h;
     2737      reduced_len[reduced_c] = h_len;
    24942738      reduced_c++;
    24952739      if (TEST_OPT_PROT)
    2496         Print("%d ",h_len);
    2497     }
    2498   }
    2499   int reduced_sum=0;
    2500   for(j=0;j<reduced_c;j++)
    2501   {
    2502     reduced_sum+=reduced_len[j];
    2503   }
    2504   poly* terms=(poly*) omalloc(reduced_sum*sizeof(poly));
    2505   int tc=0;
    2506   for(j=0;j<reduced_c;j++)
    2507   {
    2508     poly h=reduced[j];
    2509 
    2510     while(h!=NULL)
    2511     {
    2512       terms[tc++]=h;
    2513       pIter(h);
    2514       assume(tc<=reduced_sum);
    2515     }
    2516   }
    2517   assume(tc==reduced_sum);
    2518   qsort(terms,reduced_sum,sizeof(poly),terms_sort_crit);
    2519   int nterms=reduced_sum;
     2740        Print ("%d ", h_len);
     2741    }
     2742  }
     2743  int reduced_sum = 0;
     2744  for (j = 0; j < reduced_c; j++)
     2745  {
     2746    reduced_sum += reduced_len[j];
     2747  }
     2748  poly *terms = (poly *) omalloc (reduced_sum * sizeof (poly));
     2749  int tc = 0;
     2750  for (j = 0; j < reduced_c; j++)
     2751  {
     2752    poly h = reduced[j];
     2753
     2754    while (h != NULL)
     2755    {
     2756      terms[tc++] = h;
     2757      pIter (h);
     2758      assume (tc <= reduced_sum);
     2759    }
     2760  }
     2761  assume (tc == reduced_sum);
     2762  qsort (terms, reduced_sum, sizeof (poly), terms_sort_crit);
     2763  int nterms = reduced_sum;
    25202764  //if (TEST_OPT_PROT)
    25212765  //Print("orig estimation:%i\n",reduced_sum);
    2522   unify_terms(terms,nterms);
     2766  unify_terms (terms, nterms);
    25232767  //if (TEST_OPT_PROT)
    25242768  //    Print("actual number of columns:%i\n",nterms);
    2525   int rank=reduced_c;
    2526   linalg_step_modp(reduced, p,rank,terms,nterms,c);
    2527   omfree(terms);
    2528 
    2529   pn=rank;
    2530   omfree(reduced);
     2769  int rank = reduced_c;
     2770  linalg_step_modp (reduced, p, rank, terms, nterms, c);
     2771  omfree (terms);
     2772
     2773  pn = rank;
     2774  omfree (reduced);
    25312775
    25322776  if (TEST_OPT_PROT)
    2533     PrintS("\n");
     2777    PrintS ("\n");
    25342778}
    25352779#else
     
    25372781#endif
    25382782#endif
    2539 static void go_on (slimgb_alg* c)
     2783static void
     2784go_on (slimgb_alg * c)
    25402785{
    25412786  //set limit of 1000 for multireductions, at the moment for
    25422787  //programming reasons
    2543   #ifdef USE_NORO
     2788#ifdef USE_NORO
    25442789  //Print("module rank%d\n",c->S->rank);
    2545     const BOOLEAN use_noro=c->use_noro;
    2546   #else
    2547   const BOOLEAN use_noro=FALSE;
    2548   #endif
    2549   int i=0;
    2550   c->average_length=0;
    2551   for(i=0;i<c->n;i++)
    2552   {
    2553     c->average_length+=c->lengths[i];
    2554   }
    2555   c->average_length=c->average_length/c->n;
    2556   i=0;
    2557   int max_pairs=bundle_size;
    2558 
    2559   #ifdef USE_NORO
    2560   if ((use_noro)||(c->use_noro_last_block))
    2561     max_pairs=bundle_size_noro;
    2562   #endif
    2563   poly* p=(poly*) omalloc((max_pairs+1)*sizeof(poly));//nullterminated
    2564 
    2565   int curr_deg=-1;
    2566   while(i<max_pairs)
    2567   {
    2568     sorted_pair_node* s=top_pair(c);//here is actually chain criterium done
    2569 
    2570     if (!s) break;
    2571 
    2572     if(curr_deg>=0)
    2573     {
    2574       if (s->deg >curr_deg) break;
    2575     }
    2576 
    2577     else curr_deg=s->deg;
    2578     quick_pop_pair(c);
    2579     if(s->i>=0)
     2790  const BOOLEAN use_noro = c->use_noro;
     2791#else
     2792  const BOOLEAN use_noro = FALSE;
     2793#endif
     2794  int i = 0;
     2795  c->average_length = 0;
     2796  for (i = 0; i < c->n; i++)
     2797  {
     2798    c->average_length += c->lengths[i];
     2799  }
     2800  c->average_length = c->average_length / c->n;
     2801  i = 0;
     2802  int max_pairs = bundle_size;
     2803
     2804#ifdef USE_NORO
     2805  if ((use_noro) || (c->use_noro_last_block))
     2806    max_pairs = bundle_size_noro;
     2807#endif
     2808  poly *p = (poly *) omalloc ((max_pairs + 1) * sizeof (poly)); //nullterminated
     2809
     2810  int curr_deg = -1;
     2811  while (i < max_pairs)
     2812  {
     2813    sorted_pair_node *s = top_pair (c); //here is actually chain criterium done
     2814
     2815    if (!s)
     2816      break;
     2817
     2818    if (curr_deg >= 0)
     2819    {
     2820      if (s->deg > curr_deg)
     2821        break;
     2822    }
     2823
     2824    else
     2825      curr_deg = s->deg;
     2826    quick_pop_pair (c);
     2827    if (s->i >= 0)
    25802828    {
    25812829      //be careful replace_pair use createShortSpoly which is not noncommutative
    2582       now_t_rep(s->i,s->j,c);
    2583     replace_pair(s->i,s->j,c);
    2584 
    2585     if(s->i==s->j) {
    2586       free_sorted_pair_node(s,c->r);
    2587       continue;
    2588     }
    2589     now_t_rep(s->i,s->j,c);
     2830      now_t_rep (s->i, s->j, c);
     2831      replace_pair (s->i, s->j, c);
     2832
     2833      if (s->i == s->j)
     2834      {
     2835        free_sorted_pair_node (s, c->r);
     2836        continue;
     2837      }
     2838      now_t_rep (s->i, s->j, c);
    25902839    }
    25912840    poly h;
    2592     if(s->i>=0)
     2841    if (s->i >= 0)
    25932842    {
    25942843#ifdef HAVE_PLURAL
    25952844      if (c->nc)
    25962845      {
    2597         h= nc_CreateSpoly(c->S->m[s->i], c->S->m[s->j]/*, NULL*/, c->r);
    2598 
    2599         if (h!=NULL)
    2600           p_Cleardenom(h, c->r);
     2846        h = nc_CreateSpoly (c->S->m[s->i], c->S->m[s->j] /*, NULL */ , c->r);
     2847
     2848        if (h != NULL)
     2849          p_Cleardenom (h, c->r);
    26012850      }
    26022851      else
    26032852#endif
    2604         h=ksOldCreateSpoly(c->S->m[s->i], c->S->m[s->j], NULL, c->r);
    2605     p_Test(h,c->r);
     2853        h = ksOldCreateSpoly (c->S->m[s->i], c->S->m[s->j], NULL, c->r);
     2854      p_Test (h, c->r);
    26062855    }
    26072856    else
    26082857    {
    2609       h=s->lcm_of_lm;
    2610       p_Test(h,c->r);
    2611   }
     2858      h = s->lcm_of_lm;
     2859      p_Test (h, c->r);
     2860    }
    26122861    // if(s->i>=0)
    26132862//       now_t_rep(s->j,s->i,c);
    26142863    number coef;
    2615     int mlen=pLength(h);
    2616     p_Test(h,c->r);
    2617     if ((!c->nc)&(!(use_noro)))
    2618     {
    2619       h=redNF2(h,c,mlen,coef,2);
    2620       redTailShort(h,c->strat);
    2621       nDelete(&coef);
    2622     }
    2623     p_Test(h,c->r);
    2624     free_sorted_pair_node(s,c->r);
    2625     if(!h) continue;
    2626     p[i]=h;
     2864    int mlen = pLength (h);
     2865    p_Test (h, c->r);
     2866    if ((!c->nc) & (!(use_noro)))
     2867    {
     2868      h = redNF2 (h, c, mlen, coef, 2);
     2869      redTailShort (h, c->strat);
     2870      nDelete (&coef);
     2871    }
     2872    p_Test (h, c->r);
     2873    free_sorted_pair_node (s, c->r);
     2874    if (!h)
     2875      continue;
     2876    p[i] = h;
    26272877    i++;
    26282878  }
    2629   p[i]=NULL;
     2879  p[i] = NULL;
    26302880//  pre_comp(p,i,c);
    2631   if(i==0)
    2632   {
    2633     omfree(p);
     2881  if (i == 0)
     2882  {
     2883    omfree (p);
    26342884    return;
    26352885  }
    2636   #ifdef TGB_RESORT_PAIRS
    2637   c->replaced=new bool[c->n];
    2638   c->used_b=FALSE;
    2639   #endif
    2640 
    2641   c->normal_forms+=i;
     2886#ifdef TGB_RESORT_PAIRS
     2887  c->replaced = new bool[c->n];
     2888  c->used_b = FALSE;
     2889#endif
     2890
     2891  c->normal_forms += i;
    26422892  int j;
    26432893#ifdef USE_NORO
     
    26462896  if (use_noro)
    26472897  {
    2648     int pn=i;
    2649     if (pn==0) {omfree(p);return;}
    2650     {
    2651       if (npPrimeM<255)
    2652       {
    2653         noro_step<tgb_uint8>(p,pn,c);
     2898    int pn = i;
     2899    if (pn == 0)
     2900    {
     2901      omfree (p);
     2902      return;
     2903    }
     2904    {
     2905      if (npPrimeM < 255)
     2906      {
     2907        noro_step < tgb_uint8 > (p, pn, c);
    26542908      }
    26552909      else
    26562910      {
    2657         if (npPrimeM<65000)
    2658         {
    2659           noro_step<tgb_uint16>(p,pn,c);
    2660         }
    2661         else
    2662         {
    2663           noro_step<tgb_uint32>(p,pn,c);
    2664         }
     2911        if (npPrimeM < 65000)
     2912        {
     2913          noro_step < tgb_uint16 > (p, pn, c);
     2914        }
     2915        else
     2916        {
     2917          noro_step < tgb_uint32 > (p, pn, c);
     2918        }
    26652919      }
    26662920    }
     
    26702924    //  Print("reported rank:%i\n",pn);
    26712925    //}
    2672     mass_add(p,pn,c);
    2673     omfree(p);
     2926    mass_add (p, pn, c);
     2927    omfree (p);
    26742928    return;
    26752929    /*if (TEST_OPT_PROT)
    2676       for(j=0;j<pn;j++)
    2677       {
    2678         p_wrp(p[j],c->r);
    2679       }*/
    2680   }
    2681 #endif
    2682   red_object* buf=(red_object*) omalloc(i*sizeof(red_object));
    2683   for(j=0;j<i;j++)
    2684   {
    2685     p_Test(p[j],c->r);
    2686     buf[j].p=p[j];
    2687     buf[j].sev=pGetShortExpVector(p[j]);
    2688     buf[j].bucket = kBucketCreate(currRing);
    2689     p_Test(p[j],c->r);
     2930       for(j=0;j<pn;j++)
     2931       {
     2932       p_wrp(p[j],c->r);
     2933       } */
     2934  }
     2935#endif
     2936  red_object *buf = (red_object *) omalloc (i * sizeof (red_object));
     2937  for (j = 0; j < i; j++)
     2938  {
     2939    p_Test (p[j], c->r);
     2940    buf[j].p = p[j];
     2941    buf[j].sev = pGetShortExpVector (p[j]);
     2942    buf[j].bucket = kBucketCreate (currRing);
     2943    p_Test (p[j], c->r);
    26902944    if (c->eliminationProblem)
    26912945    {
    2692         buf[j].sugar=c->pTotaldegree_full(p[j]);
    2693     }
    2694     int len=pLength(p[j]);
    2695     kBucketInit(buf[j].bucket,buf[j].p,len);
    2696     buf[j].initial_quality=buf[j].guess_quality(c);
    2697     assume(buf[j].initial_quality>=0);
    2698   }
    2699   omfree(p);
    2700   qsort(buf,i,sizeof(red_object),red_object_better_gen);
     2946      buf[j].sugar = c->pTotaldegree_full (p[j]);
     2947    }
     2948    int len = pLength (p[j]);
     2949    kBucketInit (buf[j].bucket, buf[j].p, len);
     2950    buf[j].initial_quality = buf[j].guess_quality (c);
     2951    assume (buf[j].initial_quality >= 0);
     2952  }
     2953  omfree (p);
     2954  qsort (buf, i, sizeof (red_object), red_object_better_gen);
    27012955//    Print("\ncurr_deg:%i\n",curr_deg);
    27022956  if (TEST_OPT_PROT)
    27032957  {
    2704     Print("%dM[%d,",curr_deg,i);
    2705   }
    2706 
    2707   multi_reduction(buf, i, c);
    2708   #ifdef TGB_RESORT_PAIRS
    2709   if (c->used_b) {
     2958    Print ("%dM[%d,", curr_deg, i);
     2959  }
     2960
     2961  multi_reduction (buf, i, c);
     2962#ifdef TGB_RESORT_PAIRS
     2963  if (c->used_b)
     2964  {
    27102965    if (TEST_OPT_PROT)
    2711         PrintS("B");
     2966      PrintS ("B");
    27122967    int e;
    2713     for(e=0;e<=c->pair_top;e++)
    2714     {
    2715         if(c->apairs[e]->i<0) continue;
    2716         assume(c->apairs[e]->j>=0);
    2717         if ((c->replaced[c->apairs[e]->i])||(c->replaced[c->apairs[e]->j])) {
    2718             sorted_pair_node* s=c->apairs[e];
    2719             s->expected_length=pair_weighted_length(s->i,s->j,c);
    2720         }
    2721     }
    2722     qsort(c->apairs,c->pair_top+1,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
    2723   }
    2724   #endif
     2968    for (e = 0; e <= c->pair_top; e++)
     2969    {
     2970      if (c->apairs[e]->i < 0)
     2971        continue;
     2972      assume (c->apairs[e]->j >= 0);
     2973      if ((c->replaced[c->apairs[e]->i]) || (c->replaced[c->apairs[e]->j]))
     2974      {
     2975        sorted_pair_node *s = c->apairs[e];
     2976        s->expected_length = pair_weighted_length (s->i, s->j, c);
     2977      }
     2978    }
     2979    qsort (c->apairs, c->pair_top + 1, sizeof (sorted_pair_node *),
     2980           tgb_pair_better_gen2);
     2981  }
     2982#endif
    27252983#ifdef TGB_DEBUG
    2726  {
    2727    int k;
    2728    for(k=0;k<i;k++)
    2729    {
    2730      assume(kFindDivisibleByInS_easy(c->strat,buf[k])<0);
    2731      int k2;
    2732      for(k2=0;k2<i;k2++)
    2733      {
    2734        if(k==k2) continue;
    2735        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));
    2736      }
    2737    }
    2738  }
     2984  {
     2985    int k;
     2986    for (k = 0; k < i; k++)
     2987    {
     2988      assume (kFindDivisibleByInS_easy (c->strat, buf[k]) < 0);
     2989      int k2;
     2990      for (k2 = 0; k2 < i; k2++)
     2991      {
     2992        if (k == k2)
     2993          continue;
     2994        assume ((!(p_LmDivisibleBy (buf[k].p, buf[k2].p, c->r)))
     2995                || (wrp (buf[k].p), Print (" k %d k2 %d ", k, k2),
     2996                    wrp (buf[k2].p), FALSE));
     2997      }
     2998    }
     2999  }
    27393000#endif
    27403001  //resort S
    27413002
    27423003  if (TEST_OPT_PROT)
    2743       Print("%i]",i);
    2744 
    2745   poly* add_those=(poly*) omalloc(i*sizeof(poly));
    2746   for(j=0;j<i;j++)
     3004    Print ("%i]", i);
     3005
     3006  poly *add_those = (poly *) omalloc (i * sizeof (poly));
     3007  for (j = 0; j < i; j++)
    27473008  {
    27483009    int len;
    27493010    poly p;
    2750     buf[j].flatten();
    2751     kBucketClear(buf[j].bucket,&p, &len);
    2752     kBucketDestroy(&buf[j].bucket);
    2753     p_Test(p,c->r);
     3011    buf[j].flatten ();
     3012    kBucketClear (buf[j].bucket, &p, &len);
     3013    kBucketDestroy (&buf[j].bucket);
     3014    p_Test (p, c->r);
    27543015    //if (!c->nc) {
    2755       if ((c->tailReductions) ||(lies_in_last_dp_block(p,c)))
    2756       {
    2757       p=redNFTail(p,c->strat->sl,c->strat, 0);
    2758       }
    2759       else
    2760       {
    2761       p=redTailShort(p, c->strat);
    2762       }
    2763       //}
    2764       p_Test(p,c->r);
    2765       add_those[j]=p;
     3016    if ((c->tailReductions) || (lies_in_last_dp_block (p, c)))
     3017    {
     3018      p = redNFTail (p, c->strat->sl, c->strat, 0);
     3019    }
     3020    else
     3021    {
     3022      p = redTailShort (p, c->strat);
     3023    }
     3024    //}
     3025    p_Test (p, c->r);
     3026    add_those[j] = p;
    27663027
    27673028    //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
    27683029  }
    2769   mass_add(add_those,i,c);
    2770   omfree(add_those);
    2771   omfree(buf);
     3030  mass_add (add_those, i, c);
     3031  omfree (add_those);
     3032  omfree (buf);
    27723033
    27733034  if (TEST_OPT_PROT)
    2774       Print("(%d)",c->pair_top+1);
     3035    Print ("(%d)", c->pair_top + 1);
    27753036  //TODO: implement that while(!(idIs0(c->add_later)))
    2776   #ifdef TGB_RESORT_PAIRS
     3037#ifdef TGB_RESORT_PAIRS
    27773038  delete c->replaced;
    2778   c->replaced=NULL;
    2779   c->used_b=FALSE;
    2780   #endif
     3039  c->replaced = NULL;
     3040  c->used_b = FALSE;
     3041#endif
    27813042  return;
    27823043}
     
    27843045#ifdef REDTAIL_S
    27853046
    2786 static poly redNFTail (poly h,const int sl,kStrategy strat, int len)
    2787 {
    2788   BOOLEAN nc=rIsPluralRing(currRing);
    2789   if (h==NULL) return NULL;
    2790   pTest(h);
     3047static poly
     3048redNFTail (poly h, const int sl, kStrategy strat, int len)
     3049{
     3050  BOOLEAN nc = rIsPluralRing (currRing);
     3051  if (h == NULL)
     3052    return NULL;
     3053  pTest (h);
    27913054  if (0 > sl)
    27923055    return h;
    2793   if (pNext(h)==NULL) return h;
     3056  if (pNext (h) == NULL)
     3057    return h;
    27943058
    27953059  int j;
    2796   poly res=h;
    2797   poly act=res;
    2798   LObject P(pNext(h));
    2799   pNext(res)=NULL;
    2800   P.bucket = kBucketCreate(currRing);
     3060  poly res = h;
     3061  poly act = res;
     3062  LObject P (pNext (h));
     3063  pNext (res) = NULL;
     3064  P.bucket = kBucketCreate (currRing);
    28013065  len--;
    2802   h=P.p;
    2803   if (len <=0) len=pLength(h);
    2804   kBucketInit(P.bucket,h /*P.p*/,len /*pLength(P.p)*/);
    2805   pTest(h);
     3066  h = P.p;
     3067  if (len <= 0)
     3068    len = pLength (h);
     3069  kBucketInit (P.bucket, h /*P.p */ , len /*pLength(P.p) */ );
     3070  pTest (h);
    28063071  loop
    28073072  {
    2808       P.p=h;
    2809       P.t_p=NULL;
    2810       P.SetShortExpVector();
    2811       loop
    2812       {
    2813           //int dummy=strat->sl;
    2814           j=kFindDivisibleByInS_easy(strat,P.p,P.sev);//kFindDivisibleByInS(strat,&dummy,&P);
    2815           if (j>=0)
    2816           {
     3073    P.p = h;
     3074    P.t_p = NULL;
     3075    P.SetShortExpVector ();
     3076    loop
     3077    {
     3078      //int dummy=strat->sl;
     3079      j = kFindDivisibleByInS_easy (strat, P.p, P.sev); //kFindDivisibleByInS(strat,&dummy,&P);
     3080      if (j >= 0)
     3081      {
    28173082#ifdef REDTAIL_PROT
    2818             PrintS("r");
    2819 #endif
    2820             nNormalize(pGetCoeff(P.p));
     3083        PrintS ("r");
     3084#endif
     3085        nNormalize (pGetCoeff (P.p));
    28213086#ifdef KDEBUG
    2822             if (TEST_OPT_DEBUG)
    2823             {
    2824               PrintS("red tail:");
    2825               wrp(h);
    2826               PrintS(" with ");
    2827               wrp(strat->S[j]);
    2828             }
    2829 #endif
    2830             number coef;
    2831             pTest(strat->S[j]);
     3087        if (TEST_OPT_DEBUG)
     3088        {
     3089          PrintS ("red tail:");
     3090          wrp (h);
     3091          PrintS (" with ");
     3092          wrp (strat->S[j]);
     3093        }
     3094#endif
     3095        number coef;
     3096        pTest (strat->S[j]);
    28323097#ifdef HAVE_PLURAL
    2833             if (nc)
    2834             {
    2835               nc_BucketPolyRed_Z(P.bucket, strat->S[j], &coef);
    2836             }
    2837             else
    2838 #endif
    2839               coef=kBucketPolyRed(P.bucket,strat->S[j],
    2840                                 strat->lenS[j]/*pLength(strat->S[j])*/,strat->kNoether);
    2841             pMult_nn(res,coef);
    2842             nDelete(&coef);
    2843             h = kBucketGetLm(P.bucket);
    2844             pTest(h);
    2845             if (h==NULL)
    2846             {
     3098        if (nc)
     3099        {
     3100          nc_BucketPolyRed_Z (P.bucket, strat->S[j], &coef);
     3101        }
     3102        else
     3103#endif
     3104          coef = kBucketPolyRed (P.bucket, strat->S[j],
     3105                                 strat->lenS[j] /*pLength(strat->S[j]) */ ,
     3106                                 strat->kNoether);
     3107        pMult_nn (res, coef);
     3108        nDelete (&coef);
     3109        h = kBucketGetLm (P.bucket);
     3110        pTest (h);
     3111        if (h == NULL)
     3112        {
    28473113#ifdef REDTAIL_PROT
    2848               PrintS(" ");
    2849 #endif
    2850         kBucketDestroy(&P.bucket);
    2851               return res;
    2852             }
    2853             pTest(h);
    2854             P.p=h;
    2855             P.t_p=NULL;
    2856             P.SetShortExpVector();
     3114          PrintS (" ");
     3115#endif
     3116          kBucketDestroy (&P.bucket);
     3117          return res;
     3118        }
     3119        pTest (h);
     3120        P.p = h;
     3121        P.t_p = NULL;
     3122        P.SetShortExpVector ();
    28573123#ifdef KDEBUG
    2858             if (TEST_OPT_DEBUG)
    2859             {
    2860               PrintS("\nto tail:");
    2861               wrp(h);
    2862               PrintLn();
    2863             }
    2864 #endif
    2865           }
    2866           else
    2867           {
     3124        if (TEST_OPT_DEBUG)
     3125        {
     3126          PrintS ("\nto tail:");
     3127          wrp (h);
     3128          PrintLn ();
     3129        }
     3130#endif
     3131      }
     3132      else
     3133      {
    28683134#ifdef REDTAIL_PROT
    2869             PrintS("n");
    2870 #endif
    2871             break;
    2872           }
    2873       } /* end loop current mon */
    2874       //   poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
    2875       //act->next=tmp;pIter(act);
    2876       act->next=kBucketExtractLm(P.bucket);pIter(act);
    2877       h = kBucketGetLm(P.bucket);
    2878       if (h==NULL)
    2879       {
     3135        PrintS ("n");
     3136#endif
     3137        break;
     3138      }
     3139    }                           /* end loop current mon */
     3140    //   poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
     3141    //act->next=tmp;pIter(act);
     3142    act->next = kBucketExtractLm (P.bucket);
     3143    pIter (act);
     3144    h = kBucketGetLm (P.bucket);
     3145    if (h == NULL)
     3146    {
    28803147#ifdef REDTAIL_PROT
    2881         PrintS(" ");
    2882 #endif
    2883   kBucketDestroy(&P.bucket);
    2884         return res;
    2885       }
    2886       pTest(h);
     3148      PrintS (" ");
     3149#endif
     3150      kBucketDestroy (&P.bucket);
     3151      return res;
     3152    }
     3153    pTest (h);
    28873154  }
    28883155}
     
    28933160
    28943161//transfers ownership of m to mat
    2895 void init_with_mac_poly(tgb_sparse_matrix* mat, int row, mac_poly m)
    2896 {
    2897   assume(mat->mp[row]==NULL);
    2898   mat->mp[row]=m;
     3162void
     3163init_with_mac_poly (tgb_sparse_matrix * mat, int row, mac_poly m)
     3164{
     3165  assume (mat->mp[row] == NULL);
     3166  mat->mp[row] = m;
    28993167#ifdef TGB_DEBUG
    2900   mac_poly r=m;
    2901   while(r)
    2902   {
    2903     assume(r->exp<mat->columns);
    2904     r=r->next;
    2905   }
    2906 #endif
    2907 }
    2908 poly free_row_to_poly(tgb_sparse_matrix* mat, int row, poly* monoms, int monom_index)
    2909 {
    2910   poly p=NULL;
    2911   poly* set_this=&p;
    2912   mac_poly r=mat->mp[row];
    2913   mat->mp[row]=NULL;
    2914   while(r)
    2915   {
    2916     (*set_this)=pLmInit(monoms[monom_index-1-r->exp]);
    2917     pSetCoeff((*set_this),r->coef);
    2918     set_this=&((*set_this)->next);
    2919     mac_poly old=r;
    2920     r=r->next;
     3168  mac_poly r = m;
     3169  while (r)
     3170  {
     3171    assume (r->exp < mat->columns);
     3172    r = r->next;
     3173  }
     3174#endif
     3175}
     3176
     3177poly
     3178free_row_to_poly (tgb_sparse_matrix * mat, int row, poly * monoms,
     3179                  int monom_index)
     3180{
     3181  poly p = NULL;
     3182  poly *set_this = &p;
     3183  mac_poly r = mat->mp[row];
     3184  mat->mp[row] = NULL;
     3185  while (r)
     3186  {
     3187    (*set_this) = pLmInit (monoms[monom_index - 1 - r->exp]);
     3188    pSetCoeff ((*set_this), r->coef);
     3189    set_this = &((*set_this)->next);
     3190    mac_poly old = r;
     3191    r = r->next;
    29213192    delete old;
    29223193
     
    29253196}
    29263197
    2927 static int poly_crit(const void* ap1, const void* ap2)
    2928 {
    2929   poly p1,p2;
    2930   p1=*((poly*) ap1);
    2931   p2=*((poly*)ap2);
    2932 
    2933   int c=pLmCmp(p1,p2);
    2934   if (c !=0) return c;
    2935   int l1=pLength(p1);
    2936   int l2=pLength(p2);
    2937   if (l1<l2) return -1;
    2938   if (l1>l2) return 1;
     3198static int
     3199poly_crit (const void *ap1, const void *ap2)
     3200{
     3201  poly p1, p2;
     3202  p1 = *((poly *) ap1);
     3203  p2 = *((poly *) ap2);
     3204
     3205  int c = pLmCmp (p1, p2);
     3206  if (c != 0)
     3207    return c;
     3208  int l1 = pLength (p1);
     3209  int l2 = pLength (p2);
     3210  if (l1 < l2)
     3211    return -1;
     3212  if (l1 > l2)
     3213    return 1;
    29393214  return 0;
    29403215}
    29413216
    2942 void slimgb_alg::introduceDelayedPairs(poly* pa,int s)
    2943 {
    2944     if (s==0) return;
    2945     sorted_pair_node** si_array=(sorted_pair_node**) omalloc(s* sizeof(sorted_pair_node*));
    2946 
    2947     for( int i = 0; i < s; i++ )
    2948     {
    2949         sorted_pair_node* si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
    2950         si->i=-1;
    2951         si->j=-2;
    2952         poly p=pa[i];
    2953         simplify_poly(p,r);
    2954         si->expected_length=pQuality(p,this,pLength(p));
    2955         p_Test(p,r);
    2956         si->deg=this->pTotaldegree_full(p);
    2957         /*if (!rField_is_Zp(r))
     3217void
     3218slimgb_alg::introduceDelayedPairs (poly * pa, int s)
     3219{
     3220  if (s == 0)
     3221    return;
     3222  sorted_pair_node **si_array =
     3223    (sorted_pair_node **) omalloc (s * sizeof (sorted_pair_node *));
     3224
     3225  for (int i = 0; i < s; i++)
     3226  {
     3227    sorted_pair_node *si =
     3228      (sorted_pair_node *) omalloc (sizeof (sorted_pair_node));
     3229    si->i = -1;
     3230    si->j = -2;
     3231    poly p = pa[i];
     3232    simplify_poly (p, r);
     3233    si->expected_length = pQuality (p, this, pLength (p));
     3234    p_Test (p, r);
     3235    si->deg = this->pTotaldegree_full (p);
     3236    /*if (!rField_is_Zp(r))
    29583237       {
    2959           p_Content(p,r);
    2960           p_Cleardenom(p,r);
    2961         }*/
    2962 
    2963         si->lcm_of_lm=p;
    2964 
    2965         //      c->apairs[n-1-i]=si;
    2966         si_array[i]=si;
    2967   }
    2968 
    2969   qsort(si_array,s,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
    2970     apairs=spn_merge(apairs,pair_top+1,si_array,s,this);
    2971   pair_top+=s;
    2972   omfree(si_array);
    2973 }
    2974 
    2975 slimgb_alg::slimgb_alg(ideal I, int syz_comp,BOOLEAN F4,int deg_pos)
    2976 {
    2977   this->deg_pos=deg_pos;
    2978   lastCleanedDeg=-1;
    2979   completed=FALSE;
    2980   this->syz_comp=syz_comp;
    2981   r=currRing;
    2982   nc=rIsPluralRing(r);
    2983   this->lastDpBlockStart=get_last_dp_block_start(r);
     3238       p_Content(p,r);
     3239       p_Cleardenom(p,r);
     3240       } */
     3241
     3242    si->lcm_of_lm = p;
     3243
     3244    //      c->apairs[n-1-i]=si;
     3245    si_array[i] = si;
     3246  }
     3247
     3248  qsort (si_array, s, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
     3249  apairs = spn_merge (apairs, pair_top + 1, si_array, s, this);
     3250  pair_top += s;
     3251  omfree (si_array);
     3252}
     3253
     3254slimgb_alg::slimgb_alg (ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
     3255{
     3256  this->deg_pos = deg_pos;
     3257  lastCleanedDeg = -1;
     3258  completed = FALSE;
     3259  this->syz_comp = syz_comp;
     3260  r = currRing;
     3261  nc = rIsPluralRing (r);
     3262  this->lastDpBlockStart = get_last_dp_block_start (r);
    29843263  //Print("last dp Block start: %i\n", this->lastDpBlockStart);
    2985   is_homog=TRUE;
     3264  is_homog = TRUE;
    29863265  {
    29873266    int hzz;
    2988     for(hzz=0;hzz<IDELEMS(I);hzz++)
    2989     {
    2990       assume(I->m[hzz]!=NULL);
    2991       int d=this->pTotaldegree(I->m[hzz]);
    2992       poly t=I->m[hzz]->next;
    2993       while(t)
    2994       {
    2995         if (d!=this->pTotaldegree(t))
    2996         {
    2997           is_homog=FALSE;
    2998           break;
    2999         }
    3000         t=t->next;
    3001       }
    3002       if(!(is_homog)) break;
    3003     }
    3004   }
    3005   eliminationProblem=((!(is_homog))&&((pLexOrder)||(I->rank>1)));
    3006   tailReductions=((is_homog)||((TEST_OPT_REDTAIL)&&(!(I->rank>1))));
     3267    for (hzz = 0; hzz < IDELEMS (I); hzz++)
     3268    {
     3269      assume (I->m[hzz] != NULL);
     3270      int d = this->pTotaldegree (I->m[hzz]);
     3271      poly t = I->m[hzz]->next;
     3272      while (t)
     3273      {
     3274        if (d != this->pTotaldegree (t))
     3275        {
     3276          is_homog = FALSE;
     3277          break;
     3278        }
     3279        t = t->next;
     3280      }
     3281      if (!(is_homog))
     3282        break;
     3283    }
     3284  }
     3285  eliminationProblem = ((!(is_homog)) && ((pLexOrder) || (I->rank > 1)));
     3286  tailReductions = ((is_homog) || ((TEST_OPT_REDTAIL) && (!(I->rank > 1))));
    30073287  //  Print("is homog:%d",c->is_homog);
    3008   void* h;
     3288  void *h;
    30093289  int i;
    3010   to_destroy=NULL;
    3011   easy_product_crit=0;
    3012   extended_product_crit=0;
    3013   if (rField_is_Zp(r))
    3014     isDifficultField=FALSE;
     3290  to_destroy = NULL;
     3291  easy_product_crit = 0;
     3292  extended_product_crit = 0;
     3293  if (rField_is_Zp (r))
     3294    isDifficultField = FALSE;
    30153295  else
    3016     isDifficultField=TRUE;
     3296    isDifficultField = TRUE;
    30173297  //not fully correct
    30183298  //(rChar()==0);
    3019   F4_mode=F4;
    3020 
    3021   reduction_steps=0;
    3022   last_index=-1;
    3023 
    3024   F=NULL;
    3025   F_minus=NULL;
    3026 
    3027   Rcounter=0;
    3028 
    3029   soon_free=NULL;
    3030 
    3031   tmp_lm=pOne();
    3032 
    3033   normal_forms=0;
    3034   current_degree=1;
    3035 
    3036   max_pairs=5*IDELEMS(I);
    3037 
    3038   apairs=(sorted_pair_node**) omalloc(sizeof(sorted_pair_node*)*max_pairs);
    3039   pair_top=-1;
    3040 
    3041   int n=IDELEMS(I);
    3042   array_lengths=n;
    3043 
    3044 
    3045   i=0;
    3046   this->n=0;
    3047   T_deg=(int*) omalloc(n*sizeof(int));
    3048   if(eliminationProblem)
    3049     T_deg_full=(int*) omalloc(n*sizeof(int));
     3299  F4_mode = F4;
     3300
     3301  reduction_steps = 0;
     3302  last_index = -1;
     3303
     3304  F = NULL;
     3305  F_minus = NULL;
     3306
     3307  Rcounter = 0;
     3308
     3309  soon_free = NULL;
     3310
     3311  tmp_lm = pOne ();
     3312
     3313  normal_forms = 0;
     3314  current_degree = 1;
     3315
     3316  max_pairs = 5 * IDELEMS (I);
     3317
     3318  apairs =
     3319    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * max_pairs);
     3320  pair_top = -1;
     3321
     3322  int n = IDELEMS (I);
     3323  array_lengths = n;
     3324
     3325
     3326  i = 0;
     3327  this->n = 0;
     3328  T_deg = (int *) omalloc (n * sizeof (int));
     3329  if (eliminationProblem)
     3330    T_deg_full = (int *) omalloc (n * sizeof (int));
    30503331  else
    3051     T_deg_full=NULL;
    3052   tmp_pair_lm=(poly*) omalloc(n*sizeof(poly));
    3053   tmp_spn=(sorted_pair_node**) omalloc(n*sizeof(sorted_pair_node*));
    3054   lm_bin=omGetSpecBin(POLYSIZE + (r->ExpL_Size)*sizeof(long));
     3332    T_deg_full = NULL;
     3333  tmp_pair_lm = (poly *) omalloc (n * sizeof (poly));
     3334  tmp_spn = (sorted_pair_node **) omalloc (n * sizeof (sorted_pair_node *));
     3335  lm_bin = omGetSpecBin (POLYSIZE + (r->ExpL_Size) * sizeof (long));
    30553336#ifdef HEAD_BIN
    3056   HeadBin=omGetSpecBin(POLYSIZE + (currRing->ExpL_Size)*sizeof(long));
     3337  HeadBin = omGetSpecBin (POLYSIZE + (currRing->ExpL_Size) * sizeof (long));
    30573338#endif
    30583339  /* omUnGetSpecBin(&(c->HeadBin)); */
    3059   #ifndef HAVE_BOOST
    3060   #ifdef USE_STDVECBOOL
    3061   #else
    3062   h=omalloc(n*sizeof(char*));
    3063 
    3064   states=(char**) h;
    3065   #endif
    3066   #endif
    3067   h=omalloc(n*sizeof(int));
    3068   lengths=(int*) h;
    3069   weighted_lengths=(wlen_type*)omalloc(n*sizeof(wlen_type));
    3070   gcd_of_terms=(poly*) omalloc(n*sizeof(poly));
    3071 
    3072   short_Exps=(long*) omalloc(n*sizeof(long));
     3340#ifndef HAVE_BOOST
     3341#ifdef USE_STDVECBOOL
     3342#else
     3343  h = omalloc (n * sizeof (char *));
     3344
     3345  states = (char **) h;
     3346#endif
     3347#endif
     3348  h = omalloc (n * sizeof (int));
     3349  lengths = (int *) h;
     3350  weighted_lengths = (wlen_type *) omalloc (n * sizeof (wlen_type));
     3351  gcd_of_terms = (poly *) omalloc (n * sizeof (poly));
     3352
     3353  short_Exps = (long *) omalloc (n * sizeof (long));
    30733354  if (F4_mode)
    3074     S=idInit(n,I->rank);
     3355    S = idInit (n, I->rank);
    30753356  else
    3076     S=idInit(1,I->rank);
    3077   strat=new skStrategy;
     3357    S = idInit (1, I->rank);
     3358  strat = new skStrategy;
    30783359  if (eliminationProblem)
    3079     strat->honey=TRUE;
     3360    strat->honey = TRUE;
    30803361  strat->syzComp = 0;
    3081   initBuchMoraCrit(strat);
    3082   initBuchMoraPos(strat);
     3362  initBuchMoraCrit (strat);
     3363  initBuchMoraPos (strat);
    30833364  strat->initEcart = initEcartBBA;
    3084   strat->tailRing=r;
     3365  strat->tailRing = r;
    30853366  strat->enterS = enterSBba;
    30863367  strat->sl = -1;
    3087   i=n;
    3088   i=1;//some strange bug else
     3368  i = n;
     3369  i = 1;                        //some strange bug else
    30893370  /* initS(c->S,NULL,c->strat); */
    30903371  /* intS start: */
    30913372  // i=((i+IDELEMS(c->S)+15)/16)*16;
    3092   strat->ecartS=(intset)omAlloc(i*sizeof(int)); /*initec(i);*/
    3093   strat->sevS=(unsigned long*)omAlloc0(i*sizeof(unsigned long));
    3094   /*initsevS(i);*/
    3095   strat->S_2_R=(int*)omAlloc0(i*sizeof(int));/*initS_2_R(i);*/
    3096   strat->fromQ=NULL;
    3097   strat->Shdl=idInit(1,1);
    3098   strat->S=strat->Shdl->m;
    3099   strat->lenS=(int*)omAlloc0(i*sizeof(int));
    3100   if((isDifficultField)||(eliminationProblem))
    3101     strat->lenSw=(wlen_type*)omAlloc0(i*sizeof(wlen_type));
     3373  strat->ecartS = (intset) omAlloc (i * sizeof (int));  /*initec(i); */
     3374  strat->sevS = (unsigned long *) omAlloc0 (i * sizeof (unsigned long));
     3375  /*initsevS(i); */
     3376  strat->S_2_R = (int *) omAlloc0 (i * sizeof (int));   /*initS_2_R(i); */
     3377  strat->fromQ = NULL;
     3378  strat->Shdl = idInit (1, 1);
     3379  strat->S = strat->Shdl->m;
     3380  strat->lenS = (int *) omAlloc0 (i * sizeof (int));
     3381  if ((isDifficultField) || (eliminationProblem))
     3382    strat->lenSw = (wlen_type *) omAlloc0 (i * sizeof (wlen_type));
    31023383  else
    3103     strat->lenSw=NULL;
    3104   assume(n>0);
    3105   add_to_basis_ideal_quotient(I->m[0],this,NULL);
    3106 
    3107   assume(strat->sl==IDELEMS(strat->Shdl)-1);
    3108   if(!(F4_mode))
    3109   {
    3110         poly* array_arg=I->m;
    3111         array_arg++;
    3112         introduceDelayedPairs(array_arg,n-1);
    3113         /*
    3114     for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
    3115     {
    3116       //     add_to_basis(I->m[i],-1,-1,c);
    3117       si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
    3118       si->i=-1;
    3119       si->j=-2;
    3120       si->expected_length=pQuality(I->m[i],this,pLength(I->m[i]));
    3121       si->deg=pTotaldegree(I->m[i]);
    3122       if (!rField_is_Zp(r))
    3123       {
    3124         p_Cleardenom(I->m[i], r);
    3125       }
    3126       si->lcm_of_lm=I->m[i];
    3127 
    3128       //      c->apairs[n-1-i]=si;
    3129       apairs[n-i-1]=si;
    3130       ++(pair_top);
    3131     }*/
     3384    strat->lenSw = NULL;
     3385  assume (n > 0);
     3386  add_to_basis_ideal_quotient (I->m[0], this, NULL);
     3387
     3388  assume (strat->sl == IDELEMS (strat->Shdl) - 1);
     3389  if (!(F4_mode))
     3390  {
     3391    poly *array_arg = I->m;
     3392    array_arg++;
     3393    introduceDelayedPairs (array_arg, n - 1);
     3394    /*
     3395       for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
     3396       {
     3397       //     add_to_basis(I->m[i],-1,-1,c);
     3398       si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
     3399       si->i=-1;
     3400       si->j=-2;
     3401       si->expected_length=pQuality(I->m[i],this,pLength(I->m[i]));
     3402       si->deg=pTotaldegree(I->m[i]);
     3403       if (!rField_is_Zp(r))
     3404       {
     3405       p_Cleardenom(I->m[i], r);
     3406       }
     3407       si->lcm_of_lm=I->m[i];
     3408
     3409       //      c->apairs[n-1-i]=si;
     3410       apairs[n-i-1]=si;
     3411       ++(pair_top);
     3412       } */
    31323413  }
    31333414  else
    31343415  {
    3135     for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
    3136       add_to_basis_ideal_quotient(I->m[i],this,NULL);
    3137   }
    3138   for(i=0;i<IDELEMS(I);i++)
    3139   {
    3140     I->m[i]=NULL;
    3141   }
    3142   idDelete(&I);
    3143   add_later=idInit(ADD_LATER_SIZE,S->rank);
    3144   #ifdef USE_NORO
    3145   use_noro=((!(nc))&&(S->rank<=1)&&(rField_is_Zp(r)) &&(!(eliminationProblem))&&(npPrimeM<=32003));
    3146   use_noro_last_block=false;
    3147   if ((!(use_noro))&&(lastDpBlockStart<=pVariables))
    3148   {
    3149       use_noro_last_block=((!(nc))&&(S->rank<=1)&&(rField_is_Zp(r)) &&(npPrimeM<=32003));
    3150   }
    3151   #else
    3152   use_noro=false;
    3153   use_noro_last_block=false;
    3154   #endif
     3416    for (i = 1; i < n; i++)     //the 1 is wanted, because first element is added to basis
     3417      add_to_basis_ideal_quotient (I->m[i], this, NULL);
     3418  }
     3419  for (i = 0; i < IDELEMS (I); i++)
     3420  {
     3421    I->m[i] = NULL;
     3422  }
     3423  idDelete (&I);
     3424  add_later = idInit (ADD_LATER_SIZE, S->rank);
     3425#ifdef USE_NORO
     3426  use_noro = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
     3427              && (!(eliminationProblem)) && (npPrimeM <= 32003));
     3428  use_noro_last_block = false;
     3429  if ((!(use_noro)) && (lastDpBlockStart <= pVariables))
     3430  {
     3431    use_noro_last_block = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
     3432                           && (npPrimeM <= 32003));
     3433  }
     3434#else
     3435  use_noro = false;
     3436  use_noro_last_block = false;
     3437#endif
    31553438  //Print("NORO last block %i",use_noro_last_block);
    3156   memset(add_later->m,0,ADD_LATER_SIZE*sizeof(poly));
    3157 }
    3158 slimgb_alg::~slimgb_alg()
     3439  memset (add_later->m, 0, ADD_LATER_SIZE * sizeof (poly));
     3440}
     3441
     3442slimgb_alg::~slimgb_alg ()
    31593443{
    31603444
    31613445  if (!(completed))
    31623446  {
    3163       poly* add=(poly*) omalloc((pair_top+2)*sizeof(poly));
    3164       int piter;
    3165       int pos=0;
    3166       for(piter=0;piter<=pair_top;piter++)
    3167       {
    3168         sorted_pair_node* s=apairs[piter];
    3169         if (s->i<0)
    3170         {
    3171             //delayed element
    3172             if (s->lcm_of_lm!=NULL)
    3173             {
    3174                 add[pos]=s->lcm_of_lm;
    3175                 pos++;
    3176             }
    3177         }
    3178         free_sorted_pair_node(s,r);
    3179         apairs[piter]=NULL;
    3180       }
    3181       pair_top=-1;
    3182       add[pos]=NULL;
    3183       pos=0;
    3184       while(add[pos]!=NULL)
    3185       {
    3186         add_to_basis_ideal_quotient(add[pos],this,NULL);
    3187         pos++;
    3188       }
    3189       for(piter=0;piter<=pair_top;piter++)
    3190       {
    3191         sorted_pair_node* s=apairs[piter];
    3192         assume(s->i>=0);
    3193         free_sorted_pair_node(s,r);
    3194         apairs[piter]=NULL;
    3195       }
    3196       pair_top=-1;
    3197   }
    3198   id_Delete(&add_later,r);
    3199   int i,j;
    3200   slimgb_alg* c=this;
    3201   while(c->to_destroy)
    3202   {
    3203     pDelete(&(c->to_destroy->p));
    3204     poly_list_node* old=c->to_destroy;
    3205     c->to_destroy=c->to_destroy->next;
    3206     omfree(old);
    3207   }
    3208   while(c->F)
    3209   {
    3210     for(i=0;i<c->F->size;i++)
    3211     {
    3212       pDelete(&(c->F->mp[i].m));
    3213     }
    3214     omfree(c->F->mp);
    3215     c->F->mp=NULL;
    3216     mp_array_list* old=c->F;
    3217     c->F=c->F->next;
    3218     omfree(old);
    3219   }
    3220   while(c->F_minus)
    3221   {
    3222     for(i=0;i<c->F_minus->size;i++)
    3223     {
    3224       pDelete(&(c->F_minus->p[i]));
    3225     }
    3226     omfree(c->F_minus->p);
    3227     c->F_minus->p=NULL;
    3228     poly_array_list* old=c->F_minus;
    3229     c->F_minus=c->F_minus->next;
    3230     omfree(old);
    3231   }
    3232   #ifndef HAVE_BOOST
    3233   #ifndef USE_STDVECBOOL
    3234   for(int z=1 /* zero length at 0 */;z<c->n;z++)
    3235   {
    3236     omfree(c->states[z]);
    3237   }
    3238   omfree(c->states);
    3239   #endif
    3240   #endif
    3241 
    3242   omfree(c->lengths);
    3243   omfree(c->weighted_lengths);
    3244   for(int z=0;z<c->n;z++)
    3245   {
    3246     pDelete(&c->tmp_pair_lm[z]);
    3247     omfree(c->tmp_spn[z]);
    3248   }
    3249   omfree(c->tmp_pair_lm);
    3250   omfree(c->tmp_spn);
    3251 
    3252   omfree(c->T_deg);
    3253   if(c->T_deg_full)
    3254     omfree(c->T_deg_full);
    3255 
    3256   omFree(c->strat->ecartS);
    3257   omFree(c->strat->sevS);
     3447    poly *add = (poly *) omalloc ((pair_top + 2) * sizeof (poly));
     3448    int piter;
     3449    int pos = 0;
     3450    for (piter = 0; piter <= pair_top; piter++)
     3451    {
     3452      sorted_pair_node *s = apairs[piter];
     3453      if (s->i < 0)
     3454      {
     3455        //delayed element
     3456        if (s->lcm_of_lm != NULL)
     3457        {
     3458          add[pos] = s->lcm_of_lm;
     3459          pos++;
     3460        }
     3461      }
     3462      free_sorted_pair_node (s, r);
     3463      apairs[piter] = NULL;
     3464    }
     3465    pair_top = -1;
     3466    add[pos] = NULL;
     3467    pos = 0;
     3468    while (add[pos] != NULL)
     3469    {
     3470      add_to_basis_ideal_quotient (add[pos], this, NULL);
     3471      pos++;
     3472    }
     3473    for (piter = 0; piter <= pair_top; piter++)
     3474    {
     3475      sorted_pair_node *s = apairs[piter];
     3476      assume (s->i >= 0);
     3477      free_sorted_pair_node (s, r);
     3478      apairs[piter] = NULL;
     3479    }
     3480    pair_top = -1;
     3481  }
     3482  id_Delete (&add_later, r);
     3483  int i, j;
     3484  slimgb_alg *c = this;
     3485  while (c->to_destroy)
     3486  {
     3487    pDelete (&(c->to_destroy->p));
     3488    poly_list_node *old = c->to_destroy;
     3489    c->to_destroy = c->to_destroy->next;
     3490    omfree (old);
     3491  }
     3492  while (c->F)
     3493  {
     3494    for (i = 0; i < c->F->size; i++)
     3495    {
     3496      pDelete (&(c->F->mp[i].m));
     3497    }
     3498    omfree (c->F->mp);
     3499    c->F->mp = NULL;
     3500    mp_array_list *old = c->F;
     3501    c->F = c->F->next;
     3502    omfree (old);
     3503  }
     3504  while (c->F_minus)
     3505  {
     3506    for (i = 0; i < c->F_minus->size; i++)
     3507    {
     3508      pDelete (&(c->F_minus->p[i]));
     3509    }
     3510    omfree (c->F_minus->p);
     3511    c->F_minus->p = NULL;
     3512    poly_array_list *old = c->F_minus;
     3513    c->F_minus = c->F_minus->next;
     3514    omfree (old);
     3515  }
     3516#ifndef HAVE_BOOST
     3517#ifndef USE_STDVECBOOL
     3518  for (int z = 1 /* zero length at 0 */ ; z < c->n; z++)
     3519  {
     3520    omfree (c->states[z]);
     3521  }
     3522  omfree (c->states);
     3523#endif
     3524#endif
     3525
     3526  omfree (c->lengths);
     3527  omfree (c->weighted_lengths);
     3528  for (int z = 0; z < c->n; z++)
     3529  {
     3530    pDelete (&c->tmp_pair_lm[z]);
     3531    omfree (c->tmp_spn[z]);
     3532  }
     3533  omfree (c->tmp_pair_lm);
     3534  omfree (c->tmp_spn);
     3535
     3536  omfree (c->T_deg);
     3537  if (c->T_deg_full)
     3538    omfree (c->T_deg_full);
     3539
     3540  omFree (c->strat->ecartS);
     3541  omFree (c->strat->sevS);
    32583542//   initsevS(i);
    3259   omFree(c->strat->S_2_R);
    3260 
    3261 
    3262   omFree(c->strat->lenS);
    3263 
    3264   if(c->strat->lenSw)  omFree(c->strat->lenSw);
    3265 
    3266   for(i=0;i<c->n;i++)
    3267   {
    3268     if(c->gcd_of_terms[i])
    3269       pDelete(&(c->gcd_of_terms[i]));
    3270   }
    3271   omfree(c->gcd_of_terms);
    3272 
    3273   omfree(c->apairs);
     3543  omFree (c->strat->S_2_R);
     3544
     3545
     3546  omFree (c->strat->lenS);
     3547
     3548  if (c->strat->lenSw)
     3549    omFree (c->strat->lenSw);
     3550
     3551  for (i = 0; i < c->n; i++)
     3552  {
     3553    if (c->gcd_of_terms[i])
     3554      pDelete (&(c->gcd_of_terms[i]));
     3555  }
     3556  omfree (c->gcd_of_terms);
     3557
     3558  omfree (c->apairs);
    32743559  if (TEST_OPT_PROT)
    32753560  {
    32763561    //Print("calculated %d NFs\n",c->normal_forms);
    3277       Print("\nNF:%i product criterion:%i, ext_product criterion:%i \n", c->normal_forms, c->easy_product_crit, c->extended_product_crit);
    3278   }
    3279 
    3280   for(i=0;i<=c->strat->sl;i++)
    3281   {
    3282     if (!c->strat->S[i]) continue;
    3283     BOOLEAN found=FALSE;
    3284     for(j=0;j<c->n;j++)
    3285     {
    3286       if (c->S->m[j]==c->strat->S[i])
    3287       {
    3288         found=TRUE;
    3289         break;
    3290       }
    3291     }
    3292     if(!found) pDelete(&c->strat->S[i]);
     3562    Print ("\nNF:%i product criterion:%i, ext_product criterion:%i \n",
     3563           c->normal_forms, c->easy_product_crit, c->extended_product_crit);
     3564  }
     3565
     3566  for (i = 0; i <= c->strat->sl; i++)
     3567  {
     3568    if (!c->strat->S[i])
     3569      continue;
     3570    BOOLEAN found = FALSE;
     3571    for (j = 0; j < c->n; j++)
     3572    {
     3573      if (c->S->m[j] == c->strat->S[i])
     3574      {
     3575        found = TRUE;
     3576        break;
     3577      }
     3578    }
     3579    if (!found)
     3580      pDelete (&c->strat->S[i]);
    32933581  }
    32943582//   for(i=0;i<c->n;i++)
     
    33113599  if (completed)
    33123600  {
    3313   for(i=0;i<c->n;i++)
    3314   {
    3315     assume(c->S->m[i]!=NULL);
    3316     if (p_GetComp(c->S->m[i],currRing)>this->syz_comp) continue;
    3317     for(j=0;j<c->n;j++)
    3318     {
    3319       if((c->S->m[j]==NULL)||(i==j))
    3320         continue;
    3321       assume(p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j],
    3322              c->S->m[i],~c->short_Exps[i],
    3323              c->r)==p_LmDivisibleBy(c->S->m[j],
    3324              c->S->m[i],
    3325              c->r));
    3326       if (p_LmShortDivisibleBy(c->S->m[j],c->short_Exps[j],
    3327           c->S->m[i],~c->short_Exps[i],
    3328           c->r))
    3329       {
    3330         pDelete(&c->S->m[i]);
    3331         break;
    3332       }
    3333     }
    3334   }
    3335   }
    3336   omfree(c->short_Exps);
    3337 
    3338   ideal I=c->S;
    3339   IDELEMS(I)=c->n;
    3340   idSkipZeroes(I);
    3341   for(i=0;i<=c->strat->sl;i++)
    3342     c->strat->S[i]=NULL;
    3343   id_Delete(&c->strat->Shdl,c->r);
    3344   pDelete(&c->tmp_lm);
    3345   omUnGetSpecBin(&lm_bin);
     3601    for (i = 0; i < c->n; i++)
     3602    {
     3603      assume (c->S->m[i] != NULL);
     3604      if (p_GetComp (c->S->m[i], currRing) > this->syz_comp)
     3605        continue;
     3606      for (j = 0; j < c->n; j++)
     3607      {
     3608        if ((c->S->m[j] == NULL) || (i == j))
     3609          continue;
     3610        assume (p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
     3611                                      c->S->m[i], ~c->short_Exps[i],
     3612                                      c->r) == p_LmDivisibleBy (c->S->m[j],
     3613                                                                c->S->m[i],
     3614                                                                c->r));
     3615        if (p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
     3616                                  c->S->m[i], ~c->short_Exps[i], c->r))
     3617        {
     3618          pDelete (&c->S->m[i]);
     3619          break;
     3620        }
     3621      }
     3622    }
     3623  }
     3624  omfree (c->short_Exps);
     3625
     3626  ideal I = c->S;
     3627  IDELEMS (I) = c->n;
     3628  idSkipZeroes (I);
     3629  for (i = 0; i <= c->strat->sl; i++)
     3630    c->strat->S[i] = NULL;
     3631  id_Delete (&c->strat->Shdl, c->r);
     3632  pDelete (&c->tmp_lm);
     3633  omUnGetSpecBin (&lm_bin);
    33463634  delete c->strat;
    33473635}
    3348 ideal t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode)
    3349 {
    3350     assume(r==currRing);
    3351     ring orig_ring=r;
    3352     int pos;
    3353     ring new_ring=rAssure_TDeg(orig_ring,1,rVar(orig_ring),pos);
    3354     ideal s_h;
    3355     if (orig_ring != new_ring)
    3356     {
    3357         rChangeCurrRing(new_ring);
    3358         s_h=idrCopyR_NoSort(arg_I,orig_ring);
    3359         idTest(s_h);
    3360         /*int i;
    3361         for(i=0;i<IDELEMS(s_h);i++)
    3362         {
    3363             poly p=s_h->m[i];
    3364             while(p)
    3365             {
    3366                 p_Setm(p,new_ring);
    3367                 pIter(p);
    3368             }
    3369         }*/
    3370     }
    3371     else
    3372     {
    3373         s_h = id_Copy(arg_I,orig_ring);
    3374     }
    3375 
    3376     ideal s_result=do_t_rep_gb(new_ring,s_h,syz_comp,F4_mode,pos);
    3377     ideal result;
    3378     if(orig_ring != new_ring)
    3379     {
    3380         idTest(s_result);
    3381         rChangeCurrRing(orig_ring);
    3382         result = idrMoveR_NoSort(s_result, new_ring);
    3383 
    3384         idTest(result);
    3385         //rChangeCurrRing(new_ring);
    3386         rKill(new_ring);
    3387         //rChangeCurrRing(orig_ring);
    3388     }
    3389     else
    3390         result=s_result;
    3391     idTest(result);
    3392     return result;
    3393 }
    3394 
    3395 ideal do_t_rep_gb(ring r,ideal arg_I, int syz_comp, BOOLEAN F4_mode,int deg_pos)
     3636
     3637ideal
     3638t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
     3639{
     3640  assume (r == currRing);
     3641  ring orig_ring = r;
     3642  int pos;
     3643  ring new_ring = rAssure_TDeg (orig_ring, 1, rVar (orig_ring), pos);
     3644  ideal s_h;
     3645  if (orig_ring != new_ring)
     3646  {
     3647    rChangeCurrRing (new_ring);
     3648    s_h = idrCopyR_NoSort (arg_I, orig_ring);
     3649    idTest (s_h);
     3650    /*int i;
     3651       for(i=0;i<IDELEMS(s_h);i++)
     3652       {
     3653       poly p=s_h->m[i];
     3654       while(p)
     3655       {
     3656       p_Setm(p,new_ring);
     3657       pIter(p);
     3658       }
     3659       } */
     3660  }
     3661  else
     3662  {
     3663    s_h = id_Copy (arg_I, orig_ring);
     3664  }
     3665
     3666  ideal s_result = do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos);
     3667  ideal result;
     3668  if (orig_ring != new_ring)
     3669  {
     3670    idTest (s_result);
     3671    rChangeCurrRing (orig_ring);
     3672    result = idrMoveR_NoSort (s_result, new_ring);
     3673
     3674    idTest (result);
     3675    //rChangeCurrRing(new_ring);
     3676    rKill (new_ring);
     3677    //rChangeCurrRing(orig_ring);
     3678  }
     3679  else
     3680    result = s_result;
     3681  idTest (result);
     3682  return result;
     3683}
     3684
     3685ideal
     3686do_t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
    33963687{
    33973688  //  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)));
     
    33993690  if (TEST_OPT_PROT)
    34003691    if (F4_mode)
    3401       PrintS("F4 Modus \n");
     3692      PrintS ("F4 Modus \n");
    34023693
    34033694  //debug_Ideal=arg_debug_Ideal;
    34043695  //if (debug_Ideal) PrintS("DebugIdeal received\n");
    34053696  // Print("Idelems %i \n----------\n",IDELEMS(arg_I));
    3406   ideal I=arg_I;
    3407   idCompactify(I);
    3408   if (idIs0(I)) return I;
     3697  ideal I = arg_I;
     3698  idCompactify (I);
     3699  if (idIs0 (I))
     3700    return I;
    34093701  int i;
    3410   for(i=0;i<IDELEMS(I);i++)
    3411   {
    3412     assume(I->m[i]!=NULL);
    3413     simplify_poly(I->m[i],currRing);
    3414   }
    3415 
    3416   qsort(I->m,IDELEMS(I),sizeof(poly),poly_crit);
     3702  for (i = 0; i < IDELEMS (I); i++)
     3703  {
     3704    assume (I->m[i] != NULL);
     3705    simplify_poly (I->m[i], currRing);
     3706  }
     3707
     3708  qsort (I->m, IDELEMS (I), sizeof (poly), poly_crit);
    34173709  //Print("Idelems %i \n----------\n",IDELEMS(I));
    34183710  //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg));
    34193711  //int syz_comp=arg_I->rank;
    3420   slimgb_alg* c=new slimgb_alg(I, syz_comp,F4_mode,deg_pos);
    3421 
    3422   while ((c->pair_top>=0) && ((!(TEST_OPT_DEGBOUND)) || (c->apairs[c->pair_top]->deg<=Kstd1_deg)))
    3423   {
    3424     #ifdef HAVE_F4
    3425     if(F4_mode)
    3426       go_on_F4(c);
     3712  slimgb_alg *c = new slimgb_alg (I, syz_comp, F4_mode, deg_pos);
     3713
     3714  while ((c->pair_top >= 0)
     3715         && ((!(TEST_OPT_DEGBOUND))
     3716             || (c->apairs[c->pair_top]->deg <= Kstd1_deg)))
     3717  {
     3718#ifdef HAVE_F4
     3719    if (F4_mode)
     3720      go_on_F4 (c);
    34273721    else
    3428     #endif
    3429       go_on(c);
    3430   }
    3431   if (c->pair_top<0)
    3432     c->completed=TRUE;
    3433   I=c->S;
     3722#endif
     3723      go_on (c);
     3724  }
     3725  if (c->pair_top < 0)
     3726    c->completed = TRUE;
     3727  I = c->S;
    34343728  delete c;
    34353729  if (TEST_OPT_REDSB)
    34363730  {
    3437     ideal erg=kInterRed(I,NULL);
    3438     assume(I!=erg);
    3439     id_Delete(&I, currRing);
     3731    ideal erg = kInterRed (I, NULL);
     3732    assume (I != erg);
     3733    id_Delete (&I, currRing);
    34403734    return erg;
    34413735  }
    34423736  //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func);
    3443   assume(I->rank>=idRankFreeModule(I));
    3444   return(I);
    3445 }
    3446 
    3447 void now_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* c)
    3448 {
    3449   int i,j;
    3450   if (arg_i==arg_j)
     3737  assume (I->rank >= idRankFreeModule (I));
     3738  return (I);
     3739}
     3740
     3741void
     3742now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * c)
     3743{
     3744  int i, j;
     3745  if (arg_i == arg_j)
    34513746  {
    34523747    return;
    34533748  }
    3454   if (arg_i>arg_j)
    3455   {
    3456     i=arg_j;
    3457     j=arg_i;
     3749  if (arg_i > arg_j)
     3750  {
     3751    i = arg_j;
     3752    j = arg_i;
    34583753  }
    34593754  else
    34603755  {
    3461     i=arg_i;
    3462     j=arg_j;
    3463   }
    3464   c->states[j][i]=HASTREP;
    3465 }
    3466 
    3467 static BOOLEAN has_t_rep(const int & arg_i, const  int & arg_j, slimgb_alg* state)
    3468 {
    3469   assume(0<=arg_i);
    3470   assume(0<=arg_j);
    3471   assume(arg_i<state->n);
    3472   assume(arg_j<state->n);
    3473   if (arg_i==arg_j)
     3756    i = arg_i;
     3757    j = arg_j;
     3758  }
     3759  c->states[j][i] = HASTREP;
     3760}
     3761
     3762static BOOLEAN
     3763has_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * state)
     3764{
     3765  assume (0 <= arg_i);
     3766  assume (0 <= arg_j);
     3767  assume (arg_i < state->n);
     3768  assume (arg_j < state->n);
     3769  if (arg_i == arg_j)
    34743770  {
    34753771    return (TRUE);
    34763772  }
    3477   if (arg_i>arg_j)
    3478   {
    3479     return (state->states[arg_i][arg_j]==HASTREP);
     3773  if (arg_i > arg_j)
     3774  {
     3775    return (state->states[arg_i][arg_j] == HASTREP);
    34803776  }
    34813777  else
    34823778  {
    3483     return (state->states[arg_j][arg_i]==HASTREP);
    3484   }
    3485 }
    3486 
    3487 #if 0 // unused
    3488 static int pLcmDeg(poly a, poly b)
     3779    return (state->states[arg_j][arg_i] == HASTREP);
     3780  }
     3781}
     3782
     3783#if 0                           // unused
     3784static int
     3785pLcmDeg (poly a, poly b)
    34893786{
    34903787  int i;
    3491   int n=0;
    3492   for (i=pVariables; i; i--)
    3493   {
    3494     n+=si_max( pGetExp(a,i), pGetExp(b,i));
     3788  int n = 0;
     3789  for (i = pVariables; i; i--)
     3790  {
     3791    n += si_max (pGetExp (a, i), pGetExp (b, i));
    34953792  }
    34963793  return n;
     
    34983795#endif
    34993796
    3500 static void shorten_tails(slimgb_alg* c, poly monom)
     3797static void
     3798shorten_tails (slimgb_alg * c, poly monom)
    35013799{
    35023800  return;
    35033801// BOOLEAN corr=lenS_correct(c->strat);
    3504   for(int i=0;i<c->n;i++)
     3802  for (int i = 0; i < c->n; i++)
    35053803  {
    35063804    //enter tail
    35073805
    3508     if (c->S->m[i]==NULL) continue;
    3509     poly tail=c->S->m[i]->next;
    3510     poly prev=c->S->m[i];
    3511     BOOLEAN did_something=FALSE;
    3512     while((tail!=NULL)&& (pLmCmp(tail, monom)>=0))
    3513     {
    3514       if (p_LmDivisibleBy(monom,tail,c->r))
    3515       {
    3516         did_something=TRUE;
    3517         prev->next=tail->next;
    3518         tail->next=NULL;
    3519         p_Delete(& tail,c->r);
    3520         tail=prev;
    3521         //PrintS("Shortened");
    3522         c->lengths[i]--;
    3523       }
    3524       prev=tail;
    3525       tail=tail->next;
     3806    if (c->S->m[i] == NULL)
     3807      continue;
     3808    poly tail = c->S->m[i]->next;
     3809    poly prev = c->S->m[i];
     3810    BOOLEAN did_something = FALSE;
     3811    while ((tail != NULL) && (pLmCmp (tail, monom) >= 0))
     3812    {
     3813      if (p_LmDivisibleBy (monom, tail, c->r))
     3814      {
     3815        did_something = TRUE;
     3816        prev->next = tail->next;
     3817        tail->next = NULL;
     3818        p_Delete (&tail, c->r);
     3819        tail = prev;
     3820        //PrintS("Shortened");
     3821        c->lengths[i]--;
     3822      }
     3823      prev = tail;
     3824      tail = tail->next;
    35263825    }
    35273826    if (did_something)
     
    35293828      int new_pos;
    35303829      wlen_type q;
    3531       q=pQuality(c->S->m[i],c,c->lengths[i]);
    3532       new_pos=simple_posInS(c->strat,c->S->m[i],c->lengths[i],q);
    3533 
    3534       int old_pos=-1;
     3830      q = pQuality (c->S->m[i], c, c->lengths[i]);
     3831      new_pos = simple_posInS (c->strat, c->S->m[i], c->lengths[i], q);
     3832
     3833      int old_pos = -1;
    35353834      //assume new_pos<old_pos
    3536       for (int z=0;z<=c->strat->sl;z++)
    3537       {
    3538         if (c->strat->S[z]==c->S->m[i])
    3539         {
    3540           old_pos=z;
    3541           break;
    3542         }
    3543       }
    3544       if (old_pos== -1)
    3545         for (int z=new_pos-1;z>=0;z--)
    3546         {
    3547           if (c->strat->S[z]==c->S->m[i])
    3548           {
    3549             old_pos=z;
    3550             break;
    3551           }
    3552         }
    3553       assume(old_pos>=0);
    3554       assume(new_pos<=old_pos);
    3555       assume(pLength(c->strat->S[old_pos])==c->lengths[i]);
    3556       c->strat->lenS[old_pos]=c->lengths[i];
     3835      for (int z = 0; z <= c->strat->sl; z++)
     3836      {
     3837        if (c->strat->S[z] == c->S->m[i])
     3838        {
     3839          old_pos = z;
     3840          break;
     3841        }
     3842      }
     3843      if (old_pos == -1)
     3844        for (int z = new_pos - 1; z >= 0; z--)
     3845        {
     3846          if (c->strat->S[z] == c->S->m[i])
     3847          {
     3848            old_pos = z;
     3849            break;
     3850          }
     3851        }
     3852      assume (old_pos >= 0);
     3853      assume (new_pos <= old_pos);
     3854      assume (pLength (c->strat->S[old_pos]) == c->lengths[i]);
     3855      c->strat->lenS[old_pos] = c->lengths[i];
    35573856      if (c->strat->lenSw)
    3558         c->strat->lenSw[old_pos]=q;
    3559       if (new_pos<old_pos)
    3560         move_forward_in_S(old_pos,new_pos,c->strat);
    3561       length_one_crit(c,i,c->lengths[i]);
    3562     }
    3563   }
    3564 }
    3565 
    3566 #if 0 // currently unused
    3567 static sorted_pair_node* pop_pair(slimgb_alg* c)
    3568 {
    3569   clean_top_of_pair_list(c);
    3570 
    3571   if(c->pair_top<0) return NULL;
    3572   else return (c->apairs[c->pair_top--]);
    3573 }
    3574 #endif
    3575 
    3576 void slimgb_alg::cleanDegs(int lower, int upper)
    3577 {
    3578   assume(is_homog);
     3857        c->strat->lenSw[old_pos] = q;
     3858      if (new_pos < old_pos)
     3859        move_forward_in_S (old_pos, new_pos, c->strat);
     3860      length_one_crit (c, i, c->lengths[i]);
     3861    }
     3862  }
     3863}
     3864
     3865#if 0                           // currently unused
     3866static sorted_pair_node *
     3867pop_pair (slimgb_alg * c)
     3868{
     3869  clean_top_of_pair_list (c);
     3870
     3871  if (c->pair_top < 0)