source: git/kernel/syz1.cc @ 0a4a704

spielwiese
Last change on this file since 0a4a704 was 0a4a704, checked in by Hans Schoenemann <hannes@…>, 14 years ago
size(resolution) git-svn-id: file:///usr/local/Singular/svn/trunk@12961 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 68.8 KB
Line 
1/****************************************
2*  Computer Algebra System SINGULAR     *
3****************************************/
4/* $Id$ */
5/*
6* ABSTRACT: resolutions
7*/
8
9#include "mod2.h"
10#include <mylimits.h>
11#include "options.h"
12#include "omalloc.h"
13#include "polys.h"
14#include "febase.h"
15#include "kstd1.h"
16#include "kutil.h"
17#include "stairc.h"
18//#include "cntrlc.h"
19#include "intvec.h"
20#include "numbers.h"
21#include "modulop.h"
22#include "ideals.h"
23#include "intvec.h"
24#include "ring.h"
25#include "syz.h"
26#include "kbuckets.h"
27#include "prCopy.h"
28#include "idrec.h"
29
30extern void p_Setm_Syz(poly p, ring r,
31                       int* Components, long* ShiftedComponents);
32
33/*--------------static variables------------------------*/
34/*---points to the real components, shifted of the actual module-*/
35int *  currcomponents=NULL;
36long *  currShiftedComponents=NULL;
37
38
39/*---head-term-polynomials for the reduction------------*/
40static poly redpol=NULL;
41/*---counts number of applications of GM-criteria-------*/
42//static int crit;
43//static int euler;
44
45/*3
46* deletes all entres of a pair
47*/
48void syDeletePair(SObject * so)
49{
50  pDelete(&(*so).p);
51  pDelete(&(*so).lcm);
52  pDelete(&(*so).syz);
53  (*so).p1 = NULL;
54  (*so).p2 = NULL;
55  (*so).ind1 = 0;
56  (*so).ind2 = 0;
57  (*so).syzind = -1;
58  (*so).order = 0;
59  (*so).isNotMinimal = NULL;
60  (*so).length = -1;
61  (*so).reference = -1;
62}
63
64/*3
65* initializes all entres of a pair
66*/
67void syInitializePair(SObject * so)
68{
69  (*so).p = NULL;
70  (*so).lcm = NULL;
71  (*so).syz = NULL;
72  (*so).p1 = NULL;
73  (*so).p2 = NULL;
74  (*so).ind1 = 0;
75  (*so).ind2 = 0;
76  (*so).syzind = -1;
77  (*so).order = 0;
78  (*so).isNotMinimal = NULL;
79  (*so).length = -1;
80  (*so).reference = -1;
81}
82
83/*3
84* puts all entres of a pair to another
85*/
86void syCopyPair(SObject * argso, SObject * imso)
87{
88  *imso=*argso;
89  (*argso).p = NULL;
90  (*argso).p1 = NULL;
91  (*argso).p2 = NULL;
92  (*argso).lcm = NULL;
93  (*argso).syz = NULL;
94  (*argso).ind1 = 0;
95  (*argso).ind2 = 0;
96  (*argso).syzind = -1;
97  (*argso).order = 0;
98  (*argso).isNotMinimal = NULL;
99  (*argso).length = -1;
100  (*argso).reference = -1;
101}
102
103/*3
104* deletes empty objects from a pair set beginning with
105* pair first
106* assumes a pair to be empty if .lcm does so
107*/
108void syCompactifyPairSet(SSet sPairs, int sPlength, int first)
109{
110  int k=first,kk=0;
111
112  while (k+kk<sPlength)
113  {
114    if (sPairs[k+kk].lcm!=NULL)
115    {
116      if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]);
117      k++;
118    }
119    else
120    {
121      kk++;
122    }
123  }
124  while (k<sPlength)
125  {
126    syInitializePair(&sPairs[k]);
127    k++;
128  }
129}
130
131/*3
132* deletes empty objects from a pair set beginning with
133* pair first
134* assumes a pair to be empty if .lcm does so
135*/
136void syCompactify1(SSet sPairs, int* sPlength, int first)
137{
138  int k=first,kk=0;
139
140  while (k+kk<*sPlength)
141  {
142    if (sPairs[k+kk].lcm!=NULL)
143    {
144      if (kk>0) syCopyPair(&sPairs[k+kk],&sPairs[k]);
145      k++;
146    }
147    else
148    {
149      kk++;
150    }
151  }
152  while (k<*sPlength)
153  {
154    syInitializePair(&sPairs[k]);
155    k++;
156  }
157  *sPlength -= kk;
158}
159
160/*3
161* replaces comp1dpc during homogeneous syzygy-computations
162* compares with components of currcomponents instead of the
163* exp[0]
164*/
165static int syzcomp0dpc(poly p1, poly p2)
166{
167  /*4 compare monomials by order then revlex*/
168    int i = pVariables;
169    if ((pGetExp(p1,i) == pGetExp(p2,i)))
170    {
171      do
172      {
173        i--;
174        if (i <= 1)
175        {
176           /*4 handle module case:*/
177           if (pGetComp(p1)==pGetComp(p2)) return 0;
178           else if
179              (currcomponents[pGetComp(p1)]>currcomponents[pGetComp(p2)])
180                return 1;
181           else return -1;
182        }
183      } while ((pGetExp(p1,i) == pGetExp(p2,i)));
184    }
185    if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
186    return -1;
187}
188
189/*3
190* replaces comp1dpc during homogeneous syzygy-computations
191* compares with components of currcomponents instead of the
192* exp[0]
193*/
194int syzcomp1dpc(poly p1, poly p2)
195{
196  int i = pVariables;
197  while ((i>1) && (pGetExp(p1,i)==pGetExp(p2,i)))
198    i--;
199  if (i>1)
200  {
201    if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
202    return -1;
203  }
204  int o1=pGetComp(p1);
205  int o2=pGetComp(p2);
206  if (o1==o2/*pGetComp(p1)==pGetComp(p2)*/) return 0;
207  if (currcomponents[o1]>currcomponents[o2]) return 1;
208  return -1;
209
210}
211
212/*3
213* replaces comp1dpc during homogeneous syzygy-computations
214* compares with components of currcomponents instead of the
215* exp[0]
216*/
217
218#ifdef PDEBUG
219static int syzcomp2dpc_test(poly p1, poly p2)
220{
221  long c1, c2, cc1, cc2, ccc1, ccc2, ec1, ec2;
222  c1 = pGetComp(p1);
223  c2 = pGetComp(p2);
224  cc1 = currcomponents[c1];
225  cc2 = currcomponents[c2];
226  ccc1 = currShiftedComponents[cc1];
227  ccc2 = currShiftedComponents[cc2];
228  ec1 = p1->exp[currRing->typ[1].data.syzcomp.place];
229  ec2 = p2->exp[currRing->typ[1].data.syzcomp.place];
230
231  if (ec1 != ccc1)
232  {
233    Warn("Shifted comp of p1 out of sync. should %d, is %d", ccc1, ec1);
234    //mmDBInfoBlock(p1);
235  }
236  if (ec2 != ccc2)
237  {
238    Warn("Shifted comp of p2 out of sync. should %d, is %d", ccc2, ec2);
239    //mmDBInfoBlock(p2);
240  }
241
242  if (c1 == c2)
243  {
244    assume(ccc1 == ccc2);
245  }
246  else if (cc1 > cc2)
247  {
248    assume(ccc1 > ccc2);
249  }
250  else
251  {
252    assume (cc1 < cc2);
253    assume (ccc1 < ccc2);
254  }
255  int o1=pGetOrder(p1), o2=pGetOrder(p2);
256  if (o1 > o2) return 1;
257  if (o1 < o2) return -1;
258
259  //if (o1>0)
260  {
261    int i = pVariables;
262    while ((i>1) && (pGetExp(p1,i)==pGetExp(p2,i)))
263      i--;
264    //(*orderingdepth)[pVariables-i]++;
265    if (i>1)
266    {
267      if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
268      return -1;
269    }
270  }
271  o1=pGetComp(p1);
272  o2=pGetComp(p2);
273  if (o1==o2/*pGetComp(p1)==pGetComp(p2)*/) return 0;
274  if (currcomponents[o1]>currcomponents[o2]) return 1;
275  return -1;
276}
277#endif // PDEBUG
278
279/*3
280* compares only the monomial without component
281*/
282static int syzcompmonomdp(poly p1, poly p2)
283{
284  int i;
285
286  /*4 compare monomials by order then revlex*/
287  if (pGetOrder(p1) == pGetOrder(p2))
288  {
289    i = pVariables;
290    if ((pGetExp(p1,i) == pGetExp(p2,i)))
291    {
292      do
293      {
294        i--;
295        if (i <= 1)
296          return 0;
297      } while ((pGetExp(p1,i) == pGetExp(p2,i)));
298    }
299    if (pGetExp(p1,i) < pGetExp(p2,i)) return 1;
300    return -1;
301  }
302  else if (pGetOrder(p1) > pGetOrder(p2)) return 1;
303  return -1;
304}
305
306poly syRedtail (poly p, syStrategy syzstr, int index)
307{
308  poly h, hn;
309  int j,pos;
310  ideal redWith=syzstr->orderedRes[index];
311
312  h = p;
313  hn = pNext(h);
314  while(hn != NULL)
315  {
316    j = syzstr->Firstelem[index-1][pGetComp(hn)]-1;
317    if (j>=0)
318    {
319      pos = j+syzstr->Howmuch[index-1][pGetComp(hn)];
320      while (j < pos)
321      {
322        if (pLmDivisibleByNoComp(redWith->m[j], hn))
323        {
324          //hn = sySPolyRed(hn,redWith->m[j]);
325          hn = ksOldSpolyRed(redWith->m[j],hn);
326          if (hn == NULL)
327          {
328            pNext(h) = NULL;
329            return p;
330          }
331          j = syzstr->Firstelem[index-1][pGetComp(hn)]-1;
332          pos = j+syzstr->Howmuch[index-1][pGetComp(hn)];
333        }
334        else
335        {
336          j++;
337        }
338      }
339    }
340    h = pNext(h) = hn;
341    hn = pNext(h);
342  }
343  return p;
344}
345
346
347/*3
348* local procedure for of syInitRes for the module case
349*/
350static int syChMin(intvec * iv)
351{
352  int i,j=-1,r=-1;
353
354  for (i=iv->length()-1;i>=0;i--)
355  {
356    if ((*iv)[i]>=0)
357    {
358      if ((j<0) || ((*iv)[i]<j))
359      {
360        j = (*iv)[i];
361        r = i;
362      }
363    }
364  }
365  return r;
366}
367
368/*3
369* initialize the resolution and puts in the argument as
370* zeroth entre, length must be > 0
371* assumes that the basering is degree-compatible
372*/
373SRes syInitRes(ideal arg,int * length, intvec * Tl, intvec * cw)
374{
375  if (idIs0(arg)) return NULL;
376  SRes resPairs = (SRes)omAlloc0(*length*sizeof(SSet));
377  resPairs[0] = (SSet)omAlloc0(IDELEMS(arg)*sizeof(SObject));
378  intvec * iv=NULL;
379  int i,j;
380
381  if (idRankFreeModule(arg)==0)
382  {
383    iv = idSort(arg);
384    for (i=0;i<IDELEMS(arg);i++)
385    {
386      (resPairs[0])[i].syz = /*pCopy*/(arg->m[(*iv)[i]-1]);
387      arg->m[(*iv)[i]-1] = NULL;
388      (resPairs[0])[i].order = pTotaldegree((resPairs[0])[i].syz);
389    }
390  }
391  else
392  {
393    iv = new intvec(IDELEMS(arg),1,-1);
394    for (i=0;i<IDELEMS(arg);i++)
395    {
396      (*iv)[i] = pTotaldegree(arg->m[i])+(*cw)[pGetComp(arg->m[i])-1];
397    }
398    for (i=0;i<IDELEMS(arg);i++)
399    {
400      j = syChMin(iv);
401      if (j<0) break;
402      (resPairs[0])[i].syz = arg->m[j];
403      arg->m[j] = NULL;
404      (resPairs[0])[i].order = (*iv)[j];
405      (*iv)[j] = -1;
406    }
407  }
408  if (iv!=NULL)  delete iv;
409  (*Tl)[0] = IDELEMS(arg);
410  return resPairs;
411}
412
413// rearrange shifted components
414long syReorderShiftedComponents(long * sc, int n)
415{
416  long holes = 0;
417  int i;
418  long new_comps = 0, new_space, max;
419
420  // count number of holes
421  for (i=1; i<n; i++)
422  {
423    if (sc[i-1] + 1 < sc[i]) holes++;
424  }
425
426  if (LONG_MAX - SYZ_SHIFT_BASE <= sc[n-1])
427  {
428    // need new components
429    new_comps = (((long) 1) << SYZ_SHIFT_MAX_NEW_COMP_ESTIMATE) - 1;
430    max = LONG_MAX;
431  }
432  else
433  {
434    max = sc[n-1] + SYZ_SHIFT_BASE;
435  }
436
437  // no we arrange things such that
438  // (n - holes) + holes*new_space + new_comps*SYZ_SHIFT_BASE= LONG_MAX
439  new_space = (max - n + holes - new_comps*SYZ_SHIFT_BASE) / holes;
440
441  assume(new_space < SYZ_SHIFT_BASE && new_space >= 4);
442
443  long* tc = ( long*) omAlloc(n*sizeof(long));
444  tc[0] = sc[0];
445  // rearrange things
446  for (i=1; i<n; i++)
447  {
448    if (sc[i-1] + 1 < sc[i])
449    {
450      tc[i] = tc[i-1] + new_space;
451    }
452    else
453    {
454      tc[i] = tc[i-1] + 1;
455    }
456    assume(tc[i] > tc[i-1]);
457  }
458
459  assume(LONG_MAX -  SYZ_SHIFT_BASE > tc[n-1]);
460#ifdef HAVE_ASSUME
461  for (i=1; i<n; i++)
462  {
463    assume(tc[i] >= 0);
464    assume(tc[i-1] + 1 <= tc[i]);
465  }
466#endif
467
468  omMemcpyW(sc, tc, n);
469  omFreeSize(tc, n*sizeof(long));
470  return new_space;
471}
472
473// this make a Setm on p
474static void pResetSetm(poly p)
475{
476#ifdef PDEBUG
477  poly q = p;
478#endif
479  while (p!= NULL)
480  {
481    pSetm(p);
482    pIter(p);
483  }
484#ifdef PDEBUG
485  pTest(q);
486#endif
487}
488
489void syResetShiftedComponents(syStrategy syzstr, int index,int hilb)
490{
491  assume(index > 0);
492  int i;
493  if (syzstr->res[index] != NULL)
494  {
495    long * prev_s;
496    int* prev_c;
497    int p_length;
498    rGetSComps(&prev_c, &prev_s, &p_length);
499    currcomponents = syzstr->truecomponents[index-1];
500    currShiftedComponents = syzstr->ShiftedComponents[index-1];
501    rChangeSComps(currcomponents,
502                  currShiftedComponents,
503                  IDELEMS(syzstr->res[index-1]));
504    if (hilb==0)
505    {
506      ideal id = syzstr->res[index];
507      for (i=0; i<IDELEMS(id); i++)
508      {
509        pResetSetm(id->m[i]);
510      }
511    }
512    else if (hilb==1)
513    {
514      assume (index>1);
515      assume (syzstr->resPairs[index-1]!=NULL);
516      SSet Pairs=syzstr->resPairs[index-1];
517      SSet Pairs1=syzstr->resPairs[index];
518      int till=(*syzstr->Tl)[index-1];
519      for (i=0;i<till;i++)
520      {
521        if (Pairs[i].syz!=NULL)
522          pResetSetm(Pairs[i].syz);
523      }
524      till=(*syzstr->Tl)[index];
525      for (i=0;i<till;i++)
526      {
527        if (Pairs1[i].p!=NULL)
528          pResetSetm(Pairs1[i].p);
529      }
530    }
531    currcomponents  = prev_c;
532    currShiftedComponents = prev_s;
533    rChangeSComps(prev_c, prev_s, p_length);
534  }
535}
536
537/*3
538* determines the place of a polynomial in the right ordered resolution
539* set the vectors of truecomponents
540*/
541static BOOLEAN syOrder(poly p,syStrategy syzstr,int index,
542                    int realcomp)
543{
544  int i=IDELEMS(syzstr->res[index-1])+1,j=0,k,tc,orc,ie=realcomp-1;
545  int *trind1=syzstr->truecomponents[index-1];
546  int *trind=syzstr->truecomponents[index];
547  long *shind=syzstr->ShiftedComponents[index];
548  int *bc=syzstr->backcomponents[index];
549  int *F1=syzstr->Firstelem[index-1];
550  int *H1=syzstr->Howmuch[index-1];
551  poly pp;
552  polyset o_r=syzstr->orderedRes[index]->m;
553  polyset or1=syzstr->orderedRes[index-1]->m;
554  BOOLEAN ret = FALSE;
555
556  // if != 0, then new element can go into same component
557  // i.e., we do not need to leave space in shifted components
558  long same_comp = 0;
559
560  if (p==NULL) return FALSE;
561  if (realcomp==0) realcomp=1;
562
563  if (index>1)
564    tc = trind1[pGetComp(p)]-1;
565  else
566    tc = pGetComp(p)-1;
567  loop         //while ((j<ie) && (trind1[orc]<=tc+1))
568  {
569    if (j>=ie)
570      break;
571    else
572    {
573      orc = pGetComp(o_r[j]);
574      if (trind1[orc]>tc+1) break;
575      else if (trind1[orc] == tc+1)
576      {
577        same_comp = 1;
578      }
579      else
580      {
581        assume(same_comp == 0);
582      }
583      j += H1[orc];
584    }
585  }
586  if (j>ie)
587  {
588    WerrorS("orderedRes to small");
589    return FALSE;
590  }
591  ie++;
592  if (j == (ie -1))
593  {
594    // new element is the last in ordered module
595    if (same_comp == 0)
596      same_comp = SYZ_SHIFT_BASE;
597
598    // test wheter we have enough space for new shifted component
599    if ((LONG_MAX - same_comp) <= shind[ie-1])
600    {
601      long new_space = syReorderShiftedComponents(shind, ie);
602      assume((LONG_MAX - same_comp) > shind[ie-1]);
603      ret = TRUE;
604      if (TEST_OPT_PROT) Print("(T%ld)", new_space);
605    }
606
607    // yes, then set new shifted component
608    assume(ie == 1 || shind[ie-1] > 0);
609    shind[ie] = shind[ie-1] + same_comp;
610  }
611  else
612  {
613    // new element must come in between
614    // i.e. at place j+1
615    long prev, next;
616
617    // test whether new component can get shifted value
618    prev = shind[j];
619    next = shind[j+1];
620    assume(next > prev);
621    if ((same_comp && prev + 2 >= next) || (!same_comp && next - prev < 4))
622    {
623       long new_space = syReorderShiftedComponents(shind, ie);
624      prev = shind[j];
625      next = shind[j+1];
626      assume((same_comp && prev + 2 < next) || (!same_comp && next - prev >= 4));
627      ret = TRUE;
628     if (TEST_OPT_PROT) Print("(B%ld)", new_space);
629    }
630
631    // make room for insertion of j+1 shifted component
632    for (k=ie; k > j+1; k--) shind[k] = shind[k-1];
633
634    if (same_comp)
635    {
636      // can simply add one
637      shind[j+1] = prev + 1;
638      assume(shind[j+1] + 1 < shind[j+2]);
639    }
640    else
641    {
642      // need to leave more breathing room - i.e. value goes in
643      // between
644      shind[j+1]  = prev + ((next - prev) >> 1);
645      assume (shind[j] + 1 < shind[j+1] && shind[j+1] + 1 < shind[j+2]);
646    }
647  }
648
649  if (o_r[j]!=NULL)
650  {
651    for (k=ie-1;k>j;k--)
652    {
653      o_r[k] = o_r[k-1];
654      bc[k] = bc[k-1];
655    }
656  }
657  o_r[j] = p;
658  bc[j] = realcomp-1;
659  (H1[pGetComp(p)])++;
660  for (k=0;k<i;k++)
661  {
662    if (F1[k]>j)
663      (F1[k])++;
664  }
665  if (F1[pGetComp(p)]==0)
666    F1[pGetComp(p)]=j+1;
667  for (k=0;k<IDELEMS((syzstr->res)[index]);k++)
668  {
669    if (trind[k]>j)
670      trind[k] += 1;
671  }
672  for (k=IDELEMS((syzstr->res)[index])-1;k>realcomp;k--)
673    trind[k] = trind[k-1];
674  trind[realcomp] = j+1;
675  return ret;
676}
677
678//#define OLD_PAIR_ORDER
679#ifdef OLD_PAIR_ORDER
680static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
681                          int howmuch, int index)
682{
683  int i=howmuch-1,i1=0,l,ll;
684  int ** Fin=syzstr->Firstelem;
685  int ** Hin=syzstr->Howmuch;
686  int ** bin=syzstr->backcomponents;
687  ideal o_r=syzstr->orderedRes[index+1];
688  intvec *result=new intvec(howmuch+1);
689  BOOLEAN isDivisible;
690  SObject tso;
691
692  while (i>=0)
693  {
694    tso = nextPairs[i];
695    isDivisible = FALSE;
696    if (syzstr->res[index+1]!=NULL)
697    {
698      l = Fin[index][pGetComp(tso.lcm)]-1;
699      if (l>=0)
700      {
701        ll = l+Hin[index][pGetComp(tso.lcm)];
702        while ((l<ll) && (!isDivisible))
703        {
704          if (o_r->m[l]!=NULL)
705          {
706            isDivisible = isDivisible ||
707              pLmDivisibleByNoComp(o_r->m[l],tso.lcm);
708          }
709          l++;
710        }
711      }
712    }
713    if (isDivisible)
714    {
715      syDeletePair(&nextPairs[i]);
716      //crit++;
717    }
718    else
719    {
720      nextPairs[i].p =
721        //sySPoly(tso.p1, tso.p2,tso.lcm);
722        spSpolyCreate(tso.p2, tso.p1,NULL,spSpolyLoop_General);
723      (*result)[i1] = i+1;
724      i1++;
725    }
726    i--;
727  }
728  return result;
729}
730#else
731static intvec* syLinStrat(SSet nextPairs, syStrategy syzstr,
732                          int howmuch, int index)
733{
734  int i=howmuch-1,i1=0,i2,i3,l,ll;
735  int ** Fin=syzstr->Firstelem;
736  int ** Hin=syzstr->Howmuch;
737  int ** bin=syzstr->backcomponents;
738  ideal o_r=syzstr->orderedRes[index+1];
739  intvec *result=new intvec(howmuch+1);
740  intvec *spl=new intvec(howmuch,1,-1);
741  BOOLEAN isDivisible;
742  SObject tso;
743
744  while (i>=0)
745  {
746    tso = nextPairs[i];
747    isDivisible = FALSE;
748    if (syzstr->res[index+1]!=NULL)
749    {
750      l = Fin[index][pGetComp(tso.lcm)]-1;
751      if (l>=0)
752      {
753        ll = l+Hin[index][pGetComp(tso.lcm)];
754        while ((l<ll) && (!isDivisible))
755        {
756          if (o_r->m[l]!=NULL)
757          {
758            isDivisible = isDivisible ||
759              pLmDivisibleByNoComp(o_r->m[l],tso.lcm);
760          }
761          l++;
762        }
763      }
764    }
765    if (isDivisible)
766    {
767      syDeletePair(&nextPairs[i]);
768      //crit++;
769    }
770    else
771    {
772      pTest(tso.p2);
773      pTest(tso.p1);
774      nextPairs[i].p =
775        ksOldCreateSpoly(tso.p2, tso.p1,NULL);
776      (*spl)[i] = pLength(nextPairs[i].p);
777    }
778    i--;
779  }
780  i3 = 0;
781  loop
782  {
783    i2 = -1;
784    for (i1=0;i1<howmuch;i1++)
785    {
786      if (i2==-1)
787      {
788        if ((*spl)[i1]!=-1)
789        {
790          i2 = i1;
791        }
792      }
793      else
794      {
795        if (((*spl)[i1]>=0) && ((*spl)[i1]<(*spl)[i2]))
796        {
797          i2 = i1;
798        }
799      }
800    }
801    if (i2>=0)
802    {
803      (*result)[i3] = i2+1;
804      (*spl)[i2] = -1;
805      i3++;
806    }
807    else
808    {
809      break;
810    }
811  }
812  delete spl;
813  return result;
814}
815#endif
816
817void syEnlargeFields(syStrategy syzstr,int index)
818{
819  pEnlargeSet(&(syzstr->res[index]->m),IDELEMS(syzstr->res[index]),16);
820  syzstr->truecomponents[index]=(int*)omRealloc0Size((ADDRESS)syzstr->truecomponents[index],
821                               (IDELEMS(syzstr->res[index])+1)*sizeof(int),
822                               (IDELEMS(syzstr->res[index])+17)*sizeof(int));
823  syzstr->ShiftedComponents[index]
824    =(long*)omRealloc0Size((ADDRESS)syzstr->ShiftedComponents[index],
825                              (IDELEMS(syzstr->res[index])+1)*sizeof(long),
826                              (IDELEMS(syzstr->res[index])+17)*sizeof(long));
827  syzstr->backcomponents[index]=(int*)omRealloc0Size((ADDRESS)syzstr->backcomponents[index],
828                               (IDELEMS(syzstr->res[index])+1)*sizeof(int),
829                               (IDELEMS(syzstr->res[index])+17)*sizeof(int));
830  syzstr->Howmuch[index]=(int*)omRealloc0Size((ADDRESS)syzstr->Howmuch[index],
831                               (IDELEMS(syzstr->res[index])+1)*sizeof(int),
832                               (IDELEMS(syzstr->res[index])+17)*sizeof(int));
833  syzstr->Firstelem[index]=(int*)omRealloc0Size((ADDRESS)syzstr->Firstelem[index],
834                               (IDELEMS(syzstr->res[index])+1)*sizeof(int),
835                               (IDELEMS(syzstr->res[index])+17)*sizeof(int));
836  syzstr->elemLength[index]=(int*)omRealloc0Size((ADDRESS)syzstr->elemLength[index],
837                               (IDELEMS(syzstr->res[index])+1)*sizeof(int),
838                               (IDELEMS(syzstr->res[index])+17)*sizeof(int));
839  syzstr->sev[index]=(unsigned long*)omRealloc0Size((ADDRESS)syzstr->sev[index],
840                                    (IDELEMS(syzstr->res[index])+1)*sizeof(unsigned long),
841                               (IDELEMS(syzstr->res[index])+17)*sizeof(unsigned long));
842  IDELEMS(syzstr->res[index]) += 16;
843  pEnlargeSet(&(syzstr->orderedRes[index]->m),IDELEMS(syzstr->orderedRes[index]),16);
844  IDELEMS(syzstr->orderedRes[index]) += 16;
845}
846/*3
847* reduces all pairs of degree deg in the module index
848* put the reduced generators to the resolvente which contains
849* the truncated kStd
850*/
851static void syRedNextPairs(SSet nextPairs, syStrategy syzstr,
852               int howmuch, int index)
853{
854  int i,j,k=IDELEMS(syzstr->res[index]);
855  int ks=IDELEMS(syzstr->res[index+1]),kk,l,ll;
856  int * Fin=syzstr->Firstelem[index-1];
857  int * Hin=syzstr->Howmuch[index-1];
858  int * bin=syzstr->backcomponents[index];
859  int * elL=syzstr->elemLength[index];
860  number coefgcd,n;
861  polyset redset=syzstr->orderedRes[index]->m;
862  poly p=NULL,q;
863  intvec *spl1;
864  SObject tso;
865  long * ShiftedComponents = syzstr->ShiftedComponents[index];
866  int* Components = syzstr->truecomponents[index];
867  assume(Components != NULL && ShiftedComponents != NULL);
868  BOOLEAN need_reset;
869
870  if ((nextPairs==NULL) || (howmuch==0)) return;
871  while ((k>0) && (syzstr->res[index]->m[k-1]==NULL)) k--;
872  while ((ks>0) && (syzstr->res[index+1]->m[ks-1]==NULL)) ks--;
873  spl1 = syLinStrat(nextPairs,syzstr,howmuch,index);
874  i=0;
875  while ((*spl1)[i]>0)
876  {
877    need_reset = FALSE;
878    tso = nextPairs[(*spl1)[i]-1];
879    if ((tso.p1!=NULL) && (tso.p2!=NULL))
880    {
881      nNormalize(pGetCoeff(tso.p1));
882      nNormalize(pGetCoeff(tso.p2));
883      coefgcd =
884        nGcd(pGetCoeff(tso.p1),pGetCoeff(tso.p2),currRing);
885      tso.syz = pHead(tso.lcm);
886      p = tso.syz;
887      pSetCoeff(p,nDiv(pGetCoeff(tso.p1),coefgcd));
888      pGetCoeff(p) = nNeg(pGetCoeff(p));
889      pSetComp(p,tso.ind2+1);
890      p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index
891      pNext(p) = pHead(tso.lcm);
892      pIter(p);
893      pSetComp(p,tso.ind1+1);
894      p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index
895      pSetCoeff(p,nDiv(pGetCoeff(tso.p2),coefgcd));
896      nDelete(&coefgcd);
897      if (tso.p != NULL)
898      {
899        kBucketInit(syzstr->bucket,tso.p,-1);
900        q = kBucketGetLm(syzstr->bucket);
901        j = Fin[pGetComp(q)]-1;
902        int pos = j+Hin[pGetComp(q)];
903        loop
904        {
905          if (j<0) break;
906          if (pLmDivisibleByNoComp(redset[j],q))
907          {
908            pNext(p) = pHead(q);
909            pIter(p);
910            pSetComp(p,bin[j]+1);
911            p_Setm_Syz(p, currRing, Components, ShiftedComponents); // actueller index
912//if (pLength(redset[j])!=syzstr->elemLength[index][bin[j]])
913//Print("Halt");
914//if (pLength(redset[j])!=syzstr->elemLength[index][bin[j]])
915//Print("Halt");
916            pGetCoeff(p) = nNeg(pGetCoeff(p));
917            number up = kBucketPolyRed(syzstr->bucket,redset[j],elL[bin[j]],
918                                       NULL);
919            // Thomas: Check whether you need number here
920            nDelete(&up);
921            q = kBucketGetLm(syzstr->bucket);
922            if (q==NULL) break;
923            j = Fin[pGetComp(q)]-1;
924            pos = j+Hin[pGetComp(q)];
925          }
926          else
927          {
928            j++;
929            if (j==pos) break;
930          }
931        }
932        int lb;
933        kBucketClear(syzstr->bucket,&tso.p,&lb);
934      }
935      if (tso.p != NULL)
936      {
937        if (TEST_OPT_PROT) PrintS("g");
938        if (k==IDELEMS((syzstr->res)[index]))
939        {
940          syEnlargeFields(syzstr,index);
941          bin=syzstr->backcomponents[index];
942          elL=syzstr->elemLength[index];
943          redset=syzstr->orderedRes[index]->m;
944          Components = syzstr->truecomponents[index];
945          ShiftedComponents = syzstr->ShiftedComponents[index];
946        }
947        pNext(p) = pHead(tso.p);
948        pIter(p);
949
950        assume(p!= NULL);
951        k++;
952        syzstr->res[index]->m[k-1] = tso.p;
953        syzstr->elemLength[index][k-1] = pLength(tso.p);
954        pNorm(syzstr->res[index]->m[k-1]);
955        need_reset = syOrder(syzstr->res[index]->m[k-1],syzstr,index,k);
956        pSetComp(p,k); // actueller index
957        p_Setm_Syz(p, currRing, Components, ShiftedComponents);
958        pGetCoeff(p) = nNeg(pGetCoeff(p));
959
960        tso.isNotMinimal = p;
961        tso.p = NULL;
962      }
963      else
964      {
965        if (TEST_OPT_PROT) PrintS(".");
966        //if (index % 2==0)
967          //euler++;
968        //else
969          //euler--;
970      }
971      if (ks==IDELEMS(syzstr->res[index+1]))
972      {
973        syEnlargeFields(syzstr,index+1);
974      }
975      syzstr->res[index+1]->m[ks] = tso.syz;
976      syzstr->elemLength[index+1][ks] = pLength(tso.syz);
977      pNorm(syzstr->res[index+1]->m[ks]);
978      tso.syz =NULL;
979      tso.syzind = ks;
980      if (need_reset)
981        syResetShiftedComponents(syzstr, index+1);
982      if (syOrder(syzstr->res[index+1]->m[ks],syzstr,index+1,ks+1))
983         syResetShiftedComponents(syzstr, index+2);
984      ks++;
985      p = NULL;
986      nextPairs[(*spl1)[i]-1] = tso;
987    }
988    i++;
989  }
990  delete spl1;
991}
992
993/*3
994* reduces the generators of the module index in degree deg
995* (which are actual syzygies of the module index-1)
996* wrt. the ideal generated by elements of lower degrees
997*/
998static void syRedGenerOfCurrDeg(syStrategy syzstr, int deg, int index)
999{
1000  ideal res=syzstr->res[index];
1001  int i=0,j,k=IDELEMS(res),kk;
1002  SSet sPairs=syzstr->resPairs[index-1];
1003
1004  while ((k>0) && (res->m[k-1]==NULL)) k--;
1005  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
1006          ((sPairs)[i].order<deg)))
1007    i++;
1008  if ((i>=(*syzstr->Tl)[index-1]) || ((sPairs)[i].order>deg)) return;
1009  while ((i<(*syzstr->Tl)[index-1]) && (((sPairs)[i].syz==NULL) ||
1010         ((sPairs)[i].order==deg)))
1011  {
1012    if ((sPairs)[i].syz!=NULL)
1013    {
1014      j = k-1;
1015      while ((j>=0) && (res->m[j]!=NULL) &&
1016             ((sPairs)[i].syz!=NULL))
1017      {
1018        if (pLmDivisibleBy(res->m[j],(sPairs)[i].syz))
1019        {
1020          (sPairs)[i].syz =
1021            ksOldSpolyRed(res->m[j],(sPairs)[i].syz);
1022            //sySPolyRed((sPairs)[i].syz,res->m[j]);
1023          j = k-1;
1024        }
1025        else
1026        {
1027          j--;
1028        }
1029      }
1030      if ((sPairs)[i].syz != NULL)
1031      {
1032        if (k==IDELEMS(res))
1033        {
1034          syEnlargeFields(syzstr,index);
1035          res=syzstr->res[index];
1036        }
1037        if (TEST_OPT_DEBUG)
1038        {
1039          if ((sPairs)[i].isNotMinimal==NULL)
1040          {
1041            PrintLn();
1042            PrintS("minimal generator: ");pWrite((syzstr->resPairs[index-1])[i].syz);
1043            PrintS("comes from: ");pWrite((syzstr->resPairs[index-1])[i].p1);
1044            PrintS("and: ");pWrite((syzstr->resPairs[index-1])[i].p2);
1045          }
1046        }
1047        //res->m[k] = (sPairs)[i].syz;
1048        res->m[k] = syRedtail((sPairs)[i].syz,syzstr,index);
1049        (sPairs)[i].syzind = k;
1050        syzstr->elemLength[index][k] = pLength((sPairs)[i].syz);
1051        pNorm(res->m[k]);
1052  //      (sPairs)[i].syz = NULL;
1053        k++;
1054        if (syOrder(res->m[k-1],syzstr,index,k))
1055          syResetShiftedComponents(syzstr, index);
1056        //euler++;
1057      }
1058      else
1059        (sPairs)[i].syzind = -1;
1060    }
1061    i++;
1062  }
1063}
1064
1065/*3
1066* puts a pair into the right place in resPairs
1067*/
1068void syEnterPair(SSet sPairs, SObject * so, int * sPlength,int index)
1069{
1070  int ll,k,no=(*so).order,sP=*sPlength,i;
1071  poly p=(*so).lcm;
1072
1073  if ((sP==0) || (sPairs[sP-1].order<=no))
1074    ll = sP;
1075  else if (sP==1)
1076    ll = 0;
1077  else
1078  {
1079    int an=0,en=sP-1;
1080    loop
1081    {
1082      if (an>=en-1)
1083      {
1084        if ((sPairs[an].order<=no) && (sPairs[an+1].order>no))
1085        {
1086          ll = an+1;
1087          break;
1088        }
1089        else if ((sPairs[en].order<=no) && (sPairs[en+1].order>no))
1090        {
1091          ll = en+1;
1092          break;
1093        }
1094        else if (sPairs[an].order>no)
1095        {
1096          ll = an;
1097          break;
1098        }
1099        else
1100        {
1101          PrintS("Hier ist was faul!\n");
1102          break;
1103        }
1104      }
1105      i=(an+en) / 2;
1106      if (sPairs[i].order <= no)
1107        an=i;
1108      else
1109        en=i;
1110    }
1111  }
1112  for (k=(*sPlength);k>ll;k--)
1113  {
1114    syCopyPair(&sPairs[k-1],&sPairs[k]);
1115  }
1116  syCopyPair(so,&sPairs[ll]);
1117  (*sPlength)++;
1118}
1119void syEnterPair(syStrategy syzstr, SObject * so, int * sPlength,int index)
1120{
1121  int ll;
1122
1123  if (*sPlength>=(*syzstr->Tl)[index])
1124  {
1125    SSet temp = (SSet)omAlloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject));
1126    for (ll=0;ll<(*syzstr->Tl)[index];ll++)
1127    {
1128      temp[ll].p = (syzstr->resPairs[index])[ll].p;
1129      temp[ll].p1 = (syzstr->resPairs[index])[ll].p1;
1130      temp[ll].p2 = (syzstr->resPairs[index])[ll].p2;
1131      temp[ll].syz = (syzstr->resPairs[index])[ll].syz;
1132      temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm;
1133      temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1;
1134      temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2;
1135      temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind;
1136      temp[ll].order = (syzstr->resPairs[index])[ll].order;
1137      temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal;
1138      temp[ll].length = (syzstr->resPairs[index])[ll].length;
1139      temp[ll].reference = (syzstr->resPairs[index])[ll].reference;
1140    }
1141    if (syzstr->resPairs[index] != NULL) // OB: ?????
1142      omFreeSize((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject));
1143    (*syzstr->Tl)[index] += 16;
1144    syzstr->resPairs[index] = temp;
1145  }
1146  syEnterPair(syzstr->resPairs[index],so,sPlength,index);
1147}
1148
1149/*3
1150* computes pairs from the new elements (beginning with the element newEl)
1151* in the module index
1152*/
1153static void syCreateNewPairs(syStrategy syzstr, int index, int newEl)
1154{
1155  SSet temp;
1156  SObject tso;
1157  int i,ii,j,k=IDELEMS(syzstr->res[index]),l=(*syzstr->Tl)[index],ll;
1158  int qc,first,pos,jj,j1;
1159  int * bci=syzstr->backcomponents[index];
1160  poly p,q;
1161  polyset rs=syzstr->res[index]->m,nPm;
1162
1163
1164  while ((k>0) && (rs[k-1]==NULL)) k--;
1165  if (newEl>=k) return;
1166
1167  long * ShiftedComponents = syzstr->ShiftedComponents[index];
1168  int* Components = syzstr->truecomponents[index];
1169
1170  ideal nP=idInit(k,syzstr->res[index]->rank);
1171  nPm=nP->m;
1172  while ((l>0) && ((syzstr->resPairs[index])[l-1].p1==NULL)) l--;
1173  for (j=newEl;j<k;j++)
1174  {
1175    q = rs[j];
1176    qc = pGetComp(q);
1177    first = syzstr->Firstelem[index-1][pGetComp(q)]-1;
1178    pos = first+syzstr->Howmuch[index-1][pGetComp(q)];
1179    for (i=first;i<pos;i++)
1180    {
1181      jj = bci[i];
1182      if (jj>=j) break;
1183      p = pOne();
1184      pLcm(rs[jj],q,p);
1185      pSetComp(p,j+1);
1186      p_Setm_Syz(p, currRing, Components, ShiftedComponents);
1187      ii = first;
1188      loop
1189      {
1190        j1 = bci[ii];
1191        if (nPm[j1]!=NULL)
1192        {
1193          if (pLmDivisibleByNoComp(nPm[j1],p))
1194          {
1195            pDelete(&p);
1196            break;
1197          }
1198          else if (pLmDivisibleByNoComp(p,nPm[j1]))
1199          {
1200            pDelete(&(nPm[j1]));
1201            //break;
1202          }
1203        }
1204        ii++;
1205        if (ii>=pos) break;
1206      }
1207      if (p!=NULL)
1208      {
1209        nPm[jj] = p;
1210      }
1211    }
1212    for (i=first;i<pos;i++)
1213    {
1214      ii = bci[i];
1215      if (nPm[ii]!=NULL)
1216      {
1217        if (l>=(*syzstr->Tl)[index])
1218        {
1219          temp = (SSet)omAlloc0(((*syzstr->Tl)[index]+16)*sizeof(SObject));
1220          for (ll=0;ll<(*syzstr->Tl)[index];ll++)
1221          {
1222            temp[ll].p = (syzstr->resPairs[index])[ll].p;
1223            temp[ll].p1 = (syzstr->resPairs[index])[ll].p1;
1224            temp[ll].p2 = (syzstr->resPairs[index])[ll].p2;
1225            temp[ll].syz = (syzstr->resPairs[index])[ll].syz;
1226            temp[ll].lcm = (syzstr->resPairs[index])[ll].lcm;
1227            temp[ll].ind1 = (syzstr->resPairs[index])[ll].ind1;
1228            temp[ll].ind2 = (syzstr->resPairs[index])[ll].ind2;
1229            temp[ll].syzind = (syzstr->resPairs[index])[ll].syzind;
1230            temp[ll].order = (syzstr->resPairs[index])[ll].order;
1231            temp[ll].isNotMinimal = (syzstr->resPairs[index])[ll].isNotMinimal;
1232          }
1233          if (syzstr->resPairs[index] != NULL) // OB: ????
1234            omFreeSize((ADDRESS)syzstr->resPairs[index],(*syzstr->Tl)[index]*sizeof(SObject));
1235          (*syzstr->Tl)[index] += 16;
1236          syzstr->resPairs[index] = temp;
1237        }
1238        tso.lcm = p = nPm[ii];
1239        nPm[ii] = NULL;
1240        tso.order = pTotaldegree(p);
1241        if ((syzstr->cw!=NULL) && (index>0) && (pGetComp(q)>0))
1242        {
1243          int ii=index-1,jj=pGetComp(q);
1244          while (ii>0)
1245          {
1246            jj = pGetComp(syzstr->res[ii]->m[jj-1]);
1247            ii--;
1248          }
1249          tso.order += (*syzstr->cw)[jj-1];
1250        }
1251        tso.p1 = rs[ii];
1252        tso.p2 = q;
1253        tso.ind1 = ii;
1254        tso.ind2 = j;
1255        tso.syzind = -1;
1256        tso.isNotMinimal = NULL;
1257        tso.p = NULL;
1258        tso.syz = NULL;
1259        syEnterPair(syzstr->resPairs[index],&tso,&l,index);
1260      }
1261    }
1262  }
1263  idDelete(&nP);
1264}
1265
1266static SSet syChosePairsPutIn(syStrategy syzstr, int *index,
1267               int *howmuch, int * actdeg, int an, int en)
1268{
1269  int newdeg=*actdeg,newindex=-1,i,t,sldeg;
1270  poly p;
1271  SSet result;
1272  SRes resPairs=syzstr->resPairs;
1273
1274  if (an>syzstr->length) return NULL;
1275  if (en>syzstr->length) en=syzstr->length;
1276  while (*index<en)
1277  {
1278    if (resPairs[*index]!=NULL)
1279    {
1280      sldeg = (*actdeg)+*index;
1281      i = 0;
1282      if (*index!=0)
1283      {
1284        while ((i<(*syzstr->Tl)[*index]))
1285        {
1286          if ((resPairs[*index])[i].lcm!=NULL)
1287          {
1288            if ((resPairs[*index])[i].order == sldeg)
1289            {
1290              result = &(resPairs[*index])[i];
1291              *howmuch =1;
1292              i++;
1293              while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1294                      && ((resPairs[*index])[i].order == sldeg))
1295              {
1296                i++;
1297                (*howmuch)++;
1298              }
1299              return result;
1300            }
1301          }
1302          i++;
1303        }
1304      }
1305      else
1306      {
1307        while ((i<(*syzstr->Tl)[*index]))
1308        {
1309          if ((resPairs[*index])[i].syz!=NULL)
1310          {
1311            if ((resPairs[*index])[i].order == sldeg)
1312            {
1313              result = &(resPairs[*index])[i];
1314              (*howmuch) =1;
1315              i++;
1316              while ((i<(*syzstr->Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1317                      && ((resPairs[*index])[i].order == *actdeg))
1318              {
1319                i++;
1320                (*howmuch)++;
1321              }
1322              return result;
1323            }
1324          }
1325          i++;
1326        }
1327      }
1328    }
1329    (*index)++;
1330  }
1331  *index = an;
1332  //if (TEST_OPT_PROT) Print("(Euler:%d)",euler);
1333  while (*index<en)
1334  {
1335    if (resPairs[*index]!=NULL)
1336    {
1337      i = 0;
1338      while ((i<(*syzstr->Tl)[*index]))
1339      {
1340        t = *actdeg+*index;
1341        if (((resPairs[*index])[i].lcm!=NULL) ||
1342              ((resPairs[*index])[i].syz!=NULL))
1343        {
1344          if ((resPairs[*index])[i].order > t)
1345            t = (resPairs[*index])[i].order;
1346        }
1347        if ((t>*actdeg+*index) && ((newdeg==*actdeg) || (t<newdeg+*index)))
1348        {
1349          newdeg = t-*index;
1350          newindex = *index;
1351          break;
1352        }
1353        i++;
1354      }
1355    }
1356    (*index)++;
1357  }
1358  if (newdeg>*actdeg)
1359  {
1360    *actdeg = newdeg;
1361    *index = newindex;
1362    return syChosePairsPutIn(syzstr,index,howmuch,actdeg,an,en);
1363  }
1364  else return NULL;
1365}
1366
1367/*3
1368* FOR THE HOMOGENEOUS CASE ONLY!
1369* looks through the pair set and the given module for
1370* remaining pairs or generators to consider
1371* returns a pointer to the first pair and the number of them in the given module
1372* works with slanted degree (i.e. deg=realdeg-index)
1373*/
1374SSet syChosePairs(syStrategy syzstr, int *index, int *howmuch, int * actdeg)
1375{
1376  return syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,syzstr->length);
1377}
1378
1379/*3
1380* FOR THE INHOMOGENEOUS CASE ONLY!
1381* looks through the pair set and the given module for
1382* remaining pairs or generators to consider
1383* returns a pointer to the first pair and the number of them in the given module
1384* works with slanted degree (i.e. deg=realdeg-index)
1385* looks first through the 0 and 1 module then through the other
1386*/
1387static SSet syChosePairsIH(syStrategy syzstr, int *index,
1388               int *howmuch, int * actdeg, int mindeg)
1389{
1390  SSet result=NULL;
1391
1392  result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,0,2);
1393  if (result == NULL)
1394  {
1395    *actdeg = mindeg;
1396    result = syChosePairsPutIn(syzstr,index,howmuch,actdeg,2,syzstr->length);
1397  }
1398  return result;
1399}
1400
1401/*3
1402* looks through the pair set and the given module for
1403* remaining pairs or generators to consider
1404* returns a pointer to the first pair and the number of them in the given module
1405* works deg by deg
1406*/
1407/*
1408*static SSet syChosePairs1(SRes resPairs,intvec * Tl, int *index, int *howmuch,
1409*                   int length,int * actdeg)
1410*{
1411*  int newdeg=*actdeg,newindex=-1,i,t;
1412*  SSet result;
1413*
1414*  while (*index>=0)
1415*  {
1416*    if (resPairs[*index]!=NULL)
1417*    {
1418*      i = 0;
1419*      if (*index!=0)
1420*      {
1421*        while ((i<(*Tl)[*index]))
1422*        {
1423*          if ((resPairs[*index])[i].lcm!=NULL)
1424*          {
1425*            if (pGetOrder((resPairs[*index])[i].lcm) == *actdeg)
1426*            {
1427*              result = &(resPairs[*index])[i];
1428*              *howmuch =1;
1429*              i++;
1430*              while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].lcm!=NULL)
1431*                      && (pGetOrder((resPairs[*index])[i].lcm) == *actdeg))
1432*              {
1433*                i++;
1434*                (*howmuch)++;
1435*              }
1436*              return result;
1437*            }
1438*          }
1439*          i++;
1440*        }
1441*      }
1442*      else
1443*      {
1444*        while ((i<(*Tl)[*index]))
1445*        {
1446*          if ((resPairs[*index])[i].syz!=NULL)
1447*          {
1448*            if ((resPairs[*index])[i].order == *actdeg)
1449*            {
1450*              result = &(resPairs[*index])[i];
1451*              (*howmuch) =1;
1452*              i++;
1453*              while ((i<(*Tl)[*index]) && ((resPairs[*index])[i].syz!=NULL)
1454*                      && ((resPairs[*index])[i].order == *actdeg))
1455*              {
1456*                i++;
1457*                (*howmuch)++;
1458*              }
1459*              return result;
1460*            }
1461*          }
1462*          i++;
1463*        }
1464*      }
1465*    }
1466*    (*index)--;
1467*  }
1468*  *index = length-1;
1469*  while (*index>=0)
1470*  {
1471*    if (resPairs[*index]!=NULL)
1472*    {
1473*      i = 0;
1474*      while ((i<(*Tl)[*index]))
1475*      {
1476*        t = *actdeg;
1477*        if ((resPairs[*index])[i].lcm!=NULL)
1478*        {
1479*          if (pGetOrder((resPairs[*index])[i].lcm) > *actdeg)
1480*            t = pGetOrder((resPairs[*index])[i].lcm);
1481*        }
1482*        else if ((resPairs[*index])[i].syz!=NULL)
1483*        {
1484*          if ((resPairs[*index])[i].order > *actdeg)
1485*            t = (resPairs[*index])[i].order;
1486*        }
1487*        if ((t>*actdeg) && ((newdeg==*actdeg) || (t<newdeg)))
1488*        {
1489*          newdeg = t;
1490*          newindex = *index;
1491*          break;
1492*        }
1493*        i++;
1494*      }
1495*    }
1496*    (*index)--;
1497*  }
1498*  if (newdeg>*actdeg)
1499*  {
1500*    *actdeg = newdeg;
1501*    *index = newindex;
1502*    return syChosePairs1(resPairs,Tl,index,howmuch,length,actdeg);
1503*  }
1504*  else return NULL;
1505*}
1506*/
1507/*3
1508* statistics of the resolution
1509*/
1510static void syStatistics(resolvente res,int length)
1511{
1512  int i,j=1,k;
1513  long deg = 0;
1514
1515  PrintLn();
1516  while ((j<length) && (res[j]!=NULL))
1517  {
1518    Print("In module %d: \n",j);
1519    k = 0;
1520    while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL))
1521    {
1522      i = 1;
1523      deg = pGetOrder(res[j]->m[k]);
1524      k++;
1525      while ((k<IDELEMS(res[j])) && (res[j]->m[k]!=NULL) &&
1526              (pGetOrder(res[j]->m[k])==deg))
1527      {
1528        i++;
1529        k++;
1530      }
1531      Print("%d elements of degree %ld\n",i,deg);
1532    }
1533    j++;
1534  }
1535}
1536
1537/*3
1538* initialize a module
1539*/
1540int syInitSyzMod(syStrategy syzstr, int index, int init)
1541{
1542  int result;
1543
1544  if (syzstr->res[index]==NULL)
1545  {
1546    syzstr->res[index] = idInit(init-1,1);
1547    syzstr->truecomponents[index] = (int*)omAlloc0(init*sizeof(int));
1548    syzstr->ShiftedComponents[index] = (long*)omAlloc0(init*sizeof(long));
1549    if (index==0)
1550    {
1551      for (int i=0;i<init;i++)
1552      {
1553        syzstr->truecomponents[0][i] = i;
1554        syzstr->ShiftedComponents[0][i] = (i)*SYZ_SHIFT_BASE;
1555      }
1556    }
1557    syzstr->backcomponents[index] = (int*)omAlloc0(init*sizeof(int));
1558    syzstr->Howmuch[index] = (int*)omAlloc0(init*sizeof(int));
1559    syzstr->Firstelem[index] = (int*)omAlloc0(init*sizeof(int));
1560    syzstr->elemLength[index] = (int*)omAlloc0(init*sizeof(int));
1561    syzstr->orderedRes[index] = idInit(init-1,1);
1562    syzstr->sev[index] = (unsigned long*) omAlloc0(init*sizeof(unsigned long));
1563    result = 0;
1564  }
1565  else
1566  {
1567    result = IDELEMS(syzstr->res[index]);
1568    while ((result>0) && (syzstr->res[index]->m[result-1]==NULL)) result--;
1569  }
1570  return result;
1571}
1572
1573/*3
1574* deletes a resolution
1575*/
1576void syKillComputation(syStrategy syzstr, ring r)
1577{
1578  if (syzstr->references>0)
1579  {
1580    (syzstr->references)--;
1581  }
1582  else
1583  {
1584    int i,j;
1585    if (syzstr->minres!=NULL)
1586    {
1587      for (i=0;i<syzstr->length;i++)
1588      {
1589        if (syzstr->minres[i]!=NULL)
1590        {
1591          for (j=0;j<IDELEMS(syzstr->minres[i]);j++)
1592          {
1593            if (syzstr->minres[i]->m[j]!=NULL)
1594              p_Delete(&(syzstr->minres[i]->m[j]),r);
1595          }
1596        }
1597        id_Delete(&(syzstr->minres[i]),r);
1598      }
1599      omFreeSize((ADDRESS)syzstr->minres,(syzstr->length+1)*sizeof(ideal));
1600    }
1601    if (syzstr->fullres!=NULL)
1602    {
1603      for (i=0;i<syzstr->length;i++)
1604      {
1605        if (syzstr->fullres[i]!=NULL)
1606        {
1607          for (j=0;j<IDELEMS(syzstr->fullres[i]);j++)
1608          {
1609            if (syzstr->fullres[i]->m[j]!=NULL)
1610              p_Delete(&(syzstr->fullres[i]->m[j]),r);
1611          }
1612        }
1613        id_Delete(&(syzstr->fullres[i]),r);
1614      }
1615      omFreeSize((ADDRESS)syzstr->fullres,(syzstr->length+1)*sizeof(ideal));
1616    }
1617    if (syzstr->weights!=0)
1618    {
1619      for (i=0;i<syzstr->length;i++)
1620      {
1621        if (syzstr->weights[i]!=NULL)
1622        {
1623          delete syzstr->weights[i];
1624        }
1625      }
1626      omFreeSize((ADDRESS)syzstr->weights,syzstr->length*sizeof(intvec*));
1627    }
1628
1629    ring sr=syzstr->syRing;
1630    if (sr==NULL) sr=r;
1631
1632    if (syzstr->resPairs!=NULL)
1633    {
1634      for (i=0;i<syzstr->length;i++)
1635      {
1636        for (j=0;j<(*syzstr->Tl)[i];j++)
1637        {
1638          if ((syzstr->resPairs[i])[j].lcm!=NULL)
1639            p_Delete(&((syzstr->resPairs[i])[j].lcm),sr);
1640          if ((i>0) && ((syzstr->resPairs[i])[j].syz!=NULL))
1641            p_Delete(&((syzstr->resPairs[i])[j].syz),sr);
1642        }
1643        if (syzstr->orderedRes[i]!=NULL)
1644        {
1645          for (j=0;j<IDELEMS(syzstr->orderedRes[i]);j++)
1646          {
1647            syzstr->orderedRes[i]->m[j] = NULL;
1648          }
1649        }
1650        id_Delete(&(syzstr->orderedRes[i]),sr);
1651        if (syzstr->truecomponents[i]!=NULL)
1652        {
1653          omFreeSize((ADDRESS)syzstr->truecomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1654          syzstr->truecomponents[i]=NULL;
1655          omFreeSize((ADDRESS)syzstr->ShiftedComponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(long));
1656          syzstr->ShiftedComponents[i]=NULL;
1657        }
1658        if (syzstr->backcomponents[i]!=NULL)
1659        {
1660          omFreeSize((ADDRESS)syzstr->backcomponents[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1661          syzstr->backcomponents[i]=NULL;
1662        }
1663        if (syzstr->Howmuch[i]!=NULL)
1664        {
1665          omFreeSize((ADDRESS)syzstr->Howmuch[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1666          syzstr->Howmuch[i]=NULL;
1667        }
1668        if (syzstr->Firstelem[i]!=NULL)
1669        {
1670          omFreeSize((ADDRESS)syzstr->Firstelem[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1671          syzstr->Firstelem[i]=NULL;
1672        }
1673        if (syzstr->elemLength[i]!=NULL)
1674        {
1675          omFreeSize((ADDRESS)syzstr->elemLength[i],(IDELEMS(syzstr->res[i])+1)*sizeof(int));
1676          syzstr->elemLength[i]=NULL;
1677        }
1678        if (syzstr->res[i]!=NULL)
1679        {
1680          for (j=0;j<IDELEMS(syzstr->res[i]);j++)
1681          {
1682            if (syzstr->res[i]->m[j]!=NULL)
1683              p_Delete(&(syzstr->res[i]->m[j]),sr);
1684          }
1685        }
1686        if ((syzstr->hilb_coeffs!=NULL)
1687        && (syzstr->hilb_coeffs[i]!=NULL))
1688          delete syzstr->hilb_coeffs[i];
1689        if (syzstr->sev[i] != NULL)
1690          omFreeSize((ADDRESS)syzstr->sev[i], (IDELEMS(syzstr->res[i])+1)*sizeof(unsigned long));
1691        id_Delete(&(syzstr->res[i]),sr);
1692        if (syzstr->resPairs[i] != NULL) // OB: ????
1693          omFreeSize((ADDRESS)syzstr->resPairs[i],(*syzstr->Tl)[i]*sizeof(SObject));
1694      }
1695      omFreeSize((ADDRESS)syzstr->resPairs,syzstr->length*sizeof(SObject*));
1696      omFreeSize((ADDRESS)syzstr->res,(syzstr->length+1)*sizeof(ideal));
1697      omFreeSize((ADDRESS)syzstr->orderedRes,(syzstr->length+1)*sizeof(ideal));
1698      omFreeSize((ADDRESS)syzstr->elemLength,(syzstr->length+1)*sizeof(int*));
1699      omFreeSize((ADDRESS)syzstr->truecomponents,(syzstr->length+1)*sizeof(int*));
1700      omFreeSize((ADDRESS)syzstr->ShiftedComponents,(syzstr->length+1)*sizeof(long*));
1701      if (syzstr->sev != NULL)
1702        omFreeSize(((ADDRESS)syzstr->sev), (syzstr->length+1)*sizeof(unsigned long*));
1703      omFreeSize((ADDRESS)syzstr->backcomponents,(syzstr->length+1)*sizeof(int*));
1704      omFreeSize((ADDRESS)syzstr->Howmuch,(syzstr->length+1)*sizeof(int*));
1705      omFreeSize((ADDRESS)syzstr->Firstelem,(syzstr->length+1)*sizeof(int*));
1706      if (syzstr->hilb_coeffs!=NULL)
1707        omFreeSize((ADDRESS)syzstr->hilb_coeffs,(syzstr->length+1)*sizeof(intvec*));
1708    }
1709    if (syzstr->cw!=NULL)
1710      delete syzstr->cw;
1711    if (syzstr->betti!=NULL)
1712      delete syzstr->betti;
1713    if (syzstr->resolution!=NULL)
1714      delete syzstr->resolution;
1715    if (syzstr->Tl!=NULL)
1716      delete syzstr->Tl;
1717    if ((syzstr->syRing != NULL) && (syzstr->syRing != r))
1718    {
1719      rKill(syzstr->syRing);
1720    }
1721    omFreeSize((ADDRESS)syzstr, sizeof(ssyStrategy));
1722  }
1723}
1724
1725/*2
1726* divides out the weight monomials (given by the Schreyer-ordering)
1727* from the LaScala-resolution
1728*/
1729resolvente syReorder(resolvente res,int length,
1730        syStrategy syzstr,BOOLEAN toCopy,resolvente totake)
1731{
1732  int i,j,l;
1733  poly p,q,tq;
1734  polyset ri1;
1735  resolvente fullres;
1736  ring origR=syzstr->syRing;
1737  fullres = (resolvente)omAlloc0((length+1)*sizeof(ideal));
1738  if (totake==NULL)
1739    totake = res;
1740  for (i=length-1;i>0;i--)
1741  {
1742    if (res[i]!=NULL)
1743    {
1744      if (i>1)
1745      {
1746        j = IDELEMS(res[i-1]);
1747        while ((j>0) && (res[i-1]->m[j-1]==NULL)) j--;
1748        fullres[i-1] = idInit(IDELEMS(res[i]),j);
1749        ri1 = totake[i-1]->m;
1750        for (j=IDELEMS(res[i])-1;j>=0;j--)
1751        {
1752          p = res[i]->m[j];
1753          q = NULL;
1754          while (p!=NULL)
1755          {
1756            if (toCopy)
1757            {
1758              if (origR!=NULL)
1759                tq = prHeadR(p,origR);
1760              else
1761                tq = pHead(p);
1762              pIter(p);
1763            }
1764            else
1765            {
1766              res[i]->m[j] = NULL;
1767              if (origR!=NULL)
1768              {
1769                poly pp=p;
1770                pIter(p);
1771                pNext(pp)=NULL;
1772                tq = prMoveR(pp, origR);
1773              }
1774              else
1775              {
1776                tq = p;
1777                pIter(p);
1778                pNext(tq) = NULL;
1779              }
1780            }
1781//            pWrite(tq);
1782            pTest(tq);
1783            for (l=pVariables;l>0;l--)
1784            {
1785              if (origR!=NULL)
1786                pSubExp(tq,l, p_GetExp(ri1[pGetComp(tq)-1],l,origR));
1787              else
1788                pSubExp(tq,l, pGetExp(ri1[pGetComp(tq)-1],l));
1789            }
1790            pSetm(tq);
1791            pTest(tq);
1792            q = pAdd(q,tq);
1793            pTest(q);
1794          }
1795          fullres[i-1]->m[j] = q;
1796        }
1797      }
1798      else
1799      {
1800        if (origR!=NULL)
1801        {
1802          fullres[i-1] = idInit(IDELEMS(res[i]),res[i]->rank);
1803          for (j=IDELEMS(res[i])-1;j>=0;j--)
1804          {
1805            if (toCopy)
1806              fullres[i-1]->m[j] = prCopyR(res[i]->m[j], origR);
1807            else
1808            {
1809              fullres[i-1]->m[j] = prMoveR(res[i]->m[j], origR);
1810              res[i]->m[j] = NULL;
1811            }
1812          }
1813        }
1814        else
1815        {
1816          if (toCopy)
1817            fullres[i-1] = idCopy(res[i]);
1818          else
1819          {
1820            fullres[i-1] = res[i];
1821            res[i] = NULL;
1822          }
1823        }
1824        for (j=IDELEMS(fullres[i-1])-1;j>=0;j--)
1825          fullres[i-1]->m[j] = pSortCompCorrect(fullres[i-1]->m[j]);
1826      }
1827      if (!toCopy)
1828      {
1829        if (res[i]!=NULL) idDelete(&res[i]);
1830      }
1831    }
1832  }
1833  if (!toCopy)
1834    omFreeSize((ADDRESS)res,(length+1)*sizeof(ideal));
1835  //syzstr->length = length;
1836  return fullres;
1837}
1838
1839/*3
1840* read out the Betti numbers from resolution
1841* (if not LaScala calls the traditional Betti procedure)
1842*/
1843intvec * syBettiOfComputation(syStrategy syzstr, BOOLEAN minim,int * row_shift,
1844                              intvec* weights)
1845{
1846  int dummy;
1847  BOOLEAN std_weights=TRUE;
1848  if ((weights!=NULL)
1849  && (syzstr->betti!=NULL)
1850  && (syzstr->weights!=NULL) && (syzstr->weights[0]!=NULL))
1851  {
1852    int i;
1853    for(i=weights->length()-1; i>=0; i--)
1854    {
1855      //Print("test %d: %d - %d\n",i,(*weights)[i], (*(syzstr->weights[0]))[i]);
1856      if ((*weights)[i]!=(*(syzstr->weights[0]))[i])
1857      {
1858        std_weights=FALSE;
1859        break;
1860      }
1861    }
1862  }
1863  if ((syzstr->betti!=NULL)
1864  && (std_weights))
1865  {
1866    if (minim || (syzstr->resPairs!=NULL))
1867      return ivCopy(syzstr->betti);
1868  }
1869  if ((syzstr->fullres==NULL) && (syzstr->minres==NULL))
1870  {
1871     if (syzstr->hilb_coeffs==NULL)
1872     {
1873        syzstr->fullres = syReorder(syzstr->res,syzstr->length,syzstr);
1874     }
1875     else
1876     {
1877        syzstr->minres = syReorder(syzstr->orderedRes,syzstr->length,syzstr);
1878        syKillEmptyEntres(syzstr->minres,syzstr->length);
1879     }
1880   }
1881  intvec *result=NULL;
1882  if (syzstr->fullres!=NULL)
1883    result = syBetti(syzstr->fullres,syzstr->length,&dummy,weights,minim,row_shift);
1884  else
1885    result = syBetti(syzstr->minres,syzstr->length,&dummy,weights,minim,row_shift);
1886  if ((result!=NULL)
1887  && ((minim) || (syzstr->resPairs!=NULL))
1888  && std_weights)
1889  {
1890    syzstr->betti = ivCopy(result);
1891  }
1892  return result;
1893}
1894
1895/*3
1896* computes the real length of the resolution
1897*/
1898int sySize(syStrategy syzstr)
1899{
1900  resolvente r=syzstr->res;
1901  if (r==NULL)
1902    r = syzstr->fullres;
1903  if (r==NULL)
1904    r = syzstr->minres;
1905  if (r==NULL)
1906  {
1907    WerrorS("No resolution found");
1908    return 0;
1909  }
1910  int i=syzstr->length;
1911  while ((i>0) && (r[i-1]==NULL)) i--;
1912  return i;
1913}
1914
1915/*3
1916* computes the cohomological dimension of res[1]
1917*/
1918int syDim(syStrategy syzstr)
1919{
1920  int i,j=-1,l;
1921  if (syzstr->resPairs!=NULL)
1922  {
1923    SRes rP=syzstr->resPairs;
1924
1925    l = syzstr->length;
1926    while ((l>0) && (rP[l-1]==NULL)) l--;
1927    if (l==0) return -1;
1928    l--;
1929    while (l>=0)
1930    {
1931      i = 0;
1932      while ((i<(*syzstr->Tl)[l]) &&
1933        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
1934        (rP[l][i].isNotMinimal!=NULL))
1935      {
1936        i++;
1937      }
1938      if ((i<(*syzstr->Tl)[l]) &&
1939        ((rP[l][i].lcm!=NULL) || (rP[l][i].syz!=NULL)) &&
1940        (rP[l][i].isNotMinimal==NULL))
1941        return l;
1942      l--;
1943    }
1944    return l;
1945  }
1946  else
1947    return sySize(syzstr);
1948}
1949
1950/*3
1951* copies the resolution (by increment the reference counter)
1952*/
1953syStrategy syCopy(syStrategy syzstr)
1954{
1955  syStrategy result=syzstr;
1956  (result->references)++;
1957  return result;
1958}
1959
1960/*2
1961* local print procedure used in syPrint
1962*/
1963static void syPrintEmptySpaces(int i)
1964{
1965  if (i!=0)
1966  {
1967    PrintS(" ");
1968    syPrintEmptySpaces(i/10);
1969  }
1970}
1971
1972/*2
1973* local print procedure used in syPrint
1974*/
1975static void syPrintEmptySpaces1(int i)
1976{
1977  if (i!=0)
1978  {
1979    PrintS(" ");
1980    syPrintEmptySpaces1(i-1);
1981  }
1982}
1983
1984/*2
1985* local print procedure used in syPrint
1986*/
1987static int syLengthInt(int i)
1988{
1989  int j=0;
1990
1991  if (i==0) return 1;
1992  while (i!=0)
1993  {
1994    j++;
1995    i = i/10;
1996  }
1997  return j;
1998}
1999
2000/*3
2001* prints the resolution as sequence of free modules
2002*/
2003void syPrint(syStrategy syzstr)
2004{
2005  if ((syzstr->resPairs==NULL) && (syzstr->fullres==NULL)
2006     && (syzstr->minres==NULL))
2007  {
2008    PrintS("No resolution defined\n");
2009    return;
2010  }
2011  int l=0;
2012  if (syzstr->resolution==NULL)
2013  {
2014    int j;
2015    if (syzstr->resPairs!=NULL)
2016    {
2017      syzstr->resolution = new intvec(syzstr->length+1);
2018      SRes rP=syzstr->resPairs;
2019      assume(idRankFreeModule(syzstr->res[1],
2020                                 (syzstr->syRing != NULL ? syzstr->syRing : currRing))==syzstr->res[1]->rank);
2021      (*syzstr->resolution)[0] = syzstr->res[1]->rank;
2022      while ((l<syzstr->length) && (rP[l]!=NULL))
2023      {
2024        j=0;
2025        while ((j<(*syzstr->Tl)[l]) &&
2026          ((rP[l][j].lcm!=NULL) || (rP[l][j].syz!=NULL)))
2027        {
2028          if (rP[l][j].isNotMinimal==NULL)
2029            ((*syzstr->resolution)[l+1])++;
2030          j++;
2031        }
2032        l++;
2033      }
2034    }
2035    else
2036    {
2037      resolvente rr;
2038      syzstr->resolution = new intvec(syzstr->length+2);
2039      if (syzstr->minres!=NULL)
2040        rr = syzstr->minres;
2041      else
2042        rr = syzstr->fullres;
2043      (*syzstr->resolution)[0]
2044        = si_max(1,(int)idRankFreeModule(rr[0],
2045                                 (syzstr->syRing != NULL ? syzstr->syRing : currRing)));
2046      while ((l<syzstr->length) && (rr[l]!=NULL))
2047      {
2048        j = IDELEMS(rr[l]);
2049        while ((j>0) && (rr[l]->m[j-1]==NULL)) j--;
2050        ((*syzstr->resolution)[l+1]) = j;
2051        l++;
2052      }
2053    }
2054  }
2055  const char *sn=currRingHdl->id;
2056  int sl=strlen(sn);
2057  syPrintEmptySpaces1(sl);
2058  l = 0;
2059  loop
2060  {
2061    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2062      break;
2063    Print("%d",(*syzstr->resolution)[l]);
2064    syPrintEmptySpaces1(sl+5);
2065    l++;
2066  }
2067  PrintLn();
2068  l = 0;
2069  loop
2070  {
2071    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2072      break;
2073    PrintS(sn);
2074    if (((l+1)>=syzstr->resolution->length()) || ((*syzstr->resolution)[(l+1)]==0))
2075      break;
2076    PrintS(" <-- ");
2077    syPrintEmptySpaces((*syzstr->resolution)[l]);
2078    l++;
2079  }
2080  PrintLn();
2081  PrintLn();
2082  l = 0;
2083  loop
2084  {
2085    if ((l>=syzstr->resolution->length()) || ((*syzstr->resolution)[l]==0))
2086      break;
2087    Print("%d",l);
2088    syPrintEmptySpaces1(sl+5+syLengthInt((*syzstr->resolution)[l])-
2089                         syLengthInt(l));
2090    l++;
2091  }
2092  PrintLn();
2093  if (syzstr->minres==NULL)
2094  {
2095    PrintS("resolution not minimized yet");
2096    PrintLn();
2097  }
2098}
2099
2100/*2
2101* deleting all monomials the component of which correspond
2102* to non-minimal generators
2103*/
2104static poly syStripOut(poly p,intvec * toStrip)
2105{
2106  if (toStrip==NULL) return p;
2107  poly pp=p;
2108
2109  while ((pp!=NULL) && ((*toStrip)[pGetComp(pp)]!=0))
2110    pLmDelete(&pp);
2111  p = pp;
2112  if (pp!=NULL)
2113  {
2114    while (pNext(pp)!=NULL)
2115    {
2116      if ((*toStrip)[pGetComp(pNext(pp))]!=0)
2117        pLmDelete(&pNext(pp));
2118      else
2119        pIter(pp);
2120    }
2121  }
2122  return p;
2123}
2124
2125/*2
2126* copies only those monomials the component of which correspond
2127* to minimal generators
2128*/
2129static poly syStripOutCopy(poly p,intvec * toStrip)
2130{
2131  if (toStrip==NULL) return pCopy(p);
2132  poly result=NULL,pp;
2133
2134  while (p!=NULL)
2135  {
2136    if ((*toStrip)[pGetComp(p)]==0)
2137    {
2138      if (result==NULL)
2139      {
2140        result = pp = pHead(p);
2141      }
2142      else
2143      {
2144        pNext(pp) = pHead(p);
2145        pIter(pp);
2146      }
2147    }
2148    pIter(p);
2149  }
2150  return result;
2151}
2152
2153/*2
2154* minimizes toMin
2155*/
2156static poly syMinimizeP(int toMin,syStrategy syzstr,intvec * ordn,int index,
2157                        intvec * toStrip)
2158{
2159  int ii=0,i,j,tc;
2160  poly p,pp,q=NULL,tq,pisN;
2161  SSet sPairs=syzstr->resPairs[index];
2162  poly tempStripped=NULL;
2163
2164  //pp=pCopy(syzstr->res[index+1]->m[toMin]);
2165  pp = syStripOutCopy(syzstr->res[index+1]->m[toMin],toStrip);
2166  while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) &&
2167             (sPairs[(*ordn)[ii]].syzind!=toMin))
2168  {
2169    ii++;
2170  }
2171  while (ii>=0)
2172  {
2173    i = (*ordn)[ii];
2174    if (sPairs[i].isNotMinimal!=NULL)
2175    {
2176      tempStripped =
2177        syStripOutCopy(syzstr->res[index+1]->m[sPairs[i].syzind],toStrip);
2178      pisN = sPairs[i].isNotMinimal;
2179      tc = pGetComp(pisN);
2180      p = pp;
2181      while (p!=NULL)
2182      {
2183        if (pGetComp(p)==tc)
2184        {
2185          tq = pInit();
2186          for(j=pVariables; j>0; j--)
2187            pSetExp(tq,j, pGetExp(p,j)-pGetExp(pisN,j));
2188          pSetComp(tq, 0);
2189          pSetCoeff0(tq,nDiv(pGetCoeff(p),pGetCoeff(pisN)));
2190          pGetCoeff(tq) = nNeg(pGetCoeff(tq));
2191          pSetm(tq);
2192          q = pAdd(q,pMult_mm(pCopy(tempStripped),tq));
2193          pDelete(&tq);
2194        }
2195        pIter(p);
2196      }
2197      if (q!=NULL)
2198      {
2199        pp = pAdd(pp,q);
2200        q = NULL;
2201      }
2202      pDelete(&tempStripped);
2203    }
2204    ii--;
2205  }
2206  return pp;
2207}
2208
2209/*2
2210* minimizes toMin
2211*/
2212static poly syMinimizeP1(int toMin,syStrategy syzstr,intvec * ordn,int index,
2213                        intvec * toStrip)
2214{
2215  int ii=0,i,j,tc,lp,ltS=-1;
2216  poly p,mp=NULL,pp,q=NULL,tq,pisN;
2217  SSet sPairs=syzstr->resPairs[index];
2218  poly tempStripped=NULL;
2219
2220  pp = syStripOutCopy(syzstr->res[index+1]->m[toMin],toStrip);
2221  kBucketInit(syzstr->bucket,pp,-1);
2222  while ((ii<ordn->length()) && ((*ordn)[ii]!=-1) &&
2223             (sPairs[(*ordn)[ii]].syzind!=toMin))
2224  {
2225    ii++;
2226  }
2227  while (ii>=0)
2228  {
2229    i = (*ordn)[ii];
2230    if (sPairs[i].isNotMinimal!=NULL)
2231    {
2232      tempStripped =
2233        syStripOutCopy(syzstr->res[index+1]->m[sPairs[i].syzind],toStrip);
2234      tc = pGetComp(sPairs[i].isNotMinimal);
2235      //p = pTakeOutComp1(&tempStripped,tc);
2236      int lu;
2237      pTakeOutComp(&tempStripped,tc,&p,&lu);
2238      kBucketTakeOutComp(syzstr->bucket,tc,&mp,&lp);
2239      mp = pDivideM(mp,p);
2240      while (mp!=NULL)
2241      {
2242        p = pNext(mp);
2243        pNext(mp) = NULL;
2244        ltS = -1;
2245        kBucket_Minus_m_Mult_p(syzstr->bucket,mp,tempStripped,&ltS);
2246        mp = p;
2247      }
2248      pDelete(&mp);
2249      pDelete(&tempStripped);
2250    }
2251    ii--;
2252  }
2253  kBucketClear(syzstr->bucket,&pp,&lp);
2254  return pp;
2255}
2256
2257/*2
2258* deletes empty components after minimization
2259*/
2260void syKillEmptyEntres(resolvente res,int length)
2261{
2262  int i,j,jj,k,rj;
2263  intvec * changes;
2264  poly p;
2265  ideal ri;
2266
2267  for (i=0;i<length;i++)
2268  {
2269    ri = res[i];
2270    if (ri!=NULL)
2271    {
2272      rj = IDELEMS(ri);
2273      changes = new intvec(rj+1,1,-1);
2274      while ((rj>0) && (ri->m[rj-1]==NULL)) rj--;
2275      j = k = 0;
2276      while (j+k<rj)
2277      {
2278        if (ri->m[j+k]!=NULL)
2279        {
2280          ri->m[j] = ri->m[j+k];
2281          (*changes)[j+k+1] = j+1;
2282          j++;
2283        }
2284        else
2285        {
2286          k++;
2287        }
2288      }
2289      for (jj=j;jj<rj;jj++)
2290        ri->m[jj] = NULL;
2291      if (res[i+1]!=NULL)
2292      {
2293        ri = res[i+1];
2294        for (j=IDELEMS(ri)-1;j>=0;j--)
2295        {
2296          p = ri->m[j];
2297          while (p!=NULL)
2298          {
2299            pSetComp(p,(*changes)[pGetComp(p)]);
2300            pSetm(p);
2301            pIter(p);
2302          }
2303        }
2304      }
2305      delete changes;
2306    }
2307  }
2308}
2309
2310/*2
2311* determines the components for minimization
2312*/
2313static intvec * syToStrip(syStrategy syzstr, int index)
2314{
2315  intvec * result=NULL;
2316
2317  if ((syzstr->resPairs[index-1]!=NULL) && (!idIs0(syzstr->res[index])))
2318  {
2319    result=new intvec(IDELEMS(syzstr->res[index])+1);
2320    for (int i=(*syzstr->Tl)[index-1]-1;i>=0;i--)
2321    {
2322      if (syzstr->resPairs[index-1][i].isNotMinimal!=NULL)
2323      {
2324        (*result)[syzstr->resPairs[index-1][i].syzind+1] = 1;
2325      }
2326    }
2327  }
2328  return result;
2329}
2330
2331/*2
2332* re-computes the order of pairs during the algorithm
2333* this ensures to procede with a triangular matrix
2334*/
2335static intvec * syOrdPairs(SSet sPairs, int length)
2336{
2337  intvec * result=new intvec(length,1,-1);
2338  int i,j=0,k=-1,l,ii;
2339
2340  loop
2341  {
2342    l = -1;
2343    for(i=0;i<length;i++)
2344    {
2345      if (sPairs[i].syzind>k)
2346      {
2347        if (l==-1)
2348        {
2349          l = sPairs[i].syzind;
2350          ii = i;
2351        }
2352        else
2353        {
2354          if (sPairs[i].syzind<l)
2355          {
2356            l = sPairs[i].syzind;
2357            ii = i;
2358          }
2359        }
2360      }
2361    }
2362    if (l==-1) break;
2363    (*result)[j] = ii;
2364    j++;
2365    k = l;
2366  }
2367  return result;
2368}
2369
2370/*2
2371* minimizes the output of LaScala
2372*/
2373static resolvente syReadOutMinimalRes(syStrategy syzstr,
2374           BOOLEAN computeStd=FALSE)
2375{
2376  intvec * Strip, * ordn;
2377  resolvente tres=(resolvente)omAlloc0((syzstr->length+1)*sizeof(ideal));
2378  ring tmpR = NULL;
2379  ring origR = currRing;
2380
2381//Print("Hier ");
2382  if (computeStd)
2383  {
2384    tres[0] = syzstr->res[1];
2385    syzstr->res[1] = idInit(IDELEMS(tres[0]),tres[0]->rank);
2386    return tres;
2387  }
2388  int i,j,l,index,ii,i1;
2389  poly p;
2390  ideal rs;
2391  SSet sPairs;
2392  int * ord,*b0,*b1;
2393
2394  assume(syzstr->syRing != NULL);
2395  rChangeCurrRing(syzstr->syRing);
2396//Print("laeufts ");
2397  syzstr->bucket = kBucketCreate();
2398  for (index=syzstr->length-1;index>0;index--)
2399  {
2400    if (syzstr->resPairs[index]!=NULL)
2401    {
2402//Print("ideal %d: \n",index);
2403      currcomponents = syzstr->truecomponents[index];
2404      currShiftedComponents = syzstr->ShiftedComponents[index];
2405      rChangeSComps(currcomponents, currShiftedComponents,
2406                    IDELEMS(syzstr->res[index]));
2407      sPairs = syzstr->resPairs[index];
2408      Strip = syToStrip(syzstr,index);
2409      tres[index+1] = idInit(IDELEMS(syzstr->res[index+1]),syzstr->res[index+1]->rank);
2410      i1 = (*syzstr->Tl)[index];
2411//Print("i1= %d\n",i1);
2412      ordn = syOrdPairs(sPairs,i1);
2413      for (i=0;i<i1;i++)
2414      {
2415        if ((sPairs[i].isNotMinimal==NULL) && (sPairs[i].lcm!=NULL))
2416        {
2417          l = sPairs[i].syzind;
2418//Print("Minimiere Poly %d: ",l);pWrite(syzstr->res[index+1]->m[l]);
2419          tres[index+1]->m[l] =
2420            syMinimizeP1(l,syzstr,ordn,index,Strip);
2421        }
2422      }
2423      delete Strip;
2424      Strip = NULL;
2425    }
2426  }
2427  currcomponents = syzstr->truecomponents[0];
2428  currShiftedComponents = syzstr->ShiftedComponents[0];
2429  rChangeSComps( currcomponents, currShiftedComponents,
2430                 IDELEMS(syzstr->res[0]));
2431  tres[1] = idInit(IDELEMS(syzstr->res[1]),syzstr->res[1]->rank);
2432  sPairs = syzstr->resPairs[0];
2433  for (i=(*syzstr->Tl)[0]-1;i>=0;i--)
2434  {
2435    if (sPairs[i].syzind>=0)
2436    {
2437      tres[1]->m[sPairs[i].syzind] = pCopy(syzstr->res[1]->m[sPairs[i].syzind]);
2438    }
2439  }
2440/*--- changes to the original ring------------------*/
2441  kBucketDestroy(&syzstr->bucket);
2442  if (syzstr->syRing != NULL)
2443  {
2444    rChangeCurrRing(origR);
2445    // Thomas: now make sure that all data which you need is pFetchCopied
2446    // maybe incoporate it into syReorder ??
2447  }
2448  tres = syReorder(tres,syzstr->length,syzstr,FALSE,syzstr->res);
2449  syKillEmptyEntres(tres,syzstr->length);
2450  idSkipZeroes(tres[0]);
2451  return tres;
2452}
2453
2454/*3
2455* minimizes any kind of resolution
2456*/
2457syStrategy syMinimize(syStrategy syzstr)
2458{
2459  if (syzstr->minres==NULL)
2460  {
2461    if (syzstr->resPairs!=NULL)
2462    {
2463      if (syzstr->hilb_coeffs==NULL)
2464      {
2465        syzstr->minres = syReadOutMinimalRes(syzstr);
2466      }
2467      else
2468      {
2469        syzstr->minres = syReorder(syzstr->orderedRes,syzstr->length,syzstr);
2470      }
2471    }
2472    else if (syzstr->fullres!=NULL)
2473    {
2474      syMinimizeResolvente(syzstr->fullres,syzstr->length,1);
2475      syzstr->minres = syzstr->fullres;
2476      syzstr->fullres = NULL;
2477    }
2478  }
2479  (syzstr->references)++;
2480  return syzstr;
2481}
2482
2483/*2
2484* implementation of LaScala's algorithm
2485* assumes that the given module is homogeneous
2486* works with slanted degree, uses syChosePairs
2487*/
2488syStrategy syLaScala3(ideal arg,int * length)
2489{
2490  BOOLEAN noPair=FALSE;
2491  int i,j,actdeg=32000,index=0,reg=-1;
2492  int startdeg,howmuch;
2493  poly p;
2494  ideal temp;
2495  SSet nextPairs;
2496  syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy));
2497  ring origR = currRing;
2498
2499  if ((idIs0(arg)) ||
2500      ((idRankFreeModule(arg)>0) && (!idHomModule(arg,NULL,&(syzstr->cw)))))
2501  {
2502    syzstr->minres = (resolvente)omAlloc0Bin(char_ptr_bin);
2503    syzstr->length = 1;
2504    syzstr->minres[0] = idInit(1,arg->rank);
2505    return syzstr;
2506  }
2507
2508  //crit = 0;
2509  //euler = -1;
2510  redpol = pInit();
2511  syzstr->length = *length = pVariables+2;
2512
2513  // Creare dp,S ring and change to it
2514  syzstr->syRing = rCurrRingAssure_dp_S();
2515  assume(syzstr->syRing != origR);
2516
2517  // set initial ShiftedComps
2518  currcomponents = (int*)omAlloc0((arg->rank+1)*sizeof(int));
2519  currShiftedComponents = (long*)omAlloc0((arg->rank+1)*sizeof(long));
2520  for (i=0;i<=arg->rank;i++)
2521  {
2522    currShiftedComponents[i] = (i)*SYZ_SHIFT_BASE;
2523    currcomponents[i] = i;
2524  }
2525  rChangeSComps(currcomponents, currShiftedComponents, arg->rank);
2526/*--- initializes the data structures---------------*/
2527  syzstr->Tl = new intvec(*length);
2528  temp = idInit(IDELEMS(arg),arg->rank);
2529  for (i=0;i<IDELEMS(arg);i++)
2530  {
2531    temp->m[i] = prCopyR( arg->m[i], origR);
2532    if (temp->m[i]!=NULL)
2533    {
2534      j = pTotaldegree(temp->m[i]);
2535      if (j<actdeg) actdeg = j;
2536    }
2537  }
2538  idTest(temp);
2539  idSkipZeroes(temp);
2540  idTest(temp);
2541  syzstr->resPairs = syInitRes(temp,length,syzstr->Tl,syzstr->cw);
2542  omFreeSize((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int));
2543  omFreeSize((ADDRESS)currShiftedComponents,(arg->rank+1)*sizeof(long));
2544  syzstr->res = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
2545  syzstr->orderedRes = (resolvente)omAlloc0((*length+1)*sizeof(ideal));
2546  syzstr->elemLength = (int**)omAlloc0((*length+1)*sizeof(int*));
2547  syzstr->truecomponents = (int**)omAlloc0((*length+1)*sizeof(int*));
2548  syzstr->ShiftedComponents = (long**)omAlloc0((*length+1)*sizeof(long*));
2549  syzstr->backcomponents = (int**)omAlloc0((*length+1)*sizeof(int*));
2550  syzstr->Howmuch = (int**)omAlloc0((*length+1)*sizeof(int*));
2551  syzstr->Firstelem = (int**)omAlloc0((*length+1)*sizeof(int*));
2552  syzstr->sev = (unsigned long **) omAlloc0((*length+1)*sizeof(unsigned long *));
2553  syzstr->bucket = kBucketCreate();
2554  int len0=idRankFreeModule(temp)+1;
2555
2556  startdeg = actdeg;
2557  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2558  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2559/*--- computes the resolution ----------------------*/
2560  while (nextPairs!=NULL)
2561  {
2562    if (TEST_OPT_PROT) Print("%d",actdeg);
2563    if (TEST_OPT_PROT) Print("(m%d)",index);
2564    if (index==0)
2565      i = syInitSyzMod(syzstr,index,len0);
2566    else
2567      i = syInitSyzMod(syzstr,index);
2568    currcomponents = syzstr->truecomponents[si_max(index-1,0)];
2569    currShiftedComponents = syzstr->ShiftedComponents[si_max(index-1,0)];
2570    rChangeSComps(currcomponents, currShiftedComponents,
2571                  IDELEMS(syzstr->res[si_max(index-1,0)]));
2572    j = syInitSyzMod(syzstr,index+1);
2573    if (index>0)
2574    {
2575      syRedNextPairs(nextPairs,syzstr,howmuch,index);
2576      syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2577    }
2578    else
2579      syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2580/*--- creates new pairs -----------------------------*/
2581    syCreateNewPairs(syzstr,index,i);
2582    if (index<(*length)-1)
2583    {
2584      syCreateNewPairs(syzstr,index+1,j);
2585    }
2586    index++;
2587    nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2588    //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2589  }
2590  if (temp!=NULL) idDelete(&temp);
2591  kBucketDestroy(&(syzstr->bucket));
2592  if (origR != syzstr->syRing)
2593    rChangeCurrRing(origR);
2594  pLmDelete(&redpol);
2595  if (TEST_OPT_PROT) PrintLn();
2596  return syzstr;
2597}
2598
2599
2600
2601/*2
2602* more general implementation of LaScala's algorithm
2603* assumes that the given module is (quasi-)homogeneous
2604* works with slanted degree, uses syChosePairs
2605*/
2606syStrategy syLaScala(ideal arg, int& maxlength, intvec* weights)
2607{
2608  BOOLEAN noPair=FALSE;
2609  int i,j,actdeg=32000,index=0,reg=-1;
2610  int startdeg,howmuch;
2611  poly p;
2612  ideal temp;
2613  SSet nextPairs;
2614  syStrategy syzstr=(syStrategy)omAlloc0(sizeof(ssyStrategy));
2615  ring origR = currRing;
2616
2617  if(weights!= NULL) 
2618    syzstr->cw = new intvec(weights);
2619  else
2620    syzstr->cw = NULL;
2621
2622  if ((idIs0(arg)) ||
2623      ((idRankFreeModule(arg)>0) && (!idTestHomModule(arg, NULL, syzstr->cw))))
2624  {
2625    syzstr->minres = (resolvente)omAlloc0Bin(char_ptr_bin);
2626    syzstr->length = 1;
2627    syzstr->minres[0] = idInit(1,arg->rank);
2628    return syzstr;
2629  }
2630
2631
2632  //crit = 0;
2633  //euler = -1;
2634  redpol = pInit();
2635 
2636  if( maxlength > 0 )
2637    syzstr->length = maxlength; //  = pVariables+2;
2638  else
2639    syzstr->length = maxlength = pVariables+2; 
2640
2641  // Creare dp,S ring and change to it
2642  syzstr->syRing = rCurrRingAssure_dp_S();
2643  assume(syzstr->syRing != origR);
2644
2645  // set initial ShiftedComps
2646  currcomponents = (int*)omAlloc0((arg->rank+1)*sizeof(int));
2647  currShiftedComponents = (long*)omAlloc0((arg->rank+1)*sizeof(long));
2648  for (i=0;i<=arg->rank;i++)
2649  {
2650    currShiftedComponents[i] = (i)*SYZ_SHIFT_BASE;
2651    currcomponents[i] = i;
2652  }
2653  rChangeSComps(currcomponents, currShiftedComponents, arg->rank);
2654/*--- initializes the data structures---------------*/
2655  syzstr->Tl = new intvec(maxlength);
2656  temp = idInit(IDELEMS(arg),arg->rank);
2657  for (i=0;i<IDELEMS(arg);i++)
2658  {
2659    temp->m[i] = prCopyR( arg->m[i], origR);
2660    if (temp->m[i]!=NULL)
2661    {
2662      j = pTotaldegree(temp->m[i]);
2663      if (j<actdeg) actdeg = j;
2664    }
2665  }
2666  idTest(temp);
2667  idSkipZeroes(temp);
2668  idTest(temp);
2669  syzstr->resPairs = syInitRes(temp,&maxlength,syzstr->Tl,syzstr->cw);
2670  omFreeSize((ADDRESS)currcomponents,(arg->rank+1)*sizeof(int));
2671  omFreeSize((ADDRESS)currShiftedComponents,(arg->rank+1)*sizeof(long));
2672  syzstr->res = (resolvente)omAlloc0((maxlength+1)*sizeof(ideal));
2673  syzstr->orderedRes = (resolvente)omAlloc0((maxlength+1)*sizeof(ideal));
2674  syzstr->elemLength = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2675  syzstr->truecomponents = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2676  syzstr->ShiftedComponents = (long**)omAlloc0((maxlength+1)*sizeof(long*));
2677  syzstr->backcomponents = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2678  syzstr->Howmuch = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2679  syzstr->Firstelem = (int**)omAlloc0((maxlength+1)*sizeof(int*));
2680  syzstr->sev = (unsigned long **) omAlloc0((maxlength+1)*sizeof(unsigned long *));
2681  syzstr->bucket = kBucketCreate();
2682  int len0=idRankFreeModule(temp)+1;
2683
2684  startdeg = actdeg;
2685  nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2686  //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2687/*--- computes the resolution ----------------------*/
2688  while (nextPairs!=NULL)
2689  {
2690    if (TEST_OPT_PROT) Print("%d",actdeg);
2691    if (TEST_OPT_PROT) Print("(m%d)",index);
2692    if (index==0)
2693      i = syInitSyzMod(syzstr,index,len0);
2694    else
2695      i = syInitSyzMod(syzstr,index);
2696    currcomponents = syzstr->truecomponents[si_max(index-1,0)];
2697    currShiftedComponents = syzstr->ShiftedComponents[si_max(index-1,0)];
2698    rChangeSComps(currcomponents, currShiftedComponents,
2699                  IDELEMS(syzstr->res[si_max(index-1,0)]));
2700    j = syInitSyzMod(syzstr,index+1);
2701    if (index>0)
2702    {
2703      syRedNextPairs(nextPairs,syzstr,howmuch,index);
2704      syCompactifyPairSet(syzstr->resPairs[index],(*syzstr->Tl)[index],0);
2705    }
2706    else
2707      syRedGenerOfCurrDeg(syzstr,actdeg,index+1);
2708/*--- creates new pairs -----------------------------*/
2709    syCreateNewPairs(syzstr,index,i);
2710    if (index<(maxlength-1))
2711    {
2712      syCreateNewPairs(syzstr,index+1,j);
2713    }
2714    index++;
2715    nextPairs = syChosePairs(syzstr,&index,&howmuch,&actdeg);
2716    //if (TEST_OPT_PROT) Print("(%d,%d)",howmuch,index);
2717  }
2718  if (temp!=NULL) idDelete(&temp);
2719  kBucketDestroy(&(syzstr->bucket));
2720  if (origR != syzstr->syRing)
2721    rChangeCurrRing(origR);
2722  pLmDelete(&redpol);
2723  if (TEST_OPT_PROT) PrintLn();
2724  return syzstr;
2725}
2726
Note: See TracBrowser for help on using the repository browser.