// newAbsorb.c

//	JR
//	3/30/96 Wrote and tested the generation of LinkG0.
//		Wrote and compiled the generation of groupedLinkG0,
//		except the constant derivative case. NOT tested.
//	4/1/96  Continuing work.
//	4/4/96  Why don't we get redundancy in DG1 when an edge
//		and its reverse appear in LinkG0???
//		Because MapElement operator == compares only src.name().
//	4/12/96 Replaced iteratedDerivativesEventuallyTheSame with more
//		efficient sameGate.

Boolean Homeo::absorbIntoP()
{
	theFingers.markInvalid();	// Finger update not yet coded here.

	Boolean didSomething=0;

	LinList< Set<Name> > G0;

	G0=generateG0();
cout << "    G0 = " << G0 << endl;
	Set<Name>G0Names=makeG0Names(G0);

	Boolean lemma421_1Satisfied
		=(G0Names.cardinality()
 			==theNameManager.periphery().cardinality());
//cout << "lemma421_1Satisfied = " << lemma421_1Satisfied << endl;
	Boolean lemma421_2Satisfied=testLemma421_2();
//cout << "lemma421_2Satisfied = " << lemma421_2Satisfied << endl;

	Boolean lemma421_3Satisfied=testLemma421_3();
//cout << "lemma421_3Satisfied = " << lemma421_3Satisfied << endl;
	
	if( lemma421_1Satisfied 
	 && lemma421_2Satisfied  
	 && lemma421_3Satisfied ) 
	{
cout << "  Conclusions of Lemma 4.2.1 are satisfied." << endl;
		return 0;
	}

cout << "  Absorbing into P" << endl;

// For use with homeo6.dat:
/*	Set<Name> tmp;
	tmp.add( 6 );
	tmp.add( 102 );
	tmp.add( 101 );
	tmp.add( 8 );
	G0.append(tmp);
	tmp.clear();
	tmp.add( 103 );
	G0.append(tmp);
//	cout << "Imposed G0 = " << G0 << endl;
*/
	LinList< CircList<DE> > LinkG0=generateLinkG0(G0);
//cout << "    Lk(G0,G)=" << LinkG0 << endl;
	
	Set<Name> LinkG0Names=makeLinkG0Names(LinkG0);

	Map DG1=generateDG1(G0Names,LinkG0);

	LinList< CircList< LinList<DE> > > structuredLinkG0=
		makeStructuredLinkG0(LinkG0,G0,G0Names,DG1);
cout << "    Lk(G0,G) = " << structuredLinkG0 << endl;
	collapseNonPeripheralG0(G0);
//cout << " After collapseNonPeripheralG0(G0):" << endl << (*this) << endl;
	LinList<  LinList<DE> > NS=splitPeripheralVertices(structuredLinkG0);

	collapsePeripheralG0(NS[0]);
//cout << "    New periphery is " << NS[1] << endl;

	establishPeripheralHomeomorphism(NS[1]);

	phi1IsotopyOnLinkG0(LinkG0);

	return 1;  
}

Set<Name> Homeo::makeG0Names( const LinList< Set<Name> >& G0 )
{
// This doesn't really belong to Homeo. But without template member
// functions, it can't go where it should.

	Set<Name> G0Names;	// Merge of the components of G0.
	LinListBrowser< Set<Name> > ig(G0);
	for(ig.init();ig.ok();++ig)
	{
		G0Names+=ig.ahead();
	}
	return G0Names;
}

Set<Name> Homeo::makeLinkG0Names( const LinList< CircList<DE> >& LinkG0 )
{
// This doesn't really belong to Homeo. But without template member
// functions, it can't go where it should.

	Set<Name> LinkG0Names;	// Merge of the components of LinkG0.
	LinListBrowser< CircList<DE> > ig(LinkG0);
	for(ig.init();ig.ok();++ig)
	{
		CircListBrowser<DE> j(ig.ahead());
		for(j.init();j.ok();++j)
		{	
			LinkG0Names.add(j.ahead().name());
		}
	}
	return LinkG0Names;
}

