// moreAbsorb.c
//	JR
//	4/3/96 	Started on splitPeripheralVertex.
//		Tested on homeo7.dat (-12,11).
//		(Would a set of fold(...,0) do the same thing?)
//	4/4/96  Wrote collapseNonPeripheralG0 (and vertexIsPeripheral).
//		Tested collapseNonPeripheralG0 on homeo8,8b,8c.
//		Wrote splitPeripheralVertices(structuredLinkG0).
//		Tested splitPeripheralVertices on homeo8c.dat (testSplits.c).
//	4/5/96  Fixed problem in splitPeripheralVertex for case of the
//		vertex being invariant. 
//		More work on establishing the peripheral simplicial 
//		homeomorphism.
//		Finished.

DE Homeo::splitPeripheralVertex( DE e, DE f )
{
	// Split the peripheral vertex which has ebar f in its link,
	// creating a new peripheral edge (with empty image).


//		\_     _/       	   \_               _/
//		/\     /\       	   /\               /\
//	       -e \   / f       	  -e \             / f'
//		   \ /          	      \           /
//		    . ______{i}   --->         . ___\___ .  ______{i'}
//		   / \          	      /     /q    \
//		  /   \p        	     /             \p' 
//		 /  .  \   		    /       .       \
//		   punc				   punc

//cout << "Into splitPeripheralVertex( " << e << " " << f << ")" << endl;
					// Check that ebar f is in the link.
	Vertex& v(theGraph.originOf(f));
	v.rotateToJustBeforeThe(f);
//cout << "v=" << v << endl;
	assert(v.behind()==e.bar());
					// Check that the vertex is peripheral.
					// And at the same time make the set of
					// edges that will be folded.
					// And create the new vertex w.
					// And modify the vertex v.
	Vertex w;
	Set<DE> foldees;
	Set<DE> nonfoldees;
	Boolean isOnPeriphery=0;
	CircListIterator<DE> i(v);
	for(i.init();i.ok(); )
	{
//cout << i.ahead() << endl;
		foldees.add(i.ahead());
		w.pushb(i.ahead());
		if(theNameManager.periphery().has(i.ahead().name()))
		{
			i.deletef();
			isOnPeriphery=1;
			break;
		}
		i.deletef();
	}
	assert(isOnPeriphery);
//cout << "v=" << v << endl;

	for(i.init();i.ok();++i) nonfoldees.add(i.ahead());
	i.init();

//cout << "nonfoldees are " << nonfoldees << endl;

					// Special attention required
					// if the spilt vertex is
					// invariant.
	Boolean vIsInvariant=vertexInvariant(v);

						// NameManager
	DE q=theNameManager.newPeripheralEdge();
//cout << "q=" << q << endl;
						// Graph
	w.pushb(q.bar());
	i.insertf(q);
	theGraph.add(w);
//cout << "new Graph = " << theGraph << endl;
//cout << "v=" << v << endl;
						// Map

	SetBrowser<DE> k(foldees);
	for(k.init();k.ok();k.advance())
	{
		DE d=k.current();
//cout << "d=" << d << endl;
		LinList<DE> r(q,d);
		substituteInImages(d,r);
	}

		// The case where the vertex is invariant is a
		// little different. For the folded half of the
		// link of the vertex, we need to shift the origins
		// of their images to w.

//cout << "v=" << v << endl;

	if( vIsInvariant )
	{
//cout << "theMap=" << theMap << endl;
		for(k.init();k.ok();k.advance())
		{
			DE d=k.current();
//cout << "d = " << d << endl;
			DELListIterator im(theMap.imageOf(d));
			im.init();
			assert(im.ok());
			if( im.ahead() == q ) 
			{
				im.deletef();
			}
			else if( nonfoldees.has(im.ahead()) ) 
			{
				im.insertf(q.bar());
			}
		}
	}
	DELList qim(q);		// Quick fix for multiple-splitting
				// of an invariant vertex.
				// Should be ignored otherwise.
	theMap.add(MapElement(q,qim));
//cout << "new Map = " << theMap << endl;
						// Equator
	// Nothing to do.

	return q;
}


void Homeo::collapseNonPeripheralG0(LinList< Set<Name> >& G0)
{
	// We collapse the non-peripheral edges in each G0i,
	// working from the peripheral vertices outwards,
	// by repeatedly collapsing just the edges in G0i that are
	// incident on the periphery (which brings another set
	// into incidence on the periphery).
	
   LinListIterator< Set<Name> > i(G0);
   for(i.init();i.ok();++i)
   {
	Set<Name>& G0i=i.ahead();
	Set<DE> pIncidentG0i;
						// Make the set of peripheral
						// edges in G0i.
	Set<Name> pG0i;
	SetBrowser<Name> ip(G0i);
	for(ip.init();ip.ok();ip.advance())
		if(theNameManager.periphery().has(ip.current()))
			pG0i.add(ip.current());
	
	Boolean notFinished=1;
	while(notFinished)
	{
						// Prepare the set of edges
						// in G0i that originate on
						// (but are not part of) 
						// the periphery.
		SetBrowser<Name> ig(G0i);
		for(ig.init();ig.ok();ig.advance())
		{
			if(!pG0i.has(ig.current()))	// If edge not peripheral,
			{				// see if incident on periphery.
							
				DE c(ig.current(),0);   // Make directed edge.
				if(vertexIsPeripheral(theGraph.originOf(c)))
				{
					pIncidentG0i.add(c);
				}
				else if	(vertexIsPeripheral(theGraph.originOf(c.bar())))
				{
					pIncidentG0i.add(c.bar());
				}
			}	
		}
		if(pIncidentG0i.isEmpty()) notFinished=0;
						// Collapse them all,
						// pushing Equator-crossings
						// outwards.
		while(!pIncidentG0i.isEmpty())
		{
			DE c=pIncidentG0i.removeOne();
			directedCollapseEdge(c);
			G0i.remove(c.name());
		}
	}	
   }
}

