// folding.H
// Written by Qi.
// 	10/18/95  Revised, corrected, and annotated by JR and Qi.
//      12/11/95  Made them return the new DE.
//	4/17/96	  Added function fold(DE e, DE f,int n).
//		  Started to add maintenance of theFingers.
//	4/18/96   Continuing.
//	4/21/96	  Modified Finger updates.

#ifndef FOLDING_H
#define FOLDING_H

// #include "DELList.H" not necessary

DE Homeo::fold(DE e, DE f,int n)	// Fold the first n segments of e and f
{
  assert(n>0);	

  if(!(f==theGraph.leftTurn(e.bar())))
  {
     cout << "theGraph: " << theGraph << endl;
     cout << "e=" << e << ", f=" << f << endl;
     cout << "theGraph.leftTurn(e.bar())=" << theGraph.leftTurn(e.bar()) << endl;	
  }
  assert(f==theGraph.leftTurn(e.bar()));   // Inserted to enforce discipline elsewhere.

  int len1=theMap.lengthOfImageOf(e);
  int len2=theMap.lengthOfImageOf(f);
  DELList l=theMap.commonLeadingSubimage(e,f);
  int len0=l.length();
  assert(len0>0);
  assert(len0>=n);
  for(;len0>n;--len0) l.popLast();

  DE t;

//cout << (*this) << endl;

  if(len1==len0 && len2==len0)
    t=foldII(e,f,l);
  else if(len1==len0)
    t=foldIII(e,f,l);
  else if(len2==len0)
    t=foldIV(e,f,l);
  else
    t=foldI(e,f,l);

//cout << t << "." << endl;
  return t;
}

DE Homeo::foldFirst(DE e,DE f)
{
//cout << "  Folding initial segment of " << e << " and " << f << ": new edge is ";
  if(!(f==theGraph.leftTurn(e.bar())))
  {
     cout << "e=" << e << ", f=" << f << endl;
     cout << "theGraph.leftTurn(e.bar())=" << theGraph.leftTurn(e.bar()) << endl;	
  }
  assert(f==theGraph.leftTurn(e.bar()));  // Inserted to enforce discipline elsewhere.

  int len1=theMap.lengthOfImageOf(e);
  int len2=theMap.lengthOfImageOf(f);
  DELList ll=theMap.commonLeadingSubimage(e,f);
  DE t;
  assert(ll.length());

  DELList l(ll.popFirst());

  if(len1==1 && len2==1)
    t=foldII(e,f,l);			
  else if(len1==1)
    t=foldIII(e,f,l);
  else if(len2==1)
    t=foldIV(e,f,l);
  else
    t=foldI(e,f,l);

//cout << t << "." << endl;
  return t;
}

DE Homeo::foldMany(DE e, DE f)
{
//cout << "  Folding " << e << " and " << f << " as much as possible: new edge is ";
  if(!(f==theGraph.leftTurn(e.bar())))
  {
     cout << "e=" << e << ", f=" << f << endl;
     cout << "theGraph.leftTurn(e.bar())=" << theGraph.leftTurn(e.bar()) << endl;	
  }
  assert(f==theGraph.leftTurn(e.bar()));   // Inserted to enforce discipline elsewhere.

  int len1=theMap.lengthOfImageOf(e);
  int len2=theMap.lengthOfImageOf(f);
  DELList l=theMap.commonLeadingSubimage(e,f);
  DE t;

  int len0=l.length();
  assert(len0);

  if(len1==len0 && len2==len0)
    t=foldII(e,f,l);
  else if(len1==len0)
    t=foldIII(e,f,l);
  else if(len2==len0)
    t=foldIV(e,f,l);
  else
    t=foldI(e,f,l);

//cout << t << "." << endl;
  return t;
}

