Word.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexander Ushakov
// Contents: Definition of class Word
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//

#ifndef _Word_H_
#define _Word_H_



#include "ObjectOf.h"
#include "Word.h"
#include "WordRep.h"
#include "WordIterator.h"
#include <string>
#include "Alphabet.h"
// #include <strstream>

#include <set>
using namespace std;


//---------------------------------------------------------------------------//
//---------------------------------- Word -----------------------------------//
//---------------------------------------------------------------------------//


class Word : public ObjectOf< WordRep >
{

 public:
  typedef ConstWordIterator const_iterator;
  typedef WordIterator iterator;
  
  //                                                     //
  //  Constructors                                       //
  //                                                     //

 public:

  typedef pair< int , int > PII;

  Word( ) : ObjectOf< WordRep >( new WordRep() ) { }
  Word( const vector< int >& gens ) : ObjectOf< WordRep >( new WordRep( gens ) ) { }
  Word( const list< int >& gens ) : ObjectOf< WordRep >( new WordRep( gens ) ) { }
  Word( int g ) : ObjectOf< WordRep >( new WordRep( g ) ) { }
    
  template< class IntIterator > 
    Word( const IntIterator& B , const IntIterator& E ) : ObjectOf< WordRep >( new WordRep( B , E ) ) { }

  // copy constructor supplied by compiler
  // destructor supplied by compiler
  
 
  //                                                     //
  //  Operators                                          //
  //                                                     //
public:


  bool operator < ( const Word& wr ) const { return (*look() < *wr.look( ) ); }
  bool operator > ( const Word& wr ) const { return (*look() > *wr.look( ) ); }
  bool operator == ( const Word& wr ) const { return (*look() == *wr.look( ) ); }
  bool operator != ( const Word& wr ) const { return !(*look() == *wr.look( ) ); }
  
  inline Word& operator *= ( const Word& w ) { 
    *change( ) *= *w.look(); 
    return *this;
  }
  inline Word operator * ( const Word& w ) const { 
    Word result( *this );
    result *= w;
    return result;
  }
  
  
  Word& operator ^= ( const Word& conjugator ) {
    *change( ) ^= *conjugator.look(); 
    return *this;
  }
  Word  operator ^  ( const Word& conjugator ) const {
    Word result( *this );
    result ^= conjugator;
    return result;
  }


  Word& operator ^= ( int power ) {
    *change( ) ^= power; 
    return *this;
  }
  Word  operator ^  ( int power ) const {
    Word result( *this );
    result ^= power;
    return result;
  }
  

  inline Word operator - ( ) const { 
    Word result;
    (*result.change( )) = look( )->inverse( );
    return result;
  }


  //                                                     //
  //  Accessors                                          //
  //                                                     //
        
public:
  
  const_iterator begin( ) const { return const_iterator(*this); }
  const_iterator end  ( ) const { return const_iterator(*this,false); }
  iterator       begin( )       { return iterator(*this); }
  iterator       end  ( )       { return iterator(*this,false); }
  
  Word freelyReduce( ) { return freelyReduce( begin() , end( ) ); }
  Word freelyReduce( iterator B , iterator E );
  // freely reduces a segment of a word specified by [beg,end]. 
  // Most of the operations produce freely reduced words,
  // except operations insert, remove. The function takes linear time to performs
  // which is not efficient. So, either try to avoid uses of functions insert and remove
  // or try to bound the changes in variables beg and end
  
  static Word randomWord( int n , int wLen );
  static Word randomWord( int n , int wLenMin, int wLenMax );

  inline const list< int >& getList( ) const { return look( )->getList( ); }
  inline list< int >& getList( ) { return change( )->getList( ); }
  
  inline int length( ) const { return look( )->length( ); }

  inline Word& push_back ( int gen ) { change()->push_back ( gen ); return *this; }
  inline Word& push_front( int gen ) { change()->push_front( gen ); return *this; }
  Word& push_back ( const Word& w );
  Word& push_front( const Word& w );

