// Map.H
// John Ringland 8/20/95
//               9/27/95
//              10/10/95 
//	10/19/95  Testing.
//		  Added Constructors from MapElement(s).
//		  Fixed derivative.
//		  deleteAllBacktracking written and tested.
//		  int lengthOfImageOf(const DE&) written and tested.

// 10/19/95 imageOf could return a ref to the image.
//	    The initialization of the iterator and browser
//	    wouldn't need to be changed, and imageRef
//	    could be dispensed with.
//	    No. Not possible, because ref to image would not
//	    contain info about the sense in which it should be read.

//	10/19/95  renameDE modified and tested
//		  Other functions tested.
//		  Only remaining thing is the "emptyImage" function:
//		  not quite sure what to do with it.
//	10/26/95  Added namesInImageOf(const DE& e).
//		  Added isPermutation().
//		  Not yet tested.
//	1/1/96	  Added substituteInImages(const DE& e,const DELList& L).
//	3/7/96	  CAUTION. There was a really nasty bug in deleteDE, that
//		  might be prevalent!!!
//		  This is where a function is passed an argument BY
//		  REFERENCE, which may be to an object that will be
//		  changed by the function. Here we had a reference to
//		  an edge in theMap, and theMap was altered by the
//		  function -- invalidating the reference.
//		  REALLY MUST LOOK THROUGH ALL CODE TO ELIMINATE
//	          BUGS OF THIS KIND!
//		  Done for this file.
//	3/14/96   Added prependToImageOf(DE e,const DELList& L).
//	3/28/96	  Added minimalInvariantSetContaining(Name n).
//	4/13/96	  Added sameGate.
//	4/18/96   Moved theMap.substituteInImages to Homeo,
//		  because now Finger update required.


#ifndef MAP_H
#define MAP_H


#include "Set.H"
#include "DE.H"
#include "LinList.H"
#include "DELList.H"
#include "MapElement.H"
#include "Boolean.H"
//#include <iostream.h>
#include <iostream>
using namespace std;
#include <assert.h>

class Map: public Set<MapElement>
{
   public:
	Map() : Set<MapElement>()
	{}
	Map(const MapElement& me1) 
	: Set<MapElement>()
	{ add(me1); }
	Map(const MapElement& me1,const MapElement& me2) 
	: Set<MapElement>()
	{ add(me1); add(me2); }
	Map(const MapElement& me1,const MapElement& me2,const MapElement& me3) 
	: Set<MapElement>()
	{ add(me1); add(me2); add(me3); }
	~Map() {};

	DE derivative(const DE&) const;	// (first element of image)
	DE derivativeKTimes(const DE& e,int k);	
	
	DE popDg( DE );		// delete and return first element of
				// image of DE

	int lengthOfImageOf(const DE&);      

	Boolean deleteAllBacktracking();

        void renameDE(DE eold, DE enew );

	void deleteDE(DE e);

      	DELListIterator imageOf(const DE& d);
      	DELListBrowser  imageOf(const DE& d) const;
	DELList& imageRef( const Name& n );

	LinList<DE> commonLeadingSubimage( const DE& e1, const DE& e2 ) const;
	DELList copyOfImageOf(const DE& e) const;
	Set<Name> namesInImageOf(const DE& e) const;

	Boolean deleteElement( Name n );

	Boolean Map::isPermutation() const;

//	MapElement& emptyImage();	// Return ref to an empty image
					// or 0 if none exists
					// 10/19/95 Can't return null ref! 

//	void substituteInImages(DE e,const DELList& L);

	LinList<DE> step7part1() const;
	
	Boolean efficient() const;

	void prependToImageOf(DE e,const DELList& L);

	Set<Name> minimalInvariantSetContaining(Name n) const; // generateG0.c

	Boolean sameGate(DE e, DE f) const;
//OBS	Boolean iteratedDerivativesEventuallyTheSame( DE e, DE f, int nitmax ) const; // newAbsorb.c

//2002_12_27   friend ostream& operator << (ostream& out, const Map& s);
//2002_12_27   friend istream& operator >> (istream&  in, Set<MapElement>& s);

};


ostream& operator << (ostream& out, const Map& s)
{	  SetBrowser<MapElement> i(s);
	  out << "{ " << endl;
	  for(i.init(); i.ok(); i.advance()) out << "  " << i.current() << endl;
	  out << "}";
	  return out;
}

