00001
00002
00003
00004
00005
00006
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
00027
00028
00029
00030 class WordRep : public RefCounter
00031 {
00032 friend class Word;
00033 typedef pair< int , int > PII;
00034
00036
00037
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
00048
00049 WordRep( int g );
00050
00051 WordRep operator=( const WordRep wr );
00052
00053 public:
00054
00055
00057
00058
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
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
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
00116 void cyclicRightShift( );
00117
00118
00119 void cyclicallyPermute( int n );
00120
00121
00122
00123 void segment( int from , int to );
00124
00125
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
00146
00148
00149 public:
00150
00151
00152 ostream& printOn( ostream& os ) const;
00153
00154
00156
00157
00158
00160
00161 private:
00162
00163 void push_back( int g );
00164 void push_front( int g );
00165
00167
00168
00169
00171
00172 private:
00173
00174 list< int > theElements;
00175
00176 };
00177
00178
00179 #endif