  void pop_back ( ) { change()->pop_back ( ); }
  void pop_front( ) { change()->pop_front( ); }


  int getPower( Word& base ) const { return look( )->getPower( *base.change( ) ); }
  
  bool doesContain( const int& gen ) const { return look( )->doesContain( gen ); }
  
  inline void cyclicLeftShift( )  { change( )->cyclicLeftShift(  ); }
  inline void cyclicRightShift( ) { change( )->cyclicRightShift( ); }
  
  inline Word cyclicallyReduce( ) const {
    Word result( *this );
    result.change( ) -> cyclicallyReduce( );
    return result;
  }
  
  inline void cyclicallyReduceWord( ) { change( ) -> cyclicallyReduce( ); }

  inline Word cyclicallyReduce( Word& conjugator ) const {
    Word result( *this );
    result.change( ) -> cyclicallyReduce( *conjugator.change( ) );
    return result;
  }
  inline void cyclicallyReduceWord( Word& conjugator ) { 
    change( ) -> cyclicallyReduce( *conjugator.change( ) ); 
  }

  inline Word inverse( ) const {
    Word result;
    (*result.change( )) = look( )->inverse( );
    return result;
  }


  inline Word cyclicallyPermute( int n ) const {
    Word result( *this );
    result.change( ) -> cyclicallyPermute( n );
    return result;
  }
  inline Word& _cyclicallyPermute( int n ) {
    change( ) -> cyclicallyPermute( n );
    return *this;
  }

  inline Word initialSegment( int len ) const {
    Word result( *this );
    result.change( ) -> initialSegment( len );
    return result;              
  }

  inline Word terminalSegment( int len ) const {
    Word result( *this );
    result.change( ) -> terminalSegment( len );
    return result;                      
  }

  // Get a segment of the word defined by ???
  inline Word segment( int from , int to ) const {
    Word result( *this );
    result.change( ) -> segment( from , to );
    return result;      
  }
  
  inline int exponentSum( const int& gen ) const {
    return look( )->exponentSum( gen );
  }
  
  int isIn( const int& gen ) const {
    return look( )->isIn( gen );
  }
  
  Word power( int t ) const;
  

  template< class ConstIntIterator > 
  void insert( int pos , ConstIntIterator B , ConstIntIterator E );

  void insert( int pos , int g );

  template< class ConstIntIterator > 
  void insert( WordIterator it , ConstIntIterator B , ConstIntIterator E );
  void insert( WordIterator it , int g );

  void replace( WordIterator it , const Generator& g );

  void replace( int pos , const Generator& g );

  template< class ConstIntIterator > 
    void replace( WordIterator it , ConstIntIterator B , ConstIntIterator E );


  Word replaceGenerators( const vector<Word>& images )const;



  Word minimalEquivalentForm( const set< int >& permutableGenerators , bool inverses , bool cyclicPermutations ) const;


  //                                                     //
  //  Internal functions                                 //
  //                                                     //

 private:

         
  //                                                     //
  //  I/O                                                //
  //                                                     //

  
  friend ostream& operator << ( ostream& os , const Word& w ) {
    InfiniteAlphabet::defaultAlphabet.printWord( os, w );
    return os;
    //return w.look( )->printOn( os );
  }
  
  friend istream& operator >> ( istream& is ,  Word& w ) {
    w = InfiniteAlphabet::defaultAlphabet.readWord( is );
    return is;
    //return w.look( )->printOn( os );
  }

  ostream& printOn ( ostream& os ) const {
    InfiniteAlphabet::defaultAlphabet.printWord( os, *this );
    return os;
    //return look( )->printOn( os );
  }
  
  /*
    friend ostream& operator << ( ostream& os , const Word& w ) {
    os << *w.look( );
    return os;
    }
  */
  


  //                                                     //
  //  Data members                                       //
  //                                                     //

  private:
                
};


#endif