source: git/factory/cf_map.cc

spielwiese
Last change on this file was d0dbd7, checked in by Hans Schoenemann <hannes@…>, 7 years ago
chg: more NEW_ARRAY/DELETE_ARRY in factory
  • Property mode set to 100644
File size: 9.8 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2
3/**
4 *
5 * @file cf_map.cc
6 *
7 * definition of class CFMap.
8 *
9 * Used by: cf_gcd.cc, fac_multivar.cc
10 *
11**/
12
13
14#include "config.h"
15
16
17#include "canonicalform.h"
18#include "cf_map.h"
19#include "cf_iter.h"
20#include "templates/ftmpl_functions.h"
21
22/** MapPair & MapPair::operator = ( const MapPair & p )
23 *
24 * MapPair::operator = - assignment operator.
25 *
26**/
27MapPair &
28MapPair::operator = ( const MapPair & p )
29{
30    if ( this != &p ) {
31        V = p.V;
32        S = p.S;
33    }
34    return *this;
35}
36
37#ifndef NOSTREAMIO
38/** OSTREAM & operator << ( OSTREAM & s, const MapPair & p )
39 *
40 * operator << - print a map pair ("V -> S").
41 *
42**/
43OSTREAM &
44operator << ( OSTREAM & s, const MapPair & p )
45{
46    s << p.var() << " -> " << p.subst();
47    return s;
48}
49
50void MapPair::print( OSTREAM&) const
51{
52}
53#endif /* NOSTREAMIO */
54
55/** CFMap::CFMap ( const CFList & L )
56 *
57 * CFMap::CFMap() - construct a CFMap from a CFList.
58 *
59 * Variable[i] will be mapped to CFList[i] under the resulting
60 * map.
61 *
62**/
63CFMap::CFMap ( const CFList & L )
64{
65    CFListIterator i;
66    int j;
67    for ( i = L, j = 1; i.hasItem(); i++, j++ )
68        P.insert( MapPair( Variable(j), i.getItem() ) );
69}
70
71/** CFMap & CFMap::operator = ( const CFMap & m )
72 *
73 * CFMap::operator = - assignment operator.
74 *
75**/
76CFMap &
77CFMap::operator = ( const CFMap & m )
78{
79    if ( this != &m )
80        P = m.P;
81    return *this;
82}
83
84/** static int cmpfunc ( const MapPair & p1, const MapPair & p2 )
85 *
86 * cmpfunc() - compare two map pairs.
87 *
88 * Return -1 if p2's variable is less than p1's, 0 if they are
89 * equal, 1 if p2's level is greater than p1's.
90 *
91**/
92static int
93cmpfunc ( const MapPair & p1, const MapPair & p2 )
94{
95    if ( p1.var() > p2.var() ) return -1;
96    else if ( p1.var() == p2.var() ) return 0;
97    else return 1;
98}
99
100/** static void insfunc ( MapPair & orgp, const MapPair & newp )
101 *
102 * insfunc() - assign newp to orgp.
103 *
104 * cmpfunc() and insfunc() are used as functions for inserting a
105 * map pair into a map by CFMap::newpair().
106 *
107**/
108static void
109insfunc ( MapPair & orgp, const MapPair & newp )
110{
111    orgp = newp;
112}
113
114/** void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
115 *
116 * CFMap::newpair() - insert a MapPair into a CFMap.
117 *
118**/
119void
120CFMap::newpair ( const Variable & v, const CanonicalForm & s )
121{
122    P.insert( MapPair( v, s ), cmpfunc, insfunc );
123}
124
125/** static CanonicalForm subsrec ( const CanonicalForm & f, const MPListIterator & i )
126 *
127 * subsrec() - recursively apply the substitutions in i to f.
128 *
129 * Substitutes algebraic variables, too.  The substituted
130 * expression are not subject to further substitutions.
131 *
132 * Used by: CFMap::operator ()().
133 *
134**/
135static CanonicalForm
136subsrec ( const CanonicalForm & f, const MPListIterator & i )
137{
138    if ( f.inBaseDomain() ) return f;
139    MPListIterator j = i;
140
141    // skip MapPairs larger than the main variable of f
142    while ( j.hasItem() && j.getItem().var() > f.mvar() ) j++;
143
144    if ( j.hasItem() )
145        if ( j.getItem().var() != f.mvar() ) {
146            // simply descend if the current MapPair variable is
147            // not the main variable of f
148            CanonicalForm result = 0;
149            CFIterator I;
150            for ( I = f; I.hasTerms(); I++ )
151                result += power( f.mvar(), I.exp() ) * subsrec( I.coeff(), j );
152            return result;
153        }
154        else {
155            // replace the main variable of f with the image of
156            // the current variable under MapPair
157            CanonicalForm result = 0;
158            CanonicalForm s = j.getItem().subst();
159            CFIterator I;
160            // move on to the next MapPair
161            j++;
162            for ( I = f; I.hasTerms(); I++ )
163                result += subsrec( I.coeff(), j ) * power( s, I.exp() );
164            return result;
165        }
166    else
167        return f;
168}
169
170/** CanonicalForm CFMap::operator () ( const CanonicalForm & f ) const
171 *
172 * CFMap::operator () - apply CO to f.
173 *
174 * See subsrec() for more detailed information.
175 *
176**/
177CanonicalForm
178CFMap::operator () ( const CanonicalForm & f ) const
179{
180    MPListIterator i = P;
181    return subsrec( f, i );
182}
183
184#ifndef NOSTREAMIO
185/** OSTREAM & operator << ( OSTREAM & s, const CFMap & m )
186 *
187 * operator << - print a CFMap ("( V[1] -> S[1], ..., V[n] ->  * S[n] )".
188 *
189**/
190OSTREAM &
191operator << ( OSTREAM & s, const CFMap & m )
192{
193    m.P.print(s);
194    return s;
195}
196#endif /* NOSTREAMIO */
197
198/** CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
199 *
200 * compress() - compress the canonical form f.
201 *
202 * Compress the polynomial f such that the levels of its
203 * polynomial variables are ordered without any gaps starting
204 * from level 1.  Return the compressed polynomial and a map m to
205 * undo the compression.  That is, if f' = compress(f, m), than f
206 * = m(f').
207 *
208**/
209CanonicalForm
210compress ( const CanonicalForm & f, CFMap & m )
211{
212    CanonicalForm result = f;
213    int i, n;
214    int * degs = degrees( f );
215
216    m = CFMap();
217    n = i = 1;
218    while ( i <= level( f ) ) {
219        while( degs[i] == 0 ) i++;
220        if ( i != n ) {
221            // swap variables and remember the swap in the map
222            m.newpair( Variable( n ), Variable( i ) );
223            result = swapvar( result, Variable( i ), Variable( n ) );
224        }
225        n++; i++;
226    }
227    DELETE_ARRAY(degs);
228    return result;
229}
230
231/** void compress ( const CFArray & a, CFMap & M, CFMap & N )
232 *
233 * compress() - compress the variables occuring in an a.
234 *
235 * Compress the polynomial variables occuring in a so that their
236 * levels are ordered without any gaps starting from level 1.
237 * Return the CFMap M to realize the compression and its inverse,
238 * the CFMap N.  Note that if you compress a member of a using M
239 * the result of the compression is not necessarily compressed,
240 * since the map is constructed using all variables occuring in
241 * a.
242 *
243**/
244void
245compress ( const CFArray & a, CFMap & M, CFMap & N )
246{
247    M = N = CFMap();
248    if ( a.size() == 0 )
249        return;
250    int maxlevel = level( a[a.min()] );
251    int i, j;
252
253    // get the maximum of levels in a
254    for ( i = a.min() + 1; i <= a.max(); i++ )
255        if ( level( a[i] ) > maxlevel )
256            maxlevel = level( a[i] );
257    if ( maxlevel <= 0 )
258        return;
259
260    int * degs = NEW_ARRAY(int,maxlevel+1);
261    int * tmp = NEW_ARRAY(int,maxlevel+1);
262    for ( i = maxlevel; i >= 1; i-- )
263        degs[i] = 0;
264
265    // calculate the union of all levels occuring in a
266    for ( i = a.min(); i <= a.max(); i++ )
267    {
268        tmp = degrees( a[i], tmp );
269        for ( j = 1; j <= level( a[i] ); j++ )
270            if ( tmp[j] != 0 )
271                degs[j] = 1;
272    }
273
274    // create the maps
275    i = 1; j = 1;
276    while ( i <= maxlevel )
277    {
278        if ( degs[i] != 0 )
279        {
280            M.newpair( Variable(i), Variable(j) );
281            N.newpair( Variable(j), Variable(i) );
282            j++;
283        }
284        i++;
285    }
286    DELETE_ARRAY(degs);
287    DELETE_ARRAY(tmp);
288}
289
290/*
291*  compute positions p1 and pe of optimal variables:
292*    pe is used in "ezgcd" and
293*    p1 in "gcd_poly1"
294*/
295static
296void optvalues ( const int * df, const int * dg, const int n, int & p1, int &pe )
297{
298    int i, o1, oe;
299    i = p1 = pe = 0;
300    do
301    {
302        i++;
303        if ( i > n ) return;
304    } while ( ( df[i] == 0 ) || ( dg[i] == 0 ) );
305    p1 = pe = i;
306    if ( df[i] > dg[i] )
307    {
308        o1 = df[i]; oe = dg[i];
309    }
310    else
311    {
312        o1 = dg[i]; oe = df[i];
313    }
314    while ( i < n )
315    {
316        i++;
317        if ( ( df[i] != 0 ) && ( dg[i] != 0 ) )
318        {
319            if ( df[i] > dg[i] )
320            {
321                if ( o1 >= df[i]) { o1 = df[i]; p1 = i; }
322                if ( oe < dg[i]) { oe = dg[i]; pe = i; }
323            }
324            else
325            {
326                if ( o1 >= dg[i]) { o1 = dg[i]; p1 = i; }
327                if ( oe < df[i]) { oe = df[i]; pe = i; }
328            }
329        }
330    }
331}
332
333
334/** void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
335 *
336 * compress() - compress the variables occurring in f and g with respect
337 * to optimal variables
338 *
339 * Compress the polynomial variables occurring in f and g so that
340 * the levels of variables common to f and g are ordered without
341 * any gaps starting from level 1, whereas the variables occuring
342 * in only one of f or g are moved to levels higher than the
343 * levels of the common variables.  Return the CFMap M to realize
344 * the compression and its inverse, the CFMap N.
345 * N needs only variables common to f and g.
346 *
347**/
348void
349compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
350{
351    int n = tmax( f.level(), g.level() );
352    int i, k, p1, pe;
353    int * degsf = NEW_ARRAY(int,n+1);
354    int * degsg = NEW_ARRAY(int,n+1);
355
356    for ( i = 0; i <= n; i++ )
357    {
358        degsf[i] = degsg[i] = 0;
359    }
360
361    degsf = degrees( f, degsf );
362    degsg = degrees( g, degsg );
363    optvalues( degsf, degsg, n, p1, pe );
364
365    i = 1; k = 1;
366    if ( pe > 1 )
367    {
368        M.newpair( Variable(pe), Variable(k) );
369        N.newpair( Variable(k), Variable(pe) );
370        k++;
371    }
372    while ( i <= n )
373    {
374        if ( degsf[i] > 0 && degsg[i] > 0 )
375        {
376            if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
377            {
378                M.newpair( Variable(i), Variable(k) );
379                N.newpair( Variable(k), Variable(i) );
380            }
381            k++;
382        }
383        i++;
384    }
385    if ( p1 != pe )
386    {
387        M.newpair( Variable(p1), Variable(k) );
388        N.newpair( Variable(k), Variable(p1) );
389        k++;
390    }
391    i = 1;
392    while ( i <= n )
393    {
394        if ( degsf[i] > 0 && degsg[i] == 0 ) {
395            if ( i != k )
396            {
397                M.newpair( Variable(i), Variable(k) );
398                k++;
399            }
400        }
401        else if ( degsf[i] == 0 && degsg[i] > 0 )
402        {
403            if ( i != k )
404            {
405                M.newpair( Variable(i), Variable(k) );
406                k++;
407            }
408        }
409        i++;
410    }
411
412    DELETE_ARRAY(degsf);
413    DELETE_ARRAY(degsg);
414}
Note: See TracBrowser for help on using the repository browser.