source: git/factory/cf_map.cc @ 90c9e3

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