// Copyright (C) 1994 The New York Group Theory Cooperative
// See magnus/doc/COPYRIGHT for the full notice.

// Contents: Definition of the SubgroupGraphRep class.
//
// Principal Author: Roger Needham
//
// Status: in progress
//
// Revision History:
//
// * 05/97 Dmitry B. implemented IPC tools.
//
// Special Notes:
//
// * The edge table is just a flat array, rather than a vector of
//   vectors, to save memory overhead: since the ambient free group is
//   liable to have small rank, we don't want scads of small vectors on the
//   heap. The tradeoffs are that random-access lookup of target vertices
//   requires an integer multiplication, and expanding the table requires
//   copying the whole thing.
//   At least the multiplication could be optimized away by changing
//   consecutive vertex numbers to row offsets into the edge table.
//   The all-important ordering of vertices would be preserved.
//
// * For the sake of efficiency all functions of SubgroupGraphRep work
//   only with freely reduced words.
//
// Next implementation steps:
//
// * More arg checking on SAFETY?
// * Should generating set be given as a VectorOf?
// * addSubgroupGenerator method.


#ifndef _SUBGROUPGRAPHREP_H_
#define _SUBGROUPGRAPHREP_H_


#include "Set.h"
#include "Word.h"
#include "Vector.h"
#include "Generator.h"
#include "RefCounter.h"

// #define DEBUG_SubgroupGraph
// #define DEBUG_IDENTIFY

//@db: class SubgroupGraphRep : public RefCounter {
// RefCounter does not have clone(), therefore clone() is never
// defined as a virtual method which leads to crash in 
// any deriviation of SubgroupGraph.

class SubgroupGraphRep : public PureRep {

  friend class SubgroupGraphRepReader;

public:
  
  SubgroupGraphRep(int ambientRank, const SetOf<Word>& S);
  // Construct a subgroup graph from the rank of the ambient free group,
  // and the subgroup generators.

  SubgroupGraphRep(int ambientRank, const VectorOf<Word>& V);
  // Construct a subgroup graph from the rank of the ambient free group,
  // and the subgroup generators.

  SubgroupGraphRep(const SubgroupGraphRep&);
  // Copy constructor does deep copy.
  
  ~SubgroupGraphRep( );

  SubgroupGraphRep* clone( ) const { return new SubgroupGraphRep( *this ); }
  // Standard clone.

  int rank( ) const {
	 return numberOfEdges() - numberOfVertices + 1;
  }
  // Returns the rank of this subgroup as a free group.

  VectorOf<Word> normalizer( );
  // Returns the normalizer of this subgroup.

  VectorOf<Word> nielsenBasis( );
  // Returns a Nielsen basis for this subgroup as a free group.

  Word nielsenWord(int i);
  // Returns an i^th element of the Nielsen basis.

  Word inNielsenWords(const Word& w);
  // Returns the word `w' written in elements of the Nielsen basis.

  SubgroupGraphRep* join(const SubgroupGraphRep&) const;
  // Returns a SubgroupGraphRep* which represents the join of this
  // subgroup and the argument.

  SubgroupGraphRep* intersection(const SubgroupGraphRep& SGR) const;
  // Returns a SubgroupGraphRep* which represents the intersection
  // of this subgroup and the argument.

  Bool contains(const Word& w) const { return loopSearch(w,0); }
  // Returns TRUE iff this subgroup contains `w'.

  Bool contains(const SetOf<Word>& S) const;
  // Returns TRUE iff this subgroup contains the subgroup generated by `S'.

  Bool contains(const VectorOf<Word>& V) const;
  // Returns TRUE iff this subgroup contains the subgroup generated by `V'.

  Bool contains(SubgroupGraphRep& SGR) const;
  // Returns TRUE iff this subgroup contains the argument.

  Bool equalTo(const SetOf<Word>& S);
  // Returns TRUE iff this subgroup and the subgroup generated by `S' are equal.

