WhiteheadAutoSet.h

Go to the documentation of this file.

#ifndef _WHITEHEAD_AUTO_SET_H_
#define _WHITEHEAD_AUTO_SET_H_


#include "Map.h"
#include "Word.h"

#include <ext/hash_set>
//#include <ext/stl_hash_fun.h>


// --------------------- structures to create a set of maps2
struct compMaps
{
  bool operator()(  Map m1,  Map m2 ) const
  {
    return (m1 == m2);
  }
};

namespace __gnu_cxx {
  struct map_hash
  {
    size_t operator()(Map m) const
    {
      int h = 0;
      const vector<Word>& is =  m.generatingImages( );
      for (int i=0;i<is.size();i++)
        h+=is[i].length();
      
      return h;
    }
  };
}

typedef __gnu_cxx::hash_set<Map, __gnu_cxx::map_hash, compMaps> SetOfMaps;


class AutoSet
{
 public:
  virtual const SetOfMaps& getSet() const = 0;
};


// -------------------------- NielsenAutoSet ---------------------------- //

class NielsenAutoSet : public AutoSet
{

public:

  
  //                                                                     //
  // Constructors:                                                       //
  //                                                                     //


  NielsenAutoSet( int  n );

  ~NielsenAutoSet( ) { }

  
  //                                                                     //
  // Accessors:                                                          //
  //                                                                     //


  const Map& getRandomAuto()const;


  const SetOfMaps& getSet() const { return theSet; }
 private:
  SetOfMaps theSet;
  int nGens;
};

// -------------------------- RestrictedWhiteheadAutoSet ---------------------------- //



class RestrictedWhiteheadAutoSet : public AutoSet
{

public:

  
  //                                                                     //
  // Constructors:                                                       //
  //                                                                     //

  

  RestrictedWhiteheadAutoSet( int n, bool use_conj = true );

  ~RestrictedWhiteheadAutoSet( ) { }

  
  //                                                                     //
  // Accessors:                                                          //
  //                                                                     //



  const Map& getRandomAuto()const;
  

  const SetOfMaps& getSet() const { return theSet; }
 private:
  SetOfMaps theSet;
  int nGens;
};

//
// -------------------------- WhiteheadAutoSetType2 ---------------------------- //
//


class WhiteheadAutoSetType2 : public AutoSet
{
  
 public:
  
  
  //                                                                     //
  // Constructors:                                                       //
  //                                                                     //


  WhiteheadAutoSetType2(  int n );

  ~WhiteheadAutoSetType2( );

  
  //                                                                     //
  // Accessors:                                                          //
  //                                                                     //



  const SetOfMaps& getSet() const { return theSet; }

  const Map& getRandomAuto() const;
  
private:

  Map getMap(   int n, const vector<int>& tCounts, Word a );
  void computeSet( int n );

  //                                                                     //
  // Data Members:                                                       //
  //                                                                     //

  const static int nElemAutos = 4;

  SetOfMaps theSet;
  int nGens;

};




class WhiteheadMinimization
{
 public:

  WhiteheadMinimization( int n ): wSet( n ) { } 


  bool isMinimal( const Word& w) const;
  
  

  Word findMinimal( const Word& w, ostream* out = NULL )const;


  const WhiteheadAutoSetType2& getSet() const { return wSet; }

 private:
  WhiteheadAutoSetType2 wSet;
};


// ---------------------------------------------------------------------------------------- //
// Check if a word is reducible by a given set
// ---------------------------------------------------------------------------------------- //

namespace WhiteheadAutoSet
{

  Word reduceBy( const Word& w, const SetOfMaps& theSet );
};

#endif