LinList< CircList<DE> > Homeo::generateLinkG0(LinList< Set<Name> > G0)
{	
	LinList< CircList<DE> > LinkG0;
	LinListBrowser< Set<Name> > i(G0);
	for(i.init();i.ok();++i)
	{
		CircList<DE> LinkG0i;
		LinkG0.append(LinkG0i=generateLinkG0i(i.ahead()));
	}
//	cout << "LinkG0 = " << LinkG0 << endl;
	return LinkG0;
}

Map Homeo::generateDG1( const Set<Name>& G0Names,
			const LinList< CircList<DE> >& LinkG0)
{
	Map DG1;
	LinListBrowser<	CircList<DE> > j(LinkG0);
	for(j.init();j.ok();++j)
	{
		CircListBrowser<DE> i(j.ahead());
	
		for(i.init();i.ok();++i)
		{
			DE e(i.ahead());
			DELList DG1Ofe;
			DELListBrowser im(theMap.imageOf(e));
			Boolean wentOut=0;
			for(im.init();im.ok();++im)
			{
				if( !G0Names.has(im.ahead().name()) )
				{
					wentOut=1;
					DG1Ofe.append(im.ahead());
					break;
				}
			}
			assert(wentOut);

					// We put the G1 derivative
					// of the reverse in also,
					// in case both e and ebar
					// appear in LinkG0.

			DE ebar(i.ahead().bar());
			DELListBrowser in(theMap.imageOf(ebar));
			wentOut=0;
			for(in.init();in.ok();++in)
			{
				if( !G0Names.has(in.ahead().name()) )
				{
					wentOut=1;
					DG1Ofe.append(in.ahead().bar());			
					break;
				}
			}
			assert(wentOut);

			DG1.add( MapElement(e,DG1Ofe) );				

		}
	}

//	cout << "DG1=" << DG1 << endl;
	return DG1;
}

LinList< CircList< LinList<DE> > > Homeo::makeStructuredLinkG0
		(LinList< CircList<DE> >& LinkG0,
		const LinList< Set<Name> >& G0,
		const Set<Name>& G0Names, const Map& DG1)
{
	// Make more structured versions of LinkG0i
	// which will prefigure the new fibered structure.

	LinList< CircList< LinList<DE> > > groupedLinkG0;

	int sizeOfLinkG0=0;
	for(int ii=0;ii<LinkG0.length();ii++) sizeOfLinkG0+=LinkG0[ii].length();

	for(int k=0;k<LinkG0.length();k++)
	{
//cout << "k=" << k << endl;
		CircList< LinList<DE> > groupedLinkG0k;
		CircList<DE>& LinkG0k(LinkG0[k]);
//cout << groupedLinkG0k << endl;
		if( LinkG0k.length()==1 )	// easy case
		{
//cout << "LinkG0k.length()==1" << endl;
			LinList<DE> ltemp(LinkG0k.ahead());
			groupedLinkG0k.pushb(ltemp);
//cout << "Now " << groupedLinkG0k << endl;
//cout << "groupedLinkG0 now " << groupedLinkG0 << endl;
		}
		else
		{	// See if sufficiently high iterate of
			// DG1 is constant on LinkG0k.

			Boolean isConstant=1;

			CircListBrowser<DE> iai(LinkG0k);
			iai.init();
			assert(iai.ok());
			for(++iai;iai.ok();++iai)
			{
//cout << iai.behind() << " <- iai -> " << iai.ahead() << endl;
				if( !DG1.sameGate(iai.behind(),iai.ahead()))
				{
					isConstant=0;
					break;
				}
			}

			if(!isConstant)
			{
				iai.init();
				while(DG1.sameGate(iai.behind(),iai.ahead()))
					 --iai;
				DE d1=iai.ahead();
				LinkG0k.rotateToJustBeforeThe(d1);
				LinList<DE> tmp;
				for(iai.init(); iai.ok();++iai)
				{
					if(DG1.sameGate(d1,iai.ahead()))
					{	
						tmp.append(iai.ahead());						
					}
					else
					{
						groupedLinkG0k.pushb(tmp);
						tmp.clear();
						tmp.append(iai.ahead());
						d1=iai.ahead();
					}
				}
				if(tmp.length()!=0) groupedLinkG0k.pushb(tmp);
			}
			else
			{
				// All edges in LinkG0k eventually mapped together by DG1.
				// Must do test to see where to part it.

				groupedLinkG0k=partComponentOfLinkG0
					(sizeOfLinkG0,LinkG0k,G0[k],G0Names,DG1);
			}
		}
		groupedLinkG0.append(groupedLinkG0k);
	}
//cout << "Equivalence classes in LinkG0=" << groupedLinkG0 << endl;	
	return groupedLinkG0;

}