  Bool equalTo(SubgroupGraphRep& SGR);
  // Returns TRUE iff this subgroup and the argument are equal.

  Bool conjugateInSubgroup(const Word& w, Word& conjugator) const;
  // Returns TRUE iff some conjugate of `w' is in the subgroup.
  // If TRUE, `conjugator' is set to the conjugator.

  Bool conjugateInSubgroup(const SetOf<Word>& S, Word& conjugator);
  // Returns TRUE iff some conjugate of the subgroup generated by `S' is
  // in the subgroup. If TRUE, `conjugator' is set to the conjugator.

  bool conjugateTo(const SetOf<Word>& S);
  // Returns true iff this subgroup and the argument are conjugate.

  long powerInSubgroup( const Word& aWord ) const;
  // returns 'the minimal power' or 0 if there are no powers of the
  // element `aWord' in H.

  int findIndex();
  // returns the index of the subgroup or 0 if infinite.

  VectorOf<Word> findWhiteheadBasis();
  // Finds the subgroup of the free group authomorphic to this with
  // smallest sum of lengths of generators.
  // Returns a vector of generators.

  Bool isAFreeFactor();
  // Returns TRUE iff this subgroup is a free factor.

  Bool generatesTheFreeGroup() const
  { 
    return (numberOfVertices==1)&&(rank()==valence/2);
  }

  Word rightSchreierRepresentative(const Word&);

  void MHallComplete();
  // Alters this graph in place so that it becomes a subgroup of
  // the ambient free group of finite index, with the original
  // subgroup a free factor.

  void joinConjugate(int generator);
  // Alters this graph in place so that it also contains the conjugate
  // by `generator' of every element it contained before.

  float completeness( ) const {
	 return ( 2 * numberOfEdges() ) / ( numberOfVertices * valence );
  }

  Bool isComplete( ) const {
	 return ( 2 * numberOfEdges() ) == ( numberOfVertices * valence );
  }

  long vertexCount( ) const { return numberOfVertices; }

  #ifdef DEBUG
    void debugPrint(ostream&) const;
    Bool consistentData( ) const;
    //friend int main( );
  #endif

  typedef long VertexType;
  // A signed integer type big enough to hold the number of vertices in a
  // graph. Used for both vertices and indices into vectors of vertices.

  static const VertexType baseVertex = 0;
  // The distinguished vertex, i.e. the only start and accept state for
  // the graph as a word acceptor.

  static const VertexType emptyTarget = -1;

  typedef int LabelType;
  // Any integer type big enough to hold twice the ambient rank.


  LabelType generatorToLabel(int g) const {
	 return ( g > 0 ? (g - 1) << 1 : (-g << 1) - 1 );
  }
  // Performs the mapping of Generator ordinals to labels:
  // . . . -3 -2 -1  1  2  3 . . .
  // . . .  5  3  1  0  2  4. . .
  // This is the inverse function of `labelToGenerator'.


  int labelToGenerator(LabelType label) const {
	 return ( label & 1 ? ( -1 - label ) >> 1 : ( label + 2 ) >> 1 );
  }
  // Performs the mapping of labels to Generator ordinals:
  // 0  1  2  3  4  5 . . .
  // 1 -1  2 -2  3 -3
  // This is the inverse function of `generatorToLabel'.


  LabelType inverseLabel(LabelType label) const {
	 return ( label & 1 ? label - 1 : label + 1 );
  }
  // Returns the label representing the inverse generator to the
  // generator represented by `label'.


  VertexType targetOfGenerator(VertexType source, int generator) const {
	 return table[ source * valence + generatorToLabel(generator) ];
  }
  // Returns the vertex gotten to from `source' vertex via `generator'.
  // -1 means there is no such edge.


  VertexType targetOfLabel(VertexType source, LabelType label) const {
	 return table[ source * valence + label ];
  }
  // Returns the vertex gotten to from `source' vertex via `label'.
  // -1 means there is no such edge.


