splist.cc
Go to the documentation of this file.
1 // ----------------------------------------------------------------------------
2 // splist.cc
3 // begin of file
4 // Stephan Endrass, endrass@mathematik.uni-mainz.de
5 // 23.7.99
6 // ----------------------------------------------------------------------------
7 
8 #define SPLIST_CC
9 
10 
11 
12 
13 #include <kernel/mod2.h>
14 
15 #ifdef HAVE_SPECTRUM
16 
17 #ifdef SPLIST_PRINT
18 #include <iostream.h>
19 #ifndef SPLIST_IOSTREAM
20 #include <stdio.h>
21 #endif
22 #endif
23 
24 #include <kernel/structs.h>
25 #include <kernel/spectrum/GMPrat.h>
26 #include <coeffs/numbers.h>
29 #include <kernel/spectrum/splist.h>
30 #include <misc/intvec.h>
31 
32 // ------------------------
33 // class spectrumPolyNode
34 // ------------------------
35 
36 // ----------------------------------------------------------------------------
37 // Initialize a spectrumPolyNode with zero
38 // ----------------------------------------------------------------------------
39 
41 {
43  mon = NULL;
44  weight = (Rational)0;
45  nf = NULL;
46  r = NULL;
47 }
48 
49 // ----------------------------------------------------------------------------
50 // Inizialize a spectrumPolyNode shallow from data
51 // ----------------------------------------------------------------------------
52 
54  spectrumPolyNode *pnode,poly m,const Rational &w,poly f, const ring R )
55 {
56  next = pnode;
57  mon = m;
58  weight = w;
59  nf = f;
60  r = R;
61 }
62 
63 // ----------------------------------------------------------------------------
64 // Inizialize a spectrumPolyNode shallow from another spectrumPolyNode
65 // ----------------------------------------------------------------------------
66 
68 {
69  next = node.next;
70  mon = node.mon;
71  weight = node.weight;
72  nf = node.nf;
73  r = node.r;
74 }
75 
76 // ----------------------------------------------------------------------------
77 // Zero constructor for spectrumPolyNode
78 // ----------------------------------------------------------------------------
79 
81 {
82  copy_zero( );
83 }
84 
85 // ----------------------------------------------------------------------------
86 // Data constructor for spectrumPolyNode is shallow
87 // ----------------------------------------------------------------------------
88 
90  spectrumPolyNode *pnode,poly m,const Rational &w,poly f, const ring R )
91 {
92  copy_shallow( pnode,m,w,f,R );
93 }
94 
95 // ----------------------------------------------------------------------------
96 // Destructor is empty since we construct our objects shallow
97 // ----------------------------------------------------------------------------
98 
100 {
101  if( mon!=NULL ) p_Delete( &mon, r );
102  if( nf !=NULL ) p_Delete( &nf,r );
103  copy_zero( );
104 }
105 
106 // ------------------------
107 // class spectrumPolyList
108 // ------------------------
109 
110 // ----------------------------------------------------------------------------
111 // Initialize a spectrumPolyList with zero
112 // ----------------------------------------------------------------------------
113 
115 {
116  root = (spectrumPolyNode*)NULL;
117  N = 0;
118  np = (newtonPolygon*)NULL;
119 }
120 
121 // ----------------------------------------------------------------------------
122 // Inizialize a spectrumPolyList shallow from data
123 // ----------------------------------------------------------------------------
124 
126  spectrumPolyNode *node,int k,newtonPolygon *npolygon )
127 {
128  root = node;
129  N = k;
130  np = npolygon;
131 }
132 
133 // ----------------------------------------------------------------------------
134 // Inizialize a spectrumPolyList shallow from another spectrumPolyList
135 // ----------------------------------------------------------------------------
136 
138 {
139  copy_shallow( splist.root,splist.N,splist.np );
140 }
141 
142 // ----------------------------------------------------------------------------
143 // Zero constructor for spectrumPolyList
144 // ----------------------------------------------------------------------------
145 
147 {
148  copy_zero( );
149 }
150 
151 // ----------------------------------------------------------------------------
152 // Data constructor for spectrumPolyList
153 // ----------------------------------------------------------------------------
154 
156 {
157  copy_shallow( (spectrumPolyNode*)NULL,0,npolygon );
158 }
159 
160 // ----------------------------------------------------------------------------
161 // Destuctor for spectrumPolyList
162 // ----------------------------------------------------------------------------
163 
165 {
166  spectrumPolyNode *node;
167 
168  while( root!=(spectrumPolyNode*)NULL )
169  {
170  node = root->next;
171  delete root;
172  root = node;
173  }
174 
175  copy_zero( );
176 }
177 
178 // ----------------------------------------------------------------------------
179 // Insert a new node into a spectrumPolyList at position k
180 // If the list is sorted, then
181 // the new node ist inserted such that the list remains sorted.
182 // ----------------------------------------------------------------------------
183 
185 {
186  #ifdef SPLIST_DEBUG
187  if( np==(newtonPolygon*)NULL )
188  {
189  #ifdef SPLIST_PRINT
190  #ifdef SPLIST_IOSTREAM
191  cerr << "void spectrumPolyList::insert_node( poly f )" << endl;
192  cerr << " no Newton polygon" << endl;
193  cerr << " exiting..." << endl;
194  #else
195  fprintf( stderr,"void spectrumPolyList::insert_node( poly f )\n" );
196  fprintf( stderr," no Newton polygon\n" );
197  fprintf( stderr," exiting...\n" );
198  #endif
199  #endif
200 
201  exit( 1 );
202  }
203  #endif
204 
205  spectrumPolyNode *newnode = new spectrumPolyNode(
206  (spectrumPolyNode*)NULL,m,np->weight_shift( m,R ),f, R );
207 
208  if( N==0 ||
209  root->weight>newnode->weight ||
210  ( root->weight==newnode->weight &&
211  p_Cmp( root->mon,newnode->mon,R )<0 ) )
212  {
213  // ----------------------
214  // insert at position 0
215  // ----------------------
216 
217  newnode->next = root;
218  root = newnode;
219  }
220  else if( N==1 )
221  {
222  // ---------------
223  // insert at end
224  // ---------------
225 
226  root->next = newnode;
227  }
228  else
229  {
230  // ----------------------------
231  // insert according to weight
232  // ----------------------------
233 
234  spectrumPolyNode *actual = root;
235  spectrumPolyNode *next = root->next;
236 
237  while( next!=(spectrumPolyNode*)NULL &&
238  ( newnode->weight>next->weight ||
239  ( newnode->weight==next->weight &&
240  p_Cmp( newnode->mon,next->mon, R )<0 ) ) )
241  {
242  actual = next;
243  next = next->next;
244  }
245 
246  actual->next = newnode;
247  newnode->next = next;
248  }
249  N++;
250 }
251 
252 // ----------------------------------------------------------------------------
253 // Delete a node from a spectrumPolyList
254 // ----------------------------------------------------------------------------
255 
257 {
258  spectrumPolyNode *foo = *node;
259  *node = (*node)->next;
260  delete foo;
261  N--;
262 }
263 
264 // ----------------------------------------------------------------------------
265 // Delete all nodes where node->mon is a multiple of m
266 // In every node delete all instances of m in node->nf
267 // ----------------------------------------------------------------------------
268 
270 {
271  spectrumPolyNode **node = &root;
272  poly *f;
273 
274  m = p_Copy( m,R );
275 
276  while( *node!=(spectrumPolyNode*)NULL )
277  {
278  if( p_Cmp( m,(*node)->mon,R )>=0 && p_LmDivisibleByNoComp( m,(*node)->mon, R ))
279  {
280  delete_node( node );
281  }
282  else if( (*node)->nf!=NULL )
283  {
284  f = &((*node)->nf);
285 
286  while( *f!=NULL )
287  {
288  if( p_Cmp( m,*f,R )>=0 && p_LmDivisibleByNoComp( m,*f,R ) )
289  {
290  p_LmDelete(f,R);
291  }
292  else
293  {
294  f = &(pNext( *f ));
295  }
296  }
297 
298  if( (*node)->nf==NULL )
299  {
300  delete_node( node );
301  }
302  else
303  {
304  node = &((*node)->next);
305  }
306  }
307  else
308  {
309  node = &((*node)->next);
310  }
311  }
312  p_Delete( &m,R );
313 }
314 
315 // ----------------------------------------------------------------------------
316 // Print a spectrumPolyList
317 // ----------------------------------------------------------------------------
318 
319 #ifdef SPLIST_PRINT
320 ostream & operator << ( ostream &s,const spectrumPolyList &l )
321 {
322  #ifdef SPLIST_IOSTREAM
323  s << "elements: " << l.N << endl;
324  s << "{";
325  #else
326  fprintf( stdout,"elements: %d\n",l.N );
327  fprintf( stdout,"{" );
328  #endif
329 
330  if( l.root!=(spectrumPolyNode*)NULL )
331  {
332  #ifdef SPLIST_IOSTREAM
333  s << "(";
334  pWrite0( l.root->mon );
335  s << "=>";
336  pWrite0( l.root->nf );
337  cout << "," << l.root->weight << ")" << endl;
338  #else
339  fprintf( stdout,"(" );
340  pWrite0( l.root->mon );
341  fprintf( stdout,"=>" );
342  pWrite0( l.root->nf );
343  fprintf( stdout,"," );
344  cout << l.root->weight;
345  fprintf( stdout,")\n" );
346  #endif
347 
348  spectrumPolyNode *node = l.root->next;
349 
350  while( node!=(spectrumPolyNode*)NULL )
351  {
352  #ifdef SPLIST_IOSTREAM
353  s << ",(";
354  pWrite0( node->mon );
355  s << "=>";
356  pWrite0( node->nf );
357  cout << "," << node->weight << ")" << endl;
358  #else
359  fprintf( stdout,",(" );
360  pWrite0( node->mon );
361  fprintf( stdout,"=>" );
362  pWrite0( node->nf );
363  fprintf( stdout,"," );
364  cout << node->weight;
365  fprintf( stdout,")\n" );
366  #endif
367 
368  node = node->next;
369  }
370  }
371  #ifdef SPLIST_IOSTREAM
372  s << "}";
373  #else
374  fprintf( stdout,"}" );
375  #endif
376 
377  return s;
378 }
379 #endif
380 
381 #endif /* HAVE_SPECTRUM */
382 // ----------------------------------------------------------------------------
383 // splist.cc
384 // end of file
385 // ----------------------------------------------------------------------------
386 
const CanonicalForm int s
Definition: facAbsFact.cc:55
spectrumPolyNode * next
Definition: splist.h:39
static int p_Cmp(poly p1, poly p2, ring r)
Definition: p_polys.h:1524
void copy_zero(void)
Definition: splist.cc:114
Rational weight
Definition: splist.h:41
static BOOLEAN p_LmDivisibleByNoComp(poly a, poly b, const ring r)
Definition: p_polys.h:1663
newtonPolygon * np
Definition: splist.h:62
int k
Definition: cfEzgcd.cc:93
void pWrite0(poly p)
Definition: polys.h:280
static poly p_Copy(poly p, const ring r)
returns a copy of p
Definition: p_polys.h:810
Definition: gnumpfl.cc:60
spectrumPolyNode * root
Definition: splist.h:60
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:49
const ring R
Definition: DebugPrint.cc:36
int m
Definition: cfEzgcd.cc:119
FILE * f
Definition: checklibs.c:7
void copy_shallow(spectrumPolyNode *, poly, const Rational &, poly, const ring)
Definition: splist.cc:53
static void p_Delete(poly *p, const ring r)
Definition: p_polys.h:849
void copy_shallow(spectrumPolyNode *, int, newtonPolygon *)
Definition: splist.cc:125
#define NULL
Definition: omList.c:10
void delete_monomial(poly, const ring)
Definition: splist.cc:269
const CanonicalForm & w
Definition: facAbsFact.cc:55
void copy_zero(void)
Definition: splist.cc:40
#define pNext(p)
Definition: monomials.h:43
static void p_LmDelete(poly p, const ring r)
Definition: p_polys.h:706
polyrec * poly
Definition: hilb.h:10
void insert_node(poly, poly, const ring)
Definition: splist.cc:184
void delete_node(spectrumPolyNode **)
Definition: splist.cc:256
int l
Definition: cfEzgcd.cc:94
ostream & operator<<(ostream &s, const spectrum &spec)
Definition: semic.cc:249