My Project  debian-1:4.1.2-p1+ds-2
lists.cc
Go to the documentation of this file.
1 /****************************************
2 * Computer Algebra System SINGULAR *
3 ****************************************/
4 /*
5 * ABSTRACT: handling of the list type
6 */
7 // to produce a non-inline version from lists.h
8 #define LISTS_CC
9 
10 
11 
12 
13 #include "kernel/mod2.h"
14 #include "Singular/tok.h"
15 //#include "ipid.h"
16 #include "kernel/polys.h"
17 #include "kernel/ideals.h"
18 #include "Singular/attrib.h"
19 #include "Singular/ipshell.h"
20 #include "misc/intvec.h"
21 #include "Singular/lists.h"
22 
24 
25 int lSize(lists L)
26 {
27  int n=L->nr;
28  while ((n>=0)&&((L->m[n].rtyp==DEF_CMD)||(L->m[n].rtyp==0))) n--;
29  return n;
30 }
31 
33 {
35  int n=L->nr;
36  if (L->nr>=0)
37  N->Init(n+1);
38  else
39  N->Init();
40  for(;n>=0;n--)
41  {
42  N->m[n].Copy(&L->m[n]);
43  }
44  //Print("copy list with %d -> %d elems\n",L->nr,N->nr);
45  return N;
46 }
47 
48 /*2
49 * concat 2 lists
50 */
52 {
54  lists ul=(lists)u->CopyD();
55  lists vl=(lists)v->CopyD();
56  l->Init(ul->nr+vl->nr+2);
57  int i;
58 
59  for(i=0;i<=ul->nr;i++)
60  {
61  //Print("u[%d]->r[%d]\n",i,i);
62  l->m[i].rtyp=ul->m[i].rtyp;
63  l->m[i].data=ul->m[i].data;
64  }
65  for(i=0;i<=vl->nr;i++)
66  {
67  //Print("v[%d]->r[%d]\n",i,i+ul->nr+1);
68  l->m[i+ul->nr+1].rtyp=vl->m[i].rtyp;
69  l->m[i+ul->nr+1].data=vl->m[i].data;
70  }
71  if (ul->m != NULL)
72  omFreeSize((ADDRESS)ul->m,(ul->nr+1)*sizeof(sleftv));
74  if (vl->m != NULL)
75  omFreeSize((ADDRESS)vl->m,(vl->nr+1)*sizeof(sleftv));
77  memset(u,0,sizeof(*u));
78  memset(v,0,sizeof(*v));
79  res->data = (char *)l;
80  //res->Print();
81  return FALSE;
82 }
83 
84 /*2
85 * insert v into list ul, destroys u
86 */
87 lists lInsert0(lists ul, leftv v, int pos)
88 {
89  if ((pos<0)||(v->rtyp==NONE))
90  return NULL;
92  l->Init(si_max(ul->nr+2,pos+1));
93  int i,j;
94 
95  for(i=j=0;i<=ul->nr;i++,j++)
96  {
97  if(j==pos) j++;
98  l->m[j]=ul->m[i];
99  }
100  for(j=ul->nr+1;j<pos;j++)
101  l->m[j].rtyp=DEF_CMD;
102  // memset(&(l->m[pos]),0,sizeof(sleftv)); - done by Init
103  l->m[pos].rtyp=v->Typ();
104  l->m[pos].data=v->CopyD();
105  l->m[pos].flag=v->flag;
106  attr *a=v->Attribute();
107  if ((a!=NULL)&&(*a!=NULL))
108  {
109  l->m[pos].attribute=(*a)->Copy();
110  }
111  if (ul->m != NULL)
112  omFreeSize((ADDRESS)ul->m,(ul->nr+1)*sizeof(sleftv));
114  return l;
115 }
116 
117 /*2
118 * insert v into list u, at the beginning
119 */
121 {
122  lists ul=(lists)u->CopyD();
123  res->data=(char *)lInsert0(ul,v,0);
124  if (res->data==NULL)
125  {
126  Werror("cannot insert type `%s`",Tok2Cmdname(v->Typ()));
127  return TRUE;
128  }
129  return FALSE;
130 }
131 
132 /*2
133 * insert v into list u at pos w
134 */
136 {
137  lists ul=(lists)u->CopyD();
138  res->data=(char *)lInsert0(ul,v,(int)(long)w->Data());
139  if (res->data==NULL)
140  {
141  Werror("cannot insert type `%s` at pos. %d",
142  Tok2Cmdname(v->Typ()),(int)(long)w->Data());
143  return TRUE;
144  }
145  return FALSE;
146 }
147 
148 /*2
149 * append v to list u
150 */
152 {
153  lists ul=(lists)u->CopyD();
154  res->data=(char *)lInsert0(ul,v,ul->nr+1);
155  return (res->data==NULL);
156 }
157 
158 /*2
159 * delete v-th element from list u
160 */
162 {
163  lists ul=(lists)u->Data();
164  int VIndex=(int)(long)v->Data()-1;
165  int EndIndex=lSize(ul);
166 
167  if((0<=VIndex)&&(VIndex<=ul->nr))
168  {
169  ul=(lists)u->CopyD();
170  int i,j;
172  l->Init(EndIndex+(VIndex>EndIndex));
173 
174  for(i=j=0;i<=EndIndex;i++,j++)
175  {
176  if (i!=VIndex)
177  {
178  l->m[j]=ul->m[i];
179  memset(&ul->m[i],0,sizeof(ul->m[i]));
180  }
181  else
182  {
183  j--;
184  ul->m[i].CleanUp();
185  }
186  }
187  omFreeSize((ADDRESS)ul->m,(ul->nr+1)*sizeof(sleftv));
189  res->data = (char *)l;
190  return FALSE;
191  }
192  Werror("wrong index %d in list(%d)",VIndex+1,ul->nr+1);
193  return TRUE;
194 }
195 
196 /*2
197 * check, if a list contains any ring dependend data
198 */
200 {
201  if (L==NULL) return FALSE;
202  int i=L->nr;
203  while (i>=0)
204  {
205  REGISTER int t=L->m[i].rtyp;
206  if ((BEGIN_RING<t /*L->m[i].rtyp*/)
207  && (/*L->m[i].rtyp*/ t<END_RING))
208  return TRUE;
209  if ((/*L->m[i].rtyp*/ t==LIST_CMD)&&lRingDependend((lists)L->m[i].data))
210  return TRUE;
211  i--;
212  }
213  return FALSE;
214 }
215 
216 lists liMakeResolv(resolvente r, int length, int reallen,
217  int typ0, intvec ** weights, int add_row_shift)
218 {
219  // re-uses r, weights[i]
221  if (length<=0)
222  {
223  // handle "empty" resolutions
224  L->Init(0);
225  }
226  else
227  {
228  int oldlength=length;
229  while (r[length-1]==NULL) length--;
230  if (reallen<=0) reallen=currRing->N;
231  reallen=si_max(reallen,length);
232  L->Init(reallen);
233  int i=0;
234 
235  while (i<length)
236  {
237  if (r[i]!=NULL)
238  {
239  if (i==0)
240  {
241  L->m[i].rtyp=typ0;
242  int j=IDELEMS(r[0])-1;
243  while ((j>0) && (r[0]->m[j]==NULL)) j--;
244  j++;
245  if (j!=IDELEMS(r[0]))
246  {
247  pEnlargeSet(&(r[0]->m),IDELEMS(r[0]),j-IDELEMS(r[0]));
248  IDELEMS(r[0])=j;
249  }
250  }
251  else
252  {
253  L->m[i].rtyp=MODUL_CMD;
254  int rank=IDELEMS(r[i-1]);
255  if (idIs0(r[i-1]))
256  {
257  idDelete(&(r[i]));
258  r[i]=id_FreeModule(rank, currRing);
259  }
260  else
261  {
262  r[i]->rank=si_max(rank,(int)id_RankFreeModule(r[i], currRing));
263  }
264  idSkipZeroes(r[i]);
265  }
266  L->m[i].data=(void *)r[i];
267  if ((weights!=NULL) && (weights[i]!=NULL))
268  {
269  intvec *w=weights[i];
270  (*w) += add_row_shift;
271  atSet((idhdl)&L->m[i],omStrDup("isHomog"),w,INTVEC_CMD);
272  weights[i] = NULL;
273  }
274  }
275  #ifdef TEST
276  else
277  {
278  // should not happen:
279  WarnS("internal NULL in resolvente");
280  L->m[i].data=(void *)idInit(1,1);
281  }
282  #endif
283  i++;
284  }
285  omFreeSize((ADDRESS)r,oldlength*sizeof(ideal));
286  if (weights!=NULL) omFreeSize(weights,oldlength*sizeof(intvec*));
287  if (i==0)
288  {
289  L->m[0].rtyp=typ0;
290  L->m[0].data=(char *)idInit(1,1);
291  i=1;
292  }
293  while (i<reallen)
294  {
295  L->m[i].rtyp=MODUL_CMD;
296  ideal I=(ideal)L->m[i-1].data;
297  ideal J;
298  int rank=IDELEMS(I);
299  if (idIs0(I))
300  {
301  J=idFreeModule(rank);
302  }
303  else
304  {
305  J=idInit(1,rank);
306  }
307  L->m[i].data=(void *)J;
308  i++;
309  }
310  //Print("make res of length %d (0..%d) L:%d\n",length,length-1,L->nr);
311  }
312  return L;
313 }
314 
315 resolvente liFindRes(lists L, int * len, int *typ0,intvec *** weights)
316 {
317  resolvente r;
318  intvec ** w=NULL,*tw=NULL;
319 
320  *len=L->nr+1;
321  if (*len<=0)
322  {
323  WerrorS("empty list");
324  return NULL;
325  }
326  r=(ideal *)omAlloc0((*len)*sizeof(ideal));
327  w=(intvec**)omAlloc0((*len)*sizeof(intvec*));
328  int i=0;
329  *typ0=MODUL_CMD;
330  while (i<(*len))
331  {
332  if (L->m[i].rtyp != MODUL_CMD)
333  {
334  if (L->m[i].rtyp!=IDEAL_CMD)
335  {
336  Werror("element %d is not of type module",i+1);
337  omFreeSize((ADDRESS)r,(*len)*sizeof(ideal));
338  return NULL;
339  }
340  *typ0=IDEAL_CMD;
341  }
342  if ((i>0) && (idIs0(r[i-1])))
343  {
344  //*len=i-1;
345  break;
346  }
347  r[i]=(ideal)L->m[i].data;
348  tw=(intvec*)atGet(&(L->m[i]),"isHomog",INTVEC_CMD);
349  if (tw!=NULL)
350  {
351  w[i]=ivCopy(tw);
352  }
353  tw = NULL;
354  i++;
355  }
356  BOOLEAN hom_complex=TRUE;
357  int j=0;
358  while ((j<i) && hom_complex)
359  {
360  hom_complex = hom_complex && (w[j]!=NULL);
361  j++;
362  }
363  if ((!hom_complex) || (weights==NULL))
364  {
365  for (j=0;j<i;j++)
366  {
367  if (w[j]!=NULL) delete w[j];
368  }
369  omFreeSize((ADDRESS)w,(*len)*sizeof(intvec*));
370  if (weights!=NULL) *weights=NULL;
371  }
372  else
373  {
374  *weights = w;
375  }
376  //Print("find res of length %d (0..%d) L:%d\n",*len,(*len)-1,L->nr);
377  return r;
378 }
379 
380 char* lString(lists l, BOOLEAN typed, int dim)
381 {
382  if (l->nr == -1)
383  {
384  if (typed) return omStrDup("list()");
385  return omStrDup("");
386  }
387 
388  char** slist = (char**) omAlloc((l->nr+1) * sizeof(char*));
389  int i, j, k;
390  char *s;
391  for (i=0, j = 0, k = 0; i<=l->nr; i++)
392  {
393  slist[i] = l->m[i].String(NULL, typed, dim);
394  assume(slist[i] != NULL);
395  omCheckAddr(slist[i]);
396  if (*(slist[i]) != '\0')
397  {
398  j += strlen(slist[i]);
399  k++;
400  }
401  }
402  s = (char*) omAlloc(j+k+2+(typed ? 10 : 0) + (dim == 2 ? k : 0));
403 
404  if (typed)
405  sprintf(s, "list(");
406  else
407  *s = '\0';
408 
409  for (i=0; i<=l->nr; i++)
410  {
411  if (*(slist[i]) != '\0')
412  {
413  strcat(s, slist[i]);
414  strcat(s, ",");
415  if (dim == 2) strcat(s, "\n");
416  }
417  omCheckAddr(s);
418  omFree(slist[i]);
419  }
420  if (k > 0) s[strlen(s) - (dim == 2 ? 2 : 1)] = '\0';
421  if (typed) strcat(s, ")");
422  omCheckAddr(s);
423  omFreeSize(slist, (l->nr+1) * sizeof(char*));
424  return s;
425 }
void * atGet(idhdl root, const char *name, int t, void *defaultReturnValue)
Definition: attrib.cc:129
void atSet(idhdl root, char *name, void *data, int typ)
Definition: attrib.cc:150
static int si_max(const int a, const int b)
Definition: auxiliary.h:140
int BOOLEAN
Definition: auxiliary.h:87
#define TRUE
Definition: auxiliary.h:100
#define FALSE
Definition: auxiliary.h:96
void * ADDRESS
Definition: auxiliary.h:135
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
int l
Definition: cfEzgcd.cc:93
int m
Definition: cfEzgcd.cc:121
int i
Definition: cfEzgcd.cc:125
int k
Definition: cfEzgcd.cc:92
Definition: idrec.h:35
Definition: intvec.h:23
Definition: attrib.h:21
Class used for (list of) interpreter objects.
Definition: subexpr.h:83
void * CopyD(int t)
Definition: subexpr.cc:739
int rtyp
Definition: subexpr.h:91
void * Data()
Definition: subexpr.cc:1176
void * data
Definition: subexpr.h:88
void CleanUp(ring r=currRing)
Definition: subexpr.cc:348
Definition: lists.h:24
sleftv * m
Definition: lists.h:46
INLINE_THIS void Init(int l=0)
int nr
Definition: lists.h:44
#define WarnS
Definition: emacs.cc:78
const CanonicalForm int s
Definition: facAbsFact.cc:55
CanonicalForm res
Definition: facAbsFact.cc:64
const CanonicalForm & w
Definition: facAbsFact.cc:55
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int j
Definition: facHensel.cc:105
void WerrorS(const char *s)
Definition: feFopen.cc:24
const char * Tok2Cmdname(int tok)
Definition: gentable.cc:140
#define VAR
Definition: globaldefs.h:5
@ END_RING
Definition: grammar.cc:310
@ IDEAL_CMD
Definition: grammar.cc:284
@ MODUL_CMD
Definition: grammar.cc:287
#define idDelete(H)
delete an ideal
Definition: ideals.h:29
BOOLEAN idIs0(ideal h)
returns true if h is the zero ideal
ideal * resolvente
Definition: ideals.h:18
ideal idFreeModule(int i)
Definition: ideals.h:111
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263
intvec * ivCopy(const intvec *o)
Definition: intvec.h:135
BOOLEAN lDelete(leftv res, leftv u, leftv v)
Definition: lists.cc:161
VAR omBin slists_bin
Definition: lists.cc:23
BOOLEAN lRingDependend(lists L)
Definition: lists.cc:199
BOOLEAN lAdd(leftv res, leftv u, leftv v)
Definition: lists.cc:51
lists lInsert0(lists ul, leftv v, int pos)
Definition: lists.cc:87
BOOLEAN lAppend(leftv res, leftv u, leftv v)
Definition: lists.cc:151
BOOLEAN lInsert3(leftv res, leftv u, leftv v, leftv w)
Definition: lists.cc:135
resolvente liFindRes(lists L, int *len, int *typ0, intvec ***weights)
Definition: lists.cc:315
char * lString(lists l, BOOLEAN typed, int dim)
Definition: lists.cc:380
BOOLEAN lInsert(leftv res, leftv u, leftv v)
Definition: lists.cc:120
lists liMakeResolv(resolvente r, int length, int reallen, int typ0, intvec **weights, int add_row_shift)
Definition: lists.cc:216
int lSize(lists L)
Definition: lists.cc:25
lists lCopy(lists L)
Definition: lists.cc:32
#define assume(x)
Definition: mod2.h:390
slists * lists
Definition: mpr_numeric.h:146
#define omStrDup(s)
Definition: omAllocDecl.h:263
#define omFreeSize(addr, size)
Definition: omAllocDecl.h:260
#define omCheckAddr(addr)
Definition: omAllocDecl.h:328
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omAllocBin(bin)
Definition: omAllocDecl.h:205
#define omAlloc0Bin(bin)
Definition: omAllocDecl.h:206
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define omFreeBin(addr, bin)
Definition: omAllocDecl.h:259
#define omGetSpecBin(size)
Definition: omBin.h:11
#define NULL
Definition: omList.c:12
omBin_t * omBin
Definition: omStructs.h:12
#define REGISTER
Definition: omalloc.h:27
void pEnlargeSet(poly **p, int l, int increment)
Definition: p_polys.cc:3656
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatiblity layer for legacy polynomial operations (over currRing)
void Werror(const char *fmt,...)
Definition: reporter.cc:189
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
ideal id_FreeModule(int i, const ring r)
the free module of rank i
long id_RankFreeModule(ideal s, ring lmRing, ring tailRing)
return the maximal component number found in any polynomial in s
void idSkipZeroes(ideal ide)
gives an ideal/module the minimal possible size
#define IDELEMS(i)
Definition: simpleideals.h:23
@ LIST_CMD
Definition: tok.h:118
@ INTVEC_CMD
Definition: tok.h:101
@ DEF_CMD
Definition: tok.h:58
#define NONE
Definition: tok.h:220
int dim(ideal I, ring r)