source: git/kernel/tgb.cc @ 7fe9e13

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