BKLLeftNormalForm.h

Go to the documentation of this file.

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

#ifndef _BKLLeftNormalForm_h_
#define _BKLLeftNormalForm_h_

#include "tuples.h"
#include "Permutation.h"

// #include "vector"
#include "list"
using namespace std ;

class BraidGroup;
class Word;


//---------------------------------------------------------------------------//
//--------------------------- BKLLeftNormalForm -----------------------------//
//---------------------------------------------------------------------------//



class BKLLeftNormalForm
{
  
 public:


  typedef triple< int , int , list< Permutation > > NF;
  
  //                                                     //
  //  Constructors:                                      //
  //                                                     //


  BKLLeftNormalForm( ) :
    theOmegaPower( 0 ) { }
    
    
  BKLLeftNormalForm( const BKLLeftNormalForm& bkl ) : 
    theRank( bkl.theRank ) ,
    theOmegaPower( bkl.theOmegaPower ) ,
    theDecomposition( bkl.theDecomposition ) { }
    
  BKLLeftNormalForm( int rank , int p , const list< Permutation >& d ) : 
    theRank( rank ) ,
    theOmegaPower( p ) ,
    theDecomposition( d ) { }
    
  BKLLeftNormalForm( const NF& bkl ) : 
    theRank( bkl.first ) ,
    theOmegaPower( bkl.second ) ,
    theDecomposition( bkl.third ) { }


  BKLLeftNormalForm( const BraidGroup& G , const Word& w );


  BKLLeftNormalForm& operator = ( const BKLLeftNormalForm& bkl ) {
    theRank = bkl.theRank;
    theOmegaPower = bkl.theOmegaPower;
    theDecomposition = bkl.theDecomposition;
  }
  
  
  BKLLeftNormalForm& operator = ( const NF& bkl ) {
    theRank = bkl.first;
    theOmegaPower = bkl.second;
    theDecomposition = bkl.third;
  }
  
  
  //                                                     //
  //  Operators:                                         //
  //                                                     //

 public:

  BKLLeftNormalForm& operator *= ( const BKLLeftNormalForm& bkl );
  BKLLeftNormalForm  operator *  ( const BKLLeftNormalForm& bkl ) const;
  BKLLeftNormalForm  operator -  ( ) const;

  bool operator ==( const BKLLeftNormalForm& bkl ) const;
  bool operator !=( const BKLLeftNormalForm& bkl ) const;
  bool operator < ( const BKLLeftNormalForm& bkl ) const;


  //                                                     //
  //  Accessor functions:                                //
  //                                                     //

 public:

  int getPower( ) const { return theOmegaPower; }
  const list< Permutation >& getDecomposition( ) const { return theDecomposition; }

  operator NF( ) const { return NF( theRank , theOmegaPower , theDecomposition ); }

  bool isTrivial( ) const { return theOmegaPower==0 && theDecomposition.size()==0; }

  static Permutation getTinyTwistPermutation( int theIndex ) {
    Permutation result( theIndex );
    for( int i=0 ; i<theIndex ; ++i )
      result[i] = (i+theIndex-1)%theIndex;
    return result;
  }


  Word getWord( ) const;
  
  
  pair< bool , Word > areConjugate( const BKLLeftNormalForm& bkl ) const;
  
  pair< BKLLeftNormalForm , BKLLeftNormalForm > cycle( ) const;
  pair< BKLLeftNormalForm , BKLLeftNormalForm > decycle( ) const;
  pair< BKLLeftNormalForm , BKLLeftNormalForm > findSSSRepresentative( ) const;


  //                                                     //
  //  Modifiers:                                         //
  //                                                     //

 public:

  inline void setPower( int p )
    { theOmegaPower = p; }

  inline void setDecomposition( const list< Permutation >& d )
    { theDecomposition = d; }
  
  //                                                     //
  //  Internal functions:                                //
  //                                                     //

 private:
  
  
  NF inverse( ) const;
  
  
  NF multiply( const BKLLeftNormalForm& bkl ) const;


  enum transformationResult { TWO_MULTIPLIERS , ONE_MULTIPLIER , NO_CHANGE };
  static transformationResult transform ( int theIndex , Permutation& p1 , Permutation& p2 );


  static set<Permutation> getSimpleConjugators( const NF& bkl );


  static set<Permutation> getSimpleSummitConjugators( const NF& bkl );

  
  static void adjustDecomposition( int rank ,
                                   int& power ,
                                   list<Permutation>& decomp );
  // this function transforms any (reasonable) decomposition
  // to a decomposition of a normal form 

  //                                                     //
  //  Data members:                                      //
  //                                                     //

 private:

  int theRank;

  int theOmegaPower;

  list< Permutation > theDecomposition;
  
};


ostream& operator << ( ostream& os, const BKLLeftNormalForm& bkl );

#endif