Word.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class Word
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _Word_H_
00010 #define _Word_H_
00011 
00012 
00013 
00014 #include "ObjectOf.h"
00015 #include "Word.h"
00016 #include "WordRep.h"
00017 #include "WordIterator.h"
00018 #include <string>
00019 #include "Alphabet.h"
00020 // #include <strstream>
00021 
00022 #include <set>
00023 using namespace std;
00024 
00025 
00026 //---------------------------------------------------------------------------//
00027 //---------------------------------- Word -----------------------------------//
00028 //---------------------------------------------------------------------------//
00029 
00031 
00038 class Word : public ObjectOf< WordRep >
00039 {
00040 
00041  public:
00042   typedef ConstWordIterator const_iterator;
00043   typedef WordIterator iterator;
00044   
00046   //                                                     //
00047   //  Constructors                                       //
00048   //                                                     //
00050 
00051  public:
00052 
00053   typedef pair< int , int > PII;
00054 
00056   Word( ) : ObjectOf< WordRep >( new WordRep() ) { }
00058   Word( const vector< int >& gens ) : ObjectOf< WordRep >( new WordRep( gens ) ) { }
00060   Word( const list< int >& gens ) : ObjectOf< WordRep >( new WordRep( gens ) ) { }
00062   Word( int g ) : ObjectOf< WordRep >( new WordRep( g ) ) { }
00063   
00064   // copy constructor supplied by compiler
00065   // destructor supplied by compiler
00066   
00067  
00069   //                                                     //
00070   //  Operators                                          //
00071   //                                                     //
00073 public:
00074 
00076 
00079   bool operator < ( const Word& wr ) const { return (*look() < *wr.look( ) ); }
00081   bool operator > ( const Word& wr ) const { return (*look() > *wr.look( ) ); }
00083   bool operator == ( const Word& wr ) const { return (*look() == *wr.look( ) ); }
00085   bool operator != ( const Word& wr ) const { return !(*look() == *wr.look( ) ); }
00086   
00088   inline Word& operator *= ( const Word& w ) { 
00089     *change( ) *= *w.look(); 
00090     return *this;
00091   }
00092   
00094   inline Word operator * ( const Word& w ) const { 
00095     Word result( *this );
00096     result *= w;
00097     return result;
00098   }
00099 
00101   inline Word operator - ( ) const { 
00102     Word result;
00103     (*result.change( )) = look( )->inverse( );
00104     return result;
00105   }
00106 
00107 
00109   //                                                     //
00110   //  Accessors                                          //
00111   //                                                     //
00113         
00114 public:
00115   
00116   const_iterator begin( ) const { return const_iterator(*this); }
00117   const_iterator end  ( ) const { return const_iterator(*this,false); }
00118   iterator       begin( )       { return iterator(*this); }
00119   iterator       end  ( )       { return iterator(*this,false); }
00120   
00122   Word freelyReduce( ) { return freelyReduce( begin() , end( ) ); }
00124   Word freelyReduce( iterator B , iterator E );
00125   // freely reduces a segment of a word specified by [beg,end]. 
00126   // Most of the operations produce freely reduced words,
00127   // except operations insert, remove. The function takes linear time to performs
00128   // which is not efficient. So, either try to avoid uses of functions insert and remove
00129   // or try to bound the changes in variables beg and end
00130   
00132   static Word randomWord( int n , int wLen );
00134   static Word randomWord( int n , int wLenMin, int wLenMax );
00135 
00137   inline const list< int >& getList( ) const { return look( )->getList( ); }
00139   inline list< int >& getList( ) { return change( )->getList( ); }
00140   
00142   inline int length( ) const { return look( )->length( ); }
00143 
00145   inline Word& push_back ( int gen ) { change()->push_back ( gen ); return *this; }
00147   inline Word& push_front( int gen ) { change()->push_front( gen ); return *this; }
00149   Word& push_back ( const Word& w );
00151   Word& push_front( const Word& w );
00152 
00154   int getPower( Word& base ) const { return look( )->getPower( *base.change( ) ); }
00155   
00157   bool doesContain( const int& gen ) const { return look( )->doesContain( gen ); }
00158   
00160   inline void cyclicLeftShift( )  { change( )->cyclicLeftShift(  ); }
00162   inline void cyclicRightShift( ) { change( )->cyclicRightShift( ); }
00163   
00165   inline Word cyclicallyReduce( ) const {
00166     Word result( *this );
00167     result.change( ) -> cyclicallyReduce( );
00168     return result;
00169   }
00170   
00172   inline void cyclicallyReduceWord( ) { change( ) -> cyclicallyReduce( ); }
00173 
00175   inline Word cyclicallyReduce( Word& conjugator ) const {
00176     Word result( *this );
00177     result.change( ) -> cyclicallyReduce( *conjugator.change( ) );
00178     return result;
00179   }
00181   inline void cyclicallyReduceWord( Word& conjugator ) { 
00182     change( ) -> cyclicallyReduce( *conjugator.change( ) ); 
00183   }
00184 
00186   inline Word inverse( ) const {
00187     Word result;
00188     (*result.change( )) = look( )->inverse( );
00189     return result;
00190   }
00191 
00193 
00194   inline Word cyclicallyPermute( int n ) const {
00195     Word result( *this );
00196     result.change( ) -> cyclicallyPermute( n );
00197     return result;
00198   }
00200   inline Word& _cyclicallyPermute( int n ) {
00201     change( ) -> cyclicallyPermute( n );
00202     return *this;
00203   }
00204 
00206   inline Word initialSegment( int len ) const {
00207     Word result( *this );
00208     result.change( ) -> initialSegment( len );
00209     return result;              
00210   }
00211 
00213   inline Word terminalSegment( int len ) const {
00214     Word result( *this );
00215     result.change( ) -> terminalSegment( len );
00216     return result;                      
00217   }
00218 
00219   // Get a segment of the word defined by ???
00220   inline Word segment( int from , int to ) const {
00221     Word result( *this );
00222     result.change( ) -> segment( from , to );
00223     return result;      
00224   }
00225   
00226   inline int exponentSum( const int& gen ) const {
00227     return look( )->exponentSum( gen );
00228   }
00229   
00230   int isIn( const int& gen ) const {
00231     return look( )->isIn( gen );
00232   }
00233   
00234   Word power( int t ) const;
00235   
00236 
00238   template< class ConstIntIterator > 
00239   void insert( int pos , ConstIntIterator B , ConstIntIterator E );
00240 
00242   void insert( int pos , int g );
00243 
00245   template< class ConstIntIterator > 
00246   void insert( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00248   void insert( WordIterator it , int g );
00249 
00251   void replace( WordIterator it , const Generator& g );
00252 
00254   void replace( int pos , const Generator& g );
00255 
00257   template< class ConstIntIterator > 
00258     void replace( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00259 
00261 
00263   Word minimalEquivalentForm( const set< int >& permutableGenerators , bool inverses , bool cyclicPermutations ) const;
00264 
00265 
00267   //                                                     //
00268   //  Internal functions                                 //
00269   //                                                     //
00271 
00272  private:
00273 
00274          
00276   //                                                     //
00277   //  I/O                                                //
00278   //                                                     //
00280 
00281   
00282   friend ostream& operator << ( ostream& os , const Word& w ) {
00283     InfiniteAlphabet::defaultAlphabet.printWord( os, w );
00284     return os;
00285     //return w.look( )->printOn( os );
00286   }
00287   
00288   friend istream& operator >> ( istream& is ,  Word& w ) {
00289     w = InfiniteAlphabet::defaultAlphabet.readWord( is );
00290     return is;
00291     //return w.look( )->printOn( os );
00292   }
00293 
00294   ostream& printOn ( ostream& os ) const {
00295     InfiniteAlphabet::defaultAlphabet.printWord( os, *this );
00296     return os;
00297     //return look( )->printOn( os );
00298   }
00299   
00300   /*
00301     friend ostream& operator << ( ostream& os , const Word& w ) {
00302     os << *w.look( );
00303     return os;
00304     }
00305   */
00306   
00307 
00308 
00310   //                                                     //
00311   //  Data members                                       //
00312   //                                                     //
00314 
00315   private:
00316                 
00317 };
00318 
00319 
00320 #endif

Generated on Mon Feb 27 22:47:04 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.4