Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/Map/include/Map.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: Map.h,v 1.6 2000/02/09 23:59:54 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: definition of MapRep and Map classes
00009 //
00010 // * provisional, one class implementation of the notion of map and
00011 //   homomorphism.
00012 //
00013 // Principal Author: Stephane Collart
00014 //
00015 // Status: under trial
00016 //
00017 // Restrictions:
00018 //
00019 // * the map may only be defined in terms of formal images in the
00020 //   generators of the range group
00021 //
00022 // * images can only be computed of formal words in the generators of
00023 //   the domain group
00024 //
00025 // * in order for formal words to have meaningful interpretations in the
00026 //   domain and range groups, both must be finitely generated
00027 //
00028 // * in keeping with the restriction to formal word images, the default
00029 //   is to evaluate an image as a formal word; to compute an evaluated
00030 //   image, use evalImage() and postEvalImage().
00031 //
00032 // Discussion:
00033 //
00034 // * Is it convenient for a map to be default initialised to the
00035 //   trivial map (everything mapped to the identity?) Is there
00036 //   and alternative? Should in cases where there are enough generators
00037 //   in the range the identity be preferred? And then all the necessary
00038 //   checks be made?
00039 //
00040 // * When moving to a more general map scheme, permitting e.g.
00041 //   additionally + images defined via actual elements + arbitrary domain
00042 //   and map groups, + etc, more machinery must be provided to
00043 //   distinguish and deal with the various cases in which formal or
00044 //   actual elements are encountered.
00045 //
00046 // Revision History:
00047 //
00048 // *@rn: dp, ep should indicate their changes here.
00049 //
00050 //  07/96 Alexey M. implemented IPC tools
00051 //
00052 //  01/99 Dmitry B. changed operator == for MapRep (see comments below)
00053 //
00054 
00055 
00056 #ifndef _MAP_H_
00057 #define _MAP_H_
00058 
00059 #include <iostream.h>
00060 
00061 #include "GenericObject.h"
00062 #include "DerivedObjectOf.h"
00063 #include "Vector.h"
00064 #include "Set.h"
00065 #include "Elt.h"
00066 #include "Group.h"
00067 #include "FGGroup.h"
00068 #include "FPGroup.h"
00069 //#include "FreeGroup.h"
00070 
00071 
00072 //------------------------- MapRep ---------------------------//
00073 
00074 struct MapRep : GenericRep {
00075 
00076   // constructors:
00077 
00078   // no default constructor
00079 
00080   // copy constructor suppled by compiler (does logical deep-copy)
00081 
00082   MapRep( const FGGroup& domain,
00083           const FGGroup& range ) :
00084     theDomain(domain), theRange(range), 
00085     theGeneratingImages(domain.numberOfGenerators())  { }
00086 
00087   MapRep(const FGGroup& domain,
00088          const FGGroup& range,
00089          const VectorOf<Word>& generatingImages ) :
00090     theDomain(domain),
00091     theRange(range),
00092     theGeneratingImages(generatingImages) { }
00093 
00094   // destructor supplied by compiler (members have own destructors)
00095 
00096   // representation members:
00097 
00098   PureRep* clone( ) const { return new MapRep(*this); }
00099 
00100   // standard operators
00101 
00102   /* @db we should probably just check the number of generators,
00103          not to compare the whole groups?
00104 
00105   bool operator == (const MapRep& m) const {
00106     return (theDomain == m.theDomain && theRange == m.theRange &&
00107             theGeneratingImages == m.theGeneratingImages);
00108   }
00109   */
00110   bool operator == (const MapRep& m) const {
00111     return 
00112       ( theDomain.numberOfGenerators() == m.theDomain.numberOfGenerators() 
00113         && theRange.numberOfGenerators() == m.theRange.numberOfGenerators() 
00114         && theGeneratingImages == m.theGeneratingImages
00115         );
00116   }
00117 
00118   // I/O
00119 
00120   MapRep* readFrom(istream& istr, Chars& errMesg) const;
00121 
00122 
00123   //  virtual void checkMapProperties() const;
00124   // Checks whether the map is a monomorphism and/or epimorphism.
00125   // Sets corresponding flags.
00126   // This can be done only for homomorphisms (isHom is true) and
00127   // only for free groups.
00128 
00129 
00130   //////////////////////////////////////////////////////////////////////
00131   //                                                                  //
00132   // Type Stuff and Access:                                           //
00133   //                                                                  //
00134   //////////////////////////////////////////////////////////////////////
00135 
00136   static const Type theMapType;
00137 
00138   static Type type() { return theMapType; }
00139 
00140   Type actualType() const { return type(); } // overrides
00141 
00142   /////////////////////////////////////////////////////////////////////////
00143   //                                                                     //
00144   // IPC tools:                                                          //
00145   //                                                                     //
00146   /////////////////////////////////////////////////////////////////////////
00147 
00148   void  write( ostream& ostr ) const {
00149       ostr < theDomain;
00150       ostr < theRange;
00151       ostr < theGeneratingImages;
00152       ostr < theFlags.isHom <  theFlags.isMono <  theFlags.isEpi;
00153   }
00154   void  read( istream& istr ){
00155       istr > theDomain;
00156       istr > theRange;
00157       istr > theGeneratingImages;
00158       istr >  theFlags.isHom >  theFlags.isMono > theFlags.isEpi;
00159   }
00160 
00161   // data members:
00162 
00163   // real data:
00164   FGGroup theDomain;
00165   FGGroup theRange;
00166   VectorOf<Word> theGeneratingImages;
00167 
00168   // flags:
00169   struct MapProperties {
00170     Trichotomy isHom;
00171     Trichotomy isMono;
00172     Trichotomy isEpi;
00173     MapProperties( ) :
00174       isHom(dontknow),
00175       isMono(dontknow),
00176       isEpi(dontknow)
00177     { }
00178   };
00179   
00180   MapProperties theFlags;
00181 
00182 private:
00183 
00184   MapRep& operator = ( const MapRep& );
00185   // disable assignment
00186 
00187 };
00188 
00189 
00190 //-------------------------- Map ---------------------------//
00191 
00192 
00193 class Map : public DerivedObjectOf<GenericObject,MapRep> {
00194 
00195 public:
00196 
00197   ////////////////////////////////////////////////////////////////////
00198   //                                                                //
00199   // Constructors                                                   //
00200   //                                                                //
00201   ////////////////////////////////////////////////////////////////////
00202 
00203   // @stc note the complete lack of consistency checks in the
00204   // constructors
00205 
00206   // no default constructor: domain and range groups must be given
00207 
00208   Map( ) :
00209     DerivedObjectOf<GenericObject,MapRep>(
00210       new MapRep(FPGroup(),FPGroup(), VectorOf<Word>())
00211                                                                                                                 )
00212   { }
00213   // copy constructor supplied by compiler
00214 
00215   Map( const FGGroup& domain,
00216        const FGGroup& range ) :
00217     DerivedObjectOf<GenericObject,MapRep>(
00218                                           new MapRep(domain, range, VectorOf<Word>(domain.numberOfGenerators()))
00219                                           )
00220   { }
00221   // to construct a map with unspecified images;
00222   // by default, becomes the trivial map, i.e.
00223   // the map mapping everything to the identity;
00224   // Word's default constructor takes care of initialising
00225   // the generating images to the identity.
00226 
00227   Map( const FGGroup& domain,
00228        const FGGroup& range,
00229        const VectorOf<Word>& generatingImages ) :
00230     DerivedObjectOf<GenericObject,MapRep>(
00231                                           new MapRep(domain,range,generatingImages)
00232                                           ) {
00233 
00234 #if SAFETY > 0 // temporary restriction
00235       if (generatingImages.length() != domain.numberOfGenerators())
00236         error("wrong number of generating images in"
00237               " Map::Map(domain,range,generatingImages)");
00238 #endif
00239   }
00240   // to construct a map, given a domain and range group, and images
00241   // for the generators of the domain
00242   // @stc this should do some fancy stuff to deal with cases when
00243   // too few or too many generating images are given (both could be
00244   // legal with appropriate semantics)
00245 
00246   // destructor supplied by compiler
00247 
00248   ////////////////////////////////////////////////////////////////////
00249   //                                                                //
00250   // Standard Operators                                             //
00251   //                                                                //
00252   ////////////////////////////////////////////////////////////////////
00253 
00254   bool operator == ( const Map& m ) const { 
00255     return look() == m.look() || *look() == *m.look(); 
00256   }
00257 
00258   ////////////////////////////////////////////////////////////////////
00259   //                                                                //
00260   // Accessors / Modifiers                                          //
00261   //                                                                //
00262   ////////////////////////////////////////////////////////////////////
00263 
00264   static Type type( ) { return MapRep::type(); }
00265 
00266   // @stc it is assumed that domain, range and generatingImages
00267   // in their entirety are modified infrequently, hence seperate
00268   // members are provided to (re)set them
00269   // individual generatingImages might be modified more often;
00270   // hence, for convenience, an intermediate assignable result is
00271   // constructed when taking the image of a generator
00272 
00273   const FGGroup& domain( ) const { return look()->theDomain; }
00274   // to poll the domain of definition of the map
00275   // not for modification
00276 
00277   const FGGroup& range( ) const { return look()->theRange; }
00278   // to poll the range of definition of the map
00279   // not for modification
00280 
00281   void setDomain( const FGGroup& g );
00282   // to modify domain group; if the number of generators of g is less
00283   // than the number of stored generating images, the extra ones are
00284   // thrown away; if it is greater, the additional generating images
00285   // are uninitialised
00286   // @stc more fancy facilities should be provided to specify how one
00287   // wants to reuse the old images.
00288 
00289   void setRange( const FGGroup& g ) { change()->theRange = g; }
00290   // to set of modify range group
00291   // @stc this should check the images for validity
00292 
00293   const VectorOf<Word>& generatingImages( ) const
00294   { return look()->theGeneratingImages; }
00295   // to poll the defining images of the map
00296   // not for modification
00297 
00298   Word generatingImages( int i ) const
00299   { return look()->theGeneratingImages[i]; }
00300   // to poll the i'th defining image (0-based indexing)
00301   // not for modification
00302   // @stc this cannot be made to return a const ref, as
00303   // theGeneratingImages[i] is not an lvalue and this would be a
00304   // a dangling reference
00305   // when changing the MapRep this could change
00306 
00307   Word generatingImages( const Generator& g ) const {
00308     int Ord = ord(g)-1;
00309     if( Ord >= 0 ) 
00310       return generatingImages(Ord);
00311     else 
00312       return generatingImages(-Ord).inverse();
00313   }
00314 
00315   void setGeneratingImages( const VectorOf<Word> gi ) {
00316 
00317 #if SAFETY > 0
00318     if (gi.length() != domain().numberOfGenerators())
00319       error("wrong number of generating images in"
00320             " Map::setGeneratingImages( const VectorOf<Word> )");
00321 #endif
00322 
00323     change()->theGeneratingImages = gi;
00324   }
00325   // to set or modify generating images
00326 
00327   void setGeneratingImages( int i, const Word& e  ) {
00328 
00329 #if SAFETY > 0
00330     if (i < 0 || i >= domain().numberOfGenerators())
00331       error("generating image index out of range in"
00332             " Map::setGeneratingImages(int, const Word&)");
00333 #endif
00334     change()->theGeneratingImages[i] = e;
00335   }
00336   // to assign to the i-th (0-based) generating image
00337 
00338   void setGeneratingImages( const Generator& g, const Word& w ) {
00339     int Ord = ord(g);
00340     if( Ord > 0 ) setGeneratingImages(Ord-1, w);
00341     else setGeneratingImages(-Ord-1, w.inverse());
00342   }
00343         
00344   ////////////////////////////////////////////////////////////////////
00345   //                                                                //
00346   // Mapping methods                                                //
00347   //                                                                //
00348   ////////////////////////////////////////////////////////////////////
00349 
00350   // computing images:
00351   // formally:
00352 
00353   Word imageOf( const Word& w ) const
00354   { return w.replaceGenerators( look()->theGeneratingImages ); }
00355   // takes a formal word in the generators of domain and evaluates its
00356   // `image' in range; if the images are defined via formal words,
00357   // then the result is also a formal word.
00358   // @stc this bears discussion -- should a seperate image evaluater
00359   // also be provided?
00360 
00361   Word imageOf( const Generator& g ) const;
00362   // image of generator g; not an lvalue
00363 
00364   // computing images:
00365   // evaluated:
00366 
00367   Elt evalImage( const Word& w ) const;
00368   // to compute the image, using the range's operations
00369 
00370   Elt postEvalImage( const Word& w ) const {
00371     return range().eval( imageOf(w) );
00372   }
00373   // to compute an image formally, the evaluate it in the range
00374 
00375   // operations on maps:
00376 
00377   friend Map composition( const Map& secondMap,
00378                           const Map& firstMap );
00379   // map-theoretic composition
00380 
00381   Map& composeAfter( const Map& firstMap );
00382   // equivalent to as *this = composition(*this,firstMap);
00383   // @stc tricky one to name: not to confuse the order of composition
00384 
00385   Map operator | ( const Map& secondMap )
00386   { return composition(secondMap,*this); }
00387   // @stc this is a tentative operator abbreviation for
00388   // composition -- its intuitive iterpretation should be a pipe,
00389   // hence composition is left to right; its advantage is to permit
00390   // syntactically light concatenation: fcomp = f1 | f2 | f3;
00391   // In the same line of thought an Word | Map is provided below
00392   // @stc not a global to avoid most kinds of unintended conversions
00393 
00394   ////////////////////////////////////////////////////////////////////
00395   //                                                                //
00396   // Mapping properties                                             //
00397   //                                                                //
00398   ////////////////////////////////////////////////////////////////////
00399 
00400   // @stc values cast to Trichotomy before returning to keep warnings
00401   // silent
00402 
00403   Trichotomy extendsToHom( ) const {
00404     return look()->theFlags.isHom;
00405   }
00406 
00407   void putIsMono( ) const { enhance()->theFlags.isMono = yes; }
00408 
00409   Trichotomy isMono( ) const
00410   { return Trichotomy(look()->theFlags.isMono); }
00411 
00412   void putIsEpi( ) const { enhance()->theFlags.isEpi = yes; }
00413  
00414   Trichotomy isEpi( ) const
00415   { return Trichotomy(look()->theFlags.isEpi); }
00416  
00417   Trichotomy isIso( ) const { 
00418 
00419     if ( isMono() == dontknow || isEpi() == dontknow) return dontknow;
00420     else return ( isMono() == yes && isEpi() == yes );
00421   }
00422 
00423   Trichotomy isTrivialMap( ) const; // @stc impl. tmp.
00424 
00425   ////////////////////////////////////////////////////////////////////
00426   //                                                                //
00427   // I/O                                                            //
00428   //                                                                //
00429   ////////////////////////////////////////////////////////////////////
00430 
00431   void printOn(ostream& ostr) const;
00432  
00433   ////////////////////////////////////////////////////////////////////
00434   //                                                                //
00435   // Debugging stuff                                                //
00436   //                                                                //
00437   ////////////////////////////////////////////////////////////////////
00438  
00439 #ifdef DEBUG
00440 
00441   //friend int main( );
00442 
00443   bool consistent( ) {
00444     // the map object is assumed to be consistent if it has no defining
00445     // images (uninitialised) or the correct number of defining images
00446 
00447     if (look()->theGeneratingImages.length() !=
00448         look()->theDomain.numberOfGenerators() &&
00449         look()->theGeneratingImages.length() != 0)
00450       return false;
00451     return true;
00452     // @stc this should also check the defining images themselves
00453     // for consistency
00454   }
00455 
00456 #endif
00457 
00458   ////////////////////////////////////////////////////////////////////
00459   //                                                                //
00460   // I/O                                                            //
00461   //                                                                //
00462   ////////////////////////////////////////////////////////////////////
00463 
00464   friend IStreamPoll operator >> ( istream&, Map& );
00465 
00466 
00467   /////////////////////////////////////////////////////////////////////////
00468   //                                                                     //
00469   // IPC tools:                                                          //
00470   //                                                                     //
00471   /////////////////////////////////////////////////////////////////////////
00472 
00473   friend ostream& operator < ( ostream& ostr, const Map& M )
00474   {
00475     M.look()->write(ostr);
00476     return ostr;
00477   }
00478   
00479   friend istream& operator > ( istream& istr, Map& M)
00480   {
00481     M.change()->read(istr);
00482     return istr;
00483   }
00484 
00485 
00486   ////////////////////////////////////////////////////////////////////
00487   //                                                                //
00488   // Representation access methods                                  //
00489   //                                                                //
00490   ////////////////////////////////////////////////////////////////////
00491  
00492 protected:
00493  
00494   // Special wrapping constructor to wrap new representations (returned
00495   // by eg. delegated methods) and for base initialisation by derived
00496   // classes:
00497  
00498   Map( MapRep* newrep ) : DerivedObjectOf<GenericObject,MapRep>(newrep) { }
00499 
00500 };
00501 
00502 
00503 //------------------ Related global functions --------------------//
00504 
00505 ostream& operator << ( ostream&, const Map& );
00506 
00507 
00508 #endif

Generated at Tue Jun 19 09:49:37 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001