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"
27 #include "polys/monomials/p_polys.h"
28 #include "kernel/spectrum/npolygon.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
copy_zero(void)40 void spectrumPolyNode::copy_zero( void )
41 {
42 next = (spectrumPolyNode*)NULL;
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
copy_shallow(spectrumPolyNode * pnode,poly m,const Rational & w,poly f,const ring R)53 void spectrumPolyNode::copy_shallow(
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
copy_shallow(spectrumPolyNode & node)67 void spectrumPolyNode::copy_shallow( spectrumPolyNode &node )
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
spectrumPolyNode()80 spectrumPolyNode::spectrumPolyNode( )
81 {
82 copy_zero( );
83 }
84
85 // ----------------------------------------------------------------------------
86 // Data constructor for spectrumPolyNode is shallow
87 // ----------------------------------------------------------------------------
88
spectrumPolyNode(spectrumPolyNode * pnode,poly m,const Rational & w,poly f,const ring R)89 spectrumPolyNode::spectrumPolyNode(
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
~spectrumPolyNode()99 spectrumPolyNode::~spectrumPolyNode()
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
copy_zero(void)114 void spectrumPolyList::copy_zero( void )
115 {
116 root = (spectrumPolyNode*)NULL;
117 N = 0;
118 np = (newtonPolygon*)NULL;
119 }
120
121 // ----------------------------------------------------------------------------
122 // Inizialize a spectrumPolyList shallow from data
123 // ----------------------------------------------------------------------------
124
copy_shallow(spectrumPolyNode * node,int k,newtonPolygon * npolygon)125 void spectrumPolyList::copy_shallow(
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
copy_shallow(spectrumPolyList & splist)137 void spectrumPolyList::copy_shallow( spectrumPolyList &splist )
138 {
139 copy_shallow( splist.root,splist.N,splist.np );
140 }
141
142 // ----------------------------------------------------------------------------
143 // Zero constructor for spectrumPolyList
144 // ----------------------------------------------------------------------------
145
spectrumPolyList()146 spectrumPolyList::spectrumPolyList( )
147 {
148 copy_zero( );
149 }
150
151 // ----------------------------------------------------------------------------
152 // Data constructor for spectrumPolyList
153 // ----------------------------------------------------------------------------
154
spectrumPolyList(newtonPolygon * npolygon)155 spectrumPolyList::spectrumPolyList( newtonPolygon *npolygon )
156 {
157 copy_shallow( (spectrumPolyNode*)NULL,0,npolygon );
158 }
159
160 // ----------------------------------------------------------------------------
161 // Destuctor for spectrumPolyList
162 // ----------------------------------------------------------------------------
163
~spectrumPolyList()164 spectrumPolyList::~spectrumPolyList( )
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
insert_node(poly m,poly f,const ring R)184 void spectrumPolyList::insert_node( poly m,poly f, const ring R )
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
delete_node(spectrumPolyNode ** node)256 void spectrumPolyList::delete_node( spectrumPolyNode **node )
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
delete_monomial(poly m,const ring R)269 void spectrumPolyList::delete_monomial( poly m, const ring R )
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
operator <<(ostream & s,const spectrumPolyList & l)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
387