source: git/kernel/GBEngine/tgb.cc @ e21795

spielwiese
Last change on this file since e21795 was f91f8f3, checked in by Hans Schoenemann <hannes@…>, 8 years ago
comments on p_Cleardenom in slimgb
  • Property mode set to 100644
File size: 125.9 KB
Line 
1//! \file tgb.cc
2//       multiple rings
3//       shorten_tails und dessen Aufrufe pruefen wlength!!!
4/****************************************
5*  Computer Algebra System SINGULAR     *
6****************************************/
7/*
8* ABSTRACT: slimgb and F4 implementation
9*/
10//#include <vector>
11//using namespace std;
12
13///@TODO: delay nur auf Sugarvergr?erung
14///@TODO: grade aus ecartS, setze dazu strat->honey; und nutze p.ecart
15///@TODO: no tail reductions in syz comp
16#include <kernel/mod2.h>
17
18#include <kernel/GBEngine/tgb.h>
19#include <kernel/GBEngine/tgb_internal.h>
20#include <kernel/GBEngine/tgbgauss.h>
21
22#include <misc/options.h>
23#include <kernel/digitech.h>
24#include <polys/nc/nc.h>
25#include <polys/nc/sca.h>
26#include <polys/prCopy.h>
27
28#include <coeffs/longrat.h> // nlQlogSize
29
30#include <stdlib.h>
31#include <stdio.h>
32#include <queue>
33
34#define BUCKETS_FOR_NORO_RED 1
35#define SR_HDL(A) ((long)(A))
36static const int bundle_size = 100;
37static const int bundle_size_noro = 10000;
38static const int delay_factor = 3;
39#define ADD_LATER_SIZE 500
40#if 1
41static omBin lm_bin = NULL;
42static int add_to_reductors(slimgb_alg* c, poly h, int len, int ecart, BOOLEAN simplified=FALSE);
43static void multi_reduction(red_object* los, int & losl, slimgb_alg* c);
44static void multi_reduce_step(find_erg & erg, red_object* r, slimgb_alg* c);
45static BOOLEAN extended_product_criterion(poly p1, poly gcd1, poly p2, poly gcd2, slimgb_alg* c);
46static poly gcd_of_terms(poly p, ring r);
47static int tgb_pair_better_gen(const void* ap,const void* bp);
48static BOOLEAN pair_better(sorted_pair_node* a,sorted_pair_node* b, slimgb_alg* c=NULL);
49static BOOLEAN state_is(calc_state state, const int & i, const int & j, slimgb_alg* c);
50static void super_clean_top_of_pair_list(slimgb_alg* c);
51static int simple_posInS (kStrategy strat, poly p,int len, wlen_type wlen);
52static int* make_connections(int from, int to, poly bound, slimgb_alg* c);
53static BOOLEAN has_t_rep(const int & arg_i, const int & arg_j, slimgb_alg* state);
54static void shorten_tails(slimgb_alg* c, poly monom);
55static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n=0);
56static poly redNFTail (poly h,const int sl,kStrategy strat, int len);
57static int bucket_guess(kBucket* bucket);
58
59static void simplify_poly (poly p, ring r)
60{
61  assume (r == currRing);
62  if(!rField_is_Zp (r))
63  {
64    p_Cleardenom (p, r);
65    //includes p_Content(p,r);
66  }
67  else
68    pNorm (p);
69}
70
71//static const BOOLEAN up_to_radical=TRUE;
72
73int slim_nsize (number n, ring r)
74{
75  if(rField_is_Zp (r))
76  {
77    return 1;
78  }
79  if(rField_is_Q (r))
80  {
81    return nlQlogSize (n, r->cf);
82  }
83  else
84  {
85    return n_Size (n, r);
86  }
87}
88
89static BOOLEAN monomial_root (poly m, ring r)
90{
91  BOOLEAN changed = FALSE;
92  int i;
93  for(i = 1; i <= rVar (r); i++)
94  {
95    int e = p_GetExp (m, i, r);
96    if(e > 1)
97    {
98      p_SetExp (m, i, 1, r);
99      changed = TRUE;
100    }
101  }
102  if(changed)
103  {
104    p_Setm (m, r);
105  }
106  return changed;
107}
108
109static BOOLEAN polynomial_root (poly h, ring r)
110{
111  poly got = gcd_of_terms (h, r);
112  BOOLEAN changed = FALSE;
113  if((got != NULL) && (TEST_V_UPTORADICAL))
114  {
115    poly copy = p_Copy (got, r);
116    //p_wrp(got,c->r);
117    changed = monomial_root (got, r);
118    if(changed)
119    {
120      poly div_by = pDivide (copy, got);
121      poly iter = h;
122      while(iter)
123      {
124        pExpVectorSub (iter, div_by);
125        pIter (iter);
126      }
127      p_Delete (&div_by, r);
128      if(TEST_OPT_PROT)
129        PrintS ("U");
130    }
131    p_Delete (&copy, r);
132  }
133  p_Delete (&got, r);
134  return changed;
135}
136
137static inline poly p_Init_Special (const ring r)
138{
139  return p_Init (r, lm_bin);
140}
141
142static inline poly pOne_Special (const ring r = currRing)
143{
144  poly rc = p_Init_Special (r);
145  pSetCoeff0 (rc, n_Init (1, r));
146  return rc;
147}
148
149// zum Initialiseren: in t_rep_gb plazieren:
150
151#endif
152#define LEN_VAR3
153#define degbound(p) assume(pTotaldegree(p)<10)
154//#define inDebug(p) assume((debug_Ideal==NULL)||(kNF(debug_Ideal,NULL,p,0,0)==0))
155
156//die meisten Varianten stossen sich an coef_buckets
157
158#ifdef LEN_VAR1
159// erste Variante: Laenge: Anzahl der Monome
160static inline int pSLength (poly p, int l)
161{
162  return l;
163}
164
165static inline int kSBucketLength (kBucket * bucket, poly lm)
166{
167  return bucket_guess (bucket);
168}
169#endif
170
171#ifdef LEN_VAR2
172// 2. Variante: Laenge: Platz fuer die Koeff.
173int pSLength (poly p, int l)
174{
175  int s = 0;
176  while(p != NULL)
177  {
178    s += nSize (pGetCoeff (p));
179    pIter (p);
180  }
181  return s;
182}
183
184int kSBucketLength (kBucket * b, poly lm)
185{
186  int s = 0;
187  int i;
188  for(i = MAX_BUCKET; i >= 0; i--)
189  {
190    s += pSLength (b->buckets[i], 0);
191  }
192  return s;
193}
194#endif
195
196#ifdef LEN_VAR3
197static inline wlen_type pSLength (poly p, int l)
198{
199  wlen_type c;
200  number coef = pGetCoeff (p);
201  if(rField_is_Q (currRing))
202  {
203    c = nlQlogSize (coef, currRing->cf);
204  }
205  else
206    c = nSize (coef);
207  if(!(TEST_V_COEFSTRAT))
208  {
209    return (wlen_type) c *(wlen_type) l /*pLength(p) */ ;
210  }
211  else
212  {
213    wlen_type res = l;
214    res *= c;
215    res *= c;
216    return res;
217  }
218}
219
220//! TODO CoefBuckets bercksichtigen
221wlen_type kSBucketLength (kBucket * b, poly lm = NULL)
222{
223  int s = 0;
224  wlen_type c;
225  number coef;
226  if(lm == NULL)
227    coef = pGetCoeff (kBucketGetLm (b));
228  //c=nSize(pGetCoeff(kBucketGetLm(b)));
229  else
230    coef = pGetCoeff (lm);
231  //c=nSize(pGetCoeff(lm));
232  if(rField_is_Q (currRing))
233  {
234    c = nlQlogSize (coef, currRing->cf);
235  }
236  else
237    c = nSize (coef);
238
239  int i;
240  for(i = b->buckets_used; i >= 0; i--)
241  {
242    assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
243    s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
244  }
245#ifdef HAVE_COEF_BUCKETS
246  assume (b->buckets[0] == kBucketGetLm (b));
247  if(b->coef[0] != NULL)
248  {
249    if(rField_is_Q (currRing))
250    {
251      int modifier = nlQlogSize (pGetCoeff (b->coef[0]), currRing->cf);
252      c += modifier;
253    }
254    else
255    {
256      int modifier = nSize (pGetCoeff (b->coef[0]));
257      c *= modifier;
258    }
259  }
260#endif
261  if(!(TEST_V_COEFSTRAT))
262  {
263    return s * c;
264  }
265  else
266  {
267    wlen_type res = s;
268    res *= c;
269    res *= c;
270    return res;
271  }
272}
273#endif
274#ifdef LEN_VAR5
275static inline wlen_type pSLength (poly p, int l)
276{
277  int c;
278  number coef = pGetCoeff (p);
279  if(rField_is_Q (currRing))
280  {
281    c = nlQlogSize (coef, currRing->cf);
282  }
283  else
284    c = nSize (coef);
285  wlen_type erg = l;
286  erg *= c;
287  erg *= c;
288  //PrintS("lenvar 5");
289  assume (erg >= 0);
290  return erg; /*pLength(p) */ ;
291}
292
293//! TODO CoefBuckets bercksichtigen
294wlen_type kSBucketLength (kBucket * b, poly lm = NULL)
295{
296  wlen_type s = 0;
297  int c;
298  number coef;
299  if(lm == NULL)
300    coef = pGetCoeff (kBucketGetLm (b));
301  //c=nSize(pGetCoeff(kBucketGetLm(b)));
302  else
303    coef = pGetCoeff (lm);
304  //c=nSize(pGetCoeff(lm));
305  if(rField_is_Q (currRing))
306  {
307    c = nlQlogSize (coef, currRing->cf);
308  }
309  else
310    c = nSize (coef);
311
312  int i;
313  for(i = b->buckets_used; i >= 0; i--)
314  {
315    assume ((b->buckets_length[i] == 0) || (b->buckets[i] != NULL));
316    s += b->buckets_length[i] /*pLength(b->buckets[i]) */ ;
317  }
318#ifdef HAVE_COEF_BUCKETS
319  assume (b->buckets[0] == kBucketGetLm (b));
320  if(b->coef[0] != NULL)
321  {
322    if(rField_is_Q (currRing))
323    {
324      int modifier = nlQlogSize (pGetCoeff (b->coef[0]), currRing->cf);
325      c += modifier;
326    }
327    else
328    {
329      int modifier = nSize (pGetCoeff (b->coef[0]));
330      c *= modifier;
331    }
332  }
333#endif
334  wlen_type erg = s;
335  erg *= c;
336  erg *= c;
337  return erg;
338}
339#endif
340
341#ifdef LEN_VAR4
342// 4.Variante: Laenge: Platz fuer Leitk * (1+Platz fuer andere Koeff.)
343int pSLength (poly p, int l)
344{
345  int s = 1;
346  int c = nSize (pGetCoeff (p));
347  pIter (p);
348  while(p != NULL)
349  {
350    s += nSize (pGetCoeff (p));
351    pIter (p);
352  }
353  return s * c;
354}
355
356int kSBucketLength (kBucket * b)
357{
358  int s = 1;
359  int c = nSize (pGetCoeff (kBucketGetLm (b)));
360  int i;
361  for(i = MAX_BUCKET; i > 0; i--)
362  {
363    if(b->buckets[i] == NULL)
364      continue;
365    s += pSLength (b->buckets[i], 0);
366  }
367  return s * c;
368}
369#endif
370//BUG/TODO this stuff will fail on internal Schreyer orderings
371static BOOLEAN elength_is_normal_length (poly p, slimgb_alg * c)
372{
373  ring r = c->r;
374  if(p_GetComp (p, r) != 0)
375    return FALSE;
376  if(c->lastDpBlockStart <= (currRing->N))
377  {
378    int i;
379    for(i = 1; i < c->lastDpBlockStart; i++)
380    {
381      if(p_GetExp (p, i, r) != 0)
382      {
383        break;
384      }
385    }
386    if(i >= c->lastDpBlockStart)
387    {
388      //wrp(p);
389      //PrintS("\n");
390      return TRUE;
391    }
392    else
393      return FALSE;
394  }
395  else
396    return FALSE;
397}
398
399static BOOLEAN lies_in_last_dp_block (poly p, slimgb_alg * c)
400{
401  ring r = c->r;
402  if(p_GetComp (p, r) != 0)
403    return FALSE;
404  if(c->lastDpBlockStart <= (currRing->N))
405  {
406    int i;
407    for(i = 1; i < c->lastDpBlockStart; i++)
408    {
409      if(p_GetExp (p, i, r) != 0)
410      {
411        break;
412      }
413    }
414    if(i >= c->lastDpBlockStart)
415    {
416      //wrp(p);
417      //PrintS("\n");
418      return TRUE;
419    }
420    else
421      return FALSE;
422  }
423  else
424    return FALSE;
425}
426
427static int get_last_dp_block_start (ring r)
428{
429  //ring r=c->r;
430  int last_block;
431
432  if(rRing_has_CompLastBlock (r))
433  {
434    last_block = rBlocks (r) - 3;
435  }
436  else
437  {
438    last_block = rBlocks (r) - 2;
439  }
440  assume (last_block >= 0);
441  if(r->order[last_block] == ringorder_dp)
442    return r->block0[last_block];
443  return (currRing->N) + 1;
444}
445
446static wlen_type do_pELength (poly p, slimgb_alg * c, int dlm = -1)
447{
448  if(p == NULL)
449    return 0;
450  wlen_type s = 0;
451  poly pi = p;
452  if(dlm < 0)
453  {
454    dlm = c->pTotaldegree (p);
455    s = 1;
456    pi = p->next;
457  }
458
459  while(pi)
460  {
461    int d = c->pTotaldegree (pi);
462    if(d > dlm)
463      s += 1 + d - dlm;
464    else
465      ++s;
466    pi = pi->next;
467  }
468  return s;
469}
470
471wlen_type pELength (poly p, slimgb_alg * c, ring /*r*/)
472{
473  if(p == NULL)
474    return 0;
475  wlen_type s = 0;
476  poly pi = p;
477  int dlm;
478  dlm = c->pTotaldegree (p);
479  s = 1;
480  pi = p->next;
481
482  while(pi)
483  {
484    int d = c->pTotaldegree (pi);
485    if(d > dlm)
486      s += 1 + d - dlm;
487    else
488      ++s;
489    pi = pi->next;
490  }
491  return s;
492}
493
494wlen_type kEBucketLength (kBucket * b, poly lm, slimgb_alg * ca)
495{
496  wlen_type s = 0;
497  if(lm == NULL)
498  {
499    lm = kBucketGetLm (b);
500  }
501  if(lm == NULL)
502    return 0;
503  if(elength_is_normal_length (lm, ca))
504  {
505    return bucket_guess (b);
506  }
507  int d = ca->pTotaldegree (lm);
508#if 0
509  assume (sugar >= d);
510  s = 1 + (bucket_guess (b) - 1) * (sugar - d + 1);
511  return s;
512#else
513
514  //int d=pTotaldegree(lm,ca->r);
515  int i;
516  for(i = b->buckets_used; i >= 0; i--)
517  {
518    if(b->buckets[i] == NULL)
519      continue;
520
521    if((ca->pTotaldegree (b->buckets[i]) <= d)
522       && (elength_is_normal_length (b->buckets[i], ca)))
523    {
524      s += b->buckets_length[i];
525    }
526    else
527    {
528      s += do_pELength (b->buckets[i], ca, d);
529    }
530  }
531  return s;
532#endif
533}
534
535static inline int pELength (poly p, slimgb_alg * c, int l)
536{
537  if(p == NULL)
538    return 0;
539  if((l > 0) && (elength_is_normal_length (p, c)))
540    return l;
541  return do_pELength (p, c);
542}
543
544static inline wlen_type pQuality (poly p, slimgb_alg * c, int l = -1)
545{
546  if(l < 0)
547    l = pLength (p);
548  if(c->isDifficultField)
549  {
550    if(c->eliminationProblem)
551    {
552      wlen_type cs;
553      number coef = pGetCoeff (p);
554      if(rField_is_Q (currRing))
555      {
556        cs = nlQlogSize (coef, currRing->cf);
557      }
558      else
559        cs = nSize (coef);
560      wlen_type erg = cs;
561      if(TEST_V_COEFSTRAT)
562        erg *= cs;
563      //erg*=cs;//for quadratic
564      erg *= pELength (p, c, l);
565      //FIXME: not quadratic coeff size
566      //return cs*pELength(p,c,l);
567      return erg;
568    }
569    //PrintS("I am here");
570    wlen_type r = pSLength (p, l);
571    assume (r >= 0);
572    return r;
573  }
574  if(c->eliminationProblem)
575    return pELength (p, c, l);
576  return l;
577}
578
579static inline int pTotaldegree_full (poly p)
580{
581  int r = 0;
582  while(p)
583  {
584    int d = pTotaldegree (p);
585    r = si_max (r, d);
586    pIter (p);
587  }
588  return r;
589}
590
591wlen_type red_object::guess_quality (slimgb_alg * c)
592{
593  //works at the moment only for lenvar 1, because in different
594  //case, you have to look on coefs
595  wlen_type s = 0;
596  if(c->isDifficultField)
597  {
598    //s=kSBucketLength(bucket,this->p);
599    if(c->eliminationProblem)
600    {
601      wlen_type cs;
602      number coef;
603
604      coef = pGetCoeff (kBucketGetLm (bucket));
605      //c=nSize(pGetCoeff(kBucketGetLm(b)));
606
607      //c=nSize(pGetCoeff(lm));
608      if(rField_is_Q (currRing))
609      {
610        cs = nlQlogSize (coef, currRing->cf);
611      }
612      else
613        cs = nSize (coef);
614#ifdef HAVE_COEF_BUCKETS
615      if(bucket->coef[0] != NULL)
616      {
617        if(rField_is_Q (currRing))
618        {
619          int modifier = nlQlogSize (pGetCoeff (bucket->coef[0]), currRing->cf);
620          cs += modifier;
621        }
622        else
623        {
624          int modifier = nSize (pGetCoeff (bucket->coef[0]));
625          cs *= modifier;
626        }
627      }
628#endif
629      //FIXME:not quadratic
630      wlen_type erg = kEBucketLength (this->bucket, this->p, c);
631      //erg*=cs;//for quadratic
632      erg *= cs;
633      if(TEST_V_COEFSTRAT)
634        erg *= cs;
635      //return cs*kEBucketLength(this->bucket,this->p,c);
636      return erg;
637    }
638    s = kSBucketLength (bucket, NULL);
639  }
640  else
641  {
642    if(c->eliminationProblem)
643      //if (false)
644      s = kEBucketLength (this->bucket, this->p, c);
645    else
646      s = bucket_guess (bucket);
647  }
648  return s;
649}
650
651#if 0                           //currently unused
652static void finalize_reduction_step (reduction_step * r)
653{
654  delete r;
655}
656#endif
657#if 0                           //currently unused
658static int LObject_better_gen (const void *ap, const void *bp)
659{
660  LObject *a = *(LObject **) ap;
661  LObject *b = *(LObject **) bp;
662  return (pLmCmp (a->p, b->p));
663}
664#endif
665static int red_object_better_gen (const void *ap, const void *bp)
666{
667  return (pLmCmp (((red_object *) ap)->p, ((red_object *) bp)->p));
668}
669
670#if 0                           //currently unused
671static int pLmCmp_func_inverted (const void *ap1, const void *ap2)
672{
673  poly p1, p2;
674  p1 = *((poly *) ap1);
675  p2 = *((poly *) ap2);
676  return -pLmCmp (p1, p2);
677}
678#endif
679
680int tgb_pair_better_gen2 (const void *ap, const void *bp)
681{
682  return (-tgb_pair_better_gen (ap, bp));
683}
684
685int kFindDivisibleByInS_easy (kStrategy strat, const red_object & obj)
686{
687  int i;
688  long not_sev = ~obj.sev;
689  poly p = obj.p;
690  for(i = 0; i <= strat->sl; i++)
691  {
692    if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
693      return i;
694  }
695  return -1;
696}
697
698int kFindDivisibleByInS_easy (kStrategy strat, poly p, long sev)
699{
700  int i;
701  long not_sev = ~sev;
702  for(i = 0; i <= strat->sl; i++)
703  {
704    if(pLmShortDivisibleBy (strat->S[i], strat->sevS[i], p, not_sev))
705      return i;
706  }
707  return -1;
708}
709
710static int
711posInPairs (sorted_pair_node ** p, int pn, sorted_pair_node * qe,
712            slimgb_alg * c, int an = 0)
713{
714  if(pn == 0)
715    return 0;
716
717  int length = pn - 1;
718  int i;
719  //int an = 0;
720  int en = length;
721
722  if(pair_better (qe, p[en], c))
723    return length + 1;
724
725  while(1)
726  {
727    //if (an >= en-1)
728    if(en - 1 <= an)
729    {
730      if(pair_better (p[an], qe, c))
731        return an;
732      return en;
733    }
734    i = (an + en) / 2;
735    if(pair_better (p[i], qe, c))
736      en = i;
737    else
738      an = i;
739  }
740}
741
742static BOOLEAN ascending (int *i, int top)
743{
744  if(top < 1)
745    return TRUE;
746  if(i[top] < i[top - 1])
747    return FALSE;
748  return ascending (i, top - 1);
749}
750
751sorted_pair_node **spn_merge (sorted_pair_node ** p, int pn,
752                              sorted_pair_node ** q, int qn, slimgb_alg * c)
753{
754  int i;
755  int *a = (int *) omalloc (qn * sizeof (int));
756//   int mc;
757//   PrintS("Debug\n");
758//   for(mc=0;mc<qn;mc++)
759// {
760//     wrp(q[mc]->lcm_of_lm);
761//     PrintS("\n");
762// }
763//    PrintS("Debug they are in\n");
764//   for(mc=0;mc<pn;mc++)
765// {
766//     wrp(p[mc]->lcm_of_lm);
767//     PrintS("\n");
768// }
769  int lastpos = 0;
770  for(i = 0; i < qn; i++)
771  {
772    lastpos = posInPairs (p, pn, q[i], c, si_max (lastpos - 1, 0));
773    //   cout<<lastpos<<"\n";
774    a[i] = lastpos;
775  }
776  if((pn + qn) > c->max_pairs)
777  {
778    p =
779      (sorted_pair_node **) omrealloc (p,
780                                       2 * (pn +
781                                            qn) *
782                                       sizeof (sorted_pair_node *));
783    c->max_pairs = 2 * (pn + qn);
784  }
785  for(i = qn - 1; i >= 0; i--)
786  {
787    size_t size;
788    if(qn - 1 > i)
789      size = (a[i + 1] - a[i]) * sizeof (sorted_pair_node *);
790    else
791      size = (pn - a[i]) * sizeof (sorted_pair_node *); //as indices begin with 0
792    memmove (p + a[i] + (1 + i), p + a[i], size);
793    p[a[i] + i] = q[i];
794  }
795  omfree (a);
796  return p;
797}
798
799static BOOLEAN
800trivial_syzygie (int pos1, int pos2, poly bound, slimgb_alg * c)
801{
802  poly p1 = c->S->m[pos1];
803  poly p2 = c->S->m[pos2];
804
805  if(pGetComp (p1) > 0 || pGetComp (p2) > 0)
806    return FALSE;
807  int i = 1;
808  poly m = NULL;
809  poly gcd1 = c->gcd_of_terms[pos1];
810  poly gcd2 = c->gcd_of_terms[pos2];
811
812  if((gcd1 != NULL) && (gcd2 != NULL))
813  {
814    gcd1->next = gcd2;          //may ordered incorrect
815    m = gcd_of_terms (gcd1, c->r);
816    gcd1->next = NULL;
817  }
818  if(m == NULL)
819  {
820    loop
821    {
822      if(pGetExp (p1, i) + pGetExp (p2, i) > pGetExp (bound, i))
823        return FALSE;
824      if(i == (currRing->N))
825      {
826        //PrintS("trivial");
827        return TRUE;
828      }
829      i++;
830    }
831  }
832  else
833  {
834    loop
835    {
836      if(pGetExp (p1, i) - pGetExp (m, i) + pGetExp (p2, i) >
837         pGetExp (bound, i))
838      {
839        pDelete (&m);
840        return FALSE;
841      }
842      if(i == (currRing->N))
843      {
844        pDelete (&m);
845        //PrintS("trivial");
846        return TRUE;
847      }
848      i++;
849    }
850  }
851}
852
853//! returns position sets w as weight
854int find_best (red_object * r, int l, int u, wlen_type & w, slimgb_alg * c)
855{
856  int best = l;
857  int i;
858  w = r[l].guess_quality (c);
859  for(i = l + 1; i <= u; i++)
860  {
861    wlen_type w2 = r[i].guess_quality (c);
862    if(w2 < w)
863    {
864      w = w2;
865      best = i;
866    }
867  }
868  return best;
869}
870
871void red_object::canonicalize ()
872{
873  kBucketCanonicalize (bucket);
874}
875
876BOOLEAN good_has_t_rep (int i, int j, slimgb_alg * c)
877{
878  assume (i >= 0);
879  assume (j >= 0);
880  if(has_t_rep (i, j, c))
881    return TRUE;
882  //poly lm=pOne();
883  assume (c->tmp_lm != NULL);
884  poly lm = c->tmp_lm;
885
886  pLcm (c->S->m[i], c->S->m[j], lm);
887  pSetm (lm);
888  assume (lm != NULL);
889  //int deciding_deg= pTotaldegree(lm);
890  int *i_con = make_connections (i, j, lm, c);
891  //p_Delete(&lm,c->r);
892
893  for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
894  {
895    if(i_con[n] == j)
896    {
897      now_t_rep (i, j, c);
898      omFree (i_con);
899      return TRUE;
900    }
901  }
902  omfree (i_con);
903
904  return FALSE;
905}
906
907BOOLEAN lenS_correct (kStrategy strat)
908{
909  int i;
910  for(i = 0; i <= strat->sl; i++)
911  {
912    if(strat->lenS[i] != pLength (strat->S[i]))
913      return FALSE;
914  }
915  return TRUE;
916}
917
918
919static void cleanS (kStrategy strat, slimgb_alg * c)
920{
921  int i = 0;
922  LObject P;
923  while(i <= strat->sl)
924  {
925    P.p = strat->S[i];
926    P.sev = strat->sevS[i];
927    //int dummy=strat->sl;
928    //if(kFindDivisibleByInS(strat,&dummy,&P)!=i)
929    if(kFindDivisibleByInS_easy (strat, P.p, P.sev) != i)
930    {
931      deleteInS (i, strat);
932      //remember destroying poly
933      BOOLEAN found = FALSE;
934      int j;
935      for(j = 0; j < c->n; j++)
936      {
937        if(c->S->m[j] == P.p)
938        {
939          found = TRUE;
940          break;
941        }
942      }
943      if(!found)
944        pDelete (&P.p);
945      //remember additional reductors
946    }
947    else
948      i++;
949  }
950}
951
952static int bucket_guess (kBucket * bucket)
953{
954  int sum = 0;
955  int i;
956  for(i = bucket->buckets_used; i >= 0; i--)
957  {
958    if(bucket->buckets[i])
959      sum += bucket->buckets_length[i];
960  }
961  return sum;
962}
963
964static int
965add_to_reductors (slimgb_alg * c, poly h, int len, int ecart,
966                  BOOLEAN simplified)
967{
968  //inDebug(h);
969  assume (lenS_correct (c->strat));
970  assume (len == pLength (h));
971  int i;
972//   if (c->isDifficultField)
973//        i=simple_posInS(c->strat,h,pSLength(h,len),c->isDifficultField);
974//   else
975//     i=simple_posInS(c->strat,h,len,c->isDifficultField);
976
977  LObject P;
978  memset (&P, 0, sizeof (P));
979  P.tailRing = c->r;
980  P.p = h;                      /*p_Copy(h,c->r); */
981  P.ecart = ecart;
982  P.FDeg = c->r->pFDeg (P.p, c->r);
983  if(!(simplified))
984  {
985    if(!rField_is_Zp (c->r))
986    {
987      p_Cleardenom (P.p, c->r); //includes p_Content(P.p,c->r );
988    }
989    else
990      pNorm (P.p);
991    pNormalize (P.p);
992  }
993  wlen_type pq = pQuality (h, c, len);
994  i = simple_posInS (c->strat, h, len, pq);
995  c->strat->enterS (P, i, c->strat, -1);
996
997  c->strat->lenS[i] = len;
998  assume (pLength (c->strat->S[i]) == c->strat->lenS[i]);
999  if(c->strat->lenSw != NULL)
1000    c->strat->lenSw[i] = pq;
1001
1002  return i;
1003}
1004
1005static void length_one_crit (slimgb_alg * c, int pos, int len)
1006{
1007  if(c->nc)
1008    return;
1009  if(len == 1)
1010  {
1011    int i;
1012    for(i = 0; i < pos; i++)
1013    {
1014      if(c->lengths[i] == 1)
1015        c->states[pos][i] = HASTREP;
1016    }
1017    for(i = pos + 1; i < c->n; i++)
1018    {
1019      if(c->lengths[i] == 1)
1020        c->states[i][pos] = HASTREP;
1021    }
1022    if(!c->nc)
1023      shorten_tails (c, c->S->m[pos]);
1024  }
1025}
1026
1027static void move_forward_in_S (int old_pos, int new_pos, kStrategy strat)
1028{
1029  assume (old_pos >= new_pos);
1030  poly p = strat->S[old_pos];
1031  int ecart = strat->ecartS[old_pos];
1032  long sev = strat->sevS[old_pos];
1033  int s_2_r = strat->S_2_R[old_pos];
1034  int length = strat->lenS[old_pos];
1035  assume (length == pLength (strat->S[old_pos]));
1036  wlen_type length_w;
1037  if(strat->lenSw != NULL)
1038    length_w = strat->lenSw[old_pos];
1039  int i;
1040  for(i = old_pos; i > new_pos; i--)
1041  {
1042    strat->S[i] = strat->S[i - 1];
1043    strat->ecartS[i] = strat->ecartS[i - 1];
1044    strat->sevS[i] = strat->sevS[i - 1];
1045    strat->S_2_R[i] = strat->S_2_R[i - 1];
1046  }
1047  if(strat->lenS != NULL)
1048    for(i = old_pos; i > new_pos; i--)
1049      strat->lenS[i] = strat->lenS[i - 1];
1050  if(strat->lenSw != NULL)
1051    for(i = old_pos; i > new_pos; i--)
1052      strat->lenSw[i] = strat->lenSw[i - 1];
1053
1054  strat->S[new_pos] = p;
1055  strat->ecartS[new_pos] = ecart;
1056  strat->sevS[new_pos] = sev;
1057  strat->S_2_R[new_pos] = s_2_r;
1058  strat->lenS[new_pos] = length;
1059  if(strat->lenSw != NULL)
1060    strat->lenSw[new_pos] = length_w;
1061  //assume(lenS_correct(strat));
1062}
1063
1064static void move_backward_in_S (int old_pos, int new_pos, kStrategy strat)
1065{
1066  assume (old_pos <= new_pos);
1067  poly p = strat->S[old_pos];
1068  int ecart = strat->ecartS[old_pos];
1069  long sev = strat->sevS[old_pos];
1070  int s_2_r = strat->S_2_R[old_pos];
1071  int length = strat->lenS[old_pos];
1072  assume (length == pLength (strat->S[old_pos]));
1073  wlen_type length_w;
1074  if(strat->lenSw != NULL)
1075    length_w = strat->lenSw[old_pos];
1076  int i;
1077  for(i = old_pos; i < new_pos; i++)
1078  {
1079    strat->S[i] = strat->S[i + 1];
1080    strat->ecartS[i] = strat->ecartS[i + 1];
1081    strat->sevS[i] = strat->sevS[i + 1];
1082    strat->S_2_R[i] = strat->S_2_R[i + 1];
1083  }
1084  if(strat->lenS != NULL)
1085    for(i = old_pos; i < new_pos; i++)
1086      strat->lenS[i] = strat->lenS[i + 1];
1087  if(strat->lenSw != NULL)
1088    for(i = old_pos; i < new_pos; i++)
1089      strat->lenSw[i] = strat->lenSw[i + 1];
1090
1091  strat->S[new_pos] = p;
1092  strat->ecartS[new_pos] = ecart;
1093  strat->sevS[new_pos] = sev;
1094  strat->S_2_R[new_pos] = s_2_r;
1095  strat->lenS[new_pos] = length;
1096  if(strat->lenSw != NULL)
1097    strat->lenSw[new_pos] = length_w;
1098  //assume(lenS_correct(strat));
1099}
1100
1101static int *make_connections (int from, int to, poly bound, slimgb_alg * c)
1102{
1103  ideal I = c->S;
1104  int *cans = (int *) omAlloc (c->n * sizeof (int));
1105  int *connected = (int *) omAlloc (c->n * sizeof (int));
1106  cans[0] = to;
1107  int cans_length = 1;
1108  connected[0] = from;
1109  int last_cans_pos = -1;
1110  int connected_length = 1;
1111  long neg_bounds_short = ~p_GetShortExpVector (bound, c->r);
1112
1113  int not_yet_found = cans_length;
1114  int con_checked = 0;
1115  int pos;
1116
1117  while(TRUE)
1118  {
1119    if((con_checked < connected_length) && (not_yet_found > 0))
1120    {
1121      pos = connected[con_checked];
1122      for(int i = 0; i < cans_length; i++)
1123      {
1124        if(cans[i] < 0)
1125          continue;
1126        //FIXME: triv. syz. does not hold on noncommutative, check it for modules
1127        if((has_t_rep (pos, cans[i], c))
1128           || ((!rIsPluralRing (c->r))
1129               && (trivial_syzygie (pos, cans[i], bound, c))))
1130        {
1131          connected[connected_length] = cans[i];
1132          connected_length++;
1133          cans[i] = -1;
1134          --not_yet_found;
1135
1136          if(connected[connected_length - 1] == to)
1137          {
1138            if(connected_length < c->n)
1139            {
1140              connected[connected_length] = -1;
1141            }
1142            omFree (cans);
1143            return connected;
1144          }
1145        }
1146      }
1147      con_checked++;
1148    }
1149    else
1150    {
1151      for(last_cans_pos++; last_cans_pos <= c->n; last_cans_pos++)
1152      {
1153        if(last_cans_pos == c->n)
1154        {
1155          if(connected_length < c->n)
1156          {
1157            connected[connected_length] = -1;
1158          }
1159          omfree (cans);
1160          return connected;
1161        }
1162        if((last_cans_pos == from) || (last_cans_pos == to))
1163          continue;
1164        if(p_LmShortDivisibleBy
1165           (I->m[last_cans_pos], c->short_Exps[last_cans_pos], bound,
1166            neg_bounds_short, c->r))
1167        {
1168          cans[cans_length] = last_cans_pos;
1169          cans_length++;
1170          break;
1171        }
1172      }
1173      not_yet_found++;
1174      for(int i = 0; i < con_checked; i++)
1175      {
1176        if(has_t_rep (connected[i], last_cans_pos, c))
1177        {
1178          connected[connected_length] = last_cans_pos;
1179          connected_length++;
1180          cans[cans_length - 1] = -1;
1181          --not_yet_found;
1182          if(connected[connected_length - 1] == to)
1183          {
1184            if(connected_length < c->n)
1185            {
1186              connected[connected_length] = -1;
1187            }
1188            omFree (cans);
1189            return connected;
1190          }
1191          break;
1192        }
1193      }
1194    }
1195  }
1196  if(connected_length < c->n)
1197  {
1198    connected[connected_length] = -1;
1199  }
1200  omfree (cans);
1201  return connected;
1202}
1203
1204#ifdef HEAD_BIN
1205static inline poly p_MoveHead (poly p, omBin b)
1206{
1207  poly np;
1208  omTypeAllocBin (poly, np, b);
1209  memmove (np, p, omSizeWOfBin(b) * sizeof (long));
1210  omFreeBinAddr (p);
1211  return np;
1212}
1213#endif
1214
1215static void replace_pair (int &i, int &j, slimgb_alg * c)
1216{
1217  if(i < 0)
1218    return;
1219  c->soon_free = NULL;
1220  int syz_deg;
1221  poly lm = pOne ();
1222
1223  pLcm (c->S->m[i], c->S->m[j], lm);
1224  pSetm (lm);
1225
1226  int *i_con = make_connections (i, j, lm, c);
1227
1228  for(int n = 0; ((n < c->n) && (i_con[n] >= 0)); n++)
1229  {
1230    if(i_con[n] == j)
1231    {
1232      now_t_rep (i, j, c);
1233      omFree (i_con);
1234      p_Delete (&lm, c->r);
1235      return;
1236    }
1237  }
1238
1239  int *j_con = make_connections (j, i, lm, c);
1240
1241//   if(c->n>1)
1242//   {
1243//     if (i_con[1]>=0)
1244//       i=i_con[1];
1245//     else
1246//     {
1247//       if (j_con[1]>=0)
1248//         j=j_con[1];
1249//     }
1250  // }
1251
1252  int sugar = syz_deg = c->pTotaldegree (lm);
1253
1254  p_Delete (&lm, c->r);
1255  if(c->T_deg_full)             //Sugar
1256  {
1257    int t_i = c->T_deg_full[i] - c->T_deg[i];
1258    int t_j = c->T_deg_full[j] - c->T_deg[j];
1259    sugar += si_max (t_i, t_j);
1260    //Print("\n max: %d\n",max(t_i,t_j));
1261  }
1262
1263  for(int m = 0; ((m < c->n) && (i_con[m] >= 0)); m++)
1264  {
1265    if(c->T_deg_full != NULL)
1266    {
1267      int s1 = c->T_deg_full[i_con[m]] + syz_deg - c->T_deg[i_con[m]];
1268      if(s1 > sugar)
1269        continue;
1270    }
1271    if(c->weighted_lengths[i_con[m]] < c->weighted_lengths[i])
1272      i = i_con[m];
1273  }
1274  for(int m = 0; ((m < c->n) && (j_con[m] >= 0)); m++)
1275  {
1276    if(c->T_deg_full != NULL)
1277    {
1278      int s1 = c->T_deg_full[j_con[m]] + syz_deg - c->T_deg[j_con[m]];
1279      if(s1 > sugar)
1280        continue;
1281    }
1282    if(c->weighted_lengths[j_con[m]] < c->weighted_lengths[j])
1283      j = j_con[m];
1284  }
1285
1286  //can also try dependend search
1287  omfree (i_con);
1288  omfree (j_con);
1289  return;
1290}
1291
1292static void add_later (poly p, const char *prot, slimgb_alg * c)
1293{
1294  int i = 0;
1295  //check, if it is already in the queue
1296
1297  while(c->add_later->m[i] != NULL)
1298  {
1299    if(p_LmEqual (c->add_later->m[i], p, c->r))
1300      return;
1301    i++;
1302  }
1303  if(TEST_OPT_PROT)
1304    PrintS (prot);
1305  c->add_later->m[i] = p;
1306}
1307
1308static int simple_posInS (kStrategy strat, poly p, int len, wlen_type wlen)
1309{
1310  if(strat->sl == -1)
1311    return 0;
1312  if(strat->lenSw)
1313    return pos_helper (strat, p, (wlen_type) wlen, (wlen_set) strat->lenSw,
1314                       strat->S);
1315  return pos_helper (strat, p, len, strat->lenS, strat->S);
1316}
1317
1318/*2
1319 *if the leading term of p
1320 *divides the leading term of some S[i] it will be canceled
1321 */
1322static inline void
1323clearS (poly p, unsigned long p_sev, int l, int *at, int *k, kStrategy strat)
1324{
1325  assume (p_sev == pGetShortExpVector (p));
1326  if(!pLmShortDivisibleBy (p, p_sev, strat->S[*at], ~strat->sevS[*at]))
1327    return;
1328  if(l >= strat->lenS[*at])
1329    return;
1330  if(TEST_OPT_PROT)
1331    PrintS ("!");
1332  mflush ();
1333  //pDelete(&strat->S[*at]);
1334  deleteInS ((*at), strat);
1335  (*at)--;
1336  (*k)--;
1337//  assume(lenS_correct(strat));
1338}
1339
1340static int iq_crit (const void *ap, const void *bp)
1341{
1342  sorted_pair_node *a = *((sorted_pair_node **) ap);
1343  sorted_pair_node *b = *((sorted_pair_node **) bp);
1344  assume (a->i > a->j);
1345  assume (b->i > b->j);
1346
1347  if(a->deg < b->deg)
1348    return -1;
1349  if(a->deg > b->deg)
1350    return 1;
1351  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
1352  if(comp != 0)
1353    return comp;
1354  if(a->expected_length < b->expected_length)
1355    return -1;
1356  if(a->expected_length > b->expected_length)
1357    return 1;
1358  if(a->j > b->j)
1359    return 1;
1360  if(a->j < b->j)
1361    return -1;
1362  return 0;
1363}
1364
1365static wlen_type coeff_mult_size_estimate (int s1, int s2, ring r)
1366{
1367  if(rField_is_Q (r))
1368    return s1 + s2;
1369  else
1370    return s1 * s2;
1371}
1372
1373static wlen_type pair_weighted_length (int i, int j, slimgb_alg * c)
1374{
1375  if((c->isDifficultField) && (c->eliminationProblem))
1376  {
1377    int c1 = slim_nsize (p_GetCoeff (c->S->m[i], c->r), c->r);
1378    int c2 = slim_nsize (p_GetCoeff (c->S->m[j], c->r), c->r);
1379    wlen_type el1 = c->weighted_lengths[i] / c1;
1380    assume (el1 != 0);
1381    assume (c->weighted_lengths[i] % c1 == 0);
1382    wlen_type el2 = c->weighted_lengths[j] / c2;
1383    assume (el2 != 0);
1384    //assume (c->weighted_lengths[j] % c2 == 0); // fails in Tst/Plural/dmod_lib.tst
1385    //should be * for function fields
1386    //return (c1+c2) * (el1+el2-2);
1387    wlen_type res = coeff_mult_size_estimate (c1, c2, c->r);
1388    res *= el1 + el2 - 2;
1389    return res;
1390
1391  }
1392  if(c->isDifficultField)
1393  {
1394    //int cs=slim_nsize(p_GetCoeff(c->S->m[i],c->r),c->r)+
1395    //    slim_nsize(p_GetCoeff(c->S->m[j],c->r),c->r);
1396    if(!(TEST_V_COEFSTRAT))
1397    {
1398      wlen_type cs =
1399        coeff_mult_size_estimate (slim_nsize
1400                                  (p_GetCoeff (c->S->m[i], c->r), c->r),
1401                                  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
1402                                              c->r), c->r);
1403      return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
1404    }
1405    else
1406    {
1407
1408      wlen_type cs =
1409        coeff_mult_size_estimate (slim_nsize
1410                                  (p_GetCoeff (c->S->m[i], c->r), c->r),
1411                                  slim_nsize (p_GetCoeff (c->S->m[j], c->r),
1412                                              c->r), c->r);
1413      cs *= cs;
1414      return (wlen_type) (c->lengths[i] + c->lengths[j] - 2) * (wlen_type) cs;
1415    }
1416  }
1417  if(c->eliminationProblem)
1418  {
1419
1420    return (c->weighted_lengths[i] + c->weighted_lengths[j] - 2);
1421  }
1422  return c->lengths[i] + c->lengths[j] - 2;
1423
1424}
1425
1426sorted_pair_node **add_to_basis_ideal_quotient (poly h, slimgb_alg * c,
1427                                                int *ip)
1428{
1429  p_Test (h, c->r);
1430  assume (h != NULL);
1431  poly got = gcd_of_terms (h, c->r);
1432  if((got != NULL) && (TEST_V_UPTORADICAL))
1433  {
1434    poly copy = p_Copy (got, c->r);
1435    //p_wrp(got,c->r);
1436    BOOLEAN changed = monomial_root (got, c->r);
1437    if(changed)
1438    {
1439      poly div_by = pDivide (copy, got);
1440      poly iter = h;
1441      while(iter)
1442      {
1443        pExpVectorSub (iter, div_by);
1444        pIter (iter);
1445      }
1446      p_Delete (&div_by, c->r);
1447      PrintS ("U");
1448    }
1449    p_Delete (&copy, c->r);
1450  }
1451
1452#define ENLARGE(pointer, type) pointer=(type*) omrealloc(pointer, c->array_lengths*sizeof(type))
1453
1454#define ENLARGE_ALIGN(pointer, type) {if(pointer)\
1455         pointer=(type*)omReallocAligned(pointer, c->array_lengths*sizeof(type));\
1456         else pointer=(type*)omAllocAligned(c->array_lengths*sizeof(type));}
1457//  BOOLEAN corr=lenS_correct(c->strat);
1458  int sugar;
1459  int ecart = 0;
1460  ++(c->n);
1461  ++(c->S->ncols);
1462  int i, j;
1463  i = c->n - 1;
1464  sorted_pair_node **nodes =
1465    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
1466  int spc = 0;
1467  if(c->n > c->array_lengths)
1468  {
1469    c->array_lengths = c->array_lengths * 2;
1470    assume (c->array_lengths >= c->n);
1471    ENLARGE (c->T_deg, int);
1472    ENLARGE_ALIGN (c->tmp_pair_lm, poly);
1473    ENLARGE_ALIGN (c->tmp_spn, sorted_pair_node *);
1474
1475    ENLARGE_ALIGN (c->short_Exps, long);
1476    ENLARGE (c->lengths, int);
1477#ifndef HAVE_BOOST
1478#ifndef USE_STDVECBOOL
1479
1480    ENLARGE_ALIGN (c->states, char *);
1481#endif
1482#endif
1483    ENLARGE_ALIGN (c->gcd_of_terms, poly);
1484    //if (c->weighted_lengths!=NULL) {
1485    ENLARGE_ALIGN (c->weighted_lengths, wlen_type);
1486    //}
1487    //ENLARGE_ALIGN(c->S->m,poly);
1488  }
1489  pEnlargeSet (&c->S->m, c->n - 1, 1);
1490  if(c->T_deg_full)
1491    ENLARGE (c->T_deg_full, int);
1492  sugar = c->T_deg[i] = c->pTotaldegree (h);
1493  if(c->T_deg_full)
1494  {
1495    sugar = c->T_deg_full[i] = c->pTotaldegree_full (h);
1496    ecart = sugar - c->T_deg[i];
1497    assume (ecart >= 0);
1498  }
1499  c->tmp_pair_lm[i] = pOne_Special (c->r);
1500
1501  c->tmp_spn[i] = (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));
1502
1503  c->lengths[i] = pLength (h);
1504
1505  //necessary for correct weighted length
1506
1507  if(!rField_is_Zp (c->r))
1508  {
1509    p_Cleardenom (h, c->r); //includes p_Content(h,c->r);
1510  }
1511  else
1512    pNorm (h);
1513  pNormalize (h);
1514
1515  c->weighted_lengths[i] = pQuality (h, c, c->lengths[i]);
1516  c->gcd_of_terms[i] = got;
1517#ifdef HAVE_BOOST
1518  c->states.push_back (dynamic_bitset <> (i));
1519
1520#else
1521#ifdef USE_STDVECBOOL
1522
1523  c->states.push_back (vector < bool > (i));
1524
1525#else
1526  if(i > 0)
1527    c->states[i] = (char *) omAlloc (i * sizeof (char));
1528  else
1529    c->states[i] = NULL;
1530#endif
1531#endif
1532
1533  c->S->m[i] = h;
1534  c->short_Exps[i] = p_GetShortExpVector (h, c->r);
1535
1536#undef ENLARGE
1537#undef ENLARGE_ALIGN
1538  if(p_GetComp (h, currRing) <= c->syz_comp)
1539  {
1540    for(j = 0; j < i; j++)
1541    {
1542
1543
1544#ifndef HAVE_BOOST
1545      c->states[i][j] = UNCALCULATED;
1546#endif
1547      assume (p_LmDivisibleBy (c->S->m[i], c->S->m[j], c->r) ==
1548              p_LmShortDivisibleBy (c->S->m[i], c->short_Exps[i], c->S->m[j],
1549                                    ~(c->short_Exps[j]), c->r));
1550
1551      if(__p_GetComp (c->S->m[i], c->r) != __p_GetComp (c->S->m[j], c->r))
1552      {
1553        //c->states[i][j]=UNCALCULATED;
1554        //WARNUNG: be careful
1555        continue;
1556      }
1557      else if((!c->nc) && (c->lengths[i] == 1) && (c->lengths[j] == 1))
1558      {
1559        c->states[i][j] = HASTREP;
1560      }
1561      else if(((!c->nc) || (c->is_homog && rIsSCA (c->r)))
1562              && (pHasNotCF (c->S->m[i], c->S->m[j])))
1563//     else if ((!(c->nc)) &&  (pHasNotCF(c->S->m[i],c->S->m[j])))
1564      {
1565        c->easy_product_crit++;
1566        c->states[i][j] = HASTREP;
1567        continue;
1568      }
1569      else
1570        if(extended_product_criterion
1571           (c->S->m[i], c->gcd_of_terms[i], c->S->m[j], c->gcd_of_terms[j],
1572            c))
1573      {
1574        c->states[i][j] = HASTREP;
1575        c->extended_product_crit++;
1576        //PrintS("E");
1577      }
1578      //  if (c->states[i][j]==UNCALCULATED)
1579      //  {
1580
1581      if((TEST_V_FINDMONOM) && (!c->nc))
1582      {
1583        //PrintS("COMMU");
1584        //  if (c->lengths[i]==c->lengths[j])
1585        //  {
1586//             poly short_s=ksCreateShortSpoly(c->S->m[i],c->S->m[j],c->r);
1587//             if (short_s==NULL)
1588//             {
1589//                 c->states[i][j]=HASTREP;
1590//             }
1591//             else
1592//             {
1593//                 p_Delete(&short_s, currRing);
1594//             }
1595//         }
1596        if(c->lengths[i] + c->lengths[j] == 3)
1597        {
1598
1599
1600          poly short_s = ksCreateShortSpoly (c->S->m[i], c->S->m[j], c->r);
1601          if(short_s == NULL)
1602          {
1603            c->states[i][j] = HASTREP;
1604          }
1605          else
1606          {
1607            assume (pLength (short_s) == 1);
1608            if(TEST_V_UPTORADICAL)
1609              monomial_root (short_s, c->r);
1610            int iS = kFindDivisibleByInS_easy (c->strat, short_s,
1611                                               p_GetShortExpVector (short_s,
1612                                                                    c->r));
1613            if(iS < 0)
1614            {
1615              //PrintS("N");
1616              if(TRUE)
1617              {
1618                c->states[i][j] = HASTREP;
1619                add_later (short_s, "N", c);
1620              }
1621              else
1622                p_Delete (&short_s, currRing);
1623            }
1624            else
1625            {
1626              if(c->strat->lenS[iS] > 1)
1627              {
1628                //PrintS("O");
1629                if(TRUE)
1630                {
1631                  c->states[i][j] = HASTREP;
1632                  add_later (short_s, "O", c);
1633                }
1634                else
1635                  p_Delete (&short_s, currRing);
1636              }
1637              else
1638                p_Delete (&short_s, currRing);
1639              c->states[i][j] = HASTREP;
1640            }
1641
1642
1643          }
1644        }
1645      }
1646      //    if (short_s)
1647      //    {
1648      assume (spc <= j);
1649      sorted_pair_node *s = c->tmp_spn[spc];    //(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1650      s->i = si_max (i, j);
1651      s->j = si_min (i, j);
1652      assume (s->j == j);
1653      s->expected_length = pair_weighted_length (i, j, c);      //c->lengths[i]+c->lengths[j]-2;
1654
1655      poly lm = c->tmp_pair_lm[spc];    //=pOne_Special();
1656
1657      pLcm (c->S->m[i], c->S->m[j], lm);
1658      pSetm (lm);
1659      p_Test (lm, c->r);
1660      s->deg = c->pTotaldegree (lm);
1661
1662      if(c->T_deg_full)         //Sugar
1663      {
1664        int t_i = c->T_deg_full[s->i] - c->T_deg[s->i];
1665        int t_j = c->T_deg_full[s->j] - c->T_deg[s->j];
1666        s->deg += si_max (t_i, t_j);
1667        //Print("\n max: %d\n",max(t_i,t_j));
1668      }
1669      p_Test (lm, c->r);
1670      s->lcm_of_lm = lm;
1671      //          pDelete(&short_s);
1672      //assume(lm!=NULL);
1673      nodes[spc] = s;
1674      spc++;
1675
1676      // }
1677      //else
1678      //{
1679      //c->states[i][j]=HASTREP;
1680      //}
1681    }
1682  }                             //if syz_comp end
1683
1684  assume (spc <= i);
1685  //now ideal quotient crit
1686  qsort (nodes, spc, sizeof (sorted_pair_node *), iq_crit);
1687
1688  sorted_pair_node **nodes_final =
1689    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * i);
1690  int spc_final = 0;
1691  j = 0;
1692  while(j < spc)
1693  {
1694    int lower = j;
1695    int upper;
1696    BOOLEAN has = FALSE;
1697    for(upper = lower + 1; upper < spc; upper++)
1698    {
1699      if(!pLmEqual (nodes[lower]->lcm_of_lm, nodes[upper]->lcm_of_lm))
1700      {
1701        break;
1702      }
1703      if(has_t_rep (nodes[upper]->i, nodes[upper]->j, c))
1704        has = TRUE;
1705    }
1706    upper = upper - 1;
1707    int z;
1708    assume (spc_final <= j);
1709    for(z = 0; z < spc_final; z++)
1710    {
1711      if(p_LmDivisibleBy
1712         (nodes_final[z]->lcm_of_lm, nodes[lower]->lcm_of_lm, c->r))
1713      {
1714        has = TRUE;
1715        break;
1716      }
1717    }
1718
1719    if(has)
1720    {
1721      for(; lower <= upper; lower++)
1722      {
1723        //free_sorted_pair_node(nodes[lower],c->r);
1724        //omfree(nodes[lower]);
1725        nodes[lower] = NULL;
1726      }
1727      j = upper + 1;
1728      continue;
1729    }
1730    else
1731    {
1732      p_Test (nodes[lower]->lcm_of_lm, c->r);
1733      nodes[lower]->lcm_of_lm = pCopy (nodes[lower]->lcm_of_lm);
1734      assume (__p_GetComp (c->S->m[nodes[lower]->i], c->r) ==
1735              __p_GetComp (c->S->m[nodes[lower]->j], c->r));
1736      nodes_final[spc_final] =
1737        (sorted_pair_node *) omAlloc (sizeof (sorted_pair_node));
1738
1739      *(nodes_final[spc_final++]) = *(nodes[lower]);
1740      //c->tmp_spn[nodes[lower]->j]=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
1741      nodes[lower] = NULL;
1742      for(lower = lower + 1; lower <= upper; lower++)
1743      {
1744        //  free_sorted_pair_node(nodes[lower],c->r);
1745        //omfree(nodes[lower]);
1746        nodes[lower] = NULL;
1747      }
1748      j = upper + 1;
1749      continue;
1750    }
1751  }
1752
1753  //  Print("i:%d,spc_final:%d",i,spc_final);
1754
1755  assume (spc_final <= spc);
1756  omfree (nodes);
1757  nodes = NULL;
1758
1759  add_to_reductors (c, h, c->lengths[c->n - 1], ecart, TRUE);
1760  //i=posInS(c->strat,c->strat->sl,h,0 ecart);
1761  if(!(c->nc))
1762  {
1763    if(c->lengths[c->n - 1] == 1)
1764      shorten_tails (c, c->S->m[c->n - 1]);
1765  }
1766  //you should really update c->lengths, c->strat->lenS, and the oder of polys in strat if you sort after lengths
1767
1768  //for(i=c->strat->sl; i>0;i--)
1769  //  if(c->strat->lenS[i]<c->strat->lenS[i-1]) printf("fehler bei %d\n",i);
1770  if(c->Rcounter > 50)
1771  {
1772    c->Rcounter = 0;
1773    cleanS (c->strat, c);
1774  }
1775
1776#ifdef HAVE_PLURAL
1777  // for SCA:
1778  // here write at the end of nodes_final[spc_final,...,spc_final+lmdeg-1]
1779  if(rIsSCA (c->r))
1780  {
1781    const poly pNext = pNext (h);
1782
1783    if(pNext != NULL)
1784    {
1785      // for additional polynomials
1786      const unsigned int m_iFirstAltVar = scaFirstAltVar (c->r);
1787      const unsigned int m_iLastAltVar = scaLastAltVar (c->r);
1788
1789      int N =                   // c->r->N;
1790        m_iLastAltVar - m_iFirstAltVar + 1;     // should be enough
1791      // TODO: but we may also use got = gcd({m}_{m\in f}))!
1792
1793      poly *array_arg = (poly *) omalloc (N * sizeof (poly));   // !
1794      int j = 0;
1795
1796
1797      for(unsigned short v = m_iFirstAltVar; v <= m_iLastAltVar; v++)
1798        // for all x_v | Ann(lm(h))
1799        if(p_GetExp (h, v, c->r))       // TODO: use 'got' here!
1800        {
1801          assume (p_GetExp (h, v, c->r) == 1);
1802
1803          poly p = sca_pp_Mult_xi_pp (v, pNext, c->r);  // x_v * h;
1804
1805          if(p != NULL)         // if (x_v * h != 0)
1806            array_arg[j++] = p;
1807        }                       // for all x_v | Ann(lm(h))
1808
1809      c->introduceDelayedPairs (array_arg, j);
1810
1811      omFree (array_arg);       // !!!
1812    }
1813//     PrintS("Saturation - done!!!\n");
1814  }
1815#endif // if SCAlgebra
1816
1817
1818  if(!ip)
1819  {
1820    qsort (nodes_final, spc_final, sizeof (sorted_pair_node *),
1821           tgb_pair_better_gen2);
1822
1823
1824    c->apairs =
1825      spn_merge (c->apairs, c->pair_top + 1, nodes_final, spc_final, c);
1826    c->pair_top += spc_final;
1827    clean_top_of_pair_list (c);
1828    omfree (nodes_final);
1829    return NULL;
1830  }
1831  {
1832    *ip = spc_final;
1833    return nodes_final;
1834  }
1835}
1836
1837static poly redNF2 (poly h, slimgb_alg * c, int &len, number & m, int n)
1838{
1839  m = nInit (1);
1840  if(h == NULL)
1841    return NULL;
1842
1843  assume (len == pLength (h));
1844  kStrategy strat = c->strat;
1845  if(0 > strat->sl)
1846  {
1847    return h;
1848  }
1849  int j;
1850
1851  LObject P (h);
1852  P.SetShortExpVector ();
1853  P.bucket = kBucketCreate (currRing);
1854  // BOOLEAN corr=lenS_correct(strat);
1855  kBucketInit (P.bucket, P.p, len /*pLength(P.p) */ );
1856  //wlen_set lenSw=(wlen_set) c->strat->lenS;
1857  //FIXME: plainly wrong
1858  //strat->lenS;
1859  //if (strat->lenSw!=NULL)
1860  //  lenSw=strat->lenSw;
1861  //int max_pos=simple_posInS(strat,P.p);
1862  loop
1863  {
1864    //int dummy=strat->sl;
1865    j = kFindDivisibleByInS_easy (strat, P.p, P.sev);
1866    //j=kFindDivisibleByInS(strat,&dummy,&P);
1867    if((j >= 0) && ((!n) ||
1868                    ((strat->lenS[j] <= n) &&
1869                     ((strat->lenSw == NULL) || (strat->lenSw[j] <= n)))))
1870    {
1871      nNormalize (pGetCoeff (P.p));
1872#ifdef KDEBUG
1873      if(TEST_OPT_DEBUG)
1874      {
1875        PrintS ("red:");
1876        wrp (h);
1877        PrintS (" with ");
1878        wrp (strat->S[j]);
1879      }
1880#endif
1881
1882      number coef = kBucketPolyRed (P.bucket, strat->S[j],
1883                                    strat->lenS[j] /*pLength(strat->S[j]) */ ,
1884                                    strat->kNoether);
1885      number m2 = nMult (m, coef);
1886      nDelete (&m);
1887      m = m2;
1888      nDelete (&coef);
1889      h = kBucketGetLm (P.bucket);
1890
1891      if(h == NULL)
1892      {
1893        len = 0;
1894        kBucketDestroy (&P.bucket);
1895        return NULL;
1896      }
1897      P.p = h;
1898      P.t_p = NULL;
1899      P.SetShortExpVector ();
1900#ifdef KDEBUG
1901      if(TEST_OPT_DEBUG)
1902      {
1903        PrintS ("\nto:");
1904        wrp (h);
1905        PrintLn ();
1906      }
1907#endif
1908    }
1909    else
1910    {
1911      kBucketClear (P.bucket, &(P.p), &len);
1912      kBucketDestroy (&P.bucket);
1913      pNormalize (P.p);
1914      assume (len == (pLength (P.p)));
1915      return P.p;
1916    }
1917  }
1918}
1919
1920static poly redTailShort (poly h, kStrategy strat)
1921{
1922  if(h == NULL)
1923    return NULL;                //n_Init(1,currRing);
1924  if(TEST_V_MODPSOLVSB)
1925  {
1926    bit_reduce (pNext (h), strat->tailRing);
1927  }
1928  int i;
1929  int len = pLength (h);
1930  for(i = 0; i <= strat->sl; i++)
1931  {
1932    if((strat->lenS[i] > 2)
1933       || ((strat->lenSw != NULL) && (strat->lenSw[i] > 2)))
1934      break;
1935  }
1936  return (redNFTail (h, i - 1, strat, len));
1937}
1938
1939static void line_of_extended_prod (int fixpos, slimgb_alg * c)
1940{
1941  if(c->gcd_of_terms[fixpos] == NULL)
1942  {
1943    c->gcd_of_terms[fixpos] = gcd_of_terms (c->S->m[fixpos], c->r);
1944    if(c->gcd_of_terms[fixpos])
1945    {
1946      int i;
1947      for(i = 0; i < fixpos; i++)
1948        if((c->states[fixpos][i] != HASTREP)
1949           &&
1950           (extended_product_criterion
1951            (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i],
1952             c->gcd_of_terms[i], c)))
1953        {
1954          c->states[fixpos][i] = HASTREP;
1955          c->extended_product_crit++;
1956        }
1957      for(i = fixpos + 1; i < c->n; i++)
1958        if((c->states[i][fixpos] != HASTREP)
1959           &&
1960           (extended_product_criterion
1961            (c->S->m[fixpos], c->gcd_of_terms[fixpos], c->S->m[i],
1962             c->gcd_of_terms[i], c)))
1963        {
1964          c->states[i][fixpos] = HASTREP;
1965          c->extended_product_crit++;
1966        }
1967    }
1968  }
1969}
1970
1971static void c_S_element_changed_hook (int pos, slimgb_alg * c)
1972{
1973  length_one_crit (c, pos, c->lengths[pos]);
1974  if(!c->nc)
1975    line_of_extended_prod (pos, c);
1976}
1977
1978class poly_tree_node
1979{
1980public:
1981  poly p;
1982  poly_tree_node *l;
1983  poly_tree_node *r;
1984  int n;
1985  poly_tree_node (int sn):l (NULL), r (NULL), n (sn)
1986  {
1987  }
1988};
1989class exp_number_builder
1990{
1991public:
1992  poly_tree_node * top_level;
1993  int n;
1994  int get_n (poly p);
1995  exp_number_builder ():top_level (0), n (0)
1996  {
1997  }
1998};
1999int exp_number_builder::get_n (poly p)
2000{
2001  poly_tree_node **node = &top_level;
2002  while(*node != NULL)
2003  {
2004    int c = pLmCmp (p, (*node)->p);
2005    if(c == 0)
2006      return (*node)->n;
2007    if(c == -1)
2008      node = &((*node)->r);
2009    else
2010      node = &((*node)->l);
2011  }
2012  (*node) = new poly_tree_node (n);
2013  n++;
2014  (*node)->p = pLmInit (p);
2015  return (*node)->n;
2016}
2017
2018//mac_polys exp are smaller iff they are greater by monomial ordering
2019//corresponding to solving linear equations notation
2020
2021//! obsolete
2022struct int_poly_pair
2023{
2024  poly p;
2025  int n;
2026};
2027
2028
2029//! obsolete
2030void t2ippa_rec (poly * ip, int *ia, poly_tree_node * k, int &offset)
2031{
2032  if(!k)
2033    return;
2034  t2ippa_rec (ip, ia, k->l, offset);
2035  ip[offset] = k->p;
2036  ia[k->n] = offset;
2037  ++offset;
2038
2039  t2ippa_rec (ip, ia, k->r, offset);
2040  delete k;
2041}
2042
2043//! obsolete
2044void t2ippa (poly * ip, int *ia, exp_number_builder & e)
2045{
2046
2047  int o = 0;
2048  t2ippa_rec (ip, ia, e.top_level, o);
2049}
2050
2051int anti_poly_order (const void *a, const void *b)
2052{
2053  return -pLmCmp (((int_poly_pair *) a)->p, ((int_poly_pair *) b)->p);
2054}
2055
2056BOOLEAN is_valid_ro (red_object & ro)
2057{
2058  red_object r2 = ro;
2059  ro.validate ();
2060  if((r2.p != ro.p) || (r2.sev != ro.sev))
2061    return FALSE;
2062  return TRUE;
2063}
2064
2065int terms_sort_crit (const void *a, const void *b)
2066{
2067  return -pLmCmp (*((poly *) a), *((poly *) b));
2068}
2069
2070#if 0                           // currently unused
2071static void unify_terms (poly * terms, int &sum)
2072{
2073  if(sum == 0)
2074    return;
2075  int last = 0;
2076  int curr = 1;
2077  while(curr < sum)
2078  {
2079    if(!(pLmEqual (terms[curr], terms[last])))
2080    {
2081      terms[++last] = terms[curr];
2082    }
2083    ++curr;
2084  }
2085  sum = last + 1;
2086}
2087#endif
2088#if 0                           // currently unused
2089static void
2090export_mat (number * number_array, int pn, int tn, const char *format_str,
2091            int mat_nr)
2092{
2093  char matname[20];
2094  sprintf (matname, format_str, mat_nr);
2095  FILE *out = fopen (matname, "w");
2096  int i, j;
2097  fprintf (out, "mat=[\n");
2098  for(i = 0; i < pn; i++)
2099  {
2100    fprintf (out, "[\n");
2101    for(j = 0; j < tn; j++)
2102    {
2103      if(j > 0)
2104      {
2105        fprintf (out, ", ");
2106      }
2107      fprintf (out, "%i", npInt (number_array[i * tn + j], currRing));
2108    }
2109    if(i < pn - 1)
2110      fprintf (out, "],\n");
2111    else
2112      fprintf (out, "],\n");
2113  }
2114  fprintf (out, "]\n");
2115  fclose (out);
2116}
2117#endif
2118//typedef unsigned short number_type;
2119
2120
2121#ifdef USE_NORO
2122#ifndef NORO_CACHE
2123static void
2124linalg_step_modp (poly * p, poly * p_out, int &pn, poly * terms, int tn,
2125                  slimgb_alg * c)
2126{
2127  static int export_n = 0;
2128  assume (terms[tn - 1] != NULL);
2129  assume (rField_is_Zp (c->r));
2130  //I don't do deletes, copies of number_types ...
2131  const number_type zero = 0;   //npInit(0);
2132  int array_size = pn * tn;
2133  number_type *number_array =
2134    (number_type *) omalloc (pn * tn * sizeof (number_type));
2135  int i;
2136  for(i = 0; i < array_size; i++)
2137  {
2138    number_array[i] = zero;
2139  }
2140  for(i = 0; i < pn; i++)
2141  {
2142    poly h = p[i];
2143    //int base=tn*i;
2144    write_poly_to_row (number_array + tn * i, h, terms, tn, c->r);
2145
2146  }
2147#if 0
2148  //export matrix
2149  export_mat (number_array, pn, tn, "mat%i.py", ++export_n);
2150#endif
2151  int rank = pn;
2152  simplest_gauss_modp (number_array, rank, tn);
2153  int act_row = 0;
2154  int p_pos = 0;
2155  for(i = 0; i < pn; i++)
2156  {
2157    poly h = NULL;
2158    int j;
2159    int base = tn * i;
2160    number *row = number_array + base;
2161    h = row_to_poly (row, terms, tn, c->r);
2162
2163    if(h != NULL)
2164    {
2165      p_out[p_pos++] = h;
2166    }
2167  }
2168  pn = p_pos;
2169  //assert(p_pos==rank)
2170  while(p_pos < pn)
2171  {
2172    p_out[p_pos++] = NULL;
2173  }
2174#if 0
2175  export_mat (number_array, pn, tn, "mat%i.py", ++export_n);
2176#endif
2177}
2178#endif
2179#endif
2180static void mass_add (poly * p, int pn, slimgb_alg * c)
2181{
2182  int j;
2183  int *ibuf = (int *) omalloc (pn * sizeof (int));
2184  sorted_pair_node ***sbuf =
2185    (sorted_pair_node ***) omalloc (pn * sizeof (sorted_pair_node **));
2186  for(j = 0; j < pn; j++)
2187  {
2188    p_Test (p[j], c->r);
2189    sbuf[j] = add_to_basis_ideal_quotient (p[j], c, ibuf + j);
2190  }
2191  int sum = 0;
2192  for(j = 0; j < pn; j++)
2193  {
2194    sum += ibuf[j];
2195  }
2196  sorted_pair_node **big_sbuf =
2197    (sorted_pair_node **) omalloc (sum * sizeof (sorted_pair_node *));
2198  int partsum = 0;
2199  for(j = 0; j < pn; j++)
2200  {
2201    memmove (big_sbuf + partsum, sbuf[j],
2202             ibuf[j] * sizeof (sorted_pair_node *));
2203    omFree (sbuf[j]);
2204    partsum += ibuf[j];
2205  }
2206
2207  qsort (big_sbuf, sum, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
2208  c->apairs = spn_merge (c->apairs, c->pair_top + 1, big_sbuf, sum, c);
2209  c->pair_top += sum;
2210  clean_top_of_pair_list (c);
2211  omfree (big_sbuf);
2212  omfree (sbuf);
2213  omfree (ibuf);
2214  //omfree(buf);
2215#ifdef TGB_DEBUG
2216  int z;
2217  for(z = 1; z <= c->pair_top; z++)
2218  {
2219    assume (pair_better (c->apairs[z], c->apairs[z - 1], c));
2220  }
2221#endif
2222
2223}
2224
2225#ifdef NORO_CACHE
2226#ifndef NORO_NON_POLY
2227void NoroCache::evaluateRows ()
2228{
2229  //after that can evaluate placeholders
2230  int i;
2231  buffer = (number *) omAlloc (nIrreducibleMonomials * sizeof (number));
2232  for(i = 0; i < root.branches_len; i++)
2233  {
2234    evaluateRows (1, root.branches[i]);
2235  }
2236  omFree (buffer);
2237  buffer = NULL;
2238}
2239
2240void NoroCache::evaluateRows (int level, NoroCacheNode * node)
2241{
2242  assume (level >= 0);
2243  if(node == NULL)
2244    return;
2245  if(level < (currRing->N))
2246  {
2247    int i, sum;
2248    for(i = 0; i < node->branches_len; i++)
2249    {
2250      evaluateRows (level + 1, node->branches[i]);
2251    }
2252  }
2253  else
2254  {
2255    DataNoroCacheNode *dn = (DataNoroCacheNode *) node;
2256    if(dn->value_len != backLinkCode)
2257    {
2258      poly p = dn->value_poly;
2259#ifndef NORO_SPARSE_ROWS_PRE
2260      dn->row = new DenseRow ();
2261      DenseRow *row = dn->row;
2262      memset (buffer, 0, sizeof (number) * nIrreducibleMonomials);
2263
2264      if(p == NULL)
2265      {
2266        row->array = NULL;
2267        row->begin = 0;
2268        row->end = 0;
2269        return;
2270      }
2271      int i = 0;
2272      int idx;
2273      number *a = buffer;
2274      while(p)
2275      {
2276        DataNoroCacheNode *ref = getCacheReference (p);
2277
2278        idx = ref->term_index;
2279        assume (idx >= 0);
2280        a[idx] = p_GetCoeff (p, currRing);
2281        if(i == 0)
2282          row->begin = idx;
2283        i++;
2284        pIter (p);
2285      }
2286      row->end = idx + 1;
2287      assume (row->end > row->begin);
2288      int len = row->end - row->begin;
2289      row->array = (number *) omalloc ((len) * sizeof (number));
2290      memcpy (row->array, a + row->begin, len * sizeof (number));
2291#else
2292      assume (dn->value_len == pLength (dn->value_poly));
2293      dn->row = new SparseRow (dn->value_len);
2294      SparseRow *row = dn->row;
2295      int i = 0;
2296      while(p)
2297      {
2298        DataNoroCacheNode *ref = getCacheReference (p);
2299
2300        int idx = ref->term_index;
2301        assume (idx >= 0);
2302        row->idx_array[i] = idx;
2303        row->coef_array[i] = p_GetCoeff (p, currRing);
2304        i++;
2305        pIter (p);
2306      }
2307      if(i != dn->value_len)
2308      {
2309        PrintS ("F4 calc wrong, as poly len was wrong\n");
2310      }
2311      assume (i == dn->value_len);
2312#endif
2313    }
2314  }
2315}
2316
2317void
2318  NoroCache::evaluatePlaceHolder (number * row,
2319                                  std::vector < NoroPlaceHolder >
2320                                  &place_holders)
2321{
2322  int i;
2323  int s = place_holders.size ();
2324  for(i = 0; i < s; i++)
2325  {
2326    DataNoroCacheNode *ref = place_holders[i].ref;
2327    number coef = place_holders[i].coef;
2328    if(ref->value_len == backLinkCode)
2329    {
2330      row[ref->term_index] = npAddM (row[ref->term_index], coef);
2331    }
2332    else
2333    {
2334#ifndef NORO_SPARSE_ROWS_PRE
2335      DenseRow *ref_row = ref->row;
2336      if(ref_row == NULL)
2337        continue;
2338      number *ref_begin = ref_row->array;
2339      number *ref_end = ref_row->array + (ref_row->end - ref_row->begin);
2340      number *my_pos = row + ref_row->begin;
2341      //TODO npisOne distinction
2342      if(!(npIsOne (coef)))
2343      {
2344        while(ref_begin != ref_end)
2345        {
2346
2347          *my_pos = npAddM (*my_pos, npMult (coef, *ref_begin));
2348          ++ref_begin;
2349          ++my_pos;
2350        }
2351      }
2352      else
2353      {
2354        while(ref_begin != ref_end)
2355        {
2356
2357          *my_pos = npAddM (*my_pos, *ref_begin);
2358          ++ref_begin;
2359          ++my_pos;
2360        }
2361      }
2362
2363#else
2364      SparseRow *ref_row = ref->row;
2365      if(ref_row == NULL)
2366        continue;
2367      int n = ref_row->len;
2368      int j;
2369      int *idx_array = ref_row->idx_array;
2370      number *coef_array = ref_row->coef_array;
2371      for(j = 0; j < n; j++)
2372      {
2373        int idx = idx_array[j];
2374        number ref_coef = coef_array[j];
2375        row[idx] = npAddM (row[idx], npMult (coef, ref_coef));
2376      }
2377#endif
2378    }
2379  }
2380}
2381#endif
2382
2383//poly noro_red_non_unique(poly p, int &len, NoroCache* cache,slimgb_alg* c);
2384
2385#ifndef NORO_NON_POLY
2386MonRedRes
2387noro_red_mon (poly t, BOOLEAN force_unique, NoroCache * cache, slimgb_alg * c)
2388{
2389  MonRedRes res_holder;
2390
2391  //wrp(t);
2392  res_holder.changed = TRUE;
2393  if(force_unique)
2394  {
2395    DataNoroCacheNode *ref = cache->getCacheReference (t);
2396    if(ref != NULL)
2397    {
2398      res_holder.len = ref->value_len;
2399      if(res_holder.len == NoroCache::backLinkCode)
2400      {
2401        res_holder.len = 1;
2402      }
2403      res_holder.coef = p_GetCoeff (t, c->r);
2404      res_holder.p = ref->value_poly;
2405      res_holder.ref = ref;
2406      res_holder.onlyBorrowed = TRUE;
2407      res_holder.changed = TRUE;
2408      p_Delete (&t, c->r);
2409      return res_holder;
2410    }
2411  }
2412  else
2413  {
2414    BOOLEAN succ;
2415    poly cache_lookup = cache->lookup (t, succ, res_holder.len);        //don't own this yet
2416    if(succ)
2417    {
2418      if(cache_lookup == t)
2419      {
2420        //know they are equal
2421        //res_holder.len=1;
2422
2423        res_holder.changed = FALSE;
2424        res_holder.p = t;
2425        res_holder.coef = npInit (1);
2426
2427        res_holder.onlyBorrowed = FALSE;
2428        return res_holder;
2429      }
2430
2431      res_holder.coef = p_GetCoeff (t, c->r);
2432      p_Delete (&t, c->r);
2433
2434      res_holder.p = cache_lookup;
2435
2436      res_holder.onlyBorrowed = TRUE;
2437      return res_holder;
2438
2439    }
2440  }
2441
2442  unsigned long sev = p_GetShortExpVector (t, currRing);
2443  int i = kFindDivisibleByInS_easy (c->strat, t, sev);
2444  if(i >= 0)
2445  {
2446    number coef_bak = p_GetCoeff (t, c->r);
2447
2448    p_SetCoeff (t, npInit (1), c->r);
2449    assume (npIsOne (p_GetCoeff (c->strat->S[i], c->r)));
2450    number coefstrat = p_GetCoeff (c->strat->S[i], c->r);
2451
2452    //poly t_copy_mon=p_Copy(t,c->r);
2453    poly exp_diff = cache->temp_term;
2454    p_ExpVectorDiff (exp_diff, t, c->strat->S[i], c->r);
2455    p_SetCoeff (exp_diff, npNeg (nInvers (coefstrat)), c->r);
2456    // nInvers may be npInvers or nvInvers
2457    p_Setm (exp_diff, c->r);
2458    assume (c->strat->S[i] != NULL);
2459    //poly t_to_del=t;
2460    poly res;
2461    res = pp_Mult_mm (pNext (c->strat->S[i]), exp_diff, c->r);
2462
2463    res_holder.len = c->strat->lenS[i] - 1;
2464    res = noro_red_non_unique (res, res_holder.len, cache, c);
2465
2466    DataNoroCacheNode *ref = cache->insert (t, res, res_holder.len);
2467    p_Delete (&t, c->r);
2468    //p_Delete(&t_copy_mon,c->r);
2469    //res=pMult_nn(res,coef_bak);
2470    res_holder.changed = TRUE;
2471    res_holder.p = res;
2472    res_holder.coef = coef_bak;
2473    res_holder.onlyBorrowed = TRUE;
2474    res_holder.ref = ref;
2475    return res_holder;
2476  }
2477  else
2478  {
2479    number coef_bak = p_GetCoeff (t, c->r);
2480    number one = npInit (1);
2481    p_SetCoeff (t, one, c->r);
2482    res_holder.len = 1;
2483    if(!(force_unique))
2484    {
2485      res_holder.ref = cache->insert (t, t, res_holder.len);
2486      p_SetCoeff (t, coef_bak, c->r);
2487      //return t;
2488
2489      //we need distinction
2490      res_holder.changed = FALSE;
2491      res_holder.p = t;
2492
2493      res_holder.coef = npInit (1);
2494      res_holder.onlyBorrowed = FALSE;
2495      return res_holder;
2496    }
2497    else
2498    {
2499      res_holder.ref = cache->insertAndTransferOwnerShip (t, c->r);
2500      res_holder.coef = coef_bak;
2501      res_holder.onlyBorrowed = TRUE;
2502      res_holder.changed = FALSE;
2503      res_holder.p = t;
2504      return res_holder;
2505    }
2506  }
2507
2508}
2509#endif
2510//SparseRow* noro_red_to_non_poly(poly p, int &len, NoroCache* cache,slimgb_alg* c);
2511#ifndef NORO_NON_POLY
2512//len input and out: Idea: reverse addition
2513poly noro_red_non_unique (poly p, int &len, NoroCache * cache, slimgb_alg * c)
2514{
2515  assume (len == pLength (p));
2516  poly orig_p = p;
2517  if(p == NULL)
2518  {
2519    len = 0;
2520    return NULL;
2521  }
2522  kBucket_pt bucket = kBucketCreate (currRing);
2523  kBucketInit (bucket, NULL, 0);
2524  poly unchanged_head = NULL;
2525  poly unchanged_tail = NULL;
2526  int unchanged_size = 0;
2527
2528  while(p)
2529  {
2530    poly t = p;
2531    pIter (p);
2532    pNext (t) = NULL;
2533#ifndef SING_NDEBUG
2534    number coef_debug = p_GetCoeff (t, currRing);
2535#endif
2536    MonRedRes red = noro_red_mon (t, FALSE, cache, c);
2537    if((!(red.changed)) && (!(red.onlyBorrowed)))
2538    {
2539      unchanged_size++;
2540      assume (npIsOne (red.coef));
2541      assume (p_GetCoeff (red.p, currRing) == coef_debug);
2542      if(unchanged_head)
2543      {
2544        pNext (unchanged_tail) = red.p;
2545        pIter (unchanged_tail);
2546      }
2547      else
2548      {
2549        unchanged_tail = red.p;
2550        unchanged_head = red.p;
2551      }
2552    }
2553    else
2554    {
2555      assume (red.len == pLength (red.p));
2556      if(red.onlyBorrowed)
2557      {
2558        if(npIsOne (red.coef))
2559        {
2560          t = p_Copy (red.p, currRing);
2561        }
2562        else
2563          t = pp_Mult_nn (red.p, red.coef, currRing);
2564      }
2565      else
2566      {
2567        if(npIsOne (red.coef))
2568          t = red.p;
2569        else
2570          t = p_Mult_nn (red.p, red.coef, currRing);
2571      }
2572      kBucket_Add_q (bucket, t, &red.len);
2573    }
2574  }
2575  poly res = NULL;
2576  len = 0;
2577  kBucket_Add_q (bucket, unchanged_head, &unchanged_size);
2578  kBucketClear (bucket, &res, &len);
2579  kBucketDestroy (&bucket);
2580  return res;
2581}
2582#endif
2583#ifdef NORO_SPARSE_ROWS_PRE
2584//len input and out: Idea: reverse addition
2585
2586/*template <class number_type> SparseRow<number_type>* noro_red_to_non_poly(poly p, int &len, NoroCache<number_type>* cache,slimgb_alg* c)
2587 * {
2588  if (n_GetChar(currRing->cf)<255)
2589  {
2590    return noro_red_to_non_poly_t<tgb_uint8>(p,len,cache,c);
2591  }
2592  else
2593  {
2594    if (n_GetChar(currRing->cf)<65000)
2595    {
2596      return noro_red_to_non_poly_t<tgb_uint16>(p,len,cache,c);
2597    }
2598    else
2599    {
2600      return noro_red_to_non_poly_t<tgb_uint32>(p,len,cache,c);
2601    }
2602  }
2603}*/
2604#endif
2605//len input and out: Idea: reverse addition
2606#ifndef NORO_NON_POLY
2607std::vector < NoroPlaceHolder > noro_red (poly p, int &len, NoroCache * cache,
2608                                          slimgb_alg * c)
2609{
2610  std::vector < NoroPlaceHolder > res;
2611  while(p)
2612  {
2613    poly t = p;
2614    pIter (p);
2615    pNext (t) = NULL;
2616
2617    MonRedRes red = noro_red_mon (t, TRUE, cache, c);
2618    assume (red.onlyBorrowed);
2619    assume (red.coef);
2620    assume (red.ref);
2621    NoroPlaceHolder h;
2622    h.ref = red.ref;
2623    h.coef = red.coef;
2624    assume (!((h.ref->value_poly == NULL) && (h.ref->value_len != 0)));
2625    if(h.ref->value_poly)
2626      res.push_back (h);
2627  }
2628  return res;
2629}
2630#endif
2631
2632#endif
2633#ifdef USE_NORO
2634#ifndef NORO_CACHE
2635void noro_step (poly * p, int &pn, slimgb_alg * c)
2636{
2637  poly *reduced = (poly *) omalloc (pn * sizeof (poly));
2638  int j;
2639  int *reduced_len = (int *) omalloc (pn * sizeof (int));
2640  int reduced_c = 0;
2641  //if (TEST_OPT_PROT)
2642  //  PrintS("reduced system:\n");
2643#ifdef NORO_CACHE
2644  NoroCache cache;
2645#endif
2646  for(j = 0; j < pn; j++)
2647  {
2648
2649    poly h = p[j];
2650    int h_len = pLength (h);
2651
2652    number coef;
2653#ifndef NORO_CACHE
2654    h = redNF2 (p_Copy (h, c->r), c, h_len, coef, 0);
2655#else
2656    h = noro_red (p_Copy (h, c->r), h_len, &cache, c);
2657    assume (pLength (h) == h_len);
2658#endif
2659    if(h != NULL)
2660    {
2661#ifndef NORO_CACHE
2662
2663      h = redNFTail (h, c->strat->sl, c->strat, h_len);
2664      h_len = pLength (h);
2665#endif
2666      reduced[reduced_c] = h;
2667      reduced_len[reduced_c] = h_len;
2668      reduced_c++;
2669      if(TEST_OPT_PROT)
2670        Print ("%d ", h_len);
2671    }
2672  }
2673  int reduced_sum = 0;
2674  for(j = 0; j < reduced_c; j++)
2675  {
2676    reduced_sum += reduced_len[j];
2677  }
2678  poly *terms = (poly *) omalloc (reduced_sum * sizeof (poly));
2679  int tc = 0;
2680  for(j = 0; j < reduced_c; j++)
2681  {
2682    poly h = reduced[j];
2683
2684    while(h != NULL)
2685    {
2686      terms[tc++] = h;
2687      pIter (h);
2688      assume (tc <= reduced_sum);
2689    }
2690  }
2691  assume (tc == reduced_sum);
2692  qsort (terms, reduced_sum, sizeof (poly), terms_sort_crit);
2693  int nterms = reduced_sum;
2694  //if (TEST_OPT_PROT)
2695  //Print("orig estimation:%i\n",reduced_sum);
2696  unify_terms (terms, nterms);
2697  //if (TEST_OPT_PROT)
2698  //    Print("actual number of columns:%i\n",nterms);
2699  int rank = reduced_c;
2700  linalg_step_modp (reduced, p, rank, terms, nterms, c);
2701  omfree (terms);
2702
2703  pn = rank;
2704  omfree (reduced);
2705
2706  if(TEST_OPT_PROT)
2707    PrintS ("\n");
2708}
2709#else
2710
2711#endif
2712#endif
2713static void go_on (slimgb_alg * c)
2714{
2715  //set limit of 1000 for multireductions, at the moment for
2716  //programming reasons
2717#ifdef USE_NORO
2718  //Print("module rank%d\n",c->S->rank);
2719  const BOOLEAN use_noro = c->use_noro;
2720#else
2721  const BOOLEAN use_noro = FALSE;
2722#endif
2723  int i = 0;
2724  c->average_length = 0;
2725  for(i = 0; i < c->n; i++)
2726  {
2727    c->average_length += c->lengths[i];
2728  }
2729  c->average_length = c->average_length / c->n;
2730  i = 0;
2731  int max_pairs = bundle_size;
2732
2733#ifdef USE_NORO
2734  if((use_noro) || (c->use_noro_last_block))
2735    max_pairs = bundle_size_noro;
2736#endif
2737  poly *p = (poly *) omalloc ((max_pairs + 1) * sizeof (poly)); //nullterminated
2738
2739  int curr_deg = -1;
2740  while(i < max_pairs)
2741  {
2742    sorted_pair_node *s = top_pair (c); //here is actually chain criterium done
2743
2744    if(!s)
2745      break;
2746
2747    if(curr_deg >= 0)
2748    {
2749      if(s->deg > curr_deg)
2750        break;
2751    }
2752
2753    else
2754      curr_deg = s->deg;
2755    quick_pop_pair (c);
2756    if(s->i >= 0)
2757    {
2758      //be careful replace_pair use createShortSpoly which is not noncommutative
2759      now_t_rep (s->i, s->j, c);
2760      replace_pair (s->i, s->j, c);
2761
2762      if(s->i == s->j)
2763      {
2764        free_sorted_pair_node (s, c->r);
2765        continue;
2766      }
2767      now_t_rep (s->i, s->j, c);
2768    }
2769    poly h;
2770    if(s->i >= 0)
2771    {
2772#ifdef HAVE_PLURAL
2773      if(c->nc)
2774      {
2775        h = nc_CreateSpoly (c->S->m[s->i], c->S->m[s->j] /*, NULL */ , c->r);
2776
2777        if(h != NULL)
2778          p_Cleardenom (h, c->r);
2779      }
2780      else
2781#endif
2782        h = ksOldCreateSpoly (c->S->m[s->i], c->S->m[s->j], NULL, c->r);
2783      p_Test (h, c->r);
2784    }
2785    else
2786    {
2787      h = s->lcm_of_lm;
2788      p_Test (h, c->r);
2789    }
2790    // if(s->i>=0)
2791//       now_t_rep(s->j,s->i,c);
2792    number coef;
2793    int mlen = pLength (h);
2794    p_Test (h, c->r);
2795    if((!c->nc) & (!(use_noro)))
2796    {
2797      h = redNF2 (h, c, mlen, coef, 2);
2798      redTailShort (h, c->strat);
2799      nDelete (&coef);
2800    }
2801    p_Test (h, c->r);
2802    free_sorted_pair_node (s, c->r);
2803    if(!h)
2804      continue;
2805    p[i] = h;
2806    i++;
2807  }
2808  p[i] = NULL;
2809//  pre_comp(p,i,c);
2810  if(i == 0)
2811  {
2812    omfree (p);
2813    return;
2814  }
2815#ifdef TGB_RESORT_PAIRS
2816  c->replaced = new bool[c->n];
2817  c->used_b = FALSE;
2818#endif
2819
2820  c->normal_forms += i;
2821  int j;
2822#ifdef USE_NORO
2823  //if ((!(c->nc))&&(rField_is_Zp(c->r)))
2824  //{
2825  if(use_noro)
2826  {
2827    int pn = i;
2828    if(pn == 0)
2829    {
2830      omfree (p);
2831      return;
2832    }
2833    {
2834      if(n_GetChar(currRing->cf) < 255)
2835      {
2836        noro_step < tgb_uint8 > (p, pn, c);
2837      }
2838      else
2839      {
2840        if(n_GetChar(currRing->cf) < 65000)
2841        {
2842          noro_step < tgb_uint16 > (p, pn, c);
2843        }
2844        else
2845        {
2846          noro_step < tgb_uint32 > (p, pn, c);
2847        }
2848      }
2849    }
2850
2851    //if (TEST_OPT_PROT)
2852    //{
2853    //  Print("reported rank:%i\n",pn);
2854    //}
2855    mass_add (p, pn, c);
2856    omfree (p);
2857    return;
2858    /*if (TEST_OPT_PROT)
2859       for(j=0;j<pn;j++)
2860       {
2861       p_wrp(p[j],c->r);
2862       } */
2863  }
2864#endif
2865  red_object *buf = (red_object *) omalloc (i * sizeof (red_object));
2866  for(j = 0; j < i; j++)
2867  {
2868    p_Test (p[j], c->r);
2869    buf[j].p = p[j];
2870    buf[j].sev = pGetShortExpVector (p[j]);
2871    buf[j].bucket = kBucketCreate (currRing);
2872    p_Test (p[j], c->r);
2873    int len = pLength (p[j]);
2874    kBucketInit (buf[j].bucket, buf[j].p, len);
2875    buf[j].initial_quality = buf[j].guess_quality (c);
2876    assume (buf[j].initial_quality >= 0);
2877  }
2878  omfree (p);
2879  qsort (buf, i, sizeof (red_object), red_object_better_gen);
2880//    Print("\ncurr_deg:%i\n",curr_deg);
2881  if(TEST_OPT_PROT)
2882  {
2883    Print ("%dM[%d,", curr_deg, i);
2884  }
2885
2886  multi_reduction (buf, i, c);
2887#ifdef TGB_RESORT_PAIRS
2888  if(c->used_b)
2889  {
2890    if(TEST_OPT_PROT)
2891      PrintS ("B");
2892    int e;
2893    for(e = 0; e <= c->pair_top; e++)
2894    {
2895      if(c->apairs[e]->i < 0)
2896        continue;
2897      assume (c->apairs[e]->j >= 0);
2898      if((c->replaced[c->apairs[e]->i]) || (c->replaced[c->apairs[e]->j]))
2899      {
2900        sorted_pair_node *s = c->apairs[e];
2901        s->expected_length = pair_weighted_length (s->i, s->j, c);
2902      }
2903    }
2904    qsort (c->apairs, c->pair_top + 1, sizeof (sorted_pair_node *),
2905           tgb_pair_better_gen2);
2906  }
2907#endif
2908#ifdef TGB_DEBUG
2909  {
2910    int k;
2911    for(k = 0; k < i; k++)
2912    {
2913      assume (kFindDivisibleByInS_easy (c->strat, buf[k]) < 0);
2914      int k2;
2915      for(k2 = 0; k2 < i; k2++)
2916      {
2917        if(k == k2)
2918          continue;
2919        assume ((!(p_LmDivisibleBy (buf[k].p, buf[k2].p, c->r)))
2920                || (wrp (buf[k].p), Print (" k %d k2 %d ", k, k2),
2921                    wrp (buf[k2].p), FALSE));
2922      }
2923    }
2924  }
2925#endif
2926  //resort S
2927
2928  if(TEST_OPT_PROT)
2929    Print ("%i]", i);
2930
2931  poly *add_those = (poly *) omalloc (i * sizeof (poly));
2932  for(j = 0; j < i; j++)
2933  {
2934    int len;
2935    poly p;
2936    buf[j].flatten ();
2937    kBucketClear (buf[j].bucket, &p, &len);
2938    kBucketDestroy (&buf[j].bucket);
2939    p_Test (p, c->r);
2940    //if (!c->nc) {
2941    if((c->tailReductions) || (lies_in_last_dp_block (p, c)))
2942    {
2943      p = redNFTail (p, c->strat->sl, c->strat, 0);
2944    }
2945    else
2946    {
2947      p = redTailShort (p, c->strat);
2948    }
2949    //}
2950    p_Test (p, c->r);
2951    add_those[j] = p;
2952
2953    //sbuf[j]=add_to_basis(p,-1,-1,c,ibuf+j);
2954  }
2955  mass_add (add_those, i, c);
2956  omfree (add_those);
2957  omfree (buf);
2958
2959  if(TEST_OPT_PROT)
2960    Print ("(%d)", c->pair_top + 1);
2961  //TODO: implement that while(!(idIs0(c->add_later)))
2962#ifdef TGB_RESORT_PAIRS
2963  delete c->replaced;
2964  c->replaced = NULL;
2965  c->used_b = FALSE;
2966#endif
2967  return;
2968}
2969
2970#ifdef REDTAIL_S
2971
2972static poly redNFTail (poly h, const int sl, kStrategy strat, int len)
2973{
2974  BOOLEAN nc = rIsPluralRing (currRing);
2975  if(h == NULL)
2976    return NULL;
2977  pTest (h);
2978  if(0 > sl)
2979    return h;
2980  if(pNext (h) == NULL)
2981    return h;
2982
2983  int j;
2984  poly res = h;
2985  poly act = res;
2986  LObject P (pNext (h));
2987  pNext (res) = NULL;
2988  P.bucket = kBucketCreate (currRing);
2989  len--;
2990  h = P.p;
2991  if(len <= 0)
2992    len = pLength (h);
2993  kBucketInit (P.bucket, h /*P.p */ , len /*pLength(P.p) */ );
2994  pTest (h);
2995  loop
2996  {
2997    P.p = h;
2998    P.t_p = NULL;
2999    P.SetShortExpVector ();
3000    loop
3001    {
3002      //int dummy=strat->sl;
3003      j = kFindDivisibleByInS_easy (strat, P.p, P.sev); //kFindDivisibleByInS(strat,&dummy,&P);
3004      if(j >= 0)
3005      {
3006#ifdef REDTAIL_PROT
3007        PrintS ("r");
3008#endif
3009        nNormalize (pGetCoeff (P.p));
3010#ifdef KDEBUG
3011        if(TEST_OPT_DEBUG)
3012        {
3013          PrintS ("red tail:");
3014          wrp (h);
3015          PrintS (" with ");
3016          wrp (strat->S[j]);
3017        }
3018#endif
3019        number coef;
3020        pTest (strat->S[j]);
3021#ifdef HAVE_PLURAL
3022        if(nc)
3023        {
3024          nc_BucketPolyRed_Z (P.bucket, strat->S[j], &coef);
3025        }
3026        else
3027#endif
3028          coef = kBucketPolyRed (P.bucket, strat->S[j],
3029                                 strat->lenS[j] /*pLength(strat->S[j]) */ ,
3030                                 strat->kNoether);
3031        pMult_nn (res, coef);
3032        nDelete (&coef);
3033        h = kBucketGetLm (P.bucket);
3034        pTest (h);
3035        if(h == NULL)
3036        {
3037#ifdef REDTAIL_PROT
3038          PrintS (" ");
3039#endif
3040          kBucketDestroy (&P.bucket);
3041          return res;
3042        }
3043        pTest (h);
3044        P.p = h;
3045        P.t_p = NULL;
3046        P.SetShortExpVector ();
3047#ifdef KDEBUG
3048        if(TEST_OPT_DEBUG)
3049        {
3050          PrintS ("\nto tail:");
3051          wrp (h);
3052          PrintLn ();
3053        }
3054#endif
3055      }
3056      else
3057      {
3058#ifdef REDTAIL_PROT
3059        PrintS ("n");
3060#endif
3061        break;
3062      }
3063    }                           /* end loop current mon */
3064    //   poly tmp=pHead(h /*kBucketGetLm(P.bucket)*/);
3065    //act->next=tmp;pIter(act);
3066    act->next = kBucketExtractLm (P.bucket);
3067    pIter (act);
3068    h = kBucketGetLm (P.bucket);
3069    if(h == NULL)
3070    {
3071#ifdef REDTAIL_PROT
3072      PrintS (" ");
3073#endif
3074      kBucketDestroy (&P.bucket);
3075      return res;
3076    }
3077    pTest (h);
3078  }
3079}
3080#endif
3081
3082
3083//try to fill, return FALSE iff queue is empty
3084
3085//transfers ownership of m to mat
3086void init_with_mac_poly (tgb_sparse_matrix * mat, int row, mac_poly m)
3087{
3088  assume (mat->mp[row] == NULL);
3089  mat->mp[row] = m;
3090#ifdef TGB_DEBUG
3091  mac_poly r = m;
3092  while(r)
3093  {
3094    assume (r->exp < mat->columns);
3095    r = r->next;
3096  }
3097#endif
3098}
3099
3100poly
3101free_row_to_poly (tgb_sparse_matrix * mat, int row, poly * monoms,
3102                  int monom_index)
3103{
3104  poly p = NULL;
3105  poly *set_this = &p;
3106  mac_poly r = mat->mp[row];
3107  mat->mp[row] = NULL;
3108  while(r)
3109  {
3110    (*set_this) = pLmInit (monoms[monom_index - 1 - r->exp]);
3111    pSetCoeff ((*set_this), r->coef);
3112    set_this = &((*set_this)->next);
3113    mac_poly old = r;
3114    r = r->next;
3115    delete old;
3116
3117  }
3118  return p;
3119}
3120
3121static int poly_crit (const void *ap1, const void *ap2)
3122{
3123  poly p1, p2;
3124  p1 = *((poly *) ap1);
3125  p2 = *((poly *) ap2);
3126
3127  int c = pLmCmp (p1, p2);
3128  if(c != 0)
3129    return c;
3130  int l1 = pLength (p1);
3131  int l2 = pLength (p2);
3132  if(l1 < l2)
3133    return -1;
3134  if(l1 > l2)
3135    return 1;
3136  return 0;
3137}
3138
3139void slimgb_alg::introduceDelayedPairs (poly * pa, int s)
3140{
3141  if(s == 0)
3142    return;
3143  sorted_pair_node **si_array =
3144    (sorted_pair_node **) omalloc (s * sizeof (sorted_pair_node *));
3145
3146  for(int i = 0; i < s; i++)
3147  {
3148    sorted_pair_node *si =
3149      (sorted_pair_node *) omalloc (sizeof (sorted_pair_node));
3150    si->i = -1;
3151    si->j = -2;
3152    poly p = pa[i];
3153    simplify_poly (p, r);
3154    si->expected_length = pQuality (p, this, pLength (p));
3155    p_Test (p, r);
3156    si->deg = this->pTotaldegree_full (p);
3157    /*if (!rField_is_Zp(r))
3158       {
3159       p_Content(p,r);
3160       p_Cleardenom(p,r);
3161       } */
3162
3163    si->lcm_of_lm = p;
3164
3165    //      c->apairs[n-1-i]=si;
3166    si_array[i] = si;
3167  }
3168
3169  qsort (si_array, s, sizeof (sorted_pair_node *), tgb_pair_better_gen2);
3170  apairs = spn_merge (apairs, pair_top + 1, si_array, s, this);
3171  pair_top += s;
3172  omfree (si_array);
3173}
3174
3175slimgb_alg::slimgb_alg (ideal I, int syz_comp, BOOLEAN F4, int deg_pos)
3176{
3177  this->deg_pos = deg_pos;
3178  lastCleanedDeg = -1;
3179  completed = FALSE;
3180  this->syz_comp = syz_comp;
3181  r = currRing;
3182  nc = rIsPluralRing (r);
3183  this->lastDpBlockStart = get_last_dp_block_start (r);
3184  //Print("last dp Block start: %i\n", this->lastDpBlockStart);
3185  is_homog = TRUE;
3186  {
3187    int hzz;
3188    for(hzz = 0; hzz < IDELEMS (I); hzz++)
3189    {
3190      assume (I->m[hzz] != NULL);
3191      int d = this->pTotaldegree (I->m[hzz]);
3192      poly t = I->m[hzz]->next;
3193      while(t)
3194      {
3195        if(d != this->pTotaldegree (t))
3196        {
3197          is_homog = FALSE;
3198          break;
3199        }
3200        t = t->next;
3201      }
3202      if(!(is_homog))
3203        break;
3204    }
3205  }
3206  eliminationProblem = ((!(is_homog)) && ((currRing->pLexOrder) || (I->rank > 1)));
3207  tailReductions = ((is_homog) || ((TEST_OPT_REDTAIL) && (!(I->rank > 1))));
3208  //  Print("is homog:%d",c->is_homog);
3209  void *h;
3210  int i;
3211  to_destroy = NULL;
3212  easy_product_crit = 0;
3213  extended_product_crit = 0;
3214  if(rField_is_Zp (r))
3215    isDifficultField = FALSE;
3216  else
3217    isDifficultField = TRUE;
3218  //not fully correct
3219  //(rChar()==0);
3220  F4_mode = F4;
3221
3222  reduction_steps = 0;
3223  last_index = -1;
3224
3225  F = NULL;
3226  F_minus = NULL;
3227
3228  Rcounter = 0;
3229
3230  soon_free = NULL;
3231
3232  tmp_lm = pOne ();
3233
3234  normal_forms = 0;
3235  current_degree = 1;
3236
3237  max_pairs = 5 * IDELEMS (I);
3238
3239  apairs =
3240    (sorted_pair_node **) omalloc (sizeof (sorted_pair_node *) * max_pairs);
3241  pair_top = -1;
3242
3243  int n = IDELEMS (I);
3244  array_lengths = n;
3245
3246
3247  i = 0;
3248  this->n = 0;
3249  T_deg = (int *) omalloc (n * sizeof (int));
3250  if(eliminationProblem)
3251    T_deg_full = (int *) omalloc (n * sizeof (int));
3252  else
3253    T_deg_full = NULL;
3254  tmp_pair_lm = (poly *) omalloc (n * sizeof (poly));
3255  tmp_spn = (sorted_pair_node **) omalloc (n * sizeof (sorted_pair_node *));
3256  lm_bin = omGetSpecBin (POLYSIZE + (r->ExpL_Size) * sizeof (long));
3257#ifdef HEAD_BIN
3258  HeadBin = omGetSpecBin (POLYSIZE + (currRing->ExpL_Size) * sizeof (long));
3259#endif
3260  /* omUnGetSpecBin(&(c->HeadBin)); */
3261#ifndef HAVE_BOOST
3262#ifdef USE_STDVECBOOL
3263#else
3264  h = omalloc (n * sizeof (char *));
3265
3266  states = (char **) h;
3267#endif
3268#endif
3269  h = omalloc (n * sizeof (int));
3270  lengths = (int *) h;
3271  weighted_lengths = (wlen_type *) omAllocAligned (n * sizeof (wlen_type));
3272  gcd_of_terms = (poly *) omAlloc (n * sizeof (poly));
3273
3274  short_Exps = (long *) omalloc (n * sizeof (long));
3275  if(F4_mode)
3276    S = idInit (n, I->rank);
3277  else
3278    S = idInit (1, I->rank);
3279  strat = new skStrategy;
3280  if(eliminationProblem)
3281    strat->honey = TRUE;
3282  strat->syzComp = 0;
3283  initBuchMoraCrit (strat);
3284  initBuchMoraPos (strat);
3285  strat->initEcart = initEcartBBA;
3286  strat->tailRing = r;
3287  strat->enterS = enterSBba;
3288  strat->sl = -1;
3289  i = n;
3290  i = 1;                        //some strange bug else
3291  /* initS(c->S,NULL,c->strat); */
3292  /* intS start: */
3293  // i=((i+IDELEMS(c->S)+15)/16)*16;
3294  strat->ecartS = (intset) omAlloc (i * sizeof (int));  /*initec(i); */
3295  strat->sevS = (unsigned long *) omAlloc0 (i * sizeof (unsigned long));
3296  /*initsevS(i); */
3297  strat->S_2_R = (int *) omAlloc0 (i * sizeof (int));   /*initS_2_R(i); */
3298  strat->fromQ = NULL;
3299  strat->Shdl = idInit (1, 1);
3300  strat->S = strat->Shdl->m;
3301  strat->lenS = (int *) omAlloc0 (i * sizeof (int));
3302  if((isDifficultField) || (eliminationProblem))
3303    strat->lenSw = (wlen_type *) omAlloc0 (i * sizeof (wlen_type));
3304  else
3305    strat->lenSw = NULL;
3306  assume (n > 0);
3307  add_to_basis_ideal_quotient (I->m[0], this, NULL);
3308
3309  assume (strat->sl == IDELEMS (strat->Shdl) - 1);
3310  if(!(F4_mode))
3311  {
3312    poly *array_arg = I->m;
3313    array_arg++;
3314    introduceDelayedPairs (array_arg, n - 1);
3315    /*
3316       for (i=1;i<n;i++)//the 1 is wanted, because first element is added to basis
3317       {
3318       //     add_to_basis(I->m[i],-1,-1,c);
3319       si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
3320       si->i=-1;
3321       si->j=-2;
3322       si->expected_length=pQuality(I->m[i],this,pLength(I->m[i]));
3323       si->deg=pTotaldegree(I->m[i]);
3324       if (!rField_is_Zp(r))
3325       {
3326       p_Cleardenom(I->m[i], r);
3327       }
3328       si->lcm_of_lm=I->m[i];
3329
3330       //      c->apairs[n-1-i]=si;
3331       apairs[n-i-1]=si;
3332       ++(pair_top);
3333       } */
3334  }
3335  else
3336  {
3337    for(i = 1; i < n; i++)      //the 1 is wanted, because first element is added to basis
3338      add_to_basis_ideal_quotient (I->m[i], this, NULL);
3339  }
3340  for(i = 0; i < IDELEMS (I); i++)
3341  {
3342    I->m[i] = NULL;
3343  }
3344  idDelete (&I);
3345  add_later = idInit (ADD_LATER_SIZE, S->rank);
3346#ifdef USE_NORO
3347  use_noro = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
3348              && (!(eliminationProblem)) && (n_GetChar(currRing->cf) <= 32003));
3349  use_noro_last_block = false;
3350  if((!(use_noro)) && (lastDpBlockStart <= (currRing->N)))
3351  {
3352    use_noro_last_block = ((!(nc)) && (S->rank <= 1) && (rField_is_Zp (r))
3353                           && (n_GetChar(currRing->cf) <= 32003));
3354  }
3355#else
3356  use_noro = false;
3357  use_noro_last_block = false;
3358#endif
3359  //Print("NORO last block %i",use_noro_last_block);
3360  memset (add_later->m, 0, ADD_LATER_SIZE * sizeof (poly));
3361}
3362
3363slimgb_alg::~slimgb_alg ()
3364{
3365
3366  if(!(completed))
3367  {
3368    poly *add = (poly *) omalloc ((pair_top + 2) * sizeof (poly));
3369    int piter;
3370    int pos = 0;
3371    for(piter = 0; piter <= pair_top; piter++)
3372    {
3373      sorted_pair_node *s = apairs[piter];
3374      if(s->i < 0)
3375      {
3376        //delayed element
3377        if(s->lcm_of_lm != NULL)
3378        {
3379          add[pos] = s->lcm_of_lm;
3380          pos++;
3381        }
3382      }
3383      free_sorted_pair_node (s, r);
3384      apairs[piter] = NULL;
3385    }
3386    pair_top = -1;
3387    add[pos] = NULL;
3388    pos = 0;
3389    while(add[pos] != NULL)
3390    {
3391      add_to_basis_ideal_quotient (add[pos], this, NULL);
3392      pos++;
3393    }
3394    for(piter = 0; piter <= pair_top; piter++)
3395    {
3396      sorted_pair_node *s = apairs[piter];
3397      assume (s->i >= 0);
3398      free_sorted_pair_node (s, r);
3399      apairs[piter] = NULL;
3400    }
3401    pair_top = -1;
3402  }
3403  id_Delete (&add_later, r);
3404  int i, j;
3405  slimgb_alg *c = this;
3406  while(c->to_destroy)
3407  {
3408    pDelete (&(c->to_destroy->p));
3409    poly_list_node *old = c->to_destroy;
3410    c->to_destroy = c->to_destroy->next;
3411    omfree (old);
3412  }
3413  while(c->F)
3414  {
3415    for(i = 0; i < c->F->size; i++)
3416    {
3417      pDelete (&(c->F->mp[i].m));
3418    }
3419    omfree (c->F->mp);
3420    c->F->mp = NULL;
3421    mp_array_list *old = c->F;
3422    c->F = c->F->next;
3423    omfree (old);
3424  }
3425  while(c->F_minus)
3426  {
3427    for(i = 0; i < c->F_minus->size; i++)
3428    {
3429      pDelete (&(c->F_minus->p[i]));
3430    }
3431    omfree (c->F_minus->p);
3432    c->F_minus->p = NULL;
3433    poly_array_list *old = c->F_minus;
3434    c->F_minus = c->F_minus->next;
3435    omfree (old);
3436  }
3437#ifndef HAVE_BOOST
3438#ifndef USE_STDVECBOOL
3439  for(int z = 1 /* zero length at 0 */ ; z < c->n; z++)
3440  {
3441    omfree (c->states[z]);
3442  }
3443  omfree (c->states);
3444#endif
3445#endif
3446
3447  omfree (c->lengths);
3448  omfree (c->weighted_lengths);
3449  for(int z = 0; z < c->n; z++)
3450  {
3451    pDelete (&c->tmp_pair_lm[z]);
3452    omfree (c->tmp_spn[z]);
3453  }
3454  omfree (c->tmp_pair_lm);
3455  omfree (c->tmp_spn);
3456
3457  omfree (c->T_deg);
3458  if(c->T_deg_full)
3459    omfree (c->T_deg_full);
3460
3461  omFree (c->strat->ecartS);
3462  omFree (c->strat->sevS);
3463//   initsevS(i);
3464  omFree (c->strat->S_2_R);
3465
3466
3467  omFree (c->strat->lenS);
3468
3469  if(c->strat->lenSw)
3470    omFree (c->strat->lenSw);
3471
3472  for(i = 0; i < c->n; i++)
3473  {
3474    if(c->gcd_of_terms[i])
3475      pDelete (&(c->gcd_of_terms[i]));
3476  }
3477  omfree (c->gcd_of_terms);
3478
3479  omfree (c->apairs);
3480  if(TEST_OPT_PROT)
3481  {
3482    //Print("calculated %d NFs\n",c->normal_forms);
3483    Print ("\nNF:%i product criterion:%i, ext_product criterion:%i \n",
3484           c->normal_forms, c->easy_product_crit, c->extended_product_crit);
3485  }
3486
3487  for(i = 0; i <= c->strat->sl; i++)
3488  {
3489    if(!c->strat->S[i])
3490      continue;
3491    BOOLEAN found = FALSE;
3492    for(j = 0; j < c->n; j++)
3493    {
3494      if(c->S->m[j] == c->strat->S[i])
3495      {
3496        found = TRUE;
3497        break;
3498      }
3499    }
3500    if(!found)
3501      pDelete (&c->strat->S[i]);
3502  }
3503//   for(i=0;i<c->n;i++)
3504//   {
3505//     if (c->rep[i]!=i)
3506//     {
3507// //       for(j=0;j<=c->strat->sl;j++)
3508// {
3509// //   if(c->strat->S[j]==c->S->m[i])
3510// {
3511// //     c->strat->S[j]=NULL;
3512// //     break;
3513// //   }
3514// //       }
3515// //      PrintS("R_delete");
3516//       pDelete(&c->S->m[i]);
3517//     }
3518//   }
3519
3520  if(completed)
3521  {
3522    for(i = 0; i < c->n; i++)
3523    {
3524      assume (c->S->m[i] != NULL);
3525      if(p_GetComp (c->S->m[i], currRing) > this->syz_comp)
3526        continue;
3527      for(j = 0; j < c->n; j++)
3528      {
3529        if((c->S->m[j] == NULL) || (i == j))
3530          continue;
3531        assume (p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
3532                                      c->S->m[i], ~c->short_Exps[i],
3533                                      c->r) == p_LmDivisibleBy (c->S->m[j],
3534                                                                c->S->m[i],
3535                                                                c->r));
3536        if(p_LmShortDivisibleBy (c->S->m[j], c->short_Exps[j],
3537                                 c->S->m[i], ~c->short_Exps[i], c->r))
3538        {
3539          pDelete (&c->S->m[i]);
3540          break;
3541        }
3542      }
3543    }
3544  }
3545  omfree (c->short_Exps);
3546
3547  ideal I = c->S;
3548  IDELEMS (I) = c->n;
3549  idSkipZeroes (I);
3550  for(i = 0; i <= c->strat->sl; i++)
3551    c->strat->S[i] = NULL;
3552  id_Delete (&c->strat->Shdl, c->r);
3553  pDelete (&c->tmp_lm);
3554  omUnGetSpecBin (&lm_bin);
3555  delete c->strat;
3556}
3557
3558ideal t_rep_gb (ring r, ideal arg_I, int syz_comp, BOOLEAN F4_mode)
3559{
3560  assume (r == currRing);
3561  ring orig_ring = r;
3562  int pos;
3563  ring new_ring = rAssure_TDeg (orig_ring, 1, rVar (orig_ring), pos);
3564  ideal s_h;
3565  if(orig_ring != new_ring)
3566  {
3567    rChangeCurrRing (new_ring);
3568    s_h = idrCopyR_NoSort (arg_I, orig_ring, new_ring);
3569    idTest (s_h);
3570    /*int i;
3571       for(i=0;i<IDELEMS(s_h);i++)
3572       {
3573       poly p=s_h->m[i];
3574       while(p)
3575       {
3576       p_Setm(p,new_ring);
3577       pIter(p);
3578       }
3579       } */
3580  }
3581  else
3582  {
3583    s_h = id_Copy (arg_I, orig_ring);
3584  }
3585
3586  ideal s_result = do_t_rep_gb (new_ring, s_h, syz_comp, F4_mode, pos);
3587  ideal result;
3588  if(orig_ring != new_ring)
3589  {
3590    idTest (s_result);
3591    rChangeCurrRing (orig_ring);
3592    result = idrMoveR_NoSort (s_result, new_ring, orig_ring);
3593
3594    idTest (result);
3595    //rChangeCurrRing(new_ring);
3596    rDelete(new_ring);
3597    //rChangeCurrRing(orig_ring);
3598  }
3599  else
3600    result = s_result;
3601  idTest (result);
3602  return result;
3603}
3604
3605ideal
3606do_t_rep_gb (ring /*r*/, ideal arg_I, int syz_comp, BOOLEAN F4_mode, int deg_pos)
3607{
3608  //  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)));
3609
3610  if(TEST_OPT_PROT)
3611    if(F4_mode)
3612      PrintS ("F4 Modus \n");
3613
3614  //debug_Ideal=arg_debug_Ideal;
3615  //if (debug_Ideal) PrintS("DebugIdeal received\n");
3616  // Print("Idelems %i \n----------\n",IDELEMS(arg_I));
3617  ideal I = arg_I;
3618  id_Compactify (I,currRing);
3619  if(idIs0 (I))
3620    return I;
3621  int i;
3622  for(i = 0; i < IDELEMS (I); i++)
3623  {
3624    assume (I->m[i] != NULL);
3625    simplify_poly (I->m[i], currRing);
3626  }
3627
3628  qsort (I->m, IDELEMS (I), sizeof (poly), poly_crit);
3629  //Print("Idelems %i \n----------\n",IDELEMS(I));
3630  //slimgb_alg* c=(slimgb_alg*) omalloc(sizeof(slimgb_alg));
3631  //int syz_comp=arg_I->rank;
3632  slimgb_alg *c = new slimgb_alg (I, syz_comp, F4_mode, deg_pos);
3633
3634  while((c->pair_top >= 0)
3635        && ((!(TEST_OPT_DEGBOUND))
3636            || (c->apairs[c->pair_top]->deg <= Kstd1_deg)))
3637  {
3638#ifdef HAVE_F4
3639    if(F4_mode)
3640      go_on_F4 (c);
3641    else
3642#endif
3643      go_on (c);
3644  }
3645  if(c->pair_top < 0)
3646    c->completed = TRUE;
3647  I = c->S;
3648  delete c;
3649  if(TEST_OPT_REDSB)
3650  {
3651    ideal erg = kInterRed (I, NULL);
3652    assume (I != erg);
3653    id_Delete (&I, currRing);
3654    return erg;
3655  }
3656  //qsort(I->m, IDELEMS(I),sizeof(poly),pLmCmp_func);
3657  assume (I->rank >= id_RankFreeModule (I,currRing));
3658  return (I);
3659}
3660
3661void now_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * c)
3662{
3663  int i, j;
3664  if(arg_i == arg_j)
3665  {
3666    return;
3667  }
3668  if(arg_i > arg_j)
3669  {
3670    i = arg_j;
3671    j = arg_i;
3672  }
3673  else
3674  {
3675    i = arg_i;
3676    j = arg_j;
3677  }
3678  c->states[j][i] = HASTREP;
3679}
3680
3681static BOOLEAN
3682has_t_rep (const int &arg_i, const int &arg_j, slimgb_alg * state)
3683{
3684  assume (0 <= arg_i);
3685  assume (0 <= arg_j);
3686  assume (arg_i < state->n);
3687  assume (arg_j < state->n);
3688  if(arg_i == arg_j)
3689  {
3690    return (TRUE);
3691  }
3692  if(arg_i > arg_j)
3693  {
3694    return (state->states[arg_i][arg_j] == HASTREP);
3695  }
3696  else
3697  {
3698    return (state->states[arg_j][arg_i] == HASTREP);
3699  }
3700}
3701
3702#if 0                           // unused
3703static int pLcmDeg (poly a, poly b)
3704{
3705  int i;
3706  int n = 0;
3707  for(i = (currRing->N); i; i--)
3708  {
3709    n += si_max (pGetExp (a, i), pGetExp (b, i));
3710  }
3711  return n;
3712}
3713#endif
3714
3715static void shorten_tails (slimgb_alg * c, poly monom)
3716{
3717  return;
3718// BOOLEAN corr=lenS_correct(c->strat);
3719  for(int i = 0; i < c->n; i++)
3720  {
3721    //enter tail
3722
3723    if(c->S->m[i] == NULL)
3724      continue;
3725    poly tail = c->S->m[i]->next;
3726    poly prev = c->S->m[i];
3727    BOOLEAN did_something = FALSE;
3728    while((tail != NULL) && (pLmCmp (tail, monom) >= 0))
3729    {
3730      if(p_LmDivisibleBy (monom, tail, c->r))
3731      {
3732        did_something = TRUE;
3733        prev->next = tail->next;
3734        tail->next = NULL;
3735        p_Delete (&tail, c->r);
3736        tail = prev;
3737        //PrintS("Shortened");
3738        c->lengths[i]--;
3739      }
3740      prev = tail;
3741      tail = tail->next;
3742    }
3743    if(did_something)
3744    {
3745      int new_pos;
3746      wlen_type q;
3747      q = pQuality (c->S->m[i], c, c->lengths[i]);
3748      new_pos = simple_posInS (c->strat, c->S->m[i], c->lengths[i], q);
3749
3750      int old_pos = -1;
3751      //assume new_pos<old_pos
3752      for(int z = 0; z <= c->strat->sl; z++)
3753      {
3754        if(c->strat->S[z] == c->S->m[i])
3755        {
3756          old_pos = z;
3757          break;
3758        }
3759      }
3760      if(old_pos == -1)
3761        for(int z = new_pos - 1; z >= 0; z--)
3762        {
3763          if(c->strat->S[z] == c->S->m[i])
3764          {
3765            old_pos = z;
3766            break;
3767          }
3768        }
3769      assume (old_pos >= 0);
3770      assume (new_pos <= old_pos);
3771      assume (pLength (c->strat->S[old_pos]) == c->lengths[i]);
3772      c->strat->lenS[old_pos] = c->lengths[i];
3773      if(c->strat->lenSw)
3774        c->strat->lenSw[old_pos] = q;
3775      if(new_pos < old_pos)
3776        move_forward_in_S (old_pos, new_pos, c->strat);
3777      length_one_crit (c, i, c->lengths[i]);
3778    }
3779  }
3780}
3781
3782#if 0                           // currently unused
3783static sorted_pair_node *pop_pair (slimgb_alg * c)
3784{
3785  clean_top_of_pair_list (c);
3786
3787  if(c->pair_top < 0)
3788    return NULL;
3789  else
3790    return (c->apairs[c->pair_top--]);
3791}
3792#endif
3793
3794void slimgb_alg::cleanDegs (int lower, int upper)
3795{
3796  assume (is_homog);
3797  int deg;
3798  if(TEST_OPT_PROT)
3799  {
3800    PrintS ("C");
3801  }
3802  for(deg = lower; deg <= upper; deg++)
3803  {
3804    int i;
3805    for(i = 0; i < n; i++)
3806    {
3807      if(T_deg[i] == deg)
3808      {
3809        poly h;
3810        h = S->m[i];
3811        h = redNFTail (h, strat->sl, strat, lengths[i]);
3812        if(!rField_is_Zp (r))
3813        {
3814          p_Cleardenom (h, r); //includes p_Content(h,r);
3815        }
3816        else
3817          pNorm (h);
3818        //TODO:GCD of TERMS
3819        poly got =::gcd_of_terms (h, r);
3820        p_Delete (&gcd_of_terms[i], r);
3821        gcd_of_terms[i] = got;
3822        int len = pLength (h);
3823        wlen_type wlen = pQuality (h, this, len);
3824        if(weighted_lengths)
3825          weighted_lengths[i] = wlen;
3826        lengths[i] = len;
3827        assume (h == S->m[i]);
3828        int j;
3829        for(j = 0; j <= strat->sl; j++)
3830        {
3831          if(h == strat->S[j])
3832          {
3833            int new_pos = simple_posInS (strat, h, len, wlen);
3834            if(strat->lenS)
3835            {
3836              strat->lenS[j] = len;
3837            }
3838            if(strat->lenSw)
3839            {
3840              strat->lenSw[j] = wlen;
3841            }
3842            if(new_pos < j)
3843            {
3844              move_forward_in_S (j, new_pos, strat);
3845            }
3846            else
3847            {
3848              if(new_pos > j)
3849                new_pos = new_pos - 1;  //is identical with one element
3850              if(new_pos > j)
3851                move_backward_in_S (j, new_pos, strat);
3852            }
3853            break;
3854          }
3855        }
3856      }
3857    }
3858  }
3859  {
3860    int i, j;
3861    for(i = 0; i < this->n; i++)
3862    {
3863      for(j = 0; j < i; j++)
3864      {
3865        if(T_deg[i] + T_deg[j] <= upper)
3866        {
3867          now_t_rep (i, j, this);
3868        }
3869      }
3870    }
3871  }
3872  //TODO resort and update strat->S,strat->lenSw
3873  //TODO mark pairs
3874}
3875
3876sorted_pair_node *top_pair (slimgb_alg * c)
3877{
3878  while(c->pair_top >= 0)
3879  {
3880    super_clean_top_of_pair_list (c);   //yeah, I know, it's odd that I use a different proc here
3881    if((c->is_homog) && (c->pair_top >= 0)
3882       && (c->apairs[c->pair_top]->deg >= c->lastCleanedDeg + 2))
3883    {
3884      int upper = c->apairs[c->pair_top]->deg - 1;
3885      c->cleanDegs (c->lastCleanedDeg + 1, upper);
3886      c->lastCleanedDeg = upper;
3887    }
3888    else
3889    {
3890      break;
3891    }
3892  }
3893
3894  if(c->pair_top < 0)
3895    return NULL;
3896  else
3897    return (c->apairs[c->pair_top]);
3898}
3899
3900sorted_pair_node *quick_pop_pair (slimgb_alg * c)
3901{
3902  if(c->pair_top < 0)
3903    return NULL;
3904  else
3905    return (c->apairs[c->pair_top--]);
3906}
3907
3908static void super_clean_top_of_pair_list (slimgb_alg * c)
3909{
3910  while((c->pair_top >= 0)
3911        && (c->apairs[c->pair_top]->i >= 0)
3912        &&
3913        (good_has_t_rep
3914         (c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i, c)))
3915  {
3916    free_sorted_pair_node (c->apairs[c->pair_top], c->r);
3917    c->pair_top--;
3918  }
3919}
3920
3921void clean_top_of_pair_list (slimgb_alg * c)
3922{
3923  while((c->pair_top >= 0) && (c->apairs[c->pair_top]->i >= 0)
3924        &&
3925        (!state_is
3926         (UNCALCULATED, c->apairs[c->pair_top]->j, c->apairs[c->pair_top]->i,
3927          c)))
3928  {
3929    free_sorted_pair_node (c->apairs[c->pair_top], c->r);
3930    c->pair_top--;
3931  }
3932}
3933
3934static BOOLEAN
3935state_is (calc_state state, const int &arg_i, const int &arg_j,
3936          slimgb_alg * c)
3937{
3938  assume (0 <= arg_i);
3939  assume (0 <= arg_j);
3940  assume (arg_i < c->n);
3941  assume (arg_j < c->n);
3942  if(arg_i == arg_j)
3943  {
3944    return (TRUE);
3945  }
3946  if(arg_i > arg_j)
3947  {
3948    return (c->states[arg_i][arg_j] == state);
3949  }
3950  else
3951    return (c->states[arg_j][arg_i] == state);
3952}
3953
3954void free_sorted_pair_node (sorted_pair_node * s, ring r)
3955{
3956  if(s->i >= 0)
3957    p_Delete (&s->lcm_of_lm, r);
3958  omfree (s);
3959}
3960
3961static BOOLEAN
3962pair_better (sorted_pair_node * a, sorted_pair_node * b, slimgb_alg * /*c*/)
3963{
3964  if(a->deg < b->deg)
3965    return TRUE;
3966  if(a->deg > b->deg)
3967    return FALSE;
3968
3969  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
3970  if(comp == 1)
3971    return FALSE;
3972  if(-1 == comp)
3973    return TRUE;
3974  if(a->expected_length < b->expected_length)
3975    return TRUE;
3976  if(a->expected_length > b->expected_length)
3977    return FALSE;
3978  if(a->i + a->j < b->i + b->j)
3979    return TRUE;
3980  if(a->i + a->j > b->i + b->j)
3981    return FALSE;
3982  if(a->i < b->i)
3983    return TRUE;
3984  if(a->i > b->i)
3985    return FALSE;
3986  return TRUE;
3987}
3988
3989static int tgb_pair_better_gen (const void *ap, const void *bp)
3990{
3991  sorted_pair_node *a = *((sorted_pair_node **) ap);
3992  sorted_pair_node *b = *((sorted_pair_node **) bp);
3993  assume ((a->i > a->j) || (a->i < 0));
3994  assume ((b->i > b->j) || (b->i < 0));
3995  if(a->deg < b->deg)
3996    return -1;
3997  if(a->deg > b->deg)
3998    return 1;
3999
4000  int comp = pLmCmp (a->lcm_of_lm, b->lcm_of_lm);
4001
4002  if(comp == 1)
4003    return 1;
4004  if(-1 == comp)
4005    return -1;
4006  if(a->expected_length < b->expected_length)
4007    return -1;
4008  if(a->expected_length > b->expected_length)
4009    return 1;
4010  if(a->i + a->j < b->i + b->j)
4011    return -1;
4012  if(a->i + a->j > b->i + b->j)
4013    return 1;
4014  if(a->i < b->i)
4015    return -1;
4016  if(a->i > b->i)
4017    return 1;
4018  return 0;
4019}
4020
4021static poly gcd_of_terms (poly p, ring r)
4022{
4023  int max_g_0 = 0;
4024  assume (p != NULL);
4025  int i;
4026  poly m = pOne ();
4027  poly t;
4028  for(i = (currRing->N); i; i--)
4029  {
4030    pSetExp (m, i, pGetExp (p, i));
4031    if(max_g_0 == 0)
4032      if(pGetExp (m, i) > 0)
4033        max_g_0 = i;
4034  }
4035
4036  t = p->next;
4037  while(t != NULL)
4038  {
4039    if(max_g_0 == 0)
4040      break;
4041    for(i = max_g_0; i; i--)
4042    {
4043      pSetExp (m, i, si_min (pGetExp (t, i), pGetExp (m, i)));
4044      if(max_g_0 == i)
4045        if(pGetExp (m, i) == 0)
4046          max_g_0 = 0;
4047      if((max_g_0 == 0) && (pGetExp (m, i) > 0))
4048      {
4049        max_g_0 = i;
4050      }
4051    }
4052    t = t->next;
4053  }
4054  p_Setm (m, r);
4055  if(max_g_0 > 0)
4056    return m;
4057  pDelete (&m);
4058  return NULL;
4059}
4060
4061static inline BOOLEAN pHasNotCFExtended (poly p1, poly p2, poly m)
4062{
4063
4064  if(pGetComp (p1) > 0 || pGetComp (p2) > 0)
4065    return FALSE;
4066  int i = 1;
4067  loop
4068  {
4069    if((pGetExp (p1, i) - pGetExp (m, i) > 0)
4070       && (pGetExp (p2, i) - pGetExp (m, i) > 0))
4071      return FALSE;
4072    if(i == (currRing->N))
4073      return TRUE;
4074    i++;
4075  }
4076}
4077
4078//for impl reasons may return false if the the normal product criterion matches
4079static inline BOOLEAN
4080extended_product_criterion (poly p1, poly gcd1, poly p2, poly gcd2,
4081                            slimgb_alg * c)
4082{
4083  if(c->nc)
4084    return FALSE;
4085  if(gcd1 == NULL)
4086    return FALSE;
4087  if(gcd2 == NULL)
4088    return FALSE;
4089  gcd1->next = gcd2;            //may ordered incorrect
4090  poly m = gcd_of_terms (gcd1, c->r);
4091  gcd1->next = NULL;
4092  if(m == NULL)
4093    return FALSE;
4094
4095  BOOLEAN erg = pHasNotCFExtended (p1, p2, m);
4096  pDelete (&m);
4097  return erg;
4098}
4099
4100#if 0                           //currently unused
4101static poly kBucketGcd (kBucket * b, ring r)
4102{
4103  int s = 0;
4104  int i;
4105  poly m, n;
4106  BOOLEAN initialized = FALSE;
4107  for(i = MAX_BUCKET - 1; i >= 0; i--)
4108  {
4109    if(b->buckets[i] != NULL)
4110    {
4111      if(!initialized)
4112      {
4113        m = gcd_of_terms (b->buckets[i], r);
4114        initialized = TRUE;
4115        if(m == NULL)
4116          return NULL;
4117      }
4118      else
4119      {
4120        n = gcd_of_terms (b->buckets[i], r);
4121        if(n == NULL)
4122        {
4123          pDelete (&m);
4124          return NULL;
4125        }
4126        n->next = m;
4127        poly t = gcd_of_terms (n, r);
4128        n->next = NULL;
4129        pDelete (&m);
4130        pDelete (&n);
4131        m = t;
4132        if(m == NULL)
4133          return NULL;
4134
4135      }
4136    }
4137  }
4138  return m;
4139}
4140#endif
4141
4142static inline wlen_type quality_of_pos_in_strat_S (int pos, slimgb_alg * c)
4143{
4144  if(c->strat->lenSw != NULL)
4145    return c->strat->lenSw[pos];
4146  return c->strat->lenS[pos];
4147}
4148
4149#ifdef HAVE_PLURAL
4150static inline wlen_type
4151quality_of_pos_in_strat_S_mult_high (int pos, poly high, slimgb_alg * c)
4152  //meant only for nc
4153{
4154  poly m = pOne ();
4155  pExpVectorDiff (m, high, c->strat->S[pos]);
4156  poly product = nc_mm_Mult_pp (m, c->strat->S[pos], c->r);
4157  wlen_type erg = pQuality (product, c);
4158  pDelete (&m);
4159  pDelete (&product);
4160  return erg;
4161}
4162#endif
4163
4164static void
4165multi_reduction_lls_trick (red_object * los, int /*losl*/, slimgb_alg * c,
4166                           find_erg & erg)
4167{
4168  erg.expand = NULL;
4169  BOOLEAN swap_roles;           //from reduce_by, to_reduce_u if fromS
4170  if(erg.fromS)
4171  {
4172    if(pLmEqual (c->strat->S[erg.reduce_by], los[erg.to_reduce_u].p))
4173    {
4174      wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
4175      int best = erg.to_reduce_u + 1;
4176/*
4177      for (i=erg.to_reduce_u;i>=erg.to_reduce_l;i--)
4178      {
4179  int qc=los[i].guess_quality(c);
4180  if (qc<quality_a)
4181  {
4182    best=i;
4183    quality_a=qc;
4184  }
4185      }
4186      if(best!=erg.to_reduce_u+1)
4187      {*/
4188      wlen_type qc;
4189      best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
4190      if(qc < quality_a)
4191      {
4192        los[best].flatten ();
4193        int b_pos = kBucketCanonicalize (los[best].bucket);
4194        los[best].p = los[best].bucket->buckets[b_pos];
4195        qc = pQuality (los[best].bucket->buckets[b_pos], c);
4196        if(qc < quality_a)
4197        {
4198          red_object h = los[erg.to_reduce_u];
4199          los[erg.to_reduce_u] = los[best];
4200          los[best] = h;
4201          swap_roles = TRUE;
4202        }
4203        else
4204          swap_roles = FALSE;
4205      }
4206      else
4207      {
4208        swap_roles = FALSE;
4209      }
4210    }
4211    else
4212    {
4213      if(erg.to_reduce_u > erg.to_reduce_l)
4214      {
4215        wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
4216#ifdef HAVE_PLURAL
4217        if((c->nc) && (!(rIsSCA (c->r))))
4218          quality_a =
4219            quality_of_pos_in_strat_S_mult_high (erg.reduce_by,
4220                                                 los[erg.to_reduce_u].p, c);
4221#endif
4222        int best = erg.to_reduce_u + 1;
4223        wlen_type qc;
4224        best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
4225        assume (qc == los[best].guess_quality (c));
4226        if(qc < quality_a)
4227        {
4228          los[best].flatten ();
4229          int b_pos = kBucketCanonicalize (los[best].bucket);
4230          los[best].p = los[best].bucket->buckets[b_pos];
4231          qc = pQuality (los[best].bucket->buckets[b_pos], c);
4232          //(best!=erg.to_reduce_u+1)
4233          if(qc < quality_a)
4234          {
4235            red_object h = los[erg.to_reduce_u];
4236            los[erg.to_reduce_u] = los[best];
4237            los[best] = h;
4238            erg.reduce_by = erg.to_reduce_u;
4239            erg.fromS = FALSE;
4240            erg.to_reduce_u--;
4241          }
4242        }
4243      }
4244      else
4245      {
4246        assume (erg.to_reduce_u == erg.to_reduce_l);
4247        wlen_type quality_a = quality_of_pos_in_strat_S (erg.reduce_by, c);
4248        wlen_type qc = los[erg.to_reduce_u].guess_quality (c);
4249        if(qc < 0)
4250          PrintS ("Wrong wlen_type");
4251        if(qc < quality_a)
4252        {
4253          int best = erg.to_reduce_u;
4254          los[best].flatten ();
4255          int b_pos = kBucketCanonicalize (los[best].bucket);
4256          los[best].p = los[best].bucket->buckets[b_pos];
4257          qc = pQuality (los[best].bucket->buckets[b_pos], c);
4258          assume (qc >= 0);
4259          if(qc < quality_a)
4260          {
4261            BOOLEAN exp = FALSE;
4262            if(qc <= 2)
4263            {
4264              //Print("\n qc is %lld \n",qc);
4265              exp = TRUE;
4266            }
4267            else
4268            {
4269              if(qc < quality_a / 2)
4270                exp = TRUE;
4271              else if(erg.reduce_by < c->n / 4)
4272                exp = TRUE;
4273            }
4274            if(exp)
4275            {
4276              poly clear_into;
4277              los[erg.to_reduce_u].flatten ();
4278              kBucketClear (los[erg.to_reduce_u].bucket, &clear_into,
4279                            &erg.expand_length);
4280              erg.expand = pCopy (clear_into);
4281              kBucketInit (los[erg.to_reduce_u].bucket, clear_into,
4282                           erg.expand_length);
4283              if(TEST_OPT_PROT)
4284                PrintS ("e");
4285            }
4286          }
4287        }
4288      }
4289
4290      swap_roles = FALSE;
4291      return;
4292    }
4293  }
4294  else
4295  {
4296    if(erg.reduce_by > erg.to_reduce_u)
4297    {
4298      //then lm(rb)>= lm(tru) so =
4299      assume (erg.reduce_by == erg.to_reduce_u + 1);
4300      int best = erg.reduce_by;
4301      wlen_type quality_a = los[erg.reduce_by].guess_quality (c);
4302      wlen_type qc;
4303      best = find_best (los, erg.to_reduce_l, erg.to_reduce_u, qc, c);
4304
4305      if(qc < quality_a)
4306      {
4307        red_object h = los[erg.reduce_by];
4308        los[erg.reduce_by] = los[best];
4309        los[best] = h;
4310      }
4311      swap_roles = FALSE;
4312      return;
4313    }
4314    else
4315    {
4316      assume (!pLmEqual (los[erg.reduce_by].p, los[erg.to_reduce_l].p));
4317      assume (erg.to_reduce_u == erg.to_reduce_l);
4318      //further assume, that reduce_by is the above all other polys
4319      //with same leading term
4320      int il = erg.reduce_by;
4321      wlen_type quality_a = los[erg.reduce_by].guess_quality (c);
4322      wlen_type qc;
4323      while((il > 0) && pLmEqual (los[il - 1].p, los[il].p))
4324      {
4325        il--;
4326        qc = los[il].guess_quality (c);
4327        if(qc < quality_a)
4328        {
4329          quality_a = qc;
4330          erg.reduce_by = il;
4331        }
4332      }
4333      swap_roles = FALSE;
4334    }
4335  }
4336  if(swap_roles)
4337  {
4338    if(TEST_OPT_PROT)
4339      PrintS ("b");
4340    poly clear_into;
4341    int new_length;
4342    int bp = erg.to_reduce_u;   //bucket_positon
4343    //kBucketClear(los[bp].bucket,&clear_into,&new_length);
4344    new_length = los[bp].clear_to_poly ();
4345    clear_into = los[bp].p;
4346    poly p = c->strat->S[erg.reduce_by];
4347    int j = erg.reduce_by;
4348    int old_length = c->strat->lenS[j]; // in view of S
4349    los[bp].p = p;
4350    kBucketInit (los[bp].bucket, p, old_length);
4351    wlen_type qal = pQuality (clear_into, c, new_length);
4352    int pos_in_c = -1;
4353    int z;
4354    int new_pos;
4355    new_pos = simple_posInS (c->strat, clear_into, new_length, qal);
4356    assume (new_pos <= j);
4357    for(z = c->n; z; z--)
4358    {
4359      if(p == c->S->m[z - 1])
4360      {
4361        pos_in_c = z - 1;
4362        break;
4363      }
4364    }
4365
4366    int tdeg_full = -1;
4367    int tdeg = -1;
4368    if(pos_in_c >= 0)
4369    {
4370#ifdef TGB_RESORT_PAIRS
4371      c->used_b = TRUE;
4372      c->replaced[pos_in_c] = TRUE;
4373#endif
4374      tdeg = c->T_deg[pos_in_c];
4375      c->S->m[pos_in_c] = clear_into;
4376      c->lengths[pos_in_c] = new_length;
4377      c->weighted_lengths[pos_in_c] = qal;
4378      if(c->gcd_of_terms[pos_in_c] == NULL)
4379        c->gcd_of_terms[pos_in_c] = gcd_of_terms (clear_into, c->r);
4380      if(c->T_deg_full)
4381        tdeg_full = c->T_deg_full[pos_in_c] =
4382          c->pTotaldegree_full (clear_into);
4383      else
4384        tdeg_full = tdeg;
4385      c_S_element_changed_hook (pos_in_c, c);
4386    }
4387    else
4388    {
4389      if(c->eliminationProblem)
4390      {
4391        tdeg_full = c->pTotaldegree_full (clear_into);
4392        tdeg = c->pTotaldegree (clear_into);
4393      }
4394    }
4395    c->strat->S[j] = clear_into;
4396    c->strat->lenS[j] = new_length;
4397
4398    assume (pLength (clear_into) == new_length);
4399    if(c->strat->lenSw != NULL)
4400      c->strat->lenSw[j] = qal;
4401    if(!rField_is_Zp (c->r))
4402    {
4403      p_Cleardenom (clear_into, c->r);  //should be unnecessary
4404      //includes p_Content(clear_into, c->r);
4405    }
4406    else
4407      pNorm (clear_into);
4408#ifdef FIND_DETERMINISTIC
4409    erg.reduce_by = j;
4410    //resort later see diploma thesis, find_in_S must be deterministic
4411    //during multireduction if spolys are only in the span of the
4412    //input polys
4413#else
4414    if(new_pos < j)
4415    {
4416      if(c->strat->honey)
4417        c->strat->ecartS[j] = tdeg_full - tdeg;
4418      move_forward_in_S (j, new_pos, c->strat);
4419      erg.reduce_by = new_pos;
4420    }
4421#endif
4422  }
4423}
4424
4425static int fwbw (red_object * los, int i)
4426{
4427  int i2 = i;
4428  int step = 1;
4429
4430  BOOLEAN bw = FALSE;
4431  BOOLEAN incr = TRUE;
4432
4433  while(1)
4434  {
4435    if(!bw)
4436    {
4437      step = si_min (i2, step);
4438      if(step == 0)
4439        break;
4440      i2 -= step;
4441
4442      if(!pLmEqual (los[i].p, los[i2].p))
4443      {
4444        bw = TRUE;
4445        incr = FALSE;
4446      }
4447      else
4448      {
4449        if((!incr) && (step == 1))
4450          break;
4451      }
4452    }
4453    else
4454    {
4455      step = si_min (i - i2, step);
4456      if(step == 0)
4457        break;
4458      i2 += step;
4459      if(pLmEqual (los[i].p, los[i2].p))
4460      {
4461        if(step == 1)
4462          break;
4463        else
4464        {
4465          bw = FALSE;
4466        }
4467      }
4468    }
4469    if(incr)
4470      step *= 2;
4471    else
4472    {
4473      if(step % 2 == 1)
4474        step = (step + 1) / 2;
4475      else
4476        step /= 2;
4477    }
4478  }
4479  return i2;
4480}
4481
4482static void
4483canonicalize_region (red_object * los, int l, int u, slimgb_alg * /*c*/)
4484{
4485  assume (l <= u + 1);
4486  int i;
4487  for(i = l; i <= u; i++)
4488  {
4489    kBucketCanonicalize (los[i].bucket);
4490  }
4491}
4492
4493#ifdef SING_NDEBUG
4494static void
4495multi_reduction_find (red_object * los, int /*losl*/, slimgb_alg * c, int startf,
4496                      find_erg & erg)
4497#else
4498static void
4499multi_reduction_find (red_object * los, int losl, slimgb_alg * c, int startf,
4500                      find_erg & erg)
4501#endif
4502{
4503  kStrategy strat = c->strat;
4504
4505  assume (startf <= losl);
4506  assume ((startf == losl - 1)
4507          || (pLmCmp (los[startf].p, los[startf + 1].p) == -1));
4508  int i = startf;
4509
4510  int j;
4511  while(i >= 0)
4512  {
4513    assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) <= 0));
4514    assume (is_valid_ro (los[i]));
4515    j = kFindDivisibleByInS_easy (strat, los[i]);
4516    if(j >= 0)
4517    {
4518      erg.to_reduce_u = i;
4519      erg.reduce_by = j;
4520      erg.fromS = TRUE;
4521      int i2 = fwbw (los, i);
4522      assume (pLmEqual (los[i].p, los[i2].p));
4523      assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p)));
4524      assume (i >= i2);
4525
4526      erg.to_reduce_l = i2;
4527      assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1));
4528      canonicalize_region (los, erg.to_reduce_u + 1, startf, c);
4529      return;
4530    }
4531    if(j < 0)
4532    {
4533      //not reduceable, try to use this for reducing higher terms
4534      int i2 = fwbw (los, i);
4535      assume (pLmEqual (los[i].p, los[i2].p));
4536      assume ((i2 == 0) || (!pLmEqual (los[i2].p, los[i2 - 1].p)));
4537      assume (i >= i2);
4538      if(i2 != i)
4539      {
4540        erg.to_reduce_u = i - 1;
4541        erg.to_reduce_l = i2;
4542        erg.reduce_by = i;
4543        erg.fromS = FALSE;
4544        assume ((i == losl - 1) || (pLmCmp (los[i].p, los[i + 1].p) == -1));
4545        canonicalize_region (los, erg.to_reduce_u + 1, startf, c);
4546        return;
4547      }
4548      i--;
4549    }
4550  }
4551  erg.reduce_by = -1;           //error code
4552  return;
4553}
4554
4555 //  nicht reduzierbare eintraege in ergebnisliste schreiben
4556//   nullen loeschen
4557//   while(finde_groessten leitterm reduzierbar(c,erg))
4558//   {
4559
4560static int
4561multi_reduction_clear_zeroes (red_object * los, int losl, int l, int u)
4562{
4563  int deleted = 0;
4564  int i = l;
4565  int last = -1;
4566  while(i <= u)
4567  {
4568    if(los[i].p == NULL)
4569    {
4570      kBucketDestroy (&los[i].bucket);
4571//      delete los[i];//here we assume los are constructed with new
4572      //destroy resources, must be added here
4573      if(last >= 0)
4574      {
4575        memmove (los + (int) (last + 1 - deleted), los + (last + 1),
4576                 sizeof (red_object) * (i - 1 - last));
4577      }
4578      last = i;
4579      deleted++;
4580    }
4581    i++;
4582  }
4583  if((last >= 0) && (last != losl - 1))
4584    memmove (los + (int) (last + 1 - deleted), los + last + 1,
4585             sizeof (red_object) * (losl - 1 - last));
4586  return deleted;
4587}
4588
4589int search_red_object_pos (red_object * a, int top, red_object * key)
4590{
4591  int an = 0;
4592  int en = top;
4593  if(top == -1)
4594    return 0;
4595  if(pLmCmp (key->p, a[top].p) == 1)
4596    return top + 1;
4597  int i;
4598  loop
4599  {
4600    if(an >= en - 1)
4601    {
4602      if(pLmCmp (key->p, a[an].p) == -1)
4603        return an;
4604      return en;
4605    }
4606    i = (an + en) / 2;
4607    if(pLmCmp (key->p, a[i].p) == -1)
4608      en = i;
4609    else
4610      an = i;
4611  }
4612}
4613
4614static void sort_region_down (red_object * los, int l, int u, slimgb_alg * /*c*/)
4615{
4616  int r_size = u - l + 1;
4617  qsort (los + l, r_size, sizeof (red_object), red_object_better_gen);
4618  int i;
4619  int *new_indices = (int *) omalloc ((r_size) * sizeof (int));
4620  int bound = 0;
4621  BOOLEAN at_end = FALSE;
4622  for(i = l; i <= u; i++)
4623  {
4624    if(!(at_end))
4625    {
4626      bound = new_indices[i - l] =
4627        bound + search_red_object_pos (los + bound, l - bound - 1, los + i);
4628      if(bound == l)
4629        at_end = TRUE;
4630    }
4631    else
4632    {
4633      new_indices[i - l] = l;
4634    }
4635  }
4636  red_object *los_region =
4637    (red_object *) omalloc (sizeof (red_object) * (u - l + 1));
4638  for(int i = 0; i < r_size; i++)
4639  {
4640    new_indices[i] += i;
4641    los_region[i] = los[l + i];
4642    assume ((i == 0) || (new_indices[i] > new_indices[i - 1]));
4643  }
4644
4645  i = r_size - 1;
4646  int j = u;
4647  int j2 = l - 1;
4648  while(i >= 0)
4649  {
4650    if(new_indices[i] == j)
4651    {
4652      los[j] = los_region[i];
4653      i--;
4654      j--;
4655    }
4656    else
4657    {
4658      assume (new_indices[i] < j);
4659      los[j] = los[j2];
4660      assume (j2 >= 0);
4661      j2--;
4662      j--;
4663    }
4664  }
4665  omfree (los_region);
4666  omfree (new_indices);
4667}
4668
4669//assume that los is ordered ascending by leading term, all non zero
4670static void multi_reduction (red_object * los, int &losl, slimgb_alg * c)
4671{
4672  poly *delay = (poly *) omalloc (losl * sizeof (poly));
4673  int delay_s = 0;
4674  //initialize;
4675  assume (c->strat->sl >= 0);
4676  assume (losl > 0);
4677  int i;
4678  wlen_type max_initial_quality = 0;
4679
4680  for(i = 0; i < losl; i++)
4681  {
4682    los[i].sev = pGetShortExpVector (los[i].p);
4683//SetShortExpVector();
4684    los[i].p = kBucketGetLm (los[i].bucket);
4685    if(los[i].initial_quality > max_initial_quality)
4686      max_initial_quality = los[i].initial_quality;
4687    // else
4688//         Print("init2_qal=%lld;", los[i].initial_quality);
4689//     Print("initial_quality=%lld;",max_initial_quality);
4690  }
4691
4692  int curr_pos = losl - 1;
4693
4694//  nicht reduzierbare eintrï¿œe in ergebnisliste schreiben
4695  // nullen loeschen
4696  while(curr_pos >= 0)
4697  {
4698    if((c->use_noro_last_block)
4699       && (lies_in_last_dp_block (los[curr_pos].p, c)))
4700    {
4701      int pn_noro = curr_pos + 1;
4702      poly *p_noro = (poly *) omalloc (pn_noro * sizeof (poly));
4703      for(i = 0; i < pn_noro; i++)
4704      {
4705        int dummy_len;
4706        poly p;
4707        los[i].p = NULL;
4708        kBucketClear (los[i].bucket, &p, &dummy_len);
4709        p_noro[i] = p;
4710      }
4711      if(n_GetChar(currRing->cf) < 255)
4712      {
4713        noro_step < tgb_uint8 > (p_noro, pn_noro, c);
4714      }
4715      else
4716      {
4717        if(n_GetChar(currRing->cf) < 65000)
4718        {
4719          noro_step < tgb_uint16 > (p_noro, pn_noro, c);
4720        }
4721        else
4722        {
4723          noro_step < tgb_uint32 > (p_noro, pn_noro, c);
4724        }
4725      }
4726      for(i = 0; i < pn_noro; i++)
4727      {
4728        los[i].p = p_noro[i];
4729        los[i].sev = pGetShortExpVector (los[i].p);
4730        //ignore quality
4731        kBucketInit (los[i].bucket, los[i].p, pLength (los[i].p));
4732      }
4733      qsort (los, pn_noro, sizeof (red_object), red_object_better_gen);
4734      int deleted =
4735        multi_reduction_clear_zeroes (los, losl, pn_noro, curr_pos);
4736      losl -= deleted;
4737      curr_pos -= deleted;
4738      break;
4739    }
4740    find_erg erg;
4741
4742    multi_reduction_find (los, losl, c, curr_pos, erg); //last argument should be curr_pos
4743    if(erg.reduce_by < 0)
4744      break;
4745
4746    erg.expand = NULL;
4747
4748    multi_reduction_lls_trick (los, losl, c, erg);
4749
4750    int i;
4751    //    wrp(los[erg.to_reduce_u].p);
4752    //PrintLn();
4753    multi_reduce_step (erg, los, c);
4754
4755
4756    if(!TEST_OPT_REDTHROUGH)
4757    {
4758      for(i = erg.to_reduce_l; i <= erg.to_reduce_u; i++)
4759      {
4760        if(los[i].p != NULL)    //the check (los[i].p!=NULL) might be invalid
4761        {
4762          //
4763          assume (los[i].initial_quality > 0);
4764          if(los[i].guess_quality (c)
4765             > 1.5 * delay_factor * max_initial_quality)
4766          {
4767            if(TEST_OPT_PROT)
4768              PrintS ("v");
4769            los[i].canonicalize ();
4770            if(los[i].guess_quality (c) > delay_factor * max_initial_quality)
4771            {
4772              if(TEST_OPT_PROT)
4773                PrintS (".");
4774              los[i].clear_to_poly ();
4775              //delay.push_back(los[i].p);
4776              delay[delay_s] = los[i].p;
4777              delay_s++;
4778              los[i].p = NULL;
4779            }
4780          }
4781        }
4782      }
4783    }
4784    int deleted = multi_reduction_clear_zeroes (los, losl, erg.to_reduce_l,
4785                                                erg.to_reduce_u);
4786    if(erg.fromS == FALSE)
4787      curr_pos = si_max (erg.to_reduce_u, erg.reduce_by);
4788    else
4789      curr_pos = erg.to_reduce_u;
4790    losl -= deleted;
4791    curr_pos -= deleted;
4792
4793    //Print("deleted %i \n",deleted);
4794    if((TEST_V_UPTORADICAL) && (!(erg.fromS)))
4795      sort_region_down (los, si_min (erg.to_reduce_l, erg.reduce_by),
4796                        (si_max (erg.to_reduce_u, erg.reduce_by)) - deleted,
4797                        c);
4798    else
4799      sort_region_down (los, erg.to_reduce_l, erg.to_reduce_u - deleted, c);
4800
4801    if(erg.expand)
4802    {
4803#ifdef FIND_DETERMINISTIC
4804      int i;
4805      for(i = 0; c->expandS[i]; i++) ;
4806      c->expandS = (poly *) omrealloc (c->expandS, (i + 2) * sizeof (poly));
4807      c->expandS[i] = erg.expand;
4808      c->expandS[i + 1] = NULL;
4809#else
4810      int ecart = 0;
4811      if(c->eliminationProblem)
4812      {
4813        ecart =
4814          c->pTotaldegree_full (erg.expand) - c->pTotaldegree (erg.expand);
4815      }
4816      add_to_reductors (c, erg.expand, erg.expand_length, ecart);
4817#endif
4818    }
4819  }
4820
4821  //sorted_pair_node** pairs=(sorted_pair_node**)
4822  //  omalloc(delay_s*sizeof(sorted_pair_node*));
4823  c->introduceDelayedPairs (delay, delay_s);
4824  /*
4825     for(i=0;i<delay_s;i++)
4826     {
4827     poly p=delay[i];
4828     //if (rPar(c->r)==0)
4829     simplify_poly(p,c->r);
4830     sorted_pair_node* si=(sorted_pair_node*) omalloc(sizeof(sorted_pair_node));
4831     si->i=-1;
4832     si->j=-1;
4833     if (!rField_is_Zp(c->r))
4834     {
4835     if (!c->nc)
4836     p=redTailShort(p, c->strat);
4837     p_Cleardenom(p, c->r);
4838     p_Content(p, c->r);
4839     }
4840     si->expected_length=pQuality(p,c,pLength(p));
4841     si->deg=pTotaldegree(p);
4842     si->lcm_of_lm=p;
4843     pairs[i]=si;
4844     }
4845     qsort(pairs,delay_s,sizeof(sorted_pair_node*),tgb_pair_better_gen2);
4846     c->apairs=spn_merge(c->apairs,c->pair_top+1,pairs,delay_s,c);
4847     c->pair_top+=delay_s; */
4848  omfree (delay);
4849  //omfree(pairs);
4850  return;
4851}
4852
4853void red_object::flatten ()
4854{
4855  assume (p == kBucketGetLm (bucket));
4856}
4857
4858void red_object::validate ()
4859{
4860  p = kBucketGetLm (bucket);
4861  if(p)
4862    sev = pGetShortExpVector (p);
4863}
4864
4865int red_object::clear_to_poly ()
4866{
4867  flatten ();
4868  int l;
4869  kBucketClear (bucket, &p, &l);
4870  return l;
4871}
4872
4873void reduction_step::reduce (red_object * /*r*/, int /*l*/, int /*u*/)
4874{
4875}
4876
4877void simple_reducer::do_reduce (red_object & ro)
4878{
4879  number coef;
4880#ifdef HAVE_PLURAL
4881  if(c->nc)
4882    nc_BucketPolyRed_Z (ro.bucket, p, &coef);
4883  else
4884#endif
4885    coef = kBucketPolyRed (ro.bucket, p, p_len, c->strat->kNoether);
4886  nDelete (&coef);
4887}
4888
4889void simple_reducer::reduce (red_object * r, int l, int u)
4890{
4891  this->pre_reduce (r, l, u);
4892  int i;
4893//debug start
4894
4895  if(c->eliminationProblem)
4896  {
4897    assume (p_LmEqual (r[l].p, r[u].p, c->r));
4898    /*int lm_deg=pTotaldegree(r[l].p);
4899       reducer_deg=lm_deg+pTotaldegree_full(p)-pTotaldegree(p); */
4900  }
4901
4902  for(i = l; i <= u; i++)
4903  {
4904    this->do_reduce (r[i]);
4905  }
4906  for(i = l; i <= u; i++)
4907  {
4908    kBucketSimpleContent (r[i].bucket);
4909    r[i].validate ();
4910#ifdef TGB_DEBUG
4911#endif
4912  }
4913}
4914
4915reduction_step::~reduction_step ()
4916{
4917}
4918
4919simple_reducer::~simple_reducer ()
4920{
4921  if(fill_back != NULL)
4922  {
4923    kBucketInit (fill_back, p, p_len);
4924  }
4925  fill_back = NULL;
4926}
4927
4928void multi_reduce_step (find_erg & erg, red_object * r, slimgb_alg * c)
4929{
4930  static int id = 0;
4931  id++;
4932  unsigned long sev;
4933  BOOLEAN lt_changed = FALSE;
4934  int rn = erg.reduce_by;
4935  poly red;
4936  int red_len;
4937  simple_reducer *pointer;
4938  BOOLEAN work_on_copy = FALSE;
4939  if(erg.fromS)
4940  {
4941    red = c->strat->S[rn];
4942    red_len = c->strat->lenS[rn];
4943    assume (red_len == pLength (red));
4944  }
4945  else
4946  {
4947    r[rn].flatten ();
4948    kBucketClear (r[rn].bucket, &red, &red_len);
4949
4950    if(!rField_is_Zp (c->r))
4951    {
4952      p_Cleardenom (red, c->r); //should be unnecessary
4953      //includes p_Content(red, c->r);
4954    }
4955    pNormalize (red);
4956
4957    if((!(erg.fromS)) && (TEST_V_UPTORADICAL))
4958    {
4959      if(polynomial_root (red, c->r))
4960        lt_changed = TRUE;
4961      sev = p_GetShortExpVector (red, c->r);
4962    }
4963    red_len = pLength (red);
4964  }
4965  if(((TEST_V_MODPSOLVSB) && (red_len > 1))
4966     || ((c->nc) || (erg.to_reduce_u - erg.to_reduce_l > 5)))
4967  {
4968    work_on_copy = TRUE;
4969    // poly m=pOne();
4970    poly m = c->tmp_lm;
4971    pSetCoeff (m, nInit (1));
4972    pSetComp (m, 0);
4973    for(int i = 1; i <= (currRing->N); i++)
4974      pSetExp (m, i, (pGetExp (r[erg.to_reduce_l].p, i) - pGetExp (red, i)));
4975    pSetm (m);
4976    poly red_cp;
4977#ifdef HAVE_PLURAL
4978    if(c->nc)
4979      red_cp = nc_mm_Mult_pp (m, red, c->r);
4980    else
4981#endif
4982      red_cp = ppMult_mm (red, m);
4983    if(!erg.fromS)
4984    {
4985      kBucketInit (r[rn].bucket, red, red_len);
4986    }
4987    //now reduce the copy
4988    //static poly redNF2 (poly h,slimgb_alg* c , int &len, number&  m,int n)
4989
4990    if(!c->nc)
4991      redTailShort (red_cp, c->strat);
4992    //number mul;
4993    // red_len--;
4994//     red_cp->next=redNF2(red_cp->next,c,red_len,mul,c->average_length);
4995//     pSetCoeff(red_cp,nMult(red_cp->coef,mul));
4996//     nDelete(&mul);
4997//     red_len++;
4998    red = red_cp;
4999    red_len = pLength (red);
5000    // pDelete(&m);
5001  }
5002
5003  assume (red_len == pLength (red));
5004
5005  int reducer_deg = 0;
5006  if(c->eliminationProblem)
5007  {
5008    int lm_deg = c->pTotaldegree (r[erg.to_reduce_l].p);
5009    int ecart;
5010    if(erg.fromS)
5011    {
5012      ecart = c->strat->ecartS[erg.reduce_by];
5013    }
5014    else
5015    {
5016      ecart = c->pTotaldegree_full (red) - lm_deg;
5017    }
5018    reducer_deg = lm_deg + ecart;
5019  }
5020  pointer = new simple_reducer (red, red_len, reducer_deg, c);
5021
5022  if((!work_on_copy) && (!erg.fromS))
5023    pointer->fill_back = r[rn].bucket;
5024  else
5025    pointer->fill_back = NULL;
5026  pointer->reduction_id = id;
5027  pointer->c = c;
5028
5029  pointer->reduce (r, erg.to_reduce_l, erg.to_reduce_u);
5030  if(work_on_copy)
5031    pDelete (&pointer->p);
5032  delete pointer;
5033  if(lt_changed)
5034  {
5035    assume (!erg.fromS);
5036    r[erg.reduce_by].sev = sev;
5037  }
5038}
5039
5040void simple_reducer::pre_reduce (red_object * /*r*/, int /*l*/, int /*u*/)
5041{
5042}
5043
5044#if 0
5045template int pos_helper<int, int*>(skStrategy*, spolyrec*, int, int*, spolyrec**);
5046template int pos_helper<long, long*>(skStrategy*, spolyrec*, long, long*, spolyrec**);
5047
5048template void noro_step<unsigned char>(spolyrec**, int&, slimgb_alg*);
5049template void noro_step<unsigned int>(spolyrec**, int&, slimgb_alg*);
5050template void noro_step<unsigned short>(spolyrec**, int&, slimgb_alg*);
5051
5052
5053template int term_nodes_sort_crit<unsigned char>(void const*, void const*);
5054template int term_nodes_sort_crit<unsigned int>(void const*, void const*);
5055template int term_nodes_sort_crit<unsigned short>(void const*, void const*);
5056
5057template spolyrec* row_to_poly<unsigned char>(unsigned char*, spolyrec**, int, ip_sring*);
5058template spolyrec* row_to_poly<unsigned int>(unsigned int*, spolyrec**, int, ip_sring*);
5059template spolyrec* row_to_poly<unsigned short>(unsigned short*, spolyrec**, int, ip_sring*);
5060
5061template void simplest_gauss_modp<unsigned char>(unsigned char*, int, int);
5062template void simplest_gauss_modp<unsigned int>(unsigned int*, int, int);
5063template void simplest_gauss_modp<unsigned short>(unsigned short*, int, int);
5064
5065
5066template int modP_lastIndexRow<unsigned char>(unsigned char*, int);
5067template int modP_lastIndexRow<unsigned int>(unsigned int*, int);
5068template int modP_lastIndexRow<unsigned short>(unsigned short*, int);
5069
5070template SparseRow<unsigned char>* noro_red_to_non_poly_t<unsigned char>(spolyrec*, int&, NoroCache<unsigned char>*, slimgb_alg*);
5071template SparseRow<unsigned int>* noro_red_to_non_poly_t<unsigned int>(spolyrec*, int&, NoroCache<unsigned int>*, slimgb_alg*);
5072template SparseRow<unsigned short>* noro_red_to_non_poly_t<unsigned short>(spolyrec*, int&, NoroCache<unsigned short>*, slimgb_alg*);
5073
5074
5075template MonRedResNP<unsigned char> noro_red_mon_to_non_poly<unsigned char>(spolyrec*, NoroCache<unsigned char>*, slimgb_alg*);
5076template MonRedResNP<unsigned int> noro_red_mon_to_non_poly<unsigned int>(spolyrec*, NoroCache<unsigned int>*, slimgb_alg*);
5077template MonRedResNP<unsigned short> noro_red_mon_to_non_poly<unsigned short>(spolyrec*, NoroCache<unsigned short>*, slimgb_alg*);
5078
5079template SparseRow<unsigned char>* noro_red_to_non_poly_dense<unsigned char>(MonRedResNP<unsigned char>*, int, NoroCache<unsigned char>*);
5080template SparseRow<unsigned char>* noro_red_to_non_poly_sparse<unsigned char>(MonRedResNP<unsigned char>*, int, NoroCache<unsigned char>*);
5081template SparseRow<unsigned int>* noro_red_to_non_poly_dense<unsigned int>(MonRedResNP<unsigned int>*, int, NoroCache<unsigned int>*);
5082template SparseRow<unsigned int>* noro_red_to_non_poly_sparse<unsigned int>(MonRedResNP<unsigned int>*, int, NoroCache<unsigned int>*);
5083template SparseRow<unsigned short>* noro_red_to_non_poly_dense<unsigned short>(MonRedResNP<unsigned short>*, int, NoroCache<unsigned short>*);
5084template SparseRow<unsigned short>* noro_red_to_non_poly_sparse<unsigned short>(MonRedResNP<unsigned short>*, int, NoroCache<unsigned short>*);
5085
5086
5087
5088template class DataNoroCacheNode<unsigned char>;
5089template class DataNoroCacheNode<unsigned int>;
5090template class DataNoroCacheNode<unsigned short>;
5091
5092template class NoroCache<unsigned char>;
5093template class NoroCache<unsigned int>;
5094template class NoroCache<unsigned short>;
5095
5096
5097
5098template void add_coef_times_dense<unsigned char>(unsigned char*, int, unsigned char const*, int, snumber*);
5099template void add_coef_times_dense<unsigned int>(unsigned int*, int, unsigned int const*, int, snumber*);
5100template void add_coef_times_dense<unsigned short>(unsigned short*, int, unsigned short const*, int, snumber*);
5101template void add_coef_times_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*, snumber*);
5102template void add_coef_times_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*, snumber*);
5103template void add_coef_times_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*, snumber*);
5104template void add_dense<unsigned char>(unsigned char*, int, unsigned char const*, int);
5105template void add_dense<unsigned int>(unsigned int*, int, unsigned int const*, int);
5106template void add_dense<unsigned short>(unsigned short*, int, unsigned short const*, int);
5107template void add_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*);
5108template void add_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*);
5109template void add_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*);
5110
5111
5112template void sub_dense<unsigned char>(unsigned char*, int, unsigned char const*, int);
5113template void sub_dense<unsigned int>(unsigned int*, int, unsigned int const*, int);
5114template void sub_dense<unsigned short>(unsigned short*, int, unsigned short const*, int);
5115template void sub_sparse<unsigned char>(unsigned char*, int, SparseRow<unsigned char>*);
5116template void sub_sparse<unsigned int>(unsigned int*, int, SparseRow<unsigned int>*);
5117template void sub_sparse<unsigned short>(unsigned short*, int, SparseRow<unsigned short>*);
5118template void write_coef_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int);
5119template void write_coef_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int);
5120template void write_coef_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int);
5121template void write_coef_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int);
5122template void write_coef_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int);
5123template void write_coef_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int);
5124template void write_coef_times_xx_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int, snumber*);
5125template void write_coef_times_xx_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int, snumber*);
5126template void write_coef_times_xx_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int, snumber*);
5127template void write_coef_times_xx_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int, snumber*);
5128template void write_coef_times_xx_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int, snumber*);
5129template void write_coef_times_xx_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int, snumber*);
5130template void write_minus_coef_idx_to_buffer_dense<unsigned char>(CoefIdx<unsigned char>*, int&, unsigned char*, int);
5131template void write_minus_coef_idx_to_buffer_dense<unsigned int>(CoefIdx<unsigned int>*, int&, unsigned int*, int);
5132template void write_minus_coef_idx_to_buffer_dense<unsigned short>(CoefIdx<unsigned short>*, int&, unsigned short*, int);
5133template void write_minus_coef_idx_to_buffer<unsigned char>(CoefIdx<unsigned char>*, int&, int*, unsigned char*, int);
5134template void write_minus_coef_idx_to_buffer<unsigned int>(CoefIdx<unsigned int>*, int&, int*, unsigned int*, int);
5135template void write_minus_coef_idx_to_buffer<unsigned short>(CoefIdx<unsigned short>*, int&, int*, unsigned short*, int);
5136
5137
5138template class std::vector<DataNoroCacheNode<unsigned char>*>;
5139template class std::vector<DataNoroCacheNode<unsigned int>*>;
5140template class std::vector<DataNoroCacheNode<unsigned short>*>;
5141template class std::vector<PolySimple>;
5142
5143template void std::sort( CoefIdx<unsigned char>* , CoefIdx<unsigned char>*  );
5144template void std::sort( CoefIdx<unsigned int>*  , CoefIdx<unsigned int>*   );
5145template void std::sort( CoefIdx<unsigned short>*, CoefIdx<unsigned short>* );
5146
5147template void std::sort_heap<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5148template void std::sort_heap<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5149template void std::sort_heap<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5150
5151template void std::make_heap<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5152template void std::make_heap<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5153template void std::make_heap<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5154#endif
5155
5156#if 0
5157template void std::__final_insertion_sort<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5158template void std::__final_insertion_sort<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5159template void std::__final_insertion_sort<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5160
5161template void std::__introsort_loop<CoefIdx<unsigned char>*, long>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, long);
5162template void std::__introsort_loop<CoefIdx<unsigned int>*, long>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, long);
5163template void std::__introsort_loop<CoefIdx<unsigned short>*, long>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, long);
5164
5165template void std::__heap_select<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5166template void std::__heap_select<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5167template void std::__heap_select<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5168
5169template void std::__insertion_sort<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5170template void std::__insertion_sort<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5171template void std::__insertion_sort<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5172
5173template void std::__move_median_first<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char>*);
5174template void std::__move_median_first<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int>*);
5175template void std::__move_median_first<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short>*);
5176
5177template void std::__unguarded_linear_insert<CoefIdx<unsigned char>*>(CoefIdx<unsigned char>*);
5178template void std::__unguarded_linear_insert<CoefIdx<unsigned int>*>(CoefIdx<unsigned int>*);
5179template void std::__unguarded_linear_insert<CoefIdx<unsigned short>*>(CoefIdx<unsigned short>*);
5180
5181template void std::__adjust_heap<CoefIdx<unsigned char>*, long, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, long, long, CoefIdx<unsigned char>);
5182template void std::__adjust_heap<CoefIdx<unsigned int>*, long, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, long, long, CoefIdx<unsigned int>);
5183template void std::__adjust_heap<CoefIdx<unsigned short>*, long, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, long, long, CoefIdx<unsigned short>);
5184
5185template void std::__push_heap<CoefIdx<unsigned char>*, long, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, long, long, CoefIdx<unsigned char>);
5186template void std::__push_heap<CoefIdx<unsigned int>*, long, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, long, long, CoefIdx<unsigned int>);
5187template void std::__push_heap<CoefIdx<unsigned short>*, long, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, long, long, CoefIdx<unsigned short>);
5188
5189template CoefIdx<unsigned char>* std::__unguarded_partition<CoefIdx<unsigned char>*, CoefIdx<unsigned char> >(CoefIdx<unsigned char>*, CoefIdx<unsigned char>*, CoefIdx<unsigned char> const&);
5190template CoefIdx<unsigned int>* std::__unguarded_partition<CoefIdx<unsigned int>*, CoefIdx<unsigned int> >(CoefIdx<unsigned int>*, CoefIdx<unsigned int>*, CoefIdx<unsigned int> const&);
5191template CoefIdx<unsigned short>* std::__unguarded_partition<CoefIdx<unsigned short>*, CoefIdx<unsigned short> >(CoefIdx<unsigned short>*, CoefIdx<unsigned short>*, CoefIdx<unsigned short> const&);
5192
5193#endif
5194
Note: See TracBrowser for help on using the repository browser.