CircList< LinList<DE> > Homeo::partComponentOfLinkG0
  (int kmax,const CircList<DE>& LinkG0j,
            	const Set<Name>& G0k,
		const Set<Name>& G0Names,const Map& DG1)
{
					// This does the case where
					// there is one equivalence class
					// of edges in LinkG0j which has
					// size > 1.
					// See Bestvina-Handel p125.
	CircListBrowser<DE> i(LinkG0j);
					// Make a set of the names in LinkG0k.
	Set<Name> LinkG0jNames;
	for(i.init();i.ok();++i) LinkG0jNames.add(i.ahead().name());

					// For each adjacent pair of edges in
					// LinkG0j, find the (minimum) k for
					// which DG1 brings them both to the
					// same edge in LinkG0j.
	int k;
//cout << "kmax = " << kmax << endl;
	for(i.init();i.ok();++i)
	{
		DE d=i.behind();
		DE e=i.ahead();
//cout << d << " <- i -> " << e << endl;
		k=0;
		while( (d!=e) || !LinkG0j.has(d) )
		{
			assert(k<kmax);		// Prevent infinite loop in case of
						// bad call to this function.
			d=DG1.derivative(d);
			e=DG1.derivative(e);
			k++;
//cout << k << ": " << d << " <- i -> " << e << endl;
		}

				// Construct the edgepath linking
				// -d to e thru G0k.

		d=i.behind();
		e=i.ahead();
		DE f=d.bar();
//cout << "d,e,f= " << d << " " << e << " " << f << endl;	
		LinList<DE> path;
		while( (f=theGraph.leftTurn(f)) != e )
		{
//cout << "f,e= " << f << " " << e << endl;
			path.append(f);	
		}
//cout << "path=" << path << endl;
				// Now form g^k(path).
		for(int m=0;m<k;m++)
		{
			LinListIterator<DE> ie(path);
			LinList<DE> image;
			for(ie.init();ie.ok();)
			{
				image=theMap.copyOfImageOf(ie.ahead());
				++ie;
				ie.replaceb(image);
			}
		}
//cout << "path=" << path << endl;
				// Now we need to append to path
				// the portion of the iterated image
				// of e that precedes the first exit
				// from G0 and prepend the analogous
				// thing for d.
		LinList<DE> tmp(e);
		for(m=0;m<k;m++)
		{
			LinListIterator<DE> ie(tmp);
			LinList<DE> image;
			for(ie.init();ie.ok();)
			{
				image=theMap.copyOfImageOf(ie.ahead());
				++ie;
				ie.replaceb(image);
			}
				// Skip past initial portion in G0.
			for(ie.init();ie.ok();++ie)
			{	
				if( !G0Names.has(ie.ahead().name()) ) break;
			}
			assert(ie.ok());
			++ie;	// Skip over the first edge not in G0.
			while(ie.ok()) ie.deletef();	// Delete the remainder.
//cout << "m=" << m << tmp << endl;
		}
		tmp.popLast();	// Delete the last edge, which is not in G0.

		path.append(tmp);
	
		tmp.clear();
		tmp.append(d);
//cout << "tmp=" << tmp << endl;			
		for(m=0;m<k;m++)
		{
			if(tmp.length()==0) break;
			LinListIterator<DE> ie(tmp);
			LinList<DE> image;
			for(ie.init();ie.ok();)
			{
				image=theMap.copyOfImageOf(ie.ahead());
				++ie;
				ie.replaceb(image);
			}
				// Skip past initial portion in G0.
			for(ie.init();ie.ok();++ie)
			{	
				if( !G0Names.has(ie.ahead().name()) ) break;
			}
			assert(ie.ok());
			++ie;	// Skip over the first edge not in G0.
			while(ie.ok()) ie.deletef();	// Delete the remainder.
//cout << "m=" << m << tmp << endl;
		}
		tmp.popLast();	// Delete the last edge, which is not in G0.

			// Prepend to path the initial portion of the iterated
			// image of d.bar() that is in G0.
		LinListReverseIterator<DE> id(tmp);
		for(id.init();id.ok();++id) path.prepend(id.ahead().bar());

//cout << "path = " << path << endl;

				// Find a (any) peripheral edge, p, in G0.
		DE p;
		SetBrowser<Name> ig(G0k);
		for(ig.init();ig.ok();ig.advance())
		{	
			if(theNameManager.periphery().has(ig.current()))
			{
				p=DE(ig.current(),0);
				break;
			}
		}
		DE pbar=p.bar();
//cout << "Peripheral edge used to measure winding is " << p << endl;

				// Now count the directed crossings of p by path.
		int winding=0;
		LinListBrowser<DE> ip(path);
		for(ip.init();ip.ok();++ip)
		{
			if     (ip.ahead()==p   ) winding++;
			else if(ip.ahead()==pbar) winding--;
		}
//cout << "Winding number is ... " << winding << endl;
		if(winding!=0)		// We've found the place to "part the hair".
		{
				LinList<DE> L(e);
				++i;
				while(i.ahead()!=e)
				{
					L.append(i.ahead());
					++i;
				}
				CircList< LinList<DE> > ctmp(L);
				return ctmp;
		}
	}

 	Boolean foundNonContractibleIteratedAlpha=0;
	assert(foundNonContractibleIteratedAlpha);
}

