My Project  debian-1:4.1.2-p1+ds-2
cf_map.cc
Go to the documentation of this file.
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"
21 
22 /** MapPair & MapPair::operator = ( const MapPair & p )
23  *
24  * MapPair::operator = - assignment operator.
25  *
26 **/
27 MapPair &
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 **/
43 OSTREAM &
45 {
46  s << p.var() << " -> " << p.subst();
47  return s;
48 }
49 
50 void 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 **/
63 CFMap::CFMap ( const CFList & L )
64 {
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 **/
76 CFMap &
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 **/
92 static int
93 cmpfunc ( 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 **/
108 static void
109 insfunc ( 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 **/
119 void
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 **/
135 static CanonicalForm
136 subsrec ( 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 **/
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 **/
190 OSTREAM &
191 operator << ( 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 **/
211 {
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 **/
244 void
245 compress ( 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 */
295 static
296 void 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 **/
348 void
349 compress ( 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 
414 }
MapPair::V
Variable V
Definition: cf_map.h:52
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
MapPair::S
CanonicalForm S
Definition: cf_map.h:53
k
int k
Definition: cfEzgcd.cc:92
canonicalform.h
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
result
return result
Definition: facAbsBiFact.cc:76
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:50
MapPair::print
void print(OSTREAM &) const
Definition: cf_map.cc:50
CFMap
class CFMap
Definition: cf_map.h:84
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
g
g
Definition: cfModGcd.cc:4031
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
subsrec
static CanonicalForm subsrec(const CanonicalForm &f, const MPListIterator &i)
static CanonicalForm subsrec ( const CanonicalForm & f, const MPListIterator & i )
Definition: cf_map.cc:136
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
MapPair::var
Variable var() const
Definition: cf_map.h:60
ftmpl_functions.h
CFIterator::hasTerms
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
Definition: cf_iter_inline.cc:75
CanonicalForm
factory's main class
Definition: canonicalform.h:77
degsg
int * degsg
Definition: cfEzgcd.cc:53
CFMap::CFMap
CFMap()
Definition: cf_map.h:89
Array::min
int min() const
Definition: ftmpl_array.cc:98
MapPair::operator=
MapPair & operator=(const MapPair &p)
MapPair & MapPair::operator = ( const MapPair & p )
Definition: cf_map.cc:28
i
int i
Definition: cfEzgcd.cc:125
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
optvalues
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition: cf_map.cc:296
M
#define M
Definition: sirandom.c:25
Array::max
int max() const
Definition: ftmpl_array.cc:104
Array::size
int size() const
Definition: ftmpl_array.cc:92
CFIterator::exp
CF_NO_INLINE int exp() const
get the current exponent
Definition: cf_iter_inline.cc:105
cf_iter.h
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
MapPair
class MapPair
Definition: cf_map.h:49
operator<<
OSTREAM & operator<<(OSTREAM &s, const MapPair &p)
OSTREAM & operator << ( OSTREAM & s, const MapPair & p )
Definition: cf_map.cc:44
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
cf_map.h
degsf
int * degsf
Definition: cfEzgcd.cc:52
Variable
factory's class for variables
Definition: factory.h:117
CFIterator::coeff
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
Definition: cf_iter_inline.cc:88
CFMap::operator=
CFMap & operator=(const CFMap &m)
CFMap & CFMap::operator = ( const CFMap & m )
Definition: cf_map.cc:77
m
int m
Definition: cfEzgcd.cc:121
cmpfunc
static int cmpfunc(const MapPair &p1, const MapPair &p2)
static int cmpfunc ( const MapPair & p1, const MapPair & p2 )
Definition: cf_map.cc:93
insfunc
static void insfunc(MapPair &orgp, const MapPair &newp)
static void insfunc ( MapPair & orgp, const MapPair & newp )
Definition: cf_map.cc:109
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
p
int p
Definition: cfModGcd.cc:4019
List< CanonicalForm >
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
OSTREAM
#define OSTREAM
Definition: canonicalform.h:16
CFMap::newpair
void newpair(const Variable &v, const CanonicalForm &s)
void CFMap::newpair ( const Variable & v, const CanonicalForm & s )
Definition: cf_map.cc:120
CFMap::operator()
CanonicalForm operator()(const CanonicalForm &f) const
CanonicalForm CFMap::operator () ( const CanonicalForm & f ) const.
Definition: cf_map.cc:178
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
CFMap::P
MPList P
Definition: cf_map.h:87
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:49
ListIterator
Definition: ftmpl_list.h:17