source: git/kernel/GBEngine/tgb.cc @ 74161f1

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