DE Homeo::foldI(DE e, DE f, const DELList L)
{
//	             		
//		\      /		 \   /
//	      ^e \    /	^f	->     ^e \ /^f
//		  \  /			   |
//		   \/			   |^t
//		   v
			
cout<<"ENTER FOLDI\n";
cout << (*this) << endl;
						// change theGraph
  Boolean eP=peripheral(e);
  Boolean fP=peripheral(f);
  DE t;
  if( (eP&&fP) || ((!eP)&&(!fP)) )
    t=theNameManager.newInteriorEdge();
  else
    t=theNameManager.newPeripheralEdge();

  Vertex& v=theGraph.originOf(e);
  v.deleteDE(e);
  v.replaceDE(f,t);

  theGraph.add( Vertex(e,f,t.bar()) );

  int lenL=L.length();

					// Partially update theFingers.
  int lenImE=theMap.lengthOfImageOf(e);
  int lenImF=theMap.lengthOfImageOf(f);

	LinListIterator<Finger> kf(theFingers.fingers());
	for(kf.init();kf.ok();++kf)
	{
		Finger& foo=kf.ahead();
//cout << "Before: " << foo << endl;
		if(foo.e()==e || foo.e()==f )
		{	
			if(foo.n()>=lenL)
			{	foo.n()-=lenL;
			}
			else
			{	foo.e()=t;
			}
		}
		else if(foo.e()==e.bar())
		{	
			if(foo.n()>=lenImE-lenL)
			{	
				foo.e()=t.bar();
				foo.n()-=lenImE-lenL;
			}
		}
		else if(foo.e()==f.bar())
		{	
			if(foo.n()>=lenImE-lenL)
			{	
				foo.e()=t.bar();
				foo.n()-=lenImF-lenL;
			}
		}
//cout << "After : " << foo << endl;
			
	}
      						//change theMap

  theMap.add(MapElement(t,L));		// t -> commonLeadingSubimage(e,f)

					// delete commonLeadingSubimage
					// from images of e and f
  DELListIterator je(theMap.imageOf(e));
  DELListIterator jf(theMap.imageOf(f));

  int i;
  for(i=0,je.init(),jf.init(); i<lenL ; i++)
  {	je.deletef();
	jf.deletef();
  }

				// Completion of update of theFingers
				// is done in substituteInImages.

  DELList te(t,e),tf(t,f);
  substituteInImages(e,te);
  substituteInImages(f,tf);

 					// the Equator does not change




  return t;
}

DE Homeo::foldIII(DE e, DE f, const DELList L)
{
//	       v2      v3		___t1>__
//		\      /		\
//	      ^e \    /	^f	->   ^t2 \
//		  \  /			  \
//		   \/			   \
//		   v1
//cout<<"******ENTER FOLDIII\n";
  Boolean eP=peripheral(e);
  Boolean fP=peripheral(f);
  DE t1,t2;
  if( (eP&&fP) || ((!eP)&&(!fP)) )
    t2=theNameManager.newInteriorEdge();
  else
    t2=theNameManager.newPeripheralEdge();
  if(fP)
    t1=theNameManager.newPeripheralEdge();
  else
    t1=theNameManager.newInteriorEdge();

  theNameManager.removeEdge(e.name());
  theNameManager.removeEdge(f.name());
                     				// Edges done

  Vertex& v1=theGraph.originOf(e);
  Vertex& v2=theGraph.originOf(e.bar());
  Vertex& v3=theGraph.originOf(f.bar());
  v1.deleteDE(e);
  v1.replaceDE(f,t2);
  v3.replaceDE(f.bar(),t1.bar());
  v2.replaceDE(e.bar(),t1);
  v2.rotateToJustAfterThe(t1);
  v2.pushb(t2.bar());
                         			// Graph done
  int lenL=L.length();
  int lenImF=theMap.lengthOfImageOf(f);
						// Partially update theFingers.

	LinListIterator<Finger> kf(theFingers.fingers());
	for(kf.init();kf.ok();++kf)
	{
		Finger& foo=kf.ahead();
		if( foo.e()==e )
		{
			foo.e() = t2;
		}
		else if( foo.e()==e.bar() )
		{
			foo.e() = t2.bar();
		}			
		else if( foo.e()==f )
		{	
			if(foo.n()>=lenL)
			{	
				foo.e() = t1;
				foo.n()-=lenL;
			}
			else
			{	
				foo.e()=t2;
			}
		}
		else if( foo.e()==f.bar() )
		{	
			if( foo.n()>=lenImF-lenL)
			{
				foo.e() = t2.bar();
				foo.n()-= lenImF-lenL;
			}
			else
			{
				foo.e() = t1.bar();
			}
		}
	}


      						//change theMap
  theMap.add(MapElement(t2,L));

  DELListIterator jf(theMap.imageOf(f));
  int i;
  for(i=0,jf.init(); i<lenL ; i++) jf.deletef();

  theMap.add(MapElement(t1,theMap.copyOfImageOf(f)));
  theMap.deleteElement(e.name());
  theMap.deleteElement(f.name());

  DELList lf(t2,t1), le(t2);
  substituteInImages(e,le);
  substituteInImages(f,lf);
						// Map done
      			
						// change the Equator
  DELList el1(e,f),el2(t2),el3(t2,t1.bar()),el4(t1);
  theEquator.substitute(el1,el2);
  theEquator.substitute(e,el3);
  theEquator.substitute(f,el4);
						// Equator done



  return t2;
}

