
// Homeo.H
// This is the entire object that we're manipulating

//	JR
//	10/20/95  Compiled.
//		  Tested Homeo() and Homeo(const BraidWord&).
//	10/25/95  Added	pullTight(),
//			collapseEdgesWithEmptyImage(),
//			collapseEdge(const DE&).		
//	10/26/95  Updated and included invariantForest.c.
//		  Added valence1.c.
//		  Worked on valence2.c. Added member preP().
//	3/5/96    Don't find implementation of preP()!
//	3/14/96	  Added growthRate(double tol,int maxits=0).
//		  Added diagnostic SIZE().
//	3/28/96	  Added generateG0().
//	4/5/96	  Wrote vertexInvariant.
//	4/8/96	  Wrote testLemma421_2, testLemma421_3.
//	4/16/96   Added theFingers, a list of marked points 
//		  on the graph which will be kept up to date by the
//		  functions that do modifications. (Only folding and
//		  subdividing functions do this at present.)
//	4/20/96	  Finished updated Step7.
//		  Added Boolean componentsOfPeripheryAreCircles().
//	5/23/96	  Added reducibleType2(). (reducible2.c)


#ifndef HOMEO_H
#define HOMEO_H

//#include <fstream.h>	
//#include <iostream.h>
#include <iostream>
using namespace std;

#include "Graph.H"
#include "Map.H"
#include "Equator.H"
#include "NameManager.H"
#include "Set.H"
#include "Boolean.H"
#include "LinList.H"
#include "CircList.H"
#include "Vertex.H"
#include "MapElement.H"
#include "DELList.H"
#include "Finger.H"
#include "FingerSet.H"
// Note: includes Constructor.H
//	      	  folding.H
//		  pullTight.C
//		  invariantForest.C
//		  subdivide.c
//       further down.

typedef int Boolean;
typedef LinList<int> BraidWord;

class Homeo
{
  // private:!!!!!!!!!!
public:
	NameManager theNameManager;		// (of the edges)
	Graph     theGraph;
	Map       theMap;
	Equator   theEquator;
	FingerSet theFingers;

   public:
	Homeo()
	: theNameManager(), theGraph(), theMap(), theEquator(), theFingers()
	{}
	Homeo(const BraidWord&);
	Homeo(istream&);
       ~Homeo(){}
	
	Boolean peripheral(const DE& e)
	{	return theNameManager.periphery().has(e.name());
	}

	Boolean collapseInvariantForest();  // invariantForest.C
	Set<Name> invariantForestNotIntersectingPInAnEdge() const;
	void pullTight();			// pullTight.C

	Boolean removeValenceOneVertices();	// valence1.C
	Boolean removeValenceTwoVertices();	// valence2.C
	Boolean removeAValenceTwoVertex();

	Set<Name> preP() const;	// Set of edges that eventually map into P.
				// In valence2.C

	Boolean collapseEdgesWithEmptyImage();	// pullTight.C
	void collapseEdge(DE);		// pullTight.C
	void directedCollapseEdge(DE e); // pullTight.C
	DE fold(DE e, DE f,int n);	// folding.H
        DE foldFirst(DE, DE);
	DE foldMany(DE, DE);
	DE foldI(DE , DE , const DELList );
	DE foldIII(DE , DE , const DELList );
	DE foldIV(DE , DE , const DELList );
	DE foldII(DE , DE , const DELList );
	void foldAvoidingMarkedPoint(DE d, DE e, Key key);

	DE subdivideOrigNear(DE e,int len);
	DE subdivideOrigFar(DE e,int len);
	void subdivideAsCloseInAsPossible(const DE& c);
	Boolean step6();

	void step7();
//	void step7part2( LinList<DE>& L );

	Boolean reducible() const;

	Boolean efficient() const
	{	return theMap.efficient();
	}

//	Boolean specializedAbsorbIntoP();

	Boolean mapIsContinuous() const;

	double growthRate(double tol,int maxIts=0) const;

