//	JR
//	1/1/96	Started subdivideOrigNear().
//		Note of caution: Suppose have e -> e f g h.
//		Then this function will make
//			e -> e
//			n -> f g h
//		but there may not be any initial segment of
//		e that gets mapped to itself.
//		No that's OK, an isotopy can be done to make it so.
//		Compiled and tested (superficially) on homeo.dat.
//	1/2/96 	Adapted subdivideOrigNear() to make subdivideOrigFar().
//		The latter not yet tested at all.
//	3/12/96	In step7, need subdivision with specified division
//		of the image. Added int argument.
//	4/12/96 These functions work as advertised.
//		However, subdivideOrigNear(e, 1) when Dg(e)=e 
//		generates an invariant edge, which destroys irreducibility. 
//		We don't want to do this!
//		Will it be OK to subdivide "at the point that gets mapped
//		to the nth vertex in the existing image?
//		Sure. In the end, the only place I used this function
//		was in Step7, which where doing it the old way is a problem.
//		Only change needed is to do the substitutions in the images
//		AFTER the actual subdividing instead of before.
//	4/18/96 Started on subdivideAsFarOutAsPossible.
//	4/19/96	Completed.
//	4/21/96 Revamped subdivideAsFarOutAsPossible as 
//		subdivideAsCloseInAsPossible.

DE Homeo::subdivideOrigNear(DE e,int len)
{
//	USED TO BE: Subdivide edge e so that e gets an image of length len.
//	NOW: Subdivide edge e at the point that gets mapped to the len^th
//	vertex in its existing image.
//	     e
//	.-------------->.
//
//	 e       n
//	.->.----------->.

	theFingers.markInvalid();	// Finger update not yet coded.


	


	// make the new edge
	DE n;
	if(peripheral(e))
		n=theNameManager.newPeripheralEdge();	
	else
		n=theNameManager.newInteriorEdge();

	// adjust the graph and add the new vertex

	Vertex& v=theGraph.originOf(e.bar());
	v.replaceDE(e.bar(),n.bar());
	theGraph.add( Vertex(e.bar(),n) );

	// add new entry to map for edge n, and adjust image of e

	DELListIterator i=theMap.imageOf(e);
	DELList L;

	assert(theMap.lengthOfImageOf(e)>len); // otherwise subdivision is not possible

	for(int ii=0;ii<len;ii++) ++i;
		
	while(i.ok())
	{	
	 	L.append(i.ahead());
		i.deletef();
	}
	theMap.add(MapElement(n,L));	

	// In the map images, replace all e's by en's

	DELList R(e,n);
	substituteInImages(e,R);


	// leave the equator-crossings alone

	return n;
}

DE Homeo::subdivideOrigFar(DE e,int len)
{
//	Subdivide edge e so that new edge n gets an image of length len.

//	     e
//	.-------------->.
//
//	 n       e
//	.->.----------->.

	theFingers.markInvalid();	// Finger update not yet coded.

	assert(theMap.lengthOfImageOf(e)>1); // otherwise subdivision is not possible

	// make the new edge
	DE n;
	if(peripheral(e))
		n=theNameManager.newPeripheralEdge();	
	else
		n=theNameManager.newInteriorEdge();

	// adjust the graph and add the new vertex

	Vertex& v=theGraph.originOf(e);
	v.replaceDE(e,n);
	theGraph.add( Vertex(n.bar(),e) );

	// add new entry to map for edge n, and adjust image of e

	DELList L;
	DELListIterator i=theMap.imageOf(e);
	int ii;
	for( i.init(),ii=0; i.ok(),ii<len; ii++ )
	{	
		L.append(i.ahead());
		i.deletef();
	}	
	theMap.add(MapElement(n,L));	

	// In the map, replace all e's by ne's

	DELList R(n,e);
	substituteInImages(e,R);

	// leave the equator-crossings alone

	return n;
}

void Homeo::subdivideAsCloseInAsPossible( const DE& c )
{
	int lenIm=theMap.lengthOfImageOf(c);
	assert(lenIm>0);
	if(lenIm==1) 
	{
		DE dgc=theMap.derivative(c);
		assert(dgc!=c);
cout << "    Can't subdivide " << c << ", so going to subdivide " << dgc << "." << endl;
		subdivideAsCloseInAsPossible(dgc);
	}

		// Now length of image of c is greater than 1.

	int lenImC=theMap.lengthOfImageOf(c);
//cout << "Length of image of " << c << " is " << theMap.lengthOfImageOf(c) << endl;

			// Do the subdivision and update the fingers.

//Subdivide edge c at the point that gets mapped to the first
//	vertex in its existing image.
//	     c
//	.-------------->.
//
//	  c       n
//	.--->.--------->.

			// make the new edge
	DE n;
	if(peripheral(c))
		n=theNameManager.newPeripheralEdge();	
	else
		n=theNameManager.newInteriorEdge();

	// adjust the graph and add the new vertex

	Vertex& v=theGraph.originOf(c.bar());
	v.replaceDE(c.bar(),n.bar());
	theGraph.add( Vertex(c.bar(),n) );

	// add new entry to map for edge n, and adjust image of c


	DELList L;
	int len=1;

	DELListIterator i=theMap.imageOf(c);
	int ii;
	for(i.init(),ii=0;ii<len;ii++) ++i;
		
	while(i.ok())
	{	
	 	L.append(i.ahead());
		i.deletef();
	}
	theMap.add(MapElement(n,L));	

					// Partially update theFingers.

	LinListIterator<Finger> kf(theFingers.fingers());
	for(kf.init();kf.ok();++kf)
	{
		Finger& foo=kf.ahead();
//cout << "Before: " << foo << endl;
		if(foo.e()==c)
		{	
			if(foo.n()>=len)
			{	
				foo.e()=n;
				foo.n()-=len;
			}
		}
		else if(foo.e()==c.bar())
		{	
			if(foo.n()<lenImC-len)
			{	
				foo.e()=n.bar();
			}
			else
			{
				foo.n()-=lenImC-len;
			}
		}
//cout << "After : " << foo << endl;
			
	}

	// In the map images, replace all c's by cn's

	DELList R(c,n);
	substituteInImages(c,R);


	// leave the equator-crossings alone

}
