PowerWord.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class PowerWord
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _Word_H_
00010 #define _Word_H_
00011 
00012 
00013 #include "ObjectOf.h"
00014 #include "PowerWord.h"
00015 #include "WordRep.h"
00016 #include "PowerWordIterator.h"
00017 #include <string>
00018 #include <strstream>
00019 using namespace std;
00020 
00021 
00022 //---------------------------------------------------------------------------//
00023 //-------------------------------- PowerWord --------------------------------//
00024 //---------------------------------------------------------------------------//
00025 
00026 
00027 class PowerWord : public ObjectOf< PowerWordRep >
00028 {
00029   // friend class WordIterator;
00030   
00031  public:
00032   typedef ConstPowerWordIterator const_iterator;
00033   typedef PowerWordIterator iterator;
00034   
00036   //                                                     //
00037   //  Constructors                                       //
00038   //                                                     //
00040 
00041 public:
00042 
00043   typedef pair< int , int > PII;
00044 
00045   PowerWord( ) : ObjectOf< PowerWordRep >( new WordRep() ) { }
00046   PowerWord( const vector< int >& gens ) : ObjectOf< PowerWordRep >( new PowerWordRep( gens ) ) { }
00047   PowerWord( const list< int >& gens ) : ObjectOf< PowerWordRep >( new PowerWordRep( gens ) ) { }
00048   PowerWord( const vector< PII >& gens ) : ObjectOf< PowerWordRep >( new PowerWordRep( gens ) ) { }
00049   PowerWord( const list< PII >& gens ) : ObjectOf< PowerWordRep >( new PowerWordRep( gens ) ) { }
00050  
00051   PowerWord( int g , int p=1 ) : ObjectOf< PowerWordRep >( new PowerWordRep( g , p ) ) { }
00052   // Cast constructor.
00053   
00054   // copy constructor supplied by compiler
00055   // destructor supplied by compiler
00056   
00057  
00059   //                                                     //
00060   //  Operators                                          //
00061   //                                                     //
00063 public:
00064 
00065   bool operator < ( const PowerWord& wr ) const {
00066     return (*look() < *wr.look( ) );
00067   }
00068   bool operator > ( const PowerWord& wr ) const {
00069     return (*look() > *wr.look( ) );
00070   }
00071   
00072   bool operator == ( const PowerWord& wr ) const {
00073     return (*look() == *wr.look( ) );
00074   }
00075   bool operator != ( const PowerWord& wr ) const {
00076     return !(*look() == *wr.look( ) );
00077   }
00078   
00079   inline PowerWord& operator *= ( const PowerWord& w ) { 
00080     *change( ) *= *w.look(); 
00081     return *this;
00082   }
00083   
00084   inline PowerWord operator * ( const PowerWord& w ) const { 
00085     PowerWord result( *this );
00086     result *= w;
00087     return result;
00088   }
00089 
00090   inline PowerWord operator - ( ) const { 
00091     PowerWord result;
00092     (*result.change( )) = look( )->inverse( );
00093     return result;
00094   }
00095 
00096 
00098   //                                                     //
00099   //  Accessors                                          //
00100   //                                                     //
00102         
00103  public:
00104   
00105   const_iterator begin( ) const { return const_iterator(*this); }
00106   const_iterator end  ( ) const { return const_iterator(*this,false); }
00107   iterator       begin( )       { return iterator(*this); }
00108   iterator       end  ( )       { return iterator(*this,false); }
00109   
00110   PowerWord& freelyReduce( ) { return freelyReduce( begin() , end( ) ); }
00111   PowerWord& freelyReduce( const_iterator beg , const_iterator end );
00112   // freely reduces a segment of a word specified by [beg,end]. 
00113   // Most of the operations produce freely reduced words,
00114   // except operations insert, remove. The function takes linear time to performs
00115   // which is not efficient. So, either try to avoid uses of functions insert and remove
00116   // or try to bound the changes in variables beg and end
00117   
00118   static PowerWord randomWord( int gens , int wLen );
00119   // generates a pseudo random reduced word 
00120   
00121   inline const list< PII >& getList( ) const { return look( )->getList( ); }
00122   // get a list representing the Word
00123   inline list< PII >& getList( ) { return change( )->getList( ); }
00124   // get a list representing the Word
00125   
00126   inline int length( ) const { return look( )->length( ); }
00127   // the length of the Word
00128 
00129   inline void push_back ( int gen , int power ) { change()->pushGeneratorBack ( gen , power ); }
00130   inline void push_front( int gen , int power ) { change()->pushGeneratorFront( gen , power ); }
00131   inline void push_back ( const pair< int , int >& g ) { change()->pushGeneratorBack ( g.first , g.second ); }
00132   inline void push_front( const pair< int , int >& g ) { change()->pushGeneratorFront( g.first , g.second ); }
00133 
00134   int getPower( PowerWord& base ) const { return look( )->getPower( *base.change( ) ); }
00135   // determines the power of the Word 
00136   // (not as an element of the corresponding Free Group)
00137 
00138   bool doesContain( const int& gen ) const {
00139     return look( )->doesContain( gen );
00140   }
00141   // Checks if the Word contains a generator
00142 
00143   inline void cyclicLeftShift( )  { change( )->cyclicLeftShift(  ); }
00144   // Shifts the word one position to the left
00145   inline void cyclicRightShift( ) { change( )->cyclicRightShift( ); }
00146   // Shifts the word one position to the right
00147 
00148   inline PowerWord cyclicallyReduce( ) const {
00149     Word result( *this );
00150     result.change( ) -> cyclicallyReduce( );
00151     return result;
00152   }
00153   // Returns the cyclically reduced Word
00154   
00155   inline void cyclicallyReduceWord( ) { change( ) -> cyclicallyReduce( ); }
00156   // Cyclically reduces the Word
00157 
00158   inline PowerWord cyclicallyReduce( PowerWord& conjugator ) const {
00159     PowerWord result( *this );
00160     result.change( ) -> cyclicallyReduce( *conjugator.change( ) );
00161     return result;
00162   }
00163   inline void cyclicallyReduceWord( PowerWord& conjugator ) { 
00164     change( ) -> cyclicallyReduce( *conjugator.change( ) ); 
00165   }
00166   
00167   inline PowerWord inverse( ) const {
00168     PowerWord result;
00169     (*result.change( )) = look( )->inverse( );
00170     return result;
00171   }
00172   
00173   inline PowerWord cyclicallyPermute( int n ) const {
00174     Word result( *this );
00175     result.change( ) -> cyclicallyPermute( n );
00176     return result;
00177   }
00178   // n>0 => left-shift permute
00179   // n<0 => rigth-shift permute
00180   
00181   inline PowerWord initialSegment( int len ) const {
00182     PowerWord result( *this );
00183     result.change( ) -> initialSegment( len );
00184     return result;              
00185   }
00186   
00187   inline PowerWord terminalSegment( int len ) const {
00188     PowerWord result( *this );
00189     result.change( ) -> terminalSegment( len );
00190     return result;                      
00191   }
00192   
00193   inline PowerWord segment( int from , int to ) const {
00194     Word result( *this );
00195     result.change( ) -> segment( from , to );
00196     return result;      
00197   }
00198   
00199   inline int exponentSum( const int& gen ) const {
00200     return look( )->exponentSum( gen );
00201   }
00202   
00203   int isIn( const int& gen ) const {
00204     return look( )->isIn( gen );
00205   }
00206   
00207   Word power( int t ) const;
00208 
00209   void insert( const PowerWord& wr , int pos ) {
00210     change( ) -> insert( *wr.look( ) , pos );
00211   }
00212 
00214   //                                                     //
00215   //  Internal functions                                 //
00216   //                                                     //
00218 
00219  private:
00220 
00221          
00223   //                                                     //
00224   //  I/O                                                //
00225   //                                                     //
00227 
00228   
00229   friend ostream& operator << ( ostream& os , const PowerWord& w ) {
00230     return w.look( )->printOn( os );
00231   }
00232   
00233   ostream& printOn ( ostream& os ) const {
00234     return look( )->printOn( os );
00235   }
00236   
00237   /*
00238     friend ostream& operator << ( ostream& os , const Word& w ) {
00239     os << *w.look( );
00240     return os;
00241     }
00242   */
00243   
00244 
00245 
00247   //                                                     //
00248   //  Data members                                       //
00249   //                                                     //
00251 
00252   private:
00253                 
00254 };
00255 
00256 
00257 #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