  LabelType getValence( ) const {
    return valence;
  } 

  /////////////////////////////////////////////////////////////////////////
  //                                                                     //
  // IPC tools:                                                          //
  //                                                                     //
  /////////////////////////////////////////////////////////////////////////

  virtual void write( ostream& ostr ) const;
 
  virtual void read( istream& istr );

  virtual bool readPiece( istream& istr, const class Timer& timer );
  // To read a big amount of information piece by piece. Returns true
  // if the last is read, false otherwise.
 

//@dbprivate:
protected:

  // IPC private data:

  enum { STOP, TABLE, SUBTREE, BASIS_EDGES };
  int isReading;
  int tableSize, n;


  /////////////////////////////////////////////////////////////////////////
  //                                                                     //
  // Private members of the class:                                       //
  //                                                                     //
  /////////////////////////////////////////////////////////////////////////

  // A graph is comprised of vertices, (edge) labels, and
  // a set of ordered triples (source vertex, label, target vertex).
  //
  // Our labels are integers 0, 1, ..., valence - 1, which represent
  // group generators; we map Generator ordinals to labels in the
  // sequence 1, -1, 2, -2, ...
  //
  // Our vertices are integers numbered 0, 1, ..., numberOfVertices - 1.


  struct Edge {
    VertexType v;          // initial vertex
    LabelType  l;

    Edge& operator = ( const Edge& anEdge ) { 
         v = anEdge.v; l = anEdge.l; 
	 return *this;
    }
    Bool operator < ( const Edge& anEdge ) const {
         if ( v < anEdge.v ) return TRUE;
         if ( v > anEdge.v ) return FALSE;
         if ( l < anEdge.l ) return TRUE;
         return FALSE;
    }
    Bool operator > ( const Edge& anEdge ) const {
         if ( v > anEdge.v ) return TRUE;
	 if ( v < anEdge.v ) return FALSE;
	 if ( l > anEdge.l ) return TRUE;
	 return FALSE;
    }
    
    friend ostream& operator < ( ostream& ostr, const Edge& e )
    {
      ostr < e.v < e.l;
      return ostr;
    }
    
    friend istream& operator > ( istream& istr, Edge& e )
    {
      istr > e.v > e.l;
      return istr;
    }

  };
  
  // Data members:

  VertexType* table;
  // Holds a transition table, represented by a 2D array of
  // numberOfVertices rows and valence columns.
  // The entry in row i and column j is the target vertex of
  // source vertex i via label j.
  // This means that finding the target of a label from a source vertex
  // requires a multiplication.

  VertexType numberOfVertices;   // Actual number of vertices allocated in table
  VertexType spaceForVertices;   // Number of vertices table can hold
  LabelType  valence;            // Number of labels


  LabelType* maximalSubtree;
  Edge* basisEdges;
  // These are NULL after the constructor exits. They must be explicitly
  // initialized by a call to makeMaxlSubtree(). Do NOT forget to
  // reinitialize these if table changes.
  // 
  // maximalSubtree `contains' backpointers which define a maximal subtree
  // of the graph: if the maximal subtree contains the edge V1 -- L --> V2,
  // then maximalSubtree[V2] == L^-1 (so V1 can be gotten from table).
  // This is used to extract a Nielsen basis, and to find a Nielsen-Schreier
  // representative of a word in the ambient free group.
  // 
  // basisEdges `contains' those edges of the graph which are missing from
  // the maximal subtree. basisEdges is sorted ( lexicographical order on 
  // pairs (iVertex,label).
  //
  // This is used to extract a Nielsen basis, and to write a word in the
  // subgroup as a word in that Nielsen basis.
  //
  // There is still the problem of indexing basis edges, so that we know
  // which element of the Nielsen basis corresponds to which edge.

  
  // Private methods:


