StraightLineProgramWord.h

Go to the documentation of this file.

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


#ifndef _StraightLineProgramWord_H_
#define _StraightLineProgramWord_H_


#include "map"
#include "list"
using namespace std;


#include "gmpxx.h"
typedef mpz_class LongInteger;
#include "Map.h"


//---------------------------------------------------------------------------//
//------------------------- StraightLineProgramWord -------------------------//
//---------------------------------------------------------------------------//



class StraightLineProgramWord
{
private:


  struct Production {
    
    Production( int t1=0, int t2=0 , LongInteger l=0 , int h=0 ) :
      theTerm1(t1), 
      theTerm2(t2),
      theLength(l),
      theHeight(h),
      reduced(false)
    { }
    
    int theTerm1;
    int theTerm2;
    LongInteger theLength;
    int theHeight;
    bool reduced;
  };



  struct Assertion {
    
    Assertion( bool b , int v1 , int v2 , LongInteger l ) : theBase1(b), theVertex1(v1), theVertex2(v2), theLength(l) { }
    
    bool operator < ( const Assertion& A ) const {
      if( theBase1<A.theBase1)
        return true;
      if( theBase1>A.theBase1)
        return false;
      if( theVertex1<A.theVertex1 )
        return true;
      if( theVertex1>A.theVertex1 )
        return false;
      if( theVertex2<A.theVertex2 )
        return true;
      if( theVertex2>A.theVertex2 )
        return false;
      if( theLength<A.theLength )
        return true;
      return false;
    }
    
    bool similar( const Assertion& A ) const {
      return (theBase1==A.theBase1 && theVertex1==A.theVertex1 && theVertex2==A.theVertex2);
    }
    
    friend ostream& operator << ( ostream& os , const Assertion& A ) {
      os << "(" << A.theBase1 << "," << A.theVertex1 << "," << A.theVertex2 << "," << A.theLength << ")";
      return os;
    }
    
    bool theBase1;
    
    int theVertex1;
    
    int theVertex2;
    
    LongInteger theLength;
  };
  
  
  //                                                     //
  //  Constructors                                       //
  //                                                     //
  
public:

  StraightLineProgramWord( ) : theRoot(0) , theTerminals(0) { }


  StraightLineProgramWord( int init , int gens );
  
  

  template< class ConstMapIterator > 
  StraightLineProgramWord( int init , ConstMapIterator B , ConstMapIterator E ) {
    int ai = abs( init );
    theRules[ai+1] = Production( init , 0 , 1 , 1 );
    theRoot = ai+1;
    theTerminals = ai;
    for( ; B!=E ; ++B )
      *this = applyMapping( *B );
  }
  

  //                                                     //
  //  Operators                                          //
  //                                                     //

public:
  
  StraightLineProgramWord& operator= ( const StraightLineProgramWord& SLP ) {
    theRoot      = SLP.theRoot;
    theRules     = SLP.theRules;
    theTerminals = SLP.theTerminals;
  }

  
  int operator[] ( LongInteger i ) const {
    return getGenerator( theRoot , i );
  }
  
  
  StraightLineProgramWord operator- ( ) const;
  
  
  StraightLineProgramWord operator * ( const StraightLineProgramWord& SLP ) const;

  
  //                                                     //
  //  Accessors                                          //
  //                                                     //
        
public:

  bool equal( int n1 , const StraightLineProgramWord& SLP , int n2 ) const;


  int terminalSegment( int n , LongInteger length ) {
    return truncateVertexLeft( n , length_rule(n)-length );
  }


  int initialSegment( int n , LongInteger length ) {
    return truncateVertexRight( n , length_rule(n)-length );
  }



  int truncateVertexLeft( int n , LongInteger length );
  
  

  int truncateVertexRight( int n , LongInteger length );
  
  
  LongInteger leftGCDLength( const StraightLineProgramWord& CS ) const {
    return leftGCDLength( theRoot , CS , CS.theRoot );
  }
  
  

  Word getWord( ) const { return getWord( theRoot ); }
  
  

  Word getWord( int N ) const;
  
  
  LongInteger length( ) const { return length_rule( theRoot ); }
  
  
  void reduce( ) { if( theRoot!=0 ) reduce_rule( theRoot ); }
  
  

  void simplify( );
  
  
  //                                                     //
  //  Internal functions                                 //
  //                                                     //

private:


  void order_vertices( int n , list< int >& order , set< int >& closure ) const;
  void order_vertices( int n , list< int >& order ) const {
    set< int > closure;
    order_vertices( n , order , closure );
  }

  
  LongInteger length_rule( int n ) const { 
    if( n==0 )
      return 0;
    if( abs( n )<=theTerminals )
      return 1;
    return (*theRules.find(abs(n))).second.theLength;
  }
  
  
  int height_rule( int n ) const { 
    if( n==0 )
      return 0;
    if( abs( n )<=theTerminals )
      return 0;
    return (*theRules.find(abs(n))).second.theHeight;
  }


  static void invertProductionPair( int& A , int& B );



  bool assertionType( const Assertion& A , const StraightLineProgramWord& SLP ) const;

  
  void extendTerminals( int nt );


  void reduce_rule( int n );
  

  LongInteger leftGCDLength( int n1 , const StraightLineProgramWord& CS , int n2 ) const;

  
  // Split an assertion.
  set< Assertion > splitAssertion( const Assertion& A , bool firstTerm , const StraightLineProgramWord& SLP ) const;
  
  
  void update_lengths( );
  void update_length( int n );
  
  void update_heights( );
  void update_height( int n );

  
  int getGenerator( int n , LongInteger pos ) const;
  
  
  LongInteger cancellationLength( int n1 , int n2 ) const;
  
  

  static pair< map< int , Production > , vector< int > > map_rules( const Map& M );



  StraightLineProgramWord applyMapping( const Map& M ) const;
  
  
  int max_rule_number( ) const;
  
  
  //                                                     //
  //  I/O                                                //
  //                                                     //

public:  

  friend ostream& operator << ( ostream& os , const StraightLineProgramWord& CS );

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

  private:


  int theRoot;
  
  
  int theTerminals;
  
  
  map< int , Production > theRules;
  
};


#endif