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   template< class IntIterator > 
00065     Word( const IntIterator& B , const IntIterator& E ) : ObjectOf< WordRep >( new WordRep( B , E ) ) { }
00066 
00067   // copy constructor supplied by compiler
00068   // destructor supplied by compiler
00069   
00070  
00072   //                                                     //
00073   //  Operators                                          //
00074   //                                                     //
00076 public:
00077 
00079 
00082   bool operator < ( const Word& wr ) const { return (*look() < *wr.look( ) ); }
00084   bool operator > ( const Word& wr ) const { return (*look() > *wr.look( ) ); }
00086   bool operator == ( const Word& wr ) const { return (*look() == *wr.look( ) ); }
00088   bool operator != ( const Word& wr ) const { return !(*look() == *wr.look( ) ); }
00089   
00091   inline Word& operator *= ( const Word& w ) { 
00092     *change( ) *= *w.look(); 
00093     return *this;
00094   }
00096   inline Word operator * ( const Word& w ) const { 
00097     Word result( *this );
00098     result *= w;
00099     return result;
00100   }
00101   
00102   
00104   Word& operator ^= ( const Word& conjugator ) {
00105     *change( ) ^= *conjugator.look(); 
00106     return *this;
00107   }
00108   Word  operator ^  ( const Word& conjugator ) const {
00109     Word result( *this );
00110     result ^= conjugator;
00111     return result;
00112   }
00113 
00114 
00116   Word& operator ^= ( int power ) {
00117     *change( ) ^= power; 
00118     return *this;
00119   }
00120   Word  operator ^  ( int power ) const {
00121     Word result( *this );
00122     result ^= power;
00123     return result;
00124   }
00125   
00126 
00128   inline Word operator - ( ) const { 
00129     Word result;
00130     (*result.change( )) = look( )->inverse( );
00131     return result;
00132   }
00133 
00134 
00136   //                                                     //
00137   //  Accessors                                          //
00138   //                                                     //
00140         
00141 public:
00142   
00143   const_iterator begin( ) const { return const_iterator(*this); }
00144   const_iterator end  ( ) const { return const_iterator(*this,false); }
00145   iterator       begin( )       { return iterator(*this); }
00146   iterator       end  ( )       { return iterator(*this,false); }
00147   
00149   Word freelyReduce( ) { return freelyReduce( begin() , end( ) ); }
00151   Word freelyReduce( iterator B , iterator E );
00152   // freely reduces a segment of a word specified by [beg,end]. 
00153   // Most of the operations produce freely reduced words,
00154   // except operations insert, remove. The function takes linear time to performs
00155   // which is not efficient. So, either try to avoid uses of functions insert and remove
00156   // or try to bound the changes in variables beg and end
00157   
00159   static Word randomWord( int n , int wLen );
00161   static Word randomWord( int n , int wLenMin, int wLenMax );
00162 
00164   inline const list< int >& getList( ) const { return look( )->getList( ); }
00166   inline list< int >& getList( ) { return change( )->getList( ); }
00167   
00169   inline int length( ) const { return look( )->length( ); }
00170 
00172   inline Word& push_back ( int gen ) { change()->push_back ( gen ); return *this; }
00174   inline Word& push_front( int gen ) { change()->push_front( gen ); return *this; }
00176   Word& push_back ( const Word& w );
00178   Word& push_front( const Word& w );
00179 
00181   void pop_back ( ) { change()->pop_back ( ); }
00183   void pop_front( ) { change()->pop_front( ); }
00184 
00185 
00187   int getPower( Word& base ) const { return look( )->getPower( *base.change( ) ); }
00188   
00190   bool doesContain( const int& gen ) const { return look( )->doesContain( gen ); }
00191   
00193   inline void cyclicLeftShift( )  { change( )->cyclicLeftShift(  ); }
00195   inline void cyclicRightShift( ) { change( )->cyclicRightShift( ); }
00196   
00198   inline Word cyclicallyReduce( ) const {
00199     Word result( *this );
00200     result.change( ) -> cyclicallyReduce( );
00201     return result;
00202   }
00203   
00205   inline void cyclicallyReduceWord( ) { change( ) -> cyclicallyReduce( ); }
00206 
00208   inline Word cyclicallyReduce( Word& conjugator ) const {
00209     Word result( *this );
00210     result.change( ) -> cyclicallyReduce( *conjugator.change( ) );
00211     return result;
00212   }
00214   inline void cyclicallyReduceWord( Word& conjugator ) { 
00215     change( ) -> cyclicallyReduce( *conjugator.change( ) ); 
00216   }
00217 
00219   inline Word inverse( ) const {
00220     Word result;
00221     (*result.change( )) = look( )->inverse( );
00222     return result;
00223   }
00224 
00226 
00227   inline Word cyclicallyPermute( int n ) const {
00228     Word result( *this );
00229     result.change( ) -> cyclicallyPermute( n );
00230     return result;
00231   }
00233   inline Word& _cyclicallyPermute( int n ) {
00234     change( ) -> cyclicallyPermute( n );
00235     return *this;
00236   }
00237 
00239   inline Word initialSegment( int len ) const {
00240     Word result( *this );
00241     result.change( ) -> initialSegment( len );
00242     return result;              
00243   }
00244 
00246   inline Word terminalSegment( int len ) const {
00247     Word result( *this );
00248     result.change( ) -> terminalSegment( len );
00249     return result;                      
00250   }
00251 
00252   // Get a segment of the word defined by ???
00253   inline Word segment( int from , int to ) const {
00254     Word result( *this );
00255     result.change( ) -> segment( from , to );
00256     return result;      
00257   }
00258   
00259   inline int exponentSum( const int& gen ) const {
00260     return look( )->exponentSum( gen );
00261   }
00262   
00263   int isIn( const int& gen ) const {
00264     return look( )->isIn( gen );
00265   }
00266   
00267   Word power( int t ) const;
00268   
00269 
00271   template< class ConstIntIterator > 
00272   void insert( int pos , ConstIntIterator B , ConstIntIterator E );
00273 
00275   void insert( int pos , int g );
00276 
00278   template< class ConstIntIterator > 
00279   void insert( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00281   void insert( WordIterator it , int g );
00282 
00284   void replace( WordIterator it , const Generator& g );
00285 
00287   void replace( int pos , const Generator& g );
00288 
00290   template< class ConstIntIterator > 
00291     void replace( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00292 
00294 
00297   Word replaceGenerators( const vector<Word>& images )const;
00298 
00299 
00301 
00303   Word minimalEquivalentForm( const set< int >& permutableGenerators , bool inverses , bool cyclicPermutations ) const;
00304 
00305 
00307   //                                                     //
00308   //  Internal functions                                 //
00309   //                                                     //
00311 
00312  private:
00313 
00314          
00316   //                                                     //
00317   //  I/O                                                //
00318   //                                                     //
00320 
00321   
00322   friend ostream& operator << ( ostream& os , const Word& w ) {
00323     InfiniteAlphabet::defaultAlphabet.printWord( os, w );
00324     return os;
00325     //return w.look( )->printOn( os );
00326   }
00327   
00328   friend istream& operator >> ( istream& is ,  Word& w ) {
00329     w = InfiniteAlphabet::defaultAlphabet.readWord( is );
00330     return is;
00331     //return w.look( )->printOn( os );
00332   }
00333 
00334   ostream& printOn ( ostream& os ) const {
00335     InfiniteAlphabet::defaultAlphabet.printWord( os, *this );
00336     return os;
00337     //return look( )->printOn( os );
00338   }
00339   
00340   /*
00341     friend ostream& operator << ( ostream& os , const Word& w ) {
00342     os << *w.look( );
00343     return os;
00344     }
00345   */
00346   
00347 
00348 
00350   //                                                     //
00351   //  Data members                                       //
00352   //                                                     //
00354 
00355   private:
00356                 
00357 };
00358 
00359 
00360 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on Mon Sep 26 18:43:45 2011 for CRyptography And Groups (CRAG) by  doxygen 1.6.1