WordRep.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of class WordRep
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _WordRep_H_
00010 #define _WordRep_H_
00011 
00012 
00013 
00014 #include "RefCounter.h"
00015 
00016 #include "vector"
00017 #include "list"
00018 #include "iostream"
00019 using namespace std;
00020 
00021 class WordIterator;
00022 
00023 typedef int Generator;
00024 
00025 //---------------------------------------------------------------------------//
00026 //-------------------------------- WordRep ----------------------------------//
00027 //---------------------------------------------------------------------------//
00028 
00029 
00030 class WordRep : public RefCounter
00031 {
00032   friend class Word;
00033   typedef pair< int , int > PII;
00034 
00036   //                                                     //
00037   //  Constructors                                       //
00038   //                                                     //
00040 
00041 private:
00042 
00043   WordRep( );
00044   WordRep( const WordRep& wr );
00045   WordRep( const list< int >& gens );
00046   WordRep( const vector< int >& gens );
00047         // special constructors, here we assume that -x is the inverse of x
00048 
00049   template< class IntIterator > WordRep( const IntIterator& B , const IntIterator& E ) {
00050     for( IntIterator C=B ; C!=E ; ++C )
00051       push_back( *C );
00052   }
00053 
00054 
00055   WordRep( int g );
00056 
00057   WordRep operator=( const WordRep wr );
00058 
00059 public:
00060 
00061 
00063   //                                                     //
00064   //  Operators                                          //
00065   //                                                     //
00067 private:
00068 
00069   WordRep& operator *= ( const WordRep& w );
00070   bool     operator <  ( const WordRep& wr ) const;
00071   bool     operator >  ( const WordRep& wr ) const;
00072   bool     operator == ( const WordRep& wr ) const;
00073   
00074   
00076   WordRep& operator ^= ( const WordRep& conjugator );
00077   WordRep  operator ^  ( const WordRep& conjugator ) const {
00078     WordRep result( *this );
00079     result ^= conjugator;
00080     return result;
00081   }
00082 
00083 
00085   WordRep& operator ^= ( int power );
00086   WordRep  operator ^  ( int power ) const {
00087     WordRep result( *this );
00088     result ^= power;
00089     return result;
00090   }
00091   
00092   
00093   inline WordRep  operator * ( const WordRep& w ) const {
00094     WordRep result( *this );
00095     result *= w;
00096     return result;
00097   }
00098   
00099   
00101   //                                                     //
00102   //  Accessors:                                         //
00103   //                                                     //
00105 
00106 public:
00107 
00108   WordRep* clone( ) const { return new WordRep( *this ); }
00109 
00110   const list< int >& getList( ) const { return theElements; }
00111   list< int >& getList( ) { return theElements; }
00112 
00113         
00114 private:
00115 
00116   bool doesContain( int gen ) const;
00117 
00118   inline int length( ) const { return theElements.size( ); }
00119 
00120   int exponentSum( int gen ) const;
00121   int isIn( int gen ) const;
00122 
00123   int getPower( WordRep& base ) const;
00124 
00125 
00127   //                                                     //
00128   //  Manipulators:                                      //
00129   //                                                     //
00131         
00132 private:
00133 
00134   WordRep inverse( ) const;
00135   
00136   
00138   void clear( ) { theElements.clear( ); }
00139   
00140   
00141   void freelyReduce( WordIterator beg , WordIterator end );
00142   void cyclicallyReduce( );
00143   void cyclicallyReduce( WordRep& conjugator );
00144 
00145   void cyclicLeftShift( );
00146   // the leftmost symbol goes to the rightmost position
00147   void cyclicRightShift( );
00148   // the rightmost symbol goes to the leftmost position
00149 
00150   void cyclicallyPermute( int n );
00151   // n>0 => left-shift permute
00152   // n<0 => rigth-shift permute
00153 
00154   void segment( int from , int to );
00155   // cut [from, to) part of the word
00156   // whole word is [0,length) part of itself
00157   void  initialSegment( int to   );
00158   void terminalSegment( int from );
00159 
00160   template< class ConstIntIterator > 
00161     void insert( int pos , ConstIntIterator B , ConstIntIterator E );
00162   template< class ConstIntIterator > 
00163     void insert( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00164 
00165   void insert( int pos , int g );
00166   void insert( WordIterator it , int g );
00167   
00168   void replace( WordIterator it , const Generator& g );
00169   void replace( int pos , const Generator& g );
00170 
00171   template< class ConstIntIterator > 
00172     void replace( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00173 
00175   //                                                     //
00176   //  I/O:                                               //
00177   //                                                     //
00179 
00180 public:
00181 
00182   // friend ostream& operator << ( ostream& os , const WordRep& wr ) {
00183   ostream& printOn( ostream& os ) const;
00184 
00185 
00187   //                                                     //
00188   //  Internal functions:                                //
00189   //                                                     //
00191 
00192 private:
00193 
00194   void push_back( int g );
00195   void push_front( int g );
00196   void pop_back( ) { theElements.pop_back( ); }
00197   void pop_front( ) { theElements.pop_front( ); }
00198 
00200   //                                                     //
00201   //  Data members                                       //
00202   //                                                     //
00204 
00205 private:
00206 
00207   list< int > theElements;
00208   // list of generators, negative integers represent inverses of positive integers
00209 };
00210 
00211 
00212 #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