Changeset 1f28ed in git for factory/cf_map.cc


Ignore:
Timestamp:
Jul 23, 1997, 6:22:34 PM (27 years ago)
Author:
Jens Schmidt <schmidt@…>
Branches:
(u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
Children:
95d5c608e097fb2e4b27e6ab645ceba80a0a64d1
Parents:
e743b32f0ead428621a515ddad45bdd5134975a5
Message:
	* cf_map.cc: doc fix
 	(subsrec): doc fix
	(CFMap): doc fix
	(operator <<): doc fix
	(newpair): doc fix
	(operator =): doc fix
	(operator ()): doc fix
	(compress): doc fix

	* cf_map.cc (CFMap( CFList )): 'P.append()' replaced by 'P.insert()'

	* cf_map.cc (CFList, CFListIterator, MPListIterator): references to
	  List<CanonicalForm>, ListIterator<CanonicalForm>, and
 	  ListIterator<MapPair> replaced by their respective typedefs

	* cf_map.cc (cmpfunc): doc fix
	  (insfunc): doc fix


git-svn-id: file:///usr/local/Singular/svn/trunk@573 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • factory/cf_map.cc

    re743b3 r1f28ed  
    11/* emacs edit mode for this file is -*- C++ -*- */
    2 /* $Id: cf_map.cc,v 1.6 1997-06-30 15:28:50 schmidt Exp $ */
     2/* $Id: cf_map.cc,v 1.7 1997-07-23 16:22:34 schmidt Exp $ */
     3
     4//{{{ docu
     5//
     6// cf_map.cc - definition of class CFMap.
     7//
     8// Used by: cf_gcd.cc, fac_multivar.cc, sm_sparsemod.cc
     9//
     10//}}}
    311
    412#include <config.h>
    513
    6 #include "assert.h"
    7 
    8 #include "cf_defs.h"
     14#include "canonicalform.h"
    915#include "cf_map.h"
    1016#include "cf_iter.h"
    … …  
    1521#endif
    1622
    17 
    18 static int cmpfunc ( const MapPair & p1, const MapPair & p2 );
    19 static void insfunc ( MapPair & orgp, const MapPair & newp );
    20 static CanonicalForm subsrec( const CanonicalForm & f, const ListIterator<MapPair> & i );
    21 
     23//{{{ static int cmpfunc ( const MapPair & p1, const MapPair & p2 )
     24//{{{ docu
     25//
     26// cmpfunc() - compare two map pairs.
     27//
     28// Return -1 if p2's variable is less than p1's, 0 if they are
     29// equal, 1 if p2's level is greater than p1's.
     30//
     31//}}}
     32static int
     33cmpfunc ( const MapPair & p1, const MapPair & p2 )
     34{
     35    if ( p1.var() > p2.var() ) return -1;
     36    else if ( p1.var() == p2.var() ) return 0;
     37    else return 1;
     38}
     39//}}}
     40
     41//{{{ static void insfunc ( MapPair & orgp, const MapPair & newp )
     42//{{{ docu
     43//
     44// insfunc() - assign newp to orgp.
     45//
     46// cmpfunc() and insfunc() are used as functions for inserting a
     47// map pair into a Map.
     48//
     49//}}}
     50static void
     51insfunc ( MapPair & orgp, const MapPair & newp )
     52{
     53    orgp = newp;
     54}
     55//}}}
     56
     57//{{{ static CanonicalForm subsrec( const CanonicalForm & f, const MPListIterator & i )
     58//{{{ docu
     59//
     60// subsrec() - recursively apply the substitutions in i to f.
     61//
     62// Substitutes algebraic variables, too.  The substituted
     63// expression are not subject to further substitutions.
     64//
     65//}}}
     66static CanonicalForm
     67subsrec( const CanonicalForm & f, const MPListIterator & i )
     68{
     69    if ( f.inBaseDomain() ) return f;
     70    MPListIterator j = i;
     71
     72    // skip MapPairs larger than the main variable of f
     73    while ( j.hasItem() && j.getItem().var() > f.mvar() ) j++;
     74
     75    if ( j.hasItem() )
     76        if ( j.getItem().var() != f.mvar() ) {
     77            // simply descend if the current MapPair variable is
     78            // not the main variable of f
     79            CanonicalForm result = 0;
     80            CFIterator I;
     81            for ( I = f; I.hasTerms(); I++ )
     82                result += power( f.mvar(), I.exp() ) * subsrec( I.coeff(), j );
     83            return result;
     84        }
     85        else {
     86            // replace the main variable of f with the image of
     87            // the current variable under MapPair
     88            CanonicalForm result = 0;
     89            CanonicalForm s = j.getItem().subst();
     90            CFIterator I;
     91            // move on to the next MapPair
     92            j++;
     93            for ( I = f; I.hasTerms(); I++ )
     94                result += subsrec( I.coeff(), j ) * power( s, I.exp() );
     95            return result;
     96        }
     97    else
     98        return f;
     99}
     100//}}}
     101
     102//{{{ MapPair& MapPair::operator = ( const MapPair & p )
     103//{{{ docu
     104//
     105// MapPair::operator = - assignment operator.
     106//
     107//}}}
    22108MapPair&
    23 MapPair::operator= ( const MapPair & p )
     109MapPair::operator = ( const MapPair & p )
    24110{
    25111    if ( this != &p ) {
    … …  
    29115    return *this;
    30116}
     117//}}}
    31118
    32119#ifndef NOSTREAMIO
     120//{{{ ostream& operator << ( ostream& s, const MapPair & p )
     121//{{{ docu
     122//
     123// operator << - print a map pair ("V -> S").
     124//
     125//}}}
    33126ostream&
    34127operator << ( ostream& s, const MapPair & p )
    … …  
    37130    return s;
    38131}
     132//}}}
    39133#endif /* NOSTREAMIO */
    40134
    41 CFMap::CFMap ( const List<CanonicalForm> & L )
    42 {
    43     ListIterator<CanonicalForm> i;
     135//{{{ CFMap::CFMap ( const CFList & L )
     136//{{{ docu
     137//
     138// CFMap::CFMap() - construct a CFMap from a CFList.
     139//
     140// Variable[i] will be mapped to CFList[i] under the resulting
     141// map.
     142//
     143//}}}
     144CFMap::CFMap ( const CFList & L )
     145{
     146    CFListIterator i;
    44147    int j;
    45148    for ( i = L, j = 1; i.hasItem(); i++, j++ )
    46         P.append( MapPair( Variable(j), i.getItem() ) );
    47 }
    48 
     149        P.insert( MapPair( Variable(j), i.getItem() ) );
     150}
     151//}}}
     152
     153//{{{ CFMap& CFMap::operator = ( const CFMap & m )
     154//{{{ docu
     155//
     156// CFMap::operator = - assignment operator.
     157//
     158//}}}
    49159CFMap&
    50 CFMap::operator= ( const CFMap & m )
     160CFMap::operator = ( const CFMap & m )
    51161{
    52162    if ( this != &m )
    … …  
    54164    return *this;
    55165}
    56 
     166//}}}
     167
     168//{{{ void CFMap::newpair( const Variable & v, const CanonicalForm & s )
     169//{{{ docu
     170//
     171// CFMap::newpair() - inserts a MapPair into a CFMap.
     172//
     173//}}}
    57174void
    58175CFMap::newpair( const Variable & v, const CanonicalForm & s )
    … …  
    60177    P.insert( MapPair( v, s ), cmpfunc, insfunc );
    61178}
    62 
     179//}}}
     180
     181//{{{ CanonicalForm CFMap::operator () ( const CanonicalForm & f ) const
     182//{{{ docu
     183//
     184// CFMap::operator () - apply the map to f.
     185//
     186// See subsrec() for more detailed information.
     187//
     188//}}}
    63189CanonicalForm
    64 CFMap::operator() ( const CanonicalForm & f ) const
    65 {
    66     ListIterator<MapPair> i = P;
     190CFMap::operator () ( const CanonicalForm & f ) const
     191{
     192    MPListIterator i = P;
    67193    return subsrec( f, i );
    68194}
     195//}}}
    69196
    70197#ifndef NOSTREAMIO
     198//{{{ ostream& operator << ( ostream& s, const CFMap & m )
     199//{{{ docu
     200//
     201// operator << - print a CFMap ("( V[1] -> S[1], ..., V[n] -> // S[n] )".
     202//
     203//}}}
    71204ostream&
    72 operator<< ( ostream& s, const CFMap & m )
     205operator << ( ostream& s, const CFMap & m )
    73206{
    74207    if ( m.P.isEmpty() )
    75208        s << "( )";
    76209    else {
    77         ListIterator<MapPair> i = m.P;
     210        MPListIterator i = m.P;
    78211        s << "( " << i.getItem();
    79212        i++;
    … …  
    86219    return s;
    87220}
     221//}}}
    88222#endif /* NOSTREAMIO */
    89223
     224//{{{ CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
     225//{{{ docu
     226//
     227// compress() - compress the canonical form f.
     228//
     229// Compress the polynomial f such that the levels of its
     230// polynomial variables are ordered without any gaps starting
     231// from level 1.  Return the compressed polynomial and a map m to
     232// undo the compression.  That is, if f' = compress(f, m), than f
     233// = m(f').
     234//
     235//}}}
    90236CanonicalForm
    91237compress ( const CanonicalForm & f, CFMap & m )
    … …  
    100246        while( degs[i] == 0 ) i++;
    101247        if ( i != n ) {
     248            // swap variables and remember the swap in the map
    102249            m.newpair( Variable( n ), Variable( i ) );
    103250            result = swapvar( result, Variable( i ), Variable( n ) );
    … …  
    108255    return result;
    109256}
    110 
     257//}}}
     258
     259//{{{ void compress ( const CFArray & a, CFMap & M, CFMap & N )
     260//{{{ docu
     261//
     262// compress() - compress the variables occuring in an a.
     263//
     264// Compress the polynomial variables occuring in a so that their
     265// levels are ordered without any gaps starting from level 1.
     266// Return the CFMap M to realize the compression and its inverse,
     267// the CFMap N.  Note that if you compress a member of a using M
     268// the result of the compression is not necessarily compressed,
     269// since the map is constructed using all variables occuring in
     270// a.
     271//
     272//}}}
    111273void
    112274compress ( const CFArray & a, CFMap & M, CFMap & N )
    … …  
    117279    int maxlevel = level( a[a.min()] );
    118280    int i, j;
     281
     282    // get the maximum of levels in a
    119283    for ( i = a.min() + 1; i <= a.max(); i++ )
    120284        if ( level( a[i] ) > maxlevel )
    … …  
    122286    if ( maxlevel <= 0 )
    123287        return;
     288
    124289    int * degs = new int[maxlevel+1];
    125290    int * tmp = new int[maxlevel+1];
    126291    for ( i = 1; i <= maxlevel; i++ )
    127292        degs[i] = 0;
     293
     294    // calculate the union of all levels occuring in a
    128295    for ( i = a.min(); i <= a.max(); i++ ) {
    129296        tmp = degrees( a[i], tmp );
    … …  
    132299                degs[j] = 1;
    133300    }
    134     i = 1;
    135     j = 1;
     301
     302    // create the maps
     303    i = 1; j = 1;
    136304    while ( i <= maxlevel ) {
    137305        if ( degs[i] != 0 ) {
    … …  
    145313    delete [] degs;
    146314}
    147 
    148 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
     315//}}}
     316
     317//{{{ void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
     318//{{{ docu
     319//
     320// compress() - compress the variables occurring in f and g.
     321//
     322// Compress the polynomial variables occurring in f and g so that
     323// the levels of variables common to f and g are ordered without
     324// any gaps starting from level 1, whereas the variables occuring
     325// in only one of f or g are moved to levels higher than the
     326// levels of the common variables.  Return the CFMap M to realize
     327// the compression and its inverse, the CFMap N.
     328//
     329//}}}
     330void
     331compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
    149332{
    150333    int n = tmax( f.level(), g.level() );
    … …  
    156339        degsf[i] = degsg[i] = 0;
    157340    }
     341
    158342    degsf = degrees( f, degsf );
    159343    degsg = degrees( g, degsg );
    … …  
    161345    while ( i <= n ) {
    162346        if ( degsf[i] > 0 && degsg[i] > 0 ) {
     347            // store common variables at the beginning
    163348            if ( i != k ) {
    164349                M.newpair( Variable(i), Variable(k) );
    … …  
    168353        }
    169354        else {
     355            // all others at the end
    170356            M.newpair( Variable(i), Variable(m) );
    171357            N.newpair( Variable(m), Variable(i) );
    … …  
    174360        i++;
    175361    }
     362
    176363    delete [] degsf;
    177364    delete [] degsg;
    178365}
    179 
    180 // static functions
    181 
    182 int
    183 cmpfunc ( const MapPair & p1, const MapPair & p2 )
    184 {
    185     if ( p1.var() > p2.var() ) return -1;
    186     else if ( p1.var() == p2.var() ) return 0;
    187     else return 1;
    188 }
    189 
    190 void
    191 insfunc ( MapPair & orgp, const MapPair & newp )
    192 {
    193     orgp = newp;
    194 }
    195 
    196 CanonicalForm
    197 subsrec( const CanonicalForm & f, const ListIterator<MapPair> & i )
    198 {
    199     if ( f.inBaseDomain() ) return f;
    200     ListIterator<MapPair> j = i;
    201     while ( j.hasItem() && j.getItem().var() > f.mvar() ) j++;
    202     if ( j.hasItem() )
    203         if ( j.getItem().var() != f.mvar() ) {
    204             CanonicalForm result = 0;
    205             CFIterator I;
    206             for ( I = f; I.hasTerms(); I++ )
    207                 result += power( f.mvar(), I.exp() ) * subsrec( I.coeff(), j );
    208             return result;
    209         }
    210         else {
    211             CanonicalForm result = 0, s = j.getItem().subst();
    212             CFIterator I;
    213             j++;
    214             for ( I = f; I.hasTerms(); I++ )
    215                 result += subsrec( I.coeff(), j ) * power( s, I.exp() );
    216             return result;
    217         }
    218     else
    219         return f;
    220 }
     366//}}}
Note: See TracChangeset for help on using the changeset viewer.