DE Homeo::foldIV(DE e, DE f, const DELList L)
{
//	       v2      v3		___<t1__
//		\      /		       /
//	      ^e \    /	^f	->            /^t2
//		  \  /			     /
//		   \/			    /
//		   v1

//cout<<"******ENTER FOLDIV\n";
  Boolean eP=peripheral(e);
  Boolean fP=peripheral(f);
  DE t1,t2;
  if( (eP&&fP) || ((!eP)&&(!fP)) )
    t2=theNameManager.newInteriorEdge();
  else
    t2=theNameManager.newPeripheralEdge();
  if(eP)
    t1=theNameManager.newPeripheralEdge();
  else
    t1=theNameManager.newInteriorEdge();

  theNameManager.removeEdge(e.name());
  theNameManager.removeEdge(f.name());
                     				// Edges done

  Vertex& v1=theGraph.originOf(e);
  Vertex& v2=theGraph.originOf(e.bar());
  Vertex& v3=theGraph.originOf(f.bar());
  v1.deleteDE(e);
  v1.replaceDE(f,t2);
  v2.replaceDE(e.bar(),t1.bar());
  v3.replaceDE(f.bar(),t1);
  v3.rotateToJustBeforeThe(t1);
  v3.pushf(t2.bar());
                         			//Graph done
  int lenL=L.length();
  int lenImE=theMap.lengthOfImageOf(e);

						// Partially update theFingers.

	LinListIterator<Finger> kf(theFingers.fingers());
	for(kf.init();kf.ok();++kf)
	{
		Finger& foo=kf.ahead();
		if( foo.e()==f )
		{
			foo.e() = t2;
		}
		else if( foo.e()==f.bar() )
		{
			foo.e() = t2.bar();
		}			
		else if( foo.e()==e )
		{	
			if(foo.n()>=lenL)
			{	
				foo.e() = t1;
				foo.n()-=lenL;
			}
			else
			{	
				foo.e()=t2;
			}
		}
		else if( foo.e()==e.bar() )
		{	
			if( foo.n()>=lenImE-lenL)
			{
				foo.e() = t2.bar();
				foo.n()-= lenImE-lenL;
			}
			else
			{
				foo.e() = t1.bar();
			}
		}
	}


      						//change theMap
  theMap.add(MapElement(t2,L));

  DELListIterator je(theMap.imageOf(e));
  int i;
  for(i=0,je.init(); i<lenL ; i++) je.deletef();

  theMap.add(MapElement(t1,theMap.copyOfImageOf(e)));
  theMap.deleteElement(e.name());
  theMap.deleteElement(f.name());

  DELList le(t2,t1), lf(t2);
  substituteInImages(e,le);
  substituteInImages(f,lf);
						// Map done
      			
						// change the Equator
  DELList ef(e,f),el2(t2),el3(t1.bar(),t2),el4(t1);
  theEquator.substitute(ef,el2);
  theEquator.substitute(e,el4);
  theEquator.substitute(f,el3);
						// Equator done

  return t2;
}


DE Homeo::foldII(DE e, DE f, const DELList L)
{
//	       v2      v3		  |
//		\      /		  |
//	      ^e \    /	^f	->        |^t
//		  \  /			  |
//		   \/			  |
//		   v1
//cout << (*this) << endl;
//cout<<"ENTER FOLDII\n";

  Boolean eP=peripheral(e);
  Boolean fP=peripheral(f);
  DE t;
  if( (eP&&fP) || ((!eP)&&(!fP)) )
    t=theNameManager.newInteriorEdge();
  else
    t=theNameManager.newPeripheralEdge();

  theNameManager.removeEdge(e.name());
  theNameManager.removeEdge(f.name());
                     				// Edges done
    		
						//change theGraph
  Vertex& v1=theGraph.originOf(e);
  Vertex& v2=theGraph.originOf(e.bar());
  Vertex& v3=theGraph.originOf(f.bar());

  Vertex w2(v2);	// save for use in changing theEquator
  Vertex w3(v3);

  v1.deleteDE(e);
  v1.replaceDE(f,t);
  v3.replaceDE(f.bar(),t.bar());
  v3.rotateToJustAfterThe(t.bar());
  v3.pushb(e);
  theGraph.mergeAlong(e);
						// Graph done

						// Partially update theFingers.

	LinListIterator<Finger> kf(theFingers.fingers());
	for(kf.init();kf.ok();++kf)
	{
		Finger& foo=kf.ahead();
		if(foo.e()==e || foo.e()==f )
		{	
			foo.e() = t;
		}
		else if(foo.e()==e.bar() || foo.e()==f.bar() )
		{	
			foo.e() = t.bar();
		}
			
	}

				      		//change theMap
  MapElement me(t,L);
  theMap.add(me);

  theMap.deleteElement(e.name());
  theMap.deleteElement(f.name());

  DELList l(t);
  substituteInImages(e,l);
  substituteInImages(f,l);
						// Map done
    			
						// change theEquator
  DELList l0(e,f),l1(t);
  theEquator.substitute(l0,l1);

  LinList<DE> l2(e.bar(),w2);
  l2.popFirst();
  LinList<DE> l3(f.bar(),w3);
  l3.popFirst();
  theEquator.substitute(e,l2);
  theEquator.substitute(f,l3);
						// Equator done
//cout << (*this) << endl;



  return t;
}

#endif