// newStep7.c
//	JR
//	4/13/96
// 	We don't want to really subdivide to create the valence-2
//	vertex, p, because that would prevent us folding through it
//	which is good to do when possible.

//	4/19/96	Working on this.
//	4/20/96 Finished and tested.

#include "IndexedLinList.H"

void Homeo::step7()
{
	// Assumes that it is only called after a call to efficient()
	// yields FALSE.


	theFingers.clear();	// Until Finger updating is done in
				// all Homeo-modification functions,
				// we must do this.


	// Find the virtual valence-2 vertex, p.
	
//cout << "step7" << endl;

	Boolean did=0;

	IndexedLinList< DE, LinList< LinList<DE> > > vlistlist;

	SetBrowser<MapElement> m(theMap);
	for(m.init();m.ok();m.advance())
	{	
		// Add to the list of (source) edges

		DE e(m.current().source());
	
		// Create the list of "turns" corresponding
		// to the image of this edge.

//cout << vlistlist << endl << endl;
		DELListBrowser i(theMap.imageOf(e));
		i.init();
		if(i.ok())
		{
			++i;		// Step to first vertex (if any)
			LinList< LinList<DE> > vlist;
			for(; i.ok(); ++i ) 
				vlist.append(LinList<DE>(i.behind().bar(),i.ahead()));
			vlistlist.append(e,vlist);
//cout << vlistlist << endl << endl;
		}
	}

	// Now start iterating Dg and look for folding.
	// Note: if the map is tight, we cannot already have (c,c)
	// as one of the "vertices".
	// Should we  assert(!pullTight())? No, pullTight is of type void.

	IndexedLinListIterator< DE, LinList<LinList<DE> > > n(vlistlist);
	int k=1;	// number of iterates  

	DE E,p,q;
	int vcount=0;
	Boolean breakout=0;  // Required because label can't be used in
			     // block with destructors.

//cout << vlistlist << endl << endl;

	while(!breakout)
	{
		k++;	
		for( n.init(); n.ok(); ++n )
		{
			if(breakout) break;
			{
				E = n.iahead();
//cout << "Looking at " << n.iahead() << endl; 
				LinListIterator< LinList<DE> > v(n.ahead());
				for( v.init(),vcount=1; v.ok(); ++v,vcount++)
				{

					// replace DE pair by images under Dg
					DE Dg0 = theMap.derivative( v.ahead()[0] );
					DE Dg1 = theMap.derivative( v.ahead()[1] );
					if( Dg0 == Dg1 )
					{
					// Break out if folding has occurred
						p=v.ahead()[0];
						q=v.ahead()[1];
						breakout=1;
						break;
					}
					v.ahead()[0] = Dg0;
 					v.ahead()[1] = Dg1; 	
					// Break out if folding has occurred
				}
			}
		}
	}

	assert(breakout);	// Otherwise the above found nothing to do.
				// This assertion should not fail, since
				// step 7 is only called if not Efficient.

//cout << "E,p,q,vcount= " << E << " " << p << " " << q << " " << vcount << endl;

	DELListBrowser iv(theMap.imageOf(E));
	int vc;
	for(iv.init(),vc=0;assert(iv.ok()),vc<vcount;++iv,vc++)
	{}
	p=iv.behind().bar();
	q=iv.ahead(); 
	
	Key key=theFingers.add(E,vcount);
	foldAvoidingMarkedPoint(p,q,key);
	theFingers.remove(key);

	theFingers.clear();	// Just to be safe.		

}

