source: git/Singular/dyn_modules/syzextra/syzextra.cc @ 542685e

spielwiese
Last change on this file since 542685e was 542685e, checked in by Oleksandr Motsak <motsak@…>, 9 years ago
Updating + Fixing
  • Property mode set to 100644
File size: 66.7 KB
Line 
1// -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2/*****************************************************************************\
3 * Computer Algebra System SINGULAR
4\*****************************************************************************/
5/** @file syzextra.cc
6 *
7 * New implementations for the computation of syzygies and resolutions
8 *
9 * ABSTRACT: Computation of Syzygies due to Schreyer
10 *
11 * @author Oleksandr Motsak
12 *
13 **/
14/*****************************************************************************/
15
16// include header file
17#include <kernel/mod2.h>
18
19#include "syzextra.h"
20
21#include "DebugPrint.h"
22
23#include <omalloc/omalloc.h>
24
25#include <misc/intvec.h>
26#include <misc/options.h>
27
28#include <coeffs/coeffs.h>
29
30#include <polys/monomials/p_polys.h>
31#include <polys/monomials/ring.h>
32#include <polys/simpleideals.h>
33
34#include <polys/kbuckets.h> // for kBucket*
35#include <polys/sbuckets.h> // for sBucket*
36//#include <polys/nc/summator.h> // for CPolynomialSummator
37#include <polys/operations/p_Mult_q.h> // for MIN_LENGTH_BUCKET
38
39#include <kernel/GBEngine/kstd1.h>
40#include <kernel/polys.h>
41#include <kernel/GBEngine/syz.h>
42#include <kernel/ideals.h>
43
44#include <kernel/oswrapper/timer.h>
45
46
47#include <Singular/tok.h>
48#include <Singular/ipid.h>
49#include <Singular/lists.h>
50#include <Singular/attrib.h>
51
52#include <Singular/ipid.h>
53#include <Singular/ipshell.h> // For iiAddCproc
54
55#include <stdio.h>
56#include <stdlib.h>
57#include <string.h>
58
59// USING_NAMESPACE_SINGULARXX;
60USING_NAMESPACE( SINGULARXXNAME :: DEBUG )
61
62
63BEGIN_NAMESPACE_SINGULARXX     BEGIN_NAMESPACE(SYZEXTRA)
64
65
66BEGIN_NAMESPACE_NONAME
67
68static inline poly pp_Add_qq( const poly a, const poly b, const ring R)
69{
70  return p_Add_q( p_Copy(a, R), p_Copy(b, R), R );
71}
72
73static inline poly p_VectorProductLT( poly s,  const ideal& L, const ideal& T, const ring& R)
74{
75  assume( IDELEMS(L) == IDELEMS(T) );
76  poly vp = NULL; // resulting vector product
77
78  while( s != NULL )
79  {
80    const poly nxt = pNext(s);
81    pNext(s) = NULL;
82
83    if( !n_IsZero( p_GetCoeff(s, R), R) )
84    {
85      const int i = p_GetComp(s, R) - 1;
86      assume( i >= 0 ); assume( i < IDELEMS(L) );
87      p_SetComp(s, 0, R); p_SetmComp(s, R);
88
89      vp = p_Add_q( vp, pp_Mult_qq( s, L->m[i], R ), R); 
90      vp = p_Add_q( vp, pp_Mult_qq( s, T->m[i], R ), R); 
91    }
92
93    p_Delete(&s, R);
94
95    s = nxt;
96  };
97
98  assume( s == NULL );
99
100  return vp;
101}
102
103static inline int atGetInt(idhdl rootRingHdl, const char* attribute, long def)
104{
105  return ((int)(long)(atGet(rootRingHdl, attribute, INT_CMD, (void*)def)));
106}
107
108END_NAMESPACE
109
110BEGIN_NAMESPACE(SORT_c_ds)
111
112#if (defined(HAVE_QSORT_R) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9))
113static int cmp_c_ds(void *R, const void *p1, const void *p2){
114#elif (defined(HAVE_QSORT_R) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
115static int cmp_c_ds(const void *p1, const void *p2, void *R){
116#else
117static int cmp_c_ds(const void *p1, const void *p2){ void *R = currRing;
118#endif
119  assume(R != NULL);
120  const int YES = 1;
121  const int NO = -1;
122
123  const ring r =  (const ring) R; // TODO/NOTE: the structure is known: C, lp!!!
124
125  assume( r == currRing ); // for now...
126
127  const poly a = *(const poly*)p1;
128  const poly b = *(const poly*)p2;
129
130  assume( a != NULL );
131  assume( b != NULL );
132
133  p_LmTest(a, r);
134  p_LmTest(b, r);
135
136
137  const signed long iCompDiff = p_GetComp(a, r) - p_GetComp(b, r);
138
139  // TODO: test this!!!!!!!!!!!!!!!!
140
141  //return -( compare (c, qsorts) )
142
143#ifndef SING_NDEBUG
144  const int __DEBUG__ = 0;
145  if( __DEBUG__ )
146  {
147    PrintS("cmp_c_ds: a, b: \np1: "); dPrint(a, r, r, 2);
148    PrintS("b: "); dPrint(b, r, r, 2);
149    PrintLn();
150  }
151#endif
152
153
154  if( iCompDiff > 0 )
155    return YES;
156
157  if( iCompDiff < 0 )
158    return  NO;
159
160  assume( iCompDiff == 0 );
161
162  const signed long iDegDiff = p_Totaldegree(a, r) - p_Totaldegree(b, r);
163
164  if( iDegDiff > 0 )
165    return YES;
166
167  if( iDegDiff < 0 )
168    return  NO;
169
170  assume( iDegDiff == 0 );
171
172#ifndef SING_NDEBUG
173  if( __DEBUG__ )
174  {
175    PrintS("cmp_c_ds: a & b have the same comp & deg! "); PrintLn();
176  }
177#endif
178
179  for (int v = rVar(r); v > 0; v--)
180  {
181    assume( v > 0 );
182    assume( v <= rVar(r) );
183
184    const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
185
186    if( d > 0 )
187      return YES;
188
189    if( d < 0 )
190      return NO;
191
192    assume( d == 0 );
193  }
194
195  return 0;
196}
197
198/*
199static int cmp_poly(const poly &a, const poly &b)
200{
201  const int YES = 1;
202  const int NO = -1;
203
204  const ring r =  (const ring) currRing; // TODO/NOTE: the structure is known: C, lp!!!
205
206  assume( r == currRing );
207
208  assume( a != NULL );
209  assume( b != NULL );
210
211  p_LmTest(a, r);
212  p_LmTest(b, r);
213  assume( p_GetComp(a, r) == 0 );
214  assume( p_GetComp(b, r) == 0 );
215
216#ifndef SING_NDEBUG
217  const int __DEBUG__ = 0;
218  if( __DEBUG__ )
219  {
220    PrintS("cmp_lex: a, b: \np1: "); dPrint(a, r, r, 2);
221    PrintS("b: "); dPrint(b, r, r, 2);
222    PrintLn();
223  }
224#endif
225
226  for (int v = rVar(r); v > 0; v--)
227  {
228    assume( v > 0 );
229    assume( v <= rVar(r) );
230
231    const signed int d = p_GetExp(a, v, r) - p_GetExp(b, v, r);
232
233    if( d > 0 )
234      return YES;
235
236    if( d < 0 )
237      return NO;
238
239    assume( d == 0 );
240  }
241
242  return 0;
243}
244*/
245
246END_NAMESPACE
247/* namespace SORT_c_ds */
248
249/// writes a monomial (p),
250/// uses form x*gen(.) if ko != coloumn number of p
251static void writeLatexTerm(const poly t, const ring r, const bool bCurrSyz = true, const bool bLTonly = true)
252{
253  if( t == NULL )
254  {
255    PrintS(" 0 ");
256    return;
257  }
258
259  assume( r != NULL );
260  const coeffs C = r->cf; assume(C != NULL);
261
262  poly p = t;
263  BOOLEAN writePlus = FALSE;
264
265  do {
266  assume( p != NULL );
267
268  // write coef...
269  number& n = p_GetCoeff(p, r);
270
271  n_Normalize(n, C);
272
273  BOOLEAN writeMult = FALSE; ///< needs * before pp or module generator
274
275  BOOLEAN writeOne = FALSE; ///< need to write something after '-'!
276
277  if( n_IsZero(n, C) )
278  {
279    PrintS( writePlus? " + 0" : " 0 " ); writePlus = TRUE; writeMult = TRUE;
280//    return; // yes?
281  }
282
283  if (n_IsMOne(n, C))
284  {
285    PrintS(" - "); writeOne = TRUE; writePlus = FALSE;
286  }
287  else if (!n_IsOne(n, C))
288  {
289    if( writePlus && n_GreaterZero(n, C) )
290      PrintS(" + ");
291
292    StringSetS(""); n_WriteLong(n, C);
293    if (true)
294    {
295      char *s = StringEndS(); PrintS(s); omFree(s);
296    }
297
298
299    writeMult = TRUE;
300    writePlus = TRUE;
301  } else
302     writeOne = TRUE;
303
304  // missing '1' if no PP and gen...!?
305  // write monom...
306  const short N = rVar(r);
307
308  BOOLEAN wrotePP = FALSE; ///< needs * before module generator?
309
310  for (short i = 0; i < N; i++)
311  {
312    const long ee = p_GetExp(p, i+1, r);
313
314    if (ee!=0L)
315    {
316      if (writeMult)
317      {
318        PrintS(" ");
319        writeMult = FALSE;
320      } else
321      if( writePlus )
322        PrintS(" + ");
323
324      writePlus = FALSE;
325
326      if (ee != 1L)
327        Print(" %s^{%ld} ", rRingVar(i, r), ee);
328      else
329        Print(" %s ", rRingVar(i, r));
330
331      writeOne = FALSE;
332      wrotePP = TRUE;
333    }
334  }
335
336  writePlus = writePlus || wrotePP;
337  writeMult = writeMult || wrotePP;
338
339  // write module gen...
340  const long comp = p_GetComp(p, r);
341
342  if (comp > 0 )
343  {
344    if (writeMult)
345      PrintS("  ");
346     else
347      if( writePlus )
348        PrintS(" + ");
349
350    if (bCurrSyz)
351      Print(" \\\\GEN{%ld} ", comp);
352    else
353      Print(" \\\\GENP{%ld} ", comp);
354
355      writeOne = FALSE;
356  }
357
358  if ( writeOne )
359    PrintS( writePlus? " + 1 " : " 1 " );
360
361
362  pIter(p);
363
364  writePlus = TRUE;
365  } while( (!bLTonly) && (p != NULL) );
366
367}
368
369
370
371
372
373/// return a new term: leading coeff * leading monomial of p
374/// with 0 leading component!
375poly leadmonom(const poly p, const ring r, const bool bSetZeroComp)
376{
377  poly m = NULL;
378
379  if( p != NULL )
380  {
381    assume( p != NULL );
382    p_LmTest(p, r);
383
384    m = p_LmInit(p, r);
385    p_SetCoeff0(m, n_Copy(p_GetCoeff(p, r), r), r);
386
387    if( bSetZeroComp )
388      p_SetComp(m, 0, r);
389    p_Setm(m, r);
390
391
392    assume( m != NULL );
393    assume( pNext(m) == NULL );
394    p_LmTest(m, r);
395
396    if( bSetZeroComp )
397      assume( p_GetComp(m, r) == 0 );
398  }
399
400  return m;
401}
402
403
404
405poly p_Tail(const poly p, const ring r)
406{
407  if( p == NULL)
408    return NULL;
409  else
410    return p_Copy( pNext(p), r );
411}
412
413
414ideal id_Tail(const ideal id, const ring r)
415{
416  if( id == NULL)
417    return NULL;
418
419  const ideal newid = idInit(IDELEMS(id),id->rank);
420
421  for (int i=IDELEMS(id) - 1; i >= 0; i--)
422    newid->m[i] = p_Tail( id->m[i], r );
423
424  newid->rank = id_RankFreeModule(newid, currRing);
425
426  return newid;
427}
428
429
430
431void Sort_c_ds(const ideal id, const ring r)
432{
433  const int sizeNew = IDELEMS(id);
434
435#if ( (defined(HAVE_QSORT_R)) && (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined OpenBSD3_1 || defined OpenBSD3_9) )
436#define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, r, cmp)
437#elif ( (defined(HAVE_QSORT_R)) && (defined _GNU_SOURCE || defined __GNU__ || defined __linux__))
438#define qsort_my(m, s, ss, r, cmp) qsort_r(m, s, ss, cmp, r)
439#else
440#define qsort_my(m, s, ss, r, cmp) qsort(m, s, ss, cmp)
441#endif
442
443  if( sizeNew >= 2 )
444    qsort_my(id->m, sizeNew, sizeof(poly), r, FROM_NAMESPACE(SORT_c_ds, cmp_c_ds));
445
446#undef qsort_my
447
448  id->rank = id_RankFreeModule(id, r);
449}
450
451/// Clean up all the accumulated data
452void SchreyerSyzygyComputation::CleanUp()
453{
454  extern void id_Delete (ideal*, const ring);
455
456  id_Delete(const_cast<ideal*>(&m_idTails), m_rBaseRing); // TODO!!!
457
458  if( m_sum_bucket != NULL )
459  {
460    sBucketDestroy(&m_sum_bucket);
461    m_sum_bucket = NULL;
462  }
463
464  if( m_spoly_bucket != NULL )
465  {
466    kBucketDestroy(&m_spoly_bucket);
467    m_spoly_bucket = NULL;
468  }
469
470  for( TCache::iterator it = m_cache.begin(); it != m_cache.end(); it++ )
471  {
472    TP2PCache& T = it->second;
473
474    for(TP2PCache::iterator vit = T.begin(); vit != T.end(); vit++ )
475    {
476      p_Delete( (&(vit->second)), m_rBaseRing);
477      p_Delete( const_cast<poly*>(&(vit->first)), m_rBaseRing);
478    }
479  }
480}
481  /*
482  for( TTailTerms::const_iterator it = m_idTailTerms.begin(); it != m_idTailTerms.end(); it++ )
483  {
484    const TTail& v = *it;
485    for(TTail::const_iterator vit = v.begin(); vit != v.end(); vit++ )
486      delete const_cast<CTailTerm*>(*vit);
487  }
488  */
489
490
491
492int CReducerFinder::PreProcessTerm(const poly t, CReducerFinder& syzChecker) const
493{
494  assume( t != NULL );
495
496  if( __DEBUG__ & __TAILREDSYZ__ )
497    assume( !IsDivisible(t) ); // each input term should NOT be in <L>
498
499  const ring r = m_rBaseRing;
500
501
502  if( __TAILREDSYZ__ )
503    if( p_LmIsConstant(t, r) ) // most basic case of baing coprime with L, whatever that is...
504      return 1; // TODO: prove this...?
505
506  //   return false; // appears to be fine
507
508  const long comp = p_GetComp(t, r);
509
510  CReducersHash::const_iterator itr = m_hash.find(comp);
511
512  if ( itr == m_hash.end() )
513    return 2; // no such leading component!!!
514
515  assume( itr->first == comp );
516
517  const bool bIdealCase = (comp == 0);
518  const bool bSyzCheck = syzChecker.IsNonempty(); // need to check even in ideal case????? proof?  "&& !bIdealCase"
519
520  if( __TAILREDSYZ__ && (bIdealCase || bSyzCheck) )
521  {
522    const TReducers& v = itr->second;
523    const int N = rVar(r);
524    // TODO: extract exps of t beforehand?!
525    bool coprime = true;
526    for(TReducers::const_iterator vit = v.begin(); (vit != v.end()) && coprime; ++vit )
527    {
528      assume( (*vit)->CheckLT( m_L ) );
529
530      const poly p = (*vit)->lt();
531
532      assume( p_GetComp(p, r) == comp );
533
534      // TODO: check if coprime with Leads... if __TAILREDSYZ__ !
535      for( int var = N; var > 0; --var )
536        if( (p_GetExp(p, var, r) != 0) && (p_GetExp(t, var, r) != 0) )
537        {
538#ifndef SING_NDEBUG
539          if( __DEBUG__ | 0)
540          {
541            PrintS("CReducerFinder::PreProcessTerm, 't' is NOT co-prime with the following leading term: \n");
542            dPrint(p, r, r, 1);
543          }
544#endif
545          coprime = false; // t not coprime with p!
546          break;
547        }
548
549      if( bSyzCheck && coprime )
550      {
551        poly ss = p_LmInit(t, r);
552        p_SetCoeff0(ss, n_Init(1, r), r); // for delete & printout only!...
553        p_SetComp(ss, (*vit)->label() + 1, r); // coeff?
554        p_Setm(ss, r);
555
556        coprime = ( syzChecker.IsDivisible(ss) );
557
558#ifndef SING_NDEBUG
559        if( __DEBUG__ && !coprime)
560        {
561          PrintS("CReducerFinder::PreProcessTerm, 't' is co-prime with p but may lead to NOT divisible syz.term: \n");
562          dPrint(ss, r, r, 1);
563        }
564#endif
565
566        p_LmDelete(&ss, r); // deletes coeff as well???
567      }
568
569      assume( p == (*vit)->lt() );
570      assume( (*vit)->CheckLT( m_L ) );
571    }
572
573#ifndef SING_NDEBUG
574    if( __DEBUG__ && coprime )
575      PrintS("CReducerFinder::PreProcessTerm, the following 't' is 'co-prime' with all of leading terms! \n");
576#endif
577
578    return coprime? 3: 0; // t was coprime with all of leading terms!!!
579
580  }
581  //   return true; // delete the term
582
583  return 0;
584}
585
586
587void SchreyerSyzygyComputation::SetUpTailTerms()
588{
589  const ideal idTails = m_idTails;
590  assume( idTails != NULL );
591  assume( idTails->m != NULL );
592  const ring r = m_rBaseRing;
593
594#ifndef SING_NDEBUG
595  if( __DEBUG__ | 0)
596  {
597    PrintS("SchreyerSyzygyComputation::SetUpTailTerms(): Tails: \n");
598    dPrint(idTails, r, r, 0);
599  }
600
601  unsigned long pp[4] = {0,0,0,0}; // count preprocessed terms...
602#endif
603
604  for( int p = IDELEMS(idTails) - 1; p >= 0; --p )
605    for( poly* tt = &(idTails->m[p]); (*tt) != NULL;  )
606    {
607      const poly t = *tt;
608      const int k = m_div.PreProcessTerm(t, m_checker); // 0..3
609      assume( 0 <= k && k <= 3 );
610
611#ifndef SING_NDEBUG
612      pp[k]++;
613#endif
614
615      if( k )
616      {
617#ifndef SING_NDEBUG
618        if( __DEBUG__)
619        {
620          Print("SchreyerSyzygyComputation::SetUpTailTerms(): PP (%d) the following TT: \n", k);
621          dPrint(t, r, r, 1);
622        }
623#endif
624
625        (*tt) = p_LmDeleteAndNext(t, r); // delete the lead and next...
626      }
627      else
628        tt = &pNext(t); // go next?
629
630    }
631
632#ifndef SING_NDEBUG
633  if( !__TREEOUTPUT__ )
634  if( TEST_OPT_PROT | 1)
635    Print("%%      **!!**      SchreyerSyzygyComputation::SetUpTailTerms()::PreProcessing(): X: {c: %lu, C: %lu, P: %lu} + %lu\n", pp[1], pp[2], pp[3], pp[0]);
636#endif
637
638#ifndef SING_NDEBUG
639  if( !__TREEOUTPUT__ )
640  if( __DEBUG__ | 0)
641  {
642    PrintS("SchreyerSyzygyComputation::SetUpTailTerms(): Preprocessed Tails: \n");
643    dPrint(idTails, r, r, 0);
644  }
645#endif
646
647}
648/*
649  m_idTailTerms.resize( IDELEMS(idTails) );
650
651  for( unsigned int p = IDELEMS(idTails) - 1; p >= 0; p -- )
652  {
653    TTail& v = m_idTailTerms[p];
654    poly t = idTails->m[p];
655    v.resize( pLength(t) );
656
657    unsigned int pp = 0;
658
659    while( t != NULL )
660    {
661      assume( t != NULL );
662      // TODO: compute L:t!
663//      ideal reducers;
664//      CReducerFinder m_reducers
665
666      CTailTerm* d = v[pp] = new CTailTerm();
667
668      ++pp; pIter(t);
669    }
670  }
671*/
672
673
674
675ideal SchreyerSyzygyComputation::Compute1LeadingSyzygyTerms()
676{
677  const ideal& id = m_idLeads;
678  const ring& r = m_rBaseRing;
679//  const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
680
681  assume(!__LEAD2SYZ__);
682
683  // 1. set of components S?
684  // 2. for each component c from S: set of indices of leading terms
685  // with this component?
686  // 3. short exp. vectors for each leading term?
687
688  const int size = IDELEMS(id);
689
690  if( size < 2 )
691  {
692    const ideal newid = idInit(1, 0); newid->m[0] = NULL; // zero ideal...
693    return newid;
694  }
695
696  // TODO/NOTE: input is supposed to be (reverse-) sorted wrt "(c,ds)"!??
697
698  // components should come in groups: count elements in each group
699  // && estimate the real size!!!
700
701
702  // use just a vector instead???
703  const ideal newid = idInit( (size * (size-1))/2, size); // maximal size: ideal case!
704
705  int k = 0;
706
707  for (int j = 0; j < size; j++)
708  {
709    const poly p = id->m[j];
710    assume( p != NULL );
711    const int  c = p_GetComp(p, r);
712
713    for (int i = j - 1; i >= 0; i--)
714    {
715      const poly pp = id->m[i];
716      assume( pp != NULL );
717      const int  cc = p_GetComp(pp, r);
718
719      if( c != cc )
720        continue;
721
722      const poly m = p_Init(r); // p_New???
723
724      // m = LCM(p, pp) / p! // TODO: optimize: knowing the ring structure: (C/lp)!
725      for (int v = rVar(r); v > 0; v--)
726      {
727        assume( v > 0 );
728        assume( v <= rVar(r) );
729
730        const short e1 = p_GetExp(p , v, r);
731        const short e2 = p_GetExp(pp, v, r);
732
733        if( e1 >= e2 )
734          p_SetExp(m, v, 0, r);
735        else
736          p_SetExp(m, v, e2 - e1, r);
737
738      }
739
740      assume( (j > i) && (i >= 0) );
741
742      p_SetComp(m, j + 1, r);
743      pNext(m) = NULL;
744      p_SetCoeff0(m, n_Init(1, r->cf), r); // for later...
745
746      p_Setm(m, r); // should not do anything!!!
747
748      newid->m[k++] = m;
749    }
750  }
751
752//   if( __DEBUG__ && FALSE )
753//   {
754//     PrintS("ComputeLeadingSyzygyTerms::Temp0: \n");
755//     dPrint(newid, r, r, 1);
756//   }
757
758  // the rest of newid is assumed to be zeroes...
759
760  // simplify(newid, 2 + 32)??
761  // sort(newid, "C,ds")[1]???
762  id_DelDiv(newid, r); // #define SIMPL_LMDIV 32
763
764//   if( __DEBUG__ && FALSE )
765//   {
766//     PrintS("ComputeLeadingSyzygyTerms::Temp1: \n");
767//     dPrint(newid, r, r, 1);
768//   }
769
770  idSkipZeroes(newid); // #define SIMPL_NULL 2
771
772//   if( __DEBUG__ )
773//   {
774//     PrintS("ComputeLeadingSyzygyTerms::Output: \n");
775//     dPrint(newid, r, r, 1);
776//   }
777
778  Sort_c_ds(newid, r);
779
780  return newid;
781}
782
783ideal SchreyerSyzygyComputation::Compute2LeadingSyzygyTerms()
784{
785  const ideal& id = m_idLeads;
786  const ring& r = m_rBaseRing;
787//  const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
788
789  // 1. set of components S?
790  // 2. for each component c from S: set of indices of leading terms
791  // with this component?
792  // 3. short exp. vectors for each leading term?
793
794  const int size = IDELEMS(id);
795
796  if( size < 2 )
797  {
798    const ideal newid = idInit(1, 1); newid->m[0] = NULL; // zero module...
799    return newid;
800  }
801
802
803  // TODO/NOTE: input is supposed to be sorted wrt "C,ds"!??
804
805  // components should come in groups: count elements in each group
806  // && estimate the real size!!!
807
808
809  // use just a vector instead???
810  ideal newid = idInit( (size * (size-1))/2, size); // maximal size: ideal case!
811
812  int k = 0;
813
814  for (int j = 0; j < size; j++)
815  {
816    const poly p = id->m[j];
817    assume( p != NULL );
818    const int  c = p_GetComp(p, r);
819
820    for (int i = j - 1; i >= 0; i--)
821    {
822      const poly pp = id->m[i];
823      assume( pp != NULL );
824      const int  cc = p_GetComp(pp, r);
825
826      if( c != cc )
827        continue;
828
829        // allocate memory & zero it out!
830      const poly m = p_Init(r); const poly mm = p_Init(r);
831
832
833        // m = LCM(p, pp) / p! mm = LCM(p, pp) / pp!
834        // TODO: optimize: knowing the ring structure: (C/lp)!
835
836      for (int v = rVar(r); v > 0; v--)
837      {
838        assume( v > 0 );
839        assume( v <= rVar(r) );
840
841        const short e1 = p_GetExp(p , v, r);
842        const short e2 = p_GetExp(pp, v, r);
843
844        if( e1 >= e2 )
845          p_SetExp(mm, v, e1 - e2, r); //            p_SetExp(m, v, 0, r);
846        else
847          p_SetExp(m, v, e2 - e1, r); //            p_SetExp(mm, v, 0, r);
848
849      }
850
851      assume( (j > i) && (i >= 0) );
852
853      p_SetComp(m, j + 1, r);
854      p_SetComp(mm, i + 1, r);
855
856      const number& lc1 = p_GetCoeff(p , r);
857      const number& lc2 = p_GetCoeff(pp, r);
858
859      number g = n_Lcm( lc1, lc2, r->cf );
860
861      p_SetCoeff0(m ,       n_Div(g, lc1, r), r);
862      p_SetCoeff0(mm, n_InpNeg(n_Div(g, lc2, r), r), r);
863
864      n_Delete(&g, r);
865
866      p_Setm(m, r); // should not do anything!!!
867      p_Setm(mm, r); // should not do anything!!!
868
869      pNext(m) = mm; //        pNext(mm) = NULL;
870
871      newid->m[k++] = m;
872    }
873  }
874
875//   if( __DEBUG__ && FALSE )
876//   {
877//     PrintS("Compute2LeadingSyzygyTerms::Temp0: \n");
878//     dPrint(newid, r, r, 1);
879//   }
880
881  if( !__TAILREDSYZ__ )
882  {
883      // simplify(newid, 2 + 32)??
884      // sort(newid, "C,ds")[1]???
885    id_DelDiv(newid, r); // #define SIMPL_LMDIV 32
886
887//     if( __DEBUG__ && FALSE )
888//     {
889//       PrintS("Compute2LeadingSyzygyTerms::Temp1 (deldiv): \n");
890//       dPrint(newid, r, r, 1);
891//     }
892  }
893  else
894  {
895      //      option(redSB); option(redTail);
896      //      TEST_OPT_REDSB
897      //      TEST_OPT_REDTAIL
898    assume( r == currRing );
899
900    BITSET _save_test; SI_SAVE_OPT1(_save_test);
901    SI_RESTORE_OPT1(Sy_bit(OPT_REDTAIL) | Sy_bit(OPT_REDSB) | _save_test);
902
903    intvec* w=new intvec(IDELEMS(newid));
904    ideal tmp = kStd(newid, currRing->qideal, isHomog, &w);
905    delete w;
906
907    SI_RESTORE_OPT1(_save_test)
908
909    id_Delete(&newid, r);
910    newid = tmp;
911
912//     if( __DEBUG__ && FALSE )
913//     {
914//       PrintS("Compute2LeadingSyzygyTerms::Temp1 (std): \n");
915//       dPrint(newid, r, r, 1);
916//     }
917
918  }
919
920  idSkipZeroes(newid);
921
922  Sort_c_ds(newid, r);
923
924  return newid;
925}
926
927poly SchreyerSyzygyComputation::TraverseNF(const poly a, const poly a2) const
928{
929#ifndef SING_NDEBUG
930  if( __DEBUG__ )
931  {
932    m_div.Verify();
933    m_checker.Verify();
934  }
935#endif
936
937  const ideal& L = m_idLeads;
938  const ideal& T = m_idTails;
939
940  const ring& R = m_rBaseRing;
941
942  const int r = p_GetComp(a, R) - 1;
943
944  assume( r >= 0 && r < IDELEMS(T) );
945  assume( r >= 0 && r < IDELEMS(L) );
946
947  assume( a != NULL );
948
949#ifndef SING_NDEBUG
950  if( __DEBUG__ )
951  {
952    PrintS("SchreyerSyzygyComputation::TraverseNF(syz_lead, poly syz_2), \n");
953    PrintS("syz_lead: \n");
954    dPrint(a, R, R, 1);
955    PrintS("syz_2: \n");
956    dPrint(a2, R, R, 1);
957    PrintLn();
958  }
959#endif
960 
961  if( __TREEOUTPUT__ )
962  {
963     PrintS("{ \"nodelabel\": \""); writeLatexTerm(a, R); PrintS("\", \"children\": [");
964  }
965
966
967  poly aa = leadmonom(a, R); assume( aa != NULL); // :(
968
969  poly t = TraverseTail(aa, r);
970
971#ifndef SING_NDEBUG
972  if( __DEBUG__ )
973  {
974    m_div.Verify();
975    m_checker.Verify();
976  }
977#endif
978 
979  if( a2 != NULL )
980  {
981    assume( __LEAD2SYZ__ );
982
983    if( __TREEOUTPUT__ )
984    {
985       PrintS("{ \"nodelabel\": \""); writeLatexTerm(a2, R); PrintS("\", \"children\": [");
986    }
987
988    // replace the following... ?
989    const int r2 = p_GetComp(a2, R) - 1; poly aa2 = leadmonom(a2, R); // :(
990
991    assume( r2 >= 0 && r2 < IDELEMS(T) );
992
993    t = p_Add_q(a2, p_Add_q(t, TraverseTail(aa2, r2), R), R);
994
995    p_Delete(&aa2, R);
996
997    if( __TREEOUTPUT__ )
998       PrintS("]},");
999
1000#ifndef SING_NDEBUG
1001    if( __DEBUG__ )
1002    {
1003      m_div.Verify();
1004      m_checker.Verify();
1005    }
1006#endif
1007  } else
1008    t = p_Add_q(t, ReduceTerm(aa, L->m[r], a), R);
1009
1010  p_Delete(&aa, R);
1011
1012  // TODO: print t???
1013
1014  if( __TREEOUTPUT__ )
1015  {
1016    poly tt = pp_Add_qq( a, t, R);  // TODO: ADD a?
1017    PrintS("], \"noderesult\": \""); writeLatexTerm(tt, R, true, false); PrintS("\", \"proc\": \"TraverseNF\" },");
1018    p_Delete(&tt, R);
1019  }
1020#ifndef SING_NDEBUG
1021  if( __DEBUG__ )
1022  {
1023    PrintS("SchreyerSyzygyComputation::TraverseNF(syz_lead, poly syz_2), ==>>> \n");
1024    dPrint(t, R, R, 0);
1025    PrintLn();
1026  }
1027#endif
1028
1029#ifndef SING_NDEBUG
1030  if( __DEBUG__ )
1031  {
1032    m_div.Verify();
1033    m_checker.Verify();
1034  }
1035#endif
1036 
1037  return t;
1038}
1039
1040void SchreyerSyzygyComputation::ComputeSyzygy()
1041{
1042#ifndef SING_NDEBUG
1043  if( __DEBUG__ )
1044  {
1045    m_div.Verify();
1046    m_checker.Verify();
1047  }
1048#endif
1049
1050  assume( m_idLeads != NULL );
1051  assume( m_idTails != NULL );
1052
1053  const ideal& L = m_idLeads;
1054  const ideal& T = m_idTails;
1055
1056  ideal& TT = m_syzTails;
1057  const ring& R = m_rBaseRing;
1058
1059  if( m_sum_bucket == NULL )
1060    m_sum_bucket = sBucketCreate(R);
1061
1062  if( m_spoly_bucket == NULL )
1063    m_spoly_bucket = kBucketCreate(R);
1064
1065
1066  assume( IDELEMS(L) == IDELEMS(T) );
1067#ifndef SING_NDEBUG
1068  int t, r;
1069#endif
1070
1071  if( __TREEOUTPUT__ )
1072  {
1073    Print("\n{ \"syzygylayer\": \"%d\", \"hybridnf\": \"%d\", \"diagrams\": \n[", __SYZNUMBER__, __HYBRIDNF__ );
1074  }
1075
1076  if( m_syzLeads == NULL )
1077  {
1078#ifndef SING_NDEBUG
1079    if( !__TREEOUTPUT__ )
1080    if( TEST_OPT_PROT | 1)
1081    {
1082      t = getTimer(); r = getRTimer();
1083      Print("%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: t: %d, r: %d\n", r, t, r);
1084    }
1085#endif
1086    ComputeLeadingSyzygyTerms( __LEAD2SYZ__ && !__IGNORETAILS__ ); // 2 terms OR 1 term!
1087#ifndef SING_NDEBUG
1088    if( !__TREEOUTPUT__ )
1089    if( TEST_OPT_PROT | 1)
1090    {
1091      t = getTimer() - t; r = getRTimer() - r;
1092      Print("%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::ComputeLeadingSyzygyTerms: dt: %d, dr: %d\n", getRTimer(), t, r);
1093    }
1094#endif
1095
1096  }
1097
1098  assume( m_syzLeads != NULL );
1099  ideal& LL = m_syzLeads;
1100  const int size = IDELEMS(LL);
1101
1102  TT = idInit(size, 0);
1103
1104  if( size == 1 && LL->m[0] == NULL )
1105  {
1106     if( __TREEOUTPUT__ )
1107       PrintS("]},");
1108     return;
1109  }
1110
1111
1112  // use hybrid method?
1113  const bool method = (__HYBRIDNF__  == 1) || (__HYBRIDNF__ == 2 && __SYZNUMBER__ < 3);
1114
1115  if(  !__IGNORETAILS__)
1116  {
1117    if( T != NULL )
1118    {
1119#ifndef SING_NDEBUG
1120      if( !__TREEOUTPUT__ )
1121      if( TEST_OPT_PROT | 1 )
1122      {
1123        t = getTimer(); r = getRTimer();
1124        Print("%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): t: %d, r: %d\n", r, t, r);
1125      }
1126#endif
1127
1128      SetUpTailTerms();
1129#ifndef SING_NDEBUG
1130      if( !__TREEOUTPUT__ )
1131      if( TEST_OPT_PROT | 1)
1132      {
1133        t = getTimer() - t; r = getRTimer() - r;
1134        Print("%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SetUpTailTerms(): dt: %d, dr: %d\n", getRTimer(), t, r);
1135      }
1136#endif
1137    }
1138  }
1139
1140#ifndef SING_NDEBUG
1141  if( !__TREEOUTPUT__ )
1142  if( TEST_OPT_PROT | 1)
1143  {
1144    t = getTimer(); r = getRTimer();
1145    Print("%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: t: %d, r: %d\n", r, t, r);
1146  }
1147#endif
1148
1149#ifndef SING_NDEBUG
1150  if( __DEBUG__ )
1151  {
1152    m_div.Verify();
1153    m_checker.Verify();
1154  }
1155#endif
1156 
1157//  for( int k = 0; k < size; ++k ) // TODO: reversed order =>> ALL wrong :((((
1158  for( int k = size - 1; k >= 0; --k ) 
1159  {
1160    const poly a = LL->m[k]; assume( a != NULL );
1161
1162    poly a2 = pNext(a);
1163
1164    // Splitting 2-terms Leading syzygy module
1165    if( a2 != NULL )
1166      pNext(a) = NULL;
1167
1168    if( __IGNORETAILS__ )
1169    {
1170      TT->m[k] = NULL;
1171
1172      assume( a2 != NULL );
1173
1174      if( a2 != NULL )
1175        p_Delete(&a2, R);
1176
1177      continue;
1178    }
1179
1180    //    TT->m[k] = a2;
1181
1182#ifndef SING_NDEBUG
1183    if( __DEBUG__ )
1184    {
1185      m_div.Verify();
1186      m_checker.Verify();
1187    }
1188#endif
1189
1190    poly nf;
1191   
1192    if( method )
1193      nf = SchreyerSyzygyNF(a, a2);
1194    else
1195      nf = TraverseNF(a, a2); // TODO: WRONG
1196
1197#ifndef SING_NDEBUG
1198    if( __DEBUG__ )
1199    {
1200      m_div.Verify();
1201      m_checker.Verify();
1202    }
1203#endif
1204
1205    TT->m[k] = nf; // ???
1206   
1207#ifndef SING_NDEBUG
1208    if( __DEBUG__ )
1209    {
1210      m_div.Verify();
1211      m_checker.Verify();
1212    }
1213#endif
1214
1215    if( __SYZCHECK__ )     
1216    {
1217#ifndef SING_NDEBUG
1218      if( __DEBUG__ )
1219      {
1220      m_div.Verify();
1221        m_checker.Verify();
1222      }
1223#endif
1224      // TODO: check the correctness (syzygy property): a + TT->m[k] should be a syzygy!!!
1225
1226      poly s = pp_Add_qq( a, TT->m[k], R); // current syzygy
1227
1228      poly vp = p_VectorProductLT(s, L, T, R); 
1229
1230      if( __DEBUG__ && (vp != NULL) && ! __TREEOUTPUT__ )
1231      {
1232        Warn("SchreyerSyzygyComputation::ComputeSyzygy: failed syzygy property for syzygy [%d], non-zero image is as follows: ", k);       
1233        dPrint(vp, R, R, 0);       p_Delete(&vp, R);
1234       
1235        PrintS("SchreyerSyzygyComputation::ComputeSyzygy: Wrong syzygy is as follows: ");
1236        s = pp_Add_qq( a, TT->m[k], R);
1237        dPrint(s, R, R, 0); p_Delete(&s, R);
1238
1239        PrintS("SchreyerSyzygyComputation::ComputeSyzygy: Testing with the other method");
1240       
1241        if( !method )
1242          s = SchreyerSyzygyNF(a, a2);
1243        else
1244          s = TraverseNF(a, a2);
1245
1246        s = p_Add_q( p_Copy(a, R), s, R); // another syzygy // :((((
1247        PrintS("SchreyerSyzygyComputation::ComputeSyzygy: The other method gives the following  syzygy: ");
1248        dPrint(s, R, R, 0); 
1249       
1250        vp = p_VectorProductLT(s, L, T, R);
1251       
1252        if( vp == NULL )
1253        {
1254          PrintS("SchreyerSyzygyComputation::ComputeSyzygy: .... which is correct!!! ");
1255        } else
1256        {
1257          Warn("SchreyerSyzygyComputation::ComputeSyzygy: failed to compute syzygy tail[%d] with both methods!!! Non-zero image (2nd) is as follows: ", k);       
1258          dPrint(vp, R, R, 0);
1259        }
1260
1261#ifndef SING_NDEBUG
1262        if( __DEBUG__ )
1263        {
1264          m_div.Verify();
1265          m_checker.Verify(); 
1266        }
1267#endif
1268       
1269      } else
1270        assume( vp == NULL );
1271
1272      p_Delete(&vp, R);
1273    }
1274
1275#ifndef SING_NDEBUG
1276    if( __DEBUG__ )
1277    {
1278      m_div.Verify();
1279      m_checker.Verify();
1280    }
1281#endif
1282  }
1283
1284#ifndef SING_NDEBUG
1285  if( !__TREEOUTPUT__ )
1286  if( TEST_OPT_PROT | 1)
1287  {
1288    t = getTimer() - t; r = getRTimer() - r;
1289    Print("%% %5d **!TIME4!** SchreyerSyzygyComputation::ComputeSyzygy::SyzygyLift: dt: %d, dr: %d\n", getRTimer(), t, r);
1290  }
1291#endif
1292
1293  TT->rank = id_RankFreeModule(TT, R);
1294
1295  if( __TREEOUTPUT__ )
1296    PrintS("\n]},");
1297}
1298
1299void SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms(bool bComputeSecondTerms)
1300{
1301//  const SchreyerSyzygyComputationFlags& attributes = m_atttributes;
1302
1303//  const BOOLEAN __LEAD2SYZ__   = attributes.__LEAD2SYZ__;
1304//  const BOOLEAN __TAILREDSYZ__ = attributes.__TAILREDSYZ__;
1305
1306  assume( m_syzLeads == NULL );
1307
1308  if( bComputeSecondTerms )
1309  {
1310    assume( __LEAD2SYZ__ );
1311//    m_syzLeads = FROM_NAMESPACE(INTERNAL, _Compute2LeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes));
1312    m_syzLeads = Compute2LeadingSyzygyTerms();
1313  }
1314  else
1315  {
1316    assume( !__LEAD2SYZ__ );
1317
1318    m_syzLeads = Compute1LeadingSyzygyTerms();
1319  }
1320//    m_syzLeads = FROM_NAMESPACE(INTERNAL, _ComputeLeadingSyzygyTerms(m_idLeads, m_rBaseRing, m_atttributes));
1321
1322  // NOTE: set m_LS if tails are to be reduced!
1323  assume( m_syzLeads!= NULL );
1324
1325  if (__TAILREDSYZ__ && !__IGNORETAILS__ && (IDELEMS(m_syzLeads) > 0) && !((IDELEMS(m_syzLeads) == 1) && (m_syzLeads->m[0] == NULL)))
1326  {
1327    m_LS = m_syzLeads;
1328    m_checker.Initialize(m_syzLeads);
1329#ifndef SING_NDEBUG
1330    if( __DEBUG__ )
1331    {
1332      const ring& r = m_rBaseRing;
1333      PrintS("SchreyerSyzygyComputation::ComputeLeadingSyzygyTerms: \n");
1334      PrintS("m_syzLeads: \n");
1335      dPrint(m_syzLeads, r, r, 1);
1336      PrintS("m_checker.Initialize(m_syzLeads) => \n");
1337      m_checker.DebugPrint();
1338    }
1339#endif
1340    assume( m_checker.IsNonempty() ); // TODO: this always fails... BUG????
1341  }
1342}
1343
1344#define NOPRODUCT 0
1345
1346poly SchreyerSyzygyComputation::SchreyerSyzygyNF(const poly syz_lead, poly syz_2) const
1347{
1348  assume( !__IGNORETAILS__ );
1349
1350  const ideal& L = m_idLeads;
1351  const ideal& T = m_idTails;
1352  const ring& r = m_rBaseRing;
1353
1354  assume( syz_lead != NULL );
1355
1356
1357#ifndef SING_NDEBUG
1358  if( __DEBUG__ )
1359  {
1360    PrintS("SchreyerSyzygyComputation::SchreyerSyzygyNF(syz_lead, poly syz_2), \n");
1361    PrintS("syz_lead: \n");
1362    dPrint(syz_lead, r, r, 1);
1363    PrintS("syz_2: \n");
1364    dPrint(syz_2, r, r, 1);
1365    PrintLn();
1366  }
1367#endif
1368
1369  if( __TREEOUTPUT__ )
1370  {
1371    PrintS("{   \"nodelabel\": \""); writeLatexTerm(syz_lead, r);
1372    PrintS("\", \"children\": [");
1373  }
1374
1375  if( syz_2 == NULL )
1376  {
1377    const int rr = p_GetComp(syz_lead, r) - 1;
1378
1379    assume( rr >= 0 && rr < IDELEMS(T) );
1380    assume( rr >= 0 && rr < IDELEMS(L) );
1381
1382#if NOPRODUCT
1383    syz_2 = m_div.FindReducer(syz_lead, L->m[rr], syz_lead, m_checker);
1384
1385    if( __TREEOUTPUT__ )
1386    {
1387      PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_2, r); PrintS("\" },");
1388    }
1389#else
1390    poly aa = leadmonom(syz_lead, r); assume( aa != NULL); // :(
1391    aa = p_Mult_mm(aa, L->m[rr], r);
1392
1393    if( __TREEOUTPUT__ )
1394    {
1395      PrintS("{ \"nodelabel\": \""); writeLatexTerm(syz_2, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(aa, r, false); PrintS("\" },");
1396    }
1397
1398    syz_2 = m_div.FindReducer(aa, syz_lead, m_checker);
1399
1400    p_Delete(&aa, r);
1401#endif
1402
1403  }
1404
1405  assume( syz_2 != NULL ); // by construction of S-Polynomial
1406
1407  assume( L != NULL );
1408  assume( T != NULL );
1409
1410  assume( IDELEMS(L) == IDELEMS(T) );
1411
1412  int  c = p_GetComp(syz_lead, r) - 1;
1413
1414  assume( c >= 0 && c < IDELEMS(T) );
1415
1416  if( m_sum_bucket == NULL )
1417    m_sum_bucket = sBucketCreate(r);
1418
1419  if( m_spoly_bucket == NULL )
1420    m_spoly_bucket = kBucketCreate(r);
1421
1422  sBucket_pt& tail   = m_sum_bucket; assume( tail != NULL );
1423  kBucket_pt& bucket = m_spoly_bucket; assume( bucket != NULL );
1424  kbTest(bucket);
1425
1426
1427//  kBucketInit(bucket, NULL, 0); // not needed!?
1428
1429  poly p = leadmonom(syz_lead, r); // :(
1430//  poly spoly = pp_Mult_qq(p, T->m[c], r);
1431  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // TODO: store pLength(T->m[c]) separately!?
1432  p_Delete(&p, r);
1433
1434  kbTest(bucket);
1435
1436  c = p_GetComp(syz_2, r) - 1;
1437  assume( c >= 0 && c < IDELEMS(T) );
1438
1439  p = leadmonom(syz_2, r); // :(
1440//  spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r);
1441  kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // pLength(T->m[c])?!
1442  kbTest(bucket);
1443  p_Delete(&p, r);
1444
1445  // TODO: use bucket!?
1446//  const bool bUsePolynomial = TEST_OPT_NOT_BUCKETS; //  || (pLength(spoly) < MIN_LENGTH_BUCKET);
1447//  CPolynomialSummator tail(r, bUsePolynomial);
1448  sBucket_Add_p(tail, syz_2, 1); // tail.AddAndDelete(syz_2, 1);
1449
1450  kbTest(bucket);
1451  for( poly spoly = kBucketExtractLm(bucket); spoly != NULL; p_LmDelete(&spoly, r), spoly = kBucketExtractLm(bucket))
1452  {
1453    kbTest(bucket);
1454    poly t = m_div.FindReducer(spoly, NULL, m_checker);
1455
1456    if( t != NULL )
1457    {
1458      p = leadmonom(t, r); // :(
1459      c = p_GetComp(t, r) - 1;
1460
1461      assume( c >= 0 && c < IDELEMS(T) );
1462
1463      if( __TREEOUTPUT__ )
1464      {
1465        PrintS("{ \"nodelabel\": \""); writeLatexTerm(t, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(spoly, r, false); PrintS("\" },");
1466      }
1467
1468      kBucket_Plus_mm_Mult_pp(bucket, p, T->m[c], 0); // pLength(T->m[c])?
1469//      spoly = p_Add_q(spoly, pp_Mult_qq(p, T->m[c], r), r);
1470
1471      p_Delete(&p, r);
1472
1473      sBucket_Add_p(tail, t, 1); // tail.AddAndDelete(t, 1);
1474    } // otherwise discard that leading term altogether!
1475    kbTest(bucket);
1476  }
1477
1478  // now bucket must be empty!
1479  kbTest(bucket);
1480  assume( kBucketClear(bucket) == NULL );
1481
1482  poly result; int len;
1483  sBucketClearAdd(tail, &result, &len); // TODO: use Merge with sBucket???
1484  assume( pLength(result) == len );
1485
1486  if( __TREEOUTPUT__ )
1487  {
1488    PrintS("]},");
1489  }
1490
1491#ifndef SING_NDEBUG
1492  if( __DEBUG__ )
1493  {
1494    PrintS("SchreyerSyzygyComputation::SchreyerSyzygyNF(syz_lead, poly syz_2) =>>> \n");
1495    dPrint(result, r, r, 0);
1496    PrintLn();
1497    // TODO: Add SyzCheck!!!???
1498  }
1499#endif
1500
1501  return result;
1502}
1503
1504// namespace     {
1505
1506// };
1507
1508bool my_p_LmCmp (poly a, poly b, const ring r) { return p_LmCmp(a, b, r) == -1; } // TODO: change to simple lex. memory compare!
1509
1510// NOTE: need p_Copy?????? for image + multiplier!!???
1511// NOTE: better store complete syz. terms!!?
1512poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, const int tail) const
1513{
1514#ifndef SING_NDEBUG
1515  if( __DEBUG__ )
1516  {
1517    m_div.Verify();
1518    m_checker.Verify();
1519  }
1520#endif
1521
1522  const ring& r = m_rBaseRing;
1523
1524  assume(m_idTails !=  NULL && m_idTails->m != NULL);
1525  assume( tail >= 0 && tail < IDELEMS(m_idTails) );
1526
1527/*  return ComputeImage(multiplier, tail); */
1528
1529  // TODO: store (multiplier, tail) -.-^-.-^-.--> !
1530  TCache::iterator top_itr = m_cache.find(tail);
1531
1532  if ( top_itr != m_cache.end() )
1533  {
1534     assume( top_itr->first == tail );
1535
1536     TP2PCache& T = top_itr->second;
1537
1538     TP2PCache::iterator itr = T.find(multiplier);
1539
1540     if( itr != T.end() ) // Yey - Reuse!!!
1541     {
1542       assume( p_LmEqual(itr->first, multiplier, r) );
1543
1544       if( itr->second == NULL )
1545         return (NULL);
1546
1547       poly p = p_Copy(itr->second, r); // no copy???
1548
1549       if( __TREEOUTPUT__ )
1550       {
1551//         PrintS("{ \"nodelabel\": \""); writeLatexTerm(multiplier, r, false);
1552//         Print("  \\\\GEN{%d}\", \"children\": [ ", tail + 1);
1553         PrintS("{ \"proc\": \"TraverseTail-lookup\", \"nodelabel\": \"");
1554         writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"look-up-poly\": \"", tail + 1);
1555         writeLatexTerm(p, r, true, false);
1556         PrintS("\", ");
1557       }
1558
1559       if( !n_Equal( pGetCoeff(multiplier), pGetCoeff(itr->first), r) ) // normalize coeffs!?
1560       {
1561         number n = n_Div( pGetCoeff(multiplier), pGetCoeff(itr->first), r);
1562         p = p_Mult_nn(p, n, r);
1563         n_Delete(&n, r);
1564
1565         if( __TREEOUTPUT__ )
1566           PrintS("\"rescale\": \"1\", ");
1567       } else
1568       {
1569         if( __TREEOUTPUT__ )
1570           PrintS("\"rescale\": \"0\", ");
1571       }
1572
1573       if( __TREEOUTPUT__ )
1574       {
1575         PrintS("\"noderesult\": \"");
1576         writeLatexTerm(p, r, true, false);
1577         PrintS("\" },");
1578       }
1579
1580#ifndef SING_NDEBUG
1581       if( __DEBUG__ )
1582       {
1583         m_div.Verify();
1584         m_checker.Verify();
1585       }
1586#endif
1587       
1588       return p;
1589     }
1590
1591
1592     if( __TREEOUTPUT__ )
1593     {
1594       PrintS("{ \"nodelabel\": \""); writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"children\": [", tail + 1);
1595     }
1596     
1597     const poly p = ComputeImage(multiplier, tail);
1598
1599     T.insert( TP2PCache::value_type(p_Copy(multiplier, r), p) ); //     T[ multiplier ] = p;
1600
1601//     if( p == NULL )
1602//        return (NULL);
1603
1604     if( __TREEOUTPUT__ )
1605     {
1606       PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\", \"proc\": \"TraverseTail-compute-and-store1\" },");
1607     }
1608
1609#ifndef SING_NDEBUG
1610     if( __DEBUG__ )
1611     {
1612       m_div.Verify();
1613       m_checker.Verify();
1614     }
1615#endif
1616     
1617     return p_Copy(p, r);
1618  }
1619
1620  CCacheCompare o(r); TP2PCache T(o);
1621
1622  if( __TREEOUTPUT__ )
1623  {
1624    PrintS("{ \"nodelabel\": \""); writeLatexTerm(multiplier, r, false); Print(" \\\\GEN{%d}\", \"children\": [", tail + 1);
1625  }
1626
1627
1628  const poly p = ComputeImage(multiplier, tail);
1629
1630  T.insert( TP2PCache::value_type(p_Copy(multiplier, r), p) );
1631
1632  m_cache.insert( TCache::value_type(tail, T) );
1633
1634//  if( p == NULL )
1635//    return (NULL);
1636
1637  if( __TREEOUTPUT__ )
1638  {
1639    PrintS("], \"noderesult\": \""); writeLatexTerm(p, r, true, false); PrintS("\", \"proc\": \"TraverseTail-compute-and-store2\" },");
1640  }
1641
1642#ifndef SING_NDEBUG
1643  if( __DEBUG__ )
1644  {
1645    m_div.Verify();
1646    m_checker.Verify();
1647  }
1648#endif
1649
1650  return p_Copy(p, r);
1651}
1652
1653poly SchreyerSyzygyComputation::ComputeImage(poly multiplier, const int tail) const
1654{
1655  const poly t = m_idTails->m[tail]; // !!!
1656
1657  if(t != NULL)
1658    return TraverseTail(multiplier, t);
1659
1660  return NULL;
1661}
1662
1663
1664poly SchreyerSyzygyComputation::TraverseTail(poly multiplier, poly tail) const
1665{
1666#ifndef SING_NDEBUG
1667  if( __DEBUG__ )
1668  {
1669    m_div.Verify();
1670    m_checker.Verify();
1671  }
1672#endif
1673
1674  assume( !__IGNORETAILS__ );
1675
1676  const ideal& L = m_idLeads;
1677  const ideal& T = m_idTails;
1678  const ring& r = m_rBaseRing;
1679
1680  assume( multiplier != NULL );
1681
1682  assume( L != NULL );
1683  assume( T != NULL );
1684
1685
1686  if( (!__TAILREDSYZ__) || m_lcm.Check(multiplier) )
1687  {
1688//    const bool bUsePolynomial = TEST_OPT_NOT_BUCKETS; //  || (pLength(tail) < MIN_LENGTH_BUCKET);
1689    if( m_sum_bucket == NULL )
1690      m_sum_bucket = sBucketCreate(r);
1691
1692    sBucket_pt& sum   = m_sum_bucket; assume( sum != NULL );
1693    poly s; int len;
1694
1695//    CPolynomialSummator sum(r, bUsePolynomial);
1696//    poly s = NULL;
1697    for(poly p = tail; p != NULL; p = pNext(p))   // iterate over the tail
1698    {
1699      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1700      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1701      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1702      const poly rt = ReduceTerm(multiplier, p, NULL); // TODO: also return/store length?
1703      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1704      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1705      // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
1706
1707      const int lp = pLength(rt);
1708      if( rt != NULL && lp != 0 )
1709        sBucket_Add_p(sum, rt, lp);
1710    }
1711
1712    sBucketClearAdd(sum, &s, &len);
1713    assume( pLength(s) == len );
1714#ifndef SING_NDEBUG
1715    if( __DEBUG__ )
1716    {
1717      m_div.Verify();
1718      m_checker.Verify();
1719    }
1720#endif
1721
1722    return s;
1723  }
1724
1725#ifndef SING_NDEBUG
1726  if( __DEBUG__ )
1727  {
1728    m_div.Verify();
1729    m_checker.Verify();
1730  }
1731#endif
1732
1733  return NULL;
1734
1735}
1736
1737
1738
1739
1740poly SchreyerSyzygyComputation::ReduceTerm(poly multiplier, poly term4reduction, poly syztermCheck) const
1741{
1742#ifndef SING_NDEBUG
1743  if( __DEBUG__ )
1744  {
1745    m_div.Verify();
1746    m_checker.Verify();
1747  }
1748#endif
1749
1750  assume( !__IGNORETAILS__ );
1751
1752  const ideal& L = m_idLeads;
1753  const ideal& T = m_idTails;
1754  const ring& r = m_rBaseRing;
1755
1756  assume( multiplier != NULL );
1757  assume( term4reduction != NULL );
1758
1759
1760  assume( L != NULL );
1761  assume( T != NULL );
1762
1763  // simple implementation with FindReducer:
1764  poly s = NULL;
1765
1766  if( (!__TAILREDSYZ__) || m_lcm.Check(multiplier) )
1767  {
1768#if NOPRODUCT
1769    s = m_div.FindReducer(multiplier, term4reduction, syztermCheck, m_checker);
1770   
1771    if( s == NULL ) // No Reducer?
1772     return s;
1773
1774    if( __TREEOUTPUT__ )
1775    {
1776      poly product = pp_Mult_mm(multiplier, term4reduction, r);
1777      PrintS("{ \"proc\": \"ReduceTerm-NOPRODUCT\", \"nodelabel\": \""); writeLatexTerm(s, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(product, r, false);
1778      p_Delete(&product, r);
1779    }
1780
1781#else
1782    // NOTE: only LT(term4reduction) should be used in the following:
1783    poly product = pp_Mult_mm(multiplier, term4reduction, r);
1784    s = m_div.FindReducer(product, syztermCheck, m_checker); // ??
1785
1786    if( s == NULL ) // No Reducer?
1787     return s;
1788
1789    if( __TREEOUTPUT__ )
1790    {
1791      PrintS("{ \"proc\": \"ReduceTerm-PRODUCT\", \"nodelabel\": \""); writeLatexTerm(s, r); PrintS("\", \"edgelabel\": \""); writeLatexTerm(product, r, false);
1792    }
1793
1794    p_Delete(&product, r);
1795#endif
1796  }
1797
1798#ifndef SING_NDEBUG
1799  if( __DEBUG__ )
1800  {
1801    m_div.Verify();
1802    m_checker.Verify();
1803  }
1804#endif
1805
1806#ifndef SING_NDEBUG
1807  if( __DEBUG__ )
1808  {
1809    m_div.Verify();
1810    m_checker.Verify();
1811  }
1812#endif
1813 
1814  if( s == NULL ) // No Reducer?
1815    return s;
1816
1817
1818  poly b = leadmonom(s, r);
1819
1820  const int c = p_GetComp(s, r) - 1;
1821  assume( c >= 0 && c < IDELEMS(T) );
1822
1823
1824  if( __TREEOUTPUT__ )
1825     PrintS("\", \"children\": [");
1826
1827  const poly t = TraverseTail(b, c); // T->m[c];
1828
1829  if( t != NULL )
1830    s = p_Add_q(s, t, r);
1831
1832  if( __TREEOUTPUT__ )
1833  {
1834
1835    PrintS("], \"noderesult\": \"");
1836    writeLatexTerm(s, r, true, false);
1837    PrintS("\" },"); 
1838  }
1839
1840#ifndef SING_NDEBUG
1841  if( __DEBUG__ )
1842  {
1843    m_div.Verify();
1844    m_checker.Verify();
1845  }
1846#endif
1847
1848 
1849  return s;
1850}
1851
1852SchreyerSyzygyComputationFlags::SchreyerSyzygyComputationFlags(idhdl rootRingHdl):
1853    __DEBUG__( atGetInt(rootRingHdl,"DEBUG", 0) ),
1854    __LEAD2SYZ__( atGetInt(rootRingHdl, "LEAD2SYZ", 0) ),
1855    __TAILREDSYZ__( atGetInt(rootRingHdl, "TAILREDSYZ", 1) ),
1856    __HYBRIDNF__( atGetInt(rootRingHdl, "HYBRIDNF", 1) ),
1857    __IGNORETAILS__( atGetInt(rootRingHdl, "IGNORETAILS", 0) ),
1858    __SYZNUMBER__( atGetInt(rootRingHdl, "SYZNUMBER", 0) ),
1859    __TREEOUTPUT__( atGetInt(rootRingHdl, "TREEOUTPUT", 0) ),
1860    __SYZCHECK__( atGetInt(rootRingHdl, "SYZCHECK", 0) ),
1861    m_rBaseRing( rootRingHdl->data.uring )
1862{
1863#ifndef SING_NDEBUG
1864  if( __DEBUG__ )
1865  {
1866    PrintS("SchreyerSyzygyComputationFlags: \n");
1867    Print("        DEBUG: \t%d\n", __DEBUG__);
1868//    Print("   SYZCHECK  : \t%d\n", __SYZCHECK__);
1869    Print("     LEAD2SYZ: \t%d\n", __LEAD2SYZ__);
1870    Print("   TAILREDSYZ: \t%d\n", __TAILREDSYZ__);
1871    Print("  IGNORETAILS: \t%d\n", __IGNORETAILS__);
1872    Print("   TREEOUTPUT: \t%d\n", __TREEOUTPUT__);
1873    Print("     SYZCHECK: \t%d\n", __SYZCHECK__);
1874  }
1875#endif
1876
1877  // TODO: just current setting!
1878  assume( rootRingHdl == currRingHdl );
1879  assume( rootRingHdl->typ == RING_CMD );
1880  assume( m_rBaseRing == currRing );
1881  // move the global ring here inside???
1882}
1883
1884
1885
1886CLeadingTerm::CLeadingTerm(unsigned int _label,  const poly _lt, const ring R):
1887    m_sev( p_GetShortExpVector(_lt, R) ),  m_label( _label ),  m_lt( _lt )
1888#ifndef SING_NDEBUG
1889    , _R(R), m_lt_copy( p_Copy(_lt, R) )
1890#endif 
1891   
1892{
1893  assume( pNext(_lt) == NULL );
1894  assume( sev() == p_GetShortExpVector(lt(), R) );
1895}
1896
1897CLeadingTerm::~CLeadingTerm()
1898{
1899#ifndef SING_NDEBUG
1900  assume( p_EqualPolys(m_lt, m_lt_copy, _R) );
1901  assume( m_sev == p_GetShortExpVector(m_lt, _R) );
1902 
1903  poly p = const_cast<poly>(m_lt_copy);
1904  p_Delete(&p, _R);
1905#endif 
1906}
1907
1908poly CLeadingTerm::lt() const
1909{
1910#ifndef SING_NDEBUG
1911//  assume( (long)(*m_lt) == (long)(*m_lt_copy) );
1912  assume( p_EqualPolys(m_lt, m_lt_copy, _R) );
1913  assume( m_sev == p_GetShortExpVector(m_lt, _R) ); 
1914#endif
1915  return m_lt;
1916}
1917unsigned long CLeadingTerm::sev() const
1918{
1919#ifndef SING_NDEBUG
1920  assume( p_EqualPolys(m_lt, m_lt_copy, _R) );
1921  assume( m_sev == p_GetShortExpVector(m_lt, _R) ); 
1922#endif
1923  return m_sev;
1924}
1925
1926unsigned int CLeadingTerm::label() const
1927{
1928#ifndef SING_NDEBUG
1929  assume( p_EqualPolys(m_lt, m_lt_copy, _R) );
1930  assume( m_sev == p_GetShortExpVector(m_lt, _R) ); 
1931#endif
1932  return m_label;
1933}
1934
1935
1936
1937CReducerFinder::~CReducerFinder()
1938{
1939  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++ )
1940  {
1941    const TReducers& v = it->second;
1942    for(TReducers::const_iterator vit = v.begin(); vit != v.end(); vit++ )
1943      delete const_cast<CLeadingTerm*>(*vit);
1944  }
1945}
1946
1947
1948void CReducerFinder::Initialize(const ideal L)
1949{
1950  assume( m_L == NULL || m_L == L );
1951  if( m_L == NULL )
1952    m_L = L;
1953
1954  assume( m_L == L );
1955
1956  if( L != NULL )
1957  {
1958    const ring& R = m_rBaseRing;
1959    assume( R != NULL );
1960
1961    for( int k = IDELEMS(L) - 1; k >= 0; k-- )
1962    {
1963      const poly a = L->m[k]; // assume( a != NULL );
1964
1965      // NOTE: label is k \in 0 ... |L|-1!!!
1966      if( a != NULL )
1967        m_hash[p_GetComp(a, R)].push_back( new CLeadingTerm(k, a, R) );
1968    }
1969  }
1970}
1971
1972CReducerFinder::CReducerFinder(const ideal L, const SchreyerSyzygyComputationFlags& flags):
1973    SchreyerSyzygyComputationFlags(flags),
1974    m_L(const_cast<ideal>(L)), // for debug anyway
1975    m_hash()
1976{
1977  assume( flags.m_rBaseRing == m_rBaseRing );
1978  if( L != NULL )
1979    Initialize(L);
1980}
1981
1982/// _p_LmDivisibleByNoComp for a | b*c
1983static inline BOOLEAN _p_LmDivisibleByNoComp(const poly a, const poly b, const poly c, const ring r)
1984{
1985  int i=r->VarL_Size - 1;
1986  unsigned long divmask = r->divmask;
1987  unsigned long la, lb;
1988
1989  if (r->VarL_LowIndex >= 0)
1990  {
1991    i += r->VarL_LowIndex;
1992    do
1993    {
1994      la = a->exp[i];
1995      lb = b->exp[i] + c->exp[i];
1996      if ((la > lb) ||
1997          (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
1998      {
1999        pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == FALSE);
2000        return FALSE;
2001      }
2002      i--;
2003    }
2004    while (i>=r->VarL_LowIndex);
2005  }
2006  else
2007  {
2008    do
2009    {
2010      la = a->exp[r->VarL_Offset[i]];
2011      lb = b->exp[r->VarL_Offset[i]] + c->exp[r->VarL_Offset[i]];
2012      if ((la > lb) ||
2013          (((la & divmask) ^ (lb & divmask)) != ((lb - la) & divmask)))
2014      {
2015        pDivAssume(p_DebugLmDivisibleByNoComp(a, b, r) == FALSE);
2016        return FALSE;
2017      }
2018      i--;
2019    }
2020    while (i>=0);
2021  }
2022#ifdef HAVE_RINGS
2023  assume( !rField_is_Ring(r) ); // not implemented for rings...!
2024#endif
2025  return TRUE;
2026}
2027
2028
2029bool CLeadingTerm::CheckLT( const ideal & L ) const
2030{
2031//  for( int i = IDELEMS(L); i >= 0; --i) assume( pNext(L->m[i]) == NULL ); // ???
2032  return ( L->m[label()] == lt() );
2033} 
2034
2035bool CLeadingTerm::DivisibilityCheck(const poly product, const unsigned long not_sev, const ring r) const
2036{
2037  // may have no coeff yet
2038//  assume ( !n_IsZero( p_GetCoeff(product, r), r ) );
2039
2040  assume ( !n_IsZero( p_GetCoeff(lt(), r), r ) );
2041  assume( sev() == p_GetShortExpVector(lt(), r) );
2042
2043  assume( product != NULL );
2044  assume( (p_GetComp(lt(), r) == p_GetComp(product, r)) || (p_GetComp(lt(), r) == 0) ); 
2045
2046#ifndef SING_NDEBUG
2047  assume( r == _R );
2048#endif   
2049 
2050//  const int k = label();
2051//  assume( m_L->m[k] == p );
2052
2053  return p_LmShortDivisibleByNoComp(lt(), sev(), product, not_sev, r);
2054
2055}
2056
2057/// as DivisibilityCheck(multiplier * t, ...) for monomial 'm'
2058/// and a module term 't'
2059bool CLeadingTerm::DivisibilityCheck(const poly m, const poly t, const unsigned long not_sev, const ring r) const
2060{
2061  assume ( !n_IsZero( p_GetCoeff(lt(), r), r ) );
2062  assume( sev() == p_GetShortExpVector(lt(), r) );
2063
2064  assume( m != NULL );
2065  assume( t != NULL ); 
2066  assume ( !n_IsZero( p_GetCoeff(m, r), r ) );
2067  assume ( !n_IsZero( p_GetCoeff(t, r), r ) );
2068
2069// assume( p_GetComp(m, r) == 0 );
2070  assume( (p_GetComp(lt(), r) == p_GetComp(t, r))  || (p_GetComp(lt(), r) == 0)  );
2071
2072//  const int k = label();
2073//  assume( m_L->m[k] == p );
2074
2075#ifndef SING_NDEBUG
2076  assume( r == _R );
2077#endif   
2078 
2079  if (sev() & not_sev)
2080    return false;
2081
2082  return _p_LmDivisibleByNoComp(lt(), m, t, r);
2083//  return p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r);
2084}
2085
2086
2087
2088/// TODO:
2089class CDivisorEnumerator: public SchreyerSyzygyComputationFlags
2090{
2091  private:
2092    const CReducerFinder& m_reds;
2093    const poly m_product;
2094    const unsigned long m_not_sev;
2095    const long m_comp;
2096
2097    CReducerFinder::CReducersHash::const_iterator m_itr;
2098    CReducerFinder::TReducers::const_iterator m_current, m_finish;
2099
2100    bool m_active;
2101
2102  public:
2103    CDivisorEnumerator(const CReducerFinder& self, const poly product):
2104        SchreyerSyzygyComputationFlags(self),
2105        m_reds(self),
2106        m_product(product),
2107        m_not_sev(~p_GetShortExpVector(product, m_rBaseRing)),
2108        m_comp(p_GetComp(product, m_rBaseRing)),
2109        m_itr(), m_current(), m_finish(),
2110        m_active(false)
2111    {
2112      assume( m_comp >= 0 );
2113      assume( m_reds.m_L != NULL ); /// TODO: m_L should stay the same!!!
2114     
2115      assume( product != NULL ); // may have no coeff yet :(
2116//      assume ( !n_IsZero( p_GetCoeff(product, m_rBaseRing), m_rBaseRing ) );
2117#ifndef SING_NDEBUG
2118      if( __DEBUG__ )
2119        m_reds.Verify();
2120#endif
2121    }
2122
2123    inline bool Reset()
2124    {
2125      m_active = false;
2126
2127      m_itr = m_reds.m_hash.find(m_comp);
2128
2129      if( m_itr == m_reds.m_hash.end() )
2130        return false;
2131
2132      assume( m_itr->first == m_comp );
2133
2134      m_current = (m_itr->second).begin();
2135      m_finish = (m_itr->second).end();
2136
2137      if (m_current == m_finish)
2138        return false;
2139
2140//      m_active = true;
2141      return true;
2142    }
2143
2144    const CLeadingTerm& Current() const
2145    {
2146      assume( m_active );
2147      assume( m_current != m_finish );
2148
2149      return *(*m_current);
2150    }
2151
2152    inline bool MoveNext()
2153    {
2154      assume( m_current != m_finish );
2155
2156      if( m_active )
2157        ++m_current;
2158      else
2159        m_active = true; // for Current()
2160
2161      // looking for the next good entry
2162      for( ; m_current != m_finish; ++m_current )
2163      {
2164        assume( Current().CheckLT( m_reds.m_L ) );
2165
2166        if( Current().DivisibilityCheck(m_product, m_not_sev, m_rBaseRing) )
2167        {
2168#ifndef SING_NDEBUG
2169          if( __DEBUG__ )
2170          {
2171            Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().label());
2172            dPrint(Current().lt(), m_rBaseRing, m_rBaseRing, 1);
2173          }
2174#endif
2175//          m_active = true;
2176          assume( Current().CheckLT( m_reds.m_L ) );
2177          return true;
2178        }
2179        assume( Current().CheckLT( m_reds.m_L ) );       
2180      }
2181
2182      // the end... :(
2183      assume( m_current == m_finish );
2184
2185      m_active = false;
2186      return false;
2187    }
2188};
2189
2190
2191
2192bool CReducerFinder::IsDivisible(const poly product) const
2193{
2194#ifndef SING_NDEBUG
2195  if( __DEBUG__ )
2196    DebugPrint();
2197#endif
2198 
2199  assume( product != NULL );
2200
2201  // NOTE: q may have no coeff!!! 
2202
2203  CDivisorEnumerator itr(*this, product);
2204  if( !itr.Reset() )
2205    return false;
2206
2207  return itr.MoveNext();
2208
2209/*
2210  const ring& r = m_rBaseRing;
2211
2212  const long comp = p_GetComp(product, r);
2213  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
2214
2215  assume( comp >= 0 );
2216
2217  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2218
2219  assume( m_L != NULL );
2220
2221  if( it == m_hash.end() )
2222    return false;
2223  // assume comp!
2224
2225  const TReducers& reducers = it->second;
2226
2227  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2228  {
2229    assume( (*vit)->CheckLT( m_L ) );
2230
2231    if( (*vit)->DivisibilityCheck(product, not_sev, r) )
2232    {
2233      if( __DEBUG__ )
2234      {
2235        Print("_FindReducer::Test LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + (*vit)->label());
2236        dPrint((*vit)->lt(), r, r, 1);
2237      }
2238
2239      return true;
2240    }
2241  }
2242
2243  return false;
2244*/
2245}
2246
2247
2248#ifndef SING_NDEBUG
2249void CReducerFinder::Verify() const
2250{
2251  const ring& r = m_rBaseRing;
2252
2253  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
2254  {
2255    const TReducers& reducers = it->second;
2256
2257    for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2258    {
2259      assume( (*vit)->CheckLT( m_L ) );
2260     
2261      const poly p = (*vit)->lt();
2262     
2263      const unsigned long p_sev = (*vit)->sev();
2264      assume( p_sev == p_GetShortExpVector(p, r) );
2265     
2266      assume( p_GetComp(p, r) == it->first );
2267
2268      const int k = (*vit)->label();       
2269      assume( m_L->m[k] == p );
2270       
2271      pp_Test(p, r, r);
2272    }
2273  }
2274}
2275   
2276   
2277
2278void CReducerFinder::DebugPrint() const
2279{
2280  const ring& r = m_rBaseRing;
2281
2282  for( CReducersHash::const_iterator it = m_hash.begin(); it != m_hash.end(); it++)
2283  {
2284    Print("Hash Key: %ld, Values: \n", it->first);
2285    const TReducers& reducers = it->second;
2286
2287    for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2288    {
2289      assume( (*vit)->CheckLT( m_L ) );
2290     
2291      const int k = (*vit)->label();
2292      const poly p = (*vit)->lt();
2293       
2294      pp_Test(p, r, r);
2295     
2296      assume( m_L->m[k] == p );
2297
2298      const unsigned long p_sev = (*vit)->sev();
2299      assume( p_sev == p_GetShortExpVector(p, r) );
2300     
2301      assume( p_GetComp(p, r) == it->first );
2302
2303      Print("L[%d]: ", k); dPrint(p, r, r, 0); Print("SEV: %ld\n", p_sev);
2304     
2305      assume( m_L->m[k] == p );
2306    }
2307  }
2308}
2309#endif
2310
2311/// TODO:
2312class CDivisorEnumerator2: public SchreyerSyzygyComputationFlags
2313{
2314  private:
2315    const CReducerFinder& m_reds;
2316    const poly m_multiplier, m_term;
2317    const unsigned long m_not_sev;
2318    const long m_comp;
2319
2320    CReducerFinder::CReducersHash::const_iterator m_itr;
2321    CReducerFinder::TReducers::const_iterator m_current, m_finish;
2322
2323    bool m_active;
2324
2325  public:
2326    CDivisorEnumerator2(const CReducerFinder& self, const poly m, const poly t):
2327        SchreyerSyzygyComputationFlags(self),
2328        m_reds(self),
2329        m_multiplier(m), m_term(t),
2330        m_not_sev(~p_GetShortExpVector(m, t, m_rBaseRing)),
2331        m_comp(p_GetComp(t, m_rBaseRing)),
2332        m_itr(), m_current(), m_finish(),
2333        m_active(false)
2334    {
2335      assume( m_comp >= 0 );
2336      assume( m_reds.m_L != NULL );
2337      assume( m_multiplier != NULL );
2338      assume( m_term != NULL );
2339     
2340      assume( m != NULL );
2341      assume( t != NULL ); 
2342      assume ( !n_IsZero( p_GetCoeff(m, m_rBaseRing), m_rBaseRing ) );
2343      assume ( !n_IsZero( p_GetCoeff(t, m_rBaseRing), m_rBaseRing ) );
2344     
2345//      assume( p_GetComp(m_multiplier, m_rBaseRing) == 0 );
2346#ifndef SING_NDEBUG
2347      if( __DEBUG__ )
2348        m_reds.Verify();
2349#endif
2350    }
2351
2352    inline bool Reset()
2353    {
2354      m_active = false;
2355
2356      m_itr = m_reds.m_hash.find(m_comp);
2357
2358      if( m_itr == m_reds.m_hash.end() )
2359        return false;
2360
2361      assume( m_itr->first == m_comp );
2362
2363      m_current = (m_itr->second).begin();
2364      m_finish = (m_itr->second).end();
2365
2366      if (m_current == m_finish)
2367        return false;
2368
2369      return true;
2370    }
2371
2372    const CLeadingTerm& Current() const
2373    {
2374      assume( m_active );
2375      assume( m_current != m_finish );
2376
2377      return *(*m_current);
2378    }
2379
2380    inline bool MoveNext()
2381    {
2382      assume( m_current != m_finish );
2383
2384      if( m_active )
2385        ++m_current;
2386      else
2387        m_active = true;
2388
2389
2390      // looking for the next good entry
2391      for( ; m_current != m_finish; ++m_current )
2392      {
2393        assume( Current().CheckLT( m_reds.m_L ) );
2394
2395        if( Current().DivisibilityCheck(m_multiplier, m_term, m_not_sev, m_rBaseRing) )
2396        {
2397#ifndef SING_NDEBUG
2398          if( __DEBUG__ )
2399          {
2400            Print("CDivisorEnumerator::MoveNext::est LS: q is divisible by LS[%d] !:((, diviser is: ", 1 + Current().label());
2401            dPrint(Current().lt(), m_rBaseRing, m_rBaseRing, 1);
2402          }
2403#endif
2404//          m_active = true;
2405          assume( Current().CheckLT( m_reds.m_L ) );       
2406          return true;
2407
2408        }
2409        assume( Current().CheckLT( m_reds.m_L ) );       
2410      }
2411
2412      // the end... :(
2413      assume( m_current == m_finish );
2414
2415      m_active = false;
2416      return false;
2417    }
2418};
2419
2420poly CReducerFinder::FindReducer(const poly multiplier, const poly t,
2421                                 const poly syzterm,
2422                                 const CReducerFinder& syz_checker) const
2423{
2424#ifndef SING_NDEBUG
2425  if( __DEBUG__ )
2426  {
2427    DebugPrint();
2428    syz_checker.Verify();
2429  }
2430#endif
2431
2432  CDivisorEnumerator2 itr(*this, multiplier, t);
2433  if( !itr.Reset() )
2434    return NULL;
2435
2436  // don't care about the module component of multiplier (as it may be the syzygy term)
2437  // product = multiplier * t?
2438  const ring& r = m_rBaseRing;
2439
2440  assume( multiplier != NULL ); assume( t != NULL );
2441
2442  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
2443
2444  long c = 0;
2445
2446  if (syzterm != NULL)
2447    c = p_GetComp(syzterm, r) - 1;
2448
2449  assume( c >= 0 && c < IDELEMS(L) );
2450
2451  if (__DEBUG__ && (syzterm != NULL))
2452  {
2453    const poly m = L->m[c]; assume( m != NULL ); assume( pNext(m) == NULL );
2454
2455    //  def @@c = leadcomp(syzterm); int @@r = int(@@c);
2456    //  def @@product = leadmonomial(syzterm) * L[@@r];
2457    poly lm = p_Mult_mm( leadmonom(syzterm, r, true), m, r); // !NC :(
2458    poly pr = p_Mult_q( leadmonom(multiplier, r, true), leadmonom(t, r, false), r); // !NC :(
2459
2460    assume( p_EqualPolys(lm, pr, r) );
2461
2462    p_Delete(&lm, r);
2463    p_Delete(&pr, r);
2464  }
2465
2466#ifndef SING_NDEBUG
2467  if( __DEBUG__ )
2468  {
2469    DebugPrint();
2470    syz_checker.Verify();
2471  }
2472#endif
2473 
2474  const BOOLEAN to_check = (syz_checker.IsNonempty()); // __TAILREDSYZ__ &&
2475
2476  const poly q = p_New(r); pNext(q) = NULL;
2477
2478  if( __DEBUG__ )
2479    p_SetCoeff0(q, 0, r); // for printing q
2480
2481  while( itr.MoveNext() )
2482  {
2483    assume( itr.Current().CheckLT( L ) ); // ???
2484   
2485    const poly p = itr.Current().lt(); // ???
2486    const int k  = itr.Current().label();
2487
2488    p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t // TODO: do it once?
2489    p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
2490
2491    p_SetComp(q, k + 1, r);
2492    p_Setm(q, r);
2493
2494    // cannot allow something like: a*gen(i) - a*gen(i)
2495    if (syzterm != NULL && (k == c))
2496      if (p_ExpVectorEqual(syzterm, q, r))
2497      {
2498#ifndef SING_NDEBUG
2499        if( __DEBUG__ )
2500        {
2501          Print("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2502          dPrint(syzterm, r, r, 1);
2503        }
2504#endif
2505        assume( itr.Current().CheckLT( L ) ); // ???
2506        continue;
2507      }
2508
2509    // while the complement (the fraction) is not reducible by leading syzygies
2510    if( to_check && syz_checker.IsDivisible(q) )
2511    {
2512#ifndef SING_NDEBUG
2513      if( __DEBUG__ )
2514      {
2515        PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2516      }
2517#endif
2518      assume( itr.Current().CheckLT( L ) ); // ???
2519      continue;
2520    }
2521
2522    number n = n_Mult( p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
2523    p_SetCoeff0(q, n_InpNeg( n_Div(n, p_GetCoeff(p, r), r), r), r);
2524    n_Delete(&n, r);
2525
2526#ifndef SING_NDEBUG
2527    if( __DEBUG__ )
2528    {
2529      DebugPrint();
2530      syz_checker.Verify();
2531    }
2532#endif
2533   
2534    assume( itr.Current().CheckLT( L ) ); // ???
2535    return q;
2536  }
2537
2538/*
2539  const long comp = p_GetComp(t, r); assume( comp >= 0 );
2540  const unsigned long not_sev = ~p_GetShortExpVector(multiplier, t, r); // !
2541
2542//   for( int k = IDELEMS(L)-1; k>= 0; k-- )
2543//   {
2544//     const poly p = L->m[k];
2545//
2546//     if ( p_GetComp(p, r) != comp )
2547//       continue;
2548//
2549//     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
2550
2551   // looking for an appropriate diviser p = L[k]...
2552  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2553
2554  if( it == m_hash.end() )
2555    return NULL;
2556
2557  // assume comp!
2558
2559  assume( m_L != NULL );
2560
2561  const TReducers& reducers = it->second;
2562
2563  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2564  {
2565
2566    const poly p = (*vit)->lt(); // ??
2567    const int k = (*vit)->label();
2568
2569    assume( L->m[k] == p ); // CheckLT
2570
2571//    const unsigned long p_sev = (*vit)->sev();
2572//    assume( p_sev == p_GetShortExpVector(p, r) );
2573
2574//    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2575//      continue;
2576
2577    if( !(*vit)->DivisibilityCheck(multiplier, t, not_sev, r) )
2578      continue;
2579
2580
2581//    if (p_sev & not_sev) continue;
2582//    if( !_p_LmDivisibleByNoComp(p, multiplier, t, r) ) continue;
2583
2584
2585    p_ExpVectorSum(q, multiplier, t, r); // q == product == multiplier * t
2586    p_ExpVectorDiff(q, q, p, r); // (LM(product) / LM(L[k]))
2587
2588    p_SetComp(q, k + 1, r);
2589    p_Setm(q, r);
2590
2591    // cannot allow something like: a*gen(i) - a*gen(i)
2592    if (syzterm != NULL && (k == c))
2593      if (p_ExpVectorEqual(syzterm, q, r))
2594      {
2595        if( __DEBUG__ )
2596        {
2597          Print("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2598          dPrint(syzterm, r, r, 1);
2599        }
2600
2601        continue;
2602      }
2603
2604    // while the complement (the fraction) is not reducible by leading syzygies
2605    if( to_check && syz_checker.IsDivisible(q) )
2606    {
2607      if( __DEBUG__ )
2608      {
2609        PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2610      }
2611
2612      continue;
2613    }
2614
2615    number n = n_Mult( p_GetCoeff(multiplier, r), p_GetCoeff(t, r), r);
2616    p_SetCoeff0(q, n_InpNeg( n_Div(n, p_GetCoeff(p, r), r), r), r);
2617    n_Delete(&n, r);
2618
2619    return q;
2620  }
2621*/
2622
2623  p_LmFree(q, r);
2624 
2625#ifndef SING_NDEBUG
2626  if( __DEBUG__ )
2627  {
2628    DebugPrint();
2629    syz_checker.Verify();
2630  }
2631#endif
2632
2633  return NULL;
2634
2635}
2636
2637
2638poly CReducerFinder::FindReducer(const poly product, const poly syzterm, const CReducerFinder& syz_checker) const
2639{
2640
2641#ifndef SING_NDEBUG
2642  if( __DEBUG__ )
2643  {
2644    DebugPrint();
2645    syz_checker.Verify();
2646  }
2647#endif
2648
2649  CDivisorEnumerator itr(*this, product);
2650  if( !itr.Reset() )
2651    return NULL;
2652
2653
2654 
2655  const ring& r = m_rBaseRing;
2656
2657  assume( product != NULL );
2658
2659  const ideal& L = m_L; assume( L != NULL ); // for debug/testing only!
2660
2661  long c = 0;
2662
2663  if (syzterm != NULL)
2664    c = p_GetComp(syzterm, r) - 1;
2665
2666  assume( c >= 0 && c < IDELEMS(L) );
2667
2668  if (__DEBUG__ && (syzterm != NULL))
2669  {
2670    const poly m = L->m[c];
2671
2672    assume( m != NULL ); assume( pNext(m) == NULL );
2673
2674    poly lm = p_Mult_mm(leadmonom(syzterm, r), m, r);
2675    assume( p_EqualPolys(lm, product, r) );
2676
2677    //  def @@c = leadcomp(syzterm); int @@r = int(@@c);
2678    //  def @@product = leadmonomial(syzterm) * L[@@r];
2679
2680    p_Delete(&lm, r);
2681  }
2682
2683#ifndef SING_NDEBUG
2684  if( __DEBUG__ )
2685  {
2686    DebugPrint();
2687    syz_checker.Verify();
2688  }
2689#endif
2690
2691  const BOOLEAN to_check = (syz_checker.IsNonempty()); // __TAILREDSYZ__ &&
2692
2693  const poly q = p_New(r); pNext(q) = NULL;
2694
2695  if( __DEBUG__ )
2696    p_SetCoeff0(q, 0, r); // ONLY for printing q
2697
2698  while( itr.MoveNext() )
2699  {
2700    assume( itr.Current().CheckLT( L ) ); // ???
2701   
2702    const poly p = itr.Current().lt(); // ??
2703    const int k  = itr.Current().label();
2704
2705    p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2706    p_SetComp(q, k + 1, r);
2707    p_Setm(q, r);
2708
2709    // cannot allow something like: a*gen(i) - a*gen(i)
2710    if (syzterm != NULL && (k == c))
2711      if (p_ExpVectorEqual(syzterm, q, r))
2712      {
2713#ifndef SING_NDEBUG
2714        if( __DEBUG__ )
2715        {
2716          Print("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2717          dPrint(syzterm, r, r, 1);
2718        }
2719#endif
2720        assume( itr.Current().CheckLT( L ) ); // ???
2721        continue;
2722      }
2723
2724    // while the complement (the fraction) is not reducible by leading syzygies
2725    if( to_check && syz_checker.IsDivisible(q) ) // ?????
2726    {
2727#ifndef SING_NDEBUG
2728      if( __DEBUG__ )
2729      {
2730        PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2731      }
2732#endif
2733      assume( itr.Current().CheckLT( L ) ); // ???
2734      continue;
2735    }
2736
2737    p_SetCoeff0(q, n_InpNeg( n_Div( p_GetCoeff(product, r), p_GetCoeff(p, r), r), r), r);
2738
2739    assume( itr.Current().CheckLT( L ) ); // ???
2740   
2741#ifndef SING_NDEBUG
2742    if( __DEBUG__ )
2743    {
2744      DebugPrint();
2745      syz_checker.Verify();
2746    }
2747#endif
2748   
2749    return q;
2750  }
2751
2752
2753
2754/*
2755  const long comp = p_GetComp(product, r);
2756  const unsigned long not_sev = ~p_GetShortExpVector(product, r);
2757
2758  assume( comp >= 0 );
2759
2760//   for( int k = IDELEMS(L)-1; k>= 0; k-- )
2761//   {
2762//     const poly p = L->m[k];
2763//
2764//     if ( p_GetComp(p, r) != comp )
2765//       continue;
2766//
2767//     const unsigned long p_sev = p_GetShortExpVector(p, r); // to be stored in m_hash!!!
2768
2769   // looking for an appropriate diviser p = L[k]...
2770  CReducersHash::const_iterator it = m_hash.find(comp); // same module component
2771
2772  if( it == m_hash.end() )
2773    return NULL;
2774
2775  assume( m_L != NULL );
2776
2777  const TReducers& reducers = it->second;
2778
2779  const BOOLEAN to_check = (syz_checker.IsNonempty()); // __TAILREDSYZ__ &&
2780
2781  const poly q = p_New(r); pNext(q) = NULL;
2782
2783  if( __DEBUG__ )
2784    p_SetCoeff0(q, 0, r); // for printing q
2785
2786  for(TReducers::const_iterator vit = reducers.begin(); vit != reducers.end(); vit++ )
2787  {
2788    const poly p = (*vit)->lt(); // ???
2789
2790    assume( p_GetComp(p, r) == comp );
2791
2792    const int k = (*vit)->label();
2793
2794    assume( L->m[k] == p ); // CheckLT
2795
2796    const unsigned long p_sev = (*vit)->sev();
2797
2798    assume( p_sev == p_GetShortExpVector(p, r) );
2799
2800    if( !p_LmShortDivisibleByNoComp(p, p_sev, product, not_sev, r) )
2801      continue;
2802
2803//     // ... which divides the product, looking for the _1st_ appropriate one!
2804//     if( !p_LmDivisibleByNoComp(p, product, r) ) // included inside  p_LmShortDivisibleBy!
2805//       continue;
2806
2807    p_ExpVectorDiff(q, product, p, r); // (LM(product) / LM(L[k]))
2808    p_SetComp(q, k + 1, r);
2809    p_Setm(q, r);
2810
2811    // cannot allow something like: a*gen(i) - a*gen(i)
2812    if (syzterm != NULL && (k == c))
2813      if (p_ExpVectorEqual(syzterm, q, r))
2814      {
2815        if( __DEBUG__ )
2816        {
2817          Print("_FindReducer::Test SYZTERM: q == syzterm !:((, syzterm is: ");
2818          dPrint(syzterm, r, r, 1);
2819        }
2820
2821        continue;
2822      }
2823
2824    // while the complement (the fraction) is not reducible by leading syzygies
2825    if( to_check && syz_checker.IsDivisible(q) )
2826    {
2827      if( __DEBUG__ )
2828      {
2829        PrintS("_FindReducer::Test LS: q is divisible by LS[?] !:((: ");
2830      }
2831
2832      continue;
2833    }
2834
2835    p_SetCoeff0(q, n_InpNeg( n_Div( p_GetCoeff(product, r), p_GetCoeff(p, r), r), r), r);
2836    return q;
2837  }
2838*/
2839
2840  p_LmFree(q, r);
2841
2842#ifndef SING_NDEBUG
2843  if( __DEBUG__ )
2844  {
2845    DebugPrint();
2846    syz_checker.Verify();
2847  }
2848#endif
2849 
2850  return NULL;
2851}
2852
2853
2854
2855CLCM::CLCM(const ideal& L, const SchreyerSyzygyComputationFlags& flags):
2856    SchreyerSyzygyComputationFlags(flags), std::vector<bool>(),
2857    m_compute(false), m_N(rVar(flags.m_rBaseRing))
2858{
2859  const ring& R = m_rBaseRing;
2860  assume( flags.m_rBaseRing == R );
2861  assume( R != NULL );
2862
2863  assume( L != NULL );
2864
2865  if( __TAILREDSYZ__ && !__HYBRIDNF__ && (L != NULL))
2866  {
2867    const int l = IDELEMS(L);
2868
2869    assume( l > 0 );
2870
2871    resize(l, false);
2872
2873    for( int k = l - 1; k >= 0; k-- )
2874    {
2875      const poly a = L->m[k]; assume( a != NULL );
2876
2877      for (unsigned int j = m_N; j > 0; j--)
2878        if ( !(*this)[j] )
2879          (*this)[j] = (p_GetExp(a, j, R) > 0);
2880    }
2881
2882    m_compute = true;
2883  }
2884}
2885
2886
2887bool CLCM::Check(const poly m) const
2888{
2889  assume( m != NULL );
2890  if( m_compute && (m != NULL))
2891  {
2892    const ring& R = m_rBaseRing;
2893
2894    assume( __TAILREDSYZ__ && !__HYBRIDNF__ );
2895
2896    for (unsigned int j = m_N; j > 0; j--)
2897      if ( (*this)[j] )
2898        if(p_GetExp(m, j, R) > 0)
2899          return true;
2900
2901    return false;
2902
2903  } else return true;
2904}
2905
2906CCacheCompare::CCacheCompare(): m_ring(currRing) {}
2907
2908
2909template class std::vector<bool>;
2910template class std::vector<CLeadingTerm const*>;
2911template class std::map< CReducerFinder::TComponentKey, CReducerFinder::TReducers >;
2912
2913template class std::map<TCacheKey, TCacheValue, struct CCacheCompare>;
2914template class std::map<int, TP2PCache>;
2915
2916
2917
2918END_NAMESPACE               END_NAMESPACE_SINGULARXX
2919
2920
2921// Vi-modeline: vim: filetype=c:syntax:shiftwidth=2:tabstop=8:textwidth=0:expandtab
Note: See TracBrowser for help on using the repository browser.