	LinList< Set<Name> > generateG0() const;	// generateG0.c
	CircList<DE> generateAi(const Set<Name>& G0i);	// frontier.c
	Boolean absorbIntoP();				// newAbsorb.c
	void SIZE() const;
	DE splitPeripheralVertex( DE e, DE f );		// moreAbsorb.c
	Boolean vertexIsPeripheral(const Vertex& v) const; // moreAbsorb.c
	void collapseNonPeripheralG0(LinList< Set<Name> >& G0); // moreAbsorb.c
	LinList< LinList<DE> > splitPeripheralVertices
		(LinList< CircList< LinList<DE> > >& structuredLinkG0);  // moreAbsorb.c
	void collapsePeripheralG0( const LinList<DE>& toBeCollapsed );  // moreAbsorb.c
	void establishPeripheralHomeomorphism( const LinList<DE>& P );  // moreAbsorb.c
	Set<Name> makeG0Names( const LinList< Set<Name> >& G0 );	 // newAbsorb.c
	Set<Name> makeLinkG0Names( const LinList< CircList<DE> >& LinkG0 );	 // newAbsorb.c
	LinList< CircList<DE> > generateLinkG0(LinList< Set<Name> > G0); // newAbsorb.c
	CircList<DE> generateLinkG0i(const Set<Name>& G0i); 	// frontier.c
	Map generateDG1( const Set<Name>& G0Names,
			 const LinList< CircList<DE> >& LinkG0); // newAbsorb.c
	LinList< CircList< LinList<DE> > > makeStructuredLinkG0
			(       LinList< CircList<DE> >& LinkG0,
				const LinList< Set<Name> >& G0,
				const Set<Name>& G0names, 
				const Map& DG1); // newAbsorb.c
	CircList< LinList<DE> > partComponentOfLinkG0
				(int kmax,const CircList<DE>& LinkG0j,
				const Set<Name>& G0k,
				const Set<Name>& G0names,const Map& Dg1); // newAbsorb.c

	Boolean vertexInvariant(const Vertex& v) const;

	void phi1IsotopyOnLinkG0(const LinList< CircList<DE> >& LinkG0); // moreAbsorb.c

	void translate();	// translator.c

	Boolean testLemma421_2() const;	// newAbsorb.c
	Boolean testLemma421_3() const;	// newAbsorb.c

	void substituteInImages(DE e,const DELList& L);

	LinList<DE> subGate(DE d,DE e);

	int BH();	// Bestvina-Handel algorithm, in runBH.c

	Boolean componentsOfPeripheryAreCircles();

	Boolean reducibleType2();

  private:
	Boolean pullTight_type1();
	Boolean pullTight_type2();

   friend ostream& operator<< (ostream& out, const Homeo& h);

};

#include "Constructor.H"	// the constructor from BraidWord

ostream& operator<< (ostream& out, const Homeo& h)
{
	out << "Edges: " << h.theNameManager.edges() << endl;
	out << "Periphery: " << h.theNameManager.periphery() << endl;
	out << "Punctures: " << h.theNameManager.punctures() << endl;
	out << "Graph: " << h.theGraph << endl;
	out << "Map: " << h.theMap << endl;
	out << "Equator: " << h.theEquator << endl;
	return out;
}

void nextline(istream& in)	//**********
{
   	int c;
   	while( (c=in.get()), (c != '\n' && c!=EOF));
}

