source: git/kernel/splist.cc @ fec53d

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