DELListBrowser Map::imageOf(const DE& d) const
{	
	SetBrowser<MapElement> i(*this);
	for( i.init(); i.ok(); i.advance() )
	{
	    if(i.current().source()==d) 
	    {   DELListBrowser tmp(i.current().image(),1);
		return tmp;
	    }
            else if( i.current().source()==d.bar() )
	    {   DELListBrowser tmp(i.current().image(),0);
		return tmp;
	    }
        }
cout << (*this) << endl;
cout << "has no image of " << d << endl;
	int No_image_in_Map_of_given_DE=0;
	assert(No_image_in_Map_of_given_DE);	
        // Means there's no image in Map of the given edge.
}

DELListIterator Map::imageOf(const DE& d)
{	
	SetIterator<MapElement> i(*this);
	for( i.init(); i.ok(); i.advance() )
	{
	    if(i.current().source()==d) 
	    {   DELListIterator tmp(i.current().image(),'f');
		return tmp;
	    }
            else if( i.current().source()==d.bar() )
	    {   DELListIterator tmp(i.current().image(),'b');
		return tmp;
	    }
        }
	int No_image_in_Map_of_given_DE=0;
	assert(No_image_in_Map_of_given_DE);	
        // Means there's no image in Map of the given edge.
}

DE Map::derivative(const DE& e) const
{
// JR 8/26/95
//    10/19/95 Redone.

	DELListBrowser i(imageOf(e));
	i.init();
	return i.ahead();
}

DE Map::popDg(DE e)
{
//   JR 10/19/95 
	DELListIterator i(imageOf(e));
	i.init();
	DE tmp(i.ahead());
	i.deletef();
	return tmp;
}



Boolean Map::deleteAllBacktracking()
{
	Boolean flag=0,flagi;
	SetIterator<MapElement> i(*this);
	for(i.init();i.ok();i.advance())
	{
		flagi=0;
		LinListIterator<DE> j(i.current().image());
// cout << "Tightening image " << i.current().image() << endl;	
		j.init();
		while(j.ok())
		{	
			if(!j.bok()) ++j;
			else
			{
				if( j.behind()==j.ahead().bar() )
				{
					j.deleteb();
					j.deletef();
					flag=1;
					flagi=1;
				}
				else
				{
					++j;
				}
			}		
		}
if(flagi) cout << "  Tightened image of " << i.current().source() << "." << endl;
	}
if(!flag) cout << "  There is no backtracking in the images." << endl;

	return flag;
}





int Map::lengthOfImageOf(const DE& e)
{
	return imageRef(e.name()).length();
}

void Map::renameDE(DE eold, DE enew )
{
        SetIterator<MapElement> i(*this);
        for(i.init(); i.ok(); i.advance() )
        {
                if( i.current().source() == eold ) 
                        i.current().source()=enew;
                else if( i.current().source() == eold.bar() )
                        i.current().source()=enew.bar();

                DELListIterator ii(i.current().image());
                for(ii.init();ii.ok();++ii)
                {
                        if( ii.ahead() == eold ) 
                                ii.replacef(enew);
                        else if( ii.ahead() == eold.bar() )
                                ii.replacef(enew.bar());
                }
        }
}

void Map::deleteDE(DE e)
{
	// Excise all occurrences of e from the images
	// and delete the element whose source().name() is e.name().

	deleteElement( e.name() );

        SetIterator<MapElement> i(*this);
        for(i.init(); i.ok(); i.advance() )
        {
                DELListIterator ii(i.current().image());
                for(ii.init();ii.ok();)
                {
                        if( ii.ahead().name() == e.name() )
			{
				ii.deletef();
			}
			else ++ii;	
		}
	}
}

LinList<DE> Map::commonLeadingSubimage( const DE& d, const DE& e ) const
{
        DELListBrowser id(imageOf(d));
        DELListBrowser ie(imageOf(e));

        LinList<DE> tmp;

        for( id.init(),ie.init();  id.ok() && ie.ok() ; ++id,++ie )
        {       if( id.ahead() != ie.ahead() ) break;
		tmp.append(id.ahead());
	}
        return tmp;
}

