[2dd068] | 1 | // emacs edit mode for this file is -*- C++ -*- |
---|
[997ae52] | 2 | // $Id: cf_map.cc,v 1.2 1997-03-26 16:47:32 schmidt Exp $ |
---|
[2dd068] | 3 | |
---|
| 4 | /* |
---|
| 5 | $Log: not supported by cvs2svn $ |
---|
[997ae52] | 6 | Revision 1.1 1996/07/08 08:17:22 stobbe |
---|
| 7 | "New function compress( f, g, M, N ) that maps the common variables to be |
---|
| 8 | the ones with the lowest level. |
---|
| 9 | " |
---|
| 10 | |
---|
[cc3e5e] | 11 | Revision 1.0 1996/05/17 10:59:44 stobbe |
---|
| 12 | Initial revision |
---|
| 13 | |
---|
[2dd068] | 14 | */ |
---|
| 15 | |
---|
| 16 | #include "assert.h" |
---|
[997ae52] | 17 | |
---|
[2dd068] | 18 | #include "cf_defs.h" |
---|
[997ae52] | 19 | |
---|
[2dd068] | 20 | #include "cf_map.h" |
---|
| 21 | #include "cf_iter.h" |
---|
[cc3e5e] | 22 | #include "templates/functions.h" |
---|
[2dd068] | 23 | |
---|
| 24 | |
---|
| 25 | static int cmpfunc ( const MapPair & p1, const MapPair & p2 ); |
---|
| 26 | static void insfunc ( MapPair & orgp, const MapPair & newp ); |
---|
| 27 | static CanonicalForm subsrec( const CanonicalForm & f, const ListIterator<MapPair> & i ); |
---|
| 28 | |
---|
| 29 | MapPair& |
---|
| 30 | MapPair::operator= ( const MapPair & p ) |
---|
| 31 | { |
---|
| 32 | if ( this != &p ) { |
---|
| 33 | V = p.V; |
---|
| 34 | S = p.S; |
---|
| 35 | } |
---|
| 36 | return *this; |
---|
| 37 | } |
---|
| 38 | |
---|
[997ae52] | 39 | #ifndef NOSTREAMIO |
---|
[2dd068] | 40 | ostream& |
---|
| 41 | operator << ( ostream& s, const MapPair & p ) |
---|
| 42 | { |
---|
| 43 | s << p.var() << " -> " << p.subst(); |
---|
| 44 | return s; |
---|
| 45 | } |
---|
[997ae52] | 46 | #endif /* NOSTREAMIO */ |
---|
[2dd068] | 47 | |
---|
| 48 | CFMap::CFMap ( const List<CanonicalForm> & L ) |
---|
| 49 | { |
---|
| 50 | ListIterator<CanonicalForm> i; |
---|
| 51 | int j; |
---|
| 52 | for ( i = L, j = 1; i.hasItem(); i++, j++ ) |
---|
| 53 | P.append( MapPair( Variable(j), i.getItem() ) ); |
---|
| 54 | } |
---|
| 55 | |
---|
| 56 | CFMap& |
---|
| 57 | CFMap::operator= ( const CFMap & m ) |
---|
| 58 | { |
---|
| 59 | if ( this != &m ) |
---|
| 60 | P = m.P; |
---|
| 61 | return *this; |
---|
| 62 | } |
---|
| 63 | |
---|
| 64 | void |
---|
| 65 | CFMap::newpair( const Variable & v, const CanonicalForm & s ) |
---|
| 66 | { |
---|
| 67 | P.insert( MapPair( v, s ), cmpfunc, insfunc ); |
---|
| 68 | } |
---|
| 69 | |
---|
| 70 | CanonicalForm |
---|
| 71 | CFMap::operator() ( const CanonicalForm & f ) const |
---|
| 72 | { |
---|
| 73 | ListIterator<MapPair> i = P; |
---|
| 74 | return subsrec( f, i ); |
---|
| 75 | } |
---|
| 76 | |
---|
[997ae52] | 77 | #ifndef NOSTREAMIO |
---|
[2dd068] | 78 | ostream& |
---|
| 79 | operator<< ( ostream& s, const CFMap & m ) |
---|
| 80 | { |
---|
| 81 | if ( m.P.isEmpty() ) |
---|
| 82 | s << "( )"; |
---|
| 83 | else { |
---|
| 84 | ListIterator<MapPair> i = m.P; |
---|
| 85 | s << "( " << i.getItem(); |
---|
| 86 | i++; |
---|
| 87 | while ( i.hasItem() ) { |
---|
| 88 | s << ", " << i.getItem(); |
---|
| 89 | i++; |
---|
| 90 | } |
---|
| 91 | s << " )"; |
---|
| 92 | } |
---|
| 93 | return s; |
---|
| 94 | } |
---|
[997ae52] | 95 | #endif /* NOSTREAMIO */ |
---|
[2dd068] | 96 | |
---|
| 97 | CanonicalForm |
---|
| 98 | compress ( const CanonicalForm & f, CFMap & m ) |
---|
| 99 | { |
---|
| 100 | CanonicalForm result = f; |
---|
| 101 | int i, n; |
---|
| 102 | int * degs = degrees( f ); |
---|
| 103 | |
---|
| 104 | m = CFMap(); |
---|
| 105 | n = i = 1; |
---|
| 106 | while ( i <= level( f ) ) { |
---|
| 107 | while( degs[i] == 0 ) i++; |
---|
| 108 | if ( i != n ) { |
---|
| 109 | m.newpair( Variable( n ), Variable( i ) ); |
---|
| 110 | result = swapvar( result, Variable( i ), Variable( n ) ); |
---|
| 111 | } |
---|
| 112 | n++; i++; |
---|
| 113 | } |
---|
| 114 | delete [] degs; |
---|
| 115 | return result; |
---|
| 116 | } |
---|
| 117 | |
---|
| 118 | void |
---|
| 119 | compress ( const CFArray & a, CFMap & M, CFMap & N ) |
---|
| 120 | { |
---|
| 121 | M = N = CFMap(); |
---|
| 122 | if ( a.size() == 0 ) |
---|
| 123 | return; |
---|
| 124 | int maxlevel = level( a[a.min()] ); |
---|
| 125 | int i, j; |
---|
| 126 | for ( i = a.min() + 1; i <= a.max(); i++ ) |
---|
| 127 | if ( level( a[i] ) > maxlevel ) |
---|
| 128 | maxlevel = level( a[i] ); |
---|
| 129 | if ( maxlevel <= 0 ) |
---|
| 130 | return; |
---|
| 131 | int * degs = new int[maxlevel+1]; |
---|
| 132 | int * tmp = new int[maxlevel+1]; |
---|
| 133 | for ( i = 1; i <= maxlevel; i++ ) |
---|
| 134 | degs[i] = 0; |
---|
| 135 | for ( i = a.min(); i <= a.max(); i++ ) { |
---|
| 136 | tmp = degrees( a[i], tmp ); |
---|
| 137 | for ( j = 1; j <= level( a[i] ); j++ ) |
---|
| 138 | if ( tmp[j] != 0 ) |
---|
| 139 | degs[j] = 1; |
---|
| 140 | } |
---|
| 141 | i = 1; |
---|
| 142 | j = 1; |
---|
| 143 | while ( i <= maxlevel ) { |
---|
| 144 | if ( degs[i] != 0 ) { |
---|
| 145 | M.newpair( Variable(i), Variable(j) ); |
---|
| 146 | N.newpair( Variable(j), Variable(i) ); |
---|
| 147 | j++; |
---|
| 148 | } |
---|
| 149 | i++; |
---|
| 150 | } |
---|
| 151 | delete [] tmp; |
---|
| 152 | delete [] degs; |
---|
| 153 | } |
---|
| 154 | |
---|
[cc3e5e] | 155 | void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N ) |
---|
| 156 | { |
---|
| 157 | int n = tmax( f.level(), g.level() ); |
---|
| 158 | int i, k, m; |
---|
| 159 | int * degsf = new int[n+1]; |
---|
| 160 | int * degsg = new int[n+1]; |
---|
| 161 | |
---|
| 162 | for ( i = 0; i <= n; i++ ) { |
---|
| 163 | degsf[i] = degsg[i] = 0; |
---|
| 164 | } |
---|
| 165 | degsf = degrees( f, degsf ); |
---|
| 166 | degsg = degrees( g, degsg ); |
---|
| 167 | i = 1; k = 1; m = n; |
---|
| 168 | while ( i <= n ) { |
---|
| 169 | if ( degsf[i] > 0 && degsg[i] > 0 ) { |
---|
| 170 | if ( i != k ) { |
---|
| 171 | M.newpair( Variable(i), Variable(k) ); |
---|
| 172 | N.newpair( Variable(k), Variable(i) ); |
---|
| 173 | } |
---|
| 174 | k++; |
---|
| 175 | } |
---|
| 176 | else { |
---|
| 177 | M.newpair( Variable(i), Variable(m) ); |
---|
| 178 | N.newpair( Variable(m), Variable(i) ); |
---|
| 179 | m--; |
---|
| 180 | } |
---|
| 181 | i++; |
---|
| 182 | } |
---|
| 183 | delete [] degsf; |
---|
| 184 | delete [] degsg; |
---|
| 185 | } |
---|
| 186 | |
---|
[2dd068] | 187 | // static functions |
---|
| 188 | |
---|
| 189 | int |
---|
| 190 | cmpfunc ( const MapPair & p1, const MapPair & p2 ) |
---|
| 191 | { |
---|
| 192 | if ( p1.var() > p2.var() ) return -1; |
---|
| 193 | else if ( p1.var() == p2.var() ) return 0; |
---|
| 194 | else return 1; |
---|
| 195 | } |
---|
| 196 | |
---|
| 197 | void |
---|
| 198 | insfunc ( MapPair & orgp, const MapPair & newp ) |
---|
| 199 | { |
---|
| 200 | orgp = newp; |
---|
| 201 | } |
---|
| 202 | |
---|
| 203 | CanonicalForm |
---|
| 204 | subsrec( const CanonicalForm & f, const ListIterator<MapPair> & i ) |
---|
| 205 | { |
---|
| 206 | if ( f.inBaseDomain() ) return f; |
---|
| 207 | ListIterator<MapPair> j = i; |
---|
| 208 | while ( j.hasItem() && j.getItem().var() > f.mvar() ) j++; |
---|
| 209 | if ( j.hasItem() ) |
---|
| 210 | if ( j.getItem().var() != f.mvar() ) { |
---|
| 211 | CanonicalForm result = 0; |
---|
| 212 | CFIterator I; |
---|
| 213 | for ( I = f; I.hasTerms(); I++ ) |
---|
| 214 | result += power( f.mvar(), I.exp() ) * subsrec( I.coeff(), j ); |
---|
| 215 | return result; |
---|
| 216 | } |
---|
| 217 | else { |
---|
| 218 | CanonicalForm result = 0, s = j.getItem().subst(); |
---|
| 219 | CFIterator I; |
---|
| 220 | j++; |
---|
| 221 | for ( I = f; I.hasTerms(); I++ ) |
---|
| 222 | result += subsrec( I.coeff(), j ) * power( s, I.exp() ); |
---|
| 223 | return result; |
---|
| 224 | } |
---|
| 225 | else |
---|
| 226 | return f; |
---|
| 227 | } |
---|