source: git/kernel/splist.cc @ abe5c8

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