DELList& Map::imageRef( const Name& n ) // can't be const, because
					// returns ref to non const object
{
//cout << "Into imageRef:" << endl << (*this) << endl;
        SetIterator<MapElement> i(*this); // Can't be Browser because
					  // returns non const ref
         
        for(i.init(); i.ok(); i.advance() )
        {
//cout << "imageRef: " << i.current().source() << " -> " << i.current().image() << endl;

                if( i.current().source().name() == n )
		{ 
      			return i.current().image();
        	}
	}

	assert(0);  // Really want to return null reference.
		    // Apparently most compilers do not support
		    // null references (only null pointers).
//      return 0; // This doesn't do it, of course.
}

DELList Map::copyOfImageOf(const DE& e) const
{
        DELListBrowser i(imageOf(e));
        DELList tmp;
        for(i.init();i.ok();++i) tmp.append(i.ahead());
	return tmp;
}

Set<Name> Map::namesInImageOf(const DE& e) const
{
	DELListBrowser i(imageOf(e));
	Set<Name> tmp;
        for(i.init();i.ok();++i) tmp.add(i.ahead().name());
	return tmp;
}


Boolean Map::deleteElement( Name n )
{
        SetBrowser<MapElement> i(*this);
         
        for(i.init(); i.ok(); i.advance() )
        {
                if( i.current().source().name() == n )  
		{	remove( i.current() );
			return 1;
		}
                                                // horrrible!
        }
	return 0;
}
 

Boolean Map::isPermutation() const
{
	SetBrowser<MapElement> im(*this);
	Set<Name> presentInImages;
	for(im.init();im.ok();im.advance())
	{	
		if(im.current().image().length()!=1) return 0;
		if(!presentInImages.add
			(im.current().image().first().name()))
				return 0;	// not injective
	}
	return 1;
}        

void Map::prependToImageOf(DE e,const DELList& L)
{
	DELListIterator i(imageOf(e));
	i.init();
	DELListBrowser j(L);
	for(j.init();j.ok();++j) i.insertb(j.ahead());
}


Boolean Map::sameGate(DE e, DE f) const
{
	CircList<DE> itsOf_e;
	CircList<DE> itsOf_f;

	Boolean eCycleComplete=0;
	Boolean fCycleComplete=0;

	int k=0;
	while( 1 )
	{
		if(e==f)
		{	
			return 1;
		}

		if( eCycleComplete && fCycleComplete )
		{
			return 0;
			// (Cycles are either disjoint or identical.)
		}
		k++;
		e=derivative(e);
		f=derivative(f);
			
		if( !eCycleComplete )
		{
			if( !itsOf_e.has(e) ) itsOf_e.pushb(e);
			else
			{	// strip out the pre-periodic part
				while( itsOf_e.ahead()!=e )
					itsOf_e.popf();
				eCycleComplete=1;
			}
		}
		if( !fCycleComplete )	// ditto for f
		{
			if( !itsOf_f.has(f) ) itsOf_f.pushb(f);
			else
			{	// strip out the pre-periodic part
				while( itsOf_f.ahead()!=f )
					itsOf_f.popf();
				fCycleComplete=1;
			}
		}
	}
}

Boolean Map::efficient() const
{
	// For each edge, its image
	//	(1) must not backtrack, and
	//	(2) must determine different gates at each vertex.

	SetBrowser<MapElement> i(*this);
	for(i.init();i.ok();i.advance())
	{	
		DELListBrowser j(i.current().image());
		j.init();
		++j;
		for(;j.ok();++j)
		{	
			if( sameGate( j.behind().bar(), j.ahead() ) )
			{
/*
cout << "  Fibered surface is not efficient: "
 	<< "Dg^" << k << "("
     	<< j.behind().bar()
	<< ") = Dg^" << k << "("
	<< j.ahead()
	<< ")  ("
	<< derivative(e)
	<< "="
	<< derivative(f)
	<< ")"		
	<< endl;				
*/
cout << "  Fibered surface is not efficient: "
 	<< j.behind().bar() << ", "
	<< j.ahead() << " in same gate." << endl;				

				return 0;
			}

		}
	}

	return 1;
}

DE Map::derivativeKTimes(const DE& e,int k)
{
	// Return the kth iterate of e under Dg.
	DE dgke=e;
	while(k--)
	{
		dgke=derivative(dgke);
	}
	return dgke;
}


#endif