/**************************** old version
Homeo::Homeo(istream& in)	
{

	// make NameManager
	Set<Name> s;
	int n;
	in >> n; nextline(in);
//	cout << n << " edges : " ;
	int edgename;
	while(n--) { in >> edgename;
//		     cout << edgename << ", ";
		     s.add(edgename);
		   }
	nextline(in);
//	cout << endl << s;
	theNameManager.edgs=s;

	Set<Name> p;
	in >> n;  nextline(in);
//	cout << n << " peripheral edges : ";
	while(n--) { in >> edgename;
		     p.add(edgename);
		   }
	nextline(in);
//	cout << p;
	theNameManager.perip=p;

	Set<Name> pu;
	in >> n;  nextline(in);
//	cout << n << " punctures : ";
	while(n--) { in >> edgename;
		     pu.add(edgename);
		   }
	nextline(in);
//	cout << pu;
	theNameManager.puncs=pu;

	// make Graph
	int nv;
	int e;
	in >> nv; nextline(in);
//	cout << nv << " vertices : " << endl;	
	while(nv--)
	{
		Vertex v;
		int ninv;
		in >> ninv; nextline(in);
//		cout << ninv << " edges : " ;

		while(ninv--)
		{
		 	in >> e;
			if(e>0) v.pushb(DE(Name(e),0));
			else 	v.pushb(DE(Name(-e),1));
		}
		nextline(in);
//		cout << v << endl;
		theGraph.add(v);

	}	

	// make Equator
	int ne;
	Equator eqtr;
	in >> ne; nextline(in);
//	cout << ne << " edge-crossings : " << endl;	
	while(ne--)
	{
	  in >> e;
		if(e>0) eqtr.append(DE(Name(e),0));
		else 	eqtr.append(DE(Name(-e),1));
	}
	nextline(in);
//	cout << eqtr << endl;
	theEquator = eqtr;

	// make Map
	Map M;
	int nme;
	in >> nme; nextline(in);
//	cout << nme << " map elements :" << endl;

	while(nme--)
	{
		in >> e; nextline(in);
		MapElement me;
		if(e>0)  me.source()=DE(Name(e),0);
		else 	 me.source()=DE(Name(-e),1);

		int il;
		in >> il; nextline(in);
		while(il--)
		{
			in >> e;
			if(e>0) me.image().append(DE(Name(e),0));
			else 	me.image().append(DE(Name(-e),1));
		}
		nextline(in);
		M.add(me);
	}
//	cout << M << endl;
	theMap=M;
}
************************************/

void Homeo::SIZE() const	// diagnostic measure of the size of the thing
{
	int itot=0;
	SetBrowser<MapElement> i(theMap);
	for(i.init();i.ok();i.advance())
	{
		int j=i.current().image().length();
		itot += j;
	}
	cout << "  NUMBER OF EDGES IS  " << theNameManager.edges().cardinality();
	cout << ", TOTAL IMAGE LENGTH IS  " << itot << endl;
}

Boolean Homeo::vertexInvariant(const Vertex& v) const
{
		// Get any edge in v.
		// See if its image originates in v.

	assert(v.length()>0);
	DE e=v.ahead();
	DE ge=theMap.derivative(e);
	if( theGraph.originOf(ge) == v ) return 1;
	return 0;
}

void Homeo::substituteInImages(DE e,const DELList& LL)
{
	DELList L(LL);
				// Update fingers on fingered edges.
	int lenL=L.length();
	LinListIterator<Finger> i(theFingers.fingers());
	for(i.init();i.ok();++i)
	{
		DE efngr=i.ahead().e();
		int nfngr=i.ahead().n();
		DELListBrowser j(theMap.imageOf(efngr));
		int jj;
		for(j.init(),jj=0;j.ok();++j,++jj)
		{
			if(nfngr<=jj) break;

			if( j.ahead()==e || j.ahead()==e.bar() )
			{
				i.ahead().n()+=(lenL-1);
			}
		}

	}	

	SetIterator<MapElement> itr(theMap);
  	for(itr.init();itr.ok();itr.advance())
  	{    
	    	DELList& im_temp=itr.current().image();
    		im_temp.substitute(e,L);
 	}
}


Boolean Homeo::componentsOfPeripheryAreCircles()
{
	// The implementation requires that the components of
	// the peripheral subgraph be circles.

	// Check by testing that each peripheral vertex has
	// precisely two peripheral edges in its link.

	Set<Name> P=theNameManager.periphery();

	SetBrowser<Vertex> iv(theGraph);
	for(iv.init();iv.ok();iv.advance())
	{
		CircListBrowser<DE> ie(iv.current());
		int pcount=0;
		for(ie.init();ie.ok();++ie)
		{
			if(P.has(ie.ahead().name())) pcount++;
		}
		if( pcount!=0 && pcount!=2 )
		{
cout << "There is a component of P that is not a circle." << endl;
			return 0;
		}
	}
	return 1;
}

#include "runBH.c"

#include "translator.c"
#include "input.c"
#include "moreAbsorb.c"
#include "newAbsorb.c"


#include "reducible2.c"	
#include "folding.H"		
#include "pullTight.C"		
#include "invariantForest.C"	
#include "valence1.C"		
#include "valence2.C"		
#include "subdivide.c"		
#include "Step6.C"		
#include "Step7.c"		
				
				
//#include "specializedAbsorbIntoP.c"		
#include "reducible.c"		
#include "mapIsContinuous.c"
#include "generateG0.c"
#include "frontier.c"

#endif

