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

/magnus/back_end/Elt/include/Word.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: Word.h,v 1.7 2000/03/03 04:12:05 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 the Word and Genref classes.
00009 //
00010 // Principal Authors: Stephane Collart, Roger Needham
00011 //
00012 // Status: Useable.
00013 //
00014 // Next Implementation Steps:
00015 //
00016 // * Need to classify and order the methods and operators better.
00017 //
00018 // * Need to decide on a more coherent scheme where and how to declare
00019 //   global functions on container classes of words. In particular,
00020 //   functions which modify their arguments in place need a closer
00021 //   look. (are they really nice and convenient to use? - problem
00022 //   of unnecessarily cloning).
00023 //
00024 // Revision History:
00025 //
00026 // 4.6.94 @stc added
00027 //   method replaceGenerators( const VectorOf<Elt>& eltvec) const
00028 // 22.11.94 @stc added
00029 //   int agreementLength( const Word& ) const;
00030 //   SetOf<Word>& closeUnderInverses(SetOf<Word>& S);
00031 //   SetOf<Word>& closeUnderCyclicPermutations(SetOf<Word>& S);
00032 //   inline SetOf<Word>& symmetrise(SetOf<Word>& S);
00033 // 7.12.94 @stc added bool isProperPower from the Omsk randomMSC stuff
00034 // 12/16/94 @rn Added nextFreelyReduced, nextCyclicallyReduced.
00035 // 12/16/94 @rn Added maximalRoot global function. It must be merged with
00036 //              isProperPower.
00037 //
00038 // 12/06/95 Roger added bool allExponentSumsZero( ).
00039 //
00040 // * 7/96 Dmitry B. made porting to gcc 2.7.2.
00041 //
00042 
00043 #ifndef _WORD_H_
00044 #define _WORD_H_
00045 
00046 #include "Elt.h"
00047 #include "WordRep.h"
00048 #include "Generator.h"
00049 #include "Vector.h"
00050 #include "List.h"
00051 #include "Chars.h"
00052 #include "DerivedObjectOf.h"
00053 
00054 
00055 class Genref;
00056 
00057 class Word : public DerivedObjectOf<Elt,WordRep> {
00058 
00059 public:  
00060 
00061 ///////////////////////////////////////////////////////////////////////
00062 //                                                                   //
00063 // Constructors:                                                     //
00064 //                                                                   //
00065 ///////////////////////////////////////////////////////////////////////
00066 
00067   Word( ) : DerivedObjectOf<Elt,WordRep>(new WordRep(0)) { }
00068   // Default constructor makes empty word.
00069 
00070   // copy constructor supplied by compiler
00071 
00072   Word( const VectorOf<Generator>& v ) :
00073     DerivedObjectOf<Elt,WordRep>(new WordRep(v))
00074   { }
00075   // For initializing a Word from a Vector of Generators.
00076 
00077   Word( const ListOf<Generator>& l ) :
00078     DerivedObjectOf<Elt,WordRep>(new WordRep(l))
00079   { }
00080   // For initializing a Word from a List of Generators.
00081 
00082   Word( const Generator& g ) : DerivedObjectOf<Elt,WordRep>( new WordRep(g) ) { }
00083   // Cast constructor.
00084 
00085   Word( const Elt& e ) : DerivedObjectOf<Elt,WordRep>( e ) { }
00086   // Cast constructor.
00087   
00088   // destructor supplied by compiler
00089 
00090 ///////////////////////////////////////////////////////////////////////
00091 //                                                                   //
00092 // Type and representation stuff:                                    //
00093 //                                                                   //
00094 ///////////////////////////////////////////////////////////////////////
00095  
00096   static Type type( ) { return WordRep::type(); }
00097  
00098   // inherited from Elt:
00099   // Type actualType( ) const { return look()->actualType(); }
00100 
00101 ///////////////////////////////////////////////////////////////////////
00102 //                                                                   //
00103 // Methods:                                                          //
00104 //                                                                   //
00105 ///////////////////////////////////////////////////////////////////////
00106 
00107   int length( ) const { return look()->length(); }
00108 
00109   Generator operator [] ( int i ) const;
00110   // access to const word just gives a val
00111   // @stc added the const version of op[] for const words - selected
00112   // automatically by compiler
00113 
00114   Genref operator [] ( int i );
00115   // Subscripting for random read/write access. Zero-based indexing.
00116   // WordData does bounds checking. Return type is actually Genref,
00117   // to be used as a Generator by the user.
00118   // @stc removed const qualifier to remove loophole
00119 
00120   Bool operator < ( const Word& ) const;
00121   // ShortLex order defined by following order on generators:
00122   // compare them first by magnitude of ord, then g < g^-1.
00123 
00124   Word nextInShortLex(int numberOfGens) const;
00125   // Return the word, not freely reduced, which comes after
00126   // *this in the ShortLex order on numberOfGens generators.
00127 
00128   Word nextFreelyReduced(int numberOfGens) const;
00129   // Return the freely reduced word which comes after
00130   // *this in the ShortLex order on numberOfGens generators.
00131   // It is a fatal error to call this with a non-freely reduced word.
00132 
00133   Word nextCyclicallyReduced(int numberOfGens) const;
00134   // Return the cyclically reduced word which comes after
00135   // *this in the ShortLex order on numberOfGens generators.
00136   // It is a fatal error to call this with a non-freely reduced word.
00137 
00138   Word subword(const int i, const int j) const;
00139   // Return the subword [i, j).
00140 
00141   Word initialSegment(const int i) const {
00142          return subword(0, i);
00143   }
00144 
00145   Word terminalSegment(const int i) const {
00146          return subword(length() - i, length());
00147   }
00148 
00149   Word findAgreement(const Word&) const;
00150   // Return identical initial segment of the argument and *this.
00151 
00152   int agreementLength( const Word& ) const;
00153   // give max length of identical initial segment; more efficient
00154   // than actually constructing segment to determine length
00155 
00156   Word shortenByRelator(const Word&) const;
00157   // Find a subword w of *this which is an initial segment of the argument
00158   // of length more than half of the argument.
00159   // Return *this if there is no such w; otherwise the result of replacing w
00160   // by the inverse of the shorter half.
00161 
00162   int numberOfOccurrences(const Generator& g) const;
00163   // Return the number of g's and -g's in *this.
00164 
00165   int exponentSum(const Generator& g) const;
00166   // Return the exponent sum of g in *this.
00167 
00168   bool allExponentSumsZero( ) const;
00169   // That is, iff this word is trivial in the derived group of the
00170   // ambient free group.
00171 
00172   bool isProperPower( ) const;
00173   // whether *this is a proper power of a non-trivial word.
00174   // @stc might need one which gives you the smallest proper factor too.
00175   // @stc apart from the implementation which might make you blanch,
00176   // there is the Q whether this should reduce first or no: now it does.
00177 
00178   Generator maxOccurringGenerator( ) const;
00179   // Return the generator in *this with ord of maximal magnitude
00180   // in the standard order on integers. It is an error for *this to be
00181   // the trivial word.
00182 
00183   Word replaceGeneratorWithWord(const Generator&, const Word&) const;
00184   // Return the result of replacing each occurrence of the Generator
00185   // (or its inverse) with the Word (or its inverse).
00186 
00187   Elt replaceGenerators( const VectorOf<Elt>& eltvec ) const;
00188   // Return the result of simultaneously replacing generator with ord i+1
00189   // through eltvec[i], i = 0 .. eltvec.length(); it is an error for 
00190   // maxOccuringGenerator() to be greater than eltvec.length()
00191 
00192   Word replaceGenerators( const VectorOf<Word>& eltvec ) const;
00193   // Return the result of simultaneously replacing generator with ord i+1
00194   // through eltvec[i], i = 0 .. eltvec.length(); it is an error for 
00195   // maxOccuringGenerator() to be greater than eltvec.length()
00196   // @stc this method added as temporary palliative to the lack of
00197   // convertibility between various Vectors
00198   // @rn Changed return type to Word to work around g++ 2.6.0 bug,
00199   //     and replaced implementation with more somewhat efficient one.
00200   //     It does not do free reduction.
00201 
00202   Word replaceSubword(const int i, const int j, const Word& w) const;
00203   // Return result of replacing *this[i, j) with w.
00204   // w may have any length.
00205 
00206   Word freelyReduce( ) const;
00207   // Return a freely reduced copy of *this.
00208 
00209   Word cyclicallyReduce(void) const;
00210   // Return a cyclically reduced copy of *this.
00211 
00212   Word cyclicallyPermute(const int j) const;
00213   // Return result where old jth gen becomes new 0th gen.
00214   // Thus w.cyclicallyPermute(j), j > 0, means `left-shift' j letters.
00215   // Negative j's yield a `right-shift'.
00216   // j's of magnitude exceeding length of *this wrap around.
00217 
00218   Word inverse( ) const { return Word(look()->inverse()); }
00219 
00220   // All Word multiplication does pure concatenation without free reduction.
00221 
00222   Word operator * ( const Word& w ) const {
00223          return ( *look() * *w.look() );
00224   }
00225 
00226   Word operator * ( const Generator& x ) {
00227          return Word( look()->rightMultBy(x) );
00228   }
00229 
00230   inline friend Word operator * ( const Generator& x, const Word& w ) {
00231          return Word( w.look()->leftMultBy(x) );
00232   }
00233 
00234   inline friend Word operator * ( const Generator& x, const Generator& y ) {
00235          return Word( new WordRep(x, y) );
00236   }
00237 
00238   Word operator *= ( const Word& w ) {
00239         return *this = *this * w;
00240   }
00241 
00242   Word operator *= ( const Generator& x ) {
00243         return *this = *this * x;
00244   }
00245 
00246 ///////////////////////////////////////////////////////////////////////
00247 //                                                                   //
00248 // Static auxiliary functions:                                       //
00249 //                                                                   //
00250 ///////////////////////////////////////////////////////////////////////
00251 
00252   static Word wordByLexRank( int numGens, int lexRank );
00253   // gives the lexRank-th word with numGens number of Generators in
00254   // the short lexicographic order
00255 
00256   static Word wordByLexRank( VectorOf<int> vi )
00257   // same for call with standardised single argument signature
00258         { return wordByLexRank(vi[0],vi[1]); }
00259 
00260 ///////////////////////////////////////////////////////////////////////
00261 //                                                                   //
00262 // I/O:                                                              //
00263 //                                                                   //
00264 ///////////////////////////////////////////////////////////////////////
00265 
00266   // Inherited from Elt:
00267   // void printOn(ostream&) const; // pseudo-virtual
00268   // void debugPrint(ostream&) const; // pseudo-virtual
00269 
00270     // helper classes
00271  
00272     class EmptyWord {
00273         Chars emptyWord;
00274     public:
00275         EmptyWord( const Chars& ew ) : emptyWord(ew) { };
00276         operator Chars( ) const { return emptyWord; }
00277     };
00278  
00279     class ProductJunctor {
00280         Chars junctor;
00281     public:
00282         ProductJunctor( const Chars& j ) : junctor(j) { };
00283         operator Chars( ) const { return junctor; }
00284     };
00285 
00286 
00287 private:
00288 
00289   typedef WordData::GeneratorPtrType GeneratorPtrType;  // Pointer to generator
00290   typedef WordData::cGeneratorPtrType cGeneratorPtrType;// Same, but const
00291   typedef WordData::GeneratorType GeneratorType;
00292   // A signed integral type. 0 is not used, and the inverse of a generator g
00293   // is -g.
00294 
00295   friend class Genref;
00296   // so Genref can access the representation to perform assignments.
00297 
00298   // Some hidden constructors:
00299 
00300   Word( int len ) : DerivedObjectOf<Elt,WordRep>( new WordRep(len) ) { }
00301   // Returns an uninitialized word of specified length.
00302 
00303   Word( const GeneratorType* p, int len ) :
00304     DerivedObjectOf<Elt,WordRep>( new WordRep(p, len) )
00305   { }
00306   // For initializing a word from a raw array of GeneratorType.
00307 
00308   //@rn:@stc arg type ok?:
00309   Word( EltRep* rep ) : DerivedObjectOf<Elt,WordRep>((WordRep*)rep) { }
00310   // Special constructor to make an object out of a delegated method
00311   // which returns a representation.
00312 
00313 };
00314 
00315 
00316 //--------------------------- Genref ------------------------------//
00317 
00318 
00319 class Genref {
00320   
00321 public:
00322   
00323   // no default constructor because of reference members
00324   // destructor compiler-supplied
00325   
00326   Generator operator = ( const Generator& g ) {
00327          return wref.change()->ref(index) = ord(g);
00328   }
00329 
00330   int operator == ( const Generator& g ) {
00331          return wref.look()->val(index) == g;
00332   }
00333   // @stc as long as there is no global == which takes two Generator
00334   // arguments, this has to be explicitely provided (ARM prohibits
00335   // type conversion to apply method).
00336  
00337   operator Generator( ) { return wref.look()->val(index); }
00338 
00339   
00340 private:
00341 
00342 friend class Word; //@rn only op[] when possible.
00343 
00344   Genref( Word& w, int i ) : wref(w), index(i) { }
00345   // Hide this from unauthorized users.
00346 
00347   // data members
00348   
00349   Word& wref;
00350   
00351   int index;
00352 
00353   // make copy constructor inaccessible
00354   Genref( const Genref& g ) : wref(g.wref), index(g.index) {
00355          error("called hidden Genref copy constructor");
00356   }
00357   
00358   // make assignment operator inaccessible
00359   Genref operator = ( const Genref& g ) {
00360          error("called hidden Genref assignment operator");
00361   }
00362 };
00363 
00364 
00365 //----------------------------------- ------------------------------//
00366 //------------------------------ Word ------------------------------//
00367 //----------------------- inline functions -------------------------//
00368 
00369 
00370 inline Generator Word::operator [] ( int i ) const { return look()->val(i); }
00371 
00372 inline Genref Word::operator [] ( int i ) { return Genref( *this, i ); }
00373 
00374 
00375 
00376 #include "Set.h"
00377 
00378  
00379 //-------------- Word: associated global functions ----------------//
00380 
00381 istream& operator>>( istream& istr, Word& );
00382 
00383 // @rn 12/16/94 This is here temporarily, until we can sort things out.
00384 int maximalRoot(const Word& w);
00385 
00386 
00387 // syntactic operations on container classes of words:
00388 // @stc some or all of these functions could be made into template
00389 // functions for various container classes, if the container classes
00390 // have sufficiently standardised handles.
00391 
00392 
00393 SetOf<Word>& closeUnderInverses(SetOf<Word>& S);
00394 // closes S syntactically to contain all syntactic inverses of words
00395 // in S; returns a reference to the new S.
00396 // Does not freely reduce.
00397 
00398  
00399 SetOf<Word>& closeUnderCyclicPermutations(SetOf<Word>& S);
00400 // closes S syntactically to contain all syntactic cyclic permutations
00401 // of words in S; returns a reference to the new S.
00402 // Does not freely reduce.
00403 
00404 
00405 inline SetOf<Word>& symmetrise(SetOf<Word>& S) {
00406 
00407   return closeUnderCyclicPermutations(closeUnderInverses(S));
00408 }
00409 // closes S syntactically to contain all syntactic inverses and
00410 // syntactic cyclic permutations of words in S; returns a reference
00411 // to the new S.
00412 // Does not freely reduce.
00413 
00414 
00415 int cancellationLambda( const SetOf<Word>& ss );
00416 // computes the smallest lambda such that no two words of ss have a
00417 // common initial segment of length greater than or equal to
00418 // one lamdba-th of either of their lengths.
00419 // ss is assumed to be symmetrised.
00420 // the function returns 0 if lambda is infinite, otherwise the value of
00421 // lambda; as a special case, lambda == 1 means two words agree over
00422 // at least half of one, ie. the words do not define a small
00423 // cancellation group.
00424 // @stc beware that if the words are compacted words, lambda can easily
00425 // overflow; the function does not check this
00426 // @stc need to add security checks
00427 
00428 
00429 Trichotomy hasMetricSmallCancellation( const SetOf<Word>& S, const int lambda );
00430 // This method takes an int argument lambda, and checks whether the given
00431 // words satisfy the C'(1/lambda) condition.
00432 // The words are expected to be freely reduced, and the set symmetrised.
00433 // If any two words R1, R2 in symmetrized relators set such that
00434 // R1 = p * r1 and R2 = p * r2 (graphically) satisfy the condition
00435 // |p| < 1/lambda * min{|R1|, |R2|},  where |w| is the length of a word w,
00436 // then the finitely presented group is the metric small cancellation one,
00437 // and the answer is YES; otherwise NO.
00438 // This function is of limited usefulness, but can refute the small
00439 // cancellation property faster for a given lambda.
00440 // @stc need to add security checks
00441 
00442 #endif
00443 

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