/************** OBSOLETE as of 4/13/96 
Boolean Map::iteratedDerivativesEventuallyTheSame( DE e, DE f, int nitmax ) const
{
	// Find out if DG^k(e)=DG^k(f) for any 0 < k <= nitmax.

	if(e==f) return 1;

	while(nitmax)
	{
		e=derivative(e);
		f=derivative(f);
		if(e==f) return 1;
		nitmax--;		
	}

	return 0;
}
*****************************/

Boolean Homeo::testLemma421_2() const
{
			// See if Dg maps Lk(P,G) into itself.
				
						// Generate Lk(P,G)
	Set<DE> LkPG = theGraph.Lk(theNameManager.periphery());
//cout << "LkPG = " << LkPG << endl;
	SetBrowser<DE> i(LkPG);
	for(i.init();i.ok();i.advance()) 
	{
//cout << i.current() << " -> " << theMap.derivative(i.current()) << endl;
		if( !LkPG.has(theMap.derivative(i.current())) )
		{
//cout << i.current() << " maps out." << endl;
			return 0;
		}
	}
	return 1;
}

Boolean Homeo::testLemma421_3() const
{
			// See if P has any valence-2 vertices.
				
	SetBrowser<Name> i(theNameManager.periphery());
	for(i.init();i.ok();i.advance()) 
	{
		if( theGraph.originOf(DE(i.current(),0)).length()==2 )
		{
//cout << "Origin of " << DE(i.current(),0) << " has valence 2." << endl;
			return 0;
		}
	}
	return 1;
}