void Homeo::foldAvoidingMarkedPoint(DE d, DE e, Key key)
{
	// Assume d and e are in the same gate.
	// Fold them, and any intervening edges in their
	// gate, together as much as possible
	// being sure to avoid increasing the valence of
	// the marked point identified by key,
	// and doing subdividing and other folding as necessary.

cout << "    Folding edges " << d << " and " << e <<
	", avoiding the point " << theFingers.finger(key) << endl;

	assert(d!=e);

				// Mark d and e.
	Key dKey=theFingers.add(d,0);
	Key eKey=theFingers.add(e,0);

	DE dd,ee;
	if( (dd=theMap.derivative(d)) != (ee=theMap.derivative(e)) )
	{
		foldAvoidingMarkedPoint(dd,ee,key);
	}

	// When we get back ...
				// Find out what d and e are called now.
	Finger tmp=theFingers.finger(dKey);
	if(tmp.n()==0)
	{
		d=tmp.e();
	}	
	else
	{
		d=tmp.e().bar();
	}
	tmp=theFingers.finger(eKey);
	if(tmp.n()==0)
	{
		e=tmp.e();
	}	
	else
	{
		e=tmp.e().bar();
	}
	theFingers.remove(dKey);
	theFingers.remove(eKey);


	LinList<DE> cls=theMap.commonLeadingSubimage(d,e);
				
				// Find L, 
				// the portion of the gate
				// of d and e bounded by d and e.
	DELList L( subGate(d,e) );

//cout << "L = " << L << endl;

	DE f=theFingers.finger(key).e();
	int n=theFingers.finger(key).n();

	if( L.has(f.bar()) )	// Reverse f for convenience.
	{
		f = f.bar();
		n = theMap.lengthOfImageOf(f)-n;
	}

	if( (!L.has(f)) || (n!=cls.length()) )
	{
					// Do the maximal fold of L.
		LinListIterator<DE> i(L);
		i.init();
		assert(i.ok());
		++i;
		while(i.ok())
		{
//cout << "About to fold " << i.behind() << " and " << i.ahead() << endl;
			i.ahead()=foldMany(i.behind(),i.ahead());
			++i;
		}
	}
	else if(n>1)
	{
		// Do a fold of L: just the first n-1 subedges.
//cout << "About to do an n-1 fold of " << L << endl;
		LinListIterator<DE> i(L);
		i.init();
		assert(i.ok());
		++i;
		while(i.ok())
		{
			i.ahead()=fold(i.behind(),i.ahead(),n-1);
			++i;
		}
	}
	else
	{
		// Need to mark the origins of edges in L,
		// because the names could get changed during subdivision.
		LinList<Key> LKeys;
		LinListBrowser<DE> i(L);
		for(i.init();i.ok();++i) LKeys.append(theFingers.add(i.ahead(),0));

		DE c=theMap.derivative(L.first());
//cout << "About to do subdivision(s) of " <<  c << endl;
		subdivideAsCloseInAsPossible( c );	// (recursively)

					// Reconstitute L and clear the marks.
		L.clear();
		LinListBrowser<Key> ik(LKeys);
		for(ik.init();ik.ok();++ik)
		{ 	
			Finger le=theFingers.finger(ik.ahead());
			if(le.n()==0)
			{
				L.append(le.e());
			}
			else
			{
//cout << "HEY! Edge " << le.e() << " got reversed." << endl;
				L.append(le.e().bar());
			}
			theFingers.remove(ik.ahead());
		}
//cout << "About to fold first segment of " << L << endl;
		// Then fold L to the first subedge only.
		LinListIterator<DE> iL(L);
		iL.init();
		assert(iL.ok());
		++iL;
		while(iL.ok())
		{
			iL.ahead()=fold(iL.behind(),iL.ahead(),1);
			++iL;
		}

	}
}

LinList<DE> Homeo::subGate(DE d,DE e)
{
	// Return the list of edges (in clockwise order)
	// from d to e in their gate.
 
	DE dd=d,ee=e;
	int k=0;
	while(dd!=ee)
	{	k++;
		dd = theMap.derivative(dd);
		ee = theMap.derivative(ee);
	}
	DE c=ee;

		// Make a list of the edges to be folded.
		// These are the edges d thru e which map
		// together under Dg^k.
	
	Vertex& v(theGraph.originOf(e));
	// Working hypothesis: e is clockwise from d in the gate.
	Boolean hypothesisSound=1;
	LinList<DE> L(d);
	v.rotateToJustAfterThe(d);
	DE f;
	while((f=v.ahead())!=e)
	{
		if( c != theMap.derivativeKTimes(f,k) )
		{
			hypothesisSound=0;
			break;
		}
		else
		{
			L.append(f);
			v.rotateb();
		}
	}

	if(!hypothesisSound)
	{
		v.rotateToJustBeforeThe(d);
		L.clear();
		L.prepend(d);
		while( (f=v.behind()) != e )
		{
			assert( c == theMap.derivativeKTimes(f,k) );
			L.prepend(f);
			v.rotatef();
		}
		L.prepend(e);
	}
	else
	{
		L.append(e);
	}
//cout << "L=" << L << endl;

	return L;
}