Boolean Homeo::vertexIsPeripheral(const Vertex& v) const
{
	CircListBrowser<DE> i(v);
	for(i.init();i.ok();++i)
	{
		if(theNameManager.periphery().has(i.ahead().name()))
			return 1;
	}
	return 0;
}


LinList< LinList<DE> > Homeo::splitPeripheralVertices
		(LinList< CircList< LinList<DE> > >& structuredLinkG0)
{
	// We look at the last edge in each equivalence class and the
	// first edge in the next equivalence class. If these edges
	// both emanate from the same vertex, we split that vertex.

	// We create a list of peripheral edges that are new or are
	// survivors of the absorbing process,
	// and a list of the peripheral edges which are to be collapsed.

   LinList<DE> toBeCollapsed;
   LinList<DE> newAndSurviving;
   
   LinListBrowser<  CircList< LinList<DE> > > i(structuredLinkG0);
   for(i.init();i.ok();++i)
   {
		// Deal with the link of the ith component G0.

	CircListBrowser< LinList<DE> > j(i.ahead());
	for(j.init();j.ok();++j)
	{
				// Deal with the transition between the
				// equivalence class behind and the one ahead.

		DE d=j.behind().last();
		DE e=j.ahead().first();
//cout << "splits: " << d << " " << e << endl;
		if(e==theGraph.leftTurn(d.bar())) 
		{
			newAndSurviving.append(splitPeripheralVertex(d.bar(),e));
//cout << "newAndSurviving=" << newAndSurviving << endl;
		}
		else
		{
			DE f=theGraph.leftTurn(d.bar());
			while(f!=e)
			{
				newAndSurviving.append(f);
				f=theGraph.leftTurn(f);
			}
		}
				// Now deal with the interior of the 
				// equivalence class ahead.

		LinListBrowser<DE> k(j.ahead());
		k.init();
		assert(k.ok());
		++k;
		while(k.ok())
		{
			d=k.behind();
			e=k.ahead();
			DE f=theGraph.leftTurn(d.bar());
			while(f!=e)
			{
					// Mark the edges in the path between
					// d.bar to e for collapse.
				toBeCollapsed.append(f);
				f=theGraph.leftTurn(f);
			}
			++k;
		}

	}
   }

   LinList< LinList<DE> > tmp(toBeCollapsed,newAndSurviving);
   return tmp;
}

void Homeo::collapsePeripheralG0( const LinList<DE>& toBeCollapsed )
{
	// We collapse the non-surviving peripheral edges in G0.
	// We do them in sequence so that we are clearing edges
	// clockwise. This might not be optimal (minimize twisting).
	
	LinListBrowser<DE> i(toBeCollapsed);
	for(i.init();i.ok();++i)
	{
		directedCollapseEdge(i.ahead());
	}
}

void Homeo::establishPeripheralHomeomorphism( const LinList<DE>& P )
{
   LinListBrowser<DE> i(P);
   for(i.init();i.ok();++i)
   {
	DE p=i.ahead();
					// The following eventuality
					// (valence-2 vertex on periphery)
					// can be dealt with if necessary.
	if( theGraph.originOf(p).length() <= 2 )
	{
		cout << "The case of a valence-2 can be accommodated" << endl;
		cout << "(with a little more work) if necessary." << endl;
	}
	assert( theGraph.originOf(p).length() > 2 );

	DE f=theGraph.rightTurn(p.bar());  // A non-peripheral edge with same
					   // vertex of origin as p.
					
					   // Find the edge along which
					   // the image of f exits P.
	DELListBrowser imf(theMap.imageOf(f));
	DE g;
	Boolean wentOut=0;
	for(imf.init();imf.ok();++imf)	
	{
		g=imf.ahead();
		if( !( P.has(g) || P.has(g.bar()) ) )
		{
			wentOut=1;
			break;
		}
	}
	assert(wentOut);
	theGraph.originOf(g).rotateToJustAfterThe(g);
	CircListBrowser<DE> j(theGraph.originOf(g));
	DE q;
	Boolean foundQ=0;
	for(j.init();j.ok();++j)	// Work clockwise around the vertex until 
	{				// arriving at a peripheral edge.
		if(theNameManager.periphery().has(j.ahead().name()))
		{
			foundQ=1;
			q=j.ahead();	
			break;
		}
	}
	assert(foundQ);
	LinList<DE> image(q);
	theMap.deleteElement(p.name());	// Get rid of existing entry for p.
	theMap.add( MapElement(p,image) );  // Add the new one.
   }	
}


void Homeo::phi1IsotopyOnLinkG0(const LinList< CircList<DE> >& LinkG0)
{
			// Delete the leading subimage in P of
			// each of the edges in LinkG0.

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

   LinListBrowser< CircList<DE> > i(LinkG0);
   for(i.init();i.ok();++i)
   {
	CircListBrowser<DE> j(i.ahead());
	for(j.init();j.ok();++j)
	{
		DELListIterator k(theMap.imageOf(j.ahead()));
		k.init();
		while( k.ok() && P.has(k.ahead().name()) )
		{
//cout << "popping " << k.ahead() << endl;
			k.deletef();
		}
	}
   }


}