  SubgroupGraphRep(int whatValence, long howManyVertices);
  // Construct a SubgroupGraphRep with `table' initialized for
  //   numberOfVertices == 1,
  //   spaceForVertices == howManyVertices,
  //   valence == whatValence.


  void resize(long howManyVertices);
  // Data members `table', `valence' and `numberOfVertices' must have
  // correct values before calling this.
  // Resizes `table' to have exactly enough room for `howManyVertices',
  // copying any that are already there, initializes any new vertices
  // to have no edges, and sets values of `numberOfVertices' and
  // `spaceForVertices' if the size changes.


  void defineEdges(VertexType source, int generator, VertexType target) {
	 #if SAFETY > 1
	 if ( (source < 0) || (source >= numberOfVertices) ||
			(target < -1) || (target >= numberOfVertices) ||
			(generatorToLabel(generator) < 0) ||
			(generatorToLabel(generator) >= valence) )
		error("bad arg(s) to SubgroupGraphRep::defineEdges");
	 #endif

	 table[ source * valence + generatorToLabel(generator) ] = target;
	 table[ target * valence + generatorToLabel(-generator) ] = source;
  }
  // Makes `generator' take `source' vertex to `target' vertex, and
  // the inverse generator take `target' vertex to `source' vertex.


  VertexType defineEdges(VertexType source, int generator) {
	 #if SAFETY > 1
	 if ( numberOfVertices > spaceForVertices )
		error("table overflow in SubgroupGraphRep::defineEdges");
	 #endif
	 if ( numberOfVertices == spaceForVertices )
		resize(numberOfVertices + max(numberOfVertices / 5, 100)); //@rn experiment
	 ++numberOfVertices;
	 defineEdges(source, generator, numberOfVertices - 1);
	 return numberOfVertices - 1;
  }
  // This version defines a new (target) vertex before doing the work
  // of `defineEdges', and returns the new vertex.


  void defineEdge(VertexType source, LabelType label, VertexType target) {
	 table[ source * valence + label ] = target;
  }
  // Makes `label' take `source' vertex to `target' vertex.


  long numberOfEdges( ) const;
  // Returns the number of edge pairs in this graph; an edge labelled by
  // a generator and one by the inverse of that generator count as one.

  long valenceAt(VertexType v) const;
  // Returns the number of edges outcomming from `v'.
						

  void adjoinWord(const Word&, VertexType);
  // Adjoins the Word to this graph, which is the same as adding
  // the Word to the generating set of this subgroup.
  // Calls defineEdges to make new edges, which resizes `table'
  // if necessary, and may leave extra space.


  void addWordArc(const Word&, VertexType, VertexType, int, int);
  // Specialized version of adjoinWord.


  void addWordLoop(const Word&, VertexType, int, int);
  // Specialized version of adjoinWord.


  void identifyVertices(VertexType, VertexType);
  // Folds this graph as necessary so that the two vertices are the same,
  // then recovers any unneeded space.


  void reduceGraph(VertexType*);
  // See comments in function body. Recovers any unneeded space.


  SubgroupGraphRep* disjointUnion(const SubgroupGraphRep&) const;
  // Returns a SubgroupGraphRep* which is the literal graph-wise
  // disjoint union of the argument and this graph.

  Bool loopSearch(const Word& w, VertexType v) const;
  // Returns TRUE iff there is a cycle starting at `v' with label `w'.

  Word getLabel(VertexType v) const;
  // Returns the label of the path from the base vertex to `v' along the
  // maximal subtree.

  Word getInverseLabel(VertexType v) const;
  // Returns the label of the path from `v' to the base vertex along the
  // maximal subtree.

  int findBasisEdgeIndex(VertexType source,LabelType label);
  // Returns index of this edge in BasisEdges if passing it in positive
  // direction or -index if passing in negative. 1-based index.

  void makeMaxlSubtree( );
  // See the comments above for maximalSubtree and basisEdges.

  int distanceFromOrigin(VertexType) const;

};

#endif