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

/magnus/back_end/AProducts/include/AP-fixups.h

Go to the documentation of this file.
00001 //
00002 // $Id: AP-fixups.h,v 1.9 2000/09/29 20:05:35 bormotov Exp $
00003 //
00004 // Copyright (C) 1996 The New York Group Theory Cooperative
00005 // See magnus/doc/COPYRIGHT for the full notice.
00006 
00007 // Contents:
00008 //
00009 // A temporary collection of various standalone procedures.
00010 // Many of them should better be methods of corresponding classes,
00011 // but we have to discuss the changes.
00012 //
00013 // Principal Authors: Eugene Paderin, Dmitry Pechkin
00014 //
00015 // Status: draft
00016 //
00017 // Revision History:
00018 //
00019 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00020 //
00021 // Discussion:
00022 //
00023 // Bugs:
00024 //
00025 //
00026 // Special Notes:
00027 //
00028 //
00029 
00030 #ifndef _FIXUPS_H_
00031 #define _FIXUPS_H_
00032 
00033 #include "SGofFreeGroup.h"
00034 #include "Associations.h"
00035 #include "File.h"
00036 
00037 struct RelatorConjugate 
00038 {
00039 
00040   RelatorConjugate( ) : relator(), conjugator() { }
00041 
00042   RelatorConjugate( const Word& r, const Word& c )
00043     : relator(r), conjugator(c) { }
00044 
00045   // Copy constructor, operator= and destructor are supplied by compiler.
00046   bool operator==( const RelatorConjugate& t) const 
00047   {
00048     return relator == t.relator && conjugator == t.conjugator;
00049   }
00050 
00051   // Data members:
00052   Word relator, conjugator;
00053 };
00054 
00055 // Standard I/O routines.
00056 inline ostream& operator<<( ostream& ostr, const RelatorConjugate& rc )
00057 { // It's a stub. Do nothing. 
00058   ostr << rc.relator << " ^ " << rc.conjugator;
00059   return ostr;
00060 }
00061 inline istream& operator>>( istream& istr, RelatorConjugate& rc )
00062 { // It's a stub. Do nothing. 
00063   return istr;
00064 }
00065 
00066 // IPC support.
00067 inline ostream& operator<( ostream& ostr, const RelatorConjugate& rc )
00068 {
00069   ostr < rc.relator < rc.conjugator;
00070   return ostr;
00071 }
00072 inline istream& operator>( istream& istr, RelatorConjugate& rc )
00073 {
00074   istr > rc.relator > rc.conjugator;
00075   return istr;
00076 }
00077 
00078 
00079 typedef VectorOf<RelatorConjugate> ProductOfRelatorConjugates;
00080 
00081 ProductOfRelatorConjugates conjugateBy( 
00082   const ProductOfRelatorConjugates& product, const Word& conjugator );
00083 
00084 
00085 template <class T>
00086 inline void swap( T& a, T& b ) 
00087 {
00088   T temp = a;
00089   a = b;
00090   b = temp;
00091 }
00092 
00093 // Here go two dummy functions for SGofFreeGroup class. They are absent
00094 // in the class, but are required by VectorOf.
00095 
00096 inline ostream& operator << (ostream& o, const SGofFreeGroup& sg)
00097 {
00098   //error("Dummy function operator<<(ostream&, SGofFreeGroup&) is called.");
00099   warn(" dumb operator<<(ostream&, SGofFreeGroup&) is called. ");
00100   o << " subgroup is ";
00101   sg.parentGroup().printVectorOfWords(o, sg.generators());
00102   o << " of ";
00103   o << sg.parentGroup();
00104   return o;
00105 }
00106 
00107 /*
00108 inline bool operator == (const SGofFreeGroup& a,  const SGofFreeGroup& b)
00109 {
00110   error("Dummy function operator==(SGofFreeGroup&, SGofFreeGroup) is called.");
00111   return true;
00112 }
00113 */
00114 
00115 // here go two local functions dealing with vectors
00116 //@ep I think they'd better be methods of the VectorOf class
00117 
00118 
00119 // exclude i-th element from vector, shifting the remainder left
00120 
00121 template <class T>
00122 inline void excludeFrom(VectorOf<T>& v, int i)
00123 {
00124   int len = v.length();
00125   for(int j=i+1; j<len; j++)
00126     v[j-1] = v[j];
00127   v.shrink(len-1);
00128 }
00129 
00130 // Cyclically permutes vector elements; v[j] becomes v[0].
00131 // Thus j > 0 means `left-shift' j elements.
00132 // Negative j's yield a `right-shift'.
00133 // j's of magnitude exceeding length of *this wrap around.
00134 
00135 template< class T > VectorOf<T> cyclicallyPermute(const VectorOf<T>& v, int j)
00136 {
00137   int len = v.length();
00138   int i = j;
00139   while ( i >= len ) i = i - len;
00140   while ( i < 0 ) i = i + len;
00141   if ( i == 0 ) return v;
00142   
00143   VectorOf<T> res(len);
00144 
00145   int t=0;
00146 
00147   for(int k = i; k < len; k++, t++)
00148     res[t] = v[k];
00149 
00150   for(int k = 0; k < i; k++, t++)
00151     res[t] = v[k];
00152 
00153   return res;
00154 }
00155 
00156 
00157 
00158 // These should be included into FreeGroup class:
00159 
00160 // finds maximal root of given word `w'.
00161 void maximalRootInFreeGroup(const Word& w, Word& root, int& power);
00162 
00163 // Solves conjugacy problem in free group. If yes, computes conjugator.
00164 Trichotomy conjugacyProblem(const FreeGroup& G, const Word& u,
00165                             const Word& v, Word& conjugator );
00166 
00167 
00168 // There are candidates for Word class:
00169 
00170 // counts exponent sum of all generators which are encountered in the word.
00171 VectorOf<int> exponentSum(const Word& w);
00172 
00173 // Returns cyclically reduced form of w such that w = answer^conjugator.
00174 // For better performance, one should rewrite Word::cyclicallyReduce
00175 Word cyclicallyReduce(const Word& w, Word& conjugator);
00176 
00177 // This one is standalone but very general procedure -- should it be
00178 // in /General, or /Global, or somewhere else?
00179 
00180 Word compose(const VectorOf<Word>& v);
00181 // Performs the multiplication of the components of given vector
00182 // and returns the product.
00183 
00184 inline int tailAgreementLength( const Word& u, const Word& v )
00185 {
00186   return u.inverse().agreementLength( v.inverse() );
00187 }
00188 // It returns agreement length of terminal segments of the words.
00189 
00190 int GCD2(int a, int b);
00191 // calculates general common divider.
00192 
00193 Word cyclicallyShortenByRelators( 
00194   const Word& u, const SetOf<Word>& givenRelators,
00195   Word& conjugator, ProductOfRelatorConjugates& productOfRelatorConjugates );
00196 // u = w^conjugator * r1^t1 * .. * rk^tk
00197 // Where u is the given word, w -- returned value, 
00198 // ri are some relators or their negatives,
00199 // ti are some words.
00200 
00201 
00202 ////////////////////////////////////////////////////////////////////////////
00203 //                                                                        //
00204 //                                                                        //
00205 //  Helper class:  DetailedReport                                         //
00206 //                                                                        //
00207 //                                                                        //
00208 ////////////////////////////////////////////////////////////////////////////
00209 
00210 class DetailedReport
00211 {
00212 public:
00213 
00214   // Constructors:
00215 
00216   DetailedReport( const FPGroup& group, const VectorOf<Word>& subgroup, 
00217                   const Chars fileName = File().getFileName() );
00218 
00219   DetailedReport( const FPGroup& group, 
00220                   const Chars fileName = File().getFileName() );
00221 
00222   // Accessors:
00223 
00224   ostream& file() { return theFile; }
00225 
00226   bool haveDetails( ) const;
00227 
00228   Chars getFileName( ) const;
00229 
00230   void printDehnTransformationDetails( const Word& w );
00231 
00232   void printTrivialWordDetails( const Word& w, 
00233                                 const ProductOfRelatorConjugates& deco, 
00234                                 const bool header );
00235 
00236   void printNonTrivialWordDetails( const Word& w, 
00237                                    const Chars& expl, 
00238                                    const bool header );
00239 
00240   void printTrivialGeneratorDetails( const Generator& g,        
00241                                      const ProductOfRelatorConjugates& deco, 
00242                                      const bool header );
00243 
00244   void printNonTrivialGeneratorDetails( const Generator& g,     
00245                                         const Chars& explanation, 
00246                                         const bool header );
00247 
00248   void printTrivialCommutatorDetails( const Chars& comm,        
00249                                       const ProductOfRelatorConjugates& deco, 
00250                                       const bool header );
00251 
00252   void printNonTrivialCommutatorDetails( const Chars& comm,
00253                                          const Chars& explanation, 
00254                                          const bool header );
00255   
00256   void printSubgroupElement( const Word& w, 
00257                              const ProductOfRelatorConjugates& deco, 
00258                              const bool header );
00259 
00260 private:
00261 
00262   // function members:
00263 
00264   void printTrivialWordDecomposition( const ProductOfRelatorConjugates& deco );
00265 
00266   void printHeader( const bool header );
00267 
00268   void buildRelators( );
00269 
00270   // data members:
00271 
00272   bool bHaveDetails;
00273   File theFile;
00274   FPGroup G;
00275   VectorOf<Word> H; // subgroup generators
00276   bool builtRelators;
00277   AssociationsOf<Word, int> theRelators;
00278   AssociationsOf<Word, int> theSGenerators;
00279 };
00280 
00281 
00282 inline
00283 bool DetailedReport::haveDetails( ) const
00284 {
00285   return bHaveDetails;
00286 }
00287 
00288 inline 
00289 Chars DetailedReport::getFileName( ) const
00290 {
00291   return theFile.getFileName();
00292 }
00293 
00294 #endif
00295 

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