// Constructor.c
// Construction of Homeo from BraidWord
//  JR	9/25/95 Much work done, but notice there is no taking care of negative
//		braid generators.
//	9/26/95 Sense of braid generators now accounted for.
//      9/27/95
//     10/12/95 Trying to compile for first time!
//	10/24/95  Converted for LinList and CircList
//	10/26/95  Fixed initial tightening code.

#include <assert.h>
#include "Homeo.H"
#include "DE.H"
#include "LinList.H"
#include "CircList.H"	// used at all?
#include "DELList.H"
#include "Vertex.H"
#include "Boolean.H"
//#include <iostream.h>
#include <iostream>
using namespace std;

typedef LinList<int> BraidWord;

Homeo::Homeo( const BraidWord& bw )
{
	// Determine the number of strands
        int n=1;	// Default, if braid word is empty.
	LinListBrowser<int> i(bw);
	for(i.init();i.ok();++i) 
	{
		int letter=i.ahead();
		if(letter<0) letter =-letter;
		if(letter>=n) n=letter+1;
	}

//   cout << "Braid has " << n << " strands." << endl;

        LinList<DE> edges;

	typedef LinList<DE> LinListDE;
        LinList<LinListDE> images;

        for( int ib=0; ib<n; ib++ )
        {
		DE d(theNameManager.newPeripheralEdge());
                edges.append( d );
                images.append( LinList<DE>(d) );
        }

// cout << "Stage 1 completed." << endl;
Boolean tflag=0;

        LinListBrowser<int> b(bw);
        for( b.init(); b.ok(); ++b )    // For each braid generator, reading left to right
        {
                int bg = b.ahead();
//cout << "Braid generator is: " << bg << endl;
		Boolean bgpos=(bg>0);
		if(bg<0) bg=-bg;
		DE e1(edges[bg-1]);   	// Note braid-strand numbering starts at 1,
		DE e2(edges[bg]);	// array indexing at 0.
	

/////////////          LinListBrowser<LinList<DE>> ii(images); // won't compile!
                LinListIterator<LinListDE> ii(images);
                for( ii.init(); ii.ok(); ++ii )         // For each image
                {
// cout << "Image: " << ii.ahead() << endl;
                        LinListIterator<DE> j(ii.ahead());
                        for( j.init(); j.ok(); ++j )    // apply the braid word to each edge
                        {
                                DE e = j.ahead();

				if( bgpos )
				{
                                	// This is the formula for the image of
                                	// the "rose with n petals" graph under the action
                                	// of the braid word (H. Huang, 9/21/95):
		
                                	if( e == e1 )
					{
						j.replacef(e1.bar());
						j.insertf(e2);
						j.insertf(e1);
						++j; ++j; 	// ++j in "for" statement will now
								// step to next original DE
                                	}
                                	if( e == e1.bar() )
					{
						j.replacef(e1.bar()); // f because ++j is about to happen!
						j.insertf(e2.bar());
						j.insertf(e1);
						++j; ++j;
                                	}
					else if( e == e2 )
						j.replacef( e1 );
					else if( e == e2.bar() )
						j.replacef( e1.bar() );
                        	//      else unchanged
				}
				else // bg negative
				{
                                	if( e == e1 )
                                     	   	j.replacef( e2 );
                                	if( e == e1.bar() )
                                     	   	j.replacef( e2.bar() );
                                	else if( e == e2 )
                                        {	j.replacef( e2 );
						j.insertf( e1 );
						j.insertf( e2.bar() );
						++j; ++j;
					}
                                	else if( e == e2.bar() )
                                        {	j.replacef( e2 );
						j.insertf( e1.bar() );
						j.insertf( e2.bar() );
						++j; ++j;
					}
                        	//      else unchanged
				}
// cout << "Transformed image: " << ii.ahead() << endl;
                        }
//cout << "About to tighten image" << endl;
                        // Tighten the image
			j.init();
			while(j.ok())
			{	
				if(!j.bok()) ++j;
				else
				{
					if( j.behind()==j.ahead().bar() )
					{
						j.deleteb();
						j.deletef();
						tflag=1;
					}
					else
					{
						++j;
					}
				}		
			}
	        }
	}
if(!tflag) cout << "No initial tightening required" << endl;
//cout << "Stage 2 completed." << endl;

        // End of construction of images for "flower" graph.
        // Now convert to "bunch-of-balloons" graph.


        LinListIterator<LinListDE> ii(images);
        for( ib=0,ii.init(); assert(ii.ok()),ib<n; ib++,++ii )  // Make n more edges.
								// These will be the
								// "strings of the balloons".
        {       edges.append( theNameManager.newInteriorEdge() );
                images.append( ii.ahead() );         // copy the image of the petal
        }
//cout << images << endl;

//cout << "n more edges made." << endl;

	for(int k=0;k<n;k++)
	{
// cout << images[k] << " flush -> ";
		images[k] = LinList<DE>();	// flush the images for the circles
// cout << images[k] << endl;
	}

// cout << "Images for circles flushed." << endl;
// cout << images << endl;

        // Now for each occurrence in the images of edge e_k replace it by e_n+k,e_k,e_n+k.bar()

	for(   k=0;k<n;k++)  // for each of the petal-edges
	{
		DE ek = edges[k];
		DE ekbar = ek.bar();
		DELList rep( edges[n+k],ek,edges[n+k].bar() );
		DELList repbar( rep.bar() );
//		LinListBrowser<List<DE>> jj(images);  won't compile
		LinListIterator<LinListDE> jj(images);
                for( jj.init(); jj.ok(); ++jj )         // For each image
         	{
// cout << "Working on image " << jj.ahead() << endl;
			LinListIterator<DE> ie(jj.ahead());
			for(ie.init();ie.ok();)
			{	
// cout << "ie.ahead() = " << ie.ahead() << "  ";
				if( ie.ahead()==ek )
				{
					ie.insertf(rep);
					++ie; ++ie; ++ie;
					ie.deletef();
				}
				else if( ie.ahead()==ekbar )
				{
					ie.insertf(repbar);
					++ie; ++ie; ++ie;
					ie.deletef();
				}
				else
				{
					++ie;
				}
// cout << "       image now " << jj.ahead() << endl;
			}
		}
	}

// cout << "Stage 3 complete." << endl;
// cout << images << endl;
//for(ii.init();ii.ok();++ii) cout << ii.ahead() << endl;

        // All images are currently of the form  W e Wbar,
	// where e is a circle.
        // First delete the Wbar from them all.

	ii.init();
	for(  k=0; k<n; k++ ) ++ii;		// Skip over the (empty) images of the circles.
        for(  k=0; ii.ok(); ++ii,++k )         // For each of the remaining images
        {
                int len=ii.ahead().length();
                LinListIterator<DE> j(ii.ahead());

                for( int jj=0; jj<(len-1)/2; jj++ ) {
// cout << j.ahead() << "  ";
							++j;}
		images[k].append(LinList<DE>(j.ahead())); // This is e, the image of the circle.
// cout << endl << images[k] << endl;
                while( j.ok() ) j.deletef();   		// Delete the Wbar
// cout << endl << ii.ahead() << endl;
        }
// cout << images << endl;
// cout << "Stage 4 complete" << endl;
	// Finally, tighten the images, i.e. remove any occurrence of a,abar for any a.
	ii.init();
	for(  k=0; k<n; k++ ) ++ii;		// Skip over the length-1 images of the circles.
        for( ; ii.ok(); ++ii )     // For each of the remaining images
        {
// cout << "Tightening image " << ii.ahead() << endl;	
tflag=0;
		LinListIterator<DE> j(ii.ahead());
		j.init();
		while(j.ok())
		{	
			if(!j.bok()) ++j;
			else
			{
				if( j.behind()==j.ahead().bar() )
				{
					j.deleteb();
					j.deletef();
tflag=1;
				}
				else
				{
					++j;
				}
			}		
		}
	}
// if(!tflag) cout << "No final tightening required" << endl;
// cout << "Tightening complete" << endl;
// cout << images << endl;
	// Preparation of map complete

	// Now initialize all the Homeo data
	// (other than theNameManager data which is already taken care of).

	LinListBrowser<DE> ie(edges);					// theMap
//	LinListBrowser<LinList<DE>> i(images);  // won't compile
	LinListBrowser<LinListDE> iii(images);
	for( ie.init(),iii.init(); ie.ok(); ++ie,++iii )
	{
		theMap.add(MapElement( ie.ahead(), DELList(iii.ahead()) ));
	}

	Vertex lastVertex;						// theGraph
	for(  k=0; k<n; k++ )
	{
		theGraph.add( Vertex( edges[k],edges[k].bar(),edges[n+k].bar()) );
		lastVertex.pushb(edges[n+k]);
	}
	theGraph.add( lastVertex );

	for(  k=0; k<n; k++ ) 					// theEquator
	{
		theEquator.append(edges[k]);
		theEquator.append( theNameManager.newPuncture() );
		theEquator.append(edges[k].bar());
	}
}