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   WordRep( int g );
00050 
00051   WordRep operator=( const WordRep wr );
00052 
00053 public:
00054 
00055 
00057   //                                                     //
00058   //  Operators                                          //
00059   //                                                     //
00061 private:
00062 
00063   WordRep& operator *= ( const WordRep& w );
00064   bool     operator <  ( const WordRep& wr ) const;
00065   bool     operator >  ( const WordRep& wr ) const;
00066   bool     operator == ( const WordRep& wr ) const;
00067 
00068   inline WordRep  operator * ( const WordRep& w ) const {
00069     WordRep result( *this );
00070     result *= w;
00071     return result;
00072   }
00073         
00075   //                                                     //
00076   //  Accessors:                                         //
00077   //                                                     //
00079 
00080 public:
00081 
00082   WordRep* clone( ) const { return new WordRep( *this ); }
00083 
00084   const list< int >& getList( ) const { return theElements; }
00085   list< int >& getList( ) { return theElements; }
00086 
00087         
00088 private:
00089 
00090   bool doesContain( int gen ) const;
00091 
00092   inline int length( ) const { return theElements.size( ); }
00093 
00094   int exponentSum( int gen ) const;
00095   int isIn( int gen ) const;
00096 
00097   int getPower( WordRep& base ) const;
00098 
00099 
00101         //                                        //
00102         //  Manipulators                          //
00103         //                                        //
00105         
00106 private:
00107 
00108   WordRep inverse( ) const;
00109   
00110   void freelyReduce( WordIterator beg , WordIterator end );
00111   void cyclicallyReduce( );
00112   void cyclicallyReduce( WordRep& conjugator );
00113 
00114   void cyclicLeftShift( );
00115   // the leftmost symbol goes to the rightmost position
00116   void cyclicRightShift( );
00117   // the rightmost symbol goes to the leftmost position
00118 
00119   void cyclicallyPermute( int n );
00120   // n>0 => left-shift permute
00121   // n<0 => rigth-shift permute
00122 
00123   void segment( int from , int to );
00124   // cut [from, to) part of the word
00125   // whole word is [0,length) part of itself
00126   void  initialSegment( int to   );
00127   void terminalSegment( int from );
00128 
00129   template< class ConstIntIterator > 
00130     void insert( int pos , ConstIntIterator B , ConstIntIterator E );
00131   template< class ConstIntIterator > 
00132     void insert( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00133 
00134   void insert( int pos , int g );
00135   void insert( WordIterator it , int g );
00136   
00137   void replace( WordIterator it , const Generator& g );
00138   void replace( int pos , const Generator& g );
00139 
00140   template< class ConstIntIterator > 
00141     void replace( WordIterator it , ConstIntIterator B , ConstIntIterator E );
00142 
00144   //                                                     //
00145   //  I/O:                                               //
00146   //                                                     //
00148 
00149 public:
00150 
00151   // friend ostream& operator << ( ostream& os , const WordRep& wr ) {
00152   ostream& printOn( ostream& os ) const;
00153 
00154 
00156   //                                                     //
00157   //  Internal functions:                                //
00158   //                                                     //
00160 
00161 private:
00162 
00163         void push_back( int g );
00164         void push_front( int g );
00165 
00167   //                                                     //
00168   //  Data members                                       //
00169   //                                                     //
00171 
00172 private:
00173 
00174   list< int > theElements;
00175         // list of generators, negative integers represent inverses of positive integers
00176 };
00177 
00178 
00179 #endif

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